马文奇
摘要
相对于单路径路由而言，多路径路由在容错、路由可靠性、QoS路由等方面有很多优势。因此，为了进一步提高移动AdHoc网络的路由质量，多路径路由问题逐渐成为了近年来的一个研究热点。首先在分析传统的单路径路由协议的特点和不足的基础上，阐述了多路径路由的基本概念及其分类，以及多路径路由的优势。然后介绍了移动Adhoc网络中多路径路由技术的最新研究进展，并对有关多径路由协议进行了评述。
1、引言
移动自组网（MobileAdHocNetwork，MANET）[1]是多个具有路由功能的移动终端（节点）组成的无线多跳网络，数据的传输需要多个节点的协作才能完成，所以路由协议是MANET中至关重要的一部分。
MANET的路由设计需要综合考虑用户业务需求、网络能力和状态信息、MANET的特点和运行环境、路由协议基本功能等诸多因素。与传统有线网络相比，MANET有自己的特点，如分布式控制、动态变化的网络拓扑结构、无线传输带宽和节点能力有限、安全性差、网络可扩展性不强以及生存时间短等。理想的MANET路由协议应该具有以下特点：
（1）采用分布式路由算法。MANET是一种无中心的分布式控制网络，所以分布式算法更适合于MANET。
（2）具有自适应能力，可适应快速变化的网络拓扑结构。MANET的拓扑结构是动态变化而难以预测的，所以路由必须具有自适应能力。
（3）无环路。无环路是任何路由协议的基本要求，可以避免路由错误和带宽浪费。
（4）路由计算与维护控制开销少。用最简单的方法、最小的控制开销做到最完整、最强大的功能是所有路由协议共同努力的目标。
（5）具有可扩展性，适应于大规模网络。
（6）安全。网络安全是MANET从理论走向实用的重要挑战。
2、传统单路径路由协议
2.1单路径路由协议概述
根据路由建立的方式不同，MANET路由协议可以分为主动式路由协议、按需路由协议和混合路由协议。
主动式路由协议又称为表驱动路由协议，网络中的每个节点都周期性地进行路由分组广播，以维护一张包含到达其他所有节点的路由信息的路由表，并根据网络拓扑的变化随时更新路由表，以实时准确地反映网络的拓扑结构。主动式路由的优势在于目的节点的路由信息存在时，数据分组传输过程就可以立即开始，延时很小；劣势在于需要大量的路由控制报文，协议开销较大。常用的表驱动路由协议如下：DSDV、FSR、OLSR、TBRPF、LANMAR等。
按需路由协议中，节点不需要维护及时准确的路由信息，当有数据分组传输需求时才查找路由信息。按需路由协议主要分为“路由查找”和“路由维护”两个过程。与表驱动路由协议相比，按需路由协议的开销小，更适合AdHoc无线网络。但是数据报文传送时延较大，不适合于实时性的应用。常用的按需路由协议如下：AODV、DSR、TORA、ABR、MSR等。
混合型路由协议是对主动式路由协议和按需路由协议的综合。这种路由协议在小范围局部区域内采用主动式路由协议，而在区域外节点的路由查找则采用按需路由协议。这样就避免了主动式路由协议中控制开销过大问题和按需路由协议中的长时延问题，常见的层次路由协议包括：ZRP、CEDAR、SRL等。
2.2单路径路由协议的不足
首先，因为有线网络具有相对较高的带宽和拓扑变化不频繁的特性；而无线网络结点移动性高，带宽资源有限，而且连接中断率高，导致网络分裂机会高。所以，传统的有线网络路由算法开销太大，收敛速度慢，不适合MANET。因此由传统的有线网络路由协议改进而来的MANET路由协议，比如由经典的Bellman-Ford路由协议改进得到的DSDV路由协议，就存在这种问题。
其次，现在最流行的按需路由协议中，需要通过洪泛技术来进行路由的查找，而当节点移动导致原来路由失效后，路由的维护也需要洪泛。洪泛需要占用一定数量的网络带宽，而网络带宽在MANET中是非常宝贵的资源，尤其是有中等数量甚至大量的路由需要维护时，频繁的全网洪泛使得按需路由协议的路由控制开销仍然是非常可观的，以至接近最短路径的开销。
再次，单路径路由协议算法简单，易于管理和配置。但是，这些MANET路由协议没有考虑公平性，它们倾向于把重的负载分布到源-目的对的最短路径的主机上；同时，它们在路由发现阶段只获取一条路径，无法很好地获取整个网络的拓扑信息，从而无法有效地利用网络的有效信息，进而导致路由开销增加；而且，数据发送一般只利用一条路径，无法并行或并发地发送数据，导致网络传输率较低，延迟增加，网络负载不平衡，甚至造成网络拥塞，无法很好地支持QoS[2]。
3、多路径路由
3.1多路径路由的基本概念
多路径路由思想并不是一种新的路由思想。多路径路由由于提供了一种简单的机制来分配通信量、平衡网络负载，以及提供容错能力，所以一直在电路交换网络和分组交换网络中受到人们的青睐。
多路径路由特点：（1）可以为不同的服务质量要求提供不同的路径。（2）多路可以为同一种类型的服务提供多条路径，经聚集可实现更高的服务质量。（3）由于主机对路径有自主的使用权，它可以通过探测各路径的状况（比如丢包率）猜测网络的拥塞程度，据此调整对各路径的使用，从而在得到优质服务的同时也提高了网络的利用率。因此，多路的正确使用还可以提高网络的利用率。
3.2多路径路由的分类
根据不相交性，多路径路由可以分为3种：节点不相交（Node-Disjoint）多路径、链路不相交（Link-Disjoint）多路径和相交多路径。节点不相交多路径，也称为完全不相关多路径，就是各条路径中除源节点和目的节点之外没有其他任何共用节点。链路不相交多路径是指各条路径间没有任何共用的链路，但有可能有共用的节点。相交多路径是指各条路径间既有共用的节点，又有共用的链路。表1是3种路径间的比较。
表1 3种多路径间的性能参数比较
相交路由同不相交路由相比，它所占用的资源要少，因为它既有共享的链路又有共享的节点，因此资源是共享的。并且同等的网络分布密度下，相交路由的搜索要容易的多，因为不相交路由的搜索其约束性要强的多。但是正是因为相交路由有共享的节点或者链路，其容错能力就差很多。在上述3种路由类型中，节点不相交路由的容错能力最强，链路不相交路由的容错能力次之，相交路由的容错能力最差。在链路不相交多路径路由中，如果共享的节点由于移动等原因发生中断的话，那么该节点所连接的所有路径便都失败了，而节点不相交路由由于链路的独立性，则不会产生连锁反应。
AdHoc网络的无线多播特性（wirelessmulticastadvantage，WMA），是指当一个节点发送报文时，在它的功率覆盖范围内的节点都能收到此报文，而在覆盖范围外的节点感知不到此通信的存在。WMA特性虽然能够以较低的能量获得新的路径，但是由于其覆盖范围内的节点都能收到此报文，带来的冲突问题比有线网络严重的多。
一般在网络分布密度相对较大的情况下，采用节点不相交多路径路由；但在在节点密度相对稀疏的网络环境中，会采用链路不相交多路径路由。一般的话，相交多路径路由是不宜采用的。
3.3多路径路由的优势
由于MANET中各个节点都具有路由功能，因而从任何一个源节点到目的节点的路径通常会有多条。同时MANET中节点具有随机移动性，整个网络的拓扑结构经常变化。如果能为各个节点对都建立一条或多条替换路径，就可以路由的可靠性和容错性。如果能够同时使用多条相互独立的路径，那么源节点一目的节点对之间的实际带宽在网络轻载时就等于各条路径的带宽和。
多路径路由可以将原本集中在一条路径上的负载分配到了几条不同的路径上，平衡网络负载，这样就能够充分利用网络资源，从而改善了通讯性能，避免了网络震荡。同时也减少了路径上中间节点的能量消耗，从而降低了由于能量消耗殆尽导致的网络分割或拓扑变化发生的概率。
4、多路径路由研究现状与协议分析
多路径路由是指为任意一对节点同时提供多条可用的路径，并允许节点主机或应用程序选择如何使用这些路径。多路径路由算法为节点间提供多条路径，并确保发往其中一条路径的数据经由该路径到达目的地。多路径路由网络是其中的路由器执行多路径路由算法的网络。文献[3，4]从理论上证明了按需多路径拥有较长的路径存活时间和更可靠路由信息，而且拥有良好的性能，并能减少部分拥塞。因此近年来多路径研究得到广泛关注。
4.1SMR[2]
分裂多路径路由（SplitMultipathRouting，SMR）协议建立和使用最大不相交路径的多条路由。多条路由是按需查找的，不必等长度，其中有一条是最短时延路径。数据的传输被分散到各条路由上进行，以高效利用有效的网络资源，避免节点拥塞。使用多条路由有助于使路由恢复进程的调用频次达到最小并使控制开销最少。适用于中速的动态网络；
在DSR协议中，中间节点只接受一次从同一个源节点发来的具有相同RREQID的RREQ包，这就极大地降低了寻找多路由的可能性。SMR协议主要对DSR的寻路过程中RREQ包的传播接受进行了改进。在SMR协议中，中间节点不是简单的将重复的RREQ（即从同一个源节点发来的具有相同RREQID的RREQ包）丢弃，而是通过检查，如果该RREQ包是从不同的前一节点发送过来，而且该RREQ中路径的跳数小于等于先前收到的RREQ包中的路径跳数，则接受这个RREQ，并进行处理，然后转发，反之，则将这个RREQ丢弃。在SMR最后路由选定部分，目的节点首先选择最早收到的RREQ中的路径，然后在接着设定得一段时间内，从收到的多个RREQ中选定一条与最初选择的路径不相关性最大的一条路径。
4.2AOMDV[5]
AdHoc按需多路径距离矢量（AdHocOn-Demand Multipath Distance Vector，AOMDV）协议计算“多条开环、节点或链路不相交路径”，提供有效的容错能力，快速、有效地恢复动态网络中的中断路由。AOMDV协议适合于高速动态Ad Hoc网络，特别是在链路频繁断开和路由失效的情况下有良好的性能。
AOMDV协议的一个显着特点就是尽可能地使用基本的AODV协议中的已有有效路由信息。因此，计算多路径所需要的额外开销非常少。AOMDV协议有下列两个主要组成部分：
（1）路由更新规则，用于建立和维护到达每个节点的多条开环路径。AOMDV协议采用“广告跳数（AdvertisedHopCount）”来建立目的节点序列号单调递增特性。节点i对于目的节点d的广告跳数表示从节点i到目的节点d的多条有效路径的“最大”跳数。最大跳数确定以后，同一个目的节点序列号的广告跳数可以保持不变。AOMDV协议只允许认可那些跳数小于最大跳数的候选路由。这个不变性对于保证路由开环是必要的。
（2）分布式协议，用于寻找多条不相交路径。为了找到节点不相交的路径，每个节点不马上拒绝重复的RREQ分组。每个来自源节点方向的不同邻居节点的RREQ分组都代表了一个节点不相交的路径。这是因为节点不能广播重复的RREQ分组，因此任何两个来自源节点方向的不同邻居节点到达某个节点的RREQ分组不可能通过相同的节点。为了得到多个链路不相交的路径，目的节点回复RREQ分组的时候不考虑它们的第一跳。为了保证RREP分组第一跳的链路不相交，目的节点仅仅回复那些通过唯一邻居的RREQ分组。第一跳之后，RREP分组沿着反向路径传输，这些路径是节点不相交和链路不相交的。每个RREP分组的轨迹可能会在某个中间节点交叉，但是每个都有不同的反向路径来到达源节点，这就保证了链路的不相交。
4.3CHAMP[6]
CHAMP（CachingandMultipathRouting）协议的特点是采用协作报文高速缓存（Cooperative Packet Caching）和最短路多径（Shortest Multipath Routing）来实现减少报文丢失率和频繁的路由中断。
路由寻找过程中，源节点采用洪泛的方式发送RREQ包。中间节点除了处理自己收到的RREQ包之外，还记录它侦听到的其它节点所处理的RREQ包，从而形成协作报文高速缓存。目的节点只处理拥有最短路（等于或小于以前收到的路径长度）的RREQ包，发送对应的路由应答RREP包给源节点。源节点也只处理拥有最短路（等于或小于以前收到的路径长度）的路由应答包中的路径，如果路径长度小于原有路径，就将原有路径更新成新路径；如果等于，则直接存储新路径。当源节点发送包时，采用包级轮询的方法来使用路由缓存的路径，这套机制叫做最短路多路径。由于最短路多路径机制所产生的多条路径都是相同跳数的，所以，使用CHAMP协议的多条路径轮询发包时，目的节点接收到的包的乱序问题会得到改善。
4.4其它多路径协议
MSR[7]是对按需路由DSR的扩展，协议中，每个节点对到目的节点的每一个路由都维护着个多径表（multiple-pathtable），这个表包含了路径编号、目的节点ID、延迟和计算出的路由传输量。目的是为了均衡每条路由的传输负载。MSR使用路径探测的方法获取多条路径，大大减少网络拥塞，但需要为探测付出额外的开支。
DPSP[8]是基于链路可靠性模型的多路径路由算法。该协议能够在线性时间里，使用一种启发式算法找到一簇高可靠性的路径集。该协议与前面的多路径协议的不同之处在于前面的多路径路由算法一般都是集中讨论如何进行路由发现，如何获取多路径来进行数据发送。而DPSP主要通过选择多条高可靠性结点不相交路径来获取多条路径。DPSP减少了路由发现次数、路由开销、网络延迟，提高了网络的传输率。
AODV-BR[9]是对AODV的扩展，多径路由是在目的节点向源节点发送响应消息的过程中建立的，它利用无线通信的特点，一个未被选中的节点侦听到并不是直接发送到自己的RREP包，它就将这个PREP包的直接目的节点作为自己发往目的节点的下一跳，利用这种方法，它就能接收到大量的对于同一路由的RREP包，它将挑选一个最佳路由记录到自己的路由表中。当RREP包最终到达源节点时，一条从源节点到目的节点主路由将建立起来，其他的一部分节点也能建立起到目的节点的备用路由。
TBP[10]协议是多路径在QoS方面的应用。该协议基于选票方式进行一跳一跳地寻找出多条较优的路径。首先源节点发送选票来探测路径，如果发送的选票只有n个选票，那么最多就只能找n条路径；其次中间节点收到选票，根据自己以往统计信息，判断是否要拆分选票并重新分发选票，发往代价最小的下游结，最后目的节点响应相应多条路径给源节点。
5、结束语
节点的随机移动性引起的网络拓扑结构的动态变化，以及MANET的分布式控制机制使得路由的计算与维护成为MANET中的一个较为困难的问题。相对于单路径路由而言，多路径路由在容错、路由可靠性、QoS路由等方面有很多优势，逐渐成为了近年来的一个研究热点。本文分析了多路径路由的基本概念及其分类，并对有关多径路由协议进行了评述。但是，多路径路由技术尚未成熟，在实际应用时还存在很多问题，有待于更加深入的研究：例如，多路径导致的报文乱序和分组重装的问题、大规模MANET网络的多路径路由协议的设计与实现问题等。（后卫编辑）