随着计算机应用范围的不断拓宽,每天会涌入大量数据,单机运行速度已经达到了瓶颈,无法满足海量数据处理的要求,在此背景下,云计算技术应运而生[1].云计算技术是多种技术的集成,主要包括:网格计算技术、分布式处理技术、并行计算及人工智能技术,其基于互联网技术将各种不同的资源打包成服务,通过收费方式提供给用户[2-3].由于云计算节点资源数量有限,且比较昂贵,因此需尽量使云计算资源上负载保持一种动态均衡,故云计算资源利用率达到最大化是云计算领域中的一个重要研究方向[4-5].
针对云计算负载均衡问题,出现了许多类型的云计算负载均衡方法[6].最初,人们采用穷举式搜索算法对负载均衡问题进行求解[7],但当云计算资源负载规模较大时,计算复杂度会呈指数形式增长,在短时间内很难搜索最优云计算负载均衡方案,不能满足现代海量数据处理的要求.随着群智能技术研究的不断深入,出现了许多类型群智能优化算法,它们模拟自然界生物的群体搜索特性对问题进行求解,如基于禁忌搜索算法、基于蝙蝠算法、基于蚁群算法及基于猫群优化算法的云计算负载均衡方法等[8-10].上述算法均需建立云计算负载均衡问题的相关数学模型,然后找到云计算资源负载最优分配方案[11-12],故在实际应用中,这些群智能优化算法存在搜索效率低、局部最优解搜索停滞、求解精度低等问题[12].
针对当前云计算负载均衡方法的节点出现过负载或者长期空闲的局限性,本文设计了基于量子粒子群优化算法[13]的云计算负载均衡方法,并与其他群智能优化算法进行了仿真对比实验,证明了云计算负载均衡方法的可行性和优越性.量子粒子群优化算法能够避免其他群智能优化算法在求解过程中存在的缺陷,提高了云计算节点资源的利用率,使节点负载更加均衡,能够获得更为理想的云计算负载方案.
云计算系统是一种为了解决海量任务的并行式处理系统,与单节点计算机系统相比,其工作模式具有比较明显的差异,云计算将服务器、存储设备、网络、打印机等抽象成资源,任何用户都可按自己的需求申请相应类型服务,能够满足不同用户服务质量要求.云计算系统的基本结构如图1所示.
图1 云计算系统的基本结构
Fig.1 Basic structure of cloud computing system
设用户任务集合为S={s1,s2,…,sm},其中,si为第i个用户的任务;云计算系统所有节点资源组成的集合为R={r1,r2,…,rl},其中,rj为节点资源的虚拟设备,其与实际相关物理设备相对应;云计算中具体物理设备集合为D={d1,d2,…,dn},dk为第k个物理设备.以上三个参数的相互关联集合可表示为
C={S,R,D,Mtr,Mrd}
(1)
式中:Mrd为云计算资源与物理设备之间的映射关系;Mtr为用户任务与云计算系统资源之间的映射关系.
设第i个用户的任务被分配到第j个资源上,云计算节点资源采用第k个物理设备处理该任务,任务在相应物理设备处理时间为E(si,Mtr,dk),物理设备dk开始执行第i个用户任务时间为ST(dk),则第i个用户的任务完成时间为
F(si,Mtr,dk)=ST(dk)+E(si,Mtr,dk)
(2)
物理设备dk上任务完成时间之和为
(3)
式中,cik=1为si在dk上执行;否则cik=0.云计算负载均衡求解就是找到一个用户任务完成时间最少的方案,即
(4)
假设对于粒子个体i,第t个时间点搜索到的最优位置为表示搜索空间的维数;第t个时间点粒子飞行速度为
当前位置为
第t个时间点整个粒子群搜索到的最佳位置为
则粒子速度及位置更新表达式为
(5)
(6)
式中:w为权值;τ1、τ2为加速因子;β为搜索时间间隔.
标准粒子群优化算法与其他智能优化算法一样,存在不同程度的局限性,如存在搜索后期效率低、找最优解的概率低等问题.为了克服标准粒子群优化算法的缺陷,提出了量子粒子群优化算法.
在经典力学理论中,粒子的状态可以采用位置和速度两种状态进行描述,但在量子力学理论中,粒子具有波动粒子的特性,粒子的位置和速度都包含了概率特征,即粒子状态可以用波函数描述为ψ(X,t),X=(x,y,z),该粒子是一个三维空间中的位置变量,波函数在某一点强度与粒子在该点出现的概率成正比,即满足
∭dxdydz=1
(7)
在量子力学中,粒子运动的动力学方程为
(8)
式中:h为普朗克常数;为哈密顿算子.
对量子粒子群优化算法的粒子收敛行为进行分析可知:算法中存在一个以点P为中心的某种形式的吸引势,把点P称为粒子的吸引子.通过在吸引子中建立一维势阱,推导出粒子在势阱中的定态薛定谔方程,解得粒子出现在相对吸引子位置Y的概率密度函数为
(9)
式中,L为粒子与种群平均最优解间的距离.
引入蒙特卡罗随机模拟方法测量粒子的位置,粒子在以P点为中心的一维势阱中运动,其位置可表示为
(10)
式中:u为一个随机数;XP为当前P点位置.
根据式(5)、(6)和(10)可以得到具有量子行为的粒子进化方程,即
(11)
式中:α为搜索扩张系数;为粒子在第t个时间点随机数.
为了测试量子粒子群优化算法(QPSO)的优越性,本文采用标准粒子群优化算法(PSO)进行了对比分析.选用的标准测试函数为Griewank和Rosenbrock,其定义分别为
(12)
(13)
图2为两种算法在不同测试函数下的对比分析结果.由图2可知,相对于粒子群优化算法,量子粒子群优化算法能够找到更优的解.
图2 量子粒子群算法和粒子群算法的性能对比
Fig.2 Performance comparison between QPSO algorithm and PSO algorithm
本文引入量子粒子群优化算法对云计算负载均衡问题的数学模型进行求解,具体步骤如下:
1) 建立云计算系统,确定各种云计算资源的数量、云计算任务数量以及各种云计算资源的处理能力;
2) 收集用户任务,对云计算用户调度任务进行分解,划分为不同大小的云计算任务;
3) 根据云计算任务、云计算资源以及物理设备之间的对应关系,以用户任务完成时间最短为目标函数,构建云计算负载均衡问题的数学模型;
4) 引入量子粒子群优化算法对云计算负载均衡的数学模型解进行搜索,找到最优的云计算负载均衡方案.
为了分析量子粒子群优化算法云计算负载均衡方法的性能,采用Matlab 2017工具箱编程云计算负载均衡程序,云计算系统中的节点资源类型为5类.量子粒子群优化算法的参数设置为:量子粒子数为20,搜索扩张系数为0.25,最大迭代次为300.
3.2.1 任务完成时间对比
选择文献[14]和文献[15]的云计算负载均衡方法进行对比实验.每一种云计算负载均衡方法均进行5次仿真实验,以增加实验结果的可靠性,3种云计算负载均衡方法的任务完成时间对比结果如图3所示.由图3可知,基于量子粒子群优化算法的云计算负载均衡方法的任务完成时间最短,而文献[14]和文献[15]的云计算负载均衡方法的任务完成时间均有一定的延长,量子粒子群优化算法提升了任务完成的速度.
图3 云计算负载均衡方法的负载完成时间
Fig.3 Load completion time of load balancing methods for cloud computing
3.2.2 资源负载分配结果对比
3种云计算负载均衡方法的资源负载分布结果对比如图4所示.根据图4结果可知,量子粒子群优化算法的云计算资源负载十分均衡,出现少量的“过负载”或者“空负载”现象;而文献[14]和文献[15]的云计算负载均衡方法均出现了大量“过负载”或者“空负载”现象,这表明量子粒子群优化算法可以保证云计算负载均衡,提高了云计算资源利用率.
3.2.3 最优方案迭代次数对比
量子粒子群优化算法与文献[14]和文献[15]的云计算负载均衡方法找到最优方案的迭代次数对比如表1所示.由表1可知,量子粒子群优化算法找到最优方案的迭代次数均值明显少于文献[14]和文献[15]的云计算负载均衡方法,量子粒子群优化算法加快了云计算负载均衡问题的求解速度,可以满足大规模云计算负载均衡应用要求.
图4 云计算负载均衡方法的负载分布对比
Fig.4 Comparison of load distribution among load balancing methods for cloud computing
表1 最优方案的迭代次数对比
Tab.1 Comparison of iteration times for optimal solution
实验编号量子粒子群优化算法文献[14]文献[15]11191371592118139162311713315741201351545114136162
负载均衡是云计算系统中的一项关键技术,针对当前云计算负载均衡方法存在的不足,为了获得更优的云计算负载均衡效果,本文设计了基于量子粒子群优化算法的云计算负载均衡方法.测试结果表明,量子粒子群优化算法可以获得理想的云计算负载均衡方案,使云计算节点之间的负载更加均衡,加快了用户任务完成速度,具有一定的推广价值.
[1]朱炜,王俊,周迅钊.基于负载均衡的医院云计算系统资源调度方案 [J].计算机工程,2018,44(3):37-41.
(ZHU Wei,WANG Jun,ZHOU Xun-zhao.Resource scheduling scheme of hospital cloud computing system based on load balancing [J].Computer Engineering,2018,44(3):37-41.)
[2]冷明,孙凌宇,朱平.云计算负载均衡任务调度问题的元胞自动机模型研究 [J].小型微型计算机系统,2016,37(10):2212-2216.
(LENG Ming,SUN Ling-yu,ZHU Ping.Research on cellular automata model for load balancing task sche-duling in cloud computing [J].Minicomputer System,2016,37(10):2212-2216.)
[3]张少辉,崔仲远,韩秋英.云计算环境下基于非均匀窗口蚁群行为的负载平衡算法 [J].重庆邮电大学学报(自然科学版),2016,28(4):567-574.
(ZHANG Shao-hui,CUI Zhong-yuan,HAN Qiu-ying.Load balancing algorithm based on non-uniform window ant colony behavior in cloud computing environment [J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2016,28(4):567-574.)
[4]徐爱萍,吴笛,徐武平,等.实时多任务异构云计算平台负载均衡算法 [J].中国科学技术大学学报,2016,46(3):215-221.
(XU Ai-ping,WU Di,XU Wu-ping,et al.Load ba-lancing algorithm for real-time multi-task heterogeneous cloud computing platform [J].Journal of China University of Science and Technology,2016,46(3):215-221.)
[5]张继荣,陈琛.基于负载均衡的云计算资源分配算法 [J].微电子学与计算机,2017,34(9):43-47.
(ZHANG Ji-rong,CHEN Chen.Cloud computing resource allocation algorithm based on load balancing [J].Microelectronics and Computers,2017,34(9):43-47.)
[6]任金霞,刘敏.基于改进GA的云计算任务调度策略 [J].沈阳工业大学学报,2019,41(3):320-325.
(REN Jin-xia,LIU Min.Task scheduling strategy for cloud computing based on improved GA [J].Journal of Shenyang University of Technology,2019,41(3):320-325.)
[7]海江.一种改进云计算虚拟资源负载均衡调度方案 [J].控制工程,2017,24(1):100-105.
(HAI Jiang.An improved cloud computing virtual resource load balancing scheduling scheme [J].Control Engineering,2017,24(1):100-105.)
[8]孙凌宇,冷明,朱平,等.云计算环境下基于禁忌搜索的负载均衡任务调度优化算法 [J].小型微型计算机系统,2015,36(9):1948-1952.
(SUN Ling-yu,LENG Ming,ZHU Ping,et al.Tabu search-based load balancing task scheduling optimization algorithms in cloud computing environment [J].Minicomputer System,2015,36(9):1948-1952.)
[9]任神河,郑寇全,关冬冬,等.基于IFTS的云计算网络动态负载均衡方法 [J].系统工程理论与实践,2019,22(5):1298-1307.
(REN Shen-he,ZHENG Kou-quan,GUAN Dong-dong,et al.Dynamic load balancing method of cloud computing network based on IFTS [J].System Engineering Theory and Practice,2019,22(5):1298-1307.)
[10]魏勇,赵开新,张松青,等.基于改进蚁群算法的云计算任务调度研究 [J].火力与指挥控制,2017,42(5):130-133.
(WEI Yong,ZHAO Kai-xin,ZHANG Song-qing,et al.Research on cloud computing task scheduling based on improved ant colony algorithm [J].Firepower and Command Control,2017,42(5):130-133.)
[11]王东亮,衣俊艳,李时慧,等.融合负载均衡和蝙蝠算法的云计算任务调度 [J].信息网络安全,2017,7(1):23-28.
(WANG Dong-liang,YI Jun-yan,LI Shi-hui,et al.Cloud computing task scheduling combining load ba-lancing and bat algorithms [J].Information Network Security,2017,7(1):23-28.)
[12]匡珍春,谢仕义.基于猫群优化算法的云计算虚拟机资源负载均衡调度 [J].吉林大学学报(理学版),2016,54(5):1117-1122.
(KUANG Zhen-chun,XIE Shi-yi.Cloud computing virtual machine resource load balancing scheduling based on cat swarm optimization algorithm [J].Journal of Jilin University (Science Edition),2016,54(5):1117-1122.)
[13]张艺瀛,金志刚.一种高维多模态优化的量子粒子群优化算法 [J].哈尔滨工业大学学报,2018,50(11):50-58.
(ZHANG Yi-ying,JIN Zhi-gang.A quantum particle swarm optimization algorithm for multi-dimensional modal optimization [J].Journal of Harbin University of Technology,2018,50(11):50-58.)
[14]陆佳炜,李杰,张元鸣,等.基于改进禁忌搜索的云任务负载均衡调度策略研究 [J].小型微型计算机系统,2018,39(10):2254-2259.
(LU Jia-wei,LI Jie,ZHANG Yuan-ming,et al.Research on cloud task load balancing scheduling strategy based on improved tabu search [J].Minicomputer System,2018,39(10):2254-2259.)
[15]孙兰芳,张曦煌.基于蜜蜂采蜜机理的云计算负载均衡策略 [J].计算机应用研究,2016,33(4):1179-1182.
(SUN Lan-fang,ZHANG Xi-huang.Cloud computing load balancing strategy based on honey harvesting mechanism [J].Computer Application Research,2016,33(4):1179-1182.)