Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks |
| |
Authors: | Fabian Castaño Eric Bourreau Nubia Velasco André Rossi Marc Sevaux |
| |
Institution: | 1. Universidad de los Andes, Departamento de Ingeniería Industrial, Bogotá, Colombia;2. Université Montpellier 2, LIRMM UMR 5506 – CNRS, Montpellier, France;3. Université de Bretagne-Sud, Lab-STICC UMR 6285 – CNRS, Lorient, France |
| |
Abstract: | In this paper, we consider the duty scheduling of sensor activities in wireless sensor networks to maximize the lifetime. We address full target coverage problems contemplating sensors used for sensing data and transmit it to the base station through multi-hop communication as well as sensors used only for communication purposes. Subsets of sensors (also called covers) are generated. Those covers are able to satisfy the coverage requirements as well as the connection to the base station. Thus, maximum lifetime can be obtained by identifying the optimal covers and allocate them an operation time. The problem is solved through a column generation approach decomposed in a master problem used to allocate the optimal time interval during which covers are used and in a pricing subproblem used to identify the covers leading to maximum lifetime. Additionally, Branch-and-Cut based on Benders’ decomposition and constraint programming approaches are used to solve the pricing subproblem. The approach is tested on randomly generated instances. The computational results demonstrate the efficiency of the proposed approach to solve the maximum network lifetime problem in wireless sensor networks with up to 500 sensors. |
| |
Keywords: | Integer programming Wireless sensor networks Column generation Constraint programming Benders&rsquo decomposition |
本文献已被 ScienceDirect 等数据库收录! |
|