Thursday 27
Network optimization and telecom applications
Yann Hermans
› 11:00 - 11:30 (30min)
› Bât. B - TD 32
Column generation and Benders' decomposition to maximize the lifetime in connected wireless sensor networks
Fabian Castaño  1, 2, *@  , Nubia Velasco  2  , André Rossi  1  , Marc Sevaux  1@  
1 : Université de Bretagne Sud - Lab-STICC  (UBS/Lab-STICC)  -  Website
Université de Bretagne Sud [UBS], CNRS : UMR6285
BP 92116 - 56321 Lorient cedex -  France
2 : Universidad de los Andes, Departamento de Ingeniería Industrial  (UA)
* : Corresponding author

This research considers the maximum network lifetime problem in wireless sensor networks with connectivity constraints and power allocation decisions. We address target coverage with sensors used for sensing and sending data to a base station through multi-hop communication. Moreover, we consider sensors provided with a limited amount of initial energy able to operate in one of three different modes. A sensor is a source if it is performing monitoring and communicating tasks, a sensor is relay if it is not covering but it is used to help communicate source nodes to the base station.

In order to extend network lifetime, we can activate sequentially subsets of sensors satisfying the coverage, connectivity and sensors battery lifetime constraints. The set of network configurations leading to the optimal solution is not always available neither is practical the enumeration of such covers. Consequently, this research exploits a problem decomposition based on column generation (CG). This strategy divides the problem into two: a Restricted Master Problem (RMP) which is used to allocate the optimal time interval during which a network configuration have to be used to maximize network lifetime, and a Pricing Subproblem (PS) used to identify profitable network configurations that are added iteratively to increase lifetime. A Benders' decomposition approach is proposed to tackle the pricing subproblem and guarantee the optimal solution for MP. Moreover, in order to approach a near optimal solution for the problem in low CPU time, the CG framework is levered by an efficient evolutionary algorithm enhanced with local search. Experimental results indicate that Benders' decomposition largely outperforms the ILP to solve PS.


Online user: 2