Trans. Nonferrous Met. Soc. China 24(2014) 1554-1561
Hybrid particle filtering algorithm for GPS multipath mitigation
Nan-shan ZHENG1,2, Liang-shi CAI1, He-fang BIAN1, Cong LIN1
1. School of Environment Science and Spatial Informatics, China University of Mining and Technology, Xuzhou 221116, China;
2. NASG Key Laboratory for Land Environment and Disaster Monitoring, Xuzhou 221116, China
Received 7 October 2013; accepted 20 January 2014
Abstract:
An alternativeor mitigating GPS multipath ilter and wavelet transform with particle filter. algorithm for mitigating GPS multipath was presented by integrating unscented Kalman filter (UKF) and wavelet transform with particle filter. Within consideration of particle degeneracy, UKF was taken for drawing particle. To remove the noise from raw data and data processing error, adaptive wavelet filtering with threshold was adopted while data preprocessing and drawing particle. Three algorithms, named EKF-PF, UKF-PF and WM-UKF-PF, were performed for comparison. The proposed WM-UKF-PF algorithm gives better error minimization, and significantly improves performance of multipath mitigation in terms of SNR and coefficient even though it has computation complexity. It is of significance for high-accuracy positioning and non-stationary deformation analysis.
Key words:
particle filtering; wavelet transformation; global positioning system (GPS); multipath mitigation;
1 Introduction
The global positioning system (GPS) is a prominent system for providing precise positioning with high sampling rates, and has been widely applied to monitoring deformation with real-time mode. Among the potential sources of GPS signal degradation, multipath maintains a major error impairing accuracy and precision of GPS positioning [1,2]. GPS multipath phenomenon occurs when GPS signals travel from a satellite to an antenna of GPS receiver via several paths due to reflection or diffraction of signals by nearby obstacles. These systematic errors can be substantial and may lead to range errors on the order of meters for the pseudorange and several centimeters for phase measurements. With the advent of high-rate applications, errors due to multipath are now of greater concern [3].
Various multipath mitigation strategies have been studied, which are categorized in terms of antenna design, improved receiver internal architecture, and post-processing. Obviously, hardware- based or signal-based approaches have improved the positioning accuracy to a certain extent [4]. Further improvement taking advantage of data processing schemes has been performed, which can be classified as time-domain and frequency-domain processing.
Pertaining to time-domain processing, carrier smoothing takes advantage of the fact that carrier phase measurement errors typically are negligible compared with code multipath. Optimal combination of carrier phase and code measurements can efficiently reduce the code multipath to centimeter level and have been widely used. Backward filtering and variable length least mean square adaptive filter for carrier phase multipath mitigation was proposed [5,6], whereas a prerequisite is reference station free from multipath, and signals of interest also tend to be filtered out. Another research interest is focused on modeling approach, which takes advantage of periodic characteristic to map the multipath environment [3,7].
The methods within frequency domain are based on spectral analysis of GPS multipath using fast Fourier transform (FFT) or wavelet decomposition [8,9]. However, multipath mitigation technique based on wavelet transformation is affected by the determination of wavelet bases and wavelet decomposition levels. Thus, an EMD-wavelet systematic error mitigation model was proposed [10]. Furthermore, neural network method to solve pseudorange equations has also been employed [4,11].
In addition, a range of schemes are focused on taking advantage of signal-to-noise (SNR) measurements at ground reference stations [12-15].
In recent literatures [16,17], particle filtering has received much attention in multipath estimation, which is a promising alternative for dealing with non-stationary observations compared with Kalman filtering and its extensions.
In this work, an alternative particle filtering is to be proposed to mitigate GPS multipath. It integrates unscented Kalman filter and wavelet transformation with particle filtering. The aim is not to find more accurate modeling for multipath, but reduce multipath effect within the solutions from GPS relative positioning. Therefore, this work focuses on studying hybrid particle filtering for multipath mitigation and analyzing its performance.
2 GPS multipath
2.1 Description of GPS multipath
The reflected signal caused by the vicinity of GPS stations takes more time to reach GPS receiver antenna than the direct or LOS (line-of-sight) signal. The magnitude and the phase of reflected signals depend on surface property of the reflecting objects and on the geometry between GPS satellite, receiver antenna and reflectors. For illustrating GPS multipath propagation, it is assumed that a signal from a single incoming direction is reflected along a single outgoing direction (Fig. 1) [16]. In practice, this assumption is an exception rather than a rule.
2.2 GPS observation models
The multipath distorts the C/A-code and P-code modulations, as well as the carrier phase observations [4]. There are some carrier phase frequencies for GPS, such as L1 (1575.42 MHz), L2 (1227.60 MHz), L5 (1176.45 MHz). These frequencies can also be expressed as a wavelength, where the wavelengths of L1, L2, and L5 are 19.03 cm, 24.42 cm and 25.48 cm, respectively. The mathematical models for GPS code measurements and carrier phase measurements are given as Eqs. (1) and (2) [1,2].
(1)
(2)
where ρ and 
indicate code measurement and carrier phase measurement. Certainly, the measurements for different frequencies are similar. r is the true range from a satellite to a receiver, and c is WGS-84 propagation constant. δts and δtu stand for satellite and receiver clock bias whereas I, T, M ρ, υρ, M, υ denote ionospheric refraction, tropospheric delay, code multipath, random noise on code, carrier phase multipath, random noise on carrier respectively. N and λ are carrier phase ambiguities in cycles and wavelength of GPS signal, respectively.
Fig. 1 Schematic diagram of GPS multipath propagation
While processing by double difference scheme for GPS observables, most spatially correlated errors within direct observables are eliminated within context of short GPS baseline. The residual can be considered multipath, antenna phase center variation and noise. Thus it is significant to study error sources and outlier identification [18,19]. Carrier phase multipath and receiver noise are independent for each receiver. Because the antennas at both ends of the baseline view the satellites at approximately the same elevation angles, differential solution can largely eliminate antenna errors while utilizing the antennas from the same type. It is acceptable that the remaining errors for a short baseline would be multipath and noise [2]. Therefore, removal of multipath becomes essential for high-accuracy GPS applications.
3 Hybrid particle filtering for GPS multipath mitigation
3.1 Particle filtering algorithm
About an introduction to particle filtering theory and practice with positioning applications, it can be cited in Refs. [20-23]. The particle filtering algorithm is to perform a recursive Bayesian filter by Monte Carlo simulations. The key is to represent the required posterior density function by a set of random samples, which is called particles with associated weights, and to compute estimates based on these samples as well as weights.
Its goal is to compute filtered estimates of x0:t taking into account all available measurement up to time t, z1:t. In practice, the solution is to recursively obtain a posterior probability density function p(x0:t|z1:t) of states at time t given all available measurements. Particle filter represents the posterior probability density function by a set of random samples with associated weight as follows:
(3)
where each particle with index i has a state 
; δ(x) is Dirac delta function; 
is associated weight with ; Np stands for the particle number; z1:t denotes the measurements accumulated up to t. The weight is always positive, 
, and sum over all weights is equal to 1. If computation load can bear, Np is expected large enough.
The state of each particle is drawn randomly from the importance sampling distribution, and one choice for the distribution is a prior probability distribution. The state can therefore be represented as
(4)
where 
denotes the state transition probabilities.
The sequential weight updated at each step can be calculated from
(5)
where the initial weight is set as 
.
3.2 Hybrid filtering algorithm
Even though particle filtering is effective for nonlinear filtering, particle degeneracy and the selection of importance density function are still essential to be studied. Herein, the work intends to put forward a hybrid particle filtering algorithm for GPS multipath mitigation, named WM-UKF-PF which takes advantage of unscented Kalman filtering and wavelet transformation. While drawing new particles, unscented Kalman filtering is taken into account. Because direct measurements are to be utilized, the proposed algorithm becomes more robust. In particular, wavelet transformation is taken to denoise while data preprocessing and drawing particles. The procedure is described as follows.
1) Decompose: to perform multi-scale decomposition for original data, and find out a prior distribution. In this research, original data is a certain solution with respect to GPS data processing scheme, which is recognized as a compound signal composed of multipath bias, receiver noise and environmental noise.
2) Initialise: to draw new particle 
in terms of a prior distribution p(x0).
3) Predict and update with UKF: to calculate with unscented Kalman filter and to update the weight for each sampling 
by Eq. (6).
(6)
where K and P denote gain matrix and error variance matrix, respectively.
4) Denoise and draw new particle: Firstly, denoising by wavelet adaptive filtering with threshold is performed. Then, new particle is to be drawn according to importance sampling. Finally, the new weight is calculated by Eqs. (7) and (8), and normalized to sum to unit.
(7)
(8)
where 
stands for importance density function and can be expressed as
5) Resample and compute effective number of particles:
, where 
is the normalized weight of particle i on the time step t. While Neff＜Nth, resampling is necessary to be performed. In general, the threshold Nth is specified 2/3Np. The degree of degeneracy can be assessed by the effective number of particles approximately, which is given by Neff. Resampling is to be applied whenever Neff falls below a threshold.
6) State output: 
.
7) Update with time and draw new particle.
8) Set k to k+1, and then go to step 3).
4 Experimental
To evaluate the performance of proposed algorithm, an experimental study is described.
4.1 GPS experiment
In this experiment, two receivers, named as GPS base station and rover station, were taken to acquire original observables [24]. Figure 2 illustrates the configuration of GPS positioning experiment. GPS base station is located at the open surroundings, in other words, no obstacle affects GPS signal transmission and the site station has excellent satellite visibility and minimal multipath sources. GPS rover station is set nearby the higher building, where is susceptible to be suffered from multipath due to obstacles. The baseline length between two GPS receivers is around 25 m. The sampling interval of GPS receivers is 5 s. Because multipath bias is environment-dependent, the differential GPS which is employed to minimize the spatially correlated errors does not sufficiently work for GPS multipath mitigation. Here, to evaluate proposed algorithm, the differential solution of both GPS stations was taken as study object.
Fig. 2 Configuration of GPS instruments
The coordinate sequences of two consecutive days in latitudinal/longitudinal direction are calculated by differential positioning scheme, as shown in Figs. 3 and 4. The correlation of multipath error is not significant in adjacent period. In general, the precision of horizontal component of GPS solutions is more satisfactory than that of its elevation component for high-precision deformation monitoring, herein only horizontal components are taken into account.
Fig. 3 Coordinate difference sequences of two consecutive days in latitudinal direction
Fig. 4 Coordinate difference sequences of two consecutive days in longitudinal direction
4.2 Filtering algorithms for GPS multipath mitigation
To mitigate GPS multipath effects, it aims to estimate the state of the multipath xk at the current time step k, given a set of measurements (observations) Zk={z0, …, zk } acquired at time steps 0, 1,
, k. The state of GPS multipath is composed of two components of latitude and longitude.
The state transition model (system or motion model) is given by
(9)
where 
is the process noise that is independent of the past and current states, which is assumed to obey normal distribution N(0, 0.0012) in this experiment.
The state measurement model is described as
(10)
where νk is the measurement noise independent of the past and current states as well as the process noise, which accounts for uncertainty in observations.
To take advantage of exceptional characteristics of particle filtering and to evaluate the performance of proposed algorithm, three algorithms related to particle filter for mitigating GPS multipath are performed, extended Kalman filtering and particle filtering (EKF-PF), unscented particle filtering (UKF-PF), and wavelet transformation and unscented particle filtering (WM-UKF-PF). In particular, the performance of the proposed algorithm WM-UKF-PF is compared with the other two approaches, namely EKF-PF and UKF-PF.
For particle filtering algorithm, it is not significant to select initial value because the state vector becomes convergent gradually after updating. However, the distribution of measurement noise has much more effect on filtering. Therefore, it is of great significance to determine a priori distribution of measurement noise.
4.3 Performance of filtering algorithms for multipath mitigation
Taken the 1st day observation as instance, wavelet adaptive filtering was conducted, where Daubechies 3 wavelet was selected and the decomposition scale was specified to be 4 (Fig. 5). It shows that observation noise dominantly distributes in the layers of d1, d2, d3 and d4 corresponding to this experiment. The mean and variance of observation noise are -1.33×10-8 (close to 0) and 1.26×10-4, respectively (Fig. 6).
Suppose that a prior probability is normal distribution p(x0)~N(0, 0.0012), the initial x0 is sampled in terms of p(x0), particle number n is given as 500, the important density function is specified as
, and the resampling threshold is set as Nth=n/3.
Fig. 5 Multi-scale decomposition with wavelet (scale=4)
Fig. 6 Noise extracted within observation signal
Before proposed algorithms are taken to deal with the GPS differential solutions from two consecutive days, they have been processed to be two components of latitude and longitude in advance. To illustrate the performance of different algorithms, firstly both EKF-PF and UKF-PF have been adopted for multipath mitigation, and the results are shown in Figs. 7 and 8. This indicates that EKF-PF is not satisfactory to complicated signal, and observation noise has much more effect on the filtering solution. While suffering from observation noise, GPS receiver noise and random noise, the precision processed by EKF-PF has not provided good performance, moreover, it is sensitive to signal anomalies and prone to be divergent.
Fig. 7 Multipath in latitudinal component with EKF-PF
Fig. 8 Multipath in latitudinal component with UKF-PF
In contrast, unscented particle filtering is able to identify multipath from the observation noise. However, random noise is still included in the filtering solution and regional divergence occurs. It is found that the initial error has been recognized little in advance, as to result in denoising insufficiently. Hence, the hybrid algorithm of wavelet transformation and unscented particle filtering (WM-UKF-PF) is presented, and the result is shown in Fig. 9.
Fig. 9 Multipath of two consecutive days in longitudinal direction extracted by WM-UKF-PF
After comparing filtering results from three algorithms, the performance of EKF-PF is not acceptable enough because the initial value and system equation are hard to be defined in advance. Extended Kalman filtering has divergence according to final solution and error scatter graph (Fig. 10 and Fig. 11). However, it is found that the hybrid algorithm of unscented particle filtering and wavelet transformation has better performance.
Fig. 10 Multipath in latitudinal direction identified by three methods (West-East)
In Table 1 and Table 2, root mean square (RMS) and signal noise ratio (SNR) with respect to three algorithms are computed. Herein the SNR calculated by TEQC software is taken as the reference.
Fig. 11 Errors in latitudinal direction derived from three filtering methods (West-East)
Table 1 RMS of three algorithms (m)
Table 2 SNR of filtered signal (db)
WM-UKF-PF gives the error minimization and maximal SNR. In other words, the results indicate that WM-UKF-PF has better performance for removing multipath from GPS differential solutions.
The periods of GPS satellite are 11 h and 58 min. In two consecutive sidereal days, the satellite on the second day occurs 3 min and 56 s earlier than that on the first day. The correlations of two consecutive days in two directions are calculated (see Table 3). Because WM-UKF-PF can effectively eliminate noise, the correlation has been improved by 54.75% and 41.78%, respectively after filtering. This demonstrates that the proposed method can mitigate multipath bias effectively. In addition, random noises are still included in the filtered results to some extent, which are likely to multipath signal from far away and GPS receiver noise. They have no significant effect on the variation of multipath bias and can be ignored.
Table 3 Correlation coefficients of two directions before and after filtering
5 Conclusions
1) A hybrid algorithm of unscented Kalman filtering and wavelet transformation with particle filter for mitigating GPS multipath effects is provided. The main advantages of proposed WM-UKF-PF algorithm are error minimization and greater SNR corresponding to final solution. Within context of this study case, RMS reaches 1.9 mm, and SNR is higher than that by TEQC solution.
2) The correlations of filtered solution in two consecutive days have been improved by over 40% with the application of WM-UKF-PF. It also demonstrates that the proposed methodology has better performance for GPS multipath mitigation. In addition, this method is independent of the GPS receiver technology so that it can be widely utilized for post-processing. It is necessary to be mentioned that the hybrid algorithm has computation complexity.
3) GPS multipath by far has been especially challenged due to its nature, remaining as the most significant obstacle to high-accuracy positioning and non-stationary deformation extraction. Due to the complexity and variation of environments, further research is recommended to thoroughly understand the effects of propagation for GNSS signal within different scenarios as well as to make full use of GNSS reflected signal.
References
[1] HOFFMANN-WELLENHOF B, LICHTENEGGER H, COLLINS J. GPS: Theory and practice [M]. Wien: Springer, 2001.
[2] LEICK A. GPS satellite surveying [M]. 3rd ed. New York: Wiley, 2004.
[3] LARSON K M, BILICH A, AXELRAD P. Improving the precision of high-rate GPS [J]. Journal of Geophysical Research: Solid Earth, 2007, 112(B5), doi:10.1029/2006JB004367.
[4] LEE Y W, SUH Y C, SHIBASAKIA R. A simulation system for GNSS multipath mitigation using spatial statistical methods [J]. Computers & Geosciences, 2008, 34 (11): 1597-1609.
[5] GE L, HAN S, RIZOS C. Multipath mitigation of continuous GPS measurements using an adaptive filter [J]. GPS Solutions, 2000, 4(2): 19-30.
[6] LIU H, LI X, GE L, RIZOS C, WANG F. Variable length LMS adaptive filter for carrier phase multipath mitigation [J]. GPS Solutions, 2011, 15(1): 29-38.
[7] AXELRAD P, LARSON K, JONES B. Use of the correct satellite repeat period to characterize and reduce site-specific multipath errors [C]//Proceedings of the ION GNSS 2005. Long Beach: CA, 2005: 2638-2648.
[8] SATIRAPOD C, KHOONPHOOL R, RIZOS C. Multipath mitigation of permanent GPS stations using wavelets [C]//International Symposium on GPS/GNSS. Tokyo, 2003.
[9] XU Pei-liang, LIU Jing-nan, DERMANIS A. VI Hotine-Marussi symposium theoretical and computational geodesy [M]. Berlin, Heidelberg: Springer-Verlag, 2008, 132: 179-184.
[10] WANG J, WANG J L, ROBERTS C. Reducing carrier phase errors with EMD-wavelet for precise GPS positioning [J]. Survey Review, 2009, 41: 152-161.
[11] MOSAVI M R. A practical approach for accurate positioning with Ll GPS receivers using neural networks [J]. Journal of Intelligent and Fuzzy Systems, 2006, 17: 159-171.
[12] BILICH A, LARSON K M. Mapping the GPS multipath environment using the signal-to-noise ratio (SNR) [J]. Radio Science, 2007. doi:10.1029/2007RS003652.
[13] BILICH A, LARSON K M, AXELRAD P. Modeling GPS phase multipath with SNR: Case study from Salar de Uyuni, Bolivia [J]. J Geophys Res, 2008, doi:10.1029/2007JB005194.
[14] ROST C, WANNINGER L. Carrier phase multipath mitigation based on GNSS signal quality measurements [J]. Journal of Applied Geodesy, 2009, 3(2): 81-87.
[15] GIREMUS A, TOURNERET J Y, CALMETTES V. A particle filtering approach for joint detection/estimation of multipath effects on GPS measurements [J]. IEEE Transactions on Signal Processing, 2007, 55(4): 1275-1285.
[16] BENTON C, MITCHELL C N. Isolating the multipath component in GNSS signal-to-noise data and locating reflecting objects [J]. Radio Science, 2011, 46(6), doi: 10.1029/2011RS004767.
[17] HWANG S S, SPEYER J L. Relative GPS carrier-phase positioning using particle filters with position samples [C]//2009 American Control Conference. New York, USA: IEEE, 2009: 4171-4177.
[18] WANG Zhen-jie, QU Guo-qing. Separation of systematic errors in processing high precision GPS baselines [J]. Transactions of Nonferrous Metals Society of China, 2005, 15 (S1): s131-s133.
[19] XU Chang-hui, WANG Jin-ling, GAO Jing-xiang, WANG Jian, HU Hong. Precise point positioning and its application in mining deformation monitoring [J]. Transactions of Nonferrous Metals Society of China, 2011, 21(S3): s499-s505.
[20] GORDON N J, SALMOND D J, SMITH A F. Novel approach to nonlinear/non-Gaussian Bayesian state estimation [J]. IEEE Proceedings F, Radar and Signal Processing, 1993, 140(2): 107-113.
[21] DOUCET A, GODSILL S, ANDRIEU C. On sequential Monte Carlo sampling methods for Bayesian filtering [J]. Statistics and Computing, 2000, 10: 197-208.
[22] DOUCET A, de FREITAS N, GORDON N. Sequential Monte Carlo in practice [M]. New York: Springer-Verlag, 2001.
[23] GUSTAFSSON F. Particle filter theory and practice with positioning applications [J]. Aerospace and Electronic Systems Magazine, IEEE, 2010, 25(7): 53-82.
[24] GAO Jing-xiang, LIU Chao, WANG Jian, LI Zeng-ke. A new method for mining deformation monitoring with GPS-RTK [J]. Transactions of Nonferrous Metals Society of China, 2011, 21: 659-664.
GPS多路径减轻的混合粒子滤波算法
郑南山1,2，蔡良师1，卞和方1,2，林 聪1
1. 中国矿业大学 环境与测绘学院，徐州 221116；
2. 国家测绘地理信息局 国土环境与灾害监测重点实验室，徐州 221116
摘 要：提出一种结合无迹卡尔曼滤波(UKF)和小波阈值自适应滤波的混合粒子滤波方法。该算法在粒子产生过程中采用UKF方法以克服粒子发散，而在数据预处理和粒子产生时采用自适应阈值小波变换算法抑制观测数据噪声和数据处理过程误差。比较了EKF-PF、UKF-PF和WM-UKF-PF不同算法的性能。结果表明，经过改进的WM-UKF-PF混合粒子滤波算法能够有效地降低均方根误差，提高信噪比和相邻恒心日观测值的相关性，从而改善解算结果的统计特性。所采取的混合滤波算法的计算复杂性提高了，但能够有效减轻GPS多路径效应影响，对高精度定位测量和非平稳形变特征提取具有重要意义。
关键词：粒子滤波；小波变换；GPS；多路径效应
(Edited by Xiang-qun LI)
Foundation item: Project (51174206) supported by the National Natural Science Foundation of China; Project (2013AA12A201) supported by the National Hi-tech Research and Development Program of China; Project (2012ZDP08) supported by the Fundamental Research Funds for the Central Universities, China; Project (SZBF2011-6-B35) supported by the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD), China
Corresponding author: Nan-shan ZHENG; Tel/Fax: +86-516-83591330; E-mail: znshcumt@163.com
DOI: 10.1016/S1003-6326(14)63225-8
Abstract: An alternativeor mitigating GPS multipath ilter and wavelet transform with particle filter. algorithm for mitigating GPS multipath was presented by integrating unscented Kalman filter (UKF) and wavelet transform with particle filter. Within consideration of particle degeneracy, UKF was taken for drawing particle. To remove the noise from raw data and data processing error, adaptive wavelet filtering with threshold was adopted while data preprocessing and drawing particle. Three algorithms, named EKF-PF, UKF-PF and WM-UKF-PF, were performed for comparison. The proposed WM-UKF-PF algorithm gives better error minimization, and significantly improves performance of multipath mitigation in terms of SNR and coefficient even though it has computation complexity. It is of significance for high-accuracy positioning and non-stationary deformation analysis.
