基于拍卖算法的相控阵雷达任务调度方法

李 波, 周静杨, 高晓光

(西北工业大学电子信息学院, 陕西 西安 710129)

0 引 言

相控阵雷达(phased array radar,PAR)是一种通过改变雷达波相位从而改变波束方向的雷达,其利用陈列天线实现波束在空间的电扫描。与传统的机械扫描雷达相比,PAR扫描速度与扫描范围更大,波束位置、波束照射时间、次数等均更为灵活多变,其抗干扰性能和环境适应能力也更为优秀[1]。因此,PAR能够实现搜索、多目标跟踪、制导等多项任务同时进行,为了更加有效合理地分配雷达资源,达到雷达的最大工作效能,需要设计雷达的任务调度方法。

相比于模板法、部分模板法等常见的PAR调度方法,自适应调度策略是最为有效且复杂的调度方法[2]。文献[3-6]在经典的最小截止期优先(earliest deadline first,EDF)算法上提出了修正的EDF模型,并在其基础上提出了PAR实时驻留的自适应调度算法。文献[7-8]利用“时间窗”增加了任务调度的时间灵活性。文献[9]提出了驻留时间可变调度算法,进一步提高了任务调度能力。文献[10]针对调度过程中因采样周期不同在时间上产生冲突的问题,提出了基于周期分区的时间调度算法。文献[11-12]提出了脉冲交错算法,进一步提高了对时间资源的利用率。文献[13-15]提出了基于遗传算法(genetic algorithm,GA)的自适应调度方案,在分析雷达约束条件的基础上,设计相应的编码方式和遗传操作。

EDF算法虽然提高了时间利用率,但是不能保障高优先级的任务调度成功率;GA虽然能够提供较好的解决方案,但迭代次数较多,实时性能较差。拍卖算法(auction algorithm,AA)也能解决此类非确定多项式问题(non-deterministic polynomial, NP),并能达到更好的实时性要求,例如文献[16-17]提出利用AA来解决任务分配问题,文献[18]提出在AA相比于GA更适用于解决时间约束条件下的目标分配问题。本文提出基于AA的PAR自适应调度方案,将任务执行时间与期望执行时间的标准差作为竞拍者的竞标期望值,最大剩余连续时间和任务优先级作为拍卖条件,以时间作为竞拍物品,求能够使拍卖者和竞拍者的社会福利最大的分配方案。仿真结果表明本文算法在具有良好的任务调度成功率和时间偏移率的前提下,可以根据实际事态需求调整加权系数来提高时间利用率或高优先级的任务调度成功率。

1 任务模型及优先级设计

1.1 任务模型

在调度间隔长度为L的时间内,有N个雷达波束驻留任务,其中单个驻留任务为

mj={Pji,tje,tjl,tjw,tjp,mjs,(Rj,αj,βj)}

(1)

式中,Pji表示任务工作优先级;由时间窗的概念可知任务有最早执行时间tje和最晚执行时间tjl。即在时间[tje,tjl]内还未被执行,则该任务被终止;tjw表示期望执行时间;tjr表示实际执行时间;tjp表示任务驻留时间;mjs为更新率即任务自动生成周期；(Rj,αj,βj)为期望波束位置。

1.2 任务优先级

基于固定优先级的调度算法是一种常见的PAR自适应调度算法,其固定优先级如表1所示。在这种固定优先级算法中,相同工作方式的调度顺序只取决于时间窗和期望执行时间。不同的工作方式优先级不同,但对于多功能PAR,工作方式不能作为确定任务优先级的唯一指标,因为相同的雷达工作方式下的不同任务也会有着不同的重要程度[19-20]。不同的跟踪任务,其目标的类型、方位、速度、加速度,都对目标威胁程度的评判有着重要影响。同时,目标的航迹质量可以用来评判目标的优先级,航迹质量越好,目标跟踪状态越好,目标优先级则可以相应地降低。

表1 雷达主要任务表

本文在优先级表的基础上,加入目标的方位、速度、加速度及航迹质量这些要素设计一种综合优先级。具体方法是通过将以上4个要素量化并加权,将跟踪任务优先级细化,同时为了保证细化后的优先级不能越级超出其本身优先级,对其加权系数进行约束，即

(2)

式中，D0=D/Dmax,D为该追踪任务的目标距离;Dmax为任务中所有目标中的距离最大值;同理,将该任务的目标速度V0、加速度a0、航迹质量Y0与所有任务中该项的最大值做比,以进行归一化处理。δ1、δ2、δ3、δ4为不小于0的常数。n为该任务在优先级表(即表1)中的优先级。

2 调度算法

PAR任务调度策略主要解决在一个调度间隔内如何分配有限的时间资源,使得PAR能够合理地、优化地满足处于饱和状态下的任务调度请求[21-25]。从这点考虑,可以将PAR资源调度问题作为时间的分配问题来求解。近来AA在资源分配问题上被广泛应用,本文采用AA对任务PAR时间资源进行分配。

2.1 算法基本思想

进行雷达任务调度时,有以下3个原则:①根据优先级原则,当多个任务竞争同一时间槽时,优先级高的优先安排。②为了充分利用时间应尽量为后续任务留出最大连续空闲时间段,避免分割时间[25]。③为了使雷达的跟踪精度达到最优化,根据期望时间原则,雷达系统给某任务安排的真实执行时间应尽量逼近该任务申请的期望执行时间。

雷达任务的真实执行时间应尽量逼近此雷达任务申请时的期望执行时间,这有利于跟踪雷达精度的最优化。AA由拍卖者和竞拍者构成拍卖机构,拍卖者提供拍卖物品由竞拍者竞价,竞拍者根据自身情况决定加价或退出本轮拍卖,拍卖者不断更新竞拍者给出的最高价,直到参加拍卖的竞拍者只剩一位,最高价不变拍卖停止。根据贪婪原则,拍卖者对物品进行拍卖时会追求利润最大化,即只追求物品拍卖后所得的最高价值。竞拍者根据自身信息对物品进行估价,不盲目竞价,同时也不轻易放弃竞价。综合上述AA的特性,结合雷达任务调度的3个原则。算法以时间作为拍卖物品,以待调度雷达任务为竞拍者。将原则①和原则②作为拍卖条件,建立竞拍价值函数。竞拍者的优先级越高,拍卖后剩余的连续时间越长,拍卖者获得的利润越高。将原则③作为竞拍者的竞标期望,建立竞标期望函数,雷达调度任务竞拍到的时间越是逼近其期望执行时间,雷达调度任务的获利越高。

2.2 调度算法设计

设在某一调度间隔为T=[t0,t1]的时间段内,有未调度任务集合M={m1,m2,m3…mn},其中调度间隔T为拍卖者,拍卖[t0,t1]上的时间。

未调度任务集合M内的调度任务为竞拍者。

下面给出本调度算法中的两个定义。

定义1在时间段T上,已经被调度任务竞拍得到并占用的时间段为占用段,竞拍并得到其时间段的调度任务为已定任务nj。时间段T上的占用段集为Td。

定义2在时间段T上,由属于调度任务mj时间窗内的任一时间点ti,作为调度任务mj的实际执行时间,能够使任务mj执行完毕,即[ti,ti+tjp]上的所有点均在时间段T上且均不属于占用段集Td,则称ti为任务mj在时间段T上的饱和点,否则称ti为任务mj在时间段T上的缺失点。任务mj在时间段T上的所有饱和点,称为任务mj在时间段T上的饱和集Bj。任务mj在时间段T上的所有缺失点,称为任务mj在时间段T上的缺失集Qj。

2.2.1 确定竞拍价值函数

为了评估各调度任务给出的竞拍价,在上述PAR调度原则①和原则②的基础上,建立在某一调度间隔内单个雷达任务的竞拍价值量(auction value),用Vj表示为

Vj=fj(pj,Δtj)

(3)

式中,f(·)为价值量函数;pj表示参与竞拍的调度任务mj的任务优先级;Δtj为最大连续剩余时间,即调度任务mj竞拍到时间段T上的时间后,将原时间段分割成两个时间段中较大的那个时间段。

Δtj的求法:设在调度任务mj竞拍到时间段T上的时间后其任务执行时间为ti,则有

(4)

若在时间段T上,ti的前后均存在占用段,则占用段上的任务分别记为nT-1和nT+1,如图1所示。

图1 最长连续时间示意图Fig.1 Diagram of the longest continuous time

此时,可知式(3)也可化为

Vj=fj(pj,ti)

(5)

根据上述任务优先级原则和最大连续时间原则可以得出,价值函数f(·)应随任务优先级的变大和最大剩余时间的变长而增加,反之变小。f(·)可以通过将任务优先级量化和最大剩余连续时间量化并加权得到,即

(6)

式中,a,b≥0,a+b=1,a和b为加权系数。当a越大b越小,pj对Vj的影响越大,Δtj对Vj的影响越小;当a为0 时,pj对Vj没有影响;当b为0 时,Δtj对Vj没有影响。

2.2.2 确定竞标期望函数

在竞标过程中,竞拍者对于不同的拍卖品获取期望是不同的,同样,在本算法中,调度任务mj对时间段T上时间点的获取期望也是不同的。根据原则(3)可知,时间点ti距离调度任务mj的期望时间越近，其相对于任务mj的价值越高,任务mj获取ti的期望越高。因此取调度任务mj对于时间段T上的时间点ti的获取期望函数为

(7)

式中,使Pj最大的ti称为调度任务mj在时间段T上的最佳时间点tjb,[tjb,tjb+jp]称为最佳时间段。

2.2.3 调度流程

设本轮拍卖是对时间段T进行的第K轮拍卖,每轮拍卖只确定一个已定任务。第K轮拍卖过程如流程图2所示。

图2 拍卖流程图Fig.2 Flow chart of auction

详细步骤如下。

步骤1求出未调度集合M中所有任务在时间段T上的最佳时间点tjb以及最佳时间段[tjb,tjb+jp]。并给出各自在最佳时间点的竞标价fj(pj,tjb)。

步骤2找到给出最高竞标价fj(pj,tjb)的调度任务mj,令T=j,tTz=tTb并将时间段[tTz,tTz+Tp]暂由任务mT占有。

步骤3对于任务集M中除mj以外的其他任务mk,若时间段[tTz,tTz+Tp]不包含任务mk的最佳调度时间段内的点,mk则不参与竞价,否则根据mk的最佳调度时间段内的被占用点的位置分为以下4种情况:

①tkb∈[tTz,tTz+Tp]且在[tTz,tTz+Tp]上不存在一点ti使得fk(pk,ti)≥fT(pT,tTz),则任务mk退出竞价。

②tkb∈[tTz,tTz+Tp]且在[tTz,tTz+Tp]上存在一点ti最先使得fk(pk,ti)≥fT(pT,tTz),则取消任务mT对时间段[tTz,tTz+Tp]的占有状态,令T=k,tTz=ti且任务mT暂时占有时间段[tTz,tTz+Tp]。

③(tkb+tkp)∈[tTz,tTz+Tp]且在[tTz,tTz+Tp]上不存在一点ti使得fk(pk,ti)≥fT(pT,tTz),则任务mk退出竞价。

④(tkb+tkp)∈[tTz,tTz+Tp]且在[tTz,tTz+Tp]上存在一点ti最先使得fk(pk,ti)≥fT(pT,tTz),则取消任务mT对时间段(tkb+tkp)∈[tTz,tTz+Tp]的占有状态,令T=k,tTz=ti且任务mT暂时占有时间段[tTz,tTz+Tp]。

重复步骤3直至在未调度任务集合M中除mT以外的其他任务都退出竞价,则转到步骤4。

步骤4将时间段[tTz,tTz+Tp]判为mT所有,并将时间段[tTz,tTz+Tp]加入占用段集Td,令nT=mT,将mT从未调度任务集合M中移除并将nT加入已定任务集合N。更新未调度任务集合M中所有任务的饱和集Bj,若Bj=∅且tjl≤t1,将任务mj从未调度任务集合M中移除并从任务队列中删除;若Bj=∅且tjl≥t1,将任务mj从未调度任务集合M中移除并推迟到下个调度间隔中的任务集合中。

步骤5若未调度任务集合M=∅,则结束拍卖,调度结束。否则,进入下一轮拍卖。

3 仿真实验分析

本文选取以下3种雷达工作方式对算法进行仿真实验:搜索(分为高优先级搜索和低优先级搜索);验证;跟踪(分为精密跟踪和普通跟踪)。雷达任务优先级和各任务驻留时间如表1所示,其中高优先级搜索任务和低优先级任务的任务周期为60SI,验证任务时间窗为20SI,精密跟踪时间窗为4SI,普通跟踪时间窗为10SI。调度间隔取SI=50 ms,仿真时长为1 000SI。δ1、δ2、δ3、δ4分别设为0.2、0.5、0.2、0.1。

本文采取任务调度成功率、实现价值率及平均时间偏移率3项指标来衡量所设计调度算法的性能,其具体定义及评估意义如下:

(1) 任务调度成功率(scheduling success rate, SSR)为

SSR=N/M

(8)

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

各类事件调度成功率(SSRk)为

SSRk=Nk/Mk,k=1,2,…,n

(9)

式中,Nk为第k类雷达事件调度成功的任务数;Mk为第k类雷达事件参与调度的任务数。

设定仿真场景为雷达任务随仿真周期的增加趋于饱和,在仿真初期逐渐将目标数目增加至150个,其中精密跟踪数目与普通跟踪数的比值为2∶3。分别取不同的a值,观测本算法在不同的a值下总任务调度成功率、精密跟踪调度成功率、实现价值率及平均时间偏移率,并与EDF算法作比较。仿真结果如图3所示。

图3 任务总调度成功率Fig.3 Success rate of task total scheduling

图3为从仿真开始到仿真雷达周期数达到1 000的过程中,本文算法在a=0.3和a=0.6时的任务总调度成功率与EDF的任务总调度成功率对比。EDF算法表示在调度处理中,截止期越早,任务优先级越高,越优先被调度。EDF算法分为抢占式EDF调度和非抢占式调度,本文采用的是抢占式EDF调度方法。其调度的充要条件为

(10)

式中,ei和pi分别是执行时间和周期。EDF算法作为最优的单一处理器调度算法,非常适用于在雷达任务不饱和时对低优先级任务进行调度,但其调度性能在任务达到饱和后不断下降。为了保持EDF算法在单一条件下的优良性能,本文将调度剩余时间加入到拍卖价值函数中,同样能够保证在任务不饱和情况下的任务调度成功率。在仿真刚开始时,雷达任务以搜索为主,调度任务处于不饱和状态,三者皆具有良好的调度性能。但随着仿真周期的增加,不断有新的目标被确认,雷达任务逐渐趋于饱和,三者SSR开始下降, EDF算法由于优先级判定条件较为单一,导致不能充分利用任务调度时间窗的灵活性,因此在仿真后期调度成功率较低。而本文算法将剩余时间和时间窗均添加到调度优先级因素中,因此能够较大限度地利用时间窗,提高本算法在饱和任务情况下的调度成功率。另外,在仿真前期本文算法在a=0.3时比在a=0.6时稍具优势,但在仿真后期任务趋于饱和时,两者性能相似。这是因为在仿真后期雷达调度任务主要以跟踪为主,而a=0.6时更加侧重优先保障高优先级调度。

图4为从仿真开始到仿真雷达周期数达到1 000的过程中,本文算法在a=0和a=1时的任务调度成功率与EDF的任务调度成功率对比。

图4 a、b取特殊值下本算法的任务调度成功率Fig.4 Success rate of task scheduling in this algorithm under the special value of a and b

当a=0时本算法的拍卖价值函数将以最大剩余时间为唯一考虑因素,剩余时间越大拍卖价值越高,这时本算法结合时间窗可以更加有效地利用调度间隔内的时间,提高算法的调度成功率。与EDF算法相比,本算法在时间利用上不但学习了EDF算法的最早截止时间优先调度思想,并且利用了时间窗概念扩充了算法的灵活性,同时结合了AA保证了算法的全局性,因此在调度任务饱和情况下相比EDF具有更高的任务调度成功率。a=1时本算法的拍卖价值函数将以任务优先级做为唯一考虑因素,优先级越大拍卖价值越高。算法虽然能够保障高优先级的优先调度,但是由于没有考虑时间原则,对于调度间隔内的时间利用不够充分。因此在a=1时本算法的总任务调度成功率要比EDF算法更低。

(2) 实现价值率(hit value rate, HVR)为

(11)

式中,pi为任务i工作方式优先级。指成功调度执行的任务工作方式优先级之和与参与调度的总任务工作方式优先级之和的比值。

图5为本算法在不同a值下的实现价值率及与EDF算法的实现价值率的比较。EDF算法由于算法设计时的针对性不同,并未将任务工作方式优先级作为任务调度的重点考虑因素,而本文算法则将任务工作优先级加入到了拍卖价值函数中。因此在调度任务处于饱和状态下,本文算法比EDF算法具有更高的实现价值率,且提高a值可以一定程度上增加实现价值率,但过于提高a值可能会影响到算法的时间利用率,因此在提高a值的时候应注意保障算法的时间利用率。

图5 实现价值率Fig.5 Hit value rate

(3) 平均时间偏移率(average time shifting rate, ATSR)为

(12)

式中,Wi为任务时间窗长度。指各调度成功任务的实际执行时刻和期望执行时刻差的绝对值与时间窗之比的平均值。

图6为本算法在不同a值下的平均时间偏移率与EDF算法的平均时间偏移率的比较。EDF算法将截止时间作为调度优先级的主要参考因素并未考察保证时间偏移率下的任务调度性能,而本文将期望执行时间作为本文拍卖算法的竞拍价值函数,保障了算法的时间偏移率,在饱和任务下比EDF算法具有更低的时间偏移率。因此本文能够很好地保证任务调度的及时性和算法设计的期望时间原则。

图6 平均时间偏移率Fig.6 Average time shifting rate

4 结 论

本文针对多功能PAR任务调度中的时间资源调度问题,提出了基于AA的PAR自适应调度方案。该算法结合PAR任务调度原则,设计AA的竞拍价值函数和竞标期望函数。基于本文提出的设计方案和算法流程进行了仿真实验,分析实验结果得到,该算法在可使多功能PAR任务调度中的各指标达到优良性能。并且通过对比该算法在2种不同a的加权条件下,算法的3项性能指标,表明算法能够通过调整加权系数来提高算法的时间利用率,并在高优先级任务的调度处理中表现出了更高的成功率。