基于机器学习的认知雷达资源管理

杨洁 李国腾 曾耀平

摘 要：现代雷达可以设计成多种功能，如监视、跟踪和火灾控制。每个功能都要求雷达执行许多收发任务。这就出现了将雷达资源分配给不同任务的问题。具体而言，雷达资源管理（RRM）模块对这些任务的参数选择、优先级和调度进行决策，在超负荷情况下，RRM变得特别具有挑战性，有些任务可能需要延迟甚至放弃。随着多通道雷达变得越来越智能，大大提高了执行任务的能力，但它也使任务调度复杂化。之前的研究选择使用分支和约束（B&B）方法来解决这一问题。文章使用B&B方法的结果来训练一个基于机器学习的调度器，通过使用神经网络估计搜索树节点的值来加快B&B方法。结果表明，使用神经网络结合B&B方法得到了一个接近最优解，同时显著降低了计算复杂度。

关键词：机器学习;认知雷达;分支定界法

0    引言

认知雷达（CR）被定义为一种进行智能信号处理的雷达，它建立在通过雷达与周围环境[1]的交互学习的基础上。CR的关键要素是通过观察获取知识，并在实际决策中使用这些知识。本文考虑了一种多功能认知雷达（MFR）中雷达资源管理（RRM）的方法。

MFR通过执行一些收发任务来处理各种功能，如广域监视和跟踪多个目标在这种情况下，可用的雷达资源，特别是时间、频率和能量，需要以有效的方式分配给不同的任务。RRM模块对[2]参数选择、优先级和任务调度进行决策。通常，在某些过载情况下，任务数量超过MFR的能力，其中一些任务可能需要延迟甚至放弃，因此RRM变得特别具有挑战性。

目前已经开发了多种技术用于多功能雷达的资源管理[3-4]，由于是RRM，任务调度通常是一个NP难题，需要考虑的一个共同主题是将RRM分为两个步骤[2]。第一步是确定任务参数，例如优先级、停留时间和重访间隔，方法是针对每一个任务单独使用基于规则的方法，或者在考虑所有任务的情况下，通过对所有任务进行联合优化来实现整体效用函数资源约束[3]。确定参数后，第二步是任務选择和调度。在选择阶段，根据资源限制选择任务的子集，并制定绩效因数，其余的任务被删除。在调度阶段，将时隙分配给任务，以上步骤也可以反复迭代以提高性能。

在单独的轨道上，多通道、多频率雷达变得越来越可行。多通道雷达带来了在不同信道上同时执行多个任务的可能性。然而，这种额外的能力也使已经困难的RRM问题复杂化。除了调度外，任务现在必须分配给通道。本文考虑了多通道多功能雷达的联合资源管理问题，即一个能够同时执行多个任务的联合雷达。在考虑多通道雷达的RRM时，本团队以往都是使用的最优的分支定界（B&B）技术[5]。但是，正如任何NP难问题的解决方案都必须考虑指数计算复杂性，并且对于任何超出任务列表的事情，都不能期望它可以实时执行。由于需要平衡性能和复杂性，本文将机器学习（ML）技术引入到多通道MFR的RRM问题中。本研究的ML方法学习了以前执行的B&B算法（在训练阶段）。然后将所获得的知识用于未来的调度问题。具体来说，本研究使用神经网络来估计B&B方法中与节点相关的值，从而收敛到接近最优解，同时显著地减少了计算负担。该值是从给定节点开始可以获得的完整解决方案的最小成本，并且如果它离最优解太远，则从树中消除节点及其子分支。

使用监督学习对神经网络进行训练。通过运行得到训练数据集（标记数据），B&B算法离线处理相对较小的问题，生成的训练数据使本研究能够训练卷积神经网络，本研究的仿真结果表示，计算负载的性能损耗低。

1    问题分析

问题如下：本研究考虑在一个时间窗口内，在K个相同的通道上执行N个任务。任务可以在不同的通道上同时执行，但不能在给定的时间轴上重叠。此外，本研究考虑了非抢占式调度场景，其中正在运行的任务直到完成才停止。对于每个任务，都有一个起始时间rn，之后才可以执行任务。还有一个截止时间Dn，在此之后，任务被删除。这第n个（1≤n≤N）任务的执行时间（驻留时间）用ln表示。

例如，考虑一个跟踪任务。任务的开始时间由所需的跟踪精度和最后一次测量的时间决定。截止时间取决于雷达的波束宽度和目标的估计轨迹。在假定目标已从雷达波束中移出后，该任务将不会执行，因此，它被丢弃将产生一定的成本，所以，需要采取进一步措施来补偿下降。

一个计划的但延迟的任务的延迟成本在这里被建模为与延迟成线性比例，令en为任务n开始执行的时间，延迟成本由ωn（en-rn）给出，其中ωn为衡量延迟的权重。让二进制变量xnk表示任务n是否在第k个时间轴上调度（=1）。如果xnk=   0k，则删除任务n。然后第n个任务相关的成本为。本研究的联合任务选择和调度问题是总成本C的最小化，由下式给出：

在此，优化变量是xnk和en。如果计划了任务，即xnk=1，对于一些k，则还需要确定执行时间en。因此，本研究的优化问题是：

第二个约束，确保在计划时将任务仅分配给单个时间轴。没有任务丢失的调度问题是NP难题[6]。可以看出，联合任务的选择和调度也是NP难题。

2    解决方法

在公式（2）[5]中，可以采用B&B过程来找到问题的最优解。B&B方法的主要缺点是执行时间，在任务数量上可能是指数的。执行时间取决于任务参数，B&B过程是重尾的，也就是说，虽然许多执行在合理的时间内是可能的，但有一些情况需要一个较长的执行时间。为了降低B&B算法的复杂度，本文提出了一种利用神经网络加速搜索的近似方法。

B&B方法隐式地列举了搜索树上所有可能的解决方案。树的根节点表示整个解决方案空间。其余节点与解空间的子集相关联。分支操作将父节点的空间分割成结果子节点的子空间。每个子空间表示部分解。在搜索过程中，使用边界和优势规则从树中消除节点。除了这些规则外，本研究还建议使用神经网络来促进从搜索树中消除未产生的节点。一旦对整个树进行了遍历，就会返回搜索中找到最佳解决方案。

对于公式（2）的问题，该树的每个节点代表一个部分调度，包括任务的子集。本研究搜索任务的最佳执行时间，可以变换为搜索任务的最佳排列。本研究通过以下方式构造搜索树。根节点为空序列，一个分支代表选择还没有被安排在父节点和其限期尚未通过的任务。所选任务将附加到父节点的序列中，以获取结果子节点的序列。使用“序列到计划的映射”[5]获得计划，该计划在序列的元素上进行迭代，并将每个任务放在最早可用的时间轴上。使用这种技术，寻找最佳序列。

优势规则是特定于问题的，并且经过数学验证的规则，用于从搜索树中消除节点。如果可以证明所有解决方案的性能在给定的节点S1比另一个节点S2的解决方案的性能更差，那么S1是由S2主导的，因此可以从树中消除S1。

下界和上界也可以用于修剪搜索树的节点。如果给定节点S的所有解的代价上的下界大于最优解的代价上界UB，则可以得出S不包括最优解。因此，S可以从树中消除。上界可以使用启发式方法初始化，并且可以在搜索过程中使用最佳解决方案发现-到目前为止进行更新。

在与节点关联的部分时间表中，一组任务被安排在特定的时间表上，具有已知的执行时间和延迟成本。此外，截止时间已经超过所有时间表的任务也被取消。其余的任务还没有安排或放弃。状态v*（s）定义为部分调度节点的表示。它包括任务的初始参数以及它们在相应的部分时间表中的状态（计划、删除或未计划）。

假设有一个值函数v*（s），其确定一个完整的时间表，表示从一个给定状态S开始至少达到的成本，这里的价值函数是S子空间中最佳解决方案的成本。搜索的深度可通过截断树S的价值函数得到，替换的最佳时间表的成本中的子树在S内是降低的。本研究使用神经网络，产生价值函数的近似vθ（s）≈v*（s），在这θ表示价值网络的权重。以状态作为输入，输出给定状态的近似最优值。这样的网络可以使用B&B算法脱机执行获得的标记数据进行训练。价值网络在给定节点S处所做的预测与UB进行比较，如果预测的成本足够大，则可以从搜索树中消除节点S。这样，B&B方法通过删除不太可能最终得到最优解的节点而变得更快。标有"*"的用于记录数据，而不用于算法的必需部分。搜索树已实现使用堆栈数据结构。深度优先搜索策略用于遍历树的节点，本研究修改了[7]的B&B方法以包括任务删除。堆栈的每个元素都是一个元组，元组由一系列任务T（代表部分调度），在T之后立即安排的一组任务PF，一组未计划的任务NS和已删除的一组任务DR组成。增强分支定界法的具体步骤如下：

在节点S，分支是通过从PF中选择具有最小起始时间的任务a来执行的。然后，将任务a从PF中删除，并添加到NS中，a被安排在当前分支中，对于S的其余分支，它还没有被安排。因此，它被添加到NS集中。这样，当在节点S处添加一个新的分支时，将NS集的任务与PF集的元素合并，形成第一组可能的节点。在根节点，可能的第一组节点被初始化为包含所有任务，NS和DR被设置为空。上界UB包含在搜索过程中获得的最佳调度的成本。UB最初设置为无穷大，根节点被推到堆栈的顶部，然后，只要堆栈不是空的，就执行以下过程：在每次迭代时，检查堆栈顶部的节点，如果可能的第一组PF为空，则节点将从堆栈中删除，在删除节点之前，检查未调度集合NS中是否有任何任务，如果NS为空，则节点是终端，并表示完整的解决方案。在这种情况下，将总体成本C与UB进行比较，如果有改进，则应该更新UB。在堆栈顶部可能的第一组节点不是空的情况下，使用PF任务生成一个新节点。具体来说，设置一个PF中最小的任务开始时间。本研究从PF中删除a并在T的末尾附加它以获得新节点的序列T'。新节点PF的可能第一组PF'被设定为PF和NS的并集。删除的任务DR'是从DR继承的，新节点NS的未计划集合被设置为空。然后，将任务a添加到NS。

在生成新节点后，应该确定是否应该将其添加到堆栈中，以便下一次迭代时进行进一步的研究，或者可以忽略它，从而进行修剪。要做到这一点，本研究首先对T'这条规则规定检查，第T'任务的执行时间的顺序应该不减少启动时间的主导地位规则，否则，T'占主导地位，无法得出最优解。接下来本研究检查PF'中的任务，任何截止时间在频道最早可用时间之前的任务都被删除。此时，可以计算新的部分解的延迟和下降成本之和，再从该节点导出的任何完整解上提供一个下界C'。如果这个成本不低于UB，则可以忽略新节点。此外，如果T'不能映射到活动计划，则它可以被丢弃。一个较好的时间表是没有任务可以提前完成，也不延迟另一个任务。对PF'中的任务检查，它们中的任何一个是否可以在T'中的最后一个任务之前进行调度且不造成延误，以确定T'是否是活动的。

接下来，本研究检查T'是否是一个最低调度。一个最低活动时间表是不交换两个相邻的任务就可以改善时间表。任务a的相邻任务被定义为在调度任务a之前，在每个时间线的最终时隙上调度的任务集。检查时间表是否为最低活动的条件与上面相同，但也需要考虑任务删除。在这种情况下，考虑时间轴的可用时间而不是完成时间，下降成本取代延迟成本。如果新节点是最低活动的，则检查它是否也是一个完整的解决方案。在这种情况下，更新父节点的统计数据，以便进行数据记录。

除了检查C是否小于UB之外，还可以使用价值网络从新节点得到预计的最低最终成本，并将其与UB进行比较。如果估计值大于UB×α，则从搜索中删除该节点。引入缩放系数α≥1以使该算法对估计误差具有鲁棒性。使用较大的α值可以实现更好的性能，但这意味着从搜索树中删除更少的节点。如果通过了边界和优势规则，则新节点将被推到堆栈的顶部。完成此步骤后，搜索将继续进行下一个迭代。最后，一旦探索了整个树，就会返回找到的最佳解决方案就。

2.1  数据记录

本研究在搜索过程中记录节点的统计信息，将它们用作标记数据以监督学习价值神經网络。对于给定的节点S，有一个标志∏s，表示是否已经达到至少一个完整搜索过程。在∏s终止的情况下，记录其最佳终端解决方案的成本。

如上一节中所述，在分支步骤中，本研究检查新的子节点S'是否为最低活动状态，如果为真，则接下来检查∏s是否为完整解决方案，如果∏s的可能第一集合为空，则代表到达了终端节点，即完整的解决方案。在这种情况下，父节点S的统计信息将被更新。如果∏s为假或S'的成本小于∏s的最佳终端成本，则S将设置为真并且最佳终端成本的S将被设置为s'的成本。

在B&B程序中，在从堆栈中删除给定节点S之前，本研究检查其是否终止，即∏s是否为真。在这种情况下，S的父节点的统计信息将更新。此外，节点S及其所有统计信息都被记录下来。而且，记录的给定节点的最佳终端成本是v*（s），记录的标记数据（s，v*（s））用于价值网络的监督学习中。

2.2  价值网络架构

本研究使用6层卷积神经网络实现价值网络[8]。前三层是卷积的，最后三层是完全连接的。在每个卷积层，将输入与滤波器卷积以产生输出特征。滤波器的系数是使用监督学习获得。每个层的输出经过一个非线性函数（整流函数），然后传递到下一层。网络的最终输出是一个标量数，表示输入部分调度的估计最小总体成本。网络的输入是一个矩阵，每个列表示一个任务，每一行表示相应任务的一个特征。

在本文中，考虑了给出的每个任务的14个特征（见表2）。假设有4个通道可用于任务调度。每个通道都有一个输入特性，本团队使用一个热编码来表示任务被调度的通道。对于每个任务，对应于任务计划所在信道的输入特征设置为1，其余输入时间轴特征设置为0。

对于卷积层，使用宽度为7的过滤器（查看每个步幅的   7个连续任务的特征）。每层使用64个滤波器，每个卷积层的输出具有64个特征。本研究已经为第一个完全连接的层考虑了512个隐藏单元。第二个完全连接的层具有128个隐藏单元，最后一层具有一个标量。

训练阶段通常使用正则化方法，以避免训练样本过拟合神经网络的问题。这些方法的一般模式是帮助网络学习训练样本的[9]，而不是记忆它们。本研究使用正则化最常用的方法退火技术[10]，在训练阶段，每个层的单位的固定百分比被随机丢弃，导致了基本网络的训练子网络，是一个好的特性。在训练阶段中，还使用批归一化来改进优化过程。设H是给定激活层的的一部分。为了规范H，本研究用H'代替它

其中μ和σ分别表示单位的均值和标准差。对于卷积层，这些矩是在H的前三个维度上得到的，因此它们的长度为64。对于完全连接的层，矩是在H行上计算的，因此，它们的长度等于隐藏单元的数目。通过广播来执行公式（3）中的减法和除法运算。在训练过程中，使用当前批次的样本均值和方差获得μ和σ。在推理过程中，μ和σ可以被训练期间收集的运行平均值所取代。将卷积层的激活标准化可能会降低网络的表现力。因此，归一化批次H'被γH'+β所取代，γ和β是在训练阶段学习的变量。

网络的权重可以通过使用梯度下降对训练状态结果（s，v*（s））进行回归来找到，以最小化估计值vθ（s）和目标值之间的均方误差（MSE）[11]。相应的真实结果v*（s）如下：

培训数据是通过离线执行B&B方法获得的，如上面所述。该网络使用90 000个样本进行了训练。通过使用自适应矩估计优化方法使损失最小化来获得权重。对于大小为100的迷你批处理，本研究使用100 000步的随机改组（RR）方法进行处理。

3    仿真结果

本研究现在给出了仿真结果，说明了该方法的性能。本研究考虑一种具有K=4个相同信道的多通道雷达。有N=35个任务分布在100 ms的时间线窗口上。目标是安排任务，使公式（2）中的目标最小。在本研究的仿真中，任务的开始时间均匀分布在100 ms的时间窗口上。其中，。

对于每个任务，起始时间和截止时间之间的间隔，即dn-rn从μ（2，12）中采样。任务长度ln是根据μ（2，11）分配的。此外，下降成本Dn和拖延权重ωn分别分布在μ（100，500）和μ（1，5）上。在仿真中，本研究使用蒙特卡洛方法进行100次试验，以获得每种方法的平均性能。

B&B的运行时间和所提出的方法与访问节点的数量成正比。正如预期的那样，B&B算法具有最佳的性能和最高的复杂度。B&B方法的平均访问节点为13 134个。在使用α=1的价值网络的情况下，平均访问节点数下降到仅342个节点，这比没有价值网络的B&B方法的访问节点数少了大约38倍。然而，这种复杂性降低导致性能下降。本研究通过增加缩放系数可以获得更好的性能。用α=2，平均成本为49。得到3个显著低于启发式方法的平均成本。然而，這时访问节点的平均数量增加到962个，但仍然比B&B算法中的平均访问节点少约14倍。性能可以随着α=3而进一步提高，但是计算负担略有增加。EST和ED分别是最早开始时间最早和最早截止时间最早的方法。SW指的是任务交换技术。最后三个列是使用具有不同比例系数的价值网络增强的B&B方法的，结果如表3和表4所示。

4    结语

本文考虑了多通道多功能雷达的雷达资源管理问题，介绍了如何利用机器学习技术在雷达运行过程中获取知识，在未来的决策中使用这些知识。

分支定界算法为任务调度问题找到了最优解，但计算负担较高。本研究展示了如何使用机器学习方法来降低分支定界方法的复杂性。在搜索树的每个节点上使用一个价值网络来预测节点的给定部分计划中可以实现的最小成本。价值网络是使用监督学习和从最佳分支定界方法的离线执行中获得的数据样本进行训练的。虽然这大大减少了搜索树的访问节点数量，但性能不会受到太大的影响。

[参考文献]

[1]HAYKIN S.Cognitive radar：a way of the future[J].IEEE Signal Processing Magazine，2006（1）：30-40.

[2]MOO P W，DING Z.Adaptive radar resource management[J].Adaptive Radar Resource Management，2015（2）：141–148.

[3]CHARLISH A，WOODBRIDGE K，Griffiths H.Phased array radar resource management using continuous double auction[J].Ieee Transactions on Aerospace and Electronic Systems，2015（3）2212–2224.

[4]MIRANDA S L C，BAKER C J，WOODBRIDGE K，et al.Comparison of scheduling algorithms for multifunction radar[J].IET Radar Sonar and Navigation，2007（6）：414–424.

[5]SHAGHAGHI M，ADVE R S.Task selection and scheduling in multifunction multichannel radars[C].Seattle：In 2017 IEEE Radar Conference（RadarConf），2017.

[6]LENSTRA J K，KAN A R，BRUCKER P.Complexity of machine scheduling problems[J].Annals of Discrete Mathematics，1977（1）：343–362.

[7]JOUGLET A，SAVOUREY D.Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates[J].Computers & Operations Research，2011（9）：1259–1266，2011.

[8]童行行.基于機器学习的网络流量分析研究[D].北京：清华大学，2015.

[9]顾依依，谈询滔，袁玉波.基于凸边界的学习样本抽取方法[J].计算机应用，2019（8）：2281-2287.

[10]曾靖，李文，李宏民，等.基于模拟退火算法的连续时间系统的时域综合[J].电子测量与仪器学报，2019（12）：189-195.

[11]姜鹏飞，蔡之华.基于遗传算法和梯度下降的RBF神经网络组合训练方法[J].计算机应用，2007（2）：366-368.

（编辑 何 琳）