Exact and metaheuristic approaches to extend lifetime and maintain connectivity in wireless sensors networks

Wireless sensor networks involve a large area of real-world contexts, such as national security, military and environmental control applications, traffic monitoring, among others. These applications generally consider the use of a large number of low-cost sensing devices to monitor the activities occurring in a certain set of target locations. One of the most important issue that is considered in this context is maximizing network lifetime, that is the amount of time in which this monitoring activity can be performed by opportunely switching the sensors from active to sleep mode. Indeed, the lifetime of the network can be maximized by individuating subset of sensors (i.e., covers) and switching among them. Two important aspects need to be taken into account among others: (i) coverage: each determined cover has to cover the entire set of targets, and (ii) connectivity: each cover should provide satisfactory network connectivity so that sensors can communicate for data gathering or data fusion (connected covers). In this paper we consider the problem of determining the maximum network lifetime to monitor all the targets by means of connected covers. We analyze the problem and propose an exact approach based on column generation and two heuristic approaches, namely a greedy algorithm and a GRASP algorithm, to solve it. We analyze the performance of the heuristic approaches by comparing the obtained solutions with those provided by the exact approach when available. Our preliminary experimental results show the proposed solution algorithms to be promising in terms of tradeoff between quality of solutions and computational effort. © 2011 Springer-Verlag