連續(xù)時(shí)間完全-限定（K=2）兩級(jí)輪詢系統(tǒng)性能分析

楊志軍，黃文潔，丁洪偉

（1.云南大學(xué)信息學(xué)院，云南昆明 650500；2.云南省教育廳教學(xué)儀器裝備中心，云南昆明 650223；3.云南師范大學(xué)教育部民族教育信息化重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650500）

0 引言

輪詢系統(tǒng)表示一類調(diào)度控制模型，其因具有較好的公平性和無競(jìng)爭(zhēng)性，可以實(shí)現(xiàn)有限資源的有效分配與共享，在通信網(wǎng)絡(luò)系統(tǒng)、工業(yè)控制和交通運(yùn)輸中得到廣泛的應(yīng)用［1-3］。根據(jù)查詢時(shí)間節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包個(gè)數(shù)，可以將其分為門限服務(wù)［4-5］、完全服務(wù)［6］、限定服務(wù)［7-8］3 種輪詢機(jī)制。近年來，隨著信息技術(shù)的高速發(fā)展，很多研究者以得到更好的系統(tǒng)性能為目標(biāo)改進(jìn)了輪詢系統(tǒng)。其中，文獻(xiàn)［9-10］針對(duì)實(shí)際信道中存在噪聲等因素導(dǎo)致數(shù)據(jù)傳輸出錯(cuò)的情況，提出了重傳機(jī)制的輪詢系統(tǒng)。但在實(shí)際應(yīng)用中，常常需要不同服務(wù)策略服務(wù)不同業(yè)務(wù)信息或不同站點(diǎn)類型，在同一系統(tǒng)中能夠區(qū)分優(yōu)先級(jí)業(yè)務(wù)［11-13］。因此，對(duì)整個(gè)輪詢系統(tǒng)采用單一的服務(wù)策略不能滿足區(qū)分優(yōu)先級(jí)的要求，需要混合使用服務(wù)策略，使性能得到更大的優(yōu)化。

針對(duì)優(yōu)先級(jí)區(qū)分的問題：文獻(xiàn)［14］通過改變門限服務(wù)的級(jí)數(shù)進(jìn)行控制，提高了系統(tǒng)的靈活性；文獻(xiàn)［15-16］提出了并行兩級(jí)服務(wù)模型，但只分析了一階特性；文獻(xiàn)［17］分析了2 種信息水平下不同優(yōu)先級(jí)客戶在加入或拒絕困境下的戰(zhàn)略服務(wù)；文獻(xiàn)［18］提出了對(duì)稱完全-非對(duì)稱門限兩級(jí)服務(wù)模型。

上述文獻(xiàn)中都是采用離散時(shí)間分析方法，計(jì)算難度較大。為了降低計(jì)算難度，研究者提出了使用拉普拉斯變換方式的連續(xù)時(shí)間型分析方法以簡(jiǎn)化計(jì)算：文獻(xiàn)［19］提出了連續(xù)時(shí)間兩級(jí)完全輪詢控制系統(tǒng)，普通站點(diǎn)和中心站點(diǎn)均采用完全服務(wù)，降低了時(shí)延；文獻(xiàn)［20］提出了完全-門限服務(wù)輪詢系統(tǒng)，保證了服務(wù)質(zhì)量；文獻(xiàn)［21-22］分別提出了完全-限定（K=1）兩級(jí)輪詢控制系統(tǒng)，以適應(yīng)系統(tǒng)中不同優(yōu)先級(jí)業(yè)務(wù)的服務(wù)需求，雖然通過普通站點(diǎn)采用限定（K=1）服務(wù)的方式，保證了普通站點(diǎn)的公平性，但是一次性發(fā)送數(shù)據(jù)包的量較少，等待時(shí)間較長(zhǎng)；而文獻(xiàn)［7］研究了限定（K=N）服務(wù)輪詢系統(tǒng)，為了區(qū)分優(yōu)先級(jí)和不同服務(wù)類型，改變K的取值，隨著K值越大，一次發(fā)送的信息分組越多，優(yōu)先級(jí)越高，并且隨著現(xiàn)代網(wǎng)絡(luò)技術(shù)的快速發(fā)展，限定（K=1）服務(wù)策略不能滿足實(shí)際需求，需要使用限定（K>1）服務(wù)策略。

基于上述分析，本文提出中心站點(diǎn)采用完全服務(wù)、普通站點(diǎn)采用限定（K=2）服務(wù)的連續(xù)時(shí)間完全-限定（K=2）兩級(jí)輪詢控制模型，在完全-限定（K=1）的基礎(chǔ)上增加一次性發(fā)送數(shù)據(jù)包的量，從而降低網(wǎng)絡(luò)時(shí)延，解決區(qū)分優(yōu)先級(jí)和保證普通站點(diǎn)公平性的問題，同時(shí)提升普通站點(diǎn)的性能。使用連續(xù)時(shí)間分析，搭建數(shù)學(xué)模型，通過概率母函數(shù)［23］推導(dǎo)出一階特性和二階特性，最后使用MATLAB 軟件仿真，驗(yàn)證理論分析的正確性。

1 系統(tǒng)模型

連續(xù)時(shí)間完全-限定（K=2）兩級(jí)輪詢系統(tǒng)模型如圖1 所示。該系統(tǒng)由1 個(gè)服務(wù)器、1 個(gè)中心站點(diǎn)和N個(gè)普通站點(diǎn)組成。其中，中心站點(diǎn)采用完全服務(wù)策略，用下標(biāo)h來表示；普通站點(diǎn)采用限定（K=2）服務(wù)策略，序號(hào)用i(i=1,2,…,N)來表示。服務(wù)器首先利用完全策略對(duì)中心站點(diǎn)服務(wù)，直到中心站點(diǎn)中所有數(shù)據(jù)包發(fā)送完畢，然后服務(wù)器轉(zhuǎn)移到i(i=1,2,…,N)號(hào)普通站點(diǎn)按限定（K=2）策略進(jìn)行服務(wù)，待服務(wù)結(jié)束后，再次轉(zhuǎn)移到中心站點(diǎn)，服務(wù)結(jié)束后，開始對(duì)i+1 號(hào)普通站點(diǎn)服務(wù)，即h→1 →h→2 →…→i→h→i+1 →…→N→h→1。中心站點(diǎn)到普通站點(diǎn)使用同步處理，直接對(duì)普通站點(diǎn)進(jìn)行服務(wù)，與普通站點(diǎn)向中心站點(diǎn)轉(zhuǎn)換相比，少了一個(gè)轉(zhuǎn)換時(shí)間。

圖1 兩級(jí)輪詢系統(tǒng)模型Fig.1 Two-level polling system model

2 數(shù)學(xué)模型

通常使用平均隊(duì)長(zhǎng)和平均時(shí)延分析系統(tǒng)性能。在相同網(wǎng)絡(luò)規(guī)模下，平均隊(duì)長(zhǎng)和時(shí)延越小，說明系統(tǒng)性能越好，服務(wù)效率越高［24-25］。因此，下文定義系統(tǒng)的工作條件、隨機(jī)變量和概率母函數(shù)來分析該兩級(jí)完全-限定（K=2）輪詢系統(tǒng)的性能。

2.1 系統(tǒng)工作條件

根據(jù)輪詢系統(tǒng)的基本模型，結(jié)合輪詢控制機(jī)制和特點(diǎn)，對(duì)系統(tǒng)的工作條件作如下定義：

1）進(jìn)入各個(gè)站點(diǎn)中的數(shù)據(jù)包的到達(dá)過程是滿足相互獨(dú)立的Poisson 分布，普通站點(diǎn)的到達(dá)率是λi，中心站點(diǎn)的到達(dá)率是λh。

2）服務(wù)站點(diǎn)i的時(shí)間滿足相互獨(dú)立、同分布的概率分布，其隨機(jī)變量拉普拉斯變換（LST）為Bi(s)，均值為β=-B'(0)，二階原點(diǎn)矩為vβ=B″(0)；服務(wù)中心站點(diǎn)h的數(shù)據(jù)包的LST 為Bh(s)，均值為βh=-(0)，二階原點(diǎn)矩為vh=(0)。

3）服務(wù)器在任意2 個(gè)相臨近的站點(diǎn)間轉(zhuǎn)換的時(shí)間變量滿足相互獨(dú)立且同分布的概率分布，其隨機(jī)變量的LST 為Ri(s)，均值為γ=-R'(0)，二階原點(diǎn)矩為vγ=(0)。

4）服務(wù)系統(tǒng)中站點(diǎn)都擁有很大的容量，不會(huì)出現(xiàn)數(shù)據(jù)包丟失的情況。

5）服務(wù)器對(duì)站點(diǎn)中的數(shù)據(jù)包按照先到先服務(wù)（FCFS）的原則進(jìn)行服務(wù)。

2.2 隨機(jī)變量

假設(shè)在tn時(shí)刻，服務(wù)器開始對(duì)i(i=1,2,…,N)號(hào)普通站點(diǎn)進(jìn)行服務(wù)，此時(shí)隨機(jī)變量ξi(n)是第i個(gè)站點(diǎn)中等待發(fā)送的數(shù)據(jù)包數(shù)，定義中心站點(diǎn)h的數(shù)據(jù)包數(shù)為ξh(n)，則整個(gè)系統(tǒng)的隨機(jī)變量為{ξ1(n),ξ2(n),…,ξi(n),…,ξN(n),ξh(n)}；在tn*時(shí)刻，服務(wù)器按照限定K=2 完成對(duì)i號(hào)普通站點(diǎn)的服務(wù)，轉(zhuǎn)向中心站點(diǎn)提供完全服務(wù)，系統(tǒng)的隨機(jī)變量為{ξ1(n*),ξ2(n*),…,ξi(n*),…,ξN(n*),ξh(n*)}；在tn+1時(shí)刻，中心站點(diǎn)服務(wù)結(jié)束后，再次轉(zhuǎn)向服務(wù)i+1 號(hào)站點(diǎn)，此時(shí)狀態(tài)變量為{ξ1(n+1),ξ2(n+1),…,ξi(n+1),…,}ξN(n+1),ξh(n+1) 。為了分析系統(tǒng)模型，定義隨機(jī)變量，如表1 所示。

表1 隨機(jī)變量Table 1 Random variables

2.3 概率母函數(shù)

tn時(shí)刻服務(wù)器為i號(hào)普通站點(diǎn)提供限定K=2 服務(wù)，tn*時(shí)刻服務(wù)器轉(zhuǎn)向中心站點(diǎn)提供完全服務(wù)，tn+1時(shí)刻服務(wù)器轉(zhuǎn)向i+1 號(hào)普通節(jié)點(diǎn)提供服務(wù)。由此得到下列關(guān)系式：

為了構(gòu)建系統(tǒng)的數(shù)學(xué)模型，通過概率母函數(shù)進(jìn)行探究，系統(tǒng)滿足+ρh<1 時(shí)保持穩(wěn)定。

定義tn和tn*時(shí)刻系統(tǒng)狀態(tài)變量的概率母函數(shù)分別為式（2）和式（3），服務(wù)器在tn*時(shí)刻輪詢服務(wù)中心站點(diǎn)，系統(tǒng)狀態(tài)變量的概率母函數(shù)為式（4），其中，i=1,2,…,N，tn+1時(shí)刻系統(tǒng)的狀態(tài)變量函數(shù)為式（5），其中，Hh(s)=B(s+λh(1-Hh(s)))。

3 系統(tǒng)性能分析

3.1 平均排隊(duì)隊(duì)長(zhǎng)

平均排隊(duì)隊(duì)長(zhǎng)是指tn時(shí)刻i號(hào)站點(diǎn)開始傳輸數(shù)據(jù)時(shí)，第j號(hào)站點(diǎn)存儲(chǔ)器中平均存儲(chǔ)的數(shù)據(jù)包數(shù)為gi(j)，則：

通過式（4）～式（6）得到中心站點(diǎn)的平均排隊(duì)隊(duì)長(zhǎng)：

其中，ρh=λh βh,ρi=λi βi。

3.2 系統(tǒng)的二階特性

定義普通站點(diǎn)的二階偏導(dǎo)特性為gi(j,k)，中心站點(diǎn)的二階偏導(dǎo)特性為gih(j,k)，由概率母函數(shù)得：

將式（4）、式（5）代入式（8）、式（9），則tn*時(shí)刻有式（10），tn+1時(shí)刻有式（11）、式（12），通過對(duì)式（10）～式（12）進(jìn)行化簡(jiǎn)迭代，根據(jù)系統(tǒng)模型的特性，可計(jì)算普通站點(diǎn)的隊(duì)長(zhǎng)gi(i)，如式（13）所示。

3.3 平均時(shí)延

平均時(shí)延是指數(shù)據(jù)包從到達(dá)站點(diǎn)到被發(fā)送出去所需要的時(shí)間。設(shè)定E(wi)為普通站點(diǎn)的平均時(shí)延，E(wh)為中心站點(diǎn)的平均時(shí)延，根據(jù)上述計(jì)算得到的表達(dá)式，可得到平均時(shí)延。

普通站點(diǎn)的平均時(shí)延為：

中心站點(diǎn)的平均時(shí)延為：

4 仿真實(shí)驗(yàn)

根據(jù)上述建立的完全-限定（K=2）系統(tǒng)模型，通過MATLAB 進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證理論分析的正確性。假設(shè)在仿真實(shí)驗(yàn)中，全部都是理想狀態(tài)，數(shù)據(jù)包全部成功發(fā)送，沒有出現(xiàn)信息丟失的問題。以時(shí)隙為單位分割時(shí)間軸，設(shè)定每一個(gè)時(shí)隙（slot）的大小為20 μs，一個(gè)數(shù)據(jù)包（packet）長(zhǎng)度為1 100 Byte，并設(shè)置循環(huán)次數(shù)為10 萬次。

4.1 結(jié)果分析

在實(shí)驗(yàn)中，改變站點(diǎn)個(gè)數(shù)、到達(dá)率、服務(wù)率和轉(zhuǎn)換率的值，比較中心站點(diǎn)和普通站點(diǎn)的平均隊(duì)長(zhǎng)、時(shí)延，如表2 所示。

表2 不同參數(shù)下中心站點(diǎn)和普通站點(diǎn)的仿真值和期望值Table 2 Simulation values and expected values of central site and common site under different parameters

表2 是連續(xù)時(shí)間兩級(jí)完全-限定（K=2）服務(wù)輪詢系統(tǒng)的不同參數(shù)下仿真值和期望值的對(duì)比，由圖中可以看出，仿真值與期望值基本吻合，驗(yàn)證了理論分析的正確性。

在不同網(wǎng)絡(luò)規(guī)模下，改變普通站點(diǎn)和中心站點(diǎn)的到達(dá)率和服務(wù)率，可以看出，不論是普通站點(diǎn)的到達(dá)率和服務(wù)率大，還是中心站點(diǎn)的到達(dá)率和服務(wù)時(shí)間大，亦或者是相等，對(duì)于平均時(shí)延和平均隊(duì)長(zhǎng)來說，均是普通站點(diǎn)大于中心站點(diǎn)，表明了該連續(xù)時(shí)間兩級(jí)完全-限定（K=2）模型擁有較強(qiáng)的區(qū)分優(yōu)先級(jí)能力。

平均隊(duì)長(zhǎng)和平均時(shí)延不僅受到達(dá)率的影響，還受服務(wù)時(shí)間等參數(shù)的影響。圖2（a）和圖2（b）分別顯示了隊(duì)長(zhǎng)與到達(dá)率和服務(wù)時(shí)間的關(guān)系。圖3 描述了平均時(shí)延隨著到達(dá)率的變化規(guī)律?？梢钥闯?，期望值與仿真值基本一致，表明系統(tǒng)的可行性。

圖2 平均隊(duì)長(zhǎng)與參數(shù)的關(guān)系Fig.2 Relationship between average length and parameters

圖3 平均時(shí)延隨到達(dá)率的變化Fig.3 Change of average time delay with arrival rate

當(dāng)系統(tǒng)數(shù)據(jù)包到達(dá)率或服務(wù)時(shí)間增加時(shí)，普通站點(diǎn)和中心站點(diǎn)的平均隊(duì)長(zhǎng)也在隨著增加。觀察普通站點(diǎn)和中心站點(diǎn)的隊(duì)長(zhǎng)和時(shí)延，可以發(fā)現(xiàn)，普通站點(diǎn)的隊(duì)長(zhǎng)和時(shí)延遠(yuǎn)遠(yuǎn)大于中心站點(diǎn)，表明該系統(tǒng)能夠很好地區(qū)分優(yōu)先級(jí)。進(jìn)一步分析隊(duì)長(zhǎng)和時(shí)延的上升趨勢(shì)，普通站點(diǎn)隨著到達(dá)率的增加快速上升，趨勢(shì)變化明顯，而中心站點(diǎn)變化趨勢(shì)較為緩慢，受到達(dá)率的影響較小。從輪詢控制機(jī)制解析，該系統(tǒng)模型將N+1 個(gè)站點(diǎn)劃分為N個(gè)普通站點(diǎn)和1 個(gè)中心站點(diǎn)，在每一次服務(wù)過程中，中心站點(diǎn)得以N次完全服務(wù)的機(jī)會(huì)，而每一個(gè)普通站點(diǎn)只利用一次限定（K=2）服務(wù)，所以從利用服務(wù)器的次數(shù)，中心站點(diǎn)的隊(duì)長(zhǎng)和時(shí)延都遠(yuǎn)遠(yuǎn)小于普通站點(diǎn)，可以最大程度上保證中心站點(diǎn)的服務(wù)質(zhì)量，更好地適應(yīng)區(qū)分優(yōu)先級(jí)的要求。

4.2 模型對(duì)比分析

為了進(jìn)一步分析本文模型的性能優(yōu)勢(shì)，對(duì)比文獻(xiàn)［6］一級(jí)完全服務(wù)模型、文獻(xiàn)［8］一級(jí)限定（K=2）模型、兩級(jí)完全-限定（K=1）模型和門限-完全服務(wù)模型，結(jié)果如圖4～圖7 所示。

圖4 一級(jí)模型與本文模型平均隊(duì)長(zhǎng)的變化Fig.4 Change of average length of the one-level model and the model in this paper

圖4、圖5 是文獻(xiàn)［6，8］模型與本文模型的對(duì)比。隨著到達(dá)率的改變探究隊(duì)長(zhǎng)和時(shí)延的變化規(guī)律，可知，當(dāng)網(wǎng)絡(luò)規(guī)模相同，即總站點(diǎn)數(shù)相同的情況下，設(shè)置一級(jí)服務(wù)的站點(diǎn)數(shù)為N1，兩級(jí)服務(wù)的站點(diǎn)數(shù)為N2+1，其中N2為普通站點(diǎn)數(shù)量，1 為中心站點(diǎn)數(shù)量，且N1=N2+1?？梢?，一級(jí)服務(wù)的平均隊(duì)長(zhǎng)和時(shí)延均大于兩級(jí)服務(wù)系統(tǒng)的普通站點(diǎn)的隊(duì)長(zhǎng)和時(shí)延，且遠(yuǎn)遠(yuǎn)大于中心站點(diǎn)，這充分表明了兩級(jí)輪詢系統(tǒng)在網(wǎng)絡(luò)規(guī)模相同時(shí)，既可以區(qū)分業(yè)務(wù)優(yōu)先級(jí)，又可以提升普通站點(diǎn)的性能。在圖4 中，普通站點(diǎn)的性能隨著到達(dá)率的增加而迅速得到優(yōu)化，到達(dá)率較低時(shí)，一級(jí)服務(wù)的隊(duì)長(zhǎng)與兩級(jí)服務(wù)隊(duì)長(zhǎng)差距不大。在圖5 中，到達(dá)率從低到高增加時(shí)，兩級(jí)服務(wù)時(shí)延均小于一級(jí)服務(wù)時(shí)延，從始至終，兩級(jí)服務(wù)的性能都優(yōu)于一級(jí)服務(wù)，說明中心站點(diǎn)使得兩級(jí)輪詢系統(tǒng)的性能得到改變。

圖5 一級(jí)模型與本文模型平均時(shí)延的變化Fig.5 Change of average time delay of the one-level model and the model in this paper

圖6 和圖7 是完全-限定（K=1）模型和門限-完全模型與本文模型的對(duì)比。在系統(tǒng)參數(shù)相同條件下，完全-限定（K=1）的隊(duì)長(zhǎng)和時(shí)延均大于本文模型，說明增加限定服務(wù)K的值能夠優(yōu)化普通站點(diǎn)的性能。雖然門限-完全模型的普通站點(diǎn)隊(duì)長(zhǎng)和時(shí)延略小于本文模型，但是對(duì)于中心站點(diǎn)，門限-完全>完全-限定（K=1）>完全-限定（K=2），表明本文模型擁有更高的優(yōu)先級(jí)。

圖6 3 種模型平均隊(duì)長(zhǎng)的變化Fig.6 Change of average length of the three models

圖7 3 種模型平均時(shí)延的變化Fig.7 Change of average time delay of the three models

5 結(jié)束語

針對(duì)完全-限定（K=1）模型一次發(fā)送數(shù)據(jù)包較少的情況，本文提出完全-限定（K=2）兩級(jí)模型。通過數(shù)學(xué)方式得到數(shù)據(jù)包的平均隊(duì)長(zhǎng)和時(shí)延表達(dá)式，并進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證理論分析的正確性和系統(tǒng)性能。通過分析可知，與單級(jí)服務(wù)模型相比，該系統(tǒng)既能滿足業(yè)務(wù)優(yōu)先級(jí)的區(qū)分，又能提升普通業(yè)務(wù)性能。與兩級(jí)完全-限定（K=1）模型相比，該模型降低了時(shí)延，提高了服務(wù)效率，充分表明了增加限定服務(wù)K值可以有效提高系統(tǒng)性能。與門限-完全兩級(jí)服務(wù)模型相比，該模型有更高的優(yōu)先級(jí)。在后期工作中，首先可劃分多個(gè)優(yōu)先級(jí)來探究系統(tǒng)性能；其次可針對(duì)各個(gè)站點(diǎn)特性的隨機(jī)變量不相互獨(dú)立的問題，提出更具有廣泛實(shí)用性的非對(duì)稱輪詢系統(tǒng)。