版权说明 操作指南
首页 > 成果 > 成果详情

联合能量和延迟优化的移动边缘计算任务调度方法

认领
导出
反馈
分享
QQ微信 微博
成果类型:
专利
发明/设计人:
邝祝芳;李林峰;汪茄琪
申请/专利权人:
中南林业科技大学
专利类型:
发明专利
语种:
中文
申请时间:
2019-01-11
申请/专利号:
CN201910026321.1
公开时间:
2019-05-03
公开号:
CN109710336A
主申请人地址:
410004 湖南省长沙市天心区韶山南路498号
申请地区:
湖南
机构署名:
本校为第一完成单位
主权项:
1.联合能量和延迟优化的移动边缘计算任务调度方法,其特征在于,包括以下步骤: 步骤1:计算每个任务在的本地执行时间,在边缘服务器的执行时间,任务卸载传输时间,边缘服务器执行耗能,本地执行耗能, 步骤2:基于CPU处理任务所需周期数的卸载调度方法求卸载决策向量, 步骤3:求解卸载任务集合S中所有任务的卸载传输功率, 步骤4:比较Val_old和Val_new,如果新算出的目标函数值与上一次循环的目标值的差值大于门限值ε,即Val_new-Val_old>ε,则退出,否则重复步骤1-步骤3。 2.根据权利要求1所述的联合能量和延迟优化的移动边缘计算任务调度方法,其特征在于,步骤1中的计算每个任务Ti在的本地执行时间在边缘服务器的执行时间任务卸载传输时间边缘服务器执行耗能本地执行耗能的步骤为: 任务Ti在边缘服务器的执行时间表示为: 任务Ti的本地执行时间表示为: 任务Ti的卸载传输速度为: 其中,w为传输带宽,g0为路径损耗常数,L0为相对距离,L为实际距离,θ为路径损耗指数,N0为噪声功率谱密度,pi表示边缘设备卸载任务Ti到边缘服务器的传输功率。 任务Ti的卸载传输时间为: 任务Ti的卸载执行耗能为: 其中,δS为边缘服务器每CPU周期的耗能,单位为焦耳/周期,η1为任务执行能量权重。 任务Ti的本地执行耗能为: 其中,δL为边缘设备每CPU周期耗能,单位为焦耳/周期。 3.根据权利要求1所述的联合能量和延迟优化的移动边缘计算任务调度方法,其特征在于,步骤2中的基于CPU处理任务所需周期数的卸载调度方法求卸载决策向量,输入为所有任务集合G,边缘设备CPU频率fuser,边缘服务器CPU频率fser。输出为卸载任务集合S={S1,S2,...,SNs},本地任务集合L={L1,L2,...,LNl},所有任务集合σ,卸载决策向量x。基于CPU处理任务所需周期数的卸载调度方法步骤如下: 1)求各个任务对应的CPU处理所需周期数K={Ki|Ki=dici,Ti∈G}。根据Ki的大小对所有任务降序排列,得到新的任务顺序Kopt。 2)设数组Kopt初始下标值为h=1,根据公式(7)(8)分别计算若放入本地集合L、卸载集合S后的完成时间 3)若则放入本地集合L,任务的卸载决策变量反复执行步骤i)直至退出该步进入步骤4)。反之,任务放入卸载集合S,任务的卸载决策变量反复执行步骤ii)直至退出该步进入步骤4)。 ⅰ)反复执行该步直至退出该步进入步骤4),比较若放入本地集合L和卸载集合S的完成时间的大小,根据式(9)计算任务Lk0完成时间,根据式(10)计算任务Sk1完成时间。若任务的卸载决策变量任务放入本地集合L,h=h+1;反之,任务放入卸载集合S,h=h+1,并执行4)。 ⅱ)反复执行该步直至退出该步进入步骤4),比较若放入本地集合L和卸载集合S的完成时间的大小,根据式(9)计算任务Lk0完成时间,根据式(10)计算任务Sk1完成时间。若任务的卸载决策变量任务放入卸载集合S,h=h+1;反之,任务放入卸载集合S,h=h+1,并执行4)。 其中 4)若任务的卸载决策变量任务放入本地集合L,否则任务的卸载决策变量任务放入卸载集合S。h=h+1,反复执行该步直至h=N。 5)对卸载集合S中所有任务进行分类,通过比较卸载传输时间和边缘服务器执行时间将卸载传输时间小于边缘服务器执行时间的任务加入数组P,将P中所有任务根据卸载传输时间升序排列。将卸载传输时间大于或等于边缘服务器执行时间的任务加入数组Q,将Q中所有任务根据边缘服务器执行时间降序排列。将数组Q加到数组P后面得到新的任务顺序S=[PQ]。 4.根据权利要求1所述的联合能量和延迟优化的移动边缘计算任务调度方法,其特征在于,步骤3中求解卸载任务集合S中所有任务的卸载传输功率,输入为所有卸载任务集合S={S1,S2,...,SNs},本地任务集合L={L1,L2,...,LNl},边缘设备CPU频率fuser,边缘服务器CPU频率fser,最大传输功率pmax。输出为卸载任务集合S,卸载任务Si传输功率采用凸优化的方法进行求解,基于凸优化的卸载任务传输功率的求解步骤如下: 1)联合任务调度和功率分配问题的目标是最小化能量消耗和所有任务的完成时间,优化问题的数学模型如(12)至(15)所示,记为原问题P1。其中式(12)为目标函数,式(13)至(15)为约束。 其中表示排序后所有卸载任务的完成时间,Ns表示所有卸载执行任务数,Nl表示本地执行任务数,为传输能耗,C=ηN0w/[g0(L0/L)θ],η为任务传输能量权重参数,为排序后第Si个卸载任务的传输速率的倒数。表示边缘服务器执行所有卸载任务的总能耗,表示边缘设备执行所有本地任务的总能耗。为排序后第Si个卸载任务的完成时间,为集合S中第Si个卸载任务的服务器处理时间。表示第Si个卸载任务分配最大传输功率pmax时的最大传输速率。为集合S中第S1至第Si个卸载任务的传输时间,计算公式如式(11)所示。 2)对步骤1)的联合优化问题P1进行问题转换,具体步骤包括: ⅰ)引入拉格朗日乘子和构造的拉格朗日函数如式(16)所示。 ii)根据步骤3求得卸载决策向量之后,可以确定卸载任务集合S,所有卸载任务Si的完成时间边缘服务器执行时间卸载任务执行能耗以及本地任务执行能耗故问题P1的最优解可通过求问题P2获得,如式(17)所示。 其中,为P2的目标式,且为凸函数,又目标式为凸函数之和,故目标式也为凸函数。为P2的约束条件。 3)根据式(12)计算当前给定卸载顺序和卸载任务最大传输功率时的Valnew_S值。 4)采用KKT条件求解转换的问题P2,求解步骤包括: ⅰ)对目标式求最小值,由于目标式为凸函数,故可采用牛顿法对其进行求解。将求得的解代入约束条件(15),若求得的解中每一个值都满足约束条件(15),则就是目标函数的最优解,否则进入步骤ⅱ)。 ⅱ)目标式对求偏导,可求得拉格朗日乘子的负数,如式(18)所示。 ⅲ)判断求得的解是否满足约束条件(15),并对其进行分类,把满足式(15)的解记为把不满足式(15)的解记为集合中元素的个数记为Ndopt,集合中元素的个数记为Nnopt。将集合中的代入式(18)求得对应的拉格朗日乘子再将满足约束(15)的最优值代入(17),对应的拉格朗日乘子此时(17)变为以为变量的优化问题,如式(19)所示。 ⅳ)再次采用牛顿法对式(19)进行求解,求得的最优解,将和代入式(20),求得传输功率。 5)对所有卸载任务Si进行分类,通过比较卸载传输时间和边缘服务器执行时间将卸载传输时间小于边缘服务器执行时间的任务加入数组P,将P中所有任务根据卸载传输时间升序排列。将卸载传输时间大于或等于边缘服务器执行时间的任务加入数组Q,将Q中所有任务根据边缘服务器执行时间降序排列。将数组Q加到数组P后面得到新的任务顺序S=[P Q]。 6)上一轮的目标值Valnew_S保存至Valold_S,用于比较两轮目标值,即Valold_S=Valnew_S,根据式(12)计算新的目标值Valnew_S。 7)重复步骤步骤3)至步骤5),直至不满足条件Valnew_S-Valold_S≤σ为止,此时将Val_new的值存入Val_old,目标值Valnew_S存入Val_new。 5.根据权利要求1所述的联合能量和延迟优化的移动边缘计算任务调度方法,其特征在于,步骤4中比较Val_old和Val_new,如果新算出的目标函数值与上一次循环的目标值的差值大于门限值ε,即Val_new-Val_old>ε,则退出,否则重复步骤1-步骤3。
摘要:
本发明公开一种联合能量和延迟优化的移动边缘计算任务调度方法。主要包括如下步骤:1、生成任务描述集合G={Ti|1≤i≤N},Ti=(di,ci);初始化目标值Val_new。2、计算每个任务的本地执行时间边缘服务器执行时间任务卸载传输时间边缘服务器执行耗能本地执行耗能3、基于CPU处理任务所需周期数的卸载调度方法求卸载决策向量x;并根据决策向量x对所有任务进行分类,卸载执行与本地执行任务分别放入S、L中;4、对集合S中所有任务的功率p采用凸优化方法求解,并将Val_new的值存入Val_old中,即Val_old=Val_new,求解新的目标值Val_new;5、比较新算出的目标函数值与上一次循环目标值的差值,如果Val...

反馈

验证码:
看不清楚,换一个
确定
取消

成果认领

标题:
用户 作者 通讯作者
请选择
请选择
确定
取消

提示

该栏目需要登录且有访问权限才可以访问

如果您有访问权限,请直接 登录访问

如果您没有访问权限,请联系管理员申请开通

管理员联系邮箱:yun@hnwdkj.com