Distributed Graph Layout for Sensor Networks
Craig Gotsman and Yehuda Koren
Vol. 9, no. 3, pp. 327-346, 2005. Regular paper.
Abstract Sensor network applications frequently require that the sensors know their physical locations in some global coordinate system. This is usually achieved by equipping each sensor with a location measurement device, such as GPS. However, low-end systems or indoor systems, which cannot use GPS, must locate themselves based only on crude information available locally, such as inter-sensor distances. We show how a collection of sensors, capable only of measuring distances to close neighbors, can compute their locations in a purely distributed manner, i.e. where each sensor communicates only with its neighbors. This can be viewed as a distributed graph drawing algorithm. We experimentally show that our algorithm consistently produces good results under a variety of simulated real-world conditions, and is relatively robust to the presence of noise in the distance measurements.
Submitted: November 2004.
Revised: July 2005.
Communicated by Emden Gansner and János Pach
article (PDF)