基于改进灰狼优化算法的无线传感器网络路由协议*

安葳鹏，邵一帆

(河南理工大学计算机科学与技术学院，河南 焦作454003)

无线传感器网络(Wireless Sensor Network，WSN)是由部署在特定监测区域内的大量微型传感器节点构成的自组织网络系统[1]，各节点通过无线通信方式将它们监测到的环境参数或特定数据以单跳或多跳的方式传输给一个或多个数据接收器。 无线传感器网络可应用于多种复杂的环境，通常传感器节点由电池供电，且节点的存储容量有限，处理能力低，在大多数应用环境中能源装置不便于更换。因此对于解决无线传感器网络节点能耗问题，设计低功耗路由协议以降低无线传感器网络整体能耗，延长网络生存时间具有深远意义[2-4]。

为了解决无线传感器网络能耗问题，Lindsey S等人在LEACH 协议[5]的基础上改进并提出了PEGASIS(Power-Efficient Gathering in Sensor Information Systems)协议[6-9]，该协议主要用贪心算法将所有的节点连接成一条单链，并由基站随机选取簇头，使数据从链两端开始传递到簇头，再由簇头将信息发送给基站，虽然该协议在延长节点寿命，平衡节点能耗上起到一定效果，但仍存在很多缺点:易因局部最优而产生长链；单链路传输对通信质量的要求很高，当网络规模增大时，会增加网络时延，不适用于对实时性要求高的环境；一旦有节点死亡，则会导致整个网络瘫痪，鲁棒性差。

针对上述问题，文献[10]提出TTEMR 协议，它将网络构造成双层树型多链路结构，分链和链头链均通过启发式算法优化，并对网络孤立点进行树型结构化处理，降低了数据传递路径长度，但TTEMR协议需要构造树型结构，计算量较大，且数据传输时对于一些节点接收融合数据的能耗过大，易导致其过早死亡。 文献[11]提出PEGASIS-I 协议，将区域进行划分，并在子区域内生成通信路由树，由树根与基站直接通信，有效降低数据传输延迟。 文献[12]提出PEGASIS-C 协议，它也是将区域进行划分，采用多跳路由进行数据通信，既减少数据链长度，又降低出现“长链”的概率；近些年，一些学者将群智能算法[13-17]引入到无线传感器路由协议中，通过群智能算法动态选择簇头，均衡整个网络能耗。 文献[18]提出一种基于改进灰狼优化算法的分簇路由协议，有效延长了网络生存周期，但簇头节点与基站之间的单跳信息传输，导致簇头节点能量消耗过快，从而使整体网络能耗不均。 文献[19]提出一种基于灰狼优化器的集中式分簇路由协议，该协议簇头节点在中继选择阶段并非都能找到下一跳路由节点，因此，同样面临簇头与基站直接通信问题，从而导致网络能耗不均。

为了延长无线传感器网络生存周期，本文在PEGASIS 的基础上采用分区的思想，主要是通过有效区域划分的方式进行局部小范围建链，这种分区建链的方法能避免整体成链产生长链以及在数据传输时由于网络传输效率降低而加大节点能耗；此外，通过改进灰狼优化算法，使得簇头选择更加合理有效，在均衡网络能耗方面更加高效、节能。

1 PEGASIS 分簇路由协议模型与设计

1.1 网络模型

假设一个传感器网络由n个随机部署的传感器节点构成，用Si表示第i个节点，相应的节点集合为{S1，S2，…，Sn}。 该传感器网络具有以下性质:①所有节点具有相同初始特性，随机分布在监测区域且位置不变；②节点之间都可以互相通信，也可以与基站直接进行通信；③基站是固定的，能量没有限制且能量可以满足监测区域能量需要；④节点能量有限且消耗完才会死亡。

1.2 能量模型

改进协议和仿真均采用经典能耗模型。 式(1)ETX(k，d)表示传感器节点发送kbits 到距离为d的邻节点所消耗的能量，由发射电路损耗和功率放大损耗两部分构成，式(2)表示接收kbits 数据的能量损耗，式(3)表示融合kbits 数据消耗的能量。

式中:d为传输距离，εfs和εamp分别是自由空间能量模型系数和衰减空间能量模型系数，Eelec表示发送或接收1 bit 数据消耗的能量，Efs表示融合1 bit 数据消耗的能量。

1.3 改进的PEGASIS 协议设计思路

改进的PEGASIS 协议采用分簇的方式，以固定的基站为圆心，在得到各节点的分布密度信息后在同心圆维度把监测区域划分多个环带，针对监测区域较大的问题，为减少节点远距离传输能耗，在环带分区基础上，将监测区域继续划分为多个扇形区域，形成扇形环带分区，每个子区域内的节点按位置分簇，每个分簇构造一条最优簇内链，在选举簇内链的簇头时，利用改进灰狼优化算法进行最优簇头的选取；在后续迭代中，对权重进行动态更新，以便继续对簇头进行遴选；当各子区域完成建链并选出簇头之后，最终将收集到的信息沿着分区内的簇头链传递给基站。 改进PEGASIS 协议主要由分区、建链、选取簇头、数据传输四个阶段组成。

2 基于改进灰狼优化算法的PEGASIS协议

2.1 灰狼优化算法

灰狼优化算法(Grey Wolf Optimizer，GWO)[20]模拟了灰狼种群的捕食行为，将狼群搜捕猎物的过程类比为寻优过程，达到寻找最优解的目标，是一种典型的群智能优化算法。 已有一些学者将灰狼优化算法应用于无线传感器网络的优化问题中[21-23]，以狼群的位置表示传感器节点的位置，猎物的最佳位置对应最优簇头。

灰狼群体内有严格的等级制度，如图1 所示。这种严格的社会等级划分，能更好地进行狩猎，其狩猎过程可分为搜索包围和狩猎。 在狩猎过程中，狼群的初始位置是随机的，通过不断搜索猎物，获得最终猎物的位置。

图1 狼群等级制度示意图

①包围猎物

捕猎时，灰狼要先得知猎物的位置然后包围猎物，因此需要首先确定灰狼与猎物的距离，对这个过程进行数据建模，得到狼群个体与猎物距离的表达公式:

式中:t代表当前迭代次数，Xp(t)是算法在第t次迭代时猎物位置，X(t＋1)是第t＋1 次迭代时灰狼位置。H和C表示系数因子，其计算公式分别为:

式中:a是收敛因子，在整个迭代过程中从2 线性减小为0；r1和r2取[0，1]范围内的随机值。

②猎杀猎物

灰狼种群中，由于α、β和δ狼具有丰富的经验，能对猎物位置做出更好的判断，所以由它们领导狼群狩猎，此过程可以利用α、β和δ狼三者的位置来确定猎物所在的位置，达到寻优的目的。 在搜索所需猎物的时候，灰狼一般会先识别猎物然后将其包围，在每次迭代的过程中，保留当前最好的三只灰狼，根据它们的位置信息更新其余狼的位置。 当猎物不再移动时，灰狼会通过攻击来捕捉猎物。

由狼群狩猎机制可清晰得出，若要获得猎物的准确位置，狼群先大致了解猎物位置以更新自身初始位置，根据α、β和δ狼的位置估算猎物位置。 而估算猎物位置的前提是需要知道α、β和δ狼与猎物的距离，α、β、δ狼根据它们与猎物的距离由式(6)计算下一刻的位置，第t＋1 次迭代时，猎物的位置如式(7)所示:

式中:Xα(t)、Xβ(t)和Xδ(t)分别是此刻α、β、δ狼的位置；H1、H2和H3，C1、C2和C3的计算方法如式(5)。

2.2 改进灰狼优化算法

当灰狼优化算法中对求解猎物位置的权重因子分配不合理时容易陷入局部最优，为了更好地应用于无线传感器网络，选出最合适的簇头，针对传感器节点特性，对猎物位置权重进行动态更新，提出一种改进的灰狼优化算法。 具体方法为，将无线传感器节点看作灰狼个体，在设计灰狼优化算法适应度函数时，将影响WSN 生命周期的相关参数以不同权重关联起来，找出灰狼群体中适应度值前三的灰狼个体，根据这三个个体的位置对猎物位置进行计算，所对应的猎物位置即为最优簇头的位置。 在算法后续的迭代中，基于动态调整权重更新节点位置。

2.2.1 适应度函数设计

为了使设计的适应度函数更好地适用于无线传感器，结合本文均衡节点能效，延长网络生命周期的目标，对适应度函数的设计主要考虑节点耗能比、同一扇形环带区域中节点间距离以及同一扇形区域中，相邻扇形环带中两簇头距离平方的期望三个因素。

①节点耗能比。 节点剩余能量Eres与初始能量E0的比值，记作Q，Q值越大，说明此节点能量消耗越均衡；

②同一扇形环带区域中节点间距离。 即分别对应α、β、δ狼之间的距离，记作D；

③同一扇形区域中，相邻扇形环带中两簇头距离平方的期望，记作。

基于能量和位置因素，改进算法适应度函数为:

式中:f1、f2、f3是平衡传感器节点耗能比、同一子区域节点间距离以及同一扇区相邻子区域中簇头间距离平方的期望的权重系数。

2.2.2 基于动态权重的灰狼优化算法

在算法开始执行时，由于猎物的位置是由狼群的初始位置决定，初始化过程应充分利用狼群的位置，考虑到节点沿着链路传输数据，故将节点间的相互距离转换为相应的权重作为寻找猎物位置的初始权重因子。 猎物的初始位置为Xp(0)为:

式中:Xα(0)，Xβ(0)，Xδ(0)是α、β、δ狼的初始位置；Dα，β、Dβ，δ、Dδ，α分别表示α、β、δ狼间的距离；ωα、ωβ、ωδ分别表示初始状态下，各灰狼间距离相对于猎物的初始权重。

在算法后续的迭代中，根据下式基于动态调整权重更新权重因子:

t＋1 次迭代后，猎物的位置更新为Xp(t＋1)，其中，Xα(t＋1)，Xβ(t＋1)，Xδ(t＋1)分别是α、β、δ狼在第t＋1 次迭代时的位置。

2.3 基于改进灰狼优化算法的PEGASIS 协议实现

在基于改进灰狼优化算法的PEGASIS 协议实现过程中，首先对网络节点进行初始化，然后开始建链、选择簇头、数据传输等过程，反复迭代更新节点信息，将融合数据传送给基站，直至网络节点全部死亡，具体流程如图2 所示。

图2 改进PEGASIS 协议流程图

2.3.1 网络分区阶段

当网络节点被部署后，基站要确定随机分布在监测区域内的节点的位置，此时，每个节点将自己的ID 信息和到基站的距离发送给基站。 以基站为中心建立直角坐标系，基站将整个监测区域看成以自身为圆心的圆形区域，在得到各节点的分布密度信息后把监测区域划分为多个以基站为圆心的同心圆，每个圆环间距为Δd，各环间距Δd相等，即各环间距是均匀分布的。 此外，如果监测区域比较大，会出现子区域内由于传输距离远导致节点与节点、节点与簇头、簇头与基站之间传输负荷大，易提前耗尽能量而死亡，针对此问题，在环带分区的基础上，以基站为圆心，将监测区域划分扇形子区域，每个扇形子区域相隔的角度为θ(0°＜θ＜90°)，可以将整个圆形区域分成2π/θ个扇形子区域，并按逆时针进行编号。 如图3 所示，形成扇形环带分区，第一环带内的节点，在扇形区域内建链，超出第一环带的节点在扇形环带区域内建链。

图3 扇形环带区域划分图

2.3.2 网络建链阶段

分区结束后，网络开始建链。 由于监测区域已完成分区，因此每个节点都有同区域标记和异区域标记两个标记，各子区域相当于一个簇分别建链，以同处一个扇形区域中的节点为例，子区域内部成链时，设置同区域标记，对每个环带子区域中的节点进行编号，计算每个节点的适应度值，遍历每个节点路径依次成链，形成多条链路，比较各链路长度，选择最短的路径作为初始链路。 子区域间成链时，设置异区域标记，在簇头之间朝着基站方向形成一条簇头链。 节点分布建链示意图如图4 所示。 当各分簇中节点数量小于3 时，由于节点数量过少导致无法建链或者建链无效，即在分区内节点无法成簇，此时将该区域的少量节点定义为孤立节点。 对于基站附近的孤立节点，为了避免延长节点通信路径和数据逆传，可直接与基站进行通信；对于远离基站超出通信距离的孤立节点，向周围发送广播信息，同扇区靠近基站方向且距离该节点最近的带有异区域标记节点做出响应，孤立节点根据响应与之建立通信连接，并将数据转发给该节点。

图4 区域内节点分布建链图

2.3.3 选择簇头阶段

在同一扇区的每个环带子区域中，对于节点数少于3 的子区域，不进行建链和簇头选择，作为孤立节点对数据进行传输；对于节点数不少于3 的子区域，则按照改进的灰狼优化算法，先进行初始化操作，在未达到最大迭代次数前，执行循环，计算每个节点的适应度值，并对每个子区域中节点适应度值进行排序，排名前三的节点视为α、β、δ狼，更新猎物位置，由猎物位置映射到簇头节点位置，获得最优解，簇头选择结束。

通过改进灰狼优化算法选择簇头后，在后续过程，各分簇不是每轮传输过后都对簇头进行更新，经过一段时间后，基站会将各子区域簇头剩余能量Eres与初始能量E0的比值Eres/E0即节点耗能比Q，与设定的节点能量阈值Ethres做比较以决定簇头的更新时间，因为随着网络能耗的增加，簇头节点Eres/E0逐渐变小，故该阈值是可变的，且随网络节点能量消耗逐渐减小，在对其初值设定时大小应适中，若初始阈值过小，表明在簇头剩余能量很少时才开始更换，难以均衡节点能量；若初始阈值过大，簇头节点的更换会比较频繁，这样会加大网络能耗。若Eres/E0不小于Ethres，则不更新簇头节点和能量阈值，继续进行下一轮数据传输；若Eres/E0小于Ethres，此时需要重新选择簇头并更新能量阈值。

2.3.4 数据传输阶段

PEGASIS 协议的核心思想是使链中的每个节点将感知得到的信息沿着长链依次发送至链头，随后链头节点将感知到的信息进行处理、融合转发至基站。与传统的链式协议不同的是，在信息传输的初始阶段，首先每个子区域按照上两节所述内容形成链路并选出簇头，数据分别从链路的两个端节点开始朝着簇头方向传递，簇头接收到簇内所有节点的数据之后，沿着簇头链传向离基站更近的下一子区域的簇头，直至数据全部被基站接收。 如果子区域中出现节点死亡，则需要重新建立链路，然后继续传输数据。 重复以上步骤，直到区域内所有节点能量耗尽。

3 仿真与性能分析

为验证改进协议的性能，与PEGASIS、PEGASIS-C、TTEMR 进行比较，采用MATLAB 进行仿真。 仿真环境设置在半径为150 m 的圆形区域中，监测区域内随机均匀分布100 个节点，基站位于圆心，其坐标为(0，0)。 仿真环境参数设置如表1 所示。

表1 仿真环境参数设置

3.1 参数的选取

对监测区域进行分区时，要考虑环间距Δd和θ对网络生命周期的影响，它们直接影响改进协议在该实验环境下的性能，监测区域中节点分布密度不同，最佳参数值的设置也不同，原则上区域面积越大，分环数应该越多，但并不是越多越好，当环数达到某一最优值后，继续增加区域环数反而会降低网络性能，其原因一方面是由于分环数越多则每个子区域内的节点数越少，不利于簇头的最优选择，其次，随着环数的不断增加，簇头接收、聚合、转发的能耗增量抵消了多跳导致的能耗增量，加速距离基站较近的簇头节点的死亡；同时，跳数过多也会大大增加网络延迟，影响网络通信。 表2 是实验设置的不同Δd和θ值，通过仿真对比确定最佳参数。 图5 是Δd和θ相互映射下取不同值时网络性能对比情况。通过对比图可以得出:当Δd取50，θ取π/3 时，节点存活时间最长，网络性能最佳。

图5 不同参数下节点存活数对比柱状图

表2 参数Δd 和θ 的确定

3.2 链路对比

PEGASIS 采用链状的路由结构，通过贪婪算法计算形成一条包含所有节点的长链，如图6(a)所示。 而改进协议采用分区成链的方法，通过仿真测出该实验环境下的环间距Δd和θ最优值，划分网络区域，在每个子区域中分别建立链路，如图6(d)所示。 图6 (b) 和 图6 (c) 分 别 是TTEMR 和PEGASIS-C 的链路图，相对于PEGASIS，二者基本解决了长链问题，但与改进协议相比较，TTEMR 需要构造树型结构，计算量较大且数据传输时对于一些节点接收融合数据的能耗过大易导致其过早死亡；PEGASIS-C 虽然也进行了分区，但相比改进协议对链路的优化不明显，而且区域内链路存在交叉链，增加了链路平均路径长度，降低了传输效率。

图6 不同协议链路图

3.3 生存周期对比

以监测区域节点向基站发送一次数据为一轮，对比四种协议每轮存活节点数，从图7 仿真结果可以看出，随着轮数的增加，改进协议存活节点的数量比PEGASIS、TTEMR 和PEGASIS-C 更多，而且首节点死亡轮数和最后一个节点死亡轮数都有明显的增加，这是由于改进协议通过多重分区形成了局部小范围成簇，建链时有效避免了长链的产生，降低了节点远距离通信的开销，从而减少了节点能耗，延长了网络整体生存时间。

图7 节点生存周期对比图

对四种协议网络能耗进行对比，从图8 仿真结果可以看出，随着轮数的增加，迭代次数越来越多，改进协议的网络能耗更加均衡，持续的轮次更多，除多重分区形成局部成簇缩短链长的原因，还有一个因素是改进协议在簇头选择时采用改进的灰狼优化算法，遴选出更合适的簇头，降低了簇头节点的能耗，缩小了网络节点间的能耗差异，使能耗整体均衡分布，延长了网络生存周期。

图8 网络剩余总能量对比图

4 结束语

改进PEGASIS 协议在PEGASIS 的基础上通过采用分区的思想进行有效分区，采取局部小范围建链的方式，更好地避免整体成链产生的长链以及在数据传输时由于网络传输效率降低而加大节点的能耗；此外，该协议通过改进灰狼优化算法对簇头进行寻优，在后续迭代过程中对权重进行动态更新，使得簇头选择更加合理有效，在均衡网络能效方面更加高效。 对改进协议的链路、存活节点数量以及网络剩余能量这三项指标进行实验对比，结果显示均优于其他三种协议。 改进PEGASIS 协议在簇内节点建链阶段，只是通过小范围建链的方式宏观减少长链的生成，并没有对此过程进行很好的优化，在今后的工作中将在此方面开展深入研究。