基于混合果蝇算法的计算卸载方法

杨子轩,张文柱,程 鹏,谢书翰

(西安建筑科技大学 信息与控制工程学院,西安 710055)

1 引 言

随着物联网技术、智能移动终端及其他相关技术的迅速发展,人们越来越青睐于将各种应用服务部署到智能手机、平板电脑、智能手表等移动设备上,并期待在移动终端上运行更多更复杂的应用服务[1].然而,移动设备有限的能源供应、硬件资源和计算能力往往难以支持图像处理、语音识别、增强现实等复杂的计算密集型应用服务,甚至造成设备能耗过大、服务时延过长等负面影响,严重制约了各类移动应用服务的进一步发展[2].

为了解决移动设备在执行复杂计算任务时的资源瓶颈,移动边缘计算引起了人们的关注[3-5].移动边缘计算(Mobile Edge Computing,MEC)是指将计算任务由移动设备发送到位于网络边缘的边缘计算服务器(下称MEC服务器),利用MEC服务器较为丰富的计算资源,提高任务的计算效率,同时减少移动设备的计算能耗[6].相较于传统的中心云计算,移动边缘计算能够更好地承担网络边缘侧移动设备产生的计算任务,可以有效解决网络拥塞等问题,显著改善网络服务质量[7].

计算卸载是移动边缘计算的关键步骤之一,是移动边缘计算中降低任务计算时延和移动设备计算能耗的重要手段.而计算卸载决策作为计算卸载顺利实施的基础和前提,是指根据任务计算量、计算时延要求等关键信息,结合系统中各个MEC服务器的计算资源情况,判断任务是否进行卸载以及卸载到哪里[8].

作为移动边缘计算的重要研究方向,近年来关于计算卸载决策方法的研究持续开展.文献[9]针对无人驾驶场景,将多MEC服务器环境中的多任务卸载决策问题转化为多维多选择的背包问题,提出了一种基于贪心算法的计算卸载决策方法.文献[10]提出了一种基于改进遗传算法的计算卸载决策方法,使用Grefenstette方法改善传统遗传算法中初始种群的多样性,加快了算法的收敛速度,提高了决策效率.文献[11]提出了一种单用户移动边缘计算环境中的计算卸载决策方法,使用改进的Q学习和深度学习算法搜索最佳卸载策略,实现移动设备计算时间和能耗的优化.为了应对复杂多变的网络环境,文献[12]将多边缘计算节点环境中的计算卸载决策问题建模为多臂赌博机问题,考虑节点可用计算资源数量和实时动态网络连接状态,提出了一种在线学习算法,将历史决策结果作为参考依据进行决策,最终实现了计算时延的最小化.文献[13]研究了医疗救灾场景下基于CAD和自组织车联网实现的边缘计算系统中移动医疗应用服务的计算卸载决策问题,并将其构建为非线性整数规划问题,提出了一种基于粒子群算法的计算卸载决策方法.文献[14]考虑了移动设备的移动性和MEC服务器的多样性,基于马尔可夫决策过程对计算卸载决策问题进行建模,并使用值迭代算法求解,对任务计算时延进行优化.文献[15]考虑了实时型应用在边缘计算过程中用户操作次数、传输数据量、应用活跃时间等多种不确定性因素,将计算卸载决策问题分解为两个子问题,分别将其转化为机会约束规划问题和三维背包问题进行求解.文献[16]研究了小型局域网边缘计算系统中的应用划分和信道资源分配问题,针对边缘计算需求较高的情况,将计算卸载决策问题构建为混合非线性整数规划问题,提出了一种启发式计算卸载决策方法,在保证应用服务完成时间公平性的同时有效减少了移动设备的能耗,并在一定程度上降低了算法复杂度.文献[17]针对多层边缘计算网络中的计算卸载决策问题,提出了一种基于博弈论的计算卸载决策方法,并应用近似算法加快决策算法的收敛速度.

移动边缘计算中的计算卸载决策已经被证明是一个NP-Hard问题[18],因此许多研究中都采用群智能优化算法进行求解.果蝇算法(Fruit Fly Optimization Algorithm,FOA)是一种启发于果蝇觅食行为的较为新颖的群体智能优化算法,相较于传统的遗传算法、粒子群算法等具有控制参数少、搜索速度快、收敛效果好的优点,已经成功应用于生产调度[19]、预测模型[20]、组合优化[21]等多种领域.而对于计算卸载决策问题,果蝇算法却鲜有应用.

此外,相较于传统中心云计算中云服务器丰富的计算资源,移动边缘计算中MEC服务器的计算资源相对有限,因此当边缘计算环境中存在较多任务需要进行计算卸载时,MEC服务器往往无法同时承担全部卸载的任务,从而势必会产生等待时间,影响任务最终计算时延.而现有研究中通常默认任务卸载到MEC服务器即可立即执行,忽略了MEC服务器的计算资源限制及其导致的任务等待时间的影响.

针对上述两点问题,面向多用户多MEC服务器移动边缘计算系统中的计算卸载决策问题,本文提出了一种基于混合果蝇算法的计算卸载决策方法.本文的主要工作如下:

1)构建了移动边缘计算系统中的计算时延模型和计算能耗模型,将任务计算时延、计算能耗、MEC服务器计算资源限制作为约束条件,设计系统效用函数对计算卸载策略进行评价,将计算卸载决策问题转化为有约束条件下系统效用的最优化问题;

2)在FOA算法的基本框架下,设计了一种基于混合果蝇算法的计算卸载决策方法,对FOA算法中种群初始化、嗅觉搜索等关键步骤进行改进,并加入模拟退火算法以进一步提高算法局部搜索能力,最终实现对计算卸载决策问题的求解;

3)设计实验对基于混合果蝇算法的计算卸载决策方法的优化效果进行验证,从计算时延、计算能耗、收敛性等方面与其他计算卸载决策方法进行对比,对提出方法的优缺点进行分析.

2 系统仿真及问题描述

本文研究的MEC系统的部署场景如图1所示.系统中包含多个移动设备和MEC服务器.计算任务由移动设备发起,可以选择两种计算方式,即本地计算和边缘计算.其中,本地计算指计算任务由移动设备本地执行;边缘计算则是将计算任务卸载到MEC服务器,由服务器执行后将计算结果返回到移动设备.根据任务计算方式和执行位置的不同,任务的计算时延和计算能耗会产生较大差异.为了实现系统中任务计算时延和计算能耗的最优化,需要通过计算卸载决策对计算卸载策略进行优化.

图1 MEC系统模型

3 问题建模

本节主要根据MEC系统中的计算卸载过程对问题进行抽象建模.首先设定如下假设和前提:

1)系统中每个移动设备只产生一个计算任务,定义移动设备编号与计算任务编号相同;

2)相比将计算任务上传到MEC服务器的数据量,服务器返回计算结果时传输的数据量很小,可以忽略;

3)边缘计算系统的主要目的是改善移动设备的计算时延和计算能耗,因此对于执行边缘计算的任务,本文忽略MEC服务器的计算能耗,只考虑移动设备的传输能耗.

表1列出了系统建模过程中使用的符号及其含义.其中下标i表示当前移动设备及其任务编号,j表示当前MEC服务器编号.

表1 符号及其含义

3.1 计算时延

3.1.1 本地计算时延

任务本地计算时延取决于任务的计算量和移动设备的计算能力,表示为:

(1)

3.1.2 边缘计算时延

假设计算任务i由MEC服务器j执行,根据任务计算过程可以将任务计算时延分为三部分:传输时延Ttrans,i、等待时延Twait,i和边缘计算时延TMEC,i,表示为:

Ti,j=Ttrans,i+Twait,i+TMEC,i

(2)

根据香农公式可知移动设备i到MEC服务器j的传输速率:

(3)

进而可以计算任务i的传输时延为:

(4)

任务在MEC服务器的计算时延则取决于MEC服务器的计算能力,表示为:

(5)

等待时延的产生主要是由于MEC服务器自身可用资源数量有限,当任务i到达MEC服务器j时,若服务器当前可用计算资源数量不能满足任务的正常计算需求(cpui>CPUj或memi>MEMj),则该任务不能立即执行,需要等待服务器完成执行中的任务并释放足够的计算资源后才可以进行计算.

假设图2为MEC服务器j上的任务执行过程,其中任务i到达时(Ttrans,i)服务器的可用计算资源数量不能满足任务需求.由图可知此时执行中任务的完成时刻集合为R={Ta,Tb},任务a最早完成.假设任务a占用的计算资源数量释放后服务器可用计算资源数量满足任务i的需求,则任务i开始执行的时刻即为任务a的完成时刻(Ta),进而可以求得任务i的等待时延Twait,i=Ta-Ttrans,i.因此任务i的等待时延可以表示为:

图2 MEC服务器j的任务执行过程

(6)

集合R通过比较任务i的到达时间和原有任务的完成时间进行判断.当原有任务的完成时间大于新任务的抵达时间时,表示原有任务此时未完成,仍然占用计算资源;反之,表示原有任务此时已完成,计算资源已经释放.假设任务i之前有g个任务已到达服务器j,各任务的完成时刻可表示为Tg,则集合R可以表示为:

(7)

3.2 计算能耗

根据文献[22],本地计算能耗为:

Ei,0=k·wi·flocal,i2

(8)

其中,k为能耗系数.

边缘计算能耗为:

Ei,j=Pi·Ttrans,i

(9)

为了保证任务计算卸载的合理性,对于执行边缘计算的任务,需要满足其边缘计算产生的计算时延和计算能耗均小于其本地计算产生的计算时延和计算能耗,即:

(10)

3.3 系统效用

(11)

(12)

为了评价当前计算卸载策略的优劣,本文定义系统效用函数Q为:

(13)

其中,TL、EL分别表示任务全部执行本地计算时的计算时延之和与计算能耗之和,β1、β2分别表示系统效用中计算时延和计算能耗所占的比重.

3.4 最优化问题制定

由式(13)可知,当T、E值越小,Q值越大.因此为了实现系统效用的最大化,可以将计算卸载决策问题转换为有约束条件下Q的最优化问题,即:

P:maxQ

s.t.

C1:Ti,j

C2:cpu′j

其中,cpu′、mem′分别表示MEC服务器j上执行中任务所占用的CPU和内存资源数量.

4 基于混合果蝇算法的计算卸载决策方法

FOA算法的基本原理是在初始种群的中心位置周围利用嗅觉搜索产生多个邻域解,计算各个解的适应度值,将其作为味道浓度,再通过视觉搜索选择其中浓度最高的解作为新的中心位置,经不断迭代,逐渐向食物源靠近.在该框架下,根据所求问题的特点,本文设计了基于混合果蝇算法的计算卸载决策方法HFOA.

HFOA首先采用启发式方法和随机方法产生多个计算卸载策略,将其作为算法初始种群,计算各策略产生的系统效用,选择其中系统效用最优的策略作为初始中心位置;然后采用基于概率选择的自适应方法通过3种方式产生新的计算卸载策略(嗅觉搜索),选择其中系统效用最优的计算卸载策略作为新的中心位置(视觉搜索);最后使用模拟退火算法对当前最优计算卸载策略进行进一步的局部搜索.通过迭代搜索,最终输出系统效用最优的最佳计算卸载策略.

4.1 编码和解码方式

算法中果蝇个体采用整数编码,每个果蝇个体即表示一个计算卸载策略.假设问题中含有n个计算任务和m个MEC服务器,计算卸载策略S可以表示为:

S={s1,s2,s3,…,sn},s∈[0,m]

(14)

此即为问题的一个解.假设问题中含有6个计算任务和3个MEC服务器,有计算卸载策略S={0,3,3,0,1,2},则表示任务1在移动设备本地执行,任务2卸载到编号为3的MEC服务器执行.

4.2 种群初始化

由于通过随机方法产生的计算卸载策略随机性较大,难以对解空间进行高效的覆盖,且难以保证个体质量.因此本文采用启发式方法和随机方法相结合的种群初始化方法,即组成初始种群的一个计算卸载策略通过启发式方法获得,其他计算卸载策略通过随机方法生成.启发式方法步骤如下:

Step 1.将计算能力最优的MEC服务器作为首选卸载目标,所有任务按其传输时间由短到长排列,依次进行卸载;

Step 2.当该服务器不能立即执行下一个卸载的任务时,则将后续任务卸载到计算能力次优的MEC服务器,重复该步骤直到全部MEC服务器均不能立即执行卸载的任务;

Step 3.将其他未卸载任务卸载到所需等待时间最短的MEC服务器.

通过启发式方法生成的计算卸载策略可以保证部分任务的计算时间和等待时间最短,相较于随机方法更容易产生系统效用较好的计算卸载策略.同时与随机方法相结合,也在一定程度上保证了初始种群的多样性.

4.3 基于概率选择的自适应嗅觉搜索和视觉搜索

嗅觉搜索的主要目的是在当前最优计算卸载策略的基础上产生新的计算卸载策略,即邻域解.为了保证算法的全局搜索能力,根据文献[23]提出的基于概率选择的多邻域协同搜索方式进行嗅觉搜索.首先定义3种邻域解生成方式如下:

1)整体交换:在计算卸载策略中随机选择一个位置点,将该点及其后任务的执行位置与之前任务的执行位置进行交换;

2)多点变异:在计算卸载策略中随机选取SN1(SN1≤n)个任务,将该任务的执行位置随机替换成其他任意位置;

3)多点交换:在计算卸载策略中随机选取SN2(SN2

定义3种邻域解生成方式的初始选择概率均为1/3,第g代时的概率分别为p1、p2、p3,第g-1代中通过3种方式产生的邻域解个数分别为C1、C2、C3,则通过以下方式对概率p1、p2、p3进行计算:

(15)

(16)

p3=1-p1-p2

(17)

对于嗅觉搜索后产生的新解,分别计算其对应计算卸载策略产生的系统效用,选择其中的最优解进行下一步的操作.

4.4 基于模拟退火的局部搜索

为了提高算法的局部搜索能力,对于视觉搜索后产生的计算卸载策略,采用模拟退火方法进行进一步的优化.具体操作为:

Step 1.计算当前最优计算卸载策略产生的系统效用作为适应度fit;

Step 2.将当前最优计算卸载策略中等待时间最长的任务卸载到任务等待时间之和最小的MEC服务器,计算此时产生的系统效用,作为新解适应度fit′;

Step 3.根据Metropolis准则[24]判断是否接受Step 2中产生的计算卸载策略;

Step 4.重复Step 2、Step 3直至达到当前温度下的内循环次数.

4.5 算法流程

HFOA方法流程图如图3所示.

图3 HFOA方法流程图

5 实验与分析

为了验证HFOA方法的可行性及性能表现,本节选取本地计算方法(LA)、随机计算卸载方法(RA)、基于遗传退火算法的计算卸载方法[25](GSA)以及基于粒子群算法的计算卸载方法[26](PSO),从计算时延、计算能耗、系统效用及算法收敛性等方面进行对比.其中,LA方法中任务全部在移动设备本地进行计算;RA方法随机判断任务是否卸载及卸载位置;GSA方法、PSO方法则分别使用GSA算法和PSO算法对前文提出的计算卸载决策问题进行求解,最终输出各自最佳计算卸载策略.

所有实验均使用Pyhthon3编程实现,基本实验流程如图4所示.实验环境为Windows 10 64位操作系统,Intel Core i7 7700HQ CPU,16GB内存.

图4 实验流程图

5.1 实验参数设置

实验采用随机方法在给定范围内生成任务和MEC服务器的各项属性参数.相关参数取值参考文献[26]进行设定,如表2所示.为了消除随机因素对实验结果的影响,本文每组实验均进行30次,仿真结果取平均值.

表2 实验参数设定

5.2 实验设计与结果分析

5.2.1 各方法决策效果对比

为了比较不同任务数量下各决策方法产生的计算时延、计算能耗和系统效用,该组实验设置MEC服务器数量10,β1=β2=0.5,分别测试任务数量为50、100、150、200、300时各方法产生的计算时延、计算能耗和系统效用.实验结果如图5所示.分析可知,不同任务数量下,HFOA方法和GSA方法产生的计算时延均优于其他方法:任务数量为50时,HFOA方法和GSA方法相较于PSO方法、RA方法、LA方法分别降低了8%、 23%、48%的计算时延.对于计算能耗,HFOA方法、GSA方法、PSO方法优化结果相同,任务数量为50时,相较于RA方法和LA方法分别降低了25%、83%.系统效用的实验结果与计算时延的实验结果基本一致,任务数量为50时,HFOA方法和GSA方法相较于PSO方法、RA方法分别提高了5%、 21%的系统效用.

图5 各方法决策效果对比

5.2.2β取值对系统优化效果的影响

为了验证β1、β2取值对系统优化效果的影响,该组实验设置3对β1、β2取值,使用HFOA方法进行计算卸载决策,比较3种取值方案下产生的计算时延、计算能耗及系统效用.实验结果如图6所示.由实验结果可知,β1=1、β2=0时系统计算时延最低,但系统计算能耗最高;β1=0、β2=1时系统计算能耗最低,但系统计算时延最高;β1=0.5、β2=0.5时,系统计算时延和计算能耗均接近最低.由于β1=0.5、β2=0.5时产生的计算时延和计算能耗相较于β1=1、β2=0、β1=0、β2=1时获得的最低计算时延和最低计算能耗相差不大,实际应用时为了平衡系统计算时延和计算能耗的收益,β1、β2应分别取0.5、0.5.

图6 β取值对系统优化效果的影响

5.2.3 各方法收敛性对比

为了比较HFOA、GSA、PSO 3种决策方法的收敛性能,该组实验设置任务数量为50,MEC服务器数量为10,β1=β2=0.5,分别测试3种方法下系统计算时延、计算能耗、系统效用的收敛情况.实验结果如图7所示.整体来看,PSO方法的收敛速度最快,但收敛值最差;GSA方法的收敛速度最慢,但收敛值较优;HFOA方法的初始值最优,收敛速度介于PSO方法和GSA方法之间,收敛值与GSA方法接近.分析可知,HFOA方法通过对种群初始化的改进,提高了初始种群的质量,有效提高了初始值;通过加入基于模拟退火的局部搜索,在迭代初期提高算法的局部搜索能力,加快了算法的收敛速度;而通过基于概率选择的自适应嗅觉搜索和FOA算法的优势,也保证了HFOA方法的全局搜索能力.

6 结束语

本文针对多用户多MEC服务器移动边缘计算系统中的计算卸载决策问题,考虑MEC服务器有限的计算资源及其导致的等待时间的问题,设计了一种基于混合果蝇算法的计算卸载决策方法HFOA.该方法在传统果蝇算法的框架下使用启发式方法和随机方法进行混合种群初始化,并分别使用基于概率选择的自适应嗅觉搜索和基于模拟退火的局部搜索改进算法的全局搜索能力和局部搜索能力,最终实现对计算卸载决策问题的求解.通过仿真实验,验证了HFOA方法在解决计算卸载问题方面的可行性,能够有效降低系统计算时延、计算能耗,提高系统效用.相较于其他计算卸载方法,HFOA方法在计算时延、计算能耗和系统效用方面均有改善,同时保证了算法的收敛速度.此外,通过对比不同β取值下的系统优化效果,证明了当β1=β2=0.5时系统收益最佳.