范書瑞,閆 伸,高 蒙

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

?

多節(jié)點(diǎn)共享保障時(shí)隙分配策略*

范書瑞*,閆 伸,高 蒙

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

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

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

近年來,無線網(wǎng)絡(luò)技術(shù)快速發(fā)展,在實(shí)時(shí)性和可靠性方面取得進(jìn)步,為其在工業(yè)的應(yīng)用提供了可能。在傳感層采用無線措施是實(shí)現(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)與自動(dòng)化協(xié)會(huì)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個(gè)工業(yè)標(biāo)準(zhǔn)中。文獻(xiàn)[4]采用自觸發(fā)采樣策略減少網(wǎng)絡(luò)利用和能耗損耗的同時(shí),確保了網(wǎng)絡(luò)性能。文獻(xiàn)[5]針對(duì)能量敏感問題設(shè)計(jì)了模型預(yù)測(cè)控制,確保WSN魯棒性。這些也都證明IEEE802.15.4適用于現(xiàn)代工業(yè)網(wǎng)絡(luò)控制系統(tǒng)。

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

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

1 保障時(shí)隙帶寬利用與分配

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è)定每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)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表示每個(gè)時(shí)隙的保障帶寬,RkTS表示分配了k個(gè)時(shí)隙GTS的保障帶寬:

RkTS=k·RTS

(1)

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

條件1:

(2)

條件2:

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

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

1.1 專用GTS帶寬利用

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

(3)

(4)

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

(ki-1)·RTS

(5)

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

(6)

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

(7)

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

圖1 GTS帶寬最小利用率

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

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

(8)

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

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

(9)

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

(10)

與專用分配一個(gè)時(shí)隙一致,共享GTS分配的到達(dá)速率ri≤RTS。問題簡化為,對(duì)k個(gè)時(shí)隙長的CFP,平均分配共享GTS,其中k≤N。在這種情況下,CFP長度不能超過7個(gè)時(shí)隙,因?yàn)樽疃嗫梢苑峙?個(gè)GTS,每個(gè)GTS長度是1個(gè)時(shí)隙。

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。

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

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

(11)

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

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

(12)

(13)

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

Tn=BI-n·Tslot

(14)

可得n個(gè)時(shí)隙GTS的延遲上界

(15)

2.1 1個(gè)節(jié)點(diǎn)調(diào)度實(shí)例

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

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

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

圖2 一個(gè)節(jié)點(diǎn)的單個(gè)時(shí)隙分配

2.2 2個(gè)節(jié)點(diǎn)調(diào)度實(shí)例

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

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

圖3 兩個(gè)節(jié)點(diǎn)的單個(gè)時(shí)隙分配

2.3 3個(gè)節(jié)點(diǎn)的調(diào)度實(shí)例

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

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

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

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

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

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

圖4 3個(gè)節(jié)點(diǎn)的時(shí)隙分配

3 共享GTS延遲界限分析

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

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

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

k

(16)

T=p·BI+q·Tslot

(17)

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

對(duì)于k≤7和N≥1得:

(18)

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

(19)

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

(20)

圖5 共享GTS延遲界限

4 數(shù)值分析

通過舉例比較共享GTS分配與專用GTS帶寬利用。假定有10個(gè)數(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性能對(duì)比

5 結(jié)論

傳統(tǒng)的GTS分配方法最多只能為7個(gè)節(jié)點(diǎn)提供性能保障服務(wù),而為了保障網(wǎng)絡(luò)節(jié)點(diǎn)比較多的采集網(wǎng)絡(luò)中數(shù)據(jù)的實(shí)時(shí)傳遞,就必須采用一種靈活的分配策略。本文在IEEE802.15.4專用GTS分配機(jī)制研究的基礎(chǔ)上,提出一種共享GTS分配策略。數(shù)值分析表明,對(duì)到達(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)先級(jí)的IEEE802.15.4 CSMA/CA建模與分析[J].傳感技術(shù)學(xué)報(bào),2009,22(3):422-426.

[8]胡倩,陳新.分簇?zé)o線傳感器網(wǎng)絡(luò)中密度感知的自適應(yīng)占空比機(jī)制的研究[J].傳感技術(shù)學(xué)報(bào),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

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

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

10.3969/j.issn.1004-1699.2014.07.021

TP273

:A

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