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

呂騰飛， 陳世平

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

云計算是在并行計算、分布式計算、網格計算基礎上發展起來的新型計算模型[1-3]。任務調度和資源分配是云計算的兩大關鍵技術，資源分配決定著資源的使用規則，關系到云計算的執行效率和并發處理能力。云計算資源管理的核心是規則和資源分配，即根據確定的資源分配規則，將有限的資源分配給不同的用戶，滿足用戶指定的服務水平目標，優化服務提供架構。

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

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

1 相關工作

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

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

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

2 包簇概念

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

為此，本文引入了新的概念：包和簇，對用戶需求和云資源給出多級抽象的遞歸定義。將用戶的云服務需求抽象成一個需求包，不同用戶的需求包匯總在一起，可以進一步抽象為更大的需求包，最上層的所有需求包可以模塊化為一個需求池。即定義“包”為虛擬機和其他包的集合。同理，將一個數據中心的計算資源抽象成一個更大的資源池，該資源池由若干計算能力相同或不同的資源簇組成。即定義“簇”為數據中心拓撲位置相近的服務器或更低級別的簇的集合，簇所擁有的資源是其組成部分的資源之和。靈活性可以通過實現需求包到資源簇的映射獲得，不同需求包可以映射到相同的資源簇上，實現閑時資源共享。相似地，數據中心資源也可以組成由服務器、簇、簇中簇構成的多級別層次結構。數據中心資源分配問題，將由傳統的虛擬機到服務器映射轉換成需求包到資源簇映射，當包、簇抽象層級增加時，相關映射問題的規模將進一步下降。

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

圖 1 包層次結構Fig.1 Package structure

圖2 是在包簇概念下的1個數據中心機架上的服務器情況，圖2（a）是1個肥胖樹拓撲，當用簇代表每個機架上的服務器后，其拓撲結構簡化為圖2（b）。將低級別簇聚合成高級別簇后，其拓撲結構又可進一步簡化成圖2（c）。上層的資源簇是對若干相同或者不同的下層簇的聚合，最下層的資源簇實際上就是映射到機架上的服務器。基于簇的定義，構建資源簇的方式更加靈活。

圖 2 簇層次結構Fig. 2 Cluster structure

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

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

3 成本評估模型

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

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

內存資源的收費特點與CPU相同，其費用公式為

式中：Mb表示資源簇提供的基礎內存大小；表示需求包在 資源簇上使用基礎內存的時間；表示基礎部分的單價；Mi-Mb表示超出基礎內存部分的資源要求；是用戶對該部分資源的使用時間；pem是該部分內存資源的單位價格。

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

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

式中：α表示當前影響CPU費用的權重；β表示當前影響內存費用的權重；cb表示滿足正常網絡傳輸帶寬的費用；Rc表示滿足n個需求包映射到m個資源簇的費用。

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

4 云計算資源分配算法設計

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

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

4.2 IGAAA中遺傳算法的設置

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

圖 3 算法框架Fig. 3 Algorithm framework

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

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

步驟3 根據適應度函數，采用輪回順序交叉、逆轉變異的方法，迭代進化，選擇出適應度高的后代。

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

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

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

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

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

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

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

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

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

5 實驗分析

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

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

圖 5 簇使用個數Fig.5 Cluster usage

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

圖 6 任務數與任務完成時間關系Fig.6 Relationship between the task number and task completion time

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

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

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

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

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

表 1 算法性能Tab.1 Algorithm performance

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

6 結束語

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