Approximately uniform random sampling in sensor networks

Boulat A. Bash, John W. Byers, Jeffrey Considine

Research output: Contribution to conferencePaperpeer-review

22 Scopus citations

Abstract

Recent work in sensor databases has focused extensively on distributed query problems, notably distributed computation of aggregates. Existing methods for computing aggregates broadcast queries to all sensors and use in-network aggregation of responses to minimize messaging costs. In this work, we focus on uniform random sampling across nodes, which can serve both as an alternative building block for aggregation and as an integral component of many other useful randomized algorithms. Prior to our work, the best existing proposals for uniform random sampling of sensors involve contacting all nodes in the network. We propose a practical method which is only approximately uniform, but contacts a number of sensors proportional to the diameter of the network instead of its size. The approximation achieved is tunably close to exact uniform sampling, and only relies on well-known existing primitives, namely geographic routing, distributed computation of Voronoi regions and von Neumann's rejection method. Ultimately our sampling algorithm has the same worst-case asymptotic cost as routing a point-to-point message, and thus it is asymptotically optimal among request/reply-based sampling methods. We provide experimental results demonstrating the effectiveness of our algorithm on both synthetic and real sensor topologies.

Original languageEnglish (US)
Pages32-39
Number of pages8
DOIs
StatePublished - 2004
Externally publishedYes
Event1st International Workshop on Data Management for Sensor Networks, DMSN '04, in Conjunction with VLDB 2004 - Toronto, ON, Canada
Duration: Aug 30 2004Aug 30 2004

Conference

Conference1st International Workshop on Data Management for Sensor Networks, DMSN '04, in Conjunction with VLDB 2004
Country/TerritoryCanada
CityToronto, ON
Period8/30/048/30/04

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Approximately uniform random sampling in sensor networks'. Together they form a unique fingerprint.

Cite this