連續時間完全服務與門限服務兩級輪詢系統性能研究

楊志軍 劉征 丁洪偉

摘 要：在信息分組以連續時間規律到達系統的基礎上，對于輪詢系統中不同優先級的業務問題，提出區分優先級的兩級輪詢服務模型。首先，在該模型中，低優先級站點采用門限服務，高優先級站點采用完全服務;然后，在高優先級轉低優先級時，將傳輸服務與轉移查詢并行處理來降低服務器在查詢轉換期間所耗費的時間，提高輪詢系統的效率;最后，運用馬爾可夫鏈和概率母函數的方法建立了系統的數學模型，通過對數學模型精確解析，得到了連續時間兩級服務系統每個站點的平均排隊隊長和平均等待時間的表達式，精確解析出平均排隊隊長和平均等待時間的值。仿真實驗結果表明：理論計算值與實驗仿真值近似相等，說明理論分析正確合理。該模型既能保障低優先級站點服務質量，又能為高優先級站點提供優質服務。

關鍵詞：輪詢系統;優先級;平均排隊隊長;平均等待時間;概率母函數

Abstract： For the fact that information groups arrive at the system in a continuous time， a two-level polling service model with different priorities was proposed for the business problems of different priorities in the polling system. Firstly， gated service was used in sites with low priority， and exhaustive service was used in sites with high priority. Then， when high priority turned into low priority， the transmission service and the transfer query were processed in parallel to reduce the time cost of server during query conversion， improving the efficiency of polling system. Finally， the mathematical model of system was established by using Markov chain and probabilistic parent function. By accurately analyzing the mathematical model， the expressions of average queue length and average waiting time of each station of continuous-time two-level service system were obtained. The simulation results show that the theoretical calculation value was approximately equal to the experimental simulation value， indicating that the theoretical analysis is correct and reasonable. The model provides high-quality services for high-priority sites while maintaining the quality of services in low-priority sites.

Key words： polling system; priority; average queue length; average waiting time; probabilistic parent function

0 引言

輪詢是一種資源調度控制的方法，通過這種方法可以實現資源的有效分配并實現資源共享[1-2]。根據到達系統的信息分組以離散時間或連續時間規律到達將輪詢服務系統分為離散時間輪詢系統和連續時間輪詢系統。按服務策略可以分為門限、完全和限定三種輪詢服務系統[3-4]，而隨著不斷的研究，在三種服務策略的基礎上區分優先級的混合服務策略成為了人們研究的重點。在近幾年的研究中，提出了各種各樣的區分優先級的混合服務策略。在這些策略中，輪詢系統既保證了隊列優先級的需求，又避免空閑查詢時空閑造成的時間延遲，達到了提高系統利用率、減少時延的效果[5]。通過對區分優先級的混合服務策略系統平均排隊隊長、循環周期和平均等待時間等特性的研究，驗證了區分優先級帶來的性能提升。由于區分優先級對系統性能上的提升，該類輪詢服務系統可以被廣泛應用于各行各業中。在通信網絡中，可以用于藍牙技術和IEEE 802.11無線局域網的研究或是在Web服務器的路由器和I/O子系統中的調度策略[5-6];在訂單分揀中，優先級輪詢控制系統具有良好的穩定性和高效率，確保了優先訂單顧客得到更優質的服務以及每一個顧客享有的同等的公平性[7-8];在軍事領域中，可以更好地實現整個作戰范圍內的戰場資源共享，最終實現戰場指揮、通信、控制、情報、信息以及綜合保障等功能的一體化[9-10]。

輪詢系統的三個基礎模型適用于不同的環境。完全服務是一種簡單、可靠、有效的服務策略，采用這種服務策略的系統平均排隊隊長和平均等待時延最短，非常適合于數據信息量少且高優先級的站點;限定服務的服務規則是一個站點接受服務時，站點內有且只有一個信息分組被服務，所以，當到達普通站點的信息分組數較大時，采用限定服務的輪詢系統平均排隊隊長和信息分組平均等待時間會過長。當信息分組到達數較小時，就可以考慮采用限定服務。本文設定普通站點信息分組到達數較大時，采用門限服務，所以，本文針對連續時間的輪詢服務系統，提出區分優先級的完全門限服務策略的兩級控制輪詢系統模型[11-13]。在該模型中，普通站點（N個）采取門限服務，中心站點（1個）采取完全服務，服務完一個普通站點就開始服務中心站點，當中心站點服務完時，又開始服務下一個普通站點。針對上述過程，本文首先通過馬爾可夫鏈和概率母函數建立其數學模型，再推出其一階特性量平均排隊隊長和循環查詢周期的精確表達式;然后對模型的二階特性量進行了分析，在此基礎上對平均等待時間進行了解析;最后，通過Matlab仿真對理論結果進行了驗證。

1 系統模型

連續時間兩級優先級輪詢控制系統由一個服務器和N+1個站點組成。因為實際生活中，服務系統中往往會出現一個服務質量要求較高的中心任務或核心任務，其他多個普通業務服務要求質量較低，普通業務之間需要公平對待地實際需求，所以，本文中N個站點為普通站點采取門限服務策略，1個站點為中心站點采取完全服務策略。在服務過程中，服務器優先對高優先級的中心站點服務，當中心站點的所有數據信息量發送完時，服務器開始對i（i=1，2，…，N）站點普通站點服務，在該模型中，中心站點轉普通站點采用并行服務模式，所以當服務器從中心站點轉向普通站點時，就不需要一個查詢轉換時間，直接對普通站點進行服務。當普通站點i完成服務時，服務器經歷一個查詢轉換時間再一次轉向中心站點對其服務，服務完成后，對i+1號普通站點服務，該模型查詢順序如圖1所示。

設定在tn時刻，服務器開始對普通站點i（i=1，2，…，N）進行服務，定義隨機變量ξi（n）是第i個站點中等待發送的數據信息量，h表示中心站點，定義h上的數據信息量為ξh（n），所以，在tn時刻，整個系統狀態隨機變量為{ξ1（n），ξ2（n），…，ξN（n），ξh（n）};設定tn*時刻，服務器從站點i轉向中心站點h服務，定義系統狀態隨機變量為{ξ1（n*），ξ2（n*），…，ξN（n*），ξh（n*）};設tn+1時刻，普通站點i+1開始接受服務，定義系統狀態變量為{ξ1（n+1），ξ2（n+1），…，ξN（n+1），ξh（n+1）}。

系統的狀態可以用馬爾可夫鏈來描述，該馬爾可夫鏈是非周期的和各態歷經的。

1.1 系統工作條件

根據輪詢系統基本模型所示，同時結合其控制機制和特點，對系統工作條件作如下設定：

1）進入各個站點內等待發送的數據信息量的到達過程是相互獨立的Poisson分布，到達率是λ;

2）任何一個站點發送信息分組的時間變量服從于相互獨立的、同分布的概率分布，其變量的拉普拉斯變換（Laplace Transform， LST縮寫詞中的S，對應英文全稱中的哪個單詞？英文全稱正確嗎？請明確。回復：正確，其英文全稱及縮寫是參考大學已學的《信號與系統》這本書以及多篇畢業論文寫的，按照我的理解是LST的意思是拉普拉斯S變換，因為在拉普拉斯變換中是將時域t轉換為S域，即將t轉換為s。）為（s），均值為β=-′（0），二階原點距為υβ=″（0）;

3）任何兩個相鄰站點之間的查詢轉換時間變量服從于相互獨立的、同分布的概率分布，其變量的拉普拉斯變換為（s），均值為γ=-′（0），二階原點距為υγ=″（0）;

4）中心站點對在任一時隙內到達的數據信息量進行完全服務所需時間的隨機變量服從于一個相互獨立、同分布的概率分布，其分布的概率母函數為H（z）;

5）設定服務系統中任何一個隊列的緩存容量足夠大，不存在數據信息量丟失的情況發生;

6）每一個加入進隊列的數據信息量，將會按照先到先服務（First Come First Served， FCFS）的方法接受服務。

定義隨機變量如下：

ui（n）表示服務器從普通站點i查詢轉換到中心站點h所耗費的時間;vi（n）表示普通站點i向服務器發送數據信息量所耗費的時間;vh（n*）表示中心站點h向服務器發送數據信息量所耗費的時間; μj（ui）表示在ui（n）時間內進入第j（j=1，2，…，N，h）個站點的數據信息量;ηj（vi）表示在vi（n）時間內進入第j（j=1，2，…，N，h）個站點的數據信息量;ηj（vh）表示在vh（n*）時間內進入第j（j=1，2，…，N，h）個站點的數據信息量。

1.2 概率母函數

為構建該模型系統的數學模型，本文引入了概率母函數。上述馬爾可夫鏈在∑Ni=1λi βi+λh βh=∑Ni=1ρi+ρh<1的條件下達到平穩狀態[14]，在平穩狀態下的概率母函數為：

對連續時間型系統進行分析時，需要對系統關鍵參數進行拉普拉斯變換。函數的拉普拉斯變換定義為：

對于以參數λ到達的泊松過程，時間t內到達的顧客數對應的概率母函數為：

在tn*時刻，服務器開始對中心站點h服務時，系統狀態變量的概率母函數為：

在tn+1時刻，服務器開始對i+1號普通站點服務時，系統狀態變量的概率母函數為：

2 輪詢系統的一階和二階特性

2.1 平均排隊隊長

定義在tn時刻第i號站點開始傳輸服務時，第j號站點中平均存儲的數據息量為i（j），則：

根據式（4）～（6）得到i號普通站點的平均排隊隊長的表達式為：

同理可得，中心站點h的平均排隊隊長的表達式為：

ih（h）表示服務器在服務完普通站點i，轉到中心站點h后，這段時間內進入中心站點h的所有數據信息量的平均排隊隊長。

2.2 循環查詢周期

輪詢系統的循環周期為該系統內所有隊列根據服務規則進行一次服務所花費時間的統計平均值，即服務器相鄰兩次開始服務同一隊列的時間差，所以，連續兩級輪詢系統的循環周期為：

2.4 平均等待時間

數據信息量的等待時間是指一個數據信息量從進入一個站點到其被服務器服務的等待時間，系統的平均等待時間是指進入一個站點的所有數據信息量等待的平均時間。本文中E（WGi）和E（WGh）分別代表普通站點與中心站點的平均等待時間，根據參考文獻[15-16]可得其平均等待時間為：

3 仿真實驗及性能分析

3.1 實驗仿真

本文實驗通過Matlab仿真上述建立的連續兩級輪詢系統服務模型。在模型仿真過程中，需要滿足以下條件[14，17]：

1）各站點的參數變量都應當服從相同的分布，普通站點之間的到達率相同但與中心站點的到達率不同;

2）任一時隙內進入各站點的數據信息量都滿足泊松分布;

3）輪詢系統滿足∑Ni=1λi βi+λh βh=∑Ni=1ρi+ρh=Nρ+ρh<1穩態條件。

在仿真實驗中，算法的復雜度為常數，算法時間效率高，所以，為了確保實驗值的準確性，每次仿真實驗的系統循環次數為30萬。

在仿真實驗中，首先驗證了理論值的準確性，分別對8個、10個普通站點的系統模型進行了仿真，仿真結果與理論值的對比結果在表1中;其次通過改變系統中的總負載，觀察分析了平均排隊隊長和平均等待時間的變化規律，如圖2～3所示;最后，通過實驗仿真，分析了中心站點對普通站點的影響，如圖4～5所示。

站點數站點到達率服務率轉換率到達率、服務率、轉換率的單位是否應該是百分數？即在后面加上“/%”？還是“服務率、轉換率”的后面加上/%，因為到達率的單位已經是小數了。注：如服務率寫為服務率/%，其下的數字2，即表示2%。而到達率后面加上/%，其中的數字0.0015，即表示0.0015%。請務必清晰表達。

回復：到達率、服務率、轉換率均表示均值，到達率表示一個時隙內到達每個站點的平均信息分組數，服務率表示服務一個信息分組數的平均時間，轉換率表示服務器從一個站點轉向另一個站點所要的平均時間。所以，在這里率僅表示均值的意思無百分率的含義在里面。

回復：因為問題簡單，我這里可以簡單說明一下。這個問題是關于到達率、服務率和轉換率的單位是否為百分數？其實，在這里這三個參數均表示各自代表的均值，其單位不能是百分數。至于這里的“率”是代表一種均值。比如到達率是指一個時隙內到達每個站點的平均信息分組數，其單位不含有百分數的意思。

3.2 性能分析

1）在表1中，本文通過設定普通站點數8、10，分別對這兩種情況作了仿真實驗，從表中數據可以看出，系統的平均排隊隊長和平均等待時間的實驗值與理論值差距極小，驗證了系統理論分析的正確性。

2）在圖2～3中，本文通過改變系統總負載，得到了普通站點和中心站點的平均排隊隊長和平均等待時間的變化曲線。從圖中曲線可以看出，兩類站點的平均排隊隊長和平均等待時間在總負載低的條件下，變化平緩，隨著總負載的增大，在總負載達到一定值后，總負載的極小變化也能對平均排隊隊長和平均等待時間造成很大的影響。

3）在圖4～5中，本文通過一級門限服務系統和連續兩級系統的對比，觀察了中心站點對普通站點的影響。為了客觀的分析，在該實驗中，設定一級門限服務的站點到達率、服務時間和轉換時間與兩級連續系統的普通站點到達率、服務時間和轉換時間相等，中心站點的到達率為普通站點的十分之一。由圖可以看出，當中心站點的到達率遠小于普通站點時，普通站點的平均排隊隊長和平均等待時間變化不大。

4）從表1、圖2～5可以看出，中心站點的平均排隊隊長與平均等待時間都遠遠小于普通站點，這說明了系統優先級站點與低優先級站點的區分度還是比較高的，達到了高優先級站點快速、高效地接受服務，低優先級站點之間可以公平接受服務的目的。

4 結語

本文采取了一種連續時間完全服務與門限服務的輪詢系統，即在低優先級的普通站點采取門限服務，在高優先級的中心站點采取完全服務。基于嵌入式馬爾可夫鏈與概率母函數得到了系統的精確數學解析，通過實驗仿真驗證了理論分析的正確性。在理論分析正確的基礎上，又通過實驗仿真，分析了總負載對系統的影響以及中心站點對普通站點的影響。通過分析，本文得出在總負載低時，系統的平均排隊隊長和平均等待時間變化緩慢，在總負載到達一定值時，系統的性能將大幅下降，每個站點等候的數據信息量與每個數據信息量等候服務的時間都將大幅增加;而通過一級門限服務系統與該系統比較，可以看出在中心站點的到達率較低時，中心站點對普通站點的影響很小，這說明了該連續時間兩級輪詢控制系統的優越性，在基本不犧牲低優先級普通站點的性能條件下，為高優先級中心站點提供優質的服務。

參考文獻 （References）

[1] WANG X M， DU L J， ZHANG Y， et al. Priority queue based polling mechanism on seismic equipment cluster monitoring[J]. Cluster Computing， 2017， 20（1）： 661-619.

[2] BOON M A A， VANDERMEI R D， WINANDS E M M. Applications of polling systems[J]. Surveys in Operations Research and Management Science， 2011， 16（2）： 67-82.

[3] BOXMA O J， KELLA O， KOSINSKI K M. Queue lengths and workloads in polling systems[J]. Operations Research Letters， 2011， 39（6）： 401-405.

[4] CHU Y Q， LIU Z M. The impact of priority policy in a two-queue Markovian polling system with multi-class priorities[C]// Proceedings of the 12th International Conference on Queueing Theory and Network Applications. Berlin： Springer， 2017： 282-296.

[5] 孫洋洋，楊志軍.無線傳感器網絡輪詢系統分析研究[J].電子測量技術，2018，41（15）：100-104.（SUN Y Y， YANG Z J. Analysis and research of wireless sensor network polling system[J]. Electronic Measurement Technology， 2018， 41（15）： 100-104.）

[6] 蘇楊，楊志軍，丁陽洋，等.無線傳感器網絡中輪詢系統控制的實現[J].電子測量技術，2018，41（4）：66-70.（SU Y， YANG Z J， DING Y Y， et al. Implementation of polling system control in wireless sensor networks[J]. Electronic Measurement Technology， 2018， 41（4）： 66-70.）

[7] 冉文學，余麗艷.普洱茶配送中心訂單分揀完全—并行門限二級輪詢控制機理研究[J].物流工程與管理，2018，40（7）：77-81.（RAN W X， YU L Y. Study on complete-parallel threshold polling control mechanism about order-sorting of Puer tea distribution center[J]. Logistics Engineering and Management， 2018， 40（7）： 77-81.）

[8] 冉文學，劉會娟，余麗艷.連續物料訂單分揀完全并行限定（k=1）輪詢控制機理[J].中國管理科學，2018，26（8）：86-93.（RAN W X， LIU H J， YU L Y. Continuity material order sorting based on the polling control mechanism of exhaustive parallel limited-1[J]. Chinese Journal of Management Science， 2018， 26（8）： 86-93.）

[9] 劉龍軍，丁洪偉，柳虔林，等.基于現場可編程門陣列戰術數據鏈中優先級輪詢接入控制協議的研究[J].兵工學報，2017，38（2）：305-312.（LIU L J， DING H W， LIU Q L， et al. Research on priority polling access control protocol in FPGA-based tactical data link[J]. Acta Armamentarii， 2017， 38（2）： 305-312.）

[10] 孔維東，王永斌，劉宏波.基于排隊論模型的輪詢協議數據鏈系統時延分析[J].火力與指揮控制，2017，42（3）：100-103.（KONG W D， WANG Y B， LIU H B. Research on time delay of polling protocol data link based on queuing theory model[J]. Fire Control and Command Control， 2017， 42（3）： 100-103.）

[11] 楊志軍，蘇楊，丁洪偉.完全服務和非對稱門限服務兩級輪詢系統特性分析[J].自動化學報，2018，44（12）：2228-2237.（YANG Z J， SU Y， DING H W. Analysis of two-level polling system characteristics of exhaustive service and asymmetrically gated service[J]. Acta Automatica Sinica， 2018， 44（12）： 2228-2237.）

[12] 楊志軍，孫洋洋.分忙閑站點的限定（K=2）輪詢控制系統分析研究[J].計算機科學，2018，45（11）：70-74.（YANG Z J， SUN Y Y. Analysis and study on limited （K=2） polling control system with busy and idle sites[J]. Computer Science， 2018， 45（11）： 70-74.）

[13] YANG Z J， SUN Y Y， GAN J H. New polling scheme based on busy/idle queues mechanism[J]. International Journal of Performability Engineering， 2018， 14（10）： 2522-2531.

[14] KIM J， KIM B. Stability of a cyclic polling system with an adaptive mechanism[J]. Journal of Industrial and Management Optimization， 2015， 11（3）： 763-777.

[15] 官錚，楊志軍，何敏，等.依托站點狀態的兩級輪詢控制系統時延特性分析[J].自動化學報，2016，42（8）：1207-1214.（GUAN Z， YANG Z J， HE M， et al. Study on the delay performance of station dependent two-level polling systems[J]. Acta Automatica Sinica， 2016， 42（8）： 1207-1214.）

[16] 木文浩，保利勇，丁洪偉，等.離散時間閘門式多級門限服務的兩級優先級輪詢排隊系統分析[J].電子學報，2018，46（2）：276-280.（MU W H， BAO L Y， DING H W， et al. An exact analysis of discrete time two-level priority polling system based on multi-times gated service policy[J]. Acta Electronica Sinica， 2018， 46（2）： 276-280.）

[17] SIDDIQUI S， GHANI S， KHAN A A. ADP-MAC： an adaptive and dynamic polling-based mac protocol for wireless sensor networks[J]. IEEE Sensors Journal， 2018， 18（2）： 860-874.