CN110062026A - 移动边缘计算网络中资源分配和计算卸载联合优化方案 - Google Patents

Abstract

本发明公开了移动边缘计算网络中无线带宽和计算资源联合分配方案，属于无线通信和移动边缘计算领域，解决了异构无线网络中多用户多移动边缘服务器部署场景下的资源竞争和负载均衡问题。方案具体包括：宏基站控制器收集本时隙内所有用户端发送的计算卸载请求信息，并通知其管辖区域内所有MEC服务器报告当前资源剩余情况；根据所获取的信息，宏基站控制器将用户计算任务和MEC服务器资源进行首次匹配；制定MEC服务器中无线带宽和计算资源分配规则；建立合作博弈模型输出最终匹配策略集。本发明兼顾了每个用户的特性，有效地降低了计算卸载的费用开销，节约了移动用户端能耗。在相同数量MEC服务器部署情况下，本发明方案能够接纳更多的计算卸载任务，平衡了服务器之间的通信和计算负载，提升了系统的任务执行效率。

Description

移动边缘计算网络中资源分配和计算卸载联合优化方案

技术领域

本发明涉及无线通信技术和移动边缘计算领域，具体涉及了一种移动边缘计算网络中资源分配和计算卸载联合优化方案。

背景技术

移动边缘计算的出现为资源受限的移动设备提供了一种有效的解决方案。移动设备可将全部或者部分计算密集型任务通过无线信道卸载到计算资源相对丰富的移动边缘计算服务器(Mobile Edge Computing，MEC)来降低本地处理任务时延和能耗。但是执行计算卸载可能会带来额外的传输时延和能量消耗，确定最佳卸载决策是MEC网络中一项研究重点。此外，无线信道带宽和MEC服务器的计算容量均属于有限资源，在多用户MEC系统中无线电和计算资源以共享的方式提供给用户设备(User Equipment，UE)。不同的用户有着不同的计算任务和服务质量要求，所以针对不同的UE具有差异化的无线电和计算资源分配方式，计算卸载和服务器资源分配联合优化被认为是提高MEC网络性能的最重要问题之一。

近年来已有学者围绕移动边缘计算网络做了广泛的研究，文献1[Chen M,HaoY.Task Offloading for Mobile Edge Computing in Software Defined Ultra-denseNetwork[J].IEEE Journal on SelectedAreas in Communications,2018:1-1.]研究了超密集软件定义网络框架下的任务卸载问题，将任务执行延迟作为优化目标，提出了一种有效的软件定义任务卸载方案。文献2[Hongzhi G,Jiajia L,Jie Z.ComputationOffloading for Multi-Access Mobile Edge Computing in Ultra-Dense Networks[J].IEEE Communications Magazine,2018,56(8):14-19.]分析了密集MEC部署场景的任务卸载问题。提出了一种启发式贪心卸载方案作为计算卸载问题优化方案，仿真结果表明宏基站和小基站的MEC服务器协同使用可以提升系统性能。文献3[Zhang J,Xia W,Cheng Z,etal.An evolutionary game for joint wireless and cloud resource allocation inmobile edge computing[C]//20179th International Conference on WirelessCommunications and Signal Processing(WCSP).IEEE,2017:1-6.]主要研究基于进化博弈的联合云和无线资源分配算法，考虑移动终端的能耗和时间延迟以及移动边缘计算环境中的货币成本。分析了进化博弈的稳定性，并通过复制动力学方法得到进化平衡。文献4[赵力强,卢晓迪,梁凯,杨键,宋凤飞.一种提供移动边缘计算服务的网络系统及服务方法:中国.108494612[P].2018.09.04]公开了一种提供移动边缘计算服务的网络系统级服务方法，解决移动通信网络上MEC灵活部署的技术问题，在C-RAN架构中，部署基于SDN的MEC控制器，在BBU中部署MEC服务器。文中分别给出了本地MEC服务器计算、多个MEC服务器联合计算、特定非本地MEC服务器计算和云中心计算四种方式，控制器根据任务的计算量和延迟敏感度作为判决依据，判断使用哪种计算方式更加合理。文献5[张伟哲,方滨兴,何慧,刘川意,余翔湛,刘亚维,刘国强.一种多用户场景下的移动边缘计算任务卸载方法:中国.108920279[P].2018.11.30]为了降低移动设备的反应时延和能耗。所述的多用户场景是多个移动设备和MEC服务器相连，每个移动设备可选择该移动设备和MEC服务器之间的多条信道中的一个进行通信，MEC服务器通过主干网与中心云相连。具体涉及两个阶段：第一阶段是决定任务是在本地移动设备上执行还是卸载到MEC服务器执行；第二阶段是当服务器资源不足时，判定任务是继续在MEC服务器上等待还是卸载到远端云中心进行执行。

本发明人发现在异构网络环境下，多用户多MEC部署场景的MEC服务器资源分配存在以下几个问题：第一，在多用户单MEC服务器接入场景中，用户设备能耗和延迟优化问题涉及到无线带宽和计算资源联合分配。一部分文献仅考虑了计算资源分配而忽视带宽资源分配对优化结果的影响，另一部分文献虽然考虑了带宽资源和计算资源联合分配，但是仅仅将带宽资源按子载波形式等比例分配给每个用户。这看似保证了每个用户的公平性，但是对于输入数据量大的任务而言会显得带宽资源不够用，而对传输数据小的任务而言，带宽资源又有富余。造成了资源分配不合理现象，所以需要一种更细粒度的无线带宽资源分配方法，根据任务特定属性差异化提供无线带宽资源。第二，超密集异构MEC部署场景下一个用户设备可以同时关联多个MEC服务器，一个MEC服务器可以同时为多个UE提供服务，大量UE随机选择MEC服务器会造成负载不均现象。

发明内容

为了解决上述问题，本发明提出了移动边缘计算网络中无线带宽和计算资源联合分配方案。该技术方案涵盖了无线通信领域和移动边缘计算领域。在超密集异构MEC服务器部署环境中，密集地部署了不同类型的基站，每个基站均部署MEC服务器。实现一个用户可以同时关联多个MEC服务器，一个MEC服务器也同时为多个UE提供计算服务。该方案具体步骤：

步骤S1：移动用户产生新的计算任务，并向宏基站控制器发送任务卸载请求。

步骤S2：宏基站控制器收集本时隙内所有用户端发送的计算卸载请求信息，并通知其管辖区域内所有MEC服务器报告资源剩余情况。

步骤S3：宏基站控制器将用户计算任务和MEC服务器资源进行首次匹配，构成初始匹配策略集。

步骤S4：在步骤S3基础上制定MEC服务器中无线带宽和计算资源分配规则。

步骤S5：建立合作博弈模型，将用户作为博弈参与者，用户对不同MEC服务器选择方式作为博弈策略，以用户任务卸载成本和系统总卸载成本作为成本函数。

步骤S6：宏基站控制器从参与者集合中依次选取参与者，将参与者任务重新匹配到其他MEC服务器，计算出新的匹配方式下用户任务卸载成本和系统总卸载成本。

步骤S7：判断是否满足转移条件，如果是转步骤S6，如果不是转步骤S8。

步骤S8：判断是否达到平衡联盟结构，如果是转步骤S9，如果不是转步骤S6。

步骤S9：判断是否全部满足计算卸载条件，如果是，继续执行步骤S10，否则将不满足卸载决策的移动用户从参与者集合中剔除，返回步骤S6。

步骤S10：输出最终匹配策略集。

本发明的有益效果在于：本发明兼顾了每个用户的特性，有效地降低了计算卸载的成本开销，节约了移动用户端能耗。在相同数量MEC服务器部署情况下，本发明方案能够接纳更多的计算卸载任务。平衡了服务器之间的计算负载，提升了系统的任务执行效率。

附图说明

图1异构网络中MEC服务器部署场景

图2无线带宽和计算资源联合优化方案流程示

具体实施方式

结合附图对本发明的原理和特征进行描述，通过具体实施实例对本发明进一步作出解释说明。

如图1所示，异构网络由一个宏基站(Macro Base Station，MBS)和k小基站(SmallBase Station，SBS)组成，各基站之间存在完全重叠覆盖和交叉重叠覆盖区域，用户设备随机分散在整个区域中。MBS上部署资源调度控制器，统一管理宏基站覆盖下的所有MEC服务器，MEC服务器具有一定的云计算能力并且通过基站与移动设备建立无线信道连接。本发明将MEC服务器组成的集合表示为M＝{1,2,3,...,m,...,M}，UE组成的集合表示为N＝{1,2,3,...,n,...,N}。如图2所示，一种移动边缘计算网络中资源分配和计算卸载联合优化方案，包括以下步骤：

步骤S1，当移动用户产生新的计算任务时，可以通过控制链路向宏基站控制器发送计算卸载请求。计算卸载请求消息包含量计算任务的相关信息，可表示为ξ(L,T_d,W,C)。L是任务输入数据大小，T_d表示任务完成的截止期限，W表示任务计算强度，以CPU周期数表示，C表示用户计算任务处理预算，C的取值与任务自身属性和移动设备性能有关。

步骤S2，宏基站控制器每个一时隙就会收集一次用户端发送的计算卸载请求信息。并通过发送询问报文通知宏基站管辖区域内所有MEC服务器当前无线信道带宽资源和计算资源剩余情况。当所有信息收集完毕，开始进行资源分配。

步骤S3，在执行资源分配之前，本发明根据移动边缘计算空间部署网络场景，建立了无线传输模型、移动设备本地计算模型和边缘服务器计算模型，制定了系统效益最大化问题模型。宏基站控制器根据所建立的数学模型，计算出任务卸载到每一个服务器的成本，选取卸载成本最小的MEC服务器作为卸载目标。所有计算任务均匹配到相应的MEC服务器，构成初始匹配策略集。

步骤S3具体包括以下步骤：

步骤S31，建立通信模型。

设b_nm为MEC服务器m分配给UEn子信道的带宽，h_nm为子信道增益，p_n为UEn在子信道s的发射功率，本发明不考虑功率分配问题，将p_n视为一个不变常数。n₀为高斯白噪声，数据发送速率可得：

公式(1)中r_nm表示无线信道发送速率，表示来自其他UE的信道干扰。

步骤S32，建立本地计算模型。

设移动设备CPU计算容量为n表示第n个移动设备，l表示本地处理任务。UEn任务在本地处理延迟及能耗

式(3)中系数k_n表示芯片硬件架构相关系统，ε₀表示每个CPU周期单元所消耗的能量。根据公式(2)，(3)可以求出本地计算所产生的花费和UEn的计算任务处理预算C_n：

公式(5)中，Q(n)＝F(f₁,f₂,...,f_n)，f₁,f₂,...,f_n表示计算任务除延迟和能耗之外的其他的属性要求，例如安全性、可靠性以及任务相对重要程度要求等。分别表示在UEn处执行计算任务消耗掉延迟和能量消耗和其他属性的权重。

步骤S33，建立服务器设备计算模型。

UEn任务卸载到MEC服务器m所产生的时延主要包括传输延迟和服务器执行延迟两部分，分别由符号和表示，结合公式(1)可得：

公式(7)中是MEC服务器m分配给UEn的计算资源。

在计算卸载过程中，传输能耗也是不容忽视的花销，根据公式6)可计算出传输能耗的公式表达式为：

分别用α_m和β_m表示MEC服务器m单位带宽价格和单位计算资源价格，定义UEn在MEC服务器m处租用带宽资源和计算资源的成本为：

联立公式(6)、(7)、(8)和(9)，UEn将计算任务卸载到MEC服务器m需要承担的时间延迟，能量消耗和货币总成本为：

式中指延迟影响因子，表示能耗影响因子，表示货币影响因子。满足且所有影响因子取值范围在[0,1]之间。

步骤S34，建立基于效益最大化的无线带宽和计算资源联合分配的问题模型。

本发明将所有用户效用最大化作为优化目标，基于上述讨论，UEn效用函数U_n可表示为：

式(11)中且联合计算卸载、无线带宽和计算资源优化问题可表述为：

由公式(12)可以看出，系统效益函数U与卸载决策A，信道带宽B和计算资源F均有关系。

步骤S35，子问题划分。本发明将问题(12)划分为两个子问题：分别为无线带宽和计算资源联合优化子问题和计算卸载优化子问题，通过两者相互迭代获得最终结果。

本发明制定无线带宽和计算资源联合分配的问题模型中，假设所有UE计算任务都将卸载到MEC服务器执行。得到无线带宽和计算资源联合优化问题描述：

由于UEn任务一旦产生，任务执行预算C_n也能根据公式(5)进行确定。所以系统中总的任务执行预算是一个恒定不变的常数。因此可以将公式(13)进一步描述为最小化卸载成本问题，如公式(14)所示：

计算卸载优化问题可以描述为：

如公式(14)(15)所示，本发明已经将问题(12)分解为两个子问题，降低了问题求解难度。

步骤S36，用户计算任务和MEC服务器资源进行首次匹配。

在步骤S33中，UE根据公式(10)计算将任务卸载到每一个服务器的成本，选取卸载成本最小的MEC服务器作为初次卸载目标。

步骤S4，制定MEC服务器上无线带宽和计算资源分配原则。可分为两步：

步骤S41，制定无线带宽分配原则。

当MEC服务器m同时接收到了k个UE的任务卸载请求，记为集合K＝{1,2,...,k,...,K}，且B_m和F_m表示MEC服务器总的带宽资源和计算资源。MEC服务器为第k个UE分配的无线带宽资源和计算资源分别表示为b_km和f_km，满足∑_k∈Kb_km≤B_m,∑_k∈Kf_km≤F_m。为了最大化传输速率，将每个用户的任务输入数据量l作为带宽分配依据，第k个UE分配到的带宽大小可表示为：

根据公式(16)进一步获得通信成本：

步骤S42，制定计算资源分配原则。

MEC计算资源分配方式则按任务执行预算占比情况分配，任务执行预算由任务处理预算减掉通信花费所得。那么UEk分配到的计算资源大小可表示为：

步骤S5，建立合作博弈模型。

将系统中所有UE组成一个群体，本发明将这样的一个群体叫做联盟体，用D表示，定义合作联盟博弈形式：

G(D,(S_n)_n∈N,(π_n)_n∈N) (19)

式(19)中，本发明将UE作为博弈的参与者，用D表示参与者集合，S_n表示参与者UEn可用策略的集合，这里的策略指联盟中UE对系统中MEC服务器的选择。π_n表示参与者成本函数，具体包括能耗、时延和货币成本。根据公式(10)可以得出

步骤S6，宏基站控制器依次选取参与者进行卸载转移。根据步骤S4每个UE所获取的无线和计算资源，结合公式(10)计算出每个UE计算卸载成本和系统总执行成本Z^r。制定转移条件如公式(20)(21)所示：

Z^r(S'_n)≤Z^r(S_n) (21)

公式(20)表示UEn转移过后的卸载成本小于转移之前的成本，(21)表示转移过后的系统总成本小于转移之前的系统总成本。只有同时满足条件(20)(21)，UE才能在联盟之间进行转移。

步骤S7，判断是否满足转移条件(20)(21)，如果是，UE进行转移，更新UE转移之后的计算卸载成本更新系统总成本Z^r，更新转移前和转移后的联盟中所有UE的计算卸载成本，然后转步骤S6，否则转步骤S8。

步骤S8，判断是否达到平衡联盟结构。达到平衡联盟结构的条件是遍历所有UE均不满足转移条件(20)(21)。

步骤S9中判断所有参与者是否满足任务卸载条件，任务卸载条件如公式(22)所示：

公式(22)中，表示任务卸载执行成本，表示本地任务执行成本。如果满足公式(22)，输出最终资源分配结果。如果不满足公式(22)，即表示该UE在本地执行计算任务，将UE从博弈参与者集合中剔除，卸载成本更新为本机执行成本然后转步骤S6。

步骤S10中获得最终匹配策略集，宏基站控制器以广播形式将资源分配结果告知所有发送计算资源请求用户。如果移动用户从参与者集合中剔除，那么宣告此次资源请求失败，只有等待下一个时隙重新发送计算卸载请求。同时通知MEC准备接收UE卸载的计算任务。

Claims (11)

1.移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，主要包括以下步骤：

步骤S1：移动用户产生新的计算任务，并向宏基站控制器发送任务卸载请求。

步骤S2：宏基站控制器收集本时隙内所有用户端发送的计算卸载请求信息，并通知其管辖区域内所有MEC服务器报告当前资源剩余情况。

步骤S3：根据步骤S2中所获取的信息，宏基站控制器将用户计算任务和MEC服务器资源进行首次匹配，构成初始匹配策略集。

步骤S4：在步骤S3基础上制定MEC服务器中无线带宽和计算资源分配规则。

步骤S5：建立合作博弈模型，将用户作为博弈参与者，用户对不同MEC服务器选择方式作为博弈策略，以用户任务卸载成本和系统总卸载成本作为成本函数。

步骤S6：宏基站控制器从参与者集合中依次选取参与者，将参与者任务重新匹配到其他MEC服务器，计算出新的匹配方式下用户任务卸载成本和系统总卸载成本。

步骤S7：判断是否满足转移条件，如果是转步骤S6，如果不是转步骤S8。

步骤S8：判断是否达到平衡联盟结构，如果是转步骤S9，如果不是转步骤S6。

步骤S9：判断是否全部满足计算卸载条件，如果是，继续执行步骤S10，否则将不满足卸载决策的移动用户从参与者集合中剔除，返回步骤S6。

步骤S10：输出最终匹配策略集。

2.根据权利要求1所述的一种移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，所述步骤S1中的移动用户随机分布于超密集异构无线网络中，该网络由一个宏基站和多个小基站组成，各基站之间存在完全重叠覆盖和交叉重叠覆盖区域，移动用户可以同时关联多个基站。宏基站上部署资源调度控制器，统一管理宏基站覆盖下的所有MEC服务器，MEC服务器具有一定的云计算能力并且通过基站与移动用户建立无线信道连接。当移动用户产生新的计算任务时，可以通过控制链路向宏基站控制器发送计算卸载请求。

3.根据权利要求1所述的一种移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，所述步骤S2中宏基站控制器每隔一个时隙就会收集一次用户端发送的计算卸载请求信息，并通过发送询问报文通知宏基站管辖区域内所有MEC服务器报告当前资源剩余情况。当所有信息收集完毕，开始进行资源分配。

4.根据权利要求1所述的一种移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，所述步骤S3中在执行资源分配之前，本发明根据移动边缘计算空间部署网络场景，建立了无线传输模型、移动设备本地计算模型和边缘服务器计算模型，制定了系统效益最大化问题模型。宏基站控制器根据所建立的数学模型，计算出任务卸载到每一个服务器的代价，选取卸载代价最小的MEC服务器作为卸载目标。所有计算任务均匹配到相应的MEC服务器，构成初始匹配策略集。

5.根据权利要求1所述的一种移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，所述步骤S4在步骤S3基础上控制器将MEC服务器的无线带宽资源按移动用户任务输入数据量占总任务输入量比例大小分配给每个接入本MEC服务器的移动用户，以最小化整体任务传输延迟，将计算资源按移动用户剩余预算占比大小分配给每个用户，兼顾了每个用户的公平性。

6.根据权利要求1所述的一种移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，所述步骤S5建立合作博弈模型。移动用户作为合作博弈的参与者，匹配同一个MEC服务器的移动用户群体作为一个联盟体，参与者可以匹配不同MEC服务器，所有的匹配方案构成策略集，移动用户卸载成本和系统总卸载成本作为博弈的成本函数。

7.根据权利要求1所述的一种移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，所述步骤S6中，根据步骤S4每个移动用户所获取的无线和计算资源，计算出每个移动用户计算卸载成本和整个系统总的卸载成本。制定参与者在联盟体中转移的条件：当转移之后移动用户卸载成本小于转移之前卸载成本且系统总成本小于转移之前的成本时，允许移动用户发生转移，否则禁止转移。

8.根据权利要求1所述的一种移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，所述步骤S7中判断所有参与者是否满足步骤S6的转移条件，如果满足，移动用户进行转移，更新移动用户转移之后的计算卸载成本，更新系统总卸载成本，更新转移前和转移后的联盟中所有移动用户的计算卸载成本，然后转步骤S6，否则转步骤S8。

9.根据权利要求1所述的一种移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，所述步骤S8中判断是否达到平衡联盟结构。达到平衡联盟结构的条件是遍历所有移动用户均不满足转移条件。

10.根据权利要求1所述的一种移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，所述步骤S9中判断所有参与者是否满足任务卸载条件，如果满足，输出最终匹配策略集，如果不满足任务卸载条件，将移动用户从博弈参与者集合中剔除，卸载成本更新为本机执行成本，然后转步骤S6。

11.根据权利要求1所述的一种移动边缘计算网络中资源分配和计算卸载联合优化方案，其特征在于，所述步骤S10中获得最终匹配策略集，宏基站控制器以广播形式将资源分配结果告知所有发送计算资源请求用户和MEC服务器。如果移动用户从参与者集合中剔除，那么宣告此次资源请求失败，只有等待下一个时隙重新发送计算卸载请求。