A Computational Geometry Method for Localization Using Differences of Distances

作者：Xu Xiaochun^*; Rao Nageswara S V; Sahni Sartaj

来源：ACM Transactions on Sensor Networks, 2010, 6(2): 10.

DOI：10.1145/1689239.1689240

• Algorithms
• Measurement
• DTOA localization
• distance-difference triangulation
• geometric search
• sensor networks

We present a computational geometry method for the problem of estimating the location of a source in the plane using measurements of distance-differences to it. Compared to existing solutions to this well-studied problem, this method is: (a) computationally more efficient and adaptive in that its precision can be controlled as a function of the number of computational operations, and (b) robust with respect to measurement and computational errors, and is not susceptible to numerical instabilities typical of existing linear algebraic or quadratic methods. This method employs a binary search on a distance-difference curve in the plane using a second distance-difference as the objective function. We show the correctness of this method by establishing the unimodality of directional derivative of the objective function within each of a small number of regions of the plane, wherein a suitable binary search is supported. The computational complexity of this method is O(log(1/gamma)), where the computed solution is guaranteed to be within a distance. of the actual location of the source. We present simulation results to compare this method with existing DTOA localization methods.

• 出版日期2010-2