改进算术优化算法的无线传感器网络覆盖

贾鹤鸣,孟 彬,魏元昊,力尚龙,文昌盛,陈俊玲

（三明学院信息工程学院,福建三明 365004）

无线传感器网络(wireless sensor networks,WSN)是一种分布式传感网络,通过大量的传感器节点部署形成自组织网络,具有精确度高、灵活性强和可靠性高等特点,实现了数据的采集、处理和传输三种功能.因此被广泛应用于环境探测、智能交通和工业领域.但是随着无线传感器网络的普及,无线传感器网络自身的缺点逐渐开始暴露.而目前急需解决的是覆盖优化问题[1-4].WSN的覆盖优化问题,可以简单描述为:在规定的可监测范围内针对传感器网络可连通情况下的传感器节点部署问题.为提高覆盖率,人们通常在范围内直接撒播大量节点,庞大的数量往往会提高部署密度从而达成目的，但会产生大量冗余节点,降低网络整体性能.而节点数目过少又会产生大量覆盖盲区,降低网络传输效率.因此需要对WSN中传感器节点的部署进行自适应调整,使节点在监测范围内分布的更均匀,节点覆盖率更高.

目前,国内已经有许多针对WSN 节点覆盖的研究,如文献[5]提出一种能量位置融合改进灰狼算法,不仅提高了覆盖率,并且为能量有限的情况下提供了新思路.文献[6]基于水波优化算法,将传感器坐标构建为水波个体,设覆盖率为适应度函数,执行水波的传播、折射和碎波操作,并对节点坐标位置进行优化,以此来提高覆盖率.文献[7]针对三维WSN 节点部署问题,提出一种基于VFA 与AFSA 的融合算法获得最优部署模型,并有效提高了网络覆盖率.

算术优化算法(arithmetic optimization algorithm,AOA)是由学者Laith Abualigah等于2021年提出的一种新型元启发式优化算法[8],其灵感来源于算术中的四则混合运算.该算法利用乘除运算进行全局探索,利用加减运算进行局部开发.目前算术优化算法被应用于求解多类优化问题中,并逐步得到了发展.算术优化算法能够迅速的寻找到全局最优解.针对算术优化算法在解决无线传感器网络覆盖问题上收敛速度慢、开发能力不足的问题,本文融合随机反向学习,引入正弦控制因子,提出了改进的算术优化算法(improved arithmetic optimization algorithm,IAOA),该算法通过改进的数学函数加速器使算法前期探索阶段尽可能的部署监测范围,后期开发阶段遍历所有点,期间通过随机反向学习避免种群中个体错过寻优路径上的有效解,最终提高算法的搜索能力.相比算术优化算法和其他优化算法,该算法具备较快的收敛速度及较高的收敛精度.

1 传感器网络节点覆盖模型

参考文献[2]建立一个监测范围为S=L×L的二维正方形平面,并在该监测范围内随机播撒N个传感器节点,分别定义为C={C1,C2,…,CN},每个节点的位置Ci的坐标为(xi,yi),i=1,2,…,N,所有节点具有相同的通信半径R和感知半径r.传感器节点的感知范围均为以点(xi,yi)为中心,以r为半径的圆形区域.将该监测范围离散为m×n个像素点,定义为zj(xj,yj),j=1,2,…,m×n.计算像素点zj与任一节点Ci之间的欧式距离,记为d,如式（1）所示.

若d≤r,说明该像素点zj已被传感器节点Ci覆盖,反之则未被覆盖.像素点zj被传感器节点Ci感应到的概率如式（2）所示.

其中:Pcov(Ci,zj)为感知概率;r为传感器节点的感知半径.

在监测范围内,任一像素点zj可同时被多个节点Ci所感应,定义zj的联合感知概率为:

其中:P(C,zj)为联合感知概率;N为范围内节点总数目;C为监测目标点的节点集合.

区域覆盖率为传感器节点集合C所覆盖的像素点数占范围总像素点数的比例,定义为COV,其计算公式如下:

2 算术优化算法

算术优化算法是一种根据运算符的不同特性实现全局寻优的元启发式优化算法,通过数学函数加速器选择优化策略,即利用乘法策略和除法策略进行全局搜索,提高解的分散性;利用加法策略和减法策略进行局部开发,增强算法的寻优能力.具体实现原理如下.

2.1 初始化

算术优化算法通过式（5）与式（6）生成随机数进行种群的初始化。

其中:N为粒子数目;dim为维度；Ub为上界,Lb为下界;Rand为0～1之间的随机数;Position(i,j)是第i个解在第j维空间的位置.

2.2 数学函数加速器MOA

根据MOA的值判断进行全局探索还是局部开发:

其中:r1为0～1之间的随机数;MOA(t)为当前的加速函数值;Min为加速函数的最小值;Max为加速函数最大值,T为最大迭代次数;t为当前迭代次数.当r1＜MOA(t)时,函数将进入全局探索阶段;反之,则进入局部开发阶段.

2.3 全局探索阶段

根据随机数r2决定采用乘法或除法策略,两种策略离散度高,有利于粒子在算法空间内探索,计算公式如下:

其中，r2为0～1的随机数,X(t+1)为下一代粒子的位置,Xb(t)为当前适应度最佳粒子的位置,μ为搜索过程控制系数(此处设为0.499),ε为极小值,MOP为数学优化器概率,其计算公式如下:

式中:MOP(t)为当前数学优化器概率;α为迭代敏感系数,α值越高迭代次数对MOP(t)影响越大.

2.4 局部开发阶段

算术优化算法通过加法策略和减法策略进行局部开发,两种策略均具有显著的低分散性,可以容易地接近目标,有利于算法更快寻找最优解.其计算公式如下:

其中:r3为0～1之间的随机数.

3 改进算术优化算法

算术优化算法由线性关系的MOA 控制探索与开发阶段,而算法为非线性变化,导致算法探索与开发不平衡.为解决该问题,本文引入正弦控制因子对MOA 进行改进,以此平衡算法探索与开发的能力.针对迭代后期种群多样性下降、搜索能力减弱的问题,引入了随机反向学习策略以帮助算法增加种群多样性,提高搜索能力.

3.1 引入正弦控制因子对MOA(数学函数加速器)的改进

MOA 的取值影响着算法探索与开发之间的平衡,针对原算法全局探索与局部开发能力不平衡的现象,本文引入正弦控制因子对MOA 进行改进.原算法中MOA 呈线性关系,而算法在进化探索过程中呈非线性变化,线性增长的MOA不能准确贴切实际迭代过程,而正弦控制因子可以将MOA的变化转变为非线性,使其更贴切算法实际迭代过程,故引入正弦控制因子来改进数学函数加速器.改进后的数学函数加速器(sin math optimizer accelerated,SMOA)能够防止算法因早熟而陷入局部最优或因收缩过慢导致收敛精度不足等问题.前期SMOA较大便于节点部署,而后期SMOA迅速减小以便算法迅速收缩,提高搜索精度.其表达式如（11）所示:

其中:MOP_Min 为SMOA 的最小值,MOP_Max 为SMOA 的最大值.选取MOP_Min=0.05、MOP_Max=0.95.

3.2 随机反向学习策略

随机反向学习策略(random opposition-based learning,ROBL)是一种能够提高种群避免局部最优能力[9],增强种群多样性的改进策略,由反向学习策略(opposition-based learning,OBL)改进而来[10].其思想为:在种群寻优过程中,当前解根据原点位置产生一个距离原点长度为随机值的反向解,比较当前解与反向解的适应度值,择优进入下一次迭代.

随机反向学习公式如下:

其中:Value(i,:)是由当前解根据原点位置产生的反向解,而fitness(Position(i,:))代表当前解的适应度值,fitness(Value(i,:))代表反向解的适应度值,对比两解的适应度值,选择适应度值更优的解进入下一次迭代.

4 改进算术优化算法应用于WSN覆盖的实现步骤

综合上述改进策略,本文提出一种改进的算术优化算法,即引入正弦控制因子对数学函数加速器进行改进以避免算法陷入局部最优,并融合随机反向学习策略来增强种群多样性,以此提高算法的寻优性能.对于WSN 覆盖问题，最优个体的适应度值与其他个体的适应度值相差较小，容易陷入局部最优而无法寻找到更优解,而改进的算术优化算法可以完美解决该问题.具体算法实现步骤如下.

步聚1输入节点数N、感知半径r、监测范围边长L等,种群大小U为30、迭代次数为500.

步聚2根据式（5）和（6）初始化种群.

步聚3根据式（11）计算SMOA,同时根据式（9）计算MOP.比较SMOA 与r1的大小,若SMOA＜r1则进入局部开发阶段并根据式（8）更新位置,否则进入全局探索阶段根据公式（10）更新位置.

步聚4以覆盖率COV为目标函数，根据式（4）计算种群适应度.

步聚5通过随机反向学习式（12）生成反向解Value.

步聚6根据式（4）计算Value的适应度.

步聚7根据式（13）比较适应度值,保留较优解..

步聚8判断是否达到当前迭代次数是否等于目标迭代次数,如果达到目标迭代次数则输出最优分布并结束循环,否则回到步聚3.

IAOA求解WSN部署优化流程图，如图1所示.

图1 IAOA的WSN部署优化流程图Fig.1 WSN deployment optimization flow chart of IAOA

5 仿真实验结果与分析

5.1 实验环境设置

为了验证改进的算术优化算法应用于WSN 覆盖优化的性能,均在主频为2.50 GHz 的11th Gen Intel(R)Core(TM)i7-11700 处理器,16 GB 内存,操作系统为64 位Windows11 的电脑上使用MATLAB2021a 进行仿真实验.

5.2 实验结果

5.2.1 与原始AOA对比

为了比较原始算术优化算法与改进后算术优化算法的性能差异,本实验设置了3 组实验参数,具体信息见表1.其他参数设置:种群大小U为30,迭代次数T为500.图2 为根据表1 数据执行后得到的迭代曲线及节点分布情况,表2为算法覆盖率结果对比.

表1 实验分组及部分参数设置Tab.1 Experimental grouping and some parameter settings

由图2可知,相较于原始算法,改进后的算术优化算法明显能够跳出局部最优.由表2所示,在全局寻优能力上,相比原始算法,改进后算法的覆盖率在各种环境下均得到了提高.为了更直观的比较两种算法对监测范围的部署情况,图2展示了传感器节点分布情况.由图2所示,IAOA在WSN覆盖问题上明显优于AOA.

图2 不同组别的IAOA算法和AOA算法结果对比Fig.2 Comparison of the results of IAOA algorithm and AOA algorithm in different groups

表2 AOA算法与IAOA算法覆盖率对比Tab.2 AOA vs IAOA coverage

5.2.2 IAOA与其他优化算法对比

设监测范围为100 m×100 m 的二维正方形平面,传感器节点数N=50,感知半径r=10 m,通信半径R=15 m,种群大小U为30,迭代次数T为500.本次实验选取了原始的AOA、改进的粒子群优化算法(binary particle swarm optimization,BPSO)[11]、改进的鲸鱼优化算法(improved whale optimization algorithm,IWOA)[12]以及改进的灰狼优化算法(improved grey wolf optimizer,IGWO)[13]作为对比算法.图3为覆盖优化时的迭代曲线及节点分布,表3为算法覆盖结果对比.

由图3所示,改进后的算术优化算法性能明显优于原始算法及文献[8-10]中所提出的优化算法.由表3看出,改进后的算术优化算法与对比算法相比,覆盖率分别提升了14.96%,6.82%,4.12%和15.82%.各算法的节点位置分布情况如图3 示,可以看出IAOA 的覆盖效果最好.通过以上实验有效证明了IAOA 对于WSN覆盖问题的有效性和实用性.

图3 各算法节点分布及迭代曲线Fig.3 Node distribution and iteration curves of each algorithm

表3 不同算法的覆盖率结果对比Tab.3 Comparison of coverage results of different algorithms

6 结语

针对实现无线传感器网络覆盖率最大化的目标,从无线传感器网络的视角,构建0-1 节点覆盖模型并通过对监测范围内的节点部署,利用改进后的算术优化算法寻找最优位置,使WSN 尽可能达到全覆盖.本文提出的改进算术优化算法,是在原始算法的基础上加入随机反向学习策略并针对数学函数加速器引入正弦控制因子,使算法更容易跳出局部最优,并且增强了算法的开发能力.仿真实验表明,在与其他4 个算法测试条件相同的情况下,IAOA的适应性更强,不仅可以有效提高网络覆盖率,而且可以降低冗余,以此减少节点数目和降低部署成本.