基于动态簇半径的非均匀分簇算法

熊 炼，叶建光，刘晓彤

(重庆邮电大学 通信工程应用新技术研究所，重庆400065)

基于动态簇半径的非均匀分簇算法

熊 炼，叶建光，刘晓彤

(重庆邮电大学 通信工程应用新技术研究所，重庆400065)

在无线传感器网络分簇路由算法中，针对节点能耗不均衡所引发的“热区”问题，提出了基于动态簇半径的非均匀分簇算法(UCDCR)。该算法在簇组建阶段，对网络进行区域划分，不同区域的候选簇首通过簇竞争半径来构建大小不同的簇，使簇首随网络的运行动态的改变簇竞争半径，为数据转发预留更多能量。仿真结果表明：与EEUC算法和CUCRA算法相比，UCDCR算法更加有效地均衡了节点能耗，延长了网络生命的周期。

无线传感器网络；动态；簇半径；非均匀分簇

0 引言

随着无线通信和微电子工艺的快速发展，无线传感器网络成为了国际上的研究热点。传感器节点能量有限，且不容易更换电池，如何减少节点的能量消耗，延长网络的生存时间成为无线传感器网络中的研究热点[1]。无线传感器网络的数据传输模式为多对一(many-to-one)模型[2-3]，但由于靠近Sink的传感器节点需要转发外层的数据[4-5]，这决定着网络中的负载必然会出现不平衡，产生“热区”问题[6]。

为了解决“热区”问题，Soro等[7]首次提出了非均匀分簇思想，主要是通过预设簇首为超级节点从而达到均衡网络负载的目的，但簇头位置是事先计算好的，无法动态建簇，适应性较弱。李成法等在文献[8]提出了EEUC算法，该算法采用了非均匀竞争半径分簇方法，在同一竞争区域内比较剩余能量多少，剩余能量多的节点当选簇首。算法在一定程度上缓解了“热区问题”，但如果簇半径保持不变，随着网络的运行，节点的剩余能量逐渐减少，维持原来的竞争半径，会过快地消耗簇首的能量，热区问题仍然存在。文献[9]对文献[8]的算法进行了改进，提出了CUCRA算法。CUCRA[9]也是采用竞争半径的思想选择簇首，并且考虑了节点的剩余能量因素，使节点的竞争半径随着节点的能量减少而变小。但随着算法的运行，竞争半径越来越小，导致簇首数增多，传输时延变长。本文在以上研究基础上，提出了基于动态簇半径的非均匀分簇算法(Uneven Clustering Algorithm Based on Dynamic Cluster Radius，UCDCR)。UCDCR算法创新之处：把网络区域划分为“热点区域”和“非热点区域”，定义不同区域簇半径，使不同区域的簇首合理利用能量，有效改善网络时延和能量均衡问题；对算法的路由进行了改进，均衡了网络的能耗，很好地解决了“热区”问题。

1 系统模型

1.1 网络模型

整个网络由一个汇聚节点和N个节点组成，并做如下假定：

① 网络中只有一个汇聚节点，其他节点随机分布在一个大小固定的区域。汇聚节点位于区域外面，且所有节点部署后不能移动；

② 所有节点具有相同的属性和功能，每一个节点都有一个唯一标识符；

③ 节点没有GPS功能去获取精确的位置信息；

④ 所有节点传输功率可控，节点可以根据距离动态地调整发射功率；

⑤ 链路是对称的，如果发射功率已知，节点根据接收信号的强度计算出发送者到自己的近似距离[10]。

1.2 能耗模型

本文主要采用与文献[11]相同的能耗模型。向距离为d的节点发送lbit数据的能量消耗如式(1)所示：

ETx(l,d)=ETx-elec(l)+ETx-amp(l,d)=

(1)

节点接收lbit数据的能耗如式(2)所示：

ERx(l,d)=l*Eelec，

(2)

2 UCDCR算法

针对网络中的“热区”和簇半径不能自适应调整的问题，UCDCR算法将从层次网络结构、成簇机制、多跳路由三个方面进行讨论。

2.1 层次网络结构

当传感器节点部署在感应区域后，基站在感应区内广播一条“hello”消息，把整个区域分成m个等宽区域，离基站最近的区域为定义为“热点区域”，其他区域定义为“非热点区域”[12]，同时定义区域数值随着远离基站而增大，即“热点区域”为1区域，以此类推，如图1所示。

图1 区域结构图

节点根据接收到的信号强度，计算出自身与基站之间的距离，决定了自身所在的区域。基站根据式(3)和式(4)计算每个区域的上下边界：

(3)

(4)

式中，UBi、LBi分别是第i个区域的上下边界，dmax、dmin分别是监控区域中节点到达基站的最大距离和最小距离。假设节点j距离基站的距离为dj，如果LBi

2.2 成簇机制

在成簇过程中，算法使用了基于距离和能量的竞争机制，每个节点在每轮开始时调整自己的竞争半径，随后网络进入簇头选举阶段。节点si的竞争半径如式(5)和式(6)所示。

“热点区域”的竞争半径Rcmp：

(5)

“非热点区域”竞争半径Rcmp：

(6)

因为簇首能耗消耗过快，UCDCR算法在2个簇之间的交汇部分选择中继节点来充当2簇首的数据转发的桥梁，减少簇首消耗。首先交汇节点向簇首发送成为中继节点的请求消息，簇首根据式(7)选择函数值较大的节点为中继节点：

(7)

式中，Erem为交汇节点的剩余能量，d为交汇节点和簇首之间的距离。

在选举开始时，设置一个额定值为T的概率阈值，随机数值(0～1)

图2 UCDCR分簇结构

UCDCR算法在分簇阶段的伪代码如下所示：

Foreverynodeinthenetwork

1.α←RAND(0,1)

2.Ifα

3.beTentativeHead←true

4.Endif

5.IfbeTentativeHead=truethen

6.BroadcastCOMPETE_HEAD_MSG

7.Endif

8.OnreceivingaCOMPETE_HEAD_MSGfromsj

10.Addsjtosi.SCH

11.End if

12.While beTentativeHead=true do

13.If∀sj∈si.SCHandsi.ResidueEnergy>sj.ResidueEnergythen

14.siBroadcastFINAL_HEAD_MSGandthenexit

15.Endif

16.Endwhile

2.3 多跳传输

当簇组结束后，无线传感器网络进入数据传输阶段。主要包括2部分：簇内数据传输和簇间数据传输。本文簇内数据传输与LEACH簇内数据传输方式相同。簇间数据传输策略如下：

① 如果簇首节点si位于热点区域内，那么它将数据直接传递给基站；

(8)

式中，u、v、w为0～1的常量，Nnember、N分别是簇内节点数和总节点数。

3 算法分析

UCDCR算法的消息复杂度为O(N)，N为网络中的节点数。

证明：假设网络中有C个交互节点，且普通节点成为候选簇首的概率为T，成为簇首的概率为P。算法开始时，有N×T个节点成为候选簇首并发送N×T条COMPETE_HEAD_MSG消息，竞选成功的候选簇首节广播一条FINISH_ELECT_MSG消息，而没有竞选成功的候选簇首则广播一条竞选失败消息退出选举；N×P个节点成为簇首并发送一条CH_V_MSG消息，N(1-P)个普通节点接收到来自簇首的CH_V_MSG消息后发送申请入簇消息，簇首接收到申请消息，同意后并回复申请者入簇的消息，交汇节点发送C个消息。所以，网络每轮总开销为N×T+N×T+N×P+N×(1-P)+C=(2T+1)N+C。综上所述，算法的复杂度为O(N)。因此，UCDCR算法的网络开销比较小。

UCDCR算法采用非均匀分簇路由，通过对网络区域划分，动态地改变簇半径来均衡簇首的能耗。“热点区域”的簇竞争半径Rcmp考虑簇首的剩余能量，使得靠近基站的簇半径减小，簇首能量消耗减少，减少“热点区域”节点过多死亡的现象，有效解决“热区问题”，“非热点区域”的簇竞争半径综合考虑节点到基站的距离、剩余能量，位置和全网的平均能量的因素，引进中继节点，避免了簇首能耗过快而死亡，延长了网络的生命周期。

4 仿真分析

本文使用MATLAB软件对UCDCR算法进行模拟实验，并与EEUC[4]算法和CUCRA[5]算法进行对比分析。网络参数如表1所示，除非特别指出，本算法的其他参数为T=0.4，R0=90 m，DIS_MAX=140 m，ΔR=1.7。

表1 网络参数设置

本文将从以下3方面对UCDCR和EEUC、CUCRA算法进行性能对比。

4.1 节点的平均能耗

图3为3个算法随着网络的运行，节点的平均能耗曲线图。从图中能够看出，EEUC算法的平均能耗高于CUCRA算法，而两者都高于UCDCR算法，说明UCDCR算法选举的簇首分布均匀，降低了簇间传输和簇内传输的能耗，使得节点的平均能耗低于其他2个算法。

图3 节点平均能耗

4.2 传输时延

图4给出了CUCRA、UCDCR算法的传输时延。可以看出，随着算法的运行，CUCRA的传输时延越来越大，这是因为网络中簇首数目随着网络运行而增多，导致传输时延增大；而本文提出的UCDCR算法虽然同样进行了簇竞争半径调节，但并没有出现CUCRA算法的现象，说明本文提出的算法是可行的。

图4 传输时延

4.3 节点存活数

本文将第1个节点死亡的时间定义为网络的生命周期。从图5中可以看出，EEUC、CUCRA和UCDCR3种算法生命周期分别为586、704和808。所以，UCDCR算法网络生命周期分别比EEUC算法和CUCRA算法提升了27%和13%。因为EEUC算法不同于CUCRA和UCDCR算法，没有簇竞争半径的调整过程，所以，EEUC出现第1个死亡节点的时间要比它们早，而CUCRA算法的簇竞争半径虽然考虑了节点的剩余能量，但并没有对簇首的位置加以限制，本算法通过“热点区域”和“非热点区域”对节点位置精确限制，保证选举出最优簇首，所以网络生命周期长。但CUCRA算法的存活节点数数量呈曲线下降趋势，在1 140～1 300轮之间，其存活节点数多余UCDCR算法，这是因为随着算法的运行，网络中节点能量越来越少，其簇竞争半径逐渐减小，使得簇首数目逐渐增多。如图4所示，网络中的簇间传输距离减少，降低了节点的能耗速率，但增加了传输时延。

图5 节点存活数

5 结束语

本文提出了一种能耗均衡的UCDCR算法，通过网络区域划分、簇竞争半径动态调整来均衡网络中簇首的能耗，以解决无线传感器网络中的“热区”问题。生命周期比EEUC算法和CUCRA算法分别延长了27%和13%。同时，比CUCRA算法传输时延更低，保证了数据的实时性。但是，UCDCR算法采用随机的方式选择簇簇首，可能造成簇首的分配不合理，今后的工作会对该问题进行修改。

[1] 朱永利,于永华,李丽芬.数据收集传感器网络的多模层次网络构建[J].计算机工程,2011,37(2)：111-113.

[2]WuX,ChenG,DasSK.AvoidingEnergyHolesinWirelessSensorNetworkswithNonuniformNodeDistribution[J].ParallelandDistributedSystems,IEEETransactionson,2008,19(5): 710-720.

[3]LiJ,MohapatraP.AnAnalyticalModelfortheEnergyHoleProbleminMany-to-oneSensorNetworks[C]∥IEEEVehicularTechnologyConference.IEEE，1999,2005,62(4): 2721-2725.

[4]XueY,ChangX,ZhongS,etal.AnEfficientEnergyHoleAlleviatingAlgorithmforWirelessSensorNetworks[J].IEEETransactionsonConsumerElectronics,2014,60(3): 347-355.

[5]LiuAF,WuXY,ChenZG,etal.ResearchontheEnergyHoleProblemBasedonUnequalCluster-radiusforWirelessSensorNetworks[J].Computercommunications,2010,33(3): 302-321.

[6]LiuAF,ZhangPH,ChenZG.TheoreticalAnalysisoftheLifetimeandEnergyHoleinClusterBasedWirelessSensorNetworks[J].JournalofParallelandDistributedComputing,2011,71(10): 1327-1355.

[7]SoroS,HeinzelmanWB.ProlongingtheLifetimeofWirelessSensorNetworksViaUnequalClustering[C]∥InProceedingsof19thInternationalParallelandDistributedProcessingSymposium(IPDPS05),2005:1-8.

[8] 李成法,陈贵海,叶 懋,等.一种基于非均匀分簇的无线传感器网络路由协议 [J].计算机学报,2007,30(1): 27-36.

[9]TongW,JiyiW,HeX,etal.ACrossUnequalClusteringRoutingAlgorithmforSensorNetwork[J].MeasurementScienceReview,2013,13(4): 200-205.

[10]KuipersF,VanMieghemP,KorkmazT,etal.AnOverviewofConstraint-basedPathSelectionAlgorithmsforQoSRouting[J].IEEECommunicationsMagazine,2002,40 (12):50-55.

[11]HeinzelmanWR,ChandrakasanA,BalakrishnanH.Energy-efficientCommunicationProtocolforWirelessMicrosensorNetworks[C]∥Proceedingsofthe33rdAnnualHawaiiInternationalConferenceon.IEEE,2000: 3005-3014.

[12] 许晓天,李德敏,周 凡,等.基于簇半径差异化和节点能量区间的分簇算法[J].2015，24(2):170-173.

Uneven Clustering Algorithm Based on Dynamic Cluster Radius

XIONG Lian,YE Jian-guang,LIU Xiao-tong

(New Technology Research Institute of Communication Engineering,Chongqing University of Post and Communications (CQUPT),Chongqing 40065,China)

In wireless sensor network clustering routing algorithm,an uneven clustering algorithm based on dynamic cluster radius (UCDCR) is put forward in view of “hot spot” caused by unbalanced node energy consumption.In clustering stage,the network is divided into different areas,and the condidate cluster head uses the competition radius of cluster to build clusters with different size.So the cluster head can dynamicallychange competition radius of cluster to reserve more energy for data forwarding.The simulation experiments show that the UCDCR algorithm can effectively balance the energy consumption of nodes and prolong the network life cycle compared with EEUC algorithm and CUCRA algorithm.

wireless sensor network; dynamic; cluster radius; uneven clustering

10.3969/j.issn.1003-3114.2017.01.13

熊 炼，叶建光，刘晓彤.基于动态簇半径的非均匀分簇算法[J].无线电通信技术,2017,43(1):51-55.

2016-10-11

长江学者和创新团队发展计划 (IRT1299)(cstc2013yykfA40010)作者简介:熊 炼(1968—)，男，硕士生导师，主要研究方向：移动通信技术。叶建光(1989—)，男，硕士研究生，主要研究方向：无线传感器网络。

TP212.9

A

1003-3114(2017)01-51-5