A combinatorial algorithmic approach to energy efficient information collection in wireless sensor networks

In this article, we examine the energy consumption of a set of sensors that transmit correlated information to a base station either directly or in an ad-hoc multihop fashion. Building on a single-hop distributed data rate allocation scheme, we present an efficient approximation algorithm for the NP-hard joint routing and data compression problem whose objective is to maximize the operation lifetime of the sensor networks. We prove that the performance of our algorithm lies within 1/O(log n) of the optimum value where n is the number of sensors. We use simulations to validate our intuitions and provide additional insights on the factors that impact the performance of the approximation scheme. The numerical results show that the proposed scheme performs close to the optimum.