余 智 汪慧君 肖雪露

(武漢船舶通信研究所 武漢 430250)

?

基于HWMP協(xié)議的無線網絡路由判據研究*

余 智 汪慧君 肖雪露

(武漢船舶通信研究所 武漢 430250)

HWMP路由協(xié)議采用標準空時開銷判據進行路徑選擇時,僅考慮了鏈路中節(jié)點所消耗的信道資源總量,不能綜合考慮鏈路的質量、負載及其受干擾的情況。針對該問題,論文提出了一種新的路徑選擇算法,該方法將MAC層中更多的信道質量參數提取到路由判據中來,能綜合考慮復雜多變的無線信道多種因數,有助于提高無線網絡吞吐量,降低端到端時延。經過仿真實驗表明,新路由判別方法能夠優(yōu)化802.11s的路徑選擇,提高網絡的整體性能。

MAC層; 路由判據; 端到端時延; 吞吐量

Class Number TM933

1 引言

無線Mesh網絡(Wireless Mesh Networks)是一種新興的無線組網技術,支持無線多跳路由,又稱“無線網格網”。無線Mesh網絡結構作為解決“最后一公里”網絡接入瓶頸問題的方案,具有較高的可靠性、較大的伸縮性、較強的自愈性和較低的投資成本,因此,無線網格網已成為當前網絡研究的技術熱點[1]。

在網絡研究領域,路由協(xié)議一直是研究的重點。IEEE802.11標準工作組針對無線網格網制定了802.11s標準,該標準中使用混合無線網格協(xié)議(Hybrid Wireless Mesh Protocol,HWMP)作為其默認的路徑選擇協(xié)議。HWMP協(xié)議是一種混合式路徑選擇協(xié)議[2],同時結合了反應式和先驗式路由協(xié)議的特點。該協(xié)議工作在MAC層,和傳統(tǒng)的三層網絡協(xié)議不同,HWMP協(xié)議中通過MAC地址進行路徑尋址、數據轉發(fā)[3]。

為得到更加優(yōu)化的路徑選擇,提高無線Mesh網絡的性能,國內外關于HWMP路由協(xié)議的研究主要集中在以下幾個方面:一是對路徑選擇判據的研究,二是對HWMP的實際性能進行測試,三是根據HWMP協(xié)議的問題,提出新的路由算法或是在HWMP基礎上進行算法改進。本文主要針對路徑選擇判據進行相應的研究,提出一種新的路徑選擇判別算法,并對該算法進行仿真實驗。試驗證明該方法優(yōu)化了路徑選擇,降低了端到端時延,提高了無線網絡吞吐量。

2 傳統(tǒng)空時路徑選擇判別方法

為了確?？蓴U展框架中不同路徑選擇協(xié)議間基本的互操作,IEEE802.11s標準定義了基于空時(airtime)消耗的默認的鏈路metric來度量無線選擇路徑[4]。當幀經過某鏈路時,采用下式計算空時鏈路metric值Ca,來度量該鏈路傳輸該幀所消耗的信道資源總量。路徑metric是路徑中所有鏈路metric的總和[5～6]。

(1)

上式中,Oca為信道接入負載,Op為MAC協(xié)議負載,Bt為測試幀中的比特數,這三個參數均是常量,不同IEEE802.11傳輸技術下其取值如表1所示。傳輸比特率r(Mbit/s)指Mesh節(jié)點基于當前無線環(huán)境傳輸一個大小為Bt數據幀的速度,幀錯誤率efr是指標準Bt大小幀在當前傳輸比特率r下,由于傳輸錯誤造成的幀丟失概率。

表1 空時消耗判據參數典型取值

可以看出,基于射頻感知的空時路徑選擇判據雖然考慮了MAC層中的一些參數作為路由判據的參量,據此進行路徑選擇,能得到稍優(yōu)化的路由;但由于Oca,Op等參數都為固定值,不能體現不斷變化的無線信道環(huán)境,因此,需要研究新的路徑判別方法,使得網絡在復雜多變的無線環(huán)境中能得到更加優(yōu)化的路徑。

3 新路徑選擇判別算法

由移動節(jié)點構成的自組織無線Mesh網絡,不同鏈路的質量是不同的,且是不斷變化的?？諘r路徑判別是802.11s中HWMP協(xié)議默認的路徑選擇判據,它雖然選取了MAC層中的參數作為路徑選擇的度量標準,但所選取的MAC層參數遠遠不夠,沒有考慮鏈路的質量、擁塞及負載等情況,也沒有考慮其他節(jié)點的干擾;而這些都影響著整個網絡的性能,如果路徑選擇沒有將這些關鍵因素都考慮進來的話,就無法適應復雜多變的無線信道環(huán)境,無法得到最優(yōu)的路徑,無法最大優(yōu)化網絡的性能。

HWMP中路徑選擇參數注重考慮了不同網絡間路徑選擇操作的兼容性,卻沒有很好考慮到各鏈路類型的差異對路徑選擇的影響。因此,需要針對其在無線多跳網格網中所存在的不足,研究新的路徑選擇判據,綜合考慮多方面因素,爭取從MAC層中提取更多的參數引入到判據中來,提供信道質量判別,幫助選擇一條鏈路質量穩(wěn)定、時延較小、因鏈路質量及擁塞問題造成重傳需求最小的路徑,避免網絡擁塞。

新路由判據在現有空時判據基礎上,至少應包含: 1) 對擁塞及鏈路質量的衡量判別, 2) 對節(jié)點干擾信息的感知。

3.1 鏈路質量和路徑擁塞判別方法

鏈路質量和路徑擁塞情況可以通過引入期望傳輸效率來表示。

節(jié)點在發(fā)送RTS或數據時,如果在規(guī)定的時間內沒有收到相應的CTS或者ACK,就會啟用重傳機制;數據包丟失或者鏈路擁塞造成RTS重傳[7]。所以利用RTSFailureCount和ACKFailureCount可以表示成功發(fā)送一個數據包所需要重傳幀的次數,RTSFailureCount表示RTS的重傳次數,ACKFailureCount表示數據重傳的次數。

設節(jié)點A到節(jié)點B成功發(fā)送第k個數據包的重傳次數為

ETXAB(k)=RTSFailureCountAB(k)

+ACKFailureCountAB(k)

(2)

理想狀態(tài)是RTS和數據只經過一次傳送就可以達到目的地。所以可認為節(jié)點A到達節(jié)點B成功發(fā)送第k個數據包的期望傳輸效率為

(3)

從源節(jié)點s到目的節(jié)點d的整個路徑上的期望傳輸效率[8]為

(4)

當鏈路沒有斷裂且沒有擁塞時,數據重傳的次數少即ETX小。在路由選擇時,在使用ETX參量作為判據,優(yōu)先選擇ETX較小的路徑,可判別出當前鏈路質量和路徑擁塞情況。此外,當其他判據相同的時候,跳數較少意味著代價更低、端到端時延更小,同時跳數也會明顯影響吞吐量。而跳數越多的路徑,其ETX值越高,通過引入期望傳輸效率ETX作為判據,還可達到選擇路徑較短、時延較低的路徑的目的。

3.2 節(jié)點間的干擾衡量方法

802.11MAC中幀與幀之間的時間間隔稱為幀間間隔(Inter Frame Space,IFS)。MAC層定義了四種不同的IFS,分別為短幀間間隔(SIFS)、集中協(xié)調功能幀間間隔(PIFS)、分布式協(xié)調功能幀間間隔(DIFS)以及擴展幀間間隔(EIFS)。使用RTS和CTS機制交互時,信道接入的幀間間隔如圖1所示,幀間間隔表示了無線信道接入的優(yōu)先級。

圖1 使用RTS/CTS交互的信道接入方式

由上圖即可看出,網絡分配矢量NAV值可體現出節(jié)點周圍數據流量的變化情況,反映出其他節(jié)點對本節(jié)點的干擾影響。因此,通過合適的計算方式對NAV值進行處理可以得到該節(jié)點所受干擾的程度。

在MAC幀頭中的duration/ID字段中記錄了數據分組需要占用信道的時間值,以此為依據可更新節(jié)點的NAV值。網絡負載越重,NAV值就越大。每個節(jié)點周期性地從MAC層中獲取NAV信息,通過下式計算出一段時間內的累積平均NAVC值。

(5)

已有的研究證明[9]:在NAVC與節(jié)點可用帶寬BW及平均延時Delay之間有固定關系,且與用戶數及通信模式無關。下式中x為NAVC值,L為平均數據包長度。

(6)

BW(L,x)=(0.0024L+0.9)-(0.0036L+1.4)x

(7)

當NAVC小于0.20時,延時較小且不受用戶數影響;當NAVC大于0.65時,說明該節(jié)點已經過載,數據傳輸時延將大大增加,此時的時延約為NAVC達到閾值時的兩倍。

NAVC衡量了鄰節(jié)點之間的干擾,節(jié)點時延隨NAVC變化而變化。引入路徑中所有節(jié)點的平均時延和Delay_SUM為路徑判斷參數,路由發(fā)現的過程中,對于節(jié)點的干擾,Delay_SUM有三種處理方式: 1) 當節(jié)點的NAVC大于0.65時,該節(jié)點被標記為過載節(jié)點,在路由發(fā)現的過程中Delay值乘以2累加入Delay_SUM; 2) 當NAVC值在0.2與0.65之間時,僅增加Delay_SUM; 3)NAVC小于0.2時,該Delay值不計。

3.3 新路徑選擇判據構成

新路徑選擇判據包含三個部分: 1) 現有的空時判據; 2) 對擁塞及鏈路質量的衡量判據; 3) 對節(jié)點的干擾感知信息,如下所示:

α+β+γ=1

(8)

式中Cn為原有空時判據,期望傳輸效率ETXn傾向于選出鏈路質量更好的路徑,平均時延和Delay_SUM信息從MAC層網絡分配矢量NAV演算而來,反映了路徑上節(jié)點周邊環(huán)境對時延的影響。α,β及γ代表了各個因素在新判據中所占的權重,其和為1。經過反復的仿真實驗,系數取值暫定α=0.3,β=0.3,γ=0.4,可得到較好的路徑選擇效果。

該路徑選擇算法不僅反映了節(jié)點傳輸數據所占的信道資源量,而且還反映了鏈路的質量及擁塞情況,同時還考慮了其他節(jié)點的干擾情況。

4 實驗仿真及性能分析

使用NS2網絡仿真軟件對上述路徑選擇算法進行仿真實驗,實驗模擬環(huán)境設置如下[10]:在傳輸范圍1200km×1200km的方形區(qū)域內分布了50個節(jié)點,節(jié)點在該區(qū)域內可隨機移動,移動速度為50m/s,每個節(jié)點的傳輸半徑為250km;采用udp進行數據的傳輸,數據包大小設為512byte。MAC層隊列緩沖區(qū)是100,使用DropTail策略,無線信道采用TwoRayGround模型。通過模擬仿真,得到采用不同路徑選擇判據下,網絡吞吐量和分組時延的仿真結果,并用Matlab繪制出對比圖。圖2和圖3分別表示采用傳統(tǒng)空時判據和新路徑選擇判據下,端到端時延和網絡吞吐量的對比情況。

圖2 兩種路徑選擇判據下網絡端到端時延比對圖

從圖2可看出,當網絡中并發(fā)的業(yè)務流數量達到40的時候,數據包每一跳的平均時延開始急劇加大,但采用新路徑選擇算法,網絡時延較采用原空時判據時時延低。圖3則顯示采用新路徑選擇算法時,網絡吞吐量較采用空時判據時吞吐量高。當并發(fā)業(yè)務流數量達到60的時候,吞吐量達到最大,之后吞吐量不再增大反而減少,是因為新路徑選擇判據將更多的因素考慮進來,綜合各方面考慮優(yōu)選路徑,使得更多的數據流量傾向于鏈路質量較好、干擾和時延較小的鏈路上進行傳輸,單節(jié)點的吞吐量雖在降低,但提高了整個系統(tǒng)的吞吐量。

圖3 兩種路徑選擇判據下網絡平均吞吐量對比圖

5 結語

本文針對HWMP路由協(xié)議中默認空時路徑選擇判據的不足,綜合考慮多方面因素,從MAC層提取多個參數加入到新路徑選擇判據中,使新路由判據能更好地考慮其他節(jié)點的干擾及鏈路的質量,更加適應復雜多變的無線環(huán)境。并通過實驗證明,新路徑選擇判別算法更加有助于提高網絡吞吐量、降低時延,對優(yōu)化mesh無線自組網的路徑選擇,提高網絡的整體性有更加積極的作用。

[1] 方旭明,馬忠建.無線Mesh網絡跨層設計研究[J].數據通信,2005,4:15-18.

[2] Liu T, Liao W. On Routing in Multichannel Wireless Mesh Networks: Challenges and solutions[J]. IEEE Network,2008,22(1):13-18.

[3] De Couto D, Aguayo D, Bicket J, et al. Morris. High-throughput path metric for multi-hop wireless routing[C]//Wireless Networks,2005,11(4):419-434.

[4] Borges V C M, Curado M, Monteiro E. The impact of interference-aware routing metrics on video streaming in Wireless Mesh Networks[J]. Ad Hoc Networks,2011,9(4):652-661.

[5] 肖曉麗,張衛(wèi)平,康忠毅,等.HWMP協(xié)議的路徑選擇參數的研究與改進.[J].計算機工程與應用,2008,44(23):107-109.

[6] 馮文江,沈嘉皓,李琳.基于負載平衡的分層無線mesh網絡路由協(xié)議[J].計算機應用研究,2011,28(2):651-653.

[7] Guo C, Gip Z, Zhang Q, et al. Seamless and proactive end-to-end mobility solution for roaming across heterogeneout wireless networks[J]. IEEE Journal on Selected Areas of Communications,2005,22(5):834-848.

[8] Jain K, Padhye J, Padmanabhan V, et al. Impact of interference on multi- hop wireless network performance[C]//ACM Annual International Conference on Mobile Computing and Networking(MOBICOM),2003:66-80.

[9] 裴曉萍.HWMP路由協(xié)議的研究與仿真[D].西安:西安電子科技大學碩士研究生論文,2008:30-55.

[10] 游波,牟榮增,閻躍鵬.Linux內核中IEEE802.11s的設計與實現[J].計算機工程,2011,12(37):84-88.

Router Metric Based on HWMP Wireless Network

YU Zhi WANG Huijun XIAO Xuelu

(Wuhan Maritime Communications Research Institute, Wuhan 430250)

The router metric of hybrid wireless mesh protocol only considers the channel resource consumption, but pay no attention to other parameters of MAC layer for interference, link quality and congestion. So a new solution of router metric is proposed, which comprehensively considers various factors. The new metric will help increase the network throughput and reduce the end-to-end delay. Finaly, simulation results show that the new metric can optimize the path selection based on 802.11s and improve the overall performance of the network.

MAC layer, router metric, end-to-end delay, network throughput

2015年2月13日,

2015年3月24日

余智,女,碩士,高級工程師,研究方向:艦船通信網絡系統(tǒng)。汪慧君,女,碩士,工程師,研究方向:艦船通信網絡系統(tǒng)。肖雪露,女,碩士,工程師,研究方向:艦船通信網絡系統(tǒng)。

TM933

10.3969/j.issn1672-9730.2015.08.021