一种基于简谐振动的云资源分配方法

张妍琰，姚 远，张 娜

河南城建学院计算机与数据科学学院，河南平顶山 467036

【电子与信息科学/ElectronicsandInformationScience】

一种基于简谐振动的云资源分配方法

张妍琰，姚 远，张 娜

河南城建学院计算机与数据科学学院，河南平顶山 467036

为优化云服务系统的资源分配，提高不同资源类型的服务质量，提出基于简谐振动的云资源分配模型，设计一种求解模型的迭代算法．根据谐振子运动特性进行能级划分，加强对邻域内最优解的精细搜索，降低云资源被局部分配的概率，依据能级差构造解空间，使用简谐系统能量转换规律自适应调整解向量的搜索步长．通过实验验证分配模型的求解算法以及解的质量，相比分支定界法和遗传算法相比，该算法在较大规模问题上执行效率高且资源分配成本低．

云计算；简谐振动；资源划分；能级；满意度；服务质量；最优解

云资源弹性分配特性允许企业和政府等组织按需购买，使其逐渐成为分布式软件系统的主要部署平台[1-2]．云计算资源分配时采用动态的拍卖机制，资源的分配更合理[3]．用户交换的闲置资源可采用基于贝叶斯博弈的云框架模型[4]．云资源分配模型可以用纳什均衡优化[5]．云虚拟机分配问题可建模为组合拍卖问题[6]．分配方根据系统当前负载定价，使用方根据响应时间还价[7]，建立一种动态的资源模型更能满足云环境下的多资源服务需求．云环境中不同资源的分配采用测试用例方法会出现组合爆炸问题，因此在现实的分配方式中，根据经验进行手工分配显得不切实际．

针对上述问题，建立适应性云资源分配模型把服务质量和资源供求作为主要因素[8]．为确保资源成本最小化，可把资源细粒度分配[9]．云资源的分配可采用元启发式搜索算法求解[10]．元启发式搜索算法(如遗传算法、蚁群算法等)可用于不确定性算法系统，该方法通过牺牲精确度来换取计算的并行性，想要同时满足高精确度和高并行计算能力是一件困难的事情．因此，本研究在资源分配过程中引入一种智能搜索模拟谐振子(simulated harmonic oscillator, SHO)算法[11]．

1 模拟谐振子简述

简谐振动物体遵循胡克定律，即物体的加速度与物体偏移平衡位置的位移大小成正比，方向与位移方向相反，总指向平衡位置．胡克公式为

F=-kx

(1)

其中，F为弹复力；k为胡克系数；x为位移．

图1是简谐振动的模型图，做简谐振动的物体有2个特殊状态：① 质点在振源(又称平衡点)位置时，F=0，x=0； 质点的速度达到最大，加速度为0；② 该状态具有对称性，当质点受到向右的弹力F时，向左运动，从振源向左端点运动过程中，弹力F和加速度逐渐增大，速度逐渐减小，质点到达左端点时速度为0．质点向右运动时，具有类似规律．根据牛顿第二运动定律可得

1)动能Ek．

(2)

其中，v为简谐振动的速度；m为谐振子质量；φ为简谐振动的相位；A为简谐振动的振幅；t为振动时间；ω为角频率．

2) 弹性势能Eu．

(3)

其中，x为位移．

3) 系统总能量E．

(4)

图1 简谐振动模型Fig.1 Harmonic vibration model

2 云资源分配模型

当胡克系数k确定时，弹性势能取决于位移．令C=k/2， 于是Eu=Cx2， 把系统的弹性势能划分为多个连续的能量等级，简称能级．当质点在平衡点时，位移和能级最小均为0；当质点在左端点或右端点位置时，位移最大，而能级最大为E． 设物体偏移平衡点的位移为xi， 其中，i=0,1,…,n， 此时质点的左右移动是一种对称运动，本研究对质点从平衡点到右端进行能级划分，划分结果如图2．其中，平衡点能级为E0=0， 从平衡点到右端点弹性势能能级大小依次划分为

En=Cn2

(5)

其中，n=0,1,2，…．

图2 能级划分Fig.2 Energy level classification

物体的振幅为A， 把系统的弹性势能划分为A个等级，每个单位长度为1个能级，将其归一化到[0,1]区间上，得到系统的单位弹性势能能级为

(6)

其中， 0≤i≤A．

定义1两个单位势能之间的弹性势能差值为能级差，记为ΔEi， 依次为

(7)

其中， 0≤i≤A．

由式(7)可知，从平衡点到端点相邻两能级的能级差逐渐变大，如图3．

图3 能级差变化Fig.3 Change of energy level difference

2.1 云资源的分析

假设云环境中物理机的数量是3，编号分别为p1、p2和p3， 其上部署了数量不等的6个虚拟机(VM1,VM2,…,VM6)，该云环境中可用资源状态如图4．为确定资源的最佳分配量，对当前可用的资源逐一搜索，将相应的编号保存在云资源矩阵R中．

图4 可用资源状态Fig.4 Available resources

逻辑服务定义．在云服务系统中资源量的分配称为逻辑服务，包含了服务质量(quality of service，QoS)属性和资源属性．

在实际应用中，QoS属性包含响应时间、吞吐量和可靠性等．为不失一般性，本研究考虑CPU 个数、内存大小和网络带宽3种QoS属性．对具有不同架构和处理能力的CPU，采用统一度量标准，如每秒百万条指令(million instructions per second, MIPS)，将其转化为具有相同计算能力的CPU[12]．

2.2 基于能级的云资源划分

云资源划分的粒度直接影响求解效率，若划分粒度过小，会使可行解空间过大；反之，若划分粒度过大，会导致云资源过剩，增加资源成本．本研究根据能级进行云资源的划分，采用图2的方式划分可用资源分配量．对于CPU资源的划分，假设可用的物理机CPU数量为48个，则一种可分配的方案为(12, 22, 32, 42, 42+2)，如图5．

图5 资源划分示例Fig.5 An example of resource partition

2.3 云资源优化分配模型

云资源优化分配模型提供2种决策行为，分别用X和Y表示．其中，X={xi,j,k|1≤i≤n, 1≤j≤ni, 1≤k≤3},xi,j,k=1为根据状态量Sj,k在物理机上创建虚拟机，否则，xi,j,k=0；Y={yj,k|1≤j≤ni, 1≤k≤3},yj,k=1表示选择逻辑服务Sj,k， 否则，yj,k=0． 因此，云资源优化分配函数为

逻辑服务资源分配量的总成本

(8)

逻辑服务的个数

(9)

物理机上创建的虚拟机个数

(10)

上述资源优化分配函数属于组合优化问题，等价于多维多选择背包问题，是非确定性多项式(non-deterministic polgnomial，NP)问题[13]，无法在多项式时间内求得精确解，因此本研究采用模拟谐振子算法求解近似最优解．

3 最优解的计算

质点是连续运动的，其位置状态与势能状态相对应，因此，质点经过全部位置状态能遍历整个势能空间．待求问题的过程解具有随机性，于是，把质点某个位置状态映射到待求问题的某个解状态，通过遍历质点所有的位置状态，能够遍历待求问题的全部解状态．求解问题时，把全部解空间投影到图3的能级差空间上，过程解分布在每个能级差区域．

4 算法设计

模拟谐振子算法主要包含：① 用于空间解的全局搜索，确保算法的全局搜索能力；② 算法的局部搜索能力，快速求出最优解．为测试模拟谐振子算法性能，文献[14]提供了4个标准测试函数，其全局最优点均为xi=0，fi(x)=0． 具体函数为[14]

1) Sphere函数：

2) Rosenbrock函数：

3) Rastrigin函数：

4) Griewank函数：

文献[14]分别对以上4个函数进行了单峰函数和多峰函数测试，结果如下：

Sphere函数最小值、最大值、平均值和标准差分别为： 9.950 1×10-51， 2.103 6×10-6， 2.103 6×10-37，6.387 1×10-62．

Rosenbrock函数最小值、最大值、平均值和标准差分别为： 9.361 7×10-1， 1.798 3×101， 1.495 2， 1.080 6．

Rastrigin函数最小值、最大值、平均值和标准差分别为： 2.016 1×10-1，2.013 0×101，3.126 3，2.213 5．

Griewank函数最小值、最大值、平均值和标准差分别为： 1.078 2×10-3， 1.231 5×10-1， 4.374 8×10-2，7.716 4×10-4．

本算法(harmonic vibration, HV)主要分为两个阶段：① 找到解空间的近似最差解和近似最优解，从而获得系统的近似最大势能；② 确定搜索的步长和接受准则．

HV算法选择Sphere函数作为目标函数，即f(s)=f1(x)． 这是因为Sphere函数标准差最小，且最小值(对应平衡点值min)和最大值(对应端点值max)区间范围最大，有利于增大解空间的搜索范围．

5 实验仿真

遗传算法是一种通过群体迭代求解优化问题的元启发式算法，可得到一系列最优候选解，而其他启发式搜索算法，如爬山算法和模拟退火算法等容易收敛于1个局部最优解[15]．文献[16]在传统遗传算法基础上提出双精英协同进化遗传算法[16](double elite coevolutionary genetic algorithm, DECGA)．DECGA算法在个体编码上，每个基因取值为十进制整数，与二进制编码相比，该编码方式长度短、求解效率高等优势．为使DECGA算法能够收敛到全局最优解，在选择算子时引入精英保留策略，从而避免最优个体在杂交操作中被破坏．因此，选择DECGA算法作为HV算法的比较对象．

实验首先对任务数和迭代条件进行初始化，任务分别为2 100、5 200、8 000和10 000，每个任务数分别迭代3次，迭代次数依次为200、500和1 000．系统仿真中使用了8块Dell PowerEdge M620刀片服务器构成服务器集群，每个刀片服务器配置6个CPU，内存为128 Gbit，设定1块刀片就是1个物理节点．问题求解规模分别为202 100，3 205 200，3 208 000和32 010 000．采用Dell服务站分析软件分别对HV算法和DECGA算法进行分析．

5.1 执行效率分析

CPU的利用率如图6(a)，调用DECGA算法VM的利用率约为50%，等待的VM约为20%，闲置的VM约为30%．调用HV算法VM的利用率约为60%，等待的VM约为20%，闲置的VM约为20%．HV算法VM利用率较高，VM资源浪费相对较少．执行任务时CPU的负载率如图6(b)，调用HV算法过程中CPU的负载率相对要低一些，CPU的负载率平均值约在40%以内．调用DECGA算法过程中CPU的负载率最高峰值接近100%，CPU的负载率平均值约在60%以内．

图6 利用率和负载情况比较Fig.6 (Color online) Comparision of VM utilization and CPU load

实验结果分析如下：模拟谐振子算法根据逻辑能级对解空间进行划分，划分的能级越高，解的领域搜索范围越大，得到近似解的概率越大．从最高势能到基态的搜索是一次对解的全局范围搜索，能够有效地避免局部解的搜索．

5.2 最小资源成本分析

对解质量(即最小资源成本)进行验证实验，目前，求解多维多选择背包问题大多采用分支定界法(branch and bound, BAB)．分支定界法是一种确定的算法，能够求得最优解，因此，实验中将HV算法与BAB算法相比较，从而验证其对最优解的近似程度．实验中CPU个数为32个，内存个数24，带宽大小为20 Mbit/s，结果如图7．

由图7可知，在不同逻辑服务数量下，HV算法求得的最小资源成本明显低于BAB算法．随着逻辑服务数量的增加，HV算法的最小资源成本与BAB算法差距逐渐增大，表明本研究的HV算法在引入精英保留策略后，解的质量明显优于BAB算法．

图7 最小资源成本比较Fig.7 Minimal resource cost comparison

结 语

研究在云环境下如何高效地分配资源和为用户提供服务保证等问题．通过对经典谐振子运动进行探讨，设计相应的模拟算法，使得云环境下的资源分配更合理，在解空间中反复迭代，寻求最优近似解．利用现有的实验环境对所提的算法进行模拟，从虚拟机的利用率、CPU的负载率以及资源成本上进行比较分析，验证求解算法的有效性．

引文：张妍琰，姚 远，张 娜．一种基于简谐振动的云资源分配方法[J]. 深圳大学学报理工版，2017，34(6)：591-596.

/

[1] Durao F, Carvalho J F S, Fonseka A, et al. A systematic review on cloud computing[J]. The Journal of Supercomputing, 2014, 68(3): 1321-1346.

[2] 陈 康，郑维民．云计算：系统实例与研究现状[J]．软件学报，2009，20(5)：1337-1348．

Chen Kang, Zheng Weimin. Cloud computing: system instances and current research[J]. Journal of Software, 2009, 20(5): 1337-1348.(in Chinese)

[3] Lin Weiyu, Lin Guanyu, Wei Hungyu. Dynamic auction mechanism for cloud resource allocation[C]// Proceeding of the 10th IEEE/ACM Conference on Cluster, Cloud, and Grid Computing. Piscataway, USA: IEEE Computer Society, 2010: 591-592.

[4] Shang Shifeng, Jiang Jinlei, Wu Yongwei, et al. DABGPM: a double auction Bayesian game-based pricing model in cloud market[C]// Proceeding of the IFIP International Conference on Network and Parallel Computing. Heidelberg, Germany: Springer-Verlag, 2010: 155-164.

[5] Sun Dawei, Chang Guiran, Wang Chuan, et al. Efficient Nash equilibrium based cloud resource allocation by using a continuous double auction[C]// Proceeding of the International Conference on Computer Design and Applications. Piscataway, USA: IEEE Computer Society, 2010: 94-99.

[6] Zaman S, Grosu D. Combinatorial auction-based allocation of virtual machine instances in clouds[J]. Journal of Parallel and Distributed Computing, 2013, 73(4): 495-508.

[7] 胡志刚，刘 艳．云环境下基于组合双向拍卖的动态资源定价[J]．计算机工程，2012，38(8)：19-21．

Hu Zhigang, Liu Yan. Dynamic resource pricing based on combinatorial double auction in cloud environment[J]. Computer Engineering, 2012, 38(8): 19-21.(in Chinese)

[8] 丁 丁，罗四维，艾丽华．基于双向拍卖的适应性云计算资源分配机制[J]．通信学报，2012，33(Z1)：132-140．

Ding Ding, Luo Siwei, Ai Lihua. Adaptive double auction mechanism for cloud resource allocation[J]. Journal on Communications, 2012, 33(Z1): 132-140.(in Chinese)

[9] Zhu Q, Agrawal G. Resource provisioning with budget constraints for adaptive applications in cloud environments[J]. IEEE Transactions on Services Computing, 2012, 5(4): 497-511.

[10] Harman M, Mansouri S A, Zhang Y. Search-based software engineering: trends, techniques and applications[J]. ACM Computing Surveys, 2012, 45(1): 11-61.

[11] 王 鹏．云计算的关键技术与应用实例[M]．北京：人民邮电出版社，2010：168-174．

Wang Peng. The key technology of cloud computing and applications[M]. Beijing: Posts & Telecom Press, 2010: 168-174.(in Chinese)

[12] Shi Xuelin, Xu Ke. Utility maximization model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013, 36(2): 252-262.

[13] 赵秀涛，张 斌，张长胜．一种基于服务选取的SBS云资源优化分配方法[J]．软件学报，2015，26(4)：867-885．

Zhao Xiutao, Zhang Bin, Zhang Changsheng. Service selection based on resource allocation for SBS in cloud environments[J]. Journal of Software, 2015, 26(4): 867-885.(in Chinese)

[14] Shi Y, Eberhart R C. A modified particle swarm optimizer[C]// IEEE International Conference on Evolutionary Computation Proceedings. Piscataway, USA: IEEE, 1998: 69-73.

[15] 王 赞，樊向宇，邹雨果，等．一种基于遗传算法的多缺陷定位方法[J]．软件学报，2016，27(4)：879-900．

Wang Zan, Fan Xiangyu, Zou Yuguo, et al. Genetic algorithm based multiple faults localization technique[J]. Journal of Software, 2016, 27(4): 879-900.(in Chinese)

[16] 刘 全，王晓燕，傅启明，等．双精英协调进化遗传算法[J]．软件学报，2012，23(4)：765-775．

Liu Quan, Wang Xiaoyan, Fu Qiming, et al. Double elite coevolutionary genetic algorithm[J]. Journal of Software, 2012, 23(4): 765-775.(in Chinese)

【中文责编：方圆；英文责编：木柯】

2016-07-28；Revised2017-04-10；Accepted2017-06-26

Associate professor Zhang Na. E-mail:gcschool2014@163.com

Harmonicvibrationbasedresourceallocationmodelincloudenvironments

ZhangYanyan,YaoYuan,andZhangNa

School of Computer and Data Science, Henan University of Urban Construction, Pingdingshan 467036,Henan Province, P.R.China

In order to optimize the resource allocation of cloud service system and improve the quality of different resource types of services, we propose a cloud resource allocation model based on harmonic vibration and design an iterative algorithm to solve the developed model. Based on the harmonic oscillator movement characteristics, our model carries out the division of energy level, strengthens the fine search of the optimal solution in neighborhood, and reduces the possibility of the local distribution of cloud resources. Then, the solution space is reorganized based on the energy level difference. Meanwhile, the search step length of solution vector is adaptively adjusted by considering the energy conversion rule of harmonic system. Finally, the experiment validates the solution quality of proposed allocation model and solving algorithm by comparison with the branch/bound method and genetic algorithm. Especially, our method performs more efficiently and needs lower cost of resource allocation when dealing with the large-scale problems.

cloud computing; harmonic vibration; resource division; energy level; satisfaction; quality of service; optimal solution

Foundation：National Natural Science Foundation of China (61202248)

：Zhang Yanyan, Yao Yuan, Zhang Na. Harmonic vibration based resource allocation model in cloud environments[J]. Journal of Shenzhen University Science and Engineering, 2017, 34(6): 591-596.(in Chinese)

TP 391

A

10.3724/SP.J.1249.2017.06591

国家自然科学基金资助项目(61202248)

张妍琰(1981—)，女，河南城建学院讲师．研究方向：云计算．E-mail：yanyanschool@163.com