Comparison of computation burden between new algorithm and conventional one
1. Introduction
GNSS (Global Navigation Satellite System) has been found application in many areas. In some cases, the performance requirements for GNSS are very high. There are many error sources that would degrade the positioning performance of GNSS, e.g., clock errors, ephemeris errors, tropospheric propagation delay, and multipath. Many positioning errors mentioned above are constant for all GNSS receivers in a given small area and can be removed or reduced by using the popular differential technique. However, due to the geographical position difference between the reference station and the receiver, the multipath environment of receivers, such as amplitudes and number of multipath signals, is totally different with that of the reference station. Thus differential technique can not eliminate the multipath error. Many studies have shown that the multipath interference will lead to a position error around several meters which endangers the reliability and accuracy of GNSS. Therefore, multipath interference mitigation has been a hot topic in the field of satellite navigation receiver design.
Multipath interferences are the signals reflected by the objects around the GNSS receiver. Then the multipath interference and the LOS (line of sight) signal are simultaneously received by antenna which brings a phase distortion in the tracking loops of receivers. Finally, the phase distortion results in the tracking and positioning error.
There have been many studies about the effect of multipath interference. Kalyanaraman et al. in [1] analyzed the multipath effects on code tracking loop. Kos et al. [2] provided a detailed analysis of the multipath effects on the positioning error. Main multipath interference mitigation techniques are based on antenna technique and signal processing algorithms.
By mounting the antenna in a welldesigned place based on the multipath environment, Maqsood et al. in [3] compared the performances of multipath interference mitigation for different antennas. Ray et al. in [4] proposed a multipath mitigation algorithm based on an antenna array. A design principle of antenna was proposed by Alfred et al. in [5] for satellite navigation landing system. The multipath mitigation technique based on the special antenna can only suppress the multipath signal coming from the ground below the antenna. However, it is useless for the multipath interference signal reflected by the objects above the antenna.
Popular signal processing techniques are the narrow correlator and MEDLL (Multipath Estimated Delay Locked Loop). Narrow correlator is adopted in many GNSS receivers which suppresses multipath interference by reducing the earlylate correlator spacing. The signal model for the narrow correlator is provided by Michael et al. in [6]. Cannon et al. in [7] analyzed the performance of narrow correlator in the satellite navigation system. The performance of narrow correlator can be improved by decreasing the earlylate correlator spacing. However, the narrow correlator assumes that the bandwidth of the received signal is infinite which is invalid in the practical applications. Thus, when the earlylate correlation spacing is less than the reciprocal of the channel bandwidth, the tracking error cannot be further decreased by reducing the earlylate correlator spacing. MEDLL is a multipath interference mitigation algorithm based on the statistical theory as in [8], which estimates the time delays via the maximum likelihood criterion. Therefore, the complexity of MEDLL is much higher than narrow correlator.
This chapter firstly presents a new acquisition algorithm for GNSS. Then two multipath interference mitigation algorithms based on the DPE (Decoupled Parameter Estimation) parameter estimation algorithms are presented. The FFT algorithm is utilized to reduce the computational complexity in all proposed algorithms. Numerical results are provided to demonstrate the performances of the proposed algorithms. The remainder of this chapter is arranged as follows. Section 2 presents the new acquisition algorithm. Two multipath interference mitigation algorithms are separately presented in Section 3. Section 4 concludes the chapter.
2. A novel GNSS acquisition algorithm
2.1. Data model and problem formulation
GNSS signal is composed of three parts, the carrier, the ranging codes and the data codes. In order to facilitate the presentation, GPS is taken as an example. However, the proposed algorithm is also suitable for other GNSS system. The carrier of GPS (Global Navigation System) consists of the three different frequency bands, i.e., L1 (1575.42 MHz), L2 (1227.6 MHz) and L5 (1176.45MHz), see [910]. The ranging codes are pseudo random noise (PRN) codes including C/A code, P code and M code which are known in advance. Data codes or the navigation data are binary codes containing the satellite ephemeris, satellite status, clock system, the orbit perturbation correction of the satellite clock motion state and the atmospheric refraction correction, etc..
Suppose that one receiver obtained the signals from P satellites and the received data can be expressed as
where
After A/D conversion, the data can be written as
The conventional acquisition procedure is a twodimensional searching algorithm, which is time consuming even when using parallel searching algorithm. Moreover, the frequency resolution of the conventional acquisition algorithm cannot satisfy the requirements of the tracking loop. Hence, a more accurate frequency estimation is required before tracking in the conventional receiver.
Therefore, a new GNSS acquisition algorithm is proposed in this section. The Doppler frequency is firstly estimated. After that, the initial code phase is then obtained via NLS (Nonlinear Least Square) fitting. Compared with the conventional acquisition algorithm, the proposed algorithm can obtain a comparative performance with a lower computational complexity.
2.2. Principle of the novel acquisition algorithm
It can be noted from the data model in section 2.1 that there are three unknown parameters in the acquisition process, which are the PRN index of the
2.2.1. Doppler frequency estimation
Due to the navigation data and C/A code are
Since the value of navigation data and C/A code is
where,
It can be seen from equation (4) that the spectrum of each satellite only contains a single dominant frequency component corresponding to the Doppler frequency. For the reason that not only the correlation of C/A code of different satellites is very small but also the signal and noise are uncorrelated, it is obviously that in equation (5) the product terms of different C/A codes as well as the product of noise and signal are close to zero. Fourier analysis method can be directly used to estimate the signal frequency.
The Fourier transform of equation (4) can be expressed as
where
The estimated value of
The frequency spectrum of the received data before and after the square operation is shown in Figure 1. It can be noted that before square operation, there are multiple dominant frequency components. Thus the Doppler frequency cannot be extracted directly. However, after being squared, there is only one dominant Doppler frequency present in the spectrum, so an accurate Doppler frequency can be estimated.
2.2.2. Code phase estimation and matching
After obtaining the Doppler frequency, the initial phases and the PRN index of the C/A code from all satellites can be estimated by using its autocorrelation characteristic. Let
As the Doppler frequency
Suppose the time delay from the
where
where
To estimate
Let
where
where
The time delay estimation can be further obtained by
Equation (16) can be solved by using FFT algorithm with a low computation burden. Since the PRN index of the received signal is unknown, consequently, it is not feasible to reconstruct
It is wellknown that the cross correlation coefficients of different C/A codes are very small. In addition, the signal and noise are uncorrelated. Thus Fourier analysis results of the above mentioned component are close to zero. The maximum correlation value can only be obtained in the case that the C/A code of the reconstructed signal is the same as the received one. Therefore, the PRN index can be obtained. Furthermore, the code delay can be estimated by the location of the maximum correlation value. Then, we obtained all the unknown parameters.
2.3. Comparison of acquisition algorithms
Suppose the searching time for Doppler frequency estimation is
Figure 2 compares the searching process of the proposed algorithm and the conventional one. It can be seen that the computation complexity of the proposed algorithm is significantly lower than that of the conventional algorithm in that the typical value of
Comparison of computation burden between new acquisition algorithm and conventional acquisition algorithm are shown Table 1. It can be clearly seen from Table 1 that, since






7MQ+4M  2MQ+3M  2MQ  O(MQ) 

6MP+4P  3MP+7P  M (P+1) +1  O(MP) 
2.4. Numerical results
To verify the performance of the proposed algorithm, GPS signals from 8 satellites with PRN indexes 1, 2, 13, 20, 22, 24, 25 and 27 are simulated. Considering the IF is 1.25MHz, the sampling rate is 7.5MHz, the pre integration time is 1ms and the signal to noise ratio (SNR) is 20dB. The frequency searching step of the conventional acquisition algorithm is 1kHz. The acquisition results are shown in Figure 3.
In Figure 3, the horizontal axis stands for the PRN index of the satellites and the vertical axis denotes the acquisition metric. Since the proposed algorithm only calculates the correlation of the received satellite signal and the local reference signal, correlation results of the other satellite are not shown in Figure 3(b). It can be noted that acquisition results are identical, and the peak value of the proposed algorithm is higher than the conventional one. Therefore, the proposed algorithm has a comparative performance with the conventional one.
3. Two novel methods for multipath mitigation
3.1. Multipath data model
The term multipath is derived from the fact that a signal transmitted from a GNSS satellite can follow a ‘multiple’ number of propagation ‘paths’ to the receiving antenna. This is possible because the signal can be reflected back to the antenna from surrounding objects, including the earth’s surface.
Suppose the signal transmitted by GNSS satellites can be written as
where
where
To obtain the Doppler frequency of the LOS signal, we use the following relation
Assume the radial velocity of the receiver relative to the satellite is
where
As the relative radial velocity is constant, the Doppler frequency can be obtained by
The propagation range of the multipath signal can be written as
where
Further simplify of equation (20) we can get
where
After A/D conversion, the transformed digital signal can be written as
Assume the Doppler frequency has been estimated accurately, then the complex phase
where
The inphase component of equation (29) can be given by
where
In classical DLL, the inphase early and late correlation value is given as
where
In GNSS navigation, the receiver is concerned to maximize the correlation function between the received and locally generated signals. This can be accomplished by determining the locations of the zero output of the discriminator which corresponds to the maximum of the correlation function. Here, the earlylate correlator is used to determine the position of this zero. However, the presence of multipath introduces some bias in the position of the first arrival peak and has an impact in the user’s position, which can be clearly seen in Figure 4. Then the classical DLL failed to cope with multipath propagation, see [78].
3.2. Code delay estimation
3.2.1. Code delay estimation in the correlation domain via NLS
In this subsection, a code delay estimation algorithm based on DPE in correlation domain is proposed. To deploy the proposed algorithm, we combine the complex constant phase
The navigation data cycle is much longer than that of the C/A code, but only one cycle of the C/A code is used in the code delay estimation. Consequently, the navigation data jump can be neglected in the signal reconstruction. Then the navigation data
To simplify the following expression,
Multipath interference mitigation based on code delay estimation focus on the estimation of the LOS delay
To obtain the initial code delay, the correlation function between the received satellite signal and the reference signal is represented as
where
where
where
Define a NLS cost function as
The unknown parameters
Consequently the cost function in equation (42) can be rewritten as
Further, we assume
Substitute equation (47) into equation (46) we have
By minimizing the cost function
and
where
With the above simple preparations, we now proceed to present the correlation domain algorithm for the minimization of the NLS cost function. The proposed algorithm comprises the following steps.
Step 1. Assume
Step 2. Assume
Next, compute
Iterate the previous two substeps until “practical convergence” is achieved then we can obtain
From the previous description one can find that the proposed algorithm can be implemented by simply FFT operation which leads to a less computation load.
The diagram of the novel code delay estimation algorithm is shown in Figure 5.
3.2.2. Code delay estimation in the data domain via NLS
Another DPE algorithm is proposed in this subsection. Different from the correlation domain algorithm, the unknown parameters
Again, the signal after downconversion is given by
To obtain the unknown parameters
where
To obtain
Let
Hence, minimizing the cost function in equation (53) is equivalent to minimizing the following cost function
Assume
Substitute equation (58) into equation (57)
Equation (59) gets the minimum while
From equation (60),
The diagram of the data domain code delay estimation algorithm is shown as in Figure 6.
With the above simple preparations, we now proceed to present the relaxation algorithm for the minimization of the nonlinear leastsquares cost function. The data domain WRELAX algorithm comprises the following steps.
Step 1. Assume
Step 2. Assume
Next, compute
Iterate the previous two substeps until “practical convergence” is achieved then we can obtain
From the previous description one can find that the proposed algorithm can be implemented by simply FFT operation which deserves a less computation load.
3.2.3. Comparison of the above two algorithms
To further analyze the two proposed algorithms, the cost functions of them are further discussed in this subsection. Following the discussion in section 3.2.1 and section 3.2.2, we define
Then
In the noise free situation we have
Then the correlation domain cost function in equation (49) can be further decomposed as
And in the same situation the data domain cost function in equation (60) can be deployed in the following way
It has been discussed in previous subsection that
Correlation of the received data and the locally generated signal and the autocorrelation of the locally generated signal should be calculated in correlation domain WRELAX algorithm. Suppose the iteration times of the two proposed algorithms are the same, the correlation domain WRELAX algorithm is more complex than the data domain WRELAX algorithm.
3.2.4. Numerical results
To investigate the performance of the proposed algorithm in the presence of multipath, a simulation experiment was performed. The code delay estimation error can be represented as the function of
Suppose there is only one reflected multipath signal combined with the LOS signal. The noise and the receiver bandwidth are not considered in the experiment. The relative amplitude of the direct and the reflected signal is
In Figure 8, the curve ‘classical DLL’ denotes the error envelope of the classical DLL, and the curve ‘narrow correlator’ denotes the error envelope of the narrow correlator with spacing
4. Conclusion
A novel acquisition algorithm is firstly proposed in this chapter. In the proposed algorithm, the Doppler frequency is obtained by utilizing FFT of the squared data. Then, the PRN index and initial code phases of the satellite are obtained based on the NLS criterion. It can be seen that the proposed algorithm can not only reduce the computation complexity but also attain a comparable performance to the conventional acquisition algorithm.
After that, two algorithms are presented to suppress the multipath interference by estimating the code delay. In the proposed algorithms, the code delay was obtained by solving a NLS equation, which can be further realized by FFT operation. Compared with the conventional estimation algorithm, the proposed two algorithms perform better in multipath propagating environments and bear lower computation burden.
Acknowledgments
The work of this chapter is supported by the Project of the National Natural Science Foundation of China (Grant No. 61179064, 61172112, 61271404 and 61471363), and the Fundamental Research Funds for the Central Universities (Grant 3122014D008 and 3122014B001).
References
 1.
Kalyanaraman S K, Braasch M S, Kelly J M. Code Tracking Architecture Influence on GPS Carrier Multipath. IEEE Transactions on Aerospace and Electronic Systems 2006; 42(2) 548561.  2.
Kos T, Markezic I, Pokrajcic J. Effects of Multipath Reception on GPS Positioning Performance. 52nd International Symposium ELMAR2010: conference proceedings, 1517 September 2010, Zadar, Croatia. 399402.  3.
ScireScappuzzo F, Makarov S N. A LowMultipath Wideband GPS Antenna With Cutoff or NonCutoff Corrugated Ground Plane. Antennas and Propagation 2009; 57(1): 3346  4.
Maqsood M, Gao S, Brown T, et al. A Compact Multipath Mitigating Ground Plane for Multiband GNSS Antennas. IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION 2014; 61(5) 27752782.  5.
Ray J K, Cannon M E, Fenton P. GPS Code and Carrier Multipath Mitigation Using a Multiantenna System. IEEE Transactions on Aerospace and Electronic Systems 2001; 37(1) 183195.  6.
Alfred R L. GPS Landing System Reference Antenna. IEEE Antennas and Propagation Society 2010; 52(1) 104113.  7.
Michael S B. GPS Multipath Model Validation. IEEE Position Location and Navigation Symposium 1996: conference proceedings, April 1996, Atlanta, GA. 672678.  8.
Cannon M E, Lachapelle G, Qiu W, et al. Performance Analysis of a Narrow Correlator Spacing Receiver for Precise Static GPS Positioning. IEEE Position Location and Navigation Symposium 1994: conference proceedings, April 1994, Las Vegas. 2994—2999  9.
Tung Hai Ta, Son Hong Ngo. A Novel Signal Acquisition Method for GPS DualFrequency Ll C/A and L2C Receivers. International Conference on Advanced Technologies for Communications (ATC 2011) : conference proceedings, Aug 2011. 231234.  10.
Chengjun Li, Mingquan Lu, Zhenming Feng, Qi Zhang. Study on GPS Acquisition Algorithm and Performance Analysis. Journal of Electronics & Information Technology 2010; 32(2) 296300.  11.
Olivier Besson, Peter Stoica. Nonlinear leastsquares frequency estimation and detection for sinusoidal signals with arbitrary envelope. Digital Signal Processing 1999; 9(1) 4556.  12.
Jian Li, Renbiao Wu. An efficient algorithm for time delay estimation. IEEE Transactions on Signal Processing 1998; 46(8) 22312235.  13.
Jian Li, Dunmin Zheng, Peter Stoica. Angle and Waveform Estimation via RELAX. IEEE Transactions on Aerospace and Electronic Systems 1997; 33(3) 10771087.  14.
Renbiao Wu, Jian Li, Zhengshe Liu. Super resolution time delay estimation via MODEWRELAX. IEEE Transactions on Aerospace and Electronic Systems 1999; 35(1) 294307.  15.
Renbiao Wu, Jian Li. TimeDelay Estimation via Optimizing Highly Oscillatory Cost Functions. IEEE Journal of Oceanic Engineering 1998; 23(3) 235244.