一种基于时间延迟机制的WSNs非均匀分簇算法

王志勇， 孙顺远， 徐保国

(江南大学 物联网工程学院，江苏 无锡 214122)

一种基于时间延迟机制的WSNs非均匀分簇算法

王志勇， 孙顺远， 徐保国

(江南大学 物联网工程学院，江苏 无锡 214122)

为减少无线传感器网络分簇路由协议中节点竞争簇首时多余的能耗，解决簇首能耗不均的问题，提出一种基于时间延迟机制的非均匀分簇算法。该算法使能量较多的节点被优先选为簇首，并提出了簇首竞争半径的计算方法，确保其数目稳定且位置均匀分布。成簇过程中，节点根据最小消费函数选择簇首，簇内成员加入时考虑簇首能量、二者距离以及簇首和汇聚节点角度等因素来均衡簇首能耗。仿真结果表明：算法能有效地均衡节点能耗，延长网络寿命，分别比CHTD和EEUC算法延长了35.1 %和12.9 %。

无线传感器网络； 时间延迟； 非均匀分簇； 能量消耗函数

0 引 言

无线传感器网络 (wireless sensor networks,WSNs)是由大量具有一定计算和通信能力的传感器相互协作而形成的自组织网络系统。它能够感知或采集监测对象的相关信息并进行处理，目前已被广泛应用于军事、环境、工业、家庭等许多方面。由于节点的能量、计算能力和带宽资源有限，因此，如何均衡节点能耗和延长网络寿命是WSNs路由协议首要设计目标和研究热点。

成簇算法是WSNs中减少能量消耗的一种关键技术,它能够提高网络的生存时间,可以减少路由算法和洪泛广播的开销。近年来，大量关于传感器网络分簇的协议被提出，Leach算法[1]提出以轮为工作周期，每轮根据阈值选择簇首，减少节点与基站的直接通信量从而节约能耗，但是簇首的选择完全依赖随机数并不合理。基于Leach的思想，文献[2]提出了DCHS算法，引入能量阈值，延长了网络生存周期，但是未考虑到全网能量的均衡消耗。文献[3]提出了HEED算法，根据依赖于节点剩余能量的主参数和依赖于簇内通信代价的次参数选择簇首，能量消耗较均衡，但是簇内多次消息迭代带来的通信开销较为巨大。

针对多跳网络，文献[4]引入了能量和距离阈值以均衡全网能量消耗，但簇首之间多跳通信的能耗问题没有得到很好地解决。文献[5]提出来一种多跳均匀分簇路由算法，即通过候选簇首的竞选半径和节点剩余能量来确定分布相对均匀的簇首，簇首之间采用以簇首节点剩余能量和链路传输代价的权值建立多跳路由算法。但是均匀分簇仍然会导致簇负载的不平衡，且距离Sink节点近的簇首会因转发大量数据而能耗较大。为了解决热区问题，文献[6]提出了EEUC算法，可以很好地解决多跳网络中的热区问题，但其簇首为随机产生，负载能力并非最优，根据阈值选择的候选簇首数量过多，导致节点间竞争簇首通信产生大量多余的能量消耗，并且成簇阶段节点依据最近原则加入簇首，没有考虑形成的簇的能耗问题。

文献[7,8]提出了一种关于定时器的时间延迟机制，但是对于簇首数目和节点加入簇的方式并没有深入研究，不稳定的被动簇首个数导致局部负载不均衡，文献[9]提出了一种新的等待时间与剩余能量之间关系。考虑了簇首的个数问题，但是对于多跳传输网络，同一的竞争半径会导致簇首能耗不均衡，远离汇聚点的节点过早死亡。

针对以上问题，结合CHTD和EEUC算法，本文提出了一种新的WSNs多跳路由算法。选择簇首时，在时间延迟机制的基础上结合了非均匀分簇的思想，并给出竞争半径计算公式。在成簇过程中，提出了一种新的消费函数，簇内成员加入时考虑簇首能量，二者距离和通过添加定位节点得出的角度等因素。多跳传输过程中给出了是否需要中继节点的衡量标准。

1 系统模型

1.1 网络模型

假设传感器节点随机均匀分布在一个M×M的方形区域中，用si表示第i个节点，相应的节点集合为S={s1,s2,…,sN}；并具有如下性质：

1)WSNs是一个高密度网络，由一个汇聚节点,一个定位节点和n个同构普通传感器节点构成，汇聚节点位于方形区域的外侧且位置坐标为(M/2,1.25M)，定位节点坐标为(M/2,0)，且所有节点在部署后就不在移动；

2)每个传感器节点都有一个事先安排好的唯一ID；

3)传感器节点发射功率可调，即能够根据与接收者的距离调节发射功率，且节点间能根据接收信号强度(received signal strength，RSS)计算相互间的距离；

4)网络中节点的时间是同步的。

1.2 能量模型

采用和文献[6]相同的无线通信能量消耗模型,如将kbit信息从节点i传送至节点j，则节点i的发射能耗为

(1)

式中Eelec为发射电路损耗的能量。若传输距离小于阈值d0，功率放大损耗采用自由空间模型；当传输距离大于等于阈值d0时，采用多路径衰减模型。Efs,Emp分别为2种模型中功率放大所需要的能量，节点接收kbit数据的能耗为

ERX(k)=Eelec×k.

(2)

数据融合也消耗一定的能量，用Edf表示融合单位比特数据消耗的能量，假设邻近节点采集的数据具有较高的冗余度，簇首可以将其成员的数据融合成一个长度固定的数据包，然后发送给汇聚节点。

2 UCTD算法

UCTD算法是一种分布式的竞争算法，要先根据本节点的剩余能量生成一个定时器，拥有较短延迟时间的节点将赢得竞争权并有可能成为簇首。算法通过竞争半径来构造大小不等的簇，靠近汇聚点的簇的规模小于远离汇聚点的簇,使其保留能量用于簇间中继转发。普通节点依据最小消费函数选择簇首加入成簇。簇内成员节点按分配好的TDMA时隙将数据发送至簇首，簇首将数据融合后通过多跳方式传送至汇聚节点。

2.1 时间延迟机制

假设Er(i)为节点i第r轮后所剩能量，E0为节点初始能量，K为决定延迟大小的比例系数，则设定节点时延为

Ttimer(i)=K·e1-Er(i)/E0+rand(0,α).

(3)

前半部分起到时间延迟的主要作用，后半部分生成一个随机数，主要是为了避免同样能量的节点相互干扰，这里,α取值0.1。从前半部分来看，这是一个关于剩余能量值Er(i)的减函数，即剩余能量越大的节点延迟时间越短，从而使得其成为簇首的机会更大。

2.2 簇首的选举

采用分簇的多跳传输网络中,簇首消耗能量占每轮能量消耗的主要部分。因为它在簇内通信时需要管理所属簇成员并与其通信进行数据传输,还要融合簇成员收集的数据；在簇间通信时作为中继节点间接或直接的将处理后的数据发送给汇聚点。簇首能量的消耗平衡与否直接关系着WSNs的生命周期长短。UCTD算法在每个数据收集周期的开始重新构造簇,选择剩余能量较高的节点作为簇首。下面阐述竞争选取簇首的算法：

WSNs中传感器节点部署后，所有节点以同样的信号强度向汇聚点依次发送信息，汇聚点计算出最大最小距离后和定位节点以一定的功率先后向全网广播一个信号。所有节点根据接收到的信号强度计算出它到汇聚点和定位点的近似距离，分别由公式(4)得到节点自身竞争半径,公式(5)得到和汇聚节点形成的角度。在收到汇聚节点竞选命令后，本轮簇首竞选开始，各节点按式(3)计算各自时延时间Ttimer(i)，节点si超时后向全网广播消息成为第1个簇首。消息包括自身标识ID、剩余能量Er(i)、竞选半径Rc(i)和汇聚节点的距离d(CHi,BS)及其根据公式(5)计算得到cosβ。未超时的普通节点收到接收其他候选簇首发送来的消息，将其计算自己和它的距离dis，若dis小于簇首的竞争半径，那么节点将定时器清零，放弃竞选簇首。其余的节点将继续竞争，成为簇首的节点依次向全网广播。时间到达最大延迟时间后，簇首选举结束。

普通节点收到簇首发来的消息后选择簇首发送加入请求消息，为了能够让靠近汇聚节点的簇规模较小，保留能量用于中继转发，算法提出了竞争半径的一种计算方法

(4)

式中dmax，dmin分别为网络中为的节点到基站的距离的最大值和最小值，d(si,BS)为节点到汇聚点的距离,c为控制取值范围的参数，竞争半径R与节点到汇聚点的距离呈递减关系，当c取值0.5时，网络中覆盖半径为1.5R。

2.3 簇的生成

簇首选择好后，节点如何加入簇首直接关系到平衡当前簇首地区的能量消耗。节点加入簇首不能仅仅以和簇首的距离大小来决定，还考虑加入的簇首剩余能量的多少；并且从网络多跳传输的角度来看，节点应该尽量选择距离汇聚节点远些的簇首加入，使靠近汇聚节点的簇内成员相对减少，彻底解决热区问题。在图1中，对于普通节点3该加入簇首1还是簇首2的问题，从距离上来看，簇首1比簇首2到汇聚节点的距离远，如果在二者剩余能量相等并且和节点3距离相同的条件下，按照上面的理论，节点3将加入簇首1，这样会导致边缘节点负荷过重，不利于平衡全网能量消耗。因此，节点还应该考虑加入与汇聚节点角度小的簇首。

图1 簇首与定位节点角度Fig 1 Angle between cluster head and location node

综上，可以添加度量标准cosβ，为了计算出节点与汇聚节点所成角度值，网络模型中添加了定位节点，节点与汇聚节点在同一直线上，这里称作BS2，由于节点不移动，所以,定位点只需在通信开始时以固定功率发送一次消息即可，每个节点接收到后各自计算和它的距离后根据余弦公式(5)计算获得自己与汇聚节点形成角度的大小

(5)

考虑以上因素，由此提出了节点i加入簇首j的消耗函数公式

(6)

其中，Ei为节点i的当前能量，ECHj为簇首j的当前能量，γ为权值，并且

(7)

(8)

式中d(ni,CHj),dn_CH_max分别为节点i到簇首j的距离及其最大值,d(CHj，BS)分别为簇首j到汇聚节点的距离及其最大值，cosβ为簇首和汇聚节点所成角度的余弦。

2.4 多跳路径的选择

文献[6]中EEUC算法在中继节点的选择上定义了开销指标

Erelay=d2(si,sj)+d2(sj,DS).

(9)

取指标最小的2个簇首并从中选取剩余能量高的作为中继节点。使得网络能量开销较小，剩余能量较大簇首成为下一跳节点，均衡了簇首间的能量。在此基础上，算法提出了簇首衡量是否需要中继节点的标准。假设节点i选择j作为中继节点，由能量消耗模型得

Ehop=ETX(k,d(i,j))+ERX(k)+ETX(k,d(j,DS)) =kεfs(d2(i,j)+d2(j,DS))+3kEelec.

(10)

若采用单跳传输则消耗能量为

Edirect=ETX(k,d4(i,BS))=k(Eelec+εmpd2(i,BS)).

(11)

若Ehop

2Eelec+εfs(d(i,j)2+d(j,BS)2)<εmpd(i,BS)4.

(12)

当满足式(12)时，簇首j被选为中继节点才能有效节省能耗;否则,节点i将不再选择中继点，直接与汇聚节点通信。

3 仿真分析

为了进一步验证UCTD算法的性能，算法运用Matlab平台进行模拟实验，假设采用理想MAC协议，忽略无线链路中发生丢包的错误。实验中统计传感器节点发送，接收数据包与控制包，融合数据消耗的能量。仿真参数如下：网络面积200 m×200 m，基站位置为(100,250)m，定位节点位置为(100,0)m，节点总数400，节点初始能量0.5 J,数据包大小为4 000 bit，控制包大小为200 bit，εfs为10 pJ/(bit·m-2)，εmp为0.001 3 pJ/(bit·m-4)，Eelec为50 nJ/bit,Edf为5 nJ/bit·signal-1。

UCTD拥有良好的自适应性，每轮都能让局部能量最高的节点成为簇首，为了能够自动调整与汇聚节点距离相关的簇首的疏密程度，确保分布均匀，竞争半径的选择尤为重要。由前面分析可知，参数c和半径R决定着簇首的数量。图2显示了当c取值0和0.5时,前200轮中平均簇首数目与R之间的关系，即当R不变时，c越大节点半径越大，簇首数目也会越少，这里，取值R=50 m，c=0.5时簇首数目较为合理，基本稳定在7～11之间。

图2 UCTD簇首数目Fig 2 Number of UCTD cluster head

算法中能量消耗函数的参数γ的选择是均衡节点成簇能量的关键，通过仿真观察网络中权值γ对节点死亡时间的影响，从0.3～1范围内进行实验，网络中第一个节点的死亡时间和γ的关系如下图3所示，可以看出γ=0.8时效果最好。

图3 能量消耗权值γ与轮数的关系Fig 3 Relationship between energy consumption weight and rounds

由于簇首消耗能量占每轮能量消耗的主要部分，因此,比较3种协议生成的簇首在一轮中所消耗能量之和，从实验中随机选取10轮统计各轮种中所有簇首消耗的能量如图4，CHTD由于是单跳通信方式传输到汇聚节点，长距离的传输导致能量消耗过大，而EEUC和UCTD采用多跳传输方式，能量消耗都小于CHTD。UCTD采用时间延迟选择出能量最高的簇首，通过竞争半径确保了簇首间的分布均衡并通过最小消费函数使节点选择最优簇首加入，使得每轮簇首的能量更小且更平均。

图5显示了在随机选取的10轮中，各轮簇首消耗能量的方差。从图中可以看出UCTD方差最小且波动平稳，说明算法均衡了簇首之间的能量消耗，EEUC算法也相对均衡但是方差略大，CHTD的方差最高而且有明显的波动，簇首能耗不均会导致节点过早死亡。

图4 簇首消耗能量之和Fig 4 Sum of energy consumption of cluster heads

图5 簇首消耗能量的方差Fig 5 Variance of energy consumption of cluster heads

比较3种协议的网络存活时间，如图6所示，CHTD，EEUC，UCTD协议中第一个节点死亡轮次分别为361，493，546；网络中50 %节点死亡轮次分别为465，597，680；节点全部死亡轮次分别为532，636，718。UCTD都要优于其他2种算法，节点全部死亡的时间比CHTD和EEUC分别延长35.1 %和12.9 %。从曲线的下落趋势来看，EEUC和UCTD算法节点的死亡轮数跨度很小，曲线下落趋势和斜率相近，说明节点能量消耗均衡，但UCTD减少了EEUC协议中候选簇首竞争簇首消耗的部分能量，并提出了更合理的成簇方式，所以,网络寿命得到了延长。

图6 各种协议网络存活时间Fig 6 Network lifetime of various protocols

4 结束语

本文结合CHTD和EEUC算法提出了一种适用于多跳传输网络的基于时间延迟机制的非均匀分簇算法UCTD,节点成簇过程中根据消费函数选择簇首，多跳传输过程中给出是否需要中继节点的判断标准。算法良好的自适应性每轮选择出局部能量最高的节点充当簇首，能够很好地减少候选簇首竞争簇首时的多余的能耗。仿真表明：算法能有效地平衡能量负载并且充分地延长了网络生命周期。

[1] Heinzelman W R,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[2] Handy M J,Haase M,Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]∥Proc of the 4th IEEE Conf on Mobile and Wireless Communications Networks:Stockholm IEEE Communications Society,2002:368-372.

[3] Younis O,Fahmy S.Heed: A hybrid,energy-efficient,distributed clustering approach for ad-hoc sensor networks[J].IEEE Trans on Mobile Computing,2004,3(4):660-669.

[4] Hsu H L,Liang Q L.An energy-efficient protocol for wireless sensor networks[C] ∥Proceedings of Vehicular Technology Confe-rence,Texas,2005:2321-2325.

[5] 徐久强,毕伟伟,朱 剑.WSNs中多跳均匀分簇路由算法的设计与仿真[J].系统仿真学报,2011,23(5):992-997.

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

[7] Cui Xiaoyan.Research and improvement of LEACH protocol in wireless sensor networks [C] ∥IEEE 2007 International Symposium on Microwave,Antenna,Propagation and EMCMAPE,Technologies for Wireless Communications,2007:8.

[8] 曹涌涛,何 晨,蒋铃鸽.无线传感器网络中基于自适应定时器策略的分簇算法[J].电子学报,2007,35(9):1719-1723.

[9] 任东海,尚凤军,王 寅.一种基于时间延迟机制的无线传感器网络分簇算法[J].传感技术学报,2009,22 (11):1646-1649.

An uneven clustering algorithm for WSNs based on time delay mechanism

WANG Zhi-yong， SUN Shun-yuan， XU Bao-guo

(School of IOT Engineering,Jiangnan University,Wuxi 214122,China)

To reduce energy consumption while nodes are competitiving cluster head in WSNs clustering routing protocol and solve the problem of unbalanced energy consumption,present a novel uneven clustering algorithm based on time delay mechanism.This algorithm can guarantee the node with high remaining energy to be chosen as the cluster head nodes in priority,besides this,propose computation method of cluster head competitive radius,to ensure a constant number of cluster heads and the cluster heads are well scattered.In cluster process,nodes select cluster heads according to least consumption function,while in cluster member is joining in,consider factors of energy of cluster head ,distance and clusher head and sink node angle.Simulation results show that the algorithm can effectively balance energy consumption of nodes,prolong network lifetime,it prolongs 35.1 % and 12.9 % lifetime compared with CHTD and EEUC algorithm.

wireless sensor networks(WSNs); time delay; uneven clustering; energy consumption function

2013—09—02

TP 393

A

1000—9787(2014)04—0146—04

王志勇(1989-)，男，江苏徐州人，硕士研究生，主要研究领域为无线传感器网络路由算法与节能策略研究。