陳越洋，顧 平，張 超

(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引言

無(wú)線傳感網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是由大量廉價(jià)的同構(gòu)或異構(gòu)具有無(wú)線通信與計(jì)算能力的微型傳感器節(jié)點(diǎn)，部署在無(wú)人值守的監(jiān)控或測(cè)量區(qū)域，能夠根據(jù)檢測(cè)目標(biāo)或?qū)ο笞灾魍瓿山o定任務(wù)，并將準(zhǔn)確的信息傳送到遠(yuǎn)程用戶的智能檢測(cè)網(wǎng)絡(luò)[1]。目前，利用網(wǎng)絡(luò)演算對(duì)無(wú)線傳感網(wǎng)絡(luò)進(jìn)行性能分析主要是基于經(jīng)典的 FIFO隊(duì)列調(diào)度[2-4]，忽略了終端節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)流比路由節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)流需要更多的跳數(shù)才能到達(dá)匯聚節(jié)點(diǎn)的數(shù)據(jù)流特點(diǎn)。本文在簇樹網(wǎng)絡(luò)拓?fù)渲幸隨P隊(duì)列調(diào)度，將路由節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)優(yōu)先提供給終端節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)流，減小網(wǎng)絡(luò)的端到端時(shí)延。本文在文獻(xiàn)[3-4]的已有網(wǎng)絡(luò)流量模型基礎(chǔ)上，利用網(wǎng)絡(luò)演算的相關(guān)理論，推導(dǎo)出最壞條件下的節(jié)點(diǎn)隊(duì)列長(zhǎng)度、單跳時(shí)延上界，并結(jié)合文獻(xiàn)[5-6]中的總流量分析法，求解該調(diào)度策略下的最大端到端時(shí)延。

1 確定性網(wǎng)絡(luò)演算的基本工具

定義1 到達(dá)曲線(Arrival Curves)[7-8]:給定一個(gè)函數(shù)α(t)，且α∈Γ，Γ為廣義增函數(shù)集合，若通信流的累積函數(shù)R(t)對(duì)任意時(shí)刻t≥s≥0滿足R(t)－R(s)≤α(t－s)，則稱 α(t)為 R(t)的到達(dá)曲線。

定義2 服務(wù)曲線(Service Curves)[9-11]:給定一個(gè)通信流的累積函數(shù)R(t)，對(duì)于函數(shù)β(t)∈Γ，且β(0)=0，若通信流的輸出函數(shù)R*(t)滿足R*≥R?β，則稱節(jié)點(diǎn)為通信流R(t)提供服務(wù)曲線β(t)。

定理1 積壓上界定理[10]:假定一個(gè)到達(dá)曲線為α(t)的通信流穿過(guò)一個(gè)網(wǎng)絡(luò)系統(tǒng)，該系統(tǒng)為通信流提供的服務(wù)曲線為β(t)，則對(duì)任意時(shí)刻t，通信流在該系統(tǒng)中的積壓數(shù)據(jù)(隊(duì)列長(zhǎng)度)Q(t)滿足如下的關(guān)系:

定理2 時(shí)延上界定理[7，10-11]:假定一個(gè)到達(dá)曲線為α(t)的通信流穿過(guò)一個(gè)網(wǎng)絡(luò)系統(tǒng)，該系統(tǒng)為通信流提供的服務(wù)曲線為β(t)，對(duì)任意時(shí)刻t，通信流在該系統(tǒng)中的延遲D(t)滿足如下的關(guān)系:

定理 3 輸出受限特性[5，7，11]:假定一個(gè)到達(dá)曲線為α(t)的通信流穿過(guò)一個(gè)網(wǎng)絡(luò)系統(tǒng)，該系統(tǒng)為通信流提供的服務(wù)曲線為β(t)，則輸出流受限于α*(t)=α?β。

2 簇樹型無(wú)線傳感網(wǎng)絡(luò)

簇樹型無(wú)線傳感網(wǎng)絡(luò)是一種分層拓?fù)浣Y(jié)構(gòu)，以單簇星型網(wǎng)絡(luò)拓?fù)錇榛A(chǔ)，簇與簇之間形成樹的結(jié)構(gòu)，見(jiàn)圖1。

圖1 簇樹型無(wú)線傳感網(wǎng)絡(luò)結(jié)構(gòu)

網(wǎng)絡(luò)主要包含3種節(jié)點(diǎn):根節(jié)點(diǎn)(root)、路由節(jié)點(diǎn)(router)、終端節(jié)點(diǎn)(end-node)。本文假設(shè)，這3種節(jié)點(diǎn)都具有感知能力，根節(jié)點(diǎn)不獲取感知數(shù)據(jù)。

本文將采用以下參數(shù)對(duì)簇樹網(wǎng)絡(luò)進(jìn)行配置:

1)網(wǎng)絡(luò)深度H:即數(shù)據(jù)流從網(wǎng)絡(luò)最底層路由節(jié)點(diǎn)到根節(jié)點(diǎn)要經(jīng)過(guò)的邏輯跳數(shù)(Logic Hop)。設(shè)根節(jié)點(diǎn)的深度為0，則最底層路由節(jié)點(diǎn)所在簇內(nèi)的終端節(jié)點(diǎn)的深度為H+1。

2)Nr(Maximum Number of Child-routers):路由節(jié)點(diǎn)所連接的最大子路由節(jié)點(diǎn)數(shù)目。

3)Ne(Maximum Number of End-Nodes):路由節(jié)點(diǎn)所連接的最大的終端節(jié)點(diǎn)數(shù)目。

本文研究在最壞情況下的網(wǎng)絡(luò)服務(wù)質(zhì)量，即所有終端節(jié)點(diǎn)和路由節(jié)點(diǎn)都被要求向匯聚節(jié)點(diǎn)發(fā)送傳感數(shù)據(jù)。

3 基于SP調(diào)度策略的無(wú)線傳感網(wǎng)絡(luò)QoS上界研究

3.1 SP 隊(duì)列調(diào)度

嚴(yán)格優(yōu)先級(jí)隊(duì)列調(diào)度是常用隊(duì)列調(diào)度算法的一種。SP調(diào)度算法嚴(yán)格按照隊(duì)列的優(yōu)先級(jí)從高到低的次序，先發(fā)送級(jí)別較高的隊(duì)列中的分組，直到高優(yōu)先級(jí)隊(duì)列為空，才會(huì)發(fā)送較低優(yōu)先級(jí)隊(duì)列中的分組。調(diào)度過(guò)程如圖2所示。

圖2 SP隊(duì)列調(diào)度

在本文中，對(duì)路由節(jié)點(diǎn)引入SP調(diào)度策略，優(yōu)先給轉(zhuǎn)發(fā)數(shù)據(jù)流αtransmit提供服務(wù)，即轉(zhuǎn)發(fā)數(shù)據(jù)流的優(yōu)先級(jí)要高于路由節(jié)點(diǎn)自身的傳感數(shù)據(jù)流αself－sense。所以對(duì)于自身傳感數(shù)據(jù)流而言，其獲得的路由節(jié)點(diǎn)提供的保證服務(wù)的服務(wù)曲線為 βself－sense=[β － αtransmit]+。但是形成匯聚轉(zhuǎn)發(fā)流的各數(shù)據(jù)流之間沒(méi)有優(yōu)先級(jí)。

在簇樹拓?fù)浣Y(jié)構(gòu)中，由于最深處的路由節(jié)點(diǎn)形成了2個(gè)優(yōu)先級(jí)的數(shù)據(jù)流，分別是匯聚轉(zhuǎn)發(fā)流和自身傳感流，那么在上層的父路由節(jié)點(diǎn)中，這2個(gè)數(shù)據(jù)流獲得保證服務(wù)的優(yōu)先級(jí)也不同，這樣的優(yōu)先級(jí)會(huì)在數(shù)據(jù)向上匯聚的過(guò)程中一直保持。也就是說(shuō)，隨著數(shù)據(jù)流向上匯聚，數(shù)據(jù)流之間的優(yōu)先級(jí)數(shù)量會(huì)不斷增加。對(duì)于H-i層的路由節(jié)點(diǎn)來(lái)說(shuō)，其優(yōu)先級(jí)數(shù)目為:

對(duì)于任意含有子路由節(jié)點(diǎn)的節(jié)點(diǎn)來(lái)說(shuō)，其優(yōu)先級(jí)情況為:簇內(nèi)匯聚傳感數(shù)據(jù)流+子路由節(jié)點(diǎn)匯聚轉(zhuǎn)發(fā)數(shù)據(jù)流＞所有子路由自身傳感數(shù)據(jù)流＞自身傳感數(shù)據(jù)流。

αH，self－sense表示深度為H的路由節(jié)點(diǎn)的自身傳感數(shù)據(jù)流，那么所有子路有節(jié)點(diǎn)自身傳感數(shù)據(jù)流之間會(huì)形成如下的優(yōu)先級(jí):

3.2 輸入輸出流計(jì)算

本文假設(shè)傳感數(shù)據(jù)流在進(jìn)入網(wǎng)絡(luò)之前經(jīng)過(guò)漏桶整形，其到達(dá)曲線為[7]:α =b+r·t。父路由節(jié)點(diǎn)為其子節(jié)點(diǎn)提供基于速率-延遲的保證服務(wù)，其服務(wù)曲線為[12-13]:β =R(t－T)+。那么，在簇樹網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，H層路由節(jié)點(diǎn)獲得H－1層父路由節(jié)點(diǎn)提供的保證服務(wù)為:

3.2.1 位于深度為H的路由節(jié)點(diǎn)的數(shù)據(jù)流分析

這里是路由節(jié)點(diǎn)的底層，對(duì)于該層的任意路由節(jié)點(diǎn)來(lái)說(shuō)，沒(méi)有子路由節(jié)點(diǎn)，就只有終端節(jié)點(diǎn)的數(shù)據(jù)流向上匯聚，引入SP調(diào)度策略之后，會(huì)出現(xiàn)2個(gè)不同優(yōu)先級(jí)的邏輯隊(duì)列 αH，0和 αH，1，分別表示自身傳感數(shù)據(jù)流和簇內(nèi)所有終端的輸出流匯聚而成的轉(zhuǎn)發(fā)數(shù)據(jù)流，其計(jì)算到達(dá)曲線分別為:

由于SP調(diào)度策略的影響，這2個(gè)隊(duì)列分別能獲得其父路由節(jié)點(diǎn)(深度為H－1)所提供的服務(wù)保證為:

由公式(1)、公式(2)和定理3可以求出深度為H的路由節(jié)點(diǎn)的輸出上界為:

3.2.2 深度為H－1的數(shù)據(jù)流分析

調(diào)度策略對(duì)H層數(shù)據(jù)流的影響會(huì)延續(xù)到H－1層。對(duì)于H－1層的路由節(jié)點(diǎn)來(lái)說(shuō)將會(huì)形成如下的邏輯隊(duì)列。

其優(yōu)先級(jí)為flow2＞flow1＞flow0，所以各數(shù)據(jù)流從其父路由節(jié)點(diǎn)獲得的保證服務(wù)如下:

類似可求出深度為H－i的路由節(jié)點(diǎn)中各隊(duì)列的輸出流:

類似地，可以推導(dǎo)出深度為H－i(0≤i≤Depth－1)的一般性表達(dá)式:

各數(shù)據(jù)流獲得服務(wù)的優(yōu)先級(jí)為flowi+1＞flowi＞…＞flow1＞flow0，所以可求出各數(shù)據(jù)流所獲得的保證服務(wù)的服務(wù)曲線如下:

各隊(duì)列的輸出流:

3.3 單節(jié)點(diǎn)服務(wù)質(zhì)量上界研究

3.3.1 緩存上界推導(dǎo)

對(duì)于每個(gè)節(jié)點(diǎn)來(lái)說(shuō)，緩存的大小等于所有邏輯隊(duì)列的隊(duì)列長(zhǎng)度之和。由公式(6)、(7)和定理1可推導(dǎo)節(jié)點(diǎn)緩存大小為:

3.3.2 時(shí)延上界推導(dǎo)

根據(jù)公式(6)、(7)和定理2可推導(dǎo)各隊(duì)列的時(shí)延上界:

3.4 端到端時(shí)延上界推導(dǎo)

由于本文引入了SP調(diào)度策略，使得數(shù)據(jù)流優(yōu)先級(jí)在向上匯聚的過(guò)程中不斷增加，各路由節(jié)點(diǎn)中會(huì)有數(shù)據(jù)分流形成各自優(yōu)先級(jí)的匯聚流，從其父路由節(jié)點(diǎn)獲得服務(wù)保證。所以本文在計(jì)算端到端時(shí)延時(shí)，采用總流分析法，即數(shù)據(jù)流的端到端時(shí)延就等于該流通過(guò)的所有服務(wù)節(jié)點(diǎn)的單跳時(shí)延之和。

所以，數(shù)據(jù)流從各深度路由節(jié)點(diǎn)到達(dá)匯聚節(jié)點(diǎn)的端到端時(shí)延上界為:

4 實(shí)例分析

本文采用文獻(xiàn)[2]中的數(shù)據(jù)進(jìn)行實(shí)例分析，對(duì)WSN進(jìn)行如下的基本參數(shù)設(shè)置:H=3，Nr=2，Ne=3，RTS=0.586 kb/s，b=0.2 kb/s，r=0.1 kb/s，終端節(jié)點(diǎn)獲得路由節(jié)點(diǎn)保證服務(wù)的固定時(shí)延T=0.1 s;根據(jù)上文推導(dǎo)的公式(9)～(11)，通過(guò)Matlab得出該實(shí)例中各節(jié)點(diǎn)的緩沖區(qū)大小和網(wǎng)絡(luò)的單跳時(shí)延上界，結(jié)果如表1、表2所示。

表1 緩沖區(qū)隊(duì)列長(zhǎng)度

表2 時(shí)延上界

從表1、表2中可以看出，SP隊(duì)列調(diào)度增加了路由節(jié)點(diǎn)的緩存開銷，增大路由節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)流到達(dá)匯聚節(jié)點(diǎn)的時(shí)延，但是降低了終端節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的端到端時(shí)延。在簇樹型無(wú)線傳感網(wǎng)絡(luò)中路由節(jié)點(diǎn)的數(shù)量遠(yuǎn)小于終端節(jié)點(diǎn)的數(shù)量，本文中路由節(jié)點(diǎn)數(shù)目和終端節(jié)點(diǎn)數(shù)目之比是1∶3，所以以犧牲小部分?jǐn)?shù)據(jù)流的時(shí)延和增加一部分緩存為代價(jià)，換取絕大多數(shù)的傳感數(shù)據(jù)能更快地到達(dá)匯聚節(jié)點(diǎn)，提升總體服務(wù)質(zhì)量是可行的。

5 結(jié)束語(yǔ)

本文研究了SP調(diào)度策略下的簇樹型無(wú)線傳感網(wǎng)絡(luò)服務(wù)質(zhì)量，分析了SP調(diào)度策略給簇樹型無(wú)線傳感網(wǎng)絡(luò)中各數(shù)據(jù)流獲得保證服務(wù)帶來(lái)的影響，基于網(wǎng)絡(luò)演算推導(dǎo)了網(wǎng)絡(luò)服務(wù)質(zhì)量相關(guān)指標(biāo)的確定上界。實(shí)驗(yàn)結(jié)果表明，雖然SP隊(duì)列調(diào)度增加了緩存需求，增大了路由節(jié)點(diǎn)自身傳感數(shù)據(jù)流到達(dá)匯聚節(jié)點(diǎn)的時(shí)延，但是也明顯降低了終端節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)流到匯聚節(jié)點(diǎn)的端到端時(shí)延。而在實(shí)際應(yīng)用中，終端節(jié)點(diǎn)數(shù)目會(huì)遠(yuǎn)大于路由節(jié)點(diǎn)數(shù)目，所以SP調(diào)度策略對(duì)于提升網(wǎng)絡(luò)整體的服務(wù)質(zhì)量是有意義的。下一步的研究，可以對(duì)節(jié)點(diǎn)的占空比進(jìn)行調(diào)節(jié)，以獲得性能和時(shí)延的平衡，也可以利用隨機(jī)網(wǎng)絡(luò)演算來(lái)對(duì)網(wǎng)絡(luò)的性能進(jìn)行研究。

[1] 王營(yíng)冠，王智.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:電子工業(yè)出版社，2012.

[2] 洪雁兵，王一軍，劉桂波，等.基于網(wǎng)絡(luò)演算的簇樹WSN性能上界分析[J].計(jì)算機(jī)工程與應(yīng)用，2012，48(19):48-53.

[3] Jurcik P，Severino R，Koubaa A，et a1.Dimensioning and worst-case analysis of cluster-tree sensor networks[J].ACM Transactions on Sensor Networks，2010，7(2):Article 14.

[4] Koubaa A，Alves M，Tovar E.Modeling and worst-case dimensioning of cluster-tree wireless sensor networks[C]//Proceedings of the 27th IEEE Real-Time Systems Symposium.2006:412-421.

[5] 李翠，巨永鋒，李雪.WSN中單數(shù)據(jù)流端到端延遲上界研究[J].計(jì)算機(jī)應(yīng)用研究，2013，30(6):1820-1823.

[6] Schmitt J B，Zdarsky F A，Thiele L.A comprehensive worst-case calculus for wireless sensor networks with in-network processing[C]//Proceedings of the 28th IEEE Real-Time Systems Symposium.2007:193-202.

[7] 李煥忠.基于隨機(jī)網(wǎng)絡(luò)演算的性能分析技術(shù)研究[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué)，2011.

[8] Le Boudec J-Y，Thiran P.Network Calculus:A Theory of Deterministic Queuing Systems for the Internet[M].Springer Verlag，2001.

[9] Firoiu V，Le Boudec J-Y，Towsley D，et al.Theories and models for Internet quality of service[J].Proceedings of the IEEE，2002，90(9):1565-1591.

[10] 張連明.基于網(wǎng)絡(luò)演算的自相似網(wǎng)絡(luò)性能上界模型研究[D].長(zhǎng)沙:中南大學(xué)，2006.

[11] 陳京文.基于統(tǒng)計(jì)型演算論的網(wǎng)絡(luò)服務(wù)性能分析[D].武漢:華中科技大學(xué)，2007.

[12] 陳艷平.基于網(wǎng)絡(luò)演算的QoS分析方法與保障技術(shù)[D].哈爾濱:哈爾濱工程大學(xué)，2012.

[13] 柴明.基于ETS的自相似網(wǎng)絡(luò)QoS性能評(píng)價(jià)[D].南寧:廣西大學(xué)，2012.