Ad Hoc网络路由协议综述

摘要：文章分析了Ad Hoc网络的特征以及路由设计协议所面临的问题与挑战，综述了Ad Hoc网络的传统路由协议，针对理想自组网路由协议应满足的7个方面，着重对适用于不同业务需求和网络需求的路由协议进行了介绍，为Ad Hoc网络路由协议的进一步研究提供了参考。
关键词：Ad Hoc网络；路由协议；改进型；综述

    移动Ad Hoc网络(MANET)是由一组带有无线收发装置的移动节点形成一个多跳的、临时性的自治系统。整个网络没有固定的基础设施，每个节点都是移动和动态变化的，可以随时随地快速进行部署。与有中心网络相比，Ad Hoc网络灵活、健壮、投资少，具有自组织性、自成形性并能够根据应用需要快速形成．特别适合于作战指挥、抢险救灾以及应付突发事件和执行临时任务的场合。因为自组网中节点的传输范围有限，源端向目的端发送数据时，通常需要其它节点的辅助，所以路由协议是自组网中不可缺少的一部分。由于Ad Hoc自身复杂多变的动态特性，路由协议的设计目前仍是一个人们关注的热点问题。

1 Ad Hoc网络的特征及路由协议设计面临的挑战
    在Ad Hoc网络中，网络拓扑、移动节点的分布情况及其自组织能力对Ad Hoc网络都具有重要的影响。正是因为Ad Hoc网络具有其自身的特征，为路由协议的设计提出了新的问题和挑战，主要表现在以下几个方面：
    1)网络拓扑动态变化与多播支持。网络节点可以任意自由移动，因此网络的拓扑可以随时发生快速动态随机的变化。这使得Ad Hoc网络中多播树不再是静态的，所以多播路由协议必须能够处理节点的快速移动和动态地加入与离开。
    2)多跳信道共享与单向信道支持。Ad Hoc网络中节点之间的信道共享采用多跳的模式。当目标节点不在源节点的传输范围之内时必须借助其他节点进行中继转发。由于网络内的所有节点共享同一信道，所以形成了多跳模式的信道共享。同时，因发射功率、地理位置等因素的影响，可能存在单向信道，因此必须解决好认知的单向性、路由的单向性和汇点的不可达等问题。
    3)对QoS的支持。QoS的支持主要是指能够保证用户所规定的一些服务特性，如延迟、带宽、丢包率等。在无线自组网中，需要同时考虑网络层和MAC层的QoS，必须充分考虑节点的动态性、终端的隐藏性和链路的波动性，深入研究支持端对端的QoS和自适应的QoS。
    4)带宽有限性。无线信道的容量比有线信道要低，且易受噪声、路径衰减、多径衰落等因素的影响，所以实际能够使用的信道带宽十分有限，而且随时间和环境的变化而变化。因此，必须充分考虑信号衰减、噪音干扰、信道间干扰等多种因素。
    5)安全机制受限。和传统有线网络相比，这种网络更容易受到物理上的安全威胁。无线信道的广播特性致使Ad Hoc网络易受来自恶意节点的攻击，如偷听(Eavesdropping)和拒绝服务(Denial-of-Service)，而且Ad Hoc网络缺乏固定的网络基础设施进行用户认证和授权。
    6)能量有限性。Ad Hoc网路中的节点一般依赖于电池进行正常的工作。有限的电池能量不仅用于处理节点自身的数据，还用于处理和转发来自其它节点的数据。因此，必须考虑电源因素。
    7)地理位置支持。在Ad Hoc网中利用位置信息，可以使节点在寻找路由时避免简单的洪泛：利用相邻节点或目的节点的位置信息，可以提高路由寻找的效率，即路由是空间的。

2 传统路由协议及其特性
    无线自组网路由协议具有预先获取(proactive)和按需获取(reactive)两种路由策略。其中，主动路由采用Proactive策略，按需路由采用Reactive策略。本文根据协议的工作机制将现有协议分为3类：主动路由协议、按需路由协议及混合路由协议。
2．1 主动路由协议
    要求每个节点维护一张或几张路由表，其中包含了网络中所有其他节点的路由信息。所有节点周期性地更新这些路由表，以保证路由信息是一致和最新的，当网络拓扑结构改变时，节点向整个网络传播路由变更消息。主动路由的优点是获取路由的延时小。因为每个节点都保存着到其它节点的路由信息，这非常适合于有实时要求的应用。缺点是需要花费较大的开销保持路由更新。当网络规模较大、移动速度较高时，会消耗大量的带宽和节点能量，同时也浪费了一些资源来建立和重建那些根本没有被使用的路由。
    主动路由协议主要有DSDV、WRP、CGSR、GSR、AGSR、FSR、HSR、ZHLR、LANMAR，研究最深入的是基于经典Bellman—Ford算法基础之上的表驱动路由协议DSDV。
2．2 按需路由协议
    与主动路由协议不同，按需路由协议只有在需要时才进行路由发现，以缓解主动路由协议由于周期性交换更新信息带来的开销和扩展性问题。这类协议一般通过请求／应答过程来发现到一个目标的路由。在需要路由信息时，都经过一个路由发现阶段。当节点要发送数据包时，先以泛洪式广播路由请求包。当路径发现后或者所有可能的路径都查找完时这个阶段结束。接下来路由维护阶段一直持续到这条路由不再需要或者目的地变成不可到达时。采用按需路由协议的优点是不需要进行周期性的路由信息广播，节省了一定的网络资源；缺点是获取路由延时相对较大、出现“广播风暴”以及单向链路问题。
    按需路由协议主要有AODV、DSR、ABR、SSR、CBRP、LAR，常用的有AODV、DSR、TORA等。
2．3 混合路由协议
    混合路由协议是在Ad Hoc网络规模大、组成员关系变化快、而少量成员的位置和链路连接状态稳定的条件下提出的。它结合主动和按需两类路由协议，避免了主动路由协议中过量的控制消息流量问题和按需路由协议中的长时延问题，达到取长补短的效果。此类协议的关键点在于两种协议应用区域的划分，合理的划分方法应该随不同情况采用自适应的策略，协议的性质在主动和按需之间应随网络的具体环境变化可以自动调整。
    混合路由协议主要有ZRP、DDR、CEDAR、HARP、BRP、IARP、IERP等，其中最具代表性的就是区域路由协议ZRP(Zone Routing Protocol)。

3 改进型路由协议及其特性
    一个理想的自组网的路由协议应当满足以下7个方面的要求：分布式运行、提供无环路由、按需操作、单向信道支持、提供节能策略、可扩展性、安全性。目前，大量的Ad Hoc网络路由协议针对不同的设计要求，使用了不同的技术方法，适用于不同的网络环境。下文将依次介绍在节能策略、QoS支持、GPS辅助、多播支持、多路径支持、安全性等方面具有一定优越性的路由协议。
3．1 基于节能的路由协议
    能量问题是制约Ad Hoc网络发展要解决的主要问题之一。目前提出的具有能量意识的路由协议可以分为四类：最小能量路由(MER)、最小电池耗费路由(MBCR)、最小最大电池耗费路由(MMBCR)、受限的最大最小电池容量路由(CMMBCR)。对DSR协议进行优化，提出以下基于能量控制的改进协议。
    SDDRP(Source-Destination Determined Delay Routing Protocol)：同时考虑网络的连通信息和节点剩余能量来选择路由，在保证网络正常运行的基础上保护了剩余能量不多的节点，均衡了各个节点的能量损耗。
    MMPEW-DSR(Maximum Minimum Power-Energy Weight DSR)：节点剩余能量和传输功率链路状态函数作为路由选择的参数，减少节点的能量消耗，保护低能量节点，延长网络的生存时间。
    TBDB(Traffic balanced Degree-based)：选择路由的原则是最小条路由，由节点根据本身负荷的情况决定是否作为新建路由的转发节点，对可选的路径集合进行了限制，避免了拥塞路径，获得了很高的网络利用率。
3．2 基于QoS的路由协议
    Q_AODV根据带宽来选择QoS参数，为每个路由条目定义了5种状态：空闲、接收路由请求、已经预约、上游断路和下游断路，为每个状态设置计时器来保证QoS的有效性。当计时器超过或者收到路由控制消息，节点转移到另外一个状态。
    CEDAR(Core-Extraction Distributed Ad Hoc Routing)根据带宽来选择QoS参数，是一种分级路由协议。它通过在网络中建立一个稳定的虚拟核心来扩散路由信息，按需式的且由核心节点基于局部状态计算路由，适用于中小规模的移动Ad Hoc网络。
    STARA(System and Traffic Dependent Adaptive Routing Algorithm)根据平均时延最短来选择QoS参数，该协议采用最短路径算法计算路径，但“最短”路由度量采用平均延时时间，而非跳数，即在进行分组路由时，考虑无线链路的容量和排队延时等因素。
    ABGP(Advanced Bandwidth Guaranteecl Routing)根据电池剩余量和带宽选择QoS参数，采用了多种限制扩散的机制来解决网络中盲目扩散而导致的带宽损耗问题，并充分考虑了节点的电能受限问题，试图在路由选择的过程中延长网络的完整性，避免由于部分节点过早地耗尽电能而使网络被分割。
    TBP(Ticket-Based Probing)是基于标签探测的路由协议，该协议基于标签方式进行一跳一跳地寻找出多条较优的路径。首先源节点发送标签来探测路径，如果发送的标签只有n个标签，那么最多就只能找n条路径；其次中间节点收到标签，根据自己以往统计信息，判断是否要拆分标签并重新分发标签，发往代价最小的下游结，最后目的节点响应相应多条路径给源节点。
3．3 基于GPS辅助的路由协议
    在自组网中利用GPS提供的有关节点位置信息，可以使节点在寻找路由时避免简单的洪泛；利用相邻节点或目的节点的位置信息，可以提高路由寻找的效率。其缺点是依赖于GPS可能限制其应用范围。该类协议的关键点是如何有效利用GPS提供的位置信息又能尽量减小交换位置信息带来的开销，以免得不偿失。典型协议的有以下几个：
    DREAM(Distance Routing Effect Algorithm For Mobility)的特点就是距离效应和移动速率两个规则的运用。每个节点维持一个包含所有节点位置信息的表，根据上述规则定期广播控制信息来通知其它节点自己的位置信息。DREAM对于节点移动速度表现出很好的强壮性，但是在重负荷环境下效果较差。
    LAR(Location-Aided Routing)利用GPS提供的信息执行一种“有限泛洪”路由请求方式。需要发送路由请求包时，源节点根据目标节点的位置和速度信息计算一个区域作为请求范围并附之于包头。只有位于请求范围内的节点才可进行路由请求信息的转发，从而减小了发现路由的开销。
    此类协议还包括GPSR、GRA、GLS、GEOCAST、GEDIR等。
3．4 基于多播的路由协议
    多播是一种一点对多点或多点对多点的分组传输方式，它能够最优化地利用网络资源，很好地适应Ad Hoc网络带宽受限和能量受限的环境，提高网络的整体性能。多播路由协议设计的基本思想是以最少的冗余建立组成员的路径。根据采用转发结构、拓扑结构的不同，可分为：基于树多播协议、基于格网多播协议、混合多播协议和无状态多播路由协议。
    基于树的多播路由协议在有线网络中具有突出的优越性能，将其特性运用于Ad Hoc网络，设计出适合Ad Hoc网络的典型协议有MAODV、AMRIS、LGT、LAM、ABAM、ADMR。
    基于格网的多播路由中，多播发送者与接收者问存在多条路径，这就提高了网络的动态适应能力，健壮性好，不需要因为少量链路的失效而重新配置多播网结构，路由维护开销少。典型的基于格网多播路由协议有ODMRP、CAMP、FGMP、NSMP。
    基于树的多播路由具有较高的分组转发有效性，但鲁棒性差。基于格网的多播路由鲁棒性好，但以牺牲有效性为代价。混合的多播路由综合了两种多播路由的优点来提高总体性能。典型的混合多播路由协议有AMRoute协议和MCEDAR协议。
    无状态的多播路由主要用于小规模的多播，并由单播路由协议根据分组的报头转发到各个接收者，避免了因频繁的拓扑变化导致的开销过大，但可扩展性较差。典型的无状态多播路由协议是DDM。
3．5 基于多路径的路由协议
    多路径路由是指在Ad Hoc网络中找出到达目的节点的多条路径，作为当前路径的备份路径，当前路径断裂后，从备份路径中选择一条最佳路径继续进行路由，从而提高带宽使用效率，增加传输可靠性以及减轻拥塞，实现网络负载均衡和网络资源的充分利用。现有的多路径路由协议大多是在原有单路径路由协议的基础上通过添加多路径的方法实现的。
    D—AOMDV协议是对AODV路由协议的多路径扩展，以距离矢量概念为基础，通过计算多条开环、节点或链路不相交路径，充分利用已有的有效路由信息，达到提高路由效率的目的，在动态高速环境下具有较高的效率。
    文章提出了一种新的多路径路由算法。该算法基于稳定性因子计算路径间海明距离并据此选择多条相似的稳定不相交多路由，从而进一步提高该路由算法的性能。
    目前多路径路由协议还有OLSR、OSPF、TYBRPF、AOMDV、TORA、MP—DSR、ROAM、SMR等。
3．6 基于安全机制的路由协议
    Ad Hoc网络具有分布式控制、开放传输媒介、有限传输带宽和有限终端等特点，路由协议中引入安全机制尤为重要。移动Ad Hoc网络的安全策略分为三类：加密、检测和冗余路径。目前典型的安全路由协议有以下几种：
    ARIADNE协议是在DSR的基础上开发的，该协议在TESLA广播认证协议的广播认证消息中添加MAC保证路由安全。采用类单向Hash链表在两个端节点之间建立共享对称密钥来保证端到端的完整性。该协议可以防止恶意节点进行路由黑洞攻击，主要缺点是需要时钟同步。
    SEAD协议构建于DSDV基础上，该协议利用Hash链表来认证路由更新信息的序列号、度量值和跳数，并提出了节点之间的相互认证机制。该协议可以抵御黑洞攻击及一定程度的DoS攻击，但需要同步时钟，且无法抵御增大度量值的伪造攻击。
    ARAN协议是基于按需路由协议开发的，该协议利用公钥证书体制提供消息鉴别、完整性以及不可抵赖性等安全机制，可以检测和防止Ad Hoc网络中的第三方和窥探者的攻击。ARAN的缺陷在于路径中每个节点仅有下一跳信息，因而无法保证路径的最优性。
    此外该类协议还有SRP、SAR、MRM、SNS、NUGLETS等。

4 结束语
    由于Ad Hoc网络复杂多变的特性，路由协议设计仍是Ad hoc网中一个非常重要的研究方向。当前，虽然此项研究取得了较大进展，但出现的各种网络路由协议都只是在某些性能上具有优势，只能满足部分需求。设计一种快速、准确、高效、可扩展性好的Ad Hoc网络协议，必须综合现有各种路由协议的优点并加以改进完善，尚需开展大量的研究工作。此外，Ad Hoc网络与蜂窝网的结合技术ODMA(机会驱动多址接入)以及Ad Hoc网络中OFDM(正交频分复用)技术的运用也是研究的热点。