AODV协议路由修复算法改进研究

蔡保国王耀国贾军

（武汉船舶通信研究所武汉430205）

AODV协议路由修复算法改进研究

蔡保国王耀国贾军

（武汉船舶通信研究所武汉430205）

论文对AODV协议的路由修复算法进行了改进研究。通过修改路由响应包（RREP）和数据包的监听机制，节点不仅建立了到目的节点的前向路由，也建立了到源节点的反向路由，减少了寻路带来的开销。除此之外，论文还对中断路由的修复策略进行了调整，以进一步提高路由修复的成功率。基于QualNet4.5的仿真结果表明，论文提出的路由修复改进算法在未明显增加数据包的平均端到端延时和控制开销的情况下，进一步提高了AODV协议的分组投递率。

路由修复算法；监听机制；中断路由；平均端到端延时；控制开销；分组投递率

Class NumberTP393

1 引言

AODV协议［1］是一种典型的按需路由协议，具有效率高、开销低的优点，能够较好地适应无线自组织网络［2］动态、自组织、多跳的特点。当某条活动路由发生链路中断时，AODV协议采用本地修复（AODV-LR）算法［3～5］。但是，洪泛式的路由修复算法不仅增加了控制开销和端到端延时，也加剧了网络拥塞和碰撞，可能导致更多的链路中断发生。为此，研究人员提出了各种改进的路由修复算法。PATCH［6］将路由修复的范围限定在两跳范围内，通过搜索中断节点的下一跳和下两跳节点来修复中断路由，以较低的开销实现中断路由的快速修复。PATCH认为链路中断时下一跳节点位于当前节点两跳范围内的概率较大，但若不能成功修复路由将会导致更多的丢包。AODV-ABR和AODV-ABL［7］借鉴了AODV-BR［8］通过监听建立替代路由的思想，只不过节点除了监听附近的RREP包传输，还监听附近的数据包传输，这提高了替代路由建立的概率。链路中断时，中断节点不是通过将数据包进行广播而是通过询问邻居节点来修复中断路由。二者的区别在于：当发生链路中断时，AODV-ABR始终依赖邻居节点的替代路由进行路由修复，而AODV-ABL则根据节点位置决定采取何种路由修复策略：AODV-LR或AODV-ABR。然而，与AODV-BR一样，它们都只建立了到RREP包（或数据包）中目的地址的前向替代路由，而没有建立到RREP包（或数据包）中源地址的反向替代路由。

为了提高AODV协议的路由修复效率，本文提出了一种不同的监听机制和中断路由修复策略，并通过仿真进行了验证。

2 有关路由修复算法

评价路由修复算法优劣的指标包括路由修复效率和路由修复代价。前者是指路由修复的成功率，后者是指路由修复所需的额外开销，它们与路由修复概率及路由搜索半径有关。路由修复概率越高，则路由修复效率越高；路由搜索半径越大，则路由修复代价越高，同时路由修复效率也越高。

在AODV-LR算法中，是否进行本地路由修复由中断节点的位置决定。当中断节点到目的节点的跳数不大于MAX_REPAIR_TTL时，其将发起洪泛式路由修复过程；否则，其将向源节点发送RERR消息报告路由中断。假设活动路由上各节点发生链路中断的概率是相等的，记源节点到目的节点的跳数为n，则AODV-LR算法进行路由修复的概率PAODV-LR满足

AODV-LR算法进行路由搜索的半径R可表示为

其中#hops表示中断节点到源节点的路由跳数。

在PATCH算法中，中断节点进行路由修复的概率为100%，其路由搜索半径为2跳（邻居节点及其下一跳）。

在AODV-ABR和AODV-ABL算法中，中断节点进行路由修复的概率也为100%，但路由搜索范围不尽相同。其中AODV-ABR算法的路由搜索半径始终为1跳，而AODV-ABL算法的路由搜索半径分为两种情况：若中断节点到目的节点的跳数不超过MAX_REPAIR_TTL，路由搜索半径与AODV-LR算法相同，如式（2）所示；否则，路由搜索半径与AODV-ABR算法相同，等于1跳（邻居节点）。

表1 几种路由修复算法比较

根据以上分析，可将上述几种路由修复算法进行简单比较，如表1所示。

3 改进的AODV路由修复算法

3.1 监听机制

如前所述，AODV-ABR和AODV-ABL算法没有建立到RREP包（或数据包）源节点的反向替代路由。除此之外，与AODV-BR类似，AODV-ABR和AODV-ABL将路由分为两类：主路由与替代路由，因此每个节点都需要维护两张路由表：主路由表与替代路由表，两种路由的处理策略可能不尽相同。在我们提出的算法中，节点通过监听不仅可以建立到RREP包（或数据包）源节点的反向路由（如果有必要的话），而且所有节点都只需维护一张路由表，这与AODV协议一致。

节点监听到RREP包时处理如下：

1）节点首先查询是否有到该RREP包中目的地址的路由（RREP包中的目的地址是产生RREP包的源地址），若无路由或路由已过期，或路由的目的序列号小于RREP包中的目的序列号，或目的序列号相等但路由跳数大于RREP包中跳数加1，则建立或更新路由，否则转2）；

2）路由保持不变

具体过程如图1所示。节点B通过监听节点F转发的RREP，建立了到RREP中目的节点D的新路由。

图1 RREP的监听处理

节点通过监听数据包，不仅可以建立或更新到数据包目的节点的路由，还可以建立或更新到数据包源节点的路由，路由建立或更新的规则与处理RREP完全相同。不过，要想通过监听邻近的数据包来建立或更新路由需要在数据包的头部记录到源节点和目的节点的跳数信息。节点监听数据包的具体过程如图2所示。节点C通过监听节点F上的数据包传输，建立了到数据包源节点S和目的节点D的路由。另外，图2还示意了通过监听建立的路由被删除的情形。节点B之前通过监听节点F转发的RREP建立了到节点D的路由（见图1），随着节点的移动和网络拓扑的变化，节点B逐渐移出了节点F的传输覆盖范围。若在一定时间内该路由未得到更新（例如节点B在该时间内始终未能从节点F接收或监听到任何消息），该路由将被认为已过期并予以删除。

图2 数据包的监听处理

3.2 中断路由修复策略

当数据传输过程中发生链路中断时，中断节点将发起路由修复过程。与文献［7］类似，路由修复也采用握手方式进行，但具体方法与AODV-LR、AODV-ABR以及AODV-ABL算法有所不同。具体操作过程如下：

1）不论中断节点位置如何，其都将广播一个一跳的RREQ；

2）若其某邻居正确收到该RREQ且有到该中断路由目的地址的有效路由，则用RREP进行回复；

3）若中断节点在一定时间内成功接收到一个或多个RREP，则路由修复成功，接下来的处理与AODV-LR相同；否则，按照AODV-LR算法进行修复；

4）若中断节点在一段时间内成功收到一个或多个RREP，则路由修复成功，接下来的处理与AODV-LR相同；否则，路由修复失败，中断节点沿反向路由方向发送RERR。

4 仿真与评估

为了检验路由修复算法性能，采用QualNet4.5［9］进行仿真。仿真场景大小设为1500m×1500m，50个节点随机分布于其中，仿真结果取20幅不同拓扑图运行结果的平均值。仿真时间为300s，信道带宽为2Mbps，路径损耗模型为Two-Ray Ground Model，节点移动模型为Random Waypoint Model，节点最大移动速率为20m/s，节点最大暂停时间为300s，物理层采用802.11b模型，MAC层采用802.11 DCF协议，随机选择若干对节点建立512字节的CBR/UDP业务，CBR包生成速率为4包/秒，节点运行AODV协议，路由修复算法分别采用AODV-LR、AODV-ABR、AODV-ABL以及本文提出的路由修复算法（记为AODV-IRR）。

4.1 分组投递率

分组投递率是指所有目的节点总共接收到的数据包数目与所有源节点总共发送的数据包数目之比。我们分别仿真了在四种不同路由修复算法下分组投递率随节点暂停时间变化的性能曲线，如图3所示。我们发现，当暂停时间增加时，分组投递率呈下降趋势，这一结果与文献［8］中的仿真结果相异。这是由于在我们设定仿真场景中，较少的暂停时间或者说更多的移动性反而提高了Ad Hoc网络的吞吐量，这正好与文献［10］的结论一致。

图3 分组投递率

4.2 端到端延时

端到端延时反映了数据包从源节点到目的节点所经历的平均时间（只考虑成功到达目的节点的数据包），它包含了数据包在各跳节点中的排队时延、传输时延、传播时延以及可能的路由重建时间（例如路由修复时间）。平均端到端延时随暂停时间变化的曲线如图4所示。

图4 端到端延时

4.3 控制开销

控制开销是指每成功发送一个数据包平均需要发送的控制包数目。如图5所示，控制开销随暂停时间的增加而增加，这是由于在节点移动状态下路由修复方案能够自适应地优化路由，减少路由中断的发生。在相同的暂停时间下，由于AODVABR将路由修复的范围限定在一跳范围，因而其控制开销最低。当中断节点和目的节点之间的距离大于MAX_REPAIR_TTL跳时，AODV-ABL和AODV-IRR仍将修复中断路由，因此其控制开销比AODV-LR高。与AODV-ABL相比，AODV-IRR可能有更多的修复尝试，因此其控制开销在四种修复方案中最高。

图5 控制开销

5 结语

本文提出了一种改进的AODV路由修复算法（AODV-IRR），其能更有效地适应网络拓扑的变化。通过监听邻近的RREP和数据包传输，AODV-IRR不仅能够创建或更新到目的节点的前向路由，也能创建或更新到源节点的反向路由。而且，AODV-IRR并不需要维持备用路由表，这也在一定程度上减少了协议的开销和复杂度。最后的仿真结果表明，与AODV-LR、AODV-ABR以及AODV-ABL相比，AODV-IRR以稍高的平均端到端延时和控制开销为代价，获得了更高的数据包投递率性能。

［1］Perkins C，Royer E，Das S.Ad hoc On-demand Distance Vector（AODV）Routing［S］.IETF RFC 3561，2003.

［2］Gupta P，Saxena P，Ramani A K，et al.Optimized use of battery power in wireless Ad hoc networks［C］//Proceedings of IEEE International Conference on Advanced Communication Technology，2010：1093-1097.

［3］Yu C W，Wu T-K，Cheng R H.A low overhead dynamic route repairing mechanism for mobile ad hoc networks［J］. Computer Communications，2007，30（5）：1152-1163.

［4］薛强，吕光宏.AODV的本地修复改进机制［J］.计算机工程，2008，34（19）：121-126.

XUE Qiang，LV Guanghong.Improved local recovery mechanism in AODV［J］.Computer Engineering，2008，34（19）：121-126.

［5］丁绪星，吴青，谢方方.AODV路由协议的本地修复算法［J］.计算机工程，2010，36（6）：126-130.

DING Xuxing，WU Qing，XIE Fangfang.Local repair algorithm for AODV routing protocol［J］.Computer Engineering，2010，36（6）：126-130.

［6］Liu G P，Wong K J，Lee B S，et al.PATCH：A novel local recovery mechanism for mobile ad-hoc networks［C］//Proceedings of IEEE Vehicular Technology Conference，2003：2995-2999.

［7］Lee S J，Gerla M.AODV-BR：Backup routing in ad hoc networks［C］//Proceedings of IEEE WCNC 2000，2000：1311-1316.

［8］Lai W K，Hsiao S Y，Lin Y C.Adaptive backup routing for ad-hoc networks［J］.Computer Communications，2007，30（2）：453-464.

［9］Scalable Network Technologies，Inc.QualNet 4.5 Programmer's Guide［EB/OL］.http：//www.qualnet.com，2008.

［10］Grossglauser M，Tse D.Mobility increase the capacity of Ad hoc wireless networks［J］.IEEE/ACM Transactions on Networking，2002，10（4）：477-486.

Research on Improved Route Repair Algorithm of AODV Protocol

CAI BaoguoWANG YaoguoJIA Jun
（Wuhan Maritime Communication Research Institute，Wuhan430205）

An improved route repair algorithm of AODV protocol is researched in this paper.By means of the modifications to overhearing mechanism of Route Reply（RREP）packets and data packets，a node can create forward routes to destination nodes and backward routes to source nodes，which decreases the costs caused by routing.Besides，the repair measures of broken routes are adjusted to improve the success rate of route repair in this paper.The simulation results based on QualNet 4.5 show that the improved route repair algorithm proposed in this paper can efficiently improve packet delivery ratio of AODV protocol and clearly decrease its control overheads in case of not obviously increasing average end-to-end delay of data packets.

route repair algorithm，overhearing mechanisms，broken routes，average end-to-end delay，control overheads，packet delivery ratio

TP393

10.3969/j.issn.1672-9722.2017.06.032

2016年12月8日，

2017年1月22日

蔡保国，男，博士，工程师，研究方向：无线通信网络总体设计。王耀国，男，博士，工程师，研究方向：无线通信网络协议及大数据应用。贾军，男，硕士，工程师，研究方向：无线通信设备硬件设计。