基于無線網(wǎng)狀網(wǎng)ＤＳＲ的多路徑分流帶寬路由算法

楊　帥　沈　武

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

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

中圖分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)22-pppp-0c

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

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

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

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

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

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

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

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

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

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

1 按需路由DSR算法

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

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

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

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

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

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

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

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

2.2 改進(jìn)DSR建立多條路徑

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

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

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

2.3 分流帶寬方案

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

2.4 預(yù)約帶寬方案

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

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

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

3 結(jié)束語

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

參考文獻(xiàn):

[1] 劉正藍(lán),朱淼良.基于邊界到邊界帶寬估計(jì)的數(shù)據(jù)包標(biāo)記器[J].通信學(xué)報(bào),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.