Probabilities and Multipath

Mitigation Techniques Using Maximum-Likelihood Principles

» Download this article (PDF)

Share via: Slashdot   Technorati   Probabilities and Multipath (Inside GNSS)Twitter   Facebook

Although modern GPS receivers achieve high pseudorange accuracy in line-of-sight (LOS) conditions, multipath remains a dominant source of ranging error in GNSS.

Multipath interference occurs when the user device receives reflected signals in addition to the direct LOS signal. These interference signals are generally reflected from the ground, buildings or trees in terrestrial navigation, while signal reflections from the host-vehicle body are more common in airborne and marine applications.

Two kinds of multipath exist: specular multipath arising from discrete, coherent reflections from smooth surfaces such as standing water, and diffuse multipath arising from diffuse scatterers and sources of diffraction. (The visible glint of sunlight off a choppy sea is an example of diffuse multipath.)

Multipath signals are generally considered undesirable in the GNSS realm because they destroy the correlation function shape used for time delay estimation, but can be useful in some cases (for example, for acquisition). Although some wireless communications techniques exploit multipath to provide signal diversity, the key point in GNSS is to efficiently mitigate the multipath effect because we use only the satellite-receiver transit time offset of the LOS signal for positioning.

This article will discuss a category of multipath mitigation techniques a principle known as maximum-likelihood estimation, reviewing some of the leading examples introduced over the last 15 years or so and then describing a new ML approach based on what we call the Fast Iterative Maximum-Likelihood Algorithm (FIMLA).

Multipath Mitigation
Examples of recently developed in-receiver multipath mitigation methods include the narrow correlator, the strobe correlator, the Multipath Estimating Delay Lock Loop (MEDLL), Multipath Elimination Technology (MET), the Multipath Mitigation Technology (MMT), and the Vision Correlator (VC).

Spatial processing is another class of multipath mitigating technology that includes choke-ring antenna design and directive antenna arrays. Directive antennas are generally physically large and heavy and are not affordable for most of civilian applications. This class of multipath mitigation will not be discussed further in this article.

The actual multipath performance of a given signal and receiver combination depends on various parameters of both, including the signal-type modulation, code chipping rate, the pre-correlation bandwidth and filter characteristics, the number of received multipath signals, the relative power of multipath signals, the path-delay, chip spacing between correlators, and the type of discriminator and algorithm used for code and carrier tracking.

Maximum-Likelihood Methods
Several multipath mitigation methods introduced in recent years such as MEDLL, MMT and VC rely on maximum-likelihood (ML) estimation principles and are driven to approach theoretical performance limits. This is not surprising, because ML estimators have desirable statistical asymptotic properties.

The idea behind ML estimation in general is to determine the parameters that maximize a likelihood function, which is the joint probability density function (PDF) of the sample data. This estimation method does not require a priori information and assumes that the unknown parameters are constant over an observation period, typically hundreds of milliseconds or multiple seconds for high-sensitivity receivers.

Thus, ML offers the optimal approach in many practical situations when the prior knowledge needed for Bayesian estimators, such as maximum a posteriori (MAP) and minimum mean-square error (MMSE) estimation, is not available.

ML Simple, But Complex
Although the methodology for ML estimation is simple, the implementation is mathematically intense.

Using the interesting progress in the branch of optimization and today’s computer power, however, complexity is no longer a significant obstacle. ML-type tracking loops are typically complex and difficult to implement, as they require the receiver to measure the received signal cross-correlation function for each reflected path with multiple correlators and to process these measurements with complex algorithms.

One commonly used technique, a line search approach, is applied to find the estimates that maximize the log-likelihood. Recently, Lawrence Weill, inventor of MMT, applied a nonlinear transformation on the multipath parameter space to reduce the computation load of the likelihood function maximization. M. Z. Bhuiyan et al. has published a non-coherent version of MEDLL that generates phases as a random uniformly distributed parameter and chooses the one that minimizes the mean square error of a residual correlation function. (See Additional Resources section at the end of this article.)

The latest ML multipath mitigation approach is the Fast Iterative Maximum-Likelihood Algorithm (FIMLA) developed by M. Sahmoudi that uses a GNSS signal model structure and the spreading code periodicity. With these, FIMLA develops an efficient implementation of the Newton iterative likelihood-maximization method by finding simple analytical expressions for the first and second derivatives of the likelihood function. Later in this article we review and discuss these different implementations of ML multipath estimation in terms of how they each improve processing efficiency.

Multipath Signal Model
Considering a received multipath or M − path signal composed of the LOS and (M − 1) reflected paths, we can express the received complex baseband signal at the input of a GPS receiver . . .

. . .

Multipath Estimation Using ML
The idea of parametric multipath mitigation methods is to reduce the multipath effect by estimating both the LOS and multipath contribution . . .

. . .

MEDLL
To illustrate how ML-based estimation works in a bit more detail, we first consider the Multipath Estimating Delay Lock Loop, which is an efficient statistical approach for multipath mitigation . Implemented commercially in 1995, this algorithm became the first widely known and practical method for multipath mitigation.

. . .

A Non-Coherent MEDLL Algorithm for ML Multipath Estimation. Recently, M. Z. Bhuiyan and others at Finland’s Tampere University of Technology suggested a non-coherent implementation of MEDLL to reduce the parameters space of optimization. This is done by including additional non-coherent integrations in the likelihood cost function to be optimized.

. . .

MMT Algorithm for ML Multipath Estimation. Developed for the case of M = 2 by Weill and Ben Fisher of Comm Sciences Corporation (CSC), MMT uses a nonlinear transformation on the multipath parameters space to permit rapid computation of a 2-path log-likelihood function that has been partially maximized with respect to four new parameters — reflected in the transformation (8) —instead of the six multipath parameters. The final maximization requires a search in only two dimensions, aided by acceleration techniques.

. . .

FIMLA
The FIMLA algorithm reformulates the cost function as a complex amplitude ai = Ai for more compact and general derivations. Thus, the phase information is considered implicitly in order to reduce the computational burden.

. . .

Other Considerations
The effect of non-white interference on performance of ML-based multipath mitigation techniques has not been investigated in the literature but is beginning to receive some attention. Refer to the Additional Resources section at the end of this article for more information.

Finally, the foregoing discussion reviewed approaches that are based on the premise that, over a sufficiently short observation interval, the signal parameters may be viewed as constant, though unknown, quantities. With this assumption, the ML yields the best performance.

However, this assumption is not valid for a large number of observation times. Thus, some kind of Kalman filter tracking algorithms may be employed in conjunction with ML estimation in order to keep the estimates from eventually drifting outside their allowable range.

For the complete story, including figures, graphs, and images, please download the PDF of the article, above.

Additional Resources
[1] Bhuiyan, M. Z., and E. S. Lohan and M. Renfors, “Code tracking algorithms for mitigating multipath effects in fading channels for satellite-based positioning,” EURASIP Journal on Advances in Signal Processing, January 2008.
[2] Garin, L., and F. Van Diggelen, and J. Rousseau, “Strobe & Edge Correlator Multipath Mitigation for Code,” in Proceedings of the ION GPS 1996, Kansas City, Missouri, September 1996
[3] Jones, J., and P. C. Fenton, “The Theory and Performance of NovAtel Inc.’s Vision Correlator”, available from <http://www.novatel.ca> or in Proceedings of the ION GNSS 2005, Long Beach, California, USA, September 2005
[4] Sahmoudi, M., and M. G. Amin, “Fast Iterative Maximum-Likelihood Algorithm (FIMLA) for Multipath Mitigation in Next Generation of GNSS Receivers,” in IEEE Trans. On Wireless Communication, Vol. 7, No. 11, November 2008.
[5] Townsend, B. R., and P. Fenton, “A Practical Approach to the Reduction of Pseudorange Multipath Errors in a L1 GPS Receiver”, in Proceedings of ION GPS-94, Salt Lake City, Utah, USA, 1994
[6] Van Dierendonck, A. J., P. Fenton and T. Ford, “Theory and Performance of Narrow Correlator Spacing in a GPS Receiver”, Journal of the Institute of Navigation, vol. 39, no. 3, Fall 1992
[7] Van Nee, R. D. J., Multipath and Multi-Transmitter Interference in Spread-Spectrum Communication and Navigation Systems, Ph.D. Thesis, Delft University Press, The Netherlands, 1995
[8] Weill, L. R., “Multipath Mitigation Using Modernized GPS Signals: How Good Can it Get?” in Proceedings of ION GPS 2002, Portland, Oregon, USA, 2002

For more information regarding the effect of non-white interference on ML-based tracking refer to Sahmoudi, M., and M. G. Ami (2008), “Robust Tracking of Weak GPS Signals in Multipath and Jamming Environments,” to appear in Signal Processing (Elsevier), 2008.

Issue Home

Manufacturers

Copyright © 2008 Gibbons Media & Research LLC, all rights reserved.