A column generation based heuristic for sensor placement, activity scheduling and data routing in wireless sensor networks

作者：Turkogullari Yavuz B; Aras Necati^*; Altinel I Kuban; Ersoy Cem

来源：European Journal of Operational Research, 2010, 207(2): 1014-1026.

DOI：10.1016/j.ejor.2010.05.020

• Integer programming
• Column generation
• Sensor networks
• Heuristics

A wireless sensor network is a network consisting of distributed autonomous electronic devices called sensors. In this work, we develop a mixed-integer linear programming model to maximize the network lifetime by optimally determining locations of sensors and sinks, sensor-to-sink data flows, and activity schedules of the deployed sensors subject to coverage, flow conservation, energy consumption and budget constraints. Since solving this model is difficult except for very small instances, we propose a heuristic method which works on a reformulation of the problem. In the first phase of this heuristic, the linear programming relaxation of the reformulation is solved by column generation. The second phase consists of constructing a feasible solution for the original problem using the columns obtained in the first phase. Computational experiments conducted on a set of test instances indicate that both the accuracy and the efficiency of the proposed heuristic is quite promising.

• 出版日期2010-12-1