一種有效降低沖突概率的CSMA/CA退避算法

萬小博，譚國平，馬賽賽

（河海大學 計算機與信息學院，江蘇 南京 210000）

802.11 是IEEE制定的一個無線局域網(wǎng)標準[1]，主要用于解決辦公室局域網(wǎng)和校園網(wǎng)中用戶終端的無線接入，該協(xié)議有802.11a、802.11b、802.11g等版本。

由于WLAN工作在ISM頻段，此頻段是不受保護的開放頻段，隨著時間的推移，會有越來越多的終端要求同時接入WLAN，而且，也會有其他系統(tǒng)的終端會工作在這個頻段上，如LTE D2D通信系統(tǒng)[2]、Adhoc移動自組網(wǎng)通信系統(tǒng)[3]等。如此多的終端、各種不同的系統(tǒng)同時通信，競爭有限的無線資源，勢必會引起嚴重的系統(tǒng)內(nèi)部與系統(tǒng)間沖突。

CSMA/CA作為一個成熟運用的機制，人們對它進行了很多方面的研究，有基本原理方面的[4],也有性能分析方面的[5-6]。并且也提出了許多的優(yōu)化方案來提高系統(tǒng)性能，如根據(jù)終端流量動態(tài)調(diào)整競爭窗口[7]、基于時槽機制的改進算法、基于優(yōu)先級的改進，同時也有一些從硬件方面提出的改進,這些方法都很好的改善了系統(tǒng)的性能。

與以前研究不同，本文提出了一種新型的改進CAMA/CA機制的退避算法。經(jīng)過仿真分析證明，此方法能夠有效的降低系統(tǒng)沖突，提高系統(tǒng)容量。

1 IEEE 802.11 MAC 協(xié)議

在無線局域網(wǎng)中，同時進行通信的終端設備很多，會存在資源競爭的問題。這個問題在IEEE 802.11MAC協(xié)議里通過帶沖突避免的載波偵聽多路訪問機制(CSMA/CA)得到了解決，其基本流程如圖1所示。

圖1 CSMA/CA流程示意圖Fig. 1 CSMA/CA flow diagram

一個終端設備在傳輸數(shù)據(jù)之前，它需要首先偵聽信道，如果信道空閑且經(jīng)過一個分布式協(xié)調(diào)幀間間隔（DIFS）后，信道仍然空閑，則該站點開始傳輸數(shù)據(jù)。如果偵聽到信道忙，那么站點就一直偵聽信道，直到空閑且持續(xù)空閑DIFS時間后，開始執(zhí)行一個二進制的指數(shù)退避機制，通常稱為競爭窗口。然后偵聽信道，如果信道空閑，則退避計數(shù)器減1，直到減為0時，開始傳輸數(shù)據(jù)；如果偵聽到信道忙，那么退避計數(shù)器就掛起，直到信道空閑且持續(xù)DIFS時間長度后，計數(shù)器重新開始遞減。

2 避免沖突的改進的CAMA/CA機制

2.1 原協(xié)議存在的問題

當ISM頻段上引入更多的設備和其他的系統(tǒng)后，其他系統(tǒng)設備和WLAN設備共享無線局域網(wǎng)信道的一個可行方法就是，所有設備均使用802.11的MAC機制去競爭信道。該方法雖然簡單，但是在站點多，業(yè)務量大的情況下，較多的幀間間隔和較大的競爭窗口容易導致整體效率低下，另外這種直接的方法也很難保證兩個系統(tǒng)間的公平性和頻譜資源利用率最大化。

當眾多的終端進行通信時，在隨機退避時間的選擇上，選擇相同退避時間的終端的概率會增加，當幾個終端的退避時間同時歸零時，它們會同時接入信道，進而導致通信失敗。所以，為了避免通信的失敗，應盡量讓不同的設備選擇不同的退避時間。

圖2 傳統(tǒng)的CSMA/CA退避機制Fig. 2 Traditional mechanism of CSMA/CA

2.2 改進方法

如圖2所示，在一個用戶完成通信后，WLAN用戶1、2、3同時檢測到信道空閑，并進入退避階段。為表述的更加清楚，假設這3個用戶通過傳統(tǒng)的CSMA/CA機制隨機選取一個相同的值作為退避時間。此時，這3個用戶將不可避免的發(fā)生競爭沖突。為了避免沖突，可適當改進CSMA/CA機制。

保持WLAN用戶2的退避時間不變，而用戶1和3通過退避時間偏移量來調(diào)整退避時間。假設在WLAN用戶1從（0,CW-1）隨機選取一個值后，將減Tslot-t長度的時間作為該用戶當前的退避時間，而WLAN用戶2從（0,CW-1）隨機選取一個同樣的值后，將加t(0＜t＜Tslot)長度的時間作為該用戶當前的退避時間，如圖3所示。

圖3 改進的CSMA/CA退避機制Fig. 3 Improved mechanism of CSMA/CA

在T時刻，WLAN用戶1的退避計數(shù)器減為零，同時檢測到信道空閑，則WLAN用戶1將發(fā)送RTS幀占用信道實現(xiàn)通信。經(jīng)過一段很短的傳輸時延后，WLAN用戶2與3將收到用戶1發(fā)送的RTS幀，同時將信道狀態(tài)信息標志為忙，并掛起退避計數(shù)器直到WLAN用戶1完成傳輸。在WLAN用戶1完成信息傳輸并等待一個DIFS時間后，WLAN用戶2和3重新開始退避計數(shù)，此時WLAN用戶2的退避時間比WLAN用戶3的退避時間短，所以WLAN用戶2將優(yōu)先接入信道完成通信。

通過這樣一個對退避時間的簡單處理，發(fā)生在這3個用戶之間的競爭沖突已完全被避免。除此之外，由于選取的退避時間偏移量t滿足0＜t＜Tslot，所以此方法只有在多個WLAN用戶選取了相同退避時間的情況下起作用。換句話說，當WLAN用戶選取退避時間不同時，此方法不會對其競爭過程產(chǎn)生任何影響。因此，除了少量的信令開銷外，不會對原有系統(tǒng)帶來任何不利的影響。

2.3 時間偏移量t的選取

首先，將通信終端分為多個小組，并給一個小組分配一個唯一且固定的退避時間偏移量ti。不失一般性，假設將通信終端分為L個小組，每個小組分配一個退避時間偏移量ti(1≤i≤L)，同時確保每個退避時間偏移量是唯一的，即ti≠ tj（? i, j∈ [1,L]&i≠ j）。

在每一組中用戶都可以隨機選擇推遲一個時間偏移量t或者提前一個時間偏移量t’。為了保證各個用戶組之間不會發(fā)生碰撞，需確保 t+t’=Tslot(t≠ 0&t’≠ 0)。

其中，（t+t’=Tslot(t≠ 0&t’≠ 0)是十分必要的。假設用戶平均分為3組，如圖4所示，并且定義退避的起始時間為t0，每一組的退避時間偏移量分別設為1/4Tslot，2/4Tslot,和3/4Tslot。現(xiàn)有第2組的兩個用戶A和用戶B通過傳統(tǒng)CSMA/CA機制選取的隨機退避時間相同，為t3-t0。根據(jù)改進的CSMA/CA機制，用戶A和B將根據(jù)優(yōu)先級選擇提前或推遲一個時間偏移量。假設用戶A提前一個時間偏移量t’，而用戶B推遲一個時間偏移量t。顯然，如果無法保證（t+t’=Tslot&t≠0&t’≠0)，那么這兩個用戶就很有可能會與其他組的用戶發(fā)生競爭沖突。不妨設t=2/4Tslot,t’=1/4Tslot,那么經(jīng)改進的CSMA/CA機制處理后，用戶B最終的時間為t3-t0+2/4Tslot（即圖4中的‘8’點），而用戶A最終的退避時間為t3-t0-1/4Tslot（即圖4中的‘6’點），這時用戶A已經(jīng)屬于第3組。要使用戶A仍然屬于第2組，而不影響其他組用戶的資源競爭，需確保t’的取值必須為Tslot-t，即t’=Tslot-t。可見，這個條件（t+t=Tslot&t≠0&t’≠0)是用戶分組方法成敗的關鍵，必須得到滿足。

圖4 用戶分組方法舉例Fig. 4 Example of user grouping method

如圖4所示，部分用戶組只能在整數(shù)倍slot time時刻（例如t1, t2, t3）接入信道，例如圖中的‘a(chǎn)’、‘b’、‘c’點；而部分用戶組只能非整數(shù)倍slot time時刻接入信道，例如第1組只能在 ‘1’、‘4’、‘7’點接入信道，第2組只能在‘2’、‘5’、‘8’點接入信道，第3組只能在‘3’、‘6’、‘9’點接入信道，這相當于將總的通信終端數(shù)量減少了一倍。很顯然，通過這種方法很好解決了系統(tǒng)內(nèi)部沖突的問題。而且如果把不同的用戶組用于不同的通信系統(tǒng)，通過這種分組方法，不僅避免了系統(tǒng)內(nèi)的競爭沖突，同時也很大程度上減小了系統(tǒng)間的碰撞概率。這種方法可以把原本因碰撞而浪費的大量頻帶資源利用起來，所以可以很大程度上提升頻譜利用率。

從理論上來講，用戶分組越多，帶來的性能增益也越大。但是，過多的分組可能引發(fā)不可預測的后果，所以建議用戶組分組不宜過多。

3 仿真分析

為了評估所提出的改進方案的性能，我們進行了仿真試驗。主要用到的仿真參數(shù)如表1所示。所有的仿真都是在系統(tǒng)為飽和的條件下進行的，并且假設包錯誤率為0%。

表1 主要仿真參數(shù)Tab.1 Main simulation parameters

圖5 沖突概率的比較Fig. 5 Comparison of collision probability

圖5比較了傳統(tǒng)方案和改進方案之間的碰撞概率。從圖中可以看出，改進的方案有效的降低了整個系統(tǒng)的碰撞概率。隨著用戶數(shù)量的增加，系統(tǒng)的碰撞概率總是呈上升趨勢的。但是我們也可以看出，隨著用戶數(shù)量的增加，兩條曲線的距離有增大的趨勢，這說明在用戶數(shù)量較多的時候，本方案可以更加有效的降低系統(tǒng)的碰撞概率。

圖5 沖突概率的比較Fig. 5 Comparison of collision probability

圖6比較了兩種方案下的系統(tǒng)的吞吐率。由于本方案有效的降低了系統(tǒng)的碰撞概率，所以其系統(tǒng)吞吐率相對于傳統(tǒng)方案有了明顯的提升。由于碰撞概率隨著用戶數(shù)量的增加而上升，所以吞吐率隨著用戶數(shù)量的增加而降低，從圖中可以看到，與原有方案相比，本方案在用戶數(shù)量較多時，吞吐率下降程度比傳統(tǒng)方案要小很多。

4 結(jié) 論

隨著入網(wǎng)需求的不斷攀升，眾多的設備如何能夠有效的和公平的競爭有限的無線資源，這是運行在ISM頻段的各種系統(tǒng)的主要問題之一。在標準的CSMA/CA協(xié)議中，各種設備，不管是相同系統(tǒng)的還是不同系統(tǒng)的，都是按照統(tǒng)一的競爭機制去競爭資源。這往往會導致嚴重的系統(tǒng)沖突和系統(tǒng)間不公平。

文中提出了一種改進的CSMA/CA機制，通過修改相同的隨機退避時間，把可能發(fā)生的系統(tǒng)沖突降低。并且提出了用戶分組的想法，并且可以在WLAN系統(tǒng)中引入優(yōu)先級的概念。通過仿真分析可以看到本方法可以有效的避免系統(tǒng)沖突，提高系統(tǒng)容量。

[1] ANSI/IEEE Std.802.11.Wireless LAN Medium Access Control(MAC) and Physical Layer (PHY) specifications[S].1999.

[2] 徐同剛. D2D通信系統(tǒng)的工作模式的選擇研究[D].南京:南京郵電大學,2013.

[3] 王付彩.多信道無線Adhoc網(wǎng)絡協(xié)議設計與研究[D].長沙:國防科學技術大學,2011.

[4] 聶世群,田偉莉.IEEE802.11MAC層CSMA/CA機制的分析與研究[J].內(nèi)江科技,2007(6):102-103.NIE Shi-qun,TIAN Wei-li. Analysis and research of IEEE802.11 MAC layer CSMA/CA mechanism[J].Neijiang Technology,2007(6):102-103.

[5] 黃仁.非時隙CSMA/CA性能分析與研究[J].計算機工程與應用,2009,45(7):108-110.HUANG Ren.Analysis and research of the performance of the unsoltted CSMA/CA[J]. Computer Engineering and Application,2009,45(7):108-110.

[6] 常大為.基于IEEE802.15.4的CSMA/CA性能分析與研究[J].電信工程技術與標準化,2006(1):28-32.CHANG Da-wei. Analysis and research of performance of CSMA/CA based on I EEE802.15.4[J].Telecommunication Engineering Technology and Standardization, 2006(1):28-32.

[7] 周林.IEEE802.15.4MAC協(xié)議CSMA_CA優(yōu)化算法研究[J].廣東通信技術,2012(2):66-69.ZHOU Lin.Research of optimization algorithm of IEEE802.15.4 MAC CSMA_CA protocol[J]. Guangdong Communication Technology,2012(2):66-69.