Oh, SewoongKarbasi, AminMontanari, Andrea2009-08-272009-08-272009-08-272009https://infoscience.epfl.ch/handle/20.500.14299/42254Sensor localization from only connectivity information is a highly challenging problem. To this end, our result for the first time establishes an analytic bound on the performance of the popular MDS-MAP algorithm based on multidimensional scaling. For a network consisting of n sensors positioned randomly on a unit square and a given radio range r=o(1), we show that resulting error is bounded, decreasing at a rate that is inversely proportional to r, when only connectivity information is given.The same bound holds for the range-based model, when we have an approximate measurements for the distances, and the same algorithm can be applied without any modification.text::report