在移动边缘计算中学习卸载

摘要

计算卸载是移动边缘计算（MEC）系统中的一项有前景的技术。本文考虑了系统动态和用户移动性，将移动计算卸载建模为一个随机最优控制问题。一方面，当系统信息完全已知时，我们推导出最优卸载策略；另一方面，在系统信息受限的情况下，我们设计了一种Q学习算法，该算法虽收敛速度较慢，但仍能实现最优系统性能。为了加快收敛速度并应对更复杂的系统，我们进一步开发了一种基于深度Q网络（DQN）的算法。仿真结果表明，我们提出的基于DQN的算法确实具有快得多的收敛速度。

索引术语 —移动边缘计算，计算卸载，马尔可夫决策过程，在线学习。

一、引言

作为一种有前景的计算卸载（也称为任务卸载）技术，移动边缘计算（MEC）近年来在学术界和工业界均受到广泛关注[2]。已有大量关于MEC的研究文献。例如，在满足计算延迟约束条件下，文献[3]通过计算卸载最小化了系统能耗。文献[4],提出了一种从移动设备到边缘设备的卸载优化框架，并设计了一种有效算法以同时最小化能耗和执行延迟。在文献[3]和[4],中，计算卸载被建模为一个确定性优化问题，作者主要关注单个任务处理的短期性能。事实上，在许多情况下，长期收益更具意义。因此，需要开发随机计算卸载策略。例如，在文献[5]和[6],中，采用随机规划方法以最大化系统的长期平均效用。

特别地，利用李雅普诺夫优化方法将随机规划问题转化为序列决策问题，使得每个时隙仅涉及一系列确定性问题。在我们之前的工作[7],中，提出了一种高效的基于老虎机学习的算法，用于在非平稳网络中平衡系统参数的学习与延迟最小化之间的关系。

在[5]–[7],中，假设用户（即任务节点）是固定的，没有任何移动性。实际上，大多数用户处于移动状态。因此，考虑用户动态以及用户在移动过程中可能经历不同的邻近节点更具意义。此外，不同节点通常具有不同的计算能力。在用户具有移动性的情况下，最优的任务卸载策略将变得高度非线性。

在[8]–[11]中被视为一个平凡问题。文献[11]研究了一种长期文件传输应用中的Wi‐Fi卸载，其中用户在一个具有无缝蜂窝连接和间歇性Wi‐Fi连接的网络中移动。给定用户移动模式后，任务卸载问题转化为马尔可夫决策过程（MDP），并可求得具有最优性的解。然而，在大多数应用中，用户移动模式通常无法预先获知。

在本文中，通过考虑用户移动性，我们在具有长期目标的动态系统中解决了一个计算卸载问题。具体而言，我们提出了高效的卸载策略以最小化系统的长期延迟。首先，我们假设可以获得系统的完整信息，并由此得到最优卸载策略。此外，当状态转移概率不可获得时，我们开发了两种学习算法，即Q学习和深度Q网络（DQN）。

本文其余部分组织如下。第二节介绍了网络模型和任务卸载问题。第三节讨论了在系统完全信息情况下的任务卸载算法。第四节提出了基于Q学习的任务卸载算法和基于DQN的算法。第五节给出了数值结果，第六节对全文进行了总结。

符号说明 ：符号 $|A|$ 表示集合 $A$ 的基数。指示函数 $1{\cdot}$ 在指定条件满足时取值为$1$，否则为$0$。符号 $[x]^+= \max{0, x}$。符号 $\emptyset$ 是空集。符号 $A\backslash{0}$ 表示集合$A$ 排除元素$0$后的集合。

二、系统模型

A. 网络模型

如图1所示，我们考虑一个物联网（IoT）网络，其中包含一个移动任务节点和一组固定辅助节点。我们假设任务节点在位置集合 $L:={1, 2, \cdots, L}$内移动。进一步地，我们将该集合中不同位置之间的转移 $L$ 建模为马尔可夫过程，这是现有研究（如[11]）中采用的一种通用方法。

所有位置均位于一个宏蜂窝基站的覆盖范围内，该宏蜂窝基站本身也是一个辅助节点。在每个位置 $l \in L$ 还有其他辅助节点，例如微微蜂窝/毫微微蜂窝。将所有辅助节点的集合记为$N={0, 1,…, N, N+ 1}$，其中节点0表示任务节点，节点 $N+ 1$表示宏基站，节点$i \in[1, N]$是一个本地辅助节点。需要注意的是，对于距离宏基站较远的位置，传输将需要较大的开销。

由于较大的传播路径损耗，可能会产生延迟。在这种情况下，任务节点更倾向于向附近的辅助节点寻求帮助。我们假设所有辅助节点都拥有充足的计算资源，并且愿意协助任务节点。

为简化问题，我们假设任务节点在同一时间只能与一个辅助节点关联。同时假设任务是周期性生成的，即每个时隙 $t \in T={1, 2,…, T}$ 开始时都会有一个任务到达任务节点。由于任务节点资源有限，其可将任务卸载至附近的辅助节点以实现更高的服务质量（QoS）。为了最小化处理任务的延迟，任务节点需要做出卸载决策，即决定是将任务在本地处理还是卸载到可访问的辅助节点。如果决定在本地处理该任务，则该任务将被缓存在任务节点中的先进先出（FIFO）缓冲区中，并且必须等待所有先前的任务处理完成后才开始处理。另一方面，如果任务被卸载，则会通过在任务节点与辅助节点之间建立通信链路将该任务传输至一个辅助节点。此外，我们假设卸载传输延迟不超过一个时隙，以便任务节点能够在移动到其他位置之前完成任务的卸载。

。任务在每个时隙的开始时刻到达。)

图2展示了一个示例时间线。任务‐t在本地处理，而任务‐(t+ 1)被卸载到一个辅助节点。由于任务节点的移动性，可访问的辅助节点及其相应的传输速率可能会发生显著变化。移动性带来的随机性使其成为一个难以处理的随机控制问题。MDP[12]是序列决策的经典框架，其中决策基于实时系统状态作出。在本文中，我们将在下一节将我们的计算卸载问题建模为一个MDP。

B. 问题建模

在时隙 t开始时，一个数据大小为 µ的任务到达任务节点。任务节点需要在 t做出卸载决策，决定是本地处理还是卸载到辅助节点。本文中，我们忽略任务节点做出卸载决策所花费的时间。为了考虑任务节点的移动性，该离散时间随机控制过程可以建模为一个MDP问题。我们的目标是找到一个最优决策策略，以最小化处理任务的总成本。该MDP问题包含四个要素，即状态空间 S、动作空间A、状态转移概率 P和成本函数 c。接下来，我们将对这些要素进行详细描述。

1) 系统状态

系统状态由 $s={l, q} \in S$ 描述，其中 $l \in L$ 是任务节点位置，$q \in Q$ 表示任务节点处已占用缓冲区长度。为了使缓冲区状态可数，需要对已占用缓冲区长度进行离散化。我们采用如下简单离散化方法：在时隙 t开始时，如果任务缓冲区为空，即 $q_t= 0$，且本时隙新生成的任务将被本地处理，则该任务会立即缓存在任务缓冲区中，此时缓冲区达到最大允许长度 µ。在下一个时隙（t+1），缓冲区长度将更新为 $q_{t+1}= \mu-f_0$，其中 $f_0$ 为任务节点的处理速率。在未来的时隙中，缓冲区长度将以 $f_0$ 的速度持续减少，直到缓冲区为空。因此，集合 Q 可以定义为
$$
Q={\mu - f_0, \mu - 2f_0,…, 0}.
$$
注意，我们使用 $s_t={l_t, q_t}$ 表示时隙$t$中的系统状态，该状态是在时隙$t$开始时观察到的。

2) 动作空间

每个动作 a是任务节点在每个时隙的特定卸载决策。所有可能的动作集合可以定义为
$$
A:={0, 1, 2,…, N, N+ 1}, \tag{1}
$$
其中 $a= 0$ 表示由任务节点自身处理任务，而$a= i$、$i \in[1, N+ 1]$表示将任务卸载至辅助节点‐i以寻求帮助。由于有限传输功率，任务节点只能发现附近的一些本地辅助节点。同时，任务节点始终可以访问宏基站。如果在时隙 t中任务节点的缓冲区非空，即 $q_t> 0$，则说明任务节点繁忙且无空闲计算资源。此时，任务节点必须将任务卸载到一个可接入的辅助节点。相反，当 $q_t = 0$时，任务节点可以由自身处理任务或将任务卸载到附近的辅助节点。因此，当 $q_t = 0$时，我们可以设置 $a_t = 0$。

3) 转移概率

状态转移概率$P(s_{t+1}|s_t , a_t)$表示在时隙 t 采取动作 $a_t$ 时，系统从状态 $s_t =(l_t , q_t)$ 转移到状态 $s_{t+1} =(l_{t+1} , q_{t+1})$ 的概率。由于任务节点按马尔可夫模型移动，位置 $l_{t+1}$ 仅依赖于 $l_t$，因此状态转移概率 $P(s_{t+1}|s_t , a_t)$ 可以分解为
$$
P(s_{t+1}|s_t, a_t)= P(l_{t+1}, q_{t+1}|l_t, q_t, a_t)
= P(l_{t+1}|l_t)P(q_{t+1}|l_t, q_t, a_t), \tag{2}
$$
其中缓冲区长度的演化如下所示
$$
P(q_{t+1}|l_t, q_t, a_t)
=\begin{cases}
1, & q_{t+1}=[q_t+ \mu \cdot1(a_t= 0)- f_0]^+, q_{t+1} \in Q \
0, & q_{t+1} \not=[q_t+ \mu \cdot1(a_t= 0)- f_0]^+, q_{t+1} \in Q
\end{cases}, \tag{3}
$$
并且 $P(l_{t+1}|l_t)$通过指定任务节点从位置 $l_t$移动到位置 $l_{t+1}$ 的概率来刻画任务节点的移动模式。可根据任务节点先前的移动模式进行估计，如[8]–[10]所示。

4) 即时成本

在本文中，我们关注系统的延迟最小化。系统 $c_t(s_t, a_t)$的即时成本定义为完成任务‐t的延迟，即
$$
c_t(s_t, a_t)= \frac{\mu}{f(l_t, a_t)} + \frac{\mu \cdot1{a_t \neq 0, a_t \in A}}{r(l_t, a_t)}. \tag{4}
$$
等式右侧的第一项是处理延迟，第二项是传输延迟。我们忽略任务处理完成后由于反馈传输带来的额外延迟，如[7]所示。处理任务‐t的节点的计算能力由$f(l_t, a_t)$表示。注意当 $a_t= 0$时，我们有 $f(l_t, a_t)= f_0$。向目标卸载辅助节点的传输速率由 $r(l_t, a_t)$表示。显然，只有当任务被卸载到一个辅助节点时，即 $a_t> 0$，才会发生传输延迟。

5) 策略

一个策略 $\pi(l_t, q_t)$是从 $L \times Q$到$A$的映射，用于指定任务节点在时隙 t、系统状态为 $s_t$时的卸载决策。目标是找到最优策略 $\pi^*$，以最小化从 $t= 1$到$t= T$的总成本，如下所示。
$$
\minimize_{\pi\in\Pi}
\sum_{t=1}^{T}
\gamma^{t-1}c_t(s_t, \pi(s_t)), \tag{5}
$$
其中， $\gamma$表示折扣因子， $\Pi$表示所有可行策略的集合。注意， $\gamma< 1$是确保在 $T\to \infty$时总成本收敛性所必需的。

III. 具有完整系统信息的最优任务卸载

在本节中，我们将为(5)中的问题寻找一个最优策略。设 $v^\pi(s)$为策略 $\pi$的状态值函数。特别地， $v^\pi(s)$表示当系统从状态 s开始时，在策略 $\pi$下的期望总成本，其定义为
$$
v^\pi(s):= \mathbb{E}^\pi\left[ \sum_{t=1}^{T}
\gamma^{t-1} c_t(s_t, a_t)\mid s_0 = s\right], \tag{6}
$$
其中 $s_0$是初始系统状态， $\mathbb{E}^\pi[\cdot]$表示在策略 $\pi$下关于任务节点移动模型的概率分布的期望。

为了找到最优策略，我们假设任务节点对系统具有完全知识。

该MDP问题可以通过满足贝尔曼最优条件[12],来获得，即
$$
v^{\pi^ }(s_t)= \min_{a\in A}
Q^{\pi^ }(s_t, a), \forall s_t \in S, \tag{7}
$$
其中 $Q^{\pi^ }(s_t, a)$定义为
$$
Q^{\pi^ }(s_t, a):= \mathbb{E}^\pi[c_t(s_t, a)+ \gamma v^{\pi^ }(s_{t+1})\mid s_t, a] \tag{8a}
$$
$$
= c_t(s_t, a)+ \gamma\sum_{s_{t+1}}
p(s_{t+1}|s_t, a)v^{\pi^ }(s_{t+1}) \tag{8b}
$$
$$
= \frac{\mu}{f(l_t, a)}
+
\frac{\mu \cdot1{a \neq 0, a \in A}}{r(l_t, a)}
+ \sum_{l_{t+1},q_{t+1}}
\gamma P(l_{t+1}|l_t)P(q_{t+1}|l_t, q_t, a)v^{\pi^ }(s_{t+1}), \tag{8c}
$$
以及 $s_{t+1}$是下一个可能的状态。(8b)中的两项分别是采取动作 a后在状态 $s_t$下的即时成本和未来时隙的预期未来成本。函数 $Q^\pi(s, a), \forall s \in S, a \in A$称为策略 $\pi$的动作价值函数。由(7)可知，给定最优动作价值$Q^{\pi^ }(s, a)$，我们需进行贪婪操作以实现最小期望总成本 $v^{\pi^ }(s)$。因此，最优动作 $\pi^ (s)$由下式给出
$$
\pi^ (s)= \argmin_{a \in A}
Q^{\pi^ }(s, a), \forall s \in S. \tag{9}
$$

根据之前的讨论，我们能够制定算法1以找到最优策略。需要注意的是，算法1需要系统的完整信息。此外，在算法1中，最优策略 $\pi^ $是通过离线方式迭代求解(7)和(8b)得出的。在时隙 t，一旦观测到系统状态 $s_t =(l_t , q_t)$，任务节点便根据已获得的策略 $\pi^ $直接做出最优卸载决策$\pi^*(s_t)$。

算法1 具有完整系统信息的最优任务卸载

1: 初始化: $\pi^ (s)= 0$, $v^{\pi^ }(s)= 0$, $\forall s \in S$;

2: repeat

3: for $l \in L$, $q \in Q$

4: if $q \neq 0$

5: 计算 $Q^{\pi^*}(l, q, a)$ as (8c), $\forall a \in A\backslash{0}$;

6: 设置 $\pi^ (l, q)= \argmin_{a\in A\backslash{0}} Q^{\pi^ }(l, q, a)$;

7: 设置 $v^{\pi^ }(s)= Q^{\pi^ }(l, q, \pi^*(l, q))$;

8: else

9: 计算 $Q^{\pi^*}(l, q, a)$, $\forall a \in A$;

10: 设置 $\pi^ (l, q)= \argmin_{a\in A} Q^{\pi^ }(l, q, a)$;

11: 设置 $v^{\pi^ }(s)= Q^{\pi^ }(l, q, \pi^*(l, q))$;

12: end if

13: end for

14: until $v^{\pi^*}(s)$, $\forall s \in S$, 收敛;

15: 输出最优策略 $\pi^*$。

IV. 基于有限系统信息的学习

用户移动性给网络带来了不确定性，并导致系统完全信息不可用。例如，通常很难获得关于用户移动模式的马尔可夫转移概率的先验知识。尽管有许多方法试图预测任务节点的移动模式，但不可避免地会带来额外的假设和开销[8]–[10]。接下来，我们将采用一种简单而有效的学习方法来解决这一问题。

A. 通过Q学习进行任务卸载

在本节中，我们考虑一种更为普遍的任务卸载场景，其中事先未知完全信息。具体而言，所有概率分布（例如 $P(l’|l), \forall l, l’ \in L$）均事先未知。因此，需要采用一种在线学习方法来应对系统动态。Q学习[13]是一种无需模型的方法，旨在通过试错来估计动作价值函数 $Q$。任务节点可以与动态环境进行交互，并从历史反馈中学习。同时，任务节点能够以在线方式智能地做出卸载决策。

在时隙 $t$，访问状态-动作对 $(s_t, a_t)$、获得成本 $c_t(s_t, a_t)$ 并观察到下一个状态$s_{t+1}$后，动作价值函数 $Q(s_t, a_t)$ 可按如下方式更新。
$$
Q_{t+1}(s_t, a_t)= (1 - \alpha_t)Q_t(s_t, a_t)+ \alpha_t(c_t(s_t, a_t)+ \min_{a\in A} Q_t(s_{t+1}, a)), \tag{10}
$$
其中， $\alpha_t \in(0, 1]$表示在时隙 t的学习率，用于权衡当前卸载经验的重要性， $Q_{t+1}$表示动作价值函数的第$(t+1)$次更新。基于Q学习的算法整体流程详见算法2。

当满足两个条件时，我们以概率 1[13]得到 $Q_{s,a}^{n}\to Q^* {s,a}, \forall s, a$。这两个条件是：1）成本 $c$有界， $|c| < C$；2）学习率$0 \leq \alpha_t < 1$，且 $\sum {t=1}^{\infty} \alpha_t = \infty$， $\sum_{t=1}^{\infty} \alpha_t^2 < \infty$。条件 1在我们的模型中已满足。通过选择合适的学习率，可以满足条件2。此外，已经证明，只要所有状态-动作对$(s, a), \forall s \in S, a \in A$被无限次访问[12]，Q-learning就会收敛到最优策略。利用 $\epsilon$-greedy方法可以满足该条件，这是平衡探索-利用权衡。任务节点在探索（以概率 $\epsilon$选择随机动作）和利用（选择具有最小成本的动作）之间采取动作。因此，即使在缺乏系统知识的情况下，基于Q学习的任务卸载算法也能够为我们的任务卸载问题找到最优策略。

Q学习是一种表格方法，意味着任务节点必须为所有可能的$(s, a)$对建立一个查找表。该表必须包含$(|S| \cdot |A|)$个值。如果状态空间和动作空间变得很大，Q学习在有限时隙内很难收敛。为了解决这一任务卸载问题，并采用更适用于实际应用的算法，我们将在下一节提出另一种低复杂度算法。

B. 基于深度Q网络的任务卸载

与Q学习方法中为所有$(s, a)$对构建最优动作值表不同，我们使用具有权重 $\theta$的深度神经网络函数来近似动作价值函数，如下所示。
$$
Q(s, a; \theta) \approx Q^ (s, a), \forall s \in S, a \in A, \tag{11}
$$
其中， $Q(s, a; \theta)$是如[14]中所述的深度Q网络（DQN），即第三节中定义的最优动作价值函数 $Q^{\pi^ }(s, a)$。该深度Q网络（DQN）将通过迭代调整权重$\theta$来训练，以减小近似器 $Q(s, a; \theta)$与最优动作价值 $Q^*(s, a)$之间的差异。

在深度Q网络（DQN）算法中，我们采用一种称为经验回放的技术，该技术能够加快学习过程的收敛速度[14]。对于每个时隙 $t$，我们将经验 $e_t:=(s_t, a_t, c_t(s_t, a_t), s_{t+1})$推入记忆池 $E_t$。记忆池仅保留最近的 $P$次经验，即 $E_t={e_{t-P+1},…, e_{t-1}, e_t}$。然后，我们从更新后的记忆池 $E_t$中均匀地选择一个固定大小为 $B$的小批量$\tilde{E} t$，以沿损失函数 $L_t(\theta_t)$的下降方向训练DQN。损失函数定义为近似器 $Q(s_t, a_t; \theta_t)$与最优动作价值 $Q^ (s_t, a_t)$之间的均方误差（MSE），如(12a)所示。同时，由于 $Q^ (s_t, a_t)$先验未知，根据(8b)中给出的贝尔曼最优方程，它可以用(12b)中的 $y_t$代替。
$$
L_t(\theta_t)= \mathbb{E} {\tilde{E} t \sim U(E_t)}\left[ ( y_t - Q(s_t, a_t; \theta_t))^2 \right], \tag{12a}
$$
$$
y_t= c_t(s_t, a_t)+ \gamma \min {a’} Q(s_{t+1}, a’; \theta_t), \tag{12b}
$$
其中符号 $\tilde{E} t \sim U(E_t)$表示 $\tilde{E}_t$从 $E_t$中均匀采样。$\mathbb{E} {\tilde{E}_t \sim U(E_t)}[\cdot]$表示关于采样概率的期望。在深度Q网络算法中，在时隙 $t$，神经网络输入是系统状态$s_t$，输出是 $Q(s_t, a; \theta_t), \forall a \in A$。与Q学习中只有当特定的$(s, a)$对被访问时才能更新 $Q(s, a)$不同，深度Q网络能够在每次 $\theta$更新时改进所有$(s, a)$对的$Q(s, a)$。

给定 $Q(s, a; \theta)$，我们可以选择一个贪婪动作为 $\pi(s)= \min_a Q(s, a; \theta), \forall s, a$。该算法在算法3中给出。

算法3 用于任务卸载的深度Q网络

1: 初始化： $t= 1$, $E_1= \emptyset$, $\tilde{E}_1= \emptyset$, $\theta_1= 0$

2: while $t \leq T$

3: 观察系统状态$s_t$；

4: 以概率 $\epsilon$，从$A$中随机选择一个动作$a_t$；否则，根据$a_t$选择 $a_t = \argmin_{a\in A} Q(s_t, a; \theta_t)$;

5: 观察成本$c_t(s_t, a_t)$和下一个状态$s_{t+1}$；

6: 将 $e_t=(s_t, a_t, c(s_t, a_t), s_{t+1})$存储到 $E_t$中，更新 $E_t$；

7: 采样一个小批量 $\tilde{E}_t \subseteq E_t$

8: 对于$e_j=(s_j, a_j, c_j, s_{j+1}) \in \tilde{E}_t$

9: 根据(12b)更新 $y_j$；

10: 执行梯度下降 step on $(y_j - Q(s_j, a_j; \theta_t))^2$关于 $\theta_t$；

11: end for

12: 更新 $\theta_{t+1}$为$\theta_t$；

13: 更新$t$为$t+ 1$。

14: end while

注意，在步骤3中引入了一种 $\epsilon$-贪婪策略，以平衡探索与利用的困境。通过这种方式，当$T\to \infty$时，每个状态-动作对都将被无限次访问。

五、数值结果

在本节中，使用第三节和第四节提出的算法提供数值结果。在整个本节中，最优卸载算法标记为Optimal。DQN表示基于深度Q网络的学习算法。Q-learning表示基于Q学习的卸载算法。

A. 参数设置

我们假设任务节点在如图1所示的 $4 \times 4$网格内移动，其中 $L= 16$。包含所有网格的整个区域大小为2公里 $\times$2公里。一个宏基站在中心部署。 $N= 20$中的本地辅助节点数量。辅助节点在该区域内随机分布。移动模式 $P(l’|l)$与[11]中的类似。当新的时隙到来时，任务节点以概率 $P(l|l)= 0.4$停留在当前位置，并以相等的概率移动到相邻位置（网格）。例如，在图1中，在时隙 $t$，如果任务节点位于左上角的网格，则其有三种可能：1）以概率 $P(l|l)= 0.4$停留在同一网格；2）以概率 $P(l’|l)= 0.3$向下移动；3）以概率 0.3向右移动。每个时隙为10秒。

在仿真中，考虑到宏基站与本地辅助节点之间的差异（例如高度和工作频段），我们对路径损耗进行了不同的建模。具体而言，任务节点到本地辅助节点的距离相关路径损耗建模为$(35.7\log_{10} d+ 33.4)$ dB，其中 $d$为以米为单位的距离。同时，到宏基站的路径损耗建模为$(35.7\log_{10} d+ 18.4)$ dB。

表I 深度Q网络的部分参数设置

参数	值
内存池大小 $P$	500
小批量大小 $B$	32
折扣因子 $\gamma$	0.9
探索概率$\epsilon$	0.1
学习率	0.001

其他网络参数设置如下，如[15]中所述。

• 任务节点的发射功率为20 dBm；
• 系统带宽为20 MHz，噪声功率谱密度（PSD）为 −174 dBm/Hz；
• 任务节点的处理速率为10 Mbps，宏基站的处理速率为 35 Mbps。本地辅助节点的处理速率在(10, 40) Mbps范围内均匀生成。

对于基于DQN的算法，我们在[16]中利用 TensorFlow框架。神经网络设计中使用了两个隐藏层，分别包含128和64个神经元。选择ReLU激活函数和 Adam优化器。其他DQN相关参数总结于表I。

B. 性能评估

我们在此部分研究了Q学习和深度Q网络的收敛性和最优性特性，并将其与最优策略进行比较。需要注意的是，最优策略被视为具有系统完整信息的基准。

1) 收敛性

基于学习的算法Q学习和DQN的收敛性通过动作值 $Q(s, a), \forall s \in S, a \in A$的累积平均值来展示。在不失一般性的前提下，我们绘制了状态 $s=(l, q)=(7, 30)$在执行卸载动作$a= 1$时的动作值累积平均值，即 $Q(7, 30, 1)$。结果如图3所示。

如图3所示，基于DQN的算法确实比Q学习快得多地收敛到最优策略。正如我们在第四节-B中提到的，Q学习仅在状态(7, 30)被访问且采取动作1时才更新 $Q(7, 30, 1)$，而DQN由于其带有权重 $\theta$的近似器在每个时隙都在更新，因此在每个时隙都更新 $Q(7, 30, 1)$。

2) 最优性

请回顾第四节-A，我们已经证明，在我们的模型中，由于成本是有界的，Q学习保证收敛到最优策略$|c_t| < C, \forall t \in T$。 $C= 18$是我们模型的一个可行设置。特别是，我们的学习算法的最优性体现在任务卸载的奖励上，该奖励定义为 $r_t = C−c_t(s_t, a_t)$。请注意，最优策略是在网络信息完全已知的情况下计算得出的，并且需要在仿真之前完成计算，而我们的算法仅从历史反馈中学习信息。

在图4中，带括号的DQN和Q学习表示在应用于模拟 5,000运行之前，先对模型进行预训练直至收敛。具体而言，Q-learning （预训练2e5）和DQN（预训练2e3）是通过预训练完成的Q学习和深度Q网络算法分别用于 200,000和 2,000个时隙。然后在模拟的 5,000次运行中，不进行训练（即不更新动作值），任务节点基于预训练模型做出卸载决策。

Q-learning和DQN未加括号的版本在之前未进行预训练，但在所有 5,000次运行中持续学习（更新动作值）。另一个基准策略Local是指任务节点始终优先选择本地处理任务。

从图4可以看出，当Q学习未经过预训练时，它需要从仿真的初始阶段开始学习系统信息，因此由于收敛速度较慢，其性能表现较差，与本地方法相当。而DQN相比 Q学习获得了更高的奖励，并且在初期波动后仍保持上升趋势，逐渐接近最优性能，这表明基于DQN的任务卸载能够以非常快的收敛速度学习系统特性，同时也印证了我们在图3中的仿真结果。另一方面，当应用Q学习（预训练2e5）时，其性能接近最优策略，验证了Q学习在本模型中的最优性。DQN（预训练2e3）的表现略逊于Q学习（预训练2e5），但其预训练步数仅为其1%，这进一步证实了DQN具有快速收敛的特性。

VI. 结论

本文研究了移动边缘计算中的任务卸载问题。为了最小化系统的期望长期延迟，我们提出了不同的学习算法，以针对不同系统设置找到最优的任务卸载策略。在具有完整系统信息的情况下，我们基于贝尔曼方程获得全局最优策略。在有限系统信息条件下，我们提出了两种基于学习的算法，包括Q学习和深度Q网络（DQN）。数值实验表明，Q学习能够实现最优性能，而DQN能够处理具有高维状态空间的系统，并且快速收敛。