Column generation algorithm for sensor coverage scheduling under bandwidth constraints
- 30 September 2011
- Vol. 60 (3) , 141-154
Abstract
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, 2012Keywords
This publication has 19 references indexed in Scilit:
- Wireless sensor network surveyComputer Networks, 2008
- Models and algorithms for three-stage two-dimensional bin packingEuropean Journal of Operational Research, 2007
- Maximizing system lifetime in wireless sensor networksEuropean Journal of Operational Research, 2007
- A generic view of Dantzig–Wolfe decomposition in mixed integer programmingOperations Research Letters, 2006
- Energy-Efficient Wireless Networks2004
- The design space of wireless sensor networksIEEE Wireless Communications, 2004
- Discharge current steering for battery lifetime optimizationIEEE Transactions on Computers, 2003
- A survey on sensor networksIEEE Communications Magazine, 2002
- Energy-aware wireless microsensor networksIEEE Signal Processing Magazine, 2002
- Exact Solution of Cutting Stock Problems Using Column Generation and Branch‐and‐BoundInternational Transactions in Operational Research, 1998