一種基于跨層的無線Mesh網絡路由協議

邵 艷,蘇 杰,肖明波

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

關鍵詞:路由協議;無線Mesh網絡(WMN);跨層設計;鏈路幀投遞率(LFDR)

中圖分類號:TN915.02文獻標識碼: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網絡(WMN)是在移動自組織網絡(MANET)和無線局域網(WLAN)基礎上發展起來的一項網絡技術,它作為下一代因特網核心網的無線版本,有效地解決“最后一公里”瓶頸問題[1],是一種具有動態自組織、自配置、高速率、高容量等特性的分布式寬帶無線網絡。

當前,WMN的MAC協議大多采用IEEE 802.11,使用這種MAC協議的Mesh網絡也稱為Wi-Mesh。跨層設計的主要思想在網絡各層共享相關的信息,對無線網絡進行整體設計,因此所有層間可以交互信息,使得協議棧能夠以全局的方式適應特定應用所需的QoS 和網絡狀況的變化,并根據系統的約束條件和網絡特征來進行綜合優化,實現對網絡資源的有效分配,提高網絡的綜合性能[2]。跨層路由[3]便是將跨層的設計思想引入路由的設計中,進而提高網絡性能。WMN的很多技術特點和優勢來自于Mesh多跳路由[4],該文的目的就是在盡量保持網絡分層結構的基礎上,運用跨層的方法設計出一個適用于Wi-Mesh(后文中直接統稱WMN)的高性能路由協議。

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

1 改進的路由協議CMRP

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

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

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

對于鏈路中的兩個節點,當下游節點接收到上游節點發給它的RTS時,說明上游節點成功獲得預定信道,將有數據幀發送給此下游節點。下游節點用計數器Ttran記錄接收到的此類RTS的次數。Ttran表示下游節點感知到的上游節點傳送給它的數據幀的發送次數。

每當下游節點成功接收到上游節點發送的數據幀并校驗無錯時,表明上游節點成功將數據幀發送給此下游節點。下游節點使用一個計數器Trec記錄接收到的此類幀次數。Trec表明下游節點成功接收來自上游節點的數據幀次數。

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

LFDR=(Trec/Ttran)×100%

(1)

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

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

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

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

(2)

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

(2) PFDR參數與CMRP的結合

CMRP主要選路原則:最優的PFDR。

LFDR的獲取:在CMRP中,每個節點都維護著其他節點到本節點的LFDR信息。LFDR是按需更新的,當需要(收到RREQ)時,節點提取從MAC計算出來的LFDR,存放到自身狀態變量中。

PFDR的獲取:在CMRP的路由發現過程中,中間節點收到RREQ后,在做任何處理前,先將本節點LFDR值與RREQ中的PFDR值相乘,用相乘結果更新RREQ的路由質量值。

PFDR的使用1:在CMRP的路由發現過程中,目的節點會收到多條從源節點發來經過不同路徑的同一類RREQ,通過這些RREQ中的路由質量信息,CMRP可以選擇優質路由。

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

PFDR的使用3:在CMRP的源路由數據包傳輸過程中,若存在非相關多徑路由,源節點可以通過路由質量信息分配流量給這些路徑。

1.2 擁塞避免

WMN的數據業務具有很大的隨機性與突發性,使得網絡中容易出現某些節點的負載突然加重,局部發生擁塞。隊列長度是擁塞的主要標志, MAC層的剩余帶寬、延遲等參數也主要由隊列長度決定。再加上隊列的長度相對于其他MAC層參數變化慢,能較穩定地反映網絡擁塞程度,許多文獻都以節點隊列長度所定義的節點負載度來衡量擁塞的程度[8]。因此,該文選用MAC層接口隊列來度量節點負載。

節點負載度與擁塞系數:

當MAC層輸出隊列的長度到達一定程度(擁塞門限)時,記為Qth b,網絡出現擁塞。定義此時MAC層輸出隊列的長度Qth與最大長度Qmax b的比值為擁塞系數ρ:

ρ=Qth/Qmax, ρ≤1

(3)

將MAC輸出隊列當前長度Q b與最大長度Qmax的比值,定義為節點負載度Ld:

Ld=Q/Qmax

(4)

這樣,當隊列當前長度Ld<ρ時,網絡未出現擁塞;當Ld≥ρ時,網絡出現擁塞。

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

1.3 CMRP的其他性能改進

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

2 網絡仿真與分析

本文使用QualNet網絡仿真工具[10],對改進的CMRP與原DSR進行路由協議的性能進行仿真比較,以證實改進思路的正確性與改進結果的有效性。仿真中采用的性能參數分別是網絡平均吞吐率、網絡平均時延、網絡平均抖動。

WMN是準靜態網絡,仿真場景中節點全部設置靜態,如圖1所示,場景中節點分布呈8×8的正方形網格結構,節點間距為180 m,仿真中比較的是DSR與CMRP的性能,仿真時間設定為200 s。

圖1 隨機業務模型場景

為了更加真實地模擬因特網數據業務流的情況,突出業務流的隨機特性與突發特性,采用Quanet中的應用層協議Traffic Gen來產生具有某種分布特性的隨機業務流。根據研究,以Pareto分布,ON/OFF模型生成業務流的疊加符合因特網業務流的特性[11] 。

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

圖2 平均吞吐率-發包率的性能曲線

圖3 平均時延-發包率的性能曲線

圖4 平均抖動-發包率的性能曲線

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

仿真結論如下:

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

3 結 語

根據WMN的節點準靜態特性,基于DSR設計了一種跨層多徑路由協議CMRP,在其中添加主動路由的思想,增加了鏈路質量判決、擁塞避免及多徑路由、路由斷鏈判定等機制。仿真結果表明,比起原來的DSR,CMRP在平均吞吐率、平均時延、平均抖動等網絡性能上都有較大的提高,達到了預期的目標,可以更好地適用于WMN。

參考文獻

[1]方旭明.下一代無線因特網技術:無線Mesh網絡[M].北京:人民郵電出版社,2005.

[2]羅明勝,黃聯芬,姚彥.無線網絡跨層設計的研究現狀及展望 [J].移動通信,2005,29(7):95-98.

[3]方旭明,馬忠建.無線Mesh網絡的跨層設計理論與關鍵技術[J].西南交通大學學報,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] 沈強,方旭明.無線Mesh網中一種基于綜合準則的DSR擴展路由方法[J].電子學報,2007,35(4):614-620.

[8]郭嘉豐,張信明,謝飛,等.基于節點空閑度的自適應移動Ad Hoc網絡路由協議[J].軟件學報,2005,16(5):960-969.

[9]于明剛.論無線網狀網路由分組接收率的提高與網絡性能的改進[D].長春:吉林大學,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.