基于鲸鱼优化算法和天牛须搜索的WSNs分簇路由协议*

赵 锋， 高 楠， 张坤钰

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)由大量小型传感器节点构成，网络可以进行采集信息并将采集的信息发送给检测人[1,2]。由于传感器常常布设在比较复杂的环境中，因此,很难对节点的能量进行补充，高效使用每个节点的有限能量并延长生命周期成为研究的重点[3]。分簇协议中基站选择合适的数量传感器节点作为簇首，其他节点加入簇首形成簇，簇接收并融合簇内成员节点发送的信息，导致簇首节点的任务过重，加大了能量的损耗，因此，为了尽可能降低簇首能耗，应合理选取簇首位置，避免与基站的距离过大[4]。

LEACH[5]协议作为最早的分簇路由协议之一，它通过设定阈值，周期性更换簇头来平衡网络能耗。但选择的簇首过于随机，易使得能量损耗过多的节点担任簇首，同时也可能会出现的网络簇首数目过少和簇首与基站太远等情况。Kuila P等人提出一种基于的能量感知分簇优化算法(PSO-C)[6]，该算法中考虑了簇首能量以及簇首与簇内成员距离，并利用粒子群优化(particle swarm optimization,PSO)算法进行迭代，选出最优簇首集。Zhao Y等人[7]提出将监测区域分成多个扇形区域，并对扇形区域进行分层，形成大小不同的簇，减少网络能耗。Bozorgi S M等人[8]将WSNs的监测区域分成4层，依据能量状态和获取状态选取合适的节点担任簇首，提出一种基于能量非均匀多跳的分簇路由算法,即NEEC(new energy-efficient clustering wireless sensor network protocol)。以上对于节点入簇时均没有同时考虑簇首和节点各自能量、簇首与节点距离、簇首和基站距离这三个因素对网络成簇是否合理的影响。而在节点入簇阶段，设计了一种基于簇首与节点两者的能量和距离以及簇首与基站距离的入簇选择函数，使得普通节点选择加入簇首更加合理。对于WSNs中簇首选取采用鲸鱼优化算法(WOA)，WOA相比其他算法所需的参数少，具有简单易实现，收敛精度高等优点，但WOA存在收敛速度慢，并且采用其他个体向最优个体移动方式，极易陷入局部最优解[9，10]。而新型智能天牛触须搜索(beetle antennae search,BAS)算法[11]，仅需一个个体，运算简单，具有很强的全局收索能力。

本文将WOA和BAS算法很好地结合起来，得到具有良好的收敛性和跳出局部最优解能力的BAS-WOA，同时通过分析网络中通信能耗的影响因子，将簇首选择转化为NP困难问题模型，设计出评价簇首的适应度函数，通过对监测区域分区选取节点进行初始化种群，提高种群多样性，利用BAS-WOA选出较优的簇首集，均衡了传感器节点的能耗，从而延长了网络的生命周期。

1 网络模型

1.1 模型假设

本文在M×M区域内随机部署N个传感器节点和1个基站(BS)，对网络模型作如下假设：1)假设所有普通节点的能量均是有限的，基站的能量不受限；2)节点均是相同类型，具有相同的性能；3)节点一旦部署完成，节点均不可移动；4)节点具有代表自己身份的唯一ID；5)节点可以随时检测周围信息并将信息发给对应的簇首。

1.2 能耗模型

网络的能耗直接影响着网络的生命周期，根据文献[12]的网络通信模型，节点传输bbit的数据，通信距离为d的消息，所需要的发射能耗表达式为

(1)

(2)

式中Eelec为发送和接收1 bit的能量消耗，εfs为自由空间信道模型的信号的信道放大功率，εamp为多路信道衰减模型的能耗放大功率，d0为距离阈值,根据不同距离的d选取不同的放大模型。

节点接收bbit的数据所消耗的能量公式如下

ERX=b×Eelec

(3)

2 BAS-WOA分簇路由协议

2.1 簇首选择

2.1.1 簇首初始化

由于改进的WOA计算相对复杂，故而由能量不受限制的基站完成，以减少节点的能耗，所有节点将自身ID,能量和位置信息发送给基站，基站保留节点信息，进行改进的WOA选择簇首，各节点根据入簇条件形成簇。

WOA种群中的一条鲸鱼代表一种分簇方案，采取随机方式初始化鲸鱼种群，这种方式易使算法陷入局部最优，导致簇头分布不均衡，因此，假设WSNs中有m个簇首，在监测区域随机选取m个节点，组成一条鲸鱼；并进行N次选取，生成N条鲸鱼，即N个初始分簇方案。

2.1.2 适应度函数

由于簇首承担着接收簇内成员信息并融合转发至基站的任务，簇首节点的能耗较大，由能耗模型可以知道簇首的能耗与距基站的距离有关，故在选取簇首时要同时考虑节点的剩余能量和节点到基站的距离，设计适应度值函数F如下

(4)

式中c为系数，Er为剩余节点能量，E0为初始节点能量，di为第i个节点距基站的距离，dmax为节点到基站的最大距离。

2.1.3 BAS-WOA位置更新

WOA收缩包围阶段将当前最优个体作为最接近目标猎物的位置或者目标猎物位置，其他鲸鱼将向最佳位置进行移动，位置更新数学表达式

X(j+2)=X*(j)+A·D

(5)

D=|CX*(j)-X(j)|

(6)

A=2a·r-a

(7)

C=2·r

(8)

式中A,C均为系数变量；X(j+1)为当前更新的位置；X(j)为当前迭代位置；X*(j)为当前迭代最佳位置；j为当前迭代次数。a的值随着迭代的次数增加，线性的从2降到0；r为[0,1]中的一个随机数。

由于WOA中的收缩包围采用当前最优鲸鱼个体作为参考物，其他个体向最优个体移动，这种移动方式，极易使算法陷入局部最优解，而BAS算法具有很强的全局搜索能力，运算量低，故将两种算法结合得到BAS-WOA，在WOA执行收缩包围进行位置更新后，将更新的位置代入BAS算法中再次进行位置更新，然后,比较WOA更新位置的适应度函数值和BAS算法更新位置的适应度函数值，若BAS算法更新位置的适应值函数值较小，则使用BAS算法更新的位置，反之，则继续使用WOA更新的位置，位置更新公式如下

(9)

Blt(j)=X(j+1)+d0*b/2

(10)

Brt(j)=X(j+1)-d0*b/2

(11)

B(j+1)=X(j+1)-δ(j)*

sign(F(Blt(j)-F(Brt(j)))

(12)

(13)

式中 rank(k,1)为随机生成k维变量；d0为天牛触须的感应长度；X(j+1)为执行WOA中收缩包围阶段更新后的位置；Blt(j),Brt(j)分别为天牛左须和右须的位置；B(j+1)为BAS算法更新的位置；其中,sign为符号函数；δ(j)为天牛移动在第j次迭代的步长；F为适应度函数。

在BAS-WOA中没有加入新的循环，与WOA相比并没有提高算法的复杂度。BAS-WOA算法的部分伪代码具体步骤如表1。

表1 BAS-WOA 部分算法执行过程

2.1.4位置映射

在WSNs中随机分布节点的监测区域内，传感节点位置是离散的，而用BAS-WOA进行更新的节点位置并不一定对应着实际监测区域内的节点位置，因此,需要将更新的节点位置映射到实际节点的位置，采用就近原理，通过计算更新节点到实际节点的欧氏距离，选择较小的欧氏距离进行映射。具体公式如下

p(Xp)={Xn|min[d(Xp,Xn)],1≤n≤N}

(14)

式中Xp为迭代后候选簇首的位置；Xn为实际监测区域内的节点位置；d(Xp,Xn)为迭代的候选簇首与实际节点的距离。

2.2 入簇方式

簇头选举成功后，一般采用就近原则，节点选择较近的簇首入簇，这样易出现部分簇内节点过多，部分簇内节点过少的现象，容易造成网络中的节点能耗不均衡。所以,普通节点入选择加入的簇首时，不仅要考虑节点与簇首的距离，还应考虑节点和簇首的各自能量，又因为距离基站越远的簇首转发同等信息量时消耗的能量越高，因此,也要考虑簇首与基站的距离因素，故本文参考库仑定律公式[13]并根据以上三个因素建立入簇选择函数如下

1≤j≤Ncluster

(15)

(16)

式中S(i)E为第i个节点的剩余能量,C(j)E为第j个簇头的剩余能量,E0为初始节点能量,dS(i),C(j)为第i个节点到第j个簇首的距离,Ncluster为簇首数目,Dmax为节点最大通信距离,dmax为节点到基站的最大距离,dC(i),BS第j个簇首到基站的距离。通过计算WSNs中每个节点与各个簇首的入簇选择函数Foption，普通传感器节点加入入簇选择函数较大的簇首。

3 仿真结果

3.1 实验设计

使用MATLAB 2016a软件，并根据表2中给定的参数搭建实验仿真场景，监测区域内随机分布100个传感器节点，根据传感器节点的存活个数、剩余能量和基站接收的数据分组数作为评价性能指标，通过与LEACH、WOA-C[14]、NWOA-CT[15]算法对比，验证本文算法的优越性。

表2 实验参数设置

3.2 不同协议的网络生命周期对比

从图1可以看出,BAS-WOA首个节点死亡轮数大于其他算法协议，LEACH协议、WOA-C协议、NWOA-CT协议和本文协议节点死亡数目达到50 %分别为750,1 200,1 320,1 500轮，故可知本文协议的网络稳定传输数据时间更长，基站获得监测信息更可靠。从图2可以看到,BAS-WOA协议的节点剩余总能量下降坡度更缓，网络每轮的能量消耗更少，节点的能耗更加均衡，极大地延长了网络的生命周期。

图1 存活节点的个数对比

图2 网络剩余总能量对比

3.3 基站接收分组数

通过观察基站接收的分组数，可以知道网络的信息采集能力。图3中BAS-WOA协议基站所获得的分组数比LEACH、WOA-C和NWOA-CT算法协议更加多，可以证明BAS-WOA协议拥有更好的信息采集能力，因为BAS-WOA协议更加理的选择簇首和网络分簇，网络传输稳定时间和生命周期更长，因此,产生的数据分组数也较多。

图3 数据接收量对比

4 结束语

针对WSNs分簇路由协议存在能耗不均衡的问题，本文提出一种WOA和BAS的WSNs分簇路由协议。首先，考虑了节点的能耗以及节点与基站的距离，合理地选择簇首的位置，然后，根据节点和簇首的能量以及之间的距离，并引入簇首与基站距离因素，使得网络成簇更加合理。最后，本文通过与LEACH、WOA-C和NWOA-CT算法协议在网络节点存活个数、网络剩余总能量和基站接收的数据分组数进行性能对比。通过仿真所得数据图像可知：本文提出的算法协议在网络分簇机制、数据传输稳定、能量利用率和信息采集能力方面要优于其他算法协议。