基于排隊服務的相控陣雷達任務調度管理方法

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

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

0 引 言

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

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

1 服務系統基本概念

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

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

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

(1) 顧客：雷達任務；

(2) 服務臺：調度器；

(3) 排隊規則：從高優先級到低優先級排隊；

(4) 服務規則：有優先權的服務(Priority，PR)；

(5) 隊長：服務系統中雷達任務數量；

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

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

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

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

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

2 雷達資源任務調度排隊服務系統

將排隊論引入雷達資源調度，構建雷達任務排隊服務系統模型，分析該系統模型，優化系統的服務指標參數，實現資源的有效調度與管控。

2.1 排隊服務系統模型

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

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

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

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

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

(1)

式中Pk表示系統狀態為k時的概率，特別是當k=1時有

P1u1=P0λ0

(2)

由此可以得到一組穩態平衡方程。聯立方程組可以求出一般服務系統的運行指標：

服務系統空閑時概率為

顧客數為n的概率為

Pn=CnP0

服務系統的任務數量期望值為

排隊任務數數學期望為

其中

具體到調度服務系統可以在上面的平衡方程加入適當的條件。

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

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

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

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

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

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

Step2：初始化系統參數。

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

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

Step5：執行任務并統計計數。

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

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

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

4 仿真分析

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

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

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

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

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

策略2：兩部雷達聯合掃描區域S，由中心節點控制任務分發。

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

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

5 結束語

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

參考文獻:

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

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

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

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

[5] 田鋼,凌牧,汪晉.基于同時多波束跟蹤的任務調度方法研究[J].現代雷達,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].系統工程與電子技術,2003, 25(6):722-725.

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

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

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

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

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