基于能量区域代理机制的移动Sink路由算法

基于能量区域代理机制的移动Sink路由算法

张建军，万磊，翟琰，魏振春

(合肥工业大学 计算机与信息学院，安徽 合肥230009)

摘要:文章提出基于能量区域代理机制的移动Sink路由算法。该算法使用剩余能量扫描算法将系统划分为若干个能量相近的区域,再在每个能量区域内构建路由信息,根据已构建的路由信息选择代理节点作为能量区域内信息存储和与Sink通信的节点,根据代理节点的分布制定Sink最小移动路径策略。仿真实验表明,在网络中使用该算法可以使网络能量得到更均衡合理充分的利用,可以很好地延长网络寿命。

关键词:无线传感器网络;移动Sink;剩余能量扫描算法;代理节点;最小移动路径策略

收稿日期：2014-01-20；修回日期：2014-03-17

基金项目：国家自然科学基金面上资助项目(61370088);国家国际科技合作专项资助项目(2014DFB10060);安徽省自然科学基金资助项目(1208085QF113);安徽省国际科技合作计划资助项目(1303063009)和安徽省高等学校省级自然科学研究资助项目(KJ2011ZD01;KJ2012A224;KJ2012A233)

作者简介：张建军(1963-),男,安徽合肥人,博士，合肥工业大学教授,硕士生导师.

doi:10.3969/j.issn.1003-5060.2015.01.008

中图分类号:TP393文献标识码：A

MobileSinkroutingalgorithmbasedon

proxymechanismofenergyarea

ZHANGJian-jun,WANLei,ZHAIYan，WEIZhen-chun

(SchoolofComputerandInformation,HefeiUniversityofTechnology,Hefei230009,China)

Abstract:In this paper, the mobile Sink routing algorithm based on the proxy mechanism of energy area is put forward. The residual energy scanning algorithm is used to divide energy areas into several energy-relevant areas, then the routing information is built in each energy-relevant area, and the proxy node is chosen according to the built routing information so as to store the information from the energy area and transmit information to the Sink node. Mobile Sink can formulate the minimum traverse strategy according to the position of the proxy node. The results of simulation experiments show that the energy in the network can be made full and balanced use of in this algorithm, and the network lifetime be prolonged as well.

Keywords:wirelesssensornetwork;mobileSink;residualenergyscanningalgorithm;proxynode;minimumtraversestrategy

无线传感器网络 (WSNs) 是一种将信息采集、 信号传输、嵌入式结合于一体的新型信息获取技术,它是利用具有感知能力的传感节点通过无线通信方式建立的一种无线网络[1]。Sink是WSNs中一类特殊的节点,它能收集节点产生的原始数据并进行处理,然后将信息传输到上一级单位。而在传统的WSNs中,Sink是静态的[2],并且其他节点受到工作方式和环境的限制,可使用的能量有限,这使得距离Sink越近的节点能量消耗越快,导致整个网络过早死亡。

为解决上述问题,人们提出一系列节能路由机制(如动态分簇算法[3]与K均值分簇算法[4]等)试图均衡节点间能量消耗,延长网络生存时间。这些文献所提方案能在一定程度上提高无线传感器网络的性能,缓解了“能量空洞”问题,但无法从根本上进行解决。为此,近年来人们提出各种基于移动Sink的路由算法,使得全网能量消耗尽可能在更多的节点之间均衡。如MECA(mobile-sinkbasedenergy-efficientclusteringalgorithm)[5]算法,使Sink围绕传感区域的边缘以固定的路径移动,区域内部划分为若干个簇进行数据收集,但簇头的选取和更新会带来较大的维护开销,且不能考虑全局能耗问题。为了能够更好地实现全局能耗均衡,文献[6]提出缓存节点辅助模式,它是单跳传输与多跳传输相结合的数据转发模式。在缓存节点辅助下,信息或数据以多跳转发方式传输到缓存节点上,移动Sink以单跳方式访问缓存节点,使得Sink的移动对全网路由信息影响较小。如AVRP(Anchor-basedVoronoi-scopingroutingprotocol)[7]协议,随着Sink的移动动态地在Sink邻居节点中选择剩余能量最大的传感节点作为锚节点用作数据收集,可以灵活地维护局部的能耗均衡,但锚节点选取后需要在Voronoi内范洪构建路由信息,使得每一次锚节点的选取都进行路由信息广播,造成系统能耗和网络通信负载较大。eScan算法[8]根据能量消耗模式具有空间局限的特性进行能量区域的划分,将全网划分为若干个能量相近的区域,便于局部区域能耗问题的解决,进而达到全网能耗的均衡。

本文在研究eScan算法的基础上,将全网划分为若干个能量相近区域,并结合缓存节点辅助模式[6],在能量区域内选取代理节点用作该能量区域内所有数据的存储和上传,同时Sink根据代理节点的分布情况设定移动路径进行数据的收集,据此提出基于能量区域代理机制的移动Sink路由算法。仿真结果表明其在能耗均衡及网络寿命等指标上有很大的改进,提高了网络生命期。

1网络模型

网络模型如图1所示。

图1　网络模型

对该网络模型做如下假设：

(1) 基于文献[9]已设定的网络模型,将网络节点分为负责数据采集的节点(Source)、负责数据转发的路由节点(Route)和负责数据收集的节点(Sink)3种类型。

(2)WSNs由若干个Source节点和若干个Route节点以及1个移动Sink节点组成,且分布在N×N的区域内。

(3) 每个节点有唯一的ID标志,且每个节点有相同的通信半径r,通信半径内的节点可以相互通信,交换信息,节点间通信可以为单跳或多跳模式。

(4)Source和Route具有相同的初始能量,且能量有限为E0,不能移动;Sink的能量不受限制,且以固定的速度可控移动。

(5) 每个节点可以通过GPS[10]或其他算法获知各自的位置信息。

为便于对算法进行描述,做如下定义:

定义Source到Route的某一路径选择概率P(i)为:

(1)

其中,CountHop为Source到Route的某一路径跳数;E0为节点初始能量;En为Source到Route的某一路径节点剩余能量之和;(E0CountHop-En)为当前路径已消耗能量总值;λ1、λ2为权值,用来调节跳数和路径已消耗能量的重要度,且λ1+λ2=1。

定义代理节点间的加权权值E为:

(2)

2能量区域划分

根据能量消耗具有空间局限性的特性,即相邻区域能耗相似度较高,利用eScan算法[8]进行能量区域的划分,从而均衡局部能量的消耗,进而达到全网的能耗均衡。

2.1　 eScan算法

利用(VALUE,COVERAGE)数组来表示能量区域,其中，VALUE=(min,max)分别表示能量区域内节点的最小、最大的能量值,如A.VALUE=(35%,37%)；COVERAGE则表示VALUE所代表的能量区域的范围。

当节点接收到能量扫描命令后,开始对其通信范围内的节点进行能量扫描,假设存在相邻的节点A和B,对这2个节点按eScan算法进行如下融合:

(1) 比较节点A和节点B的相似度，即

(3)

其中,T为剩余能量的最大相对误差。

(2) 对节点A和节点B通信区域进行比较,比较规则如下:

Distance{A.Cov,B.Cov}

(4)

其中,R为2个节点间的融合距离。如果2个节点满足上述的2个规则,则可以将这两者看成一个新的能量区域C,则C满足：

C.min=min{A.min,B.min}

(5)

C.max=max{A.max,B.max}

(6)

C.Cov=Merge{A,B,R}

(7)

从起始的采集节点Source开始,依次和其通信范围内的节点进行上述比较、融合,通过循环迭代,可以将整个网络划分成若干个能量相近的区域,且在每个能量区域内存在若干个Source和Route节点,如图2所示。

图2　某一能量区域模型

2.2　构建能量区域内路由信息

通过eScan算法可将全网划分为若干个能量相近区域,在能量相近区域内包括若干个Source和Route节点,且Source节点周期性地发送路由数据包,在上述划分的能量区域内构建路由信息,其中Route可存储所有Source节点的信息,并依据Route中存储的Source节点信息,选择该能量区域内代理节点用于该能量区域内数据的收集和上传,当Sink移动至该能量区域内进行信息收集时,以该Route代理节点为信息收集节点。

采集节点Source周期性发送路由数据包,数据包如图3a所示。其中，ID代表某个Source节点的编号；CountHop代表编号为ID的Source节点到当前Route的跳数；En代表编号为ID的Source节点到当前Route的路径节点的剩余能量之和；SerivalNum代表某一能量区域标志且相同能量区域的编号相同；PathNum是以位图的方式存储从Source到当前Route的路径节点信息。

Route中存储路由信息的结构如图3b所示,其中，ET代表编号为ID的Source到Route的路径节点剩余能量之和；P(ID)代表编号为ID的Source到Route的路径选择概率,其余项和图3a中含义相同。

IDCountHopEnSerivalNumPathNum

( a)

(b)

图3路由信息结构

假设每一个Route都有足够的存储空间用于存储能量区域内的所有Source节点的信息。在Source节点发出更新路由数据包后,与通信范围内的所有节点Route通信,首先Route根据SerivalNum判断该Source是否属于当前能量区域,若不属于,则丢弃;否则,Route根据ID判断是否已有该Source的信息,若无,则存储当前Source节点的信息,并按(8)式中方法更新路由数据包信息后在其通信范围内继续转发。

(8)

若Route中已有Source的相关信息,则通过(1)式计算P(i)值,并比较P(ID)与P(i)。若P(ID)≥P(i)则原先路径更优,即被选择概率更大,此时仍按(8)式中方法更新路由数据包后继续转发;若P(ID)

(9)

由此使得所有Route获得每一个Source节点的最短路由路径信息,其能量区域内路由算法流程如图4所示。

图4　能量区域内路由算法

2.3　代理节点选取

(10)

其中,W为选取某一Route作为代理节点的期望;λ3+λ4=1,λ3、λ4为权衡跳数最小化和剩余能量最大化的系数。由(10)式可知剩余能量越大,跳数越小,则期望值越高。

根据(10)式计算能量区域内所有Route作为代理节点的期望值W,选取具有最大W值的Route作为该能量区域的代理节点,用于存储该能量区域内Source产生的信息以及与Sink进行数据通信的节点,并形成图5所示的能量区域信息传输路径。

图5　某一能量区域路由路径

3Sink最小移动路径策略

3.1　基于能量区域的网络模型

在经过eScan算法对系统进行能量区域划分以及能量区域内路由信息的构建和代理节点的选取后,形成图6所示的系统模型图,其中底部为能量区域的划分,顶部为代理节点形成的连通图。

图6　基于 eScan的网络模型图

3.2　 Sink的移动路径策略

假设Sink节点可以获知各个代理节点的位置信息,并根据代理节点位置信息制定可控移动路径,同时假设Sink节点移动过程中不接收数据,只在代理节点处停止时开始接收数据。为更加有效地进行数据收集,维持系统能耗均衡,本文所描述的Sink移动策略应考虑以下2个方面:

(1) 移动Sink在系统内部收集信息时的路径形成环路,即从起点出发收集完数据后最终又要回到起始点(也为终点)。则将问题转化为访问各能量区域代理节点的环路遍历问题,如图6顶部所示。

(2) 能量区域采集的信息都存储在Route代理节点,加快了区域的能量消耗,易造成低能量区域出现“能量空洞”,不利于信息采集和区域寿命延长,为了提高低能量区域的有效性,延长区域网络寿命,则采用低能量区域优先访问的原则。

在综合考虑上述2个方面的基础上,在最短路径环路遍历和低能量区域优先访问之间进行加权折中,确保移动Sink收集信息的有效性及系统能耗均衡性,延长网络生命周期。具体权值计算采用(2)式。根据(2)式可计算出任意2个Route代理节点之间的权值E,故本文的Sink最小移动路径策略转化为求已形成的带权无向连通图的最小环路遍历路径问题,如图6顶部所示。

对于最短环路遍历问题,为使遍历路径总权值最小,本文依据Dijkstra[11]算法,提出以下赋权连通图的最小环路遍历算法,该算法描述如下:

(1) 确定始点A(也为终点)。

(2) 应用Dijkstra算法求出从始点A到其余各顶点B,C,D，…的最短路径权值DistA-B,DistA-C,DistA-D，…以及相应的最短路径PathA-B,PathA-C,PathA-D，…。

(3) 在各最短路径权值DistA-B,DistA-C,DistA-D，…中查找最小路径权值DistA-i,并求出i到A的次短路径顶点序列Pathi-A。

(4) 检查2个路径序列PathA-i和Pathi-A中是否包含所有代理节点,若已经全部包含,则这2个路径顶点序列顺序即为Sink节点的环路遍历路径。否则,保持PathA-i不变,求出i到A的下一个次短路径顶点序列Pathi-A,若路径PathA-i和Pathi-A`包含全部代理节点,则这2个路径的顶点序列即为Sink的环路遍历路径,否则,按照上述方式继续查找次短路径顶点序列Pathi-A,直到找到包含全部代理节点的环路遍历路径或者i到A的路径已经达到最大。

(5) 若i到A的路径已经达到最大时还未求出包含全部代理节点的环路遍历路径序列,则从A到i的次短路径开始,继续重复步骤(2)~步骤(4)过程,求出从i到A的下一个次最短路径顶点序列并作检查,直到找到包含全部代理节点的环路遍历路径序列为止。

结合图6顶部数据以及步骤(1)~步骤(5)算法,计算出代理节点最短环路遍历路径A→E→D→B→C→A,如图7所示。

图7　移动 Sink最短遍历路径

Sink计算出代理节点最短环路遍历路径后依次按照顺序访问各个代理节点,当Sink回到起始点时,系统依照eScan算法重新进行能量区域划分,重新制定路由和遍历路径,进行第2次信息采集。

4仿真实验

采用TCL/TK语言在NS2[12]环境下进行仿真,对基于能量区域代理机制的移动Sink路由算法的网络寿命进行评估与分析,并以AVRP[7]算法和eScan[8]算法作为对象进行比较分析网络寿命。本文网络寿命定义为从网络开始运行到第1个节点死亡时的时间。

在仿真试验中,节点的布设如图1所示,传感节点被随机部署在一块100m×100m的矩形目标区域中,Source节点数量设为500个,Route节点为200个,其节点通信半径为1m,节点接收和转发1个数据均消耗1个单位能量,MAC协议采用IEEE802.11,Sink节点按照设定路线从起点收集数据后返回原点。为便于实验分析,把矩形区域划分为3个能量相近的区域,且每个区域初始能量随机分布在(500±50)、(400±50)、(300±50)个单位。

图8描述了节点能量对网络寿命的影响。通过对比分析发现,本文提出的路由算法相比于AVRP算法和eScan算法在每个区域的能耗上都能够很好地将各个节点均衡地利用,有效地减少范洪的次数,达到全局能耗的均衡,网络的平均寿命分别提高约40%和25%,故本文提出的路由算法有效地提高了网络寿命。

图8　节点能量对网络寿命的影响

图9描述了节点发包率对网络寿命的影响。通过对比分析发现,AVRP算法和eScan算法在Sink移动时只在通信范围内选取代理节点作为数据收集点,不仅没有考虑整体能耗,且路由链路也不断被拓展,随着节点发包率不断变大,通信负载也增大,网络能量会较快耗尽,而本文算法都是局部最优路由,且在局部最优的基础上,Sink的移动也最优化,故而随着发包率的变化,网络寿命平均延长约30%~35%。

图9　数据发包率对网络寿命的影响

5结束语

在研究eScan算法的基础上,结合缓存节点辅助模式的思想,提出了基于能量区域代理机制的移动Sink路由算法。仿真实验结果表明,通过剩余能量扫描,可以将能量相近的节点划分为一个能量区域,在每一个能量区域中进行局部路由的构建,有效地避免全局路由的范洪,节约了路由构建的开销;同时基于代理节点的选取,使代理节点的选取更加合理化,进而使得每个能量区域的消耗达到均衡；再结合Sink最小移动路径策略,使得总体的能耗更为均衡。本文算法从局部到整体都达到有效的均衡,延长网络的寿命。

[参考文献]

[1]朱红松,孙利民.无线传感器网络技术发展现状[J].中兴通信技术,2009,15(5):1-5.

[2]WuXB,ChenGH,DasSK.Avoidingenergyholesinwirelesssensornetworkswithnonuniformnodedistribution[J].IEEETransactionsonParallelandDistributedSystems,2008,19(5):710-720.

[3]MartaM,CardeiM.Improvedsensornetworklifetimewithmultiplemobilesinks[J].PervasiveandMobileComputing,2009,5(5):542-555.

[4]NakayamaH,AnsariN,JamalipourA,etal.Fault-resilientsensinginwirelesssensornetworks[J].ComputerCommunications,2007,30(11/12):2375-2384.

[5]WangJ,YinY,etal.Anmobile-sinkbasedenergy-efficientclusteringalgorithmforwirelesssensornetworks[C]//ProcofIEEE12thInternationalConferenceonComputerandInformationTechnology,2012:678-683.

[6]TianK,ZhangBX,HuangK,etal.Datagatheringprotocolsforwirelesssensornetworkswithmobilesinks[C]//ProcofIEEEGlobecom,2010.

[7]DemirE,AykanatC,CambazogluBB.Alink-basedstorageschemeforefficientaggregatequeryprocessingonclusteredroadnetworks[J].InformationSystems, 2010, 35(1):75-93.

[8]ZhaoYJ,GovindanR,EstrinD.Residualenergyscanformonitoringsensornetworks[C]//ProcofIEEEWirelessCommunicationsandNetworkingConference,Orlando,2002:356-362.

[9]罗兖,徐云,黄刘生,等.一种动态传感器网络中的新型路由算法[J].计算机工程,2008,34(16):141-143.

[10]KaplanED.UnderstandingGPS:principlesandapplications[M].Boston,MA:ArtechHouse,1996.

[11]王缔.最佳旅行问题的一种求解方法[J].科教文汇:上旬刊,2011(8):1-3.

[12]KyunghwiK,WonjunL.MBAL:amobilebeacon-assistedlocalizationschemeforwirelesssensornetworks[C]//Procof16thInternationalConferenceonComputerCommunicationsandNetworks,2007:57-62.

(责任编辑马国锋)