欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2023105656779
申请人: 重庆邮电大学空间通信研究院
专利类型:发明专利
专利状态:授权未缴费
专利领域: 计算;推算;计数
更新日期:2024-01-31
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于任务依赖关系的联合调度和卸载方法,其特征在于,所述方法包括:

根据设备在应用层面的子任务以及子任务依赖关系,建立多任务依赖关系边缘协作系统;

根据多任务依赖关系边缘协作系统,建立通信模型、时延计算模型和能耗计算模型;

基于通信模型、时延计算模型和能耗计算模型,通过最小化设备的实际最小完成时间构建出任务卸载模型;

根据多任务依赖关系边缘协作系统,建立基于子任务优先级顺序的任务调度模型;

按照任务调度模型对子任务进行优先级排序,并基于优先级顺序进行子任务调度;

获取设备在应用层面的子任务数量、子任务大小、子任务数据交换大小;

根据获取的子任务数量、子任务大小、子任务数据交换大小,计算出子任务平均数据交换时间、子任务平均执行时间和子任务卸载开销和本地能量消耗;

根据子任务平均数据交换时间、子任务平均执行时间和子任务卸载开销和本地能量消耗,计算出子任务优先级;所述子任务优先级的计算方式包括:其中,Priority(i,j')表示设备i的第j'个子任务的优先级,βi和εi分别是设备i的计算开销和能耗的权重系数,即βi+εi=1;order(i,j')表示设备i的第j'个子任务的排序结果;

表示设备i的第j'个子任务在本地执行能耗; 表示设备i的第j'个子任务在边缘服务器k执行能耗;next(j')是子任务j'的直接后续子任务集合; 是子任务j'与其后续任务j之间的平均数据交换时间; 是子任务j'的平均执行时间;

根据子任务优先级对子任务排序,确定出具有最高优先级的子任务;

计算出最高优先级的子任务在本地计算实际最早完成时间和子任务在边缘计算实际最早完成时间;

按照子任务调度顺序,通过求解任务卸载模型分别计算出子任务本地计算实际最早完成时间和任务边缘计算实际最早完成时间;

若子任务本地计算实际最早完成时间小于任务边缘计算实际最早完成时间,则执行子任务本地计算,否则执行子任务边缘计算。

2.根据权利要求1所述的一种基于任务依赖关系的联合调度和卸载方法,其特征在于,所述多任务依赖关系边缘协作系统包括每个用户都有一个应用层面的任务需要在边缘服务器的帮助下完成,将这些应用划分为一些相互依赖的子任务,子任务依赖关系用有向无环图表示为G=,其中,V表示子任务依赖节点集合也即子任务集合,E表示子任务之间依赖关系的有向边集,若子任务之间存在依赖关系,则子任务之间存在数据交换量,dataj'j≠0,dataj'j是第j'个子任务和第j个子任务之间的数据交换量;物联网设备i中的第j个子任务表示为Wi,j=(di,j,ci,j,ai,j),其中,di,j表示物联网设备i中第j个子任务传输的数据大小;ci,j表示完成物联网设备i的第j个子任务所需的总的CPU周期数大小,ai,j表示物联网设备i的第j个子任务的卸载决策,其中,ai,j=0表示物联网设备i在本地执行子任务,ai,j=k表示子任务被卸载到第k个边缘服务器上执行,设备i的子任务卸载决策表示为vi表示物联网设备i的子任务总数,若第k个边缘服务器不能处理被卸载的任务,将部分任务卸载到其他边缘服务器;i∈[1,2,...,N],N表示物联网设备数量,k∈[1,2,...,S],S表示边缘服务器数量,j,j',vi∈[1,2,...,V]。

3.根据权利要求1所述的一种基于任务依赖关系的联合调度和卸载方法,其特征在于,所述根据多任务依赖关系边缘协作系统,建立通信模型、时延计算模型和能耗计算模型包括根据多任务依赖关系边缘协作系统中的相互依赖的子任务之间传输的数据大小、完成设备的子任务所需的CPU周期数大小以及设备的子任务的卸载决策结合通信资源,分别构建出本地通信模型、边缘通信模型、本地时延计算模型、边缘时延计算模型、本地能耗计算模型和边缘能耗计算模型。

4.根据权利要求1所述的一种基于任务依赖关系的联合调度和卸载方法,其特征在于,所述基于通信模型、时延计算模型和能耗计算模型,通过最小化设备的实际最小完成时间构建出任务卸载模型表示为:其中,AEFT(Vi)表示设备i上所有子任务的实际最早完成时间;xj表示卸载决策; 表示子任务Wi,j在本地执行能耗;pi是设备i的传输功率;vi表示物联网设备i的子任务总数,Vi表示物联网设备i的子任务集合;di,j表示需要物联网设备i中第j个子任务传输的数据大小;

ri,k任务从设备i卸载到边缘服务器k的上行传输速率;Cj'j表示边缘服务器上前置子任务j'传输数据到子任务j所产生的通信成本;N表示物联网设备总数;Q表示通信成本;ai,1表示ai,j表示物联网设备i的第1个计算子任务的卸载决策, 表示ai,j表示物联网设备i的第vi个计算子任务的卸载决策;C1表示成本约束;C2和C3表示子任务调度策略和子任务放置策略;C4和C5表示第一个子任务和最后一个子任务必须在本地执行。

5.根据权利要求4所述的一种基于任务依赖关系的联合调度和卸载方法,其特征在于,所述设备i上所有子任务的实际最早完成时间包括:其中,AEST(exit)表示退出子任务的实际最早开始时间, 表示物联网设备i的最后一个子任务vi的执行时间。

6.根据权利要求5所述的一种基于任务依赖关系的联合调度和卸载方法,其特征在于,所述实际最早开始时间的计算公式包括:其中,AEST(i,j,k)是卸载到边缘服务器k时设备i上的子任务j的实际最早开始时间;

avail{i,j,k}表示子任务最早开始在边缘执行或者本地执行的情况;predj表示任务的直接前置子任务集;Cj'j表示边缘服务器上前置子任务j'传输数据到子任务j所产生的通信成本;AEFT(i,j')表示设备i上的子任务j'的实际最早完成时间;α∈{S∪{‑i}}表示子任务在本地计算或者在边缘服务器计算; 表示设备i上的子任务j'在本地计算时延或边缘计算时延。

7.根据权利要求1所述的一种基于任务依赖关系的联合调度和卸载方法,其特征在于,根据多任务依赖关系边缘协作系统,建立基于子任务优先级顺序的任务调度模型包括根据多任务依赖关系边缘协作系统中的子任务与其后续任务之间的平均数据交换时间,子任务的平均执行时间以及计算开销和本地能量消耗,构建出任务调度模型。

8.根据权利要求1‑7任一所述的一种基于任务依赖关系的联合调度和卸载方法,其特征在于,所述方法还包括分别计算出每个设备的子任务解;通过启发式算法从可选设备子任务集中选择出能够使得时延降低最大的一组子任务解;直至所有子任务卸载决策计算完成;若达到纳什均衡则更新调度结果。