《舰船编队无线自组织网络路由协议研究硕士研究生学位论文.doc》由会员分享,可在线阅读,更多相关《舰船编队无线自组织网络路由协议研究硕士研究生学位论文.doc(84页珍藏版)》请在三一办公上搜索。
1、学科门类:工 学 单位代码:90006中图分类号:TP915 密 级:公 开硕士研究生学位论文舰船编队无线自组织网络路由协议研究一级学科: 信息与通信工程学科专业: 通信与信息系统 研究方向:宽带网络与交换技术二零零九年三月解放军理工大学学位论文原创性声明本人郑重声明:所呈交的学位论文,是本人在导师指导下,进行研究工作所取得的成果。除文中已经注明引用的内容外,本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体,均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。研究生签名: 年 月 日摘 要舰船编队
2、自组织网络是Ad Hoc网络技术的典型应用之一,具有拓扑规律性变化、业务流量分布不均衡、特殊的物理信道等不同于一般Ad Hoc网络的特点,这些特点使一般的路由协议很难适应舰船编队网络的应用需要。本论文在现有研究的基础上,以舰船编队网络应用为背景,设计了一个混合式的路由协议,并针对舰船编队网络的突出的负载均衡问题进行深入的研究,提出了一种负载均衡算法。论文的研究工作主要体现在以下几点:1、设计了一种适用于舰船编队自组织网络的路由协议。协议采取了拓扑变化感知和路由缓存保持策略提高路由质量;引入了多点中继机制限制路由控制分组的广播;融合跨层设计思想减小路由开销。从而降低了协议对网络资源的占用,提高网
3、络的性能。2、设计了一种简单高效的负载感知方法。在这种方法中,节点用物理信道的忙闲比例来表征网络的负载状态,不仅对网络的负载状态描述准确,而且不需要增加网络开销,具有很好的适用性。3、设计了一种基于历史信息和概率路由准入的负载调度算法。节点根据历史负载信息和概率算法进行路由准入的判断,完成对负载的均衡调度。算法具有自学习、自适应的特点,在没有增加任何网络开销的基础上,能够对网络中的负载进行动态准确的调度,且算法对各种反应式路由协议都具有很好的适应性。4、在Qualnet仿真平台上实现了适用于舰船编队网络的路由协议和负载均衡算法,并对协议和算法进行了详细的仿真分析,验证了协议和算法的有效性与适用
4、性。在Qualnet仿真平台上对协议和算法的仿真表明,论文所设计的路由协议能够很好的适应舰船编队网络的特点,较好的满足应用需要,相比于主流的DSR和ZRP协议,舰船编队网络的路由协议在丢包率、时延和路由开销等方面均具有明显的优势;论文所设计的负载均衡算法能够很好的解决舰船编队网络的负载均衡问题,在网络吞吐量和时延等方面提升网络的性能,性能提升最大分别达到10%和20%。本论文的研究成果对Ad Hoc网络路由协议的研究具有较高的参考价值。关键词:Ad Hoc网络;路由协议;拓扑;负载均衡;丢包率;时延;吞吐量;AbstractThe fleet group self-organizing net
5、work is a typical application of Ad Hoc networks technology. The application has some specific characteristics such as topology changing regularly、traffic flow distribution unbalanced、special physical channel and so on. These characteristics make the general routing protocol be very difficult to mee
6、t the needs of the application. In this paper, on the basis of existing research, we design a hybrid routing protocol and conduct in-depth research on the prominent problem in the fleet group self-organized network. Then we proposed a kind of load balance routing algorithm. The main work of the pape
7、r is as follows:1、A routing protocol is designed for the fleet group self-organized network. We adapt topology change sensation and routing cache holding mechanism to improve the quality of routing; introduce the mechanism of MPR to limit the broadcasting of routing control packet; integrate the cro
8、ss-layer idea to reduce routing overhead. We adapt these measures to reduce the waste of the routing protocol and to make the network effectively.2、One simple and efficient load sensation method is designed. In this method, the node attributes the load state of the network with physical channel idle
9、 portion .This method is not only accurate for the network, moreover it does not need to increase extra overhead, and it has very good applicability. 3、We design a load balance algorithm based on historical information and route admittance judged by probability. The node judges whether to accept new
10、 route request by historical information and probability algorithm. The algorithm has the characteristics of self-studying and self-adapting, and it can balance the network load dynamically and accurately with no extra overhead. Also the algorithm is suitable for other reactive routing protocols.4、W
11、e implement the routing protocol and the algorithm which is designed for fleet group network with Qualnet simulation platform, and we simulate the protocol and algorithm in detail to verify the accuracy and adaptation.The simulation of the protocol and algorithm on the simulation platform shows that
12、 the protocol designed in the paper is suitable for fleet group self-organizing network and can meet the needs of application. Compared to DSR and ZRP protocol ,the protocol designed has obvious advantages on aspect of packet lost rate、end to end delay and routing overhead; the load balance algorith
13、m designed in the paper can solve the problem of load balance and improve the performance of the network on throughput and end to end delay to 10% and 20% separately at most. The research result of the paper will offer valuable reference to Ad Hoc network routing protocol.XXXX(Communications and Inf
14、ormation Systems)Directed by Prof. XXXXKey words: Ad hoc network, routing protocol, topology, load balance, packet lost rate, end to end delay, network throughput.目录摘 要IAbstractII目录III图清单V表清单VI第一章 绪论11.1课题来源及背景11.2本课题研究的目的和意义11.3相关技术及研究现状21.4论文的主要工作41.5论文的内容组织5第二章 MANET中的路由协议72.1引言72.2先应式路由协议82.2.1
15、WRP14路由协议82.2.2 DSDV15路由协议92.2.3 FSR16路由协议102.2.4 OLSR17路由协议112.3 反应式路由协议122.3.1 DSR18路由协议132.3.2AODV19路由协议142.3.3TORA20路由协议152.4混合式路由协议152.4.1ZRP21路由协议162.4.2SHARP22路由协议162.5几类路由协议的比较172.6小结18第三章 舰船编队无线自组织网络的路由协议设计193.1引言193.2舰船编队网络的场景特点193.3协议设计203.3.1协议设计思想203.3.2近距离路由规则203.3.3中远距离路由规则213.3.4差错处理
16、263.3.5协议的跨层交互263.4仿真及分析273.4.1仿真平台介绍273.4.2HSRP协议的仿真实现283.4.3仿真设置283.4.4协议性能分析313.5小结36第四章 负载均衡路由协议研究374.1引言374.2负载均衡问题的提出374.3当前负载均衡路由协议研究374.3.1负载感知方法384.3.2负载调度策略394.3.3典型的负载均衡路由协议414.4负载均衡算法及协议设计434.4.1基于信道负荷的负载感知434.4.2基于历史信息和概率路由准入的负载调度454.4.3协议设计494.5仿真分析564.5.1负载感知性能分析564.5.2路由准入负载均衡性能分析594
17、.5.3基于概率函数的路由准入性能分析614.5.4协议性能分析634.6小结65第五章 结束语675.1论文工作总结675.2下一步工作68在学期间的研究成果69参考文献71图清单图2.1 路由波动问题示例图10图2.2 FSR路由协议“鱼眼”图11图2.3 OLSR路由更新过程12图2.4 DSR路由过程14图2.5 ZRP半径为2的路由区域16图2.6 SHARP的区域调整示意图17图3.1 源节点反应式路由流程22图3.2 中间节点源路由流程23图3.3 拓扑变化前的节点分布24图3.4 拓扑变化之后节点分布25图3.5 拓扑变化时间26图3.6 网络层与MAC层接口设计27图3.7
18、MAC协议时帧图30图3.8 路由开销32图3.9 路由平均跳数32图3.10 丢包率33图3.11 时延34图3.12 路由开销 图3.13平均跳数34图3.14 丢包率 图3.15 时延35图3.16 路由开销 图3.17 平均跳数35图3.18 丢包率 图3.19 时延35图4.1 缓存数据量与节点竞争关系44图4.2 信道负荷44图4.3 路由建立阶段的路由准入45图4.4 节点的移动与节点的负载47图4.5 路由准入示意图48图4.6 信道时间占用描述49图4.7 网络瓶颈节点55图4.8 信道繁忙比例与RREQ丢弃概率函数关系57图4.9 网络吞吐量曲线58图4.10 平均端到端时
19、延曲线59图4.11基于概率与基于门限的路由准入网络吞吐量60图4.12 基于概率与基于门限路由准入的平均端到端时延图61图4.13 不同函数曲线对应的网络吞吐量62图4.14 不同函数曲线对应的平均端到端时延63图4.15 负载均衡的HSRP与HSRP协议吞吐量64图4.16 负载均衡的HSRP与HSRP时延64表清单表2.1 WRP路由表条目格式9表2.2 各类路由协议比较18表2.3 先应式路由协议比较18表2.4 反应式路由协议比较18表3.1 仿真参数设置29表4.1 典型负载均衡路由协议42表4.2 仿真配置56表4.3 信道繁忙比例与路由准入概率57表4.4 仿真配置59第一章
20、绪论1.1课题来源及背景随着人们对移动通信需求的增大,Ad Hoc网络1技术得到了迅速的发展。Ad Hoc网络是一组带有无线收发装置的移动终端组成的一个多跳的临时性自治系统。Ad Hoc网络具有铺设简单、鲁棒性强、不需要基础设施等优点,被广泛应用在抢险救灾、临时会议、MESH网络以及军事应用等诸多方面。舰船编队自组织网络就是Ad Hoc网络的典型应用之一。舰船编队网络中,舰船之间的通信大部分在水面上进行,离陆地较远而无法应用地面上已有的通信基础设施,所以在每次完成任务时,需要在舰船之间建立一个临时的分布式网络,以满足编队舰船之间的通信需要。而Ad Hoc网络的特点特别适合舰船编队网络的应用,能
21、够为舰船编队提供有力的通信支撑。在Ad Hoc网络中,由于物理信道带宽窄和拓扑变化频繁等因素的影响,路由协议相比有线网络中有很大的不同,Ad Hoc网络中的路由协议的设计面临很大的挑战。而舰船编队网络中的路由协议作为通信网络的重要组成部分,其设计除了考虑一般无线信道的环境特点之外,还要考虑对舰船编队应用所特有的因素带来的影响。本课题的研究建立在舰船编队网络应用基础之上,论文针对应用的场景特点设计了一种适用于舰船编队网络的混合式路由协议,以满足舰船编队通信的需要;同时,论文分析研究了影响舰船编队网络通信效率的重要问题-负载均衡问题,该问题也广泛存在于其它Ad Hoc网络应用中,并提出一种负载均衡
22、算法来解决网络拥塞导致的网络性能降低问题,同时该算法也具有广泛的适用性。1.2本课题研究的目的和意义作为Ad Hoc网络的典型应用之一,舰船编队网络在物理信道、移动模型、流量模型等方面有自己的特征,这些特征使其有别于一般的Ad Hoc网络场景,同时也对路由协议的设计提出了新的要求。所以,尽管国内外学者已经对Ad Hoc网络的路由协议进行了大量的研究,提出了很多适用的、有价值的协议和算法,但是这些协议和算法难以满足舰船编队网络的通信需求、或者说不能很好的适应舰船编队网络。因此,有必要在现有路由协议研究的基础上,针对舰船编队网络的特点设计一个适用于舰船编队网络的路由协议。研究舰船编队网络的应用特点
23、可以发现,舰船编队网络通信中存在着较为突出的负载均衡问题。通常舰船编队中会有一艘舰船作为编队的指挥,我们称之为旗舰,其它舰船可称之为僚舰。由于旗舰要指挥协调整个舰队的运行与工作,而各僚舰也经常需要把各种信息汇报给旗舰,所以旗舰相对于僚舰具有更大的通信业务量。通信业务上的这一特点使网络中存在明显的负载不均衡现象,旗舰附近网络的负载较重,而其他节点业务量相对较轻。事实上不仅是舰船编队的Ad Hoc网络中存在负载分布不均衡问题,其它Ad Hoc网络应用中也都普遍存在负载分布不均衡问题,而且这些问题绝大多数都与路由协议有关,在路由协议中设计负载均衡算法也成为路由协议的一个重要功能。所以对路由协议中的负
24、载均衡技术进行广泛深入的研究,解决由负载分布不均导致的网络拥塞,具有非常重大的意义。虽然本课题的研究建立在舰船编队网络应用的背景下,但是论文提出的路由协议同样可以应用在其它类似的具有编队特点的Ad Hoc网络中;同样,论文提出的负载均衡算法也具有普遍适用性,可以用在其它反应式的路由协议中。1.3相关技术及研究现状Ad Hoc网络的无中心、自组织、分布式、多跳转发等特点,使它具有无需网络基础设施、可快速临时组网、系统抗毁性强等突出优点,应用前景广阔。移动自组网(MANET,Mobile Ad hoc Network)和无线传感器网络(WSN,Wireless Sensor Network)是Ad
25、 Hoc网络的两个重要分支,面向不同应用。移动自组网主要面向“人与人”之间的移动通信,最早源自军事移动通信。移动自组网技术的起源可追溯到1968 年的ALOHA项目和1972年的PRNET 网络。1968 年,美国夏威夷大学为了将分布在四个岛屿的七处校园内的计算机之间互连,构建了第一个无线自组网ALOHA 2系统。在该网络中,计算机不能移动,相互之间一跳可达。该项目首先研究了共享无线媒介的多站点接入信道问题,提出了著名的ALOHA 协议。1972 年,夏威夷大学在美国国防部预先研究计划局(DARPA,Defence Advanced Research Projects Agency)的支持下,
26、开发了支持节点移动的分组无线电网络PRNET(Packet Radio Networks)3。PRNET 允许在一个更广的地理范围内,采用分组多跳存储转发方式进行通讯。PRNET 设计时希望网络的形成无需人工干预,系统能自动初始化和自动运行。这意味着网络节点能够发现邻居节点,并根据这些邻居节点形成路由。1983 年,DARPA资助进行了具有抗毁性和自适应的无线网络SURAN项目(Survivable Adaptive Radio Networks)4。该项目重点解决以下三个关键技术问题:当时的无线通信装置体积大,功率大,成本高;组网算法虽然在小规模网络上得到验证,但是无法支持大规模网络;网络抗
27、电子干扰能力差。该项目研制出低成本的分组无线电电台LPR。基于 LPR 平台,研究人员提出一种基于分层链路状态路由协议,以支持大规模网络。美国海军研究实验室于 20 世纪 70 年代末研制完成了短波自组织网络 HF-ITF5 系统,该系统能够保障海军舰队在 500 公里范围的舰只、飞机、潜艇相互之间进行联网。系统工作在短波频段,是采用跳频方式组网的低速自组织网络。二十世纪九十年代初期,随着移动通信和移动终端技术的高速发展,Ad Hoc网络技术不但在军事通信领域得到充分发展,而且在民用通信领域也得到应用。因特网的成功推动了将全球信息基础设施扩展到移动无线环境的进程。1993 年,美国国防部启动近
28、期数字无线电台(NTDR, Near-term Digital Radio)6计划,目标是研制支持 IP 数据业务的战术无线电台。基于该电台可自组织成两层的Ad Hoc 网络。网络分为若干簇,每个簇由一个簇首和若干簇成员组成,各簇首构成一个骨干网。NTDR 配置到美军旅及旅以下部队战术作战中心,是目前少数的“实际”使用的 Ad Hoc 网络之一。1994 年,美国DARPA启动全球移动信息系统(GloMo)计划,目标是为移动用户提供信息服务,使移动无线环境成为国防信息基础设施的重要组成。WINGs(Wireless Internet Gateways)7是 GloMo 计划中的一个项目,主要目
29、标是在 IP 层完成路由功能,实现Ad Hoc网络与多媒体因特网的无缝结合。各种基于无线和红外技术通信设备的广泛出现和便携计算机的流行,产生了移动终端互连的需求,为Ad Hoc网络的应用提供了广阔空间。1994 年,C.E.Perkins 和D.B.Johnson提出了对个人便携设备进行无需基础设施支持的组网思想,并对相应的路由算法进行了探索。这标志着移动自组网技术开始从军事通信领域转向民用通信领域。进入二十一世纪后,Ad Hoc网络的一个重要发展方向是无线传感器网络(Wireless Sensor Network)8。无线传感器网络主要面向“物与物、人与物”之间的信息交互,是由部署在监测区域
30、内大量的廉价微型传感器节点组成,通过无线通信方式形成的一个多跳的、自组织的网络系统,其目的是协作地感知、采集和处理网络覆盖范围内感知对象的信息,并传送给信息获取者。由于大量微小传感器节点随机分布,每个节点传输功率非常有限,因此只能采用Ad Hoc网络技术进行组网通信。2001 年,美国国防部预先研究计划局启动 SensIT(Sensor Information Technology)计划9,该计划研究的关键技术包括:如何以战场为背景,让传感器节点通过自组织方式完成网络的快速部署;如何从部署的传感器网络收集有用的、可靠的、实时战场态势信息。该计划要求 SensIT 网络具有交互和编程能力,适应动
31、态任务部署和查询;具有多任务能力,允许多用户同时使用;具有精确的感知和跟踪能力。同年,美国陆军提出“灵巧传感器网络通信”计划。目标是在战场上部署大量传感器以收集信息,对相关原始数据初步融合后,再把重要信息传送到各数据融合中心,将大量信息集成战场全景图,提高美军战场态势的感知能力。2002 年,美国 Sandia 国家试验室与美国能源部合作,共同研究能够尽早发现以地铁、车站等场所为目标的生化武器袭击,并及时采取防范对策的系统。同年,INTEL公司发布“基于微型传感器网络的新型计算发展规划”,宣称将致力于微型传感器网络在预防医学、环境监测、森林灭火,乃至海底板块调查、行星探测等领域的应用。目前,无
32、线传感器网络作为信息领域的一个全新方向,引起了学术界的广泛关注。近年来各国学者在移动自组网和无线传感器网络方面的研究有力促进了Ad Hoc网络的发展,而各种应用系统又对Ad Hoc网络的进一步研究提供了有价值的参考。但纵观现存的Ad Hoc网络系统,其与具体应用的关系都很紧密。每个Ad Hoc系统都有自己相对独特应用背景与特点,这使得Ad Hoc网络系统一般很难直接进行移植使用。针对一个新的应用场景,往往都要根据具体情况来进行网络的规划与设计。而舰船编队网络作为Ad Hoc网络的一个典型应用,其相关研究还处于起步阶段。一方面水面上的舰船通信研究相对较少,另一方面由于组织模式以及物理设备之间的差
33、异,其它Ad Hoc网络系统对于舰船编队网络研究的借鉴意义有限。本课题研究的路由协议为舰船编队网络的建设提供有价值的参考。1.4论文的主要工作论文首先总结了舰船编队网络的应用特点,说明为舰船编队网络设计一个路由协议的价值和意义。在对现有研究成果进行总结和分析之后,论文以舰船编队网络应用为背景,提出并设计了一种混合式路由协议;然后针对舰船编队网络中突出的负载均衡问题进行了研究,提出了基于信道负荷的负载感知和基于历史信息概率准入的负载调度算法。最后在Qualnet仿真平台上分别对路由协议和负载均衡算法进行了仿真验证。仿真结果表明论文设计的路由协议能够较好的适应舰船编队网络的特点,在丢包率、时延、协
34、议开销等诸多方面优于DSR和ZRP等现有的协议;论文设计的负载均衡算法能够有效的解决舰船编队网络中负载分布不均带来网络拥塞,显著的提高了网络在吞吐量和时延等方面的性能。本论文设计的路由协议和负载均衡算法,具有以下创新点:1、结合舰船编队网络的拓扑变化特点,提出了拓扑变化感知和路由缓存机制,减少路由开销和数据的路由时延。2、设计了一种基于信道负荷的负载感知方法,能够在不占用网络资源的基础上对网络的负载状态进行准确的映射。3、设计了一种基于历史信息和概率路由准入的负载调度算法,算法不需要增加任何的开销、不需要改变数据的格式,完全分布式的完成负载的调度,很大程度上避免和减少网络拥塞。1.5论文的内容
35、组织本论文的组织结构如下:第一章 绪论。首先介绍课题的背景、来源及意义,然后阐述了课题的相关研究和技术,最后概括论文的主要工作;第二章 MANET中的路由协议。首先对路由协议的发展现状进行简要的介绍,然后对典型的路由协议进行较为详尽的分析和介绍;第三章 舰船编队无线自组织网络的路由协议设计。首先对舰船编队网络场景的特点进行了归纳,然后针对这些特点设计了一个适用于舰船编队无线自组织网络的路由协议(HSRP),并对协议设计的关键问题进行详细的阐述,最后对路由协议的性能进行仿真和分析;第四章 负载均衡路由协议研究。首先是负载均衡的提出以及介绍相关研究热点,然后设计了一种适用于反应式路由协议的负载均衡
36、算法,最后对该算法进行详细的仿真和分析得到结论。第五章 结束语。对论文的工作进行总结,并指出下一步将要完成的工作。第二章 MANET中的路由协议2.1引言Ad Hoc网络是一个临时的自治系统,网络中的移动终端兼具传统意义上终端和路由器的功能,网络中的节点处在对等地位,而且网络中没有中心节点协调网络的运行。这些都使得Ad Hoc网络技术比传统有线网要复杂的多,Ad Hoc网络技术涉及到OSI分层10模型中的每个层面。研究者已经在媒质接入、路由、功率控制、QoS、安全等方面发布了相关的研究成果10-12。在众多的研究中,Ad hoc网络的路由问题尤其关键,IETF已经成立了MANET工作组集中从事
37、Ad hoc网络路由协议及其性能评定的研究。Ad Hoc网络中的特点使Ad Hoc网络中的路由协议设计比有线网面临更多的困难和更大的挑战,主要表现在以下几个方面:1、动态拓扑:动态变化的网络拓扑是Ad Hoc网络的一个显著特点。由于通信终端的随机移动、无线发信装置发送功率的变化、无线信道间的互相干扰以及地形等综合因素的影响,移动终端间通过无线信道形成的网络拓扑结构随时都有可能发生变化,而且变化的方式和速度都是不可预测的。2、多跳组网:所谓“跳数”是指经过路由器的个数。Ad Hoc网络中,由于节点的通信距离有限,分组通常都要经过多个路由器进行中继才能到达目的地。因此,Ad Hoc网络是一个多跳网
38、络,这与无线局域网的单跳有很大的区别。多跳的特点给工作在同频段的终端节点带来了“隐藏终端”“暴露终端”等问题13,对网络的性能产生重要影响。3、分布式控制:Ad Hoc网中用户终端的地位平等,不存在中心控制点,组成一个对等式网络,其中的节点可以随时加入和离开网络,每个节点都分布式的寻找到目的节点的路由。4、无线广播信道:Ad Hoc网络中使用的是无线信道,无线信道具有天然的广播特性,并且它所能提供的网络带宽相比于有限信道要低得多,质量也差得多。考虑到竞争共享无线信道产生的冲突、信号衰减、噪音和信道之间干扰等因素,移动终端获得的实际带宽远远小于理论上的最大值,并且会随时间动态地发生变化。5、单向
39、信道的存在:单向信道是指存在单向链路的信道。由于各无线终端发射功率的不同以及地形环境的影响,Ad Hoc网络中可能产生单向链路,使相邻两个节点只能进行单向通信。到目前为止,已经针对Ad Hoc网络开发出了许多的路由协议,其分类可以采用多种方法,一般从不同的角度将Ad Hoc网络路由协议按照以下四种方式分类:(1)主动型(Proactive)和反应型(Reactive);(2)平面型(Flat)和层次型(Hierarchical);(3)GPS辅助型(GPS Assisted)和非GPS辅助(Non GPS Assisted)型路由协议;(4)单路径型(Single-Path)和多路径型(Mul
40、ti-Path)。这些分类方法的着眼点不同,在具体的路由协议设计过程中,可以采用单一策略,也可以同时采用多种策略,如反应型的GPS辅助多路径路由协议等。虽然路由协议的分类不同,但是归纳起来各种路由协议所针对的核心问题都是围绕着如何控制路由开销、提高收敛速度、增强拓扑感知能力以及避免路由环路等方面展开的。目前主流的分类方法是依据网络中节点获取路由的方式和时机的不同而分为先应式(或称主动式)、反应式(或称被动式)以及混合式三大类,下面将对这三种协议分别加以介绍。2.2先应式路由协议先应式路由协议又称表驱动协议,其路由信息的获取方式与有线网类似,一般是采用节点周期性动态洪泛的方式,将距离矢量或者链路
41、状态信息通告给网络中的其它节点,从而使网络中的节点获取网络路由信息。先应式协议的主要代表有WRP14、DSDV15、FSR16、OLSR17协议等。2.2.1 WRP14路由协议WRP(Wireless Routing Protocol)协议即无线路由协议,是一种基于距离矢量的表驱动路由协议。WRP利用bellman-ford的基本算法通告距离矢量信息来维护路由表,每个节点保存在路由表中的信息如下:距离、路由、链路开销和重传计数器、每一个节点正确应答所需的标识和更新消息的更新列表(MRL)等。MRL记录关于消息序列号、重传计数器、每一个邻节点正确应答所需的标识和更新消息的列表等信息。这就使得节
42、点可以决定何时发送更新消息以及发送给哪个节点。更新消息包括目的节点的地址、到目的节点的距离和目的节点的上游节点,然后邻节点就可以修改自己的路由表并试图建立新的路由。由于无线链路的特性或网络拥塞,更新分组可能丢失或者过期,需要采用重传机制来保证更新分组的可靠传输。节点正确地收到更新分组之后需要发送一个ACK进行确认。如果节点没有转发数据分组或者更新消息,则要定期发送HELLO分组,以确保节点间的连通性。节点在一段时间内没有收到邻节点发送的任何分组,就认为和该节点的链路失败。表2.1 WRP路由表条目格式Dest idDistancePredecessorSuccessorTagWRP协议中,节点
43、为每个目的节点保存一个路由条目。表2.1所示为节点i到目的节点j的路由条目。Dest id:目的节点j的id。Distance:i到目的节点j的距离。Predecessor:节点i到目的节点j的最短路径上j的上一跳节点。Successor:节点i到目的节点j的最短路径上的i的下一跳节点。Tag:标志位,标志节点i和j之间的路由无环路、有环路和无路由。WRP协议中,通过路由表中的Successor位可以解决距离矢量算法中的无穷计算问题。同时,为了限制路由信息周期性发送所带来的网络开销,WRP的拓扑更新采用周期触发和事件触发相结合的方式。即节点在发现链路故障后主动发起拓扑更新消息,而在无故障的情况
44、下以较小的频度周期发送拓扑更新消息。2.2.2 DSDV15路由协议另外一种先应式路由协议为DSDV(Destination-Sequenced Distance-Vector Routing)协议,该协议是一种基于bellman-ford算法的距离矢量协议。每个节点都维护一张路由表,表中记录到其他节点的路由信息,包括目的节点的标识以及距离(即跳数,Number of Hops),当节点发现目的节点不可达时,将距离设为无穷大。DSDV与有线网络中的距离矢量协议大致相同,但是增加了目的节点序号的记录、路由增量的更新和延时路由表更新等策略。DSDV中主要是通过在拓扑更新消息中引入序列号的机制来区分
45、路由的新旧,节点收到路由更新之后,比较其中的目的节点序列号和自己保存的同一目的节点的序列号,如果前者大,就更新自己的路由;如果路由序列号相同,则选择具有较少跳数的路由。DSDV协议中通过延时路由表更新的策略防止路由表的波动。在如图2.1所示的网络中,节点B有一条路由经12跳到达节点A,节点C有一条11跳到达节点A的路由,且节点D先收到节点B的路由更新分组,经过10s后又收到节点C的路由更新分组。如果节点D一收到B的路由更新分组就更新自己的路由表,并广播路由更新分组,则在图2.1所示的情况下,节点D在短短的10s内就更新了两次路由表,并且还广播了很多路由更新分组。这就是路由表波动问题。图2.1
46、路由波动问题示例图在DSDV中采用触发更新和稳定时间机制来解决此类问题。当节点收到新的路由信息时,可分为两种情况:一是链路失败,二是调整已存在的路由。对于第一种情况需要立即发送路由更新分组,这就是所谓的触发更新;而对于第二种情况则需要等待一段时间再发送路由更新分组,这就是所谓的稳定时间机制。2.2.3 FSR16路由协议FSR(Fisheye State Routing)协议是一种先应式链路状态协议,但是其综合采用了距离矢量和链路状态两种协议思想。其来源于基于全局链路状态的GSR(Global State Routing)协议,并在拓扑更新和路由维护方面进行了改进。FSR协议中每个节点通过几张
47、表来维护一张网络拓扑图,包括邻居表、拓扑表、下一跳表和距离表,用来计算到目的节点的最短路径。FSR协议中节点周期性地发送链路状态分组来更新路由表,但是不同于一般的链路状态协议,FSR协议的链路状态分组仅在邻节点之间交换,而普通的链路状态协议采用全网广播的方法。为降低链路状态信息通告开销,FSR利用距离长度限制路由表项的更新频度。跳数较远的路由表项被包含在拓扑更新消息中的频度较小,反之较大,这样就控制了路由信息占用的开销,节省了部分网络资源。FSR协议的拓扑结构如图2.2所示,由于其拓扑结构像鱼的眼睛,所以称之为FSR(Fisheye State Routing,鱼眼协议)。图2.2 FSR路由协议“鱼眼”图2.2.4 OLSR17路由协议OLSR(Optim