Sensor network localization from local connectivity: Performance analysis for the mds-map algorithm

This paper addresses the problem of determining the node locations in ad-hoc sensor networks when only connectiv-ity 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 er-ror decreasing at a rate inversely proportional to the radio range r. The main limitation of MDS-MAP is the assump-tion that the available connectivity information is processed in a centralized way. In this work we investigate a practically important ques-tion whether similar performance guarantees can be obtained in a distributed setting. In particular, we analyze the per-formance 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 esti-mate x̂i and the correct position xi is bounded by ‖xi − x̂i ‖ ≤ 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 approxi-mate measurement for the distances is provided