一种任务队列生成和调度方法

1.本发明属于车联网领域，涉及一种任务队列生成和调度方法。


背景技术：

2.在智能交通系统中，车辆在行驶时需要执行高度计算密集型任务，例如自动驾驶、和增强现实。这些任务的一个共同特点是需要在严格的完成时间限制内计算大量数据。此外，处理大量数据会消耗大量电力，这会影响电池容量有限的智能汽车的续航里程。因此，智能车辆应与部署在道路上的基础设施协同工作，以获得额外的计算和存储资源，或通过事件触发的估计框架中的v2v链路融合来自其他车辆的信息。为了解决这个问题，引入了车载边缘计算(vec)作为多接入边缘计算的子类。作为车联网中最有前途的计算范式，vec网络架构通过rsu为智能车辆提供所需的资源。智能车辆可以通过将计算任务卸载到可能包含部署在rsu上的多个虚拟机的边缘服务器来显着减少时延和能源消耗。而且，与传统的云计算相比，车辆与边缘服务器之间的通信距离要小得多，降低了车辆在vec架构中的通信成本。此外，车辆可以满足智能交通系统的服务质量，以实现低时延和低能耗。
3.然而，由于vec环境的易变性，卸载操作并不总能提高vec系统的性能。例如，在不利的无线链路状态的情况下，卸载操作可能比本地执行产生更多的时间延迟和传输能量消耗。此外，当边缘服务器过载时，卸载操作会导致更长的等待时间。因此，对于一个整体的vec系统，设计一个灵活的vec任务调度策略，使系统能够平衡计算成本和传输成本是一个关键的优化问题。


技术实现要素：

4.有鉴于此，本发明的目的在于提供一种任务队列生成和调度方法。
5.为达到上述目的，本发明提供如下技术方案：
6.一种任务队列生成和调度方法，该方法包括以下步骤：
7.s1：根据子任务依赖关系使用有向无环图dag对子任务进行建模，dag中没有边相连的子任务且都为某个子任务的前驱子任务无依赖关系，所以能并行调度处理减少子任务等待时延，并设计子任务的最迟开始时间作为队列排序规则；
8.s2：根据各子任务属性对多车子任务调度的成本进行建模，能耗是影响车辆续航的重要指标，时延是车载任务的重要指标，所以构建子任务调度的能耗和时延模型并对其进行加权求和得到系统的成本；
9.s3：采用多智能体强化学习方法对各车中子任务队列进行调度以最小化车辆系统的长期平均成本。
10.可选的，所述s1具体包括以下步骤：
11.s11：使用有向无环图dag建模任务中子任务的依赖关系，任务表示为其中，为节点集合代表各子任务，为边的集合表示各子任务间的依赖关
系，表示子任务的数量；
12.s12：根据每个子任务的最迟开始时间度量它们的紧急性作为排序的规则，拥有最小最迟开始时间的子任务拥有最高优先级放在队尾；则子任务的最迟开始时间为：
[0013][0014]
其中，为子任务在x计算的执行时间，x∈{0,1,2,
…
,m}，其中，x＝0表示本地计算，其他表示调度到rsu的m个vms上进行计算；最小的计算时间用来构建优先级队列，实际计算时间通过实际调度计算而来；表示子任务i的最迟完成时间计算方式为：
[0015][0016]
其中，表示子任务的后继子任务集合；dag出节点的最迟完成时间即为整个任务的约束时间；利用出节点依次向前递推的方式得到其他任务的最迟开始时间，将所有子任务降序排列得到优先级队列。
[0017]
可选的，所述s2具体包括以下步骤：
[0018]
s21：构建本地计算的时延和能耗模型；调度实现本地计算的模式，即x＝0，为计算整个任务的处理时间，引入子任务的最早开始时间为：
[0019][0020]
其中，表示子任务的前驱子任务集合，为子任务的实际完成时间；任务车辆通过v2i链路或者本地计算机能够得到前驱子任务的计算结果，忽略计算结果的通信成本；对于子任务的本地计算时间表示为：
[0021][0022]
其中，fn表示车n的cpu频率，表示子任务的比特数，表示完成一比特任务所需要的cpu周期数，得到子任务在本地执行的最早完成时间：
[0023][0024]
计算出相应能耗为：
[0025][0026]
其中，ξ和ν都是于芯片属性相关的常数；
[0027]
s22：构建任务调度至rsu的时延和能耗模型；将子任务卸载到rsu的vms进行处理除计算的时间，还需要额外的传输时延和能耗；则任务车辆n与rsu之间的传输速率表示为：
[0028][0029]
其中，ωn和pn分别表示传输带宽和功率，hn为信道增益，σ2为噪声功率；κn＝∑n′
∈n\{n}
pn′hn
′
为其它车辆产生的干扰功率，得到车n卸载大小为的子任务的传输时延和传输能耗为：
[0030][0031][0032]
若存在多任务车辆同时竞争一个rsu上的计算资源，这会造成任务的排队等待；子任务的排队等候时间由它的前驱子任务和比它优先级更高的子任务决定；前驱子任务的计算在本地或者在vms上；比它优先级高的其他任务的子任务只考虑在vms上排队的任务，则子任务在vms上计算的最早开始时间表示为：
[0033][0034]
其中，表示比子任务优先级高的其他任务的子任务集合，计算出子任务在vms上的计算时间：
[0035][0036]
其中，fm表示第m个vm的cpu周期频率；能计算出子任务的最早完成时间为：
[0037][0038]
s23：构建成本模型；记每个任务的产生时间为任务的个子任务在经过s1规则进行优先级排序后会被依次调度到本地或者rsu上的vms进行计算；其中，的出节点完成时间即为整个任务的最终完成时间；根据出节点的实际完成时间，算出任务的处理时延：
[0039][0040]
其中，πn表示调度器使用策略π对子任务进行调度；同样可以求得调度策略下的能耗为：
[0041][0042]
其中，表示子任务是否在此处理机x上执行，且有，根据根据时延和能耗构建长期平均成本作为优化目标为：
[0043]
p2其中，α用来控制能耗和时延之间的权重，β用来平衡时延和能耗之间的数量级差异。
[0044]
可选的，所述s3具体包括以下步骤：
[0045]
s31：为每辆车构建基于策略梯度的深度强化学习模型；
[0046]
s32：将任务队列中处理固定子任务数量作为训练回合，采取一回合的子任务调度数据；
[0047]
s33：为强化学习设计损失函数进行训练学习。
[0048]
本发明的有益效果在于：首先，根据任务间子任务关系构建任务依赖的数学模型，并定义子任务的最迟开始时间作为队列排序规则；其次，根据各子任务属性对多车子任务调度的成本进行建模；最后，采用多智能体强化学习方法对各车中子任务队列进行调度以最小化车辆系统的长期平均成本。
[0049]
本发明的其他优点、目标和特征在某种程度上将在随后的说明书中进行阐述，并且在某种程度上，基于对下文的考察研究对本领域技术人员而言将是显而易见的，或者可以从本发明的实践中得到教导。本发明的目标和其他优点可以通过下面的说明书来实现和获得。
附图说明
[0050]
为了使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作优选的详细描述，其中：
[0051]
图1为本发明的子任务调度架构图；
[0052]
图2为本发明中带子任务依赖的模型。
具体实施方式
[0053]
以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需要说明的是，以下实施例中所提供的图示仅以示意方式说明本发明的基本构想，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。
[0054]
其中，附图仅用于示例性说明，表示的仅是示意图，而非实物图，不能理解为对本发明的限制；为了更好地说明本发明的实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；对本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。
[0055]
本发明实施例的附图中相同或相似的标号对应相同或相似的部件；在本发明的描述中，需要理解的是，若有术语“上”、“下”、“左”、“右”、“前”、“后”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此附图中描述位置关系的用语仅用于示例性说明，不能理解为对本发明的限制，对于本领域的普通技术人员而言，可以根据具体情况理解上述术语的具体含义。
[0056]
请参阅图1和图2，本发明提出的一种任务队列生成和调度方法的算法，具体包含以下步骤：
[0057]
步骤1：根据子任务依赖关系使用有向无环图(dag)对子任务进行建模，dag中没有边相连的子任务且都为某个子任务的前驱子任务无依赖关系，所以能并行调度处理减少子任务等待时延，并设计子任务的最迟开始时间作为队列排序规则，具体包括以下步骤：
[0058]
步骤1.1：使用有向无环图(dag)建模任务中子任务的依赖关系，任务d
nl
表示为其中，为节点集合代表各子任务，为边的集合表示各子任务间的依赖关
系，表示子任务的数量；
[0059]
步骤1.2：根据每个子任务的最迟开始时间度量它们的紧急性作为排序的规则，拥有最小最迟开始时间的子任务拥有最高优先级放在队尾。则子任务的最迟开始时间为：
[0060][0061]
其中，为子任务在x计算的执行时间，x∈{0,1,2,
…
,m}，其中，x＝0表示本地计算，其他表示调度到rsu的m个vms上进行计算。这里直接考虑最小的计算时间只是用来构建优先级队列，但是实际计算时间还需通过实际调度计算而来。表示子任务i的最迟完成时间计算方式为：
[0062][0063]
其中，表示子任务的后继子任务集合。dag出节点的最迟完成时间即为整个任务的约束时间。利用出节点依次向前递推的方式便可得到其他任务的最迟开始时间，从而将所有子任务降序排列得到优先级队列。
[0064]
步骤2：根据各子任务属性对多车子任务调度的成本进行建模，能耗是影响车辆续航的重要指标，时延是车载任务的重要指标，所以构建子任务调度的能耗和时延模型并对其进行加权求和得到系统的成本，具体包括以下步骤：
[0065]
步骤2.1：构建本地计算的时延和能耗模型。调度实现本地计算的模式也即x＝0，为方便后续计算整个任务的处理时间，这里需要引入子任务的最早开始时间为：
[0066][0067]
其中，表示子任务的前驱子任务集合，为子任务的实际完成时间。任务车辆通过v2i链路或者本地计算机能够得到前驱子任务的计算结果，这里忽略计算结果的通信成本，因为计算结果相比原数据足够小。对于子任务的本地计算时间可以表示为：
[0068][0069]
其中，fn表示车n的cpu频率，表示子任务的比特数，表示完成一比特任务所需要的cpu周期数。则可以得到子任务在本地执行的最早完成时间：
[0070][0071]
此外，还可计算出相应能耗为：
[0072][0073]
其中，ξ和ν都是于芯片属性相关的常数；
[0074]
步骤2.2：构建任务调度至rsu的时延和能耗模型。将子任务卸载到rsu的vms进行处理除计算的时间，还需要额外的传输时延和能耗。则任务车辆n与rsu之间的传输速率可表示为：
[0075][0076]
其中，ωn和pn分别表示传输带宽和功率，hn为信道增益，σ2为噪声功率。κn＝∑n′
∈n\{n}
pn′hn
′
为其它车辆产生的干扰功率。可得到车n卸载大小为的子任务的传输时延和传输能耗为：
[0077][0078][0079]
若存在多任务车辆同时竞争一个rsu上的计算资源，这会造成任务的排队等待。子任务的排队等候时间由它的前驱子任务和比它优先级更高的子任务决定。前驱子任务的计算可能在本地也可能在vms上。比它优先级高的其他任务的子任务只考虑在vms上排队的任务，则子任务在vms上计算的最早开始时间可表示为：
[0080][0081]
其中，表示比子任务优先级高的其他任务的子任务集合。可以计算出子任务在vms上的计算时间：
[0082][0083]
其中，fm表示第m个vm的cpu周期频率。同样，能计算出子任务的最早完成时间为：
[0084][0085]
步骤2.3：构建成本模型。记每个任务的产生时间为任务的个子任务在经过s1规则进行优先级排序后会被依次调度到本地或者rsu上的vms进行计算。其中，的出节点完成时间即为整个任务的最终完成时间。根据出节点的实际完成时间即可算出任务的处理时延：
[0086][0087]
其中，πn表示调度器使用策略π对子任务进行调度。同样可以求得调度策略下的能耗为：
[0088][0089]
其中，表示子任务是否在此处理机x上执行，且有，根据根据时延和能耗可以构建长期平均成本作为优化目标为：
[0090][0091]
其中，α用来控制能耗和时延之间的权重，β用来平衡时延和能耗之间的数量级差异。
[0092]
步骤3：采用多智能体强化学习方法对各车中子任务队列进行调度以最小化车辆系统的长期平均成本，具体包含以下步骤：
[0093]
步骤3.1：为每辆车构建基于策略梯度的深度强化学习模型；
[0094]
步骤3.2：将任务队列中处理固定子任务数量作为训练回合，收集一回合的子任务调度数据，维护一个经验回放池b，将经验(su,ou,au,ru,s
u+1
,o
u+1
)存储到经验池中，使用如下公式计算优势的估计：
[0095][0096]
其中，su为环境状态，ou为所有智能体发观测，ru为所有智能体的共享奖励，表示为：
[0097]ru
＝-(αtu+(1-α)βeu)-θc
[0098]
其中，c为常数表示任务超出阈值的惩罚θ∈{0,1}表示若任务超出阈值则θ＝1，否则θ＝0。
[0099]
步骤3.3：为强化学习设计损失函数进行训练学习，设计价值网络损失函数：
[0100][0101]
对其采用梯度下降进行参数优化。ψ为策略网络参数，b为批次大小。
[0102]
对于策略函数对如下：
[0103][0104]
采用梯度上升进行参数优化。为策略网络参数，s为策略熵用于增加智能体的探索。
[0105]
在每回合所有智能体与环境交互的数据进行多次网络更新，之后将经验池清空进行下以回合的数据采样和训练。
[0106]
最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本技术方案的宗旨和范围，其均应涵盖在本发明的权利要求范围当中。

技术特征：
1.一种任务队列生成和调度方法，其特征在于：该方法包括以下步骤：s1：根据子任务依赖关系使用有向无环图dag对子任务进行建模，dag中没有边相连的子任务且都为某个子任务的前驱子任务无依赖关系，所以能并行调度处理减少子任务等待时延，并设计子任务的最迟开始时间作为队列排序规则；s2：根据各子任务属性对多车子任务调度的成本进行建模，能耗是影响车辆续航的重要指标，时延是车载任务的重要指标，所以构建子任务调度的能耗和时延模型并对其进行加权求和得到系统的成本；s3：采用多智能体强化学习方法对各车中子任务队列进行调度以最小化车辆系统的长期平均成本。2.根据权利要求1所述的一种任务队列生成和调度方法，其特征在于：所述s1具体包括以下步骤：s11：使用有向无环图dag建模任务中子任务的依赖关系，任务表示为其中，为节点集合代表各子任务，为边的集合表示各子任务间的依赖关系，表示子任务的数量；s12：根据每个子任务的最迟开始时间度量它们的紧急性作为排序的规则，拥有最小最迟开始时间的子任务拥有最高优先级放在队尾；则子任务的最迟开始时间为：其中，为子任务在x计算的执行时间，x∈{0,1,2,
…
,m}，其中，x＝0表示本地计算，其他表示调度到rsu的m个vms上进行计算；最小的计算时间用来构建优先级队列，实际计算时间通过实际调度计算而来；表示子任务i的最迟完成时间计算方式为：其中，表示子任务的后继子任务集合；dag出节点的最迟完成时间即为整个任务的约束时间；利用出节点依次向前递推的方式得到其他任务的最迟开始时间，将所有子任务降序排列得到优先级队列。3.根据权利要求2所述的一种任务队列生成和调度方法，其特征在于：所述s2具体包括以下步骤：s21：构建本地计算的时延和能耗模型；调度实现本地计算的模式，即x＝0，为计算整个任务的处理时间，引入子任务的最早开始时间为：其中，表示子任务的前驱子任务集合，为子任务的实际完成时间；任务车辆通过v2i链路或者本地计算机能够得到前驱子任务的计算结果，忽略计算结果的通信成本；对于子任务的本地计算时间表示为：
其中，f
n
表示车n的cpu频率，表示子任务的比特数，表示完成一比特任务所需要的cpu周期数，得到子任务在本地执行的最早完成时间：计算出相应能耗为：其中，ξ和ν都是于芯片属性相关的常数；s22：构建任务调度至rsu的时延和能耗模型；将子任务卸载到rsu的vms进行处理除计算的时间，还需要额外的传输时延和能耗；则任务车辆n与rsu之间的传输速率表示为：其中，ω
n
和p
n
分别表示传输带宽和功率，h
n
为信道增益，σ2为噪声功率；κ
n
＝∑
n
′
∈n\{n}
p
n
′
h
n
′
为其它车辆产生的干扰功率，得到车n卸载大小为的子任务的传输时延和传输能耗为：为：若存在多任务车辆同时竞争一个rsu上的计算资源，这会造成任务的排队等待；子任务的排队等候时间由它的前驱子任务和比它优先级更高的子任务决定；前驱子任务的计算在本地或者在vms上；比它优先级高的其他任务的子任务只考虑在vms上排队的任务，则子任务在vms上计算的最早开始时间表示为：其中，表示比子任务优先级高的其他任务的子任务集合，计算出子任务在vms上的计算时间：其中，f
m
表示第m个vm的cpu周期频率；能计算出子任务的最早完成时间为：s23：构建成本模型；记每个任务的产生时间为任务的个子任务在经过s1规则进行优先级排序后会被依次调度到本地或者rsu上的vms进行计算；其中，的出节点完成时间即为整个任务的最终完成时间；根据出节点的实际完成时间，算出任务的处理时延：
其中，π
n
表示调度器使用策略π对子任务进行调度；同样可以求得调度策略下的能耗为：其中，表示子任务是否在此处理机x上执行，且有，根据根据时延和能耗构建长期平均成本作为优化目标为：其中，α用来控制能耗和时延之间的权重，β用来平衡时延和能耗之间的数量级差异。4.根据权利要求3所述的一种任务队列生成和调度方法，其特征在于：所述s3具体包括以下步骤：s31：为每辆车构建基于策略梯度的深度强化学习模型；s32：将任务队列中处理固定子任务数量作为训练回合，采取一回合的子任务调度数据；s33：为强化学习设计损失函数进行训练学习。

技术总结
本发明涉及一种任务队列生成和调度方法，属于车联网领域。由于任务间存在依赖关系串行的任务处理方式会带来较大的时延，降低了用户的服务质量。其中，根据任务间子任务关系构建任务依赖的数学模型，并定义子任务的最迟开始时间作为队列排序规则；然后，根据各子任务属性对多车子任务调度的成本进行建模；最后，采用多智能体强化学习方法对各车中子任务队列进行调度以最小化车辆系统的长期平均成本。进行调度以最小化车辆系统的长期平均成本。进行调度以最小化车辆系统的长期平均成本。


技术研发人员：李职杜 刘涛 唐桐 吴大鹏 王汝言
受保护的技术使用者：重庆邮电大学
技术研发日：2023.04.23
技术公布日：2023/7/18