Beacon-based time-of-flight indoor localization systems have shown great promise for applications ranging from indoor navigation to asset tracking. In large-scale deployments, a major practical challenge is determining the placement of a minimal number of beacons that ensures full coverage -- each point in the domain has line-of-sight paths to enough beacons to uniquely localize itself. Three beacons with line-of-sight paths are always enough, but two beacons within line of sight may also work, given a favorable geometry. In this paper, we propose two beacon placement algorithms that leverage the floor plan geometry with provable theoretical guarantees. First, we present a greedy algorithm using properties of sub-modular functions to place O(OPT · ln m) beacons, where m is the number of discrete location points in the region that need to be localized, and OPT is the size of the optimal solution. Second, we present a random sampling algorithm that places O (OPT · log(OPT)) beacons while localizing all targets. We evaluate our algorithms on both real-world and randomly generated floor plans. Our algorithms place on an average 6 ~ 23% and 12% fewer beacons in real-world topologies and randomly generated floor plans respectively, as compared to prior work. We also present a study where we ask users to attempt to place nodes manually and discover that even humans that are well versed on the coverage problem find it hard to balance the trade-off between the number of beacons and area localized.

In this paper, we show how beacon-based indoor localization and additional environmental fingerprints like magnetic field data can be used to both accelerate and increase the robustness of Augmented Reality (AR) relocalization. We show how the combination of Visual Inertial Odometry (VIO) and beacons can be used to construct a dense indoor magnetic field map that can act as a fine-grained calibration for compasses to quickly determine a mobile device's orientation. Unique to our approach is that we leverage accurate VIO trajectories to provide full vector magnetic field mapping that can be collected and used with devices placed in any orientation. We demonstrate a system running on an iPhone that can acquire location with 80th percentile 3D accuracy of 27cm in LOS and 46cm in NLOS, and our magnetic field mapping approach can instantly estimate orientation with 80th percentile accuracy of 11.7 degrees. We demonstrate an end-to-end system for generating a magnetic field map and subsequently localizing and tracking mobile users using beacons and VIO. This has the side effect of enabling multi-user (even cross-platform) AR applications, as all users can now be localized with respect to a common global reference without any sharing of visual feature maps.

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.

We demonstrate multi-user persistent Augmented Reality (AR) on mobile devices with a novel technique that provides nearly instant acquisition of location and orientation. Visual Inertial Odometry (VIO) provides accurate position and orientation tracking relative to device start-up for AR applications. Unfortunately, the tracking is local to the AR session of a single user and is not anchored in a global coordinate system. In order to provide all devices an accurate location in a common frame of reference, we utilize UWB nodes that range to the devices. To avoid the long startup time required to compute the device's orientation, we propose a novel technique that utilizes previously recorded magnetic field information to rapidly calibrate the compass. In order to simplify setup, we demonstrate automatic mapping of beacon locations and surveying of magnetic field by a pedestrian walking around the test area with a mobile device.

In this paper, we introduce Pulsar, a wireless time transfer platform that can achieve clock synchronization to better than five nanosecond between indoor or GPS-denied devices. Nanosecond-level clock synchronization is a missing capability for many real-time applications like next-generation wireless systems that leverage spatial multiplexing to improve channel capacity and provide services like time-of-flight localization. With fine-grained synchronization, both clock stability and propagation delays introduce significant sources of error. Pulsar leverages a stable clock source derived from a Chip-Scale Atomic Clock (CSAC) along with an Ultra-WideBand (UWB) radio able to perform sub-nanosecond packet timestamping to estimate and correct for clock offsets. We design and evaluate a proof-of-concept network-wide synchronization protocol for Pulsar that selects low-jitter links to both estimate the location of nodes and reduce cumulative synchronization error across multiple hops. The Pulsar platform and protocol together provide a phase synchronized one pulse per second (1PPS) signal and 10 MHz reference clock that can be easily integrated with typical enduser applications like software-defined radios and communication systems. We experimentally evaluate the Pulsar platform in terms of clock synchronization accuracy, Allan deviation between pairwise clocks and ranging accuracy to show a clock synchronization of better than five nanoseconds per hop with an average of 2.12 ns and a standard deviation of 0.84 ns. The platform is able to identify and avoid clock error in cases where there is heavy multi-path or non-Line-of-Sight signals.

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.

In this paper, we present the design and evaluation of a platform that can be used for time synchronization and indoor positioning of mobile devices. The platform uses the Time-Difference-Of-Arrival (TDOA) of multiple ultrasonic chirps broadcast from a network of beacons placed throughout the environment to find an initial location as well as synchronize a receiver's clock with the infrastructure. These chirps encode identification data and ranging information that can be used to compute the receiver's location. Once the clocks have been synchronized, the system can continue performing localization directly using Time-of-Flight (TOF) ranging as opposed to TDOA. This provides similar position accuracy with fewer beacons (for tens of minutes) until the mobile device clock drifts enough that a TDOA signal is once again required. Our hardware platform uses RF-based time synchronization to distribute clock synchronization from a subset of infrastructure beacons connected to a GPS source. Mobile devices use a novel time synchronization technique leverages the continuously free-running audio sampling subsystem of a smartphone to synchronize with global time. Once synchronized, each device can determine an accurate proximity from as little as one beacon using TOF measurements. This significantly decreases the number of beacons required to cover an indoor space and improves performance in the face of obstructions. We show through experiments that this approach outperforms the Network Time Protocol (NTP) on smartphones by an order of magnitude, providing an average 720μs synchronization accuracy with clock drift rates as low as 2ppm.

The proliferation of Bluetooth Low-Energy (BLE) chipsets on mobile devices has lead to a wide variety of user-installable tags and beacons designed for location-aware applications. In this paper, we present the Acoustic Location Processing System (ALPS), a platform that augments BLE transmitters with ultrasound in a manner that improves ranging accuracy and can help users configure indoor localization systems with minimal effort. A user places three or more beacons in an environment and then walks through a calibration sequence with their mobile device where they touch key points in the environment like the floor and the corners of the room. This process automatically computes the room geometry as well as the precise beacon locations without needing auxiliary measurements. Once configured, the system can track a user's location referenced to a map.

We demonstrate the Acoustic Location Processing System (ALPS), a platform that augments BLE proximity beacons with ultrasonic transmitters in a manner that allows for precise and robust indoor localization. {\em ALPS} uses Time-Difference-Of-Arrival (TDOA) and Time-Of-Flight (TOF) ranging to accurately localize mobile devices such as off-the-shelf smartphones and tablets in 2D space. Users inside the demo area will be able to determine their location and can directly plot it relatively to a map of the area using our app on a smartphone. Once a receiving device has determined its initial position, it can synchronize its audio clock with the transmission infrastructure to perform TOF-based localization, which provides similar position accuracy to TDOA based localization with fewer beacons. Multilateration and trilateration processing for each device's location is offloaded onto a cloud-based solver that can provide localization as a service to ALPS and similar TOF/TDOA based systems.

In this demonstration, we show an energy measurement system that estimates the energy consumption of individual appliances using a wireless sensor network consisting of contactless electromagnetic field (EMF) sensors deployed near each appliance, and a whole-house power meter. The EMF sensor can detect appliance state transitions within close proximity based on magnetic field fluctuations. Data from these sensors are then relayed back to the main meter using a low-latency wireless sensor networking protocol, where changes in the total power consumption of the house are used to determine the power usage of individual appliances. The sensors are low-cost, easy to deploy and are able to detect current changes associated with the appliance from a few inches away making it possible to externally monitor in-wall wiring to devices like overhead lights or heavy machinery that might operate on multiple phases of the AC distribution system of the building. Appliance-level energy data provide continuous feedback to end users about their consumption patterns and provide building managers accurate information that can be used to target the most effective update and retrofit strategies.

Time synchronization in wireless sensor networks is important for event ordering and efficient communication scheduling. In this paper, we introduce an external hardwarebased clock tuning circuit that can be used to improve synchronization and significantly reduce clock drift over long periods of time without waking up the host MCU. This is accomplished through two main hardware sub-systems. First, we improve upon the circuit presented in [1] that synchronizes clocks using the ambient magnetic fields emitted from power lines. The new circuit uses an electric field front-end as opposed to the original magnetic-field sensor, which makes the design more compact, lower-power, lower-cost, exhibit less jitter and improves robustness to noise generated by nearby appliances. Second, we present a low-cost hardware tuning circuit that can be used to continuously trim a micro-controller's low-power clock at runtime. Most time synchronization approaches require a CPU to periodically adjust internal counters to accommodate for clock drift. Periodic discrete updates can introduce interpolation errors as compared to continuous update approaches and they require the CPU to expend energy during these wake up periods. Our hardware-based external clock tuning circuit allows the main CPU to remain in a deep-sleep mode for extended periods while an external circuit compensates for clock drift. We show that our new synchronization circuit consumes 60% less power than the original design and is able to correct clock drift rates to within 0.01 ppm without power hungry and expensive precision clocks.