移动边缘计算中带有缓存机制的任务卸载策略

郭 煜

(广东国防科技技师学院 广东 广州 510515)

0 引 言

当前，随着无线通信技术和物联网技术的迅速发展，越来越多的移动设备(如智能手机、穿戴设备)对于带宽与计算能力有了更多的无线网络访问需求。未来的移动设备将变得更加智能，而部署于移动设备上的应用将需要更多的计算能力和数据访问[1]。然而，这些新型应用和服务的部署受到移动设备有限计算能力和电池容量的限制。虽然将数据饥饿型和计算密集型任务卸载至云端执行可以克服移动设备计算能力受限的弊端，但移动设备与云端间的无线网络连接带来的较长延时会导致延时敏感型应用的执行无法达到用户的满意[2]。

近年来，移动边缘计算通过将计算节点部署于网络边缘的方式为用户满足延时敏感型任务的需求提供了低延时和高性能计算的保证[3,4]。边缘云具备的优势在于：1)比较移动设备的本地计算[5]，移动边缘计算克服了移动设备的计算能力受限的不足；2)比较远程云端计算[6]，尽管边缘云部署范围较小，且资源能力受限制，但可避免任务卸载至远程云端的高延时问题。因此，移动边缘计算可以在延时敏感和计算密集型任务的执行上得到更好的平衡。

当前移动边缘计算中的卸载问题主要包括：页面卸载，即边缘缓存，页面提供者将常用页面缓存于边缘云上，以降低用户请求页面时的延时和能耗[7-8]。相关研究中已有考虑页面分布[9]和用户移动性[10]的缓存策略。任务卸载，该问题即是决定何时、何地、多少任务应从移动设备卸载至边缘上执行，以降低计算延时和节省能耗。该类研究中主要集中于考虑多用户环境[11]和多服务器环境[12]下的卸载决策问题。页面卸载主要关心边缘云的存储能力，不同步考虑计算能力。而在任务卸载的相关研究中，是以边缘云具有足够的软硬件资源支持任务计算为常态假设的，这与边缘云资源受限以及无法支持所有类型的任务是相违背的。

本文将设计更加实际且注重能效的移动边缘计算卸载策略。首先引入任务缓存的概念，即将多次请求的任务及相关数据缓存于边缘云的操作。由于任务同时需要存储与计算资源，任务缓存需要同时考虑边缘云的计算和存储能力。在此基础上，设计基于边缘云的任务缓存与卸载联合优化策略，目的是通过最优的任务缓存与卸载决策，实现满足用户延时需求的情况下最小化移动设备总能耗达到最小。

1 系统模型

系统目标是在满足用户延时需求的同时最小化移动设备的总体能耗，系统模型如图1所示。

图1 系统模型

移动设备拥有五个计算任务，每个任务拥有不同的请求次数(即任务分布不同)、数据量以及计算能力需求。以虚拟现实应用为例，其场景渲染任务拥有更多分布，会重复多次执行，而追踪目标任务则拥有更大的数据量，需要更多的数据传输，而目标识别任务则需要更高性能的计算资源。通过任务缓存和卸载可以在满足用户延时需求的同时降低移动设备的能耗。对于在考虑任务异构和边缘云资源受限的情况下实现最优的任务缓存和卸载，重点需要解决：1) 哪些任务需要缓存，即决定是否任务需要缓存于边缘云上；2) 多少任务需要卸载，即决定多少任务在本地执行，多少任务在边缘云上执行。

1.1 场景描述

移动边缘计算场景由多个移动设备和一个边缘云组成，假设移动设备(用户)数量为N，计算任务数量为K，用户n={1,2,…,N},任务k={1,2,…,K}，且假设用户数量大于任务数量，即N≥K，这是由于某些计算任务具有更高的分布，使得这些任务需要重复请求并多次执行。假设任意用户一次仅能进行一个任务请求，且不同用户可根据其偏好进行同一任务的请求。定义un,k表示用户n请求任务k，移动设备通过无线信道与边缘云连接，边缘云为拥有计算和存储资源的小规模数据中心，计算资源为移动设备提供任务处理资源，存储资源为任务代码处理提供存储资源。

对于异质计算任务，利用三元组定义计算任务模型，将用户un,k定义为un,k={wk,sk,Dn}，wk表示任务un,k请求的计算资源数量，以每bit的CPU周期数表示，即完成该任务需要的CPU周期总数，sk表示任务un,k的数据量，单位为bit，Dn表示用户n的任务完成截止时间。由于边缘云计算和存储能力受限，假设边缘云的缓存大小和计算能力分别为ce和cs。

1.2 通信模型

令Hn表示用户n与边缘云间的信道增益，假设用户在将任务卸载至边缘云时不发生移动，则为常量。令Pn表示用户n的移动设备的发送功率，则用户n的上传数据速率可定义为：

(1)

式中：σ2表示噪声功耗，B表示移动设备与边缘云间的无线信道带宽。本文不考虑边缘云处理后的数据下载延时，由于处理后的数据量通常远小于任务处理前的数据量，且边缘云至移动设备的下载速率是远高于移动设备至边缘云的上传速率的。

1.3 计算模型

1) 本地任务计算的延时和能耗代价。

对于本地任务计算，定义fln为移动用户n的CPU计算能力，则任务un,k的本地执行时间为：

(2)

单个CPU计算周期的能耗可表示为：ε=κf2，则在本地执行时的能耗代价为：

(3)

式中：κ表示能量因子，大小取决于CPU芯片工艺，本文在实验中将该值设置为10-25。

2) 边缘云计算的延时和能耗代价。

对于边缘云上的任务计算，定义fcn为分配给用户n的CPU计算能力，此时任务执行延时包括：(1) 移动用户卸载任务的时间，即任务上传时间Ttran,k；(2) 边缘云执行任务的时间，即任务处理时间Tpron,k。因此，任务un,k在边缘云上的处理延时为：

(4)

若任务卸载至边缘云，移动设备的能耗仅为任务卸载时间通信能耗，因此，发送skbit的任务至边缘云时的传输能耗代价为：

(5)

1.4 任务缓存模型

1.5 问题形式化

对于任务缓存问题，定义一个整型缓存决策变量xk∈{0,1}，表示任务k是否在边缘云缓存，若是，xk=1；否则，xk=0。因此，任务缓存策略可表示为：x=(x1,x2,…,xk)。对于任务卸载问题，定义卸载决策变量an∈[0,1]，若an=1，则用户n任务在本地执行，若an=0，则用户n任务卸载至边缘云执行，若an∈(0,1)，则用户n的任务部分an在本地执行，任务部分1-an在边缘云执行。因此，任务卸载策略可表示为：a=(a1,a2,…,an)。

基于以上定义，考虑任务缓存、任务的本地和边缘云执行，用户n任务kun,k的总执行延时为：

(6)

移动设备的能耗代价为：

(7)

算法目标是在确保服务质量的同时最小化移动设备的能耗代价，则问题可形式化为：

C3:Tn,k≤Dn∀n∈N,k∈K

C4:xk∈{0,1} ∀k∈K

C5:an∈[0,1] ∀n∈N

(8)

式中：目标函数表明通过任务的缓存与卸载决策对移动设备的总能耗代价最小化，约束C1表明缓存任务的数据量不能大于边缘云的缓存能力，约束C2表明卸载任务的总的资源请求不能大于边缘云的计算能力，约束C3表明用户n的任务执行需在截止时间前完成，约束C4表明任务缓存决策变量为二进制变量，约束C5表明任务是可分割的，可部分在本地执行，部分在边缘云上执行。

2 能效任务缓存与卸载

本节求解以上的任务缓存与卸载决策最优化问题，考虑两个子优化问题：1) 任务卸载问题：当给定任务缓存策略，即x=x0时，初始问题可转变为关于a的凸最优化问题，可以通过内点法获得最优解a*。2) 任务缓存问题：当a*固定时，该子优化问题可转变为0-1整数规划问题，可利用分支限界法获得问题的最优解。以下将分别证明以上的结论。

1) 能效任务卸载。

定理：给定x=x0，式(8)中关于a的初始最优化问题为凸最优化问题。

证明：给定x=x0，目标函数变为a的函数。由于目标函数中的xkTpron,k与a无关，因此，可定义关于a的目标函数为f(a)，表示为：

(9)

进一步，式(8)关于a的最优化问题可重写为：

C2:Tn,k≤Dn∀n∈N,k∈K

C3:an∈[0,1] ∀n∈N

(10)

其中，目标函数表示给定任务缓存策略时通过制定最优任务卸载决策得到能耗的最小化，约束C1表明卸载任务的总的资源请求不能大于边缘云的计算能力，约束C2表明用户n的任务执行需在截止时间内完成，约束C3表明任务是可分割的，可部分在本地执行，部分在边缘云上执行，an本身是任务在本地执行的比例。

由于目标函数是线性的，且约束条件也均是线性的，故该最优化问题为凸最优化问题。证毕。

凸最优化问题即可利用内点法得到最优任务卸载策略a*，即通过求解一系列KKT条件的修改形式，在等式约束下得到最优解，求解方法可具体参见文献[13]。

2) 能效任务缓存。

根据以上的讨论，可能得到最优任务卸载策略a*。当a=a*时，目标函数可转变为x的函数，可表示为：

(11)

进一步，式(8)关于x的最优化问题可表示为：

C2:Tn,k≤Dn∀n∈N,k∈K

C3:xk∈{0,1} ∀k∈K

(12)

其中，目标函数表示给定任务缓存卸载策略时通过制定最优任务缓存决策得到能耗的最小化，约束C1表明卸载任务的总的资源请求不能大于边缘云的计算能力，约束C2表明用户n的任务执行需在截止时间内完成，约束C3表明任务缓存决策变量为二进制变量，只有任务缓存或不进行缓存两种选择。

因此，目标函数可转变为关于x的0-1线性规划问题，利用分支限界法即可得到其最优解，具体过程如下：

(1) 分支步骤。该步骤中，计算任务集合被转换为一棵树，代表所有任务在本地或需要缓存的可能性组合。该树由空节点的树根开始构建，对于该父节点，每个任务的副本被连接为孩子节点，每个孩子节点代表在本地执行或云端缓存(标记为local或云端服务器编号)。类似地，下一任务节点的副本与树结构的每一层上与孩子节点相连。重复以上过程直到所有任务被添加至树结构中，该树的每条分支即代表一个侯选的任务缓存决策解。

为了减少决策时间，将节点添加至树结构中时，需要根据任务的能耗代价降序进行添加，这样得到的树中主分支将拥有更高的代价，这将使得分支步骤中可以提前遍历对代价影响更大的节点，从而尽可能早地发现不可行的高代价分支，有利于修剪分支状态，降低决策空间的搜索时间。

(2) 搜索步骤。该步骤由搜索分支步骤构建的树、计算每条分支的代价和寻找最小代价分支组成。为了加快决策时间，搜索过程利用一个限界函数修剪树结构中的某些非最优的分支。每条分支利用深度优先规则DFS计算其代价。同时，若分支的局部代价超过限界函数定义的限制值则修剪该分支。设计的限界函数以完全的本地执行或云端执行得到的能耗代价进行初始化。若一个分支被完整搜索而未被修剪，则将其考虑为当前的最优解，且其代价作为新的限界函数值。当所有分支被搜索后，算法返回最优解。

3 仿真实验

3.1 实验配置

考虑一个由边缘云和移动设备组成的移动边缘计算系统，移动设备拥有计算密集型任务和数据密集型任务执行需求，假设边缘云部署于无线访问点AP的附近，移动设备可通过无线信道将任务卸载至边缘云执行。假设无线信道带宽B=20 MHz，移动设备的发送功率Pn=0.5 W，对应的噪声功耗σ2=2×10-13，无线信道增益Hn=127+30×logd，d表示用户n与边缘云间的距离。对于任务un,k，假设请求的计算能力wk和数据量sk由概率分布产生，分别服从正态分布和均匀分布。对于任务的分布，假设任务请求次数服从Zipf分布，同时，设置边缘云和移动设备的计算能力分别为25 GHz和1 GHz。其他相关参数中，n=100，ce=500 MB，w服从均值为0.8(单个任务的CPU周期数)的均匀分布，s服从均值为100 MB的均匀分布。利用MATLAB进行实验的验证分析。

3.2 结果分析

1) 任务卸载影响 将本文提出的基于能效的任务缓存与卸载算法命名为TCO算法，并与以下算法进行性能比较：

缓存+本地执行算法，简称CLA。该算法根据本文提出的缓存策略对计算任务进行缓存，然后，未被缓存的任务仅在本地设备上执行，不被卸载至边缘云处理。

缓存+边缘云执行算法，简称CEA。与CLA不同，该算法中未缓存的任务全部卸载至边缘云处理。

从图2看出，TCO算法得到的能耗最低，说明应用最优的缓存部署和任务卸载可以有效降低移动设备的能耗。图2(a)中，当任务数据量较小时，TCO和CEA的能耗差异较小，而任务数据量较大时，TCO和CLA的能耗差异较小。可以得出，在相同的任务计算能力请求下，当任务数据量较小时，任务应在边缘云上处理更为有效。比较来说，若任务数据量较大，则任务应在本地执行较好。从图2(b)可以得出，在相同的任务数据量下，当任务计算能力请求相对较小时，任务应在本地执行较好，而计算能力请求较大时，则在边缘云执行较优。

(a)任务数据量变化

(b) 任务请求计算能力变化图2 任务卸载的影响

2) 任务缓存影响 观察两种情况下的能耗状况：任务不被缓存和任务缓存，如图3所示。当任务被缓存时，移动设备的能耗低于不缓存时的能耗，说明计算任务缓存可以降低能耗。还可以看出，任务数据量越大，计算能力请求越高，能耗将越高。

(a) 任务数据量变化

(b) 任务请求计算能力变化图3 任务缓存影响

为了评估缓存策略对结果的影响，将TCO与以下算法进行比较：

任务尽力缓存与卸载算法，简称TPO。对于边缘云，它将最大限度地缓存计算任务直到达到边缘云的缓存能力。

任务随机缓存与卸载算法，简称TRO。边缘云随机地进行任务缓存，直到达到边缘云的缓存能力。

任务有限缓存与卸载算法，简称TFO。边缘云的缓存能力初始设置为空，迭代式增加一个任务至缓存以最小化总能耗，直到达到边缘云的缓存能力。

由图4可知，TCO是最优的，TRO相对较差，这是由于随机缓存策略没有考虑任务请求数量的原因导致，且该算法在进行任务缓存时也无法考虑任务计算量和计算任务的数据量。TPO仅考虑了任务请求数量，没有考虑任务数据量和任务计算量，TFO在一定程度上考虑了以上三个量。从图4(a)还可以看到，边缘云的缓存能力越大，能耗将越小，这是由于缓存能力越大，缓存任务越多，能耗将降低。从图4(b)和(c)可以看出，任务数据量对算法的影响要弱于计算能力对算法的影响。

(a) 边缘云缓存大小变化

(b) 任务数据量变化

(c) 任务请求计算能力变化图4 任务缓存的影响

4 结 语

移动边缘计算环境中，延时敏感型应用任务的执行不仅需要满足用户时延的约束，还需要考虑移动设备端的能耗问题。为了解决这一问题，基于移动边缘计算环境提出了一种融入任务缓存机制的任务卸载策略。不同于常规的边缘计算仅仅关注计算卸载决策问题，该策略设计了一种基于边缘云的任务缓存机制，降低了重复的任务需求执行时的卸载延时。此外，策略将计算与存储能力受限的边缘云中的任务缓存与卸载优化决策问题形式化为混合整数规划问题，并对其进行了求解。实验结果证明，带有缓存机制的任务卸载策略在动态异构的任务执行环境下可以实现更好的能效优化。进一步的研究将集中于面向多个边缘云的任务卸载环境，在任务缓存与卸载的边缘云资源的选择上作出优化。