本发明涉及一种基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，属于无线通信网络领域。
背景技术：
1、随着通信技术的不断发展，出现了大量新颖的应用，如虚拟现实、增强现实、工业物联网、智能交通。这些应用通常是计算密集型，需要大量的通信和计算资源，这给受限于计算能力和能量限制的设备带来了巨大的挑战。移动边缘计算将云计算资源下沉到接入网络的边缘，为资源受限的物联网设备提供处理能力。具有低时延、低带宽成本、高数据安全性、更好的用户体验等优点。
2、考虑到物联网中任务复杂性，单一复杂任务通常由多个从属子任务组成。例如，人脸识别任务，主要由五个子任务组成，包括：输入图像、人脸检测、特征提取、人脸匹配、输出匹配结果。人脸检测需要输入图像，特征提取需要从人脸检测结果中提取特征，人脸匹配需要输入图像，需要从特征提取结果中获取特征，输出匹配结果需要从人脸匹配结果中获取匹配结果。因此，一般子任务间存在依赖关系，只有在前序子任务完成后，后续子任务才能执行。
3、近年来，边缘计算研究受到了广泛的关注。通过将任务卸载到边缘服务器中计算并返回，可以极大缓解终端处理复杂任务的压力。在边缘计算任务卸载过程中，复杂任务中子任务间的上述依赖关系应当纳入考虑。如[x.lv,h.du,and q.ye,“tbtoa:a dag-basedtask offloading scheme for mobile edge computing,”in icc 2022-ieeeinternational conference on communications,2022,pp.4607–4612]等人利用有向图建模了子任务关系，设计了相关算法实现子任务的合理卸载，在本地设备能量有限的情况下，尽可能的减少了任务处理延迟。[j.li,y.shang,m.qin,q.yang,n.cheng,w.gao,andk.s.kwak,“multiobjective oriented task scheduling in heterogeneous mobileedge computing networks,”ieee transactions on vehicular technology,vol.71,no.8,pp.8955–8966,2022.]中，将具有依赖性子任务的卸载问题建模为多目标优化过程，通过求解该问题实现任务完成时间和终端能耗的双重降低。然而，以往工作未严格考虑本地设备的能量约束。事实上，若对本地设备能耗考虑不周全，易导致本地能量过早消耗殆尽，使得本地留存子任务无法处理、或者无法上传边缘服务器，最终可能会导致整个任务无法完成的不利后果。
技术实现思路
1、针对现有技术的不足，本发明提出一种基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，用于解决本地设备能量有限的前提下以最小化时延来调度任务相关问题。
2、本发明提出了一种能量预分配机制，为剩余未调度的子任务预留一定能量，以保证整个任务的顺利完成。在此基础上，为更好减少延迟，提出了一种基于能量需求率的改进能量预分配机制。
3、本发明的技术方案为：
4、一种基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，该方法应用于边缘计算网络，以尽可能小的时延完成任务；边缘计算网络包括若干边缘服务器、一个用户设备，边缘服务器位置是均匀分布在边缘计算网络中；用户设备基于时延最小原则为每个子任务选择最合适的服务器，在执行完所有子任务后，将计算处理完的结果回传给用户；包括：
5、单一用户设备拥有由有向无环图(dag)表示的计算密集型任务；包括一系列子任务；一组异构边缘服务器在边缘计算网络中部署，每个子任务被调度到边缘服务器或在本地执行；
6、优先计算出各个子任务优先级，根据优先级大小来依次调度子任务；
7、根据信道条件计算得到本地设备传输子任务至边缘服务器花费的时间及消耗的本地设备能量或者本地计算时花费的时间及消耗的本地设备能量；
8、根据边缘服务器、本地设备的卸载任务计算时间以及根据能量预分配机制来分配给调度每个子任务的能量值，调度每个子任务至最合适的服务器，并得到其调度消耗的本地设备能量；
9、执行完所有的子任务后，将计算处理完的结果回传给用户，得到最终的完成时延。
10、根据本发明优选的，计算密集型任务建模为g＝(v，e)，其中，v是一系列子任务节点的集合，假设每个子任务在执行期间都是不可中断的；每个子任务vi＝(bi，ci)，其中，bi表示子任务的数据大小，ci表示子任务所需要的cpu周期数；e是子任务之间边的集合，e＝eij|i,j∈v，表示每个子任务之间的约束；边的权重ωij表示从子任务vi向vj传输的结果大小；使用pred(vi)表示子任务vi的前序节点，使用succ(vi)表示子任务vi的后继节点；一组异构边缘服务器s＝{s0，s1，s2，...，sm}在边缘计算网络中部署，将s0标记为用户设备，每个子任务被调度到边缘服务器或在本地执行。
11、根据本发明优选的，计算出子任务的优先级等级，用下式(i)、(ii)、(iii)表示：
12、
13、pct表是一个|v|×|s|的矩阵：行表示子任务的数量,列表示服务器的数量，每个元素pct(vi，sm)表示子任务vi卸载到服务器sm后，剩余子任务最短完成时间的最大值；递归得到上述pct表的所有值；用下式(ii)表示:
14、
15、其中，如果子任务vi，vj都在本地计算或者在相同服务器时，则为0；
16、在计算得到pct表之后，用下式(iii)计算得到每个子任务的优先级：
17、
18、在获得每个子任务的等级后，按降序排列优先级列表sdsort，子任务的值越高表示优先级越高。
19、根据本发明优选的，分析通信模型，根据信道条件计算得到传输子任务至边缘服务器花费的时间、消耗的本地设备能量；具体计算表达式如下：
20、当某个子任务或者某个子任务的结果需要从本地设备传输到其他服务器时，传输速率用下式(iv)表示：
21、
22、其中，b0m表示本地设备和服务器之间的信道带宽，表示本地设备的传输功率，n0表示白噪声功率，g0m表示本地设备和服务器之间的信道功率增益，定义如式(v)：
23、
24、其中，d0m表示本地设备和服务器之间的距离，α表示路径损耗系数；
25、使用二进制|v|×|s|矩阵y来表示卸载决策；如果子任务vi被卸载到sm处，矩阵的相关元素yim表示为1，否则为0；基于此，一个合理的调度满足如下式(vi)约束：
26、
27、如果子任务vi被卸载到sm,那么卸载时延即传输子任务至边缘服务器花费的时间表示为下式(vii)：
28、
29、其中，m＝0表示子任务vi在本地执行，卸载时延为0；
30、对于边eij，因为子任务vi要传输其计算结果给vj,故传输时延表达如下式(viii):
31、
32、其中，wij表示传输子任务结果的大小；
33、若子任务vi被卸载到边缘服务器，本地设备传输子任务至边缘服务器消耗的本地设备能量用式(ix)表示：
34、
35、对于边eij，如果子任务vi本地设备执行并且子任务vj被卸载到边缘服务器执行，本地设备传输子任务vi的结果给相应的服务器需要花费的能量如下式(x)：
36、
37、根据本发明优选的，计算模型包括本地计算模型和边缘计算模型；分析计算模型，得到本地设备传输子任务的结果至边缘服务器花费的时间、消耗的本地设备能量；包括：
38、如果子任务vi本地执行的话，本地执行时延即本地设备传输子任务的结果至边缘服务器花费的时间如下式(xi)表示:
39、
40、其中，ci表示完成子任务所需要的cpu周期数，f0表示本地设备的计算能力；
41、本地设备传输子任务vi的结果至边缘服务器消耗的本地设备能量表示为式(xii)：
42、
43、其中，本地设备运行一个cpu周期的平均能量消耗为
44、如果子任务vi被卸载到边缘服务器sm执行，计算时延被表示为式(xiii)):
45、
46、其中，fm表示边缘服务器的计算能力大小；
47、因此，得到调度子任务vj时消耗的本地设备能量如式(xiv)：
48、
49、其中，子任务vi被卸载到sm，子任务vj被卸载到sn；表示指示函数，如果括号中输入为true的话则输出1，否则输出0；等式前一项表示子任务vj本地计算或者卸载时花费的本地设备能量，除此之外，它也考虑了子任务结果传输的本地设备能量消耗；
50、因此，执行整个任务本地设备的能量消耗表示如下式(xv)：
51、
52、则完成整个任务消耗的本地设备能量需要满足下列(xvi)约束：
53、
54、根据本发明优选的，分析时延模型；具有依赖关系的任务整个执行时延是从初始任务开始到最后一个任务的完成，子任务vi在设备sm上执行的最早开始时间表示如下式(xvii)：
55、
56、其中，auail(sm)表示服务器sm的最早空闲时间，afu(i，m)是子任务vi从本地设备实际到达服务器sm的时间，具体表达式如式(xviii)所示；最后一项表示如果子任务vi将被执行的话，其所依赖的所有前序子任务必须被完成并且结果数据必须被传输过来；
57、
58、其中，pq表示优先级队列，从头到尾降序存储着比子任务vi优先级更高的子任务；m′子任务被卸载到的服务器；式中第一项表示优先级高于vi的子任务被调度到相应服务器时的传输延迟，第二项表示子任务vi被调度到sm时的传输时延；
59、在获得了est(vi，sm)之后，计算得到子任务vi的最早结束时间如下式(xix)所示:
60、
61、获得整个任务的结束时间如下式(xx)所示:
62、eft(g)＝eft(vexit). (xx)
63、因此，在这个问题中，目标是在本地设备能量有限的前提下获得一个最优的任务卸载决策以极可能的减少卸载时延，问题模型如下式(xxi)所示:
64、
65、
66、其中，y表示子任务与服务器之间的最优匹配矩阵；约束条件中第一项和第二项表示每个子任务应该被卸载到一个设备处；第三项和第四项不等式保证了每个子任务的最早开始时间需要满足约束；最后一项表示本地设备的能量约束。
67、根据本发明优选的，根据边缘服务器、本地设备的卸载任务计算时间以及根据能量预分配机制来分配给调度每个子任务的能量值，调度每个子任务至最合适的服务器，并得到其调度消耗的本地设备能量；包括：
68、任务优先级列表由式(iii)得到并且表示为sdsort＝{v′1，v′2，...，v′n}，其中，n是子任务数量；当调度子任务vi时，已经调度了的子任务集合表示为{v′1，v′2，...，v′i-1}，未调度的子任务集合为{v′i+1，…，v′n},因此，优化问题中的本地设备能量约束flocal转换为式(xxii)：
69、
70、其中，第一项表示已经调度的子任务消耗的本地设备能量，第二项表示目前正在被调度的子任务，第三项表示未调度的子任务花费的本地设备能量；因为efu是未知的，假设这些子任务是调度在消耗最少的本地设备能量的服务器上，因此，式(xxii)转换为式(xxiii)：
71、
72、其中，emin表示每个子任务的最小能量需求；使用遗传算法确定场景中本地设备完成整个dag任务所需的最小能量需求emin(g)，将最小能量需求emin(g)下各子任务所需的本地设备能量消耗近似为emin(vi)；因此，使用下式(xxiv)转换本地设备能量约束至每个子任务：
73、
74、通过上式，得到了调度每个子任务时的能量约束；
75、能量需求率定义为每个子任务的最小能量需求除以完成整个任务的最小能量需求，计算公式未下式(xxv):
76、
77、可分配能量定义为给定的能量约束减去任务的最小能量消耗需求，计算公式为(xxvi):
78、δeae(g)＝elocal-emin(g). (xxvi)
79、基于能量需求率的能量预分配机制，如下式(xxvii)所示：
80、etae(vi)＝emin(vi)+δeae(g)×edr(vi). (xxvii)
81、所以，式(xxiv)被转化为下式(xxviii)：
82、
83、至此，已经合理地分解本地设备能量约束至每个子任务；
84、调度子任务至合适的服务器时，采用如下式(xxix)、(xxx)准则:
85、oeft(vi，sm)＝eft(vi，sm)+pct(ci，sm)
86、
87、当为子任务vi选择最合适的服务器时，本地设备能量约束需要被考虑，在能量约束下，选择完成时延最短的服务器。
88、一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现基于能量预分配机制的边缘计算网络依赖任务卸载调度方法的步骤。
89、一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现基于能量预分配机制的边缘计算网络依赖任务卸载调度方法的步骤。
90、本发明的有益效果为：
91、1.本发明基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，针对边缘计算网络，充分利用本地设备和服务器的计算资源，从而使得边缘服务器在卸载任务中充分发挥作用，降低整个系统的完成时延，提升网络性能。
92、2.本发明提出了一种基于能量预分配机制的任务卸载方法，该方法核心是为合理地给未调度的子任务预分配一定部分的能量来保证任务的顺利完成，以最小化任务的完成时延为目标，根据本地设备与每个边缘服务器的信道容量、计算能力，将每个子任务调度到最合适的设备上。
93、3.在本发明基于能量预分配机制的边缘计算网络依赖任务卸载调度方法中，与现有技术即边缘服务器卸载计算不同的是，该方法充分考虑了每个边缘服务器的计算资源、通信资源、存储能力以及严格考虑本地设备的能量限制，为每个子任务确定最合适的服务器，来最小化完成时延。
1.一种基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，其特征在于，该方法应用于边缘计算网络，边缘计算网络包括若干边缘服务器、一个用户设备，边缘服务器位置是均匀分布在边缘计算网络中；用户设备基于时延最小原则为每个子任务选择最合适的服务器，在执行完所有子任务后，将计算处理完的结果回传给用户；包括：
2.根据权利要求1所述的一种基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，其特征在于，计算密集型任务建模为g＝(v，e)，其中，v是一系列子任务节点的集合，假设每个子任务在执行期间都是不可中断的；每个子任务vi＝(bi，ci)，其中，bi表示子任务的数据大小，ci表示子任务所需要的cpu周期数；e是子任务之间边的集合，e＝eij|i，j∈v，表示每个子任务之间的约束；边的权重wij表示从子任务vi向vj传输的结果大小；使用pred(vi)表示子任务vi的前序节点，使用succ(vi)表示子任务vi的后继节点；一组异构边缘服务器s＝{s0，s1，s2，...，sm}在边缘计算网络中部署，将s0标记为用户设备，每个子任务被调度到边缘服务器或在本地执行。
3.根据权利要求1所述的一种基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，其特征在于，计算出子任务的优先级等级，用下式(i)、(ii)、(iii)表示：
4.根据权利要求1所述的一种基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，其特征在于，分析通信模型，根据信道条件计算得到传输子任务至边缘服务器花费的时间、消耗的本地设备能量；具体计算表达式如下：
5.根据权利要求1所述的一种基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，其特征在于，分析计算模型，得到本地设备传输子任务的结果至边缘服务器花费的时间、消耗的本地设备能量；包括：
6.根据权利要求1所述的一种基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，其特征在于，分析时延模型；具有依赖关系的任务整个执行时延是从初始任务开始到最后一个任务的完成，子任务vi在设备sm上执行的最早开始时间表示如下式(xvii)：
7.根据权利要求1-6任一所述的一种基于能量预分配机制的边缘计算网络依赖任务卸载调度方法，其特征在于，根据边缘服务器、本地设备的卸载任务计算时间以及根据能量预分配机制来分配给调度每个子任务的能量值，调度每个子任务至最合适的服务器，并得到其调度消耗的本地设备能量；包括：
8.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1-7任一基于能量预分配机制的边缘计算网络依赖任务卸载调度方法的步骤。
9.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1-7任一基于能量预分配机制的边缘计算网络依赖任务卸载调度方法的步骤。
