一种支持边缘计算中双向主动卸载的先进决策模型

摘要

边缘计算被认为是一种有前景的手段，能够利用边缘端的计算能力，并解决云计算中面临的问题。本文提出了一种先进的决策模型，以解决边缘计算中的计算卸载问题。该模型利用互联网内在的分层拓扑结构，以去中心化方式执行在线调度，从而消除预期建模的需求。同时，它也承认拥塞可能由于过时信息等原因意外发生。本决策模型通过两种增强机制，赋予卸载操作中的发送方和接收方“丢弃”请求的能力，以避免拥塞。此外，还引入了随机早期检测（RED）算法。仿真结果表明，该决策模型能够良好地处理工作负载，且这两种增强机制是有效的。

关键词 ：边缘计算、卸载问题、拥塞避免、RED算法集成

1. 引言

云计算的成熟在各个方面极大地影响了我们的生活。著名的软件即服务（SaaS）实例，如谷歌应用，已经拥有日活跃用户（DAU）达到数百万甚至数十亿的规模。与此同时，旨在提供可扩展性、弹性和自主性的各种基础设施，如亚马逊EC2和微软Azure，已被开发以支持这些服务。我们之前的工作[1]及其增强版本[2]也对此主题提出了一些建议。

近年来，物联网（IoT）、云粒和手机的普及正在逐渐发生变化。在传统云计算中，数据消费者和数据生产者之间有明确的界限；而如今这些物联网设备不仅可以作为数据生产者，还可以作为数据消费者[3]。基于这一角色转变，数据生产者的数量激增，同时作为生成的原始数据。尽管中心服务器的处理能力在不断发展，但数据量的增长和网络带宽的限制正成为基于云计算的瓶颈[3]。

此外，服务尤其是移动服务对延迟越来越敏感，并需要即时响应[4]。像我们在传统云计算中所做的那样，将工作负载卸载到中心服务器，由于网络传输[5]不可避免地会带来较长的延迟，从而对性能产生重大影响。此外，其他考虑因素，如隐私保护要求，也正引起越来越多的关注。

这些趋势推动了新型计算范式——边缘计算的发展。在边缘计算中，数据应在产生数据的边缘附近进行处理。由于该范式能够节省网络带宽并充分利用边缘的处理能力，因此被视为一种具有前景的使能技术。然而，仍有一些问题需要解决。其中，涉及能耗与服务延迟之间权衡的计算卸载问题已引起广泛关注。

最近的研究工作集中在提出一些混合框架，这些框架利用中心服务器和边缘服务器来解决计算卸载问题。其他研究（如[8]）提出了一种基于消息的模块化网关平台，以实现集群网关以及对外围通信协议细节的抽象。然而，大多数研究不恰当地将边缘服务器视为黑箱，这意味着一旦做出卸载决策，所选服务器就能完全按预期工作，且不会发生拥塞。换句话说，这些混合框架以静态方式做出决策。此外，它们还在中心服务器与边缘服务器之间以扁平方式进行决策，忽略了从边缘服务器到中心服务器网络的内在层次结构[3]。尽管一些研究人员利用了层次结构，但他们进行了人为组织，其工作负载放置是一个离线任务[9]。

在本文中，我们通过将边缘服务器和中心服务器组织在其内在分层结构中，分别在每个服务器上维护任务队列，并对工作负载进行在线调度，从而解决计算卸载问题。我们的基本思想是赋予卸载操作的发送方和接收方“丢弃”请求的能力，以避免拥塞。我们将用于网络调度器的队列机制随机早期检测（RED[10]）集成到增强的决策过程中，从而提高资源利用率，并保持整个框架的轻量级特性。

仿真结果表明，即使在处理峰值负载或由拓扑结构或工作负载本身引起的偏斜负载时，我们的方法也能良好地应对工作负载。

本文的主要贡献可以总结如下：
- 我们指出了现有计算卸载方案的不足，并相应地提出了一种轻量级决策模型，该模型利用网络的内在层次结构，容忍过时信息，并以在线方式实现双向主动卸载。
- 我们详细分析了随机早期检测算法的机遇，并在进行适当修改后将其迁移到我们的决策模型中。
- 我们从各个方面对我们的决策模型进行了全面评估，以验证其有效性和鲁棒性。

本文的其余部分组织如下。第2节讨论相关工作。第3节介绍系统模型。第4节详细说明我们的先进决策模型及其实现。第5节展示评估结果。第6节得出结论并讨论未来工作。

2. 相关工作

在计算卸载问题方面已开展了大量研究。从学术上讲，该问题可分解为一系列需要做出的决策：当工作负载产生时（通常以原始数据的形式），用户设备（UE）（例如物联网设备）应决定是在本地处理还是将其卸载到某个远程服务器；一旦决定卸载，UE需从多个可访问的边缘/中心服务器中选择一个合适的服务器作为接收方。此外，根据对隐私和依赖性的考虑，UE可以选择完全卸载或部分卸载[11]。

早期，研究人员一直在寻找一些自适应方法。咸等人[12]通过引入超时避免了预测，该超时最初是2-竞争性的，最终达到统计最优。Gonzalo等人[13]提出了一种基于应用程序执行历史分析的可适应机制，以实现自适应卸载。

近年来，大多数决策[6][7][14][15]都是基于能耗与延迟之间的权衡[11]做出的。徐等人[6]将决策问题建模为一个去中心化计算卸载博弈，并提出了一种基于博弈论的方法来实现高效的卸载。张等人[7]设计了一种高效能计算卸载（EECO）方案，联合优化卸载和无线资源分配，结合了5G异构网络的多接入特性。杨等人[14]认为用户设备（UE）与其可访问的远程服务器（如云粒）之间的连接可能是间歇性的，因此他们建立并求解了一个马尔可夫决策过程(MDP)模型，以获得最小化计算和卸载成本的最优策略。拉希米等人[15]提出了一种称为MAPCloud的混合分层云架构，旨在利用本地和公共云来提高移动应用的性能和可扩展性。

如第1节所述，尽管这些策略考虑了移动应用和边缘计算的不同特性，但它们的决策方式是静态且扁平的。现有研究更侧重于调度，将边缘/中心服务器不适当地视为黑箱，忽略了网络中可能出现意外拥塞的可能性。同时，它们仅根据传输时间来估算“服务器有多远”，从而忽视了网络内在的层次化结构[3]。

Mike等人[16]试图通过基于流网络重定向任务并寻找工作负载的最佳放置方案来弥补这些缺陷。然而，他们假设所有云粒都相互连接，因此整体扁平结构仍然存在。梁等人[9]则提出了一种分析模型，以证明层次化结构在应对峰值负载时具有更高的效率，并进一步开发了算法来自适应地将工作负载部署到不同层级的服务器中。然而，他们采用了人为组织的方式，而非利用固有的内在层次结构。此外，这些策略存在一个共同的缺陷：工作负载的放置变成了一个离线任务。因此，预期的建模及其带来的开销不可避免。

从其他方面来看，陈等人[17]将单用户设备场景扩展到了多用户设备场景，所提出方案的整体复杂度为O(N⁶)，当连接的用户设备数量较多时，该复杂度可能过高。尤等人[18]研究了异步计算卸载系统中面向能效的资源管理策略，其中用户设备具有不同的输入数据到达时刻和计算截止时间，建立了优化问题，并提出了针对数据划分（用于卸载和本地计算）以及时分（用于传输）的两种最优策略。然而，仍未考虑意外拥塞可能发生的情况。

面对可能的拥塞问题，谢尔米拉等人[19]采用博弈论，将问题建模为少数者博弈（MG），并应用强化学习来求解该博弈。通过这种方法，可能的拥塞问题从资源分配的角度加以考虑，而非计算卸载[11]，且需要集中式调度。其他研究如[20][21]也转向强化学习和博弈论，以解决利用能量收集的边缘计算等其他问题。

为用户提供服务质量(QoS)并降低货币成本。然而，这些模型需要时间才能收敛，且预热过程将导致开销。

3. 系统模型

在本节中，我们将从两个方面介绍系统模型：内在分层结构和原始决策模型。

3.1. 层次结构

如第1节所述，边缘计算旨在在数据产生的近处处理数据，以降低服务延迟、利用各层级资源并节省网络带宽。根据某些受限定义，整个边缘系统被限制在有限的地理区域内。然而，如[3][9]所分析的，边缘系统可以被扩展和泛化。边缘计算中存在两条计算流：一条从边缘服务器向上行至中心服务器；另一条从中心服务器向下行至边缘服务器。“边缘服务器”被视为沿这两条计算流的任何计算和网络资源。图1展示了这种分层结构。用户设备通过底层的边缘服务器连接到互联网，并可在多次跳转后最终到达中心服务器。用户设备与底层边缘服务器之间的连接可以是有线或无线的，而两个相邻层级的服务器之间的连接通常通过互联网骨干网实现。值得注意的是，由于物联网的发展，系统中的任何节点（包括用户设备和服务器）都可能在某种程度上同时扮演消费数据和生产数据的角色。

基于这种分层结构，每个发送到中心服务器的请求实际上在最终到达中心服务器之前，都会经过多个配备有计算资源的边缘服务器（包括生产者自身）。请求所经过的每个边缘服务器可被视为该请求经历的一跳。上述“在尽可能近的位置处理数据”可以指在尽可能少的跳数内处理数据。同时，计算卸载问题可以转化为各个服务器上的分布式决策问题：一旦请求到达，无论由谁产生，当前服务器都应决定是将其在本地处理（如果可行），还是继续传输到其“下一跳”服务器。现实中存在一种具有权衡关系的贪婪情境。可以提取出抽象模型。

由于每台服务器都可以实时独立地做出决策，上述分析的去中心化决策问题能够消除工作负载预处理，并对这些请求进行在线调度。同时，由于利用了内在分层结构，决策将不再以扁平的方式进行。此外，如[9]所证明的，分层结构在应对峰值负载时具有更高的效率。

3.2. 原始决策模型

为了便于阐述，我们首先考虑原始决策模型，这是计算卸载问题中常用的一种决策模型[6][15]。当一个服务器仅为一个到达的请求提供服务时，可以应用该模型。该服务器可以决定是本地处理此请求，还是将其卸载到下一跳服务器，而不受其他请求的影响，这意味着相关服务器上永远不会发生拥塞。拥塞的存在将在第4节中讨论。

如第1节所述，我们假设这些请求是计算密集型且延迟敏感的。它们可以在当前服务器上本地计算，也可以在下一跳服务器上远程计算。每个请求可以表示为
$$ I_i \triangleq {B_i, D_i} $$
其中，$ B_i $ 表示该请求中涉及的计算输入数据（例如输入参数和程序代码）的大小，$ D_i $ 表示完成该请求所需的总CPU周期数。这些信息可通过与[22]中使用的方法类似的方式获得。同时，我们考虑一个服务器集合 $ N={1, 2,…, N} $，它们位于整个分层结构的不同层级。每个服务器具备不同的计算能力，可以用每秒CPU周期数 $ F_i $ 来量化。需要考虑能耗和时间消耗方面的开销。

3.2.1. 通信模型

我们首先介绍通信模型，它与传输所花费的时间密切相关。

如第3.1节中分析的，系统中的连接可分为两种类型：有线连接和无线连接。前者可能出现在位于相邻层的服务器之间；后者可能出现在用户设备与位于底层的边缘服务器之间。

对于这些有线连接，通常会提供相对稳定的带宽用于卸载，可以表示为 $ \text{Wired}_i $。

对于这些无线连接，应进一步考虑不同信道的占用情况。我们使用 $ d_i \in {0, 1} $ 来描述服务器 $ i $ 所做出的决策：0 表示本地处理该请求，1 表示将该请求卸载到下一跳服务器。然后可以根据[23]计算卸载数据速率
$$
\text{Wireless} i = W \log_2\left(1 + \frac{P_i H_i}{\omega_i + \sum {m \in N\backslash{i}: d_m = 1} P_m H_m}\right)
\quad (1)
$$
其中，$ W $ 是信道带宽，$ P_i $ 是发射功率，$ H_i $ 是服务器 $ i $ 的信道增益，而 $ \omega_i $ 是背景干扰功率。

因此，通信开销可以总结为
$$
W_i =
\begin{cases}
\text{Wired}_i & \text{under wired connection} \
\text{Wireless}_i & \text{under wireless connection}
\end{cases}
\quad (2)
$$

3.2.2. 本地处理

我们接着讨论由本地处理请求引起的开销。通过此选择，当前服务器决定在本地处理请求。

计算执行时间主要导致了时间消耗开销，这可以根据
$$
T_i = \frac{D_i}{F_i}
\quad (3)
$$
然后可以根据能耗开销进行估算
$$
E_i = \nu_i D_i
\quad (4)
$$
其中 $ \nu_i $ 是每个CPU周期的能耗系数。根据一些实际测量结果[24]，$ 10^{-11}(F_i)^2 $ 可用于估计 $ \nu_i $。

基于公式(3)(4)，我们可以计算本地处理所引起的开销
$$
\text{Overhead}_{i,\text{local}} = \gamma_t \frac{D_i}{F_i} + \gamma_e 10^{-11}(F_i)^2 D_i
\quad (5)
$$
其中 $ \gamma_t $、$ \gamma_e $（$ \gamma_t + \gamma_e = 1 $ 和 $ 0 \leq \gamma_t $、$ \gamma_e \leq 1 $）分别是时间和能量消耗的权重。不同的权重可以在不同的服务器上进行配置，并且这些权重可以在运行时调整，从而提供灵活性。较低层的设备和服务器通常对能耗更为敏感，因为它们可能正在使用电池。

3.2.3. 卸载请求

我们接着讨论由卸载请求引起的开销。通过这种选择，当前服务器决定将请求卸载到其下一跳服务器。

时间消耗开销由传输时间和潜在的计算执行时间组成。可以根据以下方式估算
$$
T_i = \frac{B_i}{W_i} + \frac{D_i}{F_j}
\quad (6)
$$
这里的表达式前半部分表示将请求卸载到其下一跳服务器所花费的传输时间；而后半部分则表示在该服务器上处理请求可能消耗的计算执行时间。即使该请求可能会被进一步卸载到其他服务器，情况也不会更差，因为除非做出另一个决策，否则不会发生进一步卸载。因此，我们直接使用可能的计算执行时间来进行当前判断。

然后可以根据以下公式估算能量消耗开销
$$
E_i = P_i \frac{B_i}{W_i}
\quad (7)
$$
其中 $ P_i $ 是能耗系数。

基于公式(6)(7)，我们可以计算卸载所引起的开销
$$
\text{Overhead}_{i,\text{offload}} = \gamma_t\left(\frac{B_i}{W_i} + \frac{D_i}{F_j}\right) + \gamma_e P_i \frac{B_i}{W_i}
\quad (8)
$$
其中 $ \gamma_t $、$ \gamma_e $（$ \gamma_t + \gamma_e = 1 $ 和 $ 0 \leq \gamma_t $、$ \gamma_e \leq 1 $）分别是时间和能量消耗的权重。我们还可以对不同的服务器应用不同的权重，以提供灵活性。

与许多研究（如[9][6][15]）类似，我们也忽略了将结果传回的时间开销，因为结果的大小通常与输入数据相比非常小。

3.2.4. 决策过程

由于对原始决策模型的假设是指一个服务器只为一个到达的请求提供服务，我们可以直接根据两种选择的开销比较来做出决策。如果本地处理的开销较低，则当前服务器将选择本地处理，反之亦然，这可以表示为
$$
d_i =
\begin{cases}
0 & \text{Overhead} {i,\text{upload}} \geq \text{Overhead} {i,\text{local}} \
1 & \text{o.w.}
\end{cases}
\quad (9)
$$
此处0表示本地处理，1表示卸载。

由于在我们的假设下拥塞永远不会发生，原始决策模型始终可以正常工作。

4. 高级决策模型

在本节中，我们基于层次结构和原始决策模型构建一个先进决策模型。我们放弃前述假设，并承认拥塞可能存在的事实。

4.1. 增强决策模型

根据第3.1节的分析，当发送一个请求时，实际上会经过多个服务器，并形成一条从原始服务器到中心服务器的路径。一个请求将生成一条路径；大量请求将生成大量不同的路径。由于层次结构的存在，这些路径可能会相交。

重叠或收敛。此时位于交汇点的边缘服务器可能会因请求涌入而过载、形成任务队列，甚至发生拥塞。例如，在图1中，如果下方所有设备都决定将请求卸载到购物中心的边缘服务器，则该服务器将发生拥塞。由于更高层级的服务器更可能成为多条路径的交汇点，因此无论这些服务器通常更强大，拥塞仍可能在更高层级发生。一些传统解决方案将边缘服务器视为黑箱，假定它们能够按预期处理所有请求（类似于我们原始的决策模型）。然而在现实中，拥塞可能意外发生。其他解决方案则采用某些全局部署策略来调度这些请求。但结果是，调度变成了离线任务，且不可避免地需要进行预先建模。

避免拥塞的一个直接解决方案是在评估卸载的时间消耗开销时，额外考虑下一跳服务器的状态，以便发送方能够主动做出决策。也就是说，公式6 应修改为
$$
T_i = \frac{B_i}{W_i} + \frac{D_i + \sum D_j}{F_j}
\quad (10)
$$
其中 $ \sum D_j $ 是下一跳服务器上完成所有排队中的请求所需的总 CPU 周期数。

通过这一小改进，我们可以避免将请求推送到已经过载的下一跳服务器。

4.2. 随机早期检测的机遇

尽管增强的决策模型能有效防止服务器将请求推送给其他过载的服务器，但这还不够。在第4.1节给出的例子中，即使购物中心的边缘服务器在下方设备独立做出决策时完全空闲，它仍可能变得拥堵。这是因为这些设备获取的状态信息可能是过时的，且在决策做出后立即可能发生拥塞。

我们进一步研究了卸载过程中边缘服务器上的拥塞情况，发现其与开放系统互连（OSI）模型中网络层路由器的拥塞具有一些共同特征[25]。该请求即将被卸载的数据就像一个数据报，但尺寸要大得多。我们假设服务器上只有一个工作线程。当服务器正在处理一个请求（例如，做决策、执行计算或处理卸载请求）时，其他请求必须进入队列等待。如果队列变得过长，位于队列尾部的请求在得到服务之前将需要等待很长时间，即使该请求之后仍会被卸载。这种情况会导致延迟显著增加。如果情况进一步恶化，即服务器不再有足够的空间缓冲更多请求，服务器将不得不拒绝后续到达的请求。这种情况将导致拥塞。这两种情况都会严重损害用户体验。更直接地说，对于某些请求，特别是那些位于队列尾部的请求，在队列中等待可能完全是浪费时间。

更深层次的原因在于，尽管增强决策模型使作为发送方的当前服务器能够根据接收方的状态主动做出决策，但它也迫使作为接收方的下一跳服务器被动地接受请求。不幸的是，无论是原始决策模型还是增强决策模型，都无法让接收方意识到自身是否已经过载，因为只有当请求最终成为队列头部时（可能经过长时间等待），接收方才会处理该请求。换句话说，当服务器在接受请求时，并不会区分是否存在队列，因此可能会接受超出其处理能力的请求。

该约束的含义是，为了保持调度为一项在线任务，每个服务器只能基于独立决策进行操作，同时不可避免地存在由于传输时间导致状态信息过时的可能性。qjump[26]的理念启发了我们，“如果你能插队，队列就不再重要”。既然在队列中等待对某些请求来说完全是浪费时间，那就让它们直接且主动地插队吧！正如之前所分析的，卸载过程中边缘服务器上的拥塞与网络层路由器上的拥塞具有相似的特征，因此随机早期检测成为一个有前景的候选方案。

随机早期检测(RED)[10]，也称为随机早期丢弃或随机早期丢包，是一种著名的网络调度器队列机制，适用于拥塞避免。只有已入队的数据报才会被处理。RED通过加权移动平均来监控队列大小。平均模型根据统计概率丢弃数据报。当缓冲区为空时，它将接受所有传入的数据报。随着队列的增长，它将根据增长概率丢弃传入的数据报。当队列最终满时，丢弃概率将达到1，所有传入的数据报都将被丢弃。

在卸载的背景下，“丢弃请求”表示将其卸载到下一跳服务器，而“处理请求”则表示由当前服务器对请求做出决策。当当前服务器已经过载时，丢弃请求有助于使该请求直接插队。这也使得作为接收方的服务器能够根据自身能力选择性地接受请求。诚然，这种主动丢弃可能会将负担自私地转嫁给下一跳服务器。然而，更高层级的服务器通常具备更强的处理能力。当当前服务器和下一跳服务器都处于负载状态时，后者应承担更多责任。这并不违背边缘计算的初衷。

值得注意的是，Jacobson 等人认为随机早期检测存在两个漏洞[27]。一些研究工作，例如[28][29]，已致力于改进原始算法。然而，在卸载的背景下，允许请求插队才是关键思想。这些改进并非必要。相反，我们对其进行了其他一些修改，以使其更适应当前场景：

首先，“队列大小”的评估被改为计算完成所有已排队请求处理的预期时间。有三个考虑因素：
- 原始版本的“队列大小”会使丢弃决策对每个请求所需的计算量敏感。例如，当前服务器正在执行一个需要大量计算的请求，并且该执行将持续一段时间。此时，如果有另一个请求到达，更好的选择是尽可能插队。但由于队列中只有一个请求，“队列大小”实际上非常小，因此不会触发插队操作。相比之下，修改后的“队列大小”能够识别这种情况并做出适当的决策。
- 在做出丢弃决定时，接收器很难预测它将如何处理这些排队中的请求。其中一些请求可能稍后被卸载，而另一些则可能被执行。在本地执行。尽管存在这种多样性，但RED假设所有这些请求都将在本地执行是有效且可靠的，这样“队列大小”将按最坏情况评估。这与第3.2.3节中评估潜在计算执行时间时采用的理念一致。
- 根据每个服务器的服务级别协议（SLA），可以独立设置“队列大小”的新版本。

其次，$ \text{minth} $ 和 $ \text{maxth} $ 应相应地进行修改。为了处理计算量较大和较小的请求，我们使用
$$
\begin{cases}
\text{min} {\text{modified}} = \min{1.0, t {\text{exe,avg}}} \times \text{min} {\text{original}} \
\text{max} {\text{modified}} = \max{1.0, t_{\text{exe,avg}}} \times \text{max} {\text{original}}
\end{cases}
\quad (11)
$$
此处 $ t {\text{exe,avg}} $ 为这些排队中的请求的平均执行时间。

对于下界，当排队中的请求需要相对较大的计算量时，阈值表示绝对执行时间；当排队中的请求需要相对较小的计算量时，阈值表示 $ \text{min}_{\text{original}} $ 个请求的期望执行时间。对于上界，我们选择尽可能扩大用于计算增长概率的范围，以便当前服务器不会过早完全“拒绝”请求，从而充分利用资源。

第三，还应修改一些其他关键参数，例如 $ w_q $ 和 $ \text{maxp} $。[10]提供了一些关于设置这些参数的建议。

显然，增强决策模型的卸载更侧重于下一跳服务器的状态，而随机早期检测的卸载更侧重于当前服务器的状态。这两种增强机制相辅相成。

4.3. 综合结果

基于第4.1节和第4.2节中引入的增强机制，综合考虑了发送方和接收方的状态，以避免在卸载过程中发生拥塞。如前所述，增强决策模型负责处理进入队列的请求，而随机早期检测（RED）则旨在当当前服务器过载时丢弃请求。因此，这两种增强机制互不干扰，可分别在不同阶段应用。

我们将它们整合在一起，使它们能够和谐地协同工作：
1. 我们基于RED算法和上述描述的修改实现了一个RED过滤器。它作为每个服务器的入口。RED过滤器将从当前服务器维护的任务队列中收集队列信息(info)，并使用加权移动平均模型评估卸载的可能性。将要“丢弃”的请求会在入队之前被卸载。
2. 每个入队的请求在其成为任务队列头部时将被处理。另一个名为开销过滤器的过滤器将决定该请求是应在本地处理还是卸载到其下一跳服务器。开销过滤器将从下一跳服务器维护的任务队列中收集队列信息(info)，并采用先进决策模型。
3. 如果请求被安排在本地处理，则会将其转发到本地执行器。执行器将执行计算，然后将结果发送回去。
4. 如果请求需要被卸载，它将被传输到其下一跳服务器的入口。该请求将在那里与其他请求一起由RED过滤器进一步判断，包括被卸载到该服务器的请求以及由该服务器自身生成的请求。

5. 评估

在本节中，我们实现了高级决策模型，并通过模拟实验对其性能进行评估。首先，在严格对称的层次拓扑上应用高级决策模型，并将其性能与其他决策模型进行比较。然后，我们使用偏斜测试用例（包括偏斜请求和偏斜拓扑）对我们的模型进行评估。

5.1. 仿真设置

如图3所示，我们创建了一个严格的对称层次拓扑。这种简单结构可以简化结果分析。同时，根据基于trace的仿真结果，在[9]中也推荐使用这种三层边缘云，相较于另外两种简单的分层结构。每个服务器下方标注的数字表示其索引号（id）和相应的可用计算资源。我们特意为第三层的服务器提供了更多的计算资源，因为中心服务器通常比边缘服务器强大得多。$ \gamma_t $ 与 $ \gamma_e $ 的比率（分别为时间消耗和能耗的权重）设置为 Comp_available:1，因为强大的服务器通常位于较高等级，很少担心能源不足的问题。这些连接的带宽设置为100 Mbps。

一个任务生成器负责定期向第一层的服务器推送请求。每个周期内的请求数量（表示工作负载率）遵循泊松分布确定。每个请求的所需计算量（表示请求大小）进一步遵循正态分布确定。

不失一般性，我们选择请求的平均完成时间作为性能指标，如[9]所做的那样。较小的平均完成时间表明整个系统提供的计算容量更大。同时，我们还记录了每个服务器处理的请求数量，用于辅助分析。

我们通过将高级决策模型与纯云计算和纯本地处理进行比较，来验证边缘计算的性能。在纯云计算中，每个请求都会被卸载到中心服务器，就像我们在日常生活中所做的那样；而在纯本地处理中，数据的生成者将自行在本地处理请求。我们还通过将集成版本与两个非完整版本进行比较，来验证上述增强的有效性。在以下描述中，第一项增强指第4.1节中介绍的增强；第二项增强指第4.2节中介绍的增强。总之，我们通过四项受控实验来评估高级决策模型。

5.2. 仿真结果

5.2.1. 工作负载率和请求大小的影响

进行了两组实验。首先，我们固定泊松分布的 $ \lambda = 8 $，并将正态分布的 $ \mu $ 从1变化到9（$ \sigma^2 $ 固定为1）。图4展示了高级决策模型的平均完成时间以及比较的归一化结果。其次，我们固定正态分布的 $ \mu = 7 $（$ \sigma^2 $ 固定为1），并将泊松分布的 $ \lambda $ 从2变化到10。图5展示了高级决策模型的平均完成时间以及比较的归一化结果。

如图所示，高级决策模型的平均完成时间随着工作负载率或请求大小的增加而线性增长。这表明没有发生过度拥塞。否则，平均完成时间将以更剧烈的方式激增。

显然，根据归一化结果，在这两组实验中，高级决策模型在这五个模型中始终表现最佳。尽管在图4中，纯本地计算在 $ \mu = 1 $ 下的归一化平均完成时间似乎异常地大于其他情况。

这是可以解释的，因为记录每个服务器处理请求数量的数据显示，当时生成了偏斜请求。因此，高级决策模型相较于其他模型具有相对稳定的优势。

5.2.2. 性能比较

然后我们进行比较在整个解空间中，这意味着我们将正态分布的 $ \mu $ 从1变为9（$ \sigma^2 $ 固定为1），将泊松分布的 $ \lambda $ 从2变为10，并对每种组合进行比较。

图6展示了由每个服务器（以其索引标记）处理的请求百分比。如预期所示，纯本地计算将所有请求调度到底层的服务器；纯云计算将所有请求调度到中心服务器。由于不同服务器的计算能力与相应连接带宽之间的关系，未包含第一项增强的模型也将所有请求调度到中心服务器。由于我们未考虑各服务器可用能耗的变化，只要系统设置在最初确定后，该模型就会进行均匀调度，而不管这些服务器在运行时的实际状态如何。未包含第二项增强的模型的调度方式与先进决策模型类似。细微差别在于第二层的服务器，即具有id=1,2的服务器。高级决策模型会将更多的请求调度到这些服务器。

这源于以下事实：根据RED机制，部分请求可以插队进入底层服务器的队列。然而，从第二层向中心服务器的插队行为并不频繁，因为第二层的服务器性能更强，不像底层服务器那样容易过载。

图7展示了平均完成时间的归一化结果。纯本地计算表现最差，因为它从不利用其他服务器的计算资源，容易过载。在我们的设置下，未采用第一项增强的模型由于决策开销，表现甚至比纯云计算更差。未采用第二项增强的模型表现不如高级决策模型，这一事实验证了前述分析，并证明了跳跃的有效性（性能提升超过20%）。显然，高级决策模型在整个解空间中表现最佳。

我们使用公式12来近似估计在高级决策模型下排队中的请求的平均数量 $ \bar{n} $。图8展示了在不同模型和不同工作负载下的结果。$ \mu $ 的不同值对队列长度影响较小，这表明我们在第4.2节中提到的对“队列大小”的修改是有效的；而 $ \lambda $ 的不同值则具有显著影响，这是合理的，因为 $ \lambda $ 决定了工作负载率。

$$
\frac{\sum n_i(n_i + 1)}{2 \cdot \text{size_avg}} \cdot \frac{1}{\text{computation} i} \sum n_i = \text{ExeTime} {\text{avg}}
\quad (12)
$$

5.3. 不同影响的评估

5.3.1. 偏斜测试用例的影响

除了上述同质测试用例外，我们还使用偏斜测试用例评估了我们的模型，包括偏斜请求和偏斜拓扑。

在生成倾斜工作负载时，我们重用对称层次拓扑，并在任务生成器中为不同服务器设置不同的权重。具体而言，我们在 ID 为 = 3、4、5、6 的服务器上分别生成比例为 1:2:3:4 的任务，从而使所有 3 个层级的工作负载呈现倾斜。为了便于比较，各服务器上的计算资源供给保持不变。

在生成偏斜拓扑时，我们采用巴尔巴西-阿尔伯特模型[30]，根据优先连接机制生成随机无标度网络，如[16][31]所做的那样。由于生成的拓扑不再对称，因此可能出现偏斜的工作负载。为了便于比较，我们仍然生成包含7个节点的网络，并保持总的计算资源不变。如图9所示，我们总共生成了五个随机网络，并分别标记为BA-1、BA-2、BA-3、BA-4和BA-5。由于任务生成器在底层有更多的服务器时会生成更多的任务，因此任务总数会有所波动。

为了减轻此类波动的影响，将比较对象设置为相对于生成的平均计算量的平均完成时间。比较在整个解空间中进行，第5.2节中讨论的设置作为基准。图11展示了归一化结果。差异均小于10%，因此偏斜请求和偏斜拓扑均未产生显著影响。我们的先进决策模型对偏斜工作负载具有鲁棒性。图11显示了由每台服务器解决或在每台服务器上生成的请求百分比。

5.3.2. 其他因素的影响

我们还比较了不同条件下的性能。

不同工作负载类型下的表现。图12展示了归一化结果。不同类型工作负载的结果彼此相似，因此这五种模型对工作负载类型不敏感。高级决策模型表现最佳。

我们比较了不同RED阈值下的性能。图13展示了RED在minth、maxth=5.0, 40.0条件下相对于minth、maxth=5.0, 20.0条件的相对性能。当工作负载较轻时，较窄的阈值范围效果更好，因为它可以以更高的概率丢弃请求；当工作负载较重时，较宽的阈值范围效果更好，因为它可以在拒绝更多请求之前容忍更长的队列。这两种设置之间的总体差异仅为0.2%。因此，高级决策模型在不同阈值下具有较强的鲁棒性。然而，不同的阈值可以适应不同趋势的工作负载。

6. 结论和未来工作

本文中，我们提出一种先进决策模型来解决边缘计算中的计算卸载问题。该决策模型基于内在层次结构工作，并对传入的请求进行在线调度。它承认即使在决策做出后，信息仍可能过时，且拥塞可能意外发生。因此，该模型通过两种增强机制旨在避免拥塞，以实现双向主动卸载。仿真的结果表明，我们的方法能够很好地处理工作负载，且这两种增强机制是有效的。

还有另一种应用场景，即中心服务器可能需要边缘服务器提供帮助。高级决策模型可以本能地支持这种场景，但仍需进一步研究以取得进展。