基于預警優先級的ZigBee傳感網絡MAC層退避算法

梁利生,周國華,武蘭民,呂玉祥*

(1.太原理工大學物理與光電工程學院,太原 030024;2.山西省電力公司大同供電分公司,山西 大同 037008;3.國家電網公司,北京 100031)

?

基于預警優先級的ZigBee傳感網絡MAC層退避算法

梁利生1,周國華2,武蘭民3,呂玉祥1*

(1.太原理工大學物理與光電工程學院,太原 030024;2.山西省電力公司大同供電分公司,山西 大同 037008;3.國家電網公司,北京 100031)

摘要:針對無線傳感器網絡中有預警信息的高優先級數據包需要盡快傳輸,且IEEE 802.15.4協議本身不支持任何優先級傳輸機制的情況,提出了一種基于預警優先級的非時隙CSMA/CA自適應調整階梯退避算法,并建立了離散時間馬爾可夫分析模型,比較分析了網絡中不同優先級節點的信道接入概率、網絡吞吐量和傳輸延時,仿真結果表明,改進的自適應調整階梯退避機制對提高無線傳感器網絡中高優先級數據包的實時傳輸性能具有積極的作用。

關鍵詞:IEEE 802.15.4;非時隙CSMA/CA;馬爾可夫鏈;退避算法;ZigBee

無線傳感網絡是一種綜合信息采集、信息處理和信息傳輸功能于一體的智能網絡信息系統[1]。2002年,IEEE開始研究制定低速個域網標準——IEEE 802.15.4。該標準針對低速無線個人區域網絡LR-WPAN(Low-Rate Wireless Personal Area Network)制定了物理層和MAC子層協議。MAC層使用沖突避免的載波多路偵聽技術CSMA-CA(Carrier Sense Multiple Access with Collision Avoidance)機制解決多個網絡節點同時訪問信道時的沖突。利用ZigBee技術組建的LR-WPAN應用在很多場合,如大型電力設備運輸使用ZigBee傳感器網絡實時監測系統,網絡中每個監測節點實時發送監測數據,使駕駛人員正確判斷設備的狀態,可以避免發生嚴重事故。

在2000年,文獻[2]提出了到目前為止對IEEE 802.11分布式協調功能(DCF)研究相對深入的Bianchi模型,假定數據包傳輸的碰撞概率不變,但不考慮節點已經碰撞的次數,使無線網絡中的每一個節點的狀態形成離散時間的馬爾可夫鏈。文獻[3]建立了單個節點在信道中的傳輸狀態模型,假設IEEE 802.15.4協議中時隙CSMA/CA在退避階段的等待時間服從均值相同的幾何分布,并用相關離散時間的馬爾可夫鏈分析了該節點的傳輸性能。文獻[4]中節點通過退避計數器遞減檢測信道來確定信道的狀態,使用IEEE 802.15.4信道接入機制和IEEE 802.11中的二進制指數退避(BEB)機制相結合的混合信道接入機制,該機制訪問信道的概率較高,但所消耗的能量遠遠高于只采用IEEE 802.15.4信道接入機制。文獻[5]中對執行一次和兩次CCA(Clear Channel Assessment)的情況建立不同的數學分析模型,分析了網絡中節點的丟包率和吞吐量。文獻[6]將網絡中節點數據分為不同的優先級,按優先級設置退避指數和CCA次數,提高了數據包的延時性能。文獻[7]中雖然為IEEE 802.15.4協議建立了精確的數學分析模型,但無法分析優先級的無線網絡性能。文獻[8]中采用OPNET仿真軟件分析了用優先級處理數據的性能,對有優先級的數據,設置較小的EB值,而對沒有優先級的數據,設置較大的EB和LCW,該機制能較好地提高優先級數據的實時性。雖然調整EB和LCW的值可以使高優先級數據的及時發送,但不同的優先級數據退避時間會有交叉,低優先級數據有可能優先發送,本文提出的階梯退避算法可以避免這種情況。文獻[9]使高優先級數據節點只執行一次CCA,以避免數據幀和ACK幀之間的沖突。文獻[10]研究了網絡中不同節點數對網絡性能的影響。

基于以上分析,本文根據網絡節點間數據通信的類型和屬性,將ZigBee傳感網絡的傳感器節點分為正常、預警和報警3種級別。IEEE 802.15.4協議本身不支持任何優先級傳輸機制,為保證ZigBee無線傳感網絡中有預警信息的高優先級數據包盡快傳輸,本文提出了一種基于預警優先級的非時隙CSMA/CA信道接入機制和自適應階梯退避算法,并對具有預警優先級的非時隙CSMA/CA機制建立馬爾可夫分析模型。通過比較分析信道接入概率、網絡流量和接入延時,本文改進的機制對提高網絡中高優先級數據包的實時傳輸性能具有積極作用。

1　IEEE 802.15.4非時隙CSMA/CA算法

1.1非時隙CAMA/CA機制簡介

IEEE 802.15.4規定的MAC層協議中,無線信道同一時刻只能容納一個節點發送數據,網絡中若有多節點需要同時發送數據,為避免發生碰撞丟失數據[11],則各節點需要通過CSMA/CA機制競爭接入信道。在非時隙CSMA/CA機制中,當節點需要發送數據時,先執行信道掃描(CCA)確定網絡中是否有其他節點占用該信道,如果有節點占用信道,則隨機產生一個一定范圍內的退避周期,防止多個節點同時發送數據造成碰撞,節點到達退避周期后再執行一次CCA監測無線信道的使用情況,從而決定是否需要發送數據。

在CSMA/CA算法中,每個節點需要有3個變量去維護:NB、LCW和EB。NB(the Number of Back-offs)是在執行當前發送任務時,實現CSMA/CA算法需要進行退避的次數,在開始一次新的算法過程時被置為0。當節點隨機退避完成后,檢測到信道為忙時NB的值加1;若NB超過最大值,則發送失敗。LCWL(Content Window Length)是競爭窗口長度,以backs off為單位,是開始傳送信息之前連續檢測到信道空閑的次數,每次CSMA/CA算法開始時被初始化為2。EB(the Back-off Exponent)是退避指數,與節點在使用信道進行發送信息之前需要等待的退避周期有關。

通過研究IEEE 802.15.4的非時隙CSMA/CA機制[12],發現EB的初始設置將影響平均延時時間。當發生碰撞時,退避時間Time of Back-off為[0,2EB-1]范圍內的隨機值。在對于碰撞頻繁的網絡增加BE的值可以減少碰撞,但各節點會增加相應的傳輸延時,尤其在考慮用優先級處理的應用系統中,高優先級的重要數據因長時間延遲不能及時發送。

1.2預警優先級非時隙CSMA/CA機制退避算法

在ZigBee傳感器網絡實時監測系統中,有些監測數據(如預警數據)比較重要,預警信號可以預告危險信息,避免危險在不知情的情況下發生。為了滿足實時監測系統的應用需求,將監測數據優先級分類,預警數據對實時性和可靠性要求較高,所以預警數據用較高的優先級,設置較短的退避時間。而對實時性和可靠性要求相對較低的正常數據,將用低優先級處理,設置較長的退避時間。

本文中,用EB[q]來表示EB的值,q表示優先級級別。用q=0,1和2,分別表示優先級由高到低的報警數據,預警數據和正常數據,即正常數據的EB值為,EB=EB[2]。為了保證高優先級的數據優先傳輸,應該使EB[0]

c(q)～(2EB[q]-1,2EB[q]-1),q∈N

(1)

式中各優先級數據的退避周期c(q)服從均勻分布,q表示優先級級別。令EB=EB[0]=1,則c(q)～(20,21-1);令EB=EB[1]=2,則c(q)～(21,22-1-1);由式(1)可知,不同優先級EB值不同時,退避周期不會交叉,可降低不同優先級數據之間的碰撞。

1.3具有優先級的非時隙CSMA/CA機制算法流程

具有優先級的CSMA/CA機制如圖1分為5步:

(1)首先網絡中各節點判斷是否有高優先級數據包存在,根據不同的優先級來初始化節點MAC層的NB和EB參數。

(2)節點根據優先級的不同根據EB參數在MAC層產生[2EB[q]-1,2EB[q]-1]范圍內一個隨機的退避周期,完成退避后轉入第3步。

(3)執行CCA檢測信道狀態,CCA偵聽信道為忙,轉入第4步;CCA偵聽信道為空閑,轉入第5步。

(4)若信道不為空,則NB和EB的值各加1,如果NBmacMaxCSMABackoffs,則節點停止執行CSMA/CA機制并將發送數據的失敗信息返回給上層,由上層指示是否重新傳輸該數據。若信道為空,則轉入第5步。

(5)節點檢測信道為空后,將在執行完c(q)的下一個退避周期的邊界上開始傳輸數據。

圖1　CSMA/CA階梯退避算法流程

2　階梯退避算法馬爾可夫鏈分析模型

假設有n臺設備競爭信道,具有優先級l的設備數為nl,每個節點通過非時隙CSMA/CA競爭信道,假設節點一次只有一個數據包要發送,且在這個數據包發送完成后短時間不再產生新的數據包。在實際應用中數據包到達的服務時間是非常短的,所以這樣的假設的正確的。

圖2　CSMA/CA階梯退避算法節點馬爾可夫模型

為了有效分析本文提出的預警模型,引進基于優先級的3個隨機變量,即n(q,t),s(q,t)和b(q,t)分別表示t時刻設備的NB,設備掃描信道的次數和設備后退計數器數值。其中0≤n(q,t)≤m,m=macMaxCSMABackoffs-1。具有優先級設備的數量為Q+1,每個節點數據包在退避階段的狀態{n(q,t),s(q,t),b(q,t)}組成一個如圖2的馬爾可夫過程,假設網絡中具有優先級的設備數不變,則n(q,t),s(q,t)和b(q,t)可以簡化為n(t),s(t)和b(t)。對應的狀態空間可表示為:

Ω={n(t),s(t),b(t)|0≤n(t)≤m+1,0≤s(t)≤q,

0≤b(t)≤Wi-1,i=0,…,m}

(2)

其中W0=2BE[q],Wi=2iW0。

為了簡化運算符號,將每個節點的傳輸概率P(i,j,k-1|i,j,k)表示為:

(3)

由馬爾可夫過程可知,每個節點單步傳輸概率可用式(4)～式(8)表示:

(4)

(5)

P(i,q,k-1|i,q,k)=1,i∈[0,m],k∈[0,Wi-1]

(6)

P(i,j-1,0|i,j,0)=p,i∈[0,m],j∈[0,q]

(7)

(8)

定義每個節點在狀態{n(t),s(t),b(t)}下的馬爾可夫穩態概率為bi,j,k,則:

(9)

其中i∈[0,m+1],j∈[0,q],k∈[0,2BE-1]

則節點在各個狀態的穩態概率可表示為:

(10)

由節點的所有狀態和為1,可得公式:

(11)

由式(11)可推出節點穩態概率b0,0,0

b0,0,0=2pq/{3-2(1-pq)m+1+3W0(1-pq)2(1-2m(1-

pq)m)/(2pq-1)+2(1-pq)m+2+

2pq(1-pq-1)/(1-p)}

(12)

將式(12)代入式(10)各個等式可求出{bi,j,k}。

若節點完成退避周期后檢測到信道為空,則表示該節點進入發送狀態,節點進入發送狀態的概率為:

(13)

(14)

3　性能指標分析

在非時隙CSMA/CA算法中主要的性能指標有信道接入概率、信號的吞吐量、接入時延、退避次數、功耗、丟包率和網絡流量等。在這里只討論丟包率、平均接入時延和網絡吞吐量。分析了發送不同優先級數據包節點的性能。

3.1網絡吞吐量

用ps表示任意一個設備成功發送數據的概率,用ps,q表示具有q優先級的節點成功發送數據的概率,則:

(15)

q∈[0,Q]

(16)

用pb表示設備掃描信道忙的概率:

(17)

用pc,q表示網絡中q優先級的節點發生碰撞的概率:

(18)

網絡中的吞吐量S定義為節點成功發送數據包的時間與消耗的總時間之比,可以得到不同優先級節點的網絡流量公式:

(19)

其中δ,L,TS,TC分別表示數據幀間隔,數據載荷長度,數據發送的時間和數據沖突占用的時間。其中,

式中TH,TE(L),SIFS,γ,tACK分別表示傳輸幀頭時間,傳輸幀載荷時間,SIFS時間,傳輸延時和傳輸ACK時間。

3.2平均延時

在本文中平均延時為節點產生數據到數據被接收或丟棄的時間。為了分析CSMA/CA機制中平均延時性能,用Di,j,k來表示數據包從狀態(i,j,k)開始成功傳輸或丟棄所需要的時間,Di,j,k是一個與優先級q有關的隨機變量。可得到成功發送一個數據包的延時的公式如下:

E(Di,0,0)=ps,qTs+pc,qTc=d0,i∈[0,m]

(20)

E(Di,q,k)=kδ+E(Di,q,k),i∈[0,m]

k∈[1,Wm-1]

(21)

(22)

則可以得出設備的平均延時:

(23)

3.3數據丟包率

在本文中假設,如果一個節點傳輸數據發生碰撞時,就將數據包丟棄,因此,節點的丟包率等于該節點發生碰撞的概率。節點的丟包率pd,q表示為:

(24)

4　仿真的結果與分析

本文使用NS2仿真工具作為網絡仿真平臺[15],根據以上建立的馬爾可夫鏈模型,仿真并分析階梯退避算法的性能,一個由n個節點構成的無線傳感網絡,有3種優先級設備,采用星型拓撲結構,節點范圍為50m×50m,節點傳輸數據時間為10min,為了分析階梯退避算法對網絡性能的影響,設置每個節點的最大退避次數為2,仿真參數如表1,為了簡化仿真并方便分析數據,假設數據包的長度固定,傳輸數據的時間為傳輸數據幀、2SIFS和ACK幀時間總和。

表1　NS2仿真參數

結合仿真參數在MATLAB中使用迭代法可以解得網絡吞吐量、網絡延時等參數。計算結果如表2和表3,仿真結果驗證了階梯退避算法模型的準確性。

表2　不同節點的網絡吞吐量

表3　不同節點的網絡延時

如圖3是不同優先級節點的EB[q]值對應的網絡的吞吐量,橫坐標代表每種優先級的節點數,縱坐標對應其網絡的吞吐量,由圖可知,不同的優先級節點的吞吐量隨著設備數的增多而減少,這是因為節點越多碰撞越頻繁,從而導致節點去執行退避算法進行退避。報警數據有最高的優先級和最小的EB值,EB的值越小,節點的退避周期就越短,占用信道的機率就越大,所以高優先級網絡吞吐量是低優先級網絡吞吐量的兩倍多。

圖3　不同節點的網絡吞吐量

如圖4是不同優先級節點對應的節點接入概率,由圖可知節點的接入概率隨著節點數量的增加而逐漸減少,在節點數較少的情況下,高優先級的節點接入概率明顯高于低優先級的節點接入概率。節點接入概率變化趨勢與吞吐量的變化趨勢相同,是因為節點傳輸數據的概率決定了網絡中設備的吞吐量。

圖4　不同節點的網絡接入概率

當節點接入信道成功時,只有一個節點在占用信道,如果有2個設備同時傳輸數據,則其中一個設備就會出現丟包。如圖5是不同優先級節點對應的丟包率曲線,顯然節點的丟包率隨著節點數的增加而變大。因為高優先級節點數據的EB值較小,所以在節點數一定的情況下,高優先級節點發生的碰撞概率較大,丟包率隨之增大。而低優先級節點在長時間的退避周期中發送碰撞的機率較小,所以丟包率降低。

圖5　不同節點的網絡丟包率

如圖6是網絡中不同優先級節點的平均延時,由圖可知,節點的平均延時隨著節點數的增加幾乎在線性增大。低優先級節點的平均延時明顯大于高優先級節點的平均延時。不同優先級的EB是連續變化的,階梯退避算法保證了高優先級數據的實時傳輸,所以正常數據的平均延時是預警數據的2倍,是報警數據平均延時的4倍。

圖6　不同節點的網絡延時

5　總結

ZigBee傳感網絡實時監測系統對網絡中節點的預警和報警數據實時性要求較高,本文提出了基于IEEE 802.15.4無線傳感網絡非時隙CAMA/CA的階梯退避算法,針對不同數據設置不同的優先級,選擇不同的退避周期,使高優先級的數據可以及時傳輸,并用離散時間馬爾可夫鏈數學模型分析了階梯退避算法的性能。運用NS2仿真軟件對階梯退避算法進行了仿真,仿真結果表面具有高優先級的報警數據在網絡中的節點接入率和吞吐量要比低優先級數據要高,但隨著節點數的增多,差異逐漸減小。階梯算法對不同優先級節點發送數據的平均延時影響非常顯著,報警數據的延時遠小于正常數據的延時。雖然高優先級數據節點的丟包率略高,但在無線傳感網絡中報警數據通常少,所以丟包率對網絡性能沒有顯著影響。總體而言,階梯退避算法對提高無線傳感網絡的實時性是非常有效的,可以應用于對有預警數據分析判斷的ZigBee無線傳感網絡實時監測系統。

參考文獻:

[1]孫利明,李建中,陳渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005.

[2]Bianchi G.Performance Analysis of the IEEE 802.11 Distributed Coordination Function[J].IEEE Journal on Selected Areas in Communications,2000,18(3):535-47.

[3]Ramachandran I,Das A K,Roy S.Analysis of the Contention Access Period of IEEE 802.15.4 MAC[J].ACM Transactions on Sensor Networks,2007,3(1):1-29.

[4]Saho P K,Sheu J P,Chang Y C.Performance Evaluation of Wireless Sensor Network with Hybrid Channel Access Mechanism[J].Journal of Network and Computer Applications,2009,32(4):878-888.

[5]Ranjeet K Patro,Manik Raina,Viswanath Ganapathy.Analysis and Improvement of Contention Access Protocol in IEEE 802.15.4 Star Network[C]//Mobile Ad Hoc and Sensor Systems,2007:1-8.

[6]Anis Koubaa,Mário Alves,Bilel Nefzi,et al.Improving the IEEE 802.15.4 Slotted CSMA/CA MAC for Time-Critical Events in Wireless Sensor Networks[C]//Proceedings of the Workshop of Real-Time Networks,2006:1-6.

[8]AnisKoubaa,Mdrio Aires,,et al.Improving the IEEE 802.15.4 Slotted CSMA/CA MAC for Time-Critical Events in Wireless Sensor Networks[C]//Proceedings of the Workshop of Real-Time Networks,2006:270-277.

[9]Kim T,Choi S.Priority-Based Delay Mitigation for Event-Monitoring IEEE 802.15.4 LR-WPANs[J].Communications Letters,IEEE.2006,10(3):213-215.

[10]Chen Zhijia,Lin Chuang,Wen Hao.An Analytical Model for Evaluating IEEE802.15.4 CSMA/CA Protocol in Low-Rate Wireless Application[C]//IEEE 21st International Conference on Advanced Information Networking and Applications Workshops,2007:899-904.

[11]呂治安.ZigBee網絡原理與應用開發[M].北京:北京航空航天大學出版社,2008.

[12]周明偉,樊曉平,劉少強.基于優先級的IEEE 802.15.4 CSMA/CA建模與分析[J].傳感技術學報,2009,29(3):422-426.

[13]黃仁,郜輝,任軍華.非飽和狀態下時隙CSMA/CA機制改進與性能分析[J].計算機工程與應用,2012,48(30):108-110.

[14]陳金,樊曉平,劉少強,等.非時隙CSMA/CA性能分析與研究[J/OL].http://www.cnki.net/kcms/detail/11.2127.tp.20110929.1036.033.html,2011-0929.

[15]趙志宏,李小珉,郭志.ZigBee無線傳感器網絡的研究與實驗[J].電子器件,2007,30(4):1503-1509.

[16]柯志亨,程榮祥,鄧德雋,等.NS2仿真實驗——多媒體和無線網絡通信[M].北京:電子工業出版社,2009.

梁利生(1988-),男,漢族,山西省呂梁市人。太原理工大學碩士研究生,主要研究方向無線傳感網絡,lianglisheng@foxmail.com;

呂玉祥(1964-),男,漢族,山西省呂梁市人。太原理工大學教授,碩士生導師,主要從事電力電子設備的開發與研究,lyx823@126.com。

TheEarly-WarningPriority-BasedZigBeeSensorNetworkMACLayerBackoffAlgorithm

LIANGLisheng1,ZHOUGuohua2,WULanming3,LüYuxiang1*

(1.College of Physics and Optoelectronics,Taiyuan University of Technology,Taiyuan 030024,China;2.Shanxi Datong Electric Power Supply Company,Datong Shanxi 037008,China;3.State Grid Corporation of China,Beijing 100031,China)

Abstract:The early warning information of high priority packets in wireless sensor network needs to be transmitted quickly.And IEEE 802.15.4 protocol doesn’t sustain any priority transmission mechanism.Based on this situation,an unslotted CSMA/CA adaptive adjustment of step backoff algorithm is proposed on early warning priority,and model Discrete time Markov analysis.Meanwhile,the channel access probability,network throughput and transmission delay are compared and analysed for the different priority nodes in network.Adaptive adjustment of the improved step backoff probability mechanism has positive effects on improving real time transmission performance of high priority packets in wireless network.

Key words:IEEE 802.15.4;unslotted CSMA/CA;Markov chain;backoff algorithm;ZigBee

doi:EEACC:6150P;723010.3969/j.issn.1005-9490.2014.05.030

中圖分類號:TN915.01

文獻標識碼:A

文章編號:1005-9490(2014)05-0937-07

收稿日期:2013-09-26修改日期:2013-10-20