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.


    • LTHC-REPORT-2009-001

    Record created on 2009-08-27, modified on 2016-08-08

Related material