《MANET中基于能量约束的机会路由研究.doc》由会员分享，可在线阅读，更多相关《MANET中基于能量约束的机会路由研究.doc（14页珍藏版）》请在三一文库上搜索。
1、MANET中基于能量约束的机会路由研究doi:10.3969/j.issn.1001-3695.2010.02.066 Study of opportunistic routing with energy constraint in mobile Ad hoc network LI Qin-wei, CHEN Zhi-gang, ZENG Feng, QI Hua-mei, LI Deng (School of Information Science & Engineering, Central South University, Changsha 410083, China) Abstrac
2、t:This paper proposed an opportunistic routing based on energy-constrainting in mobile Ad hoc networks to maximize the life of energy-constrainting wirless networks. Firstly, introduced the node energy-consuming model(NECM), and constructed the waiting time function(WTF). Then proposed the strategy
3、for selecting forwarding candidates set based on metric named ECETX which consider both the unitary energy(PI) and the link state in order to build the delivery matrix, and then selected the nodes priorities which in forwarding candidates set. At last, designed an energy-constrainting opportunistic
4、routing(ECOR) based on all of the above strategies. The simulation results show that the life of the network using ECOR is longer than using ExOR, increase by 6070 percents in average, and the throughput increase by about 1523 percents. Key words:MANET; opportunistic routing; energy-constraint; NECM
5、; WTF; ECETX 无线自组织网(MANET,又称Ad hoc网络)是一种节点完全对等的无线网络。网络中的每个节点既有主机又有路由器的功能,具有很强的移动性和灵活性,这也给设计高效的路由协议带来了挑战。传统路由协议如AODV1、DSDV2等必须先建立一条有效的传输路径之后,才能传输数据,而在很短的时间内由于网络节点的移动或链路故障等问题往往会导致该条路由的失效,源节点只能重新建立路由,这就给网络带来了较大的传输延时并且导致数据报文的丢失。机会路由37与传统路由不同,它并不在传送数据报文之前建立一条完整的路由,而是通过邻居节点的每一次转发更加靠近目的节点。机会路由提高了在不稳定的无线链路传
6、输数据的可靠性,尤其是在丢包率很高的动态变化的网络中。然而,无线自组网中的每个节点都是通过能量有限的电池来支持其运行,一些节点提前死亡对整个网络数据的传输会带来很大的影响8,但目前的机会路由,如ExOR4、DART7等并没有考虑节点能量的限制,因此,本文在ExOR路由协议的基础上,考虑每个节点的能量状况,提出了一种基于能量约束的机会路由(energy constraint opportunistic routing, ECOR)。 在一般情况下,机会路由的主要工作过程如下所述: a)源节点通过某种策略在邻居节点中选择转发候选节点集(forwarding candidates set), 并给候
7、选集中的节点分配转发优先级(relay priority),之后再向邻居节点广播发送数据包。 b)分为以下三种:(a)邻居节点如果不在候选集中则忽略接收到的数据包;(b)如果在候选集中,首先检查自己在候选集中的优先级,如果发现自己在候选集中优先级最高,则向发送节点返回ACK,并转发数据包,否则必须等待优先级比它高的节点返回ACK后,再把自身的ACK和接收到的ACK绑定发回给源节点;(c)如果该节点经过一段时间等待后并没有收到优先级比它高的节点的ACK,那么它认为优先级比它高的节点并没有收到数据包,它有义务转发数据包并返回自身的ACK给源节点。可以看出,机会路由充分利用了节点之间的协作和无线网络
8、的广播机制,能够在很大程度上提高链路传输数据的可靠性和网络的吞吐量。 1 相关工作 2005年,Biswas等人3,4首先提出机会路由(extremely opportunistic routing, ExOR)基本策略之后,许多学者对其进行了深入的研究。文献5提出的MORE路由算法,通过随机线性网络编码与机会路由的结合,消去ACK响应,使得协议性能提升明显,但随之而来的是计算的开销明显增大,对节点的性能要求也比较高。在文献9中给出了基于机会路由策略的网络缓存模型Ditto。在文献10中,提出了基于机会路由与节点地理位置结合的路由算法GOR,使用地理位置与传输时间消耗结合作为转发候选集合的选择
9、指标,然而不可忽略的是该算法(GOR)需要明确知道节点的地理位置。同时可以看出,以上各种算法均基于一个假设,节点能量是无限的(以上算法均未考虑节点的能量情况),即使采用一种洪泛广播方式来搜寻整个网络的链路状态信息,并且每个邻居节点都时刻处于侦听并等待转发数据包的情况下,都不会给网络的节点寿命带来任何影响。事实上,无线自组网中的节点能量是极其有限的8,每个节点都来广播并时刻等待转发数据包势必会造成某些负载重的节点提前死亡,造成网络寿命的降低。影响整个网络的性能。因此,有必要建立一种能够均衡网络节点能耗的机会路由,保证网络中节点耗能的平衡性,从而提高网络的整体寿命。 目前,已有很多学者提出了基于节
10、能路由协议,总结起来有两种设计方法:最小化传输能量和最大化网络生存时间。以上设计都是基于传统路由协议。机会路由因为其特有的特性,如投递矩阵靠洪泛广播方式完成,由每个节点维护,并依靠其对候选集节点分配转发优先级,这些均导致了在机会路由中加入节能机制的困难性。本文通过给网络中每个节点根据自身能量状况建立等待时间函数(wait time function,WTF),保证能量低的节点延时较长时间返回ACK帧,以回避转发数据包;同时,提出了基于能量的节点转发候选集选择策略(ECETX),综合考虑每个节点的归一化能量值(PI)与链路状况来产生投递矩阵,确定候选集中节点的优先级,从而避免使用能量低的节点转发
11、数据包,最终实现提高网络寿命的目的。 本文介绍了节点的能量消耗模型,并构造了等待时间函数,同时,提出转发候选节点集选择策略(ECETX),并以此为基础在MANET中重新设计了一种基于能量约束的机会路由(ECOR)。通过仿真实验,验证了本文提出协议的有效性。 2 基于能量约束的机会路由设计 2.1 节点的能量消耗模型及等待时间函数 本文采用文献11中提出的能量消耗模型,设节点i的电池能量最大值是Eimax,Ei表示当前节点剩余能量,Eiconsume表示节点i已经消耗的总能量,因此,可以得到: Ei=Eimax-Eiconsume(1) 定义PI为PI=Ei/Eimax(2) 节点的能量消耗主要
12、可以分为三种状态,分别是发送、接收和转发。设节点发送一个数据分组所需能量为 Esend=PsTp=IsvTp(3) 接收一个数据分组所需要的能量为 Erecv=PrTp=IrvTp(4) 转发一个数据分组所需能量为 Efw=(Psend+Precv)Tp(5) 可以得到节点i已经消耗的总能量为 Eiconsume=Esend+Erecv+(N-1)Efw(6) 其中:Psend为发射功率;Precv为接收功率;Tp表示发送和接收一个分组所需时间,在传输速率为1 Mbps的情况下,Tp=Psize10-6,Psize为分组长度;Is为发送电流;Ir为接收电流。根据文献12,在Ad hoc网络环境
13、下,经过多次实验所测的对于不同传输速率的无线网卡在相同状态下的能量消耗值近似。因此,取v=4.74 V5.00 V,在发射状态下Is=280 mA,接收状态下Ir=204 mA。 为了能够使网络的寿命最大化,网络中的节点应该满足:能量充足的节点应该转发数据包,而能量低的节点则应该尽量回避转发数据包。机会路由中,源节点向邻居节点广播发送数据包,数据包中的头部字段标明了候选集中节点的优先级,如果优先级高的节点能量很小,这时候可以让它启动一个计时器等待一定的时间,这就会使优先级比它低的候选集节点收不到优先级高的节点的回应ACK帧,从而,优先级稍低的节点就会认为优先级高的节点并没有收到源节点广播的数据
14、包,它有义务将接收到的数据包转发出去,而此时优先级高的节点侦听到其他候选节点将数据包转发出去后,就停止计时器,并丢弃收到的源节点的数据包。从而,避免了能量低的优先级高的节点转发数据包耗费大量的能量,降低网络的寿命。 由以上分析可知,应该根据节点剩余能量值产生一定的延时时间,当能量充足时,延时时间极小,近似为0;而当能量比较低,尤其是低于某个限度时,此时的延时应该足够大,大于SIFS和ACK帧的回应时间。从而,可以建立一个延时函数,使之与PI成反比关系,当PI很大时,延时函数下降速度加快,并且值极小(近似为0),PI很小时,延时函数快速增大。由此,本文定义WTF为PI的函数,并基于以上性质,可以
15、用指数函数ex得到函数e-nx,如图1所示。该函数的值域为0,1,n为常数。由图可知,取n=23或25均可。本文中取n=23。在这种情况下,可以得到当PI0.2时,WTF(PI)值很小,近似于0。而当PIECETX(vs,vj),则有vi优先级大于vj。其中,ETX为发送节点通过每个邻居节点到目的节点的平均期望发包数,PI为节点剩余能量归一化值,为链路状态与PI之间的均衡因子,且01。本文中取=0.5。从该策略中可以看出,每个节点根据当前的链路状态和剩余能量状况选择转发候选集中节点的优先级,而不是像ExOR一样单纯地考虑候选集节点距离目的节点的远近来选定节点的优先级。本文中,设候选节点集的节点
16、数为83。 在这种情况下,转发候选集产生算法如下: /GetFsByECETX(s,Ns) Cs?鳓?,Cs?鳓?,Fs?鳓?,old-ECETX(s,Nx)=0,cnt=0; for each v Ns(vNs,PI(v)0) add v to Cs; calculate ECETX(s,Ns); old-ECETX(s,Ns)=ECETX(s,Ns); decending sort Csby old-ECETX(s,Ns); CsCs; while(Cs!=) Remove v from Cs, and add v to Fs, cnt+; if(cnt8PI(vNs)=0) break;
17、 get new-ECETX(s,Ns)according to Eq.8; decending sort Cs by new-ECETX(s,Ns); /end while return Cs,Fs; 对于转发候选集产生算法,其计算量比较小,设n为s节点邻居节点数,则该算法的时间复杂度仅为O(n2)。下面给出一个示例,如图2所示。 示例中,节点1向8发送数据,节点1首先计算与每个邻居节点的ECETX值,更新自己的投递矩阵,并得到F1=2,4,3,然后依此类推,得到F2=5,3,F5=8,6,可见,采用本文提出的ECETX转发候选集选择策略有效地避免了使用能量很低的节点3作为转发优先级高的节点
18、。 2.3 基于ECETX的机会路由设计 本文设计的机会路由中,ACK帧5增加一个字段,表示节点自身剩余的能量信息,这样,节点在收到候选集节点返回的ACK帧时,可以查看这个字段,并将信息读取出,以更新转发矩阵。这时的ACK帧如图3所示。 preamblePLCPheaderframecontrolrecieveraddresscand.ID FCSpadenergyPI 图3 ACK帧字段 则更改后的机会路由过程可以描述如下: /Initizlize: enum pkt_typeack, pkt;node PI=1,countack=0, countpkt=0, from now on, ev
19、ery node update PI with count changing/ 1Sending node calculate delivery matix with ECETX, and creates prioritized candidate set. 2Send packet with cand.ID, countnode_IDpkt+, update PI. 3Accept pkt, countnode_IDpkt+, update its PI. Check if(destination), Reply the sending node with ACK that the pkt
20、arrives the destination now, return; else open its timer, and delay WTF(PI); During timer not expired, listen and judge if(Timer0), go on waiting untill time expire, and if(pkt=itself or recv other Cand.ID relpy ACK), drop its pkt, set timer=0; if(timer=0) reply sending node ACK, countnode_IDack+, u
21、pdate PI. Forwarding node act as sending node, goto 1. End. 以上为基于能量约束的机会路由的具体执行过程,可以看出,此过程仅在原来算法(ExOR)基础上增加了少量的更新节点能量的开销,这对于整体网络来说,影响甚小,可以忽略。当然,在具体应用ECOR时,可以采取WTF和ECETX启用或关闭的方式使用。 3 仿真实验与性能分析 3.1 评价指标 1)网络节点存活数 当节点能量耗尽时,称该节点死亡。网络节点存活数指网络中未死亡节点的个数。表示为 liveNum=i0)(9) 其中:num(energy0)表示为当节点能量值大于0时,记为1,最
22、终累加得到网络节点存活数。 2)节点剩余能量均方差 在某一时刻,取所有节点的剩余能量的均方差值来衡量网络中节点能量消耗之间的均衡程度。表示为 t=1NNi=0(Eit-Et)2(10) 其中:Eit为t时刻节点i的剩余能量,Et-表示t时刻网络中所有剩余能量的平均值,N为网络中节点的数目。 3)网络吞吐量 指网络实际所达到的有效带宽大小。表示为 throughput=Ni=0Ni(recv)Pkt_size/T(11) 其中:Ni(recv)表示节点i所接收到的所有数据包,Pkt_size为数据包的大小,T为仿真的时间。 3.2 仿真场景与结果分析 本文的整个实验在NS2.3113上完成,物理
23、层为双向无线链路,每个节点的信道带宽为1 Mbps,MAC子层采用IEEE 802.11协议,模拟节点在20002000的区域内移动,移动模型采用random way point运动模型,采用的协议分别为ECOR、ExOR,网络的规模为100个节点。模拟时间为100 s,节点的最大移动速度Vmax取5 m/s,停止时间pausetime=10 s。数据包大小为512 bit,类型为cbr,修改后的ACK帧大小为32 bit。取电压v=5.00V,在发射状态下Is=280 mA,接收状态下Ir=204 mA。每个节点初始能量均为10 J。 在随机场景下按照以上实验配置,每隔2 s统计一次各种情况
24、下的节点存活数,得到结果如图4所示。 由图4可以看出,本文设计的机会路由ECOR(WTF-ON,ECETX-ON,后文中若不特别注明,均为此种情况)比传统的机会路由ExOR的平均网络寿命提高了60%70%,同时,可以看到ExOR中网络节点在30 s以后,死亡速率基本相同,在90 s时,网络节点全部死亡。而ECOR的网络节点中50 s80 s时,节点陆续死亡,但死亡数量很少,而在80 s90 s时,大量节点死亡,网络中存活节点剧烈减少。这是因为,本文设计的ECOR有效的回避了能量低的节点转发数据包,从而延长了网络寿命,网络节点的死亡完全是因为自身发送数据包而造成。同时,从ECOR(WTF-ON,
25、ECETX-OFF)和ECOR(WTF-OFF,ECETX-ON),可以发现它们均与ECOR变化规律基本吻合,只是ECOR比它们的网络寿命稍长,因此,后文中,只讨论ECOR在WTF和ECETX均启用时的网络状态。 同样采用以上随机场景,每10 s统计一次网络中节点剩余能量的均方差,得到结果如图5所示。 由图5可以看出,在仿真时间小于20 s时,网络中节点剩余能量均方差几乎相等,而在仿真时间大于30 s后,ExOR中节点剩余能量均方差均大于ECOR的节点剩余能量均方差。则说明了本文提出的ECOR路由能够很好的均衡网络中节点能量消耗,从而达到最大化网络寿命的目的。 最后,本文使用相同的随机场景,每
26、10 s计算一下网络的吞吐量,吞吐量为网络中这10 s内所传输数据的大小。所得结果如图6所示。 由图6可以看出,仿真时间T40 s时,ExOR吞吐量明显下降,而ECOR则相对稳定,网络吞吐量下降缓慢。整体来看,ECOR比ExOR的网络吞吐量提高了15%23%。 以上实验将本文设计的机会路由ECOR与传统的机会路由ExOR比较,均体现了ECOR的有效性。其网络寿命和网络吞吐量均比ExOR有所提高,同时,能够达到网络节点能量消耗均衡的目的。 4 结束语 本文中设计了基于能量约束的机会路由,通过引入节点的能量模型,构造了等待时间函数WTF并提出了基于能量约束的节点转发候选集选择策略ECETX,有效地做到了网络中各个节点能量消耗的均衡,延长了网络的寿命并提高了网络的吞吐量。然而,在网络中常常会出现某些节点负载很重而造成局部拥塞的现象,但此基于能量约束的机会路由尚没有考虑网络的负载情况,同时也可能因采用了一定的WTF机制导致数据包传输的延时增大,因此将在下一步工作中继续研究基于能量约束和负载均衡的机会路由协议,并寻找出一种能够均衡网络能量消耗和降低数据包传输延时的路由机制。