鄧皓文,江 虹,李 維

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

0 引 言

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

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

1 EDCA機制簡介

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

2 自適應(yīng)退避算法

2.1 算法思想

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

圖1 自適應(yīng)退避過程

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

2.2 改進算法具體描述

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

1)Si更新:當(dāng)業(yè)務(wù)i處于Tupdate,根據(jù)當(dāng)前的退避階段,對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è)務(wù)i的情況。定義碰撞概率為pc,最大退避階段為m,最大重傳次數(shù)為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è)務(wù)i發(fā)送數(shù)據(jù)的概率τ可以表示為

(5)

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

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

(6)

網(wǎng)絡(luò)中有站點發(fā)送數(shù)據(jù)的概率可表示為

ptr=1-(1-τ)n

(7)

網(wǎng)絡(luò)中有站點成功發(fā)送數(shù)據(jù)的概率為[7]

(8)

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

(9)

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

3.2 改進算法分析

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

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

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

4 仿真分析

4.1 仿真模型

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

表1 仿真用到的參數(shù)

4.2 仿真結(jié)果分析

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

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

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

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

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

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

圖5 AC[0]平均時延

5 結(jié) 論

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