Accurate, Low-Energy Trajectory Mapping for Mobile Devices

Arvind Thiagarajan, Lenin S. Ravindranath, Hari Balakrishnan, Samuel Madden, Lewis Girod
8th USENIX Symp. on Networked Systems Design and Implementation (NSDI), Boston, MA, March 2011

CTrack is an energy-efficient system for trajectory mapping using raw position tracks obtained largely from cellular base station fingerprints. Trajectory mapping, which involves taking a sequence of raw position samples and producing the most likely path followed by the user, is an important component in many location-based services including crowdsourced traffic monitoring, navigation and routing, and personalized trip management. Using only cellular (GSM) fingerprints instead of power-hungry GPS and WiFi radios, the marginal energy consumed for trajectory mapping is zero. This ap- proach is non-trivial because we need to process streams of highly inaccurate GSM localization samples (average error of over 175 meters) and produce an accurate trajectory. CTrack meets this challenge using a novel two-pass Hidden Markov Model that sequences cellular GSM fingerprints directly without converting them to geographic coordinates, and fuses data from low-energy sensors available on most commodity smartphones, including accelerometers (to detect movement) and magnetic compasses (to detect turns). We have implemented CTrack on the Android platform, and evaluated it on 126 hours (1,074 miles) of real driving traces in an urban environment. We find that CTrack can retrieve over 75% of a user’s drive accurately in the median. An important by-product of CTrack is that even devices with no GPS or WiFi (constituting a significant fraction of today’s phones) can contribute and benefit from accurate position data.

[PDF (0KB)]

Bibtex Entry:

   author =       "Arvind Thiagarajan and Lenin S. Ravindranath and Hari Balakrishnan and Samuel Madden and Lewis Girod",
   title =        "{Accurate, Low-Energy Trajectory Mapping for Mobile Devices}",
   booktitle =    {8th USENIX Symp. on Networked Systems Design and Implementation (NSDI)},
   year =         {2011},
   month =        {March},
   address =      {Boston, MA}