云环境下基于化学反应优化算法的多目标BoT调度

马敬敬，王文秀

（河南大学 计算机与信息工程学院，河南 开封475000）

云计算作为一种新的大规模分布式计算范式，通过对硬件和软件的虚拟化，可实现软件、服务器和网络的充分融合和共享，提供不同层次的服务，提高资源利用效率，降低运营成本和能耗。随着云计算的出现及按照其对按需配置计算资源的承诺，传统形式的网格计算将极大可能逐渐转向云计算。云计算带来的“按使用付费”的经济模式，使人们只需投入很少的管理工作，或与服务供应商进行很少的交互就能够快速得到所需资源［1］。如今，云计算已在商业应用和科学研究领域中得到了广泛关注。云环境提供了一个方便、灵活的能够部署各种应用，特别是BoT（bag of tasks）应用的平台。然而，基于服务结果的云基础设施的需求较高，为此建立的巨大的数据中心会消耗大量的电力，不仅增加了云服务提供商的运营成本，降低了利润，也导致了较高的二氧化碳排放，对环境极其不友好［2］。根据Pike Research研究，仅在2010年，全世界的数据中心就消耗了201.8 TWh的电能，能源支出达到233亿美元［3］。欧盟发表的一份报告显示［4］，为有效减缓和应对气候变暖趋势，控制温室气体排放，国际组织已经将避免2℃全球变暖作为温室气体减排的主要目标。因此，有必要从能耗的角度，从整个产业链出发，找到一种绿色、节能、环保的云计算实现途径。

作为云系统的重要组成部分，任务调度的优劣影响着云系统的整体性能和服务质量，故任务调度问题一直是云计算研究中的重点。目前的调度策略的主要优化目标包括执行时间、执行费用和负载均衡，其中执行时间和执行费用是为了满足用户的服务质量，而负载均衡是为了保证整个云环境的稳定性。关于云计算的任务调度尚处于初步研究的阶段，有关这一问题的算法研究成果还比较少，而且现有的大部分云任务调度算法考虑的因素都较少。针对这个问题，我们提出了用化学反应优化算法［5］解决任务调度中的多目标优化问题。该算法以任务量和资源数作为优化目标，并结合负载均衡作为约束条件。

本文组织结构如下：介绍任务调度相关研究工作，给出多目标任务调度模型及其相关定义，给出对CRO算法的简短介绍和对CRO算法框架的详细介绍，给出实验结果及分析。

1 相关研究

在过去的几年中，在异构计算环境中基于不同的优化指标或用户约束下的BoT任务调度被广泛研究。解决调度问题，找到最佳的任务和资源是NP完全问题。为获得最佳组合，人们提出了许多启发式算法，如Min-min 算法、Max-min 算法和 Sufferage 算法等［6］。这些启发式算法被广泛地应用在分配独立处理器的异构计算系统中。之后，这些算法又被改进，以适应不同的计算环境或调度方案。E.K.Tabak等［7］结合新提出的Min-min算法、Max-min算法以及Sufferage算法，获得了两种混合算法。Oprescu等［8］提出的BaTS（预算约束调度）可以将大量任务安排到具有不同CPU性能和成本的多个云上，在满足一定预算的基础上，最大限度地减少完工时间。同时，在文献［9］中，刘英英针对负载均衡和经济两方面对Min-min调度算法进行了改进，以减少完工时间和提高资源的利用率（LBIMM）。

近年来随着AdHoc网络以及无线传感器网络（WSN）的快速发展和在网格中的广泛应用，能量消耗问题在网格资源调度中的重要性逐步增加。比如，在AdHoc网格中，资源节点的能量都是有限的，故在实现资源调度过程中，能量约束是一个不可忽视的因素。因此施步青［10］提出了一种基于能量优化的网格资源调度模型并在此基础上提出改进的网格资源调度算法。S.K.Garg等［11］提出了一个较优的调度策略，该策略利用云提供商的多个数据中心的异构性实现更高的利润和更少的碳排放量。

网格的复杂性及其资源的多样性和广域性决定了网格环境下BoT调度的复杂性，其关键在于需要综合考虑网格环境的各项特征对于调度的影响。传统的实时任务调度方法在网格环境下已不再适用,而启发式方法是解决这类问题的一个很好选择。如Liu H.等［12］提出了一种基于粒子群优化（PSO）的计算网格调度作业的新方法，它动态地生成最佳调度，以便在最短的时间段内完成任务及以有效的方式利用资源。在算法设计的过程中，作者虽然将网络带宽、网络延迟和执行时间作为三重约束条件，但是在寻求最优解的时候只考虑了执行时间这一个目标。李建锋等［13］提出了一种基于遗传算法的云任务调度策略，它将任务的最大完工时间最短作为调度策略的优化目标，同时又将任务的平均执行时间作为评价调度算法优劣的重要标准。虽然此算法考虑了两个目标，但它考虑的都是执行时间，没有考虑到其他的约束因素。

针对以上问题，我们有必要探索新的元启发式算法来解决基于云环境下的多目标BoT调度问题。A.Y.S.Lam等［14］开发了一种新型元启发式算法，它模拟化学反应（CRO）中分子间的相互作用以寻求最小势能的过程。近年来CRO已经成功地解决许多复杂问题，尤其是在调度问题中［15］，CRO的性能优于已知的其他优化算法。在本文中，我们将能耗、二氧化碳排放量和利润作为优化目标，对CRO算法进行优化。

2 问题描述

在现实中，每个云供应商都拥有多个数据中心，这些数据中心分布在世界各处。每个区域会提供不同类型的不同价格的虚拟实例，这样，用户在不同域请求同一实例时，由于地域分布和网络条件的不同会有完全不同的体验。因此，为调度任务选择虚拟资源时的首要任务是确定一个合适的域来提交请求。

本文采用如图1所示的调度模型。当接收到任务资源发来的请求时，调度程序就将任务提交到不同的数据中心。在这些数据中心中，该任务会被分配给一组可用资源来执行。

图1 调度模型

在本文中，N个任务可以用一个集合 T＝{T1，T2，…，TN}来表示，所有资源的集合表示为集合R={R1，R2，…，Rn}。每一个任务Ti都有一个属性，即任务的工作量，用于表示数以百万计的指令。而资源模型是由许多在不同地点的云端系统构成的，这意味着每一个资源都有一定的属性。

在能耗模型中，需要计算能耗来源，云数据中心冷却系统的能耗也需要考虑在内。因为不同地区温差很大，所以用于冷却的能耗是与数据中心所处的地理区域紧密相关的。制冷系数w是用于衡量冷却系统效率的指标，即CPU能源消耗量与冷却系统能源消耗量的比。w不是恒定的，是随冷却系统工作时所处区域空气温度变化的。利用w可以推断出每个数据中心冷却设备的能耗。

下面，我们将给出调度问题的能量消耗的数学描述和用于计算各候选解决方案中适度调度的函数。

CPU的能耗表示为

其中，vi是CPU消耗的静态功耗，是比例常数， f是CPU的工作频率，ej表示资源执行完所分配的任务时消耗的时间。

总能量消耗为

其中，Eij表示能耗模型在任务ti和资源ri上的能耗，为第i个任务的制冷系数。

总的二氧化碳排放量为这里，Cij表示在任务ti部署在资源ri下的二氧化碳排放量，ri表示CO2排放速率。

利润计算公式为

其中，pc是固定的价格单位，是供应商用使用云资源j执行应用程序需要支付的费用。

调度问题可以形式化为

函数的约束如下：

1）应用程序必须在截止时间之前完成，否则应用的调度会被拒绝；

2）每一个应用程序仅能分配给一个云资源执行。

式（5）、式（6）、式（7）分别表示目标函数的三个目标。式（5）表示最大限度地减少整个分布式云的能源消耗，式（6）表示减少分布式云的碳排放量，式（7）表示最大限度地提高供应商的利润。我们定义的寻找最佳的解决方案的适应度函数为

其中a、b和c表示三个目标（能耗、二氧化碳排放量和利润）的权重。

3 基于CRO的调度算法

下面我们先详细阐述化学反应优化算法的原理，再给出每个基本反应操作算子的变化。

3.1 化学反应优化算法

CRO是一个新型的以种群为基础的通过近似最优解来求解优化问题和搜索问题的算法，基本思想来源于对化学反应过程的类比。它将每一个解都模拟成一个分子，通过搜索整个解空间来寻找势能（PE）最低的分子个体。分子在独立空间内通过碰撞来产生四种化学反应，在反应过程中使得能量逐渐趋于最低，即达到寻找最小值的目的。搜索最小值的方式有两种：一种是查找局部区域最小值，即通过寻找分子的邻居分子来获取它们的势能；另一种是查找全局区域最小值，即当局部搜索中没有找到更低势能的分子个体时，可以跳出这片搜索区域而去探测另一片新的区域。在CRO的四个化学反应中，器壁碰撞和分子间无效碰撞反应属于前一种方式，而分解反应和合成反应则属于后一种方式。在搜索最小分子个体的整个过程中，参与反应的分子的能量通过不同的方式进行转换分配。

CRO初始化过程需要先初始化容器和分子，每个分子代表一个候选解，每个分子都有N维。这N维依赖于特定的研究问题，在我们研究的问题中，N就是要分配的任务。M代表种群大小。 ω表示化学反应中分子结构，即对于问题的解决方案。PE值越小意味着分子越稳定，求得的适应度越好。Ke代表分子动能，Kei为分子的初始动能。E为存储反应过程中由部分动能转化的能量。Hnum表示分子的碰撞次数。t决定参与化学反应的分子个数。在［0，1］间服从平均分布的随机数k，若k＞t，将会发生单分子反应，否则发生分子间的化学反应。α 和 β 分别决定分解和合成是否执行。α为分子碰撞次数的极限值，当分子的碰撞次数大于 α 时，将执行分解反应；β 表示分子应至少拥有的动能，若参与反应的两分子的动能均小于 β ，将执行合成反应。RKE表示分子在反应中的动能损失率。Pem为分子在反应过程中拥有的最小势能。 ω ’为分子获得Pem的对应分子结构，Be代表能量缓冲区。

3.2 CRO的四个基本反应

3.2.1 器壁碰撞

器壁碰撞属于单分子化学反应，是根据给定的一个分子结构 ω 产生新的分子结构 ω ’的局部搜索过程。如：假设当前分子结构 ω ［1 2 3 4 5 6］，数字2和5分别代表随机选择的两个任务，在碰撞反应后，任务2变化到任务5的位置，任务5变化到任务2的位置，即

3.2.2 分解反应

分解为单分子反应，对应的是全局搜索过程，由选定的一个分子结构 ω 生成两个新的分子结构如：有一个分子结构 ω 进行分解反应，将大于或等于任务总数的分配资源的索引移动几个位置，就得到两个新的分子结构。设，随机产生的两个任务是2和5，则移动后得到。

3.2.3 分子间碰撞

分子间弹性碰撞是两分子间的化学反应，是为获得新解而进行的局部搜索过程。首先给出两个分子结构然后在［1，N］的范围内随机产生一个整数p，其中N是总任务数。交换p个任务的位置，不改变分子结构中的其他任务及位置，得到新的分子结构。如：随机产生的p=2，原始的两个分子结构分子间碰撞后，前两个任务的位置发生互换，其他位置保持不变，产生了新的分子结构

3.2.4 合成反应

合成反应是分子间的化学反应过程，是通过结合两个已存在的分子结构来生成新的分子结构ω的全局搜索。在合成反应中，两个分子结构中的相同的任务被保留到下一代，其余的空余位置从［1，n］中随机产生。 例如：有两个分子结构其中相同部分是 2，4 和 5，设从［1，n］中随机产生三个数1、6和3，则新的分子结构为

3.3 算法描述

基于多目标化学反应优化算法的流程图如图2所示。算法的详细实现过程如下：

输入：一组任务和资源，指定的参数为初始种群M，能量缓冲器Be，分子反应分数t，动能损失率RKE，分解常数 α ，合成分数 β ，初始解的分子结构 ω 。

输出：输出整体的最优解和适应值。

1）初始化CRO设置，形成初始种群M，并初始化任务数资源数

2）while （迭代次数＜500） do

3）k=random（0,1）

4）if k＞t then

5）发生单分子反应

6）if满足上述的分解条件 then

7）对于解决方案进行分解反应

8）更新种群M和能量缓冲器Be

9）else

10）进行单分子器壁碰撞

11）end if

12）else

13）发生多分子反应

14）if满足合成条件 then

15）发生合成反应来更新解

16）else

17）发生分子间无效碰撞

18）end if

19）end if

20）更新解空间获取当前最优解

21）end while

22）end

图2 CRO流程图

4 实验结果及分析

4.1 实验描述

我们建立了一个模拟云计算的实验环境，用来评估所提出的基于CRO的调度算法的性能，并将该算法与GA算法［15］进行对比。在模拟中，每一个资源都有一些参数，详细设置如表1所示。在表1中，每个ID号代表1条资源，每个资源有7个参数。任务的长度在［18 000，32 000］内。CRO算法的详细参数设置如表2所示。

表1 每个资源的参数设置

表2 CRO算法参数设置

4.2 仿真结果

我们采用两种资源配置（如表3和表4所示），测试的任务数分别是 10、50、200、500和 1 000，其他参数见表1。表3给出了在资源数为5时，CRO算法和GA算法的最大适应度值和最小适应度值的比较结果。当资源数为10时，我们得到了如表4所示的仿真结果。从表3和表4可以看出，当资源数一定时，从任务数50开始，CRO和GA算法随着任务数的增加适应度值也不断增加。在表3和表4中，算法CRO和GA在任务数为10时的适应度值远远大于任务数为50、200和500时的适应度值。对比两个表的实验结果，当任务数一样时，两种算法的资源数为10的适应度值远远大于资源数为5的适应度值。从表3可以看出：对同一资源数和同一任务数，除了资源数为5、任务数为50以及资源数为10、任务数为10时，CRO算法的最大适应度值与GA相比略低外,CRO算法的结果都远优于GA算法。总体而言，当资源数一定时，不同的任务数对算法的性能有不同的影响。和GA算法相比，CRO算法可以使适应函数中的三个目标达到更好的优化效果。

为了进一步验证实验结果的可靠性和稳定性，图3显示了任务数为200时CRO和GA算法的收敛能力。收敛时的适应度值代表的是目标函数值向最优解靠近的结果。从图3中可以看出：随着迭代次数的增加，CRO和GA算法的适应度值都在降低，当迭代次数达到400以后CRO算法开始收敛，当迭代次数达到600时GA算法开始收敛了。从图4可以看出，CRO算法的收敛速度更快，并且在迭代过程中CRO算法的适应度值都高于GA。因此，CRO算法有更好的收敛性并且可更快地收敛到一个更好的解。

表3 资源数为5时各算法性能比较

表4 资源数为10时各算法性能比较

图3 不同算法的收敛性比较

5 结束语

任务调度性能的好坏对任务的执行有影响。虽然目前已经有很多关于云任务调度算法的研究，但现有的调度算法多数集中于单一目标，忽略了能耗和环境问题，不能满足当前云供应商绿色计算的需求。为了减少能源消耗和二氧化碳排放量，最大化云服务提供商的利润，我们提出了一种基于CRO解决云计算环境中的多目标优化问题的算法并进行实验模拟。实验结果表明，CRO作为一种新的元启发式优化算法和GA算法相比具有更好的性能。