基于自适应非线性因子杂草算法的WSN覆盖优化

付波 黄晓啸 赵熙临 权轶 贺章擎

［收稿日期］2022-03-29

［基金项目］湖北省自然科学基金项目（2020CFB814）

［第一作者］付波（1973-），男，湖北武汉人，工学博士，湖北工业大学教授，研究方向为图像识别与能源优化

［通信作者］黄晓啸（1997-），男，湖北恩施人，湖北工业大学硕士研究生，研究方向为电气工程

［文章编号］1003-4684（2023）02-0007-04

［摘要］无线传感器网络（WSN）的覆盖率与区域内的传感器节点分布密切关联，而现有传感器分布算法存在收敛速度慢、易陷入局部极值等问题。对此，提出了一种基于自适应非线性因子杂草算法（HA-IWO）的传感器节点分布优化方法。首先，在初始阶段，利用Halton序列产生偏差很小的初始点，使种群分布更均匀；其次，在种群扩散階段，将非线性调和因子设置为根据迭代次数自适应产生，以调整搜索步长，解决算法易陷入局部最优的问题。最后，通过4组标准函数测试与WSN覆盖优化仿真对该算法进行验证。仿真实验表明：相比于标准杂草算法，改进后的算法具有收敛速度快、覆盖率高的优点，能有效解决WSN覆盖优化问题。

［关键词］WSN覆盖率；杂草算法；节点分布；Halton序列；非线性调和因子

［中图分类号］TP18；TP212.9  ［文献标识码］A

随着科技的不断进步，无线传感器网络（WSN）的应用范围日趋广泛，尤其在电气、航空、商业、工农业生产、医疗健康等领域有着广泛的应用[1]。WSN是一种分布式传感网络，其末梢是可以感知和检查外部世界的传感器，传感器节点的覆盖率决定WSN的工作效率。

近年来，将智能算法应用于WSN覆盖优化问题得到了广泛关注。文献[2]提出改进灰狼算法优化BP神经网络的无线传感器网络数据融合算法，提高了无线传感器的数据融合精度；文献[3]针对无线传感器节点能源有限导致负载不均衡，提出一种改进萤火虫算法优化模糊C均值的无线传感器网络路由算法；文献[4]将改进的麻雀搜索算法应用于无线传感器节点定位，取得了很好的效果；文献[5]提出改进遗传算法解决了无线传感器网络节点修复不确定性问题。但这些应用于WSN覆盖问题的群智能算法由于本身存在缺陷，导致优化结果不是很理想。

杂草优化算法（Invasive Weed Optimization，IWO）由A.R. Mehrabian和C. Lucas[7]于2006年提出，是一种启发式搜索算法，由于IWO算法简单、易于并行实现，具有全局和局部搜索能力，目前已经广泛应用于许多自然科学与工程领域，如电力市场的纳什均衡问题[6]、电价预估、神经网络、鲁棒控制器参数整定[8]等。同时，针对IWO的收敛速度和寻优策略，涌现许多改进杂草算法。范宏等[9]利用柯西分布对算法进行空间扩散，在计算初始产生更多可行解；顿晓晗等[10]将杂草个体以正态分布改为混合种群多种分布产生子代个体，提高了寻优精度；张华强等[11]将杂草算法与粒子群算法进行结合，改善了算法跳出局部最优的能力；王子豪等[12]改变了传统杂草算法的适应度计算方式，提高了算法的收敛速度。

为进一步提高杂草算法的收敛速度和寻优精度，作者提出了一种基于Halton序列初始化、根据迭代次数自适应产生非线性调和因子的改进杂草算法，仿真实验表明：本文算法不仅有更快的收敛速度，还能跳出局部极值，搜索到质量更好的最优解，能有效提高WSN覆盖率。

1    WSN覆盖优化模型

假设覆盖区域为二维平面A，将A离散成n×n的网格，每个网格的面积设置为1，A中分布着属性相同且位置不变的M个传感器节点。每个节点同时具有通信半径R1和感知半径R2，且2R2=R1。所有传感器节点可以看成是L{l1，l2，l3，…，ln}的集合，li=（xi， yi）， （i=1，2，…，n），zi=（xi， yi）为目标点的位置，则节点到目标点的距离如式（1）所示：

dij=（xi－xj）2+（yi－yj）2（1）

WSN中传感器节点覆盖概率分布为：

P（x，y，l）=1dij≤R2－re，-α1β1λ1α2+β2λ2R2－re

式中：re（0

α1=Re－R2+dij（3）

α2=re+R2－dij（4）

多个传感器共同作用的WSN感知概率：

pcov（Lall）=1－∏li∈Lall（1－P（x，y，l））（5）

式中：Lall为传感器节点集合。

WSN的覆盖率为所有节点覆盖面积与总面积的比值，用公式（6）表示：

Rall=∑n×nj=1Pcov（Lall）n×n（6）

2    杂草算法（IWO）

杂草算法主要步骤如下：

1）种群初始化。由下式随机产生杂草i：

xi=xmin+（xmax－xmin）·rand（0，1）（7）

其中，xi=（xi1，xi2，…，xiD），且i=1， 2， …，P，D为问题的维度，P为种群数量，xmax和xmin分别为xi的极大值和极小值。

2）生长繁殖：杂草按照式（8）产生种子：

weedn=f－fminfmax－fmin·（smax－smin）+smin（8）

式中，f为杂草适应度值，s为杂草个体生成的种子数。子代种子数目与适应度值呈线性关系，计算过程如图1所示。

3）扩散阶段：在IWO算法中，种子按照平均值为0，标准差为б的正态分布，б的变化公式如下：

σ=（itermax－iter）n（itermax）n·（σinit－σfinal）+σfinal（9）

其中，iter为迭代次数，б为标准差，n为非线性调和因子，n=2或3。

4）竞争生存阶段：在种群扩散过程中，如果种群数量达到预设最大种群规模，则按照适应度值高低对杂草和种子进行排序，选取适应度好的前pmax数目个体，淘汰其余个体（图2）。

5）停止准测：重复步骤1）到4），记录每一代种群中适应度最好的个体，到最大迭代次数为止，得到种群的最优解。

3    改进的杂草算法（HA-IWO）

3.1    基于Halton序列的種群初始化

IWO算法在初始阶段会随机生成初始点，初始点分布不均匀易导致算法陷入局部极值，因此初始点的分布选择是提升IWO算法效率的重要环节。低偏差序列能较好地解决分布不均匀的缺陷，提高初始解质量。图3、图4分别是伪随机序列和低偏差序列的空间分布效果。

从图4可以看出，伪随机序列分布的点有聚集和扎堆现象，这种初始点极易让算法陷入局部极值。而低偏差序列的点在空间内呈现均匀分布，因此具有更好的寻优能力。Halton序列属于低偏差序列的一种，由于其定义简单且能生成无穷个样本点，因此被广泛应用。它是一种为数值方法（如蒙特卡洛模拟算法）产生顶点的系列生成算法。虽然这些序列是以确定的方法算出来的，但它们的偏差很小，所以，这些点可以看成是空间内随机分布的点。

3.2    利用非线性因子调整搜索步长

杂草种子按照式（9）分布在父代周围，基本IWO算法中的非线性因子n是一个定值，极大限制了杂草个体的全局寻优能力。将非线性因子设置成根据迭代次数自适应变化，使得迭代前期算法的标准差较大，种子分布在离父代较远的位置，迭代后期算法标准差变小，种子分布在离父代较近的位置，从而实现算法从全局到局部的搜索，避免早熟。非线性因子n的变化如式（10）：

n=2－1+iteritermax0

式中：iter表示当前迭代次数，itermax为最大迭代次数。HA-IWO算法步骤见图5。

4    仿真实验与分析

为验证本文HA-IWO算法在WSN覆盖优化研究中的优势，选用4个国际通用Benchmark函数[13]进行了测试，并选择基本粒子群算法（PSO）、基本杂草算法（IWO）、本文算法（HA-IWO）进行对比分析。本次仿真实验所使用环境为：DELL inspiron 15-5557系列，内存为8 GB，操作系统为Windows 10，编程环境Matlab 2019a。

设置检测区域为100 m×100 m的二维平面，传感器覆盖节点数为20个，节点通信半径为15 m，感知半径为7.5 m。用HA-IWO算法、IWO算法、PSO算法分别对这些节点在区域内进行覆盖优化，三种算法同时迭代300次，重复操作10次，记录下每次迭代得到的最优解。各算法参数：PSO（c1=c2=2， ω=0.6， vmax=5）， IWO（smax=20， smin=0，бini=300，бfinal=0.05）， HA-IWO（smax=20， smin=0， бini=300，бfinal=0.05）。

4.1    算法覆盖率对比

用以上三种算法对WSN覆盖优化仿真。首先，仅用Halton序列对杂草算法进行改进，结果见表1第二列，可以看出，相比于另外两种优化算法，H-IWO算法对WSN的平均覆盖率大大提高了，比IWO算法高出大约2.66%，比PSO算法高出大约9.52%。其次，仅用非线性因子对杂草算法进行改进，见表1第三列，可以看出，A-IWO算法的覆盖率比IWO算法高出3.55%，比PSO算法高出8.18%。最后，用Halton序列和非线性因子同时改进杂草算法，见表1第四列，可以看出，HA-IWO算法的覆盖率比IWO算法高出5.76%，比PSO算法高出11.31%。综上所述，相比于PSO算法和IWO算法，经过Halton序列和非线性因子改进后的HA-IWO算法能有效地提高WSN的覆盖率，体现了该算法的有效性。

另外，三种算法的传感器最终分布如图6所示，不难看出，PSO算法和IWO算法的传感器分布较杂乱，导致覆盖率低下；HA-IWO算法引入了Halton序列，使得传感器分布更加均匀，从而使覆盖率大大提高。

4.2    不同节点数对比试验

传感器节点个数不同，对WSN覆盖率也会有影响。本文记录了传感器节点数为10、15、20个时各算法的覆盖率（表2）。

随着传感器节点数的增加，各算法的覆盖率均有提高，且HA-IWO算法的覆盖率均高于PSO算法和IWO算法。另外分析各算法达到最大覆盖率时的迭代次数可知，HA-IWO达到最大覆盖率时的迭代次数为100次左右，而PSO和IWO在迭代150次以后才达到覆盖率最大，这表明HA-IWO算法的收敛速度更快。3种算法的WSN覆盖率随迭代次数的变化曲线见图7-9。可见，IWO和PSO分别在182次和227次时才开始收敛，而HA-IWO的曲线在50次时就开始收敛，收敛速度明显更快，加强了寻优精度。

4.3    算法的优越性对比

选用4个标准函数分别测试PSO、IWO和HA-IWO（表3），最终结果以最大值0为最优。从表中可以看出，HA-IWO算法得出的函数值均优于前两种算法，说明HA-IWO算法得到的解质量更高，寻优精度更好。

5    结束语

本文针对无线传感器网络节点分布不均匀导致的覆盖率低下的问题，提出了一种基于非线性因子的改进杂草算法（HA-IWO），该算法在种群初始化阶段引入了一种Halton序列，使得初始种群分布更加均匀，提高算法全局寻优的能力；在种群扩散阶段，引入自适应非线性调和因子，使得前期种群的标准差更大，防止算法陷入局部最优。并将改进的杂草算法应用于WSN覆盖优化中。从仿真结果可以看出，相比于粒子群算法和杂草算法，HA-IWO算法能增强杂草在空间的搜索速度，提高求解精度，从而有利于提升WSN的覆盖率。

［参考文献］

［1］M SALEHI. HOSSAIN. Federated learning in unreliable and resource-constrained wireless Networks[J]. IEEE Transactions on Communications，2021：5136-5151.

[2]曹轲，谭冲，刘洪，等.基于改进灰狼算法优化BP神经网络的无线传感器网络数据融合算法[J].中国科学院大学学报，2022，39（02）：232-239.

[3]余修武， 秦晓坤， 刘永. 基于萤火虫算法优化FCM的WSN路由算法[J]. 北京邮电大学学报（自科版）， 2022， 45（02）：50-56.

[4]彭铎， 杨雅文， 高玉蔚，等. 基于多通信半径和麻雀搜索的节点定位算法[J].传感技术学报，2021，34（11）：7.

[5]苟平章，孙现超，毛刚.基于改进遗传算法的覆盖空洞修复优化[J].传感技术学报，2020，33（12）：1800-1807.

[6]MALLAHZADEH A R， ORAIZI H， DAVOODI-RAD Z.Application of the invasive weed optimization technique for antenna configuration[C].∥Proc of Loughborough Antennas and Propagation Conference. Piscataway： IEEE Press， 2008：425-428.

[7]Mehrabian A R， Lucas C. A noveloptimization algorithm inspired from weed colonization[J]. Ecological Informatics， 2006， 1（4）：355-366.

[8]HAJIMRSADEGHI H， GHAZANFARI A， RAHIMI-KIAN A， et al. Cooperative coevolutionary invasive weed optimization andapplication to Nash equilibrium search in electricity markets[C].∥Proc of World Congress on Nature&Biologically Inspired Computing. [S.l.]：IEEE Press， 2009：1532-1535.

[9]FAN H，LIU Z C.Reconfiguration of distribution Network containing distributed power generation based on differential evolution invasive weed algorithm[J]. Renewable Energy，2019，37（04）：545-551.

[10] 顿晓晗，周建中，曾小凡.基于改进杂草算法优化的神经网络模型在径流预报中的应用[J].水电能源科学，2018，36（05）：17-20.

[11] 张华强，陈传训，吕云飞，等.IWO-PSO-SVR算法在甲烷检测中的应用[J].中国环境科学，2020，40（04）：7.

[12] 王子豪，马俊涛，鲁军，等.基于改进杂草入侵算法的阵元失效校正方法[J].计算机仿真，2021，38（10）：222-226.

[13] 艾哈迈迪 M，莫贾拉利 H. 混沌入侵杂草优化算法及其在混沌系统参数估计中的应用[J]．Chaos Solitons & Fractals the Interdisciplinary Journal of Nonlinear Science & Nonequilibrium & Complex Phenomena， 2012， 45（s9-10）：1108-1120.

WSN Coverage Optimization by AdaptiveNonlinear Factor based Weed Algorithm

FU Bo， HUANG Xiaoxiao， ZHAO Xilin， QUANG Yi， HE Zhangqing

（School of Electrical and Electronic Engineering， Hubei Univ. of Tech.， Wuhan 430068，China）

Abstract： The coverage rate of wireless sensor network （WSN） is closely related to the distribution of sensor nodes in the area， and existing sensor distribution algorithms have problems such as slow convergence speed and easy to fall into local extreme values. In this regard， this paper proposes an optimization method for sensor node distribution based on adaptive nonlinear factor weed algorithm （HA IWO）. First， in the initial stage， the Halton sequence is used to generate initial points with small deviations to make the population distribution more uniform; second， in the population diffusion stage， the nonlinear harmonic factor is set to be adaptively generated according to the number of iterations to adjust the search step size. Solve the problem that the algorithm is easy to fall into the local optimum. Finally， the algorithm is verified by 4 sets of standard function tests and WSN coverage optimization simulation. Simulation experiments show that the algorithm has the advantages of fast convergence speed and high coverage rate， and can effectively solve the WSN coverage optimization problem.

Keywords：WSN coverage rate; Weed algorithm; Node distribution; Halton sequence; Nonlinear harmonic factor

［責任编校： 张岩芳］