基于广义时间窗的旋转相控阵雷达资源调度算法

李纪三，纪彦星，曹 鼎，刘 溶，任 渊

（1.南京船舶雷达研究所,江苏南京 210000；2.291404部队,河北秦皇岛 066000）

1 引言

相控阵雷达任务调度的内涵为当多任务抢占资源时确定任务执行的时刻和使用的资源［1］.相控阵雷达资源分为时间资源、能量资源和计算资源.为了提高探测威力和保持对弱小目标的探测能力，雷达通常需要满载工作.计算资源主要是指板卡的处理能力.随着芯片集成技术的发展及高速处理器的广泛应用，实时计算能力也不再受到限制.因此通常说的相控阵雷达资源调度主要指时间资源的调度［2，3］.

现代战场电磁环境日益复杂，作战目标更加多样化，相控阵雷达执行的任务种类和数量不断增多，这就要求在有限时间资源内尽可能多地执行任务［4］.相控阵雷达主要承担的任务包括：低空搜索，中高空搜索，海面目标跟踪，空中目标跟踪，武器制导，失跟捕获，目标确认，打击评估，目标分类识别，气象探测等［5～7］.

高效合理的调度策略对提升相控阵雷达整体作战效能具有重要意义.基于时间窗和优先级的自适应调度算法，被广泛应用在相控阵雷达的任务调度中［8～12］.文献［13］首次提出相控阵雷达任务调度时间窗，文献［14］对相控阵雷达跟踪类任务时间窗的计算进行了分析和描述，认为跟踪任务时间窗与目标位置、速度、距离以及雷达波束宽度有关，但没有给出时间窗的具体计算过程.文献［15］提出一种基于动态时间窗的任务调度方法，根据目标跟踪滤波中的残差与目标跟踪波门之间的约束关系以及搜索帧周期的约束，分别实现对跟踪任务和搜索任务的时间窗计算.文献［16］基于任务的固定时间窗，提出一种基于分支定界法的调度算法，兼顾了相控阵雷达事件调度问题中调度成功率、时间偏移率与算法时效性三者之间的矛盾.文献［17］针对相控阵雷达事件调度传统的基于固定时间窗的方法，在面对高速高机动目标时存在跟踪精度较低、调度成功率不高的问题，利用可变时间窗对传统调度方法加以改进.

以上研究应用在固定相控阵雷达资源调度取得了很好的效果，但是无法直接移植到旋转相控阵雷达的资源调度.相对于固定面阵相控阵雷达旋转相控阵雷达有其自身特点［18］.

旋转相控阵雷达受到扇区饱和攻击时应用传统的基于时间窗和优先级调度算法会造成任务调度失败.因为通常任务时间窗较小，大约为50～100 ms，要是考虑目标的机动性则时间窗会更小.如果在某个扇区方位来袭目标密集，并且单个跟踪任务花费时间较多，将导致多个任务竞争同一调度时间间隔的资源，造成任务调度成功率下降.

针对上述问题，本文在传统自适应调度算法基础上提出一种基于广义时间窗的任务预规划调度算法.根据旋转相控阵雷达波束偏扫最大角度计算出目标跟踪的最大方位窗，通过天线转速将最大方位窗换算为目标跟踪广义时间窗，基于广义时间窗进行任务编排，确定目标跟踪的执行时刻.再根据目标运动状态信息，外推出执行时刻的目标方位和仰角.相较于传统自适应调度算法的由数据处理计算执行位置和执行时刻以及时间窗的调度方法，本算法计算出的广义时间窗远远大于传统自适应调度的时间窗，当同方位上跟踪任务饱和时，较大的时间窗能够显著提高任务调度的成功率.

2 雷达任务时间窗分析

A G Huizing 在1996 年研究雷达自适应调度算法时在文献［13］首次提出时间窗概念，其含义为波束驻留发射时刻在期望发射时刻前后可移动的有效范围.在时间上有冲突的雷达任务在时间窗约束下经过调整后可能都被执行，这将提高相控阵雷达的任务调度成功率和时间利用率，在有限时间资源内调度执行更多的任务.因此，基于任务优先级和时间窗的调度算法被广泛地应用于相控阵雷达的任务调度中.

一般相控阵雷达采用专门的TAS（Track And Search）波束对目标进行跟踪.单脉冲和差比幅测角具有测角精度高、抗干扰能力强等特点，在实际工程领域得到广泛应用.为保证测角精度，一般目标应位于波束中心附近［15］.因此，相控阵雷达跟踪波门大小受限于波束的宽度和测角精度的要求.如图1 所示，在k时刻目标位于A点，坐标（xk，yk，zk），采样周期为T，目标的速度为（vx，vy，vz），k+1 时刻目标位置A1，坐标

图1 雷达跟踪时间窗示意图

在k+1时刻，雷达对极坐标系的A1预测点进行照射，由于存在过程噪声（目标发生机动）目标所在位置实际在C点，A1与C点的空间距离称为残差.如果跟踪执行的提前（目标还没运动到B点）或者执行的延后（目标已运动到D点）都无法照射到目标，从B时刻到D时刻的时间段称为目标跟踪时间窗.固定时间窗、可变时间窗及广义时间窗的原理、计算方法和效果如表1所示.

表1 各种时间窗对比

3 时间窗计算

3.1 基于卡尔曼滤波算法的跟踪时间窗计算

卡尔曼滤波器由于具有数据存储量小计算实时性强等优点，被广泛应用于雷达及其他跟踪测量系统中，其空间模型可用如下状态方程和量测方程描述［18］：

w(k)和v(k)为零均值的高斯白噪声且互不相关，即

其中，Q(i)为过程噪声的协方差矩阵，R(i)为量测噪声的协方差矩阵.在图1 中，k时刻目标在A点的状态的估计值记为对应协方差为P(k|k)，由于目标状态方程为线性方程，且高斯分布经过线性变换后仍为高斯分布，因此目标状态的一步状态预测值同样服从高斯分布，即k+1 时刻A1点的预测值为x(k+1|k)对应协方差为P(k+1|k))，同理预测的值为

通常，

被称为任务在k+1 时刻执行时的残差，z(k+1)为目标在量测值.

若任务不在期望时刻（k+1 时刻）执行，而在k+1+ΔT时刻执行，此时的残差计算为［15］

v是目标速度，ΔT为在时间窗约束下执行时刻相对于期望执行时刻左右移动的时间偏移.雷达在极坐标系下跟踪残差的形式为

其中，vθ和vβ分别为方位和仰角上的速度.

为了覆盖住目标雷达的波束宽度，σ须满足：

为保证和差比幅测角的精度，需要满足：

其中，λ为满足比幅测角精度要求所在目标在波束的中心位置的比例系数，当式（9）取等号时，则可计算出时间窗的大小.

以上推导没有考虑目标的机动，若目标在运行过程中发生机动，根据牛顿运动方程：

其中，s为目标的位置，v0为目标的速度，a为目标的加速度，T为跟踪采样时间间隔.位置的变化量为

角度的变化率Δφ还与目标的距离有关：

由式（7）～（12）可推导出时间窗ΔT的关系式如下：

若天线的旋转周期为2 s，目标速度为800 m/s，TAS的波束宽度为2°，跟踪最大的机动过载为10g，g为重力加速度，保精度的比例系数为0.6，根据式（13），在距离25 km 处目标速度与时间窗的关系如图2，从图2 中可以看出速度越大时间窗越小，即高速目标需要设置更小的时间窗.

图2 时间窗随速度变化图

3.2 广义时间窗计算

时间窗与目标的运动状态和采样周期相关，特别对于高速高机动目标时间窗更小，当多个跟踪任务位于同一调度间隔，会造成任务调度失败.本文提出的广义时间窗是为了扇区任务负载的提前规划，即该目标所在的任务扇区饱和时，将该任务调配到其他扇区.广义时间窗的大小受限于雷达的转速和偏扫范围，通常比传统的时间窗大的多，能够将饱和扇区的任务稀释到空闲的扇区，因此能够显著提高任务调度成功率和时间利用率.相控阵雷达天线增益随扫描角增大而变小，大的扫描角将会导致降低作用距离和增大测量误差，天线扫描角为(φ，θ)，雷达信噪比将由天线法线扫描的SNB0下降到SNBs：

广义时间窗TW计算公式如下：

其中，α为天线最大允许偏移角度，TC为天线周期.当天线周期为2 s 时，天线允许最大偏移角度为45°，则对应时间窗为250 ms.

4 调度策略

调度策略有固定模板法和自适应调度算法，固定模板法的时间利用率低，且调度灵活性不高.自适应调度算法主要有基于时间指针调度算法和基于时间窗和优先级的自适应调度算法.自适应调度算法主要思想是按照任务选时间，即高优级的任务按照其期望执行时刻在本调度间隔内优先选择执行的时间段，低优先级的任务在剩余的时间碎片中选择可以执行的时间段，如果与已经排好的高优先级的任务有冲突，则在时间窗的约束下左右移动，直到找到合适的时间，如果找不到，则将该任务加入到延迟队列或删除队列.

由以上分析看出，基于时间指针的算法其时间利用率高，但任务执行的偏移率也高.旋转相控阵雷达任务执行偏移率高将引起天线波束偏离法线大，导致威力下降和信噪比降低.因此相较于时间指针算法，自适应调度算法更适合旋转相控阵雷达的任务调度.

4.1 调度数学模型

相控阵雷达任务调度本质上可归为车间作业调度问题，属于典型的NP-hard 难题，需要满足多参数优化与多约束条件.本文主要考虑相控阵时间资源的调度，实时驻留调度的数学模型的可描述为［19］

其中，MA为调度代价，MB为延迟代价，MC为删除代价.约束条件为：对于传统雷达来说，事件执行期间无法被其他事件抢占，且雷达在同一时刻只能执行一个事件.则事件i所占用的雷达时间资源可表述为，要调度第i+1个事件需满足：

4.2 任务综合优先级计算分析

合理有效的任务优先级设计方法对提升相控阵雷达的整体性能有着重要意义，通常工作方式优先级、目标威胁度和任务紧急程度作为综合优先级的构成因素.其中，工作方式优先级由雷达工作方式确定，任务紧急程度与任务的截止期相关，目标威胁度与目标的当前状态信息有关，目标威胁度函数由目标威胁模型来构造：

式中，ρi为各因素的权重，pv、ph、pθ和pr分别为速度威胁函数、高度威胁函数、航向威胁函数和径向距离威胁函数［5］.

4.3 基于广义时间窗的扇区的任务预分配

传统的自适应调度算法在受到扇区饱和攻击或者多个跟踪任务竞争同一时间片时，任务调度成功率会下降.在当前的调度间隔内任务排满之后，仍然存在大量的未被调度的任务，但由于时间窗限制（通常跟踪任务时间窗在几十毫秒到百毫秒之间），未被安排的任务无法调配到其他扇区.本文在自适应调度算法的基础上，提出了一种基于广义时间窗的任务预规划自适应调度算法，如图3 所示.当某个方位扇区上的任务出现饱和时，利用广义时间窗内任务预规划调配算法，将受到饱和攻击扇区内的任务调配到前面的调度间隔和后面的调度间隔中去执行.

图3 相控阵雷达扇区饱和攻击偏扫示意图

跟踪任务预分配：跟踪任务按照期望执行的时刻加入相应的扇区任务库中，每一个扇区对应于一个调度间隔.根据跟踪任务期望执行的时刻加入到相应的任务库.调度模块收到跟踪任务请求后，读取当前任务所在扇区已经分配任务的总时间，如果总时间超过某一门限值则将该任务规划到相邻扇区.然后重新设置该任务的期望执行时间，并按照新的期望执行时刻，对照射的方位和仰角进行外推.如果相邻的扇区的任务也满了，则将任务放在本扇区内，在调度过程中按照优先级进行取舍.由于对原有的时间窗进行了扩大，则目标必不在预测的位置为中心的波束宽度内，因此需要根据目标的航向航速和对目标的位置重新计算，重新计算位置的时间窗，可设置为与原先时间窗大小相同.

4.4 任务调度

由于搜索任务涉及回波的视频显示和点迹凝聚处理，任务执行的顺序最好保持方位从小往大，仰角从低往高.本算法通过设置搜索任务的期望执行时间来控制任务顺序执行.如方位1上的任务比方位2上的期望时刻早，同一方位上低仰角要比高仰角的期望时刻早.另外自适应调度算法会产生一些很小的时间碎片，在编排的过程中需要将这些小时间碎片挤掉以提高时间资源的利用率.具体任务编排过程如下：

（1）在每个调度间隔开始，取出该调度间隔对应的扇区任务库中的搜索任务列表、跟踪列表和确认列表，按照优先级从高到低排序；

（2）按照优先级从高往低取出任务，根据任务的期望执行时刻确定该任务的执行时刻，每安排完一个任务，同时记录本间隔内的空隙时间段；

（3）从任务列表中取出下个任务，判断能否在时间窗约束下在某个空闲时间段内执行；

（4）安排完所有能在本间隔内的任务后，获取发射波束的顺序列表，然后重新设定每个任务的发射时刻，把前一个任务的结束时刻作为下个任务的执行时刻，把时间碎片挤掉；

（5）本间隔内最后一个任务结束时刻作为下个调度间隔的开始时间.

通过以上任务编排过程可以看出，相对于传统的自适应调度算法，本算法在任务编排完成后，又对任务执行列表进行了优化，将前一个任务的结束时刻作为下个任务的执行开始时刻，对任务的实际执行时刻进行优化，优化后任务与任务之间将没有小的时间碎片，通过将本间隔的结束时刻作为下个调度间隔的开始时刻，则调度间隔之间没有时间碎片，这两个措施有效的提高了时间资源的利用率；在取任务阶段，先进行优先级的排序，然后从优先级高往低取任务，保证了高优先级任务优先执行.

5 仿真实验

5.1 任务模型

任务模型设置为{ptype，pId，ppri，tdwell，texpect，texcute，twindow，mazi，mele，mdis，mv，mcourse}其中ptype为任务类型，pId为目标批号，ppri为任务优先级，tdwell为任务驻留时间，texpect为任务期望执行时刻，texcute为任务实际执行时刻，twindow为任务执行的时间窗，mazi为任务执行的方位，mele为任务执行的仰角，mdis为目标的距离，mv为目标的速度，mcourse为目标的航向.调度性能评估指标包括：任务调度成功率，时间利用率，平均时间偏移率和实现价值率.

5.2 仿真态势

通常相控阵雷达为了抑制杂波在不同的仰角层采用不同的信号波形.如英国的MESAR 雷达［8］仰角分区如图4所示.

图4 仰角分区扫描示意图

搜索任务分为了Search_Pd、Search_MTI、Search_single1、Search_single2 四类任务，将跟踪分为了近程确认（Check_near）、近程精跟（TAS_near）、中远程精跟（TAS_far）三类任务.雷达转速为2 s，方位波束宽度为3°，则全区域有120个方位波位，2 s内共有20个调度间隔，每个调度间隔内要完成6 个方位波位的搜索任务，假设搜索占用的时间资源最高为80%，每个调度间隔剩余20 ms的剩余时间.每个方位波位上有4个任务，分别为Search_PD、Search_MTI、Search_single1、Search_single2，则整圈有480 个搜索任务.本实验主要验证基于广义时间窗调度算法的任务调度的时间利用率和成功率，工作方式优先级设置原则为跟踪类任务高于搜索类任务，即当时间资源紧张时，先舍弃低优先级的搜索任务，跟踪类任务优先级的变化不会影响调度的时间利用率和成功率，因此本实验采用固定任务优先级，搜索和跟踪任务的优先级设置如表1所示.

表1 任务优先级及时间窗

场景1在第4 个调度间隔有3 个跟踪请求而其他时间段无请求，3 个任务占用时间资源为23 ms，而本间隔内搜索任务占用的时间为80 ms，调度结果如图5 所示，本文算法和自适应调度算法的结果相同.

图5 场景1调度执行队列

场景2在第4个调度间隔有6个跟踪任务请求，任务请求的总时间为46 ms.传统的自适应调度算法调度结果如图6所示.6个跟踪任务都在本调度间隔内执行.跟踪任务挤占了搜索任务，本调度间隔内的搜索任务只能执行优先级为4的，也就是最低仰角的PD任务，而优先级3的任务只能执行3个.本文算法的调度结果如图7所示.

图6 场景2自适应调度算法调度队列

第4个任务到来时，由于已经超过了扇区资源的规划门限，另外3个跟踪任务，在广义时间窗的约束下，排到了下个调度间隔，本调度间隔内高优先等级的搜索仍然能够执行.两种算法在1、2、3、6 调度结果相同，传统算法在第四个调度间隔的调度成功率只有0.486，而本文算法在第4 个调度间隔能达到0.91.在第5 个调度间隔传统算法的调度任务成功率为1，而本文的成功率是0.91，这是因为本文算法将第4 个调度间隔的高优先级的跟踪任务调配到第5 个调度间隔，调配后第5 个调度间隔的时间需求总量超过了本调度间隔的时间预算，低优先级的任务被舍弃，导致任务调度的成功率小于1，如果综合看第4 和5 调度间隔的时间利用率和价值实现率，本文算法有明显优势.

场景3本场景共设置12个任务跟踪请求，12个请求的总的时间资源为92 ms，达到任务饱和状态，即跟踪的时间资源接近了总的调度间隔的时间资源.自适应调度算法结果如图8所示，调度间隔内主要是跟踪任务，搜索任务被舍弃了.而本文算法，如图9 所示，将任务释放到了相邻的两个调度间隔，保住了高优先级的搜索.

图8 场景3自适应调度算法调度队列

图9 场景3本文算法调度队列

本文提出的调度算法在第4个饱和扇区的调度成功率要高于自适应调度算法，在相邻的第3 和第5 个调度间隔，本文的成功率不及传统算法，原因与场景2中分析一致，即为了执行饱和扇区的高优先级任务，而舍弃了本调度间隔的低优先级任务，从调度间隔3、4、5的综合性能看，本文的调度算法也优于传统的自适应算法.

5.3 结果分析

场景1 到场景3 跟踪任务量依次增加，3 个场景展示了雷达在工作过程中任务由少变多直到饱和的三个阶段.场景1 任务量少，基于固定时间窗的传统自适应调度算法和本文基于广义时间窗的调度算法性能相当，场景2 任务量增多，通过任务规划将第4 个调度间隔的部分任务调配到第5 个调度间隔执行，场景3中任务饱和，本文算法将饱和的任务稀释到了左右相邻扇区.统计了饱和扇区及其左右受影响扇区共300 ms 时间长度的平均价值实现率，当任务数不饱和时本算法和传统算法性能相当，随着任务增多本算法优于传统算法，时间利用率对比如图10，本算法在任务饱和时的3 个扇区的平均时间利用率也高于传统算法.

图10 时间利用率随任务数变化曲线

6 结论

针对旋转相控阵雷达任务调度问题，提出一种基于广义时间窗的任务预规划调度方法，给出新的调度方法的详细流程.并将该方法与传统的自适应调度算法进行对比仿真，验证了该方法的有效性和优越性.仿真结果表明，在任务量饱和的情况下该方法能释放旋转相控阵雷达的相扫潜能，将任务饱和扇区内的任务调配到相邻扇区执行，有效提高了时间资源的利用率.