周 坤,李宝林,李仕伟,张刚元

(西华师范大学 计算机学院，四川 南充 637009)



基于梯度的分层成链路由协议的优化改进

周 坤,李宝林,李仕伟,张刚元

(西华师范大学 计算机学院，四川 南充 637009)

能源的有限性制约着无线传感器网络的生命周期，而节点间的通信消耗了绝大多数能量，所以无线传感器路由协议的设计决定着网络生命周期的长短。结合LEACH和PEAGSIS协议的特点，对基于梯度的无线传感器网络做了以下几点改进：①在簇头的选择算法方面，将网络平均能量、包接受率和节点与基站的距离纳入了算法；②簇内成链阶段在考虑链长门限值的同时增加了备用下一跳节点；③在链的重建设定上提出了一种能量折半的思想。经实验论证，算法在延长网络生命周期和减少端到端数据时延方面有明显改进。

无线传感器网络；LEACH；PEGASIS；分层成链；簇头门限值

0 引 言

得益于微机电系统、低功耗嵌入式技术、传感器技术与无线通信技术等的飞速发展，无线传感器网络成为了当今世界研究的热点之一。无线传感器网络(Wireless Sensor Networks,WSNs)是由大量具有感知、通信和数据处理能力的传感器节点组成的多跳自组织网络[1]。该网络通常被部署在环境恶劣的区域，用于获取目标信息。它是通过节点间的相互合作，对监测区域进行信息收集，然后将信息数据经过简单融合后发送给监测者。无线传感器网络在军事情报、环境监测、医疗护理、智能家居、工业应用、灾害预警等诸多领域具有良好的应用前景。

然而，无线传感器网络自身的局限性(计算、能量、存储等资源非常有限)，使得无线传感器网络路由设计的一个非常重要的目标就是降低节点能耗，进而提高网络的寿命。传统分簇算法如LEACH、PEGASIS、TEEN等[2-4]，成簇后存在簇的大小和簇头分布不均匀的问题，导致节点负载不均衡，降低网络的生命周期；后来的MERR[5]、AMERR[6]，通过优化传感器节点与SINK节点间的跳数和传输距离达到减少传输能耗的目的；文献[7]提出了基于梯度的拓扑控制算法，结合定向扩散协议中梯度的思想，根据通信半径把网络建成一个梯度场，以减少分级簇等级和数据分组转发跳数，进而降低时延；CLBG[8]算法结合梯度拓扑控制与PEGASIS算法，它缩减了簇内链的长度，降低了因为距离增加带来的通信开销，同时采用梯度簇头间成链传递数据给SINK节点，既实现了传输的可靠性又进一步降低了通信开销。

梯度场按照通信半径把网络分为不同的区域，结合PEGASIS算法，同一梯度区域内的节点进行簇头竞争，进而成簇。然后通过梯度间簇头成链传输至SINK节点，这样不仅能保证节点的通信消耗不会因为距离的增加而呈指数增加。同时，梯度间各自成链又能有效地均衡各节点的能耗，文献[8]很好地证明了基于梯度的分簇成链算法能有效降低和均衡节点能耗。

本文结合梯度场的概念，在LEACH和PEGASIS的基础上，对簇头选择算法进行了改进；在簇内成链的过程中考虑了下一跳节点的距离，同时增加了下一跳备用节点；针对PEGASIS协议每轮都重新成链的弊端，提出了一种能量折半思想。实验证明通过以上改进能更好均衡节点能耗以及减少时延。

1 基础概念

无线传感器网络路由协议按照网络结构可以划分为平面结构和层次结构两种类型[9]，经典的LEACH协议就是一种低功耗自适应集簇分层路由协议，该协议是由Heinzelman等人在2000年提出，是无线传感网中第一个被提出的分簇路由协议，后面广为人知的PEGASIS协议也是在其基础上进行的改进。

1.1 LEACH路由协议

LEACH[2]协议的运行过程是先选举簇头，然后稳定传输信息数据，一段时间后重新选择簇头，再稳定传输信息数据，周而复始直至网络结束生命周期。在这里，将每个循环称为“轮”，由运行过程可知每轮分为簇建立阶段和稳定运行阶段两个阶段。此外，在每轮的建立阶段簇头都重新选举，簇内成员不变。在稳定阶段簇内节点和簇头节点进行数据传输。

在簇建立阶段的簇头选举时，每个节点随机选择区间(0，1)之间的一个数。若选定的数小于设定的门限阈值，则该节点成为簇头节点。节点n的门限阈值计算公式[10]如下：

(1)

上式中,p：簇头个数与节点总数的比值；r：进行了多少轮簇头选举；G：在前1/p轮中没有被选为簇头的节点集合。

完成簇头选举后，簇头通过广播通知整个网络，网络中的非簇头节点则通过接收到的信号情况选择从属的簇，在普通节点发报文告知相应簇的簇头节点后就完成了簇的建立。在此阶段中，LEACH协议为了避免多个簇头广播和节点间的冲突碰撞采用了基于CSMA的随机存取机制。稳定运行阶段，传感器节点通过基于TDMA的方式将收集到的监测信息向簇头进行传输，簇头收到数据后，和本身信息数据进行融合处理后再发送给汇聚节点。节点运行一段时间后，网络进入到下一“轮”，节点重新开始簇头选举。

由LEACH协议的运行过程可知：网络中的簇头一直保持着通信状态，而簇内的普通节点只有在簇创建阶段与稳定运行时被分配的时隙内处于通信状态。这样让普通节点在绝大多数时候保持待机状态，有效地减少了普通节点的功耗开销，延长了整个网络的生命周期。但LEACH协议还存在着一些不足之处，如：①簇头的选举过于频繁，增加了大量开销；②簇内节点直接同簇头节点通信，增加了簇头节点的能耗；③公式(1)这种簇头的选举策略，在很大程度上会导致网络中簇头分布不均和簇的大小有很大差别，这样就会造成各簇头节能耗不同，导致个别簇头节点较早死亡；④簇头节点直接和基站通信，当网络存在较多簇头节点时，不仅加速了节点的能耗，同时较多的信号之间也存在干扰，从而降低网络的生存时间。

1.2 PEGASIS路由协议

PEGASIS协议[11-12]的执行过程是，先通过贪心算法把传感器节点组成一条链，设定节点只与距离它最近的邻居节点通信，然后在每轮中只选一个节点作为簇头(或链首)与基站通信。簇头或链首由各个节点轮流担当，通过点对点的方式将监测数据传输至基站，在传输的过程中可以对数据进行融合处理，链首利用“令牌”(token)控制两端的节点将数据传送给链首本身，最后由链首将融合后的数据直接传输给汇聚节点。PEGASIS协议传输数据过程如下图1所示。

相较于LEACHA协议，PEGASIS协议避免了前者频繁选举簇头所带来的额外通信开销，同时链式结构在数据传输的过程中可以将数据进行有效的融合处理，有效地避免了冗余数据带来的额外通信能耗。另外，链式结构使得节点间的通信基本上都是使用最小功率，避免了因距离的增加而使通信能耗呈指数级增长的情况。虽然实验仿真表明PEGASIS协议能够有效地提高网络的能量效率和延长网络的生命周期。但PEGASIS协议也有一些不足之处，如：链的生成算法会不可避免地导致长链的产生，在数据传输时，长链部分会消耗过多的能量而缩短节点的生命周期；PEGASIS采用轮流担当链首的方法选举簇头与基站通信，会产生节点间能量消耗不均衡，导致部分离基站较远的节点过早死亡；每轮结束后都要重新选择簇头然后成链，且当链上只要有一个节点死亡时，链就需要重新构建，这增加了额外的通信开销。

针对上述两个协议的不足，结合LEACH和PEGASIS两个协议各自的优点，笔者在梯度模型的基础上设计了一种新的能量均衡路由协议，该协议分为梯度建立、成簇阶段、网络成链阶段(包括簇内成链和簇间成链)、数据传输4个阶段。在簇头的选举时采用改进的阈值设定算法；簇内成链时设置距离门限和代价函数机制，能有效地避免长链的产生，同时提供能量的利用效率；数据传输阶段采用次级节点备选结合功率控制机制减少数据传输的时延，同时能有效避免因节点失效引起的链的重建，减少开销。

2 网络体系模型

2.1 网络模型

假设无线传感器网络中共有n个节点，均匀分布在SINK节点一侧长度为L的区域内，同时具有以下特性：

1)传感器节点部署后除非节点失效或者能量耗尽死亡，否则网络的拓扑不会变化；

2)各节点结构和功能以及初始能量相同；

3)每个节点都有与网关进行直接通信的能力，并且可以随意进行功率控制；

4)基站位于监测区域一侧外固定位置，其发射功率可以人工控制，并且无能量限制；

5)相邻节点间采集的目标数据具有相关性，支持数据融合；

6)每个节点都具有唯一标识和充分的计算能力，满足不同MAC协议和数据处理对计算性能的要求。

2.2 能量模型

采用文献[5]中的能量模型作为本文协议的模型，如下所示。

数据发送能耗模型：

(2)

数据接收能耗模型：

ETx(k)=Eelec×k。

(3)

数据融合能耗模型：

EGx(k)=Egather×k。

(4)

式(2)为发送数据的能耗模型，ETx(k,d)表示将kbit数据传输距离d时节点的能耗。根据发送节点和接收节点之间的距离远近，又可将功率放大耗损分为自由空间模型和多路径衰减模型。Eelec表示发射电路的耗损能量。εfs和εmp分别表示两种信道模型下功率放大所需要的能量。

式(3)为接收kbit数据的能量耗损模型，仅由发射电路耗损引起。

式(4)为将接收到的n个节点发送过来的nkbit 数据与自身数据融合成kbit数据的能耗模型，Egather为数据融合耗损能量[13-14]。

3 路由协议的优化

3.1 梯度建立阶段

网络建立之初，SINK节点以nR为通信半径，递增地向所覆盖的区域发布当前梯度信息(n=1，2，……，[L/R]，R表示节点通信半径的1/2，[L/R]是向上取整的整数)[8]，节点根据收到的梯度信息，选择最小的梯度值为自己所在梯度。如下图2所示，传感器接收SINK节点广播的梯度信息。

3.2 成簇阶段

梯度建立完毕后，等待一段时间，让所有节点都明确自己梯度的同时让各节点根据信号强弱计算到基站的距离，记为dNB。接着各节点发送NGT(Nid，Gradient，T(n))报文竞争簇头，T(n)为簇头门限值由下式(5)决定。根据SINK节点广播梯度信息的过程，节点可能收到多个梯度的报文，节点A收到节点B的NGT报文后首先比较Gradient，若不等则丢弃；若相同则比较A.T(n)与B.T(n)，值大的进入休眠状态，等待簇头产生，值小的继续广播NGT报文竞争簇头。节点簇头竞争成功后，簇头节点广播Hello(Nid，Gradient)报文告知相邻节点加入成簇。处于监听状态的节点收到Hello报文后，马上向簇头发送申请入簇报文(AFJC)，簇头收到申请报文后，回复确认报文(Re-ack)。

簇头门限值T(n):

(5)

其中，En是节点当前的剩余能量，Einitial为节点的初始能量，Eaverage为网络节点的平均能量，DNB是节点到基站的距离，PRR是节点包接收率。簇头选举算法优先考虑了高剩余能量、高能量利用效率的节点，同时在节点的信道质量和与基站距离之间做了一个折中，均衡了节点的能耗和传输效率。

3.3 网络成链阶段

3.3.1 簇内成链

各节点接收到簇头发送的Hello报文后，根据信号强度计算与簇头的距离dNC，然后发送确认消息AFJC(包括入簇节点的id，dNC)申请入簇,簇头收到AFJC报文后，比较节点距离，确定端节点。和PEGASIS方法一样，也是从最远的节点开始建链。为了防止长链的生成，采用文献[7]的方法设定一个距离门限dthreshold，节点v与节点v+1间的链路距离用dv表示。如果dv大于dthreshold则这条链路为长链。假设已有i个节点加入链，距离门限dthreshold定义：

(6)

其中μ是用户自定义的系数。

假设节点i+1与节点i最近，节点i+2与节点i次近，先将节点i+1和节点i之间的距离dv与距离门限dthreshold进行比较：如果前者小于后者，那么节点i+1直接与节点i相连，然后将节点i+2和i节点之间的距离dv+1与dthreshold比较，若dv+1小于dthreshold，那么将节点i+2记录在节点i下一跳节点备选表中；如果dv大于dthreshold，则表示节点i+1与节点i链接将形成长链，它们不能直接相连，节点i+1继续从链上找出距离自己最近的节点j，此时若节点i+1与节点j之间的距离小于距离门限dthreshold，则节点i+1与节点j直接相连，若大于dthreshold，则长链不可避免，节点i+1直接与节点i相连。建链方法具体实现如图3所示。由文献[15]中依据上述成链方法得到如图4的链。

从图中可以看出该建链方法组成的链是具有多分支的链，距离门限的设置能够有效避免相邻节点间长链的生成，从而节约节点能耗。同时距离门限值也是根据节点情况动态改变。但此方法同PEGASIS协议一样，链上任何一个节点死亡都将重新建链，作者在此基础上提出了在门限值范围内的下一跳节点次级备用节点i+2，当下一跳节点i+1失效时，当前END节点首先查看自身下一跳节点备用表，若有备用节点i+2，则节点i直接与节点i+2相连。若没有，则重新成链。在一定程度上减少了重新成链的开销。

3.3.2 簇间成链

由于是以通信半径1/2建立的梯度。所以簇头节点以正常功率广播簇头成链报文时相邻两梯度值的簇头节点必定能收到。簇头节点根据接收到的梯度值大小信息，按照贪婪算法从大到小依次连接。最后，梯度值最小的的簇头直接与基站通信。

3.4 数据传输阶段

本文算法数据的传输与PEGASIS协议相似[16]，每轮数据的收集都是由基站发送信标(Beacon)触发，簇头接收到信号后，在簇间链向下传播的同时，簇头节点生成控制令牌(token)发送到端节点，然后从端节点启动数据的传输。端节点将数据沿着token来的方向传递给下一跳节点，下一跳节点收到数据后，将其与自身产生的数据进行处理融合，然后继续向下发送。当数据传输到簇头后，簇头节点将数据沿着簇间链向基站的方向传输，下一跳簇头同样要对接收数据进行处理融合。最终，当数据发送到远端的基站时标志着完成了一轮数据的传输过程。数据传输流程如图5所示。

每一轮数据传输完成后，基站都会对Data中各节点捎带的节点信息表NIS(Nid，Gradient，dNB，PRR，En)进行分析，当簇头节点当前能量En为刚当选簇头时能量的1/2时，或簇头节点能量低于一轮通信必需能量时发起簇头重选操作，这时由基站根据节点信息表NIS直接计算得出各梯度簇头，然后广播簇头信息，各节点根据梯度值加入簇。另外当基站在一定时间未收到某簇头发来的Data时，则认为此簇头节点失效，将立即重新启动该簇的链头选举过程。

4 实验仿真及分析

本文采用MATLAB软件仿真，从网络生存周期和数据传输时延两方面比较改进算法与LEACH算法、PEGASIS算法和文献[7]中的CLBG算法。在100m×100m的传感区域内布置100个传感器节点，假设节点不知其地理位置且随机分布，节点可根据需求调节通信功率，其他实验参数如下表。

表1 实验参数设置

本次实验距离门限参数μ取1.5，同时由于随机因素对仿真结果的影响，所以对四种协议各循环计算100次取统计数据平均值，得到如下实验结果。

从实验结果得，LEACH、PEGASIS、CLBG、改进算法四个算法第一节点死亡的时间依次为683轮、780轮、817轮、855轮，节点全部死亡时间分别为1 289轮、1 330轮、1 496轮、1 572轮。可得当WSN网络中有1%、100%节点死亡时，本文算法的通信轮数相对于LEACH算法分别延长了25.1%、21.9%，相对于PEGASIS协议分别延长了9.6%、18.2%。相对于CLBG协议分别延长了4.6%、5.1%。

通过仿真计算四种算法中每轮通信数据端到端的时延来验证本文算法对传输时延的改进情况。结果如下图：

由实验结果可得，当网络中节点存活数较多时，改进算法数据传输时延明显低于其他三种算法；随着节点的死亡，四种算法的数据传输端到端时延都逐渐减少，改进算法虽无LEACH与PEGASIS算法减少得多，但时延仍然低于后两者。

5 结 论

本文算法结合梯度场的概念，在吸取LEACH算法与PEGASIS算法优点的同时，优化了簇头的选择算法，在一定程度上减少了簇头的频繁更换和整个传感网节点能量不均衡问题。此外，在成链阶段设置链长门限值与增加备用下一跳节点，避免了PEGASIS算法中的产生长链问题和节点因意外死亡而重新成链的时延问题。由实验结果可得，改进算法更能降低网络中节点的能耗，延长网络的生命周期，采用分层成链，簇内成链，簇头成链的方式传递节点数据，有效减少了数据的传输时延。

[1] 徐 佳.无线传感器网络路由协议的研究[D].杭州：中国计量学院,2013.

[2] HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNAN H.Energy-efficient communication protocol for wireless sensor networks[C]// Hawaii International Conference on System Sciences.2000:8020.

[3] LINDSY S,RAGHAVENDRA C.PEGAS IS:Power-efficient gathering in sensor information systems[C]//Proceedings of the IEE E Aerospace Conference’02.Montana,2002:1125-1130.

[4] RAGHUNANDAN G H,LAKSHAMI B N.A comparative analysis of routing techniques for wireless sensor networks[C]//Proceedings of National Conference on Innovations in Emerging Technology,2011:17-22.

[5] ZIMMERLING M,DARGIE W,Reason J M.Energy-efficient routing in linear wireless sensor network[C]//Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems,2007:1-3.

[6] ZIMMERLING M,DARGIE W,Reason J M.Localized power-aware routing in linear wireless sensor network[C]//Proceedings of the 2nd ACM International Conference on Context-Awareness for Self-Managing Systems,2008:24-33.

[7] 段 磊.无线传感器网络基于梯度的分级簇算法研究[D].郑州：郑州大学,2009.

[8] 范晓辉,王延年,郑晓庆.链状线型WSN中基于梯度的分簇成链算法[J].计算机应用与软件,2014,31(6):111-115.

[9] 胡 钢,谢冬梅,吴元忠.无线传感器网络路由协议LEACH的研究与改进[J].传感技术学报,2007,20(6):1391-1396

[10] 卢先领,王莹莹,王洪斌,等.无线传感器网络能量均衡的非均匀分簇算法[J].计算机科学,2013,40(5):78-81.

[11] 王 镇.无线传感器网络分簇路由协议综述[J].电脑知识与技术,2011,07(8):1788-1793.

[12] JARRY A,LEONE P,POWELL O,et al.An optimal data propagation algorithm for maximizing the lifespan of sensor networks[C]// IEEE International Conference on Distributed Computing in Sensor Systems.Springer-Verlag,2006:405-421.

[13] 李建奇,曹斌芳,王 立,等.一种结合LEACH 和PEGASIS 协议的WSN的路由协议研究[J].传感技术学报,2012,25(2):263-267.

[14] 刘伟强,蒋 华,王 鑫.无线传感器网络中PEGASIS协议的研究与改进[J].传感技术学报,2013，(12):1764-1769.

[15] 余勇昌,韦 岗.无线传感器网络中基于PEGASIS协议的改进算法[J].电子学报,2008,36(7):1309-1313.

[16] 李文峰,沈连丰,胡 静.传感器网络簇间通信自适应节能路由优化算法[J].通信学报,2012，(3):10-19.

The Optimization and Improvement of Hierarchical Chain’s Routing Protocol Based on Gradient

ZHOU Kun,LI Baolin,LI Shiwei,ZHANG Gangyuan

(College of Computer Science,China West Normal University,Nanchong Sichuan 637009,China)

The life cycle of wireless sensor network is limited by the limitation of energy,and the communication between nodes consumes a large amount of energy,so the design of wireless sensor routing protocol determines the length of the network life cycle.In this paper,according to the characteristics of LEACH and PEAGSIS protocol,the following improvements have been made to the wireless sensor network based on gradient:① in the aspect of cluster heads selection algorithm,the average energy of the network,the packet acceptance rate and the distance between node and base station are incorporated into the algorithm;② chain threshold restriction value are taken into consideration and the alternate next-hop node is increased at the stage of cluster endogenetic chain;③ the thought of a kind of energy binary phase is proposed in the reconstruction of the chain set.The experiments demonstrated that the algorithm can prolong the network life cycle and reduce the end-to-end delay of data significantly.

wireless sensor network;LEACH;PEGASIS;hierarchical chain;cluster head threshold

1673-5072(2016)04-0472-07

2016-03-17

四川省科技厅支撑项目(2013SZ0056，2014SZ0104)

周 坤(1989—)，男，四川遂宁人，硕士研究生，主要从事物联网应用技术研究。E-mail:846240787@qq.com

李宝林(1976—)，男，安徽太湖人，博士，副教授，硕士生导师，主要从事物联网应用技术与大数据分析研究。 E-mail: scu_lbl@sina.com

TP393

A

10.16246/j.issn.1673-5072.2016.04.020