郭金淮，閆曉輝，張祝盛

(中國人民解放軍94201部隊，山東 濟南250002)

排隊系統(tǒng)廣泛應(yīng)用于理論研究與實際系統(tǒng)設(shè)計中，通常應(yīng)用于服務(wù)系統(tǒng)，如通信系統(tǒng)、交通系統(tǒng)、計算機應(yīng)用系統(tǒng)、存儲系統(tǒng)、生產(chǎn)管理系統(tǒng)等領(lǐng)域［1-7］。根據(jù)重要程度的不同可以將排隊系統(tǒng)服務(wù)對象分為多個優(yōu)先級，將服務(wù)對象可分為多個優(yōu)先級的排隊系統(tǒng)稱為多優(yōu)先級排隊系統(tǒng)，多優(yōu)先級排隊系統(tǒng)在排隊系統(tǒng)研究中占有重要地位［2，3，4，7］。對于服務(wù)對象來說，通常關(guān)心其完成服務(wù)所需時間，即系統(tǒng)逗留時間。因此，平均逗留時間成為排隊系統(tǒng)研究的重要性能指標［1，3，6，7］。針對多優(yōu)先級排隊系統(tǒng)，有大量文獻對平均逗留時間或平均等待時間進行了研究?？紤]軍事應(yīng)用，文獻［3］根據(jù)信息重要程度將服務(wù)對象分為兩種優(yōu)先級，對信息平均逗留時間進行了分析，其性能提升以損失低優(yōu)先級服務(wù)對象為代價，在無服務(wù)對象損失前提下性能并沒有改善;文獻［7］針對多媒體業(yè)務(wù)流，考慮兩類優(yōu)先級，基于馬爾科夫到達過程與離散時間模型，對穩(wěn)態(tài)隊長、平均延時性能進行了研究;針對ATM網(wǎng)絡(luò)，考慮實時業(yè)務(wù)與非實時業(yè)務(wù)，文獻［8］提出了基于門限的優(yōu)先級策略，研究表明該策略優(yōu)于靜態(tài)優(yōu)先級策略;基于ATM網(wǎng)絡(luò)不同突發(fā)業(yè)務(wù)及服務(wù)質(zhì)量要求，將業(yè)務(wù)分為兩類，文獻［9］提出了動態(tài)優(yōu)先級排隊策略并進行了性能分析。

上述研究具有較強針對性，根據(jù)具體應(yīng)用場景，給出了相應(yīng)策略。區(qū)別于上述策略研究，本文考慮排隊系統(tǒng)存在多個優(yōu)先級服務(wù)對象的情況，證明了搶占式排隊系統(tǒng)為無性能損失排隊系統(tǒng)，采用資源分層方法，對不同優(yōu)先級服務(wù)對象的平均逗留時間作了針對性研究。文中方法具有適應(yīng)性，可用于任意數(shù)目優(yōu)先級的排隊系統(tǒng)。

1 系統(tǒng)模型

文中采用系統(tǒng)模型如下。

(1)排隊模型?？紤]多服務(wù)臺排隊系統(tǒng)，就性能來說，相同服務(wù)臺數(shù)目情況下，單隊列多服務(wù)臺模型優(yōu)于多隊列多服務(wù)臺模型［10］，本文采用單隊列多服務(wù)臺模型，服務(wù)臺數(shù)量為m，不考慮隊長限制，即M/M/m/∞排隊模型。服務(wù)臺數(shù)目為一時，可退化為單服務(wù)臺排隊系統(tǒng)。

(2)輸入過程。根據(jù)重要程度，將服務(wù)對象分為r個優(yōu)先級，優(yōu)先級i的服務(wù)對象服從到達率為λi的泊松分布，t時間內(nèi)到達k個優(yōu)先級i服務(wù)對象的概率為Pki(t)=，其中i=1，2，…，r，i越大優(yōu)先級越高。

(3)排隊規(guī)則。采用搶占式排隊規(guī)則，即高優(yōu)先級服務(wù)對象到達隊列時排在低優(yōu)先級服務(wù)對象之前，若服務(wù)臺全忙且有低優(yōu)先級服務(wù)對象正在接受服務(wù)，則停止低優(yōu)先級服務(wù)對象服務(wù)以搶占服務(wù)資源。

(4)服務(wù)過程。所有服務(wù)對象服務(wù)時間均服從參數(shù)μ的負指數(shù)分布。隊長可無限長，滿足∑ri=1λi＜mμ，排隊系統(tǒng)可達穩(wěn)態(tài)。

(5)研究指標。對不同優(yōu)先級服務(wù)對象的平均逗留時間進行研究。

2 性能研究

主要包括資源分層概念、時間累加等效性定理、平均逗留時間研究三部分。

2.1 資源分層概念

文中資源指服務(wù)資源，根據(jù)搶占式排隊系統(tǒng)的特點，結(jié)合系統(tǒng)模型提出資源分層的概念。具體如下。

(1)優(yōu)先級越高、擁有資源權(quán)限越大。

(2)最高優(yōu)先級服務(wù)對象擁有系統(tǒng)全部資源。

(3)對于優(yōu)先級i服務(wù)對象來說，其擁有資源為比其優(yōu)先級高服務(wù)對象的剩余資源，即優(yōu)先級為i+1，…，r-1，r服務(wù)對象的剩余資源。

2.2 時間累加等效性定理

定理:服務(wù)臺服務(wù)能力服從負指數(shù)分布，單位時間平均服務(wù)率s。時間段TT對應(yīng)時間區(qū)間［ta，tb］，時間段Ti應(yīng)時間區(qū)間［tai，tbi］，其中i=1，…，L，ta1≤tb1≤…tai≤tbi≤…taL≤tbL，考慮時間長度，滿足TT=。則時間段TT完成服務(wù)的平均數(shù)等于所有時間段Ti完成服務(wù)的平均數(shù)的和。

證明:根據(jù)指數(shù)分布性質(zhì)，服務(wù)臺完成服務(wù)的次數(shù)服從參數(shù)為s的泊松公布。令L=2，則滿足TT=，則TT完成k次服務(wù)的概率:

令時間段T1，T2完成服務(wù)次數(shù)分別為n1，n2，則時間段T1，T2共完成k次服務(wù)的概率:

根據(jù)二項式定理，可得到式(1)等于式(2)。

基于數(shù)學歸納法，上述結(jié)論適用于L為任意正整數(shù)的情況，定理得證。也就是說，只要累加時間和相同，則完成服務(wù)的平均數(shù)相同，與時間段數(shù)目無關(guān)。該定理成立的原因是指數(shù)分布的無記憶性。

基于時間累加等效性定理可知，搶占式排隊系統(tǒng)服務(wù)能力與非搶占式排隊系統(tǒng)服務(wù)能力相同，為無性能損失排隊系統(tǒng)。

2.3 平均逗留時間

基于上述資源分層概念與時間累加等效性定理，下面對不同優(yōu)先級服務(wù)對象平均逗留時間進行研究。

2.3.1 最高優(yōu)先級服務(wù)對象

最高優(yōu)先級服務(wù)對象擁有系統(tǒng)全部資源，可按無優(yōu)先級單隊列多服務(wù)臺模型研究。設(shè)pm為隊列有n個最高優(yōu)先級服務(wù)對象的概率，得到:

2.3.2 一般優(yōu)先級服務(wù)對象

不失一般性，考慮優(yōu)先級i服務(wù)對象，其平均逗留時間分析如下。

(1)將優(yōu)先級i到r的服務(wù)對象看作一類，記Si→r，其到達率λi→r=。根據(jù)式(5)，其平均逗留時間wi→r為:

(2)將優(yōu)先級i+1到r的服務(wù)對象看作一類，記Si+1→r，其到達率λi+1→r=。同理，其平均逗留時間wi+1→r:

顯然，把所有服務(wù)對象看作一類時，直接計算所得平均逗留時間與式(9)相同。

3 實例分析

信息服務(wù)系統(tǒng)是軍隊信息化建設(shè)的重要組成部分，需要處理各種不同信息。根據(jù)重要程度，將信息分為三個優(yōu)先級:①后勤保障信息，包括物資和給養(yǎng)的保障情況;②武器裝備狀態(tài)信息，指武器作戰(zhàn)平臺的方位、運動速度、運動方向及燃料儲備等;③戰(zhàn)場態(tài)勢信息，敵我友三方的兵力部署、火力配置等。

戰(zhàn)場態(tài)勢信息優(yōu)先級最高，武器裝備狀態(tài)信息次之，后勤保障信息優(yōu)先級最低。結(jié)合系統(tǒng)模型，優(yōu)先級高的信息優(yōu)先接受服務(wù)，將該信息服務(wù)系統(tǒng)等價為搶占式排隊系統(tǒng)。其中，平均逗留時間是重要系統(tǒng)設(shè)計指標，基于文中方法，對不同優(yōu)先級信息的平均逗留時間進行分析。假設(shè)優(yōu)先級1、2、3信息的到達率分別2、3、5，單服務(wù)臺服務(wù)率3，服務(wù)臺數(shù)目分別為5、6、7、8時，不同優(yōu)先級服務(wù)對象及所有優(yōu)先級服務(wù)對象平均逗留時間如圖1所示。由圖可以看出，服務(wù)臺數(shù)量同樣存在瓶頸效應(yīng)，即當服務(wù)臺達到一定數(shù)量后，數(shù)量的進一步增加不會明顯減少平均逗留時間。

圖1 平均逗留時間示意圖

根據(jù)分析數(shù)據(jù)，可以在滿足不同優(yōu)先級信息服務(wù)要求的前提下，對信息服務(wù)系統(tǒng)進行優(yōu)化，比如系統(tǒng)需要的服務(wù)臺數(shù)量等等。

4 結(jié)論

考慮存在多優(yōu)先級服務(wù)對象的搶占式排隊系統(tǒng)，提出了資源分層概念，并基于時間累加等效性定理，對排隊系統(tǒng)不同優(yōu)先級服務(wù)對象的平均逗留時間進行了分析?；谖闹蟹椒ǎ蛇M一步對不同優(yōu)先級服務(wù)對象的其他性能作針對性分析，對多優(yōu)先級排隊系統(tǒng)的設(shè)計具有重要指導意義。

1 盛友招.排隊論及其在計算機通信中的應(yīng)用［M］.北京:北京郵電大學出版社，2000.

2 胡根生，朱翼雋.帶有兩個優(yōu)先權(quán)M/M/s排隊的通信網(wǎng)交換性能分析［J］.江蘇大學學報(自然科學版)，2002，23(4):91-94.

3 趙軼飛，齊和平，劉伶平，等.排隊論在軍事信息服務(wù)中的應(yīng)用［J］.火力與指揮控制，2011，36(7):111-113，118.

4 王知人，侯培國，關(guān)新平.具有優(yōu)先級排隊系統(tǒng)輸入隊列調(diào)度算法性能比較［J］.黑龍江自動化技術(shù)與應(yīng)用，1999，18(2):10-14.

5 吳錦標，劉再明，尹小玲，等.基于排隊論的一個物流模型［J］.系統(tǒng)工程理論與實踐，2009，29(9):78-83.

6 甘應(yīng)愛.運籌學(第三版)［M］.北京:清華大學出版社，2005.

7 孟坤.基于排隊論的通信網(wǎng)絡(luò)QoS研究［D］.鎮(zhèn)江:江蘇大學，2008.

8 LEE D，SENGUPTA B.Queueing Analysis of a Threshold based Priority Scheme for ATM Networks［J］.IEEE/ACM Trans.Netw.，1993，1(6):709-717.

9 CHOI D I，LEE Y.Performance Analysis of a Dynamic Ppriority Queue for Traffic Control of Bursty Traffic in ATM Networks［J］.IEE Proc.-Commun.，2001，148(3):181-187.

10 岳立業(yè).排隊方式在優(yōu)化排隊系統(tǒng)中的應(yīng)用［J］.科技信息，2007(36):154-155.