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

陳越洋，顧 平，張 超

(廣西大學計算機與電子信息學院，廣西 南寧 530004)

0 引言

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

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

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

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

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

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

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

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

簇樹型無線傳感網(wǎng)絡(luò)是一種分層拓撲結(jié)構(gòu)，以單簇星型網(wǎng)絡(luò)拓撲為基礎(chǔ)，簇與簇之間形成樹的結(jié)構(gòu)，見圖1。

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

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

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

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

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

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

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

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

3.1 SP 隊列調(diào)度

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

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

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

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

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

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

3.2 輸入輸出流計算

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

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

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

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

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

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

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

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

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

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

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

各隊列的輸出流:

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

3.3.1 緩存上界推導

對于每個節(jié)點來說，緩存的大小等于所有邏輯隊列的隊列長度之和。由公式(6)、(7)和定理1可推導節(jié)點緩存大小為:

3.3.2 時延上界推導

根據(jù)公式(6)、(7)和定理2可推導各隊列的時延上界:

3.4 端到端時延上界推導

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

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

4 實例分析

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

表1 緩沖區(qū)隊列長度

表2 時延上界

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

5 結(jié)束語

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

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

[2] 洪雁兵，王一軍，劉桂波，等.基于網(wǎng)絡(luò)演算的簇樹WSN性能上界分析[J].計算機工程與應用，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].計算機應用研究，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] 李煥忠.基于隨機網(wǎng)絡(luò)演算的性能分析技術(shù)研究[D].長沙:國防科學技術(shù)大學，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].長沙:中南大學，2006.

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

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

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