无线自组织网络AODV协议仿真研究.doc

本科生毕业设计（论文）任务书学生姓名： 吴雪松 专业班级： 通信0604 指导教师： 周 宁 工作单位： 信息工程学院 设计（论文）题目：无线自组织网络AODV路由协议仿真研究设计（论文）主要内容：在深入研究AODV协议的基础上，以家庭厨房智能家电Ad Hoc网络为应用背景，建立网络仿真模型，并在NS2网络仿真平台上设计针对AODV协议的相关仿真实验。深入分析仿真结果及关键网络参数，验证其性能是否满足于家庭厨房智能家电Ad Hoc网络要求。要求完成的主要任务：1. 查阅相关文献资料15篇以上（其中英文文献不少于2篇）。2. 完成开题报告。3. 深入了解Ad Hoc网络的体系结构、分层情况以及几种典型的路由协议，利用NS2软件对AODV协议进行仿真，并分析仿真结果。4. 在设计中完成不少于3张12#图纸的描绘。5. 完成不少于12000字的论文的撰写并完成答辩的相关工作。6. 完成不低于5000汉字（20000英文印刷符）的教师指定的相关文献的英译汉翻译。7. 完成毕业设计周志。必读参考资料：1Charles E.Perkins，Elizabeth Royer and Samir R.Das.RFC3561：ad hoc on demand distance vector(AODV) routingEB/OL. /rfc/rfc3561.txt.2003.2 NS-2 Tutorial. /nsnam/ns/tutorial/3 NS by Example. /NS/.指导教师签名 系主任签名 院长签名(章)_ 武汉理工大学本科学生毕业设计（论文）开题报告1、目的及意义（含国内外的研究现状分析）无线自组织网络又称为移动Ad Hoc、无线多跳网络等，它是由若干带有无线收发器的节点构成的一个无中心的、多跳的、自组织的对等式通信网络，其前身是美国国防高级计划研究署（DARPA，Defense Advanced Research Project Agency）于1972年所启动的分组无线网（PRNET，Packet Radio NETwork）项目，之后通过全球移动信息系统（Glomo，Global Mobile Information Systems）等项目的推动，无线自组织网技术得到了广泛而深入的研究，一直持续至今。自组织网络技术是移动Ad Hoc研究的一个非常重要的部分。由于自组织网络拓扑结构的动态变化以及资源特性，决定了传统的路由算法不适用于这种自主系统，如何在移动中建立和保持有效、可靠的通信路由成为Ad Hoc研究的热点。目前，一些研究机构提出了许多的路由算法，但是这些算法都各有优缺点。这些算法中，Ad Hoc按需距离矢量算法（AODV，Ad hoc On-demand Distance Vector）的性能优越且实现复杂度低，被IEIF的MARNET（Mobile Ad Hoc NETwork）工作组认为是无线自组织网络最好的候选路由协议之一，因此，AODV也成为自组织网应用与实现方案中路由协议的首选。因此，随着移动自组织网络研究的发展和相关产品的成熟，移动自组网必将越来越受到人们的重视，会有越来越多的应用领域，因而其具有广泛的研究与发展前景，给民用产品的开发也带来了巨大的经济和社会效益。几年来，随着各种短距离无线通信技术的发展，引入了一个新的概念个人局域网（PAN，Personal Area Network）。PAN核心思想是用无线电或红外线代替传统的有线电缆，实现个人信息终端的智能化互联，组建个人化的信息网络。它是一种通信范围大约在10m左右的小型局域网。其中一个很好的应用就是家庭无线网络。家庭无线网络用语支持家庭内部或周围的各种通信电子设备和家用电器的通信与互连。例如，用户可以通过PDA查询电脑中的信息以及控制音响设备，观测室内温度并调节空调，访问Internet进行网上办公和购物等。家庭无线网络面临的最大问题是如何支持不同应用可变的服务质量要求，例如家庭娱乐系统对时延有较高的要求。对于家庭无线网络来说，使用对等结构的Ad Hoc网络是较好的选择：设备间的对等通信不需要中心结点的协调，可以采用多跳路由来节省能量。家庭无线网络中设备的移动性很低，不需要过多考虑移动性限制，主要问题是提供高质量的流媒体服务。2、基本内容和技术方案基本内容：本课题的主要研究内容是Ad Hoc路由协议AODV及NS2仿真，以网络的可靠性和实时性为研究目标，在家庭厨房Ad Hoc的特定场景下，对仿真场景进行建模，通过NS2软件的仿真，根据RFC2501标准文档中对无线自组织网络的路由性能评估制定的评价标准，从中选取封包送达比例（Packet Delivery Fraction）、封包点到点平均延迟时间（Average end-to-end Delay of Data Packets）、第一个封包收到的时间等参数进行性能评估，并与典型的表驱动路由协议DSDV的相关参数比较。分析AODV协议与DSDV协议的优缺点，验证在智能家居系统这一特点环境下，按需路由协议AODV的可行性。 技术方案：首先对所选课题进行深入的理论研究，学习先进理论和思维方法，认真研读相关参考文献，掌握Ad Hoc网络及相关路由协议知识，学习Tcl与Otcl语言，然后深入了解AODV协议的路由表、消息控制帧结构以及路由发现、维护、修复等机制，Unbuntu9.10系统中利用NS2软件对AODV协议进行仿真分析，并与DSDV协议进行比较，其中NS2仿真一般分为以下几个步骤：编写所需构件，测试，编写OTcl脚本文件，用NS命令执行脚本文件，分析trace。根据实验所得数据检验AODV协议应用在家庭厨房智能家电Ad Hoc网络中的可行性。3、进度安排第1-3周：查阅相关文献资料，明确研究内容，了解研究所需理论和技术支持手段。确定方案，完成开题报告。第4-9周：了解Ad Hoc网络的体系结构、分层情况以及几种典型的路由协议并根据家庭厨房智能家电Ad Hoc网络的特点建立网络仿真模型。第10-13周：熟练使用NS2软件，对AODV及相关协议进行相关仿真实验，分析实验所得数据，检验AODV协议应用在家庭厨房智能家电Ad Hoc网络中的可行性。第14-15周：对论文进行系统审查和完善，完成论文终稿并按规范装订论文一式三份。第16周：准备论文答辩。4、指导教师意见 指导教师签名： 年 月 日 注：1开题报告应根据教师下发的毕业设计（论文）任务书，在教师的指导下由学生独立撰写，在毕业设计开始后三周内完成。2“设计的目的及意义”至少800字，“基本内容和技术方案”至少400字。进度安排应尽可能详细。3指导教师意见：学生的调研是否充分？基本内容和技术方案是否已明确？是否已经具备开始设计（论文）的条件？能否达到预期的目标？是否同意进入设计（论文）阶段。武汉理工大学毕业设计（论文）目 录摘 要IAbstractII1 绪论11.1 本文研究背景和意义11.2 Ad Hoc网络国内外研究现状11.3 本文所做的工作及组织结构22 AODV路由协议算法分析研究32.1 AODV路由协议基本原理32.2 AODV路由协议的路由表结构32.3 AODV路由协议消息控制帧42.4 AODV路由算法的详细过程62.4.1 路由发现过程62.4.2 路由维护92.5 AODV路由建立和维持举例112.6 本章小结123 AODV路由协议仿真研究133.1 NS2仿真平台133.1.1 NS2简介133.1.2 NS2仿真环境的搭建143.2 AODV路由协议的实现与NS2仿真153.2.1 仿真性能指标及场景参数的确立153.2.2 使用NS2进行仿真163.3 仿真结果分析及与DSDV性能对比研究183.4 本章小结214 总结与展望224.1 总结224.2 展望22致 谢23参考文献24附录25i摘 要无线自组织网络（Ad Hoc）是当前无线通信领域一种新的、正在发展的网络技术，这种网络是一种工作在无固定结构环境下的自组织的无线移动网络。在当前的智能家居系统中，大多数采用Ad Hoc网络作为内网。由于Ad Hoc网络的拓扑动态性，使得常规路由协议在该环境下无法正常运行，本文在Ad Hoc网络路由协议研究的基础之上，采用AODV按需路由协议的方法，很好地解决了这一问题。本文以智能家居系统为Ad Hoc网络的应用背景，以网络的可靠性和实时性为研究目标，针对无线自组织网络的AODV路由协议进行深入研究，分析了AODV路由协议的路由表、控制帧结构以及详细的路由算法，并以此为基础，对仿真场景建模，采用NS2软件对AODV协议进行仿真，用Awk分析NS2输出的trace，并在分组投递率和端到端延时这两个性能指标上与典型的表驱动路由协议DSDV进行对比，从仿真结果中得出，AODV比DSDV具有更高的分组投递率及几乎相当的端到端延时，保证了极高的可靠性与实时性，从而验证了在智能家居系统这一应用背景下，按需路由协议AODV比表驱动路由协议DSDV更有优势。关键词：无线自组织网络；智能家居；AODV；DSDV；NS2 AbstractA mobile Ad Hoc network is a new and developing network technology in the wireless communication field. This network is an autonomous system of mobile hosts connected by wireless links. In the current intelligent household system, most systems take Ad Hoc as an internal network. Because of constantly changing topology, Ad hoc networks cant adopt traditional routing protocolsOn the base of this papers research，using ad hoc on demand distance vector(AODV) routing is a good solution to this problem.In is paper, intelligent household system is taken to be the Ad Hocs application background. And study the packet delivery ratio, average end-to-end delay according to RFC2501. And base on the relative research, AODV is compared with DSDV on NS2. The result of the project shows that AODV is more feasible for the Ad Hoc network of intelligent household system.Keywords：Ad Hoc; Intelligent household; AODV; DSDV; NS2311 绪论1.1 本文研究背景和意义随着移动通信，个人通信和计算机网络的发展，无线通信网络技术成为当前信息技术中最活跃的一个研究领域1。我们经常提及的移动通信技术一般都是集中式控制的，即为有中心的。它们通常要基于预先架设的网络基础设施才能运行。但对于有些应用场合，比如，发生大型自然灾害后的营救工作，野外科考，战场上部队的快速展开和推进，临时性的大型会议等，就不能依赖于任何预先架设的网络设施，而应该需要一种能够临时快速自动组网的移动通信技术，Ad Hoc网络技术可以满足这些需要2。无线移动Ad Hoc网络中没有专用的固定基站，网络中所有节点都相当于一个移动路由器，所有节点作为同等实体相互连接，实现数据转发，参与路由发现和维护过程。与中心网络相比，无线移动Ad Hoc网络更坚固、耐用，不需要提供固定的骨干设置3。Ad Hoc网络有这动态拓扑网络节点自组织性等特点。因此，随着移动自组织网络研究的发展和相关产品的成熟，移动自组网必将越来越受到人们的重视，会有越来越多的应用领域，因而其具有广泛的研究与发展前景，给民用产品的开发也带来了巨大的经济和社会效益4。而路由协议作为影响网络性能的一个重要因素，是确保移动自组织网络正确运行的关键。对该领域进行深入而广泛的研究将为移动自组网的应用提供重要科学依据。1.2 Ad Hoc网络国内外研究现状90年代以来，移动Ad Hoc网络的研究在世界范围内方兴未艾，已经从无线通信领域中的一个小分支逐渐扩大到相对较独立的领域。目前，国际上在移动Ad Hoc网络方面研究较为活跃的几个研究机构有：美国康奈尔大学Zygmunt J.Hass教授领导的“无线网络实验室”。研究方向包括：Ad Hoc网络重构、Mac协议、路由协议等。网址为：/美国伊利诺斯大学Urbana-Champaign分校Klara Nahrstedt教授领导的“多媒体操作系统和网络小组”。他们参与了美国海军的Ad Hoc网络研究项目，研究方向包括Ad Hoc网络路由、网络管理、拥塞控制、QoS等。网址为：/adhoc/index/html美国国家标准和技术研究所“无线通信技术小组”也设立了Ad Hoc网络项目组，负责对Ad Hoc网络的路由协议性能、Ad Hoc网络仿真工具、传感器网络的组网和应用等进行评估和研究。网址为：/wctg/manet/index/htmlInternet工程任务组也已经成立了专门的研究小组MANET(Mobile Ad Hoc Network)工作组，负责Ad Hoc网络的路由协议的标准化工作。网址为：/html.charters/marnet-charter.html鉴于Ad Hoc网络的特殊性和重要性，自20实际90年代后期开始，国内的一些大学和研究所也开始关注Ad Hoc网络技术，并对它进行了一些研究。比如：解放军理工大学、清华大学、西安电子科技大学等。国内学者所发表的Ad Hoe网络的研究成果较少。目前，国内研究学者的主要成果基本上集中在对路由协议的一些改进上，少量成果涉及MAC层协议的研究。可以说国内在该研究领域基本上是刚刚起步，因此，对这一领域的研究对于国家来讲具有重要的战略意义。1.3 本文所做的工作及组织结构本文以智能家居系统为Ad Hoc网络的应用背景，以网络的可靠性和实时性为研究目标，针对无线自组织网络的AODV(Ad hoc On-Demand Distance Vector Routing)路由协议进行深入研究，在此基础上，采用NS2软件对AODV协议进行仿真，并与典型的表驱动路由协议DSDV(Destination-Sequenced Distance Vector)进行性能对比，以仿真结果验证了在智能家居系统这一应用背景下，按需路由协议AODV比表驱动路由协议DSDV更有优势。本文各章节安排如下：第一章为本文的绪论部分，首先简要阐明了本文的研究背景和意义，然后介绍了当前国内外关于无线自组织网络的研究情况，最后提出了本文研究的主要内容。第二章对AODV路由协议进行了详细分析，包括其AODV基本原理、路由表结构、消息控制帧、以及路由算法的过程。第三章是本文的重点，这一希望通过网络建模与仿真来验证AODV路由协议比典型的表驱动路由协议DSDV更适合于智能家居系统，首先通过实际的工程应用背景建立了网络模型，同时以NS2为网络仿真平台，对AODV和DSDV进行了可靠性和实时性的对比研究，并对仿真结果进行了详细分析。第四章为总结，总结了本文所作的工作。2 AODV路由协议算法分析研究2.1 AODV路由协议基本原理自组织按需请求型距离向量路由协议(AODV) 5-7是在DSDV协议的基础上，结合类似DSR中的按需路由机制进行改进后提出的8。AODV采用逐跳转发分组方式，在每个中间节点隐式的保存了路由请求和回答的结果，因而数据报头部不再需要携带完整的路由信息，从而提高了协议的效率。与表驱动路由协议不同的是，按需驱动路由协议只有当源节点需要到目的节点的路由或者当某个节点希望加入一个多播组时才寻找路径。此外AODV另一个显著的特点是它加入了组播路由协议扩展，并支持QoS(Quality of Service)。它的缺点是不支持单向信道，原因是AODV协议基于双向信道的假设工作，路由回答分组直接沿着路由请求的反方向回到源节点。AODV协议中，当一个源节点希望建立通向某个目的节点的路径时，源节点发起一个路径发现程序，它广播RREQ(Route Request)给它的邻近节点（相互处于对方的无线电覆盖范围之内的节点），RREQ再被这些邻近节点转发，直到到达目的节点或一个拥有到达目的节点的足够新鲜路径的中间节点。在转发RREQ的时候，中间节点在它们的路由表中记录第一个转发给它们RREQ的邻近节点通过这样的方式来建立一条反向路径。一旦RREQ到达了目的地或拥有一条通向目的节点足够新的路径的中间节点，则目的节点和中间节点通过建立的反向路径单播一个RREP(Route Reply)给转发给它RREQ拷贝的邻近节点。当RREP通过反向路径到达源节点的过程中，这条路径上的节点在它们的路由表中建立起通向目的节点的正向路径。路由表项建立以后，路由中的每个节点都要执行路由维持、管理路由表的任务，其路由表中都需要保持一个相应目的地址的路由表项，以实现逐条转发。在维护路由表的过程中，当路由不再被使用时，节点会从路由表中删除相应项。同时，节点会监视一个活动路由中下一跳节点的状况，当发现有链路断开的情况时，就发出路由错误RERR(Route Error)消息通知其他结点以修复路由。在RERR消息中，指明了由于断链而导致无法到达的目的节点。每个节点都保留了一个“先驱列表来帮助完成错误报告的功能，该列表中保存了该节点的一个相邻节点，而这个相邻节点的去往故障节点的下一跳就是当前节点。2.2 AODV路由协议的路由表结构AODV的路由表中储存下面几项信息：l 目的节点IP地址l 目的节点序列号l 目的节点的序列号为有效（或者无效）的标志l 另外的状态或者路由标志（有效或者无效，可修复，或者正在修复）l 网络接口（移动节点访问信道的接口)l 到达目的节点所需要的跳数l 下一跳地址l 前向指针列表l 链路生存期（路由过期或者被删除的时间）目的节点序列号可以防止网络产生环路，只有当收到的RREP和RREQ中传送的序列号比本节点对应路由表项中的序列号大或者相等时，才有可能被接收用于更新路由表项。目的序列号标志显示是否有效。其他标志表明该条路由为有效或者无效，是否可修复或者正在被修复。前向指针列表指向使用该路由表项的所有邻居节点地址。链路生存期表明该路由表项是过期或者已经被删除。当状态标志是有效时，生存期是它的过期时间；当标志为已过期时，生存期是它的删除时间。管理序列号是避免路由环出现的关键。当一条链路断开，某些节点不能提供自己的序列号，某些目的节点变得不能到达时，路由把目的序列号变为无效，并且把路由表的状态标志为无效。2.3 AODV路由协议消息控制帧AODV路由协议中有三种类型的消息控制帧：路由请求RREQ，路由应答RREP和路由错误RERR消息。RREQ分组格式如下：表2-1 RREQ分组格式Type(8bit)JRGDUReserved(11bit)Hop Count(8bit)RREQ IDDestination IP AddressDestination Sequence NumberOriginator IP AddressOriginator Sequence Numberl Type：l；l J：参与标志；(1 bit，为多播保留)l R：修复标志；(1 bit，为多播保留)l G：免费RREP标志；指明中间节点是否将免费RREP发送至目的IP地址域中列出的节点；(1 bit)l D：只允许目的节点对RREQ做出回应的标志；(1 bit)l U：未知序列号；指出目的节点的序列号未知；(1 bit)l Reserved：保留位；发送时置0，接受时忽略；l Hop Count：从源节点IP地址到对该请求信息做出回应的节点之闻的跳数；l RREQ ID：每一个RREQ信息都具有唯一的ID，与源节点的IP地址配合使用来标志特定的RREQ信息；l Destination IP Address：目的节点IP地址；l Destination Sequence Number：目的节点序列号；l Originator IP Address：源节点口地址；l Originator Sequence Number：源节点序列号。RREP分组格式如下：表2-2 RREP分组格式Type(8bit)RAReserved(11bit)Prefix size(5 bit)Hop Count(8bit)Destination IP AddressDestination Sequence NumberOriginator IP AddressLifetimel Type：2；l R：修复标志(用于多播)；l A：需要通知；用于当发送RREP应答的连接可能是不可信的或者单向连接时。如果RREP信息里已经设置了“A”位，收到RREP节点应该返回一个RREP-ACK信息；l Reserved：保留位；发送时置0，接受时忽略；l Prefix Size：如果不为0，这5 bit的前缀说明指定的下一跳节点可能被具有同样前缀的任何一个节点作为请求的目的地址：l Hop Count：从源IP地址到目的IP地址的跳数；l Destination IP Address：同RREQ；l Destination Sequence Number：同RREQ；l Originator IP address：同RREQ；l Lifetime：以毫秒计；节点收到RREP后计算的路由有效时间。这个值是在目的节点/中间节点对RREQ产生应答RREP时确定的，为目的节点/中间节点对应路由表项超时的时间，当源节点收到该RREP时利用该值设置对应路由表项的超时时间，以和目的节点/中间节点的路由表项生存期保持一致。RERR分组格式如下：表2-3 RERR分组格式Type(8bit)NReserved(15bit)DestCount(8bit)Unreachable Destination IP Address(1)Unreachable Destination Sequence Number(1)Additional Unreachable Destination IP Addresses(if needed)Additional Unreachable Destination Sequence Numbers(if needed)l Type： 3；l N：不删除标志；当节点进行了连接的本地修复，逆向节点不应该删除该条路由时设置；l Reserved：保留位；发送时置0，接受时忽略；l DestCount：在该RERR信息里包含的不能到达的目的节点的个数，至少为l；l Unreachable Destination IP Address：当连接断开时不能到达的目的节点的m地址：如果多个目的节点不能到达则列在Additional Unreachable Destination IP Addresses域中；l Unreachable Destination Sequence Number：不能到达的目的IP地址域里列出的目的节点的序列号：如果多个目的节点不能到达则列在Additional Unreachable Destination Sequence Numbers域中。RREP ACK分组格式如下：表2-4 RREP ACK分组格式Type(8bit)Reserved(8bit)l Type：4；l Reserved：保留位；发送时置0，接受时忽略。RREP-ACK (Route Reply Acknowledgment)消息只有在RREP信息设置了“A”位时才会发送，特别是当该链路有可能是单向链路，会影响路由发现时用到。2.4 AODV路由算法的详细过程2.4.1 路由发现过程AODV的路由发现过程由反向路由的建立和前向路由的建立两部分组成。反向路由指从目的节点到源节点的路由，用于将路由响应报文回送至源节点，反向路由是源节点在广播路由请求报文的过程中建立的，具体过程见下文介绍，如图2-1所示。前向路由指从源节点到目的节点方向的路由，用于以后数据报文的传送，前向路由是在节点回送路由响应报文的过程中建立起来的，如图2-2所示。图2-1 反向路由的建立图2-2 前向路由的建立（1）路由请求的产生当源节点需要与目的节点进行通信时，它首先在自己的路由表中查找是否存在到达该目的节点的有效路由。若路由表中已包含了到达该目的节点的有效路由，则使用此路由发送数据分组，否则它将启动一个路由发现过程，广播一个路由请求分组RREQ，来找到一条到达该目的节点的有效路由。每个节点都有两个独立的计数器：“分组ID”和“源节点IP地址”，用于唯一标示一个路由请求，当源节点再次发起一个新的路由发现过程时，ID就加1，“源节点序列号”用于在广播路由请求的过程中保证反向路由的有效性，该字段值为源节点维护的当前序列号值加1；目的节点序列号则说明了到目的节点的路由在被源节点接收前所必须有的新鲜度，如果路由表中没有该序列号，则将目的序列号设为0。（2）路由请求的转发与处理收到RREQ的节点，首先创建或更新到前向节点的缺少有效序列号的路由。然后，判断是否在PATH_DISCOVERY_TIME曾经收到过具有相同源ID地址和源节点序列号的RREQ信息。如果是，则丢弃当前分组，否则将RREQ的“跳数”加1。接下来，在节点路由表中查找是否有一条通往源节点的反向路由：如果没有，就利用RREQ中的“源节点D地址”和“源节点序列号”建立一条通往源节点的反向路由，这样该节点在此后处理返回源节点的RREP时，就可直接使用该反向路由进行单播转发。反向路由的表项主要有如下设置：“目的节点m地址”设为RREQ中的源节点m地址；“目的节点序列号”设为RREQ中源节点序列号；“下一跳节点设为广播RREQ的邻居节点；“跳数设为RREQ中的跳数值。如果有，但RREQ中携带的源节点序列值比节点路由表中存储的源节点序列值大，或二者序列值相等，但RREQ中的跳数值比节点路由表项中的小，以上两种情况都需要对现有表项进行更新。如果当前节点不是目的节点，则对RREQ的部分字段进行更新(如，将IP头中的TTL和跳数最小值域分别减1)，并向所有邻居转发更新后的RREQ分组。如果产生RREP的节点是目的节点本身，或当前节点的路由表中存在到达目的节点的有效路由，则生成一个RREP分组，并将RREQ的目的节点口地址和源节点序列号复制到RREP分组的相应区域。若是中间节点回复RREP，那还要检查RREQ的G标记是否被置位：如果未置位，则只需向源节点单播发送该RREP，如果被置位，则向源节点单播发送RREP后，还要向目的节点单播一个无偿RREP，以通知目的节点创建一条通往源节点的路由。目的节点回复的RREP主要字段设置如下：“目的节点口地址”设为目的节点口地址，“目的序列号”设为目的节点维护的当前序列号(可能要加一)，“源节点地址”设为产生RREQ的源节点ID地址，“跳数”置为0，目的节点把RREP信息里的生存期域设为MY _ROUTE_TIMEOUT，每个节点都可以在适度的约束下重新设置MY_ROUTE_TIMEOUT值。中间节点回复的RREP主要字段设置如下：“目的节点口地址”设为目的节点口地址，“目的序列号”设为节点路由表项中存储的目的序列号，“源节点口地址”设为产生RREQ的源节点口地址，“跳数”设为自己到达目的节点的跳数值，RREP里的生存期域是由路由表的过期时间减去当前时间计算得来的。无偿RREP的主要字段设置如下：“目的节点口地址”设为产生RREQ请求的节点的IP地址，“目的序列号”设为RREQ中的源节点序列号，“源节点口地址”设为RREQ中的目的节点IP地址，“跳数”设为该中间节点到源节点的跳数值，“生存时间”设为：中间节点所知的，通往RREQ发起者路由的剩余生存期。回复了RREP后节点就可丢弃已处理过的RREQ。（3） 路由回复的处理与转发当节点收到RREP消息时，它首先建立或更新没有有效序列号的到上一跳的路由。然后，将RREP中的“跳数加1，得到新跳数值。接下来，若不存在一条指向目的节点的路由，则创建一条到达目的节点的正向路由。否则，看节点路由表中该正向路由是否需要更新，是则给予更新。己经存在的路由表项在下面几种情况下会进行更新：现有表项中的序列号已经被标志为无效；RREP信息里的目的序列号比该节点己知的目的序列号大并且已知目的序列号的是有效的；序列号相同，但是路由己经被标志为不活跃；序列号相同，但新跳数值比现有表项中的跳数值小。若当前节点不是源节点，则找出路由表中通向源节点的反向路由(在处理RREQ时已建立)，节点根据反向路由的表项信息，决定接下来将RREP单播传给哪个节点。若当前节点是源节点，它就可立即使用该正向路由来进行数据包的发送。2.4.2 路由维护路由维护的方式分为邻居发现和链路层反馈两种。邻居发现是节点周期性的广播TTL=1的HELLO广播报文，收到报文的节点知道发送者是其邻居，这样就维护和其邻居的本地互连性，HELLO报文格式和RREP报文格式相同。如果在一定时间内，节点没有收到邻居的HELLO报文，并且路由表中存在以该邻居作为下一跳的路由表项，节点就会广播RERR报文。链路层反馈是当转发数据报文时，如果在链路层收到下一跳节点路由信息里通告目的节点不可达的报文，即下一跳没有通往目的节点的路由，则表明路由中断，根据中断节点离源节点和目的节点跳数的比较来选择进行本地恢复或广播RERR报文。在下面三种情况下，节点会发送RERR报文：1) 邻居发现时，当邻居不可达时，遍历路由表找到所有以该邻居作为下一跳的路由表项，构造RERR报文，把这些路由表项中的目的地址、序号依次放入RERR报文的不可达目的节点地址数组、序号数组中，然后广播此报文；2) 转发数据报文时，存在到目的节点的路由，但其标志为DOWN，说明此路由表项过期，构造RERR报文，把这个路由表项中的目的节点地址和序号放入报文不可达目的节点地址数组和不可达目的节点序号数组中，并丢弃数据报文；3) 转发数据报文时，存在到目的节点的路由；其标志为UP，但实际转发时，收到链路层的不可达报文，如果当前节点到目的节点的跳数大于到源节点的跳数，会广播路由错误报文，这是通过链路层反馈得到邻居节点不可达信息，采用和第一种情况相同的方式构造RERR报文。收到RERR报文的节点，对报文中每个不可达目的节点，在路由表中查找以不可达目的节点为目的节点并且以RERR报文发送者作为下一跳的路由表项，把路由标志置为DOWN状态，并判断路由表项的前向节点地址是否为空，如果不为空，则把这个不可达目的节点信息放入新构造的RERR报文中。只有当使用一条状态为UP的路由表项转发报文失败时，并且当前节点到目的节点的跳数小于到源节点的跳数，才进行本地恢复。当前节点把转发失败的数据报文插入报文缓存队列中，并把使用到的那个路由表项置为REPAIR状态，然后广播RREQ报文，同时开启一个本地恢复定时器，如果在定时器到期时，当前节点仍然没有收到RREP报文，则会把使用的路由表项置为DOWN。如果收到RREP报文，则说明到目的节点的路由恢复。当中断节点发送RREQ报文时，原来路径中的上一跳节点和下一跳节点由于具有到中断目的节点的活跃路由，都会发送RREP报文。根据收到RREP报文时更新到目的节点路由的条件3)得知，为了消除回环，只有当从新路径比原来路径到失败目的节点的跳数小时，才接受RREP报文。AODV协议的流程图可用图2-3表示：图2-3 AODV协议的流程图2.5 AODV路由建立和维持举例如图2-4所示，有8个编号由1到8的node，当source有TCP的资料要传送时，AODV会将RREQ的信息广播出去，中间的node第一次收到RREQ就会再加以广播出去，并将RREQ的org IP填到routing table。这个routing table在RREP送回source时会用到，如果已经收到过相同的RREQ，则会将RREQ丢弃掉。图2-4 收到RREQ后各个node的routing table改变的情形当destination收到RREQ，回送RREP的信息给source，当中间的点收到RREP时就会将RREP的dst IP填到routing table的destination，将RREP的org IP填到routing table的next hop建立routing table，并更新RREP的org IP为自己的IP。如此路径上的点都知道要到destination的next hop是哪个node，如图2-5所示。图2-5 收到RREP后各个node的routing table改变的情形当node3检测到断线，node3会判断自己离destination的hop数是不是小于1/3的network diameter，此为AODV中的参数，会随着网络的大小而不同，如果小于1/3的network diameter则会启动local repair的机制，会从node3将RREQ的信息广播出去，并且把source传来的packet buffer在node3，直到收到RREP，才把buffer的packet送出去。但是经过一段时间而一直没有收到RERR的信息，则表示local repair失败，会清除buffer的packet，并送回RREP的信息给source。反之，如果大于1/3的network diameter的话则会传出RERR的信息给他的上游node和source告知断线，收到RERR的node会将Unreachable Destination从routing entry删除，当source收到RERR如果AODV的queue中有packet要传送的话，则会发出RREQ的信息区重新找寻路径，如图2-6所示。图2-6 node4移动后由node3进行local repair之后routing table改变的情形2.6 本章小结本章是对AODV协议进行研究的重点内容，在这一章中，分为五个部分来分析AODV协议，第一部分是AODV路由协议基本原理，第二部分是AODV路由表结构，第三部分是AODV路由协议消息控制帧，分别包括路由请求RREQ，路由应答RREP和路由错误RERR消息，第四部分是AODV路由算法的详细过程，主要由路由发现过程和路由维护过程，第五部分用举例的方式来更形象地说明了AODV协议的路由建立和保持。3 AODV路由协议仿真研究网络仿真是进行网络技术研究的一种基本手段。在新技术的研究过程中，由于各种原因，实际网络系统的实现往往是代价较高的或是不现实的。这种情况下，仿真就成了最佳可供选择的测试、评估和验证手段之一。网络仿真有着周期小、成本低的特点，而且可以使研究者更专注自己研究的部分而不必为系统其它部分耗费过多精力。典型的用于Ad Hoc网络研究的网络仿真器主要有NS29-11，OPNET，其中OPNET是商业软件，价格昂贵，而NS2属于免费开源软件，被世界各国的网络研究者广泛使用，在国际学术上享有很高的声誉。本论文选择免费开源软件NS2。3.1 NS2仿真平台3.1.1 NS2简介NS2，即Network Simulator Version 2，是面向对象的、离散事件驱动的网络环境模拟器，主要用于解决网络研究方面的问题12。NS2提供了在无线或有线网络上的TCP、路由、多播等多种协议的模拟。NS2采用C+和Otcl两种语言共同工作13。一方面，具体的协议实现需要一种系统编程语言，它能有效地处理字节、报头和算法，其关键是整个协议的运行时间；另一方面，网络参数和仿真场景关心的是收发功率、传输速率、节点和拓扑生成等配置性工作，其模型建立的配置时间显得尤为重要。C+是一种编译语言，编译时由编译器一次性生成可执行代码，运行速度较快，但每改动一次都需要重新编译，比较费时；而Otcl是一种脚本解释语言，运行时由解释器逐行地解释，方便修改，无需重新编译，但运行效率低。NS2通过使用这两种语言的对象分裂模型来提高效率，C+运行速度快且不易改变，因而它适合于实现具体协议；Otcl运行较慢，但可以交互的进行改变，适合用来做仿真环境配置。NS2内核的层次结构如图3-1所示。图3-1 NS内核的类层次结构NS2仿真器用到了六种Tcl类，它们是：(1)Tcl类：封装TOtcl解释器实例，向外提供方法(methods)来访问解释器，获得Tcl实例的一个参考；过解释器激活otcl过程；返回结果；报告错误状态：存储和查找Tcl对象。(2) Instvar类：定义了一些方法和机制，在编译类结构对象的成员变量和对应的解释类结构对象的成员变量之间建立映射，使两类变量一致共享。(3)Tclclass类：把用户通过类Tclobject在解释器中建立的类结构映射至INS编译类结构，提供方法来实例化新的对象。(4) Tclobjeet类：是所有仿真对象的基类。封装了绑定、跟踪和对相关命令的调用机制。(5) Tclcommand类：提供一种机制使NS内核向解释器输出简单的命令。(6) EmbededTcl类：允许用户以编译代码或解释代码来扩展NS功能。3.1.2 NS2仿真环境的搭建VMware Workstation软件允许操作系统和应用程序在一台虚拟机内部运行。在 VMware Workstation 中，可以在一个窗口中运行一台虚拟机，这个虚拟机可以加载自己的操作系统。在Windows平台上按照虚拟机软件VMware Workstation 6.5.2后，在该虚拟机上新建客户机并安装了Ubuntu 9.10客户机操作系统，之后在其客户机操作系统上安装ns-2.34的网络仿真环境，最后还需要安装NSG214、gnuplot15等相关的仿真所需工具。3.2 AODV路由协议的实现与NS2仿真3.2.1 仿真性能指标及场景参数的确立参照IETF RFC250116 （移动专用网：路由协议性能问题和评估考虑）的规定，通常用端到端的分组投递率、端到端的平均延迟（delay）这两个指标用来对仿真结果进行分析，估算各协议的性能17：1)分组投递率分组投递率：即应用层目的端接收的分组数目与源端发送的分组数目之比。描述的是通过应用层观察到的丢失率，又反映了网络所支持的最大吞吐量。它是路由协议完整性和正确性的指标。分组投递率=接收分组数/发送分组数=（发送分组数-丢弃分组数）/发送分组数2)端到端延迟端到端时延主要包括路由查找时延、数据包在接口队列中的等待时延、传输时延及MAC层的重传时延，这个参数很好地表明了路由有效性。在网络通信中，尤其对于语音数据包的传输而言，端到端时延太大会严重影响通信质量。端到端延迟=接收到数据包的时间-发送数据包的时间本文使用端到端的分组投递率、端到端的延迟(delay) AODV协议的性能评价指标。分组投递率是评估路由协议的一个重要参数，它可以反映网络所能支持的最大吞吐量，从而在一定程度上刻画了协议的完整性和正确性。对于路由协议要求具有较小的端到端的延迟；具有较高的成功分