Prolonging lifetime in wireless sensor networks with interference constraints

In this work, we consider a scenario in which we have to monitor some locations of interest in a geographical area by means of a wireless sensor network. Our aim is to keep the network operational for as long as possible, while preventing certain sensors from being active simultaneously, since they would interfere with one another causing data loss, need for retransmissions and overall affecting the throughput and efficiency of the network. We propose an exact approach based on column generation, as well as a heuristic algorithm to solve its separation problem. Computational tests prove our approach to be effective, and that the introduction of our heuristic in the Column Generation framework allows significant gains in terms of required computational effort.