一种分布式无线传感器网络能量均衡路由算法

刘湘雯1　薛　峰2　李　彦1　于宏毅3　胡捍英3

(空军工程大学电子科学系　西安710051)1　(武警陕西省总队通信站　西安710054)2

(信息工程大学通信工程系　郑州450002)3

摘　要　针对无线传感器网络的能量均衡问题,基于一种度量局部能量均衡性能指标,提出了一种基于预测的分布式

能量均衡路由(Predicting2basedDistributedEnergyBalancingRouting,PDEBR)算法。PDEBR基于地理位置信息,结合功率控制,以分布式方式达到能量有效性的目标。最后,对PDEBR的性能进行了仿真分析,结果表明PDEBR可以有效延长网络寿命。关键词　无线传感器网络,能量均衡,网络寿命中图法分类号　TN919　　　文献标识码　A　

DistributedEnergyBalancingRoutingAlgorithminWirelessSensorNetworks

LIUXiang2wen1　XUEFeng2　LiYan1　YUHong2yi3　HUHan2ying3

(DepartmentofElectronScience,AirForceEngineeringUniversity,Xi’an710051,China)1(ShaanxiPeople’sArmedPoliceCorps,CommunicationStation,Xi’an710054,China)2

(DepartmentofCommunicationEngineering,InformationEngineeringUniversity,Zhengzhou450002,China)3

Abstract　Aimingattheenergybalancingissueinwirelesssensornetwork(WSN),basedonalocalenergybalancingmetric,predicting2baseddistributedenergybalancingrouting(PDEBR)algorithmwasproposed.PDEBRgetstoenergyefficiencywithgeographiclocationinformationandpowercontrol.PDEBRwascomplementedwithdistributedstyle.ThesimulationresultsshowPDEBRcanprolongnetworklifetimeefficiently.Keywords　Wirelesssensornetworks,Energybalancing,Networklifetime　　　无线传感器网络(WirelessSensorNetwork,WSN)中,传感器节点主要依靠电池供电,因此能量是极为重要的网络资源。最大限度地提高节点及网络的能量有效性,使网络以有限的能量工作尽可能长的时间,是该类网络的主要设计目标之一[123]。能量消耗的不合理可以分为无效的能量消耗和不均衡的能量消耗。无效能量消耗由空闲侦听、监听等引起,不均衡能量消耗由无线传感器网络的特性带来,例如事件感知的不平衡、数据传输不对称(多对一)等。提高能量有效性的方法包括:从器件角度降低数据获取、处理和通信所需要的基本能耗参数;通过休眠机制,降低节点在空闲状态无谓的能量消耗,这属于休眠调度问题,既要考虑连通性,又要考虑网络覆盖;能量均衡消耗机制。我们主要研究WSN提高能量有效性的能量均衡消耗机制。

向能量不均衡,一方面是所有数据都要传送到Sink,另一方面是Sink节点数量少,通常只有一个Sink。这种数据流的方向性以及业务的多对一特性,导致距离Sink近的节点的能量消耗比较大。对于能量均衡问题,可以从多个角度来解决:功率控制的角度[527]、考虑传感器网络特点的数据压缩的角度[6]、路由的角度、多Sink和移动Sink的角度[8]以及节点密度控制的角度[9]等。

路由是解决能量均衡的一个重要方法,文献[10]针对格状规则网络拓扑,提出了边界转发策略———DSAP(Direction2

alSource2AwareProtocol),在选择源到目的的路径时,让边

界节点完成分组转发。边界转发要比内部转发的能量均衡性能好,这是因为边界节点的邻居节点个数少,需要其帮助完成转发的分组个数少,并且侦听能耗比较小。DSAP没有路由表,并且以边界转发提高了网络的能量均衡性能。但是边界转发会带来比较多的端到端能量消耗。而且,边界转发的可扩展性差,这是因为随着边界其节点个数的增加速率要低很多。文献[11]基于一种基于流量规划的路由策略,采用线性规划的方法,提出了一种基于线性规划的集中式能量均衡路由算法(CentralizedEnergyBalancingRouting,CEBR)。CE2

1　WSN能量均衡路由技术

能量均衡可以分为横向均衡和纵向均衡[4]。导致横向能量不均衡有两方面的原因:一方面是低能量节点总是先于高能量节点中继数据,造成不均衡的累积,这是可以人为控制的;另一方面是事件发生的不均衡,这是不可控制的。导致纵

到稿日期:2009202225　返修日期:2009204230　　本文受CNGI示范工程项目(CNGI20421021D),国家自然科学基金(60472064)资助。刘湘雯(1977-),女,博士,讲师,主要研究方向为无线传感器网络路由等,E2mail:wujingkj@126.com;薛　峰(1976-),男,工程师,主要研究方向为视频通信等;李　彦(1963-),男,教授,主要研究方向为信号处理等;于宏毅(1963-),男,教授,博士生导师,主要研究方向为信号处理、无线网络等;胡捍英(1961-),男,教授,博士生导师,主要研究方向为第三代移动通信技术等。

・122・

BR的基本思想是网络中有一个中心控制节点,中心控制节点

认为是Sink节点,由Sink节点收集全网拓扑信息,并在每一轮开始时收集所有节点的能量信息。然后利用非线性规划,求解每条链路的最佳转发概率,并把计算得到的链路转发概率分发到每个节点。每个传感器节点根据可达链路的概率选择一个下一跳节点进行转发分组,使得能量均衡性能达到最佳。这种做法如果不考虑收集拓扑信息以及能量信息的开销,就会得到接近最优的优化结果。但是,CEBR的控制开销比较大,需要收集全网拓扑信息;需要在全网散播概率转发表;每一轮开始时,每个节点都需要向Sink更新能量信息。CEBR以集中式方式实现,当网络规模比较大时,开销会随着网络规模的增大而不断增大,可扩展性比较差。

本文结合功率控制机制,从路由的角度提出一种分布式基于局部拓扑信息的能量均衡路由算法PDEBR(Predicting2basedDistributedEnergyBalancingRouting)。PDEBR具有如下几个特点:首先,采用本地能量均衡,达到了次优的全网能量均衡;其次,在PDEBR中,每个节点根据判断哪个邻居节点作为下一跳可以达到比较好的局部能量均衡性能而选择其作为当前下一跳,是一种分布式的、基于局部网络状态信息的工作机制,具有良好的稳定性和可扩展性,比较适合WSN无中心控制、节点容易失效等特点。通过对算法性能仿真分析的结果表明,PDEBR可以有效延长网络寿命。

1)传感器节点随机均匀分布。

2)所有节点的地理位置信息已知。

3)每个节点可以根据自己到下一跳节点之间的距离,动

态调整自己的发射功率。

4)所有传感器节点类型相同,并且初始能量相同。采用文献[8]、文献[12]以及文献[13]等广泛采用的节点能耗模型,即节点i到j发送长度为lbit的分组消耗的能量为

k

(2)Et-ij=l(α12+α2di,j)

接收长度为lbit的分组的能耗为

Er=αl11

(3)

ααα其中,发射机基带电路和发射11,12,2分别为接收机电路、机放大电路的能耗参数。令α1=α11+α12,di,j为节点i到j的距离,l为分组长度,k为路径衰减因子,一般为2～4之间的整数。

3.2　PDEBR的基本思想

首先给出前向邻居节点的定义。定义1(前向邻居节点)　当前节点距离目的更近的邻居节点。如图1所示,节点1的前向邻居节点为节点2和节点3。

2　能量均衡的度量指标

对于WSN来说,采用集中式方式可以达到全网能量均衡。但是,随着网络规模的增大,集中式方式会带来比较大的控制开销,协议的可扩展性比较差。而利用局部信息以分布式方式实现全网能量均衡,是提高网络可扩展性的一个重要出路。

对于网络中某一个节点来说,若以局部信息实现能量均衡,只能最小化与自己一跳的邻居节点的均方差,这可以认为是一种局部能量均衡方式。如果网络中所有节点都能够达到局部能量均衡,也就能够接近全网能量均衡的目的。采用节点剩余能量的均方差φ来衡量网络能量均衡的程度,即局部能量均衡的度量指标为

φlocal=

∑(Ei-Ek)2

i图1　PDEBR基本思想

PDEBR的基本思想为:①利用地理位置信息约束最小能

量路径。根据邻居节点的地理位置信息,分组只发送给前向

节点,这些节点构成下一跳备选集Ω。这使得分组不断向距离Sink更近的方向前进,从而保证了端到端传输能耗比较小。②以式(1)的φlocal为度量指标达到局部能量均衡。分别预计算Ω中各个元素作为下一跳后的局部能量均衡性能φlocal,选择使得局部能量均衡性能最好的节点作为下一跳。

下面以图1为例说明PDEBR路由过程。本例中,节点1要向Sink发送一个数据分组,节点的基本处理过程如下:

1)节点1根据自己以及邻居节点与Sink之间的距离确定下一跳备选集Ω,Ω={2,3}。

2)节点1分别估算把分组发送给备选集中的节点2或者节点3之后的局部能量均衡性能。Ee表示估计的节点剩余能量,Ec表示节点的当前剩余能量。节点1以自己发送分组后估计的剩余能量Ee1、选择节点2或者节点3之后估计的剩余能量Ee2或者Ee3,以及邻居节点4的当前剩余能量Ec4,计算局部能量均衡性能。根据式(1),节点1把分组发送给节点

2后的局部能量均衡性能为

(Ee1-Ek2)2+(Ee2-Ek2)2+(Ec3-Ek2)2+(Ec4-Ek2)2

k

,i=1,2,…,k(1)

其中,k为节点的邻居节点个数加1。Ek是k个节点能量的

∑Ei

均值,Ek=

ik

,i=1,2,…,k。

定理1　当网络中节点发送功率不能调整时,选择剩余能量最多的邻居节点作为下一跳,即可达到局部能量均衡性能最好。

证明略。

3　分布式能量均衡路由PDEBR

在节点发送功率可以调整的情况下,以该节点作为下一跳后导致的局部能量均衡性能作为选择下一跳的标准,这就是本文提出的基于预测的分布式能量均衡路由算法PDEBR的依据。局部能量均衡性能用式(1)度量。

3.1　网络模型及能耗模型

φ　local-2=

4

其中,Ek2为节点1选择节点2作为下一跳后一跳邻居节点的

Ee1+Ee2+Ec3+Ec4能量均值,Ek2=。节点1把分组发送给

4节点3后的局部能量均衡性能为

(Ee1-Ek3)2+(Ec2-Ek3)2+(Ee3-Ek3)2+(Ec4-Ek3)2

φ　local-3=

4

首先给出WSN的网络模型:

・123・

其中,Ek3为节点1选择节点3作为下一跳后一跳邻居节点的能量均值,Ek3=

Ee1+Ec2+Ee3+Ec44

。节点1比较φlocal-2和

φlocal-3,如果φlocal-2<φlocal-3,那么选择节点2作为下一跳,否

则选择节点3作为下一跳。

3)下一跳节点接收到分组后,回到第1)步。重复以上步骤,直到分组到达Sink。

4)在选择下一跳节点的过程中,应当遵循前进距离为正的原则,以有效避免环路。如果在自己的一跳范围内不能找到满足该要求的下一跳节点,则说明发生了“局部最大”问题。但是,由于PDEBR已知两跳邻居信息,可以进一步在两跳范围内找到使得局部能量均衡性能最好的前向节点,以努力摆脱“局部最大”的困境。

3.3　PDEBR的关键技术

φ3.3.1　local的估算

PDEBR中,节点要根据一跳邻居范围内不参与分组转发表及其地理位置信息。这样做带来的另外一个好处是,可以

利用两跳邻居的地理位置信息有效避免“局部最大”问题。3.3.2　估算φlocal的范围可以知道,估算φlocal的范围越大,越接近全网范围,就能够达到越好的全网能量均衡性能。估算φlocal范围的极限情况就是以全网所有节点的剩余能量进行估算,这显然可以达到最好的全局能量均衡性能,但这是需要付出开销的,包括计算开销和控制开销。尤其是对于节点分布密集、网络规模大的WSN网络,其开销更不容忽视。

对于PDEBR来说,在一跳范围内预测φlocal要用到两跳邻居信息。同理,由于选择第二跳节点作为下一跳会对第三跳的能耗有影响,在两跳范围内预测φlocal就要用到第三跳节点的能耗信息,这会带来额外的控制开销。因此,考虑到协议的可扩展性问题,仍然把估算φlocal的范围限定在一跳范围内。

4　仿真与性能分析仿真条件如下。

1)网络范围:X×Y的矩形拓扑。

2)节点数:若干个WSN节点,1个Sink节点。

3)节点位置分布:每个WSN节点在网络范围内服从均匀、独立分布,Sink节点固定在[X,Y]位置。

4)节点最大有效通信距离:R=100m。

5)节点初始能量配置:WSN节点0.1J,Sink节点100J。6)业务模型:每个WSN节点每一轮向Sink节点发送1个长度为20bytes的分组。

7)节点能耗参数:如表1[12]所列。取k=4时的能耗参数。

8)仿真性能指标:分组递交率;平均端到端能耗;能量均衡性能;网络寿命(以网络中第一个节点失效的轮数计算)。

表1　收发信机能耗参数

信道衰减指数收发信机能耗参数

k=2

α11=135nJ/bit

k=4

α11=135nJ/bit

的节点的剩余能量Ec和参与分组转发的节点估计的剩余能量Ee,估算局部能量均衡性能φ因此,Ec和Ee的获取是local。估算φlocal的关键。

根据式(2),当前节点i把分组发送给节点j后,其估计的剩余能量为

k

(4)Eei=Eci-l(α12+α2di,j)

Eei只需要已知邻居节点的地理位置信息即可得到。邻

居节点的位置信息通过Hello消息即可获知。

Ω)转发该分组后估计的剩余能量为第j个邻居节点(j∈

(5)Eej=Ecj-Er-ej

其中,Ecj为第j个邻居节点的当前剩余能量;Er为节点接收该分组需要消耗的能量,可由式(3)得到;ej为第j个邻居节点转发该分组可能要消耗的能量。

下面分别介绍如何得到Ecj以及如何估算ej。

1)Ecj的估算:采用数据分组捎带和Hello携带能量信息相结合的方式跟踪节点的能量Ecj。在发送数据分组时,携带节点的能量信息,其它接收或侦听到数据分组的节点更新有关该节点的能量信息。另外,由于环境因素的影响以及无线链路的不可靠性,链路通常会发生时通时断的情况,导致节点间的连接关系发生变化,因此通常以Hello消息周期性地通告节点的存在性。由此,可以在Hello消息中增加节点的剩余能量域。通过这两种机制的结合,降低能量跟踪的能量消耗。

2)ej的估算:假设从节点i看来,节点j选择每个前向邻居节点的概率都相同,为p0,且p0=

1nj

α12=45nJ/bitα12=45nJ/bit

2α2=10pJ/bit・mαm4)2=0.001pJ/(bit・

图2是网络范围为300m×300m,节点最大有效通信范围为100m时,网络中节点个数对GPSR和PDEBR性能影响

的比较曲线图。

,其中,nj为邻居节点

j的前向邻居节点个数。节点j把分组发送给第k个前向邻

居节点消耗的能量为ejk,那么邻居节点j发送分组可能要消

nj

耗的能量为ej=

k=1∑ejk

nj

。

图2　节点个数对GPSR和PDEBR的性能影响

可以看出,节点i估算邻居节点j发送分组的能耗ej要已知两跳邻居节点信息———邻居节点j的前向邻居节点个数

nj以及邻居节点j把分组发送给第k个前向邻居节点所消耗的能量ejk。

因此,在PDEBR中,为了让节点i获得自己的两跳邻居节点信息nj和ejk,Hello消息还需要携带节点的邻居节点列

图2(a)是PDEBR与GPSR的分组递交率比较曲线图。从图中可以看出,随着网络中节点个数的增多,分组递交率增大。这是因为,节点个数越多,节点密度越大,节点的邻居节点个数越多,找到下一跳的可能性越大,分组端到端成功递交率也就越大。

・124・

图2(b)是PDEBR与GPSR的端到端平均能耗比较曲线图。从图中可以看出,在开始时,随着网络中节点个数的增多,PDEBR和GPSR的端到端平均跳数和能耗增大。这是因为,节点密度很低时,距离Sink远的节点的分组大部分被丢弃,这可以从图2(a)看到。只有距离Sink比较近、跳数比较少的分组才能成功递交,从而使得端到端跳数和能耗比较小。而节点密度增大后,距离Sink远的节点的分组也能够成功递交,故使得端到端平均能耗增大。

当分组递交率非常接近1时,随着节点个数的继续增多,

GPSR的端到端平均能耗减小,PDEBR的端到端平均能耗依

一种简单的结合方式。但是,PDEBR达到网络寿命最大化还

是有一定距离的。因此,我们需要进一步研究如下问题。

1)在考虑能量均衡的基础上进一步考虑最小能量路径,并在此基础上,进一步研究无线传感器网络的寿命问题。

2)研究能量均衡、端到端最小能量与网络寿命的关系。能量均衡希望所有节点轮流消耗能量,最小能量路径每次转发分组都用同样的路径,网络寿命与这二者之间具有一定的关系。在研究这个问题的基础上,理论分析网络寿命的寿命限,并研究能够延长网络寿命的度量指标。

参考文献

[1]

AkyildizIF,SuW,SankarasubramaniamY,etal.Wirelesssen2sornetworks:asurvey[J].ComputerNetworks,2002,38(4):3932422[2]ChongChee2Yee,KumarSP.Sensornetworks:evolution,op2portunitiesandchallenges[J].Proc.oftheIEEE.2003,91(8):124721256[3][4]

KarlyH,WilligA.Protocolsandarchitecturesforwirelesssen2sornetworks[M].EditorialJohnWiley&Sons,Ltd,2006LeeDong2Wook,KimJai2Hoon,KoYoung2Bae.Anenergyba2lanceddatadisseminationschemeforlifetimeextensioninwire2lesssensornetworks[C]∥Proc.oftheWirelessNetworksandEmergingTechnologies(WNET2005).Banff,Alberta,Canada:ACTApress,Jul.2005[5]

MhatreV,RosenbergC.Designguidelinesforwirelesssensornetworkscommunicationsclusteringandaggregation[J].Jour2nalofAdHocNetworks,2004,2(1):45263[6]

HaenggiM.Energy2balancingstrategiesforwirelesssensornet2works[C]∥Proc.ofIEEEInternationalSymposiumonCircuitsandSystems(ISCAS’03).Bangkok,Thailand:IEEECSPress,May2003:25228[7]

OlariuS,StojmenovicI.Designguidelinesformaximizinglife2timeandavoidingenergyholesinsensornetworkswithuniformdistributionanduniformreporting[C]∥Proc.IEEEINFO2COM.Barcelona,Spain,April2006:1212[8]

GaoJL.Analysisofenergyconsumptionforadhocwirelesssensornetworksusingabit2meter2per2joulemetric[R].IPNProgressReport.August2002:422150

[9]LianJ,NaikK,AgnewGB.Datacapacityimprovementofwirelesssensor

networksusingnon2uniformsensordistribution[J].InternationalJournalofDistributedSensorNetworks,2006,2(2):1212145

[10]SalhiehA,WeinmannJ,KochhalM,etal.Powerefficienttopolo2

giesforwirelesssensornetworks[C]∥Proc.ofInternationalConferenceonParallelProcessing.Valencia,Spain:IEEECom2puterSociety,Sep.2001:1562163

[11]GandhamS,DawandeM,PrakashR,etal.Energyefficient

schemesforwirelesssensornetworkswithmultiplemobilebasestations[C]∥IEEEGlobalTelecommunicationsConference(GLOBECOM’2003).SanFransico,California:IEEECommuni2cationsSociety,Dec.2003:3772381

[12]BhardwajM,GarnettT,ChandrakasanAP.Upperboundson

thelifetimeofsensornetworks[C]∥Proc.ofIEEEInternatio2nalConferenceonCommunications(ICC’01).Helsinki,Fin2land,2001:7852790

[13]侯惠峰,刘湘雯,于宏毅,等.一种基于地理位置信息的无线传感

然继续增大。这是因为,GPSR能够选择到距离自己更远、距离Sink更近的邻居节点作为下一跳,使得端到端平均能耗减小。而对于PDEBR,其以局部能量均衡性能选择下一跳节点,由于WSN业务的方向性以及目的节点的唯一性,距离Sink比较远、距离本节点比较近的邻居节点剩余能量相对比较多,这会使得局部能量均衡性能比较好。节点个数越多,邻居节点分布越密集,因而会选到距离Sink更远、距离本节点更近的节点作为下一跳,从而增大了端到端的平均能耗。

图2(c)是PDEBR与GPSR的网络能量均衡性能φ的比较曲线图。从图中可以看出,在节点密度比较低时,网络的能量均衡性能比较好。随着网络中节点个数的增多,能量均衡性能变差。当节点个数增多到使得网络分组递交率为98%以上时,随着节点个数的增多,PDEBR的网络能量均衡性能又不断变好,而GPSR的网络能量均衡性能基本保持不变。这是因为,网络的能量均衡性能最主要是由距离Sink一跳的节点的能量以及距离Sink最远的节点的差异决定的,当节点个数比较少时,距离Sink最远的节点的分组被中途丢弃的可能性比较大,使得距离Sink一跳的节点的能量消耗减小,网络能量均衡性能比较好。随着网络中节点个数的增多,距离

Sink比较远的分组也成功递交,增大了距离Sink一跳的节点

的能耗,使得网络的能量均衡性能变差。当网络中节点个数增多到可以使得分组递交率保持在98%以上时,PDEBR的能量均衡性能变好。这是因为,节点个数越多,节点越能够找到使得局部能量均衡性能更好的下一跳节点,使得全网的能量均衡性能得到提高。而GPSR的能量均衡性能基本保持不变,这是因为,GPSR总选择距离Sink最近的节点作为下一跳,与能量均衡性能无关。

另外,从图2(c)还可以看出,PDEBR要优于GPSR的能量均衡性能。这是因为PDEBR是以能量均衡性能为准则选择下一跳,而GPSR并没有考虑能量均衡性能,而是根据距离选择下一跳。

图2(d)是PDEBR与GPSR的网络寿命的比较曲线图。从图中可以看出,随着节点个数的增多,网络寿命缩短。这是因为,节点个数越多,节点接收的邻居发现消息越多,能耗越大,网络寿命越短。另外,PDEBR的寿命比GPSR的寿命长很多,这说明追求能量均衡可以有效延长网络寿命。

结束语　从本文研究结果可以看到,能量均衡是延长网络寿命的有效手段。但是,纯粹考虑能量均衡,而不考虑最小能量路径,有可能导致分组端到端消耗更多的能量,进而影响网络寿命。PDEBR在前向邻居节点集合中寻找使局部能量均衡性能最好的节点作为下一跳,以比较粗略的方式考虑了最小能量路径,这可以看作最小能量路由和能量均衡路由的

器网最小能耗路由算法[J].电子与信息学报,2007,29(1):1772

181

・125・