(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211229503.7 (22)申请日 2022.10.08 (71)申请人 杭州电子科技大 学 地址 310018 浙江省杭州市下沙高教园区2 号大街 (72)发明人 姚英彪　赵浩　冯维　李沛　 杨阿锋　徐欣　 (74)专利代理 机构 杭州君度专利代理事务所 (特殊普通 合伙) 33240 专利代理师 朱月芬 (51)Int.Cl. G06F 9/50(2006.01) (54)发明名称 一种面向雾计算的存在依赖关系的任务调 度方法 (57)摘要 本发明公开了一种面向雾计算的存在依赖 关系的任务调度方法。 本发明包括步骤： 1.任务 建模； 利用有向无环图来建模终端节 点用户任务 的子任务之间的依赖关系； 2.收集区域内网络的 公开信息； 3.任务执行时延建模； 4.任务传输时 延建模； 利用下述步骤建模第i个终端设备与第k 个边缘服务器匹配时的传输时延； 5.单 终端与单 边缘服务器匹配时的子任务调度,在本地和边缘 服务器之间调度终端节点的全部子任务的执行； 6.多终端与多 边缘服务器场景下的任务调度； 按 下面步骤进行多终端与多边缘服务器的终端设 备任务调度。 本发明探索考虑子任务间具有依赖 关系的任务卸载方案， 以追求时延的降低和边缘 服务器利用率的提升， 使 得边缘雾网络中的任务 卸载模型与实际应用更接 近。 权利要求书3页 说明书7页 附图1页 CN 115543621 A 2022.12.30 CN 115543621 A 1.一种面向雾计算的存在依赖关系的任务调度方法， 其特征在于该应用场景下的主要 设备包括终端设备、 边缘服务器和控制中心； 一个边缘服务器能够与多个终端设备匹配， 并 在不同时段为 终端设备提供服务； 每个终端设备只能与一个边缘服务器匹配， 若匹配成功， 终端设备的子任务就能够选择在本地执行或者卸载到匹配的边缘服务器上执行； 终端设备 与边缘服务器之间通过无线连接方式进行通信； 控制中心通过与终端设备和边缘服务器进 行有线或无线通信收集 终端和边缘设备各项工作指标， 包括CPU的工作频率、 设备所在的位 置信息、 发射功率、 噪声功率、 信道质量以及任务信息； 控制中心依据所收集到的这些数据 执行本发明所提出的基于贪心策略的任务卸载调度决策， 得到终端设备和边缘服务器之间 的匹配向量以及终端设备子任务的调度向量； 控制中心将匹配结果以及子任务调度向量广 播给终端用户和边缘服务器， 终端设备和边缘服务器依据调度结果进行任务的传输和执 行。 2.根据权利要求1所述的一种面向雾计算的存在依赖关系的任务调度方法， 其特征在 于该方法包括以下步骤： S1.任务建模； 利用有向无环图来建模终端节点用户任务的子任务之间的依赖关系； S2.收集区域内网络的公开信息； S3.任务执 行时延建模； S4.任务传输时延建模； 利用下述步骤建模第i个终端设备与第k个边缘服务器匹配时 的传输时延； S5.单终端与单边缘服务器匹配时的子任务调度,按下面步骤在本地和边缘服务器之 间调度终端节点的全部 子任务的执 行； S6.多终端与多边缘服务器场景下的任务调度； 按下面步骤进行多终端与多边缘服务 器的终端设备任务调度。 3.根据权利要求2所述的一种面向雾计算的存在依赖关系的任务调度方法， 其特征在 于步骤S1具体实现如下： 每个终端节点的用户任务用一个DAG来建模； DAG节点表示子任务， 边表示任务间的依 赖关系； 每个子任务都有唯一序号标识， 子任务按照序号以及依赖 关系有序执行； 对于每一 个子任务， 还假设该子任务输出给依赖它的下一个子任务的数据量和该子任务自身需要的 计算周期已知； 由于第一个任务开始执行时需要有数据量的输入， 因此任务建模时添加了序号为0的 节点， 该节点只有输出数据量但没有计算任务， 其后续依赖子任务在开始执行时需要接受 来自子任务0的数据， 子任务0默认在本地设备执行； 此外假设终端节点最后一个子任务输 出的结果数据量可忽略不计， 即最后一个子任务计算完成后， 就认为该终端节点的任务处 理完成。 4.根据权利要求2所述的一种面向雾计算的存在依赖关系的任务调度方法， 其特征在 于步骤S2区域内网络的公开信息包括： 边缘服务器的数量N和每个边缘服务器的计算能力 ffog； 终端设备的数量M和每个终端设备的计算能力flocal， 每个终端用户所分配的信道带宽 B； 终端设备以及边缘服务器所在位置坐标(x,y)， 噪声功率W； 终端与边缘服务器之间信息 传输的发射功率p。 5.根据权利要求2所述的一种面向雾计算的存在依赖关系的任务调度方法， 其特征在权　利　要　求　书 1/3 页 2 CN 115543621 A 2于步骤S3任务执 行时延建模， 具体实现如下： S3‑1.子任务j在本地计算的时延建模为： 表示第j个子任务在本地的计算时延， flocal表示终端设备的计算能力， Cj表示第j个 子任务所需的计算周期； S3‑2.子任务j在边 缘服务器计算的时延建模为： 表示第j个子任务在边 缘服务器上的计算时延， ffog表示边缘服务器的计算能力。 6.根据权利要求5所述的一种面向雾计算的存在依赖关系的任务调度方法， 其特征在 于步骤S4任务传输时延建模， 利用建模第i个终端设备与第k个边缘服务器匹配时的传输时 延， 具体实现如下： S4‑1.计算第i个终端设备与第k个边缘服务器匹配时的传输速率； 该传输速率采用香 农公式进行计算： 表示第i个终端设备到匹配服务器k的传输速 率， 其中B为信道带宽， p和 为第i个终 端设备与匹配服 务器k之间发射功率和信道增益， 分母W是噪声功率； 信道增益 的计算公式为： 其中， 表示第i个终端设备与 匹配服务器k之间的路径损 耗， 路径损 耗的计算公式 为： 其中dik是第i个终端 设备和匹配服务器k之间的欧氏距离， 可由这两个设备的位置坐标 计算得到； S4‑2.第i个终端设备与第k个边缘服务器匹配时， 终端设备的子任务j和其依赖的子任 务f之间的数据的传输时延建模为： 上式中， Df,j表示子任务f需要传输给子任务j的数据量， 表示边缘服务器与本地终端 之间的传输 速率。 7.根据权利要求5所述的一种面向雾计算的存在依赖关系的任务调度方法， 其特征在权　利　要　求　书 2/3 页 3 CN 115543621 A 3