-
摘要:
在这个万物互联的时代,海量的设备和数据、云和设备之间存在巨大的传输延迟,给开发应用、处理数据、最终提升系统的服务质量带来了多重挑战. 因此,通过在终端设备附近部署计算能力以显著减少传输到云服务器的数据量和服务请求的响应时间的边缘计算结构应运而生. 然而,负载均衡、边缘设备的安全性和移动性依旧是影响边缘计算架构的服务质量的关键点. 为了解决上述问题,提出了一种2阶段的服务质量优化方案以解决移动边缘计算架构下的服务部署问题. 在第1阶段,考虑了服务的解耦和边缘服务器的负载均衡问题,对服务部署问题进行建模,提出了一种集中式服务的实时解耦方案,并且设计了一种静态部署策略;在第2阶段,考虑了边缘设备的移动性,设计了一种设备移动感知的服务动态部署策略,优化了移动边缘计算架构下的服务质量. 在2个数据集上的实验结果表明,所提出的静态部署策略能够使服务请求的响应时间降低36%,所提出的动态部署策略能进一步降低13%的服务响应时间.
Abstract:In the era of the Internet of everything, the huge transmission delays between massive devices and data, clouds and devices have brought multiple challenges to developing applications, processing data, and ultimately improving the quality of service(QoS). As a result, edge computing architectures that significantly reduce the amount of data transferred to cloud servers and the response time of service requests by deploying computing power near end devices have emerged. However, load balancing, security, and mobility of edge devices are still the key points that affect the quality of service of edge computing architectures. In order to solve the above problems, we propose a two-stage QoS optimization scheme to solve the service deployment problem under the mobile edge computing architecture. In the first stage, we consider the decoupling of services and the load balancing of edge servers, model the problem of service deployment, propose a real-time decoupling scheme for centralized services, and design a static deployment strategy; In the second stage, we consider the mobility of edge devices, design a dynamic deployment strategy for device mobility-aware services, and optimize the quality of service under the mobile edge computing architecture. The experimental results on two datasets show that the static deployment strategy proposed in this paper can reduce the response time of service requests by 36%, and the dynamic deployment strategy can further reduce the service response time by 13%.
-
Keywords:
- edge computing /
- quality of service(QoS) /
- response time /
- service decoupling /
- service deployment
-
随着物联网和5G无线网络的快速发展,万物互联已经成为一种趋势,促进了各个领域新兴应用的发展[1]. 与此相对应的是边缘设备及其产生的数据量迅速增长. 麦肯锡全球研究报告称,预计到2025年,物联网连接的设备将超过300亿个,相关的数据量也从2016 年的96 ZB/月增长到了2021 年的278 ZB/月[2]. 这些海量而多样的设备和数据连接物与物、物与人,最终实现“万物互联”[3].
关键技术的蓬勃发展也使得分布式的用户请求数量迅速增加. 然而,当前的服务模式大多是将应用程序的功能封装为独立的单元并将该单元部署在云服务器上. 分布式的用户向云端服务器发送服务请求,云端服务器运行相应的应用程序并向用户反馈结果. 然而,这种集中式的服务往往会带来巨大的服务响应延迟和带宽开销,降低服务质量(quality of service, QoS)[4].
解决上述问题的一种有效的方法是将这种集中式服务解耦为子服务. 例如,Auer等人[5]提出了一个基于问卷调查的评估框架,他们通过问卷调查归纳出将集中式服务解耦并部署到子服务架构上的重要指标,并根据问卷调查的结果来推断具体的集中式服务具体如何解耦并部署到子服务架构中. 然而,这种基于问卷调查的解耦方案受限于问卷设计,通常都比较主观,其效果和普适性较差,并且会耗费大量的人力和时间成本. 为了解决上述问题,Arisholm等人[6]提出了动态耦合度的概念用于衡量应用程序在实际运行时的相关程度. Poshyvanyk等人[7]提出了一种用于衡量程序的类之间的标识符和相关性的耦合度. 然而,这些现有的工作忽略了服务自身的特性(如服务的字段等),因而效果不佳.
除了对集中式服务进行解耦,将解耦后的子服务部署到边缘计算架构中也是一个能够有效降低时延的解决方案. 边缘计算利用终端设备的计算能力,可以显著减少传输到云服务器的数据量和服务请求的响应时间[8-9]. 然而,由于边缘设备的存储空间和计算能力有限,如何将解耦后的子服务部署在边缘服务器上是亟待解决的问题. 现有关于边缘计算架构下的服务部署的相关工作如文献[10-12],并没有同时考虑边缘服务器本身的异构性和服务器之间的负载均衡,并且脆弱的边缘设备也带来了严重的安全性问题. 首先,对于大多数边缘计算相关技术(如无线网络和分布式系统等),不仅需要保护其中的组件免受网络攻击,还需要协调不同等级的安全机制. 其次,对边缘计算而言,在异构的系统下提供稳定的连接和高可访问性是提供高质量服务的基础[13]. 因此,边缘服务器在保证网络安全的条件下及时响应用户的服务请求就显得尤为重要.
移动设备数量的爆炸式增长推动了传统的边缘计算向移动边缘计算(mobile edge computing, MEC)的方向发展. 移动边缘计算[14]将云端的计算能力推向了边缘端,即在移动设备和无线接入网的边缘部署计算平台,使得移动设备可以就近使用所需服务和云端计算功能[15]. 尽管移动边缘计算可以显著地降低端到端的延迟,但是设备移动的不可预测性给部署服务带来了新的挑战[16]. Wang等人[17]设计了一种服务迁移策略来解决顺序决策服务的部署问题. Taleb等人[18]基于马尔可夫链模型提出了一种面向移动设备的边缘计算部署策略. 然而,文献[14-18]所述工作都没有考虑到移动边缘计算服务部署的成本问题.
本文提出了一种2阶段的服务质量优化方案以解决移动边缘计算架构下的服务部署问题. 在第1阶段,本文考虑了服务的解耦和边缘服务器的负载均衡问题,对服务部署问题进行建模,提出了一种集中式服务的实时解耦方案,并且设计了一种静态部署策略;在第2阶段,本文考虑了边缘设备的移动性,设计了一种设备移动感知的服务部署策略,优化了移动边缘计算架构下的服务质量. 具体来说,本文的主要贡献包括3个方面:
1)在考虑边缘服务器负载均衡的前提下提出了一种面向集中式服务的解耦策略,并设计了一种基于分解的多目标进化算法的服务部署策略以优化服务质量. 该策略能够在保证服务器负载均衡和安全性的前提下,优化服务请求的响应时间.
2)进一步考虑了边缘设备的移动性,提出了一种动态服务部署策略. 首先,为了适应移动的服务请求,建模动态用户的服务部署问题. 然后,提出了一种设备移动感知的实时服务放置策略以进一步优化服务请求的响应时间.
3) 为了验证所提方法的有效性,本文进行了一系列的仿真实验. 实验结果表明,与多种基准方法相比,在保证系统安全以及服务器负载均衡的前提下,本文所提出的面向集中式服务静态部署策略能够服务请求的响应时间降低36%,所提出的动态部署策略能进一步降低13%的服务响应时间.
1. 系统模型
本节主要介绍本文主要用到的相关模型,包括系统架构模型、服务模型、耦合度模型和传输成本模型.
1.1 系统架构模型
不失一般性,本文采用常见的移动边缘计算系统架构. 假设该架构硬件上包含1个云服务器、Nes个边缘服务器、Nbs个基站和Ntd个终端设备. 基站之间通过有线连接,终端设备与基站之间通过无线连接,终端具有可移动性. 边缘服务器的集合用ES={ES1, ES2, …,
ESNes }表示,其中ESi (1⩽ i\leqslant Nes)为第i个边缘服务器. 基站的集合用Vbs表示,终端设备的集合用Vt表示. 系统架构图如图1所示,其拓扑关系可以用无向图G={V, E}表示,其中V=Vbs∪Vtd,E=Ewire∪Ewireless,其中Ewire为2基站之间所有的有线连接组成的集合,Ewireless为所有基站和终端设备之间的无线连接所组成的集合.在云端服务器上维护完整的集中式服务,并且负责将集中式服务解耦为Nser个子服务并且将这些子服务部署/卸载到Nes个边缘服务器上. 每个边缘服务器通过使用子服务来快速响应终端设备的服务请求,这些边缘服务器在计算能力和存储空间上是异构的. 由于基站数量的不断增加,在所有的基站上部署边缘服务器会带来巨大的成本,因此并不是所有的基站附近都会部署边缘服务器,即Nes
\leqslant Nbs. 在本文中,使用文献[19]所提出的方法将Nes个边缘服务器部署在Nbs个基站上. 基站会负责接收邻近终端设备的服务请求,这个基站被称为这些终端设备的本地基站,对应的边缘服务器被称为这些终端设备的本地边缘服务器. 如果终端设备的本地基站部署了边缘服务器,且终端设备的服务请求可以在本地边缘服务器上处理,则请求将直接在本地边缘服务器上处理,否则这个服务请求将被转发到可以处理该请求的边缘服务器上,结果会被返回给终端设备.1.2 服务及耦合度模型
假设云服务器维护Nser个服务,服务集合S={S1, S2, …,
S_{N_{{\rm{ser}}}} },每个服务Sj (1\leqslant j\leqslant Nser)包含Mj个字段. 定义一个Mj×Nes大小的矩阵Ij来表示服务中各个字段的被订阅情况:{{\boldsymbol{I}}_j} = \left( {\begin{array}{*{20}{c}} {I_{j,1}^1}& … &{I_{j,1}^{{N_{{\text{es}}}}}} \\ \vdots &{}& \vdots \\ {I_{j,{M_j}}^1}& … &{I_{j,{M_j}}^{{N_{{\text{es}}}}}} \end{array}} \right), (1) 如果边缘服务器ESi (1
\leqslant i\leqslant Nes)订阅服务Sj (1\leqslant j\leqslant Nser)上的第m (1\leqslant m\leqslant Mj)个字段,则I_{j,m}^i = 1 ,否则I_{j,m}^i = 0 . 易得,矩阵Ij中第i列为边缘服务器ESi对服务Sj的订阅情况. 对服务中字段的操作包括3种:删除、增加和修改. 我们定义了3个指示变量,以分别表示对服务Sj中字段m的操作.{\mu }_{j,m}^{\text{del}}=\left\{ \begin{aligned} & 1, 服务S_{ j}删除字段m,\\& 0, 其他. \end{aligned} \right. (2) {\mu }_{j,m}^{\text{add}}=\left\{ \begin{aligned} &1, 服务S_{ j}增加字段m,\\& 0, 其他. \end{aligned} \right. (3) {\mu }_{j,m}^{\text{upd}}=\left\{ \begin{aligned} &1, 服务S_{ j}更新字段m,\\& 0, 其他. \end{aligned} \right. (4) 对于边缘服务器ESi (1
\leqslant i\leqslant Nes),定义一个对服务Sj中字段m的影响因子:f_{j,m}^i = I_{j,m}^i\left( {{\omega ^{{\text{del}}}}\mu _{j,m}^{{\text{del}}} + {\omega ^{{\text{add}}}}\mu _{j,m}^{{\text{add}}} + {\omega ^{{\text{upd}}}}\mu _{j,m}^{{\text{upd}}}} \right), (5) 其中
{\omega ^{{\text{del}}}} ,{\omega ^{{\text{add}}}} ,{\omega ^{{\text{upd}}}} 分别为删除、增加和更新字段m对服务Sj影响的权重因子. 需要注意的是,这3种对服务中字段的操作都是原子操作. 也就是说,在每次对字段的操作中,有且只有上述3种操作的其中一种. 服务的耦合度用于判定服务是否需要被解耦的依据. 将服务Sj在边缘服务器ESi上的耦合度定义为FS_{ j}^i = \sum\limits_{m = 1}^{{M_j}} {f_{j,m}^i} . (6) 因此,服务Sj的耦合度为
F{S_{ j}} = \sum\limits_{i = 1}^{{N_{{\text{es}}}}} {FS_{ j}^i} . (7) 从式(6)(7)的定义可以看出,一个服务的耦合度越高,其中的字段操作越频繁. 如果不对这种高耦合度的服务进行解耦,产生的传输成本就会越高. 因此,本文的方案倾向于解耦对高耦合度的服务.
1.3 安全性模型
本文定义了一个包含了K种不同类型的安全服务的集合,该集合用A={A1, A2, …, AK}表示. 假设seci (1
\leqslant i\leqslant K)为服务Sj使用安全服务Ai后的安全等级. T(Ai, Sj)为服务Sj使用安全服务Ai时的开销:T\left( {{A_i},{S_j}} \right) = {C_i} \times se{c_i}, (8) 其中Ci为常数系数,取决于具体的安全服务算法. 本文采用指数模型[20]计算服务Sj采用安全服务Ai失败的概率为
{P}_{\text{fail}}\left({S}_{j}\right)=\left\{ \begin{aligned} &1-\mathrm{exp}\{-\lambda \left(se{c}_{j}^{\mathrm{min}}-se{c}_{i}\right)\}, se{c}_{j}^{\mathrm{min}}\ge se{c}_{i},\\ & 0, 其他,\end{aligned} \right. (9) 其中
sec_j^{\min } 是服务{S_j} 最低要求的安全级别,\lambda 表示具体应用的安全风险的常数. 因此,服务被成功运行的概率为QS\left( {{S_j}} \right) = 1 - {P_{{\text{fail}}}}\left( {{S_j}} \right). (10) 整个系统的安全性可以被定义为各个服务的安全性的乘积:
Q{S_{{\text{sys}}}} = \prod\limits_{j = 1}^{{N_{\text{s}}}} {QS\left( {{S_j}} \right)} . (11) 因此,为所有服务提供安全服务的总耗时为
{T_{{\text{ss}}}} = \sum\limits_{j = 1}^{{N_{\text{s}}}} {T\left( {{A_i},{S_j}} \right)Cost\left( {{S_j}} \right)} , (12) 其中
Cost\left( {{S_j}} \right) 为传输服务{S_j} 所带来的开销,在1.4节详细定义了该值.1.4 传输成本模型
为了将服务从云服务器卸载到边缘服务器,一般会将服务封装到Internet协议数据包中. 因此,除了要考虑服务本身的大小,还需要考虑一些额外信息(如头部信息等)所产生的开销. 假设这类开销用
Cos{t_{{\text{head}}}} 表示,则传输服务{S_j} 所带来的开销被计算为Cost\left( {{S_j}} \right) = Cos{t_{{\text{head}}}} + \sum\limits_{m = 1}^{{M_j}} {Cost\left( m \right)} , (13) 其中,
Cost\left( m \right) 为服务{S_j} 中第m个字段的大小.假设服务
{S_j} 被解耦为Nsub个子服务,第n个子服务用S_n^{(j)} 表示,则{S_j} = S_1^{(j)} \cup S_2^{(j)} \cup … \cup S_{{N_{\text{sub}}}}^{(j)} . 卸载子服务的开销为Cost\left( {S_n^{(j)}} \right) = Cos{t_{{\text{head}}}} + \sum\limits_{m = 1}^{\left| {S_n^{(j)}} \right|} {Cost\left( m \right)} , (14) 其中
\left| {S_n^{(j)}} \right| 为服务{S_j} 解耦产生的子服务的个数.在传输成本方面,假设设备通过无线连接与服务器进行通信,服务器之间通过电缆或者光纤的有线连接方式传输信息. 2个边缘服务器
E{S_i} 和E{S_j} \left( {1 \leqslant i\leqslant {N_{{\text{es}}},\,{1}\leqslant{j}\leqslant{N_{{\text{es}}}}}} \right) 之间的传输时延为T_{i,j}^{{\text{trans}}} = {{{W_{i,j}}} \mathord{\left/ {\vphantom {{{W_{i,j}}} {{B_{i,j}}}}} \right. } {{B_{i,j}}}}, (15) 其中
{W_{i,j}} 和{B_{i,j}} 分别为边缘服务器E{S_i} 和E{S_j} 之间需要传输的数据量和带宽大小. 而这2个服务器之间的传播时延为T_{i,j}^{{\text{prop}}} = {{{D_{i,j}}} \mathord{\left/ {\vphantom {{{D_{i,j}}} \theta }} \right. } \theta }, (16) 其中,
{D_{i,j}} 为E{S_i} 和E{S_j} 之间根据路由的物理链路距离,\theta 为电缆/光缆中电信号的传播速率. 因此,可以定义E{S_i} 和E{S_j} 之间的有线总时延:T_{i,j}^{{\text{wire}}} = T_{i,j}^{{\text{trans}}} + T_{i,j}^{{\text{prop}}}. (17) 设备i与服务器
E{S_j} 之间的无线传输时延为T_{i,E{S_j}}^{{\text{wireless}}} = {{{W_{i,E{S_j}}}} \mathord{\left/ {\vphantom {{{W_{i,E{S_j}}}} {T{R_{i,E{S_j}}}}}} \right. } {T{R_{i,E{S_j}}}}}, (18) 其中
{W_{i,E{S_j}}} 和T{R_{i,E{S_j}}} 分别为设备i和E{S_j} 之间需要传输的数据大小和最大传输速率.T{R_{i,E{S_j}}} 计算为[21]T{R_{i,E{S_j}}} = {B_{i,E{S_j}}}\ln {\text{ }}\left( {1 + {{{P_{\text{sig}}}} \mathord{\left/ {\vphantom {{{P_{\text{s}}}} {{P_{\text{n}}}}}} \right. } {{P_{\text{noi}}}}}} \right), (19) 其中,
{B_{i,E{S_j}}} 为设备i和E{S_{ j}} 之间的带宽,{P_{\text{sig}}} ,{P_{\text{noi}}} 分别为设备i和E{S_j} 之间的信号功率与噪声功率.2. 集中式服务的实时解耦方案以及部署策略
本文所提方案用于解决移动边缘计算架构下的服务安全部署问题. 本节主要介绍所提方法的第1阶段. 具体来说,在这个阶段,我们考虑了服务的安全性和边缘服务器的负载均衡问题,对服务部署问题进行建模,提出了一种集中式服务的实时解耦方案以及部署策略.
2.1 基于K-Means算法的服务实时解耦
根据1.2节对服务耦合度的定义可知,如果一个服务的耦合度越高,其中的字段被进行增加、修改和删除的操作越频繁. 如果不对这种高耦合度的服务进行解耦,会产生较高的传输成本. 因此,本文所提方案仅对高耦合度的服务进行解耦. 具体来说,定义一个服务的耦合度阈值Fth. 如果服务Sj的耦合度FSj>Fth,则Sj被认为是高耦合度服务,需要被解耦;反之,则认为服务Sj为低耦合度服务,不需要被解耦.
在对服务进行耦合度分类后,采用文献[22]中所提出的算法ISODATA (iterative self-organizing data analysis techniques algorithm), 对服务进行初始解耦. 这种解耦方法原理简单且易于实现,然而,该解耦方式本质上是一种离线的解耦,不适合增加、删除和修改操作频繁的移动感知应用场景,其对应的响应时延也较长. 因此,本文提出了一种基于加权K-Means算法的服务解耦方案,该方案可以实现对服务的实时解耦.
K-Means是一种迭代求解的聚类分析算法,是基于欧氏距离的聚类算法. K-Means算法认为2个目标的距离越近,相似度越大. 具体来说,该算法首先会随机选择初始化后的K个样本作为初始聚类中心,这些聚类中心被表示为
\left\{ {{C_1},{C_2}, … ,{C_K}} \right\} . 对于每个待聚类的样本,首先计算该样本和每一个聚类中心的欧氏距离,然后将样本分类到与其距离最小的聚类中心对应的类别,最后算出每个类别的平均值以更新聚类中心.在本文的应用场景下,文献[22]所提出的ISODATA算法会产生一个对服务的初始解耦结果,即对服务集合中每一个服务的解耦方案,解耦出的子服务即为一个类别,这些子服务的中心即为聚类中心. 以服务
{S_j} 为例,假设ISODATA算法将服务{S_j} 解耦为Nsub个子服务,其中,第n个子服务用S_n^{(j)} 表示,则{S_j} = S_1^{(j)} \cup S_2^{(j)} \cup … \cup S_{{N_{\text{sub}}}}^{(j)} . 为每个子服务定义了一个中心,在时隙t的第k 个中心的定义为C_k^t = \frac{{C_k^{t - 1}n_k^{t - 1} \pm x\,_k^{t - 1}m_k^{t - 1}}}{{n_k^{t - 1} \pm m_k^{t - 1}}}. (20) 其中,
x\,_k^t 为时刻t第k个子服务中所增加(或删除)字段的中心;m_k^t 为属于第k个聚类中心的新增加(或删除)字段的数量;n_k^t 为时刻t第k个子服务中所包含的字段的数目,该值的计算式为n_k^t = n_k^{t - 1} \pm m_k^{t - 1}. (21) 时刻t中心的集合被表示为
\left\{ {C_1^t,C_2^t, … ,C_{{N_{{\rm{sub}}}}}^t} \right\} . 需要注意的是,如果是增加字段,那么式(21)中的±取“+”;如果是删除字段,式(21)中的±取“−”;如果是更新字段,则m_k^t =0.我们只对高耦合度的服务进行解耦. 具体来说,定义了一个耦合度阈值
{F_{{\text{th}}}} ,对于每一个服务{S_j} ,采用式(7)计算其对应的耦合度F{S_{ j}} . 若F{S_{ j}} > {F_{{\text{th}}}} ,则服务{S_{ j}} 为高耦合度服务,需要采用解耦算法进行解耦;反之,服务{S_{ j}} 为低耦合度服务,不需要被解耦. 提出的基于加权K-Means算法的实时服务解耦方案将ISODATA产生的结果作为初始解,实时地根据对服务中字段的操作(增加、删除和更新),不断地实时更新每一个服务的解耦方案,在考虑边缘服务器节点负载均衡的条件下优化服务请求的响应时间.所提出的基于K-Means的服务解耦算法对应的伪代码如算法1所示.
算法1. 基于K-Means的服务解耦算法.
输入:阈值
{F_{{\text{th}}}} ,服务集合S={S1, S2, …,S_{N_{{\rm{ser}}}} };输出:对每一个服务的解耦方案.
① 初始化:Ω=
\varnothing ,K=Nsub;② for each 服务
{S_{ j}} ③
F{S_{ j}} = 0 ;④ 采用式(7)计算服务
{S_{ j}} 的耦合度;⑤ if
F{S_{ j}} > {F_{{\text{th}}}} ⑥ 将服务
{S_{ j}} 加入集合Ω;⑦ 采用ISODATA算法[22]得到初始解耦 方案和K个聚类中心的初始取值;
⑧ else
⑨ 不对服务
{S_{ j}} 进行解耦操作;⑩ end if
⑪ end for
⑫ for each Sj∈Ω
⑬ for each 子服务中心
C_k^t /*往服务{S_{ j}} 中 增加字段*/⑭ 计算增加字段与
C_k^t 之间的欧氏距离;⑮ 将增加的字段加入与之最近的
C_k^t 对应 的子服务;⑯ 根据式(20)更新聚类中心
C_k^t ;⑰ end for
⑱ for each 子服务中心
C_k^t /*往服务{S_{ j}} 中删除或 更新字段*/⑲ 从对应的子服务中删除/更新字段;
⑳ 根据式(20)更新聚类中心
C_k^t ;㉑ end for
㉒ end for
㉓ return 对每一个服务的解耦方案.
算法1以耦合度阈值
{F_{{\text{th}}}} 和服务集合S={S1, S2, …, SNser }作为输入,并输出对每一个服务的解耦方案. 算法1首先初始化需要被解耦的服务的集合为空集,该集合用Ω表示;然后将聚类中心的个数K设为预计解耦得到的子服务的个数Nsub(算法1的行①). 对于每一个服务{S_{ j}} ,首先将其耦合度F{S_{ j}} 初始化为0,然后采用式(7)计算服务{S_{ j}} 的耦合度(算法1的行③④). 如果服务{S_{ j}} 的耦合度大于耦合度阈值,则认为{S_{ j}} 为高耦合度服务,此时需要对服务进行解耦,因此将{S_{ j}} 加入集合Ω,并采用ISODATA算法[22]得到初始解耦方案和K个聚类中心的初始取值;否则认为{S_{ j}} 为低耦合度服务,不需要对其进行解耦(算法1的行②~⑪). 对集合Ω中每一个服务{S_{ j}} ,如果此时需要增加其中的字段,则算法1首先计算增加的字段与此时每一个聚类中心C_k^t 之间的欧氏距离,然后将增加的字段加入与之最近的C_k^t 对应的子服务,并根据式(20)更新C_k^t (算法1的行⑬~⑰). 如果此时需要删除/更新服务{S_{ j}} 中的字段,则从对应的子服务中删除/更新相应字段,并根据式(20)更新C_k^t (算法1的行⑱~㉑). 需要注意的是,如果相应的操作是更新,则式(20)中m_k^t =0. 也就是说,此时相应子服务中的字段数量不会改变. 迭代结束后,算法1会返回对每一个服务的解耦方案.2.2 基于MOEA/D的服务静态放置策略
在对服务进行解耦之后,我们设计了一种静态的服务部署策略将解耦后的子服务部署到边缘服务器上以优化服务质量. 具体来说,首先将子服务的部署问题建模为一个多目标优化问题(multi-objective optimization problem, MOP),然后采用基于分解的多目标进化算法(multi-objective evolutionary algorithm based on decomposition, MOEA/D)去解决该问题,以保证在服务器负载均衡和安全性的前提下,优化服务请求的响应时间.
结合第1节的建模,可以将本文所关注的问题建模为一个多目标优化问题,该多目标优化问题表示为
\begin{gathered} {\text{min}}\left\{{F_M}\left( x \right) =\{ {{f_1}\left( x \right),{f_2}\left( x \right), … ,{f_M}\left( x \right)}\}\right\}, \\ {\text{s}}{\text{. t}}{\text{. }}x \in Y, \end{gathered} (22) 其中
{F_M}:Y \to {\mathbb{R}^M} 由M个实值函数组成,Y为决策空间,{\mathbb{R}^M} 为目标空间. 为了便于表述,给出2个定义.定义1. 如果存在2个向量u, v
\in {\mathbb{R}^M} ,任意i = 1,2, … ,M ,都满足{u_i} < {v_i} ,则称u支配v.定义2. 如果不存在
x \in Y ,满足{F_M}\left( x \right) 支配{F_M}\left( {\hat x} \right) ,则点\hat x 为{F_M}\left( x \right) 的一个帕累托最优解,帕累托集合PS=\{\hat{x}|不存在x\in Y,{F}_{M}\left(x\right)支配 \left. {F}_{M}{\left( {\hat x} \right)} \right\} . 假设由所有帕累托目标向量所组成的集合PF = \left\{ {{F_M}\left( x \right) \in {\mathbb{R}^M}|x \in PS} \right\} 为帕累托前沿.MOEA/D算法将式(22)中的目标函数分解为M个实值函数的优化问题,然后通过解决这M个实值函数的优化问题得到式(22)中的帕累托集合. 使用基于切比雪夫的分解算法来解决多目标优化问题,具体来说,首先定义目标优化问题:
\begin{gathered} {\text{min }}\left\{{g_M}\left( x \right) = \mathop {\max }\limits_{1 \leqslant i \leqslant M} \left\{ {{\lambda _i}|{f_i}\left( x \right) - z_i^*} \right\}\right\}, \\ {\text{s}}{\text{. t}}{\text{. }}x \in Y, \\ \end{gathered} (23) 其中
\lambda = \left\{ {{\lambda _1},{\lambda _2}, … ,{\lambda _M}} \right\} 是权重集合,{z^*} = \left\{ {z_1^*,z_2^*, … ,z_M^*} \right\} 是式(22)对应优化问题的参考解的集合. 在生成1组均匀分布的权重集合\lambda = \left\{ {{\lambda _1},{\lambda _2}, … ,{\lambda _M}} \right\} 并设置参考解{z^*} 后,式(22)的帕累托前沿PF 可以近似地分解成M个标量子问题,其中第j个子问题表示为\begin{gathered} {\text{min }}\left\{{g_M}\left( {x|{\lambda ^j},{z^*}} \right) = \mathop {\max }\limits_{1 \leqslant i \leqslant M} \left\{ {\lambda _i^j|{f_i}\left( x \right) - z_i^*} \right\}\right\}, \\ {\text{s}}{\text{. t}}{\text{. }}x \in Y, \\ \end{gathered} (24) 其中
{\lambda ^j} = \left\{ {\lambda _1^j,\lambda _2^j, … ,\lambda _M^j} \right\} . 由于函数g关于\lambda 是连续的,因此,如果{\lambda ^i} 无限接近于{\lambda ^j} ,则{g_M}\left( {x|{\lambda ^i},{z^*}} \right) 也无限接近于{g_M}\left( {x|{\lambda ^j},{z^*}} \right) . 所以邻近{\lambda ^j} 的权重向量可以帮助优化问题{g_M}\left( {x|{\lambda ^j},{z^*}} \right) . 定义{\lambda ^j} 的邻居为邻近{\lambda ^j} 的权重向量,第j 个子问题的邻居是{\lambda ^j} 的邻居对应的子问题.基于切比雪夫的MOEA/D算法,在每一轮迭代中更新4个内容:
1) 分解成的子问题数量M以及子问题i的当前解
{x\,^i} \in Y ;2) 定义
F{V^i} = {F_M}\left( {{x^{\,i}}} \right) ,\forall i = 1,2, … ,M ;3)
z = \left\{ {{z_1},{z_2}, … ,{z_M}} \right\} ,其中{z_i} 是到目前函数{f_i}\left( x \right) 的最优值;4) 在搜索过程中存储的非支配解的集合,该集合被表示为EP.
本文提出了基于MOEA/D的集中式服务放置算法来探索集中式服务配置到边缘服务器的解决策略. 具体来说,随机选择交叉算子和变异算子作为本文的遗传算子:
1) 交叉算子. 本文所关注的多目标优化问题为,在保证服务器负载均衡和安全性的前提下,将云服务器维护Nser个服务中每一个服务对应的Nsub个子服务部署至Nes个边缘服务器上,以优化服务请求的响应时间. 因此,该问题的解空间为
{\left[ {0,{N_{{\text{es}}}} - 1} \right]^{{N_{\text{sub}}}}} ,并在这个解空间内随机生成一个整数作为交叉算子. 为了便于理解,以子服务个数Nsub=7、边缘服务器个数Nes=3的情况为例. 假设随机生成的交叉算子为3,即从位置3开始进行交叉(子服务编号从0开始),则交叉情况如图2所示.2) 变异算子. 本文使用基于正态分布的随机数生成方式进行变异操作. 具体来说,对于染色体i的每个位置,先以
{P_{{\text{mutation}}}} 的概率判断是否会发生变异,若发生变异,则在该位置加上一个正态分布的随机数\tau ,并将结果调整到限定范围内,即{x}\,_{i,j}^{t+1}=\left\{ \begin{aligned} &{x}\,_{i,j}^{t}+Gauss(0,{\sigma }^{2}),& {\tau} < {P}_{\text{mutation}},\\ &{x}\,_{i,j}^{t},& 其他,\end{aligned} \right. (25) 其中
x\,_{i,j}^t 表示第t轮迭代时第i个个体的第j个子服务部署在第 x\,_{i,j}^t 个边缘服务器上.所提出的基于MOEA/D的子服务放置算法的伪代码如算法2所示.
算法2. 基于MOEA/D的子服务放置算法.
输入:最大迭代轮次
{T_{{\text{max}}}} ,子问题的数量{N_{{\text{pop}}}} ,权重向量集,邻居数{T_{{\text{nb}}}} ;输出:对子服务的放置方案.
① EP=∅,PS=∅,T=0;/*初始化*/
② 随机生成的参考解
z = \left\{ {{z_1},{z_2}, … ,{z_{{N_{{\text{pop}}}}}}} \right\} ;③ 计算每个权重向量的
{T_{{\text{nb}}}} 个邻居;④ 随机生成种群
{x^1},{x^2}, … ,{x^{{N_{{\text{pop}}}}}} ,计算每个F{V^i} ;⑤ while
T \leqslant {T_{{\text{max}}}} ⑥ for each
{x\,^i} in 种群⑦ 生成基于个体i邻居的新解yi;
⑧ for each 邻居j
⑨ if
{g_{{N_{{\text{pop}}}}}}\left( {y|{\lambda ^j},z} \right) \leqslant {g_{{N_{{\text{pop}}}}}}\left( {{x^j}|{\lambda ^i},z} \right) ⑩ 更新
{x^j} = {y_i},F{V^j} = {z_j} ;⑪ end if
⑫ end for
⑬ end for
⑭ for PS中的每一个 j
⑮ if
{z_j} 支配yi⑯ 从
EP 中删除{z_j} ;⑰ 从
PS 中删除j;⑱ end if
⑲ end for
⑳ if 在
EP 中没有向量支配yi㉑ 向
EP 中添加{z_j} ;㉒ 从
PS 中删除j;㉓ end if
㉔ T=T+1;
㉕ end while
㉖ return
PS .算法2以大迭代轮次
{T_{{\text{max}}}} 、 子问题的数量{N_{{\text{pop}}}} 、权重向量集、邻居数{T_{{\text{nb}}}} 为输入,并输出对子服务的放置方案,也就是本文提出的多目标优化问题对应的帕累托集合PS . 算法2首先将在搜索过程中存储的非支配解的集合EP 和帕累托集合PS 初始化为空集,并且将迭代次数设置为0(算法2中的行①). 然后随机生成参考解z = \left\{ {{z_1},{z_2}, … ,{z_{{N_{{\text{pop}}}}}}} \right\} ,并计算每一个权重向量的{T_{{\text{nb}}}} 个邻居(算法2中的行②③). 接着,随机生成种群{x^1},{x^2}, \ldots ,{x^{{N_{{\text{pop}}}}}} ,并计算每个F{V^i} (算法2中的行④). 在每一轮迭代中,首先计算种群中每一个个体{x\,^i} 的邻居的新解yi,然后对于每个邻居j,如果{g_{{N_{{\text{pop}}}}}}\left( {y|{\lambda ^j},z} \right) \leqslant {g_{{N_{{\text{pop}}}}}}\left( {{x^j}|{\lambda ^i},z} \right) 成立,则更新{x^j} = {y_i}, F{V^j} = {z_j} (算法2中的行⑤~⑬). 对于每一个已经在帕累托集合PS 中的邻居j,首先判断{z_j} 是否支配yi,如果是,则分别从集合EP 和PS 中删除{z_j} 和j(算法2中的行⑭~⑲). 如果在EP 中没有向量支配yi, 说明此时的邻居j为目前的最优解,将对应的{z_j} 和j加入集合EP 和PS (算法2的行⑳~㉓). 迭代结束后,算法2会返回对子服务的放置方案,即迭代得到的帕累托集合PS .3. 设备移动感知的动态服务部署策略
现实生活中,越来越多的终端设备会随着用户一边移动一边进行服务请求. 为了进一步考虑边缘设备的移动性,本文提出了一种设备移动感知的动态服务部署策略. 首先,为了适应移动的服务请求,建模了服务迁移成本队列解耦动态用户的服务部署问题;然后,提出了一种基于响应时间优先的实时服务放置策略.
图3展示了用户移动情况下,在移动边缘计算架构下一个用户移动轨迹的示例[23]. 在该架构下,考虑网络运营商设置了
{N_{{\text{mes}}}} 个MEC节点来服务{N_{{\text{user}}}} 个移动用户. 每个MEC节点都通过高速局域网与邻近的基站或是无线接入点相连接. 每个用户携带一个移动设备,在移动设备上运行的应用程序的服务配置文件将分配到给定的边缘服务器的专用虚拟机[24]或容器[25]. 将系统的运行均分成若干时隙,其时间线被离散成若干时间帧t \in \left\{ {0,1, … ,T} \right\} . 在每个离散时隙,每个移动用户向本地MEC节点发送服务请求,由软件定义网络控制器(SDN控制器)收集所有用户的服务请求信息并根据当前全局系统确定最佳MEC节点为相应用户提供服务.用户的移动通常是不规律的,为了使用户可以获得高质量的QoS服务,每个用户的服务配置文件应该随着用户移动性动态迁移. 定义
{x_{i,j}}\left( t \right) 表示在时隙t 用户j 的服务配置文件是否部署在MEC节点i 上,如果是,则{x_{i,j}}\left( t \right) = 1 ,否则{x_{i,j}}\left( t \right) = 0 .在MEC架构下,安全关键型服务的QoS由通信时延、计算时延以及为服务提供安全服务的时延所决定. 假设记
T_j^{{\text{QoS}}}\left( t \right) 为时隙t 时用户j 的总QoS时延,T_j^{{\text{QoS}}}\left( t \right) 被定义为T_j^{{\text{QoS}}}\left( t \right) = \sum\limits_{i = 1}^{{N_{{\text{mes}}}}} {{x_{i,j}}\left( t \right)\left( {T_{i,E{S_j}}^{{\text{wireless}}} + T_{i,j}^{{\text{cal}}} + {T_{{\text{ss}}}}} \right)} , (26) 其中
T_{i,E{S_j}}^{{\text{wireless}}} 和{T_{{\text{ss}}}} 分别由式(18)和式(12)给出,T_{i,j}^{{\text{cal}}} 被定义为T_{i,j}^{{\text{cal}}} ={{M_{i,j}}}/{{P_j}}\text{,} (27) 其中,
{M_{i,j}} 为用户i 在MEC节点j 上的服务配置文件的大小,{P_j} 为节点j 的计算能力.使用
Cost\,_{{i_1},{i_2}}^j\left( t \right) 表示将用户j 的服务配置文件从MEC节点{i_1} 迁移到MEC节点{i_2} 的开销,则在时隙t 用户j 的服务迁移成本Cos{t_j}\left( t \right) 计算为Cos{t_j}\left( t \right) = \sum\limits_{{i_1}}^{{N_{{\text{mes}}}}} {\sum\limits_{{i_2}}^{{N_{{\text{mes}}}}} {{x_{{i_1},j}}\left( {t - 1} \right)} }\times {x_{{i_2},j}}\left( t \right)\times Cost_{{i_1},{i_2}}^j\left( t \right). (28) 因此,在时隙
t 时所有用户的服务迁移成本Cos{t_{{\text{total}}}}\left( t \right) 计算为Cos{t_{{\text{total}}}}\left( t \right) = \sum\limits_{j = 1}^{{N_{{\text{user}}}}} {Cos{t_j}\left( t \right)} . (29) 定义队列
{Q_{\text{L}}}\left( t \right) 表示从零时隙到时隙t 时累计超出给定的长期平均期望预算的度量. 由式(26)(29)可得,{Q_{\text{L}}}\left( {t + 1} \right) 可由时隙t 时的{Q_{\text{L}}}\left( t \right) 、时隙t 时的服务迁移成本以及长期平均期望预算推导得出:{Q_{\text{L}}}\left( {t + 1} \right) = \max \left\{ {{Q_{\text{L}}}\left( t \right) + Cos{t_{{\text{total}}}}\left( t \right) - Cos{t_{{\text{avg}}}}\left( t \right),0} \right\}. (30) 为了保证迁移成本的平均值不超过长期平均期望预算,则
{Q_{\text{L}}}\left( t \right) 的长期平均值应趋向于0. 因此,{Q_{\text{L}}}\left( {t + 1} \right) \geqslant {Q_{\text{L}}}\left( t \right) + Cos{t_{{\text{total}}}}\left( t \right) - Cos{t_{{\text{avg}}}}\left( t \right) 成立. 定义二次李雅普诺夫函数为L\left( t \right) = \frac{1}{2}{Q_{\text{L}}}{\left( t \right)^2}. (31) 一般地,
L\left( t \right) 越小表示队列{Q_{\text{L}}}\left( t \right) 的队列积压越小[26]. 因此,当二次李雅普诺夫函数保持有界时,则可推导得到队列{Q_{\text{L}}}\left( t \right) 是稳定的. 此时假设服务部署策略为d ,并构建一条平稳分布的马尔可夫链.p_d^{d'}\left( t \right) 是时隙t 时状态d 到状态d' 的非负转移率,其中p_d^{d'}\left( t \right) 在满足式(32)条件时,马尔可夫链满足平稳分布[27].p_d^{d'}\left( t \right) = \alpha \exp \left\{ {\frac{\beta }{2}\left( {s\left( {d',t} \right) - s\left( {d,t} \right)} \right)} \right\} \text{,} (32) 其中
\alpha 和\beta 为常数.本文所提出的设备移动感知的动态服务部署策略的伪代码如算法3所示.
算法3. 设备移动感知的动态服务部署策略.
输入:服务放置策略的状态空间
d\left( t \right) ,最大迭代轮次{T_{{\text{max}}}} ;输出:最优服务放置策略
{d^*} .① 初始化服务部署策略
d ,该部署策略将每个 服务配置文件随机分配到{N_{{\text{mes}}}} 个MEC节 点上;/*初始化*/② 迭代轮次
T =0;③ while
T \leqslant {T_{{\text{max}}}} ④ 随机选择一个用户的服务配置文件;
⑤ for each
d' \in d\left( t \right),d' \ne d ⑥ 使用式(26)计算成本函数;
⑦ end for
⑧ 根据式(29)计算得到的概率选择一种放 置策略;
⑨ 通过将服务放置到新的MEC节点来更 新服务放置策略;
⑩ 设使得
Cos{t_{{\text{total}}}}\left( t \right) 最小的服务放置策略为{d^*} ;⑪ T++;
⑫ end while
⑬ return
{d^*} .算法3以状态空间
d\left( t \right) 和最大迭代轮次{T_{{\text{max}}}} 作为输入,并输出最优服务放置策略{d^*} . 算法3首先初始化迭代轮次为0,并随机生成一个服务部署策略d ,该部署策略d将每个服务配置文件随机分配到{N_{{\text{mes}}}} 个MEC节点上(算法3的行①). 对于每一次迭代,首先随机选择一个用户的服务配置文件,对于在此时服务放置策略的状态空间d\left( t \right) 中除了d 以外的每一个部署策略d' ,使用式(26)计算成本函数(算法3的行⑤~⑦). 接着算法3根据式(29)计算得到的概率选择一种放置策略并通过将服务放置到新的MEC节点来更新现有的服务放置策略(算法3的行⑧~⑩). 设使得Cos{t_{{\text{total}}}}\left( t \right) 最小的服务放置策略为{d^*} ,该策略{d^*} 即为最佳放置策略,{d^*} 会在每一轮迭代中被更新(算法3的行⑩). 最后,算法3会返回迭代结束后得到的最佳服务放置策略(算法3的行⑬).4. 实 验
本文在2个数据集上进行实验以验证所提方案的有效性. 具体来说,首先介绍了相关的实验设置;然后以传输开销为评价标准来衡量所提的基于K-Means的服务解耦算法的有效性; 接着,在多个方面将所提的基于MOEA/D的服务静态放置策略与3种基准算法相比较,以验证所提的静态放置策略的有效性; 最后,在多个方面将所提的设备移动感知的动态服务部署策略与3种基准方法相比较,以验证所提的动态服务部署策略的有效性.
4.1 实验设置
本文的实验环境使用Windows 10操作系统,8GB内存,AMD Ryzen 5 4500U @ 2. 38GHz处理器,并使用Python3. 7的运行环境.
在数据集方面,本文采用2个数据集进行实验. 第1个数据集是1990年美国人口普查公开数据集(以下简称数据集1)[28],该数据集包含了大约20万条1990年美国人口的普查结果,其包含年龄等68种基本特征. 我们将该数据集分为10个服务,并由68个边缘设备对这些服务中的字段进行订阅. 第2个数据集是由上海交易中心信息技术有限公司提供的真实数据集(以下简称数据集2). 该数据集提供了上海交易中心信息技术有限公司真实的20个设备对15个服务对应的所有字段的订阅情况. 我们对每一个服务的耦合度进行计算,并采用所提出的实时解耦策略对这2个数据集中的服务进行解耦. 删除、增加和更新这3个指示变量,均设为1. 为了比较离线算法与在线算法节省的带宽,将头部信息的大小设置为10b,并假设每条数据为200b.
在开销方面,本文所提出的策略所带来的开销分为2个部分:算法的运行时间和因传输解耦后的服务所带来的传输开销. 因此,本文在4.2~4.4节对这2个方面的开销进行了详细的分析和对比.
4.2 基于K-Means的服务实时解耦策略验证
为了验证基于K-Means的服务实时解耦策略,本文对比了解耦前后的传输开销. 数据集1和数据集2的解耦前后传输开销分别如图4和图5所示. 从图4可以看出,编号1在解耦后的所有服务的通信开销平均减少了29.04%; 对编号3的服务解耦效果最为明显,其通信开销减少了44.20%. 从图5可以看出,与解耦前相比,所有服务在解耦后的传输开销平均减少了24.71%,其中传输开销减少可高达29.92%. 这是因为解耦后,边缘服务器减少了大量无关子服务的订阅数,因此减少了大量不必要的通信开销. 只有少数服务(如编号8的服务)在解耦前后通信开销变化不大. 这是因为这些服务解耦后边缘服务器仍然订阅了大量的子服务. 如果某服务订阅了解耦后服务集合的所有子服务,会由于解耦增加的额外成本导致解耦后的字段开销大于解耦前的字段开销. 在实际应用中,可以考虑不对该服务进行解耦.
图6对比了在数据集2上增加字段时ISODATA[22]和所提出的基于K-Means的实时解耦策略的运行时间. 在不改变划分结果的条件下,在线算法的运行时间远小于离线算法的运行时间. 在数据集2的10组数据中,在线算法的算法运行时间平均减少了78.14%,最多减少高达80.35%. 这是因为在线算法只需要遍历1遍数据即可完成对整个服务的划分,而离线算法通常要迭代很多轮才能收敛得到最终的划分结果.
图7展示了字段个数分别为2万、4万、8万以及12万时ISODATA[22]和所提出的基于K-Means的实时解耦策略的运行时间. 相比于ISODATA算法,4种不同字段个数的在线算法的算法运行时间分别减少了78.95%,85.37%,86.06%,85.35%. 由于算法的时间复杂度与字段个数呈正相关,字段个数越大,在线算法节省的时间也就越多. 因此,我们认为,所提出的基于K-Means的实时解耦策略比较适合服务体量较大也就是字段个数较大的情况. 在这种情况下,所提算法能够节约的处理时间较多,效果更好. 但是当服务较小或子服务耦合度较低时,所提方法反而可能会导致较大的开销. 这是因为所提方法需要传输解耦后的服务,而这会带来较大的传输延迟.
图8展示了数据集2在删除字段的场景ISODATA算法和所提的基于K-Means 的实时解耦策略的运行时间比较. 在解耦结果一致的条件下,所提实时解耦算法的运行时间远小于ISODATA算法的运行时间. 具体来说,在数据集2上所提出的实时解耦算法的运行时间平均减少了73.02%,最多减少高达75.80%.
4.3 基于MOEA/D的服务静态放置策略验证
为了验证所提的基于MOEA/D的集中式服务静态放置算法的有效性,本实验比较并分析了基于MOEA/D策略(本文算法)和3种基准算法的集中式服务静态放置结果,其中3种基准算法分别是基于随机的算法(RAND)、遗传算法(GA)[29]和粒子群算法(PSO)[30]. 这3种基准算法的原理为:
1) RAND. 随机选取每个服务部署的边缘节点放置服务.
2) GA. 遗传算法基于染色体自然进化,对染色体编码后,使用交叉和变异生成新的染色体,并基于适应度函数评估染色体的质量,最后根据最优染色体得到最优解以放置服务.
3) PSO. 粒子群优化是一种使用粒子模拟一群寻找食物的鸟的算法. 具有“速度”和“位置”的粒子是目标函数空间中的搜索个体,算法会基于所有粒子的历史最优位置调整速度. 最后将所有粒子当前位置的最优解视为全局最优解.
图9对比了当设备数量分别为3,5,10时,使用本文算法、PSO、 GA、RAND得到的平均服务响应时间. 服务响应时间是由本文算法运行时间和终端设备请求服务的响应时间组成,终端设备的响应时间由服务请求的通信时延、服务加密消耗的时间以及服务在边缘服务器运行所需的时间组成. 由图9可以看出,与PSO, GA,RAND 这3种基准算法相比,本文算法分别平均优化了9.23%,10.33%,15.07%,最高优化分别为24.89%,25.94%,35.55%. 这是因为本文算法的运行时间以及服务放置策略均优于这3种基准算法.
图10展示了当设备数量分别为3,5,10时,使用本文算法、PSO、GA、RAND算法得到的负载均衡平均优化率. 将本文算法的负载均衡平均优化率设置为1,与PSO, GA,RAND这3种基准算法相比,本文算法分别平均优化了3.28%,29.15%,66.97%,最高优化分别为89.67%,87.91%,96.10%. 虽然当边缘服务器数量为5时,PSO算法的负载均衡平均优化率小于1,然而此时其响应时间比本文算法高10.18%. 由于PSO和GA难以找到优化问题的全局最优解,因此使用PSO和GA算法得到的负载均衡平均优化率不如本文算法. 因此,由图10可以看出,本文所提的基于MOEA/D的服务静态放置策略适合被应用于设备数量较多、需要进行负载均衡的场景中. 此时,本文算法相较于基准算法,能够取得更好的优化效果.
4.4 设备移动感知的动态服务部署策略验证
为了验证所提设备移动感知的动态服务部署策略的有效性,本文所提方案与“总是迁移”(always migration, AM)、“从不迁移”(no migration, NM)以及“随机迁移K个服务”(random K-service migration, RKM)三种基准方法进行了对比. 这3种方法的原理简介如下:
1) AM. 在每个时隙中,用户的服务配置文件总是迁移到距离用户最近的MEC节点上.
2) NM. 在每个时隙中,用户的服务配置文件总保持在初始的MEC节点不迁移.
3) RKM. 在每个时隙中,随机选取K个服务配置文件迁移到当前最优的MEC节点上.
本节使用2007年由芬兰国家土地调查局提供的赫尔辛基市区的街道进行仿真[31]. 假设终端设备在该市区街道上进行移动,我们将该市区街道划分成64个正方形区域,每块大小500 m×500 m,在每块区域的中心位置部署MEC服务器提供移动服务,其中每台MEC服务器具有多个CPU核,其计算频率为25 GHz,存储空间为100~160 GB,2个MEC节点的距离使用曼哈顿距离. 假设街道上有2种类型的移动用户:一种是行人,速度在0. 5~1.5 m/s;一种是车载用户,速度在5.56~11.11 m/s,假设行人的数量占总人数的比率是7/8. 本实验仿真100个时隙,每个时隙是5 min,在每个时隙t内,假设用户的服务配置文件所在的MEC节点保持不变,响应用户所需要的服务大小均匀分布在0.8~1 GB.
图11展示了AM,NM,RKM和响应时间优先的算法(本文算法)得到的总时延,该总时延为服务的通信时延、加密时延以及计算时延之和. RKM算法中选取的配置文件个数K取总人数的10%. 与AM,NM,RKM这3种基准算法相比,本文算法的总时延分别平均减少了8.52%,10.64%,2.78%,最多减少可分别达10.78%,12.70%,3.74%. 这是由于NM算法从不迁移服务配置文件,因此其服务总时延基本与初始化服务配置文件放置结果有关;而AM算法虽然一直将服务配置文件迁移到距离用户最近的位置,然而当一个局部地区的人数过多时,迁移到同一MEC服务器上会给服务器的计算带来较大的压力,每个服务分得的资源也会减少,甚至会出现资源不够的情况;RKM算法每轮随机选取K个服务配置文件进行迁移,然而当K过小时,其性能会接近NM算法,且可能会导致无法优化部分服务配置文件的放置,而当K过大时会接近AM算法,同样可能出现资源分配不当的问题.
图12展示了AM,NM,RKM和响应时间优先的算法(本文算法)的服务迁移成本,其中平均期望预算被设定为200. 从图12中可以看出,AM算法由于频繁地进行服务配置文件的迁移,其服务迁移成本远超过长期平均期望预算;虽然NM算法不进行服务配置文件的迁移,但其服务的总时延过高,且与初始化的结果有很大的关系,通常会导致服务质量不高; 而RKM算法没有充分利用服务迁移预算,使其服务迁移成本一直保持在较低的水平; 而本文算法其服务迁移成本保持在长期平均期望预算的迁移成本之内的条件下,能够取得最优的服务总时延.
5. 结 论
本文提出了一种2阶段的服务质量优化方案以解决移动边缘计算架构下的服务安全部署问题. 在第1阶段,本文考虑了服务的安全性和边缘服务器的负载均衡问题,对服务部署问题进行建模,提出了一种基于K-Means的服务实时解耦方案,并设计了一种基于MOEA/D的服务部署策略;在第2阶段,本文考虑了边缘设备的移动性,设计了一种设备移动感知的服务部署策略,优化了移动边缘计算架构下的服务质量. 实验结果表明,与多种基准方法相比,在保证系统安全以及服务器负载均衡的前提下,本文所提出的面向集中式服务部署策略能够使服务请求的响应时间降低36%,所提出的动态部署策略能进一步降低13%的服务响应时间.
作者贡献声明:李丽颖提出了算法思路并撰写论文;张润泽负责完成实验;魏同权提出指导意见并修改论文.
-
-
[1] 施巍松,孙辉,曹杰,等. 边缘计算:万物互联时代新型计算模型[J]. 计算机研究与发展,2017,54(5):907−924 doi: 10.7544/issn1000-1239.2017.20160941 Shi Weisong, Sun Hui, Cao Jie, et al. Edge computing—An emerging computing model for the Internet of everything era[J]. Journal of Computer Research and Development, 2017, 54(5): 907−924 (in Chinese) doi: 10.7544/issn1000-1239.2017.20160941
[2] Cleber S, Leandro A, Flávia D, et al. Increasing the availability of IoT applications with reactive microservices[J]. Service Oriented Computing and Applications, 2021, 15(2): 109−126 doi: 10.1007/s11761-020-00308-8
[3] 钱志鸿,王义君. 物联网技术与应用研究[J]. 电子学报,2012,40(5):1023−1029 doi: 10.3969/j.issn.0372-2112.2012.05.026 Qian Zhihong, Wang Yijun. IoT technology and application[J]. Acta Electronica Sinica, 2012, 40(5): 1023−1029 (in Chinese) doi: 10.3969/j.issn.0372-2112.2012.05.026
[4] Xiao Yang, Li Haizhong, Li Bo. Bandwidth sharing schemes for multimedia traffic in the IEEE 802.11e contention-based WLANs[J]. IEEE Transactions on Mobile Computing, 2007, 6(7): 815−831 doi: 10.1109/TMC.2007.1054
[5] Auer F, Lenarduzzi V, Felderer M, et al. From monolithic systems to Microservices: An assessment framework[J]. Information and Software Technology, 2021, 137: 106600
[6] Arisholm E, Briand L C, Foyen A. Dynamic coupling measurement for object-oriented software[J]. IEEE Transactions on Software Engineering, 2004, 30(8): 491−506 doi: 10.1109/TSE.2004.41
[7] Poshyvanyk D, Marcus A, Ferenc R, et al. Using information retrieval based coupling measures for impact analysis[J]. Empirical Software Engineering, 2009, 14(1): 5−32 doi: 10.1007/s10664-008-9088-2
[8] Wang Xiaofei, Han Yiwen, Leung V C M, et al. Convergence of edge computing and deep learning: A comprehensive survey[J]. IEEE Communications Surveys & Tutorials, 2020, 22(2): 869−904
[9] Shi Weisong, Cao Jie, Zhang Quan, et al. Edge computing: Vision and challenges[J]. IEEE Internet of Things Journal, 2016, 3(5): 637−646 doi: 10.1109/JIOT.2016.2579198
[10] Yin Hao, Zhang Xu, Liu Hongqiang Harry, et al. Edge provisioning with flexible server placement[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 28(4): 1031−1045
[11] Farhadi V, Mehmeti F, He Ting, et al. Service placement and request scheduling for data-intensive applications in edge clouds[J]. IEEE/ACM Transactions on Networking, 2021, 29(2): 779−792 doi: 10.1109/TNET.2020.3048613
[12] Dong Yunmeng, Xu Gaochao, Ding Yan, et al. A ‘joint-me’ task deployment strategy for load balancing in edge computing[J]. IEEE Access, 2019, 7: 99658−99669 doi: 10.1109/ACCESS.2019.2928582
[13] 樊琦,李卓,陈昕. 基于边缘计算的分支神经网络模型推断延迟优化[J]. 计算机应用,2020,40(2):342−346 doi: 10.11772/j.issn.1001-9081.2019081406 Fan Qi, Li Zhuo, Chen Xin. Inference delay optimization of branchy neural network model based on edge computing[J]. Journal of Computer Applications, 2020, 40(2): 342−346 (in Chinese) doi: 10.11772/j.issn.1001-9081.2019081406
[14] Ahmed E, Rehmani M H. Mobile edge computing: Opportunities, solutions, and challenges[J]. Future Generation Computer Systems, 2017, 70: 59−63 doi: 10.1016/j.future.2016.09.015
[15] Chen Xu, Shi Qian, Yang Lei, et al. ThriftyEdge: Resource-efficient edge computing for intelligent IoT applications[J]. IEEE Network, 2018, 32(1): 61−65 doi: 10.1109/MNET.2018.1700145
[16] Deng Tao, You Lei, Fan Pingzhi, et al. Device caching for network offloading: Delay minimization with presence of user mobility[J]. IEEE Wireless Communications Letters, 2018, 7(4): 558−561 doi: 10.1109/LWC.2018.2795617
[17] Wang Shiqiang, Urgaonkar R, Zafer M, et al. Dynamic service migration in mobile edge-clouds[C] //Proc of IFIP Networking Conf. Piscataway, NJ: IEEE, 2015: 1−9
[18] Taleb T, Ksentini A. An analytical model for follow me cloud[C]// Proc of the 2013 IEEE Global Communications Conf (GLOBECOM). Piscataway, NJ: IEEE, 2013: 1291−1296
[19] Cao Kun, Li Liying, Cui Yangguang, et al. Exploring placement of heterogeneous edge servers for response time minimization in mobile edge-cloud computing[J]. IEEE Transactions on Industrial Informatics, 2020, 17(1): 494−503
[20] Jiang Wei, Jiang Ke, Zhang Xia, et al. Energy aware real-time scheduling policy with guaranteed security protection[C]// Proc of the 19th Asia and South Pacific Design Automation Conf (ASP-DAC). Piscataway, NJ: IEEE, 2014: 317−322
[21] Wang Shangguang, Guo Yan, Zhang Ning, et al. Delay-aware microservice coordination in mobile edge computing: A reinforcement learning approach[J]. IEEE Transactions on Mobile Computing, 2019, 20(3): 939−951
[22] Wei Xiaohui, Li Zijian, Liu Yuanyuan, et al. SDLSC-TA: Subarea division learning based task allocation in sparse mobile crowdsensing[J]. IEEE Transactions on Emerging Topics in Computing, 2020, 9(3): 1344−1358
[23] Ouyang Tao, Zhou Zhi, Chen Xu. Follow me at the edge: Mobility-aware dynamic service placement for mobile edge computing[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(10): 2333−2345 doi: 10.1109/JSAC.2018.2869954
[24] Chaufournier L, Sharma P, Le F, et al. Fast transparent virtual machine migration in distributed edge clouds[C/OL]//Proc of the 2nd ACM/IEEE Symp on Edge Computing. Piscataway, NJ: IEEE, 2017 [2023-03-21].https://dl.acm.org/doi/10.1145/3132211.3134445
[25] Ma Lele, Yi Shanhe, Li Qun. Efficient service handoff across edge servers via docker container migration[C/OL]//Proc of the 2nd ACM/IEEE Symp on Edge Computing. Piscataway, NJ: IEEE, 2017 [2023-03-23].https://dl.acm.org/doi/10.1145/3132211.3134460
[26] Pierdomenico P. Converse Lyapunov theorems for discrete-time switching systems with given switches digraphs[J]. IEEE Transactions on Automatic Control, 2019, 64(6): 2502−2508 doi: 10.1109/TAC.2018.2867166
[27] Chen Minghua, Liew C S, Shao Ziyu, et al. Markov approximation for combinatorial network optimization[J]. IEEE Transactions on Information Theory, 2013, 59(10): 6301−6327 doi: 10.1109/TIT.2013.2268923
[28] Meek C, Thiesson B, Heckerman D. The learning curve method applied to clustering[C] // Proc of the 8th Int Workshop on Artificial Intelligence and Statistics. New York: PMLR, 2001: 196−202
[29] Zhao Chenhong, Zhang Shanhan, Liu Qingfeng, et al. Independent tasks scheduling based on genetic algorithm in cloud computing[C]//Proc of the 5th Int Conf on Wireless Communications, Networking and Mobile Computing. Piscataway, NJ: IEEE, 2009: 1−4
[30] Kennedy J, Eberhart R. Particle swarm optimization[C]//Proc of the Int Conf on Neural Networks. Piscataway, NJ: IEEE, 1995: 1942−1948
[31] Radenkovic M, Grundy A. Efficient and adaptive congestion control for heterogeneous delay-tolerant networks[J]. Ad Hoc Networks, 2012, 10(7): 1322−1345 doi: 10.1016/j.adhoc.2012.03.013
-
期刊类型引用(4)
1. 贾乃征,薛灿,杨骝,王智. 基于融合集成学习的鲁棒近超声室内定位方法. 计算机研究与发展. 2025(02): 488-502 . 本站查看
2. 马安佳. 数智化背景下城市交通规划研究. 办公自动化. 2024(10): 8-10 . 百度学术
3. 陈文海,黄智华,周雅欣. 基于边缘计算的继电保护海量数据轻量级传输优化方法. 电气技术与经济. 2024(06): 294-296 . 百度学术
4. 冯国富,刘桂,王娟. 边-云计算中一种结合服务产生的服务部署策略. 中南大学学报(自然科学版). 2024(07): 2578-2587 . 百度学术
其他类型引用(2)