混合无线Mesh网络中改进的分层AODV路由协议

1、2010,46(191引言无线Mesh网络(WMN1作为一种新技术,不久的将来将成为无线网络互联的解决方案。WMN具有快速部署和自组织等特点,这使得它非常适应于临时的按需网络部署场景。WMN对于热点地区的基础设施网,以及能提供低成本回程的传感器网和偏远农村蜂窝网基站,都有一种具有很大吸引力的技术。WMN最具商业价值的网络形式通常是混合Mesh网络2。在混合Mesh网络中(图1,PDA和笔记本电脑等终端用户组成了Mesh客户端网络,而Mesh路由器节点是网络基础设施的一部分。相比于移动Ad hoc网络,WMN中的节点有相对固定的位置并且通过一个或多个网关和Internet通信。尽管传统的Ad-h

2、oc路由选择算法可以用于WMN,但是它们的性能都不太理想。因为这些算法都基于在WMN中不成立的一些假设(如高速移动,没有基础设施等,而这些假设对于无线Mesh 网络环境中路由性能有很大的影响。现在已经提出了许多关于WMN的路由协议。这些协议可以根据不同的标准分成不同的种类。如按其对网络拓扑变化的反应来分类,可以分为先应式(或路由表驱动路由协议和反应式(或按需路由协议(但也存在几个混合协议;若按路由节点的功能和网络组织结构分类,可以分为平面路由协议和分层路由协议。先应式路由协议定期的发送网络拓扑信息并周期性地查找路由,而反应式路由协议如动态源路由协议(DSR3和Ad-hoc按需矢量路由协议(AO

3、DV4是根据需要查找路由的。一般来说,反应式路由协议在分组投递率,路由开销和能效方面比先应式路由性能更好。然而在平面路由协议中,一混合无线Mesh网络中改进的分层AODV路由协议曾文丽,裴廷睿,张朝霞,赵智ZENG Wen-li,PEI Ting-rui,ZHANG Zhao-xia,ZHAO Zhi湘潭大学信息工程学院,湖南湘潭411105College of Information Engineering,Xiangtan University,Xiangtan,Hunan411105,ChinaZENG Wen-li,PEI Ting-rui,ZHANG Zhao-xia,et al.I

4、mproved hierarchical AODV routing protocol for hybrid wireless Mesh network.Computer Engineering and Applications,2010,46(19:125-128.Abstract:Routing is the main research issue in the development of Wireless Mesh Network(WMNs.Many of the routing approaches have been borrowed from MANETs to achieve r

5、outing solutions in WMNS but are not ideal or optimal and do not utilize the characteristics of WMNs to their benefits.In this paper,an improved Hierarchical AODV routing protocol (IH-AODVis proposed,which exhibits better scalability and performance in the network and incurs less routing overhead fo

6、r finding alternate routes when a route is lost.Furthermore,a novel technique for IH-AODV term fresh route detection is presented.This paper provides comparisons of both AODV and IH-AODV in the simulation using NS-2.Simulation results show that IH-AODV scales well for large network and other metrics

7、 are also better than or comparable to AODV in hybrid WMNs.Key words:wireless Mesh networks;routing protocols;hierarchical;Ad hoc On-demand Distance Vector(AODVrouting摘要:路由是无线Mesh网络发展中的一个研究热点。无线Mesh网络从移动Ad hoc网络中借鉴了许多路由选择算法作为路由的解决方案,但是这些方法都不太理想或者没有达到性能的最优化,且没有利用到无线Mesh网络自身的特点。提出了一个改进的分层AODV路由协议(IH-A

8、DOV,它表现出了更好的可扩展性和网络性能,当一条路由丢失时,它使寻找替代路由的路由开销得到降低。在IH-AODV中,还提出了一种新技术,即最新链路发现机制。利用NS-2软件对AODV和IH-AODV进行了仿真比较。基于混合无线Mesh网络的仿真结果表明,IH-AODV在大的网络中也表现出了很好的扩展性,相对于AODV,在其他性能方面也表现良好甚至更优。关键词:无线Mesh网络;路由协议;分层;Ad-hoc按需矢量路由作者简介:曾文丽(1981-,女,硕士研究生,主要研究方向为无线Mesh网络关键技术的研究等;裴廷睿(1970-,男,副教授,博士,主要研究领域涉及移动通信、自组织移动网络及无线

9、资源管理等;张朝霞(1984-,女,硕士研究生,主要研究方向为无线Mesh网络关键技术的研究等;赵智(1986-,男,硕士研究生,主要研究方向为无线Mesh网络关键技术的研究等。收稿日期:2008-12-15修回日期:2009-03-05Computer Engineering and Applications计算机工程与应用125,j:0Computer Engineering and Applications 计算机工程与应用2010,46(19条路由总是维持从源节点到目的节点的路径中的所有节点。这种方式对于路由较短的小型网络有很好的表现。随着网络规模的扩大,路径将会变长并且经常容易断裂。

10、由于新的路由发现和丢弃过于频繁,路由开销将会增大。这些是平面路由协议中固然存在的问题。分层路由协议能有效地解决平面路由协议中存在的这些问题。在分层路由协议中,网络节点被分组,并且每个节点子集都被分配了特定的功能。簇头网关交换路由协议(CGSR 5是一种典型的分层路由协议。CGSR 将网络分成半径为预先定义好跳数的圆形簇集。当网络被分成簇集后,本地路由维护行为只会对少数邻居簇集产生影响,而其他簇集将不会受到影响。Way Point Routing (WPR 6是一种改进的分层路由协议,它只对当前路由进行维护,它将一条路由的许多中间节点选作Way Point 节点,并通过Way Point 节点将

11、这条路由分成许多段,从而达到简化路由维护的目的。尽管分层路由协议实现了可扩展性,但其算法通常十分复杂,使得它很难应用。旨在提供一种基于AODV 的轻量级分层路由协议。因为WMN 本身是一种介于移动Ad-hoc 网络和静态网络之间的混合网络,所以使混合WMN 中不同特性的节点具有不同的功能,然后根据不同的功能将它们划分为半径为单跳的簇(正如CGSR 。在簇内,不再有簇头,而只有定义的特殊节点WayPoint (正如WPR 。在簇间,仍然使用AODV 路由协议。将CGSR 和WPR 的特性结合到AODV 中,提出了一种改进的分层AODV 路由协议,即IH-AODV 。2无线Mesh 网络中的IH-

12、AODV 路由协议2.1IH-AODV 路由协议的客观需求WMN 发展的主要目的是为了提供可靠的数据通信和负载平衡。许多假设(如高速移动和无基础设施等在无线Mesh 网络中不再成立;而且大部分已有的路由选择方案没有利用到WMN 的优良特性。这就使得为WMN 制定专门的路由协议非常必要。在AODV 中,由于其路由发现过程是基于泛洪的,所以造成了较重的业务负载。再加上路由发现过程需要较长的时延,使得单纯的AODV 路由不太适应于实时业务通信中。基于WMN 中许多节点的移动性低,如果能在路由发现阶段,通过将节点分簇来减少活动节点的数目,那么发送分组前的等待时延可能会减小,并且由于簇机制使得新节点加入

13、到路由中变得更加容易,使得可扩展性问题也能得到解决。IH-AODV 路由协议的设计目标是在保留AODV 优点的同时提高其网络扩展潜能,以支持更大规模的网络。设计主要包括如下特点:(1最新链路检测机制这是IH-AODV 应用的一种新技术,称这种机制为最新链路检测。它旨在对加入簇的节点进行快速路由发现,能够提高路由发现的速度和效率。对于路由维护,这种技术也非常有用。下面将对这种机制进行详细的介绍。(2与AODV 兼容AODV 是一种被广泛认可的路由协议。IH-AODV 的一个重要设计原则是要与AODV 兼容,即在同一个网络中,应用AODV 协议的节点能与应用IH-AODV 协议的节点协同工作。为此

14、,保留了所有AODV 路由控制报文,并且根据需要增加了一些新的控制报文。事实上,为了最小化发现时延,把这些节点设定为静态节点。(3本地路由修复在文献7中提出了一种优化AODV 的本地路由修复机制,但是它主要适用于发生在目的节点附近的路由失效情况。随着网络规模的增加,源节点和目的节点之间的路径将变得更长,这种机制不能再发挥很好的作用。IH-AODV 让断裂链路的上游节点用本地修复来取代发送RERR 。如果本地修复成功,路由请求分组将会从目的节点或者一个与目的节点之间存在一条有效路由的节点返回。如果没有返回路由应答分组,即本地修复没有成功,那么就会给源节点发送一个RERR 路由错误消息。2.2IH

15、-AODV 路由协议路由发现路由机制是在混合无线Mesh 网络环境下提出的,并做了如下假设:首先,在网络中有很多静态节点,定义这些节点为Way Point (WP 节点,其他节点称为Cluster Member (CM 簇Wi-Fi ,Wi-MAX ,Sensor Networks ,Cellular Networks ,etc.Mesh Router with Gateway/Bridge Mesh Router with GatewayMesh RouterMesh RouterMesh RouterMesh RouterMesh Routerwith IP GatewayWireless

16、 MeshBackboneInternetMesh Router with Gateway/BridgeConventional ClientsWireless Mesh Clients图1混合无线Mesh 网络1262010,46(19成员节点。其次,在首次发起路由发现过程时,假设已经有一个初始化分簇。WP节点是簇中的功能节点,它们有与传统AODV中节点相同的特点,并且还维护着一个簇成员列表。在每个簇中,都有Start-WP和End-WP两个WP节点。两个相邻簇共享一个WP节点,这个节点作为上游簇的End-WP,下游簇的Start-WP。如果这两个节点在单跳范围内,它们就可以直接通信。在簇成

17、员列表中,包含了簇成员信息和表示各簇成员所在链路的新鲜度序号,即当簇成员所在链路被使用一次,初始值为0的新鲜度序号就加1。新鲜度的值是用来确定簇中的最新路径的,这类似AODV中使用的序列号机制,用于确定到达目的节点的路由请求报文是不是最新路由。称上述的这种机制为最新链路检测。当一个普通节点需要一条路由进行数据转发时,它就发送“Hello”消息给它所有的单跳邻居节点,邻近的WP节点接收到消息后,就检查这个节点是否已经在簇成员列表中,如果不在,就反馈一个应答消息来邀请这个节点加入簇中,当这个节点分别接收到同一个簇的Start-WP节点和End-WP节点的应答消息时,它就发送加入请求并且加入到簇中,

18、成为簇成员节点CM,并向该簇WP节点发出数据转发请求,然后由WP节点像AODV一样开始路由发现过程8。图2举例说明了源节点S找到到达目的节点d的路由发现过程。选择节点S,A,B和C作为WP节点,一个簇可以通过它的Start-WP和End-WP节点来区别。节点d到l是CM节点,包括节点d。在图2中,有三个簇,分别为:S-e/f-A,A-g/h/ i-B和B-j/k/l/d-C。为了区分WP节点和CM节点,用大写字母来标识WP节点,用小写字母来标识CM节点。按照上述路由发现机制,可以找到一条路由如:S-A-h-B-d。由于CM节点的动态特性,路由中的链路可能会失效,路由维护就是处理路由断裂的机制。

19、IH-AODV扩展了许多AODV中路由维护的特性。例如,用RERR消息通知受到断裂链路影响的节点等。除此之外,IH-AODV还增加了一些有关簇的维护机制,包括最新链路检测和本地路由修复。最新链路检测不仅用于路由发现,还用于路由维护,当一条链路失效时,其所在簇的单跳WP节点首先检查它的簇成员列表,然后找到除这条断裂链路外的最新路径,即新鲜度序号仅比断裂链路小的路径。如果因为簇成员列表更新,而导致最新链路检测不能进行,本地修复将作为第二级路由修复机制。簇成员列表更新是指旧簇已经被改变,本地路由修复将会在一个簇范围内启动7。在路由修复初始化到得到修复结果这段时间,上游节点将会对从需要修复的路由上发送

20、过来的数据包进行缓存。如果修复成功,上游节点将把缓存的数据包重新发送出去,否则,它将启用AODV中的典型修复,并继续缓存未能发送的数据包。本地路由修复试图在失效簇的Start-WP和End-WP节点之间建立一条新的路径。如果修复成功,被修复的路由上的WP节点将不会改变,源节点也不会得到通知,因为数据包能沿着同样的WP节点继续发送。图3给出了一个示例:簇A-g/h/i-B的初始路径是A-h-B,h 和B之间链路断裂了。当最新链路检测成功时,簇A-g/h/i-B 的一条新路径A-g-B就建立了起来。这样就建立了一条S-A-g-B-d的新路由。3性能评估3.1仿真使用在无线网络领域流行的网络仿真软件

21、NS29进行仿真。在相同条件下,通过将IH-AODV与AODV协议进行对比来评估IH-AODV的性能。在仿真中,设定MAC层协议为IEEE802.11标准分布式协调功能DCF。业务源为恒比特率CBR。源-目的节点对在网络中随机分布。初始化时,节点在仿真区域均匀的分布,一半节点为静态的,另一半节点为随机移动状态。移动节点的速率在0m/s至20m/s之间。仿真停留时间设置为30s。数据包大小为512字节。将在两个场景下进行仿真。首先,设置CBR业务流的值为常数20,网络节点从100个逐渐增加到1000个。网络大小和面积范围的选择见表1,这使得节点密度接近常数,可以恰当地反应路由协议的可扩展性。其次

22、,研究了在400个节点的情况下,CBR业务流在20和60之间的协议性能。每个仿真运行900s的时间。每个抽样数据的值取5次仿真的平均值。对3个性能指标进行评估,即分组投递率,平均控制开销和端到端时延。(1分组投递率:目的节点接收到的数据包个数与源发送的数据包个数之比。(2平均控制开销:路由发现,簇维护和路由修复等的控制开销。(3端到端时延:由路由发现,传输等引起的所有可能时延的平均时延。3.2结果和分析在第一个场景中,将研究协议的可扩展性。仿真结果如图4所示。由图4(a可知,即使在有1000个节点的网络中,IH-AODV和AODV的分组投递率都很高,但是IH-AODV比AODV递交率持续的高出

23、1%2%。这是因为Sef Aihgjk cldB图2路由发现过程SefAihgjk cldB图3路由修复过程大小(节点个数1002004006008001000面积/m21400×14002000×20002800×28003500×35004000×40004500×4500表1网络大小及网络面积对应表曾文丽,裴廷睿,张朝霞,等:混合无线Mesh网络中改进的分层AODV路由协议127÷一;一、;一rl-.。 睁:。j Computer Engineering and Applications 计算机工程与应用2010,46

24、(19IH-AODV 分层次的维护路由,增加了一个簇成员列表,并且能够在本地对断裂的路由进行修复,所以当前路由的存活时间更长,并且递交的数据包个数更多。图4(b 是两个路由协议的路由开销比较。当节点数超过200时,AODV 的开销迅速增加,而IH-AODV 由于应用了路由分层,所以开销较小。IH-AODV 的低控制开销对WMN 的扩展起着至关重要的作用。图4(c 表明,当节点数少于400时,IH-AODV 的端到端时延比AODV 的时延要稍大一些。这是因为形成簇需要时间开销。但当网络规模扩大以后,情况就发生了变化。在大型网络中,由于最新链路检测和路由修复机制能够快速的恢复断 裂路由,使得数据包

25、不必等待另一轮路由发现后再发送,所以IH-AODV 的端到端时延更小。以上结果表明,IH-AODV 结合了AODV 和分层路由的一些优良特性并展示了良好的性能。在第二个场景中,对路由协议进行了3个性能指标的对比,如图5所示。图5(a 给出了分组投递率的比较。由于网络变得非常拥挤,AODV 的分组投递率随着数据流数目的增加而变小。然而IH-AODV 却仍然表现良好。从图5(b 可以看出,改进后IH-AODV 协议的开销 比AODV 协议有所降低。原因是:IH-AODV 中维护一个簇成员列表,使得路由发现开销减少,并且该协议采用分簇维护机制,减少了每个数据流的控制包,从而降低了开销。从图5(c 可

26、知,随着数据流的增加,IH-AODV ,IH-AODV的端到端时延要比AODV 小,这是因为IH-AODV 通过簇成员列表能使节点在发送数据包前更容易找到一条路由。但是建立簇和簇成员列表会增加更多的时延。以上仿真结果表明,IH-AODV 在网络变得拥塞时,表现更好。4结论基于Ad hoc 中典型的AODV 协议,提出了一种新的路由协议模型IH-AODV 。该协议能分层地维护节点,是对平面和分层路由查找方法的特性的结合。仿真结果表明,由于低路由时延和开销,IH-AODV 提供 了更好的分组投递率,并且在保留了AODV 的优点的同时,实现了更好的可扩展性。其次,IH-AODV 还有效地利用了WMN

27、 的特点。由于在IH-AODV 中,没有考虑通信安全和WP 和CM 节点的能量平衡等问题,所以将进一步研究,使IH-AODV 协议更加可靠并具有可行性。参考文献:1Bruno R ,Conti M.Gregori E.Mesh networks :Commodity multi-hop ad hoc networksJ.IEEE Communications Magazine ,2005,43(3:123-131.2Akyildiz I F ,Wang Xu-dong ,Wang Wei-lin.Wireless Mesh net-works :A surveyJ.Computer Netwo

28、rks Magazine ,2005,47(4:445-487.3Johnson D B ,Maltz D A.Dynamic source routing in Ad hocwireless networksJ.Mobile Computing ,1996,353.4Perkins C E ,Royer E M.Ad-hoc on-demand distance vectorroutingC/Proc Workshop Mobile Computing Systems and Ap-plications (WMCSA 99,1999.5Chiang C C ,Wu H K ,Liu W ,e

29、t al.Routing in clustered multi-hop mobile wireless networks with fading channelC/Proc Sin-gapore Int l Conf Networks (SICON 97,1997:197-211.6Bai Ren-dong ,Sighal M.DOA :DSR over AODV routing formobile Ad hoc networksJ.IEEE Transactions on Mobile Com-puting ,2006,5(10.7Perkins C E ,Belding-Royer E M

30、 ,Chakeres I D.Ad hoc on de-mand distance vector (AODV routingS.IETF ,2003.8Garcia-Luna-Aceves J J ,Mosko M.Multipath routing in wire-lessMeshnetworksC/FirstIEEE Workshopon WirelessMesh Networks (WiMesh 2005,Santa Clara ,CA ,September 26,2005.9Fall K ,Vardhan K.The network simulator (ns-2EB/OL.http:

31、/6000050000400003000020000100000A v e r a g e c o n t r o l p a c k e t sNumber of flowsAODVIH-AODV10080604020Number of flows P a c k e t d e l i v e r y r a t i o /(%AODVIH-AODV图5(a 分组投递率Number of flows5.0E n d -t o -e n d d e l a y /sAODV IH-AODV图5(c 端到端时延20040060080010001600014000Number of nodesA

32、 v e r a g e c o n t r o l p a c k e t sAODV IH-AODV图4(b 平均控制开销2004006008001000Number of nodesE n d -t o -e n d d e l a y /sAODV IH-AODV图4(c 端到端时延2004006008001000Number of nodesP a c k e t d e l i v e r y r a t i o /(%AODVIH-AODV图4(a 分组投递率(下转131页128一:i /H 5/ll/。:;i ;j ;,;i 一数据规模/万条排序时间/m sAB C D E图2

33、排序时间与数据规模关系图网络语料所抽取的1600万条中文字符串。为了更好地分析算法性能,分别进行了横向和纵向对比试验,前者是改进算法同快速排序算法所进行的对比试验,后者是指本文算法针对不同规模语料的多次对比试验,结果见表1和表2。3.2试验数据分析从表1中可见,对不同规模的试验数据,基数排序算法都比快速排序算法具有更快速度;且随着数据规模的增长,二者的时间消耗差距在增大。试验结果实现了对前述理论分析结果的良好验证:基数排序的时间复杂度低于快速排序,所以取得了更快的排序速度。表2中数据是为了减少偶然性影响,使用改进的基数排序算法,对同一规模数据进行了5次试验,且不同规模的语料进行了纵向比较。为说

34、明排序速度与规模之间的关系,绘制了二者的关系图,见图2。从图中可见,排序时间与数据规模之间是一种线性关系,这也很好地验证了改进算法时间复杂度为O (dn 的论断。4结束语通过对基数排序算法的研究,使用快速转换机制将汉字字符串转化为与之等长的整型数组,用以实现中文字符串的基数排序。理论分析和试验结果都表明,改进的基数排序方法可以实现对中文字符串的线性时间排序。该方法不仅适于汉语,同样适用于其他语种的字串快速排序。但在实现基数排序算法时,为了提高速度,对不同长度的字串使用等长的整型数组,造成内存浪费。下一步考虑改进算法实现机制,在不降低性能的同时,减少内存消耗,提高总体性能。致谢研究中使用了搜狗实

35、验室的大规模中文网络文本语料,并得到了倪剑莉老师的大力协助,在此表示感谢。参考文献:1卢开澄.计算机算法导引:设计与分析M.2版.北京:清华大学出版社,1996.2Owen A.Bubble sort :An archaeological algorithmic analysisC/Proc of the 34th SIGCSE Technical Symp on Computer Sci-ence Education.New York :ACM Press ,2003:1-5.3Hore C.QuicksortJ.The Computer Journal 1962,5(1:10-16.4杨磊

36、,黄辉,宋涛.桶外排序算法的抽样分点分发策略J.软件学报,2005,16(5:643-651.5杨磊,宋涛.基于数组的桶排序算法J.计算机研究与发展,2007,44(2:341-347.6Cormen T H ,Leiserson C E ,Rivest R L ,et al.Introduction toAlgorithmsM.2nd ed.Cambridge MA :MIT Press ,2001.7何文明,崔俊芝.针对字符串等复杂数据的一种新的高效分档混合排序算法J.小型微型计算机系统,2004,25(4:698-701.8严蔚敏,吴伟民.数据结构:C 语言版M.北京:清华大学出版社,1997.11001600A119381598524922B1140