基于迁置优化的云计算资源调度算法

许文庆

(1.福州理工学院，福建 福州 350506;2.福州理工学院移动通信和 物联网福建省高校工程研究中心，福建 福州 350506)

0 引言

近年来随着大数据和云计算等新技术的协同[1]推进，基于云计算环境下的数据中心网络在节点数量和数据规模上变得更加错综复杂.这使得整个云环境在系统可靠性、扩展性、成本可控性等诸多方面受到严峻的挑战.科学的虚拟资源调度策略作为云计算环境的核心技术，不仅可以应对传统网络的“僵化”[2]问题，对全新的应用服务和网络协议实施评估，也有利于改善云计算环境中数据中心的能耗度、资源冲突、载荷均衡及用户服务质量(QoS)等一系列问题[3].所谓的虚拟资源调度是指通过为云计算环境下的数据中心物理主机节点重载程度展开评估，并将其中的虚拟机科学地迁置到数据中心中其他最合适的目标物理宿机上.此举意在为虚拟机的迁移做铺垫，从而最小化服务成本和资源开销,最大化整个云计算系统的服务效益，同时也便于服务供应商良好地对数据中心进行管理.如此看来，对虚拟机资源实施科学高效地迁置就成了当前云计算环境下数据资源管理的核心问题之一.

对云计算系统中虚拟机实施迁置的关键在于使参与虚拟资源调度的物理主机节点规模最小，使参与虚拟资源调度的物理主机节点资源使用率最高，避免整个云计算数据中心的载荷分布失衡进而真正实现能源的绿色[4]管理.尤其在当前云计算和大数据协同并进的形式下，日益凸显的能源问题再次引发学术界的热议.并因此围绕以能耗管理为目标的云计算系统虚拟机安置问题展开一系列相关研究.对于虚拟机的安置可视为装箱问题来讨论，因此对于该问题的求解可考虑通过启发式算法来解决,譬如，遗传算法.但是文献[5]的研究结果表明该算法在编码效率中表现出的科学性有待改进.因此若将该算法用于笔者所提的分组问题的求解，那么在虚拟机实施安置过程中将无法得到全局最佳值.这势必造成虚拟机迁移效率劣化等一系列恶性循环问题，最终导致安置管理方案的失效.为了优化云计算系统中数据中心的物理主机资源利用率，改善能耗的管理效率，文献[6]提出了多目标安置优化思路.先是通过描述多目标优化模型极力提高物理资源使用率，将能耗最小化.然后使用经过改良的多适应函数遗传算法来并行优化多个目标.该算法思想相对于传统的遗传算法，在安置管理方面的科学效益较为显著.然而此思路的编码对象仅为虚拟机，编码长度较为冗繁，算法复杂度不占优势.因此也不适用于笔者提出的复杂分组问题的求解.为进一步使算法在分组[7]求解问题中具备更好的适应性，文献[8]对上述改良的多适应函数遗传算法做了持续优化.在秉承遗传算法在云环境数据中心资源使用率方面发挥优势的基础上，对遗传算法中3个步骤均做了延伸思考.显然此举促进遗传算法性能上升了一个台阶.然而从实际成效来看，该研究在至关重要的交叉步骤、变异步骤中却未能保证总是把优质的基因保留下来.从理论上看这样的思路在科学性方面稍显不足，而实际实验成效也应验了算法收敛较早.据此，可以预测该项持续改进的算法研究用于应对笔者提出的复杂分组求解问题收效甚微.

鉴于当前主流研究始终未能在资源利用率、效能安置、复杂分组问题求解中寻求到一个科学的平衡解，笔者围绕云计算环境下数据中心中以优化为目标，规划一个兼顾效能和极优解的虚拟机安置策略.

1 迁置优化算法数学模型

云计算环境下的数据中心基础设施由若干个物理服务器经由拓扑结构连接而成.为了最大化云计算系统中物理服务器的资源使用率和最小化基础设施的能耗等问题，在物理服务器中实施虚拟机高效部署显得至关重要，这也是迁置虚拟机的目标所在.所谓高效部署指从x个物理服务器形成的集合PM=[pm1,pm2,pm3,…,pmx]中筛选出合适的目的物理服务器用于响应y个虚拟机形成的虚拟机集合VM=[vm1,vm2,vm3,…,vmy]提出的迁置请求.部署过程不仅要使参与迁置作业的物理服务器规模最小，更要使迁置的部署过程具有最佳的鲁棒性.由于云计算系统的边缘用户请求呈现多样化，云计算对象的数据较大，故用于响应迁置请求的物理服务器集合所提供的资源类型和容量也需多元化[9].所提供的计算响应资源包括：带宽(GBs/day)、中央处理器(MIPS)、内存(GB)等.令第k个物理服务器中用于响应虚拟迁置计算请求的t类资源容量为sk-t，则PM=[pm1,pm2,pm3,…,pmx]中所能提供的资源大小记作Sk=[sk-1,sk-2,sk-3,…,sk-t].同时，令第l个虚拟机提请的资源要求为d1-t，则VM=[vm1,vm2,vm3,…,vmy]所提请的资源要求记作Dl=[dl-1,sl-2,sl-3,…,sl-t].为响应迁置优化算法中关于物理服务器规模最小化的宗旨，迁置过程可描述为：

(1)

其中，二进制数参量Jk=0，说明第k个物理服务器为关机睡眠；Jk=1则表示参与高效迁置部署作业中.NWPM指参与高效迁置部署作业的物理服务器规模.令云环境数据中心物理服务器使用率为u，算得高效迁置部署的目标函数为：

(2)

p(u)=u·(1-r)·PH+r·PH.

(3)

则在时间T范围内整个云环境下的数据中心能耗度为：

(4)

(5)

于是，求得第k个物理服务器的失衡度为

(6)

整个云环境数据中心载荷失衡度为

(7)

要规避云计算系统中物理服务器载荷失衡问题实现高效迁置部署目标，要求最小化NBDC参数值.

2 算法部署设计

正如引言所述，云数据中心虚拟机的迁移部署可用集装箱问题来应对.通过梳理传统研究方案的不足可知，高效的遗传算法在编码长度和搜索长度方面都应该是简短的.所以在为空间内个体搜索求解值的时候要采用小的染色体编码方法来表征，从而避免染色体的长度问题导致迁置部署的效能性[12].故笔者考虑用分组表征方法.

传统的遗传算法研究方案为了较快地生成第二代染色体,往往直接锁定那些适配值较高的染色体，该思想下的搜索解通常由于收敛过早导致所求解不具备全局普适性.为避免此类情形再次出现，笔者首先为个体逐一分析其适配值，再通过轮询方式计算出个体的命中率进而筛选出优质[13]的个体，即所谓的优胜劣汰.按照此思路，首先给出第k个个体Jk的命中率：

(8)

式中的Mk指Jk的匹配值.所谓的轮询适配即指通过一个圆形模型将种群的数量和个体命中率划分出x个区域，则第k个区域的角度为：

(9)

可见，Mk和anglek所对应的扇形区域呈正比.再通过累计方式计算圆形模型滚动过的弧度即可求解出第n个个体的命中率，记作：

(10)

现引入一个服从区间[0,1]分布的随机均衡系数δ，用于求解最适合用作第一代染色体的个体.将此求解过程函数表征为：

(11)

为使CH2 nd染色体能够延续到CH1 st个体中优质的基因，算法需先对CH1 st个体基因展开分析，评估函数记作：

(12)

若算得评估值越小，则表明该个体基因的失衡问题越凸显，非优质基因；反之，则为优质基因.然后根据评估值的权重选择用于交错的基因.从而使得CH2 nd能够可靠地延续到CH1 st优质的基因.极大地提高了物理服务器接受虚拟机高效迁置部署的科学性，克服了传统研究关于基因随机继承引发的灰色效应[14].

具体实施过程为:首先定义两个首代染色体CH1 st-A和CH1 st-B;然后对CH1 st-A中的个体服务器展开基因质量评估，将Ek值较大的个体嵌入CH1 st-B序列中的任意点使之生成CH2 nd序列;接着开始遍历CH2 nd序列串中的个体服务器直至计算出含有相同编号虚拟机的个体服务器，并将其剔除.若因剔除而孤立了某些虚拟机则综合采用优先适应算法[15]对其实施迁置.

迁置优化算法的目标旨在最小化NWPM从而节约云计算系统数据中心服务器的耗能.基于此思想，本次变种算子研究使用剔除已用过的服务器以及变种后不具备依赖性的虚拟机，也就是所求的解中缺少某个虚拟机而需采用优先适应算法对其实施返填的方式,以避免出现更大规模的扩散.关于服务器剔除的选取标准，主要参照基因评估函数的评估值Ek.若该值越小，表明该物理服务器中的虚拟机安置欠缺科学性，被剔除的概率越高；反之被保留的概率越高.此举目的在于将劣化变种事件约束在适配值较低的服务器个体上.

为了使高效迁置部署算法在迭代计算期间更好地评估染色体个体的优质状况，现引入适配参量M用于考量策略收敛快慢程度.为贯彻迁置优化算法思想，所引入的适配参量除了要顾及物理服务器资源使用率外,也应最小化被唤醒的服务器规模.故该参量具有较大权重，关系到所得解的科学性，表征为：

(13)

3 迁置优化算法实施

根据上述设计的算法方案，本次研究的算法思路为首先结合虚拟机提请的迁移请求得出X个排列.然后使用优先适应机制得到X个不同的安置方法.每历经一次迭代式计算便对X个序列串实施编码、选择、交叉、变异等处理，使CH1 st优质的基因传播到CH2 nd.随着循环迭代计算的持续深入，所有个体的适配参量M的权重值都将增加直至搜索到科学解.整个迁置优化方案的具体实施过程如下:步骤1,实施基于分组的基因编码；步骤2,随机化方式将种群进行初始化，并将迭代[16]次数置零；步骤3,根据所引入的适配评估函数依次计算出种群内的个体适配参量值；步骤4,使用轮询方式实施选择作业，选出两个首代染色体CH1 st-A和CH1 st-B;步骤5,根据优质基因评估函数的计算值获取优质个体，然后放在任意交叉处生成CH2 nd序列，并参照适配参量值筛选出变种的个体;步骤6,根据基因评估函数剔除劣质基因实施变种;步骤7,结合个体的适配参量值筛选出染色体CH1 st和染色体CH2 nd中最优质的个体,用作下一轮的迭代计算，同时迭代计数执行加1操作.

4 效益评估

4.1 实验环境

部署迁置优化算法的测评平台是在Cloudsim云模拟平台[17]上.为使该平台更好地适应于迁置优化算法的评估,需事先将六个类进行相关扩展.一般而言,云计算系统通常可提供满足各种需求的物理主机服务器，所以用于实施测评的物理主机服务器资源容量等配置也需要多样化.相关研究[18]显示，当物理主机服务器的中央处理器处于闲置休眠状态时所消耗的能源可达到满载状态时能耗的七成，所对应的功耗约220 W.为了考查迁置优化算法相对于传统研究方案中遗传算法和优先适应机制在应对虚拟机提请安置计算请求方面的优势，同时体现资源计算请求的多元化，本次测试分别设立了[100,200,300,400,500,600]6种不同载荷规模分布的虚拟机反复运行测试30次，再统计测试数据的均值.同时假设每个物理主机服务器容纳4个虚拟机.虚拟机的配置分别是：带宽(度量单位：GBs/day)∈[1,2,2,4]、中央处理器(度量单位：MIPS)∈[1K,2K,3K,5K]、内存(度量单位：GB)∈[4,8,16,24].

4.2 效益分析

目前许多关于遗传算法的延伸研究都是在传统遗传算法基础上优化而来，正如文献[6,8]研讨的两种改进型研讨方案.因此业界经常将遗传算法作为参照标准用于衡量各类改进算法的实施成效.此外，优先适应机制是一种常用作部署虚拟机安置的启发式算法.基于此，笔者通过4个指标对比遗传算法、优先适应机制、迁置优化算法来凸显各自方案效益.

图1和图2描述了3种研究方案在受理虚拟机提请安置计算请求时整个云计算环境下的数据中心资源调度情况.所统计的数据主要考查在安置请求规模逐渐递增的情形下3种研究方案实施调度计算期间的性能差异性以及性能总体趋势.根据前文方案设计的思想以及方案实施的过程所述可知，相对于遗传算法和优先适应机制，迁置优化算法在实施虚拟机安置时不仅考虑到目标物理宿机选取(即：优质基因分析)的合理性，还考虑到了编码和交叉环节中尽可能地减少CH2 nd染色体(即：物理主机服务器节点)的冗余规模.迁置优化算法的这些思想均填补了传统遗传算法和优先适应机制的改进空间.因此从图1、2所收集的数据不难看出，部署策略曲线走势表现出了与遗传算法和优先适应机制的相对性优势.显著地提高了云计算数据中心综合资源使用率，最小化被唤醒的物理主机服务器参与到策略中.由于每个物理主机服务器资源有限，故随着提请安置计算请求的虚拟机的规模持续增加，势必要有更多物理主机服务器被唤醒参与到响应计算请求的行列中.这种规律是所有研究方案都会存在的.所以图2所示的3条曲线走势呈线性递增.随着负载增加，迁置部署策略在编码、选取、遗传环节的优势愈加明显，因此资源使用情况愈发良好.故图1所示曲线在虚拟机规模达到300个后效益更加凸显.

云计算系统中物理机负载失衡与否也是考量优化成效的重要指标.图3所示曲线即表述了在发起迁置请求虚拟机规模保持相同的前提下，3种研究方案所表现出的载荷失衡严重程度.对于优先适应机制而言，其思想为首先按照资源请求数量对虚拟机实行降序排序，一旦找到符合作为目的物理宿机要求的物理主机便开始停止后续搜寻，既便所求解具备全局性也极具偶然性.遗传算法通过编码、选择等4个环节虽然在一定程度上促进了云计算系统数据中心的服务性能，但受限于编码环节的复杂和冗余困扰而不具备普适性[19].因此这2种研究方案存在的问题很容易使负载集中于某些特定的物理主机服务器上引发负载失衡问题.而本文研究目标正是将这些欠周之处作为迁置优化算法的改造空间.

图2 3种方案的服务器唤醒情况

图3 3种方案的失衡情况

相对而言，实施迁置优化算法后云计算数据中心参与迁置虚拟机的物理主机服务器规模最小，且该算法在重载情形下的资源使用率最优.而节能成效高低与否完全取决于整个云数据中心参与工作的物理主机数量以及主机内所定义的各类资源利用率.相对于迁置优化算法而言，遗传算法和优先适应机制下被激活的工作主机服务器数量较多，加之相对较低的资源利用率所造成的浪费，都需要为此付出较高的能源代价.甚至于相关研究[20]也表明了虚拟机放置过程中云计算数据中心若无法应对物理主机节点载荷随机波动和动态虚拟放置请求时，物理主机将出现频繁开关机.这必然使得原本凸显的能耗问题被进一步加剧.据此分析，占相对优势的迁置优化算法所对应的能源消耗最低.正如图4所示的数据曲线走势，充分说明了该问题.随着虚拟安置请求的增加，用于响应该计算的开销资源也需同步增加，需要为开销和主机供给更多的能源.故曲线走势依旧总体呈现递增趋势.

图4 3种方案的能源消耗情况

5 结论

笔者从科学的角度为云计算环境中的虚拟机构思一种迁置优化算法以实现高效率的资源调度.该算法在总结传统研究方案改进空间的基础上，以绿色指标为导向探讨了一种通过对优质的物理主机节点展开科学性评估后再用于高效地实施虚拟机迁置请求.测试表明，所研究的算法在应对云计算资源调度中具有切实的有效性与可行性.