Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Twelfth International Symposium on Graph Drawing, GD 2004
DOI: 10.7155/jgaa.00112
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.
|
Journal Supporters
|