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

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