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

吳大鵬，武穆清，甄巖

(北京郵電大學 寬帶通信網(wǎng)實驗室，北京 100876)

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 自適應回退機制

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

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

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

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

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

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

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

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

5 算法性能分析

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

圖2 自適應回退機制

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

表1 二進制指數(shù)回退機制復雜度分析

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

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

表2 EIED機制復雜度分析

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

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

表3 CAA復雜度分析

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

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

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

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

圖3 退避過程的二維Markov鏈

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

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

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

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

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

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

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

經(jīng)整理可得：

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

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

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

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

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

圖4 碰撞概率與傳輸概率關系

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

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

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

圖5 碰撞次數(shù)

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

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

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

圖7 分組投遞率

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

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

7 結束語

以被動方式調(diào)整競爭窗口變化情況無法從根本上改善當前網(wǎng)絡中資源競爭情況，文中提出了一種結合主動和被動的數(shù)據(jù)分組傳輸過程調(diào)整機制，節(jié)點根據(jù)數(shù)據(jù)幀碰撞情況被動地調(diào)整競爭窗口增加和縮減的速度，同時采用主動的方式，動態(tài)地控制進入到節(jié)點隊列中的數(shù)據(jù)分組速率。結果表明，該聯(lián)合調(diào)整策略能夠有效地提高網(wǎng)絡吞吐量，為業(yè)務提供更好的服務質(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].電子科技大學學報,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] 朱穎,夏海輪,武穆清.一種最小競爭窗口自適應調(diào)整的802.11退避算法[J].電子與信息學報,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].北京郵電大學學報,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.