多節點共享保障時隙分配策略*

范書瑞,閆 伸,高 蒙

(河北工業大學信息工程學院,天津 300401)

?

多節點共享保障時隙分配策略*

范書瑞*,閆 伸,高 蒙

(河北工業大學信息工程學院,天津 300401)

在現代工業無線網絡中,IEEE 802.15.4標準以其獨特的低功耗、低成本特點被廣泛應用。IEEE 802.15.4可以提供最低0.006%的占空比,最大限度降低功耗,同時提供的保障時隙GTS機制為節點提供了實時服務保障。然而,在為大規模節點提供保障時,IEEE 802.15.4提供的GTS機制缺乏靈活性,只能為有限節點提供實時保障服務。本文針對這一問題提出一種多節點共享保障時隙分配策略,允許多個數據流在滿足延遲需求前提下,共享同一個GTS減少帶寬浪費。分析表明,多節點共享的保障時隙分配策略與普通分配方法相比,可有效提高帶寬利用率。

工業無線網絡;保障時隙分配;實時服務;帶寬利用率

近年來,無線網絡技術快速發展,在實時性和可靠性方面取得進步,為其在工業的應用提供了可能。在傳感層采用無線措施是實現工業環境下物聯網的關鍵,現在主流的工業無線網絡技術主要解決現場通信問題。目前由IEC TC65推出的WirelessHART[1]、美國儀表系統與自動化協會ISA推出的ISA100.11a[2]和我國自主研發的WIA-PA[3]標準形成三足鼎立的局面。IEEE802.15.4標準則以其技術的合理性和先進性的統一,被廣泛應用于以上3個工業標準中。文獻[4]采用自觸發采樣策略減少網絡利用和能耗損耗的同時,確保了網絡性能。文獻[5]針對能量敏感問題設計了模型預測控制,確保WSN魯棒性。這些也都證明IEEE802.15.4適用于現代工業網絡控制系統。

IEEE802.15.4可以提供最低0.006%(1/214)的占空比,最大限度降低功耗,同時提供的GTS機制為節點提供了一種實時服務保障,滿足對時間敏感場合的應用,可預測每個應用節點的最糟糕性能。信標使能模式下,PAN協調器周期性的發送信標幀同步網絡,對請求實時保障的節點分配GTS。超幀最多可以分配7個GTS形成CFP階段,因此享用GTS保障的節點就不能超過7個,其余節點使用CSMA/CA協議競爭使用CAP階段。文獻[6]采用網絡演算方法研究有限的時隙資源分配,提高可享受保障服務的節點數,是一種最糟糕情況下的確定性能分析方法。文獻[7]對時隙CSMA/CA機制建模進行了分析,但是當高優先級節點較多時,依然不能避免CSMA/CA機制本身不可預測的弊端。為了滿足有嚴格傳輸時延期限要求場合的應用,文獻[8]提出自適應調整占空比的方法,文獻[9]提出保障時隙調度算法,這種兩種算法都需要設備節點掌握網絡全局信息,在網絡參數改變時應變力較差。文獻[10]提出一種多信標的超幀提高帶寬利用率,文獻[11]提出的時分信標調度TDBS(Time Division Beacon Scheduling)根據負載大小改變信標幀BI發送間隔,并且文獻[12]對TDBS的系統容量進行了分析,實際上就是改變了超幀結構,需要全局設備節點同步調整。

對大規模節點提供保障時,GTS機制缺乏靈活性,只能為有限節點提供實時保障服務。本文介紹一種共享GTS策略,允許多個數據流在滿足延遲需求前提下,共享同一個GTS。同時通過減少GTS帶寬浪費提高CFP利用,CFP長度最小化使得CAP最大化。共享GTS的關鍵就是分析給定數據流共享確定時隙的可調度性,并且不需要單獨考慮數據流周期信息,而是采用了一種更一般的到達曲線描述達到流量,是基于網絡演算的一種描述。

1 保障時隙帶寬利用與分配

IEEE 802.15.4在PAN協調器同步的星型拓撲基礎上,通過子協調器可以擴展出簇結構網絡,用于組建大規模傳感采集網絡。設定每個網絡節點i產生數據流Fi,受限于到達曲線ai(t)=bi+rit,其中bi是最大猝發數據大小,ri是平均到達速率,Di表示Fi的最大延遲需求。采用Fspec,i=(bi,ri,Di)表示數據流Fi。

RTS表示每個時隙的保障帶寬,RkTS表示分配了k個時隙GTS的保障帶寬:

RkTS=k·RTS

(1)

需要考慮的主要問題就是對N個數據流Fspec,i=(bi,ri,Di)的請求節點,如何公平的分配k個時隙。在保證網絡中設備節點傳輸時延界限要求的情況下,N個數據流共享k個時隙的GTS,必須滿足2個條件[12]:

條件1:

(2)

條件2:

Di,max≤Di,?1≤i≤N

條件1表示到達速率ri的總和不能超過k個時隙完整帶寬,條件2表示為每個數據流Fi分配的GTS延遲界限不能超過最大延遲需求。

1.1 專用GTS帶寬利用

考慮一個數據流Fi=(bi,ri,Di),對節點i分配ki個時隙的GTS,帶寬利用率定義為:

(3)

(4)

可分配的最小帶寬是由單個時隙提供的RTS,節點i要求分配ki個時隙的GTS,則GTS提供的保障帶寬和節點i的到達速率ri滿足:

(ki-1)·RTS

(5)

從式(1)、式(3)和式(5)可得:

(6)

所以,最小帶寬利用界限為[11]:

(7)

從圖1可以看出,分配一個時隙的GTS利用率最低。這是由于數據流的到達速率只是占用了不可分割帶寬RTS的很小一部分。所以考慮到達速率比較低的WSN中,在滿足數據流延遲要求的前提下,可以與其他節點共享時隙。

圖1 GTS帶寬最小利用率

1.2 提高帶寬利用的共享GTS分配

N個數據流總到達速率小于或等于GTS保障帶寬,就可以共享一個GTS。而主要問題是,在每個信標間隔BI間尋找適當的時隙分配調度,使為每個數據流提供的保障帶寬大于或等于它們的到達速率。循環調度RRS為GTS提供了一個比較平等的共享方式,為所有數據流提供了一個無任何差別的相同數目的保障帶寬。每個數據流到達速率需要共享的GTS小于平均GTS時RRS有效。N個數據流Fspec,i=(bi,ri,Di),i=1,…,N平均分配k個時隙的多個GTS,則:

(8)

各個數據流的到達速率一致時,平均共享GTS比較有效。共享GTS的每個數據流都要滿足式(2),與WSN中每個傳感器采用相同采樣速率的情況比較一致。為了簡便且不失一般性,分析一個時隙的數據流分配。原因有2點:WSN中的數據流產生速率比較低;單個時隙分配更能反映i-GAME方法。

根據共享GTS分配的定義,N個數據流Fspec,i=(bi,ri,Di),i=1,…,N分配k個時隙的GTS利用率:

(9)

GTS中單個數據流的利用率:

(10)

與專用分配一個時隙一致,共享GTS分配的到達速率ri≤RTS。問題簡化為,對k個時隙長的CFP,平均分配共享GTS,其中k≤N。在這種情況下,CFP長度不能超過7個時隙,因為最多可以分配7個GTS,每個GTS長度是1個時隙。

2 共享GTS分配舉例

假定IEEE802.15.4簇網絡中,PAN協調器設定超幀結構BO=SO=0,相應的BI=SD=15.36 ms,TSlot=0.96 ms和RTS=9.38 kbit/s。

對于速率是R,延遲時間為T的速率-延遲服務曲線一般描述為:

βR,T(t)=R·(t-T)+

(11)

對于n個時隙GTS提供的保障帶寬是Rn,延遲時間是Tn,可知提供的速率-延遲服務曲線是:

βRn,Tn(t)=Rn·(t-Tn)

(12)

(13)

保障服務的等待時間:

Tn=BI-n·Tslot

(14)

可得n個時隙GTS的延遲上界

(15)

2.1 1個節點調度實例

設定節點A產生數據流FA受限到達曲線aA(t)=0.4+3tkbit,向PAN協調器發送GTS分配請求的流量規格是Fspec,A=(400 bit,3 kbit/s,150 ms)。PAN協調器根據資源現狀決定是否接受數據流FA請求。根據式(13)和(14)可得保障帶寬Rn=9.38 kbit/s和等待時間Tn=BI-nTslot=14.40 ms。單時隙GTS提供的服務曲線:

如圖2描述了節點A的GTS分配和它的服務曲線。采用式(15),PAN協調器根據Fspec,A可以計算單個時隙的延遲保障邊界:

同時單個時隙分配的保障帶寬9.38 kbit/s大于到達速率3 kbit/s。式(2)中的條件得到滿足,因此對數據流分配單個時隙。節點A使用了GTS的部分帶寬,根據式(9)可以計算利用率rA/RTS=31.98%。

圖2 一個節點的單個時隙分配

2.2 2個節點調度實例

在節點A基礎上,節點B產生數據流FB,按規格要求Fspec,B=(400 bits,3 kbit/s,150 ms)申請分配GTS。

采用循環調度共享一個時隙,在每個信標間隔BI間交替變化兩個數據流,如圖3(a)。圖3(b)對節點A和節點B采用另外一種不同于循環調度的方式,雖然保障帶寬沒有變化,但改變了服務曲線。最大的等待延遲變成3BI-TS=45.12 ms,此時FA,max=FB,max=130.41 ms也可以滿足式(2)中的2個條件。圖3(c)描述了每個數據流對應的服務曲線,其中分配時隙2BI-TS=29.76 ms,節點A速率bA=3 kbit/s,節點B速率bB=3 kbit/s。

圖3 兩個節點的單個時隙分配

2.3 3個節點的調度實例

在節點A和節點B的基礎,節點C產生數據流Fc,按規格要求Fspec,c=(400 bit,3 kbit/s,150 ms)申請分配GTS。根據循環調度,計算為每個數據流提供的服務曲線β3node,1TS(t)=3.12·(t-45.12)+,如圖4(a)。每個數據流的延遲邊界分別是:

DA,max=DB,max=DC,max=173.33 ms≥150 ms

雖然到達速率總和低于保障帶寬3+3+3<9.38,但節點B和C的延遲不能保障,不能與節點A共享一個時隙。

DA,max=DB,max=DC,max=92.8 ms≤150 ms

采用2個時隙可以滿足3個數據流需求。

圖4(c)描述了每個數據流對應的服務曲線,其中分配時隙2BI-2TS=28.80 ms,節點A速率bA=3 kbit/s,節點B速率bB=3 kbit/s,節點C速率bC=3 kbit/s。

圖4 3個節點的時隙分配

3 共享GTS延遲界限分析

本文采用擴展CFP長度,循環調度計算相應服務曲線的分析方法。

采用循環調度尋求N個數據流共享k個時隙的服務曲線,其中k≤N,并且數據流Fi的到達曲線ri≤RTS。每個超幀的GTS最多7個,因此k≤7。因為采用平等共享GTS的循環調度策略,所有數據流共享GTS的βi(t)等價于速率-延遲服務曲線βR,T(t)。分兩種情況分析:

k=N時類似專用分配,采每個節點都有自己的時隙。每個節點延遲界限Di可以通過式(15)計算。

k

(16)

T=p·BI+q·Tslot

(17)

其中p∈N表示與服務延遲相關的信標間隔數,q∈Z-表示從延遲中減去的時隙數。

對于k≤7和N≥1得:

(18)

在循環調度下,N個節點平等共享k個時隙的服務曲線(k

(19)

因此,對一個數據流Fi(ri≤R),平均共享延遲界限:

(20)

圖5 共享GTS延遲界限

4 數值分析

通過舉例比較共享GTS分配與專用GTS帶寬利用。假定有10個數據流Fi(i=1,…,10),到達速率分別是1.25、1、0.5、1.25、1、0.5、1.25、1、0.5和1(單位kbit/s)。由于保障延遲主要依賴猝發數據的多少,假定所有數據流有相同的促發值bi=200 bit(i=1,…,10)。PAN協調器設定參數為BO=SO=0的網絡,相應的BI=SD=15.36 ms,Tslot=0.96 ms和RTS=9.38 kbit/s?？紤]3種情況:①數據流F1到F5采用專用GTS分配;②數據流F1到F5采用共享GTS分配;③數據流F1到F10采用共享GTS分配。

圖6 專用與共享方法的GPS性能對比

5 結論

傳統的GTS分配方法最多只能為7個節點提供性能保障服務,而為了保障網絡節點比較多的采集網絡中數據的實時傳遞,就必須采用一種靈活的分配策略。本文在IEEE802.15.4專用GTS分配機制研究的基礎上,提出一種共享GTS分配策略。數值分析表明,對到達速率和緩沖數值較小的一類工業傳感采集網絡,在保證延遲需求的前提下,提高了帶寬利用率。

[1] Osama Khader,Andreas Willig.An Energy Consumption Analysis of the WirelessHART TDMA Protocol[J].Computer Communications,2013,36:804-816.

[2]Nguyen Quoc Dinh,Dong-Sung Kim.Performance Evaluation of Priority CSMA-CA Mechanism on ISA100.11a Wireless Network[J].Computer Standards and Interface,2012,34(1):117-123.

[3]Liang Wei,Zhang Xiaoling,Xiao Yang,et al.Survey and Experiments of WIA-PA Specification of Industrial Wireless Network[J].Wireless Communications and Mobile Computing,2011,11(8):1197-1212.

[4]Tiberi U,Fischione C,Johansson K H.Energy-Efficient Sampling of Networked Control Systems over IEEE 802.15.4 Wireless Networks[J].Automatica,2013,49:712-724.

[5]Daniele Bernardini,Alberto Bemporad.Energy-Aware Robust Model Predictive Control Based on Noisy Wireless Sensors[J].Automatica,2012,48:36-44.

[6]Jurcik Petr,Koubaa Anis,Severino Ricardo,et al.Dimensioning and Worst-Case Analysis of Cluster-Tree Sensor Networks[J].ACM Transactions on Sensor Networks,2010,7(2):1-47.

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

[8]胡倩,陳新.分簇無線傳感器網絡中密度感知的自適應占空比機制的研究[J].傳感技術學報,2013,26(1):105-109.

[9]Chewoo Na,Yaling Yang,Amitabh Mishra.An Optimal GTS Scheduling Algorithm for Time-Sensitive Transactions in IEEE 802.15.4 Networks[J].Computer Networks,2008,52:2543-2557.

[10]Li-Chun Ko,Zi-Tsan Chou.A Novel Multi-Beacon Superframe Structure with Greedy GTS Allocation for IEEE 802.15.4 Wireless PANs[C]//IEEE Wireless Communications and Networking Conference.New York:Institute of Electrical and Electronics Engineers Inc.2007:2330-2335.

[11]Anis Koubaa,Andre Cunha,Mario Alves,et al.TDBS:a Time Division Beacon Scheduling Mechanism for Zigbee Cluster-Tree Wireless Sensor Networks[J].Real-Time Systems,2008,40(3):321-354.

[12]Anis Koubaa,Ma-Rio Alves,Eduardo Tovar.i-GAME:An Implicit GTS Allocation Mechanism in IEEE 802.15.4[C]//Proceedings 18th Euromicro Conference on Real-Time Systems(ECRTS’06).Dresden:IEEE Computer Society.2006:183-192.

范書瑞(1979-),男,講師,博士,研究方向無線傳感器網絡和嵌入式系統,fansr@hebut.edu.cn。

GuaranteedTimeSlotsAllocationinMulti-NodeWirelessSensorNetworks*

FANShurui*,YANShen,GAOMeng

(School of Information Engineering,Hebei University of Technology,Tianjin 300401,China)

With unique characteristics of low power consumption and low cost,IEEE 802.15.4 standard is widely used in the modern industrial wireless networks.It can provide the lowest 0.006% of duty ratio to reduce power consumption,and offer real-time service for the node through the guarantee time slots(GTS)mechanism.However,IEEE 802.15.4 can only provide real-time guarantees service for certain nodes,which is lack of flexibility for large-scale networks.A shared security timeslot allocation policy by multi-node is present for overcome the shorting of special GTS allocation method,taking into account the traffic specifications and the delay requirements of the flows.The policy enables the use of a GTS by multiple nodes,and still ensure delay and bandwidth requirements.Numerical analysis clearly showed that,compared with the traditional method,the improvement of allocation policy can effectively improve the bandwidth utilization.

industrial wireless network;GTS allocation;real-time service;bandwidth utilization

項目來源:河北省自然科學青年基金項目(F2013202102);河北省科學研究與發展計劃項目(11213566);國家級大學生創新創業訓練計劃立項項目(201310080009)

2014-01-02修改日期:2014-06-09

10.3969/j.issn.1004-1699.2014.07.021

TP273

:A

:1004-1699(2014)07-0976-06