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 \textit{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 the 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 \textit{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 $\hat{x}_i$ and the correct position $x_i$ is bounded by \begin{displaymath} |x_i-\hat{x}_i| \leq \frac{r_0}{r}+o(1), \end{displaymath} where $r_0=C_d (\log n/ n)^{\frac{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.