有效提高WLAN 吞吐量的數據幀發送策略

吳大鵬，武穆清，甄巖

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

1 引言

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

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

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

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

為了更加合理地利用有限的網絡資源，本文提出了MAC層自適應退避機制和網絡層數據分組發送時間調整的聯合優化策略，該機制能夠有效地根據網絡當前的碰撞情況調整數據分組發送速率，同時還能夠根據當前回退階數調整競爭窗口，根據網絡當前競爭狀態充分利用網絡資源。

2 網絡吞吐率分析

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

節點成功完成數據幀傳輸的概率為

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

圖1 節點成功傳輸概率與節點發送概率關系

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

網絡的歸一化系統吞吐率S定義為單位時隙內傳輸數據凈荷所用的時間與時隙長度的比例，可以按照下面的方式來描述：

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

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

3 自適應回退機制

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

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

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

4 動態發送時間調整策略

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

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

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

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

5 算法性能分析

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

圖2 自適應回退機制

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

表1 二進制指數回退機制復雜度分析

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

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

表2 EIED機制復雜度分析

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

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

表3 CAA復雜度分析

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

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

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

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

圖3 退避過程的二維Markov鏈

上述狀態轉移事件的意義如下：

1) 退避計數器減少；

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

3) 數據幀之間發生碰撞導致發送不成功，調整競爭窗口；

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

令bi,k表示穩態分布{i,k}的概率，則有：

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

經整理可得：

可以獲得系統初始狀態b0,0的表達式：

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

當采用BEB算法的時候，則節點發送概率為

因此，兩者在相同碰撞概率情況下的節點發送數據幀概率如圖4所示。

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

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

6 網絡性能仿真

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

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

圖5 碰撞次數

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

圖6 網絡吞吐量

CAA調整策略能夠降低數據幀碰撞次數，對特定數據幀來說，連續發生碰撞的概率小于標準中所使用的 BEB機制，因此，其成功傳輸的概率也就高于使用BEB機制的情況。仿真結果如圖7所示，通過使用 CAA調整策略，網絡中分組投遞率上升接近13%。

圖7 分組投遞率

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

圖8 數據分組平均時延

7 結束語

以被動方式調整競爭窗口變化情況無法從根本上改善當前網絡中資源競爭情況，文中提出了一種結合主動和被動的數據分組傳輸過程調整機制，節點根據數據幀碰撞情況被動地調整競爭窗口增加和縮減的速度，同時采用主動的方式，動態地控制進入到節點隊列中的數據分組速率。結果表明，該聯合調整策略能夠有效地提高網絡吞吐量，為業務提供更好的服務質量保障。

[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] 朱穎,夏海輪,武穆清.一種最小競爭窗口自適應調整的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協議[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.