摘要：为提高差分进化算法在无线传感器网络中的部署能力，提出了一种改进的差分进化部署算法。算法利用Voronoi图的顶点可以确定盲区位置的特性，用盲区位置替代差分进化算法中变异操作的一个随机向量，引导节点向盲区移动。仿真实验结果表明，算法覆盖效果明显提升，该改进方法为群体智能算法在覆盖部署上的应用提供了新思路。
关键词：无线传感器网络；差分进化；Voronoi图；覆盖部署
DOI：10.11907/rjdk.162754中图分类号：TP312文献标识码：A
文章编号：16727800（2017）004005902
0引言 由于无线传感器网络（Wireless Sensor Networks，WSN）中传感器节点的数量巨大且大多部署于人员不易到达的区域，故可采用无人机随机抛撒的形式将传感器节点部署于监测区域。随机部署的传感器节点，其初始化位置的网络覆盖率和连通性不可靠，节点冗余度高。针对该问题，使用具有移动能力的传感器节点，使其按照一定的部署算法在监测区域自动部署展开，达到一个合适的网络覆盖率后，可以使WSN正常工作完成感知任务。无人机携带可以运行部署算法的嵌入式处理器，传感器节点只负责接收移动位置信息进行移动，以节省传感器节点的制造成本与功耗，从而延长网络生命周期。 WSN的覆w部署问题与群体智能行为中的自组织能力有紧密联系，所以许多学者将群体智能算法应用于该问题。群体智能算法只要给定优化目标，不需依赖优化问题的特征信息，依靠算法本身的随机搜索机制与进化机制即能在解空间内进行搜索，并向全局最优解逼近。群体智能算法的引入拓展了覆盖控制问题的解决思路。文献[1]提出通过增强因子对局部最优粒子进行扰动的分簇粒子群算法；文献[2]在鱼群算法的聚群行为和追尾行为之后加入混沌搜索，提出了一种混沌鱼群算法；文献[3]提出了一种差分蜂群算法，将差分进化算法的变异与交叉操作作为附加成分加入到蜂群算法搜索过程中。在覆盖部署问题中，仅依靠群体智能算法本身的随机搜索机制寻优，存在收敛速度慢、覆盖效率不高等缺陷。本文的优化思路是利用传感器节点的Voronoi图提取覆盖部署问题中的特征信息，引导算法在监测区域的盲区内进行随机搜索，提升差分进化算法的收敛速度和覆盖率。
1问题描述
3Voronoi差分进化算法改进直接将DE算法用于WSN的覆盖部署问题虽然能够产生较优解集，但算法中缺乏引导传感器节点向盲区移动的机制，算法的收敛速度和寻优能力还有待改进。Voronoi图是传感器节点连线构成的Delaunay三角网作垂直平分线得到的网状图，Voronoi图顶点的覆盖情况能够有效确定盲区位置[6]。在改进的Voronoi差分进化算法（Voronoi Differential Evolution， VDE）中，让未覆盖的Voronoi图顶点参与变异操作，引导算法在盲区进行随机搜索。算法步骤如下：步骤1：在监测区域内随机部署N个节点，节点的位置集合为S={s1，s2，…，sN}，si=（xi，yi），并计算初始覆盖率C。步骤2 ：对监测区域进行Voronoi图划分[6]，Voronoi图未覆盖顶点的位置集合为V={vor1，vor2，…，vorN}。步骤3： 根据节点位置集合和Voronoi图未覆盖顶点位置的集合进行变异操作，vi，g=xr0，g+F（xr1，g-vorr2，g），得到所有节点的变异向量种群。步骤4： 根据式（5）对变异向量种群进行交叉操作，得到试验向量种群。步骤5： 根据式（1）～式（3）计算试验向量位置和当前节点位置的覆盖率，根据式（6）进行选择操作，取较高覆盖率的节点位置更新当前节点位置，并相应更新覆盖率，直至所有节点比较结束。步骤6： 重复步骤2～步骤5进行迭代，直至满足停止迭代条件。
4实验仿真为验证VDE的覆盖效果，本文在Matlab平台下进行了3组仿真实验。实验的监测区域为二维平面，节点间可相互通信，传感器节点的感知半径Rs为2.5m。实验中两种算法的变异操作权重均取0.85，交叉概率均取0.5。实验一在该监测区域内随机抛洒30个节点，使用VDE寻优某一次部署过程。图1为随机抛撒的传感器节点的初始化位置，此时覆盖率为76.41%。图2为运行VDE迭代200次后的节点位置，此时覆盖率为99.09%，部署过程中的覆盖率变化如图3所示。
实验二取30个节点在30种随机初始化位置下将VDE与DE进行覆盖部署，两种算法的平均覆盖率变化如图4所示。VDE的最终平均覆盖率为99.29%，DE的最终平均覆盖率为99.14%。实验三取不同节点数量在30种随机初始化位置下将VDE与DE进行覆盖部署，得到的平均覆盖率如表1所示，100%覆盖成功的次数如表2所示。结果表明，VDE的平均覆盖率与100%覆盖监测区域的次数都优于DE。
5结语 本文针对WSN的覆盖部署问题进行了研究，借助Voronoi图提出了VDE算法。VDE算法利用Voronoi图探测到传感器节点周围的盲区位置，用盲区位置替换节点位置参与DE算法的变异操作。在变异操作中有了盲区位置的引导，有效改进了DE算法局部搜索能力不强、收敛速度慢的缺点。下一步工作拟将VDE算法应用于异构WSN的覆盖部署问题中，并把部署算法移植到无人机携带的嵌入式处理器中进行实际部署研究。
参考文献：[1]丁旭，吴晓蓓，黄成.基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究[J].电子学报，2016（4）：967973.
[2]李显，刘明生，李燕，等.基于混沌鱼群改进算法的无线传感网覆盖优化[J].激光杂志，2015（1）：98101.
[3]熊伟丽，刘欣，陈敏芳，等.基于差分蜂群算法的无线传感器网络节点分布优化[J].控制工程，2014（6）：10361040.
[4]宋鑫宏，方伟，熊伟丽.形心导向虚拟力的无线传感器网络部署算法[J].江南大学学报：自然科学版，2015（5）：549555.
[5]PRICE K.Differential evolution：a practical approach to global optimization[M].NewYork：SpringerVerlag，2007：3843.
[6]方伟，宋鑫宏.基于Voronoi图盲区的无线传感器网络覆盖控制部署策略[J].物理学报，2014（22）：132141.（责任编辑：黄健）
基于Voronoi盲区的差分进化WSN部署算法
