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

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

武汉理工大学硕士学位论文AdHoc网络的QoS路由协议与NS2仿真研究姓名：郑四海申请学位级别：硕士专业：计算机应用技术指导教师：李腊元20080501 武汉理工大学硕士学位论文摘要服务质量(QoS)路由技术是在AdHoc网络中应用多媒体业务的关键问题。目fi百AdHoc网络中的QoS路由还存在着不少期待解决的问题。本文在深入研究和分析现有QoS路由协议的基础上，针对AdHoe网络的仿真、单径路由、QoS、多QoS等问题，重点深入研究了多径路由和QoS多径路由这两个主题。本文所做的主要研究工作和创新性可体现在以下几个方面：1．从无线网络通信的基础入手，首先介绍了无线网络的两种系统结构。然后重点研究了无线AdHoc网络的特点、体系结构、路由协议的分类；最后研究分析了表驱动路由协议和按需路由协议的工作机制，并对它们的性能作了相应的比较。2．NS2是国内外公认的网络仿真平台，熟练的掌握好它，是进行网络协议研究的重要基础。本文对NS2作了较深入的研究和分析，介绍了NS2的工作原理、层次结构，特别重点介绍了无线网络模块。通过在NS2中添加一个本文新开发的数据传输协议的实例，详细阐述了利用NS2进行仿真分析的过程。3．多径路由作为一种重要的降低拥塞的手段已经引起了AdHoc网络研究领域的重视，然而现有多径算法在很多方面做得还不够好，有的过于复杂，难以实现；有的路由开销过大，反而增加了网络拥塞。本文对AdHoc网络的多径路由作了大量的研究分析，提出了一种改进的多径源路由协议MPDSR。该协议改进了DSR的路由机制，可以同时获得多条节点不相关路由。通过在DSR路由请求报文中添加字段来帮助获取多径信息；适当增大路由缓存，以存放更多冗余路由，加快路由发现的速度。仿真实验表明，MPDSR协议的性能达到了预期的效果。4．随着AdHoc网络的发展，QoS保障越来越重要。QoS路由是提供QoS保证的一种重要手段，但已经提出的QoS路由大多建立在单径的基础上的，这并没有充分利用AdHoc网络资源。以MPDSR协议为基础，本文提出了一种新的多径QoS路由协议QMPDSR。该协议主要考虑带宽和时延的约束来选择多条QoS路由。当QoS业务到达时，该协议能分解QoS要求，利用一条或多条路径同时传输QoSX_lk务。仿真实验表明，QMPDSR协议提高了分组投递率，降低了时延，路由开销的增加也不明显。最后，对本文的工作进行总结，并提出了本课题有待于进一步研究的问题。 武汉理工大学硕士学位论文本文得到了国家自然科学基金项目《批准号：60672137，60773411)，教育部褥士点基金项目(批准号：20060497015)和湖北省科技攻关项目(批准号：2007AAl01C63)的资助。关键词：AdHoc网络，路由协议，多径路由，QoS，NS2II AbstractQoS．BasedroutingtechniqueisthekeytoapplymultimediaoperationsinAdHocnetworks．However,SOfarthereremainmanyproblemsstillexpectingtobesolvedinthefieldofQoS-basedroutinginAdHocnetworks．Surroundingthetwothemes．multiplepathandQoS．basedmultiplepath，thisthesisundertakesanin．d印thstudyofsomekeyissuesinAdHocnetworks，includingsimulationofAdHocnetworks，singlepath，QoSconstraints，andmultipleQoSconstraintsetc．ThefollowingworkiSaccomplishedinthisthesis．1．Atfirst，twokindsofstructuresofwirelessnetworksareintroducedinthis廿lesis．thensomethemesinAdHocnetworksareresearchedaskeypartssuch懿thecharacteristic，thearchitecture，andtheroutingprotocols．Atlast，weresearchthetwokindsofroutingprotocolsofAdHocnetworksincludingthetabledrivenprotocolsandondemandprotocols，andmakethecorrespondingcompansontotheirperformancesamongthetypicalroutingprotocols·2．NS2isanetworksimulationplatformwhichisuniversallyacknowledgedintheworld．It’simportanttomasterandskillfullyuseNS2．Thisthesismakesa如rtherstudyonNS2，andthenintroducestheworkprincipleandstructureofNS2．Moreover。tllewirelessnetworksmoduleisintroducedindetailasaspecialpartinthisthesis．Throughappendinganewlydevelopeddatatransmittingprotocol，weelaboratehowtosimulateprotocolsandanalyzedatabyNS2．3．Multi．pathrouting，asakindofimportantmeasureofreducingcongestlon，hasattachedtheattentioninAdHocnetworksresearchfield．However,there’restillsomeflawsexistinginthecurrentmulti-pathalgorithms．Forexample，somealgorithmsaretoocomplicatedtorealize，someroutings’spendingSOhighthatincreasecongestion．ThisthesisputsforwardanewmultiplepathroutingprotocolnamedMPDSR．MPDSRhasimprovedtheroutingmechanismofDSR，andcanobtainseveralroutingmessageswhichnodesdisjointedatthesametime．WeappendseveralfieldsintheRREQinordertogetthemessageofmulti-path，andproperlVextendtheroutingcachetoacceleraterouting．SimulationshowsthattheIII 武汉理工大学硕士学位论文performanceofMPDSRisasfullandcompleteasweexpected．4．WiththedevelopmentofAdHoe，itismoreandmoreimportanttoprovideQoSguaranteeformultimediaapplication．AlthoughQoS—basedroutingisanavailablemethodtoprovideQoSguarantee，mostofpresentQoS—basedroutingbasedonsinglepath，whichdonottakefulladvantageofresourceofAdHocnetworks．Thus，onthebaseofMPDSR，thisthesisputsforwardaQoS—basedmultiplepathroutingprotocolnamedQMPDSR．QMPDSRCanfindseveralpathsprovidedQoSguarantee．Also，itcandisassembleQoSdemandstotransmitapplicationdatastreamusingdifferentnodedisjointedpathsimultaneously．SimulationshowsthatQMPDSRprotocolisbetterthanQoS-MSR．Itspacketdeliveryratioishigher,timedelayislower,eventheincreasedroutingspendingcausedisnotoutstanding．Finally,someconclusionsforthisthesisaremadeandsomesuggestionsforfutureresearchonthisfieldaregiven．．ThisthesisissupportedbyNationalNaturalScienceFoundationofChina(60672137，60773411)，thePh．D．ProgramsFoundationofMinistryofEducationofChina(20060497015)andHubeiProvinceKeyScientificandTechnologicalProject(2007AAl01C63)．Keywords：AdHocnetworks，routingprotocol，multi-pathrouting，QoS，ns2Ⅳ 独创性声明本人声明，所呈交的论文是我个人在导17iI：l：旨导下进行的研究工作及取得的研究成果。据我所知，除了文中特JltlD霸n．nJ,标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名：件冒期掣关于论文使用授权的说明本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有杈保留送交论文的复印件，允许论文被查阅和借阕；学校可以公布论文的全部内容，可以采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后应遵守此规定)研究生签名：翩签名剖鳖臼麓蜉上攀 武汉理工大学硕士学位论文第1章绪论本章主要介绍本文的背景和意义、所作的主要工作及创新、主要结构和课题来源。1．1论文的研究背景和意义无线网络自从二十世纪七十年代出现以来，越来越受到计算机行业的重视。尤其是最近十年间，由于无线网络与移动技术相结合，令其大受欢迎。但通常来说，移动无线通信网络通常以蜂窝移动通讯系统，无线局域网11J(IEEE802．11)方式出现，这样的移动网络依然离不开通信基站或接入点为基础。比如在蜂窝移动网络当中，移动终端与固定基站相互通信，移动终端本身不具备路由功能，由移动交换机负责路由与交换功能，同时充当网关，以有线方式接入固定网。而在无线局域网当中，则用符合802．11协议的无线网卡把移动节点(笔记本，PDA等)通过无线接入访问点连接到现有的固定网络。这些移动通信方式都需要类似基站、访问服务点或外地代理等这样的中心控制设备。就是说采用事先建好的网络设备进行通讯，利用基站之间的信息交换来实现终端的通信。AdHoc网络起源于美国国防部高级研究规划署(DARPA)资助的一项特别的研究——移动分组无线网络(MobilePacketRadioNetworking)，即报文交换技术，在不受固定或有线的基础设施限制的环境下运行。最初的动机之一就是满足战场生存的军事需求。在战场恶劣的环境下，通信设备不可能依赖已经敷设的通信基础设施：一方面这些设施可能根本不存在；另一方面，这些设施会随时遭到破坏。因此，能快速装备、自组织的移动基础设施是这种网络区别于其他商业蜂窝系统的基本要素。在结构上，这种网络是由一系列移动节点组成，是一种自组织的网络，它不依赖于任何已有的网络基础设施。网络中的节点动态且任意分布，节点之间通过无线方式互连，它将分组交换网络的概念引伸到广播网络的范畴。这项工作开辟了AdHoc网络研发的先河。与此同时，美国政府还资助了其他一些相关研究项目，其中包括“可生存目适应网络(SURAN)”、“低成本报文无线电(LCR)"、“可生存通信网络 武汉理工大学硕士学位论文(scN)"、“战术因特网和近期无线电(NTDR)”项目等。90年代中期，随着一些技术的公开，AdHoe网络开始成为移动通信领域一个公开的研究热点。由于AdHoc网络可以广泛地应用于战场通信指挥与控制、警察与医疗部门的抢险救灾、传感器网络、课堂教育等众多领域，其战略意义非常重要。1991年成立的IEEE802．1l标准委员会采用了“AdHoe网络’’一词来描述对等式无线移动网络。一般把基于AdHoe技术的网络译为“自组网"或者“多跳网络”等等。AdHoe网络不需要固定的基站，各个节点均可自由移动，且能实现动态的连接，生存性极强，使之弥补了蜂窝系统与有线网络的不足，在许多特殊情况下有着不可替代的作用。因此，AdHoe网络的研究对网络的发展具有重大促进作用。同时，随着AdHoe网络研究的发展和相关产品的成熟，AdHoe网络也越来越受到人们的重视，因而其具有广泛的研究与发展前景。路由协议作为影响网络性能的一个重要因素，是确保AdHoc网络正常运行的关键。目前大多数无线AdHoe网络路由协议都是建立在单径路由的基础上，对多径路由研究不是很多。特别是在按需路由协议中通常以跳数最少的路由作为最佳路由，这样往往使得多条路由共用某一个节点，而使得它的能量迅速消耗完毕造成链路中断。近年来，无线AdHoe网络中的QoS问题越来越得到研究者的关注。为了提供QoS保证，首要的任务就是在源节点和目的节点之间寻找必要资源来满足QoS要求的路由，其次对于特定的流一旦路由被选择后，必须为该流预留必要的资源(OH带宽、路由器中的缓存空间等)。提供QoS路由可以将这些任务结合在一起，这样QoS保证转换为QoS路由问题。QoS路由不仅要找到一条从源到目的的路径，而且要使这条路径满足端到端的服务质量要求【2吲，QoS多径路由还要能分解QoS要求，以增强链路的稳定性，提高服务质量。因此，为无线AdHoe网络提供服务质量保证对于推动无线AdHoc网络的研究和应用有着非常重要的意义。1．2本文的主要工作及创新本文的主要研究对象是无线AdHoc网络的多径路由和QoS多径路由协议。对多径路由和QoS多径路由协议的设计思想、工作方式进行了深入的研2 武汉理工大学硕士学位论文究和探讨，为QoS路由协议的实际应用提供理论依据。本文的主要工作如下：1．对AdHoc网络的产生、特点、研究热点和应用作了介绍。对AdHoe网络典型的单播路由协议DSDV，DSR，AODV，TORA等进行了深入的研究和分析。2．网络仿真工具NS2的研究。NS2是知名的网络仿真软件，其优势是免费且源代码开放。NS2在学术界得到充分肯定。熟练掌握好NS2是我们进一步进行路由协议研究和开发的重要基础。本文通过在NS2中添加一个传输协议的实例，阐述了NS2的基本原理和仿真流程，为进一步利用NS2进行仿真研究奠定了基础。3．AdHoe网络的多径路由协议的研究。多径作为一种重要的降低拥塞的手段已经引起了AdHoc网络研究领域的重视。但是有线网络中的多径技术不能直接应用到AdHoc网络中，本文在深入研究了DSR路由协议的基础上，提出了一种改进的多径路由协议MPDSR。MPDSR协议能在路由发现过程中获得多条路由信息，然后选择出最多3条节点不相关路径进行数据传送。仿真实验表明，其性能优良。4．QoS多径路由的研究与性能分析。随着多媒体业务和实时性业务的出现，要求AdHoc网络提供一定的QoS保证，特别是带宽和时延保证。本文对AdHoe网络的QoS多径路由进行了深入的研究，在MPDSR协议的基础上提出了一种新的QoS多径路由协议QMPDSR，详细阐述QMPDSR协议的Qos模型和路由机制。仿真实验表明QMPDSR协议的性能达到了预期的效果。1．3本文的主要结构第l章：绪论。介绍论文的背景、意义和本文的主要工作。第2章：无线AdHoc网络及路由协议分析。介绍无线AdHoc网络的概念及其特点，并简要介绍现有的AdHoc网络的单播路由协议，分析了各自的优缺点；接着重点介绍了DSR协议，详细分析了它的路由机制。第3章：NS2与网络仿真。介绍了网络仿真工具NS2和其无线仿真部分，通过添加一个新的传输算法演示了利用NS2进行仿真实验和分析的流程。3 武汉理工大学硕士学位论文第4章：一种改进的多径路由协议MPDSR。对AdHoc网络的多径路由协议进行深入的研究和分析，提出了一种改进的基于DSR多径源路由协议MPDSR，对它的路由机制和思想作出详细的阐述，最后进行了仿真分析。第5章：一种新的QoS多径路由协议QMPDSR。对AdHoe网络的QoS体系结构、QoS路由算法进行了研究，同时对典型的QoS多径路由协议的基本思想、路由机制和存在的问题进行了研究。本章提出了一种QoS多径路由协议QMPDSR，对它的路由机制作了详细的阐述，最后进行了仿真分析。第6章：总结与展望。对本文的研究进行总结和对将来的工作进行展望。1．4本文的课题来源本文得到了国家自然科学基金资助项目(批准号：60672137，60773411)，教育部博士点基金资助项目(批准号：20060497015)和湖北省科技攻关项目(批准号：2007AAl01C63)的资助。4 武汉理工大学硕士学位论文第2章无线AdHoc网络及路由协议分析本章将对无线AdHoc网络的特点和应用作出简单的介绍，对AdHoc网络的路由协议进行深入的研究，特别对AODV、DSR、TORA等协议的路由机制和性能作出比较、分析。2．1无线网络的特征无线通信，是不借助有线传输媒介，而是通过电磁波在空间传递信息的通信方式。无线通信的特点在于它的传输媒介——无线信道，其特征是：1．广播性：一个发射机发射，多个接收机都可以接收；2．信道随空间而变化：随着空间环境的不同，信道特性往往不同；3．信道随时间而变化：有快速变化和较慢变化的区别；4．传播距离有限：发送信号随距离增大在逐渐衰减，信号衰减到一定程度，接收机将不能正确接收；5．多径效应：信号可沿不同路径到达接收机，造成衰落和时延扩展；6．相互之间形成干扰：多个发射机发送的信号可能会在接受端叠加，形成相互干扰，从而对信号的正确接收造成影响。无线通信系统，就是采用无线通信技术的通信系统。无线通信系统有若干分类方式，按照使用的频段不同，可分为长波、中波、短波、超短波、微波、红外线等。按照系统使用的通信体制和技术又可分为蜂窝移动通信、寻呼移动通信、集群移动通信、卫星通信、微波传输、无线局域网、无线个域网等系统。2．2无线通信系统结构无线通信系统有两种网络结构：有基础设施网和无基础设施网。下面分别对这两种结构加以介绍。有基础设施网络结构：通常是对有线通信网的一种扩展。有线网被用作骨干网，连接到特殊的有线／无线转接节点【41，即基站(BS，BaseSation)或接入点(AP，AccessPoint)。常见的有GSM系统和CDMA系统，如图2-1所示。5 武汉理1=大学硕士学位论文◇囡轨他脑≮∥脚◇⋯蛾图2．1有基础设施网络结构无基础设施网络结构：一般称为无线AdHoc网络，AdHoe网络是由多个移动节点组成的多跳无线网络。这些移动节点处在同一个局域区域内，每个节点都具备路由器的功能，可以通过存储转发帮助其他节点构成通信链路。它与有基础设施网最大的区别是不需要预设的基础设施(基站BS)。网络组建是临时的、按需的、自动的。由于自组网无基础设施，导致无控制中心，因此必须采用分布式的控制方式【51，如图2．2所示。图2-2无基础设施网络结构6夕一回m 武汉理工大学硕士学位论文2．3无线AdHoe网络的特点在AdHoc网络中，每一个移动节点都有自己的无线收发器，使之可以在一定距离内与其它节点通信，节点间的通信可以通过一个节点链，链上的相邻节点是直接通信的，沿着这条链路，数据就可以以“多跳"的方式传输。因此所有节点都必须有路由和转发数据的能力。如图2．3描述了一个由三个节点组成的简单的AdHoc网络。图2—3简单的AdHoc网络在该图中，节点主机A不在节点主机C的传输范围内，同时C也不在节点主机A的传输范围内，而A，C都在主机B的传输范围内，因此，A要传输消息到C，必须通过节点主机B。与有中心网络相比，AdHoc网络更坚固，更耐用，具有以下特点：1．无中心和自组织性。任何时候、任何地点快速构建移动通信网络，并且不需要现有信息基础网络设施的支持。所有节点地位平等，各节点通过网络协议和分布式算法调节彼此的行为。节点可以随时加入和离开网络，任意节点故障都不会影响整个网络运行，具有很高的鲁棒性。2．多跳路由。由于节点功率的限制，通信的目的节点可能不在源节点的覆盖范围内，于是通过一个或多个中间节点来完成通信。这样接受端和发送端的节点可使用比两者直接通信小得多的功率进行通信，因此大大节约电池能量的消耗。中间节点参与分组转发，能有效降低对无线传输设备的设计难度和成本，同时扩大了自组网络的覆盖范围。3．节点功能双重性。在AdHoc网络中没有基站设施的支持，报文的转发是通过终端节点间的协同工作来完成，每个终端都将承担为其他终端进行分组转发的义务。因此，终端作为主机，要运行面向用户的应用程序；作为路由器，要运行相应的路由协议，具有双重功能。7 武汉理工大学硕士学位论文4．节点功耗受限。由于网络节点的移动特征，其中大多数节点以电池作为动力，因而在进行系统设计时节能就成为一个非常重要的指标。5．生存时间短。AdHoc网络一般是为了满足临时需要而建立的，等任务完成后将被撤除。AdHoc网络作为现有网络的一种补充和扩展，主要应用在没有现成网络基础设施支持的环境中或现有网络不能满足移动性、机动性等要求的环境中，例如，军事作战环境；救火、救生等需要紧急部署通信网络的环境；人员处于没有现成网络支持但又需要协同工作的商业活动区域中。它可以在独立的环境下运行，也可以通过网关连接到现有的网络基础设施上，如Intemet。2．4AdHoc网络的体系结构2．4．1网络结构AdHoc网络一般有两种结构【4，6】：平面结构(图2．4)和分级结构(图2．5)。图2_4平面结构图2-5分级结构在平面结构中，所有结点的地位平等，所以又可以称为对等式结构。分级结构中，网络被划分为簇。每个簇由一个簇头和多个簇成员组成。这些簇头形成了高一级的网络。在高一级网络中，又可以分簇，再次形成更高一级的网络，直至最高级。在分级结构中，簇头结点负责簇间数据的转发。簇头可以预先指定，也可以由结点使用算法自动选举产生。分级结构的网络又可以被分为单频分级和多频分级两种。单频率分级网络中，所有结点使用同一个频率通信。为了实现簇头之间的通信，要有网关结点(同时属于两个簇的结点)的支持。而在多频率分组网络中，不同级采用不同的通信频率。低级结点的通信范围较小，而高级结点要覆盖较大的范 武汉理工大学硕士学位论文围。高级的结点同时处于多个级中，有多个频率，用不同的频率实现不同级的通信。在两级网络中，簇头结点有两个频率。频率1用于簇头与簇成员的通信。而频率2用于簇头之间的通信。分级网络的每个结点都可以成为簇头，所以需要适当的簇头选举算法，算法要能根据网络拓扑的变化重新分簇。2．4．2协议栈结构根据AdHoc网络的特征，参照OSI／RM的经典7层协议栈模型和TCP／IP的体系结构，可以将AdHoc网络划分为5层【71，如图2-6所示。图2-6AdHoc网络的协议栈结构各层的功能描述如下：1．物理层。物理层负责频率的选择、无线信号的检测、调制解调、信道加密解密、信号发送和接收等工作。此外还要确定采用哪种无线扩频技术(直接序列扩频DSSS或跳频扩频FHSS)。由于多径传播带来的多径衰减、码间串扰以及无线传输的空间传播特性带来的节点问的相互干扰，使AdHoc网络的传输链路带宽容量低。因此物理层的设计目标是以相对低的能耗，克服无线媒体的传输损伤，获得较大的链路容量。2．数据链路层。数据链路层的MAC子层控制移动节点对共享无线信道的访问，它可以采用随机竞争机N(CSMA、IEEE802．11或MACA)、基于信道划分的接入机制(TDMA、FDMA、CDMA或SDMA)、轮转机制(轮询或令牌环)、动态调度机制以及以上机制的组合。逻辑链路控制子层负责数据流的复用、数据帧的检测、分组的确认、优先级排队、差错控制和流量控制等。链路层的设计目标是在相对能量小的条件下，使得数据速率接近最基本的信道容量。3．网络层。网络层是AdHoc网络的重点，主要包括邻居发现、分组路由、拥塞控制和网络互连等功能；网络层的单播路由协议维护路由表，使其与当前9 武汉理工大学硕士学位论文的AdHoc网络拓扑结构一致；多播路由协议提供群组通信的底层支持；网络互联支持AdHoc网络与其它现有网络互联。4．传输层。传输层主要是向应用层提供可靠的端到端服务，使上层与通信子网(下三层的细节)相隔离，并根据网络层的特性来高效地利用网络资源，当AdHoc网络需要接入Internet等外部网络时尤其需要传输层协议的支持。5．应用层。应用层协议提供面向用户的协同应用服务，包括具有严格时延和丢失率限制的实时应用(紧急控制信息)、基于RTP／RTCP的自适应应用(音频和视频)和没有任何服务质量保障的数据业务。2．5AdHoc网络路由协议目前国际上根据路由的触发机制将AdHoe无线网路由选择协议分为两大类：表驱动路由协议(TableDrivenProtocols)和按需路由协议(Source．InitiatedOn．DemandProtocols)，如图2．7、2．8所示。根据网络拓扑结构的差异，又可以将它们分为平面结构的路由协议(FlatProtocols)和分簇路由协议(ClusteredProtocols)。2．5．1表驱动路由协议与按需路由协议表驱动路由协议(TableDrivenProtocols)，又被称为主动式(或先验式)路由协议，是一种基于表格的路由协议。在这种路由协议中，每个节点维护一张或多张表格，这些表格包含到达网络中所有其它节点的路由信息。当检测到网络拓扑结构发生变化时，节点在网络中发送更新消息。收到更新消息的节点更新自己的表格，以维护一致、及时、准确的路由信息。不同的表驱动路由协议的区别在于拓扑更新消息在网络中传播的方式和需要存储的表的类型。表驱动路由协议不断的检测网络拓扑和链路质量的变化，根据变化更新路由表，所以路由表可以准确地反映网络的拓扑结构。源节点一旦要发送报文，可以立即取得到达目的节点的路由。表驱动路由协议有DSDV，CGSR，WRP，GSR，FSR，HSR，ZHLS[81等。按需驱动路由协议(On．DemandProtocols)，又称为反应式路由，是一种当需要时才查找路由的路由选择方式。节点并不保存及时准确的路由信息。当源节点要向目的节点发送报文时，源节点在网络中发起路由查找过程，找到10 武汉理工大学硕士学位论文相应的路由后，才开始发送报文，为了提高效率，节点可以将找到的路由保存在缓存中供后续发送使用。按需驱动路Eh协议有DSR,AODV，TORA,ABR[9】艟{于。图2-7表驱动路由协议按需路由协议土1L、，1L上IAoDVDSTORAABRSSR图2—8按需路由协议2．5．2平面式路由协议和分簇式路由协议根据网络拓扑结构的不同，相应地将AdHoe网络路由协议划分为平面结构的路由协议和分簇式路由协议【lo】。在平面结构的路由协议中，网络结构简单，网络中的节点都处于平等的地位，它们所具有的功能完全相同，各节点共同协作完成节点间的通信。随着网络规模的逐步扩大，网络中节点个数不断增加，每个节点要想维护整个网络的拓扑信息或选择到远端节点合适的路由将十分困难，由此产生了分簇式路由协议。在分簇式路由协议中，网络节点按照不同的分簇算法分成相应的簇。簇中的每个节点完成的功能是不相同的，簇首节点维护和管理本簇范围内节点，有的节点被赋予一些特别的功能，如负责簇内节点的通信，同时为簇间节 武汉理工大学硕士学位论文点通信提供合适的路由信息；网关节点负责与相邻节点通信。由底层簇的簇首节点可以进一步组成高一层的簇，如图2．9所示。分层l一一一一一分层2一一一一一图2．9分簇式路由协议中分层结构图●簇首节点囝内部节点■网关节点根据簇的划分方法、簇首的选择方式以及簇首职责的不同，出现了一些不同的基于分簇结构的路由协议【111，如CEDAR、HSR及ZHLS等。2．6典型的AdHoc网络路由协议分析2．6．1表驱动的路由协议1．DSDVDSDV[12~13](Destination—sequencedDistance．vector)是最早的自组网路由协议。在DSDV中，每个移动节点都需要维护一个路由表。路由表表项包括目的节点、跳数和目的地序号，其中目的地序号由目的节点分配，主要用于判别路由是否过时，并可防止路由环路的产生。每个节点必须周期性与邻节点交换路由信息，当然也可以根据路由表的改变来触发路由更新。路由表更新有两种方式。一种是全部更新，即拓扑更新消息中将包括整个路由表，主要应用于网络变化较快的情况；另一种方式是部分更新，更新消息中仅包含变化的路由部分，通常适用于网络变化较慢的情况。在DSDV中只使用序列号最高的路由，如果两个路由具有相同的序列号，那么将选择最优的路由(如跳数最短)。DSDV的特点是采用了序列号机制用于区分路由的新旧程度，防止可能产生的路由环路。它的缺点是不适应变化速度快的自组网，不支持单向信道。12 武汉理工大学硕十学位论文2．CGSRCGSR[14](ClusteredGatewayswitchRouting)以DSDV算法为基础，但是CGSR并适用于平面网络，它使用了分簇路由结构和启发式路由选择机制。CGSR分配指定了簇首节点和网关节点，其中簇首节点用来控制一组节点和网关节点，网关节点是两个簇之间的节点。当一个节点要发送分组时，这个分组首先到达该发送节点的簇首节点，然后簇首节点把这个分组通过网关节点转发给另一个簇首节点。不断重复这个过程直到分组到达目的节点。因此，每个节点都必须有其簇成员的路由表。虽然CGSR用DSDV作为其底层的协议，但是由于在CGSR中寻路是通过簇首节点和网关节点来完成的，所以它比DSDV更有效。其优点是适合大规模的AdHoc网络环境，可扩展性比较好。问题是簇首节点的稳定性、可靠性对全网性能影响较大，对于节点在群之间的移动将产生一定的开销。3．WRPWRP[”](WirelessRoutingProtoc01)路由协议在网络的节点中保存路由信息。每个节点保存在路由表中的信息如下：距离、路由、链路开销和重传消息的列表(MRL)。MRL记录关于消息序列号、重传计数器、每一个邻节点正确应答所需的标识和更新消息的更新列表等信息。这就使得节点可以决定何时发送更新消息以及发送给哪个节点。WRP的优点就是算法收敛快，并避免路由当中的环路。由于WRP需要保存4个路由表，所以比大多数的协议需要更大的内存。WRP还依赖于周期性的Hello消息，这也要占用带宽。2．6．2按需驱动的路由协议1．AoDVAODV[1607kAdHocOn．demandDistantVector)的路由发现过程由逆向路由的建立和正向路由的建立两部分组成。路由中的每个节点都维护路由表，因而数据报文头部不需要携带完整的路由信息，从而提高了协议的效率。当源节点不具备一条到目的地的路由而又要发送数据到目的地时，源节点广播RREQ消息给邻居。邻居接收请求消息，建立一条到源的逆向路径，并设置逆向路径的生存期。如果该节点没有到目的节点的路由，就把收到的RREQ转给自己的邻居，直到到达目的节点，或者到达某个具有“更新"路由的中间节点。目的节点收到RREQ，就建立到源节点的逆向路由，返回一个RREP13 武汉理工大学硕士学位论文路由应答报文。单播该RREP给源节点。中间节点收到RREP，就建立到目的节点的正向路由。AODV路由协议采用Hello消息机制进行链路连通性管理，从而对有效路由进行维护。具有有效路由的节点每隔固定时间T便广播一个Hello消息。邻节点收到Hello消息，可对各自的相应路由进行建立或更新。若节点在连续的几个T的时间内未收到有效路由中相邻节点的Hello消息便认为该链路中断，并发送RERR至相关路由的节点。AODV协议具有以下特点：(1)基于传统的距离向量路由机制，思路简单、易懂。(2)通过使用目的序列号有效地防止了循环的发生，解决了传统的基于距离向量路由协议存在的无限计数问题，并且易于编程实现。(3)支持中间主机回答，能使源主机快速获得路由，但存在过时路由问题。(4)需要周期性地广播报文，需要消耗一定的电池能源和网络带宽。2．DSRDSR[18～19](DynamicSourceRouting)是一个简单而有效的路由协议。它要求每个移动节点维护一个存放路由的快速缓冲区。当某一移动节点要发送数据分组时，首先查询本地高速路由缓冲区，确定是否存在可以使用的路由。若路由存在，则沿路由发送数据；否则发送一个包含源节点和目的节点地址的路由请求分组，启动路由发现过程。中间节点收到该请求分组后查询本地缓冲区，若没有到达目的节点的路由，则将本节点地址加入请求分组后转发，直至将分组转发到目的节点或有到达目的节点路由的中问节点，该节点发回一个路由应答分组。路由应答分组中包含了从源到目的节点路径上的所有节点的节点序列。每个发送的数据分组中都将包含该路径节点序列。因此，中间节点不需保存用于分组转发的路由信息，从而避免了周期性的路由广播和邻居发现。DSR协议具有以下几个优点：(1)仅在需要通信的节点间维护路由，减少了路由维护的代价。(2)路由缓冲技术可进一步减少路由发现的代价。(3)由于采用了路由缓冲技术，因此在一次路由的发现过程中，会产生多种到达目的节点的路径。(4)支持非对称传输信道模式。14 武汉理工大学硕士学位论文但DSR协议也存在一些问题和不足：(1)由于采用源节点路由，每个数据报文的头部都要携带路由信息，增加了报文长度。(2)用于路由发现的控制报文可能会波及全网各节点，造成一定的耗费；一种可行的优化方法是控制路由发现报文的传输距离(如跳数)，如果本轮路由发现失败，后续的路由发现过程再加大传输距离。(3)“路由响应风暴”(RouteReplyStorm)问题。由于采用路由缓冲技术，中间节点根据自己的缓冲路由，对路由请求直接应答，源节点会同时收到多个路由响应，造成路由响应信息之间的竞争。(4)“脏”缓冲路由对其他节点的影响。如果中间节点的路由缓冲已经过时，当该节点根据缓冲路由回复路由请求时，会造成“脏"缓冲路由的污染传播。3．TORATORA[20~21](TemporallyOrderedRoutingAlgoritlm)采用链路反转的分布式算法，具有高度自适应、高效率和较好的扩充性，比较适合高度动态移动、多跳的无线网络，该协议的主要设计理念是将路由信息的传递限制在距离拓扑变化最近的少部分节点，节点只保存相邻节点的路由信息，尽可能减少控制信息的通信开销。该算法中路由不一定是最优的，常常使用次优路由以减少发现路由的开销。TORA包括三个基本模块：路由的创建、路由的维护和路由的删除。TORA算法的原理可以用水从高山上流下的过程来比喻，水道代表节点之间的链路，水道的转接处代表节点，水流代表分组，每个节点有一个相对于目的节点的高度，用做计算路由的度量。如果节点A到节点B的链路中断，就给A一个比其邻近节点都高的高度值，这样水流(分组)就从A回流(这个过程称为反转)，通过其它节点流向目的节点。4．ABRABR[22](AssociativityBasedRouting)采用新的方法解决无线路由问题，避免了回路、死锁和重复分组等缺陷。它定义了一种新的路由制式，称为联合稳定度，用于描述两个节点在时间和空间的连接稳定性。节点的联合稳定度高，说明节点处于低移动状态，反之处于较高移动状态。ABR的实质就是发现长期有效的路由。在ABR中，根据节点的联合稳定度选择路由，每个节点周期性地产生信15 武汉理工大学硕士学位论文号(Beacon)以表示它的存在，当邻近节点收到一个Beacon，就修改它的相关表，若收到来自相同节点的信号，则增加与此节点的相关度。ABR协议由三部分组成：路由发现、路由重构和路由删除。路由发现采用广播查询与等待应答的循环方式(BQ、REPLY)，源节点首先广播一个BQ报文，各节点只转发一次BQ包。当中间节点收到BQ报文后，将其地址和相关标记值附加到此报文中。后续节点删除其上行节点的邻近点联合稳定标记实体，只保留与其自身和上行节点有关的实体。到达目的节点的每个分组包含有各路径节点的联合稳定标记值，这样目的节点通过检查各节点的联合稳定标记值，选择最佳路由。当多条路由有相同联合稳定标记值时，则选择具有最小跳数的路径。一旦路径选定，目的节点沿着被选定的各路径发送一个应答分组。有应答分组经过的路径为有效路径，其它路径保持非激活状态，因此可避免重复分组到达目的节点。路由重构包括局部路由发现、无效路由的删除、有效路由的修改和新路由的发现等，它视不同节点的移动而定。若是源节点移动，将引起一个新的BQ、REPLY处理，因为ABR是源路由协议，路由通知报文(RN)用于删除与下行节点相关的路由实体。当目的节点移动时，其直接上行节点删除此路由。本地查询处理LQ(H)，确定该节点是否仍然可达。若目的节点收到LQ分组，则选择最佳局部路由并应答；否则初始节点超时并返回到下一个上行节点，RN报文发送给下一个上行节点去删除无效路由并通知它进行LQ的处理，当这样的处理导致路径回退超时一半时，则LQ处理不再继续，源节点初始化一个新的BQ处理。当所发现的路由不再需要时，源节点广播一个路由删除(RD)报文通知各节点从路由表中删除此路由实体。2．7典型路由协议的分析比较在基于表驱动的路由协议中，节点实时的维护着网络拓扑信息，因此当节点有数据发送时，能够根据路由表迅速的找到到达目的节点的路径，即分组的发送时延小。而且通过这些拓扑信息，比较容易实现路由的优化及QoS路由。在按需路由协议中，只有在需要一条路径时才开始建立。如果节点在发送分组时没有到目的节点的路由，需要启动相应的路由发现机制搜寻路由，这样将会产生一定的时延，不利于实时业务的传输。因此，在拓扑变化频繁16 武汉理工大学硕士学位论文的AdHoc网络环境中，应采用按需路由协议；而在网络拓扑结构相对稳定的环境中，如果业务对实时性要求较高时，应尽量采用基于表驱动方式的路由协议。表驱动路由协议和按需方式路由协议的路由时延、控制开销、耗电量和带宽开销的比较如表2一l所示，按需路由协议的基本性能比较如表2．2所示。表2．1表驱动和按需方式路由协议的性能比较表驱动(Table—Driven)按需(On-Demand)方式路由协议DSDV、CGSR、WRPAoDV、DSR、ToRA、ABR路由获取时延低高控制开销高低耗电量高低带宽开销高低表2．2按需路由协议比较表AODVDSRToRAABR整体复杂性中等高向开销低中等高拓扑结构平面LoOP—free是多路径支持否是否路由存放位置路由表路由缓存路由表删除路由链路反向局部广路由重置方法通知源端路由修复播查询最新最相关度和路由度量最短路径短路径最短路径AODV与DSR的路由机制类似，不同点是在寻路分组发出的时候，AODV的分组中只带有目的节点的信息，而DSRfl了于是源路由方式，则包含所有节点的信息。因此在一方面，DSR的开销要大一些，但是在寻路分组返回时，两者开销是一样的，分组中都记录了整条路径的信息。AODV的缺点是要求链17 武汉理工大学硕+学位论文路都对称(Symmetric)，无法使用不对称的(Asymmetric)，而DSR贝JJ无此限制。AODV和DSR的另一个主要区别是DSR支持多径路由而AODV不支持，因此在中间节点发现路径中断时，AODV只能将分组丢弃；而DSR却可以在路由缓存中寻找其他的路径对分组进行补救，这一点在AdHoc网络中尤为重要。TORA作为一种“链路反向"算法，非常适合于节点密度高的网络。TORA的创新之处在于使用了有向无环图的方法。TORA可以支持多条路径，在TORA协议中，为了降低寻路造成的负载，不将路径是否最优作为其选择路径的首要因素，因此选择的路径有时会很长。2．8本章小结本章从无线网络特征入手，首先介绍了无线网络的两种系统结构形式：有基础设施网络和无基础设施网络；然后研究了无线AdHoc网络的特点、路由协议的分类；最后重点研究、分析了常见的几种AdHoc网络路由协议的特点、路由机制、路由维护、路由优化、适用范围等，并对这几种路由协议的性能作了相应的比较。 武汉理工大学硕士学位论文第3章NS2与网络仿真本章从NS2的特点开始，分析了NS2的基本原理、层次结构等。最后在NS2中添加一个本文提出的一种多媒体数据流传输控制协议，进一步来阐明NS2的工作原理和仿真分析的具体过程。3．1NS2简介NS2[231(NetworkSimulatorVersion2)是一个开放源代码软件。它是从1989年的一系列实时网络仿真器开始，并且在过去的多年中不断改进。1995年NS2的开发得到了美国国防部远景规划署(DARPA)所资助的VINT(VirtualInterNetworkTestb)项目的支持。该项目包括有LBL，XeroxPARC，UCB，和USC／ISI等的参与。当前的NS2开发由DARPA的SAMAN项目支持。NS2还包括从NSF的CONSER项目、ACIRI，UCBDaedelus项目、CMUMonarch项目和SunMicrosystems的贡献和支持。目前，通信领域内知名的网络仿真软件主要有NS2、OPNET、OMNET++等，其中NS2的公认程度最高，已被大量的科研机构广泛采用。NS2对现有的网络协议提供了很好的支持，它提供了基本的网络元素支持并用对象来实现，易于组合，易于扩展，这样大大减少了网络模拟研究的工作量；另外，它的源代码开放，这使得利用NS2进行网络模拟的研究者可以很方便的扩展NS2的功能，也可以方便的共享和交流研究成果。NS2可以完成的功能和特点包括：1．构建网络拓扑。NS2中网络拓扑是由Node君ILink构成，其中Node大约可被看作是对实现网络底三层设备的一个模拟，LiIll【则可被视为是对物理传输链路的模拟。2．实现RTP协议的Agent。在NS2中，Agent是对某一个网络协议的模拟。NS2预先实现了UDPAgent和TCPAgent及一些常用网络应用协议的Agent。3．加载应用数据流。Application／Traffic实现加载应用数据流。4．离散事件驱动。其中“事件"是指网络状态的变化，即只有网络状态发生变化时，模拟机才工作，网络状态不发生变化的时间段不执行任何模拟计算。因此，与时间驱动相比，离散事件驱动的模拟机计算效率得到很大提19 武汉理工大学硕士学位论文高。5．建模采用面向对象方式。NS2采用面向对象技术，这就保证了软件的可扩充性和重用性，提高了程序开发的效率。对象的属性能够很容易地配置，每个对象属于相应的行为和功能的类。类也可以继承其他类，也可以通过C++来定义新的类来满足用户自己特定的需求。6．使用两种语言C++和OTcl编写代码。C++程序模块的运行速度非常快，适合用于实现具体的协议。OTcl是面向对象的TCL脚本程序设计语言，适合用来进行仿真的配置。Tclcl模块把出现在两种语言里的变量、对象胶合起来。7．支持各种业务模型和多种通信协议。NS2内置了各种常用的业务模型，包括FTP业务模型、CBR业务模型、on／of!f业务模型等。同时还支持TCP和UDP两种传输协议以及多种路由协议，包括分级路由、广播路由、多播路由、静态路由、动态路由、MAC层协议等。3．2NS2的层次结构NS2是一个用C++编写的面向对象仿真器，它的前端是一个OTcl解释器仿真器内核定义了有层次结构的多种类，称为编译类结构；OTcl解释器中有相似的类结构，称为解释类结构。NS2内核的层次结构如图3．1所示。NS2—多孑7弋≤＼TclTclClass．．InstVat．．TclObject．TclCommandEnbcdedTclNsObject—／—＼ConncctorClassifier／。＼／＼＼＼QueueDelayAgentTraceAddClassifierReplicateDropTailAgentTCPREDAgentMessage图3．1NS2的层次结构NS2用到了六种TCL类【241，他们是：20 武汉理工大学硕士学位论文1．Tel类：封装了OTcl解释器实例，向外提供方法来访问解释器。2．TclObject类：它是两种类结构中的大多数类的基类。3．Telclass类：把用户通过类TclObject在解释器中建立的类结构映射到NS2编译类结构，提供方法来实例化新的对象。4．TclCommand类：提供一种机制使NS2内核向解释器输出简单的命令。5．EmbededTcl类：允许用户以编译代码或解释代码来扩展NS2功能。6．Instvar类：定义了一些方法和机制，在编译类结构对象的成员变量和对应的解释类结构对象的成员变量之间建立映射，使两类变量一致共享。在NS中，绝大部分类都是TelObject类的子类，同时，TelObjeet类也是所有oTcl库对象如调度器、网络组件、计时器以及包括NAM相关对象在内的其它对象的超类。TclOb]eet用一个静态链表来记录用户所创建的所有对象，而每个对象都有唯一的标识来记录其所属的类名。使用公用基类可以将各种对象存储在同一个链表中。函数可以方便的使用和处理对象并按需进行强制类型转换。NsObject一方面是TelObject的子类，另一方面又是全部基本网络组件对象按的父类，包括节点、链路、代理、跟踪记录和数据发送源等。基本网络对象按照输出数据的路径数进一步被分为连接器(Connector)和分类器(Classifier)两个子类。分类器具有一个或多个可能的数据输出路径，比如端口分类器，它根据IP报文中上层协议字段将IP报文提交给相应的上层协议处理。连接器只有一个可能的数据输出路径，即一个单进单出的管道，这一点和分类器有一个或多个可能的数据输出路径是截然不同的。连接器的例子包括：队YlJ(Queue)、代理．(Agent)、信道(Channel)等。NS2对网络构件所做的第二次抽象是从Connector和Classifier中派生出一系列的类来将功能进一步细化。从Connector中派生出的Queue类用来表征分组被存储、排队的队列机制；Channel类用来表征数据传输中所使用的共享物理介质；Agent类用来表征产生、接收、处理网络层报文的终节点。Monarch扩展也引入了Topography拓扑对象来跟踪每一时刻网络上节点的拓扑关系。3．3NS2的工作机制图3．2是NS2的总体框架图，．普通的用户(非NS2的开发人员)在左下角的位置思考，使用在OTcl库中的仿真对象设计和运行用OTcl语言编写的仿21 武汉理工大学硕士学位论文真程序。事件调度器和大多数网络元件使用C++开发，并且通过OTcl链接在OTcl中使用。因此，可以将NS2看做是一个具有网络仿真库的面向对象的Td解释器。为了设置和运行一个网络仿真，用户需要编写OTcl脚本来初始化一个事件调度器，使用网络组件对象(NetworkComponentObjects)建立一个网络拓扑并且利用网络连接模型(NetworkSetupHelpingModules)将创建的各个网络对象连接起来，确定网络流量源的开始时间与结束时间，通过事件调度器传送数据包。EventSchedulerNS2Ztclcl量吴昙习暑图3-2NS2的框架图当仿真结束时，NS2产生一个或多个输出文件。这些文件中包含输入OTcl脚本中要求的详细仿真数据。这些数据可以用于仿真分析或者作为图形仿真显示工具NAM(NetworkAnimator)的输入文件。它可以动态的显示数据包的吞吐量和每条链路的丢包情况等。3．4NS2的仿真流程NS2仿真分为两个层次【25~261，其仿真流程如图3．3所示。一个层次是基于OTcl编程的配置、构造层次，利用NS2已有的网络仿真元素实现仿真，无需对NS2本身进行任何修改，只要编写OTcl仿真脚本。它的基本步骤是：1．创立仿真器并配置或构造仿真网络拓扑(包括链路和节点)。仿真之前首先要构造一个基本的网络拓扑平台。此时，可以确定链路的基本特性，如时延、 武汉理工大学硕士学位论文带宽和丢失策略等。2．建立协议代理，包括端设备的协议绑定和通信量模型的建立。3．给节点进行特性化配置。根据仿真具体要求对节点进行代理、路由协议等的初始化。4．编写必要的OTcl过程或构造可能需要的OTcl类，如记录过程等。5．进行仿真结果的追踪。NS2通过建立追踪文件来保存仿真期间网络性能的参数变化。6．设定通信量应用和时间相关过程的发送、结束时间，然后运行仿真。7．仿真结果分析。仿真完成后，调用相应观察器(如Xgraph，Nam)对结果文件进行分析、研究。图3．3NS扩展与仿真流程另一个层次是基于C++和OTcI编程的编译、配置层次，即对NS2进行扩展。如果NS2中没有所需的仿真元素，NS2提供了用户自我升级或修改协议的技术，即利用oTcl和NS2的接口类来实现NS2的更新，添加新的协议。它的基本 武汉理工大学硕士学位论文步骤如下：1．NS2用户添加新的C抖类，然后重新编译NS2。2．编写OTcl脚本进行仿真。3．对仿真结果进行分析。如果不满足用户要求，修改新协议，转第1步。否则结束。-仿真过程要用不同的场景文件，不断修改仿真脚本，直到能得到较为稳定的仿真结果。3．5NS2的无线模块NS的无线模块是以移动节点(MobileNode)为基本核心的，并通过一些附加的特性来支持AdHoc网络模拟。MobileNode类是Node类的派生类，它扩展了Node类的功能，这样它可以用来创建移动、无线的模拟环境。MobileNode是一个由C++和OTcl共同实现的对象，它的功能主要有：节点移动、周期性的位置更新、维护拓扑边界等。它是在C++中实现的，而设定MobileNode的各个网络构件(例女HClassifier、LL、Mac、Channel等)则是在OTcl中实现的12¨。在NS2中移动节点的结构如图3．4所示。图3_4移动节点的结构24 武汉理工大学硕士学位论文创建一个移动节点，首先通过node—config函数来进行配置，可以配置的选项包括：AdHoe路由协议、网络协议栈、信道、拓扑、无线传输模型以及是否打开路由trace、是否打开各层(agent、router和mac)的trace。具体配置方法如下：$nS-node·config-adhocRouting$val(rp)＼-llType$val(11)|一macType$val(mac)|-ifqType$val(ifql＼·ifqLen$val(ifqlen)|一antType$val(ant)|一propType$val(prop)|一phyType$val(netif)|．channel$channel|一topolnstance$topo|-agentTraceoN＼．routerTraceON|．macTraceOFF|．movementTraceOFF通过下面的方法来创建移动节点：for{setiO){$i<$val(nn)){incri){setnode_($i)[Sns_node】$nodc_($i)random—motion0；)3．6一种多媒体数据流传输算法的实现与仿真由于UDP协议没有拥塞控制机制，若基于TCP协议的应用和基于UDP协议的应用共享同一个网络，当TCP检测到网络拥塞时，根据AIMD算法，TCP的发送端会将发送的速率降低一半，如果TCP不断检测到网络拥塞，TCP的发送端会不停降低发送速率，直到停止数据的发送。这时UDP就会独自占用带宽，导致相关连接的WWW、f碴等数据流全部停止工作。解决这个问题的 武汉理工大学硕士学位论文方法之一是在基于UDP协议的应用中增加拥塞控制机制，使基于UDP和基于TCP的数据流能共享带宽【281。本文改进了一种基于UDP协议的多媒体数据流发送时的速率调整算法并利用C++语言在NS2上实现了这一算法，最后进行了仿真实验。现有的NS2的各版本中，均把TCP和UDP连接作为数据传输的主要方式，本文采用的是NS2．29。为了对多媒体数据流进行合理的传输，必须对NS2．29的UDPAgent进行适当的修改，再添加实现算法的C++源码，最后对NS2．29进行重新编译。3．6．1改进的多媒体流传输控制算法算法描述：发送端以速率R口c加，发送媒体流；while(R口。m口l<发送速率上限尺){接收端监测网络状态(status_)；接收端每隔，．“时间向发送端反馈网络状态(status_)；if(丢包较多)降低R删删；else<增加R删Ⅳ口，；if(R删删>发送速率上限R)降低R口cm口，_1／2R；)这个算法的主要目的是让基于UDP流能与与TCP流合理地竞争带宽，尽量使得多媒体数据流能获得更平滑的数据发送速率和更小的抖动。3．6．2传输协议UDPMultimedia的定义实时多媒体数据流是基于UDP协议的，所有的媒体信息都要作为数据流交给UDPAgent进行传输。然而在NS2中，UDPAgent只具有常用的一些数 武汉理工大学硕+学位论文据包头结构，为了实现对多媒体数据进行发送和接收，必须在UDPAgent中增加一个数据包头结构：structhdr—multimedia{intsequene；／／媒体数据包的序号intnb矾es；／／当前数据包发送的个数doublelocatime；／／当前的时间intack；∥判断当前数据包是否是反馈数据包intadjustvale：／／发送速率调整的尺度staticintoffset：／／数据包头在包头栈中的偏移量inlinestaticint&offset(){returnoffset_；}inlinestatichdr—multimedia木access(constPacket木p){return(hdrmultimedia)p一>access(offset_)；>)为了不影响NS2的完整性，本文定义了UDP的一个子类：UDPMultimed．ia，把hdrmultimedia头结构放在UDPMultimedia中，用它来完成多媒体数据流的传输任务，收集相应的速率控制和调整信息。3．6．3代码说明本文一共编写了6个文件，分别是：udpmultimedia．h、udpCC和multimediatrans．h、multimediatrans．CC以及speed．h、speed．CC。其中前面两个是实现对UDPAgent的改进，使它能处理多媒体数据流；后面四个是对多媒体数据流发送速率的确定、调整和控制，使多媒体数据流进行合理的传输，不致于引起基于TCP协议的数据流的拥塞。。这6个文件均放到NS2目录中。3．6．4修改NS2中的相关配置文件首先在packet．h和as．packet．tcl中对新的数据包头进行登记；接着在agen-t．h中添加支持多媒体数据流功能的代码；另外在app．h中增加recvmsg()i甄i数声明，recv_皿sg()函数的主要作用是从下层代理中接收数据包并作出相应处 武汉理工大学硕士学位论文理，它是在multimediatrans．CC中实现的。最后还要在ns．default．tcl中设置文件中用到的变量的默认值。3．6．5仿真与比较分析为了测试多媒体数据流是否能与TCP流共享带宽，本文作了两组仿真。一组是让基于UDP协议的恒定速率发生器CBR所产生的数据流与基于TCP协议的FTP应用数据流共享一条1M的带宽，另一组是TCP数据流与多媒体流共享一条1M的带宽。从竞争的角度考虑，每一组又分别设置了两个FTP流和两个CBR流或两个多媒体流。网络仿真拓扑结构如图3．5和图3-6。t—书图3．5TCP流与UDP流共享带宽图3-6TCP流与多媒体流共享带宽在图3．5和图3-6的两种仿真环境中，ftpl在0．5秒开始发送数据流，在124．0秒停止发送；lip2在1．0秒开始发送数据流，在125．0秒停止发送；cbrl和mml均在1．5秒开始发送数据流，在120。0停止发送；cbr2和mm2在2．0秒开始发送数据流，在121．0秒停止发送。28 武汉理工大学硕士学位论文对图3．5和图3-6所示的网络参数分别进行仿真结束后，分析产生的trace文件进行，计算出却1、邱2、cbrl、cbr2四种数据流以及ftpl、ftp2、mml、mm2四种数据在各个时刻的吞吐率，利用plot作图，分别如图3-7、图3-8所示。图3．7FTP流和CBR流共享带宽时的吞吐率图3．8FTP流和多媒体流共享带宽时的吞吐率从图3。7可以看出：当基于TCP的FTP数据流和基于UDP的数据流在2秒左右竞争带宽时，ftpl和ftp2的吞吐率急剧下降，40秒后，ftpl的吞吐率一直处于O．05左右；ftp2的吞吐率更低，在110秒左右就因拥塞太严重而停止发送数据。相反，cbrl和cbr2却一直处于很高的吞吐率。这说明，当基于8765珥32l08765432l0O0 武汉理工大学硕士学位论文TCP的数据流和基于UDP数据流共享带宽时，会造成TCP传输的严重地拥塞。从图3．8可以看出：当FTP流和多媒体流在2秒左右竞争带宽时，flpl和邱2的吞吐率有所下降，10秒后，flpl和邱2流和multimedial和multimedia2流吞吐率均处于相对平衡的水平。这说明，利用改进后的传输控制算法所产生的多媒体数据流和基于TCP协议的数据流共享带宽时，不会造成TCP传输的大的拥塞。把上面两图中的FTP数据流放在同一个图3-9中，就能更明显的比较这两种情况的TCP流的吞吐率的变化情况。图3-9两种情况中的TCP流吞吐率的比较实验证明，当基于UDP的多媒体流与基于TCP的数据流共享带宽时，利用改进的传输控制算法对多媒体数据流的发送速率进行适当地控制，能有效的减轻TCP流的的拥塞。3．7本章小结深入掌握网络仿真软件NS2，对我们研究和开发AdHoc网络的路由协议有极大的帮助。本章深入研究和分析了NS2的基本原理、层次结构、工作机制、无线节点的结构，以及NS2的仿真流程。通过在NS2中添加一个新的多媒体数据流传输协议，详细阐述了利用NS2进行仿真实验的过程。最后，对新的传输协议的性能进行了比较、分析。876543210O0 武汉理工大学硕士学位论文第4章一种改进的多径路由协议MPDSR这一章将对AdHoc网络的多径路由协议进行深入的研究和分析；提出一种改进的基于DSR多径路由协议MPDSR，对它的路由机制和思想作出详细的阐述；最后对它进行仿真分析。4．1多路径概述有线网络中的多路径路由的研究比较多，但是在AdHoe网络中的多路径路由研究才刚刚开始。这主要是多路径路由的算法复杂、实现困难，而在AdHoc网络的动态拓扑下的实现更加困难。4．1．1多路径路由的概念多路径路由指的是一对通信节点之间能同时提供多条可用的传输路径，并允许节点主机(或应用程序)选择并使用这些路径进行数据流的传送。因此多径路由算法要能为节点间提供多条传输路径，并确保发往其中一条或几条路径的数据能到达目的地。对于多路径的使用方法，现在主要是有以下两种基本的模式【29】：1．先使用主路径，当主路径失效后再利用备份路径作为主路径的替换路径。这种模式也称为替换多径。2．同时使用多条路径。不分主次，按照一定的权重在各条路径上分配一定的数据流，同时传输。这种模式也称为同时多径。4．1．2多径路由的特点相比单路径路由，多路径具有可靠性高，能提供更好的吞吐量等优点。由于有多条路径可传输数据，当其中一条路径出现问题时，可通过选择另一条路径或增加其它路径流量等方法来保持继续传输，对应用层来说几乎没有什么影响。多条路径同时传输，能在很大程度上提高传输的流量，适用于某些带宽要求特别高的应用，也能降低突发的大量数据流对网络的影响。多路径路由算法与单路径相比具有以下显著特点： 武汉理工大学硕士学位论文1．加快传输速度，减少时延。在多条路径之间分配资源进行传输，其传输性能明显优于单路径。2．提高网络路由的可靠行，增加稳定度。由于AdHoc网络中节点具有很强的随机移动性，整个网络的拓扑结构会频繁变化，链路断开的情况将经常发生。单路径中如果断裂，传输将失败，必须重新进行路由发现，多路径算法中当有路径断裂时，其他路径可以照常传输，可以将资源重新分配给稳定的路径而不是重新进行路由发现。3．平衡网络负载。单路径的路由协议往往把数据分组的转发工作全部放在一条路径的节点上，可能导致这些节点过载而拥塞。在多路径的路由协议中，数据分组可以分配到多条路径当中，使负载平均分布。4．提供QoS服务。如果在源节点和目的节点之间能够同时使用多条互相独立的路径，它们之间的实际带宽就等于各条路径的带宽和。这样就能够充分利用网络资源，有效的减少对带宽的限制，满足一定的QoS需求。4．1．3多路径的分类多路径按照相关性原则可分为二种类型【30】：节点不相关多径和链路不相关多径。1．节点不相关多路径(Node．Disjoint)节点不相关多路径，也可以称为完全不相关多路径，路径之间除了源节点和目的节点之外没有共用的节点或链路。如图4．1所示，源节点S与目的节点D之间的路径(S'A，B，C，D)、(S，E，F，GD)、(S，H，I，J，D)是典型的节点不相关多路径。图4．1节点不相关多径32 武汉理工大学硕士学位论文2．链路不相关多路径(Link—Disjoint)链路不相关多路径指的是各路径之间没有共用的链路，但是可能有共用的节点。如图4—2所示，源节点S和目的节点D之间的路径(S，A，B，C，D)与(S，E，F,C，D)是链路不相关多径，它们共用一个节点C；同时(S，E，F，C，D)与(S,G,F,H，D)也是链路不相关多径，它们共用一个节点F。图4．2链路不相关多径在上述两种多路径类型中，节点不相关多径路由的容错能力最强，链路不相关路由的容错能力较低。在链路不相关多路径路由中，如果共享的节点由于移动等原因发生中断的话，那么该节点所连接的所有路径便都失败了，而节点不相关路由由于链路的独立性，则不会产生连锁反应。一般在网络分布密度相对较大的情况下，采用节点不相关多径路由，但在节点密度相对稀疏的网络环境中，会采用链路不相关多径路由。4．2典型的多路径路由协议分析近年来，研究者相继提出了一些AdHoc网络的多径路由算法，具体内容可参考文献[31～34】。下面分别对几个比较典型的多径路由机制进行分析和比较，它们分别是MSR、SMR、AOMR。4．2．1MSRMSRt35](MultipathSourceRoutingAlgorithm)是一种在DSR的基础上扩展的多路径源路由算法，它继承了DSR的优点，利用中间结点和目的结点反馈多条路径，并使用路径探测来减少网络拥塞和网络时延。 武汉理工大学硕士学位论文MSR采用与DSR相似的路由发现算法。它让拥有到达目的节点的中间结点反馈相应路由信息，由此获得到达目的节点的多条路径，并将这些路径通过唯一的路由标识存储起来。为了监视MSR中每条路径的实时信息，MSR使用探测作为反馈控制机制。它通过在不同路径上定时发送探测包来测量它们的R1阿，并使用Karn算法估算路径时延，以此来反映该路径的性能。因为如果一条路径时延太长的话，分配给它的流量将会比较少，以避免拥塞。依据这个时延，MSR给出了一种流量分配的方案，希望以此使得整个网络的平均时延最小。MSR的负载平衡对减少端到端的时延具有显著效果，充分利用了网络资源，吞吐量有了较大的提高，端对端时延和丢失率相应减少。在负载分配时，MSR使用权重循环策略(weighted．round—robin)，根据每个路径的传输数据的能力，给每个路径分配不同的权值，使其能够接受相应的权值数的负载。。‘但是MSR有一定的缺点，在负载分配时它假设多路径完全独立，而在路由发现时它并没有实现路径的完全独立，只是试图找出一种最大的脱节多路径，同时也增加了计算复杂度，并且需要为探测付出额外的开销。4．2．2SMRSMR[36](SplitMulti．PathRouting)建立和使用最大不相交路径的多条路由。多条路由是按需寻找的，其中有一条是最短时延路径。建立的各条路由不必是等长度的。数据传输被分散到各条路由上进行，以便避免节点拥塞，高效的利用有效的网络资源。SMR采用与DSR相似的路由发现机制(通过RREQ和RREP的循环)，但做了一些改进：当源节点需要发送数据到目的节点而没有路由时，它用洪泛的方式发送路由请求包(RREQ)，请求包通过不同的路径到达目的节点，目的节点根据所获得的路径选择最大脱节多路径并发送应答包(RREP)至tJ源节点。为了让目的节点获得从源节点到目的节点尽量多的路径，中间节点缓存内不管有无到目的节点的路径都不允许发送RREP包。如果中间节点象DSR一样发送应答包到源节点，目的节点就不能获得中间节点所转发的路由信息，从而不能有效的选择出多路径。中间节点有选择的转发RREQ分组，其条件是RREQ通过的输入链不同于所接收到的第一个RREQ分组，并且其跳数不大于所接收到的第一个RREQ分组的转发跳数。这种方法的缺点是需要发送更 武汉理工大学硕士学位论文多的RREQ分组，但是却能够找到最大不相交路径。在SMR中，目的节点选择两条最大不相交的路径。其中一条是最短时延路由，即到达目的节点的第一个RREQ分组所经过的路径。使用这条最短时延路由作为所选择的两条路由中的一条，以便使按需路由协议所要求的路由获取时延最小。目的节点接收到RREQ分组后，记录其通过的整条路径信息，然后通过该条路由给源节点回送～个RREP应答分组。RREP应答分组中记录有整条路径的各个节点的身份识别码ID，所以中间可以使用这个路由信息转发该RREP应答分组。目的节点完成这个过程之后，等待一段时间，以便接收更多的RREQ分组和获得所有可能的路由：然后从中选出一条路由，该条路由与已应答的那条路由最大不相交。因为目的节点知道第一条路由和所有其他候选路由的完整路由信息，所以目的节点能够选出最大不相交路由。如果与第一条路由最大不相交的路由有多条，那么就选择将RREQ分组最快传递给目的节点的那条路由。然后，目的节点沿着选出的第二条路由给源节点回送一个RREP分组。在SMR中，当一个节点不能将数据分组交付给其传递路由上的下一跳节点(例如，通过接收到的IEEE802．1l链路层反馈信息，或者接收不到被动应答来判断)的时候，该节点则认为该条链已经失去连接，然后朝路由上行方向发送一个RERR分组。RERR分组包含到达源节点的路由、中断链的紧邻上行节点和紧邻下行节点的信息。源节点接收到RERR分组后，将路由表使用了该条中断链的全部条目删除。如果一次会晤的两条路由中只有一条路由无效，那么源节点则使用剩余的那条有效路由继续传递数据分组。源节点在得到路由中断通知，并且会晤还在进行时，可采取以下两种策略中的一种重新寻找路由。(1)多路径中任何一条路径出错时，发起一个新的路由请求RREQ。(2)多路径中所有路径都出错时才发起新的路由请求。这两种处理方法各有优、缺点，第一种方法能确保在数据传输过程中一直使用多路径传输，缺点是比第二种方法使用较多的RREQ请求包，但路由健壮性要好。4．2．3AoMRAOMR[37~381(AdHocOn．DemandMulti．pathRouting)也是DSR协议的一个扩展，它是A．Nasipuri和S．R．Das提出的。协议的主要思想是为源节点和中问节点提供一条以上的替换路径(AletemateRoute)。由于替换路径与主路径是独35 武汉理工人学硕士学位论文立路径，当主路径失效时，数据传输不会被打断，而是换用替换路径来继续发送数据包。AOMR的路由发现过程和DSR基本相似。不同的是，当第一个路由请求RREQ包到达目的节点以后，目的节点除了向源节点发送路由应答RREP包之外，还记录下这条路径，作为主路径。对于随后到达的路由请求包，如果其中的路径和所记录的所有路径都是独立路径，目的节点就发送相应的路由应答包，同时记录下这条路径；否则，直接丢掉该路由请求包。这样既可以保证当主路径失效时，其它路径还可以发包(因为它们和主路径是相互独立的)，又避免了目的节点发送过多的路由应答包而带来不必要的网络拥塞。A．Nasipuri和S．R．Das提出并比较了两个对DSR所进行的多径扩展。在第一种扩展中，只有当路由请求包中所含路径和已经记录下的所有路径都独立时，目的节点才会发送相应的路由应答包。这样，当路由发现过程结束的时候，源节点就有了多条到目的节点的彼此独立的路径，而具体采用几条路径发包是一个可选的系统参数。当主路径失效后系统会自动选取剩余可用路径中最短的一条路径继续发包直到所有路径都失效，系统才会发起一次新的路由发现过程。在第二种扩展中，替换路径不是像前一种那样只存储在源节点上，而是也被存储到主路径的各个中间节点中。这样，当路径失效时，丢失的数据就会降到最低。具体实现：目的节点在发送路由应答包时，不仅给源节点发送，同时还给主路径上的各个中间节点发送。由于路由应答包的增多，在第二种扩展中，除主路径外，只保留一条替换路径，这是它和第一种扩展的另一个区别。在A．Nasipuri和S．R．Das所设计的分析模型中，他们假定各条路径的路由有效期(路径可用时间)是具有相同均值的指数分布的随机变量，并且都彼此独立。基于这个假定，作者给出了公式，可以算出相邻两次路由发现间隔的均值。计算结果表明，第一种扩展减少了路由发现之间的时间间隔。但是，在第一种扩展中，如果要同时保存两条或更多的替换路径，这种扩展所带来的性能提高是微乎其微的。同样的，第二种扩展也只带来了很小的性能改善。4．3多路径路由协议MPDSRMPDSR(Multi—PathDynamicSourceRouting)是本文提出的一种改进的基36 武汉理工大学硕士学位论文于DSR的独立多路径路由协议。现有的多路径路由算法在减少路由控制包，多路径的稳定性等方面考虑得不够充分。为了能减少多径之间的干扰，使负载均衡，本文重点在节点无关路径算法方面做了深入的研究，使得MPDSR协议在路由开销不太大的情况下明显的增加了分组投递率，降低了时延。4．3．1多路径的稳定性分析AdHoe网络的路径稳定性同许多因素有关，比如说无线信道的干扰，地理位置的影响，节点的移动性等。在本节的稳定性分析中，不考虑其他因素，只考虑节点的移动性以及路径的相关性对路径稳定所产生的影响【39枷1。假设在路径Path(a，，口：，⋯，a。)中，每个节点因移动等原因而造成路径失效的概率均为P。则有：该路径的稳定性为：￡埘姗=(1一p)“；(4一1)而其失效率为：只删=1一匕6肌=1一(1一p)”；(4—2)依据概率的特性，我们知道0≤1一P≤l，因此有0≤(1一p)”≤(1一p)“≤1(1≤m<以)(4-3)0≤1一(1-p)”≤l一(1-p)”≤1(1≤m<拧)(4-4)即己≤只。由此可知，单路径路由中，路径的节点个数越多则该路径越不稳定。定义MPi为包含两条路径的多路路由，其中i值为两条路径的共用中间节点数。设第一条路径的跳数为，l，第二条为m，因此0≤i≤min(n，掰)当i=O，即为MPo，它包括的两条路径分别是尸口l，么2，⋯，彳^)和P(BI，历，⋯，召小)没有共用的中间节点，如图4．3所示，则其失效率P(MPo)为：P(MPo)=【1一(1一p)”1[1一(1一p)”】(4—5)当i=1，即为脚l，它包括的两条路径分别是尸(Cl，C2，⋯，G)和P暇l，易，⋯，厶)有一个共用的中间节点C2，如图4．4所示，则其失效率P(MPI)为：P(MPl)=【1一(1一p)”1】[1一(1一p)埘1】+p(4—6)如此类推，37 武汉理工大学硕士学位论文当i=k，即为MPk，它包括的两条路径共用中间节点数为k，其中k=min(n，m)。则其失效率P(MPk)为：P(MPk)=[1-(1-p)”‘】[1-0-p)”‘】+kp(4—7)⋯一一◇⋯⋯⋯一◇⋯⋯图4-3多路径MPo⋯9～⋯9⋯图4-4多路彳仝MPl下面我们比较MPk和MPk．1的失效率，令q=l--p。嗍)一P(帔一。)=[1一(1一p)4t】[1一(1一p)7’H】+kP一【1一(1一p)”·七-1’】【1一(1一力州卜1’卜(七一1)p≥(1-q)O—q”一‘一q”t+g“一‘g“一七)=(1一g)(1_qm-‘)(1-q舻‘)≥0即P(假)≥P(MP七一1)(4-8)flj(4．8)式可知，有k个公共中间节点的多路径集MPk比有如1个公共中间节点的多路径集朋P缸l的失效率高。由此，我们可以得出下面的结论：P(^以之)≥P(MPy)≥P(MPo)(石>Y>o，x≤min(n，m))(4·9)由(4．9)式可知多路径中的公共中间节点越多，其稳定性越差。因此，节点不相关类型的多路径稳定性最好。综合上面两个方面的分析和结论，我们应该按照以下原则来寻找多路径：38 武汉理工大学硕士学位论文1．每条路径中的中间结点要尽量少；2．尽量寻找节点不相关的多路径。4．3．2．多路径数目的确定在相关的多径路由文献中，一般只是介绍如何寻找多径路由，但是对多径的数目却没有明确的说明和分析。实际上，并不是多径数目越多，效果越好。寻找到路径越多，路由开销也会相应的越大，协议的性能不但没有提高，反而还会下降，因此多径数目的确定有着重要的意义。本文通过数学分析的数据比较来确定路由数目的最优值。1．数学分析用一个随机变量表示一对通信节点之间的一条链路的寿命。考虑一条从源节点S到达目的节点D的路由，由跨越缸1个中间节点的k条链路组成。设乞i为路由中第i条链路，其生命值设为彳厶。这里假设了X厶(i=1，2，⋯，舡l>为独立同分布的变量，每个变量的均值为，。在路由P中，只要其中任何一条链路中断，路由P就会中断。因此路由尸的寿命％是一个随机变量，可以表示为：Xp2minCXt,，丘，⋯，托)⋯o)根据文献[41～421可以知道％为服从指数分布的一个随机变量，其均值为／／k。下面推导多径路由中连续两次路由寻找之间的时间间隔r的统计特性。假设源节点s到目的节点D有Ⅳ条路由。其第一条记为尸l，剩下的N-1条分别记为B、尸3、⋯、PⅣ，路由B的长度记为岛。当源节点发现所有路由均不能使用时就要发起新的路由寻找进程，那么两次连续路由寻找之间的时间间隔Z是一个随机变量，可表示为：T=maxⅨ日，％，-，xPⅣ)(4—11)对于Ⅳ个独立同分布的指数分布变量x毋，如，⋯，x目，x辟，它的概率密度分布函数为：^。(f)=以P叫(以=ki／li=1,2，⋯，N)(4—12)因为XP是相互独立的，所以r的累积分布函数辱(f)为：弓O)=e[T≤t】=e[maxor毋，X恳，⋯，XPⅣ)≤t】=尸[(x毋≤t)n(叉-≤f)n⋯n(x岛≤f)】39 武汉理工大学硕士学位论文Ⅳ=兀‰o)iM由fx。(f)=z,e～，可以得到瓦。(f)=1一e一钾，边对t微分。由此便得到r的概率密度分布函数：厶(f)=21e-a,'(1一e-,W)(1一P一南‘)⋯(1一e-aNt)+如P一如‘(1一e-a,‘)(1一e-&t)⋯(1一e一2∥)+⋯+ANe-2一t(1一e-即)(1一P一如’)⋯(1一e一知+t‘)根据(4．14)式，来求丁的期望值以乃，(4-13)将其代入(4．13)式中后，两(4-14)占(砷=Itfr(t)dt(4—15)5下面通过一个实例来简单说明以乃与多径数目的关系。令N=2，可以求出丁的期望值为：E(jrT)=子0[^P呐‘(1一e一句)+五P一缸(1一P一却)】出=号揣(4-16)—1—2、一l⋯2，此时，如果主路由长度kl=3跳，次路由恕=4跳，则：印)=遵半，=昌㈨044051(4-17)、712×784然而对于一条长度为3的路由单路径来说，r的期望值为：E(丁)=L，，I≈0．3333l(4-18)由(4．17)和(4—18)可以发现，两条路径路由协议的路由寻找频次比单路径路由协议的降低了25％。2．数据分析用前面介绍的分析方法很容易计算出一定量的数据结果，通过这些数据我们能比较、分析出当多径数目为多少时，能使得协议的路由寻找频率最佳。为了简化计算，我们使用了两种特殊情形下的数据来作统计。情形么：假设源节点S和目的节点D之间的Ⅳ条路径中，最初的路径是最短的一条，其他路径的长度是递增的，且每条路径和长度增l。即：kl=k，k2=k+1,---,k=k+Ⅳ一1；情形雪：假设源节点S和目的节点D之间的Ⅳ条路径中，最初的路径是 武汉理工大学硕士学位论文最短的一条，其他路径的长度是递增的，且每条路径的长度增2。即：岛=露，如=k+2，⋯，kN=k+2(N一1)；在计算中令，=1。同时设定七=3，Ⅳ=1，2，⋯，7，统计结果如4．5图所示。图4-5E(D与与多径数目N的关系从上图4-5中，可以发现：以乃随着Ⅳ的增大而增大。当N>3时，这种增长的趋势变得很缓慢。因此确定多径路由时，一般取路径数N=3就足够了，如果超过3，性能改善不但不明显，反而增加了协议的路由开销。4．3．3MPDSR路由协议的路由寻找MPDSR路由协议主要是在DSR路由协议的基础上添加了多径发现机制，从而继承了DSR协议的以最短跳数作为选路的标准的方法。这既是出于路径稳定性的考虑，又便于MPDSR的实现。同时，为了能尽可能的捕获到多条节点不相关的路径，MPDSR增加了DSR的缓冲区的容量，使得中间节点能尽可能多的存储路由记录，当然为了控制路由消息的全网洪泛，对于缓存数量也作了一定的限制。当目的节点得到了多条路径信息记录后，以跳数最短的路径作为主路径选择出节点不相关的多条路径，并向源节点作出RREP回复，源节点收到RREP回复包后，启动数据传输机制，发送数据流。MPDSR协议改进了DSR的RREQ报文，增加了几个字段，便于记录和判别多径记录。同DSR协议的路由寻找过程不同的是，MPDSR协议的路由4l 武汉理工大学硕士学位论文寻找过程包括三个部分：路由请求、节点不相关路由的选择和路由回复。1．路由请求在路由发现过程中源节点首先向其邻节点广播RREQ报文。RREQ报文格式如下：(Source—Addr，Destination—Addr，Request_ID，Route—Record，Hops)SourceAddr表示源节点地址；DestinationAddr表示目的节点地址；RequestID是路由请求报文序列号，是区分请求报文的标志；RouteReco坩表示路由记录，用于记录从源节点到目的节点路由中的中间节点地址，当路由请求报文到达目的节点时，该字段中的所有节点地址即构成了从源节点到目的节点的路由。Hops表示从源节点到当前节点所经历的跳数，它是控制路径数目过多而加重路由负载的一个重要参数。中间节点维护序列对列表，，>序列用于惟一标．Addr是否存在于本节点的序列对列表中。若不存在，则跳转到第二步执行；若存在，则表明此请求报文已经收到过。节点然后判断新收到报文中的路由信息是否与已保存在路由记录队列表中记录相同。若相同，丢弃该路由请求报文，这样能有效的防止环路的形成；否则，按下面的原则进行处理：(1)检查本节点路由缓存中是否存在到目的节点的路由记录。若不存在，则跳转到(2)执行。否则，利用缓存路由信息直接向目的节点发送路由请求报文。如果存在多条到目的节点的路由记录，那么选择跳数最少的路由向目的节点发送路由请求报文；(2)无论本节点是否存在缓存记录，中间节点作如下判断：①是否超过转发最大次数TransMax。若超过，则丢弃路由请求报文；否则，跳转到②进行判断执行；②判断路由请求报文中的Hops>hop。若真，则丢弃路由请求_max报文；否则，跳转到③进行判断执行；·③判断Hops。。存．ID在于本节点的序列队列表后，将节点地址附在报文的“路由记录"字段，更新报文中相应信息后，向邻节点广播该路由请求，并转第五步；第五步将该请求报文中的路径信息保存在相应的缓存中，作为其他路由请求的冗余路由。当目的节点在收到第一个路由请求报文后的△d时间内，继续接受其它的请求报文，并保存相应的路由信息。酣时间以后，如果继续收到请求报文则不处理。这样，目的节点记录了多条路径信息。下面通过实例，来进一步来说明路由发现过程。如图4．6所示，源节点S到目的节点D之间存在多种可能的路由。其中TransMax=3，hopmax7，AHops=l，节点的路由最大缓存数为6。按照MPDSR协议的路由机制，源节点S如果想向目的节点D传输数据。它首先检查路由缓存中是否存在到D的路由，如果存在，则利用现有路由进行数据的传送。如果S的路由缓存中没有可用的路由，则它启动路由寻找机制，向邻节点A、B、C发送路由请求报文(RREQ)，如图4．7所示。节点A收到从S发送来的RREQ之后，检查自己的路由缓存中是否有到D的路由可用，没有则把自己的地址添加到RREQ的路由记录表中后向邻节点B、E、F转发。同理，其他的节点收到这个RREQ后也作相同的处理。为了控制路由开销，本文规定每个节点对于一个相同的报文的转发次数不能超过3次。转43 武汉理工大学硕士学位论文发的次数太多会增加节点不相关路径选择的难度，也会造成节点能量的过度消耗。同样，节点的路由缓存容量如果设置过大，也会使路由寻找过程中的查找和比较的难度增加，加重网络的路由负载。本文根据仿真实验结果的比较，确定路由缓存记录最大数为6。当路由缓存中的记录已经达到6条时，再加入新的记录时，就要把新记录和原来的记录作跳数上的比较。如果新记录的跳数短，则先删除跳数长的记录，再加入新的记录。如果新的记录的跳数比现记录长或是相等，则丢弃。当节点G中的路由缓存记录为(SCG，SABG，SBCG，SCHG)时，收到从B点发送过来的RREQ报文，它的路由记录为SBG，节点G的路由缓存没满，且SBG的跳数没有超过缓存记录，则加入到缓存中，结果是是AdHoc网络移动节点集合，E={el，e2，⋯，em)是AdHoe网络寻找到的多路径的链路集合【4”。由于是在相对较短的时间内作出节点不相关路径的选择，所以链路集合层将相对稳定。如果某节点i(iE功和节点j(je功是一条路径上的两个相邻的节点，则表示节点i到节点_，之间存在一条有向链路eiy(eiy∈目。针对图G中源节点S和目的节点D，我们可以按照跳数最短的标准来寻找节点独立的多路径集合MPo，具体算法如下：MPDSR节点不相关路径选择算法：while(目的节点构造有向图G(巧D){max_num(Path)=3；朋咒=≯；num—Meo=O；利用Dijkstra算法从有向图G中寻找从S到D的最短路径P；if(P存在)／／用于保存到某节点的所／／有路径及路径相关信息ClassDestination：publicTclObject／／保存到目的节点的所有{／／路径及路径相关信息Cache—to—Node幸dest_array；intsize；>4．5仿真实验4．5．1仿真环境及参数仿真环境及参数配置情况见表4．1。本文所统计的每个数据都是取5个随机场景文件仿真的平均值。用脚本语言awk统计trace文件，并用gnuplot工具作图。4．5．2统计指标1．分组平均投递率(PacketDeliveryRatio)定义4．1分组平均投递率=％纂差篆裂器器49 武汉理T大学硕士学位论文2．路由控制开销(RoutingOverheadRatio)定义4．2路由控制开销=垄藿篓嵩篙篆器3．平均端到端的时延．(AverageEnd—to—EndDelay)定义4．3平均端到端的时延=∑(数据分组i接收时刻一数据分组i发送时刻)／接收数据分组总数。表4．1仿真环境及参数配置项目环境、参数配置操作系统RedHat9．0仿真软件及版本NS2．29路由协议DSR、MPDSR网络拓扑：市点数为50个、随机分布场景800m×800m节点移动模式节点随机移动，平均速率在0～25m／s之间数据源CBR，发包率为1．0，包人小为512bytesMAC协议IEEE802．1l天线类型OmniAntennaTwo-RayGroundReflectionModel，无线电传播模型载频是914MHz，带宽为2M：4．5．3仿真结果及分析仿真实验NAM动画截图如图4．13所示。为了充分的考查MPDSR协议的性能，本文进行了两组仿真实验。第一组仿真实验中，节点具有相同的最大移动速率，不同的连接数。实验中节点最大移动速率为10m／s，节点间的连接数分别是：5、10、15、20、25、30。比较DSR和MPDSR协议的分组投递率、端到端的时延和路由控制开销，反映网络负载对协议性能的影响。第二组仿真实验中，节点具有相同的连接数，不同的节点最大移动速率。实验中节点间的连接数是15对，节点的最大移动速率分别是：0、5、10、15、20、25。比较DSR和MPDSR协议的分组投递率、端到端的时延、路由控制 武汉理工大学硕士学位论文开销，反映节点的移动对协议性能的影响。v墨■重量田墨■■—■■—■■■■■■■■■■■■—■■■■■■■■■■■■■■■■■■一·!!mM自¨_-__·。．．．-■”，，¨二⋯知图4—13MPDSR协议仿真的NAM动画截图第一组仿真实验的结果如图4一14、4．15和4-16：第二组仿真实验的结果如图4．17、4-18和4．19。图4-14不同连接数的分组投递率 武汉理工大学硕士学位论文图4．15不同连接数的平均端到端时延4．16不I司连接数的路由开销图4．14反映了DSR和MPDSR协议在节点移动速率为10m／s的情况下，它们平均分组投递率均随着节点间的连接数的增加而下降。在连接数只有5对的时候，它们的分组投递率在95％左右，而当连接数增加到30对时，DSR协议的分组投递率下降到58％左右，MPDSR的为73％左右。从整个过程来看，MPDSR协议的分组投递率始终比DSR的要高，这说明MPDSR的多径效果很明显。特别是当网络节点连接数较多、网络负载较重时，MPDSR的分组投递率比DSR的要高很多。‘从图4．15可以看出，MPDSR协议的平均端到端的时延比DSR要少一些，5232l9876543210l1l0 武汉理工大学硕士学位论文且随着网络连接数的增大两增加，最然总体上逞递增趋势，但MPDSR的优势还是明显一些。这主要是因为多径的传输，减少了数据在队列中的等待时间，从而降低了时延。从图4．16中可以看出，不同连接数下的路由控制开销的变化情况。随着网络连接数的增加，两协议都逞递增趋势，但是MPDSR协议的路由控制丌销比DSR的稍大一点，这是因为因为它要实现多径的寻找，必须转发更多的RREQ报文，使得路由控制开销增大。根据图4．16，MPDSR协议的路由控制开销比DSR协议的高出5％左右，路由开销的增加在可接受的范圈内，但还有改进的余地。图4．17表示的是在连接数为15对的50个节点的网络中，不同最大节点移动速度下，两协议的平均分组投递率的变化情况。MPDSR协议的平均分组投递率比DSR协议要高，虽然当连接数增大时，总体上两协议都逞递减趋势，但当节点的速度比较快的时候，两协议差距较大，特别是速度超过15m／s时。这是因为节点的高速移动，网络拓扑发生了快速的变化，这缩短了路由失效的时间，丽MPDSR协议采用多径，只有所有路径失效它才停止传输，重薪路由，所以它的路由失效相对要慢，分组投递率自然要比DSR的高。Speed4．17不同速率的分组投递率图4．18表明随着节点移动速度的加快，MPDSR协议和DSR协议的时延也相应增加。这说明，节点的快速移动对两协议的路由都有很大的影响，增加了重路融的概率。不过，MPDSR协议平均端到端的时延始终比DSR要少。53 武汉理工大学硕士学位论文主要是因为MPDSR采用多径同时传输，其传输速度比DSR要快，时延受到的影响也就比DSR相对要小。4．18不同速率的端到端的平均时延从图4．19可以看出，不同速率下的路由控制开销的变化情况，总体上，随着网络连接数的增加，两协议都逞递增趋势，虽然MPDSR协议的路由控制开销略高于DSR的，但是并没有很大差距。MPDSR由于要寻找和维护更多的路由信息，其路由开销自然比DSR稍微大一点，MPDSR协议的路由开销比DSR协议的平均高2％左右，比较理想。图4．19不同速率的路由开销通过上面两种情况的仿真实验，说明MPDSR协议除了在路由开销上比54屉弱与诣一筠_筠七圬。晒oo玑。玑。叭。叭。钆。队 武汉理工大学硕士学位论文DSR协议有一定的增加外，它的分组投递率和平均时延都比DSR的要小。从总的性能上来说，MPDSR协议有一定优势。这为多径路由研究打下了良好的基础。4．6本章小结本章首先深入的研究了AdHoc网络的多径路由协议，简要介绍了多路径的概念的特点，比较和分析了几种典型多路径路由协议；然后提出并实现了一种改进的多径路由协议MPDSR，分析和讨论了它的稳定性以及路径数目的确定，详细阐述了MPDSR协议的路由机制、路由维护和路由实现中的关键问题；最后进行了仿真实验。实验表明：MPDSR协议的性能优于DSR协议。下一章将在MPDSR协议的基础上添加相应的QoS参数，使之能提供一定的服务质量(QoS)保证。55 武汉理工大学硕十学位论文第5章一种新的QoS多径路由协议QMPDSR前面我们研究的路由协议主要关注于如何在AdHoc网络中寻找到达目的节点的路由，以及当路由失效时，协议如何保证重选路由等问题。随着网络的发展和用户需求的不断提高，一些业务不仅要求能够通信，同时要求网络能够在时延、带宽等方面提供保证，以保证这些特殊业务的开展，因此，各种QoS技术应运而生。本章在深入研究QoS路由的基础上提出了一种新的QoS多径路由协议QMPDSR，详细阐述了它的QoS保证和路由机制，最后进行了仿真分析。5．1QoS概念QoS定义了一个系统的非功能化特征，通常是指用户对通信系统提供的服务的满意程度。在计算机网络中，QoS的目标是获得更加确定的通信行为，以便能够更加安全可靠的保护网络承载的信息，并更加高效的使用网络资源。具体而言，QoS是指网络为用户提供的一组可以预测的服务参数，包括时延、时延抖动、带宽和分组丢失率等，也可以看成是用户和网络达成的需要双方遵守的协定附】。简单而言，QoS是指网络需要提供给应用实现正常功能所需的性能级别保证。网络所能提供的QoS能力将直接影响到它所支持和满足的业务。5．1．1QoS主要参数QoS要求通常是被量化为一些端到端的数据传输指标，如带宽(bandwidth—h)，端到端时延(end—to—enddelay)，分组丢失率(packetloss)，抖动(jitter)，吞吐量(Tllrougll)等，这些统称为QoS参数。下面给出这五个参数的具体概念。定义5．1带宽B：数据的传输速率，单位为比特／秒。对于多媒体文件来说，其传输所要求的平均带宽为：Bf=F毒R毒c其中，为单位时间内播放的帧数(帧／秒)，R为图像的分辨率，(5-1)C为压缩 武汉理工大学硕士学位论文编码的速率。定义5．2端到端时延丁：数据包从源端出发，到被目的端接收所经历的时间，单位为秒。r=∑(Z(，)+耳(J))+t唧(s，D)(5-2)』其中，，为选定路由包括的各节点，S为源节点，D为目的节点，乃为数据包的传输时延，乃为处理时延，昂rDp为信号在无线信道中的传播时延，它们进一步可以表示为：Z(，)=s曲／或(，)，(5—3)L(J)=瓦(，)+乃(，)(5-4)其中‰为数据包的大小(比特)，Ba(，)为节点，实际能够利用的有效带宽(比特／秒)，乃∽为数据包在节点，的处理时间(秒)，它又包括了在节点，在队列中的等待时间瓦(，)和真正的数据包被处理的时间乃(，)。对于多媒体文件来说，其传输要求的平均时延必须满足TTZ≤2T】=研Z>2T—z赫Ic≤2T】≈z匆／2T(5—21)相对于T，哳的值是很小的，所以路由选择失误的概论很低。因此，用双向时延的一半来估计端到端的时延是合理的。因此，当源节点收到来自目的节点的路由回复时，根据当前时间与其发送路由要求的时间算出乃，并与数据流允许的最大时延作比较，最终决定是否可以利用这条路由来传输数据流。在实际操作过程中，还可以对它进一步的优化。当RREQ包到达目的节点时，％枷已经超过了乃即Tdown>T时，本文认为该路由已经不满足时延了，所以我们可以直接丢弃该RREQ报文，这样减少了一定的路由开销，即：臣Trio．>或z>，不符合时延需求、。5．2．4QMPDSR协议路由寻找QMPDSR协议的路由寻找分为三个部分：路由发现、节点不相关路径选择和负载分配。路由发现时，路由请求报文(RREQ)并不携带将要传送的数据流的带宽和时延信息，而是尽力搜寻多条可用带宽高且时延小的路径j当目的节点收到RREQ后，将收集到的多条路径信息沿着时延最小的路径立即返 武汉理工大学硕士学位论文回给源节点。源节点根据目的节点反馈多路径信息表，启动路由选择机制，发现并资源预留最多三条节点不相关多路径。最后进行负载分配，使网络负载均衡。、1．路由发现路由发现时，路由请求报文(RREQ)并不携带将要传送的数据流的带宽和时延信息，而是尽力搜寻多条可用带宽高且时延小的路径，当目的节点收到RREQ后，将收集到的多条路径信息沿着时延最小的路径返回给源节点。当有数据需要传送时，源节点首先检查路由缓存中是否存在符合带宽、时延要求可行路由；若不存在，则向其邻节点广播RREQ报文。RREQ报文格式如下：{SourceAddr,Destination_Addr,Request_ID，Route__Record,Hops,Bandwidth,Delay，Bth，％)SourceAddr、DestinationAddr、Request、的作用与4．3．3_IDRouteRecord节相同。Bandwidth表示从源节点到当前节点路径上的最小可用带宽，Delay表示当前路径的累积时延；B价Dth是寻找路由的带宽和时延的门限值，它们可以防止路由请求信息的全网洪泛，找到一些质量很差的废路由。同4．3．3节，中间节点维护序列对列表，<，．AddrSourceAddrRequestAddr>序列用于惟一标识一个路由请求报文。中间节点在收到源节点的路由请求报文后，按照以下步骤处理报文：第一步判断路由请求报文的是否存在于本节点的序列对列表中。若不存在，则跳转到第二步执行；否则，表明此请求报文已经收到过，节点进一步判断新收到报文中的路由信息是否与已保存在路由记录队列表中记录相同。若相同，丢弃该路由请求报文，这样能有效的防止环路的形成；否则，节点获取可用带宽召一ilable和时延瓦“胱一，。再按下面的原则进行处理：(1)此请求报文是否超过转发最大次数TransMax。若超过，则丢弃路由请求报文；否则，跳转到(2)进行判断执行；(2)判断曰咖存在于本节点的序列队列表．ID后，将节点地址附在报文的“RouteRecord"字段，更新报文中相应信息后，向邻节点广播该路由请求，并转第五步；第五步将该请求报文中的路径信息保存在相应的缓存中，作为其他路由请求的冗余路由。当目的节点在收到第一个路由请求报文后的△d时间内，继续接受其它的请求报文，并保存相应的路由信息。△d时间以后，如果继续收到请求报文则不处理。这样，目的节点应记录了多条路径信息。2．节点不相关路径选择目的节点收到多条QoS路由信息记录后，启动路由回复机制。目的节点利用时延最小的路径向源节点回复多径记录，源节点收到从目的节点返回的RREP报文后，获得了多条QoS路由信息记录，构造有向图G<瑚胗。把带宽 武汉理T大学硕士学位论文作为第一选择标准，在图G中选择出主路径，在带宽相同的情况下选择时延小的路径。然后在G中删除这条路径的中间节点和它们的链路，构成新的图G’，再次进行选择，最多选出三条路径。具体过程同4．3．3节。这样选择出的QoS路由能确保它们的节点无关性，从而减少数据传输过程中的干扰，增强路由协议的健壮性。3．负载分配QMPDSR路由协议在路由发现时，严格控制了每条路由的跳数差距不能超过2，所以最终的多径之闻的时延差缀小。由此本文的负载分配是与路径的带宽成正比的。设第k条路径负载分配权重为溉，(g=-I，2，3，⋯，奶，则应满足：％∞BI(k=-I，2，3，⋯，加(5—23)其中最是第k条路径的可用带宽。令Bu=Bt+B2十⋯+玩(5-24)wk=B℃徊眭(g=-I，2，3，”·，№t5-25)则舷可满足Ii[5．23)式。因此，如果按《5．25)式，能达到负载均衡。通过仿真实验，对(5．25)式进行改进，得到负载分配算法如下：f嚣-1哌=minq嚣l埘)×R(5砭6)其中，掰是鼹取值的上限，防止鳜取值太大，否则会因一条路径上过量分配而使多径退化成单径，而起不到负载平衡的效果。R用来控制每条路径上的负载分配的粒度，慕越大，单条路径一次分到的负载越多。在多条路径上分配负载时，采用轮循调度算法。5．2．5路由维护只有当路由在使用的过程时才进行维护，没有数据传输时不进行维护。QMPDSR协议路由采用MPDSR协议的路由维护枕制。即褶邻节点闻通过数据链路层的消息证实机制，来检测路由中各相邻节点的可达性。当发现节点闻的传输故障，向上级节点发送RERR报文，收到RERR摄文的节点将该路由从本节点的路由缓冲区中删除。同时向源节点继续发送RERR报文，源节点收到RERR报文后删除相应的故障路径，把这条路径上的数据流分配到其67 武汉理工大学硕士学位论文他路径上继续传送，如果没有其他路径可用，则重新启动路由寻找机制。5．3仿真实验5．3．1仿真环境、参数配置仿真环境及参数配置愤况见表5。2。本文所统计的每个数据都是取5个随机场景文件进行仿真实验的平均值。表5-2彷囊环境及参数配置项目环境、参数配置攥作系统RedHat9．0仿真软件及版本NS2．29路由协议QoS—MSR和QMPDSR阏络拓扑节点数为30个和50个，随机分布连接数10对和30对场景500m×500m窥1000m×1000m节点移动模式节点随机移动，平均速率是10m／s和15m／s数据源CBR，发包率为200．0翻300．0，包大小为512bytesMAC协议IEEE802．1l天线类型OmniAntenna仿真时间100秒Two—RayGroundReflectionModel，载频是914无线电传撩摸型MHz，带宽为2M；协议性能分析的统计指标和4．5．2节相同。5．3．2仿囊结果分析仿真实验NAM动画截图如图5。3所示。本章仿真实验同4．5节仿真实验不同的主要地方是：根据多媒体流的特点，把数据源的发包率进行了大幅度的提高，目的是要测试QMPDSR协议的QoS性能。为了充分的考查QMPDSR协议的性能，本文进行了两组仿真实验。 武汉理下大学硕士学位论文第一组仿真实验中，场景大小是500m×500m：节点数为30个，随机分布；连接数为10对；节点随机移动，最大速率为10m／s；数据源是CBR，数据包的大小为512字节，发包率为2000；第二组仿真实验中，场景大小是1000mx1000m；节点数为50个，随机分布；连接数为30对；节点随机移动，最大速率为15m／s；数据源是CBR，数据包的大小为512字节，发包率为3000；vi：__一n7×图5-3OMPDSR协议仿真的NAM动画截图第一组仿真实验结果如下图5-4、5-5、5-6所示，分别表示分组平均投递率、平均端到端的时延、路由丌销。第二组仿真实验结果如下图5—7、5-8、5-9所示。从图5-4中可以看出，QMPDSR比QoS—MSR的分组投递率有了明显的提高。由此可见QMPDSR协议的数据包传输成功的概率比QoS．MSR的要高很多，这也表明QMPDSR更能适应处理媒体流数据，其服务质量要好得多。图5-5表明，QMPDSR的平均端到端的时延比QoS—MSR的小很多。这说明QMPDSR的多径传输与带宽和时延的控制结合得相对较好，它能找到一条 武汉理工大学硕士学位论文或几条合适的、满足要求的QoS路由，加快了数据包的传送；从而保障了传输流的QoS服务，减小了数据传输的时延。图5_430个节点分组平均投递率图5．530个节点平均端到端的时延图5-6中，QMPDSR协议的路由开销比QoS．MSR明显要小。这进一步的说明，QMPDSR能有效的控制路由请求报文的过度转发，在QoS寻径的过程中综合考虑了各路径的跳数差、带宽和时延限制。同时，QMPDSR的带宽分离原则也起了很大的作用，这样能有效了减少重路由和次数，从而降低了路由开销。70 武汉理工大学硕士学位论文图5-630个节点路由控制开销第二组仿真实验相对第一组来说，场景扩大了一倍；节点数也从原来的30个增加到50个，连接数从lO对增加到30对；数据包发送率从原来的200增加到300。仿真实验的目的是要比较和分析QMPDSR协议在网络规模扩大，节点移动更快情形下的QoS性能。仿真实验结果如下图5．7、5．8、5-9所示。从图5—7中可以看出，QMPDSR比QoS．MSR的分组投递率要高5％左右，但是在第一组仿真中QMPDSR比QoS．MSR的分组投递率要高15％左右，所以它们之间的差距缩小了很多。这主要是由于第一组仿真中30个节点中连接数只有10对，这有利于节点不相关路径的选择；第二组仿真实验里50个节点中有30对连接，所以节点间通信频繁，独立多径的选择范围小得多，从而导致分组投递率差距的缩小。图5．8表明，QMPDSR的平均端到端的时延比QoS．MSR的少一些。这说明QMPDSR能找到一条或几条QoS路由，加快了数据包的传送；从而保障了传输流的QoS服务，减小了数据传输的时延。但是相对第一组仿真实验来说，第二组中的两个协议的时延都有了较大的增加。这说明网络规模的扩大，导致有些通信链路的跳数增加，造成平均时延相应的增加。不过QMPDSR协议的优势还是很明显的。图5．9表明，QMPDSR协议的路由开销比QoS．MSR要小。这主要是因为QMPDSR能有效的控制路由请求报文的过度转发，在QoS寻径的过程中综合考虑了各路径的跳数差、带宽和时延限制，从而降低了路由开销。相对第一7l 武汉理工大学硕士学位论文组来说，它们之闻的差距不是很大，并且QMPDSR和QoS．MSR的路由开销都有了很大的增加，这也进一步说明，随着网络规模的扩大，协议的性能都有所下降。从以上两组仿真实验结果的比较和分析来看，QMPDSR的分组投递率、端到端的时延、路由开销均比QoS．MSR的要小。但是扩大网络规模后，不利于多径的选择，所以QMPDSR协议的优势相应的有所减小。总的来说，QMPDSR协议的QoS性能优于QoS．MSR。这进一步说明利用多径路由提供一定的服务质量保证是可行的。图5，750个节点分组平均投递率图5．850个节点平均端捌端的辩延 武汉理工大学硕士学位论文5．4本章小结图5．950个节点路由控制开销本章研究了QoS的概念及相关参数，重点介绍了本文提出的一种新的QoS多径路由协议QMPDSR。首先从QMPDSR协议的多径数学模型开始，分别对它的带宽的计算、时延的统计、路由机制、路由维护等几个方面进行了全面的阐述；然后进行两种不同网络规模的仿真实验，最后对仿真实验结果进行比较和分析；从分组投递率、平均时延、路由控制开销三个方面把QMPDSR和QoS．MSR进行了对比，结果表明：QMPDSR协议具有良好的QoS性能。73 武汉理工大学硕士学位论文第6章总结及展望本文主要论述了AdHoe网络的QoS路由协议和NS2仿真。AdHoc网络作为无线网络的一种特殊形式，具有其它网络不可替代的地位，对AdHoc网络中路由协议进行研究是加快AdHoc网络发展的关键，其中多径路由和基于QoS约束的路由协议的研究尤为重要，但这方面的研究工作目前开展还不久，很多问题有待解决。本文研究的主题是多径路由和QoS多径路由，它是当前研究的热点，具有很高的研究价值。该课题的研究将为AdHoc网络的大规模应用提供重要科学依据。6．1工作总结本文对AdHoc网络的路由协议进行了较深入的研究，详细阐述了AdHoc网络的多径路由机制和QoS路由协议；同时介绍了目前业界一直推崇的网络仿真软件NS2，并应用该软件于实际的研究工作中，使用它来对AdHoc网络的路由协议进行了实验性研究。本文所做的主要研究工作体现在以下几个方面：1．以AdHoc网络的单径路由协议为基础，研究分析了典型的路由协议的路由机制，特别是按需路由协议。对DSR、AODV、TORA的路由发现和维护进行了深入的讨论，最后比较、分析了这几种路由协议的性能，为提出一种改进的多径路由协议MPDSR奠定了良好的基础。2．熟练的掌握好NS2，是进行网络协议研究和开发的重要基础。本文对NS2作了较深入的研究和分析，介绍了NS2的工作原理、层次结构，特别重点介绍了无线网络模块。通过在NS2中添加一个本文新开发的一种多媒体数据流传输协议的实例，详细阐述了利用NS2进行仿真分析的过程。3．本文对AdHoc网络的多径路由作了深入的研究分析，提出了一种改进的多径路由协议MPDSR。首先对MPDSR协议的稳定性进行了理论分析；然后通过数学分析、数据比较确定了多径的最佳数目；最后详细阐述了MPDSR协议的路由发现、路由选择、路由维护等关键性的问题。为了从多角度来比较MPDSR协议的性能，本文采用了两组仿真实验。一组是相同的节点移动速度，不同的连接数；另一组是相同的连接数，不同的节点移动速度。这两组实验74 武汉理工大学硕士学位论文的结果均表明MPDSR协议有比较好的性能。4．QoS保证是在AdHoc网络上开展多媒体应用的关键。本文充分利用MPDSR协议的多径优势，提出了一种新的多径QoS路由协议QMPDSR。该协议主要根据带宽和时延这两种参数来选择多条QoS路由。QMPDSR协议的一个显著特点是，路由寻找时暂时不考虑是否存在某一条或某几条路径满足QoS要求，而是尽量找到多的QoS路由。目的节点最后优化组合，把QoS、Jk务直接发送或分解后再发送，这样就充分利用了网络资源，最大可能的提供QoS保证。为了达到仿真的目的，实验时模仿了多媒体业务的流量进行数据传输，结果表明QMPDSR协议的性能优良，其分组投递率高，时延低，路由开销的增加也不明显。6．2未来工作的展望本文虽然作了大量的研究工作，但由于路由协议的复杂性，有些问题还有待于更深入的研究。主要体现在以下几个方面：1．MPDSR协议在多路径选择时需要多次利用Dijkstra算法在图G中选择最短路径，这对于节点数很多的情况来说计算开销会明显增大。关于这方面的优化工作是今后研究的一个重点，用邻接表来代替多路径图G进行最短路径的选择是值得进一步研究的一个方向。2．QMPDSR协议的QoS参数仅仅考虑了带宽和时延，对于其他的参数还没有考虑到新协议中。如果要加入其他QoS参数，是按照一定的权重综合考虑QoS路由还是对几种参数进行排序，确定优先级，再以优先级作为QoS路由的衡量标准?关于这两种情况的讨论也很多，但对于多径QoS路由的研究还很少。如何更好的使QMPDSR协议满足多QoS约束也是值得进一步研究的一个问题。3．本文只重点考虑了多径路由搜寻和选择等方面，对于如何更有效的进行负载平衡，以减少因多径而产生的乱序问题考虑得较少。这个方面的研究也需进一步展开，它将有利于推动AdHoc网络多径QoS路由更深入的研究和实际应用。75 武汉理工大学硕士学位论文【l】【2】【3】[4】【5】【6】【7】【8】【9】【10】【l1】[12】【13】【14】【15】【16】参考文献李腊元，李春林．计算机网络技术．北京：国防1：业出版社，2004：28～38．LiLayuan，LiChunlin．AQoS—guaranteedmulticastrouting．ComputerCommunication，Elsevier,2004，27(1)：59-69．李腊元，李春林．多QoS约束的多播路由协议．软件学报，2004，15(2)：286～291．郑少仁，王海涛，赵志峰等．AdHoc网络技术．北京：人民邮电出版社，2005：64～91．马东冉，张科．AdHoc网络的体系结构分析．重庆科技学院学报(自然科学版)，2007，9(3)：63～66．KrauseWolfram，GlaucheInqmar,SollacherRudolf．Impactofnetworkstructureonthecapacityofwirelessmultihopadhoecommunication．PhysAStatMechAppl，Elsevier,2004，338(3-4)：633—658．CongzheZhang，MengChuZhou，MingYu．AdHocnetworkroutingandsecureity：Arevi—ew．InternationalJournalofCommunicationSystems，2007，20(8)：909～925．ElizabethM．Royer，TohCK．AreviewofcurrentroutingprotocolsforAdHoemobilewirelessnetworks．IEEEPersonalCommunicationsMagazine，l999，6(2)：46--55．余旭涛，毕光国等．AdHoe网络按需路由协议的改进．计算机学报，2004，27(6)：838～844．HirohitoTaniguchi，MichikoInoue，ToshimitsuMasuzawa．ClusteringalgorithmsinAdHoenetworks．ElectronicsandCommunicationsinJapan，2005，88(1)：51-59．王海涛．移动AdHoe网络的分簇算法及性能比较．北京邮电大学学报，2004，27(1)：93～97．LakshmiM．，SankaranarayananP．E．．PerformanceanalysisofthreeroutingprotocolsinwirelessmobileAdHocnetworks．InformationTechnologyJournal，2006，5(1)：114~120．刘洛琨，张远，许家栋．AODV与DSDV路由协议性能仿真与比较．计算机仿真，2006，23(2)：l18～120．WeiXiaohai，ChenGuoliang，WanYingyu．Optimizedprioritybasedenergyefficientrou-ringalgorithmformobileadhoenetworks．AdHocNetworks，2004，2(3)：231-239．RajuJyoti．Garcia-Luna—AcevesJ．J．．Comparisonofon-demandandtableddvenroutingforad．hocwirelessnetworks．In：Proe．ofIEEEInternationalConferenceonCommunica．tions，2000，3：1702～1706．PerkinsCharlesE．，RoyerElizabethM．，DasSamirR．．Performancecomparisonoftwoondemandroutingprotocolsforadhocnetworks．IEEEPersonalCommunications，2001，76 武汉理工大学硕士学位论文8(1)：16--28．【17】PerkinsC，Belding-RoyerE，DasS．AdHocon-demanddistancevector(AODV)routing．RequestforComment(RFC)：3561，2004．【18】JohnsonDB，MaltzDA，HuY-C．ThedynamicsourceroutingprotocolformobileAdHocnetworks(DSR)(workinprogress)．IETFMANETWorkingGroup，draft-ietf-manet-dsr-09．txt，2003．[19】AlilouMehdi，Dehghan．tMehdi．UpgradingperformanceofDSRroutingprotocolinmobileadhocnetworks．In：Proceedings—WEC’05：3rdWbrldEnformatikaConferenc-e．Istanbul：EnformatikaSociety2005．38～40．[20】杨锦亚，郭虹，胡捍英．自组网路由协议性能比较．微计算机信息，2006，22(24)：196--198．【2l】LiLayuan，LiChunlin．Selffault—toleranceofprotocols：Acasestudy．JournalofSystEng&Electronics，2000，l1(3)：28～34．【22】KummakasikitManoon，ThipchaksuratSakchai，VarakulsiripunthRuttikorn．Performanceimprovementofassociatevity-basedroutingprotocolformobileAdhocnetworks．In：2005FifthInternationalConference011Information，CommunicationsandSignalProee—ssing，2005：16--20．【23】王永胜，吴德伟，刘勇．基于NS2网络仿真研究．计算机仿真，2004，21(11)：257-259．【24】徐雷鸣，庞博，赵耀．NS与网络模拟．北京：人民邮电出版社，2003：57～88．【25】颜昕，李腊元．NS的仿真机制及协议扩展．武汉理工大学学报，2004，28(2)：182～185．【26】颜昕，李腊元．动态网络的仿真系统研制．武汉理工大学学报，2006，30(3)：405,-408．【27】ChenLixin．NS2basedperformancemeasurementofmobileadhocnetworksroutingprotocols．JournalofComputationalInformationSystems，2007，3(1)：109-115．【28】郑四海，李腊元．一种实时多媒体数据流传输算法的研究与在NS．2上的实现．武汉理工大学学报(交通科学与工程版)，2008，32(1)：47～50．【29】WuK．，HarmsJ．．PerformancestudyofamultipathroutingmethodforwirelessmobileAdHocnetworks．In：IEEEIntWorkshopModelAnalSimulComputTelecommunSystPr,2001：99-107．【30】WuZhengyu，SongHantao，JiangShaofcng．Areliablenode-disjointmultipathroutingalgorithminmobilead-hoenetworks．BeijingLigongDaxueXuebao，2007，23(3)：243～246．[3l】WajahatMateen，SaqibRaza，ZartashA．Adaptivemulti-pathon—demandroutinginmobileAdHocnetworks．In：Proceedings·EighthIEEEInternationalSymposium011Obj-ect-OrientedReal-TimeDistributedComputing，ISORC2005，InstituteofElectricalandElectronicsEngineersComputerSociety，2005：237～244． 武汉理工大学硕士学位论文【32】【33】【34】[35】[36】【37】[38】【39】[40】【41】[42】【43】【44】【45】[46】LianfangZhang，ZenghuaZhao，YantaiShu．LoadbalancingofmultipathsourceroutinginAdHoenetworks．In：Proe．ofIEEEInternationalConferenceonCommunications，Ins-tituteofElectricalandElectronicsEngineersInc．，2002，5：3197-3201．FangJing，R．S．Bhuvaneswaran，YoshiakKatayama．On-demandmultipathroutingproto-colwithpreferentialpathselectionprobabilitiesforMANET．In：ProceedingsofInternat-ionalConferenceonAdvancedInformationNetworkingandApplications，AINA，Instit-uteofElectricalandElectronicsEngineersInc．2006：758-762．安辉耀，卢锡城．移动自主网络多路径路由技术研究进展．计算机工程与科学，2006，28(2)：4～9．WangLei，ZhangLianfang，ShuYantai．Multipathsourceroutinginwirelessadhocnetw-orks．In：Proc．ofCanadianConferenceonElectricalandComputerEngineering，InstituteofElectricalandElectronicsEngineersInc．，2000：497～483．LeeS．J，GerlaM．SplitmultipathroutingwithmaximallydisjointpathsinAdHoenetworks．InProc．ofIEEEInternationalConferenceonCommunications，Helsinki，2001：320l～3205．MateenWajahat，RazaSaqib，UzmiZartashA．．Adaptivemulti-pathon-demandroutinginmobileadhoenetworks．In：Proceedings—EighthIEEEInternationalSymposiumonObje—ctOrientedReal-TimeDistributedComputing，ISORC2005，InstituteofElectricalandElectronicsEngineersComputerSociety,2005：237-244．ValeraAlvin。SeahWinstonk．G,RaoS．V．．cooperativepacketcachingandshortestmulti-pathroutinginmobileadhoenetworks．In：Proceedings—IEEEINFOCOM，InstituteofElectricalandElectronicsEngineersInc．，2003：260-269．盛聚，谢式千，潘承毅．概率论与数理统计．北京：高等教育出版社，2001：7～69．朱伟．AdHoe网络独立多路径路由的研究与改进：【硕士学位论文】．济南：山东大学，2006．赵选民，徐伟，师义民等．数理统计．北京：科学出版社，2002：3～59．PhamPeterP．，PerreauSylvie．Performanceanalysisofshortestpathandmulti-pathrout-ingmechanicsm、析thloadbalance．In：ProceedingsofIEEEINFOCOM．InstituteofEle-ctricalandElectronicsEngineersInc．，2003：251-259．孙宝林，李腊元．AdHoe网络QoS多播路由协议．计算机学报，2004，27(10)：1402-1407．肖小玲，李腊元，张翔．AdHoc网络00S路由协议研究，计算机工程与应用，2006．01．ZhangBaoxian，MouftahHusseinT．．QoSroutingforwirelessadhoenetworks：problems，algorithms，andprotocols．IEEECommunicationsMagazine，2005，43(10)：110-117LiLayuan，LiChunlin．AhierarchicalQoSmulticastroutingprotocolformobileAd—Hoc78 武汉理工大学硕十学位论文networks．ChineseJournalofElectronics．2006，15(4)：573-577．【47】MammeriZoubir．Frameworkforparametermappingtoprovideend—to．endQoSguar-anteesinIntServ／DiffServarchitectures．ComputerCommunications，2005，28(9)：1074～1092．【48】ShanshanChen，KasslerAndreasJ．．ExtendingSWANtoprovideQoSforMANETscon-nectedtotheinternet．In：Proceedingsof2ndInternationalSymposiumonWirelessCom—municationsSystems，InstituteofElectricalandElectronicsEngineersComputerSoeie·ty，2005：503—507．【49】陈年生．无线移动自组织网络QoS路由协议的研究：【博士学位论文】．武汉：武汉理工大学计算机科学与技术学院．2007．【50】李腊元，李春林动态QoS多播路由协议．电子学报，2003，31(9)：1345—1350．【5l】陈林星，曾曦，曹毅．AdHoe网络．北京，电子工业出版社，2006：517～536．【52】TangShengsheng，LiWei．QoSprovisioningandqueuemanagementinmobileadhoenetworks．In：Proc．ofIEEEWirelessCommunicationsandNetworkingConference，WC—NC2006，InstituteofElectricalandElectronicsEngineersInc．，2006：400-405．[53】LeiChen，WendiB．Heinzelman．QoS-awareroutingbasedonbandwidthestimationformobileAdHoenetworks．JournalonSelectedAreasinCommunications，2005，23(3)：561-572【54】金堂．移动AdHoc网络QoS路由协议及NS2仿真研究：【硕士学位论文】．武汉：武汉理工大学计算机科学与技术学院．2007．【55】WuHuayi，JiaXiaohua．QoSmulticastroutingbyusingmultiplepaths／treesinwirelessadhoenetworks．AdHoeNetworks，2007，5(5)：600---612． 武汉理工大学硕士学位论文致谢三年紧张而充实的研究生活即将结束，我顺利地完成了课程学习、项目验收、毕业论文，为研究生的生活画上了一个圆满的句号。这一切与老师们的悉心指导和同学们的热心帮助是分不开的，在此，一并表示我诚挚的谢意。感谢我的导师李腊元教授三年来的悉心指导。李老师严谨的治学态度、精益求精的工作作风让我受益匪浅，终身难忘。李老师在学术上的高深造诣、为人师表的风范和宽以待人的高尚品德，永远是我学习、生活和工作的榜样。在此，特向李老师致以最诚挚的敬意和最衷心的感谢。感谢冯美来、高庆锋、王跃峰、何昆鹏、王博、郑辉、许重球、赵新伟、徐鹏、冯振新、燕立杰～郭琳、袁俊春、蔡英华几位同学的帮助和支持，在与他们一起学习和讨论问题中，我学到了很多知识，让我受益匪浅。最后要感谢我的父母和妻子对我不断的鞭策和无私的奉献。本文得到了国家自然科学基金项目(批准号：60672137，60773411)，教育部博士点基金项目(批准号：20060497105)和湖北省科技攻关项目(批准号：2007AAl01C63)的资助，谨此表示感谢。郑四海2008年4月8日于武汉理工大学 武汉理工大学硕士学位论文攻读硕士学位期间发表的论文和参加科研项目情况攻读硕士期间发表论文情况【l】‘一种实时多媒体数据流传输算法的研究与在NS一2上的实现．武汉理工大学学报(交通科学与工程版)，2008，32(1)．EI收录．【2rAdHoc网络QoS多径路由协议研究。武汉理工大学学报(交通科学与工程版)，2008，32(3)EI收录．【3】．AnAdmissionControlAlgorithmforAdHoeNetworks．InternationalSymposiumonDistributedComputingandApplicationstoBusiness，EngineeringandScience(DCABES)，2007：239-243．ISTP收录．【4】多径路由协议MPDSR的研究．中国科技论文在线(http：／／www．paper．edu．cn)．【5】一种AdHoe网络QoS路由算法研究．中国科技论文在线(http：／／www．paper．edu．en)．注：幸获武汉理工大学三人检索学术论文收录奖．攻读硕士期间参加科研项目情况【l】国家自然科学基金项目【2】国家自然科学基金项目[3】教育部博士点基金项目【4】湖北省科技攻关项目(批准号：60672137)60773411)20060497105)2007AAl01C63)攻读硕士期间申请发明专利情况【l】专利《网格资源用户与提供者共同优化的多QoS资源调度方法》专利受理号：2007l0053023．9【2】专利《一种AdHoc网络中实现优化能量消耗的方法》专利受理号：200710053022．4【3】专利《一种基于市场经济下商品价值规律模型考虑网格任务重要性和时间紧迫性网格任务调度方法》专利受理号：200810046707．081