A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints

This paper addresses the maximum network lifetime problem in wireless sensor networks with connectivity and coverage constraints. In this problem, the purpose is to schedule the activity of a set of wireless sensors, keeping them connected while network lifetime is maximized. Two cases are considered. First, the full coverage of the targets is required, and second only a fraction of the targets has to be covered at any instant of time. An exact approach based on column generation and boosted by GRASP and VNS is proposed to address both of these problems. Finally, a multiphase framework combining these two approaches is built by sequentially using these two heuristics at each iteration of the column generation algorithm. The results show that our proposals are able to tackle the problem efficiently and that combining the two heuristic approaches improves the results significantly. (C) 2013 Elsevier Ltd. All rights reserved.