(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210366936.0 (22)申请日 2022.04.08 (71)申请人 湖南工学院 地址 421002 湖南省衡阳市珠晖区衡花路 18号 (72)发明人 柳佳刚　潘智斌　曹水莲　王鹏　 (74)专利代理 机构 衡阳雁城专利代理事务所 (普通合伙) 43231 专利代理师 龙腾 (51)Int.Cl. G06F 9/50(2006.01) G06F 9/445(2018.01) G06F 9/48(2006.01) (54)发明名称 边缘计算中基于任务图整体资源需求的多 应用在线计算卸载资源调度方法和系统 (57)摘要 边缘计算中基于任务图整体资源需求的多 应用在线计算卸载资源调度方法和系统， 具体而 言， 是由需要为应用进行计算卸载的用户设备先 根据当前移动边缘计算中边缘计算设备的负载 状态和要卸载执行的应用的任务图结构生成一 个离线的任务分配映射表， 系统再从用户的角 度， 将满足每个用户的离线任务 分配方案作为对 计算资源的总需求， 从最大化用户应用的总体价 值角度， 于当前收到的卸载请求集合中选择一个 用户请求， 并基于该用户的离线分配映射， 将应 用的任务全部分配到边缘计算网络的对应计算 设备上。 本发 明中所采用的计算 资源分配方法在 应用的总价值、 平均执行跨度和平均成功率方面 均表现出较佳的效果， 综合来看， 其总体测试结 果要明显优于现有的其它方法。 权利要求书6页 说明书14页 附图3页 CN 114610503 A 2022.06.10 CN 114610503 A 1.边缘计算中基于任务图整体资源需求的多应用在线计算卸载资源调度方法， 其特征 在于， 包括以下步骤： S1.用 表示要执行计算卸载的应用n对应的DAG模型， 其中, 和 εn分别为应用 n的任务集合和有向边集合， 中任务的总数 应用n中的一个任务为 其中i表示 集合 中的第i个任务， 任务tni的计算负载量表示成δni； S2.给应用n分别增加两个计算负载量为0的伪节点作为入口和出口， 即 和 在集合 中的编号分别用0和In+1表示， 且从 发出的有向边和进入 的有向边 都分别赋予一个数据传输量， 其中， 出边的传输量表示要从用户设备上卸载的应用数据 量， 其数值大小表示为 表示 的后继； 入边的数据传输 量表示要传回用户设备的结果数据量， 其数值大小表示为 代表 的前驱； S3.根据应用n的DAG结构计算每 个任务的优先级； S4.构建一个用于记录算出的部分关键路径——PCP的空集 根据计算出的任务优先 级为应用n的DAG结构计 算PCP路径， 将获得的PCP路径存放在集合 中， 并用 表示集合 包 含的PCP路径的数目； S5.根据所有边缘计算设备的处理能力和单位时间执行开销， 将集合 中的每条PCP路 径 分 配 到 为 应 用卸载 生 成 的 离 线 分 配映 射 表 中 ； 所 述 离 线 分 配映 射 表 其数据结构为链表 每一条链表 都与一个边缘计算设备m 相对应将应用n的每条PCP路径都映射到各个链表 中， 由所有链表 构成离线分配 映射表 S6.用 表示执行计算卸载的应用向某一边缘计算设备mn发送的 计算卸载请求， 其中rn为应用的卸载请求释放时间， ln为截止期限， bn为应用在边缘计算网 络上成功处理完成的期望开销， 是应用的DAG结构， σn是应用在申请的计算资源上能成功 执行完的预计处 理时间； S7.计算各计算卸载请求的期望开销权值 μn＝bn/σn， 并把各计算卸载请求按照 μn值升序 排列一个队列 中； S8.从 中找出 μn值最大的请求 并读取出其对应 应用n的离线分配映射表 S9.遍历离线分配映射表 中与每个 边缘计算设备m相对应的链表 并把链表上元 素 对应的任务分配到边 缘计算设备m的计算队列上。 2.如权利要求1所述多应用在线计算卸载资源调度 方法， 其特征在于， 步骤S3 中按下式 计算应用n中的任务 的优先级:权　利　要　求　书 1/6 页 2 CN 114610503 A 2其中， 表示边缘计算网络中所有计算设备的平均数据传输率； 是边缘计算网络中所 有计算单 元的平均处 理能力。 3.如权利要求2所述多应用在线计算卸载资源调度方法， 其特征在于： 步骤S4中， 使用 SearchPCP算法递归地计算PCP路径。 4.如权利要求3所述多应用在线计算卸载资源调度方法， 其特征在于： 计算PCP路径过 程中， 使用已标记任务来辅助标定任务， 所述已标记任务是在计算P CP的过程中已经被标记 过的任务， 对于给定的应用n， 初始时伪节点 和 始终当作已标记任务， 其它任务都当作 未标记的任务； 并用H(tni)表示任务tni的一个特定子集， 在该特定子集中， 每一个任务都不 是已标记 任务， 但每个任务的父任务都是已标记 任务； 对于一个已标记 任务tni， 如果其子任 务tnj在集合H(tni)中有最高的优先级， 那么将该子任务tnj作为关键子任务， 并将已标记任 务tni的关键子任务表示 为Hcri(tni)； 之后再从入口节点 开始使用SearchPCP算法递归地计算PCP， 并把为应用n计算出的 PCP存入集合 节点 和 不在集合 中。 5.如权利要求1所述多应用在线计算卸载资源调度方法， 其特征在于： 步骤S5中， 链表 有p个元素， 初始时， 为带头结点 的空链表并且边缘计算设备m的可用时间Rm 记录在 中； 其中， Q(m)表示边缘计算设备m的计算队列， tn′,i′为在Q(m)中的一个等待任务， 表示任务tn′i′的完成时间， 其 一般化形式为 即 为任务tni的完成时间； 若任务tni为作为入口或出口 的伪任务， 则其按下式计算： 在式(3)中， 第一个条件下， rn是应用n的卸载请求的释放时间， 故其直接就是伪任务 的完成时间； 第二个条件表示伪任务 需要收到发送回应用n的结果数据； 若任务tni不是伪任务， 则 由下式计算： 其中， R(ani)表示要执行任务tni的边缘设备m在分配规划ani下准备执行tni的时间，权　利　要　求　书 2/6 页 3 CN 114610503 A 3