王俊杰，李 達(dá)，劉守印

（華中師范大學(xué) 湖北 武漢 430079）

802.11DCF退避算法改進(jìn)與仿真

王俊杰，李 達(dá)，劉守印

（華中師范大學(xué) 湖北 武漢 430079）

針對(duì)IEEE802.11DCF競(jìng)爭(zhēng)窗口調(diào)整策略，提出了一種新的競(jìng)爭(zhēng)窗口退避算法HBDCF（Hybrid Distributed Coordination Function）。算法利用了TCP（Transmission Control Protocol）擁塞控制的機(jī)制，發(fā)送失敗時(shí)，競(jìng)爭(zhēng)窗口采用先指數(shù)增長(zhǎng)，達(dá)到閾值后線性增長(zhǎng)；發(fā)送成功次數(shù)達(dá)到函數(shù)值時(shí)，競(jìng)爭(zhēng)窗口采用先線性遞減，后指數(shù)遞減的方式。采用二維Markov chain模型進(jìn)行理論分析和通過(guò)OPNET對(duì)改進(jìn)算法進(jìn)行仿真實(shí)驗(yàn)。研究結(jié)果表明，研究結(jié)果表明，該算法在規(guī)模較大的網(wǎng)絡(luò)中能夠有效地降低DCF碰撞概率和網(wǎng)絡(luò)延時(shí)，提高系統(tǒng)的飽和吞吐量。

IEEE802.11 DCF；競(jìng)爭(zhēng)窗口；退避算法；OPNET仿真

IEEE 802.11[1]標(biāo)準(zhǔn)定義了無(wú)線網(wǎng)絡(luò)（WIFI）的物理層和MAC（介質(zhì)訪問(wèn)控制）層[2]，MAC層的協(xié)議規(guī)定了兩種信道接入機(jī)制，即分布式協(xié)調(diào)控制機(jī)制（DCF，Distributed Coordination Function）和無(wú)競(jìng)爭(zhēng)的 點(diǎn) 協(xié) 調(diào) 控 制 機(jī) 制 （PCF，Point Coordination Function）。在實(shí)際的WIFI協(xié)議中，MAC層最常用的接入?yún)f(xié)議為DCF[3]，它主要采用了帶沖突避免的載波偵聽(tīng)多路訪問(wèn)（CSMA/CA[4]）控制機(jī)制，利用虛擬載波偵聽(tīng)與物理載波偵聽(tīng)相結(jié)合的方式，通過(guò)二進(jìn)制指數(shù)退避算法來(lái)實(shí)現(xiàn)不同節(jié)點(diǎn)的自適應(yīng)接入。DCF接入?yún)f(xié)議還引入了RTS/CTS協(xié)議 （Request To Send/Clear To Send），有效地解決隱藏節(jié)點(diǎn)和暴露節(jié)點(diǎn)的問(wèn)題。

MAC協(xié)議設(shè)計(jì)是無(wú)線局域網(wǎng)研究的關(guān)鍵技術(shù)之一[5]，對(duì)DCF協(xié)議的改進(jìn)一直是一個(gè)研究熱點(diǎn)。針對(duì)DCF算法的特點(diǎn)，通過(guò)Markov分析模型或仿真實(shí)驗(yàn)，得到各參數(shù)與網(wǎng)絡(luò)性能之間的關(guān)系[6]，并對(duì)這些參數(shù)進(jìn)行調(diào)整來(lái)優(yōu)化網(wǎng)絡(luò)性能。主要研究有：1）對(duì)DCF退避算法的競(jìng)爭(zhēng)窗口的調(diào)整機(jī)制改進(jìn)及優(yōu)化；2）對(duì)DCF初始競(jìng)爭(zhēng)窗口機(jī)制改進(jìn)及優(yōu)化。

針對(duì)退避算法競(jìng)爭(zhēng)窗口的調(diào)整機(jī)制改進(jìn)和優(yōu)化，Bianchi[7]首先提出了二維Markov Chain模型，并證明了模型的正確性，為以后人們從理論上分析DCF性能提供了理論依據(jù)；Song等人[8]提出了發(fā)送成功通過(guò)乘以大于1的因子增加競(jìng)爭(zhēng)窗口，發(fā)送失敗則通過(guò)乘以小于 1的因子來(lái)減小競(jìng)爭(zhēng)窗口的EIED算法來(lái)改進(jìn)性能；Ni Q[9]提出了發(fā)送成功競(jìng)爭(zhēng)窗口減半，發(fā)送失敗競(jìng)爭(zhēng)窗口加倍，改善了節(jié)點(diǎn)中數(shù)據(jù)的發(fā)送效率和公平性；Deng[10]利用已有的分析模型，提出了MILD （乘性增加線性減?。┩吮軝C(jī)制；Wang Chong gang等[11]提出了當(dāng)發(fā)送沖突時(shí)，競(jìng)爭(zhēng)窗口加倍，當(dāng)連續(xù)傳輸成功C次后，競(jìng)爭(zhēng)窗口減半的GDCF算法；徐穎[12]提出了WDCF算法，該算法在GDCF算法的基礎(chǔ)上，增加了一個(gè)分段函數(shù)，連續(xù)傳輸成功的次數(shù)門限C（i）根據(jù)不同的退避階段產(chǎn)生不同的連續(xù)傳輸次數(shù)。但是，以上算法在減少碰撞概率和網(wǎng)絡(luò)延時(shí)的等方面還存在著一些不足，還有進(jìn)一步的改進(jìn)空間。

文中在充分分析和理解上述算法的基礎(chǔ)上，比較了每種算法的優(yōu)缺點(diǎn)，借鑒傳統(tǒng)協(xié)議中擁塞控制算法的機(jī)制，在飽和吞吐量基本不變的情況下，為了降低規(guī)模較大的網(wǎng)絡(luò)中碰撞概率和網(wǎng)絡(luò)延時(shí)，提出了用分段函數(shù)來(lái)表示競(jìng)爭(zhēng)窗口的改進(jìn)算法HBDCF（Hybrid Distributed Coordination Function），并對(duì)它的碰撞概率等性能參數(shù)進(jìn)行了理論和仿真分析。

1 算法設(shè)計(jì)思想及理論模型介紹

1.1 HBDCF算法設(shè)計(jì)思想介紹

HBDCF是在WDCF算法的基礎(chǔ)上，依據(jù)TCP擁塞算法思想，提出一種新型退避算法的競(jìng)爭(zhēng)窗口優(yōu)化算法，它采用WDCF算法中設(shè)定連續(xù)傳輸次數(shù)門限C（i）的方法，并在此基礎(chǔ)上引入分段函數(shù)來(lái)表示競(jìng)爭(zhēng)窗口大小的變化。具體做法是，當(dāng)每次數(shù)據(jù)發(fā)送失敗之后，CW（Contention Window）隨著退避階段i加倍，若退避階段達(dá)到規(guī)定的窗口閾值S時(shí)，CW開(kāi)始線性增長(zhǎng)。當(dāng)連續(xù)成功傳輸次數(shù)沒(méi)有達(dá)到C次，CW窗口大小不變；當(dāng)連續(xù)成功傳送次數(shù)達(dá)到C次，若CW大于窗口閾值，CW則線性減少，若小于窗口閾值，CW則指數(shù)減少。算法采用分段函數(shù)來(lái)表示競(jìng)爭(zhēng)窗口的變化，在達(dá)到窗口閾值S之前指數(shù)增長(zhǎng)，使得競(jìng)爭(zhēng)窗口迅速接近最佳窗口值，達(dá)到閾值S之后線性增長(zhǎng)，避免了窗口增長(zhǎng)過(guò)快引起的網(wǎng)絡(luò)時(shí)延等性能的降低。公式（1）、（2）分別給出了競(jìng)爭(zhēng)窗口與連續(xù)傳輸次數(shù)C與退避階段i的數(shù)學(xué)表達(dá)式。該算法的流程圖如圖1所示。

圖1 HBDCF算法流程圖

1.2 Markov Chain模型

目前，在IEEE 802.11 DCF的性能分析和建模的方法中，大家都是在Bian Chi提出的二維Markov鏈模型上進(jìn)行相關(guān)理論研究。它通過(guò)對(duì)模型的穩(wěn)態(tài)求解，近似的得到了任意時(shí)隙內(nèi)節(jié)點(diǎn)的發(fā)送概率和發(fā)送數(shù)據(jù)的沖突概率，進(jìn)而得到飽和吞吐量。但是，這個(gè)模型沒(méi)有考慮到多跳網(wǎng)絡(luò)中存在的隱藏終端和暴露終端的問(wèn)題以及只考慮了數(shù)據(jù)發(fā)送失敗沒(méi)有考慮信道發(fā)生錯(cuò)誤的情況；同時(shí)在建模過(guò)程中，沒(méi)有考慮有限重傳次數(shù)、退避凍結(jié)以及等情況。為了解決上述問(wèn)題，許多研究學(xué)者都進(jìn)行了相關(guān)的研究[13-16]。

由于本文主要研究DCF算法的改進(jìn)對(duì)網(wǎng)絡(luò)性能的影響，考慮到分析簡(jiǎn)單的基礎(chǔ)上，采用了與文獻(xiàn)[1]同樣的假設(shè)：1）理想信道，不考慮信道的錯(cuò)誤，只有沖突才引起丟包和重傳；2）各站點(diǎn)均處于飽和狀態(tài)，即每個(gè)站點(diǎn)始終都有數(shù)據(jù)包在緩存隊(duì)列中等待發(fā)送；3）每個(gè)時(shí)隙發(fā)送數(shù)據(jù)時(shí)，可能產(chǎn)生沖突的概率值p，始終獨(dú)立且為固定值。

如圖2為二維Markov Chain模型，二維隨機(jī)過(guò)程{S（t），B（t）}表示節(jié)點(diǎn)的退避計(jì)數(shù)器在t時(shí)刻所處的狀態(tài)，其中S（t）表示在t時(shí)刻節(jié)點(diǎn)所處的退避階段（0，1，2，…，m），m為最大退避階數(shù)，b（t）表示節(jié)點(diǎn)在t時(shí)刻退避計(jì)數(shù)器的值，t和t+1表示兩個(gè)連續(xù)時(shí)隙（slot）的起始時(shí)刻。

圖2 二維Markov鏈模型

假設(shè)P{i1，k1|i0，k0}=P{S（t+1）=i1，B（t+1）=k1|S（t）= i0，B（t）=k0}

則圖2所示的二維Markov鏈模型的單步轉(zhuǎn)移概率p可以用以下公式來(lái)表示。

其中，P代表某站點(diǎn)嘗試傳送數(shù)據(jù)包時(shí)的發(fā)生碰撞的沖突概率。

指站點(diǎn)在隨機(jī)選取的時(shí)隙里成功傳輸數(shù)據(jù)包的概率。Pi代表站點(diǎn)從第i個(gè)退避階段回退到第i-1個(gè)退避階段的概率

Markov鏈的穩(wěn)態(tài)分布為：

bi，k代表階段退避時(shí)隙位于第i個(gè)退避階段的第k個(gè)時(shí)隙的概率。由圖2和（3）式可得：

以此來(lái)推便可以得出：

將（1）和（5）代入（7）可得：

其中

由于對(duì)任意的k[1，Wi-1]，根據(jù)鏈?zhǔn)椒▌t可得：

所有時(shí)隙的概率都可以用 表示，并且滿足以下關(guān)系：

所有的數(shù)據(jù)成功傳輸都是在退避時(shí)隙計(jì)為0時(shí)發(fā)生的，所以

以上歸納總結(jié)，由方程（4）、（10）、（11）組成的方程可以得到b0，0，p，τ的非線程方程組，從而可以求借得到p，τ的值。

1.3 飽和吞吐量的計(jì)算

設(shè)S為歸一化系統(tǒng)吞吐量，其定義為有效載荷在信道中占用的時(shí)間與總信道時(shí)間的比值。定義Pt1為在選取任一時(shí)隙時(shí)有至少一個(gè)節(jié)點(diǎn)在發(fā)送數(shù)據(jù)的概率，則Pt1的等式為

定義Ptx為在至少有一個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的情況下有節(jié)點(diǎn)成功發(fā)送數(shù)據(jù)的概率

則歸一化系統(tǒng)吞吐量公式:

其中，E[P]表示數(shù)據(jù)包平均有效載荷大小，在一個(gè)時(shí)隙中成功傳輸?shù)挠行лd荷的平均大小Pt1PtxE[P]，Ts是因?yàn)閿?shù)據(jù)包成功傳輸而導(dǎo)致其它節(jié)點(diǎn)檢測(cè)到信道繁忙的平均時(shí)間；Tc是因?yàn)閿?shù)據(jù)包發(fā)送碰撞而導(dǎo)致檢測(cè)到信道繁忙的平均時(shí)間；σ表示空閑時(shí)隙持續(xù)時(shí)間。

若僅考慮只通過(guò)基本的接入機(jī)制管理的通信系統(tǒng)，設(shè)分組頭部H=PHYhdr+MAChdr，另設(shè)δ為傳輸時(shí)延，則有關(guān)于Ts，Tc的如下關(guān)系式：

E[P*]表示最長(zhǎng)數(shù)據(jù)包在有沖突的情況下平均有效載荷大小。

在分析采用RTS/CTS接入機(jī)制的通信系統(tǒng)時(shí)，根據(jù)協(xié)議約定，考慮到碰撞僅僅發(fā)生在RTS幀，此時(shí)關(guān)于Ts，Tc的關(guān)系式如下：

2 HBDCF算法的理論計(jì)算和仿真分析

上一節(jié)從理論上分析了算法，本節(jié)通過(guò)MATLAB和OPNET對(duì)標(biāo)準(zhǔn)DCF、WDCF和HBDCF三種算法從理論和實(shí)際情況進(jìn)行仿真，比較在不同站點(diǎn)的情況下，各個(gè)算法的碰撞概率、飽和吞吐量和網(wǎng)絡(luò)延遲。

首先，我們最關(guān)注的是碰撞概率，通過(guò)MATLAB對(duì)標(biāo)準(zhǔn)DCF、WDCF和HBDCF 3種算法的

碰撞概率進(jìn)行了理論計(jì)算，計(jì)算結(jié)果如表1所示。

表1 不同站點(diǎn)3種算法包碰撞概率比較

表2 網(wǎng)絡(luò)節(jié)點(diǎn)仿真參數(shù)

從表格可以看出，HBDCF算法在不同規(guī)模節(jié)點(diǎn)下的包碰撞概率值都是最小的，由此可以得出HBDCF算法減小了碰撞概率，并且在規(guī)模越大的網(wǎng)絡(luò)中效果越明顯。不過(guò)在達(dá)到減小碰撞概率的同時(shí)，也導(dǎo)致了節(jié)點(diǎn)接入延時(shí)的增大。

其次，為了更好地對(duì)驗(yàn)證算法在實(shí)際情況下的表現(xiàn)情況，我們利用OPNET仿真軟件，通過(guò)OPNET對(duì)標(biāo)準(zhǔn)DCF、WDCF和HBDCF3種算法在相同的條件下進(jìn)行仿真，獲得各個(gè)算法的碰撞概率、飽和吞吐量和網(wǎng)絡(luò)延遲的仿真值。仿真時(shí)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)的數(shù)據(jù)傳輸速率都設(shè)置為1Mbps，物理層采用Direct Sequence技術(shù)，網(wǎng)絡(luò)中節(jié)點(diǎn)的WLAN參數(shù)設(shè)置如表2所示。

以下分別給出了HBDCF算法在RTS接入與非RTS接入方式下與DCF、WDCF在碰撞概率、網(wǎng)絡(luò)時(shí)延、以及歸一化吞吐量在不同節(jié)點(diǎn)數(shù)時(shí)的具體參數(shù)。

圖3 非RTS接入方式碰撞概率的變化曲線

圖4 RTS接入方式碰撞概率的變化曲線

從圖3和圖4可以看出，HBDCF算法的碰撞概率要優(yōu)于其他算法，并且在網(wǎng)絡(luò)規(guī)模越大是表現(xiàn)的越明顯，從而印證了理論分析的正確性，并且可以看出，HBDCF算法在非RTS協(xié)議有更好的效果。

從圖5和圖6可以看出，HBDCF算法對(duì)吞吐量的改善不是很大，特別是在規(guī)模較小的網(wǎng)絡(luò)中，不過(guò)在網(wǎng)絡(luò)規(guī)模數(shù)大于50個(gè)節(jié)點(diǎn)時(shí)，吞吐量會(huì)有一些明顯的改善。同時(shí)也可以看出，在非RTS情況下的吞吐量比RTS情況下的吞吐量要大。

圖5 非RTS接入方式歸一化飽和吞吐量的變化曲線

圖6 圖6 RTS接入方式的歸一化飽和吞吐量的變化曲線

圖7 非RTS接入方式網(wǎng)絡(luò)延遲的變化曲線

圖8 RTS接入方式網(wǎng)絡(luò)延遲的變化曲線

從圖7和圖8可以看出，HBDCF算法對(duì)網(wǎng)絡(luò)延時(shí)的沒(méi)有很大的改善，不過(guò)還是有了一些優(yōu)化，同時(shí)在我們仿真中部分節(jié)點(diǎn)延時(shí)反而比較大，也就是說(shuō)，HBDCF算法并不能對(duì)網(wǎng)絡(luò)的各個(gè)標(biāo)準(zhǔn)參數(shù)都進(jìn)行了改善和提高，也可以看出該算法也具有一定的局限性。

從以上仿真圖我們可以看出，HBDCF算法能夠有效地降低WLAN網(wǎng)絡(luò)中各節(jié)點(diǎn)發(fā)送包的碰撞概率，整個(gè)系統(tǒng)飽和吞吐量的性能也有所改善，并且在網(wǎng)絡(luò)延時(shí)方面也有一定的優(yōu)化。另外，HBDCF算法應(yīng)用于RTS/CTS環(huán)境比應(yīng)用于非RTS環(huán)境中，對(duì)網(wǎng)絡(luò)整體性能有更好的改善。

3 結(jié)束語(yǔ)

文中是為了優(yōu)化大規(guī)模網(wǎng)絡(luò)下的包碰撞概率，提出了一種新型的競(jìng)爭(zhēng)窗口動(dòng)態(tài)調(diào)整退避算法，巧妙的在退避階段增長(zhǎng)時(shí)采用擁塞函數(shù)思想以及在退避門限減少時(shí)兩次采用擁塞函數(shù)思想對(duì)DCF算法進(jìn)行了優(yōu)化。本文首先根據(jù)二維Markov鏈建立了理論模型，從理論上計(jì)算出了該算法在包碰撞概率；然后在OPNET上進(jìn)行了實(shí)驗(yàn)仿真，仿真結(jié)果表明該算法在不僅僅在包碰撞概率有了很大的改善，在時(shí)延和網(wǎng)絡(luò)吞吐量方面相對(duì)于DCF以及WDCF算法也都有所改善。并且可以通過(guò)閾值s和斜率k2，來(lái)動(dòng)態(tài)改變碰撞概率和吞吐量等網(wǎng)絡(luò)性能參數(shù)，使其能夠符合特定的網(wǎng)絡(luò)需求。然而，對(duì)不同規(guī)模網(wǎng)絡(luò)的最佳閾值和最佳斜率等因素尚未得出結(jié)論，這些將是下一步研究的內(nèi)容。

[1]by IEEE eD.11:Wireless LAN Medium Access Control （MAC） and Physicallayer （PHY）specifications:Medium Access Control（MAC）Enhancements for Quality of Service（QoS），Draft Supplement to[C]//IEEE 802.11 Standard，Draft 13.0.2010.

[2]MATTBEW S.GAST.802.11無(wú)線網(wǎng)絡(luò)權(quán)威指南[M].2版.南京：東南大學(xué)，2007.

[3]范謙.IEEE 802.11 MAC機(jī)制性能分析及其改進(jìn)[D].杭州：浙江大學(xué)，2003.

[4]Ni J，Srikant R.Distributed CSMA/CA algorithms for achieving maximum throughput in wireless networks[C]//Information Theory and Applications Workshop,2009（2015）:250.

[5]熊春蘭.IEEE802.11DCF協(xié)議性能分析及退避算法改進(jìn)[D].廣州：中山大學(xué)，2009.

[6]張南.無(wú)線網(wǎng)絡(luò)MAC層接入控制研究[D].北京：北京交通大學(xué)，2013.

[7]Bianchi Giuseppe.Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications，2000，18（3）:535-547.

[8]Song N O，Kwak B J，Song J，et al.Enhancement of IEEE 802.11 distributed coordination function with exponential increase exponential decrease back off algorithm [C]//Vehicular Technology Conference, 2003.VTC 2003-Spring.The 57th IEEE Semiannual.IEEE，2003，4:2775-2778.

[9]Decrease Ni Q,Aad I,Barakat C,et al.Modeling and analysis of slow CW decrease IEEE 802.11 WLAN[C]//14th IEEE Proceedings on Personal, Indoor and Mobile Radio Communications（PIMRC 2003）.IEEE，2003，2:1717-1721.

[10]Deng J,Varshney P K,Haas Z J.A new back off algorithm for the IEEE 802.11 distributed coordination function[EB/OL].（2017-03-20）.http：//www.docin.com/p-854815510.html.

[11]WANG Chong-gang，LI Bo.A new collision resolution mechanism to enhance the performance of IEEE 802.11 DCF[J].IEEE Transactions on Vehicular Technology，2004，53（4）:1235-1246.

[12]徐穎，白光偉，王明超.基于競(jìng)爭(zhēng)窗口動(dòng)態(tài)調(diào)整的802.11 DCF改進(jìn)算法 [J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（23）:5308-5310.

[13]鐘萍，施海彬，莊玉祥，等.IEEE 802.11DCF協(xié)議性能分析模型[J].應(yīng)用科學(xué)學(xué)報(bào)，2013，31（1）:41-47.

[14]唐倫，劉益富，劉青海，等.一種改進(jìn)IEEE 802.11 DCF的建模與分析 [J].北京郵電大學(xué)學(xué)報(bào)，2014（5）:96-99.

[15]馮鑫，黨幼云，向乾，等.基于物聯(lián)網(wǎng)的電量采集及分析系統(tǒng)設(shè)計(jì) [J].陜西電力，2014（2）：80-84.

[16]申定輝，劉坤，劉宇滕，等.基于統(tǒng)計(jì)學(xué)指標(biāo)的配電網(wǎng)狀態(tài)估計(jì)目標(biāo)函數(shù)的性能分析[J].陜西電力，2015（7）：43-47.

New improved back-off algorithm and simulation for 802.11DCF

WANG Jun-jie，LI Da，LIU Shou-yin
（Central China Normal University，Wuhan 430079，China）

In this paper，Hybrid Distributed Coordination Function algorithm for 802.11DCF is proposed. We begin with the read of existing strategies on back-off methods.Similar to the traditional Transmission Control Protocol congestion control，after consecutive failure transmission，contention window increases exponentially with back-off stage initially，then turns to increase linearly when the threshold is arrived；after successful transmission，if the consecutive successfully transmission times reach to the function value，contention window decreases linearly initially，then turns to decrease with back-off stage when the threshold is arrived.We use a Markov chain model to analyze the impact of the HBDCF and Through OPNET Simulation Tools to simulate.The simulation demonstrate that this algorithm reduce the probability of collision and delay，improve the saturation throughput effectively in large wireless net.

IEEE802.11 DCF；contention window；back-off algorithm；OPNET simulation

TN923

A

1674－6236（2017）10-0148-06

2016-04-23稿件編號(hào)：201604230

王俊杰（1989—），男，山西陽(yáng)泉人，碩士。研究方向：WIFI穩(wěn)定性研究、物聯(lián)網(wǎng)。