Maximizing Lifetime for a Zone Monitoring Problem Through Reduction to Target Coverage

We consider a scenario in which it is necessary to monitor a geographical region of interest through a network of sensing devices. The region is divided into subregions of regular sizes (zones), such that if a sensor can even partially monitor the zone, the detected information can be considered representative of the entire subregion. The aim is to schedule the sensor active and idle states in order to maximize the lifetime of the network. We take into account two main types of scenarios. In the first one, the whole region is partitioned into zones. In the second one, a predefined number of possibly overlapping zones are randomly placed and oriented inside the region. We discuss how to transform any problem instance into a target coverage one, and solve the problem through a highly competitive column generation-based method.