MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}}); function MyAutoRun() {    var topp=$(window).height()/2; if($(window).height()>450){ jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); }  }    window.onload=MyAutoRun; $(window).resize(function(){ var bodyw=$win.width(); var _leftPaneInner_width = jQuery(".rich_html_content #leftPaneInner").width(); var _main_article_body = jQuery(".rich_html_content #main_article_body").width(); var rightw=bodyw-_leftPaneInner_width-_main_article_body-25;   var topp=$(window).height()/2; if(rightw<0||$(window).height()<455){ $("#nav-article-page").hide(); $(".outline_switch_td").hide(); }else{ $("#nav-article-page").show(); $(".outline_switch_td").show(); var topp=$(window).height()/2; jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); } }); 基于混合遗传模拟退火算法的SaaS构件优化放置
  软件学报  2016, Vol. 27 Issue (4): 916-932   PDF    
基于混合遗传模拟退火算法的SaaS构件优化放置
孟凡超1, 2 , 初佃辉1, 李克秋2, 周学权3    
1. 哈尔滨工业大学(威海) 计算机科学与技术学院, 山东 威海 264209;
2. 大连理工大学 计算机科学与技术学院, 辽宁 大连 116024;
3. 哈尔滨工业大学(威海) 经济管理学院, 山东 威海 264209
摘要: 目前,对于SaaS优化放置问题的研究都是假定云环境中的虚拟机的种类和数量都是确定的,即,在限定的资源范围内进行优化.然而,在公有云环境下,SaaS提供者所需要的云资源数量是不确定的,其需要根据IaaS提供者所提供的虚拟机种类以及被部署的SaaS构件的资源需求来确定.为此,站在SaaS提供者角度,提出一种新的SaaS构件优化放置问题模型,并采用混合遗传模拟退火算法(hybrid genetic and simulated annealing algorithm,简称HGSA)对该问题进行求解.HGSA结合了遗传算法和模拟退火算法的优点,克服了遗传算法收敛速度慢和模拟退火算法容易陷入局部最优的缺点,与单独使用遗传算法和模拟退火算法相比,实验结果表明,HGSA在求解SaaS构件优化放置问题方面具有更高的求解质量.所提出的方法为SaaS服务模式的大规模应用提供了理论与方法的支撑.
关键词软件即服务(SaaS)    SaaS构件优化放置    虚拟机网络图    混合遗传模拟退火算法    
Solving SaaS Components Optimization Placement Problem with Hybird Genetic and Simulated Annealing Algorithm
MENG Fan-Chao1, 2 , CHU Dian-Hui1, LI Ke-Qiu2, ZHOU Xue-Quan3    
1. School of Computer Science and Technology, Harbin Institute of Technology at Weihai, Weihai 264209, China;
2. School of Computer Science and Technology, Dalian Institute of Technology, Dalian 116024, China;
3. School of Economics and Management, Harbin Institute of Technology at Weihai, Weihai 264209, China
Foundation item: National Key R&D Plan Project of China (2014BAF07B02); National Natural Science Foundation of China (61432002); Major Scienece & Technology Specific Project of Shandong Province (2015ZDXX0201B02); Natural Science Foundation of Shandong Province (2015ZRA10032)
Abstract: Current researches on SaaS(software as a service) optimization placement mostly assume that the types and number of virtual machines are constant in cloud environment, namely, the optimization placement is based on the restricted resource. However, in actual situation the types and number of virtual machines are unknown, and they need to been calculated according to the resource requirement of components deployed. To address the issue, from the view of SaaS providers, this paper proposes a new approach to SaaS optimization placement problem that not only is applied to initial deployment of SaaS, but also is applied to component dynamic deployment in the running phase of SaaS. A hybrid genetic and simulated annealing algorithm(HGSA) is used in this approach that combines the advantages of genetic algorithm and simulated annealing algorithm, and overcomes the problems of the premature of genetic algorithm and the lower convergence speed. Compared with the separated using of genetic algorithm and simulated annealing algorithm, the experimental results show that HGSA has higher quality in solving the problem of SaaS component optimization placements. The approach proposed in this paper will provide the support of theory and method for the large-scale application of SaaS service mode.
Key words: software as a service(SaaS)    SaaS component optimization placements    virtual machine network graph    hybrid genetic and simulated annealing algorithm    

随着云计算产业的发展,云计算逐步从概念走向实际应用,越来越多的传统软件提供商正在将其应用向云服务模式迁移.这些应用被部署在IaaS(infrastructure as a service)提供商或者自己的云基础设施上,通过互联网,以按需、易扩展的方式向客户提供服务.被部署在云中的应用是以SaaS(software as a service)模式对外提供服务.在SaaS服务模式下,使用SaaS应用的客户不需要购买完整的软件产品,也不需要配备相应的硬件系统和维护人员,只需通过互联网,按需租用即可,这对于成本预算有限、技术条件不足的中小企业来说,具有很强的吸引力.与传统的软件模式相比,SaaS具有部署时间短、成本低、使用方便等优势,因此,其市场应用前景非常广阔,被认为是未来应用软件的发展趋势[1].

当传统软件提供商在向SaaS服务模式迁移时,所面临的一个重要问题是:如何根据需要部署的SaaS应用中每个构件的资源需求来确定最优的SaaS构件放置方案,即:选择哪些类型的虚拟机?每种虚拟机的数量是多少?每个被选择的虚拟机上放置哪些构件?如何放置才能够在满足每个构件资源需求的条件下,使得总的云资源使用成本最低?制定优化的SaaS构件放置方案是提高云资源利用率、降低运营成本的一项重要手段,具有十分重要的应用价值.尽管目前已经提出了许多SaaS构件优化放置方法,但是这些方法都假定虚拟机的类型和数量是确定的,即,在限定的云资源上进行优化放置,因此在实际应用中还存在许多问题.例如,SaaS提供者在将其SaaS应用部署到IaaS提供者的云环境时,其只知道IaaS提供商所发布的虚拟机种类和价格,例如,亚马逊EC2的m1.small,m1.large,m2.x large等,但是所需要的每种类型的虚拟机的数量是未知的,它需要根据构件的资源需求来确定.尽管目前许多IaaS提供商也提供了相应的虚拟机选择方案,但是这些方法大都是简单的资源匹配,很难满足大型复杂企业级SaaS应用的部署需求.SaaS构件优化放置问题是一个NP问题[2],针对该问题,本文提出一种基于混合遗传模拟退火算法的SaaS构件优化放置方法,其目标是提高云资源利用率、降低云资源使用成本.该方法既可以应用于SaaS应用的初始部署,也可应用于SaaS运行阶段的动态部署.

1 相关工作

针对SaaS优化放置问题,国内外学者已经展开了许多研究工作.根据放置的粒度,可分为租户放置、构件放置和应用放置这3个层次.

租户放置是指建立租户与SaaS应用或构件实例之间的服务关系,即,哪些租户的服务请求被分配到哪些SaaS应用或构件实例上执行.租户优化放置的一个主要目标是:在满足每个租户服务质量需求的条件下,使得现有的云资源数量能够支持更多的租户和并发用户请求.针对租户放置问题,目前已提出了多种优化策略和算法,例如启发式算法[2]、遗传算法[3]、准入控制策略[4]、分等级策略[5]等.

应用放置是指,建立SaaS应用与IaaS层的虚拟机之间的部署关系[6],应用放置主要适合于粒度比较小的SaaS应用,而对于大型复杂企业级SaaS应用来说,由于单个虚拟机的资源能力难以满足整个SaaS应用的资源需求,因此需要将SaaS应用分解为一组可独立部署的构件,这些构件被放置在多个虚拟机上运行.此时,SaaS应用放置问题可转化为SaaS构件放置问题.SaaS构件放置是指建立SaaS应用中的构件与IaaS层的虚拟机之间的部署关系[7],即,哪些构件被部署在哪个虚拟机上执行.由于同一个SaaS应用被分布式地部署在多个虚拟机上执行,因此,如何提高整个应用的性能是一个需要考虑的重要问题[8].构件优化放置的主要目标是,在保证每个租户的服务质量需求的前提下提高云资源利用率、降低云资源使用成本.

本文主要研究构件优化放置问题,针对该类问题,目前已经提出了许多相应的方法.Yusoh提出了一种组合SaaS应用放置方法(SPP),SPP分为初始放置和资源优化两个过程:初始放置的目标是确定如何将服务/数据构件放置到相应的计算/存储服务器上,使得整个SaaS应用的执行时间最少;资源优化的目标则是通过调整运行阶段构件的放置方案来提高资源的利用率、减少运营成本[7].Moens采用特征模型来描述SaaS应用的构件及其关系,并采用整数线性规划和启发式方法对问题进行求解[9].Zhu针对云数据中心的应用构件放置问题,提出了一个基于MIP的求解算法[10].Jin针对跨多个云数据中心的应用构件放置问题提出了一种分布式方法,并给出了相应的模拟分析方法[11].Sailer提出了一个基于图的云服务放置方法,该方法采用图来描述业务支持的服务(BSS)、操作支持的服务(OSS)以及它们之间的映射,并提出了一种基于服务需求和数据中心资源类型的云资源分配算法[12].

尽管目前已经存在许多求解构件优化放置的算法,但是这些算法都是将虚拟机的类型和数量看作是固定的常量,该类问题可以抽象为多背包问题(multiple knapsack problem,简称MKP),MKP是一个NP问题[13].目前,求解MKP的方法主要有精确算法[13]、启发式算法[14]、遗传算法[15]和蚁群克隆算法[16]等.MKP的目标是使装入多个背包中的物品的总价值最大或者物体放置得更佳均衡,由于背包的数量是有限的,因此有些物体不能被装入任何包中.本文所提出的SaaS构件优化放置问题也可以看作是一个特殊的背包问题,我们称其为多维多类背包问题(multidimensional multiple-class knapsack problem,简称MMCKP),其中,构件可以看作是物品,而虚拟机模板则看作是背包的类型,不是具体的背包.另外,物品和背包的属性都是多维的.与传统的MKP问题不同的是,MMCKP要求所有的物品都必须被放入到一个具体的背包中,其目标是使用背包的成本最低.另外,由于SaaS构件优化放置问题不仅要考虑虚拟机的使用成本,而且还要考虑不同虚拟机之间的网络通信成本,因此,其问题的复杂度要比MKP更高,目前并未见到相关文献解决此类问题.

SaaS构件放置问题是一个NP问题,当问题的规模较大时,采用枚举等精确算法的运行时间代价比较高,很难满足实际应用的需求.因此,需要采用相应的近似算法对其进行求解.目前,求解SaaS构件优化放置问题的主要近似方法有启发式算法[2,9]和遗传算法(genetic algorithm,简称GA)[7]等进化算法.由于GA在生成初始解时已经采用了相应的启发式规则,因此在解决构件放置问题时,其求解质量比单纯采用启发式算法的效果要好. GA是解决离散优化问题的一种常用的方法,它通过选择、交叉、变异等进化操作来实现群体的协同进化.GA具有较强的全局搜索能力,但其局部搜索能力较差,容易产生“早熟”收敛问题[17].由于本文所提出的构件放置问题中虚拟机的数量是不确定的,因此染色体中每个基因的取值范围较大,采用交叉操作会使虚拟机的范围变大,其求解质量较低.另外,由于本文所提出的构件优化问题不仅考虑新放置的构件和新创建的虚拟机,同时还需要考虑已创建的虚拟机和已放置的构件,因此在产生新解时,许多虚拟机已经放置了构件,尽管这些虚拟机的可用资源量已经不具备放置资源需求量较高的大粒度构件的条件,但仍有可能放置一些资源需求量较小构件的条件.因此在解的搜索过程中,如果只采用遗传算法的随机交叉、变异等操作来产生新解,其错误率较高,进而影响算法的效率和求解质量.

为了克服遗传算法在求解SaaS构件优化放置问题方面的不足,本文将遗传算法与模拟退火算法(simulated annealing algorithm,简称SA)相结合,取长补短,提出了一种求解SaaS构件优化放置问题的混合遗传模拟退火算法(hybrid genetic and simulated annealing algorithm,简称HGSA).SA是对热力学中退火过程的模拟,它是一种在某一给定的初始温度下,通过缓慢下降温度参数,并根据相应的概率接受准则在解空间中随机寻找目标函数全局最优解的优化方法.SA具有较强的局部搜索能力,但其全局把握能力较弱[18].HGSA是将GA与SA相结合而构成的一种优化算法,它克服了GA收敛速度慢和SA容易陷入局部最优的缺点,从而提高了问题的求解质量[19].混合遗传模拟退火算法目前已在许多领域得到应用,并取得了较好的效果[20, 21, 22].例如:Ren采用混合遗传模拟退火算法以解决电子商务供应链环境下具有返程的本地库存车辆路线优化问题[20];Deb利用混合遗传模拟退火算法解决计算机辅助计划中零件装配序列规划问题[21];McCall提出了一种并行混合遗传模拟退火算法来求解计算网格中的Q3AP问题[22].由于问题领域的不同,因此针对不同问题的混合遗传模拟退火算法的结构和流程也不完全相同.本文针对云计算领域中SaaS构件放置问题的特点,提出了一种基于二元组的染色体编码方法来表示虚拟机类型和虚拟机,并设计了4种邻域搜索规则来改善种群中每个个体的质量,避免了交叉操作所导致解的质量下降问题.与单独使用遗传算法和模拟退火算法相比,实验结果表明,HGSA具有较高的求解质量.

2 SaaS构件优化放置问题描述

SaaS构件优化放置是指在SaaS应用的初始部署或者运行阶段,SaaS提供者根据部署的每个构件的资源需求以及现有云环境中构件的放置情况,确定一个当前的最优放置方案.图 1描述了SaaS构件优化问题的框架.从软件部署角度来看,一个SaaS应用可以抽象为一个图结构,称为构件关系图,其中,图的顶点代表构件,边代表构件之间的连接关系.同时,SaaS构件放置方案也可表示为一个图结构,称为虚拟机网络图,其中,图的顶点代表包含一组构件的虚拟机,边则代表虚拟机之间的通信链路,因此,构件放置可以看作是对构件关系图的划分,每个被划分的子图被映射为一个由相应的虚拟机模板所创建的虚拟机,构件之间的连接关系被映射为虚拟机之间的通信链路.虚拟机是由相应的虚拟机模板创建的,不同的虚拟模板具有不同的资源配置和价格.由同一虚拟机模板所创建的虚拟机具有相同的资源配置和价格.如果被放置在两个不同虚拟机上的构件之间存在连接关系,则这两个虚拟机之间存在通信链路.为了降低网络通信成本,我们尽量将具有紧密耦合关系的构件放置到一个虚拟机中.但是虚拟机的资源需求会受到其所属的虚拟机资源能力的约束,因此,SaaS构件优化放置的关键就是确定一个最优的构件关系图划分,该划分使得虚拟机网络的资源使用成本最低.该问题是一个NP问题.

Fig. 1 Frame of SaaS component optimal placement problem 图 1 SaaS构件优化放置问题框架

下面我们给出SaaS构件优化放置问题中所涉及到的一些基本概念的定义.

定义1(构件关系图). 构件关系图可以定义为G=(C,E),其中,

C=CACB为构件的集合,CA为已放置的构件集合,CB为新放置的构件集合;

E={(c,c')|c,c'∈C}为构件之间的连接关系集,对于∀(c,c')∈E,表示从cc'存在连接关系,对于∀cC,rc(c)为c的计算资源消耗量,rm(c)为c的内存资源消耗量,rd(c)为c的存储资源消耗量;对于∀(c,c')∈E,rt(c,c')表示从cc'的网络通信带宽消耗量.

构件放置的一个难点在于,事先并不知道每种虚拟机的数量,因此,我们首先需要确定每种虚拟机模板所要创建的虚拟机的数量.假设有n种虚拟机模板,令VC={vc1,vc2,…,vcn}表示虚拟模板的集合,其中,vci表示第i (i=1,2,…,n)种虚拟机模板,令rc(vci)表示vci的计算资源提供量,rm(vci)表示vci的内存资源提供量,rd(vci)表示vci的存储资源提供量,p(vci)为vci的资源使用成本.

我们通过n个非负整型决策变量S={s1,s2,…,sn}来表示由虚拟机模板所创建的虚拟机数量,如果si=0,表示没有选择vci创建虚拟机.令VM=VMAVMB=VM1VM2∪…∪VMn表示放置构件的虚拟机集合,其中,VMA表示已创建的虚拟机集合,VMB表示需要新创建的虚拟机集合,VMi表示由vci所创建的虚拟机集合,如果si=0,则有VMi=∅,即,不存在类型为vci的虚拟机;否则,VMi={vmi1,vmi2,…,$v{m_{i{n_i}}}$},其中,vmij(j=1,2,…,ni)表示由vci所创建的第j个虚拟机.对于∀vmijVMi,令rc(vmij),rm(vmij)和rd(vmij)分别表示vmij的计算、内存和存储资源提供量.由同一虚拟机模板所创建的虚拟机具有相同的资源配置和价格,即:

${r_c}\left( {v{m_{ij}}} \right) = {r_c}\left( {v{c_i}} \right),{r_m}\left( {v{m_{ij}}} \right) = {r_m}\left( {v{c_i}} \right),{r_d}\left( {v{m_{ij}}} \right) = {r_d}\left( {v{c_i}} \right),p\left( {v{m_{ij}}} \right) = p\left( {v{c_i}} \right).$

集合VMi(i=1,2,…,n)可划分为两个子集:已创建的虚拟机集合VMAi和新创建的虚拟机集合VMBi,即VMi= VMAiVMBi.令nAi=|VMAi|表示VMi中已创建的虚拟机数量,nBi=|VMBi|表示VMi中新创建的虚拟机数量,因此,ni=nAi+nBi.为了处理方便,我们规定VMi中的前nAi个虚拟机为已创建的,后nBi个虚拟机为新创建的,nBi的数量在新构件放置开始时是不确定的,其需要根据放置结果来确定,因此,

$V{M_A} = V{M_A}_1 \cup V{M_A}_2 \cup \ldots \cup V{M_{An}},V{M_B} = V{M_B}_1 \cup V{M_B}_2 \cup \ldots \cup V{M_{Bn}}.$

例如,在图 1所示的放置场景中:CA={c1,c2,c3,c4}为已放置的构件集合,其中,c1,c2c3被放置在由虚拟机模板vc2所创建的虚拟机vm21中,c4被放置在由vc1所创建的虚拟机vm11中;CB={c5,c6,c7,c8,c9,c10}为新放置的构件集合,通过制定新的放置方案,c5将被放置在vm11上,c6,c7,c8将被放置在由虚拟机模板vc2所创建的虚拟机vm22中,c9c10将被放置在由虚拟机模板vc3所创建的虚拟机vm31中.

为了提高云资源的利用率,我们尽量将CB中的构件放置在VMA,这样可以减少新创建虚拟机的数量,进而可以降低云资源的使用成本.

定义2(SaaS构件放置方案). SaaS构件放置方案可以定义从构件集合C到虚拟机集合VM的映射函数ρ:CVM.对于∀cC,ρ(c)∈VM表示c所放置的虚拟机;对于∀vmijVM,C(vmij)={cC|ρ(c)=vmij}表示放置在虚拟机vmij上的构件集合.

例如,在图 1所示的放置场景中,

$\begin{array}{l} VM = \left\{ {v{m_{11}},v{m_{21}},v{m_{22}},v{m_{31}}} \right\},C\left( {v{m_{11}}} \right) = \left\{ {{c_4},{c_5}} \right\},C\left( {v{m_{21}}} \right) = \left\{ {{c_1},{c_2},{c_3}} \right\},\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;C\left( {v{m_{22}}} \right) = \left\{ {{c_6},{c_7},{c_8}} \right\},C\left( {v{m_{31}}} \right) = \left\{ {v{m_9},v{m_{10}}} \right\}. \end{array}$

在构件关系图中,如果两个构件之间存在连接关系,并且这两个构件被放置在不同的虚拟机上,则这两个虚拟机之间存在网络通信.根据放置在两个不同虚拟机之间的构件连接关系,我们可以定义虚拟机网络图.

定义3(虚拟机网络图). 虚拟机网络图可以定义为VN=(VM,LVM),其中,VM为放置C中的构件所需要的虚拟机集合;LVM={(vmij,vmst)|∃cC(vmij),c'∈C(vmst):(c,c')∈Evmijvmst}表示VM中虚拟机之间的通信链路的集合,对于∀(vmij,vmst)∈LVM,表示vmijvmst之间存在通信链路.

对于∀(vmij,vmst)∈LVM,E(vmij,vmst)={(c,c')|cC(vmij),c'∈C(vmst),(c,c')∈E}为从vmijvmst的构件连接关系集,则从vmijvmst的通信流量可以定义为

${r_t}(v{m_{ij}},v{m_{st}}) = \sum\limits_{(c,c') \in E(v{m_{ij}},v{m_{st}})} {{r_t}(c,c')} .$

因此,虚拟机网络的通信流量可定义为rt(LVM)=${r_t}({L_{VM}}) = \sum\limits_{(v{m_{ij}},v{m_{st}}) \in {L_{VM}}} {{r_t}(v{m_{ij}},v{m_{st}})} .$

基于上述分析,虚拟机网络的成本可以定义为c(VN)=c(VM)+c(LVM),其中,$c(VM) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^{{s_i}} {p(v{m_{ij}})} } $为虚拟机的使用成本,c(LVM)=pt(rt(LVM))为虚拟机网络的通信成本.在这里,pt(T)表示虚拟机网络通信计费价格函数,如何确定pt(T),需要根据具体的网络通信计费模式来确定.本文的目标就是确定一种使得c(VN)最小的SaaS构件放置方案,因此,SaaS构件优化放置问题可以描述为

${\bf{Min}}c\left( {VN} \right) = c\left( {VM} \right) + c\left( {{L_{VM}}} \right)$ (1)

Subject to:

$S = \left\{ {{s_1},{s_2},...,{s_n}} \right\},{s_i} \in N\left( {i = 1,2,\ldots ,n} \right)$ (2)
$\begin{array}{*{20}{l}} {VM = V{M_1} \cup V{M_2} \cup ... \cup V{M_n}}\\ {V{M_i} = \left\{ {\begin{array}{*{20}{l}} {\emptyset ,{\rm{ }}{s_i} = 0}\\ {\{ v{m_{i1}},v{m_{i2}},...,v{m_{i{s_i}}}\} ,{\rm{ }}{s_i} > 0} \end{array}} \right.} \end{array}$ (3)
$\rho \left( c \right) \in VM,\forall c \in C$ (4)
$C\left( {v{m_{ij}}} \right) \ne \emptyset \wedge C\left( {v{m_{ij}}} \right) \subseteq C,\forall v{m_{ij}} \in V{U_B}$ (5)
$E\left( l \right) \ne \emptyset \wedge E\left( l \right) \subseteq E,\forall l \in {L_{VM}}$ (6)
$\sum\limits_{c \in C(v{m_{ij}})} {{r_c}(c)} \le {r_c}(v{m_{ij}}) - r_c^0(v{m_{ij}}),\forall v{m_{ij}} \in VM$ (7)
$\sum\limits_{o \in C(v{m_{ij}})} {{r_m}(c)} \le {r_m}(v{m_{ij}}) - r_m^0(v{m_{ij}}),\forall v{m_{ij}} \in VM$ (8)
$\sum\limits_{c \in C(v{m_{ij}})} {{r_d}(c)} \le {r_d}(v{m_{ij}}) - r_d^0(v{m_{ij}}),\forall v{m_{ij}} \in VM$ (9)

在上面的形式化描述中:公式(1)为问题的优化目标,表示SaaS构件放置方案,即,虚拟机网络图VN的成本最低;公式(2)给出了一组非负整型决策变量S={s1,s2,...,sn},其中,siN表示由第i类虚拟机模板vci所创建的虚拟机数量,N为非负整数集合;公式(3)是基于公式(2)的决策变量所构造的虚拟机集合VM=VM1VM2∪…∪VMn,其中,VMi表示由第i类虚拟机模板vci所构造的虚拟机集合,vmij(j=1,2,…,si)表示VMi中第j个虚拟机,VMivmij是需要根据决策变量S来动态创建的;公式(4)表示对于C中的任何构件,都被放置到VM中的一个虚拟机上;公式(5)表示VM中的任何虚拟机所包含的构件都不能为空,并且都是C中的构件;公式(6)表示LVM中的任何通信链路所包含的构件连接都不能为空,并且都是E中的构件连接;公式(7)到公式(9)是对虚拟机资源需求的约束,分别表示虚拟机所包含的构件的计算、内存和存储资源不能超过该虚拟机资源的提供能力,其中,$r_c^0(v{m_{ij}}),r_m^0(v{m_{ij}})$和$r_d^0(v{m_{ij}})$分别表示vmij的计算、内存和存储资源预留量.虚拟机的资源利用率不能超过一定的阈值,因此需要预留一部分资源作为缓冲以保证应用运行的质量,虚拟机的资源预留量与虚拟机的类型有关.

3 基于HGSA的SaaS构件优化放置算法

针对SaaS构件优化放置问题,本文采用混合遗传模拟退火算法(HGSA)对其进行求解.与遗传算法类似,HGSA也是从一组随机产生的初始解开始进行全局最优解搜索,它首先通过遗传算法(GA)中的选择和交叉操作来产生一组新个体,然后,针对每个新产生的个体采用模拟退火算法(SA)进行邻域搜索,并以其结果作为下一代种群中的个体.HGSA将GA与SA的优点充分结合起来,从而提高了SaaS构件优化放置问题的求解质量.

3.1 解的编码

HGSA采用基于构件的编码方式,染色体中每一个基因代表一个构件,染色体的长度为构件的数量|C|,基因的取值代表构件所放置的虚拟机,每个虚拟机采用一个二元组(i,j)来表示,其中,i表示虚拟机类型编号,j表示虚拟机编号.每一类虚拟机都是从1开始编号,并且要保持编号的连续性.令P表示一条染色体,P可分为两个部分:已放置构件的基因片段PA和新放置构件的基因片段PB,其中,PA中的每个基因代表CA中的一个构件,PB中的每一个基因代表CB中的一个构件.例如,针对图 1所示的SaaS构件放置方案,其所对应的编码如图 2所示.

Fig. 2 Coding of SaaS component placement project 图 2 SaaS构件放置方案编码
3.2 解初始化

解的初始化是指生成种群中的每一条初始染色体,本文采用基于贪心策略的启发式方法来生成初始染色体,具体步骤如下:

Step 1. 按照构件的编号顺序生成一条初始染色体P,其中,PA中每个构件的基因取值为该构件所在的虚拟机编码,PB中的每个构件的基因取值为空.

Setp 2. 随机产生一个VMA中虚拟机序列SVMCB中构件序列SC.

Step 3. 按照顺序取出SC中的每一个构件c,依次检查SVM中的每一个虚拟机是否能够放置c:如果满足放置条件,则将构件c放置到一个匹配的虚拟机上(即,c的基因取值为该虚拟机编号);如果SVM中的每一个虚拟机都不能放置构件c,则随机创建一个新的虚拟机,并将该虚拟机编号加入到序列SVM的末尾,然后将构件c放置到新创建的虚拟机上(即,构件c的基因取值为新创建的虚拟机编号).重复上述过程,直到SC中的每一个构件都被放置完成.

按照上述步骤,可以生成初始种群中的每一条染色体.解初始化的时间复杂度为O(s·|CB|·|VM|),其中,s为种群的数量,|CB|为新放置构件数量,|VM|为虚拟机的数量上限.

3.3 新解产生规则

HGSA采用SA中的邻域搜索策略来实现解的局部搜索能力.在SA中,新解产生是旧解向邻域搜索的结果,其搜索规则决定了邻域的范围.新解产生规则的设计与实际问题密切相关,而不是简单的随机搜索.针对本文所提出的SaaS构件优化放置问题,由已知解向邻域搜索的操作对象主要有构件和虚拟机,因此,我们设计了如下4种新解产生规则,其中,规则(1)和规则(2)属于构件粒度层次的邻域搜索,规则(3)和规则(4)属于虚拟机粒度层次的邻域搜索.

(1) 改变构件放置位置

随机选择一个基因k,设其取值为(i,j),为k重新赋予一个新值(i',j'),其对应的放置操作为:将构件ck从虚拟机vmij迁移到vmi'j'上,这要求vmi'j'的可用资源能够满足放置ck的资源需求.如果虚拟机vmij中只包含ck一个构件,则可以将vmij从虚拟机网络图VN中删除.图 3(a)描述了改变构件放置位置产生新解过程的示意图,它表示将构件c6从虚拟机vm22迁移到虚拟机vm12上.

Fig. 3 Four types rules of creating new solutions 图 3 4种新解产生规则

(2) 交换构件放置位置

随机选择两个取值不同的基因kl,交换kl的值,其所对应的放置操作为:将构件ck迁移到构件cl所在的虚拟机上,同时将构件cl迁移到构件ck所在的虚拟机上,即,互换ckcl的放置位置.迁移后的虚拟机应满足构件放置的资源约束条件.图 3(b)描述了交换构件放置位置产生新解过程的示意图,它表示将构件c5从虚拟机vm11取出放置到虚拟机vm22中,同时将构件c8从虚拟机vm22取出放置到虚拟机vm11中.

(3) 从高价虚拟机向低价虚拟机迁移

vmij为虚拟机网络图VN中的一个虚拟机,若存在比vmij价格低且能够放置其上所有构件的虚拟机模板vci',则创建vci'的一个实例vmi'j',将vmij上的所有构件都迁移到vmi'j'上,并将所有取值为(i,j)的基因值都替换为(i',j'),然后,再将vmij从虚拟机网络图VN中删除.由于vmi'j'的成本要比vmij低,因此通过该操作虚拟机网络VN的成本降低了p(vmij)-p(vmi'j').图 3(c)描述了从高价虚拟机向低价虚拟机迁移过程示意图,它表示存在比虚拟机vm31价格低且能够放置其上所有构件的虚拟机模板vc1,因此可以创建vc1的一个实例vm12(由于已存在编号为1的虚拟机vm11,为了保持编号的连续性,新创建的虚拟机编号应为2),然后将vm31中的构件c9c10迁移到新创建的虚拟机vm12中,最后,将vm31从虚拟机网络图中删除.

(4) 从小型虚拟机向大型虚拟机迁移

vmij为虚拟机网络图VN中的一个虚拟机,若存在能够放置vmij上所有构件的虚拟机vmi'j',则将vmij上的所有构件都迁移到vmi'j'上,并将这些构件的基因值都替换为(i',j'),然后,将vmij从虚拟机网络图VN中删除.由于减少了一个虚拟机vmij,而且vmijvmi'j'之间的通信由虚拟机之间转变为虚拟机内部(本文假定虚拟机内部的通信不产生成本),因此,通过该操作虚拟机网络图VN的成本低了p(vmij)+pt(rt(vmij,vmi'j')).图 3(d)描述了从小型虚拟机向大型虚拟机迁移过程的示意图,它表示存在一个能够放置虚拟机vm21上所有构件的虚拟机vm31,因此,可以将vm21上的所有构件都迁移到vm31上,并将vm21从虚拟机网络图中删除.迁移后,vm31上包含5个构件c9,c10,c1,c2c3,其中,c9c10为迁移之前vm31中已存在的构件,c1,c2c3是从vm21迁移过来的构件.

3.4 选择与交叉操作

HGSA采用遗传算法中的选择和交叉操作来提高解的全局搜索能力,其中,选择操作采用比例选择策略,交叉操作采用双切交叉法.

(1) 选择操作

选择操作采用比例选择策略和旋轮法来实现,其目的是使适应度高的个体具有更高的生存概率.

Pi(i=1,2,…,s)为种群中的一个染色体,s为种群规模,f(Pi)为Pi的适应度,适应度采用虚拟机网络图成本来表示.令VNiPi所对应的虚拟机网络图,则f(Pi)=c(VNi),c(VNi)为VNi的成本.为了便于选择操作,我们采用正规化技术将适应值映射到(0,1)区间.设F(Pi)为映射后的正规化适应度,则有:

$F({P_i}) = \frac{{{f_{\{ \max \} }} - f({P_i}) + r}}{{{f_{\{ \max \} }} - {f_{\{ \min \} }} + r}},$

其中,f{min}f{max}分别为种群中的最小和最大适应度;r∈(0,1)是一个常数,它可以根据实际情况进行设定,我们设定r=0.8.根据比例选择策略,Pi被选择的概率为$F({P_i})/\sum\limits_{i = 1}^s {F({P_i})} .$得到每个染色体的选择概率后,采用旋轮法来实现选择操作,共旋转s次,每次转轮时,随机产生ξk∈(0,1),如果$\sum\limits_{j = 1}^{i - 1} {F({P_i})} /\sum\limits_{i = 1}^s {F({P_i})} \le {\xi _k} < \sum\limits_{j = 1}^i {F({P_i})} /\sum\limits_{i = 1}^s {F({P_i})} $则选择染色体Pi.

(2) 交叉操作

交叉操作采用双切交叉法,对于两个选定的染色体P1P2,随机选取两个切点k1k2,交换k1k2之间的基因编码,生成两个新的染色体P1P2.图 4描述了交叉操作过程的示意图.

Fig. 4 Crossover operation 图 4 交叉操作

如果新生成的染色体不满足虚拟机资源约束条件,则需要对其进行修复,染色体修复过程如下:

Step 1. 针对每个不满足资源约束的虚拟机,生成该虚拟机所放置构件的一个序列,然后,按照该序列依次取出每个构件,直到虚拟机满足资源约束为止.

Step 2. 对于从所有不满足资源约束条件的虚拟机取出的所有构件,随机生成一个构件序列SC.同时,对于所有已经使用的虚拟机,随机生成一个虚拟机序列SVM.

Step 3. 按照顺序取出SC中的每一个构件c,依次检查SVM中的每一个虚拟机是否能够放置c:如果满足放置条件,则将构件c放置到第1个匹配的虚拟机上(即,c的基因取值为该虚拟机编号);如果SVM中的每一个虚拟机都不能放置构件c,则随机创建一个新的虚拟机,并将该虚拟机编号加入到序列SVM的末尾,然后将构件c放置到新创建的虚拟机上(即,构件c的基因取值为新创建的虚拟机编号).重复上述过程,直到SC中的每一个构件都被放置完成.

3.5 算法流程

基于HGSA的SaaS构件优化放置算法流程如图 5所示,其具体步骤如下:

Fig. 5 Process diagram of SaaS component optimal placement based on HGSA 图 5 基于HGSA的SaaS构件优化放置算法流程图

Step 1. 设置算法参数,包括种群规模s、初始温度Thigh、退火系数α、终止温度Tlow、交叉概率pc、内循环次数l、最优染色体Pbest.

Step 2. 设置当前温度t=Thigh.

Step 3. 根据第3.1节所提出的种群初始化操作,产生初始种群Pop={P1,P2,…,Ps},并将Pop中的最优解保存在Pbest中.

Step 4. 设置当前内循环次数n=0.

Step 5. 根据第3.2节所提出的比例选择策略,从当前种群Pop中选择s个染色体,并用其替换原染色体.

Step 6. 按照交叉概率pc,从当前种群Pop中选择$\left\lfloor {s/2} \right\rfloor $对染色体进行交叉操作,产生$\left\lfloor {s/2} \right\rfloor $对新染色体,令$Pop' = \{ {P'_1},{P'_2},...,{P'_s}\} $为新染色体的集合,其中,Pi'Pi的子染色体.对于Pop'中每个不满足资源约束条件的染色体,按照第3.4节所提出的策略对其进行修复.

Step 7. 对于新种群Pop'中的每个染色体${P'_i}$(i=1,2,…,s),令VNi为${P'_i}$所对应的虚拟机网络图,VMiVNi中所包含的虚拟机集合,依次检索VMi中的每个虚拟机,然后按照第3.3节所提出的规则(3)和规则(4)对其进行迁移操作,产生新的染色体${P''_i}$,如果$f({P''_i}{\rm{ }}) < f({P'_i}{\rm{ }}),$则用${P''_i}$替换${P'_i}$;如果$f({P'_i}) < $f(Pbest),则用${P'_i}$替换Pbest.

Step 8. 对于新种群Pop'中的每个染色体${P'_i}$(i=1,2,…,s),利用Metropolis准则判断其是否替换当前种群Pop中其所对应的父染色体Pi,令$\Delta f = f({P'_i}) - f({P_i})$:

如果Δf<0,则用${P'_i}$替换Pi;

否则,产生一个随机数ξ#8712;(0,1):如果exp(-Δf/(α·t))>ξ,则用${P'_i}$替换Pi;如果f(Pi)<f(Pbest),则用Pi替换Pbest.

Step 9. 对于当前种群Pop中的每个染色体Pi(i=1,2,…,s),按照第3.3节所提出的规则(1)和规则(2)对其进行构件的迁移和交换操作,产生新的染色体${P'_i}$,利用Metropolis准则判断是否接受该新染色体${P'_i}$.令$\Delta f = f({P'_i}) - f({P_i})$:

如果Δf<0,则用${P'_i}$替换Pi;

否则,产生一个随机数ξ#8712;(0,1):如果exp(-Δf/(α·t))>ξ,则用${P'_i}$替换Pi;如果f(Pi)<f(Pbest),则用Pi替换Pbest.

Step 10. 令n=n+1,如果n<l,转到Step 5;否则,执行Step 11.

Step 11. 令t=α·t,如果t>Tlow,转到Step 4;否则,执行Step 12.

Step 12. 输出最优解Pbest.

上述算法的时间复杂度为$O\left( {s \cdot l \cdot {{\log }_\alpha }\left( {\frac{{{T_{low}}}}{{{T_{high}}}}} \right) \cdot |C| \cdot |VM{|^2}} \right),$其中,|C|为构件的数量,|VM|为所使用的虚拟机数量.由于算法每次执行所产生的虚拟机数量是不确定的,因此,|VM|不是固定的常量,$|MV| < \sum\limits_{i = 1}^n {{n_{\max }}(v{c_i})} ,$其中,

nmax(vci)表示只选择虚拟模板vci所使用的最大虚拟机数量.对于给定的构件模型和虚拟机模板的集合,该值可以通过实验来确定.

4 实验分析 4.1 算法输入

基于HGSA的SaaS构件优化算法的输入为IaaS提供商所发布的虚拟机模板和SaaS提供商所要部署的构件模型.在本实验中,虚拟机模板参考亚马逊EC2的虚拟机模板类型进行设置,我们主要考虑CPU、内存和存储这3种资源.在EC2中,不同虚拟机模板的资源数量和价格是不同的,我们选择了13种虚拟机模板作为实验对象,其配置见表 1.其中,CPU的单位为CU(compute unit),内存的单位是GiB(230字节),存储的单位是GB,虚拟机价格的单位为$\$ $/h,网络通信的价格为0.01 $\$ $/GB.虚拟机模板的数量可以根据实际需要动态地进行调整.

Table 1 Parameters of EC2 virtual machine template 表 1 EC2虚拟机模板参数

由于不同的SaaS应用其构件模型是不同的,为了验证本文所提出的算法在解决大规模SaaS应用优化放置方面的处理能力,我们采用仿真的方式动态生成构件模型.在本实验中,构件数量的模拟范围为[10,100],对于每个构件,其CPU需求数量的模拟范围为[0.2,2],内存需求数量的模拟范围为[0.5,3],存储需求数量的范围为[50,200],构件之间的连接关系按照概率[0,0.4]随机生成,其通信量模拟范围为[1,5].EC2的计费方式主要分为预留和按需两种方式,这里,我们主要考虑按需计费方式,并设定租期为1天(24h).

4.2 算法参数设置

HGSA中的参数包括种群规模s、初始温度Thigh、终止温度Tlow、退火系数α、内循环次数l和交叉概率pc.不同的参数对算法的性能和质量具有不同的影响,所以首先要对各种参数进行分析,确定每种参数的变化趋势和最佳的取值范围.

(1) 种群规模s

一般来说,种群规模越大越好,因为如果种群太小容易使算法发生早熟,但是种群规模的扩大也将导致运算时间的延长,从而降低了算法的性能.在本实验中,我们设定种群规模为100.

(2) 初始温度Thigh

一般来说,初始温度要足够大,以此来保证算法在开始时处于平衡状态.但是如果初始温度过高,则接受不可行解的概率就会增大,从而导致算法的运行时间过长.本文采用多次随机搜索所得到的适应函数的平均增量方法来确定初始温度.通过逆推Metropolis准则接受概率公式可得${T_{high}} = \frac{{ - \overline {\Delta f} }}{{\ln ({p_0})}}$,其中,p0为初始接受概率,$\overline {\Delta f} $为初始搜索所得到的适应度平均增量.我们设定p0=0.8,通过反复实验分析,最终确定Thigh=250.

(3) 退火系数α

退火系数α控制温度下降的方式,对于退火系数,通常在0.5~0.95之间取值.通过实验分析发现:在本问题中,退火系数对于解的影响远小于其他参数.因此,根据经验值可设置α=0.9.

(4) 内循环次数l

内循环是指在一个给定的温度下,通过Metropolis准则进行随机搜索,最终达到一种平衡状态的过程.为了保证在每一个温度下算法都能够达到平衡状态,内循环的次数l一般要足够大,但是如果l过大,则会导致邻域搜索时间过长,从而影响算法的性能.为了确定一个较为合适的内循环次数,我们在一系列终止温度条件下,通过不断地增加l取值来观测当前种群全局最优解的变化趋势(执行算法100次,取所有次数的平均值).通过实验分析发现:当构件数量较少时(≤40),内循环次数l对解的质量影响较小.这是因为,当构件数量较少时,虚拟机的使用成本占总成本的比例较高,而HGSA可以快速地搜索到成本最低的虚拟机.图 6给出在构件数量n分别为50,60,70,80,90和100、种群规模s=100、初始温度Thigh=250、退火系数α=0.9、交叉概率pc=0.9、终止温度Tlow分别为200,100,10,1,0.1和0.01时的种群全局最优适应度(成本)变化趋势曲线图.从这些曲线可以看出:当l增加至6以后,每种终止温度下种群最优适应度(成本)的下降趋势不大,因此可以设置l≥6.l的具体取值可以根据实际问题的规模来设定.

Fig. 6 Tendency of fitness vary with length of inner loop 图 6 适应度随内循环次数变化趋势

(5) 终止温度Tlow

当初始温度Thigh和退火系数α确定以后,可以通过终止温度Tlow来控制外循环的执行次数,终止温度可以设定为一个很小的正数.一般来说,终止温度要足够小,以保证算法有足够的时间来获取全局最优/好解.然而,如果终止温度过小则会增加中间温度的数量,进而导致过多的邻域搜索,增加了算法的执行时间.为了确定一个较为合理的终止温度,我们通过不断降低Tlow的取值来观测当前种群全局最优解的变化趋势(执行算法100次,取所有次数的平均值).图 7给出了在构件数量n分别为50,60,70,80,90和100、种群规模s=100、初始温度Thigh=250、退火系数α=0.9、内循环次数l=6、交叉概率pc=0.9时的种群全局最优适应度(成本)随终止温度变化趋势曲线图.从这些曲线图可以看出:当Tlow降低至0.01以后,种群最优适应度(成本)的下降趋势不大,因此可以设置Tlow≤0.01,Tlow的具体取值可以根据实际问题的规模来设定.

Fig. 7 Tendency of fitness vary with end temperatures 图 7 适应度随终止温度变化趋势

(6) 交叉概率pc

交叉概率Pc为各代中交叉产生的后代数与种群中的个体数的比值.一般来说,较高的交叉概率将会达到更大的解空间,从而减少停止在非最优解上的机会.但是,如果交叉概率太高,则会因过多地搜索不必要的解空间而耗费大量的计算时间,从而降低了算法的性能.在HGSA中,交叉概率的设置与终止温度Thigh密切相关:如果Thigh的值较高,则pc的值应该设置得低一些,这样可以加快收敛的速度;反之,pc的值可以设置得高一些,因为这样有更多的机会进行解空间的搜索.图 8给出了在构件数量为100、种群规模s=100、初始温度Thigh=250、退火系数α=0.9、内循环次数l=6、终止温度Thigh=0.01时的种群全局最优适应度(成本)变化趋势曲线图.

Fig. 8 Tendency of fitness vary with crossover probabilities 图 8 适应度随交叉概率变化趋势

根据该曲线可以看出:当交叉概率较小和较大时,解的质量较好;当交叉概率大于0.8以后,种群最优适应度的下降趋势不大.因此,可以设定pc≥0.8.

4.3 对比实验

为了验证本文所提出的混合遗传模拟退火算法(HGSA)在求解SaaS构件优化放置问题方面的有效性,我们又单独采用了遗传算法(GA)和模拟退火算法(SA)对该问题进行了求解.

在GA中,由于虚拟机的数量是不确定的,因此,通过交叉操作所产生的新染色体的质量不但没有改进反而在不断地下降.这是因为,交叉操作会增加虚拟机的数量,导致构件的放置更加稀疏,从而增加了放置方案的成本.为了提高GA的求解质量,我们采用本文所提出的新解产生规则(3)和规则(4)对交叉操作后所产生的新解进行了优化,通过实验分析发现其求解质量已显著提高.

传统的SA是从一个初始解开始不断进行邻域搜索来产生新解,因此,初始解的质量对算法的影响比较大.为了提高SA的求解质量,我们从初始种群中选择一个最优解作为SA的初始解.在传统的SA中,邻域搜索是通过改变染色体中某个基因的取值来实现的,该操作相当于本文所提出的邻域搜索规则(1),即,改变构件的放置位置.这一操作的收敛速度比较慢,而且很容易陷入局部最优/好解.为此,我们又将其他3个邻域搜索规则都加入到SA中,从而极大地提高了SA的求解质量.

另外,本文所提出的解初始化方法采用的是一种基于贪心策略的启发式算法(HA),即,每次放置构件都是尽量选择已经存在的虚拟机,这样可以减少虚拟机的使用数量.单独采用HA进行问题求解的运行效率比较高,但是解的质量较差.为了提高HA的求解质量,我们首先采用HA来生成一组解(种群),然后,从中选择一个最优解(相当于SA的初始解)作为HA的最终解.

本文通过实验对上述4种算法(HGSA,GA,SA和HA)的求解质量进行了比较.我们采用模拟的方式随机生成了10个构件模型,其构件数量分别是10,20,…,100,每个构件的资源需求数量以及构件之间通信量按照第4.1节所给出的范围进行随机均匀生成.针对每一构件模型,我们分别采用上述4种算法对其进行求解30次取平均值.为了体现实验的公平性,每次求解它们都是从同一初始种群开始,其中,SA的初始解是该种群中的最优解,HGSA和GA的进化代数和交叉概率是一致的(s=100,pc=0.9),GA的变异概率设置为0.1.图 9给出了4种算法所计算的总成本(虚拟机使用成本+网络通信成本)的对比分析图.

Fig. 9 Comparison of total cost calculated by four algorithms 图 9 4种算法所计算的总成本比较

通过实验分析发现:对于任意给定的初始种群,HGSA求解质量最好,其次是SA,再次是GA,最后是HA.由于SA是在HA的基础上继续进行邻域搜索,因此从理论上来说,SA的求解质量至少不会比HA差.由于HGSA是采用多个解在其邻域内并行搜索的方式,并且利用交叉操作来提高全局搜索能力,因此其求解质量要高于SA.与HGSA和SA相比,GA对该问题的求解能力较弱,这主要是由于虚拟机数量的不确定性而导致搜索范围扩大,尽管我们希望通过相应的邻域搜索规则来改善新解的质量,但其效果仍不理想.

表 2表 3分别给出了在每一构件数量下,4种算法所计算的虚拟机使用成本和网络通信成本的具体数值.从实验结果可以看出:在每一个构件数量下,HGSA所计算的虚拟机使用成本和网络通信成本都要低于其他3种算法;而且随着构件数量的增加,其求解质量显著提高.这说明HGSA在求解SaaS构件优化放置问题方面具有较好的效果.

Table 2 Comparison of virtual machine usage cost calculated by four algorithms 表 2 4种算法所计算的虚拟机使用成本比较

Table 3 Comparison of network communication cost calculated by four algorithms 表 3 4种算法所计算的网络通信成本比较
4.4 实例分析

本节通过图 1所示的实例来说明HGSA在求解SaaS构件优化放置方面的能力.在该实例中,包含10个构件,每个构件的资源需求以及构件之间的通信如图 10上半部分所示,虚拟机模板采用亚马逊的EC2(具体配置见表 1).利用本文所提出的HGSA算法(算法参数设置为s=100,α=0.9,Thigh=250,Tlow=0.01,l=6,pc=0.9),一次即可求得最优SaaS构件放置方案,如图 10下半部分所示.在该方案中,我们选择了2台虚拟机,它们分别是C3.xlarge和I2.2xlarge,其中,I2.2xlarge上放置构件c5,C3.xlarge上放置其他所有构件,假设租期为72h,网络通信价格为0.01$/GB,则最终成本为67.602$.其中,虚拟机使用成本为67.536$,网络通信成本为0.066$.这说明,本文所提出的算法在虚拟机数量不确定的情况下具有较好的效果.

Fig. 10 Txample of SaaS component optimal placement 图 10 SaaS构件优化放置实例
5 结束语

针对传统软件提供商在向SaaS服务模式迁移时所遇到的SaaS构件放置问题,本文提出了一种基于混合遗传模拟退火算法的SaaS构件优化放置方法,其优化目标是提高云资源利用率、降低云资源使用成本.尽管目前存在许多SaaS优化放置方法,但是这些方法都假定云环境中虚拟机的类型和数量是确定的,即,在限定的资源上进行优化放置;然而实际情况是:虚拟机的类型和数量一般都是不确定的,需要根据被部署的构件资源需求来确定.而本文所提出的SaaS构件优化放置模型弥补了这些方法的不足.本文采用混合遗传模拟退火算法HGSA对SaaS构件优化放置问题进行求解,HGSA算法结合了遗传算法和模拟退火算法的优点,克服了GA收敛速度慢和SA容易陷入局部最优的缺点,与单独使用遗传算法和模拟退火算法相比,HGSA算法具有更高的求解质量.从云架构角度来看,本文所提出的放置方法不仅适用于公有云基础设施的放置,同时也适用于私有云基础设施的放置.从软件生命周期阶段来看,本文所提出的放置方法不仅适用于SaaS的初始部署,而且也适用于SaaS运行阶段的动态部署.

参考文献
[1] Kang S, Kang S, Hur S. A design of the conceptual architecture for a multitenant SaaS application platform. In: Proc. of the Int’l Conf. on Computers, Networks, Systems, and Industrial Engineering. IEEE Computer Society Press, 2011. 462-467 .
[2] Zhang Y, Wang ZH, Gao B, Guo CJ, Sun W, Li XP. An effective heuristic for on-line tenant placement problem in SaaS. In: Proc. of the 2010 IEEE Int’l Conf. on Web Services. IEEE Computer Society Press, 2010. 425-432 .
[3] Yu HY, Wang DH. System resource allocation algorithm for multi-tenant SaaS application. In: Proc of the 2011 Int’l Conf. on Cloud and Service Computing. IEEE Computer Society Press, 2011. 207-211 .
[4] Wu LL, Garg SK, Buyya R. SLA-Based admission control for a software-as-a-service provider in cloud computing environments. Journal of Computer and System Sciences, 2012,78(5):1280-1299 .
[5] Yang EF, Zhang Y, Wu L, Liu YL, Liu SJ. A hybrid approach to placement of tenants for service-based multi-tenant SaaS application. In: Proc. of the 2011 IEEE Asia-Pacific Services Computing Conf. IEEE Computer Society Press, 2011. 124-130 .
[6] Tian C, Jiang HB, Iyengar A, Liu X, Wu ZD, Chen JH, Liu WY, Wang CG. Improving application placement for cluster-based Web applications. IEEE Trans. on Network and Service Management, 2011,8(2):104-115 .
[7] Yusoh ZIM, Tang M. Composite SaaS placement and resource optimization in cloud computing using evolutionary algorithms. In: Proc. of the 2012 IEEE 5th Int’l Conf. on the Cloud Computing. IEEE Computer Society Press, 2012. 590-597 .
[8] Lloyd W, Pallickara S, David O, LyonbAuthor J, ArabibAuthor M, Rojas K. Performance implications of multi-tier application deployments on infrastructure-as-a-service clouds: Towards performance modeling. Future Generation Computer Systems, 2013, 29(5):1254-1264 .
[9] Moens H, Truyen E, Walraven S, Joosen W, Dhoedt B, De Turck F. Cost-Effective feature placement of customizable multi-tenant application in the cloud. Journal of Network System Management, 2014,22(4):517-588 .
[10] Zhu XY, Santos C, Beyer D, Ward J, Singhal S. Automated application component placement in data centers using mathematical programming. Int’l Journal of Network Management, 2008,18:467-483 .
[11] Jin ZH, Cao J, Li ML. A distributed application component placement approach for cloud computing environment. In: Proc. of the 9th IEEE Int’l Conf. on Dependable, Automic and Secure Computing. IEEE Computer Society Press, 2011. 488-495 .
[12] Sailer A, Head MR, Kochut A, Shaikh H. Graph-Based cloud service placement. In: Proc. of the 2010 IEEE Int’l Conf. on Services Computing. IEEE Computer Society Press, 2010. 89-96 .
[13] Pisinger D. An exact algorithm for large multiple knapsack problem. European Journal of Operational Research, 1999,114(3): 528-541 .
[14] Kataoka S, Yamada T. Upper and lower bounding procedures for the multiple knapsack assignment problem. European Journal of Operational Research, 2014,237(2):440-447 .
[15] Sarac T, Sipahioglu A. Generalized quadratic multiple knapsack problem and two solution approaches. Computer & Operations Research, 2014,43:78-89 .
[16] Ren ZG, Feng ZR, Zhang AM. Fusing ant colony optimization with Lagrangian relaxation for the multiple-choice multidimensional knapsack problem. Information Science, 2012,182(1):15-29 .
[17] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation, 2002,6(2):182-197 .
[18] McCall J. Genetic algorithms for modelling and optimization. Journal of Computational and Applied Mathematics, 2005,184(1): 205-222 .
[19] Chen D, Lee CY, Park CH. Hybrid genetic algorithm and simulated annealing (HGASA) in global function optimization. In: Proc. of the 17th IEEE Int’l Conf. on Tools with Artificial Intelligence. IEEE Computer Society Press, 2005. 113-117 .
[20] Li WD, Ong SK, Nee AYC. Hybrid genetic algorithm and simulated annealing approach for the optimization of process plans for prismatic parts. Int’l Journal of Production Research, 2002,40(8):1899-1922 .
[21] Loukil L, Mehdi M, Mebab N. A parallel hybrid genetic algorithm-simulated annealing for solving Q3AP on computational grid. In: Proc. of the IEEE Int’l Symp. on Parallel & Distributed Processing. IEEE Computer Society Press, 2009. 1-8 .
[22] Li YH, Guo H, Wang L, Fu J. A hybrid genetic-simulated annealing algorithm for the location-inventory-routing problem considering returns under E-supply chain environment. The Scientific World Journal, 2013 .