基于最小跳数的无线传感器网络能量自适应路由算法

收稿日期:2006-08-05;修返日期:2006-10-27 基金项目:山东省信息产业攻关项目(2003118) 作者简介:于磊磊(1982-),男,山东聊城人,硕士研究生,主要研究方向为无线传感器网络(yllsdu@mail.sdu.edu.cn);柴乔林(1956-),男,山东青岛人,教授,主要研究方向为计算机网络;王春雷(1982-),男,山东聊城人,硕士研究生,主要研究方向为无线传感器网络.

基于最小跳数的无线传感器网络能量自适应路由算法*

于磊磊,柴乔林,王春雷(山东大学计算机科学技术学院,济南250061)

摘 要:针对基于最小代价的路由算法冗余信息过多和能耗不均衡问题,提出了一种新的路由算法———MHEP算法。新算法通过在网络中建立最小跳数场和路径节点最小能量场,使得信息包可以沿着能耗最优的路径向网关节点发送。通过仿真实验与基于最小代价的路由算法的比较,结果表明该路由算法在能量节省和能耗均衡方面具有明显的优势。关键词:无线传感器网络;路由算法;最小代价;最小跳数;OMNET++仿真中图分类号:TP393 文献标志码:A 文章编号:1001-3695(2007)11-0236-03

EnergyadaptiveroutingalgorithmforWSNbasedonminimumhopsYULei-lei,CHAIQiao-lin,WANGChun-lei(SchoolofComputerScience&Technology,ShandongUniversity,Jinan250061,China)

Abstract:Considerthetoomuchredundantdataandthenon-balancedenergyconsumptionoftheroutingprotocolbasedontheminimumcost,proposedanewalgorithm———MHEProutingalgorithm.Theprotocolsetupminimumhopsfieldandmini-mumpath-nodeenergyfield.Thensenddatabythepathwiththebestenergyconsumption.Accordingtothecomparisonswiththeroutingprotocolbasedontheminimumcostbysimulation,thisalgorithmhadobviousadvantagesinsavingtotalenergyandbalancingenergyconsumption.Keywords:wirelesssensornetworks;routingprotocol;minimumcost;minimumhops;OMNET++simulation

无线传感器网络综合了传感器技术、嵌入式计算技术、分布式信息处理技术和通信技术,能够协作地实时监测、感知和采集网络分布区域内的各种环境或监测对象的信息,并对这些信息进行处理,传送给需要这些信息的用户[1,2]。无线传感器网络是一种能量有限的网络,且能量通常无法得到补充。因此,在无线传感器网络中,有效利用有限的能量资源是任何路由算法首要考虑的因素。无线传感器网络设计的一个主要目标是最大化网络生命期[3]。如果网络中某些节点能量消耗过快,这对网络的生存期有很大的影响。所以,每个节点能耗均衡也是路由算法的重要考虑因素。本文提出了一种基于最小跳数的能量自适应路由算法(minimumhopsenergy-adaptedprotocol,MHEP)。该路由算法的关键思想是利用到sink节点的最小跳数(minimumhopscount,MHC)和路径节点最小剩余能量(minimumpath-nodeenergy,MPE)作为路由选择度量来完成信息包的转发。仿真实验显示该算法具有良好的性能。1 当前研究现状无线传感器网络的路由算法是一个非常活跃的研究领域,基于最优路径的路由是其中比较重要的研究方向。目前国内外提出了多种基于最优路径的路由算法。这些路由算法中比较有代表性的是基于最小代价的路由算法[4]。该算法中每个节点只需要维持自己到接收器的最小代价,信息包就可以沿着最小代价路径向网关发送。这个路由算法的缺点是会在网络中引起很多的冗余信息,且没有考虑网络的能量消耗。针对该路由算法的不足和缺点,笔者提出了一种基于最小跳数并充分考虑能耗均衡的最优路径路由算法。

2 新算法设计算法假定网络中节点分布固定且相对均匀,信息包消耗的总能量可以用经过的跳数来衡量。在初始化阶段,首先由sink节点向网络中洪泛最小跳数场消息,每个接收到该消息的节点建立或更新自己的最小跳数场,并保存一个最小跳的next-hop可用节点集;之后由sink节点发起沿最小跳数场的方向洪泛路径节点最小剩余能量场消息,在网络中建立起路径节点最小剩余能量场。这样沿最小跳数场递减的方向,每个节点均建立了到sink节点的多条路径,信息包选择路径节点最小剩余能量最大的路径进行转发。基于最小跳数的路由可以保证任何节点的信息沿着最优路径向网关节点发送,使得整个信息传输过程消耗的总能量最小,路径节点最小剩余能量的引入可以使得网络中节点的能耗相对均衡,从而最大化网络的生存期。另外,针对传感器节点能量的变化,算法引入了一种基于通信量的MPE场更新策略。

第24卷第11期2007年11月 计算机应用研究ApplicationResearchofComputersVol.24No.11Nov.20072.1 初始化工作MHEP路由算法的初始工作阶段分成以下两步:a)Sink节点发起建立MHC场;传感节点获得到sink节点的最小跳数信息,并保存next-hop可用节点集。算法采用经典的洪泛算法(flooding)来建立MHC场和next-hop可用节点集。开始阶段,置sink节点的MHC为0,置其他所有节点的MHC为无穷大,然后sink节点向其所有邻居节点发送MHC消息,并置消息的当前MHC为0;这些邻居节点收到MHC消息后,将自己的MHC置为0+1=1,并生成一个当前MHC为1、sender为节点本身的新消息向其邻居节点广播。当节点Vn收到由节点Vm发送的消息后作如下处理:(a)若消息的当前MHC+1小于Vn的MHC,则首先清空

置Vn的next-hop可用节点集,然后置Vn的MHC为MHC消息的当前MHC+1,并把Vm加入Vn的next-hop可用节点集,然后转(b);若消息的当前MHC+1等于Vn的MHC,则直接把Vm加入Vn的next-hop可用节点集,然后转(b);若消息的当前

MHC+1大于Vn的MHC,则抛弃该消息。

(b)Vn向其邻居节点广播新消息,消息当前MHC为Vn的

新MHC值,sender为Vn。b)Sink节点沿已经创建的MHC的方向发起建立MPE场。MPE场的建立同样是通过洪泛的方式进行。开始阶段,为next-hop可用节点集中的每个节点加入MPE字段,初始值均设为0,然后由sink节点发起向其所有邻居节点发送MPE消息。该消息由消息标志、当前MHC、当前MPE和sender构成。置消息的当前MPE为sink节点MPE,当前MHC为0;sink节点的邻居节点接收到该MPE消息后修改当前MPE为当前节点能量,当前MHC为1,并向邻居节点广播修改后的MPE消息。当节点Vn收到由节点Vm发送的消息后作如下处理:(a)若Vm不在Vn的next-hop可用节点集中,或者消息的

当前MHC+1不等于Vn的MHC,则抛弃该MPE消息。(b)若Vm在Vn的next-hop可用节点集中且消息的当前

MHC+1等于Vn的MHC,则比较MPE消息的当前MPE和

next-hop可用节点集中Vm的MPE的大小。若前者小于或等于后者,抛弃该MPE消息;若前者大于后者,置next-hop可用节点集中Vm的MPE为MPE消息的当前MPE值,然后转(c)。(c)MPE消息的当前MPE值取为MPE消息的当前MPE和Vn能量的较小值,消息的当前MHC取为Vn的MHC值;然后Vn向其邻居节点广播修改后的MPE消息。通过以上初始化过程,每个节点均获得了到sink节点的最小跳数,并保存了一个“跳数=当前节点跳数-1”的next-hop可用节点集。这样每个节点均建立了到sink节点的多条最小跳路径并记忆了各条路径的最小节点能量,为信息包的路由传送做好了准备。2.2 路由策略传感节点发送信息时,首先搜索本节点的next-hop可用节点集,从中选择MPE最大的节点进行转发,下跳节点接收到该信息后作同样的处理,直至发送到sink节点为止。路由选择算法如下:foreachsensornodeido//对于任何一个传感器节点begindimtemp=infinity;//定义temp为无穷大dimnode;//定义节点变量if(packetgenerateorpacketin)then//如果有信息产生或者有信息到来for(k=0;k=avanodelist[k].MPE)then //选择next-hop可用节点集中路径MPE最大的节点 temp=avanodelist[k].MPE; node=k; }send(packet,node);//向选定节点发送信息包end在路由过程中,信息沿着距离网关节点跳数最少且能量最均衡的路径进行转发,不但能够节省网络整体能量,而且使得各个节点的能量消耗更加均衡。2.3 MPE场的维护和更新在网络的运行过程中,节点的能量会不断变化,因此MPE场的维护和更新是必需的。经典无线网络的周期性更新策略将带来大量的能量消耗,而无线传感器网络本身最大的特点就是能量的局限性。该算法采用一种基于通信量的MPE更新策略:sink节点维护一个通信量计数器,当通信量计数器达到设定的门限值时,sink节点重新发起MPE消息的洪泛。其原理如图1所示。图1 混合场的维护和更新这种MPE场更新策略具有很大的灵活性,可根据网络的整体流量动态调整MPE场的更新频率,能很好地适应网络的变化,并且能够最大程度地节省网络中的有限能量资源。为避免某些节点能量消耗过快而影响网络的生存期,在MPE场的更新过程中,如果某个节点的剩余能量小于某个β值(用户设定),则该节点将不再作为转发节点,同时该节点向所有的邻居节点发送esc消息;邻居节点接收到该esc消息后从自己的next-hop可用节点集中删除该低能量节点。这种策略可以有效地减少低能量节点的消耗,避免节点过早失效。

2.4 节点自动配置对于运行过程中新节点加入的情况,网络的重新配置显然代价太大,算法采用一种握手机制来实现节点的自动配置。当一个新节点加入无线传感器网络时,它首先置MHC为-1,并清空可用节点集,之后向通信范围内所有单跳邻居节点发送move消息,告之有新节点到来;所有收到该move消息的邻居节点把自己的MHC和MPE发送给该节点,如图2所示。新节点选择MHC最小的邻居节点加入自己的可用节点集,并记录它们的MPE。通过以上的握手过程,新节点就建立了到sink节点的多条路径。这种节点配置策略非常简单,不会增加算法的复杂性,而且能量耗费不大,是一种非常理想的策略,也是该路由算法的优点之一。