首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号