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

摘要:

权利要求书:

1.在多接入边缘计算中卸载依赖任务的方法,其特征是,包括:S101:系统初始化,获取所有待执行任务的实时信息;所述所有待执行任务彼此之间存在依赖关系;

S102:根据所有待执行任务的实时信息、本地设备的计算能力、候选边缘服务器的计算能力和远程云服务器的计算能力,确定适应度函数;

S103:根据适应度函数的所有待执行任务允许的最晚完成时间和实际执行过程中的最晚完成时间,确定每个任务执行的优先级;

S104:生成各个任务的初始接入点和执行点;

S105:寻找帕累托最优解、局部最优解和全局最优解;

S106:基于帕累托最优解、局部最优解和全局最优解,优化每个任务的卸载过程;

S107:判断是否达到终止条件,当迭代次数达到给定的最大值,或者设定时间范围内最优解不发生变化,则迭代终止,输出最优解中各个任务的接入点和执行点;按照最优解中各个任务的接入点和执行点,完成本地设备的若干个相互依赖的待执行任务的卸载过程;否则,重复步骤S104~S107。

2.如权利要求1所述的在多接入边缘计算中卸载依赖任务的方法,其特征是,所述S101:系统初始化,获取所有待执行任务的实时信息;其中,系统初始化包括:本地设备、边缘服务器和远程服务器的资源限制;具体包括:本地设备一次只能运行一个任务;边缘服务器服务器具有多个处理器,一次能够运行多个任务;远程云服务器具有无限的计算能力,且能够服务用户所选的整个区域,所以任何任务都能够被卸载到远程云服务器执行,且远程云服务器能够同时执行无限多个任务。

3.如权利要求1所述的在多接入边缘计算中卸载依赖任务的方法,其特征是,所述S102:根据所有待执行任务的实时信息、本地设备的计算能力、候选边缘服务器的计算能力和远程云服务器的计算能力,确定适应度函数;具体包括:决策方式1:当本地资源充足时,任务在本地设备上执行;

决策方式2:当本地设备被占用时,且本地设备最近的边缘服务器可用时,将任务卸载到距离本地设备最近的边缘服务器上执行;

决策方式3:当本地设备被占用,且距离本地设备最近的边缘服务器也被占用时,距离本地设备最近的边缘服务器将任务卸载到另外一个边缘服务器上执行;

决策方式4:当本地设备和边缘服务器都不可用时,将任务卸载到远程服务器上执行;

结合四种决策方式,计算任务卸载的总完成时间和总执行成本;最小化任务卸载的总完成时间和总执行成本。

4.如权利要求1所述的在多接入边缘计算中卸载依赖任务的方法,其特征是,所述S103:根据适应度函数的所有待执行任务允许的最晚完成时间和实际执行过程中的最晚完成时间,确定每个任务执行的优先级;具体包括:计算每个任务允许的新的最晚完成时间;

根据每个任务允许的新的最晚完成时间,计算每个任务最晚执行时间;

按照最晚执行时间从小到大的顺序对任务进行排队,得到每个任务执行的优先级;

按照最晚执行时间从小到大的顺序,将任务放置到第一队列中;第二队列为备用队列,初始为空。

5.如权利要求1所述的在多接入边缘计算中卸载依赖任务的方法,其特征是,所述S104:生成各个任务的初始接入点和执行点;具体包括:比较第一队列和第二队列中开始任务的优先级,挑选优先级高的任务优先执行;判断任务j是否是用户k的第一个任务,若是,则任务j没有前序任务,任务j允许被直接执行;否则,判断任务j的前序任务是否完成,如果任务j的前序任务都已经完成,则执行任务j,否则,将任务j放置到第二队列中;

若任务j可执行,判断本地设备是否有正在执行的任务,由于本地设备一次只能执行一个任务,若本地设备上没有任务执行,则任务j在本地设备上执行,接入点和执行点都为本地设备;

若本地设备不可执行,则判断M(K)集合中是否有可执行的边缘服务器,若只有一个,则该边缘服务器即为任务j的接入点和执行点,若同时有多个可执行的边缘服务器,则在可选的边缘服务器中选择完成时间最早的边缘服务器作为任务j的接入点和执行点,并按决策方式2执行;

若本地设备和M(K)中都没有可执行的设备,用户k在M(K)中随机选择一个边缘服务器卸载任务,然后判断其他边缘服务器中是否有可执行的设备,如果只有一个可执行的设备,则该设备即为任务j的执行点,如果同时有多个边缘服务器可执行,则计算各个边缘服务器的完成时间,选择完成时间最早的边缘服务器作为执行点,按决策方式3执行;否则,由该接入边缘服务器作为中继,根据决策方式4将任务上传至远程服务器执行;

当第一队列和第二队列都为空时,所有应用执行完成,即一个粒子初始化结束,记录目标函数T1和T2的值。

6.如权利要求1所述的在多接入边缘计算中卸载依赖任务的方法,其特征是,所述S105:寻找帕累托最优解、局部最优解和全局最优解;其中,寻找局部最优解,具体包括:用户对任务卸载的总完成时间T1和执行成本T2的喜好程度由用户任务的完成时间约束和对成本的承受能力来决定;

对于一个时间紧急度高于设定阈值的任务来说,用户通过牺牲一部分的执行成本T2以换取更早的完成时间T1;

因此,根据实际场景中的情况为目标函数T1和目标函数T2设计权重系数,得到:T=η1T1+η2T2    (26)其中η1+η2=1;η1和η2属于[0,1],表示任务在决策时的完成时间和执行成本的加权系t

数;根据(26)得到唯一的PBi。

7.如权利要求1所述的在多接入边缘计算中卸载依赖任务的方法,其特征是,所述S105:寻找帕累托最优解、局部最优解和全局最优解;其中,寻找全局最优解,具体包括:t t

选取全局最优粒子GBj;使用网格法从档案集中的选取GBj;具体步骤如下:S1051:计算档案集中的密度信息;

t t t t

S10511:计算第t次迭代时目标空间的边界(minT1,maxT1)和(minT2,maxT2);

S10512:根据以下式子计算网格的模:其中M*M是要划分的网格数;

S10513:档案集中粒子j所在的网格编号可由以下式子得出:j j

其中,Int(·)是求整函数;T1和T2分别为粒子j在目标函数1和目标函数2的值;

t

S1052:为粒子选取全局最优粒子GBj ;为了有效的保证IMOPSOQ算法的收敛性能和帕累托解集的多样性,对于档案集中的粒子,其密度值越低,选择的概率就越大,反之,则越小;

以粒子j为例;

t

S10521:计算Archive集中优于粒子j的子集Arj;

t t

S10522:找出Arj集中密度最小的粒子集合Gj;

t t t

S10523:若集合Gj中只有一个粒子即为全局最优粒子GBj,反之则按PBi选取方法选出t

全局最优粒子GBj;

或者,

所述S106:基于帕累托最优解、局部最优解和全局最优解,优化每个任务的卸载过程;

具体包括:

t t

根据粒子j、个体最优粒子PBj 和全局最优粒子GBj 更新粒子j;为防止算法陷入局部最优,设计一个转移概率对粒子的更新过程进行了优化;转移概率如下:其中,Proj、 分别表示粒子维持自己先前的执行方式、向自身历史最佳执行方式逼近和向群体最佳执行方式逼近的概率;适应度值T1和T2的值越好,该任务向该解转移的概率越大,反之越小;

更新Archive集:进化得到新一代的粒子后,将新一代粒子中的帕累托解放到Archive集中;具体的,若Archive集为空,将新一代粒子中的帕累托解直接放到Archive集中;若Archive集不为空,将新一代中优于或者独立于Archive集中的粒子放到Archive集中;当Archive集的粒子数超过规定大小时,对于粒子数超过1的网格GR,按(30)计算需删除的粒子数DQ;

在按(26)计算各个网格中粒子的适应度值,将其降序排序后,删除后DQ个粒子;

其中|Art+1|表示第t代时Archive集中的粒子数; 是Archive集中允许的最大粒子数;Grid[GR]示网格GR中包含的粒子数。

8.在多接入边缘计算中卸载依赖任务的系统,其特征是,包括:初始化模块,其被配置为:系统初始化,获取所有待执行任务的实时信息;所述所有待执行任务彼此之间存在依赖关系;

适应度函数确定模块,其被配置为:根据所有待执行任务的实时信息、本地设备的计算能力、候选边缘服务器的计算能力和远程云服务器的计算能力,确定适应度函数;

任务优先级确定模块,其被配置为:根据适应度函数的所有待执行任务允许的最晚完成时间和实际执行过程中的最晚完成时间,确定每个任务执行的优先级;

任务接入点和执行点生成模块,其被配置为:生成各个任务的初始接入点和执行点;

最优解计算模块,其被配置为:寻找帕累托最优解、局部最优解和全局最优解;

优化模块,其被配置为:基于帕累托最优解、局部最优解和全局最优解,优化每个任务的卸载过程;

判断模块,其被配置为:判断是否达到终止条件,当迭代次数达到给定的最大值,或者设定时间范围内最优解不发生变化,则迭代终止,输出最优解中各个任务的接入点和执行点;按照最优解中各个任务的接入点和执行点,完成本地设备的若干个相互依赖的待执行任务的卸载过程,否则,返回任务接入点和执行点生成模块。

9.一种电子设备,其特征是,包括:一个或多个处理器、一个或多个存储器、以及一个或多个计算机程序;其中,处理器与存储器连接,上述一个或多个计算机程序被存储在存储器中,当电子设备运行时,该处理器执行该存储器存储的一个或多个计算机程序,以使电子设备执行上述权利要求1‑7任一项所述的方法。

10.一种计算机可读存储介质,其特征是,用于存储计算机指令,所述计算机指令被处理器执行时,完成上述权利要求1‑7任一项所述的方法。