移动边缘计算中的能量高效计算卸载与发射功率分配方案

引言

在过去几年中，随着智能手机、手持游戏机和车载多媒体计算机等移动设备（MD）几乎无处不在，增强现实、图像处理、自然语言处理、人脸识别和交互式游戏等越来越多的新移动应用不断涌现，并受到广泛关注[1, 2]。这类移动应用通常对延迟敏感，需要密集的计算资源，并具有高能耗特性。由于物理尺寸的限制，移动设备（MD）通常资源有限，这限制了其电池寿命和计算能力[3, 4]。

最近的研究表明，移动边缘计算卸载（MECO）技术通过有效克服与移动设备的硬件和能耗问题相关的限制，提供了极具前景的解决方案。将计算密集型任务卸载到移动网络边缘的邻近云进行执行[5–7]。特别是，移动边缘计算（MEC）通过在基站（BS）部署MEC服务器，能够在移动网络边缘提供云计算能力，实现低延迟和优异的用户体验质量，已引起学术界和工业界的广泛关注[8]。

鉴于计算性能和能量消耗对移动用户[9]至关重要，因此有必要为移动边缘计算系统设计高效的计算卸载方案。为了最小化移动设备上计算任务的完成时间，洪等人[10]在多用户移动边缘计算系统中针对时分多址（TDMA）和频分多址（FDMA）方案建立了一个联合优化问题。刘等人[11]在考虑计算任务调度的情况下，推导出移动边缘计算系统中一种受功率约束的延迟最小化卸载策略，并采用了马尔可夫决策过程方法。毛等人[12]还提出了一种有效的计算卸载方案，旨在降低配备能量收集设备的绿色移动边缘计算系统中的执行时间。在多用户时分多址（MU-TDMA）移动边缘计算卸载系统中，任等人[6]研究了通过联合分配通信与计算资源来实现延迟最小化的问题，并推导出了本地与边缘计算模型下的最小系统延迟。然而，上述工作的不足之处在于卸载决策未考虑移动设备端的能量消耗。

快速电池耗尽也已成为现代网络中的一个重大障碍。为此，萨德尔蒂等人[13]设计了一个能量最小化卸载问题，通过优化MIMO多小区系统中的无线资源来降低能耗。张等人[14]提出了一种高效的计算卸载方案，在延迟约束下通过优化5G异构网络中具有多接入特性的移动边缘计算的卸载策略和无线资源分配，实现最小能耗。尤等人[15]基于对输入数据到达时间点和计算截止时间的理解，研究了移动边缘计算系统的高效能资源管理策略，并制定了一种优化策略以最小化总移动能量消耗。然而，这些工作主要关注降低能耗，而未尝试减少计算任务的完成时间。

此外，移动设备被不同个体所使用，他们可能追求多样化兴趣。因此，在设计卸载策略时，有必要同时关注能量和时间消耗。近年来，一些研究考虑了移动设备的能量消耗与移动边缘计算系统执行延迟之间的权衡[16, 17]。然而，在这些优化模型中，仅考虑了传输延迟，而忽略了服务器计算延迟；因此，它们无法应用于计算能力受限的移动边缘计算服务器。

上述大多数针对多用户MECO系统的研究仅集中于二进制计算卸载策略，这意味着计算任务只能通过本地计算或边缘计算之一执行。然而，根据其通信能力，一些移动设备可能更倾向于部分卸载。通过将耗时和/或耗能的子任务卸载到MEC服务器，这种部分卸载相比二进制卸载可实现更高的节能效果和更低的计算延迟[18]。尽管[19]中的开创性工作研究了节能型部分计算卸载问题，但对于某些高延迟敏感型应用而言，一个更为紧迫的设计目标尚未讨论，即延迟最小化问题。此外，郭等人[20]提出了一种高效能动态二进制卸载与资源调度（eDors）策略，并设计了分布式eDors算法以最小化能效成本（EEC），该成本定义为任务的能耗与计算完成时间的加权和。基于上述观察，本研究中提出了EEC最小化问题。

针对具有部分计算卸载的多用户MEC系统进行了研究。此外，本文还讨论了二进制卸载的一个特例，即完全卸载或完全本地计算。本研究旨在最小化移动设备在完成时间截止期限约束下完成任务所支付的EEC。具体而言，本文还证明了EEC最小化问题是一个凸优化问题，我们能够通过采用Karush–Kuhn–Tucker（KKT）条件来求解该凸优化问题。此外，根据MEC服务器和本地设备上的EEC，提出了一种最优的计算卸载和发射功率分配方案。本文的主要贡献总结如下：

(i) 我们提出了一种用于移动边缘计算的多用户计算卸载框架，并解决了性能有保障的计算卸载问题。
(ii) 建立了一个EEC优化问题，旨在在满足延迟约束的同时最小化能耗与计算完成时间的加权和。
(iii) 利用拉格朗日乘子法和KKT条件求解该凸优化问题，并提出了一种高效的算法，该算法包含针对移动设备的计算卸载策略和传输功率分配。

本文的其余部分组织如下。接下来的部分介绍了系统模型。然后，对优化问题进行了建模。随后，描述了提出的有效任务卸载算法。接着，给出了数值结果，以证明我们提出的方法相较于现有方法具有出色的性能。最后，给出了结论性评述。

2. 系统模型

所考虑的MEC系统由N个移动设备（MDs）组成，如图1所示。MEC服务器是安装在无线接入站上的计算设备。移动设备可以连接到位于移动用户附近的站点资源。将计算任务分配给基站（BS）有助于移动用户提升计算性能。由于已有先驱性文献研究了移动云计算（例如 [10, 15, 21]）和移动网络（例如[22, 23]），为了便于进行可处理的性能分析并获得有价值的见解，我们将应用场景视为准静态，即在一次计算卸载周期内移动设备集合保持不变。本研究考虑一组N = {1, 2, …, N}共址的移动设备，并为每个移动设备设定一个需要完成的计算密集型任务。用元组{cn, dn}表示移动设备n的任务需求，其中cn描述完成该任务所需的CPU周期数，dn表示任务数据大小。移动设备n的卸载数据量记为ln。令αn表示移动设备n的卸载任务比例。所有移动设备的卸载策略配置文件表示为A = {αn | n ∈ N}。

2.1 通信模型

我们首先介绍MEC系统的通信模型。移动设备根据其能量消耗和完成时间性能来制定计算卸载策略。移动设备n的传输功率表示为pn，gn表示基站的信道增益。此外，本文考虑一个多用户计算卸载系统，它们在上行链路中会相互干扰。因此，移动设备n进行计算卸载的上行链路数据速率为

$$
r_n = B \log_2 \left(1 + \frac{p_n g_n^2}{N_0 + I}\right),
$$

其中N₀和I分别表示加性白高斯噪声和干扰的功率谱密度。设B为信道带宽，在移动边缘计算（MEC）端，接收信号功率可表示为数据速率r的函数：

$$
h(r) = (N_0 + I)B \left(2^{(r/B)} - 1\right),
$$

在r > 0范围内单调递增且凸。卸载传输速率可以表示为

$$
r_n = \frac{d_n}{t_n},
$$

其中tn是移动设备n卸载大小为dn的输入数据的传输时间。然后，通过结合(2)和(3)可计算传输功率pn：

$$
p_n = \frac{1}{g_n^2} h\left(\frac{d_n}{t_n}\right).
$$

2.2 计算模型

假设移动设备n有一个计算任务Tn = {cn, dn}，其中cn表示完成计算任务Tn所需的总CPU周期数，dn描述计算任务Tn的输入数据大小。接下来，我们将讨论EEC在移动设备在本地计算和边缘计算方法下的能耗和完成时间。

2.2.1 本地计算

在本地计算方法中，移动设备n在其自身设备上本地执行其计算任务Tn。设hn表示移动设备n的计算能力（即每秒CPU周期）；不同的移动设备可能具有不同的计算能力。因此，本地计算的完成时间定义为

$$
t_{n,\text{loc}} = \frac{c_n}{h_n}.
$$

对于计算能耗，我们有

$$
e_{n,\text{loc}} = f_n c_n,
$$

其中fn是移动设备n每个CPU周期消耗的能量。根据公式(5)和(6)，本地计算方法的EEC在计算时间和能量方面的计算方式为

$$
Z_{n,\text{loc}} = c_e^n e_{n,\text{loc}} + c_t^n t_{n,\text{loc}},
$$

其中$ c_e^n, c_t^n \in [0, 1] $分别表示移动设备n在制定任务Tn卸载策略时对能耗和计算完成时间的权重。我们允许移动设备在制定策略时设置不同的权重值以满足其特定需求。例如，电池电量较低的设备在制定卸载策略时更有可能选择较大的$ c_e^n $以节省更多能量。当移动设备运行延迟敏感型应用（如在线游戏）时，其目标是设置较大的$ c_t^n $以减少延迟。

2.2.2 边缘计算

采用边缘计算方法时，移动设备n将其计算任务Tn卸载到MEC服务器。随后，该服务器执行计算任务并将结果反馈给移动设备。显然，移动设备n将其计算任务Tn卸载至MEC服务器执行，整个过程包括三个连续阶段：(i) 传输阶段，(ii) 计算阶段，和 (iii) 接收阶段。

根据通信模型，移动设备n将其计算任务Tn传输至MEC服务器的传输时间和能耗分别计算如下

$$
t_{n,\text{trs}} = \frac{d_n}{r_n} = t_n,
$$

$$
e_{n,\text{trs}} = p_n t_n.
$$

此外，任务Tn在MEC服务器上的执行时间通过以下方式计算

$$
t_{n,\text{exe}} = \frac{c_n}{h_c^n},
$$

其中$ h_c^n $表示MEC服务器的计算能力。在本研究中，我们考虑了移动设备侧的能耗，而未来工作将考虑MEC服务器的执行能耗。因此，对于边缘计算方法，任务Tn的完成时间和能耗分别表示为

$$
t_{n,\text{off}} = t_{n,\text{trs}} + t_{n,\text{exe}} + t_{n,\text{rece}},
$$

$$
e_{n,\text{off}} = e_{n,\text{trs}} + e_{n,\text{rece}},
$$

其中，$ t_{n,\text{rece}} $和$ e_{n,\text{rece}} $分别表示移动设备n从MEC服务器接收计算结果所需的时间和能量。根据公式(9)和(11)，可通过公式(13)基于完成时间和能耗计算边缘计算方法的EEC。

$$
Z_{n,\off} = c_e^n e_{n,\off} + c_t^n t_{n,\off}.
$$

从公式(8)和(9)可以看出，当移动设备n的无线接入数据传输速率rn较低时，在将输入数据卸载到MEC服务器的过程中会导致较长的传输时间以及较高的能耗。与现有研究[17, 24]类似，接收时间$ t_{n,\text{rece}} $和接收能量$ e_{n,\text{rece}} $可以忽略不计，因为对于许多人脸识别等应用而言，结果数据的大小通常远小于输入数据的大小。

3. 问题建模

在本节中，通过综合考虑每个移动设备的能量消耗和任务完成时间，建立了移动边缘计算系统的EEC优化问题。其中，αn被定义为任务Tn中卸载到MEC服务器的部分。因此，移动设备n的EEC包括本地计算消耗和卸载消耗：

$$
Z_n = Z_{n,\off} \alpha_n + Z_{n,\loc} (1 - \alpha_n).
$$

移动设备n的任务Tn的完成时间可以表示为

$$
t_{n,\all} = t_{n,\off} \alpha_n + t_{n,\loc} (1 - \alpha_n).
$$

目标是提供最优计算卸载策略A∗和传输功率分配P∗以最小化EEC。因此，所有移动设备的EEC可表述为一个约束最小化问题：

$$
\min_{A,P} \sum_{n=1}^{N} Z_n,
$$
$$
\text{s.t. } \left(t_n + \frac{c_n}{h_c^n}\right)\alpha_n + \frac{c_n}{h_n}(1 - \alpha_n) \leq T_{n,\max}, \quad \forall n,
$$

其中，A = {αn | n ∈ N}，P = {pn | n ∈ N}。如方程（16）所示，p∗n可由 tn∗得出。因此，优化问题（16）的变量为 αn和tn。该约束条件规定移动设备n的任务总完成时间受限于要求的最大完成时间Tn,max。下面探讨方程（16）中优化问题的凸性。

证明。 首先，应证明方程（16）中的目标函数Zn关于优化变量αn和tn是联合凸的。然后，我们证明该约束的凸性。

$$
Z_n = \left(c_e^n t_n \frac{1}{g_n^2} h\left(\frac{d_n}{t_n}\right) + c_t^n \left(t_n + \frac{c_n}{h_c^n}\right)\right)\alpha_n + \left(c_e^n f_n c_n + c_t^n \frac{c_n}{h_n}\right)(1 - \alpha_n),
$$

$$
\frac{\partial^2 Z_n}{\partial t_n^2} = \frac{2 d_n / B t_n ( ) d^2_n \alpha_n r e_n (\ln 2)^2 N_0}{B g_n^2 t_n^3} \geq 0.
$$

由于Zn是 αn的仿射函数，因此它关于优化变量αn是凸的。类似地，该约束条件关于优化变量 αn和tn是联合凸的。可以看出，方程（16）中的优化问题具有零对偶间隙，并满足Slater约束条件。零对偶间隙的结果提供了一种方法，可通过其对应的对偶问题来获得方程（16）中原始问题的最优解。

4. 最小能量效率成本（EEC）问题算法

通过求解方程（16）的对偶问题，得出计算卸载和资源分配方案。因此，方程（16）中原始问题的拉格朗日函数定义为 $ L(\alpha_n, t_n, \lambda) $。拉格朗日乘子 $ \lambda $ 表示移动设备 $ n $ 的任务总完成时间不超过要求的最大完成时间的价格。方程（16）中原始问题的对偶问题由以下给出

$$
\max_\lambda \min_{\alpha_n,t_n} L(\alpha_n, t_n, \lambda),
$$

其中 $ \lambda \geq 0 $ 是与完成时间约束相关的拉格朗日乘子。然后，应用相应的KKT条件将其转换为以下方程：

$$
L(\alpha_n, t_n, \lambda) = \left(c_e^n t_n \frac{1}{g_n^2} h\left(\frac{d_n}{t_n}\right) + c_t^n \left(t_n + \frac{c_n}{h_c^n}\right)\right)\alpha_n + \left(c_e^n f_n c_n + c_t^n \frac{c_n}{h_n}\right)(1 - \alpha_n)
+ \lambda \left[\left(t_n + \frac{c_n}{h_c^n}\right)\alpha_n + \frac{c_n}{h_n}(1 - \alpha_n) - T_{n,\max}\right],
$$

$$
\frac{\partial L}{\partial \alpha_n^ } = \left(c_e^n t_n^ \frac{1}{g_n^2} h\left(\frac{d_n}{t_n^ }\right) + c_t^n \frac{c_n}{h_c^n}\right) - \left(c_e^n f_n c_n + c_t^n \frac{c_n}{h_n}\right)
+ \lambda^ \left(t_n^* + \frac{c_n}{h_c^n} - \frac{c_n}{h_n}\right) = 0,
$$

$$
\frac{\partial L}{\partial t_n^ } = \alpha_n^ \frac{c_e^n}{g_n^2} h\left(\frac{d_n}{t_n^ }\right) + \alpha_n^ \frac{c_e^n t_n^ }{g_n^2} h’\left(\frac{d_n}{t_n^ }\right) + c_t^n \alpha_n^* = 0,
$$

$$
\lambda^ \left[\left(t_n^ + \frac{c_n}{h_c^n}\right)\alpha_n^ + \frac{c_n}{h_n}(1 - \alpha_n^ ) - T_{n,\max}\right] = 0, \quad \lambda > 0.
$$

通过表示 $ X = (d_n / B t_n^*) $，并根据方程(21)，X 满足以下条件：

$$
(1 - X \ln 2)2^X = -\frac{g_n^2 (c_t^n + \lambda)(N_0 + I)B}{c_e^n} + 1.
$$

由方程(23)可进一步推导出

$$
2^{(1/\ln 2)} \ln 2 \left(X - \frac{1}{\ln 2}\right) \ln 2 X - \frac{1}{\ln 2} = \frac{g_n^2 (c_t^n + \lambda)(N_0 + I)B}{c_e^n} - \frac{1}{e}.
$$

根据Lambert W函数

$$
Q = z e^z \longrightarrow z = W_0(Q), \quad Q \geq -\frac{1}{e}.
$$

方程(24)的反函数表示为

$$
X = \frac{1}{\ln 2} W_0\left(\frac{g_n^2 (c_t^n + \lambda)(N_0 + I)B}{c_e^n} - \frac{1}{e}\right) + 1.
$$

因此，最优传输速率表示为

$$
r_n^* = \frac{B}{\ln 2} \left[W_0\left(\frac{g_n^2 (c_t^n + \lambda)(N_0 + I)B}{c_e^n} - \frac{1}{e}\right) + 1\right].
$$

对于给定的 $ \lambda > 0 $，该EEC最小化问题的最优解 $ t_n^ $ 和 $ p_n^ $ 可按如下方式计算：

$$
t_n^* = \frac{d_n \ln 2}{B \left[W_0\left(\frac{g_n^2 (c_t^n + \lambda)}{(N_0 + I)B c_e^n}\right) - \frac{1}{e}\right] + 1}.
$$

同时，根据方程(3)和(4)，$ p_n^* $ 由以下给出

$$
p_n^ = \frac{(N_0 + I)B}{g_n^2} \left(2^{d_n/(B t_n^ )} - 1\right).
$$

通过求解方程(22)可以获得卸载策略：

$$
\alpha_n^ = \frac{(T_{n,\max} h_n - c_n) h_c^n}{t_n^ h_n h_c^n + c_n h_n - c_n h_c^n}.
$$

对于给定的 A 和 P，拉格朗日乘子通过以下方式更新

$$
\lambda(k+1) = \left[\lambda(k) + \theta(k) \left(T_{n,\max} - \frac{c_n}{h_n}(1 - \alpha_n) - \left(t_n + \frac{c_n}{h_c^n}\right)\alpha_n\right)\right]^+,
$$

其中 $ k > 0 $ 为迭代索引，$ \theta(k) $ 为正迭代步长。然后，方程(31)中更新的拉格朗日乘子可用于更新方程(28)和(29)中的传输功率分配以及方程(30)中的卸载策略。

5. 性能评估

在本节中，我们对所提算法的性能进行评估。仿真设置如下：首先考虑移动边缘计算场景的覆盖范围为50米，其中有30台智能手机随机分布在该覆盖区域内[25]。MEC服务器上为移动设备n分配的计算能力设为 $ h_c^n = 10 $ GHz，移动设备的CPU能力 $ h_n $ 随机设为{0.5, 0.6, …, 1.0} GHz，以体现移动设备之间异构的计算能力。我们将初始策略权重 $ c_e^n = c_t^n = 0.5 $，这意味着移动设备n同时考虑计算时间和能耗。任务大小均匀分布在(0, 20) MB之间。不失一般性，设 $ c_n $ 为737.5 周期/比特[26]。对于无线接入，设置信道带宽B = 5 MHz，以及 $ N_0 + I = -100 $ dBm[27]。通过与本地计算和完全卸载方法进行比较，我们评估提出的部分卸载方案。

5.1 能耗与完成延迟的比较

在本小节中，针对任务大小的变化，将提出的方案的能耗和完成时间与本地计算方法、完全卸载方法以及Li等人提出的二进制卸载方法在[28]中的表现进行了比较。

图2展示了四种方案的能量消耗和完成时间。从图2可以看出，提出的部分卸载和李的二进制卸载方案优于本地计算和完全卸载方案。此外，与本地计算相比，完全卸载方法在任务大小较大时表现更优。因此，对于输入数据较大的计算任务，所提出的方案和Li的方案倾向于将大部分计算任务卸载到MEC服务器，以最小化移动设备的EEC支出。此外，当输入数据较小时，Li的二进制卸载方法能耗最低。然而，这种能耗随着任务大小的增加而增加，最终大于所提出的部分卸载方案。这是因为所提出的部分卸载方案不仅根据本地计算和完全卸载之间的权衡，将计算密集型子任务卸载到MEC服务器，而且还利用传输功率来减少移动边缘计算中的能量和时间消耗。此外，将任务卸载到MEC服务器所需的完成时间包括无线通信时间。

从图2(b)可以看出，我们提出的部分卸载方案的任务完成时间随任务大小的增加而相对缓慢地增长。

5.2 权重的影响 $ c_e^n $ 和 $ c_t^n $

在本小节中，研究了权重 $ c_e^n $ 和 $ c_t^n $ 对具有不同输入数据大小的任务的能耗和计算时间的影响。

图3展示了在不同 $ c_e^n $ 和 $ c_t^n $ 设置下能耗和计算延迟的差异。能量消耗随着 $ c_e^n $ 的减小而增加，且与任务大小无关；然而，计算延迟的变化则相反。这是预料之中的，因为较大的 $ c_e^n $ 将导致传输速率下降，如公式(26)所示，从而在边缘计算执行期间引起传输功率的降低。

5.3 执行策略上EEC的比较

在本小节中，在严格的完成时间截止约束下，将提出的任务执行算法与另外两种执行方法（即本地计算和完全卸载）进行了比较。

如图4所示，延迟要求的差异会影响相同任务配置文件下的EEC。从图4中可以得出以下观察结果。首先，只有任务数据大小和CPU计算能力会影响本地计算方法的EEC，因此延迟要求的变化不会影响其EEC。其次，与本地计算相比，部分卸载方案可以显著降低EEC。这是因为所提算法能够根据边缘端和本地设备上的EEC，将部分计算任务最优地卸载到MEC服务器上执行。第三，与完全卸载方法相比，所提算法在较长的完成时间截止期限下具有更低的EEC。这是合理的，因为所提算法采用了最优卸载策略和传输功率分配。

6. 结论

在本研究中，探讨了移动边缘计算中的能量高效计算卸载问题。我们将计算卸载与发射功率分配相结合，以在完成时间截止约束下最小化能耗和时间消耗。我们设计了一种新颖的算法，该算法包含计算卸载策略和传输功率分配子算法。实验结果表明，我们提出的方案通过利用移动边缘计算中的动态计算卸载策略和传输功率分配，能够有效降低能耗和完成时间。

未来工作将考虑一种更普遍的情况，即移动用户可能在计算卸载周期内动态离开和到达。在这种情况下，用户的迁移模式将极大地影响问题建模。