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

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

過濾發(fā)送閾值退避算法*

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

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

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

無線網(wǎng)絡(luò)； MAC機制； IEEE 802.11 DCF; 退避算法

0 引 言

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

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

1 TFTB算法

1.1 算法描述

在動態(tài)分布式的網(wǎng)絡(luò)環(huán)境中，動態(tài)競爭站點數(shù)量反映了網(wǎng)絡(luò)當(dāng)前的競爭狀態(tài)，站點的競爭接入碰撞概率隨著網(wǎng)絡(luò)中競爭站點數(shù)量的增多而增大，當(dāng)碰撞概率很大時,盲目地發(fā)送數(shù)據(jù)包會導(dǎo)致網(wǎng)絡(luò)狀況惡化。以符號r表示過濾發(fā)送閾值，并將探討如何根據(jù)競爭節(jié)點數(shù)量選取r，才能實現(xiàn)網(wǎng)絡(luò)吞吐量的最大化。TFTB算法描述如下：

if (reach the slot of transmission) ∥到達(dá)發(fā)送時隙

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

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

then {send frames or RTS packet } ∥發(fā)送數(shù)據(jù)幀

else {back off in current back-off stage} ∥D>r,不進行數(shù)據(jù)發(fā)送，在當(dāng)前退避階段重新退避

if (the node fails to access the channel)

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

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

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

1.2r的理論最優(yōu)值

假定1 在網(wǎng)絡(luò)中有n個站點競爭一個無線信道，信道條件是理想的，系統(tǒng)工作在飽和狀態(tài)，即每個站的發(fā)送隊列總是非空的。

假定2 某一個站點在某個時隙發(fā)送的數(shù)據(jù)幀發(fā)生沖突的概率pc為的常量，和數(shù)據(jù)幀經(jīng)歷過多少次沖突無關(guān)[9]。

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

(1)

式中 W=W0=CWmin表示CW的最小值，2mW=CWmax表示CW的最大值，i為退避階段即數(shù)據(jù)幀經(jīng)歷的重傳次數(shù)。 m為最大退避階段。 其他參數(shù)定義如下：k為退避計數(shù)器的值;馬爾科夫鏈的二維狀態(tài)空間為：{(0,0),(0,1),(1,0)，…，(i,k)},i∈[0,m],k∈[0,Wi-1];P{i,k|i-1,k-1}表示從狀態(tài)(i-1,k-1)轉(zhuǎn)移到狀態(tài)(i,k)的轉(zhuǎn)移概率；bi,k表示站點處于退避階段為i,退避計數(shù)器的值為k這一狀態(tài)的穩(wěn)態(tài)概率。τ表示某個隨機選定的時隙，每個站點發(fā)送數(shù)據(jù)幀的概率。記q=r(1-pc)，可以得到TFTB算法的二維離散時間馬爾科夫鏈模型，如圖1所示。

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

由馬爾科夫鏈模型可得到如下穩(wěn)態(tài)方程

(2)

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

(3)

由于遍歷狀態(tài)空間中所有狀態(tài)的穩(wěn)態(tài)概率分布之和為1，得到

=1

(4)

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

(5)

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

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

(6)

由文獻[9]可得使S最大化τ的最優(yōu)解

(7)

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

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

2 仿真結(jié)果與分析

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

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

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

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

3 結(jié)束語

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

圖2 基本發(fā)送方式網(wǎng)絡(luò)歸一化飽和吞吐量Fig 2 Normalized system throughput of basic access scheme

圖3 RTS/CTS方式網(wǎng)絡(luò)歸一化飽和吞吐量Fig 3 Normalized system throughput of RTS/CTS access scheme

圖4 基本發(fā)送方式平均接入時延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] 李運鵬,徐昌彪,劉 琳.無線傳感器網(wǎng)絡(luò)中一種競爭窗口自

適應(yīng)MAC協(xié)議[J].傳感器與微系統(tǒng),2010,29(1):49-54.

[4] 劉云璐,蒲菊華,方維維,等.一種無線傳感器網(wǎng)絡(luò)MAC協(xié)議優(yōu)化算法[J].計算機學(xué)報,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協(xié)議性能分析[J].計算機研究與發(fā)展,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

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

TP 393

A

1000—9787(2016)07—0143—04

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