云边端满足截止时间要求的资源代价最小的任务卸载方法

1.本发明涉及一种云边端满足截止时间要求的资源代价最小的任务卸载方法。


背景技术：

2.随着在线游戏、图像信号实时处理、增强现实和实时翻译服务等计算密集型和延迟敏感型移动任务的大规模增长，给移动移动终端(md)带来了巨大的计算需求，但移动移动终端如手机、平板电脑、vr等，它们的电量和计算能力有限，很难满足这些任务对长时间续航和低延迟的需求。云服务器有强大的计算能力，能够完成移动终端无法完成的大量计算问题，但移动终端通常距离云服务器较远，将大量数据上传到云服务器时不可避免会产生大量的能耗和传输时延，很难满足用户的高服务质量要求。
3.移动边缘计算(mobile edge computing，简称mec)在近移动终端的网络边缘布置服务器，将远程云端提供服务和计算的能力缩短到距离移动终端更近的位置，从而以较低的时延和服务器进行数据传输，提高服务器的处理效率。当移动终端提交任务时，可以选择在计算能力较强的边缘服务器进行数据处理，不需要传输到云端处理，减少数据的传输时间，提高任务的处理效率。因而，移动边缘计算计算模式很好地解决了移动设备能力有限、云计算模式时延较高的问题。与云计算相比，边缘计算提供的计算、网络及存储资源还是有限的。当大量用户同时向边缘服务器提交任务卸载请求时，不可避免带来用户会对边缘服务器资源的竞争，不合理的任务卸载可能会导致计算、存储、网络等资源利用不充分，存在忙闲不均的情况，严重降低了边缘计算的服务效率，造成服务质量下降。因此，多用户同时向资源受限的边缘服务器提交任务卸载请求的边缘计算资源分配问题非常值得研究。
4.现有中，将移动任务卸载问题转化为马尔可夫决策过程，根据移动任务缓冲区的排队状态、本地处理单元的执行状态以及传输单元的状态对移动任务进行调度。通过分析完成每个任务的平均时间和移动设备的平均能耗，建模功率约束的移动任务时延最小化问题，通过一维搜索算法找到问题的最佳卸载策略。现有还提出一种多用户协作移动边缘计算系统，通过优化任务分配、时间分配和功率分配来最小化本地用户的计算时延。上述的工作都是从理论层面出发，通过大量仿真实验验证结果的有效性。在真实环境条件下，如果仅考虑最小化时延卸载，由于移动设备的电池容量有限，当电池能量耗尽时，相应的任务处理就会中断，相应的决策就无法继续进行下去。在真实环境条件下，通过优化设备的发射功率和网络链路的质量降低能耗，虽然降低了能耗，但由于网络环境是随时间变化而变化的，设备在低功率状态下可能导致高时延。
5.现有还提出一种“端-边-云”协同的5g车联网边缘计算模型，针对该系统模型设计了深度强学习和深度强化学习协同的分布式服务卸载方法，该方法能够降低0.4％-20.4％的用户平均服务时延和能耗。虽然综合考虑了减少时延和降低能耗，但没有考虑任务之间的依赖关系，然而在现实中每一个移动终端都会产生多个任务，这些任务之间可能会产生一定的依赖关系，如人脸识别任务，目标跟踪任务等，这时如果仅考虑单任务计算卸载，可能会引起具有依赖关系的任务卸载失败，从而引起连锁反应导致卸载结果与预期出现较大
偏差。


技术实现要素：

6.为了解决上述技术问题，本发明提供一种云边端满足截止时间要求的资源代价最小的任务卸载方法。
7.本发明采用以下技术方案：
8.一种云边端满足截止时间要求的资源代价最小的任务卸载方法，包括：
9.计算所有设备完成所有任务的时间和能耗，并分别存储在时间矩阵和能耗矩阵中；
10.分别将时间矩阵和能耗矩阵中的所有元素进行归一化处理；
11.设定每个任务的目标权重向量，所述目标权重向量包括设备对任务的时间和能耗的目标权重；
12.对归一化处理后的时间矩阵和能耗矩阵采用加权算术平均算子对目标代价值进行加权求和，求出设备完成任务付出的代价值，并将求解得到的代价值存放在资源代价矩阵中；
13.通过匈牙利算法，基于为任务匹配最小代价的设备，为所有任务匹配最佳资源，得到所有任务的最佳卸载方案。
14.在一个实施例中，所述通过匈牙利算法，基于为任务匹配最小代价的设备，为所有任务匹配最佳资源，得到所有任务的最佳卸载方案，包括：
15.初始化卸载策略，并从任务节点集合中随机选择一个移动任务，卸载策略初始化为空集，已卸载任务集合初始化为空集；
16.遍历当前任务可卸载设备资源节点集合，并选择最小代价卸载，更新卸载策略；将任务从任务节点集合中删除并插入到已卸载任务集合中；
17.若卸载到该设备资源上使得决策值的叠加值大于等于1，则说明存在设备资源竞争，使用匈牙利算法解决资源竞争并选择出最优卸载方案并更新卸载策略；
18.当任务节点集合为空集时，此时以达到最大匹配数量，得出最佳卸载决策。
19.在一个实施例中，所述所有设备完成所有任务的时间和能耗的计算过程如下：
20.获取每一个移动终端处理其所产生的移动任务所需的时间，每一个移动终端产生的移动任务卸载到对应虚拟机进行处理所需的时间，以及当每一个移动设备产生的移动任务卸载到云服务器上的虚拟机处理时，虚拟机处理任务所需的时间；并结合对应权重，做加权求和运算，得到所有设备完成所有任务的时间；
21.获取每一个移动终端处理其所产生的移动任务产生的能耗，每一个移动终端产生的移动任务卸载到对应虚拟机进行处理产生的能耗，以及当每一个移动设备产生的移动任务卸载到云服务器上的虚拟机处理时，虚拟机处理任务产生的能耗；并结合对应权重，做加权求和运算，得到所有设备完成所有任务的能耗；
22.相应地，根据所有设备完成所有任务的时间和能耗，结合任务全部在本地计算的总时间和总能耗，以及系统代价中计算时延和计算能耗所占比重，得到系统代价；
23.基于系统代价最小，将计算卸载决策问题转换为有约束条件下，系统代价的最小化问题。
24.本发明的有益效果包括：在云边端环境下，针对移动设备处理能力有限、边缘服务器资源有限和任务服务质量需求难满足问题，提出满足截至时间要求的最小化资源代价的移动任务卸载方法，首先根据移动任务在不同设备资源上进行处理花费的时间和能耗，结合目标规划算法给出资源处理任务代价函数，计算资源处理任务的代价，将多服务质量满足问题转化成最小资源代价的任务卸载问题，然后通过匈牙利匹配算法为任务匹配合适的资源并不断解决任务资源需求的冲突，使得全体任务的卸载方案满足系统总的代价最小，能够满足任务处理截止时间的前提下最小化系统总代价，表现出较好的处理性能。
附图说明
25.图1是本技术实施例提供的云边端协同卸载多任务的系统架构图；
26.图2是任务处理过程示意图；
27.图3是本技术实施例提供的一种云边端满足截止时间要求的资源代价最小的任务卸载方法的整体流程示意图；
28.图4是云边端计算具体环境示例图；
29.图5是目标跟踪任务的处理过程图；
30.图6是ω1与时间关系示意图；
31.图7是ω1与能耗关系示意图；
32.图8是ω1与代价关系示意图；
33.图9是不同移动终端数量下系统总时延曲线图；
34.图10是不同移动终端数量下系统总能耗曲线图；
35.图11是不同虚拟机数量下的计算时间曲线图；
36.图12是不同虚拟机数量下的计算能耗曲线图；
37.图13是不同网络带宽下的系统总时延曲线图；
38.图14是不同网络带宽下的系统总能耗曲线图。
具体实施方式
39.本技术实施例提供的一种云边端满足截止时间要求的资源代价最小的任务卸载方法，针对移动设备处理能力有限、边缘服务器资源有限和任务服务质量需求难满足场景下开展满足任务处理时延要求的最小化资源处理代价的研究，具体工作如下：(1)建模云边端协同的边缘计算框架，移动任务模型，本地计算、边缘计算和云计算的计算时间模型和计算能耗模型，提出了边缘服务器中资源最小代价模型。(2)基于目标规划算法和匈牙利算法，提出一种资源代价最小的移动任务卸载算法(mcdroa，mobile task offloading algorithm with minimized resource cost that satisfies the as-of-time requirement)求解满足任务时延要求的最小化资源代价的卸载策略，依据处理任务花费的时间和能耗，算法首先通过目标规划算法计算每个资源处理任务花付出的代价，然后基于匈牙利算法不断寻优求出资源最小代价方案，使系统以总的最小代价完成所有任务。
40.首先介绍云边端系统和移动任务建模。其中，云边端系统建模具体如下：
41.图1是云计算、边缘计算、移动终端(三者简称云边端)协同卸载任务的系统架构，主要包括云服务器、边缘服务器、移动终端3种物理设备，使用云服务器、边缘服务器虚拟出
来的虚拟机(vm)向移动终端任务提供服务。每个移动终端可以与边缘服务器建立蜂窝连接，也可以与云服务器建立链接，本实施例研究针对不同的移动终端提交的任务对时延和能耗的不同需求，动态调整执行任务执行策略和虚拟机资源配置策略来优化整个系统的服务性能，同时降低系统运营代价。
42.对于移动终端：移动终端是产生任务的环境，移动任务如人脸识别、目标跟踪、在线游戏等，本实施例假设每个移动终端都只运行一个移动应用。移动应用可以产生多个具有依赖关系的任务，每个任务可以选择移动设备计算、边缘服务器中的虚拟机计算或云服务器中的虚拟机处理。
43.设移动移动终端集合表示为mb＝{mb1,mb2,
…
,mbk}，每一个移动终端可表示为一个三元组mbk＝{ak,ok,memoryk}，其中，k为移动终端的索引，ak表示移动终端总的计算能力(即单位时间内cpu周期数目)，ok表示移动终端当前处理能力占比，memoryk表示移动终端可用内存资源。
44.对于边缘服务器：边缘服务器部署在靠近移动终端的网络边缘，为移动终端提交的任务提供计算、网络和存储等服务。
45.边缘服务器集合表示为es＝{es1,es2,
…
,esm}，每个边缘服务器可表示为一个五元组esm＝{am,om,memorym,erm,epm}，其中，m为边缘服务器的索引，am表示边缘服务器esm总的计算能力，om表示边缘服务器esm当前的处理能力占比，memorym表示边缘服务器esm的可用内存资源，erm表示边缘服务器与移动移动终端之间的数据传输速率，epm表示边缘服务器esm的发射功率。
46.对于云服务器：云服务器集合表示为cs＝{cs1,cs2,...,cs
l
}，每个云服务器可表示为一个三元组cs
l
＝{f
l
,cr
l
,cp
l
}。其中，l为云服务器的索引，f
l
表示云服务器cs
l
总的计算能力，cr
l
表示云服务器cs
l
与移动终端之间的数据传输速度，cp
l
表示云服务器cs
l
的发射功率。
47.对于虚拟机：虚拟机是指在服务器(云服务器或边缘服务器)上利用虚拟化技术按照任务的需求虚拟出的计算机，用于执行某类型任务，所有虚拟机组成一个虚拟机池，由调度中心按某种策略将虚拟机分配给任务使用。一个虚拟机vm
ij
可用一个四元组表示其中cpui为虚拟机所在的服务器的可用处理能力大小，memoryi为虚拟机所在的服务器的可用内存大小，为虚拟机vm
ij
从服务器的cpui分到的cpu百分比，为虚拟机vm
ij
从服务器的memoryi分到的内存百分比。当任务卸载到边缘服务器或者云服务器上进行数据处理时，实际是在服务器虚拟出来的虚拟机上进行处理。
48.移动任务建模具体如下：移动任务是移动终端上运行的移动应用提交的任务，如人脸识别任务、求方程的根任务等，任务一般分为独立任务和依赖任务两种。独立任务表示任务是不可分割的，如求方程的根；依赖任务表示任务可自动划分为多个具有前后关系依赖关系的子任务，子任务之间可能存在数据交互，表现为一个子任务不能在获得它的父任务所有信息之前启动执行，如人脸识别任务。
49.本实施例假设移动移动终端mbk产生的移动应用包含n个具有依赖关系的子任务产生的移动应用包含n个具有依赖关系的子任务每个子任务可以表示为一个五元组其中，wj表示任务的计算量，用所需cpu周期数度量；f
min.j
表示处理任务t
jk
所需要的最小计
算能力；memoryj表示任务执行时所需要的最小内存资源；表示移动终端mbk产生的任务卸载时需要传输的数据量，t
max.j
表示任务允许的最大时延时间。
50.当任务卸载到边缘节点esm上，若边缘节点满足任务需要的计算资源和内存资源，则任务传输到该资源节点后立即进行数据处理，当边缘节点满足任务的存储资源但不满足cpu计算资源时，任务到达计算节点后先存储到内存中，等待计算资源完成若干个任务后释放cpu资源以达到任务需求后进行数据处理，具体处理过程如图2所示。
51.图2中，a1，a2，a3分别表示任务1、任务2和任务3到达边缘服务器esm的时间。假设当任务1和任务3到达节点后，该节点的资源大于任务所需要资源，任务到达节点之后立即执行。若任务2到达节点时，节点的剩余资源不能满足任务2的需求，则任务2不能立即执行。任务1完成后，立即释放其占有的资源，若此时可用总资源满足任务2的计算资源需求，则任务2开始执行。
52.移动任务处理模型与系统处理代价公式化描述：调度中心基于任务的处理时间代价和处理能耗代价向移动任务以虚拟机的方式分配物理资源。
53.对于移动任务处理时间模型：
54.(1)移动任务在本地设备上的处理时间：当移动终端的计算资源和内存资源都满足移动任务的资源需求，则该任务可选择在本地设备进行数据处理，此时移动终端处理该任务需要的时间取决于任务的计算量以及移动终端的处理能力。移动终端的当前处理能力fk为：
55.fk＝(1-ok)akꢀꢀ
(1)
56.其中，ak表示移动终端的总处理能力，ok表示移动终端当前可用处理能力占比。
57.移动终端mbk处理其所产生的移动任务所需的时间为：
[0058][0059]
其中，wj表示移动任务的计算量。
[0060]
(2)移动任务在边缘服务器上的处理时间：移动终端通过蜂窝网络将移动任务卸载到边缘服务器的虚拟机处理，移动任务的处理时间包括移动任务上传到虚拟机的传输时间、移动任务在虚拟机的等待时间、移动任务在虚拟机进行任务处理的处理时间和将任务处理结果返回给移动终端的传输时间。
[0061]
根据边缘服务器的资源是否满足虚拟机的资源要求，移动任务在边缘服务器esm上的处理时间分为以下两种情况：
[0062]
①
移动任务到达边缘服务器后，若服务器的当前可用计算资源和存储资源满足任务的资源需求，则生成虚拟机(表示为vmm)立即执行任务。边缘服务器的当前处理能力fm为：
[0063]fm
＝(1om)amꢀꢀ
(3)
[0064]
其中，am表示边缘服务器esm总的计算能力，om表示边缘服务器esm当前的负载(即当前处理能力占比)。
[0065]
移动终端mbk产生的移动任务卸载到虚拟机vmm进行处理所需的时间为：
[0066][0067]
其中表示移动任务卸载到虚拟机vmm的传输时间，表示移动任务在虚拟机vmm上的计算时间，表示虚拟机vmm将结果返回到移动终端的时间。
[0068]
移动终端产生的移动任务采用正交频分多址方案进行数据传输。为确保用户上行链路传输信道的正交性，假设移动与边缘服务器之间的每条链路只允许有1台设备占用。根据香农公式可知，移动终端mbk和虚拟机vmm的上行链路传输速率erm为：
[0069][0070]
其中，w为信道之间带宽，pk表示移动终端的发射功率，no表示信道内部的高斯噪声功率，h
k.m
表示移动终端mbk和虚拟机vmm之间的信道增益。
[0071]
移动终端mbk将移动任务上传到虚拟机vmm的传输时间为：
[0072][0073]
其中，表示移动终端产生的移动任务大小。和的值可通过式(7)和式(8)进行求解。
[0074][0075][0076]
其中，表示虚拟机从服务器上分到的计算能力百分比，表示虚拟机处理任务所得的计算结果数据的大小。
[0077]
②
任务到达边缘服务器esm后，若该边缘服务器当前剩余资源小于移动任务所要求的虚拟机所需资源。此时移动任务需要等到此服务器上的虚拟机执行完其上的任务并释放足够的资源后，方可生成虚拟机(表示为vmm)来执行任务其完成时间为式(9)：
[0078][0079]
其中，表示任务到达边缘服务器esm到虚拟机vmm开始处理任务这段等待时间。
[0080][0081]
(3)移动任务在云中心的处理时间：当移动设备mbk产生的移动任务t
jk
卸载到云服务器cs
l
上的虚拟机vm
l
处理时，vm
l
处理任务t
jk
所需的时间为：
[0082][0083]
其中，表示任务由移动终端传输到虚拟机vm
l
的时间，cpt
lj
表示任务在虚拟机vm
l
上的计算时间，表示任务在虚拟机vm
l
上计算的结果数据返回移动终端的时间。
[0084][0085][0086][0087]
其中，cr
l
表示云服务器cs
l
与移动终端mbk之间的数据传输速度，f
l
表示云服务器cs
l
的处理能力，为虚拟机vm
l
从服务器的cpu
l
分到的cpu百分比，表示虚拟机vm
l
处理任务所得到的结果数据集大小。
[0088]
移动任务处理能耗模型：
[0089]
(1)当任务选在在本地计算时，移动终端mbk处理移动任务产生的能耗如式(15)所示：
[0090][0091]
其中，表示移动终端1个cpu周期所产生的能耗，σ1表示移动终端开关电容(由芯片结构而定的开关电容)。
[0092]
(2)当移动终端mbk产生的移动任务卸载到边缘服务器esm生成的虚拟机vmm上计算时，假设模型中不考虑并行计算等到过程中的能耗，则vmm处理移动任务产生的能耗如式(16)所示：
[0093][0094][0095][0096][0097]
其中，表示移动任务由移动设备卸载到vmm产生的传输能耗，表示vmm处理移动任务产生的能耗，表示vmm将处理任务所得到的结果返回到移动终端的传输能耗，σ2×fi2
表示es
m 1个cpu周期所产生的能耗，epm表示边缘服务器esm的发射功率。
[0098]
(3)当移动终端mbk产生的任务卸载到云服务器cs
l
生成的虚拟机vm
l
上进行数据处理，虚拟机vm
l
处理移动任务产生的能耗如式(20)所示：
[0099][0100][0101][0102][0103]
其中，表示移动终端将任务卸载到虚拟机vm
l
过程中的传输能耗，表示虚拟机vm
l
处理移动任务所产生的能耗，表示虚拟机vm
l
将处理任务所得到的
结果返回到移动终端所产生的传输能耗，σ3×fl2
表示云服务器1个cpu周期所产生的能耗，cp
l
表示云服务器cs
l
的发射功率。
[0104]
系统最小总代价公式化描述：系统完成所有任务需要的总时间t
total
和总能耗e
total
如式(24)和式(25)所示。其中αk+αm+α
l
＝1，αk、αm和α
l
的取值由任务的执行位置决定。
[0105][0106][0107]
为了评价当前计算卸载策略的优劣，本实施例定义系统代价f为：
[0108][0109]
其中分别表示任务全部在本地计算的总时间和总能耗。ω1,ω2分别表示系统代价中计算时延和计算能耗所占比重。
[0110]
由式(26)可知，当t
total
,e
total
值越小，f值越小，因此为了实现系统总代价最小，可将计算卸载决策问题转换为有约束条件下f的最小化问题，即：
[0111][0112]
资源代价最小的移动任务卸载策略：在本实施例模型中，移动终端产生的移动任务可选择在移动终端、边缘服务器或云服务器(这三者统称为系统设备资源)进行处理。若终端任务选择卸载到边缘服务器或者云服务器上进行处理，服务器根据移动任务服务质量需求虚拟出虚拟机进行处理，本实施例假定虚拟机处理完任务后立即释放资源。无论哪个设备资源处理移动任务，都需要花费一定时间和能耗。本实施例根据任务在每个设备资源上花费的时间和能耗，通过目标规划算法得到每个设备资源处理每个任务付出的资源代价，并生成资源处理任务的代价矩阵。然后根据代价矩阵，通过匈牙利算法为任务匹配合适的系统设备资源，实现以总的最小代价完成所有任务。
[0113]
多标准目标规划算法评价资源处理任务的代价：目标规划算法主要用于解决多目标决策问题，通过多种标准来评价每个决策的优劣，从而选出最优的决策。由于目标和标准的多样性，多目标决策工作比较复杂，难以找到使所有目标都达到最佳的方案。目标规划算法通过将许多相互矛盾的目标(如在生产中既要保证产量大又要使产品产量高，成本低等)转换成一个目标来求解多目标决策。在本实施例中，根据移动任务在不同设备资源上进行处理花费的时间和能耗，通过目标规划算法评价每个设备资源处理当前任务需要付出的资源代价，将多目标卸载问题转化成最小代价卸载问题。基于此，本实施例提供一种云边端满足截止时间要求的资源代价最小的任务卸载方法，如图3所示，包括：
[0114]
步骤s1：计算所有设备完成所有任务的时间和能耗，并分别存储在时间矩阵和能
standard target planning algorithm，mstpa)，伪代码如表1所示：
[0131]
表1
[0132][0133][0134]
假设云边端计算环境由四个移动移动终端，一个边缘服务器和一个云服务器组成。边缘服务器虚拟处三个虚拟机，云服务器虚拟出一个虚拟机。每个移动终端生成移动应用包含若干个具有依赖关系的任务请求，具体如图4所示。
[0135]
移动移动终端产生的任务，可以选择在本地执行、卸载到边缘服务器虚拟机执行或者云服务器虚拟机执行。通过式(3)-式(24)计算出计算设备ri对任务t
jk
的时间代价和能耗代价。
[0136]
假定在图4所示的边缘计算环境中，移动终端产生的任务在每个设备上处理的时间和能耗如表2所示。本实施例不考虑移动移动终端产生的任务卸载到其他移动终端上进行处理，如移动设备mb1产生的任务t1、t2、t3不能卸载到移动设备mb2、mb3、mb4上进行数据处理，可视为此部分计算设备对移动任务的代价较高，所以将该部分数据设置为一个大于表中数据最大值的数值即可。
[0137]
表2
[0138][0139][0140][0141][0142]
通过式(28)将时间矩阵和能耗矩阵进行规范化，假设ω1＝ω2＝0.5，求得时间和能耗的归一化矩阵t,e以及代价矩阵d
t
分别为：
[0143]
[0144][0145][0146]
步骤s5：通过匈牙利算法，基于为任务匹配最小代价的设备，为所有任务匹配最佳资源，得到所有任务的最佳卸载方案：
[0147]
本实施例通过匈牙利算法为任务匹配最小代价的设备资源。匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，在云边端系统中，为了实现系统以总的最小代价完成所有任务，每个移动终端倾向于花费最低时间和能耗来卸载移动任务。这势必会导致一个资源竞争问题，具体地说，这是一个多任务对计算资源的非合作竞争。为解决资源竞争问题，通过匈牙利算法为任务匹配最小代价的设备资源制定，从整体上为所有任务匹配最佳资源，整体上得到所有任务的最佳卸载方案。任务设备资源匹配问题可表示为一个三元组：
[0148]dt
＝{t,r,f}
ꢀꢀ
(30)
[0149]
其中，t表示参与竞争的任务集合，r表示参与处理任务的设备资源集合，f表示所有参与者所采用的代价函数，这里使用式子(28)作为代价函数计算每个设备资源处理当前任务的代价值。为任务分配到一个设备资源称为任务获得匹配，令s＝{s1,s2,...,sn}表示系统当前最优卸载方案，si表示一个任务到具体设备资源的匹配。
[0150]
定义1：任务到设备资源集的最大匹配方案：任务集中尽可能多的任务获得设备资源匹配的方案。
[0151]
寻找最小代价最大匹配方案的过程就是不断寻找设备资源使得任务集中的任务尽可能多的完成卸载并且执行代价最小。系统在制定卸载决策过程中，通过式(31)寻求所有任务的最小代价和制定匹配方案。
[0152][0153]
其中，d
i.j
表示综合代价矩阵中的值，x
i.j
表示决策值，x
i.j
∈{0,1}，当x
i.j
取1时表示卸载到此设备资源上，c表示系统设备资源数。若当前匹配方案s使得：
[0154][0155]
此时匹配方案中存在设备资源竞争，通过匈牙利算法为存在设备资源竞争的任务集寻找最优匹配，在匹配过程不断为存在冲突的任务寻找最佳方案，使得尽可能多的任务获得匹配以达到最大匹配。将冲突设备资源存放在集合cr中，已卸载的任务存放在集合ut中，通过匈牙利算法解决冲突选出未匹配任务集合中的最小匹配代价值的过程，如下：
[0156][0157][0158]
其中表示d
t
变换后的矩阵。
[0159]
解决冲突后将找到的冲突任务的卸载方案添加到s中，继续递归寻找其他未参与卸载的任务，直到当前匹配方案满足：
[0160][0161]
此时任务到设备资源集的匹配达到最大匹配。
[0162]
确定：任务到设备资源集的最大匹配是最优匹配。当前最大匹配结果s一定是最优匹配，若在下次搜寻过程中出现设备资源竞争即：
[0163][0164]
此时对于匹配方案d
t
通过式(33)变换，变换后的结果重新选择最佳卸载方案满足：
[0165][0166]
将当前冲突任务的最佳卸载方案添加到s中。在不断寻找新的任务匹配过程中实时更新s。因此最后得到的匹配一定最大匹配且是最优的。
[0167]
通过上述匹配理论，基于匈牙利算法为所有任务寻找最佳决策s过程具体步骤如下：
[0168]
(1)初始化卸载策略，并从任务节点集合t中随机选择一个移动任务卸载策略已卸载任务集合即卸载策略初始化为空集，已卸载任务集合初始化为空集。
[0169]
(2)遍历当前任务可卸载设备资源节点集合r，并选择最小代价卸载，更新卸载策略s；将任务从任务节点集合中删除并插入到已卸载任务集合中，即：
[0170]
t
′←
t-{tj}，ut
←
{tj}
ꢀꢀ
(37)
[0171]
(3)若卸载到该设备资源上使得决策值的叠加值大于等于1，即则说明存在设备资源竞争，使用匈牙利算法解决资源竞争并选择出最优卸载方案s
*
并更新s，即：
[0172]s←s*
＝minf(s1,s2,
…
,si)(38)
[0173]
(4)当任务节点集合为空集时，即时，此时以达到最大匹配数量，得出最佳卸载决策s。
[0174]
表3为满足截至时间要求的最小化资源代价的移动任务卸载算法(mcdroa)对应的伪代码。
[0175]
表3
[0176][0177][0178]
假设系统中包含n个移动应用，m个计算设备资源，则mcdroa算法的时间复杂度为o(mn+mn2)。
[0179]
证明：mcdroa算法主要由两个部分组成：最小代价求解部分和任务匹配设备资源问题求解部分。首先通过mstpa算法计算任务在每个资源上处理付出的代价，其时间复杂度
为o(mn)；然后通过匈牙利算法进行资源匹配，在每次迭代中，都会增加匹配，因此需要n次迭代。在每次迭代中，寻找匹配时，每个任务资源匹配不超过一次，因此操作的复杂度为o(mn)，每次将匹配插入到匹配方案中都会更新方案，每次迭代发生不超过m次，更新松弛需要o(n)，该过程的时间复杂度为o(mn)，因此匈牙利匹配过程总的时间复杂度为o(mn2)。从而得到mcdroa算法的时间复杂度为o(mn+mn2)。
[0180]
多标准目标规划算法评价资源处理任务的代价中模拟任务场景产生的数据，已经通过多目标分配算法求解出设备资源综合代价矩阵d
t
，此时通过匈牙利算法求解卸载决策矩阵的过程如下：
[0181]
[0182]
[0183][0184]
从最后得到的矩阵可得出模拟任务场景中最优卸载方案为：
[0185]
t1→
ed1，t2→
mb1，t3→
cl1，t4→
mb2，t5→
ed3，t6→
mb3，t7→
ed2，t8→
mb4[0186]
如下给出仿真实验验证过程：
[0187]
(1)仿真实验环境：
[0188]
1)移动终端：实验中的移动终端选取a、b、c和d这四款手机，其详细的参数配置见表4，具体的功率值是通过移动终端的power-profile.xml文件获取得到。
[0189]
表4
[0190][0191][0192]
2)边缘服务器：采用由实验室2台服务器搭建的版本为juno的openstack集群环
境，2台服务器的操作系统是版本为ubuntu18.04(64位)的linux系统、cpu为intel(r)xeon(r)gold5117、主频是2.8ghz、内存大小是64g、硬盘容量是2t。
[0193]
3)网络环境：使用带宽为100gbps的无限带宽(ib)高速交换机进行边缘服务器的内部节点之间连接，交换机的型号为迈络思qsfp28；使用asus的千兆以太网交换机进行边缘服务器与外部设备连接，交换机型号为gigax024x。
[0194]
4)移动任务程序：在本实施例实验中选择目标跟踪作为移动任务，任务的处理过程如图5所示，具体包括输入运动模型、特征提取、观测模型、模型更新、合奏后处理、结果输出6个处理过程。其中输入运动模型和结果输出分别代表目标跟踪程序的开始和结束，只能在移动终端处理。
[0195]
(2)实验与分析：
[0196]
将提出的mcdroa方法与无延时激励服务卸载算法(lo-iso)、local计算卸载方法、edge计算卸载方法和random计算卸载方法进行对比，其中lo-iso方法首先估计移动设备总服务时延，然后考虑不同服务的独特优先级的情况下，通过激励服务卸载方案最大化用户利润。edge方法将任务全部放在边缘服务器进行处理。local方法将任务全部放在本地处理。random方法随机卸载任务到任意设备上进行处理。本节首先做权重因子对mcdroa方法性能影响的实验，然后做终端用户数量、边缘服务器设备以及网络带宽三个方面对卸载方法性能影响的实验。实验中使用的相关参数参考文献设定，具体数据如表5所示。
[0197]
表5
[0198][0199]
[0200]
1)权重因子影响实验：图6、图7和图8分别为系统在处理40个随机任务的情况下，ω1取不同值的情况下，系统的处理时间、处理能耗以及系统处理全部任务需要付出的总代价情况。
[0201]
从图6、图7和图8中可知，随着ω1的增加，系统的计算时间、计算能耗以及系统代价都是先减小后增加，其中当ω1取0.6时，系统的计算时间取最小值；当ω1取0.5时，系统的计算能耗和系统代价取最小值。从三个实验结果的变化趋势可看出，ω1的取值在0.5附近时对系统的计算时间、计算能耗和总代价影响较大。
[0202]
2)移动终端数量影响实验：本实验将每个边缘服务器资源虚拟出8个虚拟机，网络带宽设定为8mbps，具体的实验结果如图9和图10所示。
[0203]
从图9和图10可以看出，5种方法基本上都呈线性关系增加。这是因为当移动终端数量增加时，所产生的任务需要的计算资源量也随之增加，此时卸载的任务对信道资源和计算资源上的竞争比较激烈，以至于任务在卸载过程中没有按照合理的卸载顺序执行，导致任务在传输和计算过程产生过长的等待时间，因此时延越来越高，且增加越来越快。由于任务在等待过程中移动终端所消耗的能量可忽略不计，因此所有卸载方法的系统总能耗都是随着移动终端数量的增加呈线性趋势增加。从图9和图10可以看出，本实施例所提mcdroa方法都是最优的，因为mcdroa算法将任务集中的任务以总的最小代价卸载，从整体上考虑了任务的资源需求和所有可用的资源情况，整体上为任务分配最合适的资源，同时尽可能减少任务对资源的竞争，从而减小因任务等待而带来的等待时间。
[0204]
3)边缘服务器虚拟机数量影响实验：本实验设置40个移动移动终端，网络带宽为8mbps，具体的实验结果如图11和图12所示。
[0205]
从图11和图12可知：随着边缘服务器虚拟机数量的增加，mcdroa方法、lo-iso方法、edge方法和random方法的系统总时延和总能耗都会显著降低。由于虚拟机数量增多，任务对资源的竞争压力减小，边缘服务器能够同时满足多个终端任务请求。local方法的所有步骤都在本地执行，其卸载方法产生的时延和能耗不受边缘服务器虚拟机的影响，但其卸载方案产生的系统总时延和能耗相对较高。从两图可看出本实施例所提的mcdroa方法花费的时间和能耗都是最少的，这是因为lo-iso无时延激励算法虽然保证了任务的无时延卸载，但由于可能存在过多的任务竞争资源，导致总的完成时间较长。random策略不考虑任务的时延和能耗需求，随机的将任务卸载到匹配的资源上，这种卸载方案具有极大的偶然性，因此很难保证卸载方案是最优的。当虚拟机数量增加时，edge方法资源竞争压力随之减小，但该方法未考虑信道带宽的影响，这可能导致传输时间过长。当虚拟机数量不断增加时，本实施例所提的mcdroa算法更容易解决任务之间的资源竞争，可以保证任务得到更合理的卸载。
[0206]
4)网络带宽影响实验：本实验设定40个移动移动终端，16个边缘服务器提供的虚拟机，实验结果如图13和图14所示。
[0207]
从图13和图14可知：local卸载方法产生的时延和能耗不受边缘服务器虚拟机的影响。mcdroa方法、lo-iso方法、edge方法以及random方法的系统总时延和终端总能耗都随着网络带宽的增加先减小后趋于平稳。这是因为随着网络带宽增大，移动移动终端和边缘服务器之间的数据传输速率增大，从而任务传输时间减小，更多的任务上传到边缘服务器上进行数据处理，因此降低了任务完成的时间和移动终端的能耗。但当传输速率增大到一
定程度后，对任务的传输时间影响越来越小，从而对卸载方法的性能提升逐渐减弱。从两图可看出，不管是系统总时延还是系统总能耗方面对比，本实施例所提的mcdroa算法都是最优的，因为lo-iso方法通过激励机制保证任务无时延卸载，而未考虑链路资源竞争和能耗问题。random方法随机制定卸载方案，当网络带宽增加，数据传输时延减少，不合理的卸载方案概率减少，并不能保证卸载方案是最优的。随着网络带宽增加，网络带宽竞争压力不断减小，虽然edge方法将所有任务都卸载到边缘服务器进行处理，但边缘服务器的资源竞争压力并未减少，导致任务在处理过程中存在过多的等待时间。本实施例所提的mcdroa算法综合考虑任务的时间和能耗，随着网络带宽的增加，任务上传到服务器的时间不断降低，从而任务处理的时间不断减小，更多的任务适合在服务器上进行处理的，减小了终端设备的压力，因此任务处理的能耗不断减小。
[0208]
针对边缘计算的服务器资源有限和多约束目标问题，提出mcdroa算法。该算法首先根据目标规划算法给出资源处理任务代价函数，对资源处理任务的代价进行评估。然后，在任务卸载过程中根据任务对资源的需求，筛选不满足条件的资源集对其进行预处理，构造一个以系统最小总代价的效益函数，从资源集中为任务选择满足条件的资源集。最后，通过匈牙利算法为任务匹配合适的资源并不断解决资源冲突，使得卸载方案满足系统总的代价最小。仿真实验表明，本实施例所提的mcdroa算法在服务器资源有限条件下以系统总的最小代价能够降低完成任务花费的时间和能耗，具有较好的系统性能。实验中将本实施例算法与random、edge和local三种经典算法以及lo-iso算法进行比较，证明了本实施例算法的有效性。

技术特征：
1.一种云边端满足截止时间要求的资源代价最小的任务卸载方法，其特征在于，包括：计算所有设备完成所有任务的时间和能耗，并分别存储在时间矩阵和能耗矩阵中；分别将时间矩阵和能耗矩阵中的所有元素进行归一化处理；设定每个任务的目标权重向量，所述目标权重向量包括设备对任务的时间和能耗的目标权重；对归一化处理后的时间矩阵和能耗矩阵采用加权算术平均算子对目标代价值进行加权求和，求出设备完成任务付出的代价值，并将求解得到的代价值存放在资源代价矩阵中；通过匈牙利算法，基于为任务匹配最小代价的设备，为所有任务匹配最佳资源，得到所有任务的最佳卸载方案。2.根据权利要求1所述的云边端满足截止时间要求的资源代价最小的任务卸载方法，其特征在于，所述通过匈牙利算法，基于为任务匹配最小代价的设备，为所有任务匹配最佳资源，得到所有任务的最佳卸载方案，包括：初始化卸载策略，并从任务节点集合中随机选择一个移动任务，卸载策略初始化为空集，已卸载任务集合初始化为空集；遍历当前任务可卸载设备资源节点集合，并选择最小代价卸载，更新卸载策略；将任务从任务节点集合中删除并插入到已卸载任务集合中；若卸载到该设备资源上使得决策值的叠加值大于等于1，则说明存在设备资源竞争，使用匈牙利算法解决资源竞争并选择出最优卸载方案并更新卸载策略；当任务节点集合为空集时，此时以达到最大匹配数量，得出最佳卸载决策。3.根据权利要求1所述的云边端满足截止时间要求的资源代价最小的任务卸载方法，其特征在于，所述所有设备完成所有任务的时间和能耗的计算过程如下：获取每一个移动终端处理其所产生的移动任务所需的时间，每一个移动终端产生的移动任务卸载到对应虚拟机进行处理所需的时间，以及当每一个移动设备产生的移动任务卸载到云服务器上的虚拟机处理时，虚拟机处理任务所需的时间；并结合对应权重，做加权求和运算，得到所有设备完成所有任务的时间；获取每一个移动终端处理其所产生的移动任务产生的能耗，每一个移动终端产生的移动任务卸载到对应虚拟机进行处理产生的能耗，以及当每一个移动设备产生的移动任务卸载到云服务器上的虚拟机处理时，虚拟机处理任务产生的能耗；并结合对应权重，做加权求和运算，得到所有设备完成所有任务的能耗；相应地，根据所有设备完成所有任务的时间和能耗，结合任务全部在本地计算的总时间和总能耗，以及系统代价中计算时延和计算能耗所占比重，得到系统代价；基于系统代价最小，将计算卸载决策问题转换为有约束条件下，系统代价的最小化问题。

技术总结
本发明涉及一种云边端满足截止时间要求的资源代价最小的任务卸载方法，计算所有设备完成所有任务的时间和能耗，并分别存储在时间矩阵和能耗矩阵中；分别将时间矩阵和能耗矩阵中的所有元素进行归一化处理；设定每个任务的目标权重向量，采用加权算术平均算子对目标代价值进行加权求和，求出设备完成任务付出的代价值，并将求解得到的代价值存放在资源代价矩阵中；通过匈牙利算法，基于为任务匹配最小代价的设备，为所有任务匹配最佳资源，得到所有任务的最佳卸载方案，不断解决任务资源需求的冲突，使得全体任务的卸载方案满足系统总的代价最小，能够满足任务处理截止时间的前提下最小化系统总代价，表现出较好的处理性能。表现出较好的处理性能。表现出较好的处理性能。


技术研发人员：曹洁 贾连辉 许金超
受保护的技术使用者：郑州轻工业大学
技术研发日：2023.04.24
技术公布日：2023/7/12