AODV路由协议的正确性研究 蔡雪莲

研究内容 路由协议是Ad hoc网络协议栈的重要组成部分，在无线环境下Ad hoc网络的移动特性对路由协议提出了更高的要求。本文在介绍现有AODV路由协议的基础上，重点证明该协议的正确性，并对路由协议的评估做了深入的研究。

内容安排 1 Ad hoc网络介绍 2 最优的路由算法 3 Ad hoc网络中的AODV路由协议 4 结束语

1 Ad hoc网络介绍（1/2） Ad hoc网络是一种自组织的无线多跳网。它不需要固定的基础设施作支撑。 网络中所有节点都是移动的，并且都能以任意方式动态地保持与其他节点的联系，网络节点可以随处移动，也可以随时开机和关机，这些都会使网络的拓扑结构随时发生变化。 两个无法直接进行通信的终端用户可以借助其他节点进行分组转发。每个移动节点兼备路由器和主机两种功能。

1 Ad hoc网络介绍（2/2） Ad hoc网络通过分组转发完成数据的交换，需要路由协议进行分组转发决策。无线信道变化的不规则性和节点的移动、加入、退出都会引起网络拓扑结构的动态变化。从而路由协议完成监控网络拓扑结构的变化、路由信息的交换、寻找目的节点、产生、维护并优化路由，保持网络数据传输的畅通。

2 最优的路由算法(1/2) 路由算法是网络层协议，路由算法既要试图使网络的通过量最大，又要试图使网络的平均分组时延最小。 路由算法通常很复杂，表现在： 1）路由算法要求要求子网中所有的节点互相协调，而不像链路层和高层那样仅涉及一对对等模块之间的协调； 2）路由算法必须处理链路和节点的故障，要求对业务进行重新定向，并对系统维持的数据库进行更新。 3)必须达到高的性能，当网络部分区域拥塞时，路由算法必须能够修正路由。 一个路由算法应当在高的业务负载的情况下，在保证相同的时延条件下，可以增加网络的通过量；在轻负荷和中等负荷的情况下，可以减少每一个分组的平均时延。

2 最优的路由算法(2/2) 理想的路由算法应具有如下的一些特点： 1)算法必须是正确的和完整的。 2)算法在计算上应简单。 3)算法应能适应通信量和网络拓扑的变化。 4)算法应是公平的。 5)算法应是最佳的。

3 Ad hoc网络中的AODV路由协议 3.1 Ad hoc网络路由协议概述 Ad hoc网络的路由协议大致可以分为先验式（Proactive）路由协议（如：DSDV）、反应式（Reactive）路由协议（如：DSR/ /TORA/ARP）以及混合式路由协议（如：AODV）。 先验式路由协议又称为表驱动路由协议（Table-driven），在这种路由协议中，每个节点维护一张包含到达其它节点的路由信息的路由表。当检测到网络拓扑结构发生变化时，节点在网络中发送更新消息，收到更新消息的节点将更新自己的路由表，以维护一致的、及时的、准确的路由信息，所以路由表可以准确地反映网络的拓扑结构。源节点一旦要发送报文，可以立即获得到达目的节点的路由。因此这种路由协议的时延较小，但是路由协议的开销较大。 反应式路由协议，又称为按需路由协议（On-Demand Routing），是一种当需要发送数据时才查找路由的路由算法。在这种路由协议中，节点不需要维护及时准确的路由信息，当向目的节点发送报文时，源节点才在网络中发起路由查找过程，找到相应的路由。与先验式路由协议相比，反应式路由协议的开销较小，但是数据报传送的时延较大。 在Ad hoc网络中单纯采用先验式或反应式路由协议都不能完全解决路由问题。由此可见，应用结合先验式和反应式路由协议优点的混合式路由协议是一种较好的折衷方案。下面对混合式的路由协议AODV（Ad hoc On demand Distance Vector Routing）进行具体的研究。

3.2 AODV协议 AODV是基于距离矢量算法的路由协议。AODV只在路由表中保持需要的路由，通常每一个目的节点保存一条路由，每条路由信息都有生存期，若超时则该项路由信息无效。AODV采用每个目的节点中保存的序列号来保持路由信息的有效性，所有的路由分组都保存序列号。 DSDV和DSR的结合 Route is set up only when requested Nodes not along active paths not 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 freedom

AODV Messages Route request (RREQ) Route reply (RREP Route error (RERR) Hello messages

Route Discovery

Route Maintenance Periodic Hello message to detect continued presence of neighbours When a link break is detected Node sends a RERR containing list of unreachable destinations due to link break Receiving nodes forwards RERR to precursors of unreachable destinations Before sending or forwarding RERR Update destination sequence number in routing table entry Invalidated entry

3.3 AODV的正确性证明 1）AODV的完整性和正确性 每个节点（交换机或路由器）中的路由表，都必须给出到所有可能的目的节点的下一跳怎样走，并且，所给出的走法应是正确的。这里，正确的含义是：沿着各节点（交换机或路由器）中路由表所指引的路由，分组一定能够最终到达目的节点（交换机或路由器）。并且，分组到达目的节点后不会再向其他节点（交换机或路由器）转发该分组。

完整性 它的路由表中通往目节点D的链路为 ，为 的邻节点，可知链路 一定存在，即 （ ） （ ） 所以 是节点 到目的节点D路由中记录的下一跳节点。是由 的任意性，我们得到在邻节不变的情况下，AODV通过记录到目的节点的下一跳节点的IP地址，在Ad hoc网络中可以形成一条完整的路由。

Loop-free

2）计算的复杂度 当一个节点希望和其他节点进行通信时，它首先会在自己的路由表中查找是否存储了到目的节点的有效路由，如果存在则采用该路由组包；当路由表中不存在到某一特点节点的路由或已知存储的路由无效，则该节点就会发起路由探索，这里节点只需遍历一遍路由表就可以得到所需的路由信息。在路由探索中，沿途收到RREQ广播的节点同样会遍历路由表，如果发现自己有到目的节点的有效路由则返回RREP，若没有则可以得到一条到源节点的最新路由信息，同时并转发RREP；沿途收到RREP的节点同样会得到一条到目的节点的最新路由信息。所以，在路由探索中AODV的计算繁杂度为 。 在本地连接管理中，每个节点都会定期地向邻节点发送Hello信息，由于Hello信息只在本地一跳范围内传递，不向外扩散，所以控制信息开销基本保持不变，不像DSDV那样以 增长。所以，由于AODV协议并不考虑链路的重量，而只关心双向链路的存在，故在Ad hoc网络中，所有单跳链路是等重的，这大大减少了节点运算的工作量，额外开销相对较少。

3）网络变化对路由协议的影响 路由表的维护： 路由表中存储的软信息用来确保路由信息的可靠性。通常路由表包含以下信息：目标IP地址、序列号、跳数（分组到达目的节点所需的跳数）、下一跳的IP地址、生存期、活跃的邻节点。 路由的维护： 如果链路出现中断,则发送一个大序列号的RREP返回给源节点，其中标识到目的节点的路由为无穷大，这样就可以清除路由表中有关该中断链路的所有信息项，与此同时AODV会触发新的路由探索。 本地连接管理： AODV还周期性地发送Hello分组探询链路是否发生变化。当路由的确发生变化时，AODV就将目的节点不可达的信息及时反馈给所有记录该条路由信息的节点。 通过以上3方面的策略，AODV能够迅速、准确地获知Ad hoc网络中路由的变化，确保了在节点移动的情况下，路由的完整性、有效性。所以说，AODV 具有很强的“稳健性”。

4）算法的公平性 在AODV路由协议中并没有规定对于某一种业务或特定用户采取不同的策略，任何业务到达后，AODV都按照相同的步骤完成路由探索过程。所以在AODV路由协议中，对于任何用户和业务都能平等地发现路由，维护路由。但这种公平性是绝对的，对于不同QoS要求的业务，AODV不能够及时调整路由策略，以达到网络传输的最佳。而这种无差别正是反映了AODV存在的不足，它没有考虑网络中的业务热点或传输瓶颈，所以基于AODV的改进有待于进一步研究。

5）算法的性能 对于一个路由协议来讲，网络中的路由性能仿真才是最有说服力的，因为路由协议的实现依靠下层协议的支撑，同时又为上层协议服务。路由协议的好坏完全依靠网络的整体规划，并体现在上层的数据传输中。事实上，对于路由协议进行评估要通过网络仿真来完成。 通常，衡量路由协议的参数有： 分组传输的成功率 链路的吞吐量 平均的端对端时延

①分组传输的成功率 从文献[1]的仿真图中可知，在TCP业务下当节点移动速度增加时，AOVD的丢包率上升，这主要是由于Hello分组的丢失，当Hello的发送周期增大时，AODV对路由协议的判断就非常迟缓。当周期减小，相对于网络的路由开销就增大。同样在网络中同时存在TCP和UDP时，随着节点的移动速率增加，AODV的丢包率也会上升，这都是由于通信链路的双向竞争。

②链路的吞吐量 从文献[1]的仿真图中可知，对于TCP业务来说，移动节点的速率增加都会引起吞吐量的下降。

③平均的端对端时延 从文献[1]的仿真图中可知，当节点的移动速率增加时，虽然链路的丢包率增加，但由于源端TCP业务的数据重发机制引起的多条路由效应，事实上提高了端对端的时延性能，即时延显著下降。

从仿真来看，由于Ad hoc网络的移动性使得AODV的性能有所下降，但总体来说，路由协议的总体性能很好，即使在节点的移动的情况下，网络分组传输的成功率、链路的吞吐量和平均的端对端时延都保持在较好的水平上。事实上，算法的网络性能随着网络参数的设计是不同的，受多方因素的影响，它们之间的关系还有待进一步研究。在具体规划网络结构时，应该对AODV参数作具体的设计，以确保网络性能的最优。

3.4 AODV性能小结 总之，AODV协议是一个比较好的路由协议，它能够实现路由的所用基本功能。同时AODV能够应对Ad hoc网络的节点移动的要求，在设定的路由延迟的情况下，表现出良好的性能。但由于未能考虑业务的QoS需求，在对传输质量要求较高的网络中，显得力不从心，尚待进一步完善。

4 结束语 通过对AODV路由协议的证明，我们可以得到衡量网络路由协议的标准。只有在理论分析和网络仿真的基础上对原有协议进行分析，才能改进原有的路由协议，不断提出有利于网络的性能提高的新的策略。