AODV路由协议路由修复研究和改进

摘 要： Ad Hoc网络具备拓扑的动态性，该特性使得一般路由协议无法正常工作，且网络节点移动变化性，也会提升路由断裂的发生率。AODV路由协议作为Ad Hoc网络目前使用最为频繁的一种路由协议，其重要性和高效率性不言而喻。主要对AODV路由协议的修复研究与改进进行分析和探讨，从AODV协议的工作原理、修复研究以及改进方法等几个方面进行了阐述。

关键词： Ad Hoc网络； AODV路由协议； 修复； 改进

中图分类号： TN915.04?34 文献标识码： A 文章编号： 1004?373X（2014）05?0055?03

0 引 言

Ad Hoc网络作为一种自组织网络，其具备节点可在主机与路由之间相互切换以及可移动等性能，且其具备的高度动态拓扑结构也对应用的路由协议提出了更多的要求。Ad Hoc网络和目前最常用的蜂窝技术不同，其与传统蜂窝技术最主要的区别在于它自身结构中的移动节点之间的相互通信和连通是建立在没有任何基础网络设施或者路由器的条件下开展或运行传递的，且该网络系统支持动态数据流控制和动态配置，运行中使用的所有路由协议都具备分布式特性。这就是说Ad Hoc网络的控制和自组性并不会过度依靠某些相对较为重要的节点，所有结构中的节点在功能上和网络组成中都是平等的，且任何一节点因故障或其他原因离开网络或加入网络都是被允许的。

Ad Hoc网络技术作为最近几年研究活动最为频繁的领域之一，其最常使用的路由协议AODV协议也成为目前研究的方向之一。下面通过对AODV路由协议的工作原理和存在的问题进行详细的描述，重点介绍了关于该协议的修复和改进，现阐述如下。

1 AODV路由协议及其原理

1.1 AODV路由协议

Ad Hoc网络是一种拥有动态化特性高的网络拓扑结构，也具备单向信道的特征，同时也有无线移动终端局限性和有限无线传输带宽等特征，Ad Hoc网络的上述特点对路由协议提出了很高的要求，一般路由协议难以在该网络中工作。

自组按需请求型距离向量协议简称AODV协议，该协议是建立在DSDV协议的条件上，通过借鉴DSR中相关路由协议机制，对上述两种协议进行改进后产生的一种协议，也就是说AODV协议糅合了DSDV和DSR两者的优点，如DSDV协议中设定的定期广播、序列号以及逐跳路由，DSR中设计的路由维护机制以及按需路由发现。这在一定程度使得AODV路由协议拥有了按需路由协议所具备的特性及功能。与此同时，在Ad Hoc网络拓扑结构运行的过程中发生变化或出现改变时，它会快速收敛，断路后也可凭借自身功能进行自我修复，保证链路畅通，使得节点能通过建立正向路由到达目的节点。在运行的过程中，还具备消耗的储存资源少，计算量小，网络带宽占用资源少等优点。

Ad Hoc网络在构建移动节点以及对移动节点进行维护时，需要借助AODV路由协议的计算功能，对网络结构中各移动节点之间多跳路由、自启动以及动态变化进行记录和计算。操作AODV路由协议过程中具有一定的开环性，而在Ad Hoc网络结构中拓扑出现改变时，即结构中节点开始在网络内移动，可以快速收敛，有效地避免了Bellman?Ford“无穷计算”产生问题的影响。若是链路出现中断，该协议会对相关受到累及的节点给予链路中断的信息通知，这就会使累及到的节点不会因路由中断而受到影响。

1.2 基本原理

AODV协议中，若结构中某个源节点在通向某个节点时会建立一个路径，此时就会使得一个路径发现程序被发起，这一时刻广播路径会自主向RREQ发出请求，并安排一个能与之处于对方无线电覆盖范畴内且相邻的节点，而该范围临近节点会依据请求转发RREQ，一直到源节点通过建立路由达到目的节点或者达到某个中间节点，同时这个中间节点必须具备能够达到目的节点的新的路径。而在RREQ被上述相邻节点转发的过程中，中间节点在与之相对性的路由表中会对第一个拷贝RREQ且转发给其他节点的相邻节点进行记录，这种记录同时也搭建了一条反向路径。当RREQ达到中间节点或者目的节点后，那么中间节点就会与目的节点借助反向路径单播一个RREP（路径响应分组），再转发给路径表上记录的相邻节点。在上述源节点移动并到目的节点的整个过程中，路径上的节点会依据路径表上的记录搭建一条源节点正确通向目的节点的路径。路由的建立如图1所示。

路由表项构建完成后，路由中任何一个节点都必须达到依据路由维持和管理路由表中各自设定的目标，即任何一个路由表项都在路由表中保持或拥有一个与之对应的目的地址，这是为了完成逐条转发而设定的。同样，在对路由表维护的时间段，与节点相对应项会被从路径表中被抹除掉，前提是路由没有被使用。这时，节点会对下一跳节点进行监视，若是在活动路由的过程中发生了链路断开，这时就会对其他节点发出相关的修复消息对路由链路断开处进行修复。

2 Ad Hoc路由修复与改进

Ad Hoc网络在运行的过程中，节点的拓扑结构在一定程度上具备很强的可移动性，也就是说路由节点会依据这种移动特性在网络中有目的移动，同时无线自组网络中构建各个节点也应节点的移动而成为中继路由器的替补，而在这一阶段链路就会因节点早网络中的移动而断路。因此，对AODV路由协议运行时因节点移动而导致路由断路进行修复对于保证通信的正常进行就显得非常重要。目前，对于断链问题修复主要有三种处理方法：

（1） 断路被发现后，广播RERREP报文会从路由中断链处的下游节点处主动发起，而节点在收到该报文后就会通过已经搭建好的正确通向目的节点的路径实现节点转移，一旦断链上游节点在收到该报文后，上游节点也会搭建正确通向目的节点路径，这样就完成了路由的修复。

（2） 断链时充分发挥本地修复功能，并通过上游节点实现对RREQ报文的传播控制，在控制范围内完成本地修复。

（3） 将源修复与本地修复相结合，依据设计者对断链做出的实际判断来选择使用何种方式进行修复。

2.1 由下游节点发广播报文

当在活动路由进行的过程中，某条中间链路正在使用，因故障原因或者其他出现了断链情况，这时出现断链位置的下游节点会对路由表进行检查，会明确位于自己上游的节点属于哪一条路由，并依据该节点到达的目的节点发起一个RERRER广播消息。任何一个节点在收到该广播消息后，都会对自身路由表进行检查，查看是否存在通往该目的节点的正确路径及可用路由，若是并不存在与之相关的路由表项，则会创建并转发；若是存在与之相关表项，而目的状态无法到达，则会根据广播消息对路由表进行更新；若存在能到达相应目标的节点，同时路由信息处于可以占用状态，那么该广播消息会不被理会或丢弃。然而，在广播消息通过链路到达断链位置的上游节点处时，就能立即建立正向的路由，完成修复。

然而，该修复方法也存在一定的问题。在广播报文被下游节点发起的过程中，路由表除了会对路由中某一下跳节点进行保存或记录时，还对上一跳点相关信息进行保存，这与AODV协议中到达目的节点的思想存在一定的冲突性。同时，下游节点发起对断链的修复过程中，它们都会对上一节点信息进行缓存，下游节点是不可预见的；因此，下游节点发起对断链处路由的修复是没有区别性的，也就是即使不存在数据传输，不存在该条路由，修复还是会被发起，这使得广播报文的传播量大大增加，加大了无线信道的负荷。

2.2 本地修复与源修复

AODV在运行的过程中，若是发现断路，传统的修复方法为源节点修复法，这就是说RERR会被传递到源节点处，并通知其路由出现断链时，而这时源节点会重新对路由进行发现，进而完成修复。这种修复方法比较可靠，但修复延时较长，因此对AODV提出了本地修复法：由于节点在网络中的移动而导致断链，而导致断链的节点极有可能就在断链处的附近或周边，借助这种方式对断链上游位置节点的TTL（生存时间）相对较小的RREQ广播报文来对断链的路由进行修复。然而，本地修复法受到路由使用效率的限制，特别适用于网络运行时，节点不会出现范围移动的可能情形中。使用OPNET软件对上述两种修复方法的仿真结果图如图2，图3所示。

本地小范围修复同样存在问题，若是位于断链处上游位置的相关节点周边临近节点较少，那么寻找下两跳节点而发起修复必将失败，这时上游节点也不可能寻到合适的总计节点，那么在此发起本地小范围修复，也必然会是失败。也就是说，由同样一个节点引发的两次寻找修复，都会因为周边临近节点不足且没有合适的中继节点而出现修复失败的问题，这样会转而寻求源节点修复，而在整个过程中会使得端到端延时、路由开销以及丢包率增加。

2.3 路由断链修复方法的改进

对上面描述进行分析，可以知道不同的修复方法其优势不相同，所面临的缺陷也具有差异性，因此，在断链发生时最好配合使用各种修复方法，这便于提升修复性能。目前，对上述修复方法的改进主要如下：

（1） 当某条路由出现断链且被某中间节点发现时，在断链上游节点发现后，可以发出具有限制跳数作用的Local RREQ，这样可以将路由重建或者断链修复的整个过程限制在因拓扑改变节点移动周边范围。若是在一段时间未能获取RREP，可以通过上游节点向上发出Route Notfication，并对上一节点进行要求，发起RREQ；若是整个向上过程直至源节点和目的节点的中点都未能获取RREP或路由重建不成功时，应该停止继续在该节点继续发送RREQ，而是通知源节点重新建立一条通向目的节点的路径，实现路由的重建。

（2） 链路中断后，首先对链路中断位置的上一处节点位于的位置进行判断，在根据其特点采取相应的修复方法。若是该节点位置距离源节点相对较近，则选择源节点修复；若是距离目的节点相对较近，则选择本地修复。判断方法：当某条活动路由出现断链的情况后，假定路由表中中断位置的上一个节点有效的反向路由与之相对应的跳数为hopl，而在程序录入中的代码“DestinationIP address”有效的路由表项与之相对应的跳数为hopl2，若是（hopl+hopl2）/2≥hopl，这表明断链路由位置的上一节点到目的节点的距离远于到源节点的距离，这时就应采取源节点修复，这便于源节点重建新的到达目的节点的路径，有效地避免了因重建路由而产生的引入时延，且相对本地修复法节省了因需要重建路由而开销的费用。若是hopl>（hopl+hopl2）/2，那么则相反，应选取本地修复，这有助于减少时延。

3 结 语

Ad Hoc网络是一种具备无线移动、自组织的网络，该网络结构并不需要在某种特定的结构环境下工作，其工作环境是可多变化的。因此，Ad Hoc网络非常适用于一些特殊场合或军事场合。在缺乏相关基础网络设施构建网络环境的条件下，Ad Hoc网络通过凭借自身具备的特性及功能完成快速组网，而且构建组网结构中任何一个节点都具备可移动的特性，这就是说每个节点除了可以作为主机外，还具备路由器的功能，而这种优秀特性也使该网络具备非常广的应用前景。而AODV路由协议作为Ad Hoc网络最常使用的路由协议，其重要性不言而喻，因此，开展相关AODV路由协议的修复研究和改进是非常有意义的，这对于提升路由协议的高效工作有着极为明显的促进作用。

参考文献

[1] 胡曦，李喆，刘军.移动Ad Hoc网络中基于链路稳定性预测的按需路由协议[J].电子与信息学报，2010（2）：284?289.

[2] 叶亮，沙学军，徐玉.Ad Hoc网络路由抖动与路由维护[J].吉林大学学报：工学版，2010（5）：1397?1403.

[3] 王琦进，侯整风.一种节点低能量避免的AODV改进协议[J].合肥工业大学学报：自然科学版，2013（4）：431?434.

[4] 周杰.基于AODV的Ad Hoc网络多路径路由协议[J].长春工业大学学报：自然科学版，2012（4）：451?455.

[5] 谢佳，徐山峰.AODV、AOMDV和AODV?UU路由协议性能仿真与分析[J].中国电子科学研究院学报，2011（6）：592?594.

[6] 王莎莎，朱国晖，王鑫.Ad Hoc网络负载均衡路由协议研究[J].现代电子技术，2013，36（3）：40?42.

[7] 曾志宏，汤碧玉，杨琦.TinyOS在CC2530下的移植及AODV路由协议的实现[J].现代电子技术，2012，35（9）：41?44.

[8] 胡海春，陈佳品，李振波.基于AODV且考虑延时能量节省的路由协议[J].现代电子技术，2012，35（3）：81?84.