Every day millions of smartphone users worldwide rely on Global Navigation Satellite Systems (GNSS), such as GPS, for navigation purposes. However, in urban environments where satellite signal reception is poor, GNSS positioning errors can become severe – in the range of tens of meters. To solve this problem, we take the view that GNSS devices, such as smartphones and tablets, are effectively passive environment sensors. The reason is simple: when a building blocks a satellite signal, the received signal strength decreases. Smartphones can log the information describing such “shadowing” events, including satellite signal to noise ratio (SNR), satellite coordinates (elevation, azimuth), and the approximate device coordinates (along with an estimated uncertainty value). With enough such data in a particular region, one can build 3D environment maps using machine learning techniques. Specifically, we show that the posterior probability distribution of the map can be modeled as sparse factor graph on which the popular Loopy Belief Propagation algorithm can be used for efficient Bayesian inference. Finally, after computing a map, one can compare new measured satellite SNR readings to predicted SNR readings (given the 3D map and a set of possible positions). In the literature, such a technique is known as Shadow Matching, the end result of which is a more accurate location estimate for the GNSS receiver. This step can be done either online (filtering scenario) for real-time GNSS position improvement, or computed offline in batch form (smoothing scenario).
We have field tested our GPS SNR based mapping and positioning improvement algorithms, which we call ShadowMaps, both on campus at UCSB and in downtown Santa Barbara. Example (offline generated) localization improvement results in downtown Santa Barbara are shown below for an Android smartphone with cellular assisted GPS+GLONASS (a-GNSS). The true path is marked in yellow, initial localization with uncertainty using a-GNSS is shown in red, and the post-ShadowMaps corrected estimate is shown in blue.
Recently, we demonstrated a version of the same system in real-time at MobiCom 2014 in Maui, where we received the Runner-up Best Demo Award. The video below shows a portion of a similar demo on UCSB campus. Jason, in the Google Hangouts video on the left, is walking around campus with a Galaxy Nexus Android phone on which our ShadowHawk Phone Finder app is installed. To the right we have the ShadowHawk web interface, which displays the estimated device location in a map view as well as some satellite and 3D map information. Specifically, the map view displays the original and corrected location estimates with uncertainty in red and blue, respectively, as well some numerical metrics just below. In the satellite skyview, the positions and likelihoods of all satellites are shown; the background image is the 3D occupancy grid map from the viewpoint of the device which was constructed offline in advance using about 7 hours of GPS data collected in the same area. At the bottom, some of the satellite information is shown in tabular form. For additional information please refer to the MobiCom demo paper.
Andrew Irish, Danny Iland
Post Doctoral Researchers
Upamanyu Madhow, Joao Hespanha