WSN自适应负载均衡集簇分层路由协议

孙 扬，何建忠

(上海理工大学光电信息与计算机工程学院，上海200093)

0 引言

相比于传统网络，无线传感器网络 (wireless sensor network，WSN)具有节点能量受限、动态性、自组织性、以数据为中心等特点，这也就决定了在设计WSN路由协议时必须将重点放在如何更有效地利用有限的节点能源上面，同时应充分考虑网络拓扑的动态变化，以数据为中心，保证网络的健壮性和实时性。另外，在实际应用背景中，网络中的传感器节点往往是非对等的，也就是节点在初始能量、计算能力以及通信能力上往往存在着差异，而这往往会对WSN路由协议的设计产生重要影响。传统的WSN路由协议从不同的角度力求均衡网络中各节点功耗，同时最大化网络寿命。但是，在不同应用背景下，这些路由协议也都存在着各自的缺陷。针对这些问题，本文提出了一种自适应负载均衡集簇分层路由协议——ALBCH(adaptive load balancing clustering hierarchy)，从多个层面对传统路由协议进行了综合性的改进，并通过引入剩余能量因子等方法使本协议可以适用于实际应用中非对等节点构成的网络，实现网络整体负载均衡和网络生存周期的延长。

1 LEACH和PEGASIS协议分析

1.1 LEACH协议

文献［1］提出了一种低功耗自适应集簇分层路由协议——LEACH(low energy adaptive clustering hierarchy)，它的核心思想是:将整个网络中的节点划分为若干个簇，每个簇内随机选举出一个簇头节点，簇内节点都通过簇头结点与基站进行通信，以减少直接与基站进行通信的节点的数量。该协议按轮进行通信，每轮分为建立阶段和稳定阶段，在建立阶段以自组织的方式进行簇头的随机选举，选举出的簇头节点进行广播，未被选为簇头的普通节点根据收到的信号强弱选择加入的簇;稳定阶段，节点采集到的数据首先发送到簇头节点，簇头节点进行数据融合后将收集到的信息发送到基站。由于每轮簇头是随机产生的，这样可以较好得平衡节点耗能，达到负载平衡的目的。

在LEACH的基础上，包括该协议作者在内的一些研究者进行了一系列基于集簇分层思想的改进，比如LEACHC［3］提出了中心化的成簇算法以解决簇头节点分布不均的问题;还有学者提出簇头节点间通过MTE(minimum transmission energy)［4］方式向基站发送数据以节省能量的策略，如图1所示。

图1 LEACH和PEGASIS协议

1.2 PEGASIS协议

PEGASIS(power efficient gathering in sensor information systems)是一种基于贪婪算法的路由策略。它本质上是LEACH的增强算法，其核心思想与LEACH是一致的，那就是尽量减少直接与基站进行通信的节点的数量［5］。它首先使用贪婪算法构成一条边长之和接近最小的链。该策略在每轮会选举一个链内簇头节点，当通信开始的时候，数据会从最远端节点开始沿链向簇首节点发送，每经过一个节点都会进行一次数据融合，直到到达簇首节点后由簇首节点将融合后的数据发送到基站。

1.3 两种协议的分析与比较

由于两种协议基本策略的差异，在实际应用场景中他们具有各自的特点，总结见表1。

表1 LEACH和PEGASIS优缺点对比

通过对比分析我们发现，LEACH和PEGASIS在很多方面，比如整体耗能均衡、实时性、容错性等特性上具有一定的可互补性，这就为我们在这两个协议的基础上进行改进提供了必要的可行性。另外，由LEACH和PEGASIS协议的原始文献，作者在分析讨论前都假设网络内所有节点是同构节点，也就是初始能量、计算能力、通信能力是一致的，而这是与实际应用中具体的节点情况不符的;同时PEGASIS中的贪婪算法机制本身也有一定的缺陷。因此，本文提出一种自适应负载均衡集簇分层路由协议——ALBCH(adaptive load balancing clustering hierarchy)，以解决上述问题。

2 改进算法描述

2.1 网络模型

本文讨论的WSN基于以下假设:

(1)所有N个传感器节点位于一个正方形区域S内。(2)所有节点部署后不再发生移动且不需人工维护。

(3)基站位于离S较远的固定位置，且其能量不受限。(4)网络内各节点初始能量、处理能力不对等。

(5)在每轮通信中各节点耗能不统一。

其中前3项是一般讨论WSN路由协议时使用的典型配置，后两项旨在讨论本协议对异构网络节点的处理能力。

2.2 簇头选举

当网络部署完毕或每次新节点被播撒加入网络后，每隔一定时间都要进行簇头的选举。在文献［1］中，采用以下方法确定当前节点是否当选为簇头:节点n每轮产生一个0到1之间的随机数，然后该随机数与阈值T(n)进行比较，若该随机数小于T(n)，则该节点n当选为本轮通信的一个簇头。阈值T(n)由以下公式产生

式中:P——簇头节点在总节点中所占的比例 (LEACH中经计算选取0.05为最佳)，r——当前轮数，n——当前还未被选为过簇头的节点的集合。

显然，这种选举办法是不适用于非对等节点构成的网络的。我们这里说的非对等包括了以下3种情形:

(1)节点本身在初始能量、计算能力、通信能力上有一定的差距;

(2)网络在运行一段时间后由于其所处环境的复杂性造成节点的耗能不均而产生的不对等;

(3)由于节点不可避免的死亡需要定期向网络中添加部署新节点才能保证系统的健壮性，这样也会产生剩余能量上的非对等现象。

为适应这些情况，对阈值计算公式进行改进

其中En为节点n剩余能量，ET为设定的剩余能量阈值，具体取值由实际节点参数决定。Pe为剩余能量相关因子，它由当前节点剩余能量和网络节点平均剩余能量的比值决定

因为让每个节点都知道网络的实时剩余能量是很难实现的，此处我们使用的节点平均剩余能量采用的是由通信轮数所计算的估计值，使用该估计值并不会影响算法的性能。本文我们采用文献［3］所提出的无线电能耗模型，发送长度为k比特的信息至距离d处所产生的能耗为

接收此信息耗能为

其中Eelec为发送或接收电路每处理1比特数据所消耗的能量，εfsd2和εmpd4分别为放大电路使用无线电自由空间模型和多径传播模型时的耗能，采用哪种模型主要取决于到接收器的距离和可允许的比特差错率。设已知N个节点的网络初始节点总能量为Einit，网络生存周期为T，则网络启动时间t后节点的平均剩余能量为

由于Einit已知，只需估算出网络的生存周期T即可计算出平均剩余能量。由上述无线电能耗模型，每轮通信消耗的能量估计值为

式中:Ec——节点进行数据处理的耗能，dBS——簇头与基站的平均距离，dCH——节点到簇头的平均距离。可以推导得到，在边长M的正方形区域中，为便于计算，设基站位于区域正中间，则

在理想情况下，有

整理代入即得平均剩余能量的估计值。

C为节点计算能力相关因子，由具体节点处理资源决定。因为一般设计的传感器节点处理能力与其电池容量有一定的约束关系，所以通常不必考虑两者不协调的情形。加入计算能力相关因子主要是出于提高网络整体实时性的考虑，因为在本协议体系中作为簇头节点相比普通节点有更多的机会参与数据融合处理和数据转发，所以簇头节点处理能力的快慢势必会影响到整个网络的延迟程度，在一些对实时性要求较高的网络中加入相关因子是必须的，而处理资源相对均等的网络时C的值可以直接置1。

由于剩余能量因子的引入，非对等节点由于作为簇头所引起的能耗将得到最大程度的均衡，并使得该协议可以应用于能量异构型网络，增强网络的可拓展性和可维护性。通过设定剩余能量阈值ET，剩余能量低于该阈值的节点将不再被选为簇首节点，大大延后节点首次死亡时间，延长网络生存周期。计算能力相关因子的引入对于网络整体实时性的增强提供了一定的帮助。

2.3 簇的建立和簇内通信

当簇头选举完毕后，当选为簇头的节点发送一个广播信息，附近的普通节点根据收到的广播信号的强弱来决定以哪个簇头作为簇首，并向簇头节点发送确认消息，并将自己的簇标志位CLUSTER_FLAG(大小写?)设为簇头节点ID。然后，在每个簇内指定任意非簇头节点开始，使用改进后的贪婪算法进行成链运算，将所有CLUSTER_FLAG值相同的节点 (含簇头节点)构成一条长链。如图2所示，当有数据要发送时，当开始收集网络数据的时，首先由本轮簇头节点c向d节点发送一个ACK信令 (非常小，带来的能量损耗可忽略)，d节点收到后依次传送该信令直至右侧端节点e;当端节点接收到ACK指令后，就将传感器模块收集到的数据发送到节点d，节点d收到e节点的数据后，将该数据与自身传感器模块收集的数据进行数据融合后发送到下一节点，依此操作直到到达簇头节点;同时，对链的另一端进行类似的处理。

图2 ALBCH基本成链机制

2.4 簇头与基站的通信

与LEACH不同的是，本协议不再采用简单的多跳路由的方式来进行簇头与基站间的通信，这主要是因为如果采用多跳路由的方式，靠近基站的簇头节点必然会过多地参与数据的转发，相应的其能耗就会过大，造成近基站节点早死的问题。

当所有簇内的节点数据经融合收集并到达簇头节点后，采用与前述簇内通信类似的机制将所有簇头节点构成一条长链，然后这些簇头节点经过二次选举再选出一个簇头来，所有簇头通过这个更高级的簇头与基站进行通信。需要注意的是，本协议的二次选举区别于PEGASIS成链策略的是:PEGASIS中是采用链上节点轮流作为簇头节点的方式，而本协议继续使用式 (2)中与剩余能量和计算能力的关联，进一步均衡网络负载和减少延迟。

2.5 改良后的贪婪算法

2.5.1 长链问题

PEGASIS中的贪婪成链算法存在长链问题，如图3所示。由于传统的贪婪算法总是取局部最优解，当由节点1发起成链过程后，始终是选择最短路径作为下一跳，这就导致节点8即使与链路前端节点距离较近，但仍然会被插入到链路的远端，从而大大增加了通信耗能，这就是所谓的长链问题［6］。

图3 长链问题

2.5.2 距离阈值法解决长链问题

为解决长链问题，在贪婪算法成链过程中加入距离阈值机制，设当前跳数为N的链中包含的节点集为S={s1，s2，s3，…sN}，成链过程由 s1发起，且已对 s1～sk-1完成成链，那么在对当前局部最优解节点sk进行如下入链处理:设定一个距离阈值L，链上节点集S中各节点的距离为Dis(si，sj)(i N，j N，i≠ j)，令 L= αMax［Dis(si，sj)］，α取值由具体网络情况决定。

(1)若Dis(sk，sk－1) L，说明该链接非长链，则节点sk即为下一跳节点，并继续成链过程;

(2)否则，若 Dis(sk，sk－1)＞ L ，将 Dis(sk，sk－1)与链上各节点到节点sk的距离逐一对比:

1)若对 i＜k，有

则说明此长链不可避免，节点sk仍作为下一跳节点，并继续成链过程;

2)若式 (10)不成立，设对 i＜k，有

此时将 Dis(sk，sj－1)与 Dis(sk，sj+1)进行比较，若 Dis(sk，sj－1)较小，则将节点sk插入到sj-1和sj之间，从节点sk-1继续成链过程;若式 (11)不能满足，则说明此长链不可避免，节点sk仍作为下一跳节点，从节点sk继续成链过程。

3 仿真结果及分析

本文使用Matlab软件平台对ALBCH协议进行仿真。搭建虚拟网络环境基本参数如表2所示。

另外，取ACK信令长度为25bit，根据所搭建的网络环境参数，计算能力因子C取1，多次仿真后确定距离阈值参数α较理想取值为1.4。

ALBCH协议相比LEACH和PEGASIS可以进一步均衡网络负载，同时延长首次节点死亡出现的时间。由于簇头分布、成链过程等的随机性较大，我们采取每种协议循环仿真50次后取平均值的方法对所得的节点存活个数进行统计。首先将节点初始能量均设为1J，已验证ALBCH在处理同构网络时的能量性能。图4为所得仿真结果。

表2 仿真参数表

图4 三种协议在同构网络环境下能耗仿真结果

由仿真结果我们可以看到，在应用于节点完全对等的网络时，LEACH协议的首次节点死亡时间和节点全部死亡时间分别出现在第570轮和第1210轮;PEGASIS协议的首次节点死亡时间个节点全部死亡时间分别出现在第760轮和第1480轮;而ALBCH协议的首次节点死亡时间和节点全部死亡时间则分别出现在第850轮和第1590轮。ALBCH协议在处理同构网络时较LEACH和PEGASIS分别延长了网络生存周期达49%和12%。

ALBCH在处理异构网络时对网络生存周期的改善就更加明显。我们将100个节点分别按1:1:1:1的比例分别取初始能量为0.5J、1J、1.5J、2J，重新进行仿真，所得结果如图5所示。

由仿真结果，在所给定的异构网络环境下，ALBCH相比LEACH和PEGASIS分别将生存周期延长了185%和72%。剩余能量因子的引入使得能量非对等节点网络各节点的负载得以均衡，大大延后了节点死亡时间。同时对贪婪算法的改进也使得网络生存周期进一步延长，整个协议取得较高的能量效率。

ALBCH协议还大大减轻了PEGASIS在采用贪婪算法链状机制时的时延问题，从而可以应用在一些对实时性要求较高的网络中。图6为三种协议在同构网络中进行通信时数据的端到端时延的仿真统计。

图5 三种协议在异构网络环境下能耗仿真结果

图6 三种协议端到端时延仿真结果

节点数为20、50、100时，ALBCH的平均端到端时延分别比LEACH减少了20%、22%、31%，比PEGASIS减少了200%、260%、300%(约略值)。由于采用了更完善的分簇机制，ALBCH使链状机制所带来的时延大大减少，提高了网络的实时性。

仿真结果证明，ALBCH比LEACH和PEGASIS具有更好的均衡负载能力、低能耗特性和实时性能，并且克服了后两者在异构网络中的局限性，在应用于能量非对等节点网络中具有非常大的优势。

4 结束语

本文在综合考虑LEACH和PEGASIS优缺点的基础上，结合实际应用中节点的不对等性，提出了一种自适应负载均衡集簇分层路由协议。该协议分别将改进过的贪婪算法成链机制引入分簇网络的双层结构，并在簇头选举时充分考虑节点剩余能量，使其在处理异构网络时具有更好的性能。该协议相比LEACH和PEGASIS在网络能耗、负载均衡、网路实时性和健壮性等方面都有显著提高。

［1］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy efficient communication protocol for wireless microsensor networks［J］.IEEE Computer society，2007:3005-3014.

［2］Lindsey S，Raghavenda CS.PEGASIS:Power efficient gathering in sensor information systems［C］//Philadelphia:Proceeding of the IEEE Aero space Conference，IEEE Press，2009:1125-1130.

［3］Heinzelman W，Chandrakasan A，Hari Balakrishnan.An application specific protocol architecture for wireless microsensor networks［J］.IEEE Trans on Wireless Communications，2009，1(4):660-670.

［4］LIU Ming，GONG Haigang，MAO Yingchi.A distributed energy efficient data gathering and aggregation protocol for wireless sensor networks［J］.Journal of Software，2005，16(12):1000-9825(in Chinese).［刘明，龚海刚，毛莺池.高效节能的传感器网络数据收集和聚合协议 ［J］.软件学报，2005，16(12):1000-9825.］

［5］JUNG Sungmin，HAN Youngju，CHUNG Taimyoung.The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS［C］//Seoul:IEEE The 9th International Conference on Advanced Communication Technology，2007，3(1):260-265.

［6］Cortez R Andres，Fierro Rafae，Wood John.Heterogeneous sensor network for prioritized sensing［C］//New York:IEEE 2011 IEEE/RSJInternational Conference on Intelligent Robots and Systems，2011:2333-2339.

［7］Akshay N Kumar，Harish M P，Dhanorkar S B.An efficient approach for sensor deployments in wireless sensor network［C］//Detroit:IEEE Technologies Internati-onal Conference on Digital Object Identifier，2010:350-355.

［8］Kee-Young Shin，Junkeun Song，JinWon Kim，et al.REAR:Reliable energy aware routing protocol for wireless sensor networks［C］//Seoul:IEEE The 9th International Conference on Advanced Communication Technology，2007，3(1):525-530.

［9］Euisin Lee，Soochang Park，Fucai Yu，et al.Communication model and protocol based on multiple static sinks for supporting mobile users in wireless sensor networks ［J］.IEEE Transactions on Consumer Electronics，2010，56(3):1652-1660.

［10］LI Xin，ZHOU Chan，FEI Minrui.Wired/Wirless heterogeneous network performance comprehensive evaluation［C］//Shanghai:WRI Global Congress on Intelligent Systems，2009:399-403.

［11］Yonis O.HEED:A hybrid，energy-efficient，distributed clustering approach for ad-hoc sensor networks［J］.IEEE Trans on Mobile Computing，2006，3(4):366-379.

［12］Manjeshwar A，Agrawal D P.TEEN:A routing protocol for enhanced efficiency in wireless sensor networks［C］//Memphis:Internatonal Proceeding of 15th Parallel and Distributed Processing Symposium，2006:23-27.