Cloud Computing Task Scheduling Strategy Based on Improved Firefly Algorithm

ZHU Li-hua; ZHU Ling-ling

doi:10.13718/j.cnki.xsxb.2021.03.002

Aiming at the problem of imbalanced resource utilization caused by low task scheduling efficiency in cloud computing, a new cloud computing task scheduling strategy based on improved firefly algorithm has beenproposed. This strategy firstly constructs the constraints of the optimization of cloud computing resource load balance, and takes the minimum user task completion time as the objective function of resource optimization; secondly, optimizes the resource search path through the improved firefly algorithm, optimizes the task load balance among multiple virtual machines in the cloud server, and shortens the user task completion by improving the response efficiency of the cloud server The purpose of the total time. Experimental results show that compared with other algorithms, the proposed strategy has obvious advantages in the completion time of cloud computing tasks, can effectively solve the problem of load imbalance in the server, and improve the response efficiency of user requests.

HTML

云计算是目前计算机领域内技术发展的焦点之一，它是将传统的分布式计算、并行计算及网格计算融为一体的数据服务系统^[1]. 美国国家标准与技术研究院定义：云计算是一种按使用量付费的模式，这种模式为用户提供低成本、可伸缩、高可靠性的计算资源及服务^[2-3]. 目前，按照云计算可提供的服务种类，划分为软件即服务(Software as a service, SaaS)、平台即服务(Platform as a Service, PaaS)、基础设施即服务(Infrastructure as a Service, IaaS)^[4]. 在云环境中，计算资源服务质量的好坏是衡量云计算效果的一个重要指标，因此如何有效地降低云计算中的负载均衡，提升计算资源利用率是当前研究的热点问题.

负载均衡是指将任务分摊到多个操作单元上执行的过程，避免产生系统瓶颈或者资源浪费^[5]. 迄今为止，国内外研究学者已经开发出许多传统算法、博弈论算法和启发式算法来解决任务负载优化问题. 经典的Min-Min与Max-Min算法^[6]通过优先安排计算量过小或过大的任务方式缩短总任务完成时间，但是这类算法的负载均衡较差. Wang等^[7]利用动态规划思想将任务与服务器的匹配作为多阶段决策组合，通过优化任务分配方案来减少任务的完成时间，但是该算法导致了大量开销. 目前，研究学者大多数采用启发式算法来解决云计算任务调度这一多项式复杂程度的非确定性问题(Non-deterministic Polynomial, NP问题). 启发式算法包括蚁群算法^[8]、粒子群算法^[9]和乌鸦搜索算法^[10]以及相关的改进融合算法. 这类方法具备操作简单、鲁棒性强和扩充性好的特点，能够有效地缩短任务完成时间，解决资源负载均衡问题. 萤火虫算法是根据萤火虫觅食和求偶行为提出的一种启发式算法，具有参数调整少、寻优能力强和简单易实现的特点，广泛应用于多个领域. Ahmed等^[11]通过引入萤火虫算法对云计算中的子任务进行调度，实现了最短的延迟时间. 李成辉等^[12]提出了一种改进萤火虫算法的任务调度方法，通过真实物理反弹理论控制搜索区域的萤火虫，提高全局最优概率. 但是上述方法采用的萤火虫算法收敛速度慢，寻优精度不高，容易陷入局部最优，因此在任务调度过程中效果不佳.

针对多个云服务器虚拟机之间由于任务调度效率低引起的负载不平衡问题，本文提出了一种改进的萤火虫优化算法，可以在大规模场景中实现虚拟机之间的动态负载均衡，能够在云服务器池中搜索并找到最佳和最近的云服务器，有效解决服务器中的负载不均衡问题，降低用户请求的响应时间.

1. 标准萤火虫算法

萤火虫算法(Firefly Algorithm, FA)是一种群智能优化算法^[13], 该算法根据自然界中萤火虫个体发光确定自身位置和吸引同伴的启发而提出. 在提出随机优化萤火虫算法时假定：单个萤火虫对其他所有萤火虫都存在吸引力，不存在同性排斥的现象；萤火虫吸引力的大小与自身的亮度成正比，与萤火虫间的相对距离成反比，亮度高的萤火虫吸引力大，会引诱低亮度萤火虫向其靠拢.

萤火虫算法中的两个关键要素是亮度和吸引度. 萤火虫的亮度和吸引度随着萤火虫i与萤火虫j之间的距离变化而变化. 因此，距离萤火虫r处的相对亮度可表示为

其中，I₀表示萤火虫自身最大亮度，γ是光吸收因子，k是指数因子，一般取2.

吸引度β可被定义为

其中，β₀表示最大吸引度，r_ij表示萤火虫i, j之间的欧式距离.

萤火虫i向更加明亮的萤火虫j移动时，移动位置可以表示为

其中，s_i, s_j表示萤火虫i, j的解空间位置，α表示移动步长，ξ_i是萤火虫i的随机因子，服从[0, 1]区间的均匀分布. 式(3)右侧第一项表示萤火虫的当前位置，第二项表示受其他萤火虫吸引而产生的位置变化量，该项体现了算法的全局寻优能力，第三项表示萤火虫在局部的随机搜索移动量，体现了算法的局部寻优能力.

2. 基于改进萤火虫算法的任务调度

标准萤火虫算法是以个体的亮度作为移动依据，向单个更亮萤火虫移动的策略保证了算法可以收敛至一个小的区域. 但是，这种策略收敛速度慢，寻优精度不高，而且容易陷入局部最优的困境. 因此，本文在标准萤火虫算法的基础上提出了改进算法，通过优化资源搜索路径，提高云计算任务完成速度，达到缩短任务完成总时间和保持云服务器之间负载动态平衡的目的.

2.1. 改进的萤火虫算法

假定将萤火虫中的个体分为两类：产生最强烈亮度的萤火虫定义为占优萤火虫，发光较少的萤火虫定义为弱萤火虫. 则萤火虫群体F中存在m个弱萤火虫{f_i|i=1, 2, …, m}和n个占优萤火虫{Df_j|j=1, 2, …, n}. 占优萤火虫通过发出强烈的亮光吸引其他弱萤火虫. 在一个特定的区域，所有的弱萤火虫都会被其中的占优萤火虫吸引，从而产生更大的亮度值(Brightness Value, BV), 进而吸引更远区域的弱萤火虫. 假设弱萤火虫以两种搜索模式飞向占优萤火虫：①从较低亮度处飞离：该值由最后搜索边界(Last Search Border, LSB)表示. ②朝亮度高的方向飞行：该值由新搜索边界(new search border, NSB)表示.

萤火虫通过一条最佳路径寻找伙伴，并采用最短飞行距离、最小能量消耗的思路来优化占优萤火虫群的平衡问题，避免长距离飞行时的资源浪费. 欧几里德距离计算法适用于萤火虫飞行路径的搜索.

通过上述分析，占优萤火虫算法是指通过建立两种搜索路径，使得弱萤火虫以消耗尾部能量最少的方式找到占优萤火虫的方法. 基于这种认知，本文将占优萤火虫搜索算法应用于云计算环境中，解决云服务器中各虚拟机(Virtual Machine, VM)之间的负载不均衡问题，降低迁移时间和云数据中心之间的响应时间.

2.2. 负载均衡优化模型

云服务提供商为最终用户提供最佳的低能耗策略，以便使用有效的云服务水平协议(Service Level Agreement, SLA)访问云中的IaaS服务. 每个云用户在与相邻云服务器通信时应具有SLA, 以确保灵活且可靠地共享文件.

在云计算中，云用户不断向可用的云服务器资源发送请求. 请求映射到预期资源是一个繁琐的过程，用户请求和云计算资源不是一一对应的映射关系. 在本文所提出的技术中，引入虚拟机的云服务器池概念用以将每个用户请求映射到云服务器. 云用户请求可以通过虚拟机随机地提供给云中的任何云服务器. 云服务器选择依赖于基本的云管理策略，这些策略取决于每个云服务器上的实际负载. 任何非抢占式系统都采用了调度策略，如Round Robin策略和First-Come-First-Served策略^[14]. 通过这些策略发现每个云服务器虚拟机(Cloud Server Virtual Machine, CSVM)上的负载都不同. 为了使每个CSVM负载平衡，需要动态负载平衡策略.

通过减少云服务器的完成时间，使得每个云服务器和整个云负载平衡的性能都获得提高，同时增强了用户满意度. 假定在云计算系统中，存在m个用户提交任务D={D₁, D₂, …, D_m}和虚拟机VM={VM₁, VM₂, …VM_m}, n个云服务器CS={CS₁, CS₂, …, CS_n}, 则云计算资源优化问题可以表述为

其中，M_{t, vm}代表任务与虚拟机之间的映射关系，M_{vm, cs}代表虚拟机和云服务器间的映射关系.

假设任务T_i被映射到虚拟机VM_j上，而VM_j的任务通过调度在CS_k云服务器上执行，则任务T_i在服务器CS_k执行的最早完成时间为

式(8)中，ST(CS_k)表示云服务器CS_k开始执行任务的时间，ET(T_iM_{t, vm}, CS_k)表示任务T_i经过虚拟机上传至服务器CS_k后的预期执行时间.

云服务器CS_k上所有任务完成的总时间为

其中，c_ik=1代表任务D_i被调度到云服务器CS_k执行，c_ik=0代表任务T_i未被调度到云服务器CS_k执行，即

全部任务D={D₁, D₂, …, D_m}总的完成时间可以表示为

云计算资源负载平衡的优化问题就是尽可能降低用户提交任务的完成时间. 本文的优化目标函数定义为

改进的萤火虫算法可以应用于云计算资源负载平衡策略. 在一群萤火虫中，总会有几个占优萤火虫和许多弱萤火虫. 该方法假设占优萤火虫代表云服务器，而弱萤火虫代表云用户. 当云服务器占用大量负载(用户请求)时，就需要以这种方式进行平衡，以便将用户请求传输到其他某个云服务器上，保证尽快完成任务. 如果萤火虫在搜索期间发现占优萤火虫已经被许多其他弱萤火虫重复占据，那么则会通过将过多的弱萤火虫传递给下一个占优萤火虫来平衡负载. 根据此算法，当云用户请求增加到云服务器阈值时，用户将自动转移到下一个云服务器. 此外，弱萤火虫朝占优萤火虫飞行的路径表示附近云服务器可提供的动态负载均衡.

改进萤火虫算法的设计是基于云环境中VM之间的动态负载均衡策略. 对于云负载平衡策略之类的大规模场景，这种改进的萤火虫算法能够在云服务器池中搜索和找出最佳、最近的云服务器，从而实现多个云服务器VM之间的最佳负载平衡. 这种设计旨在更简单，更有效地解决云计算环境中复杂的任务负载平衡问题. 云服务器的路径搜索可以通过应用本文提出的算法来进行优化，具体流程如表 1伪码所示.

4. 结语

本文提出了一种基于改进萤火虫算法的虚拟机任务调度策略，用于改善当前云计算中任务调度效率低的问题，提高云服务器间负载均衡的性能. 该算法以缩短传输路径、优化云计算资源负载平衡为出发点，通过改进的萤火虫算法优化资源搜索路径，减少云计算任务的响应时间，达到缩短任务完成总时间的目的，最终结果使得云计算资源利用率得以提高，云计算资源负载平衡得以优化. 仿真实验结果表明，本文算法可以有效地对云计算资源进行调度，任务完成时间明显优于其他算法.

Figure (3) Table (1) Reference (14)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	PANDA S K, JANA P K. An Energy-efficient Task Scheduling Algorithm for Heterogeneous Cloud Computing Systems[J]. Cluster Computing, 2019, 22(2): 509-527. doi: 10.1007/s10586-018-2858-8 CrossRef Google Scholar
[2]	ELAZIZ M A, XIONG S W, JAYASENA K P N, et al. Task Scheduling in Cloud Computing Based on Hybrid Moth Search Algorithm and Differential Evolution[J]. Knowledge-Based Systems, 2019, 169: 39-52. doi: 10.1016/j.knosys.2019.01.023 CrossRef Google Scholar
[3]	DE MATOS J G, DE M MARQUES C K, LIBERALINO C H P. Genetic and Static Algorithm for Task Scheduling in Cloud Computing[J]. International Journal of Cloud Computing, 2019, 8(1): 1. doi: 10.1504/IJCC.2019.097891 CrossRef Google Scholar
[4]	王磊, 赵晓永. 基于区块链机制的云计算环境下服务组合策略的研究[J]. 计算机应用研究, 2019, 36(1): 81-86, 90. Google Scholar
[5]	ARUL XAVIER V M, ANNADURAI S. Chaotic Social Spider Algorithm for Load Balance Aware Task Scheduling in Cloud Computing[J]. Cluster Computing, 2019, 22(1): 287-297. doi: 10.1007/s10586-018-1823-x CrossRef Google Scholar
[6]	LIANG B, DONG X S, WANG Y F, et al. A Low-power Task Scheduling Algorithm for Heterogeneous Cloud Computing[J]. The Journal of Supercomputing, 2020, 76(9): 7290-7314. doi: 10.1007/s11227-020-03163-8 CrossRef Google Scholar
[7]	WANG P P, DONG K K, LIU H R, et al. Research on Task Allocation and Resource Scheduling Method in Cloud Environment[M]//Advances in Intelligent Systems and Computing. Cham: Springer International Publishing, 2019. Google Scholar
[8]	SELVAKUMAR A, GUNASEKARAN G. A Novel Approach of Load Balancing and Task Scheduling Using Ant Colony Optimization Algorithm[J]. International Journal of Software Innovation, 2019, 7(2): 9-20. doi: 10.4018/IJSI.2019040102 CrossRef Google Scholar
[9]	KUMAR A M S, PARTHIBAN K, SHANKAR S S. An Efficient Task Scheduling in a Cloud Computing Environment Using Hybrid Genetic Algorithm-Particle Swarm Optimization(GA-PSO)algorithm[C]//2019 International Conference on Intelligent Sustainable Systems(ICISS). Tokyo: IEEE, 2019. Google Scholar
[10]	PRASANNA KUMAR K R, KOUSALYA K. Amelioration of Task Scheduling in Cloud Computing Using Crow Search Algorithm[J]. Neural Computing and Applications, 2020, 32(10): 5901-5907. doi: 10.1007/s00521-019-04067-2 CrossRef Google Scholar
[11]	AHMED S I, IBRAHIM A O, ABDUTTALIB M S, et al. Task Scheduling for Cloud Computing Based on Firefly Algorithm[J]. Journal of Physics: Conference Series, 2019, 1294: 042004. doi: 10.1088/1742-6596/1294/4/042004 CrossRef Google Scholar
[12]	李成辉, 李仁旺, 杨强光, 等. 基于改进萤火虫算法的云计算任务调度算法[J]. 浙江理工大学学报(自然科学版), 2019, 36(3): 354-359. Google Scholar
[13]	LANGARI R K, SARDAR S, AMIN MOUSAVI S A, et al. Combined Fuzzy Clustering and Firefly Algorithm for Privacy Preserving in Social Networks[J]. Expert Systems With Applications, 2020, 141: 112968. doi: 10.1016/j.eswa.2019.112968 CrossRef Google Scholar
[14]	MASHUQUR RAHMAN MAZUMDER A K M, ASLAM UDDIN K M, ARBE N, et al. Dynamic Task Scheduling Algorithms in Cloud Computing[C]//2019 3rd International conference on Electronics, Communication and Aerospace Technology(ICECA). Coimbatore: IEEE, 2019. Google Scholar

Message Board

Cloud Computing Task Scheduling Strategy Based on Improved Firefly Algorithm

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors