混合無(wú)線Mesh網(wǎng)絡(luò)中改進(jìn)的分層AODV路由協(xié)議

1、2010,46(191引言無(wú)線Mesh網(wǎng)絡(luò)(WMN1作為一種新技術(shù),不久的將來(lái)將成為無(wú)線網(wǎng)絡(luò)互聯(lián)的解決方案。WMN具有快速部署和自組織等特點(diǎn),這使得它非常適應(yīng)于臨時(shí)的按需網(wǎng)絡(luò)部署場(chǎng)景。WMN對(duì)于熱點(diǎn)地區(qū)的基礎(chǔ)設(shè)施網(wǎng),以及能提供低成本回程的傳感器網(wǎng)和偏遠(yuǎn)農(nóng)村蜂窩網(wǎng)基站,都有一種具有很大吸引力的技術(shù)。WMN最具商業(yè)價(jià)值的網(wǎng)絡(luò)形式通常是混合Mesh網(wǎng)絡(luò)2。在混合Mesh網(wǎng)絡(luò)中(圖1,PDA和筆記本電腦等終端用戶組成了Mesh客戶端網(wǎng)絡(luò),而Mesh路由器節(jié)點(diǎn)是網(wǎng)絡(luò)基礎(chǔ)設(shè)施的一部分。相比于移動(dòng)Ad hoc網(wǎng)絡(luò),WMN中的節(jié)點(diǎn)有相對(duì)固定的位置并且通過(guò)一個(gè)或多個(gè)網(wǎng)關(guān)和Internet通信。盡管傳統(tǒng)的Ad-h

2、oc路由選擇算法可以用于WMN,但是它們的性能都不太理想。因?yàn)檫@些算法都基于在WMN中不成立的一些假設(shè)(如高速移動(dòng),沒(méi)有基礎(chǔ)設(shè)施等,而這些假設(shè)對(duì)于無(wú)線Mesh 網(wǎng)絡(luò)環(huán)境中路由性能有很大的影響?，F(xiàn)在已經(jīng)提出了許多關(guān)于WMN的路由協(xié)議。這些協(xié)議可以根據(jù)不同的標(biāo)準(zhǔn)分成不同的種類。如按其對(duì)網(wǎng)絡(luò)拓?fù)渥兓姆磻?yīng)來(lái)分類,可以分為先應(yīng)式(或路由表驅(qū)動(dòng)路由協(xié)議和反應(yīng)式(或按需路由協(xié)議(但也存在幾個(gè)混合協(xié)議;若按路由節(jié)點(diǎn)的功能和網(wǎng)絡(luò)組織結(jié)構(gòu)分類,可以分為平面路由協(xié)議和分層路由協(xié)議。先應(yīng)式路由協(xié)議定期的發(fā)送網(wǎng)絡(luò)拓?fù)湫畔⒉⒅芷谛缘夭檎衣酚?而反應(yīng)式路由協(xié)議如動(dòng)態(tài)源路由協(xié)議(DSR3和Ad-hoc按需矢量路由協(xié)議(AO

3、DV4是根據(jù)需要查找路由的。一般來(lái)說(shuō),反應(yīng)式路由協(xié)議在分組投遞率,路由開銷和能效方面比先應(yīng)式路由性能更好。然而在平面路由協(xié)議中,一混合無(wú)線Mesh網(wǎng)絡(luò)中改進(jìn)的分層AODV路由協(xié)議曾文麗,裴廷睿,張朝霞,趙智ZENG Wen-li,PEI Ting-rui,ZHANG Zhao-xia,ZHAO Zhi湘潭大學(xué)信息工程學(xué)院,湖南湘潭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摘要:路由是無(wú)線Mesh網(wǎng)絡(luò)發(fā)展中的一個(gè)研究熱點(diǎn)。無(wú)線Mesh網(wǎng)絡(luò)從移動(dòng)Ad hoc網(wǎng)絡(luò)中借鑒了許多路由選擇算法作為路由的解決方案,但是這些方法都不太理想或者沒(méi)有達(dá)到性能的最優(yōu)化,且沒(méi)有利用到無(wú)線Mesh網(wǎng)絡(luò)自身的特點(diǎn)。提出了一個(gè)改進(jìn)的分層AODV路由協(xié)議(IH-A

8、DOV,它表現(xiàn)出了更好的可擴(kuò)展性和網(wǎng)絡(luò)性能,當(dāng)一條路由丟失時(shí),它使尋找替代路由的路由開銷得到降低。在IH-AODV中,還提出了一種新技術(shù),即最新鏈路發(fā)現(xiàn)機(jī)制。利用NS-2軟件對(duì)AODV和IH-AODV進(jìn)行了仿真比較?；诨旌蠠o(wú)線Mesh網(wǎng)絡(luò)的仿真結(jié)果表明,IH-AODV在大的網(wǎng)絡(luò)中也表現(xiàn)出了很好的擴(kuò)展性,相對(duì)于AODV,在其他性能方面也表現(xiàn)良好甚至更優(yōu)。關(guān)鍵詞:無(wú)線Mesh網(wǎng)絡(luò);路由協(xié)議;分層;Ad-hoc按需矢量路由作者簡(jiǎn)介:曾文麗(1981-,女,碩士研究生,主要研究方向?yàn)闊o(wú)線Mesh網(wǎng)絡(luò)關(guān)鍵技術(shù)的研究等;裴廷睿(1970-,男,副教授,博士,主要研究領(lǐng)域涉及移動(dòng)通信、自組織移動(dòng)網(wǎng)絡(luò)及無(wú)線

9、資源管理等;張朝霞(1984-,女,碩士研究生,主要研究方向?yàn)闊o(wú)線Mesh網(wǎng)絡(luò)關(guān)鍵技術(shù)的研究等;趙智(1986-,男,碩士研究生,主要研究方向?yàn)闊o(wú)線Mesh網(wǎng)絡(luò)關(guān)鍵技術(shù)的研究等。收稿日期:2008-12-15修回日期:2009-03-05Computer Engineering and Applications計(jì)算機(jī)工程與應(yīng)用125,j:0Computer Engineering and Applications 計(jì)算機(jī)工程與應(yīng)用2010,46(19條路由總是維持從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑中的所有節(jié)點(diǎn)。這種方式對(duì)于路由較短的小型網(wǎng)絡(luò)有很好的表現(xiàn)。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大,路徑將會(huì)變長(zhǎng)并且經(jīng)常容易斷裂。

10、由于新的路由發(fā)現(xiàn)和丟棄過(guò)于頻繁,路由開銷將會(huì)增大。這些是平面路由協(xié)議中固然存在的問(wèn)題。分層路由協(xié)議能有效地解決平面路由協(xié)議中存在的這些問(wèn)題。在分層路由協(xié)議中,網(wǎng)絡(luò)節(jié)點(diǎn)被分組,并且每個(gè)節(jié)點(diǎn)子集都被分配了特定的功能。簇頭網(wǎng)關(guān)交換路由協(xié)議(CGSR 5是一種典型的分層路由協(xié)議。CGSR 將網(wǎng)絡(luò)分成半徑為預(yù)先定義好跳數(shù)的圓形簇集。當(dāng)網(wǎng)絡(luò)被分成簇集后,本地路由維護(hù)行為只會(huì)對(duì)少數(shù)鄰居簇集產(chǎn)生影響,而其他簇集將不會(huì)受到影響。Way Point Routing (WPR 6是一種改進(jìn)的分層路由協(xié)議,它只對(duì)當(dāng)前路由進(jìn)行維護(hù),它將一條路由的許多中間節(jié)點(diǎn)選作Way Point 節(jié)點(diǎn),并通過(guò)Way Point 節(jié)點(diǎn)將

11、這條路由分成許多段,從而達(dá)到簡(jiǎn)化路由維護(hù)的目的。盡管分層路由協(xié)議實(shí)現(xiàn)了可擴(kuò)展性,但其算法通常十分復(fù)雜,使得它很難應(yīng)用。旨在提供一種基于AODV 的輕量級(jí)分層路由協(xié)議。因?yàn)閃MN 本身是一種介于移動(dòng)Ad-hoc 網(wǎng)絡(luò)和靜態(tài)網(wǎng)絡(luò)之間的混合網(wǎng)絡(luò),所以使混合WMN 中不同特性的節(jié)點(diǎn)具有不同的功能,然后根據(jù)不同的功能將它們劃分為半徑為單跳的簇(正如CGSR 。在簇內(nèi),不再有簇頭,而只有定義的特殊節(jié)點(diǎn)WayPoint (正如WPR 。在簇間,仍然使用AODV 路由協(xié)議。將CGSR 和WPR 的特性結(jié)合到AODV 中,提出了一種改進(jìn)的分層AODV 路由協(xié)議,即IH-AODV 。2無(wú)線Mesh 網(wǎng)絡(luò)中的IH-

12、AODV 路由協(xié)議2.1IH-AODV 路由協(xié)議的客觀需求WMN 發(fā)展的主要目的是為了提供可靠的數(shù)據(jù)通信和負(fù)載平衡。許多假設(shè)(如高速移動(dòng)和無(wú)基礎(chǔ)設(shè)施等在無(wú)線Mesh 網(wǎng)絡(luò)中不再成立;而且大部分已有的路由選擇方案沒(méi)有利用到WMN 的優(yōu)良特性。這就使得為WMN 制定專門的路由協(xié)議非常必要。在AODV 中,由于其路由發(fā)現(xiàn)過(guò)程是基于泛洪的,所以造成了較重的業(yè)務(wù)負(fù)載。再加上路由發(fā)現(xiàn)過(guò)程需要較長(zhǎng)的時(shí)延,使得單純的AODV 路由不太適應(yīng)于實(shí)時(shí)業(yè)務(wù)通信中?；赪MN 中許多節(jié)點(diǎn)的移動(dòng)性低,如果能在路由發(fā)現(xiàn)階段,通過(guò)將節(jié)點(diǎn)分簇來(lái)減少活動(dòng)節(jié)點(diǎn)的數(shù)目,那么發(fā)送分組前的等待時(shí)延可能會(huì)減小,并且由于簇機(jī)制使得新節(jié)點(diǎn)加入

13、到路由中變得更加容易,使得可擴(kuò)展性問(wèn)題也能得到解決。IH-AODV 路由協(xié)議的設(shè)計(jì)目標(biāo)是在保留AODV 優(yōu)點(diǎn)的同時(shí)提高其網(wǎng)絡(luò)擴(kuò)展?jié)撃?以支持更大規(guī)模的網(wǎng)絡(luò)。設(shè)計(jì)主要包括如下特點(diǎn):(1最新鏈路檢測(cè)機(jī)制這是IH-AODV 應(yīng)用的一種新技術(shù),稱這種機(jī)制為最新鏈路檢測(cè)。它旨在對(duì)加入簇的節(jié)點(diǎn)進(jìn)行快速路由發(fā)現(xiàn),能夠提高路由發(fā)現(xiàn)的速度和效率。對(duì)于路由維護(hù),這種技術(shù)也非常有用。下面將對(duì)這種機(jī)制進(jìn)行詳細(xì)的介紹。(2與AODV 兼容AODV 是一種被廣泛認(rèn)可的路由協(xié)議。IH-AODV 的一個(gè)重要設(shè)計(jì)原則是要與AODV 兼容,即在同一個(gè)網(wǎng)絡(luò)中,應(yīng)用AODV 協(xié)議的節(jié)點(diǎn)能與應(yīng)用IH-AODV 協(xié)議的節(jié)點(diǎn)協(xié)同工作。為此

14、,保留了所有AODV 路由控制報(bào)文,并且根據(jù)需要增加了一些新的控制報(bào)文。事實(shí)上,為了最小化發(fā)現(xiàn)時(shí)延,把這些節(jié)點(diǎn)設(shè)定為靜態(tài)節(jié)點(diǎn)。(3本地路由修復(fù)在文獻(xiàn)7中提出了一種優(yōu)化AODV 的本地路由修復(fù)機(jī)制,但是它主要適用于發(fā)生在目的節(jié)點(diǎn)附近的路由失效情況。隨著網(wǎng)絡(luò)規(guī)模的增加,源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的路徑將變得更長(zhǎng),這種機(jī)制不能再發(fā)揮很好的作用。IH-AODV 讓斷裂鏈路的上游節(jié)點(diǎn)用本地修復(fù)來(lái)取代發(fā)送RERR 。如果本地修復(fù)成功,路由請(qǐng)求分組將會(huì)從目的節(jié)點(diǎn)或者一個(gè)與目的節(jié)點(diǎn)之間存在一條有效路由的節(jié)點(diǎn)返回。如果沒(méi)有返回路由應(yīng)答分組,即本地修復(fù)沒(méi)有成功,那么就會(huì)給源節(jié)點(diǎn)發(fā)送一個(gè)RERR 路由錯(cuò)誤消息。2.2IH

15、-AODV 路由協(xié)議路由發(fā)現(xiàn)路由機(jī)制是在混合無(wú)線Mesh 網(wǎng)絡(luò)環(huán)境下提出的,并做了如下假設(shè):首先,在網(wǎng)絡(luò)中有很多靜態(tài)節(jié)點(diǎn),定義這些節(jié)點(diǎn)為Way Point (WP 節(jié)點(diǎn),其他節(jié)點(diǎn)稱為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混合無(wú)線Mesh 網(wǎng)絡(luò)1262010,46(19成員節(jié)點(diǎn)。其次,在首次發(fā)起路由發(fā)現(xiàn)過(guò)程時(shí),假設(shè)已經(jīng)有一個(gè)初始化分簇。WP節(jié)點(diǎn)是簇中的功能節(jié)點(diǎn),它們有與傳統(tǒng)AODV中節(jié)點(diǎn)相同的特點(diǎn),并且還維護(hù)著一個(gè)簇成員列表。在每個(gè)簇中,都有Start-WP和End-WP兩個(gè)WP節(jié)點(diǎn)。兩個(gè)相鄰簇共享一個(gè)WP節(jié)點(diǎn),這個(gè)節(jié)點(diǎn)作為上游簇的End-WP,下游簇的Start-WP。如果這兩個(gè)節(jié)點(diǎn)在單跳范圍內(nèi),它們就可以直接通信。在簇成

17、員列表中,包含了簇成員信息和表示各簇成員所在鏈路的新鮮度序號(hào),即當(dāng)簇成員所在鏈路被使用一次,初始值為0的新鮮度序號(hào)就加1。新鮮度的值是用來(lái)確定簇中的最新路徑的,這類似AODV中使用的序列號(hào)機(jī)制,用于確定到達(dá)目的節(jié)點(diǎn)的路由請(qǐng)求報(bào)文是不是最新路由。稱上述的這種機(jī)制為最新鏈路檢測(cè)。當(dāng)一個(gè)普通節(jié)點(diǎn)需要一條路由進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時(shí),它就發(fā)送“Hello”消息給它所有的單跳鄰居節(jié)點(diǎn),鄰近的WP節(jié)點(diǎn)接收到消息后,就檢查這個(gè)節(jié)點(diǎn)是否已經(jīng)在簇成員列表中,如果不在,就反饋一個(gè)應(yīng)答消息來(lái)邀請(qǐng)這個(gè)節(jié)點(diǎn)加入簇中,當(dāng)這個(gè)節(jié)點(diǎn)分別接收到同一個(gè)簇的Start-WP節(jié)點(diǎn)和End-WP節(jié)點(diǎn)的應(yīng)答消息時(shí),它就發(fā)送加入請(qǐng)求并且加入到簇中,

18、成為簇成員節(jié)點(diǎn)CM,并向該簇WP節(jié)點(diǎn)發(fā)出數(shù)據(jù)轉(zhuǎn)發(fā)請(qǐng)求,然后由WP節(jié)點(diǎn)像AODV一樣開始路由發(fā)現(xiàn)過(guò)程8。圖2舉例說(shuō)明了源節(jié)點(diǎn)S找到到達(dá)目的節(jié)點(diǎn)d的路由發(fā)現(xiàn)過(guò)程。選擇節(jié)點(diǎn)S,A,B和C作為WP節(jié)點(diǎn),一個(gè)簇可以通過(guò)它的Start-WP和End-WP節(jié)點(diǎn)來(lái)區(qū)別。節(jié)點(diǎn)d到l是CM節(jié)點(diǎn),包括節(jié)點(diǎn)d。在圖2中,有三個(gè)簇,分別為:S-e/f-A,A-g/h/ i-B和B-j/k/l/d-C。為了區(qū)分WP節(jié)點(diǎn)和CM節(jié)點(diǎn),用大寫字母來(lái)標(biāo)識(shí)WP節(jié)點(diǎn),用小寫字母來(lái)標(biāo)識(shí)CM節(jié)點(diǎn)。按照上述路由發(fā)現(xiàn)機(jī)制,可以找到一條路由如:S-A-h-B-d。由于CM節(jié)點(diǎn)的動(dòng)態(tài)特性,路由中的鏈路可能會(huì)失效,路由維護(hù)就是處理路由斷裂的機(jī)制。

19、IH-AODV擴(kuò)展了許多AODV中路由維護(hù)的特性。例如,用RERR消息通知受到斷裂鏈路影響的節(jié)點(diǎn)等。除此之外,IH-AODV還增加了一些有關(guān)簇的維護(hù)機(jī)制,包括最新鏈路檢測(cè)和本地路由修復(fù)。最新鏈路檢測(cè)不僅用于路由發(fā)現(xiàn),還用于路由維護(hù),當(dāng)一條鏈路失效時(shí),其所在簇的單跳WP節(jié)點(diǎn)首先檢查它的簇成員列表,然后找到除這條斷裂鏈路外的最新路徑,即新鮮度序號(hào)僅比斷裂鏈路小的路徑。如果因?yàn)榇爻蓡T列表更新,而導(dǎo)致最新鏈路檢測(cè)不能進(jìn)行,本地修復(fù)將作為第二級(jí)路由修復(fù)機(jī)制。簇成員列表更新是指舊簇已經(jīng)被改變,本地路由修復(fù)將會(huì)在一個(gè)簇范圍內(nèi)啟動(dòng)7。在路由修復(fù)初始化到得到修復(fù)結(jié)果這段時(shí)間,上游節(jié)點(diǎn)將會(huì)對(duì)從需要修復(fù)的路由上發(fā)送

20、過(guò)來(lái)的數(shù)據(jù)包進(jìn)行緩存。如果修復(fù)成功,上游節(jié)點(diǎn)將把緩存的數(shù)據(jù)包重新發(fā)送出去,否則,它將啟用AODV中的典型修復(fù),并繼續(xù)緩存未能發(fā)送的數(shù)據(jù)包。本地路由修復(fù)試圖在失效簇的Start-WP和End-WP節(jié)點(diǎn)之間建立一條新的路徑。如果修復(fù)成功,被修復(fù)的路由上的WP節(jié)點(diǎn)將不會(huì)改變,源節(jié)點(diǎn)也不會(huì)得到通知,因?yàn)閿?shù)據(jù)包能沿著同樣的WP節(jié)點(diǎn)繼續(xù)發(fā)送。圖3給出了一個(gè)示例:簇A-g/h/i-B的初始路徑是A-h-B,h 和B之間鏈路斷裂了。當(dāng)最新鏈路檢測(cè)成功時(shí),簇A-g/h/i-B 的一條新路徑A-g-B就建立了起來(lái)。這樣就建立了一條S-A-g-B-d的新路由。3性能評(píng)估3.1仿真使用在無(wú)線網(wǎng)絡(luò)領(lǐng)域流行的網(wǎng)絡(luò)仿真軟件

21、NS29進(jìn)行仿真。在相同條件下,通過(guò)將IH-AODV與AODV協(xié)議進(jìn)行對(duì)比來(lái)評(píng)估IH-AODV的性能。在仿真中,設(shè)定MAC層協(xié)議為IEEE802.11標(biāo)準(zhǔn)分布式協(xié)調(diào)功能DCF。業(yè)務(wù)源為恒比特率CBR。源-目的節(jié)點(diǎn)對(duì)在網(wǎng)絡(luò)中隨機(jī)分布。初始化時(shí),節(jié)點(diǎn)在仿真區(qū)域均勻的分布,一半節(jié)點(diǎn)為靜態(tài)的,另一半節(jié)點(diǎn)為隨機(jī)移動(dòng)狀態(tài)。移動(dòng)節(jié)點(diǎn)的速率在0m/s至20m/s之間。仿真停留時(shí)間設(shè)置為30s。數(shù)據(jù)包大小為512字節(jié)。將在兩個(gè)場(chǎng)景下進(jìn)行仿真。首先,設(shè)置CBR業(yè)務(wù)流的值為常數(shù)20,網(wǎng)絡(luò)節(jié)點(diǎn)從100個(gè)逐漸增加到1000個(gè)。網(wǎng)絡(luò)大小和面積范圍的選擇見表1,這使得節(jié)點(diǎn)密度接近常數(shù),可以恰當(dāng)?shù)胤磻?yīng)路由協(xié)議的可擴(kuò)展性。其次

22、,研究了在400個(gè)節(jié)點(diǎn)的情況下,CBR業(yè)務(wù)流在20和60之間的協(xié)議性能。每個(gè)仿真運(yùn)行900s的時(shí)間。每個(gè)抽樣數(shù)據(jù)的值取5次仿真的平均值。對(duì)3個(gè)性能指標(biāo)進(jìn)行評(píng)估,即分組投遞率,平均控制開銷和端到端時(shí)延。(1分組投遞率:目的節(jié)點(diǎn)接收到的數(shù)據(jù)包個(gè)數(shù)與源發(fā)送的數(shù)據(jù)包個(gè)數(shù)之比。(2平均控制開銷:路由發(fā)現(xiàn),簇維護(hù)和路由修復(fù)等的控制開銷。(3端到端時(shí)延:由路由發(fā)現(xiàn),傳輸?shù)纫鸬乃锌赡軙r(shí)延的平均時(shí)延。3.2結(jié)果和分析在第一個(gè)場(chǎng)景中,將研究協(xié)議的可擴(kuò)展性。仿真結(jié)果如圖4所示。由圖4(a可知,即使在有1000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中,IH-AODV和AODV的分組投遞率都很高,但是IH-AODV比AODV遞交率持續(xù)的高出

23、1%2%。這是因?yàn)镾ef Aihgjk cldB圖2路由發(fā)現(xiàn)過(guò)程SefAihgjk cldB圖3路由修復(fù)過(guò)程大小(節(jié)點(diǎn)個(gè)數(shù)1002004006008001000面積/m21400×14002000×20002800×28003500×35004000×40004500×4500表1網(wǎng)絡(luò)大小及網(wǎng)絡(luò)面積對(duì)應(yīng)表曾文麗,裴廷睿,張朝霞,等:混合無(wú)線Mesh網(wǎng)絡(luò)中改進(jìn)的分層AODV路由協(xié)議127÷一;一、;一rl-.。 睜:。j Computer Engineering and Applications 計(jì)算機(jī)工程與應(yīng)用2010,46

24、(19IH-AODV 分層次的維護(hù)路由,增加了一個(gè)簇成員列表,并且能夠在本地對(duì)斷裂的路由進(jìn)行修復(fù),所以當(dāng)前路由的存活時(shí)間更長(zhǎng),并且遞交的數(shù)據(jù)包個(gè)數(shù)更多。圖4(b 是兩個(gè)路由協(xié)議的路由開銷比較。當(dāng)節(jié)點(diǎn)數(shù)超過(guò)200時(shí),AODV 的開銷迅速增加,而IH-AODV 由于應(yīng)用了路由分層,所以開銷較小。IH-AODV 的低控制開銷對(duì)WMN 的擴(kuò)展起著至關(guān)重要的作用。圖4(c 表明,當(dāng)節(jié)點(diǎn)數(shù)少于400時(shí),IH-AODV 的端到端時(shí)延比AODV 的時(shí)延要稍大一些。這是因?yàn)樾纬纱匦枰獣r(shí)間開銷。但當(dāng)網(wǎng)絡(luò)規(guī)模擴(kuò)大以后,情況就發(fā)生了變化。在大型網(wǎng)絡(luò)中,由于最新鏈路檢測(cè)和路由修復(fù)機(jī)制能夠快速的恢復(fù)斷 裂路由,使得數(shù)據(jù)包

25、不必等待另一輪路由發(fā)現(xiàn)后再發(fā)送,所以IH-AODV 的端到端時(shí)延更小。以上結(jié)果表明,IH-AODV 結(jié)合了AODV 和分層路由的一些優(yōu)良特性并展示了良好的性能。在第二個(gè)場(chǎng)景中,對(duì)路由協(xié)議進(jìn)行了3個(gè)性能指標(biāo)的對(duì)比,如圖5所示。圖5(a 給出了分組投遞率的比較。由于網(wǎng)絡(luò)變得非常擁擠,AODV 的分組投遞率隨著數(shù)據(jù)流數(shù)目的增加而變小。然而IH-AODV 卻仍然表現(xiàn)良好。從圖5(b 可以看出,改進(jìn)后IH-AODV 協(xié)議的開銷 比AODV 協(xié)議有所降低。原因是:IH-AODV 中維護(hù)一個(gè)簇成員列表,使得路由發(fā)現(xiàn)開銷減少,并且該協(xié)議采用分簇維護(hù)機(jī)制,減少了每個(gè)數(shù)據(jù)流的控制包,從而降低了開銷。從圖5(c 可

26、知,隨著數(shù)據(jù)流的增加,IH-AODV ,IH-AODV的端到端時(shí)延要比AODV 小,這是因?yàn)镮H-AODV 通過(guò)簇成員列表能使節(jié)點(diǎn)在發(fā)送數(shù)據(jù)包前更容易找到一條路由。但是建立簇和簇成員列表會(huì)增加更多的時(shí)延。以上仿真結(jié)果表明,IH-AODV 在網(wǎng)絡(luò)變得擁塞時(shí),表現(xiàn)更好。4結(jié)論基于Ad hoc 中典型的AODV 協(xié)議,提出了一種新的路由協(xié)議模型IH-AODV 。該協(xié)議能分層地維護(hù)節(jié)點(diǎn),是對(duì)平面和分層路由查找方法的特性的結(jié)合。仿真結(jié)果表明,由于低路由時(shí)延和開銷,IH-AODV 提供 了更好的分組投遞率,并且在保留了AODV 的優(yōu)點(diǎn)的同時(shí),實(shí)現(xiàn)了更好的可擴(kuò)展性。其次,IH-AODV 還有效地利用了WMN

27、 的特點(diǎn)。由于在IH-AODV 中,沒(méi)有考慮通信安全和WP 和CM 節(jié)點(diǎn)的能量平衡等問(wèn)題,所以將進(jìn)一步研究,使IH-AODV 協(xié)議更加可靠并具有可行性。參考文獻(xiàn):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 端到端時(shí)延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 端到端時(shí)延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 分組投遞率(下轉(zhuǎn)131頁(yè)128一:i /H 5/ll/。:;i ;j ;,;i 一數(shù)據(jù)規(guī)模/萬(wàn)條排序時(shí)間/m sAB C D E圖2

33、排序時(shí)間與數(shù)據(jù)規(guī)模關(guān)系圖網(wǎng)絡(luò)語(yǔ)料所抽取的1600萬(wàn)條中文字符串。為了更好地分析算法性能,分別進(jìn)行了橫向和縱向?qū)Ρ仍囼?yàn),前者是改進(jìn)算法同快速排序算法所進(jìn)行的對(duì)比試驗(yàn),后者是指本文算法針對(duì)不同規(guī)模語(yǔ)料的多次對(duì)比試驗(yàn),結(jié)果見表1和表2。3.2試驗(yàn)數(shù)據(jù)分析從表1中可見,對(duì)不同規(guī)模的試驗(yàn)數(shù)據(jù),基數(shù)排序算法都比快速排序算法具有更快速度;且隨著數(shù)據(jù)規(guī)模的增長(zhǎng),二者的時(shí)間消耗差距在增大。試驗(yàn)結(jié)果實(shí)現(xiàn)了對(duì)前述理論分析結(jié)果的良好驗(yàn)證:基數(shù)排序的時(shí)間復(fù)雜度低于快速排序,所以取得了更快的排序速度。表2中數(shù)據(jù)是為了減少偶然性影響,使用改進(jìn)的基數(shù)排序算法,對(duì)同一規(guī)模數(shù)據(jù)進(jìn)行了5次試驗(yàn),且不同規(guī)模的語(yǔ)料進(jìn)行了縱向比較。為說(shuō)

34、明排序速度與規(guī)模之間的關(guān)系,繪制了二者的關(guān)系圖,見圖2。從圖中可見,排序時(shí)間與數(shù)據(jù)規(guī)模之間是一種線性關(guān)系,這也很好地驗(yàn)證了改進(jìn)算法時(shí)間復(fù)雜度為O (dn 的論斷。4結(jié)束語(yǔ)通過(guò)對(duì)基數(shù)排序算法的研究,使用快速轉(zhuǎn)換機(jī)制將漢字字符串轉(zhuǎn)化為與之等長(zhǎng)的整型數(shù)組,用以實(shí)現(xiàn)中文字符串的基數(shù)排序。理論分析和試驗(yàn)結(jié)果都表明,改進(jìn)的基數(shù)排序方法可以實(shí)現(xiàn)對(duì)中文字符串的線性時(shí)間排序。該方法不僅適于漢語(yǔ),同樣適用于其他語(yǔ)種的字串快速排序。但在實(shí)現(xiàn)基數(shù)排序算法時(shí),為了提高速度,對(duì)不同長(zhǎng)度的字串使用等長(zhǎng)的整型數(shù)組,造成內(nèi)存浪費(fèi)。下一步考慮改進(jìn)算法實(shí)現(xiàn)機(jī)制,在不降低性能的同時(shí),減少內(nèi)存消耗,提高總體性能。致謝研究中使用了搜狗實(shí)

35、驗(yàn)室的大規(guī)模中文網(wǎng)絡(luò)文本語(yǔ)料,并得到了倪劍莉老師的大力協(xié)助,在此表示感謝。參考文獻(xiàn):1盧開澄.計(jì)算機(jī)算法導(dǎo)引:設(shè)計(jì)與分析M.2版.北京:清華大學(xué)出版社,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、,黃輝,宋濤.桶外排序算法的抽樣分點(diǎn)分發(fā)策略J.軟件學(xué)報(bào),2005,16(5:643-651.5楊磊,宋濤.基于數(shù)組的桶排序算法J.計(jì)算機(jī)研究與發(fā)展,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何文明,崔俊芝.針對(duì)字符串等復(fù)雜數(shù)據(jù)的一種新的高效分檔混合排序算法J.小型微型計(jì)算機(jī)系統(tǒng),2004,25(4:698-701.8嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu):C 語(yǔ)言版M.北京:清華大學(xué)出版社,1997.11001600A119381598524922B1140