无线AdHoc网络的路由协议及分类概述

1、第18卷第4期2007年8月贵州教育学院学报(自然科学Journal of Guizhou Educati on I nstitute (Natural Science Vol .18.No .4Aug .2007无线Ad Hoc 网络的路由协议及分类概述张长安(上海财经大学信息管理与工程学院,上海200434摘要:无线移动Ad Hoc 网络(W irelessMobile Ad Hoc Net w orks 是随着无线通信技术的快速发展而出现的一种新型网络。它具有无中心结点限制、无有线介质限制、自组性、自愈性、高移动性和快速建立等优点,适合在复杂不确定的移动环境中应用。总括了Ad Hoc 的

2、基本概念、原理和现状,针对无线Ad Hoc 网络特有的节能、QoS 和安全三方面要求,对目前的Ad Hoc 相关协议进行了概述、对比和分类,有助于进一步研究。关键词:无线移动Ad Hoc 网络;路由协议;节能性;QoS;安全性中图分类号:O233文献标识码:A 文章编号:10026983(200704-0042-05Su mmary of routi n g protocols and cl a ssi f i ca ti on s ofw i reless m ob ile Ad Hoc networksZ HANG Chang 2an(School of I nf or mati on M

3、 anage ment &Engineering,Shanghai University ofFinance &Econom ics,Shanghai 200434,China Abstract:W irelessMobile Ad Hoc Net w orks are ne wly and s wiftly devel op ing net w orks benefited fr om the devel opment of wireless transiti ons technol ogy .Mobile Ad Hoc net w orks are free of li m

4、 itati ons like access points,physical media for trans porting,and bear several merits like self 2organizing,self 2heal 2ing,capability of moving,quickly organizing and s o on,all of which p r om ise mobile Ad Hoc net w orks the fitness t o work in comp lex and unsure envir on ment .This paper summa

5、ries,compares and categori 2zes relative p r ot ocols of mobile Ad Hoc net w orks according t o the three point features of mobile Ad Hoc net w orks 2power saving,QoS and security,which may be hel p of further researches .Key words:wireless mobile Ad Hoc net w orks;r outing p r ot ocol;energy saving

6、;QoS;security目前许多无线网络都基于移动的主机和固定的路由器而建立,即主机在进行通信的时候必须依赖固定的路由基站,或称为访问点(access point 。但在海洋、沙漠、乡村、偶发灾难或临时小范围会议等地区,两个或多个主机之间只有进行自带路由的移动通信,这样形成的网络称为移动Ad Hoc 网络(Mobile Ad Hoc Net w orks 或Ad Hoc 网络。Ad Hoc 网络有无中心结点限制、无有线介质限制、自组织、自愈、强移动性、强抗毁性和快速建立性等优点。利用Ad Hoc 网络技术,人们只要通过智能移动通信设备(智能手机,P DA,移动电脑等,而无须建立固定的中心结点

7、或有线介质就可以方便快速的进行通信连接。我国的Ad Hoc 网络技术正处于起步阶段,对Ad Hoc 的研究有着广阔前景和应用价值。本文通过对国内外Ad Hoc 网络基础协议发展的综述3收稿日期:2007-06-07作者简介:张长安(1985-,男,上海财经大学本科生。和对其协议进行的按特性分类总结,希望能使Ad Hoc 网络未来的研究和相关产品的开发更具针对性,促进无线Ad Hoc 网络技术在我国的推广与应用。1Ad Hoc 网络的定义和特性无线Ad hoc 网络又称多跳网络(multi -hop net w ork 、非固定网络设施网络(infrastructure less net w o

8、rk 、自组网(self organizati on net w ork 、对等网(P2P net w ork 或自愈网(self healing net w ork 。它是一种逻辑意义上的组网方式,可以看作是计算机网络与移动通信技术的交叉,即能在独立于有线网络设施的基础上由一定地理区域内的移动终端动态的建立可以互联的网络。Ad Hoc 网络使用的是计算机网络的分组交换机制,而不是电路交换机制或报文交换机制。与传统的蜂窝式网络相比,无线Ad hoc 网络没有基站,所有结点动态的分布运行,都具有路由器的功能。结点负责发现和维护到网内其他结点的路由,向邻居结点发送、转发或接受分组。通信的结点可以是

9、笔记本电脑、个人数字助理(P DA 等移动终端设备。Ad Hoc 网络既可以单独运行,又可以通过网关接入到有线骨干网络(如因特网,见图1。无线Ad Hoc 因其独立于有线线路、没有中心控制结点的局限,所以具有较好的抗毁性、自组性和机动性等特性。Ad Hoc 的这些特性使其在被广泛利用于军事之后在商业和民用领域也得到了重视。在紧急或临时场合,利用可快速搭建的无线Ad Hoc 网络优势明显 。图1Ad Hoc 网络动态的网络拓扑结构2Ad Hoc 网络的网络结构2.1平面结构(p lanar structures 又称对等式结构。在此结构中,所有网络结点的通信地位相等,无需建立具有特殊簇(clus

10、ter 头功能结点的层次结构,是一种完全分布式网络结构。该结构采用了相同的低层结构和协议,使得整个无线网络较为健壮,不会因为某个关键结点(对应分级结构中的簇头结点的故障而导致整个无线网络的坍塌。网络中所有结点都需要知道到达其他结点的路由信息,将其静态或动态的保存为路由表,以便在传递信息时按已知的路由进行快速的转发,但这就使维护这些路由信息占用了结点很多的控制信息。并且所有结点都要适时的更新路由表以同步每一个新加入或离开通信范围的结点的路由信息,这使得网络的扩充性较差。平面结构适用于较小的网络。2.2分级结构(classificati on structure 又称簇结构(clustering

11、。在此结构中,网络按簇(clusters 来划分,预先指定的或在一定算法下根据网络拓扑变化随机生成的簇头(cluster heads 形成了较高一层的网络,在较高一层的簇头结点的集合中,又可以选择更高管理权的簇头,以此类推形成有不同等级层次的金字塔形结构。每个簇头作为类似于管理的结点管辖一个或多个簇成员(cluster me mbers ,簇成员间的数据转发由簇头结点完成。簇结构使得Ad Hoc 网络的可扩性增强,但同时由于簇头的通信负荷随簇成员的增多和分层级别的增多而呈指数性上升,簇头往往会成为网络中的瓶颈。由于不同层次簇集合的通信范围不同,不同对等层的通信可以使用不同的通信频率,这样的物理

12、通信方式称为多频分级结构(multi -frequency and classificati on structure 。由于簇头结点需要与簇成员和同层的簇头进行通信,簇头往往利用多个频率接受、存储或转发信息。并且由于网络拓扑是动态的,簇头和簇成员也往往不固定,多频分级机构使得在簇结构变化的情况下要额外考虑物理通信频率的变化,这便增加了无线网络的不稳定性。与多频分级结构相对应的称为单频分级结构,其所有结第4期张长安:无线Ad Hoc 网络的路由协议及分类概述点使用同一通信频率。相对于平面结构,分级结构更适用于较大的网络。3Ad Hoc网络的网络路由协议(算法的基础分类目前提出的多种无线Ad H

13、oc网络路由协议(算法大体可分为三类1先应式(Pr o-active算法:又称为表驱动(table-driven路由算法。该算法将网络中每个结点当作一个独立主动的路由器进行全网络周期性的路由信息的广播和更新,每个结点需要维护一张完整的网络路由表,路由表项的内容包括目的结点、跳数、目的结点序号等。每个结点周期性的与邻结点交换路由信息来更新自身的路由表,路由发现依据路由表来进行。先应式算法的优点是通信时可以立即得到路由信息,缺点是当网络内结点发生变化时,必须重新交换路由信息以获得新路由的路径,这样增加了网络的负载,路由开销也随着网络的增大而越来越大。其代表协议有DS DV、OL2 SR等1。2按需

14、求(On-de mand算法:又称反映式路由算法。无线网络当需要路由来传送数据包时才被动的进行路由发现,即结点仅构建和维护当前需要用来发送数据包的路由信息。网络拓扑结构和路由表内容也是按需建立的,不需建立去往网络内各个结点的路径,因此不需要周期性的广播路由信息,节省了一定的网络资源。按需求算法具有较小的通信控制(路由维护更新开销,但在需要发送数据时,因没有通向目的结点的路由信息,要临时启动路由发现机制来寻找路由,这会带来一定的时延。代表协议有AODV(Ad hoc On De mand D is2 tance Vect or、DSR、DSRD、T ORA协议等。3混合式算法:结合了先应式算法和

15、按需求算法的优势。该算法按区域将无线网络划分为几个逻辑子网,在逻辑子网内采用先应式的主动算法,在区域间采用按需求的被动算法,通过调节区域划分的大小和子网内结点数量以综合提高结点和无线网络的路由能力。代表协议有ZRP协议等。4Ad Hoc的网络路由协议的按特性分类4.1节能(energy saving路由在Ad Hoc网络中,所有或大多数结点的供能都依靠于有限供电能力的电池,由于电池的体积重量等限制,结点电量非常有限。所以在设计路由协议时应该着重考虑节能问题。无线Ad Hoc网络结点在带电工作情况下有四种模式:睡眠(doze、空闲(idle、接收(receive以及发送(trans m it模式

16、。睡眠模式中的结点既不能接受也不能发送信息,它只消耗很少的电能(66mW2130mW。而要一个结点能接受或发送信息,它必须处在其他三种非睡眠状态(weak state。空闲模式的结点只是处在准备状态但既未接受也未发送信息,但它却要消耗大约800mW的电能。相比较接收模式下大约1000mW和发送模式下大约1300mW的功率,空闲模式是一个非常耗能的模式。所以,节能协议的焦点主要放在如何管理结点在睡眠模式和非睡眠模式之间的转换。更广泛的电能与功率控制涉及了电池的管理、传输功率的控制和结点本身的功率控制,其中大多数都是基于低三层的方法,这里不再赘述。而大多数节能路由协议则是基于MAC和物理层的协议。

17、1802.11节能机制(I EEE802.11power sav2 ing mechanis m s凭借其完善稳定的协议的定义,得到了最广泛的应用。2Span则利用控制集(do m inating set的方法,将Ad Hoc网络中的部分结点定义为控制结点,这些结点在电能充足的情况下不会进入睡眠模式,而其余结点在无通信任务时处于睡眠状态。控制结点的集合作为无线Ad Hoc网络的中心结点采用一系列的路由方法和唤醒方法对其他大多处于睡眠模式的结点和整个网络进行调节,以达到节电的目的2。3基于BECA(basic energy conservati on algo2 rithm的AFECA(adap

18、 tive fidelity energy conserva2 ti on algorithm算法则应用了自适应技术(adap tive techniques3,将每个结点都独立看待,并让每个结点都以一定的几率在睡眠模式和空闲模式之间贵州教育学院学报(自然科学第18卷转换,该几率取决于无线Ad Hoc网络的质量、结点拓扑结构和网络结点数,而信息只利用处于空闲模式下的结点转发。4.2QoS(Quality of Service路由QoS路由即是选择能满足一定可靠性,带宽,低抖动,低延迟需求的具有足够资源的网络路径。无线网络协议在QoS路由方面进行了从层间到整个网络构架上的优化。各层内部(层间协议

19、有如基于应用层的RTP(real2ti m e trans port p r ot ocol和RTSP(real2ti m e strea m ing p r ot ocol,基于传输层和网络层的类似于RE D拥塞避免策略(congesti on a2 voidance和ECN(exp licit congesti on notificati on等。在网络框架层面上,I ETF提出的基于通信量监控(traffic policing的综合式服务(integrated service和差别式服务是目前最流行的无线网络QoS优化服务,并且还可以将两者整合在一起使无线网络QoS特性获得最优的效果。而

20、在无线Ad Hoc网络中,网络拓扑、结点路由信息的时变性和结点能源有限造成的网络资源提供不足等特点使得选择满足QoS需求的路由协议以及优化策略较其它无线网络而言更为重要。目前实现Ad Hoc网络下的QoS在策略上可以分为三类:1优化基础协议。基于802.11的异步数据传输协议被重点研究以平衡同步数据传输协议的不足,通过增加数据帧的长度为代价换取结点间同步的开销,能在一定程度上缩短建立和维护传输的时间4。移动暴露站和移动隐藏站问题也被积极讨论并努力解决以提供更高的传输速率和更低的结点间传输影响。对于P-坚持的CS MA的MAC算法考虑到了环境因子(contingency,通过微调不同环境中的P的

21、值(P的值域为0-1,以期达到算法的最优解5。通过对退避过程(back2off p r oce2 dure建立马尔可夫链模型(Markov chain model的方法最近也被利用到衡量Ad Hoc网络通信质量中来6。2优化每个结点通信的综合质量。最优帧大小预测的基本思想就在于根据变化的无线信道质量来动态的改变帧的大小以达到信息吞吐量的最大化,当信道的通信质量较高时,传输较大的帧能获得较高的信息吞吐量,较小的帧却恰恰相反。而基于链路自适应(link adap tati on的方法除了考虑到帧的大小以外,均衡器设计、瑞利衰弱环境(Ray2 leigh2fading envir on ment中的

22、能量控制等许多因素也被综合衡量。分段门限制自适应算法(algo2 rithm s of frag mentati on threshold adap tati on则将一个较大的长帧划分为几个短帧,分别路由后再在接收端将帧重新组合为完整的长帧,以便缓解长帧的路由排队时间和被丢弃的可能性7。3优化全局无线网络的综合质量。目前大多数改进协议或算法都基于对每个站或结点自我路由通信性能的提高。但过于强调结点通信质量往往会造成网络整体性能的下降,无论是有线还是无线网络。最新的研究视角大都被放在了优化Ad Hoc网络的全局通信质量和信息吞吐量上8。4.3安全(security路由要建立一个结构性能稳定且能

23、高效低成本组建的Ad Hoc网络,安全性成为其必不可少的一环。安全问题可以分为四类交织的领域:保密,可甄别,不可抵赖,和完整性控制。保密是指对于特定权限的信息不能泄露给未达此权限的个体或组织。可甄别是指对于特定意味的信息,在网络传递后仍能对信息使用者保持原意。不可抵赖是指抵赖方不可抵赖其发送过或已接受信息。完整性控制是指对信息的完整性在信息起始端和目标端保持一致。许多主动或被动的攻击会源于网络外部的恶意主机或网络内部的授权的主机。网络外部的攻击者通过发送错误的路由信息、重放过期的路由信息、破坏路由信息等手段,使网络产生分割或无效的错误路由(路由破坏性攻击,无谓重传分组导致网络拥塞(资源消耗性攻

24、击,攻击者还可以通过截获信号来获取有用信息(资源窃取性攻击。本网内部的攻击者同样可以通过上述三类攻击方法,或作为其他网络的外部攻击者或对本网进行恶意攻击。针对上述攻击方式,许多基于密码学并侧重于路由安全的协议被提出,例如SRP,SE AD,和S AODV都基于公匙管理系统(PK MS对路由协议进行了安全方面的优化9-11。TES LA协议则论证和运用了不对称密匙管理框架(AK MF12。移动确认授权密匙管理(MOCA授予MOCA结点以确第4期张长安:无线Ad Hoc网络的路由协议及分类概述保安全性的服务,这些MOCA结点比其他未授权的结点更具物理上的安全性和高效能。较之于MOCA方法,本地化密

25、匙管理法(URS A则将所有结点作为同等授权的服务结点,这样做的好处是使得每个结点的安全性和整个系统的安全性都一致,但缺点是当每个结点的物理防护不完善的时候,整个网络的安全性都会受到威胁13。安全效率密匙管理系统(SEK M将服务结点进行分组,并区域性管理可以进行信息共享的一般结点,对未授权的不能进行信息共享的结点进行路由屏蔽,使授权结点之间能进行安全有效的数据通信14。除此之外,还有基于I D的加密方法,混沌加密法等方法也在提高无线Ad Hoc网络的安全性能方面得到应用。5结束语虽然有众多协议使无线Ad Hoc网络的性能得到了很大的提高,但是目前Ad Hoc网络还处于未成熟阶段,网络的各个关

26、键特性都还不完善,还存在许多未解决的问题,这些不足都将成为未来相关方面工作的挑战,有待于进一步的研究。参考文献:1T Clausen,P Jacquet,L V iennot.Comparative study ofr outing p r ot ocols f or mobile ad-hoc net w orksC.Pr o2 ceedings of M ed2Hoc2Net,2002(9:10-35.2Chen B,Ja m ies on K,Balakrishnan H.Span:An Energy2Efficient Coordinati on A lgorith m for Top

27、ol ogyMaintenance in Ad Hoc W ireless Net w orksJ.AC M W ireless Net2 works,2002,8(5:481-494.3Y Xu,J Heidemann,D Estrin.Geography I nf or med En2ergy Conservati on f or Ad hoc RoutingC.AC M/I EEEI nternati onal Conference on Mobile Computing and Net2working,2001.70-84.4F Eshghi,A Elhakee m.Perf or m

28、ance analysis of ad hocwireless LAN s for real2ti m e trafficJ.Selected A reas inCommunicati ons,2003,21(2:204-215.5F.Cali,M.Conti,E.Gregori.Dyna m ic tuning of theI EEE802.11p r ot ocol t o achieve a theoretical thr oughputli m itJ.I EEE Transacti ons on Net w orking,2000,8(6:785-799.6S ong Ci,Ha m

29、 id Sharif.Evaluating saturati on thr oughputperfor mance of the I EEE802.11MAC under fading chan2 nelsC.Pr oceedings of the I EEE/AC M B r oad Nets, 2005.726-731.7Hua Zhu,M ing L i,Chla m tac I,Prabhakaran B.A surveyof quality of service in I EEE802.11net w orksJ.I EEE W ireless Communicati ons,2004,11(4:6-14.8Song Ci,Mohsen Guizani.Self2Regulating Net w ork U tili2zati on in Mobile Ad Hoc W ireless Net w orksJ.I EEE Transacti ons on Vehicular Technol ogy,2006,55(4: 1302-1310.9Papadi m itrat os P,Haas Z.Secure r