一种基于LEACH与PEGASIS协议的分层成链优化路由算法*

严 英，郭 丽，许建真

(南京邮电大学计算机学院和计算机技术研究所，南京 210003)

无线传感器网络(Wireless Sensor Network，WSN)是散布在一定区域的大量传感器节点，通过无线通信方式形成多跳自组织的网络系统。网络中的节点由电池供电，因其数目多、分布广、所处环境复杂等特点，造成了节点严重的能量约束问题。通常，传感器节点的能量是受限的，当节点的能量耗尽之后，网络便失去了作用。因为WSN由大量低成本的微型节点组成，能量、带宽、计算、存储等资源非常有限。有效管理和使用这些资源，最大限度地延长网络寿命是WSN研究所面临的一个关键技术挑战。因此，网络的能耗和路由协议是无线传感网络的重要研究内容［1］。

在WSN中，节点中的能量大部分消耗在了数据的接收及转发的过程中［2］，由于节点分布的位置不均匀，所以距离基站(Basic Station，BS)远的节点消耗的能量比较快，容易及早死亡。而距离BS较近的节点，也会由于要进行邻接节点数据的融合而消耗大量的能量，加速死亡的概率。这样就导致了节点能耗的分布不均问题。

本文基于PERASIS的链状结构，吸收了LEACH的分簇思想，提出一种新型的分簇分层成链的优化路由算法，既避免了PERASIS协议相邻节点容易形成长链的缺点也解决了LEACH协议的各个节点负载不平衡的问题，使探测区域不容易出现盲区。

1 MSN路由协议比较分析

1.1 LEACH 协议

LEACH协议是一种基于聚类(clustering)的低功耗自适应路由协议［3］，建立在每个节点的能量都是相等的基础上的，把无线传感网络(Wireless Sensor Network)分为以簇为单位的若干单元，在每个簇内都定义一个簇头(Cluster Head)，负责将该簇内各个传感器收集到的信息传输给接收器节点(Sink)。传送以轮为单位，在一轮结束之后，Sink节点负责更换簇头节点，以便进行下一轮的数据传输。这种模式可以有效的降低网络能量消耗，延长网络生存周期［3－4］。

在初始化阶段，每个节点产生一个0～1之间的随机数，如果这个数小于阈值T(n)，则该节点向整个网络广播它是簇头。T(n)的计算公式为［5－6］

p:期望的簇头节点在总的节点中所占百分比;r:当前轮数;G:在剩余的1/p轮中未成为簇头节点的节点集。

节点被选作簇头后，向该簇内各节点通知其是簇头，其余各节点根据接收信号的大小决定加入至该簇，并返回加入信号。簇头，簇内节点与Sink节点的具体数据传输方式如图1所示。

图1 LEACH协议以“轮”传输数据方式

但是LEACH协议存在不足之处:①每轮簇头更换会导致大量能量的浪费，而且在此被选择的簇头，只能保证下一轮不被选为簇头，而以后则不可以保证;②簇头的选择是随机的，簇头的能量剩余问题考虑的不完善，有可能导致某些节点的能量提早耗尽;③在簇头选择完毕之后，开始分簇传递数据，簇头节点管理整个簇的数据接收工作，这样簇内节点同时传送数据会造成簇头的工作量加大，从而导致簇头的能量消耗的过快，生命周期衰减的速度也加快。

1.2 PERASIS 协议

PERASIS协议是一种典型的链状结构的路由协议［7］，它使用贪婪算法把WSN中的所有节点链接成一条链［8］，链上的节点只跟自己的邻接节点通信。从离BS最远端的节点开始构建链，构链完成之后，从远端节点依次向其链接节点传递数据信息，除了端节点之外的其他节点都要进行数据融合之后再传递给自身的邻接节点，直到传递到簇头节点，簇头节点将自己的数据跟接收的数据融合之后传递给BS。当链中有一个节点死亡时，链就需要重新构建［9］。

图2 PERASIS协议构造数据链方式

相比LEACH协议，PERASIS协议取的了以下几个方面的优势:①基于链状的拓扑结构减少了节点之间传送数据的平均距离;②仅仅只有一个LEADER节点向BS传递数据，减少了向远端节点发送的数据量，从而减少了能量的消耗［10］;③PERASIS的建链算法比较简单，时间复杂度为O(n2)。

虽然PERASIS在网络寿命以及能量均衡方面取的了优势，但是还是存在一些不足之处:①长链的出现:由于在链上的某个节点死亡之后会重新构造链，从而死亡节点的邻接节点就不可避免的会出现长链现象，这样就会导致传送数据时，在长链部分会消耗过多的能量而造成节点的生命周期缩短;②簇头节点的更换问题:PERASIS采用的是轮流在链上选择簇头的方式进行簇头与BS之间的通信，如果离BS较远的节点担任了簇头，就会该簇头的能量消耗不均衡问题，导致过早的死亡。

2 优化路由协议LDBPL

基于上述分析，结合LEACH和PERASIS的协议各自的优点，提出一个分簇分层成链的路由算法LDBPL。LDBPL算法摈弃了上述提出的LEACH和PERASIS各自的缺点，采用簇内成链传输数据至簇头，数据汇总后再簇头成链传送数据至BS的分层思想。本算法假设:①节点是静止的，BS知道每个节点的能量信息以及地理位置信息;②每个节点的初始能量均衡;③在每一轮数据传输完毕后，每个节点都能反馈自己的剩余能量信息给BS。

LDBPL算法分为以下几个阶段。

2.1 分簇阶段

与LEACH协议相似，由BS统一管理簇头的选择，但是为了避免LEACH协议随机的选择簇头容易导致整个传感器网络的能量分配不均衡，本协议在选择簇头以及划分簇团范围时采用了文献［11］的方法，从节点的剩余能量以及其地理位置方面考虑簇头的选择问题。文献［11］总体算法是利用等角度分区避免簇头分布不均的问题，根据簇内各节点剩余能量决定簇头的选取，其仿真结果证明了算法具有更高的能量使用率和更长的生存时间。这就避免了LEACH协议的缺点②由于随机选择簇头而导致整个网络的能量不均衡。

根据文献［11］的优化算法得出的簇团结构为:簇头位于簇中心，簇内节点分布均衡，并且区内节点把自身带有的node_id，area_id和标示本身能量的信息传输给它的邻节点，这样同区域内的每个节点都相互知道其它节点的相关信息［11］。这样就为下一阶段的簇内成链阶段奠定了基础。

假设有N个节点均匀分布在M*M区域内k为簇头数，则簇内节点数即为N/k。

从节点到簇头的平均距离计算公式如下:

2.2 成链阶段

LDBPL算法在分簇阶段完成之后，以每个簇为一个集团开始做成链操作，每个簇头在接收完成本簇内的信息之后，BS根据各个簇头的剩余能量选定一个LEADER节点(假设BS选择LEADER节点所消耗的能量全部由BS承担)，再成链传递数据至LEADER节点，之后LEADER节点把数据与自身的数据相融合之后，与BS直接通信。具体操作如下:

(1)簇内成链

借用 PEGASIS的成链方法，由簇头集中管理［12］，根据PERASIS协议的贪婪算法成链，这种分簇成链就会避免整体成链带来的能量的损耗，也可以避免长链的产生。具体成链方法如下:

算法中出现的变量含义表述如下:①V—已经入链的节点，V'—还没有入链的节点;②vi，vj，vk—簇内节点，vhead—簇头节点;③pi，j—节点 vi到 vj传送数据所需要能耗的加权值。

算法描述如下:步骤一:初始状态:V={vhead}，V'={v1，v2，…，vn};步骤二:由 V 广播信息至 V'内各节点，要求报告 pv，j，使得对任意 vj属于 V'，都有pv，i＜ =pv，j，把 vj节点吸收进入 V 集合，V'=V'－{vj};步骤三:循环执行步骤二一直到 V'为空集结束。

整个吸收节点成链的模型图如下(节点之间的虚线说所示的数字是节点之间相互传送数据所消耗的能耗加权值 Pi，j):

图3 PERASIS分链成图

图4 PERASIG分链详细图

本算法采用无线通信模型，发送传输n bit的数据到距离为d2的接收方所消耗的能量为:

其中，Eelec表示发射电路消耗的能量;￡fs和￡mp为信号放大器所消耗的能量;d0为常量。

节点接收n bit的数据所消耗的能量为:

将M个长度为n bit的数据包融合所消耗的能量为:

其中，k表示簇头数目;N/k表示整个WSN一共有多少个簇;EDA表示簇头进行数据融合所消耗的能量。则簇头消耗的总能量为:

(2)簇头成链

成链步骤跟簇内成链的步骤大体相同，其中有一个主要的区别，即BS选择簇头的LEADER节点时，考虑到了簇头节点的剩余能量以及距离BS的距离。也就是说BS在选择LEADER节点的时候会优先选取剩余能量多而且距离近的簇头节点，这样在数据传送的时候就会减少能量的消耗。

簇头成链的步骤如下:①由BS发出广播相信，要求每个接受到信息的簇头节点反馈node_id以及area_id;②收到BS广播信息的簇头开始单播的发送反馈信息给簇头，其他的非簇头节点则不做任何反应，进入休眠状态;③在BS接受到簇头节点的反馈的信息做以下计算:

(xi，yi，zi)是簇头节点的坐标;(XBS，YBS，ZBS)是BS的坐标;E剩:表示簇头的剩余能量;Qi:表示d与E剩的函数。

④BS把Qi最大的节点设置为LEADER节点，广播给所有的簇头节点LEADER节点的node_id并且从远离LEADER节点的簇头节点开始建链;⑤建链的过程同簇内成链的步骤一样;⑥建链完成之后的数据传输与PERASIS协议声明的一样，从最远端输送数据给相邻节点，相邻节点接收到数据之后与自身的数据融合在传送到次相邻节点，以此类推。直到簇内所有成链的节点把数据传送给LEADER节点，LEADER节点在进行自身的数据融合之后传送给BS。到此，整个LDBPL算法一轮完成。

下图表示在一个100 m×100 m的范围内有60个传感器节点，利用LDBPL建链方法得到的链如图5所示。

图5 LDBPL方法成链方法

与PEGASIS算法一样，在LDBPL算法中，无论是簇内成链还是簇头成链，只要链上任何一个节点死亡都将重新按上述方法重新建链，并且LDBPL没有增加计算的时间复杂度，其时间复杂度和PEGASIS算法一样为O(n2)。

LDBPL算法采用了文献［10］的思路，即不是在每轮通信之后重新选择簇头节点，而是在一定轮数的通信完成之后才选择节点，这就节省了簇头重新选择耗费的大量不可再生的能源。根据文献［10］的仿真算法可以得出这类思想一定的延长了WSN的网络生存时间。该思想根据节点的剩余率的多少来计算重新选择簇头节点的轮数。

表1 剩余率与选择簇头关系表

值得注意的是:LEADER节点是在每轮通信之后就重新选择，这是考虑到了LEADER节点直接与BS通信的耗能问题。由于LEADER节点是从簇头节点中选取的，簇头在簇内成链，簇头成链以及数据融合节点消耗了大量的能量。如果LEADER节点也根据上述表格每隔一定的轮数选取，会导致LEADER节点的能耗过早的消耗完毕，使得整个WSN负载不均衡。

3 仿真结果及分析

本文利采用了MATLAB软件对LDBPL算法，LEACH算法和PEGASIS算法进行了对比，分别从网络生存周期和数据传输时延两方面考虑，评价LDBPL算法的性能。在范围为100 m×100 m的区域内有100个传感器节点，设节点的坐标值在(0，0)～(100，100)范围内变化，BS的位置位于(50，175)的位置上，节点的初始能量Eo=1 J，发送和接收电路通信耗能Eelec=50 nJ/bit，数据融合耗能EDA=5 nJ/bit/signal，￡mp和￡fs分别为 0.001 3 pJ/bit/m4、10 pJ/bit/m2。

LDBPL算法改进了以往算法中节点负载不均衡，能量消耗差异等缺点，以延长整个网络生存周期为设计目标。其中图6表示的是LDBPL协议与LEACH协议，PEGASIS协议节点生存周期的比较。由于传感器的节点分布，簇头的选择以及成链的随机因素很大。所以，每种协议循环计算100次取其平均值从而得到结果。

图6 100个节点的网络生存时间

由仿真结果得出:LEACH协议的第一个节点死亡和全部节点死亡分别出现在第在第700轮和第1 250轮;PEGASIS协议的第一个节点死亡和全部节点死亡分别出现自第780轮和第1330轮;而LDBPL协议的第一个节点死亡和全部节点死亡分别出现在第850轮和第1 520轮(以上均为模糊取值)。同时本文还计算了当整个WSN网络中有1%、20%、50%、100%节点死亡时，LDBPL算法的通信轮数与LEACH算法以及PEGASIS算法的比较，可得出LDBPL算法相对于LEACH算法在分别延长了25%、38%、47%、56%相对于PEGASIS分别延长了19%、31%、35%和45%。

LDBPL算法还缩短了数据传输间的时延问题。本文通过仿真计算LEACH协议、PEGASIS协议以及LDBPL协议中每轮通信数据的端到端时延来验证数据传输时延的改进情况。

图7 节点的端到端时延

LEACH协议的数据传送:在成簇阶段完成之后，簇内节点开始按照TDMA方式向簇头节点传送数据信息，待簇头节点接收到簇内全部节点的数据之后开始进行数据融合，数据融合完成后发往BS，故LEACH协议的数据传输时延为:簇内节点到簇头的的传输时延与簇头到BS传输时延之和。由于节点的分布是随机的，而且数量众多，所以计算的是数据传输时延最长的一轮，故端到端传输时延如图7所示。

其中，D(Ni)表示簇内节点到簇头的时延。

PEGASIS协议的数据传送:整个WSN内的节点成链，之后在链中选择一个领导节点，领导节点在接收到链中所有节点的数据之后，与自己的数据进行融合，融合之后再发往BS。故PEGASIS协议的数据传输时延为:整条链中节点传递数据的时延与领导节点到BS的传输时延之和。

其中，DL_BS表示CH到BS的时延

LDBPL协议的数据传送:分簇之后先簇内成链，簇头节点接收到簇内的数据之后再簇头成链，之后传递给LEADER节点进行数据融合后发往BS，忽略BS进行LEADER节点选择所引起的时间迟延。故LDBPL协议的数据传输时延为:簇内节点链传输数据的时延，簇头成链传输数据的时延以及LEADER节点发往BS的传输时延三者之和。

其中，dij为第i个簇中的第j个节点。

仿真证明LDBPL协议相对于LEACH协议以及PEGASIS协议在网络生存周期和数据传输时延方面有一定的改进，使用LDBPL协议均衡了网络节点的能耗，也节省了网络节点在传送数据以及每轮更换节点的能量消耗。

4 结论

LDBPL协议吸取了LEACH协议和PERASIS协议的优点，改善了LEACH协议中每轮随机选择节点当簇头以及频繁的更换簇头而导致的整个传感网络节点能量不均衡的问题，同时也避免了PERASIS协议所产生的长链问题。采用均匀成簇，簇内成链，簇头成链的方法传递整个WSN中节点的数据信息。由仿真结果可得，改进的新协议更加的能节省节点能量，延长网络的生命周期并且分层的成链操作减小了数据的传输时延。

［1］李晓维，徐勇军，任丰原.无线传感器网络技术［M］.第1版.北京:北京工业大学出版社，2007:1－17.

［2］罗玉红，陈松乔，王建新.移动自组网中能量有效的路由算法［J］.计算机工程及应用，2004，36:15－21.

［3］Wendi Rabiner Heinzelman，Anantha Chandrakasan，Hari Balakrishnan.Energy-Efficient Communication Protocol for Wireless SensorNetworks［J］.IEEE Computer Society，2000(8):30－47.

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

［5］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks，Proc.of the 33rd Annual Hawaii International Conference on System Sciences(HICSS)［M］.January 4 ～ 7，2000.Maui，Hawaii.p.3005－3014.

［6］Heinzelman W.Energy—Efficient Communication Protocol for Wireless Microsensor Networks［A］.Proceedings of the 33rd Annual Hawaii International Conference on System Sciences［C］.Hawaii，USA，2000.4－7.

［7］Stephanie Lindsey，Cauligi S，Raghavendra.PEGASIS:Power Efficient Gathering in Sensor Information Systems［J］.IEEE Aerospace Conference Proceedings，2002，3(3):1125－1130.

［8］张震，闫连山，潘炜，等.基于LEACH和PEGASIS的簇头成链可靠路由协议研究［J］.传感技术学报，2010，23(8):1173－1178.

［9］Jung Sung-Min，Han Young-Ju，Chung Tai-Myoung.The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS［C］//Proceeding of 9th International Conference on Advanced Communication Technology，2007:260－265.

［10］余勇昌，韦岗.无线传感器网络中基于PEGASIS协议的改进算法［J］.电子学报，2008，36(7):1309－1313.

［11］丁睿，南建国.基于LEACH协议簇头选择算法的改进［J］.微计算机信息，2009，24:187－189.

［12］姜华，郑春雷，刘海涛.无线传感网络中链路级能量有效策略的研究［J］.传感技术学报，2006，19(6):2738－2742.