過濾發送閾值退避算法*

張長森, 陳鵬鵬, 胡宇鵬, 劉曉惠, 劉雪貞

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

過濾發送閾值退避算法*

張長森, 陳鵬鵬, 胡宇鵬, 劉曉惠, 劉雪貞

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

針對二進制回退機制存在的問題進行了分析，并提出了一種改進的回退算法。該算法通過引入過濾發送閾值的概念，動態地調整無線節點的等待時間，以實現網絡吞吐量的最大化。在IEEE 802.11 DCF協議中以相同的物理層參數進行仿真。實驗結果表明:與BEB算法、SD-DCF算法和MMS算法相比，改進算法在兩種發送方式尤其是基本方式下，飽和吞吐量和分組平均接入時延均可獲得不同程度的改善。

無線網絡； MAC機制； IEEE 802.11 DCF; 退避算法

0 引 言

退避機制是無線網絡MAC層協議中解決站點競爭信道資源發生碰撞的方法，目的是在多個站點爭用同一信道時，保證接入的有效性，使得系統資源得到合理利用。包括IEEE802.11[1]和802.15.4標準在內的許多無線網絡協議都采用二進制指數退避(binary exponential backoff,BEB)機制管理數據的重發。BEB算法為節點提供一種基于競爭窗口(contention window,CW)解決碰撞問題的方法。站點發送數據發生碰撞，CW的大小調整為原來的2倍；數據交互成功，CW置為最小。BEB算法因其原理簡單且執行效率高等特點而備受研究者的青睞，多種針對BEB的擴展方法被提了出來[2～5]。Ni Qiang等人[6]提出了SD-DCF(slow CW decrease DCF)算法。SD-DCF在數據發送成功時，把CW的大小置為當前的1/2。Wang Chonggang等人[7]在文獻[6]的基礎上提出了GDCF(gentle DCF)。GDCF設定了連續傳輸成功次數計數器，計數器達到閾值時，CW大小減1/2。文獻[8]提出的MMS(multi-channel MAC schemes based on 802.11)通過碰撞概率 管理退避計數器的遞減頻率，以達到動態調整無線站點等待時間的目的。

MMS保留了BEB的CW調整策略，實現簡單，改善了信道帶寬利用率，提高了網絡吞吐量。但由于碰撞概率這一單一信息不能完全真實地反映當前網絡狀態，MMS算法并沒有實現吞吐量最大化。本文在深入研究文獻[8]的基礎上，提出TFTB (transmission-filtered threshold back-off)算法。算法設置了一個和網絡中競爭站點數量密切相關的閾值以控制節點競爭信道的激烈程度，并通過二維離散時間馬爾科夫鏈建模分析了其理論最優值的設置。仿真實驗表明，TFTB算法有效地改善了網絡吞吐量和平均接入時延。

1 TFTB算法

1.1 算法描述

在動態分布式的網絡環境中，動態競爭站點數量反映了網絡當前的競爭狀態，站點的競爭接入碰撞概率隨著網絡中競爭站點數量的增多而增大，當碰撞概率很大時,盲目地發送數據包會導致網絡狀況惡化。以符號r表示過濾發送閾值，并將探討如何根據競爭節點數量選取r，才能實現網絡吞吐量的最大化。TFTB算法描述如下：

if (reach the slot of transmission) ∥到達發送時隙

then {calculate r based on the information of competition stations } ∥根據競爭站點數確定r。

if (D≤r) ∥按照均勻分布在[0,1]中隨機取一個值D和r進行比較

then {send frames or RTS packet } ∥發送數據幀

else {back off in current back-off stage} ∥D>r,不進行數據發送，在當前退避階段重新退避

if (the node fails to access the channel)

then {CWnew=min(CWmax,CWold×2} ∥將CW更新為原來的2倍，直到達到最大。

else {CWnew=CWmin} ∥將CW設置為最小值。

在上述對TFTB算法的描述中容易發現，和BEB算法、S-DCF算法以及MMS算法不同的是TFTB算法在節點完成退避過程后并不直接發送數據,而是根據過濾發送閾值來確定是否發送數據。由均勻分布的性質可得，站點完成退避后，有r的概率進行數據發送，有1-r的概率不發送數據，在當前退避階段重新退避。

1.2r的理論最優值

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

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

由于TFTB算法保留了BEB的CW調整策略，以Wi表示節點各個退避階段CW的大小，則Wi滿足

(1)

式中 W=W0=CWmin表示CW的最小值，2mW=CWmax表示CW的最大值，i為退避階段即數據幀經歷的重傳次數。 m為最大退避階段。 其他參數定義如下：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這一狀態的穩態概率。τ表示某個隨機選定的時隙，每個站點發送數據幀的概率。記q=r(1-pc)，可以得到TFTB算法的二維離散時間馬爾科夫鏈模型，如圖1所示。

圖1 TFTB的馬爾科夫鏈模型Fig 1 Markov link model for TFTB

由馬爾科夫鏈模型可得到如下穩態方程

(2)

經過化簡式(3)可以表示為

(3)

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

=1

(4)

聯立式(2)、式(3)中后兩個式子和式(4)可得

(5)

式中 pc=1-(1-τ)n-1。

由于r的過濾作用，結合式(3)中第一個式子可以將某個時隙站點的發送概率τ表示為

(6)

由文獻[9]可得使S最大化τ的最優解

(7)

表1(a) r的最優值(10～50) Tab 1(a) Optimal value of r (10-50)

表1(b) r的最優值(60～100)Tab 1(b) Optimal value of r(60-100)

2 仿真結果與分析

為了評估TFTB算法的性能和理論分析的正確性，利用Matlab R2009a進行仿真實驗。設置發送節點數量以10為步長從10變化到100，仿真時間為300 s。這10個網絡場景中，網絡中所有站點向同一個目的節點發送有效負載為1 000 B的數據流。其它仿真參數參照文獻[1]中基于DSSS PHY的DCF協議，如表2所示。相同條件下，仿真還分析了BEB算法、SD-DCF算法和MMS算法。

表2 主要仿真參數Tab 2 Main simulation parameters

圖2和圖3描繪了網絡飽和吞吐量隨著競爭站點數的變化曲線。從圖中可以看到：1)兩種方式下，飽和吞吐量隨競爭站點的增多呈現下降趨勢，BEB算法的網絡飽和吞吐量隨競爭站點數的增加下降的最為明顯，TFTB算法的飽和吞吐量隨競爭站點數的增加，基本保持平穩，下降幅度很小。2)RTS/CTS方式下，競爭站點數為10時，TFTB算法的飽和吞吐量和其他三種算法比較并無明顯優勢。這是因為RTS/CTS模式下站點很少時，網絡的擁塞程度很小，其他算法也能較好地適應網絡狀況。隨著競爭節點增多，TFTB算法跟蹤網絡規模的變化把 設置為理論最優值，其飽和吞吐量逐漸高于其他三種算法。3)在基本方式下，TFTB算法的飽和吞吐量始終高于其他三種算法，隨著競爭站點數量的增加，這種趨勢越來越明顯。競爭站點數目為100時，TFTB算法的網絡飽和吞吐量比BEB算法提高約67.24 %，比SD-DCF算法提高約43.44 %，比MMS算法提高了約26.67 %。

分組的平均接入時延為數據幀進入MAC層緩存到完成發送所需時間。圖4和圖5分別給出兩種發送方式下平均接入時延隨著競爭站點數的變化曲線。從圖中可以看出：1)兩種方式下，隨著競爭站點數量的增大不同算法的平均接入時延曲線均呈現上升趨勢。對于不同競爭站點數目，TFTB算法的平均接入時延始終低于其他三種算法，隨著站點數量的增加，它們之間的差距有擴大的趨勢。2)在基本發送方式下，當競爭站點數量為100時，TFTB算法的接入時延不到BEB算法的1/2，這表明TFTB算法可以有效地提高站點接入信道的效率。

3 結束語

針對BEB機制存在的缺陷，本文提出了FTTB算法，根據網絡規模設置相應的過濾發送閾值，動態地調整無線節點的等待時間。實驗結果表明：FTTB算法的飽和吞吐量和平均接入時延與BEB算法相比均有明顯的改善。其中基本發送方式下競爭站點數為10時，算法的飽和吞吐量比BEB算法提高了約67.24 % ，平均接入時延不到BEB算法的1/2。和其他BEB的增強算法相比FTTB算法的網絡性能也有不同程度地改善。

圖2 基本發送方式網絡歸一化飽和吞吐量Fig 2 Normalized system throughput of basic access scheme

圖3 RTS/CTS方式網絡歸一化飽和吞吐量Fig 3 Normalized system throughput of RTS/CTS access scheme

圖4 基本發送方式平均接入時延Fig 4 Average packet delay of basic access scheme

圖5 RTS/CTS方式平均接入時延Fig 5 Average packet delay of RTS/CTS access scheme

[1] IEEE 802.11.Part 11:Wireless LAN medium access control(MAC) and physical Layer (PHY) specifications[S].2007,IEEE Std:New York.

[2] Sun Xianghua,Dai Lin.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] 李運鵬,徐昌彪,劉 琳.無線傳感器網絡中一種競爭窗口自

適應MAC協議[J].傳感器與微系統,2010,29(1):49-54.

[4] 劉云璐,蒲菊華,方維維,等.一種無線傳感器網絡MAC協議優化算法[J].計算機學報,2012,35(3):529-539.

[5] Liu Jainshing.Design and performance evaluation of a distributed transmission control protocol for wireless local area network[J].IEICE Trans on Communications,2006,89(6):1837-1845.

[6] Ni Qiang,Aad I,Turletti T,et al.Modeling and analysis of slow CW decrease IEEE 802.11 WLAN[C]∥14th PIMRC,Beijing:IEEE,2003:1717-1721.

[7] Wang Chonggang,Li Bo,Li Lemin.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] 毛建兵,毛玉明,冷甦鵬,等.基于802.11的多信道MAC協議性能分析[J].計算機研究與發展,2009,46(10):1651-1659.

[9] 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.

Back-off algorithm based on transmission-filtered threshold*

ZHANG Chang-sen, CHEN Peng-peng, HU Yu-peng, LIU Xiao-hui, LIU Xue-zhen

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

Analyze on existing problems of the binary back-off mechanism,and propose an improved back-off algorithm.By introducing the concept of the transmission-filtered threshold,the algorithm dynamically adjusts waiting time of wireless nodes，in order to achieve the maximum network throughput.In the IEEE 802.11 DCF protocol,the simulation experiments are carried out with the same physical layer parameters.Experimental results show that normalized network throughput and average packet access delay of improved algorithm can all be improved with varying degrees under two access modes and especially basic access mode,by contrast with BEB algorithm,SD-DCF algorithm and MMS algorithm.

wireless networks; MAC scheme; IEEE 802.11 DCF; back-off algorithm

10.13873/J.1000—9787(2016)07—0143—04

2015—10—19

國家自然科學基金資助項目(51174263)； 教育部博士點基金資助項目(20124116120004)；河南省基礎與前沿技術研究項目(142300410144)

TP 393

A

1000—9787(2016)07—0143—04

張長森(1969-)，男，河南洛陽人，教授，博導，主研方向為無線傳感器網絡。