1.云边协同计算中的卸载决策与资源配置联合优化的博弈方法,其特征在于,包括以下步骤:S1,构建云边协同计算环境模型;
S2,定义云边协同计算平台的性能模型;
S3,以任务卸载比例和边缘服务器最大配置资源为约束条件,用户设备和边缘服务器的响应时间为优化目标,建立多约束优化问题;
S4,根据拉格朗日乘子法、KKT条件和数值法求解优化问题,寻找用户设备的最优计算卸载策略、边缘服务器最优计算资源配置以及最优计算卸载策略;
所述S4中,包括以下步骤:
S41,求解用户设备的最优响应;
S42,求解边缘服务器的最优响应;
S43,求解总纳什均衡;
所述步骤S41包括:
首先,根据拉格朗日乘子法,将约束条件λi,0+λi,1+λi,2+...+λi,j=1重构为函数F(λi,0,λi,1,...,λi,j)=λi,0+λi,1+...+λi,j-1,然后结合目标函数和约束函数构造如下拉格朗日函数:其中,为拉格朗日乘数,
化简之后,得到:
当给定一个时,是λi,j的递增函数,所以基于经典二分法在给定的搜索区间中找到一个λi,j,使得具体流程为算法1,算法1包括以下步骤:
S1.1,接收相关参数,包括提供的
S1.2,初始化λi,j的搜索区间;
S1.3,使用二分法在搜索区间λi,j∈[0,1]中搜索找到一个λi,j,使得S1.4,根据以上二分法找到一个合适的λi,j,最终输出该λi,j;
λi,j是的增函数,所以λi,0+λi,1+λi,2+...+λi,j是的增函数;所以基于经典二分法找到一个合适的和一组(λi,0,λi,1,λi,2,...,λi,j),使得约束条件成立,具体流程为算法2,算法2包括以下步骤:
S2.1,接收第i个UE的相关参数;
S2.2,初始化的搜索区间;
S2.3,判断搜索区间是否大于ε;
当大于时,令等于搜索区间的中值,然后在当前的值下,调用算法1遍历k+1个服务器的节点,获得(λi,0,λi,1,λi,2,...,λi,j);然后再判断是否小于1,如果是则调整搜索区域为右半部分,然后返回到S2.3的起始继续进行,如果否则调整搜索区域为左半部分,然后返回到S2.3的起始继续进行;
S2.4,直到搜索区间小于ε时,直接输出和(λi,0,λi,1,λi,2,...,λi,j);
所述的初始搜索区间为[0,ub],ub的含义表示的搜索区间的上界,其中ub的求解如下:(1)如果j=0,当λi,0=1时,ub取得最大值,即:(2)如果j≠0,当λi,j=1时,ub取得最大值,即:所述S42包括:
1),求解边缘服务器的资源配置方案
首先,根据KKT条件,将约束f1,j+f2,j+...+fn,j≤Fj重构为函数g(f1,j,f2,j,...,fn,j)=f1,j+f2,j+...+fn,j-Fj,然后结合目标函数和约束函数构造如下拉格朗日函数:其中是拉格朗日乘子;根据上式,可以得到:
然后,根据KKT条件可以得到:
基于经典二分法在给定的搜索区间中找到一个fi,j,使得具体流程为算法3,算法3包括以下步骤:
S3.1,接收相关参数,包括提供的
S3.2,初始化fi,j的搜索区间;
S3.3,使用二分法在搜索区间fi,j∈[0,Fj]中搜索到一个fi,j,使得S3.4,根据以上二分法找到一个合适的fi,j,最终输出该fi,j;
目标是寻找一个合适的使得这一组计算资源配置方案(f1,j,f2,j,...,fn,j)满足约束条件f1,j+f2,j+...+fn,j≤Fj;采用经典二分法,找到一个合适的和一组(f1,j,f2,j,...,fn,j),使得约束条件成立,具体流程为算法4,算法4包括以下步骤:
S4.1,接收第j个MEC的相关参数;
S4.2,初始化的搜索区间;
S4.3,判断搜索区间[0,ub']范围是否大于ε,ub'表示的搜索区间的上界;
当大于ε时,令等于搜索区间的中值,在当前值下,调用算法3遍历n个用户节点,获得f1,j,f2,j,...,fn,j;然后判断是否小于Fj,如果是,则调整搜索区间为左半部分,然后返回到S4.3的起始继续进行,如果否,则调整搜索区间为右半部分,然后返回到S4.3的起始继续进行;
当小于ε时,输出和f1,j,f2,j,...,fn,j;
的初始搜索区间为[0,ub'],ub'表示的搜索区间的上界,根据公式(5),取fi,j=1,那么
2),求解边缘服务器的计算卸载策略
基于二分方法的算法5,在给定的搜索区间中找到使最终求到一组计算卸载策略算法5包括以下步骤:
S5.1,接收第j个MEC的相关参数;
S5.2,遍历所有的用户节点,初始化的搜索区间;
S5.3,判断搜索区间范围是否大于ε;
当大于时,则令等于搜索区间中值,然后计算是否小于0,如果是,则调整搜索区间为右半部分,然后返回到S5.3的起始继续进行;如果否,则调整搜索区间为左半部分,然后返回到S5.3的起始继续进行;
当小于时,输出
3),求解边缘服务器的计算卸载与资源配置联合策略
首先初始化子博弈的动作组合z=(z1,z2,…,zk),其中然后,每个MEC通过使用算法3-算法5来找到自己对当前情况的最佳响应,当连续两轮的动作组合足够接近时,即该算法终止,最终的收敛动作组合z*=(z1*,z2*,…,zk*)作为纳什均衡返回;z'为新一轮的动作组合,fi,j'、'表示新一轮z状态下边缘服务器的计算资源和卸载比例的取值;
所述步骤S43包括:
首先初始化总博弈的动作组合x=(λ1,λ2,…,λn,z1,z2,…,zk),其中x包含所有用户的计算卸载策略和所有服务器的资源分配和计算卸载策略;然后,每一轮中,每个UE找到自己对当前情况的最佳响应;每个MEC找到自己对当前情况的最佳响应,当连续两轮的动作组合足够接近时,即该算法终止,最终的收敛动作组合x*=(λ1*,λ2*,…,λn*,z1*,z2*,…,zk*)作为纳什均衡返回。
2.根据权利要求1所述的云边协同计算中的卸载决策与资源配置联合优化的博弈方法,其特征在于,所述S1中,包括三层网络体系,第一层由多个异构UE模型组成、第二层由多个MEC模型组成和第三层由一个远程DC模型组成;
所述UE模型中,向量(λi,0,λi,1,λi,2,…,λi,k)是用户设备ui的计算卸载策略,ui的计算数据ri可以被划分为k+1份,分别由用户设备ui,边缘服务器s1,s2,…,sk执行处理;其中λi,0∈[0,1]为用户设备ui在本地处理的计算任务的比例,λi,j∈[0,1]表示卸载到边缘服务器sj远程处理的计算任务的比例;
所述MEC模型中,每个边缘服务器sj都为地理区域内的n个用户设备U={u1,u2,…,un}提供计算卸载服务,sj将从n个UE接收到一组计算数据,计算数据表示为一个向量(λ1,jr1,λ2,jr2,…,λn,jrn),其中λi,jri表示来源于用户设备ui的计算数据总量;MEC需计算是否将任务完全或部分卸载到DC;Fj表示sj配置的总计算资源,fi,j表示边缘服务器为用户设备分配的计算能力,则边缘服务器sj的资源分配策略表示为向量(f1,j,f2,j,…,fn,j),有以下约束条件:对于所有1≤j≤k;
所述DC模型中,DC保证在任何输入数据大小下都可以在tdc内完成执行,其中tdc为云数据中心的处理延迟。
3.根据权利要求1所述的云边协同计算中的卸载决策与资源配置联合优化的博弈方法,其特征在于,所述S2中,包括UE的性能模型和MEC的性能模型;
其中,建立UE的性能模型来分析UE生成的任务的平均响应时间,用户设备ui的平均任务响应时间为:λi,0∈[0,1]为用户设备ui在本地处理的计算任务的比例,ri表示输入任务数据的大小,ci表示处理1-bit数据所需的CPU周期数,fi表示用户设备的CPU频率,表示从ui卸载的任务即将进一步从sj卸载到DC的任务的比例,λi,j∈[0,1]表示卸载到边缘服务器sj远程处理的计算任务的比例,Ri.j用户设备ui与边缘服务器sj的无线通信速率,fi,j表示边缘服务器为用户设备分配的计算能力,Rdc表示广域网中的平均数据传输速率,tdc云数据中心的处理延迟为,d表示从MEC向DC传输数据时的平均传播延迟;
其中,建立MEC的性能模型来分析MEC生成的任务的平均响应时间,边缘服务器sj的平均任务响应时间为:λl,jrl与λi,jri含义相同。
4.根据权利要求1所述的云边协同计算中的卸载决策与资源配置联合优化的博弈方法,其特征在于,所述S3中,遵循的约束条件为:
1),λi,j∈[0,1],且λi,0+λi,1+λi,2+...+λi,j=1,对于所有1≤i≤n;
2),对于所有1≤i≤n和1≤j≤k;
3),fi,j∈[0,Fj],对于所有1≤j≤k;
其中,λi,j∈[0,1]表示卸载到边缘服务器sj远程处理的计算任务的比例,表示从ui卸载的任务即将进一步从sj卸载到DC的任务的比例,fi,j表示边缘服务器为用户设备分配的计算能力,Fj表示sj配置的总计算资源。