Integer Programming Formulations for Maximum Lifetime Broadcasting Problems in Wireless Sensor Networks

• 作者: Roberto Montemanni
• 来源期刊: 无线传感网络(英文)
• 学科: 工学
• 关键词: Sensor Networks Mixed INTEGER Linear PROGRAMMING Energy Models TOPOLOGY Optimization
• 年，卷（期）: wxcgwlyw_2010,（12）
• 页码范围: 924-935
• 页数: 12页
• 分类号: TN92

摘要

Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show that it is possible to accommodate realistic models for energy consumption and communication protocols into integer linear programming. We analyze the maximum lifetime broadcasting topology problem and we present realistic models that are also shown to provide efficient and practical solving tools. We present a strategy to substantially speed up the convergence of the solving process of our algorithm. This strategy introduces a practical drawback, however, in the characteristics of the optimal solutions retrieved. A method to overcome this drawback is discussed. Computational experiments are reported.