基于边缘云和移动辅助设备的计算卸载优化方案

方加娟 李 凯

1(郑州职业技术学院软件工程系 河南 郑州 450121)2(南京理工大学计算机科学与工程学院 江苏 南京 210094)

0 引 言

近年来，全球移动设备的数量急剧增加，随着移动设备的普及，覆盖不同领域的新的应用程序如人脸识别、增强现实、自然语言处理和交互式游戏相继出现。这些应用具有密集的计算需求。为了满足现实计算需求，移动边缘计算(Mobile Edge Computing，MEC)的概念被研究人员提了出来[1-2]。

移动边缘计算[3]是指将移动网络与互联网有效地结合，利用在移动网络边缘部署的计算、存储和处理功能，为用户提供高带宽和超低时延的网络服务解决方案。计算卸载[4]作为 MEC 架构中的一项关键技术，是指终端设备将部分或全部计算任务交给云计算环境处理的技术。基于MEC的计算卸载技术可以提高移动设备的性能，通过节省移动设备的能耗来延长设备的工作时间。

尽管计算卸载技术可以很好地提高移动设备端的能力，但仍存在诸多问题，计算卸载效率问题是其中之一。在具有大量计算密集型任务的CUE的延迟敏感系统中，当多个移动用户同步通过无线信道进行计算卸载时，设备之间势必会出现相互干扰，从而降低数据传输速率，导致数据传输时间的延长。因此，在计算资源有限的情况下，将所有CUE的任务卸载到云端并不总是明智的[5]。如今，随着移动设备的性能稳步提高，许多移动设备并没有充分利用它们的处理器，因此将任务卸载到这些临近闲置移动设备是一个诱人的选择。为了平衡功耗与服务响应时间，移动设备需要合理选择卸载至云端和移动终端处理的应用部分。柳兴等[6]通过遗传算法来搜索移动终端和云端计算资源联合执行应用的全局最优解，主要研究了迁移任务的选择问题。张文柱等[7]从移动终端硬件出发，在能耗方面进行了优化处理。曹傧等[8]提出一种利用临近闲置移动终端作为卸载目标的分布式博弈算法，给出一种最优结果。Ti等[9]给出了一种在移动用户、移动对等点设备和云端之间进行联合计算卸载的非中心式博弈算法，通过多用户的设置制定了资源分配的优化方案，有效提高了计算卸载效率问题。

为了尽可能缩短CUE任务的完成时间，本文在文献[9]研究的基础上做进一步的探索，主要考虑以下几点：识别具有空闲计算资源的辅助用户设备HUE；决策对等点和云端之间的计算卸载平衡；云计算资源的分配问题。由于HUE不需要消耗它们有限的能量来为其他人计算，引入了带宽激励的概念，探讨交换带宽计算活动的好处。

1 移动边缘计算

MEC是由欧洲电信标准协会ETSI提出的基于5G 演进架构的一项新技术。移动边缘计算借助边缘计算中心在无线接入网(RAN)内提供IT服务环境、云计算和存储功能，其目标是减少网络延迟，确保高效的网络运营和服务交付，并提高用户体验。

1.1 MEC基本架构

移动边缘计算的关键要素是集成在RAN元素上的移动边缘计算IT应用服务器。MEC的基本框架如图1所示，该框架从一个比较宏观的层次出发，对MEC架构下不同的功能实体进行了网络层、移动边缘主机层和移动边缘系统层的划分。其中MEC主机层包含主机(ME host)和相应的主机层管理实体(ME host-level management entity)，ME主机又可以进一步划分为ME平台(ME platform)、ME应用(ME application)和虚拟化基础设施(Virtualization Infrastructure)。网络层主要包含3GPP蜂窝网络、本地网络和外部网络等相关的外部实体，该层主要表示MEC工作系统与局域网、蜂窝移动网或者外部网络的接入情况。最上层是 ME系统层的管理实体，负责承载应用程序及MEC系统的全局掌控。

图1 MEC架构示意图

1.2 MEC计算卸载技术

MEC计算卸载技术不仅解决了移动设备在计算性能、资源存储和能效方面的不足，还减轻了核心网的压力，降低了因传输带来的时延。计算卸载主要包含资源分配和卸载决策两个方面。资源分配主要研究将资源卸载到哪里的问题；卸载决策则研究的是用户终端如何卸载和卸载内容的问题。图2为计算卸载决策和资源分配示意图。其中：(a)为CUE卸载决策的3种方式，分别是本地执行、完全卸载和部分卸载，具体决策结果可通过CUE能量消耗和完成计算任务时延决定；(b)为计算卸载的资源分配方案，该方案采用MDP 解决了在SCeNB中的虚拟机(Virtual Machine，VM)分配问题。CUE1通过创建VM，将计算任务全部卸载到SCeNB1上。对于CUE2，考虑到从SCeNB1到其他SCeNB的时延问题，CUE2在时延更低的SCeNB3上进行计算卸载。但是，如果考虑VM的迁移成本时，一般会在MEC计算资源充足的情况下，优先选择近距离的MEC中进行卸载。

图2 计算卸载决策和资源分配示意图

2 计算卸载方案

考虑一个与边缘云关联的基站，可以服务N个CUE，每个CUE都有一个计算密集型任务要执行。同时，附近还存在M个带有空闲处理器的HUE。为了激励HUE辅助CUE进行计算卸载，CUE需要分出一部分可用带宽给HUE，因此，假设每个HUE至多可以帮助一个CUE，不考虑用户的移动性和切换的情况下，每个CUE有两个选择：

(1)将其任务卸载到边缘云上，这时CUE的全带宽可用于卸载，因此卸载延迟被最小化，但是对任务应用的计算能力降低。

(2)将部分带宽提供给一个HUE，然后将部分任务卸载到云，另外部分则卸载到该HUE。此时由于只有部分带宽可供卸载导致卸载延迟会增加，但是具备更多的应用计算能力。

2.1 通信模型

每个CUE都具备一定的带宽B(以赫兹为单位)，假设αi,j∈(0,1)是HUEj协助CUEi所需的带宽份额。当CUEi卸载到HUEj和利用基站卸载到边缘云时，CUEi到HUEj和基站的遍历瑞利衰落信道容量分别为：

(1)

(2)

在CUEi所提供的带宽上，HUEj达到了其预期接收器的比特率，其规模增益为gj：

(3)

2.2 计算模型：云-HUE卸载

(4)

(5)

(6)

(7)

(8)

(9)

本文忽略了发送计算结果所花费的时间，因为相对于输入数据，输出数据的大小往往很小。

2.3 计算模型：仅云卸载

假设现在一个CUEk(k∈C,k≠i)只将其任务的一部分卸载到云上。总的完成时间为：

(10)

3 资源分配和解决方案

让π表示所有用户的一个集合分区，其中每个子集都有一个CUE，最多有一个HUE，Π表示所有这些可能分区的集合。例如，当C={1,2}和H={1}时，有三个分区:

Π={{1,1},{2}},{{1},{2,1}},{{1},{2}}

(11)

在每个子集中，第一项和第二项分别是CUE和HUE，假设ρδ和ζδ分别表示δ集合中具有基数1和2的子集，例如δ={{1}，{2，1}}表示CUE1只卸载到云上，而CUE2卸载到云和HUE1上，ρδ={1}，ζδ={2，1}。然后，决定哪个HUE与每个CUE配对，哪个任务共享卸载到配对的HUE和云，以及如何在用户之间划分云资源的问题可以表示为：

(12)

由于αi,j<1，所以

(13)

3.1 HUE固定分配

假定HUE到CUE的分配是固定的，并且优化扩展到任务共享以卸载和用户之间的云资源分区。

3.1.1最佳解决方案

对于给定的HUE分配δ，式(12)可以变为：

(14)

式中：ζδ表示δ集合中基数为2的子集。

(15)

可以获得：

(16)

Tk≤Vk∈ρδ

(17)

本文应用迭代技术来最优求解式(16)，对于迭代t，使用式(17)和式(18)将其中的第一约束转换为单项式：

(18)

式中：λ1(t)、λ2(t)、λ3(t)为：

(19)

同样，对于每次迭代t，第四约束条件可以通过式(17)和式(18)将其转换为单项式：

(20)

式中：γ1(t)、γ2(t)为：

(21)

总而言之，迭代t要解决的整体优化问题是：

(22)

s.t. 式(18) ∀{i,j}∈ζδ

式(20)k∈ρδ

当|V(t)-V(t-1)|<ε，0≤ε<1时迭代终止。

算法1基于GP的固定HUE分配算法

2.while true do

t=t+1;

计算λ1(t)、λ2(t)、λ3(t);

if |V(t)-V(t-1)|≤εthen

Break;

end if

end while

3.1.2次优云资源分配

在式(12)中，云资源的最佳分配取决于HUE分配。制定了一个独立于这些任务的有效的次优分配。为此，考虑每个CUE仅卸载到云的情况，即：

(23)

上述优化问题类似于式(16)，因此可以使用基于GP的算法最佳地求解。通过求解式(23)得到的F′i值就是所寻求的次优分配。

3.2 云资源固定分配

(24)

和

(25)

(26)

式(25)中的第一和第二约束分别随MEC的增加而减小。因此，当两个约束都满足相等条件时，就可以得到卸载到云中的最佳比特数:

(27)

CUEk仅云卸载的完成时间为:

(28)

3.3 HUE最佳分配

式(12)的最优解可以通过搜索3.1.1节中描述的所有可能的HUE分配以及对每个HUE分配的优化来获得。但是，这需要搜索(M+N)!/M!个HUE分配。或者，从3.1.2节和3.2节中导出的用于云资源分配和卸载位数的次优解中，因此HUE分配问题可以简化为：

(29)

并通过一个二分图形匹配算法对其进行优化求解。

(30)

(31)

(32)

式(32)中的HUE选择问题可以表示为所定义的图的瓶颈匹配(Bottleneck Matching，BM)问题，即最大边缘权重尽可能小的最大匹配问题：

(33)

(a)图形网络 (b)带有虚拟顶点的图像 (c)BM输出

4 实验结果与分析

表1 模拟参数

本文主要对比4种不同的卸载方案：

(1)“HUE-云BM”方案，卸载量由式(24)、式(25)给出，HUE分配通过BM算法获得。

(2)“HUE-云BM-GP”，首先获得卸载量和HUE 分配，然后通过算法1求解式(16)，更新卸载量和云资源分配。

(3)“HUE-云 随机选择”，其中卸载量是式(24)、式(25)的解决方案，每个CUE随机分配一个HUE。这个基线的复杂性是Ω(min(N,M))。

(4)“云”，仅卸载到云，这是任务计算的传统选择。

图4-图5为不同策略的完成时间对比，其中云的计算能力在4～20 GHz之间变化，图4中有30个CUE和50个HUE存在网络中，图5则将网络中的CUE和HUE的数量分别增加到70和100。可以发现，卸载到云和HUE的具有极大的优势，即便HUE是随机分配的。算法1对计算结果的提升度很小，简单的“HUE-云BM”方案即可达到理想的结果。

图4 不同卸载方案的完成时间对比(CUE=30)

图5 不同卸载方案的完成时间对比(CUE=70)

在图6中，通过详细检查特定CUE任务的卸载延迟和计算时间，进一步了解不同方案的性能。通过分析不同方案在本地、HUE与云的计算时间和卸载时间发现，计算时间在不同的处理器之间很平衡，并且卸载延迟时间在总时间中所占比例不高。

图6 不同卸载方案的计算时间和卸载延迟对比

5 结 语

本文提出一个将计算卸载到边缘云和移动对等端的通用框架。该设计旨在保持应用程序延迟需求的同时，最大限度地减少总计算时间。数值结果表明，通过带宽激励，将计算卸载到边缘云和移动对等端的方案是可行的。与将计算卸载到边缘云方案相比，该方案具有较大的性能增益，在卸载延迟时间没有明显增加的情况下，总计算时间可以减少35%～40%。