Exact and Heuristic Methods to Maximize Network Lifetime in Wireless Sensor Networks with Adjustable Sensing Ranges

Wireless sensor networks involve many dierent real-world contexts, such as monitoring and control tasks for traffic, surveillance, military and environmental applications, among others. Usually, these applications consider the use of a large number of low-cost sensing devices to monitor the activities occurring in a certain set of target locations. We want to individuate a set of covers (that is, subsets of sensors that can cover the whole set of targets) and appropriate activation times for each of them in order to maximize the total amount of time in which the monitoring activity can be performed (network lifetime), under the constraint given by the limited power of the battery contained in each sensor. A variant of this problem considers that each sensor can be activated in a certain number of alternative power levels, which determine dierent sensing ranges and power consumptions. We present some heuristic approaches and an exact approach based on the Column Generation technique. An extensive experimental phase proves the advantage in terms of solution quality of using adjustable sensing ranges with respect to the classical single range scheme