邵 艷,蘇 杰,肖明波

摘 要:無線Mesh網(wǎng)絡(luò)的很多技術(shù)特點(diǎn)和優(yōu)勢來自于Mesh多跳路由。因此,路由協(xié)議的研究與設(shè)計(jì)是無線Mesh網(wǎng)絡(luò)技術(shù)的一個重要課題。由于無線Mesh網(wǎng)絡(luò)有自身負(fù)載均衡、路由容錯與網(wǎng)絡(luò)容量等要求,因此運(yùn)用跨層設(shè)計(jì),采用更好的路由參數(shù),使用多徑路由等方法已經(jīng)成為無線Mesh網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)的重要思路。根據(jù)無線Mesh的網(wǎng)絡(luò)特點(diǎn),按照其路由協(xié)議的設(shè)計(jì)要求,分析了路由協(xié)議DSR在Mesh網(wǎng)絡(luò)中的不足,引入跨層設(shè)計(jì)的方法,提出了采用路由質(zhì)量路徑幀投遞率(PFDR)為路由準(zhǔn)則,并具有負(fù)載平衡、擁塞避免的路由協(xié)議CMRP。分析和仿真結(jié)果表明,CMRP在保持Mesh網(wǎng)絡(luò)自身優(yōu)點(diǎn)的同時,比起DSR在網(wǎng)絡(luò)性能上有了較大的提升,在吞吐率方面有了很大的提高,相應(yīng)的時延、抖動參數(shù)均有了大幅的下降,更加適用于無線Mesh網(wǎng)絡(luò)。

關(guān)鍵詞:路由協(xié)議;無線Mesh網(wǎng)絡(luò)(WMN);跨層設(shè)計(jì);鏈路幀投遞率(LFDR)

中圖分類號:TN915.02文獻(xiàn)標(biāo)識碼:A

文章編號:1004-373X(2009)19-027-03

Routing Protocol of Wireless Mesh Network Based on Cross-layer

SHAO Yan,SU Jie,XIAO Mingbo

(Xiamen University,Xiamen,361005,China)

Abstract:Wireless Mesh Network (WMN) is a technology with outstanding technical characteristics and advantages,many of which originate from the muti-hop routing.Therefore,the study and design of routing protocol is of utmost importance for WMN.In order to satisfy the requirements of WMN such as load balancing,fault tolerance,network capacity,techniques such as cross-layer design and multi-path routing may have to be considered in protocol design for WMN.The deficiencies of Dynamic Source Routing(DSR) protocol applied in WMN is analysed,and an improved routing protocol Cross-layer Multi-path Routing Protocol(CMRP) is proposed,using PFDR (Path Frame Deliver Rate) as the measure.Analysis and simulation results show that CMRP greatly improved the network performance,in load balancing,congestion avoidance,link failure sensing mechanism and the capability of multi-path routing.

Keywords:routing protocol;wireless Mesh network;cross-layer design;link frame deliver rate

0 引 言

無線Mesh網(wǎng)絡(luò)(WMN)是在移動自組織網(wǎng)絡(luò)(MANET)和無線局域網(wǎng)(WLAN)基礎(chǔ)上發(fā)展起來的一項(xiàng)網(wǎng)絡(luò)技術(shù),它作為下一代因特網(wǎng)核心網(wǎng)的無線版本,有效地解決“最后一公里”瓶頸問題[1],是一種具有動態(tài)自組織、自配置、高速率、高容量等特性的分布式寬帶無線網(wǎng)絡(luò)。

當(dāng)前,WMN的MAC協(xié)議大多采用IEEE 802.11,使用這種MAC協(xié)議的Mesh網(wǎng)絡(luò)也稱為Wi-Mesh?？鐚釉O(shè)計(jì)的主要思想在網(wǎng)絡(luò)各層共享相關(guān)的信息,對無線網(wǎng)絡(luò)進(jìn)行整體設(shè)計(jì),因此所有層間可以交互信息,使得協(xié)議棧能夠以全局的方式適應(yīng)特定應(yīng)用所需的QoS 和網(wǎng)絡(luò)狀況的變化,并根據(jù)系統(tǒng)的約束條件和網(wǎng)絡(luò)特征來進(jìn)行綜合優(yōu)化,實(shí)現(xiàn)對網(wǎng)絡(luò)資源的有效分配,提高網(wǎng)絡(luò)的綜合性能[2]?？鐚勇酚蒣3]便是將跨層的設(shè)計(jì)思想引入路由的設(shè)計(jì)中,進(jìn)而提高網(wǎng)絡(luò)性能。WMN的很多技術(shù)特點(diǎn)和優(yōu)勢來自于Mesh多跳路由[4],該文的目的就是在盡量保持網(wǎng)絡(luò)分層結(jié)構(gòu)的基礎(chǔ)上,運(yùn)用跨層的方法設(shè)計(jì)出一個適用于Wi-Mesh(后文中直接統(tǒng)稱WMN)的高性能路由協(xié)議。

動態(tài)源路由(DSR)是一種以最小跳數(shù)為度量,基于源路由機(jī)制,采用按需路由策略的路由協(xié)議,它允許節(jié)點(diǎn)從多跳無線網(wǎng)絡(luò)中動態(tài)地發(fā)現(xiàn)一條通向任何目的節(jié)點(diǎn)且跳數(shù)最少的路由。DSR的路由發(fā)現(xiàn)與維護(hù)按需進(jìn)行,不需周期性傳遞控制包,可節(jié)省大量帶寬,但DSR在路由選擇時采用的最小跳數(shù)度量準(zhǔn)則,可能導(dǎo)致每一跳傳輸距離過大,從而導(dǎo)致接收端信號減弱,給網(wǎng)絡(luò)帶來不必要的重傳,而且DSR沒有充分利用所獲得的多徑路由,也沒考慮負(fù)載平衡來提高網(wǎng)絡(luò)性能。這里對DSR進(jìn)行適當(dāng)?shù)母倪M(jìn),希望既保持DSR的優(yōu)點(diǎn),又避免上述缺陷。

1 改進(jìn)的路由協(xié)議CMRP

1.1 新路由準(zhǔn)則:路徑幀投遞率(PFDR)

用來表征鏈路質(zhì)量的參數(shù)有多種,如 mETX[5],ENT [5]等,這些鏈路質(zhì)量參數(shù)都可從網(wǎng)絡(luò)層直接獲得,文獻(xiàn)[6]分析了上述參數(shù)的優(yōu)劣。網(wǎng)絡(luò)層的鏈路質(zhì)量參數(shù)主要都是基于一個最基本的鏈路性能:鏈路包投遞率(Link Packet Deliver Rate,LPDR)。LPDR表征了數(shù)據(jù)包經(jīng)過某條鏈路時,在網(wǎng)絡(luò)層可成功傳送的概率。但僅限于網(wǎng)絡(luò)層不足以精確衡量某一鏈路的質(zhì)量,而在MAC層則可相對客觀地反映鏈路的質(zhì)量。對于無線網(wǎng)絡(luò),當(dāng)信號差、誤碼率較高,接收的數(shù)據(jù)幀多次校驗(yàn)錯誤,使多次重傳失敗時的丟包能較好地反映鏈路質(zhì)量。此時鏈路質(zhì)量與節(jié)點(diǎn)位置、距離、發(fā)射功率、調(diào)制技術(shù)等有關(guān),路由協(xié)議根據(jù)此情況下獲得的參數(shù),可得到較優(yōu)的路由。文中采用跨層交互的方法,在MAC層計(jì)算出與LPDR類似的參數(shù):鏈路幀投遞率(Link Frame Deliver Rate,LFDR),作為度量鏈路質(zhì)量和選路的參數(shù)。

一般來說,LFDR是由鏈路的前向節(jié)點(diǎn)計(jì)算的,在按需式路由的路由請求中,上游節(jié)點(diǎn)要將全部已知下游節(jié)點(diǎn)的地址與相應(yīng)的鏈路質(zhì)量都加入請求信息包中,這大大增加了請求信息包長度,且使其長度變得很不穩(wěn)定。CMRP采用后向計(jì)算的方法獲得LFDR,整條路由的PFDR就是路由中每段鏈路LFDR的連乘[7]。

對于鏈路中的兩個節(jié)點(diǎn),當(dāng)下游節(jié)點(diǎn)接收到上游節(jié)點(diǎn)發(fā)給它的RTS時,說明上游節(jié)點(diǎn)成功獲得預(yù)定信道,將有數(shù)據(jù)幀發(fā)送給此下游節(jié)點(diǎn)。下游節(jié)點(diǎn)用計(jì)數(shù)器Ttran記錄接收到的此類RTS的次數(shù)。Ttran表示下游節(jié)點(diǎn)感知到的上游節(jié)點(diǎn)傳送給它的數(shù)據(jù)幀的發(fā)送次數(shù)。

每當(dāng)下游節(jié)點(diǎn)成功接收到上游節(jié)點(diǎn)發(fā)送的數(shù)據(jù)幀并校驗(yàn)無錯時,表明上游節(jié)點(diǎn)成功將數(shù)據(jù)幀發(fā)送給此下游節(jié)點(diǎn)。下游節(jié)點(diǎn)使用一個計(jì)數(shù)器Trec記錄接收到的此類幀次數(shù)。Trec表明下游節(jié)點(diǎn)成功接收來自上游節(jié)點(diǎn)的數(shù)據(jù)幀次數(shù)。

因此,鏈路的后向幀傳遞率計(jì)算公式為:

LFDR=(Trec/Ttran)×100%

(1)

式(1)中的LFDR就是鏈路幀傳遞率。

(1) 路徑幀傳遞率(Path Frame Deliver Rate,PFDR)

LFDR只能反映某條鏈路情況,而由概率知識可知,整條路由的PFDR與路由中的每段鏈路LFDR的關(guān)系是:

PFDR=∏n-1i=1LFDRi,i+1

(2)

式中:n表示此路徑的節(jié)點(diǎn)總各數(shù);i表示此路徑從源節(jié)點(diǎn)起算的第i個中間節(jié)點(diǎn),i=1表示源節(jié)點(diǎn),i=n 表示目的節(jié)點(diǎn);LFDRi,i+1則表示第i個節(jié)點(diǎn)到第i+1個節(jié)間的鏈路幀傳遞率。

(2) PFDR參數(shù)與CMRP的結(jié)合

CMRP主要選路原則:最優(yōu)的PFDR。

LFDR的獲取:在CMRP中,每個節(jié)點(diǎn)都維護(hù)著其他節(jié)點(diǎn)到本節(jié)點(diǎn)的LFDR信息。LFDR是按需更新的,當(dāng)需要(收到RREQ)時,節(jié)點(diǎn)提取從MAC計(jì)算出來的LFDR,存放到自身狀態(tài)變量中。

PFDR的獲取:在CMRP的路由發(fā)現(xiàn)過程中,中間節(jié)點(diǎn)收到RREQ后,在做任何處理前,先將本節(jié)點(diǎn)LFDR值與RREQ中的PFDR值相乘,用相乘結(jié)果更新RREQ的路由質(zhì)量值。

PFDR的使用1:在CMRP的路由發(fā)現(xiàn)過程中,目的節(jié)點(diǎn)會收到多條從源節(jié)點(diǎn)發(fā)來經(jīng)過不同路徑的同一類RREQ,通過這些RREQ中的路由質(zhì)量信息,CMRP可以選擇優(yōu)質(zhì)路由。

PFDR的使用2:在CMRP的源路由數(shù)據(jù)包傳輸過程中,通過路由質(zhì)量信息,可以基于路由質(zhì)量的變化情況對路由進(jìn)行主動維護(hù)。

PFDR的使用3:在CMRP的源路由數(shù)據(jù)包傳輸過程中,若存在非相關(guān)多徑路由,源節(jié)點(diǎn)可以通過路由質(zhì)量信息分配流量給這些路徑。

1.2 擁塞避免

WMN的數(shù)據(jù)業(yè)務(wù)具有很大的隨機(jī)性與突發(fā)性,使得網(wǎng)絡(luò)中容易出現(xiàn)某些節(jié)點(diǎn)的負(fù)載突然加重,局部發(fā)生擁塞。隊(duì)列長度是擁塞的主要標(biāo)志, MAC層的剩余帶寬、延遲等參數(shù)也主要由隊(duì)列長度決定。再加上隊(duì)列的長度相對于其他MAC層參數(shù)變化慢,能較穩(wěn)定地反映網(wǎng)絡(luò)擁塞程度,許多文獻(xiàn)都以節(jié)點(diǎn)隊(duì)列長度所定義的節(jié)點(diǎn)負(fù)載度來衡量擁塞的程度[8]。因此,該文選用MAC層接口隊(duì)列來度量節(jié)點(diǎn)負(fù)載。

節(jié)點(diǎn)負(fù)載度與擁塞系數(shù):

當(dāng)MAC層輸出隊(duì)列的長度到達(dá)一定程度(擁塞門限)時,記為Qth b,網(wǎng)絡(luò)出現(xiàn)擁塞。定義此時MAC層輸出隊(duì)列的長度Qth與最大長度Qmax b的比值為擁塞系數(shù)ρ:

ρ=Qth/Qmax, ρ≤1

(3)

將MAC輸出隊(duì)列當(dāng)前長度Q b與最大長度Qmax的比值,定義為節(jié)點(diǎn)負(fù)載度Ld:

Ld=Q/Qmax

(4)

這樣,當(dāng)隊(duì)列當(dāng)前長度Ld<ρ時,網(wǎng)絡(luò)未出現(xiàn)擁塞;當(dāng)Ld≥ρ時,網(wǎng)絡(luò)出現(xiàn)擁塞。

通過建模和分析可以得出擁塞系數(shù)ρ的參考值,它可用仿真時的指導(dǎo)。根據(jù)文獻(xiàn)[9],可以取ρ=Smax,其中Smax為MAC層的最大歸一化吞吐率。另外,在CMRP中還通過引入預(yù)警門限Pre(Pre值略小于ρ),增加了預(yù)測擁塞的能力。

1.3 CMRP的其他性能改進(jìn)

在CMRP中除了提出新的路由準(zhǔn)則PFDR和擁塞避免參數(shù)Ld之外,還在非相關(guān)多徑路由、斷鏈判定和主動路由方面進(jìn)行了考慮,進(jìn)一步提高網(wǎng)絡(luò)的性能。中間節(jié)點(diǎn)通過對RREQ的轉(zhuǎn)發(fā)次數(shù)進(jìn)行限制,使目的節(jié)點(diǎn)可以根據(jù)PFDR選擇最優(yōu)非相關(guān)路由進(jìn)行回復(fù)。在CMRP中,根據(jù)下游節(jié)點(diǎn)是否可以收到上游節(jié)點(diǎn)的RTS情況來判斷是否斷鏈,并且在斷鏈的上游節(jié)點(diǎn)處進(jìn)行維護(hù)。除此之外,CMRP還改進(jìn)了偵聽路由緩存機(jī)制,CMRP將按需路由與主動路由相結(jié)合,適用于節(jié)點(diǎn)變化小而業(yè)務(wù)要求高的WMN中。

2 網(wǎng)絡(luò)仿真與分析

本文使用QualNet網(wǎng)絡(luò)仿真工具[10],對改進(jìn)的CMRP與原DSR進(jìn)行路由協(xié)議的性能進(jìn)行仿真比較,以證實(shí)改進(jìn)思路的正確性與改進(jìn)結(jié)果的有效性。仿真中采用的性能參數(shù)分別是網(wǎng)絡(luò)平均吞吐率、網(wǎng)絡(luò)平均時延、網(wǎng)絡(luò)平均抖動。

WMN是準(zhǔn)靜態(tài)網(wǎng)絡(luò),仿真場景中節(jié)點(diǎn)全部設(shè)置靜態(tài),如圖1所示,場景中節(jié)點(diǎn)分布呈8×8的正方形網(wǎng)格結(jié)構(gòu),節(jié)點(diǎn)間距為180 m,仿真中比較的是DSR與CMRP的性能,仿真時間設(shè)定為200 s。

圖1 隨機(jī)業(yè)務(wù)模型場景

為了更加真實(shí)地模擬因特網(wǎng)數(shù)據(jù)業(yè)務(wù)流的情況,突出業(yè)務(wù)流的隨機(jī)特性與突發(fā)特性,采用Quanet中的應(yīng)用層協(xié)議Traffic Gen來產(chǎn)生具有某種分布特性的隨機(jī)業(yè)務(wù)流。根據(jù)研究,以Pareto分布,ON/OFF模型生成業(yè)務(wù)流的疊加符合因特網(wǎng)業(yè)務(wù)流的特性[11] 。

隨機(jī)選取16條Traffic Gen業(yè)務(wù)流,ON期間比例分別為20%,40%,60%,80%,100%,也就是Traffic Gen業(yè)務(wù)流的發(fā)送概率從0.2增加到1.0,相應(yīng)業(yè)務(wù)流的突發(fā)性就越來越低了。第二組隨機(jī)選取16條Traffic Gen業(yè)務(wù)流,其余設(shè)置同于第一組。Traffic Gen的ON期間長度分布由均一分布改為Pareto分布。仿真結(jié)果如圖2~圖4所示。

圖2 平均吞吐率-發(fā)包率的性能曲線

圖3 平均時延-發(fā)包率的性能曲線

圖4 平均抖動-發(fā)包率的性能曲線

從圖2~圖4可以看出,對于重負(fù)載下16條隨機(jī)業(yè)務(wù)流的情況,DSR與CMRP的差距非常明顯,CMRP的性能優(yōu)越更加體現(xiàn)出來。CMRP在保持性能平穩(wěn)的同時,平均吞吐量約為DSR的三倍,而平均時延及平均抖動都在DSR的40%以下。

仿真結(jié)論如下:

為了真實(shí)地模擬因特網(wǎng)數(shù)據(jù)業(yè)務(wù)流量特性,設(shè)置了16條隨機(jī)連接的ON/OFF業(yè)務(wù)流場景中,比較平均吞吐率、平均時延、平均抖動三個網(wǎng)絡(luò)性能參數(shù)可以看到,CMRP的性能比起DSR有了極大的提高,能夠適應(yīng)網(wǎng)絡(luò)中業(yè)務(wù)流的隨機(jī)特性與突發(fā)特性。

3 結(jié) 語

根據(jù)WMN的節(jié)點(diǎn)準(zhǔn)靜態(tài)特性,基于DSR設(shè)計(jì)了一種跨層多徑路由協(xié)議CMRP,在其中添加主動路由的思想,增加了鏈路質(zhì)量判決、擁塞避免及多徑路由、路由斷鏈判定等機(jī)制。仿真結(jié)果表明,比起原來的DSR,CMRP在平均吞吐率、平均時延、平均抖動等網(wǎng)絡(luò)性能上都有較大的提高,達(dá)到了預(yù)期的目標(biāo),可以更好地適用于WMN。

參考文獻(xiàn)

[1]方旭明.下一代無線因特網(wǎng)技術(shù):無線Mesh網(wǎng)絡(luò)[M].北京:人民郵電出版社,2005.

[2]羅明勝,黃聯(lián)芬,姚彥.無線網(wǎng)絡(luò)跨層設(shè)計(jì)的研究現(xiàn)狀及展望 [J].移動通信,2005,29(7):95-98.

[3]方旭明,馬忠建.無線Mesh網(wǎng)絡(luò)的跨層設(shè)計(jì)理論與關(guān)鍵技術(shù)[J].西南交通大學(xué)學(xué)報(bào),2005(12):711-719.

[4]Bruno R,Conti M,Gregori E.Mesh Networks:Commodity Multihop Ad Hoc Networks [J].IEEE Communications Magazine,2005,43(3):123 -131.

[5]Koksal C E,Balakrishnan H.Quality Aware Routing Me-trics for Time-varying Wireless Mesh Networks[J].IEEE Journal on Selected Areas in Communications,2006:1 984-1 994.

[6]Ekram Hossain,Kin K Leung.Wireless Mesh Networks:Architectures and Protocols[M].Springer,2007.

[7] 沈強(qiáng),方旭明.無線Mesh網(wǎng)中一種基于綜合準(zhǔn)則的DSR擴(kuò)展路由方法[J].電子學(xué)報(bào),2007,35(4):614-620.

[8]郭嘉豐,張信明,謝飛,等.基于節(jié)點(diǎn)空閑度的自適應(yīng)移動Ad Hoc網(wǎng)絡(luò)路由協(xié)議[J].軟件學(xué)報(bào),2005,16(5):960-969.

[9]于明剛.論無線網(wǎng)狀網(wǎng)路由分組接收率的提高與網(wǎng)絡(luò)性能的改進(jìn)[D].長春:吉林大學(xué),2007.

[10]Scalable Network Technologies[EB/OL].http:/www.QualNet.com,2005.

[11]Hans-Peter Schwefel,Lester Lipsky.Impact of Aggregated,Self-Similar ON/OFF traffic on Delay in Stationary Queueing Models (Ext.Version)[A].Performance Evaluation[OL].2000.