An Algorithmic and Systematic Approach for Improving Robustness of TOA-Based Localization

Indoor localization using Time-of-Arrival (TOA) of ultrasound is accurate, but remarkable errors may occur occasionally due to effects by indoor environment issues, such as when ultrasound propagates in Non-Line-Of-Sight (NLOS) paths, or synchronization signal is interfered by background signals. This paper presents an algorithmic and systematic approach to address these issues to improve robustness of ultrasound TOA positioning. We firstly show from an optimization point of view that NLOS detection problem is NP-hard. We propose a novel clustering and filtering (COFFEE) algorithm to conduct density-based clustering iteratively on a bipartite graph model, which enables accurate, robust positioning and efficient NLOS outlier detection. Then, we develop a systematic method to address the robust time synchronization problem, which is called first-falling-edge time synchronization. It guarantees robust time synchronization even in severe interference environments. Both the COFFEE algorithm and the robust synchronization scheme are developed and implemented in a ultrasound positioning prototype called Dragon. Extensively simulations and experiments in Dragon show that the proposed methodologies outperform the robustness performances of the state-of-the-art methods, which demonstrate great improvements in various interference scenarios.