基于幀服務時延的擁塞控制算法

馬新華， 楊俊清

(西安航空學院 計算機工程系， 陜西 西安710077)

基于幀服務時延的擁塞控制算法

馬新華， 楊俊清

(西安航空學院 計算機工程系， 陜西 西安710077)

針對無線傳感器網(wǎng)絡介質(zhì)訪問控制(MAC)層存在的擁塞問題，提出一種擁塞控制算法。利用IEEE802.15.4協(xié)議 MAC層幀服務時延對擁塞指示的有效性，在IEEE802.15.4協(xié)議的CSMA/CA算法中增加以幀服務時延為閥值的計時器，并根據(jù)計時器的值調(diào)整傳感器節(jié)點的發(fā)射速率，可達到對MAC層擁塞進行控制的目的。仿真結果表明，與傳統(tǒng)算法相比，網(wǎng)絡中有40個節(jié)點時，新算法對網(wǎng)絡擁塞大約有60%的改善。

介質(zhì)訪問控制;幀服務時延;擁塞控制;無線傳感器網(wǎng)絡

在現(xiàn)有的無線傳感器網(wǎng)絡擁塞控制算法中[1-6]，為了提前向下游節(jié)點通知擁塞，上游節(jié)點使用主動隊列管理(Active Queue Management, AQM)[7]來檢測擁塞，下游節(jié)點在接到擁塞通知后進行相應處理，雖然主動隊列管理技術在有線網(wǎng)絡中可以相對有效地解決網(wǎng)絡擁塞，但在無線傳感器網(wǎng)絡環(huán)境下，網(wǎng)絡的擁塞并不表現(xiàn)為隊列長度的增長，更多的表現(xiàn)為由于大量節(jié)點競爭信道而造成的介質(zhì)訪問控制(Media Access Control, MAC)層擁塞，這種擁塞發(fā)生在網(wǎng)絡層的擁塞之前，先于網(wǎng)絡層擁塞對無線傳感器網(wǎng)絡的時延產(chǎn)生影響。因此，在有線網(wǎng)絡中成熟的擁塞控制技術，在無線傳感器網(wǎng)絡中并不適用。

為了有效指示無線傳感器網(wǎng)絡擁塞，本文首先對IEEE802.15.4協(xié)議的MAC幀服務時延進行建模，研究MAC幀服務時延作為網(wǎng)絡擁塞指示的可行性和有效性，并將結果用于IEEE802.15.4協(xié)議中載波監(jiān)聽多路訪問/沖突檢測(Carrier Sense Multiple Access/Collision Detect, CSMA/CA)算法的改進中。

1 MAC幀服務時延模型

IEEE802.15.4協(xié)議是眾多無線傳感器MAC層和物理層協(xié)議中最有影響力的標準[8]，工作在信標使能模式和非信標使能模式下，由于非信標使能模式不使用超幀和信標，信道接入使用非時隙模式的CSMA/CA來實現(xiàn)，這種方式和其他的競爭型MAC協(xié)議相同，并不能體現(xiàn)802.15.4特性。信標使能模式采用時隙CSMA/CA機制作為信道接入方式，采用競爭期(Contention Access Period, CAP)和無競爭期(Contention-Free Period, CFP)兩種方式進行幀傳輸，CFP與傳統(tǒng)的時分多址(Time Division Multiple Access, TDMA)方式相同，且在實際的應用中以CAP方式為主，因此本文只考慮信標使能模式下的CAP方式。

CAP是IEEE802.15.4信標使能模式下的基本MAC協(xié)議，用于超幀的競爭期，在進行幀傳輸時采用CSMA/CA+確認(Acknowledgement, ACK)方式，任何需要發(fā)送的幀都使用時隙的CSMA/CA機制訪問信道，在幀傳輸后，如果在規(guī)定時間內(nèi)未收到MAC層的確認幀，則發(fā)送方認為該幀沖突或丟失，該幀會按照二進制指數(shù)退避算法進行退避和重傳。

圖1 TD的時延構成

節(jié)點有數(shù)據(jù)發(fā)送時，首先對退避參數(shù)進行初始化，計算隨機退避時間，退避時間結束后，進行消除信道評估，最后嘗試發(fā)送數(shù)據(jù)。如果發(fā)生沖突，重新計算隨機時間，在退避時間結束后，再次嘗試發(fā)送數(shù)據(jù)，這樣的過程一直達到最大重試次數(shù)C，或者傳送此幀成功為止。所以傳送的過程中，可能包含多次的沖突。

為計算幀服務時延，以隨機變量N(0

(1)

TCRi=TCWN+D′ (0

(2)

TTP=TCWN+1+TL+D(N≤C),

(3)

其中

D=TCCA+TACK+TSIFS+TLIFS,
D′=TCCA+TL+TSIFS,

服務時延TD的數(shù)學期望為

(4)

將式(2)(3)代入式(4)，由于

(5)

于是有

(6)

當節(jié)點有數(shù)據(jù)發(fā)送時，IEEE802.15.4協(xié)議的CSMA/CA算法先按均勻分布規(guī)則從(0，Wi-1)中隨機選取一個值作為退避時隙數(shù)，其中

Wi=2iWmin，i∈[0,m]，

而i為退避級數(shù)，m為最大退避級數(shù)，Wmin為最小退避窗口數(shù)。若退避級數(shù)到達最大時仍沒有發(fā)送成功，則Wm將維持2mWmin，直到達到最大重試次數(shù)C或發(fā)送成功為止。

節(jié)點第一次接入信道時，平均退避時間為

其中TE表示等效的時隙長度。第i次接入信道時，平均退避時間為

(7)

因此，只需確定TE和P{N=n}的分布，就可以確定服務時延TD的數(shù)學期望E(TD)。

假設網(wǎng)絡中有n個節(jié)點，除了當前節(jié)點傳輸外，其它節(jié)點至少有一個準備進行數(shù)據(jù)傳輸，每個節(jié)點發(fā)送幀的概率為τ，則發(fā)生沖突的概率

p=1- (1-τ)n-1，

(8)

于是節(jié)點發(fā)送幀時發(fā)生沖突的概率為[9]

(9)

從而節(jié)點傳送幀成功的概率

(10)

當節(jié)點處于退避時期時，考慮到信道空閑、傳輸成功和失敗的情況，一個等效的時隙長度為

TE=(1-p)δ+pTSPs+pTCPs,

(11)

其中δ為空閑時隙，表示系統(tǒng)固定時隙的長度,TS為成功發(fā)送數(shù)據(jù)包占用的平均時間,TC為發(fā)送數(shù)據(jù)失敗浪費的平均時間。

從式(11)可得

TS=TH+TEL+TSIFS+γ+TACK+TLIFS,

(12)

TC=TH+TEL+TSIFS+γ,

(13)

其中TH表示傳輸數(shù)據(jù)包頭的時間，包括MAC層包頭和物理層(Physical Layer, PHL)包頭，TEL表示每次沖突中傳輸平均最長負載的時間，γ表示數(shù)據(jù)傳播延遲。

隨機變量N服從幾何分布[9]，即

綜上可知，當m>C時，有

而當m

可見，TD與幀的發(fā)送時延TL、沖突概率p、系統(tǒng)參數(shù)m、C以及Wmin有關，而p則由節(jié)點發(fā)送數(shù)據(jù)的概率τ和飽和節(jié)點數(shù)量n決定,其中τ只與飽和節(jié)點的數(shù)量n以及參數(shù)最大退避級數(shù)m和最小退避窗口Wmin有關[8]，所以當系統(tǒng)參數(shù)一定時，平均幀服務時延TD只與幀的發(fā)送時延TL和飽和站的數(shù)量n有關。

2 服務模型仿真分析

當網(wǎng)絡發(fā)生擁塞時，一般會出現(xiàn)數(shù)據(jù)丟失，時延加大，吞吐量下降等現(xiàn)象[10]。為了驗證理論分析的有效性，分別對幀服務時間隨τ的變化以及隨飽和站點數(shù)的關系進行仿真。

所有節(jié)點均采用IEEE802.15.4協(xié)議，物理層采用直接序列擴頻，每個從節(jié)點以CSMA/CA方式競爭信道，并且所有節(jié)點發(fā)送數(shù)據(jù)幀長度均為127字節(jié)，最大嘗試次數(shù)C為4，最大退避級數(shù)m為5，仿真時間120 s。

幀服務時延隨τ變化情況如圖2所示，從中可見，相對于網(wǎng)絡中各節(jié)點的臨界發(fā)送概率τ*，當節(jié)點發(fā)送幀的概率τ≤τ*時，TD隨發(fā)送概率的增加而緩慢增大，當τ≥τ*時，TD隨τ的增加而急劇增大。若網(wǎng)絡經(jīng)常處于τ≥τ*時，將大大增加點到點時延，因而根據(jù)網(wǎng)絡情況適當調(diào)整τ，可以獲得較高吞吐量和較低時延的折中。

圖2 幀服務時延隨τ而變化

幀服務時延隨飽和站點數(shù)的變化情況如圖3所示，從中可見，當τ一定時，TD隨飽和站數(shù)據(jù)的增大而增大。當系統(tǒng)維持較高的τ時，TD隨飽和站的增加而快速增加，通常TD只與網(wǎng)絡中飽和站的數(shù)量、系統(tǒng)的參數(shù)m和Wmin有關，當部署節(jié)點時，m和Wmin一般不會改變，因此為了獲得較高吞吐量以及較低時延，另一個可行的方法是根據(jù)網(wǎng)絡狀況適當?shù)臏p少同一時間飽和站的數(shù)量。

圖3 幀服務時延隨飽和站點數(shù)而變化

3 擁塞控制算法

基于上面的分析，幀服務時延對信道的擁塞很敏感，因此采用TD做為節(jié)點擁塞指示，對CSMA/CA進行改進，改進的思路是在CSMA/CA中設置計時器，并在隨機退避開始階段系統(tǒng)開始計時，當計時器數(shù)據(jù)大于TD值時，節(jié)點自動降低發(fā)射速率，從而降低同一時間飽和節(jié)點數(shù)量。

算法流程改進部分的偽代碼如下。

Begin(算法開始)

{

……

隨機退避開始；

計時器開始計時(T)；

if T>TDthen 節(jié)點減速；

……

}

End (算法結束)

以TD做為擁塞指示信號的平均時延較采用平均隊長作為擁塞指示信號有了明顯的下降，結果如圖4所示。網(wǎng)絡中節(jié)點數(shù)越多，則改善的程度越明顯，當節(jié)點數(shù)為40時，時延大約減少60%。

圖4 采用TD做為擁塞指示信號前后時延比較

4 結語

針對無線傳感器網(wǎng)絡在網(wǎng)絡層擁塞發(fā)生之前由于大量節(jié)點競爭信道而造成的MAC層擁塞問題，建立了IEEE802.15.4協(xié)議幀服務時延TD模型，給出了TD與平均幀長、沖突概率以及飽和站數(shù)量之間的關系，當節(jié)點的傳輸概率大于臨界概率時，平均TD隨傳輸概率或飽和節(jié)點的數(shù)量的增大而急劇增大，顯示其對網(wǎng)絡擁塞較為敏感在網(wǎng)絡中存在發(fā)射的臨界概率。把TD作為擁塞信號指示，對CSMA/CA算法進行改進，仿真表明，TD作為無線傳感器網(wǎng)絡擁塞指示，在一定條件下能有效的減少網(wǎng)絡時延，提高網(wǎng)絡吞吐量。

[1] Hull B, Jamieson K, Balakrishnan H. Mitigating congestion in wireless sensor networks[C]//Proceeding of the 2nd ACM Conference on Embedded Networked Sensor Systems(SenSys). Baltimore: ACM Press, 2004:134-147.

[2] Wang Yunbo, Vuran M C, Goddard S. Cross-Layer Analysis of the End-to-End Delay Distribution in Wireless Sensor Networks[J]. IEEE/ACM Transactions on Networking,2012,20(1):305-318.

[3] Nath S, Gibbons P B. Communicating via fireflies: geographic routing on duty-cycled sensors[C]//International Conference on Information Processing in Sensor Networks (IPSN).Cambridge, MA:MIT Press,2007: 440-449.

[4] Gu Yu, He Tian. Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links[C]∥The ACM Conference on Embedded Networked Sensor Systems (Sensys). Penn Plaza:ACM Press, 2007:321-334.

[5] Shifrin M, Cidon I. C3: Collective Congestion Control in Multi-hop Wireless Networks[C]//Wireless On-demand Network Systems and Services. Kranjska Gora: IEEE Press, 2010:31-38.

[6] Teo J Y, Ha Y, Tham C K. Interference-minimized multipath routing with congestion control in wireless sensor network for high-rate streaming[J]. IEEE Transactions on Mobile Computing, 2008, 7(9): 1124-1137.

[7] Tinnakornsrisuphap P, La R J. Characterization of queue fluctuations in probabilistic AQM mechanisms[J]. ACM Journal on IGMETRICS Performance Evaluation Review, 2004,32(1):283-294.

[8] Standard for part 802. 15.4. Wireless medium access control (MAC) and physical layer (PHY) specifications for low rate wireless personal area networks (WPAN)[S]. 2003 ed, New York, NY: IEEE,2003:166-192.

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

[10] 馬新華.基于區(qū)分服務的無線傳感器網(wǎng)絡性能研究[J].西安郵電學院學報，2011,16(1):29-31.

[責任編輯:王輝]

Congestion control algorithm based on frame service delay

MA Xinhua, YANG Junqing

(Department of Computer Engineering, Xi’an Aeronautical University, Xi’an 710077, China)

An improved congestion control algorithm is proposed to solve the MAC layer congestion in wireless sensors network. The algorithm adds a timer in the CSMA/CA algorithm of IEEE802.15.4 protocol with frame service delay as its threshold due to the effectiveness of IEEE802.15.4 MAC layer frame service delay on the congestion indication. The MAC layer congestion can be controlled by a sensor node which adjusts launch rate based on the value of timer. Simulation result shows that the revised protocol can better indicate network congestion compared with the conventional way. The congestion is reduced by 60% on a network with 40 nodes.

media access control(MAC), frame service delay, congestion control, wireless sensors network

10.13682/j.issn.2095-6533.2014.01.019

2013-09-13

陜西省教育廳科學研究計劃基金資助項目(11JK1073)

馬新華(1978-),女，碩士，講師，從事無線傳感器網(wǎng)絡研究。E-mail:maxinhua922@163.com 楊俊清(1966-),男，教授，從事無線傳感器網(wǎng)絡研究。E-mail: yjqfive@163.com

TN915.04

A

2095-6533(2014)01-0086-04