孟凡超，周學(xué)權(quán)，曹祖鳳，初佃輝，戰(zhàn)德臣

（哈爾濱工業(yè)大學(xué)（威海）企業(yè)與服務(wù)智能計算研究中心，山東 威海 264209）

0 引言

隨著云計算的出現(xiàn)，IT領(lǐng)域正在進(jìn)行著一場深刻的變革。云計算是一種新型的計算模型，它將IT資源、數(shù)據(jù)和應(yīng)用作為服務(wù)，通過互聯(lián)網(wǎng)提供給用戶［1］。云計算根據(jù)其服務(wù)類型可分為基礎(chǔ)設(shè)施即服務(wù)（Infrastructure as a Service，IaaS）、平臺即服務(wù)（Platform as a Service，PaaS）和軟件即服務(wù)（Software as a Service，SaaS）。在SaaS模式下，客戶不需要購買完整的軟件系統(tǒng)，也不需要配備相應(yīng)的硬件系統(tǒng)和維護(hù)人員，只需通過互聯(lián)網(wǎng)按需租用應(yīng)用軟件即可，這對成本預(yù)算有限、技術(shù)條件不足的中小企業(yè)來說，具有很強(qiáng)的吸引力［2］。

在云計算環(huán)境下，SaaS主要涉及客戶（也稱為租戶）、SaaS提供商和云基礎(chǔ)設(shè)施提供商［3］三類角色。租戶租用SaaS提供商所提供的SaaS應(yīng)用來滿足自己的業(yè)務(wù)需求，每個租戶可以租用一個或多個SaaS應(yīng)用。SaaS提供商通過向租戶提供SaaS應(yīng)用服務(wù)來獲取利潤，每個SaaS應(yīng)用可以部署多個實例，這些實例被部署在云基礎(chǔ)設(shè)施提供商所提供的虛擬機(jī)上，例如，Amazon的彈性計算云EC2，或者部署在自己的服務(wù)器或虛擬機(jī)上，本文主要研究前者，即租用云基礎(chǔ)設(shè)施提供商的虛擬機(jī)，此時SaaS提供商需要向云基礎(chǔ)設(shè)施提供商支付相應(yīng)的租金［4］。云基礎(chǔ)設(shè)施提供商對外提供一組虛擬機(jī)模板，由同一模板所生成的虛擬機(jī)具有相同的資源配置和價格，例如，亞馬遜提供的虛擬機(jī)模板有m1．small，m1．large和 m1．large等［5］。

基于成本優(yōu)化的SaaS應(yīng)用放置是指在SaaS應(yīng)用部署的初始階段，SaaS提供商根據(jù)已有租戶的數(shù)量以及對每類租戶市場規(guī)模的預(yù)測，確定應(yīng)部署的SaaS應(yīng)用實例的數(shù)量和租用每一類虛擬機(jī)的數(shù)量，并建立租戶與SaaS應(yīng)用實例，以及SaaS應(yīng)用實例與虛擬機(jī)之間的放置關(guān)系，其優(yōu)化目標(biāo)是在滿足每個租戶服務(wù)級別協(xié)議（Service Level Agreement，SLA）的條件下，使租用的虛擬機(jī)的總成本最低。

1 相關(guān)工作

針對多租戶SaaS應(yīng)用優(yōu)化放置問題，國內(nèi)外學(xué)者已經(jīng)展開了許多研究。Kwok等提出一種多租戶SaaS應(yīng)用實例資源消耗度量模型，該模型描述了SaaS應(yīng)用實例的資源消耗與租戶數(shù)量和用戶數(shù)量之間的關(guān)系，基于該模型，又提出了一種租戶放置算法并開發(fā)了相應(yīng)的支撐工具［6］。Zhang等擴(kuò)展了Kwok等所提出的資源消耗度量模型，加入了服務(wù)響應(yīng)時間的約束，并提出一種啟發(fā)式在線租戶放置算法［7］。Wu 等 站 在 SaaS 提 供 商 的 角 度［3－4］，提 出了基于SLA的SaaS應(yīng)用資源分配算法以降低租用虛擬機(jī)的成本，并通過仿真實驗來模擬在線租戶放置過程。Yu等提出了面向租戶服務(wù)質(zhì)量（Quality of Service，QoS）的資源優(yōu)化分配模型，同時給出啟發(fā)式算法和遺傳算法，并對這兩種算法的性能進(jìn)行了比較［8］。汪德帥等面向租約用戶的非功能需求，提出一種支持多租約SaaS應(yīng)用按需服務(wù)的負(fù)載均衡策略［9］。Izzah等研究了構(gòu)件化的SaaS應(yīng)用優(yōu)化部署問題，提出一種基于懲罰的遺傳算法來求解最優(yōu)SaaS放置方案［10］。Yang等針對基于服務(wù)的SaaS應(yīng)用，提出一個基于案例推理（Case－Based Reasoning，CBR）的混合租戶放置方法［11］。

多租戶SaaS應(yīng)用放置可分為租戶放置和SaaS應(yīng)用實例放置兩方面，租戶放置是指確定租戶與SaaS應(yīng)用實例之間的服務(wù)關(guān)系；SaaS應(yīng)用實例放置是指建立SaaS應(yīng)用實例與服務(wù)器或虛擬機(jī)之間的部署關(guān)系。然而，現(xiàn)有研究大多針對租戶放置［3－4，6－9，11］，對 SaaS 應(yīng) 用 實 例 放 置 的 研 究 比 較 少。有些研究雖然也考慮了資源的預(yù)分配［8－9］和SaaS應(yīng)用實例的放置策略［10］，但都是在給定服務(wù)器/虛擬機(jī)的數(shù)量，即限定資源數(shù)量的基礎(chǔ)上進(jìn)行的優(yōu)化，然而現(xiàn)實情況是服務(wù)器/虛擬機(jī)的數(shù)量和SaaS應(yīng)用實例的數(shù)量是不確定的，例如，SaaS提供商在初次租用虛擬機(jī)/服務(wù)器時，只知道虛擬機(jī)的類型，如EC2的小、中、大型虛擬機(jī)，但要租用的各類虛擬機(jī)的個數(shù)未知，而且要部署的SaaS實例的個數(shù)也需要根據(jù)租戶需求確定。

因此，對于給定的租戶需求，如何確定需要部署的SaaS應(yīng)用實例的數(shù)量和租用的虛擬機(jī)數(shù)量，同時建立租戶與SaaS應(yīng)用實例，以及SaaS應(yīng)用實例與虛擬機(jī)之間的放置關(guān)系，是本文所要解決的問題。針對該問題，本文通過分析多租戶SaaS應(yīng)用服務(wù)模式，提出了面向租戶響應(yīng)時間的資源消耗度量模型，采用基于虛擬機(jī)序列的遺傳算法來求解多租戶SaaS應(yīng)用優(yōu)化放置問題，并通過實驗分析了算法的可行性和有效性，最后通過一個應(yīng)用案例來描述放置方案的確定過程。

2 多租戶SaaS應(yīng)用放置模型

設(shè)某SaaS提供商有m個租戶，對外提供n種SaaS應(yīng)用（簡稱應(yīng)用），每種應(yīng)用可以部署多個SaaS應(yīng)用實例（簡稱應(yīng)用實例），每個應(yīng)用實例可以放置多個租戶，這些應(yīng)用實例需要部署在云基礎(chǔ)設(shè)施提供商所提供的虛擬機(jī)上。設(shè)云基礎(chǔ)設(shè)施提供商對外提供q種虛擬機(jī)，應(yīng)用實例的運(yùn)行需要消耗其所在虛擬機(jī)的資源，例如，CPU、內(nèi)存、網(wǎng)絡(luò)帶寬等，設(shè)p為資源種類的數(shù)量。每個租戶在使用應(yīng)用前需要與SaaS提供商簽訂SLA，SLA規(guī)定了應(yīng)用實例所要滿足的性能需求。應(yīng)用實例所消耗的資源一般與該應(yīng)用的類型、租戶數(shù)量、并發(fā)用戶數(shù)量以及租戶的性能需求等因素有關(guān)，對于性能需求，本文主要考慮服務(wù)響應(yīng)時間。

基于成本優(yōu)化的多租戶SaaS應(yīng)用放置問題可描述為：對于給定的租戶集合TS＝｛T1，T2，…，Tm｝、應(yīng)用集合 AS＝｛A1，A2，…，An｝、租戶與應(yīng)用之間的租約關(guān)系集合TA?TS×AS、虛擬機(jī)類型集合VMTS＝｛VMT1，VMT2，…，VMTq｝，確定多租戶SaaS應(yīng)用放置方案，即確定SaaS提供商所要租用云基礎(chǔ)設(shè)施提供商的虛擬機(jī)數(shù)量xj、部署應(yīng)用實例的數(shù)量應(yīng)用實例與虛擬機(jī)之間的放置關(guān)系集合PRAV?AIS×VMS、租戶與應(yīng)用實例之間的放置關(guān)系集合PRTA?TS×AIS，其優(yōu)化目標(biāo)是租用虛擬機(jī)的成本最低，并且部署的應(yīng)用實例數(shù)量y盡可能少。

其中：xj表示虛擬機(jī)類型VMTj的實例數(shù)量；yj表示應(yīng)用Aj的實例數(shù)量；AIS表示部署的應(yīng)用實例集合；VMS表示租用的虛擬機(jī)集合，它們的數(shù)量分別為y和x；cj表示虛擬機(jī)類型VMTj的成本。

多租戶SaaS應(yīng)用放置的一個關(guān)鍵問題是建立應(yīng)用的資源消耗模型。本文借鑒文獻(xiàn)［6－7］的思想，提出一個面向租戶服務(wù)響應(yīng)時間的資源消耗模型。

設(shè)Sk∈AIS表示被部署的第k（k＝1，2，…，y）個應(yīng)用實例，VMj∈VMS 表示被租用的第j（j＝1，2，…，x）個虛擬機(jī)，當(dāng)把Sk放置到VMj上時，Sk在VMj上消耗的第i（i＝1，2，…，p）種資源的數(shù)量其中：表示在沒有租戶和用戶時的資源消耗；表示隔離租戶的資源消耗，隔離租戶指當(dāng)多個租戶共享同一應(yīng)用實例時，為使不同租戶的業(yè)務(wù)和數(shù)據(jù)互不干擾所采取的技術(shù)手段表示處理用戶服務(wù)請求的資源消耗，ut表示租戶t∈Tk所包含的并發(fā)用戶數(shù)量，Tk表示放置在Sk上的租戶集合，rt表示租戶t∈Tk對Sk服務(wù)響應(yīng)時間的需求，fik（r，u）＝（w/r）·fik（w，u），fik（w，u）表示基準(zhǔn)響應(yīng)時間為w、并發(fā)用戶數(shù)為u時Sk對第i類資源的消耗，該函數(shù)可以根據(jù)測試和實際運(yùn)行數(shù)據(jù)來確定［6－7］。一般來說，隔離租戶的資源消耗遠(yuǎn)小于處理用戶服務(wù)請求的資源消耗［6］。

設(shè)rij表示虛擬機(jī)VMj上的第i（i＝1，2，…，p）種資源的最大可用量，則有

式中：zj表示在VMj上放置的應(yīng)用實例的數(shù)量，αij表示VMj上第i種資源的最大利用率。

綜上所述，基于成本優(yōu)化的多租戶SaaS應(yīng)用優(yōu)化部署問題可以表示為：

例如，某SaaS提供商有5個租戶，對外提供3種應(yīng)用，云基礎(chǔ)設(shè)施提供商為其提供3種虛擬機(jī)模板，圖1描述了租戶與應(yīng)用之間的租約關(guān)系。針對圖1所示的租約關(guān)系，圖2給出一種多租戶SaaS應(yīng)用放置方案：租用類型為VMT1的兩個虛擬機(jī)VM1和VM2，租用類型為VMT3的1個虛擬機(jī)VM3，即租用虛擬機(jī)的數(shù)量x＝3（x1＝2，x2＝0，x3＝1）；部署2個A1實例S1和S2，部署2個A2實例S3和S4，部署1個A3實例S5，即部署應(yīng)用實例的數(shù)量為y＝5（y1＝2，y2＝2，y3＝1）；應(yīng)用實例S1和S3放置在虛擬機(jī)VM1上，應(yīng)用實例S2和S4放置在虛擬機(jī)VM2上，應(yīng)用實例S5放置在虛擬機(jī)VM3上；應(yīng)用實例S1上放置1個租戶T1，應(yīng)用實例S2上放置1個租戶T2，應(yīng)用實例S3上放置2個租戶T2和T3，應(yīng)用實例S4上放置1個租戶T4，應(yīng)用實例S5上放置3個租戶T2、T4和T5，即應(yīng)用實例放置關(guān)系集PRAV＝｛（S1，VM1），（S3，VM1），（S2，VM2），（S4，VM2），（S5，VM3）｝，租戶放置關(guān)系集PRTA＝｛（T1，S1），（T2，S2），（T2，S3），（T2，S3），（T2，S5），（T3，S3），（T4，S4），（T4，S5），（T5，S5）｝。

基于成本優(yōu)化的多租戶SaaS應(yīng)用放置問題可以劃分為2個子問題：①確定應(yīng)用實例數(shù)量y（y≤｜TA｜）和虛擬機(jī)的數(shù)量x（x≥q）；②確定租戶放置關(guān)系PRTA和應(yīng)用實例放置關(guān)系PRAV。其中問題②可以看作是將y個物體放到x個箱子的裝箱問題，其中，每個物體代表一個應(yīng)用實例及其所包含的租戶，每個箱子代表一個虛擬機(jī)，該問題的時間復(fù)雜度為xy，因此，多租戶SaaS應(yīng)用放置問題屬于NP問題。為提高問題的求解效率和質(zhì)量，本文提出一個基于虛擬機(jī)序列的遺傳算法來求解近似最優(yōu)放置方案。

3 多租戶SaaS應(yīng)用優(yōu)化放置遺傳算法

3．1 初始應(yīng)用實例和虛擬機(jī)的確定

為了采用遺傳算法進(jìn)行問題求解，首先需要確定放置方案的染色體編碼方式。因為在初始部署階段，應(yīng)用實例的個數(shù)和虛擬機(jī)個數(shù)都未知，所以染色體的長度和基因的取值都是不確定的，不能直接運(yùn)用遺傳算法進(jìn)行求解。為此，首先根據(jù)租約關(guān)系來確定初始的應(yīng)用實例數(shù)量和虛擬機(jī)的數(shù)量，具體計算方法如下：

（1）將每一個租約關(guān)系（Ti，Aj）∈TA 映射為一個租戶放置關(guān)系（Ti，Sk）∈PRTA，其中，Sk為Aj的一個實例，并且對于每個應(yīng)用的每個租戶都分配一個不同的實例，這樣可以確定初始的應(yīng)用實例集AIS，其數(shù)量為租約關(guān)系的數(shù)量y＝｜TA｜，且每個應(yīng)用實例只放置一個租戶。

（2）對每一種虛擬機(jī)VMTi（i＝1，2，…，q），計算所有應(yīng)用實例都放置到該類虛擬機(jī)時，需要的虛擬機(jī)實例個數(shù)的下限xi，則初始的虛擬機(jī)需求數(shù)量可以定義為這樣可以保證有足夠的虛擬機(jī)供選擇，本文的目標(biāo)就是從這些虛擬機(jī)中選擇能夠放置所有應(yīng)用實例及其所包含的租戶、并且滿足成本最低的一組虛擬機(jī)。

確定每一類虛擬機(jī)VMTi（i＝1，2，…，q）需求數(shù)量的算法如下：

算法1 確定每類虛擬機(jī)需求數(shù)量。

輸入：初始應(yīng)用實例集AIS、虛擬機(jī)類型VMTi；

輸出：VMTi的需求數(shù)量xi。

步驟1 令VMSi＝?為已部署的VMTi實例集（VMSi為有序集）。

步驟2 生成VMTi的一個實例加入VMSi中。

步驟3 從AIS中取出一個應(yīng)用實例Sk。

步驟4 依次檢查VMSi中的每個實例VMj，計算將Sk放置到VMj后，VMj的每一類資源需求量是否滿足其資源可用量約束。

（1）如果滿足，則將Sk從AIS中取出，并將其加入VMj所放置的應(yīng)用實例集AIS（VMj）中，轉(zhuǎn)步驟3；

（2）如果不滿足，則生成VMTi的一個實例，加入VMSi的第一個位置，轉(zhuǎn)步驟4；

（3）如果AIS中的所有應(yīng)用實例都已放置，即AIS＝?，則轉(zhuǎn)步驟5。

步驟5 輸出VMTi的需求數(shù)量xi＝｜VMSi｜。

算法1的最壞時間復(fù)雜度是O（｜AIS｜2）＝O（y2），即AIS中的每個應(yīng)用實例都放置在不同的虛擬機(jī)中，則確定所有類型的虛擬機(jī)數(shù)量的時間復(fù)雜度為O（q·y2）。

例如，針對圖1所示的租約關(guān)系，可以確定如圖3左側(cè)所示的8個初始租戶放置關(guān)系：（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）。根據(jù)算法1，可以確定初始虛擬機(jī)數(shù)量，為了簡化問題的復(fù)雜度，這里省略了計算過程，只給出計算結(jié)果，三類虛擬機(jī)的初始數(shù)量分別為4，3和4，即x＝11（x1＝4，x2＝3，x3＝4），它們的編號如圖3右側(cè)所示。

3．2 染色體編碼設(shè)計

確定了初始應(yīng)用實例數(shù)量和虛擬機(jī)需求數(shù)量后，就可以對放置方案進(jìn)行編碼。針對該類問題，目前的編碼方式主要有基于應(yīng)用實例（看作物體）的編碼和基于虛擬機(jī)（看作箱子）的編碼［12］?；趹?yīng)用實例的編碼方式是每個基因代表一個初始應(yīng)用實例，基因的取值為初始虛擬機(jī)的編號，表示該應(yīng)用實例所放置的虛擬機(jī)［10］?；谔摂M機(jī)的編碼方式是每個基因表示一個初始虛擬機(jī)，基因的取值為一組應(yīng)用實例的集合，表示放置在該虛擬機(jī)上的所有應(yīng)用實例［13］。

通過實驗發(fā)現(xiàn)，采用這兩種編碼方式的遺傳算法在求解多租戶SaaS應(yīng)用放置問題時的優(yōu)化結(jié)果都不是很理想。目前，基于應(yīng)用實例編碼的染色體主要采用隨機(jī)生成的方法，即對每個基因隨機(jī)生成一個虛擬機(jī)編號［10］。對于多租戶應(yīng)用放置問題來說，如果初始的虛擬機(jī)數(shù)量非常大，則采用隨機(jī)生成方式會導(dǎo)致被選擇的虛擬機(jī)的數(shù)量非常多，算法的收斂速度會很慢，而且解的質(zhì)量也很低。另外，隨機(jī)生成還會產(chǎn)生許多不可行的染色體，對這些染色體進(jìn)行修復(fù)還會消耗一定的時間。雖然基于虛擬機(jī)的編碼在解的質(zhì)量上有所提高，但是由于編碼方式的復(fù)雜性，算法的時間復(fù)雜度相對較高［13］。

針對上述兩種編碼方式存在的問題，本文提出一種基于虛擬機(jī)序列的編碼方式，在該編碼方式中，每條染色體是一個初始虛擬機(jī)的序列，表示一個初始應(yīng)用實例序列所放的順序。例如，針對圖3右側(cè)所示的初始虛擬機(jī)集合，可隨機(jī)生成一個初始虛擬機(jī)序列：1 2 5 9 3 4 6 7 8，表示初始應(yīng)用實例序列S1S2S3S4S5S6S7S8的放置順序，即按照該順序?qū)⑦@些應(yīng)用實例先放置到虛擬機(jī)VM1中，如果VM1放滿（表示該虛擬機(jī)當(dāng)前狀態(tài)下的可用資源不能再滿足應(yīng)用實例序列中沒有被放置的任何應(yīng)用實例的資源需求）則再往VM2中放置，如果VM2放滿則再往VM5中放置，直到所有應(yīng)用實例都被放完為止，此時可能還存在閑置的虛擬機(jī)，表示它們沒有被選擇。在此例中選擇了VM1，VM2，VM5和VM94個虛擬機(jī)，其中：S1和S2放置在VM1中，S3和S4放置在VM2中，S5，S6和S7放置在VM5中，S8放置在VM9中，其他虛擬機(jī)則沒有被選擇。對基于虛擬序列的編碼方式來說，由于不同的虛擬機(jī)序列會產(chǎn)生不同的放置方案，虛擬機(jī)的序列是影響求解質(zhì)量的關(guān)鍵因素。

在應(yīng)用實例放置過程中，如果同一應(yīng)用的多個實例被放置到一個虛擬機(jī)上，則將這些應(yīng)用實例合并為一個應(yīng)用實例（同一應(yīng)用在一個虛擬機(jī)上只能部署一個實例），合并后的應(yīng)用實例的租戶為這些應(yīng)用實例租戶的并集，因此在計算應(yīng)用實例的資源消耗時，不是單獨計算每個應(yīng)用實例的資源消耗再求它們的和，而是先按照類別合并同類應(yīng)用實例，再計算合并后每類應(yīng)用實例的資源消耗，最后求所有應(yīng)用類別的資源消耗之和。因此，對基于虛擬序列的編碼方式來說，應(yīng)用實例的放置順序也會影響放置方案的質(zhì)量，為了盡量將同類應(yīng)用實例放置到一個虛擬機(jī)上，以減少應(yīng)用實例的數(shù)量和資源消耗，可以按照同類應(yīng)用實例放在一起的規(guī)則來進(jìn)行放置。

例如，在圖3的示例中，首先放置A1的實例，然后放置A2的實例，最后放置A3的實例。由于S1和S2是同屬A1的兩個實例，當(dāng)它們被放置在同一個虛擬機(jī)VM5上時，應(yīng)把它們作為一個實例來處里，該實例上放置兩個租戶T1和T2。圖4描述了圖3所示的應(yīng)用實例序列和虛擬機(jī)序列（染色體編碼）所對應(yīng)的放置方案。

初始染色體的生成以及建立染色體與放置方案之間映射關(guān)系的算法如下：

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

輸入：初始應(yīng)用實例集AIS、初始虛擬機(jī)集合VMS；

輸出：染色體P、P所對應(yīng)的租戶放置關(guān)系PRTA和應(yīng)用實例放置關(guān)系PRAV。

步驟1 按照同類應(yīng)用實例放在一起的規(guī)則，生成AIS中應(yīng)用實例的一個序列Q＝i1，i2，…，iy（應(yīng)用實例放置順序），Q 為集合｛1，2，…，y｝的一個排列，y＝｜AIS｜。

步驟2 隨機(jī)生成VMS中虛擬機(jī)的一個序列P＝j(luò)1，j2，…，jx，P 為集合｛1，2，…，x｝的一個排列（代表一條染色體，對應(yīng)于虛擬機(jī)放置順序），x＝｜VMS｜。

步驟3 按順序取出Q中的每個應(yīng)用實例，首先檢查將該應(yīng)用實例放置到P中的第一個虛擬機(jī)上是否可行，如果不可行則再放置到P中的下一個虛擬機(jī)上，直至找到一個可以放置的虛擬機(jī)為止；然后建立該應(yīng)用實例與所放置的虛擬機(jī)之間的放置關(guān)系，以及其上租戶與應(yīng)用實例之間的放置關(guān)系，分別加入PRAV和PRTA中。

步驟4 重復(fù)步驟3，直到Q中所有的應(yīng)用實例都被放置為止。

算法2的時間復(fù)雜度為O（x（y），其中x和y分別為初始虛擬機(jī)數(shù)量和應(yīng)用實例數(shù)量。

3．3 遺傳操作與染色體修復(fù)

遺傳操作包括交叉操作和變異操作。針對基于虛擬機(jī)序列的編碼方式，采用循環(huán)交叉操作和移位變異操作。

循環(huán)交叉的核心思想是子串位置上的值必須與父母相同位置上的值相等［14］，其主要步驟如下：

步驟1 選擇父染色體P1的第一個基因作為子染色體C1的第一位，選擇父染色體P2的第一個基因作為子染色體C2的第一位。

步驟2 在P1中找出P2的第一個基因賦給C1的相對位置，并把P2中該位置的基因賦給C2的相對位置，重復(fù)此過程，直至P2上得到P1的第一個基因為止，稱為一個循環(huán)。

步驟3 對最前面的基因按P1、P2基因輪替原則重復(fù)以上步驟。

步驟4 重復(fù)以上步驟，直至所有的位都完成。

循環(huán)交叉操作的時間復(fù)雜度是O（x2），如圖5所示為循環(huán)交叉過程的示意圖。

移位變異是任意選擇一位基因，將其移動到最前面，該操作的時間復(fù)雜度是O（x），圖6描述了移位變異過程的示意圖。

3．4 適應(yīng)函數(shù)

本文的優(yōu)化目標(biāo)是降低租用虛擬機(jī)的成本，如果兩個放置方案的成本相同，則部署應(yīng)用實例數(shù)量少的方案優(yōu)于應(yīng)用實例數(shù)量多的方案，這是因為較多的應(yīng)用實例將會帶來較高的維護(hù)成本。

設(shè)P為一個染色體（對應(yīng)放置方案），c和y分別為P的虛擬機(jī)成本和應(yīng)用實例的數(shù)量，將適應(yīng)函數(shù)定義為一個二元組F（P）＝（c，y），并定義適應(yīng)函數(shù)之間的等價關(guān)系“?”和超優(yōu)關(guān)系“?”。

設(shè)P1和P2為兩個染色體，c1和c2分別為P1和P2的虛擬機(jī)成本，y1和y2分別為P1和P2的應(yīng)用實例數(shù)量，即F（P1）＝（c1，y1），F(xiàn)（P2）＝（c2，y2）。如果c1＜c2，則F（P2）?F（P1）；如果c1＝c2且y1＜y2，則F（P2）?F（P1）；如果c1＝c2且y1＝y(tǒng)2，則F（P2）≡F（P1）。如果F（P2）?F（P1），則說明P1的適應(yīng)度大于P2的適應(yīng)度，如果F（P2）≡F（P1），則說明P1的適應(yīng)度等于P2的適應(yīng)度。本文的優(yōu)化目標(biāo)就是選擇適應(yīng)度大的放置方案。

3．5 遺傳算法

基于前述分析，給出多租戶SaaS應(yīng)用優(yōu)化放置遺傳算法。

算法3 多租戶SaaS應(yīng)用優(yōu)化放置遺傳算法。

輸入：初始應(yīng)用實例集AIS、初始租戶放置關(guān)系PRTA、虛擬機(jī)集合VMS、資源消耗度量模型、適應(yīng)函數(shù)、種群大小pop＿size、遺傳操作進(jìn)化代數(shù)gen、交叉操作概率pc，變異操作概率pm；

輸出：最優(yōu)放置方案P。

步驟1 設(shè)定種群大小pop＿size，遺傳操作進(jìn)化代數(shù)gen、交叉操作概率pc、變異操作概率pm等參數(shù)的取值。

步驟2 產(chǎn)生初始種群old＿pop，令g＝0表示當(dāng)前代數(shù)。

步驟3 將當(dāng)前種群old＿pop中個體適應(yīng)度最大的染色體放入新種群new＿pop。

步驟4 從種群old＿pop中采用輪盤賭算法任選兩條染色體進(jìn)行交叉、變異等遺傳操作，計算新染色體的個體適應(yīng)度并放入new＿pop中，令g＝g＋1。

步驟5 若g＜gen，則old＿pop＝new＿pop，轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟6。

步驟6 從new＿pop中選擇適應(yīng)度值最高的染色體best＿chrom，根據(jù)該染色體計算得出最終的放置方案P。

在算法3中，步驟1的時間復(fù)雜度是O（1），可以忽略不計；步驟2初始化種群的時間復(fù)雜度是O（pop＿size·x·y）；步驟3和步驟6的時間復(fù)雜度都是O（gen）；步驟4～步驟5的時間復(fù)雜度是O（gen（x2）。因此，算法3的時間復(fù)雜度是O（pop＿size·x·y＋2（gen＋gen（x2）＝O（pop＿size·x·y＋gen（x2），加上確定初始虛擬機(jī)數(shù)量的時間復(fù)雜度O（q·y2），整個問題求解的時間復(fù)雜度為O（q·y2＋pop＿size·x·y＋gen·x2）。

4 實驗分析

本文所提算法已經(jīng)利用Java進(jìn)行了模擬仿真，實驗環(huán)境為：CPU為雙核AMD Athlon 2．7GHz，內(nèi)存2GB，操作系統(tǒng)為Windows 7。

4．1 實驗參數(shù)設(shè)定

實驗參數(shù)設(shè)定主要是對模擬仿真實驗中所涉及的各類參數(shù)進(jìn)行，包括虛擬機(jī)模擬參數(shù)、SaaS應(yīng)用模擬參數(shù)、租約模擬參數(shù)和算法實驗參數(shù)。

（1）虛擬機(jī)參數(shù) 虛擬機(jī)類型參考亞馬遜EC2的虛擬機(jī)模板類型進(jìn)行參數(shù)設(shè)置，主要考慮CPU、內(nèi)存和存儲三種資源，不同虛擬機(jī)類型的資源數(shù)量不同，成本價格也不同，如表1所示。其中，CPU的單位為CU（compute unit），內(nèi)存的單位是 GiB（230字節(jié)），存儲的單位是G。小型的虛擬機(jī)CPU大小為1CU，內(nèi)存為1．7GiB，存儲為160G，價格為0．115＄/h。可以根據(jù)實驗的需要動態(tài)增加虛擬機(jī)類型及其模擬參數(shù)。設(shè)虛擬機(jī)的資源利用率αij＝0．95。

表1 EC2虛擬機(jī)資源約束及價格表

（2）應(yīng)用參數(shù) 應(yīng)用的模擬數(shù)據(jù)按如下方法設(shè)置：

1）應(yīng)用對資源的初始消耗r＊ik取值范圍為［1，5］×10－2，忽略了隔離租戶的資源消耗。

2）假設(shè)資源消耗函數(shù)fik（w，u）與用戶數(shù)u呈線性關(guān)系，fik（w，u）的斜率取值范圍為（0，10］，基準(zhǔn)響應(yīng)時間設(shè)置為w＝0．1s。

仿真實驗中，模擬了12個應(yīng)用Ak（k＝1，2，…，12），每個應(yīng)用的主要模擬參數(shù)為資源消耗函數(shù)的斜率，其詳細(xì)參數(shù)設(shè)置如表2所示?？梢愿鶕?jù)實驗的需要動態(tài)增加應(yīng)用及其模擬參數(shù)。

表2 基準(zhǔn)響應(yīng)時間資源消耗函數(shù)斜率表

續(xù)表2

（3）租戶租約參數(shù) 一個租戶租約包含了租用的應(yīng)用類型、用戶數(shù)量、響應(yīng)時間、起止日期和價格等信息，本文主要關(guān)注應(yīng)用類型、用戶數(shù)量和響應(yīng)時間，響應(yīng)時間集合定義為R＝｛0．1，0．3，0．5｝s。

（4）算法實驗參數(shù) 算法實驗參數(shù)包括種群大小、進(jìn)化代數(shù)、交叉概率、變異概率、租約個數(shù)和用戶數(shù)，詳細(xì)設(shè)置如表3所示。

表3 算法實驗參數(shù)設(shè)置

4．2 實驗結(jié)果分析

通過實驗仿真，分別實現(xiàn)了用基于應(yīng)用實例編碼的遺傳算法（Genetic Algorithm based on Application Instances Coding，AI－GA）［10］、基于虛擬機(jī)編碼的遺傳算法（Genetic Algorithm based on Virtual Machines Coding，VM－GA）［13］和基于虛擬機(jī)序列編碼的遺傳算法（Genetic Algorithm based on Virtual Machines Order Coding，VMO－GA）等算法求解多租SaaS應(yīng)用放置問題，并從運(yùn)行時間、運(yùn)行結(jié)果、收斂速度等方面進(jìn)行了分析和對比。

（1）VMO－GA運(yùn)行結(jié)果分析

首先分析VMO－GA的平均收斂速度。圖7顯示了租約個數(shù)為200時算法運(yùn)行100次的平均收斂速度，在每次運(yùn)行中，進(jìn)化到400代左右算法開始收斂到一個相對最優(yōu)的結(jié)果。

接下來分析VMO－GA的進(jìn)化代數(shù)為400、租約個數(shù)仍然為200時，交叉概率和變異概率對算法結(jié)果的影響。圖8顯示了交叉概率與運(yùn)行結(jié)果之間的關(guān)系，從圖中可以看出，在交叉概率為0．8時運(yùn)行結(jié)果最好，最好時虛擬機(jī)成本為4．921 6，交叉概率小于或大于0．8時運(yùn)行得出的虛擬機(jī)成本都會變大。

圖9顯示了在交叉概率為0．8時變異概率與運(yùn)行結(jié)果之間的關(guān)系。當(dāng)變異率為0．05時運(yùn)行結(jié)果最好，虛擬機(jī)成本為4．916 4＄，變異率大于或小于0．05時運(yùn)行得出的虛擬機(jī)成本都會增大。

種群的大小對算法的運(yùn)行結(jié)果也有很大的影響，一般種群規(guī)模越大、運(yùn)行結(jié)果越好，但是所消耗的時間也越長，因此通常采用一個折中的大小。圖10顯示了租約個數(shù)為200、進(jìn)化代數(shù)為400、交叉概率和變異概率分別為0．8和0．05時，VMO－GA的運(yùn)行結(jié)果與種群大小之間的關(guān)系。

（2）三種算法運(yùn)行結(jié)果比較

首先對三種算法的運(yùn)行時間進(jìn)行比較。以租約個數(shù)為500，進(jìn)化代數(shù)分別為50，100，150，200，250，300，350，400時的運(yùn)行時間為例，隨著進(jìn)化代數(shù)的增加，三種算法的運(yùn)行時間都呈線性增長，在相同進(jìn)化代數(shù)下，VM－GA的運(yùn)行時間最長，VMO－GA的

運(yùn)行時間居中，而AI－GA的運(yùn)行時間最少，如圖11所示。

進(jìn)一步比較三種算法的求解質(zhì)量。從運(yùn)行結(jié)果來看，VMO－GA和VM－GA在求解多租戶SaaS應(yīng)用放置問題時的結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于AI－GA，如圖12所示。在進(jìn)化代數(shù)為500時，隨著進(jìn)化代數(shù)的逐漸增加，虛擬機(jī)成本逐漸收斂到一個最小的值，AI－GA，VMO－GA和 VM－GA 得 到 的 最 好 結(jié) 果 分 別 為64．148 5＄，10．887 5＄和10．929 1＄。通過實驗結(jié)果可以看出，VMO－GA和VM－GA的收斂速度比AI－GA快，而在虛擬機(jī)成本上，VMO－GA得到的結(jié)果最好，VM－GA的結(jié)果次之，AI－GA的結(jié)果最差。

4．3 應(yīng)用案例

為了說明多租戶SaaS應(yīng)用放置方案的確定過程，以圖3所描述的租戶放置關(guān)系為例，分析最終放置方案的選擇策略。在本例中，包含5個租戶、8個租約和3個應(yīng)用，根據(jù)初始應(yīng)用實例的計算規(guī)則（見第3．1節(jié)），每個租約映射為一個應(yīng)用實例，租約的參數(shù)設(shè)置如表4所示。

表4 租戶SLA需求設(shè)置

當(dāng)租戶確定了租約的響應(yīng)時間和用戶數(shù)后，就可以根據(jù)本文提出的資源消耗模型（見第2章），對各租約的資源消耗進(jìn)行計算。這里忽略了隔離租戶的資源消耗，應(yīng)用A1，A2和A3的基準(zhǔn)響應(yīng)時間資源消耗函數(shù)斜率如表2所示，虛擬機(jī)的資源利用率設(shè)置為0．95。表5給出每個租約所對應(yīng)的初始應(yīng)用實例放置在虛擬機(jī)上的資源需求，包括應(yīng)用實例在沒有租戶放置情況下的初始資源需求，以及在實際響應(yīng)時間下根據(jù)用戶數(shù)增長的資源需求，這兩部分的和就是租約部署在虛擬機(jī)上資源需求。

表5 租約的資源需求

為簡化問題的復(fù)雜度，這里只考慮小、中、大三種虛擬機(jī)類型，其資源約束和價格如表1所示。首先根據(jù)算法1，可以確定三類虛擬機(jī)的初始數(shù)量，如圖3右側(cè)所示；然后根據(jù)算法2和算法3，選出一條最優(yōu)的染色體作為最終的放置策略，租戶、應(yīng)用實例和虛擬機(jī)之間的映射關(guān)系如圖 所示。根據(jù)放置策4略，確定需要中型虛擬機(jī)1個、大型虛擬機(jī)2個，因此，租用虛擬機(jī)的成本為1．15＄/h。對租戶和應(yīng)用實例進(jìn)行放置后，每個虛擬機(jī)的負(fù)載情況如表6所示。

表6 虛擬機(jī)負(fù)載情況

5 結(jié)束語

本文提出了基于成本優(yōu)化的多租戶 應(yīng)用SaaS放置模型和算法。研究了在多租戶SaaS應(yīng)用部署的初始階段，如何根據(jù)租戶的需求來確定應(yīng)用部署的SaaS應(yīng)用實例的數(shù)量以及租用的虛擬機(jī)數(shù)量，并建立租戶與SaaS應(yīng)用實例、SaaS應(yīng)用實例與虛擬機(jī)之間的放置關(guān)系，使租用的虛擬機(jī)成本最低，對于SaaS提供商減少初期資金投入具有重要意義。本文提出了面向租戶服務(wù)響應(yīng)時間的資源消耗度量模型，給出了基于成本優(yōu)化的多租戶SaaS應(yīng)用放置問題的形式化描述；依據(jù)租約關(guān)系給出了計算初始的應(yīng)用實例數(shù)量和虛擬機(jī)數(shù)量的方法，并采用基于虛擬機(jī)序列編碼的遺傳算法來求解多租戶SaaS應(yīng)用放置問題；通過實驗分析了算法的可行性與有效性，并與基于應(yīng)用實例編碼的遺傳算法和基于虛擬機(jī)的遺傳算法進(jìn)行了比較，證明了該方法具有較高的求解質(zhì)量；最后通過一個實例說明了多租戶SaaS應(yīng)用放置方案的確定過程。

由于目前還缺乏實際的實驗環(huán)境，本文主要采用模擬實驗的方法對所提算法進(jìn)行驗證。下一步工作主要集中在兩方面：①基于已有的項目基礎(chǔ)，搭建實際的應(yīng)用環(huán)境，從而進(jìn)一步驗證本文所提出方法的可行性；②研究將多租戶SaaS應(yīng)用部署到云環(huán)境后，如何進(jìn)行在線租戶優(yōu)化放置，以提高資源的利用率。

［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應(yīng)用按需服務(wù)的負(fù)載均衡策略 ［J］．東北大學(xué)學(xué)報：自然科學(xué)版，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］．計算機(jī)工程與設(shè)計，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）．［汪定偉，王俊偉，王洪峰，等．智能優(yōu)化方法［M］．北京：高等教育出版社，2007．］