鮑鵬飛，黃孝鵬，崔威威，丁世譜

(中國船舶重工集團公司第七二四研究所，南京 211153)

0 引 言

相控陣雷達具有波束快速捷變、資源可控性強等技術特點[1]，可實現(xiàn)同時多功能，具有靈活性高、自適性強的探測優(yōu)勢，同時也對相控陣雷達任務調度管理技術[2]的需求更加凸顯。相控陣雷達任務調度需要考慮調度策略選擇、任務優(yōu)先級確定和調度算法設計[3-5]，并直接影響雷達最大效能的發(fā)揮。傳統(tǒng)任務調度方法根據(jù)系統(tǒng)下發(fā)任務在一個調度間隔內安排調度序列[6]，缺乏考慮任務總體性，難以總體上使任務到達與調度相適應。本文引入排隊服務系統(tǒng)概念[7-8]，提出一種相控陣雷達任務動態(tài)排隊管控方法，在系統(tǒng)層面考慮相控陣雷達資源服務系統(tǒng)的參數(shù)優(yōu)化設計、任務到達分布、服務時間分布、任務狀態(tài)轉換以及任務-資源動態(tài)自適應性，并增強任務排隊合理性，保證任務有序執(zhí)行，提高調度服務水平。

排隊論起源于Erlang A K對電話服務系統(tǒng)的研究，是研究系統(tǒng)排隊與服務規(guī)律的一門學科。它越來越多地滲透到軍事、經濟、生產與服務等多種部門。[9]隨著排隊特征、排隊規(guī)則、服務機構變得越來越復雜，相關研究越來越多。[10-11]利用排隊理論構建各種應用服務系統(tǒng)模型，解決復雜現(xiàn)實問題，并分析服務系統(tǒng)最佳運行的各項指標，對于提出服務改進措施、優(yōu)化服務系統(tǒng)結構、降低系統(tǒng)的研制成本和提高系統(tǒng)服務效率有重要意義。基于排隊服務法的任務調度管理方法將雷達任務到達和執(zhí)行的過程看作是“排隊服務”過程，通過“服務臺”實現(xiàn)相控陣雷達的任務調度管理。

1 服務系統(tǒng)基本概念

在服務系統(tǒng)中要求得到某種服務的對象稱之為顧客，為顧客提供服務的機構稱之為服務臺。服務系統(tǒng)基本運行過程為：顧客進入服務系統(tǒng)，當服務臺繁忙時，按一定規(guī)則進行排隊，服務臺按一定規(guī)則對顧客進行服務，服務完成后顧客離開服務系統(tǒng)?？梢?，一個服務過程由以下幾個基本部分組成：輸入過程(顧客)與到達規(guī)則、排隊規(guī)則、服務機構、服務時間與服務規(guī)則。

服務系統(tǒng)中服務臺根據(jù)其數(shù)量可以分為無服務臺、單服務臺、有限個服務臺以及無限個服務臺。根據(jù)服務流程關系，多個(有限)服務臺又可分為串聯(lián)與并聯(lián)形式，主要有單服務臺單隊列結構、多服務臺(并聯(lián))單對列結構、多服務臺多隊列結構、多服務臺(串聯(lián))單隊列結構、多服務臺混合結構。[12]實際服務系統(tǒng)可由以上構成各種結構組合組成。圖1是相控陣雷達任務調度服務系統(tǒng)的服務流程圖。

針對雷達任務調度管理應用場景，基于排隊服務理論，給出雷達任務調度服務系統(tǒng)中一些概念：

(1) 顧客：雷達任務；

(2) 服務臺：調度器；

(3) 排隊規(guī)則：從高優(yōu)先級到低優(yōu)先級排隊；

(4) 服務規(guī)則：有優(yōu)先權的服務(Priority，PR)；

(5) 隊長：服務系統(tǒng)中雷達任務數(shù)量；

(6) 排隊長：系統(tǒng)中排隊等待調度的雷達任務數(shù)量；

(7) 逗留時間：一個雷達任務在系統(tǒng)中停留時間；

(8) 等待時間：一個雷達任務排隊等待執(zhí)行的時間；

(9) 服務強度：任務到達速率與服務速率之比；

(10) 排隊閾值：設定調度服務系統(tǒng)可容納排隊的最大任務數(shù)。

2 雷達資源任務調度排隊服務系統(tǒng)

將排隊論引入雷達資源調度，構建雷達任務排隊服務系統(tǒng)模型，分析該系統(tǒng)模型，優(yōu)化系統(tǒng)的服務指標參數(shù)，實現(xiàn)資源的有效調度與管控。

2.1 排隊服務系統(tǒng)模型

顧客平均到達速率λ與規(guī)律、顧客平均服務速率u與規(guī)律和服務通道數(shù)目對服務系統(tǒng)的運行有重要影響。1953年，肯達(Kendal)用符號的方式描述服務系統(tǒng)，用[A/B/C]表示一個服務系統(tǒng)的基本模型，其中A、B、C分別表示服務系統(tǒng)的顧客到達規(guī)律、服務時間的分布規(guī)律和服務通道數(shù)目。由于該服務參數(shù)基本模型缺少考慮顧客及其系統(tǒng)其他特性對服務運行的重大影響，1966年里氏(Lee)在肯達的基礎上完善了服務系統(tǒng)符號化描述，即[A/B/C]：[d/e/f]；d、e、f分別表示服務系統(tǒng)的最大容量、顧客總體數(shù)量和服務規(guī)則，可以用這樣6個符號描述服務系統(tǒng)模型特征。

針對特定空域特定目標的任務，通過大量任務分析，得到雷達任務分布模型。設雷達任務近似泊松流，雷達任務平均到達速率λ、任務平均服務速率u。排隊服務系統(tǒng)限制任務數(shù)為N，新任務到達且系統(tǒng)任務滿時則按一定(優(yōu)先級)規(guī)則刪除任務。對于單雷達系統(tǒng)而言，該任務調度模型近似[M/M/1]∶[N/∞/PR]系統(tǒng)模型。多雷達有控制調度中心時，任務調度模型近似[M/M/C]∶[N/∞/PR]系統(tǒng)模型。構建服務模型后，可獲得服務系統(tǒng)排隊任務數(shù)期望值Lq、任務在系統(tǒng)平均停留時間Ws、排隊等待時間Wq等關鍵指標參數(shù)。

在處理系統(tǒng)狀態(tài)不斷變化的雷達調度過程時，可以用狀態(tài)轉移圖來描述這一過程。調度服務系統(tǒng)的狀態(tài)可以用系統(tǒng)中的任務數(shù)n(n=1,2,3,…)表示，可見系統(tǒng)的狀態(tài)是一間斷、變化的。雷達任務請求的到達或離去都會引起系統(tǒng)狀態(tài)發(fā)生變化。[13]任務調度服務系統(tǒng)的生滅過程狀態(tài)轉移圖如圖2、圖3所示，圈中的數(shù)字表示系統(tǒng)的狀態(tài)，一條箭線表示從狀態(tài)i到狀態(tài)j的狀態(tài)轉移關系，箭頭方向表示狀態(tài)轉移方向，箭線旁邊的符號λ、μ分別表示從一個狀態(tài)轉換到另一狀態(tài)的任務到達速率和離開速率。

基于服務系統(tǒng)狀態(tài)轉換圖，建立穩(wěn)態(tài)的狀態(tài)平衡方程，得到調度服務系統(tǒng)的運行參數(shù)與指標，可為雷達任務調度提供參考。根據(jù)穩(wěn)態(tài)平衡方程基本原理，即對于任意狀態(tài)k，產生該狀態(tài)與破壞該狀態(tài)的平均速率相等時系統(tǒng)可達到穩(wěn)態(tài)平衡，可建立穩(wěn)態(tài)平衡方程：

Pk+1uk+1+Pk-1λk-1=Pkλk+Pkuk

(1)

式中Pk表示系統(tǒng)狀態(tài)為k時的概率，特別是當k=1時有

P1u1=P0λ0

(2)

由此可以得到一組穩(wěn)態(tài)平衡方程。聯(lián)立方程組可以求出一般服務系統(tǒng)的運行指標：

服務系統(tǒng)空閑時概率為

顧客數(shù)為n的概率為

Pn=CnP0

服務系統(tǒng)的任務數(shù)量期望值為

排隊任務數(shù)數(shù)學期望為

其中

具體到調度服務系統(tǒng)可以在上面的平衡方程加入適當?shù)臈l件。

3 基于排隊服務的任務管控算法

目前，雷達資源調度有從任務優(yōu)先級方面考慮，如通過網(wǎng)絡加權的方法、優(yōu)先級表算法、BP神經網(wǎng)絡得到任務的優(yōu)先級，也有從參數(shù)設置方面考慮，如設置合理跟蹤數(shù)據(jù)率、波位編排方式、駐留時間等提高任務執(zhí)行效率。在資源調度服務系統(tǒng)的參數(shù)優(yōu)化設計、服務時間分布、動態(tài)自適應等層面的研究相對欠缺。

“排隊等待”是服務系統(tǒng)廣泛存在的現(xiàn)象。就雷達任務調度系統(tǒng)而言，排隊論主要解決任務擁擠問題，通過優(yōu)化服務系統(tǒng)參數(shù)、有效安排任務和動態(tài)匹配任務-資源，提高任務管控水平和資源利用率。排隊服務法利用雷達先驗知識分析計算服務系統(tǒng)參數(shù)，并通過反饋控制使任務期望數(shù)(隊長)控制在一定范圍，從而提高相控陣雷達資源調度服務水平。

排隊服務資源管控算法：通過分析相控陣雷達任務先驗知識，獲取資源調度服務系統(tǒng)的參數(shù)，如平均等待隊長、平均任務等待時間等，再組合應用專家群評分、判斷矩陣、加權計算等方法得到任務優(yōu)先級，生成任務執(zhí)行序列。通過監(jiān)控任務排隊隊長是否超過排隊閾值，合理分配任務-資源，并可調整調度間隔，優(yōu)化系統(tǒng)服務速率，使得任務到達與任務執(zhí)行的動態(tài)平衡，實現(xiàn)最佳服務水平。

設計算法流程如圖4所示。

Step1：分析大量相控陣雷達任務的先驗知識，得到相控陣雷達任務分布模型。設雷達任務流近似泊松流，計算雷達任務平均到達速率λ、任務平均服務速率u，獲取此服務系統(tǒng)排隊任務數(shù)期望值Lq、任務在系統(tǒng)平均停留時間Ws、排隊等待時間Wq等參數(shù)。

Step2：初始化系統(tǒng)參數(shù)。

Step3：任務到達，判斷系統(tǒng)任務是否為空，是則轉Step 5。

Step4：根據(jù)排隊系統(tǒng)參數(shù)設置排隊閾值，調整相關服務參數(shù)。判斷服務系統(tǒng)任務是否已滿，若已滿則先綜合優(yōu)先級排序，從隊列中剔除排序最后的任務，保證重要任務優(yōu)先執(zhí)行，并根據(jù)任務調度規(guī)則決定該剔除任務是進入刪除鏈表還是等待下個調度周期執(zhí)行；若未滿則先優(yōu)先級排序，并根據(jù)時間窗準則判斷任務是否執(zhí)行。

Step5：執(zhí)行任務并統(tǒng)計計數(shù)。

Step6：服務效率計算，如調度成功率、排隊等待時間等參數(shù)。

Step7：判斷任務是否執(zhí)行完畢，若沒有則轉Step 3。

Step8：調度效能評估，結束調度。

4 仿真分析

仿真條件：單雷達系統(tǒng)仿真時間為1 s，任務平均到達率50個/s，任務服務率60個/s，計算任務平均排隊長度4.17。排隊閾值分別為N1=4、N2=8，任務時間窗100 ms。任務服務時間為負指數(shù)分布，設置搜索、跟蹤、協(xié)同、確認等任務若干。任務按綜合和優(yōu)先級預先排序完成，進行排隊調度仿真。

如圖5結果表明，當排隊閾值為4時部分任務丟失，調度成功率91.7%(圖5中實線部分為丟失的任務)，平均等待時間0.0209 s，排隊閾值為8時調度成功率100%，平均等待時間0.0314 s，表明增加系統(tǒng)排隊閾值，可提高任務調度成功率，但等待時間有所增加。

仿真圖6更直觀表明，排隊閾值越大任務調度成功數(shù)越多，但同時任務排隊等待時間越長。任務調度時需要平衡考慮調度成功率與排隊等待時間，從而調整服務系統(tǒng)排隊閾值、服務速率等參數(shù)。

若探測區(qū)域S(如圖7)的目標到達率由50個/s增加至100個/s，服務率60個/s、排隊閾值N=4保持不變時，為保證目標有效探測，需增加探測資源，可利用兩部雷達探測，并采用兩種調度策略。調度策略分析如下：

策略1：分區(qū)掃描，兩部雷達掃描區(qū)域分別為S1、S2；

策略2：兩部雷達聯(lián)合掃描區(qū)域S，由中心節(jié)點控制任務分發(fā)。

兩種策略下系統(tǒng)的服務參數(shù)如表1，可以看出策略2調度效果更好。

運行指標策略1策略2系統(tǒng)空閑概率0.25060.1307平均排隊任務數(shù)2.45881.0678平均系統(tǒng)內任務數(shù)3.95772.5895平均排隊等待時間(s)0.02730.0117平均系統(tǒng)逗留時間(s)0.04410.0284

5 結束語

本文主要研究基于排隊服務的相控陣雷達任務調度管理以及資源動態(tài)管控方法。該方法將雷達任務到達與執(zhí)行看作是“排隊服務”過程，通過對相控陣雷達大量任務的先驗知識分析，獲取任務排隊平均長度、平均等待時間等服務系統(tǒng)參數(shù)；基于任務截止期、工作方式優(yōu)先級、駐留時間、期望執(zhí)行時間等特征參數(shù)，計算任務的綜合優(yōu)先級并生成任務隊列；動態(tài)匹配雷達系統(tǒng)資源，實現(xiàn)任務與資源的動態(tài)平衡。仿真分析表明任務排隊長度和調度成功率受排隊閾值的影響較大，需要平衡考慮排隊長度和調度成功率參數(shù)，設定合理的排隊閾值；同時，設計有效的調度策略，調整排隊服務模型，可有效提升調度性能。

參考文獻:

[1] 邵春生. 相控陣雷達研究現(xiàn)狀與發(fā)展趨勢[J]. 現(xiàn)代雷達,2016, 38 (6):1-4.

[2] 鄭玉軍,田康生,邢曉楠,豐坤. 帶時間窗的相控陣雷達實時任務調度方法[J]. 火力與指揮控制,2016(10):70-74.

[3] 趙培焱,孫濤,陳鯨. 空間探測相控陣雷達系統(tǒng)的任務優(yōu)化編排仿真[J]. 計算機仿真,2013(7):21-24.

[4] 姚婧,宋銳,王壯,胡衛(wèi)東. 空間探測相控陣雷達系統(tǒng)的觀測任務編排仿真[J]. 計算機仿真,2006(10):65-68，71.

[5] 田鋼,凌牧,汪晉.基于同時多波束跟蹤的任務調度方法研究[J].現(xiàn)代雷達,2016, 38(4):46-49.

[6] Hasan SMir, Adel Guitouni. Variable Dwell Time Task Scheduling for Multifunction Radar[J]. IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2014, 11(2):463-472.

[7] 寧宣熙.管理運籌學教程[M].北京：清華大學出版社,2007.

[8] 宗群,牙淑紅,王振世.基于排隊論的上高峰電梯群控調度的研究[J].系統(tǒng)工程與電子技術,2003, 25(6):722-725.

[9] 鄭孟雪. 多服務窗串聯(lián)排隊模型研究[D].重慶師范大學,2015.

[10] 汪浩,黃明和,龍浩. 基于G/G/1-FCFS、M/G/1-PS和M/G/∞排隊網(wǎng)絡的Web服務組合性能分析[J]. 計算機學報,2013(1):22-38.

[11] 劉名武,楊迎春,馬永開. 一類排隊服務系統(tǒng)的最優(yōu)控制策略研究[J]. 控制理論與應用,2012(3):323-330.

[12] 張龍. 基于隨機服務理論的施工機群配置對溫度離析的影響研究[D].長安大學,2013.

[13] 艾合買提·卡斯木. 幾個排隊模型的動態(tài)分析[D].新疆大學,2013.