基于包簇映射的云計算資源分配策略

呂騰飛， 陳世平

（上海理工大學(xué) 光電信息與計算機工程學(xué)院 上海 200093）

云計算是在并行計算、分布式計算、網(wǎng)格計算基礎(chǔ)上發(fā)展起來的新型計算模型[1-3]。任務(wù)調(diào)度和資源分配是云計算的兩大關(guān)鍵技術(shù)，資源分配決定著資源的使用規(guī)則，關(guān)系到云計算的執(zhí)行效率和并發(fā)處理能力。云計算資源管理的核心是規(guī)則和資源分配，即根據(jù)確定的資源分配規(guī)則，將有限的資源分配給不同的用戶，滿足用戶指定的服務(wù)水平目標(biāo)，優(yōu)化服務(wù)提供架構(gòu)。

目前，資源分配策略大多是在虛擬機級別上完成的，根據(jù)一定的分配策略，實現(xiàn)虛擬機到服務(wù)器的映射，即資源管理直接在個體虛擬機與個體服務(wù)器間進行[4]。但是，隨著數(shù)據(jù)中心規(guī)模的不斷擴大，用戶需求的動態(tài)變化，傳統(tǒng)的資源分配方式加大了對虛擬機預(yù)留資源的分配，導(dǎo)致所要解決問題規(guī)模的擴大，不利于實現(xiàn)虛擬機間空閑資源共享。由于這些資源分配算法的自身局限性，導(dǎo)致解決問題的時間復(fù)雜度和空間復(fù)雜度比較高，算法整體性能低下，運行效率不理想，數(shù)據(jù)中心資源利用率不高。

為了突破這些限制，本文引入了一種分層的抽象模型來降解問題的規(guī)模，即包、簇概念[5]。通過多目標(biāo)遺傳算法與改進的螞蟻算法融合[6]，將來自不同用戶的需求包映射到合適的資源簇上，來縮短任務(wù)時間，提高資源分配效率。在滿足需求包的同時，減少資源簇的數(shù)目，建立成本模型，評估資源分配過程中數(shù)據(jù)中心的成本，實現(xiàn)計算綠色、節(jié)能[7]。

1 相關(guān)工作

云計算中的資源分配問題是多目標(biāo)優(yōu)化問題，屬于裝箱問題，如何高效地實現(xiàn)資源分配是云計算的關(guān)鍵，直接影響到云環(huán)境的負(fù)載和性能。啟發(fā)式仿生算法，通過模擬生物進化過程，可以有效解決NP完全問題，在眾多可行解中，找到問題的最優(yōu)解，比傳統(tǒng)算法更加高效、可靠，有著不可比擬的優(yōu)越性。

面對用戶的彈性要求，云服務(wù)提供商如何在滿足用戶需求的前提下，降低服務(wù)成本，健全云計算資源分配機制，減少資源浪費，已經(jīng)成為國內(nèi)外云計算學(xué)者致力解決的一個研究問題。文獻(xiàn)[5]提出了一種基于染色體編碼方式和適應(yīng)度函數(shù)的改進遺傳算法，仿真結(jié)果表明，該算法能更好地適用于大規(guī)模任務(wù)下的云計算資源調(diào)度，但缺點是消耗資源太多和時間太長。文獻(xiàn)[8]提出了一種基于蟻群優(yōu)化的資源分配算法，該算法利用蟻群算法得到一組最優(yōu)的計算資源，仿真實驗證明，分配算法具有更短的響應(yīng)時間和更好的運行質(zhì)量，但由于前期信息素匱乏，求解速度較慢。文獻(xiàn)[9]提出了以應(yīng)用性能、保證云應(yīng)用的服務(wù)質(zhì)量和提高資源利用率為目標(biāo)的多目標(biāo)優(yōu)化模型，并結(jié)合最新的神經(jīng)網(wǎng)絡(luò)改進粒子群算法對云資源分配求解，但神經(jīng)網(wǎng)絡(luò)模型設(shè)計的合理性制約著算法的時間復(fù)雜度。文獻(xiàn)[10]提出了一種云計算環(huán)境下基于用戶的成本最優(yōu)存儲策略，在滿足用戶需求的前提下，構(gòu)建最低服務(wù)成本模型，提升服務(wù)性能，但該方法采用對文件進行分塊、冗余副本機制，將會造成存儲空間大量浪費，空間復(fù)雜度較差。文獻(xiàn)[11]提出了面向云計算任務(wù)的資源分配模型，采用層次分析法實現(xiàn)任務(wù)資源分配，提高了云計算資源的利用效益，但該方法在構(gòu)造比較矩陣過程中要維系數(shù)以千計的自由變量，可擴展性較差。

在以上研究工作的基礎(chǔ)上，本文將多目標(biāo)遺傳算法和改進的螞蟻算法融合（improved genetic algorithm ant algorithm, IGAAA），該算法在滿足不同用戶云服務(wù)需求的前提下，以節(jié)約成本為目標(biāo)，完成需求包到資源簇的映射，通過建立成本評估模型來評估系統(tǒng)開銷，從而減少服務(wù)成本，最大化資源利用效率。

2 包簇概念

在傳統(tǒng)的虛擬機層面上直接管理資源既不具備擴展性[12]，也不具備資源共享的靈活性。可擴展性問題主要表現(xiàn)在虛擬機中的資源到服務(wù)器映射時需要大量的變量維護。靈活性問題主要表現(xiàn)在用戶對資源需求的動態(tài)要求。

為此，本文引入了新的概念：包和簇，對用戶需求和云資源給出多級抽象的遞歸定義。將用戶的云服務(wù)需求抽象成一個需求包，不同用戶的需求包匯總在一起，可以進一步抽象為更大的需求包，最上層的所有需求包可以模塊化為一個需求池。即定義“包”為虛擬機和其他包的集合。同理，將一個數(shù)據(jù)中心的計算資源抽象成一個更大的資源池，該資源池由若干計算能力相同或不同的資源簇組成。即定義“簇”為數(shù)據(jù)中心拓?fù)湮恢孟嘟姆?wù)器或更低級別的簇的集合，簇所擁有的資源是其組成部分的資源之和。靈活性可以通過實現(xiàn)需求包到資源簇的映射獲得，不同需求包可以映射到相同的資源簇上，實現(xiàn)閑時資源共享。相似地，數(shù)據(jù)中心資源也可以組成由服務(wù)器、簇、簇中簇構(gòu)成的多級別層次結(jié)構(gòu)。數(shù)據(jù)中心資源分配問題，將由傳統(tǒng)的虛擬機到服務(wù)器映射轉(zhuǎn)換成需求包到資源簇映射，當(dāng)包、簇抽象層級增加時，相關(guān)映射問題的規(guī)模將進一步下降。

如圖1所示，一個跨國公司在上海、倫敦各有一個子公司，其總部設(shè)在舊金山。圖1中使用了3個包來分別描述總部和子公司的資源需求。其中，總部的需求包有1臺防火墻、虛擬機以及3個二級包，分別對應(yīng)了管理部、財務(wù)部和工程部的資源需求。

圖 1 包層次結(jié)構(gòu)Fig.1 Package structure

圖2 是在包簇概念下的1個數(shù)據(jù)中心機架上的服務(wù)器情況，圖2（a）是1個肥胖樹拓?fù)?，?dāng)用簇代表每個機架上的服務(wù)器后，其拓?fù)浣Y(jié)構(gòu)簡化為圖2（b）。將低級別簇聚合成高級別簇后，其拓?fù)浣Y(jié)構(gòu)又可進一步簡化成圖2（c）。上層的資源簇是對若干相同或者不同的下層簇的聚合，最下層的資源簇實際上就是映射到機架上的服務(wù)器?；诖氐亩x，構(gòu)建資源簇的方式更加靈活。

圖 2 簇層次結(jié)構(gòu)Fig. 2 Cluster structure

在包簇概念下，可以通過分層、遞歸的抽象模型，用局部代替整體，降解包到簇映射的問題規(guī)模。頂層需求包映射到頂層資源簇上，二級需求包映射到二級資源簇上，更低級別的需求包映射到更低級別的資源簇上。而且用戶需求包到資源簇映射的過程是遞歸重復(fù)的，當(dāng)最底層的虛擬機被映射到機架上的服務(wù)器時，停止遞歸過程，這樣已經(jīng)將用戶的所有需求包映射到簇節(jié)點上。采用這種“分而治之”的方法，可以將一個復(fù)雜度很高的、較難處理的問題簡化細(xì)分成若干個較低復(fù)雜度、可處理的子問題，針對每個子問題，又可以利用本文提出的融合改進算法求解。

在傳統(tǒng)的云計算中，利用虛擬化技術(shù)可以監(jiān)控每個計算節(jié)點的任務(wù)執(zhí)行情況。在某一時刻如果用戶對計算能力的要求超過當(dāng)前執(zhí)行節(jié)點的最大計算能力，任務(wù)將執(zhí)行失敗。但在包、簇概念下，可以很好地解決因為用戶需求的彈性變化導(dǎo)致資源分配不能滿足用戶需求的問題。不再為每臺虛擬機分配一個固定量的資源，而是為這些虛擬機指定一個公共的共享資源池，將這些資源共享的虛擬機以一個需求包的形式整體放在一個服務(wù)器集群上。

3 成本評估模型

在云環(huán)境中，用戶的需求是千差萬別的。如一些用戶需要很高的CPU來保證計算，另一些用戶對CPU沒有特殊要求，但需要更多的存儲，用來存儲數(shù)據(jù)文件。CPU和存儲的費用是不同的，不同用戶資源的使用時間也是各不相同。為了更好地評估資源分配的成本，本文將從資源使用時間和基礎(chǔ)資源成本兩個角度構(gòu)建成本模型。

式中：Cb表示該資源簇j提供的最低CPU資源，因為，在包簇概念下，可以有多個包被分配到同一個資源簇上，所以，每個資源簇首先都會為需求包分配一個最低的CPU資源；是當(dāng)前需求包對最低CPU使用的時間；pbc是對應(yīng)最低CPU的單位價格；Ci-Cb表示該需求包超出最低CPU資源部分的計算能力；是超出資源部分的使用時間；pec是超出資源部分的對應(yīng)單價。

內(nèi)存資源的收費特點與CPU相同，其費用公式為

式中：Mb表示資源簇提供的基礎(chǔ)內(nèi)存大?。槐硎拘枨蟀?資源簇上使用基礎(chǔ)內(nèi)存的時間；表示基礎(chǔ)部分的單價；Mi-Mb表示超出基礎(chǔ)內(nèi)存部分的資源要求；是用戶對該部分資源的使用時間；pem是該部分內(nèi)存資源的單位價格。

數(shù)據(jù)中心的網(wǎng)絡(luò)資源是一種特殊資源，對它的精確描述往往還涉及到網(wǎng)絡(luò)拓?fù)?，有研究表明，?shù)據(jù)中心上的大規(guī)模云計算可能還會面臨帶寬瓶頸的問題。數(shù)據(jù)中心帶寬資源的不足將會限制對云中其他資源的最優(yōu)化利用，并降低包映射到簇時的自由度。本文不考慮資源漂移問題，故對帶寬的要求僅滿足正常網(wǎng)絡(luò)傳輸即可。

本文的目標(biāo)是在保證所需時間內(nèi)能完成用戶的不同需求，做到最小化資源分配成本，即將每個需求子包分配到特定的資源簇上，使得使用的簇節(jié)點數(shù)目最少。需求包到資源簇的映射效益模型為

式中：α表示當(dāng)前影響CPU費用的權(quán)重；β表示當(dāng)前影響內(nèi)存費用的權(quán)重；cb表示滿足正常網(wǎng)絡(luò)傳輸帶寬的費用；Rc表示滿足n個需求包映射到m個資源簇的費用。

任務(wù)執(zhí)行時間越少，以及占用更少的數(shù)據(jù)中心計算資源，則該數(shù)據(jù)中心資源的利用率越高，因此，本文提出的成本評估模型的目的是最大化包簇映射的效益。

4 云計算資源分配算法設(shè)計

4.1 遺傳算法與螞蟻算法的融合

為了解決遺傳算法在進化的后期進行大量的無用迭代和螞蟻算法在進化初期由于缺少信息素進化緩慢的弊端，本文將遺傳算法在進化的“適時”階段融合進螞蟻算法，即遺傳算法與螞蟻算法的融合改進算法（improved genetic algorithm ant algorithm, IGAAA）。IGAAA算法的基本思想是吸取遺傳算法和螞蟻算法的優(yōu)點，克服各自的缺陷，揚長避短，優(yōu)勢互補，融合改進算法總體框架如圖3所示。

4.2 IGAAA中遺傳算法的設(shè)置

遺傳算法在解決多目標(biāo)優(yōu)化問題時，首先針對問題域中的每種可能情況使用染色體編碼方式進行編碼，也就是將所有可能存在的資源分配方案進行染色體編碼，用來表示需求包到資源簇的映射關(guān)系，即每產(chǎn)生一條染色體后代就表示為問題域中的一個可行性解，算法目標(biāo)首先是得到該問題域所有可行解的候選集，再在可行解候選集中找到最優(yōu)解，實現(xiàn)需求包與資源簇之間的最優(yōu)匹配。

圖 3 算法框架Fig. 3 Algorithm framework

步驟1 在IGAAA算法中，采用間接編碼方式對染色體編碼。初始化階段，隨機地將n個需求包映射到m個資源簇上。染色體的長度就是需求包的數(shù)目。每條染色體上的基因值表示該需求包對應(yīng)的資源簇。

步驟2 適應(yīng)度函數(shù)用于評估算法優(yōu)越性、收斂性，本文從成本角度，評估在包、簇概念下的資源分配效益情況。適應(yīng)度函數(shù)

步驟3 根據(jù)適應(yīng)度函數(shù)，采用輪回順序交叉、逆轉(zhuǎn)變異的方法，迭代進化，選擇出適應(yīng)度高的后代。

4.3 IGAAA中螞蟻算法的改進與銜接

圖4為遺傳算法與螞蟻算法進化率隨時間的變化趨勢圖。在NP完全問題中，同等求解規(guī)模下，分別采用遺傳算法和螞蟻算法求問題最優(yōu)解，每經(jīng)過時間間隔T，觀察進化速率。時間間隔T的設(shè)定與該問題規(guī)模成正比。隨著迭代次數(shù)的增加，發(fā)現(xiàn)在0～3T區(qū)間內(nèi)，遺傳算法呈下降趨勢，螞蟻算法呈上升趨勢。但是，就整體進化效率而言，遺傳算法優(yōu)于螞蟻算法。在3T時刻，兩算法的進化效率相等；在3T時刻之后，遺傳算法出現(xiàn)大量無用的冗余迭代，進化率趨于平緩。由于螞蟻算法正反饋的特點，信息素濃度的逐漸積累，其進化速率得到顯著提高。所以，應(yīng)在3T時刻之后融入螞蟻算法。

圖 4 遺傳算法與螞蟻算法進化率-時間關(guān)系圖Fig. 4 Evolutionary rate-time relationship between the genetic algorithm and ant algorithm

在本文的問題域中，如何確定3T時刻是解決問題的關(guān)鍵。采用動態(tài)融合策略來實現(xiàn)遺傳算法與螞蟻算法的融合。

步驟1 分別設(shè)置遺傳算法最小迭代次數(shù)Gmin和最大迭代次數(shù)Gmax。

步驟2 統(tǒng)計遺傳算法在迭代過程中子代的進化率，得到整個迭代過程中進化速率的最小值。

步驟3 遺傳算法在正常求解過程中，第i次的迭代記為Gi，其中，，，說明遺傳算法已進入無用迭代時期，求解速度減慢，應(yīng)在這一時刻引入螞蟻算法。

螞蟻圈模型是全局優(yōu)化較好的螞蟻算法[13]，結(jié)合實際問題，在此采用MMAS(max-min ant system)算法[14]對螞蟻圈模型改進。初始狀態(tài)，根據(jù)遺傳算法得到的信息素，放置螞蟻，為了獲得準(zhǔn)確的局部最優(yōu)解，充分利用螞蟻算法正反饋尋優(yōu)特點，將種群中每只螞蟻經(jīng)過路徑的信息素初始值設(shè)為最大值。在螞蟻圈中，只有到目標(biāo)物距離最短的螞蟻才能進行信息素的修改[15]。為了避免融合算法過早收斂非全局最優(yōu)解，將各路徑的信息素濃度限制在之間，超出這個范圍的值被強制設(shè)為或>[16]。

通過前期的遺傳算法已經(jīng)得到了一定的路徑信息素。所以，在螞蟻算法初始化階段，資源簇Rj信息素的初始值設(shè)置為

5 實驗分析

為了驗證本文提出的包、簇概念的科學(xué)性、可行性以及基于包、簇概念下云資源分配算法的收斂性能，現(xiàn)給出仿真實驗結(jié)果。仿真軟件采用Matlab，CloudSim，設(shè)置任務(wù)數(shù)為500個，設(shè)置的資源簇為120個。通過構(gòu)建成本評估模型，觀察分析簇節(jié)點的個數(shù)、任務(wù)執(zhí)行時間和成本。對比算法為多目標(biāo)虛擬機資源分配算法[17]（multi-object virtual machine resource allocation algorithm, MOA）以及文獻(xiàn)[6]提出的基于包簇框架的改進多目標(biāo)遺傳算法（improved multi-objective genetic algorithm based on package-cluster, IMOPC）。

本文中所有的服務(wù)器資源已經(jīng)抽象成資源簇概念，用戶的需求已經(jīng)抽象成需求包，為了驗證本文算法在同一需求下可以有效減少資源簇的個數(shù)，分別采用本文算法和文獻(xiàn)[6]中的IMOPC算法將500臺虛擬機部署到250臺物理服務(wù)器。通過仿真實驗得到圖5的結(jié)果。實驗表明，本文算法部署的簇個數(shù)明顯要比IMOPC算法部署的簇個數(shù)要少，這是因為本文算法后期采用了螞蟻算法，相較單一的遺傳算法能夠獲得更精確的解集。

圖 5 簇使用個數(shù)Fig.5 Cluster usage

任務(wù)完成時間越短，則任務(wù)執(zhí)行過程中對相應(yīng)資源的占用時間越短，降低了任務(wù)執(zhí)行成本，有效提高了數(shù)據(jù)中心資源的利用率。為了驗證本文算法的性能，將任務(wù)數(shù)從100增加到500，觀察本文算法與對比算法的任務(wù)完成時間y，如圖6所示。x為任務(wù)數(shù)。

圖 6 任務(wù)數(shù)與任務(wù)完成時間關(guān)系Fig.6 Relationship between the task number and task completion time

圖6 中，在相同任務(wù)數(shù)下，與另外兩種算法相比，本文算法的完成時間較少。在任務(wù)數(shù)小于300時，本文算法與IMOPC算法任務(wù)執(zhí)行時間相近，但是，隨著任務(wù)數(shù)的逐漸增多，動態(tài)融合的IGAAA算法的任務(wù)完成時間仍然保持在6×104s以內(nèi)，而其他2個算法的完成時間已經(jīng)大幅增長。這主要得益于本文算法前期采用遺傳算法獲得初始信息素，螞蟻算法在后期的快速求解能力。通過對比實驗可以看出，本文算法能夠有效地減少計算資源的投入時間。

云用戶在享受便捷云服務(wù)的同時，如何降低服務(wù)開銷是用戶普遍關(guān)切的問題。對云服務(wù)提供商來說，在保證服務(wù)質(zhì)量的同時，降低服務(wù)成本也是改進的方向。因此，降低任務(wù)執(zhí)行成本對云用戶和云提供商來說都是有益的。在任務(wù)數(shù)為200，不同完成時間要求下，分別觀察本文算法和對比算法的執(zhí)行情況，通過建立成本評估模型，評估各算法成本優(yōu)劣。圖7給出了仿真實驗的結(jié)果。

圖 7 不同任務(wù)完成時間限制下各任務(wù)執(zhí)行成本Fig.7 Execution cost of each task under the different task completion time limit

由圖7可知，任務(wù)完成時間與費用b為近似線性相關(guān)。在任一完成時間要求下，本文算法的任務(wù)平均執(zhí)行成本都低于對比算法。當(dāng)云任務(wù)完成時間從1.0×104增加到7.0×104時，本文提出的融合改進算法的任務(wù)執(zhí)行成本依舊保持在3.3×104～9.0×104，而IMOPC算法的任務(wù)執(zhí)行平均成本保持在 5.4×104～10.0×104，MOA 算法的平均任務(wù)執(zhí)行成本平均在7.7×104～11.0×104。分析得出，在同一需求、相同完成時間的條件下，本文提出的融合改進算法的任務(wù)執(zhí)行成本更低，在云環(huán)境計算資源分配上具有更好的性能。

在以上2個實驗的基礎(chǔ)上，建立成本評估模型，在任務(wù)數(shù)為200，要求任務(wù)完成時間為4×104s的情況下，取 α=0.7，β=0.3（其中，α+β=1），將實驗參數(shù)代入式（4），得到如表1所示的實驗結(jié)果。

表 1 算法性能Tab.1 Algorithm performance

在成本評估模型中，采用倒數(shù)的形式反映任務(wù)效益，即計算結(jié)果越大，任務(wù)完成時間和任務(wù)執(zhí)行成本越少。由表1可以看出，相比其他2個對比算法，本文算法具有更高的效益值。

6 結(jié)束語

提出了一種基于包簇映射的云計算資源分配策略，通過構(gòu)建包、簇層次模型，利用分而治之的思想，將龐大、復(fù)雜的云資源管理優(yōu)化問題分解成若干較低復(fù)雜度的可以通過遞歸循環(huán)解決的問題。實驗證明，利用包、簇概念可有效降解問題規(guī)模。為了有效地進行資源分配，將云環(huán)境中的計算資源以最低的服務(wù)成本通過彈性配置進行按需分配。為了使得計算資源能夠合理地按需進行分配，將多目標(biāo)遺傳算法與螞蟻算法動態(tài)融合，在仿真實驗中，通過比較任務(wù)完成時間、任務(wù)執(zhí)行的平均成本、資源簇的使用個數(shù)，衡量改進算法的性能。從實驗結(jié)果可以看出，在基于包簇框架的資源分配機制中，本文算法在資源分配上取得了較好的效果，相比傳統(tǒng)基于虛擬機的分配機制，更大程度地降低了成本。