基于改进鲸鱼算法的无线传感器网络能耗优化

郑爱云,张震,刘伟民,郑直

(华北理工大学机械工程学院,河北 唐山 063210)

近年来,绿色低碳的观念深入人心,以物联网(Internet of Things, IOT)助力碳中和,已经成为发展中国家绿色发展的大势所趋,而无线传感器网络(Wireless Sensor Networks, WSNs)作为IOT的关键,被广泛应用于医疗、家居、农业、预测救援等各行各业[1-3]。WSNs经常被部署于复杂环境中,节点能量难以补充,所以能量成为制约其发展的主要因素之一。

启发式算法是1种解决全局优化问题的常用方法,对于优化网络能耗十分有效,例如Tang等[4]提出1种基于模拟退火(Simulated Annealing, SA)算法的高效资源分配策略,结合多目标资源分配模型,用来降低网络能耗;Tabibi等[5]提出1种基于粒子群算法(Particle Swarm Optimization, PSO)的方法来选择网络中的最优交汇点,从而增强了网络的性能。

对于一些新提出的算法,如2015年提出的帝王蝶优化(Monarch Butterfly Optimization, MBO)算法,其结构简单,参数根据蝴蝶在各地活动的月数来确定,在一定程度上优于其他算法中均匀对称的参数。但MBO在某些特定测试中存在收敛速度慢的问题,针对此问题Wang等[6]在MBO中引入自适应交叉算子,在后期提高算法的种群多样性,并通过贪婪策略仅选择更好适应度的个体用来传递给下一代,从而加速算法收敛。

哈里斯鹰(Harris Hawks Optimizer, HHO)算法的提出,受到哈里斯鹰群体捕食行为的启发,其主要分为探索和开发2种阶段,其开发状态根据猎物的状态又分为4种策略进行局部搜索,在多种测试中该算法表现出强大的寻优能力,但是其算法过程十分复杂,存在易于早熟收敛、寻优精度差的缺点。Houssein等[7]利用HHO算法来解决大规模网络下汇聚节点难以确定的问题,从而成功降低网络能耗。

饥饿游戏搜索(Hunger Games Search, HGS)算法,具有结构简单、易于实现、高效特点,但也存在易陷入局部最优解和收敛速度慢的问题。针对此问题,张大明等[8]受到平衡优化器算法的启发,提出1种动态更新策略增强HGS的全局搜索能力,并对其种群实施基于莱维飞行的变异操作,从而增强HGS跳出局部最优解的能力;Yang等[9]针对水下WSNs的能耗问题,提出1种黑猩猩优化和HGS混合算法,用于聚类和构建路由过程,从而成功优化网络能耗。

聚类方法可以有效降低网络能耗[10-12],其将网络划分为多个簇,通过簇首(Cluster Head, CH)来接收成员节点的数据,但随机选取的CH会带有不确定性和不均匀性[13],为了进行合理的聚类得到CH,国内外学者利用聚类方法和启发式算法对WSNs能耗问题进行了相当多的研究。在国内,王宗山等[14]利用人工蜂群和模糊C均值(Fuzzy C-Means, FCM)算法结合的方式对网络进行聚类,从而选出CH,再利用改进蚁群算法得到传输的最佳路由,降低了传输代价;余修武等[15]使用FCM算法来对网络进行聚类,并利用萤火虫算法对其进行优化,根据能量和距离得到CH,从而成功降低网络能耗。而在国外,Heidari等[16]提出了1种基于鲸鱼算法(Whale Optimization Algorithm, WOA)的路由协议,其采用WOA根据能量级别、CH到其他节点的距离和能量来对网络进行聚类,并根据距离和能量准则来选择CH,最终降低传输能耗;Hu等[17]提出了1种基于亲和力和混沌狮子优化算法,首先利用亲和力传播构造聚类拓扑,并根据能量和距离形成初始聚类,其次使用狮子算法寻找最优CH,最后利用混沌映射优化算法的收敛速度,从而延长了网络寿命。

k-means算法作为聚类中的经典的算法,多年以来被学者广泛应用,但是其需要在聚类前确定聚类数目,因此,贾瑞玉等[18]将1种确定初始中心的方法和聚类有效性标准进行结合,从而提出1种确定聚类数的方法;Fahim等[19]提出在k-means开始前,使用1种基于密度的方法获得初始聚类,不再需要确定聚类数。

WOA虽然具有原理简单且参数少的优点,但也存在跳出局部最优解能力差的缺点,于是在WSNs领域,许多学者对其进行改进研究。Xiao等[20]采用1种新的克隆算子和基于离散的二进制编码方式来改进WOA,从而降低了网络能耗;赵锋等[21]利用WOA来选取CH,并利用天牛须搜索算法来避免WOA陷入局部最优解,从而延长了网络寿命。

将k-means算法和WOA用来解决WSNs中的能耗问题,其效果并不理想,所以提出1种新的方法在解决k-means和WOA缺点的同时,对WSNs的能耗问题进行优化是十分有必要的。针对上述问题,本文提出K-SAWOA-PSO方法,该方法可以很好的解决k-means和WOA算法中难以确定的分簇数量和跳出局部最优解能力较差的问题,此方法从以下4个方面进行改进:(1) 通过簇内节点标准阈值和三分簇方法使k-means算法不再需要确定聚类数,进而使网络聚类更加合理;(2) 使用模拟退火策略改进WOA来选择CH,增强WOA跳出局部最优解的能力;(3) 利用k-means中寻找到的聚类中心替换WOA中的超界种群,提高WOA的寻优能力;(4) PSO算法寻找合适位置的辅助节点用来减少CH的传输距离,从而降低能耗。通过对网络生命周期、节点死亡情况和网络剩余能量进行分析,结果表明经K-SAWOA-PSO优化后的网络在减少传输能耗方面具有有效性。

1 资料与方法

1.1 WSN模型

1.1.1 模型设定

模型设定于F×F的范围内,并将N个传感器节点随机部署于该区域,且设置BS的位置在(50,110)处,并且当节点被判定为死亡时,节点剩余能量并不为零,而是处于较低的水平不能正常工作。

现对传感器节点进行如下假设:(1) 同型同构;(2) 唯一身份ID;(3) 不可移动;(4) 能量有限,而基站能量无穷;(5) 单跳传输。

1.1.2 能耗模型

网络通信能量消耗模型表达式如下:

(1)

(2)

式中ETX为数据发送能量消耗,a为数据量,Eelec表示每bit数据接收或发送消耗的能量,εfs为自由空间放大电路参数,εmp为多路径衰减空间放大电路参数,d0为阈值,d为传输距离。

接收数据能量消耗表达如下

ERX=aEelec。

(3)

现对该模型中的能耗计算进行说明,对于普通节点与CH节点之间的能耗计算,要根据两者之间的距离来确定能耗计算公式,能耗公式如式(1)所示;CH节点接收能耗计算如式(3)所示;CH节点发送能耗计算如式(1)所示;CH节点中的数据处理的能耗,使用数据融合Eda进行计算。

1.2 k-means聚类原理

假设样本集合YB={yb1,yb2,yb3, …,yb5}存在5个样本,每个样本存在2个参数特征,ybj={ybj1,ybj2},随机选定h个样本Centre={Centre1,Centre2, …Centreh}作为初始中心点。

dis(ybj,Centrew)=

(4)

(5)

式中Centrew为选定的某一样本;cy为与Centreh相对应的簇内样本。

首先,随机选择初始点为聚类中心;其次,使用公式(4)计算样本点与聚类中心的距离,根据结果形成聚类簇;最后,聚类中心不再改变或到达迭代次数停止,其约束函数如公式(5)所示。

1.3 SA策略原理

SA策略因其可以在概率下使当前最优个体能够接受一个比自己差的解,所以在一定情况下可以跳出局部最优解。本文利用此特性根据SA中的Metropolis准则,计算接受次解的概率,并根据每次迭代更新温度,从而控制产生的概率。

1.4 WOA算法原理

WOA因为具有强大的寻优能力,且参数易于调控,所以受到研究界学者们的广泛关注。

(1) 包围阶段

被包围对象的位置通常为最优解的位置,而此阶段目的就是使鲸鱼个体不断在搜索空间逼近最优解,其位置更新如下所示。

A=|CD*(t)-D(t)|,

(6)

D(t+1)=D*(t)-BA,

(7)

B=2br-b,

(8)

C=2r。

(9)

式中A为D*(t)与当前鲸鱼之间的距离;D(t+1)表示第t+1次迭代的位置;D*(t)为当前最好的位置;t为目前的迭代次数;B和C为系数变量;b随迭代的增加而线性减少从2到0;r为0至1间的随机值。

(2) 狩猎阶段

在此阶段鲸鱼以螺旋的方式逼近被包围对象,其表达式如下所示。

A′=|D*(t)-D(t)|,

(10)

D(t+1)=D*(t)+A′eglcos(2πl)。

(11)

式中A′表示当前鲸鱼到当前最优解的距离;g和l分别为影响螺旋线形状的常数和-1至1之间的随机值。

鲸鱼在以螺旋方式更新位置时也要减少与最优解间的距离,所以以概率的形式来确定是螺旋更新位置还是减少与最优解间的距离,本文此概率为50%,此阶段的数学模型表达如下所示。

D(t+1)=

(12)

式中p为0至1间的随机值。

(3) 搜寻阶段

为了更好的得到最优解,鲸鱼需要扩大搜索范围,所以采用随机选择鲸鱼来指导其他鲸鱼的方式来更新位置。

A=|CDrand(t)-D(t)|,

(13)

D(t+1)=Drand(t)-BA。

(14)

式中Drand(t)为选择到的随机鲸鱼位置。

1.5 PSO算法原理

PSO是1种以鸟群觅食为原型的启发式算法,其中每一个粒子都是1组解,PSO通过控制粒子的飞行来寻找最优解。

粒子的位置和速度更新如下所示。

(15)

(16)

1.6 算法改进

1.6.1 改进k-means

k-means聚类在用于WSNs时,需要提前确定聚类数,而聚类数对于网络能耗十分重要,在聚类数不确定时,可能造成额外的能量消耗。

以二分k-means[22]为启发,将每次聚类由二分簇改为三分簇。这是因为在簇内节点阈值约束下三分簇更加不易分簇,不会使簇内节点过少,而对于单簇内节点数量过多的情况下,对其进行聚类更易接近簇内节点标准阈值。在每次使用k-means聚类时根据簇内节点标准阈值对聚类对象进行三分簇,直至分簇对象不可再分,从而得到聚类结果。

改进k-means不再需要设定固定分类数目,使节点数量合理分配成簇,减少网络能耗,改进k-means流程如图1所示。

由于低能量自适应聚类分层(Low-Energy Adaptive Clustering Hierarchy, LEACH)协议常设置成为CH概率为10%,在100个节点的情况下,理论上CH的数量为10个,则在均衡的角度,簇内节点标准阈值为10。

1.6.2 改进WOA

(1) 改进

采用SA策略来改善WOA跳出局部最优解能力差的问题,并且对于超出界限的种群个体利用改进k-means方法中生成的聚类中心来更新,从而使超界种群恢复为正常种群,并且更利于找到全局最优解,改进WOA的具体流程如图2所示。

图2 改进WOA流程图

SA策略中接受次解的概率表达如式(17)所示,温度如式(18)所示。

(17)

T=T0α。

(18)

式中fch(t)为第t次迭代式(21)的适应度值;T为SA策略中的温度参数;T0为初始温度;α为温度衰减因子,设为0.96。

(2) 选择CH

从减少簇间能量消耗和节点剩余能量的角度出发,将式(19)与式(20)进行归一化处理得到式(21)作为改进WOA选择CH的目标函数。

(19)

(20)

f3=uf1+ (1-u)f2。

(21)

式中hsn为簇内普通节点总数;Dis(SNX,CH)表示簇内非CH节点到CH的距离;ES(x)表示节点剩余能量;EC(ch)为CH的剩余能量;u为[0,1]间的常数。

1.6.3 改进PSO

(1) 惯性权重改进

惯性权重ω可以影响PSO的搜索能力,采用基于正态分布衰减惯性权重[23]来调节ω,表达式如下所示。

(22)

式中ωmax=0.9;ωmin=0.4;θ=0.443 3;It为迭代次数;Itmax为最大迭代次数。

(2) 选择辅助节点

辅助节点(Assistant Nodes, AN)的作用是用来降低CH向BS传输数据时的能耗,在此阶段使用改进PSO来寻找AN,并以AN与CH间的距离和AN与BS之间的距离作为目标函数,其数学表达式如下所示。

(23)

(24)

f6=pf4+ (1 -p)f5。

(25)

式中k为簇的数量;Dis(CHv,ANv)为CH到AN的距离;Dis(ANv,BS)为AN到BS的距离;p为0到1间的常数。

1.7 K-SAWOA-PSO方法

本文所提的K-SAWOA-PSO方法主要由以下3个阶段组成:(1) 使用改进k-means聚类算法,使网络被合理划分,簇内节点数量合理,CH的能量消耗不会过量,保证了CH的工作时长;(2) 根据聚类结果,改进WOA以簇内间隙和节点剩余能量为目标,建立目标函数最终找到CH;(3) 改进PSO基于上述结果将AN到CH间的距离和AN到BS间的距离作为目标函数,从而找到1组合适的AN来减少CH的能量消耗,算法流程如图3所示。

图3 K-SAWOA-PSO流程

本文所提出的K-SAWOA-PSO方法的伪代码如表1所示。

表1 K-SAWOA-PSO伪代码

复杂度是用来衡量算法优劣的标准之一,分为时间复杂度和空间复杂度,对于当前计算机性能的提高,空间复杂度似乎不是那么重要了,所以本文仅对时间复杂度进行分析,本文时间复杂度如表2所示。

表2 算法时间复杂度

表中Nf为节点数;Itmax为PSO最大迭代次数;Ps为PSO的粒子数;Ws为鲸鱼规模;tmax为WOA的最大迭代次数;dw为WOA中鲸鱼的空间维度;Ms为样本个数;dk为维数;tk为迭代次数。

对于本文算法K-SAWOA-PSO的时间复杂度,其主要由改进k-means、改进WOA和改进PSO所决定。改进k-means与k-means的复杂度差别不大,所以改进k-means的复杂度仍为O(Ms·dk·tk·1/10·Nf)。改进PSO的复杂度与惯性权重无关,其复杂度仍为O(Itmax·Ps)。对于改进WOA而言,由于在WOA中加入了SA策略,寻找最优解的能力得到了提升,所以tmax减小,改进WOA的复杂度应小于O(Ws·tmax·dw),K-SAWOA-PSO的复杂度O=O(Ms·dk·tk·1/10·Nf)+O(Itmax·Ps)+O(Ws·tmax·dw)≈O(Ms·dk·tk·1/10·Nf),在此复杂度中除Nf外皆为定量,所以K-SAWOA-PSO的时间复杂度为O(Nf),由复杂度可知K-SAWOA-PSO性能较优。

2 结果与分析

为了验证K-SAWOA-PSO的有效性,决定采用网络生命周期、节点死亡情况、网络剩余能量3个衡量标准进行验证。

2.1 数据传输方式及实验设计

仿真阶段的数据传输方式如下:

如图4所示,在网络建立开始,簇内节点已知簇内CH位置,再将数据传输给CH,此时CH将数据进行聚合,减少冗余,再将数据发送给AN来减少自身到BS的距离,最后AN将数据发送给BS。如果普通节点距离BS较近,可直接发送数据到BS。

图4 数据传输方式

由图5所示,使用改进WOA通过簇内距离和剩余能量因素得到CH,而CH在左上区域分布较为稀疏,在其他部分较为均匀,这是因为在选CH时考虑了节点的剩余能量,并且左上部区域离基站较近,直接传输给BS更为合理。

图5 节点分布图

使用改进PSO得到的AN的分布主要在中上部区域,AN对于BS和CH来说相当于中继节点作用,所以AN的分布主要处于CH与BS之间,这样有利于减少数据传输距离。CH和AN的分布情况体现了使用改进WOA和改进PSO的合理性。

实验设计:

为验证K-SAWOA-PSO的有效性,通过与传感器信息采集系统节能收集(Power-Efficient Gathering in Sensor Information Systems, PEGASIS)、低能量中心自适应聚类分层(Low-Energy Adaptive Clustering Hierarchy-Central, LEACH-C)、LEACH、PSO和WOA进行对比。实验条件如表3所示。

表3 实验条件设定

本文算法中出现的符号说明如表4所示。

表4 符号说明

为了使仿真结果更具有说服性,将本文算法和对比算法进行了多次仿真,多次仿真结果如图6所示。

图6 多次仿真结果

本文计算出多次仿真结果的平均值,并选择最靠近平均值的仿真结果作为最终的对比。

2.2 网络生命周期对比

由图7所示,将K-SAWOA-PSO应用于WSN模型中,可以看到网络在800轮左右开始出现死亡节点,而使用PEGASIS、LEACH-C、LEACH、PSO和WOA的网络模型开始出现死亡节点大约在750、730、660、650和750轮,经K-SAWOA-PSO优化后的网络模型在2000轮左右节点全部死亡,而使用PEGASIS、LEACH-C、LEACH、PSO和WOA的网络模型在大约1 200、900、870、1 300和1 950轮节点全部死亡。

图7 生命周期对比

对图7结果进行分析,由于LEACH算法中CH的选取是随机的,并且没有考虑节点的剩余能量,可能会出现某能量过低的节点成为CH,最终影响到网络生命周期。LEACH-C则在LEACH的基础上考虑了节点的能量因素,其表现要好于LEACH算法。对于PEGASIS算法采用链的方式来传输数据,这样可以缩短传输距离,从而减少能耗,但在构建链的动态过程中,会造成额外的能量消耗。对于PSO算法的表现稍逊色于PEGASIS,这是因为PSO在寻找CH的过程中可能陷入了局部最优解,从而导致CH的选择并非最优解,使得簇内能耗增大,而WOA算法寻优能力要强于PSO,其找到的CH可以很好的减少簇内能耗。本文提出的K-SAWOA-PSO充分考虑了节点剩余能量和簇内间隙,并且使用SA策略来提高算法跳出局部最优解的能力,使用k-means算法中的聚类中心替换超界种群提高算法的寻优能力,所以K-SAWOA-PSO的表现强于其余几种算法。

2.3 节点死亡情况对比

由图8所示,使用K-SAWOA-PSO的网络模型出现1%死亡节点在806轮,25%节点死亡在1 615轮,50%节点死亡在1 933轮,100%节点死亡在1 978轮,而经PEGASIS、LEACH-C、LEACH、PSO和WOA优化过的网络模型开始出现死亡节点分别在757、732、664、653和750轮,25%节点死亡分别在1 162、745、728、1 040和1 475轮,50%节点死亡分别在1 178、748、752、1 054和1 789轮,节点100%死亡分别在1 190、893、877、1 303和1 928轮。

图8 节点死亡情况对比

由上述可知,使用K-SAWOA-PSO优化过的网络模型在死亡节点数1%、25%、50%、100%这4个阶段的表现均优于其余5种算法优化过的模型,这是因为K-SAWOA-PSO采用AN节点缩短了CH的传输距离,降低了CH的能量消耗。K-SAWOA-PSO和WOA使网络出现死亡节点的轮数在此4个阶段呈逐步上升的趋势,并随死亡节点数的增加而逐渐平缓,而使用其余4种算法优化的网络模型在死亡节点出现的轮数方面,上升趋势不明显,更多的是趋于平缓,缓慢上升,表明K-SAWOA-PSO更加高效。

2.4 网络能量消耗对比

由图9所示,经PEGASIS、LEACH-C、LEACH和PSO算法优化过的网络模型,其剩余能量的下降趋势十分迅速,而与K-SAWOA-PSO和WOA对应的网络模型,其剩余能量的下降趋势相对较平缓。

图9 网络能量消耗对比

由上述可知,经K-SAWOA-PSO优化过的网络模型,其能耗得到了有效降低,这是因为在选取CH时综合考虑了簇内距离和节点剩余能量,并且AN的存在对于减少传输能耗也起着重要作用。

3 结论

k-means聚类算法易使无线传感器网络(WSNs)分簇不稳定,导致簇内能耗过大;同时,鲸鱼算法(WOA)易陷入局部最优解,导致簇首(CH)选择不合理而消耗更多的能量。针对上述问题,对k-means聚类和WOA进行改进,以优化WSNs当中的聚类和CH选择,形成K-SAWOA-PSO新方法,并得到以下结论:

(1) 使用改进k-means算法对网络进行聚类,解决了传统k-means中需要设定指定聚类数的问题,从而使网络分簇更加合理。

(2) 应用模拟退火策略来改善WOA跳出局部最优解的能力,使用聚类中心用来更新WOA中的超界个体,可以更加贴近簇间距离,从而增强WOA后期的局部搜索能力,与WOA相比,经K-SAWOA-PSO优化过的网络模型在1%、25%、50%和100%节点死亡的轮数分别提高了7.46%、9.5%、8%和2.6%。

(3) 利用k-means算法中的聚类中心替换WOA中的超界种群,提升WOA算法的寻优能力。

(4) CH和辅助节点的存在可以提高网络寿命,与PEGASIS、LEACH-C、LEACH、PSO和WOA相比,经K-SAWOA-PSO优化过的网络模型,将出现1%节点死亡的迭代轮数分别提高了约6.47%、10.1%、21.3%、7.46%和23.4%,而在25%节点死亡的轮次分别提高了约38.9%、116.7%、121.8%、55.2%和9.5%,由此可见K-SAWOA-PSO对延长网络周期更有效。

仿真结果表明,本文算法和其他算法相比,在延长网络寿命方面具有一定优势,但本文并没有考虑网络延迟问题,对于后续的研究,如何将网络能耗与延迟问题进行共同优化是一个重要的研究方向。