基于闲时逆寻和路由学习机制的优化AODV路由协议

杜青松，朱江，张尔扬

（1. 国防科技大学 电子科学与工程学院，湖南 长沙 410073；

2. 湖南大学 计算机与通信学院，湖南 长沙 410082）

1 引言

按需距离矢量路由协议 AODV是移动自组织网络（MANET）中一种经典的反应式路由协议，它专门针对MANET网络自身特点而设计，具有算法简单易实现、适度的控制开销和带宽开销、具有良好的扩展性等优点，已经成为MANET网络中一种标准化的路由协议[1]。

但在不同的网络场景下，AODV路由协议在性能和效率方面存在着一定的局限和不足。

1) 在AODV协议中，一条已建立的路由在超过一段时间没有进行数据传输的情况下会被删除。在网络拓扑变化相对较缓慢的MANET网络中，节点间的路由相对较稳定，然而根据AODV协议，这些稳定的路由会由于超时而被删除，导致额外的重路由开销，增加了网络负担。

2) 在较大规模的MANET网络中，处于网络边缘的节点之间跳数较多，当网络一侧的边缘节点需要建立到网络另一侧的边缘节点的路由时，最坏情况下路由的建立过程将贯穿整个网络，这将导致较大的路由建立延时，对于实时性要求较高的业务数据传输是不利的。

3) AODV协议的路由发现过程只能建立一条源节点到目的节点的最短距离路由，没有冗余路由信息，一旦由于网络拓扑变化等原因导致路由故障，将不得不由上游节点进行本地修复或由源节点重新发起路由发现过程。如果网络拓扑变化较快，则整个网络中用于重路由和本地修复的开销将大大增加，导致网络性能的急剧下降。

不少研究文献对AODV协议进行了改进，以提高它的性能。文献[2～6]在 AODV协议的基础上进行扩展，在一次路由发现的过程中建立多条到目的节点的路由，通信时使用其中一条路由，其余路由作为备份。这种多径路由的方式提高了数据传输的可靠性，但路由建立的时延较大，路由发现和维护过程比较复杂。AODV-PA协议[7]利用DSR协议[8]的路径收集思想，一次路由发现过程能够建立很多路由，提高了路由发现的效率，但协议开销大，路由请求响应延迟大。文献[9]根据节点的速度和方向信息计算节点之间的可靠通信距离，通过选择可靠距离大的节点建立路由的方式来提高 AODV协议对拓扑结构变化较快的网络的适应能力，但要求每个节点配置GPS设备。ELRAODV[10]通过在节点间交互增强的Hello分组和NHello分组中，能够快速感知路由中的故障点，并通过一种改进的本地修复机制提高故障路由的修复率。SARP[11]提出一种自学习机制，节点在转发路由请求和响应分组时从分组头中提取路由信息，从而使转发节点能够建立到源节点和目的节点的路由，但学习的节点仅限于最终建立的主路由上的节点。

本文在节点不增加硬件设备和不过多增加节点处理负担的前提下，对基础AODV路由协议进行扩展，利用网络中很多节点经常处于空闲状态的特点，提出一种节点在空闲时间进行反向路由搜索机制（本文简称闲时逆寻机制），该机制能够在网络中建立局部路由、刷新现成路由和更新故障路由；参照文献[11]中节点学习路由的思想，利用无线信道广播传输的特性，提出一种邻居节点路由监听学习机制（本文简称为路由学习机制），在不增加路由开销的前提下为主路由建立冗余的路由信息，能够加快新路由的发现和故障路由的快速修复。结合这2种机制而提出的O-AODV（optimized AODV）路由协议能够在网络规模扩大或网络拓扑快速变化的情况下提升基础 AODV路由协议的性能和路由效率，减少重路由的次数，降低网络中无谓的路由开销和控制开销。

2 O-AODV的基本思想

2.1 闲时逆寻机制的基本思想

定义 1 节点空闲状态：当一个节点在某个时间段内除了与邻居节点交换Hello信息分组外，不进行任何其他信息分组（包括数据分组、路由信息分组RREQ和RREP等）的发送、接收和转发，则定义该节点在此时间段内处于空闲状态。

定义 2 节点空闲时间：一个节点连续处于空闲状态的时间长度称为该节点的一段空闲时间，记作τIdle。在整个MANET网络维持期间，同一节点可能会有很多段空闲时间，尤其是在通信量较少的网络中。

在 O-AODV路由协议中定义一个节点空闲时间的阈值Tth，当某节点L检测到自己的空闲时间τIdle＞Tth，就尝试在网络中广播一个反向RREQ探测分组（R-RREQ），反向寻找以L为目的节点的源节点；如果R-RREQ在广播过程中，正好碰到某个节点S要建立到节点L的路由，则节点S广播的RREQ和节点L广播的R-RREQ会在某个中间节点I相遇，由于此时节点I已经有I→S的反向路由和I→L的正向路由，I只要分别向S和L发送RREP报文就可以建立 S→L的路由，这样就加快了路由发现的过程，这种在节点空闲时反向寻找源节点的过程就是本文提出的闲时逆寻机制。工作原理如图1所示。

不过，上面描述的过程不是闲时逆寻机制的主要用途，因为并不是空闲节点L每次进行反向探测时都恰好能碰到有别的节点正在建立到L的路由。闲时逆寻机制的主要作用如下。

1) 空闲节点 L通过闲时逆寻操作，可以让 L附近的其他节点建立到L的局部路由，一旦网络中有节点要与L通信，这些局部路由就可以帮助源节点快速建立到L的路由，从而充分利用网络资源。

图1 闲时逆寻机制工作原理示例

2) 利用空闲时间刷新已经存在的路由，使这些已经存在的路由不会因为超时而被删除。如图2所示，节点f到节点q已经建立了路由f→g→m→q，该路由完成数据传输后就空闲下来，在该路由将要失效前，节点q在网络上广播一个R-RREQ分组，该路由上的节点m、g和f收到来自q的R-RREQ后就刷新自己路由表中到节点q的路由，使得路由继续保持，以便下次使用。

3) 更新网络中由于拓扑结构变化而断裂的路由，加快路由的修复。如图2所示，节点S建立了到节点d的路由S→c→e→h→d，但由于节点d在通信过程中移出了h的通信范围使得h到d的链路断开，因此断开一段时间后d进入空闲状态，于是d在网络上广播一个R-RREQ分组，此时节点e收到此R-RREQ，就可以重建S到d的路由。

图2 闲时逆寻机制进行路由维护的原理示例

定义 3 信道空闲：如果一个节点的邻居中有节点正在发送或转发除Hello信息分组外的其他信息分组，则称该节点的信道不空闲；反之则称为信道空闲。

由于网络可能会有很多节点同时处于空闲状态，如果这些空闲节点同时进行反向探测，将会使网络负载急剧上升，网络中传输的数据分组发生碰撞的概率大大增加，反而使得网络的性能下降，因此要采取措施限制同一时刻网络进行反向探测的空闲节点数。本文采用信道侦听+随机退避机制来完成这种限制，具体做法是：源空闲节点在发送R-RREQ前先侦听信道，如果信道不空闲，就随机退避一段时间后再侦听信道，直到信道空闲才开始广播自己的R-RREQ；中间节点在转发R-RREQ前先侦听信道，如果信道不空闲，就停止转发该R-RREQ，而只是向源空闲节点单播一个RREP分组，建立局部的双向路由，从而限制R-RREQ在全网的洪泛。

2.2 路由学习的基本思想

由于无线信道具有广播特性，因此MANET网络中的任何一个节点向外发送任何消息时，它的邻居节点都可监听到此消息。如果将节点的工作模式设置为杂收模式，该节点就可以接收所有监听到的消息并进行处理。

在AODV中，每一个数据分组和路由应答分组（RREP）中都包含有到源节点或目的节点的路由信息，如果所有节点都工作于杂收模式，则每个节点可以通过监听邻居节点发送或转发的数据分组或RREP分组，从而可以获取网络中的路由信息，这一过程称为路由学习。

如图3所示，网络中存在2条路由，一条是正在进行数据传输的路由L→n→j→g，另一条是正在从目的节点l向源目的发送RREP分组的即将建立的路由S→c→e→h→l。节点f可以监听到节点c转发的RREP分组，因此能从RREP分组头中提取到源节点S和目的节点l的路由信息，从而可以建立到 S的路由 f→c→S和到 l的路由 f→c→e→h→l。同理，节点I可以监听到j转发的数据分组，根据从数据分组头中提取的路由信息，分别可以建立节点 I到节点 g和到节点 L的路由：I→j→g和 I→j→k→L。但这些学习到的路由信息有些是不完整的，在3.3节中进行了分析，并提出了解决方案，从而使网络中增加了很多冗余的备份路由信息。

图3 路由学习机制工作原理示例

通过路由学习机制获得的路由并不一定是最短路由，但它用很少的节点处理开销就为网络中的主路由增加了很多有用的冗余路径，给故障路由的快速修复和新路由的发现提供了可能。

3 O-AODV中的算法描述

3.1 路由发现与维护算法

O-AODV的路由发现过程与AODV相似，当源节点S需要到某个目的节点D的路由而其路由表中又没有时，它就启动路由发现过程[1]。

O-AODV对AODV的拓展在于，当中间节点I有到目的节点D的路由时，I要同时进行如下2项操作。

1) I向S单播RREP以建立S→I的正向路由（I→S的反向路由在I收到RREQ报文时已建立）。

2) I向D单播RREP以刷新或建立I→D的路由，以确保该路由是有效的（因为 I→D的路由可能已过时，或者有可能是单向路由）。如果I→D的路由发生故障，则由I到D中检测到故障的上游节点启动本地修复。

O-AODV的路由维护过程与AODV相同[1]，只不过 O-AODV在进行路由本地修复时可以使用闲时逆寻机制和路由学习机制得到的局部路由进行快速修复。

3.2 闲时逆寻规则

以下规则中假设广播R-RREQ分组的源空闲节点为L。

规则 1 网络中的所有节点都维护一个记录本节点空闲时间的变量τIdle，该变量初始值为零。如果节点发送或转发过除Hello信息分组外的任何其他分组，则将τIdle清零。

规则2 当节点检测到自己的τIdle大于空闲时间的阈值，即有τIdle＞Tth，则先侦听信道，如果信道空闲，则向网络上广播一个R-RREQ分组；否则随机退避一段时间后再侦听信道，寻机广播R-RREQ。

R-RREQ分组的格式与RREQ的格式相同[1]，只不过其类型值为5，即Type=5。源空闲节点L在广播R-RREQ分组前，R-RREQ分组中有关域的设置如图4所示。

图4 R-RREQ分组的域值设置

规则3 收到R-RREQ分组的节点I做如下处理。

1) 根据 RREQ ID判断自己是否收到过该R-RREQ，如果收到过则简单丢弃，结束处理；否则转处理2)。

2) 根据R-RREQ分组中的Destination IP检查自己的路由表中是否有到节点L的路由，如有，转处理3)；否则转处理4)。

3) 设节点I收到的R-RREQ中节点L的序列号为SLNew，跳数HopCount为 HLNew；节点I路由表中维护的节点L的序列号为SLOld，到节点L的跳数为 HLOld。如果 SLNew＞SLOld；或者 SLNew＝SLOld，但HLNew+1＜HLOld，则使用 SLNew和 HLNew+1更新到节点L的路由，然后转处理5)；否则丢弃该R-RREQ，结束处理。

4) 在路由表中添加一个到节点L的路由表项，该表项中L的序列号为SLNew，跳数为HLNew+1，然后转处理5)。

5) 将 R-RREQ分组中的 HopCount设为HLNew+1，然后按规则4进行处理（转发或结束转发）。

规则4 节点I在转发处理完的R-RREQ分组前先侦听信道，当信道空闲时广播该R-RREQ分组，否则结束转发该R-RREQ分组，往节点L单播一个RREP分组，从而建立I到L的局部路由。

收到过该R-RREQ分组的节点越多，网络中到节点L的局部路由就越多，当网络中有节点要建立到L的路由时，这些局部路由就能发挥作用，从而提高路由发现的效率，减少路由的时延。

另外，利用规则3和规则4，能够刷新网络中已经存在的路由，也可以更新网络中由于故障断裂的路由。

3.3 路由学习规则

将网络中节点的工作模式设置为杂收模式，节点就具有了路由学习的功能。

规则 5 节点只对监听到的有效监听分组进行处理。有效监听分组包括RREP分组、数据分组以及下面定义的HREP分组。

节点从监听到的RREP分组中可以提取出源节点IP和目的节点IP、目的节点序列号及到目的节点的跳数，但不能提取源节点序列号及到源节点的跳数；从数据分组的头信息中可以提取源节点IP、源节点序列号和目的节点IP、目的节点序列号，但不能提取到源节点的跳数和到目的节点的跳数。为了获取这些跳数信息，特定义了规则6和规则7。

规则 6 节点在信道空闲时向有效监听分组的来源节点单播一个查询分组 HREQ（HopCount request），HREQ只在2个相邻节点间传输，不会扩散到网络中去，从而将网络开销限制在很小的范围内。HREQ分组的格式如下：

Source IP：发送查询分组的节点的IP地址；

Source SN：发送查询分组的节点的序列号；

Dest IP：产生有效监听分组的节点的IP地址；

Node 1 IP：第一个待查询节点的IP地址；

Node N IP：第N个待查询节点的IP地址。

规则7 产生有效监听分组的节点收到HREQ分组后，根据HREQ分组中的待查询节点信息，从自己的路由表获取这些节点的序列号和跳数信息，填充到HREP分组中，然后将HREP分组单播给发送查询分组的节点。HREP分组的格式如下：

Source IP：产生有效监听分组的节点的IP地址；

Source SN：产生有效监听分组的节点的序列号；

Dest IP：发送查询分组的节点的IP地址；

Node 1 IP：第一个要查询节点的IP地址；

Node 1 SN：第一个要查询节点的序列号；

Node 1 HC：本节点到第一个要查询节点的跳数；

…

进行路由学习的节点通过与有效监听分组的来源节点之间交互HREQ和HREP，就可以获取通过监听得到的完整路由信息，从而增加了网络中路由的冗余信息。

3.4 路由快速修复规则

通过闲时逆寻和路由学习，网络中会存在很多冗余的局部路由，为故障路由的快速修复提供了可能。当某条正在使用的路由发生故障时，由发现故障的节点广播一个RREQ分组进行本地修复，则发送或转发该RREQ分组的节点J可能会有很多邻居节点都有到目的节点的局部路由，都可能会对节点J回复RREP分组，因此会在节点J处产生碰撞。为此，特定义如下规则。

规则8 节点I在收到节点J发送或转发的进行本地修复的RREQ分组后，如果自己的路由表中存在到目的节点的路由，则先侦听信道，当发现信道空闲时，就向节点J发送自己的RREP分组。如果到节点J的信道不空闲，则重复“退避→侦听→发送”的过程。

启动本地修复的节点可能会收到多个RREP，分别包含不同的到达目的节点的路由，但只选择其中跳数最少的路由，从而完成故障路由的快速修复。

4 仿真与性能分析

4.1 仿真环境设置

为了验证O-AODV路由协议的有效性，本文采用网络仿真软件 OPNET 11.5对其性能进行仿真分析，并与标准的 AODV协议[1]进行性能比较。

基本的仿真参数为：MAC协议类型为 IEEE 802.11 DCF；节点无线传输半径为 250m；节点移动模型为Random Waypoint；信号传播模型为自由空间传播；带宽为 2Mbit/s；业务类型为 CBR；分组长度为512byte；分组发送速率为2packet/s。

在基本仿真参数的基础上，本文设置了如下 2种场景来验证O-AODV路由协议的性能。

1) 节点最大运动速度变化的场景：仿真区域大小为1 500m×1 500m，节点数量为100个，节点间的最大连接数为30，节点的最大运动速度分别设置为 0m/s、5m/s、10m/s、15m/s、20m/s、25m/s、30m/s、35m/s、40m/s时进行仿真实验。

2) 网络规模变化的场景：节点的最大运动速度设置为 10m/s，同时在保证节点平均分布密度基本不变的前提下，扩大仿真区域，使得网络规模逐渐加大。仿真区域大小和网络中节点数量设置如表 1所示，节点间的最大连接数为30，并且将进行通信的节点选择为网络边缘的节点。

表1 网络规模变化场景下的参数设置

仿真时间均为600s，所有实验结果均为3次模拟的平均值。

4.2 性能评估指标

本文采用端到端分组投递率、数据分组端到端时延、平均路由修复时间和归一化路由开销 4个指标对AODV和O-AODV进行比较，前3个指标反映路由协议的可靠性和有效性，归一化路由开销则反映路由协议的效率。其中端到端分组投递率指的是目的节点接收到的数据分组的个数与源节点发送的数据分组的个数之比值；端到端时延指的是目的节点的分组接收时间与源节点的相应分组发送时间的平均差值；归一化路由开销反映的是为传输数据分组而发送的路由控制分组的开销；平均路由修复时间则指的是网络中节点从发现路由断裂并启动本地路由修复过程开始，到路由修复成功时所花费的时间的平均值（如果网络拓扑变化非常快，或者网络由于通信业务量大而发生拥塞，则断裂路由修复过程可能会由于超时而失败。本文忽略了所有修复不成功的断裂路由所花费的时间，只对成功修复的断裂路由所花费时间进行平均计算）。

4.3 仿真结果分析

4.3.1 节点最大移动速度变化场景下的仿真结果分析

图5(a)～图5(d)分别给出了AODV和O-AODV 2种路由协议在不同的节点最大运动速度条件下分组投递率、端到端时延、平均路由修复时间和归一化路由开销的仿真结果。

图5 最大移动速度变化场景下的仿真结果

由图5(a)可以看出，随着节点运动速度的提高，网络拓扑结构变化加剧，路由失效率增多，因此导致 2种路由协议的分组投递率都在下降。由于O-AODV采用的路由学习和闲时逆寻机制加快了故障路由修复的速度，提高了路由修复的成功率，因此 O-AODV的分组投递率在节点移动条件下高于AODV。

由图 5(b)可知，2种路由协议的端到端时延都随着节点运动速度的提高而增加，运动越快，时延越大。由于 O-AODV的闲时逆寻机制加快了路由发现的速度，路由学习机制则提高了断裂路由修复的成功率和速度，因此 O-AODV的源节点路由发现时延和路径中断修复时延均小于 AODV，使得O-AODV的端到端时延小于AODV。网络拓扑结构变化越快，O-AODV与AODV的端到端时延差别越大。

图 5(c)对比了 2种协议对断裂路由的修复速度。在节点处于静止状态时，网络中的路由发生断裂的可能性非常小，因此在最大速度为0时2种协议的平均路由修复时间接近于 0；随着节点移动速度的增加，2种协议的平均路由修复时间也随着增加。由于 O-AODV在网络中产生很多冗余的局部路由，加快了断裂路由的修复速度，因此O-AODV的平均路由修复时间大大低于AODV。

图5(d)则说明，随着节点运动速度的提高，用于成功传输数据分组的路由开销越来越大。由于O-AODV在路由学习和闲时逆寻时都需要少量的路由开销，因此在节点静止或慢速运动时，O-AODV的归一化路由开销略大于AODV。当节点最大移动速度大于20m/s时，网络拓扑结构变化加快，AODV路由修复次数和重路由次数逐渐增多，路由开销越来越大；而O-AODV通过路由学习和闲时逆寻减少了重路由，路由开销渐渐小于AODV。

4.3.2 网络规模变化场景下的仿真结果分析

此场景下的仿真结果如图6所示。

根据仿真结果可知，随着网络规模增大，从网络一侧的边缘节点到另一侧的边缘节点之间的路由跳数在增加，使得一条路由由于节点运动而断裂的可能性也加大了，因此AODV的分组投递率在明显下降；但网络规模的扩大增加了网络中的空闲节点，使得O-AODV产生的局部冗余路由也增多了，有利于加快路由发现和故障路由修复，因此网络规模的扩大对O-AODV协议的分组投递率影响不大。

图6 网络规模变化场景下的仿真结果

由于规模的扩大使得路由跳数增加了，使得数据传输时延和路由断裂的可能性都加大了，因此 2种协议的端到端时延以及平均路由修复时间就相应地增加了。但 O-AODV协议产生的大量局部路由加快了路由发现和断裂路由修复的速度，因此O-AODV的端到端时延和平均路由修复时间都小于AODV。

另外，网络规模的扩大使得2种协议的路由开销都明显增加了，由于 O-AODV的大量局部路由有利于减少了重路由的次数，因此可以有效地减少路由开销。

5 结束语

针对AODV路由协议在大规模和拓扑变化快的 MANET网络中性能较差和效率低的特点，本文提出了节点闲时逆寻机制和邻居节点路由监听学习机制，结合这 2种机制进一步提出了优化的AODV路由协议——O-AODV。O-AODV协议改进了原AODV协议的路由发现和故障路由修复过程，增加了对稳定路由的刷新，从而减少了节点重路由的次数，加快了故障路由的修复速度，节省了网络带宽。仿真结果表明，在规模大和拓扑结构变化快的MANET网络中，O-AODV协议中具有比AODV协议更好的性能和更高的路由发现与修复效率。

[1] PERKINS C, BELDING R E, DAS S. Ad-hoc On-demand Distance Vector ( AODV ) Routing[S]. IETF RFC 3561, 2003.

[2] MARINA M K, DAS S R. On-demand multipath distance vector routing for ad hoc networks[A]. Proceedings of IEEE International Conference on Network Protocols[C]. 2001. 14-23.

[3] AMMAAR Z, ALADDIN A. Analytical study to detect threshold number of efficient routes in multipath AODV extensions[A]. IEEE Cairo Conference(ICEEC07)[C]. 2007.95-100.

[4] HIGAKI H, UMESHIMA S. Multiple-route ad hoc on-demand distance vector (MRAODV) routing protocol[A]. Proceedings of the 18th International Parallel and Distributed Processing Symposium, IEEE[C].2004. 237.

[5] ZAHARY A, AYESH A. On-demand multiple route maintenance in AODV extensions (ORMAD)[A]. International Conference on Computer Engineering & Systems[C]. 2008. 225-230.

[6] SUJATA V. M, SUJATA T. Enhanced ad-hoc on demand multipath distance vector routing protocol (EAOMDV)[J]. International Journal of Computer Science and Information Security, 2010, 7(3):166-170.

[7] GWALANI S, ELIZABETH M, ROYER B. AODV-PA: AODV with path accumulation[A]. Proceedings of IEEE International Conference on Communication[C]. 2003.527-531.

[8] JOHNSON D B, MALTZ D A. Dynamic Source Routing in Ad Hoc Wireless Networks[M]. Kluwer Academic Publishers, 1996.

[9] ZHAO Q, ZHU H B. An optimized AODV protocol in mobile ad hoc network[A]. The 4th International Conference on Wireless Communications, Networking and Mobile Computing[C]. 2008. 1-4.

[10] JAGPREET S, PARAMJEET S, SHAVETA R. Enhanced local repair AODV (ELRAODV)[A]. International Conference on Advances in Computing, Control, and Telecommunication Technologies[C]. 2009.787-791.

[11] BEST P, GUNDETI S, PENDSE R. Self-learning ad-hoc routing protocol[A]. Vehicular Technology Conference, VTC 2003-Fall 2003 IEEE 58th[C]. 2003. 2824-2828.