ENUMERATING ALL HAMILTONIAN CYCLES IN SOME GRAPHS BY USING THE GENERALIZED FIBONACCI SEQUENCE AND ITS PRODUCTION RULE

1.   引言

相控阵雷达具有波束无惯性捷变和波形自适应能力，可以同时执行搜索、跟踪等多种任务^[1]，相比传统机械扫瞄雷达有着巨大优势。为充分发挥这种性能优势，需要对雷达任务进行自适应调度，以实现相控阵雷达资源的高效分配^[2]。

相控阵雷达任务调度模块主要包含两部分：任务优先级规划和调度策略选取。典型的动态优先级算法是截止期最早最优先(Earliest Deadline First, EDF)算法^[2]，但是只利用一种参数动态确定任务优先级，仍然不够全面。文献[3-5]将工作方式优先级和任务截止期置于同一层面，并引入优先级表的思想来计算任务综合优先级，提出工作方式优先级加截止期算法(High Priority And EDF, HPEDF)及其两种变形算法：修正EDF算法(Modified EDF, MEDF)和修正工作方式优先级算法(Modified High Priority First, MHPF)。然而上述优先级规划算法没有充分利用目标先验信息，且存在人为划定工作方式优先级而导致主观性过强的问题。针对此，文献[6]利用目标信息构建了目标威胁度模型，通过目标威胁度和任务截止期共同确定任务优先等级。在调度策略方面，主要有模板类策略和自适应调度策略，后者更能发挥相控阵雷达的优势。文献[7-9]将时间窗概念引入动态任务调度中，使雷达任务请求的实际执行时刻可以在其期望时间前后移动，有利于提高调度成功率和时间利用率。文献[10,11]采用了任务交错算法，使任务的等待期可以执行其他任务的发射或接收，进一步提高时间利用率。文献[12-15]提出了基于代价或收益的调度算法，构建任务调度的优化模型，并利用二次规划、启发式算法等进行求解。上述研究存在以下问题：一是将任务价值作为一个与任务优先级等价的固定参数，没有考虑任务价值随执行时刻的动态变化；二是没有充分考虑任务调度及时性及其对实现价值率的影响，尤其是对于高价值任务的及时性。

因此，本文提出一种基于价值优化的相控阵雷达任务调度算法。采用跟踪任务竞争时间资源，而搜索任务等待空闲时间片的策略^[16]。首先对跟踪任务进行调度，提出任务调度属性参数，以此判断跟踪任务请求队列可行性；对于不可行队列进行筛选操作，生成新的可行队列。随后建立关于实际执行时刻的动态任务价值函数，并构建基于价值优化的任务调度模型，使跟踪任务尽可能贴近期望时刻被执行，以满足调度及时性原则。其次，利用空闲时间片进行搜索任务调度。最后，通过仿真对本文方法进行验证。

2.   调度算法总体结构

任务调度过程一般以调度间隔(Scheduling Interval, ${\rm{SI}}$)为周期，在一个${\rm{SI}}$中，调度器接收输入端的任务请求队列，进行处理后输出结果是执行队列、延迟队列、删除队列。

相控阵雷达工作在跟踪加搜索(Track And Search, TAS)模式下，所执行的任务种类主要包括两种：跟踪和搜索，且跟踪任务一般比搜索任务优先级更高。跟踪任务对执行时刻要求严格，这是由于期望调度时刻由跟踪采样间隔决定，提前执行虽然能提升相应目标跟踪精度，但是会占用更多时间资源，影响其它任务执行；若延迟执行，则会降低目标跟踪精度，甚至检测不到目标，这意味着当一个跟踪驻留请求的调度被过度延迟时，会导致任务被删除。因此，任务调度过程需要尽可能满足跟踪任务的时间资源要求，并提高其调度及时性。搜索任务属于常驻任务，其驻留请求一般不受时间窗限制，可以持续发送给调度器，未被执行的任务都能够在下一调度间隔继续进入请求队列，被成功调度后依然具备有效性。

根据上述跟踪、搜索任务调度的相关特点，本文采用跟踪任务竞争时间资源，而搜索任务等待空闲时间片的思想，将调度器分成跟踪任务调度器、搜索任务调度器两个子调度器，其总体结构框图如图1所示。

图  1  任务调度模型总体结构

下载: 全尺寸图片 幻灯片

根据该模型，任务调度的总体过程描述如下：首先，跟踪任务请求队列输入到跟踪任务子调度器，输出跟踪任务执行队列、延迟队列和删除队列；随后搜索任务子调度器接收跟踪任务执行队列和搜索任务请求队列，利用执行跟踪任务间的空闲时间片对搜索任务进行调度，生成最终执行任务队列。

3.   跟踪任务调度

3.1   任务模型

在调度间隔$[{t_0},{t_0} + {\rm{SI}}]$内，假设跟踪任务调度模块收到$M$个任务驻留请求，第$i$个任务请求为

其中${P_i}$为任务优先级；${t_{{\rm{e}}i}}$为期望执行时刻；${t_{{\rm{a}}i}}$为请求到达时刻，${t_{{\rm d}i}}$为截止期，因此任务时间窗为$\left[ {{t_{{\rm{a}}i}},{t_{{\rm d}i}}} \right]$; $t{i_i}$为采样间隔；$\Delta {t_i}$为任务驻留时间；$V_i^*$为任务最大价值，当任务在期望时刻被调度时可达到该最大价值；假设任务实际执行时刻为${t_{{\rm{s}}i}}$，当${t_{{\rm{s}}i}}$相对于${t_{{\rm{e}}i}}$提前或者延迟时，分别用${\delta _i}$,${\theta _i}$表示任务价值变化斜率大小，此外${t_{{\rm{e}}i}}$,${t_{{\rm{s}}i}}$应满足

如果${T_i}$在${t_{{\rm{s}}i}}$被执行，那么执行结束时刻为${t_{{\rm{s}}i}}{\rm{ + }}\Delta {t_i}$。由于相控阵雷达在同一时刻只能实施一次驻留，下一任务的执行时刻不能早于${t_{{\rm{s}}i}}{\rm{ + }}\Delta {t_i}$。由此给出以下定义：

定义　对于一个按照执行时刻${t_{{\rm{s}}i}}$由小到大排列的任务队列，当其满足

时，该任务队列是可行的。

3.2   跟踪任务调度流程

本文假设输入的$M$个任务按照期望执行时刻由小到大排列成$\left\{ {{T_1},{T_2}, ·\!·\!· ,{T_M}} \right\}$，即

跟踪任务调度主要分两步，一是判断任务调度属性，即能否被调度，原则是尽可能调度多的任务；二是为能够被调度的任务分配执行时刻，原则是尽可能使任务执行时刻贴近期望时刻。跟踪任务调度模块结构框图如图2所示。

图  2  跟踪任务调度流程

下载: 全尺寸图片 幻灯片

调度流程简要描述如下：

步骤 1　对$\left\{ {{T_1},{T_2}, ·\!·\!· ,{T_M}} \right\}$进行任务调度属性参数计算，并判断其是否可行。若可行，转步骤3；若不可行，转步骤2。

步骤 2　对$\left\{ {{T_1},{T_2}, ·\!·\!· ,{T_M}} \right\}$进行筛选操作，对选出的任务请求，判断其是否满足延迟条件：${t_{{\rm d}i}} \ge {t_0} + {\rm{SI}}$。若满足，将其加入延迟队列；若不满足，则加入删除队列。剩余任务请求形成一个新的可行队列，转步骤3。

步骤 3　对可行任务请求队列进行执行时刻优化分配，得到跟踪任务执行队列。

3.3   任务调度属性参数计算

任务调度属性参数主要包括两方面：最早可能执行时刻$\{ {t_{{\rm{f}}i}}^\prime \} _{i = 1}^M$和最大可能延迟时间$\{ {D_i}^\prime \} _{i = 1}^M$。参数的求解过程如下：

步骤 1　令${t_{{\rm{f}}1}}^\prime $=${t_{{\rm{a}}1}}$, ${D_1}^\prime $=${t_{{\rm{d}}1}}$-${t_{{\rm{f}}1}}^\prime $，设置一个辅助变量$q = 1$, ${S_q} = 1$，且$i = 2$。

步骤 2　令$ {t_{{\rm{f}}i}}^\prime = \max ({t_{{\rm{a}}i}},{t_{{\rm{f}}i - 1}}^\prime + \Delta {t_{i - 1}}) $, ${D_i}^\prime = $${t_{{\rm d}i}} - {t_{{\rm{f}}i}}^\prime $。若${t_{{\rm{a}}i}} > {t_{{\rm{f}}i - 1}}^\prime + \Delta {t_{i - 1}}$，则令${G_q} = {t_{{\rm{a}}i}} -$$ ({t_{{\rm{f}}i - 1}}^\prime + \Delta {t_{i - 1}})$, $q = q + 1$，且$\;{S_q} = i$。

步骤 3　如果$i = M$，令$Q = q$并退出；否则令$i = i + 1$，并转至步骤2。

在上述求解任务调度属性参数过程中，将任务请求队列分成了$Q$个序列，且${S_q}$表示第$q$序列中的第1个任务请求、${G_q}$表示前后两个序列之间的最大时间延迟。

对于任务${T_i}$, ${D_i}^\prime $表示其截止期和最早可能执行时刻之间的差值。用$\{ {D_i}^\prime \} _{i = 1}^M$来判定任务请求队列的可行性：如果对于$\forall i \in \left\{ {1,2, ·\!·\!· ,M} \right\}$，都有${D_i}^\prime \ge 0$成立，则判定$\left\{ {{T_1},{T_2}, ·\!·\!· ,{T_M}} \right\}$是可行请求队列；否则判定$\left\{ {{T_1},{T_2}, ·\!·\!· ,{T_M}} \right\}$不可行。

3.4   任务队列筛选操作

对于不可行的任务请求队列$\left\{ {{T_1},{T_2}, ·\!·\!· ,{T_M}} \right\}$，要对其进行筛选操作，生成一个新的可行队列。筛选操作流程如下：

步骤 1　将原任务序列按照最大价值降序排列得到：$\left\{ {{O_1},{O_2}, ·\!·\!· ,{O_M}} \right\}$。

步骤 2　定义一个任务集合，并将价值最大的任务置于集合中：$C = {O_1}$，且令$i = 2$。

步骤 3　将${O_i}$置于$C\;$中，其在$C\;$中的位置$n$满足：${t_{{\rm e}{C_{n - 1}}}} \le {t_{{\rm e}{O_i}}} \le {t_{{\rm e}{C_{n + 1}}}}$。

步骤 4　对$C$进行任务调度属性参数计算，判断其是否可行。如果可行，则新的任务集合被保留；如果不可行，则对${O_i}$进行分析，确定其是被延迟或删除。

步骤 5　若$i = M$，结束并输出可行集合$C$；否则令$i = i + 1$，转至步骤3。

经过筛选操作，最终得到$\left\{ {{O_1},{O_2}, ·\!·\!· ,{O_M}} \right\}$的一个可行子集，任务最大价值在该过程中起决定作用。${O_1}$一定会被保留，对于其他任务，最大价值越大，对其进行筛选时$C$中任务数目越少，就有更大的可能性被保留。

3.5   任务执行时刻优化分配

3.5.1   任务价值函数

任务执行时刻变化会导致目标跟踪精度的不同，也必然会对任务的实现价值产生影响。因此任务的价值应该是随实际执行时刻动态变化的。本文给每个跟踪任务赋予一个价值函数${V_i}({t_{{\rm{s}}i}})$，大小由实际执行时刻${t_{{\rm{s}}i}}$决定

该函数中，实际执行时刻在时间窗$\left[ {{t_{{\rm{a}}i}},{t_{{\rm d}i}}} \right]$内变动，执行时刻越靠近期望时刻，得到的回波信噪比越大且跟踪精度越高，进而相应的任务实现价值越大。

3.5.2   优化分配模型

任务执行时刻优化分配模块的输入是一个可行的任务请求队列。假设输入队列为$\{ {C_i}\} _{i = 1}^N(N \le M)$，其相关参数$\{ {t_{{\rm{f}}i}}^\prime \} _{i = 1}^N,\{ {D_i}^\prime \} _{i = 1}^N$已经计算得到。${t_{{\rm{f}}i}}^\prime $是${C_i}$的最早可能执行时刻，则所有任务的可能执行时刻可以表示为

其中，${y_i}$是相对于最早可能执行时刻的延迟，要满足以下条件

其中，

${C_i}$在${t_i}^\prime $时刻的实现价值为

其中，${f_i}( \cdot )$表示一个价值变化函数。

所有任务的总实现价值表示为

以该总实现价值最大为目标，进行任务执行时刻的优化分配。

当$ {t_{{\rm{f}}i}}^\prime > {t_{{\rm{e}}i}} $时有

此时${f_i}( \cdot )$表示为一个线性函数

当${t_{{\rm{f}}i}}^\prime \le {t_{{\rm{e}}i}}$时有

因此，当${t_{{\rm{f}}i}}^\prime \le {t_{{\rm{e}}i}}$时${f_i}({y_i})$表达式为

进一步，可将其表示为

其中，

综合式(15)，式(18)，式(19)，得到完整的${f_i}({y_i})$表达式为

根据以上分析，得到基于价值优化的任务调度模型为

其中，$\{ {t_{{\rm{f}}i}}^\prime \} _{i = 1}^N$经过筛选操作已得到且任务价值函数已知(式(6)，式(7))，各任务在最早可能执行时刻的价值${V_i}({t_{{\rm{f}}i}}^\prime )$可以求出。因此，该调度模型的实质是选择约束条件下最优的$\{ {\hat y_i}\} _{i = 1}^N$，使得$\displaystyle\sum\nolimits_{i = 1}^N {{f_i}({y_i})} $达到最大

这是一个线性规划问题，可运用简单的求解方法(例如单纯形法)进行求解。最终得到的任务实际调度时刻可以表示为

该价值优化模型能够使各任务实际执行时刻在满足条件下最靠近期望值，因此该模型的建立体现了任务调度及时性的原则。

4.   搜索任务调度

假设搜索功能包含$P\,$个任务请求，搜索任务优先级一致，且驻留时间都为$d$；此外，有$Q$个空闲时间片按先后顺序构成集合$\{ {\text{π}_q}\} _{q = 1}^Q$, ${L_q}$为时间片长度。在本文中，搜索任务属于常驻请求，根据队列思想，采用先入先出(First In First Out, FIFO)的方式进行调度^[17]。其流程如图3所示。

图  3  搜索任务调度框架

下载: 全尺寸图片 幻灯片

具体描述如下：

步骤 1　设各搜索任务距上一次被调度的等待时间为$\varepsilon $，所有任务按照$\varepsilon $由大到小构成队列：$\{ {\lambda _{hm}}\} _{m = 1}^P$，其中$h$为队列更新次数编号。队列更新次数指针初始化为：$h = 1$。

步骤 2　若$Q{\rm{ = }}0$，则保持$\{ {\lambda _{hm}}\} _{m = 1}^P$不变，等待下一调度间隔；若$Q \ge 1$，则将时间片指针初始化为：$q = 1$，转步骤3。

步骤 3　对${\pi _q}$的时长${L_q}$进行检验，若满足${L_q} < d$，则保持$\{ {\lambda _{hm}}\} _{m = 1}^P$不变，令$q = q + 1$，转步骤4；若满足$kd \le {L_q} < (k + 1)d$，则$\{ {\lambda _{hm}}\} _{m = 1}^P$中前$k$个任务被成功调度，并按照原顺序产生新的任务请求加入队列末尾，形成新任务请求队列$\{ {\lambda _{hm}}\} _{m = 1}^P, $$h = h + 1$，原队列中的${\lambda _{k + 1}}$成为新队列的${\lambda _1}$，且令$q = q + 1$，转步骤4。

步骤 4　判断$q > Q$是否满足，若不满足则转步骤3；若满足，则完成次间隔的搜索任务调度，输出$\{ {\lambda _{hm}}\} _{m = 1}^P$等待下一调度间隔。

5.   仿真验证

5.1   评价指标

通过以下指标来评判算法的性能优劣：

(1) 调度成功率^[3,4]：成功调度的任务与请求调度的任务数目之比

其中，${X_{{\rm{suc}}}}$表示调度成功的任务总数，${X_{{\rm{tot}}}}$表示请求调度的任务总数。

(2) 时间偏移率^[14,15]：成功调度任务的实际执行时刻相对于期望时刻的偏移程度，用以反映任务调度的及时性

(3) 实现价值率：常用的实现价值率指标^[3,4,14,15]将各任务的优先级直接作为任务价值，用成功调度任务的总价值与所有请求任务的总价值相比得到指标值。这只能反映出任务调度成功率以及满足重要性原则的情况，而不能体现任务及时性对实现价值率的动态影响。因此根据文中动态价值函数，对实现价值率进行改进

5.2   参数设置

仿真中对本文算法、MEDF算法^[5]、HPEDF算法^[5]、任务交错算法^[11]的调度性能进行对比。调度间隔50 ms，仿真时长25 s，以目标总数来代表不同的雷达负载情况。目标数量设为：$10,\,20\,, ·\!·\!· ,$80批，高中低价值的目标跟踪任务占比为$5:3:2$，不同价值类型任务的参数如表1所示。每增加10批目标，进行100次蒙特卡洛仿真，取实验平均值。每一个跟踪采样的探测概率设置为1。搜索任务为常驻任务，驻留时间为4 ms，搜索间隔4 s，依编排好的1000个波位构成队列进行调度，仿真开始后按照更新周期产生。此外，搜索任务优先级设为1。

表  1  跟踪任务参数设置

跟踪任务类别	$P$	${V^*}$	$\delta $=$\theta $	时间窗(ms)	$\Delta t$(ms)	$ti$
高价值	4	1000	35	30	2	300 ms
中价值	3	600	10	50	2	600 ms
低价值	2	200	3	60	2	1 s

下载: 导出CSV 

| 显示表格

5.3   仿真结果及分析

图4为4种算法的调度成功率对比。在目标数量超过20批的时候，4种算法的调度成功率都处于下降状态，但是随着目标数量的增加，MEDF算法的调度成功率下降速度最快，而HPEDF算法、任务交错算法和本文算法相对于MEDF优势明显。在目标数目为80批的时候，相对于MEDF算法的调度成功率，本文算法提升了13%，而HPEDF提高了20%，任务交错算法提高了24%。这是由于HPEDF算法能够在尽量减少删除搜索任务的情况下调度更多跟踪任务，而任务交错算法可以充分利用任务驻留等待期，使得其调度成功率相对更高。

图  4  调度成功率对比

下载: 全尺寸图片 幻灯片

图  5  时间偏移率对比

下载: 全尺寸图片 幻灯片

图5为4种算法的时间偏移率对比。MEDF, HPEDF和任务交错算法都没有考虑到及时性因素，随目标数目增加时间偏移率上升速率较快。此外，MEDF优先对截止期临近的任务进行调度，导致时间偏移率最高；任务交错算法为确保交错成功率，会减小执行时刻的偏移程度，其时间偏移率相对HPEDF略低。而本文算法注重任务及时性的满足，在尽可能调度多的跟踪任务基础上，使任务贴近期望执行时刻被调度。因此，本文算法时间偏移率优于另3种算法，当目标数目80批时，相对于MEDF, HPEDF，任务交错算法分别减小了48%, 46%和42%。

图6为4种算法的实现价值率对比。结合图4—图6可以看出，当调度成功率为1的时候，实现价值率并不一定为1，这是由于本文中的任务实现价值率指标不仅与成功调度的任务数目有关，还受到任务及时性的动态影响。任务交错算法的调度成功率和时间偏移率指标都优于HPEDF算法，因此前者的实现价值率高于后者。此外，本文算法在调度成功率略低于HPEDF、任务交错算法的基础上，实现价值率却比后二者更高，当目标数目80批的时候，指标分别提升了12%, 7%。这是由于本文算法更能满足跟踪任务及时性要求；尤其是对于高价值任务，其时间偏移率更低。该结果说明任务及时性的变化对于实现价值率有重要影响。

图  6  实现价值率对比

下载: 全尺寸图片 幻灯片

图7所示为在本文算法中，不同类型任务的实现价值率对比。可以看出，在高价值跟踪任务数目和中低价值任务数目一致的情况下，本文算法对于高价值任务的实现价值率更高，在80批的时候达到了78%，比中低价值任务高47%。这说明本文算法在保证总体调度性能的基础上，注重对高价值任务的调度效果。

图  7  不同任务实现价值率对比

下载: 全尺寸图片 幻灯片

以上仿真结果表明，本文算法相比MEDF算法，HPEDF算法，任务交错算法能够更好满足任务调度及时性；且本文算法能够带来更高的任务实现价值率，对于高价值任务的调度效果尤为明显。

6.   结束语

资源的优化调度是发挥和提升相控阵雷达效能的关键，本文提出一种基于价值优化的任务调度算法，所做的主要贡献和结论如下：(1)构建了关于实际执行时刻的动态任务价值函数，反映出任务价值随调度时刻的变化规律。(2)提出任务调度属性参数，并给出了求解算法，用以判断任务请求队列的可行性。(3)提出一种筛选算法对不可行的任务请求队列进行处理，将部分任务加入延迟或删除队列，并得到新的可行队列。(4)构建了基于价值优化的调度模型，使任务实际执行时刻尽可能靠近期望时刻，满足任务调度及时性原则。(5)改进了实现价值率指标，能更好反映出任务及时性对任务价值的影响。