Distributed sensor network localization from local connectivity: Performance analysis for the HOP-TERRAIN algorithm

This paper addresses the problem of determining the node locations in ad-hoc sensor networks when only connectivity information is available. In previous work, we showed that the localization algorithm MDS-MAP proposed by Y. Shang et al. is able to localize sensors up to a bounded error decreasing at a rate inversely proportional to the radio range r. The main limitation of MDS-MAP is the assumption that the available connectivity information is processed in a centralized way. In this work we investigate a practically important question whether similar performance guarantees can be obtained in a distributed setting. In particular, we analyze the performance of the HOP-TERRAIN algorithm proposed by C. Savarese et al. This algorithm can be seen as a distributed version of the MDS-MAP algorithm. More precisely, assume that the radio range r = o(1) and that the network consists of n sensors positioned randomly on a d-dimensional unit cube and d + 1 anchors in general positions. We show that when only connectivity information is available, for every unknown node i, the Euclidean distance between the estimate x̂_i and the correct position x_i is bounded by ∥x_i - x̂_i∥ ≤r₀/r + o(1), where r₀ = C_d(log n/n) ^1/d for some constant C_d which only depends on d. Furthermore, we illustrate that a similar bound holds for the range-based model, when the approximate measurement for the distances is provided.