无线自组网中的路由协议

单思宇

摘要:无线自组网组网方式灵活,整体鲁棒性高,系统成本低,近年来引起广泛关注。在无线自组网中,路由协议占有重要地位,该文分析了无线自组网中的路由协议,重点介绍了多径路由技术。

关键词:Ad Hoc;无线自组网;多径路由

中图分类号:TP393文献标识码:A文章编号:1009-3044(2009)20-0000-00

无线自组网(Ad Hoc)网络中的节点能够动态的加入和退出网络,其组网灵活性强、网络整体鲁棒性高和系统成本低等优点使得Ad Hoc网络具有不可替代的作用和广阔的应用和发展前景[1]。

Ad Hoc网络自身的特殊性决定了路由协议的特殊性和重要性,动态变化的网络拓扑结构要求路由必须建立及时迅速,有限的无线网络资源要求路由协议必须具有较小的开销和能耗。传统的路由技术已无法适应Ad Hoc网络动态变化的拓扑结构,必须设计新的适合Ad Hoc网络特点的路由协议。

目前,国内外许多相关的大学和科研机构都开始了Ad Hoc网络特别是Ad Hoc路由技术的研究。上个世纪九十年代中后期,各研究机构向MANET工作组提交了许多路由选择协议[2],如卡耐基马龙大学提交的动态源路由DSR[3],C-K。Toh提交的ABR[4]等。这些路由协议各自基于不同的出发点和度量,通过按需机制解决了动态变化的拓扑结构带来的问题。从路由路径上分,目前的Ad Hoc网络按通信模型分可分为单径路由和多径路由两大类,下面分别予以介绍。

1 单径路由

传统的分类方法将Ad Hoc网络中的路由分成“表驱动”和“按需驱动”两大类,表驱动路由中,网络中的任一节点都维护一个到其它所有节点的路由表。当网络拓扑发生变化时,节点间及时更新该信息以维护路由表的正确性。按需驱动路由中,仅当源节点有路由需求时才启动路由发现,针对特定的目的节点在网络中找到合适的路径。在该路径的使用中,网络中的相关节点会通过消息的交互来维护有效的路由并删除失效的路由多径路由是指在同一对源/目通信节点之间建立多条不相交的路径同时进行分组投递,源节点和目的节点对之间的多条路径能够补偿移动Ad Hoc网络的动态特性和不可预测性,从而改善通信双方的通信服务质量[5]。

这种传统分类方法过于模糊,还可以根据Ad Hoc的网络结构将路由协议分为平面路由协议和分级路由协议。平面路由协议在网络中没有等级的划分,所有的网络节点都具有同样的功能与优先级,它们以相同的动作收发路由控制信息。而分级路由协议在处理路由信息时需要区分级别不同的节点以减少控制报文的数量。分级路由协议又分为两种,一种称为邻居选择,该协议中的节点根据其邻居节点动态选择路由;另一类称为分区选择,即根据网络拓扑划分区间进行管理。

根据Ad Hoc网络的状态信息可将路由协议分为基于拓扑和基于目的节点的路由协议。基于拓扑的路由协议需要在节点保存大量拓扑信息,这与链路状态协议的原则是一致的。基于目的节点的路由协议在节点不需要保存大量拓扑信息,只需要保存所需的最近节点的拓扑信息,这类协议中最著名的是距离矢量路由协议,该协议需要维护到达目的节点的距离矢量。

此外,根据路由建立方式可以分为先应式路由协议和被动式路由协议。先应式路由协议以表驱动路由协议为代表,每个网络节点为目的节点保存路由信息,所有的节点周期性地交换路由信息。被动式路由协议的过程可分为路径发现和路由保持,路径发现只有在源节点有需求时才会启动,路由保持则是在拓扑信息发生变化时寻找丢失的路由信息并重新启动路径发现。

2 多径路由

多路径传输(Multiple Path Transport:MPT)是指采用多条不相交的路径来投递应用分组,以增加连接的带宽和可靠性的机制。移动Ad hoc网络中,由于缺乏基础设施、网络拓扑动态变化等,其对QoS的支持较弱。但是其网络结构和用户的移动增加了网络的灵活性、用户的多样性和网络的容量,这些都对在其中实施MPT提供了有利的因素。

多路径路由模型为任意一对节点同时提供多条可用路径,并允许节点主机(或应用程序)选择如何使用这些路径。多路径路由算法为节点间提供多条路径,并确保发往其中一条路径的数据经由该路径到达目的地。为在节点间计算路径,必须根据路径的用途规定路径的特性。如为了得到最大的端到端吞吐量,必须规定路径的特性是:在任意节点对之间的多条路径的聚合吞吐量最大。而为了得到最小的端到端时延,就必须规定路径的特性是:任何时刻,任意节点对之间都存在至少一条具有最小时延的路径。路径规格规定了特定路径集合的特征,路径计算算法实际计算出符合路径规格所规定的特征的路径集。

路径类型规定了节点对间的多条路径之间的关系。有两种路径类型:多服务的多路径和多选择的多路径。多服务的多路径是具有不同特征的多条路径。例如,网络可以同时提供高带宽路径和低时延路径,这使得应用程序可以选择最符合其通讯要求的路径。多选择的多路径为同一服务提供多条路径。例如,网络可能为高带宽服务提供四条路径,即每个节点都有到任意目的节点的四条高带宽路径。但一般说来多服务的多路径选择算法一般较为复杂,不易实现,而多选择的多路径选择算法相对容易,故目前一般多采用多选择的多路径路由。

3 多径路由的使用模式

对多路径的使用模式,主要有两种:在同一时刻对于每个源节点-目的节点对只能在某条路径上传输数据,当这条路径中断时,可以用多条路径中的其它路径(备份路径)来传输,该模式称之为“备份多路径”;另一类是对每个源节点-目的节点对能够同时使用两条或两条以上的路径来传输数据,该模式称之为“并行多路径”。

4 多径路由的优势

1) 容错 多路径传输可以避免传统的单路径路由中路由错误后的重新路由过程。

如图1所示,源节点S与目的节点D间有三条路径,如果S同时沿着三条路径向D发送同样的数据包,那么只要三条路径中有一条路径正常工作,数据包就能到达D。图中节点D由于移动,原先的两条路径S-A-D和S-B-D都相继失效,只剩下S-C-D,但此时S和D仍能够正常地通信,需要注意的是这期间并没有重新路由的过程。但如果采用传统的单路径路由,原先有可能选中最短路径-S-B-D,但当D移动,B-D之间的链路出现错误后,就需要重新路由找到路径S-C-D,而后再进行传输。这期间就有重新路由的过程,即S和D之间就有一段时间不能正常通信。当然像这种在所有路径上发送同样数据包的冗余数据的做法,并不是最好或唯一的利用多路径的方法,这里只是利用它来说明多路径路由是如何在链路出现错误的时候提供错误容忍服务的。

2) 高带宽 无线网络中的带宽比有线网络要低很多,为一个连接建立的单独的一条路径可能不能提供满足需求的带宽。然而如果使用多条路径同时传送数据(当然不是像上述的不同路径上传送相同的数据),就能够取得满足要求的带宽。同时,因为有更多的带宽可以获得,就可以取得更小的端到端的延时。

5 多径路由协议

好的路由协议可以进一步增强多路径的性能,多路径集合的选择要根据诸如路径特征、链路层上的相互影响等标准进行。从错误容忍的角度来看,更多“健壮”的路径应当被选择以减小路径出错的几率。目前常见的Ad Hoc网络中的多径路由协议有SMR协议[6]和AOMDV协议[7]。

6 结束语

根据本文的分析介绍,可以看出,多径路由技术由于具有容错性好,带宽高等优势,非常适合在Ad Hoc网络中应用,将使未来移动Ad Hoc网络路由的主要方式,但目前,对移动Ad Hoc网络多径路由技术的研究仍然处于初级阶段,还有许多诸如路由发现、路由选择策略等问题需要进一步深入研究。

参考文献:

[1] Corson MS,Macker J R,Cirincione G H.Internet-Based Mobile Ad Hoc Networking[J].IEEE Internet Computing,1999,3(4):63-70.

[2] Royer E M,Toh C K.A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks[J].IEEE Personal Communications,1999,6(2):46-55.

[3] Johnson D B,Maltz D A,Broch J.The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks[Z].Internet Draft,MANET Working Group,draft-ietf-manet-dsr-01.txt,1998.

[4] Toh C K.A Novel Distributed Routing Protocol To Support Ad-Hoc Mobile Computing[C].Proc. 1996 IEEE 15th Annual Intl.Phoenix Conf. Comp. and Commun.,1996:480-486.

[5] Kuosmanen R.Classification of Ad Hoc Routing Protocols[EB/OL].http://eia.udg.es/~ramon/xdsi_ant/classification-of-ad-hoc.pdf.

[6] Lee S J,Gerla M.Split multi path routing with maximally disjoint paths in Ad Hoc networks[J].ICC01.June 2001,10:3201-3205.

[7] Nasipuri A,Das S R.On-Demand Multipath Routing for Mobile Ad Hoc Networks[C].Proceedings of the 8th International Conference on Computer Communications and Networks,1999.