(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210136561.9 (22)申请日 2022.02.15 (71)申请人 南京邮电大 学 地址 210003 江苏省南京市 鼓楼区新模范 马路66号 (72)发明人 鲁蔚锋　李学晴　徐佳　徐力杰　 蒋凌云　 (74)专利代理 机构 南京苏科专利代理有限责任 公司 32102 专利代理师 周湛湛 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/445(2018.01) G06F 9/50(2006.01) (54)发明名称 一种移动边缘计算中相关性任务的调度方 法 (57)摘要 本发明公开了一种在移动边缘计算中相关 性任务的调度方法和系统。 本发 明针对边缘节点 的处理速度不同和边缘节点之间的传输速率不 同， 形式化了调度相关性任务的方法。 本发明提 供了系统模型， 包括任务依赖模型、 网络模型和 通信模型， 将任务依 赖模型建模为DAG图； 考虑边 缘节点的异构性和任务的相关性， 设计系统目标 函数为最小化任务的完成时间； 本发 明对在边缘 节点的不同处理速度上提出了分组的概念， 用以 对边缘节点分组； 此外， 对在同一个组的边缘节 点， 采用最早时间优先调度算法。 使用本发明的 调度方法， 可 以缩小边缘节点空闲的时间， 从而 减少任务的完成时间。 权利要求书4页 说明书9页 附图3页 CN 114546615 A 2022.05.27 CN 114546615 A 1.一种移动边 缘计算中相关性任务的调度方法， 其特 征在于： 包括以下 具体步骤： 步骤1： 云端收集每个应用程序产生的任务信 息和边缘节点的信 息： 设用户终端设备集 合 将终端设备上的应用程序的任务化分为多个子任务， 各子任务之间存在依赖关系， 用有向无环图 来表示任务的依赖关系； 设任务集合 任务由二元 组表示(Bi， di)， E是边的集 合， 表示任务 i的依赖关系； 其中V是任务的数量， 用i， j表示任务， Bi表示任务i的计算负载量， di表示任务i的输入 数据量， 任务 i和任务j之间传输的数据量 为ui,j； 设边缘节点的集合 fk是边缘节点k的处理速度， 其中K是边缘节点的数 量， 用k， k'表示 边缘节点， 所述 边缘节点k， k'之间的传输 速率用 ξkk'表示； 步骤2： 确定任务卸载到不同边 缘节点上的传输时间： 首先令 其中Rh,k表示终端设备h将任务卸载到边缘节点k的传输速率， h是产生任务i的用户终 端设备， Wh,k是设备h到边缘节点k的链 路带宽， Ph是终端设备h的发射功率， lh,k是设备h和边 缘节点k之间的距离， β 是路径损失指数， σ 是信道噪声功 率。 则， 任务i卸载到边缘节 点k的传 输时间 可以表示 为： 步骤3： 给 出以下定义： (1)pred(i)： 任务 i的直接前驱的集 合， 任务i有多个直接前驱； (2)succ(i)： 任务 i的直接后继的集 合， 任务i有多个直接后继； (3)ETi,k： 是任务i在边缘节点k上的执行时间， 计算公式为： 其中， xi,k是二进制变量， 当xi,k＝1时表示任 务i是卸载到边缘节点k上执行的； Bi是任务 i的计算负载量， fk是边缘节点k的处理速度； (4)RTi,k:是任务i的准备完成时间， 它与两部分时间有关， 一是任务i上传到边缘节点k 的传输时间， 二是任务i的所有 前驱节点 都已经完成计算并将所需的数据传输至任务i所在 的边缘节点k上， 计算公式为： (5)STi,k： 是任务i在边缘节点k上的开始执 行时间； (6)ESTi,k： 是任务i在边缘节点k上的最早开始执行 时间， 它与两部分时间有关， 一是任 务i已经准备完成的时间， 二是边 缘节点k开始空闲的时间， 计算公式为： ESTi,k＝max{RTi,k,ATk}    (5) 其中， ATk是边缘节点k开始空闲的时间； (7)FTi,k： 是任务i在边缘节点k上的完成时间： 它是由开始时间和执行时间共同决定 的， 计算公式为：权　利　要　求　书 1/4 页 2 CN 114546615 A 2FTi,k＝STi,k+ETi,k    (6) (8)T:任务图的总的完成时间， 表示 为： 步骤4： 形式化相关性任务的调度问题： 系统中所有 的任务卸载且只能被卸载到一个边缘节点上执行， 并建立约束 以保证所有的任务只能被卸载到一个边 缘节点上； 系统中所有的边缘节点每次只 能执行一个任务， 如果有其它的任务， 需要等待前一个 任务完成之后才能执行， 并建立约束STi,k+ETi,k≤STj,k， 以保证边缘节点一次只能执行一个 任务且任务在执 行的过程中不会被中断执 行； 由于任务之间依赖性， 因此， 具有依赖关系的两个任务的执行受到约束， 建立约束 以保证具有依赖关系的两个任务i， j必须满足任 务j在开始执行之前， 它的前驱任务i已经计算完成并将数据传输至任务j所在的边缘节点 k'上； 优化目标是最小化任务 图(DAG)的完成时间， 构造得到统一的形式化相 关性任务的调 度问题： 步骤5： 设计边 缘节点的组分配规则， 得到任务与边 缘节点组的映射关系； 步骤6： 确定相关性任务在边缘节点上的调度 方案： 采用基于速度的最早优先调度算法 得到相关性任务在边 缘节点上的调度方案； 步骤7： 设备根据得到的调度方案， 将任务卸载到对应的边缘节点上， 通过边缘节点对 任务进行调度执 行。 2.根据权利要求1所述的移动边缘计算中相关性任务的调度方法， 其特征在于： 所述步 骤1中， 应用程序产生的任务信息包括任务的输入 数据量和计算负载量； 所述边缘节点的信 息包括边缘节点的处 理速度和边 缘节点之间的传输 速率。 3.根据权利要求1所述的移动边缘计算中相关性任务的调度方法， 其特征在于： 所述步 骤5中， 根据边缘节点的不同速度， 将边缘节点分成Q组， 其中 K是边缘节点的数 量， γ＝log  K/log log K， 不失一般性， 假设组 里的边缘节点的速度范围为 [γq‑1,γq)； 划分完组之后， 需要确定任务分配到哪个边缘节点组中， 组分配的设计是基于线性规权　利　要　求　书 2/4 页 3 CN 114546615 A 3