Assist GPS to Improve Accuracy Under Complex Road Conditions Using Sensors on Smart Phone

Abstract

This paper presents the design and implementation of a new vehicle tracking technology. It can assist GPS to achieve high precision under special situations. For example, the situations when the road conditions are complex or the GPS signal strength is weak. In our method, the barometer data and acceleration data are used to assist the GPS data, and the Hidden Markov Model is used to assist the location tracking. We make two key technical contributions. The first is to propose a Hidden Markov Model to combine the barometer and accelerometer reading hints for estimating the location of the vehicle. The second is to design some novel techniques for parameter estimation. The experiment shows that the accuracy of our method is improved by 19.2% compared with GPS under these special situations.

1 Introduction

Location tracking techniques are now widely used in many location based services, such as car navigation [9] and logistics management [13]. The GPS (Global Positioning System) has high precision outdoors, making it the most used technology for location tracking. However, the GPS positioning accuracy will be greatly affected in some scenarios. For example, there will have large error when the GPS signal is bad, and the tracking accuracy will be affected in complex road conditions. Also, when there are roads interlaced, the GPS tracking accuracy can be influenced. More detail: 1) when the car is driving in a tunnel or under dense tall buildings, the GPS signal will be very weak, and the tracking cannot be precise. 2) when the car is passing the overpass, there may be several roads at different altitudes but under the same GPS longitude and latitude. The altitude provided by GPS can have an error of tens of meters, which is not accurate enough to know which road the car is driving on. A typical example is at car navigation, if the car goes to the wrong route when passing the overpass, the existing GPS based system cannot re-locate the car and recalculate the navigation route. Based on the above observations, an approach to improve the accuracy of GPS based vehicle tracking in such particular situations is desperately needed.

In order to improve the accuracy of GPS based vehicle tracking, the most common method is to utilize the accelerometer and compass for inertial navigation [4, 5]. However, the sensors are noisy and the error of accelerometer and compass will accumulate [8] over time. Moreover, when it comes to complicated road conditions such as interlaced roads, even with the assistance of accelerometer, the GPS still can not realize precise tracking. Other techniques such as Wi-Fi [12] or cellular network [20] based positioning and tracking are not suitable here because they need infrastructure support and are not accurate enough [21].

In this paper, we believe that except for GPS, accelerometer and compass readings, there are also other information which can help us achieve more precise location tracking [6, 7]. Take the barometer sensor on smart phone as an example, it can senses the precise altitude change of the car, which can help improve the tracking accuracy on the elevated roads and overpasses where the altitude changes along the road. Real-time traffic congestion and road conditions data can also help location tracking.

In this paper, we put forward a new solution to satisfy the need for accurately tracking a car in many situations. Our solution is to utilize the data collected from barometer and accelerometer to assist GPS. All of these sensors can be found in smart phones nowadays. We will feed the sensor data to a Hidden Markov Model (HMM) to derive the location list that the car is driving through. Generally, to solve this problem, we will face the following challenges: a) The sensor data are noisy, they need to be preprocessed before use. For example, the barometer reading will be affected by the weather, which should be handled carefully. b) We will have to design some methods for initializing the parameters for HMM.

In general, in this paper, we made the following contributions:

• We proposed an HMM based method to effectively combine different sensor readings to solve the problem.

• We designed some novel techniques for parameter estimation of the model.

• We improved GPS accuracy when tracking a moving car in particular situations by 19.2% compared to traditional GPS based method.

In the rest of this paper, we first discuss the problem definition and modeling in Sect. 2. Later we solve the model in Sect. 3. Section 4 shows the evaluation results of the proposed method. Section 5 shows the related work and finally Sect. 6 concludes this paper.

2 Problem Definition and Modeling

Figure 1 describes the overall structure of our method. First of all, the left part shows the application scenario of the method. Our method is designed to assist GPS in tracking the car under complex road conditions. The figure shows the scene of the car driving on the complex overpass. The locations in the figure are the real locations of the car passing by, but due to GPS error, we can not get the exact locations. The middle part of the figure shows the data obtained by mobile phone, they are road map, GPS data, barometer data and acceleration data. After preprocessing these data, we can convert them into the parameters needed by HMM. The part on the right shows the model we used. We use HMM to predict the most likely driving path of the car. We get the emission probability through GPS data and barometer data, and the transition probability through GPS data and acceleration data.

Fig. 1.

Overview of our method.

The following content of this section contains two parts. The first part gives some basic definitions and describes the problem that needs to be solved. The second part introduces how to solve this problem through HMM.

2.1 Problem Definition

First some notations will be defined in Table 1 to make our problem definition clearer.

In this paper, we will use barometer data and acceleration data to assist GPS to improve the tracking accuracy of GPS under special circumstances. Specifically, we solve the problem by using a probabilistic model called HMM. This model can help us get a sequence of unobserved states which is also called hidden states. In our solution, the hidden states are the passing-by locations of the car which we can not observe directly due to GPS error. Also, the observed readings of GPS, barometer and accelerometer depends on the hidden states. Based on the above observations, we define the problem as follows.

Problem Definition. For a moving car, given the road map M, number of time stamp T, and all the observation readings—GPS readings $\{g_{t}\}_{t=1:T}$, barometer readings $\{b_{t}\}_{t=1:T}$ and accelerometer readings $\{a_{t-1,t}\}_{t=1:T}$. The purpose is to accurately infer the hidden location list Trace = $\{l_{t}\}_{t=1:T}$ of the car.

Table 1. Notations and meanings for problem definition

Table 2. Notations and meanings for modeling

2.2 Hidden Markov Model

Before introducing the model, some notations with their meanings are defined in Table 2.

In order to solve the problem, HMM is used in this paper. It is a probabilistic model and one of its applications is to get the hidden states based on the observed values. In this problem, the observed values are the GPS data, barometer data and acceleration data recorded by the mobile phone sensors in time series. The hidden states are the car’s passing-by locations. There are two variables and three parameters of HMM, two variables are the state variable ${(x_1,x_2,...,x_t,...,x_T)},x_t\in {X}$ and the observation variable ${(y_1,y_2,...,y_t,...,y_T)},y_t\in {Y}$. State variable is also called hidden variable. Given a road map M, the state space X is all the location points on the map, and the state variable is the driving trace of the car. $y_t$ in observation variable represents the observation value at time stamp t under hidden state $x_t$. Then three parameters of hidden Markov model are as follows.

Initial state probability matrix $\varPi$. The initial state probability matrix is actually the probability that the car may start from each state in the state space. The initial state probability matrix is represented as $\varPi =(\pi _1,\pi _2,...,\pi _N)$. Each element $\pi _i=P(x_1=s_i),{1}\leqslant {i}\leqslant {N}$ in $\varPi$ denotes the probability that the car begins form location state $s_i$.

State transition probability matrix $\mathbf {A}$. The state transition probability refers to the probability that every state in the state space is transferred to every other state. The size of the state transition probability matrix is $N*N$. Each value in the state transition matrix is denoted as $a_{ij}=P(x_{t+1}=s_j|x_t=s_i)$, ${1}\leqslant {i,j}\leqslant {N}$. It represents the probability of transitioning from the location state at time t to the state at time $t+1$.

Emission probability matrix $\mathbf {B}$. The emission probability refers to the probability of observation value taking $o_j$ at time stamp t, given the hidden state $s_i$. It can be represented as $b_{ij}=P(y_t=o_j|x_t=s_i),{1}\leqslant {i}\leqslant {N},{1}\leqslant {j}\leqslant {M}$. Thus the size of emission probability matrix is $N*M$.

Now that we have got the three required parameters, we get the HMM $\lambda = (A, B,\varPi )$. Next we will get the most likely state sequence that produces the observations by using Viterbi algorithm. It is given by the following recurrence relations,

$$\begin{aligned} \begin{aligned}&V_{1,k}=P(y_1|k)\cdot \pi _k&\\&V_{t,k}=P(y_t|k)\cdot max_{x\in X}(e_{x,k}\cdot V_{t-1,x})&\\ \end{aligned} \end{aligned}$$

(1)

Here $V_{t,k}$ is the probability of the most probable state sequence responsible for the first t observations that have k as its final state. $e_{x,k}$ represents the probability of transitioning from state x to state k. The Viterbi path can be retrieved by saving back pointers that remember which state x was used in the second equation.

3 Solve the Model

This part will introduce how to solve the model proposed in the previous part, mainly introduce how to obtain the three parameters of HMM, and then use a modified Viterbi algorithm to solve our model to get the trace of the car.

Firstly, GPS data, barometer data and acceleration data can be acquired continuously in time series from sensors in mobile phone. After collecting these data, we pre-process these data using pre-processing method like [19]. Since the barometric pressure and altitude can be converted into each other, we convert the barometric pressure to altitude, and the conversion formula is as follows,

$$\begin{aligned} h=44300*(1-(\frac{p}{p_0})^{\frac{1}{5.256}}) \end{aligned}$$

(2)

In (2), h represents altitude, p represents barometric pressure and $p_0$ is the sea level standard atmospheric pressure. Next part of this section will introduce how to get the three parameters of HMM.

Fig. 2.

Probability density function of initial location state.

Get initial state probability matrix $\varPi$. The initial state probability is the probability that the car may start from each state of the state space. The state space X in our case refers to all the location points on the map, therefore N is very large, and it will cause too much calculation. However, as the initial state’s GPS value is known, the probability of location points far from the GPS value is close to zero, and the number of these points is very large, so in order to reduce the complexity of calculation, we only consider the location points on the road within the error range of initial GPS value, and then calculate their probability according to the distance between them and the initial GPS location. We assume that the distance follows the normal distribution $N(0,\sigma ^2_{gps})$, where $\sigma _{gps}$ is the error range of GPS, we give it a value of 10 m on normal road and 100 m when in tunnel. Figure 2 shows an example of getting the initial state probability, we map the longitude and latitude to a two-dimensional road map and divide each road into multiple location points. We get the probability density of each point through the normal distribution probability density function shown as follows.

$$\begin{aligned} f(g_{initial})=\frac{1}{\sqrt{2\pi }\sigma _{gps}}exp(-\frac{g_{initial}^{2}}{2\sigma _{gps}^{2}}) \end{aligned}$$

(3)

In (3), ${g_{initial}}$ represents the distance between the first GPS point and its surrounding points within the error range $\sigma _{gps}$. Once we have got the probability density of each location state, next we can get the initial state probability matrix $\varPi$.

Get state transition probability matrix ${\varvec{A}}$. The state transition probability in our case refers to the probability that the car move from the previous location point at time t to the next location point at time $t+1$. The size of A is $N*N$ and N is very large, so it needs to be reduced properly to reduce the computational complexity. In our case, we only need to calculate the probability of points within the error range of the previous GPS point transfer to that of the next GPS point. The size of the state transition probability matrix can be reduced to $n*m$. n and m respectively refer to the number of location points within the error range of the two GPS points. Based on the above analysis, the size of state transition probability matrix changes dynamically between each two location states.

To estimate the transition probability for each location state, we utilize the accelerometer reading $\{a_{t-1,t}\}_{t=1:T}$ and the GPS reading $\{g_{t}\}_{t=1:T}$. Next part will introduce how to calculate the transition probability between each two location states.

First, the distances between all the location points within the error range of the previous GPS point and the next GPS point are calculated respectively and the results are represented as $S_{g}$. The size of $S_{g}$ is $n*1$. Then we get the average speed of the car by dividing the duration time $v_{g}=S_{g}/t_{dur}$.

Then according to the acceleration reading, the car speed at the previous GPS sampling point and the sampling interval time, the displacement between the two GPS sampling points can be calculated by the displacement formula, the formula is as follows.

$$\begin{aligned} S_{a}=v_{0}t_{dur}+\frac{1}{2}\sum _{i=1}^{t_{dur}}a_{i-1,i} \end{aligned}$$

(4)

In (4), $v_{0}$ represents the car speed at the previous GPS sampling point, $a_{i-1,i}$ represents the acceleration reading of every second in a sampling time interval. $t_{dur}$ is the interval time between each two sampling. Then we get the average speed of the car by $v_{a}=S_{a}/t_{dur}$.

Now that we have got the average speed of the car in two ways, respectively represented as $v_{g}$ and $v_{a}$, Then we get the final average speed of the car by giving both of them a weight. It can be represented as

$$\begin{aligned} v_{avg}=av_{g}+bv_{a}\quad (a+b=1) \end{aligned}$$

(5)

We define $a=0.4$ and $b=0.6$ because the distance calculated from GPS data has relatively higher error than that of acceleration data.

Next we will calculate the distance matrix between all location points on the road map M within the error range of the former GPS point and that of the next GPS point, it is represented as $S_{l}$ and the size of it is $n*m$. Then we get the average speed matrix by formula $v_{l}=S_{l}/t_{dur}$.

For each row of $v_l$, we assume that their values follow the normal distribution $N=(v_{avg},\sigma _v^2)$, where $v_{avg}$ is the expected value and the standard deviation $\sigma _v$ is 10% of $v_{avg}$. The probability density function for average speed $v_{avg}$ is as follows.

$$\begin{aligned} f(v_{l})=\frac{1}{\sqrt{2\pi }\sigma _{v}}exp(-\frac{(v_{l}-v_{avg})^2}{2\sigma _{v}^2}) \end{aligned}$$

(6)

In this way, we can get the state transition probability matrix A, the size of it is $n*m$.

Get emission probability matrix ${\varvec{B}}$. Finally we will estimate the emission probability for each observation. We use the combination of GPS reading $\{g_{t}\}_{t=1:T}$ and barometer reading $\{b_{t}\}_{t=1:T}$ as the observation. In the problem to be solved, emission probability refers to the probability of taking the GPS reading and the barometer reading under every hidden state. Similarly, the size of emission probability matrix is also reduced to reduce computational complexity.

We divide the computation of emission probability into two parts, one is the GPS emission probability, the other is the barometer emission probability, and then combine them to get the final emission probability. The specific steps are as follows.

Get GPS reading emission probability. According to the GPS value sampled at time t, the location points on the road map M within its error range are got. Assuming that the distance $g_{l}$ between the GPS sampling point and these location points follow the normal distribution, the probability of these points is calculated. The following formula is the normal distribution probability density function for GPS reading.

$$\begin{aligned} f(g_l)=\frac{1}{\sqrt{2\pi }\sigma _{g}}exp(-\frac{g_l^{2}}{2\sigma _{g}^{2}}) \end{aligned}$$

(7)

In (7), $\sigma _{g}$ is the error expectation of GPS. And $f(g_{l})$ is the probability density of $g_{l}$. Then we can get the emission probability $P_g$ of GPS reading.

Get air pressure emission probability. According to the air pressure value sampled at time t, for the location points within the error range of GPS reading at time t, it is assumed that the air pressure values at these points also follow the normal distribution with respect to the sampled barometer reading. The following is the normal distribution probability density function for barometer reading.

$$\begin{aligned} f(b_{l})=\frac{1}{\sqrt{2\pi }\sigma _b}exp(-\frac{(b_l-b_t)^{2}}{2\sigma _{b}^2}) \end{aligned}$$

(8)

In (8), $b_l$ represents the barometer reading of the surrounding location points, however actually we can not get the barometer value of location points from the map, we can only get the altitude information of every location point. Based on the above observation, we transfer the barometer reading $b_t$ to altitude. We represent the altitude of hidden state at time t as $h_t$ and transfer formula (6) as follows.

$$\begin{aligned} f(h_{l})=\frac{1}{\sqrt{2\pi }\sigma _h}exp(-\frac{(h_l-h_t)^{2}}{2\sigma _{h}^2}) \end{aligned}$$

(9)

In (9), $h_{l}$ represents the altitude of one of the surrounding locations. $\sigma _{h}$ is the error expectation of altitude. Here we set the value of $\sigma _{h}$ to be 1 m. Finally, $f(h_{l})$ is the probability density of parameter $h_{l}$. Then we can get the emission probability $P_h$ of air pressure.

Now that we have got the probability of GPS reading and barometer reading, then we will combine them together to get the emission probability.

$$\begin{aligned} B=P_g*P_h \end{aligned}$$

(10)

Finally, with the above three parameters of HMM, we maximize the probability with Viterbi algorithm and get the most probable trace of the car, thus we can determine which road on earth the car is driving on and then navigate it accurately.

Fig. 3.

Roads map for experiment.

4 Evaluation

In this part, we will analyse the results of experiment and evaluate the effect of our method. First, we will introduce our experimental environment. We choose Xinzhuang overpass and Xuanwu Lake Tunnel in Nanjing for experiment. Figure 3 shows the map of roads for our experiment. The color change on roads represents altitude change of road. The color bar on the right shows the color of altitude. We divide these roads into five parts as shown in Fig. 4, and carry out experiments on them respectively. The arrows on each map indicate the direction of the road. Road 1 has a diversion point, and one branch road turn around and pass under the main road. Road 2 has two diversion points and road 3 has a three-branch diversion point, they both contain changes in altitude. Road 4 has no fork but changes in altitude. Last the tunnel has almost no changes in altitude and no fork but GPS signal is very weak in it.

Fig. 4.

Map of each road

The purpose of the experiment is to test the locating accuracy of our method under complex road conditions and compare it with GPS. We record a car’s driving information from the smart phone, including GPS information, barometer information and acceleration information. The sampling frequency of the information is once every 2 s, and our method is executed every 10 s to track the car. The map information in the experiment was obtained from Baidu map, we divided each road into many location points, and the distance between each two points was 1 m. We only map the longitude and latitude of GPS reading to the map and don’t use its altitude. We get altitude from barometer reading. Next, we will evaluate the experimental effect from several aspects.

4.1 Compare Our Method with GPS

The method proposed in this paper aims to assist GPS tracking in complex road conditions, so we need to compare it with GPS. Figure 5 shows the comprehensive locating accuracy of the two methods on all roads (excluding tunnel). As can be seen from the figure, the overall effect of our method is better than GPS. The locating accuracy of our method is 79.2% within 8 m, while that of GPS is 60%.

Fig. 5.

The locating accuracy comparison between our method and GPS.

Next, we will separately compare the effects of the two methods on four roads. Figure 6 shows the comparison of the two methods on different roads. As can be seen from Fig. 6, the effect of our method on each road is better than that of GPS. However, there are some places where the two curves intersect, and the difference is not big. This is because in some cases, for example, there are no interlaced roads, that is, there is no altitude difference, the method in this paper can not really play its advantages.

Fig. 6.

Locating accuracy comparison of our method and GPS on each road.

4.2 Verify the Effect of Barometer Data on Accuracy

In order to verify the influence of air pressure data on locating accuracy, we will compare the method in this paper with that only using GPS and acceleration data. Figure 7 shows the comprehensive locating accuracy comparison of the two methods on all roads (excluding tunnel). It can be clearly seen from the figure that the effect of the method proposed in this paper is better. Therefore, we verify that the barometer data is helpful to improve the locating accuracy.

Fig. 7.

Locating accuracy of our method and no barometer data method.

Next, we will analyze the four roads respectively to verify the impact of barometer data on locating accuracy, and the effect is shown in Fig. 8. In Fig. 8 (b)(c), the curve overlaps because the barometer data can not play its role fully without altitude difference, while some parts of road 2 and road 3 don’t have obvious altitude change, so the effect of the two methods is almost the same under this situation.

Fig. 8.

Locating accuracy contrast on four roads.

4.3 Verify the Effect of Acceleration Data on Accuracy

In the method proposed in this paper, we use acceleration to calculate the transfer probability matrix in HMM. If we don’t use acceleration data, we can’t use HMM. Next, we will compare the method in this paper with the method using only GPS and barometric data.

Fig. 9.

Locating accuracy of our method and no acceleration data method.

Figure 9 shows a comparison of the locating accuracy of the two methods on all roads (except tunnel). It can be seen from the figure that the two curves have intersecting parts, and the difference between the two curves is relatively small when the abscissa is the same. It is because they all use the barometer data and this is very useful when there are altitude changes during driving the car. Although the effect of these two methods on overpasses is similar, their effect in tunnels is quite different. We will discuss the situation of tunnels separately later.

4.4 Comparison of the Effect of Four Methods on Overpass

The above three comparisons are actually the comparison between the three different methods and the method proposed in this paper. Next, we will compare the four methods together.

Figure 10 shows a comparison of the locating accuracy of the four methods together. Figure 11 uses a bar chart to compare the effects of the four methods. The abscissa represents the error range, and the ordinate represents the proportion of the error range. It can be seen from the figure that the method in this paper accounts for the highest proportion when the error is in the range of 0–5 m, while in the range of 10–15 m, the method in this paper accounts for a relatively low proportion, indicating that the method error is mainly concentrated in the low error area. We can clearly figure out that the method in this paper and the method using only GPS and barometer data are better than the other two methods without air pressure data on overpass.

Fig. 10.

Locating accuracy comparison of four methods on overpass.

Fig. 11.

Locating accuracy comparison of four methods on overpass.

Fig. 12.

Locating accuracy comparison of four methods in tunnel.

Fig. 13.

Locating accuracy comparison of four methods in tunnel.

4.5 Compare the Effect of Four Methods in Tunnel

The above only evaluates the effect of these four methods on overpass, and next we will separately evaluate their effect in the tunnel. A comparison of their locating accuracy is shown in Fig. 12. It can be seen from the figure that in the tunnel, the effect of our method is obviously better than other methods and GPS works worst in tunnel.

Figure 13 analyses the proportion of several error ranges in detail. It can be seen from the figure that $60\%$ of the error of our method is within 20 m, and the proportion of error over 60 m is zero. We can figure out that the effect of our method is better than other methods in tunnel.

5 Related Work

In recent years, there have been some methods proposed for vehicle tracking. The conventional way is to use GPS/INS integration system [4, 5]. However, the error will accumulate over time. To solve the problem, authors in [8] introduced the development of a two-filter smoother (TFS) algorithm to improve the accuracy. Authors in [1] used a reduced inertial sensor system (RISS) instead of the full INS to improve the accuracy of the overall system. Authors in [11] proposed that extended Kalman filter (EKF) and Unscented Kalman Filter (UKF) be used to improve the accuracy. Authors in [18] design an adaptive dual-rate EKF estimator for fusing data from GPS and an INS in order to estimate the position.

Also, other sensors are used to assist GPS. Authors in [14] utilizes magnetometer and barometer to assist GPS/INS system. Authors in [10] proposed a method using odometer and barometer to integrate with GNSS/INS system. However, compared with our method, they need extra devices while our method only uses sensors on the smart phone, which is very portable.

In addition to GPS/INS integrated methods, some other methods have been proposed for location tracking. Authors in [2, 22] employed a dead-reckoning algorithm for localization. Authors in [6] demonstrated how mobile devices can be used to accurately track driving patterns based solely on pressure data collected from the device’s barometer. It only uses the barometer while our method is a combination of GPS, barometer and accelerator, which will have higher accuracy. Authors in [7] showed us how to use the barometer on the smart phone to improve vertical positioning accuracy. While our method can derive a track of the car instead of a single positioning point. Other techniques such as WheelLoc [15] only made use of low power sensors and cell tower information, but the accuracy was not good enough compared to our method. Authors in [3] extended the sensor management strategies of the EnTracked T system that intelligently determines when to sample different on-device sensors (e.g., accelerometer, compass and GPS) for trajectory tracking. Authors in [16, 17] designed a mobile system that effectively captures significant journeys based solely on the embedded barometer sensor of a smart phone. However, it based on the analysis of a large amount of history data while our method is a real-time locating and tracking method.

As for the usage of HMM in tracking, authors in [19] proposed a HMM based method called BTrack. It can assist users to track their location on mountain roads. While our method in this paper focuses on track vehicle on the roads especially in situations such as tunnel and overpass where GPS error is large or GPS signal is weak.

6 Conclusion and Discussion

In this paper, we propose a novel method to assist GPS tracking. We use barometer data and acceleration data, combined with GPS data from the sensors on the smart phone, and use HMM to calculate the most likely driving path of the car. We only use the sensors on smart phones, do not need extra devices. We have carried out experiments on a complex overpass and in a tunnel. The experimental results show that the accuracy of our method is 19.2% higher than that of GPS. Also, the experiment results show that the comprehensive locating accuracy of our method is better than that of other methods. However, our method still has some defects, that is, it works better when there is obvious altitude change. In addition, our method uses HMM to calculate and the energy consumption is not considered. In our future work, we will consider improving the method to reduce the energy consumption and achieve higher accuracy.