Localization from Connectivity in Sensor Networks

Yi Shang, Wheeler Ruml, Ying Zhang, and Markus P.J. Fromherz

Abstract

We propose an approach that uses connectivity information - who is within communications range of whem - to derive the locations of nodes in a network. The approach can take advantage of additional information, such as estimated distances between neighbors or known positions for certain anchor nodes, if it is available. It is based on multidimensional scaling (MDS), an efficient data analysis technique O(n³) time for a network of n nodes. Unlike previous approaches, MDS takes full advantage of connectivity or distance information betwen nodes that have yet to be localized. Two methods are presented: a simple method that builds a global map using MDS and a more complicated one that builds small local maps and then patches them together to form a glabal map. Furthermore, least-squares optimization can be incorporated into the methods to further improve the solutions at the expense of additional computation. Through simulation studies on uniform as well as irregular networkks, we show that the methods achieve more accurate solutions than previous methods, especially when there are few anchor nodes. They can even yield good relative maps when no anchor nodes are available.

For PDF file, send mail to shangy@missouri.edu or try TPDS Online (IEEE CS subscription needed).

Back to the top.