Sensor network localization from local connectivity: Performance analysis for the MDS-MAP algorithm

Sewoong Oh, Andrea Montanari, Amin Karbasi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationIEEE Information Theory Workshop 2010, ITW 2010
DOIs
StatePublished - 2010
Externally publishedYes
EventIEEE Information Theory Workshop 2010, ITW 2010 - Cairo, Egypt
Duration: Jan 6 2010Jan 8 2010

Publication series

NameIEEE Information Theory Workshop 2010, ITW 2010

Other

OtherIEEE Information Theory Workshop 2010, ITW 2010
Country/TerritoryEgypt
CityCairo
Period1/6/101/8/10

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Sensor network localization from local connectivity: Performance analysis for the MDS-MAP algorithm'. Together they form a unique fingerprint.

Cite this