**Jianjun Yin**

Department of Electronic Engineering, Fudan University, China

Ming Gu

Suzhou-CAS Semiconductor Integrated Technology Co., Ltd, China

Jianqiu Zhang

Electronic Engineering Department, Fudan University, China

Department of Electronic Engineering, Fudan University, China

Ming Gu

Suzhou-CAS Semiconductor Integrated Technology Co., Ltd, China

Jianqiu Zhang

Electronic Engineering Department, Fudan University, China

A novel dynamic state space model was established for Global Positioning System (GPS) navigation by adopting the polynomial predictive filtering idea and state dimension expansion. We called the new model expanded state space model which was established without the exact knowledge of the original state dynamics, i.e., we way use the proposed model to describe the state dynamics no matter we know the original state propagation well or not. A correspondent Expanded State Space Kalman filter (ESSKF) was then presented based on the proposed model. The results of the GPS navigation examples demonstrated that the proposed method did work better than the existed Extended Kalman Filter (EKF), especially in the situations that the state dynamics were not known well.

PDF Abstract XML References Citation

Jianjun Yin, Ming Gu and Jianqiu Zhang, 2011. The Expanded State Space Kalman Filter for GPS Navigation. *Information Technology Journal, 10: 2091-2097.*

**DOI:** 10.3923/itj.2011.2091.2097

**URL:** https://scialert.net/abstract/?doi=itj.2011.2091.2097

The Global Positioning System (GPS) is part of a satellite-based navigation system. It estimates a user's position and velocity from the delay and Doppler of direct-sequence code-division multiple-access signals sent by satellites. Because of its confidence and usefulness, GPS is utilized in numerous civil and military applications, ranging from golf and leisure hiking to spacecraft navigation (Grewal *et al*., 2001). In recent years, a rich of filtering algorithms have been applied in GPS navigation. They offer efficient and iterative means of combining information from sensor(s) to estimate the state such as the position and velocity of a vehicle. At each iteration, the future state is predicted using a state model. Then the measurements of sensor(s) are used to update the estimate of the state. The state model essentially allows past state information to be projected forward in time and combined with current measurement information (Grewal *et al*., 2001; Lehmann, 2009). Yamaguchi and Tanaka (2006), was used the Kalman Filter (KF) for the of improvement of the GPS positioning precision under small number of satellites used for calculating. The authors adapted the Kalman filter to GPS positioning calculating when they could see only 3 satellites in the sky. It is concluded that the positioning precision of the proposed method was improved as compared with the algorithm of least mean square. Guo *et al*. (2010), was used the KF for GPS/magnetometer integrated navigation system, which improved the accuracy. Hwang and Speyer (2011), was applied the Particle Filter (PF) to the relative position estimation using GPS carrier-phase measurements. The probability density function of the position was estimate by sampling from the position space with the particle filter and the ambiguity problem was resolved without any integer ambiguity search procedures. Koyama *et al*. (2009), was adopted the KF for GPS measurement of a motorcycle trajectory, where the trajectory with excellent continuity and stability were obtained even in the situation that the observation data were missed within a few seconds. In addition, the extended Kalman filter was used to make the trajectory smooth and the trajectory with high accuracy which is sufficiently continuous, was got.

Note that the KF and PF above work well only if the state transition density or dynamics is known. When the state dynamics is not known exactly, the filters may not provide correct results, sometimes even be divergent, i.e., they may not provide correct position and velocity estimations in GPS navigation. Polynomial Predictive Filter (PPF) is an effective way to predict future signal values (Valiviita *et al*., 1999; Tanskanen, 2000). Future estimates of the signal are produced by extrapolating and it turns out that the coefficients of the filter are not dependent on the signal but only on the values assigned to the degree of polynomial model, the number of latest samples and the forward prediction step. In this study, we firstly use polynomial predictive filter to construct the process model for GPS navigation by expanding the dimension of the state, i.e., the expanded state at the current time step consists the original state at the current time step and those of several backward time steps. In this way, we may obtain the expanded state dynamics for GPS navigation whether the original state transition density is known exactly or not. Similarly we expand the measurement model for the pseude ranges. A new dynamic state space model-the expanded state space models-for GPS navigation is established by the combination of the expanded process and measurement models. Then the Expanded State Space Kalman Filter (ESSKF) is presented based on the proposed expanded GPS navigation model. Simulation results show that in the situations that the state dynamics are not known well, the proposed method still works well while the existed Kalman filter does not.

**BACKGROUND**

According to Weierstrass approximation theorem, for a continuous real-valued signal, it can always be divided into lots of sequential closed and bounded intervals in which the signal can be uniformly approximated by low degree polynomials to any degree of accuracy. In this section, we recall the polynomial predictive filter (Tanskanen, 2000). Suppose that the signal x_{k} can be modeled as a polynomial with low degree L, then we have:

(1) |

where, p_{1} is the polynomial coefficients. We may have:

(2) |

when signal x_{k} does not fit the polynomial model exactly and w_{k} is an error term. In turns out that predictions using polynomial models can be done by taking a weighted average of the past few values of the signal and that the weighted coefficients are not dependent on the signal but only on the values assigned to polynomial degree, number of prediction steps and the length of the filter (Valiviita *et al*., 1999; Tanskanen, 2000), i.e., for exactly polynomial signals, a future value x_{k+N} can be obtained as:

(3) |

where, N and M denote the number of prediction steps and the length of the filter, respectively, h_{m} are the filter coefficients. Substituting (1) into (3) yields:

(4) |

Then, we have:

(5) |

which yields:

(6) |

for *l* = 1, ..., L. We know that in the case of FIR filter, the noise gain can be expressed as (Tanskanen, 2000):

(7) |

The purpose is to minimize Eq. 7 under the constraints of Eq. 6. This is done using the method of Lagrange multipliers by considering Eq. 7 as the function to be minimized and the L+1 equations of Eq. 6 as the constraint functions. Then we can construct a Lagrange function as follows:

(8) |

Then we get:

(9) |

Where:

(10) |

and

(11) |

For example, with N = 1, L = 1, h_{m} becomes:

(12) |

with N = 1, L = 2, h_{m} becomes:

(13) |

with N = 1, L = 3, h_{m} becomes:

(14) |

**EXPANDED PROCESS MODEL CONSTRUCTION FOR GPS NAVIGATION**

Firstly, we consider the process model. Suppose that the true model is as follows:

(15) |

where, n_{k} is the process noise and f_{k} (.) is unknown. By the knowledge of polynomial predictive filter reviewed in last section, we rewrite Eq. 15 as:

(16) |

where, v_{k+1} is a noise term and it is zero if x_{k} is a strictly polynomial signal. Further more, Eq. 16 can be rewritten in an expanded form:

(17) |

Where:

(18) |

(19) |

(20) |

Suppose that v_{k} is white Gaussian with mean zero and covariance Q and it is independent at different time steps. Then is also white Gaussian with mean zero and covariance Q_{ppf}, i.e.,

(21) |

where, *l* is the dimension of the original state.

**THE ESSKF FOR GPS NAVIGATION**

**Regular motion:** Suppose that the user motion is regular, i.e., constant velocity motion or constant acceleration motion, in which the user positions can be expressed by polynomials exactly. Then the expanded process model Eq. 17 can be reduced to the following according to the comments after Eq. 16:

(22) |

We now consider the correspondent measurement model. Suppose that the original pseudorange measurement model is as follows (Kaplan and Hegarty, 2006):

(23) |

(24) |

where, x_{k}, y_{k}, z_{k} are the x, y, z positions of the user, x_{ik}, y_{ik}, z_{ik} are the x, y, z positions of ith satellites, i = 1, 2, 3, 4, c is the light speed, t_{k} is the clock bias, t_{k} is white Gaussian with mean zero and covariance R. Then we may rewrite Eq. 23 in an expanded form corresponding to Eq. 17, i.e.,

(25) |

Where:

(26) |

Suppose that W_{k} is independent at different time steps, the covariance of can be expressed as:

(27) |

Then we have the expanded dynamic state space model for GPS navigation which is comprised of Eq. 22 and 25, where, and are expanded state and measurement, respectively, and are expanded process and measurement noises, respectively. By applying the extended Kalman filter (EKF) to Eq. 22 and 25, we have:

(28) |

Where:

are the state prediction and estimate, respectively, P_{k+1|k}, P_{k+1|k+1} are the predict covariance and estimate covariance, respectively, K_{k+1} is the Kalman gain and:

(29) |

(30) |

(31) |

**Irregular motion:** We know that generally the user motion is irregular, i.e., the acceleration may change with time, which means that the user positions can’t be exactly expressed by polynomials. In this situation, the expanded dynamic state space model for GPS navigation is comprised of Eq. 17 and 25. By using the EKF, we have:

(32) |

The equations in system 32 are the same as those in (system 28 to 31) except the P_{k+1|k}. In Eq. 32, there exists one more item, Q_{ppf} which denotes the uncertainty of the expression by polynomials as in Eq. 21.

**Discussions and implementation issues:** According to the Weierstrass theorem, the user positions can be divided into some sufficient small sequential intervals, which are approximated by low degree polynomials, respectively. Thus it can be expressed by Eq. 17 to 21 with small Q_{ppf} or sometimes even zero Q_{ppf}. Figure 1 gives an illustrative example. However, at the junction point of two adjacent intervals, there exists changes, for instance, in the acceleration. This means there will be a transition stage near these discontinuity points before the algorithm converges again. In the following, we will discuss how to detect these discontinuity points and how to shorten the transition stage.

It is well known that the innovation sequence is a Gaussian white noise sequence with mean zero under steady state (Melrra, 1970) while it dose not have this statistical property when the filter is not under steady state, i.e., the mean of the innovation sequence is not zero, or even far from zero near the junction/discontinuity points as shown in Fig. 1. So the mean of the innovation sequence can be used to identify whether the process model is good or not. The innovation and its covariance can be presented as:

(33) |

(34) |

then is a χ^{2} variable with m freedoms which corresponds to the dimensions of innovation. At a given significant level α, the condition indicates the mean of innovation sequence is non-zero, i.e., discontinuity occurs, otherwise when , the process model goes well (Melrra, 1970). If discontinuity occurs, the state prediction using process model is not accurate enough, more information contained in incoming measurements should be used, i.e. the Kalman gain K_{k+1} should be enlarged. From Eq. 32, we may obtain the Kalman gain as follows:

Fig. 1: | Low degree polynomials expression |

(35) |

i.e., K_{k+1} will increase as the covariance of process noise, Q_{ppf}, increases. So when discontinuity is detected, i.e., , we may use a lager Q_{ppf}, e.g., is a large positive integer, then we may obtain:

(36) |

where,“→”denotes tend to, then:

(37) |

Otherwise, when , which means that Eq. 22 goes well, then we may use a small Q_{ppf}, or even, Q_{ppf} = 0.

Note that the estimate we get at time k+1 is the expanded state , we may obtain the original state estimate just by reserving the first component of and discarding the others, i.e., according to Eq. 18, we may rewritten as:

(38) |

and we just need to discard .

**DEMONSTRATION RESULTS IN GPS NAVIGATION**

The process model used in the existed EKF is the well-known WNA model as follows (Bar-Shalom *et al*., 2001),

(39) |

where, x_{k} = [px_{k}, py_{k}, pz_{k}, vx_{k}, vy_{k}, vz_{k}], px_{k}, py_{k} and pz_{k} are the user position in x, y, z axes, respectively, vx_{k}, vy_{k} and vy_{k} are the corresponding speeds and F_{k} = (1, 0, 0, dT, 0, 0; 0, 1, 0, 0, dT, 0; 0, 0, 1, 0, 0, dT; 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 1, 0; 0, 0, 0, 0, 0, 1)^{T}. Γ = (dT^{2}/2, 0, 0; 0, dT^{2}/2, 0; 0, 0, dT^{2}/2; T, 0, 0; 0,T, 0; 0, 0, T)^{T}. The measurement model used in the existed EKF is Eq. 23.

The satellite data used are as follows (Grewal *et al*., 2001).

Table 1: | GPS satellite data |

where, the angle Ω_{0} is the right ascension of the satellite and θ_{0} is the angular location of the satellite in its circular orbit. It is assumed that the satellites orbit the earth at a constant rate θ with a period of approximately 43082s or slightly less than half a day (Grewal *et al*., 2001). The equations of motion that describe the angular phasing of the satellites are given, as in the simulation:

In the simulation, the parameter used in the proposed ESSKF is N = 1, L = 2, M = 3 then according to Eq. 13, we obtain h_{0} = 3, h_{1} = -3, h_{2} = 1 which can be used to calculate F_{ppf} according to Eq. 19 easily.

**Example 1-regular motion:** Suppose that the user motion is regular with constant acceleration a, initial velocity V and total time simulation is T, the time step interval dT. In the simulation: T = 150s, dT = 1s, a [1; 1; 1], m sec^{-2}, V = [0, 0, 0] m sec^{-1}the process noise covariance in EKF is blkdiag (σ^{2}_{v1}, σ^{2}_{v2}, σ^{2}_{v3}) with σ^{2}_{v1} = 30, σ^{2}_{v2} = 9, σ^{2}_{v3} = 1, the measurement noise covariance is σ^{2}_{w} = 36 for each satellite. The results in detail are listed in Table 2, where it is shown that the propose algorithm is better that the existed EKF, especially in terms of stability, i.e., the standard deviations are much smaller.

**Example 2-irregular motion:** Suppose that the acceleration is a within time interval (0, T_{1}) and a_{1} within time interval (T_{1}, T). In the simulation: T_{1} = 70s, a_{1} = 10xa, a = [3; 2; 1]^{T}m sec^{-2}, V = [30; 20 ; 10] m sec^{-1}. The other simulation data are the same as those in example 1. Figure 2 shows the absolute estimation error in x position (top one), y position (middle one) and z position (lower one), where solid lines with dots represent the results of the existed EKF, the solid lines represent the results of the proposed ESSKF. It can be seen from Fig. 2 that the proposed ESSKF still works well when the acceleration is changed, however, the existed method does not provide true estimates.

Table 2: | Simulation results (regular motion) |

Fig. 2: | Absolute errors in position estimation |

In this study, we presented a new dynamic filtering method called the Expanded State Space Kalman Filter (ESSKF) for GPS navigation, where the system state dimension is expanded by the combination of the original state at current time step and those of backward time steps. By using the ESSKF we may get accurate estimation of the user position even in the situation that the user state dynamics is not known well. The simulation results demonstrate the good performance of the proposed ESSKF over the existed EKF when the state dynamics is not known well.

The work reported in this study was funded under the National Natural Science Foundation of China under Grant No. 60872059 and the National Basic Research Program of China (2011CB302900).

- Lehmann, F., 2009. Deterministic particle filtering for GPS navigation in the presence of multipath. AEU-Int. J. Electron. Commun., 63: 939-949.

CrossRefDirect Link - Yamaguchi, S. and T. Tanaka, 2006. GPS standard positioning using kalman filter. Proceedings of the SICE-ICASE International Joint Conference, Oct. 18-21, Busan, South Korea, pp: 1351-1354.

CrossRef - Guo, H., M. Yu, C. Zou and W. Huang, 2010. Kalman filtering for GPS/magnetometer integrated navigation system. Adv. Space Res., 45: 1350-1357.

CrossRef - Koyama, Y., T.K. Liang and T. Tanaka, 2009. High-precision GPS measurement for motorcycle trajectory using kalman filter. Proceedings of the Sixth International Conference on Networked Sensing Systems, June 17-19, Pittsburgh, PA., USA., pp: 1-4.

CrossRef - Valiviita, S., S.J. Ovaska and O. Vainio, 1999. Polynomial predictive filtering in control instrumentation: A review. IEEE Trans. Ind. Electronics, 46: 876-888.

CrossRef - Melrra, R.K., 1970. On the identification of variance and adaptive Kalman filtering. IEEE Trans. Autom. Control, 15: 175-184.

CrossRefDirect Link