基于PEGASIS 的无线传感器网络路由协议改进

王海浪，张玲华，2

（1.南京邮电大学通信与信息工程学院，南京 210023；2.南京邮电大学 江苏省通信与网络技术工程研究中心，南京 210023）

0 概述

无线传感器网络（Wireless Sensor Network，WSN）［1］是一种由数量众多的传感器节点自组织而成的网络，节点通过把数据发送给具有信息处理功能的基站（Base Station，BS）完成信息采集，WSN 可以用于军事行动、环境监测、医疗健康等领域［2-3］。传感器节点为了实现信息采集功能，需要在信息采集、数据处理、信息传递等过程中消耗节点自身的能量，但是目标节点周围的环境复杂性和节点数目的庞大性，决定了其不可能在为部署之后的节点进行二次充能和节点的补充［4］，因此传感器系统的能量会逐渐耗尽，整个网络最终将走向死亡。因此，如何促进节点的能耗均衡从延长网络的生命周期，是研究无线传感器网络需要考虑的关键问题［5］。

由于节点能量和网络通信能力的限制，如果让所有节点均和基站直接进行数据传输，节点的能量会急剧衰耗，并且会在一定程度上降低网络的传输效率，使延时增大。针对这些问题，国内外研究人员提出分簇的思想。低能量自适应分层分簇（Low Energy Adaptive Clustering Hierarchy，LEACH）协议［6-7］从整个网络中随机选取一定数目的簇头进行信息整合和发送，从而减少节点损耗，但是当距离基站较远的节点当选簇头时会造成节点提前死亡。传感器信息系统能量高效聚集（Power-Efficient Gathering in Sensor Information System，PEGASIS）协议［8-10］减少了LEACH 协议中频繁的簇头选举所带来的能量损耗，采用轮流当选头节点的策略进行数据传输，但是网络通信时延较大，当出现传输信息的方向和基站位置相反的情况时，会额外增加能耗。文献［11］提出EPEGASIS 协议，提出移动汇聚技术并通过设置多个阈值来保护即将死亡的节点，平衡了节点间的能量消耗，缓解了因靠近基站的节点在接收邻居节点信号时产生的热点问题。但在实际应用中，移动节点容易受到环境因素的影响。文献［12］提出改进的HCTRP-PEGASIS 路由协议，在成链阶段综合传感器的通信半径、当前节点周围密度等因素进行链的建立，可以产生较少的数据冗余和较低能耗的传输链，但有较大的通信延迟。文献［13］提出能量有效链形成算法解决经典PEGASIS 协议贪婪算法中由于某些节点的远距离数据传输所导致的能量消耗不平衡问题，可以避免长链的产生，但同样没有解决网络时延较长的问题。文献［14］提出新型簇头选举方式（PEGASIS Novel-Select-Head，PEGASISNSH）的改进协议，该协议始终优先选取距离基站最近的节点作为头节点，直至当前头节点死亡才开始下一个头节点的选取，选取头节点的策略相对简单，但没有很好地均衡能量和降低网络延迟。

在融合LEACH 协议中多个簇头思想的基础上，本文提出一种基于PEGASIS 的剩余能量距离分 区（Residual Energy Distance Partition，REDP）协议，将每个区域内节点的剩余能量、节点到基站的距离、各区域平均能量等多个影响因素作为网络中头节点选取条件，从而减少头节点的更换次数。此 外，对LEACH协议、PEGASIS协议、PEGASISNSH 协议［14］与本文协议进行对比分析，证明本文协议的有效性。

1 系统模型

1.1 网络模型

基于网络模型对WSN 做如下的设定［15］：

1）所有的节点除了有可以区分自身和其他节点的唯一标识之外，其他属性如初始能量、数据融合能力、通信计算能力等完全相同。

2）节点可以根据节点之间的位置或者节点接收到的信号大小确定节点之间的间距和位置信息。

3）在网络开始运行前，在各个区域随机地部署传感器节点，且节点部署后的位置不会改变。

4）基站位于网络中心，具有稳定的能量供应，但是其余的节点能量有限，不能二次充能。

基于以上设定，本文网络模型如图1 所示。

图1 本文网络模型Fig.1 Network model in this paper

1.2 网络能耗模型

本文所有协议的网络能耗模型均采用一阶无线电能耗模型［16-17］，网络中邻居节点之间传递数据时的能量损耗模型如图2 所示。

图2 节点能耗模型Fig.2 Node energy consumption model

从图2 可以看出节点在进行数据传输时的能量消耗过程，其中Eelec为节点在接收或者发送每比特数据时消耗的能量，ETX和ERX分别代表发送数据包和接收数据包所需要的能量消耗，Ed代表数据在传输过程中的能量损耗，如式（1）所示，根据传输路径的不同，节点能耗模型分为多径衰落模型和自由空间模型，当传输距离小于阈值d0时为自由空间模型，反之为多径衰落模型。

其中：εfs和εamp分别代表自由空间模型和多径衰落模型中的能量损耗因子。在计算传输过程中的能耗时，根据节点之间的距离采取不同的能耗策略，其中d0的计算公式如式（2）所示：

对当前节点来说，每一个节点除了在发送和接收信号时消耗能量，还需要对接收的信号进行数据融合，将接收的数据包融合为相同长度的数据包，节点融合一个长度为Kb 的数据包所消耗的能量EDA的表达式如式（3）所示：

其中：Eda代表每比特的数据融合所消耗的能量。

结合PEGASIS 协议在传输过程中的特点，除了链中末端的节点之外，所有的节点都要进行数据接收、数据融合、数据传输等至少3 个过程，因此每一个节点在完成每一轮传输过程时需要消耗的总能量E(i)如式（4）和式（5）所示，其中式（5）是结合式（1）、式（3）和式（4）所得。

2 经典PEGASIS 协议

2.1 PEGASIS 协议原理

PEGASIS 协议是一种基于链状结构的路由传输协议，是对经典LEACH 协议的改进。此协议包含链的形成阶段、头节点的选取阶段和数据传输阶段3 个阶段［18］，最后由本轮所选取的头节点将本网络的所有信息传递给基站，完成一轮数据采集［19］。

2.2 链的形成阶段

PEGASIS 协议在将整个网络中的节点成链时，为保证每一个节点的通信距离最小，总是从距离基站最远的节点开始形成链［20］。采用贪心算法，将找到所有存活节点中距离当前节点最近的节点作为下一个节点，当串起所有存活的节点成一个网络时，链的形成阶段结束。

2.3 头节点的选取阶段

PEGASIS 协议中头节点的选取策略是将网络中节点进行编号，根据编号轮流当选头节点，在第i轮时，当选头节点的编号为imodn［21］。采用这种选取策略可以使整个网络中的节点均有机会当选为头节点［22］，在一定程度上能够实现能量的均衡消耗。

如图3 所示为经典的PEGASIS 协议在第1 轮时网络成链的示意图，所有节点随机地部署在整个网络中，BS 位于整个网络的中心，从图3 可以看出从距离基站最远的34 号节点开始成链，到47 号节点结束，并且在第1 轮时所选取的头节点正是编号为1 的节点。

图3 PEGASIS 协议第1 轮网络成链图（节点总数n=100）Fig.3 Network forming chain diagram of PEGASIS protocol in the first round（total number of nodes n=100）

2.4 数据传输阶段

PEGASIS 协议的数据传输阶段采用Token（令牌）控制机制［23-24］，如图4 所示，网络中存在6 个传感器节点，编号分别为N1、N2、N3、N4、N5、N6。假设在当前轮N4 为头节点，在数据传输时头节点N4 把Token 沿着链传递给链的末尾N1，N1 将含有本节点采集信息的数据包传递给N2，N2在接收数据之后结合自身采集的信息，并进行数据融合，形成一个相同长度的数据包，然后按照相同流程经过节点N3 传递给头节点N4，此时头节点又将Token 传递给N6，然后按照相同的流程把数据包传递给头节点N4，N4将数据包进行融合后发送给基站，本轮的数据传输结束。

图4 PEGASIS 协议数据传输过程Fig.4 Process of PEGASIS protocol data transmission

3 PEGASIS-REDP 协议

传统的PEGASIS 协议采用轮流方式当选头节点，没有综合头节点距离基站的距离和头节点剩余的能量问题，因此会在传递信息的过程中出现部分剩余能量较少或者距离基站较远的节点当选头节点的现象，造成能耗增加。针对这些问题，根据经典协议对PEGASIS-REDP 协议进行改进。

3.1 区域划分

虽然在经典的PEGASIS 协议成链过程中，通常采用贪心算法寻找最近的节点成链，但结果也有差链和优链之分［25］，如图3 中的17 号和61 号节点即是利用贪心算法形成的差链。经过多次仿真结果分析可知，网络区域越大，就越容易在成链的过程中产生差链。为避免出现2 个节点间距离过大的差链情况发生，本文对网络进行分区，缩短成链过程中节点之间的距离。

分区分为均匀分区和非均匀分区，非均匀分区类似于LEACH 协议中的分簇［26］，普通节点只根据与簇头的距离远近情况选取距离最近的簇头并加入网络中，但当区域内节点密度较大时，簇内节点数目会急剧增加，导致出现头节点的能耗加快、节点提前死亡的问题。均匀分区可以很好地解决因为簇内节点数目过多而造成节点提前死亡的问题，在每一个区域内设置相同数目的节点，从而保证区域内节点随机分布时节点密度相同，以均衡能耗，延长节点的死亡时间。

因此，PEGASIS-REDP 协议提出对整个网络空间进行均匀分区，并且采用将每个区域单独成链的策略，缩短在差链形成时节点之间的距离，从而减少传输能耗。

3.2 剩余能量和距离因子

PEGASIS-REDP 协议在区域内选取头节点时，不再采取轮流当选头节点的方式，而是综合考虑节点距离基站的距离d、节点剩余能量Ei、区域内平均能量Eavg等因素。Eavg的表达式如式（6）所示：

其中：Eij表示在第j个区域内编号为i的节点能量；mj表示第j个区域内存活的节点数。

在选取头节点的过程中，总是从距离基站最近的节点开始当选头节点，不会频繁地在每一轮中更换头节点，且只有当前轮头节点的剩余能量满足更换条件时才更换头节点。因此可以保证在头节点能量剩余的情况下，始终距离基站最近。如图5 所示是在第1 轮时采用PEGASIS-REDP 协议分区成链的示意图，其中6 号、50 号、69号和97 号这4 个节点因为距离基站最近，所以在第1 轮中被选取为每一个区域的头节点。

图5 PEGASIS-REDP 协议第1 轮网络成链图（节点总数n=100）Fig.5 Network forming chain diagram of PEGASIS-REDP protocol in the first round（total number of nodes n=100）

图6 和图7 分别是在同一网络部署条件下采用PEGASIS-REDP 协议时，网络运行到第1 000 轮和第1 100 轮的网络成链图。

图6 PEGASIS-REDP 协议第1 000 轮网络成链图（节点总数n=100）Fig.6 Network forming chain diagram of PEGASIS-REDP protocol in the 1 000th round（total number of nodes n=100）

图7 PEGASIS-REDP 协议第1 100 轮网络成链图（节点总数n=100）Fig.7 Network diagram of PEGASIS-REDP protocol in the 1 100th round（total number of nodes n=100）

由图5～图7 可对比分析得出：

1）每一轮均会重新组链，但有些节点因为能量耗尽而死亡时就不再参与到网络成链中。

2）当前一轮的头节点在当前轮不满足能量因子要求时，会重新进行头节点的选取，但是选取时仍然是选取距离基站较近的节点。

因此，可以从头节点到基站的传输距离上达到降低传输能耗的目的。

3.3 PEGASIS-REDP 协议流程

PEGASIS-REDP 协议流程如下：

1）整个网络进行分区，在每个区随机部署等量的节点，并对节点进行初始能量赋值；

2）基站向全网广播信息，网络内的节点接收信息，计算并记录自身与基站的距离；

3）统计每个区域内存活的节点和剩余能量；

4）将每个区内存活的节点成链，并记录节点顺序和节点之间的距离；

5）找出距离基站最近的节点并将其作为头节点，判断节点是否满足能量阈值和剩余能量的条件，如果满足条件则确定为当前轮的头节点，如果不满足则找到距离基站次近的节点作为头节点；

6）开始进行数据传输，根据网络传输模型进行数据传输和接收数据包时的能耗计算；

7）一轮完成，将每个区域内的节点剩余能量和存活的节点进行统计；

8）若网络中节点未全部死亡，则返回第3 步，若网络中所有的节点死亡则结束。

PEGASIS-REDP 协议流程如图8 所示。

图8 PEGASIS-REDP 协议流程Fig.8 Procedure of PEGASIS-REDP protocol

4 实验结果与分析

本文在MATLAB 2018a 平台上进行仿真实验，由于PEGASIS 协议是在LEACH 基础上的改进，且PEGASIS-REDP也融合了LEACH 协议中多簇头的思想，因此本文对LEACH、PEGASIS、PEGASIS-NSH、PEGASIS-REDP 协议在网络存活节点、节点的剩余能量以及网络延迟方面进行分析和比较，网络模型的参数设置见表1。

表1 网络参数设置Table 1 Network parameter settings

4.1 网络延迟对比

PEGASIS-REDP 协议采用了分区策略，分区后每个区域内节点数目相对于PEGASIS 协议网络中节点数目大大减少，在不同区域内可以单独完成信息采集，将结果单独传输给基站。因此采用分区可以很好地解决网络延迟问题。

由网络参数模型可知，节点处理信息能力相同，设2 个邻居节点之间进行数据接收、数据融合和数据发送所消耗的总时间为ti，则PEGASIS 协议一轮数据传输总耗时TP的表达式如式（7）所示：

PEGASIS-REDP 协议一轮数据传输总耗时TREDP表达式如式（8）所示：

其中：j表示划分区域的数目。

假设每一个节点在传递数据包过程中节点在接收、融合和发送过程共需要1 ms。由图9 可以看出，相比于PEGASIS 协议传递整个网络的数据包的延迟时间，PEGASIS-REDP 协议将整个网络的延迟时间减少了约300%。这是因为PEGASIS-REDP 协议采用的是将整个区域进行分区的策略，在数据传输的过程中，数据包可以在各个区内单独进行信息传递并发送给基站，所以PEGASIS-REDP协议可以很好地改善整个网络的延迟。在实现成本方面，虽然与经典的PEGASIS 协议相比，PEGASIS-REDP 协议多出3 个头节点，但是网络中普通节点会减少3 个，且PEGASISREDP协议中每一次区域内头节点的选取均是选择距离基站最近的节点，可以在传输数据包的同时将能量损耗达到最小。

图9 网络延时对比Fig.9 Comparison of network delay

4.2 网络剩余能量对比

经典协议PEGASIS 在每一轮都会进行头节点的更换，PEGASIS-REDP 协议相比于经典协议引入了距离因子dmin、最小能量阈值Emin和剩余能量因子Ei，只有在满足更换条件时才进行头节点的更换，不会频繁更换头节点，且只选择距离基站最近的节点来传输信息，因此可以均衡网络能耗。

不同协议的网络剩余能量随轮数变化情况如图10 所示。从图10 中可以看出PEGASIS-REDP协议的网络剩余能量始终优于LEACH 协议、PEGASIS 协议和PEGASIS-NSH 协议。当网络能耗为50%时，LEACH、PEGASIS 和PEGASIS-NSH 协议分别运行了281 轮、484轮和498 轮，而PEGASISREDP 协议运行了525 轮，相比于这3 种协议分别延迟了86.8%、8.5%和5.4%。当能量消耗为90%时，LEACH、PEGASIS和PEGASIS-NSH 协议分别运行了601 轮、926 轮和940 轮，PEGASIS-REDP 运行了988 轮，相比于其他3个协议分别延迟了64.4%、6.7%和5.1%。

图10 不同协议的网络剩余能量Fig.10 Network residual energy of different protocols

综合以上可知，PEGASIS-REDP 协议在均衡网络能量方面要优于LEACH、PEGASIS 和PEGASIS-NSH协议，这是因为PEGASIS-REDP 协议在选取头节点的过程中，不会频繁更换头节点，且引入了最小能量阈值和剩余能量作为头节点的更换条件，从而均衡了整个网络的能耗。

4.3 存活节点对比

经过多次实验并取平均值，4 种协议的网络存活节点关系如图11 和表2 所示。

图11 不同协议的存活节点数随轮数的变化Fig.11 Variation of the number of surviving nodes with the number of rounds of different protocols

表2 不同协议在相同死亡节点数时运行的轮数Table 2 Number of rounds of different protocols running at the same number of dead nodes

从图11 可以看出，PEGASIS-REDP 协议在相同轮数下存活的节点数始终多于其他协议。对表2 进行数据分析得到：PEGASIS-REDP 协议在第10 个节点死亡时运行了864 轮，相比于LEACH 协议的350 轮、PEGASIS 协议的563轮和PEGASIS-NSH 协议 的585 轮分别延迟了147%、53.5% 和47.7%；PEGASIS-REDP 协议在20%节点死亡时的轮数为1 010 轮，相比于LEACH 协议的418 轮、PEGASIS 协议的735轮和PEGASIS-NSH 协议的751 轮，分别延迟了141.6%、37.4%和34.5%。由图10 可以看出，当有50%节点死亡时整个网络剩余的能量已经不足95%，因此本文以50%节点死亡时的轮数作为网络的生存时间，此时PEGASIS-REDP 协议的网络生命周期为1 115 轮，相比于LEACH 协议的602 轮、PEGASIS 协议的932轮和PEGASIS-NSH 协议的983 轮，分别延迟了85.2%、19.6%和13.4%。

综上所述，PEGASIS-REDP 协议在延迟节点死亡的轮数和延长网络存活时间上优于LEACH 协议、PEGASIS 协议和PEGASIS-NSH 协议。这是因为PEGASIS-REDP 协议采用分区策略，每次头节点的选取总是选择在节点能量满足要求的前提下，并选择距离基站最近的节点作为头节点进行数据发送，很好地均衡了距离基站的距离和节点剩余的能量，因此可以有效延迟节点死亡的轮数，延长整个网络的生存时间。

5 结束语

本文针对经典的PEGASIS 协议存在的问题提出PEGASIS-REDP 协议，通过对整个网络进行分区，并选取多个头节点的方法进行数据传输，在每个区域采用优先寻找距离基站最近的节点作为头节点的策略。实验结果表明，与LEACH、PEGASIS、PEGASIS-NSH 协议相比，PEGASIS-REDP 协议可以有效减少整个网络的延迟，均衡整个网络的能量消耗，延迟节点死亡的轮数及延长网络的生存时间。虽然在成链阶段依靠分区缩小网络范围缩短了差链形成的距离，但仍然可能出现差链的情况。下一步将设置距离阈值因子，利用贪心算法寻找下一个距离当前节点最近的节点，当此节点间的距离大于所设定的距离阈值时，则重新寻找邻居节点，从而对成链过程中的差链进行优化。