基于双簇头的WSNs 非均匀分簇路由算法

陈辉，高岩

（安徽理工大学计算机科学与工程学院，安徽淮南 232001）

0 概述

无线传感器网络（Wireless Sensor Networks，WSNs）由大量密集部署的传感器节点组成［1］，通过节点间的相互协作，才能周期性地感知监控区域的状况，并将监测数据传输到基站，因此传感器节点之间的协作非常重要［2］。在分层网络体系结构中，将网络中的节点分成若干个簇，每个簇都指定一个簇头［3］，簇头负责收集并融合簇内成员节点的信息或转发邻居簇头的信息，并将信息向基站方向传递。根据网络的结构，簇头通常使用单跳或多跳通信方式将数据发送到基站［4］。单跳传输意味着部分节点必须进行长距离通信，而长距离传输比短距离传输消耗更多的能量［5-6］，因此距离基站较远的节点比距离基站近的节点消耗更多的能量，导致网络的能量消耗不平衡，进而导致部分节点过早死亡，此问题可以通过使用多跳通信解决。但在多跳通信的网络中，靠近基站的节点会出现过重的流量负载［7］，这样易造成局部网络拥塞，形成“热区”问题［8］，导致网络延迟增加、加速节点能耗，严重影响簇的生存周期和整个网络的生存时间。因此，如何缓解和避免无线传感器网络“热区”问题已成为研究的重点［9］。

为缓解“热区”问题，许多路由算法被提出。低功耗自适应集簇分层型（Low Energy Adaptive Clustering Hierarchy，LEACH）协议［10］是最经典的基于单跳通信的分簇路由协议，在该协议中，簇头节点随机轮转，节点以一种循环的方式来担任簇头并直接与基站通信，以达到均衡网络负载的目的。但是，随机选择簇头会引发簇头分布不均匀、能量较低的节点也会被选取为簇头，最终导致部分节点过早死忙。文献［11］提出低功耗非均匀分簇路由（Energy-Efficient Uneven Clustering，EEUC）算法，该算法将路由通信方式分为簇内通信、簇头与基站通信两部分。簇内通信采用单跳通信，簇头与基站的通信采用多跳的方式，避免了长距离数据传输造成的能量浪费。但是簇头的选取方法类似LEACH 协议，容易导致簇头分布不均匀。文献［12］对EEUC 协议进行改进，提出一种改进型的EEUC 协议。该协议在簇头竞争阶段综合考虑了节点的剩余能量、节点与基站的距离、邻居节点的数目以及能耗速率，有效均衡了网络能耗。但该算法适用于长宽差别不大的监测环境，针对狭长的环境适用性较差。

文献［13］提出异构分簇路由（Distributed Energy-Efficient Clustering，DEEC）协议，通过引入节点剩余能量避免了低能量节点担任簇头节点，但没有考虑到节点位置分布可能会造成簇头节点分布不均匀。文献［14］对LEACH 协议的阈值公式进行了改进，引入了节点剩余能量以及考虑了节点与基站之间的距离，增大了靠近基站的节点当选簇头的机率。在节点竞争半径的计算中引入了继任以及前任能量消耗因子，使得竞争半径的计算更加合理。虽然该算法能够有效地均衡节点间的能耗，但是不适用于狭长型的网络区域。文献［15］在优化链路状态路由算法的基础上引入了多径思想，通过路径节点的剩余能量占比、节点的邻居节点比例等因素对转发路径进行评估，并选择最优路径进行数据传输，但在中继路由的选择中只考虑了节点的能量因素。文献［16］针对“热区问题”提出一种基于梯度异构WSNs 非均匀分簇路由协议（Gradient-Based Unequal Clustering Routing Protocol，GURCP），通过虚拟梯度分区，根据节点能量计算簇头竞争半径，从而形成不均匀分簇，综合节点的剩余能量和与中转节点的距离选择下一跳路由，最终达到均衡网络能耗的目的，算法适用于狭长型的网络区域。但是，协议在选择簇头阶段只考虑了节点的能量因素，没有考虑到节点的邻居数量以及簇头与中转节点的相对距离。

此外，也有学者对簇内采用双簇头节点开展了研究。文献［17］提出基于双簇头的多跳路由协议（Multihop Routing Protocol Based on Double Cluster-heads，MRDC）。该协议引入了副簇头节点，在主簇头选择完毕后由主簇头从成员节点中选择剩余能量较大且距离自身较近的节点成为副簇头，主簇头将收集到的信息发送给副簇头节点，由副簇头节点进行转发，从而减少主簇头的能耗。但该协议中副簇头长期工作会使网络的整体能耗增加。文献［18］提出一种基于副簇头的移动自组织网络分簇算法，在成簇阶段选取权值最小的节点为副簇头，副簇头能够分摊簇头的通信负担，必要时还可以独立出来成为新的簇头。该算法可以减少簇的重组次数，降低节点通信的丢包率，但副簇头节点长期处于工作状态中，而且频繁进行簇内簇头选举也会消耗网络能耗。文献［19］提出一种基于非均匀划分的自适应双簇头路由算法，在网络初始化阶段根据节点与基站的距离将网络的区域进行不均匀划分，并在靠近基站的簇内选举产生副簇头，帮助主簇头分摊通信负担。该算法可以均衡网络节点的能量消耗，同时也延长了网络的生存时间，但在副簇头的选取上，只考虑了节点的能量因素，忽略了距离因素的影响，且副簇头没有设定启动机制。

本文提出一种基于双簇头的非均匀分簇路由算法（Non-uniform Clustering Routing Algorithm Based on Double Cluster Heads，NCDH）。在网络初始化阶段将网络区域划分为若干子区域，根据节点所在的子区域面积计算簇头竞争半径，实现非均匀分簇。在簇头选择阶段，综合考虑节点的能量、节点与基站的距离、节点度等因素选择主簇头，副簇头选择除了考虑主簇头选取应考虑的因素外，还需考虑与主簇头的距离。在数据传输阶段，簇头节点根据自身的剩余能量以及拥塞情况决定是否启用副簇头，以缓解簇头节点的压力，从而延长簇的生存时间，最终达到均衡网络能耗、改善“热区”问题的目的。

1 网络与能耗模型

1.1 无线传感器网络的层次结构

无线传感器网络的结构模型如图1 所示，成员节点通过单跳通信方式与主簇头通信，主簇头或副簇头通过多跳通信方式与基站通信。由于传感器节点通常处于不便于经常更换电池的地方，因此对传感器网络进行能耗优化是整个网络长期稳定运行的必要前提［20-21］。

图1 无线传感器网络层次结构Fig.1 Wireless sensor networks architecture

本文的无线传感器网络模型假设［22］如下：

1）网络区域由m个传感器节点和1 个基站组成，传感器节点均匀分布在N×M的区域内；

2）网络区域内没有障碍物和噪声干扰，基站能量充足；

3）每个节点的电池容量、存储能力、通信的范围、感知范围相同；

4）传感器节点是静止的，且信息接收节点能基于接收信号强度计算出与信息发射节点的距离。另外，节点无线发射功率可控，节点可以根据需要调整自身发射功率。

1.2 能耗模型

本文算法NCDH 的所有通信过程均采用文献［23］的通信模型，节点接收或发送信息，节点的发射模块或者接收模块都会消耗能量。

传感器节点发送b比特的信息能耗如下：

其中：Eelec为节点传输单位bit 所要消耗的能量；d为发送节点至目标节点的距离；d0为距离阈值，d0=为自由空间模型下电路的损耗系数；εa为多径衰落信道模型下的电路损耗系数。传感器节点接收b比特的信息能耗如下：

设簇内有n个成员节点，则簇头节点收到成员节点长度为l的信息进行信息融合的能耗为：

其中：ED为簇头节点融合单位bit 所消耗的能量。

1.3 网络区域模型

为了均衡网络的整体能耗，将网络区域根据距离阈值TX_MAX 分为近区和远区。当节点与基站的距离UNIT_BS≤TX_MAX 时，该区域定义为近区。在近区区域内来自网络上游的信息包过多且处于与基站的有效通信范围内，因此近区网络节点可直接与基站通信，上级网络随机选择该区域的高能量节点作为中转节点。当节点与基站的距离大于TX_MAX时，该区域定义为远区。为了延长簇生存时间，首要任务就是要解决簇头能耗过高的问题。因此，在每一个簇内，除了设置一个负责簇内数据收集的簇头外，还设置一个辅助簇头转发数据的节点。前者称为主簇头，后者称为副簇头。在启用副簇头后，主簇头的主要任务是收集成员节点的信息，将其融合后转发至副簇头节点。副簇头负责协助主簇头接收转发信息，将收集到的信息进行信息融合后发送给下一级网络区域的转发节点。远区网络节点的通信方式如图2 所示，网络区域划分如图3 所示。

图2 远区网络启用副簇头后的通信方式Fig.2 Communication mode with secondary cluster headers

图3 网络区域划分Fig.3 The network area division

网络区域划分完毕后根据文献［24］计算出最优网络子区个数和簇头竞争半径。求解|f(k)|的最小值可得出网络的最优分区个数k，f(k)的表达式如式（4）所示：

其中：M为远区网络的长度。

若在远区网络区域i中，区域的面积为Si，簇头竞争半径为Ri，区域簇头个数为ci，则可以得出：

设q(i)为区域i的簇头节点负担的平均数据流量，则可得到式（7）：

其中：ρ为节点密度；a是数据融合率；q为每个节点的数据包大小；ci为子区i的簇的数量；k为区域个数；i为远区网络子区域编号。

为了均衡相邻两区域的数据传输量，根据式（7），令q(i)=q(i+1)，得式（8）：

结合式（6）和式（8）可得出区域i+1 的簇竞争半径：

根据式（9）可知距离基站近的区域簇竞争半径较小，距离基站远的区域簇竞争半径较大。在经典的非均匀分簇方法中，每个簇头节点的竞争半径往往是由簇头节点独立计算得出，导致计算量增大；而通过区域划分的方式进行非均匀分簇，簇头节点的竞争半径可直接通过其所在的分区以及前一分区簇头的竞争半径直接计算获得，效率更高。

2 NCDH 算法

本文提出的NCDH 算法按照以轮为周期采集数据。每一轮由3 个阶段组成，分别为主簇头和副簇头选取、簇的形成、簇间路由。

2.1 簇头竞选

2.1.1 主簇头竞选

以文献［25］为基础对主簇头竞选阈值公式改进，如式（10）所示：

其中：p为主簇头在全网节点所占的比例；r为当前轮数；G为未当选簇头节点的集合；e(i)=，Ei为节点的剩余能量；E0为节点的初始能量；f(i)=，m为节点个数；Nn为节点i的邻居节点数目，是指在第r轮时节点i通信范围R内可进行信息交互存活的节点；d(i)=1-，其中dt为节点i距基站的距离；dMAX=+TX_MAX 为节点所在区域的区域边缘与基站的距离，其中：i（取值1，2，…，k）为节点所在的区域编号；M为网络的区域长度；k为网络区域的个数；C1、C2、C3为参数，且C1+C2+C3=1。网络中远区节点产生0～1 的随机数，若随机数<阈值T（n）则成为候选簇头，加入候选集。若该节点为候选集中剩余能量最大值则竞选成功，向区域广播竞选成功的消息；反之则进入休眠等待入簇通知。

改进阈值公式的理论依据：首先，由于簇头的处理任务多，转发任务重，若能量较低的节点当选簇头会因能量消耗过快加速死亡，因此需要剩余能量高的节点当选簇头，根据节点的能量水平选择簇头是最为重要的因素；其次，当簇头节点处于的区域节点密集时，由能量消耗模型可知簇内的能耗会减少，因此根据节点的邻居节点数量选择簇头可有效减少簇头能耗；最后，簇头节点与基站的距离直接影响数据传输的路径长度，因此选择合理的传输距离也是路由算法设计中的重要方面。在网络的运行过程中，节点剩余能量、邻居节点个数以及邻居节点到基站的距离都较容易获得，因此簇头的竞选过程是易于实现的。

2.1.2 簇的形成

根据簇头的竞争半径计算式（9）可知：随着簇头与基站距离增大，簇头的竞争半径逐增大。节点竞选簇头成功后以自身竞争半径广播竞选成功的消息，周围节点接收到竞选成功消息后向簇头节点发送入簇请求，待簇头节点同意请求后加入该簇。若节点接收到多个簇头竞选成功消息，则选择距离较近的簇头节点发送入簇请求。

2.1.3 副簇头的竞选

副簇头的选取思想与主簇头类似。首先，为了使副簇头的能量高，应当选取节点剩余能量高的节点，节点的剩余能量越高，则选举成功的概率越大。其次，为了降低节点的传输能耗，副簇头应该靠近主簇头且位于靠近基站的方向。当节点与簇头的距离越小时，选举成功的概率越高。成员节点入簇完成后，主簇头向簇内成员节点广播副簇头选举通知，成员节点根据式（11）计算自身的选举阈值并向簇内广播计算结果，若节点的选举阈值为簇内最大值则向主簇头发送竞选成功消息，主簇头记录该节点的信息，副簇头处于等待启动状态。

其中：α、β为参数且α+β=1；Ei为节点剩余能量；E0为节点的初始能量；di为节点i与簇头的距离。为了使选取的副簇头位于靠近基站的方向，定义节点的方向阈值Di表达式如下：

其中：di为节点i与基站的距离；dC为簇头与基站的距离。

当副簇头选举完成后，网络进入运行阶段。簇头向中转节点通信时，会将自身信息打包发送给中转节点，中转节点记录簇头节点的信息。簇头节点在网络运行期间根据自身状态判断是否启用副簇头。当簇头能量低于簇内节点平均能量时，簇头向副簇头与中转节点发送启用信息，中转节点修改路由表与副簇头建立连接。另外，当簇头缓存区队列长度达到拥塞阈值即节点的缓存队列溢出时，簇头也会启用副簇头以缓解网络拥塞。

2.2 NCDH 簇间路由设计

NCDH 算法采用簇内单跳通信，簇头与基站之间采用多跳通信方式。为了使网络的通信能耗降低，延长网络的生存时间，簇头下一跳节点应当具有较高的能量且距离簇头较近。定义中转函数Tran（i，j）：

其中：λ+μ=1；j为节点i的候选下一跳节点；Ej为节点j的剩余能量；D（i，j）为节点i与节点j的距离；Davg为节点i与其可到达下一跳节点的平均距离。当下一跳节点的剩余能量越多，距离节点i越近时其中转函数值越大。假设簇头节点ni所在的网络区域为i，则该簇头节点寻找下一跳中转节点的步骤是：首先获取下一跳区域能够接收节点信息包的节点信息；然后分别计算与下一跳区域中转节点的中转函数值；最后选择中转函数值最大的节点作为簇头的中转节点。

NCDH 算法运行流程如下：

步骤1基站广播初始化信息，成员节点接收信息后开始划分网络区域，网络近区节点直接与基站进行通信。

步骤2网络远区各子区间根据簇头竞选规则进行簇头选举，簇头选举完成后，成员节点根据簇头竞争半径申请入簇。

步骤3成员节点入簇完成后簇头节点为成员节点分配时隙。

步骤4簇内成员节点根据式（11）选举副簇头节点。

步骤5簇头节点获取相邻区域中转节点信息，分别计算与它们的中转函数，选取中转函数最大的节点作为中转节点。

步骤6网络进入稳定运行阶段，簇头在运行期间监控自身剩余能量和缓存区队列长度是否到达启用副簇头的条件，若满足任一条件则及时启用副簇头。

步骤7若簇内副簇头启动，簇头与中转节点修改路由表与副簇头建立通信。簇头创建TDMA 时隙并将簇内信息收集融合后发送给副簇头后进入休眠模式。副簇头将信息中转后进入休眠模式等待下一时隙的到来。若副簇头没有启用则继续进行步骤6。

步骤8每一轮结束后，转向步骤2，开始新的一轮。

3 NCDH 算法的能耗分析

在NCDH 算法中，区域i中的簇头需要接收本簇成员节点的信息，同时也需要转发来自网络上游区域的消息。若区域i的面积为Si，区域内的节点密度为ρ，区域内的簇头数为ci，数据融合率为a，每个节点的数据包大小为q。那么每个簇头需要收集簇内节点的数据包个数为（ρ×a×q×Si）/ci，若网络的最优区域数为k，那么每个簇头需要转发数据包的数量为（ρ×a×q×Si）(k-i)/ci。

因此，在单簇头网络中，簇头需要发送的数据包个数Q1=（ρ×a×q×Si）(k-i+1)/ci；在双簇头网络中，簇头需要转发的数据包个数Q2=（ρ×a×q×Si）/ci，而此时副簇头需要转发的数据包个数Q1=（ρ×a×q×Si）(k-i+1)/ci。根据以上分析可以得出单簇头网络和双簇头网络中区域i的网络能耗E1和E2分别为：

其中：Q2要远小于Q1；Eto_transfer1为单簇头网络中簇头传输1 bit 数据至中转节点的能耗；Eto_DCH为双簇头网络中簇头传输1 bit 数据至副簇头的能耗；Eto_transfer2为双簇头网络中副簇头传输1 bit 数据至中转节点的能耗。

由1.2 节中的能耗模型可知，节点的能耗随着通信距离的增加而变大，由于NDCH 算法优化了簇间通信的距离，因此Eto_transfer2≤Eto_transfer1；另外，由于簇内通信的距离通常小于簇间通信的距离，因此Eto_DCH＜Eto_transfer1。通过式（14）与式（15）可以得出所提算法的双簇头网络相对于单簇头网络的能耗并没有明显的增加，且NDCH 算法中副簇头并非一直处于工作状态，只有当簇头能量低于能量阈值或陷入拥塞时，副簇头才会被唤醒工作，因此NDCH 算法能够有效防止因簇头提前死亡导致的网络“热区”问题。

4 实验结果与分析

4.1 仿真参数设置

为了验证NCDH 算法的有效性，采用MATLAB R2019a 仿真软件分别对网络能量均匀程度、网络区域长度对算法性能的影响、网络生命周期和网络吞吐量4 个方面进行了对比实验，实验序号分别记为E1、E2、E3、E4。在 式（10）中，C1、C2、C3分别取值0.3、0.3、0.4；在式（11）中，α、β分别取值0.8、0.2；在式（13）中，λ、μ分别取值0.4 和0.6。其余仿真实验参数设置如表1 所示。

表1 仿真参数设置Table 1 Simulation parameter setting

在仿真实验中，使用DEEC 算法、MRDC 算法及GURCP 作为对比算法，4 种算法的特点如表2所示。

表2 4 种算法的特点对比Table 2 Comparison of features of four algorithms

DEEC 算法是一种基于LEACH 改进的算法，在簇头选举阶段综合考虑了节点的剩余能量，避免了能量过低的节点当选簇头的情况，在数据传输阶段使用单跳传输方式与基站通信。MRDC 算法是一种基于LEACH 改进的双簇头算法，在副簇头的选举上综合考虑了节点本身的剩余能量和距簇头节点的距离，在数据传输阶段使用多跳传输方式与基站通信。GURCP 算法是一种基于虚拟区域划分的非均匀分簇算法，在簇头节点的选举上改进了LEACH 的阈值公式，加入了全网平均剩余能量，在数据传输阶段使用多跳传输方式与基站通信。

4.2 结果分析

4.2.1 网络能量均匀程度

在网络节点数为400，网络面积为800 m×30 m的情况下，在网络运行1 000 轮后，DEEC、MRDC、GURCP 以及NCDH 算法的节点剩余能量等高线如图4 所示。由图4 可知，MRDC 算法的热区问题比较突出，网络剩余能量很不均匀。DEEC 算法由于采用单跳传输，因此能量消耗较快，远离基站的区域，节点几乎完全死亡。GURCP 算法中节点的剩余能量集中在0.20～0.34 J 之间，在靠近基站的区域形成了“热区”，NCDH 算法的剩余能量集中在0.35～0.41 J 之间，这两种算法能耗较为均匀，但NCDH 算法的均匀程度更好些。

图4 4 种算法的节点剩余能量等高线Fig.4 Contour of node residual energy of four algorithms

4.2.2 区域长度的影响

为了探究网络区域大小对4 种算法的影响，固定网络区域的宽度为30 m，仿真轮数为1 000 轮，网络区域长度从100 m 至1 000 m 依次增加。在1 000 轮后网络的生存节点数量与网络剩余能量分别如图5、图6 所示。当网络的长度逐步增加时，4 种算法的生存节点数量和网络剩余能量都在减少。但NCDH 算法减少的变化趋势最缓慢，这是因为NCDH 算法采用了虚拟分区的方式进行分簇，优化了簇头和副簇头的选举方式，且副簇头不会一直处于工作状态。DEEC 由于是单跳路由算法，难以适应狭长的网络环境，因此生存节点数量快速减少。MRDC 算法采用副簇头长期存在的工作方式使得网络能量开销增加，因此表现出剩余能量与生存节点数都下降的趋势。GURCP 算法和NCDH 算法在网络长度增加时表现较好，但是在长距离为1 000 m左右时，NCDH 算法由于采用双簇头的工作方式要明显优于GURCP 算法，这说明NCDH 算法适合用于狭长的网络环境。

图5 生存节点数量与网络区域长度的关系Fig.5 Relationship between the number of surviving nodes and the length of network area

图6 网络剩余能量与网络区域长度的关系Fig.6 Relationship between the network residual energy and the length of network area

4.2.3 网络生命周期

为了验证本文算法中双簇头的有效性，以网络剩余能量与网络初始能量的比为切入点，在网络区域为800 m×30 m 的条件下比较NCDH 算法有副簇头情况、无副簇头情况与MRDC 算法双簇头时算法性能差异情况。图7 为3 种算法的网络剩余能量对比柱状图。

图7 不同方案的网络剩余能量对比Fig.7 Comparison of network residual energy of different schemes

由图7 可知，3 种算法运行至网络剩余能量比为0.8 的时间大致相同，但是当运行的轮数逐渐增大时差距逐渐拉开，MRDC 算法随着运行轮数的增加，剩余能量降低的速度越来越快，造成这种现象的原因主要是由于该算法副簇头一直处于工作状态，造成了不必要的能量消耗。另外，MRDC 算法在选举簇头以及副簇头时对节点的自身因素考虑较少，而NCDH 算法在选举簇头时能够选取更优质的节点作为簇头，因此在NCDH 算法单簇头的情况下网络剩余能量下降的速度也更缓慢。NCDH 算法在使用双簇头方式时，通过设置副簇头启用时间有效避免了不必要的能量开销，且副簇头的出现也均衡了簇头的通信负担，因此在使用双簇头时网络生存时间最长，这充分证明了NCDH 算法双簇头的有效性。

为了验证本文阈值设定的有效性，设置了4 种对比方案，如表3 所示。

表3 4 种对比方案信息Table 3 Information of four comparison schemes

图8 为4 种方案的网络剩余能量对比柱状图。从图中可以得出，有能量阈值的路由方案要优于只有拥塞阈值的路由方案。方案1 由于无拥塞阈值和能量阈值，副簇头会一直处于工作状态，因此会过多消耗网络能量，网络生存时间过短。而本文方案（方案4）的能量阈值和拥塞阈值可以适时地加入网络，能够分摊簇头的通信负担，延长网络的生存时间，这证明所提算法的阈值设定是有效的。

图8 不同方案的网络剩余能量对比Fig.8 Comparison of network residual energy of different schemes

网络生存节点数量是衡量路由算法是否优越的重要指标。在网络区域为800 m×30 m 条件下，DEEC、MRDC、GURCP 以及NCDH 这4 种算法的网络生存节点曲线图如图9 所示，表4 为4 种算法第1 个节点和50%节点死亡时间。

表4 4 种算法节点死亡时间比较Table 4 Comparison of node dead time of four algorithms

图9 网络生存节点随时间的变化Fig.9 Network survival nodes varying with time

通过表4 和图9 可知，NCDH 算法在网络运行周期内生存节点数较多，这表明NCDH 算法通过划分网络区域进行不均匀分簇，再通过优化簇头选举，令副簇头适时加入网络以减少簇头的能耗，可以有效均衡网络能耗。DEEC 算法由于“热区”问题的存在导致节点死亡数量随网络的运行逐步增加，最终导致节点全部死亡。

MRDC 算法引入双簇头方案解决了簇头节点能耗过高的问题，但是双簇头自网络运行开始就共存，导致网络整体能耗增加，在运行到第1 034 轮后网络中生存节点数量迅速减少。GURCP 算法与NCDH 算法的节点死亡速度相对均衡，由于NCDH 算法采用非均匀分簇并适时加入副簇头均衡簇头能耗，从而延长了簇的生存时间，在网络生存时间上优于其他3 种算法。

图10 为网络剩余能量随时间变化图。在网络运行初期，NCDH 算法的剩余能量低于MRDC 算法，这是因为在网络运行初期划分网络区域以及选举簇头和副簇头时消耗了部分能量传递初始化消息，但是随着运行时间的增加，网络剩余能量明显高于其他3 种算法。在第701 轮时，NCDH 算法的剩余能量下降加快，这是因为网络中簇头节点的状态触发了副簇头的启用条件，导致副簇头与簇头节点、中转簇头通信消耗了部分能量。由于采用了不均等分簇的方法，GURCP 算法与NCDH 算法的剩余能量随着时间的增加下降缓慢。同时，随着网络运行时间的增加，网络中生存节点逐步减少，导致转发数据量减少，在网络运行后期，4 种算法的剩余能量减少变缓。这表明NCDH 算法可以有效延长网络生存时间。

图10 网络剩余能量与时间的关系Fig.10 Relationship between the network residual energy and time

4.2.4 网络吞吐量

图11 为在网络的生存周期内，基站接收到数据包的变化情况。NCDH 算法的网络吞吐量分别是DEEC、MRDC、GURCP 算法的1.64 倍、1.36倍和1.08 倍。DEEC 算法的网络吞吐量在生命周期内最小。MRDC 算法与GURCP 算法的网络吞吐量相差较大，这是因为GURCP 算法采用了不均等分簇使网络的生命周期有所增加，而MRDC 算法虽然采用双簇头的方案减少了簇头的能耗，但是副簇头一直存在，增加了网络整体的能耗，使网络的生命周期有所下降。NCDH 算法在网络初期进行网络区域划分，副簇头只有在满足一定条件下才启用，并且在不同区域副簇头的启用时间也可能不同，进而延长了网络的生存时间，提升了网络的整体吞吐量。

图11 网络吞吐量与时间的关系Fig.11 Relationship between the network throughput and time

5 结束语

针对无线传感器网络簇头间能耗不均衡导致的“热区”问题，本文提出一种基于双簇头的非均匀分簇路由算法，在路由初始化阶段将网络划分为若干子区域，在双簇头选择阶段综合考虑节点的剩余能量、节点到基站的距离、节点度等因素，优化网络中簇头的选择。根据簇头所在区域不同赋予簇头不同的竞争半径，使各簇头的能耗更加均衡。在网络运行阶段，簇头根据自身情况决定是否启用副簇头，缓解簇头节点的压力。实验结果表明，该算法能有效均衡网络能耗，解决网络“热区”问题，延长网络的生存时间。下一步将考虑在真实场景（如隧道、矿井巷道等）中部署传感器网络，并探究实际场景中的干扰因素对路由算法的影响。