AODV路由协议分析研究

《AODV路由协议分析研究》由会员分享，可在线阅读，更多相关《AODV路由协议分析研究（44页珍藏版）》请在装配图网上搜索。

1、西南交通大学本科毕业设计论文AD HOC网络中AODV路由协议分析THE ANALYSIS OF AODV ROUTING PROTOCOLIN AD HOC NETWORK 年级2021级学号XX专业通信工程指导老师2021年 6月承诺本人郑重承诺：所呈交的设计论文是本人在导师的指导下独立进行设计研究所取得的成果，除文中特别加以标注引用的内容外，本文不包含任何其他个人或集体已经发表或撰写的设计研究成果。对本设计研究做出奉献的个人和集体，均已在文中以明确方式标明。如被发现设计论文中存在抄袭、造假等学术不端行为，本人愿承当一切后果。学生签名：年月日37 / 44院系计算机与通信工程系专业通信工程

2、年级2021级XX题目Ad hoc网络中AODV路由协议分析指导教师评语指导教师 (签章)评阅人评语评阅人(签章)成绩辩论委员会主任 (签章)年月日毕业设计论文任务书班级学生XX学号发题日期：2021年2月28日完成日期：2021年6月15日题目Ad hoc网络中AODV路由协议分析1、本论文的目的、意义自从 1997 年 IEEE802.11 协议正式发布以来，无线局域网得到了快速开展，但 IEEE802.11 协议不具有转发功能，组成的网络规模小，传输距离近，需要铺设较多的 AP 点。而无线自组网那么可以弥补这个缺点。而近几年，由于军用和民用需求的增加，大大促进了无线自组网的研究。无线自组

3、网现在广泛应用于自然灾害抢险、科学考察、以与在战场等通信场合。无线自组网研究的一个重要方面就是无线自组网的路由。移动Ad hoc网络中的拓扑结构始终是动态变化的，这导致路由成为Ad hoc网络设计中的根本问题，路由算法的研究也始终是移动Ad hoc网络研究中的一个至关重要的研究课题。本课题任务是在 IEEE802.11b 协议的根底上，在 Linux/Windows操作系统上实现 AODV(Ad hoc On-Demand Distance Vector)路由算法仿真。课题具有军民两用的特点，既能适合军队的无线电台组网，又能扩展IEEE802.11 协议的应用，具有广泛的应用前景。2、学生应完

4、成的任务1完成资料收集、阅读等工作2AODV 路由协议工作原理3制定仿真方案4分析仿真结果5撰写毕业设计论文3、论文各局部内容与时间分配：共 16 周第一局部完成选题、下达任务书( 1 周) 第二局部完成资料收集、阅读等工作( 1 周) 第三局部研究AODV 路由协议工作原理( 5周)第四局部制定仿真方案、分析仿真结果( 5周)第五局部撰写毕业设计论文( 3周)评阅与辩论( 1 周)备注指导 年月日审批人：年月日摘要自1997年IEEE802.11协议正式发布以来，无线局域网得到了快速开展，但IEEE802.11协议不具有转发功能，组成的网络规模小，传输距离近，需要铺设较多无线接入点，而Ad

5、Hoc网络那么可以弥补这些缺点。Ad Hoc网络的路由协议作为影响网络性能的一个重要因素，是确保Ad Hoc网络正确运行的关键。由于传统的路由协议己无法满足移动Ad Hoc网络的要求，因此更适合移动节点特性的路由协议不断的被讨论。AODV路由协议作为Ad Hoc网络中代表性的按需路由协议，它既能适合军队的无线电台组网，又能扩展无线局域网的应用，具有军民两用的特点，具有广泛的应用前景。本文首先简要介绍了移动 Ad hoc 网络的现状和开展前景，Ad hoc 网络的工作原理和特性，以与Ad hoc 网络的路由协议分析比拟。然后，重点分析研究了AODV路由协议的报文格式和工作原理。在理论分析AODV

6、路由协议的根底上，采用网络模拟器NS2实现 AODV 路由算法，通过对数据包投递率、端到端的平均延迟、归一化路由协议开销和平均跳数这四个方面进行了性能分析，得出AODV路由协议适用于规模较大的网络，并且在发包率较高的情况下性能表现良好，但是随着网络节点移动速度提升协议的通信质量将降低。关键词Ad hoc；AODV路由协议；性能分析；NS2仿真AbstractIEEE802.11 protocol has been officially released in 1997, the wireless LAN has developed rapidly.HoweverIEEE802.11protoc

7、ol do not have a forwarding function.As a consequence, only a network of small scale can be constructed, and the transmission distance is not long enough. And relatively more Access Pointare needed to deploy. But, Ad Hoc Networkscompensate for these shortcomings.However, as an important factor to af

8、fect the network performance, Ad Hoc network routing protocols are critical to ensure the correct operation of the Ad Hoc network. However, Traditional routing protocols are unable to meet the requirements of mobile Ad Hoc networks,sorouting protocols that are more suitable for the mobile node chara

9、cteristics are constantly discussed by people.AODV routing protocol is a typical on-demanded protocol in Ad Hoc Networks, it not only suitable for the armed forces radio network, but also extended the application of wireless LAN, it have dual-use features and broad application prospects.This paper b

10、riefly describes the status and development prospects of the mobile Ad hoc networks, the principles and features of the Ad hoc network, as well as the Ad hoc network routing protocol analysis and comparison. Then, we spend most of the works in the study and analysis of the packets format as well as

11、the working principle of AODV routing protocol. On the basis of the theoretical analysis of the AODV routing protocolbyNS2, a network simulator is usedfor AODV routing algorithm. Throughperformance analysis on packet delivery ratio, average end-to-end delay, normalized routing overhead and average h

12、op counts. The simulation results showed that the AODV routing protocol is applicable to the larger the network,and performed well in the case of high packet rate, but network nodes move too fast will reduce the communication quality agreement.Key wordsAd hoc; AODV routing protocol; Performance Anal

13、ysis; NS2 simulation目录第1章 Ad Hoc网络11.1 无线网络通信技术简介11.2 Ad Hoc网络的开展21.3 Ad Hoc网络工作原理21.4 Ad Hoc网络特性与应用31.4.1 Ad Hoc 网络特性31.4.2 Ad Hoc 网络应用4第2章 AODV路由协议52.1 Ad Hoc 路由协议介绍52.2 AODV路由协议简介62.3 AODV路由协议路由表72.4 AODV路由协议分组格式82.4.1 RREQ 路由请求82.4.2 RREP 路由回复92.4.3 RERR 路由错误102.4.4 RREP-ACK 路由回复确认102.4.5 Hello报

14、文102.5 AODV路由协议工作过程11 维护序列号11 生成路由请求12 路由请求处理13 路由回复处理15 路由维护162.6 AODV路由协议性能20第3章 AODV路由协议仿真213.1 性能指标213.2 仿真工具简介223.2.1 NS2介绍223.2.2 NS2网络协议仿真233.3 AODV仿真环境243.4 AODV仿真过程25 网络节点运动场景设计25 网络负载场景设计263.4.3 tcl仿真脚本26 仿真与结果分析27第4章 仿真结果与分析304.1 不同网络规模的网络模型304.2 不同移动速度的网络模型334.3 不同发包速率的网络模型364.4 仿真分析结论39

15、结论40致谢41参考文献42第1章 Ad Hoc网络1.1 无线网络通信技术简介随着科技的开展，无线网络通信得到了迅速的开展，以满足了人们生活和生产的需求，同时人们对摆脱有线网络束缚的要求也越来越强。在无线通信中，基于根底设施的无线通信技术越来越成熟，如基于基站和移动交换中心的蜂窝移动通信技术、基于有限骨干网的无线局域网如IEEE 802.11系列协议等通信技术，在通信质量和通信范围上均到达商用标准。此外，GPS作为一个由卫星收发数据的通信技术，但其单向通信限制了在日常通信中的语音传输等。在某些特定场合和环境如抗灾救险、偏远山区、沙漠和海洋科考探险等中，基于根底设施的无线通信将无法使用，GPS

16、能帮助人们定位，却不能在相互之间以与和外界进行有效地双向通信，因而无线自组网通信成为最适合的通信方式。无线自组网通信技术包含了蓝牙(Bluetooth)技术、移动Ad hoc(Ad Hoc是一个拉丁词汇，意思是即兴、临时网络技术等。蓝牙(Bluetooth)是由爱立信、英特尔、诺基亚、IBM和东芝等公司1998年推出的一种短距离无线通信技术，用于在较小的范围内通过无线连接的方式实现固定设备或移动设备之间实现灵活、平安、低功耗、低本钱的语音和数据通信。蓝牙技术的连接方式无须任何复杂软件支持，其软件体系是一个独立的操作系统，不与任何操作系统捆绑。在组网方式上，通过蓝牙设备中的主设备与从设备可以形成

17、一点到多点的连接，即在主设备周围组成一个微微网，网内任何从设备都可与主设备通信。但是一个主设备同时最多只能与网内的7个从设备相连接进行通信，在一个有效区域内多个微微网通过节点桥接构成散射网。但蓝牙设备相互之间的通信距离在10米左右，距离稍远时无法实现有效通信。蓝牙技术常应用于应用到无线传感器网络，同时它也可广泛应用于无线短距离通信设备中，例如打印机、蓝牙耳机、医疗健身、智能建筑等无线短距离通信设备。为了能够在没有固定基站或者接入点无法正常工作的环境中进行实时有效通信，一种能够临时快速自动组网的移动通信技术Ad Hoc网络技术应运而生。1.2 Ad Hoc网络的开展Ad Hoc网络的前身是分组无

18、线网PRNET(Packet Radio Network，对分组无线网的研究源于军事通信的需要。早在1972年，美国DARPA(Defense Advanced Research Project Agency启动了分组无线网PRNET(Packet Radio NETwork工程，研究分组无线网在战场环境下数据通信中的应用。工程完成之后，DAPRA又在1993年启动了高残存性自适应网络SURAN(SURvivable Adaptive Network工程。研究如何将分组无线网PRNET的成果加以扩展，以支持更大规模的网络，还要开发能够适应战场快速变化环境下的自适应网络协议。1994年，DARP

19、A又启动了全球移动信息系统GloMo(Globle Mobile Information Systems工程。在分组无线网已有成果的根底上对能够满足军事应用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究，并一直持续至今。1997年成立的IEEE802.11标准委员会采用了“Ad hoc网络一词来描述这种特殊的对等式无线移动网络1。由于无线通信和终端技术的不断开展，Ad Hoc网络在民用环境下也得到了快速开展，例如在没有有线根底设施的地区进行临时通信时，可以很方便地通过搭建Ad Hoc网络实现。1.3 Ad Hoc网络工作原理Ad Hoc网络是由一组带有无线收发装置的自主的无线节点

20、或终端通过相互合作形成的网络，可以独立于固定的根底设施，是一种自创造、自组织和自管理的网络。Ad Hoc网络不需要有线根底设备的支持，通过移动节点自由的组网实现通信。在AdHoc网络中，网络中所有节点的地位平等，均具有普通移动终端所需的功能，而且具有报文转发能力，无需设置控制节点。网络中节点间的通信可直接通信，也可以经过中间节点的转发完成，因此AdHoc网络的节点间通信可能经过多跳。当两个移动节点在彼此的通信覆盖范围内时，它们可以直接通信。但是由于移动节点的通信覆盖范围有限，如果两个相距较远的节点要进行通信，那么需要通过它们之间的移动节点的转发才能实现。因此在Ad Hoc网络中，节点同时还是路

21、由器，担负着寻找路由和转发报文的工作。在Ad Hoc网络中，每个节点的通信范围有限，因此路由一般都由多跳组成，数据通过多个节点的转发才能到达目的地，故Ad Hoc网络也被称为多跳无线网络2。Ad Hoc网络可以看作是移动通信和计算机网络的交叉。在Ad Hoc网络中，使用计算机网络的分组交换机制，而不是电路交换机制。通信的节点一般是便携式计算机、个人数字助理(PDA等移动终端设备。Ad Hoc网络不同于目前因特网环境中的移动IP网络。在移动IP网络中，移动节点可以通过固定有线网络、无线链路和拨号线路等方式接入网络，而在Ad Hoc网络中只存在无线链路一种连接方式。在移动IP网络中，移动节点通过相

22、邻的基站等有线设施的支持才能通信，使用因特网的传统路由协议，而Ad Hoc网络没有这些设施的支持，网络节点间可直接通信。此外，在移动IP网络中移动节点不具备路由功能，只是一个普通的通信终端，当移动节点从一个区移动到另一个区时并不改变网络拓扑结构。而Ad Hoc网络中移动节点的移动将会导致拓扑结构的改变,当移动节点移动时进入或者退出网络，Ad Hoc网络节点检测其所涉与到的路由的更改，将会发出命令或请求如RREQ重新建立可用路由。1.4 Ad Hoc网络特性与应用1.4.1 Ad Hoc 网络特性Ad Hoc网络具有常规移动蜂窝通信网和无线局域网所难以到达的网络特性，它所特有的网络特性如下3：1

23、.自组织性：Ad Hoc网络可以在任何时刻任何地点构建，而不需现有的信息根底网络设施的支持。节点可以通过自身分层协议和分布式算法协调各自行为，快速地组建一个独立的网络。2.分布式控制：Ad Hoc 网络没有严格的控制中心，用户节点之间的地位是平等的，路由功能集成到移动用户节点中，不存在类似基站的集中网络中心控制点。节点可以随时加人和离开网络，任何节点的故障都不会影响整个网络的运行，网络具有很强的抗毁性和鲁棒性。而常规的通信网络受基站、控制中心、路由器等束缚，用户之间地位不平等，影响网络的抗毁性和鲁棒性。3.多跳路由：当节点要与其覆盖范围外的节点进行通信时，需要中间节点的多跳转发。与固定网络的多

24、跳转发不同，Ad Hoc 网络中的多跳是由普通的网络节点完成的，而不是由专用的路由设备完成的。4.动态网络拓扑结构：Ad Hoc网络中，用户终端的移动具有很大的随机性，加上无线发射装置发送功率的变化、无线信道间的互相干扰以与地形等综合因素的影响，网络的拓扑结构可能随时发生改变。5.能量限制：由于Ad hoc网络中节点均为移动节点，依靠电池供电，限制了其能量供应使用。6.平安性：Ad hoc网络作为无线网络，采用的无线信道、分布控制，其平安性相对有线网络差，更易受到窃听、电子欺骗和拒绝效劳等攻击。1.4.2 Ad Hoc 网络应用Ad hoc网络特殊的网络特性决定了其应用范围和有线网络的有着较大

25、区别。它常被用于无法或者不便铺设网络设施的场合、需要快速自动组网的场合等。这些特殊的环境可能在军事环境，也存在于民用或者商业应用上，具体的应用如下：1. 移动会议:在室外临时环境中，工作团体的所有成员可以通过Ad Hoc组网方式组成一个临时网络来协同完成一项大的任务，或协同完成某个计算任务。在室内办公环境中，办公人员携带的包含收藏器的PDA可以通过Ad Hoc无线方式自动从台式机上下载电子，更新工作日程表等。2. 家庭网络:通过移动联网的方式把办公室的办公环境延伸到家庭，必要时在家庭办公。或者利用我们随身携带的个人无线设备与装备了收发器的家庭电器通信，自动完成开锁、开灯、翻开娱乐设备、调节空调

26、等操作。3. 紧急效劳:由于停电或其他灾害出现，网络根底设施遭到破坏时，组建一个网络帮助紧急救援人员完成必要的通信工作。4. 传感器网络:最近人们开始关注大量分布的传感器协调工作问题。传感器可以工作在危险的环境(如化学有害物质泄漏现场)，通过在传感器上装备位置指示器、收发器等，将传感器所在现场的信息传送到危险现场以外，防止救援人员进入现场，收集和区分事故信息。5. 军事无线通信:军事应用是Ad Hoc网络技术的主要应用领域。因其特有的无需架设网络设施、可快速展开、抗毁性强等特点，它是数字化战场通信的首选技术。Ad Hoc网络技术己经成为美军战术互联网的核心技术。6. 其他商业应用:如未来装备收

27、发设备的机场预约和登机系统可以自动地与乘客携带的个人无线设备通信，完成目前的换登机牌等手续。第2章 AODV路由协议路由协议作为影响网络性能的一个重要因素，是确保Ad Hoc网络正确运行的关键。路由协议的主要作用是迅速准确地计算到达目的节点的路由，同时通过监控网络拓扑变化来更新和维护路由。Ad Hoc网络中网络的拓扑结构是动态变化的，路由协议的周期性播送会涉与大量带宽和能量，对系统的性能起到决定性因素，因此，对路由协议的深入了解和分析至关重要。2.1 Ad Hoc 路由协议介绍Ad Hoc网络是由一系列移动节点组成的自组织网络，不依赖任何已有的网络根底设施或集中的管理控制中心。在移动自组网的研

28、究和开发过程中，涉与到路由协议、功率控制、数据平安等关键技术，其中路由协议是人们研究的重点，并提出了一系列路由协议如 DSR，DSDV，AODV，TORA 等。通常将路由协议主要分为两种类型：表驱动路由协议和按需路由协议4,5。1. 表驱动路由协议表驱动路由协议是网络不管是否需要通信时都建立从一个节点到网络中所有其它节点的路由，并以路由表的形式存储在节点中，当需要发送报文时那么马上能找到所需路由并加以使用；当网络发生变化时，协议通过播送将包含路由变化的更新信息即报文，从而保持路由表信息与网络拓扑结果的变化之间的一致性。典型的表驱动路由协议有DSDV(destination-sequenced

29、distance-vector routing)、CGSR(cluster head gateway switch routing)和WRP(wireless routing protocol)等。表驱动路由协议虽然可以很快地获得到其它所有节点的路由，但是不可防止地存在信号拥塞和能量过度消耗的问题，在使用中规模和续航使用时间都存在缺乏。2. 按需路由协议按需路由协议和表驱动路由协议相反，只有在需要通信时才建立连接，即有报文需要发送时才开始寻找路由，找到路由后开始发送报文。典型的按需路由协议有AODV(Ad hoc on-demand vector touting)、DSR(dynamic so

30、urce routing)、TORA(TemporarilyOrdered Routing Algorithm)等。当源节点需要到达某一目的节点的路由时，它在网络中发起一个路由发现过程，路由建立之后，会有一个路由维护程序进行维护，直到每条路径都断裂或者不需要路由为止。按需路由协议不像表驱动路由协议那样实时地维持每个节点的路由信息，因此降低了对网络带宽和能量的消耗。但是在发送数据分组时，如果没有去往目的节点的路由，数据分组需要等待因路由发现而引起时延。通过对国内外有关方面研究的学习了解发现，在各种不同的情况下比拟时，如数据源数、节点的移动性、自组织网络模型以与网络负载等等，按需路由协议要比表驱动

31、路由协议在性能上有着明显的优势。本文就按需路由协议中的AODV路由协议进行学习，并搭建仿真平台，对AODV路由协议进行仿真分析。2.2 AODV路由协议简介AODV路由协议中文全称为无线自组网按需平面距离矢量路由协议(Ad hoc On-Demand Distance Vector Routing，该协议是在DSDV协议根底上结合类似DSR中的按需路由机制加以改良后提出的。AODV路由协议由Nokia研究中心的Charles E.Perkins和加利福尼亚大学Santa Barbara的Elizabeth M.Belding-Roryer以与Cincinnati大学Samir R.Das等共同

32、开发,已经被 IETF MANET工作组于2003年7月正式公布为自组网路由协议的RFC标准6AODV路由协议采用了路由发现和路由维护机制，又利用逐跳路由、顺序编号和路由维持阶段的周期性更新，还参加了对组播路由QOS(Quality of Service)的支持。AODV路由协议其最显著的特点是为路由表中每个项都使用了目的序列号，因而还可以防止环路的发生，并且很容易编程实现。AODV路由协议是按需式路由协议又称反响式路由协议7。在源节点需要通信时才在网络中发送路由分组，而不会周期性地交互路由信息以得到所有其它主机的路由；同时它具有距离向量路由协议的一些特点，即各节点路由表只维护本节点到其他节点

33、的路由，而无须掌握全网拓扑结构。AODV协议工作过程可简单的看作是源节点发起路由请求RREQ，在查找并建立路由后进行通信，并通过使用一个或多个可用连接或者网络层的机制实现连接的保持，在通信完成后断开连接并释放带宽。AODV路由协议在节点移动而导致路由拓扑结果变化时，将会发出路由错误请求来删除错误路由，寻找适宜畅通的路由，从而保证了路由信息和网络拓扑结构保持一致。2.3 AODV路由协议路由表AODV是一个路由协议，它的工作就是管理路由表。即使是短期的路由，也必须保存它在路由表里的信息，比方为RREQ临时存储的返回路径。AODV路由协议的每个路由表项将会包含以下的域：1. 目的节点IP地址：每个

34、表项都具有不同的目的路由器IP地址，以此作为区别和查找网络路由的关键字；2. 目的节点序列号：可防止网络产生环路，只有当收到的RREP和RREQ中传送的序列号比本节点对应路由表项中目的序列号大时才能被接收并用于更新路由表项；3. 目的节点序列号是否正确的标志：显示路由表项中目的序列号是否有效；4. 网络接口；5. 下一跳：到达目的节点的路径上的下一跳节点的地址；6. 跳数：从本节点到达目的路由器所需要的跳数；7. 生存时间：路由过期或应当删除的时间；8. 先驱表：先驱链表指针指向使用此路由表项的所有可能的邻居节点地址；9. 其他状态和路由标志：如路由有效、无效、可修复、正在修复。当一个节点从它

35、的邻居接收到一条AODV控制包时，以与为某个特定的目的节点或目的子网创立或更新它的路由表的时候，它就会去检查它的路由表里是否有一个表项对应到那个目的。当没有相关的表项时，新的表项就会被创立。路由在新序列号满足以下三种条件时更新：1. 新序列号要比路由表里原来的原目的序列号大；2. 新旧序列号相等，但是新信息里包含的跳数加一比原来的跳数小；3. 新序列号是未知的。路由表里的生存期从路由消息里得到，或设置为ACTIVE_ROUTE_TIMEOUT毫秒。有效路由可以用作发送数据包，并且能满足其他的路由请求。当一条路由被用来转发一个数据包时，此路由的源节点、目的节点和下一跳节点的路由生存期都会被更新，

36、新的值不小于当前时间加上ACTIVE_ROUTE_TIMEOUT(有效路由超时。由于每对发起节点和目的节点之间的路由应当是对称的，节点上一跳路由的生存期也会被更新为不小于当前时间加上ACTIVE_ROUTE_TIMEOUT。不管目的地址是单个的节点还是一个子网，每当路由被用到的时候，路由生存期都会被更新。节点将相邻节点的连接状态保存在活动的路由表里，对每个放在路由表项里的有效路由，节点还会维护一张先驱表，这些先驱可能会沿着这条路由转发数据包。路由表项里的先驱列表包含的是都是本节点的相邻节点，路由回复信息将会被发送到这些节点，指出了不能再到达的目的节点。先驱表里的信息可以很轻易的从回传RREP消

37、息的过程中获得。当检测到下一跳断开时，这些先驱就会从本节点收到通知(RERR消息)。2.4 AODV路由协议分组格式AODV路由协议通过路由消息传递信息，包含了路由请求RREQ(Route Request，路由回复RREP(Route Reply，路由错误RRER(Route Error和路由回复确认RREP-ACK。在网络节点在维护通信时，还应用了一种TTL=1的RREP消息，这种消息叫做Hello报文。这些消息通过用户数据包协议(UDP，User Datagram Protocol和通常的IP协议来接收。2.4.1 RREQ 路由请求在Ad Hoc网络中，当一个节点无法找到一个可用路由到目

38、的节点时，它将会利用播送RREQ消息来寻找建立路由通路。路由请求消息的格式如图2-1所示。类型JRGDU保存跳数RREQ ID 路由请求消息标识目标节点IP地址目的节点序列号源节点IP地址源节点序列号图2-1 RREQ消息格式路由请求消息的局部字段定义如下：1. 类型：此字段值1；2. J：Join flag参加标志，为多播保存；3. R：Repair flag修复标志，为多播保存；4. G：Gratuitous RREP flag免费路由回复标志，指是否该向目标节点IP地址域指定的节点发送一个免费路由回复消息；5. D：Destination only flag仅允许目的节点回复标志，标志置

39、位那么仅允许目的节点回复本条路由请求；6. U：Unknown sequence number未知序列号，指目标节点序列号未知；7. 保存：发送时填充0，接收时忽略此字段；8. 跳数：从发起节点到处理该请求的节点的跳数；9. RREQ ID：路由请求标识,这是一个序列号，用它和发起节点的IP就可以唯一标识一个RREQ信息。2.4.2 RREP 路由回复当节点需要对收到的RREQ消息进行回复时，节点将会根据收到的RREQ消息和路由表信息生成路由回复消息RREP，然后按查找相应的反向路由转发RREP。路由回复消息的格式如图2-2所示。类型RA保存前缀长度跳数目的节点IP地址目的节点序列号源节点IP

40、地址生命期图2-2 RREP消息格式RREP路由回复消息局部字段解释如下：1. 类型：此字段值2；2. R：Repair flag修复标志3. A：Acknowledgement required需要确认；4. 前缀长度：非0代表下一跳节点可作任何具有相同路由前缀节点被请求时的目的节点；5. 保存：发送时填充0，接收时忽略此字段；6. 生命期：路由声明时间，单位为毫秒，在这段时间里，收到RREP的节点会认为这条路由是有效的。2.4.3 RERR 路由错误在Ad hoc网络中，可能出现节点间因为某一节点退出网络、信息不可达或者路由信息与网络拓扑结构不符等情况，这时节点将会把路由的错误信息RERR

41、发给相邻节点。路由错误消息RERR的消息格式如图2-3所示。类型N保存不可达目的节点数不可达目的节点IP地址不可达目的节点序列号附加不可达目的节点IP(if needed)附加不可达目的节点序列号(if needed)图2-3 RERR消息格式RERR路由请求消息的局部字段解释如下：1. 类型：此字段置3；2. N：No delete flag不比删除标志：置位时上游节点就不删除此路由；3. 不可达目的节点数：本消息包含的不可达目的节点的数目，必须至少为一；4. 保存：发送时填充0，接收时忽略此字段。2.4.4 RREP-ACK 路由回复确认当目的节点成功收到RREP消息后，目的节点将会发送R

42、REP-ACK消息确认路由回复，其消息格式如图2-4所示。类型保存位图2-4 RREP-ACK消息格式在路由回复确认消息中Type字段置位为4。保存位在发送时填充0，节点接收时忽略此字段。2.4.5 Hello报文在AODV路由协议维护整个网络连接情况时，节点利用周期性播送Hello报文来确定与邻居节点是否保持着连接，然后根据网络连接情况对路由进行建立或更新等维护。Hello报文是 TTL=1的RREP，因此Hello报文只能在相邻节点间传送。对于 Hello报文，设置字段“目的节点IP地址和“目的节点序列号为生本钱报文的节点IP地址和序列号，跳数设置为0，其余字段无效。2.5 AODV路由协

43、议工作过程AODV路由协议在工作中涉与到生成路由请求、节点对生成路由请求的处理、节点接受和转发路由回复以与路由的维护等几个步骤，具体的工作过程如下8,9,10。2.5.1 维护序列号在Ad Hoc网络中，每个节点的路由表项必须包含关于目的节点IP地址的最新可用序列号，这个序列号叫做目的序列号。AODV网络为了保证源节点朝向目的节点的所有路由路径都是无环路的，要求网络中每个节点都要拥有并维护其目的序列号。当节点接收到了跟RREQ、RREP或者RERR消息中的序列号有关的新信息，目的序列号就会更新。在两种情况下目的节点会增加自己的序列号：1. 在节点发起一个路径发现的请求之前，它必须增加自己的序列

44、号。对于已经建立好了的朝向RREQ消息发起者的反向路由来说，这样可以防止本次请求与其相冲突；2. 在目的节点生成RREP消息以响应RREQ消息之前，它必须更新自己的序列号，新的值是它目前的序列号和RREQ消息包中目的序列号的较大者。目的节点的序列号在路由消息中占有32位，它通过无符号整型变量的形式来增加其序列号。当序列号到达32位无符号整型变量所能到达的最大可能值4294967295时，将会使序列号变0。为了确定目的节点的信息是否是新的，当前节点会拿它收到的AODV信息中的序列号数减去自己目前的序列号数，如果结果小于0的话，那么这个接收到的有关目的节点的AODV信息就必须被丢弃。在目的节点使用

45、了不可用的下一跳节点(下一跳丧失或者过期时，当前节点会增加其序列号并把此路径标记为不可用。一旦节点接收到了一个足够新的(也就是包含大于等于本节点所记录的序号，并且是来自于已经标记相应路由表项为不可用的节点的路由信息时，当前节点应该以新的信息来更新其路由表信息。当以下情况发生时，节点需要改变目的路由表项中的序列号：1. 它自己就是目的节点，并且提供了一个到它自己的新的路由；2. 它接收到了一个拥有关于目的节点序列号的新AODV消息；3. 朝向目的节点的路径过期了或者崩溃了。2.5.2 生成路由请求在源节点需要与某一目的节点进行通信时，如果源节点路由表没有到目的节点相应的路由，或者当前路由过期了(

46、或被标记为无效，源节点就会创立一个RREQ(Route Request Packet)消息，通过向自己的邻居播送RREQ来发起一次路由发现过程。RREQ消息在创立时信息位写入情况如下：1. 目的节点序列号：填入最近一次获得的目的节点序列号。如果尚未获得任何目的节点序列号，那么U(未知序列号)标志被置位；2. 源节点序列号：是将发起请求的源节点自己的序列加1后放入；3. RREQ ID：路由请求消息标识，填入该节点上次RREQ ID加1后的值，每个节点只维护一个RREQ ID；4. 跳数：填0；5. G：免费路由回复标志位在需要目的节点回复源节点请求时被置位。在节点播送RREQ消息之前，源节点会

47、将“RREQ ID和“源节点IP地址缓存一段时间，缓存时间由PATH_DISCOVERY_TIME决定。在RREQ消息中的“RREQ ID和“源节点IP地址就可以唯一标识一个RREQ信息。如果从邻居那里收到具有相同“RREQ ID和“源节点IP地址的RREQ消息，它将会认为这是一个发回来的包而将它丢弃。为了防止RREQ的不必要播送，源节点采用“扩张式环搜索作为优化方法，源节点在RREQ分组的IP报头中将生存周期TTL(time-to-live设为初始值TTL-START毫秒，设置等待RREP的超时时间为RING_TRAVERSAL_TIME毫秒。一旦等待超时，源节点重传RREQ，此时TTL值将

48、被加上TTL_INCREMENT。这样一直持续到RREQ包内的TTL到达阈值TTL_THRESHOLD。在到达阈值后，每次使用的TTL都将被设置为NET_DIAMETER。等待路由的数据包(比方在送出RREQ消息后还在等待RREP消息被存在缓冲区里，缓冲遵循“先进先出原那么。如果一个路由寻找过程已经在最大的TTL值下尝试了RREQ_RETRIES次而还没有收到RREP时，所有被缓冲的送往这个目的的数据包都应当被丢弃，并且还应当向应用程序回送一个“目的不可达消息。为减少网络拥塞，源节点向单个目的节点建立连接的尝试必须遵从二的幂次递减原那么。当节点第一次播送一个RREQ消息时，它会等待NET_TR

49、AVERSAL_TIME毫秒来接收RREP消息。如果在这段时间内RREP没有到达，源节点就会送出一个新的RREQ。第二个RREQ的回复消息RREP的等待时间就应当遵从二的幂次递减原那么，也就是，这个等待时间应该为2NET_TRAVERSAL_TIME毫秒。如果在这段时间内RREP消息仍然没到，另一个RREQ就又可以送出去了。在第一个RREQ消息发出去以后，最多还可以再尝试RREQ_RETRIES次。对每一次的尝试，它的等待时间都应当是上一次尝试时间的2倍。这样就从等待时间上保证遵从了网络协议的二的幂次递减原那么。2.5.3 路由请求处理源节点发送的RREQ消息经过无线通路传播而被目的节点或中间

50、节点接收和处理。当节点收到一条RREQ消息时，如果有必要该节点将创立一个到前一跳节点的反向路由或更新原已有反向路由。在建立反向路由时，节点用RREQ中的“源节点序列号作为路由表项中的“目的节点序列号，建立或者更新通向源节点的反向路由。节点将对反向路由表进行以下操作：1. 目的节点序列号：路由建立时，填入RREQ中“源节点序列号；更新路由时，比拟RREQ和路由表里的“源节点序列号的数值，填入较大值；2. 有效序列号：被设置为有效；3. 下一跳：设置为向它发送 RREQ的上一节点；4. 跳数：由 RREQ信息里进行拷贝。任何收到RREQ消息，到发起者IP地址的反向路由表项的生存期设置为现有生存期和

51、最小生存期里的最大值。同时，最小生存期=当前时间+2*NET_TRAVERSAL_TIME-2*跳数* NODE_TRAVERSAL_TIME。收到RREQ路由请求的节点检查在PATH_DISCOVERY_TIME时间内是否收到过具有相同“源节点IP地址和“RREQ ID的RREQ消息，从而判断收到的路由消息是否重复。如果节点已经接收到过相同的RREQ消息，将丢弃这个RREQ而不作任何操作；如果接收到不同的RREQ消息，那么会根据RREQ消息内容生成路由回复消息RREP，并查询节点的反向路由表，选择适当的路由发送RREP消息。1. 节点转发RREQ节点收到非重复的RREQ消息时，将搜索到源节点

52、IP地址的反向路由，如果RREQ消息带“G标志，那么节点将建立或更新反向路由；然后检查RREQ消息的TTL是否大于1，如果TTL大于1，那么这个节点就更新这条RREQ消息；最后在查询路由表在相应网络接口上转发或者播送更新后的RREQ消息。中间节点对RREQ消息做的更新是：(1)IP头内TTL或者跳数限制被减1；(2)跳数：将被加1，用于对新的一跳计数；(3)目的节点序列号：设置为RREQ消息内对应值和节点本身维护的目的节点序列号之间的大者。但是，转发节点一定不能修改它维护的目的节点序列号，即使接收到的RREQ消息内的这个序列号比当前维护的值要大也不行。对于RREQ消息带“G标志时中继节点生成路

53、由回复RREP的情况，在下面介绍节点生成回复RREP中详细讲解。2. 生成回复RREP当一个节点收到非重复的RREQ消息，在下面两种情况下会生成RREP消息：第一种：节点自己就是目的节点；第二种：节点到目的节点有一条有效路由，路由表项内的目的节点序列号有效并且不小于RREQ消息内的目的节点序列号，且RREQ内的“D仅目的节点回复标志位未被置位。节点收到非重复的RREQ消息并且满足以上两种情况时，节点将产生一个RREP消息，节点拷贝RREQ消息中的“目的地IP地址和“源节点序列号到RREP的对应字段。一旦建立了RREP，该节点就把RREP单播至通往RREQ请求发起者的下一跳，该下一跳在到发起者的

54、路由表项中指出。随着RREP被转发回发起RREQ消息的节点，跳数字段也在每一跳加1。这样，当 RREP到达发起RREQ的节点，跳数就代表从目的节点到发起节点的距离。(1)目标节点生成路由回复如果接收RREQ消息的节点就是目标节点，且该节点现有的序列号和RREQ信息里携带的“目的序列号相同，该节点必须让自身的序列号加1。否那么，目的节点不会在生成RREP包以前改变它的序列号。目的节点在生成RREP消息时，将对RREP进行如下操作：a. 目的节点IP地址:发起RREQ的节点的“源节点IP地址；b. 目的节点序列号：填入目的节点的序列号可能是新增加过的；c. 跳数：设置0；d. 生命期：设置为MY_

55、ROUTE_TIMEOUT的值，每个节点都可以在一定的限制下重新配置MY_ROUTE_TIMEOUT的值。(2)中继节点生成路由回复当节点是从源节点到达目的节点的路径上的一个中间节点时，通过把最后跳过的节点从收到RREQ中IP报头源IP地址段中可得到参加了前向路由表项的先驱表，更新了前向路由表项即目的IP地址的入口。中继节点为逆推路由表项，通过把向目的节点的下一跳放入先驱表更新了RREQ发生节点的路由表项-即RREQ消息数据中起源IP地址字段的项。中继节点在生成RREP消息时，将对RREP进行如下操作：a. 目的节点IP地址:发起RREQ的节点的源节点IP地址；b. 目的节点序列号：设置为中继

56、节点所知的“目的节点的序列号；c. 跳数：中继节点到目的节点用跳数在路由表中标识的跳数；d. 生命期：设置为在路由表项中由满期时间减去当前时间得到的时间值。(3)生成未被要求的路由回复当一个节点收到一个RREQ且收到RREP回复之后，它会丢弃掉这个RREQ。如果这个RREQ的G标识位被置位，且中间节点向发起节点返回一个RREP的话，它必须也要单播一个未被要求的RREP到目的节点。这个RREP的各消息字段值设置如下：a. 目的节点IP地址:发起RREQ节点的IP地址；b. 目的节点序列号:来自RREQ的发起节点中的序列号；c. 源节点IP地址:RREQ中目的节点的IP地址；d. 跳数:在节点的发

57、起节点路由表项中被标识；e. 生存期:中间节点所知的从RREQ的发起节点开始的路由剩余生存期。2.5.4 路由回复处理当一个节点收到RREP消息后，它将使用最长前缀匹配方法搜索到前一跳的路由，并且将RREP消息中的跳数值加。当节点到目的节点的前向路由不存在时，那么建立此前向路由。当前向路由存在，该节点将已存储的“目的节点序列号与RREP中的“目的节点序列号相比拟，如果RREP消息中的“目的节点序列号大，并且节点的“目的点序列号是有效的，这时路由将会更新；如果目的序列号是相同的，但路由标示为无效或者新跳数小于路由表项中的跳数，路由也会被更新。节点通过以下操作进行前向路由表项的创立或更新：1. 此

58、路由被标识为活动,且目标序列号被标识为有效；2. 路由表项中的下一跳被指定为在收到的RREP的IP头的源IP地址段所指出的节点；3. 跳数被更新的跳数；4. 路由过期时间被设置为当前时间加上RREP信息中的生命期；5. 目的序列号取RREP中的目的序列号。当节点不是RREP消息中标识的节点，且前向路由已被创立或更新，该节点查询它的路由表项来确定RREP的下一跳，然后使用路由表信息向源节点转发RREP。节点发送了一个RREP,符合目的节点的先驱表中参加下一跳节点以被更新，其RREP被转发。随着RREP传送回源节点，沿路的节点建立到发送RREP节点的转发指针，更新它的路由表中到源节点和目的节点的超

59、时信息并记录请求目的节点的最新的序列号。节点收到RREP消息后传播第一个从给定源节点到源端的RREP消息。如果它后来又收到RREP消息，只有当RREP消息比以前RREP消息有更大的目的节点序列号或者有相同的序列号。但是有更小的跳数时，它才更新它的路由信息并传播这个RREP消息。它阻止任何其他收到的RREP包。这样就减少了传播到源的RREP数量并确保最新和最快的路由信息。源节点当第一个RREP收到后就可以发送数据包，并可以在知道更好的路由后更新路由信息。如果一个节点通过以上路由转发一个可能出错或是单向的RREP，这个节点应该将“A标志位置位以指示此RREP包的接受者送回一个RREP-ACK包确认

60、已接收到该包。2.5.5 路由维护1.维护本地连接如果源节点在活动会话期间移动，它可以重新发起路由发现过程来建立到目的节点的新路由。当目的节点或者中间节点移动时，特别的RREP消息被发往受影响的源节点。定期的Hel10消息可以用来确保同步连接，也可以用来检测连接中断。相反，如果只有很少的延迟，这个错误可以用链路层应答检测到。当试图发往下一跳失败时也可以检测到链路中断。Hello报文只能在相邻节点间进行传播，当节点收到一个Hello包后，就可以新建一个邻居条目或者知道邻居节点与自己依然保持着连接。如果节点在HELLO_INTERVAL微秒内没有邻居节点的Hello包，那么认为该邻居节点与自己不再

61、连接，该邻居节点的路由将被设置为无效状态。就这样，AODV路由协议在Hello报文的协助下完成了整个路由的维护。Hello信息，其RREP信息字段设置如下：(1) 目的节点IP地址：本节点的IP地址；(2) 目的节点序列号：本节点最新的序列号；(3) 跳数：为0；(4) 生命期：设为ALLOWED_HELLO_LOSS * HELLO_INTERVAL。节点收到来自邻居节点的Hello消息，就可以确信具有到这个邻居的有效路由。如果到这个邻居的有效路由不存在，那么建立该路由；如果该路由已经存在，那么增加这条路由的生存期为ALLOWED_HELLO_LOSS*HELLO_INTERVAL。当前节点

62、可以使用这条路线转发数据包。没有被其它活动路径使用的由Hello信息创立的路线将拥有一个空的先驱表，且如果临近节点移走或超时不会触发RRER信息。2.维护路由错误当路由出现错误时，路由错误消息要么被播送如果存在多个前驱节点，要么被单播如果只存在一个前驱节点，要么被反复地单播到所有的前驱节点如果播送不可用。在三种情况下，节点会发起RERR消息过程：(1) 节点检测到一条正传送数据的活动路由的下一跳链路断开；(2) 节点接收到了一个数据包，而路由表中没有到数据包目的节点的活动路由而且也没有修复，只有一个不可达目的地；(3) 节点从邻居节点接收到了一个或多个活动路由的RERR消息。节点首先产生一张不

63、可达目的节点列表，包含不可达邻居节点、使用不可达邻居节点作为下一跳的其它任何目的节点、情况3中RERR中的一些目的地节点。这些目的地节点在本地路由表中存在着对应的路由表项，路由表项的下一跳是所收到的RERR消息的发送者。在发送RERR消息之前，在路由表中要做某些更新，这些更新可能会影响到不可达节点的目的节点序列号。对于每一个目的节点，对应的路由表项应该按如下更新：(1)目的节点序列号：如果存在并可用，那么增1；对于情况3那么从接收到的RERR消息中拷贝；(2)标记路由表项为无效；(3)生存期：被更新为当前时间加上DELETE_PERIOD。路由表中“生存期扮演着两个角色对于活动的路由来说，它是超时时间；对于无效路由来说，它是删除时间。如果接收到了一个无效路由的数据包，“生存期就被更新为当前时间加上DELETE_PERIOD。应该接收RERR消息的邻居节点都是在前驱列表之中的，这个前驱列表是新创立的RERR消息中不可达目的节点之一所创立的。如果只有一个需要接收RERR消息的邻居节点， RERR消息应该向那个邻居节点单播；否那么， RERR消息会被发送到本地播送地址。不可达目的节点IP地址、不可达目的节点序列号、和不可达目的节点个数那么会包含在EREE里。3.维护路由中断当网络中路由发生了连接中断时，如果目的节