Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

Optimized Query Routing and Data Gathering in Sensor Networks

View Current Project Information

Alexandra Meliou, Carlos Guestrin1 and Joseph M. Hellerstein

National Science Foundation IIS-0205647

Sensor network deployments are widely used for data-gathering purposes in various applications. The distributed nature of such systems requires the integration of query processing with routing techniques. We show that existing routing techniques are suboptimal, and propose new approaches, building on the work of [1].

In particular, we focus on the problem of minimizing communication costs for answering queries in a sensor network. Each query requires the retrieval of measurements from specific nodes in the network. We show that computing the optimal communication scheme for performing this data-gathering task is NP-hard, and propose approximation algorithms for this problem. We further extend our approach to accommodate link and node failures, and examine how different approaches behave with dynamic changes in the network topology [2].

Seeing that many sensor network applications are based on continuous monitoring, we also extend our schemes to handle continuous queries, i.e., queries that are repeatedly executed over specified time intervals, as opposed to their single-step counterparts, and generalize the optimization problem to take into account the multiple timesteps of queries [3].

A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, and W. Hong, "Model-driven Data Acquisition in Sensor Networks," VLBD, 2004.
A. Meliou, D. Chu, C. Guestrin, J. Hellerstein, and W. Hong, "Data Gathering Tours in Sensor Networks," IPSN, 2006.
A. Meliou, A. Krause, C. Guestrin, and J. Hellerstein, "Nonmyopic Informative Path Planning in Spatio-Temporal Models," AAAI, 2007.

1Carnegie Mellon University