Power Efficient Gathering of Correlated Data: Optimization, NP-Completeness and Heuristics

This paper studies the interaction between the communication costs in a sensor network and the structure of the data that it measures. We formulate an optimization problem definition for power efficient data gathering and assess its computational difficulty. In particular, we show that the problem is NP-complete. We propose some scalable, distributed and efficient heuristic algorithms for solving this problem and show by numerical simulations that the power consumption can be significantly improved over direct transmission or the shortest path tree, with up to 40% for highly correlated data. Also, our algorithms provide solutions close to a computationally heavy heuristic which we use as benchmark, simulated annealing, which is provably optimal in the limit.