楊利斌 謝瑞煜 杜亞杰

（海軍航空大學(xué) 煙臺(tái) 264001）

1 引言

在柵格環(huán)境中，分布式的戰(zhàn)術(shù)計(jì)算為未來(lái)海上信息化作戰(zhàn)提供了技術(shù)保障。特別是協(xié)同作戰(zhàn)已成為海上主要的作戰(zhàn)方式，而柵格化的戰(zhàn)術(shù)計(jì)算環(huán)境正好為更深入全面的協(xié)同作戰(zhàn)提供了實(shí)施的基礎(chǔ)［1］。柵格化環(huán)境下多無(wú)人機(jī)（UAV）分布式戰(zhàn)術(shù)計(jì)算技術(shù)已成為現(xiàn)代高技術(shù)條件下各種作戰(zhàn)樣式中的重要技術(shù)支撐，隨著“網(wǎng)絡(luò)中心戰(zhàn)”作戰(zhàn)理念的提出，它的重要性將越來(lái)越凸顯，成為各戰(zhàn)術(shù)節(jié)點(diǎn)具備網(wǎng)絡(luò)中心戰(zhàn)能力所面臨的巨大技術(shù)挑戰(zhàn)之一［2］。

2 戰(zhàn)術(shù)計(jì)算任務(wù)分解

多UAV 協(xié)同對(duì)海面目標(biāo)打擊整個(gè)過(guò)程涉及到一系列的戰(zhàn)術(shù)計(jì)算，由于對(duì)精度的要求、參與協(xié)同的UAV 數(shù)量增加以及敵目標(biāo)增多和反打擊措施的引入，使該打擊過(guò)程需要的戰(zhàn)術(shù)計(jì)算變得復(fù)雜化，需要處理的信息量呈指數(shù)遞增，實(shí)時(shí)性要求也進(jìn)一步提高［3］。因此，單個(gè)計(jì)算機(jī)可能難以完成計(jì)算任務(wù)，我們采用分布式戰(zhàn)術(shù)計(jì)算方法，其中最需要解決在整個(gè)打擊過(guò)程中，戰(zhàn)術(shù)計(jì)算任務(wù)在多個(gè)計(jì)算機(jī)之間的合理分配和調(diào)度問題［4］。

我們首先把協(xié)同攻擊過(guò)程中指揮UAV 所要完成的戰(zhàn)術(shù)計(jì)算分解為多個(gè)獨(dú)立的計(jì)算任務(wù)，這樣就可以把不同任務(wù)分配到不同的計(jì)算機(jī)上執(zhí)行，對(duì)于指揮UAV 而言，協(xié)同對(duì)海面目標(biāo)打擊過(guò)程中的戰(zhàn)術(shù)計(jì)算可以分解為以下的12 個(gè)計(jì)算子任務(wù)，這些計(jì)算子任務(wù)如下所示。

1）接收并處理目標(biāo)航跡；

2）估算目標(biāo)打擊精度需求；

3）生成現(xiàn)有態(tài)勢(shì)；

4）根據(jù)現(xiàn)有態(tài)勢(shì)推算符合精度需求的協(xié)同UAV編號(hào)；

5）接收并處理協(xié)同UAV的目標(biāo)跟蹤信息；

6）信息融合算法進(jìn)行態(tài)勢(shì)融合，生成融合態(tài)勢(shì)，更新現(xiàn)有態(tài)勢(shì)；

7）處理指揮UAV的運(yùn)動(dòng)參數(shù)；

8）接收并處理協(xié)同UAV的運(yùn)動(dòng)參數(shù)；

9）確定各UAV的陣位及各UAV從現(xiàn)陣位到發(fā)射陣位的機(jī)動(dòng)要素；

10）處理指揮UAV的氣象環(huán)境參數(shù)；

11）接收并處理協(xié)同UAV的氣象環(huán)境參數(shù)；

12）計(jì)算各UAV 的導(dǎo)彈發(fā)射控制參數(shù)，并確定協(xié)同攻擊的方案［5］。

3 基于DAG圖的任務(wù)調(diào)度建模

任務(wù)調(diào)度的形式化描述用有向無(wú)回路圖DAG（Directed Acyclic Graph）所示，其中每一個(gè)節(jié)點(diǎn)表示一個(gè)任務(wù)，有向邊表示任務(wù)之間的互相優(yōu)先次序［6～7］。

圖1 任務(wù)DAG圖

任務(wù)的執(zhí)行時(shí)間μik，表示任務(wù)在資源類型為Qk的某一資源上的預(yù)計(jì)執(zhí)行時(shí)間。記i ?Qk表示任務(wù)i 在資源類型為Qk的某一資源上執(zhí)行。

記Mr為在資源Rr∈R 上執(zhí)行的所有任務(wù)的集合。記Er?Mr×Mr為在資源Rr∈R 上執(zhí)行的所有任務(wù)的約束條件集合。

若Pm,Pn∈P ，i ?Pm，j ?Pn，則從任務(wù)i 到任務(wù)j 的數(shù)據(jù)傳輸時(shí)間為

式中，Dmn=0 表示當(dāng)任務(wù)i 與任務(wù)j 在同一地理位置節(jié)點(diǎn)執(zhí)行時(shí)，沒有傳輸延遲，dij=0 表示任務(wù)i與任務(wù)j 在同一地理位置節(jié)點(diǎn)的同一資源上執(zhí)行時(shí)，不需要進(jìn)行數(shù)據(jù)傳輸。

1）起始任務(wù)的開始執(zhí)行時(shí)刻為0，其他任務(wù)的開始執(zhí)行時(shí)刻大于等于0，且活動(dòng)的執(zhí)行具有原子性；

2）同一過(guò)程的相鄰兩任務(wù)，后繼任務(wù)的開始執(zhí)行時(shí)刻不先于前驅(qū)任務(wù)的開始執(zhí)行時(shí)刻、前驅(qū)任務(wù)的執(zhí)行時(shí)間和數(shù)據(jù)傳輸時(shí)間三者之和；

3）同一資源上任務(wù)的執(zhí)行時(shí)間不能重疊。

則任務(wù)調(diào)度模型的形式化描述為

當(dāng)然依據(jù)數(shù)據(jù)傳輸流程，任務(wù)之間存在著依賴關(guān)系。任務(wù)分解后就可以把協(xié)同攻擊過(guò)程中的戰(zhàn)術(shù)計(jì)算抽象成一個(gè)任務(wù)DAG圖。

圖2 多UAV協(xié)同打擊的計(jì)算任務(wù)DAG圖

一個(gè)任務(wù)的深度值反映了該任務(wù)的優(yōu)先級(jí)，深度值越小，優(yōu)先級(jí)越高?？梢圆捎蒙疃缺闅v的方法獲取DAG 圖節(jié)點(diǎn)的深度信息。獲取每個(gè)任務(wù)的深度信息后，就可以對(duì)染色體解碼所得到的任務(wù)序列按任務(wù)的深度值由小到大進(jìn)行排序，這樣得到的就是在相同資源上執(zhí)行的已排序的任務(wù)序列，優(yōu)先級(jí)越高的任務(wù)執(zhí)行順序越靠前［8～9］。

4 算法實(shí)現(xiàn)

4.1 編碼方式

采用自然數(shù)直接編碼方式來(lái)完成編碼和解碼問題。設(shè)有n 個(gè)任務(wù)和m 個(gè)資源，選取n 個(gè)值在[1 ,m] 之間的整數(shù)來(lái)構(gòu)成染色體[k1k2…kn] ，染色體的長(zhǎng)度n 即為任務(wù)的數(shù)量，染色體中每一位基因kj其下標(biāo)代表了任務(wù)編號(hào)，基因kj的值都是[1 ,m]之間的正整數(shù)，代表該任務(wù)占用的資源編號(hào)?；虻闹悼梢韵嗤硎緮?shù)個(gè)任務(wù)在同一資源上執(zhí)行。編碼方式如圖3所示。

圖3 染色體的編碼方式

4.2 適配值計(jì)算

一個(gè)調(diào)度方案，即一個(gè)染色體，它的最大完成時(shí)間Cmax，就是所有任務(wù)中最晚完成的任務(wù)的完成執(zhí)行時(shí)刻:

重要的是tiS的計(jì)算，在本文中認(rèn)為它由三個(gè)因素決定:所在資源上的空閑時(shí)刻，任務(wù)i 所有前驅(qū)任務(wù)的最晚完成執(zhí)行時(shí)刻，以及最晚完成的前驅(qū)任務(wù)到任務(wù)i 的數(shù)據(jù)傳輸時(shí)間。由此可得任務(wù)i 在資源k 上開始執(zhí)行時(shí)刻的計(jì)算公式為

其中Tidle( k )為資源k 上最近一次空閑時(shí)刻；表示任務(wù)i 前驅(qū)任務(wù)集合中具有最大完成時(shí)刻的前驅(qū)任務(wù)j 的完成執(zhí)行時(shí)刻；dji表示從任務(wù)j 到任務(wù)i 的數(shù)據(jù)傳輸時(shí)間，它由式（1）給出，為了簡(jiǎn)化分析，可將dji理解為從執(zhí)行任務(wù)j 的資源到執(zhí)行任務(wù)i 的資源的通信時(shí)間，它也是一個(gè)已知量［10］。

綜上所述，計(jì)算一個(gè)染色體（個(gè)體）的適配值就可以按如下過(guò)程進(jìn)行，首先對(duì)染色體進(jìn)行解碼，得到每個(gè)資源上執(zhí)行的任務(wù)序列，然后對(duì)每個(gè)任務(wù)序列根據(jù)任務(wù)的深度值進(jìn)行排序，就得到了相應(yīng)的調(diào)度方案，根據(jù)式（1）、式（2）和式（3）可以求得該調(diào)度方案的最大完成時(shí)間Cmax，從而得到個(gè)體的適配值［11］。

4.3 算法流程

Step1:根據(jù)假設(shè)已經(jīng)將其分為若干個(gè)任務(wù)，并且已經(jīng)得到描述此次戰(zhàn)術(shù)計(jì)算應(yīng)用的DAG 圖，算法讀入DAG圖，計(jì)算圖中每個(gè)任務(wù)的深度值；

Step2:隨機(jī)產(chǎn)生N 個(gè)初始個(gè)體（染色體）構(gòu)成初始種群；

Step3:評(píng)價(jià)當(dāng)前種群中每個(gè)個(gè)體的適配值；Step4:判斷算法的終止條件是否滿足，若滿足則輸出結(jié)果；

Step5:不滿足終止條件，采用輪盤賭方式進(jìn)行選擇操作，從當(dāng)前種群中選取兩個(gè)個(gè)體；

Step6:隨機(jī)生成ξ ∈[0 ,1] ，若交叉概率pc＞ξ ，則對(duì)選中個(gè)體執(zhí)行交叉操作來(lái)產(chǎn)生兩個(gè)臨時(shí)個(gè)體；否則將所選中父代個(gè)體作為臨時(shí)個(gè)體；

Step7:按變異概率pm對(duì)臨時(shí)個(gè)體執(zhí)行變異操作產(chǎn)生兩個(gè)新個(gè)體；

Step8:將新個(gè)體的適配值與當(dāng)前種群中適配值最小的個(gè)體比較，若大于則用新個(gè)體替換適配值最小個(gè)體；否則舍棄新個(gè)體；

Step9:若m ＜N ，則返回步驟Step6；否則令k=k+1，并轉(zhuǎn)向Step3［12］。

5 仿真分析

假設(shè)指揮UAV 上用于本次協(xié)同攻擊戰(zhàn)術(shù)計(jì)算的空閑計(jì)算機(jī)有3 臺(tái)，這樣就成為一個(gè)12/3 調(diào)度問題。為了使調(diào)度方案多樣性，我們又假設(shè)這3 臺(tái)計(jì)算機(jī)對(duì)于同一個(gè)任務(wù)具有不同的執(zhí)行時(shí)間，假設(shè)執(zhí)行時(shí)間比為3:4:5。根據(jù)不同任務(wù)的計(jì)算量和計(jì)算復(fù)雜度，設(shè)定12個(gè)任務(wù)在3臺(tái)計(jì)算機(jī)上的執(zhí)行時(shí)間如表1 所示，表中數(shù)據(jù)不代表真實(shí)的計(jì)算時(shí)間，只定性地表征任務(wù)的計(jì)算復(fù)雜度。每個(gè)任務(wù)在不同資源上的執(zhí)行時(shí)間以及資源之間的數(shù)據(jù)傳輸時(shí)間隨機(jī)產(chǎn)生。

圖4 樹型結(jié)構(gòu)任務(wù)DAG圖

我們應(yīng)用遺傳算法來(lái)對(duì)多艦載UAV 協(xié)同對(duì)海攻擊過(guò)程中的計(jì)算任務(wù)進(jìn)行調(diào)度。首先將圖2 所示的戰(zhàn)術(shù)計(jì)算任務(wù)DAG 圖讀入程序中，然后運(yùn)行遺傳算法。由于該實(shí)例的調(diào)度屬于小規(guī)模的調(diào)度問題，算法一般在20 代以內(nèi)即可收斂，所以設(shè)置算法的進(jìn)化代數(shù)為40 代。算法參數(shù)設(shè)置如下:種群數(shù)目為100，交叉概率和變異概率分別為0.8和0.2，適配值函數(shù)中的參數(shù)α=1000、β=0.05。分別進(jìn)行10次實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)如表2所示。

表1 戰(zhàn)術(shù)計(jì)算任務(wù)在不同計(jì)算資源上的執(zhí)行時(shí)間

表2 對(duì)協(xié)同攻擊問題的任務(wù)調(diào)度算法實(shí)驗(yàn)數(shù)據(jù)

10 次實(shí)驗(yàn)的平均收斂代數(shù)為47.7 代，最快用了27 代就得到了最優(yōu)解。遺傳算法對(duì)于協(xié)同攻擊實(shí)例平均只用58.8ms 就可以得到最優(yōu)的調(diào)度方案，顯示了良好的性能。

圖5 適配值隨迭代的變化曲線

如圖5，該任務(wù)調(diào)度問題最優(yōu)解的適配值為33.887，對(duì)應(yīng)的最大完成時(shí)間為55.5，即該調(diào)度問題最小的戰(zhàn)術(shù)計(jì)算總時(shí)間為55.5 個(gè)時(shí)間單位。最優(yōu)調(diào)度方案有幾種，因?yàn)樗鼈兙哂邢嗤淖顑?yōu)完成時(shí)間。其中一種最優(yōu)調(diào)度方案對(duì)應(yīng)染色體，我們把它表示成Gantt 圖的形式，如圖所示。通過(guò)Gantt 圖6 可以直觀地顯示協(xié)同攻擊過(guò)程中，12個(gè)戰(zhàn)術(shù)計(jì)算任務(wù)在3臺(tái)計(jì)算機(jī)之間的分配和調(diào)度情況。

圖6 多UAV協(xié)同打擊最優(yōu)任務(wù)調(diào)度Gantt圖

針對(duì)協(xié)同對(duì)海導(dǎo)彈精確目標(biāo)攻擊作戰(zhàn)樣式，根據(jù)協(xié)同攻擊的步驟和數(shù)據(jù)傳輸流程，將該作戰(zhàn)實(shí)例進(jìn)行計(jì)算任務(wù)分解，并把分解得到的戰(zhàn)術(shù)計(jì)算任務(wù)以及它們之間的依賴關(guān)系抽象成任務(wù)DAG 圖。然后用遺傳算法將這些戰(zhàn)術(shù)計(jì)算任務(wù)在不同的計(jì)算資源上進(jìn)行合理的分配和調(diào)度，以達(dá)到分布式戰(zhàn)術(shù)計(jì)算的目的。從調(diào)度的結(jié)果來(lái)看，遺傳算法能夠?qū)?shí)際的柵格化戰(zhàn)術(shù)計(jì)算進(jìn)行任務(wù)調(diào)度，并顯示出了良好的實(shí)時(shí)性能。

6 結(jié)語(yǔ)

針對(duì)多UAV 協(xié)同決策分布式柵格戰(zhàn)術(shù)計(jì)算問題進(jìn)行研究，以協(xié)同對(duì)海作戰(zhàn)為背景確定該過(guò)程的戰(zhàn)術(shù)計(jì)算流和戰(zhàn)術(shù)計(jì)算任務(wù)進(jìn)行分解和抽象，建立基于DAG 圖的任務(wù)調(diào)度模型。采用遺傳算法對(duì)任務(wù)進(jìn)行調(diào)度，仿真結(jié)果表明該遺傳算法能夠?qū)鸥窕郩AV 戰(zhàn)術(shù)計(jì)算系統(tǒng)進(jìn)行任務(wù)調(diào)度，具有良好的精確性和實(shí)時(shí)性。