孟凡超，周学权，曹祖凤，初佃辉，战德臣

（哈尔滨工业大学（威海）企业与服务智能计算研究中心，山东 威海 264209）

0 引言

随着云计算的出现，IT领域正在进行着一场深刻的变革。云计算是一种新型的计算模型，它将IT资源、数据和应用作为服务，通过互联网提供给用户［1］。云计算根据其服务类型可分为基础设施即服务（Infrastructure as a Service，IaaS）、平台即服务（Platform as a Service，PaaS）和软件即服务（Software as a Service，SaaS）。在SaaS模式下，客户不需要购买完整的软件系统，也不需要配备相应的硬件系统和维护人员，只需通过互联网按需租用应用软件即可，这对成本预算有限、技术条件不足的中小企业来说，具有很强的吸引力［2］。

在云计算环境下，SaaS主要涉及客户（也称为租户）、SaaS提供商和云基础设施提供商［3］三类角色。租户租用SaaS提供商所提供的SaaS应用来满足自己的业务需求，每个租户可以租用一个或多个SaaS应用。SaaS提供商通过向租户提供SaaS应用服务来获取利润，每个SaaS应用可以部署多个实例，这些实例被部署在云基础设施提供商所提供的虚拟机上，例如，Amazon的弹性计算云EC2，或者部署在自己的服务器或虚拟机上，本文主要研究前者，即租用云基础设施提供商的虚拟机，此时SaaS提供商需要向云基础设施提供商支付相应的租金［4］。云基础设施提供商对外提供一组虚拟机模板，由同一模板所生成的虚拟机具有相同的资源配置和价格，例如，亚马逊提供的虚拟机模板有m1．small，m1．large和 m1．large等［5］。

基于成本优化的SaaS应用放置是指在SaaS应用部署的初始阶段，SaaS提供商根据已有租户的数量以及对每类租户市场规模的预测，确定应部署的SaaS应用实例的数量和租用每一类虚拟机的数量，并建立租户与SaaS应用实例，以及SaaS应用实例与虚拟机之间的放置关系，其优化目标是在满足每个租户服务级别协议（Service Level Agreement，SLA）的条件下，使租用的虚拟机的总成本最低。

1 相关工作

针对多租户SaaS应用优化放置问题，国内外学者已经展开了许多研究。Kwok等提出一种多租户SaaS应用实例资源消耗度量模型，该模型描述了SaaS应用实例的资源消耗与租户数量和用户数量之间的关系，基于该模型，又提出了一种租户放置算法并开发了相应的支撑工具［6］。Zhang等扩展了Kwok等所提出的资源消耗度量模型，加入了服务响应时间的约束，并提出一种启发式在线租户放置算法［7］。Wu 等 站 在 SaaS 提 供 商 的 角 度［3－4］，提 出了基于SLA的SaaS应用资源分配算法以降低租用虚拟机的成本，并通过仿真实验来模拟在线租户放置过程。Yu等提出了面向租户服务质量（Quality of Service，QoS）的资源优化分配模型，同时给出启发式算法和遗传算法，并对这两种算法的性能进行了比较［8］。汪德帅等面向租约用户的非功能需求，提出一种支持多租约SaaS应用按需服务的负载均衡策略［9］。Izzah等研究了构件化的SaaS应用优化部署问题，提出一种基于惩罚的遗传算法来求解最优SaaS放置方案［10］。Yang等针对基于服务的SaaS应用，提出一个基于案例推理（Case－Based Reasoning，CBR）的混合租户放置方法［11］。

多租户SaaS应用放置可分为租户放置和SaaS应用实例放置两方面，租户放置是指确定租户与SaaS应用实例之间的服务关系；SaaS应用实例放置是指建立SaaS应用实例与服务器或虚拟机之间的部署关系。然而，现有研究大多针对租户放置［3－4，6－9，11］，对 SaaS 应 用 实 例 放 置 的 研 究 比 较 少。有些研究虽然也考虑了资源的预分配［8－9］和SaaS应用实例的放置策略［10］，但都是在给定服务器/虚拟机的数量，即限定资源数量的基础上进行的优化，然而现实情况是服务器/虚拟机的数量和SaaS应用实例的数量是不确定的，例如，SaaS提供商在初次租用虚拟机/服务器时，只知道虚拟机的类型，如EC2的小、中、大型虚拟机，但要租用的各类虚拟机的个数未知，而且要部署的SaaS实例的个数也需要根据租户需求确定。

因此，对于给定的租户需求，如何确定需要部署的SaaS应用实例的数量和租用的虚拟机数量，同时建立租户与SaaS应用实例，以及SaaS应用实例与虚拟机之间的放置关系，是本文所要解决的问题。针对该问题，本文通过分析多租户SaaS应用服务模式，提出了面向租户响应时间的资源消耗度量模型，采用基于虚拟机序列的遗传算法来求解多租户SaaS应用优化放置问题，并通过实验分析了算法的可行性和有效性，最后通过一个应用案例来描述放置方案的确定过程。

2 多租户SaaS应用放置模型

设某SaaS提供商有m个租户，对外提供n种SaaS应用（简称应用），每种应用可以部署多个SaaS应用实例（简称应用实例），每个应用实例可以放置多个租户，这些应用实例需要部署在云基础设施提供商所提供的虚拟机上。设云基础设施提供商对外提供q种虚拟机，应用实例的运行需要消耗其所在虚拟机的资源，例如，CPU、内存、网络带宽等，设p为资源种类的数量。每个租户在使用应用前需要与SaaS提供商签订SLA，SLA规定了应用实例所要满足的性能需求。应用实例所消耗的资源一般与该应用的类型、租户数量、并发用户数量以及租户的性能需求等因素有关，对于性能需求，本文主要考虑服务响应时间。

基于成本优化的多租户SaaS应用放置问题可描述为：对于给定的租户集合TS＝｛T1，T2，…，Tm｝、应用集合 AS＝｛A1，A2，…，An｝、租户与应用之间的租约关系集合TA⊆TS×AS、虚拟机类型集合VMTS＝｛VMT1，VMT2，…，VMTq｝，确定多租户SaaS应用放置方案，即确定SaaS提供商所要租用云基础设施提供商的虚拟机数量xj、部署应用实例的数量应用实例与虚拟机之间的放置关系集合PRAV⊆AIS×VMS、租户与应用实例之间的放置关系集合PRTA⊆TS×AIS，其优化目标是租用虚拟机的成本最低，并且部署的应用实例数量y尽可能少。

其中：xj表示虚拟机类型VMTj的实例数量；yj表示应用Aj的实例数量；AIS表示部署的应用实例集合；VMS表示租用的虚拟机集合，它们的数量分别为y和x；cj表示虚拟机类型VMTj的成本。

多租户SaaS应用放置的一个关键问题是建立应用的资源消耗模型。本文借鉴文献［6－7］的思想，提出一个面向租户服务响应时间的资源消耗模型。

设Sk∈AIS表示被部署的第k（k＝1，2，…，y）个应用实例，VMj∈VMS 表示被租用的第j（j＝1，2，…，x）个虚拟机，当把Sk放置到VMj上时，Sk在VMj上消耗的第i（i＝1，2，…，p）种资源的数量其中：表示在没有租户和用户时的资源消耗；表示隔离租户的资源消耗，隔离租户指当多个租户共享同一应用实例时，为使不同租户的业务和数据互不干扰所采取的技术手段表示处理用户服务请求的资源消耗，ut表示租户t∈Tk所包含的并发用户数量，Tk表示放置在Sk上的租户集合，rt表示租户t∈Tk对Sk服务响应时间的需求，fik（r，u）＝（w/r）·fik（w，u），fik（w，u）表示基准响应时间为w、并发用户数为u时Sk对第i类资源的消耗，该函数可以根据测试和实际运行数据来确定［6－7］。一般来说，隔离租户的资源消耗远小于处理用户服务请求的资源消耗［6］。

设rij表示虚拟机VMj上的第i（i＝1，2，…，p）种资源的最大可用量，则有

式中：zj表示在VMj上放置的应用实例的数量，αij表示VMj上第i种资源的最大利用率。

综上所述，基于成本优化的多租户SaaS应用优化部署问题可以表示为：

例如，某SaaS提供商有5个租户，对外提供3种应用，云基础设施提供商为其提供3种虚拟机模板，图1描述了租户与应用之间的租约关系。针对图1所示的租约关系，图2给出一种多租户SaaS应用放置方案：租用类型为VMT1的两个虚拟机VM1和VM2，租用类型为VMT3的1个虚拟机VM3，即租用虚拟机的数量x＝3（x1＝2，x2＝0，x3＝1）；部署2个A1实例S1和S2，部署2个A2实例S3和S4，部署1个A3实例S5，即部署应用实例的数量为y＝5（y1＝2，y2＝2，y3＝1）；应用实例S1和S3放置在虚拟机VM1上，应用实例S2和S4放置在虚拟机VM2上，应用实例S5放置在虚拟机VM3上；应用实例S1上放置1个租户T1，应用实例S2上放置1个租户T2，应用实例S3上放置2个租户T2和T3，应用实例S4上放置1个租户T4，应用实例S5上放置3个租户T2、T4和T5，即应用实例放置关系集PRAV＝｛（S1，VM1），（S3，VM1），（S2，VM2），（S4，VM2），（S5，VM3）｝，租户放置关系集PRTA＝｛（T1，S1），（T2，S2），（T2，S3），（T2，S3），（T2，S5），（T3，S3），（T4，S4），（T4，S5），（T5，S5）｝。

基于成本优化的多租户SaaS应用放置问题可以划分为2个子问题：①确定应用实例数量y（y≤｜TA｜）和虚拟机的数量x（x≥q）；②确定租户放置关系PRTA和应用实例放置关系PRAV。其中问题②可以看作是将y个物体放到x个箱子的装箱问题，其中，每个物体代表一个应用实例及其所包含的租户，每个箱子代表一个虚拟机，该问题的时间复杂度为xy，因此，多租户SaaS应用放置问题属于NP问题。为提高问题的求解效率和质量，本文提出一个基于虚拟机序列的遗传算法来求解近似最优放置方案。

3 多租户SaaS应用优化放置遗传算法

3．1 初始应用实例和虚拟机的确定

为了采用遗传算法进行问题求解，首先需要确定放置方案的染色体编码方式。因为在初始部署阶段，应用实例的个数和虚拟机个数都未知，所以染色体的长度和基因的取值都是不确定的，不能直接运用遗传算法进行求解。为此，首先根据租约关系来确定初始的应用实例数量和虚拟机的数量，具体计算方法如下：

（1）将每一个租约关系（Ti，Aj）∈TA 映射为一个租户放置关系（Ti，Sk）∈PRTA，其中，Sk为Aj的一个实例，并且对于每个应用的每个租户都分配一个不同的实例，这样可以确定初始的应用实例集AIS，其数量为租约关系的数量y＝｜TA｜，且每个应用实例只放置一个租户。

（2）对每一种虚拟机VMTi（i＝1，2，…，q），计算所有应用实例都放置到该类虚拟机时，需要的虚拟机实例个数的下限xi，则初始的虚拟机需求数量可以定义为这样可以保证有足够的虚拟机供选择，本文的目标就是从这些虚拟机中选择能够放置所有应用实例及其所包含的租户、并且满足成本最低的一组虚拟机。

确定每一类虚拟机VMTi（i＝1，2，…，q）需求数量的算法如下：

算法1 确定每类虚拟机需求数量。

输入：初始应用实例集AIS、虚拟机类型VMTi；

输出：VMTi的需求数量xi。

步骤1 令VMSi＝∅为已部署的VMTi实例集（VMSi为有序集）。

步骤2 生成VMTi的一个实例加入VMSi中。

步骤3 从AIS中取出一个应用实例Sk。

步骤4 依次检查VMSi中的每个实例VMj，计算将Sk放置到VMj后，VMj的每一类资源需求量是否满足其资源可用量约束。

（1）如果满足，则将Sk从AIS中取出，并将其加入VMj所放置的应用实例集AIS（VMj）中，转步骤3；

（2）如果不满足，则生成VMTi的一个实例，加入VMSi的第一个位置，转步骤4；

（3）如果AIS中的所有应用实例都已放置，即AIS＝∅，则转步骤5。

步骤5 输出VMTi的需求数量xi＝｜VMSi｜。

算法1的最坏时间复杂度是O（｜AIS｜2）＝O（y2），即AIS中的每个应用实例都放置在不同的虚拟机中，则确定所有类型的虚拟机数量的时间复杂度为O（q·y2）。

例如，针对图1所示的租约关系，可以确定如图3左侧所示的8个初始租户放置关系：（T1，S1），（T2，S2），（T2，S3），（T2，S6），（T3，S4），（T4，S5），（T4，S7），（T5，S8）。其中：A1包含S1和S2两个实例，A2包含S3，S4和S5三个实例，A3包含S6，S7和S8三个实例，即y＝8（y1＝2，y2＝3，y3＝3）。根据算法1，可以确定初始虚拟机数量，为了简化问题的复杂度，这里省略了计算过程，只给出计算结果，三类虚拟机的初始数量分别为4，3和4，即x＝11（x1＝4，x2＝3，x3＝4），它们的编号如图3右侧所示。

3．2 染色体编码设计

确定了初始应用实例数量和虚拟机需求数量后，就可以对放置方案进行编码。针对该类问题，目前的编码方式主要有基于应用实例（看作物体）的编码和基于虚拟机（看作箱子）的编码［12］。基于应用实例的编码方式是每个基因代表一个初始应用实例，基因的取值为初始虚拟机的编号，表示该应用实例所放置的虚拟机［10］。基于虚拟机的编码方式是每个基因表示一个初始虚拟机，基因的取值为一组应用实例的集合，表示放置在该虚拟机上的所有应用实例［13］。

通过实验发现，采用这两种编码方式的遗传算法在求解多租户SaaS应用放置问题时的优化结果都不是很理想。目前，基于应用实例编码的染色体主要采用随机生成的方法，即对每个基因随机生成一个虚拟机编号［10］。对于多租户应用放置问题来说，如果初始的虚拟机数量非常大，则采用随机生成方式会导致被选择的虚拟机的数量非常多，算法的收敛速度会很慢，而且解的质量也很低。另外，随机生成还会产生许多不可行的染色体，对这些染色体进行修复还会消耗一定的时间。虽然基于虚拟机的编码在解的质量上有所提高，但是由于编码方式的复杂性，算法的时间复杂度相对较高［13］。

针对上述两种编码方式存在的问题，本文提出一种基于虚拟机序列的编码方式，在该编码方式中，每条染色体是一个初始虚拟机的序列，表示一个初始应用实例序列所放的顺序。例如，针对图3右侧所示的初始虚拟机集合，可随机生成一个初始虚拟机序列：1 2 5 9 3 4 6 7 8，表示初始应用实例序列S1S2S3S4S5S6S7S8的放置顺序，即按照该顺序将这些应用实例先放置到虚拟机VM1中，如果VM1放满（表示该虚拟机当前状态下的可用资源不能再满足应用实例序列中没有被放置的任何应用实例的资源需求）则再往VM2中放置，如果VM2放满则再往VM5中放置，直到所有应用实例都被放完为止，此时可能还存在闲置的虚拟机，表示它们没有被选择。在此例中选择了VM1，VM2，VM5和VM94个虚拟机，其中：S1和S2放置在VM1中，S3和S4放置在VM2中，S5，S6和S7放置在VM5中，S8放置在VM9中，其他虚拟机则没有被选择。对基于虚拟序列的编码方式来说，由于不同的虚拟机序列会产生不同的放置方案，虚拟机的序列是影响求解质量的关键因素。

在应用实例放置过程中，如果同一应用的多个实例被放置到一个虚拟机上，则将这些应用实例合并为一个应用实例（同一应用在一个虚拟机上只能部署一个实例），合并后的应用实例的租户为这些应用实例租户的并集，因此在计算应用实例的资源消耗时，不是单独计算每个应用实例的资源消耗再求它们的和，而是先按照类别合并同类应用实例，再计算合并后每类应用实例的资源消耗，最后求所有应用类别的资源消耗之和。因此，对基于虚拟序列的编码方式来说，应用实例的放置顺序也会影响放置方案的质量，为了尽量将同类应用实例放置到一个虚拟机上，以减少应用实例的数量和资源消耗，可以按照同类应用实例放在一起的规则来进行放置。

例如，在图3的示例中，首先放置A1的实例，然后放置A2的实例，最后放置A3的实例。由于S1和S2是同属A1的两个实例，当它们被放置在同一个虚拟机VM5上时，应把它们作为一个实例来处里，该实例上放置两个租户T1和T2。图4描述了图3所示的应用实例序列和虚拟机序列（染色体编码）所对应的放置方案。

初始染色体的生成以及建立染色体与放置方案之间映射关系的算法如下：

算法2 染色体生成及放置方案映射算法。

输入：初始应用实例集AIS、初始虚拟机集合VMS；

输出：染色体P、P所对应的租户放置关系PRTA和应用实例放置关系PRAV。

步骤1 按照同类应用实例放在一起的规则，生成AIS中应用实例的一个序列Q＝i1，i2，…，iy（应用实例放置顺序），Q 为集合｛1，2，…，y｝的一个排列，y＝｜AIS｜。

步骤2 随机生成VMS中虚拟机的一个序列P＝j1，j2，…，jx，P 为集合｛1，2，…，x｝的一个排列（代表一条染色体，对应于虚拟机放置顺序），x＝｜VMS｜。

步骤3 按顺序取出Q中的每个应用实例，首先检查将该应用实例放置到P中的第一个虚拟机上是否可行，如果不可行则再放置到P中的下一个虚拟机上，直至找到一个可以放置的虚拟机为止；然后建立该应用实例与所放置的虚拟机之间的放置关系，以及其上租户与应用实例之间的放置关系，分别加入PRAV和PRTA中。

步骤4 重复步骤3，直到Q中所有的应用实例都被放置为止。

算法2的时间复杂度为O（x（y），其中x和y分别为初始虚拟机数量和应用实例数量。

3．3 遗传操作与染色体修复

遗传操作包括交叉操作和变异操作。针对基于虚拟机序列的编码方式，采用循环交叉操作和移位变异操作。

循环交叉的核心思想是子串位置上的值必须与父母相同位置上的值相等［14］，其主要步骤如下：

步骤1 选择父染色体P1的第一个基因作为子染色体C1的第一位，选择父染色体P2的第一个基因作为子染色体C2的第一位。

步骤2 在P1中找出P2的第一个基因赋给C1的相对位置，并把P2中该位置的基因赋给C2的相对位置，重复此过程，直至P2上得到P1的第一个基因为止，称为一个循环。

步骤3 对最前面的基因按P1、P2基因轮替原则重复以上步骤。

步骤4 重复以上步骤，直至所有的位都完成。

循环交叉操作的时间复杂度是O（x2），如图5所示为循环交叉过程的示意图。

移位变异是任意选择一位基因，将其移动到最前面，该操作的时间复杂度是O（x），图6描述了移位变异过程的示意图。

3．4 适应函数

本文的优化目标是降低租用虚拟机的成本，如果两个放置方案的成本相同，则部署应用实例数量少的方案优于应用实例数量多的方案，这是因为较多的应用实例将会带来较高的维护成本。

设P为一个染色体（对应放置方案），c和y分别为P的虚拟机成本和应用实例的数量，将适应函数定义为一个二元组F（P）＝（c，y），并定义适应函数之间的等价关系“◦”和超优关系“≺”。

设P1和P2为两个染色体，c1和c2分别为P1和P2的虚拟机成本，y1和y2分别为P1和P2的应用实例数量，即F（P1）＝（c1，y1），F（P2）＝（c2，y2）。如果c1＜c2，则F（P2）≺F（P1）；如果c1＝c2且y1＜y2，则F（P2）≺F（P1）；如果c1＝c2且y1＝y2，则F（P2）≡F（P1）。如果F（P2）≺F（P1），则说明P1的适应度大于P2的适应度，如果F（P2）≡F（P1），则说明P1的适应度等于P2的适应度。本文的优化目标就是选择适应度大的放置方案。

3．5 遗传算法

基于前述分析，给出多租户SaaS应用优化放置遗传算法。

算法3 多租户SaaS应用优化放置遗传算法。

输入：初始应用实例集AIS、初始租户放置关系PRTA、虚拟机集合VMS、资源消耗度量模型、适应函数、种群大小pop＿size、遗传操作进化代数gen、交叉操作概率pc，变异操作概率pm；

输出：最优放置方案P。

步骤1 设定种群大小pop＿size，遗传操作进化代数gen、交叉操作概率pc、变异操作概率pm等参数的取值。

步骤2 产生初始种群old＿pop，令g＝0表示当前代数。

步骤3 将当前种群old＿pop中个体适应度最大的染色体放入新种群new＿pop。

步骤4 从种群old＿pop中采用轮盘赌算法任选两条染色体进行交叉、变异等遗传操作，计算新染色体的个体适应度并放入new＿pop中，令g＝g＋1。

步骤5 若g＜gen，则old＿pop＝new＿pop，转步骤3；否则转步骤6。

步骤6 从new＿pop中选择适应度值最高的染色体best＿chrom，根据该染色体计算得出最终的放置方案P。

在算法3中，步骤1的时间复杂度是O（1），可以忽略不计；步骤2初始化种群的时间复杂度是O（pop＿size·x·y）；步骤3和步骤6的时间复杂度都是O（gen）；步骤4～步骤5的时间复杂度是O（gen（x2）。因此，算法3的时间复杂度是O（pop＿size·x·y＋2（gen＋gen（x2）＝O（pop＿size·x·y＋gen（x2），加上确定初始虚拟机数量的时间复杂度O（q·y2），整个问题求解的时间复杂度为O（q·y2＋pop＿size·x·y＋gen·x2）。

4 实验分析

本文所提算法已经利用Java进行了模拟仿真，实验环境为：CPU为双核AMD Athlon 2．7GHz，内存2GB，操作系统为Windows 7。

4．1 实验参数设定

实验参数设定主要是对模拟仿真实验中所涉及的各类参数进行，包括虚拟机模拟参数、SaaS应用模拟参数、租约模拟参数和算法实验参数。

（1）虚拟机参数 虚拟机类型参考亚马逊EC2的虚拟机模板类型进行参数设置，主要考虑CPU、内存和存储三种资源，不同虚拟机类型的资源数量不同，成本价格也不同，如表1所示。其中，CPU的单位为CU（compute unit），内存的单位是 GiB（230字节），存储的单位是G。小型的虚拟机CPU大小为1CU，内存为1．7GiB，存储为160G，价格为0．115＄/h。可以根据实验的需要动态增加虚拟机类型及其模拟参数。设虚拟机的资源利用率αij＝0．95。

表1 EC2虚拟机资源约束及价格表

（2）应用参数 应用的模拟数据按如下方法设置：

1）应用对资源的初始消耗r＊ik取值范围为［1，5］×10－2，忽略了隔离租户的资源消耗。

2）假设资源消耗函数fik（w，u）与用户数u呈线性关系，fik（w，u）的斜率取值范围为（0，10］，基准响应时间设置为w＝0．1s。

仿真实验中，模拟了12个应用Ak（k＝1，2，…，12），每个应用的主要模拟参数为资源消耗函数的斜率，其详细参数设置如表2所示。可以根据实验的需要动态增加应用及其模拟参数。

表2 基准响应时间资源消耗函数斜率表

续表2

（3）租户租约参数 一个租户租约包含了租用的应用类型、用户数量、响应时间、起止日期和价格等信息，本文主要关注应用类型、用户数量和响应时间，响应时间集合定义为R＝｛0．1，0．3，0．5｝s。

（4）算法实验参数 算法实验参数包括种群大小、进化代数、交叉概率、变异概率、租约个数和用户数，详细设置如表3所示。

表3 算法实验参数设置

4．2 实验结果分析

通过实验仿真，分别实现了用基于应用实例编码的遗传算法（Genetic Algorithm based on Application Instances Coding，AI－GA）［10］、基于虚拟机编码的遗传算法（Genetic Algorithm based on Virtual Machines Coding，VM－GA）［13］和基于虚拟机序列编码的遗传算法（Genetic Algorithm based on Virtual Machines Order Coding，VMO－GA）等算法求解多租SaaS应用放置问题，并从运行时间、运行结果、收敛速度等方面进行了分析和对比。

（1）VMO－GA运行结果分析

首先分析VMO－GA的平均收敛速度。图7显示了租约个数为200时算法运行100次的平均收敛速度，在每次运行中，进化到400代左右算法开始收敛到一个相对最优的结果。

接下来分析VMO－GA的进化代数为400、租约个数仍然为200时，交叉概率和变异概率对算法结果的影响。图8显示了交叉概率与运行结果之间的关系，从图中可以看出，在交叉概率为0．8时运行结果最好，最好时虚拟机成本为4．921 6，交叉概率小于或大于0．8时运行得出的虚拟机成本都会变大。

图9显示了在交叉概率为0．8时变异概率与运行结果之间的关系。当变异率为0．05时运行结果最好，虚拟机成本为4．916 4＄，变异率大于或小于0．05时运行得出的虚拟机成本都会增大。

种群的大小对算法的运行结果也有很大的影响，一般种群规模越大、运行结果越好，但是所消耗的时间也越长，因此通常采用一个折中的大小。图10显示了租约个数为200、进化代数为400、交叉概率和变异概率分别为0．8和0．05时，VMO－GA的运行结果与种群大小之间的关系。

（2）三种算法运行结果比较

首先对三种算法的运行时间进行比较。以租约个数为500，进化代数分别为50，100，150，200，250，300，350，400时的运行时间为例，随着进化代数的增加，三种算法的运行时间都呈线性增长，在相同进化代数下，VM－GA的运行时间最长，VMO－GA的

运行时间居中，而AI－GA的运行时间最少，如图11所示。

进一步比较三种算法的求解质量。从运行结果来看，VMO－GA和VM－GA在求解多租户SaaS应用放置问题时的结果远远优于AI－GA，如图12所示。在进化代数为500时，随着进化代数的逐渐增加，虚拟机成本逐渐收敛到一个最小的值，AI－GA，VMO－GA和 VM－GA 得 到 的 最 好 结 果 分 别 为64．148 5＄，10．887 5＄和10．929 1＄。通过实验结果可以看出，VMO－GA和VM－GA的收敛速度比AI－GA快，而在虚拟机成本上，VMO－GA得到的结果最好，VM－GA的结果次之，AI－GA的结果最差。

4．3 应用案例

为了说明多租户SaaS应用放置方案的确定过程，以图3所描述的租户放置关系为例，分析最终放置方案的选择策略。在本例中，包含5个租户、8个租约和3个应用，根据初始应用实例的计算规则（见第3．1节），每个租约映射为一个应用实例，租约的参数设置如表4所示。

表4 租户SLA需求设置

当租户确定了租约的响应时间和用户数后，就可以根据本文提出的资源消耗模型（见第2章），对各租约的资源消耗进行计算。这里忽略了隔离租户的资源消耗，应用A1，A2和A3的基准响应时间资源消耗函数斜率如表2所示，虚拟机的资源利用率设置为0．95。表5给出每个租约所对应的初始应用实例放置在虚拟机上的资源需求，包括应用实例在没有租户放置情况下的初始资源需求，以及在实际响应时间下根据用户数增长的资源需求，这两部分的和就是租约部署在虚拟机上资源需求。

表5 租约的资源需求

为简化问题的复杂度，这里只考虑小、中、大三种虚拟机类型，其资源约束和价格如表1所示。首先根据算法1，可以确定三类虚拟机的初始数量，如图3右侧所示；然后根据算法2和算法3，选出一条最优的染色体作为最终的放置策略，租户、应用实例和虚拟机之间的映射关系如图 所示。根据放置策4略，确定需要中型虚拟机1个、大型虚拟机2个，因此，租用虚拟机的成本为1．15＄/h。对租户和应用实例进行放置后，每个虚拟机的负载情况如表6所示。

表6 虚拟机负载情况

5 结束语

本文提出了基于成本优化的多租户 应用SaaS放置模型和算法。研究了在多租户SaaS应用部署的初始阶段，如何根据租户的需求来确定应用部署的SaaS应用实例的数量以及租用的虚拟机数量，并建立租户与SaaS应用实例、SaaS应用实例与虚拟机之间的放置关系，使租用的虚拟机成本最低，对于SaaS提供商减少初期资金投入具有重要意义。本文提出了面向租户服务响应时间的资源消耗度量模型，给出了基于成本优化的多租户SaaS应用放置问题的形式化描述；依据租约关系给出了计算初始的应用实例数量和虚拟机数量的方法，并采用基于虚拟机序列编码的遗传算法来求解多租户SaaS应用放置问题；通过实验分析了算法的可行性与有效性，并与基于应用实例编码的遗传算法和基于虚拟机的遗传算法进行了比较，证明了该方法具有较高的求解质量；最后通过一个实例说明了多租户SaaS应用放置方案的确定过程。

由于目前还缺乏实际的实验环境，本文主要采用模拟实验的方法对所提算法进行验证。下一步工作主要集中在两方面：①基于已有的项目基础，搭建实际的应用环境，从而进一步验证本文所提出方法的可行性；②研究将多租户SaaS应用部署到云环境后，如何进行在线租户优化放置，以提高资源的利用率。

［1］ BOSS G，MALLADI P，QUAN D，et al．Cloud computing［EB/OL］．［2013－01－10］．http：//download．boulder．ibm．com/ibmdl/pub/software/dw/wes/hipods/Cloud＿computing＿wp＿final＿8Oct．

［2］ KANG S，KANG S，HUR S．A design of the conceptual architecture for a multitenant SaaS application platform［C］//Proceedings of the 2011 1st ACIS/JNU International Conference on Computers，Networks，Systems，and Industrial Engineering．Washington，D．C．，USA：IEEE Computer Society，2011：462－467．

［3］ WU L L，KUMAR S，BUYYA R．SLA－based rsource allocation for software as a service provider（SaaS）in cloud computing environments［C］//Proceedings of the IEEE/ACM International Symposium on Cluster，Cloud and Grid Computing．Washington，D．C．，USA：IEEE Computer Society，2011：195－204．

［4］ WU L L，GARG S K，BUYYA R．SLA－based admission control for a Software－as－a－service provider in cloud computing environments［J］．Journal of Computer and System Science，2012，78（5）：1280－1299．

［5］ Wikipedia．Amazon．com［EB/OL］．［2013－01－10］．http：//en．wikipedia．org/wiki/Amazon．com．

［6］ KWOK T，MOHINDRA A．Resource calculations with constraints，and placement of tenants and instances for multi－tenant SaaS applications［C］//Proceedings of International Conference on Service－Oriented Computing．Berlin，Germany：Springer－Verlag，2008：633－648．

［7］ ZHANG Y，WANG Z H，GAO B．An effective heuristic for on－line tenant placement problem in SaaS［C］//Proceedings of IEEE International Conference on Web Services．Washington，D．C．，USA：IEEE Computer Society，2010：425－432．

［8］ YU H Y，WANG D S．System resource allocation algorithm for multi－tenant SaaS application［C］//Proceedings of International Conference on Cloud and Service Computing．Washington，D．C．，USA：IEEE Computer Society，2011：207－211．

［9］ WANG Deshuai，ZHANG Yichuan，ZHANG Bin，et al．Load balancing strategy for multi－tenancy SaaS applications supporting service on demand［J］．Journal of Northeastern University：Natural Science，2011，32（3）：353－355（in Chinese）．［汪德帅，张一川，张 斌，等．支持多租约SaaS应用按需服务的负载均衡策略 ［J］．东北大学学报：自然科学版，2011，32（3）：353－355．］

［10］ IZZAH Z，YUSOH M，TANG M．A penalty－based genetic algorithm for the composite SaaS placement problem in the cloud［C］//Proceedings of the IEEE Congress on Evolutionary Computation．Washington，D．C．，USA：IEEE Computer Society，2010：1－8．

［11］ YANG E F，ZHANG Y，WU L，et al．A hybrid approach to placement of tenants for service－based multi－tenant SaaS application［C］//Proceeding of IEEE Asia－Pacific Services Com－puting Conference．Washington，D．C．，USA：IEEE Computer Society，2011：124－130．

［12］ ZHANG Dabin，LIU Guiqin，WANG Jing，et al．Genetic algorithm based on group coding for bin－packing problem［J］．Computer Engineering and Design，2008，29（12）：3154－3156（in Chinese）．［张大斌，刘桂琴，王 婧，等．基于群体编码方式的遗传算法求解装箱问题［J］．计算机工程与设计，2008，29（12）：3154－3156．］

［13］ FALKENAUER E，DELCHAMBRE A．A genetic algorithm for bin packing and line balancing［C］//Proceedings of the IEEE International Conference on Robotics and Automation．Washington，D．C．，USA：IEEE Computer Society，1992：1186－1192．

［14］ WANG Dingwei，WANG Junwei，WANG Hongfeng，et al．Intelligent optimization methods［M］．Beijing：Higher Education Press，2007（in Chinese）．［汪定伟，王俊伟，王洪峰，等．智能优化方法［M］．北京：高等教育出版社，2007．］