边缘计算环境中的数据缓存优化

摘要

随着移动设备在人们日常生活中的使用迅速增加，近年来移动数据流量呈爆炸式增长。在将边缘服务器部署在移动用户周围的边缘计算环境中，将热门数据缓存在边缘服务器上可以确保移动用户快速访问这些数据，并减少移动用户与集中式云之间的数据流量。现有研究主要关注降低网络延迟和提高移动设备能源效率的数据缓存问题。本文从服务提供商的角度出发，研究边缘计算环境中的数据缓存问题，其目标是最大化缓存自身数据带来的收入。该问题较为复杂，因为数据缓存会带来收益，但同时也会产生成本，通常需要在两者之间进行权衡。本文将数据缓存问题建模为一个整数规划问题，在满足数据访问延迟约束的同时，最大化服务提供商的收入。我们在一个包含边缘服务器和移动用户位置的真实世界数据集上进行了大量实验，结果表明，我们的方法显著优于基线方法。

关键词 —数据优化, 边缘计算, 数据流行度, Page‐Hinckley检验(PHT), 整数问题(IP)

I. 引言

在过去十年中，随着移动设备在人们日常生活中使用量的迅速增加，互联网上的移动数据流量大幅增长[1]。传统的云计算架构越来越难以支持具有大量、多样化且高速增长数据的移动服务或应用。解决这一挑战的一个有前景的方案是边缘计算，这是一种以超低延迟为特征的分布式计算范式[2],[3]。该范式通过在移动用户附近的基站或接入点部署通用边缘服务器来实现。这些边缘服务器为服务提供商提供缓存、计算和通信等服务。在边缘服务器上进行数据缓存可以减少移动用户访问热门数据的延迟以及移动用户与集中式云之间的数据流量[4],[5]。

计算中的数据缓存是一种通用技术，允许将数据副本存储在某个位置，以便在将来请求时快速检索数据。数据缓存已应用于各种领域，如自组织网络[6],数据库[7], Web服务器[8],多处理器[9]和存储[10]，以提高信息检索的效率并减少数据访问延迟。如何缓存数据，特别是热门数据，以优化这些研究领域的系统性能[10]。

边缘计算中的数据缓存问题是一个活跃的研究课题，已被广泛研究以实现不同的目标。例如，[11],[12]中提出的工作旨在基于数据流行度最小化数据检索延迟，而[13],[14]中的工作则利用用户请求和边缘服务器位置来实现相同目标。[15]的作者致力于设计一种最优的缓存空间分配方案，以最大化缓存性能和能源效率。这些研究均从边缘服务器管理的角度考虑缓存优化问题，重点关降低移动用户的延迟并提高能源效率。[16]的作者提出，在基站进行内容缓存会产生两种成本，即数据存储成本和用户转向其他服务提供商所带来的用户流失成本，其目标是最小化服务提供商支付的总成本。

在本研究中，我们从一个不同的角度考虑了基站的数据缓存问题。我们的目标是在满足数据访问延迟约束的同时，最大化服务提供商的收入。服务提供商在边缘服务器上使用数据缓存服务所获得的收入包含两个主要组成部分。

第一部分是缓存被大量移动用户请求的热门数据所带来的收益。第二部分是存储成本和传输成本，其中服务提供商需要向蜂窝网络运营商支付费用，以将其数据缓存在边缘服务器上。在数据缓存的收益与成本之间存在权衡。服务提供商需要确定在其边缘服务器上缓存数据的位置和方式，以最大化其收入，即收益减去成本。本文将边缘计算环境中的数据缓存问题建模为一个优化问题，在满足数据检索延迟约束的同时，最大化服务提供商的整体收入。本文的主要贡献如下：
- 我们提出了一种模型，该模型基于数据缓存的收益和成本，并考虑数据的流行度，来表示服务提供商的收入。
- 我们提出了一种扩展Page‐Hinckley检验(PHT)的方法，用于检测数据是否流行。
- 我们将边缘计算环境中的数据缓存问题建模为一个整数规划问题，旨在最大化服务提供商获得的总体收入。
- 我们证明了该问题是NP‐完全的。
- 我们在边缘计算环境中不同的数据缓存场景下进行实验，使用边缘服务器和移动用户的真实世界位置进行模拟，并将我们的方法与两种基线方法进行了比较。

本文的其余部分组织如下：第2节介绍了边缘数据缓存架构。第3节基于收益和成本描述了服务提供商的收入模型。第4节提出了数据缓存问题的优化模型，证明其为NP完全问题，并使用整数规划技术求解该问题。第4节通过实验评估了所提出的方法。第5节回顾了相关文献。最后，第6节对本文进行了总结。

II. 边缘数据缓存架构

云计算极大地促进了大规模数据处理，其中大量数据被传输到集中式云中进行处理。然而，随着边缘移动设备产生的数据迅速增长，数据传输正成为基于云的计算范式性能的瓶颈。近年来，边缘计算作为一种新范式应运而生，它允许在云端边缘生成的数据在边缘进行处理。该模式允许将不同的服务部署并提供在靠近移动设备的边缘服务器上。通过这种方式，可以更快地响应移动用户的需求。这些边缘服务器配备了存储，构成了缓存移动用户访问的热门数据的完美基础设施。

云。通过在靠近移动用户的边缘服务器上存储和更新热门数据，显著降低了移动用户访问热门数据的延迟。图1展示了通用三层边缘数据缓存架构。

如图1所示，边缘数据缓存架构由服务提供层、边缘服务器层和移动用户层[13]组成。该架构的三个主要组成部分如下所述：
(1) 服务提供层 ：在此层中，云中的服务器上的服务提供层提供各种类型的数据，以响应移动用户对数据访问的请求。
(2) 边缘服务器层 ：该层中的边缘服务器部署在基站上。它们为附近的移动用户提供热门数据的缓存和分发，实现超低延迟。为了识别需要缓存的热门数据，边缘服务器可以聚合对相似数据的请求，并计算这些请求的到达率。
(3) 用户层 ：在此层中，移动用户可以从附近的边缘服务器获取流行数据。移动用户的地理位置通过无线通信与其周围的边缘服务器共享。如果数据已缓存在某个边缘服务器上，移动用户即可直接从该边缘服务器立即检索数据，而无需从集中式云获取。

基于该架构，位于服务提供商和移动用户之间的边缘服务器提供数据缓存服务。从服务提供商的角度来看，首先要解决的问题是缓存哪些数据。如果在特定区域内，大量移动用户在短时间内请求某份数据，服务提供商将显著受益于在该区域部署的边缘服务器上缓存此数据。这将使该区域内的移动用户能够从这些边缘服务器以超低延迟访问该数据。由于请求该数据的移动用户可能分布在不同的边缘服务器周围，因此可能需要在多个边缘服务器上存储该数据，以满足这些移动用户的请求。在特定区域内的所有边缘服务器上缓存该数据，将确保该区域内所有移动用户均能以超低延迟访问数据。然而，这可能会导致过高的数据存储成本和数据传输成本。如何在这两项成本之间进行权衡，以最大化服务提供商的收入，是一个关键且具有挑战性的问题，将在下一节中将其建模为一个优化问题。

III. 边缘数据缓存方法

我们考虑一个特定区域内的边缘计算网络，该网络由一组相互连接的具备缓存能力的边缘服务器组成，表示为 K={1, 2,…, k,…, K}。令0表示云中服务提供商服务器的索引。我们有 M={1, 2,…, j,…, M}数据大小为 S={s1, s2,…, sj,…, sM}，请求 S的移动用户数量记为 ν={ν1, ν2,…, νj,…, νM}。设 N表示移动用户的数量。

随着数据存储价格的显著下降，我们假设每个边缘服务器的缓存容量是无限的。未来的工作中将研究具有缓存容量约束的更复杂的数据缓存场景。但这不会从根本上改变我们的优化模型，因为缓存容量可以作为约束条件纳入我们的优化模型中。设 fkj表示在第 k个边缘服务器上缓存第 j份数据所产生的单位成本。设 hj ik表示第 i个移动用户从第 k个（k> 0）边缘服务器获取第 j份数据所产生的单位传输成本，或第 i个移动用户从云（即 k= 0）获取第j份数据所产生的单位传输成本。设 Pkj表示第 j份数据在第 k个边缘服务器覆盖区域内的流行度，threshold表示用于判断一份数据是否值得在边缘服务器上进行缓存的流行度阈值。因此，并非所有数据都会被缓存在边缘服务器上，只有那些根据该阈值被认为足够流行的数据才会被缓存。在实际应用中，该阈值需领域特定地并经验性地设定。它决定哪些数据需要缓存，但不决定如何缓存这些数据。因此，它不会影响我们方法的有效性或效率。

A. 数据缓存效益模型

本文中，数据是否在边缘服务器上进行缓存，取决于该数据的流行度。数据的流行度取决于特定时间段内请求该数据的移动用户数量。通常情况下，如果请求数量随时间迅速增加，则该数据的流行度较高。目前有许多方法可用于计算项目[17]的流行度。

符号	描述
K	边缘服务器的集合
M	待缓存的数据集
Sj	数据大小 Mj
N	移动用户的集合
νT j	移动用户对数据 Mj的请求数量
UT j	在时间 T 数据 Mj 请求的累计变化 at T
δ	允许的变化幅度
hT i	UT i 的最小值
HT i	UT i 的最大值
PHT i	PHT测试值的下限
MPHT i	PHT测试值的上限
B	每个移动用户请求的收益
Pkj	第 j个数据的流行度 k号边缘服务器的覆盖区域
threshold	数据流行度的阈值
fkj	在 j号边缘服务器上缓存 j号数据所产生的单位成本
hj ik	第 k个边缘服务器 第 i个用户检索数据所产生的单位传输成本 从第 k个（k> 0）获取第 j个数据 边缘服务器

这些不同的方法可以与数据缓存方法灵活结合。在本文中，我们采用PHT[18]，这一高效且广泛使用的数据流行度计算方法。它分析数据请求数量的动态变化，通过计算累积变化值来得出当前值与窗口内平均值之间的差异：

$$
U T i = \sum_{t=0}^{T} (\nu t i - \nu T - \delta)
$$

其中 $\nu t i$ 表示在时间 $Tt$, $\nu T = \frac{1}{T} \sum \nu t i$ 表示 $\nu t i$ 的 $\delta$ 表示 $t=0$ 变化的允许范围。

为了评估数据流行度的上升情况，定义了UT i的最小值和 PHT的测试值：

$$
hTi= min(UT i), 0 ≤ t ≤ T,
$$

$$
PHT i= UT i − hTi,
$$

如果 $PHT i > threshold$，则认为数据 Mi是流行的，并应缓存在边缘服务器上。然而，数据流行度是数据的一种局部且短暂的属性。为了能够检测出某项数据是否变得不流行，我们扩展了PHT测试，使其能够判断两个方向（即上升和下降）的累积变化。 UT i的最大值以及 PHT测试的下限测试值定义如下：

$$
HT i= max(UT i), 0 ≤ t ≤ T,
$$

$$
MPHT i= HT i − UT i,
$$

如果 $MPHT i > ε$，则认为该数据不热门。我们为PHT测试定义了时间窗口的大小为 W。

数据流行度定义为：

$$
Pi={\nu t | t ≥ 0, 1 ≤ i ≤ M},
$$

缓存数据Mj的收益是：

$$
Benefitj= B ∗ Pj.
$$

B. 缓存策略制定

本节将数据缓存问题建模为整数规划（IP算法）问题，同时考虑了存储成本和传输成本，并证明了该问题的NP完全性。

首先，我们引入以下变量：

$$
Ykj =
\begin{cases}
1 & \text{if the } j \text{th data is cached at the } k \text{th edge server,} \
0 & \text{otherwise.}
\end{cases}
$$

$$
Zj ik =
\begin{cases}
1 & \text{if the } i \text{th user retrieves } j \text{th data from the } k \text{th edge server,} \
0 & \text{otherwise.}
\end{cases}
$$

$$
dik =
\begin{cases}
1 & \text{if the } i \text{th the user is in the span field of the } k \text{th edge server,} \
0 & \text{otherwise.}
\end{cases}
$$

$$
UP i j = Sgn\left[\sum_{i=1}^{K} d ik \cdot \max\left(\frac{P i j}{threshold} - 1, 0\right)\right]=
\begin{cases}
1 & \text{if the } j \text{th data is popular where the } i \text{th mobile user is located} \
0 & \text{if the } j \text{th data is not popular where the } i \text{th mobile user is located} \
-1 & \text{not existed}
\end{cases}
$$

数据缓存问题的IP算法优化模型建模如下：

$$
\max Benefitj -\left(\sum_{k=1}^{K} \sum_{j=1}^{M} f_j^k Y_j^k S_j + \sum_{k=1}^{K} \sum_{j=1}^{M} \sum_{i=1}^{N} h_j^{ik} S_j Z_j^{ik}\right)
$$

受限于：

$$
\begin{cases}
Ykj \le \frac{Pij}{threshold} \
\sum_{k=1}^{K} dik \cdot Zj ik \ge UPij \
Zj ik \le Ykj
\end{cases}
$$

定理1 ：边缘计算环境中的数据缓存问题为NP完全。

证明 ：为了证明数据缓存问题的NP完全性，我们将经典的NP完全集合覆盖问题归约到数据缓存问题的一个实例上。设有一个全集U={u1, u2,…, uN}，bi中的每个元素表示 U的一个子集，且每个元素 bi具有一个权重 ai。集合覆盖问题的目标是从 B中选择一个子集，使得该子集中所有元素的并集等于全集 U，并且权重之和最大或最小。

将集合覆盖问题约简为数据缓存问题的方法如下。
（1）设置数据的数量为1。
（2）令U={u1, u2,…, uN}为所有边缘服务器。
（3）令 B={b1, b2,…, bN}为在边缘服务器上缓存数据的不同方式。例如，b1={1, 3, 6}表示数据被缓存在第1、第3和第6个边缘服务器上，而 b2={3, 6, 7}表示数据被缓存在第3、第6和第7个边缘服务器上。
（4）令收益和成本分别表示每个子集的权重。

我们的问题可以描述为如下形式的集合覆盖问题。我们有一个集合 S={s1, s2,…, sK}表示所有的边缘服务器，集合中的每个元素 C={c1, c2,…, cL}表示在某个边缘服务器上对一份数据的所有可能缓存决策。对于每个缓存决策 ci，都有一个数据缓存效益和一个数据缓存成本。数据缓存效益与数据缓存成本之间的差值即为通过ci获得的数据缓存收益，记为 ri。我们问题的目标是找到一个集合 C′={c1 , c 2 ,…, c L ′},，它是 C的子集，并且 C′中所有元素的并集满足 c 1 ∪c 2 ∪···∪c L ′= S，使得所有ri的值之和最大化。

通过上述设置，我们可以将集合覆盖问题约简为我们的数据缓存问题。我们将实际变量纳入集合覆盖问题的框架中，发现这些实际变量对应于集合覆盖问题中的通用变量。换句话说，我们的问题考虑了与集合覆盖问题相同的因素，可被视为集合覆盖问题的一种变体。因此，数据缓存问题是NP‐完全问题。

IV. 实验评估

本节展示并讨论了为评估我们的方法而进行的实验结果。

A. 数据集

在实验中，我们使用了包含澳大利亚墨尔本中央商务区基站（即边缘服务器部署位置）和移动用户位置的EUA数据集[19]，该数据集可从 https://sites.google.com/site/heqiang/eua-repository 获取。本实验结合该数据集中的边缘服务器和移动用户的地理位置信息以及合成的热门数据进行。

B. 实验设置

如第III-B节所证明，数据缓存问题为NP完全问题。因此，在大规模数据缓存场景中，精确求解该问题是不可行的。为此，我们从EUA数据集中选取了80个边缘服务器和600个移动用户，以模拟边缘计算场景中的数据缓存场景。待缓存的数据是合成生成的，包括其大小和流行度（通过移动用户的请求次数来衡量）。每个边缘服务器覆盖区域内，移动用户对某一数据的请求次数（记为 νi）各不相同且相互独立。νi从 {0, 1,…, K × N}中随机选取。待缓存数据数量（记为 M）设为20，每条数据的大小（记为 Sj）从{10, 11,…, 30} MB中随机选取。B的值设为20。fkj从[5, 25]中随机选取，hj ik从[0.5到 2]中随机选取。为了模拟不同的数据缓存场景，我们改变边缘服务器数量和移动用户数量。每个实验运行100次，并报告平均结果。

为了评估我们称为IP算法的方法，我们将它与两种基线方法进行比较，一种Random方法和一种Greedy方法。对于给定的数据，Random方法随机选择边缘服务器来缓存该数据，以确保满足数据检索延迟的约束。而Greedy方法则始终选择请求该数据的移动用户最多的边缘服务器来缓存数据，直到满足数据检索延迟的约束为止。在每个边缘服务器上缓存数据后，它会计算数据缓存收益，并在数据缓存收益开始下降时停止。

实验在配备 Intel Xeon Gold 6130 @ 2.10 GHz、64GB内存的虚拟机上进行。第三节-B中提出的整数规划问题通过CPLEX优化器[20]（一种商业整数规划问题求解器）求解。

C. 实验结果与分析

在图2中，我们将移动用户数量固定为600，观察当边缘服务器数量从10增加到80时，服务提供商的数据缓存收益如何变化。结果显示，总体而言，三种方法下的数据缓存收益均随边缘服务器数量的增加而增加。我们的方法在数据缓存收益上的增长速度明显快于两种基线方法。这表明我们的方法在以最低的数据缓存成本实现最大数据缓存效益方面具有优越能力。一个有趣的观察是，在边缘服务器数量刚开始增加时，我们的方法所带来的数据缓存收益增长较快；当边缘服务器数量超过60后，增长速度开始放缓。在初期，边缘服务器数量的增加能够在相对较低的数据缓存成本下获得更高的数据缓存效益。当边缘服务器数量达到一定值（例如，在我们的实验场景中如图2所示为60）时，大部分数据已经被缓存在边缘服务器上，这些服务器已能够覆盖几乎所有的移动用户，因此后续收益的增长开始减缓。与我们的方法相比，贪婪方法实现的数据缓存收益较低，因为贪婪方法会冗余地且不必要地缓存部分数据，从而降低了服务提供商的数据缓存收益。随机方法的结果最差，其数据缓存效益远低于我们的方法和贪婪方法。

如图3所示，我们固定边缘服务器数量为80，观察数据缓存收益随移动用户数量的变化情况。与图2类似，总体上，随着移动用户数量的增加，数据缓存收益也随之增长。如图所示，数据缓存收益在初始阶段增长相对较慢，之后增速加快。具体而言，当移动用户数量在0到200之间时，数据缓存收益增长缓慢，因为用户数量过少导致对数据的请求数量较少，从而造成数据缓存效益较低。当移动用户数量超过200时，由于移动用户数量增加所带来的数据缓存效益增长开始主导相应的数据缓存成本，因此数据缓存收益开始显著上升。随着移动用户数量继续增加，数据缓存成本基本保持不变，传输成本仅略有增加，因此在此阶段，数据缓存收益随着移动用户数量的增加而快速提升。这意味着，当移动用户在整个区域内呈水平分布时，我们的方法仅略优于贪婪方法；而当移动用户呈垂直增长（即每个边缘服务器周围的用户密度增加）时，移动用户更加集中，此时我们的方法开始显著优于基线方法。

我们还测量了在边缘服务器数量和移动用户数量变化时，不同方法所达到的缓存命中率。缓存命中率是评估数据缓存性能的一个常见且重要的性能指标[21]。较高的缓存命中率表明数据缓存性能更高。结果如图4所示。与贪婪方法和随机方法相比，我们的方法表现出更高的缓存命中率。平均而言，它比贪婪方法高出34.43%，比随机方法高出168.77%。

除了数据缓存收益和缓存命中率外，数据缓存方法的计算时间也是一个重要的性能指标，因为方法的效率体现了其在实际场景中的实用性，尤其是在大规模场景中。图5分别比较了当边缘服务器数量和移动用户数量变化时，我们的方法与基线方法的计算时间。如图所示，我们的方法比两种基线方法花费更多的时间，且随着边缘服务器数量或移动用户数量的增加，时间差距变得更大。平均而言，我们的方法在求解边缘计算环境中的数据缓存问题时，比贪婪方法多花费433.18%的时间，比随机方法多花费186.67%的时间。如第三节-B所证明，边缘计算环境中的数据缓存问题是NP完全问题。因此，我们的方法不可避免地需要大量时间来寻找最优解。这表明在大规模数据缓存场景中寻找最优解是不现实的。更高效的、能够找到次优解的方法（例如启发式方法）更加实用和可取。

(a) 缓存命中率与边缘服务器数量的关系
(b) 缓存命中率与移动用户数量的关系

(a) 计算时间与边缘服务器数量的关系
(b) 计算时间与移动用户数量的关系

D. 有效性威胁

本节讨论评估有效性的威胁。用户和边缘服务器的位置是可能影响本文实验综合性的因素。我们进行了位置随机模拟的实验，结果受到很大影响，甚至可能无法返回任何结果。而当我们使用澳大利亚EUA数据集中的用户和边缘服务器位置时，所得结果更加可靠。实验结果是否因实验设置的使用而产生偏差，作为所选参数及其变化，可能符合假设。在实验中，我们使用了三个代表性参数（每次用户请求的收益、单位缓存成本和单位传输成本）。这三个参数也会影响结果，然而，如果我们控制单位缓存成本与单位传输成本之间的倍数关系，则收入的增长趋势几乎相同。

对我们的评估外部有效性的主要威胁在于生成的数据大小及其在用户上的分布的代表性。本文中，我们随机生成了数据大小，并通过遵循正态分布来模拟用户对边缘服务器上数据的请求。另一个对外部有效性的潜在威胁是COP模型未考虑非线性质量约束和参数。例如，可以考虑协调缓存机制，此时可使用二次表达式作为目标函数，且质量参数的值可以是名义上的，如缓存成本或传输成本。然而，这种威胁是微乎其微的。线性质量约束和参数一直是许多其他研究工作的相同前提。仅采用线性质量约束和参数不会影响IP算法与其他两种算法之间的比较。因此，考虑线性质量约束和参数并不是我们方法的显著限制。

V. 相关工作

在处理大量用户请求时，网络拥塞成为一个主要问题[22]。近年来，边缘计算中的支持缓存的架构作为解决该问题的一种方案，引起了研究人员的关注。

Ammar Gharaibeh 等人[16]从最小化内容提供商支付的总成本的角度研究了协作缓存问题。他们将该问题建模为一个整数线性问题，并提出了一种在线缓存算法，无需了解数据流行度的任何信息。

Tuyen X. Tran 等人[11]提出了一种联合协作缓存与处理的框架，支持自适应比特率视频流。他们还将视频变体在缓存中放置位置的决策问题建模为一个整数线性问题，并在视频流行度已知或未知的情况下提出了高效的解决方案。张曦[23]提出了在边缘所有缓存之间进行协作缓存的机制，以最大化缓存命中率。但他们未考虑如何确认一个视频是否流行。

张山 等人[14]研究了延迟最优的协同边缘缓存，其中基于带宽分配、信道质量和数据流行度来优化内容放置和簇大小。Jimy George 等人[12]提出了一种协同视频缓存策略。他们设计了一个选择待缓存视频的标准，并根据每个小区站点的视频流行度分布进行缓存替换。该工作考虑了活跃用户和用户偏好，以推导局部视频流行度。他们使用特定用户请求各类视频的概率来计算视频流行度，然后通过一个阈值将其划分为两个不同的组。缓存替换机制依赖于这两个组。

上述所有研究为我们提供了良好的范例。在本文中，我们从一个不同的角度考虑边缘计算环境中的数据缓存优化问题。我们的目标是在给定数据延迟约束下，最大化服务提供商获得的收入。我们使用扩展的PHT来判断数据是否为热门数据，并将缓存优化建模为一个整数规划问题。在计算服务提供商的收入时包含两个部分：第一部分是来自热门数据的收益，该收益与用户请求的数量相关；第二部分是在边缘服务器上进行数据缓存以及在云和边缘服务器之间传输数据所产生的成本。这两类成本使得服务提供商需要在缓存位置选择上进行权衡，以最大化其收益。

VI. 结论与未来工作

本文研究了该架构中的数据缓存问题，旨在最大化服务提供商获得的收入。我们通过时间扩展了PHT通过一个窗口来检查数据是否流行，并将数据缓存问题建模为一个优化问题，我们证明了该问题是NP完全的。通过使用墨尔本边缘服务器和用户位置的真实数据进行大量仿真，我们表明IP解优于贪心算法和随机访问算法。

在未来的工作中，可以研究缓存中数据放置的优化。为此，可以识别协作边缘服务器中的所有数据。无需从云中检索所有数据，而可以在边缘服务器之间实现数据传输。此外，还可以开发在线数据放置算法，通过最小化延迟来实现快速交付。