移动边缘计算中资源受限的串行任务卸载策略*

刘 伟 , 黄宇成 , 杜 薇 , 王 伟

1(武汉理工大学 计算机科学与技术学院,湖北 武汉 430070)2(交通物联网技术湖北省重点实验室,湖北 武汉 430070)3(同济大学 计算机科学与技术系,上海 200092)

据思科视觉网络指数预测,到2021 年,全球移动数据流量每月将达到49 艾字节(EB),这对移动终端的性能和移动网络的数据传输率提出了新的要求[1].此外,一类新的应用程序也应运而生,诸如人脸识别[2]、移动增强现实[3]等,这类应用对延迟比较敏感,且需要大量的资源.然而,移动终端的计算和存储资源有限,尤其是电池的续航周期较短,运行这类应用程序会带来较高的延迟,增加移动终端的能耗.而移动云计算(mobile cloud computing,简称MCC)[4]的出现,为解决这些问题提供了一种有效方式,通过任务卸载(也称计算卸载或计算迁移)[5,6]将应用程序的部分计算任务卸载到远程云端,减少了应用程序的完成时间,提高了移动终端的续航能力.

然而在传统移动云计算中,移动终端通过互联网与远程公有云连接,如阿里云、腾讯云等,由于集中式部署的远程公有云距离移动终端较远,在两者之间通过互联网进行数据传输往往会带来比较高的网络延迟[7],这对于延迟敏感型的移动应用程序无法容忍.为了解决MCC 存在的高延迟问题,诞生了一种新的计算模式——移动边缘计算(mobile edge computing,简称MEC)[8],在靠近移动终端的网络边缘部署边缘服务器,将远程云端提供的IT 服务和计算能力延伸到距离移动终端更近的位置,移动终端便能够利用边缘服务器强大的资源,并以较低的网络延迟与边缘服务器进行数据传输.当终端提交卸载请求时,可以直接在边缘服务器上处理而不需要发送给远程云端,节省了应用完成时间和终端能耗.MEC 既有强大的计算和存储能力,又有靠近用户的高带宽、低时延的优势,能够显著地提高用户的实时体验和满意度.国内相关学者在边缘计算体系结构等领域取得了一定的研究成果[9].但是,边缘计算在移动性管理、虚拟化技术和计算卸载等领域还存在一定的技术挑战[10].

学者们针对边缘服务器环境中的任务卸载问题,从不同的角度开展研究工作[11-24].然而,这些工作大多针对单个移动终端或边缘服务器资源无限的场景.与传统的云计算相比,边缘服务器提供的计算、网络及存储资源是有限的.此外,当有大量用户同时向边缘服务器提交卸载请求时,用户之间会对边缘服务器的资源产生竞争,导致资源的不足而带来应用性能的衰减.因此,考虑多用户同时向资源受限的边缘服务器提交卸载请求的场景是非常有必要的.但是,与已存在的工作相比,这将导致计算卸载情况更加复杂.

本文针对边缘服务器资源受限场景下的任务卸载和资源分配问题展开研究,提出了一种面向多用户的串行任务动态卸载策略(MSTDOS).此策略考虑了多用户同时请求的竞争关系和任务卸载决策与服务器资源分配之间的相互影响,以应用的平均完成时间和移动终端的平均能量消耗作为评价指标,采用化学反应优化算法求解.该策略遵循先来先服务原则,合理分配边缘服务器的资源,减少任务在服务器上的等待时间,从而使用户得到一个更好的卸载结果,提高用户体验和应用性能.

本文的主要贡献如下.

1)解决了边缘服务器资源受限时的多终端串行任务卸载问题.本文建立了串行任务模型、应用完成时间模型和终端能耗模型,旨在降低应用平均完成时间和终端平均能耗;同时,采用线性加权的方法将多目标优化问题归一为单目标优化问题,并证明该问题属于NP-hard;

2)提出了一种面向多用户的串行任务动态卸载策略MSTDOS.该策略基于化学反应优化算法,在满足组件间依赖关系的前提下,充分考虑多用户的竞争关系和任务卸载决策与资源分配的相互影响,提高了应用性能和用户体验;

3)验证了MSTDOS 策略的有效性.本文选取现实生活中的人脸识别应用作为评估对象,仿真实验表明:在边缘服务器资源受限的多终端任务卸载场景下,MSTDOS 策略比存在的方法在应用性能提升上有明显优势.

本文第1 节介绍国内外的研究现状.第2 节描述任务卸载的场景及相关概念.第3 节阐述具体的系统模型和问题定义.第4 节重点介绍本文提出的卸载策略.第5 节分析实验环境和评估结果.最后,对本文工作进行总结和展望.

1 相关工作

近年来,任务卸载[11-24]问题在学术界引起了广泛的关注.为了扩展移动终端的计算能力,延长终端的续航周期,相关研究者们提出了多种任务卸载框架,如MAUI[11],ThinkAir[12],CloneCloud[13]等,关于计算迁移的研究方法和策略也开展了相关工作.浙江大学的邓水光等人[14]考虑到移动云环境中用户的移动性,提出了一种包含容错机制的卸载系统,保障了应用的稳定执行,并采用遗传算法为应用做出卸载决策.北京大学的黄罡团队[15]针对Web 应用中由复杂脚本导致任务计算量过大的问题,将Web 应用动态变化的特征和计算卸载相结合,提出了一种应用运行时的卸载策略从而得到Web 应用的卸载结果.南洋理工大学的张维文等人[16]研究了移动云环境中基于随机无线信道的任务卸载问题,分别采用穷举法和one-climb 策略为应用做出卸载决策,确定在截止时间约束下能耗最优的选择结果.文献[17]针对由多用户资源竞争而导致的高能耗问题,提出了一种任务联合执行策略,将联合执行应用的优化问题建模为最小化终端能耗问题,并采用遗传算法来处理该优化问题.武汉大学的傅建明团队[18]对CM-MCC 和CA-MCC 两类弹性移动云计算方式展开了研究,分析了其实现流程及存在的问题;同时,针对弹性移动云计算的安全问题展开分析,并研究相应防御方法.北京邮电大学的王尚广团队[19]针对已有服务选择工作没有考虑到移动终端的状态和历史特征信息的问题,提出了一种状态感知和稳定性感知的选择方法,分别对任务在移动终端和云端运行两种情况建模,并设计了一种选择算法决定最优的服务.

由于集中式部署的远程公有云距离移动终端较远,他们之间的数据传输将带来较高的网络延迟.借助于移动边缘计算,将计算和存储服务部署在移动网络的边缘,能有效弥补传统云计算的不足.韦恩州立大学的施巍松等人[8]针对集中式数据处理方式无法满足大量数据的实时处理需求问题,提出了面向边缘设备的边缘计算模型,将其与现有的云计算模式相结合,提升了数据处理的效率.香港科技大学的张军等人[20]针对移动边缘计算中终端电量不足的问题,提出了基于李雅普诺夫优化的动态任务卸载策略,综合考虑应用的卸载策略、移动终端执行的时钟频率和云端执行的传输功耗,为应用做出最优的卸载决策.西安电子科技大学的汪彦婷等人[21]针对移动边缘计算中的部分任务卸载问题,分别从单个边缘服务器场景和多个边缘服务器场景来考虑任务的卸载问题,并采用动态电压频率调节技术来优化移动终端能耗,提出的卸载算法降低了应用延迟和终端能耗.

然而,上面的研究工作都是考虑单个移动终端或边缘服务器资源无限的场景,这在实际应用中存在一定的局限性.香港理工大学的曹建农等人[22]针对云端资源受限的多终端任务卸载问题,提出了一种卸载策略SearchAdjust.该策略先假设云端资源无限然后再作调整,有效提高了应用性能和用户体验.西南大学的郭松涛等人[23]针对时间约束下的移动终端能耗最优问题,提出了一种节能的动态卸载和资源调度策略eDors.该策略由任务卸载、CPU 时钟频率控制和传输功率分配这3 个子算法组成,有效降低了终端能耗.关于多信道干扰的多终端任务卸载策略的问题,中山大学的陈旭等人[24]采用博弈论的方法为所有应用做出近似最优的卸载决策,从而在满足应用完成时间约束时,达到移动终端的能耗最优.

本文针对边缘服务器资源受限条件下多终端的串行任务卸载问题,考虑多个用户请求之间的相互影响,研究如何高效分配边缘服务器的资源,为所有应用做出近似最优的卸载决策,使得所有应用的平均完成时间和移动终端的平均能耗达到近似最优.

2 任务卸载场景及介绍

图1 呈现了多终端任务卸载的场景,该场景主要包括3 个部分:移动终端、移动网络和边缘服务器.本文的研究工作主要集中在移动终端和边缘服务器端.多终端的任务卸载过程如下:对于移动终端,产生并运行移动应用程序,通过移动网络向边缘服务器提交卸载请求;对于边缘服务器端,接收来自移动端的任务卸载请求,分配合适的资源处理应用请求,处理完成后通过移动网络将最终的结果返回到移动终端.

接下来主要介绍在任务卸载过程中涉及到的相关概念的定义.

(1) 移动应用程序

移动应用程序是移动终端运行的任务,此类任务一般分为独立任务和依赖任务两种:独立任务表示应用程序的结构是不可分割的,只由单个任务构成,如N皇后问题、矩阵运算问题等;依赖任务表示应用程序可自动划分为多个具有相互依赖关系的子任务,子任务之间存在数据交互,如人脸识别应用、QR 二维码应用等.本文以依赖任务中的串行移动应用程序为研究对象.假设一个任务可划分为n个子任务,即Task={1,2,…,n}.第k个子任务能够开始执行,除了要分配有足够的计算、存储和网络资源外,还需其前驱组件k-1 已执行完成.串行任务模型已被许多研究者所采用[2,17,22].具体介绍见第3.1 节.

(2) 移动终端

移动终端是产生应用程序的环境,本文假设每个移动终端都只运行一个相同的应用程序.用N表示提交卸载请求的移动终端数量,可以表示为MDs={md1,md2,…,mdN},而每个移动终端可以表示成一个八元组:

其中,i表示移动终端的编号,i∈[1,N];表示移动终端的计算能力(每秒执行的指令数,单位为MIPS);poweri表示移动终端i当前的可用电量;分别表示移动终端的CPU 在工作状态和空闲状态下的功率;Pi,send,Pi,recv和分别表示移动终端的网络接口在发送数据、接收数据和空闲状态下的功率.

(3) 边缘服务器

边缘服务器部署在靠近移动终端的网络边缘,为任务卸载提供计算、网络和存储等服务.本文只考虑部署在单个固定地理位置的边缘服务器.选取M个配置相同的虚拟机表示边缘服务器资源的集合,即VMs={VM1,VM2,…,VMM},每个虚拟机可以表示为一个四元组:VMi={i,capacityi,Bi,waiti},其中,i表示虚拟机的编号,i∈[1,M];capacityi为虚拟机i的计算能力,表示每秒执行的指令数;Bi表示当前时刻移动终端与边缘服务器通信的网络带宽;waiti表示组件卸载到虚拟机i上需要等待的时间.假设所有虚拟机的处理能力和传输能力均一致,并不会随着任务量的上升而改变.

(4) 移动网络

移动网络表示移动终端和边缘服务器之间数据的通信方式,为组件的卸载提供了可能.移动终端可以通过蜂窝网络(如4G,5G[25])或者无线接入点(Wi-Fi)方式,将应用程序的部分组件卸载到边缘服务器执行.

(5) 卸载策略

卸载策略表示应用程序的卸载结果,对于每个终端运行的应用程序,其卸载策略可以表示为一个n维向量:Si={xi,1,xi,2,…,xi,n},其中,n为应用i包含的组件个数.向量中的每个值xi,j代表应用i的组件j是在本地执行还是边缘服务器执行,其取值为0 或1:xi,j=0 表示应用i的组件j在本地执行,xi,j=1 表示组件卸载到边缘服务器执行.

Fig.1 An illustration of task offloading with multiple mobile terminals图1 多终端任务卸载场景

3 系统模型及问题定义

3.1 任务模型

本文的研究对象是由若干个串行组件组成的移动应用程序.如图2 所示,该应用由n个组件构成,其中,组件0 和组件n+1 为虚拟组件,表示数据输入和结果输出的组件,且固定在本地执行.本文采用线性链表L={V,E}来表示组件之间的依赖关系,每个节点i∈V示移动应用程序的一个组件,每条有向边e(i,j)∈E表示组件i和组件j之间的依赖关系.可以看出,组件j只有等待其前驱组件i执行完成后才能开始执行.

Fig.2 An illustration of serial task model for mobile applications图2 移动应用的串行任务模型

串行应用程序在实际生活中存在着广泛的应用,如人脸识别应用[2]、视频字符识别和国际象棋等.人脸识别应用包括图片输入、人脸检测、图像预处理、脸部特征提取、人脸匹配和结果输出等6 个顺序执行组件,前一个组件计算的输出结果作为后一个组件的输入数据,当所有组件执行完成并输出最终结果,表示应用执行完毕.视频字符识别应用包括视频输入、关键帧提取、文本区域定位、字符识别、OCR 识别和文本输出等6 个组件.人机对战中的中国象棋或国际象棋,机器每走一步,其后台的计算都可以划分为几个串行的任务:首先计算每颗棋子能够移动的位置,然后计算每个棋子的最优移动位置,最后计算最优的移动棋子[17].

3.2 完成时间模型

完成时间[26]是评价应用性能的一个重要指标,表示应用程序从数据输入到结果输出整个过程所需的时间.接下来,分别从应用组件在本地执行和边缘服务器执行来讨论组件的执行时间.

3.2.1 本地执行

本地执行表示组件(i,j)在移动终端上执行,STi,j,FTi,j分别表示组件(i,j)的开始执行时间和结束时间,RTi记录移动终端i可以开始执行任务的时间.由于组件(i,j)必须等待其前驱组件(i,j-1)执行完成后才能开始执行,则组件(i,j)在本地的开始执行时间表示为

其中,pred(i,j)表示组件(i,j)的前驱组件的集合;Ti,j-1,j表示组件(i,j-1)和(i,j)之间的数据传输时间,计算公式如下:

其中,datai,j-1,j表示组件(i,j-1)和组件(i,j)之间数据传输的大小.

3.2.2 边缘服务器执行

边缘服务器执行表示组件通过移动网络卸载到边缘服务器上执行.对于组件(i,j),如果前驱组件没有在边缘服务器上执行,由于应用之间对边缘服务器资源的竞争使用,则需要考虑等待时间;反之,则不需要考虑等待时间.因此,组件(i,j)在边缘服务器上的开始执行时间可以表示为

其中,waiti,v表示应用i在虚拟机v中的等待时间,其等待时间的长短主要取决于虚拟机v中排队在应用i之前的应用的服务时间之和.这里用servicek,v表示应用k在虚拟机v上的服务时间,每个应用维护一个链表Listk,表示应用k卸载到边缘服务器上的组件的集合.则应用i的等待时间可以通过如下公式得到:

其中,FTi,exit表示应用程序出口组件的结束时间,STi,entry表示应用程序入口组件的开始执行时间.

3.3 能耗模型

移动终端包括屏幕、CPU、蓝牙、GPS、ROM、RAM、网络接口等[27]多个部件,本文主要考虑移动终端CPU 和网络接口产生的能耗.

3.3.1 计算能耗

移动终端的CPU 主要包括运行和空闲两种状态.如果CPU 有任务执行,就会一直处于运行状态,没有任务处理时,CPU 则会进入空闲状态.CPU 处于运行状态的能耗计算如下:

3.3.2 传输能耗

传输能耗主要是移动终端和边缘服务器之间进行数据传输产生的,包括数据发送能耗、数据接收能耗和网络接口空闲能耗.对于一个应用而言,当存在两个满足前驱后继关系的相邻组件都在移动端或边缘服务器上执行时,传输能耗为零;只有当两个组件在不同的位置执行时,才存在传输能耗.移动终端发送数据到边缘服务器产生数据发送能耗,接收边缘服务器返回的数据产生数据接收能耗.则对应的能耗分别表示为

3.4 问题定义

在第3.2 节和第3.3 节中分别建立了单个应用的完成时间模型和单个移动终端的能耗模型,MskeSpani表示应用i的完成时间,Ei表示移动终端i产生的能耗.上述时间和能耗模型都受卸载决策S的影响,不能通过独立计算同时达到最小值,其中,S={S1,S2,…,SN}.本文针对边缘服务器资源受限条件下多终端的串行任务卸载问题,旨在提高串行应用性能的同时降低移动终端能耗,采用线性加权的方法来规划联合目标函数.因此,原问题可以定义为

上述λt和λe分别代表应用完成时间和终端能耗所占的权重,有λt,λe∈(0,1),且满足λt+λe=1.其中:限制条件(a)保证了组件(i,j)只有等待其前驱组件(i,j-1)执行完成才能开始执行;限制条件(b)表示边缘服务器中每个虚拟机在同一时间只能处理一个任务,即应用k和应用i都有任务在虚拟机v上执行,应用k表示应用i后面的应用,则应用k的任务只有等待应用i的任务执行完成后才能开始执行;限制条件(c)表示所有任务所分配的带宽量应满足边缘服务器提供的网络带宽的约束;限制条件(d)表示应用组件的执行位置只能是0 或1.根据应用系统模型,应用的输入数据由移动终端产生,输出结果将返回到移动终端,限制条件(e)表明应用的入口组件和出口组件只能在本地执行.

命题1.F1 问题属于NP-hard.

证明:考虑F1 问题的一种特殊情况,参数λt=1,λe=0,并忽略组件之间传输时间.此时,应用i的任务完成时间仅由所有组件的执行时间构成.计算如下:

满足上述约束条件(a)～约束条件(e).

可以看出:该特殊情况为组件在本地执行或边缘服务器执行的完成时间最小化问题,等价于0-1 背包问题.我们知道,0-1 背包问题属于NP-hard 问题[28].因此,F1 问题的特殊情况也是NP-hard 问题,故F1 问题也属于NP-hard[29].

4 算法描述

本文研究的任务卸载问题是典型的多目标组合优化问题[30],属于NP-hard 问题,可以采用启发式算法求解该类问题.目前存在多种启发式算法,如遗传算法(GA)[31]、粒子群算法(PSO)[32]、蚁群算法(ACO)[33]和化学反应优化算法(CRO)[34]等.相比于遗传算法,化学反应优化算法能避免过早地陷入局部最优,获取全局近似最优解,同时以更快的速度收敛于最优解[35].化学反应优化算法[34]最早是在2010 年由Lam 和Li 提出来的,灵感来源于大自然中的化学反应.根据实际应用表明:化学反应算法能够有效地解决多目标优化问题,并且在二次分配问题、网格任务调度问题、人工神经网络训练、资源受限项目调度问题等方面得到广泛的应用.针对边缘服务器资源受限的多终端任务卸载问题,本文采用化学反应优化算法求解.

4.1 算法框架

化学反应优化算法中,分子具有3 个必要属性:分子结构(structure,简称S)、分子势能(potential energy,简称PE)和分子动能(kinetic energy,简称KE).分子结构S表示任务卸载策略的一个解空间;分子势能PE表示分子结构的稳定性,定义为目标函数的值;分子动能KE使得分子势能趋向更高的状态,避免目标函数值过早地陷入局部最优解而继续寻找全局最优解.第4.2 节～第4.4 节主要从问题编码、适应度函数和操作算子设计这3 个角度介绍化学反应优化算法.问题编码定义了卸载策略与分子结构之间的关系;适应度函数是评估分子好坏的标准,分子的适应度值越小,代表所求问题的解越优,因此,设计一种好的适应度函数有利于获得最优解;操作算子是算法搜索解空间的关键步骤,不同的操作算子能够改变分子结构,避免算法过早陷入局部最有解,同时搜索全局最优解.第4.5 节介绍具体的算法设计,第4.6 节和第4.7 节分别对算法的复杂度和收敛性进行分析.

4.2 问题编码

化学反应优化算法是一种通过模拟化学反应过程搜索最优解的方法,问题解空间用分子集合表示,分子是由若干个原子编码组成.本文研究的移动应用程序是由串行执行的组件构成,每个组件执行位置分为移动终端执行和边缘服务器执行,分别用0 和1 表示.移动应用程序的卸载决策表示为分子,组件的执行位置用原子表示.

图3 是移动应用程序及其对应的分子结构,该应用程序包含5 个组件,分子结构表示应用程序的卸载策略,分子中每个原子的值代表组件的卸载位置.图中是一种可能的分子结构S={1,1,0,1,0},表示组件3、组件5 在移动终端上执行,组件1、组件2、组件4 卸载到边缘服务器执行.

4.3 适应度函数

本文评价卸载策略性能的指标是平衡所有应用的平均完成时间和移动终端的平均能耗.对于一种卸载策略S,对应的应用完成时间用T表示,移动终端能耗用E表示,将两个不同量纲的目标进行归一化处理,并采用线性加权方式将双目标转化为单目标,则适应度函数[36]可以表示为如下形式:

其中,Tmax和Tmin分别代表分子种群中所有分子对应的应用完成时间的最大值和最小值,Emax和Emin分别代表分子种群中所有分子对应的移动终端能耗的最大值和最小值.α和β分别代表应用完成时间和移动终端能耗的比例所占权重,其取值主要由移动终端的可用电量来决定,α,β∈(0,1),且满足α+β=1.当移动终端电量充足时,完成时间为主要优化目标,参数设置条件为α>β;当电量不足时,主要优化移动终端能耗,设置α<β.然而,在实际场景中,完成时间和能耗的权重的合理分配可根据多属性决策理论[24,34]来确定.

4.4 操作算子设计

本节介绍化学反应优化算法的4 种基本操作算子,包括单分子碰撞、单分子分解、分子间碰撞和分子合成.问题编码中介绍过每个分子结构表示一种卸载策略,不同的操作算子对分子结构会产生变化,应用程序的卸载策略也会随之改变.单分子碰撞和分子间碰撞对原分子结构改变较小,旨在原卸载策略的邻域空间搜索更优的卸载策略;单分子分解和分子合成提供搜索更大解空间的机会,避免卸载策略过早地陷入局部最优解.下面详细介绍4 种基本操作算子的具体设计.

4.4.1 单分子碰撞

单分子碰撞是指单个分子与容器壁发生碰撞并反弹的过程.对于分子S,发生单分子碰撞后产生新的分子S′,新分子S′与原分子S在分子结构上相差不大,表示碰撞过程是在分子S的邻域空间搜索最优解.

具体设计如图4 所示:从原分子S中随机选择一个原子,改变其执行位置,剩余部分保留不变.对应到卸载策略中,原先的卸载策略经过单分子碰撞后,随机改变应用某个组件的执行位置,产生新的卸载策略.

Fig.4 On-wall ineffective collision图4 单分子碰撞

4.4.2 单分子分解

单分子分解是指单个分子与容器壁发生碰撞后分解为两个或多个分子的过程.本文假设分解后产生两个分子.对于分子S,经过单分子分解后产生新的分子S1 和S2,新分子S1 和S2 与原分子S在分子结构上差别较大,表示分解过程是探索更大的解空间,避免结果过早地收敛于局部最优解.

具体设计如图5 所示:在原分子中随机选择一个分解点point,新分子S1 保留原分子S的[start,point]部分的原子,新分子S2 保留原分子S的[point,end]部分的原子,S1 和S2 剩余的原子位随机生成.对应到卸载策略中,原卸载策略经过单分子分解,随机选择一个组件作为分解点,将分解点的前部分组件和后部分组件分别保留到两个新分子的对应位置,剩余组件的执行位置随机产生,从而得到新的卸载策略.

Fig.5 Decomposition图5 单分子分解

4.4.3 分子间碰撞

分子间碰撞是指两个分子相互碰撞并反弹的过程.对于分子S1 和S2,发生分子间碰撞后产生新分子S1′和S2′,新分子S1′和S2′与原分子在分子结构上比较相似,表示碰撞过程是在分子S1 和S2 的邻域空间搜索最优解.

具体设计如图6 所示:从原分子中选择两个碰撞点point1 和point2,交换原分子S1 和S2 对应碰撞点的原子的值,形成新的分子.对应到卸载策略中,原卸载策略经过分子间碰撞,随机交换两个卸载策略中对应两个组件的执行位置,得到两个新的卸载策略.

Fig.6 Inter-Molecular ineffective collision图6 分子间碰撞

4.4.4 分子合成

分子合成是指两个或多个分子相互碰撞并合成一个分子的过程.本文假设是两个分子进行分子合成操作.对于分子S1 和S2,经过分子合成后产生新的分子S,新分子S和原分子在分子结构上相差较大,表示合成使得分子种群呈现多样化,扩大解的搜索空间.

具体设计如图7 所示:随机生成一个合成点point,新分子继承原分子S1 的[start,point]部分的原子和原分子S2 的[point,end]部分的原子.对应到卸载策略中,原卸载策略经过分子合成后,随机选择一个组件作为合成点,将第1 种卸载策略的合成点的前部分组件和第2 种卸载策略对应合成点的后部分组件保留,合成后得到新的卸载策略.

Fig.7 Synthesis图7 分子合成

4.5 算法设计

本文提出了一种面向多用户的串行任务动态卸载策略MSTDOS.针对边缘服务器资源受限的多终端任务卸载问题,MSTDOS 算法为所有应用做出近似最优的卸载决策,使得在减少应用完成时间的同时降低移动终端能耗.

算法1 中,首先,MSTDOS 对边缘服务器上所有虚拟机的状态进行初始化(line 1),保证所有虚拟机可以最早开始执行任务的时间为零,其次,进入迭代过程,为所有应用做出近似最优的卸载决策.在每次迭代过程中,遍历所有的虚拟机,选择可以最早开始执行任务的虚拟机v,记录该虚拟机的最早开始时间为RTmin(line 3～line 7),此时,将虚拟机v作为应用i卸载组件到边缘服务器的候选虚拟机.确定应用i卸载的候选虚拟机后,采用化学反应优化算法CRO(i,RTmin)为应用i做出任务卸载决策(CRO 算法的具体过程在算法2 中介绍)(line 7),并返回应用i的近似最优卸载策略,将其添加到所有应用的策略集StrategyList中(line 8),并更新虚拟机的最早开始执行时间(line 9).最后,迭代过程结束,得到所有应用的近似最优卸载策略.

算法1.多用户串行任务动态卸载策略MSTDOS.

输入:所有移动终端的卸载请求、移动应用程序;

输出:所有应用的近似最优任务卸载策略.

算法2 详细介绍了通过化学反应优化算法CRO 为应用做出任务卸载决策的过程.CRO 算法包括3 个阶段:初始化、迭代和结果输出.在初始化阶段(line 1～line 11)进行相关参数的定义(line 1),并随机生成包含PopSize个分子的分子种群(line 2～line 11).在迭代阶段(line 12～line 31)进行MaxIter次迭代过程,每一次迭代过程中,从4种基本操作中选择一种操作发生反应.将参数MoleColl定义为分子间发生反应的概率,生成一个随机数t∈(0,1),如果t>MoleColl,则发生单分子反应(line 15～line 21);否则发生分子间反应(line 22～line 28).单分子反应时,随机选择一个分子,如果分子满足分解条件,则发生单分子分解操作;否则发生单分子碰撞操作,单分子反应结束时更新策略集Strategies.分子间反应时,随机选择一对分子,判断分子对是否同时满足分子合成操作:满足则发生单分子合成操作,否则发生单分子碰撞操作.在结果输出阶段(line 32,line 33),从分子种群中选择具有最小势能的分子,作为应用i的近似最优卸载策略.

算法2.化学反应优化算法CRO(i,RTmin).

输入:移动终端i的请求、移动应用程序;

输出:应用i的近似最优任务卸载策略.

4.6 算法的时间复杂度分析

设应用的个数为N,边缘服务器的虚拟机个数为M,分子种群的规模为PopSize,最大迭代次数为MaxIter,应用的组件个数为n.算法1 中,MSTDOS 算法为每个应用做决策主要包括两个步骤:首先,从边缘服务器中选择合适的虚拟机,作为卸载应用的候选虚拟机,其时间复杂度为O(M);其次,采用CRO 算法为当前应用做出具体的任务卸载决策,其中,初始化分子种群的时间复杂度为O(PopSize×n),单分子碰撞操作的时间复杂度为O(1),单分子分解操作的时间复杂度为O(n),分子间碰撞的时间复杂度为O(1),分子合成的时间复杂度为O(n),基本操作迭代的次数为MaxIter,因而,CRO 算法的时间复杂度为O(PopSize×n+MaxIter×n2).

因此,算法1 总的时间复杂度为O(N×(M+PopSize×n+MaxIter×n2)).

4.7 算法的收敛性分析

MSTDOS 算法的收敛性主要受化学反应算法的基本操作影响.参考文献[37]中建立的有限吸收马尔可夫链模型,将每个分子结构表示成一种状态,用X表示所有状态空间的集合.对于一种状态,经过基本操作Λ后会改变其状态,令ΨΛ(x)表示分子x经过操作Λ后可能出现的状态的集合,且ΨΛ(x)⊆X,二元组(X,(ΨΛ(x),x∈X))能够抽象成一个有向无环图G(V,E),顶点集V用X表示,边集E则根据ΨΛ(x)={i|(x,i)∈E}得到.如图8 所示为经过操作Λ后状态的转换过程,可以得出,状态x1经过操作Λ可以转换成x2,x3和x4,即ΨΛ(x1)={x2,x3,x4},以此类推,ΨΛ(x2)={x2,x5,x6},ΨΛ(x3)={x1,x2,x6},ΨΛ(x4)={x3,x5},ΨΛ(x5)={x2,x6},ΨΛ(x6)={x2}.

Fig.8 A state transition under operator Λ图8 操作Λ下的状态转换

定义1(最佳可达性[37]).设G(V,E)为CRO 算法的解图,若∀x∉X-Xopt,则经过一定的状态转换,至少存在一个最优解xopt∈Xopt,使得x=x0→x1→x2→…→xI=xopt,其中,l为从x到xopt状态转换的次数,则称G(V,E)为最佳可达.

定理1.CRO 收敛于全局最优解的必要条件是G(V,E)最佳可达.

证明:CRO 中每种操作算子都存在一个解图,用G(V,Eowi),G(V,Edec),G(V,Eimi),G(V,Esyn)分别表示单分子碰撞、单分子分解、分子间碰撞和分子合成的解图,G(V,E)表示CRO 算法的解图,则满足E=Eowi∪Edec∪Eimi∪Esyn.假设解图G(V,E)不是最佳可达,其解图的任意非最优解都无法通过状态转化到达最优解,则存在解x′∈X-Xopt.CRO 算法中初始种群产生的解都是非最优解x′的概率为1/||X||n,||X||表示X的基,n为初始种群大小.于是,从x′转换到最优解的概率为

则不存在一个从非最优解到最优解的转换过程,因此,产生最优解的概率计算如下:

由此可得:当G(V,E)不满足最佳可达的条件时,CRO 算法不能收敛于全局最优解.证毕.□

5 仿真实验与结果分析

5.1 仿真实验环境

(1) 移动终端

本文的移动终端选取Oppo A37、乐视3、Vivo Y67 和小米6 这4 款手机,其详细的参数配置见表1,具体的功率值是通过移动终端的power-profile.xml 文件获取得到.

Table 1 Mobile terminals configuration表1 移动终端配置

(2) 边缘服务器

采用由实验室4 台服务器搭建的Openstack 集群环境,Openstack 的版本为Juno,4 台服务器的型号都是Lenovo ThinkServer RD330,CPU 是两个核心数为四核的Intel Xeon E5-2620,主频是2.1GHz,内存大小是32G,硬盘容量是500G,操作系统是Ubuntu 14.04 的linux 系统.

(3) 网络环境

边缘服务器的内部节点之间是通过带宽为56Gbps 的InfiniBand 高速交换机进行连接,交换机的型号是Mellanox SX602.边缘服务器与外部设备通过TP-Link 的千兆以太网交换机连接,交换机型号为TL-SG1024T.

(4) 移动应用程序

本文选用人脸识别应用[2]作为实验验证的应用程序.如图9 所示,人脸识别应用主要包括6 个顺序执行的组件,分别是图片输入、人脸检测、图像预处理、脸部特征提取、人脸匹配和结果输出.将每个组件用序号进行编号,其中,No.0 和No.5 分别代表人脸识别应用程序的开始和结束组件,固定在移动终端执行.实验中,选取一张240KB 大小的包含人脸图像的图片作为输入数据.

Fig.9 Face recognition applications图9 人脸识别应用

首先,分别在给定的移动终端和服务器上运行人脸识别应用,测出应用的每个组件的执行时间,表2 给出了每个组件的平均执行时间.

Table 2 Average execution time of each component表2 应用程序组件的平均执行时间

然后,对组件之间传输的数据大小进行了测量,测量结果见表3.

Table 3 Transmission data size among components表3 组件之间的传输数据大小

5.2 实验结果分析

本节将提出的MSTDOS 策略与已有的AllInMobile 策略[24]、SearchAdjust 策略[22]和MDSA 策略[38]进行比较.其中,AllInMobile 策略表示应用的所有组件都在本地执行,不受边缘服务器资源和网络带宽的影响.SearchAdjust 策略是一种多终端离线卸载策略,先假设边缘服务器资源无限,做出应用的卸载决策,再对不满足资源限制条件的组件进行延迟执行,保证所有任务都能够正常执行完成.MDAS 策略是一种多维搜索调整策略,在边缘服务器资源受限时,通过判断计算资源和网络资源是否发生冲突,来动态调整任务的卸载位置以达到降低延迟的效果.接下来,文献[22,38]分别通过调整移动终端数量、虚拟机数量和网络带宽这3 个参数对上述4个策略的性能进行对比分析,以及测试权重因子α和β对MSTDOS 卸载策略性能的影响和测试MEC 服务器性能瓶颈.

5.2.1 移动终端数量的影响

本组实验研究应用数量对不同卸载策略的影响,具体的参数配置见表4.

Table 4 Environment configuration of experiment 1表4 实验1 的环境配置

本实验中,边缘服务器有200 个虚拟机,网络带宽取8Mbps,移动终端选取上面提到的4 款手机,主要研究移动终端数量不断增加时对卸载策略性能的影响.具体的实验结果如图10 所示.

Fig.10 Impact of mobile terminals’ number on average completion time and average energy consumption图10 移动终端数量对平均完成时间和平均能耗的影响

从图10(a)和图10(b)可知:随着移动终端数量的增加,SearchAdjust 策略、MDSA 策略和MSTDOS 策略的应用平均完成时间和终端平均能耗都会明显的增加;而AllInMobile 策略所有组件都在本地执行,不受移动终端数量的影响,且其平均完成时间和平均能耗开销较大.其中,MSTDOS 策略与MDSA 策略相比,两者平均完成时间较接近,有一点劣势;但在平均能耗上有较大的优势.主要是由于在移动终端可用电量不充足时,MSTDOS 策略以牺牲一部分完成时间的代价来获得更低的平均能耗,而MDSA 策略只关注于减少平均完成时间,忽视了终端能耗.其中,MSTDOS 策略与SearchAdjust 策略相比,当移动终端数量较小时,两者平均完成时间非常接近,在平均能耗上有点优势;当移动终端数量较大时,在平均完成时间有明显优势,而平均能耗很接近.因为当移动终端数较少时,边缘服务器资源充足,MSTDOS 策略和SearchAdjust 策略都能取得较好的性能.但移动终端数量的增加,大量的移动终端会同时向边缘服务器提交卸载请求,MSTDOS 策略考虑到移动终端之间卸载策略的影响,能够动态地调整某些应用组件的执行位置,缩短了组件在边缘服务器上的等待时间;而SearchAdjust 策略并不会做出类似MSTDOS 策略的调整过程,对于卸载到边缘服务器的组件只考虑了延迟执行,这会增加额外的等待时间,导致应用性能的衰减.

5.2.2 边缘服务器虚拟机数量的影响

本组实验研究边缘服务器虚拟机个数对不同卸载策略的影响,具体参数配置见表5.

Table 5 Environment configuration of experiment 2表5 实验2 的环境配置

本实验中,移动终端数量为500 个,网络带宽为8Mbps,移动终端选取上面提到的4 款手机,主要研究边缘服务器上虚拟机不断增加时对卸载策略性能的影响.具体的实验结果如图11 所示.

Fig.11 Impact of virtual machines’number on average completion time and average energy consumption图11 虚拟机数量对平均完成时间和平均能耗的影响

从图11(a)和图11(b)可知:随着边缘服务器虚拟机数量的增加,SearchAdjust 策略、MDSA 策略和MSTDOS策略的应用平均完成时间和终端平均能耗都会明显的降低.主要由于随着虚拟机数量增多,应用对虚拟机资源的竞争得以缓解,边缘服务器能提供足够的资源同时服务多个终端的请求.而AllInMobile 策略所有组件都在本地执行,虚拟机数量的变化对其性能没有影响,且其平均完成时间和平均能耗开销较大.其中,MSTDOS 策略与MDSA 策略相比,两者平均完成时间较接近;但在平均能耗上有较大的优势.主要是由于两者策略的专注点不同,MSTDOS 策略是折中平均完成时间和平均能耗,在移动终端可用电量不充足时,为了降低平均能耗而牺牲一部分完成时间;但MDSA 策略主要针对减少平均完成时间,没有考虑如何降低终端能耗,从而取得了最优的平均完成时间,而导致平均完成能耗比较高.其中,MSTDOS 策略与SearchAdjust 策略相比,当虚拟机数量较小时,在平均完成时间和平均能耗上都有优势;当虚拟机数量较大时,平均完成时间和平均能耗都非常接近.因为虚拟机数量较少时,用户数大于虚拟机数量,导致用户请求对虚拟机资源的竞争激烈.此时,MSTDOS 策略会采取动态调整机制为应用做出近似最优的卸载决策,尽可能地降低所有应用的平均完成时间和终端平均能耗,而SearchAdjust 策略对于卸载到边缘服务器的请求,采用推迟执行的方法,应用之间的等待时间会大大增加,导致应用性能较差.但虚拟机数量较大时,边缘服务器资源充足,能够同时处理的用户请求量大.此时,MSTDOS 策略和SearchAdjust 策略在平均完成时间和平均能耗上都能取得较好的性能.

5.2.3 网络带宽的影响

本组实验研究网络带宽对不同卸载策略的影响,具体参数配置见表6.

Table 6 Environment configuration of experiment 3表6 实验3 的环境配置

本实验中,移动终端数量有500 个,边缘服务器提供200 个虚拟机,移动终端选取上面提到的4 款手机,主要研究网络带宽不断增加时对卸载策略性能的影响.实验具体结果如图12 所示.

Fig.12 Impact of network bandwidth on average completion time and average energy consumption图12 网络带宽对平均完成时间和平均能耗的影响

从图12(a)和图12(b)可知:AllInMobile 策略由于所有的组件都在本地执行,网络带宽的变化对其没有影响,且其平均完成时间和平均能耗的开销较大.而SearchAdjust 策略、MDSA 策略和MSTDOS 策略的应用平均完成时间和终端平均能耗都与网络带宽呈负相关关系.随着网络带宽的增加,数据传输的延迟会减小,更多的组件会卸载到边缘服务器上执行,从而降低了应用平均完成时间和终端平均能耗.3 种策略的性能随着网络带宽的增加最初变化明显,而后趋近于平稳.主要是因为网络带宽决定着移动终端与边缘服务器之间数据的传输速率与应用传输时间成反比,随着网络带宽的增大,对应用传输时间的影响越来越小,从而对决策性能的提升逐渐减低.其中,MSTDOS 策略与MDSA 策略相比,在平均完成时间上存在劣势;但在平均能耗上有较大的优势.主要是由于MSTDOS 策略侧重于平均完成时间和平均能耗的均衡,而MDSA 策略侧重于减少平均完成时间.在移动终端可用电量不充足时,前者为了得到较低的平均能耗以牺牲部分完成时间为代价,而后者只关注于减少平均完成时间,忽视了终端能耗.其中,MSTDOS 策略与SearchAdjust 策略相比,在平均完成时间和平均能耗上都有一定的优势.主要是由于边缘服务器资源有限,用户请求会对资源产生竞争.此时,MSTDOS 策略考虑到多个终端之间会相互影响,能够根据边缘服务器的状态信息调整应用的卸载策略,为所有应用做出较优的卸载决策,而SearchAdjust 策略只是延迟组件的执行,并没有采取相应措施进行调整.

5.2.4 权重因子α和β的影响

本组实验研究权重因子α和β对平均完成时间和平均能耗的影响.α和β的取值依赖于移动终端当前可用电量的多少,且满足α+β=1.具体参数配置见表7.

Ta ble 7 Environment configuration of experiment 4表7 实验4 的环境配置

本实验中,移动终端数量有500 个,边缘服务器提供200 个虚拟机,网络带宽取8Mbps,移动终端选取上面提到的4 款手机,主要研究移动终端可用电量充足和不足时对卸载策略性能的影响,实验具体结果如图13 所示.

从图13 中可以看出:随着权重因子α的减少,用户的平均完成时间是增加的,存在负相关关系;而终端平均能耗却相应减少,存在正相关关系.主要原因是:当α的值较大时,意味着移动设备有着充足的电量,用户更关心减少应用的完成时间;相反,当α的值较小时,β的值较大,意味着移动设备电量不充足.在这种情况下,执行能耗的权重比平均完成时间的更高,才能有效地降低应用执行能耗.

Fig.13 Impact of mobile terminal’s available batter power on average completion time and average energy consumption图13 移动终端可用电量对平均完成时间和平均能耗的影响

5.2.5 MEC 服务器性能瓶颈测试

本组实验研究服务器的性能瓶颈,即对于一定数量的虚拟机能够支持的最大用户数.实验配置见表8.

Table 8 Environment configuration of experiment 5表8 实验5 的环境配置

为了验证MEC 服务器的性能瓶颈,本文选择与AllInMobile 策略进行实验比较.在AllInMobile 策略中,人脸识别应用的所有组件都在移动终端上执行,通过实验测得应用平均执行时间是515ms.人脸识别应用的执行时间一般分布在370 ms～620ms[39],AllInMobile 策略的结果在合理范围内.最终实验测试结果如图14 所示.

Fig.14 Performance bottlenecks of MEC server图14 MEC 服务器的性能瓶颈

如图14 所示:当MEC 服务器的虚拟机数量变化时,通过调节提交卸载请求的用户数目来测试MEC 服务器的性能瓶颈.对于MEC 服务器上指定数量虚拟机,不断地调节移动用户数目,当MSTDOS 策略的执行性能低于AllInMobile 策略的执行性能时停止调节,将此时的用户数量作为MEC 服务器支撑的最大用户数.例如:在MEC服务器拥有50 台虚拟机的情况下,当用户数量小于1 100 时,MSTDOS 策略的执行性能高于AllInMobile 策略的执行性能;而一旦用户数量超过1 100 时,MSTDOS 策略的执行性能将会下降,同时低于AllInMobile 策略的应用性能.因此,我们能够得出一个结论:有50 台虚拟机时,MEC 服务器最多能够支撑1 100 个用户,则将此环境下1 100 个用户作为MEC 服务器的性能瓶颈.

6 总结与展望

本文针对边缘服务器资源受限的多终端任务卸载问题,提出了一种面向多用户的串行任务动态卸载策略MSTDOS.该策略根据收集的移动终端信息和边缘服务器状态信息,动态地为所有应用做出近似最优的卸载决策.最后进行一系列实验,对MSTDOS 的性能进行了评测.实验结果表明:本文提出的卸载策略在边缘服务器资源受限的多终端任务卸载场景下,在平均完成时间方面要优于SearchAdjust 策略和AllInMobile 策略,较劣于MDSA 策略;而在平均能耗方面与SearchAdjust 策略比较接近,比AllInMobile 策略和MDSA 策略有明显优势.

本文研究的任务卸载问题默认移动终端的位置是固定的,因此,将来的工作可以考虑用户移动性导致网络连接的变化,将任务卸载问题与移动性管理问题相结合来开展研究工作.此外,当前的研究工作主要考虑了边缘服务器只部署在单个固定的地理位置,其资源有限的特点会影响多终端任务卸载的应用性能,因而可以考虑部署在多个地理位置的边缘服务器场景下,研究多个终端的任务卸载问题.