WSN 中基于非均匀梯度的分簇拓扑算法

阎新芳，张永坤，李 腾，王晓晓

(1．郑州大学 信息工程学院，河南 郑州450001;2．北京邮电大学 信息与通信工程学院，北京100876)

0 引言

路由技术是无线传感网(Wireless Sensor Network，WSN)的一个关键技术，而目前WSN 发展最大的瓶颈就是节点能量有限且不易补充．因此，避免不必要的通信、均衡整个网络的能耗成为路由协议设计的关键因素［1-2］． 基于分簇的层次路由算法由于其能量高效且易于扩展而被广泛研究和应用［3-6］．其中，文献［6］提出一种基于能量的分级簇算法ETBG(Energy-Aware Topology Protocol Based on Gradient)算法，该算法参考定向扩散协议中梯度的思想，根据节点的通信半径把网络建成一个梯度场，以减少分级簇等级和数据分组转发跳数，降低延迟时间，同时延长网络生存周期．ETBG［7-8］是分布式、异步并行算法，但存在如下问题:靠近基站的簇首由于转发大量数据而负载过重，可能过早耗尽能量而失效．

为解决这个问题，笔者提出了一种基于梯度的分簇拓扑算法CTAUG(a Clustering Topology Algorithm Based on Uneven Gradient in WSN)，即将网络划分为依次递增的非均匀梯度，并对簇成员入簇的策略进行改进，使得靠近基站的簇的规模小于远离基站的簇的规模，从而使靠近基站的簇头可以为簇间的数据转发预留更多能量，延长网络的生存周期．

1 基于非均匀梯度的分簇算法

无线传感器节点被随机部署到目标区域以后，基站按照等差数列的方法将整个网络以基站为圆心从近到远，划分为大小不等、依次递增的非均匀梯度，并将梯度信息以一个初始化消息向全网广播．网内节点收到该消息后，开始执行CTAUG 算法．

如图1 所示，算法将时间划分为轮，总体分为簇树建立和数据传输两个阶段． 簇树建立包括以下几个过程:判断梯度、构建邻居集、簇头竞争、节点入簇、簇树形成等．数据传输阶段包括簇内数据传输和簇间数据传输．

图1 CTAUG 协议的生存时间划分Fig．1 The divided of CTAUG agreement survival time

1．1 非均匀梯度的划分

基站感知它到网络的最远距离和最近距离，分别记为dmax、dmin，然后以自己为圆心把网络划分为多个半径不同的同心圆环梯度，最大半径为Rmax(Rmax=dmax)，最小半径为Rmin(Rmin=dmin)．基站规定圆环梯度层数L 及每个梯度的上界值UG 和下界值LG，把以基站为圆心，Rmin为半径的圆定义为第0 梯度L0，然后把以半径Rmin到Rmax的这个圆环划分为大小不等、依次递增的圆环梯度，划分方法如下:

Rmax-Rmin=La1+L(L-1)r/2． (1)

其中，层数值L 和第1 层梯度的跨度a1均由基站决定，等差数列的差值r 在L、a1的值确定后，由式(2)可得．

r=2(Rmax-Rmin-La1)/(L-1)L． (2)

由此可得第i(i=2，…，L)层梯度的跨度:

ai=a1+(i-1)r=a1+

2(i-1)(Rmax-La1)/(L-1)L． (3)

假设LG1=Rmin，基站可采用以下公式计算每层梯度的上界值和下界值:

UGi=LGi+ai(i=1，…，L); (4)

LGi=UGi-1(i=2，…，L)． (5)

划分成三层的非均匀梯度如图2 所示．

图2 非均匀梯度划分示意图Fig．2 Schematic division of uneven gradient

算法开始时，基站向全网广播初始化消息INITMessage，消息格式如下．

各层上边界:UGL，…，UG2，UG1(L≥2);各层下边界:LGL，…，LG2，LG1(L≥2)．

1．2 簇树建立阶段

1．2．1 判断梯度

收到基站发出的初始化消息后，各节点根据自己到基站的近似距离和初始化消息中各个梯度的上下边界，计算得到自己的梯度等级和到自己所在梯度中心线的距离Dm．

1．2．2 构建邻居集

(1)第一次信息交互． 首先各个节点启动定时器T1，开始以R 为功率半径向其邻居节点广播当前状态信息STATUSMessage，其中包括节点ID、当前剩余能量Er、梯度L、状态status、到梯度中心线的距离Dm．然后将交互得到的邻居信息保存在自己的邻居集中，并对邻居节点个数进行计数．

(2)综合权值的计算． 在T1 计时结束之后，节点根据自己邻居集中的信息开始计算自己的综合权值W，其定义为

W=w1Er+w2/Nd+w3/Da+w4/Dm． (6)

式中:w1+w2+w3+w4=1;Er为节点剩余能量;Nd为节点邻居节点数目;Da为到邻居节点的平均距离;Dm为到节点所在梯度中心线的距离．

用层次分析法［9-10］来确定各自的权系数．此方法通过两两比较的方式确定诸因素的相对重要性，然后综合人的判断，决定诸因素总的顺序．

(3)第二次信息交互． 节点计算好自己的综合权值后，启动定时器T2，进行第二次信息交互，将自己的综合权值发送给所有的邻居． 节点将所有邻居第二次交互时发送来的综合权值保存在自己的邻居集中．

1．2．3 簇头竞争

等邻居集构建完成后，节点将自己的综合权值与邻居节点的综合权值进行比较，如果自己的权值是邻居集中最大的，就宣布自己是簇头，并向周围邻居节点广播簇头消息HEADMessage，这样就选出了部分在邻居节点中综合权值最大的节点为簇头节点．

1．2．4 节点入簇

此阶段节点启动定时器T3，开始接收邻居簇头发来的簇头消息HEADMessage，并将其保存在自己的簇头列表中．

在T3 计时结束后，节点如果只收到一个簇头消息，就直接加入该簇头所在的簇中，并向其发送JOINMessage;如果收到两个或两个以上的簇头消息，则优先选择加入到梯度较大的簇头中，并向其发送JOINMessage;如果这几个簇头在同一梯度中，则优先加入到剩余能量较大的簇头中，并向该簇头发送JOINMessage;如果没有收到簇头消息，且邻居中综合权值比自己大的节点状态都已经确定，则宣布自己成为簇头，并向邻居节点中比自己权值小的节点广播簇头消息HEADMessage． 否则，继续等待并接收来自邻近节点发来的消息，直到分簇完成．

考虑到WSN 中节点与基站直接通信的能耗和其先将数据发送到簇头再转发到基站的能耗相近，则让这些节点与基站直接通信不仅可以减少在数据转发中产生的额外负载，也减少了靠近基站的簇头的簇成员数量，从而可以为数据转发预留更多的能量．因此该算法拟让能与基站通信的节点直接与基站进行通信，其他节点则按照以上方法入簇，分簇完成后，按照ETBG 算法形成簇树．

1．3 特例说明

特例:假设在一个100 m×100 m 的区域内随机抛洒50 个传感器节点，采用参考文献［3］所示能量模型，最大通信半径R =30 m，梯度层数L =3，第一层梯度的跨度a1=20 m．

图3 为算法改进前后的分簇对比图． 由图3(b)和图3(a)可以看出:图3(b)中产生的簇头兼顾剩余能量的同时，更接近所在梯度的中心，且更靠近簇的质心位置．

由图3(c)和图3(b)可以看出:图3(c)中的灰色节点14，23，30，27，8，35，47，49，3，40，6，42，29，21 按照优化的规则选择了加入梯度较大、剩余能量更多的簇头节点，而白色节点依然保留在原来的簇中．例如:节点39 只收到簇头9 发来的簇头消息，则依然保留在原来的簇中;节点35 收到两个簇头46，48 发来的簇头消息，选择梯度更高的48 作为自己的簇头;节点8 收到3 个簇头9，13，36 发来的簇头消息，其中13 的梯度比自己低，而9，36 和自己同一梯度，因此选择剩余能量更多的36 作为自己的簇头．

图3 算法改进前后的分簇对比图Fig．3 Comparison chart of before and after algorithm optimization

图3(d)和图3(c)还可以看出:图3(d)中的三角形节点44，43，2，5，40，6，38 按照优化的规则直接与基站进行通信．

2 性能分析

2．1 梯度层数对生存期的影响

设定簇头轮换频率为1 500 轮/次，通信半径为30 m，所有仿真结果都是模拟10 次的均值，图4 为梯度层数L 的变化对网络生存期的影响．

从图4 可以看出:两种算法的生存期都在L=2 时最短及L =3 时最长;随着L 值继续增大，生存期慢慢变短，曲线成山峰型．这是因为当L 值较小即梯度层数较少时，最外层的簇首的成员过多，簇内通信能耗增大，节点过早死亡;而当L 值较大即梯度层数较多时，各层跨度变窄，非均匀程度降低，簇间路由增多，导致靠近基站的簇头容易过早死亡．

图4 不同梯度的生存期对比图Fig．4 Lifetime versus layers of gradient

2．2 簇首消耗的能量之和

簇头轮换频率设定为1 500 轮/次，梯度层数L=3，节点个数分别为20，40，…，180，200，从实验中随机选取10 轮，统计各轮中所有簇头消耗的能量，结果如图5 所示．

图5 不同节点个数时每轮所有簇首消耗能量对比图Fig．5 Average energy dissipation versus nodes’number

从图5 可以看出，随着区域内节点个数的增加，节点也越来越密集，相应的簇头的任务也更加繁重，簇首所消耗的总能量随之快速增加． 但在CTAUG 算法中由于靠近基站的节点直接与基站通信，其余节点优先加入梯度等级较高、剩余能量较大的簇头所在的簇中，因此CTAUG 算法中每轮所有簇头的能耗仍大大低于ETBG 算法中每轮所有簇头的能耗．

3 结论

通过研究ETBG 算法中存在的“热区”问题，提出了一种基于非均匀梯度的分簇拓扑结构算法CTAUG．该算法综合考虑节点剩余能量、邻居节点个数、到邻居节点之间距离的平均值和到梯度中心线的距离等因素构造综合权值，且用层次分析法来确定各个因素的权系数，使生成的簇头分布更加合理．另外，该算法划分了非均匀梯度，使靠近基站的节点直接与基站通信，其余节点则优先加入梯度较大、剩余能量较多的簇头所在的簇中，有效解决“能量空洞”问题，延长了网络的生存期，适用于大规模的网络．

［1］ AKKAYA K，YOUNIS M．A survey on routing protocols for wireless sensor network［J］． Ad Hoc Networks，2005，3(3):325 -349．

［2］ JAMAL N A，AHNED E K． Routing techniques in wireless sensor networks:a survey［J］．IEEE Wireless Communication，2004，11(6):6 -28．

［3］ HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H． An application-specific protocol architecture for wireless microsensor network［J］． Wireless Communication，2002，1(4):660 -670．

［4］ MANJESHWAR A，AGRAWAL D P．TEEN:A routing protocol for enhanced efficiency in wireless sensor networks［C］//IEEE Conference Proceedings on Parallel and Distributed Processing． San Francisco CA，USA:IEEE Press，2001:2009 -2015．

［5］ LINDSEY S，RAGHAVENDRA C S．PEGASIS:Powerefficient gathering in sensor information systems［C］//IEEE Conference Proceedings on Aerospace． Los Angeles，CA，USA:IEEE Press，2002:1125-1130．

［6］ AN Na，YAN Xin-fang，ZHU Yu-fang，et al． A virtual backbone network algorithm based on the multilevel cluster tree with gateway for wireless sensor networks［C］//The IET International Communication Conference on Wireless Mobile and Sensor Networks． Shanghai，China:IET Press，2007:462 -465．

［7］ 阎新芳，段磊，李腾．无线传感网中基于梯度的拓扑控制算法［J］． 计算机工程与应用，2011，47(2):95 -98．

［8］ 阎新芳，王志龙，闫新生，等．WSN 中基于梯度场拓扑控制算法的维护更新［J］． 传感器与微系统，2011，30(8):56 -58．

［9］ SAATY T L．The analytic hierarchy process［M］． New York:McGraw-Hill，1980:180 -230．

［10］KWANG E Y，YOUN C C． Analytic hierarchy process approach for identifying relative importance of factors to improve passenger security checks at airports［J］． Air Transport Management，2006，12(3):135 -142．