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_17: This paper focuses on the principled study of distance reconstruction for distance-based node localization. We address an important issue in node localization by showing that a highly incomplete set of inter-node distance measurements obtained in ad-hoc node deployments carries sufficient information for the accurate reconstruction of the missing distances, even in the presence of noise and sensor node failures. We provide an efficient and provably accurate algorithm for this reconstruction, and we show that the resulting error is bounded, decreasing at a rate that is inversely proportional to radicn, the square root of the number of nodes in the region of deployment. Although this result is applicable to many localization schemes, in this paper we illustrate its use in conjunction with the popular multidimensional scaling algorithm. Our analysis reveals valuable insights and key factors to consider during the sensor network setup phase, to improve the quality of the position estimates
summary: Our first result, specifically the analysis of MDS-MAP , has a similar flavour as in @cite_17 . We provide a theoretical guarantee that backs up experimental results. We use shortest paths as our primary guess for the missing entries in the distance matrix and apply MDS to find the topology of the network. In contrast to @cite_17 , we require weaker assumptions for our results. More specifically, we assume that only neighbouring sensors have information about each other and that only connectivity information is known. Furthermore, the knowledge of detection probabilities plays no role in our analysis or the algorithm. And last, in our analysis we assume that the average degree grows logarithmically-not linearly- with the number of sensors, which results in needing many less revealed entries in the distance matrix. In particular, the last condition is quite realistic: If the average degree grows any slower then the network is not even connected (more on this issue in ). As the shortest paths algorithm works for both rage-free and range-aware cases, our analysis includes both and provides the first error bounds on the performance of MDS-MAP .