Column Generation Embedding Carousel Greedy for the Maximum Network Lifetime Problem with Interference Constraints

We aim to maximize the operational time of a network of sensors, which are used to monitor a predefined set of target locations. The classical approach proposed in the literature consists in individuating subsets of sensors (covers) that can individually monitor the targets, and in assigning appropriate activation times to each cover. Indeed, since sensors may belong to multiple covers, it is important to make sure that their overall battery capacities are not violated. We consider additional constraints that prohibit certain sensors to appear in the same cover, since they would interfere with each other. We propose a Column Generation approach, in which the pricing subproblem is solved either exactly or heuristically by means of a recently introduced technique to enhance basic greedy algorithms, known as Carousel Greedy. Our experiments show the effectiveness of this approach.