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.