連續時間完全-限定（K=2）兩級輪詢系統性能分析

楊志軍，黃文潔，丁洪偉

（1.云南大學信息學院，云南昆明 650500；2.云南省教育廳教學儀器裝備中心，云南昆明 650223；3.云南師范大學教育部民族教育信息化重點實驗室，云南 昆明 650500）

0 引言

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

針對優先級區分的問題：文獻［14］通過改變門限服務的級數進行控制，提高了系統的靈活性；文獻［15-16］提出了并行兩級服務模型，但只分析了一階特性；文獻［17］分析了2 種信息水平下不同優先級客戶在加入或拒絕困境下的戰略服務；文獻［18］提出了對稱完全-非對稱門限兩級服務模型。

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

基于上述分析，本文提出中心站點采用完全服務、普通站點采用限定（K=2）服務的連續時間完全-限定（K=2）兩級輪詢控制模型，在完全-限定（K=1）的基礎上增加一次性發送數據包的量，從而降低網絡時延，解決區分優先級和保證普通站點公平性的問題，同時提升普通站點的性能。使用連續時間分析，搭建數學模型，通過概率母函數［23］推導出一階特性和二階特性，最后使用MATLAB 軟件仿真，驗證理論分析的正確性。

1 系統模型

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

圖1 兩級輪詢系統模型Fig.1 Two-level polling system model

2 數學模型

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

2.1 系統工作條件

根據輪詢系統的基本模型，結合輪詢控制機制和特點，對系統的工作條件作如下定義：

1）進入各個站點中的數據包的到達過程是滿足相互獨立的Poisson 分布，普通站點的到達率是λi，中心站點的到達率是λh。

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

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

4）服務系統中站點都擁有很大的容量，不會出現數據包丟失的情況。

5）服務器對站點中的數據包按照先到先服務（FCFS）的原則進行服務。

2.2 隨機變量

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

表1 隨機變量Table 1 Random variables

2.3 概率母函數

tn時刻服務器為i號普通站點提供限定K=2 服務，tn*時刻服務器轉向中心站點提供完全服務，tn+1時刻服務器轉向i+1 號普通節點提供服務。由此得到下列關系式：

為了構建系統的數學模型，通過概率母函數進行探究，系統滿足+ρh<1 時保持穩定。

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

3 系統性能分析

3.1 平均排隊隊長

平均排隊隊長是指tn時刻i號站點開始傳輸數據時，第j號站點存儲器中平均存儲的數據包數為gi(j)，則：

通過式（4）～式（6）得到中心站點的平均排隊隊長：

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

3.2 系統的二階特性

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

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

3.3 平均時延

平均時延是指數據包從到達站點到被發送出去所需要的時間。設定E(wi)為普通站點的平均時延，E(wh)為中心站點的平均時延，根據上述計算得到的表達式，可得到平均時延。

普通站點的平均時延為：

中心站點的平均時延為：

4 仿真實驗

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

4.1 結果分析

在實驗中，改變站點個數、到達率、服務率和轉換率的值，比較中心站點和普通站點的平均隊長、時延，如表2 所示。

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

表2 是連續時間兩級完全-限定（K=2）服務輪詢系統的不同參數下仿真值和期望值的對比，由圖中可以看出，仿真值與期望值基本吻合，驗證了理論分析的正確性。

在不同網絡規模下，改變普通站點和中心站點的到達率和服務率，可以看出，不論是普通站點的到達率和服務率大，還是中心站點的到達率和服務時間大，亦或者是相等，對于平均時延和平均隊長來說，均是普通站點大于中心站點，表明了該連續時間兩級完全-限定（K=2）模型擁有較強的區分優先級能力。

平均隊長和平均時延不僅受到達率的影響，還受服務時間等參數的影響。圖2（a）和圖2（b）分別顯示了隊長與到達率和服務時間的關系。圖3 描述了平均時延隨著到達率的變化規律。可以看出，期望值與仿真值基本一致，表明系統的可行性。

圖2 平均隊長與參數的關系Fig.2 Relationship between average length and parameters

圖3 平均時延隨到達率的變化Fig.3 Change of average time delay with arrival rate

當系統數據包到達率或服務時間增加時，普通站點和中心站點的平均隊長也在隨著增加。觀察普通站點和中心站點的隊長和時延，可以發現，普通站點的隊長和時延遠遠大于中心站點，表明該系統能夠很好地區分優先級。進一步分析隊長和時延的上升趨勢，普通站點隨著到達率的增加快速上升，趨勢變化明顯，而中心站點變化趨勢較為緩慢，受到達率的影響較小。從輪詢控制機制解析，該系統模型將N+1 個站點劃分為N個普通站點和1 個中心站點，在每一次服務過程中，中心站點得以N次完全服務的機會，而每一個普通站點只利用一次限定（K=2）服務，所以從利用服務器的次數，中心站點的隊長和時延都遠遠小于普通站點，可以最大程度上保證中心站點的服務質量，更好地適應區分優先級的要求。

4.2 模型對比分析

為了進一步分析本文模型的性能優勢，對比文獻［6］一級完全服務模型、文獻［8］一級限定（K=2）模型、兩級完全-限定（K=1）模型和門限-完全服務模型，結果如圖4～圖7 所示。

圖4 一級模型與本文模型平均隊長的變化Fig.4 Change of average length of the one-level model and the model in this paper

圖4、圖5 是文獻［6，8］模型與本文模型的對比。隨著到達率的改變探究隊長和時延的變化規律，可知，當網絡規模相同，即總站點數相同的情況下，設置一級服務的站點數為N1，兩級服務的站點數為N2+1，其中N2為普通站點數量，1 為中心站點數量，且N1=N2+1。可見，一級服務的平均隊長和時延均大于兩級服務系統的普通站點的隊長和時延，且遠遠大于中心站點，這充分表明了兩級輪詢系統在網絡規模相同時，既可以區分業務優先級，又可以提升普通站點的性能。在圖4 中，普通站點的性能隨著到達率的增加而迅速得到優化，到達率較低時，一級服務的隊長與兩級服務隊長差距不大。在圖5 中，到達率從低到高增加時，兩級服務時延均小于一級服務時延，從始至終，兩級服務的性能都優于一級服務，說明中心站點使得兩級輪詢系統的性能得到改變。

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

圖6 和圖7 是完全-限定（K=1）模型和門限-完全模型與本文模型的對比。在系統參數相同條件下，完全-限定（K=1）的隊長和時延均大于本文模型，說明增加限定服務K的值能夠優化普通站點的性能。雖然門限-完全模型的普通站點隊長和時延略小于本文模型，但是對于中心站點，門限-完全>完全-限定（K=1）>完全-限定（K=2），表明本文模型擁有更高的優先級。

圖6 3 種模型平均隊長的變化Fig.6 Change of average length of the three models

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

5 結束語

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