Sensor Network Localization from Local Connectivity : Performance Analysis for the MDS-MAP Algorithm

Sensor 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