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.
Original language | English (US) |
---|---|
Pages (from-to) | 327-346 |
Number of pages | 20 |
Journal | Journal of Graph Algorithms and Applications |
Volume | 9 |
Issue number | 3 |
DOIs | |
State | Published - 2005 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science
- Computer Science Applications
- Geometry and Topology
- Computational Theory and Mathematics