舰船编队无线自组织网络毕业论文.doc

舰船编队无线自组织网络毕业论文目录摘 要IAbstractII目录III图清单V表清单VI第一章 绪论11.1课题来源及背景11.2本课题研究的目的和意义11.3相关技术及研究现状21.4论文的主要工作41.5论文的内容组织5第二章 MANET中的路由协议72.1引言72.2先应式路由协议82.2.1 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差错处理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.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 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 平均端到端时延曲线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第一章 绪论1.1课题来源及背景随着人们对移动通信需求的增大，Ad Hoc网络1技术得到了迅速的发展。Ad Hoc网络是一组带有无线收发装置的移动终端组成的一个多跳的临时性自治系统。Ad Hoc网络具有铺设简单、鲁棒性强、不需要基础设施等优点，被广泛应用在抢险救灾、临时会议、MESH网络以及军事应用等诸多方面。舰船编队自组织网络就是Ad Hoc网络的典型应用之一。舰船编队网络中，舰船之间的通信大部分在水面上进行，离陆地较远而无法应用地面上已有的通信基础设施，所以在每次完成任务时，需要在舰船之间建立一个临时的分布式网络，以满足编队舰船之间的通信需要。而Ad Hoc网络的特点特别适合舰船编队网络的应用，能够为舰船编队提供有力的通信支撑。在Ad Hoc网络中，由于物理信道带宽窄和拓扑变化频繁等因素的影响，路由协议相比有线网络中有很大的不同，Ad Hoc网络中的路由协议的设计面临很大的挑战。而舰船编队网络中的路由协议作为通信网络的重要组成部分，其设计除了考虑一般无线信道的环境特点之外，还要考虑对舰船编队应用所特有的因素带来的影响。本课题的研究建立在舰船编队网络应用基础之上，论文针对应用的场景特点设计了一种适用于舰船编队网络的混合式路由协议，以满足舰船编队通信的需要；同时，论文分析研究了影响舰船编队网络通信效率的重要问题-负载均衡问题，该问题也广泛存在于其它Ad Hoc网络应用中，并提出一种负载均衡算法来解决网络拥塞导致的网络性能降低问题，同时该算法也具有广泛的适用性。1.2本课题研究的目的和意义作为Ad Hoc网络的典型应用之一，舰船编队网络在物理信道、移动模型、流量模型等方面有自己的特征，这些特征使其有别于一般的Ad Hoc网络场景，同时也对路由协议的设计提出了新的要求。所以，尽管国内外学者已经对Ad Hoc网络的路由协议进行了大量的研究，提出了很多适用的、有价值的协议和算法，但是这些协议和算法难以满足舰船编队网络的通信需求、或者说不能很好的适应舰船编队网络。因此，有必要在现有路由协议研究的基础上，针对舰船编队网络的特点设计一个适用于舰船编队网络的路由协议。研究舰船编队网络的应用特点可以发现，舰船编队网络通信中存在着较为突出的负载均衡问题。通常舰船编队中会有一艘舰船作为编队的指挥，我们称之为旗舰，其它舰船可称之为僚舰。由于旗舰要指挥协调整个舰队的运行与工作，而各僚舰也经常需要把各种信息汇报给旗舰，所以旗舰相对于僚舰具有更大的通信业务量。通信业务上的这一特点使网络中存在明显的负载不均衡现象，旗舰附近网络的负载较重，而其他节点业务量相对较轻。事实上不仅是舰船编队的Ad Hoc网络中存在负载分布不均衡问题，其它Ad Hoc网络应用中也都普遍存在负载分布不均衡问题，而且这些问题绝大多数都与路由协议有关，在路由协议中设计负载均衡算法也成为路由协议的一个重要功能。所以对路由协议中的负载均衡技术进行广泛深入的研究，解决由负载分布不均导致的网络拥塞，具有非常重大的意义。虽然本课题的研究建立在舰船编队网络应用的背景下，但是论文提出的路由协议同样可以应用在其它类似的具有编队特点的Ad Hoc网络中；同样，论文提出的负载均衡算法也具有普遍适用性，可以用在其它反应式的路由协议中。1.3相关技术及研究现状Ad Hoc网络的无中心、自组织、分布式、多跳转发等特点，使它具有无需网络基础设施、可快速临时组网、系统抗毁性强等突出优点，应用前景广阔。移动自组网（MANET，Mobile Ad hoc Network）和无线传感器网络（WSN，Wireless Sensor Network）是Ad Hoc网络的两个重要分支，面向不同应用。移动自组网主要面向“人与人”之间的移动通信，最早源自军事移动通信。移动自组网技术的起源可追溯到1968 年的ALOHA项目和1972年的PRNET 网络。1968 年，美国夏威夷大学为了将分布在四个岛屿的七处校园内的计算机之间互连，构建了第一个无线自组网ALOHA 2系统。在该网络中，计算机不能移动，相互之间一跳可达。该项目首先研究了共享无线媒介的多站点接入信道问题，提出了著名的ALOHA 协议。1972 年，夏威夷大学在美国国防部预先研究计划局(DARPA，Defence Advanced Research Projects Agency)的支持下，开发了支持节点移动的分组无线电网络PRNET(Packet Radio Networks)3。PRNET 允许在一个更广的地理范围内，采用分组多跳存储转发方式进行通讯。PRNET 设计时希望网络的形成无需人工干预，系统能自动初始化和自动运行。这意味着网络节点能够发现邻居节点，并根据这些邻居节点形成路由。1983 年，DARPA资助进行了具有抗毁性和自适应的无线网络SURAN项目(Survivable Adaptive Radio Networks)4。该项目重点解决以下三个关键技术问题：当时的无线通信装置体积大，功率大，成本高；组网算法虽然在小规模网络上得到验证，但是无法支持大规模网络；网络抗电子干扰能力差。该项目研制出低成本的分组无线电电台LPR。基于 LPR 平台，研究人员提出一种基于分层链路状态路由协议，以支持大规模网络。美国海军研究实验室于 20 世纪 70 年代末研制完成了短波自组织网络 HF-ITF5 系统，该系统能够保障海军舰队在 500 公里范围的舰只、飞机、潜艇相互之间进行联网。系统工作在短波频段，是采用跳频方式组网的低速自组织网络。二十世纪九十年代初期，随着移动通信和移动终端技术的高速发展，Ad Hoc网络技术不但在军事通信领域得到充分发展，而且在民用通信领域也得到应用。因特网的成功推动了将全球信息基础设施扩展到移动无线环境的进程。1993 年，美国国防部启动近期数字无线电台（NTDR， Near-term Digital Radio）6计划，目标是研制支持 IP 数据业务的战术无线电台。基于该电台可自组织成两层的Ad Hoc 网络。网络分为若干簇，每个簇由一个簇首和若干簇成员组成，各簇首构成一个骨干网。NTDR 配置到美军旅及旅以下部队战术作战中心，是目前少数的“实际”使用的 Ad Hoc 网络之一。1994 年，美国DARPA启动全球移动信息系统（GloMo）计划，目标是为移动用户提供信息服务，使移动无线环境成为国防信息基础设施的重要组成。WINGs(Wireless Internet Gateways)7是 GloMo 计划中的一个项目，主要目标是在 IP 层完成路由功能，实现Ad Hoc网络与多媒体因特网的无缝结合。各种基于无线和红外技术通信设备的广泛出现和便携计算机的流行，产生了移动终端互连的需求，为Ad Hoc网络的应用提供了广阔空间。1994 年，C.E.Perkins 和D.B.Johnson提出了对个人便携设备进行无需基础设施支持的组网思想，并对相应的路由算法进行了探索。这标志着移动自组网技术开始从军事通信领域转向民用通信领域。进入二十一世纪后，Ad Hoc网络的一个重要发展方向是无线传感器网络（Wireless Sensor Network）8。无线传感器网络主要面向“物与物、人与物”之间的信息交互，是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的、自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖范围内感知对象的信息，并传送给信息获取者。由于大量微小传感器节点随机分布，每个节点传输功率非常有限，因此只能采用Ad Hoc网络技术进行组网通信。2001 年，美国国防部预先研究计划局启动 SensIT(Sensor Information Technology)计划9，该计划研究的关键技术包括：如何以战场为背景，让传感器节点通过自组织方式完成网络的快速部署；如何从部署的传感器网络收集有用的、可靠的、实时战场态势信息。该计划要求 SensIT 网络具有交互和编程能力，适应动态任务部署和查询；具有多任务能力，允许多用户同时使用；具有精确的感知和跟踪能力。同年，美国陆军提出“灵巧传感器网络通信”计划。目标是在战场上部署大量传感器以收集信息，对相关原始数据初步融合后，再把重要信息传送到各数据融合中心，将大量信息集成战场全景图，提高美军战场态势的感知能力。2002 年，美国 Sandia 国家试验室与美国能源部合作，共同研究能够尽早发现以地铁、车站等场所为目标的生化武器袭击，并及时采取防范对策的系统。同年，INTEL公司发布“基于微型传感器网络的新型计算发展规划”，宣称将致力于微型传感器网络在预防医学、环境监测、森林灭火，乃至海底板块调查、行星探测等领域的应用。目前，无线传感器网络作为信息领域的一个全新方向，引起了学术界的广泛关注。近年来各国学者在移动自组网和无线传感器网络方面的研究有力促进了Ad Hoc网络的发展，而各种应用系统又对Ad Hoc网络的进一步研究提供了有价值的参考。但纵观现存的Ad Hoc网络系统，其与具体应用的关系都很紧密。每个Ad Hoc系统都有自己相对独特应用背景与特点，这使得Ad Hoc网络系统一般很难直接进行移植使用。针对一个新的应用场景，往往都要根据具体情况来进行网络的规划与设计。而舰船编队网络作为Ad Hoc网络的一个典型应用，其相关研究还处于起步阶段。一方面水面上的舰船通信研究相对较少，另一方面由于组织模式以及物理设备之间的差异，其它Ad Hoc网络系统对于舰船编队网络研究的借鉴意义有限。本课题研究的路由协议为舰船编队网络的建设提供有价值的参考。1.4论文的主要工作论文首先总结了舰船编队网络的应用特点，说明为舰船编队网络设计一个路由协议的价值和意义。在对现有研究成果进行总结和分析之后，论文以舰船编队网络应用为背景，提出并设计了一种混合式路由协议；然后针对舰船编队网络中突出的负载均衡问题进行了研究，提出了基于信道负荷的负载感知和基于历史信息概率准入的负载调度算法。最后在Qualnet仿真平台上分别对路由协议和负载均衡算法进行了仿真验证。仿真结果表明论文设计的路由协议能够较好的适应舰船编队网络的特点，在丢包率、时延、协议开销等诸多方面优于DSR和ZRP等现有的协议；论文设计的负载均衡算法能够有效的解决舰船编队网络中负载分布不均带来网络拥塞，显著的提高了网络在吞吐量和时延等方面的性能。本论文设计的路由协议和负载均衡算法，具有以下创新点：1、结合舰船编队网络的拓扑变化特点，提出了拓扑变化感知和路由缓存机制，减少路由开销和数据的路由时延。2、设计了一种基于信道负荷的负载感知方法，能够在不占用网络资源的基础上对网络的负载状态进行准确的映射。3、设计了一种基于历史信息和概率路由准入的负载调度算法，算法不需要增加任何的开销、不需要改变数据的格式，完全分布式的完成负载的调度，很大程度上避免和减少网络拥塞。1.5论文的内容组织本论文的组织结构如下：第一章 绪论。首先介绍课题的背景、来源及意义，然后阐述了课题的相关研究和技术，最后概括论文的主要工作；第二章 MANET中的路由协议。首先对路由协议的发展现状进行简要的介绍，然后对典型的路由协议进行较为详尽的分析和介绍；第三章 舰船编队无线自组织网络的路由协议设计。首先对舰船编队网络场景的特点进行了归纳，然后针对这些特点设计了一个适用于舰船编队无线自组织网络的路由协议(HSRP)，并对协议设计的关键问题进行详细的阐述，最后对路由协议的性能进行仿真和分析；第四章 负载均衡路由协议研究。首先是负载均衡的提出以及介绍相关研究热点，然后设计了一种适用于反应式路由协议的负载均衡算法，最后对该算法进行详细的仿真和分析得到结论。第五章 结束语。对论文的工作进行总结，并指出下一步将要完成的工作。71第二章 MANET中的路由协议2.1引言Ad Hoc网络是一个临时的自治系统，网络中的移动终端兼具传统意义上终端和路由器的功能，网络中的节点处在对等地位，而且网络中没有中心节点协调网络的运行。这些都使得Ad Hoc网络技术比传统有线网要复杂的多，Ad Hoc网络技术涉及到OSI分层10模型中的每个层面。研究者已经在媒质接入、路由、功率控制、QoS、安全等方面发布了相关的研究成果10-12。在众多的研究中，Ad hoc网络的路由问题尤其关键，IETF已经成立了MANET工作组集中从事Ad hoc网络路由协议及其性能评定的研究。Ad Hoc网络中的特点使Ad Hoc网络中的路由协议设计比有线网面临更多的困难和更大的挑战，主要表现在以下几个方面：1、动态拓扑：动态变化的网络拓扑是Ad Hoc网络的一个显著特点。由于通信终端的随机移动、无线发信装置发送功率的变化、无线信道间的互相干扰以及地形等综合因素的影响，移动终端间通过无线信道形成的网络拓扑结构随时都有可能发生变化，而且变化的方式和速度都是不可预测的。2、多跳组网：所谓“跳数”是指经过路由器的个数。Ad Hoc网络中，由于节点的通信距离有限，分组通常都要经过多个路由器进行中继才能到达目的地。因此，Ad Hoc网络是一个多跳网络，这与无线局域网的单跳有很大的区别。多跳的特点给工作在同频段的终端节点带来了“隐藏终端”“暴露终端”等问题13，对网络的性能产生重要影响。3、分布式控制：Ad Hoc网中用户终端的地位平等，不存在中心控制点，组成一个对等式网络，其中的节点可以随时加入和离开网络，每个节点都分布式的寻找到目的节点的路由。4、无线广播信道：Ad Hoc网络中使用的是无线信道，无线信道具有天然的广播特性，并且它所能提供的网络带宽相比于有限信道要低得多，质量也差得多。考虑到竞争共享无线信道产生的冲突、信号衰减、噪音和信道之间干扰等因素，移动终端获得的实际带宽远远小于理论上的最大值，并且会随时间动态地发生变化。5、单向信道的存在：单向信道是指存在单向链路的信道。由于各无线终端发射功率的不同以及地形环境的影响，Ad Hoc网络中可能产生单向链路，使相邻两个节点只能进行单向通信。到目前为止，已经针对Ad Hoc网络开发出了许多的路由协议，其分类可以采用多种方法，一般从不同的角度将Ad Hoc网络路由协议按照以下四种方式分类：(1)主动型(Proactive)和反应型(Reactive)；(2)平面型(Flat)和层次型(Hierarchical)；(3)GPS辅助型(GPS Assisted)和非GPS辅助(Non GPS Assisted)型路由协议；(4)单路径型(Single-Path)和多路径型(Multi-Path)。这些分类方法的着眼点不同，在具体的路由协议设计过程中，可以采用单一策略，也可以同时采用多种策略，如反应型的GPS辅助多路径路由协议等。虽然路由协议的分类不同，但是归纳起来各种路由协议所针对的核心问题都是围绕着如何控制路由开销、提高收敛速度、增强拓扑感知能力以及避免路由环路等方面展开的。目前主流的分类方法是依据网络中节点获取路由的方式和时机的不同而分为先应式(或称主动式)、反应式(或称被动式)以及混合式三大类，下面将对这三种协议分别加以介绍。2.2先应式路由协议先应式路由协议又称表驱动协议，其路由信息的获取方式与有线网类似，一般是采用节点周期性动态洪泛的方式，将距离矢量或者链路状态信息通告给网络中的其它节点，从而使网络中的节点获取网络路由信息。先应式协议的主要代表有WRP14、DSDV15、FSR16、OLSR17协议等。2.2.1 WRP14路由协议WRP(Wireless Routing Protocol)协议即无线路由协议，是一种基于距离矢量的表驱动路由协议。WRP利用bellman-ford的基本算法通告距离矢量信息来维护路由表，每个节点保存在路由表中的信息如下：距离、路由、链路开销和重传计数器、每一个节点正确应答所需的标识和更新消息的更新列表(MRL)等。MRL记录关于消息序列号、重传计数器、每一个邻节点正确应答所需的标识和更新消息的列表等信息。这就使得节点可以决定何时发送更新消息以及发送给哪个节点。更新消息包括目的节点的地址、到目的节点的距离和目的节点的上游节点，然后邻节点就可以修改自己的路由表并试图建立新的路由。由于无线链路的特性或网络拥塞，更新分组可能丢失或者过期，需要采用重传机制来保证更新分组的可靠传输。节点正确地收到更新分组之后需要发送一个ACK进行确认。如果节点没有转发数据分组或者更新消息，则要定期发送HELLO分组，以确保节点间的连通性。节点在一段时间内没有收到邻节点发送的任何分组，就认为和该节点的链路失败。表2.1 WRP路由表条目格式Dest idDistancePredecessorSuccessorTagWRP协议中，节点为每个目的节点保存一个路由条目。表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的拓扑更新采用周期触发和事件触发相结合的方式。即节点在发现链路故障后主动发起拓扑更新消息，而在无故障的情况下以较小的频度周期发送拓扑更新消息。2.2.2 DSDV15路由协议另外一种先应式路由协议为DSDV(Destination-Sequenced Distance-Vector Routing)协议，该协议是一种基于bellman-ford算法的距离矢量协议。每个节点都维护一张路由表，表中记录到其他节点的路由信息，包括目的节点的标识以及距离(即跳数，Number of Hops)，当节点发现目的节点不可达时，将距离设为无穷大。DSDV与有线网络中的距离矢量协议大致相同，但是增加了目的节点序号的记录、路由增量的更新和延时路由表更新等策略。DSDV中主要是通过在拓扑更新消息中引入序列号的机制来区分路由的新旧，节点收到路由更新之后，比较其中的目的节点序列号和自己保存的同一目的节点的序列号，如果前者大，就更新自己的路由；如果路由序列号相同，则选择具有较少跳数的路由。DSDV协议中通过延时路由表更新的策略防止路由表的波动。在如图2.1所示的网络中，节点B有一条路由经12跳到达节点A，节点C有一条11跳到达节点A的路由，且节点D先收到节点B的路由更新分组，经过10s后又收到节点C的路由更新分组。如果节点D一收到B的路由更新分组就更新自己的路由表，并广播路由更新分组，则在图2.1所示的情况下，节点D在短短的10s内就更新了两次路由表，并且还广播了很多路由更新分组。这就是路由表波动问题。图2.1 路由波动问题示例图在DSDV中采用触发更新和稳定时间机制来解决此类问题。当节点收到新的路由信息时，可分为两种情况：一是链路失败，二是调整已存在的路由。对于第一种情况需要立即发送路由更新分组，这就是所谓的触发更新；而对于第二种情况则需要等待一段时间再发送路由更新分组，这就是所谓的稳定时间机制。2.2.3 FSR16路由协议FSR(Fisheye State Routing)协议是一种先应式链路状态协议，但是其综合采用了距离矢量和链路状态两种协议思想。其来源于基于全局链路状态的GSR(Global State Routing)协议，并在拓扑更新和路由维护方面进行了改进。FSR协议中每个节点通过几张表来维护一张网络拓扑图，包括邻居表、拓扑表、下一跳表和距离表，用来计算到目的节点的最短路径。FSR协议中节点周期性地发送链路状态分组来更新路由表，但是不同于一般的链路状态协议，FSR协议的链路状态分组仅在邻节点之间交换，而普通的链路状态协议采用全网广播的方法。为降低链路状态信息通告开销，FSR利用距离长度限制路由表项的更新频度。跳数较远的路由表项被包含在拓扑更新消息中的频度较小，反之较大，这样就控制了路由信息占用的开销，节省了部分网络资源。FSR协议的拓扑结构如图2.2所示，由于其拓扑结构像鱼的眼睛，所以称之为FSR(Fisheye State Routing，鱼眼协议)。图2.2 FSR路由协议“鱼眼”图2.2.4 OLSR17路由协议OLSR(Optimized Link State Routing)协议是一种基于链路状态算法的先应式路由协议。OLSR协议的核心是多点中继(Multipoint Relay)机制。多点中继的思想是通过减少同一区域内相同控制分组的重复转发次数来减少网络中广播分组数量。网络中的每一个节点选取其邻节点的一个子集用于转发该节点的控制分组。这些被选中的节点就称为该节点的MPR，该节点就称为这些MPR的多点中继选择节点(MPR Selector)。节点A的MPR集合是满足下面条件的节点集合：(1) MPR 中的每个节点都是 A 的一跳邻居节点；(2) 通过MPR 中的节点，A 可以将信息传播到所有两跳节点。同时，OLSR协议规定，节点广播的链路状态消息仅被其MPR节点转发，非MPR集合中的节点不转发。协议中路由信息的传播更新过程如图2.3所示：(a)(b) (c)图2.3 OLSR路由更新过程图2.3中的灰色节点即为MPR节点。可以看到，在图2.3的拓扑中，仅A、C、E、H转发了链路状态更新报文，而其它节点都没有转发。OLSR协议利用这种MPR机制有效抑制了路由信息的扩散，降低路由开销。上边介绍的WRP、DSDV和OLSR都属于先应式路由协议，先应式路由协议由有线网中的路由协议发展而来，其优势在于能为上层服务提供较小的时延。下边将要介绍另一类路由协议-反应式路由协议，相比于先应式路由协议，反应式路由协议有着截然不同的路由方式。2.3 反应式路由协议除前边介绍的各种先应式路由协议外，还存在一类专门针对Ad Hoc网络的特点而提出的路由协议-反应式路由协议。反应式路由协议中节点并不周期性地维护到目的节点的路由信息，而是当有上层业务到达时，再发起到目的节点的路由寻找。这种路由协议的优势在于：路由与业务紧密相关，网络没有业务请求时，无需路由维护开销；并且由于反应式路由协议对路由处理的即时性，协议中不易引入环路和过期路由，具有较好的健壮性。所以，越来越多的人把目光投向了反应式路由协议。目前有代表性的反应式路由协议有DSR18、AODV19以及TORA20协议，下面分别对这些路由协议加以简要的介绍。2.3.1 DSR18路由协议DSR(Dynamic Source Routing)协议是一种反应式源路由协议。源节点通过洪泛路由请求消息(RREQ)发起路由寻找，收到请求的中间节点将自身地址添加到DSR报头的源路由选项中并转发，直到该路由请求消息抵达目的节点。目的节点通过RREQ中的节点列表信息获取到RREQ源节点的路由，然后目的节点向RREQ的源节点发送RREP，RREP中包含了从源节点到目的节点的路由信息，所以源节点收到RREP之后形成到达目的节点的路由。DSR的路由查询流程如图5所示。 图2.4 DSR路由过程图2.4中A为源节点，节点K为目的地址。节点A发送RREQ分组发起路由查找，中间节点E和H收到之后把自己的地址添加到RREQ的源路由选项并转发，最终RREQ到达目的节点K，目的节点K根据RREQ中路径信息的逆序向节点A发送RREP，节点A收到RREP后形成到节点K的路由。需要注意的是，诸如RREQ报文、RREP报文以及源路由数据报文中均携带路由信息，所有监听到上述报文的节点将提取其中的路由信息，更新本地路由表，以节省路由查询的时延和开销。由于DSR路由查询和应答的多路径传输特性，一次路由申请可能获取多条源路由，这为流量均衡以及QoS服务等方面提供了较大的便利。在不需要多路径路由的应用场景下，可以采用一些广播风暴抑制的策略限制RREQ和RREP消息在全网的扩散。2.3.2AODV19路由协议另外一种较为有代表性的反应式路由协议是AODV(Ad Hoc On Demand Distance Vector)协议，AODV协议由DSDV算法发展而来。AODV协议采用与DSR协议相似的路由发现与查找过程。如图2.4所示，节点A广播RREQ分组发起到目的节点K的路由寻找，AODV的RREQ分组中并没有DSR中RREQ那样的源路由字段选项，而是只有一个上一跳节点选项，中间节点H收到节点E转发的RREQ，那么其能够获知自己到节点A的路由下一跳节点是E，并把此路由信息保存在路由缓存表中。RREQ在网络中不断的扩散，每个收到RREQ的节点都像节点H一样根据上一跳节点构造一个反向路由并保存。目的节点K收到RREQ后用构建的反向路由回送RREP，从而使源节点A获得到节点K的路由。AODV协议中，节点获得到目的节点的路由之后，不再把路由信息放到数据分组的首部，而是利用逐跳转发的方式把数据分组路由到目的节点。由于AODV的数据包中不携带源路由信息，所以相对DSR具有较好的可扩展性，比较适合节点容量大的网络。但是同时，去除源路由信息也导致了节点监听信息量的减少，无法应用监听的信息获取多跳以外的路由。2.3.3TORA20路由协议反应式路由家族中的另外一个协议为TORA(Temporally Ordered Routing Algorithm)协议，该协议借鉴图论中的有向图概念，利用传播、维护和修改节点在链路中的相对高度值构建从源到目的节点的多径路由。TORA采用链路翻转的分布式算法，该协议为每个节点分配一个相对目的节点的高度值，作为路由度量值。相邻两个路由节点之间直接通信时，具有较大高度值的节点被规定为上游节点，TORA规定被路由的分组只能从上游节点流向下游节点。当发生链路断裂时，协议赋给断裂处节点一个比其邻节点都高的高度值，这样分组就在此处返回，这一过程称之为反转，并在断裂处附近查找可用路由，协议的控制报文只在最靠近拓扑变化的地方产生。此种算法中路由不一定是最优的，其常常使用次优路由以减少路由发现过程带来的开销。但是当拓扑较为复杂并且移动性较强时，其收敛较慢，开销较大；并且TORA协议是基于同步时钟的，所以时钟的时间不同步可能导致路由协议故障。综上所述，反应式路由依靠应用层数据驱动协议的运行，因此一般认为反应式路由协议比先应式更适合Ad Hoc网络。但是根据具体应用场合和应用需求不同，两类协议各有所长，也都有自己的局限。先应式路由协议需要不断的交互路由信息来维护路由表，所以协议开销较大 (尤其在拓扑变化较频繁、剧烈时)，但是寻路时延较小且受上层业务流量的影响较小；反应式路由协议仅在需要时才搜索路由，开销相对较小，但是寻路时延较大，并且受数据突发影响较严重，即如果相邻节点几乎同时发起路由查找请求，往往寻路失败的概率较大。为了弥补双方的不足，出现了先应式和反应式路由协议的结合体-混合式路由协议。2.4混合式路由协议混合式路由协议的基本思想是结合先应式和反应式路由的寻路方式，在部分区域内采用先应式路由，而在另一部分区域内则采用反应式，从而获得高效与低开销的统一。混合式路由协议中比较有代表性的是ZRP21和SHARP22。下面分别介绍这两个路由协议。2.4.1ZRP21路由协议ZRP(Zone Routing Protocol) 协议基于近端节点先应式而远端节点反应式的思想，通过定义先应式半径d区别维护路由表。先应式半径d一般以跳数为单位，节点利用DV算法维护d(d一般设为2)跳以内的路由，而当需要寻址到d跳以外时，再利用反应式路由算法寻找路由，其反应式路由机制类似DSR。先应式半径区域内的路由称为Intra-zone路由，而先应式半径区域外的路由称为Inter-zone路由。如图2.5所示，节点S 的一个半径为2的路由区域。与节点的距离等于区域半径的点称为边界点，如节点K即为S的边界点。S维护在虚线以内(2跳)的节点的路由表，而在两跳以外节点(如节点J)的路由通过类似于DSR的反应式机制来发现和维护。图2.5 ZRP半径为2的路由区域2.4.2SHARP22路由协议另外一种混合式路由协议为SHARP(Sharp Hybrid Adaptive Routing Protocol)路由协议。SHARP是针对ZRP协议中存在的静态半径和区域重叠等问题由V. Ramasubramanian等人提出的，其是一种可以根据网络流量动态调整先应式区域半径大小的路由协议，其特点体现在如下几个方面：1、协议可以根据网络流量特性来动态调整先应式半径的大小。SHARP协议中考察节点作为目的节点的属性，对于繁忙的目的地节点(即有多个源发送数据给它)，其设置先应式的半径较大，而对于不繁忙的目的节点，其设置先应式半径较小。这样在网络流量较小的时候，全网退化成反应式的寻路，而当全网流量较大且分布均匀时，则全网退化成先应式路由。2、SHARP的区域内先应式协议借鉴了DSDV（序号机制）、TORA的有向图机制、以及piggyback技术，其反应式的路由基于AODV协议；3、SHARP的先应式路由维护、半径调整以及维护都是通过邻近节点之间交互信息实现的，交互的信息包括先应式半径、丢包率等信息。图2.6 SHARP的区域调整示意图如图7所示，S为源节点，D为目的节点，r先应式半径。目的节点D根据自己统计的信息计算出最佳先应式半径为r。源节点采用AODV的方式发起到目的节点D的路由查找，到达h-r跳之后路由查找结束，路由变为先应式。SHARP基于先应式引入开销而反应式引入时延的假设，通过动态调整节点的先应式区域半径，达到降低开销和控制时延以及限制丢包率的目的(开销、时延以及丢包率均是先应式区域半径R的函数)。2.5几类路由协议的比较上边介绍了先应式、反应式以及混合式路由协议和各类中比较典型的路由协议。总体看来，几类协议在寻路方式上风格迥异，各有特点。一般我们习惯从寻路时延、路由开销以及能量耗费等23诸多方面来对路由协议进行考察比较，各类路由协议的特点比较如表2.2所示（表中标注的高、中、低是相对而言）：表2.2 各类路由协议比较先应式反应式混合式典型协议DSDV，WRP，FSR，OLSRDSR，AODV，TORAZRP，SHARP寻路时延低高Intra-zone低Inter-zone高路由开销高低中能量耗费高低中带宽占用高低中先应式路由协议之间的比较主要从路由环路、存储表的数目、路由更新方式等方面考察，如表2.3所示：表2.3 先应式路由协议比较先应式路由协议DSDVWRPFSROLSR路由环路避免是是，不立刻是是存储表的数目2445路由更新方式周期+按需周期+按需周期周期是否使用HELLO是是否是反应式路由协议之间的比较主要从路由开销、多路径支持以及复杂度等方面考察，如表2.4所示：表2.4 反应式路由协议比较反应式路由协议DSRAODVTORA复杂度中中高寻路开销低中中多播支持否是否多路径支持否是是路由保存路由表路由缓存路由表路由度量最新及最短路径最短路径最短路径2.6小结本章对课题研究的Ad Hoc网络路由协议进行了介绍，包括先应式、反应式和混合式路由协议，并对各类典型路由协议的进行了描述和分析。通过本章的分析发现，虽然目前已经诞生了很多路由协议，但是这些协议大部分都是针对一般的应用提出的，而与具体应用场景的关联不够紧密。这也使得现有的路由协议应用在舰船编队网络中都有不足之处，难以适应舰船编队网络的特点。本文根据舰船编队网络的特点，借鉴现有路由协议的研究成果，设计了一种适用于舰船编队网络的混合式路由协议，称之为HSRP(Hybrid Source Routing Protocol)路由协议，本文将在第三章对其进行详细的介绍。第三章 舰船编队无线自组织网络的路由协议设计3.1引言从论文第二章关于Ad Hoc网络路由协议的阐述可以看出，研究人员已经在此领域取得了丰硕的成果，但是考虑到舰船编队网络中物理信道、移动模型和流量分布上的特殊性，这些研究成果难以直接应用，或者说不能很好的适应舰船编队网络应用的特点。我们在借鉴论文第二章介绍的相关思想的基础上，提出并设计了一种专门针对舰船编队网络应用的路由协议，称之为HSRP(Hybrid Source Routing Protocol)路由协议。HSRP协议是以舰船编队网络为应用背景的混合式路由协议，协议中加入了基于拓扑变化感知的路由更新和基于MRP(Multi Point Relay，多点中继)17的路由开销控制策略，力求通过简单有效的机制提高路由协议的性能，最终达到满足舰船编队网络应用需要的目的。本章第二节介绍舰船编队网络场景的特点，第三节介绍HSRP协议的设计，第四节对HSRP进行仿真及结果分析，最后给出小结。3.2舰船编队网络的场景特点舰船编队网络是Ad Hoc网络的典型应用之一，其场景的诸多特点使其不同于一般地面上的Ad Hoc网络应用环境。总结起来，其特点有以下几个方面：1、物理信道。水上环境的特点使水上无线信道有别于陆地。水面相对陆地更加空旷平坦，无线通信受地形影响相对较小；编队网络中舰船之间通信设备的性能差异不大，可认为节点间是双向链路；水面环境下的信道衰落和多径等特点也不同于地面。2、移动模型。舰船编队网络中节点的移动具有显著的规律性。多艘舰船执行任务时往往编队行进，而且编队的队形有多个，编队可能经常需要从一个队形变化到另一个队形。这使得舰船编队网络的拓扑变化具有两个特点，一个是拓扑的阶段稳定性，另一个是拓扑变化的全局性。舰船以某一个队形行进时，舰船的位置相对稳定；当舰船编队从一个队形变化到另一个队形时，各舰船之间的邻接关系基本上全部发生了变化，基本上很少出现拓扑局部变化的情形。3、流量模型。基于当前的舰队组织模式可以预见,编队舰船之间的业务流量具有显著的不均衡性。一方面旗舰要经常下发指挥控制信息给其它僚舰，另一方面各僚舰要经常向旗舰报告一些信息，这就导致旗舰附近的负载很重而其它僚舰的负载相对较少且分布平均。根据应用场景的这些特点，我们设计了HSRP路由协议，第三节描述该路由协议的设计。3.3协议设计3.3.1协议设计思想基于舰船编队网络的应用，HSRP路由协议采用混合式的路由策略，同时协议中融入了跨层设计的思想，以便在得到较好网络时延的同时控制协议的开销。舰船编队网络中的MAC协议采用的是混合式的TDMA协议(简称HTDMA)，其在MAC层保存两跳范围邻居节点的信息。为节省无线网络宝贵的信道资源，HSRP协议直接从MAC层跨层共享两跳范围内的路由信息来构造先应式的路由表。对于2跳范围外的路由，HSRP采用类似于DSR的反应式路由机制。ZRP协议中，先应式半径区域内的路由一般称为Intra-zone，而先应式半径区域外的路由则称为Inter-zone，在HSRP协议中我们也延续这一说法。同时，HSRP的反应式路由过程中加入了类似OLSR协议的MPR思想，来限制广播包在网络中的扩散，降低协议的开销。3.3.2近距离路由规则传统混合式路由协议中，先应式半径内的路由需要通过节点之间的路由信息交互来实现，一般采用距离矢量(DV)算法或链路状态(LS)算法，例如ZRP中先应式半径内的路由维护采用的是距离矢量算法。而HSRP协议有效利用了舰船编队网络体系结构的特点，通过跨层信息共享来减小路由开销。舰船编队网络的MAC层使用的是混合式的TDMA型信道接入控制协议，该协议在MAC层维护两跳范围内的节点信息，并且两跳范围节点信息会每隔2秒更新一次。所以，从舰船编队网络的整体架构考虑，为有效利用MAC层维护的两跳范围节点信息，HSRP协议中融入了跨层设计的思想。HSRP通过跨层共享从MAC层获取两跳范围节点信息，从而构造两跳范围的路由表。由于MAC层的两跳范围节点信息会每隔2秒更新一次，更新的频度足够快，基本上能够保证信息的及时准确，所以路由协议不再单独通过节点间信息交互的方式维护两跳范围拓扑。同时，也是为了使HSRP协议简单实用，将HSRP协议的先应式半径设置为2。这样一来，HSRP完全不用任何其它的耗费就能够及时准确的更新和维护先应式的路由表，很大程度上降低了协议的开销。3.3.3中远距离路由规则HSRP协议采用反应式维护中远距离(两跳以外)节点的路由，其实现方式类似DSR协议，并且针对本方案的应用背景进行了优化，以提高其路由命中率和降低路由开销。3.3.3.1 HSRP反应式路由机制HSRP对于先应式半径之外的节点采取反应式的策略路由，其反应式路由机制设计如下：1、当节点需要向2跳以外节点发送数据时，首先在路由缓存中查找是否有到目的节点的路由，若有则将该路由添加到数据包的源路由选项中，然后封装成HSRP的源路由数据包发送；若缓存中没有到目的节点的路由，则发送RREQ消息开始路由寻找。RREQ消息中含有源地址、目的地址、消息的ID号和RREQ消息所经过的节点等信息。2、中间节点收到RREQ消息之后，把RREQ的ID字段信息保存在路由请求表(Route Request Table)表中，但是在具有相同源节点和目的节点的RREQ路由请求中，此表只记录其最新的ID号。于是，当节点收到R