MANET多播路由协议MAODV扩展.pdf

《MANET多播路由协议MAODV扩展.pdf》由会员分享，可在线阅读，更多相关《MANET多播路由协议MAODV扩展.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/总第222期2008年第4期 计算机与数字工程Computer&D igital Engineering Vol.36No.447MANET多播路由协议MAODV扩展3燕立杰1)李腊元1)贾琴勇1)易国彪2)(武汉理工大学计算机科学与技术学院1)武汉 430063)(空军工程大学工程学院2)西安 710038)摘 要 在MAODV的基础上,提出一种新的多播路由可扩展性解决方案。仿真实验显示改进后的协议减少了开销,降低了时

2、延,在高动态的网络中尤为明显。关键词 A d hoc网络 MAODV 多播路由协议 NS-2中图分类号 TP393.01D istension ofM ulticast Routing ProtocolMAODV forM ENETYan L ijie1)L i L ayuan1)Jia Q inyong1)Yi Guobiao2)(D epartm ent of Computer Science and Technology,W uhan U niversity of Technology1),W uhan430063)(Engineering College,A ir Force Engi

3、neering U niversity2),Xian710038)A bs tractBased on MAODV,a new solution for scalable m ulticasting is presented.The si m ulation show s that the im2provem ent could reduce the routing overhead and delay in high m ovem ent network.Keyw o rdsAd hoc netw ork,MAODV,m ulticast routing protocol,NS-2Class

4、 N um be rTP393.011 引言MAN ET1-2又称为移动A d hoc网络,是随无线通信技术的快速发展而出现的一种新型网络。在A d Hoc网络中,各节点兼有主机和路由器的功能。移动节点之间通信是通过多路无线链路进行通信的,每个移动节点在必要时都要充当路由器的角色为其他节点转发数据包。多播(M ulticast)业务是支持多方通信的高效业务模式,其基本特点是发送节点的数据不是通过向逐个接收节点发送来传送到多方,而是发送节点只向网络发送数据的一份实例,经由网络节点复制并发送到多个接收节点。多播在传输多方通信的数据时,不仅减轻了源系统的处理负荷,也降低了网络带宽的使用。按需距离矢量

5、多播路由协议MAODV(M ulti2cast A d-Hoc O n-dem and D istance V ector Proto2col)是应用按需路由技术的一种基于树的多播路由协议,所谓的按需路由协议就是指该路由协议并不是一直保持到每一目的的路由,而是根据路由源的需要建立相应的路由。这种按需的路由技术有效地减轻了网络信道中协议控制包的负载,提高了信道利用率。按需多播路由协议非常适合应用于无线自主多跳网络。MAODV采用的是双向共享树(B i-direction Shared Tree)的多播分发机制。共享树是一棵以管理点为根,包括所有组成员的树。每棵共享树都有自己的管理点,由管理点负责

6、受理来自树外节点的加入申请。共享树中多播数据的分发分作两步进行:多播数据源节点先将数据用单播方式发送到管理点,再由管理点沿多播树的分枝分发多播数据。“双向”是指多播树中的节点同时设置指向树中上游节点(父母节点)和下游节点(子节点)的指针。本文提出一种新的方案,即从现有的多播路由协议MAODV出发,按照其已提出的且较成熟的3收稿日期:2008年1月4日,修回日期:2008年2月8日基金项目:国家自然科学基金项目(编号:60672137)资助;教育部高校博士点基金项目(编号:20060497015)资助。作者简介:燕立杰,男,硕士,研究方向:高性能网络技术、通信协议。李腊元,男,教授,研究方向:高

7、性能网络技术、通信协议。贾琴勇,男,硕士,研究方向:并行计算。易国彪,男,硕士,研究方向:网络通信协议。1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/思路,完善并修改现有的协议,充分挖掘它自身的可扩展性。对扩展后的协议实现并且仿真,试验表明改进后的协议减少了开销,降低了时延,在高动态的MAN ET网络中尤为明显。2MAODV路由协议机制MAODV3用广播路由发现机制按需发现多播路由。如果源节点需要加入多播组,或需要向自己不是多播组成员的组发送数据而尚未发现可达路由时,

8、源节点通过发送路由请求报文RREQ发起路由发现过程。不能满足源节点路由请求的中间节点重新广播收到的RREQ,更改IP头为自己的IP地址。同时,它们也在单播路由表中添加到源节点的路由项,并把下一跳设置成将RREQ发送给它的节点,以建立反向路由。随着RREQ在网络中传播,如果接收到RREQ的节点是多播组成员,或者是能满足源节点路由请求的中间节点,则该节点通过发送路由回复(RREP)报文回复源节点的路由请求。RREP以单播的方式沿RREQ传播时建立的反向路径发送到源节点。RREP传播的同时,沿途节点在单播路由表中添加到多播组地址的路由项(此时该路由项处于不活动状态),并将下一跳设置成把RREP发送给

9、自己的邻节点,直到源节点,这样就建立了源节点到多播树某成员的正向路径。源节点广播发送请求到某多播路径时,可能收到多个路由回复RREP,这样就建立了多个转发路径。源节点在发送完RREQ后将等待一段时间,并记录下这段时间内收到的有最大序列号,最小跳数的RREP。该RREP意味着一条最新的最短的到多播组的路径。等待时间到达后,源节点单播发送多播激活(MACT)报文到收到把最大序列号最小跳数的RREP发送给自己的邻居节点。邻居节点收到MACT后激活单播路由表中到该组地址的路由项,并把MACT转发给路由表项指出的下一跳节点。MACT的传播激活了唯一的一条从源节点到多播树某成员的路径上所有中间节点的路由表

10、项,保证了源节点到多播树只有一条路径。多播组的第一个成员为该组的领导者。一个结点若多次加入某多播组没有成功,它将成为组领导者。组领导者负责维护多播组序列号,并将其广播到多播组,这是通过GRPH消息完成的。MAODV协议要主动追踪和响应树中的变化。若有成员结束了同该组的成员关系,多播树就要进行剪枝。在一定时间内未收到邻居的任何分组。则说明链路不可用,发生了断链,由链路的下游节点负责修复。若链路的下游节点修复失败,则认为多播树出现了分割,下游节点所在的子树失去组长,必须重新选择一个组长。当一个节点会收到两个不同组长节点发出GRPH消息,说明两个子树重新恢复了连接,由所在的组的组长IP地址小的节点发

11、起多播树的重构。3MAODV路由协议的改进(MAODVD)本文根据已有的MAODV本身的特点出发,在它的基础上进行了一定的改进,加入了一些新的功能,使之在网络规模、组成员数量、结点移动性等急剧增大的情况下,能保持较稳定的高效性,从而具有了好的可扩展性。MAODVD的修改和完善主要体现在以下3个方面:1)标准的MAODV协议中,假如A节点要加入多目标组G时,则将发送Join RREQ消息。如果源节A有多播组G组长节点的一条有效路由,则向此节点单播Join RREQ消息;否则,向整个网络广播这个Join RREQ消息。原协议中如果源节点单播的向G的组长节点发送Join RREQ消息,且没有收到它的

12、响应RREP消息,那么随后的全部RREQ消息只是简单的广播到整个网络。在随机移动的自组织网络中这和情况时常发生,在具有成千上万个节点的大规模网络中,如果简单的广播随后的RREQ的话,则将消耗大量的网络资源,大量的广播操作使得网络性能急剧下降,限制了路由协议的可扩展性。在MAODVD中源节点使用本地查找技术,当节点单播向组长节点的RREQ没有相应的RREP消息返回时,则说明源节点A中的这条有效路由断链,但失去联系的节点很可能还在附近,简单采用了扩展环搜索(Expanding Ring Search)技术也不能真实的反映节点的情况,本文使用本地查询技术5,将中RREQ消息中TTL初始值为HO P_

13、COUN T+LOCAL_ADD_TTL。其 中HO P_COUN T的值为A节点中保存的这条失效路径条目中到组长节点的跳数的值。这样,链路中断的影响可以局部化,提高的网络响应速度,降低了网络资源的消耗。2)标准的MAODV协议是基于单播AODV的基础上发展而来的,并立的多播组,并且每个节点维护相应的单播路由和多播路由。但实际上MAODV采用的是AODV的单播实现,即源节点84燕立杰等:MANET多播路由协议MAODV扩展 总第222期 1994-2009 China Academic Journal Electronic Publishing House.All rights reserve

14、d.http:/发送数据包到多播组,多播组的成员则根据保存的多播路由条目通过多播树向其它的多播组成员发送数据包,数据包是单播的发送到多播组成员的。对于每个多播成员的发送节点都要维护多条单播连接,给网络带来高流量负载,造成网络带宽的浪费。改进协议中,利用无线广播媒介固有的广播特性,采用多播树广播的的方式,对多播组数据包统一处理实现多播,这样就降低了网络拥塞负载和数据延迟,提高了数据包的交付率。3)大规模网络中,广播操作将消耗大量的网络资源,大量的广播操作使得网络性能急剧下降,限制了路由协议的可扩展性。MAODV协议中的部分控制报文(GRPH,RREQ)是在网络中广播传输的,随着多播组数量的增加和

15、数据源节点的增加,这部分广播流量也会随之增加,会增加网络延迟,导致协议效率下降,更严重的情况是引起“广播风暴”。本文运用Hyojun L im提出的一种“自我抑制泛洪”(Self-Pruning flooding)4的泛洪方式来抑制MAODV的GRPH和RREQ广播流量。自我抑制泛洪的算法描述如下:节点A在转发的广播分组中包含自己邻居节点的列表N(A)。接收到节点A的广播分组的节点B检查Q(n)=N(B)-N(A)-A(A为仅包含节点A的集合)是否为空集。如果Q(n)为空,则说明节点B的邻居节点都收到A转发的广播分组,B不需要转发该广播分组;否则,B转发该广播分组。4 路由协议的仿真分析4.1

16、 协议的性能评测指标实验中选取了如下三个指标进行性能评估:1)分组投递率:数据包交付率定义为实际收到的数据包数量相对于理想情况下应收到的总数据包数量。实际收到的数据包数量在模拟中是能直接测出的,理想情况下应收到的包数量是多播接收者的数量乘以发送数据包的数量。反映了网络传输的可靠性和网络所能支持的最大吞吐量。2)端到端的传输延迟:指数据包从源节点发出到最终被接收的时间。包括路由查找时延,数据包在接口队列中的等待时延,传输时延及MAC层的时延,这里只测量被多播接收者收到的包的延迟。反映了路由的有效性。4.2 仿真平台及参数设定本文采用NS-2仿真平台对种协议进行了测试,仿真环境为:操作系统为red

17、hat9,模拟软件为ns2.6;MAC层协议为IEEE802.11分布式协调功能(DCF);无线传输模型是自由空间传播模型。仿真参数设置为:节点传输距离为250m;它们可以在1000m1000m的正方形区域内任意移动;节点移动速度在0m/s20m/s范围内变化;数据源使用恒定比特速率(CBR);每次模拟时间为900s。4.3 仿真结果及性能分析如图1,分组投递率与节点移动速度的关系曲线图,随着节点移动速度的不断提高,路由协议分组投递率不断降低。这是因为节点移动速度越大,网络拓扑变化越频繁,链路就越容易失效,将会引起多播组的数据包的丢失,造成数据包分组投递率的降低。分组投递率与多播组成员数量的关

18、系曲线如图2所示,在一定的移动速度下,随着多播组规模的增大,网络负载的增加,协议的分组投递率不断降低。然而MAODVD的分组投递率都比MAODV好得多,特别是在稳定性方面,这是因为MAOD2VD协议采取本地查讯策略,提高了链路响应,而且MAODVD允许网络中的所有节点都能发送多播数据包,减少了数据包的丢失率,从而进一步提高了数据包的分组投递率。随着节点移动速度的不断提高,路由协议的平94第36卷(2008)第4期 计算机与数字工程 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.h

19、ttp:/均延迟也不断增加,如图3。这是因为节点移动速度越大,网络拓扑变化越频繁,路由更新的次数就越多,从而使分组的转发时间变长。平均延迟与多播组成员数量的关系曲线如图4所示,在一定的移动速度下,随着多播组规模的增大,网络负载的增加,协议的平均延迟亦具有增加的趋势。而MAODVD在延迟方面的表现更优于它在分组投递率方面的表现。尤其在速率较高和网络负载增大的情况下此性能的改善更加有效,这是因为控制报文采用自我抑制洪泛机制,减少了网络中的广播消息数量,降低网络负载,从而降低了延迟。5 结束语在无线或移动网络中,因为节点的带宽和能源非常有限,所以多播传送尤其重要。多播路由技术是A d hoc网络的核

20、心问题。本文通过对现有多播协议实现的修改和完善,充分挖掘它们本身的可扩展性。从模拟结果来看,这是一种可行的方案。路由控制开销和端到端平均时延特性都有所改善,在高动态情况下改善效果更加明显。仅仅从某个具体协议本身出发,是远远不够的。而结合多种方法、充分整合各种思路优点的综合性协议是值得进一步去研究和探索的。参 考 文 献1李腊元,李春林.计算机网络技术第二版M.北京:国防工业出版社,2004:231452于宏毅.无线移动自组织网M.北京:人民邮电出版社,2005:2882903Royer E M,Perkins CE.M ulticastAd Hoc O n-de2m and D istance

21、 V ector(MAODV)Routing C.IETF,Inter2net D raft:draft-ietf-m anet-m aodv-00.txt,20004Hyojun L im,Chongkw on Kim.M ulticast Tree Con2struction and Flooding in W ireless Ad Hoc N et w orks C.ACM M SW I M2000.Boston,2000,3:61685Castaneda R,SasS.Q uery localization techniques foron-dem and routing Protoeols in A d Hoc networks C.inProc.ACM/IEEE M oB ICoM99,1999:1861946徐雷鸣,庞博,赵耀.NS与网络模拟M.北京:人民邮电出版社,2003:112105燕立杰等:MANET多播路由协议MAODV扩展 总第222期