基于改进粒子群的边缘计算任务卸载策略

曹 靖 王朝亮 郑国权 孙 毅

1.华北电力大学电气与电子工程学院 北京 102206;2.国网浙江省电力有限公司营销服务中心 浙江杭州 310000;3.中国电力科学研究院 北京 100080

第五代移动通信系统(The Fifth Generation Mobile Communications System,5G)是新一代蜂窝移动通信技术,具有高带宽、低时延、大连接通信优势,已列为国家“新基建”重点部署的七大领域之一[1]。随着5G通信服务普及,大量互联网信息技术已成为研究热点,其中以边缘计算(Edge computing)技术[2]为代表的分布式数据计算技术在5G通信技术支持下得到大力发展。边缘计算技术通过将计算服务分布式从网络中心下沉至网络边缘,允许为网络用户提供应用程序、数据资料与服务运算,从而满足各类用户低时延业务的运算需求。

随着虚拟现实技术、自动驾驶等新型业务出现,网络终端侧数据呈现爆炸式增长,此类业务数据的响应时延需求进一步提高,同时大量业务数据计算依赖于相应算法框架,这给现有边缘计算服务系统带来巨大的通信和算力压力。边缘缓存技术[3]和设备直连通信(Device-to-Device,D2D)技术[4]的引入为实时高频数据计算提供了可靠解决方案。边缘缓存技术允许边缘侧设备缓存业务计算所需业务算法框架,从而减少边缘服务器的数据计算压力,同时设备直连通信技术可实现两个设备之间的通信链路的建立,使数据计算更多的在边缘设备处理,减少基站通信和计算压力,进一步提高业务响应能力。

本文在5G通信支持的边缘计算系统中引入服务缓存和设备间直连通信,允许终端设备缓存部分服务并为相邻设备提供任务卸载和计算,研究依赖服务缓存的业务数据边缘计算卸载决策的制定。首先设计考虑服务缓存和设备间直连任务卸载的系统模型,在此基础上设计基于改进粒子群的卸载决策算法,并通过仿真分析验证所提算法在边缘计算场景下的可行性和优越性。

1 系统模型

如图1所示,本文考虑由一个基站和N个终端设备组成的多接入边缘计算场景,设所有网络节点集合为N+={1,2,…,N,N+1},其中N={1,2,…,N}为终端设备集合,N+1表示基站。基站处配备了边缘计算服务器,拥有所有类型的服务缓存M={1,2,…,M},同时为覆盖范围内的终端提供通信信道分配及边缘计算服务;终端具有固定缓存列表,以支持对应业务类型的数据计算,各设备的服务缓存列表表示为bi=(bi,1,…,bi,M),其中bi,m=1表示设备i∈N具有业务m∈M的缓存文件。到达设备的计算任务可以通过设备间直连通信或与基站间5G通信将计算任务卸载至具有相应缓存的节点进行计算处理。

图1 系统模型

1.1 设备任务到达模型

假设计算任务到达设备遵循离散化时间尺度T={1,2,…,T},每个时隙间隔为τ,每个时隙t∈T开始时,所有设备将有多个计算任务到达,且任务受服务类型区分,到达设备的计算任务表示为{dm,Tm,ρ},其中,dm为计算任务数据大小,Tm为数据处理的时延要求,ρ为处理器每计算单位该类型的计算任务所需的CPU周期数。

1.2 任务卸载模型

(1)

(2)

(3)

1.3 任务队列模型

(4)

(5)

(6)

(7)

式中,κ为设备数据计算能耗系数。

在该系统所描述的边缘计算任务卸载过程中,计算任务从产生到完成处理最多经过卸载、排队和处理三个过程。由于计算任务的排队模型无法给出任务的具体等待时间,可采用平均排队时延[5]来表示:

(8)

1.4 问题建立

本文目标旨在考虑设备缓存的边缘计算系统中构建最优任务卸载算法,故将边缘计算系统中设备任务处理能耗与时延的加权平均和作为目标函数,定义目标函数为:

(9)

约束:

(10)

(11)

(12)

(13)

(14)

式中α和β分别为时延和能耗权重系数,本文设定其值均为0.5。约束(10)、(11)表示计算任务卸载有且仅有一个卸载目标,且该目标需要拥有相应服务缓存;约束(12)、(13)分别对设备的最大计算频率和最大传输功率进行约束;约束(14)为任务处理时延约束。对于该问题的求解由于受约束及排队时延限制,需要对任务卸载决策Y进行决策分析和制定。本文提出基于改进粒子群算法的服务缓存约束卸载决策方法对该问题进行求解。

2 基于改进粒子群的卸载决策算法

本文目标为系统所有设备的任务处理能耗与时延加权和最小优化问题,由于存在任务处理时延约束(14)和任务卸载变量Y,该问题属于NP-hard问题[6],无法直接求解。本文设计基于改进粒子群算法设计卸载决策求解方法,对于单一变量问题的求解具有计算简单、收敛性好的特点,具有较好性能。

(15)

(16)

其中,ω为惯性权重,c1和c2为学习因子,r1,r2∈[0,1]为0到1之间随机数。传统粒子群算法对于惯性权重和学习因子采用恒定赋值,其数值大小不会随着迭代进行而改变,这使得粒子群算法所求解出的计算结果容易陷入局部最优解,采用该方法无法得出系统最优卸载决策。本文所设计的改进粒子群算法分别通过对惯性权重系数及学习因子进行改进,其值在每次迭代中自我更新,在求解中能够以最少次数迭代得出全局最优解,且该解不落入局部最优。本文惯性权重和学习因子表示为:

(17)

(18)

(19)

其中,ω1和ω2分别为当前迭代过程开始与结束时的惯性权重,c11、c21、c12及c22分别为两个学习因子在当前迭代过程中开始与结束时的值,k为当前迭代次数,N为迭代总次数。

本文所设计的考虑服务缓存的改进粒子群算法具体步骤如图2所示。

图2 算法流程

3 仿真分析

本节基于Matlab R2017b仿真平台设计仿真算法对本文所提任务卸载问题求解,并与随机卸载算法和传统粒子群算法进行比较分析,从而验证本文算法优越性。部分仿真参数设置如下表所示。

仿真参数表

图3为本文所提算法的收敛性证明,由图可知本文算法能够在百次迭代内即接近收敛,具有较好的收敛性。

图3 算法收敛性验证

图4和图5分别对比了随机卸载算法、传统粒子群算法和本文算法受设备缓存服务数及计算任务数据规模变化的影响。其中随机卸载算法旨在对于设备所到达的计算任务,在满足其时延要求情况下随机选择一个具有相应缓存的设备进行卸载,而不考虑所选择卸载目标设备是否为当前系统中最优目标,因此该卸载方案在三种方案中,其平均时间能耗加权和最大,性能最差;传统粒子群算法在设备缓存数和计算任务规模较小时,其优化结果与本文算法相近,然而随着缓存数的增加,设备能为更多类型业务提供数据计算服务,但设备的计算能力并未改变,因此任务的排队时延增加,而传统粒子群算法在此时所得出优化结果不及本文算法,得出的结果为局部最优解;计算任务数据规模的增大导致设备对于单一任务的计算时延增加,也相应增加了队列中任务的等待时延,而本文算法相比于其他算法具有最优优化结果,进一步证明了本文算法的优越性。

图4 设备缓存服务数对目标的影响

图5 计算任务数据规模对目标的影响

结语

为推进5G通信与边缘计算技术的普及和发展,本文针对业务数据计算对于求解算法框架依赖的场景下此类数据边缘计算可行方案,提出了联合服务缓存和设备直连通信的边缘计算系统,对该系统中任务卸载和计算过程进行数学模型规定,在此基础上设计了基于改进粒子群的卸载决策算法,通过仿真分析验证了所提算法在边缘计算场景下的有效性。