Data Gathering with Tunable Compression in Sensor Networks.

We study the problem of constructing a data gathering tree over a wireless sensor network in order to minimize the total energy for compressing and transporting information from a set of source nodes to the sink. This problem is crucial for advanced computation-intensive applications, where traditional "maximum" in-network compression may result in significant computation energy. We investigate a tunable data compression technique that enables effective tradeoffs between the computation and communication costs. We derive the optimal compression strategy for a given data gathering tree and then investigate the performance of different tree structures for networks deployed on a grid topology as well as general graphs. Our analytical results pertaining to the grid topology and simulation results pertaining to the general graphs indicate that the performance of a simple greedy approximation to the Minimal Steiner Tree (MST) provides a constant factor approximation for the grid topology and good average performance on the general graphs. Although theoretically, a more complicated randomized algorithm offers a poly-logarithmic performance bound, the simple greedy approximation of MST is attractive for practical implementation. [ABSTRACT FROM AUTHOR]