Select Lab Publications


Data Gathering Tours in Sensor Networks (2006)

By: Alexandra Meliou, David Chu, Carlos Guestrin, Joseph Hellerstein, and Wei Hong

Abstract: A basic task in sensor networks is to interactively gather data from a subset of nodes in the network. When data needs to be gathered from a selected set of nodes in the network the existing communication schemes behave poorly. In this paper we study the algorithmic challenges in efficiently routing a fixed-size packet through a small number of nodes in a sensor network, picking up data as the query is routed. We show that computing the optimal routing scheme to visit a specific set of nodes is NP-complete, but we develop approximation algorithms that produce plans with costs within a constant factor of the optimum. We then enhance the robustness of our initial approach to accommodate the practical issues of limited-sized packets as well as network link and node failures, and examine how different approaches behave with dynamic changes in the network topology. Our theoretical results are validated via an implementation of our algorithms on the TinyOS platform and a controlled simulation study using Matlab and TOSSIM.

Download Information
Alexandra Meliou, David Chu, Carlos Guestrin, Joseph Hellerstein, and Wei Hong (2006). "Data Gathering Tours in Sensor Networks." Fifth International Conference on Information Processing in Sensor Networks (IPSN). pdf   talk        
BibTeX citation

@inproceedings{Meliou+al:ipsn2006tours,
author = {Alexandra Meliou and David Chu and Carlos Guestrin and Joseph Hellerstein and Wei Hong},
title = {Data Gathering Tours in Sensor Networks},
booktitle = {Fifth International Conference on Information Processing in Sensor Networks (IPSN)},
year = {2006},
month = {April},
wwwfilebase = {ipsn2006-meliou-chu-guestrin-hellerstein-hong},
wwwtopic = {Sensor Networks}
}



full list