《AODV路由协议的正确性研究ppt课件》由会员分享，可在线阅读，更多相关《AODV路由协议的正确性研究ppt课件（25页珍藏版）》请在金锄头文库上搜索。
1、AODV路由协议的正确性研讨路由协议的正确性研讨蔡雪莲 研讨内容研讨内容路由协议是Ad hoc网络协议栈的重要组成部分，在无线环境下Ad hoc网络的挪动特性对路由协议提出了更高的要求。本文在引见现有AODV路由协议的根底上，重点证明该协议的正确性，并对路由协议的评价做了深化的研讨。 内容安排1Adhoc网络引见网络引见2最优的路由算法最优的路由算法3Adhoc网络中的网络中的AODV路由协议路由协议4终了语终了语1Adhoc网络引见网络引见1/2Ad hoc网络是一种自组织的无线多跳网。它不需求固定的根底设备作支撑。网络中一切节点都是挪动的，并且都能以恣意方式动态地坚持与其他节点的联络，网络
2、节点可以随处挪动，也可以随时开机和关机，这些都会使网络的拓扑构造随时发生变化。两个无法直接进展通讯的终端用户可以借助其他节点进展分组转发。每个挪动节点兼备路由器和主机两种功能。 1Adhoc网络引见网络引见2/2Ad hoc网络经过分组转发完成数据的交换，需求路由协议进展分组转发决策。无线信道变化的不规那么性和节点的挪动、参与、退出都会引起网络拓扑构造的动态变化。从而路由协议完成监控网络拓扑构造的变化、路由信息的交换、寻觅目的节点、产生、维护并优化路由，坚持网络数据传输的畅通。 2最优的路由算法最优的路由算法(1/2)路由算法是网络层协议，路由算法既要试图使网络的经过量最大，又要试图使网络的平
3、均分组时延最小。路由算法通常很复杂，表如今：1路由算法要求要求子网中一切的节点相互协调，而不像链路层和高层那样仅涉及一对对等模块之间的协调；2路由算法必需处置链路和节点的缺点，要求对业务进展重新定向，并对系统维持的数据库进展更新。3)必需到达高的性能，当网络部分区域拥塞时，路由算法必需可以修正路由。一个路由算法该当在高的业务负载的情况下，在保证一样的时延条件下，可以添加网络的经过量；在轻负荷和中等负荷的情况下，可以减少每一个分组的平均时延。 2最优的路由算法最优的路由算法(2/2)理想的路由算法应具有如下的一些特点：1)算法必需是正确的和完好的。 2)算法在计算上应简单。 3)算法应能顺应通讯
4、量和网络拓扑的变化。4)算法应是公平的。 5)算法应是最正确的。 3Adhoc网络中的网络中的AODV路由协议路由协议3.1Adhoc网网络路由路由协议概述概述Adhoc网网络的的路路由由协议大大致致可可以以分分为先先验式式Proactive路路由由协议如如：DSDV、反反响响式式Reactive路路由由协议如如：DSR/TORA/ARP以及混合式路由以及混合式路由协议如：如：AODV。先先验式式路路由由协议又又称称为表表驱动路路由由协议Table-driven，在在这种种路路由由协议中中，每每个个节点点维护一一张包包含含到到达达其其它它节点点的的路路由由信信息息的的路路由由表表。当当检测到到
5、网网络拓拓扑扑构构造造发生生变化化时，节点点在在网网络中中发送送更更新新音音讯，收收到到更更新新音音讯的的节点点将将更更新新本本人人的的路路由由表表，以以维护一一致致的的、及及时的的、准准确确的的路路由由信信息息，所所以以路路由由表表可可以以准准确确地地反反映映网网络的的拓拓扑扑构构造造。源源节点点一一旦旦要要发送送报文文，可可以以立立刻刻获得得到到达达目目的的节点的路由。因此点的路由。因此这种路由种路由协议的的时延延较小，但是路由小，但是路由协议的开的开销较大。大。反反响响式式路路由由协议，又又称称为按按需需路路由由协议On-DemandRouting，是是一一种种当当需需求求发送送数数据据
6、时才才查找找路路由由的的路路由由算算法法。在在这种种路路由由协议中中，节点点不不需需求求维护及及时准准确确的的路路由由信信息息，当当向向目目的的节点点发送送报文文时，源源节点点才才在在网网络中中发起起路路由由查找找过程程，找找到到相相应的的路路由由。与与先先验式式路路由由协议相相比比，反反响响式式路路由由协议的开的开销较小，但是数据小，但是数据报传送的送的时延延较大。大。在在Adhoc网网络中中单纯采采用用先先验式式或或反反响响式式路路由由协议都都不不能能完完全全处理理路路由由问题。由由此此可可见，运运用用结合合先先验式式和和反反响响式式路路由由协议优点点的的混混合合式式路路由由协议是是一一种
7、种较好好的的折折衷衷方方案案。下下面面对混混合合式式的的路路由由协议AODVAd hoc OndemandDistanceVectorRouting进展展详细的研的研讨。3.2AODV协议协议AODV是基于间隔矢量算法的路由协议。AODV只在路由表中坚持需求的路由，通常每一个目的节点保管一条路由，每条路由信息都有生存期，假设超时那么该项路由信息无效。AODV采用每个目的节点中保管的序列号来坚持路由信息的有效性，一切的路由分组都保管序列号。 DSDV和DSR的结合 Route is set up only when requested Nodes not along active paths n
8、ot required to maintain route information Avoids the Bellman-Ford “counting to infinity problem Link breakages notification only to affected nodes Multicasting Key Feature: Use of Destination sequence Number Loop freedomAODV MessagesRoute request (RREQ)Route reply (RREPRoute error (RERR)Hello messag
9、esRoute DiscoveryRoute MaintenancePeriodic Hello message to detect continued presence of neighboursWhen a link break is detectedNode sends a RERR containing list of unreachable destinations due to link breakReceiving nodes forwards RERR to precursors of unreachable destinationsBefore sending or forw
10、arding RERRUpdate destination sequence number in routing table entryInvalidated entry3.3AODV的正确性证明的正确性证明1AODV的完好性和正确性每个节点交换机或路由器中的路由表，都必需给出到一切能够的目的节点的下一跳怎样走，并且，所给出的走法应是正确的。这里，正确的含义是：沿着各节点交换机或路由器中路由表所指引的路由，分组一定可以最终到达目的节点交换机或路由器。并且，分组到达目的节点后不会再向其他节点交换机或路由器转发该分组。完好性它的路由表中通往目节点D的链路为 ，为 的邻节点，可知链路 一定存在，即
11、所以 是节点 到目的节点D路由中记录的下一跳节点。是由 的恣意性，我们得到在邻节不变的情况下，AODV经过记录到目的节点的下一跳节点的IP地址，在Ad hoc网络中可以构成一条完好的路由。 Loop-free2计算的复杂度当一个节点希望和其他节点进展通讯时，它首先会在本人的路由表中查找能否存储了到目的节点的有效路由，假设存在那么采用该路由组包；当路由表中不存在到某一特点节点的路由或知存储的路由无效，那么该节点就会发起路由探求，这里节点只需遍历一遍路由表就可以得到所需的路由信息。在路由探求中，沿途收到RREQ广播的节点同样会遍历路由表，假设发现本人有到目的节点的有效路由那么前往RREP，假设没有
12、那么可以得到一条到源节点的最新路由信息，同时并转发RREP；沿途收到RREP的节点同样会得到一条到目的节点的最新路由信息。所以，在路由探求中AODV的计算繁杂度为 。在本地衔接纳理中，每个节点都会定期地向邻节点发送Hello信息，由于Hello信息只在本地一跳范围内传送，不向外分散，所以控制信息开销根本坚持不变，不像DSDV那样以 增长。所以，由于AODV协议并不思索链路的分量，而只关怀双向链路的存在，故在Ad hoc网络中，一切单跳链路是等重的，这大大减少了节点运算的任务量，额外开销相对较少。3网络变化对路由协议的影响 路由表的维护：路由表中存储的软信息用来确保路由信息的可靠性。通常路由表包
13、含以下信息：目的IP地址、序列号、跳数分组到达目的节点所需的跳数、下一跳的IP地址、生存期、活泼的邻节点。 路由的维护：假设链路出现中断,那么发送一个大序列号的RREP前往给源节点，其中标识到目的节点的路由为无穷大，这样就可以去除路由表中有关该中断链路的一切信息项，与此同时AODV会触发新的路由探求。 本地衔接纳理：AODV还周期性地发送Hello分组探询链路能否发生变化。当路由确实发生变化时，AODV就将目的节点不可达的信息及时反响给一切记录该条路由信息的节点。 经过以上3方面的战略，AODV可以迅速、准确地获知Ad hoc网络中路由的变化，确保了在节点挪动的情况下，路由的完好性、有效性。所
14、以说，AODV 具有很强的“稳健性。 4算法的公平性 在AODV路由协议中并没有规定对于某一种业务或特定用户采取不同的战略，任何业务到达后，AODV都按照一样的步骤完成路由探求过程。所以在AODV路由协议中，对于任何用户和业务都能平等地发现路由，维护路由。但这种公平性是绝对的，对于不同QoS要求的业务，AODV不可以及时调整路由战略，以到达网络传输的最正确。而这种无差别正是反映了AODV存在的缺乏，它没有思索网络中的业务热点或传输瓶颈，所以基于AODV的改良有待于进一步研讨。 5算法的性能 对于一个路由协议来讲，网络中的路由性能仿真才是最有压服力的，由于路由协议的实现依托下层协议的支撑，同时又
15、为上层协议效力。路由协议的好坏完全依托网络的整体规划，并表达在上层的数据传输中。现实上，对于路由协议进展评价要经过网络仿真来完成。通常，衡量路由协议的参数有：分组传输的胜利率 链路的吞吐量 平均的端对端时延 分组传输的胜利率 从文献1的仿真图中可知，在TCP业务下当节点挪动速度添加时，AOVD的丢包率上升，这主要是由于Hello分组的丧失，当Hello的发送周期增大时，AODV对路由协议的判别就非常缓慢。当周期减小，相对于网络的路由开销就增大。同样在网络中同时存在TCP和UDP时，随着节点的挪动速率添加，AODV的丢包率也会上升，这都是由于通讯链路的双向竞争。链路的吞吐量 从文献1的仿真图中可
16、知，对于TCP业务来说，挪动节点的速率添加都会引起吞吐量的下降。平均的端对端时延 从文献1的仿真图中可知，当节点的挪动速率添加时，虽然链路的丢包率添加，但由于源端TCP业务的数据重发机制引起的多条路由效应，现实上提高了端对端的时延性能，即时延显著下降。 从仿真来看，由于Ad hoc网络的挪动性使得AODV的性能有所下降，但总体来说，路由协议的总体性能很好，即使在节点的挪动的情况下，网络分组传输的胜利率、链路的吞吐量和平均的端对端时延都坚持在较好的程度上。现实上，算法的网络性能随着网络参数的设计是不同的，受多方要素的影响，它们之间的关系还有待进一步研讨。在详细规划网络构造时，应该对AODV参数作详细的设计，以确保网络性能的最优。 3.4AODV性能小结性能小结总之，AODV协议是一个比较好的路由协议，它可以实现路由的所用根本功能。同时AODV可以应对Ad hoc网络的节点挪动的要求，在设定的路由延迟的情况下，表现出良好的性能。但由于未能思索业务的QoS需求，在对传输质量要求较高的网络中，显得力不从心，尚待进一步完善。4终了语终了语经过对AODV路由协议的证明，我们可以得到衡量网络路由协议的规范。只需在实际分析和网络仿真的根底上对原有协议进展分析，才干改良原有的路由协议，不断提出有利于网络的性能提高的新的战略。
