基于机会网络的qos路由协议的研究

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

分类号卫222：QUDC论文题目密级编号10126-31109010研究生：玉匾蛙指导教师：墨堂拯副塾援．一专业：让篡担科堂皇撞苤研究方向：让篡担圈络所在学院：让箕担堂陵2014年4月21日 原创性声明本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得由筮直太堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：垂垂盐遗指导教师签名：日期：——日期：在学期间研究成果使用承诺书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和导师的知识产权，作者在学期间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意；若用于发表论文。版权单位必须署名为内蒙古大学方可投稿或公开发表。学位论文作者签名：垂函盘日期：指导教师签名：．二缈日期： 内蒙古大学硕士学位论文基于机会网络的QoS路由协议的研究摘要近年来，随着大量低成本、具备短距离无线通信能力设备的出现，推动了机会网络的迅速发展。机会网络类似于MANET网络，节点随机移动，使得链路频繁中断，导致网络拓扑动态变化，因此很难建立一条端到端的完整路径。在MANET网络中，为了提高路径稳定性，多路径路由已经被广泛应用。但是，目前在机会网络中没有使用多路径路由传输消息，因此在满足QoS约束条件下使用多路径路由提高路径稳定性引起了学者们的广泛重视。基于以上原因，结合MANET网络中相应的多路径路由协议，并根据机会网络的特性，本文提出了两个在满足QoS约束条件下的多路径路由协议：基于可靠节点的多路径路由协议(ReliabilityNodebasedMultipathRoutingprotocol，RNMR)和基于备用路径的路由协议(BackupPathQoSRoutingprotocol，BPQR)。为了验证RNMR和BPQR的性能，通过数学推导得到了这两个路由协议的路径寿命的累积分布函数，并通过进一步计算得到路径过期时间的期望，来判定路径的稳定性。本文通过对这两个路由协议的性能进行理论分析和验证，结果表明在主路径长度不同的情况下，它们都具有较长的路径寿命，使得路径的稳定性得到了提高，同时降低了端到端的丢包率，从而保证了网络的QoS。本文对多路径QoS路由协议的研究，为进一步在机会网络中选取稳定的路径以及提高网络的QoS打下了坚实的基础。关键词：机会网络：多路径；稳定性；QoS：路由协议 基于机会网络的QoS路由协议的研究THESTUDYOFQOSROUTINGPROTOCOLBASEDONOPPORTUNISTICNETWORKSABSTRACTInrecentyears，alargenumberoflow—cost，short—rangew疵Msscommunicationdevicesappeared,whichpromotedtherapiddevelopmentofopportunisticnetworks．Theopporttmisticnetworksaresimilartomobileadhoenetworks．NodesmoverandomlySOthatlinksfrequentlyareinterruptedwhichresultsinconstantlychangeofnetworktopology．Thus，itisdifficulttoestablishanend—to—endcompletepath．InMANETs．multipathroutingprotocolshavebeenwidelyusedtoimprovethepathstability,butthemultipathroutingprotocolsinopportunisticnetworkshavenotvirtuallybeentakenapplicationintoconsideration．Therefore，weUSemultipathroutingprotocolsandmatchconditionofQoSconstraintstoimprovestability．Thisresearchattractsextensiveattentionfromscholars．CombinedthecorrespondingmultipathroutingprotocolsinMANETswiththecharacteristicofopportunisticnetworks，thethesisproposestwokindsofQoSroutingprotocols：reliabilitynodebasedmultipathrouting(RNMR)protocolandbackuppathQoSrouting(BPQR)protoc01．Inordertovalidtheperformanceofthem，也ethesisusesmathematicalmethodtoachieveCumulativeDistributionFunction(CDF)，whichdescribesthepathlifetimeofRNMRprotocolandBPQRprotoc01．Throughfurthercalculationfortheexpectancyofthepathlifetime，wecanjudgethestabilityofthepath．Moreover,throughthetheoreticalanalysisandperformancevalidationforthetwoprotocols，theresultsshowedthat，undertheconditionofvariouslengthsoftheprimarypath,theirpathlifetimealeallimproved；thestabilityofthepathisenhanced；andpacketlossratefromsourcetodestinationisreduced．Thus．theQoSofthenetworkisguaranteedatthesametime．ThestudyofmultipathQoSroutingprotocolsinthethesislaidasolidfoundationforboththeselectionofstablepathandimprovementtoQoSintheopporttmisticnetworks．KEYWORDS：opportunisticnetworks；mulfipath；reliability；qos；routingprotocolⅡ 内蒙古大学硕士学位论文目录摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．IABSTRACT⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．II第一章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．1引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．2研究背景及意义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．21．3国内外研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯41．4本文的主要研究内容⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯61．5本论文的结构安排⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯7第二章MANET网络路由协议及QoS⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．82．1路由协议的分类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯82．1．1主动式路由协议⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯82．1．2按需路由协议⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．82．2多路径路由协议⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯92．2．1多路径路由的不相交性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯102．2．2多路径路由的优点⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯102．2．3多路径路由的组成⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯102．2．4多路径路由的分类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯112．3MANET网络的Qos⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯142．3．1服务质量(Qos)概述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．152．3．2在MANET网络中提供Qos所面临的问题与挑战⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．152．3．3MANET网络中QoS解决方法概述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．162．4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．17第三章一种基于可靠节点的多路径QoS路由协议⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯183．1RNMR路由协议的提出⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯18m 基于机会网络的QoS路由协议的研究3．2RNMR路由协议的设计⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．193．2．1研究场景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯193．2．2可靠节点的选取⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯203．2．3节点的转发策略⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯233．2．4RNMR路由协议的描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯263．3对m瓜路由协议的验证和性能分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．283．4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．30第四章一种基于备用路径的QoS路由协议⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯314．1BPQR路由协议的提出⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯3l4．1．1不相交路径的稳定性分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯314．1．2BPQR路由协议的提出原因⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．334．2路由协议的设计⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．344．2．1研究场景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯344．2．2稳定节点的选取⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯354．2．3节点的路径维持⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯374．3BPQR路由协议的验证和性能分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯394．3．1BPQR路由协议的路径寿命的累积分布函数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯394．3．2BPQR路由协议的性能分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．404．3．3BPQR路由协议和RNMR路由协议的性能分析与比较⋯⋯⋯⋯⋯⋯⋯⋯⋯。424．4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯～43第五章总结与展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．44致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．45参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．46攻读硕士期间发表的学术论文⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．50IV 内蒙古大学硕士学位论文图目录图1．1挑战性网络的发展⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯4图1．2机会网络中节点的通信过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯6图3．1两个面积相同的研究区域中节点的通信过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．20图3．2可靠节点的选取过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．21图3．3两个相邻节点移动前后的位置关系⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．23图3-4不同长度的主路径的期望寿命⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．29图4-1链路不相交路径(口)和节点不相交路径(6)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯31图4．2一个稳定节点的选取过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．35图4．3节点i移动后的新的位置坐标⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯38图4．4不同长度的主路径的期望寿命⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．41图4．5BPQR和RNMR路由协议的路径寿命的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯42V 基于机会网络的QoS路由协议的研究表目录表3．1公式(3．1)中相关参数说明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．表3．2RNMR，GBR．WB和BSR路由协议相关参数的设定⋯⋯⋯⋯⋯．表4．1公式(4．11)中相关参数的说明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯表4-2BPQR和BSR路由协议相关参数的设定⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．VI丝凹弘叭 内蒙古大学硕士学位论文1．1引言第一章绪论目前，随着大量具备无线通信的便携设备的推广，使得无线自组织网络得到了迅猛的发展。无线自组织网络被应用于车载网络，该网络可以检测路况信息以及交通事故预警等情况(1】；实现数据共享或协作访问互联网，使用各种配备蓝牙或Wi．Fi接口的便携式电子设备进行自组网‘2】；采集动物迁徙的数据，使得装有传感器的动物组成移动传感器网络13】等。但是，在许多实际应用领域中，节点随机移动以及网络节点密度稀疏等原因可能会导致形成的网络出现不连通的现象。传统的移动自组织网络(MobileAdHoeNetwork，MANET)的传输模式要求源节点和目的节点之间至少存在一条完整的路径，因此该网络无法在许多实际应用环境中运行[4，141。然而，在机会网络中，不要求网络是全连通的，而是利用节点移动所带来的相遇机会进行自组织网络来实现网络通信‘51。机会网络利用“存储一携带一转发”[61的路由模式进行逐跳转发消息来实现节点间的相互通信，这是一种完全不同于传统网络通信模式的新兴组网方式，因此，引起了研究界越来越多的广泛关注。在机会网络中，由于终端设备的无线覆盖范围的有限性，如果两个用户终端不在彼此的通信范围内时，因此用户之间就无法直接进行相互通信，那么用户终端之间的所有消息转发就必须通过中间节点进行分组转发，进行消息传输，其中的每个中间节点都可以看成是一个路由器，使其能够发现和维持到达其它节点的路由。尽管节点移动，导致网络拓扑结构动态改变，使得网络连接不断地变化，但是路由协议必须能够适应网络的不断变化并且能够维持链路继续路由。因此，在军事方面、紧急救援方面以及其它战术应用等方面[71，机会网络是非常适用于这些方面的。在这样的动态无线网络中，设计有效的路由协议找到稳定的路径来保证消息的成功传输是一个主要的挑战。在MANET网络中，为了提高路径的寿命，提出了一些多路径路由协议，并且在多路径路由协议中考虑网络的QoS【8】也有一定的相关研究，从而使得有限资源可以高效合理的利用。但是，在机会网络中没有使用多路径路由进行消息传输来提高路径的稳定性以及改善网络的QoS。因此，为了使得有限资源可以得到高效合理的利用，本文提出的基于可靠节点的多路径路由协议(ReliabilityNodebasedMultipathRoutingprotocol，RNMR)和基于备用路径的路由协议(BackupPathQoSRoutingprotocol，BPQR)是在满足QoS约束条件 基于机会网络的QoS路由协议的研宄下使用多路径路由进行消息传输，从而，大幅度地提高了路径的寿命，使得通信路径具有更高的稳定性。随着无线网络通信技术的不断发展，在许多领域中使用机会网络引起了越来越多领域的广泛重视和关注。在机会网络中通信源节点和目的节点之间进行通信时，并没有考虑使用多路径路由协议进行数据传输，而大部分使用的路由协议是传染病‘91、SprayandWait／101等路由协议。尽管使用这些路由协议能够将消息最终传输到目的节点，但是会造成较大的路由开销、网络负载，延迟以及丢包率等问题，通过提高网络中的QoS来改善传输消息网络中存在的这些缺点，从而使得有限资源能够高效合理的利用，因此，多路径路由协议和QoS路由协议是目前改善机会网络中通信网络的QoS的研究重点。基于以上原因，本文结合国内外多路径路由协议‘n1和QoS路由协议[12】的最新研究，提出了两个新的、实用的满足QoS约束条件下的多路径路由协议，分别被称为基于可靠节点的多路径QoS路由协议(RNMR)和基于备用路径的QoS路由协议(BPQR)。RNMR路由协议改进了移动自组网中的链路不相交的多路径，并且由3条路径组成，这3条路径中公共的中间节点被设置为可靠节点，通过这些可靠节点将整条路径分割成几段子路径，每段子路径由节点不相交的路径组成，来延长路径的寿命，从而提高路径的稳定性。本文通过对RNMR路由协的性能进行理论分析和验证，结果表明了该路由协议具有较好的性能表现。BPQR路由协议是由一条主路径和一条备用路径构成的，并通过数学公式推导得到了该路由协议的路径寿命的累积分布函数，进而求其路径寿命的期望来分析和验证该路由协议的性能，提高路径的稳定性，降低端到端的丢包率，因此使得网络的QoS得到了保障。此外，通过对这两个路由协议的性能比较，为进一步在研究场景中选取合适的路由协议，做出了相应的分析和判定。1．2研究背景及意义目前，随着智能设备的推广和普及，使人们走入了信息化时代，并且人们对智能设备的需求也越来越大，从而导致各种具备短距离的无线通信能力的智能设备得到了广泛推广，推动了机会网络(OpportunisticNetworks)应用到各个领域的快速发展。例如，野生动物追踪[31、利用手持设各进行组网实现数据交换与共享口1、车载网纠11以及偏远地区网络传输[”】等。同时，由于无线网络通信技术的不断发展以及用户对通信质量的要求越来越高，因此如何为机会网络提供服务质量(QualityofService，QoS)保障是至关重要的问题，而在整个机会网络中利用路由协议来改善QoS保障体系具有相当重要的作用。路由协议的作用是在满足QoS 塑鍪直丕堂堡主兰垡堡壅约束条件下如何选取最优路径，来提高路径的稳定性，从而使得网络中有效的资源可以高效合理的利用。机会网络类似于移动自组织网络(MobileAdHocNetwork，MANET)[14】。在MANET网络中传输数据之前，需要预先在通信期间使用AdHoc按需平面距离矢量路由协议(AdhocOn-DemandDistanceVectorRouting，AODV)[15】或动态源路由协议(DynamicSourceRouting，DSR)[16】等进行路由发现，对其数据分组并根据路由表确定的下一跳节点依次进行转发，最终将数据传送到目的节点。在这种工作模式并以网络全连通为前提的条件下进行消息传输，即网络中至少有一条完整的端到端的路径用于消息传输。但是，在MANET网络中可能会有网络不连通的时刻出现，此时，通信源节点和目的节点可能将位于不同的连通域，从而导致MANET网络的路由协议无法发现到达目的节点的路由，使得路径发现最终失败，因此不能找到一条端到端的连通路径继续传输消息。当源节点和目的节点之间没有一条完整的连通路径时，节点通过移动进入到彼此的通信范围内进行数据交换与共享，而机会网络(OpportunisticNetworks)[5,6,271就是利用这种方式传输消息的，使得机会网络更加适用于实际的自组网需求，并且通过利用这种节点对之间逐跳转发的方式，将消息从通信源节点最终传输到目的节点。机会网络中节点之间相互通信的这种传输模式对于实现未来普适计算(UbiquitousComputing)t17】具有重大的影响，因而近年来引起了科研人员的密切关注。在MANET网络中，研究人员提出了许多不同的多路径路由进行路径选择，并且使用多路径路由来寻找更加稳定的路径，提高路径的稳定性，使得消息成功传输的概率也得到提高，减少了路由开销，平衡了网络负载。因此，在MANET网络中使用多路径路由协议进行路径的发现和维持起到了很好的作用。由于机会网络的特性类似与MANET网络的特性，不需要固定的基础设施，同时网络拓扑动态变化，使得链路频繁中断，因此在端到端之间建立一条相对稳定的路径具有一定的挑战性。在机会网络中，为了提高路径的稳定性，已有的路由协议使用的是基于洪泛[9】、SprayandWaittlo]或者是最短路径㈣等路由协议，没有考虑使用多路径路由进行消息传输，并且也没有考虑网络体系中QoS的保障，因此如何在机会网络中选取最优、最稳定的路径，来提高路径的稳定性以及改善网络的QoS，使得有限的资源能够得到高效合理的利用是机会网络研究的热点。在机会网络中满足QoS约束条件下使用多路径路由提高路径的稳定性以及改善网络的QoS。因此，本文提出了两个多路径路QoS由协议，其分别是：RNMR路由协议和BPQR路由协议，并对这两个路由协议的性能进行理论分析和验证。． 基于机会网络的Qos路由协议的研究目前，机会网络在国外已经取得了一定的成果，并获得了许多政府以及公司的赞助。机会网络是一种以无线移动设备为主的新式的网络结构，欧美国家目前为了解决这种新式的网络结构，提出了很多的新型方案并适用于新一代网络。此外，瑞士国家研究院(ETHZurich)进行组织研究的自组网络结构项目(ANAProject)091、ImrichChlamtac研发的生物启发网络和服务项目(BIONETS)【2们以及剑桥大学的Haggle项目【2l】都是为了创建一个跨网络层的机会网络结构。在意大利的比萨信息技术研究院(11T)举行的两届MobiOpp会议是首个专门研讨机会网络的会议。而且国内目前对于机会网络的研究也逐渐地进行发展，并且由孙利民2009年在《软件学报》发表的第一篇机会网络综述论文开始起步的，同时，国家自然科学基金也开始对机会网络的基础理论以及实践应用的相关研究给予了高度重视和经费的资助，推动了国内对机会网络的相关研究。随着人们对社会信息化时代的不断推进，促使了社会对网络技术的发展不断地提出了新的要求。这些新的要求使得基于因特网的网络应用功能更加丰富以及人性化，并且超出了传统互联网的网络结构的应用场景。为了满足网络环境中的各种新要求，从20世纪90年代起，学术界先后提出了传感器网络(SensorNetworks，SNs)吲、无线传感器网络(WirelessSensorNetworks，WSNs)[23】、移动无线传感器网络(MobileWirelessSensorNetworks，MWSNs)洲、移动自组织网络(MobileAdHocNetworks，MANETs)B4]、无线网格网络(WirelessMeshNetworks，WMNs)[25】、延迟容忍网络(DelayTolerantNetworks，DTNs)【2叼以及机会网络(OpportunisticNetworks)匹7】等一系列的具有挑战性网络(如图1．1)的概念与技术，这些技术在连接性能、网络环境、节点特性、组网方式、数据传输的模式等方面与传统的因特网存在着本质上的区别，并且为物联网时代的来临奠定了理论和实践的基础。一_一一__圈图1-1挑战性网络的发展Fig．1-1Thedevelopmentofthechallengednetworks4 内蒙古大学硕士学位论文MANET网络是目前较为流行的一种自行组建网络的方式。MANET网络是一种没有固定基础设施的多跳移动的无线网络，并由若干移动节点组建成的自组织无线网络，使得动态网络拓扑不断变化，并且该网络也没有固定的基站或路由器来协助工作，因此，每个节点都具有两个功能：终端主机和路由器。此外，节点之间是通过对等方式进行消息传输的。近年来，随着手持设备、车载设备、无线通信设备的逐渐增加，使得MANET网络在无线通信网络中被广泛地应用。同时，由于物联网大战略方向的引导和推进，使得这些通信设备出现在人们的生活中更具有人性化。MANET网络目前在路由协议以及QoS等方面都有一定的研究。机会网络是一种新型的MANET网络，主要来源于目前的MANET网络和WSN网络的大量研究与应用，是继这两种网络之后在无线网络通信领域中兴起的又一个新兴研究热点。并且机会网络继承了MANET网络的很多特点，同时它的大部分概念来源于DTN[261，是广义上的DTN。机会网络是一种特殊的自组织网络，源节点和目的节点之间没有一条完整的路径，通过节点移动带来的相遇机会，使得数据逐跳进行转发，并最终将数据传输到目的节点[5】。在传统的MANET网络中，必须以通信源节点和目的节点之间至少有一条完整的路径为前提进行路由，而机会网络则不需要设定这一前提。在机会网络中，相遇是指节点之间发生的一次联系。当节点进行连接时，节点之间进行通信和数据共享，但是，随着节点的自由移动，导致节点断开连接，造成连接链路中断，使得节点间的通信不能继续，而机会网络中的节点就是利用这种相遇方式来建立路径的，将消息最终传输到目的节点。机会网络的概念有一部分是来源于早期的DTNl26】研究。DTN的概念最初是容迟网络研究组(DelayTolerantNetworkResearchGroup，DTNRG)在星际网络通信项目(InterplanetaryNetwork，IPN)[28】中提出来的，其主要支持在间歇性连通、延迟大以及错误率高的情况下，实现数据转发，用于解决由于不连通的异构网络之间的通信问题。因此，机会网络可以看作是具有一般DTN特性的新型MANET网络。机会网络的消息转发模式，如图1．2所示【5]。 基于机会网络的QoS路由协议的研究一H岭甲麓{争藤●爨l|@|j甏鬈鬻萝图1-2机会网络中节点的通信过程Fig．1-2Theprocessofcommunicafionbetweennodesinopportunisticnetworks在机会网络中，由于节点随机自由地移动，并且节点的通信范围具有局限性，同时在所构建的区域中没有固定的网络拓扑结构，导致节点连接频繁地中断，通过利用容迟网络中的“存储．转发”模式转发消息，组建成了没有固定基础设施的无线网络。基于以上原因，传统的MANET网络中的路由策略并不适用于机会网络中。然而，在机会网络中节点的移动比较频繁，导致网络拓扑结构不断地变化，并且只能利用先前获得的路由表来寻找下一条链路，这样会对路由发现工作带来不利的影响，此外，节点之间短暂的相遇不能认为和传统网络中的路由算法一样，即假设网络中路径是全连通的。因此，在机会网络中需要尽可能地利用节点移动带来的相遇机会进行数据交换和共享，来提高机会网络路由协议的性能。因此，本文提出了两个在满足QoS约束条件下的多路径QoS路由协议，其分别是：RNMR路由协议和BPQR路由协议，这两个路由协议通过延长路径的寿命来提高路径的稳定性，进而降低端到端的丢包率，使得网络的QoS得到了保障，因此，在机会网络中有限的资源可以得到有效合理的利用。为了将MANET网络中的多路径路由协议更好地应用于机会网络中，并且在机会网络中满足QoS的约束条件下如何改进已有的多路径路由协议，以及考虑如何获得更加稳定的路径，使得消息能够尽可能的从通信源节点传输到目的节点，是本文主要研究的内容。为了在机会网络中提出可以提高路径稳定性的多路径路由协议(RNMR路由协议和BPQR路由协议)，本文对MANET网络中已有的多路径路由协议进行了分析。在机会网络中，为了提高路径的稳定性，并且使得路径的控制开销较低，多路径使用链路不相交的多路径组 堕鐾查查兰婴圭堂垡丝茎成并进行消息传输，路径中公共的中间节点利用可靠节点代替，来延长路径的寿命。这些可靠节点将路径分割成几段节点不相交的子路径，使得整个路径便于维护并且相互独立，从而缩短了路径发现的时间，提高了路径的稳定性，降低了端到端的丢包率，使得网络整体的QoS得到了保障。在机会网络中满足QoS约束条件下使用多路径路由提高路径的稳定性以及改善网络的QoS。因此，本文提出了两个多路径路QoS由协议，其分别是：RNMR路由协议和BPQR路由协议，并对这两个路由协议的性能进行理论分析和验证。将RNMR路由协议与MANET网络中已有的GBR-WBE2明路由协议和BSRC30】路由协议的相关QoS参数进行比较，用于说明NMR路由协议的性能更好。此外，BPQR路由协议与MANET网络中已有的BSR【21】路由协议的性能进行比较，来说明该路由协议也具有更好的性能表现，并且根据研究场景的不同，选取不同的路由协议传输消息，对本文提出的这两个路由协议的性能通过理论分析和比较，来判定在不同场景中选取哪个路由协议使得整体路径的稳定性更好，同时有限的资源可以被高效的利用，从而更好的保证了网络的QoS。将MANET网络中已有的多路径路由协议通过改进运用到机会网络中进行路由，本文改进了MANET网络中原有的多路径路由协议，设计了两个新的路由协议，在使用多路径路由的同时也考虑了网络的QoS。通过本文的研究，将MANET网络中的多路径路由的想法以及QoS引入到了机会网络中，为建立稳定的路径奠定了坚实的基础。1．5本论文的结构安排本文共分为五章，具体安排如下：第一章，主要介绍了机会网络的研究背景与意义、机会网络的国内外研究现状及本文的主要研究内容。第二章，介绍了MANET网络路由协议及QoS。第三章，详细阐述了RNMR路由协议以及对其性能进行分析和验证。第四章，详细阐述了BPQR路由协议以及对其性能进行分析和验证。第五章，总结了本文的研究内容以及对今后工作进行的展望。 基于机会网络的QoS路由协议的研究第二章MANET网络路由协议及00S在MANET网络中，已经有许多路由协议被提出并被广泛应用到各种应用场景中，由于节点随机移动，导致网络拓扑动态变化，使得链路频繁中断，为此多路径路由被广泛运用到MANET网络中。为了使网络中有限资源能够得到高效合理的利用，考虑QoS是十分必要的。本小节从路由协议的分类，多路径路由协议以及QoS三方面对MANET网络进行简要的概述。2．1路由协议的分类在MANET网络中，已经有许多路由协议被提出，大致可以被分为两大类‘31】：主动式路由协议和按需路由协议。主动式路由协议出现在MANET网络路由协议的研究初期，通过改进有线网络的路由协议并将其运用到MANET网络环境中，又被称为表驱动路由协议。该路由协议的特点是网络中的每个节点不管是否进行通信，都会主动进行路由发现，同时对所有已知目的节点的路由表进行维护，周期地更新路由信息。常见的表驱动路由协议有DSDV_【321、OLSR[331、WRP[34】和STAR[353等。2．1．2按需路由协议按需路由协议只在有通信需求时，即在有报文转发时才按需进行路由发现寻找可以到达目的节点的可用路由，如果按需路由在有效时间内未进行任何通信，那么将过期的路由信息自动删除，又被称为反应式路由协议。常见的按需路由协议主要有DSR和AODV等。一、DSR路由协议DsR【171路由协议是一种基于源路由概念的按需自适应路由协议，并且利用该路由协议发现新的路由时，需要更新移动节点保留的存储节点己知的源路由的路由缓冲器。DSR路由协议通过利用源路由机制使得每个分组的头部具有整个链路的信息。DSR路由协议使用的是源路由，并将路由信息存放到缓存器中，使得中间节点不需要存放进行转发分组所需要的路由信息，从而减少了网络开销，但缺点是缓存器中仍存在未更新的路由。DSR路由协议主要包 堕鐾直奎堂堡主堂垡丝茎括两个部分：路由发现和路由维护。(1)路由发现：当通信源节点需要发送消息到目的节点时，必须先查询路由缓存器，确定该缓存器中是否存有到达目的节点的路由。如果存在，那么就利用该路由发送消息；如果不存在，源节点则开始执行路由发现过程，并通过利用洪泛路由机制来执行路由发现过程。(2)路由维护：DSR路由协议主要支持两种链路状态的探测方式，其分别为主动应答和被动应答。该路由协议通过利用路由错误分组和确认分组实现路由维护过程。如果发现当前节点到达下一跳节点的链路发生中断时，该节点将发送路由出错分组到其源节点，源节点一旦收到向它发送的路由出错分组，就会将失效路由从原路由表中删除，同时在此过程中用于转发错误路由的节点也将会更新自己的路由表，并将路由表中包含链路中断的所有路由全部删除。此外，为了验证路由分组的正确性，则使用确认分组。二、AODV路由协议AODVtMl路由协议是根据DSDV路由协议以及结合DSR路由协议的按需路由机制对其进行改进而提出的。该路由协议是利用逐跳转发方式来提高带宽的利用率，而不是利用DSR的源路由方式。AODV路由协议一般认为无线链路是双向的。AODV路由协议主要包括两个部分：路由发现和路由维护。(I)路由发现：当一个节点有一条路由要到达新的目的节点时，广播RREQ消息用于找到一条可以到达这个新的目的节点的路由，并且该路由协议依赖中间节点动态地建立路由表使其分组传送。(2)路由维护：由于每个节点监视活动路由中到达下一跳节点的链路状态，当检测到一条活动路由中的一条链路发生中断时，就使用RRER消息来告知其他节点该链路已经被中断，并更新每个节点的路由表中的路由信息。2．2多路径路由协议目前，MANET网络的多路径路由协议主要是对按需路由协议进行扩展的。因为按需路由协议具有较低的路由开销，即该路由协议只在节点需要发送数据到目的节点时，才会建立路由，并不需要周期地进行更新路由表来对路径进行维护。源节点通过洪泛RREQ消息寻找可以到达目的节点的路由，并且随着节点移动导致链路中断时，才会更新路由，而不需要周 基于机会网络的QoS路由协议的研究期地更新路由表，减少了控制开销，同时使得路由信息能够有效的得到利用。多路径路由能够降低洪泛的频率，并在每次进行的查询过程中寻找多条可能的路由来降低成本，从而提供足够的冗余度。多路径路由可以使得通信节点的有限带宽、网络拥塞以及突发传输能够得到有效的利用，同时分组交付的可靠性也可以得到提高。因此，多路径路由是一种具有分配通信量、平衡网络负载、提供容错能力以及可靠性的简单机制。2．2．1多路径路由的不相交性不相交多路径能够使各条路径相互独立，同时路径连接或中断不会互相影响。不相交多路径主要以下有两种类型36】：(1)节点不相交多路径：除路径中共享的源节点和目的节点之外，任何公共的中间节点；(2)链路不相交多路径：除路径中共享的源节点和目的节点之外，公共的中间节点。2．2．2多路径路由的优点各条路径之间没有各条路径之间存在在MANET网络中，使用多路径路由进行消息传输来解决该网络的动态特性以及不可预测性。使用多路径路由的优点是使得网络负载可以得到平衡、具有解决容迟的能力以及可以提供较高的总带宽。方法是将数据分组发送到多条路径上来平衡网络负载，使得网络拥塞和瓶颈都有所减少。由于无线网络中的带宽资源的有限性，使得单路径路由不能保证可以为连接提供足够的带宽。而利用多条路径传输消息，则可以通过多条路径提供的总带宽来满足应用所需的带宽。因此，多路径路由能够提供更多的可用带宽，使得端到端的时延较小。2．2．3多路径路由的组成多路径路由主要由三个部分组成：路由发现、路由维护和流量分配。1．路由发现与路由维护：包含在通信源节点和相应的目的节点之间搜索多条可用路径的过程。多路径路由可以搜索多条节点不相交路由、链路不相交路由，或相交路由(具有公共节点和公共链路)。在多路径路由中，每当发生一次路由中断时就会触发路由发现过程，或者当所有路由全部中断后才会触发路由发现过程。如果直到所有路由中 内蒙古大学硕士学位论文断后才开始启用路由发现，那么需要花费一定时延来寻找新的路由，该方法是通过增加时延来降低应用的QoS。但是，如果每发生一次路由中断就触发路由发现过程又会使得开销过高。2．流量分配：当通信源节点选定了一个到达目的节点的路径集合时，利用这些获得的路径进行数据传输。流量分配策略是通过将数据分配到各条路径上进行传输的，并且如何选择分配间隔是相当关键的，这个分配间隔就是分配到每条路径上的最小单元。2．2．4多路径路由的分类根据MANET网络多路径路由对MANET网络性能的改善，可以将MANET网络多路径路由分成五种基本类型[37】：(1)以改善端到端时延为主的多路径路由技术，如AOMDV{38】；(2)以实现负载平衡为主的多路径路由技术，如SMRC39】；(3)以提高MANET网络系统可靠性为主的多路径路由技术，如MP．DSR[40]；(4)以提高MANET网络系统安全性能为主的多路径路由技术，如SPREADC4l】；(5)基于多重目标的多路径路由技术，如以实现负载平衡和改善端到端时延以及吞吐量为主的多路径路由MRP—LBf42J。一、AOMDV路由协议AdHoc按需多路径距离矢量(AdHocOn-DemandMultipathDistanceVector，AOMDV)【381路由协议是对AODV路由协议的改进，用来计算多条无环路和链路不相交的路径。无环路是利用“广播跳数”确定的，而链路不相交的路径是通过使用一种特定的洪泛策略获得的。AOMDV路由协议的主要思想是在路由发现过程计算多条路径。AOMDV路由协议主要是为了解决MANET网络中拓扑结构不断变化，导致链路频繁发生中断而提出的。由于该路由协议避免了AODV等单路径按需路由协议中存在的问题，即对每次发生的路由中断需要重复进行路由发现，并且进行一次路由发现都需要大的开销和长的时延，因此利用多条有效的冗余路径来解决这个问题。使用多路径的优点是只有当所有到达目的节点的路径全部发生中断时，才需要重新启用路径发现过程。二、SMR路由协议分离多路径路由(SplitMultipathRouting，SMR)【删协议是通过利用按需路由发现机制来建立两条最大不相交路径，并使用这两条路径进行消息传输，其中有一条路径的时延最短。SMR路由协议建立的每条路径不要求其长度是相等的，并将数据流分配到各条路由上进行传输，用于避免拥塞，使得有限资源可以得到高效合理的利用。利用多条路由可以使路由恢复过程的调用频率达到最小以及使控制开销最少，使其在MANET网络具有很好的性能表现。 基于机会网络的QoS路由协议的研究SMR路由协议具有两种路由维护方式[37]：(1)当已经建立的两条路径中的任意一条路径发生中断时，就重新建立一对新的路径；(2)当己经建立的两条路径全部发生中断时，就重新进行路由发现过程。与DSR路由协议比较，SMR路由协议丢失的分组更少，并且该路由协议将流量分散到多条路由上，使得负载被分散到多个网络主机。SMR路由协议具有较短的端到端时延，原因是当所有路由中断时，进行路由不需要获取时延。在上述两种路由维护方式中，第二种方式进行路由恢复的次数较少，因此使得路由开销产生的较少，表现出更高的效率。三、MP．DSR路由协议多路径源动态路由协议(MultipathDynamicSourceRouting，MP．DSR)‘401用于提高端到端的可靠性。端到端的可靠性是指通信源节点在时间窗口内给相应目的节点成功发送数据的概率。MP．DSR路由协议只能提供可以满足特定的端到端的可靠性要求的高概率持续路由，而且也允许QoS短暂中断。MP．DSR路由协议的要求：(1)MANET网络中移动节点移动的速度不能过快，否则不能实现QoS路由；(2)每个移动节点需使用全向天线，使其具有相同的通信距离，并且所有链路都是双向的；(3)存在相邻节点寻找协议。因为一条路径由多条链路组成，所以链路有效性来计算该路径的有效性。已知一条链路在时亥lJto是活动链，就将链路有效性定义为这条活动链从toNto+r有效的概率。根据节点的当前移动情况计算链路有效性。路径被定义为从源节点到目的节点的链路序列。如果假设所有组成路径的链路是相互独立的，那么路径可靠性就等于其所有链路有效性的乘积。4．。(f)表示连接节点m和n的链在时间周期f内的链路有效性，ri；．D(f)表示源节点S和目的节点D之问第七条路径在时间周期t内的路径可靠性，于是ri：．。(f)=1-I以，。(r)(2-1)(_，n)Ek根据链路有效性模型和路径可靠性模型定义端到端可靠性。已知一个特定应用的端到端可靠性要求，则MP．DSR寻找多条满足该要求的节点不相交路径，用于传输应用数据。在多路径路由中，当且仅当所有不相交路径在相同时刻全部中断后，数据传输才会中断。因此，多路径路由的数据传输中断概率低于单路径路由的数据传输中断概率。端到端可靠性P(0定义为在两个移动节点之间从时间气到f0+r内数据传输的成功概率，乙为任意时刻。于是，从源节点S到目的节点D的端到端可靠性以0为：12 内蒙古大学硕士学位论文肌)_l一罂(兀：∥r))(2-2)其中：K表示从S到D的节点不相交路径集合。可以按照并行方式或者备用方式沿着多条节点不相交路由发送数据。四、SPREAD路由协议可靠数据交付安全(SecureProtocolforReliableDataDelivery，SPREAD)[411协议通过结合秘密共享和多路径路由，降低消息被失密节点中途拦截或者被偷听的概率。SPREAD共享生成：SPREAD采用门限秘密共享系统来生成秘密消息的共享。假定有一个系统秘密K，将K分析Ⅳ小块Sl，＆，⋯，曲，这些小块被称为共享。系统有Ⅳ个参与者局，B，⋯，PⅣ，每个参与者单独拥有K的一个共享。秘密共享的生成保证不足r个参与者不能得到系统秘密K的任何信息，但Ⅳ个参与者中任意r个参与者采用某种有效算法能够恢复系统秘密K。这就是(T，Ⅳ)门限秘密共享方法，并且包含两个算法，一是分发器算法，即产生共享，并将共享分发到每条路径上进行传输；二是组合器算法，即从参与者中收集任意丁个共享，并回复原始秘密。如果收集的共享少于丁个，那么组合器将不能恢复原始秘密。SPREAD运用拉格朗日内插多项式生成共享。分发器通过多项式度数(T-1)得到第i个参与者的共享&：厂(功=(％+alx+a2x2+⋯+吩-IX卜1)roodp(2．3)墨=厂(耽x=i&分配给参与者尸，。其中p是大质数且大于所有系数口，，对分发器和组合器均有效；ao=K就是系数秘密，随机选择其他系数a0，aI，⋯，唧一。。组合器接收到丁个共享后，采用拉格朗日内插法就能够重构原始多项式。例如，如果所收r个共享为墨。，S：，⋯，＆，那么采用拉格朗日内插法恢复原始多项式删如下厂(x)=∑岛·lV(x)modp(2-4)j=l其中，伽)2飘irk=l，嚣(2-5)．It，‘，一k计算go)，得到原始秘密K，式(2卸在有穷域GF(p)上有唯一解。SPREAD的工作原理：源节点S如果需要给目的节点D安全地发送一条消息，那么运用 基于机会网络的QoS路由协议的研究多路径路由算法寻找从S到D的多条路径，并且多条路径具有某种属性，具体依赖所要求的消息安全等级和多条路径的有效性；然后S确定秘密共享方法，生成消息共享，将共享分配到选定的各条路径上，传递给D。S为分发器，D为组合器。由于受到质数P大小的限制，分发器将一条长消息分成若干个小块。根据所使用的路径数量，SPREAD可能会浪费许多带宽。为了节省带宽，在SPREAD中采用消息块分配全部系数a0，ai，a2，⋯，aN。D接收到r个共享后就能够恢复原始安全消息。五、MRP．LB路由协议具有负载平衡策略的多路径路由(Mul印athRoutingProtocolwithLoadBalancePolicy，MRP—LB)[421协议以分组为单位将流量均匀分配到源节点和目的节点之间的多条有效路径上，因此具有较强的路由变化的自适应能力，适用于MANET网络。MRP．LB是反应式路由协议，包含路由发现和路由维护两个部分【371。1．路由发现：在路由发现过程，源节点通过洪泛请求分组(REQ)发现到达目的节点路由。REQ分组包括源节点和目的节点的地址、本分组传递通过的转发跳序列、序列号。REQ分组将最终传播到目的节点。在REQ分组传播时，每个转发节点只为每个源节点和目的节点对转发一个REQ分组。2．路由维护：在lVlRP．LB路由协议中，每个节点为了连续跟踪与其相邻节点之间的连通性，需要周期性发送HELLO消息。HELLO消息中的源节点D是为了与相邻节点进行区分。如果一个节点在TIMEOUT时间内没有接收到其相邻节点的HELLO消息或者数据分组，那么可以检测出链路中断。每个节点为其相邻节点维护一个递减定时器，定时器初始值为TIMEOUT，节点只有在接收到其相邻节点的HELLO消息或者数据成功传输的确认时，才会将其定时器复位成TIMEOUT。一旦检测出链路中断后，立刻回复一个错误分组(ERR)给源节点。源节点和中间节点接收到ERR后，检查其路由表，删除使用该条中断链的路由，并更新路由表。2．3删盯网络的QoSMANET网络中的服务质量(QualityofService，QoS)是一个既富有挑战又复杂的问题，涉及到协议栈中物理层、MAC层、网络层、传输层以及应用层。14 内蒙古大学硕士学位论文2．3．1服务质量(OoS)概述QoS是网络为用户提供服务的性能等级。提供QoS主要是为了达到比较确定性的网络性能，能够更好地交付网络承载的信息以及网络资源的使用。网络可以为用户提供不同种类的服务，并且一种服务是由一组可测量的、预先说明的服务要求进行表述的。MANET网络的QoS参数：因为不同的应用对QoS的要求也不同，所以应用中所需的服务和有关QoS参数也有所不同。例如，多媒体应用的关键QoS参数主要有带宽、时延抖动、时延：军事应用需要具有比较高的安全要求；紧急搜寻与营救之类的应用的关键OoS参数主要是网络的有效性；会议厅中的小组通信主要是由于网络节点资源受限而造成影响，受限的资源主要有电池电量、处理能力、缓存器大小。2．3．2在II州ET网络中提供OoS所面临的问置与挑战MANET网络的特点给其QoS服务增加了很多困难。具体原因如下[371：(1)网络拓扑动态变化。由于MANET网络中节点是随机移动的，导致网络拓扑结构动态地进行改变，造成允许进行的QoS会晤可能经常会受到节点移动造成传输路径中断的影响，因此需要为QoS会晤重新建立用于传输消息的路径。在新建路径上，进行QoS会晤产生的时延可能会导致该会晤流的一些分组出现传输超时问题。但是对QoS有严格要求的应用是不能接受的。(2)状态信息不精确。在许多情况下，MANET网络节点需要维护特定链和特定流的状态信息。链路状态信息包括每条链的带宽、时延、时延抖动、分组丢失率、比特误码率、稳定性、开销、距离。流状态信息包括流的会晤Ⅲ、源节点地址、目的节点地址、OoS要求。由于MANET网络具有网络拓扑动态变化和无线信道的特点，因此状态信息和路由决策不精确，导致了有些实时分组发送的传输超时。(3)没有集中协调能力。MANET网络不同于无线局域网和蜂窝网络，没有固定基础设旋来协助节点的操作，使得为MANET网络提供QoS更加困难。(4)无线共享信道存在传输误码。无线信道实质上是广播传输媒介，在无线信道上进行传输时，无线电波容易受到多种损伤，如衰减、多路径传播以及相邻区域内其它无线装置的干扰。(5)隐含终端问题。隐含终端问题是MNAET网络中固有的问题。当两个或两个以上的通信节点同时发送分组时，在其公共的接收节点上会发生分组碰撞，此时就发 基于机会网络的QoS路由协议的研究生了隐藏终端问题。由于分组碰撞后使得消息传输失败，因而需要重传碰撞分组，但是在具有严格QoS要求的应用中进行分组重传是绝对不可以的。(6)资源有效性很有限。MANET网络的带宽、电池寿命、存储器容量、处理能力等资源都是很有限的。其中，带宽和电池寿命是比较重要的资源，其有效性能够严重影响QoS机制的性能。因此，需要通过高效资源管理机制，优化使用MANET网络的稀缺资源。(7)无线传输媒介不安全。无线传输媒介是广播信道，因此导致无线信道上的通信很不安全。MANET网络易受偷听、拒绝服务、消息失真、伪装等攻击。如果没有很好的安全机制，那么很难提供安全的通信保证。2．3．3IIMIET网络中OoS解决方法概述从协议层次来看，现有的MNAET网络的QoS解决方法分为两类：第一类是基于单个协议层的解决方法，即只从MAC层或网络层提供QoS服务和保证。MAC层协议主要提供带宽预留能力和实时流支持能力，但是只能确保链路级的预留。而网络层从端到端保证资源的协商、预留、重新配置。第二类是多个协议层在一定QoS体系下，跨层交互，相互协作，共同提供QoS服务和保证。QoS框架体系是一个完整的系统，其各组成部分通过密切协作来为每个网络用户提供所要求的服务或者所允若的服务。从网络协议栈来看，QoS框架体系经常会涉及到协议栈的多个层次。QoS框架体系主要由QoS模型、QoS路由、QoS信令、QoS媒介访问控制、呼叫准入控制、分组发送时间安排组成，其中QoS建模是关键组成部分。各个组成部分的功能和要求如下【37】：(1)QoS模型：定义满足用户要求的方法和途径，并对网络状态变化和流状态变化即时做出反应。(2)QoS路由协议：用于完成寻找从源节点到目的节点的路由，以及通过所寻找的路由逐跳将分组转发到目的节点。要求QoS路由协议利用极少的网络资源，迅速的对网络状态变化和流状态变化做出反映，并与QoS其他组成部分高效协作，共同提供端到端QoS保证。(3)QoS信令。找到QoS路由后，资源预留信令立即沿着这条路由做出所要求的资源预留。会晤结束后，将立即释放所预留的资源。(4)准入控制。找到可用的QoS路径后，系统必须决定是否真正为连接服务。如果呼 内蒙古大学硕士学位论文叫获得服务，那么QoS信令协议预留资源：如果呼叫未获得服务，那么应用得到准入被拒绝的通知。接受新呼ⅡLI不会影响已经获得准入的呼叫的QoS保证。QoS会晤服务数量是评估QoS框架体系的一个重要性能参数。准入控制可以确保己提供给获得准入的QoS会晤的QoS不会出现下降现象。(5)分组发送时间安排。当在一条传输链上存在多个活动QoS连接时，由分组发送时间安排机制确定下一个服务的QoS流。2．4本章小结本章首先介绍了MANET网络路由协议的分类，并且对其分类中典型的路由协议进行了详细阐述，其次详细介绍了几种多路径路由协议，最后对MANET网络的QoS存在的困难以及解决方法进行了详细的说明。 基于机会网络的QoS路由协议的研究第三章一种基于可靠节点的多路径QoS路由协议3．1RNMR路由协议的提出由于机会网络的特性，节点是随机自由移动的，并且没有固定的基础设施，导致网络拓扑结构不断地变化，使得链路频繁的中断[43】。为了在机会网络中能够找到相对稳定的路径，本章提出了一种在满足QoS约束条件下基于可靠节点的多路径路由协议(黜咖己)，来提高路径的稳定性，同时改善网络的QoS。多路径使用的是链路不相交的多路径，并且路径中公共的中间节点利用可靠节点所代替，这些可靠节点将整个路径分割成多条节点不相交的子路径，使得每条子链路相互独立，互不影响，来提高路径的稳定性。路径中的可靠节点是通过在所选取的研究场景中根据位置坐标信息确定的，并且通过电量模型来选取用于通信的最优可靠节点。机会网络中节点之间的通信一般都是通过节点所携带的无线通信设备进行互相通信，并且相遇节点进入到彼此的通信范围内时进行消息转发，并且节点所携带的无线通信设备的剩余电量和节点的传输距离相关联，即节点所携带的无线通信设备的剩余电量越多，节点传输消息的距离就越长并且节点的存活时间也会越长，反之，节点所携带的无线通信设备的剩余电量越少，节点传输消息的通信距离就越短并且节点的存活时间也会越短。因此，节点所携带的无线通信设备的剩余电量可以反映路径的稳定性【删。如果只考虑链路的连接时长不考虑节点的所剩电量，那么就不能准确的判定通信源节点能否将消息成功传输到目的节点。RNIVIR路由协议通过移动模型计算链路的过期时间，从而可以得到整条路径的过期时间，同时也考虑了相应节点所携带的无线通信设备的剩余电量，通过对这两个因素的综合考虑，利用路径中可靠节点，使其通过“存储．携带．转发”的路由模式进行消息传输，来提高消息的成功传输概率，使得整条路径的稳定性得到有效地提高，同时网络的QoS也得到了保障。在真实的场景中，通过观察和分析可知，移动节点并不是完全随机进行移动的，他们的移动轨迹具有一定的规律性，因为节点的移动范围往往会局限在某个特定区域或路径上【45】。例如，在学校里利用学生所携带的智能设备组成的机会网络中，学生经常在宿舍、食堂、教学楼这几个特定的建筑物进行活动，因此，这些节点的移动轨迹大部分时间是固定的。随着全球定位系统(GlobalPositionSystem，GPS)等定位工具的普及，节点的位置信息是可以通过这些工具获取到的。本章中提出RNMR路由协议用于提高路径的稳定性，保证消息能够尽可能地从源节点传输到目的节点。通过上述对影响路径稳定性因素的分析，设计一个有效合 内蒙古大学硕士学位论文理的多路径路由协议来改善网络的QoS是十分有必要的。3．2刚胀路由协议的设计为了说明RNMR路由协议的有效性，本节首先确定了研究场景，然后通过所确定的研究场景得到了节点所在区域范围的大小，利用全球定位系统(GlobalPositioningSystem，GPS)确定所在区域内节点的初始位置坐标信息，并且划定了可靠节点区域范围的大小。一、研究场景的确定通过对学校里学生的移动行为的观察和分析，发现节点的活动具有一定的规律性，因为在机会网络中节点虽然是随机自由移动的，但是在学校范围内活动的节点的移动轨迹大多数时间是相对固定的，所以，根据节点活动的相对固定的路线能够确定节点移动的方向以及偏移角度。一般情况下，节点是通过所携带的无线通信设备进行相互通信的，并且通过节点的移动到达彼此的通信范围内时，节点之间就可以进行数据的交换与共享了。为了确定节点的所属区域，利用全球定位系统(GlobalPositioningSystem，GPS)来获取节点初始时刻的位置坐标信息，并且通过节点移动的规律性确定移动节点的方向和偏移角度，然后通过移动模型可以计算出节点移动后的位置坐标信息。因此，研究场景一旦确定，选取研究场景中的建筑物作为节点所在区域范围的大小并对其进行研究，从而也说明了确定研究场景的重要性。二、研究区域的选取通过对研究场景的分析，将研究场景设定为学校，并且选择学校里的建筑物(例如，教学楼、宿舍楼、图书馆等)作为用来选取研究区域的对象。根据在学校内所选取的建筑物的面积大小的不同来确定所选研究区域的范围大小。选取研究区域范围大小的方法：将所选定的建筑物的中心作为所研究区域的圆心，并且以该建筑物的宽度作为所研究区域的直径，获得的这个圆的面积的大小就是研究区域选取的大小范围。假设所选取的这个圆的圆心为0，半径为R，即以R为半径这个圆的面积就是所选取的某个区域范围的大小。利用该方法选取研究区域范围大小的优点是：根据建筑物大小的不同，所选的研究区域范围大小也有所不同，并且每个区域内节点数目也各不相同，体现了该方法的实用性以及更加接近实际。因此，这种确定研究节点活动区域的方法可以运用到真实的环境中，并且也说明了该方法具有通用性。 茎王塑全堕垒堕旦!兰堕虫堡望塑堑塞三、可靠区域所在范围的确定在图3．1中所选取的研究区域范围内，截取一个以O为圆心，r为半径的同心圆，且设r=0．5R。将以r为半径的这个小圆的面积大小作为可靠节点所在区域范围的大小，并且该区域内的所有节点都被认为是可靠节点。利用GPS记录该区域内每个节点的初始位置坐标，同时由于可靠节点所在区域面积相对较小，因此每个节点通过广播RREQ消息获取其它可靠节点的位置坐标信息。例如，假设学校内相邻的两栋建造相同的建筑物的形状是相同的，因此其所选取的研究区域面积也是相同的，并且可靠节点所在区域的面积大小也相同，如图3．1所示。图3．1说明了在这两个面积大小相同的研究区域之间，它们区域中节点进行转发消息的过程，并且区域内的这些节点是随机分布的。图3-1两个面积相同的研究区域中节点的通信过程Fig．3-1Thecommunicationprocessofthenodesinthetwosameregions图3．1说明了在这两个面积大小相同的研究区域之间，其区域中的节点进行消息传输的过程，并且区域内的节点是随机分布的。3．2．2可靠节点的选取为了在可靠节点区域内选取最优的可靠节点进行消息传输，通过电量模型判定节点所携带的无线通信设备当前的剩余电量，并且通过计算每个节点的剩余电量比率来选取剩余电量比率最大的可靠节点用于消息传输。 内蒙古大学硕士学位论文一、可靠节点的选取过程图3．1中小圆的面积大小为可靠节点所在区域范围的大小，并且在该区域内选取用于传输消息的可靠节点。用于传输消息的可靠节点的选取过程如下：(I)通过GPS确定节点的位置坐标信息，判定该节点是否在可靠节点区域范围内：如果该节点在可靠节点区域范围内，那么继续执行第(2)步操作：否则就结束操作。(2)判定该节点是否为未被访问过的节点：如果该节点是未被访问过的节点，那么标记该节点，标记节点是为了与其它未被访问的节点进行区别，并且继续执行第(3)步操作；否则返回执行第(1)步操作。(3)判定当前标记的节点的剩余电量比率是否大于或等于0．3：如果该节点的剩余电量比率大于或等于O．3，那么将该节点存入到用于传输消息的可靠节点的集合中，并且寻找用于传输的可靠节点的循环一直进行，将所有找到的通信节点都存入到该集合中，直到所有节点被遍历完为止；否则返回执行第(1)步操作。上述描述的用于传输消息的可靠节点的选取过程，如图3—2所示：图3-2可靠节点的选取过程Fig．3-2Theselectionprocessoft．hereliablenodes21 基于机会网络的QoS路由协议的研究二、可靠节点剩余电量的判定为了从可靠区域内选出用于传输消息的最佳可靠节点，使用电量模型判定可靠节点的剩余电量，并通过进一步计算这些可靠节点的电量比率，来选出用于传输消息的最佳可靠节点。1．可靠节点的电量模型：设F是一个节点所携带的无线通信设备的电池的满电量，那么t时刻，节点f的剩余电量形一(r)的公式，如下所示：彬～(f)=彬～p一1)一Ⅳ母形”(t-1，f)一M木形”(t-1，f)一形“@一l，f)(3-1)上述公式(3．1)中的相关参数说明，如表3．1所示。袁3-1公式(3-1)中相关参数说明Table3-1TheinstructionsoftherelatedparametersinEq．(3-1)彬一0)节点i在t时刻的剩余电量彬r'm(t—I)节点f在t．1时刻的剩余电量彬”(t-1，r)节点i发送一个数据包所消耗的电量彬”(t-1，r)节i接收一个数据包所消耗的电量形“(t-1，，)电池内部所消耗的电量N节点f发送的数据包的个数M节点f接收的数据包的个数当f=oN，形”(f)=F。剩余电量形”(r)的取值范围为：0<形⋯(f)≤1。2．剩余电量比率的判定：通过计算节点的剩余电量比率，选取最佳的可靠节点，计算剩余电量比率Powerratio公式[461，如下所示：PD讹，．僦：型(3-2)}?通过上式，判定可靠节点所携带的无线通信设备的电池所剩电量比率。3．可靠节点剩余电量的范围判定公式，如下所示：删_{淼焉，慧篡8篇彗p3， 内蒙古大学硕士学位论文通过上述公式(3．3)判定节点的剩余电量所属范围，设可靠节点当前剩余电量比率为足拗讲Ⅳ，选取可靠节点的规则如下：(1)当‰曲，m≥0．3时，作为选取传输消息的可靠节点的范围。按照电量比率从大到小依次选取可靠节点，优先选取电量比率最大的可靠节点进行消息传输；(2)当RM。。0，有⋯limPm：刊<占)=-通过公式(3．18)可知，节点的相遇概率具有收敛性。3．2．4RN敝路由协议的描述(3·18)在机会网络中，网络拓扑结构是动态变化的，导致链路频繁中断，很难建立一条端到端的稳定路径。RNMR路由协议为了提高路径的稳定性以及数据包的成功传输的概率，因此在机会网络中使用多路径路由进行消息传输，使得消息能够尽可能地从源节点传输到相应的目的节点，同时网络的QoS也得到了保障。RNMR路由协议的设计思想是：通过使用MANET网络中链路不相交多路径路由协议传输消息，其中多路径由多条链路不相交的路径组成，并且将多路径中公共的中间节点设置为可靠节点，用于提高路径整体的稳定性，同时可靠节点的选取不仅考虑了其活动范围而且也考虑了可靠节点所携带的无线通信设备的剩余电量，进行综合评定选取最优的可靠节点，并且将选取的最优可靠节点用于消息的携带和传输，使得消息能够尽可能地传输到目的节点，从而来降低整个网络的丢包率，因此使得网络的QoS得到了保障。由于一条路径的寿命可以反映这条路径的稳定性，本节通过数学推导可以计算得出RNMR路由协议的路径寿命的累积分布函数(CumulativeDistributionFunction，CDF)[471，并且通过得到的CDF进一步计算RNMR路由协议的路径过期时间的期望，用于确定路径的寿命。以下通过对网络场景中的路径进行设计，获得RNMR路由协议的路径寿命的CDF。假设在源节点S和目的节点D之间包含三条路径：一条主路径和两条相应的备用路径。这三条路径是由链路不相交的路径组成，路径中公共的中间节点设置为可靠节点，相邻的两个可靠节点之问的不相交子路径的长度为3跳。主路径是由可靠节点及中间节点连接而成的距离最短的路径，其中，可靠节点的数量为m，并且可靠节点将整条路径分割为m一1条子路径，第i条子路径表示为厶(i=1，2，．．．，m一1)，其相应寿命为z厶。厶有两条备用路径，分别表示为幽f，1)和缎啦)，幽u)的相应链路分别表示为嬲：，1)，职i。)和幽j1)’其相对应的寿命分别表示为‰'I)，誓k，1)和《k，1)，嬲啦，的相应链路分别表示为幽：’2)，磁i：)和嬲i：)，其相对 内蒙古大学硕士学位论文应的寿命分别为xk．2)，x葫，2)和％，2)，这两条备用路径的相应寿命分别表示为五鹳，。)和五鹕．2)。因此，厶的两条备用路径础u)和础f’2)的相应寿命五础-1)和五衅，2)的公式，如下所示：五艘’1，=州磁∞，誓‰∞，墙∞)五础，2)=min(Xk．2)，誓岛．2)，露鹋’2))(3-19)(3—20)上述两条备用路径职¨)和职f．2)中，它们每条路径中的其中的一条链路分别表示为上B昂，。)LB&啦J，其相应寿命分别为五嘲．1】和五域．2】。当主路径连接失败时，选取备用路径螂¨)和幽啦)中的一条最优的路径继续进行消息传输。‰表示为五础，1)和五域J2)中寿命最长的那条备用路径的寿命，其公式如下所示：f3-21)从源节点S到目的节点D的路径寿命r的公式，如下所示：r=min(max(X厶，五明，I)，五明，2))，max(X岛，五观m，五明，2))，-．．，max(屯。，五置‰，1)，五砜。)))(3-22)=rain(‰，五啦，五％)路径寿命r的累积分布函数公式，如下所示：FAt)=PIT≤f】=尸[m巡max(墨，五幽．1)，五竭’2))，ma《吒，x(飓’1)，五码，2))，．．．，max(&。，五‰”五‰，2)))≤妇=P[mtn(‰，‰，-．．，‰。)≤胡(3-23)=1一兀(1一研‰≤f】)t=1J^—I=1-n(1一％∽)f=l假设五．扛1，2，．．．，m-1，是独立同分布的随机变量，吒的概率密度函数近似满足指数分布。其中，五蚺的概率密度函数是k(f)=^P叫‘471，^=(m-1)／l，f是平均链路寿命。置和％见的累积分布函数公式，如下所示：j，吃(f)=1一P。(3-24)-苎，％剐(r)=1一e7(3-25) 基于机会网络的QoS路由协议的研究B口)=1一e7“(础，2)、7吃。(f)=(1一P飞l—P7)2RNMR路由协议的路径寿命丁的累积分布函数公式，如下所示：Fr(t)=1_[1一吃(f)‘剐(f)‘剐(f)r=1-[1一B。(坩’1；1一[1一(1一e-7‘)(1一P-7‘)2】“一1=1-(e‘+2e’一2P。一e7+el--!--!)⋯“～r—f3．3刚脓路由协议的验证和性能分析(3—26)(3·27)(3-28)为了研究RNMR路由协议的路径寿命，将其与没有本地备用路径的基于贪婪的备用路由协议(GBR-WB)以及备用源路由协议(BSR)进行比较。GBR．W-B[291是一种没有本地备用路径的基于贪婪的备用路由协议(GBR)，是一个单路径路由协议，使用贪婪转发机制构建一条路径，并且不考虑任何备用路径。该路由协议的路径寿命近似等于Z／h。其中，Z是平均链路寿命，h是路径长度。BSR[301是一个多路径路由协议，该路由协议除主路径之外还有相应的备用路径，在路径之间可能有公共的节点或链路，并且通过链路相似性和节点相似性构建备用路径。BSR路由协议的路径寿命的累积分布函数公式，如下所示‘30】：辱o)=1一P一缸兀№-h／+P一咖一e-h／-h))(3—29)户1其中，k表示为主路径和备用路径中具有相同链路的数量，w表示为路径中不相交子路径的数量，hj和办：分别表示为相应的不相交子路径的长度U=1，2，．．．，w)。为了验证RNMR路由协议的性能，使其与GBR-WB以及BSR路由协议进行比较，其相关参数的设定如表3．2所示。根据文献[30】可知，在BSR路由协议中，主路径和备用路径之间链路相似性越低，路径的寿命越长。因此，k的值越小，W的值越大，获得的相应路径寿命就越长。 内蒙古大学硕士学位论文表3-2m眦R，GBR-WB和BSR路由协议相关参数的设定Table3-2ThesettingoftherelatedparametersaboutRNlVIR，GBR·WBandBSRprotocol平均链路寿命，=ls主路径和备用路径的相同链路数量k=0主路径长度h=2，3，4，5，6，7，8=m-1不相交子路径1的长度h；=2不相交子路径2的长度h：=3利用可靠节点将主路径分割后的m一1子路径的长度通过理论分析可知，随着RNMR、GBR-WB和BSR路由协议的主路径长度的改变，其相应的路径寿命的期望值也会随之改变，如图3．4所示。Lengthoftheprimarypath∞图3．4不同长度的主路径的期望寿命Fig．3-4Theexpectedroutelifetimeofthedifferentprimaryroutelength图3-4说明了随着主路径长度的不断增加，导致路径寿命的期望则随之减少。其中，X轴表示主路径的长度，Y轴表示路径寿命的期望。这个趋势的发生主要有两个原因： 基于机会网络的OoS路由协议的研究(1)随着路径长度的增加，导致路径的稳定性降低；(2)主路径越长，则备用路径就越长。从图3-4中可以得知，RNMR路由协议的路径寿命的期望明显高于GBR．WB和BSR路由协议的路径寿命的期望，说明了RNMR路由协议具有更好的性能。3．4本章小结本章主要分析了RNMR路由协议的性能，并且对其性能进行了理论分析和验证。在该路由协议中引入了可靠节点，用于延长路径的寿命，从而使得路径整体的稳定性得到提高，其中可靠节点是通过节点位置的判定以及节点的剩余电量所确定的，同时提高了消息的端到端的成功传输概率，因此保证了网络的QoS。30 内蒙古大学硕士学位论文第四章一种基于备用路径的QoS路由协议4．1BP讯路由协议的提出4．1．1不相交路径的穗定性分析在多路径路由协议中，建立多条不相交路径可以分散网络中的预留资源以及数据，使得网络的有效带宽得到了增加，同时丢包率和拥塞控制被降低。不相交路径主要被分为两种类型：链路不相交的路径和节点不相交的路径【3们。链路不相交路径除了源节点和目的节点之外，路径中存在公共的中间节点，如图4-1(口)所示，而节点不相交路径除了源节点和目的节点之外，路径中没有一个公共的中间节点，如图4．1(6)所示。N21(口)Nlt，论一一一一一一、、--o一一一一一一一N2tN1肘N2HA11A12⋯⋯AlkA1ⅢA22⋯⋯一一咱一⋯⋯A2t(6)A2H图4．1链路不相交路径(a)和节点不相交路径(b)Fig．4-1Link-Disjoinmesspath(a)andNode-Disjoinmesspath(b) 萎主垫盒堕塑塑Q!兰堕虫垫坚塑堕壅本节通过对链路不相交路径和节点不相交路径的稳定性进行了分析和比较，并根据分析比较结果在多路径中选择一条合适的路径。在机会网络中，由于节点的随机移动，导致链路频繁中断，很难建立一条稳定的端到端的路径。一条路径的稳定性分析：假设一个多路径艘由2条路径组成，其中f表示两条路径中公共的中间节点的数量，这两条路径分别为互和昱，其长度分别为州和行。因此，多路径煅被分为以下两种情况：(1)当i：0时，表示这两条路径中没有公共的中间节点，即它属于节点不相交路径；(2)当i≥1时，表示这两条路径中至少有一个公共的中间节点，即它属于链路不相交路径。假设每个节点的移动概率是P，即每个节点都有相同的移动概率。因此，根据节点移动的概率，可以计算出路径中断概率p，以及路径稳定性概率见的公式，如下所示：p，=l-(1-p)”(4-1)只=(1-p)”(4-2)根据上述给出的这两个公式，可以计算出一个多路径中路径被破坏的概率。设‰表示路径中没有公共的中间节点(如节点不相交路径)，‰表示路径中有一个公共的中间节点(如链路不相交路径)，其计算公式如下所示：(1)当i=0时，p蛾=fiN8=[1一(1一p)”】[1一(1一曲”】(4-3)(2)当i=1时，p他=墨n￡=【1一(1一p)’”1l[1-(1-p)”。1】+p(4-4)比较Pueo和‰的大小，来判定路径的稳定性，其比较公式如下所示：Z(p)=乌蛸一，k=【1一(1一p)“_1Ⅱ1一(1一p)“-1】+p一[1一(1一p)“】[1一(1一p)”]=l一(1一p)”～一(1一p)“-1+(1一p)”+”一2+p-1+(1一p)”+(1一p)”一(1一p)””=P-p(1-p)”．1-p(1-p)”1+p(2一p)(1一p)“”_2=p[1一(1一p)”～一(1一p)”。1+(2-p)(1-p)“。1(1-p)“。1】(4-5)≥p[1一(1一p)1～一(1一p)”_1+(1一p)4_1(1-p)4-1]=p[1-(1-p)”1][1-(I-p)”1]>032 内蒙古大学硕士学位论文通过公式(4．5)可以得到，当i=2时，％≥％p鸠=露n罡=【l一(1一p)⋯一2】【l一(1一p)”一2】+2p(4-6)(4—7)比较p姚和PMn的大小，用于判定路径的稳定性，其比较公式如下所示：五(p)=‰一PM4=【1一(1一p)⋯-2】[1一(1一p)”2】+2p一[1一(1一p)”-1][1-O-p)”1]-p=1一(1一p)”2一(1一p)”2+(1一p)”“-4+2p-l+(1-p)”1+(1一p)”-1-(1-p)””～一p=p—p(1一p)”～一p(1一p)砘+p(2一朋一p)””-4(4．8)=p[1一(1一p)”一2一(1一p)4-2+(2一p)(1一p)”’2(1一p)”一2】≥p[1一(1一p)”2一(1一p)“-2+(1一p)”2(1一p)”毛】=烈l一(1一p)”一2][1一(1一p)”-2】≥0通过公式(4．8)可以得到，％≥‰根据以上推导可知，对于Vf，都有，(4-9)p峨≥P旧≥P^儡，七>，>0，Ij}≤mirl(m，玎)(4-10)通过对链路不相交路径和节点不相交路径的稳定性进行分析和比较可知，多路径的破坏概率不仅与中间节点的数量有关，而且与路径不相交性也有关。因此，多路径中节点数越少，链路被破坏的可能性越小。通过公式(4—10)可知，多路径中路径之间的公共中间节点数越少，路径的破坏概率越小，反之，多路径中路径之间的公共中间节点数越多，路径的破坏概率越大，其中，多路径PMa的破坏概率最小。也就是说，节点不相交路径的破坏概率最小，其路径的稳定性最好。因此，在多路径路由协议中基于节点不相交的路径被广泛使用。4．1．2BP豫路由协议的提出原因随着智能设备的不断普及，人们对网络的QoS的要求也越来越高。因此，在机会网络中，通过使用长的路径寿命、低的路由开销以及高的发送速率来建立稳定的路径是一种不断发展的趋势。此外，路径的寿命可以反映该路径的稳定性‘481。根据上述对不相交路径的稳定性的分析，在多路径路由协议中，路径中路径之间的公共中间节点数越少，路径的稳定性越高， 茎主塑全塑竺塑旦!兰堕叟塑鲨堕堕壅而且节点不相交路径比链路不相交路径的稳定性更高，同时链路不相交路径之间的公共中间节点数越少，路径就越稳定。但是在机会网络中没有固定的基础设施，节点又是随机移动的，导致链路频繁中断，为了解决这些问题，本章提出了一种基于备用路径的QoS路由协议(BPQR)，使用BPQR路由协议来改善网络的QoS，并且多路径由链路不相交的路径构成，同时为了让链路不相交路径的稳定性近似于节点不相交路径的稳定性，本协议引入了稳定节点，用于提高路径的稳定性，并利用这些稳定节点代替路径中公共的中间节点，用于提高路径整体的稳定性，同时将长的路径分割成较短的节点不相交路径用于消息传输，减少了路由开销以及降低了端到端的丢包率，因此，使得网络的QoS得到了保障。根据对移动节点的分析发现，每条链路的连接时长不仅和节点的移动速度以及通信半径有关，而且与节点所携带的无线通信设备的剩余电量也有密切关系，因为设备所剩电量越少，通信范围就越小，同时传输的消息数量也会变少。例如，当两个节点在连接时长范围内进行消息传输时，可能在链路没有中断时节点的电量已经全部耗尽，因此，对链路的寿命不能得到准确的判定。综上所述，BPQR路由协议可以提高路径的稳定性，同时能够使有限的网络资源高效合理的利用，体现了BPQR路由协议的有效性。4．2路由协议的设计本协议首先对研究场景中节点的活动进行了观察和分析，并发现节点的活动具有一定的规律性，可以通过GPS确定每个节点的初始位置坐标。然后，由于节点的移动具有方向性，可以通过移动模型获得节点移动后的位置坐标。其次，通过判定相遇节点剩余电量来选取稳定的节点作为主路径和备用路径中公共的中间节点。最后，通过计算每条链路的过期时间得到整条路径的过期时问，从而确定路径的寿命。通过对学校学生以及上班族移动行为的观察和分析发现，大多数移动节点的活动具有一定的规律性，并且这些移动节点具有方向性。利用全球定位系统(GlobalPositioningSystem，GPS)确定每个节点的初始位置坐标，并根据节点的移动方向可以判定节点的偏移角度，从而能够计算出节点移动后的位置坐标信息。 内蒙古大学硕士学位论文4．2．2稳定节点的选取一、稳定节点的选取过程在研究场景中，从源节点S到目的节点D之间选取最优的路径是通过相遇节点的剩余电量以及节点之间形成的链路的寿命进行选取的。稳定节点的选取过程，如图4．2所示：图4．2一个稳定节点的选取过程Fig．4-2Theselectionprocessofastablenode图4-2中稳定节点的选取过程分为以下三个步骤：(1)利用GPS确定节点的初始位置坐标，判定节点是否在研究场景内：如果该节点在研究场景内，继续执行第(2)步操作；否则就结束操作。(2)判定该节点是否为未被访问过的节点：如果当前节点是未被访问过的节点，那么读取节点当前的剩余电量并标记该节点为已访问节点，继续执行第(3)步操作；否则返回执行第(1)步操作。 墨主塑全塑丝箜里!兰堕虫塑望堕堡壅(3)判定当前标记的节点的剩余电量是否在高电量范围内：如果节点的剩余电量是在高电量范围内，那么选取该节点作为稳定节点，完成了稳定节点的选取过程并结束操作；否则返回执行第(1)步操作。二、稳定节点的判定标准为了提高路径的寿命，在路径建立的过程中选取相对稳定的节点来维持路径，根据相遇节点当前剩余电量来选取稳定节点。这些稳定节点被作为主路径和备用路径中公共的中间节点，来提高路径整体的路径寿命。根据计算每个节点当前的剩余电量，来选取用于传输消息的稳定节点，从而可以获得更加稳定的路径。假设节点接收和发送数据包的大小相同(即每个节点接收和发送一个数据包所需的电量是相同的)，那么，，时刻，节点f的剩余电量P(t)的公式，如下所示：只～(r)=P⋯@一1)一K’只“O一1，r)一只“(t-1，f)(4·11)上述公式(4—11)中的相关参数说明，如表4．1所示。袁4-1公式(4．11)中相关参数的说明Table4-1TheinstructionoftherelatedparametersinEq．(4-11)#～(，)节点i在t时刻的剩余电量P～O-1)节点i在t一1时刻的剩余电量节点f在r一1到r时刻接收或发送一个数据包P⋯(f—l，，)所消耗的电量P“(t-1，r)节点f在f一1到t时刻自身所消耗的电量K节点f在t-1到t时刻接收和发送数据包的个数为了在研究场景中选取更加稳定的节点用于消息传输，根据计算节点的剩余电量，将研究场景中的节点的剩余电量分为两个范围：低电量范围和高电量范围。设剩余电量的阈值为圪(f)，节点f的剩余电量的所属范围的判定规则如下：(1)当时圪(f)≥P”O)，说明节点i的剩余电量在高电量范围内；(2)当时岛(，)