一种基于灰狼优化算法和Dijkstra的分簇路由协议*

王 军，丁丕欣，刘鼎坤

（1.沈阳化工大学计算机科学与技术学院，沈阳 110142；2.辽宁省化工过程工业智能化技术重点实验室，沈阳 110142）

0 引言

无线传感器网络（wireless sensor network，WSNs）由许多传感器节点组成［1］，负责收集监测区域的信息并传输给基站（BS）［2］。它是以自组织形式组成的大规模网络，应用领域广泛，如：军事、航天、救灾等［3］。虽然无线传感器网络部署方便、成本低，但存在节点能量有限、网络生命周期短等问题［4］。因此，优化分簇路由算法已成为延长整个网络生命周期的一个研究对象。

针对WSNs在分簇路由中存在问题，HEINZELMA W R 等学者最早提出了LEACH 协议［5］，该协议通过随机数与阈值比较进行簇头选举，簇群内部普通节点单跳传输给簇头，簇头节点将以单跳方式传输给基站，将整个过程分为簇内和簇间传输两个部分。朱素霞等学者基于LEACH 协议进行改进［6］，充分考虑节点能量、节点密度以及与基站距离等因素优化阈值函数，其次通过成本函数选举最优簇头，簇间通信根据距离因素选取单跳或多跳。张慧娟提出禁止拥塞节点担任簇头［7］，考虑节点的剩余能量及离汇聚节点距离选择簇头，利用贪婪启发式Dijkstra算法构建簇头间的最短路径，缓解簇头的能量消耗。MARWAH M A 等采用智能优化算法提高无线传感器网络的能量效率［8］，在簇头选举过程中用金鹰优化算法选举最后簇头，黄色马鞍形山羊算法优化簇头向基站传输的路径，降低数据包传输的能量损耗。富立琪等提出用K-means 聚类算法对整体节点进行分簇［9］，并在每个簇群内部考虑节点能量和邻居节点等因素竞选最优簇首，数据传输采用单跳或多跳将数据包传输到基站。

上述学者提出了不同的分簇路由协议，能有效地降低网络能耗并延长网络寿命，但在协议的设计过程中对簇首规模数，簇首选举的局部与全局的寻优分配，以及数据传阶段的路径选取缺少针对性的研究，对此本文提出一种基于灰狼优化和Dijkstra算法的分簇路由协议（clustered routing protocol based on gray wolf optimization and dijkstra algorithm，CRGWOD）。利用灰狼优化算法的收敛速度快，能很好地平衡局部与全局最优的特点，求解传感器网络节点分布的最优簇首数，在每个簇群内找出能量高、密度均匀，与基站位置合理以及当选簇头频率较低的节点担任簇头节点。簇间路由阶段结合簇头节点能量和距离计算权值函数值，判断权值函数用Dijkstra 算法选取最合理的簇间路由路径。目的解决节点分布热区现象，全面考虑网络寿命延长的问题，提高网络节点能源利用效率。

1 系统模型

1.1 网络结构模型

本文采用的网络结构模型如图1 所示，为精确计算节点间信息，确保基站持续稳定接受数据，节点按照距离自主选择合适的发射功率，以及避免节点遭受恶劣环境等因素影响，网络结构需满足如下要求［10］：

图1 网络结构Fig.1 Network structure

1）传感器节点均匀分布、位置固定不变且具有唯一的ID。

2）基站具有无限的能量，且该网络周围无任何信号干扰。

3）每个传感器都具有相同的属性且位置相对稳定。

4）每个传感器节点发送与接收功率可控。

1.2 能耗模型

本文采用一阶无线通信能耗模型［11］，其分为自由空间模型和多径衰减模型。具体公式如式（1）～式（4）。

其中，ETX为发送abit数据的能耗；Eelec为收发1 bit数据的能耗；εfs为自由空间模型损耗因子；εmp为多径衰减模型能量损耗因子；d为传输距离，ERx为接受abit 数据的能耗；EDA为融合每比特能量消耗；EMx为融合abit 数据的能耗。

2 CRGWOD算法

2.1 最优簇首规模

能耗是评价网络整体性能的其一标准，簇首的数目以及能量损耗对整个网络起着至关重要的作用，本文网络能量消耗分为：普通节点向簇首发送数据，簇首节点接受并融合数据，向中继节点转发数据。则网络能耗一轮消耗能量为：

每个簇内普通节点能耗为：

式中，dtoCH是每个簇内普通节点到簇首的距离。在M×M模型内部署的节点均匀分布，将N个节点平均地分布在K个呈圆状的簇内，则每个簇区域内的密度为ρ，如图2所示。

图2 节点假设分布图及半径、密度公式Fig.2 Node assumption distribution diagram and formulas of radius and density

簇首节点能量消耗为：

整理上述式子，对网络整体能耗Eall最小化，得最优簇首数K与M、N、EELEC、EDA等有关，计算出最佳簇首规模数K：

式中，NCHs表示簇头节点需要中继的次数。

2.2 改进灰狼优化算法

2.2.1 灰狼优化算法（GWO）

在灰狼优化算法中，灰狼呈金字塔形状，分为4个等级：α狼、β狼、δ狼、ω狼［12］。每一只狼都受α 狼的引导，进行位置更新，灰狼狩猎的具体过程为：

式中，Xa（t）是经过t次迭代后猎物的位置向量；X是灰狼个体所在的位置向量；A、C均为系数向量；a为收敛系数，在［2，0］区间内线性递减，r1和r2是介于0～1之间的随机数。

狼群中其他狼的位置将会受α狼、β狼、δ狼所引导：

该算法与分簇路由算法有极大的相似性，其相似关系如表1 所示，将该算法解决应用到簇头选举中的算法流程图如图3所示。

表1 无线传感器网络与灰狼优化相似对应表Table 1 Similar correspondence table between wireless sensor networks and gray wolf optimization

图3 灰狼优化算法解决簇头选举流程图Fig.3 Flowchart of Gray wolf optimization algorithm solving the cluster head election

2.2.2 适应值函数改进

为优化簇头选取来提高整体网络生命周期，在确定最优簇首规模后，根据节点的状态设定适应值函数。簇头节点所承担的数据量大，因此，簇头的选取应具备节点的能量相对高，邻居节点的密度相对大，簇头频率低等特点。下面从节点的能量、节点的密度、节点的位置以及担任簇头的频率4 个方面设计适应度函数。

节点能量水平：即节点的当前剩余能量与节点的初始能量的比值。能量是节点处理数据必然条件，如果当前节点的剩余能量高，比值就高，在相同条件下所能更好地处理数据，就应当选为簇头。

节点的密度级：节点在其感知半径范围内，所具有的邻居节点数量，如果邻居节点越多且距离小于感知半径，周围节点的密度就越高，越有可能承担簇头的责任。

式中，count（）表示返回符合条件的数量；dist（Ni，Nj）表示节点之间的距离；Rs表示节点的感知半径。

节点位置：在簇群内部，簇头节点与每个节点之间的距离平均值，以及簇头节点与基站之间距离的综合考虑因素。距离的平均值可以反映出节点在空间中是否处于簇群内部中心位置，可兼容并降低节点与其通信的能量损耗；在整体网络布局中，簇头与基站的距离短，所需传输的消耗的能量低，一定程度上降低簇头的能耗。

式中，Ncluster代表簇群内节点数量；dist（Ni，BS）代表节点与基站的距离。

簇头频率：一个节点多次担任簇头，必要在下一次选择中降低被选中担任簇头的几率，簇头节点需要处理接受、融合、转发等任务，能量消耗速率大大增加，避免多次担任可提高网络整体的寿命，用Ncount表示当选簇头次数，具体公式如下：

基于节点能量、密度、位置以及簇头频率4个因素，通过权值控制的方式对适应值函数进行改进：

式中，t1，t2，t3，t4为权重因子并对每一部分的权重比例呈递减趋势选取，且满足

对于位置更新策略调整，本文采用文献［13］中所提出的采用适应度值去衡量变化情况，将式（15）中X（t+1）进行更新，具体更新如式（21）和式（22）：

式中F1，F2，F3是改进后的位置权重因子；Fα、Fβ、Fδ是每个簇内的前三优的适应度函数值。根据改进的适应度函数，对每一个灰狼的适应度函数进行计算，选出最终的簇首，其算法流程如表2所示。

表2 改进后选取簇头算法表Table 2 Improved cluster head selection algorithm table

2.3 基于Dijkstra簇间路由

在簇间路由过程中，采用Dijkstra算法进行选择传输路径，本文将距离与能量进行权重分配后，再作为Dijkstra算法的权值进行最短路径选取，从而完成路由设计，获得最合理的传输路径。将簇头节点与基站节点分成两个集合，由基站节点担任Dijkstra算法的初始节点，寻找合适的簇头与基站的传输路径。将簇头节点与权值函数值构建带权图G=（V，W），V代表簇头节点与基站节点的集合，W代表权值函数值。在顶点集合中，需要先将顶点分为两类，引入集合S和集合H，集合S中记录基站节点和最小权值簇头，集合H内记录未出现在最短权值路径中的顶点集合，初始情况下集合S和集合H分别用S｛s0｝、H｛a1，a2，…，ak｝表示，s0表示基站，ai-K表示簇头节点。集合H中的节点若想加入到集合S中需要满足的权值函数如下：

式中，c1、c2为权重影响因子且满足c1+c2=1，dis（t，BS）表示簇头节点与基站的距离，表示当前轮次簇头的平均能量与待加入集合S的簇头能量比重。算法详细流程如下：

Step 1 初始化参数，将基站作为起点S｛s0｝，其他簇头节点记为H｛a1，a2，…，ak｝。

Step 2 在集合H中计算出W值最小的顶点ai，把ai放入集合S中，此时需要更新中继节点，以ai计算与集合H内其余节点的W值，更新W值作为新的权值，如果W值变小就更新，否则，保留原始W值。

Step 3 在更新过程中记录最小的权值路径，当W值不再变化并H集合仍有簇头，则返回Step 1，重新记录新的路径。

Step 4 当集合H内没有簇头节点时，输出最终的最小权值路径，该路径就是簇头在数据传输过程中将数据传输到基站的路径。

3 实验仿真分析

3.1 实验参数设定

为检验本文算法在延长网络寿命方面的仿真效果，在MATLAB R2019a 平台进行算法对比分析，对LEACH 协议、PEGASIS 协议、文献［14］中的ABC算法，以及本文算法在网络系统能量、节点数量变化、1 100～1 500 轮死亡节点数量3 个方面验证本文算法的优化性。拟定100 m×100 m 的实验仿真区域，均匀分布100 个节点，基站位于区域中心，具体参数如表3所示。

表3 实验参数表Table 3 Experimental parameter table

3.2 节点数量变化分析

死亡节点数量体现出网络的整体稳定性，如图4 所示，600 轮之后几种算法出现死亡节点，死亡的节点越多对网络整体的影响越大，同时死亡速度也影响网络收集信息的效率。LEACH 协议约在800轮之后出现明显的节点死亡，1 300轮节点死亡数几乎达到最值，而PEGASIS 算法1 050 轮后死亡节点增加并大约仅用200 轮就达到最大值，虽然前期死亡节点较少，但局部死亡速率较快的情况，对无线传感器网络整体的影响不容忽略，相比之下，LEACH 的整体变化比PEGASIS 好。相比传统的分簇路由算法，文献中提到的ABC 算法有了明显的提升，进行1 500 轮节点死亡率达84%，本文算法节点相对稳定，比ABC 算法的能量消耗更加均匀，进行1 500轮节点死亡率未达到80%，显著地提高了网络的生命周期。

图4 节点数量变化图Fig.4 Change diagram of the number of nodes

3.3 系统能量变化分析

本节针对4 种算法的网络能量变化进行分析。下页图5 中LEACH 算法在1 320 轮消耗了所有能量，PEGASIS 算法在第1 210 轮消耗了所有能量，ABC算法在第1 500轮能量还剩余14%，本文算法在第1 500 轮能量剩余23%，在1 300 轮前消耗速率较慢。可见，本文算法相比于其他3个算法，通过改进灰狼优化算法选举最优簇头，将能量、节点密度作为首要考虑因素，将簇头的位置和簇头的当选频次作为辅助因素，簇间路由不再将单一的距离作为权值，采用能量距离作为权值的迪杰斯特拉路径规划，可以更好地平衡网络整体能耗，延长网络能耗，实验结果与理论预想相符。

图5 系统剩余能量变化图Fig.5 Residual energy change diagram of the system

3.4 关键期节点数量分析

本节将1 100～1 500 轮节点死亡数量进行对比，无线传感器网络节点一般处于环境恶劣，地势偏僻，以及军事勘测过程中，不会经常性地更换，同时受到节点的能量受限，所以，对于同等环境下，轮数越多，死亡节点数量越少，所收集的数据就越多。认为1 100 轮之后的节点整体情况是评价一个网络性能的关键。从图6 中可以看到，LEACH 算法和PEGASIS 算法在1 200 轮后节点几乎死亡，而ABC算法和本文提出的算法有明显优势，死亡节点数量少且均衡变化，同时本文算法的相比较ABC 算法，死亡节点数量相差近100 轮，从而提升了数据传输效率，稳定性适合在特殊军事勘测等环境中的信息数据收集，充分发挥了灰狼优化算法的寻优能力，适应度函数的改进更进一步优化簇头选举的精确性，Dijkstra 算法在簇间路由构建中减少簇头的能耗，避开路径近节点能量少的情况，在关键时期充分发挥传感器收集信息的能力。

图6 1 100～1 500轮节点死亡数量对比图Fig.6 Comparison chart of the number of deaths at 1 100～1 500 round nodes

4 结论

本文提出一种基于灰狼优化和Dijkstra 最小权值路径的分簇路由算法。通过能量、节点密度、位置、簇头频次来改进适应度函数，用灰狼优化算法基于适应度值进行位置更新选举最优簇首，充分发挥了全局搜索性和收敛性的优势，均衡每个簇群内的网络能量消耗，簇间路由通信阶段，采用基于权值函数的Dijkstra路径通讯，降低簇头节点的能量消耗。最后将本文算法与LEACH、PEAGASIS、ABC 算法仿真对比，通过结果分析，本文算法在收集数据过程中节点死亡速率降低，网络整体的能量消耗降低，关键期节点仍保持均衡的状态，有效地提高了网络生命周期。