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

萬(wàn)小博，譚國(guó)平，馬賽賽

（河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 南京 210000）

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

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

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

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

1 IEEE 802.11 MAC 協(xié)議

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

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

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

2 避免沖突的改進(jìn)的CAMA/CA機(jī)制

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

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

當(dāng)眾多的終端進(jìn)行通信時(shí)，在隨機(jī)退避時(shí)間的選擇上，選擇相同退避時(shí)間的終端的概率會(huì)增加，當(dāng)幾個(gè)終端的退避時(shí)間同時(shí)歸零時(shí)，它們會(huì)同時(shí)接入信道，進(jìn)而導(dǎo)致通信失敗。所以，為了避免通信的失敗，應(yīng)盡量讓不同的設(shè)備選擇不同的退避時(shí)間。

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

2.2 改進(jìn)方法

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

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

圖3 改進(jìn)的CSMA/CA退避機(jī)制Fig. 3 Improved mechanism of CSMA/CA

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

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

2.3 時(shí)間偏移量t的選取

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

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

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

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

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

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

3 仿真分析

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

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

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

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

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

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

4 結(jié) 論

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

文中提出了一種改進(jìn)的CSMA/CA機(jī)制，通過(guò)修改相同的隨機(jī)退避時(shí)間，把可能發(fā)生的系統(tǒng)沖突降低。并且提出了用戶分組的想法，并且可以在WLAN系統(tǒng)中引入優(yōu)先級(jí)的概念。通過(guò)仿真分析可以看到本方法可以有效的避免系統(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].南京:南京郵電大學(xué),2013.

[3] 王付彩.多信道無(wú)線Adhoc網(wǎng)絡(luò)協(xié)議設(shè)計(jì)與研究[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2011.

[4] 聶世群,田偉莉.IEEE802.11MAC層CSMA/CA機(jī)制的分析與研究[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] 黃仁.非時(shí)隙CSMA/CA性能分析與研究[J].計(jì)算機(jī)工程與應(yīng)用,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].電信工程技術(shù)與標(biāo)準(zhǔn)化,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].廣東通信技術(shù),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.