带时间窗的相控阵雷达实时任务调度方法*

郑玉军，田康生，邢晓楠，丰坤

（1.空军预警学院，武汉430019；2.驻207所军代室，太原030006）

带时间窗的相控阵雷达实时任务调度方法*

郑玉军1，田康生1，邢晓楠2，丰坤1

（1.空军预警学院，武汉430019；2.驻207所军代室，太原030006）

为了解决传统相控阵雷达任务调度中采用基于工作方式优先级的方法而存在忽略任务时间紧迫性和重要性的问题，提出了一种基于任务自身工作方式优先级、截止期和空闲时间3个特征参数的相控阵雷达任务调度方法，通过调整参数的权重来适应调度器不同的负载情况，并采用时间窗处理发生冲突的任务请求，确保更多的高优先级任务在调度间隔内被调度。仿真结果表明，所提出的方法能够有效提高任务的调度成功率，明显改善调度器性能。

相控阵雷达，任务调度，截止期，空闲时间，优先级，时间窗

0　引言

相控阵雷达天线在计算机的控制下，可以在微秒量级上进行波束捷变，这就使得相控阵雷达能够在搜索的同时进行多目标跟踪、制导等多种工作方式的操作［1］。充分发挥相控阵雷达波束的灵活电扫描优势的关键在于任务调度。一种高效的调度方法能够有效地分配相控阵雷达资源，达到提升相控阵雷达整体性能的目的。

文献［1］提出了基于最小时间窗的调度算法，将每个任务的可执行时间扩展到整个调度间隔，但仅参考了两个特征参数进行排序；文献［2］提出的多任务并行EDF，综合了截止期和任务自身工作方式优先级的两个特征参数，在负载量较小的情况下有一定的优势，但在过载情况下其调度性能并不理想；文献［3］以加权时间偏移量平方和为调度代价设计调度算法，但算法复杂度过大，以至于影响执行效率；文献［4］提出了一种基于任务综合规划的相控阵雷达调度算法，引入了时间窗的方法，但仅参考了调度时刻前后任务和资源使用情况。

本文在上述研究的基础上，综合考虑了相控阵雷达自身工作方式优先级、任务截止期和空闲时间3个特征参数，提出了一种带时间窗的相控阵雷达调度方法。仿真结果表明本文所提出的方法可以有效改善调度器的性能。

1　任务模型

相控阵雷达任务调度的特点是非抢占式，即已执行的任务不能被其他任务所中断［5］。与实时系统中任务调度不同的是相控阵雷达是按照调度间隔进行任务的调度，即当前调度间隔内调度分析下一个调度间隔内的驻留请求。

任务请求Qi包含以下要素：

①prii表示任务自身工作方式优先级。工作方式优先级类型个数是在调度效率、计算机处理时间、存储器占用量以及目标分类方法之间折衷的结果［6］，旨在根据目标的重要程度强制实现对空监视和目标跟踪。

②di表示任务的截止期，即该任务在这个时间之前必须执行完毕。

③ai表示任务的到达时间，即任务被启动并准备执行的时间。

④dwelli表示任务的驻留时间，即任务在没有其他任务中断的条件下所需的处理器时间。

⑤si表示任务的空闲时间，即该任务执行完毕时刻到截止期的时间间隔，反映了任务的紧迫性。

其中，w2为最晚有效执行时间，w1为最早有效执行时间。

2　调度算法

2.1综合优先级设计

任务的工作方式优先级、截止期和空闲时间是任务的3个重要参数，在很多经典的调度算法（HPF、EDF、LSF等）中得到广泛应用。本文综合考虑这3个特征参数来进行调度分析，将这3个不同量纲的参数映射到同一层面上，再利用线性加权综合法计算其综合优先级pi。本文约定优先级越高，pi数值越小。

假设当前时刻调度器有n个请求，分别记为Q= {Q1，Q2，…，Qn}，并满足所有任务的到达时间不大于当前时刻，且所有任务的截止期减去其驻留时间不小于当前时刻。

将这n个请求按照d、s从小到大和pri从高到低进行排序，得到d序列d1，d2，…，dn（满足d1＜d2＜…＜dn）、s序列s1，s2，…，sn（满足s1＜s2＜…＜sn）以及pri序列pri1，pri2，…，prin（满足pri1＜pri2＜…＜prin）。任务请求Q中每一个任务Qi的3个参数di、si和prii必然是上述3组排列中的3个值，记为＜di，si，prii，＞=＜dk，sl，prim＞，其中k、l、m是［1，n］范围内的自然数，分别为特征参数在d序列、s序列和pri序列中的位置。那么该任务的综合优先级就由参数＜k，l，m＞确定，表示任务的3个属性参数映射到同一层面，并可以直接加权的3个值。那么有pi为k、l和m的函数pi=f（k，l，m）。

综合优先级设计的目的是为了使紧迫的、重要的任务具有较高的优先级，考虑到相控阵雷达处理目标数据的实时性和算法复杂度，本文采用简单线性函数计算pi，即

其中α、β、γ分别为k、l、m的加权值，且α+β+γ=1。当α＞β+γ时，调度算法为截止期优先，即任务的截止期对综合优先级的影响最大；当β＞α+γ时，调度算法为空闲时间优先；同样，γ＞α+β时，调度算法为工作方式优先级优先；当α=β=γ时（本文选取α=0. 33、β=0.33、γ=0.34），即均衡考虑3个参数，得到的是截止期加空闲时间加工作方式优先级的调度算法，是在截止期、空闲时间以及工作方式优先级之间进行折衷的结果。

式（2）得到的综合优先级与每个任务请求可能不是一一对应的，有可能出现多个请求的综合优先级相同的情况［7］。在这种情况下，对综合优先级相同的请求可采用FIFO（FirstInFirstOut）准则来处理。

2.2时间窗设计

为了解决任务请求在时间上冲突的问题，利用任务的实际执行时间可在期望执行时间前后移动的特点，本文在部分借鉴文献［8］时间窗设计的基础上，提出了一种带时间窗的相控阵雷达任务实时调度方法。算法流程如下页图1所示。

2.3调度算法的实现

文中提出的带时间窗的相控阵雷达实时任务调度方法流程如图2所示，由综合优先级设计和时间窗两个部分组成。

图1　带时间窗的相控阵雷达任务实时调度流程

3　仿真实验

3.1仿真参数设置

相控阵雷达工作在TAS模式，模拟5种典型的雷达任务：验证、精密跟踪、普通跟踪、高优先级搜索和低优先级搜索，如表1所示。调度间隔SI=1 s，按照固定的更新周期产生搜索任务，当搜索检测到目标时或以一定概率出现虚警时产生验证任务，检测概率Pd=0.9，虚警概率Pfa=10-6。目标跟踪起始后按其更新率周期产生跟踪任务，一次实验的仿真时间为10s。

图2　调度算法流程图

相控阵雷达调度器负载容量是目标跟踪能力的综合体现，由跟踪的驻留时间和采样率决定［9］。根据式（3）推算调度器负载为250个。

其中，T为采样周期，dwell为驻留时间。

3.2仿真结果与分析

表征任务调度优劣的指标一般用任务截止期错失率（Missed DeadlineRatio，MDR）和调度成功率（Scheduling Success Rate，SSR），计算公式如下所示［10］。

其中，Ne为未成功调度执行的任务数，N为任务总数。

表1　相控阵雷达任务参数设置

图3　搜索任务的截止期错失率

图4　跟踪任务的截止期错失率

图3和图4为10次仿真结果的平均值，可以看出当γ=1时，pi=m，综合优先级完全取决于自身的工作方式优先级，在过载的情况下，删除的搜索任务最多，跟踪任务的截止期错失率最低；当γ=0.7时，pi=α·k+β·l+0.7m，综合优先级由截止期、空闲时间和工作方式优先级决定，但工作方式优先级权重较大，在调度器过载的情况下，删除了一定量的搜索任务，保证了跟踪任务的执行；同样，γ=0.5时，删除了一定量的搜索任务和跟踪任务；在γ=0.3时，综合优先级很大程度上取决于截止期和空闲时间，跟踪任务虽然工作方式优先级高，但权重较小，故调度器删除了一定量的跟踪任务；当γ=0时，综合优先级完全由截止期和空闲时间决定，此时，搜索任务的截止期错失率最低，跟踪任务的截止期错失率最高。

权值的大小可以由相控阵雷达执行的任务来调节，当执行搜索任务时，可适当降低γ值，当执行跟踪任务时，可适当增大γ值。

为了验证本文算法的性能，在相同仿真场景下与经典EDF算法进行对比。图5是γ分别为0.7和0.3时与经典EDF算法的仿真图，可以看出跟踪目标数在250个之前两种算法的调度成功率在0.99以上；随着调度器负载的增加，两种算法的SSR随之降低，且γ=0.3比γ=0.7时的算法SSR下降的快，但调度性能均优于EDF算法。

图5　任务调度成功率曲线

为验证带时间窗的调度算法的有效性，将文中提出的方法与无时间窗的综合优先级任务调度算法进行仿真对比，结果如图6～图8所示。可以看出，带时间窗的调度算法优于无时间窗的综合优先级任务调度算法。

图6　任务请求序列

图7　无时间窗的综合优先级任务调度序列

图8　带时间窗的综合优先级任务调度序列

下页表2为两种算法调度性能结果，其中执行任务数包括搜索任务和跟踪任务。在跟踪目标不多的情况下，两种方法的调度成功率都维持在较高的水平上，且差别不大；随着跟踪目标数增加，带时间窗调度方法的优势显现出来，调度成功率比传统方法高出2%～4%，且在跟踪150个目标的情况下调度成功率维持在0.74以上。

表2　两种算法调度成功率对比

4　结论

如何在资源约束和雷达限制范围内高效地执行多目标探测和跟踪任务是相控阵雷达研制和使用中的一个关键问题。本文针对传统调度算法调度成功率低的问题，提出了一种新的相控阵雷达任务调度方法，该方法借鉴了EDF、HPF和LSF等经典调度算法的优势，综合考虑了任务自身工作方式优先级、截止期和空闲时间，并且引入了时间窗的方法来提高时间资源利用率。仿真结果表明文中方法可以高效地调度任务请求，特别是在资源受限的情况下具有很高的调度成功率。

从文中可以看出3个特征参数的权重在不同程度上影响任务调度的性能，权重值设置过小会弱化该参数的作用，权重值设置过大同样会降低调度成功率。因此，如何设置合理的权重是下一步研究的内容。

［1］綦文超，杨瑞娟，李晓柏，等.基于最小时间窗的多功能雷达调度算法研究［J］.现代防御技术，2012，40（5）：104-110.

［2］綦文超，杨瑞娟，李晓柏，等.多功能一体化雷达任务调度算法研究［J］.雷达科学与技术，2012，10（2）：150-155.

［3］赵宇.李建勋，曹兰英，等.基于二次规划的相控阵雷达任务自适应调度算法［J］.系统工程与电子技术，2012，34（4）：698-703.

［4］郑世友，郑瑶.基于任务综合规划的相控阵雷达自适应调度方法［J］.计算机仿真，2013，30（7）：11-16.

［5］卢建斌，胡卫东，郁文贤.多功能相控阵雷达实时任务调度研究［J］.电子学报，2006，34（4）：732-736.

［6］赵新爽，汪厚祥，蔡益朝.反导预警作战资源调度方法［J］.系统工程与电子技术，2015，37（6）：1300-1305.

［7］郑伟，王磊，曹建蜀.改进DPSO算法求解仿真任务调度问题［J］.信号处理，2015，31（4）：474-482.

［8］郭坤鹏，左燕，薛安克.一种基于模糊逻辑优先级的雷达任务自适应调度算法［J］.江南大学学报（自然科学版），2013，12（5）：591-595.

［9］罗江锋，朱承，刘忠，等.连续多目标来袭下的舰艇防空火力在线调度［J］.系统工程理论与实践，2014，34（11）：2929-2937.

［10］叶朝谋，丁建江，余志强，等.基于周期分区的相控阵雷达任务交叉调度研究［J］.电子与信息学报，2014，36（2）：435-440.

Way of Phased Array Radar Real-time Task Scheduling with Time Windows

ZHENG Yu-jun1，TIANKang-sheng1，XING Xiao-nan2，FENG Kun1
（1.Air Force Early-warning Academy，Wuhan 430019，China；2.Martial Delegate Office of PLA in 207 Institute，Taiyuan 030006，China）

In order to solve the traditional phased array radar task scheduling，a prior way，which will ignore the issues of the urgency and importance of task time，based on work style，is adopted to come up with a way of the phased array radar task scheduling that is based on the three characteristic parameters：the priority of itself work style，deadline and idle time.It accommodates the different load conditions of the radar scheduler by adjusting the parameter weight.The request of handling sudden tasks with time windows is aimed at making sure that more and more high priority tasks can be dispatched in a scheduling interval.The simulation results show that the methods mentioned in the article can efficiently increase the successful rate of task scheduling and obviously improve the property of radar scheduler.

phasedarrayradar，task scheduling，deadline，idletime，priority，timewindow

TN958.92

A

1002-0640（2016）10-0070-05

2015-08-13

2015-09-16

2014年度全军军事类研究生基金资助项目（2014JY548）

郑玉军（1988-），男，山东济宁人，博士生。研究方向：预警情报组网。