一種基于動態約束發送門限退避算法

張長森　陳鵬鵬

(河南理工大學計算機科學與技術學院　河南 焦作 454000)

?

一種基于動態約束發送門限退避算法

張長森陳鵬鵬

(河南理工大學計算機科學與技術學院河南 焦作 454000)

為了改進IEEE 802.11 DCF協議的二進制退避算法，提出一種基于動態約束發送門限退避算法。算法根據網絡中站點對信道資源的爭用程度設置動態門限，適當地約束部分站點數據的發送。一方面，算法沒有對二進制退避算法的競爭窗口調整機制進行修改，保留了其簡單、容易實現的優點；另一方面，有效地解決了傳統二進制退避算法在完成退避過程后，沒有考察網絡狀況而直接進行數據傳輸，容易產生沖突的缺點。仿真結果表明，該算法能夠提高飽和吞吐量和降低分組平均接入時延。

退避算法分布式協調功能動態門限

0　引　言

隨著人們對便攜電腦和移動工作站需求的日益增加，需要無線終端提供更加高效和可靠的通信。退避機制是無線網絡MAC層協議中解決站點競爭信道資源發生碰撞的方法，目的是在多個站點爭用同一信道時，保證接入的有效性，使得系統資源得到合理利用。算法既要抑制沖突的發生，又要避免因回退時間過長導致信道利用率的降低。

BEB機制為節點提供一種基于競爭窗口CW(Contention Window)解決沖突問題的方法。站點經歷一個以時隙為單位的退避時間后，進行數據發送，當沖突發生時，CW增大為原來的二倍；當數據幀傳輸成功時，CW設置為初值。BEB算法在一定程度上抑制了沖突的發生。包括IEEE 802.11[1]、802.15.4標準在內的許多無線網絡協議都采用二進制指數退避機制BEB(Binary Exponential Backoff)管理數據的重發。但是，當網絡中存在大量動態站點嘗試接入傳輸媒體時，其存在碰撞概率高、信道利用率低、接入公平性差等缺點[2-4]。針對算法的不足，一些研究者通過改進CW的調整方式來提高網絡性能。在文獻[5]提出的MIMD(Multiple Increase Multiple Decrease)算法中，發生碰撞時，CW按二進制指數方式逐級增加；發送成功時，CW按二進制指數方式減小。文獻[6,7]在文獻[5]的基礎上提出GDCF(Gentle DCF)，GDCF設定了一個連續傳輸成功次數計數器，計數器達到閾值c時，CW減半。文獻[8]發現在網絡負載較重時，算法不能賦予站點充足的退避時間，將導致大量沖突。為此，提出根據網絡規模調整站點對信道的爭用策略。文獻[9]提出一種適用于無線傳感器網絡的退避算法，使用工作模式切換機制管理網絡中動態站點數量，進而制定相應的CW。文獻[10]參照站點傳輸數據成功次數和失敗次數對CW進行設定，提高了信道接入的公平性。在文獻[11]中，無線站點利用接入點AP(Access Point)共享信息在分布式的網絡環境中優化CW。文獻[12]根據網絡中競爭節點的數量自適應地調整最小競爭窗口，提高了網絡吞吐量。

傳統二進制指數退避算法在完成退避過程后，沒有考察網絡狀況而直接進行數據傳輸，容易產生沖突。文獻[13]的思想是站點完成退避后不是立即接入信道，而是通過一個和數據幀重傳次數相關的傳輸概率P_T來競爭信道的使用權，并改進了數據發送成功時BEB算法的CW調整方式，但是卻沒有通過建立數學模型對傳輸概率的選取進行討論。文獻[14]延續了文獻[13]的思想并通過數學建模求得傳輸概率P_T的理論最優值，但是沒有考慮數據幀重傳次數對站點接入信道概率的影響。為了便于表述，稱之為CDCF。

在深入研究文獻[13，14]的基礎上，提出一種基于動態約束發送門限退避算法。算法設置了一個和網絡中競爭站點數量密切相關的門限對數據的傳輸進行適當的約束，以達到靈活地配置站點退避時間的目的。門限值設置為關于數據幀重傳次數的隱函數，并通過二維離散時間馬爾科夫鏈建模分析其取值對網絡性能的影響。和大多數改進算法不同的是，該算法完整地保留了BEB算法的CW調整策略，便于控制、容易實現。理論分析和仿真結果表明，該算法在網絡飽和吞吐量等性能指標上都有不同程度的提高。

1　相關工作

1.1IEEE 802.11 DCF

分布式協調功能(DCF)是IEEE802.11中重要的信道接入機制。DCF描述了兩種數據幀發送方式：基本方式和RTS/CTS方式。RTS/CTS方式可以解決隱藏終端和數據幀過大引起的信道利用率降低等問題。DCF采用BEB機制解決節點沖突問題，在高負荷的無線網絡中，站點都要經歷一個和CW相關的退避時間。具體方法是每個站點在嘗試發送報文之前，以CW表示CW的大小，按照均勻分布在競爭窗口[0,CW-1]中取一個退避時隙數T作為退避計數器的初值。每次站點偵聽到一個空閑時隙，T自減1。當 T減小到0時，站點以基本方式或者RTS/CTS方式發送數據。CW按照數據是否傳輸成功進行更新，如下式所示：

(1)

需要指出的是，CWmax表示當CW最大時T的最大取值，由于T是按照均勻分布在[0,CW-1]中取值的，CW的最大取值比CWmax大1；CWmin表示CW最小時T的最大取值，同理，CW的最小值比CWmin大1。

以Wi表示節點各個遞增階段CW的大小，則Wi滿足：

(2)

其中，W=W0=CWmin+1 表示CW的最小值，2mW=CWmax+1表示CW的最大值，i為數據幀所經歷的重傳次數，即節點所處退避階段，m為最大重傳次數或最大退避階段。可見，網絡中碰撞越頻繁，重傳次數越大，節點所處退避階段越高。

1.2飽和吞吐量

假定1在網絡中有n個站點競爭一個無線信道，信道條件是理想的(不考慮隱藏終端和信道捕獲)，系統工作在飽和狀態，即每個站的發送隊列總是非空的。

以τ表示某個隨機選定的時隙，每個站點發送數據幀的概率對于整個網絡中的n個站點，可能有以下三個事件發生：

(1) 網絡中沒有站點嘗試接入信道，其概率pidl為:

pidl=(1-τ)n

(3)

(2) 網絡中有一個節點成功接入信道，其概率psuc為:

(4)

(3) 網絡中有兩個或者更多的站點嘗試接入信道發生碰撞，其概率pcol為:

pcol=1-psuc-pidl=1-(1-τ)n-nτ(1-τ)n-1

(5)

整個網絡的歸一化飽和吞吐量可以定義為成功傳輸數據分組(不包含頭部)的信道時間與總的信道時間的比值[15]。以符號S表示歸一化飽和吞吐量。可以把S表示成下面的形式：

(6)

其中，Ts是一次傳輸成功導致信道被偵聽到繁忙的平均時長，Tc是一次沖突而導致信道被偵聽到繁忙平均時長，E[L]是數據分組平均有效長度，σ是一個空閑時隙的長度。

圖1　飽和吞吐量S和節點發送概率τ的關系

圖1參照標準[1]中相關參數描述了在基本發送方式和RTS/CTS方式下，網絡中競爭站點數量為10到30時，飽和吞吐量S與節點發送概率τ的關系。其中，數據分組平均有效長度E[L]為1000 Byte。從圖中發現，在相同條件下，基本方式下飽和吞吐量的曲線比RTS/CTS方式更為陡峭。兩種方式中，均存在一個使得S取得最大值的發送概率τ0，在τ0兩側S均呈現下降趨勢。設計退避算法時，應該使得發送概率τ盡量接近τ0，這樣可以提升網絡性能。

2　基于動態約束發送門限退避算法

2.1算法描述

在動態分布式的網絡環境中，動態競爭站點數量反映了網絡當前的競爭狀態。站點的競爭接入碰撞概率隨著網絡中競爭站點數量的增多而增大，當碰撞概率很大時,盲目地發送數據包會導致網絡狀況惡化。為了能夠根據動態競爭站點數量調整門限值從而達到特定的性能需求，把門限值定義成一個容易實現的非線性函數，以表現站點在不同退避階段所偵聽到信道的擁塞程度。定義約束發送門限如下式所示：

Ci=θii∈[0,m]

(7)

式中符號Ci表示站點處于退避階段i時的約束發送門限。在2.2節中，將根據網絡中競爭站點數量確定θ的最優值。基于動態門限約束發送門限退避算法描述如下所示：

if (reach the slot of transmission)

//到達發送時隙

then { obtain θ based on the information of competition stations,then calculate Ci}

//根據競爭站點數量確定θ，從而得到門限值Ci

if (R≤Ci)

//按照均勻分布在[0,1]中隨機取一個值R和Ci進行比較

then {send frames or RTS packet }

//發送數據幀

else { back off in current back-off stage}

//若R>Ci，不進行數據發送，在當前退避階段重新退避

if (the node fails to access the channel)

then {CWnew=min(CWmax+1,CWold×2) }

//把競爭窗口更新為原來的2倍，直到達到最大

else {CWnew=CWmin+1}

//把競爭窗口設置為最小值

在上述對改進算法的描述中容易發現，站點完成退避過程后，需要通過門限值Ci判斷是否對數據進行發送。由均勻分布的性質可得，站點完成退避后，有Ci的概率進行數據發送，有1-Ci的概率約束發送，在當前退避階段重新退避。

2.2算法性能分析

這一節主要是通過建立二維離散時間馬爾科夫鏈模型，分析當網絡中競爭節點數量變化時θ和網絡飽和吞吐量的關系，求得θ的最優值。

假定2某一個站點在某個時隙發送的數據幀發生沖突的概率pc為常數，和數據幀經歷過多少次沖突無關[15]。

其余參數定義如下：

k為退避計數器的值;

馬爾科夫鏈的二維狀態空間為：{(0,0)，(0,1)，(1,0)，…，(i,k)},i∈[0,m],k∈[0,Wi-1]；

P{i,k|i-1,k-1}表示從狀態(i-1,k-1)轉移到狀態(i,k)的轉移概率；

bi,k表示站點處于退避階段為i,退避計數器的值為k這一狀態的穩態概率。

改進算法保留BEB算法的競爭窗口調整策略，以Wi表示站點處于各個退避階段的競爭窗口CW，則Wi同樣滿足式(2)，CWmax、CWmin和W的定義均和1.1節中相同。在假定1和假定2的條件下，可以得到改進算法的二維離散時間馬爾科夫鏈模型，如圖2所示。其一步非空狀態轉移關系，如式(8)所示：

(8)

式(8)中第一個式子表示在退避過程中，站點每次偵聽到一個空閑時隙，退避計數器的值自減1；第二個式子表示站點退避計數器的值減至0，站點以Ci的概率進行數據發送，且發送成功，退避階段設置為0，退避計數器按均勻分布在[0,W0-1]中取值；第三個式子表示如果發生沖突，退避階段增加1，退避計數器按均勻分布在[Wi-1]中取值；第四個式子表示站點在完成退避過程后，以1-Ci的概率不進行數據發送，根據原退避階段所對應的競爭窗口確定退避計數器的值，重新進行退避；第五個式子表示當退避階段達到最大值m時，被約束發送或者發送數據失敗都不會使得退避階段增加。

圖2　改進算法的二維馬爾科夫鏈模型

由狀態轉移關系得各穩態概率滿足式(9):

(9)

將式(7)代入式(9)，經過化簡，得到：

(10)

由于遍歷狀態空間中所有狀態的穩態概率分布之和為1，得到：

(11)

聯立式(2)、式(10)、式(11)，得到：

(12)

由式(10)可以把某個時隙站點的發送概率τ表示為:

(13)

聯立式(6)、式(12)和式(13)，可以把系統飽和吞吐量表示成只含有θ、W和n的函數 。在W和競爭站點數量n為常量的情況下，使得系統歸一化飽和吞吐量S最大化需要滿足S對θ的偏導數為0。

(14)

在MATLAB中使用迭代法可以得到在競爭節點數量n為10到100，θ在兩種接入方式下的最優值，如表1所示。其中，W=32，E[L]=1000 Byte。

表1　θ的最優解

求得θ的最優解后，聯立式(12)和式(13)，得到某個隨機選定的時隙，某個站點發送數據幀的概率τ。圖3描繪了在兩種發送方式下，改進算法和BEB算法的發送概率τ隨著競爭站點數量的變化曲線。為了進行比較，在圖3中還給出了當歸一化飽和吞吐量取得最大值時發送概率τ0的取值隨著競爭站點數量的變化曲線。在圖中可以看到，在兩種方式中發送概率τ都是隨著競爭站點數量的遞增而減小。在兩種方式下，BEB算法的發送概率是相同的，改進算法的發送概率τ都小于BEB算法。隨著競爭站點數量的增加，改進算法的發送概率τ越來越接近于飽和吞吐量最大時發送概率τ0的曲線。通過前面的結論可知，改進算法通過約束站點數據幀的發送減小站點的發送概率，可以使得網絡穩態性能得到提升。

圖3　站點發送概率與競爭站點數量的關系

3　仿真分析

為了驗證改進算法的效果以及上述理論分析的正確性，利用Matlab R2009a進行仿真實驗。仿真時間為300 s。網絡中競爭站點數目分別取10到100，隨機選取一個站點為目的站點，其余站點均向其發送數據分組。任意兩個站點之間均是一跳可達的。數據分組的平均有效長度為1000 Byte，其他仿真參數參照文獻[1]中基于DSSS PHY的DCF協議，如表2所示。下面仿真分析了改進算法在不同競爭站點數量下的網絡性能。

表2　主要仿真參數

圖4和圖5給出了兩種方式下，不同算法的飽和吞吐量隨著競爭站點數量增大的變化曲線。從圖中可以看到，在RTS/CTS方式下，當競爭站點數量較少時，BEB算法和其他算法的飽和吞吐量差距較小。隨著競爭站點數量的增大，其他算法的飽和吞吐量開始均高于BEB算法，其中，改進算法的網絡飽和吞吐量是所有算法中最高的。在基本發送方式下，網絡飽和吞吐量隨著競爭站點的增多呈現下降趨勢，其中，BEB算法的網絡飽和吞吐量隨著競爭站點數目的增加下降最為明顯，改進算法的飽和吞吐量隨著競爭站點數量的增加基本保持平穩，下降幅度很小。改進算法的飽和吞吐量始終高于其他算法，隨著競爭站點數目的增大這種趨勢越來越明顯。在競爭站點數目為100時，改進算法的網絡飽和吞吐量比BEB算法提高了69.35%。

圖4　基本發送方式網絡飽和吞吐量

圖5　RTS/CTS方式網絡飽和吞吐量

分組的平均接入時延為數據幀從進入MAC層緩存到完成發送所需的時間。圖6給出了兩種發送方式下平均接入時延隨著競爭站點數量的變化曲線。

圖6　兩種方式平均接入時延

從圖中可以看出，在兩種發送方式下，隨著競爭站點數量的增大不同算法的平均接入時延曲線均呈現上升趨勢。在兩種發送方式下，對于不同競爭站點數目，改進算法的平均接入時延始終低于BEB算法，隨著站點數量的增加，它們之間的差距有擴大的趨勢。在基本發送方式下，當競爭站點數量為100時，改進算法的平均接入時延不到BEB算法的一半。這表明改進算法可以有效地降低網絡中節點競爭有限資源發生碰撞的概率，提高了站點接入信道的效率。

4　結　語

為了改進BEB機制，提出一種基于動態約束發送門限退避算法。算法中設置了一個和網絡中競爭站點數量密切相關的門限對數據的傳輸進行適當的約束,并通過二維離散時間馬爾科夫鏈建模求得其最優值。以相同的物理層參數在802.11 DCF協議中進行仿真，在兩種發送方式下，該算法的網絡飽和吞吐量和平均接入時延均優于BEB算法。在基本發送方式下，改進算法網絡性能的提升更加明顯，和其他改進算法相比該算法也有不同程度的性能提升。和大多數改進算法不同的是，該算法完整地保留了BEB算法的CW調整策略，便于控制、容易實現。

[1] IEEE Std 802.11.Part 11:Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[S].New York:IEEE Press,2007.

[2] Xinghua S,Dai L.Backoff Design for IEEE 802.11 DCF Networks:Fundamental Tradeoff and Design Criterion[J].IEEE/ACM Transactions on Networking,2015,23(1):300-316.

[3] Lei G,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.

[4] Shugong X,Saadawi T.Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks?[J].Communications Magazine,IEEE,2001,39(6):130-137.

[5] Haitao W,Shiduan C,Yong P,et al.IEEE 802.11 distributed coordination function (DCF):analysis and enhancement[C]//Procedings of IEEE International Conference on Communications,New York,NY,2002(1):605-609.

[6] Chonggang W,Weiwen T,Sohraby K,et al.A simple mechanism on MAC layer to improve the performance of IEEE 802.11 DCF[C]//Proceedings of the First International Conference on Broadband Networks,2004:365-374.

[7] Chonggang W,Bo L,Lemin L.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.

[8] Cali F,Conti M,Gregori E.Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit [J].IEEE/ACM Transactions on Networking,2000,8(6):785-799.

[9] Haosong G,Younghwan Y.An Energy Efficient MAC Protocol Based on IEEE 802.11 DCF for Wireless Sensor Networks in Port Logistics[C]//Proceedings of High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS),Liverpool.2012:728-733.

[10] Shurman M,Al-Shua’B B,Alsaedeen M,et al.N-BEB:New backoff algorithm for IEEE 802.11 MAC protocol[C]//Proceedings of 2014 37th International Convention on Information and Communication Technology,Electronics and Microelectronics,Opatija.2014:540-544.

[11] Krishnan M N,Shicong Y,Zakhor A.Contention window adaptation using the busy-idle signal in 802.11 WLANs[C]//Proceedings of Global Communications Conference (GLOBECOM),IEEE:Austin,TX,2014:4794-4800.

[12] Yubin X,Minghe H,Ma L,et al.A self-adaptive minimum contention window adjusting backoff algorithm in IEEE 802.11 DCF[C]//Proceedings of Consumer Electronics,Communications and Networks,Yichang,2012:1577-1582.

[13] 何宏,李建東,盛敏,等.一種基于慢退避思想的SD_DCC退避算法及其性能分析[J].計算機學報,2005,28(11):151-158.

[14] Guo W,Xiaofeng Z,Shunliang Mei,et al.A new constrained-send mechanism to enhance the performance of IEEE 802.11 DCF[C]//Proceedings of Communications and Networking in China (CHINACOM).IEEE:Harbin,2011:448-452.

[15] Bianchi G.Performance analysis of the IEEE 802.11 distributed coordination function[J].IEEE Journal on Selected Areas in Communications,2000,18(3):535-547.

A BACK-OFF ALGORITHM BASED ON DYNAMIC SENDING-CONSTRAINED THRESHOLD

Zhang ChangsenChen Pengpeng

(College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454000,Henan,China)

In order to improve the binary back-off algorithm of IEEE 802.11 DCF protocol,this paper proposes a dynamic sending-constrained threshold-based back-off algorithm.According to contention degree of sites in networks on the use of channel resources the algorithm sets the dynamic threshold,and appropriately constrains the data sending of part sites.On the one hand,the algorithm does not modify the adjustment mechanism of competition window of binary back-off algorithm but retains its advantages of simplicity and convenience in implementation;on the other hand,it effectively solves the shortcomings of traditional binary back-off algorithm that it directly transmits data without inspecting the network status after the completion of back-off process and thus is prone to cause conflicts.Simulation results demonstrate that this algorithm can improve the saturation throughput and reduce the average access delay.

Back-off algorithmDistributed coordination functionDynamic threshold

2015-05-21。國家自然科學基金項目(51174263)；教育部博士點基金項目(20124116120004);河南省基礎與前沿技術研究項目(142300410144)。張長森，教授，主研領域：礦井監控與通信，無線傳感器網絡。陳鵬鵬，碩士。

TP393.04

A

10.3969/j.issn.1000-386x.2016.09.026