OFA: An optimistic approach to conquer flip ambiguity in network localization

Accurate self-localization is a key enabling technique for many pervasive applications. Existing approaches, most of which are multilateration based, often suffer ambiguities, resulting in huge localization errors. To address this problem, previous approaches discard those positioning results with possible flip ambiguities, trading the localization performance for the result robustness. However, the high false positive rate of flip prediction incorrectly rejects many reliable location estimates. By exploiting the characteristics of flip ambiguity, which causes either huge or zero error, we propose the concept of optimistic localization and design an algorithm, OFA, that employs a global consistency check and a location correction phase in the localization process. We analyze the performance gain and cost of OFA, and further evaluate this design through extensive simulations. The results show that OFA obtains robustness with extremely low performance cost, so as to reduce the requirement on the average degree from 25 to 10 for robustly localizing a network.