CS 789 THEORY SEMINAR [home]

Speaker:     Ashish Goel, Stanford
Date:          September 12, 2005
Title:          Sampling, aggregation, and phase transitions in sensor networks

Abstract:

Unlike data networks, the connectivity of sensor networks is largely
dictated by spatial proximity. This makes grids and random geometric
graphs good idealized models for sensor networks, and often results
in simpler algorithms and stronger properties. We will explore three
problems along this general theme.

(a) Multi-scale sampling: We present a scheme whereby any sensor node
(in an N x N grid) can approximately answer moment and quantile
queries about any rectangular region which contains the node. No
communication is required at query-time. During the pre-processing
phase, each node essentially draws K independent samples from all
surrounding rectangular regions while performing only O(K log^2 N)
transmissions.

(b) Aggregating spatially correlated data: We present a simple
randomized process for aggregating spatially correlated data (in an N
x N grid) as it travels to a central collection agent. The
aggregation tree we construct is within a constant factor of the
optimum, regardless of the scale of correlation.

(c) Phase transitions: We show that all monotone graph properties
undergo sharp phase transitions in geometric random graphs as the
radius of communication increases. This settles a conjecture of
Krishnamachari et al and McColm. The phase transitions in geometric
random graphs are both much sharper and much stronger than for
Bernoulli random graphs.

Part (b) represents joint work with Enachescu, Govindan, and Motwani.
Part (c) represents joint work with Rai and Krishnamachari.