移动Ad Hoc网络AODV路由协议的改进

俞双龙，于瀛

(中国传媒大学 信息工程学院，北京 100024)

移动Ad Hoc网络AODV路由协议的改进

俞双龙，于瀛

(中国传媒大学 信息工程学院，北京 100024)

针对目前AODV路由协议仅维持一条路由，在路由失效时本地修复机制不够完善，重新发起路由建立过程必定增加了路由延时和开销的问题，本文提出建立一种备用路由及本地修复相结合的路由协议。首先简要介绍了移动Ad Hoc网络和AODV路由协议，然后在对AODV路由协议进行了研究的基础上实现一种带备份路由和本地修复的优化。最后通过NS2对改进的路由协议与AODV路由协议的仿真模拟，在延时、到达率和路由开销方面进行了对比。仿真结果证明了修改后的路由协议能更好的提高了网络的性能。

移动Ad Hoc网络；AODV路由协议；备份路由；NS2

1 引言

移动Ad Hoc网络是一种不依赖固定设施的、自组织的无线网络。具有抗毁性强，组网灵活及使用方便的特点。既可应用于救援、会议、战场、探险或危险环境中的目标监控等场合，又可用于有线网末端网络的扩展。移动Ad Hoc网络的动态变化的拓扑结构，使得传统的路由协议在该环境下无法正常运行。因此，Ad Hoc网络的路由协议是研究热点之一。目前已提出的平面路由算法分为表驱动路由协议和按需路由协议。由于表驱动路由协议要周期性地交换路由信息，导致路由开销很大，因而当需要路由时才发起路由查找的按需路由协议更加适合于 Ad Hoc 网络环境。

自组网按需距离矢量路由(Ad-Hoc On-Demand Distance Vector Routing，AODV)协议[1]是移动Ad Hoc网络中被广泛应用的按需路由协议之一。

AODV协议借鉴了动态源路由(Dynamic Source Routing，DSR)协议[2]和目的节点序列号距离矢量路由(Destination-Sequenced Distance-Vector，DSDV)协议[3]的优点，借用了DSR中的路由发现和路由维护的基础程序，以及 DSDV 中的逐跳路由、顺序编号等机制。近年来，人们针对AODV协议的特点提出了很多改进方法，如文献[5]提出了避免路由断裂的节能路由算法，文献[6]提出了基于AODV改进型备用路由修复协议。本文提出另一种带备用路由协议的新方案，在节点发生断裂时首先判断是否满足本地修复条件，若满足则进行本地修复，否则直接调用备用路由继续通信。通过仿真证明了改进了的路由协议有效的降低了端到端延时和路由开销，改善网络性能。

2 AODV路由协议

AODV 路由协议中，每个节点分布式地生成并维护一个路由表。路由表信息主要包括目的节点地址、目的节点序列号、跳数、下一跳节点、前驱列表、寿命、路由标记等参数。协议不进行周期性路由信息的交换，而是在需要进行通信而路由表中又没有路由的情况下才发起路由请求。AODV路由协议主要分为两个过程：

路由建立：如果在源节点需要和目的节点通信时没有可用路由，则源节点向周围节点广播 路由请求(Route Request，RREQ)消息。中间节点在第一次收到这个消息后，建立一条反向路由，而且对以后收到的同一个 RREQ 加以丢弃。当目的节点收到第一个 RREQ 消息后，向源节点沿着反向路由单播一个路由应答(Route Reply，RREP)消息，从而沿着这条反向路由将正向路由建立，对以后收到的 RREQ 将不做 RREP 响应。如果中间节点收到 RREQ 消息，先查找路由表，若发现已有通往目的节点的可用路由时，此中间节点将代替目的节点向源节点单播 RREP 消息，从而建立双向路由。对于那些建立了反向路由，但没有收到RREP 消息的中间节点，它们先前建立的反向路由将会在一定时间后自动变为无效。

路由维护：每个节点定时向周边节点发送一个特殊的消息——HELLO 消息，以通知相邻节点自己的存在，通过这种方法来维护网络的连通性。当一段时间没有收到某个下一跳节点的 HELLO 消息时，就代表这个路由已经断裂。如果此节点离目的节点较近的话，就会进行本地修复(Local Repair)工作——即上游节点发送一个 TTL 值合适的 RREQ，期间收到的数据包将被节点缓冲。如果此节点离源节点较近或者本地路由修复不成功的话，就向源节点发送 RERR 消息，以更新沿途节点的路由信息。当源节点收到这个 RERR 消息后，重新发起路由发现过程，来重新建立路由。

3 改进的AODV算法

3.1 改进思想

针对AODV只维护一条路由及本地修复不完善的情况，本文提出一种带备用路由协议的新方案，在路由发起过程中，源节点路由表中不仅保存一条主路由，源节点和邻居节点都保存一条到目的节点的其他路由。主路由失效时，根据断裂节点的位置和周围节点的情况而确定是否进行本地修复。若不满足本地修复条件，则通知源节点，源节点则可直接通过调用备用路由继续进行数据的传送。

3.2 改进关键思想的实现

为了实现源节点维护两条路由，需要修改原AODV路由协议的协议函数和路由表项以使源节点保存两条最新的路由。首先分析节点中是否存在一条主路由，若存在，则比较目的节点序列号和路由跳数，若新的路由较优，则将该新路由作为主路由，将原来的路由不删除作为备用路由。若收到RREP的节点路由表中没有路由，则直接将其作为主路由保存到路由表中。总之保证将最优和次优路由作为主路由和备用路由。

在路由失效时，若断裂的节点离目的节点较近时，进本地修复不仅可以快速进行路由维护减少数据包的丢失，也能减少源节点进行新的路由发现造成的路由开销。为了控制本地修复的范围，减少开销，AODV 路由协议设置了能够进行本地修复的最大修复长度(MAX_REPAIR_TTL)而且只有当下游节点断开时才有可能进行本地修复。最大修复长度可以人为设定，文献[7]发现随着 AODV 路由协议本地修复的最大修复长度逐渐变大，数据分组投递率也会逐渐变大。但若MAX_REPAIR_TTL过大，本地修复可能会适得其反，造成更大延时和开销，当断裂的节点离源节点较近时，重新发现路由可能更能发现最优路由。因此本文中将发送断裂的节点距目的节点跳数的参考值设为MAX_REPAIR_TTL+2。在某节点发生断裂时，设该节点距目的节点的跳数为hop_count，根据断裂节点与目的节点距离来判断是否进行本地修复，分以下三种情况进行处理：

若hop_count为3跳以内，则按原AODV方式进行本地修复。

若hop_count大于3小于MAX_REPAIR_TTL+2，则将本地修复定时器LOCAL_REPAIR_WAIT_TIME设为T1(T1值小于原AODV的定时值)，先进行本地修复，若T1时间内修复不成功则发送RERR给源节点。

若hop_count1大于等于MAX_REPAIR_TTL+2，则直接发送RERR给源节点，收到RRER源节点检查是否存在有效的备用路由，若存在则直接使用备用路由，若不存在则重新启用路由发现机制。

3.3 改进后协议的工作过程

改进后的协议，如图1所示，当源节点S要与目的节点D进行通信时，节点S没有到D的有效路由，节点S会广播一个RREQ分组发起路由查询。一段时间后节点S会收到不同路由的RREP分组，同原AODV协议一样，源节点S会选择一条最优路由作为路由发送数据。对与收到的其他RREP，源节点和周围一跳节点范围内的节点选一条次优路由保存在路由表中。当主路由失效断裂时，首先判断发生断裂的节点离源节点和目的节点的距离，若发现离目的节点D较近，如图1中节点4到目的节点断裂，且发现节点4周围邻居节点数较多，则进行定时并开始本地修复，此时进行本地修复成功率一般较高，若在一定时限内本地修复未成功，则向源节点报错，源节点则进行相应的处理。若发现断裂的节点离目的节点较远而离源节点距离较近，如图1中节点8与节点9发送断裂，则节点8直接向源节点S发送路由出错RERR分组，源节点收到报错后，直接调用备用路由继续进行数据传输，若备份路由也失效，则源节点直接广播RREQ分组发起新的路由建立过程。我们把改进后的AODV协议命名为AODVB(AODV with Backup route)协议。

图1 简单的拓扑结构

4 仿真及分析

4.1 仿真模型建立

NS2是一种可扩展、可重用、基于离散事件驱动、面向对象的网络仿真软件。NS2是一个用C++编写，并且以Otcl为前段的 面向对象的模拟器。模拟器支持C++中类的层次接口和Otcl解释器中类似的层次结构。本文的仿真是在NS2中进行的，设定的运动场景如下：

50个移动节点的网络，随机分布在1500m×300m的平面矩形内。节点的无线传输范围默认为250m，节点间的最大连接数为30，分组的发送率设为4，即每秒发4个512字节的分组，随机种子数设为1。节点到达目的节点后都停留60s，再往其他地方移动，整个模拟时间设定为900s，节点的最大移动速度分别设为0m/s，5m/s，10m/s，15m/s，20m/s和25m/s。节点的移动速度越大，表示网络的拓扑结构变化越频繁。MAC 层协议采用的是 IEEE 802.11，无线电传播模型是Two-Ray Ground Re-flections Model。

4.2 性能评估参数

选择以下三个参数作为性能评估参数：

1.平均端到端延时：各目的节点收到数据分组的时间与相应源节点生成数据分组的时间之差的平均值，丢弃的分组不统计在内。

2.分组到达率：应用层信宿接收到的分组数与信源发送的分组数之比，反映了网络传输的可靠性，投递率越高，可靠性越大。

3.归一化路由开销指的是每发送一个数据报文所需要的路由控制报文数。使用归一化路由开销比单纯使用路由开销即路由控制分组更能说明协议的开销情况。

4.3 仿真结果分析

从图2可以看出，AODVB路由协议的延时要小于AODV路由协议。这是因为主路由失效时，AODVB能及时进行本地修复找到新的路由或使用备用路由，随着节点移动速度的逐渐增大，网络变化的也越快，AODV和AODVB的延时基本保持平稳，体现了按需路由协议适应网络拓扑变化的优点。

图2 平均端到端延时比较

从图3可以看出，由于网络环境较复杂，分组到达率都较低，随着节点移动速度的增加，分组的到达率整体都有下降的趋势，但AODVB路由协议由于其改进的本地修复及带有备用路由，减少了路由断裂时重新发起路由建立而造成的分组丢失，其分组到达率要高于AODV路由协议。

图3 分组到达率比较

图4显示了两种路由协议的归一化路由开销情况，由图可见随着网络变化的频繁，路由开销都有增大的趋势，但AODVB由于其本地修复和备用路由的存在，减少了路由发现的次数，故减少了广播分组新建路由，从而大大降低了路由开销。

图4 归一化路由开销比较

5 结论

针对AODV每次发起路由发现过程都会广播RREQ报文，这个过程会造成网络开销的增加和延时的增大，本文提出了一种带备用路由协议的改进型协议。仿真表明改进的路由协议在延时、到达率和路由开销方面都得到了改善。后面的工作将研究如何减少RREQ的盲目广播，进一步减少路由开销，提高网络性能。

[1]Perkings C，Royer E，Das S.Ad Hoc On-demand Distance Vector Routings[R].RFC3561，2003.

[2]Johnson D B，Maltz D A，Hu Yih-Chun.The dynamic source routing protocol for mobile ad hoc networks[EB/OL].http：//tools.ietf.org/html/draft-ietf-manet-dsr-10.2004-07.

[3]Perkins C E，Bhagwat P.Highly dynamic destination sequenced Distance Vector routing(DSDV) for mobile computers[C].Proc of ACM SIGCOMM，London，1994：134-244.

[4]徐雷鸣，庞博，赵耀.NS与网络模拟[M].北京：人民邮电出版社，2003.

[5]张昱.Ad Hoc 网络中避免路由断裂的节能 AODV 算法改进[J].计算机工程与应用，2006，(16).

[6]潘有芬，黄波，赵春霞.一种基于AODV的备用路由协议[J].通信市场，2012，(7).

[7]高芳，董泽，陆原，黄永平，陈义.移动Ad Hoc网络路由协议系能仿真分析[J].华北电力大学学报，2008，35(2)：108-112.

ImprovementofAODVRoutingProtocolinMobileAdHocNetwork

YU Shuang-long，YU Ying

(Communication University of China，Beijing 100024，China)

As current AODV routing protocol maintain only one routing，re-initiate route establishment process would increase the routing delay and overhead.This paper established a routing protocol with a combination of an alternate route and local repair.First this paper introduced the Ad Hoc network and AODV routing protocol.Than it proposed an optimization method based on studying its inadequacies.The average delay，arrive ratio，normalized routing load were compared by simulating new routing protocol and the AODV routing protocol through NS2.Results indicated that the optimized protocol decreased the expense of network and showed better performance than AODV routing protocol.

Mobile Ad Hoc network；AODV routing protocol；alternate routing；NS2

2013-05-08

俞双龙(1988-)，男(汉族)，安徽人，中国传媒大学硕士研究生.E-mail：ahnuysl@126.com

TP393.03

A

1673-4793(2013)04-0062-05

(责任编辑：王谦)