text: We consider the problem of localizing wireless devices in an ad-hoc network embedded in a d-dimensional Euclidean space. Obtaining a good estimation of where wireless devices are located is crucial in wireless network applications including environment monitoring, geographic routing and topology control. When the positions of the devices are unknown and only local distance information is given, we need to infer the positions from these local distance measurements. This problem is particularly challenging when we only have access to measurements that have limited accuracy and are incomplete. We consider the extreme case of this limitation on the available information, namely only the connectivity information is available, i.e., we only know whether a pair of nodes is within a fixed detection range of each other or not, and no information is known about how far apart they are. Further, to account for detection failures, we assume that even if a pair of devices is within the detection range, it fails to detect the presence of one another with some probability and this probability of failure depends on how far apart those devices are. Given this limited information, we investigate the performance of a centralized positioning algorithm MDS-MAP introduced by , and a distributed positioning algorithm, introduced by , called HOP-TERRAIN. In particular, for a network consisting of n devices positioned randomly, we provide a bound on the resulting error for both algorithms. We show that the error is bounded, decreasing at a rate that is proportional to R Rc, where Rc is the critical detection range when the resulting random network starts to be connected, and R is the detection range of each device.
  @cite_8: A distributed algorithm for determining the positions of nodes in an ad-hoc, wireless sensor network is explained in detail. Details regarding the implementation of such an algorithm are also discussed. Experimentation is performed on networks containing 400 nodes randomly placed within a square area, and resulting error magnitudes are represented as percentages of each node’s radio range. In scenarios with 5 errors in distance measurements, 5 anchor node population (nodes with known locations), and average connectivity levels between neighbors of 7 nodes, the algorithm is shown to have errors less than 33 on average. It is also shown that, given an average connectivity of at least 12 nodes and 10 anchors, the algorithm performs well with up to 40 errors in distance measurements.
summary: All the above analytical results crucially rely on the fact that there is a central processor with access to the inter-sensor distance measurements. However, as we have mentioned earlier, centralized algorithms suffer from the scalability problem and require higher computational complexity. Hence, a distributed algorithm with similar a performance bound is desirable. In our second result, we analyse the reconstruction error of a distributed sensor localization algorithm. To the best of our knowledge we show for the first time that Hop-TERRAIN , introduced in @cite_8 , achieves a bounded error when only local connectivity information is given.