Lighthouse: Enabling Landmark-Based Accurate and Robust Next Generation Indoor LBSs on a Worldwide Scale

A WiFi-based landmark (LM) is a unique point in the physical space that has a repeatable and identifiable WiFi signature as sensed by a mobile device. We present Lighthouse, a new class of WiFi landmarks based on concepts from computational geometry theory that can be leveraged to provide worldwide robust and accurate location based services (LBSs). The proposed Lighthouse landmarks have the nice properties of being abundant in space, hardware-and carry position-independent, can be computed efficiently from a single scan, are confined to a small area of space, do not restrict the user movement path, and do not require any calibration. We show that the positioning error of the Lighthouse landmarks is bounded and present the different extensions that allow it to handle practical situations including the noisy wireless channel, different AP transmit powers, obstacles in the environment, among others. We further present efficient algorithms for extracting them from WiFi scans. We have implemented and evaluated Lighthouse using thousands of surveys collected from different cities worldwide over a six months period. Our results show that Lighthouse's landmarks are one order of magnitude more frequent in the environment compared to the other state-of-the-art WiFi-based landmarks. In addition, the median accuracy of determining the LMs location is less than 3.6 meters. This accuracy is robust over time, different phones hardware, phone carrying positions, and parameters configurations; highlighting the promise of Lighthouse landmarks for enabling the next generation LBSs on a worldwide scale.