Probabilities and Multipath
Mitigation Techniques Using Maximum-Likelihood Principles
With increased computer power, receiver designers can now make use of complex algorithms and computationally intense solutions to reduce the bad effects of multipath – reflected signals – on GNSS equipment. The authors describe a category of multipath mitigation techniques based on principles of maximum-likelihood (ML) estimation — including a new variation of their own — that can improve receiver performance
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).
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.
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
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
. . .
Multipath Estimation Using ML
. . .
. . .
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.
. . .
. . .
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.
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.
ManufacturersMEDLL, MMT, and the Vision Correlator were commercially implemented by Novatel, Inc., Calgary, Alberta, Canada.
Copyright © 2017 Gibbons Media & Research LLC, all rights reserved.