移动边缘计算中的低能耗任务卸载决策算法

张文杰, 魏振春,2, 徐俊逸, 吕增威, 韩江洪,2

(1.合肥工业大学 计算机与信息学院,安徽 合肥 230601; 2.安全关键工业测控技术教育部工程研究中心,安徽 合肥 230601)

移动边缘计算(mobile-edge computing,MEC)中,智能移动设备(smart mobile devices, SMD)可选择将部分本地任务上传到云端处理,以降低SMD本身的能耗,提高任务处理的实时性。通过在靠近用户的区域内布置微蜂窝基站为SMD提供任务卸载服务,能够有效降低SMD的能耗和任务处理时间[1-2]

现有相关文献的研究目标主要是降低SMD能耗和减少卸载任务的处理时间。SMD能利用边缘微蜂窝基站提供的计算资源、存储资源,将本地的任务卸载到边缘微蜂窝基站上处理[3]。合理的微蜂窝基站通讯资源和计算资源的分配可以降低SMD的能耗或任务处理交付的时间,如文献[4]考虑如何分配信道的资源、文献[5]关注如何分配计算资源、文献[6-10]综合考虑多个因素降低能耗。SMD设备能耗的降低或任务处理时间的减短都需通过向微蜂窝基站卸载任务来实现,但是目前的研究主要集中在如何优化微蜂窝基站信道资源和计算资源的分配上,只有少量研究涉及了微蜂窝基站的能耗问题,如文献[11]讨论了每个微蜂窝基站能量有限的情况下,如何通过微蜂窝基站间相互的任务卸载来保证整个系统运行时间最长;但是这种方法只能延长整体微蜂窝基站节点的存活时间,考虑到微蜂窝基站间数据传输的能量消耗,微蜂窝基站群整体单位时间内的能耗水平实际上是提高的。

动态电压调整(dynamic voltage scaling,DVS)能够在实时任务处理过程中动态地调整电压频率以降低能耗,同时还能保证实时任务在规定时限前执行完毕[12]。在MEC中引入DVS技术,可以有效地降低整个MEC系统的能耗。少数文献已经将DVS技术引入MEC系统中,如文献[13]研究了利用DVS技术通过SMD向微蜂窝基站部分卸载任务,既能够在规定时限中完成任务的处理,又可以使SMD的能耗最低;文献[14-15]进一步讨论了在使用DVS技术的MEC系统中实现SMD的能耗最低、任务处理时间最短等问题。但是这些研究同样没有涉及SBS能耗的研究。

针对微蜂窝基站的能耗问题,本文提出一种实时任务卸载决策算法(task-offloading decision algorithm,TDA),控制微蜂窝基站协作处理任务;通过理论分析,根据任务的紧急度给出了各种情况下任务在各微蜂窝基站上的分配量,并通过实验进行了验证。

1 系统模型

本文主要考虑的问题场景是由M+1个微蜂窝基站组成的,记为{S0,S1,S2,…，SM},微蜂窝基站S1、S2、…、SM都在S0的无线通讯范围内，每个微蜂窝基站都有一定的数据存储容量和数据处理能力。微蜂窝基站由于通讯范围的限制,只能和无线通讯范围内的其他微蜂窝基站进行直接通讯。

本文的优化目标是通过微蜂窝基站间的任务协作,使得卸载在微蜂窝基站上的任务可以在规定时限之前被处理完,同时微蜂窝基站消耗的能量最少。

1.1 微蜂窝基站间任务卸载模型

假设在时刻O,任务λ从SMD完整地卸载到微蜂窝基站S0上,任务λ的数据量为D,任务λ被要求在时间点T(O

设从SMD卸载到SBS上的任务λ在时间点O完成数据传输,任务λ的数据量为D,要求任务λ在时间点T之前处理结束,u是判断任务紧急度的阈值。

(1) 松弛任务。若D/(T-O)≤u,则该任务为松弛任务。

(2) 紧急任务。若D/(T-O)>u,则该任务为紧急任务。

(1)

1.2 微蜂窝基站间数据传输的能耗和耗时

本文主要关注任务在微蜂窝基站间的分配和处理,为简化问题的分析,将微蜂窝基站的无线发射功率P和微蜂窝基站的数据传输速率r设为定值。微蜂窝基站S0与微蜂窝基站{S1,S2,…,SM}之间进行数据通讯时,采用频分多路复用技术传输多路信号,将带宽平均分配给各路信号;当所有微蜂窝基站确认任务分片接受完毕时,微蜂窝基站将任务分片加入微蜂窝基站的任务队列等待处理。微蜂窝基站S0从开始将任务分片{λ1,λ2,…,λM}卸载到微蜂窝基站{S1,S2,…,SM}再到所有任务分片卸载结束的用时满足:

(2)

1.3 任务处理的能量消耗和时间限制

ti=αDi/fi

(3)

(4)

因为任务分片λ0已经存在于微蜂窝基站S0上,不需要通过无线传输卸载到其他微蜂窝基站上,所以任务分片λ0的处理时长t0满足:

O+t0≤T

(5)

任务分片{λ1,λ2,…,λM}的处理时长{t1,t2,…,tM}满足:

O+Δ+ti≤T

(6)

微蜂窝基站CPU的最小和最大运行频率分别为fmin、fmax,因此任务分片λi的数据量Di和处理时间ti还应当满足:

fmin≤αDi/fi≤fmax

(7)

1.4 优化目标

对于任务λ,微蜂窝基站群SS通过协作处理,以最小能耗处理该任务,建立的微蜂窝基站群协作处理任务能耗最小问题模型为:

(8)

该模型满足约束条件(1)～(3)、(5)～(7)。约束(1)表示数据量的和应等于原始任务片λ的数据总量;约束(2)表示微蜂窝基站S卸载任务分片{λ1,λ2,…,λM}的数据传输用时;约束(5)、约束(6)要求每个任务分片λi都必须在任务的处理截止时间点前完成;约束(3)、约束(7)是对各微蜂窝基站处理任务分片时运算频率的要求。

2 问题分析

2.1 任务紧急度的阈值

从SMD卸载到微蜂窝基站上的任务,若被判断为紧急任务,则可通过微蜂窝基站协作任务处理方式降低处理任务的总能耗。

因为x→0,所以f0=f,fx=fmin。此时卸载任务可以为微蜂窝基站节约的能量为:

2.2 任务分片数据量分析

本节将证明当任务分片的数据量{D1,D2,…,DM}满足D1=D2=…=DM时,微蜂窝基站群SS协作处理任务λ消耗的能量最少。

(9)

(10)

证明完毕。

2.3 任务卸载数据量

(11)

满足约束条件：

fmin≤fx≤fmax。

(12)

(13)

(14)

解得:

(15)

基于上述讨论,TDA算法描述如下。

输入:任务λ的数据量D,任务处理时限T,微蜂窝基站S0可通讯微蜂窝基站数目M;

输出:任务分片的数据量Di(i∈{1,2,…,M});

1.根据微蜂窝基站任务量D和任务处理时限T判断是否需进行任务卸载;

2.if 0

3.Di=0

4.end if

7.采用(13)式求出Di

8.end if

10.采用(15)式求出Di

11.end if

3 仿真设计与分析

任务λ的数据量D满足10～20 MB,每单位任务数据处理的时间[13]t为0.125～0.600 s/MB。微蜂窝基站间通过无线通讯,传输数据消耗的能量为8 J/MB;微蜂窝基站的最小运算频率fmin=2×109c/s;微蜂窝基站所能达到的最大运算频率fmax=8×109c/s;相应的平均每单位数据所需运算的轮数a=1 000 c/B;微蜂窝基站运算能耗的相关系数[14]k=10-27。

D/T和微蜂窝基站数目对节能效果的影响如图1所示。从图1可以看出,微蜂窝基站上单位时间内要处理的任务量和可供进行任务卸载的微蜂窝基站的数目都会影响到任务卸载的节能率。该节能率表示与不采用本文卸载策略相比节约能量的比率。

由图1可知,当单位时间内要处理的任务量越大时,即不卸载任务时微蜂窝基站处理任务所需的运算频率越高,通过任务卸载带来的节能效果越好；单位时间内要处理的任务量达到5.5 MB/s时,任务卸载的节能效果有所降低,随着可卸载的空闲微蜂窝基站数目增加,任务卸载带来的节能效果开始提高,直到稳定。可见进行任务卸载的微蜂窝基站的数目不足时,微蜂窝基站的任务卸载节能效果并不能达到最佳。

图1 D/T和微蜂窝基站数目对节能效果的影响

紧急任务数量对微蜂窝基站群协作任务处理能耗的影响如图2所示。

图2 紧急任务数量对微蜂窝基站群协作任务处理能耗的影响

在一个10×10的蜂窝网络中采用任务卸载算法,横坐标表示紧急任务的数量,纵坐标表示基站的节能率。实际中紧急任务的出现往往是不规则的,因此实验中加入了紧急任务随机(random)出现在蜂窝网络中的任意微蜂窝基站上和将紧急任务固定(nonrandom)卸载到蜂窝网络选定的微蜂窝基站中2种情形，并进行了对比,其中选定的微蜂窝基站在蜂窝网络中的分布是均匀的。这2种情形最主要的差别在于均匀分布在蜂窝网络中的任务(nonrandom情形下)能够让更多的微蜂窝基站参与任务的处理。

由图2可知,当紧急任务数量较小时,节能的效果更好,但是当紧急任务的数量提高时,节能的效果开始下降。采用TDA算法的节能率可达到31%～36%。

单位任务处理时限会对微蜂窝基站群协作任务处理能耗产生影响,如图3所示。由图3可知,单位任务量处理时间的时限要求越大,任务在微蜂窝基站上处理的运算频率越低;当单位任务处理的时限为0.50 s/MB时,微蜂窝基站就需要采用协作处理的方法来降低能耗;单位任务处理的时限越小,采用微蜂窝基站间协作处理任务带来的节能效果就越好。

图3 单位任务处理时限对任务处理能耗的影响

4 结 论

本文研究了使用DVS技术的微蜂窝基站群任务协作处理问题,给出了微蜂窝基站群以最低能耗处理任务时各微蜂窝基站所需处理的任务量;提出了一种TDA算法,通过实验证明了使用DVS技术的微蜂窝基站群采用TDA带来的节能效果,也通过实验展示了各种因素对使用该策略的微蜂窝基站群节能效果的影响。