Indoor localization systems typically determine a position using either ranging measurements, inertial sensors, environmental-specific signatures or some combination of all of these methods. Given a floor plan, inertial and signature-based systems can converge on accurate locations by slowly pruning away inconsistent states as a user walks through the space. In contrast, range-based systems are capable of instantly acquiring locations, but they rely on densely deployed beacons and suffer from inaccurate range measurements given non-line-of-sight (NLOS) signals. In order to get the best of both worlds, we present an approach that systematically exploits the geometry information derived from building floor plans to directly improve location acquisition in range-based systems. Our solving approach can disambiguate multiple feasible locations taking into account a mix of LOS and NLOS hypotheses to accurately localize with significantly fewer beacons. We demonstrate our geometry-aware solving approach using a new ultrasonic beacon platform that is able to perform direct time-of-flight ranges on commodity smartphones. The platform uses Bluetooth Low Energy (BLE) for time synchronization and ultrasound for measuring propagation distance. We evaluate our system's accuracy with multiple deployments in a university campus and show that our approach shifts the 80% accuracy point from 4-8m to 1m as compared to solvers that do not use the floor plan information. We are able to detect and remove NLOS signals with 91.5% accuracy.

In this paper, we address the problem of range-based beacon placement given a floor plan to support indoor localization systems. Existing approaches for trilateration require three or more beacons to determine a unique position solution. We show that with prior knowledge of the map and a model of beacon coverage, it is possible to uniquely localize with only two beacons. This not only reduces installation cost by requiring fewer nodes, but can also improve robustness. One of the main challenges with respect to beacon placement algorithms is defining a metric for estimating performance. We propose augmenting the commonly used Geometric Dilution of Precision (GDOP) metric to account for indoor spaces. We then use this enhanced GDOP metric as part of a toolchain to compare various beacon placement algorithms in terms of coverage and expected accuracy. When applied to a set of real floor plans, our approach is able to reduce the number of beacons between 22% and 60% (33% on an average) as compared to standard trilateration.