中国指挥与控制学会会刊 
随着战场电磁环境的日益复杂,多功能相控阵雷达技术得到了大力的发展。多功能相控阵雷达可以通过孔径分割技术将一个大的阵面分割成多个子阵,每个子阵接一个接收通道,形成多个独立收发的波束,实现同时跟踪多个目标、搜索多个空域,甚至是同时完成雷达、电子战和通信等多种任务,大大提高了平台的作战效能[1,2]。
考虑到多功能相控阵雷达具备多个子阵,可以通过子阵级的孔径动态重构方法来实现多任务并行调度,因此,如何同时对时间和孔径资源进行联合管理,优化多任务并行调度过程成为一个重要的研究方向。
目前,已有大量学者对多功能雷达的任务调度方法展开了深入研究,但大部分文章都是针对单一孔径的任务调度技术开展研究[3,4,5,6,7,8,9,10],少部分文章针对基于孔径分割技术的多功能雷达开展任务调度研究。文献[11,12]从孔径资源占用百分比的角度出发,分别提出了基于多任务并行EDF算法和基于最小时间窗的方法来实现系统的自适应调度。文献[13,14,15]在文献[11,12]考虑孔径资源占用百分比的基础上进一步考虑了一维孔径位置问题进行了任务调度算法的设计。文献[13]提出了雷达通信一体化系统动态孔径分割条件下的孔径、时间二维资源管理问题,并根据FIFO原则提出适合该问题的任务调度算法;文献[14]提出了一种基于孔径分割的4子阵雷达自适应任务调度方法;文献[15]针对雷达搜索、跟踪与成像任务的自适应调度问题,提出了一种基于时间-孔径二维资源管理的雷达资源调度算法。
本文在上述一维孔径资源和一维时间资源(共二维)联合优化的基础上,进一步考虑了二维孔径资源问题,针对子阵级多功能相控阵雷达展开基于子阵级孔径动态重构的多任务并行调度技术的研究,分别提出了基于混合多任务并行EDF(Earliest Deadline First)算法和混合遗传算法的二维孔径资源和时间资源(共三维)联合优化管理的方法,并通过仿真验证了算法的有效性。
1 基于启发式算法的二维孔径动态重构方法
1.1 阵列模型
考虑如图1 所示的矩形阵面,该矩形阵面一共划分成Ny×Nx个子阵,方位维有Nx个子阵,俯仰维有Ny个子阵,每个子阵接一个发射/接收通道,最多可以形成Ny×Nx个独立的收发波束。该阵列可以通过子阵级孔径重构实现多任务并行调度,最多可同时完成Ny×Nx个雷达任务。
1.2 雷达任务模型
建立如下雷达任务模型:
Task,i={ts,i,texp,i,te,i,tr,i,nmin,i,nx,i,ny,i,pi}
式中,Task,i为第i个雷达任务,ts,i 为任务i的可最早执行时刻,texp,i 为任务i的期望执行时刻,te,i 为任务i的最晚可执行时刻,tr,i 为任务i的实际执行时刻,nmin,i 为任务i最少所需子阵个数,本文采用子阵个数nmin,i 来表征任务i的最小所需孔径面积,nx,i 为任务i在方位维占用的子阵个数,ny,i 为任务i在俯仰维占用的子阵个数,pi为任务i的优先级。
1.3 二维孔径动态重构算法步骤
在实际作战过程中,为了满足基本的雷达任务需求,二维孔径动态重构的基本算法步骤如下(假设当前雷达任务集合为Task={Task,1,Task,2,···,Task,i,···,Task,N},N为当前雷达任务的总数):
步骤1:根据具体雷达任务的作用距离来计算当前雷达任务集合Task 中各任务最小所需孔径面积nmin,i [12];
步骤2:根据具体雷达任务对天线方向图的要求计算当前雷达任务集合Task 中各任务所需的孔径形状,考虑上述阵列模型,本文设计的孔径形状只可能是矩形,本文分别采用方位维子阵个数nx,i 和俯仰维子阵个数ny,i 来表征i个雷达按任务的孔径形状,通过孔径形状规划后,实际所需的孔径面积nx,i×ny,i 可能会大于上述最小所需孔径面积nmin,i;
步骤3:为了能够提高孔径的利用率,同一个雷达工作帧尽可能多的执行任务,且执行任务中需包含优先级最高的任务,需要对不同任务的孔径位置进行合理排布。
考虑到孔径面积分配和形状规划采用现有常规方法均可解决,因此,本文重点对雷达任务的孔径位置规划方法进行研究。孔径位置规划问题类似于著名的二维装箱问题,本文借鉴二维装箱问题的解决思路[12],提出了一种基于启发式算法的孔径位置规划方法,具体算法步骤如下:
步骤1:将当前雷达任务集合Task 中所有的任务按照ny,i 值从高到低进行排序,对于ny,i 值相同的根据任务优先级高低排序,形成雷达任务序列1: ={ , ,···, ,···, };
步骤2:将任务 所对应的矩形孔径放到阵面的最下角,并形成第一条参考线,将未填阵面分为两个子空间,如图2 a)所示,图中灰色部分即为任务 对应的孔径位置;
步骤3:在参考线下找到未填阵面,按照 中任务的顺序将任务依次进行装填,每次从未填阵面的最低点开始装填,最低点如果无法装填,再选择次低点,一直重复,直到该任务装填成功,或者无法装填此任务,则当次装填结束,继续下一个任务,如图2 b)所示,当前最低点即图中的A点;
步骤4:当未填阵面不能装下任何雷达任务所需孔径时,则在参考线之上的未填阵面高度允许的条件之下放入 集合中还未放入的ny,i值最高的探测任务,将该雷达任务所对应的孔径作为新的参考矩形,得到新的参考线,以前的参考线作废,如图2 c)所示;
步骤5:重复步骤2和步骤3,直到集合 中所有任务装填完成或者无法再进行任务装填时,结束集合 中任务的孔径位置规划,得到最终的孔径位置规划结果 ;
步骤6:将当前雷达任务集合Task 中所有的任务按照优先级从高到低进行排序,形成雷达任务序列2: ={ , ,···, ,···, };
步骤7:将 所对应的矩形孔径放到阵面的最下角,参考线直接设置在阵面的最高处;
步骤8:在参考线下找到未填阵面,按照集合 的顺序将任务依次进行装填,每次选择最低点进行装填;
步骤9:当不能装下任何雷达任务所需孔径时,结束集合 中任务的孔径位置规划,得到最终的孔径规划结果 ;
步骤10:判断 中是否包含集合Task 中优先级最高的任务,如果是,将 和 中得到调度的任务进行价值总和计算,选择任务价值较高的方案;如果否,选择 作为最终方案。
2 时间资源和二维孔径资源联合管理方法
2.1 混合MTPEDF算法
考虑到传统的多任务并行EDF(MTPEDF)算法[7]只能实现带有孔径占用资源百分比的多任务并行调度,无法实现二维孔径重构功能,因此,本文在此基础上提出了混合MTPEDF算法。
2.2 混合遗传算法
2.2.1 多任务并行调度模型建立
二维孔径和时间联合管理问题本质上属于一类带约束条件的优化问题。对于第k个调度间隔和任务集Task={Task,1,Task,2,···,Task,i,···,Task,N},联合管理的目标是在满足约束集的前提下,确定可执行的任务集 (k)={ , ,···, ,···, }、任务执行顺序Θ(k)以及各任务所对应的孔径规划结果Α(k),其中,Ns是在该调度间隔内可以得到调度的任务个数。
在以上定义的基础上,建立如下所示的多任务并行调度模型:
其中,η为任务调度成功率,L为惩罚函数,NT为期望在该调度间隔内得到调度的总的任务数量,NZ为调度间隔内总的帧数,Hi为任务i的调度情况,Hi=1说明该任务调度成功,Hi=0说明该任务调度失败,li为任务i的惩罚值,nmax 为总的子阵个数。
任务i的惩罚值li与任务调度的时间偏移量相关,当实际执行时刻过早,会导致时间资源的浪费,反之,当实际执行时刻过晚时会影响任务的完成质量,因此,任务i的实际执行时刻 与期望执行时刻 总是越接近越好,惩罚值的计算公式如下[17]:
li=
其中,αi为提前执行的惩罚系数,βi为滞后执行的惩罚系数。
2.2.2 混合遗传算法设计
如式(2)所示的优化模型仅仅解决了带孔径资源占用百分比约束的多任务并行调度问题,没有考虑到二维孔径位置规划问题,为了将二维孔径和时间进行联合管理,在求解如式(2)所示的优化模型的过程中加入孔径位置规划,并采用混合遗传算法进行求解。
混合遗传算法是将传统的遗传算法与启发式算法相结合,用于求解带二维孔径位置约束的多任务并行调度问题。
1)编码方式设计
混合遗传算法采用矩阵编码的方式进行编码,编码方式如下所示:
X=
其中,NT为雷达在该调度间隔内需要执行的总任务数量;NZ为调度间隔内总的帧数;xij取0或1,i表示第i个任务,j表示调度间隔内的第j帧,xij=1说明任务i在第j帧得到调度,反之,xij=0则表示没有得到调度。
2)适应度函数设计
适应度函数基于式(2)中的优化目标进行设计,并采用加权的方式设计如下适应度函数:
f=-η+L/5+2
3)约束条件处理
针对多约束问题,采用个体变异的方式来解决;此处所说的变异与遗传算法中为了丰富群体多样性所做的变异不同,这里的变异是为了将不满足约束条件的个体按照一定的规则变异成可以满足约束条件的个体。
混合遗传算法在进行约束条件处理过程中个体资源约束检查与变异阶段加入基于启发式算法的孔径重构方法,对遗传算法中的个体进行变异。
混合遗传算法中个体资源约束检查与变异具体步骤如下:
步骤1:令j=1;
步骤2:假设占用该帧,即在该帧xij=1的任务集合为Task,j={Task,1,···,Task,m,···, },Mj为任务集合Task,j中任务的总数量,将任务集合Task,j中的任务分成两类,Ⅰ类:后一帧惩罚函数值变大的任务,即li,j+1>li,j,Ⅱ类:后一帧惩罚函数值变小的任务,即li,j+1≤li,j;
步骤3:分别将Ⅰ类任务集合和Ⅱ类任务集合按照惩罚函数值从高到低进行排序,得到任务序列SI和SII;
步骤4:按照Ⅰ类任务优先级高于Ⅱ类任务优先级的原则合并两个任务序列,得到新的任务序列Sall={SI,SII};
步骤5:令xij=0,i=1,2···,NT;
步骤6:按照新的任务序列Sall采用1.3节中孔径规划方法的步骤7~步骤9对不同任务的孔径位置进行规划,得到满足资源约束条件的孔径规划结果和可以得到调度的任务,并将可以得到调度的任务对应的xij逐一置1;
步骤7:令j=j+1,如果j>NZ,结束;否则,返回步骤2。
3 仿真分析
3.1 二维孔径动态重构方法仿真验证
仿真场景设置如下:假设阵列模型中Nx=8,Ny=4;一共有6个雷达跟踪任务,各任务的参数如表1 所示;该节只对单帧孔径位置规划进行仿真。
表1 各任务参数 |
| 任务编号 | 所需子阵个数 | |
|---|---|---|
| 方位维 | 俯仰维 | |
| 1 | 3 | 2 |
| 2 | 3 | 3 |
| 3 | 4 | 3 |
| 4 | 5 | 3 |
| 5 | 3 | 2 |
| 6 | 3 | 2 |
1)针对任务优先级排序为6,4,2,1,5,3的情况,二维孔径位置规划过程如下:
①步骤1:形成雷达任务序列1: ={T4,T2,T3,T6,T1,T5};
②步骤2:将任务T4 所对应的矩形孔径放到阵面的最下角,并形成第一条参考线,将未填阵面分为两个子空间,如图3 a)所示;
③步骤3:在参考线下找到未填阵面,按照 中的顺序对任务T2 进行装填,如图3 b)所示,此时当前参考线下的阵面已完全填满;
④步骤4:由于在参考线之上的未填阵面高度允许的条件之下没有任务可进行装填,此次孔径位置规划结束,形成孔径位置规划结果 ={T4,T2},如图3 b)所示;
步骤5:形成雷达任务序列2: ={T6,T4,T2,T1,T5,T3};
步骤6:将T6 所对应的矩形孔径放到阵面的最下角,参考线直接设置在阵面的最高处,如图3 c)所示;
步骤7:在参考线下找到未填阵面,按照集合 的顺序将任务依次进行装填,每次选择最低点进行装填,如图3 d)和图3 e)所示,得到孔径规划结果 ={T6,T4,T1},如图3 e)所示;
步骤8:由于 中不包含集合Task 中优先级最高的任务T6,因此,选择 为最终方案,如图3 e)所示。
2)针对任务优先级排序为3,1,4,6,2,5的情况,二维孔径位置规划过程如下:
①形成雷达任务序列1: ={T3,T4,T2,T1,T6,T5},按照1.3节中的步骤2~步骤5生成当前任务序列下的孔径位置规划结果 ,如图4 a)所示;
②形成雷达任务序列2: ={T3,T1,T4,T6,T2,T5},按照1.3节中的步骤7~步骤9生成当前任务序列下的孔径位置规划结果 ,如图4 b)所示;
③由于 中包含优先级最高的任务T3,因此,
将方案 和方案 进行任务价值总和对比,由于 的任务总价值高于 ,因此,选择 的结果为最终方案,如图4 b)所示。
从上述仿真结果可以看出,基于启发式算法的二维孔径重构方法可以实现孔径位置的合理排布,且保证优先级最高的任务得到调度的情况下尽可能多地调度任务,提高孔径利用率。
3.2 二维孔径和时间联合管理方法仿真验证
为了对两种算法进行对比分析,本文依据公式(2)引入任务执行时间偏移惩罚值和任务调度成功率两个指标。
1)任务执行时间偏移惩罚值对比分析
仿真场景设置如下:假设雷达每个调度间隔内有5帧,一共20个调度间隔,共100帧。在该场景中一共设置15个目标,在每一次的仿真过程中,目标的初始发现时间随机产生,任务的孔径形状规划结果是在限定范围内随机产生,任务期望的平均回访间隔由数据率控制算法进行计算。任务(此处均为跟踪任务)的初始出现时间和期望的平均回访间隔如表2 所示。
表2 目标参数表 |
| 目标编号 | 初始发现时间/s | 期望的平均回访间隔/s |
|---|---|---|
| 1 | 0.042 | 0.33 |
| 2 | 0.639 | 0.32 |
| 3 | 0.503 | 0.31 |
| 4 | 0.839 | 0.39 |
| 5 | 0.343 | 0.47 |
| 6 | 1.768 | 0.83 |
| 7 | 0.682 | 0.62 |
| 8 | 0.410 | 0.80 |
| 9 | 1.590 | 0.74 |
| 10 | 0.048 | 0.67 |
| 11 | 0.079 | 2.28 |
| 12 | 1.059 | 2.28 |
| 13 | 1.866 | 2.28 |
| 14 | 1.204 | 2.28 |
| 15 | 1.202 | 2.28 |
仿真结果如表3 所示,从仿真结果可以看出,在该仿真条件下雷达的资源充裕,所有任务均可得到有效调度,通过表中数据计算可知:①混合遗传算法的任务执行时间偏移惩罚值为0.65,混合MTPEDF算法为0.89,由此可知,混合遗传算法任务调度时刻更接近期望值;②混合遗传算法用于跟踪的资源比率比期望设计的值多了1.8%,相差不多,然而,混合MTPEDF算法的跟踪资源占用率却比期望的值多了17.8%,这样就会大大压缩系统用于其他任务的资源,由上述分析可知,混合遗传算法要优于混合MTPEDF算法。
表3 两种算法平均回访间隔对比表 |
| 目标 编号 | 平均回访间隔/s | ||
|---|---|---|---|
| 期望 | 混合遗传算法 | 混合MTPEDF算法 | |
| 1 | 0.33 | 0.32 | 0.27 |
| 2 | 0.32 | 0.31 | 0.27 |
| 3 | 0.31 | 0.31 | 0.26 |
| 4 | 0.39 | 0.38 | 0.27 |
| 5 | 0.47 | 0.46 | 0.38 |
| 6 | 0.83 | 0.82 | 0.73 |
| 7 | 0.62 | 0.60 | 0.50 |
| 8 | 0.80 | 0.84 | 0.76 |
| 9 | 0.74 | 0.76 | 0.74 |
| 10 | 0.67 | 0.67 | 0.76 |
| 11 | 2.28 | 2.23 | 2.21 |
| 12 | 2.28 | 2.26 | 2.24 |
| 13 | 2.28 | 2.23 | 2.08 |
| 14 | 2.28 | 2.38 | 2.35 |
| 15 | 2.28 | 2.38 | 2.40 |
2)任务调度成功率对比分析
仿真场景设置如下:假设雷达每个调度间隔内有5帧,一共50个调度间隔,共250帧,在该仿真中,目标的初始发现时间、任务的孔径规划结果、任务期望的平均回访间隔设成定值,任务数量依次由1增长到50,一共进行50组仿真。
仿真结果如图5 所示,从图中可以看出在任务数量较少时,两种算法都可以保证100%的任务调度成功率,但随着任务数量的增多,两种算法都发生了任务丢失的情况,但混合遗传算法的任务调度成功率总体上要比混合MTPEDF算法高。这是由于混合遗传算法的优化能力更强,任务调度实际调度时刻更接近期望调度时刻,对资源的分配更加合理;从上文任务执行时间偏移惩罚值对比分析可知,混合MTPEDF算法的调度时刻偏差较多,浪费了较多的时间资源,因此,随着任务负载的增加,任务调度成功率比混合遗传算法要低。
4 结束语
本文主要对基于孔径动态重构的多功能雷达任务调度方法进行研究:
1)针对二维孔径资源提出了一种启发式的孔径位置规划方法,并对该方法进行仿真验证,仿真结果表明该方法可以实现孔径位置的合理排布,且保证优先级最高的任务得到调度的情况下尽可能多地调度任务,提高孔径利用率;
2)针对时间资源和二维孔径资源联合管理问题,分别提出了混合MTPEDF算法和混合遗传算法,并对这两种方法进行仿真对比分析,仿真结果表明,对于任务执行时间偏移惩罚值和任务调度成功率这两个指标来说,混合遗传算法均优于混合MTPEDF算法。