Relative Localization with GPS
In many mobile wireless applications such as the automated driving of cars, formation flying of unmanned air vehicles, and source localization or target tracking with wireless sensor networks, it is more important to know the precise relative locations of nodes than their absolute coordinates. GPS, the most ubiquitous localization system available, generally provides only absolute coordinates. Furthermore, low-cost receivers can exhibit tens of meters of error or worse in challenging RF environments. This project is developing an approach that uses GPS to derive relative location information for multiple receivers. Nodes in a network share their raw satellite measurements and use this data to track the relative motions of neighboring nodes as opposed to computing their own absolute coordinates. The system has been implemented using a network of Android phones equipped with a custom Bluetooth headset and integrated GPS chip to provide raw measurement data. Our evaluation shows that centimeter-scale tracking accuracy at an update rate of 1 Hz is possible under various conditions with the technique. This is more than an order of magnitude more accurate than simply taking the difference of reported absolute node coordinates or other simplistic approaches due to the presence of uncorrelated measurement errors.
Technical Overview
Our approach to high-accuracy relative localization comes from two separate and distinct research areas. The first area involves computing highly-accurate tracking results between pairs of mobile nodes through time, and the second area uses these precise tracking results to unambiguously solve for receiver-receiver baselines at any given point in time.
Pairwise Node Tracking
Our precise relative node tracking methodology is achieved via three main concepts:
- Identification and characterization of error sources specific to the dual-receiver localization case,
- Extrapolation of satellite measurement data from independent GPS receivers to a common time epoch, and
- Creation of a temporal observation model describing the relative changes in range between a satellite and two receivers through time.
Due to the imprecision of local clocks used in low-cost GPS receivers, it was found that the actual measurement times of observation sets taken at the same apparent time by two independent receivers may differ by up to several milliseconds. The high orbital velocities of the GPS satellites, coupled with the rotation of both the Earth and the local coordinate frames of the GPS receivers themselves during these seemingly small timing discrepancies, cause non-trivial relativistic errors to be introduced into the standard GPS positioning models when combined in a relative positioning sense.
In order to overcome these errors, we first characterize them as either signal propagation errors or time bias errors and quantify their respective effects on relative positioning accuracy. We then employ a correction procedure which is used to extrapolate the satellite orbital positions, raw measurement data, and receiver coordinate frames into a cohesive unit, with the end result that relativistic effects that originally introduced errors on the order of 1-3 meters per satellite observation now result in only micrometer-scale inaccuracies.
Using the corrected satellite observations, we developed a so-called temporal double-differencing model which is able to very precisely track the relative changes in range between a single satellite and two receivers through time. By noting that these changes in satellite-receiver range can be geometrically linked to the relative change in baseline between two receivers, we developed an algorithm whereby sets of receiver-receiver baselines can be accurately tracked without requiring knowledge of the precise absolute locations of any of the receivers taking part in the localization procedure.
While the accuracies achievable by our relative tracking system show significant improvement over existing GPS-only solutions, our tracking approach suffers from one serious limitation, namely that it requires manual baseline initialization. Additionally, if a complete loss of satellite locks is experienced at any point during the tracking procedure, manual re-initialization must again be carried out each and every time. As such, we extended our tracking algorithm to carry out its own initialization routines, such that it can be used as a complete, standalone localization service. This is described in the next section.
Relative Localization
The Ambiguity Function Method (AFM) was introduced in 1981 by Counselman and Gourevitch. This method is unique in that it leverages the “integer-ness” of the ambiguity values in the double-differenced carrier phase model to determine a baseline position which minimizes the range errors in the participating satellites’ observations. However, computing the AFM is too computationally expensive to carry out at each epoch. Instead, we rely on our accurate tracking results to track the peaks in the function across time until only the peak corresponding to the true location remains. A detailed description of the technique is provided in the dissertation linked below as well as in a paper accepted for SenSys 14.
Relevant Publications
Details about our approach can be found in the following papers:
"Accurate Real-Time Relative Localization Using Single-Frequency GPS", The ACM Conference on Embedded Networked Sensor Systems (SenSys '14), Memphis, TN, ACM, 11/2014. Download: Accurate Real-Time Relative Localization Using Single-Frequency GPS.pdf (3.35 MB)
"High-Accuracy Differential Tracking of Low-Cost GPS Receivers", ACM 11th International Conference on Mobile Systems, Applications, and Services (MobiSys '13), Taipei, Taiwan, ACM, 06/2013. Download: mobisys229-hedgecock.pdf (3.74 MB)
"Accurate Real-Time Localization Using Single-Frequency GPS", ACM Conference on Embedded Networked Sensing Systems (SenSys '14) Download: sensys-GPS.pdf
"Precise Real-Time Relative Localization Using Single-Frequency GPS", Electrical Engineering, vol. PhD, Nashville, Vanderbilt University, pp. 135, 05/2014. Download: RHedgecock-Dissertation.pdf (4.29 MB)
Demos and Results
Our team built a fully functional hardware prototype of our relative localization system, enabling us to carry out a series of proof-of-concept experiments. The following graphics illustrate some of the results achievable using our approach.
Running Track
(Tracking-Only Results)
In this experiment, one receiver was placed in a stationary position on the side of a running track, and two receivers were connected to either end of a rigid, 9-foot long pole. The pole was held perpendicular to the direction of motion and walked around the track in the middle of lane 4, producing the following results (where the left-most figure shows the ground truth, the middle figure shows the built-in results produced by the GPS chip itself, and the right-most figure shows our results). The dotted line represents the ground truth in the last two figures.
 |
 |
 |
Football Field
(Full Localization Results)
In this experiment, we placed a node on the roof of our office building and then traveled to a football stadium approximately a mile away. We placed two nodes on the field, one at the 0-yard line and one at the 20-yard line, with both nodes located on the same sideline. We then walked the two nodes in parallel along their respective yard lines. Once the nodes reached the opposite end, one node would remain stationary while the other traveled 40 yards along the sideline to the opposite side of the first node, such that the node pair remained 20 yards apart. They would then walk in parallel along their respective yard lines and repeat this laddering process until the entire football field had been traversed. The first two figures show the individual paths of the mobile nodes as computed by the node on our office building, and the third figure shows a composite view of both nodes together. For comparison, the bottom figure shows a zoomed-in view of the paths of one of the nodes as computed by our technique (in pink) compared to that of the built-in positioning algorithm of the GPS chip itself (in yellow).
 |
 |
 |
 |
||
High-Speed Driving
(Full Localization Results)
In this experiment, 3 nodes were attached to the roof of a car and driven in a large 12.2-km loop around Nashville. The route took us through narrow alleyways, suburban roads, and an interstate highway, driving at speeds ranging from 15mph all the way up to 70mph, before returning to the same starting position from which we left. The following figure shows a track of one of the nodes on the roof of the car as localized by a stationary receiver located in a parking lot ranging anywhere from 0 to 3.5-km away at any given time:
Video Demonstration
(Tracking-Only Results)
The following 5-minute video was accepted and shown at the MobiSys '13 conference. It shows the in-depth tracking-only results from the driving experiment previously described in Nashville, TN:
Source Code and Data Sets
The code for our relative GPS tracking algorithm is open-source and can be downloaded from https://github.com/isisdeveloper/relativegps. Note that all code is distributed under the GNU Affero GPL license and certain restrictions apply. Please refer to the README file in the root directory of the source for further information.
Additionally, many of the datasets used for experimentation in the aforementioned publications can be downloaded as ZIP archives from the following links. Each archive contains a number of GPS log files in the proprietary UBX format of the uBlox receiver (see UBX Protocol and Specifications), along with a README file explaining the GPS environment, receiver configuration, and approximate ground truth for the included files.
Sponsors
This work has been supported by the National Science Foundation under the CNS-NeTS program (Grant #1218710), a Google Research Award, and Project #TAMOP-4.2.2.A-11/1/KONV-2012-0073 of the European Union and the European Social Fund.
Copyright © 2011 ISIS / Vanderbilt University / School of Engineering