摘要:移动自组织网络(MobileAdHocNetworks, MANET)是由一组自治通信节点组成的集合,当前对其路由协议的研究最为集中。
用户所关心的是哪一种路由协议才能使AdHoc网络应用性能最好。本文基于QualNet这种功能强大的动态网络仿真器比较了AODV、DSR、FSR这3种AdHoc网络路由协议的性能,包括不同网络负载情况下的路由协议收敛速度、分组发送成功率、网络吞吐量、端对端延时和抖动等参数指标,为构建运行多媒体通信业务的AdHoc网络提供了指导和借鉴。
要害词:网络仿真器,移动自组织网络,按需距离矢量,动态源路由,鱼眼,路由协议
1、引言
AdHoc网络是由一组自治通信节点组成的集合[1]。节点可以根据需要随时组网,在两个节点无法直接通信(如通信距离不够或有访问限制)的情况下,其它节点可以中继。
AdHoc网络始于美国军方上个世纪70年代开始的无线分组网项目[1]。近年来,随着人们对于个人通信需求的增长,对AdHoc网络的研究逐渐升温,IETF专门为此组成了MANET工作组。AdHoc网络研 究主要集中于传输方式(包括物理层和MAC子层)、组网方式(路由协议)和高层应用上。其中以路由协议的研究最为集中,提出了各种Ad Hoc网络的路由协议[2][3][4][5]。但是,各种路由协议的研究都是以某一特定网络应用场景为前提的。组网工程人员和最终用户关心的是采用哪一种路由协议才能够使得自己的网络应用效果最好。为此,需要将现有的多种Ad Hoc路由协议进行对比,找到满足需要的性能指标对应的路由协议。
国内外研究人员已经展开了对此问题的探讨,JoshBroch等人利用ns-2网络仿真器对AODV、DSDV、DSR和TORA等AdHoc路由协议进行了仿真实验[6],得到了不同RandomWaypoint暂停时间下的路由开销和分组发送成功率。Azzedine Boukerche基于ns-2得到了不同暂停时间下AODV、DSR和CBRP的网络吞吐量和平均延时[7]。Samba Sesay等人比较了不同暂停时间下DSDV、TORA、DSR、AODV路由协议的路由收敛时间、平均延时和吞吐量[8]。
本文借助于QualNet网络仿真器的强大功能,比较了当前AdHoc网络中AODV、DSR和Fisheye这3种常见路由协议的性能参数指标,包括不同网络负载情况下的路由协议收敛速度、分组发送成功率、网络吞吐量、端对端延时和端对端抖动,为运行多媒体通信业务的AdHoc网络构建提供了指导和借鉴。
本文组织如下:第2部分综述了当前AdHoc的主流路由协议;第3部分介绍了QualNet网络仿真器的强大功能;第4部分对AODV、DSR和Fisheye这3种AdHoc路由协议进行了仿真性能评估,给出了仿真结果和图表;最后进行了总结。
2、AdHoc路由协议
根据路由触发原理,目前的路由协议大致可以分为先验式路由协议、反应式路由协议和混合式路由协议3种。
先验式(PRo-active)路由协议又称表驱动路由协议,每个节点维护一张包含到达节点的路由信息的路由表,并根据网络拓扑的变化随时更新路由表,所以路由表可以准确地反映网络的拓扑结构;源节点一旦要发送报文,可以立即获得到达目的节点的路由,这类的路由协议通常是通过修改现有的有线路由协议来适应AdHoc无线网络要求,如FSR(FisheyeState Routing)路由协议。
反应式(Re-active)路由协议又称按需路由,是一种当需要时才查找路由的路由选择方式。节点不需要维护及时准确的路由信息,当需要发送数据时才发起路由查找过程。与先验式路由协议相比,反应式路由协议的开销小,但是数据报传送的时延较大,不适合于实时性的应用。AODV(AdHocOn Demand Distance Vector)和DSR (Dynamic Source Routing)都属于反应式路由。
我们选取了AODV、DSR和FSR这三种常见AdHoc路由协议进行QualNet仿真实验比较。
DSR使用源节点路由而非逐跳路由,每一个寻路分组在其头部都携带了完整的途经节点的按顺序列表。运行DSR的节点使用一个缓存用来存放已知目的节点的所有路由。需要发送分组时,节点首先查询路由表。假如路由表包含目的节点和所需路由,则使用该路由;否则,就广播路由请求分组进行寻路。当路由请求分组在网络中传输时,其到达的每一个节点都检查自己的路由表看它们是否有到达目的节点的路由。假如这些节点的路由表中有到达目的节点的路由,就应答该请求并提交这条路由。当路由请求分组到达了目的节点时,中继接点就查看路由请求分组经过的这条路径是否在高速缓冲区中。假如高速缓冲区中没有这条路由,就把这个目的节点和路由加到自己的高速缓冲区中以备将来使用。
DSR的优点在于中间节点无需维持更新的路由信息为它们的转发分组寻路,因为分组本身已经包含了所有的路由决定。事实上,这个协议和按需相结合消除了周期路由广播和其他协议中所出现的邻节点的检测分组;再者,它不依靠于其它节点的保持有效的消息,这就减少了带宽的占用和所需的能量。而且,由于节点的高速缓冲区储存了到目的节点的多条路由,所以假如当一条路由断开时,节点可以在高速缓冲区中找到预备的路由。缺点是在DSR分组较大,这就使得DSR的网络参数相对的比较小,也避免了按比例放大到大的网络中所存在的一些问题。
AODV是基于距离矢量的算法。所不同的是,AODV只保持需要的路由,而不需维持通信过程中未激活的目的节点的路由。
当源节点S需要到某个目的节点D的路由时,他就广播一个路由请求消息给他的邻节点,其中还包含了那个目的节点的最终所知道的序列号。路由请求消息以一种控制的方式在网络中进行泛洪直到它到达了一个节点,并且这个节点知道到目的节点的路由。每一个转发路由请求的节点就为自身创建一条到节点S的反向路由。
当路由请求分组到达有路由到D的节点时,这个节点就产生一个包含到达D所必需的跳数和此节点最近所知道的D的路由应答分组的序列号。每一个参与转发应答分组给产生路由请求原始节点的转发节点都建立一条到D的转发路由。从S到D路由上的每个节点的链路状态是逐跳状态。也就是说,每一个节点仅仅是记住下一跳而不是像源路由那样记住整个路由。除此之外,AODV为了维护路由还周期性地发送Hello分组。
AODV的优点是可以利用多播的优势,这正是所有其它路由协议所缺少的;而缺点则是依靠于对称性的链路,而不能处理非对称性链路的网络。
FSR是一个先验式(表驱动)路由协议。它使用了鱼眼技术,在不同鱼眼域中的节点以不同的频率(这个频率是由节点距离决定的)只向邻居节点广播链路更新信息,这能够大大减少链路状态更新信息,从而降低了泛洪的开销。通过节点之间相互交换链路状态消息,每个FSR路由器都能获知网络全局的拓扑信息。根据这些最新的拓扑信息,FSR为每个目的节点计算最短路径。由于链路更新频率由距离决定,因此对于域内的节点路由都是精确的,而对于域外的节点,离目的节点越远,路由的精确度便越低,这是因为距离较近的更新较快,较远的更新较慢。但不会像按需路由那样需要花时间去寻找路由,因此能维持较低的延时。而且随着距离目的节点越来越近,路由信息越来越精确,正好弥补了路由的不精确性。在移动网络中,逐渐精确的路由减小了节点移动对路由精确度的影响。当链路崩溃时,FSR不会发出任何控制信息,而且也不包含在下一个更新信息中,而是简单地删除邻居列表和拓扑结构表中的信息,因此适合于拓扑高度变化的网络环境。目的序列号的使用不仅使得FSR能使用最新的链路状态信息去维护拓扑结构,而且还避免了环形路由的形成,因此较适合高移动性的无线网络。
3、QualNet仿真器
QualNet是美国ScalableNetworksTechnologies公司的产品,前身是GloMoSim,根源于美国国防部高级研究计划署(DARPA)的全球移动通信计划,主要对无线移动通信网络进行了优化处理,从仿真速度上得到了很大的提升,同时通过对无线信道和射频技术的建模也保证了较高的仿真精度。QualNet基于已经过验证的PARSEC并行仿真内核。每个结点都独立进行运算,这也和现实相符合。答应用户在真正的并行仿真环境当中优化并行仿真性能。对小规模同种复杂度的网络模型仿真,QualNet仿真速度是其它仿真器的几倍,对于大规模网络,QualNet仿真速度是其它仿真器的几十倍,假如QualNet采用并行仿真机制,能达到比其它仿真器快千倍的速度。
QualNet的协议模块更加独立,更加模块化,可以方便屏蔽、增加、删除某些协议模块。支持TCP/ip协议栈的标准层间接口,用户无需自己开发这种类型(绝大多数的协议都满足,包括大量军方数据通信联网设备)的层间接口;同时支持非标准协议栈的开发,即跨层交互(CrossLayerInteraction)。QualNet具有Batch功能,一次可以选择某些参数的不同取值,只需执行一次,就可以得到同一仿真场景下的不同协议或者同一参数的不同取值情况下的网络性能,进行比较。QualNet仿真结果的数据统计和分析包支持side-by-side参数逐一比较、直方图和基于文本的统计存储。基于仿真时刻的数据记录由Animator存储。基于文本的统计存储支持后续的各种工具进行数据处理。
QualNet的协议代码,一般来说只有头文件(.h文件)和对应的实现文件(.cpp文件),为通用结构,而且查看其代码干净利落。用户假如想要开发协议的硬件实现,就可以马上使用QualNet提供的源代码,稍加改动,就可以整段整段地采用源代码,大大缩短了原型系统的开发周期。
综上,我们选择QualNet作为仿真工具的理由如下:
(1)包含大量预设的模型、协议和算法。
(2)学术界广泛接受。
(3)扩展性好。
(4)相当好的高度模块化设计。
(5)可用性、可修改性、可扩展性。
(6)图形和算术工具便于实验建立、监视和后续处理数据。
(7)并行分布式仿真实现。
4、AdHoc路由协议仿真
遵循一般的网络仿真实验流程,在QualNet当中进行网络仿真相当方便,首先设置仿真网络的场景以及网络参数,然后配置业务流量,就可以开始运行仿真实验,得到仿真结果以后就可以进行后续的处理,得到所需的参数图表。
我们的实验目的就是要查看在不同的网络负载和不同的网络拓扑变化频率下AODV、DSR和FSR这三种路由协议的性能,为此,我们选择了如下的仿真场景进行实验设置:
表1 仿真实验设置
一般情况下,进行如上的实验,需要进行5种发送间隔,7种暂停时间,3种路由协议共5*7*3=105次实验,但是在QualNet当中,只需要进行一次设置就可以完成,而且仿真速度相当快,我们的机器配置为主频P4-3.0GHz,512MB内存,WindowsXP操作系统,这105次实验总共花费了7分多钟的时间,平均每个实验4.2秒钟。QualNet的这个良好的用户接口设置给我们进行参数性能的改进和比较提供了极大的方便,能够最大限度地节省我们的仿真等待时间,并直接得到比较的结果图表。与同类仿真器相比,QualNet的仿真速度和便捷性首屈一指。
5、仿真结果及讨论
5.1仿真结果
我们得到了上述105个仿真实验的结果,利用QualNet的结果导出机制,我们将仿真实验结果在Excel中进行了处理,得到了如下的一系列网络性能参数的比较图表,其中的每一个数据点都是对应的路由协议在RandomWaypoint移动模型的7种暂停时间(0,1,2, 5, 10, 15, 20S)下仿真结果的算术平均值。
需要说明的是,为了验证路由协议在不同网络负载下的表现性能,我们选取了不同的业务流量发送间隔来代表不同的网络负载。发送间隔越小,即发送频率越高,网络流量负载就越大,反之就越小。
5.2结果讨论
(1)分组发送成功率
从图1可以看出,三种路由协议的分组发送成功率都是随着网络负载的增大而减小。在网络轻载情况下,AODV的分组发送成功率最高,FSR的最低;在重载情况下,FSR的分组发送成功率要优于AODV和DSR。
图1 分组发送成功率的比较
(2)接收到第一个分组的时刻
接收到第一个分组的时刻表明路由表收敛速度的快慢。路由收敛速度是衡量路由协议性能的一个重要标志。
从图2可以看出,无论是网络轻载还是重载的情况下,DSR路由协议的路由表收敛速度均明显好于AODV和FSR。FSR的收敛速度最慢,DSR次之。
图2 接收到第1个分组时刻的比较
(3)吞吐量
从图3可以明显看出,三种路由协议的吞吐量相差较大,FSR的吞吐量最大,AODV次之,DSR最小。在网络重载情况下的吞吐量差别尤其明显。
图3 吞吐量的比较
(4)端对端延时和抖动
对于许多多媒体应用而言,不仅仅要求承载网络提供无差错的透明传输,还要满足用户对于多媒体应用的主观感受要求,如话音和视频的延时和抖动,这两个参数都要越小越好。
图4 端对端延时的比较
从图4、图5可以看出,不论是网络重载还是轻载情况下,FSR协议都能够保证较低的延时和抖动。DSR的表现就不尽人意了,延时达到了两秒钟以上,这对于实时多媒体通信而言是无法忍受的。
图5 端对端抖动的比较
6、将来的工作
基于QualNet网络仿真器,我们进行了一个在中规模AdHoc网络中AODV、DSR和FSR这三种路由协议的性能仿真比较,得到了分组发送成功率、路由收敛时间、吞吐量、端对端延时和抖动等网络性能参数指标的比较结果。
我们下一步还要仿真测试大规模AdHoc网络中包括FTP、VBR等业务流量下的AODV、DSR、FSR、OLSR、ZRP等多种路由协议的性能。(北京华仪盛科科技有限公司供稿)
参考文献:
[1]ImrichChalamtac,MarcoConti, Jennifer J.-N. Liu, Mobile ad hoc networking: imperatives and challenges, Ad Hoc Networks I (2003) 13-64.
[2]AdHocOnDemand Distance Vector (AODV) Routing (RFC 3561), IETF, July 2003.
[3]OptimizedLinkStateRouting Protocol (RFC 3626), IETF, October 2003.
[4]TheDynamicSourceRouting Protocol for Mobile Ad Hoc Networks (DSR), Internet Draft, IETF, 19 July 2004.
[5]DynamicMANETOn-demand(DYMO) Routing, Internet Draft, IETF, June 21, 2005.
[6]JoshBroch,DavidA. Maltz, David B. Johnson, Yih-Chun Hu, Jorjeta Jetcheva, A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols, MobiCom’98, ACM.
[7]AzzedineBoukerche,APerformance Comparison of Routing Protocols for Ad Hoc Networks, 2001 IEEE。
[8]SambaSesay,SimulationComparison of Four Wireless Ad hoc Routing Protocols, Information Technology Journal 3 (3): 219-226, 2004.