移动边缘计算环境中基于能耗优化的深度神经网络计算任务卸载策略

高 寒，李学俊+，周博文，刘 晓，徐 佳

(1.安徽大学 计算机科学与技术学院，安徽 合肥 230601；2.迪肯大学 信息技术学院，澳大利亚 墨尔本 VIC 3125)

1 问题的提出

目前，深度神经网络(Deep Neural Networks, DNNs)因具有在海量数据中准确地提取信息，赋予机器感知环境的能力，已经迅速成为移动智能应用中的重要技术。如，DNNs已经被证明能在包括计算机视觉、自然语言处理和语言识别[1-3]等众多问题领域提供优于其他机器学习方法的解决方案。DNNs的执行有两种常见计算任务卸载策略：计算任务基于终端设备执行的不卸载和计算任务基于云端执行的完全卸载。基于终端设备的DNNs执行给终端设备带来沉重的能耗负担，由于终端设备资源有限，电池和续航方案的发展状况远远跟不上深度学习应用急速增长的需求[4]。基于云服务器的DNNs执行，从终端设备生成的原数据直接发送到云进行执行，然后将结果返回给终端设备。但利用集中式云计算的范式，大量数据需通过广域网(Wide Area Network, WAN)上传到远端云，由于数据传输网络有限，从而导致网络拥塞和高时延[5-6]。例如，谷歌的自动驾驶汽车每秒可产生高达750 MB的传感器数据[7]，但现在最快的4 G平均上传速率仅为5.85 Mbps[8]。诸如此类数据密集型的实时性DNNs应用除了自动驾驶还有虚拟现实、增强现实和智慧城市等，如何在保证实时性的同时减少终端设备的能耗是仍待解决的问题。

为克服上述基于单一资源的任务卸载策略的弊端，本文引入新兴的计算架构移动边缘计算(Mobile Edge Computing, MEC)[9]。该架构的基本思想是将云计算平台的各项服务拓展到网络边缘。移动边缘计算架构包括终端设备、边缘服务器、云服务器3层，边缘服务器是部署在移动基站上的小规模计算中心，因此终端设备和边缘服务器通过局域网(Local Area Network, LAN)进行数据传输。移动边缘计算中可以统一考虑端—边—云多重资源，可以先将原数据在终端设备和边缘服务器进行预处理，对数据提前进行过滤和分析，而不需要将原数据通过WAN低速传输到云服务器上处理，这样能充分利用边缘服务器的计算资源，减少网络数据流量压力，且能实现任务的低时延和低能耗[10-11]。

典型的DNNs模型通常具有多层结构，可以以神经网络层为单位对DNNs的计算任务进行拆分。并且DNNs的执行过程实际是信息提取的过程，在提取到足够信息之前，每个神经网络层可以快速缩小数据大小。如图1所示，Tiny YOLOv2[12]的输入数据大小为0.99 MB，而中间层Maxpool5的输出大小为0.08 MB，减少了91%。因此，DNNs的执行非常适合移动边缘计算环境。本文考虑在移动边缘计算环境中对DNNs计算任务进行卸载，以降低终端设备能耗和传输时间。如图2所示，将完整的DNNs模型各层部署到移动边缘计算环境中的各种计算资源上，只在终端设备或边缘服务器上执行部分DNNs计算任务后，将提取特征后减少过的中间值传输到云上，而云得到中间值可以从任何断点恢复计算[13]，接着执行余下计算任务。在移动边缘计算环境中综合考虑终端设备、边缘服务器、云服务器的任务卸载策略，不仅能实现低时延、低能耗和高吞吐量，还在移动边缘计算环境中的深度学习很好地保护了用户隐私。通过边缘服务器的预处理，从而避免将原始用户数据直接发送给远程服务提供商[14]。

虽然认识到移动边缘环境中DNNs任务卸载的好处，但由于DNNs各层的计算任务具有不同的输入、输出数据和计算负载，如何选择任务调度方案，才能保证时间约束下尽可能地优化终端设备能耗，即如何决定DNNs各层的计算任务分别卸载到终端设备、边缘服务器还是云端。本文首先基于DNNs结构将其计算任务建模为有向无环图(Directed Acyclic Graph, DAG)，在移动边缘计算环境中建立了适用于不同DNNs结构计算任务卸载的时间和能耗评价模型，然后设计了时间约束下评价能耗的适应度函数，最后提出了移动边缘计算环境中基于多重资源任务卸载的粒子群优化调度(Multi-Resource task offloading based Particle Swarm Optimization Scheduling, MRPSO)算法。该算法能够考虑DNNs各层计算任务不同的输入、输出数据和计算负载，弹性自适应地选择调度方案，使其在满足时间约束下，充分优化终端设备能耗。实验表明，本文所提出的解决方案适应度值最低，即在满足时间约束下，能更好地优化终端设备能耗。

2 相关工作

为了将深度学习应用更好地与移动终端设备结合，针对DNNs模型越来越复杂，同时移动终端设备的计算资源受限等挑战，一些研究团队从硬件和软件的角度提出方案优化服务质量;硬件推理加速是其中一种方法。例如，华为公司在新款智能手机芯片中加入了专门的神经网络处理单元，使其DNNs推理能力有较大提升。文献[15]探索了在移动端使用图形处理器(Graphics Processing Unit, GPU)实现实时深度学习推断的可能性。还有一些团队在尽量不影响推理精度的情况下，构建了轻量级DNNs模型。例如文献[16-17]通过构建轻量级DNNs模型减少终端设备的推理压力，在移动设备上完全执行推理功能。很多科技公司也积极地发布针对移动终端设备更轻量级的深度学习开发框架，如Google的TensorFlow Lite、Facebook的Caffe2go。但是模型的轻量化都牺牲了一定的精度，最主要的是完全运行于移动终端设备，仍然会大大增加终端设备的能耗，减少使用寿命。

另一方面，一些研究与上述硬件加速和模型轻量化的创新不同但互为补充，其研究边云之间的协同计算，将DNNs计算任务从资源受限的移动终端设备部分卸载至云端。文献[18-19]通过将DNNs计算任务部分卸载至云端，对比完全卸载到云端的策略，通过实际测量，时延、终端设备能耗都有明显的优化。但是该方法是固定DNNs计算任务的放置，并不能根据模型的差异和网络变化自主进行调度。文献[20]考虑在边缘服务器服务能力有限的情况下，提出调度算法来选择合适的调度方案，最大化任务在边缘服务器的部署，以减少网络拥塞，但没有对时间和能耗进行评估。文献[21-22]通过回归模型预测DNNs各层分别在终端设备和云的执行时间，然后进行遍历，选择最短时间下对应的DNNs层调度方案。该方法需预先根据历史数据建立回归模型，且不适合对含有并行DNNs结构的网络进行有效划分。

本文主要研究了移动边缘计算环境中DNNs计算任务的卸载问题。相比上述已有工作，本文考虑了移动边缘计算环境中端—边—云多重计算资源，并基于DNNs结构特征，建立了移动边缘计算环境中DNNs计算任务卸载的时间和能耗评价模型。在该模型的基础上，设计了移动边缘计算环境中基于能耗优化的DNNs计算任务卸载策略。最后提出了基于多重资源任务卸载的粒子群调度算法，该算法适用于不同DNNs，可自主选择调度方案，从而保证在时间约束下，降低终端设备能耗。

3 移动边缘计算中深度神经网络计算任务卸载模型

3.1 基于DNNs结构的计算任务模型和负载模型

首先根据DNNs结构对其计算任务进行建模，以神经网络层为单位，对计算任务之间的依赖关系进行描述，然后说明神经网络层计算任务的负载模型。

3.1.1 基于DNNs结构的计算任务模型

根据DNNs结构，将以神经网络层为单位拆分的计算任务建模为一个DAG，表示为G=(V∪{ventry,vexit},E)。其中：V=(v1,v2,…,vNt)代表顶点集合，Nt代表DNNs层的总数。不同顶点表示不同神经网络层的计算任务，各神经网络层的计算任务是不可分割的，只能在同一个计算资源上处理。添加输入顶点ventry和输出顶点vexit表示DNNs的起点和终点。E代表有向边集合，每条边eij=(vi,vj)∈E(i,j=1,2,…,Nt;i≠j)代表各DNNs层计算任务的依赖关系，vj必须在vi之后执行，且vi的输出是vj的输入。每个vi∈V都有计算负载Wi，输入数据大小Ini，输出数据大小Outi。pred(vi)代表vi所有直接前置DNNs层的计算任务，succ(vi)代表vi所有直接后置DNNs层的计算任务。如图3所示，本文分别给出了NiN[23], Tiny YOLOv2，AlexNet[1]，ResNet-18[24]四个常用DNNs的DAG实例[25]。

3.1.2 负载模型

对于DNNS来说，只要网络结构确定，在不实际执行神经网络的情况下能估计出其执行时间[26]。使用浮点运算次数(Floating Point Operations, FLOPs)来表示vi，计算负载Wi，尽管只考虑FLOPs忽略了一些其他操作所花费时间(如数据转换)，但它可作为执行时间计算的主要指标[20]。如今的DNNs模型中，卷积和全连接层是最常用且计算密集的两种深度网络层，其他类型的神经网络层FLOPs计算模型简单[26-27]，因此本文给出卷积和全连接层FLOPs的计算模型。

对于卷积层负载如式(1)所示：

Wi=(2×Cin×K2[-1])×Hout×

Wout×Cout；

(1)

对于全连接层如式(2)所示：

Wi=(2×I[-1])×O。

(2)

式(1)和式(2)中：Hout、Wout和Cout分别是输出特征图的高、宽和通道数;K是卷积核的宽;Cin是输入特征图通道数;I和O分别是输入神经元数目和输出神经元数目；括号内的-1是在不考虑偏置时才需要的，而考虑加上偏置的情况时则不需要-1。

3.2 任务卸载时间与能耗模型

基于多重资源任务卸载的粒子群调度算法是为了在保证时间约束的情况下，尽可能地降低终端设备能耗，主要是依据DNNs执行的总时间和终端设备的总能耗两个评价指标。因此，需要建立相应的时间和能耗评价模型。现存并没有针对DNNs特点在多重资源下的任务卸载策略，特别是大多没考虑计算任务间的数据传输，因此本文基于DNNs的特点，根据文献[26,28]改进多重资源卸载下的时间和能耗评价模型。

3.2.1 任务卸载时间模型

(3)

(4)

(5)

(6)

式(4)～式(6)中：BL和BW分别代表LAN和WAN带宽;Outi为前置DNNs层计算任务vi的输出数据，同样也是任务vj的输入数据。任务vi和vj如果被分配到相同的计算资源时，其任务间的传输时间为0。由于终端设备Rend在本文有且仅有一个，则相邻DNNs层计算任务的卸载决策均为终端设备时，该对任务的传输时间为0。用户输入数据的发送以及最终回传结果数据的接收均为终端设备，因此对于输入顶点ventry和输出顶点vexit,可认为它们的计算资源均为终端设备，即Rentry,Rexit∈Rend。

(3)DNN运行总时间ST(vi)和FT(vi)分别表示任务vi的开始执行时刻和完成时刻，T(W)表示DNN运行总时间，如式(7)～式(9)所示：

ST(vi)=max∀vp∈pred(vi){FT(vp)+

(7)

(8)

(9)

式(7)～式(9)中任务vi的开始执行时刻ST(vi)取决于直接前置DNNs层上计算任务vp完成时刻及其数据传输时间之和。如图3c和图3d所示，DNNs中存在并行结构，则可能一个任务vi有多个前驱任务vp，此时需要等到所有vp执行完毕之后vi才开始执行，因此需要取其执行完成时刻的最大值。任务vi的完成时刻FT(vi)则是vi的开始时刻和其计算时间之和，当任务vi的前驱任务为ventry时，则FT(ventry)=0。任务vi的后继任务是输出任务vexit时，其累计时间定义为DNNs运行总时间T(W)。

3.2.2 任务卸载能耗模型

终端设备的能耗Eend是根据任务在不同卸载决策进行执行时，终端设备的执行与数据传输能耗构成，主要包括任务在终端设备的执行能耗、任务数据发送到云服务器或边缘服务器的数据发送能耗以及任务执行完成后结果数据回传终端设备的数据接收能耗3个部分，具体如式(10)所示：

Eend=pend×Tend+pup×Tup+Pdown×Tdown。

(10)

式中：Pend、Pup、Pdowm分别表示终端执行功率、终端上传功率、终端接收功率；Tend、Tup、Tdowm分别表示终端执行时间、终端上传时间、终端接收时间，如式(11)～式(13)所示：

(11)

(12)

(13)

式(11)～式(13)中：vi所在执行资源Ri∈Rend时，终端设备为数据发送方；vj所在执行资源Rj∈Rend，终端设备为数据接收方。由式(10)～式(13)可以看出，终端设备的能耗由任务的卸载决策决定，即任务的不同卸载决策决定了该任务的能耗计算方式。例如，当任务不卸载时其能耗就为任务在终端上的执行能耗；而当任务卸载至边缘或云服务器中,则需要考虑计算任务的数据发送与接收能耗。

4 基于多重资源任务卸载的粒子群调度算法

基于第3章提出的移动边缘计算环境中DNNs多重资源任务卸载的时间和能耗模型，本章设计出满足时间约束下评价终端设备能耗的适应度计算函数，然后提出移动边缘计算环境中基于多重资源任务卸载的粒子群调度算法，将DNNs层上的计算任务分配给合适的计算资源，得到合适的调度方案，用于解决在时间约束下终端设备能耗优化问题。

4.1 适应度函数

适应度函数用来评估粒子群算法中粒子所对应调度方案的优劣。本文基于文献[30-31]适应度函数的设计，结合移动边缘计算环境中DNNs任务卸载的时间和能耗模型，设计出一种新的适应度函数，能综合评价卸载方法的执行时间和终端设备能耗，如式(14)所示：

fitness=(f1×Eend)+

(14)

式中：Eend表示终端设备总能耗，T(W)表示移动边缘计算环境DNNs运行总时间，Tdeadline表示DNNs执行的时间约束。该适应度函数可以衡量基于粒子群算法生成的调度方案的优劣。适应度值越低，对应的终端设备能耗越低；反之，所需终端设备能耗越高。该适应度函数主要由两部分构成：①DNNs运行总时间小于时间约束时(f1=1,f2=0)，适应度值为调度方案终端设备能耗；②DNNs运行总时间大于时间约束时(f1=0,f2=1)，适应度值为能耗和超过时间约束比之积。

4.2 算法描述

基于DNNs结构的特点，设计了移动边缘计算环境中时间和能耗模型以及适应度函数，提出移动边缘计算环境中基于多重资源任务卸载的粒子群优化调度算法MRPSO，具体算法流程如下：

算法1移动边缘计算环境中基于多重资源任务卸载的粒子群调度算法。

输入：算法迭代次数Iteration，云服务器Clouds，边缘服务器Edges，边缘设备End，粒子个数pNum，响应时间Tdeadline，深度神经网络G；

输出：能耗优化的任务卸载决策Denergy-best与调度方案Senergy-best。

1 for j=1 to pNum do

2 随机初始化调度方案Sj，搜索速度vj及其卸载决策dj；

3 计算此粒子对应的卸载决策dj与调度方案Sj的总时间(式(3)～式(9))；

4 计算此粒子对应的卸载决策dj与调度方案Sj的总能耗(式(10)～式(13))；

5 计算此粒子对应的卸载决策dj与调度方案Sj的适应度值(式(14))

6 end for

7 for k=1 to Iteration do

8 根据搜索速度更新所有粒子对应卸载决策dj与调度方案Sj；

9 for j=1 to pNum do

10 计算每个粒子对应的卸载决策dj与调度方案Sj的总时间(公式3～9)；

11 计算每个粒子对应的卸载决策dj与调度方案Sj的总能耗(公式10～13)；

12 计算每个粒子对应的卸载决策dj与调度方案Sj的适应度值(公式14)；

13 if 计算所得的适应度值比之前计算所得的适应度值小 then

14 更新该粒子当前最优的适应度值、总时间以及总能耗

15 end if

16 end for

17 找出适应度值最小的粒子即此迭代全局最优任务卸载决策Dglobal-best与调度方案Sglobal-best；

18 更新每个粒子对应任务卸载决策dj与调度方案Sj的搜索速度；

19 end for

20 return最终得到最优任务卸载决策与调度方案Denergy-best与Senergy-best。

MRPSO算法先初始化调度方案、粒子搜索速度以及任务卸载决策，且计算每个粒子对应的初始调度方案的总时间、总能耗和适应度值(第1～6行)。然后进入算法迭代，首先根据搜索速度由粒子群位置更新公式[32]，更新所有粒子对应任务卸载决策与调度方案(第8行)。然后对于其中每一个卸载决策与调度方案，计算其任务执行总时间(第10行)、总能耗(第11行)以及适应度值(第12行)。接下来判断适应度值是否比原来的小，若是则更新此粒子当前最优的适应度值、总时间、以及总能耗(第13～15行),并从粒子群中找到适应度值最小的粒子所对应的任务卸载决策与调度方案，作为本次迭代的全局最优任务卸载决策与调度方案(第17行)。每次迭代的最后由粒子群的速度更新公式[32]，更新每个粒子的搜索速度、下一次迭代更新粒子的任务卸载决策与调度方案(第18行)。最后在达到迭代次数时，得出在用户响应时间约束下的能耗最优的任务卸载决策与调度方案(第20行)。该算法通过结合移动边缘计算环境中DNNs多重资源任务卸载时间和能耗模型与评价终端设备能耗的适应度函数，得到时间约束下终端设备能耗最优的任务卸载决策与调度方案。如果任务卸载决策与调度方案的数量为K，算法迭代次数为D，DNNs总层数为Nt，则算法的时间复杂度为O(KDNt)。

5 实验分析

5.1 实验环境及参数设置

仿真实验采用C++编写，均运行于Visual Studio 2017，运行环境为Intel core i7 3.6 GHz CPU，8 GB内存的PC机。根据Tiny YOLOv2结构生成DAG图，并随机生成不同的输入数据大小。一旦DNNs结构确定，每个DNNs任务根据输入数据大小可得到不同的中间数据和各层计算任务负载。本文仿真实验设置1台终端设备的工作功率、上传功率和接受功率分别为0.7 W、0.1 W、0.025 W，其计算能力为每秒290千兆浮点运算(Giga Floating Point Operations Per Second, GFLOPS)，2台边缘服务器(其计算能力均为2.1 TFLOPS)，1台云服务器(其计算能力为8.7TFLOPS)和2台云服务器(其计算能力为3.5 TFLOPS)[20]。取云服务器计算能力的平均值作为中型服务器的计算能力，用户时间约束为DNNs任务在中型服务器上平均执行时间[33]。LAN和WAN的网络带宽分别为100 Mbps和10 Mbps[29]。

5.2 实验结果与分析

本节从适应度值、终端设备能耗和DNN任务完成时间3方面对基于4种任务卸载策略的粒子群调度算法进行对比。对比的任务卸载策略包括：基于终端设备不卸载(记为LOPSO)、基于云服务器的完全卸载(记为FOCPSO)、基于端云的部分卸载(记为POPSO)，以及本文提出的基于端—边—云多重资源卸载MRPSO。

5.2.1 适应度值的比较

下面对4种基于不同任务卸载策略的粒子群算法所对应调度方案适应度值进行比较，以证明本文所提出的基于多重资源卸载策略的MRPSO算法能够在考虑用户响应时间约束的前提下，充分降低边缘计算环境中的终端设备能耗。

4种卸载策略所对应的粒子群调度算法的平均适应度值比较如图4所示。不断增大DNNs任务数量，基于多重资源卸载策略的MRPSO算法所得调度方案的平均适应度值均最低。尤其是比较基于单一资源卸载策略LOPSO和FOCPSO算法，MRPSO平均适应度值比其低70%到80%。另一种计算卸载策略是基于端云的部分卸载，但是本文提出的基于多重资源卸载策略的MRPSO算法平均适应度值比POPSO还要低40%～50%。

5.2.2 能耗和时间的比较

下面对4种基于不同任务卸载策略的粒子群算法所对应调度方案能耗与时间进行比较。4种卸载策略所对应的粒子群调度算法的平均能耗如图5所示。图中FOCPSO对应右侧次坐标轴，其余任务卸载策略对应左侧主坐标轴。4种卸载策略所对应的粒子群调度算法的平均完成时间如图6所示。其中LOPSO对应右侧次坐标轴，其余任务卸载策略对应左侧主坐标轴。

FOCPSO所对应的平均能耗最小，这是因为将DNNs所有层的计算任务全部卸载到云端，终端设备不存在执行能耗，只有很少的发送能耗。通过图6中的任务完成时间对比实验可以进一步看出，由于FOCPSO传输时间过多，其平均完成时间是MRPSO的2倍左右，无法满足时间约束，这也是适应度值没有MRPSO低的原因。而除了FOCPSO算法之外，本文所提出MRPSO平均能耗均小于其他算法。LOPSO所对应的平均完成时间最小，这是因为完全在终端设备执行不存在传输时间，仅存在计算时间，但是计算任务的不卸载会导致终端设备平均能耗最大，平均能耗值是MRPSO的5～7倍左右，因此其适应度值最高。

综上所述，与基于已有3种任务卸载策略所对应的粒子群调度算法相比，本文提出的基于多重资源任务卸载策略的粒子群调度算法MRPSO，适应度值最低。本文综合分析平均完成时间和平均能耗两个评价指标，进一步证明了MRPSO算法能够在考虑用户时间约束的前提下，充分降低终端设备能耗，取得最佳的综合性能。

6 结束语

本文针对现存移动智能应用在使用DNNs时无法满足用户时间约束下终端设备的能耗优化，在移动边缘计算环境中，首先基于DNNs结构特征建立了其计算任务卸载的时间和能耗评价模型，并在该模型基础上提出移动边缘环境中基于能耗优化的DNNs计算任务卸载策略。然后设计出能够在满足用户时间约束下优化终端设备能耗的适应度函数，最后提出了移动边缘计算环境中基于多重资源任务卸载的粒子群调度算法(MRPSO算法)，将DNNs各层的计算任务动态分配给相应的执行资源。实验表明，与已有的3种任务卸载策略所对应的调度算法相比，MRPSO算法所得适应度值最低，在用户时间约束下，终端设备的能耗最优。本文的工作还有进一步优化的空间，如本文中设备的计算速度和网络带宽都是固定值，而在实际过程中计算速度和网络带宽都会有波动，同时DNNs真实执行时间会受到多种因素影响。因此，未来计划将本文工作放入到真实的移动智能应用场景中，进一步观察其效果。