基于紧时间约束的多功能相控阵雷达任务调度

宋伟强 陈 春 高 剑

(西安电子工程研究所 西安 710100)

基于紧时间约束的多功能相控阵雷达任务调度

宋伟强 陈 春 高 剑

(西安电子工程研究所 西安 710100)

本文阐述了雷达任务的调度问题，定义了两类任务，分为紧时间约束(Hard Time Constraint，HTC)任务和松时间约束(Soft Time Constraint，STC)任务，紧时间约束任务不能延迟执行超过一个固定变量α，而松时间约束任务可以在任意时刻被执行。为解决上述问题，本文详细介绍了一种算法，首先分别建立了HTC任务序列和STC任务序列，接下来针对两类任务序列被调度的顺序问题提出了一种选择原则。

仿真；调度；相控阵雷达

0 引言

现代雷达多使用相控阵天线，它可以瞬间控制和调整雷达波束。这种灵活性使雷达能同时实现多种功能，如导弹制导，跟踪和监视，其中每个功能都进行了大量的雷达任务。多功能的实现需要雷达资源管理的研究，需考虑雷达任务的调度和优先顺序。在过载期间当雷达没有足够的时间预算去调度所有雷达任务时，雷达资源管理显得特别重要。在这种情况下，雷达调度必须决定哪些任务必须执行而哪些任务必须被拒绝,这类问题被称为雷达任务调度问题，它是雷达资源管理的子问题[1]。此外，这类问题决定了雷达任务调度的起始时刻和执行顺序。

本文将重点研究在考虑紧时间约束和优先级情况下的雷达任务调度问题。系统的物理性(例如波形计算和信号处理)不予考虑。为了解决这类问题，首先分别建立了HTC任务序列和STC任务序列，接下来针对两类任务序列被调度的顺序问题提出了一种算法。

1 紧时间约束和优先级的调度问题

对于多功能雷达系统，有几种类型的任务要处理(图1)[2]。其中一些是定期的：监视，跟踪，武器制导等，还有一些是不确定的：确认，分类等。本文重点研究防空雷达系统。雷达必须进行对空搜索以便检测目标，总搜索量可以看作是m行和n列的二维矩阵，矩阵的每个元素代表对应的波束位置，每个波束位置关联一个监视任务。当目标被检测到，雷达将会对它实施跟踪，系统控制台将会发出拦截请求，并且在每个拦截请求中都有武器制导任务(对于同一个目标而言可能拥有多个拦截请求)。在拦截结束后，杀伤评估任务将被用来确定目标是否被摧毁。可见任务类型之间有明确的优先级结构。

详细的说，一个定期任务想要每θi秒执行一次。这意味着一个任务被获取后最佳表现是该任务恰好在θi秒内被执行，其中该任务的最后一次重复记为起始时刻si，那么该任务的截止时刻oi即为起始时刻si与执行时间θi的和。尽管oi是任务Ti的截止时刻，但是Ti没有必要在oi时被执行。如图2所示，任务Ti在oi之前被调度，增加了系统负载导致任务Ti的性能降低；在oi时被调度或者在oi之后被调度，虽减小负载但是更降低了Ti的性能。另一方面，一个不确定任务必须恰好在一段时间内被执行，所以一个不确定任务可以用创建时刻ci和截止时刻oi表示。但是相比于定期任务，不确定任务可以在截止时刻之前、截止时刻或截止时间之后被执行。

对于本文所提问题，任务被分为两类。第一类定义了紧时间约束(HTC)任务。这类任务不能延迟执行超过一个固定变量α，且不能在截止时刻oi之前被执行。这意味HTC任务必须在区间[oi,oi+α]内开始执行，否则任务被拒绝(图3)。对于HTC任务，这一约束将会带来很高的跟踪精度。例如，导弹制导就是HTC任务。第二类定义了软时间约束(STC)任务。这类任务可以在任意时刻被处理，但是越延迟任务的处理，任务的性能会越低。例如，搜索任务就是STC任务。

如前所述，任务类型之间有优先级结构。这意味着，如果在过载期间，系统宁愿继续跟踪目标而不是试图发现新的目标，这说明跟踪任务相比于搜索任务有更高的优先级。而且在相同类型任务之间同样存在优先级结构。例如，在跟踪敌对目标上的任务优先级要高于跟踪友好目标上的任务优先级。

通过上述对雷达任务的描述，本文将定义以下雷达任务参数：

表1 雷达任务参数

任务最后一次重复的开始时刻si(定期任务)ci(不确定任务)执行时间pi截止时刻oi完成时刻di=oi+pi+α(仅适用于HTC任务)优先级wi

本文理论上讨论的是实时任务调度问题。事实上，雷达系统通过对任务的处理来监视空域，每次任务的处理都会发生环境的变化。由此可见，环境是动态变化的，并且随着任务的出现、消失或更新而改变。但在实际中，雷达系统的任务调度是建立在框架内的，在建立框架之前，我们固定环境变量。这意味着，在一个框架的构造期间，环境是固定的，它将在下一个框架构造之前更新[3]。

2 松时间约束任务序列的确认

前文提到，STC任务可以在任意时刻被处理，但是越延迟他们的处理，任务的表现会越低。因此，在本节中，我们将根据其截止时刻和优先结构对STC任务进行排序(见图4.确认STC任务序列概述)。

存在某任务晚于截止时刻(即当前时刻大于该任务截止时刻)，那么如果一个计划任务在截止时刻之前执行，不仅没有增加该计划任务的性能，而且增加了这些后期任务的延迟降低它们的表现。

利用上述约束，我们定义了一个规则用以确定STC任务序列。那么，首先将STC任务根据其截止时刻降序排列，然后把该顺序分成两个子集。第一组称为“紧急状态”包含的为晚于他们截止时刻的任务，第二组称为“非紧急状态”包含的任务为不晚于截止时刻(即如果没有这些晚于截止时刻的任务，这些任务将被执行)。这个区分是用当前时刻t值来完成的，所以如果一个任务的截止时刻大于或等于当前时刻，则该任务处于“紧急状态”，否则就是“非紧急状态”。

当雷达系统过载时，寻找两类任务间优先级最高的任务进行调度[4]。因此，在“紧急状态”的任务根据他们的优先级进行降序排列，在“非紧急状态”的任务根据其相对延迟降序排列(即依据pi/(oi-ai)的大小降序排列)，通过调度这类任务来使局部过载最小化。

3 紧时间约束任务序列的确认

为确认HTC任务序列，我们将依据被拒绝任务最大优先级的数量最小化的原则安排任务的执行顺序。正如前文提到的，HTC任务不能延迟处理超过固定变量α，且不能在截止时刻之前被执行。所以，HTC任务必须在区间[oi,di]内开始执行，否则该任务被拒绝。

文献[5]中指出调度时刻表的标准形式：存在索引j,0≤j≤n-1，标准形式的调度顺序开始于任务T1,T2,…Tj，接下来的执行顺序为Tn,Tj+1,Tj+2,…,Tn-1，尽可能的减少无意义的时间。需要说明的是，标准形式定义的任务序列依据它们的截止时刻増序排列。

首先定义SF(i,t)为任务T1,T2,…Ti子集标准形式的排列顺序，其中每个优先级任务的数量包含在数组t中。例如，如果SF(i,t)任务优先级的顺序为(1,3,5,3,4)，那么t为[1;0;2;1;1]。定义C(i,t)为SF(i,t)顺序中每个任务尽可能被调度的情况下任务的完成时间。从标准形式的定义知，SF(i,t)由SF(j,t′),0≤j≤i-1和Ti,Tj+1,Tj+2,…,Ti-1组成。

a)l=0:

b)l=1:

c)l≥2:

对于任意t值，当全部序列SF(i,t)和全部值C(i,t)已知时，那么当前迭代i已完成。通过迭代i直到i=n，使序列中所含任务最大优先级增至最大时，HTC任务序列就可以通过SF(n,t*)获得，其中t是最优解，C(n,t*)≠+。需要注意的是，在t1=[0;1;2;1;3]和t2=[0;0;1;2;3]两解中，t2优于t1。因为t1执行3个优先级为5的任务和一个优先级为4的任务，而t2执行3个优先级为5的任务和2个优先级为4的任务。

4 算法和仿真结果

4.1 算法

正如前文所述，雷达任务调度是实时调度，但实际上是使用框架来进行雷达任务调度。这种方式对于任务调度顺序给予了一定的灵活性，因为只要框架的构造还没有完成，那么仍有可能改变包含在框架内任务的执行顺序。另一方面，这种方式对于环境变化有延迟，因为当我们建立现有框架时，雷达天线调度先前的框架。此外，环境的更新仅发生在一个框架构造之前。所以，当一个框架被执行时，环境的改变由于框架的执行并没有包括在下一个框架构造的系统中(下一个框架的构造发生在当前框架被执行期间)。但是在下一个框架之后将会充分考虑环境因素。

我们的调度算法必须构造这些框架。当一个框架开始构造时，将使用在先前章节确认的STC任务序列和HTC任务序列，即STC任务序列和HTC任务序列作为算法的输入。之后结合这两类序列去建立框架。所以，本文提出算法必须决定两类序列中被首批执行的任务，哪类任务将首先进入到框架中。

因为在HTC序列中的任务不能它的截止时刻之前被执行，所以在插入框架之前，我们必须判断当前时刻是否大于某HTC任务的截止时刻。这个限制将会用于决定两类序列首批被执行任务中，哪类任务将首先进入到框架中。当任务被插入到框架时，该任务在当前时刻将会执行，随后我们将通过增加任务的执行时间来更新当前时刻。当框架构造完成，任务调度停止。(图6.算法说明概述)

4.2 仿真结果

最后针对侦察范围为方位[-45°，+45°]俯仰[0°，70°]的多功能相控阵雷达，我们搭建了类似仿真平台，得出仿真结果。对于这种相控阵雷达，跟踪任务相比于搜索任务有较高的优先级，所以当系统的全部负载超过100%时，搜索任务将会在跟踪任务之前被延时。

讨论多功能相控阵雷达的搜索范围是以便发现目标。仿真中主要考虑两类目标：敌对目标和友好目标。其中敌对目标会被判定为HTC任务，而友好目标会被判定为STC任务。敌对目标将会在Xms且不超过α的时间内被调度，而友好目标会每Y秒被调度一次。敌对目标的优先级固定为wx，而友好目标的优先级被固定为wy，wxgt;wy。

在仿真期间，如果某敌对目标的跟踪任务被拒绝(即该任务在Xms且不超过α的时间内被执行、系统过载或者有太多HTC任务共享时间区间[oi，di])，那么任务的执行时间将增加Xms，任务的优先级增加1，之后该任务带着这些新参数插入到系统中。当该任务被调度时，它的参数将会被重新定义执行时间Xms和优先级wx。

跟踪敌对目标的执行时间会被作为系统表现的评估标准，这意味着每2Xms跟踪两个敌对目标的系统表现好于每Xms跟踪一个敌对目标，另一个目标每3Xms跟踪一次。

本文进行了两类仿真，第一类仿真(SHTC)使用的是本章节第一部分介绍的算法，跟踪敌对目标划为HTC任务。第二类仿真(SSTC)使用的是一种典型算法，跟踪敌对目标划为STC任务：每个敌对目标每Xms被跟踪一次，优先级为wx，划为STC任务。如果该STC任务被执行时刻超过最大延迟变量α，那么该任务被拒绝并且参数将会更新(它的处理时段增加Xms，优先级增加1)，当该任务再被执行时，它的参数被重新定义为每Xms处理一次，优先级为wx。

图7、图8分别呈现了SSTC仿真和SHTC仿真针对敌对目标跟踪任务的重复执行时间。SHTC的仿真结果显示多功能相控阵雷达利用本文提供的算法同时跟踪四个敌对目标所能达到的最大重复时间为2Xms。而SSTC达到了3Xms。由此可得结论，本文提出的算法在保持很高跟踪精度的前提下管理高优先级目标方面明显好于典型算法。

图9是图10在[x,x+α]时段和[2x,2x+α]时段的放大图。图10说明了搜索任务的重复执行时间。从图中可以明显看出三个负载状态：满载，过载，欠载。第一阶段即为满载状态，系统的全部负载为100%。在第一阶段，目标还没有判定为敌对目标，它们被认为STC任务进行跟踪。第二阶段系统开始出现过载，目标被判定为敌对目标，当目标为敌对目标时，系统将每Y秒重复一次的STC任务转为每Xms重复一次的HTC任务。因为Xlt;Y，每一次目标都被定为敌对目标，系统的负载增加，然而，在第二阶段系统负载的增加是逐步的。第二阶段结束，目标被摧毁。因为仅有搜索任务被调度，雷达的负载减小，出现最后一个阶段，欠载状态。在这一阶段，任务在它的截止时刻之前被调度。

5 结束语

在本文中，我们讨论了雷达任务调度问题，要求在保持高跟踪精度的前提下率先执行优先级较高的任务，然而这些任务必须在[oi,oi+α]内被调度。为了解决这类问题，定义了两类任务：紧时间约束(HTC)任务和松时间约束(STC)任务，确认每类任务的执行顺序，首先STC任务依据其截止时刻降序排列，然后将任务分为两个子集，最后根据优先级顺序重新排列每个子集中任务的顺序；对于HTC任务序列，我们提出了利用调度时刻表的标准形式动态确认任务的执行顺序。最后将这两类任务序列作为输入，结合这两类序列构建框架，被采用的操作即位雷达要执行的任务。在每一步中，通过当前时刻与HTC任务截止时刻相比的原则决定排列在这两类序列中被首批执行的任务谁先被调度。基于仿真结果可以验证，相比于传统算法，本文提出的算法对于多功能相控阵雷达任务的调度具有一定的优越性。

[1] 侯泽欣.多功能相控阵雷达资源调度理论与方法研究[D].中国舰船研究院.2013.

[2] Q. Zheng, P. Baptiste, and F. Barbaresco.On scheduling a multifunc-tion radar with duty cycle budget. International Conference COGIS’09 (COG nitive systems with Interactive Sensors). 2009.

[3] 冀琛.对相控阵雷达工作模式的资源调度研究[D].现代防御技术.2014.

[4] P.W. Moo.Scheduling for multifunction radar via two-slope benefit functions.IET Radar Sonar Navig, 2011, 5(8):884-894.

[5] 胡晓培.相控阵雷达数据处理和资源调度仿真[D].西安电子科技大学. 2015.

[6] 卢建斌,席泽敏.一种基于IMMKF的相控阵雷达波束调度算法[D].海军工程大学.2014.

HardTimeConstraintBasedTasksSchedulingforaMultifunctionPhasedArrayRadar

Song Weiqiang, Chen Chun, Gao Jian

(Xi’an Electronic Engineering Research Institute, Xi’an 710100)

Scheduling of radar tasks is described, two types of tasks are defined: hard time constraint (HTC) task, and soft time constraint (STC) task. Execution of HTC tasks cannot be delayed for more than a fixed constraint , STC tasks can be executed at any time. An algorithm is presented for this purpose, sequence of HTC tasks and sequence of STC tasks are made, then a selection rule to determine scheduling sequence between these two kinds of tasks is presented.

simulation; scheduling; phased array radar

2017-05-30

宋伟强(1990-)，男，硕士研究生。研究方向为信号处理技术。

TN958.92

A

1008-8652(2017)03-006-05