Extending Lifetime Through Partial Coverage And Roles Allocation in Connectivity-Constrained Sensor Networks

We consider a scenario in which certain target locations are monitored through sensors, which are scattered all over a considered area. A quality-of-service threshold imposes that, at any given time, a predefined percentage of the overall number of targets must be monitored. Furthermore, the activated sensors must be able to transmit the sensed information to a central base station, and the different roles assumed by the sensors (sensing, relay or idle) lead to different energy consumptions. We propose an exact algorithm to solve the problem of maximizing the operational time in this scenario, and test it on a set of benchmark instances.