History

Please fill in your query. A complete syntax description you will find on the General Help page.
On the cover scheduling problem in wireless sensor networks. (English)
Pahl, Julia (ed.) et al., Network optimization. 5th international conference, INOC 2011, Hamburg, Germany, June 13‒16, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21526-1/pbk). Lecture Notes in Computer Science 6701, 657-668 (2011).
Summary: Cover scheduling for wireless sensor networks has attracted a lot of attention during the last decade. Many heuristic approaches and exact methods have been proposed for producing covers, i.e. subsets of sensors to be used at the same time. However, the actual schedule of the generated covers has never been explicitly addressed to the best of our knowledge. Though, this problem is of particular relevance when coverage breach is allowed in the aforementioned problems, i.e., when a full coverage of targets at any time is not mandatory. In that case, the objective of the wireless sensor network cover scheduling problem (WSN-CSP) is to schedule the covers so as to minimize the longest period of time during which a target is not covered in the schedule. In this paper, this problem is proved $\mathcal{NP}$-Hard, a MILP formulation is provided along with a greedy heuristic and a genetic algorithm based approach. Computational results show the effectiveness of the last approach.