基于移动边缘计算环境下的服务缓存和任务调度联合优化算法

杜建华，王立俊，谢寒生,赵卓宁, 王双双

(1.海南省气象信息中心，海口 570203；2.成都信息工程大学，成都 610225；3.海南省南海气象防灾减灾重点实验室，海口 570203)

0 引言

物联网以及无线通信技术的推陈出新，使得各种移动相关应用呈爆炸式发展势头。大量的计算密集和时间敏感型应用，在通信资源和计算资源方面对网络基础设施提出了更高的要求。而传统云计算框架中，网络带宽因终端设备与云中心服务器之间要处理大量数据上传、处理和结果的回传，承受巨大的压力。为提高资源效率和用户体验，移动边缘计算(MEC,mobile edge computing)框架能够给予移动终端以任务卸载支持，使得云计算服务从集中云扩展至网络边缘，在近端提供资源的同时有效降低了服务延迟。需要注意的是，边缘设备在通信、计算、存储资源等方面具有一定的局限性，尤其是当终端用户的任务需求激增时。大量终端用户向边缘设备卸载任务，会造成边缘设备资源紧张、负载过重和任务处理时延的增加，影响任务处理的时效和用户体验。此外，各边缘设备间的负载不均衡现象会进一步加剧，部分闲置的服务资源无法被充分利用。

为了给终端用户提供更准确、更精确粒度的服务，一些基于移动边缘计算的服务缓存策略被提出。文献[10]对支持MEC的密集蜂窝网络中的动态服务缓存策略进行了研究，提出了一种高效的基于联合优化动态服务缓存和任务卸载的在线算法。文献[11]针对MEC系统在服务异构性、空间需求耦合和分散协调等方面存在的问题，基于MEC的密集小区网络中的协作服务部署方法进行了分析，提出了一种高效的分布式算法。文献[12]研究了具有多维约束的服务部署和请求路由的联合优化问题，提出了一种使用随机取整实现接近最优性能的算法。为实现更可行的边缘资源分配，文献[13]提出了齐次条件下的常数因子近似算法和一般条件下的启发式算法来解决缓存服务放置和任务请求调度问题。文献[14]引入卸载成本模型来捕获用户能耗、服务缓存成本和云使用成本，利用局部搜索技术设计了一个多项式时间迭代算法COSTA。为了充分利用边缘节点的存储和计算能力，文献[15]针对边缘节点之间的协作服务缓存和工作负载调度问题建立数学模型，并设计了迭代算法来解决上述混合整数非线性规划问题。从上述研究工作可以看到，边缘设备之间的协作能够更高效地利用各设备的通信、计算和存储资源。计算任务卸载决策需要对众多终端用户的服务响应进行合理的安排，同时尽可能地避免边缘设备间的负载不均衡的情况。任务卸载和服务缓存之间相互耦合，进行联合优化能够在任务执行时延限制的条件下，有效保障用户的服务质量。

1 问题描述

1.1 网络模型

考虑如图1所示的移动边缘计算网络，

K

个基站配备了具有计算和存储功能的边缘服务器，

N

个移动用户产生任务后，指定服务器或远程云数据中心来执行。考虑到边缘服务器的密集部署以及覆盖范围会出现重叠，对于移动用户

n

可能位于多个不同基站的控制区域，用

K

表示该用户所能访问的基站集合。由于任务的执行需要用户的输入及计算资源，

C

和

F

分别表示基站

k

的最大存量容量和最大周期频率。系统能够处理的任务种类为

S

，且任意移动用户在一个时间段提交一个任务请求。Ø,表示用户

n

的任务请求

s

，计算任务模型用三元组Ø,={

f

,)，

d

,,

T

,}来描述，其中，

f

,为任务所需的计算资源，

d

,为任务的输入数据量，

T

,为任务所允许的时间延迟。

图1 网络模型

当移动用户的服务请求被迁移到邻近的基站组上，如果该基站已缓存移动用户请求的服务并具有足够的计算能力和带宽资源以供移动用户使用，则直接进行处理。如果邻近的基站组中没有缓存所请求的服务，则接收到服务请求的边缘设备将请求其他缓存相应的服务的边缘设备进行协同工作，该移动用户的服务请求将被迁移至协助处理的边缘设备。若所有的边缘设备都无法进行响应，则直接将任务上传至远端中心云来进行处理。

1.2 服务缓存模型

移动用户卸载的计算任务与边缘设备缓存的服务相关联，任务能否得以执行取决于边缘设备上是否缓存了对应的服务。由于边缘设备上的缓存容量有限，无法缓存全部的服务。因此，边缘设备需要定期地与覆盖范围内的移动用户进行交互，以确定将哪些服务置于其缓存中。对于时隙

t

，用

Θ

={

Θ

,|

k

∈

K

}表示时所有边缘设备的服务缓存策略，其中：

Θ

,={

Θ

,(

s

)|

s

∈

S

}为为时隙

t

边缘设备

k

中所缓存的服务集合。

Θ

,(

s

)是一个二元变量，取值为1表示边缘设备

k

在时隙

t

时缓存了服务

s

，取值为0则表示未缓存服务

s

。边缘设备所缓存的服务集合不能超过其缓存容量上限，因此，服务缓存约束条件可以表示为：∑∈

θ

(

s

)≤

C

,∀

k

∈

K

(1)

1.3 任务卸载策略

相比于移动用户，边缘设备的计算、缓存等资源比较充足，移动用户将任务卸载至相关联的边缘设备进行处理，能有效弥补移动终端资源不足、能耗受限等问题。任务卸载处理的前提条件是边缘设备是否对相应的服务事先予以缓存。由于边缘设备资源有限，若因缓存不足没有对用户请求的服务进行缓存，它会先寻求其他缓存相关服务的边缘设备进行协作处理。如果其他边缘设备也无法处理，则再将计算任务卸载至远端云服务中心处。因此，移动用户产生的计算任务的卸载优先顺序依次为：关联的边缘设备、协作的边缘设备以及远端云服务中心。边缘设备间通过核心网互联，边缘设备间的传输速率可以看成是定值，用

R

表示。若移动用户的任务请求无法通过边缘设备处理，而需要在远端云服务中心处执行时，将由关联的边缘设备通过核心网和回程链路传输至远端，用恒定值

t

来表示这部分的传输时延。另外，由于处理后的数据量一般远小于任务的输入，且移动用户端的下载速率远高于其上传速率，本文不考虑边缘设备或云数据中心处理后的数据下载延时。假设移动用户上传任务数据为恒定功率

P

，时隙

t

内的信道状态为

H

(

t

)={

h

,(

t

)|

k

∈

K

,

n

∈

N

}，其中

h

,(

t

)表示移动用户

n

到边缘服务器

k

之间的信道增益。

B

(

t

)={

b

,(

t

)|

s

∈

S

,

n

∈

N

}表示该时隙带宽资源分配，

b

,(

t

)∈[0,1]表示接入边缘设备为卸载移动用户

n

的

s

类任务所分配的带宽资源比例。考虑到边缘设备带宽资源限制，

b

,(

t

)需满足约束条件：∑∈∑∈

δ

,(

t

,

k

)

b

,≤1,∀

k

∈

K

(2)

其中：

δ

,(

t

,

k

)为二元变量，取值1表示在时隙

t

中移动用户

n

的任务类型

s

将被卸载到边缘服务器

k

进行处理，反之取值为0。根据接入控制和带宽资源分配决策，移动用户

n

在时隙

t

用于任务卸载时的数据传输速率可表示为：

R

,(

t

)=

(3)

其中:

N

为噪声功率谱密度，

B

表示边缘设备

k

的信道带宽，|

M

|表示边缘设备

k

关联的移动用户个数。

1.3.1 关联的边缘设备执行任务

若移动设备产生的任务卸载到自身关联的边缘设备处执行，则执行时延包括：移动用户

n

上传数据到边缘设备所需的传输时延以及边缘设备执行任务所需的计算时延。

(4)

其中:

F

,表示边缘设备

k

分配给任务Ø,的计算量。

1.3.2 协作的边缘设备执行任务

若移动设备相关联的边缘设备处没有缓存任务相应的服务，边缘设备会寻求其他能够予以协作的边缘设备。这种情况下，时间延迟包括：移动用户上传数据到相邻边缘设备所需的传输时延，边缘设备之间传输数据所需的传输时延以及进行协作的边缘设备执行任务所需的计算时延。

t

,(

k

,

l

)=

(5)

其中:

dis

(

k

,

l

)表示边缘设备

k

和

l

之间的链路长度，

F

,表示边缘设备

l

分配给任务Ø,的计算量。

1.3.3 远端云执行任务

若关联的边缘设备和其他边缘设备都没有缓存移动用户卸载的计算任务所对应的服务，关联的边缘设备需要将任务发送至远端云服务中心处执行。考虑到远端云计算和存储资源丰富，故不考虑其计算所需时间开销。此时所需的时延包括：移动用户至边缘设备间的数据传输时延以及边缘设备至远端云服务中心间的数据传输时延。因此，任务被处理所需要的时间开销为：

(6)

1.4 目标函数

每个移动用户的计算任务选择合适的关联边缘设备作为任务卸载目标，关联的边缘设备若提前缓存了该任务执行所需的服务则分配计算资源予以执行，否则将向其他边缘设备提出协作请求或发送至远端云服务中心进行处理。本文目标为通过对任务卸载与缓存决策进行合理调度，优化通信和计算资源分配，实现所有移动用户的任务的平均处理时间延迟的最小化。因此，优化目标表示为：

(7)

∑∈

θ

,(

s

)≤

C

,∀

k

∈

K

(8)

w

+

w

+

w

=1,∀

w

,

w

,

w

∈{0,1}

(9)

F

,>0,∀

n

∈

N

,∀

k

∈

K

(10)

∑∈

F

,≤

F

,∃

w

=1,∀

k

∈

K

(11)

∑∈

F

l

,

n

)≤

F

,∃

w

=1,∀

l

∈

K

(12)

[

t

,(

k

)

t

,(

k

,

l

)

t

,(

k

,

z

) ]·[

w

w

w

]≤

t

,,∀

k

∈

K

(13)

式(8)的约束条件为边缘设备缓存的服务不能超过其缓存容量。式(9)的约束条件为移动用户的计算任务的可以为关联的边缘设备、协作的边缘设备或远端云服务中心。式(10)表示边缘设备为移动用户的计算任务分配的计算量为正。式(11)表示边缘设备为用户任务分配的计算资源不能超过其计算资源总量。式(12)表示协作的边缘设备同样为用户分配的计算资源不能超过其资源总量限制。式(13)约束条件为所有任务的处理时间需满足其时延限制。

2 算法设计

上述任务卸载与缓存决策调度问题本质上为多目标组合优化问题。算法目标是在满足边缘设备的缓存容量、计算资源分配的约束条件下，将移动用户的任务请求分配至关联的边缘设备，使得任务处理的耗费时间最少，实现对用户的及时响应。对于此类问题，启发式算法能够在一定的范围内求解次优解或以一定的概率求其最优解，其中，粒子群优化(PSO,particle swarm optimization)算法具有参数设置少、全局搜索能力强的优点，其并行性和分布式的特点适合用来求解上述任务卸载与缓存决策调度问题。首先，需要对粒子进行编码，使缓存策略、任务卸载与粒子的位置、速度等联系起来。

2.1 粒子编码

假设粒子群规模为U，所有移动用户的任务集合。

Φ

={Ø,Ø,…,Ø}。粒子个体的编码维度与任务集合元素数量一致，并采用整数编码。每个粒子元素的取值范围为[0,

K

]，其中0表示移动用户的任务在远端云服务中心被处理，1～

K

则表示某移动用户的任务卸载至相应编号的边缘设备进行处理。每个粒子的卸载决策向量

X

={

x

,

x

,…,

x

}表示所有任务最优的执行位置。初始化时，

xi

在0到

K

之间随机取值，且需要保证其对应的服务请求和需要的计算能力满足对应的边缘设备的资源限制条件。粒子的速度为调整当前任务分配至其他边缘设备的趋势快慢，用

V

={Ø,Ø,…,Ø}来表示。

pBest

={

p

1,

p

2,…,

p

N

}为第

i

个粒子的个体极值，

pBest

={

p

1,

p

2,…,

p

}为全局最优粒子。

2.2 适应度函数

算法的优化目标为最优的适应度。本文建立的模型优化目标是在满足边缘设备的缓存容量、计算资源分配的约束条件下，将移动用户的任务请求分配至关联的边缘设备，使得任务处理的耗费时间最少。因此，可以将适应度函数定义为:

(14)

可见，所有移动用户的任务的平均处理时间延迟值越大，优化性能越差；反之则优化性能越强。

2.3 反向粒子的选择

粒子群优化在算法迭代到一定程度后，会因为种群多样性的逐渐收窄而可能陷入局部最优。为了提高求解精度和获得比较好的稳定性，本文将反向学习(OBL,oposition-based learning)的理论引入对算法进行改进。其主要思想为：在求解过程中，根据每个粒子个体对应的反向粒子，将其假定为可能得到更接近最优解的粒子个体，通过粒子个体以及其反向个体来提高种群的多样性，再从中择优选择作为后续迭代的条件。

(15)

2.4 速度更新

考虑到粒子一旦陷入局部极值，则其速度无法进行更新，且过低的速度会造成粒子不易从局部极值范围内脱离。本文采取极值扰动的方法拓展粒子的搜索区间，对学习因子采用非线性变化的策略来调整粒子的社会学习和自我学习能力。粒子的速度更新公式修改为：

(16)

c

=1.3+1.2cos(π

u/u

)，

c

=2.0-1.2cos(π

u/u

)，

c

、

c

为学习因子，

ψ

(·)为高斯分布函数，

δ

取搜索空间长度的0

.

2倍，

u

max为最大迭代次数。

3 实验结果与分析

为了验证本文提出的移动边缘计算环境下的数据缓存和任务调度联合优化模型的性能，采用CloudSim进行了仿真实验。实验参数设置为：终端用户的传输功率为0.5 W，每个边缘服务器的信道带宽、存储容量和计算容量分别被设置为 10 MHz、200 GB和 25 GHz，噪声功率100 dBm，服务类型总数为10。任务的输入数据大小为0.5～2 Mbits，所需的计算周期为100～1 000 CPU cycles。边缘设备的覆盖范围为200 m，边缘设备之间的直线距离为350 m。

首先，对算法的收敛性进行评估。图2为本文提出的算法与传统粒子群算法对上述服务缓存和任务调度联合优化问题的求解情况对比。从实验结果可以看到，在前15次迭代过程中收敛较快，迭代30次后得到的效用函数值趋于平稳并找到最优解。这说明本文算法在全局优化能力方面具有优势，相比传统的粒子群优化算法，能够得到更小的效用函数值。

图2 算法的收敛性对比

图3 缓存空间利用率对比

对比实验选取了远程云处理策略、随机策略、贪心算法、以及本文提出的算法在服务缓存和任务调度联合优化问题的应用效果进行了比较。本文算法中的参数初始化为：种群规模初始化为100，最大迭代次数为50。图3为边缘设备缓存空间利用率对比。所利用的服务器缓存空间越大，移动用户任务的响应时间越短。由于远程云处理策略中所有移动用户的任务都是直接由边缘设备转发至云数据中心进行处理，因此对应的MEC服务器不缓存任何任务，会造成较大的传输延迟。随着移动用户数量的增加，任务数量越来越多，贪心算法和本文算法在缓存空间利用率上提升更快，这有利于实现卸载到边缘设备的任务能直接进行处理，减少任务的响应时间。

图4为边缘设备的负载均衡情况对比。从图4可以看出，在不同的用户规模条件下，本文算法和贪心算法能获得更好的负载均衡度。在远程云处理策略中，边缘设备负责将用户请求转发至远端云数据中心，其负载均衡度取决于覆盖范围内的用户数量。随机策略有时会获得较好的负载均衡度，但整体上不稳定。贪心算法在用户数量较大时负载均衡度偏大，说明其对边缘设备的利用不够均衡。

图4 负载均衡情况对比

图5 执行时间对比

图5为执行时间的对比。可以看到使用随机策略，边缘设备的缓存任务和对移动用户的任务请求处理都是随机选择的，获得的目标值不稳定，且随机卸载策略的总延迟增长速度越快，相比贪心算法和本文算法在执行时间上的优化差距较大。在任务规模比较小的情况下，本文算法相比贪心算法的最优调度方案所需的总执行时间相差不明显。但是随着任务规模的增加，可以看到本文算法能够明显表现出在执行时间上的优势，当移动用户数在400～800时，本文提出的算法的总执行时间比贪心策略少14.5%～32.1%。上述结果表明本文调度方案能够适应大规模任务调度，在较短的时间内完成用户任务。

4 结束语

针对任务卸载与服务缓存决策问题，本文建立数学模型并提出一种联合优化算法来求解任务执行时延约束条件下的服务缓存决策最优解。通过仿真实验，分析了边缘设备的缓存空间利用率、负载均衡、执行时间等指标下的效果。实验结果验证了本文提出的算法的有效性，与其他策略相比在提高卸载效率、减少任务完成时间和大规模任务调度的条件下都获得较好的性能。下一步工作，我们将继续探索和对服务缓存算法和卸载策略进行优化、完善。