基于排隊(duì)服務(wù)的相控陣?yán)走_(dá)任務(wù)調(diào)度管理方法

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

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

0 引 言

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

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

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

在服務(wù)系統(tǒng)中要求得到某種服務(wù)的對象稱之為顧客，為顧客提供服務(wù)的機(jī)構(gòu)稱之為服務(wù)臺(tái)。服務(wù)系統(tǒng)基本運(yùn)行過程為：顧客進(jìn)入服務(wù)系統(tǒng)，當(dāng)服務(wù)臺(tái)繁忙時(shí)，按一定規(guī)則進(jìn)行排隊(duì)，服務(wù)臺(tái)按一定規(guī)則對顧客進(jìn)行服務(wù)，服務(wù)完成后顧客離開服務(wù)系統(tǒng)?？梢姡粋€(gè)服務(wù)過程由以下幾個(gè)基本部分組成：輸入過程(顧客)與到達(dá)規(guī)則、排隊(duì)規(guī)則、服務(wù)機(jī)構(gòu)、服務(wù)時(shí)間與服務(wù)規(guī)則。

服務(wù)系統(tǒng)中服務(wù)臺(tái)根據(jù)其數(shù)量可以分為無服務(wù)臺(tái)、單服務(wù)臺(tái)、有限個(gè)服務(wù)臺(tái)以及無限個(gè)服務(wù)臺(tái)。根據(jù)服務(wù)流程關(guān)系，多個(gè)(有限)服務(wù)臺(tái)又可分為串聯(lián)與并聯(lián)形式，主要有單服務(wù)臺(tái)單隊(duì)列結(jié)構(gòu)、多服務(wù)臺(tái)(并聯(lián))單對列結(jié)構(gòu)、多服務(wù)臺(tái)多隊(duì)列結(jié)構(gòu)、多服務(wù)臺(tái)(串聯(lián))單隊(duì)列結(jié)構(gòu)、多服務(wù)臺(tái)混合結(jié)構(gòu)。[12]實(shí)際服務(wù)系統(tǒng)可由以上構(gòu)成各種結(jié)構(gòu)組合組成。圖1是相控陣?yán)走_(dá)任務(wù)調(diào)度服務(wù)系統(tǒng)的服務(wù)流程圖。

針對雷達(dá)任務(wù)調(diào)度管理應(yīng)用場景，基于排隊(duì)服務(wù)理論，給出雷達(dá)任務(wù)調(diào)度服務(wù)系統(tǒng)中一些概念：

(1) 顧客：雷達(dá)任務(wù)；

(2) 服務(wù)臺(tái)：調(diào)度器；

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

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

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

(6) 排隊(duì)長：系統(tǒng)中排隊(duì)等待調(diào)度的雷達(dá)任務(wù)數(shù)量；

(7) 逗留時(shí)間：一個(gè)雷達(dá)任務(wù)在系統(tǒng)中停留時(shí)間；

(8) 等待時(shí)間：一個(gè)雷達(dá)任務(wù)排隊(duì)等待執(zhí)行的時(shí)間；

(9) 服務(wù)強(qiáng)度：任務(wù)到達(dá)速率與服務(wù)速率之比；

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

2 雷達(dá)資源任務(wù)調(diào)度排隊(duì)服務(wù)系統(tǒng)

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

2.1 排隊(duì)服務(wù)系統(tǒng)模型

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

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

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

基于服務(wù)系統(tǒng)狀態(tài)轉(zhuǎn)換圖，建立穩(wěn)態(tài)的狀態(tài)平衡方程，得到調(diào)度服務(wù)系統(tǒng)的運(yùn)行參數(shù)與指標(biāo)，可為雷達(dá)任務(wù)調(diào)度提供參考。根據(jù)穩(wěn)態(tài)平衡方程基本原理，即對于任意狀態(tài)k，產(chǎn)生該狀態(tài)與破壞該狀態(tài)的平均速率相等時(shí)系統(tǒng)可達(dá)到穩(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時(shí)的概率，特別是當(dāng)k=1時(shí)有

P1u1=P0λ0

(2)

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

服務(wù)系統(tǒng)空閑時(shí)概率為

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

Pn=CnP0

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

排隊(duì)任務(wù)數(shù)數(shù)學(xué)期望為

其中

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

3 基于排隊(duì)服務(wù)的任務(wù)管控算法

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

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

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

設(shè)計(jì)算法流程如圖4所示。

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

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

Step3：任務(wù)到達(dá)，判斷系統(tǒng)任務(wù)是否為空，是則轉(zhuǎn)Step 5。

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

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

Step6：服務(wù)效率計(jì)算，如調(diào)度成功率、排隊(duì)等待時(shí)間等參數(shù)。

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

Step8：調(diào)度效能評(píng)估，結(jié)束調(diào)度。

4 仿真分析

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

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

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

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

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

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

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

運(yùn)行指標(biāo)策略1策略2系統(tǒng)空閑概率0.25060.1307平均排隊(duì)任務(wù)數(shù)2.45881.0678平均系統(tǒng)內(nèi)任務(wù)數(shù)3.95772.5895平均排隊(duì)等待時(shí)間(s)0.02730.0117平均系統(tǒng)逗留時(shí)間(s)0.04410.0284

5 結(jié)束語

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

參考文獻(xiàn):

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

[2] 鄭玉軍,田康生,邢曉楠,豐坤. 帶時(shí)間窗的相控陣?yán)走_(dá)實(shí)時(shí)任務(wù)調(diào)度方法[J]. 火力與指揮控制,2016(10):70-74.

[3] 趙培焱,孫濤,陳鯨. 空間探測相控陣?yán)走_(dá)系統(tǒng)的任務(wù)優(yōu)化編排仿真[J]. 計(jì)算機(jī)仿真,2013(7):21-24.

[4] 姚婧,宋銳,王壯,胡衛(wèi)東. 空間探測相控陣?yán)走_(dá)系統(tǒng)的觀測任務(wù)編排仿真[J]. 計(jì)算機(jī)仿真,2006(10):65-68，71.

[5] 田鋼,凌牧,汪晉.基于同時(shí)多波束跟蹤的任務(wù)調(diào)度方法研究[J].現(xiàn)代雷達(dá),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] 寧宣熙.管理運(yùn)籌學(xué)教程[M].北京：清華大學(xué)出版社,2007.

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

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

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

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

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

[13] 艾合買提·卡斯木. 幾個(gè)排隊(duì)模型的動(dòng)態(tài)分析[D].新疆大學(xué),2013.