一种改进的AODV路由协议的实现与仿真

周德荣， 夏 龄， 田关伟， 舒 涛

(四川民族学院 网络信息中心，四川 康定 626001)

0 引 言

在网络协议研究和开发时，验证网络协议的正确性和测试协议性能工作通过实际的硬件实验系统完成非常困难[1]。网络仿真器是进行网络研究重要的工具,NS2是其中比较常用的软件之一。面向对象的网络仿真器(Network Simmlator, Version 2, NS2)是由美国加州大学伯克利分校开发的开放源代码网络仿真软件，它是面向对象的网络仿真器,自身有一个虚拟时钟,所有的仿真都是由离散事件驱动[2]。NS2常用于协议和算法的开发及评估。Ad hoc网络是一种特殊的在不借助任何中间网络设备的情况下，可在有限范围内实现多个移动终端临时互联互通的网络，它具有无中心、自织组、多跳路由、独立组网、结点移动等特点[3-4]。路由协议是Ad hoc网络的重要组成部分，优秀的路由协议是网络性能的可靠保证。传统的路由协议不能满足Ad hoc网络的要求，根据其特点设计出了表驱动路由协议DSDV、WRP和按需路由协议DSR、AODV和TORA等。AODV路由协议具有一定优势，但也存在一定缺点，本文提出一种改进的AODV路由协议，分析了改进后的AODV协议在NS2中的实现和仿真。

1 NS2的基本结构

NS2是一种离散事件驱动的网络模拟器[5]，它包含仿真事件调度器、网络组件对象库以及网络构建模型库等。事件调度器计算仿真时间，激活事件队列中的当前事件，执行一些相关的事件。网络组件通过传递分组来相互通信，所有需要花费仿真时间来处理分组的网络组件都必须要使用事件调度器。NS2中的网络构件一般由相互关联的两个类来实现，一个是C++类，一个在OTCL类，C++类是算法和协议的具体实现。OTCL对象是用户接口对象，主要是建立OTCL对象、设置属性、通过事件调度器调度网络模拟事的发生。通过编写Tcl模拟脚本，使用NS2进行仿真产生Trace文件，通过NAM模块对仿真过程进行动画演示，通过Xgraph进行仿真结果图形绘制,NS2的基本结构如图1所示。

NS2(NS2的allinone包)由多个开源模块组成[6]，所有模块均包含源代码。NS2网络仿真器安装后的目录结构如图2所示，NS2安装后生成的目录与模块是相互对应的,即某个模块包含的内容放在同名的目录下。目录结构中最重要的是ns2-allinone-2.34/ns-2.34,NS2中对网络协议、算法实现的C++源代码主要位于ns-2.34目录,OTCL源码主要位于ns-2.34/tcl/lib目录。NS2中实现新协议、新算法要编写新的C++和OTCL代码,同时修改ns-2目录下的相关代码,然后重新编译连接到NS2核心模块即可。

2 AODV协议及其不足

AODV协议[7]是一种综合了DSR和DSDV各自优点改进而来的按需距离矢量路由协议。AODV路由协议包括路由发现和路由维护两种机制[8]。当源结点与目的结点进行通信时，源结点通过查找路由表是否有到目的结点的路由，有则直接发送，若没有源结点就通过发送RREQ路由请求分组发起路由寻找，中间结点收到RREQ路由请求分组后对比序列号，如果之前收到过该分组就丢弃。反之，从路由表找到到目的结点的路由，目的结点收到RREQ后向源结点发送路由应答消息RREP，建立一条源结点到目的结点的路径。AODV路由协议主要通过本地修复和源结点重建路由两种方式实现路由维护。AODV路由协议通过周期性广播HELLO报文来检测链路状态，如果规定时间内，结点未收到邻居结点的“HELLO”响应报文，就判断该链路已经断开，此时启动本地修复机制，若本地修复失败，删除缓存中源结点发送过来的数据包，发送RRER错误分组给源结点，源结点重新发起路由发现过程。

AODV路由协议有很多优点，同时也存在路由表中仅维护一条到指定的目的结点的路由、仅适用于双向传输信道的网络环境、采用了超时删除路由的机制，即使路由未失效，在超过时限后也将被删除等缺点[9]。在拓扑变化频繁的网络中，AODV协议中每个源结点只维护一条到指定目的结点的路由这个缺点尤为突出。如图3所示网络拓扑,结点n0要向结点n4发送数据，结点n0会创建一个路由请求包RREQ,将其广播给所有邻居结点，如果结点n1收到来自结点n0的RREQ,则建立到结点n0的逆向路由。如果结点n1没有到n4的路由，则将该RREQ重新广播给自身的其他邻居。所有邻居结点均会转发RREQ，直到有自身到结点n4的有效路由或直接邻接结点n4。当RREQ达到结点n5后，n5发现有一条到n4的路由，且其序号不小于RREQ中的序号，则会构造一个路由响应包RREP并沿逆向路由单播给n0，在n0结点中形成n0-n1-n7-n6-n5-n4路由信息。同理，当RREQ达到结点n3后，还会形成n0-n1-n2-n3-n4路由。结点n0根据目的结点序列号及到目的结点的跳数选择n0-n1-n7-n6-n5-n4作为最佳路由,n0-n1-n2-n3-n4将被丢弃。若结点n0通过最佳路由与结点n4通信时,当结点n1得知到结点n7的路由断开时,结点n0将重新广播到结点n4的路由请求包RREQ,最终会再次收到包含路由n0-n1-n2-n3-n4的路由响应包RREP。

3 AODV协议改进及实现

3.1 AODV协议改进思想

针对上述AODV协议的缺点，提出AODV协议的改进方法是每个源结点增加一条到指定目的结点的备份路由，形成源结点到目的结点主备两条路由。当主路由失效时,使用备份路由发送数据, 只有当备用路由也失效时才重新发起路由发现过程。协议改进后路由表中主备路由的建立流程图4所示，选择最优路由原则是路由序列号较大或跳数较小。

协议改进后,采用图3所示网络拓扑，如果结点n0与结点n4需要通信，但结点n0的路由表中没有到结点n4的有效路由,结点n0则广播一个RREQ分组。路由建立完后，结点n0将先后收到包含n0-n1-n2-n3-n4和n0-n1-n7-n6-n5的路由RREP分组，结点n0收到的两条路由以主备方式保存于自身的路由表，若结点n0与结点n4通信时,结点n1发现与结点n7路由断开,路由断裂处理的同时,会立即查找是否有本结点至目的结点的备份路由,若有,则将收到的数据包通过备份路由发送至目的结点。只有当主路由与备份路由都失效时,n0再次重新发起路由发现过程。

3.2 改进的AODV协议实现

NS2 2.34中,AODV路由协议主要由协议实体、路由表、定时器、日志记录器、路由缓存队列等组件构成。AODV路由协议源代码位于安装目录下的ns-2.34/aodv目录，协议由aodv_packet.h,aodv.h,aodv.cc,aodv_rqueue.h,aodv_rqueue.cc,aodv_rtable.h,aodv_rtable.cc及aodv_logs.cc文件构成，协议改进以AODV为基础实现。

3.2.1改进的AODV协议核心代码实现

对原有的路由表进行扩充实现主路由与备份路由,做法是通过修改aodv_rtable.h文件中的aodv_rt_entry类声明部分，在其中添加变量rt_priority作为标志位，aodv_rt_entry类构造函数将rt_priority初始化为0，0表示主路由,1表示备份路由。aodv_rtable类中添加rt_addbak(nsaddr_t id)和rt_lookupbak(nsaddr_t id) 两个函数，用于实现备份路由添加及查找功能。修改aodv.cc中的recvReply(Packet*P)函数，实现源结点可根据选择序列号最大以及跳数最小的两条路由作为主路由与备份路由的功能。同时，对aodv.cc中rt_ll_failed(Packet*P)函数中的本地修复机制进行修改[10-11],完成当链路层发现主路由失效时能够使用备份路由来传输数据。部分关键代码实现如下：

3.2.2NS2中改进的AODV协议实现

NS2使用分裂对象模型，协议开发从C++和Tcl两个类入手。以AODV协议源代码为基础将改进后的协议取名AODVN,将协议源代码存于ns-2.34/aodvn目录中，主要由定义计时器和路由代理的aodvn.h文件，实现所有定时器、路由代理和Tcl链接的文件的aodvn.cc文件，声明aodvn路由协议需要在无线自组网结点交换数据包的aodvn_packet.h文件，声明路由表的aodvn_rtable.h文件，路由表实现的aodvn_rtable.cc文件，队列声明及实现的aodvn＿queue.h和aodvn＿queue.cc等文件组成。

(1) 声明分组类型。在common/packet.h把PT＿AODVN添加到枚举类型值列表中，为新的分组类型在p＿info类中定义名称name＿[PT＿AODVN]= "aodvn"。

(2) 实现跟踪支持。要记录分组信息，在Trace/cmu-trace.h、Trace/cmu-trace.cc文件中的CMUTrace类添加并实现void format_aodvn()函数，修改trace/cmu-trace.cc文件中的format()函数添加case PT＿AODVN实现能够调用void format_aodvn()函数。

(3) 修改OTCL库文件。tcl/lib/ns-packet.tcl文件中添加协议名AODVN实现协议分组类型； Tcl/lib/ns-default.tcl文件中添加Agent/AODVN set accessible＿var＿ true绑定属性的默认值；Queue/priqueue.cc文件中添加case PT_AODVN实现队列对协议的支持；tcl/lib/ns-lib.tcl文件中新建一个使用AODVN路由协议的无线结点过程。

(4) 修改ns-2.34/Makefile文件增加对新类的编译。文件放在ns-2.34/aodvn目录下，修改Makefile文件里OBJ_CC变量，增加aodvn/aodvn_logs.o aodvn/aodvn.o aodvn/aodvn_rtable.o aodvn/aodvn_rqueue.o实现改进协议的编译、连接到NS2。

4 仿真结果与分析

仿真网络由50个移动结点构成,各结点随机分布在1 200～400 m的平面矩形区域内, 结点的无线传输范围为300 m,随机以均匀分布最大20 m/s的速度向任意方向移动，结点间的最大连接数为30，20个源结点，每秒发送4个CBR包,每个CBR包的大小为512B,Mac层协议采用IEEE802.11，模拟时间为900 s,不同运动场景中,结点到达目的地后的停留时间分别为0，30，60，120，300，600，900 s，结点停留时间越短,网络拓扑变化越频繁。具体仿真参数如表1所示。

根据仿真参数使用NS2中的传输产生器(cbrgen)生成传输模型文件，用结点移动产生器(setdest)生成结点暂停时间不同，结点个数、结点运动的最大速度、结点运动区域大小、场景持续时间等参数完全相同的运动场景文件[12, 13]。编写TCL脚本,使用AODV协议、AODVN协议分别载入规定的场景文件进行仿真,通过awk脚本对仿真产生Trace文件进行处理，分别提取两种协议的分组投递率、端到端平均时延、归一化路由开销以及路由发现频率等网络性能数据[14]，最后绘制协议仿真图。

表1 主要仿真参数

仿真中分别使用了0、30、60、120、300、600和900 s的暂停时间，暂停时间越小，结点的移动性越强，网络拓扑变化越频繁。每个暂停时间数据点仿真时采用相同的业务流模型和不同移动模型。AODV和AODVN两种协议的分组投递率、端到端的平均时延、归一化的路由开销和路由发现频率的仿真结果如图5～图8所示。

图5 分组投递率仿真结果

从图5看出，当暂停时间较小时,由于结点移动频繁使得路由失效频发，AODV和AODVN的分组投递率较低，由于暂停时间的增加，AODV和AODVN的分组投递率逐渐提高，AODVN比AODV有一定提高。从图6看出,随着结点暂停时间的增加,AODV和AODVN的端到端平均时延均呈现下降趋势，与AODV比较,AODVN大幅降低了端到端的平均时延,特别是网络拓扑变化较慢时,降低的幅度尤为明显。由图7和图8看出,AODVN与AODV相比较,归一化的路由开销以及路由发现频率均有大大降低，这也表明AODVN协议当主路由失效时,备份路由能及时起到原来主路由的作用,减少了路由发现过程的次数,降低路由发现频率，网络性能得到一定提高。

图6 端到端的平均延时仿真结果

图7 归一化的路由开销仿真结果

图8 路由发现频率仿真结果

5 结 语

网络仿真是检验网络协议和算法的正确性和有效性,以及测试网络性能必不可少的有效方法[15]。本文通过提出一种改进的AODV协议,详述改进的AODV协议在NS2中的实现过程,对新协议进行测试和验证，仿真结果验证了新协议的有效性。采用NS2实现一些新协议和算法进行网络仿真研究大大提高了效率、降低了成本, 具有很好的灵活性。

[1] 夏 利，张 鹏，杨 宏，等. NS2中单播动态路由机制的剖析与扩展[J]. 微计算机应用, 2006, 27(3): 275-277.

XIA Li, ZHANG Peng, YANG Hong,etal. The Analyses and Extending of Unicast Dynamic Routhing in NS2[J]. Microcomputer Applications, 2006, 27(3): 275-277.

[2] 王 辉. NS2网络模拟器的原理和应用[M]. 西安: 西北工业大学出版社, 2008.

[3] 陈林星，曾 曦，曹 毅，编著. 移动Ad Hoc网络自组织分组无线网络技术[M]. 北京: 电子工业出版社, 2006.

[4] 周杰英，陈子凡，雷 淳，等. 无线网状网组建及应用[J]. 实验室研究与探索, 2011(12): 56-59.

ZHOU Jie-ying, CHEN Zi-fan, LEI Chun,etal. Wireless Mesh Network Construction and Application[J]. Research and Exploration in Laboratory, 2011(12): 56-59.

[5] Ekram H., Issariyakul T. Introduction to Network Simulator NS2[M]. Springer, 2009.

[6] Fall Kevin, Varadhan Kannan. The ns Manual (formerly ns Notes and Documentation)[Z]. The VINT Project, 2008.

[7] 童 燕，李俭兵. NS2的Ad hoc网络AODV协议的仿真[J]. 数字通信, 2009(3): 50-53.

TONG Yan, LI Jian-bing. Simulation of AODV routing protocol in Ad hoc networks based on NS2[J]. Digital Communication, 2009(3): 50-53.

[8] 庄春梅，陆建德. AODV协议分析及过期路由维护机制改进[J]. 计算机技术与发展, 2009(7): 44-47.

ZHUANG Chun-mei, LU Jian-de. Analysis and Improvement of Expired Routing Management Mechanism of AODV Routing Protocol[J]. Computer Technology and Development, 2009(7): 44-47.

[9] 张登银，王军玲. 改进的AODV路由协议性能比较研究[J]. 计算机技术与发展, 2010(1): 67-70.

ZHANG Deng-yin, WANG Jun-ling. Research on Performance Comparison among Improved AODV Routing Protocols[J]. Computer Technology and Development, 2010(1): 67-70.

[10] 陈模科，陈 勤，张 旻. 基于hello消息的AODV路由协议的改进[J]. 计算机仿真, 2009(8): 143-146.

CHEN Mo-ke, CHEN Qin, ZHANG Min. The Improve of AODV Based on HelloMessage[J]. Computer Simulation, 2009(08): 143-146.

[11] 丁绪星，吴 青，谢方方. AODV路由协议的本地修复算法[J]. 计算机工程, 2010(6): 126-127.

DING Xu-xing, Qing Wu, Fang-Fang Xie. Local Repair Algorithm for AODV Routing Protocol[J]. Computer Engineering. 2010(06): 126-127.

[12] 赵新伟，郑洪飞. Ad Hoc网络路由协议分析与仿真[J]. 计算机安全, 2011(7): 40-43.

ZHAO Xin-wei, ZHENG Hong-fei. Analysis and Simulation on Routing Protocols of Ad Hoc Networks[J]. Computer Security, 2011(7): 40-43.

[13] 何增颖. 基于NS2的Ad Hoc网络路由协议分析实验[J]. 实验室研究与探索, 2010(5): 71-74.

ZHAO Xin-wei, ZHENG Hong-fei. Analysis Experiment of Ad Hoc Network Routing Protocol Based on NS2[J]. Research and Exploration in Laboratory, 2010(05): 71-74.

[14] 果 然，谭学治，徐贵森. 一种基于NS2的多信道网络模型的建立和性能检测[J]. 科学技术与工程, 2009(17): 4950-4954.

GUO Ran, TAN Xue-zhi, XU Gui-sen. Construction and Performance Test of a Multi-channel Network Model Based on NS2[J]. Science Technology and Engineering, 2009(17): 4950-4954.

[15] 周德荣，龄 夏，舒 涛，等. NS2网络协议虚拟仿真实验平台研究[J]. 实验技术与管理, 2014, 31(3): 87-90.

ZHOU De-rong, XIA Ling, SHU Tao,etal. Protocol, Research of Virtual Simulation[J]. Experimental Technology and Management. 2014, 31(3): 87-90.