(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 201910286347.X
(22)申请日 2019.04.10
(71)申请人 中国科学技术大学
地址 230026 安徽省合肥市包河区金寨路
96号
(72)发明人 谈海生 刘柳燕 李向阳 黄浩强
(74)专利代理机构 北京凯特来知识产权代理有
限公司 11260
代理人 郑立明 付久春
(51)Int.Cl.
G06F 9/50(2006.01)
G06F 9/48(2006.01)
(54)发明名称边缘计算中结合功能按需配置的有依赖关系任务的调度方法(57)摘要本发明公开了一种边缘计算中结合功能按需配置的有依赖关系任务的调度方法，包括：步骤1，获取网络和任务的相关参数，选取一初始化边缘服务器；步骤2，用步骤1的相关参数对边缘服务器进行贪心初始配置得出服务器配置信息；步骤3，用有向无环图表示步骤1中具有依赖关系的任务，并对有向无环图中任务进行拓扑排序成拓扑序列；步骤4，用步骤2的服务器配置信息对步骤3的拓扑序列迭代，算出各任务在各边缘服务器上运行最早结束的完成时间，得到任务的分配和调度方案；步骤5，在边缘服务器实际容量约束下，按照步骤4的任务的分配和调度方案对各任务进行分配和调度。该方法能在边缘计算环境中最小化一个由多个依赖任务组成的应用的完
成时间。权利要求书2页 说明书7页 附图3页CN 110069341 A 2019.07.30
C N 110069341
A
权 利 要 求 书1/2页CN 110069341 A
1.一种边缘计算中结合功能按需配置的有依赖关系任务的调度方法，其特征在于，包括：
步骤1，获取边缘计算网络和包含具有依赖关系任务的应用的相关参数，从边缘计算网络中选取一个边缘服务器作为处理所述应用输入和输出的初始化服务器；
步骤2，利用所述步骤1获取的应用的相关参数对所述边缘计算网络中的各边缘服务器进行贪心初始配置得出服务器配置信息；
步骤3，用有向无环图表示所述步骤1中的应用的具有依赖关系的任务，并对所述有向无环图中的任务进行拓扑排序，得到任务的拓扑序列；
步骤4，利用所述步骤2得出的服务器配置信息对所述步骤3得出的任务的拓扑序列迭代计算，计算出拓扑序列中每个任务放置在边缘计算网络的各边缘服务器上运行最早结束的完成时间并存储对应分配过程，根据最后一个任务完成时间反向搜索所存储的各分配过程来反向重建所有任务的分配和调度方案；
步骤5，在边缘服务器实际容量约束下，按照所述步骤4最终确定的任务的分配和调度方案对各任务进行分配和调度。
2.根据权利要求1所述的边缘计算中结合功能按需配置的有依赖关系任务的调度方法，其特征在于，所述方法的步骤1中，边缘计算网络包括：
一个远程云和多个异构的边缘服务器，每个边缘服务器具有有限容量，其中，任意两个边缘服务器之间的双向数据传输率相等。
3.根据权利要求1或2所述的边缘计算中结合功能按需配置的有依赖关系任务的调度方法，其特征在于，所述方法的步骤1中，获取边缘计算网络和包含具有依赖关系任务的应用的相关参数包括：
各任务在边缘计算网络的各边缘服务器上的运行时间以及各边缘服务器配置不同功能需花费的时间。
4.根据权利要求1或2所述的边缘计算中结合功能按需配置的有依赖关系任务的调度方法，其特征在于，所述方法的步骤2的利用所述步骤1获取的应用的相关参数对所述边缘计算网络中的边缘服务器进行贪心初始配置得出服务器配置信息中，在各边缘服务器上设置一个对应的数组记录配置功能的编号，配置过程包括以下步骤：
步骤21，在忽略边缘服务器的实际容量的前提下，贪心的确保每个任务在其运行时间最少的边缘服务器上配置好对应的功能，将功能的编号记录在该边缘服务器的数组中，并计算出当前配置下，边缘服务器中最大容量花费值作为虚拟容量；
步骤22，将所有边缘服务器的容量设为虚拟容量，对所述步骤21中未满配的边缘服务器继续进行如下配置：将所有任务在所有边缘服务器的运行时间从小到大排序，依次判断运行时间所对应的边缘服务器上是否已经满配，若满配，则跳过后续步骤，若未满配，判断未满配的边缘服务器是否已经配置任务对应的功能，若已配置，跳过后续步骤，否则，进行配置并保存到数组后再跳到下一个运行时间进行判断，直到所有的边缘服务器均配满。
5.根据权利要求4所述的边缘计算中结合功能按需配置的有依赖关系任务的调度方法，其特征在于，所述步骤22中，未满配是指配置的功能数小于边缘服务器的虚拟容量；
满配是指配置的功能数等于边缘服务器的虚拟容量。
6.根据权利要求1或2所述的边缘计算中结合功能按需配置的有依赖关系任务的调度
2