基于绿色云计算平台的等价黄金分割资源分配优化算法研究

王咏梅，施培蓓，刘 磊，周媛媛

（1.合肥师范学院 计算机学院，安徽 合肥 230031；2.合肥市公安信息中心，安徽 合肥 230001；3.安徽大学 计算机学院，安徽 合肥 230036）

1 引言

在信息技术的高速发展过程中，随着企业用户和数据的爆炸式增长，能源效率已经成为一个突出的矛盾.如何减少碳排放和节约成本已成为大数据运营商越来越关注的问题[1].随着云计算的计算服务向普及化方向发展，对云计算的需求不断扩大，需要建立大规模的数据中心，而数据中心的运行维护需要消耗大量的能量[2].保证云计算系统的高性能，提高资源利用率，降低能耗已成为亟待解决的问题.绿色云计算为云计算技术的发展提供了契机，它通过构建合理的资源分配环境和高效的任务执行环境来降低能耗、提高效率，以达到节能环保的目的[3].资源分配是绿色云计算的关键技术之一.目前，资源分配的研究主要集中在通过平衡数据中心的负载来提高整体性能这一方面.这些研究没有把如何降低系统的能耗充分考虑进去.在资源配置过程中优化资源分配策略可以减少服务器产生的热量，降低散热成本，从而提高系统的稳定性和延长硬件[4,5]寿命.资源利用率的提高能有效节约能源，降低二氧化碳的排放，对缓解温室效应具有一定的贡献，对整个生态环境保护也具有重要意义，它符合当今社会的“绿色IT”概念.因此，研究绿色云计算环境下的资源分配优化策略具有重要的理论意义.

2 国内外资源配置优化策略的现状

随着云计算技术的蓬勃发展，谷歌、Amazon、IBM等大公司纷纷开发了自己的云计算平台，而云计算相关技术的研究与实现也呈现出快速发展的趋势.作为云计算的关键技术，资源配置仍处于研究阶段，到目前为止，还没有一个统一的行业标准[6].国内外研究有代表性的有：

文献[7]采用了演化博弈的方式对整个云计算市场进行建模分析，最终通过动态演化整个市场可以达到演化稳定.但是作者只是考虑了资源的价格，忽略了用户所关心的QoS问题.S.S.Manvi等人最早提出了面向市场的云计算架构，以及基于该架构的云计算资源分配方式[8].M.Macia等人采用遗传算法解决云计算市场中的定价问题，使得每一个云服务提供商能在整个市场中制定合理的服务价格[9].S.AT等人提出了基于市场机制的资源分配策略[10]，通过利用市场机制来寻找资源需求与分配的平衡点.但以上策略都侧重在运用市场机制方面对各种角色进行优化，对资源的分配方式没有提出具体的方案.

Shuai Ding等人通过动态分配虚拟机到服务器，证明了在保证服务质量的前提下可以通过虚拟机的迁移和关闭空闲服务器来降低功耗[11].S.T.Maguluri等人将虚拟资源分配问题建模为多维背包问题，并找到服务器执行单位事务功耗的最优点[12].文献[13]提出了一种基于云计算虚拟机初始分配的节能算法，设计了一种基于网络感知的虚拟机再调度算法.这些研究侧重从虚拟化应用方面考虑如何充分发挥虚拟化技术的优势，以实现硬件资源利用的最大化.

在资源分配算法的设计方面，为了实现资源分配的负载均衡，Florin Pop等人设计了一种基于遗传算法的能量感知优化模型和资源分配策略[3].Y.J.Chiang等人提出一种高效的绿色能耗控制资源分配方法[14]，但均没有充分考虑到资源分配中的能耗优化问题.J.T.Tsai等人提出了一种基于差分进化算法的云计算资源分配方法(IDEA)，实验证明了该算法比其他云计算资源分配方法具有更优的效率，但是该算法只考虑带宽占用、网络负载和响应时间等因素对云端资源分配的影响[15],没有充分考虑系统能耗情形下，如何构建动态能耗优化模型、资源分配优化模型的问题.

针对上述绿色云计算环境下的资源分配问题，本文提出了一个等价黄金分割资源分配优化算法(Equivalent Golden Partition Resource Allocation Optimization,EGPRAO)，该算法能实现全局和局部搜索的平衡，在构建合理的资源分配环境和高效的任务执行环境方面，该算法比目前已有的资源分配策略具有更低能耗、更高效率的优点.

3 等价区间划分与黄金分割策略

为了避免算法陷入局部最优值，实现全局和局部搜索的平衡，本文将算法的初始种群构建为一种等价区间划分优化模型.其目的是尽可能地将冗余个体划分为一个区间块，然后对不同的区间块进行不同的操作，从而指导相关算法算子进行引导搜索.图1描述的是该算法的种群等效区间划分模型流程图.

在图1中,N表示等价区间划分的个数,a表示种群中个体最小的适应度值,b表示种群中个体最大的适应度值,c表示种群中个体平均的适应度值.

黄金分割策略是利用区间消去法的原理，通过不断缩小单峰区间长度，即每次迭代都消去一部分不含极小值点的区间，使搜索区间不断缩小，从而逐渐逼近目标函数极小值点的一种优化方法.黄金分割策略是直接寻优法，通过直接比较区间上点的函数值的大小来判断区间的取舍，这种方法具有计算简单，收敛速度快等优点.

黄金分割策略是基于选择区间内计算点的位置，它具有以下通用的策略：

（1）点α1和α2相对于区间[a,b]的边界要对称分布，即区间[a,α1)的区间大小和(α2,b]的区间大小相等.

（2）每次计算一个新点，要求保留的区间长度l与原区间长度L之比等于被消去的区间长度L-l与保留区间长度之比，即满足以下条件：

4 等价黄金分割资源分配优化算法

本文设计的等价黄金分割资源分配优化算法的实现步骤如下：Step 1. 在[a,b]内取两点 α1和 α2,使

α1=a+0.382×(b-a),α2=a+0.618×(b-a)

Step 2. 计算 f1=f(α1)，f2=f(α2).

Step 3. 当 f1＜f2时，消去区间(α2,b].同时，令 b=α2，α2=α1，f1=f2.令 α1=a+0.382×(b-a)，f1=f(α1).

Step 4.当f1≥f2时，消去区间 [a,α1).同时，令 a=α1，α2=α1，f1=f2.令 α2=a+0.618×(b-a)，f2=f(α2).

Step 5.当b-a≤δ，算法结束；否则，返回到Step 3.

5 实验测试与结果分析

为了验证本文设计的EGPRAO算法的可行性和优越性，从算法的执行时间、资源分配的能耗和资源平均利用率三个方面设计了不同的目标函数，利用实验仿真平台CloudSim，进行仿真测试实验.考虑到单个数据中心的数据具有一定的不确定性，该绿色云计算平台设置了8个数据中心，每个数据中心包含10GB的RAM和2TB的存储，8核CPU,每个CPU的计算能力是10000MIPS.文献[15]的IDEA算法在多种不同平台环境下都取得了较好的实验结果，因此，在相同的测试条件下本文将EGPRAO算法与文献[15]的IDEA算法进行性能对比，实验结果分别如图2、图3和图4所示.

图2 两种不同资源分配算法的执行时间比较

图3 两种不同资源分配算法的能耗函数比较

图2显示的两种不同资源分配算法的执行时间函数对比结果，图3显示的是两种不同资源分配算法的能耗函数对比结果，图4显示的是两种不同资源分配算法的资源平均利用率函数对比结果.

图4 两种不同资源分配算法的资源平均利用率函数比较

通过图2-4的实验结果，我们不难看出：在执行时间、能耗优化和资源平均利用率等方面，本文设计的EGPRAO算法比传统的IDEA算法表现出更良好的性能.

6 结论

信息技术日新月异的变化，导致人类对云计算技术的应用越来越普及.本文针对绿色云计算中日益严重的能耗问题，设计了一种新的资源分配算法.该算法利用黄金分割策略和等价区间划分优化模型资源的优点，能实现全局和局部搜索的平衡.在构建合理的资源分配环境和高效的任务执行环境方面，该算法具有更低能耗、更高效率的优点.在CloudSim测试平台中，该算法取得了比较理想的实验结果.