Title: Approximately Uniform Random Sampling in Sensor Networks
Authors: Boulat A. Bash, John W. Byers and Jeffrey Considine
Date: July 19, 2004
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.