a-Coverage to Extend Network Lifetime on Wireless Sensor 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. In this scenario, a critical issue is the lifetime of the network, that is, the amount of time in which this monitoring activity can be performed; an obvious constraint on this factor is the limited power of the battery contained in the sensors, both for cost and size reasons. The lifetime of the network can be maximized by individuating covers (sub- sets of sensors that can cover the whole set of targets) and switching among them. This problem is known as the Maximum Network Lifetime Problem. In this paper we consider a variant of it, where we allow each cover to neglect a certain fraction of the targets. We analyze the problem and show that the total network lifetime can be hugely improved by neglecting a very small portion of the targets. An exact approach, based on a Column Generation scheme, is presented and a heuristic solution algorithm is also provided. The proposed solution approaches are tested on a wide set of instances. The experimentation shows the effectiveness of both the proposed problem and solution algorithms in extending network lifetime and improving target coverage time when some regularity conditions are taken into account.