基于HWMP協(xié)議的無(wú)線網(wǎng)絡(luò)路由判據(jù)研究*

余 智 汪慧君 肖雪露

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

?

基于HWMP協(xié)議的無(wú)線網(wǎng)絡(luò)路由判據(jù)研究*

余 智 汪慧君 肖雪露

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

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

MAC層; 路由判據(jù); 端到端時(shí)延; 吞吐量

Class Number TM933

1 引言

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

在網(wǎng)絡(luò)研究領(lǐng)域,路由協(xié)議一直是研究的重點(diǎn)。IEEE802.11標(biāo)準(zhǔn)工作組針對(duì)無(wú)線網(wǎng)格網(wǎng)制定了802.11s標(biāo)準(zhǔn),該標(biāo)準(zhǔn)中使用混合無(wú)線網(wǎng)格協(xié)議(Hybrid Wireless Mesh Protocol,HWMP)作為其默認(rèn)的路徑選擇協(xié)議。HWMP協(xié)議是一種混合式路徑選擇協(xié)議[2],同時(shí)結(jié)合了反應(yīng)式和先驗(yàn)式路由協(xié)議的特點(diǎn)。該協(xié)議工作在MAC層,和傳統(tǒng)的三層網(wǎng)絡(luò)協(xié)議不同,HWMP協(xié)議中通過(guò)MAC地址進(jìn)行路徑尋址、數(shù)據(jù)轉(zhuǎn)發(fā)[3]。

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

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

為了確保可擴(kuò)展框架中不同路徑選擇協(xié)議間基本的互操作,IEEE802.11s標(biāo)準(zhǔn)定義了基于空時(shí)(airtime)消耗的默認(rèn)的鏈路metric來(lái)度量無(wú)線選擇路徑[4]。當(dāng)幀經(jīng)過(guò)某鏈路時(shí),采用下式計(jì)算空時(shí)鏈路metric值Ca,來(lái)度量該鏈路傳輸該幀所消耗的信道資源總量。路徑metric是路徑中所有鏈路metric的總和[5～6]。

(1)

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

表1 空時(shí)消耗判據(jù)參數(shù)典型取值

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

3 新路徑選擇判別算法

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

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

新路由判據(jù)在現(xiàn)有空時(shí)判據(jù)基礎(chǔ)上,至少應(yīng)包含: 1) 對(duì)擁塞及鏈路質(zhì)量的衡量判別, 2) 對(duì)節(jié)點(diǎn)干擾信息的感知。

3.1 鏈路質(zhì)量和路徑擁塞判別方法

鏈路質(zhì)量和路徑擁塞情況可以通過(guò)引入期望傳輸效率來(lái)表示。

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

設(shè)節(jié)點(diǎn)A到節(jié)點(diǎn)B成功發(fā)送第k個(gè)數(shù)據(jù)包的重傳次數(shù)為

ETXAB(k)=RTSFailureCountAB(k)

+ACKFailureCountAB(k)

(2)

理想狀態(tài)是RTS和數(shù)據(jù)只經(jīng)過(guò)一次傳送就可以達(dá)到目的地。所以可認(rèn)為節(jié)點(diǎn)A到達(dá)節(jié)點(diǎn)B成功發(fā)送第k個(gè)數(shù)據(jù)包的期望傳輸效率為

(3)

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

(4)

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

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

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

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

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

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

(5)

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

(6)

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

(7)

當(dāng)NAVC小于0.20時(shí),延時(shí)較小且不受用戶數(shù)影響;當(dāng)NAVC大于0.65時(shí),說(shuō)明該節(jié)點(diǎn)已經(jīng)過(guò)載,數(shù)據(jù)傳輸時(shí)延將大大增加,此時(shí)的時(shí)延約為NAVC達(dá)到閾值時(shí)的兩倍。

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

3.3 新路徑選擇判據(jù)構(gòu)成

新路徑選擇判據(jù)包含三個(gè)部分: 1) 現(xiàn)有的空時(shí)判據(jù); 2) 對(duì)擁塞及鏈路質(zhì)量的衡量判據(jù); 3) 對(duì)節(jié)點(diǎn)的干擾感知信息,如下所示:

α+β+γ=1

(8)

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

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

4 實(shí)驗(yàn)仿真及性能分析

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

圖2 兩種路徑選擇判據(jù)下網(wǎng)絡(luò)端到端時(shí)延比對(duì)圖

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

圖3 兩種路徑選擇判據(jù)下網(wǎng)絡(luò)平均吞吐量對(duì)比圖

5 結(jié)語(yǔ)

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

[1] 方旭明,馬忠建.無(wú)線Mesh網(wǎng)絡(luò)跨層設(shè)計(jì)研究[J].數(shù)據(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é)議的路徑選擇參數(shù)的研究與改進(jìn).[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(23):107-109.

[6] 馮文江,沈嘉皓,李琳.基于負(fù)載平衡的分層無(wú)線mesh網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)應(yīng)用研究,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].西安:西安電子科技大學(xué)碩士研究生論文,2008:30-55.

[10] 游波,牟榮增,閻躍鵬.Linux內(nèi)核中IEEE802.11s的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(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日

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

TM933

10.3969/j.issn1672-9730.2015.08.021