Massachusetts Institute of Technology, Cambridge, MA,
This dissertation is concerned with the problem of determining the track or trajectory of a mobile
device — for example, a sequence of road segments on an outdoor map, or a sequence of rooms
visited inside a building — in an energy-efficient and accurate manner.
GPS, the dominant positioning technology today, has two major limitations. First, it consumes
significant power on mobile phones, making it impractical for continuous monitoring. Second, it
does not work indoors. This dissertation develops two ways to address these limitations: (a) sub-
sampling GPS to save energy, and (b) using alternatives to GPS such as WiFi localization, cellular
localization, and inertial sensing (with the accelerometer and gyroscope) that consume less energy
and work indoors. The key challenge is to match a sequence of infrequent (from sub-sampling) and
inaccurate (from WiFi, cellular or inertial sensing) position samples to an accurate output trajectory.
This dissertation presents three systems, all using probabilistic models, to accomplish this
matching. The first, VTrack, uses Hidden Markov Models to match noisy or sparsely sampled
geographic (lat, lon) coordinates to a sequence of road segments on a map. We evaluate VTrack on
800 drive hours of GPS and WiFi localization data collected from 25 taxicabs in Boston. We find
that VTrack tolerates significant noise and outages in location estimates, and saves energy, while
providing accurate enough trajectories for applications like travel-time aware route planning.
CTrack improves on VTrack with a Markov Model that uses “soft” information in the form of
raw WiFi or cellular signal strengths, rather than geographic coordinates. It also uses movement
and turn “hints” from the accelerometer and compass to improve accuracy. We implement CTrack
on Android phones, and evaluate it on cellular signal data from over 126 (1,074 miles) hours of
driving data. CTrack can retrieve over 75% of a user’s drive accurately on average, even from
highly inaccurate (175 metres raw position error) GSM data.
iTrack uses a particle filter to combine inertial sensing data from the accelerometer and gyro-
scope with WiFi signals and accurately track a mobile phone indoors. iTrack has been implemented
on the iPhone, and can track a user to within less than a metre when walking with the phone in the
hand or pants pocket, over 5× more accurately than existing WiFi localization approaches. iTrack
also requires very little manual effort for training, unlike existing localization systems that require
a user to visit hundreds or thousands of locations in a building and mark them on a map.