@inproceedings{a70b326e83324599ae6ded9a7b2e40fd,

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

abstract = "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 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 approximate measurement for the distances is provided.",

keywords = "Distributed, Localization, Sensor network",

author = "Amin Karbasi and Sewoong Oh",

year = "2010",

doi = "10.1145/1811099.1811047",

language = "English (US)",

isbn = "9781450302111",

series = "Performance Evaluation Review",

number = "1 SPEC. ISSUE",

pages = "61--70",

booktitle = "SIGMETRICS'10 - Proceedings of the 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems",

edition = "1 SPEC. ISSUE",

note = "2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'10 ; Conference date: 14-06-2010 Through 18-06-2010",

}