CN108990159B - 移动边缘计算系统中基于分层博弈的联合资源分配方法 - Google Patents

Abstract

本发明公开了一种移动边缘计算系统中基于分层博弈的联合资源分配方法，包括：(1)用户端根据不同的基站/AP接入策略建立代价函数；(2)基站/AP获取覆盖区域内各个移动用户端连接数和当前区域内的可用资源，反馈至用户端，用户端进行演进博弈，确定基站/AP选择并请求资源，且基站/AP将资源请求和网络信道信息发送至相连的MEC服务器；(3)MEC服务器基于完全势博弈进行资源共享，建立效用函数，利用KKT条件得到全局最优解；(4)基站/AP和MEC服务器根据全局最优解为当前请求用户端分配无线资源和计算资源。本发明基于分层博弈，最小化用户端代价和最大化服务器层收益，延长用户终端寿命，充分利用MEC服务器的有限资源，满足移动用户的任务处理需求。

Description

移动边缘计算系统中基于分层博弈的联合资源分配方法

技术领域

本发明涉及移动边缘计算技术，尤其涉及一种移动边缘计算系统中基于分层博弈的联合资源分配方法。

背景技术

在5G异构网络融合环境中，随着物联网技术以及智能移动终端的广泛普及，手机电视、增强现实、视频通话、语音聊天等移动数据业务带给用户全新的体验。但是，移动终端是资源受限的设备，种类繁多的互联网应用在丰富人们日常生活的同时，也在消耗着有限的终端设备资源，从而直接降低人们对应用服务的体验质量(QoE，Quality ofExperience)。移动云计算(MCC，Mobile Cloud Computing)是移动互联网技术和云计算技术自然结合的产物，基于异构无线通信网络基础设施，并拥有共享的云资源池，向移动终端设备提供计算、存储等网络资源，提供云服务，是提升用户QoE的有效途径。然而，将任务卸载至离用户远的中心云，无法满足一些对时延敏感的应用的需求。因此，架设在靠近用户的云端服务器被引入至移动云计算中，这一技术被称为移动边缘计算(MEC，Mobile EdgeComputing)。MEC的概念首先是由欧洲电信标准协会(ETSI)于2014年提出，并被定义为“在接近移动用户无线接入网络中为用户提供IT和云计算能力”。移动边缘云计算的目标是减少时延，确保高效的网络操作和服务交付，并提供改进的用户体验。

移动边缘计算系统中的资源分配是近年来的研究热点。移动用户将任务卸载至云端除了占用移动边缘云的计算资源之外，对任务的上传也需要占用通信资源，这在很大程度上增加了网络负载，因此需要考虑网络中通信资源与计算资源的有效利用。多服务器之间的资源共享不仅可以改善资源利用率及服务提供者的收益，也能提供给移动用户更多的资源，从而改善QoE。

本发明所涉及的服务器资源共享场景包括按区域分组的移动用户，基站/AP，MEC服务器，以及IP核心网与数据中心。用户通过无线链路连接至不同的基站或AP，基站/AP与MEC服务器之间通过光纤连接，各个服务器之间根据链路状态进行资源共享。每个MEC服务器接收相关基站的用户任务请求，当发生当前MEC服务器剩余资源不足时，各个服务器之间互相协作。由于MEC服务器是一种相对小型的计算资源池，其通信资源与计算资源相对有限。因此如何实现移动边缘云计算系统中服务器资源共享，最大化整个网络的收益是亟待解决的问题。

发明内容

本发明所要解决的技术问题是：

本发明针对当前服务器资源共享技术存在的问题，提供一种基于分层博弈的资源共享方法，上下层分别以最大化服务器收益和最小化用户代价为目标，满足基站/AP的通信资源和MEC服务器计算资源容量限制，延长用户终端寿命，同时实现各移动用户任务处理的有效性。

本发明为解决上述技术问题采用以下技术方案：

一种移动边缘计算系统中基于分层博弈的联合资源分配方法，该方法包括：

步骤1移动用户端根据不同的基站/AP接入策略建立代价函数；

步骤2基站/AP获取覆盖区域内各个移动用户端连接数和当前区域内的可用资源，反馈至移动用户端，移动用户端进行演进博弈，确定基站/AP选择并进行资源请求，且基站/AP将资源请求和网络的信道信息发送至相连的移动边缘计算MEC服务器；

步骤3MEC服务器基于完全势博弈进行资源共享，建立效用函数，利用KKT条件得到全局最优解，并将该解发送至基站/AP；

步骤4基站/AP和MEC服务器根据该全局最优解为当前请求用户端分配无线资源和计算资源。

优选地，步骤1中该代价函数包含能量消耗代价、时延代价和付费代价，所述代价函数表示为：

其中，E_m,k(B_m,k)表示能量消耗部分，T_m,k(f_m,k,B_m,k)表示时延影响部分，ε₁f_m,k+ε₂B_m,k为因占用基站/AP及MEC资源所需支付的费用，ε₁,ε₂分别为单位计算资源费用与单位通信资源费用，B_m,k为用户m向基站/AP k请求的通信资源数，f_m,k为用户m向MEC服务器k请求的计算资源总数，

分别为能量消耗、时延和付费的影响因子，该三项影响因子之和为1；

通过动态地调节影响因子

增加或减少能量消耗、时延和付费所占的比例。

优选地，步骤2中所述演进博弈包括：

设参与者为I个种群中所有M个用户，所有用户的集合为

策略为从K个基站/AP中选择一个网络接入，策略集合为

I个区域构成I个种群；

代价函数：

种群状态：矩阵

其中

且

其中n_i,k为种群i中选择基站k的用户数，M_i为种群i中的总用户数，

求解

其中，Θ_i为种群i中的用户集合，

上述问题的解即为演进博弈均衡下的纳什均衡解。

优选地，使用动态复制法求解

即求解：

其中：

π_i,k＝C_m,k(f_m,k,B_m,k),m∈Θ_i

且η为动态复制法中的增益因子，种群i中的平均收益为

其中x_i,k是与移动用户端选择接入的基站/AP相连的MEC服务器i向服务器k租借的资源，

当动态复制子满足

时达到演进均衡。

优选地，步骤3中MEC服务器进行资源共享包括：将通信资源和计算资源表示为归一化的资源利用率：

y_k＝x_i,k+σ_k

其中，

分别为服务器i向服务器k租借的计算和通信资源，a，β分别为对应的比例因子，

为服务器k的可用计算资源及通信资源，且x_i,k是与用户端选择接入的基站/AP相连的MEC服务器i向MEC服务器k租借的资源，y_k为MEC服务器k的归一化资源利用率，ξi_i为MEC服务器组总共提供给用户的资源，σ_k是MEC服务器k在本次资源共享之前已被占用的资源。

优选地，步骤3中完全势博弈包括用完全势博弈进行建模：

设参与者为K个MEC服务器

策略为X＝[x₁,x₂,...,x_i,...,x_K]；x_i＝(x_i,1,x_i,2,...,x_i,i,x_i,i+1,...x_i,K)^T

MEC服务器k的效用函数为

优化目标:

s.t.g_k(x_i)＝x_i,k≥0，k＝1,2,..K

其中，x_i,i是与无线用户端选择接入的基站/AP相连的MEC服务器i本身分配给用户端的资源，θlog[1+(x_i,k+σ_k)]为吞吐量所带来的收益，且θ为单位吞吐量带来的效益；γ_k(x_i,k+σ_k)^j为分配x_i,k资源所需要的成本，γ_k为单位资源成本因子，且该成本与资源利用率之间满足j的因子关系。

优选地，该完全势博弈的势函数为：

对该势函数进行迭代求解KKT条件，直至收敛即得到最优解即资源共享矩阵

其中

该最优解即为纳什均衡解。

优选地，在步骤3中根据链路状态信息将效用函数简化。

本发明采用以上技术方案与现有技术相比，具有以下技术效果：

本发明基于分层博弈，充分利用可相互通信的MEC服务器有限的资源，用户层和服务器层分别以最小化移动用户代价和最大化服务器收益为目标，并保证各移动终端任务处理的实时性。所述方法充分考虑终端任务处理需求，以及基站/AP通信资源和MEC服务器计算能力的限制，不仅可以改善资源利用率及服务提供者的收益，也能提供给移动用户更多的资源，从而改善用户体验。

附图说明

图1是本发明场景示意图；

图2是本发明的上下层博弈之间的联系；

图3是本发明的联合资源分配方法的流程图；

图4是本发明的演进博弈流程图。

具体实施方式

本发明基于分层博弈，充分利用可相互通信的MEC服务器有限的资源，在用户层和服务器层分别以最小化移动用户能耗代价和最大化服务器全局收益为目标，并保证各移动终端任务处理的实时性。下面结合附图对本发明的实施方法作进一步的描述。

如附图1所示，其中包括按区域分组的移动用户，基站，AP，MEC服务器，以及核心网。用户通过无线链路连接至不同的基站/AP，基站/AP与MEC服务器之间通过光纤连接，各个服务器之间根据链路状态通过无线通信进行资源共享。MEC服务器可作为一个模块部署在基站/AP内部，也可以通过有线连接部署在基站/AP附近。MEC服务器是一种相对小型的计算资源池，其通信资源与计算资源相对有限。每个服务器接收相关基站/AP的用户任务请求，若当前MEC服务器剩余资源不足时，各个服务器之间互相协作，进行资源共享。MEC服务器，基站/AP均可通过广域网连接至IP核心网。假设无线接入网络中共I个小区，表示为I＝{1,2,...,I}，每个小区内有多个用户请求资源，用户总数为M，用集合表示为

各个用户从所在区域中的可选基站/AP中选择一个接入。

如附图2所示，分层博弈中上下层博弈之间的关系可描述为：

底层用户根据上层广播的可用资源和不同策略下的效用函数进行演进博弈，选择基站/AP接入，目的是最小化自身代价函数；根据下层演进博弈的结果，向服务器层提交资源请求，MEC服务器进行完全势博弈从而实现资源共享，提高整体资源利用率。根据此结果，MEC服务器和基站/AP分别向用户分配计算和通信资源。另外，用户层面资源分配公式中的可用资源分别为：

(f_i,k,B_i,k)分别为服务器层中服务器i向服务器k租借的计算资源及通信资源。

如附图3所示，本发明的MEC服务器资源共享方法的基本步骤为：

(1)用户根据不同的基站/AP接入策略建立代价函数，其中，该代价函数包含能量消耗代价，时延代价和付费代价，且三项代价所占的比例可通过动态地调节相关因子增加或减少。能量消耗代价是移动用户接收和发送无线信息消耗的能量，时延代价为终端任务上传时间、MEC服务器处理时间和下行链路传输至用户所用时间之和，付费代价是因占用通信资源和计算资源分别向MEC服务器支付的费用；

(2)基站/AP获取覆盖区域内各个移动用户连接数和当前区域内的可用资源，反馈至用户端，用户端据此平均请求资源。基站/AP将资源请求和网络的信道信息发送至相连的MEC服务器；

(3)MEC服务器基于完全势博弈和各服务器的链接状态进行资源共享，建立效用函数，根据链路状态将函数简化，然后利用KKT条件得到纳什均衡解，并将纳什均衡解发送至终端；

(4)基站/AP和MEC服务器根据该全局最优解为当前请求用户分配通信资源和计算资源。

其中，步骤(1)中移动用户的代价函数为：

其中第一项为能量消耗部分，第二项为时延影响部分，第三项为因资源所需支付的费用，ε₁,ε₂分别为单位计算资源与单位通信资源费用。具体表达式如下：

式(1)中，

分别为能量消耗、时延和资费的影响因子。式(2)中，时延影响分别包括上行数据传输时间、任务处理时间和下行传输时间。b_m,s_m分别为用户应用请求上传所需的比特数和处理该请求需要的CPU指令数。由于经MEC服务器处理后输出的比特数相对很小，可将下行传输时间视为常数。另外，因回程链路的高速传输特点，时延部分中的回程链路传输时间忽略不计。式(3)中，

分别为用户端传输和接收信号功率。r_m,k为基站/APk分配给用户的传输速率，由香农信道容量公式可得式(4)，r_m,k与分配带宽B_m,k及信道参数G_m,k(即用户m与基站/AP k之间的信道增益)及

(高斯噪声方差)有关。

步骤(2)中用户请求的资源为：

式(5)为资源分配公式，根据选择各个基站/AP k的用户数目N_k和可用资源

为连接用户平均分配资源，因基站/AP和MEC服务器为其分配正交信道，用户之间无干扰。其中，

(f_i,k,B_i,k)分别为服务器层中服务器i向服务器k租借的计算资源及通信资源。

如附图4所示，步骤(2)所述的演进博弈具体描述如下：

参与者：I个种群中所有M个用户，

策略：从K个基站/AP中选择一个网络接入，策略集合为

种群：图中所示的I个区域构成I个种群；

种群状态：矩阵

其中

且

目标：

其解为演进博弈均衡下的纳什均衡解，求解方法为动态复制法：

其中：

π_i,k＝C_m,k(f_m,k,B_m,k),m∈Θ_i 式(8)

种群i中的平均收益：

具体实现算法流程图如附图4所示。

当动态复制子满足

时达到演进均衡。在实际中，可对该条件适当放宽限制。允许有一定的偏差因子ρ，即当

时，认为达到演进均衡。

如附图3所示，步骤(3)的详细描述如下：

与用户所选择接入的基站/AP相连的MEC服务器称为用户归属服务器。当用户按区域分组后，用户i进行资源请求，收到该请求后，相应的归属服务器根据服务器的链路状态，与各个服务器进行资源共享。将通信资源和计算资源表示为归一化的资源利用率，表示如下：

y_k＝x_i,k+σ_k

式(10)中，

分别为服务器i向服务器k租借的计算和通信资源，且x_i,k是归属用户服务器i向服务器k租借的资源，特别地，x_i,i是归属用户服务器i本身分配给用户端的资源。y_k为MEC服务器k的归一化资源利用率。ξ_i为服务器组总共提供给用户的资源。σ_k是服务器k在本次资源共享之前已被占用的资源，其中包含MEC服务器k在上一时隙的被占用的资源以及租借给其他服务器的资源

将资源利用率与资源成本的关系表示为γ_k(x_i,k+σ_k)^j,j>1形式，那么，在高资源利用率的情况下，服务器运行成本将会很高。这样，各个服务器之间会愿意进行资源共享来降低自己的资源利用率，从而降低成本，提高全局收益。本发明中服务器之间资源共享问题可用完全势博弈进行建模，可表述为：

参与者：K个MEC服务器

策略：X＝[x₁,x₂,...,x_i,...,x_K]；x_i＝(x_i,1,x_i,2,...,x_i,i,x_i,i+1,...x_i,K)^T

服务器k的效用函数：

优化目标:

s.t.g_k(x_i)＝x_i,k≥0，k＝1,2,..K

为服务器k的效用函数，式(11)中第一项为吞吐量所带来的收益，且θ为单位吞吐量带来的效益；第二项为分配x_i,k资源所需要的成本，与当前总的资源利用率有关，且γ_k为单位资源成本因子；对于归属用户服务器i的资源共享结果也会影响其他服务器的资源共享，即资源共享结果具有相关性。

该完全势博弈的势函数为：

对公式(13)的势函数进行迭代求解KKT条件，直至收敛即得到最优解即资源共享矩阵

其中

该最优解即为纳什均衡解。

步骤(3)中纳什均衡解的具体求解方法为：假设链路状态因子χ_i,k已知，为简化问题求解，我们假设当前服务器i与N个服务器进行资源共享，并设置成本与资源利用率之间的因子j＝2。式(13)可进一步写为：

首先验证优化目标是否可使用KKT条件求解，对x_i,k分别求二阶偏导：

可见，

对于每个x_i,k都是凹的，满足KKT条件的使用前提，因此，可转化为非线性补偿问题，用拉格朗日乘子法求解。构建拉格朗日(Lagrange)函数：

式(15)中，ω＝(ω₁,ω₂,...,ω_K)与ν为拉格朗日乘子(Lagrange multiplier)。KKT条件的一阶等价形式为：

g_k(x_i)≥0,k＝1,2,...,K,

h(x_i)＝0, 式(17)

ω_kg_k(x_i)＝0,

ω_k≥0,k＝1,2,...,K.

拉格朗日乘子的更新规则为：

ω_k(t+1)＝max{0,μ*x_i,k} 式(18)

式中，μ为迭代步长。

以上所述仅为本发明的一种优选实施例而已，本发明的保护范围并不以上述实施方式为限，但凡本领域普通技术人员根据本发明所揭示内容所作的等效修饰或变化，皆应纳入权利要求书中记载的保护范围内。

Claims (2)

1.一种移动边缘计算系统中基于分层博弈的联合资源分配方法，其特征在于，该方法包括：

步骤1、移动用户端根据不同的基站/AP接入策略建立代价函数；

步骤2、基站/AP获取覆盖区域内各个移动用户端连接数和当前区域内的可用资源，反馈至移动用户端，移动用户端进行演进博弈，确定基站/AP选择并进行资源请求，且基站/AP将资源请求和网络的信道信息发送至相连的移动边缘计算MEC服务器；

步骤3、MEC服务器基于完全势博弈进行资源共享，建立效用函数，利用KKT条件得到全局最优解，并将该解发送至基站/AP；

步骤4、基站/AP和MEC服务器根据该全局最优解为当前资源请求的移动用户端分配无线资源和计算资源；

其中，步骤1中该代价函数包含能量消耗代价、时延代价和付费代价，所述代价函数表示为：

其中，E_m,k(B_m,k)表示能量消耗代价部分，T_m,k(f_m,k,B_m,k)表示时延代价部分，ε₁f_m,k+ε₂B_m,k为因占用基站/AP及MEC资源所需的付费代价部分，ε₁,ε₂分别为单位计算资源费用与单位通信资源费用，B_m,k为用户m向基站/APk请求的通信资源数，f_m,k为用户m向MEC服务器k请求的计算资源总数，

分别为能量消耗代价、时延代价和付费代价的影响因子，该三项影响因子之和为1；

通过动态地调节影响因子

增加或减少能量消耗代价、时延代价和付费代价所占的比例；

步骤2中所述演进博弈包括：

设参与者为I个种群中所有M个用户，

策略为从K个基站/AP中选择一个网络接入，策略集合为

I个区域构成I个种群；

代价函数：

种群状态：矩阵

其中

且

其中n_i,k为种群i中选择基站/AP k的用户数，M_i为种群i中的总用户数，

求解问题：

其中，Θ_i为种群i中的用户集合，X^u代表种群状态矩阵；

上述问题的解即为演进博弈均衡下的纳什均衡解；

使用动态复制法求解

即求解：

其中：

π_i,k(t)＝C_m,k(f_m,k,B_m,k),m∈Θ_i

且η为动态复制法中的增益因子，种群i中的平均收益为

其中x_i,k是与移动用户端选择接入的基站/AP相连的MEC服务器i向服务器k租借的资源，

当动态复制因子满足

时达到演进均衡；

步骤3中MEC服务器进行资源共享包括：将通信资源和计算资源表示为归一化的资源利用率：

y_k＝x_i,k+σ_k

其中，

分别为MEC服务器i向MEC服务器k租借的计算和通信资源，α，β分别为对应的比例因子，

为MEC服务器k的可用计算资源及通信资源，且x_i,k是与移动用户端选择接入的基站/AP相连的MEC服务器i向MEC服务器k租借的资源，y_k为MEC服务器k的归一化资源利用率，ξ_i为MEC服务器组总共提供给用户的资源，σ_k是MEC服务器k在本次资源共享之前已被占用的资源；

步骤3中完全势博弈包括用完全势博弈进行建模：

设参与者为K个MEC服务器

策略为X＝[x₁,x₂,...,x_i,...,x_K]；x_i＝(x_i,1,x_i,2,...,x_i,i,x_i,i+1,...x_i,K)^T

MEC服务器k的效用函数为

优化目标:

s.t.g_k(x_i)＝x_i,k≥0，k＝1,2,..K

其中，X表示MEC服务器资源共享矩阵，

表示除MEC服务器i之外的其他服务器的资源共享结果，x_i,i是与移动用户端选择接入的基站/AP相连的MEC服务器i本身分配给移动用户端的资源，θlog[1+(x_i,k+σ_k)]为吞吐量所带来的收益，且θ为单位吞吐量带来的效益；γ_k(x_i,k+σ_k)^j为分配x_i,k资源所需要的成本，γ_k为单位资源成本因子，且该成本与资源利用率之间满足j的因子关系；

该完全势博弈的势函数为：

对该势函数进行迭代求解KKT条件，直至收敛即得到最优解即资源共享矩阵

其中

j代表成本与资源利用率之间的因子，该最优解即为纳什均衡解。

2.根据权利要求1所述的移动边缘计算系统中基于分层博弈的联合资源分配方法，其特征在于，在步骤3中根据链路状态信息将效用函数简化。

Images