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

馬新華， 楊俊清

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

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

馬新華， 楊俊清

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

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

介質訪問控制;幀服務時延;擁塞控制;無線傳感器網絡

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

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

1 MAC幀服務時延模型

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

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

圖1 TD的時延構成

節點有數據發送時，首先對退避參數進行初始化，計算隨機退避時間，退避時間結束后，進行消除信道評估，最后嘗試發送數據。如果發生沖突，重新計算隨機時間，在退避時間結束后，再次嘗試發送數據，這樣的過程一直達到最大重試次數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的數學期望為

(4)

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

(5)

于是有

(6)

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

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

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

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

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

(7)

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

假設網絡中有n個節點，除了當前節點傳輸外，其它節點至少有一個準備進行數據傳輸，每個節點發送幀的概率為τ，則發生沖突的概率

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

(8)

于是節點發送幀時發生沖突的概率為[9]

(9)

從而節點傳送幀成功的概率

(10)

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

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

(11)

其中δ為空閑時隙，表示系統固定時隙的長度,TS為成功發送數據包占用的平均時間,TC為發送數據失敗浪費的平均時間。

從式(11)可得

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

(12)

TC=TH+TEL+TSIFS+γ,

(13)

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

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

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

而當m

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

2 服務模型仿真分析

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

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

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

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

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

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

3 擁塞控制算法

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

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

Begin(算法開始)

{

……

隨機退避開始；

計時器開始計時(T)；

if T>TDthen 節點減速；

……

}

End (算法結束)

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

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

4 結語

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

[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] 馬新華.基于區分服務的無線傳感器網絡性能研究[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-),女，碩士，講師，從事無線傳感器網絡研究。E-mail:maxinhua922@163.com 楊俊清(1966-),男，教授，從事無線傳感器網絡研究。E-mail: yjqfive@163.com

TN915.04

A

2095-6533(2014)01-0086-04