基于二次规划优化算法的雷达自适应调度研究

彭新家，栾铸徵

(中国船舶重工集团公司第723研究所，扬州 225001)

基于二次规划优化算法的雷达自适应调度研究

彭新家，栾铸徵

(中国船舶重工集团公司第723研究所，扬州 225001)

建立了雷达任务数学模型，介绍了几种常用的资源调度方法，对其中的自适应调度算法进行了分析。在此基础上，提出了一种基于二次规划的自适应调度优化算法，分别对其与有时间窗自适应算法进行仿真，然后对比，得到了比传统自适应算法更优的结果。

雷达任务数学模型；自适应调度；时间窗；二次规划

0 引 言

相控阵雷达是目前被广泛研究和应用的雷达。传统雷达大多数情况下是通过电机来实现机械扫描，而相控阵雷达则可利用电子扫描来实现波束在方位和仰角同时扫描，且辐射波束可以在很短的时间内改变波束指向。因此，相控阵雷达可以同时兼具实时搜索、跟踪和制导多目标的能力，使传统雷达发展模式有了质的改变。在相控阵雷达体系中，工作时间、能量、信号处理单元等资源是有限的，需要对目标搜索、跟踪、制导等多任务进行重新动态分配。除此之外，雷达系统的资源还受其他环境因素的影响，如雷达自身工作产生的热噪声，跟踪目标的类型、速度、数量、距离、机动性，以及雷达自身有限的能量等，这些都会动态影响雷达资源去执行相应的任务。相控阵雷达资源管理是一项非常复杂、严格且必不可少的工作，它已不能仅凭借操作人员的经验或者通过事先直接分配来进行。因此，对相控阵雷达资源管理理论进行研究，分析波束驻留调度算法以及自适应资源分配算法，实现有效、实时、动态的雷达系统资源管理，以提高相控阵雷达系统的整体作战效能，是一项有十分有意义的研究工作[1]。

1 相控阵雷达任务调度研究

1.1 雷达任务数学模型

在雷达任务数学模型中，首先定义一个雷达调度间隔(SI)。在1个SI内，这个任务数学模型可定义为[Ti，pi，tei，ηi，Δti，tsi，tfi，tli]。其中pi表示任务Ti的任务优先级，tei表示任务Ti的期望执行时间，ηi表示任务Ti的调度属性(或直接执行，或延迟，或删除)，Δti表示任务Ti的驻留时间，tsi表示任务Ti的实际执行时间，任务Ti时间窗区间[tfi，tli]中，tfi表示任务Ti的最早可执行时间，tli表示任务Ti的最晚可执行时间，时间窗tw=tli-tfi。上述定义中，优先级用阿拉伯数字表示。其数值越大，代表任务的级别越高。驻留时间代表任务执行的时间长度[2]。

1.2 相控阵雷达任务优化调度模型

在同一个时间槽内，如果出现多个任务进行竞争，这就表示各个任务彼此之间出现了冲突，需要对调度进行优化。在对相控阵雷达任务调度优化算法进行研究时，通常情况下需满足下面几个设计原则：(1)优先级原则；(2)不重叠原则。同时，时间资源、能量资源和计算资源等几种资源的约束在分析和设计调度策略时也必须考虑。

在雷达任务调度中，满足上述几个设计原则和资源约束条件是前提，而最终的目的却是使雷达任务调度成功率和时间利用率尽可能地高。因此在进行调度时，首先要确定雷达任务的调度属性ηi，然后是调度出雷达任务的实际执行时间tsi(要使调度时耗费的时间资源、能量资源和计算资源最小)。这是一般的任务调度流程。

1.3 资源调度策略

相控阵雷达的任务调度，通常根据雷达系统的不同作用方式以及功能特性来选择不同的调度策略。一些简易的策略诸如固定模板、多模板、部分模板和自适应调度算法在开始研究任务调度时被广泛拿出来进行研究。这4种策略的调度性能和效率逐渐增加，但同时其复杂度也变得越来越高[1-2]。

其中，固定模板法是在事先设定好的一个调度间隔内对雷达事件执行调度任务。该方法消耗资源较少，但同时该方法缺乏灵活性，且自适应性比较差，仅能适应功能单一的特定雷达。多模板法顾名思义是有多个模板，提前设定好，然后使每种模板均能在这些特定雷达环境下适用。该方法比固定模板法更加灵活，但不利于系统调整及状态更新，且增大了系统资源消耗。所以该方法仅适用于对目标环境有一定先验知识的情况下进行雷达任务调度。部分模板法是结合了固定模板法，将某些固定模板嵌入到雷达任务的SI内，并且同时给其他突发事件在SI内预留空余的时间。该方法与前2种方法相比，适应性更强，效率更高，但设计较复杂，故只能适用于某些特定功能的雷达。基于前3种策略较为简易，本文主要对第4种算法进行深入分析和仿真验证。

2 自适应调度算法

雷达任务的自适应调度是根据各个任务的tei确定其tsi的过程。在这个过程中，会对任务的时间、能量和计算等资源进行重新分配。下面开始介绍无时间窗自适应调度算法和有时间窗自适应调度算法[3-4]。

2.1 无时间窗自适应调度算法

无时间窗表明雷达任务的tsi与tei保持一致，提前或者延迟在这种调度中是不被允许的。任务出现竞争时，pi值较大的任务被执行，而pi值较小的则被删除；pi值相同时，tei较早的执行，同样较晚的会被删除。由于在该算法中大量雷达任务被删除，整个系统的资源利用率、作战效能都会降低。

2.2 有时间窗自适应调度算法

在有时间窗自适应调度中，雷达任务的tsi可以在tei周围进行提前或延迟执行。这个“周围”就是指的tw，tsi在tw内。

首先，建立雷达任务模型如下：

(1)

可知，被成功调度执行的雷达任务的最终实际执行时刻是在[tei-tw，tei+tw]之间。其中，tw表示时间窗。

在满足上述3个原则的基础上，有时间窗自适应调度会将雷达任务请求分别送进执行列表、延迟列表和删除列表中。

执行列表中，pi值较大的雷达任务其tei也相应较早。即：(1)ΔTi+TEQ≤IS， ΔTi是指第i个雷达任务请求的波束驻留长度，而TEQ是指执行列表中已调度任务的波束驻留长度之和；(2)max(t0,tei-twi)≤tsi≤min(tei+twi,t0+IS-ΔTi)，其中t0表示调度间隔的起始时刻，twi表示第i个雷达任务请求的时间窗长度；(3)min(tsj-tsi)≥ΔTi,j∈{j|tsj>tsi}；(4)上文提到的时间利用原则也需尽量满足。

延迟列表中，pi值较大的雷达任务其tei也相应较早，即：(1)不满足执行列表中的约束条件；(2)tli满足在下一个SI内执行。

删除列表中的雷达任务：(1)不满足执行列表和延迟列表的约束条件；(2)tli不满足在下一个SI内执行[5]。

2.3 自适应调度算法仿真

针对上文分析的有时间窗自适应调度算法，本文对其进行了仿真。

为了验证自适应调度算法的正确性与合理性，本文设定了多任务请求抢占同一执行时间的仿真场景，任务量饱和。对此，选择了6种雷达事件，分别为搜索、低级跟踪、中级跟踪、失搜、高级跟踪和确认，选择的时间间隔IS=50ms，仿真得到的任务请求时序图和调度结果时序图如图1所示。其中，时序图中的矩形框表示雷达任务请求，矩形框的高度表示任务的相对优先级(优先级1～6)，宽度表示事件的驻留时间。由调度结果时序图可知，当不同雷达任务的期望执行时间发生冲突时，调度会选择相对优先级较高的任务优先执行，而相对优先级较低的任务则在时间窗允许范围内调整实际执行时间，部分无法调整的任务会被删除。

图1 多目标的有时间窗自适应调度算法的时序图

3 基于二次规划的自适应调度算法

二次规划是一种优于常规自适应算法、解决非线性优化问题的算法，已应用于很多方面的非线性问题。通过对比分析，二次规划算法自身有以下几个特性且可进行应用：(1)二次规划算法的目标函数是二次实函数，且其约束条件为线性约束，这样就方便进行求解。(2)对于二次实函数，若其在可行域内连续，则由连续函数最大值和最小值定理：在有界闭域内的多元连续函数，其一定有最大值和最小值。这就可以证明二次规划的目标函数在可行域内连续的条件下其最优解在可行域有界闭域时是一定存在的。(3)如果二次实函数的Hesse矩阵正定，则该二次函数为凸函数，且其最优解存在且唯一。

由此可知，二次规划算法已经在大量工程实际中应用，而本文研究的雷达任务优化调度可通过提出相应的自适应调度算法[6]进行运用。

3.1 雷达数学模型

对于集合T中的2个任务T(p-1)和T(p)，当优化准则选择为加权的时间偏移量平方和最小时，所建立的优化模型如下：

(2)

式中：Ei为调度间隔内任务调度消耗能量；第i个事件的最佳时间偏移量dti=tsi-twi；pi为第i个事件的优先级。

雷达任务的相对优先级用目标函数中的权值来表征，这表明对于同一时间偏移量，pi越高的雷达任务，其对应付出的代价、消耗的资源也就越大。合理选择约束条件，就可以使优化模型中的几个任务之间不存在冲突的情况[7]。

3.2 优化调度算法分析

首先，在定义的周期T中，将雷达任务按pi排序，如果pi相同，则将其按tei排序，组成待调度队列T={T1，T2，…，TN}。接着定义2个不参与调度分析的端点任务T0和TN+1，设定其pi为最高，同时令tf0=tw0=tl0=ts0=t0，Δt0=0和tf(N+1)=tw(N+1)=tl(N+1)=ts(N+1)=t0+IS，ΔtN+1=0成立。

可以假定当调度到第k步，先从待调度队列T中取出雷达任务Ti。并设此时已有M(M≤k)个已确定调度的雷达任务，再算上2个自定义的任务T0和TN+1后，组成新的调度队列T={T0，T1，…，TM，T(M+1)}，而且调度执行时间满足ts0≤ts1<…

前文的连续函数最小值和最大定理已经提到，二次规划的目标函数的最优解在可行域是有界闭域时一定存在，仅需确保可行域为有界闭域。

判断调度属性时，在满足约束条件的前提下，就是要使雷达任务Ti的tei前面的任务T(p-1)尽可能前移，而后面的任务T(p)则尽可能延迟即后移，假使空余出的时间间隔大于雷达任务Ti的驻留时间，则将雷达任务Ti插入至调度雷达序列T中。

3.3 基于二次规划的自适应调度算法仿真

为验证基于二次规划的自适应调度算法的正确性与合理性，本文同样设定了多任务请求抢占同一执行时间的仿真场景，任务量饱和。选择了6种雷达事件，分别为低优先级搜索、高优先级搜索、普通跟踪、精密跟踪和确认，任务请求时序图和调度结果时序图如图2所示。

图2 基于二次规划的自适应调度算法的时序图

对比常规的有时间窗自适应调度算法与基于二次规划的自适应调度算法，上文对这2种算法分别仿真，得出了调度后时序图的仿真结果。其中，2种算法均选择了6种雷达事件，分别为搜索、低级跟踪、中级跟踪、失搜、高级跟踪和确认，选择的时间间隔SI均为50ms，优先级均为1～6，任务时间设置均为300ms，任务负载均在100%以上。由图1和图2可知，经过基于二次规划的自适应调度算法的任务调度的调度成功率相对于常规的有时间窗自适应调度算法是更高的。常规的有时间窗自适应调度算法的调度成功率SSR接近74%，但基于二次规划的自适应调度算法的调度成功率SSR达到了83.7%，调度成功率提高了接近10%，调度成功率改善较显著。

4 结束语

本文主要针对二维相控阵雷达资源管理以及任务调度问题，展开了一系列研究，阐述了常用的资源优化方法，介绍了资源调度策略，建立了基于二次规划的自适应调度算法下相控阵雷达任务调度数学模型，并对其优化策略算法进行了仿真分析，与自适应调度算法相比，任务调度率提高，验证了算法的有效性，为相控阵雷达资源管理提供了一种实现方法。

[1] 丁鹭飞，耿富录，陈建春.雷达原理[M].北京：电子工业出版社，2014.

[2] 赵宇.相控阵雷达资源优化管理[D].上海：上海交通大学，2012.

[3] 毛依娜.相控阵雷达在跟踪模式下的资源管理及任务调度研究[D].西安：西安电子科技大学，2011.

[4] 李倩.多功能相控阵雷达跟踪及调度算法研究[D].西安：西安电子科技大学，2011.

[5]WASHBURNR,SCHNEIDERM,FOXJ.Stochasticdynamicprogrammingbasedapproachestosensorresouecemanagement[C]//Proceedingof5thInternationalConferenceonInformationFusion,2002:608-615.

[6] 陈永森，徐磊.一种基于二次规划法的雷达资源调度方法[J].舰船电子对抗，2015,38(6):18-20.

[7] 卢建斌，胡卫东，郁文贤.多功能相控阵雷达实时任务调度研究[J].电子学报，2011，34(4):732-736.

Radar Adaptive Scheduling Research Based on Quadratic Programming Optimized Algorithm

PENG Xin-jia，LUAN Zhu-zheng

(The 723 Institute of CSIC，Yangzhou 225001，China)

This article founds the mathematical model of radar task,introduces several common methods of resource scheduling,and analyzes the adaptive scheduling algorithm.On this basis,the article puts forward an adaptive scheduling optimized algorithm based on quadratic programming,separately simulates the algorithm and the adaptive algorithm with time window,then compares the simulation results,and gets a simulation result which is better than traditional adaptive algorithm.

mathematical model of radar task；adaptive scheduling；time window；quadratic programming

2016-04-13

国家国际科技合作专项项目，项目编号：2015DFR10560

TN958.92

A

CN32-1413(2016)06-0058-04

10.16426/j.cnki.jcdzdk.2016.06.013