Innovation: Position estimation using non-line-of-sight GPS signals

March 15, 2017  - By and

Reflected Blessings

A technique developed by researchers at the University of Illinois at Urbana-Champaign distinguishes a reflected non-line-of-sight (NLOS) signal of a particular satellite from the LOS signal and characterizes the NLOS signal as coming from a virtual mirror-image satellite in the direction of the signal reflection point. By using information on the position and orientation of the reflector, the NLOS signal can be treated as an additional LOS signal.

By Yuting Ng and Grace Xingxin Gao

INNOVATION INSIGHTS with Richard Langley

INNOVATION INSIGHTS with Richard Langley

THIS ARTICLE IS ABOUT VIRTUAL SATELLITES. No, we don’t mean physical objects that are almost satellites. That’s the common everyday meaning of the word virtual. We mean it in the sense used in computing to describe something that is not physically present but made to appear so by software (and perhaps aided by hardware). The word was first used in this sense by computer scientists in the 1950s in the term virtual memory to describe a memory management technique. It is now widely used in computing, most commonly as virtual reality. But what is a virtual satellite then?

As we all know, GPS satellite signals are quite weak. The antenna of a standard GPS receiver needs to have a clear line-of-sight (LOS) view to the satellites for successful signal tracking and position determination. Buildings and other structures will block signals coming from certain directions. In built-up areas, this can result in fewer LOS signals than the minimum of four needed for unaided positioning. Even with four or more LOS signals, the receiver-satellite geometry may be poor resulting in a large dilution of precision and poor positioning accuracy as a result. It is true that augmentations such as wheel sensors and inertial measurement units coupled with dead reckoning may permit an acceptable level of positioning accuracy for some kinematic applications, but the accuracy will degrade over time if satellite blockage continues unabated. And yes, multi-GNSS can help in these situations with receivers availing themselves of additional LOS signals from the GLONASS, Galileo, and BeiDou systems and in Japan, QZSS. But Galileo, BeiDou and QZSS are still in development with a variable number of satellites available at a given location during the day. Is there anything else that can be done to improve the availability of GPS signals?

In fact, there are often more GPS signals arriving at a receiver’s antenna than just the LOS signals. These are non-line-of-sight (NLOS) signals that bounce off nearby structures before arriving at the antenna. We call the phenomenon multipath and, as we have discussed before in this column, multipath typically reduces positioning performance when the NLOS signals from a particular satellite combine with the LOS signal to distort a receiver’s standard correlator outputs thereby biasing pseudorange and carrier-phase measurements. Various techniques have been developed to reject multipath signals at the antenna or in the receiver while others have been developed to lessen the effect of these signals and so minimize their impact on position solutions. On the other hand, non-positioning GPS applications have been developed to use reflections from the Earth’s surface to measure snow depth, ground moisture content, and ocean-surface roughness. But could we somehow use multipath signals to improve positioning applications rather than degrade them?

In this month’s column, we look at a technique developed by researchers at the University of Illinois at Urbana-Champaign that distinguishes a reflected NLOS signal of a particular satellite from the LOS signal and characterizes the NLOS signal as coming from a virtual mirror-image satellite in the direction of the signal reflection point. By using information on the position and orientation of the reflector, the NLOS signal can be treated as an additional LOS signal, albeit from a ghost satellite. The authors have demonstrated that the technique works well in practice and in one difficult positioning environment, obtained an improvement in horizontal position accuracy of 40 meters — a reflected blessing indeed.


Building obstructions and reflections present serious challenges to GPS receivers operating in urban environments. In such environments, buildings may obstruct GPS signals, leading to reduced GPS signal availability. In addition, buildings may reflect GPS signals, resulting in reception of non-line-of-sight (NLOS) signals. NLOS GPS signals are delayed versions of the line-of-sight (LOS) signals. As such, they lead to pseudorange errors, resulting in positioning errors. Conventional approaches treat NLOS GPS signals as unwanted interference to be rejected or mitigated.

Conventional approaches reject NLOS GPS signals at multiple stages of GPS signal processing. Antenna-based approaches include the use of right-hand-circularly-polarized (RHCP) antennas and controlled reception pattern antennas (CRPA). Correlator-based approaches include the use of the narrow correlator, the double-delta correlator, the multipath estimating delay lock loop (MEDLL) and the vision correlator by various receiver manufacturers. In addition, receiver autonomous integrity monitoring (RAIM) approaches reject pseudoranges with inconsistent positioning residuals.

Besides rejecting NLOS GPS signals, conventional approaches also make use of robust filtering and joint signal tracking techniques to mitigate the effects of these signals. Robust filtering techniques include the use of Bayesian filters such as Kalman filters and particle filters. Joint signal tracking techniques include vector tracking and direct position estimation (DPE). A list of existing approaches addressing NLOS GPS signals is provided in TABLE 1.

TABLE 1. Approaches for rejecting and mitigating NLOS GPS signals.

TABLE 1. Approaches for rejecting and mitigating NLOS GPS signals.

In contrast to conventional approaches that reject or mitigate the effects of NLOS GPS signals, we propose transforming NLOS GPS signals from being unwanted interference to becoming additional useful navigation signals. In addition, we provide a navigation solution under reduced GPS signal availability.

RELATED WORK

In our approach to using NLOS GPS signals, we make use of DPE and 3D map-aided positioning. The following sections provide an overview of these techniques.

Direct Position Estimation. DPE is an unconventional joint signal tracking and navigation technique that directly estimates the GPS receiver’s navigation parameters from the GPS raw signal. It does so by directly comparing the expected signal reception of multiple potential navigation candidates against the actual received signal. The navigation solution is then estimated as the navigation candidate with the highest overall correlation between the expected and the actual received signal. This overall correlation is an accumulation of signal correlations across all available satellites, with replica signal parameters aligned to the candidate navigation parameters. In this manner, DPE jointly uses signal correlations from all available satellites to produce a robust navigation solution.

3D Map-Aided Positioning Techniques. State-of-the-art approaches use available 3D maps to predict NLOS signal reception. Apart from rejecting and/or mitigating the effects of NLOS pseudoranges, state-of-the-art approaches leverage the benefits of NLOS pseudoranges, constructively using the affected pseudorange measurements through special treatment of NLOS paths during trilateration. Using 3D building models, they model NLOS paths as LOS paths from satellites to virtual receivers located at receiver mirror-image positions. However, these approaches are limited by the issue of reduced signal availability due to multipath fading in addition to building obstruction. Under reduced signal availability, the navigation solution obtained via trilateration is degraded. With further reduction in signal availability — the number of available pseudorange measurements reduced to fewer than four — conventional calculation of the GPS navigation solution via trilateration with four unknowns is not possible.

In contrast to state-of-the-art approaches addressing NLOS signal reception at the GPS pseudorange measurement level, we directly address and constructively use NLOS signals at the GPS signal level via DPE using NLOS signals.

OUR APPROACH: DPE USING NLOS SIGNALS

We first model NLOS signals as LOS signals to virtual satellites at satellite mirror-image positions, as shown in FIGURE 1. This approach is similar to using virtual transmitters for multipath-assisted wireless indoor positioning. We calculate these satellite mirror-image positions and velocities using knowledge of building reflection surfaces estimated from available 3D maps.

FIGURE 1. NLOS signal transformed from being (a) an unwanted interference to becoming (b) an additional LOS signal to a virtual satellite at the satellite mirror-image position.

FIGURE 1. NLOS signal transformed from being (top) an unwanted interference to becoming (bottom) an additional LOS signal to a virtual satellite at the satellite mirror-image position.

We then integrate these NLOS signals into GPS positioning via DPE. We modify the expected signal reception used in DPE to include NLOS signal information, as shown in FIGURE 2. Our approach deeply integrates this information and accurately describes the actual received signal.

FIGURE 2. Overall correlation in DPE, with the NLOS signal treated as an additional LOS signal to a virtual satellite at the satellite mirror-image position.

FIGURE 2. Overall correlation in DPE, with the NLOS signal treated as an additional LOS signal to a virtual satellite at the satellite mirror-image position.

In addition, our approach provides a navigation solution under reduced signal availability. FIGURE 3 shows a block diagram of our approach.

FIGURE 3. Block diagram of DPE using NLOS signals and involving calculation of satellite position, velocity and time (PVT) and batch correlation using a fast Fourier transform (FFT).

FIGURE 3. Block diagram of DPE using NLOS signals and involving calculation of satellite position, velocity and time (PVT) and batch correlation using a fast Fourier transform (FFT).

IMPLEMENTATION AND EXPERIMENT RESULTS

We implemented DPE using NLOS signals with commercial front-end components and our software platform, PyGNSS. We conducted an experiment in front of the 53 meters by 40 meters wind tunnel located at NASA’s Ames Research Center, Mountain View, California (see FIGURE 4).

FIGURE 4. Experiment setup in front of the 53 meters by 40 meters wind tunnel located at NASA’s Ames Research Center, Mountain View, California. (a) data collection equipment; (b) wide-angle photograph of the wind tunnel’s air-intake port.

FIGURE 4. Experiment setup in front of the 53 meters by 40 meters wind tunnel located at NASA’s Ames Research Center, Mountain View, California. (a) data collection equipment; (b) wide-angle photograph of the wind tunnel’s air-intake port.

The material of the vertical surface of the wind tunnel’s air-intake port is a metal wire mesh with a grid spacing of 1.8 centimeters by 1.8 centimeters, as shown in FIGURE 5. This grid spacing is approximately one tenth of the carrier wavelength of the GPS L1 signal; the mesh wire radius is much less than the grid spacing. Thus, the vertical surface of the air-intake port acts as a reflector of GPS L1 signals.

FIGURE 5. Metal wire mesh on the vertical surface of the wind tunnel’s air-intake port. (Left) close-up photograph showing the grid spacing of 1.8 centimeters by 1.8 centimeters; (right) photograph from another perspective showing wire mesh covering the entire vertical surface of the air-intake port.

FIGURE 5. Metal wire mesh on the vertical surface of the wind tunnel’s air-intake port. (Left) close-up photograph showing the grid spacing of 1.8 centimeters by 1.8 centimeters; (right) photograph from another perspective showing wire mesh covering the entire vertical surface of the air-intake port.

We estimated the normal vector and a point on the wind tunnel’s reflection surface using a geo-referenced 3D point cloud available on line through the National Oceanic and Atmospheric Administration’s (NOAA’s) Data Access Viewer tool. We refined the estimate using iterative closest point map-matching with a lidar scan (FIGURE 6).

FIGURE 6. Building reflection surface estimated from NOAA Data Access Viewer (DAV) point cloud, refined using map-matching with a lidar scan.

FIGURE 6. Building reflection surface estimated from NOAA Data Access Viewer (DAV) point cloud, refined using map-matching with a lidar scan.

We then determined possible LOS and NLOS paths from satellite elevation-azimuth plots. Plotted in FIGURE 7 are the satellite positions, the satellite mirror-image positions and the building reflection surface. An NLOS path to a satellite exists if the corresponding LOS path to the satellite mirror-image intersects the building reflection surface. In our experiment, LOS paths exist to satellite PRNs 5, 7, 27 and 28 and an NLOS path exists to satellite PRN 5. Thus, both LOS and NLOS signals from satellite PRN 5 are present. This is verified by examining the amplitude of the in-phase prompt correlations over time. Only the in-phase prompt correlations of satellite PRN 5 exhibit a sinusoidal behavior characteristic of having both LOS and NLOS signals, as shown in FIGURE 8.

FIGURE 7. Elevation-azimuth plot with satellites highlighted using green boxes and satellite mirror-images highlighted using red boxes. The 3D point cloud of the wind tunnel’s air-intake port is plotted using grey dots. The path to the mirror-image of satellite PRN 5 passes through the surface of the wind tunnel. Thus, an NLOS path to satellite PRN 5 exists. In addition, LOS paths exist to satellite PRNs 5, 7, 27 and 28.

FIGURE 7. Elevation-azimuth plot with satellites highlighted using green boxes and satellite mirror-images highlighted using red boxes. The 3D point cloud of the wind tunnel’s air-intake port is plotted using grey dots. The path to the mirror-image of satellite PRN 5 passes through the surface of the wind tunnel. Thus, an NLOS path to satellite PRN 5 exists. In addition, LOS paths exist to satellite PRNs 5, 7, 27 and 28.

FIGURE 8. Only the in-phase prompt correlation of satellite PRN 5 exhibits a sinusoidal behavior characteristic of having both LOS and NLOS signal components.

FIGURE 8. Only the in-phase prompt correlation of satellite PRN 5 exhibits a sinusoidal behavior characteristic of having both LOS and NLOS signal components.

We then performed DPE, including the signal correlation contribution from the NLOS path to satellite PRN 5, where the NLOS path is represented as a LOS path to the satellite mirror-image. The overall correlation result, including the signal correlation from the NLOS path to satellite PRN 5, is shown in FIGURE 9. The color of the position markers, plotted using Google Maps, represents the overall correlation amplitude. Red indicates a high overall correlation amplitude and blue indicates a low overall correlation amplitude. The navigation solution is directly estimated as a correlation-weighted mean of the navigation candidates.

FIGURE 9. Normalized overall correlation with contributions from all satellites, including the satellite mirror-image of PRN 5.

FIGURE 9. Normalized overall correlation with contributions from all satellites, including the satellite mirror-image of PRN 5.

The result, as compared to that estimated using pseudoranges from scalar tracking followed by trilateration, is shown in FIGURE 10. DPE using NLOS GPS signals demonstrated improved horizontal positioning accuracy by 40 meters.

FIGURE 10. DPE using NLOS GPS signals demonstrates improved horizontal positioning accuracy by 40 meters. This is in comparison to the navigation result obtained using pseudoranges estimated from conventional scalar tracking followed by trilateration.

FIGURE 10. DPE using NLOS GPS signals demonstrates improved horizontal positioning accuracy by 40 meters. This is in comparison to the navigation result obtained using pseudoranges estimated from conventional scalar tracking followed by trilateration.

CONCLUSION

In summary, we proposed DPE using NLOS signals to mitigate the issues of NLOS GPS signal reception and reduced GPS signal availability in urban navigation. We modeled NLOS signals as LOS signals to virtual satellites at satellite mirror-image positions. In this manner, NLOS signals are transformed from being unwanted interference to becoming additional useful navigation signals. We then created expected signal receptions to include NLOS GPS signal information at multiple potential navigation candidates and use DPE for positioning. Finally, we experimentally demonstrated a reduction in horizontal positioning error by 40 meters. This is in comparison to the navigation result obtained using pseudoranges estimated from conventional scalar tracking followed by trilateration.

ACKNOWLEDGMENTS

The authors thank the Safe Autonomous Flight Environment (SAFE50) and the Unmanned Aircraft System Traffic Management teams at NASA’s Ames Research Center, where the lead author was hosted for the summer of 2016, for their equipment support. The authors also thank Akshay Shetty for collecting and map-matching the lidar scan to the geo-referenced 3D point cloud.

This article is based on the paper “Direct Position Estimation Utilizing Non-Line-of-Sight (NLOS) GPS Signals” presented at ION GNSS+ 2016, the 29th International Technical Meeting of the Satellite Division of The Institute of Navigation, held Sept. 12–16, 2016, in Portland, Oregon.


YUTING NG received her B.S. degree in electrical engineering and her M.S. degree in aerospace engineering from the University of Illinois at Urbana-Champaign (UIUC) in 2014 and 2016, respectively. Her research interests are advanced signal processing, satellite navigation systems and radar.

GRACE XINGXIN GAO is an assistant professor in the Aerospace Engineering Department at UIUC. She obtained her Ph.D. degree in electrical engineering from the GPS Laboratory at Stanford University in 2008. Before joining UIUC in 2012, she was a research associate at Stanford University.

FURTHER READING

• Authors’ Conference Paper

“Direct Position Estimation Utilizing Non-Line-of-Sight (NLOS) GPS Signals” by Y. Ng and G.X. Gao in Proceedings of ION GNSS+ 2016, the 29th International Technical Meeting of the Satellite Division of The Institute of Navigation, Portland, Oregon, Sept. 12–16, 2016, pp. 1279–1284.

• Non-Line-of-Sight Signals

GNSS Solutions: Multipath vs. NLOS Signals: How Does Non-Line-of-Sight Reception Differ from Multipath Interference” by M. Petovello with P. Groves in Inside GNSS, Vol. 8, No. 6, Nov./Dec. 2013, pp. 40–42.

• Direct Position Estimation

“Mitigating Jamming and Meaconing Attacks Using Direct GPS Positioning” by Y. Ng and G.X. Gao in Proceedings of IEEE/ION PLANS 2016, the Position, Location, and Navigation Symposium, Savannah, Georgia, April 11–14, 2016, pp. 1021–1026, doi: 10.1109/PLANS.2016.7479804.

“Evaluation of GNSS Direct Position Estimation in Realistic Multipath Channels” by P. Closas, C. Fernández-Prades, J. Fernández-Rubio, M. Wis, G. Vecchione, F. Zanier, J.A. Garcia-Molina and M. Crisci in Proceedings of ION GNSS+ 2015, the 28th International Technical Meeting of the Satellite Division of The Institute of Navigation, Tampa, Florida, Sept. 14–18, 2015, pp. 3693–3701.

Collective Detection: Enhancing GNSS Receiver Sensitivity by Combining Signals from Multiple Satellites” by P. Axelrad, J. Donna, M. Mitchell and S. Mohiuddin in GPS World, Vol. 21, No. 1, Jan. 2010, pp. 58–64.

“On the Maximum Likelihood Estimation of Position” by P. Closas, C. Fernández-Prades and J. Fernández-Rubio in Proceedings of ION GNSS 2006, the 19th International Technical Meeting of the Satellite Division of The Institute of Navigation, Fort Worth, Texas, Sept. 26–29, 2006, pp. 1800–1810.

• PyGNSS

Python GNSS Receiver: An Object-Oriented Software Platform Suitable for Multiple Receivers” by E. Wycoff, Y. Ng and G.X. Gao in GPS World, Vol. 26, No. 2, Feb. 2015, pp. 52–57.

• 3D Maps for Multipath Detection

“NLOS Correction/Exclusion for GNSS Measurement Using RAIM and City Building Models” by L.-T. Hsu, Y. Gu and S. Kamijo in Sensors, Vol. 15, No. 7, 2015, pp. 17329–17349, doi: 10.3390/s150717329.

“GPS Multipath Detection and Rectification Using 3D Maps” by S. Miura, S. Hisaka and S. Kamijo in Proceedings of ITSC 2013, the 16th International IEEE Conference on Intelligent Transportation Systems, The Hague, The Netherlands, Oct. 6–9, 2013, pp. 1528–1534, doi: 10.1109/ITSC.2013.6728447.

“Urban Multipath Detection and Mitigation with Dynamic 3D Maps for Reliable Land Vehicle Localization” by M. Obst, S. Bauer and G. Wanielik in Proceedings of IEEE/ION PLANS 2012, the Position, Location, and Navigation Symposium, Myrtle Beach, South Carolina, April 23–26, 2012, pp. 685–691, doi: 10.1109/PLANS.2012.6236944.

• Virtual Transmitters

“Simultaneous Localization and Mapping in Multipath Environments” by C. Gentner, B. Ma, M. Ulmschneider, T. Jost and A. Dammann in Proceedings of IEEE/ION PLANS 2016, the Position, Location, and Navigation Symposium, Savannah, Georgia, April 11–14, 2016, pp. 807–815, doi: 10.1109/PLANS.2016.7479776.

About the Author: Yuting Ng

Yuting Ng received her bachelor’s degree in electrical engineering and her master’s degree in aerospace engineering from the University of Illinois at Urbana-Champaign in 2014 and 2016, respectively. Her research interests are advanced signal processing, satellite navigation systems and radar.

About the Author: Grace Xingxin Gao

Grace Xingxin Gao received a Ph.D. degree in electrical engineering from Stanford University. She is an assistant professor in the Aerospace Engineering Department at the University of Illinois at Urbana-Champaign.