支持QoS的無線局域網自適應MAC協(xié)議算法*

鄧皓文,江 虹,李 維

(西南科技大學 信息工程學院,四川 綿陽 621010)

0 引 言

隨著網絡服務種類增多,不同的服務具有不同的服務質量(quality of service,QoS)需求[1,2]。為此,IEEE制定了802.11e協(xié)議,其中的增強分布式接入(enhanced distributed channel access,EDCA)機制為數據流提供了QoS區(qū)分。但其參數不能隨負載自適應變化,尤其是固定的退避機制在競爭站點較多的情況下會明顯增加碰撞幾率[3],使網絡性能顯著下降。國內外學者對如何改進EDCA的退避方式進行了大量研究,主要分為兩大類：第一類是通過飽和吞吐量模型優(yōu)化飽和吞吐量。文獻[4～6]均是通過文獻[7,8]中的飽和吞吐量模型來計算最優(yōu)競爭窗口,使飽和狀態(tài)下吞吐量接近最優(yōu)。但是,以上方法的前提均是所有站點的業(yè)務都處于飽和狀態(tài),且需要準確估計競爭站點數目,求解復雜方程組,算法復雜度較高；第二類是通過網絡負載因子調節(jié)競爭窗口來優(yōu)化網絡性能。文獻[9]通過估計站點數目來動態(tài)調整競爭窗口的值。文獻[10,11]通過監(jiān)測時隙周期中的碰撞概率來自適應調整競爭窗口大小。文獻[12]提出了GDCF算法,能有效降低網絡碰撞,且額外開銷較少,但不具有自適應性。

為了使EDCA機制能夠適應網絡負載變化,并針對目前大多數改進算法開銷較大,不適用于無線傳感器網絡等場景,本文在GDCF基礎之上提出了一種自適應退避算法。改進算法能夠解決GDCF算法競爭窗口減小過慢的問題,進而降低網絡時延,為高優(yōu)先級業(yè)務提供更好的QoS保障。

1 EDCA機制簡介

802.11e定義了8種流量種類(traffic category,TC),對應了4種業(yè)務接入種類(access category,AC),分別是語音業(yè)務(AC_VO)、視頻業(yè)務(AC_VI)、盡力而為業(yè)務(AC_BE)、背景業(yè)務(AC_BK)。每個站點內部有4個AC隊列,分別接收來自不同優(yōu)先級業(yè)務的數據,每個AC隊列形成“虛擬”站點,獨立進行退避過程,有各自的仲裁幀間間隔(arbitration inter-frame space,AIFS),最小競爭窗口CWmin,最大競爭窗口CWmax和傳輸機會(transmission opportunity,TXOP)。高優(yōu)先級業(yè)務有著較小的AIFS,CWmin,CWmax和較大的TXOP,因此高優(yōu)先級業(yè)務有更大的幾率競爭到信道,進而實現業(yè)務區(qū)分。EDCA機制的退避過程使用二進制指數退避(binary exponential backoff,BEB)算法,記b為退避階段,第一次嘗試發(fā)送MAC幀時,b=0,若發(fā)生碰撞,退避階段加一,CW=2b*CWmin,當CW=CWmax時,競爭窗口不再增加。

2 自適應退避算法

2.1 算法思想

負載較重時,BEB算法成功發(fā)送數據后立即將競爭窗口重置到最小值,導致網絡碰撞進一步加劇。文獻[12]提出的GDCF算法,能夠有效降低碰撞,基于GDCF算法,本文提出的自適應退避算法退避過程如圖1(以6個退避階段為例)。

圖1 自適應退避過程

在更新周期內,各優(yōu)先級隊列i記錄每個數據包到達的最大退避階段,得到每個更新周期內的平均最大退避階段Bi。重置競爭窗口時,如果當前的退避階段小于等于Bi,采用GDCF的窗口減小方式,如果當前的退避階段大于Bi,將競爭窗口重置為2BiCWmin,相比GDCF有更快的競爭窗口遞減速度。

2.2 改進算法具體描述

記Tupdate為數據包成功發(fā)送或者達到最大重傳次數被丟棄時的時刻。定義更新周期為k個Tupdate時刻,bi為站點優(yōu)先級業(yè)務i當前所處退避階段,Si為累加變量(初值為0),Bi為優(yōu)先級i的平均最大退避階段,CW[i]為第i類業(yè)務當前的退避窗口,c為常數。k和c的取值將在仿真分析部分介紹。改進算法具體描述如下：

1)Si更新:當業(yè)務i處于Tupdate,根據當前的退避階段,對Si進行更新,Si=Si+bi。

2)重置窗口:若bi,j

3)發(fā)生碰撞:CW[i]=2×CW[i],達到CW[i]max不再增加。

4)達到更新周期:計算出Bi=round(Si/k),并且令Si=0。

3 理論分析

3.1 二維Markov鏈模型

BEB算法的性能可由Bianchi提出的二維Markov鏈進行分析。為了簡單說明問題,這里只考慮站點只有一個優(yōu)先級業(yè)務i的情況。定義碰撞概率為pc,最大退避階段為m,最大重傳次數為l,Wi,0為最小競爭窗口,Wi,m為最大競爭窗口,可建立如圖 2所示的二維Markov鏈。

圖2 退避過程二維Markov鏈

(1)

(2)

由Markov鏈穩(wěn)態(tài)概率之和為1,有

(3)

文獻[8]只考慮m=l的情況,這里考慮m有可能小于l的情況,由式(1)～式(3)可得

(4)

業(yè)務i發(fā)送數據的概率τ可以表示為

(5)

設共有n個站點,碰撞概率可表示為

pc=1-(1-τ)n-1

(6)

網絡中有站點發(fā)送數據的概率可表示為

ptr=1-(1-τ)n

(7)

網絡中有站點成功發(fā)送數據的概率為[7]

(8)

定義P為數據包長度,E[P]為數據包長度均值。Ts為成功發(fā)送數據整個過程所用時間,Tc為碰撞過程占用的時間,Tc和Ts的計算方法可參見文獻[7]。σ為一個時隙的時間,整個網絡歸一化吞吐量S定義為[7]

(9)

通過數值解法可以求解式(4)～式(6)構成的非線性方程組,得到不同n值下的pc和τ,進而通過式(9)計算出歸一化吞吐量的值,詳細計算參數可參見文獻[7]。

3.2 改進算法分析

當bi≤Bi時,減小競爭窗口,碰撞幾率較高,此時采取GDCF的窗口遞減方式。當bi>Bi時,重置窗口時令CW[i]=CW[i]min×2Bi,在CW[i]max不變的情況下,相當于增大了CW[i]min的值并減小了m的值。利用式(9)可以求解出不同最小競爭窗口W下的歸一化吞吐量(Basic模式,最大競爭窗口為256),如圖 3。

圖3 不同最小競爭窗口下歸一化吞吐量

可以看到,W為8時在站點數少的情況下吞吐量最高,但隨著站點輸增多,吞吐量會明顯下降,此時W取較大值(32和128)能夠顯著提升網絡吞吐量。這表明,站點數較多的情況下,增大W會減小碰撞概率,提高網絡吞吐量；在站點數較少的情況下,較大的W會導致空閑時隙數增多,反而會降低吞吐量。因此,合理改變W的值能使網絡具有自適應性。改進算法通過周期性更新Bi的值,重置競爭窗口時將退避階段重置到Bi,相當于將最小競爭窗口動態(tài)調整到多個數據包發(fā)送成功時的平均競爭窗口,進而減小碰撞幾率,提升網絡性能。

4 仿真分析

4.1 仿真模型

使用NS—2.35來進行仿真,仿真場景大小為250 m×250 m,仿真參數見表1。網絡中有多個靜止站點和一個AP,站點在AP覆蓋范圍內隨機均勻布置,站點僅與AP進行通信,形成星型拓撲結構,無隱藏站點,網絡工作在Basic模式下。每個站點傳輸3種業(yè)務類型,分別是高優(yōu)先級業(yè)務(AC[0])、中優(yōu)先級業(yè)務(AC[1])和盡力而為業(yè)務(AC[2]),傳輸層采用UDP協(xié)議。每次仿真運行120s,結果取10次平均值。

表1 仿真用到的參數

4.2 仿真結果分析

首先,要選取合理的k值和c值。在網絡飽和的情況下(站點數為30),選取不同k值進行實驗,當k值取30時,飽和吞吐量接近最大,k大于30時,吞吐量不會有明顯增加,因此,本文選擇k=30作為統(tǒng)計周期。參考文獻[12]建議,高、中、低優(yōu)先級業(yè)務c值分別為2,3,4。

AC[0]的吞吐量變化如圖 4(a)。原始EDCA機制在站點數大于20時AC[0]逐漸進入飽和狀態(tài)；本文算法和GDCF能夠降低網絡碰撞,都能明顯提升AC[0]吞吐量,GDCF在站點數為36時接近飽和,而本文算法在站點數為40時才接近飽和,這是由于GDCF競爭窗口減小過慢,AC[0]發(fā)送數據概率減小,抵消了減少碰撞帶來的增益。在站點數為40的情況下,本文算法相對于EDCA和GDCF吞吐量分別提高了43 %和6 %。

圖4(b)和圖4(c)顯示了AC[1]和AC[2]吞吐量隨站點數目的變化。本文算法和GDCF算法AC[1]和AC[2]業(yè)務吞吐量明顯高于EDCA。本文算法AC[1]業(yè)務吞吐量在站點數小于30的情況下明顯高于GDCF,在站點數大于30情況下略低于GDCF；本文算法AC[2]的吞吐量較EDCA有明顯提高,但低于GDCF。

圖4 3種業(yè)務吞吐量隨站點數目的變化

綜合分析三種優(yōu)先級業(yè)務的吞吐量,可以看到GDCF高優(yōu)先級的業(yè)務的退避窗口減小過慢,使得低優(yōu)先級業(yè)務有更高的幾率競爭到信道。出現了本文算法AC[2]吞吐量不如GDCF的情況和站點數為30的時候AC[1]的吞吐量逐漸小于GDCF的情況,但本文算法AC[0]吞吐量始終高于GDCF算法。因此,本文的自適應算法相比于GDCF更能保證高優(yōu)先級業(yè)務QoS。

AC[0]為時延敏感型業(yè)務,圖5顯示了不同站點數目下各種算法的時延。EDCA機制在站點數較多時,由于碰撞幾率最高,時延最大。GDCF由于競爭窗口減小過慢,在站點數小于12時延最大；站點數大于12時GDCF能夠有效避免碰撞,時延比EDCA??；站點數大于36時連續(xù)成功發(fā)送數據的概率變低,GDCF會將競爭窗口維持在較大值,此時低優(yōu)先級接入信道的幾率變大,導致退避時間過長,時延最大；本文算法平均時延最小,這是由于自適應算法既能夠有效避免網絡碰撞,且相比于GDCF能夠避免競爭窗口下降過慢導致額外的退避時延。

圖5 AC[0]平均時延

5 結 論

本文提出了一種支持區(qū)分服務的無線網絡改進MAC協(xié)議,通過對EDCA機制中的退避算法進行改進,使得該機制具有自適應性。改進算法提高EDCA機制性能,在網絡負載較高的情況下,降低了高優(yōu)先級業(yè)務的時延,大幅提高了各優(yōu)先級業(yè)務的吞吐量；改進算法相比于GDCF算法有更好的QoS區(qū)分和更低的網絡時延。該算法額外開銷較少,在需要電池供電的無線局域網以及無線傳感器網絡中具有一定的應用價值。