基于布谷鸟搜索算法的云计算资源负载分配研究

摘 要： 資源负载分配是云计算领域的重要研究方向，当前云计算资源负载分配算法难以得到最合理的分配方案，导致部分云计算资源上存在负载过重或者空负载现象，云计算资源利用率低。为了解决当前云计算资源负载分配算法存在的局限性，提出基于布谷鸟搜索算法的云计算资源负载分配算法。首先分析当前云计算资源负载分配算法的研究进展，建立云计算资源负载分配模型，然后利用具有模拟鸟群群集行为和特征的布谷鸟搜索算法对其进行求解，根据最优鸟巢位置得到云计算资源负载分配方案，最后采用CloudSim软件实现了云计算资源负载分配仿真测试实验。结果表明，相当于当前其它云计算资源负载分配算法，布谷鸟搜索算法的求解效率得到了明显提升，求解精度也得到了相应的改善，可以保证云计算资源上分配的负载十分均衡，提高了云计算资源负载利用率，降低了云计算系统的运行成本。

关键词： 云计算资源; 负载分配; 鸟群群集行为; 求解效率; 最合理分配方案

中图分类号： TP311      文献标志码： A

Research on Cloud Computing Resource Load Allocation

Based on Cuckoo Search Algorithms

LI Bo

（Institute of Intelligent Manufacturing， Guangdong Nanfang Institute of Technology， Jiangmen 529000）

Abstract： Resource load allocation is an important research direction in the field of cloud computing. Current cloud computing resource load allocation algorithms are difficult to obtain the most reasonable allocation scheme， which results in overload or empty load on some cloud computing resources and low utilization rate of cloud computing resources. In order to solve the limitations of current cloud computing resource load allocation algorithm， a cloud computing resource load allocation algorithm based on Cuckoo search algorithm is proposed. Firstly， the current research progress of cloud computing resource load allocation algorithms is analyzed， and model of cloud computing resource load allocation is established. Then， the Cuckoo search algorithm with simulated bird swarm behavior and characteristics is used to solve the problem. According to the optimal nest location， the cloud computing resource load allocation scheme is obtained. Finally， CloudSim software is used to realize simulation test of cloud computing resource load allocation. The results show that the efficiency and accuracy of Cuckoo search algorithm have been improved significantly， which can ensure that the load allocated on cloud computing resources is very balanced. It improves the load utilization of cloud computing resources and reduces the cloud computing system operation cost compared with other cloud computing resource load allocation algorithms.

Key words： Cloud computing resources; Load allocation; Bird clustering behavior; Solution efficiency; Optimal allocation scheme

0 引言

随着互联网技术的发展，网络用户数量急剧增多，数据呈现爆炸性增长，当前已经进入了“大数据时代”，传统计算机系统无法满足大数据处理的要求，“云计算技术”应运而生。云计算技术包含许多技术，如：网格计算、虚拟化计算、分布式计算等，将不同地理位置的资源连接成一个虚拟化资源池，用户可以根据自己的需求花费得到相应的服务[1]。在云计算技术的实际应用中，一些问题不断出现，如云计算庞大的资源规模，而用户需求各异，如何提高云计算资源率，更好为客户服务是云计算资源负载分配必须面对的问题，因此设计性能更好的云计算资源负载分配算法是人们一直努力的方向[2，3]。

最初，云計算资源负载分配算法沿用网络计算资源分配算法，如Min-min算法，以服务费用最小为目标，将负载分配到一些性能较高的云计算资源上，由于网络计算资源和云计算资源存在一定的差别，如：约束条件多、优化目标多样性，因此Min-min算法得到的云计算资源负载分配方案并非最优，从而造成用户需求得不到满足，云计算资源负载不均衡等问题[4]。随后，许多学者投身于云计算资源负载分配问题的研究中，涌现出了许多云计算资源负载分配算法。当前云计算资源负载分配算法可以划为2类：静态算法和动态算法，静态算法主要有：轮询法、加权轮转调度算法，它们以云计算资源负载均衡为目标，采用先来先服务的规则，将负载分配到不同的云计算资源上，该类算法的工作过程十分简单，但是它们假设云计算资源上负载呈现一种静态变化特点，这与实际情况不相符合，因此局限性十分明显[5-7]。动态算法可以适应云计算资源上负载变化的特点，成为当前一个主要的研究方向，其将云计算资源负载分配问题看作为一个含有复杂约束条件的组合优化问题，然后通过启发式算法来解决该问题，如：基于粒子群优化算法的云计算资源负载分配算法、基于各种改进粒子群优化算法的云计算资源负载分配算法，这些动态算法可以得到较好的云计算资源负载分配方案[8-10]。在实际应用中，由于云计算资源负载分配问题是一个典型NP-hard问题，粒子群优化算法存在易出现早熟现象、时间复杂度过髙，获得局部最优的云计算资源负载分配方案概率高等缺陷[11]。

针对当前云计算资源负载分配过程中存在的负载严重不均衡、云计算资源利用率低等难题，提出基于布谷鸟搜索算法的云计算资源负载分配算法，并采用具体云计算资源负载分配仿真测试实验分析了其性能。结果表明，布谷鸟搜索算法的求解效率高，可以快速得到云计算资源负载分配最优方案，使云计算资源上分配负载均衡，而且性能要明显优于其它云计算资源负载分配算法，具有更好的实际应用价值。

1 布谷鸟搜索算法

布谷鸟将自己蛋放入其它鸟类的巢中，让它们帮助其哺育幼鸟，是一种典型寄生育雏行为。布谷鸟首先会观察其它鸟类的鸟巢，通过Lévy flights选择一个鸟巢，然后将自己蛋放在该鸟巢中，因此根据布谷鸟的寄生育雏行为提出了布谷鸟搜索算法[12]。为了模拟布谷鸟的寄生育雏行为，布谷鸟搜索算法设定了3个理想状态，具体如下：

（1） 布谷鸟1次只能生1个蛋，随机选择其它鸟类的鸟巢进行孵化;

（2） 最好的鸟巢会被保存到下一代;

（3） 鸟巢数量固定不变，鸟巢主发现布谷鸟鸟蛋概率为pa固定不变。

对于一个待解决的问题，鸟巢位置为一个d 维向量X=（x1，x2，…，xd），其代表问题的一个可行解，鸟巢位置的好坏由适应度来评价，布谷鸟寻找适合自己的鸟巢方式为式（1）。Xt+1i=Xti+α⊕Levy（λ） i=1，2，…，n

（1）式中，t表示迭代次数，⊕表示点积运算;α表示布谷鸟搜索步长，Levy（λ）表示Lévy 分布，其满足条件为式（2）。Levy（λ）～t-λ， 1<λ<3

（2）式中，λ表示Lévy分布的步长参数。

谷鸟搜索步长的变化方式为式（3）。a=a0（xti-xbest）

（3）式中，xbest表示当前最优解，即最优的布谷鸟巢位置。

测评通过Lévy flights方式更新鸟巢位置后，根据Pa丢弃一些新鸟巢位置，并采用如下方式对鸟巢位置进行更新为式（4）。Xt+1i=Xti+rand·（Xtk-Xtj） i=1，2，…，n

（4）式中，Xtk和Xtj表示两个鸟巢，rand表示缩放因子，是一个（0 1）区间的随机数。

布谷鸟搜索算法的工作流程如图1所示。

3 基于布谷鸟搜索算法的云计算资源负载分配设计3.1 云计算的体系结构

云计算的系统结构如图2所示。

从图2可以看出，云计算的系统结构包括：云应用、用户层中间件、核心中间件、系统级，具体描述如下：

（1） 云应用，该层由云提供商提供，包括了直接对终端用户可用的应用。

（2） 用户层中间件，该层包括软件结构，是用户接口。

（3） 核心中间件，该层用于支持管理用户级应用服务的工作环境。

（4） 系统级，该层包括大量的物理资源，用于支持数据中心。

3.2 云计算资源负载分配的模型

云计算资源负载分配是指在满足一定的约束条件下，将待处理的一些负载分配到多个云计算资源上，并在云计算资源上执行负载。最优的云计算资源负载分配方案应该满足：（1） 满足用户对负载完成的时间;（2） 根据负载和云计算资源特点，将负载分配到最合理的云计算资源上执行，这两点相互制约，因为完成负载的时间越短，需要的云计算资源会越多，整个云计算系统的功耗相应增加。设负载和云计算资源的集合分别为：X={x1，x2，…，tn}和Y={y1，y2，…，ym}，第i个负载在第j个云计算资源上的预期执行时间为Texe（i，j），则有式（5）。Texe（i，j）=xlon（i）/Ycal（j）

（5）式中，xlon（i）表示i个负载的大小，Ycal（j）表示第j个云计算资源的执行速度。

第j个云计算资源完成第i个负载的所花费的总时间为式（6）。Tsum（i，j）=Texe（i，j）+Tdur（i，j）

（6）式中，Tdur（i，j）表示第i个负载传输到第j个云计算资源需要的时间。

云计算资源能够采用并行运行模式，云计算系统处理所有负载的时间为式（7）。Tcos=max∑nj=1∑mi=1Tsum（i，j）

（7）  执行完负载的功耗计算公式为式（8）。Ccos=∑nj=1 ∑mi=1Texe（i，j）×Cexe+Tdur（i，j）×Cdur

（8）式中，Cexe和Cdur分別表示云计算资源执行和和传输的功耗。

3.3 基于布谷鸟搜索算法的云计算负载分配步骤

（1） 根据云计算系统的资源和负载建立云计算资源负载分配的模型。

（2） 初始化布谷鸟搜索算法的鸟巢位置，每一个布谷鸟的鸟巢位置表示一种云计算资源负载分配可行分配方案。

（3） 计算每一个鸟巢位置的适应度值，本文选择执行完负载的功耗和，云计算系统处理所有负载的时间作为适应度函数，并保留最优鸟巢位置。

（4） 迭代次数增加。

（5） 随机产生1个数，并与巢主发现布谷鸟鸟蛋概率进行比较，如该数大于巢主发现布谷鸟鸟蛋概率，那么对鸟巢位置进行更新操作，不然，鸟巢位置不变，从而产生新的一组鸟巢位置。

（6） 计算新的一组鸟巢位置的适应度值，保留适应度较优的鸟巢位置。

（7） 如果迭代次数达到最大迭代次数，就执行步骤（8），不然返回步骤（4）。

（8） 根据最优鸟巢位置得到云计算资源负载分配方案。

4 仿真模拟测试

4.1 云计算系统的相关设置

Cloudsim是通过java语言编写的云计算环境的工具库，采用作为云计算资源负载分配的仿真软件，云计算资源负载分配程序通过java语言编程实现。负载数量为30～350，云计算资源数量为：40个，布谷鸟搜索算法参数设置如表1所示。

选择文献[11]的云计算资源负载分配算法进行对比实验。

4.2 结果与分析

不同负载数量的条件下，两种云计算资源负载分配算法找到最优方案的迭代次数变化曲线如图3所示。

从图3可以看出，随着负载数量的增加，迭代次数不断的增加，当负载数量较小时，两种算法的迭代次数相差不大，但当负载数量比较大时，布谷鸟搜索算法的迭代次数少于文献[11]算法，从而加快了找到云计算资源负载分配最优方案的速度，验证了布谷鸟搜索算法的有效性。

不同负载数量条件下，两种云计算资源负载分配算法的功耗变化曲线如图4所示。

从图4可以看出，随着负载数量增加，布谷鸟搜索算法的功耗增长幅度小，而文献[11]算法的功耗增长幅度较大，说明布谷鸟搜索算法找到更优的云计算资源负载分配方案的运行成本更低，验证了布谷鸟搜索算法的优越性。

不同负载数量的条件下，两种云计算资源负载分配算法的资源负载率最大值变化曲线如图5所示。

从图5可以看出，随着负载数量增加，两种算法的资源负载率最大值上升，但是在相同的负载数量条件下，布谷鸟搜索算法的资源负载率最大值始终小于文献[11]算法，没有出现负载过高的云计算资源，便资源上的负载分配更加合理，提高了云计算资源利用率。

4 总结

资源负载分配是云计算领域的重要研究方向，为了解决当前云计算资源负载分配算法存在的局限性，提出基于布谷鸟搜索算法的云计算资源负载分配算法。首先建立云计算资源负载分配的模型，然后利用布鸟搜索算法对其进行求解，得到云计算资源负载分配方案，仿真测试实验结果表明，布谷鸟搜索算法可以快速找到云计算资源负载最优分配方案，确保整个云计算系统具有较好的负载均衡状态。

参考文献

[1] Buyya R， Yeo C S， Venugopal S， et al. Cloud computing and emerging IT platforms： Vision， hype， and reality for delivering computing as the 5th utility[J]. Future Generation Computer Systems， 2009， 25（6）： 599-661.

[2] 姜栋瀚，林海涛. 云计算环境下的资源分配关键技术研究综述[J]. 中国电子科学研究院学报， 2018，13（3）：308-314.

[3] 周墨颂，董小社，陈衡，等. 基于计算资源运行时剩余能力评估优化云平台[J]. 计算机研究与发展，2017，54（11）：2516-2533.

[4] 刘小铭，李宗辉，王俊杰，等. 云计算中时间感知应用的资源分配与调度算法[J].西南师范大学学报（自然科学版）， 2017， 42（7）： 46-53.

[5] 朱新峰，张智浩，王彦凌. 移动边缘计算环境下的动态资源分配策略[J]. 计算机工程与科学， 2019， 41（7）：1184-1190.

[6] 李杰，张静，李伟东，等. 一种基于共享公平和时变资源需求的公平分配策略[J]. 计算机研究与发展，2019，56（7）：1534-1544.

[7] 陈钦荣，刘顺来，林锡彬. 一种混合优化的云计算资源调度算法[J]. 韩山师范学院学报， 2016，37（6）：15-23.

[8] 赵宏伟. 基于改进粒子群算法的云计算资源调度模型的研究[J]. 沈阳大学学报（自然科学版）， 2015，27（6）：507-511.

[9] 谢辅雯，张敏. 基于改进型离散粒子群优化的云计算资源分配方案[J]. 湘潭大学自然科学学报，2017，39（3）：89-93.

[10] 周丽娟，王春影. 基于粒子群优化算法的云计算资源调度策略研究[J]. 计算机科学， 2015， 42（6） ：279-281.

[11] 冯小靖，潘郁. 云计算环境下的DPSO资源负载均衡算法[J].计算机工程与应用， 2013， 49（6）：105-108.

[12] Yang X S， Deb S. Multi-objective Cuckoo search for design optimization [J]. Computers & Operations Research， 2013， 40（6）： 1616-1624.

（收稿日期： 2019.07.01）

作者简介：李波（1983-），男，汉，广东吴川人，硕士，计师，研究方向：电子与通信技术。文章编号：1007-757X（2020）02-0141-04