(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211081358.2 (22)申请日 2022.09.05 (71)申请人 南京航空航天大 学 地址 211106 江苏省南京市江宁区将军大 道29号 (72)发明人 张强　葛笑　 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/50(2006.01) (54)发明名称 一种多云系统中带有能耗约束的计算卸载 方法 (57)摘要 本发明公开了一种多云系统中带有能耗约 束的计算卸载方法， 该方法综合考虑不同云节点 的优缺点和组合方式， 提出了基于任务路径和调 度优化的计算卸载方法， 从而减少移动终端的应 用完成时间。 该方法首先计算每个任务在各个工 作节点的执行时间和本地执行时间之差的平均 值， 根据任务对应的时间差平均值确定其调度顺 序。 对于排序后的任务， 以其作为目的任务， 利用 深度优先搜索查找入口任务到目的任务的多条 路径。 并根据路径上所有任务的计算负载之和确 定路径优先级。 该方法将路径上成功遍历的任务 看做一个整体进行工作节点分配， 从而减少具有 依赖关系的任务之间进行数据传输带来的延迟 和终端能耗。 此外， 本发明还对初始的调度结果 进行优化， 使得该方法能在能耗约束范围内获得 较低的应用完成时间。 权利要求书1页 说明书6页 附图1页 CN 115408132 A 2022.11.29 CN 115408132 A 1.一种多云系统中带有能耗约束的计算卸载 方法， 包括如下步骤： (1)任务排序、 路径建立和路径优先级计算方法。 (2)路径任务调度算法。 (3)面向能耗约束的优化 算法。 2.根据权利要求1所述的多云系统中带有能耗约束的计算卸载方法， 首先提出任务排 序、 路径建立和优先级计算方法： 移动应用中的任务具有依赖关系， 前驱任务必须执行完成， 后继任务才可以开始执行， 其依赖关系 可以用有向无环图表示。 应用执行 的工作节点包括各个云节点和移动终端。 计 算每个任务在各个工作节点执行 的时间和本地执行时间的差值绝对值， 然后求平均值， 并 作为任务 排序的依据。 任务 i对应的平均值pi的计算公式如下： 其中， 表示云节点k执行任务i对应的时间， 表示本地执行时间， M表示工作节点个 数， S表示工作节点集合。 平均值p较大的任务， 被优先进行路径建立和 工作节点分配。 以排 序后的任务作为目的任务， 利用深度优先搜索算法查找入口任务到目的任务的执行路径。 整个路径建立执行N次深度优先搜索算法， 从而生 成多条路径， N表 示任务个数。 对于生成的 路径， 计算每一条路径上的计算负载之和， 并作为其优先级， 优先对负载较大的路径分配工 作节点。 3.根据权利要求1所述的多云系统中带有能耗约束的计算卸载方法， 在权利要求2所述 的任务排序、 路径建立和优先级计算方法的基础上， 提出路径任务调度算法： 遍历路径上的每个任务， 找到第 一个没有被分配的任务作为此条路径分配的第 一个任 务， 然后继续遍历。 遍历结束的条件是遇到一个任务j存在未被分配的前驱任务， 同时该前 驱任务不在当前路径上。 当遍历结束时， 对任务j之前遍历的任务(成功遍历)进行调度， 对 任务j及其在该路径上的后继任务暂不调 度。 将路径上成功遍历的任务看作一个整体， 并分 配到同一个工作 节点。 遍历所有工作 节点， 选择完成时间最小值对应的工作 节点。 循环执行 上述步骤， 即路径选择和路径任务调度， 直到所有任务完成调度， 形成初始调度方案 。 4.根据权利要求1所述的多云系统中带有能耗约束的计算卸载方法， 在权利要求2和权 利要求3所述的任务调度算法的基础上， 提出面向能耗约束的优化算法， 包括以下两个部 分： (1)移动终端能耗大于约束值的情况： 根据任务的能耗值对任务降序排序， 单个任务的 能耗包括CPU处理能耗和数据传输能耗。 对于排序后的任务， 进行工作节点重分配。 对于当 前任务i， 遍历 所有工作节点(已分配的工作节点除外)进行分配， 确定终端能耗最小值Ek对 应的工作节点k， 并标记任务i为已处理。 如果Ek小于之前方案的终端能耗， 则将任务i分配 到节点k。 更新剩余任务的能耗 值， 按照上述方法对未处 理的任务进行迭代处 理。 (2)移动终端能耗小于等于约束值的情况： 将调度方案中的所有任务按完成时间降序 排列。 对于当前任务i， 使用贪婪算法生成调度方案， 记为节点k， 并标记任务i为已处理。 如 果其应用完成时间小于之前方案的应用完成时间并且能耗值满足约束 条件， 则更新调 度方 案。 更新剩余任务的完成时间， 按照上述方法对未处 理的任务进行迭代处 理。权　利　要　求　书 1/1 页 2 CN 115408132 A 2一种多云系统中 带有能耗约束 的计算卸载 方法 技术领域 [0001]本发明涉及云计算和无线网络领域， 特别涉及多云系统中的任务调度方法。 背景技术 [0002]随着硬件和软件方面的不断发展， 移动通信技术也日趋成熟， 人们开始希望在移 动终端上实现更多的功能和应用。 手机、 平板电脑等移动终端的功能从简单 的通讯设备逐 渐扩展成为集通讯、 多媒体、 游戏等功能于一身的计算工具。 如人脸识别、 虚拟现实等应用 技术不仅计算负载和数据量较大， 对于响应时间也有着较高的要求。 由于移动 终端在硬件 条件上的局限性， 在处理这种应用程序时往往延迟较大。 同时， 过长的任务执行时间也会消 耗移动终端较多的电量。 [0003]在上述的背景下， 移动云计算中的计算卸载技术被提出， 并成为了克服这些限制 的一种有 前途的方法， 其主要目标是降低应用完成时间， 节省移动终端电量。 使用单云节 点 的计算卸载方法没有办法满足不同用户对服务质量的不同需求， 不同云服务器根据处理 能 力的不同具有不同的收费标准。 因此本发明考虑在多云系统的服务场景， 从而满足不同的 服务质量需求。 发明内容 [0004]本发明的目的在于提供一种多云系统中带有能耗约束的计算卸载方法。 不同于现 有技术， 本发明考虑 任务在多云系统中的组合调度问题， 并在 满足移动终端能耗的同时， 以 降低完成时间作为优化目标。 本发明针对具有任务依赖关系的移动应用进行计算卸载。 [0005]基于上述发明的目的， 本发明提出的方法包括如下步骤： [0006]步骤S1、 任务 排序、 路径建立和路径优先级计算方法 [0007]步骤S2、 路径任务调度算法 [0008]步骤S3、 面向能耗约束的优化 算法 [0009]进一步地， 所述步骤S1具体为： [0010]对于任务依赖关系， 用pred(i)来表示任务 i的前驱任务 集合。 [0011]任务i在工作节点 k上的执行时间计算如下。 [0012] [0013]其中 表示对应的执行时间。 wli表示任务i的计算负载， spk表示工作节 点k的处理 速度。 [0014]以下是移动终端执 行能耗(即CPU处 理能耗)的计算方法。 [0015]当k＝0时， 表示任务在本地执 行(即移动终端执 行)， 执行能耗计算公式如下： [0016] [0017]当k≠0时， 即任务在某个云节点执 行， 终端执 行能耗计算公式如下： [0018] 说　明　书 1/6 页 3 CN 115408132 A 3