有效提高WLAN 吞吐量的數(shù)據(jù)幀發(fā)送策略

吳大鵬，武穆清，甄巖

(北京郵電大學(xué) 寬帶通信網(wǎng)實(shí)驗(yàn)室，北京 100876)

1 引言

IEEE802.11協(xié)議規(guī)定了分布式協(xié)調(diào)功能(DCF,distributed coordination function)為節(jié)點(diǎn)提供信道接入[1]，其采用CSMA/CA偵聽信道，當(dāng)數(shù)據(jù)幀發(fā)生碰撞后根據(jù)二進(jìn)制指數(shù)退避(BEB,binary exponential backoff)算法計(jì)算退避時間，進(jìn)而執(zhí)行重傳。此機(jī)制無法充分利用有限的無線資源[2～4]，其原因主要包含2個方面：首先，當(dāng)網(wǎng)絡(luò)負(fù)載逐漸增加的時候，共享無線媒介的各個節(jié)點(diǎn)處于飽和狀態(tài)，所發(fā)送的數(shù)據(jù)幀碰撞概率也隨之上升，雖然 BEB算法能夠通過競爭窗口加倍機(jī)制來降低碰撞概率，但是其調(diào)整速度較慢，在短時間段內(nèi)，數(shù)據(jù)幀碰撞的情況沒有明顯的緩解；此外，節(jié)點(diǎn)成功發(fā)送數(shù)據(jù)幀之后，BEB算法將競爭窗口恢復(fù)到最小值，由于沒考慮到當(dāng)前碰撞情況，快速縮減競爭窗口將會導(dǎo)致碰撞概率顯著增加。以上2個方面都將浪費(fèi)無線資源。

減少退避過程中空閑時隙數(shù)量或者降低數(shù)據(jù)幀碰撞次數(shù)都能夠提高網(wǎng)絡(luò)的總體性能，而通過減少退避空閑時隙數(shù)量來增加網(wǎng)絡(luò)資源利用率的方法又會增大數(shù)據(jù)幀的碰撞概率。諸多文獻(xiàn)根據(jù)上述分析提出了各種退避機(jī)制，以被動地解決數(shù)據(jù)幀碰撞問題，文獻(xiàn)[5]提出了一種分布式競爭控制機(jī)制，利用數(shù)據(jù)幀發(fā)送前的退避過程來估計(jì)網(wǎng)絡(luò)當(dāng)前的競爭狀態(tài)，并根據(jù)結(jié)果決定退避結(jié)束后是否發(fā)送該數(shù)據(jù)分組。該算法在每次數(shù)據(jù)幀發(fā)送成功后立刻將退避寄存器的窗口置為最小競爭窗口，當(dāng)網(wǎng)絡(luò)進(jìn)入高負(fù)載狀態(tài)后，每次發(fā)送數(shù)據(jù)幀均需經(jīng)歷多次碰撞，導(dǎo)致數(shù)據(jù)幀時延增大，網(wǎng)絡(luò)吞吐率下降。

文獻(xiàn)[6]提出了一種“慢退避”機(jī)制用于解決多個節(jié)點(diǎn)競爭信道過程中出現(xiàn)的多次碰撞問題，其主要思想是在節(jié)點(diǎn)成功發(fā)送數(shù)據(jù)幀后，并不將競爭窗口的數(shù)值立即恢復(fù)為最小值，而按照固定速度縮減當(dāng)前競爭窗口。但是該機(jī)制沒有考慮發(fā)送成功后網(wǎng)絡(luò)當(dāng)前的競爭狀態(tài)，進(jìn)而無法合理地選取下一幀的競爭窗口以避免盲目的發(fā)送動作，使得其無法適用于各種網(wǎng)絡(luò)環(huán)境。此外，文獻(xiàn)[7～10]均采用被動方式調(diào)整競爭窗口，但當(dāng)網(wǎng)絡(luò)擁塞程度較高的時候，節(jié)點(diǎn)始終處于回退狀態(tài)，這將導(dǎo)致業(yè)務(wù)產(chǎn)生的數(shù)據(jù)分組將會由于緩沖溢出而丟棄，另一方面，當(dāng)信道處于相對空閑狀態(tài)的時候，隊(duì)列中數(shù)據(jù)幀較少，無法高效地利用當(dāng)前空閑的網(wǎng)絡(luò)資源。解決這個問題的關(guān)鍵點(diǎn)在于根據(jù)不同的網(wǎng)絡(luò)狀態(tài)調(diào)整數(shù)據(jù)分組的發(fā)送速率。

區(qū)別于各種退避機(jī)制，Clausen提出了一種隨機(jī)發(fā)送時間機(jī)制[11]從網(wǎng)絡(luò)層主動地來解決該問題，節(jié)點(diǎn)對其負(fù)責(zé)發(fā)送的數(shù)據(jù)分組進(jìn)行分類，包括本地業(yè)務(wù)產(chǎn)生的數(shù)據(jù)分組和為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)分組，然后按照不同的方式隨機(jī)地改變各種數(shù)據(jù)分組發(fā)送到MAC隊(duì)列的時間，從而有效地降低了數(shù)據(jù)幀同時發(fā)送所導(dǎo)致的碰撞問題。但是與前面所介紹的回退機(jī)制類似，其固定調(diào)整范圍的方式無法適用于不同網(wǎng)絡(luò)負(fù)載情況。

為了更加合理地利用有限的網(wǎng)絡(luò)資源，本文提出了MAC層自適應(yīng)退避機(jī)制和網(wǎng)絡(luò)層數(shù)據(jù)分組發(fā)送時間調(diào)整的聯(lián)合優(yōu)化策略，該機(jī)制能夠有效地根據(jù)網(wǎng)絡(luò)當(dāng)前的碰撞情況調(diào)整數(shù)據(jù)分組發(fā)送速率，同時還能夠根據(jù)當(dāng)前回退階數(shù)調(diào)整競爭窗口，根據(jù)網(wǎng)絡(luò)當(dāng)前競爭狀態(tài)充分利用網(wǎng)絡(luò)資源。

2 網(wǎng)絡(luò)吞吐率分析

若當(dāng)前共享同一無線媒介的節(jié)點(diǎn)數(shù)量為 n，則至少有一個節(jié)點(diǎn)發(fā)送數(shù)據(jù)幀的概率為 Ptr，如式(1)所示，τ為一個時隙內(nèi)節(jié)點(diǎn)發(fā)送數(shù)據(jù)幀的概率。

節(jié)點(diǎn)成功完成數(shù)據(jù)幀傳輸?shù)母怕蕿?/p>

節(jié)點(diǎn)成功傳輸數(shù)據(jù)幀概率與節(jié)點(diǎn)發(fā)送概率之間的關(guān)系可以按照圖1中所示的各個曲線描述，在此選擇了6種節(jié)點(diǎn)密度進(jìn)行考慮。

圖1 節(jié)點(diǎn)成功傳輸概率與節(jié)點(diǎn)發(fā)送概率關(guān)系

由Ps的定義和圖1可知，碰撞發(fā)生過程中，較低的節(jié)點(diǎn)數(shù)據(jù)幀發(fā)送概率將會使得發(fā)送成功概率增加。

網(wǎng)絡(luò)的歸一化系統(tǒng)吞吐率S定義為單位時隙內(nèi)傳輸數(shù)據(jù)凈荷所用的時間與時隙長度的比例，可以按照下面的方式來描述：

其中，Ts和Tc分別為信道由于成功發(fā)送以及碰撞所導(dǎo)致的占用時間；E[P]表示平均數(shù)據(jù)幀長度，δ表示一個時隙所占用的時間，由于δ數(shù)值相對較小，則式(3)可以簡化為

對于式(4)來說，E[P]、Ts和 Tc都是固定值，因此，網(wǎng)絡(luò)歸一化吞吐率將隨Ps變化而單調(diào)變化。結(jié)合圖1和式(2)的結(jié)果可知，在碰撞頻繁的過程中，降低數(shù)據(jù)分組的發(fā)送概率將能夠有效地提升網(wǎng)絡(luò)吞吐率。

3 自適應(yīng)回退機(jī)制

在檢測到數(shù)據(jù)幀連續(xù)碰撞的時候，節(jié)點(diǎn)需要快速地增加競爭窗口以有效地避免該數(shù)據(jù)幀再次碰撞，其增加程度與連續(xù)碰撞次數(shù)明顯相關(guān)。因此，在數(shù)據(jù)幀出現(xiàn)碰撞的時候，按照式(5)調(diào)整競爭窗口，其中k表示節(jié)點(diǎn)當(dāng)前的回退階數(shù)，即該數(shù)據(jù)幀碰撞次數(shù)。

如前所述，與標(biāo)準(zhǔn)中規(guī)定的數(shù)據(jù)幀成功傳輸后的競爭窗口調(diào)整策略不同，若當(dāng)前數(shù)據(jù)幀在傳輸過程中連續(xù)出現(xiàn)碰撞，則表明共享相同無線媒介的節(jié)點(diǎn)數(shù)量較大，且多個節(jié)點(diǎn)都處于飽和狀態(tài)，此時，若各個成功發(fā)送數(shù)據(jù)幀節(jié)點(diǎn)都將競爭窗口恢復(fù)到最小，數(shù)據(jù)幀的碰撞情況無法得到明顯改善，因此，連續(xù)碰撞多次的數(shù)據(jù)幀成功傳輸之后，各個節(jié)點(diǎn)應(yīng)將競爭窗口維持在較大的范圍以有效地降低數(shù)據(jù)幀碰撞概率，調(diào)整方法如式(6)所示，其中m為最大重傳次數(shù)。

按照上述競爭窗口調(diào)整策略，節(jié)點(diǎn)競爭窗口的狀態(tài)轉(zhuǎn)移情況如圖2所示，由于基于碰撞感知的競爭窗口增加速度和節(jié)點(diǎn)成功傳輸數(shù)據(jù)分組后競爭窗口的縮減速度并不相同，因此，為了簡潔，只對主要狀態(tài)進(jìn)行描述。

4 動態(tài)發(fā)送時間調(diào)整策略

主動調(diào)節(jié)注入到隊(duì)列中的數(shù)據(jù)分組數(shù)量能夠從根本上提高無線資源利用率，將節(jié)點(diǎn)所需要傳輸?shù)臄?shù)據(jù)分組分為兩類：節(jié)點(diǎn)本地業(yè)務(wù)數(shù)據(jù)分組和為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)分組，2個類型的數(shù)據(jù)分組所對應(yīng)的發(fā)送時間偏移量均勻分布在區(qū)間[0,Jg]和[0,Jf]，其中Jg和Jf分別為用于調(diào)整本地業(yè)務(wù)數(shù)據(jù)分組和轉(zhuǎn)發(fā)數(shù)據(jù)分組發(fā)送時間的計(jì)時器，滿足

對于本地產(chǎn)生的數(shù)據(jù)分組來說，按照式(7)的方式調(diào)整其發(fā)送間隔，其中Jc為均勻分布在[0,Jg]的數(shù)值，Io為原始數(shù)據(jù)分組間隔。

節(jié)點(diǎn)可以獲知應(yīng)用層所產(chǎn)生的數(shù)據(jù)流情況，其中包括帶寬、數(shù)據(jù)分組長度、數(shù)據(jù)分組間隔等信息，因此，當(dāng)碰撞發(fā)生的時候，節(jié)點(diǎn)需要減小發(fā)送速率，而當(dāng)數(shù)據(jù)幀成功發(fā)送的時候，節(jié)點(diǎn)則需要加大發(fā)送速率以有效地使用無線資源，為了加快節(jié)點(diǎn)的調(diào)整速度，采用加性增加乘性減小(AIMD,additive increase multiplicative decrease)的方式，具體如式(8)和式(9)所示。

對于轉(zhuǎn)發(fā)數(shù)據(jù)分組來說，節(jié)點(diǎn)無法獲得其業(yè)務(wù)產(chǎn)生數(shù)據(jù)分組的速率，從而無法計(jì)算數(shù)據(jù)分組之間的間隔，因此，在數(shù)據(jù)分組轉(zhuǎn)發(fā)過程中對其接收到的數(shù)據(jù)分組采用延遲發(fā)送的方式，在區(qū)間[0,Jf]上均勻地選取具體的延遲時間數(shù)值。與發(fā)送本地?cái)?shù)據(jù)分組類似，當(dāng)轉(zhuǎn)發(fā)的數(shù)據(jù)分組出現(xiàn)碰撞的時候，節(jié)點(diǎn)需要降低其轉(zhuǎn)發(fā)速率，否則，增加轉(zhuǎn)發(fā)速率。類似地，采用了乘性增加加性減小(MIAD,multiplicative increase additive decrease)的方式來加速節(jié)點(diǎn)的調(diào)整速度，具體如式(10)和式(11)所示。

5 算法性能分析

文中所提出的基于競爭感知的聯(lián)合調(diào)整(CAA,contention aware adjusting)策略的偽代碼如下：

圖2 自適應(yīng)回退機(jī)制

對于IEEE 802.11標(biāo)準(zhǔn)中的二進(jìn)制指數(shù)退避算法來說，其復(fù)雜度分析過程如表1所示，假設(shè)平均重傳次數(shù)為mBEB。

表1 二進(jìn)制指數(shù)回退機(jī)制復(fù)雜度分析

由表1結(jié)果可知，IEEE802.11標(biāo)準(zhǔn)中所采用的二進(jìn)制指數(shù)退避算法的時間復(fù)雜度僅與平均重傳次數(shù)有關(guān)，即O(mBEB)。

對于文獻(xiàn)[6]中所提出的EIED算法來說，其時間復(fù)雜度分析過程如表2所示，假設(shè)平均重傳次數(shù)為mEIED。

表2 EIED機(jī)制復(fù)雜度分析

由上述分析過程可知，EIED算法的時間復(fù)雜度也僅與平均重傳次數(shù)有關(guān)，即O(mEIED)。

對于本文所提出的基于競爭感知的聯(lián)合調(diào)整策略來說，假設(shè)平均重傳次數(shù)為madaptive，最大重傳次數(shù)為m，復(fù)雜度分析過程如表3所示。

表3 CAA復(fù)雜度分析

為了衡量采用了碰撞感知技術(shù)之后，節(jié)點(diǎn)退避算法對網(wǎng)絡(luò)吞吐率的改進(jìn)情況，本文采用二維Markov模型分析穩(wěn)態(tài)條件下的吞吐率。W(t)、b(t)分別為描述節(jié)點(diǎn)競爭窗口和退避計(jì)數(shù)器數(shù)值的隨機(jī)過程，該二維Markov{W(t),b(t)}模型如圖3所示，其中p表示數(shù)據(jù)幀傳輸過程中的碰撞概率，L為最大重傳次數(shù)。

最大競爭窗口和最小競爭窗口分別為CWmin和CWmax，當(dāng)重傳次數(shù)達(dá)到某個數(shù)值的時候，競爭窗口將增加至CWmax而不再繼續(xù)增長，令該數(shù)值為m，則BEB退避策略可以按照式(12)進(jìn)行描述。

而所提出的碰撞感知的節(jié)點(diǎn)回退算法可以按照式(13)描述。

則圖3所示的狀態(tài)轉(zhuǎn)移關(guān)系可以用下面等式描述：

圖3 退避過程的二維Markov鏈

上述狀態(tài)轉(zhuǎn)移事件的意義如下：

1) 退避計(jì)數(shù)器減少；

2) 發(fā)送數(shù)據(jù)幀成功后，新數(shù)據(jù)幀的計(jì)數(shù)器需要從退避階段0開始；

3) 數(shù)據(jù)幀之間發(fā)生碰撞導(dǎo)致發(fā)送不成功，調(diào)整競爭窗口；

4) 碰撞次數(shù)達(dá)到最大值，無論數(shù)據(jù)幀成功發(fā)送還是再次碰撞，都直接開始下一個數(shù)據(jù)幀傳輸過程。

令bi,k表示穩(wěn)態(tài)分布{i,k}的概率，則有：

由Markov模型歸一化條件可知：

經(jīng)整理可得：

可以獲得系統(tǒng)初始狀態(tài)b0,0的表達(dá)式：

任意一個站點(diǎn)發(fā)送的概率τ可表示為

當(dāng)采用BEB算法的時候，則節(jié)點(diǎn)發(fā)送概率為

因此，兩者在相同碰撞概率情況下的節(jié)點(diǎn)發(fā)送數(shù)據(jù)幀概率如圖4所示。

可見，采用碰撞感知的回退機(jī)制之后，節(jié)點(diǎn)能夠有效地根據(jù)碰撞情況調(diào)整數(shù)據(jù)幀發(fā)送情況。碰撞發(fā)生比較頻繁的時候，采用碰撞感知的方法能夠有效地降低節(jié)點(diǎn)發(fā)送數(shù)據(jù)幀的概率，從而降低碰撞發(fā)生次數(shù)，達(dá)到增加系統(tǒng)吞吐率的目的。可見，所提出的 CAA機(jī)制能夠在不改變原有網(wǎng)絡(luò)物理結(jié)構(gòu)以及拓?fù)潢P(guān)系的情況下，通過更新終端驅(qū)動軟件，即可在維持原算法復(fù)雜度的情況下，實(shí)現(xiàn)網(wǎng)絡(luò)性能的改善。

圖4 碰撞概率與傳輸概率關(guān)系

6 網(wǎng)絡(luò)性能仿真

采用OPNET平臺對CAA機(jī)制進(jìn)行了計(jì)算機(jī)仿真，與文獻(xiàn)[9]類似，選取 Jmin為 1ms，Jmax為10ms，仿真場景為1 000m×1 000m，數(shù)據(jù)分組長度為1 024byte，仿真時間為300s，數(shù)據(jù)速率為11Mbit/s，其他參數(shù)使用標(biāo)準(zhǔn)中推薦的數(shù)值，文中以每秒數(shù)據(jù)分組數(shù)量為參數(shù)描述網(wǎng)絡(luò)負(fù)載。

如前所述，數(shù)據(jù)幀碰撞將導(dǎo)致網(wǎng)絡(luò)資源浪費(fèi)，因此，碰撞次數(shù)是衡量調(diào)整機(jī)制的重要指標(biāo)，如圖5所示，對于各種網(wǎng)絡(luò)負(fù)載情況來說，CAA機(jī)制都能夠有效地降低碰撞次數(shù)，并且性能改善程度隨負(fù)載上升而增加，總體來說，相比于BEB算法，CAA機(jī)制能夠使得整個網(wǎng)絡(luò)的數(shù)據(jù)幀碰撞次數(shù)降低27.5%，同時也明顯優(yōu)于EIED機(jī)制。

圖5 碰撞次數(shù)

網(wǎng)絡(luò)吞吐量是衡量資源利用率的有效指標(biāo)，采用CAA機(jī)制之后的網(wǎng)絡(luò)吞吐量如圖6所示，從整體來說，相比于BEB算法，網(wǎng)絡(luò)吞吐量平均提高30%以上，可見，采用CAA機(jī)制能夠更加合理地利用網(wǎng)絡(luò)資源；此外，結(jié)果表明，當(dāng)網(wǎng)絡(luò)達(dá)到飽和之后，增加注入到網(wǎng)絡(luò)的數(shù)據(jù)分組數(shù)量并不能提高網(wǎng)絡(luò)吞吐量，同時，CAA機(jī)制的性能也優(yōu)于EIED機(jī)制。

圖6 網(wǎng)絡(luò)吞吐量

CAA調(diào)整策略能夠降低數(shù)據(jù)幀碰撞次數(shù)，對特定數(shù)據(jù)幀來說，連續(xù)發(fā)生碰撞的概率小于標(biāo)準(zhǔn)中所使用的 BEB機(jī)制，因此，其成功傳輸?shù)母怕室簿透哂谑褂肂EB機(jī)制的情況。仿真結(jié)果如圖7所示，通過使用 CAA調(diào)整策略，網(wǎng)絡(luò)中分組投遞率上升接近13%。

圖7 分組投遞率

CAA機(jī)制采用主動和被動 2種方式調(diào)整數(shù)據(jù)分組發(fā)送過程中的相關(guān)參數(shù)，其在各種網(wǎng)絡(luò)負(fù)載以及節(jié)點(diǎn)密度情況下的數(shù)據(jù)分組平均時延如圖8所示，從結(jié)果中可知，當(dāng)網(wǎng)絡(luò)負(fù)載較小時，采用CAA機(jī)制對數(shù)據(jù)分組時延改善程度并不明顯，但是當(dāng)網(wǎng)絡(luò)負(fù)載逐漸增加的時候，相比于EIED機(jī)制和BEB機(jī)制來說，采用CAA機(jī)制能夠獲得較小的平均時延。

圖8 數(shù)據(jù)分組平均時延

7 結(jié)束語

以被動方式調(diào)整競爭窗口變化情況無法從根本上改善當(dāng)前網(wǎng)絡(luò)中資源競爭情況，文中提出了一種結(jié)合主動和被動的數(shù)據(jù)分組傳輸過程調(diào)整機(jī)制，節(jié)點(diǎn)根據(jù)數(shù)據(jù)幀碰撞情況被動地調(diào)整競爭窗口增加和縮減的速度，同時采用主動的方式，動態(tài)地控制進(jìn)入到節(jié)點(diǎn)隊(duì)列中的數(shù)據(jù)分組速率。結(jié)果表明，該聯(lián)合調(diào)整策略能夠有效地提高網(wǎng)絡(luò)吞吐量，為業(yè)務(wù)提供更好的服務(wù)質(zhì)量保障。

[1] IEEE Std 802.11.Part 11: Wireless LAN Medium Access Control(MAC) and Physical Layer(PHY) Specifications[S].IEEE LAN/MAN Standards Committee,New York,USA,IEEE Press,2007.

[2] GUANG L,ASSI C M.BENSLIMANE A.Enhancing IEEE 802.11 random backoff in selfish environments[J].IEEE Transactions on Vehicular Technology,2008,57(3):1806-1822.

[3] 黎寧,史誠光.一種802.11DCF性能分析的簡單方法[J].電子科技大學(xué)學(xué)報(bào),2006,35(3): 339-342.LI N,SHI C G.An easy way for 802.11 DCF performance analysis[J].Journal of University of Electronic Science and Technology of China,2006,35(3): 339-342.

[4] SAKURAI T,VU H L.MAC access delay of IEEE 802.11 DCF[J].IEEE Transactions on Wireless Communications,2007,6(5): 1702- 1710.

[5] BONONI L,CONTI M.Runtime optimization of IEEE 802.11 wireless LANs performance [J].IEEE Transactions on Parallel and Distributed Systems,2004 ,15(1):66-80.

[6] SONG N,KWAK B,SONG J,et al.Enhancement of IEEE 802.11 distributed coordination function with exponential increase exponential decrease backoff algorithm[A].Proceedings of Vehicular Technology Conference[C].2003.2775-2778.

[7] XIAO Y,LI F H,WU K.On optimizing backoff counter reservation and classifying stations for the IEEE 802.11 distributed wireless LANs[J].IEEE Transactions on Parallel and Distributed Systems,2006,17(7):713 – 722.

[8] 朱穎,夏海輪,武穆清.一種最小競爭窗口自適應(yīng)調(diào)整的802.11退避算法[J].電子與信息學(xué)報(bào),2008,30(4): 961-965.ZHU Y,XIA H L,WU M Q.A self-adaptive minimum contention window adjusting backoff algorithm in IEEE 802.11 DCF[J].Journal of Electronics and Information Technology,2008,30(4): 961-965.

[9] 王朝翔,苗建松,丁煒.模糊邏輯控制的 MAC協(xié)議[J].北京郵電大學(xué)學(xué)報(bào),2007,30(6): 131-134.WANG Z X,MIAO J S,DING W.A fuzzy logic MAC protocol[J].Journal of Beijing University of Posts and Telecommunications,2007,30(6): 131-134.

[10] IBRAHIM M,ALOUF S.Design and analysis of an adaptive backoff algorithm for IEEE 802.11 DCF mechanism[J].Lecture Notes in Computer Science,2006,3976:184-196.

[11] CLAUSEN T,DEARLOVE C.Jitter considerations in mobile ad hoc networks [EB/OL].http://www.ietf.org/rfc/rfc5148.txt.2008-07-10.