2016.12 IEEE JSAC “Dynamic Computation Offloading for Mobile-Edge Computing With Energy Harvesting Devices”

1. 动机

MEC 提供边缘云计算能力，移动设备通过负载卸载为计算密集型任务创造了条件，而且从云到网络边缘的转移可以减少传播延迟，因此 MEC 为延迟关键型应用也开辟了道路。最重要的是，计算任务卸载到边缘执行，可以为移动设备节省更多的能量。
MEC 固然能节省能量，但是电池能量不足时，设备上的移动执行和云端的云执行都将被终止。增大电池容量或者定期充电都将造成巨大的硬件开销或者维护开销。能量收集技术（Energy harvest，EH）通过收集环境中的能量，例如太阳能，风能，热能，动能，电磁能，来为设备充电，从而达到可持续利用的目的，这一技术非常有前景。
通过将 EH 技术集成到 MEC 中，可以获得令人满意和持续的计算性能。
当前的 MEC 系统研究只适用于带电池的设备，因此作者为具有 EH 设备的 MEC 系统开发新的卸载策略。

2. 相关工作

关于 MEC 的研究，包括基于无线信道条件的负载卸载策略，以及移动设备上基于DVFS技术的计算策略。从单用户到多用户，从单一的能耗最低的目标到能耗和时延的权衡，许多学者基于不同的条件，提出了各种调度算法。
具有EH技术的通信技术被广泛研究，例如用包括信道边信息(CSI)和能量边信息(ESI)的非因果边信息(SI)，可以通过定向注水(DWF)算法实现点对点 EH 衰落信道的最大吞吐量。还有更多关于各种通信场景的资源分配算法也被提出。
具有 EH 装置的 MEC 系统的设计原则不同于 EH 通信系统或具有电池供电装置的 MEC 系统。一方面，与 EH 通信系统相比，计算卸载策略需要综合考虑三个方面，即卸载决策（即是否卸载任务）、移动执行的CPU周期频率以及任务卸载的传输策略进行综合决策，这使得它更具挑战性。另一方面，与采用电池供电设备的 MEC 系统相比，设计目标从最小化电池能耗转向优化计算性能，因为收集的能量是免费的。此外，ESI 是一个新的设计考虑因素，与时间相关的电池能量动态构成另一个挑战。

3. 系统模型

3.1 采用 EH 设备的移动边缘计算系统

移动设备和MEC服务器组成一个MEC系统，移动设备配备了EH组件，完全由收集的能源供电，MEC服务器与移动设备相聚 $d$，且可以通过无线信道访问。MEC服务器上有移动设备的云克隆，上面部署的虚拟机可以运行移动设备的应用程序。移动设备的计算任务可以被卸载到边缘端。

假设：

时间是由一个个时隙组成的，时隙 $\tau \in \mathcal{T} \triangleq {0,1, \cdots}$。
无线信道是独立同分布的块衰落，即信道在每个时隙内是相同的，但是不同时隙是不同的。记 $t$ 时隙的信道增益为 $h ^ {t}$，且 $h^{t} \sim F_{H}(x), t \in \mathcal{T}$，其中$F _ {H}(x)$ 是 $h ^ {t}$ 的分布函数。

3.2 计算模型

假设 $A(L,\tau _d)$ 表示一个计算任务，$L$ 表示输入bits，$\tau _d$ 表示截止时间。在移动设备上运行的应用程序所请求的计算任务服从独立同分布的伯努利过程。即有 $\rho$ 的概率请求计算 $A(T,\tau _d)$，也有 $1-\rho$ 的概率不请求。如果 $t$ 时隙，一个计算任务被请求，记为 $\zeta ^ {t}=1$，反之记为 $\zeta ^ {t}=0$。即，$\mathbb{P}\left(\zeta ^ {t}=1\right)=1-\mathbb{P}\left(\zeta ^ {t}=0\right)=\rho, t \in \mathcal{T}$。主要关注延迟敏感性任务，即 $\tau _ {d} \leq \tau$，并假设没有缓冲区可以对计算请求进行排队。

与传统的MEC不同的是，任务除了移动执行，边缘执行外，还有第三种可能，两种执行方式都不可行时，例如移动设备的能量不足时，计算任务将被丢弃。$I _ {j} ^ {t} \in{0,1}$。

\[I_{\mathrm{m}}^{t}+I_{\mathrm{s}}^{t}+I_{\mathrm{d}}^{t}=1, \quad t \in \mathcal{T} \tag{1}\]

上式中，对于 $j={\mathrm{m}, \mathrm{s}, \mathrm{d}}$，$I _ {j} ^ {t} \in{0,1}$，当任务移动执行的时候，$I _ {m}^{t}=1$，当MEC服务器执行的时候，$I _ {s} ^ {t}=1$，当被丢弃的时候，$I _ {d} ^ {t}=1$。

3.2.1 本地执行模型：

移动设备上第 $t$ 个时隙申请的计算任务所需的执行时延为

\[\tag{2} D_{\text {mobile }}^{t}=\sum_{w=1}^{W}\left(f_{w}^{t}\right)^{-1}\]

对应的能量消耗为

\[\tag{3} E_{\text {mobile }}^{t}=\kappa \sum_{w=1}^{W}\left(f_{w}^{t}\right)^{2}\]

其中 $\kappa$ 是取决于芯片架构的有效开关电容，且假设CPU周期频率受限于 $f _ {\mathrm{CPU}} ^ {\max }$，即 $f _ {w} ^ {t} \leq f _ {\mathrm{CPU}} ^ {\max }, \forall w=1, \cdots, W$。

3.2.2 移动边缘执行模型：

假设：

假设服务器上有足够的计算资源，因此计算延迟可以忽略。
服务器上计算的输出数据很小，因此从服务器到移动设备的反馈的传输延迟也可以忽略。
发射功率应该小于最大发射功率，即 $p ^ {t}<p _ {\mathrm{tx}} ^ {\max }$。根据香农公式，$t$ 时隙的最大信息传输速率为 $r\left(h ^ {t}, p ^ {t}\right)=\omega \log _{2}\left(1+\frac{h^{t} p^{t}}{\sigma}\right)$，其中，$\omega$ 是系统带宽，$\sigma$ 是接收器的噪声功率。因此，如果计算任务由 MEC 服务器执行，则执行延迟等于输入比特的传输延迟，即

\[\tag{4} D_{\text {server }}^{t}=\frac{L}{r\left(h^{t}, p^{t}\right)}\]

移动设备消耗的能量由下式给出

\[\tag{5} E_{\text {server }}^{t}=p^{t} \cdot D_{\text {server }}^{t}=p^{t} \cdot \frac{L}{r\left(h^{t}, p^{t}\right)}\]

3.2.3 能量收集模型：

EH过程可以建模为连续的能量包到达的过程，即 $E _ {H} ^ {t}$ 个能量单位在 $t$ 时隙的开始到达移动设备，假设不同的时隙，到达的能量包是独立同分布的，最大值是 $E _ {H} ^ {\max}$。虽然独立同分布的过程简单，但是其反映了可再生能源的间歇性和随机性。在每个时隙中，部分到达的能量，表示为 $e ^ {t}$，满足

\[0 \leq e^{t} \leq E_{H}^{t}, t \in \mathcal{T}\tag{6}\]

将被收集并存储在电池中，从下一个时隙开始，用于本地执行或者计算卸载。假设电池容量足够大，作者后面证明了通过选取 $e ^ {t}$ 的值，在所提出的计算卸载策略下，电池的能量水平是确定的上限，因此在实际实现中我们只需要一个有限容量的电池。将电池能量水平表示为 $B^{t}$，假设 $B ^ {0}=0$，且 $B ^ {t}<+\infty, t \in \mathcal{T}$。为了简单起见，本文忽略了用于本地计算和传输以外的其他目的的能量消耗。将移动设备在时隙 $t$ 消耗的能量记为 $\mathcal{E}\left(\boldsymbol{I} ^ {t}, \boldsymbol{f} ^ {t}, p ^ {t}\right)$，取决于选定的计算模式、规划的 CPU 周期频率和分配的发射功率，可以表示为

\[\tag{7} \mathcal{E}\left(\boldsymbol{I}^{t}, \boldsymbol{f}^{t}, p^{t}\right)=I_{\mathrm{m}}^{t} E_{\mathrm{mobile}}^{t}+I_{\mathrm{s}}^{t} E_{\mathrm{server}}^{t}\]

受以下能量因果关系约束：

\[\tag{8} \mathcal{E}\left(\boldsymbol{I}^{t}, \boldsymbol{f}^{t}, p^{t}\right) \leq B^{t}<+\infty, \quad t \in \mathcal{T}\]

因此，电池能级根据以下方程式演变：

\[B^{t+1}=B^{t}-\mathcal{E}\left(\boldsymbol{I}^{t}, \boldsymbol{f}^{t}, p^{t}\right)+e^{t}, \quad t \in \mathcal{T}\tag{9}\]

随着EH移动设备的出现，MEC系统的计算卸载策略设计变得比传统的电池供电的移动云计算系统复杂得多。具体地说，ESI和CSI都需要处理，并且时间上相关的电池能量水平使得系统决策耦合在不同的时隙中。因此，一个最优的计算卸载策略应该在当前和未来计算任务的计算性能之间取得良好的平衡。

3. 问题表述

3.1 执行成本最小化问题

执行延迟是衡量用户 QoE 的关键指标之一。
当丢弃任务时，也应该对其进行惩罚。

因此，作者将执行成本定义为执行延迟和任务丢弃成本的加权和，可以用以下公式表示：

\[\operatorname{cost}^{t}=\mathcal{D}\left(\boldsymbol{I}^{t}, \boldsymbol{f}^{t}, p^{t}\right)+\phi \cdot \mathbf{1}\left(\zeta^{t}=1, I_{\mathrm{d}}^{t}=1\right)\tag{10}\]

其中，$\phi$ （单位：s）是任务丢弃成本的权重。$\mathbf{1}(\cdot)$ 是指示器函数，

\[\mathcal{D}\left(\boldsymbol{I}^{t}, \boldsymbol{f}^{t}, p^{t}\right)=\mathbf{1}\left(\zeta^{t}=1\right) \cdot\left(I_{\mathrm{m}}^{t} D_{\mathrm{mobile}}^{t}+I_{\mathrm{s}}^{t} D_{\mathrm{server}}^{t}\right)\tag{11}\]

假设成功执行任务比丢弃任务更可取，所以 $\tau _ {d} \leq \phi$。

一个任务应该在deadline前执行，

\[\mathcal{D}\left(\boldsymbol{I}^{t}, \boldsymbol{f}^{t}, p^{t}\right) \leq \tau_{d}, t \in \mathcal{T}\tag{12}\]

因此，执行成本最小化（ECM）问题可以表征为：

\[\begin{align} \mathcal{P}_{1}: & \min _{\boldsymbol{I}^{t}, \boldsymbol{f}^{t}, p^{t}, e^{t}} \lim _{T \rightarrow+\infty} \frac{1}{T} \mathbb{E}\left[\sum_{t=0}^{T-1} \operatorname{cost}^{t}\right] \\ \tag{1} \text{s.t.} \ & I_{\mathrm{m}}^{t}+I_{\mathrm{s}}^{t}+I_{\mathrm{d}}^{t}=1, \quad t \in \mathcal{T} \\ \tag{6} & 0 \leq e^{t} \leq E_{H}^{t}, \quad t \in \mathcal{T} \\ \tag{8} & \mathcal{E}\left(\boldsymbol{I}^{t}, \boldsymbol{f}^{t}, p^{t}\right) \leq B^{t}<+\infty, \quad t \in \mathcal{T} \\ \tag{12} & \mathcal{D}\left(\boldsymbol{I}^{t}, \boldsymbol{f}^{t}, p^{t}\right) \leq \tau_{d}, \quad t \in \mathcal{T} \\ \tag{13} & I_{\mathrm{m}}^{t}+I_{\mathrm{s}}^{t} \leq \zeta^{t}, \quad t \in \mathcal{T} \\ \tag{14} & \mathcal{E}\left(\boldsymbol{I}^{t}, \boldsymbol{f}^{t}, p^{t}\right) \leq E_{\max }, \quad t \in \mathcal{T} \\ \tag{15}& 0 \leq p^{t} \leq p_{\mathrm{tx}}^{\max } \cdot \mathbf{1}\left(I_{\mathrm{s}}^{t}=1\right), \quad t \in \mathcal{T} \\ \tag{16} & 0 \leq f_{w}^{t} \leq f_{\mathrm{CPU}}^{\max } \cdot \mathbf{1}\left(I_{\mathrm{m}}^{t}=1\right) \\ & w=1, \cdots, W, \quad t \in \mathcal{T} \\ & I _ {\mathrm{m}} ^ {t}, I _ {\mathrm{s}} ^ {t}, I _ {\mathrm{d}} ^ {t} \in\{0,1\}, \quad t \in \mathcal{T} \tag{17} \end{align}\]

其中 (13) 表示如果没有请求计算任务，则移动执行和 MEC 服务器执行都不可行。(14) 是电池放电约束，即每个时隙的电池输出能量不能超过 $E _ {\max}$，这对于防止电池过放电是必不可少的。最大允许发射功率和最大 CPU 周期频率约束分别由 (15) 和 (16) 施加，而用于计算模式指示符的 0/1 指示符约束由 (17) 表示。

3.2 问题分析

在所考虑的 MEC 系统中，系统状态由任务请求、可收获能量、电池能量水平和信道状态组成，动作是能量收集和计算卸载决策，包括预定的 CPU 周期频率和分配的发射功率。允许动作集仅取决于当前系统状态，而与状态和动作历史无关。系统当前状态只取决于上一个状态。此外，目标是长期平均执行成本。因此，P1是一个马尔可夫决策过程(MDP)问题。原则上，P1 可以通过标准的 MDP 算法(例如相对值迭代算法和线性规划重构法)来最优求解，但是需要离散化计算成本太高，作者采用基于Lyapunov优化的动态计算卸载(LODCO)算法求解。

MEC+EH-IoTs

论文阅读笔记