随着5G通信技术的发展, 移动设备种类和数量不断增长, 对于任务的实时计算要求也越来越高^[1]。移动边缘计算(Mobile Edge Computing, MEC)的出现实现了设备间的低延迟通信、计算与控制。MEC通过将移动用户设备的任务卸载至边缘服务器或云服务器中, 大大减少设备的运行时间与能耗^[2], 具有高灵活、低时延的特性^[3]。它作为一种新的计算架构, 可以将移动设备的任务卸载至附近的边缘服务器中, 从而有效平衡网络中的计算资源和链路负载。其中, 卸载算法的主要目标是在满足时间约束的条件下使得系统能耗最小化^[4]。

移动用户通过将不同任务卸载至微基站边缘服务器或宏基站云服务器中, 来优化整个系统的运行性能, 提高应用程序的使用效率。计算卸载作为MEC中的关键技术之一, 是将移动设备中的任务卸载至边缘服务器中, 以解决资源限制和提高处理效率。

在执行卸载任务时, 卸载过程会受到移动无线通信质量、计算资源和网络环境等因素的影响, 同时也会占用系统的带宽, 从而影响上行无线信道, 增加系统延迟。因此, 如何进行计算卸载是MEC中的关键问题。另外, 采用无线传输的方式进行任务卸载, 必须考虑不断变化的无线传输带宽, 而自适应算法可以根据动态无线环境来确定卸载决策。

MEC网络中的研究重点在于运用卸载决策和卸载资源的联合规划来优化系统效率。ZHANG G W等人^[5]提出了一种公平且能耗最小化的任务卸载算法(Fair and Energy-Minimized Task Offload, FEMTO)。该算法考虑了卸载的能耗、网络节点的历史平均能量和节点的优先级。MUKHERJEE M等人^[6]将卸载问题和上行链路信道分配问题设为二次约束二次规划(Quadratic Constraint Quadratic Programming, QCQP)问题, 通过矩阵算法求解, 并获得了次优解。WU H M等人^[7]提出了一种基于Lyapunov优化的动态卸载算法。该算法基于当前解可以找到最优解, 但需要大量的运行时间和多次迭代才能收敛到一个解。ZHAO P T等人^[8]和YANG X T等人^[9]提出通过分枝定界算法寻找最优解, 但算法的运行时间随着用户数量的增加呈指数级上升, 很难应用于实际系统。CHEN M H等人^[10]将卸载问题转化为非凸QCQP问题, 通过所提出的半定松弛算法(Semi-Definite Relaxation Algorithm, SDRA)求解。大约在100次松弛试验后, 该算法可以找到最优解, 但算法执行时间较长, 且参数复杂, 不适用于无线动态环境。

本文提出了一种新的动态规划算法(Dynamic Programming Algorithms Harvest, DPAH)。该算法经过多次迭代后可以找到最优解, 进而快速找到最优决策, 但最终解决方案取决于无线传输带宽、基站以及边缘服务器的计算能力。

移动边缘计算系统中单个节点的网络模型由移动设备、基站和边缘服务器组成, 应用程序可以在本地执行或传输到边缘服务器中执行。单个节点网络模型如图 1所示。

移动用户包括1个不可卸载的本地任务和N个独立可卸载的应用程序。本地任务可以直接处理任务交互以及访问移动设备上特定信息的任务。可卸载的应用程序通过无线链路传输至基站中, 然后转发至边缘服务器。其中, 移动设备使用无线网络进行无线传输, 而无线网络的传输带宽可能发生动态变化, 因此在动态规划中移动设备需要根据当前传输带宽来决定是否进行卸载任务。同时, 由于执行任务有时间限制, 因此还必须考虑移动设备与边缘服务器之间传输所需时间。

假设任务i的输入数据为D_in(i), 输出数据为D_out(i); E_li和t_li分别表示本地处理任务i的能耗和执行时间; E_ri和t_ri分别表示任务i由基站传输至边缘服务器的能耗和执行时间, E_ti和t_ti分别表示任务i由用户传输至基站的能耗和执行时间。用于卸载每个任务的传输能耗取决于无线传输带宽, 假设每个任务的传输时间等于每个任务的大小与传输速率的比值, 那么传输速率的变化将影响卸载决策。

完成每个任务的总能耗包括上行传输、基站处理、边缘服务器处理过程所需的能耗。本文只考虑上行传输能耗^[11-12], 并允许MEC服务器使用电网供电。

移动用户首先要决定任务i是进行本地处理, 还是卸载至边缘服务器。这一决定的赋值表示为

$ x_i= \begin{cases}0, & \text { 任务 } i \text { 在本地处理 } \\ 1, & \text { 任务 } i \text { 卸载至边缘服务器 }\end{cases} $

(1)

任务上行传输路径包含由用户传输到基站(过程1)和由基站传输至边缘服务器(过程2)。过程1的传输时间t_ti取决于输入速率R_ua和输入数据大小D_in(i), 公式为

$ \sum\limits_{i=1}^N t_{\mathrm{t} i} x_i=\frac{\sum\limits_{i=1}^N D_{\mathrm{in}}(i) x_i}{R_{\mathrm{ua}}} $

(2)

式中: N——任务数。

同理, 过程2的传输时间t_ri取决于传输速率R_ae和输出数据大小D_out(i), 可得

$ \sum\limits_{i=1}^N t_{\mathrm{r}i} x_i=\frac{\sum\limits_{i=1}^N D_{\mathrm{out}}(i) x_i}{R_{\mathrm{ae}}} $

(3)

整个传输过程中产生的总能耗E是本地处理能耗E_li、过程1的能耗E_ti与过程2的能耗E_ri之和, 可表示为

$ E=\sum\limits_{i=1}^N\left[\left(1-x_i\right) E_{1 i}+x_i E_{\mathrm{r} i}+x_i E_{\mathrm{t} i}\right] $

(4)

相应地, 整个传输过程的执行时间t为本地处理时间t_li、过程1的时间t_ti与过程2的时间t_ri之和, 可表示为

$ t=\sum\limits_{i=1}^N\left[\left(1-x_i\right) t_{1 i}+x_i t_{\mathrm{r}i}+x_i t_{\mathrm{t} i}\right] $

(5)

其中, t≤t_max, t_max为规定的最大执行时间。

本文的目标是确认哪些任务应传输至边缘服务器进行卸载, 以满足移动应用程序在执行时间约束下实现能耗最小化。因此, 上述优化问题表示为minE, 且满足t≤t_max。

本文采取一种新的填表方式, 创建一个N×N的表来表示存储卸载任务的比特流, 每个位置表示需要卸载的任务。

首先, 生成第1个解的随机比特流, 然后将其分配填入表中, 设定将“1”分配给下一个水平单元格, 将“0”分配给下一个垂直单元格。如果比特流第1位是1, 则初始单元格所在位置为(1, 2), 如果比特流第1位是0, 则初始单元格所在位置为(2, 1)。采取这种填表方式可以避免算法对公共比特串的位置进行额外计算。

当生成新的随机比特流时, 计算表内每个单元格对应的能耗和时间, 以及整个比特流的能耗和时间。当出现新的比特流时, 可以不用计算公共单元格中的能耗和时间, 而直接对新的单元格进行计算。

然后, 将计算所得新的总能耗与该比特流现有的能耗进行对比。若新的能耗小于现有能耗, 则保留新的字符串删除旧字符串, 同时用新能耗代替旧能耗。

根据公共单元的值更新新字符串的剩余单元能耗和时间, 如果现有比特流总能耗小于公共单元中新比特流的能耗, 则保持现有字符串并计算下一个新字符串的能耗和时间。通过不断迭代运算, 当迭代次数、时间、能耗或汉明距离满足设定标准时, 输出总能耗与总时间。

上述DPAH算法的具体程序如表 1所示。

根据文献[10], 将任务数N设置为10, 本地计算时间T_li=4.75×10^－7s/bit, 本地处理能耗E_li=3.25×10^－7 J/bit。设置每个任务的输入数据大小D_in(i)均匀分布在10~30 MB, 输出数据大小D_out(i)均匀分布在1~3 MB。在任务传输至边缘服务器过程中, 每个任务传输时间为任务大小与传输速率的比值, 最大执行时间为T_max=700 s。输入速率的变化范围为3~10 Mb/s。基站中, 最高传输速率为72 Mb/s。

在MATLAB-R2016b软件中进行算法仿真, 仿真数据为100次实验的平均值。本文分别利用输入速率、传输速率和任务数等不同参数对所提算法的性能进行评估。同时, 将本文DPAH算法与模拟退火算法(Simulates Annealing, SA)、SDRA算法和遗传算法(Genetic Algorithm, GA)进行对比实验。

不同输入速率下, 4种算法和全卸载、本地执行2种状态的能耗如图 2所示。

由图 2可以看出, 在本地执行状态下, 由于系统仅在移动用户本地执行, 不产生传输能耗, 因此总能耗保持不变。在其他算法和状态下, 对设备所有任务进行卸载分配, 所产生的能耗随输入速率的增大而下降。其中, 在全卸载状态下, 由于传输至边缘服务器的传输成本较大, 因此产生的能耗较多。DPAH算法所产生的能耗始终小于其他算法所产生的能耗。由此可见, 在不同传输速率下, DPAH算法的能耗优于其他算法。

不同输入速率下, 4种算法和全卸载、本地执行2种状态的时延如图 3所示。

由图 3可以看出, 在本地执行状态下, 虽然不受输入速率的影响, 但用户自身的处理速率较慢, 因此时延最大且保持不变。在其他算法和状态下, 时延随输入速率的增加而减小。其中, 在全卸载状态下, 虽然时延有所减小, 但传输成本增加, 能耗较大。当传输速率一定时, DPAH算法所产生的时延小于其他算法。

当输入速率和传输速率一定时, 不同算法的时延如图 4所示。

由图 4可以看出, 不同算法产生的时延随着任务数的增多而增大, 而DPAH算法所产生的时延始终小于其他算法。

当任务数相同时, 不同传输速率下各算法的能耗如图 5所示。

由图 5可以看出, 当传输速率为零时, 移动设备任务只在本地执行, 4种算法产生的能耗相同。在实验设定的多种传输速率下, DPAH算法所产生的能耗均小于其他算法。

当任务数相同时, 不同传输速率下各算法的时延如图 6所示。

由图 6可以看出, 当传输速率为零时, 4种算法的时延最大。当传输速率增加后, DPAH算法的时延均小于其他算法。

本文提出了一种自适应动态规划算法, 将动态规划与随机化相结合, 可以快速找到最优卸载方案。仿真结果表明, 该算法可以找到近似最优解, 在不损失计算效率的前提下处理较多的卸载问题。DPAH算法倾向于卸载更多的计算任务, 以便满足在时间约束条件下, 使能耗和时延最小化。在未来的工作中, 一方面可以将该算法与物联网自适应计算卸载框架相结合, 使应用程序实现按需卸载; 另一方面, 考虑将其与粒子群算法相结合, 寻找更优的卸载决策。