移动ad hoc网络qos路由协议的研究与仿真

《移动ad hoc网络qos路由协议的研究与仿真》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

武汉理工大学硕士学位论文AbstraCtMobileAdHoenetwork15amulti一hoPautonomoussystemwhiehgrouPedbymobilenodesequiPPedwithwirelesstranseeiversandreeeivers.Thissystem15noneedofafixedeentercut一overPointorbasiePointsuPPort.AsasPecialwirelessnetworkwhiehnotonlywithoutanyfixednetworkinfrastructurebutalsotakingflexibility，sPeedinessandeonvenieneeasitsadvantages，ithasanextensiveaPPlieationProsPeetinmilitaryandeivilianfield.50ithasbeenafoeusineurrentnetworkresearehfield.WiththePrevaleneeofmultimediaaPPliearion，QoSbeingProvidedinmobileAdHoenetworkshasbecomemoreandmoreimPortant.However’AdHoenetworkshavealotofeharaeteristicssuehasmulti一hoP，limitedbandwidtllresourcea一lddynamienetworktoPology.ThesemakeQoStobemoreeomPlexa:ldalsotake11e、vchallengesforresearehers.Byreferringtotheresearehesathomeandabroad，thisthesisaimsto一11akefurtherresearehesonhowtoProvideroutingProtoeolguaranteedbyQoSinAdHoenetworks.Theflowingarethemainresearchesandinnovationsofthisthesis.l)BeeausethatinAdHoenetworks，differentProtoeolshavedifferentadvantagesanddisadvantagesunderdifferentenvironment，andeveryProtocolhasitsownaPPlieationeonditions，50itbeeomesveryimPortanttoresearchandanalyzethePe而rmaneeParametersofdifferentProtocolsunderdifferentconditions.T}115thesisintroducestheeoneePtsandcharaeteristiesofAdHoenetworks，concludesclassieroutingProtoeols，afteranalyzingtheeurrentroutingProtocolandsimulationsmodelsonthebaseofrelativereferenees，makesasimulationunderanodemovingsPeedyandmorethiekerenvironment，andcomParesthePe而rmaneesofAODV，DS民TORAandDSDVondelay一time，jitter，Packetdeliveryrateandeffieieney.2)DuetothetransferrequirementofAdHocnetworksaPPlieationenvironmentandmultimediatraffieflowthatAdHocnetworksmustsuPPortQoS，50manyQoSroutingProtoeolshavebeenPresentednowandtoStUdytheseQoSdesignideology，Pe而rmaneesandeharacteristieswillhelPtoimProveevenPresentnewQoSroutingm 武汉理工大学硕士学位论文Protocolsinfuture.ThisthesisstudiesQoSteehniquesofAdHoenetworks，eomParesthePe而rmaneesofthecurrentroutingalgorithms，eoneludestheeurrentQoSroutingProtocolsofAdHocnetworksandcomParestheirPerformaneesbyseveralasPect，suehasroutingsystem，QoStarget，distributedoPeratingsystem，unidirectional一linksuPPortandmultieastsuPPort.3)Aeeordingtotherequirementofrealtimeflow，thisthesisPresentsRT_Q即Protoeolwhieh15animProvedAODVwithrealtimedelayconstraint.InRT_QRPProtoeol，whenthedelaytimelimitedflowaPPears，itwilleh00seroutillgontllebaseoftheleastdelaytimetomeettheneedsofflowandtakeuseofroutingcoPytoeutdowntheunneeessarysPendingProdueedwhenrebootroutingdiscoveryinordertoeovertheneedsofdelaytimeandatthesametimeoPtimizeresoureedistribution.TheresultofsimulationshowsthateomParingwit}1elassieAODVProtoeol，RT一RPredueedroutingsPending，boosteddeliveryratio，deereaseddelayti，、、ea，:dimProvednetservieequality.4)TheeurrentQoSroutingProtoeolofAdHocnet、vorksn、ai，、lystudyl，o、vtofindausefulPathsatisfyingeertaineondjtionsbet、veentwonodeswithoutt};i，，ki，:901’thestabilityofthisPath，thisthesisPresentsakindofroutingProtoc0I，PS_QRP，whichtakesbandwidthasQoSlimitedPara一neterandPathstabilityasbase.Beea一seofPS_Q即ehoosingroutingonPathstabilitybasis，whiehredueest}le11，IkerackedtimeseausedbymainframemovinganddeereasesthesPendingofroutingcontrol.Besides，beeauseittakesPrimaryandseeondaryreservationideawhenreserveresouree，50itgreatlyenhaneedthestabilityofchosenPathandfurtherinereasedrequestsueeeedrateandsendingsuceeedrate.Thisthesis15suPPortedbyNationalNaturalSeieneeFoundationofChi一a(90304018，60773211，60672137)，HubeiProvineeSeientineandTechnologicalResearchProjeet(2007AA10IC63)andthePh.D.ProgramsFoundationofMinist叮ofEdueationofChina(20060497015).Keywords:AdHoenetworks，QOS，routingProtocols，stability，simulationIV 武汉理工大学硕士学位论文目录第l章绪论.…““”.”........................……“...……”.....................................……”....……l1.1引言...........................................................................................................……11.2移动AdHoc网络的基本概念..................................................................……21.2.1移动AdHoc网络的定义...................................................................……21.2.2移动AdHoc网络的特点...................................................................……21.2.3移动AdHoc网络的体系结构...........................................................……41.3本课题的来源及研究意义...........................……，.......................................……81.3.1课题来源............................................................................................……81.3.2课题研究的目的及意义...............................................……，...............……81.4本文的主要工作及创新........................................................................……，…8第2章移动AdHoc网络路由协议研究分析....................................................……102.1弓}言.........................................................................................................……102.2移动AdHO。网络路由协议分类............................................................……112.2.1表驱动路由协议...................................................····························……112.2.2按需路由协议...................................................................................……132.3两种类型路由协议的比较.......................................................................……172.4小结..................……，...............................................................................……18第3章移动AdHoc网络QOS技术分析.............................................................……203.1弓，言........................................................................................................……203.2移动AdHoc网络QoS衡量参数..........................................................……213.3移动AdHoc网络QoS模型..................................................................……233.4移动AdHoc网络QoS路由..................................................................……253.5移动AdHoc网络QoS研究热点..........................................................……273.6几种典型的移动AdHoc网络QOS路由协议........................................……303.6.1CEDAR..............................................................................……，.........……303.6.2TBP....................................................................................................……313.6.3Q--A0Dv........................................................................···.....···········……323.6.4HQM[RP............................................................................................·……323.6.5STARA..............................................................................................……323.6.6QRM[E........................................................................................·..·..··……333.6.7Ls一。5.....................................................……，......··.....····················……333.6.8LTM...................................................................................................……33 武汉理工大学硕士学位论文3.6.9ABGR................................................................................................……343.6.10LBRM..............................................................................................……343.7移动AdHoc网络QoS路由协议的比较...............................................……353.8小结...........................................................................……，.......................……35第4章NSZ与网络协议仿真.“....................……““.“…..……”””“”....................……374.1NS网络仿真............................................................................................……374，2路由协议的仿真模型分析.......................................................................……394.3仿真度量标准..........................................................................................……404.4仿真环境和仿真实现..............................................................................……414.5仿真结果分析.........................................................................................……424.5.1平均延时分析...................................................................................……424.5.2抖动分析..........................................................................................……434.5.3包投递率分析...................................................................................……434.5.4效率分析.，...................................................................................……，.，.444.6性能比较.................................................................................................……454.7小结.........................................................................................................……46第5章一种基于延时约束的AODV改进协议设计与实现..............................……475.1引言........................................................................................................……475.2端到端的延时估计与优化......................................................................……485.3RTweQ”协议描述..................................................................................……515.3.IRT一”协议模型............................................................................……525.3.2RT_Q”协议包结构................................................................……，.……525.3.3路由发现..........................................................................................……535.3.4路由维护..........................................................................................……545.4增加备份路由机制.................................................................................……555.4.1备份路由的作用...............................................................................……555.4.2备份路由的设计...............................................................................……565.5协议正确性证明和复杂性分析...............................................................……575.6仿真实现..................……，........................................................................……575.6.1协议的修改......................................................................................……575.6.2性能评价参数...................................................................................……585.6.3仿真环境和参数设定.......................................................................……585.6.4仿真结果分析....................................................................……，........……585.7小结..................................……，................................................................……61矛 武汉理工大学硕士学位论文第6章一种基于路径稳定性的QoS路由协议.............................……“.............……636.1弓l言.…，......……，....……，....……，.........……，，，，，...……，..…，.，.....................……636.2带宽问题..................................................................................................……636.3PS一即协议...........................................................................................……656.3.1PS一”协议模型..........……，............................................................……656.3.2路由发现.........................................................................................……666.3.3资源预约.............……，.............................................……，...........……696.3.4路由维护..........................................................................................……696.4仿真实现..................................................................................................……706.4.1仿真步骤..........................................................................................……706.4.2仿真环境和参数设定.......................................................................……716.4.3性能评价参数...............................................……，.............................……7]6.4.4模拟结果与性能分析.......................................................................……716.5小结.......……，..........................................……，...........................................……73第7章总结及展望...........................................................................................……747.1工作总结..................................................................................................……747.2未来工作的展望.............................................……，..................................……75参考文献...........................................................................................................……76致谢................................................................................................................……80攻读硕士学位期间发表的论文和参加科研项目情况.....................................……81附录一trace输出文件信息的td代码.........................................................……82附录二trace信息的awk脚本代码.”...........................................................……85今 武汉理工大学硕士学位论文第1章绪论日l性旨JI「刁随着计算机网络的日益普及，能否快速方便地获取所需要的信息显得越来越重要。移动通信技术为人们无论在何时何地获取信息提供了一条有效的途径，并逐步成为了计算机网络领域研究的一个热点问题。移动通信网络按照有无基础设施的支持可以分为两大类:有固定基础设施支持的网络和没有固定基础设施支持的网络。目前需要固定基础设施支持的移动通信骨干网己被世界上广泛应川，例如GSM(GlobalSystemMobileCommunieation)、CDMA(CodeDivision入lultiPleAccess)等网络。但上述这些网络仅适应于已有骨干网络的区域，对于原本不存在骨干网的区域或者骨干网遭到重大破坏的区域，如在大海上、沙漠「!，，以及灾区、战场、临时会议、军事行动等特殊场所，上述移动通信网络就不能满足要求。在某些紧急情况下，需要临时、快速地建立一个新的移动通信网络，以便实现信息的传送。为了满足这种要求，作为移动通信的另一种特殊形式一一移动AdHoc网络就应运而生了川。移动AdH。。网络最初是应用于军事领域的，它的研究起源与TCP/IP协议族类似，是20世纪70年代美国国防部高级研究计划局(DARp，DefenseAd’，aI1cedResearehpesearchprojectAgency)资助研究的、在战场环境下采用分组无线网(PRNET，PacketRadioNet)进行数据通信的项目中产生的一种新型的网络架构技术。其后，又由DARPA资助，于1983年和1994年进行了具有抗毁性的自适应网络(sURAN，survivableAd即tiveNetwork)和全球移动信息系统(GloMo，GlobalMobileInformationsystems)项目的研究。AdHoe技术就是吸收了pRNET，SURAN以及GfoM。等项目的组网思想，从而产生的一种新型的网络架构技术。目前AdHoc网络继承和发扬了DARPA资助无线分组数据网的思想，特别是伊RNET，PacketPadioNet)。PRNET强调的是在一个广阔的区域实现多跳的无线通信，基于这种多跳的无线信道特点，PRNET面临着诸如介质接入、寻址路由、网络初始化和控制等难题。但是PRNET所倡导的系统自组织(self-organizing)特性 武汉理工大学硕士学位论文使得PRNET网络系统组建灵活，网络的抗破坏性强[2l。1.2移动^dHoc网络的基本概念.2.1移动AdHoc网络的定义移动AdHoc网络是由一组自主的无线节点或终端相互合作而形成的，独立于固定的基础设施，并且采用分布式管理的网路，是一种自动创建、自动组织和自我管理的网络。与传统的蜂窝网络相比，移动AdHoc网络没有基站，所以节点分布式运行，具有路由器的功能、负责发现和维护到其他节点的路由，向邻居节点发射或转发分组。这种网络既然可以单独运行，又可以通过网关接入到有线骨干网络(如互联网)。在移动AdH。。网络中，每个移动终端兼备主机和路由器两种功能:作为主机，终端需要运行面向用户的应用程序;作为路由器，终端需要运行相应的路由协议，进行路由发现、路由维护等常见的路由操作。由于终端的无线传输范围有限，两个无法直接通信的终端结点往往会通过多个中间结点的转发来实现通信。图1一1描述了一个由三个终端组成的简单的移动AdHO。网络。主机C不在主机A的无线覆盖范围之内(用环绕主机A的圆环表示)，同时主机A也不在主机C的无线覆盖范围之内。如果主机A和C之间需要交换信息，就需要主机B为它们转发分组，因为主机B在主机A和C的无线覆盖范围之内，此时B就在为A和C的通信中担当路由器的功能。，、矛、‘‘|图1一1一个简单的移动AdHoc网络.2.2移动AdHo。网络的特点与传统的通信网络相比，移动AdHoc网络具有以下显著特点，川: 武汉理工大学硕士学位论文l)动态变化的网络拓扑结构:AdHo。网络中，用户终端的移动具有很大的随机性，加上无线发信装置发送功率的变化、无线信道间的互相干扰以及地形等综合因素的影响，网络的拓扑结构可能随时发生变化，并且这种变化的方式和速度难以预测。2)移动终端的局限性:AdHoc网络中的用户终端便于携带、轻巧灵便，但也有固有缺陷，比如能量受限、CPU处理能力低和成本较高，从而给应用和开发带来难度，同时显示屏等外设的功能和尺寸受限，不利于开展功能复杂的业务。3)无中心和自组织性:所有节点地位平等，各节点通过分层的网络协议和分布式算法调节彼此的行为。节点可以随时加入和离开网络，任意节点故障不会影响整个网络运行，具有很高的鲁棒性。无中心和自组织特点使得移动AdHoc网络可以实现快速自动组网。4)多跳路由:由于节点发射功率的限制，节点的覆盖范围是有限的。当要与其覆盖范围之外的节点进行通信时，需要中间节点的转发，即要经过多跳。反过来，使用多跳路由，节电的发射功率可以很低，从而达到节省电能、延长电池工作时间的目的。5)特殊的无线信道特征:单向信道的存在。，常规路由协议通常认为底层的通信信道是双向的，但在采用无线通信的AdH。。网络中，由于发射功率或者地理位置等因素的影响，可能存在单向信道，这会使得常规路由协议产生路山单向性和汇点不可达以及“隐终端”和“暴露终端”等问题。另外，由于AdIl()c网络采用无线传输技术作为通信手段，而无线信道本身所能提供的网络带宽相对较低，再加上竞争共享无线信道带来的信号冲突、衰减及干扰等多种因素的影响，移动终端可得到的有效带宽将远小于理论上的最大带宽。6)有限的安全性和服务质量:由于移动AdHoc网络缺乏固定的网络基础设施进行用户鉴权和认证，因此其安全性难以保证。多跳网络、动态拓扑以及动态链路容量使服务质量的保证变得也困难，目前大多数移动AdHoc网络都只能提供尽力而为仍est.eflbrt)的服务。另外，移动AdHoc节点自身充当路由器，不存在命名服务器和目录服务器等网路设施，也不存在“网络边际”的概念，因此需要特别考虑信道加密、抗干扰、用户认证、密钥管理、访问控制和其他安全措施。 武汉理工大学硕士学位论文1.2.3移动AdHo。网络的体系结构网络各层及其协议的集合，称为网络的体系结构，它是网络及其部件所应完成功能的精确定义。考虑到移动AdHoc网络的特殊性，传统的体系结构和现存的大量协议已不再实用，AdHo。网络的体系结构和设计方法应充分考虑网络的动态自组织性和特殊的应用环境。l)移动AdRoc网络的节点结构移动AdHoc网络的节点同时具有移动终端和路由器的功能，因此节矛.从通常包括主机、路由器和电台三部分。其中主机部分完成移动终端的功能，包括人机接口、数据处理等;路由器部分主要负责网络的拓扑结构和路由信息，完成报文的转发功能;电台部分完成无线传输功能。如图1一2所示，从物理结构上分，节点可以分为以下几类:单主机单电台、单主机多电台、多主机单电台、多主机多电台151。路由器路由器主机主机主机主机(a)单主机单电台(b)多主机单电台路由器路由器主机主机主机主机(c)单主机多电台(d)多主机多电台图1一2移动AdHoc网络节点的结构2)移动AdRoc网络的拓扑结构拓扑可变的网络包含四种基本结构:中心式控制结构、分层中心式控制结构、完全分布式控制结构和分层式控制结构。对于移动AdHoc网络，由于节点 武汉理工大学硕士学位论文的能力通常相同并且都可以移动，故不适合于采用集中式控制结构，特别是在战场环境中，中心控制节点易被发现和易遭摧毁。因此移动AdH。。网络一般采用分布式控制结构，即平面结构和分层结构。平面结构的AdHoc网络如图1一3所示。这种网络结构的特点是比较简单，所有节点在网络控制、路由选择和流量管理上都是平等的，所以又称之为对等式结构。这种结构原则上不存在瓶颈，网络比较健壮。源节点和目的节点之间通常存在多条路径，可以较好地实现负载均衡和选择最优化的路由。此外，平面结构中节点的覆盖范围较小，相对较安全。但在节点数目很多，特别足在’节点大量移动的情况下，平面结构网络具有控制开销大，路由经常中断等缺J点，并且很难实施集中式的网络管理和控制。还有，它的可扩充性较差，梅个节点都需要知道到达其他所有节点的路由信息，当网络规模增大时，维护这些动态变化的路由信息就需要大量的控制消息，路由维护的开销指数增长而消耗有};陡的带宽，因此平面结构只适用于中小规模的AdHoc网络。分层结构AdHoc网络如图1一4所示。户.，.，、户·.…·簇二.簇头;.簇成员;▲网关图1一3平面网络结构图1一4分层网络结构移动AdHo。网络被划分为一到多个簇(cluster)，每个簇由一个簇头(ClusterHeader)和多个簇成员(elusterMember)组成。这些簇头形成高一级的网络，在高一级网络中，又可以再分簇，形成更高一级的网络。在分层结构中，簇头节点主要负责簇间数据的转发，它可以预先指定，也可以由节点使用算法选举产生。当两个不同簇中的节点需要交互数据时，通常都需要源簇和目的簇中的簇头进行转发。分层结构的网络中，簇成员的功能比较简单，不需要维护复杂的路由信息，这大大减少了网络中路由控制信息的数量，具有良好的可扩展性，网络规模不受限制。但同时它具有以下几个缺点:维护分层结构需要节点执行簇头选举算法，增加了计算的复杂性;簇间信息都要经过簇头寻路，不一定使用最 武汉理工大学硕士学位论文佳路由;簇头节点的任务相对较重，可能成为网络的瓶颈。总之，当网络的规模较小时，可以采用简单的平面结构;当网络规模较大时，应采用分层结构。3)移动AdHoc网络的协议栈根据移动AdHoc网络的特征，参照051爪M的经典7层协议栈模型和TCP月P的体系结构，可以将移动AdH。。网络划分为5层l’l，如图l一5所示，应用层:实时业务、自适应应用数据报业务.，.移动定位、自动配置、安全策略…传传输层:阿)TCP、uDP……网网络互联层:I叭·4、IP诵、MobileIP……网网络层:邻居发现、路由协议(DSR、DSDV等)、VC机制……逻逻辑链路控制子层(LLc):分组转发/确认、差错控制……媒媒体接入控制子层(MAC):TDMA、CDMA、IEEE802.11、MACAAA物物理层:扩频技术口S·55、HF一55)、调制解调、发送接收收图卜5移动AdHoc网络的通用协议栈结构其中虚线框表示可选的功能部件。考虑到TCP皿协议已经成为事实上的网络互联标准，AdHoc网络体系结构应基于TCP仰体系结构，并需要根据自身特点进行必要的简化、修改和扩充。例如，必须修改路由协议以适应网络拓扑的6 武汉理工大学硕士学位论文动态变化;修改TCP来提高其在无线传输环境下的性能。此外，还要考虑与有线骨干网的无缝连接，兼顾网络的效率与抗毁性等。例如，必须修改路由协议以适应网络拓扑的动态变化;修改TCP来提高其在无线传输环境下的性能。此外，还要考虑与有线骨干网的无缝连接，兼顾网络的效率与抗毁性等。在通用协议栈结构中，各层的功能描述如下:l)物理层:物理层负责频率的选择、无线信号的检测、调制解调、信道加密解密、信号发送和接收等工作。此外还要确定采用哪种无线扩频技术(直接序列扩频DSSS或跳频扩频FHSS)。由于多径传播带来的多径衰减、码问串扰以及无线传输的空间传播特性带来的节点间的相互干扰，使移动AdHoc网络的传输链路带宽容量低。因此物理层的设计目标是以相对低的能耗，克服无线媒体的传输损伤，获得较大的链路容量。2)数据链路层:数据链路层的MAC子层控制移动节点对共享无线信道的访问，它可以采用随机竞争机制(CSMA、IEEE802.ll或MAcA)、华于信遒划分的接入机制(TDMA、FDMA、CDMA或SDMA)、轮转机制(轮询或令牌环)、动态调度机制以及以上机制的组合。逻辑链路控制子层负责数据流的父川、数据帧的检测、分组的确认、优先级排队、差错控制和流量控制等。链路层的设计目标是在相对能量小的条件下，使得数据速率接近最基本的信道容量。3)网络层:网络层是移动AdHoc网络的重点，主要包括邻居发现、分组路由、拥塞控制和网络互连等功能;网络层的单播路由协议维护路由表，使其与当前的移动AdHoc网络拓扑结构一致;多播路由协议提供群组通信的底层支持;网络互联支持移动AdHoc网络与其它现有网络互联。4)传输层:传输层主要是向应用层提供可靠的端到端服务，使上层与通信子网(下三层的细节)相隔离，并根据网络层的特性来高效地利用网络资源，当移动AdHoc网络需要接入Iniemet等外部网络时尤其需要传输层协议的支持。5)应用层:应用层协议提供面向用户的协同应用服务，包括具有严格延迟和丢失率限制的实时应用(紧急控制信息)、基于RTP爪TCP的自适应应用(音频和视频)和没有任何服务质量保障的数据业务。6)其他功能:包括功率控制和拓扑控制、分簇算法、信令协议、移动管理和位置定位、服务发现、地址自动配置和安全策略等。图中给出了这些可选功能模块在协议栈中可能出现的位置，具体的位置取决于各功能模块的作用以及与上、下层协议的关系。基于该协议栈是一个通用的AdHoc网络协议栈，对于 武汉理工大学硕士学位论文具体的应用场合，该协议栈可以简化，去掉不必要的功能模块或添加新的模块，并根据系统的要求和应用的特性作进一步的细化。1.3本课题的来源及研究意义.3.1课题来源本文受到国家自然科学基金资助项目(批准号:90304018，60773211，60672137)，湖北省科技攻关项目(批准号:2007AA10lC63)和教育部博士点华金项目(批准号:20060497015)的资助。.3.2课题研究的目的及意义移动AdHoc网络是指一组带有无线收发装置的移动节点组成的一个多跳的临时性的自治系统。与其他移动通信网络相比，它不需要固定纂站支持，具有网络自组性、动态变化的网络拓扑结构、存在单向的无线信道等特点。因此，移动AdHoc网络可以通过临时组网的方式在恶劣环境中支持移动竹点之问的数据、语音、图像和图形等业务的无线传输，应用范围可以覆盖工业、商业、医疗、家庭、办公环境、军事等各种场合，所有行业几乎无所不在其中，尤其在未来战场上，AdHo。网络网络对于高技术武器装备、集中指挥、协同作.饯和提高作战机动性等具有非常重要的意义。在今天大获成功的Intemet上，QoS路由仍然是一个带有挑战性的问题。不同业务类型有不同的QoS目标，确定链路的QOS容量不是一件简单的事情，对于组播业务困难更大。路由计算不能花费太长时间，路由选择必须考虑计算的复杂度。多于一个QOS限制使得QoS路由问题成为完全的NP问题。在移动AdHoc网络中，链路带宽受限，RF信道特性的不可预测变化，众多具有可变QoS要求的邻居共享信道介质，需要在不断变化的环境下提供多种不同等级的服务质量，使移动AdHoc网络面临比有线网更大的QoS难题。.4本文的主要工作及创新本文主要研究移动AdHoc网络中的QoS路由协议，分析QoS路由协议在 武汉理工大学硕士学位论文AdHoc网络中对网络的各项性能指标的影响，为获得具有较优网络性能的QoS路由协议提供科学参考，也为在实用AdHoc网络中部署QoS路由协议提供理论依据。根据移动AdHoc网络的特性，研究实用性强的，可靠性高的，具有自适能力的QoS路由协议是急需解决的问题，本文所作的主要工作如下:l)研究AdHoc网络的特点、体系结构、应用和技术难点。2)研究分析了NSZ的特点和仿真流程。3)研究分析AdHoc网络典型的单播路由协议，并对DSDV，DSR，AODV，TORA路由协议进行了仿真实验研究。4)深入探讨AdHoc网络的QoS技术，分析比较了现有QoS路由算法的性能，并从路由机制、多播功能、QoS参数选择等多个方面对QoS路由协议进行对比，提出了改进的QoS路由协议。在研究过程中，本文主要的创造性可体现在以下两个方而:l)针对实时业务的需求，提出了基于延时约束的AODV改进协议RT_QRP，并和传统AODV路由协议进行了仿真实验研究。2)针对当前移动AdHoc网络的QoS路由协议主要集中研究如何在两个节点之间找到满足QoS条件的可行路径，而没有考虑可行路径的稳定性，建议了一种以带宽为QoS约束参数，基于路径稳定性的QoS路由协议PS_QRP，夕干和RTesQRP路由协议进行仿真分析。 武汉理工大学硕士学位论文第2章移动AdHoc网络路由协议研究分析91日1.套.‘.二J.「刁目前Internet常规路由协议主要采用两种形式的路由思想:基于距离矢量的的路由协议(如犯P协议)和基于链路状态的路由协议(如OSPF协议)。这两类协议都是针对固定网络而设计的，它们都需要周期性的交换信息来维护网络正确的路由表或网络拓扑结构图。由于AdHoc网络带宽有限、拓扑变化频繁，因此，传统的路由协议如IUP，OSPF等都不适用于AdHo。网络，主要体现在以下儿个方面lvl:l)动态变化的网络拓扑结构。动态变化的拓扑结构是AdH。。网络最显著的特点。在这种动态变化的网络环境下直接运行常规路由协议，当网络拓扑变化时，常规路由协议需要花费很长时间和较大代价才能达到收敛状态。2)’单向信道的存在。常规路由协议通常认为底层的通信信进是双向!，1{J，但在采用无线通信的AdHoc网络中，由于发射功率或一者地理位置等因素的彩响，可能存在单向信道，这会使得常规路由协议产生路由单向性和汇点不可达等严重问题。3)周期性的广播拓扑信息会占用大量的无线信道资源，耗费电池能源，将会严重降低系统的性能。尤其是在拓扑变化频繁的AdHoc网络环境中，可能当路由算法还未收敛时，网络的拓扑结构就又发生了变化。4)移动终端的局限性。移动终端在带来移动性、灵巧、轻便等好处的同时，也有其固有的弱点，如采用电池一类可耗尽能源提供电源、内存较小、CPU性能较低等。这就要求路由算法能够简单有效，实现的程序代码短小精悍，同时需要考虑如何节省能源等问题。而常规路由协议基于高性能路由器作为运行的硬件平台，没有上述限制。综合以上分析，AdHoc网络与传统网络在路由选择方面有很大的差异，特别是在网络拓扑结构、信道、广播机制、移动终端等方面，所以必须采用合适的路由算法以解决AdHoc网络中的路由选择问题。 武汉理工大学硕士学位论文2.2移动AdHoc网络路由协议分类传统的路由协议无法适应AdHo。网络的需要，因此必须选择或设计适用于AdHoc网络环境特点的路由协议。经过多年的研究，许多路由协议方案相继被提出。除了MANETWG发布的DSR、AODV、Z即等路由协议草案外，研究人员还发表了许多关于移动AdHoc网络路由协议的学术论文，如DSDv、WRp、CGsR等。目前，已存在数十种以AdHoc网络为网络环境路由协议，其中较为基础和常见的有:DSDV、WRP、WRP、STARA、FSR、FSLS、OLSR、TBRPF、AODV、DSR、TORA、ABR、SSR、HSR、CGSR、ZRP、LAN入IAR、CEDAR、GeoCast、LAR、DREAM、GPSR。常见的几种分类方式为:1)根据发现路由的驱动方式分类l吕一9】。按照路由发现策略的角度，可分为表驱动路由协议和按需驱动路由协议两种。表驱动路由协议采用周期性的路山分组广播来交换路由信息。按需驱动路由协议是根据发送数据分组的需要按击进行路由发现，建立传输路径，从而实现信J自、传送。2)根据网络拓扑结构分类l’”一川。可以分为平面结构的路由协议和分级的路由协议两种。对于平面结构的路由协议，网络的逻辑视图是平面结构，移动竹点具有平等的地位。其优点是网络中没有特殊节点，节点移动性较简单，易于管理。对于层次结构的路由协议，网络的逻辑结构是层次性的。在两级网络l!，，骨干网由较为稳定、综合性能较好的骨干节点组成。其优点是适合大规模移动移动AdHoc网络，扩展性较强。2.2.1表驱动路由协议表驱动(TableDrive)路由协议也被称为主动路由协议、先应式路由协议，其路由发展策略类似于传统的路由协议。在表驱动路由协议中，网络的每一个节点都要周期性地向其他节点发送最新的路由信息，并且每一个节点都要保存一个或者更多的路由表来存储路由信息。当网络拓扑结构发生改变时，节点就在全网内广播路由更新信息，这样每一个节点就能连续不断地获得网络信息。表驱动路由协议的优点是当节点需要发送一个去往其他节点的数据分组时，只要路由存在，发送分组的延时很小。缺点是需要花费较高代价(带宽、电源及CPU资源等)，尽量使得路由表能够跟上当前网络拓扑结构的变化，但动态变化的拓扑结构可能使得花费较高代价得到的路由表中的内容变成无效信息，路由 武汉理工大学硕士学位论文协议始终处于不收敛状态。下面介绍几种典型的表驱动路由协议。1)DSDV(DestinationSequeneedDistaneeVector)DSDvllZ~141协议(目的节点序列距离矢量路由)是一个基于传统的Bellman一Ford路由选择机制的表驱动算法，它被认为是最早的移动AdHoc网络路由协议，通过给每个路由设定序列号避免了路由环路的产生。DSDV采用时间驱动和事件驱动技术控制路由表的传送，即每个移动节点在本地都保留一张路由表，其中包括素有有效目的节点、路由跳数、口的节点路由序列号等信息，目的节点路由序列号用于区别有效和过期的路由信息以避免环路的产生。路由表更新分组在全网内周期性地广播而使路由表保持连贯性。衍个节点周期性地将本地路由表传送给邻近节点，或者当其路由表发生变化时，也会将其路由信息传给邻近节点。当无节点移动时，DSDV使用间隔较长、包含多个数据单元地大多数据分组进行路由更新;在节点移动时使用较小地数据分组，;1二比支队移动地节点更新路由，这样降低了整体地开销。当邻近节点收到包含修改地路由表信息后，先比较源节点、日的节点路山序列号地大小，标有更大序列号的路由信息总是被接收，目的节点路山序列号小的路由则被淘汰。如果两个更新分组有相同的序列号，则选择跳树(metric)址小的，而使路由最优(最短)。为了消除最优路由的频繁变化，节点首先根抓历史记录，估计产生路由所需的保留时间T(settletime)，推迟一个T再发送修改的路山信息。DSDV的优点是原理及操作相对简单，并解决了传统距离矢量路由协议中的无穷环路问题，缺点是不适应快速变化的网络，不支持单向信道，且网络耗费很高。2)CGSR(ClusteredGatewayswitehRouting)CGsRI’51协议是在DsDv协议基础上融合分层次的思想设计的。协议采用LCC(LeastclusterChange)算法，把移动自组织网络划分成若干个簇，每一个簇中有一个“簇首”(austethead)，而同时位于多个簇的节点被称为网关。每个节点维护两种数据结构:路由表和簇成员表。节点使用DSDV协议，周期性地与同簇内的邻居节点交换簇成员表，更新表信息。当一个节点要通信时，数据包首先传递给自己所在簇的簇首，然后通过网关到达另外一个簇首，以此种方法穿过中间的分簇，到达目的节点所在簇的簇首，然后再转发给目的节点。CGSR 武汉理工大学硕士学位论文通过分簇，大大减少了维护路由表所需要的信息量。另外，采用这种路由的网络有比较好的扩展性，但其缺点是算法相对复杂，需要一定的执行代价。3)WRP(WirlessRoutingProtocol)WR卫I‘61路由协议在网络的节点中保存路由信息。每个节点保存在路由表中的信息如下:距离、路由、链路开销和重传消息的列表(MRL)。MRL记录关于消息序列号、重传计数器、每一个邻节点正确应答所需的标识和更新消息的史新列表等信息。这就使得节点可以决定何时发送更新消息以及发送给哪个节点。更新消息包括目的节点的地址、到目的节点的距离和目的节点的上游节点然后邻节点就修改自己的路由表并试图通过预备的节点建立新的路由。W又P白勺优点就是当一个节点试图执行路径计划算法时，可以通过目的节点的上游节点所保存的信息和邻节点所保存的信息来限制算法，使得算法收敛得更快并避免路由当中的环路。由于WRP需要保存4个路由表，所以比大多数的协议需要更大的内存。WRP还依赖于周期性的Hell。消息，这也要占用带宽。2.2.2按需路由协议按需路由协议也称为反应式路由协议、源启动按需路由协议(Souree一Initiatedon一DemandDriven)。与表驱动路由协议不同的是，按需路以J仅在需要路由的时候才由源节点创建，因此，拓扑结构和路由表内容是按需建立的，它可能仅仅是拓扑结构信息的一部分。通信过程中维护路由，通信完毕后便不再进行维护。通常，按需路由包括3个过程:路由发现过程、路由维护过程和路由拆除过程。这种路由选择方式只有当源节点需要时才建立路由。当一个节点需要到目的节点的路由时，它会在全网内开始路由发现过程。一旦检验完所有可能的路由排列方式或找到新的路由后就结束路由发现过程。路由建立后，由路由维护程序来维护这条路由，直到它不再被需要或发生链路断开现象。当源节点发现没有去往目的节点的路由时，触发路由发现过程;找到路由后，在通信过程中进行路由维护，此过程一般依靠底层提供的链路失效检测机制进行触发;通信完毕之后，路由拆除过程将路由取消。由于重要性不及前两个过程，路由拆除过程在有些协议中被忽略。以下是几种常见的按需路由协议。l)DsR(Dynamiesouree助uting)l’下，.1DSR协议是一种基于源路由方式的按需路由协议。在DSR协议中，当发送者发送报文时，在数据报文头部携带到达目的节点的路由信息，该路由信息由网 武汉理工大学硕士学位论文络中的若干节点地址组成，源节点的数据报文就通过这些节点的中继转发到达目的节点。与基于表驱动方式的路由协议不同的是，在DSR协议中，节点不需要实时维护网络的拓扑信息，因此在节点需要发送数据时，如何能够知道到达目的节点的路由是DSR路由协议需要解决的核心问题。DSR路由协议主要由路由发现和路由维护两部分组成。路由发现过程主要用于帮助源节点获得到达目的节点的路由。当路由中的节点由于移动、关机等原因无法保证到达目的节点时，当前的路由就不再有效了。DSR协议通过路由维护过程来监测当前路由的可用情况，当监测到路由故障时，将调用新的一轮路山发现过程。同时为了提高系统性能在DSR协议中，还引入了一系列的优化技术，如路由缓冲(RouteCaehe)等。DSR协议具有以下几个优点:.仅在需要通信的节点间维护路由，减少了路由维护的代价。.路由缓冲技术可进一步减少路由发现的代价。.由于采用了路由缓冲技术，因此在一次路由的发现过程中，会产生多种到达目的节点的路径。.支持非对称传输信道模式。DSR协议存在一些问题和不足:.由于采用源节点路由，每个数据报文的头部都要携带路由信息，增加了报文长度。.用于路由发现的控制报文可能会波及全网各节点，造成一定的耗费;一种可行的优化方法是控制路由发现报文的传输距离(如跳数)，如果本轮路由发现失败，后续的路由发现过程再加大传输距离。.“路由响应风暴”(RonteRePlyStorm)问题。由于采用路由缓冲技术，中间节点根据自己的缓冲路由，对路由请求直接应答，源节点会同时收到多个路由响应，造成路由响应信息之间的竞争。.“脏”缓冲路由对其他节点的影响。如果中间节点的路由缓冲已经过时，当该节点根据缓冲路由回复路由请求时，会造成“脏”缓冲路由的污染传播。DSR协议特点的改进:采用路由缓存技术，以加快路由发现，减少路由请求消息对信道的占用。:通过限制路由请求消息的传播距离或者通过使用位置信息来减少路由 武汉理工大学硕士学位论文请求消息的泛滥。.当链路出错时，出错点的中间节点可从自己的路由列表中选出另一个可选路由，完成到目的节点的数据分组传输。.出错信息加到源节点重新发出的路由请求信息中，随着路由信息广播出去，以便更新网络含有该出错链路的节点的路由信息。.当中间节点的路由信息中含有到目的节点的路由信息时，该中间节点可直接向源节点返回路由应答消息。应答消息中包含了整个路径信息。2)AoDV(^dHoeonDemandnistanceveetor)l’9一川在AODV协议中，路由中的每个节点都维护路由表，因而数据报文头部不需要携带完整的路由信息，从而提高了协议的效率。AODV的路由发现过程由反向路由的建立和前向路由的建立两部分组成。AODV的路由发现过程如下:l)源节点首先发起路由请求过程，在发起的路由请求报文中携带以卜信息字段:<源地址，源序列号，广播ID，目的地址，目的序列号，跳数计数器>，其中，序列对<源地址，广播ID>惟一标识一个路由请求。2)中间节点在收到路由请求报文时，比较本节点和目的节点的地址，如果自己是目的节点，则回复路由响应报文。否则根据<源地址，广播10>判断是否收到过该请求消息，如果收到过则丢弃该请求消息、，否则记录相应的信息、，以形成反向路由。同时跳数计数器加1，向邻节点转发该路由请求报文。AODV路由发现的反向路由建立过程如图2一4所示，前向路由建立过程如图2一5所示:℃月-一反向D司---反向叫卜一一一正向住心ss口图2一反向路由的建立图2一5前向路由的建立AODV路由协议中的路由表主要包括目的节点、下一跳节点、距离目的节点 武汉理工大学硕士学位论文的跳数、目的节点序列号、本路由活跃邻节点和本路由的超期时长等信息。同时，在AODV协议中，节点还存储一些与路由表相关的信息。路由请求超时定时器:和反向路由相关的定时器，当定时器超期后，节点仍未收到路由响应报文时，节点则认为该反向路由无效，删除该反向路由。活跃超时时长:和前向路由相关的时长。当超过活跃时长时间后，节点仍然无数据利用该路由发送时，删除该路由(即使该路由可能有效)。AODV的优点是综合了DSDV协议和DSR协议两者的特点。在AODV协议中，由于通往目的节点路径中的节点建立和维护路由表，数据报文头部不再需要携带完整路径，减少了数据报文头部路由信息对信道的占用，提高了系统效率。因此，协议的带宽利用率高，能够及时对网络拓扑结构变化作出响应，同时也避免了路由环路现象的发生。但是AODV协议中也存在以下一些问题:.AODV协议仅适用于双向传输信道的网络环境。由于在路山i吉求消启、的广播过程中建立了反向路由，供路由响应报文寻路，因此网络要满足双向传输信道的要求。.路由表中仅维护一条到指定的目的节点的路由，而在DSR协议「!，，源节点可以维护多条到目的节点的路由。如果节点间存在多条路山，当某条路由失效时，源节点可以选择其他的路由而不需要重新发起路山发现过程，这在网络拓扑结构变化频繁的环境中尤其重要。.由于AODV协议采用了超时删除路由的机制，因此即使路由未失效，在超过时限后也将被删除。3)ToRA(Temporallyordered助uting^一gorithm)12，lTORA是一个基于链路反转方法的自适应的分布式路由算法，主要用于高速动态的多跳无线网络。作为一个由源端发起的按需路由协议，它可以找到从源到一个目的节点的多条路由。TORA的主要特点是:当拓扑发生改变时，控制消息只在拓扑发生改变的局部范围传播。因此，节点只需维护相邻节点的路由信息。协议由3部分构成:路由产生、路由维护和路由删除。初始化时，目的节点的高度(即传播序列号)被置为。。然后由源端广播一个含有目的节点m的QRY分组，一个高度不为O的节点响应一个UDP分组。收到UDP分组的节点的高度将比产生该UDP分组的节点的高度大1，并且具有较大高度值的节点被规定为上游节点。通过这种方式能够创建一个从源到目的节点的一个有向无环路图 武汉理工大学硕士学位论文(DAG)。当节点移动时，路由需要重建。在路由删除阶段，TORA通过广播一个CLR分组来删除无效的路由。TORA的优点是可以处理高密度的网络。还支持保存2个节点间的多条路由以及广播，快速建立路由和通过拓扑变化的局部算法来减小通信开销。路由的优化(最短路径路由)是次要的，通常采用更长的路由来避免发现新路由时的开销。然而，TORA算法是基于同步时钟的，所以时钟时间的不同可以导致路由故障。并且当多个节点同时进行选路和删除路由时会产生路由振荡现象，这可能影响路由的建立时间。4)L从(LoeationAidedRouting)12，JLAR协议是一个基于预测节点当前位置算法的反应式路由协议。它的目标是如何有效提高路由请求的效率，限制路由请求过程中被影响的节点数目。类似的思想也出现在移动蜂窝电话系统选呼机制(selectivePaging)中。LAR假设节点采用GPS系统获得位置信息，且每个节点都知道其他节点的平均运动速度。路由请求时，源节点根据目的节点历史位置和移动速度指定一个地理区域:请求范围，并将此信息附在路由请求分组中。LAR规定只有位于请求范围内的中间节点才允许进行路由请求分组的转发操作，从而减少了路由请求的影响范围。当路由请求失效时，源节点将扩大请求范围，重新进行路山请求。LAR的缺点是它必须依靠GPS系统才能正常工作，限制了其应用范围。5)ssR(signalstability一basedadaptiveRouting)I，41SSR是基于信号强度的反应式自适应路由协议，它选择路由的根据是节点之间的信号强度和节点位置的稳定度，目标是得到更稳定和更长久的路由，利用这种路由选择标准可以选择强连接性的路由。SSR由两个互相合作的协议构成:动态路由协议(DRP)和静态路由协议(SRP)。D即负责维护信号稳定度表(SST)和路由表(RT)。SST记录邻节点的信号强度，信号强度通过接收链路层发出的周期性信标获得。在选择路由时，将信号强度作为选择依据，以得到稳定性最好的路由。SSR能提供无环路由，支持QoS，但周期地标识路由会带来额外的开销。2.3两种类型路由协议的比较表驱动路由协议基于路由表更新机制，其更新间隔对性能的影响很大，间 武汉理工大学硕士学位论文隔太大，协议将不能快速反应拓扑结构的变化;间隔太小，则网络可能因充满路由表更新消息而阻塞。当网络中活动的源目通信对数目较大时该类协议更有效率，因为浪费的路由开销相对减少，反之则利用率较低。每一节点到达其它任何节点的路由总是就绪的，不管它是否确实需要，尽管这种特性适合于传递诸如UDP之类的无连接信息流，但这将导致持续的路由信息传播，加重网络的载荷，同时将增加能量消耗，由于带宽和电池容量都是移动计算机宝贵的紧缺资源，这将造成严重的局限性。当网络规模和移动性增加(超过一定的闽值)时，大部分表驱动路由方案将不可行，因为仅用于保持与拓扑变化一致而需要传送的路由更新消息就将消耗大部分的网络容量和节点处理能力。相反，按需路由协议并不维护尚未需要的路由，而且其路由请求应答(RREQRREP)控制分组通常比预选方案中用于路由表更新的分组小，因此所产生的路由控制信息比表驱动协议少得多。但由于在数据开始传输之前必须先建立路由，因此会产生一定的路由延时，而这在表驱动协议中没有。因此，在拓扑变化频繁的AdHoc网络环境中，应采用按需路由协议;而在网络拓扑结构相对稳定的环境中，如果业务对实时性要求较高时，应尽量采)}〕基于表驱动方式的路由协议。表驱动路由协议和按需方式路由协议的路山延退、控制开销、耗电量和带宽开销的比较如表2一1所示:表2一l表驱动和按需方式路由协议的性能比较表表表驱动(Table一Dri、，en)))按需(On一De，11a.记)方式式路路由协议议DSDV、CGSR、WRPPPAODV、DSR、TORA、SSRRR路路由获取延迟迟低低高高控控制开销销高高低低耗耗电量量高高低低带带宽开销销高高低低2.4小结本章首先介绍了移动AdH[oc网络与传统网络在路由选择方面的差异，然后 武汉理工大学硕士学位论文参考相关文献，分析经典路由协议的设计思路和优缺点，最后从路由获取延迟、控制开销、耗电量和带宽开销方面比较表驱动和按需方式路由协议的性能特点，其目的是明确AdHoc网络中不同的协议在不同的应用环境中有各自的优缺点，和每种协议的适用条件。 武汉理工大学硕士学位论文第3章移动AdHoc网络005技术分析ql日!省…J二刁Qosl，，l(qualityorserviee)是一种协定或保证，即通过网络对用户提供一系列预先指定的可量度的业务属性，如跨网延时、延时抖动、可用带宽机分组丢失率等。QoS协议用于在移动AdHoc网络络中对数据进行等级化处理，为高数据速率的应用预留更好的连接，同时为低速率数据通信维护足够带宽，有它自己的体系结构，QoS路由是其中最重要一环，QoS路由试图找出能满足给定性能限制的路由，以便为业务流预留足够容量。QoS路由是指在具体的路由协议中增加QoS参数对路由的约束，根据网络的可用资源来决定传送路径，从而提供更好的数据传送性能。QoS路由不仅涉及点到点的传送质量，更需满足端对端的QoS要求。有线环境下基于QOS的路由协议通常与某种资源预留机制如RSVP协议配合使用，满足具有不同信息流的QoS需求。但在移动AdHoc网络环境下，由于其特性，难于实现这种较为精巧的策略，要达到的目的也有所不同。首先，有线环境下基于QOS的路由需要传播网络资源信息，进行资源预留操作，保留信息流的状态信息和可用的网络资源信息。这些开销会在AdH。。网络环境下占据大量信道带宽、CPU处理能力和内存空间。其次，AdHoc网络中网络节点的任意移动可能会使得有关的网络资源发生较大的改变，保存的资源预留的有关状态无效，从而导致以较大协议开销形成的路由无效，并且可能触发更多的路由更新信息。最后，有线环境下的目标是通过选择相应的路由，以保障具有QoS需求的信息流的传输，而AdH。。网络环境下的目标是在所选择路由存在的前提下，提供最有可能满足特定QoS需求的信息流的传播。移动AdHoc网络需要进一步研究的QoS问题包括:1)QoS健壮性问题。不管网络中拓扑结构如何更新都能保持一系列特定的QoS保证则称QoS健壮的。在拓扑更新成功至下一次拓扑变化发生之间的间隔内都能持续保持QoS保证则称QoS可保持。QoS健壮的AdHoc网络的QoS也可保持的，反之不成立。2)具有多优先级的QoS路由策略、算法和协议。 武汉理工大学硕士学位论文3)干扰导致链路质量变化，是QoS具有时效性，需要解决链路连接质量变化的检测和报告方法。3.2移动AdHo。网络QoS衡量参数QoS是用来定量和定性的描述服务的提供者和服务的接受者之间的协商的服务性能，它是相对于Intemet服务中尽力而为服务(Best一Effort)提出来的。根据灯c2386的定义晰!，Q。s指网络在传输数据流时所必须满足的一系列服务要求等，这些服务要求也就是所谓的QoS参数。在通常情况下有网络带宽，传输延迟，延时抖动，差错率、跳数等。在作进一步的讨论之前，先要明确衡量AdHoc网络中路由协议QoS的参数指标。一般来说，AdHoc网络中路由层的QoS应该能够为传输的数据流提供带宽、延时、吞吐量、丢包率等方面的保障。本文也将以这四个参数作为衡量协议性能的标准。下面给出本文采用的这四个参数的具体概念。l)带宽B数据的传输速率。单位为比特/秒。对于多媒体文件来说，其传输所要求的平均带宽。B=F*R*C(3.1)其中F为单位时间内播放的帧数(帧/秒)，R为图像的分辨率，C为压缩编码的速率。2)端到端延时T数据包从源端发出，到被目的端正确接收所经历的时间延迟，单位为秒。T=艺t(毛(I)+Tp(I))+T。(S，D)(3.2)其中，I为选定路由包括的各节点，S为源节点，D为目的节点，T，为数据包的传输延时，Tp为处理延时。T二。p，为信号在无线信道中的传播延时，它们进一步可以表示为:Tt(D=S内/Ba(I)(3·3)Tp(I)=Tw(D+Td(I)(3.4)其中s内为数据包的大小(比特)，Ba(I)为节点I实际能够利用的有效带宽(比特/秒)，Tp(D为数据包在节点I的处理时间(秒)，它又包括了在节点I的队列中的等待时间Tm(l)和真正的数据包被处理的时间Td(l)对于多媒体文件来说，其传输 武汉理工大学硕士学位论文所要求的平均延时必须满足TB，T‘B，艺Tij一s一t一x一y>/一nnumofnodes的值指定了场景中的总共有多少节点。一pPausetime指定了节点在运动到一个目的地后停留的时间，如果设为o，则节点不停留。一5maxsPeed指定了节点随机运动速度的最大值，单位是(m/s)，节点的运动速度将在(o，maxspeed)中随机选择。一tsimtime指定了模拟场景的持续时问(单位为s)。一xmaxx指定节点运动区域的长度(x车由方向，单位为m)。一ymaxy指定节点运动区域的长度(y轴方向，单位为m)。outdir/scenario一file指定了生成场景的输入文件。节点的运行速率和初始位置均随机设置，在整个仿真时问内模拟出各节点的随机运行场景。具体参数如下:(l)网络拓扑:生成50种随机拓扑，每组节点对应10种，节点个数分别为10、20、40、50和100，最后的数据为10种拓扑所产生数据的平均值。场景在1000:11*l000m的空间内。(2)节点移动模式:节点的停留时间为0s，平均速率在O一40而s之间。(3)节点通信模式:由cbrgen工具随机设置，分别随机产生6对、12对、24对、30对和60对ebr流，发包率为1.0，包大小为51Zbytes，网络的初始连通度为0.“6，带宽为ZM，节点的发射半径为250m。(4)M[AC协议:采用IEEEso2.11。(5)仿真时间:3005。其中cbrg即命令格式如下:nsebrgen.tcl[一tyPeebr}tcP][·nnnodes][一seedseed][一mcconnections][一raterate]砚冲e该参数指定了产生的是tcP流还是cbr流。一nn通过nodes的值指定节点的个数。 武汉理工大学硕士学位论文一seed指定了随机数种子。一mc这些节点之间的最大连接数。一rate指定连接间的流的负载量。如果是cbr流，则包长固定slZByte，rate指定的是每秒发送多少个包。此外，信道和无线模型采用TwoRayoroundReneetionMode，在MAC层使用正EE502.1一的DeF(Distributedeoo川inationFunction)1491。DeF是移动^dHoe网络在独立的网络配置下共享无线信道的基本接入方式。对单播数据包它使用RTS/CTS心AT刀ACK模式，对多播数据包则采用直接发送模式。使用带确认的载波监听多路访问/冲突避免(earriersenseMultipleAeces以CollisionAvoidance)模式监听信道的空闲状态。在这种模式下，如果数据包过长，则采用分段机制，在我们的实验中没有采用分段机制，因为实验中的数据包很小，所以采用分段机制会造成的额外负载将会降低网络的整个吞吐量。通过adho。，tcl生成trace结果输出文件，再借助awk脚本使用gawk命令统计traee信息，命令为:gawk一fadhoe.awkseene.tr，最后用gnuplotl具作图。adhoc.tcl文件源代码如附录一。adhoc.awk文件源代码如附录二。4.5仿真结果分析4.5.1平均延时分析图4一3是网络拓扑节点个数对平均延时的影响，由此图可知，当节点个数小于20时，四种协议的延时下降，当节点个数大于50时，四种协议的延时都明显增大，这表明在拓扑结构增大的时候，数据包在接口队列中等待的时间增加，使得其相应延时加大。其中DSR和TORA表现出了较大的延时，DSDV和AODV延时较小，主要原因是DSR寻路的时候首先查找cache中的路由信息，对于陈旧的信息没有采用计时器来进行门阀值的限定;而TORA路由协议只对拓扑结构发生改变范围内的节点存储其路由信息，相应地缺少远处节点的信息，因此二者均表现出了较差的延时特性。DSDV是一种表驱动的路由协议，节点存储了拓扑的全局信息，所以路由延时较小，而AODV寻路时采用按需路由的方式，但在路由维护阶段采用表驱动的方式，故也表现出了较好的延时特性。当节点个数增加时，DSR的延时一致大于AoDv的延时。而文献【46」中给出 武汉理工大学硕士学位论文了当节点暂停时间长时DSR的延时大于AoDV的延时，当节点暂停时间短时则相反，文献【50〕给出当源节点个数小于20时，DsR延时小，大于30时，AODv的延时小，由此可见，由于仿真模型设计的不同，相同的协议得出的结果却不一致。，呼民浦甘.脚I咧介TORA叭D、.、sR呼月().1P助的.，‘，·-习‘..勺︺乃‘J山l民，匀︺伪J﹄叹J月人、、入、_.二汤袱茶一嘴淤一.、、第一一狱102030405060708090100njmberO犷nodeS图4一3平均延时与节点个数的关系4.5.2抖动分析抖动主要反映了协议传输数据的稳定性，对于视频流业务尤为重要。图4一4是网络拓扑节点个数对抖动的影响，如此图所示，当节点个数小一J几3即寸，DS0v抖动情况最小，性能最优，其次是AODV、TORA和DSR;当节点个数人J几301(lj小于50时，AODV性能最优，DSDV次之，值得注意的是在上述两种情况之下，AODV、DSR、TORA均表现不同程度的下降趋势，其中DSR下降的最明显，而DSDV在节点个数大于2即寸，一直表现上升趋势;当节.点个数大于50时，四种协议均表现为上升趋势，其中DSR上升最为显著;在整个的仿真过程中，我们发现TORA表现较为平缓，DSR反差较大，且四种协议随着节点数的增多，抖动不是一直表现为上升趋势，而是先下降后上升，其中AODV上升斜率最小，也表现出了最优的抖动性能。4.5.3包投递率分析包投递率是指源节点发送的数据包中目的节点正确接收到的数据包所占的比率。包投递率的大小能说明协议的可靠程度。图4一5是网络拓扑节点个数对包投递率的影响，如此图所示，除DSDV协议外，当节点个数大于20时，其他三种 武汉理工大学硕士学位论文路由协议的包投递率随着节点的增多而下降。在节点个数小于50时，DSR的包投递率最大;大于50时，AODV的包投递率最大，说明其可靠性高，这与文献【46]中的结论基本一致(文献[46】中的节点个数为60);当节点个数大于30时，TORA的包投递率最小。在整个的仿真实验过程中，DSDV的包投递率比较平稳，这是因为DSDV是一种表驱动路由协议，节点存储了整个拓扑的全局信息，使寻路成功率较高。刁4b人j孟口OSDVwe闷卜一AODV一仑一OSR一奋~.pp).(助名‘盆‘的·;p~11246c020oTORAee命ee/，入、.戈“皿尸、、、，’<之称，.’、_应，-一一一丁卜一一~102030405060708090100nUm匕ero犷node公图4一4平均抖动与节点个数的关系助26543987。01000Q0000衬P名润叫p()。，O.o.衬工盆‘.，J‘。AOS。D，V一_王十~’--一~一、’DSR一」卜一一~一_，TD舶一嘴卜一1020的40加6070的90100口.翻七曰、0犷朋由8图4一5包投递率4.5.4效率分析效率是指一定的控制报文(路由负载)能够传送数据报文(有效吞吐量)的比 武汉理工大学硕士学位论文例。效率的大小能反映协议对网络资源的利用情况。图4.6是网络拓扑节点个数对效率的影响，由此图可知，当节点个数增加时，AODV和DSR路由协议的效率均有所增大，并且当节点个数小于50时，DSDV表现出了最好的效率特性，其次是AODV和DSR;大于50小于75时，AODV的效率最好，其次DSDV和DSR;节点个数大于75时，AODV的效率依然最高，但此时DSDV效率小于DSR。此外，四种协议随着网络规模的扩大，表现出了三种不同的发展趋势，AODv和DSR表现为先上升后下降，DSDV恰好相反，TORA则一直呈下降趋势，这说明在高速移动、大规模的环境中AODV的效率高，而随着节点个数的增多，DSR也表现出较好的效率特性，而TORA的效率最差。有趣的是四种协议的效率都小于1，这说明传送的控制报文的容量要人于实际传送的数据报文的容量，也就是说发送IBYTE的数据报文需要大I’-1B丫TEI’内控制报文进行辅助。因此我们开发新的协议的时候需要特别注意，尽主!吏使)IJ址少的控制报文传送尽可能多的数据报文，以此来提高协议的实际效率。月65430987山0000200000上仁认广衬队日卜卜︸尸..，茶朴带令.J.汁1..41!l戮‘丁吉二二李叹二，’衬年)润叫(‘筑。年丝‘一一协一食一，----，一DSDVAODVDSRTORA102030405060708090100nUmberofnodeS图4一6效率与节点个数的关系4.6性能比较通过分析仿真结果可知，TORA由于路由负载较低，可扩展性好，可以作为底层协议，不能适应无线组播的路由算法提供服务;DSR路由负载适中，在中小拓扑结构内，包投递率最大，效率居中，延时较大，适合于中等规模的网络环境和对延时要求不高的环境;DSDV由于要维护全局信息，当拓扑结构变化频繁时，开销很大，所以其不适合大规模高速移动的无线环境;AODV表现出了最小 武汉理工大学硕士学位论文的延时、较优的包投递率及最大的效率，其可扩展性及适应能力最强。表4一1给出了四种路由协议的数值比较(在无线网络节点较多的情况下)表4。1AdHoc网络四种路由协议的性能比较乓、乓、裔婴婴AODVVVDSRRRTORAAADSDVVV延延时时良良差差中中优优抖抖动动优优差差中中良良包包投递率率优优中中差差良良效效率率优优良良差差中中协协议开销销中中良良优优差差可可扩展性性中中良良优优差差支支持多播播支持持不支持持不支持冲冲不支持持注:不支持*表示TORA本身不支持多播，但运行TORA上的LAM可支持多播4.7小结本章首先介绍了NSZ和仿真的具体过程，然后参考相关文献，分析现有的路由协议仿真模型，最后在一个高速运动、节点密度逐渐变大的环境中进行仿真，从延时，抖动，包投递率和效率等来考察AooV，nSR，TORA和oSDv路L上l协议的性能，对文献[44]、[45]、[46〕和[47〕中的相关结论进行了补充和完善，为进一步研究支持QoS的AdHoc网络单播和多播路由算法做铺垫。 武汉理工大学硕士学位论文第5章一种基于延时约束的AOOV改进协议设计与实现5.1引言随着移动AdHO。网络的迅速发展，人们提出在移动AdHoc网络上传送综合数据、声音和三维图像等综合业务的要求，希望能像固定的有线或蜂窝无线网络一样为不同业务的服务质量提供保障，因此，在AdHoc网络中，如何合理、有效的利用无线网络资源，提高数据传输性能，为各种业务提供服务质量保障，即AdHoc网络对QoS支持是一个很重要的问题，而QoS路由则是Q。S保障中的关键因素。QoS是网络在传输数据流时要满足的一系列服务请求，QoS路山指标代表了网络的特征，因此，它们是决定QoS路由算法的复杂性和可支持QoS保证的范围的主要因互素。需要考虑的因素主要有:l)对任何选择的路由指标而言，必须存在计算路径的有效算法以保证路山协议能够扩展。2)路由指标必须反映网络的基本特性，约束条件应当包含支持基才‘QoS需求的信息。3)路由指标之间必须是相互正交的以保证路由指标不包含冗余信息。这些路由指标可以具体量化为带宽、延时、路由生存时间和分组丢失率等QoS指标。下面是这些QoS指标的分类和特性。对于任何路径尸=j~k一…‘l一fn，(j，K…，l，m代表网络中的节点号)，称QoS参数d是:可加性参数:当满足条件d(P)=d(i，j)+do，k)+d(l，m)可乘性参数:当满足条件d(P)=d(i，j)+do，k)*d(l，m)最小化参数:当满足条件d(P)=min{d(i，j)，do，k)，d(l，m)}带宽和路由生存时间属于最小化参数，延时属于可加性参数，数据分组丢失率属于可乘性参数。多个QoS路由指标可以更准确地模型化一个网络，但是寻找满足多个QoS路由指标约束的路径是很困难的，解决此问题的多项式算法 武汉理工大学硕士学位论文可能不存在。因此，在设计QoS路由协议时，应当综合考虑QoS路由协议所提供的QoS性能和它所带来的计算耗费以及协议开销这些因素。本章提出了一种保证实时传输的路由协议RT一即(QoSRoutingProtocolbasedonRealTime升affie)，该协议是在传统AODV协议进行改进与优化，使其满足通过延时约束来选择路由，同时为了能够有效的减少路由重建的开销，增加了备份路由机制。5.2端到端的延时估计与优化盯卫RP协议以端到端的延时作为Qos指标，那么有必要通过有效的方法对端到端延时进行估计，从而获得较为准确的QoS指标。对于同步网络，端到端的延时是很容易计算的。只要用目的节点收到数据包的时刻减去源节点发送数据包的时刻就可以了。在异步网络中，这个问题就变得复杂起来。根据AODV协议的路山建立基本过程(即源节点广播路由请求，目的节点收到路收请求即按照翻转路径向源节点返回路由恢复)，可以考虑利用这个路由建立过程的双向延时(源节点一>目的节点一>源节点)来估算下行延时(源节点一>目的节点)。下面将证明这个估算是合理的l川:端到端延时T定义如下:端到端延时T:数据包从源端发出，到被目的端正确接收所经历的时问延迟。单位为秒。T=乙(界(I))+TP(I))+T，，。，(S，D)(5·l)其中，I为选定路由包括的各节点，S为源节点，D为目的节点，T，为数据包的传输延时，T，为处理延时。TproP为信号在无线信道中的传播延时，它们进一步可以表示为:T，(I)=S户/B。(I)(5.2)T，(I)=T，(I)+T‘(I)(5.3)其中s沙为数据包的大小(比特)，Ba(I)为节点I实际能够利用的有效带宽 武汉理工大学硕士学位论文(比特/秒)，T，(I)为数据包在节点I的处理时间(秒)，它又包括了在节点I的队列中的等待时间T，(I)和真正的数据包被处理的时间Td(I)。对于多媒体文件来说，其传输所要求的平均延时必须满足T目的节点一>源节点的双向延时.T*、，:下行链路的延时(源节点一>目的节点).Tur:上行链路的延时(目的节点一>源节点)另外假设:.所有节点具有相同的处理能力.所有节点具有相同的信道带宽.无线信道是对称的.路由请求包和路由回复包的大小相等设有数据流j，取路由s一>A一>B一>c一>D，S是源节点，D是目的节点，A、B、C是中间节点。根据公式5.1一5.3，有几矿乙四麻界(I)+几(I)]+几研s，D)=乙四耐蕊了Ba仍+Tw仍+几仍卜TP衫S，D)其中DOWN={s，A，B，C};凡=乙。[Tt(，)+TP(，)]+丁脚(D，习 武汉理工大学硕士学位论文=名。[Srer/Ba仍+Tw(I)+几(I)1+几研D，习，其中UP={D，C，B，A};根据假设，T，，(S，D)=TproP(D，S)，且所有节点的实际处理延时TJ相等。另外，由于无线节点只有一条信号发送通道，因此对于中间节点来说，其队列中的上行数据包和下行数据包经历的平均等待时间也是相等的。所以，上下行延时的差为:T叮二Tdo，一T，=(T，·(S)一T，l(D))+(艺，。。o，，;，(S。。/B‘，(I))一艺，。‘，(S、/B‘:(I)))“(T，(S)一T，(D))+艺[(Sre，一S、)/B(.2)]“(T，(S)一T二(D))第二个近似成立的原因是一般情况一凡S、与S、。相差不过儿}’，么黔至儿个比特而己。理论上，要使选择的路由满足数据流的端到端延时要求，应有:Tdo、l，’T}T，‘ZT]二尸【T;>ZT一丁那}T;‘ZTI“T雌/ZT 武汉理工大学硕士学位论文相对于T，7谕的值是很小的。而且，厂够的值只与源结点、目的节点的队列等待时间有关，与所选择的路由基本没有关系。因此，用T;/2，来估计Tuo.是合理的。还需要说明的是，在带宽条件满足的情况下，网络能够为数据流的传输提供稳定的延时，因此我们推断如果路由建立过程中估算的传输延时能够满足数据流的延时要求，那么数据流实际传输的延时也能满足要求。这样就能得到:当源节点收到来自目的节点的路由回复(能够收到的路由回复都是满足延时要求的，下面还会具体说明)时，根据当前时间与其发送路由要求的时间算出T，，并与数据流允许的最大延时作比较，最终决定是否可以利用这条路由来传输数据流。T;‘ZT，能够传输数据流(5.5)了;>ZT，不能传输数据流端到端延时估计的优化如下:在传输过程中，当源节点发送的REQUEST包达到目的节点时，如果此时的Tdo.，已经超过了T时，即T*>T时，我们认为此时此刻该路由己经不满足延时了，所以我们可以直接丢弃该REQUEST报文，没有必要再去统计T;了，这样减少了一定的路由开销。优化后的5.5式:Tdo，”、T且Tr‘ZT，能够传输数据流{(5.6)Tdo，>T或T;>ZT，不能传输数据流5.3RT_QRP协议描述盯-QRP协议是传统AODV协议改进而来，主要改变有:在路由条目中增加延时信息，在路由请求分组扭。uteRequest)、回复分组(RouteReply)中增加了新域:延时，并在路由发现和路由维护中加入QoS机制，最后加入备份路由机制。 武汉理工大学硕士学位论文5.3.IRT_QRP协议模型盯一QRP定义了一个移动AdHoc网络的拓扑结构为一个加权图侧v，E)，v代表网络的节点集合，EgV，V代表网络中连接节点对的通信链路集合。如果两个移动节点间的距离小于或等于节点通信的有效距离:时，则称这两个节点互为邻居节点。}vl和lEl分别表示网络中的节点数和链路数，}茂}表示节点i的度。定义节点x的邻居节点集点万二=={n，ld(x，n，)(r，x半nj，n，任V，j簇I拟[}，万二集合随着时间而变化。在G(ME)中，考虑源节点到目的节点的Qos约束的路由问题，即给定一个非空集合M={s，u}，其中，Mgy，s为源节点，u为目的节点。寻找的Qos路由p一(犷，，E，)，其中犷，gV，万，二E。定义5.1在侧ME)中，假定路由请求的最大延时约束为D，对于丫(i，j)EE，L(i，j)为从节点i到节点j的路径，若L(i，j)满足:D(i，j)簇D，则称此路径以ij)为可行路径。定义5.2在G(V，E)中，对于源节点s，目的节点u，假设G(R)为满足上述延时约束的可行路径集合，则我们要寻找的QoS路由P应满足:S(p卜max(s(G，)，G，EG(R))。p是节点s与节点u间最小代价的可行路径，称为最佳路径，P即为RTeeQ”所选择的QoS路由。5.3.ZRT_ORp协议包结构表5.1给出RTeeQ”路由请求包(RouteRequest)结构。表5.2给出RT_Q”路由回复包(RouteRePlv)结构。表5一IRT一”路由请求包(RouteRequest)盯盯‘QRP包类型型保留字段(16bit)))跳数(sbit)))路路由请求广播ID(32bit)))目目的节点地址(32bit)))目目的节点序列号(32bi)t))源源节点地址(32bit)))源源节点序列号(32bi)t))时时间戳(32bit)))请请求最大延时(32bit) 武汉理工大学硕士学位论文表s一2盯一”路由回复包(RouteReply)盯盯卫RP包类型型保留字段(16bit)))跳数(sbit)))路路由请求广播ID(32bi)t))目目的节点地址(32bit)))目目的节点序列号(32bi)t))源源节点地址(32bit)))路路由维持时l’ed(32bit)))时时间戳(32bit)))请请求最大延时(32bit)))5.3.3路由发现RT一”是一种按需的路由协议，因为延时约束机制的引入，所以中间结点收到RouteRequest包时，即使存在到达目的地的QoS路由，也不能回复，必需继续转发该请求包。同样，中间结点收到RouteRePly包时，也不能通过己建一立的路由发送数据。如图5一l所示源节点S到目的节点D的路由建立过程。OOOC)/尹。。_气以布_。斑坦QBaC匆筛ardPoint叮R只即图5一1路由建立过程下面是具体流程: 武汉理工大学硕士学位论文l)当源节点S要发送数据时，先检查它的路由缓存，如果有满足Qos约束的到达目的节点的可行路径，则源节点在可行路径中选择最佳路径发送数据分组。如果在路由缓存区中没有可行路径，则节点将启动路由发现过程，发送路由请求分组(RouteRequest)。2)源节点s广播对目的节点D的路由请求RouteRequest，请求分组里包含请求延时信息、路由发现发起时刻。3)当中间节点接收到RouteRequest分组时，如果收到过该分组，则丢弃，如果没有收到过，则将该分组中的上一节点的地址加入到的反向路由链表中，并更新路由表，转发该RouteRequest分组。4)当目的节点D收到该RouteRequest分组时，将比较延时，如果满足就向源节点发送RouteReply分组，该分组中将记录对应的RouteRequest分组‘t，的路由发现发起时刻及延时信息，否则，丢弃该RouteRequest分组。5)当中间节点收到RouteRePly分组时，建立正向路由链表，向源节点转发该RouteReply分组。6)当源节点S收到RouteRePly分组时，通过5.6式判断延时是否满足，若满足则更新路由表，在可行路由中选择延时最小的作为最佳路由，少1几发送数据包，否则，丢弃分组。图5一2是接收到RREQ后的处理过程流程图，图5一3是接收到RREP后的处理过程流程图。5.3.4路由维护移动AdHoc网络中节点的移动特性决定了网络的拓扑随时可能变化，建祝的路由可能断裂，也可能不再能提供所要求的QoS保证。因此，在AdHoc网络中，实时有效的QoS路由维护也是非常必要的。由子节点的移动可能造成己有链路的断裂，AODv提供了两种方法用以检测无线链路的断裂。一是通过链路层的反馈信息;二是通过路由层定期发送的HELLO包。对于路由层的探测机制，具体的说，就是每个节点都定期(HELL0we仆汀E孙从L)广播HELLO包，并且通过收到的其他节点的Hell。包来获得其邻节点的信息。如果在预定时间段但ELETEeePE犯OD)内，节点没有收到某一邻节点的Hall。信息，便认为节点到这个邻节点的链路断裂了。如果链路的断裂影响了正在传输数据的路由，那么源节点也将重新发起路由建立的过程。 武汉理工大学硕士学位论文接接收到RREPPP更更新路由由派派黔~骂’鉴一一..奢一一根根据时间戳参数和当时时刻估计时延延将下游节点加入到本节点的正向路由由链链链中中手手巡乡万万.吮攫墨了了更更新路由表表丢弃RREP包包更新RREP包的跳跳丢弃RREP包包数数数数及源地址址址发发送缓冲区中的的的立即向上游节点点点数数据据据转发RREP包包包更更更更新反向路由链链链结结束束图5一2RREP的过程流程图本文建议的RT_Q”协议将利用路由层的反馈信息来测链路状态，原因是文献[52〕中己经比较上述两种检测方式的性能，并证明利用链路层的反馈信息在控制负载、路由建立时间、路由恢复时间等方面的性能均优于利用路由层的定期广播机制。5.4增加备份路由机制5.4.1备份路由的作用根据本文延时估计模型所描述的，每次估计延时时都需要控制报文从源节点到目的节点一个来回的时间，QoS路由的发现代价是很高的，当QoS路由发生.断裂或是原QoS路由条目失效时，源节点将不得不重新执行路由发现过程，这在大规模网络应用下，网络开销是相当大的。此外，AODV采用的机制是将新. 武汉理工大学硕士学位论文找到的路由与路由表中的路由比较，如果新路由较优，则用新路由条目覆盖旧的路由条目，否则丢弃新路由，然后发送数据，等待下一条新的路由到来，显然这样做存在很大的局限性，在这种机制下，一些较优的可行的QoS路由也被丢弃了。因此增加了备份路由机制能够有效的减少路由重建的开销。接接收到RREQ包包诀诀.攫是燮鳖鹦哗一一爪一一更更更新反向路由链链更更更新路由表表\\\本节“地址是“是Request夕///丢丢弃弃。。。樱更新广缨播链链J‘嘿/否否RRRREQ包包包包包包包包包包包包包包包包包包包包包包包汾汾汾矍笋了了更新新发发发送Reply的的丢弃RequestttRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRe;q!:u广es播播t包包报报报文回复复包包包销销销毁原Requesttttttt报报报文文文文结结束束图5一3RREQ过程流程图5.4.2备份路由的设计关于备份路由的算法主要包括三个方面:1)当源节点收到RouteReply包时，首先比较是否有新路由，如果有，则删除旧的路由条目链，增加将新的QoS路由条目链，否则将新的QoS路由与同序列号的路由条目上比较，如果延时小于原来路由条目中最大的延时时，则覆盖掉旧的，并保持整个链表是有序的。否则，丢弃新的QoS路由。 武汉理工大学硕士学位论文2)当路由发生断裂，源节点收到错误分组后，就必须查找备份路由，以取代现在的失效路由。如果没有备份路由，则删除整个备份路由链，重启路由发现过程。3)在所有路由条目中增加该链表上路由条目的计数和备份路由的链表。因为备份路由本身要消耗资源，如果增加的备份路由链表过大，那么在存储上将占用大量的内存，在查找时也会占去大量的查找时间，增大了延时，所以本文将新增加的链表上的计数设为3，即在有一个最佳路由的情况下，最多只能有2个备份路由。并且这3个路由条目是按延时从小到大排序的，链头为最佳路山.，5.5协议正确性证明和复杂性分析定理IRT一RP协议的路由选择是无环的。证明假设p是一个以D为目的探测帧，而S(P，D)是路由算法选择的路径。若S(P，D)中存在一个环路，则说明在路径S(P，D)上存在一个节点j两次收到了探测帧p并转发p。又因为盯贝”延用了原AODv的广播机制，所以这与RT_QRP协议中根据<源地址，广播ID>判断是否收到过该请求消息，如果收到过则丢弃请求消息矛盾，因此，S(P，D)必定无环。证毕。定理2RT一Q即协议的路由算法中，时间复杂性为O(21;)。式中:h为AdHoc网络中各条路径中链路数量的最大值。证明在RTesQ即协议的路由算法中，需要发送探测帧来建立路山，成功建立一条路径需要花费的时间开销是一个来回的时间。假设消息每经过一条链路花费的时间开销是一个单位，而假设h是被选择的多路径中链路数量的最大值，则RT_QRP协议算法路径建立的时间复杂性为o(2h)，证毕。5.6仿真实现5.6.1协议的修改本次使用的仿真程序仅以延时作为参数，程序的实现是在ns一2.29版本下完成，主要对ns一2.29下的aody协议进行了修改，涉及到文件有aedy夕acket，h，aodveePacket.ee，aody.tcl，aody--rtable.h，aody--rtable.ec，aody.h，aody.cc，主要修改内容如下: 武汉理工大学硕士学位论文1)修改路由条目，增加延时变量，备份路由链表及计数，并在构造函数中初始化。2)修改路由请求、回复包头，增加延时变量，并修改包头大小变量52。3)修改sendRequest、recvRequest、sendReply、reevReply等函数。5.6.2性能评价参数使用的性能评价参数主要包括:1)平均分组投递率=目的端收到的数据包数/源端发送的数据包数。2)路由控制开销=发送的路由控制分组总数/发送的数据分组总数。3)平均端到端的延时=艺(数据分组i接收时刻一数据分组i发送时刻)/接收数据分组总数。5.6.3仿真环境和参数设定l)网络拓寸l、:随机分布节点数为100，场景在1200m*1200m的空I司内。2)节点移动模式:节点随机移动，最大速率40而s。3)节点通信模式:数据流类型:CBR，发包率为1.0，包大小为51Zbytes4)MAC协议:采用IEEE802.ll。5)无线电传播模型:模型采用Two一RayGroundRefleetionModel，载频是gl4MHz，带宽为ZM。6)天线类型:天线采用omniAntenna。每个仿真取5个随机场景平均值的结果，用脚本语言awk统计NsZ产生的裸数据，并用gnuplot工具作图。5.6.4仿真结果分析从图5一4可以看出，在100个节点的网络中，不同网络连接数下，RTQRP协议的平均包投递率比AODV协议要高，虽然当连接数增大时，总体上两协议都逞递减趋势，但连接数较大时，两协议差距较大，特别是网络中连接数超过50个后。这是因为在协议中支持了延时约束和备份路由，体现了RT一即的优越性。从图5一5可以看出，盯卫RP协议的平均端到端的延迟比AODv要少很多， 武汉理工大学硕士学位论文且随着网络连接数的增大，虽然总体上逞递增趋势，但两协议延时有差距，特别当连接数超过50后，这是因为在协议中支持了延时约束的要求，整体上降低了网络中传输的延时。0。95r.~~~~~~，产~~~~---甲-.~，~------，.-U八八八八...6。的巧﹀︺︺...旧5768P名叫叫‘忿o..p1pd‘，‘;八叼八V八V六·、、‘、RT_ORP~吮卜weAODV一住三一.102030405060ConneCtion图5一4平均包投递率与连接数的关系RT_QRP一.沐一~AOOV一份一工P!()助.仍‘角，I矽‘吧吧/"了一0八八V叼六叼勺8月b口‘kf止︸.﹄.户狱滋.沪102030405060COnneCt主On图5一5平均端到端的延时与连接数的关系从图5一6可以看出，不同连接数下的，路由控制负载的变化情况，总体上，随着网络连接数的增加，两协议都逞递增趋势，虽然RT一”协议的路由控制负载略高于AODv的，但是并没有很大差距，特别当连接数超过50后，盯一Q”的增加相比AODV更趋于平稳，这是因为由于协议对延时的约束，导致在路径的选择中增加了许多控制报文，使得路由控制负载的增大，备份路由的机制也减少了一些路由控制的负载，总体上达到了预期的效果。图5一7反映了在100个节点的网络中，不同最大节点移动速度下，两协议的 武汉理工大学硕士学位论文平均分组投递率的变化情况，盯-Q即协议的平均分组投递率比AoDv协议要高，虽然当节点移动速度增大时，总体上两协议都逞递减趋势，但节点移动速度较大时，两协议差距较大，特别是速度超过30后。这是因为在协议中支持了延时约束和备份路由，体现了义几Q即的优越性。O。7盯~QRPee嵌...以刃V目~曰一.工矽P丈叫O二心‘O心pJ00七心李0‘0。650。55/不0.510203040ConneCtion图5一6路由控制开销与连接数的关系。‘”厂RT_ORp一+..一O。96’杯AOOV，~·份一叫P名p叫。‘.吧J‘o汤;工p立‘八VO八V八:.89V84?权?、，/、·、、O。86O。84510152025303540川口X价OVesPeed(m/s)图5一7分组投递率与节点最大移动速度的关系图5一8给出了在100个节点、连通度为30的网络中，不同的最大节点移动速度下，平均端到端的延时的变化情况，可以看出，盯-Q即协议的平均端到端的延迟比AODV要少很多，随着网络节点移动速度的增大，两协议总体上逞递增趋势，但盯一QRP协议延时增长较快，特别是速度超过30后，这是因为虽然在协议中支持了延时约束的要求，整体上降低了网络中传输的延时，但是由于延时估计模型的限制以及在高速网络环境下，网络变化太快给备份路由机制带 武汉理工大学硕士学位论文来了影响，总体上来说，达到了预期效果。RT_ORp一带一0。18朗口Vwe毛卜.1()润罕梦.矽.的a夕.0。160。14O。1_/O。1200八V008604扩卜一曰510152025劝面40肋x加vesPeed(m/s)图5一8平均端到端的延时节点最大移动速度的关系从图5一9可以看出，节点最大移动速度不同时，路由控制负载的变化情况，总体上，随着网络节点移动速度的增加，两协议都逞递增趋势，虽然RT_Q即协议的路由控制负载略高于AODV的，但是;卜没有很大差距，特别当速度超过30后，RT一RP的增加相比AODv更趋于一平稳，这是因为由于协议对延时的约束，导致在路径的选择中增加了许多控制报文，使得路由控制负载的增大，备份路由的机制也减少了一些路由控制的负载。RRRT一QRp~邻‘一夕吐吐叫p丈P叫OOU‘O‘心叮O，p山山O‘一一“0vD一和..不夕厂---:::厂了{{{厂厂‘……图5一9路由控制开销节点最大移动速度的关系5.71」、结本章首先分析了端到端的延时估计，然后提出了盯-Q”协议模型，分析 武汉理工大学硕士学位论文其包结构，路由发现和路由维护，分析了备份路由的作用和设计思路，证明了协议的正确性，分析了协议的复杂性。最后在NSZ仿真平台下对AODV和RTeeQRP协议进行了性能分析和正确性验证，仿真结果表明，与经典的AODv协议相比，RT一”协议减少了路由开销，提高了包投递率，降低了延时，改善了网络的服务质量。 武汉理工大学硕士学位论文第6章一种基于路径稳定性的005路由协议只1日l省，“.J二刁随着无线网络中多媒体应用的需要，研究工作已经开始关注在移动AdHoc网络中提供QoS的问题，并提出了一些用于移动AdHoc网络的QoS路由协议。比如CEDAR，TBP，sTARA协议，但是这些QoS路由协议主要集中研究如何在两个节点之问找到满足QOS条件的可行路径而没有考虑可行路径的稳定性。实际上即使在移动AdHoc网络中我们能够建立这样一条可行路径，也会由于节点的运动而导致可行路径上的链路经常破裂，从而必须重构路由。针对移动AdHoc网络的特点和应用需求，在综合考虑路径稳定性的基础!几，以带宽为主要的Qos参数，提出了墓于路径稳定性153】的QoS路由协议PS_Q朋(QoSRoutingProtoeolbasedonpatllStability)。6.2带宽问题在基于时隙的网络中，我们可以将带宽定义成“空闲”时隙的个数。那么链路带宽就是相邻两个节点的公共空闲时隙数，两个节点的路径带宽则是它们之问可用时隙的集合。当两个节点是相邻节点时，路径带宽就等于链路带宽。在一个无线网络中由于数据发送者和接收者使用同样的频率波段，使得两者不可能在同时使用同一个公共可用时隙发送和接收数据。考虑图6.1的带宽计算问题。在图6一l中，假设节点A，B，C，D的可用时隙分别为毛l，3，5}，厦l，2，3，4}，麦l，2，3，5}和{2，3，4，5}。根据链路带宽的定义，链路AB，BC，CD的带宽分别为夏l，3}，{l，2，3}和{2，3，5}。记Bw(X)表示链路或路径x的带宽，则有Bw(linkAB)=2，Bw(linkBC)=3，Bw(linkCD)=3。值的注意的是，路径AD的可用带宽并不等于所有链路带宽的最小值，即Bw(PathAD卜min(Bw(linkAB)，aw(linkBC)，Bw(linkCD))，同时也有Bw(pathAD卜min(Bw(link(AB)，Bw(PathBD))。实际上，Bw(PathAD卜1而Bw(pathBD)=2。这是因为中间节点(例如节点B)不能在同一个公共可用时隙上既处于传输模式又处于接收模式。节点A不能 武汉理工大学硕士学位论文同时使用时隙l和3来向节点B发送分组，而只能用时隙l或3。如果节点A使用时隙3，节点B就只能使用时隙1或2来转发来自节点A的分组。因此路径AD的可用带宽大小为1而不是2。同样对于路径BD，节点B不能同时使用时隙厦1，2，3}向节点C发送分组，而只能使用时隙{1，2，3}两两的任意组合(例如1，2)。如果节点B使用时隙{1，2)，那么节点C只能使用时隙价{3，5}来转发来自节点B的分组。因此路径BD的可用带宽大小为2而不是3。份竺丈)生O喇~④{l，3，5}{l，2，3，4}夏l，2，3，5}夏2，3，4，5}图6-1带宽计算一般来说，在一个基于时隙的无线网络中计算路径的可用带宽不但需要知道路径上链路的可用带宽，而且需要知道如何调度空闲时隙。因此，在多跳的移动AdH。。网络中可用带宽的计算变得比较困难，实际上它是一个N’P难问题。为了解决这个问题，在基于路径稳定性的Qos路由协议PS一即中，我们使用启发式算法来计算和预留带宽。为了避免“隐终端”问题，可以在时分多址TDMA(TimenivisionMu一tipleAeeess)的基础上，使J}J码分多址CnMA(eodeDivisionMultiple^ceess)方案。通过使用经典的同步方案，整个网络在帧和时隙的基础上进行同步。每个帧又由固定数目的时隙构成，如图6一2所示，这种帧分为控制阶段和数据阶段两部分。控制阶段的时隙小于数据阶段的时隙。它主要完成所有相关的控制功能，包括帧和时隙的同步和能量的测定。帧结构{控制阶段性.”一’}数据阶段}图6一2帧的结构启发式带宽计算算法的基本思想是，从源节点到目的节点以逐跳方式来计算可用带宽。源节点首先将它的空闲时隙信息传递给离目的节点更近的一个邻节点，这个邻节点计算它到源节点的可用链路带宽。然后把这个可用链路带宽信息传递给离目的节点更近的邻节点。中间节点利用收到的带宽信息，计算出当 武汉理工大学硕士学位论文前节点到源节点的带宽。最终，目的节点使用它收到的带宽信息可以得出整个路径的带宽。6.3PS_QRP协议6.3.1PS_QRp协议模型目前所提出的Q。S路由协议主要关注于如何在源节点和目的节点之问找到一条满足QoS条件的最短可行路径，而没有考虑可行路径的稳定性问题。由于移动AdH。。网络的高动态性，使得它的拓扑结构不断发生改变。在这种环境中如果不考虑稳定性问题，将不可避免的导致可行路径上链路的经常破裂，使得两节点需要不断的重构路由。基于这一点，本文提出了基于路径稳定性的QoS路由协议PS一RP。协议通过引入路径稳定性因子，来考虑可行路径稳定性问题。目的节点在多条可行路径中选择具有最大路径稳定性因子的可行路径，从而在源节点和目的节点之问建立了一条稳定的QoS路由，大大减少了路由重构的次数。如果具有最大路径稳定性因子的可行路径不止一条，为了减小延时，l_」的节点将从中选择最短的可行路径来建立QoS路由。同时协议在资源预约过程，1，采用了主次预约的思想，即目的节点首先使用最大路径稳定性因子的可行路径来进行主预约。一旦主预约失败，在释放了己预约的资源后，使用具有第二大路径稳定性因子的可行路径来进行次预约，使用这种预约思想能够大大提高资源预约的成功率，从而进一步提高QoS请求的成功率。结合图6一3给出链路稳定性因子LSF(Linkstabi，ityFactor)LBSFFSFXIRx图6一3传输范围 武汉理工大学硕士学位论文L孙’=—=二二乙二二--二二二二二一(6.1)一乙尺兰下一+一乙刀二改一厂丈尺下+丈尺沪其中L雕R:一}XY卜R厂寸(xx一xy尹十认一Yy尹+诊二一凡LBSF=凡一】XY卜凡一了(xx一xy厂+(Yx一称厂+(z:一z，，在式(6.1)中，LFsF和LBSF分别表示链路前向稳定性因子和反向稳定性因子;Rx和RY分别为节点x和Y的无线传输半径;{xy}表示节点x和Y之i飞‘Jii勺距离;(Xx，YxZx)和(X丫Y丫zy)分别表示节点X和Y的位置，它们可以通过全球定位系统(GPS)获得。那么，路径稳定性因子Ps(Pathstability)可定义为路径上所有链路稳定性因子LSF的最小值。即:Ps=min{艺(i.)j。PLSFiIjP15apath斤omsoureenodetodestinationnode}路径稳定性因子PS可以反映出路径的稳定性状况，PS越大的路径越稳定。口的节点根据PS值选择来最佳QoS路径，以保证所建路径的稳定性。6.3.2路由发现PS卫RP路由协议是一个按需路由协议，协议不需要周期性地交换路山信息一当源节点与目的节点进行通信时，如果发现没有去往该目的节点的路由，源节点则向网络泛洪(Flooding)一个RREQ(RouteRequestforQoS)的分组。我们将这个请求分组记为RREQ，其中每个域的具体定义见下页表6一1。为了对泛洪所产生的开销有效的实行控制，减少重复信息的传播，协议使用Source和Sequence_ID来唯一标识RREQ分组。当中间节点收到一个RREQ分组后，根据Source和Sequence--不D来判断是否己经收到过该分组。如果该分组是一个重复分组，则马上丢弃该分组。同时如果中间节点己经在节点列表Nodehst中，中间节点也将丢弃该分组。否则，中间节点将首先使用62节所介绍的带宽计算算法来计算从源节点到当前节点的可用带宽，并将可用数据时隙的信息记录到路径时隙列表数组slot一st一rray中。如果可用带宽不满足QoS要求，这个RREQ分组将被丢弃不再进一步处理。然后，中间节点修改分组的TTL值，如果TTL二O，节点将丢弃该分组。在协议中使用TTL能够有效地限制QoS路由的长度。因为即使在网络中能够找到一条满足QoS请求的可行路径，但是如果该可行路径太长，在移动AdHoc网络 武汉理工大学硕士学位论文动态的环境下来维持这条路径也是非常困难的。同时TTL的使用能够进一步控制泛洪所带来的开销。随后中间节点利用RREQ分组所携带的上游节点的位置信息和无线传输半径以及自己的位置和无线传输半径信息，按照式(6.1)计算出当前的LFS。如果当前的LFS小于RREQ分组中的LSF，则将RRfQ分组中的LSF值替换成当前的LFS。这样，目的节点将得到路径上所有链路稳定性因子LSF的最小值即PS。表6一1RREQ分组域的定义域域名名定义义SSSOUrCeee源节点点DDDestinationnn目的节点点SSSequenee--IDDDRREQ分组顺序号，协议使用该分组顺序号和source唯一一标标标识RREQ分组组PPPacketjyPeeeMMMMM分ain组R类eso型ur，ee包一括eseRrRveEwQeFa，ilR，RReEsoPu，rcCeleeeRae几se双rve_EFQa，，il，，RRRRRoute--Setup_Fail，Route一rror，DATA等类型。。NNNodelisttt源节点到当前节点的节点列表，用于记录路山信息息555Iot_list_arrayyy路径时隙列表数组，用来记录路径上的时隙分配情况况QQQoS_infoooQoS请求信息，这里主要对带宽的要求求LLLSFFF链路稳定性因子子XXXXXX节点X的x坐标，可通过GPS得到到YYYXXX节点X的y坐标，可通过GPS得到到ZZZxxx节点X的z坐标，可通过GPS得到到RxRRxx节点X无线传输半径径TTTTLLL生存时间间最后中间节点将自己添加到路由节点列表Nodelist中，如果该一节，.从不是日的节点，它还必须用自己的位置和传输半径信息来更新RREQ分组中的相应域，并将该分组以泛洪的方式发送出去。中间节点I处理RREQ分组的算法如下，其中算法中我们用P表示RREQ分组，分组中域的值用刘一象式的方法表示，例PSouree表示RREQ分组的Souree域的值。I坟IsRePetitionl，kt(P.Source’PSequence--1D)}}ExistlnNodelist(I))Discard(P);Exit; 武汉理工大学硕士学位论文EI货AvailableBandwidth=CalculateBandwidth(P.Source，I);I坟AvailableBandwidthhighest一aeket_id)l、ighest一aeket_id=Paeket_id，i坟start一ime【Paeket_id』==0)startjillle【Paeket_id」=ti:、le;i坟actio:1==”r，，&&tyPel==”AGT”&&t)，PeZ=二”ebr，，){reeeives++;end一ime【Paeket_id」=time;}i坟aetion==”s，，}}aetion==，，f，&&tyPel=”RTR”&&tyPeZ二”AODV’川tyPeZ=”DSR，，}}tyPeZ=，，message”日tyPeZ=”DSDV”日tyPeZ=”TORA，，)router夕aekets一;}END{for(Paeket_id=0;Packetseid<=highest少aeket_id;Paeket一d什)毛Paeket--duration=end--time[Paeket_id]一start一ime[Packet_id];i坟Packet_duration>o)end--to-end_delay+=paeket一uration;}Print坟”85 武汉理工大学硕士学位论文*****************************************************功”Print坟”sends%八n”，sends);Print坟”receivs%nn”，reeeives);Prini坟，，Pdfraction%八n，，，reeeive澎sends);Print坟，，routingoverheadPaekets%八n”，route甘ackets);Print坟，，Normalizedroutingload%八n，，，route吵aekets/reeeives);Print坟”AvgEndjnddelay%八n”，end一。_end一elay/reeeives);Print坟，，***************************************************** ”86