多无人机协同决策分布式栅格战术计算技术研究∗

杨利斌 谢瑞煜 杜亚杰

（海军航空大学 烟台 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 战术计算系统进行任务调度，具有良好的精确性和实时性。