Data Gathering Tours in Sensor Networks
by Alexandra Meliou, David Chu, Joseph M. Hellerstein, Carlos Guestrin, Wei Hong
Abstract:
A basic task in sensor networks is to interactively gather data from a subset of the sensor nodes. When data needs to be gathered from a selected set of nodes in the network, existing communication schemes often 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 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.
Citation:
Alexandra Meliou, David Chu, Joseph M. Hellerstein, Carlos Guestrin, and Wei Hong, Data Gathering Tours in Sensor Networks, in Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN), 2006, pp. 43–50.
Bibtex:
@inproceedings{DBLP:conf/ipsn/MeliouCHGH06,
    Abstract = {A basic task in sensor networks is to interactively gather
    data from a subset of the sensor nodes. When data needs to be gathered
    from a selected set of nodes in the network, existing communication
    schemes often 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 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.},
    Author = {Alexandra Meliou and David Chu and Joseph M. Hellerstein and Carlos Guestrin and Wei Hong},
    Booktitle = {Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN)},
    Pages = {43-50},
    Title = {\href{http://people.cs.umass.edu/ameli/papers/IPSN2006.pdf}{Data Gathering Tours in Sensor Networks}},
    doi = {10.1145/1127777.1127788},
    Venue = {IPSN},
    address = {Nashville, TN},
    month = {April},
    Year = {2006}
}