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 xi and the correct position xi is bounded by ||xi-xi|| < r0/r + o(1), where r0=Cd (log n/ n)(1/d) for some constant Cd 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