Aggregating Correlated Data in Sensor Networks
<-- Return to the list
Date: 01-24-2005
Start Time:
2:00pm
End Time: 3:00pm
Speaker: Ashish Goel
From:
Stanford University
Location: CEPSR Interschool Lab
Hosted by:
Distributed Network Analysis (DNA) Lab
Abstract:
Consider a sensor network of n nodes where each node gathers data from its vicinity and sends it to a central processing agent. If the information is correlated, significant energy savings may be obtained by aggregation information as it travels towards the central sink. In this talk we will prove that for large classes of correlation patterns, there exists a single routing tree which is close to optimum. Hence the problems of designing the right coding scheme and the right routing structure can be decoupled.
We will first consider the case where the amount of information obtained by aggregating data from k sources is f(k), for an arbitrary non-decreasing concave function f. We will present an algorithm for constructing a single tree which is simultaneously an O(log n) approximation for all such functions f.
We will then treat the case of spatially correlated data. We will prove that simple rules can result in a constant factor approximation simultaneously for a large class of spatial correlations.
This represents joint work with Deborah Estrin, Mihaela Enachescu, Ramesh Govindan, and Rajeev Motwani.