Advanced Techniques for Mobile Localization and Tracking

There is an exponential growth of smartphone usage and computational capability in the past several years. The widespread usage of smartphones provides a unique opportunity for large-scale monitoring of urban and suburban environments. For example, aggregated and anonymous localization and tracking of smartphones of a subset of people in a particular area enable several applications such as monitoring street traffic flow and crowd movement. With the increasing computational and sensing capability of smartphones, it is now possible to build compute-intensive applications such as high-accuracy localization of a smartphone by video analysis, which can be more accurate and offers and attractive complement to the GPS. How- ever, there are many challenges for building these applications effectively, such as low-level and domain-specific computation methods, accuracy, resource cost, and efficient system and network architecture. In this dissertation, we address some of these fundamental challenges and develop three systems in the context of localization and tracking. First, we present a system for tracking unmodified smartphones using Wi-Fi. In this system, we use hidden-Markov-model along with map topology and signal strength characteristics to achieve high accuracy localization and tracking in challenging conditions such as sparse packet reception, signal strength variation, and a variable number of received packets. Furthermore, we use low-level Wi-Fi protocol features involving association process and management frames to obtain additional packets from a passing smartphone for improved tracking accuracy. Second, we present an online GPS tracking system that transmits the GPS locations to a central server over a cellular uplink with controllable location error, data usage budget, and reporting delay. We also show the first fundamental three-way trade-off between error, budget, and delay in such a system. Finally, we present a system for sub-meter localization of smartphones using video analysis. In this system, we use the 3D reconstruction of the environment and efficient image feature matching to obtain sub-meter accurate localization in both indoor and outdoor environments. Here, we optimize various stages of the localization pipeline such as compression of the 3D reconstruction and features, and interleaved matching and tracking to achieve near real-time operation.