移动ad hoc网络AODV协议的分析与改进

来源 :计算机辅助工程 | 被引量 : 0次 | 上传用户:menangchen
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘 要:由于移动ad hoc网络的AODV(Ad hoc on-Demand Distant Vector)协议仅维护1条到目的节点的路由记录,即使路由未失效,在超时后也会被删除,因此提出改进的AODV协议——HI-AODV协议. 改进内容为:(1)借鉴DSR协议的特点,使其路由表维护多条路由记录;(2)在路由发现和路由维护中有效利用路由缓存信息和多路径路由,使得路由发现更加迅速. 仿真结果表明HI-AODV协议可以提高数据吞吐量,减小平均延时. 但由于移动ad hoc网络节点的移动性,采用HI-AODV协议容易导致路由信息失效,对路由协议产生负面影响.
  关键词:移动ad hoc网络;AODV协议;HI-AODV协议;路由缓存;多路径
  中图分类号:TP393 文献标志码:A
  
  Analysis and improvement on AODV protocol of mobile ad hoc network
  ZHANG Tianming,WANG Peikang
  (School of Info. Sci. & Tech.,Univ. of Sci. & Tech. of China,Hefei 230027,China)
  Abstract:Only one routing record which indicates the route to the destination node is maintained in Ad hoc on-Demand Distant Vector(AODV) protocol of mobile ad hoc network. Although the routing record is valid,it will be deleted if it is overtime. So the improved AODV protocol,HI-AODV is proposed. The improvement is:(1)Multi-records are maintained in the routing table referring to the advantages of DSR protocol;(2)the routing cache and the multi-path routine are effectively utilized in the process of routing discovery and maintenance. So the routing discovery is more effective. The simulation result shows that HI-AODV protocol can improve data throughput and reduce average time delay. However,due to the node mobility in mobile ad hoc network,HI-AODV protocol easily leads to invalidation of routing information and have negative impact on routing protocol.
  Key words:mobile ad hoc network;AODV protocol;HI-AODV protocol;routing cache;multi-path
  
  0 引 言
  
  移动ad hoc网络是由1群无线移动主机组成的自治网络,无须固定的基础设施和集中管理,网络中的每台主机既作为主机面对用户运行程序,又作为路由器转发数据.由于ad hoc网络节点可以任意移动,传统的路由协议(如RIP,OSPF)很难适应这种动态变化的拓扑结构.此外,考虑到ad hoc网络的低带宽、主机低运算存储能力以及能源受限等特点,要设计出适用于ad hoc网络的路由协议是1个重要课题.近年来,针对ad hoc网络研究人员提出相当多的路由协议,大致可分为先验式路由协议和反应式路由协议,其中AODV协议(Ad hoc on-Demand Distant Vector)[1]和动态源路由协议(Dynamic Source Routing,DSR)[2]是2种被广泛研究的反应式路由协议.本文对AODV协议进行详细分析,对其不足进行改进[3],使节点存储更多的路由信息并在路由发现和路由维护中有效利用路由缓存,降低路由开销和时延.
  
  1 AODV路由协议
  
  AODV路由协议是1种按需平面距离矢量路由协议,由DSR与DSDV(Destination-Sequenced Distance-Vector Routing)[4]结合,一方面借用DSR中的按需进行路由发现和路由维护机制,另一方面借用DSDV中的逐跳路由,引用目的序列号防过时路由策略.协议由路由发现和路由维护两部分组成.
  1.1 路由发现
  为了找到到达目的节点的路由,源节点广播路由请求报文(RREQ),收到请求报文的节点,查询自己的路由表中是否记录有到目的节点“更新”的路由,所谓“更新”是指目的序列号大于请求报文中的序列号.若没有,节点记录请求报文的源节点、目的节点、上游节点地址和目的序列号并广播;如有或本节点是目的节点,将对源节点的路由请求发送路由应答报文(RREP),报文中包含“更新”的目的序列号和路由,转发RREP的节点根据RREP所携带的信息更新路由表,设置路由的下游节点、目的序列号和有效时间信息,并沿着反向路由将RREP转发至源节点.
  1.2 路由维护
  AODV路由协议采用Hello消息机制进行链路连通管理,从而对有效路由进行维护.具有有效路由的节点每隔固定时间T广播1个特殊的RREP,即Hello消息.邻节点收到Hello消息,可对各自的相应路由建立更新.如连续几个T时间内未收到有效路由中相邻节点的Hello消息,便认为该链路断开,主机将从路由表中删除包含该链路的路由,并发送路由出错报文(RRER)至前序节点.在AODV路由协议中,路由表的每条记录都保存1个前序节点列表,这些前序节点用这条记录表示的路由发送数据,如路由上的某条链路断开,断开处的节点发送RRER到其所有前序节点,每个收到RRER的节点继续把RRER包发送给其前序节点,这样删除所有用到这条断开链路的路由.
  1.3 AODV协议存在的不足
  (1)路由表中仅仅维护1条到目的节点的路由记录,而在DSR协议中,源节点可以维护多条到目的节点的路径,如果两节点间存在多条路径路由,当最优路由失效后,源节点可以选择次优的路由而不需要重新发起路由发现过程,这在网络拓扑结构变化频繁的环境中尤其重要.
  (2)由于AODV协议采用超时删除路由的机制,即使路由未失效,在超时限后也将被删除.
  
  2 对AODV协议的改进
  
  针对AODV协议的不足,提出以下改进方法:
  (1)随着电脑技术的发展,主机配置越来越高,包括运算速度的提高、内存容量和电池容量的增大等,而增加路由表缓存容量可以存储更多的路由信息.为克服AODV路由表的不足,AODV可以借用DSR的特点,使路由表维护多路径的路由,多路径路由按照目的节点序列号由大到小的顺序排列,当最优的路由断开时,欲发送数据的节点可以选择次优的路由,而不需要发起路由发现过程,减小数据的传输延时.
  由于AODV协议采用超时删除路由机制,即使路由未失效,超过时限后也被删除.为了保留有用的路由信息,可以把路由表分成有效路由部分和超时路由部分,当某路由超时后,不作删除处理,而是将其挪到超时路由部分.这些路由信息能帮助路由发现和路由维护.
  


  图 1 多径路由
  
  (2)在AODV的RREQ和RREP中增加1条路径记录,记录报文所经过的节点,这样中间节点在转发RREQ和RREP时就可以获得到达路径中所有节点的路由.如图1,节点A欲向节点D发送数据而路由缓存里没有此路由,源节点A发起路由发现过程,获得路由A—B—C—D,由于在RREQ和RREP中增加1条路径记录,节点A和D也获得到达该路由中所有节点(如节点B和C)的路由,节点B等中间节点也获得到达节点A和D的路由.[5]
  (3)由于无线广播信道的特点,节点可以工作于“混合监听”状态,即可以听到相邻节点发出的所有报文,包括RREQ,RREP和数据报文.这些报文中携带网络的一些路由信息,节点从监听到的报文中获得很多新路由,而不需要通过发起路由发现过程,可以减少每次发送新报文时启动的路由发现过程,提高系统效率.节点从监听到的报文中提取的路由信息分3种情况:第1种是此路由在缓存中没有,则存入缓存;第2种是此路由在缓存中已有,则更新;第3种是此路由是去往同一目的节点的不同路径,存入缓存,所以在节点的路由缓存里往往存在多径路由.如图1中源节点A到目的节点D存在2条路径:A—B—C—D,A—F—G—E—D,网络中存在的多路径路由对路由发现和路由维护均有帮助.
  
  3 有效利用路由缓存信息
  
  3.1 路由发现中利用路由缓存信息
  AODV的每个路由表项都有1个超时值,表示此表项在多少时间内有效,而有些超时路由信息依然能够帮助迅速发现到达同一节点的路由.某个节点需要向目的节点发送数据时,先查询其路由表中(包含已经超时的路由表项)是否有到达目的节点路径,若存在且没有过期,则可以直接发送数据;若此路由已经过期,就利用此路由开始单播式的路由发现,而不需要全局广播RREQ.若中间节点有到达目的节点路由,就直接回复,若没有就逐跳转发到目的节点,目的节点沿反向路径回复RREP.图2中粗线箭头表示活动路径,细线箭头表示非活动路径.当A需要向H发送数据时,它发现路由表中有到达H的过期路由,那么A向B发送1个单播路由请求,B收到此请求后同样检查其路由表发现自己有1条到达H的活动路径,B回复A 1个RREP;若B发现自己有1条通过F的非活动路径,那么B就可以用RREQ单播到F,最后RREQ到达G时,由G发送1个RREP给A,若B发现自己没有任何可以到达目的节点的路由,可以给A发送1个RERR,或者B不作任何反应,A收到RRER或路由发现超时后,进行广播式的路由发现.
  


  图 2 利用缓存信息的路由发现
  
  节点移动造成路径上某些链路断开,如当E和F移动后,BE和BF失效,B无法帮助A找到到达H的路由,可以返回A 1个错误或者积极帮助A寻路.B发送1个带有很小TTL的广播路由请求,如TTL=2即意味着所有距B为2个HOP范围内的节点响应此请求,C收到此RREQ后发现自己的路由表项里有1条去往F的活动路径,则C给B 1个RREP以告知自己有去向F的路由;若C有1条非活动路径去往H,那么它将RREQ单播给F,直到G,当G返回RREP时,C将此RREP传给B;如C发现没有到达目标节点的路径时,不作任何反应.如果此范围内的节点能够找到去往H的路径,那么它们将发送给B 1个RREP,否则就按照AODV的方式进行路由发现,此方式是广播与单播方式的结合.
  3.2 路由维护中利用路由缓存信息
  改进后的AODV路由表允许记录多条源点和目标节点的路径,当某条路径失效后,可以选择另外路径继续传输数据,而不进行重新选路.图3中,假定B有2条去往H的活动路径,分别经过E和F,当B发现BE失效时,B自动将数据发往下一跳F,而不用通知A链路BE失效.当B去往H所有邻节点链路失效时,B将给其上游节点广播1个RRER,A收到后,删除失效的AB链路,然后将其数据发往下一跳C,而不重新选路.
  


  图 3 多路径的路由
  
  这种多路径方法能极大增强路由协议的健壮性,但它选择的路径未必最优.
  
  4 仿真实验及结果
  
  实验以AODV协议作为比较对象,使用被广泛应用的NS-2模拟器.网络拓扑结构设计为50个移动节点的网络模型,各节点随机分布在1 000 m×1 000 m的平面矩形区域,随机任意方向运动(Random Way-point),节点停留时间0 s,实验模拟时间600 s,运动最大速率分别为5 m/s,10 m/s,15 m/s,20 m/s,连接为TCP协议(由NS-2的cbrgen tcl产生),最大连接数为10,数据分组长度为64字节,数据速率为1包/s.
  图4给出在不同最大速率下改进的AODV(记作HI-AODV)和AODV的吞吐量性能,吞吐量定义为每秒目的节点成功接收到的数据包,图中可见HI-AODV的吞吐量性能要优于AODV,原因是HI-AODV协议的节点充分利用路由缓存帮助路由发现和路由维护,当局部链路失效后,HI-AODV协议只需要在网络的局部范围内寻路,从而减少全局范围的路由发现过程,降低路由开销,提高数据传输效率.但网络中节点不移动时,由于建立好的路由断开,HI-AODV的优越性得不到发挥,两者的吞吐量没有什么分别.
  


  图 4 数据吞吐量
  
  图5给出HI-AODV与AODV端到端的平均延时仿真结果.从实验结果可知,HI-AODV的平均延时比AODV的平均延时小,这是因为HI-AODV在路由发现和路由维护中利用路由缓存快速找到需要的路由,减小数据传输的延时.
  


  图 5 平均延时
  
  5 结束语
  
  随着对ad hoc网络研究的不断深入,发现其具有广阔的应用前景.针对AODV的不足,对其进行一些改进,增加路由缓存容量,在路由发现和路由维护中有效利用路由缓存信息和多径路由,帮助快速路由发现,减少路由发现过程,HI-AODV在吞吐量和延时方面相对AODV有明显改进.但HI-AODV增加路由缓存容量,由于节点的移动,路由表里存储的许多路由实际上已经失效,如果利用这些错误路由寻路或传送数据,就会失败,需要重新在全局范围发起寻路,相对AODV反而增加延时.这是改进方案对路由协议的负面影响.
  
  参考文献:
  [1] PERKINS C,BELDING-ROYER E,DAS S. Ad hoc on-demand Distance Vector(AODV) routing[S]. RFC3561,2003.
  [2] JOHNSON D B,MALTZ D A,HU Yih-chun. The dynamic source routing protocol for mobile ad hoc networks (DSR)[J/OL]. [2004-07-19].http://www.ietf.org/internet-drafts/ draft-ietf-manet-dsr-10.txt.
  [3] 王金龙,王呈贵,吴启晖,等. Ad hoc无线移动网络[M]. 北京:国防工业出版社,2004:3-12.
  [4] PERKINS C E,BHAGWAT P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers[J]. Comput Commun Rev,1994,24(4):234-244.
  [5] PATRICIA B,SIDDARTHA G,RAVI P. Self-learning ad hoc routing protocol[J] . IEEE J Selected Areas Commun,2003:2 824-2 828.
  (编辑 廖粤新)
其他文献
摘 要:针对传统企业管理信息系统(Management Information System,MIS)集成过程中出现信息孤岛、不同系统之间数据难以共享等问题,探讨当前企业MIS的集成方式,基于XML和Web服务提出1套开放式的企业MIS构建方案. 该方案采用XML文档作为数据存储及不同系统之间传输数据的主要载体,并将Web服务接口作为服务端接口以提高系统的开放性. 在该方案中还给出身份验证、安全数
期刊
2007年11月29日,由长春达尔康科技有限公司承办的英国Delcam公司新产品演示会在大连凯宾斯基饭店成功举行. 长春达尔康科技有限公司总经理沈维华先生致辞并介绍Delcam公司及其产品;技术经理韩永军先生介绍FeatureCAM和PartMaker软件产品并进行生动的案例分析;英国Delcam公司专程派技术专家BIRD Kevin为来宾作报告. 来自大连模具行业的80多位来宾亲身体验具有强大功
期刊
2008年1月14日,MSC.Software公司宣布收购Network Analysis,Inc.(NAI),此举将使MSC.Software公司大大增强其热分析软件市场的占有率.  NAI成立于1982年,研发、销售和支持热分析软件,产品为SINDA/G,拥有主要的客户包括Boeing,Lockheed Martin,Northrop Grumman,Hamilton Sundstrand,R
期刊
Altair公司与ACUSIM软件公司宣布:集群、网格和按需计算软件PBS Professional与AcuConsole软件集成,成为行业领先的计算流体力学(CFD)求解器解决方案.这个完善的解决方案包含1个集成在AcuConsole中的“PBS按钮”,此按钮可以为运行CFD的组织提供图形化前处理软件和集群计算操作之间的无缝链接.
期刊
NEC信息系统(中国)有限公司将于2008年3月17日—19日在上海市九江路700号南新雅华美达大酒店举行LS-DYNA及其在相关行业应用研讨会,并组织培训,届时将邀请LS-DYNA的创始人HALLQUIST博士、在LS-DYNA使用方面有着丰富经验的TABIEI教授和在汽车碰撞方面有着丰富工程经验的清华大学汽车工程系周青教授发表演讲. 可访问NEC信息系统(中国)有限公司的网站www.lsdyn
期刊
计算科学被称作科学探索的第3大支柱,与实验、理论相并列.软件产业是最能全面体现理论创新能力和科技成果水平的载体.我国要从加工制造业发展到制造业强国,不能缺少计算机辅助工程(Computer Aided Engineering,CAE)软件系统的自主开发和成熟发展.满足以装备制造业发展需求为导向的自主CAE软件产业,不仅是现代服务业和先进装备制造业产业结构调整的需要,也是关系到国家安全的战略考虑.
期刊
摘 要:为研究SiC/Al梯度功能材料(Functionally Gradient Material,FGM)的性能,采用ANSYS分别对具有4个梯度层的该种材料的3点弯曲试样和紧凑拉伸试样,在热载荷和机械载荷热载荷共同作用下的蠕变性能进行数值模拟分析,得到不带微裂纹、带垂直梯度方向微裂纹和平行梯度方向微裂纹的SiC/Al FGM试样在这两种工况下的蠕变应变随坐标位置及时间变化曲线. 结果发现:(
期刊
摘 要:由于二维裂纹扩展模式不能非常全面地反映岸边集装箱起重机结构件的疲劳裂纹扩展行为,以岸边集装箱起重机圆管构件为研究对象,利用Zencrack三维裂纹分析软件,详细分析未穿透裂纹与穿透裂纹的裂纹扩展关系,以及初始裂纹大小和载荷幅值对未穿透裂纹的疲劳裂纹扩展寿命的影响.对岸边集装箱起重机结构的抗疲劳设计及裂纹管理具有一定的参考价值.  关键词:岸边集装箱起重机;圆管构件;穿透裂纹;未穿透裂纹;疲
期刊
摘 要:针对钢结构施工过程中的数值模拟问题,基于AutoCAD环境,用ObjectARX作为开发工具,设计施工过程跟踪计算软件的整体架构. 运用面向对象编程方法编写施工过程跟踪模拟的有限元计算程序,包括构件形成、构件拆除、施工载荷变化和结构边界转换等模拟计算. 通过继承基类构造施工步类和构件类,并给出这些类的继承关系及实现方法. 实例证明该方法效果较好.   关键词:钢结构;施工过程;有限元;CA
期刊
摘 要:针对现有文献中普遍存在的永磁无刷直流电机(Permanent Magnet Brushless DC Motor,PMBLDCM)仿真模型工作状态单一的缺点,通过分析PMBLDCM在4状态工作过程中转子位置与开关触发逻辑之间的关系,定义开关因数S和调制因数T,建立PMBLDCM的4状态工作统一数学模型,并利用Matlab/Simulink构建仿真模型.结果表明,该仿真模型运行稳定可靠,为P
期刊