多節(jié)點共享保障時隙分配策略*

范書瑞,閆 伸,高 蒙

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

?

多節(jié)點共享保障時隙分配策略*

范書瑞*,閆 伸,高 蒙

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

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

工業(yè)無線網(wǎng)絡(luò);保障時隙分配;實時服務(wù);帶寬利用率

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

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

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

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

IEEE 802.15.4在PAN協(xié)調(diào)器同步的星型拓?fù)浠A(chǔ)上,通過子協(xié)調(diào)器可以擴(kuò)展出簇結(jié)構(gòu)網(wǎng)絡(luò),用于組建大規(guī)模傳感采集網(wǎng)絡(luò)。設(shè)定每個網(wǎng)絡(luò)節(jié)點i產(chǎn)生數(shù)據(jù)流Fi,受限于到達(dá)曲線ai(t)=bi+rit,其中bi是最大猝發(fā)數(shù)據(jù)大小,ri是平均到達(dá)速率,Di表示Fi的最大延遲需求。采用Fspec,i=(bi,ri,Di)表示數(shù)據(jù)流Fi。

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

RkTS=k·RTS

(1)

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

條件1:

(2)

條件2:

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

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

1.1 專用GTS帶寬利用

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

(3)

(4)

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

(ki-1)·RTS

(5)

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

(6)

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

(7)

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

圖1 GTS帶寬最小利用率

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

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

(8)

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

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

(9)

GTS中單個數(shù)據(jù)流的利用率:

(10)

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

2 共享GTS分配舉例

假定IEEE802.15.4簇網(wǎng)絡(luò)中,PAN協(xié)調(diào)器設(shè)定超幀結(jié)構(gòu)BO=SO=0,相應(yīng)的BI=SD=15.36 ms,TSlot=0.96 ms和RTS=9.38 kbit/s。

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

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

(11)

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

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

(12)

(13)

保障服務(wù)的等待時間:

Tn=BI-n·Tslot

(14)

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

(15)

2.1 1個節(jié)點調(diào)度實例

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

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

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

圖2 一個節(jié)點的單個時隙分配

2.2 2個節(jié)點調(diào)度實例

在節(jié)點A基礎(chǔ)上,節(jié)點B產(chǎn)生數(shù)據(jù)流FB,按規(guī)格要求Fspec,B=(400 bits,3 kbit/s,150 ms)申請分配GTS。

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

圖3 兩個節(jié)點的單個時隙分配

2.3 3個節(jié)點的調(diào)度實例

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

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

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

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

采用2個時隙可以滿足3個數(shù)據(jù)流需求。

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

圖4 3個節(jié)點的時隙分配

3 共享GTS延遲界限分析

本文采用擴(kuò)展CFP長度,循環(huán)調(diào)度計算相應(yīng)服務(wù)曲線的分析方法。

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

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

k

(16)

T=p·BI+q·Tslot

(17)

其中p∈N表示與服務(wù)延遲相關(guān)的信標(biāo)間隔數(shù),q∈Z-表示從延遲中減去的時隙數(shù)。

對于k≤7和N≥1得:

(18)

在循環(huán)調(diào)度下,N個節(jié)點平等共享k個時隙的服務(wù)曲線(k

(19)

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

(20)

圖5 共享GTS延遲界限

4 數(shù)值分析

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

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

5 結(jié)論

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

[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]周明偉,樊曉平,劉少強(qiáng).基于優(yōu)先級的IEEE802.15.4 CSMA/CA建模與分析[J].傳感技術(shù)學(xué)報,2009,22(3):422-426.

[8]胡倩,陳新.分簇?zé)o線傳感器網(wǎng)絡(luò)中密度感知的自適應(yīng)占空比機(jī)制的研究[J].傳感技術(shù)學(xué)報,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-),男,講師,博士,研究方向無線傳感器網(wǎng)絡(luò)和嵌入式系統(tǒng),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

項目來源:河北省自然科學(xué)青年基金項目(F2013202102);河北省科學(xué)研究與發(fā)展計劃項目(11213566);國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃立項項目(201310080009)

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

10.3969/j.issn.1004-1699.2014.07.021

TP273

:A

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