含时间窗的资源调度算法性能分析

万 铮,孟庆鹏

(1. 中国船舶重工集团公司第七二四研究所，南京 211153;2. 海军驻南京地区雷达系统军事代表室，南京 210003)

0 引 言

现代军事战争中，雷达和电子战有着重要的意义，电子侦察也是其中亟待研究的领域。资源调度策略的优劣决定了雷达、电子战系统性能的高下，影响着现代化战争的进程。相控阵雷达资源调度的主要算法有静态优先级的速率单调调度算法、时限单调调度算法、动态优先级的最早截止期优先(EDF)调度算法、最小裕度优先调度算法等[1-2]。这些常规的资源调度策略雷达的系统资源无法充分利用，重点目标和任务无法有效实现。因此，急需一种与目标优先级和时间利用率密切相关的调度策略优化系统性能。

1 强实时系统资源调度策略

现代电子侦察系统的强实时资源综合调度问题，其核心有两点：一是系统各项公共资源的利用效能问题，需要依据系统要求操作的不同功能和任务，调配相应的硬件资源，通过资源合理调度实现整体性能提升，增强软硬件资源利用率，使得任务可以高效完成并有一定的均衡性；二是多样化任务服务可靠性问题，即在系统资源有限的前提下，如何确保任务安全、可靠、持续、稳定地完成，维持整个系统的稳定运转[3]。

对于现今越来越重要的软件化系统而言，资源调度软件需要考虑系统重组的效率。系统的软件可重组包括了软件功能新构和软件故障屏蔽重构。

软件功能新构是软件化系统需要执行一项新任务时进行软件配置到部件运行退出的一系列操作，其流程可用图1表示。

图1 软件功能新构流程图

系统决定执行功能新构时，首先根据决策下达部件配置指令，各部件根据执行功能任务的需求控制相互间数据流向和芯片架构。配置完成后将各部件启动，并对下载传输的任务功能完成初始化。在部件等待时清理过往数据，等待接收新的信息。之后根据决策执行各部件功能算法，将得到的结果储存传输，之后结束功能退出等待下一步指令。

软件故障重组流程则是当系统面对功能更新、部件故障、任务更改等需求时执行的重组操作，其具体流程如图2所示。

监测单元实时监控各部件的故障信息，接收到部件故障情报通过总线上报故障，系统将各个部件的监测单元情报信息收集后进行判断。根据各部件信息计算重组策略。将决策下达至各个部件，部件根据决策重启模块，清空信息等待新的数据流传入，回归正常运行。

系统的硬件平台是资源调度中另一个需要提前考虑的问题。软件化系统的硬件平台需要很强的通用性，由中心处理机控制着包括数字信道化、数字多波束形成到辐射源识别在内的数字信号处理。天线阵列及前端模拟量处理应在规范协议下实现可重构[4]。

因为电子侦察系统超宽带工作的特性，所以有着较高的数据传输速率。这就对各部分硬件的处理速率和数据吞吐量有着极高的要求，同时也要考虑成本的控制和实现难易的问题。图3为软件化系统硬件平台的基本组成框图。

利用光电转换模块进行数字信号传输适合于传输数据量大和易被外界噪声干扰的背景。集成方便、软件化程度高且易于维护和升级的高性能通用计算机可以实现软件控制重组等多种操控。

为适应宽频域、全空域处理带来的海量数据，基于PCI-E和Rapid I/O总线的快速传输网络可以减少处理机的性能限制。结合高速光纤传输网络可以基本满足软件化系统总线高带宽、低延迟支持并行处理、扩展自由灵活的要求[5]。

基于宽带相控阵体制的多功能软件化系统的任务调度可根据系统需执行的不同任务和功能选择不同的调度策略。常用的调度策略有固定模板、多模板、部分模板和自适应调度策，调度的性能随着调度策略复杂度的提升而增加。

(1) 固定模板法

这是最简单直接的一种调度策略。在一个调度间隔内固定分配一系列固定的电子侦察任务组合，分别执行搜索确认跟踪等任务。系统按此流程固定的调度硬件进行序列任务，如图4所示。这种调度策略的设计结构简单，需求系统资源较少，也不需要实时进行任务排序。但是，由于这种算法的固定性限制，导致这种策略仅适用于一些特殊的任务目标，缺乏普遍性和灵活性，无法自动根据任务进行调节，不适合多功能的电子侦察系统。

(2) 多模板法

这是由固定模板法衍生而来的一种调度策略。它摆脱了固定性的局限，增强了策略的多功能适应性。多模板法提前根据面对的环境设计了多个固定模板，在调度时根据一定要求寻找其中最适合的模板，其流程如图5所示。这种调度策略适用在对目标具有一定先验知识的情况下，但若面对的模板数过多则会耗费大量的计算机硬件资源进行搜寻模板的计算，难以满足多功能强实时调度的要求。

(3) 部分模板法

该策略在调度间隔中事先设计了部分电子侦察系统需要完成的任务以保证一些功能的最小程度执行，而对调度间隔中的其余时间则根据其他任务的优先级和约束条件进行调度安排，如图6所示。

这种调度策略相比前两种在系统资源利用率上有较大提升，且对不同的电磁环境有着较强的自适应能力，但在设计和分析策略时较为困难，在多任务多功能强实时要求下仍有缺陷。

(4)自适应调度法

该策略根据不同工作方式优先级条件，在电子侦察系统硬件约束范围内实时响应各种任务功能的驻留请求时间、能力和计算机资源，为每一个调度间隔选择最佳的实时任务调度序列。图7所示是这种调度策略的框图。这种调度策略需要与动态的电子侦察环境相匹配，要符合系统设计条件，在多功能、多任务、强实时需求下的电子侦察系统中具有灵活调度、可自适应、资源利用率高等优点。

2 综合优先级自适应算法

各类资源调度算法在处理不同任务数情况下的资源利用率和调度成功率有明显差异。在任务数较少时，系统调度产生的资源冲突少，各种调度算法都能顺利完成调度。但是，当同时执行多种任务时，资源竞争加剧，只有拥有自适应能力的调度算法可以保持对高优先级目标的精密跟踪。在系统资源趋近饱和时，自适应调度策略可以根据当前任务及资源分配合理提高资源和时间利用率，高效准确地完成各项任务，并能对系统资源做出合理配置。

因此，结合目标威胁度设计一种优先级自适应调度算法对系统的资源调度进行优化。设计时的准则为：

(1) 在同一时间段内申请执行的任务，优先调度综合优先级更高的。当系统硬件资源不足时，首先配置资源给综合优先级高的任务，优先级较低的任务可根据需要进行延迟，任务冲突时优先保证高级别任务执行。

(2) 在系统约束条件下按时间利用率高的方式配置系统公共资源(如式(1)所示)，使调度间隔内执行的任务数量最多，空闲时间最少，任务执行时间总和趋近于调度间隔。

(1)

系统调度得益的评判标准可以由以下几个指标给出：

(1) 任务调度成功率(SSR)(如式(2)所示)是调度成功的任务数与申请调度的总任务数之比，成功率越高则说明调度策略性能越好。

(2)

(2) 实现价值率(HVR)(如式(3)所示)是成功调度任务的综合优先级之和与申请调度任务的综合优先级之和的比值，实现价值率越高说明高优先级任务成功调度越多，优先级调度算法越可靠。

(3)

(3) 时间利用率(TUR)(如式(4)所示)表示成功调度任务的调度时间与总调度时间之比，时间利用率越高则电侦系统资源有效调度效率越高，调度策略性能越好。

(4)

基于数字相控阵体制的电子侦察系统利用数字相控阵多自由度的特点可以执行多种体制功能，针对不同优先级的目标也有相应的应对策略。一般情况下，系统在低优先级搜索中按固定规律对全空域、宽频段进行常规搜索，在高优先级搜索中对特定的空域进行精细搜索，在截获目标后通过系统的信号、信息处理功能对目标识别，根据目标种类和战术需求进行编批、跟踪。对于威胁程度不高的普通目标，系统可以利用较少的资源进行更新率较低的普通跟踪定位。对威胁程度高的目标以较大更新率进行精密跟踪。

侦察系统根据目标的威胁程度进行优先级判定，判定截获信号为高威胁的目标后，会对其进行更高优先级的跟踪、显示；判定为低威胁目标后，会对其进行较低优先级的警戒跟踪。截获目标的威胁度是由目标自身特性决定的，一般以截获信号的脉冲宽度(PW)和脉冲重复频率(PRF)作为判决指标[6]。低重频、宽脉冲雷达信号测向距离远，但需长时间积累，测速能力和抗杂波能力弱，一般应用在远程搜索警戒雷达上，对我方电侦系统威胁度较小。高重频、窄脉冲雷达信号测向、测速精确迅速，一般设计为机载雷达、导弹制导等近目标快速作战装备，对我方威胁程度高，应调度资源对其优先跟踪定位。

设计的算法流程如图8所示。首先初始化调度程序，查询调度申请序列，计算所有申请任务的综合优先级并排序，然后依次执行调度，分析调度结果。

3 时间窗优化策略

现代相控阵系统采用了时间窗优化自适应算法。利用时间窗对存在冲突的任务进行调整调度，从而提高调度效率和时间利用率。若申请调度的任务在一定时间窗内仍未被调度执行，则判断此任务请求失效，送入删除队列处理。利用时间窗调整优先级低的任务占用的调度时间，提高实现价值率[7]。

为了验证有时间窗的综合优先级自适应调度算法的性能，设计了仿真试验，调度间隔为50 ms，高、低优先级任务在一定虚警概率下按固定频率产生。设计的虚警概率为0.001，检测概率0.9，在随机产生的50个目标中有20个需要精确跟踪。将有时间窗和无时间窗的自适应调度算法结果与传统的平均分配型固定模板法作对比得到表1所示。可以看到，采用优先级自适应算法可以在各项指标中获得更优的结果，有时间窗的调度方法在实现价值率上比无时间窗算法有明显提升。

表1 时间窗对资源调度算法性能影响分析

4 结束语

在电子侦察系统作战管理中，综合资源调度系统是任务编排的决策部件。本文提出以目标综合优先级为核心，建立含有时间窗的自适应调度算法。仿真结果表明，该算法在任务安排上合理、有效，具有较高的调度成功率、时间利用率和实现价值率。