基于簇头分级的改进非均匀分簇算法*

康 琳，董增寿

（太原科技大学电子信息工程学院，太原030024）

无线传感器网络被越来越多地应用于森林火灾监控、战场状况检测、动物行为监控等领域。在这些应用中，采用电池供电的传感器节点被随机地部署在无人到达的恶劣环境中，节点的再供电几乎是不可能的，在能量受限的传感网络中，设计能量有效的路由策略以延长网络的生存时间成为亟待解决的问题。

传感器网络中节点之间常形成簇状的分层拓扑，被选中的簇头节点CH（Cluster Head）将成员节点CM（Cluster Member）收集的数据包聚合为单一数据，并通过直接通信或CH中继，将数据传输至汇聚节点（Sink）［1-2］，CH的数据聚合及CH之间的多跳中继减少了网络中冗余数据传输的能耗，因此，网络的生存时间得以延长［3-4］。

但是，在成簇网络中，距离sink节点较近的CH由于承担过重的簇间中继转发任务，会过早的耗尽能量而形成“热点”，引发网络的不连通。文献［5］设计了能量有效的非均匀成簇算法EEUC（Energy Efficient Unequal Clustering），首次提出了竞争半径的概念，以CH的可变竞争半径来调节簇的大小，使距离sink节点较近的CH拥有较小的簇，而较远的CH形成较大的簇，以均衡CH消耗在簇内以及簇间中继的能量，解决热点问题，但是，算法的簇头选举过程耗能较多。文献［6］通过优化非均匀簇的大小及簇头轮换均衡了网络能耗。特别地，对于节点分布均匀的传感器网络，文献［7］设计了一种非均匀成簇策略（UCA）来均衡节点簇内及簇间的能耗，延长网络生存时间。文献［8］将备选CH的剩余能量、与sink节点的距离以及备选CH的度数作为模糊量，利用模糊算法选取了最佳CH以及竞争半径。文献［9］则基于PSO优化算法为非均匀簇选取了最优的双簇头。文献［10］利用节点的剩余能量、节点到sink节点的距离、节点的邻居节点数以及节点到簇头的距离来优化非均匀簇的簇头选择。文献［11］采用混合蛙跳算法优化了簇头选择；文献［12］利用对节点选票及传输距离的加权，优化了非均匀簇的簇头选取。文献［13］则利用动态分簇及基于节点休眠/唤醒机制改进了非均匀簇的簇间路由。文献［14］基于网络的动态分区产生的区头以及非均匀簇的簇头构造了最优的簇间协作路由均衡网络能耗。

虽然各类的非均匀成簇算法均通过选择最佳CH、竞争半径及簇间路由均衡了传感器网络中的能耗分布，解决了热点问题。但是，在传感器网络每一轮数据传输开始时，即使当前CH还有足够的能量完成数据传输，CH都会得到轮换，而在新CH的竞争选取过程中，竞争CH的节点需要向整个网络广播自身的ID号、剩余能量、感知半径、到sink节点的距离，用以形成以自身为CH的新的簇内通信以及簇间路由。频繁的CH轮换会引发过多的广播能量开销，进而缩短网络的生存时间。

针对频繁的簇头轮换对网络生存时间的影响，本文提出了一种基于簇头分级的改进的非均匀成簇算法 CHCI（CH Classified Improved Unequal Clus⁃tering），来降低网络中过多的广播能量开销。在一个簇内，设置主要簇头节点（PrimaryCH）以及次要簇头节点（Secondary CH），PCH完成簇内数据的聚合，SCH承担簇间数据转发任务，为PCH设置CH轮换阈值，只有当前PCH的剩余能量低于CH重选阈值时，才会启动CH轮换过程，并将簇间中继路由的选择转化为二次规划问题，选择了能耗最低的簇间通信路由，延长网络的生存时间。

本文第1部分对系统模型及场景进行了描述。第2部分具体介绍CHCI算法。第3部分通过仿真对比了本算法与经典的LEACH以及经典的EEUC算法性能的比较，最后，第4部分总结全文。

1 系统模型

假设N个传感器节点随机分布在M×M区域内，Sink节点处于M×M区域之外，其他基本假设如下：①Sink节点位置信息已知。②所有随机分布的节点皆为静态节点。③每一个节点有独立的ID号和相同的初始能量Eo。④节点没有配置GPS，但是在网络初始化阶段，节点可以根据RSSI值计算自身与sink节点的距离。⑤节点可以根据自身与Sink节点的距离调整传输半径。

节点无线传输的能耗模型采用一阶无线电模型［15］。将每l比特数据传输d所需要的能耗表示如下：

接收此l比特数据的能耗为：

式中：ETx表示发射节点能耗，ERx表示接收节点能耗，Eelec表示每发送或接收1比特数据电路消耗的能耗。l代表传输数据的长度。ξfs及ξmp分别表示传感器节点中放大器在自由空间以及多径衰落模型下的能耗系数。当d＜d0时，选用电波传输的自由空间模型，当d≥d0时采用多径衰落模型，阈值d0表示如下：

2 CHCI算法

CHCI算法的数据传输主要分为：PCH选取，簇内通信建立，SCH选择，簇间中继选择4个阶段。以下先说明本算法的簇头分级模型。

2.1 簇头分级模型

在网络初始化阶段，Sink向区域内所有节点广播“hello”数据包，每一个节点根据RSSI值确定自身距离sink节点的距离dtosink。而后，为了节省能量，我们将以随机概率μ处于工作状态的节点根据概率阈值P分为两类：活跃节点及睡眠节点，如表1所示。

表1 节点工作状态区分

当节点成为活跃节点后，加入活跃节点集，并向节点集中的其余节点广播包含自身ID号、剩余能量、当前感知半径信息的HEAD_MSG数据包，参与簇头节点的竞争。参与竞争节点的当前感知半径被定义为竞争半径，用下式表示：

式中，d（i，Sink）表示任意节点i与 sink之间的距离。dmax及dmin分别表示所有dtosink数值中的最大以及最小值。c被定义为半径控制因子，Rini为所有节点在网络初始化时的半径。而后，在活跃节点集中，拥有最高剩余能量的节点j当选为PCH，向其余节点发送CONFIRM_CH_MSG数据包以确认自身的PCH身份，没有当选为PCH的节点向其周围的CH节点发送JOIN_MSG数据包以确认自己加入此PCH，成为其成员节点。对于睡眠节点，当其接收到当选PCH广播的CONFIRM_CH_MSG信息后，变为激活节点，向邻近PCH节点发送JOIN_MSG信息，当PCH为其分配数据传输时隙后，这些节点会接收到ACK_MSG以确认自身已成为该PCH的成员节点。此后，PCH根据竞争半径RTH(j)获得簇的成员数kin，PCH为kin个成员节点分配TDMA时隙表，来完成簇内节点信息的汇聚，成员节点只在被分配的时隙内完成数据传输，在其他节点传输数据时则进入睡眠状态，以减少数据包碰撞来减少网络的能耗。假定当前轮t内，每个成员节点传输l比特数据，则簇内数据收集完成后，PCH的剩余能量为

则当前轮t网络的平均剩余能量定义为

定义第t轮SCH节点的选举因子p(k)为

显然，我们选择p(k)较高的节点作为SCH，将接收到的来自PCH的数据传输至Sink节点。其余节点作为成员节点将数据传输至PCH。

2.2 SCH-sink的中继路由选择

当SCHk从PCH接收到聚合的数据后，会广播一个包含自身ID号、剩余能量、以及dtosink的STATE_MSG信息给其余SCH，而后节点k根据表2选取直接单跳通信或借助其余SCH的多跳通信以完成簇间中继，将信息传输至Sink节点。

表2 中继选择方案

TDmax是判定SCHk采用单跳或多跳通信方式的阈值。

图1 能量有效路由的中继节点选择示意图

如图1，当SCHk通过邻近sink的节点m作为中继节点时，数据传输时耗费的能量可以表示为：

为了减少能耗，SCHk需选择一条经过中继节点m∗的能量有效的路由，节点m∗可通过以下方式选择：

式中，Ω(k)表示SCHk的一跳邻居节点集。

2.3 PCH重选因子

在数据传输阶段，当第t（t≥1）轮数据传输结束后，引入PCH重选因子T（t+1）来降低PCH轮换的频率，T（t+1）可表示为：

表3 CHCI算法中的数据传输

3 仿真与分析

3.1 算法的消息复杂度

假定传感器网络中共有N个节点，在执行CHCI算法网络初始化时，Sink节点向N个节点广播“hel⁃lo”数据包，N×P个节点被选为激活节点参与簇头竞争，会广播N×P条HEAD_MSG信息，若M个节点竞选PCH成功，会发送M条CONFIRM_CH_MSG信息，其余N-M个节点收到CONFIRM_CH_MSG信息后，向PCH发送JOIN_MSG信息，M个PCH发送NM个ACK_MSG信息以确认加入节点被分配了时隙。簇内通信的消息复杂度为O（N）。簇间路由建立时，M个SCH在网络内产生M条STATE_MSG信息，计算最佳路由时，消息复杂度为O（M）。

若T（t+1）=1，PCH不得到更换，则网络中不需要重复簇内通信的建立过程，只需要SCH建立簇间路由，此时算法的消息负杂度为O（M），若T（t+1）=0，PCH更换，网络重新进行簇内及簇间通信的建立，由于N≫M，算法的消息复杂度为O（N）。

3.2 仿真参数设置

假设400个节点随机分布200 m×200 m的区域内。主要仿真参数参考表4。

本部分通过仿真分析了参数c，Rini，a，TDmax对网络性能的影响，然后比较了CHCI协议与经典的LEACH算法以及非均匀成簇的EEUC算法对网络生存时间以及节点平均剩余能量的影响。

表4 仿真参数

3.3 仿真结果及分析

图2显示了参数c对于首个死亡节点出现轮数的影响，对于一个确定的初始竞争半径Rini，c增大时，竞争簇头的节点的竞争半径减小，网络中会出现更多的簇，消耗在簇间中继通信上的能量增大，相应地会缩短网络生存时间，从图2中可以看到，当c=0.6时，网络中的簇的数量可以均衡簇内及簇间能耗，从而延迟首个死亡节点出现的轮数。

图3显示了Rini对首个死亡节点出现轮数的影响，当Rini增大时，网络中簇的尺寸增大，引起PCH用于簇内汇聚的能耗增大，当Rini=30 m时，簇内及簇间中继通信的能耗得到均衡，首个死亡节点出现的轮数出现在850轮，延长了网络生存时间。

图2 参数c对网络性能的影响

图3 参数Rini对网络性能的影响

图4显示了参数a对网络死亡节点的影响，当进行了600轮数据传输后，若a=0，即没有选取SCH时，大概60个节点死亡，当a=0.4时，由于SCH分担了PCH用于簇间中继的能耗，降低了PCH的能量损耗，从而降低了PCH轮换的频率，死亡节点的数量达到最少，SCH的引入降低了网络中死亡节点的数量，改善了网络的性能。

图5显示了TDmax对网络生存时间的影响，从表2可知，若TDmax较小簇间通信主要采用中继通信，若TDmax变大，簇间通信主要采用直接通信，当TDmax=140 m时，网络中有更多的节点存活。

图4 参数a对网络死亡节点的影响（r=600）

图5 参数TDmax对网络性能的影响

图6、图7分别比较了LEACH，EEUC，CHCI算法执行1200轮后，节点的平均剩余能量以及存活节点的数量，这里将一半节点死亡定义为网络生存时间的结束。LEACH算法在执行700轮后，一半节点死亡，采用了非均匀成簇的EEUC算法执行750轮后，一半节点死亡，网络不再连通。采用CHCI算法后，由于SCH的存在，节省了节点的能耗，增加了节点的平均剩余能量，从而降低了PCH轮换的频率，此外，簇间中继最佳路由的确定也降低了SCH的能耗，网络的总体能耗得到降低，生存时间被延长至900轮。生存时间比EEUC算法提高了20%。

图6 节点平均剩余能量比较

图7 存活节点比较

4 结论

本文设计了基于簇头分级的新的非均匀成簇算法CHCI。在主要簇头PCH当选后，每一个簇内会选出一个次要簇头节点SCH来承担簇间中继转发任务，以此降低PCH的能耗。PCH重选因子T（t+1）在每一轮数据传输结束时得到更新，只有在当前簇头的剩余能量低于PCH轮换阈值时，启动PCH的轮换，来降低网络中由于EEUC算法中CH频繁更换引起的额外的广播开销，延长网络的生存时间，并将SCH传输的中继选择问题通过二次规划问题得出能量有效的路由。仿真结果表明，与LEACH以及非均匀成簇的EEUC算法相比，CHCI算法延长了网络生存时间。

［1］Tian Q，Coyle E J.Optimal Distributed Detection in Clustered Wireless Sensor Networks：The Weighted Median［C］//INFO⁃COM，2006.

［2］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Effi⁃cient Communication Protocol for Wireless Microsensor Networks.In：Proc of the 33rd Hawaii Int’l Conf on System Science（HICSS 2000），2000：3005-3014.

［3］Engels D W，Sarma S E.The Reader Collision Problem.In：Proc of IEEE International Conference on Systems，Man and Cybernet⁃ics.SMC，2002.

［4］AbdelSalam H S，Olariu S.Bees：Bioinspired Backbone Selection in Wireless Sensor Networks［J］.Parallel and Distributed Sys⁃tems，IEEE Transactions on，2012，23（1）：44-51.

［5］李成法，陈贵海，叶懋，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30（1）：27-36.

［6］Xiang M，Shi W R，Jiang C J，et al.Energy Efficient Clustering Al⁃gorithm for Maximizing Lifetime of Wireless Sensor Networks［J］.AEU—Int’l Journal of Electronic and Communication，2010，64（4）：289-298.

［7］Yuan Huiyong，Liu Yongyi，Yu Jiaping.A New Energy-Efficient Unequal Clustering Algorithm for Wireless Sensor Networks［C］//IEEE Conference Proceedings，2011：431-434.

［8］Mao S，Zhao C，Zhou Z，et al.An Improved Fuzzy Unequal Clus⁃tering Algorithm for Wireless Sensor Network［J］.Mobile Net⁃works and Applications，2013，18（2）：206-214.

［9］门顺治，孙顺远，徐保国.基于PSO的无线传感器网络非均匀分簇双簇头路由算法［J］.传感技术学报，2014，27（9）：1281-1286.

［10］张文梅，廖福保.改进的无线传感器网络非均匀分簇路由算法［J］.传感技术学报，2015，5：21.

［11］刘洲洲，王福豹，张克旺.基于混合蛙跳算法的非均匀分簇WSNs路由协议［J］.计算机应用研究，2013，30（7）：2173-2176.

［12］张瑞华，贾智平，程合友.基于非均匀分簇和最小能耗的无线传感网络路由算法［J］.上海交通大学学报，2012，46（11）：1774-1778.

［13］彭铎，黎锁平，杨喜娟.一种能量高效的无线传感器网络非均匀分簇路由协议［J］.传感技术学报，2014，27（12）：1687-1691.

［14］孙彦清，彭舰，刘唐，等.基于动态分区的无线传感器网络非均匀成簇路由协议［J］.通信学报，2014，35（1）：198-206.

［15］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Effi⁃cient Communication Protocol for Wireless Microsensor Networks［C］//System Sciences，2000.Proceedings of the 33rd Annual Ha⁃waii International Conference on.IEEE，2000，（2）：10.