基于综合优先级的改进执行时间分配算法

侯泽欣，涂刚毅，吴少鹏

(中国船舶重工集团公司第七二四研究所，南京 210003)

0 引言

相控阵天线的波束快速扫描技术特点使相控阵雷达可在搜索的同时进行多目标跟踪及多种雷达功能的操作，但相控阵雷达的多目标、多功能工作能力受雷达时间资源及雷达辐射信号总能量的限制。因此，研究合理的雷达任务调度算法对相控阵雷达的资源有效分配及优化雷达的整体性能具有重大意义。

传统相控阵雷达调度按照任务预定的优先级由高到低或截止期由早到晚调度执行，灵活性差、时间利用率低。何金新、李大鹏等［1-2］对驻留时间窗进行了研究，使雷达任务调度的时间灵活性得到提高，但对任务的优先级设计均未作考虑。卢建斌等［3］提出综合考虑工作方式优先级和截止期两个参数获得综合优先级，算法灵活性高，调度性能有明显改善。王多强等［4］对实时任务调度的多特征参数综合优先级设计进行了研究，使调度性能得到提高。

本文基于多特征参数的任务优先级表设计思想，研究一种雷达任务多特征参数综合优先级的计算方法，并在传统的自适应执行时间顺序分配调度算法基础上提出改进的执行时间分配算法，根据综合优先级计算结果进行任务的自适应调度。最后仿真结果表明，本文所提算法能够有效地减小任务的平均时间偏移率，确保多功能相控阵雷达中对时序要求极高的通信、干扰及数据传输等任务的有效执行，提高多功能相控阵雷达的作战效能。

1 综合优先级设计

相控阵雷达控制器需要对申请执行的任务进行有效的调度分配，根据各任务综合优先级的大小进行合理的调度。下面对几种主要雷达驻留任务进行分析，根据各任务特征参数研究任务综合优先级的计算算法。

1.1 雷达驻留任务分析

根据相控阵雷达系统的两种最基本工作方式，将申请调度任务分为搜索和跟踪两类，其中搜索任务包括低优先级搜索和高优先级搜索任务。搜索检测到新目标后将产生确认任务对目标进行航迹起始，然后针对目标的不同特征属性及威胁度分析将跟踪任务分为普通跟踪和精密跟踪任务。下面给出相控阵雷达的驻留任务的形式化描述:

其中，Pri为工作方式优先级;TOA为期望发射时间即到达时间;W 是任务时间窗;Tdwell为驻留时间即任务执行所需时间长度;D 表示任务的绝对截止期(D=TOA+W/2），即任务必须在该时刻前执行完毕;TaskStep为任务自动生成的周期即更新率;(R，α，β）为期望波束位置。任务调度模块将根据雷达申请任务的相关属性参数进行综合优先级的计算，根据综合优先级大小在下一调度间隔分配任务序列。

1.2 综合优先级计算

运用优先级表的思想［5］及任务的空闲时间、截止期和工作方式优先级3个特征参数进行综合优先级的设计。

1.2.1 任务调度原则

考虑到任务的重要性和紧迫性，综合优先级设计首先需要遵循以下调度原则:

(1）工作方式优先级越高、截止期越早及任务空闲时间越短的任务的综合优先级越高，任务就越早得到执行;

(2）综合优先级值计算结果相同时采用FIFO的准则进行调整。

1.2.2 综合优先级计算算法

基于优先级表的思想并按照任务调度原则设计任务综合优先级的计算算法，其具体实现步骤如下:

步骤1 将任务空闲时间和截止期序列按照升序排列，工作方式优先级序列按照降序排列。各任务的3个参数在排序后的序列值为ti、di、wi;

步骤2 由图1 优先级表设计模式计算各任务的优先级等级pi=wi+di+ti;

图1 优先级表设计

步骤3 优先考虑工作方式优先级和截止期参数，其重要程度相同且均大于空闲时间参数。综合优先级的计算公式如式(1）。图2为综合优先级计算结果。

图2 任务综合优先级

下面利用本节综合优先级的计算算法对雷达驻留任务进行自适应资源调度。

2 自适应调度算法设计

对于多功能多任务相控阵雷达系统，采用自适应调度算法，雷达的资源利用率最高、资源管理调度效果最好。

2.1 自适应调度算法

相控阵雷达自适应调度算法的设计需要遵循3 种原则:优先级原则、时间利用原则和期望时间原则，然后对雷达申请任务进行分析，可将满足不同条件的任务送入执行队列、延迟队列或删除队列。基于综合优先级的自适应调度算法实现步骤如下:

(1）初始化调度程序，清空各类任务队列;

(2）计算申请任务队列中期望执行时间在本调度间隔内任务的综合优先级;

(3）依次取综合优先级最大的任务，判断其驻留时间是否满足小于调度间隔的剩余时间，若满足则根据该任务的可执行时间范围［te－W/2，te+W/2］分配任务实际执行时刻tp，且任务在该时刻执行不与已调度执行的任务在时间上产生冲突，将任务送入执行队列;当不满足调度间隔剩余时间或任务可分配执行时刻与其他已调度任务时间冲突则时转入步骤4;

(4）判断任务最晚可执行时间是否满足在下一调度间隔内执行，若满足则将任务送入延迟队列，否则送入删除队列;

(5）分析统计调度结果并计算评估指标，调度分析结束。

2.2 改进任务执行时间分配算法

经过仿真分析，发现基于综合优先级的自适应调度算法若按照传统的执行时间顺序分配方法(即将当前仿真时刻设置为该任务的实际调度执行时刻），其任务调度的平均时间偏移率较高。

平均时间偏移率体现了雷达任务调度执行的及时性，反映了任务执行效果的好坏，并且有些任务如通信、数据传输和干扰等对任务执行的时序要求很高，较大的时间偏移会使任务执行的效果很差甚至会造成执行失败。基于上述分析，本文研究了改进的执行时间分配算法。

改进执行时间分配算法:首先选择综合优先级最高的任务进行分配调度。若其到达时刻，即期望执行时间未被占用，则将到达时刻分配给任务执行;若到达时刻已被先前所调度任务占用，则查找距离其到达时刻最近的空余时间段分配实际执行时间。改进执行时间分配算法流程如图3所示。

3 仿真结果分析

基于以上研究对算法进行了仿真。为有效衡量调度算法的性能，根据自适应调度算法的设计原则，从任务调度成功率(SSR）、实现价值率(HVR）、时间利用率(TUR）和平均时间偏移率(ATSR）四项指标［6-7］评估算法的调度性能，并将本文所提算法与传统调度算法性能进行仿真比较。

图3 改进执行时间分配算法流程图

3.1 基于综合优先级的自适应调度仿真

假设仿真场景中有5 种典型雷达任务:确认任务、精密跟踪、普通跟踪、高优先级搜索和低优先级搜索，其具体参数如表1所示，其中调度间隔SI=50 ms。高优先级、低优先级搜索任务是按照固定的更新率周期性产生，确认任务一部分以一定概率产生代表虚警，另一部分是当搜索检测到目标时产生，检测概率为0.9，虚警概率0.001。精密跟踪、普通跟踪任务是对目标跟踪起始后按其更新率周期性产生。雷达作用空域内随机产生50个目标，对其中20个目标进行精密跟踪，总调度仿真时间12 s。

采用基于综合优先级的自适应调度算法进行相控阵雷达任务调度仿真，分析执行时间顺序分配方法与改进执行时间分配算法的仿真结果，得到各项评估性能指标的比较结果如表2所示。雷达任务调度执行序列结果如图4所示，条形框表示各雷达任务，其高度为任务工作方式优先级，宽度表示任务的驻留时间长度。图4(a）、(b）为两种执行时间分配方法未经调度的雷达任务原始请求序列图，可以看出两种方法产生的原始任务请求序列均有较多的任务重叠，即不同任务的期望执行时间产生冲突、抢占同一执行时间段。经过自适应算法调度使发生冲突的雷达申请任务的实际执行时刻相对期望执行时刻提前或延迟，使它们得到成功调度，调度结果如图4(c）、(d）所示。通过与原始请求序列比较可明显看出，改进算法任务实际执行时间与其期望执行时间更贴近，任务执行的效果更好，且该调度间隔内的任务基本在本调度间隔分配成功，而传统方法有大量任务将被延迟到时间窗范围内的下几个调度间隔中分配执行。

表1 相控阵雷达任务参数设置编号任务类型工作方式

调度仿真结束计算分析结果，各项评估性能指标如表2所示。

表2 调度算法性能评估指标

由表2 指标结果可以看出，利用基于综合优先级的自适应调度算法进行调度时，不管运用何种执行时间分配算法都能达到较好的调度性能。而通过比较两种不同执行时间分配方法的评估指标，得出如下结论:改进算法在任务调度成功率、时间利用率及实现价值率等指标损失很小的情况下平均时间偏移率大幅度降低。

3.2 算法性能比较

为验证本文算法性能的优劣，在相同场景设置下精密跟踪目标数由2个增加到20个;对本文算法和传统EDF(截止期优先）、HPF(高工作方式优先级优先）算法进行仿真，计算算法性能评估指标，做100 次蒙特卡洛实验结果如图5。

由图5 可见，本文算法任务调度的时间偏移率较传统算法大大降低且任务调度成功率、时间利用率等指标损失极小。因此，本文算法可有效保障多功能相控阵雷达通信、干扰及数据传输等多功能多任务的有效调度执行，具有很好的调度性能。

图4 雷达任务自适应调度仿真结果

图5 性能评估曲线比较

4 结束语

本文基于综合优先级的改进执行时间分配算法，在综合优先级计算算法研究的基础上，提出相控阵雷达自适应调度的改进执行时间分配方法并进行仿真。仿真结果表明，与传统调度算法相比，本文算法在任务调度成功率、时间利用率等指标损失极小的情况下有效降低了任务执行的时间偏移率，可有效保障通信等多功能多任务的执行效果、提高多功能相控阵雷达系统的作战效能。

［1］何金新，邱杰，王国宏.相控阵雷达事件调度中的时间窗研究［J］.雷达科学与技术，2010，8(1）:80-86.

［2］李大鹏，何金新，胡云安.资源调度时间窗在垂直发射导弹导引上的应用［J］.导弹与制导学报，2009，29(4）:85-87.

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

［4］王多强，鲁剑锋，李庆华.实时调度中基于多特征参数的任务优先级设计方法［J］.计算机工程与科学，2008，30(1）:73-78.

［5］王永炎，王强，等.基于优先级表的实时调度算法及其实现［J］.软件学报，2004，15 (3）:360-370.

［6］赵洪涛，程婷，何子述.数字阵列雷达波束驻留调度间隔分析算法［J］.信息与电子工程，2011，9(1）:17-21.

［7］陈大伟.相控阵雷达自适应调度算法研究［D］.成都:电子科技大学，2011.