The cover scheduling problem arising in wireless sensor networks

Abstract

One critical problem in wireless sensor networks is to assemble the sensors in different covers in order to solve different objectives such as maximum duration of the network lifetime of minimizing the coverage breach. The output of these problems is a set of covers with a duration of usage. Another problem coming just after is how to schedule the covers. Most of the time, this part is left unsolved as the challenges appear less important than generating the covers. Our current work will describe the wireless sensor network cover scheduling problem (WSN- CSP), a non-linear mathematical model, a MILP model and a heuristic (CSH) that solves this problem. To improve the quality of the solutions, we also propose a memetic algorithm (CSMA). Both approaches will be tested on a large set of instances. Moreover, some complexity results and theorical properties are also given in the paper.