802.11DCF退避算法改進與仿真

王俊杰，李 達，劉守印

（華中師范大學 湖北 武漢 430079）

802.11DCF退避算法改進與仿真

王俊杰，李 達，劉守印

（華中師范大學 湖北 武漢 430079）

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

IEEE802.11 DCF；競爭窗口；退避算法；OPNET仿真

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

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

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

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

1 算法設計思想及理論模型介紹

1.1 HBDCF算法設計思想介紹

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

圖1 HBDCF算法流程圖

1.2 Markov Chain模型

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

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

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

圖2 二維Markov鏈模型

假設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可以用以下公式來表示。

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

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

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

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

以此來推便可以得出：

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

其中

由于對任意的k[1，Wi-1]，根據(jù)鏈式法則可得：

所有時隙的概率都可以用 表示，并且滿足以下關系：

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

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

1.3 飽和吞吐量的計算

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

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

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

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

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

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

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

2 HBDCF算法的理論計算和仿真分析

上一節(jié)從理論上分析了算法，本節(jié)通過MATLAB和OPNET對標準DCF、WDCF和HBDCF三種算法從理論和實際情況進行仿真，比較在不同站點的情況下，各個算法的碰撞概率、飽和吞吐量和網(wǎng)絡延遲。

首先，我們最關注的是碰撞概率，通過MATLAB對標準DCF、WDCF和HBDCF 3種算法的

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

表1 不同站點3種算法包碰撞概率比較

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

文中是為了優(yōu)化大規(guī)模網(wǎng)絡下的包碰撞概率，提出了一種新型的競爭窗口動態(tài)調(diào)整退避算法，巧妙的在退避階段增長時采用擁塞函數(shù)思想以及在退避門限減少時兩次采用擁塞函數(shù)思想對DCF算法進行了優(yōu)化。本文首先根據(jù)二維Markov鏈建立了理論模型，從理論上計算出了該算法在包碰撞概率；然后在OPNET上進行了實驗仿真，仿真結(jié)果表明該算法在不僅僅在包碰撞概率有了很大的改善，在時延和網(wǎng)絡吞吐量方面相對于DCF以及WDCF算法也都有所改善。并且可以通過閾值s和斜率k2，來動態(tài)改變碰撞概率和吞吐量等網(wǎng)絡性能參數(shù)，使其能夠符合特定的網(wǎng)絡需求。然而，對不同規(guī)模網(wǎng)絡的最佳閾值和最佳斜率等因素尚未得出結(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ǎng)絡權威指南[M].2版.南京：東南大學，2007.

[3]范謙.IEEE 802.11 MAC機制性能分析及其改進[D].杭州：浙江大學，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é)議性能分析及退避算法改進[D].廣州：中山大學，2009.

[6]張南.無線網(wǎng)絡MAC層接入控制研究[D].北京：北京交通大學，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]徐穎，白光偉，王明超.基于競爭窗口動態(tài)調(diào)整的802.11 DCF改進算法 [J].計算機工程與設計，2009，30（23）:5308-5310.

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

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

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

[16]申定輝，劉坤，劉宇滕，等.基于統(tǒng)計學指標的配電網(wǎng)狀態(tài)估計目標函數(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稿件編號：201604230

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