移动边缘网络下服务缓存与资源分配联合优化策略

龙隆，刘子辰，陆在旺,2，张玉成,2，李蕾,2

（1.中国科学院计算技术研究所，北京 100190；2.中国科学院大学计算技术研究所，北京 100049）

0 引言

随着移动通信与物联网的高速发展，许多计算密集和时延敏感应用（如无人驾驶、图像识别以及自然语言处理等）产生，这类具有低时延高可靠特点的应用对终端设备的计算能力提出较高要求[1]。由于计算能力有限的终端设备在处理这类应用时将产生较高的任务时延，因此如何降低应用处理时延是目前亟待解决的关键问题之一。移动云计算（MCC,mobile cloud computing）技术的出现很好地解决了终端计算能力受限的问题。MCC 的目标是将云端丰富的计算资源扩展至资源受限的终端设备，从而增强终端设备潜在的计算能力[2-4]。终端设备与云服务器间较远的通信距离所产生的网络时延使单纯依靠MCC 无法满足时延敏感型应用程序的时延要求。为了克服以上问题，并对MCC 技术进行补充，移动边缘计算（MEC,mobile edge computing）作为一种新的技术被提出[5-6]。移动边缘计算主要由基站及其边缘服务器组成。当终端设备执行计算任务时，由基站与服务器组成的边缘节点可以就近为这些终端提供计算、通信以及数据存储等服务，从而降低任务执行时延、提高系统性能。目前，基于MEC 网络的任务卸载和资源分配等问题已有相关研究。文献[7-9]在不同应用场景下以最大化能效为目标，对系统频谱资源和功耗等进行联合优化。文献[10-11]分别以最小化能耗、时延为目标，对计算与频谱资源进行联合优化。然而在实际应用中，边缘服务器的计算资源与存储资源是有限的，过多的计算请求必然为边缘服务器带来较高的计算与存储压力，进而影响系统性能。MCC 与MEC 融合网络下的资源分配与卸载方案为解决以上问题提供了新的解决思路。在MCC 与MEC 融合的网络架构中，终端设备进行任务请求时，既可以在本地执行，也可以在边缘服务器或云端执行。因此，该网络架构可以为终端提供更高效且更灵活的卸载服务，从而满足不同的服务需求。目前已有相关研究表明，在三级网络架构下通过卸载决策与资源分配联合优化的方式可以提升网络性能[12-13]。在MEC 与MCC 融合的集中式网络下，文献[12]对卸载决策与资源进行联合优化，以降低所有终端的任务时延；文献[13]以最大化系统收益为目标，对任务卸载与资源分配进行联合优化设计。

上述研究从不同方面解决任务卸载与资源分配联合优化问题，但是这些研究忽略了任务卸载与服务缓存耦合性对系统性能的影响。这里的服务缓存是指将与计算任务相关的数据库、应用程序、函数库以及相关代码等放在边缘服务中，从而支持不同类型的应用程序。从任务卸载角度可以将现有MEC 研究分为两大类，即计算任务完全卸载与计算任务部分卸载。完全卸载模型适用于高度集成或相对简单的任务，如自然语言处理、导航等任务，这些任务不能被分割，并且只能在移动设备上执行或者作为一个整体由边缘服务器执行。部分卸载模型适用于可分割的任务，如图像识别、增强现实（AR,augmented reality）应用等，这类应用的任务可以被分割为多个子任务通过并行或串行的方式执行。与完全卸载模型相比，基于部分卸载模型的资源分配更加合理，资源利用率也更高。目前，关于服务缓存与资源分配已有相关研究。文献[14]以最小化供应商成本为目标，提出了一种整数线性规划和随机搜索算法，对边缘节点间的服务缓存资源进行优化。文献[15]以最小化服务缓存总成本为目标，对边缘服务器的位置和用户服务需求进行联合优化。文献[16]以最小化时延与成本为目标，对边缘服务器的内容缓存进行协同优化。尽管以上研究通过任务卸载与服务缓存优化使系统性能得到提升，但都是基于任务不可分的情况进行的资源分配优化，而对任务可分的情况不适用。

大多数复杂的应用程序由多个不同的执行组件组成，如执行实时面部识别任务时需要将其分为4 个子任务分别处理，即人脸检测、图像处理与特征提取、人脸识别。这些子任务所需的计算资源、存储资源以及带宽资源各不相同。因此，如何基于部分任务卸载和服务缓存联合优化是目前亟待解决问题。文献[17]通过构建服务链模型，在存储资源以及计算资源约束下以最小化网络响应时延为目标，通过开放马尔可夫排队网络模型构建边缘节点服务调度模型，并对缓存决策与计算资源联合优化，但在任务卸载过程中忽略终端设备以及云服务器资源等可用资源。文献[18]基于部分卸载模型，在计算资源约束下对服务缓存与任务卸载进行联合优化研究，但其假设带宽资源均匀分配，导致计算数据量较大的任务得到较少的带宽资源而产生较高时延，计算数据量较少的任务得到较多的带宽资源造成资源浪费。另外，文献[18]并未对边缘节点的存储空间进行约束，这意味着在该研究中边缘服务端拥有无限大的存储空间，可以缓存所有任务执行所需的相关数据，这在实际应用场景下显然不合理。

综上所述，本文将在终端、边缘服务以及云构成的三层网络架构下，综合考虑无线带宽资源、计算资源以及存储资源等因素。通过计算、通信、存储融合的思想，以最小化所有终端设备的任务时延为目标，综合考虑存储资源、计算资源、卸载决策以及任务卸载比例等对任务时延的影响，提出一种服务缓存与资源分配的联合优化算法。具体创新点介绍如下。

1) 构建了一个由多用户、边缘服务器以及云服务器组成的三层网络架构，每个用户的计算任务可以通过部分卸载的方式将任务分别卸载至本地、边缘服务器或云服务器。引入了最小化终端任务时延模型，考虑了用户计算资源、边缘服务的计算资源、存储资源以及带宽资源等因素对时延的影响。

2) 提出了服务缓存与资源分配联合（JSCRA,joint service caching and resource allocation）优化策略。首先，将原问题的连续变量与离散变量进行解耦，变为2 个子问题，即服务缓存决策问题、计算资源与通信资源联合优化问题。其次，基于重构线性化技术（RLT,reformulation linearization technique）、松弛以及凸优化方法对2 个子问题进行交替迭代优化。最后，获得问题次优解。

3) 仿真结果表明，与随机缓存和资源分配（RCRA,random caching and resource allocation）策略相比，所提策略在收敛速度和性能表现上都有明显优势，可以获得更低的任务时延。

1 系统模型

1.1 集中式移动边缘网络模型

集中式移动边缘网络如图1 所示。从图1 可以看出，集中式移动边缘网络由云服务器、单一服务节点（由边缘服务器与基站组成）以及L个具有计算与通信能力的终端组成。这里的终端泛指具有计算能力的终端设备，如手机、平板电脑、车辆等。终端个数表示为L={1,2,…,L}，i∈L。云服务器与服务节点通过光纤进行有线连接，为终端提供稳定的通信、计算以及存储服务。这里的云服务器主要由云服务器集群组成，因此拥有丰富的计算资源与存储资源。

图1 集中式移动边缘网络

在图1 所示场景中，服务节点不仅可以为终端提供通信、计算以及存储资源，而且扮演着协调器的角色，即根据终端的任务请求提供存储决策以及计算决策。这里假设边缘服务器存储计算服务的最大存储容量为C，最大计算能力为F。计算服务数据主要由数据库、数据字典以及相关的应用代码组成，其中每一种应用代表一个类型的计算任务。此外，由于存储是一个长期的过程，因此需要服务缓存进行定时更新。本文认为系统在离散的时间段中运行，每个时间段的持续时间与服务缓存和任务分配决策更新的时间尺度相匹配。本文对其中一个时间段进行研究，忽略其他时间段的索引[18]。在一个时间段的开始阶段，每个终端随机请求一个计算任务，其中一类计算任务对应一类计算服务。这里假设存在计算服务K={1,2,…,K}，表示用户i请求计算服务Ai相应的任务，Ai∈K，其中，表示终端i执行服务Ai相关任务的输入数据大小，si表示执行1 bit 数据所需循环数。为了便于分析，本文做出如下合理假设。

1) 服务节点已知信道状态信息（CSI,channel state information）、每个任务输入数据的大小以及执行任务所需的循环数。基于以上假设，可以得到优化的卸载决策以及资源分配[19]。

2)每种应用的计算结果数据都远小于计算输入数据，因此忽略计算结果的回程链路传输时延[20]。

1.2 通信模型

本文采用正交频分复用的方式将频谱资源分配给终端设备，频谱的总带宽为B。由于每个终端设备将计算任务卸载至服务节点时会占用上行频谱资源，因此终端i执行服务Ai相关任务的上行传输速率可以表示为[12]

其中，为终端上传数据所占上行带宽百分比，Pi,s为终端的发送功率，hi,B为基站与终端间的信道衰落系数，d为终端与基站的距离，r为路径损耗，σ2为信道的噪声功率。

1.3 服务缓存模型

若边缘服务器存储计算服务，则意味着服务节点可以处理相关的计算任务，否则将任务交由云服务器执行。由于边缘服务器的存储空间有限，故无法满足所有终端设备的计算请求，因此边缘服务器需要对所缓存的服务数据进行决策。这里将服务端的存储决策表示为，∈ { 0,1}且Ai∈K，i∈L；表示服务器是否缓存终端设备请求的Ai，xAi=1表示服务器缓存计算服务Ai，=0表示服务器没有缓存相应的计算服务Ai。每个服务Ai所需存储大小为，而边缘服务器缓存决策受到存储容量的限制，即

1.4 计算任务卸载模型

任务部分卸载意味着计算任务可以分解成多个大小不同的子任务。本文将基于卸载模型（即向代码分区的应用，如图像识别，这类应用分为多个模块，其中一个模块的输出结果为下一个模块的输入）进行研究，接下来本文将在部分卸载模型下，对任务执行时延模型进行描述。

1) 当计算服务Ai存储在边缘服务器时，任务可以在边缘服务器执行，此时任务执行时延分析如下。

如果部分任务在服务节点卸载，任务卸载至边缘服务器时，任务卸载百分比表示为1-，相应的任务卸载至边缘服务器的数据大小表示为。分配给终端设备的计算资源表示为，任务在边缘服务器的执行时延表示为

当任务卸载至边缘服务器时，终端设备将占用上行链路对数据进行传输，此时上行链路的传输时延表示为

综上所述，当计算服务存储在服务中心时，任务执行总时延表示为

2) 当计算服务Ai未存储在边缘服务器时，计算任务将在本地以及云端进行部分卸载。

如果任务卸载至云服务器，卸载百分比表示为1-，其中，任务卸载至边缘服务器的数据大小表示为。基于前文假设，云服务器具有丰富的计算资源，所以任务执行时延只与传输时延有关，即上行链路传输时延以及回程链路传输时延。因此，任务在云服务器执行时其传输时延表示为

其中，R为边缘服务与云服务器之间的传输速率。因此，计算服务存储在云服务器时任务执行总时延表示为

2 问题的形式化描述

由于存储是一个长期统计的过程，因此其在短期内变化很小，但计算与通信资源是实时的，需要根据不同用户的任务需求实时变化。基于以上特点，本文考虑在当前时间段内对计算、通信以及存储资源进行联合优化。本文的主要目标是在计算、通信、存储资源约束条件下，对服务缓存决策x、上行频谱资源θ、任务部分卸载百分比α和β，以及服务器计算资源f联合优化，以最小化所有终端设备执行任务总时延。优化目标可以表示为

从P0 可以看出，约束条件C1表示分配给所有终端设备的计算资源总和小于或等于服务器的最大计算能力，C2 表示分配给所有终端设备的频谱资源小于或等于总频谱带宽，C3 表示任务卸载比例，C4 表示服务缓存决策，C5 表示边缘服务器可以缓存计算服务的最大容量。此外，P0 是由离散变量与连续变量组成的混合整数非线性规划问题，很难求解，因此需要设计一种新的优化方法对该问题进行求解。

3 服务缓存与资源分配联合优化策略

为了解决以上问题，本文提出一种面向任务卸载与服务缓存问题的服务缓存与资源分配的联合优化策略，简称为服务缓存与资源分配的联合优化策略。首先，将原问题的连续变量与离散变量进行解耦，变为2 个子问题，即服务缓存决策问题以及计算资源与通信资源联合优化问题；其次，在固定缓存决策基础上对计算与通信资源分配问题进行求解；再次，在得到优化的资源分配变量后对缓存决策进行优化；最后，通过循环迭代得到原问题的解。

3.1 计算资源与通信资源联合优化

首先，初始化缓存决策；随后，对计算与通信资源进行联合优化。在给定缓存决策条件下，P0 变成由计算资源、带宽资源以及任务卸载比例等连续变量组成的函数。接下来将对连续变量进行求解。在给定初始缓存决策为x(0)后，多终端时延优化函数表示为

相应的优化问题表示为

缓存决策确定后，其相应的约束条件同时发生变化，其约束条件将由C1变为C6。为了避免除零情况的发生，对变量加入常量ε1、ε2，可表示为。最后将该变量代入式(10)以及对应的约束条件中，得到新的函数以及约束条件。相应的问题表示为

由P2 可以看出，式(12)中存在2 个变量相乘的乘积项，因此该问题是一个非凸优化问题。为了求解P2，需要对以上问题进行再次变换。

3.2 基于RLT 的问题转换

其中，{·}LS表示线性化步骤。将代入式(14)可得

其中，∀i∈L。同理，对应的RLT 因子积约束条件为

经过以上变换后，得到新的优化问题P3 为

3.3 缓存优化问题的解决

获得P1的解后，下面解决缓存决策问题。首先，将获得的资源分配方案α(0)、β(0)、θ(0)、f(0)代 入P0，得到缓存决策问题P4 为

P4 是0-1 问题，可以通过分支定界法对以上问题进行求解。然而，分支定界法在最坏的情况下需要运算2k次，当输入数据量较小时，其复杂度是可接受的；随着输入数据量的增大，则很难在有效时间内获得近似最优解。为了降低时间复杂度，本文将整型变量松弛成的连续变量。此时，P4 变为凸优化问题，可以通过内点法与KKT（Karush-Kuhn-Tucker）条件进行求解。随后采用四舍五入的方法对连续变量进行恢复，这里将阈值简单设置为0.5。

3.4 算法描述

基于上述分析可知，边缘服务器通过阶段性获取当前接入终端的完整信息，执行JSCRA 优化策略，并将缓存决策以及资源分配结果发送至终端设备，从而最小化所有设备任务的执行时延，具体步骤如算法1 所示。

算法1服务缓存与资源分配联合优化算法

初始化边缘服务的缓存策略，终端发射功率pi,s，任务的输入数据大小，每比特输入数据所需的计算量si，最大迭代次数tmax，算法终止条件ξ。

步骤1在已知服务缓存策略基础上，原问题变换为连续非线性问题，得到新问题P2。

步骤2通过RLT 技术对P2 松弛，将非线性问题变为凸优化问题P3。

步骤3采用内点法对P3 进行求解，并得到在已知缓存决策条件下的资源分配方案。

步骤4将步骤3 得到的解代入P4，通过松弛法以及凸优化方法得到相应的卸载决策。

步骤5获取步骤3 与步骤4 中目标函数的差值，如果差值小于ξ或者迭代次数达到最大值tmax，则停止计算；否则，对步骤3 以及步骤4 进行循环迭代。

4 仿真实验与性能评估

本节在MATLAB 2017b 上进行仿真实验，并分析JSCRA 优化策略的性能。此外，为了进行性能对比，本文对以下基准策略进行了仿真。

完全本地卸载（LOC,local offloading completely）策略：所有任务均在终端本地进行处理，此时假设本地终端存储任务相关的服务数据[21]。

完全卸载至云（COC,cloud offloading completely）策略：任务相关服务数据全部存储在云服务器，此时任务完全在云服务器执行，而上行链路带宽资源均匀分配给每个终端设备[18]。

随机缓存与资源分配（RCRA,random caching and resource allocation）策略：在存储约束条件下，边缘服务器采用随机缓存策略尽可能多地缓存服务内容并在其基础上对计算与带宽资源进行优化[18]。

4.1 仿真参数设置

在仿真实验中，终端设备的数量为10，随机分布在边长为500 m 的正方形区域内。hi,B服从均值为1 的指数分布[22]，计算任务数据大小表示为ci且服从[100,200]KB 的均匀分布，si设置为1 500 cycle/bit。仿真参数设置如表1 所示。

表1 仿真参数设置

4.2 算法复杂度与收敛性分析

由于原始问题P0 是混合整数非线性规划问题，通过穷举法求解问题的复杂度为O(2n)，呈现指数级增长。所提算法将原始问题P0 转换成为P3 与P4，P3 为标准凸优化问题，可以通过内点法解决，内点法的复杂度为O(n3)；P4 为0-1 问题，离散变量经过松弛后为凸优化问题，其算法复杂度为O(n3)，此外，交替迭代次数的复杂度为O(n)，因此，所提算法总体复杂度为O(n3)。与穷举法相比，所提算法复杂度大大降低。

算法收敛过程如图2 所示。本文将通过穷举法获得的值作为最优解。由于穷举法非常耗时，因此一般在小规模场景下使用。由图2 可以看出，所提算法通过迭代25 次快速收敛并接近最优解，这表明所提算法性能非常接近于穷举法的性能，并可以获得近似最优解。

图2 算法收敛过程

4.3 仿真结果和分析

本节仿真结果是在配置有 Intelcorei59400F 2.9 GHz 处理器和 16 GB RAM 的台式机上用MATLAB 2017b 实现的。在N=10，C=300 GB，R=1的条件下，边缘服务器的计算能力和存储能力对任务执行时延的影响分别如图3 和图4 所示。

图3 边缘服务器的计算能力对任务执行时延的影响

图4 边缘服务器的存储能力对任务执行时延的影响

从图3 可以看出，随着边缘服务器的计算能力逐渐增大，所提JSCRA 优化策略与RCRA 策略的任务执行时延逐渐减小，而LOC 策略以及COC策略任务执行时延保持不变。这是因为LOC 策略的任务时延仅与本地计算能力有关，任务执行时延与边缘服务器所拥有的资源没有关系，所以LOC策略的所有任务执行时延保持不变。对于COC 策略而言，当任务在云服务器执行时，其任务执行时延仅与无线带宽资源以及回程链路传输速率有关，因此COC 策略的任务执行时延不随边缘服务器计算能力的增大而改变。另外，从图3 还可以看出，JSCRA 优化策略在性能上略优于RCRA 策略，这是因为JSCRA 优化策略对服务缓存进行合理优化，使更多任务可以在边缘服务器中执行，因此性能优于RCRA 策略。

从图4 可以看出，随着边缘服务器的存储能力逐渐提升，所提策略与RCRA 策略任务执行时延逐渐减小，而LOC 策略以及COC 策略的任务执行时延保持不变。所提策略与RCRA 策略相比可以减少10%的任务执行时延，与COC 策略相比可以减少30%的任务执行时延。LOC 策略的任务执行时延仅与本地计算能力有关，COC 策略的任务执行时延与带宽资源以及回程链路传输速率有关，所以LOC 策略与COC 策略的任务执行时延不随边缘服务器存储能力的大小变化。此外，从图4 可以看出，随着边缘服务器存储能力的增加，与COC 策略相比，所提策略与RCRA 策略性能增益增大。这是因为当边缘服务器存储能力较小时，只能缓存部分计算服务，剩余服务将存储在远端云服务器。此时，大多数任务将在云服务中执行，因此所提策略与RCRA 策略的任务执行时延性能略优于COC 策略。但是，随着存储能力的增加，边缘服务器可以缓存的服务内容增多，远端执行任务比例逐渐降低，此时边缘服务器计算资源被充分利用，因此所提策略与RCRA 策略的性能显著优于COC 算法。

任务输入数据大小对任务执行时延的影响如图5 所示。从图5 可以看出，任务输入数据越大，所有策略的任务执行时延越大，而所提策略的性能优于其他策略。这是因为随着输入数据量的增大，任务所需的计算资源与通信资源将会增多，所有策略的任务执行时延逐渐增大。另外，由于所提策略对计算、通信以及存储资源进行联合优化，因此其性能优于其他策略。

图5 任务输入数据大小对任务执行时延的影响

边缘服务器与远端云间传输速率对任务执行时延的影响如图6 所示。从图6 可以看出，随着边缘服务器与远端云间的传输速率逐渐增大，所提策略与RCRA 策略、COC 策略的所有任务总时长逐渐减小，当R=5 时，上述3 种策略性能基本相同。这是因为当边缘服务器与远端云间传输速率较小时，任务卸载至云服务器的时延大于在边缘服务器的执行时延，此时大部分任务将在边缘服务器执行，因此所提策略性能优于RCRA 策略以及COC 策略。随着传输速率增大，任务在云端执行的时延与任务在边缘服务器执行时延越来越接近，因此所提策略与RCRA 策略以及COC 策略的性能差异将越来越小，这也表明所提策略在传输速率较小时可以获得较高的性能增益。此外，LOC 策略任务执行时延没有变化，这是因为任务本地时延与终端自身计算资源有关与边缘服务器，而与云端间的传输速率无关。

图6 边缘服务器与远端云间传输速率对任务执行时延的影响

5 结束语

在多终端、单服务节点以及云服务器组成的集中式移动边缘网络下，针对任务卸载与服务缓存耦合性对任务时延的影响，本文提出了一种服务缓存与资源分配的联合优化策略。首先，在计算、通信以及存储容量约束下，建立服务缓存与资源分配联合优化问题。随后，将原问题进行分解为2 个子问题并通过重构线性化方法、松弛以及凸优化方法对其进行交替迭代优化。仿真结果表明，与RCRA 策略、LOC 策略和COC 策略相比，所提策略可以有效地降低系统时延并具有良好的收敛性。