基于搶占型離散排隊的軍事信息服務系統(tǒng)性能研究

陳樹肖，郭金淮，王 晨，葛貴斌

（1.中國人民解放軍國防大學聯(lián)合作戰(zhàn)學院，河北 石家莊 050084；2.中國人民解放軍94201部隊，山東 濟南 250002；3.中國人民解放軍93176部隊，遼寧 大連 116023）

0 引言

1985年沈偉光提出信息戰(zhàn)概念[1]，1991年海灣戰(zhàn)爭拉開了信息化戰(zhàn)爭序幕，隨后，“網(wǎng)絡中心戰(zhàn)”“知識中心戰(zhàn)”“分布式殺傷”“馬賽克戰(zhàn)”“決策中心戰(zhàn)”等作戰(zhàn)概念陸續(xù)提出。態(tài)勢感知與信息融合、自主無人系統(tǒng)技術、人工智能等技術在軍事領域的應用日益深入，推動信息化戰(zhàn)爭向更高 階段發(fā)展[2-6]。

當前，信息化戰(zhàn)爭軍事思想與軍事技術進入快速發(fā)展階段。軍事信息服務系統(tǒng)是信息化戰(zhàn)爭的核心支撐要素，軍事信息通常具有類型多樣、重要信息優(yōu)先服務的特點[7]。

軍事信息服務系統(tǒng)數(shù)字化水平日益提升，離散時間排隊模型是研究該系統(tǒng)的重要方法。作為數(shù)學與運籌學的重要分支，離散排隊模型領域有大量研究成果：燕山大學馬占友教授研究團隊[8-10]，從數(shù)學角度出發(fā)，研究了離散排隊模型；從應用角度出發(fā)，針對多優(yōu)先級業(yè)務應用，郭金淮等人[11,12]對多優(yōu)先級離散排隊模型展開了相關研究，等待中斷概率是主要研究內(nèi)容；基于馬爾可夫鏈，汪榮明[13]研究了兩個吸收壁生死鏈的平均吸收時間。本文針對軍事信息服務系統(tǒng)應用，基于軍事信息服務系統(tǒng)特點，結合文獻[11]動態(tài)優(yōu)先級概念，并基于文獻[13]對具體業(yè)務排隊過程的分析，提出了擴展隊列長度、虛擬狀態(tài)空間、構造吸收壁等方法。此外，對各個優(yōu)先級業(yè)務的性能進行了研究，具體性能包括阻塞概率、排隊中斷概率、服務成功概率、排隊時間等，并得到了這些性能的顯式數(shù)學表達式。

1 相關定義

為便于理解，對搶占型離散排隊以及排隊阻塞概率、排隊中斷概率、服務成功概率、排隊時間等定義進行說明。

1.1 搶占型離散排隊

在優(yōu)先權服務中，高優(yōu)先權顧客一旦到達，立即驅逐正在接受服務的低優(yōu)先權顧客的服務，被稱為搶占型優(yōu)先權服務[10]。搶占型離散排隊指高優(yōu)先級業(yè)務到達，立即驅逐正在接受服務的低優(yōu)先級業(yè)務或排在低優(yōu)先級業(yè)務前面，低優(yōu)先級業(yè)務按照優(yōu)先級和到達時間重新排隊。排隊論中搶占型與搶占式含義相同，本文采用搶占型的說法。

1.2 排隊阻塞概率

排隊阻塞概率是指業(yè)務到達隊列后，隊列已滿且隊列中均為更高優(yōu)先級業(yè)務或同優(yōu)先級業(yè)務時，該業(yè)務未能進入隊列的概率。

1.3 排隊中斷概率

排隊中斷事件指更高優(yōu)先級業(yè)務到達時，該業(yè)務被擠出隊列的事件，包括等待中斷事件與服務中斷事件。排隊中斷概率指業(yè)務進入隊列未接受服務或未完成服務離開隊列的概率。

1.4 服務成功概率

服務成功概率是指業(yè)務進入隊列后，未發(fā)生排隊中斷事件時，該業(yè)務成功完成服務離開隊列的概率。

1.5 排隊時間

排隊時間指從業(yè)務進入隊列開始到業(yè)務離開隊列所需的時間。離開隊列可以是完成服務離開，也可以是被高優(yōu)先級業(yè)務擠出隊列。排隊時間也就是指業(yè)務在隊列中的時間，是等待時間或等待時間與服務時間之和。

2 系統(tǒng)模型

搶占型離散排隊模型可描述如下。

2.1 業(yè)務到達

基于多優(yōu)先級業(yè)務特點，業(yè)務優(yōu)先級數(shù)量為r，r≥2。優(yōu)先級i的業(yè)務記為Bi，i=1,2,…,r，i越小優(yōu)先級越高。對于Bi來說，如果某時隙有高優(yōu)先級業(yè)務到達，其到達概率為0；反之，則到達概率為pi，1>pi>0。

2.2 服務機制

采用單服務臺，隊長限制為N，其中N≥1，并采用搶占型離散排隊。有業(yè)務接受服務時，每個時隙服務完成概率為μ，1>μ>0。

2.3 業(yè)務模型

考慮業(yè)務到達、服務完成以及業(yè)務被擠出隊列時間，采用早到模型，即業(yè)務到達發(fā)生在時隙首端(n,n+)處，服務完成發(fā)生在時隙末端(n-,n)處[10]，低優(yōu)先級業(yè)務被擠出隊列時刻為相應高優(yōu)先級業(yè)務到達時刻，即時隙首端(n,n+)。早到模型如圖1所示。

圖1 早到模型

以具體業(yè)務為研究對象，其到達前需要觀察隊列狀態(tài)，因此觀察時刻為時隙開始時，即時刻n。

2.4 參數(shù)關系

結合業(yè)務到達描述，每個時隙有業(yè)務到達的概率為：

排隊系統(tǒng)達到穩(wěn)態(tài)分布，需要滿足業(yè)務到達概率小于服務完成概率的條件，即滿足p<μ。

3 性能研究

根據(jù)系統(tǒng)模型，由于服務時間無記憶性，高優(yōu)先級業(yè)務導致低優(yōu)先級業(yè)務服務中斷不影響服務效率。考慮軍事信息服務系統(tǒng)業(yè)務排隊具體過程，基于動態(tài)優(yōu)先級與業(yè)務穩(wěn)態(tài)隊長分布，提出擴展隊列長度、虛擬狀態(tài)空間、構造吸收壁等方法，區(qū)分最高優(yōu)先級業(yè)務與非最高優(yōu)先級業(yè)務，并對排隊阻塞概率、排隊中斷概率、服務成功概率、排隊時間等性能進行研究。

3.1 最高優(yōu)先級業(yè)務

根據(jù)搶占型離散排隊工作機理，最高優(yōu)先級業(yè)務不受其他業(yè)務影響，可獨立分析。為便于研究其性能，下面對穩(wěn)態(tài)隊長分布進行分析。

時刻n最高優(yōu)先級業(yè)務數(shù)為{Ln,n≥0}，對應狀態(tài)空間是Ω={0,1,…,N}，其轉移概率矩陣為：

基于最高優(yōu)先級業(yè)務的狀態(tài)轉移概率矩陣、穩(wěn)態(tài)隊長分布，對其排隊阻塞概率、排隊中斷概率、服務成功概率與排隊時間進行研究。

（1）排隊阻塞概率

排隊阻塞概率為到達隊列時，隊長為N的概率。結合式（3）、式（4）得到：

（2）排隊中斷概率

最高優(yōu)先級業(yè)務不會被搶占，排隊中斷概率為0，即：

（3）服務成功概率

最高優(yōu)先級業(yè)務不會被搶占，服務成功概率為1，即：

（4）排隊時間

假設業(yè)務進入隊列前隊長為k，排隊時間T1k為服務完k+1個業(yè)務所需時間。其中0≤k≤N-1。

根據(jù)系統(tǒng)模型，1個業(yè)務完成服務平均需要μ-1個時隙。因此T1k=(k+1)μ-1。

排隊時間均值為：

3.2 非最高優(yōu)先級業(yè)務

不失一般性，以Bi中某具體業(yè)務bi為研究對象，i=2,…,r。文獻[11]動態(tài)優(yōu)先級概念是針對多優(yōu)先級搶占型離散排隊提出的，僅考慮對排隊性能有影響的業(yè)務，其本質(zhì)是bi到達隊列之前考慮B1,B2,…,Bi，到達隊列之后考慮B1,B2,…,Bi-1。為方便描述，令BI表 示B1,B2,…,Bi，令BI-1表示B1,B2,…,Bi-1。令HI=(πI0,πI1,…,πIN)為BI的穩(wěn)態(tài)分布，表示BI到達隊列的概率，表示BI-1到達隊列的概率。參考3.1部分，得到：

基于式（9）、式（10），對非最高優(yōu)先級業(yè)務的排隊阻塞概率、排隊中斷概率、服務成功概率與排隊時間進行研究。

（1）排隊阻塞概率

排隊阻塞概率即bi到達隊列時，BI隊長為N的概率。

（2）排隊中斷概率

bi進入隊列前，觀察時刻記（0），BI業(yè)務穩(wěn)態(tài)隊長為k，0≤k≤N-1，k服從式（9）、式（10）概率分布。研究對象是前述k個BI業(yè)務、bi以及bi進入隊列后到達的BI-1業(yè)務構成的隊列，bi排在隊列末尾。

bi進入隊列時，隊長為k+1。第1個時隙沒有更高優(yōu)先級業(yè)務到達，以概率μ完成1個業(yè)務服務。觀察時刻（1），初始隊長為k的概率為μ，初始隊長為k+1的概率為1-μ。

為了研究排隊中斷概率、服務成功概率、排隊時間等性能，下面提出擴展隊列長度、虛擬狀態(tài)空間、構造吸收壁等研究方法。

實際隊列長度最大值為N，為便于研究，提出擴展隊列長度研究方法，即在實際隊列長度最大值的基礎上加1，擴展后隊列長度最大值為N+1。實際狀態(tài)空間為Ω={0,1,…,N}，基于擴展隊列長度，構造虛擬狀態(tài)空間={0,1,…,N,N+1}。進一步地，根據(jù)虛擬狀態(tài)空間構造吸收壁，結合系統(tǒng)模型，進入狀態(tài)0和N+1，則狀態(tài)不再發(fā)生變化，即狀態(tài)0表示服務成功，狀態(tài)N+1表示排隊中斷，狀態(tài)0，N+1稱為吸收壁。

基于虛擬狀態(tài)空間，觀察時刻（1）開始，具有雙吸收壁的轉移概率矩陣：

基于式（12），對文獻[13]研究結果進行擴展，初始隊長為x時，排隊中斷概率為：

式中：0≤x≤N+1，式（13）在空集上求和為零；F0=1；；i≥1。基于式（13），BI業(yè)務穩(wěn)態(tài)隊長為k時，bi排隊中斷概率為：

結合式（9）、式（10），得到bi排隊中斷概率：

（3）服務成功概率

參考上述排隊中斷概率的分析過程，對服務成功概率進行研究。

初始隊長為x時，服務成功概率為：

式中：0≤x≤N+1，式（16）在空集上求和為零；F0=1；Fi=βi；；i≥1。基于式（16），BI業(yè)務穩(wěn)態(tài)隊長為k時bi服務成功率為：

結合式（9）、式（10），得到bi服務成功概率：

（4）排隊時間

根據(jù)上述排隊中斷概率的分析，觀察時刻（1），初始隊長為k的概率為μ，初始隊長為k+1的概率為1-μ。參考文獻[13]研究結果，初始隊長為x時，排隊時間如式（19）所示。

基于式（19），BI業(yè)務穩(wěn)態(tài)隊長為k時bi排隊時間為：

結合式（9）、式（10），得到bi排隊時間：

4 實例分析

影響排隊性能的因素包括隊長限制N、每個時隙服務完成概率μ、業(yè)務到達概率P等。下面通過實例，分析排隊性能與相關因素的變化規(guī)律。

不失一般性，實例中變量為隊長限制、每個時隙服務完成概率，常量為業(yè)務到達概率。業(yè)務優(yōu)先級數(shù)量設為3，結合系統(tǒng)模型，假設優(yōu)先級1，2，3業(yè)務的到達概率P=[p1,p2,p3]=[0.3,0.2,0.3]，以優(yōu)先級3業(yè)務的排隊性能為分析對象。

4.1 排隊阻塞概率

隊長限制N=3∶1∶10，每個時隙服務完成概率μ=0.7∶0.05∶0.8，排隊阻塞概率變化趨勢如圖2所示。

圖2 排隊阻塞概率變化趨勢

如圖2所示，排隊阻塞概率與每個時隙服務完成概率成反比關系，原因是每個時隙服務完成概率越高，業(yè)務到達時隊列滿的概率越低；排隊阻塞概率與隊長限制成反比關系，原因是隊長限制值越大、隊列容量越大，業(yè)務到達時隊列滿的概率越低。

4.2 排隊中斷概率

隊長限制N=5∶1∶7，每個時隙服務完成概率μ=0.62∶0.02∶0.72，排隊中斷概率變化趨勢如圖3所示。

圖3 排隊中斷概率變化趨勢

如圖3所示，排隊中斷概率與每個時隙服務完成概率成反比關系，原因是每個時隙服務完成概率越高，業(yè)務進入隊列完成服務的概率越高、被高優(yōu)先級業(yè)務擠出隊列的概率越低；排隊中斷概率與隊長限制成反比關系，原因是隊長限制值越大，隊列容量越大，被更高優(yōu)先級業(yè)務擠出隊列的概率 越低。

4.3 服務成功概率

隊長限制N=5∶1∶7，每個時隙服務完成概率μ=0.62∶0.02∶0.72，服務成功概率變化趨勢如圖4所示。

圖4 服務成功概率變化趨勢

如圖4所示，服務成功概率與每個時隙服務完成概率成正比關系，原因是每個時隙服務完成概率越高、被更高優(yōu)先級業(yè)務擠出隊列的概率越低，服務成功概率越高；服務成功概率與隊長限制成正比關系，原因是隊長限制值越大，隊列容量越大，被更高優(yōu)先級業(yè)務擠出隊列的概率越低，完成服務離開隊列的概率越高。

4.4 排隊時間

隊長限制N=5∶1∶7，每個時隙服務完成概率μ=0.62∶0.02∶0.72，排隊時間變化趨勢如圖5所示。

圖5 排隊時間變化趨勢

如圖5所示，排隊時間與每個時隙服務完成概率成反比關系，原因是每個時隙服務完成概率越高，業(yè)務以更高概率、更短時間完成服務；排隊時間與隊長限制成正比關系，原因是隊長越長，業(yè)務服務成功或被高優(yōu)先級業(yè)務擠出隊列所需時間越長，即排隊時間越長。

5 結語

本文針對軍事信息服務系統(tǒng)業(yè)務類型多樣、重要業(yè)務優(yōu)先服務的特點，建立了多優(yōu)先級搶占型離散排隊模型。文中分析了系統(tǒng)業(yè)務的具體排隊過程，采用擴展隊列長度、虛擬狀態(tài)空間、構造吸收壁等方法，區(qū)分業(yè)務優(yōu)先級，對排隊阻塞概率、排隊中斷概率、服務成功概率、排隊時間等性能進行研究，并得到其顯式數(shù)學表達式。本文研究結果對軍事信息服務系統(tǒng)的設計、維護、管理與使用具有參考價值，還可應用于其他具有類似特征的信息服務系統(tǒng)。