Exact distributed Voronoi cell computation in sensor networks

Boulat A. Bash, Peter J. Desnoyers

Research output: Chapter in Book/Report/Conference proceedingConference contribution

64 Scopus citations

Abstract

Distributed computation of Voronoi cells in sensor networks, i.e. computing the locus of points in a sensor field closest to a given sensor, is a key building block that supports a number of applications in both the data and control planes. For example, knowledge of Voronoi cells facilitates efficient methods for computing the piece-wise approximation of a field, whereby each sensor acts as a representative for the set of points in its Voronoi cell; awareness of Voronoi boundaries and Voronoi neighbors is also useful in load balancing and energy conservation. The methods currently advocated for distributed Voronoi computation in sensor networks are heuristic approximations that can introduce significant inaccuracies that are difficult to rigorously quantify; we demonstrate that these methods may err by a factor of 5 or more in some circumstances. We present and prove an exact method which eliminates these inaccuracies, at the cost of increased messaging overhead, but without necessitating contact with the entire network. To our knowledge, this is the first distributed algorithm that computes accurate Voronoi cells without requiring all-to-all communication. We implement it as a TinyOS module and quantitatively analyze its performance.

Original languageEnglish (US)
Title of host publicationIPSN 2007
Subtitle of host publicationProceedings of the Sixth International Symposium on Information Processing in Sensor Networks
Pages236-243
Number of pages8
DOIs
StatePublished - 2007
Externally publishedYes
EventIPSN 2007: 6th International Symposium on Information Processing in Sensor Networks - Cambridge, MA, United States
Duration: Apr 25 2007Apr 27 2007

Publication series

NameIPSN 2007: Proceedings of the Sixth International Symposium on Information Processing in Sensor Networks

Other

OtherIPSN 2007: 6th International Symposium on Information Processing in Sensor Networks
Country/TerritoryUnited States
CityCambridge, MA
Period4/25/074/27/07

Keywords

  • In-network processing and aggregation
  • Sensor networks
  • Voronoi diagrams

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Exact distributed Voronoi cell computation in sensor networks'. Together they form a unique fingerprint.

Cite this