楊志軍 蘇楊 丁洪偉

輪詢服務(wù)系統(tǒng)代表了一類調(diào)度控制的模型,因為其擁有較好的公平性,所以它不僅可以讓有限的資源得到有效的分配,而且可以讓資源得到共享[1?2].按服務(wù)方式的不同,輪詢服務(wù)系統(tǒng)可以分為門限、完全以及限定三類[3?4].在三種基本的輪詢服務(wù)模型的基礎(chǔ)上,可以構(gòu)成多種混合式區(qū)分優(yōu)先級的輪詢服務(wù).文獻[4]利用延遲周期的概念,給出了各類型客戶等待時間的精確LST(Laplace steltjes transform)表達式和表示方法.此外,證明了優(yōu)先級較小的平均服務(wù)時間的客戶可以縮短平均響應(yīng)時間,尤其是在繁忙的交通當(dāng)中.文獻[5]提出了一種基于閘門式多級門限服務(wù)的兩級優(yōu)先級輪詢系統(tǒng),該輪詢系統(tǒng)滿足了周期性系統(tǒng)服務(wù)資源分配過程中業(yè)務(wù)多樣性和彈性服務(wù)的發(fā)展需求,使得輪詢控制策略應(yīng)用方面更為廣泛.文獻[6]提出了一種新型的兩級優(yōu)先級輪詢系統(tǒng),既保證了隊列優(yōu)先級的需求,又避免了空閑查詢時造成的時間延遲,達到了提高系統(tǒng)的利用率,減少時延的效果.文獻[7]分析了隊列中在不區(qū)分優(yōu)先級和區(qū)分優(yōu)先級的情況下,對每一個隊列提供門限服務(wù)或者是完全服務(wù).并根據(jù)于此建立數(shù)學(xué)模型,然后對此模型的聯(lián)合隊列長度、循環(huán)周期、邊際隊列長度和時延等性能特點進行了解析,驗證了區(qū)分優(yōu)先級所帶來的顯著成效.對輪詢系統(tǒng)區(qū)分優(yōu)先級主要目的,是旨在讓輪詢系統(tǒng)的性能得到顯著的提升.在優(yōu)先級輪詢的應(yīng)用方面,它可以用于藍牙技術(shù)和IEEE 802.11無線局域網(wǎng)協(xié)議的研究或是在Web服務(wù)器的路由器和I/O子系統(tǒng)中的調(diào)度策略.例如,保證服務(wù)質(zhì)量(Quality of service,QoS)是無線LAN協(xié)議中非常重要的問題,雖然延遲對響應(yīng)或數(shù)據(jù)傳輸不會產(chǎn)生重大影響,如網(wǎng)頁瀏覽或電子郵件流量,但是視頻傳輸和無線局域網(wǎng)語音(VoWLAN)對延遲或數(shù)據(jù)丟失卻是非常的敏感.所以,802.11e則引入了不同的優(yōu)先級來區(qū)分為類型之間的數(shù)據(jù)提高流媒體業(yè)務(wù)的服務(wù)質(zhì)量.優(yōu)先級輪詢模型也可以用來研究流量,比如在交通路口,交通流同時面對綠燈時的情況.由此看出,對輪詢系統(tǒng)進行優(yōu)先級區(qū)分的研究有著重大的意義.

本文也是對區(qū)分優(yōu)先級的兩級輪詢服務(wù)進行了研究,所不同的是,本文選擇了一種對稱性輪詢服務(wù)與非對稱性輪詢服務(wù)相結(jié)合的混合式服務(wù)模型.為了更好地適應(yīng)實際應(yīng)用的需求,非對稱的輪詢服務(wù)分析一直是研究的熱點,但實質(zhì)性突破相對較難.由于在實際應(yīng)用中,經(jīng)常會有不同類信息或不同類站點,相應(yīng)要求在同一種服務(wù)策略下,系統(tǒng)設(shè)置的參數(shù)需要滿足不同類站點自身所需的要求,這就需要非對稱的服務(wù)策略.由于輪詢系統(tǒng)中各隊列之間是相互聯(lián)系的,而且系統(tǒng)的概率分布特性非常復(fù)雜,所以在對多隊列的非對稱輪詢系統(tǒng)進行解析時,具有一定的困難度.而本文采用的對稱與非對稱相結(jié)合的混合服務(wù)模式,在對其性能解析過程中有著巨大的挑戰(zhàn)性.同時,多隊列的非對稱輪詢服務(wù)的二階特性(平均等待時間)很難給出其精確的數(shù)學(xué)解析式,所以選擇一種合理的近似方法去解析平均等待時間是研究非對稱性輪詢服務(wù)最關(guān)鍵的一點.

針對以上的分析過程,本文首先建立兩級優(yōu)先級非對稱性的服務(wù)模型,給出一階特性量平均排隊隊長及循環(huán)查詢周期的精確表達式.然后對模型的二階特性量進行分析,并且參照文獻[8]運用查詢周期的二階特性近似相等的方法,對平均等待時間進行解析.最后在軟件Matlab中進行實驗仿真,并與理論計算結(jié)果進行對比.本文在構(gòu)建數(shù)學(xué)模型當(dāng)中,則是采用了完全的調(diào)度策略服務(wù)于中心隊列,而普通隊列則采用了非對稱的門限服務(wù)的方式.在服務(wù)的過程當(dāng)中,服務(wù)器優(yōu)先對高優(yōu)先級的中心隊列進行發(fā)送服務(wù),直到中心隊列所存在數(shù)據(jù)信息量為空時,服務(wù)器會轉(zhuǎn)換到第i(i=1,2,···,N)個普通隊列,因為該服務(wù)模型由中心隊列轉(zhuǎn)換到普通隊列時,采用的是并行服務(wù)模式,所以當(dāng)服務(wù)器由中心隊列轉(zhuǎn)向?qū)ζ胀犃羞M行服務(wù)時,就不需要再經(jīng)歷一個查詢轉(zhuǎn)換時間,而是直接轉(zhuǎn)向普通隊列對其進行服務(wù).當(dāng)普通隊列i的數(shù)據(jù)信息量完成發(fā)送之后,服務(wù)器會經(jīng)歷一個查詢轉(zhuǎn)換時間再一次轉(zhuǎn)向中心隊列,對其進行完全服務(wù),當(dāng)中心隊列的發(fā)送服務(wù)完成之后,第i+1個普通隊列將會得到服務(wù),該模型的查詢順序如下圖2所示.服務(wù)器采用兩種混合式的輪詢服務(wù),可以讓中心隊列獲得更多的服務(wù)時間,實現(xiàn)了中心隊列與普通隊列之間優(yōu)先級的區(qū)分,同時也保證了一般的業(yè)務(wù)能夠得到普通隊列的服務(wù)[10].

1 系統(tǒng)模型

兩級優(yōu)先級非對稱輪詢控制系統(tǒng)的控制機制是由一個服務(wù)器及N+1個隊列來構(gòu)建組成的,N+1個隊列中包括N個普通隊列和一個中心隊列[9],分析過程中則用h來對中心隊列進行代替.因為兩級優(yōu)先級非對稱輪詢系統(tǒng),是一種對稱與非對稱相結(jié)合的混合式輪詢服務(wù)系統(tǒng),在這種服務(wù)模式中,中心隊列由1個隊列構(gòu)成,在每一次輪詢服務(wù)的過程中,其自身的性能參數(shù)都是固定不變的,這在局部的意義上可以說是一種對稱性的體現(xiàn);此外,由于多個普通隊列中,每個隊列都有其獨立不同的性能參數(shù)(到達率、服務(wù)時間、轉(zhuǎn)換時間)設(shè)置,體現(xiàn)多個普通隊列之間所存在的非對稱性,所以需要對中心隊列和普通隊列,分別采用兩種不同的輪詢服務(wù).

圖1 兩級輪詢服務(wù)模型Fig.1 Two-level polling service model

圖2 系統(tǒng)的查詢服務(wù)順序Fig.2 System query service sequence

設(shè)定在tn時刻隊列i(i=1,2,···,N)接受到服務(wù)器的發(fā)送服務(wù),第i個隊列中所包含的數(shù)據(jù)信息量為ξi(n),定義系統(tǒng)的隨機變量為{ξ1(n),ξ2(n),···,ξN(n),ξh(n)}, 其所耗費的服務(wù)時間定義為νi(n).隊列在接受服務(wù)期間不斷地會有數(shù)據(jù)信息量加入隊列,在此時間段到達第j(j=1,2,···,N,h)個隊列的數(shù)據(jù)信息量為ηj(νi).服務(wù)器所提供給普通隊列的服務(wù)完成之后,會經(jīng)過一個查詢轉(zhuǎn)換時間,在時刻服務(wù)器為中心隊列h提供發(fā)送服務(wù),此刻中心隊列中所存在的數(shù)據(jù)信息量為ξh(n?),定義系統(tǒng)的隨機變量為{ξ1(n?),ξ2(n?),···,ξh(n?),ξh(n?)}. 中心隊列h需要的服務(wù)時間定義為νh(n?),隊列中的數(shù)據(jù)信息量采用完全服務(wù)的方式期間,進入到第j(j=1,2,···,N,h)個隊列的數(shù)據(jù)信息量為ηj(νh).服務(wù)完成之后,在tn+1時刻第i+l個普通隊列開始接受服務(wù),定義隨機變量{ξ1(n+1),ξ2(n+1),···,ξN(n+1),ξh(n+1)}.服務(wù)器經(jīng)第i個隊列轉(zhuǎn)換到中心隊列,再經(jīng)中心隊列轉(zhuǎn)換到第i+l個隊列,其所耗費的轉(zhuǎn)換時間為μi(n),在此時間段加入到第j(j=1,2,···,N,h)個隊列的數(shù)據(jù)信息量為μj(μi),輪詢系統(tǒng)的隨機變量存在以下關(guān)系為

1.1 工作條件

1)在任何時刻加入隊列的數(shù)據(jù)信息量服從于彼此獨立的、且同分布的泊松過程,其分布概率母函數(shù)為Ai(zi),均值為,方差為其中i=1,2,···,N;中心隊列的分布為.

2)服務(wù)器對任意一個隊列進行發(fā)送時,隊列中所包含的數(shù)據(jù)信息量在發(fā)送的時候所耗費的時間滿足于彼此獨立的、且同分布的過程,其分布概率母函數(shù)為Bj(zj),均值為,方差為,其中j=1,2,···,N;中心隊列的分布為.

3)服務(wù)器完成隊列的發(fā)送服務(wù),隊列之間進行切換時,所耗費時間的分布過程的概率母函數(shù)為Rk(zk),均值為,方差為,其中k=1,2,···,N;中心隊列的分布為.

4)設(shè)定服務(wù)系統(tǒng)中任何一個隊列的緩存容量足夠大,不存在數(shù)據(jù)信息量丟失的情況發(fā)生;

5)每一個加入進隊列的數(shù)據(jù)信息量,將會按照先到先服務(wù)(First come first served,FCFS)的方法接受服務(wù)[11].

1.2 系統(tǒng)分析定義的變量

ui(n):第i個普通隊列在接受完服務(wù)之后,查詢轉(zhuǎn)換到中心隊列所耗費的時間;

vi(n):服務(wù)器完成對第i個普通隊列中數(shù)據(jù)信息量的發(fā)送服務(wù)所耗費的時間;

vh(n?):服務(wù)器完成對中心隊列所包含的數(shù)據(jù)信息量的發(fā)送服務(wù)所耗費的時間;

μj(ui):設(shè)定為在ui(n)這段時間長度內(nèi)加入進第j個隊列的數(shù)據(jù)信息量;

ηj(vi):設(shè)定為vi(n)這段時間長度內(nèi)加入進第j個隊列的數(shù)據(jù)信息量;

ηj(vh):設(shè)定為在vh(n?)這段時間內(nèi)加入進第j個隊列的數(shù)據(jù)信息量.

概率母函數(shù)定義為

在tn?時刻系統(tǒng)狀態(tài)變量的概率母函數(shù)為

在tn+1時刻系統(tǒng)狀態(tài)變量的概率母函數(shù)為

式中,Fi(zi)=Ai(Bi(ziFi(zi))),i=1,2,···,N表示服務(wù)器對任意一個隊列,在任一時段內(nèi)到達的數(shù)據(jù)信息量以及在服務(wù)期間到達的數(shù)據(jù)信息量使用完全服務(wù)的方式所需時間的隨機變量的概率母函數(shù)[13].

2 輪詢系統(tǒng)的一階和二階特性

2.1 平均排隊隊長

根據(jù)式(4)和式(5)求得第i個普通隊列的平均排隊隊長的表達式為

同理,采用上述方法可以得到中心隊列的平均排隊隊長的表達式為

gih(h)表示為普通站點i所有的數(shù)據(jù)信息量接受完服務(wù),轉(zhuǎn)換到中心站點之后,這段時間內(nèi)以及在服務(wù)期間進入中心站點的所有數(shù)據(jù)信息量的平均排隊隊長,所以在以下對中心隊列進行分析時會出現(xiàn)多段各不相同的平均排隊隊長和平均等待時間的情況.

2.2 循環(huán)查詢周期

輪詢系統(tǒng)的循環(huán)查詢周期表示為:同一隊列被服務(wù)器前后兩次訪問時刻的時間差,其具體為N+1個隊列按規(guī)定的服務(wù)規(guī)則進行一次服務(wù)所花費時間的統(tǒng)計平均值[14].所以可以計算得到兩級非對稱輪詢系統(tǒng)的循環(huán)周期E(θ).

2.3 二階偏導(dǎo)量

定義:

則由式(4)和式(5)可以得到以下二階偏導(dǎo)量:

將式(18)求和,并利用式(20)化簡得到

2.4 基于循環(huán)查詢周期的近似分析方法

根據(jù)循環(huán)查詢周期的定義得到該隨機變量的概率母函數(shù)為θi(zi),并有如下關(guān)系式:

對此式進行二階求導(dǎo),得到

因為系統(tǒng)的二階特性量有

根據(jù)式(22),式(24)及式(25)得到

根據(jù)式(26)并分別結(jié)合式(22)和式(18)可以得到gih(h,h)和gi(i,i)的近似表達式.

2.5 平均等待時間

信息分組的平均等待時間是指數(shù)據(jù)信息量到達隊列被發(fā)送出去所需的時間.根據(jù)上述計算得到的gi(i,i)和gih(h,h)的近似表達式,分別代入下面兩式即可求得平均等待時間的表達式.

普通站點的平均等待時間為

中心站點的平均等待時間為

3 仿真實驗及性能分析

基于上述所建立的兩級優(yōu)先級非對稱輪詢服務(wù)模型,同時根據(jù)以下所建立的工作條件進行理論值計算和實驗仿真[15?16].

1)各隊列的參數(shù)變量都應(yīng)當(dāng)服從相同的分布,但是各變量并不具備對稱性;

2)任一時隙內(nèi)進入各隊列的數(shù)據(jù)信息量都滿足Poisson分布;

根據(jù)如下表1中所設(shè)置的初始參數(shù)的基礎(chǔ)之上,得到以下圖中服務(wù)模型性能特點的變化情況.

表1 服務(wù)模型的基礎(chǔ)參數(shù)Table 1 Basic parameters of the service model

圖3與圖4展示了普通隊列與中心隊列的平均排隊隊長隨到達率變化的情況,從圖中可以看出在到達率不斷增加的情況下,普通隊列服從于與到達率相同的變化規(guī)律,即到達率變大其也會隨之而變大,當(dāng)然中心隊列亦滿足此種變化形式.同時,可以從圖中分析得到高優(yōu)先級的隊列與低優(yōu)先級隊列的隊長之間的區(qū)分度是比較高的,受到達率影響的情況下,低優(yōu)先級的隊長都遠大于高優(yōu)先級的隊長.

圖3 普通隊列平均排隊隊長隨到達率影響變化(N=5)Fig.3 The average queue length of ordinary queue varies with arrival rate(N=5)

圖4 中心隊列平均排隊隊長隨到達率影響變化(N=5)Fig.4 The average queue length of central queue varies with arrival rate(N=5)

圖5 普通隊列平均排隊隊長隨服務(wù)時間影響變化(N=5)Fig.5 Variation of average queue length with servicetime in ordinary queue(N=5)

從圖5與圖6可以看出普通隊列與中心隊列的平均排隊隊長受服務(wù)時間的影響比較明顯,服務(wù)時間增加時隊長也會隨之而變大.同樣,兩種具有不同優(yōu)先級的隊列,其平均排隊隊長有著很大的差別,很好地說明了輪詢系統(tǒng)的優(yōu)先級得到了較好的區(qū)分.除此之外,圖中1至h與5至h這兩段時長的中心隊列的平均排隊隊長的增長率與其他幾個隊列相比是比較小的.主要原因則由各隊列到達率的不同而引起的,這與理論分析相一致,由式(6)可以看出中心隊列的隊長與到達率成正比關(guān)系,所以這兩段時長到達率較小時,給中心隊列的隊長帶來的影響較小.

表2 兩種模型理論值與實驗值的對比Table 2 Comparison between theoretical values and experimental values of two models

圖6 中心隊列平均排隊隊長隨服務(wù)時間影響變化(N=5)Fig.6 The average queue queue length of central queue varies with service time(N=5)

圖7 循環(huán)查詢周期隨系統(tǒng)負(fù)載影響變化(N=5)Fig.7 Cyclic query cycle varies with system load(N=5)

圖7中系統(tǒng)的負(fù)載是指普通隊列的總負(fù)載,并不包含中心隊列的負(fù)載,主要是為了方便仿真圖形的構(gòu)建,并與其他非對稱模型形成對比,此外需要說明的是中心的負(fù)載的改變,同樣會對系統(tǒng)的特性產(chǎn)生影響.圖7至圖8也是如此情況.從圖6中可以看出,輪詢系統(tǒng)的循環(huán)查詢周期隨著負(fù)載的增大而不斷變大,同時,循環(huán)查詢周期的理論值與實驗值之間有著較好的穩(wěn)合性.

從圖8到圖9可以看出,當(dāng)選取的循環(huán)次數(shù)較大時,平均等待時間的理論值與實驗值是保持一致的且誤差較小.對于同一系統(tǒng)而言,當(dāng)系統(tǒng)的負(fù)載變大時,平均等待時間也是隨之而變大的,同時,系統(tǒng)的隊列數(shù)增加時這種關(guān)系依然存在.系統(tǒng)在同一負(fù)載的情況下,中心隊列的平均等待時間小于普通隊列的平均等待時間,這也很好地說明采用混合的輪詢服務(wù)方式來進行優(yōu)先級的區(qū)分,是有顯著成效的,使得系統(tǒng)的性能得到了一個整體優(yōu)化.綜上所述,該服務(wù)模型運用循環(huán)查詢周期二階特性近似相等的方法得到了平均等待時間的近似解.該種近似方法運用在本文所建立的模型當(dāng)中,比較適用于達到率較小的情況,同時,當(dāng)系統(tǒng)的負(fù)載相對較高時,理論值與實驗仿真值的誤差就會相對變大,此時需要考慮該分析方法的容錯范圍.

表2中展示了非對稱門限服務(wù)與本文所提出模型的性能特性比較,從表2中可以看出當(dāng)兩級優(yōu)先級非對稱輪詢模型普通隊列的總負(fù)載與非對稱門限服務(wù)的總負(fù)載在相同的情況下,兩級優(yōu)先級非對稱模型的平均排隊隊長和平均等待時間都略大于非對稱門限的兩種特性,從另一方面也說明了中心隊列的負(fù)載可以影響整個系統(tǒng)的服務(wù)特性,所以對非對稱性的輪詢服務(wù)系統(tǒng)進一步進行優(yōu)先級的區(qū)分,可以讓具備更高優(yōu)先級的隊列獲得更多的服務(wù)時間和更高的服務(wù)效率.此外兩種非對稱性的模型理論值與實驗值之間都有著較好的吻合性,誤差較小,說明了兩種非對稱模型的服務(wù)特性得到了較好的解析,進一步驗證了模型解析過程的正確性.

圖8 普通隊列平均等待時間受負(fù)載影響變化(N=5)Fig.8 Average waiting time of ordinary queues is affected by load changes(N=5)

圖9 中心隊列平均等待時間受負(fù)載影響變化(N=5)Fig.9 The average waiting time of the central queue is affected by load changes(N=5)

4 結(jié)論

本文采取了一種對稱性輪詢服務(wù)與非對稱輪詢服務(wù)相結(jié)合的區(qū)分優(yōu)先級的輪詢服務(wù),即在具有低優(yōu)先級的普通隊列采用非對稱的門限服務(wù),在具有高優(yōu)先級的中心隊列使用對稱性的完全服務(wù).為了提高系統(tǒng)的利用率,所以本文選擇了非對稱性的輪詢服務(wù),并且運用并行模式的服務(wù)機制構(gòu)建了兩級優(yōu)先非對稱服務(wù)模型.服務(wù)模型的平均排隊隊長和循環(huán)查詢周期,得到了精確的解析.經(jīng)過大量的實驗分析,使用了一種較為合理的方法較優(yōu)的對系統(tǒng)的二階特性量,平均等待時間進行了解析.并通過仿真實驗實驗與理論分析相比較,驗證了模型解析過程的正確性.

除此之外,需要說明的是此模型二階特性量的近似方法并不局限于本文中所使用的分析方法,還有許多的近似方法值得我們?nèi)ミM一步探索,去找到一種更優(yōu)的方法來對平均等待時間進行解析.當(dāng)然,在未來工作當(dāng)中,對其他的一些非對稱性混合服務(wù)模型,如對稱性完全–非對稱性完全、限定–非對稱性門限、門限–非對稱性門限等區(qū)分優(yōu)先級的兩級非對稱服務(wù)模型進行探討是非常有意義的.