多無人機(jī)協(xié)同決策分布式柵格戰(zhàn)術(shù)計(jì)算技術(shù)研究?

楊利斌 謝瑞煜 杜亞杰

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 任務(wù)DAG圖

任務(wù)的執(zhí)行時間μik，表示任務(wù)在資源類型為Qk的某一資源上的預(yù)計(jì)執(zhí)行時間。記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ù)傳輸時間為

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

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

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

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

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

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

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

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

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

4.1 編碼方式

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

圖3 染色體的編碼方式

4.2 適配值計(jì)算

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

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

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

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

4.3 算法流程

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

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

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

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

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

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

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

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

5 仿真分析

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

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

我們應(yīng)用遺傳算法來對多艦載UAV 協(xié)同對海攻擊過程中的計(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í)行時間

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

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

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

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

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

針對協(xié)同對海導(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é)果來看，遺傳算法能夠?qū)?shí)際的柵格化戰(zhàn)術(shù)計(jì)算進(jìn)行任務(wù)調(diào)度，并顯示出了良好的實(shí)時性能。

6 結(jié)語

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