Optimized Content Caching and User Association for Edge Computing in Densely Deployed Heterogeneous Networks

Optimized Content Caching and User Association for Edge Computing in Densely Deployed Heterogeneous Networks

1、问题背景

在宏基站（MBS）的覆盖区域下部署小型小区（cell）基站（SBS），并预先在SBS处缓存流行内容，是在下一代移动的通信网络中提供高速和低延迟服务的有效手段。本文研究了内容缓存和用户关联的优化问题。

贡献点：

考虑缓存内容分布在云中心和基站（MBS和SBS）的情况，以最小化平均内容下载延迟为目标，建立了内容缓存和用户关联联合优化问题（JCC-UA）.我们还证明了JCC-UA问题是NP-hard的。
为了解决JCC-UA问题，提出了一种基于三次指数平滑的智能内容缓存策略（SCCP）用于内容缓存，提出了一种快速关联（RA）算法和一种延迟关联（DA）算法用于用户关联。
提出的JCC-UA方法，包括SCCP，RA和DA算法，在我们的模拟研究对他们的性能进行了全面评估，在缓存命中率和内容下载延迟。在我们的模拟研究中，所提出的方案优于几个基线方案具有相当大的利润率。

2、系统建模及问题公式化

系统建模

异构网络的两层内容缓存和服务模型如图所示：
- 内容缓存的上层位于与核心网相连的云中心，而下层内容缓存则位于包含部分MBS和SBS的蜂窝网络中
在本文中，我们假设所有的基站都通过回程链路连接到核心网，并且基站之间没有直接的链路，这是现实网络中常见的场景。为了简单化，只存在一个MBS，MBS和SBS的集合为\(F = \{f_0,f_1,...,f_N\}\)，\(f_0\)为MBS，其余N个基站为SBS，\(U = \{u_1,u_2,...,u_M\}\)表示在蜂窝网络中的M个移动用户。考虑分配给不同BS的频率子信道是正交的，因此在该设置中不需要小区间干扰。基站\(f_n\)处的可用带宽为\(B_n(n=0,1,...,N)\)，其被划分为\(I_n\)个子信道。每个\(f_n\)的子信道带宽为\(b_n = B_n/I_n\)。每个子信道服务于一个移动的用户，这意味着由每个基站\(f_n\)能够服务移动用户的最大数量是\(I_n\)。由于SBS和MBS之间的重叠覆盖，重叠覆盖区域中的用户可以通过与MBS或SBS其中的一个相关联来接入蜂窝网络。
\(SNR_{mn_j}\)是从基站\(f_n\)到移动用户\(u_m\)在子信道\(j,j \in \{1,2,...,I_n\}\)上的信噪比（signal-to-noise），\(SNR_{mn_j} = P_{n_j}G_{mn_j}/\sigma^2_N\)。其中\(P_{n_j}\)是基站\(f_n\)在子信道\(j\)的传输功耗，\(G_{mn_j}\)是在子信道\(j\)上从基站\(f_n\)到用户\(u_m\)的无线链接的信号增益。\(\sigma^2_N\)是高斯白噪声功率。
通信链路的衰落由Rayleigh衰落和路径损耗组成，因此我们有\(G_{mn_j} = \kappa·\tau_{mn_j}·d^{-\epsilon_{mn_j}}\)，其中
\(r_{mn_j}\)表示通过子信道\(j\)，移动用户\(u_m\)从基站\(f_n\)下载内容的数据速率，它可以通过香农公式计算为：
令\(C=\{c_1,c_2,...,c_K\}\)表示为在系统中的\(K\)个内容的集合。其中\(c_k\)的大小为\(l_k,k=1,2,...,K\)。内容可以分布式存储在云中心或BS中，包括MBS和SBS。基站\(f_n\)的缓存容量表示为\(S_n(n=0,1,...,N)bits\)。如果内容\(c_k\)缓存在基站\(f_n\)上并且移动用户\(u_m\)与\(f_n\)联系，则用户\(u_m\)可以直接从\(f_n\)下载内容，否则从云中心下载内容。如在[17]中，我们假设从BS到核心网络的回程链路（backhaul links）的延迟等于\(T_C\)。
注意，仅当内容已经由移动的用户通过BS下载时，该内容才被缓存在BS处。这种类型的内容缓存可以被称为“被动内容缓存”。因此，我们并不考虑基站获取内容的额外成本。
为了满足移动的用户的QoS要求，我们假设对于移动的用户\(u_m\)的最小保证数据速率是\(r_{m,min}\)。移动的用户\(u_m\)可能在子信道\(j\)上与BS \(f_n\)相关联，当且仅当\(r_{m,min} \leq r_{mn_j}\)。如果没有BS可以满足最低保证数据速率，则用户请求将被拒绝。在这种情况下，用户可以在稍后的时间再次发起新的关联请求。

问题公式化

制定最小化移动用户的平均内容下载延迟的JCC-UA问题：

JCC-UA问题定义如下：有\(K\)个内容将被分布式缓存在云中心和\(N+1\)个BS（包括MBS和N个SBS），并且\(M\)个移动用户将通过内容中心和BS下载这些内容。JCC-UA问题是决定每个内容应该被缓存在哪个BS上以及每个移动用户将与哪个BS相关联。
移动用户\(u_m\)请求内容\(c_k\)，下载延迟为\(l_k/r_{mn_j}\)，如果\(c_k\)被缓存在了\(f_n\)上并且\(u_m\)与\(f_n\)的\(j\)子信道相关联。否则，内容下载延迟为\(l_k/r_{mn_j} + T_C\)。
定义\(X = \{x_{nk}|f_n \in F,c_k \in C\}\)作为内容缓存决策矩阵，\(x_{nk} \in \{0,1\}\)。\(x_{nk} = 1\)意味着内容\(c_k\)缓存在了基站\(f_n\)上。
定义\(Y = \{y_{mn_j}|u_m \in U,f_n \in F,j \in I_n\}\)作为用户关联决策矩阵，\(y_{mn_j} \in \{0,1\}\)。\(y_{mn_j} = 1\)意味着用户\(u_m\)在子信道\(j\)上与基站\(f_n\)关联。
因此，移动用户请求内容\(c_k\)的内容下载延迟为：
令\(q_{mk} \in \{0,1\}\)表示是否移动用户\(u_m\)请求内容\(c_k\)。用户\(u_m\)下载内容的总内容下载延迟为：
在本文中，我们的目标是最小化平均内容下载延迟，其由下式给出：
考虑到系统约束，JCC-UA优化问题可以表示为：
- 不等式（6）确保存储在BS处的内容的总和不大于BS的存储容量
- 约束（7）保证BS服务的移动用户的数量不大于BS可以服务的移动的用户的最大数量
- 约束（8）表示移动用户可以与至多一个BS的一个子信道相关联
- 不等式（9）表示如果用户\(u_m\)与BS相关联，则移动用户\(u_m\)下载内容的数据速率将不小于所需的最小数据速率

通过引理Lemma1证明了问题的Np-hard性质：

考虑一种特殊情况：即，每一个基站都能缓存所有内容，每个内容都能直接传输（因为最小保证数据率为0）
因此，约束条件（6）（7）可以不用考虑了，问题转变为：
公式（12）中的优化问题是一个经典的分配问题，已被证明是NP-hard [36]。这意味着JCC-UA问题的特殊情况是NP-hard的。因此，在（5）、（6）、（7）、（8）、（10）和（11）中公式化的JCC-UA问题是NP-Hard

联合内容缓存和用户关联策略

本节中，提出了有效的启发式算法来解决JCC-UA问题

启发式算法包括：
1. 基于三次指数平滑的智能内容缓存策略：智能内容缓存策略根据与用户关联相关的内容请求历史来做出缓存决策
2. 两种动态的用户关联算法：动态用户关联算法根据缓存的内容将用户关联到SBS。

与用户关联相比，在大多数情况下，内容缓存可以在更粗的时间粒度上执行。这样，我们解耦内容缓存和用户关联在提出的JCC-UA算法上

智能内容缓存策略

智能内容缓存策略（SCCP）基于对内容下载次数的预测。并且使用指数平滑法来预测移动用户通过基站下载内容的下载次数（DCC），由于移动的用户下载内容时的随机行为，DCC的数据序列是非线性的。因此，三次指数平滑法比单次指数平滑法更适合预测DCC值[37]。
\(z_{nk}(i)\)表示在时隙\(i\)，内容\(c_k\)由移动用户从基站\(f_n\)下载的下载数量：
\(z_{nk}(i)\)的平滑值表示为\(F_{nk}(i)\)，\(z_{nk}(i+1)\)的预测值为\(\hat{z}_{nk}(i+1)\)。
- 其中\(\alpha\) 为平滑参数，\(\alpha\)越大，新观测数据的权重也就越大。在三次指数平滑中，公式(14)进一步用来计算具有非线性趋势的预测方程的系数。立方指数平滑法用于预测\(\hat{z}_{nk}(i+1)\)的数学模型在（15）中给出。当观测数据的长期趋势相对稳定时，\(\alpha\)的值应该较小
在通过上述三次指数平滑方法预测DCC的值之后，我们根据以下简单策略缓存每个内容：
- 在时隙 \(i\)，当我们想要缓存内容时，我们在每个BS处缓存内容根据预测的DCC值的降序（即，\(\hat{z}_{nk}(i+1)\)），直到BS的缓存容量被完全占用。

动态用户关联方法

当移动的用户想要下载内容时，对于移动的用户来说重要的是选择适当的BS来关联以减少内容下载延迟。这意味着移动的用户与适当BS的适当子信道相关联。在这一小节中，我们提出了动态用户关联方法，包括快速关联方法和延迟关联方法

在传统的用户关联策略中，移动用户可以根据信号强度、传输速率等进行关联。在本文中，移动用户根据是否以最小延迟下载内容与BS进行关联

RA（Rapid Association）Algorithm：

DA (Delayed Association) Algorithm:

在RA中，一旦做出关联决定，RA方法仅关联一个移动用户，这可能导致在整个网络的总体平均内容下载延迟方面的局部优化。在本小节中，我们提出了延迟关联（DA）方法，以实现更有效的用户关联。每个时间片表示为\(T_s\)
我们的目标是将这些移动的用户与适当的BS相关联，以优化这些移动的用户的平均内容下载延迟。这种优化可以建模为图论中的最优匹配问题。
定义一个带权二分图：\(G_t = (U_t,CH_t,E_t,W_t)\)。\(CH_t\)表示基站的可使用（获得）的信道集合，\(E_t\)表示边的集合。边\(e_t\)的权重，表示为\(\omega(e_t)\)，是移动用户\(u_t\)下载内容\(R_t(u_t)\)的内容下载等待时间，\(W_t\)是边权重的集合。根据\(G_t\)的定义，将最小化平均内容下载延迟的延迟用户关联问题转化为寻找\(G_t\)的最佳匹配，可以通过Kuhn-Munkers（KM）算法[38]。
在应用KM算法求出\(G_t\)的完美匹配之前，首先要将\(G_t\)转化为一个正则二部图，即在\(G_t\)上增加虚顶点和虚边。正则二分图表示为\(G^r_t = (U^r_t,CH^r_t,E^r_t,W^r_t)\)
- (正则二分图：https://www.luogu.com.cn/blog/rqy/hall-theorem-regular-bigraph)
- 使得二部图左右两边的点数一样，除了原始图边权存在以外，其他点之间边的权值为正无穷：
具体算法如算法2所示：
- 一共分为4个步骤：