一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法

1.本发明涉及边缘计算和深度强化学习领域，具体是一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法。


背景技术：

2.随着通信技术的快速发展和移动设备数量的爆炸性增长加速了创新应用的出现，如增强现实、人脸识别、智能汽车和智能家居。这些复杂的应用程序通常需要密集的计算资源和低响应延迟，这将给核心网络带来巨大压力。同时，由于这些移动设备通常受到计算、存储和能量的限制，因此很难在移动设备上运行这些应用程序，此类应用程序一般是在云端进行的，但由于云端远离移动设备，在云端运行这些应用程序将导致高传输延迟。
3.移动边缘计算是近年来新兴的技术之一可以有效克服这一困境的。具体而言，作为移动边缘计算的关键技术，任务卸载旨在将计算密集型任务从移动设备卸载到部署在网络边缘的边缘服务器，通过联合考虑任务的性质和边缘服务器的资源利用率，任务卸载可以显著减少移动设备的系统延迟和能耗，并提高对用户的服务质量。因此，任务卸载在满足这些计算延迟敏感任务的要求方面起着至关重要的作用。
4.目前普遍采用的优化方法是将移动终端的计算任务卸载到边缘服务器，但是此优化方法存在着一些难以解决的问题：第一，当移动边缘计算系统中包含大量的移动设备时，边缘服务器会因此而过载，从而会导致计算任务的处理时间显著增加，降低用户的体验质量。第二，这种方法没有充分考虑移动终端、边缘服务器、和云服务器的协作能力，仅联合单个边缘服务器和多个移动终端忽略了云服务器的服务能力，导致整个移动边缘计算系统效率低下。


技术实现要素：

5.本发明的目的是提供一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，包括以下步骤：
6.1)建立多用户移动边缘计算系统，包括云端服务器、b个边缘基站和n个无线移动设备；每个基站均具有边缘服务器；
7.2)获取边缘计算网络信息，包括云端服务器、边缘服务器、无线移动设备产生的任务信息；
8.3)对于无线移动设备第n个应用程序，建立有向非循环图，以表示应用程序中i个依赖性子任务之间的依赖关系；
9.4)根据有向非循环图，建立依赖性任务卸载时延和能耗模型；
10.5)根据依赖性任务卸载时延和能耗模型，建立任务卸载决策模型，并利用马尔可夫决策方式对任务卸载决策模型进行解算，得到任务卸载决策。
11.进一步，所述有向非循环图具有入口节点和出口节点；其中，入口节点和出口节点
分别表示应用程序的开始任务和结束任务；
12.有向非循环图中所有任务根据秩值进行了降序排列；
13.其中，任务q
in
的秩值rank(q
in
)如下所示：
[0014][0015]
式中，ft
in
表示卸载和处理任务q
in
的等待时间；(i+1)n表示退出任务的集合。rank(q
jn
)为任务q
jn
的秩值。
[0016]
进一步，建立依赖性任务卸载时延和能耗模型的步骤包括：
[0017]
4.1)根据有向非循环图，将任务的一组直接前任表示为的一组直接前任表示为
[0018]
4.2)计算任务的最大完成时间，即：
[0019][0020]
式中，当在本地处理任务时，的就绪时间为任务为任务的最大完成时间；为在本地、边缘服务器或云服务器上执行任务的完成时间；
[0021]
4.3)将任务的本地执行时间表示为将本地平均计算能力表示为
[0022]
计算任务的本地执行时间和完成时间即：
[0023][0024][0025]
式中，为任务所需的cpu周期；
[0026]
4.4)计算在本地执行的任务的能耗即；
[0027][0028]
式中，κ为能耗系数；
[0029]
4.5)建立在边缘服务器端的任务的就绪时间即：
[0030][0031]
式中，分别表示本地到边缘服务器、边缘服务器b到边缘服务器b
′
的传输时间；
[0032]
4.6)计算从边缘服务器b到云服务器的传输时间4.6)计算从边缘服务器b到云服务器的传输时间为数据大小；
为从边缘服务器b到云服务器的传输速率；
[0033]
计算任务在云服务器的执行时间fc为云服务器的计算能力；
[0034]
计算任务在云服务器的就绪时间即：
[0035][0036]
式中，为从边缘服务器到云服务器的传输时间；
[0037]
4.7)计算第n个应用程序的任务卸载时延与能量加权和
[0038]
其中，为移动设备的总能耗；本地能耗上传任务的能耗上传任务的能耗为单位能耗。
[0039]
进一步，任务卸载决策模型的目标函数为：任务卸载总时延和总能量的加权和达到最小。
[0040]
进一步，利用马尔可夫决策方式对任务卸载决策模型进行解算的步骤包括：
[0041]
5.1)建立任务卸载过程中的动作空间a和状态空间s；
[0042]
5.2)根据任务卸载决策模型的目标函数，定义出每次训练的系统奖励r
t
；
[0043]
5.3)基于系统奖励r
t
，确定任务卸载决策。
[0044]
进一步，所述状态空间s如下所示：
[0045]
s＝{s|s＝(g_n({i_{n}，θ_{n})，α_{1：i})}； (8)
[0046]
式中，g_n({i_{n}，θ_{n})为任务嵌入，包括嵌入当前任务的索引和直接前任和后继任务的索引；α_{1：i}表示从任务到的卸载决策。
[0047]
动作空间a中，时隙t的动作a
t
如下所示：
[0048]at
＝0，1，2，
…
，|{b}+1|； (9)
[0049]
式中，a
t
＝0表示任务在本地执行，a
t
＝{1，2，
…
，b}表示任务被卸载到边缘服务器，a
t
＝b+1表示此任务被卸载至云服务器。
[0050]
进一步，系统奖励r
t
如下所示：
[0051][0052]
式中，ξn为任务卸载总时延和总能量的加权和。
[0053]
进一步，基于系统奖励r
t
，确定任务卸载决策的步骤包括：
[0054]
5.3.1)建立动作a的表达式，即：
[0055]
a＝{argmax}{q(s，a
′
；w)}； (11)
[0056]
式中，w是参数矩阵；s为状态；q为行动值q
*
；
[0057]
5.3.2)在状态s上按照策略π执行动作a，以获得动作值q(s，a)；
[0058]
5.3.3)改变动作a，重复步骤5.3.2)，获得多个动作值q(s，a)，以最大动作值作为最佳作用值q
*
(s，a)，即：
[0059]
q*(s，a)＝{max}[r
t
|s
t
＝s，a
t
＝a，π]；
ꢀꢀ
(12)
[0060]
5.3.4)对最佳作用值q
*
(s，a)进行优化，得到：
[0061]q*(s，a)
＝{e}
′s[r+γ{a
′
}{max}q(s
′
，a
′
)|s，a] (13)
[0062]
式中，q
*(s，a)
为优化后的最佳作用值；γ为折扣因子；s
′
为状态；a
′
为动作；
[0063]
5.3.5)以优化后的最佳作用值作为下一步动作值q
{t+1}
(s，a)，即：
[0064]q{t+1}
(s，a)＝{e}
′s[r+γ{a
′
}{max}q
t
(s
′
，a
′
)|s，a]； (14)
[0065]
式中，r为奖励。e为时延和能量加权和。
[0066]
进一步，动作值q(s
′
，a
′
；w)与最佳作用值q*(s’，a’)之间的均方误差f如下所示：
[0067]
f＝r+γ{a
′
}{max}q(s
′
，a
′
；w)； (15)
[0068]
式中，r为动作产生的奖励值。
[0069]
进一步，确定任务卸载决策的过程中，迭代更新参数w矩阵时，使用的损失函数如下所示：
[0070]
loss(w)＝{e}
{s，a，r}
[{e}s[f|s，a]-q(s
′
，a
′
；w-)] (16)
[0071]
式中，w-为上一轮迭代的参数矩阵。
[0072]
本发明的技术效果是毋庸置疑的，本发明综合考虑云端，边缘服务器端和移动设备端，可以根据任务卸载所需要的时间和能量进行最优的任务卸载决策。
[0073]
本发明设计了一种通用的端边缘云网络架构，并提出了一种基于深度强化学习的依赖性感知任务卸载方法，以联合卸载所考虑网络中具有依赖性的任务。
[0074]
本发明通过有向无环图对任务之间的依赖性进行建模，并将问题表述为最小化所有用户的平均时间能量加权和。为了解决这个np难题，本发明创造性地利用深度神经网络来提取系统特征，并提出了基于深度q网络的框架来确定任务卸载策略。
[0075]
本发明提出的强化学习框架在解决依赖性任务调度问题综合考虑了能量和时延两种因素，实现了能量时延加权最优，大大降低了无线移动设备的通信时延和能量成本，满足了用户需求，节约了链路成本。
附图说明
[0076]
图1为系统模型图；
[0077]
图2为任务模型图；
[0078]
图3为强化学习架构图；
[0079]
图4为依赖性任务卸载的算法流程图。
具体实施方式
[0080]
下面结合实施例对本发明作进一步说明，但不应该理解为本发明上述主题范围仅限于下述实施例。在不脱离本发明上述技术思想的情况下，根据本领域普通技术知识和惯用手段，做出各种替换和变更，均应包括在本发明的保护范围内。
[0081]
实施例1：
[0082]
参见图1至图4，一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，包括以下步骤：
[0083]
1)建立多用户移动边缘计算系统，包括云端服务器、b个边缘基站和n个无线移动设备；每个基站均具有边缘服务器；
[0084]
2)获取边缘计算网络信息，包括云端服务器、边缘服务器、无线移动设备产生的任务信息；
[0085]
3)对于无线移动设备第n个应用程序，建立有向非循环图，以表示应用程序中1个依赖性子任务之间的依赖关系；
[0086]
4)根据有向非循环图，建立依赖性任务卸载时延和能耗模型；
[0087]
5)根据依赖性任务卸载时延和能耗模型，建立任务卸载决策模型，并利用马尔可夫决策方式对任务卸载决策模型进行解算，得到任务卸载决策。
[0088]
所述有向非循环图具有入口节点和出口节点；其中，入口节点和出口节点分别表示应用程序的开始任务和结束任务；
[0089]
有向非循环图中所有任务根据秩值进行了降序排列；
[0090]
其中，任务q
in
的秩值rank(q
in
)如下所示：
[0091][0092]
式中，ft
in
表示卸载和处理任务q
in
的等待时间；(i+1)n表示退出任务的集合。rank(q
jn
)为任务q
jn
的秩值。
[0093]
建立依赖性任务卸载时延和能耗模型的步骤包括：
[0094]
4.1)根据有向非循环图，将任务的一组直接前任表示为的一组直接前任表示为
[0095]
4.2)计算任务的最大完成时间，即：
[0096][0097]
式中，当在本地处理任务时，的就绪时间为任务为任务的最大完成时间；为在本地、边缘服务器或云服务器上执行任务的完成时间；
[0098]
4.3)将任务的本地执行时间表示为将本地平均计算能力表示为
[0099]
计算任务的本地执行时间和完成时间即：
[0100][0101][0102]
式中，为任务所需的cpu周期；
[0103]
4.4)计算在本地执行的任务的能耗即；
[0104][0105]
式中，κ为能耗系数；
[0106]
4.5)建立在边缘服务器端的任务的就绪时间即：
[0107][0108]
式中，分别表示本地到边缘服务器、边缘服务器b到边缘服务器b
′
的传输时间；
[0109]
4.6)计算从边缘服务器b到云服务器的传输时间4.6)计算从边缘服务器b到云服务器的传输时间为数据大小；为从边缘服务器b到云服务器的传输速率；
[0110]
计算任务在云服务器的执行时间fc为云服务器的计算能力；
[0111]
计算任务在云服务器的就绪时间即：
[0112][0113]
式中，为从边缘服务器到云服务器的传输时间；
[0114]
4.7)计算第n个应用程序的任务卸载时延与能量加权和
[0115]
其中，为移动设备的总能耗；本地能耗上传任务的能耗上传任务的能耗为单位能耗。
[0116]
任务卸载决策模型的目标函数为：任务卸载总时延和总能量的加权和达到最小。
[0117]
利用马尔可夫决策方式对任务卸载决策模型进行解算的步骤包括：
[0118]
5.1)建立任务卸载过程中的动作空间a和状态空间s；
[0119]
5.2)根据任务卸载决策模型的目标函数，定义出每次训练的系统奖励r
t
；
[0120]
5.3)基于系统奖励r
t
，确定任务卸载决策。
[0121]
所述状态空间s如下所示：
[0122]
s＝{s|s＝(g_n({i_{n}，θ_{n})，α_{1：i})}； (8)
[0123]
式中，g_n({i_{n}，θ_{n})为任务嵌入，包括嵌入当前任务的索引和直接前任和后继任务的索引；α_{1：i}表示从任务到的卸载决策。
[0124]
动作空间a中，时隙t的动作a
t
如下所示：
[0125]at
＝0，1，2，
…
，|{b}+1|； (9)
[0126]
式中，a
t
＝0表示任务在本地执行，a
t
＝{1，2，
…
，b}表示任务被卸载到边缘服务器，a
t
＝b+1表示此任务被卸载至云服务器。
[0127]
系统奖励r
t
如下所示：
[0128][0129]
式中，ξn为任务卸载总时延和总能量的加权和。
[0130]
基于系统奖励r
t
，确定任务卸载决策的步骤包括：
[0131]
5.3.1)建立动作a的表达式，即：
[0132]
a＝{argmax}{q(s，a
′
；w)}； (11)
[0133]
式中，w是参数矩阵；s为状态；q为行动值q
*
；
[0134]
5.3.2)在状态s上按照策略π执行动作a，以获得动作值q(s，a)；
[0135]
5.3.3)改变动作a，重复步骤5.3.2)，获得多个动作值q(s，a)，以最大动作值作为最佳作用值q
*
(s，a)，即：
[0136]
q*(s，a)＝{max}[r
t
|s
t
＝s，a
t
＝a，π]；
ꢀꢀ
(12)
[0137]
5.3.4)对最佳作用值q
*
(s，a)进行优化，得到：
[0138]q*(s，a)
＝{e}
′s[r+γ{a
′
}{max}q(s
′
，a
′
)|s，a] (13)
[0139]
式中，q
*(s，a)
为优化后的最佳作用值；γ为折扣因子；s
′
为状态；a
′
为动作；
[0140]
5.3.5)以优化后的最佳作用值作为下一步动作值q
{t+1}
(s，a)，即：
[0141]q{t+1}
(s，a)＝{e}
′s[r+γ{a
′
}{max}q
t
(s
′
，a
′
)|s，a]； (14)
[0142]
式中，r为奖励。e为时延和能量加权和。
[0143]
动作值q(s
′
，a
′
；w)与最佳作用值q*(s’，a’)之间的均方误差f如下所示：
[0144]
f＝r+γ{a
′
}{max}q(s
′
，a
′
；w)； (15)
[0145]
式中，r为动作产生的奖励值。
[0146]
确定任务卸载决策的过程中，迭代更新参数w矩阵时，使用的损失函数如下所示：
[0147]
loss(w)＝{e}
{s，a，r}
[{e}_s[f|s，a]-q(s
′
，a
′
；w-)] (16)
[0148]
式中，w-为上一轮迭代的参数矩阵。
[0149]
实施例2：
[0150]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，包括以下步骤：
[0151]
1)建立多用户移动边缘计算系统，此系统包含一个云端服务器，b个边缘基站和n个无线移动设备，其中每个基站均有边缘服务器，每个无线移动设备运行一个应用程序n包含i个依赖性子任务。
[0152]
2)获取边缘计算网络信息，包括云服务器，边缘服务器和用户移动设备产生任务信息，其任务所需的cpu周期和输入数据大小分别表示为和
[0153]
3)对于应用程序n，本发明通过具有入口节点和出口节点的有向非循环图来描述其任务的依赖关系，入口节点和出口节点分别表示应用程序的开始任务和结束任务。本发明使用θn表示n的所有任务的依赖性。
[0154]
4)将任务卸载策略表示为α∈{0，1，...，b，b+1}中，其中0表示任务在本地执行，1意味着它被卸载到相应的边缘服务器，b+1意味着它卸载到云服务器。注意，由于下载传输的速度很高，本发明认为可以忽略下载传输时间。此外，本发明将任务的就绪时间定义为其所有直接前置任务完成处理的时间，而完成时间定义为任务完成处理时的时间。基于此，在本地、边缘服务器或云服务器上执行任务的准备时间和完成时间可以分别表示为rt
lin
、rt
ein
、rt
cin
和ft
lin
、ft
ein
、ft
cin
[0155]
5)根据移动端，边缘服务器端和云端的任务卸载原则，并根据各自参数的初始化值，构造出移动端，边缘服务器端和云端的任务卸载执行的时间和能量期望模型，并进一步根据构造的模型，计算得到移动设备端的应用程序n执行完系列子任务所需要的总时延和
能量期望模型。
[0156]
5.1)本发明将任务的一组直接前任表示为当在本地处理时，的就绪时间，即应为的最大完成时间。由于也可以在本地处理、卸载到边缘服务器或卸载到云服务器，因此任务的最大完成时间应该是其最大完成时间和本地执行时间的总和，可以建模为
[0157][0158]
5.2)此外，本发明将任务的本地执行时间表示为mdn的平均计算能力表示为其上限为因此，可以通过计算，任务的完成时间可以通过计算。本地执行的任务的能耗可通过以下公式获得：
[0159][0160]
5.3)在边缘服务器端的任务完成准备时间建模为
[0161][0162]
5.4)本发明将从边缘服务器b到云服务器的传输速率表示为从b到云服务的传输时间可以计算为本发明将云计算能力表示为fc，那么任务的执行时间可以计算为任务在云中的就绪时间可以表示为：
[0163][0164]
5.5)对于无线移动设备的每个应用n，本发明将时延和能量加权和定义为
[0165]
其中e是每个移动设备的总能耗，可以通过
[0166]
其中e
in
表示本地或上传任务的能耗，可由下式给出
[0167][0168][0169]
定义出移动设备端依赖性任务卸载的最优决策问题，并且以最小化任务卸载总时延和总能量的加权和最终优化目标，根据步骤5中得到的任务卸载所需的时间和能量期望模型将最优决策问题转化为目标函数及其约束。
[0170]
将任务卸载决策建模转化为马尔可夫决策过程，定义出任务卸载过程中的动作空间a状态空间s，并根据之前得到的目标函数定义出每次训练的奖励r。通过深度强化学习算法而有效地确定任务卸载决策。
[0171]
7.1)系统的延迟和能耗可能受到许多因素的影响，例如任务配置文件(即，数据大
小、所需cpu周期)、有向无环图的拓扑结构、由于过长而抑制的标题11、无线传输速率和移动边缘计算系统状态。移动边缘计算系统的状态取决于先前的任务卸载决策。因此，本发明将状态空间定义为包括有向无环图信息和部分卸载计划的集合
[0172]
s＝{s|s＝(g_n({i_{n}，θ_{n})，α_{1：i})}，
[0173]
其中gn(in，θn)由一组任务嵌入组成，α1：i表示从任务到的卸载决策。此外，为了将有向无环图转换为任务嵌入序列，本发明根据秩值按降序对有向无环图的任务进行排序，可以定义为
[0174][0175]
其中ftin表示卸载和处理任务qin的等待时间，(i+1)n表示退出任务的集合。每个任务嵌入都由三个向量组成，分别嵌入当前任务的索引和直接前任和后继任务的索引
[0176]
7.2)在每个时隙t，本发明假设只有一个任务可以被决定。动作a
t
可以表示为
[0177]at
＝0，1，2，
…
，|{b}+1|，
[0178]
其中a
t
＝0表示任务在本地执行，a
t
＝{1，2，
…
，b}表示任务被卸载到边缘服务器，a
t
＝b+1表示此任务被卸载至云服务器。
[0179]
7.3)在每个时隙t，需要确定一个任务，并且系统根据当前状态s
t
选择最合适的卸载动作a
t
。在采取动作之后，移动边缘计算系统的状态从s
t
改变为s
t+1
。为了最小化所有用户的平均cft，本发明将时间步长t处的奖励定义为移动边缘计算系统中所有用户的cet加权和的负增量。那么系统奖励可以计算为
[0180][0181]
此外，本发明采用奖励塑造方法来选择满足训练过程中约束条件的行动。也就是说，本发明构建了一个奖励价值函数，通过设置惩罚来促使代理人满足约束条件，从而在不满足约束条件时减少奖励。
[0182]
提出了一个基于深度强化学习的框架，本发明将依赖性任务卸载问题建模为移动边缘计算网络中的马尔可夫决策过程。
[0183]
8.1)强化学习代理采用一种平衡的方法，包括开发和探索，以学习移动边缘计算网络并与之交互。开发的方法是利用通过贪婪学习获得的与q值相关的经验来利用相关经验，这可以描述为
[0184]
a＝{argmax}{q(s，a
′
；w)}
[0185]
其中w是参数矩阵。此外，勘探代理可以采取随机行动获取移动边缘计算环境信息。
[0186]
8.2)此外，代理人的目标是通过找到最佳行动值q
*
(s，a)和找到最佳决策π
*
，使长期累积报酬最大化。代理可以通过在状态s上按照策略π执行动作a来获得动作值q(s，a)。然后，本发明可以通过选择所有可能值中q(s，a)的最大值来获得最佳作用值q
*
(s，a)
[0187]
q*(s，a)＝{max}[r
t
|s
t
＝s，a
t
＝a，π]
[0188]
最优政策π*满足贝尔曼方程，并可优化作用值q*(s，a)，如下：
[0189]q*(s，a)
＝{e}
′s[r+γ{a
′
}{max}q(s
′
，a
′
)|s，a] (13)
[0190]
最佳行动值的步骤是从q(s，a)的下一步的所有可能行动中采取行动a，该行动可使r+q(s
′
，a
′
)最大化，并重复该行动，直到产生最佳策略。在每一轮迭代中，通过更新贝尔曼方程，q值不断增加，qt
→
q*作为t
→
∞，如
[0191]q{t+1}
(s，a)＝{e}
′s[r+γ{a
′
}{max}q
t
(s
′
，a
′
)|s，a]
[0192]
8.3)在本发明提出的dqn模型中，为了防止训练过程中的波动和错误，dqn模型引入了目标网络，该网络具有固定的参数w-。目标网络参数在某些情况下可以保持不变。另一个被称为具有参数w的主网络的神经网络可以从经验缓冲器中不断学习，每k步，主网络将其参数更新到目标网络，以最小化损失函数。具有q(s
′
，a
′
；w)的电流作用值与最佳q
*
(s’，a’)之间的均方误差可用固定项f代替：
[0193]
f＝r+γ{a
′
}{max}q(s
′
，a
′
；w)
[0194]
其中w-在先前迭代中更新。损失函数可由下式给出
[0195]
loss(w)＝{e}
{s，a，r}
[{e}_s[f|s，a]-q(s
′
，a
′
；w-)]
[0196]
实施例3：
[0197]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，包括以下步骤：
[0198]
1)建立所述多用户移动边缘计算系统，包括云端服务器、b个边缘基站和n个无线移动设备；每个基站均具有边缘服务器。
[0199]
2)获取边缘计算网络信息，包括云端服务器、边缘服务器、无线移动设备产生的任务信息；
[0200]
3)对于无线移动设备第n个应用程序，建立有向非循环图，以表示应用程序中i个依赖性子任务之间的依赖关系；
[0201]
4)根据有向非循环图，建立依赖性任务卸载时延和能耗模型；
[0202]
5)根据依赖性任务卸载时延和能耗模型，建立任务卸载决策模型，并利用马尔可夫决策方式对任务卸载决策模型进行解算，得到任务卸载决策。
[0203]
实施例4：
[0204]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，主要内容见实施例3，其中，所述有向非循环图具有入口节点和出口节点；其中，入口节点和出口节点分别表示应用程序的开始任务和结束任务；
[0205]
有向非循环图中所有任务根据秩值进行了降序排列；
[0206]
其中，任务q
in
的秩值rank(q
in
)如下所示：
[0207][0208]
式中，ft
in
表示卸载和处理任务q
in
的等待时间；(i+1)n表示退出任务的集合。rank(q
jn
)为任务q
jn
的秩值。
[0209]
实施例5：
[0210]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，主要内容见实施例3，其中，建立依赖性任务卸载时延和能耗模型的步骤包括：
[0211]
1)根据有向非循环图，将任务的一组直接前任表示为的一组直接前任表示为
[0212]
2)计算任务的最大完成时间，即：
[0213][0214]
式中，当在本地处理任务时，的就绪时间为任务为任务的最大完成时间；为在本地、边缘服务器或云服务器上执行任务的完成时间；
[0215]
3)将任务的本地执行时间表示为将本地平均计算能力表示为
[0216]
计算任务的本地执行时间和完成时间即：
[0217][0218][0219]
式中，为任务所需的cpu周期；
[0220]
4)计算在本地执行的任务的能耗即；
[0221][0222]
式中，κ为能耗系数；
[0223]
5)建立在边缘服务器端的任务的就绪时间即：
[0224][0225]
式中，分别表示本地到边缘服务器、边缘服务器b到边缘服务器b
′
的传输时间；
[0226]
6)计算从边缘服务器b到云服务器的传输时间6)计算从边缘服务器b到云服务器的传输时间为数据大小；为从边缘服务器b到云服务器的传输速率；
[0227]
计算任务在云服务器的执行时间fc为云服务器的计算能力；
[0228]
计算任务在云服务器的就绪时间即：
[0229][0230]
式中，为从边缘服务器到云服务器的传输时间；
[0231]
7)计算第n个应用程序的任务卸载时延与能量加权和
[0232]
其中，为移动设备的总能耗；本地能耗上传任务的能耗上传任务的能耗为单位能耗。
[0233]
实施例6：
[0234]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，主要内容见实施例3，其中，任务卸载决策模型的目标函数为：任务卸载总时延和总能量的加权和达到最小。
[0235]
实施例7：
[0236]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，主要内容见实施例3，其中，利用马尔可夫决策方式对任务卸载决策模型进行解算的步骤包括：
[0237]
1)建立任务卸载过程中的动作空间a和状态空间s；
[0238]
2)根据任务卸载决策模型的目标函数，定义出每次训练的系统奖励r
t
；
[0239]
3)基于系统奖励r
t
，确定任务卸载决策。
[0240]
实施例8：
[0241]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，主要内容见实施例3，其中，所述状态空间s如下所示：
[0242]
s＝{s|s＝(g_n({i_{n}，θ_{n})，α_{1：i})}； (8)
[0243]
式中，g_n({i_{n}，θ_{n})为任务嵌入，包括嵌入当前任务的索引和直接前任和后继任务的索引；α_{1：i}表示从任务到的卸载决策。
[0244]
动作空间a中，时隙t的动作a
t
如下所示：
[0245]at
＝0，1，2，
…
，|{b}+1|； (9)
[0246]
式中，a
t
＝0表示任务在本地执行，a
t
＝{1，2，
…
，b}表示任务被卸载到边缘服务器，a
t
＝b+1表示此任务被卸载至云服务器。
[0247]
实施例9：
[0248]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，主要内容见实施例3，其中，系统奖励r
t
如下所示：
[0249][0250]
式中，ξn为任务卸载总时延和总能量的加权和。
[0251]
实施例10：
[0252]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，主要内容见实施例3，其中，基于系统奖励r
t
，确定任务卸载决策的步骤包括：
[0253]
1)建立动作a的表达式，即：
[0254]
a＝{argmax}{q(s，a
′
；w)}； (11)
[0255]
式中，w是参数矩阵；s为状态；q为行动值；a
′
为动作；
[0256]
2)在状态s上按照策略π执行动作a，以获得动作值q(s，a)；
[0257]
3)改变动作a，重复步骤2)，获得多个动作值q(s，a)，以最大动作值作为最佳作用
值q
*
(s，a)，即：
[0258]
q*(s，a)＝{max}[r
t
|s
t
＝s，a
t
＝a，π]； (12)
[0259]
4)对最佳作用值q
*
(s，a)进行优化，得到：
[0260]q*(s，a)
＝{e}
′s[r+γ{a
′
}{max}q(s
′
，a
′
)|s，a] (13)
[0261]
式中，q
*(s，a)
为优化后的最佳作用值；γ为折扣因子；s
′
为状态；a
′
为动作；
[0262]
5)以优化后的最佳作用值作为下一步动作值q
{t+1}
(s，a)，即：
[0263]q{t+1}
(s，a)＝{e}
′s[r+γ{a
′
}{max}q
t
(s
′
，a
′
)|s，a]； (14)
[0264]
式中，r为奖励。e为时延和能量加权和。
[0265]
实施例11：
[0266]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，主要内容见实施例3，其中，动作值q(s
′
，a
′
；w)与最佳作用值q*(s
′
，a
′
)之间的均方误差f如下所示：
[0267]
f＝r+γ{a
′
}{max}q(s
′
，a
′
；w)； (15)
[0268]
式中，r为动作产生的奖励值。
[0269]
实施例12：
[0270]
一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，主要内容见实施例3，其中，确定任务卸载决策的过程中，迭代更新参数w矩阵时，使用的损失函数如下所示：
[0271]
loss(w)＝{e}
{s，a，r}
[{e}s[f|s，a]-q(s
′
，a
′
；w-)] (16)
[0272]
式中，w-为上一轮迭代的参数矩阵。

技术特征：
1.一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，其特征在于，包括以下步骤：1)建立所述多用户移动边缘计算系统，包括云端服务器、b个边缘基站和n个无线移动设备；每个基站均具有边缘服务器。2)获取边缘计算网络信息，包括云端服务器、边缘服务器、无线移动设备产生的任务信息；3)对于无线移动设备第n个应用程序，建立有向非循环图，以表示应用程序中i个依赖性子任务之间的依赖关系；4)根据有向非循环图，建立依赖性任务卸载时延和能耗模型；5)根据依赖性任务卸载时延和能耗模型，建立任务卸载决策模型，并利用马尔可夫决策方式对任务卸载决策模型进行解算，得到任务卸载决策。2.根据权利要求1所述的一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，其特征在于，所述有向非循环图具有入口节点和出口节点；其中，入口节点和出口节点分别表示应用程序的开始任务和结束任务；有向非循环图中所有任务根据秩值进行了降序排列；其中，任务q
in
的秩值rank(q
in
)如下所示：式中，ft
in
表示卸载和处理任务q
in
的等待时间；(i+1)n表示退出任务的集合。rank(q
jn
)为任务q
jn
的秩值。3.根据权利要求1所述的一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，其特征在于，建立依赖性任务卸载时延和能耗模型的步骤包括：1)根据有向非循环图，将任务的一组直接前任表示为pred2)计算任务的最大完成时间，即：式中，当在本地处理任务时，的就绪时间为任务为任务的最大完成时间；为在本地、边缘服务器或云服务器上执行任务的完成时间；3)将任务的本地执行时间表示为将本地平均计算能力表示为计算任务的本地执行时间和完成时间即：即：式中，为任务所需的cpu周期；
4)计算在本地执行的任务的能耗即；式中，κ为能耗系数；5)建立在边缘服务器端的任务的就绪时间即：式中，分别表示本地到边缘服务器、边缘服务器b到边缘服务器b
′
的传输时间；6)计算从边缘服务器b到云服务器的传输时间6)计算从边缘服务器b到云服务器的传输时间为数据大小；为从边缘服务器b到云服务器的传输速率；计算任务在云服务器的执行时间f
c
为云服务器的计算能力；计算任务在云服务器的就绪时间即：式中，为从边缘服务器到云服务器的传输时间；7)计算第n个应用程序的任务卸载时延与能量加权和其中，为移动设备的总能耗；本地能耗上传任务的能耗任务的能耗为单位能耗。4.根据权利要求3所述的一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，其特征在于，任务卸载决策模型的目标函数为：任务卸载总时延和总能量的加权和达到最小。5.根据权利要求1所述的一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，其特征在于，利用马尔可夫决策方式对任务卸载决策模型进行解算的步骤包括：1)建立任务卸载过程中的动作空间a和状态空间s；2)根据任务卸载决策模型的目标函数，定义出每次训练的系统奖励r
t
；3)基于系统奖励r
t
，确定任务卸载决策。6.根据权利要求5所述的一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，其特征在于，所述状态空间s如下所示：s＝{s|s＝(g_n({i_{n}，θ_{n})，α_{1：i})}；
ꢀꢀꢀꢀ
(8)式中，g_n({i_{n}，θ_{n})为任务嵌入，包括嵌入当前任务的索引和直接前任和后继任务的索引；α_{1：i}表示从任务到的卸载决策。动作空间a中，时隙t的动作a
t
如下所示：a
t
＝0，1，2，...，|{b}+1|；
ꢀꢀꢀꢀ
(9)式中，a
t
＝0表示任务在本地执行，a
t
＝{1，2，
…
，b}表示任务被卸载到边缘服务器，a
t
＝
b+1表示此任务被卸载至云服务器。7.根据权利要求5所述的一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，其特征在于，系统奖励r
t
如下所示：式中，ξ
n
为任务卸载总时延和总能量的加权和。8.根据权利要求5所述的一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，其特征在于，基于系统奖励r
t
，确定任务卸载决策的步骤包括：1)建立动作a的表达式，即：a＝{argmax}{q(s，a
′
；w)}；
ꢀꢀꢀꢀ
(11)式中，w是参数矩阵；s为状态；q为行动值；a
′
为动作；2)在状态s上按照策略π执行动作a，以获得动作值q(s，a)；3)改变动作a，重复步骤2)，获得多个动作值q(s，a)，以最大动作值作为最佳作用值q
*
(s，a)，即：q*(s，a)＝{max}[r
t
|s
t
＝s，a
t
＝a，π]；
ꢀꢀꢀꢀ
(12)4)对最佳作用值q
*
(s，a)进行优化，得到：q
*(s，a)
＝{e}
′
s
[r+γ{a
′
}{max}q(s
′
，a
′
)|s，a]
ꢀꢀꢀꢀ
(13)式中，q
*(s，a)
为优化后的最佳作用值；γ为折扣因子；s
′
为状态；a
′
为动作；5)以优化后的最佳作用值作为下一步动作值q
{t+1}
(s，a)，即：q
{t+1}
(s，a)＝{e}
′
s
[r+γ{a
′
}{max}q
t
(s
′
，a
′
)|s，a]；
ꢀꢀꢀꢀ
(14)式中，r为奖励。e为时延和能量加权和。9.根据权利要求8所述的一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，其特征在于，动作值q(s
′
，a
′
；w)与最佳作用值q*(s’，a’)之间的均方误差f如下所示：f＝r+γ{a
′
}{max}q(s
′
，a
′
；w)；
ꢀꢀꢀꢀ
(15)式中，r为动作产生的奖励值。10.根据权利要求8所述的一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，其特征在于，确定任务卸载决策的过程中，迭代更新参数w矩阵时，使用的损失函数如下所示：loss(w)＝{e}
{s，a，r}
[{e}
s
[f|s，a]-q(s
′
，a
′
；w-)]
ꢀꢀꢀꢀ
(16)式中，w-为上一轮迭代的参数矩阵。

技术总结
本发明公开一种基于边缘计算和深度强化学习的多用户依赖性任务卸载方法，步骤包括：1)建立多用户移动边缘计算系统；2)获取边缘计算网络信息，包括云端服务器、边缘服务器、无线移动设备产生的任务信息；3)对于无线移动设备第n个应用程序，建立有向非循环图，以表示应用程序中I个依赖性子任务之间的依赖关系；4)根据有向非循环图，建立依赖性任务卸载时延和能耗模型；5)根据依赖性任务卸载时延和能耗模型，建立任务卸载决策模型，并利用马尔可夫决策方式对任务卸载决策模型进行解算，得到任务卸载决策。本发明大大降低了无线移动设备的通信时延和能量成本，满足了用户需求，节约了链路成本。路成本。路成本。


技术研发人员：李秀华 李君楠 李辉 郝金隆 蔡春茂 范琪琳 杨正益 程路熙
受保护的技术使用者：重庆大学
技术研发日：2023.03.01
技术公布日：2023/7/19