陈运海

摘要： 该文通过研究移动自组网AODV路由协议，分析了AODV路由协议在链路断链时进行链路修复时的缺点，提出了AODV-OPT路由协议；新协议通过一个更加合理的链路修复方案提高了网络的性能。仿真实验表明AODV-OPT路由协议提高了网络中数据包的抵达率，同时减小了网络中传送数据时端到端的时延。

关键词： 移动自组网；AODV协议；优化；仿真

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）09-0039-03

Improvement and Simulation of AODV Routing Protocol in Mobile Ad Hoc Network

CHEN Yun-hai

（Department of Electronic Information Technology， Shenzhen Institute of Technology， Shenzhen 518116， China）

Abstract： In this paper，the author researched the AODV routing protocol in mobile Ad Hoc network，analyzed the drawback of the AODV routing protocol when it repair the broken link，and proposed AODV-OPT routing protocol to improve the network performance by a more reasonable way to fix the broken link. The simulation results prove that the AODV-OPT routing protocol can increase the Packet delivery ratio and reduce the Average end to end Delay.

Key words ：Ad Hoc network； AODV protocol ； improvement；simulation

1 引言

移动无线自组网络是一种自组织、快速配置而且无需固定设施的动态网络。网络节点能够以任意的速度和移动模式移动，也可以随时开机和关机，这些因素导致网络拓扑结构的不断变化。无线自组网络的路由协议可以分为表驱动和按需两大类。在按需路由协议中，只有节点需要进行通信时，才建立路由，以减少路由开销。目前用得比较多的典型按需路由协议为AODV（Ad Hoc on-demand Distance Vector）。

AODV是一种优秀的按需路由协议。在网络的拓扑结构发生改变的时候，它能快速收敛，计算量相对较小，占用的存储资源小，同时能够自我修复断路，占用网络带宽较小。并且AODV协议在网络中引入了节点序列号机制，可以有效避免网络环路和无穷计数问题。但在有效路由发生链路中断的情况下，在选择源节点修复还是本地修复的选择上，有可能选择不恰当的方式，从而引起网络的整体性能下降。

本文通过研究和分析现有的AODV路由协议的工作过程，在现有的AODV路由协议的基础上，提出了一个优化后的路由协议AODV-OPT。在AODV-OPT路由协议中，我们根据链路中断节点的上一跳节点的即时地理位置，选择合适的路由修复方案，减少了网络中的路由维护开销。通过仿真表明，这种协议很好地解决了链路中断时原AODV路由协议丢包率过高和数据分组传送延迟较高的问题。

2 AODV路由协议的工作过程

2.1 AODV路由协议的路由发现

在AODV协议中，当一个源节点希望发送一个数据到目标节点时，这时候才需要建立一个源节点到目标节点的路径。为了找到通往目的节点的路径，源节点就发起一个路径发现程序，它广播一个路由请求信息RREQ到邻居节点，邻居节点再转发这个RREQ到下一跳邻居节点，直到到达目标节点或一个拥有达到目标节点的有效路径的中间节点。

同时，收到RREQ的中间节点根据RREQ中的信息，建立到源节点的路由---在路由表中增加一个路由条目---称为“反向路由”。反向路由条目的目的节点是广播RREQ的源节点，下一跳节点是将RREQ发送给本节点的邻居节点。

如果到达目标节点或一个拥有达到目标节点的有效路径的中间节点时，这时候，此节点回复路由应答消息（RREP）到源节点，向源节点传送是沿着之前建立的方向路由进行单播传送。在传送的过程中，收到RREP的节点建立到目标节点的路由---在路由表中增加一条“正向路由”的路由条目。正向路由条目的目的节点是发送RREP的源节点，下一跳是将RREP发送给本节点的邻居节点。

2.2 AODV路由保持过程

路由建立后，为维护已建立的路由，每个节点周期性地广播发送Hello消息，以提供与相邻节点的相互连接信息，该消息的传播仅限于发送节点和相邻节点之间。收到Hello消息的节点将建立或更新一条至发送节点的路由。在AODV中，任何时候节点收到任何控制报文，也具有和收到显性的Hello消息一样的意义，从而随时保证节点的有效连接性。

如果在路由有效的时间没有被使用而引发路由过期，或者节点在确定的有效路由的下一跳无法到达（如节点移动或链路故障等）时，该路由无效。当节点检测到某一路由无效时，它在路由表中将该路由表项设置成无效，且经过一段时间后才将其删除。

如果在传送数据的过程中，有效路由发生链路中断，AODV协议中有两种处理方式：本地修复和源节点重建路由。如果断链处的上一个节点距离目标节点在MAX_REPAIR_TTL跳以内，则该节点就会进行本地修复，本地修复是发生断链的上一个节点发起路由发现，为了修复链路，节点将关于目标节点的序列号增加1，然后广播关于目的节点的RREQ；发起修复的节点等待路由发现周期来获得对RREQ进行访问的RREP。如果断链处的上一个节点距离目标节点大于MAX_REPAIR_TTL，则进行源节点修复，源节点修复是发生断链处的上一个节点向源节点发送RERR消息，源节点收到RERR消息后，由源节点发起路由发现，源节点将目标节点的序列号增加1，然后广播关于目标节点的RREQ。

如图1，假定MAX_REPAIR_TTL=4；发生节点6与7之间的断链时，由于节点6到D的距离为2<4，所以发起本地修复，只要修复6到D之间的路径即可。如图2，同样假定MAX_REPAIR_TTL=4；发生节点3与4之间的断链时，此时，节点3与D的距离为5>4，所以发起源节点修复。

2.3 AODV路由协议的路由修复过程的缺陷

我们知道，无线自组网的每个节点是不断移动的，如图3所示，如果节点6到7之间断链，目标节点D移动到距离源节点S一跳的位置，这时节点6发起本地修复将会引起整个网络系统性能的下降。这时反而采用源节点修复比较合理。

同样的，如果节点3到4之间断链，目标节点D移动到距离源节点附近几跳的节点3位置，如图4所示；这时通过源节点发起重建路由将会引起整个网络系统性能的下降。这时反而采用本地节点修复比较合理。

3 AODV路由协议的优化

3.1 AODV路由协议的改进思想

为了避免无线自组网在发生断链时在链路修复上浪费过多的时间，必须根据节点的移动状况来判定选用合适的路由修复方案。无线自组网发生断链时，很多情况下是由于节点的移动造成的，所以，我们要随时跟踪目标节点的地理位置情况。我们设目标节点离断链处的上一个节点的距离为hop1，源节点离断链处的上一个节点的距离为hop2；当hop1< hop2 时，采用本地节点修复；否则，采用源节点修复。为了准确捕捉目标节点的地理位置，需要在发起修复时，探测目标节点和源节点的相对位置，根据探测结果来采取相应的修复方案。我们称这种新的路由协议为AODV-OPT路由协议。

3.2 AODV-OPT路由协议的实现

NS3网络模拟器是一个优秀的网络模拟器，本身集成了对一些通用网络实体的建模，并且自带了对于AODV路由协议的仿真源程序。本文以AODV协议的源代码为基础框架，对改进后的路由协议进行编程改进，得到了改进后的AODV-OPT协议仿真源码。然后分别运行改进前后的源代码程序，并设定一定的场景。运行后，得出跟踪信息，然后收集跟踪信息进行对比分析。

4 AODV-OPT路由协议的性能仿真与分析

为了对AODV-OPT路由协议的性能进行分析，我们采用比较优秀的网络模拟器NS3，分别对AODV、AODV-OPT路由协议进行了分析，通过仿真分别得到了它们的数据包传送率、端对端的平均延迟，用来衡量比较两种路由协议的性能。

4.1 模拟场景设计

我们知道，在移动无线自组网中，影响移动无线自组网的性能指标的节点因素有：节点运动拓扑区域的大小范围、网络中节点的个数、有多少节点在发送数据（即数据链路数）、节点发包速率、节点的移动速度、节点传输能量等。我们取80个节点随机分布在300m*1500m的平坦区域内，节点采用Random Waypoint随机运动模型，节点发包速率为2048bit/s，节点的传输能量为7.5 dBm。我们分别记录节点的最大移动速度为10m/s、20m/s、30m/s、40m/s、50m/s、60m/s、70m/s、80m/s、90m/s、100m/s的数据发送和接收情况，端到端的传送延迟情况，然后再进行统计分析。

4.2 数据包抵达率的统计和分析

数据包抵达率（Packet delivery ratio）是源节点产生的数据包与目的节点收到的数据包的比值。该指标反映了网络的吞吐量，表明路由协议的有效性和适应网络变化的性能。我们可以利用下面这个计算机公式来进行求解数据包抵达率：

数据包抵达率=目的节点接收到的数据包个数/源节点发送的数据包个数

我们根据仿真过程中产生的数据，得出了两种路由协议数据包抵达率的变化情况，如图5所示。我们可以看出，在节点移动速度变大时，对于两种路由协议，数据包抵达率都有下降的趋势。但总体上看，AODV-OPT路由协议的数据包抵达率明显高于AODV路由协议，优化造成了网络性能的明显提高。

4.3 平均端到端时延的统计和分析

平均端到端时延反映了在实际网络应用中的时间特性，特别是对于按需路由协议来说显得更为重要。它包括了节点进行路由查找和在端口排队时，数据分组在缓冲区中的延迟，同时也包括了MAC层进行重组以及分组传播的时间。平均端到端时延即为所有成功传送数据分组时延的平均数。我们可以用下面的公式来计算：

平均端到端时延 = ∑（接收到数据包的时间 - 发送包数据包的时间）/发送的数据包个数

我们根据仿真过程中产生的数据，得出了两种路由协议数据包平均延时的变化情况，如图6所示。我们可以看出，AODV-OPT路由协议的数据包平均延时明显小于AODV路由协议。端到端延时越小，说明网络传送数据越顺畅，表明网络的性能越好。因此，通过仿真实验证明，优化路由协议明显提高了无线自组网的性能。

5 结束语

本文主要对无线自组网中的AODV路由协议进行了研究和改进。首先介绍了无线自组网AODV路由协议的工作过程，然后指出了AODV在路由修复中存在的缺点和不足，并提出了一种改进的AODV路由协议。最后利用NS3网络模拟器进行编程仿真，运行仿真程序，收集仿真过程中的数据进行统计和分析；并通过对比分析，从而证明了改进的路由协议AODV-OPT在性能上是优越的。

参考文献：

[1] 陈娟.基于Ad Hoc网络的自适应中断容忍路由协议的研究[D].北京：北京邮电大学，2015.

[2] 麻晋文.移动Ad hoc网络中AODV路由协议的研究[D] .兰州：兰州大学，2014.

[3] 翟振辉.自组织网络中的AODV路由协议的优化研究[D].北京：北京邮电大学，2011.

[4] Mehdi Zarei，Karim Faez，Javad Moosavi Nya，Modified Reverse AODV Routing Algorithm using Route Stability in Mobile Ad Hoc Networks[C].Multitopic Conferenee，2008，：255-259.

[5] ns-3 developers[EB/OL]. http：//www.nsnam.org/developers/overview

[6] ns-3documentation[EB/OL]. http：//www.nsnam.org/docs/doxygen/index.html.