移动边缘计算系统的动态服务请求调度

1. 引言

随着信息技术的快速发展和终端设备的不断推广[1],，在终端设备上运行的移动服务（应用）变得越来越复杂且计算密集[2,3]。然而，终端设备的计算能力和电池续航通常有限，无法在本地完全处理所有这些服务请求。

为解决这一问题，一些研究提出将服务请求从终端设备卸载到拥有更多计算资源和更大容量的云计算平台[4–8]。但云计算通常位于远离终端设备的远程位置。此外，随着终端设备上运行的移动服务日益普及，将所有卸载的服务请求调度至云计算会给网络带来显著负担[9, 10]。

为应对这一挑战，近期研究提出在网络边缘部署具备计算能力的边缘服务器，使其靠近终端设备。移动边缘计算（MEC）正是基于这一理念而兴起的技术[11–14]，并且引起了学术界和工业界的广泛关注[15–18]。

在移动边缘计算研究中的一个关键问题是如何调度服务请求[2, 19, 20]：当大量服务请求被卸载时，如何在多个移动边缘计算系统之间调度服务请求，以降低调度成本的同时提供性能保障。直观来看，调度成本与性能之间存在权衡。此外，由于多种原因，在多个 MEC系统之间的服务请求调度问题具有挑战性。首先，由于终端设备处于移动状态且服务环境随时间变化[21, 22],，如何根据请求模式的不确定性以及变化的环境做出动态请求调度决策是一个巨大的挑战[23]。其次，随着终端设备和移动服务的推广不断推进，终端设备和移动服务的数量急剧增加，使得服务请求调度问题更加复杂。

一些现有的研究已经探讨了MEC系统中的服务请求调度问题。文献[24]将移动边缘计算系统中的服务器建模为一个 M/M/1队列。[2]假设卸载的移动服务请求以泊松过程到达多接入边缘计算系统。这些研究假设请求到达遵循某种分布。然而，在现实中，请求到达过程高度动态，且请求到达的统计信息难以获取或精确预测[25, 26]。此外，随着终端设备和移动服务数量的增加，传统的集中式优化技术（如组合优化和动态规划）可能面临高复杂度问题，导致执行时间过长。

本文中，我们提出一种动态在线服务请求调度机制，该机制无需请求到达的统计信息。具体而言，多个 MEC系统之间的请求调度被建模为一个优化问题，目标是最小化请求调度成本的同时提供性能保障。基于李雅普诺夫优化技术，我们提出了一种动态服务请求调度（DSRS）算法。DSRS使用参数 V来控制调度成本与队列长度之间的权衡。本文给出了数学分析，证明了 DSRS在平均调度成本方面是 O(1/V)‐最优的，同时仍将平均队列长度限制在 O(V)以内。实验结果表明，DSRS能够做出动态控制决策以适应可变环境，并实现调度成本与队列长度之间的权衡。

本文其余部分组织如下：第2节介绍多个MEC系统之间动态请求调度的系统模型，并对优化问题进行建模；第3节基于李雅普诺夫优化技术，提出一种在线动态服务请求调度算法；第4节给出该调度算法的理论分析；第5节通过实验评估该调度算法的效率和有效性；第6节对本文进行总结。

2. 系统模型

2.1. 概述

考虑 n移动边缘计算（MEC）系统。每个 MEC系统均配备一个边缘服务器，该服务器被虚拟化为m个虚拟机，用于处理来自终端设备的m种类型服务的卸载请求[25, 27]。具体而言，MEC系统中每个边缘服务器上的第i个虚拟机负责处理第 i类服务的卸载请求。

令 I表示应用程序索引集合， J表示MEC系统中边缘服务器索引集合。不失一般性，假设不同MEC系统中的边缘服务器是异构的。我们采用时隙模型，时隙长度记为τ。本节的主要符号列于表1。

2.2. 问题建模

2.2.1. 服务请求调度

在每个时隙 t ∈{0,1,..,T −1}中，会卸载多种服务类型的若干服务请求。设A i( t)表示在时隙 t内卸载到MEC系统的服务 i的请求数量。在本文中，我们不需要事先了解Ai(t)的统计信息，而这在现实生活中通常难以获取或精确预测。aij(t)表示在第 j个移动边缘计算系统中，于时隙 t被调度到边缘服务器的服务 i的请求数量。aij(t)是请求调度控制变量。应满足以下条件：

$$
\sum_{j \in J} a_{ij}(t) = A_i(t), \quad \forall i \in I. \tag{1}
$$

本文中的请求调度方法将利用不同MEC系统的多样性来提供服务，以在提供性能保障的同时降低调度成本。

2.2.2. 调度成本

设γij(t)为将服务 i的请求调度到第 j个移动边缘计算系统的单位成本。γij(t)在不同服务 i和不同MEC系统 j之间可能不同，也可能由于流量、无线衰落、可用资源等因素随时间变化。服务 i在时隙 t的请求调度成本可计算为∑j∈J γij(t) aij(t)。所有服务的总调度成本可表示为

$$
g(t) = \sum_{i \in I} \sum_{j \in J} \gamma_{ij}(t)a_{ij}(t). \tag{2}
$$

我们不研究瞬时调度成本，而是关注长期平均成本。跨时隙 t ∈{0, 1, …, T − 1}的时间平均调度成本可表示为

$$
g = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}{g(t)}. \tag{3}
$$

g是本文请求调度问题的最小化目标。

2.2.3. 性能

排队延迟是最重要性能指标之一。根据利特尔定律，排队延迟与队列中等待的请求数量成正比。因此，我们力求减少队列长度并维持低拥塞状态。设Qij(t)表示在时隙 t中第 j个MEC系统的服务 i的队列长度。bij(t) 表示第j个MEC系统能够服务的服务 i的请求数量。因此，队列长度Qij(t) 的演化如下

$$
Q_{ij}(t+1) = \max[Q_{ij}(t) - b_{ij}(t), 0] + a_{ij}(t). \tag{4}
$$

为了减少排队延迟并维持系统稳定性，我们力求限制平均队列长度。设 t ∈{0,1, …, T − 1} 时隙内的时平均队列长度由 qij 表示。本文中的服务请求调度方法将平均队列长度限制为

$$
q_{ij} = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}{Q_{ij}(t)} < \zeta, \quad \exists \zeta \in \mathbb{R}^+. \tag{5}
$$

表1：符号和定义。

符号	定义
I	服务集合。
J	MEC系统集合。
Ai(t)	服务i在时隙 t内的请求数量。
aij(t)	在时隙 t中被调度到第j个移动边缘计算系统的服务i的请求数量。
bij(t)	在时隙 t中可由第 j个移动边缘计算系统提供服务的服务i的请求数量。
γij(t)	服务i的请求调度到第j个移动边缘计算系统的单位成本。
Qij(t)	第 j个移动边缘计算系统中服务i在时隙 t的队列长度。
g(t)	时隙 t 中所有服务的调度成本

2.2.4. 统一框架

为了结合调度成本和性能，本文将请求调度问题表述为

$$
\text{minimize } g = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}{g(t)}; \tag{6}
$$

满足约束(1)、(5)。

离线求解问题(6)需要未来的相关信息（如请求到达信息、调度成本信息），而这些信息在实际中通常难以获取或精确预测。因此，我们提出一种在线动态服务请求调度算法来解决该问题，该算法将在第3节中给出。

3. 动态请求调度算法设计

在本节中，基于李雅普诺夫优化框架[28],，我们将原始优化问题分解为一系列独立的子问题。然后，我们设计了一种动态服务请求调度算法，以分布式方式求解这些子问题。

3.1 基于李雅普诺夫技术的问题转换

基于李雅普诺夫优化技术，我们定义 Θ(t) = (Qij(t)) 为 MEC系统的队列长度矩阵。然后，我们将 L(Θ(t)) 表示为李雅普诺夫函数，如下所示，其为系统中队列拥塞状态的标量度量，

$$
L(\Theta(t)) = \frac{1}{2} \sum_{i \in I} \sum_{j \in J} Q_{ij}^2(t). \tag{7}
$$

L(Θ(t)) 的值较小时，表明所有MEC的队列长度较小，根据利特尔定律，这代表MEC系统处于低拥塞状态。为了减小队列长度并维持系统稳定性，我们希望将李雅普诺夫函数保持在较小的值。接着，我们定义条件李雅普诺夫漂移Δ(Θ(t))，

$$
\Delta(\Theta(t)) = \mathbb{E}{L(\Theta(t+1)) - L(\Theta(t)) \mid \Theta(t)}. \tag{8}
$$

通过减小 Δ(Θ(t))的值，我们可以使李雅普诺夫函数趋近于一个较小的值。为了在MEC系统中整合调度成本和队列长度，我们根据李雅普诺夫优化框架定义漂移加成本，其表达式为

$$
\Delta(\Theta(t)) + V\mathbb{E}{g(t) \mid \Theta(t)}. \tag{9}
$$

参数 V可以被视为调度成本与队列长度之间的权衡参数，服务提供商或用户可根据实际应用中的需求来确定该参数。接下来在定理1中，我们证明如果服务到达率有上界，则漂移加成本也有上界。

定理1 （漂移加成本的界）。 在每个时隙 t 中，在任何算法下，对于所有可能的 Θ（t） 值以及任意的 V 参数值，如果存在一个峰值 Amax i 能够上界化每个时隙中到达的请求数量，则漂移加成本可被上界化为

$$
\Delta(\Theta(t)) + V\mathbb{E}{g(t) \mid \Theta(t)}
\leq B + \sum_{i \in I} \sum_{j \in J} Q_{ij}(t)\mathbb{E}{a_{ij}(t) - b_{ij}(t) \mid \Theta(t)} + V\sum_{i \in I} \sum_{j \in J} \mathbb{E}{a_{ij}(t)\gamma_{ij}(t) \mid \Theta(t)},
\tag{10}
$$

其中 $ B = \frac{1}{2}[\sum_{i \in I}(A^{\text{max}} i)^2 + \sum {i \in I} \sum_{j \in J} \hat{b}_{ij}^2] $ 是一个常数。

证明。 通过对(4)式的两边平方，并应用不等式（$\max[Q_{ij}(t) - b_{ij}(t), 0]$）² ≤ $(Q_{ij}(t) - b_{ij}(t))^2$，我们得到

$$
Q_{ij}^2(t+1) \leq (Q_{ij}(t) - b_{ij}(t))^2 + a_{ij}^2(t) + 2a_{ij}(t)\max[Q_{ij}(t) - b_{ij}(t), 0]. \tag{11}
$$

然后，我们定义 $ b_{ij}(t) $ 为第 j个多接入边缘计算系统在时隙 t中为服务 i实际处理的请求数量，

$$
b_{ij}(t) =
\begin{cases}
b_{ij}(t), & b_{ij}(t) \leq Q_{ij}(t) \
Q_{ij}(t), & \text{otherwise}.
\end{cases}
\tag{12}
$$

我们可以得到 $\max[Q_{ij}(t) - b_{ij}(t), 0] = Q_{ij}(t) - b_{ij}(t)$，并将 (11) 重写如下：

$$
Q_{ij}^2(t+1) \leq Q_{ij}^2(t) + a_{ij}^2(t) + b_{ij}^2(t) + 2Q_{ij}(t)(a_{ij}(t) - b_{ij}(t)) - 2a_{ij}(t)b_{ij}(t). \tag{13}
$$

因为 $ a_{ij}(t)b_{ij}(t) \geq 0 $，我们有

$$
\frac{1}{2}[Q_{ij}^2(t+1) - Q_{ij}^2(t)] \leq \frac{1}{2}[a_{ij}^2(t) + b_{ij}^2(t)] + Q_{ij}(t)[a_{ij}(t) - b_{ij}(t)]. \tag{14}
$$

对(14)式两边关于 Θ(t)的条件取期望，并对 i ∈ I 和 j ∈ J求和，可得

$$
\Delta(\Theta(t)) \leq \frac{1}{2} \sum_{i \in I} \sum_{j \in J} \mathbb{E}{a_{ij}^2(t) + b_{ij}^2(t) \mid \Theta(t)} + \sum_{i \in I} \sum_{j \in J} Q_{ij}(t)\mathbb{E}{a_{ij}(t) - b_{ij}(t) \mid \Theta(t)}. \tag{15}
$$

由于 $\sum_{j \in J} a_{ij}(t) = A_i(t)$ 且 $A_i(t) \leq A^{\text{max}}_i$ 成立，因此我们有

$$
\sum_{j \in J} \mathbb{E}{a_{ij}^2(t) \mid \Theta(t)} \leq \mathbb{E}{A_i^2(t) \mid \Theta(t)} \leq (A^{\text{max}}_i)^2. \tag{16}
$$

此外，我们定义 $\hat{b} {ij}$ 为 $b {ij}(t)$ 在所有时隙上的上界。我们可以得到

$$
\sum_{i \in I} \sum_{j \in J} \mathbb{E}{a_{ij}^2(t) + b_{ij}^2(t) \mid \Theta(t)} \leq \sum_{i \in I} (A^{\text{max}} i)^2 + \sum {i \in I} \sum_{j \in J} \hat{b}_{ij}^2. \tag{17}
$$

通过在两边同时加上 $V\mathbb{E}{g(t) \mid \Theta(t)}$，并令 B取值为$(1/2)[\sum_{i \in I}(A^{\text{max}} i)^2] + \sum {i \in I} \sum_{j \in J} \hat{b}_{ij}^2$，可得

$$
\Delta(\Theta(t)) + V\mathbb{E}{g(t) \mid \Theta(t)}
\leq B + V\mathbb{E}{g(t) \mid \Theta(t)} + \sum_{i \in I} \sum_{j \in J} Q_{ij}(t)\mathbb{E}{a_{ij}(t) - b_{ij}(t) \mid \Theta(t)}. \tag{18}
$$

将(2)代入(18)的右侧（R.H.S.），可得(10)。

3.2. 动态请求调度算法

根据李雅普诺夫优化技术的设计原则，我们设计了一种高效的动态服务请求调度（DSRS）算法，以最小化每个时隙 t中漂移加成本的上界。通过分解该最小化问题，将上界问题分解为一系列独立的子问题后，我们的 DSRS算法以分布式方式同时优化平均调度成本。此外，将证明DSRS算法能够实现长期时间平均调度成本任意接近最优值，同时保持MEC系统的稳定性。

在每个时隙 t，基于MEC系统的当前队列长度矩阵 Θ(t)，DSRS算法做出请求调度决策 aij(t)，以最小化 (10)式右端的上界。由于 B和bij在优化问题中可视为常数，因此可将上界最小化重写为

$$
\min_{a_{ij}(t)} \sum_{i \in I} \sum_{j \in J} a_{ij}(t)Q_{ij}(t) + Va_{ij}(t)\gamma_{ij}(t). \tag{19}
$$

受限于

$$
\sum_{j \in J} a_{ij}(t) = A_i(t), \quad \forall i \in I. \tag{20}
$$

由于不同服务之间的请求调度决策 aij(t) 相互独立，上述集中式最小化问题（19）可分解为针对每个服务 i ∈I 的如下子问题（21），即

$$
\min_{a_{ij}(t)} \sum_{j \in J} a_{ij}(t)(Q_{ij}(t) + V\gamma_{ij}(t)). \tag{21}
$$

受限于

$$
\sum_{j \in J} a_{ij}(t) = A_i(t). \tag{22}
$$

问题(21)可被视为一个广义最小权重问题，其中调度到MEC系统的请求数量由$Q_{ij}(t) + V\gamma_{ij}(t)$的值加权。因此，对于每个服务 i ∈ I，最优解是将所有请求调度到具有最小$Q_{ij}(t) + V\gamma_{ij}(t)$值的MEC系统；即

$$
a_{ij}(t) =
\begin{cases}
A_i(t), & j = j^* \
0, & \text{otherwise}
\end{cases}
\tag{23}
$$

其中 $j^* \in \arg\min(Q_{ij}(t) + V\gamma_{ij}(t))$ 对所有 $j \in J$。

备注。 在MEC系统的调度成本和队列长度之间存在权衡。将所有服务请求调度到成本较低的MEC系统可以降低总体调度成本；然而，该MEC系统的队列长度可能变得非常大。DSRS算法结合了调度成本和队列长度，$Q_{ij}(t) + V\gamma_{ij}(t)$ 可被视为每个MEC系统的惩罚因子。回顾一下，V表示调度成本与队列长度之间的权衡。通过DSRS算法获得的最优调度策略的直观思路是在每个时隙中最小化MEC系统的惩罚函数。这样，DSRS算法能够同时降低调度成本和队列长度。此外，通过改变V的值，DSRS算法可以实现调度成本与队列长度之间的任意权衡。

在确定调度决策aij(t)后，队列长度Qij(t)根据式(4)进行更新。详细算法如算法1所示。

4. 算法分析

在本节中，我们对DSRS算法的时平均队列长度和调度成本的边界进行数学分析。可以证明，我们的算法能够在保持MEC系统稳定性的同时，使调度成本任意接近最优值。设{v3}表示长期时平均队列长度，

$$
Q = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \sum_{i \in I} \sum_{j \in J} \mathbb{E}{Q_{ij}(t)}. \tag{24}
$$

我们在引理2中指出，如果到达Ai(t)在时隙上是独立同分布(i.i.d.)的，则存在一种随机化策略π∗，能够实现式(3)所定义的最小成本g∗，其中控制决策aij(t)遵循与队列长度矩阵 Θ(t)无关的某个固定概率分布。

引理2。 对于任意服务请求到达率 λ ∈ Λ，其中Λ是系统的容量区域，如果请求到达A i( t)在时隙上是独立同分布的，则存在一个随机化策略 π∗，该策略在每个时隙 t 确定控制决策 aij (t)，并实现以下目标：

$$
\mathbb{E}{g^{\pi^ }(t)} = g^ (\lambda);
$$
$$
\mathbb{E}\left{\sum_{j \in J} a^{\pi^*} {ij}(t)\right} \leq \mathbb{E}\left{\sum {j \in J} b_{ij}(t)\right}.
\tag{25}
$$

其中 g∗(λ)表示在到达率 λ 下的最小时均成本。

证明。 引理2 可通过 [28], 中的卡拉西奥多里定理证明，为简洁起见，此处省略详细证明。

由于假设服务请求到达率存在上界 Amax i ，因此目标 g也存在上界ĝ和下界 g。̌然后，我们基于引理2推导 DSRS算法的队列长度和调度成本的边界。

定理3。 假设存在满足 λ+ ε ∈ Λ的 ε，则在我们的DSRS算法下，对于参数V的任意取值，(24)中定义的时平均队列长度有界如下

$$
Q \leq \frac{B + V(\hat{g} - \check{g})}{\varepsilon}. \tag{26}
$$

此外，时均系统调度成本可以由(27)进行界定，这表明通过增加参数 V，我们DSRS算法所产生的成本可以接近最优值。其中， B是定理1中定义的常数。

$$
g_{\text{DSRS}} \leq g^* + \frac{B}{V}. \tag{27}
$$

证明。 由于 λ+ ε ∈ Λ成立，根据引理2，我们可以得到存在一个随机策略π󸀠满足(28)和(29)。

$$
\mathbb{E}{g^{\pi’}(t)} = g^*(\lambda + \varepsilon); \tag{28}
$$
$$
\mathbb{E}\left{\sum_{j \in J} a^{\pi’} {ij}(t)\right} \leq \mathbb{E}\left{\sum {j \in J} b_{ij}(t)\right} - \varepsilon. \tag{29}
$$

由于我们的DSRS算法能够在所有可行策略（包括策略π󸀠）中实现(10)式右边的最小值，因此可以得出

$$
\Delta(\Theta(t)) + V\mathbb{E}{g(t) \mid \Theta(t)}
\leq B + V\mathbb{E}{g^{\pi’}(t) \mid \Theta(t)} + \sum_{i \in I} \sum_{j \in J} Q_{ij}(t)\mathbb{E}{a^{\pi’} {ij}(t) - b {ij}(t) \mid \Theta(t)}. \tag{30}
$$

将(28)和(29)代入(30)的右端，对两边取期望，然后利用迭代期望，可得

$$
\mathbb{E}{L(\Theta(t+1)) - L(\Theta(t))} + V\mathbb{E}{g(t)}
\leq B + Vg^*(\lambda + \varepsilon) - \varepsilon \sum_{i \in I} \sum_{j \in J} \mathbb{E}{Q_{ij}(t)}. \tag{31}
$$

将 $V\mathbb{E}{g(t)}$ 移至(31)的右端，可得

$$
\mathbb{E}{L(\Theta(t+1)) - L(\Theta(t))}
\leq B + V(g^*(\lambda + \varepsilon) - \mathbb{E}{g(t)}) - \varepsilon \sum_{i \in I} \sum_{j \in J} \mathbb{E}{Q_{ij}(t)} \leq B + V(\hat{g} - \check{g}) - \varepsilon \sum_{i \in I} \sum_{j \in J} \mathbb{E}{Q_{ij}(t)}. \tag{32}
$$

为了具有一般性，我们假设当t= 0时队列长度为空。对(32)两边在 t ∈{0,1,…,T −1}上求和，并应用 L(Θ(t)) ≥ 0这一事实，可得

$$
\varepsilon \sum_{t=0}^{T-1} \sum_{i \in I} \sum_{j \in J} \mathbb{E}{Q_{ij}(t)} \leq (B + V(\hat{g} - \check{g}))T - \mathbb{E}{L(\Theta(T))} \leq (B + V(\hat{g} - \check{g}))T. \tag{33}
$$

将(33)两边除以εT并取T →∞时的极限，得到(26)。

对(31)两边在t ∈{0,1,…,T −1}上求和，并应用$\mathbb{E}{Q_{ij}(t)} \geq 0$这一事实，可得

$$
V \sum_{t=0}^{T-1} \mathbb{E}{g(t)} \leq (Vg^*(\lambda + \varepsilon) + B)T. \tag{34}
$$

将(34)的两边同时除以VT，我们得到

$$
\frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}{g(t)} \leq g^*(\lambda + \varepsilon) + \frac{B}{V}. \tag{35}
$$

对(35)取 T → ∞的极限，应用勒贝格控制收敛定理，并令 ε → 0得到(27)。

备注。 定理3表明，我们的DSRS算法能够在时间平均调度成本与队列长度之间实现[O(1/V),O(V)]权衡。根据 (27)，我们的DSRS算法所得的时间平均调度成本与最优值之间的差距在 O(1/V)范围内。通过将 V的值设置得足够大，DSRS算法可以逼近最优调度成本。然而，过大的V会导致MEC系统的队列积压显著增加。尽管如此，根据 (26)，我们DSRS算法所获得的队列长度也是有界的。并且，通过让 ζ取值为(B + V(ĝ − ǧ))/ε，可满足约束(5)。

然后，我们分析DSRS算法的时间复杂度。根据算法1，对于两个内层循环（第5‐10行和第11‐17行），DSRS算法对每个边缘服务器遍历一次。因此，每个循环在 O(n)次操作内终止，其中 n是边缘服务器的数量。对于外层循环（第1‐18行），由于不同服务应用的请求调度相互独立，它在O(n)次操作内终止。因此，DSRS算法的时间复杂度为 O(n)。

5. 评估

在本节中，我们通过实验评估了我们的DSRS算法。首先，我们分析了参数的影响。然后，我们展示了对比实验，结果表明了我们的DSRS算法的有效性。

在实验中，我们考虑了4个MEC系统，每个系统均有一个边缘服务器为卸载的请求提供服务。存在两种类型的异构服务。对于每种服务 i ∈ I，请求到达过程根据到达率为λi[29]的泊松分布生成。需要注意的是， DSRS算法实际上不需要了解请求到达的统计信息。

MEC系统的计算能力设置为βi ⋅λi，其中βi> 1。不失一般性，我们假设这些MEC系统具有不同计算能力，因而是异构的。不同MEC系统的单位调度成本设定为其计算能力的正相关函数。

5.1. 参数分析

5.1.1. 权衡参数的影响

图1和图2显示了具有不同 V值的MEC系统的时间平均调度成本和队列长度。从图1可以看出，随着V值的增加，调度成本降低，这与定理3中的(27)一致。这是因为随着 V增大，调度成本所占比重更高，DSRS算法会将更多的服务请求调度到单位成本较低的MEC系统中，以降低总体调度成本。然而，图2显示队列长度也随着 V的增加而上升，这与定理3中的(26)相符。尽管如此，当V进一步增大时，队列长度将逐渐趋于稳定。结合图1和图2可以看出，DSRS算法通过调整 V的值，能够在调度成本与队列长度之间实现权衡。

5.1.2. 服务请求到达率的影响

我们分析了服务请求到达率对调度成本的影响。在实验中，对于每个应用 i ∈ I，我们将服务请求到达率按p ⋅λi进行缩放。我们考虑了三种不同情况，分别为 p= 1、1.2和1.4。图3和图4显示，随着请求到达率的增加，调度成本和队列长度均有所上升。然而，队列长度能够随着服务请求到达率的增加而快速稳定下来。这表明我们的DSRS算法能够根据不同服务请求到达情况动态调整请求调度决策，并维持MEC系统的稳定性。

5.1.3. 单位调度成本的影响

为了分析单位调度成本对 MEC系统的影响，我们将单位调度成本按q ⋅ γij进行放大或缩小。我们考虑了三种不同情况，分别为 q= 1、1.2和1.4。从图5可以看出，随着单位调度成本的增加，总体调度成本上升，因为每个请求的调度成本增加了。在图6中，我们可以看到MEC系统的队列长度也随着单位调度成本的增加。原因是我们的DSRS算法通过将更多请求调度到单位调度成本较小的MEC上来实现较低的调度成本。然而，这将导致某些MEC系统中的队列积压增大。

5.2. 对比实验

我们进行了对比实验，将DSRS算法与随机化算法进行比较，以评估DSRS算法的有效性。随机化算法将所有服务请求随机调度到各个MEC系统。

两种算法的调度成本和队列长度分别如图7和图8所示。从图7可以看出，我们提出的DSRS算法的调度成本低于随机化方法的调度成本，这表明了我们的DSRS算法在降低成本方面的有效性。从图8中可以看出，在最开始时，随机化算法的队列长度略小于我们的DSRS算法。然而，随着时间推移，随机化算法的队列长度持续增加。而我们的 DSRS算法的队列长度则迅速稳定并保持在较低水平。原因是我们的DSRS算法能够根据当前的队列积压动态调整调度决策，并在MEC系统中维持低拥塞状态。结合图7和图8可以看出，我们的DSRS算法在优化调度成本和队列长度方面均表现出良好的有效性。

6. 结论

在本文中，我们研究了MEC系统的动态请求调度。我们将该问题建模为一个优化问题，目标是在提供性能保证的同时优化调度成本。我们提出了DSRS算法来解决该优化问题，该算法将其转化为一系列子问题，并以分布式方式高效地求解每个子问题。文中给出了数学分析，证明了DSRS算法能够在限制队列长度的同时逼近最优调度成本。通过参数分析实验和对比实验验证了 DSRS算法的有效性。