多無人機協同決策分布式柵格戰術計算技術研究?

楊利斌 謝瑞煜 杜亞杰

（海軍航空大學 煙臺 264001）

1 引言

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

2 戰術計算任務分解

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

我們首先把協同攻擊過程中指揮UAV 所要完成的戰術計算分解為多個獨立的計算任務，這樣就可以把不同任務分配到不同的計算機上執行，對于指揮UAV 而言，協同對海面目標打擊過程中的戰術計算可以分解為以下的12 個計算子任務，這些計算子任務如下所示。

1）接收并處理目標航跡；

2）估算目標打擊精度需求；

3）生成現有態勢；

4）根據現有態勢推算符合精度需求的協同UAV編號；

5）接收并處理協同UAV的目標跟蹤信息；

6）信息融合算法進行態勢融合，生成融合態勢，更新現有態勢；

7）處理指揮UAV的運動參數；

8）接收并處理協同UAV的運動參數；

9）確定各UAV的陣位及各UAV從現陣位到發射陣位的機動要素；

10）處理指揮UAV的氣象環境參數；

11）接收并處理協同UAV的氣象環境參數；

12）計算各UAV 的導彈發射控制參數，并確定協同攻擊的方案［5］。

3 基于DAG圖的任務調度建模

任務調度的形式化描述用有向無回路圖DAG（Directed Acyclic Graph）所示，其中每一個節點表示一個任務，有向邊表示任務之間的互相優先次序［6～7］。

圖1 任務DAG圖

任務的執行時間μik，表示任務在資源類型為Qk的某一資源上的預計執行時間。記i ?Qk表示任務i 在資源類型為Qk的某一資源上執行。

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

若Pm,Pn∈P ，i ?Pm，j ?Pn，則從任務i 到任務j 的數據傳輸時間為

式中，Dmn=0 表示當任務i 與任務j 在同一地理位置節點執行時，沒有傳輸延遲，dij=0 表示任務i與任務j 在同一地理位置節點的同一資源上執行時，不需要進行數據傳輸。

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

2）同一過程的相鄰兩任務，后繼任務的開始執行時刻不先于前驅任務的開始執行時刻、前驅任務的執行時間和數據傳輸時間三者之和；

3）同一資源上任務的執行時間不能重疊。

則任務調度模型的形式化描述為

當然依據數據傳輸流程，任務之間存在著依賴關系。任務分解后就可以把協同攻擊過程中的戰術計算抽象成一個任務DAG圖。

圖2 多UAV協同打擊的計算任務DAG圖

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

4 算法實現

4.1 編碼方式

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

圖3 染色體的編碼方式

4.2 適配值計算

一個調度方案，即一個染色體，它的最大完成時間Cmax，就是所有任務中最晚完成的任務的完成執行時刻:

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

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

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

4.3 算法流程

Step1:根據假設已經將其分為若干個任務，并且已經得到描述此次戰術計算應用的DAG 圖，算法讀入DAG圖，計算圖中每個任務的深度值；

Step2:隨機產生N 個初始個體（染色體）構成初始種群；

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

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

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

Step7:按變異概率pm對臨時個體執行變異操作產生兩個新個體；

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

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

5 仿真分析

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

圖4 樹型結構任務DAG圖

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

表1 戰術計算任務在不同計算資源上的執行時間

表2 對協同攻擊問題的任務調度算法實驗數據

10 次實驗的平均收斂代數為47.7 代，最快用了27 代就得到了最優解。遺傳算法對于協同攻擊實例平均只用58.8ms 就可以得到最優的調度方案，顯示了良好的性能。

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

如圖5，該任務調度問題最優解的適配值為33.887，對應的最大完成時間為55.5，即該調度問題最小的戰術計算總時間為55.5 個時間單位。最優調度方案有幾種，因為它們具有相同的最優完成時間。其中一種最優調度方案對應染色體，我們把它表示成Gantt 圖的形式，如圖所示。通過Gantt 圖6 可以直觀地顯示協同攻擊過程中，12個戰術計算任務在3臺計算機之間的分配和調度情況。

圖6 多UAV協同打擊最優任務調度Gantt圖

針對協同對海導彈精確目標攻擊作戰樣式，根據協同攻擊的步驟和數據傳輸流程，將該作戰實例進行計算任務分解，并把分解得到的戰術計算任務以及它們之間的依賴關系抽象成任務DAG 圖。然后用遺傳算法將這些戰術計算任務在不同的計算資源上進行合理的分配和調度，以達到分布式戰術計算的目的。從調度的結果來看，遺傳算法能夠對實際的柵格化戰術計算進行任務調度，并顯示出了良好的實時性能。

6 結語

針對多UAV 協同決策分布式柵格戰術計算問題進行研究，以協同對海作戰為背景確定該過程的戰術計算流和戰術計算任務進行分解和抽象，建立基于DAG 圖的任務調度模型。采用遺傳算法對任務進行調度，仿真結果表明該遺傳算法能夠對柵格化多UAV 戰術計算系統進行任務調度，具有良好的精確性和實時性。