基于Ad Hoc网络的路由协议的分析比较

基于AdHoc网络的路由协议的分析比较

徐春丹，吕玉琴

北京邮电大学电子工程学院，北京（100876）

E-mail：chundanxu@gmail.com

摘 要：Ad Hoc网络是由一组具有路由功能的节点组成的分布式无线多跳网络，它不依赖于任何预设的网络基础设施。因为网络中节点的传输范围有限，源节点在向其他节点发送数据时通常需要借助其他节点的辅助，所以路由协议是Ad Hoc网络中不可缺少的一部分。本文从Ad Hoc网络的特点出发，基于Ad Hoc网络的特点探讨现有的应用协议的性能及特点。通过对典型路由协议DSDV, OLSR, DSR等协议的分析着力分析比较表驱动路由协议族与按需路由协议族的性能控制开销及影响因素，比较他们的优劣，最后由Ad Hoc网络的特点给出在路由协议上可改进的方向。

关键词：Ad Hoc，按需路由，表驱动路由，控制开销，优化

1．引言

Ad Hoc网络是一种不需要任何基站或固定基础设施的多跳无线网络，具有独立组网、自组织、动态拓扑、无约束移动、多跳路由等众多特点，能够快速的布设局部通信网络。

由于它网络拓扑结构动态变化、无线传输带宽有线，移动节点能力有限、需要采用分布式控制方式、安全性差、网络可扩展性不强等不足，要求用于Ad Hoc网络的路由协议必须要充分考虑这些问题。本文在分析了Ad Hoc网络的特点基础上，对现有的路由协议进行分析比较。主要对比两类路由协议：表驱动路由协议与按需路由协议，通过分析他们的协议特点，控制开销等，总结一些可以优化的方法，提出可以进行优化的方向。

2．Ad Hoc网络的特点分析

移动Ad Hoc网络中的每一个节点都兼有路由器和主机的功能，它的特点表现在： (1)移动性与网络拓扑动态性：移动Ad Hoc网络节点可以自由的任意移动，再加上无线发射装置发送功率的变化，环境的影响以及无线信道间的互相干扰等因素致使网络拓扑可能随机、迅速、不可预测的变化。移动首先限制了网络的可扩展性，因此对路由协议的选择也提出了较高的要求。

(2)带宽有限：无线信道产生的碰撞，信号衰减、噪音干扰以及信道间干扰等因素，使移动主机可得到的实际带宽远远小于理论上的最大带宽值。因此在路由协议设计上必须尽可能多的将带宽留给数据传输。

(3)多跳通信方式：在移动Ad Hoc网络中，节点的覆盖范围有限，当网络中的两个通信节点不能处在同一覆盖网络时，可以采用多跳通信，即通过中间节点的多跳转发方式，实现不同覆盖网络之间的源主机之间的通信。

(4)分布式控制：由于移动Ad Hoc网络节点不能依靠固定基础设施或者中心管理，所以移动Ad Hoc网络节点必然是分布式的，各个节点间地位平等，网络路由协议通常采用分布式控制方式。因而它比采用集中式的网络具有更强的鲁棒性和抗毁性。

(5)安全有限：移动Ad Hoc网络的节点间通信由于采用了无线信道、有限电源、分布式控制技术和方式，使传输的信息非常容易受到监听、重发、篡改、伪造等各种攻击，若路由协议遭受到上述恶意攻击，那么整个Ad Hoc网络将无法正常工作。

- 1 -

http://www.paper.edu.cn

移动Ad Hoc网络的特性为移动Ad Hoc网络路由协议设计提出了新的问题和挑战，合理的路由算法必须考虑有限的无线传输带宽、动态变化的网络拓扑结构、有限的网络安全等各方面因素。

3．传统的Ad Hoc路由协议分类

由Ad Hoc网络特点可知，路由协议是移动Ad Hoc网络中不可缺少的一部分，其主要作用是发现和维护路由，在移动Ad Hoc网络中由于节点的任意移动性导致拓扑结构动态、随机且较快速的变化，因此如果使用常规的路由协议在网络拓扑结构变化时，会花费很大的代价重建路由，且协议状态始终处于不收敛状态，占用大量的网络资源，致使信息的传输无法实现，所以就需要有专门的应用于移动Ad Hoc网络的路由协议，它们主要满足下列要求：

(1) 它必须可对网络拓扑结构的变化具有快速反应能力，在计算路由时能够迅速收敛，且在链路失效时必须能避免无穷计算。

(2) 能够提供无环路由且设计应简单实用。

(3) 要能够高效地利用有限的带宽资源，尽可能减少控制管理开销。

(4) 不能对终端节点性能要求过高，且实施多跳通信的中间转接次数是有限的，一般不超过3次。

(5) 在可能条件下，使设计的路由协议具有一定的安全性，以降低遭受攻击的可能性。

现有的用于Ad Hoc网络的路由协议大致可分为平面路由协议与分层路由协议两大类，而分层路由协议中主要包括表驱动路由协议、按需路由协议和混合式路由协议等。

表驱动路由协议又称为先验式路由协议或主动路由协议。网络中的每个节点都要维护一张到其他节点的相对稳定的路由表，当网络拓扑结构发生变化时，节点在全网内广播路由信息更新，使每个节点能连续不断的获得当前网络信息，路有表可以准确地反映网络的拓扑结构，当节点需要发送数据时，可立即获得到达目的节点的路由，适于有实时和Qos要求的通信网络。

按需路由协议又称反应式路由协议或源启动按需路由协议，是一种在需要时才查找路由的路由选择方式。节点不需要维护及时准确地路由信息，当需要发送数据时才在全网内发起路由查找过程，一旦检验完所有可能的路由排列方式或找到新的路由后就结束查找。路由建立后，由路由维护程序来维护这条路由，直到它不再被需要时拆除此路由。

混合式路由协议是将按需路由协议和表驱动路由协议相结合的一种协议，因为在高速动态变化的移动Ad Hoc网络中，使用单纯的表驱动路由协议会产生大量的控制报文，且很多控制报文常常是无用的；如果单独采用按需路由协议，需要为每个报文查找路由，这也是不合理的。因此在许多研究中提出将二者结合的混合式路由协议，在局部范围内采用表驱动路由协议，维护准确的路由信息，并可缩小路由控制消息传播的范围，当目标节点较远时，通过查找发现路由，这样既可以减少路由协议的开销，时延特性也得到一定改善，如ZRP协议。

现有的一些用于移动Ad Hoc网络的路由协议如图1所示。

- 2 -

http://www.paper.edu.cn

图1 Ad Hoc网络协议图

4．表驱动路由协议与按需路由协议分析

本文着力比较按需路由与表驱动路由的性能及开销，下表为两类协议的概要对比。

表1 两类协议的概要对比

比较内容 路由信息的获取

表驱动路由协议 不论是否需要，总可

按需路由协议 在需要时才获取 等待时间较长，随网络规模的

较小

平面路由结构 否

大多数协议支持最短路径，几乎不提供其他

以得到

获得路由的等待时间 等待时间几乎忽略不

计

路由协议开销 路由算法体系结构 是否需周期性路由更新

服务质量Qos支持

大多数协议除了支持最短路径

较大

绝大多数是平面路由结构

是

表驱动路由的一个比较典型的代表为DSDV协议。它是对距离矢量（Distance Vector）算法改进而得。DSDV[1]协议在DV算法中加入了目的节点的序列号。目的节点每次因位置发生变化而与某相邻节点的 连接断开后其序列号变大，而该相邻节点也会更新其序列号，并设其到目的节点的距离为∞。当节点收到多个不同的矢量表数据包时，采用序列号大的来计算；当序列号相同时，比较路径的长短并取短路径节点。目的节点序列号可以区别新旧路由，这样可以避免环路的产生。本协议中的开销反映了表驱动路由开销的特点。

OLSR[1]为另一种表驱动协议，它是为了适应Ad Hoc网络的需求，对纯链路状态算法进行了优化而形成的。它的核心技术在于多点中继（Multipoint Relay）。多点中继的思想是通过减少同一区域内相同控制分组的重复转发次数来减少网络中广播分组的数量的。网络中每一个节点选取其邻节点的一个子集用于转发该节点发送的控制分组。这些被选择的节点称

- 3 -

http://www.paper.edu.cn

为该节点的MPR（Multipoint Relays），而该节点就称为这些MPR的多点中继选择节点（MPR selector）。节点N的MPR是从与N有双向链路的一跳邻居中选择的，因此，通过多点中继选择路由，自动的避开了在单向链路上传输数据分组的问题。这样，节点N的邻节点被分为两类：MPR和非MPR。节点N发送的广播分组通过MPR转发能到达节点N的两跳范围以外的其他节点。对于节点的非MPR，收到来自节点N的广播分组，只进行读取和处理，不进行转发。为此，每个节点都维护着一张MPR selector列表，记录当前有那些节点选择它作为MPR。

每个节点从其一跳邻居中选择自己的MPR集，使得该节点通过这个集合转发的分组能够覆盖该节点的所有两跳邻节点。节点N的多点中继集MPR(N)是节点N的邻节点的任意子集，它满足以下条件：N的每个两跳邻节点都必须有到达MPR(N)的双向链路，且节点N与MPR(N)间的链路也是双向的。MPR集越小，路由协议性能越好。下图给出节点N的点中继集MPR(N)。

图2 多点中继选择

OLSR对纯链路状态算法所做的优化在于：

（1） 采用多点中继机制减少了控制分组的洪泛范围：节点选择部分邻节点作为它的多点中继节点MPR，只有它的MPR才转发该节点发送的控制分组，其他邻节点收到该节点发送的控制分组时，只进行处理不进行转发。这样减少了网络中广播的控制分组的数量。

（2） 缩减了控制分组的大小：节点并不发布与所有邻节点相连的链路信息，而只发布它与部分邻居的链路子集，这些邻居是它的多点中继选择节点（MPR Selector），即节点只发布与它的MPR Selector间的链路。

在表驱动路由协议中，开销[2]主要包括用于邻节点探测的HELLO分组和用于路由更新与信息交互的拓扑控制(Topology Control，TC)分组，不同的表驱动路由协议的区别在于两种分组在网络中传播的方式和需要存储的表的类型不同。

表驱动路由协议没有明显的路由发现过程，无论网络拓扑有没有变化，节点间都要通过周期性的广播TC分组来交互路由信息，以确保路由信息的正确性。当有重要的新信息时也需要广播TC分组。链路失效时路由表同样需要维护。节点定期的发送HELLO分组来检测

- 4 -

http://www.paper.edu.cn

邻节点的状态以确保节点间的 连通性，HELLO分组可以不携带任何更新消息。发送两个HELLO分组之间的时间间隔称为Hello Interval,若某个节点在规定的Hello Interval内没有收到邻节点发送的任何分组或之间检测到邻节点的链路失效，该节点就广播一个更新分组。如果某个节点收到了新节点的HELLO分组，则把新节点信息加入路由表中，并把自己保存的信息发送给新节点。

而按需路由协议开销主要用于路由的建立和用于失效链路检测的控制分组，包括请求分组(RREQ)、应答分组(RREP)和出错分组(RERR)等。按需路由协议分为路由发现和路由维护两个阶段。当需要发送数据时，源节点首先检查路由表中是否有到达目的节点的可用路由，若有则直接发送，否则通过广播RREQ分组发起路由发现过程，RREQ分组中包含广播ID、最大跳数、源节点和目的节点地址等路由信息。其他节点收到RREQ分组后，检查源地址和标识号是否已经收到过，如果收到则丢弃该分组。如果自己的路由表中有到目的节点的路由，则复制路由记录表到RREP分组中，并反向发送到源节点。否则，将自己的地址加入到路由记录表，重新广播这个RREQ分组，直到源节点收到目的节点的RREP分组，将路由信息存入路由缓冲器中，路由发现过程结束。

在按需路由协议中，路由维护只针对那些正在使用的路由。若数据分组在传输过程中检测到链路失效，链路上游节点则向源节点回传一个RERR分组。收到RERR分组后，源节点从路由缓冲条目中删除所有不可到达的路由（这条路径的中间节点也利用这个信息更新路由缓冲器）。若路由表中没有备用路由，源节点将重新启动新的路由发现过程。

下面通过介绍几种典型的按需路由协议来进一步说明。DSR(Dynamic Source Routing)动态源路由协议是一种基于源路由的按需路由协议。它使用源路由算法，每一个给定路线的数据分组都在报头带有完整、有序的此分组必经的节点列表。使用源路由可以保证无环路，转发或者侦听分组的节点可以缓存分组中的路由信息以备后用，而且由于要传输的数据分组已含有必要的路由信息，中间节点不必保存路由信息。图3说明了一个应用源路由在Ad Hoc网络中传输数据分组的例子。网络中共有9个节点，节点9向节点2发送数据分组，节点9建立路由后，将路由信息写到数据分组报头，如图中节点4处的分组示意图。中间节点按照数据分组报头的路由信息转发分组。

DSR协议主要包括两个过程：路由建立和路由维护。这两个过程都是按需的，当节点S向D发送数据时，它首先检查缓存中是否存在到目的节点D的有效路由。如果存在则直接使用，否则启动路由建立过程。具体过程如下：源节点S将使用洪泛法发送路由请求消息(RREQ)，RREQ包含源节点地址、目的节点地址、唯一的标志号及中间节点列表；中间节点转发RREQ，并附上自己的节点标识；当RREQ消息到达目的节点D或任何一个缓存有到目的节点路由的中间节点时（此时，RREQ中已经记录了从节点S到D或该中间节点的所经过的节点），节点D或该中间节点将向S发送路由应答消息（RREP），该消息中将包含节点S到D的路由信息，并反转节点S到D的路由供RREP消息使用；节点S收到RREP后，路由建立过程结束，通信开始。在通信过程中，当中间节点检测到通往目的节点的下一跳链路中断时，它将从自己的路由缓存中移去包含该链路的路由并向节点S返回一个路由出错分组RERR。节点S收到路由出错分组后，触发一次新的路由建立。

- 5 -

http://www.paper.edu.cn

图3 DSR传输数据实例

针对路由协议的开销问题，目前已经提出了许多路由开销优化的方法和策略。 （1） 洪泛（Flooding）优化技术。洪泛作为最简单的广播方式广泛应用于Ad Hoc网络路由协议中，特别在网络动态变化剧烈的情况下，洪泛可能是最基本和最健壮的方式，但是洪泛具有很大的盲目性，消耗了大量的带宽，路由开销大。因此，提高洪泛效率，降低路由开销是优化路由协议的有效途径。LAR(Location-Aided Routing)在地理位置信息的支持下，通过限制在Ad Hoc网络中搜索的范围，使路由控制分组的数量显著减少。DREAM(Distance Routing Effect Algorithm for Mobility)利用定向洪（Directed Flooding）技术限制了到达目的节点的洪泛范围，从而控制分组的数目和控制分组在网络中的传播范围。文献[]提出了一种相对密度自适应的泛洪广播算法，该算法可以根据网络中各节点的实时密度（即该节点的实时有效邻节点数），合理的选择需要转发的邻节点，在不降低分组传输有效性的前提下，减少了路由开销。另一种常见的洪泛优化技术是在分组中加入TTL域，将分组的传播限定在一定的范围内，像AODV在路由发现阶段用的扩展环搜索（ERS）技术。OLSR采用多点中继（Multipoint Relay）机制减少控制分组的洪泛范围，多点中继的思想是通过减少同一区域内相同控制分组的重复转发次数来减少网络中广播分组的数量，也是对洪泛的一种优化。

（2） 多范围（Multi-scope）技术。在大规模Ad Hoc网络中，受传播时延和节点移动性的影响，距离节点越远的链路状态信息准确性越差，对路由计算的意义越小。多范围技术就是通过减少对这些节点的控制信息来达到降低路由开销的目的。ZRP(Zone Routing Protocol)以多范围技术为基础，划分了不同的路由区域，在不同的区域采用不同的路由策略，并可以根据网络特性等对节点的路由区域半径进行调整，使系统的整体路由开销最小。FSR(Fisheye State Routing Protocol)模仿鱼眼的生理特性对节点划分不同的鱼眼范围，通过不同鱼眼范围内采用不同的路由更新频率使距离越近的节点掌握的路由信息越精确。由于其路由更新分组仅在邻节点之间交换，所以降低了路由的控制开销。

（3） 增量消息技术（Increment HELLO）。增量消息技术是一种常用的降低路由开销的技术，节点向邻节点报告拓扑信息、路由表信息时，只报告对应信息的变化部分，这样可以减小控制开销的长度，从而降低开销。TBRPF(Topology Dissemination based on Reverse-Path Forwarding)中的节点在邻居发现模块通过周期性的发送“增量HELLO”分组，只报告发生变化的邻节点的状态信息，不报告所有邻节点的状态信息，所以其分组长度要小的多。

（4） 按需（On-demand）路由策略和最小开销算法(LORA)。在网络负载较轻的情况下，按需路由协议的路由开销要比表驱动式路由协议的路由开销小的多，因为按需路由是

- 6 -

http://www.paper.edu.cn

被动的发起路由发现过程，省去了大部分的路由维护开销。有的表驱动式路由协议为了降低开销，局部采用按需方式。由于激活路由的平均开销要远远高于表驱动路由协议的平均开销，所以在网络负载较重的情况下，按需路由的平均开销会很大。最小开销算法的思想是在协议能够正常运行的前提下使控制分组的开销达到最小，并不追求路由的最佳化，这样就不用频繁的更新路由表，从而降低了开销。STAR(Source Tree Adaptive Routing)就是采用最小开销算法，使自己的控制开销达到了一个较低的水平。

5．结束语

与有线网络相比移动Ad Hoc网络具有许多独特之处，如它不依赖于网络中的某一个固定设备，自组织并且具有很强的抗毁性，然而，它的优点也从一个方面反应了它在实现上对系统路由的要求，目前的主流路由算法网网仅仅在一个方面上满足了Ad Hoc网络的性能需求，并不能满足它所有的需求，因而如何进行折中考虑进而选择一种适合路由协议将显得尤为重要，这也为以后的基于Ad Hoc网络的路由协议研究提出了新的要求。

参考文献

[1] 陈林星，曾曦，曹毅 “移动Ad Hoc网络——自组织分组无线网络技术”电子工业出版社2006年4月 [2] 张敏，张焕生，王世伟 “移动AdHoc网络及其路由协议剖析” 河北省科学院学报2007年6月

[3] 张强，余立建，林国军，何玉婉 “无线Adhoc网络典型路由协议的网络性能分析” 成都大学学报2007年9月

[4]于宏毅等 “无线移动自组织网”人民邮电出版社2005年4月

[5] 李士宁，张琪，于超 “基于AdHoc网络路由协议的控制开销研究” 微电子与计算机 2007年第24卷第7期

[6]李园，孙雅东，黄超 “基于TCP的Ad Hoc路由协议分析” 吉林大学学报 2007年1月第25卷第1期

The Analysis And Comparison On Routing Protocols In Ad

Hoc Network

Xu Chundan，Lv Yuqin

Beijing University of Posts and Telecommunications，Beijing （100876）

Abstract

The Ad Hoc network is a distributed wireless network composed of a group of nodes which have routing ability. It doesn’t depend on any exsited network facilities. Because of the limited scale of transfering between nodes, source node relies on other nodes’ help when transtering data. From this aspect, effective routing protocols are necessary for Ad Hoc networks. Based on the characteristics of Ad Hoc networks, the author analyzed the existing routing protocols, and did some comparison between the list-driven routing protocols and on-demand routing protocols. Finaly, the improvements on existing routing protocols were proposed.

Keywords：Ad Hoc，Routing On Demand，Routing Driven By List，Control Overhead，Optimize

作者简介：徐春丹，女，北京邮电大学硕士研究生，研究方向是P2P网络，协议及信息安全。

- 7 -