Reducing the number of flips in trilateration with noisy range measurements

Abstract

Many applications in wireless networks depend on accurate localization services to operate properly. Trilateration is a widely used range-based localization method that can operate in polynomial time, given that the distance measurements are precise. However in real-world, range measurements tend to have errors due to internal and external factors. Flip ambiguities that occur during trilateration as a consequence of imprecise range measurements turn localization via trilateration into an intractable problem. In this paper, we analyze flip ambiguities due to range measurement errors and propose a heuristic solution that tries to minimize the number of flips in trilateration even in highly noisy environments. We simulate our algorithms under various noise scenarios and observe that the use of our heuristic based solution effectively decreases the number of flips in trilateration and increases the accuracy of the localization. Copyright © 2013 ACM.