Premium
Column generation algorithm for sensor coverage scheduling under bandwidth constraints
Author(s) -
Rossi André,
Singh Alok,
Sevaux Marc
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20466
Subject(s) - column generation , computer science , wireless sensor network , scheduling (production processes) , computation , algorithm , bandwidth (computing) , column (typography) , heuristic , constraint (computer aided design) , mathematical optimization , computer network , mathematics , artificial intelligence , geometry , frame (networking)
This article addresses three problems that arise in coverage scheduling for wireless sensor networks subject to bandwidth constraints. The first problem focuses on minimizing the total breach under a lifetime constraint, where a breach occurs when some targets are not covered by active sensors. The second problem aims at maximizing the network lifetime under a breach constraint. Finally, the problem of computing the possible trade‐offs between breach and lifetime offered by the sensor network is also addressed. An exact approach based on a column generation algorithm is proposed for solving these problems, and a heuristic is also derived from it and briefly presented. The use of a genetic algorithm within the column generation scheme appears to significantly decrease computation time. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012