Accurate and Energy-Efficient GPS-Less Outdoor Localization

Location-based services have become an important part of our daily lives. However, such services require continuous user tracking while preserving the scarce cell-phone battery resource. In this article, we present Dejavu , a system that uses standard cell-phone sensors to provide accurate and energy-efficient outdoor localization. Dejavu is capable of localizing and navigating both pedestrian and in-vehicle users in real time. Our analysis shows that, whether walking or in-vehicle, when the user encounters a road landmark such as going inside a tunnel, ascending a staircase, or even moving over a bump, all these different landmarks affect the inertial sensors on the phone in a unique pattern. Dejavu employs a dead-reckoning localization approach and leverages these road landmarks, among other automatically discovered virtual landmarks, to reset the dead-reckoning accumulated error and achieve accurate localization. To maintain a low energy profile, Dejavu uses only energy-efficient sensors or sensors that are already running for other purposes. Moreover, Dejavu provides a localization confidence measure along with its predicted location. This improves the usability of the predicted location from end users’ perspective. We present the design of Dejavu and how it leverages crowd-sourcing to automatically learn virtual landmarks and their locations. Our evaluation results from implementation on different Android devices using different testbeds showing that Dejavu can localize cell-phones in vehicles with a median error of 8.4 m in city roads and 16.6 m on highways and can localize cell-phones carried by pedestrians with a median error of 3.0m. Moreover, compared to the global position system (GPS) and other state-of-the-art systems, Dejavu can extend the battery lifetime by up to 347%, while achieving even better localization results than GPS in the more challenging in-city areas. In addition, Dejavu estimates the localization confidence measure accurately with a median error of 2.3m and 31cm for in-vehicle and pedestrian users, respectively.