SmartLoc: sensing landmarks silently for smartphone-based metropolitan localization

The most popular outdoor localization method is GPS [14]. In an open environment, GPS could provide extremely accurate location information to the user and more improved techniques such as WAAS [32], and differential GPS (DGPS) [33] have been adopted in general civilian devices. Another feasible method is GSM-based localization [12], such as Nericell [21], which is widely available but with low accuracy (up to hundreds of meters). Also, it needs to know the exact position of cellular towers in advance.

Other techniques for both outdoor and indoor localization mainly fall into two categories: fingerprint-based and modeling-based. The main idea of the fingerprint is to first establish a database of signal fingerprint of each location based on the surrounding environment and then match the measured fingerprint to the database. The mapping returns the location with the most similar fingerprint. Modeling-based techniques rely on some theoretical or experimental signal propagation models, relating delay or strength to distance, and then calculate the location based on estimated distances.

In an indoor environment, Radar [34] collects WiFi fingerprints beforehand at known locations inside a building and identifies the user’s location using the matching fingerprint. It could achieve relatively high accuracy, with a median error of 2.94 m. Similar systems using RF signals include Horus [35] and LANDMARC [36]. Fingerprints generated through the combination of WiFi and FM are also studied in [37], which increases the accuracy by 83 % compared with WiFi fingerprint only. Unlike other systems mentioned above, SurroundSense [38] estimates the location in indoor environment through multiple ambience features, including the light, the color of the floor, the WiFi, and the sound. LiFS [19] does not have to know the APs’ location in prior, and the high location accuracy is achieved through exploiting user’s motion from crowdsourcing. PinLoc [39] uses physical layer information to locate users with the accuracy ∼89 %.

In an outdoor environment, both PlaceLab [1] and ActiveCampus [40] make full use of both WiFi and GSM signal for location. The former creates a map by war-driving a region and maps both APs and cell towers’ signal against the wireless map. The latter is quite similar except it assumes that the APs’ location is known prior. Taking advantages of both systems, CompAcc [17] uses dead-reckoning combined with AGPS to calibrate rather than preliminary war-driving. All these systems demand time-consuming calibration and are not suitable for a large-scale area, such as urban environments. StarTrack [41] provides a framework for track-based applications, which does not require precise location. However, our work mainly focuses on providing accurate real-time location in outdoor environments, which provides fundamental techniques for location-based service and navigation.

Other common ways to calculate location are based on the geometric model. In time-based techniques, time of arrival (ToA) [42], time difference of arrival (TDoA) [43], and angle of arrival (AoA) [44, 45] establish a geometric relationship between two separate devices and calculate the location. Although pleasing accuracy is achieved, the high cost cannot be neglected. In acoustic ranging, the distance of transmitter and receiver is estimated more precisely. Existing work includes Active Bat [46], Cricket [43], ENSBox [47], and WALRUS [48].

Liu et al. [20] calibrate the location accuracy in the WiFi fingerprint using a more accurate distance estimation from acoustic ranging. Centaur [49] combined acoustic ranging and RF measurement to locate a device in an office environment with acceptable accuracy. However, the acoustic approach is not suitable for large-scale localization either.

Several promising techniques such as crowdsourcing are introduced in localization recently, such as Zee [50], which also uses inertial sensors to track users’ movement. However, this inertial sensor-based approach is only suitable for indoor localization, and using such sensors for outdoor localization is more challenging.

Recently, dead-reckoning using internal sensors to estimate motion activities attracts a lot of research interests. For example, Strapdown Inertial Navigation System (SINS) [51] and Pedometer System [52] use MEMS to estimate the moving speed and trace. The key issue is to deal with noise of internal sensors, and the accumulated errors, which sometimes grow cubically [53]. Personal Dead-reckoning (PDR) system [11] uses “zero velocity update” to calibrate the drift. The majority of the dead-reckoning results focus on walking estimation, such as UnLoc [18] and CompAcc [17]. They mainly use an accelerometer to estimate the number of steps and then measure the distance through estimated step length. AutoWitness [13] is a system with an embedded wireless tag integrated with vibration sensors, accelerometer, and gyroscope. The tag is attached to a vehicle, and accelerometer and gyroscope are used to track the moving trace.

We dispatch four cars, driving through every road segment in the area, including the road infrastructure such as bridge and underground tunnels. While driving, we record the longitude, latitude, location accuracy, and driving speed in every 50 ms. The GPS location accuracy is provided in the GPS data collected from the smartphone. Meanwhile, we also periodically (20 Hz) collect all the sensory data coming from motion sensors, which will be used to identify the driving condition. To remove time-dependent GPS location errors, we conducted three independent measurements at three different times. The results reported here are the average of these three measurements.

Our measurements generated over 100,000 sample points during driving. The location accuracy was not so high as expected. The smallest error we collected from GPS was 5 m, while the largest error reached 400 m, which is nearly the length of three blocks downtown. Such a high error will lead to the wrong instruction for turning or stopping in the navigation.

We also calculated the proportion of different road segments with certain GPS localization error and plotted the results in Fig. 1 b. From this figure, we could find that only about half of the sampling points endure the error of less than 20 m, over one quarter of the locations have an error of about 50 m, and the rest of the quarter has an error larger than 50 m.

Localization is a fundamental step for navigation and location-based services. We assume that, while driving in metropolis, the largest location error we could accept should be less than a quarter of one block, which is about 30 m. For simplicity, we denote the position with GPS location error less than 30 m as the place with good GPS signal, and the rest as the position with poor GPS signal.

Our measurement shows that ≥25 % of sampling points have low GPS localization accuracy (i.e., with poor GPS signal). However, this does not imply that GPS cannot provide good navigation services. Typically, only under the circumstance that GPS localization accuracy is low for a whole segment of roads will the navigation system work poorly. For this reason, we then examined the length of continuous road segments that do not have good GPS signal, and we denote such road segment as “bad segment.” We find from our measurement that there are 182 straight bad segments of roads, see Fig. 2 a for some statistical information. The length of the longest bad road segments are almost 1 km, and the average length of all bad road segments is approximately 200 m, which is nearly two blocks. We also plot the number of bad segments in each length in Fig. 2 b. From this figure, we observe that there are about 9 bad segments with length over 400 m, which are all located in the center of downtown.

Since the behavior of the accelerometer acts like a damped mass on a string, the sensor in the device measures not only the linear acceleration applied to the device but also the force of gravity. In addition, the intrinsic noise of the motion sensors also affect the orientation estimation of the smartphone, which also leads to dramatic velocity and distance deviation eventually. To verify our assumption, we analyze noises in accelerometer with a set of experiments by putting the smartphone on a horizontal ground in different orientations. By transforming the acceleration from the device’s coordinate system to the Earth Frame Coordinate system, we plot both the mean value and standard deviation of acceleration in different axes in Fig. 3 a, b, respectively. From these two figures, it is obvious that the mean is not zero even when the phone is static, the readings of acceleration in three axes fluctuate frequently over the time domain, and the errors also change in different orientations.

In addition, the readings from magnetometer in the smartphone is sensitive to ambient environments, especially around a vehicle. We collect the magnetic field in three dimensions in two different scenarios: in and out of car, and calculate the mean value and standard deviation for three axes in different cases, illustrated in Fig. 3 c, d. From these figures, it is obvious that even if the smartphone is in the same position, the magnetic field readings differ a lot. Meanwhile, both means and standard deviations in the car are approximately over 100 times larger than that outside a car, which means even if the smartphone is stationary, the fluctuation is larger while driving. The key influence comes from the engine.

However, the performance of gyroscope is much stable than the others as can be seen in Fig. 3 e, f. These readings from all three scenarios are similar, which provide us a good opportunity to improve the device’s orientation estimation and the following trajectory calculation.

Note that the orientation of smartphone could be considered as the Euler Angle rotated around X, Y, and Z, the three axes of body frame coordinate sequently. The angle is presented as: pitch (θ), roll (ϕ), and yaw (φ), respectively. The orientation could be computed by

where G _u is the unit vector of the acceleration and both E _u and N _u are the unit vector of y direction and the magnetic north, respectively.

After we fixed the smartphone on the windshield, we first wait for approximately 10 s to calculate the initial orientation. The reason for this process is to eliminate the device-dependent errors and fluctuation on sensory data. We take the average gravity, and magnetic field as \(\overline {G}_{1}\), and \(\overline {B}_{1}\), respectively, and calculate the initial orientation based on Eq. (1).

In the following sensor fusion process, the estimated orientation and measured orientation in EKF are based on gyroscope and a combination of accelerometer and magnetometer. The orientation in time k is related to the posteriori estimation of orientation in time k −1. We present the non-linear stochastic difference equation as:

where q _k indicates the estimated orientation at time k, Q _am denotes the orientation based on current accelerometer and magnetometer, and \(\widetilde {q}_{k}\) presents the priori estimate at time k, which is calculated through last orientation and rotation increment. Here, A, h _k , and R _k are the Kalman gain, measurement matrix, and rotation increment, respectively.

The rotation increment is the changing rotation angle at time slot k, and \(\overline {R_{k}}\) is given as:

where Δ t is the time interval of sampling, and Ω is

The EKF will bring a continuous changing orientation of smartphone, and the improved orientation in the following time slots will be:

Rotating the linear acceleration from BFC to EFC, the calculating of velocity and driving distance from the starting point is feasible.

In SmartLoc, the system updates the latest location for a certain time interval, denoted as Δ t; therefore, the distance from starting point after one time slot could be described by the linear state equation:

where \(\widetilde {X}_{k}\) is the current estimated distance from the starting point at time slot k, X _k−1 is the distance from starting point at previous time slot, V _k−1 is the velocity of vehicle at beginning of time slot k, and a _k is the acceleration during time slot k. Equation (6) could be presented recursively as:

However, in practice, both V _i and a _i contain large noises. Suppose the noises of V _i and a _i obey normal distributions, and the standard deviations of these noises are σ ₁ and σ ₂, respectively. The standard deviation on the estimated distance error will be: \({(k-1)}\cdot {\sigma _{1}}\cdot {\Delta {t}} + \frac {1}{2}\cdot {\Delta {t}^{2}}\cdot {k}\cdot {\sigma _{2}}\). Therefore, with the increase of dead reckoning duration (k Δ t), the accumulated errors will increase more than linearly. Such errors, in a long run, are inevitable, and our extensive real world experiments confirm it.

We then establish a model to calibrate the location based on both GPS information and sensory data.

Speed estimator: The true velocity V _i at the end of a timeslot i could be represented as

where β is the parameters learnt and adjusted in real time, a _s is the mean of the measured acceleration data during the timeslot, and μ is the noise. Thus, when GPS signal is strong, we will compute V _i and V _i−1 from GPS values. The measured acceleration a _s will be computed from accelerometer. Then, using linear regression, we find the best β.

When GPS signal is weak, we will use the model to estimate the velocity V _i .

Distance estimator: When GPS signal is strong, let G(Δ(t)) be the moving distance during timeslot i from GPS, which still contains errors (denoted as η). This distance provided by GPS could be denoted as \(G(\Delta {t}) = {\lambda }_{1}\cdot {V_{i-1}}\cdot {\Delta {t}} + \frac {1}{2}\cdot {a_{r}}\cdot {\Delta {t}^{2}} + \eta \), where a _r is the actual unknown acceleration in timeslot Δ t. Here, λ ₁ is used to reflect possible error in the estimated speed V _i−1 for timeslot i−1. We only know the measured acceleration a _s , which could be denoted as a _s =(1+ε)a _r +δ. In this work, we use the following formula to estimate the distance G(Δ t):

where λ _i are the parameters to be learnt by linear regression. When GPS signal is strong (GPS error is ≤20 m), based on the value of V _i−1 and a _s estimated from the sensor data in every sample point, we train the parameters λ _i in Eq. (9). These parameters will be used by dead reckoning to predict the moving distance S(Δ t) in the timeslot i when GPS signal is as weak as the following:

From the estimated moving distance S(Δ t), we can estimate the location at timeslot i.

As we mentioned previously, the road infrastructures, including tunnels, bridges, crossroads and traffic lights, cause large noises in the data collected from inertia sensors, which also result in a large drift in the estimated moving distance if they are not treated rigorously. In this work, we exploit the precise location of these infrastructures that are available in Google Map to calibrate the localization as landmarks without any extra cost.

Traffic light: While driving in many large well-organized cities, such as Chicago, one often encounters traffic lights. When the vehicle stops by the traffic lights, and then drives through the crossroad, there is a unique pattern reflected by motion sensors, as shown in Fig. 4 a. When vehicles face traffic lights, the pattern could be considered as the combination of braking and speeding up. The acceleration falls below zero when the car brakes, reaching the lowest point at the very moment when the vehicle stops, and gets back to zero swiftly. As soon as the green light turns on, the vehicle speeds up with the acceleration increases. However, in rush hours, the real location where the car stops may not be at the crossroad but with a certain distance away from the crossroad. In this case, SmartLoc will adjust the moving distance based on the estimated stopping location from empirical data, i.e., subtracting the distance from the car to the crossroad.

Turning: Sometimes, vehicles may face both traffic lights and turning at the same time. During the turning, all the motion sensors will detect the turning. Figure 4 b indicates the centripetal force sensed by the accelerometer, and the scale of the acceleration depends on the speed that the vehicle is turning. Simultaneously, the angular velocity sensed by gyroscope also reaches up to 0.5 r a d/s in our test case in Fig. 4 c, and the data from the magnetometer changes as well, with large fluctuations as shown in Fig. 4 d. Finally, the orientation of smartphone will also change approximately 90 ^o when turning left or right. Such angle change is observed mainly along the Z axis on EFC, and the readings of 0, 90, 180, 270 represent north, east, south, and west, respectively. Although the angle may not be accurate enough due to the large noises in magnetometer (the maximum error we experienced in our tests was about 30 ^o ), we can still correctly determine the road segment to which the car is turning. In Fig. 5 a, the vehicle turns from north, the angle changes from about 350 ^o to 100 ^o , which is east. We also compare the measured angle difference for turning and changing lanes, as shown in Fig. 5 b. The amplitude of angle difference when a car changes lanes is much smaller than that when a car turns into a different road segment. In addition, we calculate the standard deviation for angle differences for lane changing, which is below 10 in most of the cases. Thus, determining the turning and the direction of driving is feasible. We conduct more study on the driving orientation estimation. Figure 5 c plots the raw trace of the vehicle through GPS, where the GPS signal is good. And Fig. 5 d illustrates the corresponding raw orientation generated through inertial sensors. We employ slide window to eliminate some noise and calculate the driving orientation, which matches the ground truth.

Bridges: Other possible road infrastructures that a vehicle may experience are bridges and tunnels. In our measurement, such patterns are more obvious and easier to be detected. Having been converted from BFC to EFC, the acceleration along the gravity will be less than 1G when the car is driving uphill and larger than 1G when downhill. A bridge or a tunnel often has both uphill and downhill pattern, as shown in Fig. 4 e.

We then present the localization results of SmartLoc in Chicago downtown. As aforementioned, it is difficult to get the ground truth for the majority of the sampling locations. We set the goal of localization is to find the final location. Since, Section 3 has demonstrated that there are nine bad road segments with lengths over 400 m, which is less than three blocks in downtown Chicago. The goal of SmartLoc is then to obtain a relatively accurate location estimation within three blocks. We randomly select 100 points as destinations in the experiment, and a destination could be one block, two blocks, or three blocks away from the starting point. We drive to these destination points to evaluate if the location of the destination can be precisely calculated by SmartLoc. We assume that the GPS signals are good before the starting point, and SmartLoc trains the dead-reckoning model during the driving. In this experiment, we test the accuracy of estimating the location of each sampling point in every time slot and of estimating the location of the final destination, as shown in Fig. 10 a, b, respectively. When SmartLoc only navigates to the destination within one block, with probability 70 %, the error of estimating the location for each sampling slot is less than 10 m, and with probability 85 %, the mean error is less than 30 m. When the destination is two blocks away, about 75 % of the errors are less than 30 m; when the destination is three blocks away, about 80 % errors are less than 50 m. From these results, the error of destination locating within a few blocks is acceptable. We also plot the localization results for one road segment with length over 6400 m in Fig. 11. In this figure, the red spots denote the ground truth generated from GPS, and the blue spots represent the localization calculated by SmartLoc, where the green line between them is the localization error for every location. It is clear that with longer segment the accuracy of localization is pretty good.

SmartLoc provides the location through both GPS and inertial sensors. Empirically, the profiles of energy consumption for GPS module and inertial sensors in smartphones are different. The average electric current of GPS module in Android smartphone is approximately 135 mA, which is larger than that of motion sensors [54]. In addition, Android API provides four rate modes of delivering sensory data, which are Fastest, Game, UI and Normal. The Fastest mode delivers the sensory data without any delay; thus, the energy consumption is the largest (95 mA [54]), while the Normal is the slowest, and also the most energy efficient one (15 mA [54]). Clearly, SmartLoc can reduce the energy consumption by leveraging inertial sensors instead of GPS compared with the approach using only GPS.

Suppose the energy cost of a GPS module for every time slot is E _GPS , and the energy cost of inertial sensors are E _AMG . Obviously, E _AMG ≤E _GPS . Generally, the main purpose of the GPS is calibration and training, as shown in Fig. 12, where GPS indicates the localization through the GPS, and AMG denotes the location estimation through motion sensors. Initially, during T ₁, the system will train the model and calculate suitable parameters through the linear regression, and such parameters will be employed in estimating the trajectory in T ₂. Periodically, SmartLoc will calibrate the location from dead-reckoning when GPS signal becomes good again in T ₃, and the parameters will be updated. Then the ratio of saved energy will be \(\frac {(E_{GPS} - E_{AMG})\cdot {T_{2}}}{E_{GPS}\cdot {(T_{2} + T_{3})}}\). The durations of T ₁, T ₂, and T ₃ will affect the acceptable accuracy and energy consumption of localization of SmartLoc. Our first experiment is taken under the circumstance of activating all the motion sensors and GPS modules, the driving duration lasts for 30 min, and the battery of smartphone discharges from 84 to 70 %. Similarly, GPS localization for half an hour will lead to the drop of battery from 70 to 61 %. In most of our cases, in order to get higher accuracy, the ratio between training duration and estimating duration is ranging from 6:3 to 8:3. For example, in the experiment shown in Fig. 8 c, the training distance is about 3400 m and SmartLoc estimates the following 1200 m (with GPS off), which reduces the energy by approximately 10 % without affecting the localization accuracy. Note that as long as the GPS signal is strong during T ₁ and T ₃, we can turn off GPS in T ₂. If GPS signal is weak in T ₁ or T ₃, we can keep the GPS alive for longer periods. Another possible working pattern is turning the GPS on/off according to the condition of the GPS signal. When GPS signal is good, SmartLoc turns the GPS to calibrate the system parameters, turns off the GPS when signal is weak, and then use the newly updated parameters to calculate the driving speed and distance.