《基于粒子群算法的ad hoc网络路由优化方法研究-宋盼盼.pdf》由会员分享，可在线阅读，更多相关《基于粒子群算法的ad hoc网络路由优化方法研究-宋盼盼.pdf（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、分类号：TP393中让史警单位代码：学 号；10110$1407109North University Of China基于粒子群算法的Ad Hoc网络路由优化方法研究硕士研究生 塞验验万方数据图书分类号UDCTP393全日制工程硕士学位论文基于粒子群算法的Ad Hoc网络路由优化方法研究宋盼盼指导教师(姓名、职称) 扬塞廷 副教授申请学位级另0 工程亟专业名称 软性王程论文提交日期 2Q! 年月上日论文答辩日期 2Q12 年月上日学位授予El期年月一日论文评阅人 鄞银童 郑窒莲答辩委员会主席 王晓熬2017年6月7日万方数据、姗原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指
2、导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人论文作者签名：穿垃函L一日期：二鲨二生L关于学位论文使用权的说明本人完全了解中北大学有关保管、使用学位论文的规定，其中包括：学校有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内容(保密学位论文在解密后遵守此规定)。签 名：叠砬赴
3、 日期： 22：!登导师了 P孓，竹7。L万方数据中北大学学位论文基于粒子群算法的k,d Hoo网络路由优化方法研究摘 要Ad Hoc网络是由多个可移动节点组成的无线网络，它以无中心、自组织、不需要基础设施支持、采用分布式管理系统、网络拓扑结构灵活变化等特点应用在特殊领域，例如：灾区救援、战场、传感器网络等。由于这些特殊领域对网络的传输速度、传输延时、传输过程中的消耗有更高的要求，原有的Ad Hoc网络协议不能提供这些服务，因此在网络拓扑结构一直变化的Ad Hoc网络中，提供有服务质量保障的路径是一个很重要的任务。本文的主要工作如下：(1)介绍标准PSO算法的思想、算法中参数的意义、算法的工作
4、流程，在此基础之上，引入惯性权重(RaIldWPSO)、线性递减(LDWPSO)、收缩因子(CFPSO)、混沌(ACPSO)四种改进粒子群算法，采用MATLAB进行仿真实验，把四种算法应用到网络中，实验结果表明：ACPSO可以更快找到最优路径并且快速传输数据。(2)AODV路由协议有两个缺点：没有考虑实际网络中带宽、时延和代价；路由表只存在唯一一条从源节点到目的节点的路径。根据这两个缺点，结合混沌粒子群算法对AODV协议的RREQ、RREP数据包进行改进，同时也改进路由发现，路由维护和修复机制。(3)基于NS2仿真平台，对改进的AODV协议建立仿真模型并且进行实验，设置不同的网络环境，测试分组
5、投递率、网络延时、路由发现频率。实验的结果表明：传输数据过程中，改进的协议比AODV协议找到的路由性能更高，可以更快、更稳定传输数据。关键词：Ad Hoe，粒子群，AODV，QoS万方数据中北大学学位论文Research on Routing Optimization ofAd Hoc networks based onparticle swarm optimizationAbstractAd Hoc network is a wireless network composed of a plurality of mobile nodes，with nocenter，self-organiza
6、tion，do not need to support infrastructure，usually adopts the distributedmanagement system，flexible network topology change characteristics used in the specialfields，such as disaster relief,battlefield，sensor networkThe special field of the networktransmission speed，transmission delay and transmissi
7、on in the process of consumption havehigher requirements，the original Ad Hoc protocol carl not provide these services，SO thenetwork topology has been changing Ad Hoc network，to provide a path to guarantee qualityof service is a very important taskThe main work of this paper is as follows：(1)the stan
8、dard PSO algorithm，the parameters in the algorithm，the significance of thealgorithm process，on this basis，the introduction of the inertia weight(RandWPSO)，(LDWPSO)，a linear decreasing shrinkage factor(CFPSO)，(ACPSO)four improved chaoticparticle swarm algorithm，using MATLAB simulation experiment，four
9、 the algorithm isapplied to the network，the experimental results show that ACPSO can quickly find theoptimal path and fast data transmission(2)AODV routing protocol has two disadvantages：without considering the bandwidth，delay and cost of the actual network；there is only one path from the source nod
10、e to thedestination node in the routing tableAccording to these two shortcomings，we combinechaotic particle swarln algorithm to improve the砌也Q and RREP packets ofAODV protocol，and also improve routing discovery，routing maintenance and repair mechanism(3)based on the NS2 simulation platform，a simulat
11、ion model is set up for the improvedAODV protocol，and experiments ale carried outDifferent network environments are set upto test packet delivery rate，network delay and route discovery frequencyThe experimental万方数据中北大学学位论文results show that in the process of data transmission，the improved protocol is
12、 higher than therouting protocol found by AODV protocol，and can transmit data faster and more stablyKeywords：Ad Hoc，PSO，AODV,QoS万方数据中北大学学位论文1绪论目 录11课题研究背景和意义。112国内外研究现状2121 Ad Hoc网络研究现状。2122粒子群算法研究现状213论文的组织结构。32 Ad Hoc网络21 Ad Hoc网络概述。5211 Ad Hoc网络特点及应用。5212 Ad Hoc网络拓扑结构。722 Ad Hoc网络路由协议8221路由协议简介82
13、22现有的Ad Hoc网络协议分类923 Ad Hoe网络路由协议的QoS保障1324本章小结。143粒子群算法31粒子群算法简介15311粒子群算法原理15312粒子群算法与其它算法比较。1732几种常用的改进的粒子群算法18321惯性权重改进算法(RandWPSo)18322线性递减的权重(LDWPSo)19323收缩因子改进算法(CFPSO)19324混沌的粒子群算法(ACPSO)19万方数据中北大学学位论文33 ACPSO算法和其它各种改进粒子群算法的比较2134 ACPSO算法在网络拓扑结构中的仿真结果和分析。2335本章小结254基于ACPSO算法的Ad Hoc网络QoS路由协议4
14、1基于ACPSO粒子群算法的Ad Hoc按需路由协议(AODV-AC)概述26411 AODV关键技术和缺点概述26412按需路由协议(AODV-AC)概述2642 AODV-AC 1办议27421 AODV-AC协议的通信包格式。27422 AoDv-AC协议的路由发现32423 AODV-AC协议的路由维护与路由修复3443 AODV-AC与AODV的对比3544本章小结355仿真实验及性能分析51 NS2网络仿真软件概述3652仿真实验36521仿真环境和参数36522不同节点数目对协议性能的影响38523不同速度对协议性能的影响39524网络负载对协议性能的影响40525仿真实验结论4
15、153本章小结426总结与展望61总l宕4362展望43参考文献45II万方数据中北大学学位论文攻读硕士学位论文期间发表的论文及所取得的研究成果致谢III万方数据中北大学学位论文11课题研究背景和意义1绪论Ad Hoc1也被称为无线自组织网(wireless self-organized network)，它是由多个可移动节点组成的无线网络，以无中心、白组织、不需要基础设施支持、通常采用分布式管理系统、网络拓扑结构灵活变化等特点应用在特殊的领域，例如：灾区救援行动、战场、传感器网络等。当发生泥石流滑坡、台风这些自然灾害、通讯设施被摧毁或者出现故障不能及时修复，为及时与灾区进行通讯，搭建不需要依
16、靠固定设备又能快速建立的Ad Hoc网络就成为最佳选择。根据Ad Hoc自身的优点，现在越来越多的人把它应用在实际生活当中。随着Ad Hoc网络被广泛应用在实际生活中，人们提出更多更高的要求来满足自己的业务的需求，除了要求Ad Hoc网络易搭建外，对网络的传输速度、传输延时、传输过程中的消耗、通讯质量和安全性也有定的需求。因此在网络拓扑结构一直变化的Ad Hoc网络中，要解决这些问题，最关键的是Ad Hoc网络要支持QoSl21。当关键特殊的业务需要在网络中需要进行传输时，首要的任务是考虑QoS指标。由于QoS是网路提供给应用的一种保障，用来确保应用可以高效完成他所需求的业务和功能，所以Ad
17、Hoc网络提供QoS保证体系【3使得自己能支持QoS。当网络负载过大，或者是发生阻塞时，QoS可以保障网络有效运行，防止一些重要的业务被遗弃或者丢失。在支持QoS的Ad Hoc网络中，为满足数据传输中各方面性能的要求，找到一条拥有足够资源的路径就成为关键。由于Ad Hoc网络拓扑结构动态变化，找到一条满足QoS要求的路径，成为一个多约束NP问题【41。现在常用粒子群算法来解决这个多约束NP问题【4。相比遗传算法【6】、蚁群算法7】等。粒子群算法8的思想简单，参数少，比较容易改进，能够更好的满足实际的需求。AdHoc网络由于可移动、自组织、动态的网络拓扑结构，给QoS路由协议的性能带来很多的限制
18、9。基于距离矢量、基于链路状态信息的这两大类协议，是传统无线网中较为成熟的协议。这两类协议的主要缺点是：都需要经常发送报文信息来控制网络的万方数据中北大学学位论文状态，而且还需要实时维护网络的连接。由于Ad Hoc自己的特点、以及传统无线网络中协议的缺点，发现传统的网络协议不能很好的适用于Ad Hoc。为了能够使协议更好的适应于Ad Hoc中，改善传输数据的能力，在满足QoS的路由协议中，使用粒子群算法找到最优路径，就变得更加有实际应用价值。12国内外研究现状121 Ad Hoc网络研究现状目前，国内外很多人开始对Ad Hoc网络进行研究。其中Ad Hoe路由协议、QoS路由、网路安全、网络重
19、构等成为现在研究的热点。例如：美国MONARCH建立的“移动测试网络床”、康奈尔大学“无线网络实验室”等【101。Kaan Bur和Cem Erosylll】，在2005年提出AQM(Ad Hoc Qos Multicasting)协议，该协议通过跟踪每个节点的可用资源，实现多播的高效率。Huayi Wu和Xiaohua Jia12在2007年提出一个新方案，通过使用多个路径，或者是多棵树满足呼叫带宽的新的多播路由，这种方案可以提高呼叫效率，更好的利用网络资源。把QoS指标加入到路由协议中，主要采用以下两种的方式：改进已有的传统路由协议；设计新的路由协议。列如：文献【”坤提到一种称为CEDAR
20、(coreextraction distributedad hoe routing)Ad Hoc路由算法；Chen于1997年提出一种基于DSDV(DestinationSequenceddistanceVector)无环路距离向量路协议的带宽约束路由算法；文献【15】给出一种LTBR(10cationaided，ticketbased QoS routing)QoS路由协议；文献16l提出新的协议称为TBP(ticketbased probing)，是基于标签探测而改进的分布式协议。122粒子群算法研究现状粒子群算法(Particle Swarm Optimization，PSO)是一种进化
21、算法，根据鸟群觅食行为，通过自我调节找到局部最优，利用局部最优寻找全局最优的算法。粒子群由于其自身原理简单、实现容易、参数少、精度高、快速收敛等优点受到许多研究人员的关注。现在有很多对粒子群算法理论方面的改进，主要是对算法中参数的修改，或者是结合其2万方数据中北大学学位论文他优化算法。例如：Angeline提出通过自然选择寻找最优粒子的方案171：Wachowiak提出基于Powell机制的改进粒子群算法18；E1 Gallad A，E1 Hawary M，Sallam通过实验对PSO算法中参数的作用进行详细的验证，寻找一种方法对参数进行统一的赋值191；Noel等人利用粒子群算法，对梯度信息
22、进行局部搜索201；Shi等人为加强局部搜索的能力把粒子群算法和遗传算法相结合211。现在粒子群算法主要应用在：(1)求解约束的优化问题。例如：许君、鲁海燕等人，在无约束优化的问题上，限制粒子群速度和调节自适应速度zz】；顾宏杰、许力，通过为粒子赋予自适应感知能力，来更好地求解约束优化问题231；廖锋，把粒子群算法的约束优化问题用在BP神经网络中【24】；寇晓丽、刘三阳，面对解决约束优化问题时候，把模拟退火算法与PSO相结合25】。(2)最优控制问题的求解。例如：胡佳俊利用粒子群算法控制有源噪声26】；梁计锋将混沌理论引入PSO算法中，优化LSSVM的核参数和惩罚系数从而提出新的交通流量预测模
23、型271；应进，基于粒子群算法，设计航空发动机鲁棒控制器【28；梁晓龙等人针对开关系统，利用PSO算法解决控制最优的问题z91。(3)多目标优化。例如：邓春玲，通过改进多目标粒子群算法，最后把改进的算法用在软件工程中网络讨戈0中【30；许婧祺，利用粒子群多目标算法，实现云计算调度优化3t；冯琳，为更好的使用电弧炉供电，在这个过程中，使用粒子群的多目标改进算法【32；陈强把改进粒子群算法应用在仿人机器人中多步态目标优似s3。13论文的组织结构本论文分为六章，具体的安排如下：第一章，绪论，介绍研究本课题的背景和意义、Ad Hoc网络和粒子群算法的现状、以及本论文的组织结构。第二章，介绍Ad Hoc
24、网络特点、应用领域、拓扑结构以及相应的路由协议；对路由协议进行分类，简单介绍表驱动路由协议DSDV和WRP、按需路由协议DSR和AODV，同时对这两种协议进行比较；提出对Ad Hoc网络QoS的保障机制。第三章，研究粒子群算法。介绍四种改进粒子群算法惯性权重改进算法3万方数据中北大学学位论文(RalldWPSO)、惯性权重改进算法(RandWPS0)、收缩因子改进算法(CFPSO)、混沌的粒子群算法(ACPSO)，并且在经典函数下对这些算法进行测试，实验结果显示：在带宽一定时，混沌粒子群算法传输数据较快、延时较低。第四章，介绍AODV协议存在的缺点，结合第三章选出混沌粒子群算法(AcPsO)的
25、特点而提出基于AODV的新协议，并且详细设计通信包格式、传输机制、最佳路由的选择和备用路由的产生。通过增加QoS约束、可靠的备用路径，使得数据传输更高效并且能够减少网络的开销。第五章，简单介绍NS2仿真软件以及选择它的理由，对改进的路由协议进行仿真实验和性能分析。通过仿真实验，验证改进后的协议比改进之前有更好的性能，更能提高AdHoe网络通讯质量。 第六章，总结与展望，对整篇文章进行内容总结，提出新的路由协议仍然有许多需要改进的地方，这些将会是自己后来的研究方向。4万方数据中北大学学位论文21 Ad Hoe网络概述211 Ad Hoc网络特点及应用2 Ad Hoc网络AdHoc网络可以根据实际
26、需要随时搭建，网络中每个节点无规律移动，路由的多跳性是它最大的特点【341。在Ad Hoc网络中，节点之间可以随机连接并且进行通讯，每个节点既可以作为源节点发送数据，也可以作为中间节点进行信息的转发，除这个特征以外，AdHoe网络仍然有许多特点，这些特点是不同于传统的网络，主要表现在：(1)无中心、自组织。搭建Ad Hoc临时网络通常采用分布式算法，随机选取节点，自己快速组网。这种特点使得网络的自我修复能力很强，当数据传输时，路径上的某一节点出现故障，自己能够快速找到其它节点连接从而建立一条新路径。(2)网络拓扑动态变化。在移动Ad Hoc网络中，网络拓扑结构的变化会随着节点的变化而变化，例如
27、，节点受到信道和天气的影响，它的网络拓扑结构就会变化；节点之间移动速度的增大减小、路径的建立和断开都使网络的拓扑结构发生变化，而且这种变化是随机的没有任何规律性。(3)带宽受限。AdHoc是一种无线自组网络，数据的传输是在无线信道中进行的。由于实际生活可以提供的无线信道的带宽较低，加上无线信道容易受到外界干扰变得不稳定，节点之间通讯竞争带宽等各种因素，使得实际的带宽远远低于理论值。(4)安全及服务质量难以保障。在Ad Hoe网络中，节点之间随机的连接而且在无线信道中进行数据传输，这种特点就使得网络容易遭到破坏，传输的数据可能遭到修改或者毁坏，整个网络的安全性就难以保障。(5)多跳路由性。在传统
28、的网路里，传输路由只允许一步路由传输，但是自组网可以多个节点转发数据，在Ad Hoc中每个节点都是平等的，每个节点都可以充当路由而不是和其他网络一样需要有独立的设备完成路由。表21为Ad Hoe网络与现有的无线网络的对比。5万方数据中北大学学位论文表21 Ad Hoc网络与现有的无线网络的对比Ad Hoc网络是由多个可移动节点组成的无线网络，它以无中心节点、节点相互独立、自己能够快速组网、不需要基础设施支持、网络拓扑结构可以随机灵活变化、多跳的路由性、采用分布式的管理系统等特点弥补传统网络中存在的一些缺点，在各领域中发挥着极其重要的作用351。Ad Hoc网络的应用领域主要有：(1)军事应用。
29、在战场上，提前建立好有线网络或者有固定设备的无线网络是不符合实际的情况。无中心、自组织、易搭建的无线网络Ad Hoc就成为最佳的选择，不仅成本低，最主要的符合战场的需求。(2)救援行动。在野外或者紧急突发的现场，又或者是在地震洪水发生的地方，这些地方有的是没有网络通讯，有的是自然灾害破坏当地的通讯设施，那么救援人员可以快速的搭建临时Ad Hoc网络与救援地区进行通讯，实时了解情况，保障救援行动的6万方数据中北大学学位论文顺利完成。(3)传感器网络。对于很多场合，传感器只能使用无线信道进行通讯，不同于分散工作的传感器，把分散的传感器结合在一起组成Ad Hoc网络，通过相互配合协调，在医疗、探测等
30、领域中发挥很大的作用36】。(4)商业应用。随着人们对网络的普及，为方便人们的使用，把Ad Hoc网络与现在的网络相结合。例如：在地铁，和隧道中铺设无线网络。2。12 Ad Hoc网络拓扑结构(1)平面网络。平面网络的网络结构很简单，不需要其它结构进行维护。网络中每一个节点都处于平等地位。两节点之间通信时，随机建立多条可用路径。可供选择的多条路径会改变整个网络的性能，面对不同数据的传输，可以选择不同的路径，这样就会改善网络的堵塞现象。根据图21所示，平面网络中每一个节点都是独立存在，不依赖与其它节点，即使节点自身毁坏，也不会影响到数据的传输，而且也不存在堵塞的节点。在平面结构中，每个节点交换数
31、据都要记录路由信息。随着节点数的增加，路由信息的数量也增加，而且链路断开的可能性也增加，导致网络管理很难实施。总体来说，当Ad Hoc网络中的节点数太多时，平面结构不能很好满足网络的需求。图21网络平面结构(2)分级网络。分级网络划分为单频网络结构和多频网络结构。在单频网络中，网络由多个簇(cluster)组成，各个簇之间通过簇头(clusterheader)或网关进行连接；在多频网络中，网络由多个层组成的，每个层包含多个簇。如图23所示。每个簇(cluster)由一个簇头(clusterheader)和多个簇成员(cluster-member)组成。同一个簇里面的簇成员可以共享路由信息，簇头
32、和网关之间可以互相传递路由信息。例如，X和Y两个簇成员在不同簇中，两者进行通讯，X把信息发送给它的簇头，簇头对信息进行解析找到7万方数据中北大学学位论文Y的簇头，Y的簇头再把信息分解找到Y，把信息传递给Y。如图212所示，在图a中，在单频网络中，所有节点使用同一种频率进行通讯，不同簇之问通讯是各自的簇头通过网关相互转化的。图b多频网络中，每个簇头有两个频率，一个供自己本簇内使用，一个是和其它的簇通信时使用。与平面结构相比，分级网络规模大，可扩展性好，通过分级，把节点局部进行优化管理，减少路由的开销。但是这个分级结构也有很大的缺点，进行数据传输时，使用那种规则来选取合适的簇头进行通讯成为1个难点
33、，如果选择的不合理，就会影响到整个数据的传输。所有信息数据的转发都是通过簇头来完成的，这样就簇头就可能会引起堵塞，造成网络瓶颈。一频率1频率2I)簇-簇头簇成员网关C)簇 簇头 簇成员(a)单频分级网络 (b)多频分级网络图22分级网络综上，当Ad Hoc网络规模较小时，应该选择单频网络，能快速建立，而且结构简单。当网络规模较大时，分级网络良好的扩展性，路由信息局部管理，易于维护等特点更能满足这种需求。22 Ad Hoc网络路由协议221路由协议简介任何网络的最主要的功能都是传输数据，Ad Hoe网络也不例外，所以两个节点通讯时至少有一条可用的路径37】。如图23所示，路由协议的主要功能是：根
34、据实际的业务需求，找到满足条件的路径，从中选择一条最合适的路径传输数据，在数据传输过程中实时的维护这条路径，防止路径断开，数据传输失败。由于Ad Hoe网络的拓扑结构8万方数据中北大学学位论文灵活多变，路由协议必须要及时了解、随时更新路由信息。路由协议性能的高低直接影响到整个网络的性能，所以现在已经成为AdHoc网络研究中热点。路由的功能 I业务需求 自组网的特性麟一攀图23路由协议的功能Ad Hoc网络广泛的应用在实际生活中，但是原来的路由协议不能E,徊11V好满足现实的需求，则设计或者改进已经有的路由协议就成为一种有效的途径。一个好的路由协议必须遵循以下的规则：首先，找到的路径中间节点是不
35、包含源节点，就是不能有环路的存在；其次，尽可能利用现有的网络资源，考虑实际业务的需求；最后，对Ad Hoc网络拓扑变化做出快速反应。在设计路由协议时尽量满足实际生活的需求，符合现在网络的特点。在具体设计和改进过程中，还要考虑到安全机制，单信道的支持等，虽然不能把所有的方面都兼顾到，但是基本的原则必须遵守，更多的加入实际要求，这样设计出的路由协议才会受到使用者青睐。222现有的Ad Hoc网络协议分类自从AdHoc网络进入到人们的生活中，根据实际需要，提出许多AdHoc网络路由协议。比如：提出年代相对较早的经典协议DSDV38】、AODV【39、ZRp40】、TORA41等；近年学术论文中提出的
36、WRP42】、LAR43、zHLS脚】等。依据寻找节点进行通讯路径的方式对Ad Hoc协议进进行分类，现在成为最常见的分类方式。该分类方式分为：主动式(proactive)和响应式(reactive)两种。主动式又称为表驱动路由协议(tabledriven)，其特点是：每个节点都有路径信息的记录，即互通可用的路径，只要自己发生变化，就重新获取到达其它节点的路径，把这些信息同时告诉其它的节点。当源节点去其它节点9万方数据中北大学学位论文需要通信时，才会寻找可以使用的路径。图24路由协议分类(1)表驱动路由协议典型的表驱动路由协议主要由DSDV、WRP等。DSDV(DestinationSeque
37、nceddistanceVector)在BellmanFord算法的基础上进行改进而来。它是无环路距离向量协议，同时也是Ad Hoc协议中最早被提出的表驱动路由协议之一。其特点是：节点之间都互相连接，而且自己的路由表中记录相关信息，同时也要交换信息、维护信息。交换的方式有两种：一种是只要网络的拓扑结构发生变化，就把每个节点到达其它节点的路径等相关信息进行更新，称为完全更新(full dump)；另一种是对于节点移动较少，拓扑结构几乎没有变化，就只会更新变化节点到达其它节点的信息，称为不完全更新(incremental update)。DSDV为避免环路的出现，给每条路由信息设置序列号。设置序列
38、号的目的是为了更好的更新节点的路由信息，当节点收到路由信息时，首先提取出目的序列号与自己存储的目的序列号比较，前者较大时才会更新自己的路由信息。主要缺点：必须通过节点周期性发送广播分组来确定整个网络的连接状态，这样会加重网络的开销，降低网络的性能。WRP(WirelessRoutingprotoc01)是表驱动距离矢量协议，每个节点都要维护距离表、路由表、链路开销表和信息重传列表(MRL)四张表。节点在链路断开或者是重新连接时交换路由信息，并且周期性的维护这些信息。MRL表中记录重传信息的序列号，统计要接收信息节点的数量，节点成功接收到信息的标志，更新整个消息的列表。节点在一段时间内没有转发数
39、据或者是更新消息，就要通过发送HELLO消息来确定节点之间是否连接；当节点收到邻节点更新消息后，也会相应的更新自己的路由列表；当节点第一次收到来自其它节点的HELLO消息，就会把这条记录保存到路由表中。表22，10万方数据中北大学学位论文为DSDV和WRP的比较。表22 DSDV和WRP的比较(2)按需路由协议典型的按需路由协议主要由AODV、DSR、TORA、ABR等。动态源路由协议DSR(DynamicSourceRouting)把源地址作为依据，根据实际业务的需求而建立路径的一种协议。主要是由路由发现(Route Discovery)、路由维护(RouteMaintenance)这两大机
40、制组成。路由发现即当源节点不知道到达目的节点的路径时，通过路由发现找到这条路径；路由维护即当源节点在找到到达目的节点路径并且开始传送数据时，启动路由维护，当发现中间节点断开时，需要源节点重新启动路由发现机制。DSR的路由发现过程，维护过程是根据实际的需要而进行的，它的核心问题是，如何找到到达目的节点的路由。AODV(Ad Hoc OnDemand Distance VectorRouting)是另一种典型的按需路由协议。在AODV中，由路由发现、路由维护、路由修复组成。当节点需要向目的节点传输数据时，首先查看自己的路由信息是否存在到达目的节点的路径，如果存在，就开始传送数据并且同时启动路由维护
41、，如果不存在，则节点就需要向其它节点发起路由请求，其它节点转发这个请求，直到找到目的节点。在这个路由发现过程中，一定会检测中间节点是否是发起请求的节点，同时建立两条路由，正向路由和反向路由。在数据传输的过11万方数据中北大学学位论文程中，可能会出现链路断开的情况，这时候就需要启动路由修复。AODV路由协议的最佳路径的选择是基于最小跳数，而且只有唯一一条从源节点到达目的节点的路径，所以当路径断开时，就会启动新一轮的路由发现。表23常见的按需路由对比(3)两种典型路由协议分析这两个协议之间最大的区别是所获取的网络状态的方式不同。表驱动路由协议常常采用的是有线的思想，监测网络拓扑结构的变化，根据这些
42、变化，监控已经建立好的路径的状态，实时的维护路由信息。最大的优点是，路由表中存在所有节点之间的可用路径，当需要发送数据时，查询路由表即可，传送的延时小。但是缺点也不容忽视，需要建立一张所有节点之间可以进行通讯的路由表，对于节点较多的网络，路由表过于庞大而且建立困难；实时的监控网络，会带来许多没用的信息，这些信息严重浪费网络的带宽、能量，同时也会增加网络堵塞的可能性。按需驱动路由协议采用另外一种思想。其思想是：网络中两个节点通讯时，需要检查自己的路由表，查看是否能找到一条可用的路径到达目的地，如果没有就启动路由发现，寻找路径。在寻找到达目的节点的过程中，采用广播的形式与邻节点建立连接。这种协议的
43、主要缺点是，当源节点和目的节点之间没有可用的路径时，就必须通过路由发现找到路径，数据传输的实时性差。优点是，不用定期的向整个网络发送广播包确定每12万方数据中北大学学位论文个节点是否断开。因此按需驱动路由协议适用于，规模较小而且节点之问传送数据的频率较低的网络。表驱动路由协议适用于，节点的移动速度低而且拓扑结构变化较小的网络。表24表驱动和按需驱动路由协议的比较23 Ad Hoc网络路由协议的OoS保障现在互联网进入人们的生活中，网络中不再是单纯的传输数据，传输视频、图片、语音成为一种普遍的现象，这种现象对Ad Hoc网络提出更多的要求。面对大量多媒体数据的传送，如何提供安全、高效的传输方式成
44、为Ad Hoc研究的重点。通过网络提供QoS保障可在一定程度上改善网络的性能。对于多媒体应用、关键应用中，QoS是网络中必不可少保证实时业务的安全机制。QoS约束参数主要有：延时、丢包率、带宽等。延时是数据从开始节点发送到目的节点接收到数据的时间和，多媒体业务的数据传送量很大，传送时间越长就会给网络带来瓶颈，降低网络的性能。丢包率的大小决定这条路由的可靠性，若丢包率过大会造成数据失真，难以保证实时业务的传输。带宽是指网络传送数据的能力，传输数据所占的带宽越大，到达目的地就会越快。所以把QoS约束参数和Ad Hoc网络的路由协议结合起来，就可以找到源节点到达目的节点的高效路由451。Ad Hoc
45、网络由于网络拓扑结构多变、路由多跳性决定了把Ad Hoc协议和QoS约束参数结合起来设计新的路由是一个难点工作。难点主要体现在：如何选择多约束路由、如何对链路状态信息进行存储和维护、如何具体了解节点的信息等。设计带有QoS约束13万方数据中北大学学位论文的路由协议主要的思想：结合传统无线网络QoS的模型设计新的路由协议；改进现有的路由协议。现在实际中的改进主要表现在如下：(1)混合经典协议。在Ad Hoc网络中，无论单纯的采取哪一种协议都不能很好满足网络的需求，选择两种合适的路由进行混合，可以互补之间的缺点，使得路由选择、路由修复等方面都有明显的改善且能够提供一定的QoS保证。LI“zH DSR和AODV协议相结合后的混合协议DOA46。(2)增加QoS约束。QoS路由不再将跳数作为唯一的参考标准，而是要求同时满足多个相互独立参数的约束条件，在选择路由的时候综合考虑带宽、延时，丢包率等因素，使得最终选出的路径在传输数据时体现出更好的优势。(3)多路径思想。在传输较大的数据时，只采用一条路径或者是依靠几个节点，有可能会导致网络堵塞，造成数据不能及时传输成功。采用多路径思想，数