IEEE802.15.4標準的自適應GTS調度機制

楊鵬飛,王申濤,文玉強,趙 林

(重慶通信學院 信息工程系,重慶 400035)

IEEE802.15.4標準的自適應GTS調度機制

楊鵬飛,王申濤,文玉強,趙 林

(重慶通信學院 信息工程系,重慶 400035)

介紹了IEEE 802.15.4協議的GTS調度機制。基于現有的IEEE802.15.4MAC協議，提出了一種針對傳輸時延和公平性問題的自適應GTS調度(Adaptive GTS Allocation,AGA)算法。建立相應的自適應GTS仿真模型，對GTS算法的性能進行評估，并用網絡演算理論對GTS進行理論分析。結果表明，提出的GTS調度機制在傳輸時延和公平性上明顯優于現有的GTS調度方案。

IEEE802.15.4；保障時隙；時延；自適應；公平性

0 引言

無線個域網(Wireless Personal Area Networks，WPANs)是以一個人的工作區為中心進行無線連接的無線網絡，最近新興的短程、低速率無線設備使得無線個域網發展迅速[1]。對此，IEEE組織針對低速率無線個人區域網(Low-Rate Wireless Personal Area Network,LRWPAN)制定了IEEE802.15.4標準。

IEEE802.15.4標準以超低的復雜性、低成本、低能耗和低速率為出發點，為廉價、便攜和可移動的設備提供低速率無線連接[2]。為了支持重復性低延遲應用所需的時延敏感數據傳輸，IEEE 802.15.4提供保障時隙(Guaranteed Time Slot，GTS)機制對一個超幀內的時隙進行分配，從而完成時延敏感數據幀的傳輸。IEEE802.15.4標準使用先來先服務[3]的GTS分配機制，無法靈活地應對網絡工作負載和應用需求。雖然專用帶寬可以保證數據傳輸的可靠性和性能,但專用資源的濫用也導致其他傳輸的沖突，某些節點還會出現饑餓現象。

1 IEEE802.15.4MAC協議

IEEE802.15.4標準定義了低速無線個域網(Low Rate-Wireless Personal Networks，LR-WPANs)的物理層和MAC層[2]，包含2種介質接入模式：信標使能模式(beacon-enabled mode)和非信標使能模式(nonbeacon-enabled mode)[4]。在非信標使能模式下，設備使用CSMA/CA機制競爭訪問信道；在信標使能模式下，設備除了使用CSMA/CA機制外，還提供了自由競爭的保障時隙(Guaranteed Time Slot，GTS)信道接入方式來實現時延敏感數據的傳輸。本文著重IEEE802.15.4的信標使能模式，圖1為IEEE802.15.4信標使能模式的超幀結構。

圖1 IEEE802.15.4標準的超幀結構

在信標使能模式下，PAN協調器周期性產生信標，2個連續的信標及其之間的時隙即為超幀，超幀分為活躍期和非活躍期：在活躍期，PAN協調器和設備之間可以互相通信；在非活躍期，PAN中所有節點進入休眠模式，停止通信[4]。超幀的持續時間為15 ms到245 s，超幀長度(Beacon Interval，BI)和超幀活躍期長度(Superframe Duration,SD)由2個參數來確定：信標參數(Beacon Order，BO)和超幀參數(Superframe Order，SO)，BO決定超幀的長度，SO決定超幀中活躍期的長度。BI和SD定義如下：

BI=aBaseSuperframeDuration*2BO,0≤BO≤14，

(1)

SD=aBaseSuperframeDuration*2SO,0≤SO≤BO≤14。

(2)

活躍期被分為16個時隙，它由3部分組成：信標、競爭訪問時段(Contention Access Period，CAP)和非競爭訪問時段(Contention Free Period，CFP)[5]。在CAP中，設備使用時隙CSMA/CA機制接入信道，CAP主要負責傳輸對時延要求不高的數據幀和MAC命令幀。

對于那些需要專用帶寬進行傳輸的設備，IEEE802.15.4標準提供了CFP時段進行低時延傳輸[6]。CFP的長度和GTS的調度由PAN協調器負責。CFP的長度取決于請求GTS分配的設備數量和超幀的現有可用容量，如果超幀內有足夠空間，PAN協調器最多可以一次性調度7個GTS[7]。

設備若需要新的GTS調度來進行數據傳輸，則會在CAP時段向PAN協調器發送GTS請求命令，PAN協調器收到GTS請求后首先會檢查當前超幀中是否有足夠容量[8]。IEEE802.15.4標準使用一個固定的定時器來限制GTS的使用時間。設備由PAN協調器分配的GTS一旦在2*n個超級幀的時間內沒有使用，PAN協調器就會收回分配給這些設備的GTS帶寬[9]。n的定義如下：

(3)

2 自適應GTS調度方案

本節提出了一個針對時延和公平性的IEEE802.15.4自適應GTS調度方案。如圖2所示，GTS的調度由PAN協調器控制，發生在星型網絡拓撲結構中。星形拓撲結構的通信方式是集中式的，即每個加入該網絡的設備若想要與其他設備之間通信就必須將其數據發送給 PAN協調器，協調器再分派數據給其他的目標設備[10]。PAN協調器通過周期性的發送信標幀以保障周圍設備的GTS描述符的更新，它最多可以跟255個設備進行通信。

圖2 WPAN中的星型拓撲結構

理想的GTS分配方案應該能較好地預估GTS傳輸設備的未來行為，PAN協調器通過預測信道情況，將GTS資源調度給有需求的設備，并回收先前已分配但現已不再使用的GTS資源。本文提出的自適應GTS調度方案有2個階段：分類階段和GTS調度階段。在分類階段，PAN協調器將根據最近的GTS使用反饋情況動態地將優先級分配給各個設備，對于那些需要PAN協調器更多注意的設備，PAN協調器將分配給它們更高的優先級；在GTS調度階段，GTS按優先級非遞減的順序分配給各個設備，對于那些優先級較低且需要GTS進行數據傳輸的設備，使用饑餓避免機制保障設備的數據傳輸。在這里定義2個術語：GTS狀態和非GTS狀態。如果一個設備在CAP時段已發出GTS請求或正通過調度GTS向PAN協調器傳輸數據，則稱其在GTS狀態(GTS hit)；反之，則稱其在非GTS狀態(GTS miss)。

2.1 設備分類階段

在這個階段,每個設備適應性地被劃分為一個狀態,并根據過去的GTS的使用反饋情況動態地分配一個優先級。假設WPAN中有N個設備，有M+1(0,1，…,M)個優先級動態的分配給N個設備。設備的優先級編號越大，則其GTS調度的優先級越低。分配給設備n的優先級編號記作Prin，則0≤Prin≤M。在自適應GTS方案中，優先級較高的設備短期預計將有更多的通信量，從而在之后的超幀中有更高的概率來傳輸它們的數據[11]。設備的狀態和優先級編號由PAN協調器確定，PAN協調器對設備的狀態和優先級的控制是基于動態分支預測和控制網絡擁塞的加性增，乘性減(Additive Increase Multiplicative Decrease，AIMD)算法，并做了一些改進，具體情況如下：

① 狀態轉換：如圖3所示，在改進GTS方案中，所有設備被分為4個通信量等級，4個流量等級的設備分別對應4個狀態，即高通信量(High Heavy，HH),較高通信量(Low Heavy，LH),較低通信量(High Light，HL)和低通信量(Low Light，LL)，這4個狀態的通信量等級順序為HH>LH>HL>LL。初始狀態下，所有的設備都為LL狀態。每個超幀結束時，PAN協調器檢查所有設備的GTS使用情況，之后決定設備的狀態。設備狀態的轉換如圖3中實線和虛線所示，實線和虛線分別代表GTS狀態和非GTS狀態。如狀態圖標所示，更頻繁使用GTS的設備有更大概率處于HH、LH這樣的高通信量狀態。而通過連續的GTS請求和GTS調用，LL狀態的設備也可以升至更高流量狀態。

圖3 改進GTS算法中設備的狀態轉移圖

在原有IEEE802.15.4規范中，新設備想要使用GTS進行數據傳輸，需要在高優先級設備使用GTS傳輸結束后再等待2n個超級幀的時間才能對GTS進行重新調用。這種被動解除GTS資源的調動方案會導致低通信量狀態的設備長時間無法調用GTS資源。通過應用改進的GTS方案，低通信量狀態的設備可以通過發送GTS請求將設備提升至高通信量狀態，有效避免此類情況的發生。

② 優先級分配：通過使用上面的狀態圖，PAN協調器可以監視設備最近的傳輸行為，并將按通信量對設備進行適當地分類。可以對圖3中的狀態圖進行進一步的修改，使得每個設備可以進行GTS優先級的動態分配，充分利用GTS資源。設備優先級編號的管理取決于傳輸反饋和設備的通信量等級狀態，維持設備優先級編號的細節如下。

與純粹地使用AIMD算法的優先級分配機制相比，本文方案提供了多層次的AIMD算法可以隨時更新設備的優先級編號，編號的更新取決于設備的通信量等級狀態。一方面，高優先級設備如果臨時中斷GTS的使用，它將會降格為較低優先級；另一方面，如果一個低優先級的設備開始請求GTS服務來傳輸數據,其優先級將大大提升，PAN協調器會為其盡快提供GTS服務，可以有效避免如低優先級的設備無法獲取GTS調度的現象。本文優先級分配重點是設備否有連續的數據通過GTS進行傳輸。此方案對于連續傳輸數據的設備有利，但對于已閑置一段時間的設備，可認為其不需要GTS服務，從而降低此類設備的優先級。

由圖3可知，如果設備n在HH狀態一直使用GTS服務然后偶然間停止使用GTS，它的優先級編號Prin會增加1。一旦設備n在接下來的超幀中繼續請求GTS服務，且其傳輸的數據是連續的，設備n增加的優先級數目會以指數方式減半，這樣設備n的優先級可以迅速的“恢復”。假設有設備k在LL狀態下，若其進行連續的GTS數據傳輸，優先級就會如設備n一般迅速的提升。但是，若設備k只進行了一次GTS傳輸，隨后停止傳輸數據，設備k的優先級的降級會比設備n快得多。為設備進行分類可以防止低優先級設備無法進行GTS傳輸，同時在高通信量等級的設備偶然終端通信時維持GTS服務的穩定。

2.2 GTS調度階段

在PAN協調器管理下，WPAN中所有設備的GTS調度優先級分配在設備分類階段已經完成。接下來，在GTS調度階段，GTS資源被調度給各個設備。調度標準是基于各設備的優先級編號，超幀長度和超幀中GTS容量。GTS調度算法如程序1所示。

程序1 DEVICE SCHEDULING

① 假設WAPN中有N個設備,

②P={Pri1,Pri2,… ,PriN},

③Th=MRBO其中M和R為常數,

④ while GTS容量未過載do,

⑤ 尋找設備k，Prik∈P是集合P中最小值,

⑥ ifPrik≤Ththen,

⑦ 設備k在當前超幀中進行GTS調度,

⑧ 將Prik從集合P中移除,

⑨ else,

⑩ break,

假設WPAN中有N個設備，P為N個設備的優先級編號的集合。在程序1中，PAN協調器首先檢查GTS容量是否過載，超幀中GTS容量贏滿足一下兩個要求：① 提供GTS服務的GTS時隙數目最多為7。② CAP最小長度為aMinCAPLength，總GTS時長的增加不會導致CAP長度小于aMinCAPLength。

如果滿足以上要求，GTS容量就沒有過載。假設有足夠GTS資源來容納更多的設備，則執行5～11行的WHILE循環。在WHILE循環的每次迭代中，選出P中最小值(設備k的優先級編號)Prik，比較Prik與動態閾值Th的大小。Th定義如下：

Th=MRBO，

(1)

式中，M為最大優先級編號，R為常數且0

這里給出閾值Th是考慮到λ的通信量負荷。當通信量負荷較輕即大多數設備優先級編號較高時，沒有必要為設備分配太多GTS資源。這種情況下將太多專用帶寬用于GTS傳輸會導致資源浪費，甚至影響系統的總體性能。因此此時應將GTS帶寬轉移到基于競爭機制的CAP時段。為此，PAN協調區必須檢測GTS通信量并使用閾值Th取消不必要的GTS調度。由式(1)可知，Th的值由M、R和BO決定。隨著信標間隔的增大，設備請求GTS調度的概率也會相應增加。基于優先級分配機制，請求GTS調度的設備即使只進行一次GTS調度請求，它們也會分配到較小的優先級編號。為了不將稀缺的GTS資源分配給那些極少發送GTS調度請求的設備，需要更精確的閾值。這種情況下，Th的值應遠小于M。而當超幀長度BI較小時，Th的值可以增大，設備選擇的限制可以更加寬松。基于上述論證，若Prik≤Th(程序第6行)，則在當前超幀中調度GTS給設備k。

3 性能分析

本節中，建立了一個GTS的仿真模型來對提出的自適應GTS調度(AGA)算法進行評估。仿真遵循IEEE802.15.4MAC協議的規范，并進行數學分析驗證。為了不失普遍性的考慮，進行了以下假設來降低仿真模型的復雜度：① 只考慮GTS業務量；② 不考慮GTS重傳的事例；③ 只接受用于上行業務的傳輸GTS。

在仿真模型中，采用星型拓撲結構，網絡中有10個設備其中1個為PAN協調器。每次仿真運行10 000個BI(即49 152 s)。每個設備的分組到達都為泊松分組到達，到達頻率為λ。分別考慮業務量大和業務量小的2種業務類型，λh和λl分別對應以上2種情況的到達頻率。仿真中，設λh=0.3/s,λl=0.1/s。因為IEEE802.15.4標準為低速率無線通訊協議，所以在基于802.15.4標準的WPAN中λ的取值是合理的。設業務量大的設備數目與所有設備數目的比值為v。表1為仿真模型的輸入參數。

表1 主要仿真參數

至于輸出量，分組平均等待時間為AGA算法中的一個重要指標。此外，使用公平指數F(分組等待次數)來衡量不同狀態的設備的公平性。F定義為：

(2)

式中，N為網絡中設備的總數量，Wi為設備i的分組平均等待時間。在式(2)中，0≤F≤1。當所有設備的平均等待次數相近時，F值趨近于1。反之，若Wi的值差別較大，F值趨近于1。因此F值越大，表明設備在獲得GTS帶寬上就越公平，饑餓現象就越不可能發生。

圖4和圖5為AGA方案和原802.15.4標準中，v(業務量大的設備數占總設備數的百分比)對分組平均等待時間和公平性的影響。

圖4 平均等待時間

圖5 GTS調度的公平性

由圖4可知，在原有GTS算法中，隨著v的增加，平均等待時間顯著增加。這是因為原GTS算法的GTS調度遵循先進先服務的原則，無法處理快速增加的負載。原GTS算法中，平均等待時間增加是因為業務量大的設備長期占據GTS的結果。另一方面，提出的改進的GTS算法，它的平均等待時延要遠小于原GTS算法。

圖5中公平性曲線可以進一步解釋為什么原GTS算法的平均等待時間迅速增加。圖5表明當80%≤v≤90%時，原IEEE802.15.4算法中會出現嚴重的不公平現象，即大多數GTS資源被分配給了業務量大的設備，業務量小的設備可能會發生饑餓現象。但是改進的GTS算法可以將平均等待時間維持在一個較小的值，并為所有設備提供更加公平的GTS傳輸。

4 結束語

在IEEE802.15.4標準的WPAN網絡中，為提高信標使能模式下GTS調度機制的性能，針對時延和公平性提出了一個新的GTS調度算法。改進了原有的FCFS調度算法，將節點按優先級進行分配，優先級大小由AIMD算法決定，避免某些節點長時間占用信道，影響傳輸公平性。仿真結果表明，該改進算法提高了GTS調度算法的公平性，降低了傳輸時延。

[1] Gutierrez J A.On the use of IEEE 802.15.4 to Enable Wireless Sensor Networks in Building Automation[C]∥IEEE International Symposium on Personal,Indoor and Mobile Radio Communications,2004:295-301.

[2] Zhang X.15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-rate Wireless Personal Area Networks (WPANs)[C]∥ Ansi/ieee,Standard 80,2006:110-115.

[3] Kishimoto Y,Kato S.Optimization of IEEE 802.15.4: Overview,Theoretical Study and Simulation[J].International Journal of Information & Communication Technology,2014,(1):412-418.

[4] Koubaa A,Alves M,Tovar E.IEEE 802.15.4 for Wireless Sensor Networks: A Technical Overview[J].IPP-Hurray Group,2008,39(1):169-204.

[5] Callaway E,Gorday P,Hester L,et al.Home Networking with IEEE 802.15.4: a Developing Standard for Low-rate Wireless Personal Area Networks[J].Communications Magazine IEEE,2002,40(8):70-77.

[6] Salman N,Rasool I,Kemp A H.Overview of the IEEE 802.15.4 Standards Family for Low Rate Wireless Personal Area Networks[C]∥ International Symposium on Wireless Communication Systems,IEEE,2010:701-705.

[7] De Nardis L,Benedetto M D.Overview of the IEEE 802.15.4/4a Standards for Low Data Rate Wireless Personal Data Networks[C]∥ Positioning,Navigation and Communication,2007.Wpnc’07.Workshop on,IEEE,2007:285-289.

[8] Yoo S,Kim D,Pham M L,et al.Scheduling Support for Guaranteed Time Services in IEEE 802.15.4 Low Rate WPAN[C]∥ IEEE International Conference on Embedded & Real-time Computing Systems & Applications,IEEE,2005:400-406.

[9] 802.15.4-2003 IEEE Standard for Information Technology-Part 15.4:Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-rate Wireless Personal Area Networks (LR-WPANs)[S],2003.

[10]Baronti P,Pillai P,Chook V W C,et al.Wireless Sensor Networks: A Survey on the State of the Art and the 802.15.4 and ZigBeestandards[J].Computer Communications,2007,30(7):1655-1695.

[11]Lu G,Krishnamachari B,Raghavendra C S.Performance Evaluation of the IEEE 802.15.4 MAC for Low-rate Low-power Wireless Networks[C]∥ IEEE International Conference on Performance,Computing,and Communications，2004:701-706.

Adaptive GTS Allocation with Latency and Fairness Considerations for IEEE 802.15.4

YANG Peng-fei,WANG Shen-tao,WEN Yu-qiang,ZHAO Lin

(Information Engineering Department of Chongqing CommunicationsInstitute,Chongqing400035,China)

This paper mainly describes the GTS mechanism in IEEE802.15.4 standard.Based on the existing IEEE 802.15.4 MAC protocol,an adaptive GTS allocation scheme is proposed with the consideration of low-latency and fairness.The simulation model and mathematical model of GTS mechanism are established to evaluate the performance of the adaptive GTS allocation scheme.Results show that the proposed GTS scheme outperforms the existing IEEE802.15.4 GTS scheme.

IEEE802.15.4;Guaranteed Time Slot;delay；arrival rate；burst size

10.3969/j.issn.1003-3114.2017.01.15

楊鵬飛,王申濤,文玉強，等.IEEE802.15.4標準的自適應GTS調度機制[J].無線電通信技術,2017,43(1):60-64.

2016-09-26

楊鵬飛(1991—)，男，碩士研究生，主要研究方向：無線傳感器網絡。王申濤(1980—)，男，碩士，主要研究方向：移動Ad Hoc網絡。

TN92

A

1003-3114(2017)01-60-5