基于位置预测的Ad hoc网络路由协议研究-硕士论文

工程硕士学位论文工程硕士学位论文基于位置预测的Ad hoc网络路由协议研究学位申请人姓名 培 养 单 位 计算机与通信学院导师姓名及职称 学 科 专 业 计算机科学与技术 研 究 方 向 无线Ad hoc网络的路由协议论文提交日期 摘 要Ad Hoc网络是一个复杂的分布式系统，具有动态变化的拓扑结构。Ad Hoc网络没有任何中心和固定基础设施，每个节点都具有主机与路由器的双重功能，形成一个多跳分布式网络。如何找到快速稳定的路由是Ad Hoc网络研究的关键问题，目前Ad Hoc路由协议基于不同的出发点和机制，尚无比较完善的性能都比较优越的Ad Hoc路由协议，特别是具有QoS保障的路由技术，仍处于探索阶段，尚无成熟的协议标准，还有待于进一步的深入研究。本文首先介绍了Ad Hoc网络的基本概念，对Ad Hoc网络的路由协议进行了详细的分析研究。通过OMNeT+仿真，比较分析了几种常见路由协议在不同环境下的性能变化，包括：移动性、网络负载和网络环境等。仿真结果表明，随网络负载的增加数据分组成功发送率下降、路由包开销增大、端到端传输时延增长。仿真分析表明，目前路由算法存路由包开销大、端到端传输时延长等问题。因此，本文提出了一种基于位置预测的LAODV路由协议(Ad hoc On Demand Distance Vector routing Based On The position prediction ) 。设计了节点定位的自适应定位算法，在网络定位系统中配置一些位置己知的信标节点，一旦信标节点不够，低级节点自动吸纳高级节点作为补充“信标”节点参与该节点的定位。在得到基本位置信息后，通过对节点的位置进行预测，确定节点的位置和基本方向，选择最稳定路径进行数据传输，降低了路由破裂与重构次数，提高了数据成功传送率。仿真结果表明，通过对节点的位置进行预测，采用定向洪泛的路由算法和资源预留机制为数据的传输提供了可靠的QoS保障，降低了路由开销。关键字:Ad Hoc网络；地理位置路由；定位；OMNeT+AbstractAd Hoc network is a complicated distribute system, which has dynamic topology. There is no infrastructure in Ad Hoc network, while every node can be router and host, then form a multi-hop distributed network.How to rapidly find a stable route is the key problemin Ad Hoc network. There is no excellent performance Ad Hoc routing now, especially for QoS routing, which still in the initial stage and there is no industry standard. So it need do further research in Ad Hoc routing. First some basic concept of Ad Hoc network was introduced, then analysed Ad Hoc routing protocols. We analyzed and compared the performance of several Ad Hoc routing protocols in different network environment via OMNeT+, such as mobility, network load and environment. The simulation shows along with network load ,send out rate decline, the cost of routing increase and the delay of end to end extend. Network simulation shows these routing protocols have some weakless such as big cost and long delay. So an LAODV (Ad hoc On Demand Distance Vector routing Based On the position prediction) is proposed. We designed an adaptive localization algorithm for locating node. Set some beacon node that known there location, once there is no enough beacon node in the network, the senior node will be alternated node for beacon and join the localization stage. When get there location, via the prediction of the new position to confirm the position and direction of the node, then choose the best route to transmit. It will decrease the numbers of break route and re-route, and increase the data transmition rate. The simulation shows, through the prediction of position, using the directional flooding and resourse reserve to ensure the QoS, the cost of routing is decreased.Key words: Ad Hoc Network; Routing base Geography; Localization; OMNeT+III工程硕士学位论文目 录学位论文原创性声明和学位论文版权使用授权书I摘 要IIAbstractIII插图索引VI附表索引VII第1章 绪 论11.1 课题的研究背景及意义11.1.1 移动Ad hoc网络概述11.1.2 Ad Hoc网络中路由协议问题21.1.3 论文研究的意义31.2 Ad Hoc网络路由协议的研究现状41.3 研究内容51.4 论文结构51.5 本章小结5第2章 Ad Hoc网络路由协议62.1 Ad Hoc路由协议概述62.2 Ad Hoc路由协议分类性能研究62.2.1 按路由建立时间分类72.2.2 按路由算法类型分类92.2.3 按网络拓扑结构分类102.2.4 按路由协议的功能分类112.3 几种常见的典型的路由协议122.3.1 表驱动路由协议122.3.2 按需驱动路由协议142.3.3 混合路由协议152.3.4 实现机制比较162.4 本章小结17第3章 Ad Hoc路由协议的OMNeT+仿真与性能分析183.1 OMNeT+仿真的基本原理183.2 Ad Hoc路由协议的OMNeT+仿真203.2.1 Ad Hoc路由协议的OMNeT+仿真流程203.2.2 仿真参数设置与性能评价223.2.3 不同负载下Ad Hoc路由协议的OMNeT+仿真233.3 本章小结28第4章 基于位置预测的LAODV路由协议294.1 基于位置预测的Ad Hoc路由协议研究294.1.1 基于位置预测的Ad Hoc路由协议研究294.1.2 位置信息路由协议的分析与优化304.2 节点定位算法314.2.1 节点定位算法基本原理314.2.2 节点定位算法误差模型及误差消除技术324.2.3 自适应节点定位算法具体内容及定位过程334.3 基于位置预测的路由协议LAODV364.3.1 LAODV路由协议描述364.3.2 算法描述与实现394.3.3 LAODV性能分析424.3.4 LAODV仿真分析424.4 本章小结46第5章 总结与展望47参考文献49致 谢52插图索引图1.1 简单的移动Ad hoc网络示例2图2.1 按需驱动路由的路由建立示意图8图2.2 分级结构路由算法示意图10图2.3 CGSR路由协议的路由机制16图3.1 OMNeT+仿真程序的体系结构19图3.2 数据包成功发送率124图3.3 数据包成功发送率225图3.4 网络路由包开销126图3.5 网络路由包开销226图3.6 端到端的平均时延127图3.7 端到端的平均时延227图4.1 圆周定位模型32图4-2 节点分类34图4.3 定位流程35图4.4 位置管理方案37图4.5 最小路径生存时间的计算37图4.6 定向路由洪泛机制38图4.7 中间节点处理RREQ报文的过程40图4.8中间节点处理RREP报文的过程41图4.9 数据包成功发送率143图4.10 数据包成功发送率244图4.11网络路由包开销144图4.12网络路由包开销245图4.13 端到端的平均时延145图4.14端到端的平均时延246附表索引表2.1 路由协议性能比较（按路由建立时间分类）8表2.2 路由协议性能比较（按逻辑组织机构分类）11表2.3 典型Ad hoc路由协议实现机制比较17VII第1章 绪 论随着通信技术和计算机技术的不断发展，计算机网络正快速进入到商业、工业、教育和科研等领域，进入到人们的日常生活中，深深影响和改变着我们的生活和工作方式。移动通信网（如GSM和CDMA等）在我们周围广泛存在，它们需要有有线网络或存在固定基站，对于原来没有有线网络的区域或者有线网络已经被破坏的区域，例如在荒芜人间的沙漠中，浩瀚无边的大海上，以及被火灾或其它灾难所毁坏的城市，战场等特殊场所，以前的移动通信网络就不能满足要求。在某些特殊情况下，需要快速、临时地建立一个新的移动通信网络，来实现信息的传输。为了满足这种需求，一种新的移动通信网（移动ad hoc网络）应运而生。移动ad hoc网络(MANET)是一个复杂的分布式系统，它由很多自由移动的无线节点，动态地自组织成一个任意网络拓扑结构系统。它使各设备之间不需要固定基础设施就可以进行相互通信，并且能很好地连接到Internet等网络。在战争和日常生活上美好的应用前景渐渐成为人们的研究中心之一，也使ad hoc网络逐渐成为下一代网络的重要分支。1.1 课题的研究背景及意义1.1.1 移动Ad hoc网络概述Ad hoc1-5来源于拉丁语，是“专门地，特别地，随机地，随时地为即将发生的特定事件或情况”的意思。这里的Ad hoc网络是指一种特定的、多跳、自组织、无中心的无线网络。目前国内很多专家将Ad hoc网络称为“自组网”，或者“多跳网络”等等。移动ad hoc网络是由许多动态节点（带有无线收发装置）自组织成一个临时性的多跳的无中心的分布式系统。在任意时刻，每个节点可以向不同方向以不同速度移动，在网络中每个节点可以完全自由的运动，因此无法预测网络的拓扑结构发生怎样变化。移动ad hoc网络是一个多跳(Multi-hop)的无线移动网络6-9，当网络中两个移动节点在彼此的数据传输范围内时，可以直接进行无线通信；而当两个移动节点不在彼此的数据传输范围内时，两个移动节点必须经过其它中间移动节点转发进行无线通信。这里，我们描述了一个简单的由三个移动节点组成的ad hoc网络，如图1-1。在该网络中，移动节点A和C都不在彼此的数据传输范围内，但是它们都在移动节点B的数据传输范围内，因此如果移动节点A要向移动节点C进行数据通信，必须通过移动节点B进行数据转发。这是移动ad hoc网络的一个基本特征多跳性，也是路由设计的一个难点。 A B C图1.1 简单的移动Ad hoc网络示例在ad hoc网络中，移动节点既作为主机，又具有路由器的功能。一方面，移动节点作为主机运行相关的协同应用程序；另一方面，移动节点作为路由器运行相关的路由协议，实现路由发现、路由维护等路由操作，如果接收到的数据不是给自己的数据分组即进行数据转发。1.1.2 Ad Hoc网络中路由协议问题当前Internet网络中主要使用的路由协议10 11是基于距离矢量的路由协议和基于链路状态的路由协议。这两类路由协议都是针对有线或固定网络而设计，由于Ad Hoc网络的动态拓扑结构、数据转发的多跳性等特点，使得实用于Internet网络的路由协议并不适合Ad Hoc网络。目前Ad Hoc路由协议基于不同的出发点和机制，尚无比较完善的性能都比较优越的路由协议。各种路由协议都存在或多或少的问题，主要表现在以下几个方面：（1）动态的网络拓扑结构Ad hoc网络中，移动节点可以以任意速度和方向移动、电源用尽/关机或损毁、同时节点发送功率的变化、无线信道之间相互干扰、地理环境等因素的影响，网络拓扑结构随时都会发生变化，若在Ad hoc网络中直接运行Internet网络的路由协议，一旦拓扑结构变化，Internet网络的路由协议需要花费很长的时间和很大的代价才能完成收敛。（2）有限的无线传输带宽、链路容量动态变化无线信道通信环境比较恶劣，信号的干扰、衰落、噪声等因素的影响以及信道的共享与竞争，使无线链路的状态随时间的变化而变化，另外，由于移动节点在网络中以任意的方式移动，Ad Hoc网络的拓扑结构变化频繁，为了能够最快、最精确地反映网络拓扑结构的变化，因此，与固定网络相比，需要在节点间不断地交互控制报文。由于无线传输信道带宽有限，路由协议只有尽量减少节点间信息交互，才能减少路由协议开销，提高信道效率。（3）移动终端能力的有限性Ad hoc网络中终端节点内存小、CPU处理能力低、所带电源和发射功率十分有限。网络中节点既要作为主机又要作为路由器，节点能量一旦耗尽将会改变网络拓扑结构，从而改变网络寿命及性能。要求路由协议算法相当简单有效，最大限度节省能源，或在路由选择时尽可能选择能量较高的节点，而Internet网络的路由协议则没有上述的限制。（4）单向无线信道的存在Internet网络的路由协议通常认为物理层的通信信道是双向的，但在Ad hoc网络中由于发射功率或地理环境等相互影响可能存在单向信道，它为Internet网络的路由协议带来了严重的影响。（5）安全性差移动Ad hoc网络是一种无线方式的无中心的分布式结构，开放的链路非常容易受到攻击，没有固定的网络基础设施对用户进行鉴权和认证，容易被入侵、窃听、网络攻击和拒绝服务等。（6）不能提供可靠的QoS保证。只有提高网络的整体性能才能提供端到端的可靠QoS保证。目前尚无比较完善的性能都比较优越的路由协议，还需要进一步的完善。虽然已出现部分QoS路由协议，但大多处于研究阶段，很难真正提供可靠的QoS保证，总的来说，Ad Hoc网络的QoS路由技术还需要进一步提高，发展空间很大。要想设计一个整体性能高，在所有情况下都合适的Ad Hoc网络路由协议非常困难，也可以说是基本不可能的。1.1.3 论文研究的意义在移动ad hoc网络中，移动节点通过多跳无线链路实现相互间的通信，开发一种能有效地找到节点间路由的动态路由协议就成为移动ad hoc网络设计的关键，是实现快速适应快速变化的网络拓扑结构，保证网络良好的鲁棒性和路由查找的有效性，减少路由开销，降低电能损耗的保障。所以设计一个好的路由协议算法具有重要的研究价值和现实意义：（1）通过自适应的节点定位算法，计算节点位置，为定向洪泛提供基础。（2）通过定向洪泛，减少网络路由开销。（3）通过自适应的节点定位算法获得节点位置，提出基于位置预测的LAODV路由协议，并详细阐述其设计过程和仿真实验，为Ad hoc网络路由查找提供一种更优化的协议，解决核心技术难点，具有现实意义。总之，本课题针对移动ad hoc网络的特点，探讨ad hoc网络路由协议，特别是AODV路由协议和基于位置的路由协议，提出基于位置预测的LAODV路由协议，对于降低路由开销，提高包转发率，降低平均时延有很重要的意义。1.2 Ad Hoc网络路由协议的研究现状由于移动Ad Hoc网络具有动态的网络拓扑结构，所以路由问题显得尤为重要，路由协议的好坏直接影响到整个网络的整体性能。对移动Ad Hoc路由协议的研究已经成为无线通信的热点之一，对路由算法的研究也越来越深入，已经从不同的角度提出了多种针对Ad Hoc网络的路由协议12，每种路由协议都有着自己的特点，他适用于不同的应用环境。目前大致可以将它们分为主动路由协议、被动路由协议，混合路由协议及全球定位系统GPS辅助的路由协议。主动路由协议又叫表驱动路由协议，目前主要有DSDV13 (Destination-Sequenced Distance-Vector)、WRP14 15 (Wireless Routing Protocol)和CGSR(Cluster Head-Gateway Switch Routing)等，该类协议每个移动节点需要维护一张包含到达其它所有节点的路由信息的路由表，随着网络拓扑结构的变化随时更新路由表，它准确地反映网络的拓扑结构。每当源节点发送报文，通过路由表即可获得到达目的节点的路由。因此这种路由协议延时较小，但维护路由开销较大。被动路由协议又叫按需路由协议，目前主要有DSR17 (Dynamic Source Routing)、AODV16 (Ad hoc On demand Distance Vector) 和TORA18 19 (Temporally-Ordered Routing Algorithm)等，该类协议中每个移动节点不需要随时维护更新路由信息，当源节点需要发送数据时才起动路由查找过程。与主动路由协议相比，按需路由协议的开销较小，但是报文传送的延时较大。混合式路由协议20 21，是结合了主动路由协议和被动路由协议的优缺点，即在小范围内使用主动路由协议，维护准确的路由信息，可以减少路由控制消息传播产生的延时。当目标节点较远时，通过被动路由协议查找发现路由，这样既可以减少路由协议的开销，也减少了报文传送时延。但是要实施混合式路由也面临着很多困难，如局部范围的确定和维护，主动和按需路由协议的合理选择等。目前该类协议主要有ABR(Associativity-Based Routing) 、CGSR ( Clustered Gateway Switch Routing，簇头网关交换路由)等。GPS辅助的路由协议。随着GPS定位技术的发展，在移动节点中实现低成本的GPS接收机成为可能，节点就知道自己的地理位置，许多研究者通过GPS定位提出了利用位置信息的路由协议，这类协议具有更好的可扩展性及对网络变化更好的适应性。目前已提出的基于节点位置的路由协议主要有LAR(Location Aided Routing)、GLS(Grid Location Service)、DREAM(Distance Routing Effect Algorithm For Mobility)、GPSR(Greedy Perimeter Stateless Routing)等。这些Ad Hoc路由协议基于不同的出发点和机制，针对每一种路由协议的特点，研究者们从不同的角度(如带宽、能量、链路稳定度、QOS等)做了相应的一些优化研究，但到目前为止尚无比较完善的性能都比较优越的路由协议。1.3 研究内容本文首先研究Ad Hoc网络路由协议存在的问题，然后对Ad Hoc网络路由协议22 23进行分类讨论研究，再对典型的路由协议进行详细分析，得出各路由协议优缺点。为了更好地进行分析验证，仔细研究OMNeT+仿真软件（仿真原理和仿真过程），并用OMNeT+对AODV ，DSDV ，DSR和TORA四种典型的路由协议进行仿真分析。通过研究分析基于位置预测的路由协议，提出自适应的节点定位算法，通过节点定位，提出基于位置预测的LAODV路由协议，对该路由协议进行详细描述，并对其进行仿真实验。1.4 论文结构本文从Ad Hoc网络路由协议存在的问题入手，比较、分析已出现的路由协议，并对典型的路由协议进行仿真分析，针对其特点，提出自适应的节点定位算法，然后通过节点定位信息，提出基于位置预测的LAODV路由协议，并对其进行详细描述和仿真实验。文章内容的组织和安排如下：第一章为绪论，分析Ad Hoc网络路由协议的问题及研究现状，并阐述了论文的选题背景与意义，研究的主要内容及其组织结构。第二章对Ad Hoc网络路由协议有关概念进行了阐述，对Ad Hoc网络路由协议按照不同的分类方法进行性能研究，最后重点研究几种常见的典型的路由协议。第三章介绍OMNeT+仿真的原理，详细分析OMNeT+仿真过程，并用OMNeT+对AODV ，DSDV ，DSR和TORA四种典型的路由协议在不同负载下的性能进行仿真分析。第四章研究分析基于位置预测的路由协议，提出自适应的节点定位算法，通过节点定位，提出基于位置预测的LAODV路由协议，对该路由协议进行详细描述，并对其进行仿真实验。第五章总结所做的工作，指出存在的问题和下一步工作。1.5 本章小结本章为绪论，分析Ad Hoc网络路由协议的问题及研究现状，并阐述了论文的选题背景与意义，研究的主要内容及其组织结构。第2章 Ad Hoc网络路由协议Ad Hoc网络自身的特殊性决定了路由协议的特殊性和重要性。本章首先分析设计理想Ad Hoc路由协议应具备的特点，然后根据不同分类方法详细研究分析Ad Hoc路由协议的性能和优缺点，最后详细研究几种经典的Ad Hoc路由算法。2.1 Ad Hoc路由协议概述由于Ad Hoc网络的动态拓扑结构、数据转发的多跳性等特点，使得实用于Internet网络的路由协议并不适合Ad Hoc网络，必须设计新的适用于Ad Hoc网络特点的路由协议。理想的Ad Hoc网络路由协议需要具有以下几个特点：分布式路由算法。Ad Hoc网络是一种无线方式的无中心的分布式结构网络，为了保证网络良好的鲁棒性和路由查找的有效性，必须采用分布式的路由算法。具有自适应性，能适应快速变化的网络拓扑结构。Ad Hoc网络中移动节点可以以不同速度和方向任意移动，网络拓扑结构不断发生变化，因此，路由协议必须能够适应这种快速变化的网络拓扑结构，并为源节点找到最佳传输路径，提高路由协议可靠性。具有良好的可伸缩性。路由协议不能随着网络规模的不断扩大，网络整体性能急剧下降，对于网络规模的大小应该是相对透明。较少的路由开销，保证路由的有效性。Ad Hoc网络的资源非常有限，大量的路由控制报文不仅会造成网络局部拥塞，同时还占用了宝贵的无线带宽，降低无线网络带宽利用率。此外，移动节点不断发送路由控制报文还会降低电源的利用率，使得节点电能很容易耗尽，严重影响Ad Hoc网络拓扑结构的稳定性。较低的电能损耗。电池供电的移动终端要求路由协议算法相当简单有效，最大限度节省能源，以降低宝贵的电源损耗，提高电源利用率，从而延长网络生存时间。目前常见Ad Hoc路由协议主要有DSDV、WRP、DSR、AODV、CGSR、ABR等几种22，其中，DSDV 、WRP为表驱动路由协议，DSR、AODV为按需驱动路由协议，CGSR为分级路由协议，ABR是一种基于联合度量的路由协议。2.2 Ad Hoc路由协议分类性能研究目前Ad Hoc路由协议基于不同的出发点和机制，出现了较多路由协议，为了方便进一步的分析研究，我们对Ad Hoc路由协议进行分类，并对它们的性能进行比较分析。本文根据不同的分类原则将Ad Hoc网络路由协议从以下四个方面进行分类研究，并对不同类型Ad Hoc路由协议的性能进行分析。按路由协议建立时间，可分为主动路由协议、被动路由协议和混合路由协议。按路由算法类型，可分为基于距离矢量的路由协议，基于链路状态的路由协议，基于反向链路的路由协议和基于源路由的路由协议，以及混和路由协议。按网络的拓扑结构，可分为平面结构路由协议和分级结构路由协议。按协议的功能，可分为支持单向链路功能，支持多播与组播功能，具有QoS保证，以及具有安全机制等不同路由协议。下面分别对四种不同分类的Ad Hoc网络路由协议的整体性能进行详细地比较分析。2.2.1 按路由建立时间分类通常将Ad Hoc网络路由协议分为主动路由协议、被动路由协议和混合路由协议22。主动路由协议又称为表驱动路由协议和先应式路由协议，路由协议通过定期交换路由信息来维持和更新关于网络拓扑结构和各个节点路由信息的路由表，移动节点之间通过周期性地互相发送“问候报文”参与路由信息交换。它的优点是通过移动节点不断维护路由表及时了解网络拓扑结构的变化情况和其它节点位置信息，在源节点需要发送数据时直接根据路由表中的信息进行数据传输，不需另外的路由查找与建立等待时间，常见的主动路由协议有DSDV，WRP等。由于Ad Hoc网络具有动态的网络拓扑结构、有限的带宽资源等特点，每一个移动节点都维护一张全网路由信息表不但带来大量的路由开销，同时随着拓扑结构的变化路由表中的大量路由信息没用，特别是路由协议的可扩展性，导致维护的不可能，这是主动路由协议的最大缺点。随着网络规模扩大，节点移动迅加快速，这种缺点就越为明显，资源的浪费就越严重。被动路由协议就是针对这种情况提出的，被动路由协议只有在数据发送时才进行路由的查找与建立，大大的节省了维护路由表带来的路由开销。被动路由协议是Ad Hoc网络特有的路由协议类型，它可以降低主动路由协议中某些不必要的路由维护开销，提高网络的数据交换量和带宽利用率。被动路由协议主要由路由查找与建立和路由维护两个过程构成，如图2-1所示。当源节点需要获取到达目的节点的路由时，路由查找机制被激活。节点采用洪泛的方式向相邻节点发送路由请求报文，中间节点根据协议的具体机制进行部分或全部转发，直到目的节点收到该请求报文。然后，目的节点根据请求报文的信息激活建立机制，选择一条合适的路径反向转发路由应答报文，当源节点收到完整的应答报文后，整个路由建立完毕。由于拓扑结构的不断变化，一旦路径上的某个链路发生中断时，系统启动路由维护机制。被动路由协议是目前Ad Hoc网络中研究最广、种类最多的一类路由协议，常见的被动路由协议有DSR、AODV、TORA、ABR等。图2.1 按需驱动路由的路由建立示意图混合路由协议是对主动路由协议和被动路由协议的综合。将若干较小的区域组成一个较大的网络，在区域内使用表驱动路由机制，区域之间采用按需的路由机制。这种设置使路由表范围较小，节点不需要维护较大的路由表，从而避免维护更新路由表，产生过大的路由开销，另一方面，由于只在区域间进行按需驱动路由，路由查找时延要比完全按需驱动路由小的多。混合路由协议实现了按需驱动路由协议和表驱动路由协议的互补，具有相对偏低的带宽损耗和路由查找与建立延迟，随着网络规模的扩大，网络整体性能越来越明显，可扩展性较好。典型的混和路由协议有ZRP ( Zone Routing Protocol )，它以R为半径将网络划分为若干个重叠的区域，在区域内采用主动路由协议，在区域之间采用被动路由协议进行路由查找24。半径R的大小是影响协议性能一个重要参数，R的大小可根据网络的具体参数(节点的密度、运动速度等)来确定。其它常见混合路由协议还有ZHLS ( Zone Based Hierarchical Link State Routing)、CBRP(Cluster Based Routing Protocol)等。混合路由协议通常采用分级或分区结构，分级结构中需要引入簇的概念，因此增加了簇的管理与维护，在获得可扩展性的同时也引入了路由算法的复杂度和管理开销，这是混合路由的不足之处。三类路由协议的主要机制和基本性能的比较如表2.1所示。表2.1 路由协议性能比较（按路由建立时间分类）主动路由协议被动路由协议混合路由协议路由开销大小一般路由建立时延小大一般可扩展性弱一般强拓扑变化适应性弱强一般算法复杂度低低高路由结构平面平面分级路由表维护全网路由表无路由表局部路由表2.2.2 按路由算法类型分类按照算法类型Ad Hoc网络路由协议大致可以分为四类：基于链路状态的路由协议，基于距离矢量的路由协议，基于源路由的路由协议和基于反向链路的路由协议。少部分路由协议采用了混合路由算法。链路状态算法(LS)和距离矢量算法(DV)是Internet网络中两种传统的路由算法，固定网络中的RIP ( Routing Information Protocol)和OSPF ( Optimist Shortest Path First )就分别使用了这两种路由算法25。距离矢量算法是基于Bellman-Ford的简单最短路径分布式路由算法，它是最早应用于Internet网的前身ARPANET网络中。距离矢量算法是每个路由节点只记录到目标节点的跳数和通往目标节点的下一跳，简单实用，比较适合小型网络。Ad Hoc路由协议DSDV和AODV就是在距离矢量算法基础上发展起来的。DSDV路由协议在距离矢量路由表上附加一个由源节点产生的序列号，节点只使用具有最新序列号的路由信息更新路由表，从而避免了由于算法不收敛而造成的路由环路，是对传统的距离矢量算法的增强，并解决了由于网络传输时延带来的路由抖动问题。AODV是DSDV协议的按需路由版本。AODV中只有当节点需要时才进行路由建立，路径中的各个节点只记录了目标节点的距离和下一跳。距离矢量算法是每个节点在每次更新时向它的邻居发送它的整个路由表，链路状态算法是节点发送路由信息到网络上所有的结点。在链路状态算法中节点的邻接关系及其代价代表了链路的状态，各节点的链路状态之和构成了整个网络的链路状态。网络链路状态可以通过一张反映网络拓扑结构的邻接表来描述，表中每一项记录了节点间的邻接关系和链路代价。网络中每个节点会定期的或在链路状态改变时，通过洪泛方式将自身链路状态向网络中扩散。链路状态算法中每个节点都记录了全网的拓扑结构，网络管理起来比较方便，另外，链路状态的改变会及时向全网传播，收敛速度快，比较适合大型网络。但是与距离矢量比，算法实现比较复杂，消耗网络的带宽大。因此，基于链路状态的路由协议在网络规模一般较小的Ad Hoc网络中使用比较有限。基于链路状态算法的典型路由协议有OLSR ( Optimized Link State Routing)。OLSR是在纯链路状态算法的基础上加以优化而成的，通过限定链路状态数据报传播的范围来提高洪泛的效率，减少路由算法对带宽的需求。源路由算法是在数据包中加入完整的路由信息，中间节点根据数据报头字节中的路由信息进行数据传输的算法。由于网络的安全和使用效率，固定网络一般不采用源路由方式。但是由于Ad Hoc网络中节点的动态变化和每次路由建立后发送的数据量有限的特性，源路由算法依然可以取得较好的性能。DSR是基于按需驱动的源路由协议，节点通过洪泛方式查找到路由后将完整的路由信息写入数据报头，中间节点不需要维护任何路由信息，只需根据数据报头中的信息进行转发。当路由跳数过多时，源路由在数据包中占地比重较大，会降低网络的传输效率。反向链路(Link reversed)算法的设计思想完全相反(链路状态协议追求的是以最快的速度将链路变化通知到全网) ，其核心是将由于拓扑结构变化而引起的连锁反应限制在局部区域内，它适合于拓扑结构快速变化的网络，具有很好的自适应能力。基于反向链路的算法有TORA26。2.2.3 按网络拓扑结构分类按照网络管理的网络拓扑结构来分，路由协议可划分为平面结构和分级结构两类。平面结构就是网络中所有移动节点在路由功能上具有同等地位，它们之间没有功能的差别，不必要引入分层管理机制。平面结构路由的优点是节点在网络中地位平等，没有特殊的节点，数据流量在网络中均匀的分布，路由算法简单易于实现，鲁棒性强。缺点是可扩展性差，在很大程度上限制了网络规模的扩展。常见的Ad Hoc路由协议大部分属于平面结构路由协议，如：DSR，AODV，TORA，WRP，ABR等。图2.2 分级结构路由算法示意图分级结构路由算法是将移动节点划分成多个簇进行层次管理。如图2-2所示，它将某一区域的若干个移动节点划分为一个簇，每个簇设一个簇首节点。无论是簇首节点还是其它的簇成员都可以作为网关，网络通过网关连接构成主干网，主干网通过簇间协议完成簇间数据通信；簇内的移动节点通过簇内路由算法进行数据通信。分级协议具有很好的可扩展性，适合规模较大的网络。分级路由协议主要由簇管理协议，簇间路由协议和簇内路由协议。簇管理协议包括：一、如何实现移动节点在动态分布式网络环境下高效的成簇，它是分级路由协议的关键。二、如何实现动态分布式网络中簇结构维护，即簇的产生和消亡，簇首的更改，以及移动节点的进入和退出等。分级结构路由协议存在的主要问题是管理的复杂性导致算法复杂度和路由开销的加大；另一个缺点是簇首节点作为关键节点，一旦其退出或受到攻击，将影响网络的健壮性和安全性，特别在军事上，网络的健壮性和安全性将具有重要意义。常见的分区或分级结构路由协议有：ZRP (Zone Routing Protocol)，ZHLS (CZone Based Hierarchical Link State Routing)和CBRP(Cluster Based RoutingProtocol) 。分级结构路由协议与平面路由协议的基本性能比较如表2.2所示。表2.2 路由协议性能比较（按逻辑组织机构分类）分级路由协议平面路由协议可扩展性强弱适应范围大规模网络小规模网络算法复杂度高低健壮性低高安全性低高2.2.4 按路由协议的功能分类按照功能进行分类Ad Hoc路由协议分为是否支持组播机制、QoS服务、单项链路、安全机制等增强功能。从是否支持组播看，支持一点到多点的有选择广播服务的Ad Hoc路由协议为组播路由协议，否则为单播路由协议。常见的组播路由协议有CBT-W1M(The Core Based Trees Wireless Multicast Protocol) 和ST-WIM ( The Shared Tree Wireless Multicast Protocol)。CBT-WIM是一种基于核心树的组播路由协议，在组播组初始化时建立核心树CBT。每个组播组有一个唯一地址和核心的组播服务器。ST-WIM是一种基于共享树的无线组播路由协议，移动节点需要维护一棵不断变化的共享树，它需要很大的存储空间和较多的网络资源，容易发生数据拥塞，其优点是算法结构简单，功能强健。由于Ad Hoc网络动态拓扑结构、带宽资源有限等特性，QoS保障具有很大的困难，因此，QoS路由成为研究热点和难点。目前支持QoS功能的路由协议很多是对现有Ad Hoc路由协议进行改进而成。采用合理的路由技术使网络整体的性能得到提高是QoS保障的前提。常见Ad Hoc网络的QoS路由协议有基于网格的路由协议QoS-GRID，基于AODV和TORA的路由协议QoS-AODV &QoS-TORA，基于最优链路状态的路由协议QoS-OLSR，ADQR(Adaptive Dispersity QoS Routing)等。在Ad Hoc网络中，由于地理环境、传输损耗、天线方向和噪声对发射接受功率的影响，可能会造成链路的不对称性，形成单向链路。目前有些路由协议必须在对称链路上运行如AODV，有些路由协议可以在单向链路上运行如DSR。2.3 几种常见的典型的路由协议目前常见的典型的Ad Hoc路由协议主要有DSDV、WRP、DSR、AODV、TORA、CGSR、ABR等几种22，其中，主动路由协议DSDV 、WRP，被动路由协议DSR、AODV、TORA，分级路由协议CGSR，基于联合度量的路由协议ABR。下面对以上几种常见的典型的Ad Hoc路由协议的基本工作原理和优缺点进行简单介绍。2.3.1 表驱动路由协议表驱路由又叫主动路由协议，其路由发现策略与传统Internet路由协议非常相似：在网络中周期性广播路由信息分组，维护更新路由信息，主动发现路由。每个移动节点需要维护一张包含到达其它所有节点的路由信息的路由表，随着网络拓扑结构的变化随时更新路由表，它准确地反映网络的拓扑结构。其优点是当源节点需要发送数据分组时，直接查找路由表，寻找去往目的节点的路由，所需的延时很小。缺点是为了尽可能使得路由更新能够能准确反映当前拓扑结构的变化，需要花费大量开销来维护路由表。然而，由于动态变化的拓扑结构很难使路由表更新信息准确地反映网络的拓扑结构，从而使得路由协议始终处于不收敛状态。最初，研究ad hoc网络路由协议，主要是通过修改Internet路由协议使其适应MANET网络运行环境。这些路由协议大多属于表驱动路由，但由于其在处理网络拓扑发生变化的方法和所需要的表的数目而有所不同。根据其拓扑结构的管理层次来看，可以分成两类：平面路由和分级路由。在平面路由中每个移动节点需要维护更新到网络中所有节点的路由表。如果网络中移动节点数较少，整体性能没有多大影响，然而，随着移动节点的数量增加，路由开销随着增加。因此平面路由算法只适合小型网络，其扩展性并不好，为了更好地实现网络的扩展性能，通常使用分级技术。下面介绍几种典型的表驱动路由协议。（1）DSDV(Destination-Sequenced Distance-Vector) 27目标序列距离矢量(DSDV) 协议是基于经典的Bellman-Ford路由算法28的表驱动路由协议，在DVA基础上进行改进设计，通过序列号机制区分新就路由，防止可能发生的路由环路。它被认为是最早的自组网路由协议。在DSDV中，每个移动节点维护其可以到达的所有移动节点的路由表，其中记录所有可能到达的目的节点、由目的节点分配序列号、到达目的节点度量值（最小跳数），该序列号标识新旧路由，避免出现路由环路。如果有新的路由条目出现，它采用序列号最大的条目；如果序列号相同，它采用度量值最小（跳数最小）的条目。移动节点周期性的向其邻节点发送路由信息，而不是采用洪泛的方式。周期性的更新路由表需要一定的时间，同时占用大量带宽，增加了路由开销，为了减少路由开销，通常使用两种类型的信息交换，即时间驱动或事件驱动。根据路由表的更新程度可分为：全部更新和增量更新。全部更新就是将整个路由表向其邻节点发送；而增量更新只向其邻节点发送变化了的那部分路由信息。当网络拓扑结构相对稳定时，增量变化较少，使用增量更新可以避免额外的通信量，有利于减轻网络负担。但是在一个快速变化的网络中，增量变化几乎就是整个路由表，因此经常会用到全部更新。由于需要周期性地更新信息，DSDV仍然产生了大量的网络开销，它以O（N*N）增长。因此，路由更新处理需要占用大部分网络带宽，DSDV协议不适合于大型网络。（2）WRP(Wireless Routing Protocol)无线路由协议(WRP)是先验式距离矢量路由协议，是在路径发现算法（Path Finding Algorithm，PFA）基础上改进设计的,以减少路由环路的出现。每个移动节点需要维护四张表：距离表、路由表、链路代价表和信息重传表。节点X的距离表由它的邻居节点Z到每个目的节点Y的距离和通过Z的路径的下一邻居节点组成。节点X的路由表由X的上一跳和下一跳信息、从X到每个目的节点Y的距离以及是简单路径、或者是环路、或者是无效路由的标签信息组成。通过节点的上一跳和下一跳信息进行环路探测和避免无穷计数。链路代价表由每个邻居节点到该节点的链接代价和从那个邻居节点收到无错信息后的超期次数。信息重传表(MRL)包含哪个邻居节点没有应答更新信息的信息，有利于向该邻居节点重传此更新信息。节点通过周期性地或者链路状态触发来与其邻居节点交换路由信息。收到更新信息的应答列表中的节点进行应答，当收到一个更新消息的应答后，节点修改其(MRL)。如果节点路由表自从上次更新后没有变化，节点将被要求发送一个“Hello”消息来检查是否与邻居节点连接。一旦收到更新消息，移动节点将修改其距离表，并利用新信息来查找更好的路径，并将新发现的更好的路径传回给其原节点以修改其表。无线路由协议(WRP)的唯一特点是通过探测到其任何邻居节点的链接变化情况，如有变化，则检查其邻居列表的一致性，从而有利于消除路由环路和加速收敛。WRP不仅很好地消除路由环路，还充分利用前一跳的信息消除了临时路由环。然而，一旦网络规模扩大将产生大量的存贮开销用来维护每个节点的四张路由表。它的另一个缺点是当节点路由表自从上次更新后没有变化，节点将被要求发送一个“Hello”消息来检查是否与邻居节点连接，这大大地消耗了有限的网络带宽，为了发送“Hello”消息，每个节点始终处于活动状态，将消耗大量的能源，对于能量有限的移动节点来说是致命的。2.3.2 按需驱动路由协议按需路由协议又叫被动路由协议，与表驱动路由协议（主动路由协议）相反，按需路由协议认为Ad Hoc网络是一个动态拓扑结构的自组织网络环境，不需要维护更新整个网络的路由信息。它只有在没有到达目的节点路由信息的时“按需”进行路由发现。它的优点是不需要周期性在网络中广播路由信息，维护更新路由表，节省大量的网络资源（如带宽、电源等）。缺点是发送数据分组