面向無人機蜂群的航電云多層任務調度模型

王榮巍，何鋒，周璇，魯俊，李二帥

北京航空航天大學 電子信息工程學院，北京 100083

航空電子云系統架構，簡稱航電云[1-3]，來源于互聯網云計算思想，通過虛擬化航電系統資源(例如通信設備，各種傳感器)為資源池，以進行資源的統一管理和按需服務。航電云不僅對單平臺資源進行虛擬，而且可將資源共享范圍從單平臺擴充到多系統平臺，使跨系統資源綜合實現成為可能[4-5]。

無人機蜂群作戰是一種抗干擾性強、成本低、作戰靈活的作戰體系。無人機蜂群作戰能力取決于總體架構、集群感知與信息融合、集群控制與群體智能、任務規劃和航跡規劃等關鍵技術的研究[6]。面向無人機蜂群作戰的航電云，是航空電子云中由無人機蜂群組成的特殊云，為解決大規模無人機蜂群作戰而提出。

國內航電云研究[1-3]分別從云服務架構、模型描述、網絡架構和跨平臺資源虛擬化等不同角度逐漸完善航空電子云概念。在具體應用方面，文獻[7-9]將云概念、軟件定義網絡技術引入到航空集群和現代交通控制，分別提出軟件定義航空集群機載戰術網絡技術、集中控制式網絡部署方法和智能交通信息物理融合云控制系統，以提高復雜和高動態網絡環境下航空集群作戰能力和智能交通控制系統運行性能。

在無人機蜂群作戰中，任務調度由任務分解和任務分配組成。針對一般航空作戰任務分解問題，王國慶等[10]引入Zachman復雜系統組織設計方法從任務需求、任務模式、任務能力、任務響應、任務組織和任務管理6個角度對使命任務進行分析，各角度再從任務目標、任務執行過程、任務執行者、任務間依賴關系以及任務執行前提條件對使命任務進行建模。本文作者團隊[11]針對Zachman方法在任務分解與映射功能上的缺陷，借鑒功能流程框圖(Functional Flow Block Diagram，FFBD)[12]將任務分段繼而分析出具體的功能與信息需求，并通過仿真實驗證明這種跨平臺任務執行方式更為準確，有效提高了航電系統整體獲取和交互信息的效率。

在無人機任務分配問題上，目前已有的研究成果大多圍繞無人機執行任務時間、執行任務飛行距離作為優化目標進行任務分配，也存在以敵方剩余威脅最小或對敵干擾最大作為優化目標。表1根據無人機模型、蜂群模型、任務模型以及目標優化模型的特點，將近年來主要參考文獻中討論的模型和研究結果進行分類。本文根據調度模型中無人機節點數量以及拓撲特點，將蜂群模型分為單層、單架無人機，單層、多架無人機以及多層、大規模無人機3類；根據調度任務的復雜度，將任務模型分為粗粒度、細粒度2類；根據任務分配對象，即無人機模型的復雜程度，將無人機模型分為平臺級和模塊級，其中將無人機整體作為任務分配對象，即為平臺級無人機模型，若將任務分配到無人機內端系統，則為模塊級無人機模型。

根據表1所示[13-23]的無人機任務分配相關文獻的整理結果，可以得出以下結論：目前對無人機任務分配問題的研究大多為粗粒度任務模型、平臺級無人機模型以及單層無人機蜂群模型，未考慮無人機模塊層任務調度，以及大規模蜂群作戰任務調度情況，其任務調度模型可視為一種單層任務調度模型，在面對航電云架構下較復雜任務的調度，還需要對以上模型進行改進，使其適應于航電云架構下大規模無人機蜂群，以及復雜多任務作戰環境。

本文主要研究航電云中基于分層分簇網絡拓撲的無人機蜂群任務調度問題，提出一種精確到模塊級的多層任務調度模型。首先建立無人機蜂群分層分簇的資源虛擬化模型，將無人機模塊層到無人機簇群逐層虛擬化為資源池；設計包括使命組、使命、任務和子任務的4層任務模型；借鑒云計算中任務分配策略設計多層任務調度算法，并求解任務以及使命組耗費時間最短、各無人機數據交互的通信開銷最小等多個優化目標組成的各層目標函數。本文所提出的多層任務調度模型充分考慮了面向無人機蜂群的航電云資源結構的特殊性，提高任務并行性以保證任務完成時間。為驗證本文提出的模型，采用OMNeT++進行仿真，以云計算中常用任務調度算法——遺傳算法和貪心算法為例求解各目標函數，并與傳統的單層任務調度模型進行性能對比。

表1 近年無人機蜂群中任務分配文獻分類Table 1 Recent literature on task assignment in UAV swarm

1 無人機蜂群航電云

無人機蜂群航電云是一種為解決未來大規模無人機蜂群在資源有限條件下執行復雜使命任務問題的跨平臺航電綜合化方法，通過利用云計算中資源虛擬化思想實現蜂群資源的動態管理和分配。與以平臺為中心的傳統無人機蜂群作戰相比，航電云技術強調以網絡為中心，按使命任務資源需求分配相應的資源，充分利用網絡資源共享優勢和各無人機間任務交互協作，實現作戰能力的優勢互補。面向航電云的無人機蜂群資源共享能力更強、使命執行性能更好。

1.1 蜂群航電云模型

如圖1所示，無人機蜂群云端將蜂群資源統一管理并按服務的方式提供給各任務請求。蜂群航電云模型在文獻[3]中航電云所列舉的資源與服務的基礎上，如計算資源提供信息處理和計算等服務、存儲資源提供信息存儲服務、圖形處理資源提供圖像數據處理服務，加入無人機特有的傳感器資源提供信息收集服務，以及武器、彈藥等作戰資源提供攻擊和防御服務的內容。蜂群航電云模型中各類資源位于無人機機載端系統，經過資源虛擬化，形成資源池，交由簇首和云端分級統一管理，并根據使命任務需求進行任務調度。

圖1 面向無人機蜂群的航空電子云任務調度示意圖Fig.1 Schematic diagram of avionics cloud task scheduling for UAV swarm

1.2 無人機蜂群資源模型

無人機蜂群資源模型由分層分簇的虛擬資源池組成，其中包括云端資源池、簇群資源池和無人機資源池，以及實際的物理設備。其層次關系如圖2所示。

(1)

圖2 無人機蜂群資源層次結構Fig.2 Hierarchical structure of UAV swarm resources

(2)

(3)

在層次資源結構中，上層資源池各資源大小為下級各資源池相同資源的總和。以某簇群資源池Ck與無人機資源池資源關系為例，假設簇群資源池Ck中無人機資源池集合為{U1,U2,…,UP}，其資源關系為

(4)

式中：k、P和j分別表示該簇群的編號、無人機數量以及資源類型。

2 多層任務調度模型

在商業云計算應用系統中，任務調度模型主要將大量相互獨立的任務分配到有限個異構可用資源上，使得任務完成時間最小，并保證高效的資源利用率[24-25]。無人機蜂群多層任務調度模型設計理念來源于云計算中任務調度設計，由任務模型和多層任務調度算法兩部分組成。根據商業云計算中用戶提交的任務請求與資源映射關系，結合無人機作戰使命任務內容，提出無人機蜂群任務模型；借鑒云計算中服務器執行任務的時間開銷算法模型，考慮到由于無人機載荷、傳感器等作戰能力不同而存在執行任務能力的差異，設計出無人機多層任務調度算法部分，各層分別以f1、f2、f3為目標函數求解分配方案。

借鑒傳統無人機蜂群作戰場景[19-21]，對無人機蜂群應用場景作如下假設：

1) 各簇群中無人機出勤一次為執行一個使命組，執行使命組期間，不參與簇首任務分配。

2) 執行完使命組的無人機回到原簇群，再次提供資源，且各類資源大小不變。

3) 各無人機資源類型、大小可以不同。

4) 任務的某種資源需求不能分解，但可根據資源需求類型分解成多個子任務。

5) 本文不考慮各類資源分配差異，任務調度過程中各類資源分配方式相同。

2.1 任務模型

基于無人機蜂群層次資源模型，借鑒文獻[11]采用功能流程框圖對無人機蜂群作戰內容分層分段，建立使命組、使命、任務與子任務的層次任務模型，并定義各任務層資源需求關系。圖3為采用該方法為無人機攻擊任務建立的層次任務模型。

圖3 攻擊使命組FFBD分解圖Fig.3 Attack mission group FFBD exploded view

如圖3所示，攻擊使命組層往下為使命層，由目標偵測、搜索鎖定、綜合導航、信息融合和火力攻擊組成，各使命又可根據具體的功能再次被分解為作戰任務，如TD1、TD2到TF3等。各作戰任務存在相互協作關系，例如某任務執行完成，需發送數據處理的結果和完成狀態到后繼任務，由后繼任務根據數據處理結果完成后續內容，圖中分別采用單向虛線、單向實線表示使命內和使命間任務關系。圖3中采用藍色虛框對武器發射任務TF3進行標注，以表明任務、子任務在資源需求上的關系。

(5)

(6)

考慮具體的任務、使命以及使命組的區別，后續公式中增加下標k對其進行標識，如Tk、Mk、Gk表示。

參考云計算中任務與其子任務對計算、存儲以及網絡資源需求關系：任務對計算、存儲以及網絡資源需求大小為其所有子任務相同資源需求的總和，對無人機任務模型做相同處理，以使命Mk與其所包含任務為例，若使命Mk中任務集合為{T1,T2,…,TI}，其資源關系為

(7)

式中：k、I和j分別表示該使命的編號、任務數量以及所需資源類型。

同理，若使命組Gk中使命集合為{M1,M2,…,MJ}，則Gk對不同資源需求大小為

(8)

在實際端系統中，計算、存儲以及圖像處理等各功能模塊對任務中各資源需求處理時相互獨立，因此，在任務調度時，可對任務進行再分解。如圖3藍色虛框標注，任務TF3根據資源需求類型被分解成多個子任務，采用符號S表示，按照調度算法，分配到端系統中計算、存儲等功能模塊上，其過程如圖1機內端系統示意。

2.2 多層任務調度算法

多層任務調度算法基于資源模型和使命任務模型，其調度過程分為3層：云端使命組分配、平臺級任務分配和模塊級任務分配，各層分別以f1、f2、f3為目標函數計算分配方案，其中平臺級任務分配和模塊級任務分配分別以遺傳算法和貪心算法為例求解目標函數。

在多層任務調度算法中，需在3層任務調度層對使命組、使命以及任務完成時間進行計算，借鑒云計算中需求、資源以及時間的關系，即在資源有限的前提下，資源需求越大，任務完成時間越長，結合無人機蜂群中任務的不同資源需求類型，由此給出多層任務調度模型中對資源需求完成時間的計算公式。

定義1無人機蜂群中資源需求與資源的比值即為該資源需求完成的時間開銷。

(9)

為描述調度算法，后續將借助以下符號：

1)N為使命組分解后任務的數量。

2)Q為任務資源需求類型個數，同時也表示無人機蜂群中資源類型個數。

3)D為無人機之間的通信開銷常量，默認各無人機間通信開銷相等。

2.2.1 第1層：云端使命組分配

在第1層任務調度模型中，由無人機蜂群云端將使命組分配到完成時間最短的簇群，主要考慮使命組的完成時間，即對各資源需求的完成時間進行求和，并采用f1表示該層目標函數。

那么分配到簇群C，使命組G時間開銷為

(10)

為區分不同簇群下使命組G的完成時間，后續采用tG Ci表示。在僅考慮使命組完成時間開銷的情況下，云端使命組分配的目標函數為

f1=min(tG Ci)i=1,2,…,n

(11)

式中：云端按最小f1選擇最佳簇群分配。

在云計算中，所有用戶提交任務在時間上服從某種分布，且任務的分配和執行可能因資源不足而產生延遲[25]，在無人機蜂群中也同樣存在。在多層任務調度模型性能測試中，假設云端使命組達到率服從泊松分布，則分配時間間隔服從指數分布，令使命組達到率為λ，即：P(X>t)=e-λt，當f1低于最低容忍時間開銷ftol時，表明無人機蜂群負載過大，資源不足，需等待下次分配。

2.2.2 第2層：平臺級任務分配

在第2層任務調度，簇首選擇任務執行時間開銷與通信開銷最小的無人機集合進行分配。由此需要定義任務之間的關聯關系和通信開銷模型。任務與任務之間關聯采用有無模型，而通信開銷主要考慮不同無人機間任務消息傳輸和數據共享所需要的時間。

定義2任務與關聯關系ξij

(12)

定義3任務Tm與Tn間由于關聯性所產生的通信開銷φmn：

(13)

以圖3中具有關聯關系的TD3、TP1為例，若兩任務被分配到相同的無人機，則φ=0，否則φ=D。依據任務關聯和通信開銷，可以得到任務在某無人機上執行所需要的時間。

定義4任務T在無人機U上的時間開銷tT：

(14)

(15)

f2反映了當前任務調度層完成整個使命組所需要的時間開銷。

2.2.3 第3層：模塊級任務分配

在第3層任務調度，無人機內部控制器選擇單個任務完成時間和總任務完成時間最短的任務調度方案進行調度。假設該無人機被分配到任務{T1,T2,…,Tn}，由此，分別定義單個任務完成時刻和使命組完成時刻，以及目標函數f3，并采用tS、tT分別表示子任務、任務完成時刻。

定義5在無人機機載網絡中，單個任務T完成時間tT為最后一個子任務執行結束時刻

tT=max(tSi)Si=S1,S2,…，Sn

(16)

式中：S1,S2,…,Sn為任務T分解所得的子任務。

定義6所有任務完成時刻tAT為任務{T1,T2,…,Tn}中最后一個任務完成時刻：

tAT=max(tTi)Ti=T1,T2,…,Tn

(17)

式中：T1,T2,…,Tn由無人機蜂群應用場景假設1可知其屬于同一個使命組。

基于定義5和定義6，無人機內部控制器不僅需考慮單個任務，同時還需考慮所有任務總完成時間，由此定義f3：

f3=min(tT)+min(tG)

(18)

式中：f3需同時考慮到單個任務完成時間最小和所有任務總完成時間最小，由此決定任務到端系統的分配方案。

在多層任務調度算法中，輸入如圖3所示資源需求不同的攻擊使命組，經云端、簇首任務分配，在無人機內部進行調度。在無人機內部，控制器根據任務間關聯性以及各端系統空閑資源信息，將任務分解為子任務，并分配到端系統。子任務完成后，釋放端系統資源等待下一個子任務，當任務中最后一個子任務完成，則將該任務完成消息發生到后繼任務所在無人機，啟動后繼任務的調度。

3 仿真模型

本節在OMNeT++[26]仿真平臺上構建無人機仿真模型。通過簡單的無人機蜂群仿真實驗驗證仿真模型和配置參數的正確性和可行性。利用驗證通過的無人機模型和配置參數，設計航電云任務調度模型對比實驗。

3.1 模型驗證

為保證以該無人機模型搭建的任務調度實驗結果正確性，并對實際無人機蜂群研究具有可參考性，在OMNeT++仿真平臺中以美軍戰術瞄準網絡技術(Tactical Targeting Network Technology, TTNT)中180 km消息傳輸端到端時延最低為2 ms、無人機節點間數據鏈傳輸速率最大可達2 Mb·s-1為指標驗證無人機仿真模型可信度和配置參數的合理性。

模型驗證實驗采用如圖4所示網絡拓撲，按表2配置仿真場景、網絡拓撲等，其中數據鏈、交換機等配置參數參考美軍小型戰術無人機。模型驗證實驗中無人機節點保持靜態，各無人機節點以盡力傳輸(Best-Effort, BE)消息類型為例，并按表3消息源配置進行通信，根據消息端到端延遲驗證無人機節點仿真模型合理性。仿真結果如表4所示。

圖4 無人機仿真模型驗證實驗拓撲Fig.4 Topology for UAV simulation model verification experiment

由表4平均端到端延遲數據可見，在仿真時間500 s內，距離為200 km左右的無人機節點間平均端到端延遲基本保持在2 ms左右。模型驗證實驗表明：按以上配置參數配置的無人機仿真模型與實際無人機模型具有較高的相似度，可用于后續航電云任務調度模型對比實驗。

表2 模型驗證實驗參數配置Table 2 Parameter configuration for model verification experiment

表3 模型驗證實驗消息源配置Table 3 Message source configuration for model verification experiment

表4 消息平均端到端延遲對比Table 4 Comparison of average end-to-end delay of messages

3.2 對比實驗

在OMNeT++下搭建如圖5和圖6所示無人機蜂群進行航電云任務調度模型對比實驗。對比實驗包括：分層分簇與單層網絡拓撲對比、多層任務調度與單層任務調度模型對比。

傳統無人機蜂群單層任務調度模型為單個簇首向100個平臺級無人機節點分配任務，如圖5所示。無人機蜂群多層任務調度模型將100架模塊級無人機節點分別劃分為5個無人機簇群，分別由5個無人機簇首管理，如圖6所示。

如圖5所示，傳統的無人機蜂群作戰網絡拓撲可歸納為單層網絡拓撲，由簇首與普通無人機組成，其任務調度模型為單層平臺級任務調度模型。單層任務調度模型與多層任務調度模型中第2層平臺級任務分配方式類似，其采用的無人機節點僅為平臺級節點，無模塊級任務調度，若將多層任務調度模型中無人機端系統數量配置為1，則兩模型實驗結果相同。

如圖6所示，無人機蜂群多層任務調度模型包括3層任務調度：云端使命組分配、平臺級任務分配和模塊級任務分配，且采用分層分簇的網絡拓撲。多層任務調度模型中，采用如圖6(c)所示模塊級無人機仿真節點，節點內部包括控制器、端系統和交換機，控制器負責資源池管理和任務分配，各端系統為各類資源物理位置，負責執行各子任務。

圖5 單層100架無人機蜂群實驗拓撲Fig.5 Experiment topology of single-layer 100 UAV swarm

圖6 多層100架無人機蜂群實驗拓撲Fig.6 Experiment topology of multi-layer 100 UAV swarm

實驗中，利用OMNeT++提供的統計接口進行相關數據收集。在不限制使命組數量情況下，統計任務吞吐量與平均端到端延遲，構建分層分簇與單層網絡拓撲對比實驗；在使命組數量有限情況下，統計使命組完成時間和單個任務完成時間，構建多層任務調度與單層任務調度模型對比實驗。兩種模型按表2中資源范圍和資源需求范圍對無人機蜂群資源和攻擊使命組資源需求進行初始化，同時根據仿真場景、數據鏈等其他參數對無人機蜂群仿真模型進行配置。

4 仿真結果與分析

仿真結果分析包括分層分簇與單層網絡拓撲對比實驗、多層任務調度模型與單層任務調度模型對比實驗。各實驗分別從網絡拓撲、任務時間開銷的角度對比兩種任務調度模型的性能。

4.1 分層分簇與單層網絡拓撲對比

在不限制使命組數量的前提下，對多層任務調度模型與傳統單層任務調度模型的網絡拓撲進行對比。實驗中設置使命組分配間隔呈指數分布，參數λ=3，最低容忍時間開銷ftol=0.2。在兩種網絡拓撲下任務吞吐量性能測試曲線如圖7所示，任務間消息傳輸端到端延遲分布如圖8所示。

圖7 任務吞吐量性能測試曲線Fig.7 Test curves of task throughput performance

圖8 任務間消息傳輸端到端延0遲分布Fig.8 Distribution of end-to-end delay of message transmission between tasks

從圖7可以得出：在前期，兩種任務調度模型任務吞吐量基本相同，后續由于單層調度模型較早出現資源不足現象，任務吞吐量停止增長，并且由于使命執行時間較長導致與多層任務調度模型任務吞吐量間距拉大，后期由于部分使命組完成，任務吞吐量開始增長，但單層任務調度模型任務吞吐量始終低于多層任務調度模型。

圖8展示出兩種網絡中消息端到端延遲分

布，根據統計，兩種網絡80%的端到端延遲數據在2 ms左右，其中單層網絡拓撲中端到端延遲大小在4 ms以上數據占11%，分層分簇網絡拓撲為3%。容易得出：分層分簇無人機蜂群拓撲消息端到端延遲在實時性以及穩定性上優于傳統單層無人機蜂群模型，且傳統的無人機蜂群易造成嚴重的消息延遲。

4.2 多層任務調度與單層任務調度模型對比

為對比模塊級多層任務調度與單層任務調度模型在執行任務性能上的差異，配置兩種模型分別間隔性下發16個作戰使命組，其中參數λ和ftol與分層分簇與單層網絡拓撲對比實驗保持一致，進行10次仿真實驗，并取10次實驗平均結果進行分析，如圖9和圖10所示。

圖9 兩種任務調度模型的任務執行時間分布Fig.9 Distribution of task execution time of two task scheduling models

1) 單個任務執行時間

圖9為兩種任務調度策略下單個任務執行時間在[1，32] s區間分布圖。從圖9可以得到：非模塊級單層任務調度模型任務執行時間普遍較長，且分散在[3，31] s區間上，任務平均完成時間為17.58 s。相比，由于多層任務調度模型存在第3層模塊級任務調度，無人機內可并行執行多個任務，任務執行時間明顯較短，約占整體64.7%集中于[8，10] s，任務平均完成時間為9.45 s，較前者任務平均完成時間約下降46.2%。

2) 使命組完成時間

圖10為兩種任務調度策略下16個使命組完成時刻統計曲線。為便于統計，按完成時間先后順序對使命組編號，并采用線性回歸方法求出兩種模型下使命組完成時間增長曲線，如圖中綠線與紅線所示。

圖10 兩種任務調度模型使命組完成時間趨勢圖Fig.10 Trend graph of mission group completion time of two task scheduling models

從圖10可以得出：隨著執行使命組數量的增加，兩種調度模型下使命組完成時間呈現遞增現象，且增長速率不同：非模塊級單層任務調度模型下，使命組時間開銷增長率為5.07 s/使命組，模塊級多層任務調度模型增長率為2.43 s/使命組。兩模型相比，模塊級多層任務調度模型將使命組完成時間開銷增長率降低了52.1%，因此具有任務執行效率高、執行時間開銷較穩定的優勢。

5 結 論

本文所提出的基于航電云的無人機多層任務調度模型，其分層調度以及精確到無人機模塊級的調度策略有利于縮減傳統無人機蜂群任務調度模型中執行任務的時間開銷，實現云端到無人機的復雜任務分配。多層任務調度模型的仿真結果表明：

1) 基于資源需求的細粒度4層無人機任務模型具有通用性強、算法部署簡單的優點，可用于大規模無人機蜂群復雜任務模型描述。

2) 模塊級多層任務調度和傳統單層任務調度相比：在網絡拓撲上，多層任務調度模型采用的分層分簇網絡拓撲任務吞吐量高于單層任務調度模型所采用的單層網絡拓撲，且網絡實時性以及穩定性優于單層網絡拓撲；在執行作戰任務上，模塊級多層任務調度模型單個任務執行時間短且分布集中、使命組完成時間低于非模塊級單層任務調度模型。

后續工作將加入移動模型到無人機節點中，研究高動態變化拓撲下的航電云任務調度問題，并對任務調度算法進行改進。