TY - GEN
T1 - Sensor network localization from local connectivity
T2 - IEEE Information Theory Workshop 2010, ITW 2010
AU - Oh, Sewoong
AU - Montanari, Andrea
AU - Karbasi, Amin
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77954824901&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954824901&partnerID=8YFLogxK
U2 - 10.1109/ITWKSPS.2010.5503144
DO - 10.1109/ITWKSPS.2010.5503144
M3 - Conference contribution
AN - SCOPUS:77954824901
SN - 9781424463725
T3 - IEEE Information Theory Workshop 2010, ITW 2010
BT - IEEE Information Theory Workshop 2010, ITW 2010
Y2 - 6 January 2010 through 8 January 2010
ER -