The Data Collection Problem in Wireless Sensor Networks

Rapid advances in sensing and wireless communication technologies have made attractive the deployment of inexpensive wireless sensor networks for various applications such as ecosystem monitoring and traffic and military surveillance. Efficient use of sensor node energy is a critical management consideration of a wireless sensor network. In this paper, we study the data collection problem in such network in order to improve network longevity. The problem involves selecting a set of representative sensor nodes (R-nodes) that covers all sensor nodes in the network for data collection purposes. We present a formal definition of the problem and develop for the first time, to the best of our knowledge, an integer programming formulation of the problem. Because of the computational complexity of the problem and the need to solve it repeatedly, we propose a heuristic algorithm aiming to maximize the bottleneck residual energy of the selected Rnodes while minimizing the number of the R-nodes with the ultimate goal of maximizing network lifetime. Extensive experimental tests on large wireless sensor networks show that the proposed algorithm significantly outperforms one of the best prior algorithms in key performances metrics, namely the network lifetime, the number of R-nodes and the energy savings.