面向移动边缘计算中多应用服务的虚拟机部署算法

李光辉 周 辉 胡世红

(江南大学人工智能与计算机学院 无锡 214122)

1 引言

近年来，5G技术和物联网技术快速发展，移动设备(如智能手机和可穿戴设备等)的数量急剧增长。各种应用服务的爆炸性激增对计算能力和实时处理提出了严格的要求。受限于计算资源和能源供给[1]的移动设备已经无法应对这一挑战。移动边缘计算[2](Mobile Edge Computing, MEC)作为一种有潜力的新兴计算范式，可通过在用户附近部署计算和存储等资源来提高服务质量[3]。AR和视频游戏等实时交互应用的增多导致移动边缘网络中的数据流量迅速增长，造成严重的网络资源消耗，使用户访问应用服务时延迟增加。因此，为了更好地控制网络时延并减少潜在的核心网堵塞，必须减少边缘网络的数据流量。一个有效的解决方案是在边缘网络中部署支持多种应用服务的虚拟机(Virtual Machine, VM)为移动用户提供各种近端服务[4]，依靠高带宽和脱机可用性来缓解核心网络的拥塞，同时通过满足延迟和能耗等关键应用需求进一步提高计算服务质量。

VM是一个逻辑容器，可使用数据运行软件实例。在MEC中使用VM技术，能使MEC服务器成为特定应用的应用服务器，即特定的应用请求只能由部署有相关应用VM的MEC服务器提供服务。目前，已有许多关于MEC中VM管理问题的研究。由于用户的移动性，MEC系统需要在用户位置随时间变化时进行服务迁移，文献[5]提出了一种代理VM迁移方案，采用基站与雾节点在本地提供计算资源的方式来为用户提供服务。为了减少服务迁移过程中出现的性能下降问题，文献[6]提出了一种自适应VM切换方法来减少用户移动时进行服务迁移需要传输的数据量。考虑到用户多种服务需求，文献[7]提出3种启发式算法寻找VRC最优部署位置来最小化平均请求响应时间。此外，文献[8]设计了一种VM容错部署机制来针对可能出现的边缘服务器故障问题。然而，很少有研究考虑边缘网络中关于数据流量的绿色通信问题。

尽管现有工作对MEC中边缘网络的资源配置问题提出了很多解决方案，但存在一个共同的局限性：没有具体考虑用户对多种应用服务的需求。在边缘网络中提供多种应用服务将面临许多挑战，如不同应用对传输带宽的需求差异会导致不同的平均链路时延，所需服务资源的多样性会导致边缘服务器不同的工作负载等。文献[9]采用云边资源协作的方式为用户提供服务，提出一种云边协同模式下的任务分配机制将应用负载分配给合适的微云(Cloudlet)来最小化用户响应时延。文献[10]通过图分割的方式将实际的物理网络抽象为一个完全图，用服务器之间的通信时延表示边缘网络中的费用，提出一种数据访问延迟最小化的虚拟机部署最优近似算法。然而他们没有考虑为用户提供多种不同特性的应用服务。文献[11]设计了一种有效的任务调度和资源管理策略最小化任务完成时间，文中提到可以支持多种应用类型，但是没有明确指出支持的不同应用之间的区别。多数工作在部署边缘网络中的资源提供服务时，没有详细考虑提供多种应用的差异性[12]，而是集中于研究边缘服务器和移动用户之间的交互及协作[13,14]，他们简单地假设所有移动用户的资源需求是统一的[15]，而实际情况中，必须考虑不同应用对资源的需求差异，这些将显著影响最优路由选择和工作负载分配。

因此，本文以最小化移动边缘网络中云边数据流量和最小化服务配置总成本为目标，构建了一种云边协同的计算架构，在此架构基础上对支持多种应用服务的虚拟机部署问题进行研究，在边缘服务器服务能力一定且提供多种应用服务前提下，将问题形式化描述为资源约束下的最小化云边数据流量和部署总成本的优化问题。本文主要工作如下：

(1) 基于MEC架构，本文首次研究了在提供多种应用服务的边缘网络中，将每种应用的k个VM部署到|S|个边缘服务器上，以最小化边缘网络中的平均数据流量(Minimizing the Average Data Traffic, MADT)为目标。

(2) 针对上述问题，本文首先从网络拓扑结构特性出发，计算每个边缘服务器的中心性特征，根据定义的适应度模型，提出了一种基于适应度的启发式部署算法(Fitness-based Heuristic Placement Algorithm, FHPA)。另外，从用户对不同应用服务需求差异化考虑，定义适应度模型，通过子问题划分策略，设计了一种基于分治的启发式部署算法

(Divide-and-Conquer Based Heuristic Placement Algorithm, DCBHPA)。

(3) 仿真结果表明，相比于基准算法和FHPA，DCBHPA能最大限度地减少数据流量，有效地缓解远端云的流量压力，减少潜在的核心网拥塞。同时，对边缘网络中提供服务的配置总成本问题进行了研究。

2 系统模型

2.1 移动边缘计算架构

基于MEC的系统框架如图1所示，该框架由移动设备、MEC服务器组成的边缘网络和远端云中心构成，其中，边缘网络采用的是MEC服务器与基站共同部署在无线接入网内的结构。各种资源密集型和时间敏感型的移动应用源服务器，例如a1,a2,a3，运行在远端云计算中心，同时在边缘端，边缘服务器 M ECS1和M ECS3分别部署有应用a1的 VM，可充当应用a1的应用服务器(Application Server, AS)，为移动用户提供特定的服务请求。

图1 提供多种应用服务的移动边缘计算架构

所有来自用户的请求首先由本地边缘服务器进行处理，每个边缘服务器会根据当前边缘网络的资源利用情况为服务请求做出最优路由抉择，确保其从边缘网络相应AS或远端云中心获取服务。例如，M ECS2服 务范围内的移动用户对应用a1的请求将被路由到部署有应用a1相 应VM的M ECS1，由服务器M ECS1提供服务。同时对每个边缘服务器的服务容量进行约束，当网络中AS的服务资源耗尽时，如 M ECS1和M ECS3全部过载，新接收的应用a1的请求由云中心提供服务。

2.2 网络模型

3 问题描述

3.1 平均数据流量最小化问题

移动用户的服务请求在云边协同的MEC架构获取服务产生的数据流量包括：(1)由边缘网络中的AS为移动设备提供服务的边缘流量；(2)远端云提供服务产生的云边通信流量。将边缘网络中任意两台边缘服务器间的最短路径作为二者间的路由选择，使用变量dv,u表示边缘服务器v到u的最短路径跳数，则MEC服务器v服务区域内的用户请求路由到MEC服务器u获取对应用a请求服务的数据流量定义为

3.2 应用服务配置总成本问题

配置总成本由VM部署成本和请求服务的数据流量成本构成。将相同应用相应VM间的状态同步和部署VM到边缘服务器的资源需求作为部署成本，定义为所有应用种类数和支持每种应用VM数的2次函数，即ε·k·|A|， 其中0＜ε ＜1。数据流量成本体现了边缘网络的拥堵情况，可由所取得的边缘端流量De和 云端流量Dc的线性函数表示，分别为σ1·De和σ2·Dc，其中σ1,σ2＞0。对部署成本和数据流量成本经过标准化函数f,N计算后，定义整个系统的服务配置总成本为

4 算法设计

4.1 基于适应度的启发式部署算法

为了解决MADT问题，本文提出一种基于适应度的启发式部署算法。对于应用a，FHPA寻找k个适应度最高的MEC服务器部署应用虚拟机，其中每个MEC服务器的适应度评价由4种网络连接特征构成，包括接近中心性(closeness centrality)、度中心性(degree dentrality)、中介中心性(betweenness centrality)和特征向量中心性(eigenvector centrality)，再根据熵权法对每个连接特征的权重进行计算。下面首先介绍上述连接特征的概念。

(1)度中心性。度中心性的基本思想是网络中重要节点为与其他节点的连接边数较多的节点。相应地，MEC服务器s的度中心性为与他直接相连的MEC服务器个数，归一化后服务器s的度中心性计算表达式为

对于应用a∈A，基于每个MEC服务器的适应度降序排序结果，选择前k个服务器为应用a的初始AS，分别分配到集合Xi,i=1,2,...,k，结合文献[17]，设计一个聚类机制如表1，轮询地将全部候选MEC服务器划分到与其最近的初始AS所在集合Xi。对集合Xi中的每一个MEC服务器，将其作为该集合中应用a的AS为集合中其他边缘服务器服务范围内的应用请求提供服务，并计算所产生的数据流量，最后选择能最小化该集合中平均数据流量的MEC服务器，部署应用VM。FHPA通过将MADT问题划分为k个子问题，在每个子问题中寻找应用服务a的一个VM最优部署位置，然后通过整合子问题的最优解求解原问题，FHPA详情如表2所示。

表1 聚类过程

表2 基于适应度的启发式部署算法

4.2 基于分治的启发式部署算法

由于应用请求在本地MEC服务器进行处理将不会注入流量到边缘网络，因此，选择覆盖范围内应用请求数较大的MEC服务器作为AS，可以减少产生到边缘网络的流量。然而，由于AS容量受限，这样会导致该AS附近的边缘服务器的应用请求发送到云端的比例将上升，进而增加系统流量成本。因此，本节进一步提出一种基于分治的启发式部署算法，与文献[18]只考虑用户请求密度不同，DCBHPA将当前已配置应用a相应VM的边缘服务器对网络中其他将部署同应用服务VM的候选MEC服务器的影响进行了考虑，从而避免应用a的AS集中在网络某一局部地区，提高服务资源的利用率。

变量Q表示已部署应用a相应VM的MEC服务器集，与当前已部署的AS越远，则候选MEC服务器所受影响越小，设当前已部署的ASj对候选MEC服务器i ∈S的影响因子为θ·t(i,j)，其中0＜θ ＜1,t(i,j)为i和j归一化后的距离。每个候选MEC服务器将受到当前所有已部署AS的影响，影响因子为

在每次迭代中，DCBHPA选择P值更高的MEC服务器作为初始AS，k次迭代更新后，选择k个初始AS加入集合Xi,i=1,2,...,k进行初始化，之后的求解MADT过程同FHPA，DCBHPA详情见表3。

表3 基于分治的启发式部署算法

4.3 算法分析

FHPA是一个简单有效的算法。它首先计算每个MEC服务器的连接特征。其中，每个MEC服务器的接近中心性表明它与边缘网络中其余MEC服务器的平均距离。度中心性越高，则该MEC服务器能在相同的距离内与更多的MEC服务器相连，距离越短则服务请求产生的数据流量越小。因此具有更高度中心性的MEC服务器更适合部署应用虚拟机。当网络中所有移动设备的应用服务请求路由到相应的应用服务器时，通过每个MEC服务器的路径个数能显示该MEC服务器上需传输数据的到达速率，边缘网络中路由路径数越多经过该MEC服务器，表明该MEC服务器节点拥堵程度越高，则请求数据在该服务器节点的等待时间将很长，这一特性通过中介中心性表现出来。为了避免在网络中影响程度较低的MEC服务器成为应用服务器，将每个MEC服务器的特征向量中心性考虑进来。因此，基于归一化的连接特征值，计算每个MEC服务器上的所有连接特征的权重之和，得出每个MEC服务器部署应用虚拟机的适应度。最后FHPA选择适应度最高的k个MEC服务器部署应用虚拟机。

然而，FHPA也存在两个缺点。第1个缺点是选择虚拟机部署的MEC服务器时，没有考虑用户的请求数。来自用户的服务请求由本地边缘服务器处理将不会注入流量到边缘网络，从而选择覆盖范围内有大量应用请求的MEC服务器部署应用虚拟机，并将其作为AS可以减少网络的流量负载。因此，边缘服务器范围内移动用户的服务请求数也是影响其部署应用虚拟机成为AS的重要因素。然而，FHPA从网络拓扑结构的连接特征出发来确定应用虚拟机部署位置，没有利用移动用户请求数来提升部署效益。第2个缺点是当大量用户集中在边缘网络同一局部地区时，FHPA容易造成部分AS过载。因此，本文从用户请求角度出发进一步提出DCBHPA算法求解MADT问题。

DCBHPA考虑了当前已部署应用虚拟机的边缘服务器对边缘网络中其余候选MEC服务器的影响因素。第1个是每个MEC服务器与当前已部署虚拟机的MEC服务器间的平均距离，为了避免应用服务器集中部署在边缘网络的某一局部地区，候选MEC服务器与当前已部署应用虚拟机的MEC服务器距离越远越合适。第2个是在当前已部署的应用服务器提供服务的情况下，每个边缘服务器接收的应用请求数量。为了减少边缘网络中的平均数据流量，接收应用请求数量更多的MEC服务器更适合部署应用虚拟机作为下一个AS。DCBHPA在每次迭代中选择适应度最高的MEC服务器来部署应用虚拟机，对于应用a∈A， 在k次迭代后，获得k个最适合部署关于应用a相应虚拟机的边缘服务器。因此，DCBHPA在共经过k·|A|次迭代后，完成所有应用的虚拟机部署。

5 仿真分析

本文利用Python工具完成了仿真实验。不失一般性，从Topology Zoo获得真实的在线网络拓扑用于VM部署实验[19]，网络拓扑图结构如表4所示。不同应用服务的网络带宽需求设置为[800 kB,1600 kB]，并假定分布在整个边缘网络的移动用户数在500～3000。默认设置3种应用以及每种应用部署4个VM和noel通信网络进行实验。同时，选择文献[20]中的RPA算法和文献[21]中的DBC算法进行性能比较。

表4 网络拓扑表

5.1 网络数据流量

如图2所示，各算法产生的平均数据流量随着支持每种应用的VM数增加而单调减少。这是因为随着边缘网络中支持同一应用服务的VM数增多，即该应用的AS数量增加，可以在本地进行更多的请求处理，从而减少注入到边缘网络中的数据流量。同时，配置更多的VM可以减少边缘网络中移动用户与请求的目的AS之间的平均距离，导致边缘网络更小的数据流量产生。从图2可以发现，DCBHPA在最小化平均数据流量方面相比其他算法可以获得最优性能，FHPA性能表现要优于DBC，且二者都优于RPA。

图2 不同VM数对数据流量的影响

从图3可以清楚地发现，在相同数量的移动用户情况下，与FHPA, DBC和RPA相比，DCBHPA总是可以获得最小的平均数据流量。此外，在移动用户数较小的情况下，各算法性能差异较小，随着用户数不断增加，所有4种算法提供服务产生的平均数据流量都会增加，其中RPA数据流量增加最为明显。当移动用户数为3000时，DCBHPA相比RPA可以减少25.8%的流量生成，反映了DCBHPA在大规模移动边缘网络中为移动用户提供多种应用服务进行VM配置的优势。

图3 移动用户数对数据流量的影响

图4为不同网络拓扑下FHPA, DCBHPA,DBC和RPA在边缘网络中最小化请求数据流量方面的性能比较结果，可以看到4种算法提出的服务配置方案产生的数据流量会随着网络规模的扩大而上升。在同一网络下，DCBHPA在减小平均数据流量方面能获得最佳性能表现。同时，图5进一步比较了FHPA, DCBHPA, DBC和RPA在应用服务类型不断增多情况下的性能。实验结果表明，DCBHPA要优于其他3种算法。与此同时，随着不同应用种类的增加，各算法进行VM配置提供服务所产生的数据流量都会增长，且DCBHPA与FHPA, DBC和RPA的性能差异也更加明显。此外，FHPA和DBC的性能表现基本相近，且二者都要优于RPA。

图4 网络规模对数据流量的影响

图5 应用服务种类数对数据流量的影响

接着，在支持每种应用服务的VM数量不同且应用服务种数不断增加的前提下，进一步分析了DCBHPA的性能表现。仿真结果如图6所示，当应用服务数量增加时，对于支持各应用服务的每组VM设置，DCBHPA获得的平均数据流量呈指数增加。这是因为更多的应用服务种类意味着边缘网络中将有更多的应用请求需要提供服务，而这将导致AS可用服务资源的短缺，进而增加系统的数据流量产生。同时，更多的服务请求将发送到云端获得服务从而增加流量成本。从图6可以看出，当应用服务种类一定时，随着支持每种应用服务的VM增加，系统的平均数据流量将越少，这与图2的实验结果相符。

图6 不同应用服务下VM部署取得的数据流量

5.2 服务配置总成本

一个好的部署方案不仅要保证较低的平均数据流量，而且要考虑边缘网络中提供服务配置的成本因素，因此，我们进一步分析了DCBHPA提供服务时的总成本。如图7所示，同一应用提供更多的VM部署到边缘网络将减少流量成本，同时增加部署成本。通过将归一化后的流量成本和部署成本相加，可以得到服务提供总成本。从图中可以发现，当VM部署数量不超过3时，总成本随着VM配置数量的增加而下降，这是因为当VM的数量很小时，主导服务配置总成本的是数据流量成本，如图2所述，因此总成本将随着支持每种应用服务的VM数量的增加而减少。当部署VM的数量继续增加时，VM的配置成本就会逐渐占据服务配置总成本的主导地位，导致当支持每种应用服务的VM数量超过3时，DCBHPA提供服务配置的总成本会随着VM数的增加而增长。

图7 不同VM数对归一化服务配置总成本的影响

如图8所示，在应用服务种类不断增加且支持每种应用服务的VM数为4的情况下，对4种算法在应用服务部署成本方面的性能进行了比较。图8表明，在最小化部署总成本方面，DCBHPA可以获得最佳性能表现，且FHPA要优于DBC，同时二者都要强于RPA。根据定义，VM部署成本为支持每种应用的VM数和不同应用种类数的2次函数，因此部署成本将会随着应用数的增加而上升。图5表明所有算法产生的数据流量会随着应用种类数的扩展而显著增加，因此数据流量成本将随着算法产生的数据流量增加而线性增长，所以服务配置总成本将随着应用种类数的增加而上升，这与图8的结果一致。

图8 应用服务种类数对归一化服务配置总成本的影响

6 结束语

本文研究了移动边缘网络中支持多种应用服务的VM部署问题，在提供多种应用服务请求和MEC服务器处理能力受限约束下，为了最小化移动边缘网络中的平均数据流量这一目标，提出了两种启发式的部署算法，并利用广泛的仿真实验来评估所提算法的性能。实验结果表明，DCBHPA算法性能在最大限度地减少平均数据流量方面，要优于FHPA算法和基准算法，能有效减少云边通信流量，缓解潜在的网络堵塞问题。未来工作中，将进一步深入研究多应用服务下不同VM部署方案对用户所需服务的平均请求响应时间的影响规律。