基于动态分区的无线传感器网络非均匀成簇路由协议

孙彦清，彭舰，刘唐,2，陈晓海

（1. 四川大学 计算机学院，四川 成都 610065；2. 四川师范大学 基础教学学院，四川 成都 610068）

1 引言

无线传感器网络是由部署在农田、森林、战场等监测区域内大量廉价的微型传感器节点和一个信息收集基站（sink）组成，通过无线通信的方式形成一个多跳的自组织分布式网络系统。作为一种新的信息获取方式和处理模式，被广泛应用于军事国防、环境监测、智能家居、医疗卫生等领域[1]。

传感器节点一般采用能量十分有限的电池，通常运行在恶劣甚至危险的偏远环境中，一旦部署就不能再充电和电源更换，因此如何设计有效的策略控制节点的能量消耗成为传感器网络研究的核心问题[2]。为了达到节省能耗的目的，许多基于成簇的层次型网络拓扑结构被提出[3~5]。分簇优化了数据的传输数量，减少了节点对基站的数据发送次数，能够有效减少网络冗余信息，降低能量消耗，延长网络的生命周期。

早期的成簇路由算法大多采用单跳通信方式（簇头节点收集簇内成员节点的数据，进行压缩、融合后直接和基站通信，如LEACH[6]），但存在网络部署面积受限、扩展性差、离基站越远的簇头能量消耗越快等缺陷。随着研究的深入，分簇网络采取多跳方式来节省能量，但也存在严重缺陷：距离基站越近的簇头需要转发的数据任务越多，消耗的能量越多，越容易因能量耗尽而过早失效。如果靠近基站的节点成块死亡，则会导致网络中数据无法成功传输，网络寿命降低。因此，如何均衡簇间能量消耗，达到网络节点的负载均衡是成簇路由协议的研究热点。

LEACH是最早提出的一种均匀分簇路由协议，通过周期性地等概率随机选择簇头来构造出大小相等的簇，在理论上达到了簇内能耗平衡，但这种局部能耗均衡会造成远离基站的簇头能量先耗尽，从而造成了能量空洞。EEDRCP[7]是对LEACH改进的一种双轮成簇协议，在簇头选取算法中引入剩余能量参数，形成混合型网络拓扑结构。

EEUC[8]通过控制簇头的竞争半径来调节簇规模大小，使得靠近基站的簇规模相对较小，这样簇头因收集簇内数据而消耗的能量就会相对减少，从而簇头就会拥有更多的能量来进行路由转发；同时在选择路由节点时，不仅考虑候选路由与基站的距离，还参考其剩余能量，这种非均匀成簇路由协议在一定程度上缓解了簇头能量消耗不均衡的问题。ACOUC[9]在 EEUC 的非均匀分簇协议的基础上对算法进行了优化，首轮所有节点参与簇头竞选、后续轮簇内调整，利用基于定向扩散的蚁群优化(ARAWSN)算法进行路径优化和动态路由调整，以建立从簇首到汇聚点综合能耗最小的多跳路由。

CEB-UC[10]是一种基于分区能耗均衡的非均匀分簇算法，将网络合理分区，使得靠近基站的分区内的簇数量较多，各簇内节点数目较少；远离基站的分区内的簇数量较少，各簇内的节点数目较多，从而保证承担数据中继转发任务的簇头节点能节约所在簇内的通信开销，供簇间数据转发使用，以优化网络各节点的能量消耗。DEBUC[10]采用基于时间的簇头竞争算法，广播时间取决于候选簇头的剩余能量和其邻居节点的剩余能量；同时，通过控制候选簇头的竞争范围，使得距离基站较近的簇的几何尺寸较小，以均衡网络中不同位置节点之间的簇内和簇间通信能耗；DEBUC采用簇间多跳路由，运用贪婪算法选择其中继节点，有效地延长了网络寿命。

本文提出了一种基于动态分区负载均衡的分布式成簇路由算法。首先利用动态非均匀分区保证网络各个区域的能耗均衡性，使得距离基站较近的区具有较小的几何尺寸；根据节点的历史能耗因子和到基站的距离竞选区头，使得剩余能量较高并且靠近基站的节点当选区头。然后综合考虑节点的剩余能量因子和“综合距离因子”进行区内成簇，使得剩余能量越多并且越靠近区头的节点出任簇头的概率越大。采用簇内单跳通信、簇头与区头直接通信和区间多跳的路由策略，簇头只负责收集簇内数据并进行融合，区头负责收集簇头数据并根据转发策略选择中继节点。这种区头和簇首共同承担数据传输的通信方式有效节省了单个节点的能量、均衡了网络能耗，实验结果表明，与LEACH、 EEUC和DEBUC协议相比，所提协议能够显著延长网络的生存周期。

2 网络与能耗模型

2.1 网络模型

[11]，本文对无线传感器网络作如下假设：

1) 节点能量可异构，网络中初始总能量 Etotal固定，节点可以获取自身的当前能量Er；

2) 每个节点有唯一的 ID，可获知自己的坐标信息。都能担任区头、簇头或者普通节点；

3) 节点通信功率可以自由调节，不同节点能够在通信范围内相互通信，通过接收信号的强度计算出通信节点之间的距离；

4) 每个节点独立工作，即每个节点的工作均不受其他节点影响；

5) 通过数据融合技术减少数据传输任务；

6) sink节点具有较强的计算、存储能力，且能量无限制。

2.2 能耗模型

本文采用简单能量消耗模型[5]，忽略节点在计算、存储等过程中的能量消耗，仅计算通信能耗。在传输l bit信息经过距离d的过程中，发送端能量消耗为

接收端的能量消耗为

其中，d0为一阈值，本文定义为 87 m。若发送节点与接收节点的传输距离小于 d0，发送方发送数据的能量消耗与距离的平方成正比，否则成4次方正比。Eelec是每比特数据在发送电路和接收电路消耗的能量，εfsd2和εmpd4是发送每比特数据放大器的能量消耗。

2.3 数据融合模型

UCDP通过数据融合技术减少网络传输的数据量，达到节约网络能量的目的。由于不同区域中数据有较大的差异，在模拟实验中不考虑区域间的数据融合。假设区内的数据融合模型为：簇头接收每个节点发送的l bit数据，压缩为l bit数据；区头接收每个簇头发送的l bit数据，压缩为l bit数据。数据融合能耗设定为DEΛ=5 nJ/bit。

3 基于动态分区的非均匀成簇（UCDP）路由协议

UCDP是一个分布式的并行成簇算法，具有良好的扩充性，算法采用轮循环机制，每轮分为3个阶段。1）动态分区阶段：首先通过节点历史能耗因子和与距离基站的距离对网络进行动态非均匀分区，使得剩余能量较高的节点当选区头并且距离基站较近的区域面积较小。2）区内成簇阶段：每个区内进行非均匀成簇，区内节点综合考虑自身与区头的距离以及自身与基站的距离计算出“复合距离因子”，保证节点的数据传输距离最优；同时参考节点的剩余能量因子来竞选簇头；既避免了能量消耗过低的节点担任簇头，又最大限度地降低了簇头的通信传输能耗。3）路由转发阶段[12]：分为簇内通信、簇首与区头通信、区头与汇聚点通信三部分，簇内通信采用单跳的方式，容易实施；同一个区内的所有簇首都采用单跳的方式与所属区头通信，只有和基站距离小于一定范围的簇首才将数据直接发送给基站；区头根据能量消耗因子建立区间多跳路由。

下面给出与UCDP算法相关的一些定义。

定义 1 能量消耗因子。能量消耗因子e _ cos tkr表明在第r-1轮工作周期内节点k所消耗的能量与区域内节点平均消耗能量的比值，

定义2 剩余能量因子。剩余能量因子 W (Ekr)表明节点此时的剩余能量和区域平均剩余能量的关系，

定义3 复合距离因子。复合距离因子D(v)表明节点此时的位置与汇聚点和区头的关系，0≤D(v)≤ 1。

3.1 动态分区

UCDP算法在每轮数据传输周期之前首先对网络进行合理的动态非均匀分区，有效均衡网络的整体负载。在UCDP中，区头的任务负担较重，不仅需要管理区内多个簇头，还要融合各个簇头收集的数据，再将处理后的数据发送给基站，因此算法以区域内节点的历史能耗因子为主要的竞选依据。所有参与区头竞争的候选区头节点都保存一张邻居节点信息表，如表1所示。

表1 候选区头邻居节点信息

首先，每个候选区头节点广播 Area_Vie_Msg报文，告知其他候选节点自身的 ID号、当前剩余能量Er和竞争范围Rvie，通过广播能够获知其他邻居节点的信息集合。

结合Younis提出的成簇思想[9]，在UCDP算法中对LEACH算法的T(n)公式做出改进

其中，PRH是节点竞选区头的概率，r是当前循环进行的轮数，G为最近1/Pk轮中未成为区头的节点集合。在 T(n)中加入 e _ costkr作为影响因子，使历史能耗较低的节点优先当选区头。新的阈值公式T(n)new有如下特性：1)当选过候选区头的节点在接下来的 1/Pk轮循环中将不能成为区头；2)未当选过候选区头的剩余节点当选为区头的概率增大；3)未成为区头的其他节点根据接收到广播信号的强弱来决定加入合适的分区。这样，通过T(n)new能够实现对传感器网络进行动态定向分割的目的。

假设传感器网络被分隔成M个区域，设在第r-1轮，对任意分区的集合中有个节点。其中，传感器节点在此轮数据传输开始时的能量为 Ekr-2，在第r -1轮成簇结束时能量为 Ekr-1。由定义1给出节点k的能量消耗因子为

为了有效保证网络每轮分割过程中各个分区能耗的均衡性，算法引入了轮转因子的概念：

当 r ounds(k,r)>0时，则节点k提前 r ounds(k,r)轮进入集合 G；当 r ounds(k,r)=0时，则当前轮转状态不变；当 r ounds(k,r)<0时，则该节点延迟rounds(k,r)轮进入集合G。

由于距离基站越近的区头需要承担的数据传输任务越重，能量耗尽而失效的概率也越大。为了避免这种现象，算法希望让靠近基站的区头的成员较少，减少区头因处理区内数据而消耗的能量。算法为每个候选区头设置一个竞争半径Rvie，随着候选区头到基站距离的减小，Rvie随之减小。假设候选区头的最大竞争半径为 Ro，则候选区头 i的 Rvie为

其中，dmax代表网络中节点到基站的最大距离，dmin代表最小距离，d(I, BS) 是节点i 到基站的距离，c是0~1之间的用于控制Rvie取值范围的常数。

当选为区头的节点向邻居节点广播获胜消息Area_Msg时，申明自己成为区头，并默认区头为区号，普通节点选择接收信号强度最大的区头并发送Join_Area_Msg请求加入，每轮分区后区头节点负责对本区节点信息的更新管理，网络动态分区结束。利用轮转因子的概念，通过引入剩余能量因子改进 T (n)new阈值，能够对节点担任区头的轮转周期进行动态调整，有效地保证了传感器网络每轮分割过程中各个分区能耗的均衡性。

3.2 区内非均匀成簇

区内成簇阶段包括簇头选举和簇的形成。

1) 簇头选举

为实现网络中节点的负载均衡，要尽可能增加分区内相对剩余能量较高的节点出任簇头的概率。首先，每个候选簇头广播Cluster_Vie_Msg报文，告知其他候选节点自身的 ID号、当前剩余能量、节点与区头的距离和节点与基站的距离。根据定义2，节点k在第r轮成簇之前的剩余能量因子 W (Ekr)计算公式为

其中，传感器节点 k的初始能量为 Ek0，当r =1（首轮）时，节点k还没有任何能量损耗，W (Ekr)为1；当r>1时， W (Ekr)越大，说明该节点在此时的相对剩余能量越高。 W (Ekr)还可以适用于初始能量不同的异构网络，如果此时有2个节点的当前剩余能量值相等，则意味着初始能量高的节点能量消耗更快，那么初始能量高的节点的剩余能量因子会较小。

节点k到区头RHi的距离越小，则k作为簇头后，簇头与区头之间的通信能耗越小，同理若k到基站的距离越小，数据传输的能耗也越小。根据自由空间能量模型可知，距离的平方直接影响能量消耗的大小，根据定义 3，给出复合距离因子可以表示为

为了实现分区内节点的负载均衡，要尽可能增加相对剩余能量大的节点出任簇头的概率；同时加入综合距离因子使得簇头尽量靠近区头和基站，尽量减少数据传输消耗的能量。

节点k成为簇头的概率由式(9)计算。

其中，α、β为调节剩余能量因子、综合距离因子在节点竞争簇头时所占权重的概率因子，且α+β=1。

利用式（9），节点 k和它的邻居节点分别计算出自身的簇头当选概率，并通过一次握手交换出对方的概率值。邻居节点在收到的所有概率值中挑选出拥有最大概率值的节点成为簇头，并通知相应的节点（若没有得到更大的概率值信息，则该节点宣告自己成为簇头）。选举结束后，当选簇头向其通信范围内的成员发送Head_Msg报文，宣布成为簇头。

2) 簇的形成

簇头确定之后，便在所属分区内广播 Cluster_Msg报文，等待其他普通节点的加入。普通节点根据接收消息的信号强弱判断发送方和接收方的距离，优先选择通信代价最小的簇头加入，即发送消息需要经过的距离最短的簇头。

普通节点i根据距离引力[13]F(i，CHi，r)来确定加入哪个簇，CHi为簇头，距离引力表示节点不仅考虑簇头的剩余能量大小，同时还要考虑与簇头的距离和与区头的距离。

从图1中可以看出，越是靠近基站的区，其物理面积越小；分区内的簇头相对靠近区头和基站。簇形成阶段之后，算法进入数据通信阶段—路由传输。

图1 UCDP协议基本原理

3.3 路由传输

UCDP采用簇内单跳通信、簇头与区头直接通信和区间多跳通信的数据传输方式。

簇头首先收集簇成员的数据并进行融合，然后进行数据发送，比较由簇头直接发送到基站的距离和由区头转发到基站的距离，选择综合距离较短的方式进行发送。如果簇头CHi满足，数据由簇头直接发送给基站；满足就由簇头交给区头发送。其中，d(CHi, BS)表示簇头CHi与基站的距离，d(RHm, BS)表示区头RHm与基站的距离，DTD-MAX为阈值。

区头到基站的距离小于 DTD-MAX，则它可以直接发送数据到基站，否则区头只能以多跳通信的方式将数据发送至基站。下面通过定理1来讨论区头的路由转发策略。

首先给出区头RHm的路由候选集合为

定理1 对剩余能量为Ecur_m的区头i，共有Z′个路由候选区头，假设其中的任意区头z的剩余能量为Ecur_z，由z到基站的消息发送距离dz_o与节点i的当前距离为dm_z可知，如果区头z满足

则区头m通过z转发数据到基站将比区头m直接发送消息到基站更节省网络能量。

证明 设区头m为了传输l bit的数据，根据文献[7]的能量模型，所需要的能量消耗为

设区头m有Z′个路由候选区头，若m通过其中的候选区头z传输消息j到基站，则能量消耗分为三部分：两区头发送消息所消耗的能量、区头 z接收消息所消耗的能量以及消息j再从z发送到基站的能量消耗。其中，消息j从m发送到z的能量消耗为

消息j再从区头z发送到基站的能量消耗为

因此，通过区头z转发消息j的总能量消耗为

若Em_z(l)占区头i和区头z剩余能量之和的比例小于ETx_mo(l，di_o)占区头m当前剩余能量的比例，即满足式(14)，则消息l通过转发的方式传至基站，更节省网络能量。

结论得证。

为了简化问题分析，简单假设能量消耗与距离的平方成正比，则Em_z(l)可以表示为

由分析可知，dm_z2+dz_o2决定了能量消耗的多少，则在选择转发节点时，优先选择dm_z2+dz_o2最小的区头作为下一跳路由节点。

路由算法伪代码如图2所示。

图2 路由算法伪代码

动态非均匀分区保证了网络各个分区的能耗均衡性；基于综合距离因子和剩余能量因子的成簇算法保证了簇头的通信距离最小化，并提高了剩余能量多的节点出任簇头的概率，因此，UCDP算法能够实现网络负载均衡性和能量有效性。

4 算法分析

定理2 在UCDP算法中，网络中广播的消息量复杂度为O(N)。

证明 在UCDP算法中，在区头竞选阶段，有NR个候选区头参与竞选，共广播NR条Area_Vie_Msg消息，竞选成功的候选区头发送获胜消息，假

其中，dm_z为m与z的距离。区头z接收消息所消耗的能量为设共有R个区头，则一共广播R条Area_Msg消息，而其他的区成员发送N-R条Join_Area_Msg消息；有NC个候选簇头参与竞选，共广播NC条Cluster_Vie_Msg消息，竞选成功的候选簇头发送获胜消息，假设共有C个簇头，则一共广播C条Cluster_Msg消息，而其他的簇成员发送N-C-R条Join_Cluster_Msg消息。因此，网络在分区阶段和成簇阶段中总的消息开销为

NR+R+N-R+NC+C+N-R-C=(R+C-2)N-R (19)所以，UCDP算法的消息量复杂度为O(N)。

5 仿真与实验

为了评估算法的性能，利用NS-2在相同条件下仿真LEACH、EEUC、DEBUC和本文算法，并进行多项性能的比较。

5.1 仿真环境

本文使用NS-2进行仿真模拟，实验环境如下：1 600个传感器节点随机分布于400 m×400 m的正方形区域，假设汇聚节点（sink）位于区域中心。表2展示了实验采用的多种参数。

表2 网络参数

5.2 簇首特征

根据前面的分析可知，算法的分区个数由参数 Ro和c共同决定。图2显示了当c取2个不同vie的值时，区头数目和 Rovie之间的关系。从图 3可以看出，c=0.5时的区头数目要多于c=0时的区头数目，同时随着区头竞争半径的减小，分区数目不断增多。

图3 区头数目和最大竞争半径关系

图4 说明了算法的稳定性，在网络拓扑固定的情况下，衡量一个分簇协议是否稳定的标准是看生成的簇首数目是否一致。分别从 LEACH算法、DEBUC算法和UCDP算法的模拟过程中随机选出100轮，统计每个协议簇首个数的分布情况，由图4可知，LEACH算法的簇首数目变化最大，这是因为LEACH算法只采用了随机数和阈值的机制竞选簇首，因此簇首数目的波动范围最大。由于DEBUC算法和本文算法都采用了局部竞争的方法，因此DEBUC算法的簇首数目相对集中，本文算法的区头数目和簇首数目也相对集中。值得注意的是，本文算法生成的簇首数目明显较多，这是因为UCDP算法通过动态划分大小非均匀的区，使得靠近基站的地方产生更多几何尺寸较小的区，再通过区内成簇，簇首个数就相对增多。总之，UCDP算法生成了数目稳定的分区和簇首，具有良好的可靠性。

5.3 生存周期

UCDP算法的核心思想是通过动态分区来均衡网络能耗，现在通过比较4种协议的网络生存时间来验证本文算法的有效性。文献[14]定义网络节点死亡 10%以上时为网络失效，从图 5可以看出，UCDP算法相对于其他3种算法有较长的网络生存时间，由于本文算法采用区头与簇首共同协作的通信方式，减缓了每个节点的任务负担，均衡了网络的整体能耗，因此，UCDP算法的第一个节点死亡时间和网络失效时间都明显晚于其他3种协议。

5.4 能量效率

图6对比了4种协议的网络总能耗随时间变化的情况。从图中可以看出，UCDP算法的能量消耗速度明显小于其他3种协议，当DEBUC算法中网络失效时，此时网络能量为61 J，而UCDP算法网络失效时，网络剩余能量仅为17 J。说明UCDP算法有更长的网络存活时间，能够有效平衡节点间的能耗，具有更好的网络监控质量。

图4 簇头数量分布

图5 存活节点与生存周期关系

图6 网络剩余能量与生存周期关系

图7 显示了4种协议的网络节点平均能量值随时间变化的情况，UCDP算法的网络节点能量均值一直都比其他3种协议的高，说明UCDP算法在能量均衡方面有较好的性能。

图7 节点平均剩余能量与生存周期关系

6 结束语

本文提出了一种新颖的基于动态分区的传感器网络成簇路由协议，核心思想是利用一个能量均衡的非均匀分区算法将网络合理分区，以缓解多跳路由中的“热区”现象；协议利用区头与簇头共同协作的通信方式，以均衡网络中节点的能量消耗；通过簇内通信、区内通信和区间转发的有机结合，建立了一个能耗最优的路由传输协议。实验结果表明，所提算法具有较好的稳定性，能够有效节省单个节点的能量、均衡网络能耗，显著延长网络的存活时间。

虽然本文算法在实验中表现了良好的性能优势，但实际环境中移动节点、异构网络和机会网络的应用越来越广泛，为了更好地适应传感器网络的发展，下一步的工作是根据算法在不同的网络环境下的需要做出改进，使其更适应于实际场合。

参考文献：

[1] 张晓玲, 梁炜, 于海斌等. 无线传感器网络传输调度方法综述[J].通信学报,2012,33(5): 143-157.ZHANG X L, LIANG W, YU H B, et al. Survey of transmission scheduling methods in wireless sensor networks[J]. Journal on Communications, 2012, 33(5): 143-157.

[2] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[3] ABBASI A A, YOUNIS M. A survey on clustering algorithms for wireless sensor networks[J]. Computer Communications, 2007, 30(14-15):2826-2841.

[4] HUANG W W, PENG Y K, WEN J, et al. Energy-efficient mhop hier ar chical routing protocol for wireless sensor netwoks[J]. IEEE Computer Society, 2009, 35( 2): 469- 472.

[5] LI B, WANG W J, YIN Q Y, et al. An energy-efficient geographic routing based on cooperative transmission in wireless sensor networks[J]. Sci China Inf Sci, 2013, 56: 4757-4762.

[6] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communications,2002,1(4): 660-670.

[7] 陈庆章, 赵小敏, 陈晓莹. 提高无线传感器网络能效的双轮成簇协议设计[J]. 软件学报,2010, 21(11): 2933-2943.CHEN Q Z, ZHAO X M, CHEN X Y. Design of double rounds clustering protocol for improving energy efficient in wireless[J]. Journal of Software, 2010, 21(11):2933-2943.

[8] LI C F, YE M, CHEN G H, et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[A]. Proc of the IEEE Int’l Conf on Mobile Ad Hoc and Sensor Systems[C].Washington, DC, USA, 2005. 597-604.

[9] ZHANG R B, CAO J F. Uneven clustering routing algorithm for wireless sensor networks based on ant colony optimization[J]. Journal of Xi’an Jiaotong University, 2010, 44(6):33-38.

[10] WANG Y, ZHANG D Y, LIANG T T. Cell energy balanced uneven clustering hierarchy scheme for wireless sensor networks[J]. Journal of Xi’an Jiaotong University, 2008, 42(4):389-394.

[11] 蒋畅江, 石为人, 唐贤伦等. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报, 2012, 23(5):190-200.JIANG C J, SHI W R, TANG X L, et al. Energy-balanced unequal clustering routing protocol for wireless sensor networks[J]. Journal of Software,2012,23(5):190-200.

[12] 刘唐, 彭舰, 杨进. 异构延迟容忍移动传感器网络中基于转发概率的数据传输[J]. 软件学报, 2013, 24(2):215-229.LIU T, PENG J, YANG J. Data delivery for heterogeneous delay tolerant mobile sensor networks based on forwarding probability[J].Journal of Software, 2013, 24(2):215-229.

[13] 洪榛, 俞立, 张贵军. 多级异构无线传感器网高效动态聚簇策略研究[J].自动化学报, 2013, 39(4):454-460.HONG Z, YU L, ZHANG G J. Efficient and dynamic clustering scheme for heterogeneous multi-level wireless sensor networks[J].Acta Automatica Sinica,2013,39(4):454-460.

[14] 卿利, 朱清新, 王明文. 异构传感器网络的分布式能量有效成簇算法[J]. 软件学报,2006,17(3): 481-489.QING L, ZHU Q X, WANG M W. A distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J].Journal of Software, 2006, 17(3): 481-489.