面向无人机蜂群的航电云多层任务调度模型

王荣巍，何锋，周璇，鲁俊，李二帅

北京航空航天大学 电子信息工程学院，北京 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) 模块级多层任务调度和传统单层任务调度相比：在网络拓扑上，多层任务调度模型采用的分层分簇网络拓扑任务吞吐量高于单层任务调度模型所采用的单层网络拓扑，且网络实时性以及稳定性优于单层网络拓扑；在执行作战任务上，模块级多层任务调度模型单个任务执行时间短且分布集中、使命组完成时间低于非模块级单层任务调度模型。

后续工作将加入移动模型到无人机节点中，研究高动态变化拓扑下的航电云任务调度问题，并对任务调度算法进行改进。