文章快速检索  
  高级检索
面向无人机蜂群的航电云多层任务调度模型
王荣巍, 何锋, 周璇, 鲁俊, 李二帅     
北京航空航天大学 电子信息工程学院, 北京 100083
摘要: 在航空作战体系中,基于航电云的无人机(UAV)蜂群作战是提高未来无人机综合作战能力的一种新模式。针对无人机蜂群作战的航电云架构,如何将云端作战任务派发到无人机且保证作战任务完成时间是其中关键。在无人机蜂群分层分簇网络结构和模块级资源虚拟化的基础上,对传统单层平台级任务调度模型进行改进,提出了一种细化到模块级的多层任务调度模型,将作战任务从云端逐层调度到无人机功能模块上执行。利用OMNeT++对无人机蜂群多层任务调度模型以及传统的单层任务调度模型分别进行仿真,云端以攻击使命组为例构建使命组集进行分配,并对任务吞吐量、消息平均端到端延时和任务完成时间进行性能对比。仿真结果表明:与平台级单层任务调度相比,在执行任务方面,模块级多层任务调度模型将单个任务平均完成时间降低了46.2%,将使命组完成时间降低了52.1%,在保证任务吞吐量的基础上具有对复杂任务更稳定的调度能力;在网络性能方面,模块级多层任务调度模型消息端到端延时更低,延时分布更集中,提高了网络消息传输的实时性。
关键词: 无人机蜂群     航电云     任务调度     分层分簇     任务吞吐量    
Avionics cloud multi-layer task scheduling model for UAV swarm
WANG Rongwei, HE Feng, ZHOU Xuan, LU Jun, LI Ershuai     
School of Electronics and Information Engineering, Beihang University, Beijing 100083, China
Abstract: In the aviation combat system, Unmanned Aerial Vehicle (UAV) swarm based on avionics cloud is a new model for improving the overall combat capability of future UAV. For the avionics cloud architecture of UAV swarm, how to distribute the cloud combat mission to the UAV and ensure the punctuality of mission completion is the key. Based on the hierarchical clustering network structure and module-level resource virtualization of UAV swarm, this paper improves the traditional single-layer platform-level task scheduling model, and proposes a multi-layer task scheduling model that is refined to the module level. The mission is scheduled from the cloud to the UAV function module. OMNeT++ is used to simulate the multi-layer mission scheduling model of UAV swarm and the traditional single-layer task scheduling model. The cloud uses the attack mission group as an example to construct the mission group for allocation and performance comparison of task throughput, message average end-to-end delay, and task completion time. The simulation results show that compared with the platform-level single-layer task scheduling, the module-level multi-task scheduling model reduces the average completion time of a single task by 46.2% and the mission group completion time by 52.1%. In addition to guarantee of throughput, the model proposed has more stable scheduling capability for complex tasks. In terms of network performance, the module-level multi-layer task scheduling model has lower end-to-end delay and more concentrated delay distribution, which improves the real-time performance of network message transmission.
Keywords: Unmanned Aerial Vehicle (UAV) swarm     avionics cloud     task scheduling     hierarchical clustering     task throughput    

航空电子云系统架构,简称航电云[1-3],来源于互联网云计算思想,通过虚拟化航电系统资源(例如通信设备,各种传感器)为资源池,以进行资源的统一管理和按需服务。航电云不仅对单平台资源进行虚拟,而且可将资源共享范围从单平台扩充到多系统平台,使跨系统资源综合实现成为可能[4-5]

无人机蜂群作战是一种抗干扰性强、成本低、作战灵活的作战体系。无人机蜂群作战能力取决于总体架构、集群感知与信息融合、集群控制与群体智能、任务规划和航迹规划等关键技术的研究[6]。面向无人机蜂群作战的航电云,是航空电子云中由无人机蜂群组成的特殊云,为解决大规模无人机蜂群作战而提出。

国内航电云研究[1-3]分别从云服务架构、模型描述、网络架构和跨平台资源虚拟化等不同角度逐渐完善航空电子云概念。在具体应用方面,文献[7-9]将云概念、软件定义网络技术引入到航空集群和现代交通控制,分别提出软件定义航空集群机载战术网络技术、集中控制式网络部署方法和智能交通信息物理融合云控制系统,以提高复杂和高动态网络环境下航空集群作战能力和智能交通控制系统运行性能。

在无人机蜂群作战中,任务调度由任务分解和任务分配组成。针对一般航空作战任务分解问题,王国庆等[10]引入Zachman复杂系统组织设计方法从任务需求、任务模式、任务能力、任务响应、任务组织和任务管理6个角度对使命任务进行分析,各角度再从任务目标、任务执行过程、任务执行者、任务间依赖关系以及任务执行前提条件对使命任务进行建模。本文作者团队[11]针对Zachman方法在任务分解与映射功能上的缺陷,借鉴功能流程框图(Functional Flow Block Diagram,FFBD)[12]将任务分段继而分析出具体的功能与信息需求,并通过仿真实验证明这种跨平台任务执行方式更为准确,有效提高了航电系统整体获取和交互信息的效率。

在无人机任务分配问题上,目前已有的研究成果大多围绕无人机执行任务时间、执行任务飞行距离作为优化目标进行任务分配,也存在以敌方剩余威胁最小或对敌干扰最大作为优化目标。表 1根据无人机模型、蜂群模型、任务模型以及目标优化模型的特点,将近年来主要参考文献中讨论的模型和研究结果进行分类。本文根据调度模型中无人机节点数量以及拓扑特点,将蜂群模型分为单层、单架无人机,单层、多架无人机以及多层、大规模无人机3类;根据调度任务的复杂度,将任务模型分为粗粒度、细粒度2类;根据任务分配对象,即无人机模型的复杂程度,将无人机模型分为平台级和模块级,其中将无人机整体作为任务分配对象,即为平台级无人机模型,若将任务分配到无人机内端系统,则为模块级无人机模型。

表 1 近年无人机蜂群中任务分配文献分类 Table 1 Recent literature on task assignment in UAV swarm
相关模型 模型分类 相关文献
无人机模型 平台级 文献[13-23]
模块级 暂无
蜂群模型 单层、单架无人机 文献[14, 19-21]
单层、多架无人机 文献[13, 15-18, 22-23]
多层、大规模无人机 暂无
任务模型 粗粒度 文献[13-17, 19-23]
细粒度 文献[17]
目标优化模型 执行任务时间 文献[13, 15-16, 18-20, 22]
通信开销 文献[17]
飞行航程 文献[21-22]
对敌干扰、攻击 文献[14, 23]

根据表 1所示[13-23]的无人机任务分配相关文献的整理结果,可以得出以下结论:目前对无人机任务分配问题的研究大多为粗粒度任务模型、平台级无人机模型以及单层无人机蜂群模型,未考虑无人机模块层任务调度,以及大规模蜂群作战任务调度情况,其任务调度模型可视为一种单层任务调度模型,在面对航电云架构下较复杂任务的调度,还需要对以上模型进行改进,使其适应于航电云架构下大规模无人机蜂群,以及复杂多任务作战环境。

本文主要研究航电云中基于分层分簇网络拓扑的无人机蜂群任务调度问题,提出一种精确到模块级的多层任务调度模型。首先建立无人机蜂群分层分簇的资源虚拟化模型,将无人机模块层到无人机簇群逐层虚拟化为资源池;设计包括使命组、使命、任务和子任务的4层任务模型;借鉴云计算中任务分配策略设计多层任务调度算法,并求解任务以及使命组耗费时间最短、各无人机数据交互的通信开销最小等多个优化目标组成的各层目标函数。本文所提出的多层任务调度模型充分考虑了面向无人机蜂群的航电云资源结构的特殊性,提高任务并行性以保证任务完成时间。为验证本文提出的模型,采用OMNeT++进行仿真,以云计算中常用任务调度算法——遗传算法和贪心算法为例求解各目标函数,并与传统的单层任务调度模型进行性能对比。

1 无人机蜂群航电云

无人机蜂群航电云是一种为解决未来大规模无人机蜂群在资源有限条件下执行复杂使命任务问题的跨平台航电综合化方法,通过利用云计算中资源虚拟化思想实现蜂群资源的动态管理和分配。与以平台为中心的传统无人机蜂群作战相比,航电云技术强调以网络为中心,按使命任务资源需求分配相应的资源,充分利用网络资源共享优势和各无人机间任务交互协作,实现作战能力的优势互补。面向航电云的无人机蜂群资源共享能力更强、使命执行性能更好。

1.1 蜂群航电云模型

图 1所示,无人机蜂群云端将蜂群资源统一管理并按服务的方式提供给各任务请求。蜂群航电云模型在文献[3]中航电云所列举的资源与服务的基础上,如计算资源提供信息处理和计算等服务、存储资源提供信息存储服务、图形处理资源提供图像数据处理服务,加入无人机特有的传感器资源提供信息收集服务,以及武器、弹药等作战资源提供攻击和防御服务的内容。蜂群航电云模型中各类资源位于无人机机载端系统,经过资源虚拟化,形成资源池,交由簇首和云端分级统一管理,并根据使命任务需求进行任务调度。

图 1 面向无人机蜂群的航空电子云任务调度示意图 Fig. 1 Schematic diagram of avionics cloud task scheduling for UAV swarm
1.2 无人机蜂群资源模型

无人机蜂群资源模型由分层分簇的虚拟资源池组成,其中包括云端资源池、簇群资源池和无人机资源池,以及实际的物理设备。其层次关系如图 2所示。

图 2 无人机蜂群资源层次结构 Fig. 2 Hierarchical structure of UAV swarm resources

图 2所示无人机蜂群层次结构图中,从底层资源模型到顶层资源模型依次为机内端系统通用资源、无人机资源池、簇群资源池和云端资源池,分别采用符号EUCB表示,其中端系统为各资源的物理位置,可提供不同类型服务。任一端系统资源池采用E={r1E, r2E, …, rnE}进行定义,其他层资源模型从下往上分别为

$ U = \left\{ {r_1^U,r_2^U, \cdots ,r_n^U} \right\} $ (1)
 
$ C = \left\{ {r_1^C,r_2^C, \cdots ,r_n^C} \right\} $ (2)
 
$ B = \left\{ {r_1^B,r_2^B, \cdots ,r_n^B} \right\} $ (3)
 

式中:rnErnUrnC以及rnB分别为不同层次资源结构的资源池中第n类资源的大小,代表单位时间内对第n类资源需求的处理能力(如计算、存储、图像处理以及武器资源)。由于存在不同的端系统、无人机以及簇群,在后续公式中增加下标k对其进行标识,如EkUkCk进行区分。

在层次资源结构中,上层资源池各资源大小为下级各资源池相同资源的总和。以某簇群资源池Ck与无人机资源池资源关系为例,假设簇群资源池Ck中无人机资源池集合为{U1, U2, …, UP},其资源关系为

$ {C_k} = \left\{ {r_j^{{C_k}}|r_j^{{C_k}} = \sum\limits_{i = 1}^P {r_j^{{U_i}}} ,j \in \left( {1,n} \right)} \right\} $ (4)
 

式中:kPj分别表示该簇群的编号、无人机数量以及资源类型。

2 多层任务调度模型

在商业云计算应用系统中,任务调度模型主要将大量相互独立的任务分配到有限个异构可用资源上,使得任务完成时间最小,并保证高效的资源利用率[24-25]。无人机蜂群多层任务调度模型设计理念来源于云计算中任务调度设计,由任务模型和多层任务调度算法两部分组成。根据商业云计算中用户提交的任务请求与资源映射关系,结合无人机作战使命任务内容,提出无人机蜂群任务模型;借鉴云计算中服务器执行任务的时间开销算法模型,考虑到由于无人机载荷、传感器等作战能力不同而存在执行任务能力的差异,设计出无人机多层任务调度算法部分,各层分别以f1f2f3为目标函数求解分配方案。

借鉴传统无人机蜂群作战场景[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进行标注,以表明任务、子任务在资源需求上的关系。

在任务资源需求模型中,采用TMG表示任务、使命以及使命组,采用符号s表示各层在单位时间内执行完所需资源大小,例如任务T={s1T, s2T, …, snT}表示单位时间内执行完任务T所需不同资源大小。同理,使命以及使命组对资源需求表示为

$ M = \left\{ {s_1^M,s_2^M, \cdots ,s_n^M} \right\} $ (5)
 
$ G = \left\{ {s_1^G,s_2^G, \cdots ,s_n^G} \right\} $ (6)
 

考虑具体的任务、使命以及使命组的区别,后续公式中增加下标k对其进行标识,如TkMkGk表示。

参考云计算中任务与其子任务对计算、存储以及网络资源需求关系:任务对计算、存储以及网络资源需求大小为其所有子任务相同资源需求的总和,对无人机任务模型做相同处理,以使命Mk与其所包含任务为例,若使命Mk中任务集合为{T1, T2, …, TI},其资源关系为

$ {M_k} = \left\{ {s_j^{{M_k}}|s_j^{{M_k}} = \sum\limits_{i = 1}^I {s_j^{{T_i}}} ,j \in (1,n)} \right\} $ (7)
 

式中:kIj分别表示该使命的编号、任务数量以及所需资源类型。

同理,若使命组Gk中使命集合为{M1, M2, …, MJ},则Gk对不同资源需求大小为

$ {G_k} = \left\{ {s_j^{{G_k}}|s_j^{{G_k}} = \sum\limits_{i = 1}^J {s_j^{{M_i}}} ,j \in (1,n)} \right\} $ (8)
 

在实际端系统中,计算、存储以及图像处理等各功能模块对任务中各资源需求处理时相互独立,因此,在任务调度时,可对任务进行再分解。如图 3蓝色虚框标注,任务TF3根据资源需求类型被分解成多个子任务,采用符号S表示,按照调度算法,分配到端系统中计算、存储等功能模块上,其过程如图 1机内端系统示意。

2.2 多层任务调度算法

多层任务调度算法基于资源模型和使命任务模型,其调度过程分为3层:云端使命组分配、平台级任务分配和模块级任务分配,各层分别以f1f2f3为目标函数计算分配方案,其中平台级任务分配和模块级任务分配分别以遗传算法和贪心算法为例求解目标函数。

在多层任务调度算法中,需在3层任务调度层对使命组、使命以及任务完成时间进行计算,借鉴云计算中需求、资源以及时间的关系,即在资源有限的前提下,资源需求越大,任务完成时间越长,结合无人机蜂群中任务的不同资源需求类型,由此给出多层任务调度模型中对资源需求完成时间的计算公式。

定义1   无人机蜂群中资源需求与资源的比值即为该资源需求完成的时间开销。

$ t = \frac{s}{r} $ (9)
 

式中:srt分别表示资源需求、资源以及时间开销,并采用tStTtG表示子任务、任务以及使命组完成所需的时间,在表示具体资源需求的时间开销时,如第j类资源需求完成时间,采用tjStjTtjG进行区分。

为描述调度算法,后续将借助以下符号:

1) N为使命组分解后任务的数量。

2) Q为任务资源需求类型个数,同时也表示无人机蜂群中资源类型个数。

3) D为无人机之间的通信开销常量,默认各无人机间通信开销相等。

2.2.1 第1层:云端使命组分配

在第1层任务调度模型中,由无人机蜂群云端将使命组分配到完成时间最短的簇群,主要考虑使命组的完成时间,即对各资源需求的完成时间进行求和,并采用f1表示该层目标函数。

由定义1可知:使命组G分到簇群C完成第j类资源需求所需时间tjG为使命组G中第j类资源需求sjG与簇群Cj类资源rjC的比值,即

$ t_j^{GC} = s_j^G/r_j^C $

那么分配到簇群C,使命组G时间开销为

$ {t^{GC}} = \sum\limits_{j = 1}^Q {t_j^{GC}} $ (10)
 

为区分不同簇群下使命组G的完成时间,后续采用t GCi表示。在仅考虑使命组完成时间开销的情况下,云端使命组分配的目标函数为

$ {f_1} = \min \left( {{t^{G{C_i}}}} \right)\;\;\;\;i = 1,2, \cdots ,n $ (11)
 

式中:云端按最小f1选择最佳簇群分配。

在云计算中,所有用户提交任务在时间上服从某种分布,且任务的分配和执行可能因资源不足而产生延迟[25],在无人机蜂群中也同样存在。在多层任务调度模型性能测试中,假设云端使命组达到率服从泊松分布,则分配时间间隔服从指数分布,令使命组达到率为λ,即:P(X>t)=eλt,当f1低于最低容忍时间开销ftol时,表明无人机蜂群负载过大,资源不足,需等待下次分配。

2.2.2 第2层:平台级任务分配

在第2层任务调度,簇首选择任务执行时间开销与通信开销最小的无人机集合进行分配。由此需要定义任务之间的关联关系和通信开销模型。任务与任务之间关联采用有无模型,而通信开销主要考虑不同无人机间任务消息传输和数据共享所需要的时间。

定义2   任务与关联关系ξij

$ {\xi _{ij}} = \left\{ {\begin{array}{*{20}{l}} 0&{{T_i},{T_j}\;无关联或\;i = j}\\ 1&{{T_i},{T_j}\;有关联} \end{array}} \right. $ (12)
 

定义3   任务TmTn间由于关联性所产生的通信开销ϕmn

$ {\phi _{mn}} = \left\{ {\begin{array}{*{20}{l}} {{\xi _{mn}}D}&{m \ne n}\\ 0&{m = n} \end{array}} \right. $ (13)
 

图 3中具有关联关系的TD3、TP1为例,若两任务被分配到相同的无人机,则ϕ=0,否则ϕ=D。依据任务关联和通信开销,可以得到任务在某无人机上执行所需要的时间。

定义4   任务T在无人机U上的时间开销tT

$ {t^T} = \sum\limits_{n = 1}^Q {\frac{{s_n^T}}{{r_n^U}}} $ (14)
 

同理,若采用ui表示任务Ti被分配到的无人机编号,则有${t^{{T_i}}} = \sum\limits_{n = 1}^Q {\frac{{s_n^{{T_i}}}}{{r_n^{{U_{{u_i}}}}}}} $。那么使命组完成时间开销与通信开销之和f2可以表示为

$ {f_2} = \sum\limits_{i = 1}^N {{t^{{T_i}}}} + \sum\limits_j^N {\sum\limits_i^N {{\phi _{ij}}} } $ (15)
 

f2反映了当前任务调度层完成整个使命组所需要的时间开销。

2.2.3 第3层:模块级任务分配

在第3层任务调度,无人机内部控制器选择单个任务完成时间和总任务完成时间最短的任务调度方案进行调度。假设该无人机被分配到任务{T1, T2, …, Tn},由此,分别定义单个任务完成时刻和使命组完成时刻,以及目标函数f3,并采用tStT分别表示子任务、任务完成时刻。

定义5   在无人机机载网络中,单个任务T完成时间tT为最后一个子任务执行结束时刻

$ {t^T} = \max \left( {{t^{{S_i}}}} \right)\;\;\;\;{S_i} = {S_1},{S_2}, \cdots ,{S_n} $ (16)
 

式中:S1, S2, …, Sn为任务T分解所得的子任务。

定义6   所有任务完成时刻tAT为任务{T1, T2, …, Tn}中最后一个任务完成时刻:

$ {t^{AT}} = \max \left( {t_t^{{T_i}}} \right)\;\;\;\;{T_i} = {T_1},{T_2}, \cdots ,{T_n} $ (17)
 

式中:T1, T2, …, Tn由无人机蜂群应用场景假设1可知其属于同一个使命组。

基于定义5和定义6,无人机内部控制器不仅需考虑单个任务,同时还需考虑所有任务总完成时间,由此定义f3

$ {f_3} = \min \left( {{t^T}} \right) + \min \left( {{t^G}} \right) $ (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
表 2 模型验证实验参数配置 Table 2 Parameter configuration for model verification experiment
参数 数值
仿真场景/km2 1 000×1 000
机载交换机 2
端系统数量 6
数据链L1速率/
(Mb·s-1)
2
机内L2速率/
(Mb·s-1)
100
机内L3速率/
(Mb·s-1)
100
交换机延时/μs 10
消息类型 BE
资源种类 6
资源范围 0~100
资源需求范围 0~500
无人机距离/km 200
表 3 模型验证实验消息源配置 Table 3 Message source configuration for model verification experiment
消息标识 周期/s 最大帧长/Byte 源节点ID 目的节点ID 传输距离/km
101 2 100 1 2/3 180/220
102 5 100 2 1 180
103 5 100 3 2 240
104 10 100 4 2/3 220/180
105 1 100 3 4 180
表 4 消息平均端到端延迟对比 Table 4 Comparison of average end-to-end delay of messages
消息标识 仿真时间/s 传输速率/(Mb·s-1) 机载带宽/(Mb·s-1) 最大帧长/Byte 平均端到端延迟/ms
101 500 2 100 100 2.225
102 500 2 100 100 2.101
103 500 2 100 100 1.851
104 500 2 100 100 1.601
105 500 2 100 100 1.702

表 4平均端到端延迟数据可见,在仿真时间500 s内,距离为200 km左右的无人机节点间平均端到端延迟基本保持在2 ms左右。模型验证实验表明:按以上配置参数配置的无人机仿真模型与实际无人机模型具有较高的相似度,可用于后续航电云任务调度模型对比实验。

3.2 对比实验

在OMNeT++下搭建如图 5图 6所示无人机蜂群进行航电云任务调度模型对比实验。对比实验包括:分层分簇与单层网络拓扑对比、多层任务调度与单层任务调度模型对比。

图 5 单层100架无人机蜂群实验拓扑 Fig. 5 Experiment topology of single-layer 100 UAV swarm
图 6 多层100架无人机蜂群实验拓扑 Fig. 6 Experiment topology of multi-layer 100 UAV swarm

传统无人机蜂群单层任务调度模型为单个簇首向100个平台级无人机节点分配任务,如图 5所示。无人机蜂群多层任务调度模型将100架模块级无人机节点分别划分为5个无人机簇群,分别由5个无人机簇首管理,如图 6所示。

图 5所示,传统的无人机蜂群作战网络拓扑可归纳为单层网络拓扑,由簇首与普通无人机组成,其任务调度模型为单层平台级任务调度模型。单层任务调度模型与多层任务调度模型中第2层平台级任务分配方式类似,其采用的无人机节点仅为平台级节点,无模块级任务调度,若将多层任务调度模型中无人机端系统数量配置为1,则两模型实验结果相同。

图 6所示,无人机蜂群多层任务调度模型包括3层任务调度:云端使命组分配、平台级任务分配和模块级任务分配,且采用分层分簇的网络拓扑。多层任务调度模型中,采用如图 6(c)所示模块级无人机仿真节点,节点内部包括控制器、端系统和交换机,控制器负责资源池管理和任务分配,各端系统为各类资源物理位置,负责执行各子任务。实验中,利用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) 模块级多层任务调度和传统单层任务调度相比:在网络拓扑上,多层任务调度模型采用的分层分簇网络拓扑任务吞吐量高于单层任务调度模型所采用的单层网络拓扑,且网络实时性以及稳定性优于单层网络拓扑;在执行作战任务上,模块级多层任务调度模型单个任务执行时间短且分布集中、使命组完成时间低于非模块级单层任务调度模型。

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

参考文献
[1] LI Z, LI Q, XIONG H G. Avionics clouds: A generic scheme for future avionics systems[C]//Digital Avionics Systems Conference. Piscataway, NJ: IEEE Press, 2012: 6E4-1-6E4-10.
[2] 屠晓杰.航空电子云的系统设计与性能分析关键技术研究[D].北京: 北京航空航天大学, 2013.
TU X J. Research on key technologies in avionics clouds design and performance analysis[D]. Beijing: Beihang University, 2013(in Chinese).
[3] 鲁俊, 何锋, 熊华钢. 航空电子云系统架构与网络[J]. 航空电子技术, 2017, 48(3): 1-9.
LU J, HE F, XIONG H G. System and network architecture of avionics cloud[J]. Avionics Technology, 2017, 48(3): 1-9. (in Chinese)
Cited By in Cnki (2) | Click to display the text
[4] KIM D H, SONG S, SHIN S J, et al. An extended cloud computing architecture for immediate sharing of avionic contents[C]//Advanced Communication and Networking. Berlin, Heidelberg: Springer, 2011: 439-446.
[5] JASTI A, MOHAPATRA S, POTLURI B, et al. Cloud computing in aircraft data network[C]//Integrated Communications, Navigation and Surveillance Conference (ICNS). Piscataway, NJ: IEEE Press, 2011: E7-1-E7-8.
[6] 钮伟, 黄佳沁, 缪礼锋. 无人机蜂群对海作战概念与关键技术研究[J]. 指挥控制与仿真, 2018, 40(1): 20-27.
NIU W, HUANG J Q, MIU L F. Research on the concept and key technologies of unmanned aerial vehicle swarm concerning naval attack[J]. Command Control & Simulation, 2018, 40(1): 20-27. (in Chinese)
Cited By in Cnki (12) | Click to display the text
[7] 赵尚弘, 陈柯帆, 吕娜, 等. 软件定义航空集群机载战术网络[J]. 通信学报, 2017, 38(8): 140-155.
ZHAO S H, CHEN K F, LYU N, et al. Software defined airborne tactical network for aeronautic swarm[J]. Journal on Communications, 2017, 38(8): 140-155. (in Chinese)
Cited By in Cnki (9) | Click to display the text
[8] 吕娜, 刘创, 陈柯帆, 等. 一种面向航空集群的集中控制式网络部署方法[J]. 航空学报, 2018, 39(7): 321961.
LYU N, LIU C, CHEN K F, et al. A method for centralized control network deployment of aeronautic swarm[J]. Acta Aeronautica et Astronautica Sinica, 2018, 39(7): 321961. (in Chinese)
Cited By in Cnki (5) | Click to display the text
[9] 夏元清, 闫策, 王笑京, 等. 智能交通信息物理融合云控制系统[J]. 自动化学报, 2019, 45(1): 132-142.
XIA Y Q, YAN C, WANG X J, et al. Intelligent transportation cyber-physical cloud control systems[J]. Acta Automatica Sinica, 2019, 45(1): 132-142. (in Chinese)
Cited By in Cnki (3) | Click to display the text
[10] 王国庆, 谷青范, 王淼, 等. 新一代综合化航空电子系统构架技术研究[J]. 航空学报, 2014, 35(6): 1473-1486.
WANG G Q, GU Q F, WANG M, et al. Research on the architecture technology for new generation integrated avionics system[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35(6): 1473-1486. (in Chinese)
Cited By in Cnki (54) | Click to display the text
[11] 李振, 李峭, 熊华钢. 基于使命任务分解的航空电子跨平台通信组织与仿真[J]. 航空电子技术, 2015, 46(1): 10-14.
LI Z, LI Q, XIONG H G. Organization and simulation of cross-platform communication of avionics based on mission decomposition[J]. Avionics Technology, 2015, 46(1): 10-14. (in Chinese)
Cited By in Cnki | Click to display the text
[12] Federal Aviation Administration. Task analysis tools used throughout development[M]. Washington, D.C.: FAA, 2008.
[13] 廖沫, 陈宗基, 周锐. 基于MAS的多UAV协同任务分配设计与仿真[J]. 系统仿真学报, 2007, 19(10): 2313-2317.
LIAO M, CHEN Z J, ZHOU R. Design and simulation of multi-UAV coordinated task allocation based on MAS[J]. Journal of System Simulation, 2007, 19(10): 2313-2317. (in Chinese)
Cited By in Cnki (28) | Click to display the text
[14] 赵振宇, 卢广山, 廖沫, 等. 基于DTC和GPGP的多UCAV任务规划方法[J]. 北京航空航天大学学报, 2011, 37(3): 305-310.
ZHAO Z Y, LU G S, LIAO M, et al. Mission planning of multiple UCAV based on DTC and GPGP[J]. Journal of Beijing University of Aeronautics and Astronautics, 2011, 37(3): 305-310. (in Chinese)
Cited By in Cnki (13) | Click to display the text
[15] 魏政磊, 赵辉, 黄汉桥, 等. 基于SAGWO算法的UCAVs动态协同任务分配[J]. 北京航空航天大学学报, 2018, 44(8): 1651-1664.
WEI Z L, ZHAO H, HUANG H Q, et al. Dynamic UCAVs cooperative task allocation based on SAGWO algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(8): 1651-1664. (in Chinese)
Cited By in Cnki (1) | Click to display the text
[16] BRUNET L, CHOI H L, HOW J. Consensus-based auction approaches for decentralized task assignment[C]//AIAA Guidance, Navigation and Control Conference and Exhibit. Reston, VA: AIAA, 2008: 6839.
[17] KIM D, LEE J. Joint mission assignment and location management for UAVs in mission-critical flying ad hoc networks[C]//2018 International Conference on Information and Communication Technology Convergence (ICTC). Piscataway, NJ: IEEE Press, 2018: 323-328.
[18] SHIMA T, RASMUSSEN S J, SPARKS A G, et al. Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers & Operations Research, 2006, 33(11): 3252-3269.
Click to display the text
[19] 谭何顺, 曹雷, 彭辉, 等. 一种多无人机层次化任务分配方法[J]. 解放军理工大学学报(自然科学版), 2014, 15(1): 18-24.
TAN H S, CAO L, PENG H. Method of multi-UAV hierarchical task allocation[J]. Journal of PLA University of Science and Technology:Natural Science, 2014, 15(1): 18-24. (in Chinese)
Cited By in Cnki (11) | Click to display the text
[20] 苏菲, 陈岩, 沈林成. 基于蚁群算法的无人机协同多任务分配[J]. 航空学报, 2008, 29(S1): 184-191.
SU F, CHEN Y, SHEN L C. UAV cooperative multi-task assignment based on ant colony algorithm[J]. Acta Aeronauticaet et Astronautica Sinica, 2008, 29(S1): 184-191. (in Chinese)
[21] 杨媛琦.基于负载均衡的Multi-UAV任务分配算法的研究[D].哈尔滨: 哈尔滨工业大学, 2016.
YANG Y Q. Research of multi-UAV load-balanced task planning algorithm[D]. Harbin: Harbin Institute of Technology, 2016(in Chinese).
Cited By in Cnki | Click to display the text
[22] 杜继永, 张凤鸣, 杨骥, 等. 多UCAV协同任务分配模型及粒子群算法求解[J]. 控制与决策, 2012, 27(11): 1751-1755.
DU J Y, ZHANG F M, YANG J, et al. Cooperative task assignment for multiple UCAV using particle swarm optimization[J]. Control and Decision, 2012, 27(11): 1751-1755. (in Chinese)
Cited By in Cnki (36) | Click to display the text
[23] 冉华明, 周锐, 董卓宁, 等. 空战中协同干扰、探测、攻击任务分配[J]. 北京航空航天大学学报, 2015, 41(5): 911-918.
RAN H M, ZHOU R, DONG Z N, et al. Cooperative jamming-detecting-attacking task allocation in air combat[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(5): 911-918. (in Chinese)
Cited By in Cnki (7) | Click to display the text
[24] 史恒亮.云计算任务调度研究[D].南京: 南京理工大学, 2012.
SHI H L. Research of job scheduling on cloud computing[D]. Nanjing: Nanjing University of Science and Technology, 2012(in Chinese).
[25] 邓见光.云计算任务调度策略研究[D].广州: 华南理工大学, 2014.
DENG J G. Research on task scheduling strategy of cloud computing[D]. Guangzhou: South China University of Technology, 2014(in Chinese).
Cited By in Cnki (1) | Click to display the text
[26] HORNIG R. An overview of the OMNeT++ simulation environment[C]//International Conference on Simulation TOOLS and Techniques for Communications, Networks and Systems & Workshops, 2008: 60.
http://dx.doi.org/10.7527/S1000-6893.2019.23183
中国航空学会和北京航空航天大学主办。
0

文章信息

王荣巍, 何锋, 周璇, 鲁俊, 李二帅
WANG Rongwei, HE Feng, ZHOU Xuan, LU Jun, LI Ershuai
面向无人机蜂群的航电云多层任务调度模型
Avionics cloud multi-layer task scheduling model for UAV swarm
航空学报, 2019, 40(11): 323183.
Acta Aeronautica et Astronautica Sinica, 2019, 40(11): 323183.
http://dx.doi.org/10.7527/S1000-6893.2019.23183

文章历史

收稿日期: 2019-05-24
退修日期: 2019-07-09
录用日期: 2019-08-22
网络出版时间: 2019-09-04 11:22

相关文章

工作空间