用改进的列生成算法优化异构WSN生命周期

Optimization of Heterogeneous WSNs Lifetime with the Modified Column Production Algorithm

研究了无线传感器网络(WSN)中有路由需求的静止目标实时覆盖问题,重点解决在保持对不同种类、不同需求的目标覆盖情况下,如何通过对路由的调度最优化网络的生命周期.在对问题进行数学建模后,提出改进的列生成算法,它把基于列生成的算法与可取得较好初始可行基加快收敛速度的随机选择算法结合起来,并且改进算法终止条件进一步加速收敛,进而求得最优解.实验探究了网络参数(如初始可行基、通讯半径等)对网络寿命的影响,验证了算法的有效性,该算法可对建立实际的系统提供指导.

The paper studies the real-time stationary target coverage problem with routing constraints for heterogeneous wireless sensor networks （WSN ） ,and focus on how to maximize network lifetime by scheduling routing while fulfilling target coverage situation of different types and different requirements .Mathematical modeling on the problem ,the improved column production algorithm is proposed ,which combines the column generation based algorithm and a random selection algorithm who can get better basic feasible set to speed up the convergence speed ,and improved termination conditions for further accelerating convergence , then get the optimal solution . Experimental results reveal the influence of the parameters on network lifetime and show the effectiveness of the algorithm ,which can for establishment of the actual system provide a useful guide .