欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2020111418558
申请人: 华侨大学
专利类型:发明专利
专利状态:已下证
专利领域: 电通信技术
更新日期:2024-01-05
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于计算图的边缘计算任务调度方法,其特征在于,包括以下步骤:步骤1,构建工业云边缘系统构架;所述工业云边缘系统构架包括:边缘计算任务管理器和边缘服务器;其中,在云端布置所述边缘计算任务管理器;在总监控区域内存在q个基站,在每个基站中布置一台所述边缘服务器,因此,共布置q台边缘服务器,分别为:边缘服务器BF1,边缘服务器BF2,...,边缘服务器BFq;每台所述边缘服务器的监控区域即为对应的所述基站的覆盖范围;

步骤2,对于任意的每台边缘服务器BFi,i=1,2,...,q,配置对应的任务调度器TDi,任务调度器TDi每隔周期T,汇总边缘服务器BFi待处理的边缘计算任务,并进行批量处理,具体方法为:

步骤2.1,边缘服务器BFi建立并实时更新本地存储的数据集合表EDSi=(DSi1,DSi2,...,DSip);

其中,p代表边缘服务器BFi监控区域当前包含的智能终端的总数量,并且,随着监控的不断进行,当边缘服务器BFi监控到其监控区域加入新的智能终端时,则更新数据集合表EDSi,将新加入的智能终端的数据集合DS加入到数据集合表EDSi;

其中:DSi1,DSi2,...,DSip分别代表边缘服务器BFi包含的第1个智能终端Ii1的数据集合,第2个智能终端Ii2的数据集合,...,第p个智能终端Iip的数据集合;

对于边缘服务器BFi包含的任意的第j个智能终端Iij,其数据集合DSij描述方式为:{Key(BFi,IDij):{Lj=Lt1,Lt2,...,Ltx}},即:采用键值对的方式存储数据,其中,IDij代表边缘服务器BFi的监控区域包含的第j个智能终端Iij的智能终端ID;Lj=Lt1,Lt2,...,Ltx代表从监控开始后,第j个智能终端Iij采集到的工业现场数据序列,即:Lt1代表监控开始后,采集到的第1个工业现场数据,Lt2代表监控开始后,采集到的第2个工业现场数据,依此类推,Ltx代表监控开始后,采集到的第x个工业现场数据,并且,随着监控不断进行,第j个智能终端Iij采集到的最新的工业现场数据不断存入该数据集合DSij,实现对数据集合DSij的实时更新;

步骤2.2,任务调度器TDi汇总边缘服务器BFi上当前已部署的边缘计算任务,假设共有n个已部署的边缘计算任务,从而形成任务集合F=[F1,F2,...,Fn];其中,F1代表第1个边缘计算任务,F2代表第2个边缘计算任务,依此类推,Fn代表第n个边缘计算任务;

对于任意的边缘计算任务Fk,其中,k=1,2,...,n,具有以下属性:任务ID、输入数据集合描述DSk、输出数据集合描述DRk、计算代码包Uk以及任务固有运行时间tk;

步骤2.3,任务调度器TDi对各个边缘计算任务之间的数据传递关系进行关联分析,形成表征边缘计算任务级联依赖关系的计算图;其中,所述计算图包括两类节点:一类节点为边缘计算任务节点,另一类节点为数据集合节点;

假设计算图共有m层,则最底层,即第m层的各个节点均为数据集合节点,并且,该数据集合节点均为智能终端采集到的工业现场数据序列形成的数据集合,或为智能终端采集到的工业现场数据序列形成的数据集合的子集合;

计算图的第m‑1层节点包括至少一个边缘计算任务节点,其对应的边缘计算任务表示为Fm‑1,边缘计算任务Fm‑1与第m层的至少一个数据集合节点采用向上箭头连接,代表第m层的对应数据集合节点所对应的数据集合输入到边缘计算任务Fm‑1,边缘计算任务Fm‑1对输入的数据集合进行计算处理后,得到输出数据集合DRm‑1,将输出数据集合DRm‑1作为数据集合节点,并表示在第m‑2层的某个节点,再采用向上箭头,使边缘计算任务Fm‑1连接到其输出的输出数据集合DRm‑1;

边缘计算任务Fm‑1输出的输出数据集合DRm‑1,可作为另一个边缘计算任务的输入数据集合或输入数据集合的子集,由此采用自下向上方向,实现各个边缘计算任务之间的数据传递关系;

步骤2.4,任务调度器TDi每隔周期T,汇总边缘服务器BFi待处理的边缘计算任务,假设当前计算周期,共汇总到y个待处理的边缘计算任务,形成待处理任务集合f=[f1,f2,...,fy];其中,f1代表第1个待处理的边缘计算任务,f2代表第2个待处理的边缘计算任务,依此类推,fy代表待处理的第y个边缘计算任务;

步骤2.5,任务调度器TDi根据待处理的边缘计算任务的类型,启动对应的第一种任务实时调度模式或第二种任务自适应调度模式;其中,第一种任务实时调度模式采用步骤2.6执行;第二种任务自适应调度模式采用步骤2.7执行;

步骤2.6,第一种实时任务调度模式:第一种任务实时调度模式是指各个待处理的边缘计算任务具有用户设定的允许的最长等待约束时间,具体实现步骤为:步骤2.6.1,对于任意的待处理的边缘计算任务fa,其中,a=1,2,...,y,具有以下属性:任务ID以及用户设定的允许的最长等待约束时间Exta;

步骤2.6.2,任务调度器TDi采用以下方式,对待处理的y个边缘计算任务进行排序,具体排序方法为:

步骤2.6.2.1,对于待处理任务f1,f2,...,fy,以最长等待约束时间从小到大的顺序,对各个待处理任务f1,f2,...,fy进行排序,从而得到待处理任务序列:f[1],f[2],...,f[y],其最长等待约束时间对应为:Ext[1],Ext[2],...,Ext[y];

步骤2.6.2.2,令h=1;

步骤2.6.2.3,预建立任务调度表;初始时,任务调度表为空;

步骤2.6.2.4,查找步骤2.3得到的计算图,以任务f[h]为起点,按从上向下方向,查找到所有与任务f[h]具有从属关系的任务节点,假设共有c个,并对c个任务节点按以下规则排序:规则1,c个子任务节点中,优先将下层子任务节点排在上层子任务节点的前面;规则2,对于属于同一层的子任务节点,进行随机排序,从而得到任务f[h]的子任务序列为:f[h1],f[h2],...,f[hc];

步骤2.6.2.5,查找任务调度表,判断子任务序列f[h1],f[h2],...,f[hc]中是否存在已存入到任务调度表中的任务,如果没有,则采用公式一计算时间t[h];如果有,则在子任务序列f[h1],f[h2],...,f[hc]中删除掉已存入到任务调度表中的任务,得到新的子任务序列,表示为:f'[h1],f'[h2],...,f'[hd];其中,d为新的子任务序列中的任务数量,再采用公式二计算时间t[h]:

公式一:t[h]=任务调度表中已存入的各个任务的任务固有运行时间之和+c个子任务f[h1],f[h2],...,f[hc]的任务固有运行时间之和+任务f[h]的任务固有运行时间之和;

公式二:t[h]=任务调度表中已存入的各个任务的任务固有运行时间之和+新的子任务序列f'[h1],f'[h2],...,f'[hd]中各个子任务的任务固有运行时间之和+任务f[h]的任务固有运行时间之和;

步骤2.6.2.6,如果时间t[h]大于任务f[h]的最长等待约束时间Ext[h],则向请求任务f[h]的客户端返回无法满足本次服务的通知消息;如果时间t[h]小于等于任务f[h]的最长等待约束时间Ext[h],则执行步骤2.6.2.7;

步骤2.6.2.7,如果子任务序列f[h1],f[h2],...,f[hc]中不存在已存入到任务调度表中的任务,则将任务序列f[h1],f[h2],...,f[hc],f[h]存入任务调度表中,并置于任务调度表中已存在的任务序列的后面;

如果子任务序列f[h1],f[h2],...,f[hc]中存在已存入到任务调度表中的任务,则将新的任务序列f'[h1],f'[h2],...,f'[hd],f[h]存入任务调度表中,并置于任务调度表中已存在的任务序列的后面;

步骤2.6.2.8,判断h是否等于y,如果等于,则执行步骤2.6.2.9;如果不等于,令h=h+

1,返回步骤2.6.2.4;

步骤2.6.2.9,将任务调度表中的最后的任务序列作为最终的调度任务序列,按最终的调度任务序列的任务顺序,依次执行各个任务,在各个任务执行过程中,一旦得到与某个客户端请求对应的结果,立即返回给对应的客户端;

步骤2.7,第二种任务自适应调度模式:第二种任务自适应调度模式是指各个待处理的边缘计算任务不具有用户设定的允许的最长等待约束时间,此时,以所有任务请求的客户端总等待时间最短为目标,对各个待处理的边缘计算任务进行排序;再根据排序结果进行任务调度。

2.根据权利要求1所述的基于计算图的边缘计算任务调度方法,其特征在于,步骤2.7具体实现步骤为:

步骤2.7.1,对于任意的待处理的边缘计算任务fa,其中,a=1,2,...,y,具有以下属性:任务ID;

步骤2.7.2,对于待处理任务f1,f2,...,fy,根据步骤2.3得到的计算图,分析各个任务之间的从属关系,将具有从属关系的任务归到一个从属关系组,并且,属于同一个从属关系组中的各个任务保持与计算图中对应任务相同的级联关系,从而将y个待处理任务f1,f2,...,fy划分为w个从属关系组,分别为:Z1,Z2,...,Zw;其中,具有从属关系的任务是指:父节点A与其子节点A1、子节点A1与其下一级子节点A2,依此类推,形成的具有从属关系的任务;

步骤2.7.3,预建立任务调度表;初始时,任务调度表为空;

步骤2.7.4,对于w个从属关系组Z1,Z2,...,Zw,从每个从属关系组中选择出组内最底层的任务,如果某个从属关系组为空,则不再进行选择,假设本次共选择出w0个任务,根据计算图,分别计算w0个任务中各个任务的总执行时间,选择w0个任务中总执行时间最小的任务,表示为任务f1";

查找步骤2.3得到的计算图,以任务f1"为起点,按从上向下方向,查找到所有与任务f1"具有从属关系的子任务节点,假设共有c1个,并对c1个子任务节点按以下规则排序:规则1,c1个子任务节点中,优先将下层子任务节点排在上层子任务节点的前面;规则2,对于属于同一层的子任务节点,进行随机排序;从而得到任务f1"的子任务序列为:f"[11],f"[12],...,f"[1c1];

查找步骤2.7.3预建立的任务调度表,判断子任务序列f"[11],f"[12],...,f"[1c1]中是否存在已存入到任务调度表中的任务,如果没有,则直接将任务序列f"[11],f"[12],...,f"[1c1],f1"存入到任务调度表中,并置于任务调度表中已存在的任务序列的后面;如果有,则在子任务序列f"[11],f"[12],...,f"[1c1]中删除掉已存入到任务调度表中的任务,得到新的子任务序列,表示为f'[11],f'[12],...,f'[1c2]:其中,c2为新的子任务序列中的任务数量,然后将任务序列f'[11],f'[12],...,f'[1c2],f1"存入到任务调度表中,并置于任务调度表中已存在的任务序列的后面;

步骤2.7.5,将本次处理的任务f1"从对应的从属关系组中删除,从而对w个从属关系组Z1,Z2,...,Zw进行更新,得到更新后的w个从属关系组Z1,Z2,...,Zw,然后返回步骤2.7.4;

如此不断循环,直到完成对y个处理任务f1,f2,...,fy的排序判断,任务调度表中最后形成的任务序列即为最终的调度任务序列,按最终的调度任务序列的任务顺序,依次执行各个任务,在各个任务执行过程中,一旦得到与某个客户端请求对应的结果,立即返回给对应的客户端。

3.根据权利要求2所述的基于计算图的边缘计算任务调度方法,其特征在于,步骤

2.7.4中,根据计算图,分别计算w0个任务中各个任务的总执行时间,具体方法为:对于w0个任务中的任意任务F0,查找步骤2.3得到的计算图,以任务F0为起点,按从上向下方向,查找到所有与任务F0具有从属关系的子任务节点,假设共有c2个,从而得到任务F0的子任务序列为:F[1],F[2],...,F[c2];

查找任务调度表,判断子任务序列F[1],F[2],...,F[c2]中是否存在已存入到任务调度表中的任务,如果没有,则采用公式三计算总执行时间t[F];如果有,则在子任务序列F[1],F[2],...,F[c2]中删除掉已存入到任务调度表中的任务,得到新的子任务序列,表示为:F'[1],F'[2],...,F'[c3];其中,c3为新的子任务序列中的子任务数量,再采用公式四计算总执行时间t[F]:

公式三:t[F]=c2个子任务F[1],F[2],...,F[c2]的任务固有运行时间之和+任务F0的任务固有运行时间之和;

公式四:t[F]=c3个子任务F'[1],F'[2],...,F'[c3]的任务固有运行时间之和+任务F0的任务固有运行时间之和。