Alexandra Meliou and David Chiyuan Chu and Carlos Guestrin and Joseph M. Hellerstein and Wei Hong

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-16

February 16, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-16.pdf

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.

---

BibTeX citation:

@techreport{Meliou:EECS-2006-16,
    Author= {Meliou, Alexandra and Chu, David Chiyuan and Guestrin, Carlos and Hellerstein, Joseph M. and Hong, Wei},
    Title= {Data Gathering Tours in Sensor Networks},
    Year= {2006},
    Month= {Feb},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-16.html},
    Number= {UCB/EECS-2006-16},
    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.},
}

EndNote citation:

%0 Report
%A Meliou, Alexandra 
%A Chu, David Chiyuan 
%A Guestrin, Carlos 
%A Hellerstein, Joseph M. 
%A Hong, Wei 
%T Data Gathering Tours in Sensor Networks
%I EECS Department, University of California, Berkeley
%D 2006
%8 February 16
%@ UCB/EECS-2006-16
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-16.html
%F Meliou:EECS-2006-16