Distributed graph layout for sensor networks

Craig Gotsman, Yehuda Koren

Research output: Contribution to journalConference articlepeer-review

22 Scopus citations

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 languageEnglish (US)
Pages (from-to)273-284
Number of pages12
JournalLecture Notes in Computer Science
Volume3383
StatePublished - 2004
Externally publishedYes
Event12th International Symposium on Graph Drawing, GD 2004 - New York, NY, United States
Duration: Sep 29 2004Oct 2 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Distributed graph layout for sensor networks'. Together they form a unique fingerprint.

Cite this