AODV、AOMDV和AODV-UU路由协议性能仿真与分析

谢 佳，徐山峰

(中国电子科学研究院，北京 100041)

0 引言

无线自组织(Ad Hoc)网络是一种特殊的无线移动通信网络。网络中的节点不仅具有普通移动终端所需的功能，而且具有报文转发能力。网络中的所有节点地位平等，无需设置任何中心控制节点，具有很强的抗毁性。Ad Hoc网络与其他移动通信网络的最根本区别是，节点间的通信可以经过多个中间节点的转发，即报文要经过多跳(Hop)到达目的地[1]。

Ad Hoc网络技术的典型应用是2001年由美国国防高级研究项目局(DARPA)提出研制的战术瞄准网络技术(TTNT，tactical targeting networking tech-nology)。TTNT是一种基于IP的嵌入到联合战术无线电系统(JTRS)中的新型战场网络技术。TTNT数据链系统可在战术飞机、武器系统和地面节点间建立类似互联网的无线宽带通信网[2]，从而对时间敏感目标的精确打击起到决定性作用，使美军的网络中心站能力产生质的飞跃[3]。

路由协议是Ad Hoc网络的核心，它负责完成邻居发现、分组路由、接纳控制、拥塞控制和网络互联等功能。针对路由协议进行性能仿真与比较分析，可以针对不同的应用场景选择合适的路由协议，提高Ad Hoc网络的通信性能。

Ad Hoc网络路由协议，大致分为两类:先验式路由协议和反应式路由协议。反应式路由不会周期性发送网络状态控制包，在节点移动性较强、节点电池能源有限的情况下，反应式路由协议性能优于先验式路由协议[4]。在反应式路由协议中，按需距离矢量路由协议(AODV)具有适度的路由开销和快速收敛性，最有研究价值。

AODV、AOMDV和AODV-UU同属AODV协议族，而AOMDV和AODV-UU在AODV基础上进行了改进。AOMDV基于无环、不相交多链路技术。AOMDV的多径路由之间不共用节点，从而保证了链路不相交[5]。AODV-UU是 AODV路由协议在Linux下的实现。AODV-UU能够更好地支持组播和子网络。此外，AODV-UU还能够支持Internet网关和多种网络接口。

1 协议简介

1.1 AODV

AODV综合使用了目标序列距离矢量路由(DSDV，destination-sequenced distance-vector)中目标序列号和动态源路由(DSR，dynamic source routing)中按需路由发现技术，提供了一种按需单径距离矢量无环路由。该协议分为路由发现和路由维护两部分。

①路由发现:当源节点需要与其他节点通信但没有到该目的节点的路由时，源节点广播路由请求RREQ。当其他节点收到这个RREQ时，首先判断是否收到过具有相同源节点和目的节点的RREQ，如果是，则丢弃，如果不是，继续广播该RREQ。当目的节点收到RREQ时，同样建立反向路由，然后向源节点发送RREP，如图1所示。

②路由维护:节点通过MAC层周期性广播hello消息来判断链路状态，如果该节点连续3次未收到hello响应消息，就认为链路已经断开，删除包含该链路的路由信息，并发送路由错误，通知相邻节点和相应上游节点删除因链路断开导致目的节点不可达的路由信息，如图2所示。

图2 AODV路由维护示意图

1.2 AOMDV

AOMDV是一种在AODV基础上扩展的按需多径路由协议。该协议通过获取多条无环和链路不相交的路径来实现多路径协议。AOMDV主要有两部分与AODV不同:(1)建立和维护无环路径更新的机制;(2)获取多条链路不相交路径分布式协议的方法。

①路由发现:AOMDV路由发现阶段与AODV类似，为了确保路径无环，仍使用目的地序列号来表明路由更新情况，并在内部数据结构增加广播跳数代替原来的跳数，以表明到达目的地节点的最大跳数和＜nexthop，hopcount＞链表及一个路由列表。每次路由更新都要对新的目的地序列号和当前的目的序列号进行比较。如果新的目的地序列号较大，则重新设置广播跳数为无穷，并把相应的地址作为到达目的节点的下一跳地址;如果两个目的地序列号相等，且新的广播跳数较小，则把该地址作为下一跳地址，以保证不出现回路。为了实现链路不相交，在路由请求阶段不是随意丢弃重复的RREQ，而是有目的地判断该RREQ包的第1跳是否与主机节点第1跳相同，如果不同，才把该路由信息保存下来，否则丢弃，如图3所示。

图3 AOMDV路由发现示意图

②路由维护:AOMDV的路由维护阶段与AODV类似，不同的只是当路由表中的所有下一跳地址的路径都失效时，才重新作路由发现，如图4所示。

图4 AOMDV路由维护示意图

1.3 AODV-UU

AODV-UU路由进程的包处理包括AODV路由协议控制包的处理和数据包处理。

①路由发现:为了让目的节点知道到源节点的路由，如果中间节点有到目的节点的路由，中间节点单播RREP帧到源节点来响应RREQ帧的同时也发送一个免费RREP帧到目的节点，让目的节点知道这条新路由。AODV-UU路由发现示意图，如图5所示。每个节点重启后在对任何路由信息做出应答前等待一个DELETE_PERIOD，以避免路由环路。

图5 AODV-UU路由发现示意图

②路由维护:为了防止过早删除在内核路由表中的路由，路由表维护包括内核路由表项的定期更新。为了维护目的节点与外出接口的交流，在路由表项中加入了interface字段。AODV-UU使用内核交互更新内核路由表，发送ICMP帧到应用并从Netfilter钩子接收包。AODV守护进程通过使用netlink套接字来改变IP路由表。

AODV-UU的内核模块使用netfilter钩子来决定包是到来的还是出去的，并且决定它应该被接收还是转发。投递到Netfilter钩子上的IP数据包会被捕获并可以通过添加自定义代码进行修改，如图6所示。

图6 Netfilter框架图

2 仿真与分析

采用NS-2作为仿真工具，NS-2是一款功能强大的网络模拟仿真器。它是用C++和OTCL两种语言完成。C++语言编写协议执行模块，OTCL语言编写模拟任务。仿真的业务场景是:50个移动节点，10/20对通信连接(所有通信模式都是点对点的，即peer to peer)，以固定码率(CBR，constants bit rate)为业务源(产生UDP业务)，每秒钟发送2个分组(每个数据包512B)。节点运动场景是:每个移动节点在1000 m×300 m的区域不停止的随机运动(random waypoint模型)，节点无线信号通信半径250 m，仿真时间300 s。仿真参数:radio frequency为2.4 GHz，channel bandwish 为 2 Mb/s，Mac protocol选取802.11。

仿真共使用了6种不同的节点最大运动速度:20/50/100/150/200/250 m/s，它反映了网络拓扑变化的频繁程度。每个数据点都是相同业务流模型，不同移动模型的5轮仿真结果的平均值，用xgraph工具绘制仿真结果图。AODV、AOMDV和AODVUU在10对连接和20对连接下的平均端到端时延、分组投递率、路由发现频率和归一化路由开销，如图7～图10所示。

由图7可以看出，随着节点移动性的增大，路由失效次数增多，各协议平均端到端时延整体呈现增加趋势。AODV-UU通过减小分组投递次数和路由失效时间，大大降低了平均端到端时延。

由图8可以看出，随着节点移动性增大，路由失效次数增多，各协议的路由发现频率整体呈增大趋势，AOMDV在一次路由发现过程中可以找到多条链路独立路由作为备份路由，大大降低了路由发现频率。而相同连接对数条件下，AODV-UU的路由发现频率低于AODV。

由图9可以看出，随着节点移动性增大，各协议归一化路由开销整体呈现增大趋势。当连接对数=10，AODV-UU归一化路由开销最低。当连接对数=20，AOMDV归一化路由开销最低。当连接对数=10时，随着节点移动性增大，AOMDV的多径路由大量失效，同时，多径机制的路由控制包更大，产生的路由响应RREP更多，计算多径有效性的开销也更大，直接导致AOMDV的归一化路由开销偏大。当连接对数=20时，由于隐终端和暴露终端的问题，网络中的碰撞和拥塞急剧增多，AOMDV的多径机制，一定程度上缓解了信号间的相互干扰，从而获得了较低的归一化路由开销[5]。

由图10可以看出，随着节点移动性增大，各协议分组投递率整体呈现减小趋势。相同连接对数条件下，AODV的分组投递率最高，AODV-UU的分组投递率略低于AODV。随着节点移动性增大，AOMDV的多径路由大量失效，造成分组投递率急剧下降，已经难以接受[5]。

综上所述，AODV-UU的整体性能优于AODV和AOMDV，尤其是在节点高速运动的情况下。因此，AODV-UU对于在高速机动平台间建立动态、健壮和高性能的无线自组织网络具有一定的应用价值。

为了降低AODV-UU的路由发现频率和归一化路由开销，可以借鉴AOMDV，在AODV-UU中引入多径路由机制。

3 结语

Ad Hoc网络技术因其无需架设网络设施、可快速展开和抗毁性强等特点，在未来军用数据链领域的应用前景非常广阔。路由协议是Ad Hoc网络技术的核心。而按需距离矢量路由(AODV)因其优越的性能，逐步成为研究热点。通过对AODV、AOMDV和AODV-UU路由协议的仿真结果进行比较，说明了AODV-UU路由协议性能的优越性，对AODVUU进行多径改进是笔者今后研究的方向。

[1]郑少仁，王海涛，赵志峰，等.Ad Hoc网络技术[M].第1版.北京:人民邮电出版社，2005.

[2]TONY SKINNER.DARPA Successfully Demonstrates Tactical Targeting Network Technology[J].Jane's Defence Weekly，2005，42(44):2.

[3]DARPA.Tactical Targeting Networked Technology(TTNT)Industry Day Sol[EB/OL](2000-10-27)[2007-05-10].http://www.darpa.mil/baa/TTNT-ID-00.htm.

[4]MUHAMMAD ASIM MUBARIK，SHOAB AHMAD KHAN，SYED AYAD HASAN et al.Implementation of Geocast Enhanced AODV-UU in Linux Testbed[C]//2009 Eigth IEEE/ACIS International Conference on Computer and Information Science.Shanghai:IEEE Computer Society，2009:803-807.

[5]GOWRISHANKAR S，SUBIRKUMARSARKAR，G.BASAVARAJU T.Performance Analysis of AODV，AODVUU，AOMDV and RAODV over IEEE 802.15.4 in Wireless Sensor Networks[C]//20092nd IEEE International Conference on Digital Object Identifier，Beijing，2009:59-63.