冒佳明 王鹏飞 赵然

摘要

混合云融合了私有云与公有云，同时兼具二者优势。然而，由于其中私有云的任务处理能力有限、任务的到达具有非周期性，动态调度所有到达任务以获得较高效益是具有挑战性的问题。针对此问题，本文建立了基于延时服务与私有云成本的分布式异构云环境模型，提出了一种私有云效益最大化算法，该算法的核心在于使用改进的模拟退火粒子群算法，对每一次迭代进行优化从而实现较优的调度效果。

【关键词】混合云 效益最大化 任务调度 启发式算法

1 简介

随着云计算技术的日益成熟和持续推广，更多用户选择将其应用托管至云平台中运行。云可以被分为三类：公有云、私有云与分布式异构云（混合云）。私有云可保证应用的安全与兼容性。公有云可保证丰富的计算资源与体验。混合云融合私有云和公有云，成为了近年来云计算的主要发展方向与模式，为更多企业级用户采用。如图1所示，混合云融合了二者的优点，不仅确保了用户的体验而且确保应用的安全性。

基于混合云架构的任务调度问题是合理调度混合云系统资源的核心问题之一。从云用户的角度看，如何合理利用混合云资源，在保证任务完成的同时最大化系统效益，是开展任务调度的核心问题。然而，由于任务的到达具有非周期性的特点，且难以预测任务的资源需求形式与规模。因此，在保证任务响应时延的前提下，如何动态调度所有任务以获得较高的总体效益是面向混合云架构的任务调度的基本问题。

从混合云执行任务的角度看，完成一定的任务具有确定的效益。而在成本方面，私有云的资源价格相比公有云要低，且利用公有云资源需要更多的传输开销与时间开销，可能会导致任务无法及时完成。但是，私有云资源的有限定迫使公有云必须要纳入到调度的资源池内。针对混合云调度的特点，本文综合考虑公有云虚拟机价格的多样性、公有云与私有云之间的数据传输速率和私有云中波动的价格成本，制定一项综合模型用以描述分布式异构云的环境;并提出私有云效益最大化算法来执行任务调度。

2 私有云效益最大化问题描述

混合云的体系架构如图2所示。该架构分为两部分，其中一部分是私有云模块，另一部分是公有云模块。任务通过网络到达混合云中的私有云模块，保存至先进先出的任务队列等待调度。任务调度器综合分析私有云的剩余资源信息与私有云的未来电价信息对任务进行调度。在私有云容纳范围之内，将部分任务调度至其中，并把其余任务调度至公有云模块中。

假设CP={CP₁，CP₂，…，CP_n}为混合云计算中心集合，CP₁为私有云计算中心，CP₂，…，CP_n为公有云计算中，n为云计算中心的数量。用CP_kv表示CP_k中第v類虚拟机的单位时隙价格;CPU_v，MEM_v和POW_v分别代表了第v类虚拟机的CPU数量，内存大小与功耗;CPU_total，CPU_t^rest，MEM_total和MEM_t^rest分别表示私有云的总CPU资源，私有云在t时隙剩余的CPU资源，私有云的总内存资源和私有云在t时隙剩余的内存资源;B和B_k则分别代表了私有云的服务延时范围与公有云k的服务延时范围;P_t代表了私有云在t时隙中的电价。假设T为一个云计算任务，则该任务到达云计算中心的时隙、目标虚拟机、需要运行时间和存储空间大小分别用T_A，T_V，T_R和T_S表示。

对于一次任务调度，用Income表示的收入，Cost表示花费，Benefit表示效益。由问题定义可得，任务调度的收入Income由所有到达任务的目标虚拟机、任务的运行长度决定。同时收入Income可定义为在时隙t任务被调度至私有云与公有云中用户所需要支付的费用之和，如下表示：

对于混合云中的成本Cost可表示为任务在私有云运行消耗电费与向公有云支付的费用之和，表示如下：

其中，中POW，表示该类虚拟机耗电量，P_t+j表示t+j时隙的电价·因此，该问题表示如下：

3 效益最大化优化算法

本问题的目标问题为最大化Benefit，当中决策参数为d_t，d_tⁱ，Y_t^jk，dk_t，dk_tⁱ都为整数型变量，同时该参数受到多条件约束。可将该问题规约至整数规划问题（integer linearprogramming，ILP）。启发式算法常用于解决整数规划问题，是由于该类算法一般不依赖于一些特定的数学结构并且有较好的鲁棒性和易于实现，基于此优点，可选择启发式算法来解决本问题。大量的实验表明，粒子群算法比其它启发式算法的计算时间快，但是其针对大规模优化问题的最终解往往偏差较大。本节提出了私有云效益最大化算法，该算法当中使用改进的模拟退火粒子群算法来进行迭代优化。其具体算法如算法I所示。

对于ISAPSO算法，在粒子初始化时，算法依据到达任务的总需求资源和私有云剩余资源的比值K进行初始化。在对粒子的速度进行更新时，使用模拟退火的规律与后期局部搜索的方式对粒子的速度进行更新。在对粒子的位置进行更新时，使用离散粒子群的位置更新方式对粒子进行更新。即对粒子的位置进行整数化。

4 结论

本文研究了混合云环境下的异构任务调度研究，以最大化系统收益为基础，在考虑异构云特征及任务响应时间约束的基础上，提出了一种基于粒子群优化的效益最大化算法，改算法在保证完成任务响应的基础上，可以实现较优的系统效益。

参考文献

[1]李智勇，陈少森，杨波，李仁发.异构云环境多目标Memetic优化任务调度方法[J].计算机学报，2016，39（02）：377-390.

[2]Q.Zhang，M.Zhani，R.Boutaba，and J.Hellerstein，“Dynamic heterogeneity-aware resource provisioning in thecloud，”IEEE Trans.Cloud Comput.，Vol.2，no.1，pp.14-28，Jan.2014.

[3]L.F.Bittencourt and E.R.M.Madeira，“HCOC：A cost optimizationalgorithm for workflow scheduling inhybrid clouds，”Journal of InternetServices and Applications，Springer，Vol.2，issue 3，pp.207-227，December 2011.