楊　帥　沈　武

摘要:無線MESH網(wǎng)絡(luò)是一種高速度,高容量的多點對多點網(wǎng)絡(luò),是一種新型的解決“最后一英里”問題的分布式網(wǎng)絡(luò),可把它堪稱Ad Hoc網(wǎng)絡(luò)的簡化版本。無線MESH網(wǎng)絡(luò)中的路由是它的一項關(guān)鍵技術(shù),基于此,本論為對無線MESH網(wǎng)絡(luò)的路由協(xié)議進行了改進研究,文中首先介紹了Ad Hoc網(wǎng)絡(luò)三種路由協(xié)議,重點研究了其中一種動態(tài)源路由協(xié)議(DSR)的具體實現(xiàn)過程,并在支持QoS服務(wù)基礎(chǔ)上,對DSR協(xié)議進行了改進,并提出了一種新的路由算法MSBR多路徑分流帶寬算法,該算法可以在源節(jié)點和目的節(jié)點之間找到多條路徑并解決單條路徑上不能滿足的帶寬請求時分配到多條路徑上的問題。

關(guān)鍵詞:無線MESH;動態(tài)源路由協(xié)議DSR;QoS;MSBR;

中圖分類號:TP301文獻標識碼:A文章編號:1009-3044(2009)22-pppp-0c

WMN網(wǎng)絡(luò)節(jié)點的移動性使得網(wǎng)絡(luò)拓撲結(jié)構(gòu)不斷變化,傳統(tǒng)的基于因特網(wǎng)的路由協(xié)議無法適應(yīng)這些特性,需要有專門的應(yīng)用于無線Mesh 網(wǎng)絡(luò)的路由協(xié)議。設(shè)計無線Mesh路由協(xié)議,當前主要有兩種做法:一種是根據(jù)WMN 與無線Ad Hoc 網(wǎng)特點相似的特征,將Ad Hoc開發(fā)的路由協(xié)議如DSDV (目的序列距離矢量路由協(xié)議)、DSR(動態(tài)源路由協(xié)議)、TORA(臨時按序路由算法) 和AODV(Ad Hoc按需距離矢量路由協(xié)議)移植過來用于WMN;另一種是開發(fā)無線下專用的路由協(xié)議,如PWRP(可預(yù)測的無線路由協(xié)議)、MR-LQSR(多射頻鏈路質(zhì)量源路由)等協(xié)議。單從性能角度來考察,必須開發(fā)適用于無線環(huán)境的Mesh 路由協(xié)議。然而,從實現(xiàn)的復(fù)雜性考慮,改進已有路由協(xié)議是最快捷的方式。

我們提到無線Mesh網(wǎng)絡(luò)的路由協(xié)議可以借鑒Ad Hoc網(wǎng)絡(luò)的路由協(xié)議。Ad Hoc 網(wǎng)絡(luò)路由協(xié)議從大的類別上不外乎分為三種:一種為先驗式路由協(xié)議,也叫表驅(qū)動式路由協(xié)議;一種為反應(yīng)式路由協(xié)議,也叫源驅(qū)動按需路由協(xié)議;最后一種就是二者的混合,叫混合式路由協(xié)議。無線Mesh網(wǎng)絡(luò)也可以沿用這三種類型的路由協(xié)議。

先驗式路由協(xié)議簡介

先驗式路由協(xié)議又被稱為表驅(qū)動路由,是一種基于表格的路由協(xié)議。在這種協(xié)議中,每個節(jié)點維護一張或多張表格,這些表格包含到達網(wǎng)絡(luò)中其它所有節(jié)點的路由信息。當檢測到網(wǎng)絡(luò)拓撲結(jié)構(gòu)發(fā)生變化時,節(jié)點在網(wǎng)絡(luò)中發(fā)送路由更新信息。收到更新信息的節(jié)點更新自己的表格,以維護一致的、及時的、準確的路由信息。

典型特征:每個節(jié)點都要周期性廣播路由信息,主動地發(fā)現(xiàn)并維護路由表。

表驅(qū)動:典型協(xié)議DSDV(Destination Sequenced Distance Vector)

反應(yīng)式路由選擇協(xié)議簡介

反應(yīng)式路由選擇協(xié)議又稱為源啟動按需路由,是一種當需要時才查找路由的路由 選擇方式。節(jié)點并不保存及時準確的路由信息。當源節(jié)點要向目的節(jié)點發(fā)送報文時,源節(jié)點在網(wǎng)絡(luò)中發(fā)起路由查找過程,找到相應(yīng)的路由后,才開始發(fā)送報文。為了提高效率,節(jié)點可以將找到的路由保存在緩存中供后續(xù)發(fā)送使用。

典型特征:只有在需要發(fā)送數(shù)據(jù)時,源站點才尋找路由

按需路由(事件驅(qū)動)典型協(xié)議:AODV(Ad Hoc On-demand Distance Vector)DSR(Dynamic Source Routing)

1 按需路由DSR算法

DSR是一種按需(on-demand)的路由協(xié)議,是一種基于源路由的按需路由協(xié)議,它使用源路由算法,每個節(jié)點都有一個Route Cache,記錄路由的路徑軌跡,當某源節(jié)點要發(fā)送數(shù)據(jù)給某一目的節(jié)點時,首先查看自己的Route Cache中是否存在現(xiàn)成的路徑可以使用(有時甚至保存有多條),如果不存在,則啟動Route Discovery過程,即廣播一個RREQ請求分組,其中包含目的節(jié)點地址、源節(jié)點地址、Request ID和一個Route Record(用于按順序逐個記錄此RREQ所途經(jīng)的節(jié)點地址)

算法描述:如圖 1-1所示 當節(jié)點收到Route Request時,如果在此之前已收到過同一源節(jié)點、同一ID的RREQ(表示這是重復(fù)的),則該請求分組丟棄,如果在Route Cache中發(fā)現(xiàn)已經(jīng)有到目的節(jié)點的路徑(表示自己可提供到達目的節(jié)點的路徑),則把此路徑加入Route Record并創(chuàng)建 RREP應(yīng)答分組,回復(fù)源節(jié)點并丟棄該請求分組,如果自己是目的節(jié)點,此時Route Record中記錄的就是從源節(jié)點到目的節(jié)點的路徑信息,把此路徑加入RREP應(yīng)答分組,回復(fù)給源節(jié)點,并丟棄該請求分組,否則,代表自己是中間節(jié)點,把自己的地址附加在Route Record中,然后再繼續(xù)廣播Route Discovery過程中的Route Reply過程以一條路徑為例,N8-N5-N2-N1 從目的節(jié)點N8回到源節(jié)點N1。

2 多路徑分流帶寬路由算法MDBR算法

提供Qos保障服務(wù)是無限Mesh和Internet 互聯(lián)的關(guān)鍵問題。而在無線Mesh網(wǎng)絡(luò)中,QoS不外乎主要包括3個方面(1)延時。(2)帶寬。(3)花費。其中主要指標是前兩個。提供多條路徑可以在一定程度使得前兩個指標得到一定改善。該文著重解決第二個方面。

多路徑路由的優(yōu)點:(1) 加快傳輸速度,減少時延;(2) 防止斷裂,增加穩(wěn)定度(3) 有利于負載平衡;(4) 減少對帶寬的要求。

多路徑算法概述:先解釋一下非相關(guān)路徑的概念,所謂非相關(guān)路徑是指兩條路徑?jīng)]有公用鏈路。我們這里提到的多路徑也都指的是非相關(guān)路徑?；贒SR協(xié)議進行改進是因為DSR協(xié)議可以在源節(jié)點到目的節(jié)點之間建立多條非相關(guān)路徑,并接可支持單向鏈路。

2.1 當前DSR協(xié)議的不足

由上述DRS協(xié)議可以看到DSR協(xié)議雖然可以找到源節(jié)點到目的節(jié)點的多條路徑,但這些路徑不能保證非相關(guān)性:以圖1.2為例,若節(jié)點C已經(jīng)存在到節(jié)點D的路由,分別為C-E-D和C-F-D,這時,源節(jié)點S的RREQ分組(目的節(jié)點仍為D)到達節(jié)點C,按傳統(tǒng)的DSR協(xié)議,則第一個到達節(jié)點C的RREQ消息被回應(yīng),其余后到得RREQ消息被摒棄。也就是說S-A-C和S-B-C只能取一條,假設(shè)為S-A-C,這樣,源節(jié)點若有分組要傳輸,則只有一條路徑可選,要么S-A-C-E-D,要么S-A-C-F-D。但兩條路徑不可同時用,應(yīng)為這兩條路徑公用了S-A-C段。實際還是建立了單一的一條路徑。如果源節(jié)點S要發(fā)送數(shù)據(jù)給目的節(jié)點D,帶寬請求為x,而這時,若只啟用一條路徑,每條路徑可支持帶寬就不能滿足帶寬請求,這時就要啟用兩條路徑同時工作,這樣就可以滿足帶寬請求。

2.2 改進DSR建立多條路徑

MDBR算法可以解決上述問題。在源節(jié)點和目的節(jié)點之間建立多條路徑。對DSR協(xié)議改進如下:

傳統(tǒng)的DSR協(xié)議只有在目的節(jié)點處才可以處理多個RREQ消息,即后到得RREQ消息不被丟棄,現(xiàn)在我們使目的節(jié)點和存在到目的節(jié)點路由的中間節(jié)點都可以處理多個RREQ消息,此數(shù)目可由我們自己確定。

例如,如圖1.2所示,假設(shè)節(jié)點C已存在到達節(jié)點D的路由C-E-D和C-F-D 。當節(jié)點S 有數(shù)據(jù)要發(fā)送到節(jié)點D時,節(jié)點S 首先發(fā)送RREQ消息,節(jié)點A和節(jié)點B收到R R E Q消息后,由于A和B不是目的節(jié)點,也不存在到達目的節(jié)點的路由,則節(jié)點A和B轉(zhuǎn)發(fā)R R E Q消息。這樣,節(jié)點C和E 收到R R E Q消息,節(jié)點C存在到達目的節(jié)點D的路由,同樣,節(jié)點E也存在到達目的節(jié)點D的路由?？梢?C和E都是中間節(jié)點,根據(jù)改進,節(jié)點C 會收到兩個R R E Q ,一個從節(jié)點A來,一個從節(jié)點B來,節(jié)點C會對這兩個R R E Q消息都給出回應(yīng)。這樣,節(jié)點C沿兩條路徑發(fā)送應(yīng)答消息,一條為C-A-S ,另一條為C-B-S。最后,節(jié)點S 得到拓撲圖中包含節(jié)點S,A,B,C,E,F,D以及鏈路S-A,A-C,S-,B-C,C-E ,C-F,E-D ,F-D。 顯然比原協(xié)議得到更完全的拓撲圖。 這樣,節(jié)點有分組要發(fā)送時,通過拓撲圖就有更多的路徑可以選擇,比如就有兩條非相關(guān)路徑 S-A-C-E-D和S-B-C-F-D以供選擇。

2.3 分流帶寬方案

由此我們找到了多條路徑,針對帶寬不足的狀況我們按以下算法解決:當有節(jié)點有分組要發(fā)送時,先在自己存儲的拓撲圖中查找到可以到達目的節(jié)點的所有路徑,以這些路徑為基礎(chǔ),需找到可以滿足帶寬要求的多條路徑。源節(jié)點發(fā)送探測分組,此探測分組含有一定數(shù)目的PACKET,每一個包負責(zé)尋找一條通路。當探測分組到達一個節(jié)點,如果節(jié)點不是目的節(jié)點,則節(jié)點將此探測分組按照一定的策略轉(zhuǎn)發(fā)給下一節(jié)點,并為這個包在轉(zhuǎn)發(fā)鏈路上保留相應(yīng)帶寬。如果節(jié)點沒有滿足帶寬請求的轉(zhuǎn)發(fā)鏈路,則在該節(jié)點處將包分為多個SUB-PACKET,,每一個SUB-PACKET負責(zé)尋找滿足部分帶寬請求的路徑,這樣,在目的節(jié)點會收到多個PACKET和SUB-PACKET,如果一個PACKET的全部SUB-PACKET都到達,則目的節(jié)點發(fā)送給路由應(yīng)答消息給源節(jié)點。具體過程見圖1.4源節(jié)點到目的節(jié)點的帶寬請求為5,在路徑S-C-D,中,鏈路S-C和C-D都預(yù)留帶寬5;在路徑S-A-E-D和S-A-F-D中,在節(jié)點A處包發(fā)生分離,一部分完成帶寬請求3的尋路,一部分完成帶寬請求2的尋路,并找到相應(yīng)路徑。這樣,就找到兩條滿足帶寬請求的通路。

2.4 預(yù)約帶寬方案

但是這種方法有一個問題,就是因為沒有進行資源預(yù)約,可能會發(fā)現(xiàn)爭搶帶寬的現(xiàn)象,也即是說應(yīng)該有一種方法使得鏈路的剩余帶寬信息能很快的反饋到各個節(jié)點。

關(guān)于各個節(jié)點剩余帶寬的解決方案:我們?yōu)槊恳粋€節(jié)點建立一張節(jié)點狀態(tài)表;(我們稱之為轉(zhuǎn)發(fā)表),用于帶寬估計,圖1.5為帶寬估計體系結(jié)構(gòu),表1所示為轉(zhuǎn)發(fā)表結(jié)構(gòu)。

在入口節(jié)點處,當有數(shù)據(jù)包到達時,查看其IP頭部的源地址,以確定改數(shù)據(jù)包從哪個節(jié)點進入MESH網(wǎng)絡(luò),再查看轉(zhuǎn)發(fā)表是否有匹配項(即是否有相應(yīng)的peerEdge),如果存在匹配項,則將數(shù)據(jù)包的大小累加到相應(yīng)項的recvByte中;如果不存在匹配項,則建立新的狀態(tài)項,并將數(shù)據(jù)包的大小累加進其recvByte中。如果該數(shù)據(jù)包被出口節(jié)點的隊列管理機制丟棄,則該數(shù)據(jù)包的大小應(yīng)累加進其相應(yīng)項的dropByte。recvByte和dropByte分別表示出口節(jié)點本地所接受的數(shù)據(jù)量和本地所丟棄的數(shù)據(jù)量。發(fā)送信息的源節(jié)點,在每一固定時間間隔向特定的目的節(jié)點發(fā)送探測包,鏈路上每一個節(jié)點在接受到探測數(shù)據(jù)包以后,查看狀態(tài)表,以(recvByte-dropByte)/(now-lastStatTime)做為該鏈路上所能使用的帶寬估計,并將該帶寬估計反饋給源節(jié)點。同時將轉(zhuǎn)發(fā)狀態(tài)表中相應(yīng)狀態(tài)項的recvByte和dropByte置為0,將lastStatTime置為當前時間。如果在路由查找時,帶寬估計夠PACKET或SUB-PACKET傳遞,預(yù)留相應(yīng)帶寬,置為1,并啟動一定的時間(即生存期)在過生存期后,預(yù)留帶寬被釋放,否則,置為0。

3 結(jié)束語

由于時間倉促,將該路由算法性能的仿真并未能完成。由于該路由算法發(fā)現(xiàn)多條路徑,并且需要計算節(jié)點的剩余帶寬,可能會出現(xiàn)相對較大的時延,但是該算法對多路徑防止斷裂,增加穩(wěn)定度,有利于負載平衡,傳遞數(shù)據(jù)時,減少對帶寬的要求,都能到很好的改善?？傊?由于無線Mesh網(wǎng)絡(luò)中節(jié)點的移動性,以及鏈路的易受干擾性,使得數(shù)據(jù)易丟失,采用多條路徑可以在一定程度上減少和克服這種缺點,并支持QoS,不失為一種較好的解決辦法。

參考文獻:

[1] 劉正藍,朱淼良.基于邊界到邊界帶寬估計的數(shù)據(jù)包標記器[J].通信學(xué)報,2003,8.

[2] 王曉燕.無線Mesh網(wǎng)絡(luò)路由協(xié)議的研究[D].西安電子科及大學(xué),2005.

[3] 樊自甫,萬曉榆. 新一代寬帶無線網(wǎng)絡(luò)結(jié)構(gòu)[J].通信世界.2003,9:42-44.

[4] Guangyu Pei and Mario Gerla,Mobility Mangement in Hierarchial Multi-hop Mobile Wireless Net works,IEEE,1999.