综合优先级下相控阵火控雷达自适应调度算法

王岩松 韩 星 陈 春 鲁 金

(西安电子工程研究所 西安 710100)

0 引言

火控雷达在近程防空武器系统中占据重要地位,可通过对波束覆盖空域内目标进行搜索和跟踪,控制火力系统对来袭目标进行拦截。目前,火控雷达多采用相控阵体制,实现了搜索和跟踪时波束的自适应捷变,为任务执行带来了极大的灵活性。为充分发挥相控阵火控雷达(下文简称火控雷达)作战性能优势,提升其时间资源利用效率,更好地执行近程防空任务,必须进行合理可行的雷达资源调度[1]。

雷达任务调度主要包括两个方面:一是任务优先级规划;二是调度策略的选择。早期的优先级规划仅利用一种参数确定优先级,如截止期最早最优先算法(EDF)[2]和高工作方式优先级最优先算法(HPF)[3]。文献[4-6]综合考虑工作方式优先级和截止期两个因素,提出工作方式优先级加截止期算法(HPEDF)以及两种变形算法:修正EDF算法(MEDF)和修正HPF算法(MHPF)。文献[7]采用优先级表思想,将根据目标信息得出的目标威胁度与任务截止期相结合,共同进行任务综合优先级规划。文献[8-9]在规划优先级时突破两个参数的限制,采用多参数加权的方式进行优先级规划。常用雷达调度策略有固定模板法、多模板法、部分模板法和自适应调度法四种,其中自适应调度策略更能发挥相控阵火控雷达性能的综合优势。文献[10-11]给任务请求增加时间窗约束,使原本在时间上有冲突的雷达任务经调整后也可能被调度执行,在任务的调度效率和时间利用率上均有较大提升。文献[12-13]基于调度收益或调度代价构建雷达任务调度模型,并采用二次规划或者遗传算法等方法进行求解。为进一步提高雷达的时间利用率,文献[14-15]采用脉冲交错算法,其思想是在单个任务收发脉冲间隔中交错调度其它任务的发射或接收脉冲。然而上述算法存在以下缺陷:一是未考虑火控雷达对各个目标的射击有利度问题,无法确定雷达所跟踪目标是否处于火控雷达配属武器的有效攻击范围内;二是火控雷达属于精密跟踪系统,波束很窄,对雷达任务及时性要求很高,而上述调度策略对调度及时性的考虑较少。针对以上不足,本文在HPEDF调度算法基础上,综合考虑工作方式优先级、任务截止期和射击有利度三个参数共同进行任务优先级规划,同时基于任务及时性构建调度代价模型,并采用所提出的带有时间窗的一步回溯法与插空法相结合的自适应调度算法来进行模型求解。

1 射击有利度分析

射击有利度是指防空火力单元对空袭兵器实施射击的有利程度,它是战场防空指挥员进行射击指令下发的重要依据。火控雷达的重要任务之一就是控制高炮对目标进行拦截,因此分析待拦截目标射击有利度时,不仅要考察来袭目标自身因素,还要考察火控雷达所配属武器的性能因素。本文从目标和火力单元覆盖范围的角度考虑,探讨影响火控雷达(配属高炮为例)射击有利度的6个主要参数:目标类型、目标速度、目标高度、航路捷径、目标飞临时间和高炮攻击区。考虑到各参数对目标射击有利度的非线性影响,分别构建如下射击有利度函数。

1.1 目标类型(TP)的射击有利度

一般大型目标速度慢,飞行高度高,机动性差,被弹面积大,在射击范围内射击较有利。构建如式(1)的目标类型射击有利度函数,若目标不属于所分类型,则射击有利度置为0。

(1)

1.2 目标速度(V)的射击有利度

目标速度越快,射击越不利;速度越慢,射击越有利。构建如式(2)的目标飞行速度射击有利度函数为

(2)

其中Vmax为目标最大飞行速度。

1.3 目标高度(H)的射击有利度

目标高度过高或过低均会降低高炮火力射击效能,只有目标飞行在中间高度时射击最有利。构建如式(3)的目标高度射击有利度函数为

(3)

其中Hmax为目标飞行最大高度,Hmin为目标飞行最小高度。

1.4 航路捷径(TR)的射击有利度

火控雷达所配属高炮只能拦截最大航路捷径(TRmax)内的目标,一般在有效射击范围内,航路捷径越小,射击越有利;航路捷径越大,射击越不利;航路捷径为0时,射击最有利。构建如式(4)的航路捷径射击有利度函数。

(4)

1.5 目标飞临时间(TA)的射击有利度

目标飞临时间是指来袭目标飞临防空火力单元的时间。目标在防空火力单元的目标分配始线(T始)以外,射击有利度置为1,在目标分配终线(T终)以内,射击有利度置为0,介于二者之间,目标飞临时间越大,射击越有利。构建如式(5)的目标飞临时间射击有利度函数(只考虑目标接近情况,未考虑目标远离情况)为

(5)

其中,Tmax为目标在高炮攻击区的最大可能停留时间,Treact为高炮系统反应时间

1.6 高炮攻击区(GA)的射击有利度

要使高炮能够毁伤目标,目标必须处于高炮的攻击区内。采用图1和图2进行说明。

图1 高炮垂直攻击区

图2 高炮水平攻击区

图1中Rmax为高炮射击最大射程:Rmin为高炮射击最小射程;εmax为高炮攻击区的最大俯仰角;θmax为高炮攻击区的最大方位角。其中,DE和IJ为高炮攻击区远界,AB和HJLK为高炮攻击区近界,CD为高炮攻击区高界,AE为高炮攻击区低界,JK和HI为高炮攻击区的侧界。判断目标是否处于高炮攻击区内,只需要满足目标方位角、俯仰角和距离小于其对应的最大方位角、最大俯仰角和最大射程。高炮攻击区所覆盖的空域,防空高炮杀伤目标的概率高于一定的给定值。本文默认处于高炮攻击区外的目标射击有利度为0,处于高炮攻击区内的目标射击有利度根据其径向距离与Rmax大小关系依次等间隔取值。

本文采用层次分析法进行相应权值计算,得出影响火控雷达火力系统射击有利度的6个因素的权值大小,结合上文介绍的各个因素射击有利度函数,得出高炮对不同目标的射击有利度。

图3 射击有利度属性层次结构图

结合参考文献[16]给出的层次分析法决策步骤,首先分析各因素之间的关系,建立系统的递阶层次关系,如图3所示;其次对第二层各元素关于射击有利度的重要性进行两两比较,构造两两比较判断矩阵;最后由判断矩阵计算第二层各元素对于射击有利度的相对权重,求出各属性的加权向量为

Wi=(w1,w2,w3,w4,w5,w6)

(6)

其中wi为第i个影响属性的权重。

针对不同目标,影响射击有利度的各个因素按照1.2节进行量化,得到量化后向量为

Ui=(u1,u2,u3,u4,u5,u6)

(7)

其中ui为第i个影响属性对应的实际量化值。

第i个目标相对于高炮的射击有利度为

(8)

n个目标相对于高炮的射击有利度的加权结果可构成多目标射击有利度向量为

(9)

2 任务综合优先级规划

任务调度一般以调度间隔SI为周期,在调度间隔[t0,t0+SI]内共有N个任务驻留请求,各个雷达任务可以用若干个属性的集合进行表征。火控雷达任务模型的驻留请求形式化描述为

Ti={ti,pi,dti,sti,wi,sii,tmax,tmin}

(10)

其中,ti为任务期望执行时刻;pi为任务的工作方式优先级;dti为任务驻留时间;sti为任务实际执行时刻;wi为时间窗;sii为目标任务的射击有利度;tmax/tmin为低截止期/高截止期。若一个任务请求被成功调度,其实际执行时刻应该满足:

ti-wi≤sti≤ti+wi

(11)

其中tmin=ti-wi,tmax=ti+wi。

本文以工作方式优先级表征任务重要性,以截止期表征任务紧迫性,以射击有利度表征任务分配的必要性,结合三者共同作为综合优先级的构成因素,其中工作方式优先级和任务截止期可以从任务属性中直接提取,射击有利度使用上节所述方法进行计算。在综合优先级计算时,为解决不同参数的量纲与取值范围不同的问题,利用文献[15]提出的二维优先级表思想,采用两级二维优先级表级联的方式进行求解。本文设定三种因素的倾向性顺序由大到小为:射击有利度、工作方式优先级、任务截止期,综合优先级计算时首先将倾向性居中的工作方式优先级和倾向性最小的任务截止期在同一层面形成一级优先级,此处α1取1;再将倾向性最大的射击有利度和一级优先级在同一层面上形成综合优先级,此处α2取2,如图4所示。

图4 任务综合优先级计算框图

将任务驻留请求集合中所有任务驻留请求分别按照射击有利度降序、工作方式优先级降序和任务截止期升序排列,记任务Ti在三个序列中的位置分别为xi,yi,zi,其中射击有利度排序过程中搜索任务排在其他类型任务之后,搜索任务之间按照期望执行时间由前到后排列。按照优先级表计算规则,一级优先级函数为

PFIi=[α1(yi-1-β1)+2·zi-2]·(yi+β1)+yi

(12)

综合优先级函数为

Pi=[α2(xi-1-β2)+2·PFIi-2]·(xi+β2)+xi

(13)

图5 优先级表设计

在该动态优先级表的设计中,改变x,y,z在式(12)和式(13)中的相应位置以及权重α的取值,可以动态快速调整任务优先级顺序,充分发挥优先级表的动态自适应特性。

3 任务自适应调度算法实现

3.1 任务调度代价模型

本文综合优先级规划过程中体现了任务调度的重要性、紧迫性以及任务分配的必要性等原则。相控阵火控雷达属于精密跟踪系统,波束很窄,当任务实际执行时刻较期望执行时刻发生变化时,就有很大几率导致跟踪精度降低,进而降低雷达性能。同时,随着武器装备的更新换代,待拦截目标机动性和威胁性大大提升,也对任务调度及时性提出更高的要求。因此,本文从及时性原则出发,构建任务调度代价模型如式(14)、式(15)所示。

(14)

(15)

其中t0表示每个调度间隔起始时刻。

将任务工作方式优先级作为目标函数中的权值,表示对同一时间偏移量,工作方式优先级越高的任务需要付出的代价越大。式(15)中:C1表示被调度任务之间相互时间约束;C2表示被延迟任务的时间约束;C3表示被删除任务的时间约束;ηi表示任务的调度属性,其含义如式(16)所示。

(16)

f(ηi)是关于任务调度属性的函数,函数表达式为

(17)

综上可以看出,本文所构建的调度代价模型等价于在满足式(15)的约束下,使式(14)所表示的总调度代价最小,主要目的包括两个:一是保证高优先级任务被优先调度;二是对被调度任务选择最优的执行时间。

3.2 调度模型求解算法

针对3.1节所构建的任务调度代价模型,本文提出带有时间窗的一步回溯法与插空法相结合的自适应调度算法,并利用该算法进行模型求解。首先将本调度间隔的待调度任务按综合优先级进行排序,再分为两组。第一组调度任务数量为N,满足任务驻留时间之和DWN≤SI,DWN+1≥SI。该部分待调度任务采用带有时间窗的一步回溯法进行调度,即在调度当前时刻的任务时若该任务与已调度任务时间上发生重叠,则通过比较二者工作方式优先级,选择工作方式优先级低的任务在其时间窗范围内进行前后调整,在分析该任务与前后任务关系的基础上,选择最合适的位置对该任务进行调度。第二组为本间隔待调度任务中剩余任务,按照综合优先级大小依次采用插空法进行任务调度安排。结合两组确定调度任务,生成最终的调度执行链表。算法实现步骤如下Step1至Step20所示,其流程图如图6所示。

Step1:从任务请求链表和延迟链表中选出期望时间ti满足当前调度间隔的任务请求;

Step2:计算所有任务综合优先级并排序;

Step3:提取前N个任务,满足总驻留时间之和DWN≤SI,DWN+1≥SI;

Step4:将雷达任务按照期望执行时间从小到大排序,得到调度序列S;

Step5:将S中的第一个任务放到临时序列Z中,并且令j=1,i=2;

Step6:判断S(i)的结束时间是否大于当前调度间隔结束的时间,如果否,转Step7;是,转Step8;

Step7:判断S(i)的期望执行时间是否大于Z(j)结束时间,如果否,计算S(i)与Z(j)的重叠时间t并转至Step9;否则转Step16;

Step8:判断S(i)是否满足延迟条件,如果否,将该任务加入删除链表转Step17;否则转入延迟队列;

Step9:判断S(i)的优先级是否大于Z(j),如果是,转Step10;否,转Step12;

Step10:判断t是否在Z(j)的时间窗内,如果是,转Step11;否,转Step12;

图6 任务调度流程图

Step11:判断Z(j)的实际执行时刻与Z(j-1)的完成时刻之间空闲时间是否≥t,如果是,将Z(j)的实际执行时刻提前t并转至Step16;否则,转至Step12;

Step12:判断t是否在S(i)的时间窗内,如果是,转至Step13;否则加入删除队列并转至Step17;

Step13:判断S(i)的完成时刻与S(i+1)的期望执行时刻之间空闲时间是否≥t,如果是,转至Step14;否则转至Step15;

Step14:将S(i)的实际执行时刻推迟t并转至Step16;

Step15:判断S(i)的优先级是否>S(i+1)的优先级,如果是,转至Step14;否则加入删除队列并转至Step17;

Step16:令Z(j+1)=S(i),转Step17;

Step17:判断i是否=N,如果是,输出Z序列并转至Step18;否则令i=i+1,j=j+1并转至Step6;

Step18:判断本调度间隔是否还有空闲时间,如果是,转至Step19;否则Step20;

Step19:按照任务优先级从第N+1个任务开始,结合其时间窗依次进行插空并遍历剩余所有任务,转至Step20;

Step20:结束并更新Z序列。

4 仿真实现与分析

4.1 性能评估指标

为评判调度算法性能优劣,给出以下指标:

1) 调度成功率(SSR):即成功调度执行的任务数与所有任务请求的总数之比,如式(18)所示。

(18)

其中,Ne为成功调度的任务数;N为请求调度的任务总数。

2) 由于任务分配的必要性是随着射击有利程度而变化的,并不依赖人为划分,因此本文提出射击价值率(SVR)指标,用以评估调度算法对射击有利度高的任务的调度性能。射击价值率即为成功调度的任务所具有的射击有利度总和与请求调度的任务射击有利度总和之比,如式(19)所示。

(19)

其中,sii为第i个任务的射击有利度,式(19)说明优先对具有高射击有利度目标属性的任务进行调度,射击价值率越高,算法的性能越优。

3)平均时间偏移率(ATSR):即各成功调度任务的实际执行时刻和期望执行时刻差的绝对值与时间窗之比的平均值,可以体现任务调度的及时性,如式(20)所示。

(20)

4.2 参数设置

设定火控雷达调度间隔50ms,仿真时长150ms,共五种任务类型:搜索任务、普通跟踪任务(本文简称普跟)、精密跟踪任务(本文简称精跟)、火控任务、确认任务。不同工作方式任务的请求参数如表1所示,确认、火控、精跟、普跟目标的数目之比为2∶3∶3∶2,搜索任务设置为常驻任务,根据编排好的波位表顺序执行,为方便说明,仿真中设定搜索任务数量与当前目标数量相等。因为当任务数量过少而不存在任务重叠时不需要进行任务调度,故本文仿真主要研究点在任务过饱和状态下的任务调度。本文以目标总数来代表不同的雷达负载情况,目标数设为70,80,…,160批,每增加10批目标,进行100次蒙特卡洛仿真取平均值。每个雷达任务的期望执行时间在0～150ms内随机均匀产生,不同目标射击有利度计算所需的先验信息由火控雷达和所配属高炮提供,其中搜索任务因不具有目标先验信息,故默认其射击有利度为0。在采用两级二维优先级表级联的方式进行任务综合优先级规划时,设定影响综合优先级三个参数的倾向性顺序由大到小为:射击有利度、工作方式优先级、任务截止期,其中α1取1,α2取2。

表1 任务请求参数表

4.3 仿真结果分析

为直观对比不同调度算法的调度优劣情况,设置确认任务20个,火控任务30个,精跟任务30个,普跟任务20个,搜索任务100个,三种不同调度算法下的自适应调度结果如图7所示,包括调度前的任务请求序列以及调度后的任务执行序列。图7中条形框表示各雷达任务,其宽度表示各任务的驻留时间,高度表示各任务的工作方式优先级。

图7 任务请求调度时序图

图7(a)为未经调度的雷达任务原始请求序列图,存在较多的任务重叠,即多个任务抢占同一时间段。图7(b)、图7(c)、图7(d)为经过三种不同的自适应算法调度后的时序图,均使发生冲突的雷达任务实际执行时刻相对其期望执行时刻提前或者滞后,最大限度地调度更多任务。下面结合已有的MEDF算法和HPEDF算法对本文所提出的自适应调度算法性能进行分析比较。

图8为3种算法的调度成功率对比。随着目标批数的增多,3种算法的调度成功率均处于下降状态。本文算法调度成功率略低于MEDF算法,高于HPEDF算法,这是由于MEDF算法综合优先级规划时只考虑任务截止期这一单因素,可能会调度更多的搜索任务,而搜索任务本文中设定的驻留时间远短于其他类型任务,故MEDF算法可以成功调度更多任务,在3种算法中调度成功率最高。在目标数目为100批时,本文算法调度成功率相对于HPEDF算法提升了10%,且接近于MEDF算法。

图8 调度成功率对比

图9为3种算法的平均时间偏移率对比。随着目标批数的增多,3种算法的平均时间偏移率均整体处于上升状态,MEDF算法的时间偏移率最高,HPEDF算法的时间偏移率次之,本文算法时间偏移率最低,这是由于MEDF算法和HPEDF算法都没有考虑到雷达任务的及时性要求。结合图7也可看出,虽然MEDF算法有着最高的调度成功率,但是是以较大的时间偏移量为代价的。本文算法注重任务及时性要求,在尽可能调度更多更高优先级任务的基础上,保证任务贴近其期望执行时刻被调度。在目标批数为100批时,本文算法的时间偏移率分别为MEDF算法的12%、HPEDF算法的20%。

图9 平均时间偏移率对比

图10为3种算法的射击价值率对比。随着目标批数的增多,3种算法的射击价值率均整体处于下降状态,本文算法的射击价值率最高,MEDF算法和HPEDF算法射击价值率次之。这是由于MEDF算法和HPEDF算法均未考虑到射击有利度因素对任务调度的影响,而本文算法在进行任务优先级规划时着重考虑了火控雷达所配属高炮对目标的射击有利度问题,在火控雷达任务调度时,确保优先调度射击有利度更高的任务,进而更合理利用火控雷达资源。在目标批数为110批时,本文算法的射击价值率相对于MEDF算法、HPEDF算法分别提高11%和12%。

图10 射击价值率对比

图11为3种算法的调度代价对比。随着目标批数的增多,MEDF算法和HPEDF算法的调度代价均处于上升状态,本文算法的调度代价基本保持稳定,且MEDF算法调度代价最大,HPEDF算法调度代价次之,本文算法调度代价最小。结合图9所示的3种算法平均时间偏移率对比进行分析,这是由于本文中的调度代价不仅与成功调度任务的工作方式优先级有关,还受到调度及时性的动态影响。MEDF算法二者均未考虑,因而调度代价最高;HPEDF算法仅考虑任务的工作方式优先级,因而调度代价低于MEDF算法;本文算法对二者的影响均进行考虑,因而本文算法的调度代价最低且保持稳定。在目标批数为160批时,本文算法的调度代价分别为MEDF算法的28%、HPEDF算法的35%。

图11 调度代价对比

以上仿真结果表明:本文算法相比于MEDF算法和HPEDF算法,能够更好地满足火控雷达任务调度的及时性以及任务分配的必要性;此外,本文算法的调度代价较小,且对高工作方式优先级任务的调度效果较为显著,整体上更切合于火控雷达的工作要求。

5 结束语

针对相控阵火控雷达多任务调度时的资源分配问题,本文提出一种综合优先级下基于调度代价的任务调度算法,所作主要贡献和结论如下:

1)充分利用目标先验信息,结合相控阵火控雷达需与高炮配合对待拦截目标进行火力打击的特性,构建射击有利度模型。

2) 综合考虑火控雷达对不同目标的射击有利度、不同任务工作方式优先级和截止期三个因素,通过设计两级二维优先级表,赋予任务动态优先级。

3) 构建了任务调度代价模型,提出了带有时间窗的一步回溯法与插空法相结合的自适应调度算法,并使用该算法进行模型求解,提高了任务调度的及时性,更满足相控阵火控雷达工作要求。

4) 对实现价值率指标进行改进,提出射击价值率这一性能评估指标,以显示调度算法对更有射击价值任务的调度情况。

5)仿真结果表明,本文所提出的自适应调度算法切实可行,能够提升射击价值率,降低平均时间偏移率和调度代价。

6)本文所提调度算法仅从时间利用的角度进行设计,未考虑计算机资源和能量资源受限条件下的任务调度工作;此外本文在计算火控雷达射击有利度时只考虑了6个因素,后续可以根据不同作战需求增加补充。