Maximizing Data Extraction in Energy-Limited Sensor Networks

Abstract

We examine the problem of maximizing data collection from an energy-limited store-and-extract wireless sensor network, which is analogous to the maximum lifetime problem of interest in continuous data-gathering sensor networks. One significant difference is that this problem requires attention to “data-awareness” in addition to “energy-awareness”. We formulate the maximum data extraction problem as a linear program and present a 1 + ω iterative approximation algorithm for it. As a practical distributed implementation we develop a faster greedy heuristic for this problem that uses an exponential metric based on the approximation algorithm. We then show through simulation results that the greedy heuristic incorporating this exponential metric performs near-optimally (within 1 to 10% of optimal, with low overhead) and significantly better than other energy aware routing approaches (developed mainly through intuition), particularly when nodes are heterogeneous in their energy and data availability.

We thank Prof. Ashish Goel for pointing us towards relevant results on the multi-commodity flow problem. We also thank the anonymous reviewers for their insightful comments on our Infocom paper (this article is an extended version of that paper). This work has been supported in part by NSF grants numbered 0435505, 0347621, and 0325875.

Keywords:

• Sensor Networks
• Mathematical Programming/Optimization
• Network Flows

Notes

We thank Prof. Ashish Goel for pointing us towards relevant results on the multi-commodity flow problem. We also thank the anonymous reviewers for their insightful comments on our Infocom paper (this article is an extended version of that paper). This work has been supported in part by NSF grants numbered 0435505, 0347621, and 0325875.

The number of nodes along the shortest S-T path changes from iteration to iteration i.e. it should be k _j . However for notational convenience, we drop the subscript j.

This might need the sink to have an approximate estimate on the number of nodes in the network.