随着万物互联时代的到来，智能终端设备数量和其产生的数据量都急剧增长^[1].Cisco云预测，2021年全球范围内将有超过500亿个的终端设备，这些设备每年产生的计算型数据总量将超84 ZB，高计算应用需求越来越多^[2].移动终端设备因其有限的电量和计算能力不能满足人们日益增长的应用需求，因此，如何提供高计算能力服务和服务质量成为一个研究重点.移动云计算（mobile cloud computing，MCC） ^[3]通过将移动终端设备的计算任务转移到计算能力强大的云中心对任务进行集中处理^[4]，成为提供高计算能力的解决方案.但MCC有其固有的局限性^[5]：云中心与远距离终端之间的传播时限使其无法高效处理终端设备产生的敏感时延性质的数据.因此，MCC不适合服务于时延敏感的应用.

欧洲电信标准协会（ETSI）在2014年提出移动边缘计算模式^[6].移动边缘计算是将计算和存储资源部署在移动网络边缘侧，为用户提供云计算能力、低时延和高带宽的网络服务^[7]，结合计算卸载技术很好地平衡了MCC的局限性.未来的无线系统中，小基站、平板电脑等计算能力与计算机服务器相当的设备都可作为边缘节点^[8].

计算卸载技术 ^[9]指终端设备将部分或全部计算任务交给边缘云或中心云处理，为移动终端设备在资源存储、计算性能以及能效等方面存在的不足提供解决方案，是移动边缘计算（mobile edge computing，MEC）的关键技术之一.其中，卸载决策是计算卸载技术的核心问题^[10]，卸载决策决定任务是否卸载、卸载什么以及卸载到哪里的问题^[11].在多终端、多任务的复杂场景下，卸载决策的制定需要综合任务计算量、数据传输量、边缘云计算能力和资源利用率等诸多因素.传统的卸载方式依靠虚拟机实现，而研究表明^[12]，Docker容器比虚拟机更轻量，节省了时间和能耗，它将任务程序代码、任务依赖项和环境概要文件打包到镜像副本中构建容器镜像，操作方便.在一个完备的执行架构中，根据任务的差异化制定最优的卸载决策能有效提高任务的执行效率，但依靠单一的终端设备计算、边缘计算和云计算都不能满足复杂场景的需求，不能同时平衡时延与能耗.因此，本文的目标是综合端—边—云的优势，实现以下目标：在最优化时延与能耗的情况下，将时延敏感的任务卸载至边缘节点计算，时延容忍的大数据量任务在云中心处理，时延容忍的小数据量任务在终端处理.本文的主要贡献有3个方面：

1）提出一个基于Docker的云—边—端协同的移动边缘计算框架，建立了任务依赖关系联合并行计算的任务执行序列，在并行计算设定上分别建立了本地计算、边缘计算和云计算的计算时间和能耗模型；

2）在多用户服务场景中，通过跨端—边—云的协作方式，制定任务最小计算时间和最低能耗的目标卸载决策，为实现减小系统计算时间的同时降低系统能耗的目标，设计了人工粒子蜂群（artificial particle swarm, APS）算法搜索最佳的卸载策略；

3）通过仿真实验，对比人工蜂群算法、粒子群算法和随机卸载算法验证了APS算法的性能；对比本地计算、边缘计算、云计算、本地—边缘联合计算和随机处理等计算模式，验证本系统的性能.

1.   相关工作

近年来，随着MEC的应用和卸载决策的研究不断深入，网络环境复杂度的提高和终端设备数据量的增大所带来的挑战也越来越严峻.尤其对于移动边缘计算模型的建立和卸载策略的制定，要满足任务的执行条件，当可用节点较少或卸载决策制定因素不完善时，会产生高时延甚至处理失败.

一些特定应用背景下MEC系统模型和卸载决策的研究成果已经落地.文献[13]提出了一种面向多节点的自动驾驶边缘卸载框架来提供效率和隐私导向的自动驾驶卸载服务,在多边缘节点中进行卸载调度策略的实时求解.文献[14]针对智慧城市领域提出了在能耗和响应时间之间进行权衡的任务卸载优化策略，包括2个子目标的建模和启发式双目标优化算法.文献[15]针对智能家居场景中的MEC,引入边缘节点的泛在感知能力, 在保证数据安全的基础上实现边缘节点资源的分配.文献[16]研究双无人机辅助MEC系统的安全问题，通过抗干扰帮助地面终端设备计算卸载的任务，联合了优化通信资源、计算资源和无人机轨迹进行任务卸载.

从MEC应用可知，任务卸载模型和计算卸载决策是MEC中的研究热点，二者共同决定任务的执行位置与分配资源，主要研究方向有3个：时延、能耗、权衡时延与能耗.文献[17]提出一个任务卸载和异构资源调度的联合优化模型，最小化用户的设备能耗、任务执行时延和成本来求解最优的任务卸载算法.文献[18]为了使时延敏感的处理任务在近终端用户执行，提出支持多个物联网服务提供商在一个通用MEC平台部署的兼容方案，在平台内引导物联网数据传输.文献[19]提出缓存辅助边缘计算的卸载决策制定与资源优化方案，通过建立最小化用户在任务执行时最高能耗值，得到理想的卸载决策集合与资源分配方案.文献[20]制定了在迁移能量预算的条件下尽量减少任务的平均完成时间的目标，设计了基于强化学习的分布式任务迁移算法.文献[21]考虑多用户的MEC系统以最小化终端能耗为目标，通过联合优化任务传输功率、局部计算和边缘计算能力来研究任务卸载问题.

然而，文献[13−21]研究都依赖单一的计算模式，在通信资源有限的条件下，会因通信链路堵塞造成更大的时延.因此提出本文第一个改进点:建立多终端、多任务的云—边—端协作任务执行模型，并加入任务计算结果传回终端设备的时延异步性因素；联合时延与能耗，通过实验为时延与能耗分配最优权重进行计算卸载，保证此模型具备实际意义.

对于任务卸载策略的研究大多处于粗粒度范畴，随着任务需求的提升，近年来也出现了考虑任务的差异化并对其进行预处理的研究，表现为将任务进行划分或建立任务依赖关系.文献[22]将一个任务划分为多个子任务卸载给多个MEC节点，通过预测每个候选MEC节点上每个任务的总处理时间决定子任务卸载位置.文献[23−24]研究单用户MEC系统、移动设备包含一个由多计算组件或具有依赖关系的任务组成的应用程序，根据依赖执行顺序计算出最优的任务卸载策略.文献[25]研究多用户任务卸载，为提高资源利用率，提出基于建立任务依赖关系的卸载调度器.文献[26]先研究2个设备间的任务依赖与相关性，然后扩展到复杂交互的多用户场景，实现最优的任务卸载策略和资源分配.文献[27] 提出一种用于多移动应用的依赖任务卸载框架,将有依赖约束的计算密集型任务自适应地卸载到MEC和云.任务划分的研究适用于资源需求大、数据量大和数量偏少的任务集，而在密集复杂环境中划分任务会导致计算量呈指数增长，于系统服务无益.

文献[22−27]研究中建立任务依赖关系的方法大多面向单用户系统，通过传统的有向无环图（directed acyclic graph，DAG）进行任务拓扑排序，再扩展到多个设备的DAG调用. 在每个处理器仅执行1个任务的情况下多个任务面临等待，且调用多个DAG进行任务分配无法解决有依赖任务与无依赖任务的区别处理，造成不必要的时延浪费.基于文献[22−27]分析，提出本文的第2个改进点：1）将任务依赖关系与任务并行处理相结合，以最优最长链路拓扑排序的Kahn算法为基础，加入行满秩矩阵结果要求，使算法输出的任务依赖矩阵的行元素直接表明任务的优先级. 第一优先级任务为无依赖任务与依赖初始任务的集合，优先级则代表任务的执行顺序；2）再结合云—边协同架构的并行处理原则，将表征任务依赖的优先级矩阵抽象成任务执行序列，每个序列将同步执行，大大缩短任务的排序处理时延.

卸载策略求解过程属于NP难问题，MEC研究中大多将其转化为多因素优化问题，近年来使用较多的求解方式是群体智能算法.文献[28−29]研究了面向智能物联网的MEC应用，采用遗传（genetic algorithm, GA）算法优化计算成本与能耗进而得到卸载决策.文献[30−31] 为了减少多接入环境和高需求应用的能耗，利用模拟退火（simulated annealing, SA）算法全局寻优能力求解卸载决策，使复杂优化问题便于处理. 文献[32] 结合灰狼和混合鲸鱼优化算法实现卸载决策的3个目标优化，并对比GA说明了混合算法在考虑多因素求解卸载决策时的优越性.文献 [33]为预测多服务器MEC的自适应服务质量，采用人工蜂群（artificial bee colony，ABC）算法求解策略后再将各服务器结果进行整体对比选择任务执行节点.在多接入边缘协同环境中，应用最为广泛的是粒子群（particle swarm optimization，PSO）算法.文献[34−35]研究了多MEC服务器对多任务的卸载决策制定，采用PSO得到任务迁移决策和计算资源分配方案.文献[36]应用PSO作为卸载决策算法处理计算密集型和时延敏感型任务，且对比说明PSO相比于GA与SA的优越性. 但PSO在处理异构边缘节点和复杂约束优化问题时全局寻优收敛时间太长，因此需融入局部寻优能力强的算法平衡PSO的缺陷，如ABC是群体智能中最成功的局部寻优算法之一，ABC与PSO的混合更有利于发挥群体智能算法在MEC中的作用.

基于文献[28−36]研究提出本文的第3个改进点为：结合ABC算法的局部寻优能力与PSO算法的全局寻优能力，组合成APS算法用于求解云—边—端协同框架下联合时延与能耗的卸载决策；从降低算法复杂度的角度出发，通过引入“全优率”参数进行迭代结果的适应度函数判断，决定个体蜂的类型与蜜源搜索方式. 表1为现有的适用于复杂约束的PSO-ABC混合算法相关研究与本文方法的对比，进一步说明本文算法特点.

表  1  ABC-PSO混合算法相关研究与本文方法对比

Table  1.  Comparison of Researches on ABC-PSO Hybrid Algorithm and the Proposed Method

方法	混合方式与特点	有无 参数	复杂度 程度
文献[37] 方法	将PSO寻优结果作为ABC的初始种群；后期收敛快，容易陷入局部极优.	无	一般
文献[38] 方法	ABC优化后的蜜源作为PSO搜索空间；前期易遗漏最优解.	无	一般
文献[39] 方法	3个ABC循环更新蜜源后用PSO寻优，保证蜜源优化，但循环更新耗时太长.	无	高
文献[40] 方法	PSO与ABC以是否产生侦查蜂交替更新；同步搜索无法保证最优解质量.	无	高
本文方法	ABC搜索后对比蜜源和全局最优解；前后期互为参考与PSO交替转换.	有	低

下载: 导出CSV 

| 显示表格

2.   系统架构

本文提出一个基于Docker的轻量级、虚拟化的云—边—端协同卸载架构，它包含K个云中心服务器、M个边缘服务器和L个移动终端设备.边缘服务器部署在近移动终端设备侧的微型基站上；远程云中心服务器附加在宏基站上，其与边缘服务器相比，它的存储和计算能力更强大.设云中心集合表示为$K= \{1,2,…,k\}$, 边缘节点集合表示为$M=\{1,2,…,m\}$, 移动终端设备集合表示为$L=\{1,2,…,l\}$.同时假设每个终端设备与边缘节点和云中心相关联，移动设备与基站之间的链路集表示为$R=\{1,2,…,r\}$.

如图1所示，系统架构由卸载调度、卸载决策算法和任务执行部分（移动设备侧、边缘节点侧和云中心侧）组成.首先，移动终端设备生成任务集合并制定执行矩阵；其次，由卸载决策模块收集任务的执行要求和边缘节点的资源使用情况，通过卸载决策算法得到任务的执行方案；最终，将队列中的全部任务分别发送到本地计算任务集合、边缘节点，计算任务集合和云中心计算任务集合.经过卸载模块计算，无需卸载的任务在本地进行计算，需要卸载的任务通过卸载调度模块将任务程序代码、数据和Dockerfile文件发送至边缘节点或云中心，构建任务镜像并创建容器进行任务计算，计算完成后将结果返回原终端设备.

图  1  云—边—端系统架构

Figure  1.  Cloud-edge-end system architecture

下载: 全尺寸图片 幻灯片

3.   系统模型和卸载决策制定

基于图1所示的多用户移动边缘计算场景，卸载决策模块为基站覆盖服务区的N个终端用户提供任务执行方案.每个终端用户都可以选择在本地计算任务，或将任务卸载至边缘节点或云中心执行.任务模型、本地计算模型、边缘计算模型、云计算模型在本节进行说明.

3.1   任务依赖模型与并行计算说明

3.1.1   任务模型

假设任务是完整的且不可再划分，移动终端设备产生n个待处理任务$Task=\{T_1,T_2,…,T_n\}$,每个任务T_j有6个基本属性：

其中：w_j表示任务j的计算量，通过CPU周期度量；f_min.j表示任务j需要的最小计算能力；cpu_j和mem_j分别表示任务j执行时需要的CPU资源和内存资源；data_j表示任务j卸载时需要传输的数据量，包括过程代码和输入参数等信息；t_max.j表示完成任务j允许的最大时延.

3.1.2   任务依赖模型

同一设备产生的不同任务通常具有一定的依赖关系，本文通过建立任务执行矩阵来提高处理任务效率.当任务生成后，将任务如何执行的初始状态抽象成DAG；再将DAG进行拓扑排序生成任务执行矩阵；最后根据卸载策略判断任务的执行位置.本文设计的任务依赖关系算法以双维护集Kahn拓扑算法为基础，融入行满秩矩阵要求,在保证最优且唯一的同时避免出现分支多组合路径.为与任务并行计算设定相结合，此算法的目标是在多种拓扑顺序的情况下选出多行少列的依赖关系矩阵结果作为任务调度方案，最大限度确保有依赖任务有序执行，无依赖任务快速执行.任务依赖矩阵结果同时也是任务优先等级的划分结果，每一行向下递减一个优先级.执行伪代码如算法1.

算法 1 .任务依赖关系算法 /*对输入的有向无环图生成拓扑排序后的执行矩阵L（该矩阵中行向量线性无关）.

输入：有向无环图G，G=(V，E)，V表示任务集，E　　　　 表示任务之间依赖关系链路集；

输出：执行矩阵L.

① 建立可放置已排序任务的空矩阵L；

② 将没有入度链路的任务放置在集合S中，　　　　S=$\{S_1,S_2,…,S_n\}$，S_n代表循环中第n轮　　　　判断无入度链路的任务；

③ while $S \neq \varnothing$

④　将S_n中任务放进L第n行(从S₁开始顺　　　　　序执行)；

⑤　从S_n中删去任务v₁；

⑥ 　for 每个通过一条链路e从任务v₁到达任　　　　　务v₂

⑦　　从E中删去链路e；

⑧ 　　if 任务v₂没有其他的入度链路

⑨　　　　将任务v₂放入S_n+1中；

⑩ 　　end if

⑪ 　end for

⑫ end while

⑬ if E中存在任意一个循环

⑭ 　return 错误；

⑮ else

⑯ 　return L；

⑰ end if

任务之间的初始状态关系如图2所示, 根据拓扑算法建立执行矩阵式（2），假设由卸载决策算法得到任务的决策矩阵式（3），其中，“1”表示任务在终端设备执行，“−1”表示任务在边缘节点执行，“0”表示任务在云中心执行.

图  2  任务之间的初始状态关系

Figure  2.  Initial state relationship among tasks

下载: 全尺寸图片 幻灯片

3.1.3   任务并行计算说明

采用Docker封装卸载的形式使并行计算成为可能.当边缘节点i满足任务j需求的存储资源但不满足任务j 的CPU计算资源需求时，结合时延与能耗，判断是否等待边缘节点i计算完1个或若干任务后释放CPU资源以达到任务需求，若合适仍将任务卸载到此边缘节点.任务到达边缘节点i后先储存到内存中，等待满足CPU资源后参与计算.并行计算过程如图3所示：

图  3  边缘节点并行计算过程

Figure  3.  Parallel computing process of edge node

下载: 全尺寸图片 幻灯片

图3中a₁，a₂，a₃，a₄分别为任务1~4抵达节点i的时间.假设任务1~3抵达节点i时，节点可用内存资源和计算资源大于任务所需资源，则任务1~3立即执行；假设任务4抵达节点时节点可用计算资源小于任务所需计算资源，则任务4不能立即执行.对比任务1~3的计算时间，任务2最先计算完毕，其次任务1完成计算；假设任务1释放CPU 计算资源后该节点满足任务4的计算需求，则任务4开始执行，时间a₆为任务1的完成时间.我们将考虑任务之间的并行依赖关系后制定的卸载决策表示为ST={st₁, st₂,…, st_n}，st_j表示任务j的执行地点.

任务并行计算的重要基础是任务依赖矩阵的生成，矩阵行向量传达了任务的优先级执行顺序，行向量之间的无依赖关系任务就可以依据资源情况在相关节点并行计算.当设备数量与任务数量较多时，结合任务依赖于并行计算，实现同一时间计算出不同设备上同一优先级的任务结果，真正将多维分散无序计算变为m$\times$1维有序执行.

3.2   本地计算模型

任务在终端设备进行计算的时延如式（4）.其中f_l表示终端设备的计算能力，cpu_l表示终端设备可用CPU资源，mem_l表示终端设备可用内存资源.任务在终端设备进行计算的能耗为E^ED，${\sigma }_{1}\times {f}_{l}^{2}$表示CPU循环1个周期所产生的能耗，${\sigma }_{1}$表示由芯片结构而定的开关电容.

3.3   边缘节点计算模型

本系统中M个边缘服务器的集合为$Edge= \{Ed_1,Ed_2,…, Ed_m\}$，每个边缘服务器的基本属性如式（6）所示.f_i表示边缘节点i的最大计算能力，cpu_i表示边缘节点i的可用CPU资源，mem_i表示边缘节点i的可用内存资源，R_i是边缘节点与移动设备间的数据传输速度，P_i为边缘节点i的发射功率.

考虑任务卸载至边缘节点时存在并行计算的情况，假设模型中并行计算等待过程的能耗忽略不计，只讨论产生的等待延时，则任务计算完成并将结果返回移动终端设备的总时延${T^{{\text{EN}}}}$计算存在2种情况，如式（7）所示：

其中$T_{{\text{ED}} \to {\text{EN}}}^{{\text{trans}}}$表示任务j由移动设备卸载到边缘节点i的传输时间，$T_{{\text{EN}}}^{{\text{compu}}}$表示边缘节点i计算任务的时间，${T^{{\text{wait}}}}$表示并行计算时任务的等待时间，$T_{{\text{EN}} \to {\text{ED}}}^{{\text{trans}}}$表示任务结果由边缘节点$i$传输回移动终端的时间.

1）任务j抵达边缘节点i后，若边缘节点$i$当前剩余资源满足任务计算所用资源，即$cpu_j \leqslant cpu_i$，$mem_j \leqslant mem_i$.此时任务j可立即执行，其完成时间如式（8）所示：

$T_{{\text{ED}} \to {\text{EN}}}^{{\text{trans}}}$的计算方式如式（9）所示，假设移动设备与边缘服务器之间有q条链路，且每条链路只允许有1台设备占用.由香农公式式（10）得R_i，其中，W为信道之间带宽，P_l表示移动设备的发射功率，${\tau ^2}$表示噪声功率，I_q为链路的干扰功率.

$T_{{\text{EN}}}^{{\text{compu}}}$和$T_{{\text{EN}} \to {\text{ED}}}^{{\text{trans}}}$的计算方式分别为式（11）和式（12），其中$data_{{\text{re}}}^{{\text{EN}}}$表示边缘节点任务计算的结果数据.

任务在边缘节点进行计算的能耗如式（13）所示，$E_{{\text{ED}} \to {\text{EN}}}^{{\text{trans}}}$表示任务j由移动设备卸载到边缘节点$i$的能耗，$E_{{\text{EN}}}^{{\text{compu}}}$为边缘节点i计算任务$j$的能耗，$E_{{\text{EN}} \to {\text{ED}}}^{{\text{trans}}}$表示边缘节点i计算任务j得到的结果返回终端设备的能耗，以上3部分的能耗计算方式分别为式（14）、式（15）和式（16）.

2）任务j抵达边缘节点i后，若边缘节点$i$当前剩余资源小于任务计算所用资源，即cpu_j>cpu_i ，mem_j>mem_i .此时任务j需要等待此节点执行完优先级高的任务并释放足够的计算资源后方可参与计算，其完成时间为式（17）.等待时间可根据已建立的任务执行矩阵得式（18）.

$T_{front \in n}^{{\text{compu}}}$表示当前任务之前到达节点$i$的任务的计算时间；${T_{front}^{{\text{trans}}}}$表示在当前任务之前到达节点$i$的任务的传输时间；${T_{behind}^{{\text{trans}}}}$表示当前任务之后到达节点$i$的任务的传输时间.

3.4   云中心计算模型

本系统中部署K个云服务器，因为云中心的CPU资源和内存资源远高于终端设备和边缘节点，本文仅考虑云中心的3个属性.其中，f_k表示云中心的最大计算能力，R_k为云中心与移动设备间的数据传输速度，P_k表示云中心的发射功率.

任务卸载到云中心的时延为式（20）中的$T^{\text{C}}$，式（21）中$T_{{\text{ED}} \to {\text{C}}}^{{\text{trans}}}$表示任务j由移动设备卸载到云中心的时间，式（22）中$T_{\text{C}}^{{\text{compu}}}$表示任务j在云中心的执行时间，式（23）中$T_{{\text{C}} \to {\text{ED}}}^{{\text{trans}}}$为任务j在云中心计算的结果数据返回终端设备的时间.其中$data_{{\text{re}}}^{\text{C}}$为云中心计算任务的结果数据.

云中心的能耗${E^{\text{C}}}$计算公式如式（24）所示，时延对应的卸载传输能耗$E_{{\text{ED}} \to {\text{C}}}^{{\text{trans}}}$、执行能耗$E_{\text{C}}^{{\text{compu}}}$和回程传输能耗$E_{{\text{C}} \to {\text{ED}}}^{{\text{trans}}}$计算公式分别为式（25）、式（26）和式（27）

3.5   联合时间与能耗的卸载决策目标函数

综上，可以得到所有任务的云—边—端协同卸载执行计算需要的时间$T_{{\text{all}}}$描述和能耗$E_{{\text{all}}}$描述分别为式（28）和式（29），其中${\beta _{{\text{ED}}}},{\beta _{{\text{EN}}}},{\beta _{\text{C}}} \in \left\{ {0,1} \right\}$. 规定任务在1个位置执行，${\beta _{{\text{ED}}}},{\beta _{{\text{EN}}}},{\beta _{\text{C}}}$这3个参数只取0或1，根据任务的执行位置决定云、边、端时间与能耗的参数取值.

为了实现云—边—端协同卸载模式下计算时间和能耗的联合优化，设计了科学评价任务卸载效果的目标函数$Q$.其中, ${\theta _1}$和${\theta _2}$分别表示时延和能耗在目标函数中所占的比重，二者最优取值通过实验判定. $T_{{\text{all}}}^{{\text{ED}}}$和$E_{{\text{all}}}^{{\text{ED}}}$分别为所有任务均在终端设备计算的时间和能耗；$T_{{\text{all}}}^{\text{C}}$和$E_{{\text{all}}}^{\text{C}}$分别表示所有任务均在云中心计算的时间和能耗.

由式（30）可知，系统计算时间和能耗的优化问题转化为有约束条件下目标函数$Q$的最优化问题，即通过搜索卸载决策方案获得$Q$最大值.优化目标及其约束条件如式（31）所示：

4.   基于APS算法求解卸载决策

4.1   APS算法说明

本文设计的人工粒子蜂群算法包含5个要素：蜜源、引领蜂、跟随蜂、粒子蜂和侦察蜂.APS采用原人工蜂群算法进行初始化，随机生成初始解$x_i$ $(i=1,2,…,SN）$.在搜索阶段，引领蜂依据式（32）寻找新蜜源.

其中$j\in\{1,2,…,D\}$，$k\in\{1,2,…,SN\}$且$i\ne k$，${\varphi }$为[−1,1] 之间的随机数.${x}_{ij}'$是新蜜源位置，${x}_{ij}$是当前蜜源位置，${x}_{kj}$是当前蜜源邻域中的一个随机蜜源位置，比较生成的新解${x}_{i}'=\left\{{x}_{i1}',{x}_{i2}',…,{x}_{iD}'\right\}$和初始化的解${x}_{i}= \left\{{x}_{i1},{x}_{i2},…,\right. \left.{x}_{iD}\right\}$的适应度值，采用贪婪选择策略保留较好的解.跟随蜂按式（33）所描述的概率公式选择蜜源，其中${fit}_{i}$表示${x}_{i}$的适应度值，${fit}_{i}=Q$，${P}_{i}'$表示选择概率.

APS融合ABC算法和粒子群算法，解决了ABC搜索效率低和提前陷入局部最优的问题.主要体现在引领蜂变异为侦查蜂阶段，APS改变了ABC算法的位置更新策略，根据全局最优解的位置和个体最优解的位置来搜索蜜源，跳出局部最优.

APS算法中引入了式（34）“全优率”参数和粒子蜂对ABC与PSO进行融合，全优率的含义为：每一个个体在迭代过程中的适应度值相对于全局最优解的概率. 假设连续几代蜜源适应度不变时所有的引领蜂都为粒子蜂，通过衡量全优率，将引领蜂分成2类：一类是全优率大于1的蜜蜂变异为侦查蜂，在当前蜜源附近搜索；另一类全优率小于1的蜜蜂变异为粒子蜂，迭代按照PSO算法的式（34）进行迭代.

其中$x_i^k$表示第$i$个粒子蜂迭代到$k$代时的位置， x_g表示所有粒子蜂中全局最优解的位置.当引领蜂转变为侦查蜂时按照式（35）更新位置，当引领蜂转变为粒子蜂时按照式（36）和式（37）更新位置.rand(0,1)表示 [0,1]间的随机数，${x}_{j}^{\mathrm{m}\mathrm{a}\mathrm{x}}$和${x}_{j}^{\mathrm{m}\mathrm{i}\mathrm{n}}$是参数变量的最大值与最小值.其中，${v}_{i}^{k}$为第i个粒子蜂迭代到第k代时的速度，w为惯性权值，${c}_{1}$和${c}_{2}$都为正常数，通常取${c}_{1}={c}_{2}=2$，${x}_{\mathrm{p}}$为粒子蜂i找到的最优解.

4.2   算法描述及流程

算法2. 为基于APS算法的卸载决策.

步骤1. 初始化参数，包括种群规模、引领蜂和跟随蜂数量、最大迭代次数、限定蜜源更新次数、搜索空间等；

步骤2. 随机生成初始蜜源，要求初始蜜源表示的卸载决策方案均满足各任务对内存的需求；

步骤3. 进行邻域搜索，通过式（33）分别计算初始蜜源和领域更新后蜜源的适应度，采用贪婪选择方法保留较好的蜜源；

步骤4. 根据引领蜂分享的信息，判断是否为跟随蜂分配蜜源，如果分配则记录下最好的蜜源位置；

步骤5. 如果不分配则为跟随蜂选择1个蜜源，然后搜索新的蜜源计算适应度函数进行贪婪选择，并保留较好的蜜源；

步骤6. 判断是否达到最大蜜源更新次数，“是”则记录最好的蜜源位置，“否”则回到步骤5；

步骤7. 为避免陷入局部最优，进行当前最好蜜源的全优率判断，全优率大于1则产生侦查蜂，使用式（4）更新蜜源位置；全优率小于1则产生粒子蜂，使用式（5）和式（6）更新蜜源位置；

步骤8. 判断是否达到最大迭代次数，“是”则进行步骤9，“否”则回到步骤3；

步骤9. 输出最优卸载决策ST.

算法2流程图如图4所示.

图  4  APS算法流程图

Figure  4.  Flow chart of APS algorithm

下载: 全尺寸图片 幻灯片

5.   仿真实验与结果分析

5.1   仿真实验介绍

在本节中，部署了一个云—边—端协同的网络结构仿真，提出的任务卸载架构包括1个服务半径为1 km的云中心服务器、4个服务半径为500 m的边缘服务器和50个移动终端设备，总覆盖面积为2 km×2 km.移动终端设备和边缘服务器随机分布在覆盖区域中.本文采用Python语言进行编程仿真，仿真实验中使用的相关参数参考文献[41]设定，如表2所示，实验内容如表3所示.

表  2  实验参数设定

Table  2.  Experimental Parameters Setting

参数	取值
终端设备数量L	50
边缘节点数量M	4
信道带宽W/MHz	20
信道噪声功率${\tau ^2}$/W	2×10−13
链路之间干扰功率Iq /W	2×10−13
任务计算量wj /( cycle·s−1)	[10,1000]
任务输入数据量dataj /MB	[0.5,5]
任务所需最小计算能力fmin.j /GHz	[2.0,20]
任务所需内存资源memj /MB	[50,500]
任务所需CPU资源cpuj /GHz	[1.0,3.0]
任务最大容忍时延tmax.j /s	[0.5,1.5]
终端设备计算能力fl /GHz	4
终端设备发射功率Pl /W	[0.1,0.5]
开关电容${\sigma _1}$/μF	0.01
边缘节点最大计算能力fi /GHz	50
边缘节点可用CPU资源cpui /GHz	[3.0,30.0]
边缘节点可用内存资源memi / MB	[1,40]
边缘节点与设备间传输速度Ri / Mbps	[1,10]
边缘节点发射功率Pi /W	4
云中心最大计算能力fk /GHz	100
云中心与设备间传输速度Rk /Mbps	[1,10]
云中心发射功率Pk /W	10
${\theta _1}$和${\theta _2}$初始值	0.5,0.5

下载: 导出CSV 

| 显示表格

表  3  实验内容设定

Table  3.  Experimental Contents Setting

项目	实验内容
1	采用APS算法评估目标函数中时间占比和能耗的占比，并得出最优的${\theta }_{1}，{\theta }_{2}$值.
2	从计算时间和能耗角度对比APS，ABC，PSO以及随机卸载算法（RAN）的表现，评估APS卸载决策算法的性能.
3	研究终端数量和边缘节点数量对协同卸载系统性能的影响.
4	研究任务的配置文件对系统性能的影响.
5	研究任务最大延迟和最小计算能力对系统性能的影响.
6	研究终端设备最大发射功率对系统性能的影响.

下载: 导出CSV 

| 显示表格

为验证以上实验内容对系统性能的影响，将本文方案与5种任务处理方式作比较:

1）Local：任务只在终端设备进行处理计算.

2）Edge：任务随机卸载到边缘节点上计算.

3）Cloud：任务全部卸载到云中心执行.

4）Local-Edge：任务在本地和边缘节点执行.

5）Random：任务在端—边—云随机执行.

5.2   实验结果与分析

5.2.1   ${\theta }_{1}，{\theta }_{2}$的取值实验

图5和图6分别表征了系统在处理100个随机任务的情况下，${\theta _1}$取不同的值时系统的计算时间和能耗情况.从图5和图6可知，当${\theta _1}$=0.6时，系统计算时间最短；${\theta _1}$=0.5时，系统能耗最低.同时从2个结果图的变化趋势可以看出，${\theta _1}$的取值对于系统计算时间的影响较大，能耗的变化相比于计算时间来讲比较平缓，尤其是当${\theta _1}$=0.4，0.5，0.6时，能耗的变化微小.因此综合以上情况分析，取${\theta _1}$=0.6时具有最合适的延时与能耗表现.

图  5  ${\theta _1}$的取值与系统计算时间的关系

Figure  5.  The relationship of value ${\theta}_1$ and the systematic calculation time

下载: 全尺寸图片 幻灯片

图  6  ${\theta _1}$的取值与系统能耗的关系

Figure  6.  The relationship of value ${\theta }_1$ and the systematic energy consumption

下载: 全尺寸图片 幻灯片

5.2.2   卸载决策算法验证

在处理不同的任务量并经过100次迭代计算后，4种卸载决策算法的计算时间和能耗对比分别如图7和图8所示.由图7可知，当任务数量较少时，APS算法虽然具备一定的优越性，但同比ABC和PSO差距较小；随着任务数量的增多，APS相比于ABC算法、PSO算法和RAN算法，计算时间分别降低了19.6%，29.6%，51.9%.图8展示了系统能耗的变化，对比不同数量的任务，APS算法的能耗都在不同程度上降低，其中，相比于ABC算法能耗最大能降低12.8%，相比于PSO算法能耗最大能降低40.3%，相比于RAN算法能耗最大能降低50.2%.由此可见，APS算法具有不可比拟的优越性，极大提升了整个系统性能.

图  7  不同任务数量下4种算法的计算时间

Figure  7.  Calculation time of four algorithms for different numbers of tasks

下载: 全尺寸图片 幻灯片

图  8  不同任务数量下4种算法的系统能耗

Figure  8.  Systematic energy consumption of four algorithms for different numbers of tasks

下载: 全尺寸图片 幻灯片

5.2.3   用户数量对系统的影响

图9和图10分别评估了终端设备的数量对系统总时延和系统能耗的影响.从图9中可以看出，所有方案的总时延都随着终端设备数量的增加而上升，但Joint的总时延始终是最小的.当终端设备数量增多时，所产生的任务需要的计算资源也迅速增多，结合任务的数据量等特性，系统依据卸载模型将一些任务从终端设备卸载到边缘节点或云中心处理，以获得最小的服务时延.此外，发现当用终端数量逐渐增多时，边缘节点计算方案的总时延大于本地计算方案的总时延，这是由于任务在卸载过程中信道和边缘节点计算资源的竞争没有遵循合理的卸载顺序，导致任务在传输过程和计算过程都存在不必要的等待环节，因此时延越来越高.

图  9  终端用户数量对系统总时延的影响

Figure  9.  Effect of the number of end users on the total systematic delay

下载: 全尺寸图片 幻灯片

图  10  终端用户数量对系统能耗的影响

Figure  10.  Effect of the number of end users on the systematic energy consumption

下载: 全尺寸图片 幻灯片

从图10中可以看出，系统能耗也随着终端数量的增多而增多，且Joint的能耗表现具有很强的优越性.Edge的能耗低于Cloud的能耗的原因在于：不同于系统时延，任务卸载到边缘节点的方案存在滞后等待，当任务到达Edge后，等待过程的能耗可忽略不计.相比于远距离的Cloud，Edge的传输能耗显著降低，因此，总体上Edge的能耗低于Cloud的能耗.

5.2.4   任务的配置文件对系统性能的影响

这里评估了任务所需计算资源量和任务输入数据量对系统总体时延和系统能耗的影响（终端设备数量为30）.2种配置下各方案的时延表现如图11和图13所示.6种方案的总体时延都随任务计算资源量的增加而增加，但Joint的总时延始终是最小的.由于本地计算不涉及任务的卸载和传输，因此时延保持为一个稳定的数值.而 Edge模式随着卸载任务和数据量的增加时，出现争夺通信资源和边缘节点计算资源的情况，因此其时延要高于云计算和本地计算.从2种任务配置因素得知，本文系统可快速处理一些要求计算资源量高和输入数据量高的任务.

图  11  任务所需计算资源对系统时延的影响

Figure  11.  Effect of computing resources required by tasks on systematic delay

下载: 全尺寸图片 幻灯片

如图12所示，当任务所需计算资源量增加时，6种方案的能耗随之上升，但Joint的能耗远小于其他系统的能耗.通过计算平均任务所需资源量，Joint能耗分别比Random降低了58.28%，比Local降低55.60%，比Cloud降低43.54%，比Edge降低24.46%，比Local-Edge降低16%.由图14得，随着任务输入数据量的增加，本地计算不涉及数据输入，能耗逐渐稳定增大，Joint尤其表现优越.因此，当面临大数据量输入时，Joint的能耗表现远远优于其他模式，其中相比Random最高降低了52.72%，比Local最高降低29.20%，比Cloud最高降低26.92%，比Edge最高降低22.45%，比Local-Edge最高降低19.82%.

图  12  任务所需计算资源对系统能耗的影响

Figure  12.  Effect of computing resources required by tasks on systematic energy consumption

下载: 全尺寸图片 幻灯片

图  13  任务输入数据量对系统时延的影响

Figure  13.  Effect of the amount of date input by tasks on systematic delay

下载: 全尺寸图片 幻灯片

图  14  任务输入数据量对系统能耗的影响

Figure  14.  Effect of the amount of date input by tasks on the systematic energy consumption

下载: 全尺寸图片 幻灯片

5.2.5   任务的固定属性对系统性能的影响

这里评估了任务最大时延和任务所需最小计算能力对系统时延和能耗的影响.如图15所示，当任务的时延要求逐渐增大时，将有更多任务在本地执行，同时所需计算资源量大的任务卸载到边缘节点，因此系统总时延随着时延容忍的增加而减少. Joint相比其他方案的总时延总是保持最小，图16中能耗也呈现出和时延状态相似的表现， Joint方案对应总体时延和能耗始终维持低数值，具有一定优越性.

图  15  任务最大延迟对系统延时的影响

Figure  15.  Effect of the maximum delay of tasks on the systematic delay

下载: 全尺寸图片 幻灯片

图  16  任务最大延迟对系统能耗的影响

Figure  16.  Effect of the maximum delay of tasks on the systematic energy consumption

下载: 全尺寸图片 幻灯片

图17和图18 反映了任务所需的最小计算能力对系统的影响.由图17得知，当最小所需计算能力不断增加时，任务的执行位置越来越受限，从而导致本地设备不能参与计算，所有任务为了卸载至边缘服务器或者云中心，全部都去竞争有限的信道资源与网络资源，因此系统总体时延性能变差.从图18可知，虽然Joint的能耗在高计算能力需求时在一定程度上与边缘计算模式和云计算相近，但充分满足了系统时延的要求.综上所述，与其他5种方案相比，Joint方案在大规模计算情况下具备很强的自适应性.

图  17  任务所需最小计算能力对系统延时的影响

Figure  17.  Effect of the minimum computing power required by tasks on the systematic delay

下载: 全尺寸图片 幻灯片

图  18  任务所需最小计算能力对系统能耗的影响

Figure  18.  Effect of the minimum computing power required by tasks on the systematic energy consumption

下载: 全尺寸图片 幻灯片

5.2.6   终端最大发射功率对系统性能的影响

图19和图20分别显示了终端设备最大发射功率对系统时延与能耗的影响.由图19可知随着终端设备最大发射功率的不断增加，发射功率的范围变大，终端设备的可用功率相应增加，因此任务卸载速度变快，系统总时延变小.由图20得知，终端最大发射功率增加幅度小，但系统时延下降较快，因此系统能耗总体上呈下降趋势.Joint方案相比于其他方案不论是时延还是能耗都显现出一定的优势，终端设备最大发射功率在合理范围内调整时，Joint系统性能始终最优.

图  19  终端设备最大发射功率对系统延迟的影响

Figure  19.  Effect of the maximum transmitting power of end on the systematic delay

下载: 全尺寸图片 幻灯片

图  20  终端设备最大发射功率对系统能耗的影响

Figure  20.  Effect of the maximum transmitting power of end on the systematic energy consumption

下载: 全尺寸图片 幻灯片

6.   总　　结

在本文中，我们部署了一个云—边—端协同计算架构，此架构可实现移动终端设备的任务择优在本地、边缘节点或云中心处理.本文在以往研究成果的基础上考虑了任务之间存在的依赖关系、任务并行计算以及任务结果回程问题，基于此分别建立了端、边、云任务计算模型，设计联合优化时延与能耗的目标函数；其次，在ABC算法和PSO算法基础上引入全优率指数与粒子蜂，设计了APS算法求解联合优化时延与能耗的任务卸载决策；最后，在多接入情况下，构造最小化任务计算时间和能耗的目标问题，在评估各项资源的情况下实现自适应地卸载任务.仿真结果表明，本文方案在多终端、多任务情况下可提供低时延、低能耗的服务.未来本研究计划通过联合优化时延和能耗进一步优化任务执行矩阵，并探索5G网络环境下，结合人工智能技术动态预测和评估计算资源的利用和服务质量.

作者贡献声明：张文柱指导论文写作，并参与实验设计和实验数据分析；余静华完成数据分析和论文的写作.