云计算的资源弹性分配特征，使得企业和组织在部署应用(application)时能够根据实际业务需求分配虚拟化资源(包括CPU、内存和带宽等)，从而减少资源浪费^[1].在业务需求中，不同的服务质量(quality of service，QoS)属性的约束，如响应时间、可靠性等，主要通过应用提供商和应用使用者之间的服务等级协议(service level agreement，SLA)进行描述^{[2, 3]}.因此，在按需付费的云环境中部署应用时，如何在保证SLA的基础上优化分配虚拟化资源，从而尽可能降低应用的资源使用成本，是应用提供商提高收益的关键途径.

在现有关于虚拟化资源优化分配的研究中，应用通常为单层或多层逻辑组成结构^{[4, 5, 6]}.然而，对于由不同组件服务按照多种组合逻辑(如顺序结构、分支结构、并行结构和循环结构等)构成的基于服务的软件系统(service-based software systems，SBS)在云环境中部署时的资源优化分配问题尚缺乏深入研究.在SBS中，各组件服务的QoS与所分配的资源数量往往具有不同的映射关系，且不同程度地影响SBS的端到端(end-to-end)QoS，同时组件服务之间存在资源竞争关系，因此，SBS的虚拟化资源优化分配更加复杂.

与已有研究不同，本文针对基于SBS的云应用的资源优化分配问题，提出了一种以满足端到端平均响应时间为约束，以最小化资源使用成本为目标的虚拟化资源分配优化模型及其遗传算法的实现.在该模型中，定义了组件服务资源配置的概念，并给出了组件服务候选资源配置的确定方法，从而将资源优化分配问题转换为一个资源配置组合优化问题，进而采用遗传算法求解.实验验证了本文的资源分配优化模型的有效性，并且表明提出的遗传算法实现收敛速度快，且与线性规划算法相比，在较大问题规模上可以快速获得质量更高的解.

本节首先定义组件服务的资源配置，并给出其确定方法，进而将SBS资源优化分配建模为一个资源配置的组合优化问题.

定义1 资源配置(resource configuration，RC).RC是一个描述一定数量的虚拟资源下，组件服务平均响应时间和资源使用成本的元组，表示为RC=< K,R,Q,C>，其中，K为与组件服务对应的虚拟机部署的物理机编号；R=(r¹,r²,…,r^u)，表示资源向量，r^α(1≤α≤u)为资源α的数量；Q表示组件服务的平均响应时间；C表示R的使用成本.

为了确定组件服务的候选资源配置，需要获取任意资源向量与该组件服务平均响应时间之间的映射关系，本文称描述该映射关系的模型为组件服务的资源模型.另外，还要确定资源使用成本的计算模型，即资源定价模型.

定义2 资源模型(resource model，RM).RM是一个描述资源向量 R与组件服务平均响应时间Q之间映射关系的模型，表示为Ψ=R→Q，其中，Ψ表示R到Q的映射函数.

实际中可能有很多种影响组件服务平均响应时间的资源，为了说明资源模型的获取过程且不失一般性，本文选取4种常用的资源类型：CPU(个)、内存(MB)、带宽(MB/s)和磁盘I/O(MB/s)，且分别以r¹,r²,r³,r⁴表示.这里，采用统一的度量标准(如MIPS)将不同架构和计算能力的CPU转换为具有相同计算能力的CPU^[7].

由于资源的基本分配单位粒度较小，不同资源组合会产生大量的资源向量，进而导致组合优化问题的可行解空间过大，影响求解效率.为此，本文首先采用Chi2方法^[8]将资源属性和组件服务的平均响应时间划分为多个区间，并用区间均值作为该区间对应的属性值，然后采用SVM方法^[9]训练组件服务的执行日志(其中记录了资源数量及相应的组件服务平均响应时间等信息)，从而获得资源向量与组件服务平均响应时间的映射关系.

实际中，不同的资源类型可以采用多种定价模型，如线性定价模型、指数型定价模型等^[10].本文假设资源使用成本与资源分配量、资源使用时长呈正比，并对所有资源类型均采用线性定价模型，可得资源r^α(1≤α≤4)的使用成本：

根据资源模型和资源定价模型，遍历所有物理机计算可得任意组件服务的候选资源配置.

本文SBS资源优化分配问题的目标是最小化资源使用成本，同时满足应用的SLA.因此，给定一个由m个组件服务S₁,S₂,…,S_m构成的SBS，SLA约定端到端平均响应时间Q≤Qmax，其中Qmax为最大平均响应时间.云环境中的物理机集合Pm= {Pmk|1≤k≤n}，Pmk的资源r^α(1≤α≤4)的可用总量为R^α_k，组件服务S_i的候选资源配置集合RC(S_i)={rc_i,j|1≤j≤n_i} ，其中rc_i,j=< k_i,j, r_i,j,q_i,j,c_i,j>，r_i,j=(r¹_i,j,r²_i,j,r³_i,j,r⁴_i,j)，c_i,j=.以解向量x_i,j表示组件服务S_i是否选择第j个候选资源配置，则优化模型为

根据优化模型可知，组件服务的资源配置组合优化是个NP难问题，而遗传算法是解决最优化问题的有效方法之一，因此本文采用遗传算法进行求解.首先，采用一维编码方式对个体进行二进制编码，基因位取值满足式(5)和式(6)；然后，采用通用的遗传算子进行种群的繁殖，为了减少无效解，对交叉操作和变异操作进行了一定限制，使其满足优化模型的约束条件.另外，在适应度函数中引入了罚函数，从而降低在解空间中无对应可行解的个体的适应度，加快收敛速度.

个体编码由m段基因连接组成，总长度等于，第i段基因对应组件服务S_i.以g_i,j表示第i段基因中的第j个基因位，则g_i,j∈{0,1}，如果S_i的第j个资源配置被选中，则g_i,j=1，否则g_i,j=0.另外，根据约束条件式(5)，任意i段基因中只能有一个基因位取值为1.图 1给出了个体编码示意图.

图 1(Figure 1)

Fig. 1

图 1 个体编码 Fig. 1 Individual encoding

为了评价个体g的质量，定义适应度函数

引入罚函数是为了降低不满足优化模型约束的个体被遗传到下一代的概率.

选择算子采用随机遍历抽样，在选择时采用随机等距的方式抽取个体，从而更好地保持种群多样性.

交叉算子采用单点交叉.为了使新的个体仍然满足约束条件式(5)，将交叉点的取值限制为不同段基因的分割点.

变异算子采用位点变异，将变异基因位的值取非.与交叉算子类似，为满足式(5)，如果变异后的值为1，则将该基因位所属基因段中其他基因位的值均置为0，否则，则在变异后，随机从该基因位所属基因段中的其他基因位中选择一个并取非.

最后，本文通过设定遗传代数作为终止迭代的条件，相比通过设定精度来终止迭代，可以防止由于种群过大、要求精度较高而引起的搜索时间过长的情况.

本节主要验证本文的遗传算法的收敛速度，并将其与线性规划算法在SBS资源分配优化模型上解的质量和求解效率两方面进行比较.

硬件环境：CPU为i5 M560 2.67GHz，RAM为6.0GB；软件环境：Windows 7 Ultimate，JDK 1.6.7，IDE Eclipse 3.6.

实验以图 2中的SBS为例，将其中的组件服务实现为4类Web服务：CPU密集型(S₁,S₂)、通信密集型(S₃)、I/O密集型(S₄,S₅)和其他型(S₆,S₇)，从而形成多样性的资源需求.为了获取用于构建资源模型的组件服务执行日志，实验采用KVM虚拟机实现不同的资源状态(142种)，在不同资源状态上分别多次调用各组件服务，并统计为各组件服务分配不同数量资源时的平均响应时间.基于获取的组件服务执行日志，根据1.1.1节的方法建立资源与组件服务平均响应时间的关系.

图 2(Figure 2)

Fig. 2

图 2 SBS的虚拟化资源分配示例 Fig. 2 An example of virtualized resource allocation for SBS

由于本实验目的是验证遗传算法在求解资源分配优化模型时的可用性和有效性，因此采用仿真数据即可.实验中，云环境中的物理机个数取值为10,15,20,25,30,35,40,45,50，且各物理机不同类型的资源数量在某个范围内随机取值，取值范围及资源的单位价格见表 1.

表 1

Table 1

表 1(Table 1)

表 1 物理机可用资源与资源单位价格 Table 1 Available resource of physical machines and price/unit of resource 属性 CPU 内存 带宽 磁盘I/O 个 MB MB·s-1 MB·s-1 单位 价格 4 2 3 2 可用资 源范围 2~14 500~4000 100~1000 100~500

表 1 物理机可用资源与资源单位价格 Table 1 Available resource of physical machines and price/unit of resource

遗传算法的主要参数设定：种群大小P=50，交叉概率Pc=0.75，变异概率Pm=0.1，终止代数T=100.

该组实验考察本文提出的遗传算法的收敛速度，这对于在合理时间内求得最优解具有重要意义.为了使算法能以较大概率收敛到最优解，本文在适应度函数中引入了罚函数，以物理机个数取值15为例，与未采用罚函数的适应度函数相比较，结果如图 3所示.

图 3(Figure 3)

Fig. 3

图 3 遗传算法的收敛性 Fig. 3 Convergence of genetic algorithm

由图 3可知，引入罚函数时的种群平均适应度值明显要高于未引入罚函数时，这是因为在解空间中没有可行解的个体不会遗传到下一代，因此可在一定程度提高收敛到最优解的概率.

该组实验通过物理机数量在10~50之间的变化，与常用的求解约束优化问题的线性规划算法在解的质量(以部署SBS的资源使用成本度量)和求解效率(以求解优化模型消耗的时间度量)两方面进行比较.

1) 部署SBS的资源使用成本.遗传算法和线性规划算法求得的最小资源使用成本对比如图 4所示.

图 4(Figure 4)

Fig. 4

图 4 最小资源使用成本对比 Fig. 4 Comparison of the lowest resource costs

根据图 4可知，对于不同的物理机数量，遗传算法得到的最小资源使用成本略高于线性规划算法，而且随着物理机数量的增加，两种算法得到的最小资源使用成本均呈降低趋势，这是由于解空间扩大增加了求得更优解的可能性，同时物理机增多也会有助于减少资源配置之间的冲突，进而产生更多的可行解.

2) 求解优化模型消耗的时间.在求解优化模型时，遗传算法和线性规划算法消耗的时间对比结果如图 5所示.

图 5(Figure 5)

Fig. 5

图 5 消耗时间对比 Fig. 5 Comparison of solving time

根据图 5可知，两种算法的时间消耗均随着物理机数量的增加而呈上升趋势.当物理机数量较小(小于25)时，线性规划算法的时间消耗要低于遗传算法；而当物理机数量较大时，线性规划算法的时间消耗显著增加，此时遗传算法的效率要优于线性规划.

综上实验结果表明：本文的遗传算法能够在可接受的时间内收敛到最优解，并且适应度函数中的罚函数对于提高算法的收敛速度具有比较明显的效果；遗传算法求解得到的资源分配方案的资源使用成本比较接近线性规划得到的最优解； 与线性规划相比，当组件服务的候选资源配置较多时，本文的遗传算法可以在更短时间内求得最优资源配置组合.

本文针对基于SBS的应用在云环境部署时的资源优化分配问题，提出了一种基于资源配置的组合优化思想、以最小化资源使用成本且满足应用SLA和物理机资源约束的资源分配优化模型，并根据该优化模型的特点给出了改进的遗传算法.实验验证了本文提出的优化模型的有效性，并且表明其基于遗传算法的实现具有较快的收敛速度，同时可获得接近线性规划最优解的资源配置组合，但在问题规模较大时求解效率明显优于后者.