路由路由协议

第35卷第1期应用科技Vo.
l35,l.
12008年1月AppliedScienceandTechnologyJan.
2008文章编号:1009-671X(2008)01-0012-05典型AdHoc网络路由协议的仿真与分析魏凯,姜弢,李明(哈尔滨工程大学信息与通信工程学院,黑龙江哈尔滨150001)摘要:移动AdHoc网络是移动节点动态临时组建的自组织的网络,它不需要任何基础设施,相距较远的节点间的通信需要中间节点的转发.
目前已经实现了多种网络协议,目的序列距离矢量路由(DSDV)、源动态路由(DSR)、AdHoc按需距离矢量路由(AODV)等.
首先介绍了DSDV、DSR、AODV3种路由协议,并用NS2(网络模拟器)对它们的网络性能指标端到端时延、数据包传送率和路由开销性能进行了仿真,并对实验结果进行了分析说明.
关键词:AdHoc;路由协议;仿真,NS2中图分类号:TP391.
9文献标识码:ASimulationandanalysisofroutingprotocolsforAdHocnetworksWEIKa,iJIANGTao,LINGMing(CollegeofInformationandCommunicationEngineering,HarbinEngineeringUniversity,Harbin150001,China)Abstract:AdHocnetworkisasel-forganizednetworkwhichisformeddynamicallyandtemporarilybymobilenodeswithoutneedofanyinfrastructureorcentralizedadministration.
Untilnow,anumberofroutingprotocolshavebeenrealized,forexample,Destination-SequencedDistance-Vector(DSDV),DynamicSourceRouting(DSR),AdHocOn-DemandDistanceVectorRouting(AODV),andsoon.
Inthepaper,firstweintroducethesethreeproto-cols.
ThenthreeimportantperformanceindexesaresimulatedwithNS2:packetdeliveryrate,averageend-to-enddelayofdatapackets,normalizedroutingload.
Finallywegiveaninterpretationtosimulationresults.
Keywords:AdHoc;routingprotoco;lsimulation;NS2收稿日期:2007-06-27.
基金项目:黑龙江省自然科学基金资助项目(AF200611).
作者简介:魏凯(1981-),男,硕士研究生,主要研究方向:AdHoc网络,E-mai:lweika@ihrbeu.
edu.
cn.
随着网络技术和无线通信技术的融合,移动无线网络成为一门新兴的热门技术.
当前,移动无线网络可以分为2大类:需要固定基础设施支持的网络(如蜂窝系统、WLAN)和无需固定基础设施支持的AdHoc网络.
前者的移动节点通过被称为BS(basestation)或者AP(accesspoint)设施进行通信;后者也称为MANET(mobileAdHocnetwork),是一种由移动主机临时组建的、无中心、自组织、不需固定基础设施的网络.
移动主机具路由功能,用于发现并维护到其他节点的路由.
这种网络灵活、健壮、投资少,可以快速方便地应用于紧急情况、军事行动、灾难恢复等场合.
由于AdHoc网络的多跳共享广播特性,网络拓扑不断变化,使得传统的路由协议不再适用.
同时AdHoc网络协议还需要考虑无线环境的低带宽和高误码率特性,需要专门设计AdHoc网络的路由协议.
路由协议的研究成为当前AdHoc网络研究的核心问题.
1典型的AdHoc网络路由协议目前,已经提出了很多用于AdHoc网络的路由协议,其中IETF公布草案的有:AODV、TORA、TBRPF、DRS、OLSR、FSR、MAODV、LANMAR等,按照驱动模式的不同,可以分为表驱动路由协议(tabledrivenprotocols)和按需路由协议(source-initiatedon-demandprotocols).
1.
1表驱动路由表驱动路由协议也叫先应式路由,它试图维护网络中从各个节点到其他节点的最新路由信息;与何时需要路由,以及需要的路由的频次无关,每个节点维护一个或者多个路由表,当网络拓扑变化时,广播更新信息传遍整个网络,以维护一致的网络视图.
表驱动路由协议的一种典型协议是DSDV[1].
DSDV协议是在Bellman-Ford路由算法基础上进行改进设计的,它能保证无环路由.
在DSDV中,每个节点要维护它所能到达的所有目的节点的路由表,其中列出了所有可能到达的目的节点、到达目的节点的跳数、分配的序列号.
DSDV采用时间驱动和事件驱动结合控制路由表更新的传送,每个节点周期性地将路由更新信息传送给相邻节点;或者当其路由表发生变化时,也会将路由更新信息传给相邻节点.
为了减少控制信息的开销,DSDV把路由更新信息分为2类:一类称为完整路由更新(fulldump),包含了该节点的路由表中所有的路由信息;另一种称为增量路由更新(incremental),携带的是从上次完整路由更新以后改变的路由信息;由于需要周期性地更新消息,DSDV仍然产生很大的网络开销,并且开销是随着网络规模来增长的.
这种协议不适于大型网络,因为网络带宽的大部分将用在路由更新处理上有许多优势,在小型到中型的网络中,这种协议运行得比较好.
1.
2按需路由按需路由协议也叫反应式路由,只当源节点需要时才寻找路由.
当源节点需要通往目的节点的一条路径时,它将发起路由发现过程,当找到一条路径或者所有可能的路径都被检查过后,路由发现过程结束.
路径一经建立,它就被某个路由程序所维护,直到目的节点无法经由任何路径到达或者该路径不再需要.
DSR和AODV属于按需协议.
源路由协议[2](DSR)是最早采用按需思想的路由协议.
它使用了源路由的路由机制,每一个发送的数据包都在其头部包含了从源节点到目的节点的完整路由信息.
当某个源节点S产生一个新的分组需要传输到某个目的节点D的时候,源节点S就在该分组的分组头中添入一条源路由,从而给出沿着该条源路由转发该分组至目的节点D的多跳转发序列.
通常情况下,源节点通过搜索其自己的路由存储器(routecache)就能够找到一条合适的源路由,路由存储器用于存储以前获得的路由;但是如果源节点S在自己的路由存储器里没有找到以前获得的路由,源节点S将初始化一个路由寻找协议,动态地寻找一条新路由到达目的节点D.
路由发现是通过泛洪(flood)实现的.
节点S按照一个单独本地广播方式发送一个路由请求(routerequest),每个收到RREQ的节点重复广播,直到达到目的节点S或者路由存储器里含有到达目的节点S路由的节点,然后此节点将产生一个路由应答(routerequest)按照反路径回送到源节点S.
自此,源节点S通过RREQ建立一条到达目的节点的路径,路径也被储存,以备将来使用.
路由维护过程是:在使用源路由发送分组的时候,每个节点都需要证实数据分组能够通过本节点到达该条源路由下一跳节点的链.
如果路由损坏,上游节点将发送一个路由错误分组(RERR)通知源节点,源节点将从它的储存中删除这条路由,初始化一个新的路由发现过程到达目的节点(如果仍然需要这条路由的话).
DSR路由协议中,路由寻找机制和维护机制完全是按需操作的,不存在某种周期性分组.
当所有节点的相互关系可以近似为静态,并且当前通信所需的所有路由已经全部被找到的时候,这种按需操作产生的开销数量成比例地下降,甚至最终为零.
AdHoc按需距离矢量路由协议[3](AODV)吸收了DSR协议按需特性,具有与之相类似的路由发现过程,不同之处是具有传统的路由表项,是DSDV的一种改进.
AODV通过按需产生路由减少了广播的次数,不像DSDV那样维护所有的路由.
它的路由发现过程是:节点发送信息时,先在路由表中查找路由,有则按照路由发送信息,没有则进行路由发现过程.
节点广播路由请求包(RREQ)发送给自己所有的邻节点,邻节点在接收到RREQ后,先在自己的路由表中查找是否有到目的节点的路由,如果有,则将路由信息写入RREP包(路由回复包)发给源节点;如果没有,再将RREQ转发给自己所有的邻节点.
依此类推,直到到达目的节点或是中间某个节点知道到达目的节点的路由.
路由维护过程是:如果中间节点移动,那么它的邻节点意识到#13#第1期魏凯,等:典型AdHoc网络路由协议的仿真与分析链路断开了,就会给其上游节点发送一个链路断开的通知,这样直到源节点,如果需要源,则重新启动路由发现过程.
因为DSR中每个包携带完整的路由信息,而在AODV中仅携带目的地址,这意味着AODV比DSR的路由开销要少.
并且DSR中路由回答包携带路由中每个节点的地址,而在AODV中路由回答包携带目的IP地址和序列号.
AODV的优点使它能适应高度动态的网络.
2NS2仿真实验NS2是一个离散型事件驱动的网络仿真软件[4-5],能够执行多种网络协议,提供多种数据源,实现多种队列算法等[6].
使用添加了CMU无线模块的NS2来进行本次实验.
仿真的步骤[6]是定义网络参数,生成仿真对象,生成仿真场景,包括运动场景和流量场景,仿真完成生成trace文件及nam动画演示,流程如图1所示.
图1仿真步骤流程图阐述节点的配置和场景的建立,仿真结果数据的处理可以使用多种程序语言进行,不再详述.
实验中使用一个node-config配置函数配置移动节点.
配置的选项包括:adhoc路由协议、协议栈、通道、拓扑、传输模型以及是否打开有线路由(如果需要有线-无线场景),是否打开各层的trace(router,mac,agent)等.
实验中使用的仿真参数见表1.
表1实验参数设定参数设定值信道类型Channel/WirelessChannel无线传播模型Propagation/TwoRayGround网络接口类型Phy/WirelessPhyMAC类型Mac/802_11接口队列类型Queue/DropTail/PriQueue链路层类型LL天线类型Antenna/OmniAntenna接口队列最大长度50移动节点个数50路由协议DSDV/DSR/AODV实验中仿真场景主要包括节点运动场景和网络流量场景[7].
运动场景主要说明网络的运行区域、节点数目、运行时间及怎样运动等.
流量场景主要说明一定时间内节点产生怎样的连接,以及以多大的速率发送等.
运动场景和流量场景除了可以手动编写脚本文件外,NS2也提供专门的场景生成工具,在~ns/indep-utils/cmu-scen-gen/setdest目录下.
命令如下:.
/setdest–n-s-P-p-m-M-t-x-y>/例如要产生8个节点的移动,范围是1000@1000,最小速度是5,最大速度是10,时间100s,移动类型是均匀分布,则可运行如下命令:.
/setdest–n8–suniform–m5–M10–t100–Puniform–pmedian–x1000–y1000用于产生流量的Tcl脚本cbrgen.
tcl位于~ns/indep-utils/cmu-scen-gen目录下.
命令为nscbrgen.
tcl[-typecbr|tcp][-nnnodes][-seedseed][-mcconnections][-raterate]例如,如下命令nscbrgen.
tcl–typetcp–nn20–seed1–mc4–rate10在20个节点中将产生4个随机的TCP连接,并且默认设置了TCP窗口的大小和包大小(cbrgen.
tcl里的缺省值).
实验中用到的场景参数见表2、3.
表2运动场景参数参数设定值节点数50移动范围/m500500节点最大运动速度m/s20节点最小速度0暂停时间/s0102040100仿真时间/s100表3流量场景参数参数设定值节点通信范围/m250带宽/MB2业务类型CBR仿真时间/s100最大连接数20发送速率/kbps8#14#应用科技第35卷参数设定值:节点通信范围250m,带宽2MB,业务类型CBR,仿真时间100s,最大连接数20,发送速率8kbps.
3仿真的性能指标及结果分析3.
1性能指标参数1)端到端时延:数据包从源节点到目的节点经历的时间.
包括路由寻找期间缓存时延、接口队列排队时延、MAC层重传时延、空中传播时延以及变换时间等所有可能时延之和.
可用下式计算:端到端平均时延=E(授受到数据包的时间-发送数据包的时间)发送的数据包个数.
2)数据包分组交付率:源节点应用层产生的数据包数目和目的节点应用层接收到的分组数目的比值.
该指标反应了协议适应网络变化的性能好坏和网络所能支持的最大吞吐量,它是路由协议完成性和正确性的指标.
可用下式计算:分组交付率=目的节点接收的数据包个数源节点发送的数据包个数.
3)标准化路由荷载:定义为每交付给目的节点一个数据分组所需要发送的路由分组的数量.
一个路由分组每当被传输一跳,则计算一次路由分组发送.
对于无线信道,该性能指标尤其重要.
用下式计算:标准路由荷载=发送和转发的路由包个数接收到的数据包个数.
3.
2实验结果及分析仿真结果如图2~4所示.
暂停时间/s图2分组交付率暂停时间/s图3平均端到端延迟暂停时间/s图4标准化路由荷载实验结果分析:分组交付率,如图2所示:移动性很弱的时候(如100s的暂停时间),3种协议DSDV、DSR、AODV表现得都很好,接近100%的分组交付率;但是当移动性变强的时候(对应暂停时间较小),反应式协议DSR、AODV比先应式路由协议DSDV的表现要好,仍能维持较高的分组交付率,达到85%以上,而DSDV恶化到70%左右.
分组交付率的结果符合理论的预期,相同的移动场景中,大多数情况下反应式路由协议的分组到达率比先应式路由协议高,这是由它们的路由机制不同决定的.
因为DSDV为目的节点,只维护一个路由表项,在高速移动环境下,路由表项可能经常失效,而一旦失效,在短时间内无法建立有效路由,以致产生分组丢失,且节点移动速度越快,分组丢失越严重,DSDV不能适应高速移动的网络.
DSR、AODV反应式路由因为本来就是按需操作的,对节点的移动相比DSDV就变得不十分敏感了.
端到端延迟,如图3所示:在延迟方面DSDV的总体表现也不如DSR和AODV,反应式路由DSR和AODV一直能维持相对稳定的延迟,DSDV延迟变化很大.
在速度较小的情况下,由于DSDV直接查表获取路由,反应式路由DSR、AODV有数据发送时才寻找可用的路由,所以相比反应式路由具有低的延迟,如图中暂停时间较大时,DSDV延迟最小;但在高速环境中,链路失效启动的更新将大大增加处理时间,也浪费了系统资源,反而导致DSDV延迟比DSR、AODV的延迟还要大.
DSR、AODV这方面与DSDV不同,不管节点移动的快和慢,都是按照路由发现、路由维护的过程操作的,所以能保持一个总体上的比较稳定的延迟时间.
(下转第24页)#15#第1期魏凯,等:典型AdHoc网络路由协议的仿真与分析参考文献:[1]田捷,杨鑫.
生物特征识别技术理论与应用[M].
北京:电子工业出版社,2005.
[2]ECKHORNR,REIBOECKHJ,ARNDTM,eta.
lAneuralnetworksforfeaturelinkingviasynchronousactivity:resultsfromcatvisualcortexandsimulations[C].
//InModelsofBrainFunction.
Cambrige,UK,1989.
[3]JOHNSONJL.
Pulse-coupledneuralnets:translation,ro-tation,scaledistortionandintensitysignalinvarianceforim-ages[J].
AppliedOptics,1994,33(26):6239-6253.
[4]石美红.
一种新的纹理图像特征提取的方法[J].
纺织高校基础科学学报,2002,15(3):189-194.
[5]LINDBLADT,KINSERJM.
Imageprocessingusingpulse-coupledneuralnetworks[J].
IEEETransonNeuralNe-tworks1999:10(3):539-544.
[6]石美红,张军英,李永刚.
基于差别特征的纹理图像识别研究[J].
计算机应用,2004,24(1):66-69.
[7]SMITHWS.
Thescientistandengineer.
sguidetodigitalsignalprocessing[M].
SanDiego:CaliforniaTechnicalPublishing,1997.
[8]郑君里,杨为理.
信号与系统[M].
2版.
北京:高等教育出版社,2000.
[9]RUSSELLSJ,NORVIGP.
Artificialintelligence:amod-ernapproach[M].
UpperSaddleRiver:Prentice-Hal,l1995.
[10]郭晶,孙伟娟.
神经网络理论与MATLAB7实现[M].
北京:电子工业出版社,2005.
[责任编辑:张晓京](上接第15页)路由荷载,如图4所示:可以看到路由荷载的消耗上,AODV最高,DSR次之,而DSDV用了最少的荷载,这也与路由机制密切相关.
DSDV由于是先应式路由,节点周期性地交换路由信息,路由开销基本与移动性无关,无论环境怎么变化,可以一直保持较小的路由开销.
随着移动速度的增加,DSR和AODV先应式路由开销也相应增加,这主要与缓存中路由失效有关,需要重新寻找新的路由,启动新的路由发现过程.
值得一提的是,虽然AODV和DSR都是反应式路由,性能相似,但是由于DSR采用的缓存技术和混杂接收方式侦听路由请求分组,大大降低了路由开销,所以DSR的路由开销比AODV表现得要低.
总之,随着节点移动速度的增加,3种协议分组交付率、平均端到端延迟、标准化路由荷载都存在一定程度的性能的下降,但是反应式路由DSR和AODV总体上比先应式路由DSDV表现得要好.
4结束语实际中要具体实现AdHoc网络的路由协议,必须了解协议的性能如何,不同的路由机制有着不同的性能,有着不同的应用环境,在性能指标方面有着不同的优缺点.
仿真中发现,分组交付率上,反应式路由DSR和AODV协议要明显好于先应式路由DSDV;在平均端到端延迟上,DSDV也许能产生最小的延迟,但是也可能因链路失效产生过大的延迟,而DSR和AODV能保持相对稳定;路由开销上DS-DV路由开销比DSR和AODV明显要小.
参考文献:[1]郑少仁,王海涛,赵志峰,等.
AdHoc网络技术[M].
北京:人民邮电出版社,2005[2]JOHNSONDB,DAVIDA.
DynamicsourceroutinginAdHocwirelessnetwork[M].
Dordrech:KluwerAcademicPublishers,1996.
[3]RFC2501MobileAdHocnetworking(MANET):routingprotocolperformanceissuesandevaluationconsiderations[S].
[4]UniversityofSouthernCalifornia.
Usingus[EB/OL].
h-ttp://www.
is.
iedu/nsnum/ns,2007-09-06.
[5]CHUNGJ,CLAYPOOLM.
NSbyexample[EB/OL].
h-ttp://nile.
wp.
iedu/NS/,2007-09-06.
[6]刘俊,徐昌彪.
基于NS的网络仿真探讨[J].
计算机应用研究,2002(9):75-78.
[7]黄冀,姜雪松.
移动IP技术与NS-2模拟[M].
北京:机械工业出版社,2006.
[责任编辑:张晓京]#24#应用科技第35卷