工程硕士学位论文
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是基于按需驱动的源路由协议，节点通过洪泛方式查找到路由后将完整的路由信息写入数
- 9 -
基于位置预测的Ad hoc网络路由协议研究
据报头，中间节点不需要维护任何路由信息，只需根据数据报头中的信息进行转发。当路由跳数过多时，源路由在数据包中占地比重较大，会降低网络的传输效率。
反向链路(Link reversed)算法的设计思想完全相反(链路状态协议追求的是以最快的速度将链路变化通知到全网) ，其核心是将由于拓扑结构变化而引起的连锁反应限制在局部区域内，它适合于拓扑结构快速变化的网络，具有很好的自适应能力。基于反向链路的算法有TORA[26]。
2.2.3 按网络拓扑结构分类
按照网络管理的网络拓扑结构来分，路由协议可划分为平面结构和分级结构两类。平面结构就是网络中所有移动节点在路由功能上具有同等地位，它们之间没有功能的差别，不必要引入分层管理机制。平面结构路由的优点是节点在网络中地位平等，没有特殊的节点，数据流量在网络中均匀的分布，路由算法简单易于实现，鲁棒性强。缺点是可扩展性差，在很大程度上限制了网络规模的扩展。常见的Ad Hoc路由协议大部分属于平面结构路由协议，如：DSR，AODV，TORA，WRP，ABR等。
图2.2 分级结构路由算法示意图
分级结构路由算法是将移动节点划分成多个簇进行层次管理。如图2-2所示，它将某一区域的若干个移动节点划分为一个簇，每个簇设一个簇首节点。无论是簇首节点还是其它的簇成员都可以作为网关，网络通过网关连接构成主干网，主干网通过簇间协议完成簇间数据通信；簇内的移动节点通过簇内路由算法进行数据通信。分级协议具有很好的可扩展性，适合规模较大的网络。
分级路由协议主要由簇管理协议，簇间路由协议和簇内路由协议。簇管理协议包括：一、如何实现移动节点在动态分布式网络环境下高效的成簇，它是分级路由协议的关键。二、如何实现动态分布式网络中簇结构维护，即簇的产生和消亡，簇首的更改，以及移动节点的进入和退出等。分级结构路由协议存在的主要问题是管理的复杂性导致算法复杂度和路由开销的加大；另一个缺点是簇首节点作为关键节点，一旦其退出或受到攻击，将影响网络的健壮性和安全性，特别在军事上，网络的健壮性和安全性将具有重要意义。
- 10 -
工程硕士学位论文
常见的分区或分级结构路由协议有：ZRP (Zone Routing Protocol)，ZHLS (CZone Based Hierarchical Link State Routing)和RoutingProtocol) 。
分级结构路由协议与平面路由协议的基本性能比较如表2.2所示。
表2.2 路由协议性能比较（按逻辑组织机构分类）
可扩展性 适应范围 算法复杂度 健壮性 安全性
分级路由协议 强
大规模网络 高 低 低
平面路由协议 弱
小规模网络 低 高 高
CBRP(Cluster Based
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。
- 11 -
基于位置预测的Ad hoc网络路由协议研究
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中，每个移动节点维护其可以到达的所有移动节点的路由表，其中记录所有可能到达的目的节点、由目的节点分配序列号、到达目的节点度量值（最小跳数），该序列号标识新旧路由，避免出现路由环路。如果有新的路由条目出现，它采用序列号最大的条目；如果序列号相同，它采用度量值最小（跳数最小）的条目。
移动节点周期性的向其邻节点发送路由信息，而不是采用洪泛的方式。周期性的更新路由表需要一定的时间，同时占用大量带宽，增加了路由开销，为了减
- 12 -
工程硕士学位论文
少路由开销，通常使用两种类型的信息交换，即时间驱动或事件驱动。
根据路由表的更新程度可分为：全部更新和增量更新。全部更新就是将整个路由表向其邻节点发送；而增量更新只向其邻节点发送变化了的那部分路由信息。当网络拓扑结构相对稳定时，增量变化较少，使用增量更新可以避免额外的通信量，有利于减轻网络负担。但是在一个快速变化的网络中，增量变化几乎就是整个路由表，因此经常会用到全部更新。
由于需要周期性地更新信息，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”消息，每个节点始终处于活动状态，将消耗大量的能源，对于能量有限的移动节点来说是致命的。
- 13 -