基于混合鸡群优化算法的WSN节点部署优化

韦修喜,郑宝峰

(广西民族大学 a.人工智能学院;b.电子信息学院,南宁 530006)

无线传感网络(WSN)是由一组轻量级、自主的空间分布节点组成,这些节点相互协调,形成一个感知特定应用任务的通信网络［1］,具有成本低,适应度高等特点.随着科技的不断发展,科学家对于WSN的研究也越来越多,并已经应用到许多领域,如:路径调度目标跟踪、灾难预警和可穿戴设备［2］等.其中WSN的覆盖率问题是关键问题也是难点之一,覆盖率的大小反映了WSN网络的性能以及效率的好坏.在传统WSN网络中,传感器的部署位置大多是采用随机抛撒进行决定的,通过这种方法部署的网络容易出现节点分布不均的问题,使得一部分空间内的节点密度过高,从而导致网络的覆盖率降低,传感速度和效率变差.而解决这一问题就需要对节点部署方法进行优化.

随着群智能优化算法的出现,如:教与学优化算法(Teaching-learning-based Optimization,TLBO)［3］,麻雀搜索算法(Sparrow Search Algorithm,SSA)［4］,旗鱼优化算法(Sail Fish Optimizer,SFO)［5］等.近年来,群智能优化算法的研究人员越来越多,由于这类优化算法对于解决寻优问题有着显著的优点,许多国内外学者将群智能优化算法融到WSN节点部署优化中,如:MIAO等［6］等将增强层次结构的灰狼优化算法应用其中,DEEPA等［7］提出了利用Lévy飞行增强的鲸鱼优化算法,并应用到WSN覆盖优化中,并将KNN(K-Nearest Neighbor,KNN)变体整合到WSN中,得到了效率更高、收敛度更好的覆盖优化方法.宋明智等［8］等提出了改进虚拟力-粒子群算法于WSN节点随机部署中的应用,最终实验表明其提出的方法覆盖率较其他优化算法有3%～5%的提升.

虽然,将群智能优化算法运用到WSN节点部署优化中能使其覆盖率有一定的提升,但使用基本算法所得到的结果仍然还有许多不足,故这些算法还有许多可以提升和改进的空间.为了获得更好的WSN网络性能,还需要进一步开拓群智能优化算法的能力,更好地改善WSN节点部署优化问题,提高覆盖率.

鸡群优化算法(Chicken Swarm Optimization,CSO),于2014年由MENG等［9］提出,该算法作为群智能优化算法中的一员,一经提出就备受研究人员及学者关注.目前CSO算法及其改进算法已经应用到了光伏发电［10］,电动汽车充电站规划［11］,电网控制［12］等领域中,但应用到WSN节点部署优化的案例还不是很成熟,因此这一方向具有一定的研究意义.并且,WU等［13］根据随机搜索算法的收敛准则,证明CSO算法满足两个收敛准则,保证了全局收敛性,但也指出了该算法的不足.由于算法的学习方法等原因,导致该算法在收敛速度和收敛精度上有所损失,同时易过早陷入局部最优解,因此CSO算法还有许多提升的空间.故DEB等［14］等将TLBO算法与CSO算法相结合,提出了一种基于教与学算法的鸡群优化算法.LIANG等［15］提出了一种改进CSO算法用于机器人路径寻优,该算法引入了具有Lévy飞行特性的搜索策略和非线性递减策略,寻找到了较好的路径.虽然已经有许多学者和专家对CSO算法的改进和应用进行了大量的研究,但仍有许多开发的空间.

针对上述不足,本文提出了一种混合鸡群优化算法(HCSO)用于WSN节点部署优化的应用.

1 WSN节点部署优化概念与模型

1.1 问题假设

1.2 节点覆盖模型

设监测区域内分布有N个传感器节点,每个节点的感知半径为r,通信半径为R,并且满足2r≤R.设T={t1,t2,…,tN},其中ti为第i个传感器,其位置坐标表示为(xi,yi),若第j个像素点为hj,其位置坐标为(xj,yj).则任意像素点与传感器之间的欧氏距离可用式(1)来表示:

(1)

对于传感器与像素点的感知概率,本文使用二元感知模型进行建模,如式(2)表示:

(2)

其中p(ti,hj)为感知概率,r为传感器的感知半径,若p(ti,hj)为1则表示像素点hj被传感器ti所覆盖,反之则没有被覆盖.

在整个监测范围中,会出现同一个像素点被不同的多个传感器同时感应到的现象,故需要进行联合感知概率的计算.像素点与多个传感器的联合感知概率如式(3)所展示:

(3)

其中p(T,hj)为联合感知概率.最终,覆盖率由式(4)求出:

(4)

其中pcov表示为覆盖率.综上所述,式(4)为HCSO应用到WSN节点部署优化的适应度函数,其目标为提高pcov数值.

2 鸡群优化算法

公鸡为适应度较好的前NR只鸡,根据上述表示方法,公鸡的位置更新公式为:

(5)

(6)

NH代表母鸡的总数,母鸡的适应度适中,母鸡的位置更新公式如下所示:

(7)

(8)

S2=exp(fr2-fi),

(9)

其中,R1和R2均为［0,1］的随机数;r1为与母鸡同一子群的公鸡;r2为另一只随机选取的鸡,且r2≠i,r2≠r1,fr2

适应度最差的个体将被划分为小鸡种群,NC代表种群中小鸡的个数.由于小鸡是种群中的弱势群体,故指定其只能跟随鸡妈妈进行觅食.式(10)展示了这一现象的位置更新公式:

(10)

3 混合鸡群优化算法

3.1 自适应种群分配

CSO算法是一个全局算法,为了加强其后期的局部搜索能力,本文加入了自适应种群分配策略.该策略使前期公鸡种群的粒子个数增加,随着迭代的过程,慢慢减少;而母鸡种群的粒子个数与之相反,是处于慢慢增加的状态.由于每G次迭代CSO会重新规划一次种群秩序,故种群数量的改变也是每G次进行一次.该策略的具体实现方法如式(11)所示:

(11)

其中PR,PH,PC分别代表每一个种群个体数量占鸡群总数量的百分比;t代表当前迭代次数;T代表最大迭代次数;C1,C2用来控制每次迭代种群个体数量百分比增长或减小的速度;PRmin用来控制最终公鸡的数量比;PHmax用来控制母鸡的最终数量比,经实验测试PRmin和PHmax的取值与基本CSO算法的公鸡和母鸡占比数相同时算法的性能最优.

3.2 融合正余弦思想的公鸡位置更新优化

由于CSO算法中公鸡位置更新方法只是基于正态分布的变异方法,当算法的种群多样性变低时,会导致公鸡种群的个体难以跳出局部最优,从而使算法效率变慢,收敛精度变低.本文引入正余弦算法(Sine Cosine Algorithm,SCA)［16］的思想来优化公鸡位置更新公式,具体方法如下:

(12)

(13)

3.3 改进小鸡更新思想

由于CSO算法中,小鸡向其母亲学习,若其母亲陷入局部最优解,小鸡也会随之学习,从而降低算法整体的效率.故本文使小鸡向其双亲学习,并增加突变的可能,学习全局最优个体.引进随机交叉变异思想,改进后的小鸡位置更新公式如下:

(14)

(15)

其中FL∈［0,2］为随机交叉变异的调节参数;Q是［-1,1］的随机数,该参数为学习调控因子,能够同时调控两边的学习力度;ω是一个自适应权重系数;r为［0,1］之间的随机数,控制小鸡是否发生突变.改进后的小鸡更新位置公式使小鸡能够更好地跳出局部最优解,提高适应度,提高算法的效率.

3.4 HCSO节点部署优化流程

步骤1 初始化WSN节点参数和HCSO算法参数,如:节点个数N,感知半径r,粒子个数pop,最大迭代次数等.

步骤2 初始化粒子位置,并使用式(1)～(4)计算覆盖率.

步骤3 判断mod(t,G)是否为1,是则根据式(11)进行种群规划;否则进行步骤4.

步骤4 每个粒子根据其被划分的种群,按照式(7)～(9),式(12)～(15)进行位置更新.

步骤5 算法若到最大迭代次数,则输出优化后的覆盖率等结果;算法若没达到最大迭代次数,跳至第3步进行下一次的迭代.

3.5 复杂度分析

假设种群中总粒子数量为N,公鸡数量为NR,小鸡数量为NC,解空间维度为D,T为最大迭代次数.HCSO引入了自适应种群分配策略,每G次更改一次种群比例,则计算种群百分比的时间复杂度为O(T/G);改进后的公鸡位置更新公式时间复杂度为O(NRDT);修改了小鸡的学习策略,其时间复杂度为O(NCDT),本算法的时间复杂度与原算法相同.

4 仿真实验设计与分析

4.1 基准函数测试

4.1.1实验设计

为了验证HCSO算法的有效性,本文选取了6个具有代表性的基准测试函数,其中函数f1为简单的单峰函数,能够测试算法的收敛速度;函数f2为高维单峰函数,能够测试算法的收敛精度和收敛速度;函数f3是不连续阶梯函数,该函数能够对算法的有效性进行测试;函数f4～f6为3个不同的多峰函数,能够很好地检验算法的全局搜索能力.通过这些函数对HCSO进行测试,并与PSO［17］,CSO,SCA,GWO［18］,ICSO［15］进行结果对照及分析,表1中给出了函数的具体表达式.每个算法在其搜索空间中共有30个粒子进行搜索,单独在6个基准函数上运行30次(每次迭代1 000次)所统计出来其优化结果进行比较.各算法的具体参数设计如表1所示,基准函数表达式如表2所示.

4.1.2测试结果分析

图1、图2为每个算法在f1～f6的函数收敛图和箱线图,附表Ⅰ为每个算法在f1～f6单独运行30次(每次迭代1 000次)所统计出来的数据表.通过3种不同的展示方法可以明显看出,HCSO与原算法相比,收敛精度、收敛速度和跳出局部最优能力都有提高.

表1 算法参数表

表2 基准函数表

在单峰测试函数,图1(a-c)中可以看到虽然本算法没有优化到理想最优值,但相较于其他算法,HCSO的精度都是最好的.GWO虽然能快速地收敛,但都陷入了局部最优.附表Ⅰ中黑体部分为HCSO运算结果,可以看出 PSO和SCA运行速度非常快,但他们的精度却不高,虽然HCSO的运行速度总体比PSO和SCA的运行速度慢,但这是由CSO算法本身的结构造成的,HCSO已经比其原算法有所减少.故本算法对于单峰函数优化起到了比较好的效果.

在多峰函数测试中,可以在箱线图中看出,HCSO是最稳定的,且没有离群值.对于函数f4和f5,HCSO已经找到了理论最优值,并且十分稳定.附表Ⅰ中可以看到其平均值和标准差都是0,说明独立运行的30次每次都能找到局部最优.虽然其他算法也能够找到,但是并不稳定.在图1(d)和图1(f)中可以看到,HCSO几乎在不到100次迭代就可以找到理论最优值,故其收敛速度也很优秀.因此可以看出,HCSO对于多峰函数的优化也很出色,其收敛速度和精度都有大幅度提高,并且稳定性较好.

由图2的算法箱线图可以看出,改进后的HCSO算法对于单峰基准函数和多峰基准函数的优化结果都很稳定,没有较大的离群值和标准差.同时在表3中也可以看到HCSO在每个算法中的标准差都是最小的,因此HCSO的改进也加强了算法的稳定性.

综上所述,本文提出的HCSO算法在测试中表现的性能均高于PSO,CSO,SCA,GWO,ICSO.其收敛速度和收敛精度以及稳定性非常出色,所耗费的时间大部分也与原算法相仿甚至优于原算法,验证了改进的有效性.

4.2 WSN节点部署优化测试

由于函数测试中的算法应用到WSN节点部署优化中其表现的性能较差,无法充分验证HCSO算法在WSN节点部署优化中的性能和效果,因此在此测试中,选择CSO,ICSO算法和文献［19-21］中的算法和模型的覆盖实验进行对比,并且设置的实验模型环境与这些文献中的实验模型环境相同.

设需要覆盖区域是一个S=20 m×20 m的二维平面,内有N=24个传感器节点,其感知半径为r=2.5 m,通讯半径为R=5 m.覆盖率对比曲线如图3(a)所示.HCSO优化节点分布图如图4(a)所示.

表3展示了在本场景中不同算法优化后得到的结果,其中随机抛撒所获得的覆盖率为67.35%,说明这种情况下,传感器无法均匀分布在整个空间中,有许多范围没有被覆盖到.使用CSO算法优化后,覆盖率达到了83.90%,使用ICSO算法优化后,覆盖率达到了87.30%,使用这两种方法比随机抛撒策略覆盖率有了一定的提高,但仍有一定的优化空间.文献［19］的IWOA算法,将覆盖提升到了93.56%,分布较为均匀.HCSO算法改进了公鸡收敛公式,使其能够学习SCA算法的更新方法,使得算法中的优秀个体能够更好地找到最优值.同时改变小鸡学习方式,提高了算法整体粒子质量,使得算法所获得的结果精度更高.从实验中可以看到,HCSO算法的覆盖率达到了94.56%,较随机抛撒提高了27.21个百分点,极大程度地解决了WSN节点分布不均匀问题.

设需要覆盖区域是一个S=200 m×200 m的二维平面,内有N=60个传感器节点,其感知半径为r=20 m,通讯半径为R=40 m.节点优化后的结果如表4,覆盖率对比曲线如图3(b)所示.HCSO优化节点分布图如图4(b)所示.

表3 优化结果对比

表4 200×200优化结果对比

在本场景下,HCSO较CSO和ICSO的覆盖率分别提升了2.96和7.61个百分点,与IWOA所获得的覆盖率相差较小,但HCSO的精度更高.通过图3(b)中的HCSO优化覆盖图可以看出,HCSO算法优化的WSN传感网络已经几乎达到了全覆盖.

设需要覆盖区域是一个S=50 m×50 m的二维平面,内有N=40个传感器节点,其感知半径为r=5 m,通讯半径为R=10 m.节点优化后的结果如表5,覆盖率对比曲线如图3(c)所示.HCSO优化节点分布图如图4(c)所示.

根据表5的数据可以看到,HCSO所获得的覆盖率相比随机抛撒最终提高了22.80个百分点.HCSO算法在迭代200次时,所用时间仅比CSO算法慢0.08 s.所获得的覆盖率比IWOA算法提高了7.27个百分点,且速度要比IWOA算法快得多.与HPSBA相比,虽然覆盖率在迭代200次不如HPSBA所得到的结果好,但HPSBA迭代200次所花费的时间比HCSO算法迭代300次所花费的时间还要多,最终HCSO算法所得到的覆盖率比HPSBA提高了0.07个百分点.HCSO算法使用自适应种群调整策略,较好平衡了算法局部搜索和全局搜索能力,提高了算法的运行速度.迭代次数调整到300次,HCSO算法的运行速度是最快的,同时其获得的覆盖率也是精度最高的.

设需要覆盖区域是一个S=100 m×100 m的二维平面,内有N=50个传感器节点,其感知半径为r=10 m,通讯半径为R=20 m.节点优化后的结果如表6,覆盖率对比曲线如图3(d)所示.HCSO优化节点分布图如图4(d)所示.

在文献［20］中,没有给出ESCA算法的迭代次数和迭代时间的数据.根据覆盖率可以看到,最终HCSO算法所获得的覆盖率比ESCA算法提高了0.68个百分点.在迭代次数为200时,随机抛撒所得到的覆盖率仅达到了79.64%,说明存在大部分节点冗余,节点分布不均匀.使用CSO算法和ICSO算法优化后,覆盖率分别为91.96%和90.55%,起到了一定的优化效果.文献［19］中的IWOA算法优化后,大幅度提高了节点覆盖率,达到了97.92%,但仍比HCSO算法优化后的覆盖率低.HCSO算法优化后覆盖率达到了98.90%,同时HCSO算法的运行速度也是最快的,耗时为66.75 s.迭代次数调整到300后,HCSO算法仍然能够继续寻找更好的分配策略,最终使WSN节点覆盖率达到了99.26%,从图4(b)中也可以看到,节点分布比较均匀,很好地解决了节点冗余问题.

5 结 论

本文针对在传统无线传感网络中,使用随机抛撒策略对传感器节点进行部署,会出现被覆盖区域的节点分布不均匀,覆盖率低等问题.提出了一种混合鸡群优化算法.该算法加入了自适应种群分配策略,提高算法的前后期搜索速度及精度;又利用正余弦算法改进CSO公鸡的更新策略,提高了跳出局部最优解的能力;最后更新小鸡学习策略,使其学习其双亲以及最优个体,还能够交叉突变,提高小鸡群体的质量,从而提高算法整体质量.通过6个基准函数测试,比对了HCSO算法与其他算法所获得的优化结果.表明HCSO算法均取得了比较理想的适应度值,加快了运行速度和收敛速度.最后将HCSO算法应用到WSN节点部署优化中去,首先与原算法比较基本都能提高2～10个百分点,与其他改进算法进行比较,也能够对不同环境下的节点覆盖率进行一定的优化提高,增强了WSN网络的性能.后续将对多目标的CSO算法进行研究,并准备运用到多目标WSN节点部署问题中.

附 录

附表Ⅰ见电子版(DOI:10.16366/j.cnki.1000-2367.2023.05.006).