一篇来自 TMC21 的关于边缘计算环境下服务放置的论文，第一次在组会做的报告。
L. Chen, C. Shen, P. Zhou and J. Xu, “Collaborative Service Placement for Edge Computing in Dense Small Cell Networks,” in IEEE Transactions on Mobile Computing, vol. 20, no. 2, pp. 377-390, 1 Feb. 2021, doi: 10.1109/TMC.2019.2945956.

Abstract

MEC 将计算的任务从集中的云端扩散到了几乎是数据源处，因此大幅度降低了提供服务的延迟并且节省了网络的带宽。MEC 的计算卸载任务被研究了很多，但是服务放置任务作为一个相当重要的设计却没有得到关注。服务放置指的是设置服务平台，并且将相关的库和数据库存放到边缘服务器。例如配置了MEC的基站（BS），允许执行相关的计算任务。由于有限的计算资源，边缘服务器通常只能提供较少数量的服务，因此具体提供什么服务需要进行正确的决策才能最大化系统的性能。
本篇论文探究了一种面向启用MEC的密集小型基地台网络的联合式的服务放置（Service Placement）。我们提出了一种有效的分布式算法，简称为 CSP（Collaborative Service Placement），在小型的基地台网络内，基站对服务放置的决策进行联合式的优化，以解决MEC系统中的一些挑战，包括服务的异构性、空间上需求的耦合性、分散式的协作。
CSP 算法基于并行的吉布斯采样，通过利用小型蜂窝网络上的图形着色而开发。和传统的吉布斯采样相比，该算法大大提高了时间效率，同时也保证了可证明的收敛性和最优性。CSP 被进一步扩展到了自私型基站的研究，在这种情况下基站是可以选择合作和不合作。我们采用了合作博弈理论来研究BS的策略并且设计了组建合作计划来使用合并和分裂规则来建立稳定的基站合作。实验结果表明，CSP可以有效降低边缘系统的操作成本，无论是对于合作还是自私的基站。

Questions

在小型基地台网络内提供服务的例子？

  1. 在博物馆内，通过在 BS 处部署 AR 服务，来为当前区域提供实时的服务。
  2. 对于在家晚上玩手机游戏的用户，开发商可以在特定时间内提供这种游戏所需要的服务。

为什么要建立这个模型？

  1. 部署在 BS 的计算资源是有限的，边缘服务器通常由于执行任务的异构性和时间的变化，而导致服务频繁的配置和删除。导致加重了网络了负担，额外的计算延迟，最终使得用户的体验恶化。
  2. 小型基地台的概念最近被提出，可以实现无缝的覆盖，增加吞吐量并且节省蜂窝网络的能量消耗。在当前以及未来高密度的基站覆盖下，一个移动的设备可能会被很多个基站覆盖，这为共同提供计算资源、共享配置的服务、协同提供计算服务。

进行 service placement 决策的困难：

  1. 需要同时基站的考虑无线接入和计算服务，因此需要一个新的模型来整体地考虑系统的各个方面。BS 之间不仅可以在服务平台上进行协作，还可以在任务的物理传输上协作。
  2. 尽管小型基地台之间的网络的部分重叠为 BS 协作创造了可能，但是这也导致了复杂的多网格交互下的服务需求和计算资源的高度耦合，因此最终的合作式服务放置成为了一个相当复杂的联合优化问题。本身分布式 MEC 使得这个问题更加棘手。
  3. 因为小型基地台的基站通常是由个人用户部署的，例如企业用户，所以如果没有一定的好处，那么他们不一定愿意参与到这套合作式的系统来。因此需要设计一个激励的机制来鼓励服务放置的合作工作。

这篇论文的工作：

  1. 将在密集小型基地台网络下的协作式服务放置任务表述为一个最大化可用性问题。
  2. 开发了 CSP 算法来解决一个困难的组合优化问题。CSP 算法的特点之一是分布式的处理原则，适用于在地理位置上分散的边缘节点。基于吉布斯采样实现，一个马尔可夫链蒙特卡洛算法。创新点在于使用图上色理论来允许并行地进行吉布斯采样，加速了算法的收敛。
  3. 采取了合作博弈理论来探索在合作式服务配置时自私的战略行为。为了推广协作服务放置，使用了激励机制。开发了一种分布式的同盟建立算法，并证明是帕累托最优的稳定合作。

以前研究的缺陷：

  1. 传统的在云服务器上部署 VM 时研究的服务共享无法直接应用到 MEC，因为移动的网络更加不稳定，最优解往往是空间耦合并且暂时的。
  2. 先有的集中式的解决方案将问题描述为一个整数线性规划问题，并且利用集中式的方式进行计算。
  3. 原有的联合优化问题下假设了边缘节点支持范围没有重叠覆盖的区域。

建模

网络建模

BS，或者说边缘服务器，从 $1$ 编号到 $N$。
对于每个 $BS_n$ 来说，都被一组用户设备（UE）订阅了，这个集合 $\mathcal M_n$ ，这些设备被允许该 $BS_n$ 访问信号和计算资源。
每一个 $UE$ 实际上都是被一个服务计划（商业的 BS）或者拥有者（自有的 BS）决定的。
对于 $\mathcal M_n$ 中的每个 UE 而言，$BS_n$ 被成为他们的 $home BS$。
例如在一个有很多层的大楼内，每个房间都部署了一个 a small cell BS（可能是 Femtocell，家庭基站），而 UE 可能是移动设备，传感器或者其他的需要联网和计算服务的智能设备。
由于 small-cell BS 的密集部署，一个 UE 可能在多个其他 BS 的覆盖范围内。对于每个 BS 来说，它们可以开启 OSG（open subscriber group）模式，允许服务其他订阅的 UE。一开始我们假设所有的 BS 都处于 OSG 模式。
对于 $UE_m$，我们用 $\mathcal N_m$ 表示可以通信的 BS 集合。
对于 $BS_i$ 和 $BS_j$ 来说，如果存在一个 $UE_m$ 使得 $i,j\in\mathcal N_m$ ，我们就它们两个是邻居，换句话说它们两个是可以合作地服务于至少一个 UE。
通过以上定义，我们可以把网络抽象为一个无向图 $G=\langle \mathcal N, \mathcal \varepsilon \rangle$，在这里 $\varepsilon$ 指代边的集合。当两个 BS 为邻居时，两者之间有边。
我们使用 $\Omega_{i,1}$ 和 $\Omega_{i,2}$ 来分别表示 $BS_i$ 在一跳和两跳范围内的邻居。

边缘服务建模

边缘服务器都是用虚拟化的技术来提供执行的环境，通常来说时 VM 和 Docker 的容器提供的服务放置。如果一项服务应用需要被放置在 BS 处，那么就需要由操作员来根据对应的资源需求来进行设置。服务的资源需求通常是由服务提供者预先决定好的。
考虑到服务的异构性，我们假设这里有 K 种服务，$\mathcal K = {1,2,…,K}$。
由于一台边缘服务资源的限制，不可能同时部署所有种类的服务，我们假设处理器的能力是资源分配的主要限制。设定 $p_k$ 表示服务 $k$ 的处理器需求，$P_n$ 表示 $BS_n$ 能提供的处理器能力。
对于一个服务放置决定 $a_n \subseteq \mathcal K$ 对于 $BS_n$ 来说是可实现的，只有在 $\sum_{k\in a_n} p_k \le P_n$ 为真，即部署在该 BS 上的所有服务的处理器需求总和要小于这个 BS 所拥有的处理器能力。

假设 $a_n \in \mathcal F_n$ 是当前 $BS_n$ 的服务放置决策，那么对于当前系统而言，服务放置状态可以表示为 $a = {a_1,…,a_N}$

计算卸载建模

主要分为两种 user-to-edge 的卸载和 edge-to-cloud 的卸载。

Edge offloading

采用了一种简单的卸载策略，每个 UE 接受服务放置和合作决策作为输入，目标是最大化 QoS。

$d_{m,k}$ 表示 $UE_m$ 在当前情况下对服务 $k$ 的需求。
$d_m={d_{m,1},d_{m,2},…d_{m,K}}$ 表示 $UE_m$ 对所有服务的需求情况。

BS 可以轻松获得这个 d，要么在决策前提前询问每个 UE，要么通过预测算法直接进行预测。

根据系统的服务放置状态 $a$，我们用 $B_{m,k}(a)\subseteq\mathcal N_m$ 表示 $UE_m$ 想要获取服务 $k$ 的可访问的 BS。
$d_{m,k}$ 被卸载至 $B_{m,k}(a)$ 中拥有最佳的上行通道的 BS，我们表示为 $argmax_{n\in\mathcal B_{m,k}(a)}H_{m,n}$ ，这个式子中的 $H_{m,n}$ 表示 ${UE_m}$ 和 $BS_n$ 之间的信道质量。

$\mathcal B_{m,k}(a) = \emptyset$ 表示 $UE_m$ 无法获取它想要的服务 $k$。这种情况下，$d_{m,k}$ 将会通过 $UE_m$ 的 home BS 被卸载到云端。
$v_{m,k}(a)\in\mathcal N_m$ 用来表述 $UE_m$ 为了获取服务 $k$ 需求最终请求的 BS。
${n_m}$ 表 $UE_m$ 的 Home BS。

给定卸载决策，我们可以将 $BS_n$ 收到的关于服务 $k$ 的请求表示为：
$\hat{\phi}{n,k}(a)=\sum{m\in\mathcal M}d_{m,k}·1{v_{m,k}(a) = n}$
这里的 $1{·}$ 是一个指示函数（真为1，假为0）。

Cloud offloading

同样使用了现有的云卸载决方案。
$\bar\phi_{n,k}$ 表示 $BS_n$ 的最大负载限制，即 $BS_n$ 对服务 $k$ 能处理的最大需求数量。
综合以上两个变量，总结出 $BS_n$ 处理的服务 $k$ 的请求：
$\phi_{n,k}(a)=\left{ \begin{aligned} min(\hat{\phi}{n,k}(a),\bar\phi{n,k}),if k \in a_n \ 0, if k\notin a_n\end{aligned}\right.$

$BS_n$ 收到但是卸载到云端进行的对服务 $k$ 的请求 $\psi_{n,k}(a) = \bar\phi_{n,k}(a) - \phi_{n,k}(a)$

Utility model

BS 在提供更加优质的服务时，我们可以认为 BS 应该获得更好的回报，服务的质量的关键因素是延迟。对于服务 $k$ 可以获得收益定义为 $\mu_k(y_k)=u_k-w_Y\cdot y_k$。
$u_k$ 是完成任务 $k$ 的收益常量，$y_k$ 是提供服务的延迟，$w_Y$ 是延迟的比重。这个延迟包含了传播时延和计算延迟。

$UE_m$ 和 $BS_n$ 之间的传输速率可以计算：
$r_{m,n} = W \log_2(1+\frac{P_m^{tx}H_{m,n}}{N_0+I_{multi-user}+I_{Inter-cell}})$
$W$ 是信道带宽，$P_m^{tx}$ 是传输功率，$H_{m,n}$ 是 $UE_m$ 和 $BS_n$ 之间信道的传输能力，$N_0$ 是噪声功率，$I_{multi-user}$ 和 $I_{Inter-cell}$ 分别是多用户和多基站的干扰。这两个变量通常可以用先进的干扰抑制技术减轻。

假设$BS_n$ 都是固定的传输速率 $r_n$，传输任务 $k$ 的延迟可以表示为 $y_{Ex,n,k}=\lambda_k/r_n$，$\lambda_k$ 是传输的任务的数据量。

从 BS 卸载至云端的额外传播延迟表示为 $y_{C_x,k}=\lambda_k/r_b$，$r_b$ 表示预期的主干网的传输速率。我们假设结果数据量非常小，下载的传播延时可以忽略不计。在边缘服务器上，服务 $k$ 的计算延迟主要是通过 CPU 进行计算所花费的开销，表示为 $y_{E_m,k}=\gamma_k/p_k$，$\gamma_k$ 表示完成这项任务需要的 CPU 周期，$p_k$ 是边缘服务器分配给服务 $k$ 的处理器频率。
云服务器的计算资源较为丰富，忽视云服务器上的阻塞延迟。云服务器上的计算延迟表示为 $y_{C_m,k}=\gamma_k/p_{c,k}$ ，这里的 $p_{c,k}$ 表示的是云服务器分配给服务 $k$ 的处理器频率。
最终我们可以分别计算出服务 $k$ 在边缘和云端处理的延迟 $y_{E,n,k}$ 和 $y_{C,n,k}$
在边缘服务器上，就是边缘的传播延迟+边缘的处理延迟。
在云服务器上，就是边缘的传播延迟+云的传播延迟+云的处理延迟。

对于 $BS_n$ 来说，它最终做出的贡献相当于提供的所有服务的收益之和 $R_n(a)$。

BS 的开销主要包含两个方面：边缘服务器的能源消耗和使用云服务器的支出。
$BS_n$ 在处理任务 $k$ 的时候消耗的能量：$E_{n,k}=\mathcal k_n\gamma_k(p_k)^2$，$\mathcal k$ 是由边缘服务器架构决定的能源系数。
$BS_n$ 的总能源消耗表示为 $C_{E,n}(a)=\sum_{k=1}^{K}E_{n,k}\cdot \phi_k(a)$
同理将 $h$ 定义为在云服务器上的一个工作单位的价格，可以同样计算出云服务器上的开销。

对于 $BS_n$，它的效益 $U_n$ 就是通过总的收益减掉边缘服务器的能源消耗和云服务器的支出。

非协作式服务放置

对于每个 BS 来说最终的优化目标方程总结为：

12a 表示最大化 K 个服务所能产生的最大效益，这个效益是由服务提供数量，延迟，卸载决策，能源消耗一起决定的。

12b 表示在提供某个服务的时候，要低于请求数和能接受的请求上限。

12c 表示只有 Home Server 为 UE 提供服务。

12d 表示确保当前的服务放置策略是可行的。

协作式服务放置模型

通过一系列推倒，我们可以将最终的优化目标总结为下式。

我们希望，通过尝试不同的服务放置组合，即穷举服务放置矩阵 $a$ 来尽可能减少整个系统总的开销。但是穷举的方式时间复杂度太高了，本论文尝试使用并行的吉布斯采样算法进行优化。

涂色+吉布斯采样

吉布斯采样是用来生成网络服务放置矩阵 $a$ 的概率分布，通过逐个扫描每个 BS，从概率分布中进行采样确定它的服务放置决策，保证其余的 BS 的服务放置决策固定不变。

吉布斯采样获取的概率分布一定是和 $e^{-\sum_n{C_n(a)/\tau}}$ 成正比的，可以简单的理解为，越低的系统开销应该会有越高的概率被选择。这里的 $\tau$

单纯的使用吉布斯采样的缺陷：

  • 因为每次只能计算一个的概率分布，所以如果 BS 数量较多，就会需要花很多时间进行循环
  • 这个算法的前提是每个 BS 知道整个系统的情况，但实际上在论文假定的密集小型基地网络环境下是基本不可行的。
    之所以没办法直接进行并行的吉布斯采样的原因是没办法保证收敛至吉布斯分布。

因此，论文基于 MRF 理论和图上色理论，来为 BS 进行分组，在不影响最终目标的情况下尽可能的实现并行计算。
Markov Blanket，中文翻译为马尔可夫毯，每一个 BS 都有一个马尔可夫毯，马尔可夫毯是一个 BS 集合，在这个集合外的所有 BS 的服务决策分配将不会对该 BS 的概率分布产生影响。
论文提出，在这个马尔可夫随机场内，每个 BS 的马尔可夫毯就是 2 跳以内的所有相邻 BS 的子集。因此，计算某个 BS 的概率分布的时候，所有不相邻的 BS 都不会影响他的最终决策。

因此，根据网络拓扑图，我们可以将所有的 BS 分成若干组，保证每个组内的 BS 进行决策时互不干扰。并且，为了让并行性更高，我们肯定是希望分的组数越少越好（每个组内的 BS 尽可能多一些）。
纯粹的着色问题求解难度是 NP-hard，但是 BS 网络拓扑结构通常每个节点的度都比较小，每个 BS 的邻居比较少，因此可以使用现有的图着色算法进行求解。本文使用了 sequential coloring algorithm 来生成图的着色情况。


在上一次迭代的最后，绿色的 1 和 4 号在更新完自己的服务放置决策之后，把自己的最新决策告诉给了 2-hop 以内的 BS。
本次迭代更新蓝色的 2 和 5 号，已知 2-hop 内所有 BS 的当前决策的总 cost，即可计算本 BS 的服务放置决策概率分布，根据概率分布进行采样（概率越大越容易被选中，只有能让总cost减小的决策才会有更大的概率）。
更新完成后，在本次迭代结束前，将自己的最新决策告诉 2-hop 以内的其他 BS，以便于在下一次迭代过程中计算他们的概率分布。

自私基站模型

每个联盟的 value function 定义为，当合作只发生在联盟内部时所能获取的最大效益。
想要计算这个效益，可以通过上文的 CPGS 算法，把这个联盟看作一个系统，计算最优服务放置方案来获得最大效益。

这篇文章定义了两种合作模式：

  1. 纯合作，通过完成的任务和开销之差直接计算效益。合作相对较弱，因为没有额外收益。
  2. 激励式合作，通过激励方案，将系统所能收获的最大效益分配给系统内的 BS。根据 proportional fairness division 来决定分配的效益，将通过合作额外获得的系统效益按比例分配给 BS。

每个参与到合作里来的 BS，都会获取更多的效益，这个效益按照下面这个公式计算：

前面这个系数代表了自己的贡献比例，每个联盟里的系数和为 1，一般来说，自己贡献越多，则获取的比例越大。

Stable Coalition：一个稳定的联盟，联盟内的基站不会因为激励措施而离开当前的联盟去成立一个新联盟。让联盟内的所有基站都获得更高的效益，对于稳定来说是必要不充分条件。