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

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

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

0 引言

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

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

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

1 相關定義

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

1.1 搶占型離散排隊

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

1.2 排隊阻塞概率

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

1.3 排隊中斷概率

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

1.4 服務成功概率

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

1.5 排隊時間

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

2 系統模型

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

2.1 業務到達

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

2.2 服務機制

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

2.3 業務模型

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

圖1 早到模型

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

2.4 參數關系

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

排隊系統達到穩態分布，需要滿足業務到達概率小于服務完成概率的條件，即滿足p<μ。

3 性能研究

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

3.1 最高優先級業務

根據搶占型離散排隊工作機理，最高優先級業務不受其他業務影響，可獨立分析。為便于研究其性能，下面對穩態隊長分布進行分析。

時刻n最高優先級業務數為{Ln,n≥0}，對應狀態空間是Ω={0,1,…,N}，其轉移概率矩陣為：

基于最高優先級業務的狀態轉移概率矩陣、穩態隊長分布，對其排隊阻塞概率、排隊中斷概率、服務成功概率與排隊時間進行研究。

（1）排隊阻塞概率

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

（2）排隊中斷概率

最高優先級業務不會被搶占，排隊中斷概率為0，即：

（3）服務成功概率

最高優先級業務不會被搶占，服務成功概率為1，即：

（4）排隊時間

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

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

排隊時間均值為：

3.2 非最高優先級業務

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

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

（1）排隊阻塞概率

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

（2）排隊中斷概率

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

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

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

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

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

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

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

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

（3）服務成功概率

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

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

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

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

（4）排隊時間

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

基于式（19），BI業務穩態隊長為k時bi排隊時間為：

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

4 實例分析

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

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

4.1 排隊阻塞概率

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

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

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

4.2 排隊中斷概率

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

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

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

4.3 服務成功概率

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

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

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

4.4 排隊時間

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

圖5 排隊時間變化趨勢

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

5 結語

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