打开文本图片集

摘要：针对移动云计算中任务调度存在时间长，成本消耗大的问题，提出了基于Fireworks Algorithm-Whale Optimization Algorithm（FWA-WOA）融合的移动云计算任务调度策略。首先，阐述了移动云计算任务调度概念，其次，针对FWA算法自身过早收敛，解精度低，容易陷入局部最优的问题，对FWA算法分别采用混沌反向学习和柯西分布进行初始化，阀值优化非烟花半径，鲸鱼算法进行个体选择，最后，仿真实验说明本文算法在完成时间和成本消耗方面都具有较好的效果。

关键词：移动云计算；任务调度；FWA-WOA

引言

随着5G技术，云计算的发展，移动云计算成为当前应用较为广泛的研究热点，如何降低任务完成时间和产生的能耗是移动云计算任务调度主要的研究方向。学者进行了广泛的研究，文献[1]提出一种多目标任务调度进化算法MTSEA.建立了截止时间、预算及能量约束下的任务调度多目标优化模型，模型引入执行跨度、执行代价及执行能耗三目标最优化；设计了一种进化算法对冲突三目标最优化进行求解，仿真实验说明该算法调度解的收敛性及解空间距离和分布上是更优的；文献[2]提出一种基于启发式自适应模拟退火遗传算法（Heuristic Adaptive Simulated Annealing Genetic Algorithm，HASAGA）的资源管理策略求解算法，仿真结果表明，所提算法可求得近似最优资源管理策略且具有收敛速度快和不易陷入局部最优解的优点；文献[3]提出了一种移动云计算的能效任务调度算法MC2ETS（Energy-efficient Tasks Scheduling of Mobile Cloud Computing），仿真实验说明算法在多数情况下可以在调度时间指标与移动设备能耗间实现均衡优化。

1.移动云计算任务调度简述

在移动云计算环境中，用户请求的服务资源种类众多，需要考虑的服务质量因素也非常多，比如减少服务过程中所产生的能耗，加快任务执行速度等等。而各个终端用户对于不同需求中的每个指标的要求也不一样.因此，移动云计算任务调度模型主要是寻找一种合理的调度方案，将任务按照服务需求分配到资源节点集上执行，提高用户的服务质量满意度.移动云计算中首先需要考虑的是时间因素，提交的任务在规定的时间内快速完成是最好的结果；同时受限于移动设备自身能耗的影响，任务调度中的能耗问题对于衡量调度算法性能优劣也十分重要，因此如何在移动云计算中满足时间和能耗的要求是衡量云计算任务调度效果好坏的关键.

2.基于FWA-WOA算法

针对FWA算法自身过早收敛，解精度低，容易陷入局部最优的问题，本节对FWA算法在初始化，烟花半径和选择策略方面进行改进，将得到的IFWA-ABC算法并用于云计算资源调度

2.1混沌反向学习和柯西分布优化初始位置

FWA算法的初始解通常采用随机方式，这种随机处理方法在一定程度上对最优解的产生具有一定的影响，假设两者极端的情况，一种是产生的随机解距离最优解很近的时候，算法的收敛速度就会很快，另一种是产生的随机解距离很远或者反向的时候，导致算法需要消耗更长的时间才能够完成收敛。针对这种问题，本文引入了混沌反向学习概念来初始化解，即在当前解的同时求得反向解，通过对两者的对比，从中选择较好的一个解，这样可以在很大程度上提高算法的执行效率。根据FWA算法中的烟花个体的位置，给出Logistic映射产生混沌状态下的初始值，如公式（1）所示，计算其位置的反向解如公式（2）所示。式中，和是搜索空间中的候选解的最大值和最小值。

因此，将反向后的解与原来解组成一个群体，按照适应度值的由高到低进行排列，选择前一半的值作为种群的初始化的解。

在标准的FWA算法中，新一代的烟花个体散落在父代个体周围，产生的解会随着迭代次数的增加而不断的减小，将搜索的范围逐渐搜索到父代个体附近，这样使得算法容易陷入局部最优，而降低求出全局最优解的效率，采用柯西分布生成的随机数能够使得搜索区域更加广泛，因此能够提高算法的全局搜索能力，因此采用如下的密度函数进行计算。

式中，表示迭代次数，表示最大迭代次数，和分别表示柯西分布中的尺度参数的初始值和最大值。

2.2设定阀值优化非核心烟花半径

根据FWA算法得知，当烟花在爆炸的时候，会在它的周围一定的区域中产生大量的火花，火花的范围就是烟花的半径，核心烟花是烟花种群中的适应度值最小的烟花个体，而非核心烟花半径如公式（4）所示，很显然这种方式会发现适应度值最小的烟花的半径非常小，几乎接近0，因此浪费了资源。为了避免这种情况的发生，设定最小半径阀值，其表现形式如下：

阀值的设定并不是一个固定的值，这是因为算法在迭代过程中会产生的动态的效果，因此采用非线性递减方式。

式中，为最大函数评估次数，为当前函数评估次数，和分别表示最初的爆炸半径和最终半径数值。

2.3权重算子优化核心烟花半径

核心烟花的爆炸半径进行一定的调整才能使得算法的性能得到改进，显然这种改进存在的一定的问题，其主要表现在主要来自局部搜索能力的提高，烟花个体之间相互并没有交流，提出的核心烟花半径计算过于简单，仅仅考虑缩放而直接忽略了搜索过程，容易造成算法陷入局部最优。使得算法过早的收敛，导致算法难以跳出多峰值的时候局部最优解的束缚，本文在此基础上采用粒子群算法中的权重算子，其主要目的是利用当前中的最好烟花位置和历史最优信息，从而避免了陷入局部最优。表达如下：

式中，表示当前位置中最好的烟花位置，为权重因子控制先产生的火花与当前最好烟花位置之间的距离，使得烟花个体具有向种群中最优秀的个体学习的能力从而向群体内历史最优点靠近。是位置参数和尺度参数为的柯西分布，当位置参数小的时候，有利于进行局部搜索，使用表示位置参数小的时候柯西分布，当位置参数大的时候，有利于进行全局搜索，使用表示参数大的柯西分布。

2.4基于WOA算法个体策略

在FWA算法中，每一次迭代过程中优秀烟花个体都能传递到下一代种群中，FWA算法主要是选择适应度值最小的个体，而剩余个体都采用随机状态，显然，这种挑选的策略存在一定的弊端，虽然在某次迭代中，按照适应度值小的选择个体，但从全局来看不一定能够保证选中的个体就一定比剩余随机状态的个体要好，同时剩余的个体采用随机的状态，从整体上不利于算法全局最优解的诞生，针对这个情况，本文引入鲸鱼算法，鲸鱼算法具有简单易实现、控制参数少、鲁棒性强以及全局搜索能力较强等特点，通过每个鲸鱼个体优化作用最终找到最优的个体。

（1）初始化，统计FWA中的种群中所有个体，并计算每个个体的适应度值，产生可行解为：

（2）记录到目前为止的最优值，借助DE算法的思想，新的鲸鱼个体的螺旋更新的公式为：

式中，为随机选择的目标，，都是随机选择的整数，是当前全局最优解，显然，借助差分算法的影响，公式（9）能够有效的保持种群的多样性，公式（10）可以提高收敛速度，增强算法的开发能力，为了能够将两者进行有效的结果，采用公式（11）来控制新的蜜源位置。

（3）鲸鱼个体寻找觅食的阶段

座头鲸通过控制向量游走获取食物，当的时候，座头鲸个体向着参考座头鲸的位置靠近，鲸鱼个体朝着随机选取的座头鲸更新位置，这种方式保证了座头鲸个体能够进行全局搜索，获得全局最优解，其数学模型表示如下：

式中，是随机获得的参考座头鲸的位置向量。

3.基于FWA-WOA的移动云计算任务调度

采用改进的FWA-WOA算法用于移动云计算任务调度中的关键是目标函数的设计.该函数以最小任务完成时间和最低系统设备能耗为优化目标，合理的为各个移动设备分配任务量，缩短任务执行时间，提高系统资源利用率.执行节点一般由大量具有移动特性的终端设备组成，在移动云计算进行任务分配的时候，必须考虑这些设备自身的计算存储能力和电量等约束因素给任务调度带来的影响。设定用户在提交任务被划分为个可并行化处理的子任务，设表示任务集合，各个子任务之间没有相互关系均可以并行执行。

3.1时间适应度函数

移动云计算环境中执行任务的移动资源具有动态性和异构性，同样的任务在不同的移动设备上完成时间可能是不相同的，因为这与设备自身的计算能力有关，一般来说，对于分配给某一个设备的任务，执行时间取决于任务的长度和设备的CPU处理能力（MIPS），因此表达式为：

式中，表示移动设备CPU使用率，考虑到移动设备CPU在空闲状态下具有一定的使用率导致所有任务实际执行时间都会出现不同程度的延长，特别是移动设备CPU使用率较大的时候任务执行时间会显著的增加，所以设定主要是为了考虑移动设备CPU的可用率给计算任务时间带来的影响.

任务完成时间除了和移动设备自身计算能力有关，还与移动设备具备的网络传输能力有关，这是因为不同的网络带宽会导致任务映射到移动设备的时间以及从设备上结果返回的时间不同.对于分配给移动设备的任务，任务映射时间和返回时间分别是和，主要是由输入数据大小和以及设备的网络带宽决定，因此分别为

3.2能耗适应度函数

在传统的云计算任务调度算法中，对于能耗指标都是以开销最低为最优目的，但在移动云计算环境中，移动设备的有限电量是不可忽视的约束条件.移动设备属于电量有限的计算资源，任务分配的过程必须考虑其产生的能耗，所以电量首先满足自身必要软件功能的正常运行，其次剩余的电量用于执行云计算调度任务.根据移动设备的CPU，内存，WiFi等硬件模块的能耗，因此移动设备的能耗模型为：

式中，表示测试样本中的第个样本的第个硬件设备产生的功耗，表示第个样本涉及的第个硬件设备的使用率（CPU使用率或者内存使用率），表示第个硬件设备使用率的相关耗电系数.计算机的能耗与CPU的利用率是线性关系，表达式为：

式中，表示CPU能耗，表示使用率，和分别表示固定系数.

借助以上的模型以及移动云计算中终端的特点，消耗电量主要来自CPU和内存模块，因此移动设备执行任务的产生的能耗如下：

式中，和分别表示CPU使用率和内存使用率，和分别表示CPU和内存模块的电量消耗系数，为任务在设备上执行时间.

移动设备与代理服务器之间的数据传输也会消耗部分能量，由于移动设备采用的不同的连接方式，因此设备功耗也不相同.移动设备中由于数据传输引起的能耗如下：

式中，和分别表示任务的输入数据大小和输出数据大小，为网络传输模块的功耗系数，为任务映射时间，为结果返回时间.

3.3FWA-WOA算法适应度函数

本文将完成时间和能耗作为任务目标调度函数，将FWA个体对应每一个任务调度方案，任务目标调度函数作为FWA-WOA的适应度函数，依靠FWA-WOA算法自身的良好性能，通过适应度函数比较获得最优的鸟群个体，即获得最优的调度方案。但由于时间适应度函数和能耗适应度函数两者取值范围差异较大，采用归一化的方法进行调整，使得调整后的函数值在[0，1]范围内.设分别表示和，和分别表示函数的最大值和最小值，调整后的适应度函数分别表示和，表达如下：

式中，和分别为调整后的任务完成时间函数和系统设备能耗函数.和分别为权重且，因此求出是FWA-WOA算法的目标。

4.仿真实验

为了更好的说明本文算法在移动云计算中的任务调度效果，我们选择了将本文算法与FWA和WOA算法进行对比。设定三种算法的迭代次数为1000，种群初始化规模为20，任务数量设定为[100，500]。三种算法的参数按照各自算法设定，以任务调度时间和完成的能耗进行实验对比。图1显示了三种算法完成时间的对比情况，从图中发现随着任务数量的逐渐增多，三种算法的完成时间逐渐变大，但是本文提出的FWA-WOA算法具有明显的效果。图2显示了三种算法的成本消耗的对比情况，从图中发现随着任务数量的逐渐增多，三种算法的消耗成本也在逐渐增大，但是本文算法的成本消耗比较低。通过两个图的对比我们发现了本文算法能够更好的适应移动云计算任务调度。

5.结束语

针对移动云计算下任务调度存在消耗时间长，成本消耗高等缺点，提出了基于FWA-WOA融合的移动云计算任务调度策略，通过种群初始化，烟花半径，个体选择方面的优化使得算法的性能得到了提升，仿真实验表明该算法在任务调度和时间消耗方面具有较好的效果。

参考文献：

[1]张小庆，安春玲，胡亚捷.移动云计算多目标任务调度进化算法[J].微电子学与计算机，2020，37（10）：79-86.

[2]金小敏，滑文强.移动云计算中面向能耗优化的资源管理[J].计算机科学，2020，47（06）：247-251.

[3]叶符明，李雯婷，王颖.MC2ETS：移动云计算中一种能效任务调度算法[J].计算机科学，2019，46（06）：135-142.

课题来源：浙江省高等学校国内访问工程师校企合作项目。

（项目编号：FG2021179，项目名称：基于FWA-WOA融合的移动云计算下的任务调度的研究。）。

作者简介：

王大伟（1982.2-）男，硕士，汉族，研究方向为云计算，算法设计。