梁 慈,陳世平,2
?
基于螢火蟲優化算法的資源再分配方法研究
梁 慈1,陳世平1,2
(1. 上海理工大學光電信息與計算機工程學院,上海 200093;2. 上海理工大學信息化辦公室,上海 200093)
為解決數據中心能耗高以及資源利用率低等問題,在包簇框架下提出一種基于螢火蟲優化算法的資源再分配方案。該方案采用首次適應算法對虛擬機進行初始分配,然后利用包簇映射框架分層思想降解問題規模,結合螢火蟲優化算法將資源利用率低于預設閾值的簇上的包以盡可能低的動態漂移能耗進行漂移,并通過關閉這些簇來降低數據中心能耗并提高資源利用率。在cloudsim仿真平臺對文中構建的資源再分配方案進行實驗仿真,結果表明該方案在降低能耗和提高資源利用率方面均有不錯表現。
數據中心;包簇;螢火蟲算法;包漂移;資源再分配
云計算作為一種新的計算模型,以其方便使用和強大的計算能力等優勢得到快速發展,大量數據中心也被建立起來。
隨著數據中心規模的不斷增加,數據中心能源成本也在不斷提高[1],據統計顯示2016年我國的數據中心總耗電量超過1200億千瓦時,這個數字超過了三峽大壩2016年全年總發電量(約1000億千瓦時)。造成數據中心高能耗的主要原因是設備數量增加和資源利用率低。
研究發現云計算平臺具有高動態性和資源異質性,因此虛擬機需要適應云計算的動態環境,通過充分利用服務和資源讓云計算數據中心達到較佳的狀態。為提高數據中心資源利用率,資源必須合理分配。然而傳統云計算資源管理方法[2]以虛擬機為中心,將資源管理直接在個體虛擬機和個體服務器間進行,這種細粒度資源管理模式導致分配問題規模增大。
鑒于此,文中采用包簇映射框架降解分配規模,并在該框架基礎上提出一種基于螢火蟲優化算法的資源再分配方案,其目的在于降低數據中心能耗問題[3],提高資源利用率。
云計算數據中心能耗成本高的主要來源可歸結為兩方面:一方面是為了增強云計算的處理能力,不斷增加物理服務器數量,導致數據中心規模不斷增長,帶來更多的能源消耗;另一方面是服務器資源利用率低導致大部分資源處于空閑狀態,產生不必要的能耗。因此迫切需要開發出新技術來提高數據中心服務器資源利用率,盡可能減少服務器開啟數量來解決數據中心高能耗問題。
目前隨著國內外研究人員的共同努力,在降低云數據中心能耗方面已經取得眾多研究成果。文 獻[4]提出一種基于分組遺傳算法的虛擬機部署方案,通過優化資源分配和調度體系以最大限度地減少系統的空閑能耗,進而降低數據中心的能源消耗。文獻[5]設計了一種改進的簡單虛擬機漂移(MSVM)算法,通過預估虛擬機上每個進程的計算量和每個虛擬機的閑置時間,將虛擬機漂移到另一個節能服務器,以降低數據中心的能源消耗。文獻[6]實現了一種降低云計算數據中心能耗的新型調度算法。通過優化虛擬機在服務器上的分配與合并,有效降低數據中心能源消耗,并在提高資源利用率方面有顯著改善。為提高云計算資源的利用率,保持負載平衡,文獻[7]設計了一種基于卡爾曼預測器的云計算資源調度算法,利用卡爾曼預測器預測虛擬資源下一時刻狀態,將任務分配到合適的虛擬資源進行調度。與此同時,文獻[8]為降低數據中心能耗提出了一種基于螢火蟲優化算法來解決虛擬機在服務器上的放置問題,在保證服務水平協議的情況下能有效降低數據中心的能源消耗。而文獻[9]為提高云計算的任務調度效率,改進了一種基于免疫算法的云計算任務調度策略,采用免疫算法求解,并基于蟻群算法核心思想來保持種群多樣性,防止局部最優解的出現,同時優化了抗體交叉策略以加快全局最優解的出現速度。考慮到現有虛擬機放置算法大多只關注成本控制和云資源使用率,忽略了負載均衡對系統性能的影響。鑒于此,文獻[10]提出一種基于改進粒子群算法的虛擬機放置算法,有效提高了資源利用率,有利于云數據中心進入負載均衡狀態。
結合上述文獻可以看出目前在降低云計算數據中心能耗問題以及提高數據中心資源利用率等方面已經取得眾多研究成果。但在優化資源分配過程中對虛擬機漂移產生的能耗問題考慮不足。只單一考慮通過優化資源分配來降低數據中心能耗有可能會造成資源分配過程中的動態漂移能耗大大增加,并不能從整體上降低能耗。
針對此問題,文中在包簇映射框架基礎上提出一種基于螢火蟲優化算法的資源再分配方法(Resource Redistribution Method Based On Glowworm Optimization Algorithm,RRMGSO),該方法將數據中心資源利用率低的簇上的包作為漂移對象,采用螢火蟲優化算法尋找最優的包簇映射關系。其中,在尋求包到簇之間最優的映射關系時,把包在漂移過程中產生的動態漂移能耗考慮在內,使得資源分配方案不僅能夠提高數據中心資源利用率,降低能耗,同時在資源分配過程中消耗盡可能少的動態漂移能耗。
文中提出的基于螢火蟲優化算法的資源再分配方法RRMGSO,首先采用首次適應算法對虛擬機進行初始分配,然后采用包簇映射框架分層思想降解計算規模,利用實時測量手段來監測開啟主機的資源利用率,查找數據中心資源利用率低于預設閾值的簇,將這些簇上的包通過螢火蟲優化算法以盡可能低的動態漂移能耗進行漂移,并通過關閉這些簇來降低數據中心能耗并提高資源利用率,最終實現以盡可能低的漂移能耗實現較優的資源再分配。
為改善現有資源管理方式低擴展性、低靈活性問題,文中采用包簇映射框架[11]。包簇框架將數據中心虛擬機-服務器之間的映射關系轉換為包-簇問題。采用遞歸方式將‘包’定義為虛擬機或子包的集合,每個包中的資源可以進行共享。定義‘簇’為數據中心拓撲中位置相近的服務器或更低級別簇的集合。其中,簇的層次結構是依據包的層次結構所構建的。
對包簇框架的資源分配形式化描述為:
設該框架具有個子包或虛擬機,以表示子包或虛擬機的編號,其中1≤≤。具有個子簇或服務器,以為子簇或服務器的編號,其中1≤≤。
當資源分配的總時間為時,每一個子簇在時刻對資源的可用總量記為a,k(),其中a,k()(a,cpu(), a,mem(),…),1≤≤,則子簇集群的資源供給矩陣定義如下:

每一個子包在時刻對資源的需求總量記為r,k(),其中r,k()(r,cpu(),r,mem(), …),則子包集群的需求矩陣定義如下:
因每個簇的供給資源應不低于其所支持映射的包的資源總需求,因此,我們要求包簇框架應滿足:

其中,1≤≤,1≤≤,x,p表示:
文中將能耗模型分為靜態能耗和動態漂移能耗,其中靜態能耗是指利用簇資源產生的能耗以及簇資源閑置浪費的能耗;動態漂移能耗是指對簇上的包進行漂移時產生的能耗。
2.2.1 動態漂移能耗模型
利用實時測量手段來監測開啟主機的資源利用率,并設置資源利用率下限閾值T作為包漂移條件。當資源利用率低于T時需將該簇上的全部包進行漂移,并關閉該簇以降低數據中心能耗。觸發條件見公式(2)。

(p,cpu)表示子簇當前資源利用率,T表示子簇的資源利用率下限閾值。
在漂移功率[12]已知的條件下,包漂移時間對漂移能耗起著重要的作用。文獻[13]研究表明虛擬機的漂移時間與虛擬機的大小(主要是內存)以及物理節點的可用帶寬有關。由于,文中是基于包簇框架,因此包漂移時間計算方法,如公式(3)所示:

其中,(v,p)表示部署在簇上的包占用的總內存,bw表示簇當前可用帶寬。
則包在漂移時產生的能耗E,如公式(4)所示:

其中,0表示包開始漂移時間,P(v,p)表示包漂移功率。
2.2.2 靜態能耗計算模型
靜態能耗是數據中心最主要的能源消耗。結合文獻[12]中能耗計算模型,數據中心的能耗主要由內存和磁盤產生。所以文中采用的能耗計算模型是對、內存和磁盤三者能耗的綜合考慮。
2.2.3 cpu能耗優化模型
研究表明,能耗與資源利用率近似呈線性關系,但在很多研究[14-16]表明能耗和資源利用率并非單純的線性關系。因此,文章在包簇框架下,參照文獻[17]通過引入經驗參數C和時間來修正兩者之間的關系。另外文中在考慮使用時產生能耗的同時將閑置時的能耗也考慮在內。修正后的能耗優化模型如公式(5)所示:

其中,(p,cpu)代表資源利用率,α表示使用率對能耗的影響因子,δ和γ是模型特定的常數,可以通過訓練獲得。
2.2.4 內存能耗計算模型
文中內存能耗采用命中次數和缺失次數進行計算,計算模型如公式(6)所示:

其中,E()表示時間內簇內存產生的總能耗,N()表示時間內命中次數,N()表示時間內缺失次數,α和為線性模型參數,可以通過訓練獲得。
2.2.5 磁盤能耗計算模型
磁盤主要是在讀取數據時產生能耗,因此文中磁盤能耗計算模型是通過計算時間內磁盤讀取和寫入的字節總數得到。磁盤能耗模型如公式(7)所示:

其中,E()表示時間內磁盤產生的總能耗,b(v,p)表示通過磁盤計數器獲得的簇中磁盤讀取和寫入的字節總數,α和γ為該模型的特定常數,可以通過訓練得到。
綜上所述,數據中心在時間內的靜態總能耗是、內存以及磁盤產生的能耗總和,計算模型如公式(8):

螢火蟲優化算法(glowworm swarm optimization,GSO)是模擬自然界螢火蟲群體行為的一類新穎的優化算法。這些螢火蟲各自攜帶自身的熒光素,在各自的區域決策范圍內以一定的概率向其鄰居螢火蟲移動。其中,螢火蟲的自身亮度取決于自身所在位置的目標值,亮度越高說明所處位置的目標值越好。螢火蟲在其區域決策范圍內尋找鄰居集合,亮度越高則螢火蟲的吸引力越大,吸引周圍的螢火蟲往這個方向移動。
螢火蟲優化算法的尋優過程包括以下幾個階段,即螢火蟲初始化、螢光素更新、螢火蟲移動和局部徑向范圍更新。
文中采用螢火蟲優化算法為待漂移的包尋找目標簇,實現資源再分配。結合文中提到的能耗計算模型,并參照螢火蟲優化算法的尋優策略,對文中所提基于螢火蟲優化算法的資源再分配方法RRMGSO進行設計。
首先根據前面提到的能耗計算模型,建立目標函數:

其中,E表示對包進行漂移過程中產生的動態漂移能耗;E表示對包進行再分配之后數據中心的能耗。另外,U表示簇對資源的利用率,這里主要是指對、內存和磁盤的利用率。
其次,根據構建的目標函數采用螢火蟲優化算法對包進行再分配,具體尋優過程描述如下:
(1)螢火蟲初始化階段
采用首次適應算法(First Fit Algorithm)將虛擬機初始分配到物理機器,即按順序查找物理機器,將虛擬機直接部署在滿足需求的物理機器上。然后根據其映射關系劃分包簇,并進行編碼。包內資源主要考慮三種,分別是,內存和磁盤。根據包在數據中心的位置進行編號,記為x()。
當0時,將包初始靜態能耗作為該包熒光素初始值l(0)。初始化包的感知范圍r,動態決策域半徑r()(0<r()s),移動步長,鄰居簇閾值n,熒光素衰變系數(<<1),螢光素增強系數和動態決策域更新率。
(2)熒光素更新階段
結合文中公式(9),將包分配給相應簇所產生的目標函數的效益值作為熒光素濃度更新因子。該目標函數效益值表示以較低的動態漂移能耗E對包進行漂移以降低再分配后的數據中心靜態能耗E和提高數據中心資源利用率(p,k)。為方便下文描述這里將目標函數用表示,目標函數效益值越大,表示該包的熒光素濃度越高。l()表示時刻包的熒光素濃度,則包在漂移過程中熒光素更新如公式(10):

其中,表示熒光素衰變系數,表示螢光素增強系數。
(3)運動階段
步驟一:查找鄰居
簇要成為包的鄰居,必須滿足在的決策域范圍內并且的熒光素值要高于。當包進行漂移時,根據公式(11)更新鄰居集合,使待漂移包能更高效地找到目標簇。時刻包鄰居集合()如下:

步驟二:計算移動概率
為保證在對包進行分配時能得到較高的目標函數效益值,通過熒光素計算待分配的包到鄰居集合中每個備選目標簇之間的移動概率。其中,時刻包移向備選目標簇的概率p()計算方法如公式(12):

其中l()表示時刻備選目標簇的熒光素值,l()表示時刻待漂移包的熒光素值。
步驟三:位置更新
待漂移的包依據其移動概率,采用輪盤賭法確定其移動方向,并根據公式(13)更新漂移后包的位置。位置更新方法如下所示:

其中,x(1)為包i再分配后的位置,x()為包待分配前的位置,為移動步長。
(4)動態決策域更新階段
確定部分包的最優位置后,根據公式(14)改變決策區域半徑以動態調整鄰居集合。時刻包的動態決策域半徑更新策略如下所示:

根據初始資源分配劃分簇的數量N,即螢火蟲種群數量,劃分待漂移包的數量,即子群數量。
文中所提RRMGSO算法代碼描述如下:
1 Input: PhList N, VMlist M, set of paramseter
2 Ouput: Allocation of package-cluster
3 Initialize paramseters:l(0),r(0),r,,n,,,,count
4 Set InitialPosition of package-cluster
5 Initilize curBulletionBoard by package-cluster postion
6 g = Glowworm(M) //g表示待漂移的包
7 for k=1 to counttdo//迭代次數
8 for j=1 to M do
9 currentluc = g.calculateLuc(F(x)) by Eq.(10)
10 neighbours = g.getNeighbours(N, lj(t)) by Eq.(11)
11 MovingProbaility = g.calculateclu(l(t)) by Eq.(12)
12 NewPosition = g.upDatePosition(x(t)) by Eq.(13)
13 DynamicRadius = g.upDateDynamicRadius(N())by Eq.(14)
14 newBulletionBoard = bulletionboard.upDate(N(t),l(t)) //選擇目標簇并計算熒光素值最高的包位置,然后更新公告板
15 if newBulletionBoard >curBulletionBoard then //更新公告板
16 curBulletionBoard =newBulletionBoard
17 end if
18 end for
19 end for
20 Allocation package-cluster = PhList.get(curBulletionBoard) //多次迭代后,根據公告板上最終的位置確定資源再分配方案
21 return Allocationpackage-cluster //返回目標值
為驗證文中所提算法合理性,本文采用CloudSim仿真平臺[18]進行實驗。首先在該平臺上模擬一個數據中心,由于用戶需求的動態變化性,為更加準確地模擬數據中心資源分配效果,在實驗平臺選取50,100至500臺虛擬機采用首次適應算法部署到物理服務器上。采用自底向上逐層劃分包結構,其中最底層為虛擬機,并根據包簇映射關系劃分簇結構,其中最底層為服務器。
文中仿真實驗需要對一些參數進行初始化,通過查閱大量相關文獻,文中對主要參數初始化設置如表1所示:
表1 主要參數初始化設置

Tab.1 The main parameter settings
為保證實驗可靠性,仿真實驗過程中嚴格保持物理機器屬性、虛擬機任務和資源閾值等影響因素的一致性。
實驗1 能耗計算
為驗證文中所提算法的可行性,將該算法與初始分配的首次適應算法(First Fit Algorithm,FFA)以及文獻[12]中提出的基于包簇框架的改進多目標遺傳算法(Improved MultiObjective genetic algorithm based on Package-Cluster,IMOPC)進行比較。實驗結果如圖1、圖2所示。

圖1 靜態能耗比較

圖2 動態漂移能耗比較
由圖1、2可知,文中所提RRMGSO算法是可行的。圖1中隨著規模的增加,文中算法產生的靜態能耗逐漸比IMOPC算法和FFA算法低。圖2中文中算法產生的動態漂移能耗也比IMOPC算法低。這主要是因為同樣基于包簇框架的IMOPC算法需要設置的參數過多,而這些參數會對結果起著至關重要決定,導致分配的結果隨機性過大,對最優解的尋找也產生一定的影響,而且該算法每次都在滿足其約束條件下搜索最小化簇個數尋求最優解,并不是以最低能耗來尋找最優解。而FFA算法也未將能耗考慮在內,僅是滿足虛擬機需求的資源分配。而文中所提RRMGSO方法結合螢火蟲優化算法,利用能耗模型構建目標函數作為數據中心簇上熒光素的更新條件,進而尋找出最優目標簇,然后將資源利用率低的簇關閉或置于節能狀態并將其上的包再分配到目標簇進而有效降低數據中心能源消耗。
實驗2 資源利用率計算
將不同規模下的包部署到簇中并達到平衡時,取5 min為一個時間單元,記錄每個規模下的10個時間單元物理機器的平均使用率和內存平均使用率。
為驗證文中所提算法能夠提高數據中心資源利用率,將文中所提算法與IMOPC算法和FFA算法的資源平均利用率和內存資源平均利用率進行比較。實驗結果如圖3、圖4所示。

圖3 CPU平均利用率比較

圖4 內存平均利用率比較
通過分析對比實驗數據可知,通過RRMGSO算法提高數據中心CPU資源利用率和內存資源利用率是可行的。在CPU資源利用率上分別優于IMOPC算法和FFA算法近5%和8%。在內存資源利用率上分別優于IMOPC算法和FFA算法近3%和7%。這主要是因為RRMGSO算法的出發點就是針對資源利用率低的情況進行的資源再分配,而且螢火蟲的種群活動能很好地模擬包分配的尋優過程,使得資源再分配方案能夠取得較優的結果。
綜上所述,文中所提算法具有一定的可行性。在降低能耗和提高數據中心資源利用率上均有不錯表現。
針對云計算數據中心能耗高、資源利用率等問題,文中提出一種基于螢火蟲優化算法的資源再分配算法。考慮到傳統資源管理方式低擴展性、低靈活性等問題,文中算法采用包簇映射框架以分層的思想降解問題的規模,并利用螢火蟲優化算法將數據中心資源利用率低于預設閾值的簇上的包以最低的動態漂移能耗進行漂移,并關閉該簇。最后通過仿真實驗驗證文中算法的可行性。實驗結果表明該算法具有一定可行性。在降低能耗和提高數據中心資源利用率方面均有不錯表現。
[1] K. Zhang, T. Wu, S. Chen, L. Cai and C. Peng, "A New Energy Efficient VM Scheduling Algorithm for Cloud Computing Based on Dynamic Programming," 2017 IEEE 4th International Conference on Cyber Security and Cloud Computing (CSCloud), New York, NY, 2017, pp. 249-254.
[2] S. K. Sonkar and M. U. Kharat, "A review on resource allocation and VM scheduling techniques and a model for efficient resource management in cloud computing environment," 2016 International Conference on ICT in Business Industry & Government (ICTBIG), Indore, 2016, pp. 1-7.
[3] 葉可江, 吳朝暉, 姜曉紅, 何欽銘. 虛擬化云計算平臺的能耗管理[J]. 計算機學報, 2012, 35(06): 1262-1285.
[4] H. Zhu, X. Wang and H. Wang, "A New Model for Energy Consumption Optimization under Cloud Computing and its Genetic Algorithm," 2014 Tenth International Conference on Computational Intelligence and Security, Kunming, 2014, pp. 7-11.
[5] R. Watanabe, D. Duolikun, T. Enokidoy and M. Takizawa, "Energy-Aware Virtual Machine Migration Models in a Scalable Cluster of Servers," 2017 IEEE 31st International Conference on Advanced Information Networking and Applications (AINA), Taipei, 2017, pp. 85-92.
[6] S. M. AlIsmail and H. A. Kurdi, "Green algorithm to reduce the energy consumption in cloud computing data centres," 2016 SAI Computing Conference (SAI), London, 2016, pp. 557-561.
[7] 周婉, 王移芝. 基于卡爾曼預測器的云計算資源調度研究[J]. 軟件, 2015(9):12-15.
[8] D. A. Alboaneen, H. Tianfield and Y. Zhang, "Glowworm Swarm Optimisation Algorithm for Virtual Machine Placement in Cloud Computing," 2016 Intl IEEE Conferences on Ubiquitous Intelligence & Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People, and Smart World Congress (UIC/ATC/ScalCom/CBDCom/IoP/ SmartWorld), Toulouse, 2016, pp. 808-814.
[9] 趙辰吟, 姚文斌. 基于一種改進免疫算法的云計算任務調度策略研究[J]. 軟件, 2015, 36(12):149-153.
[10] 曹盟盟, 姚文斌. 基于改進粒子群算法的虛擬機放置算法[J]. 軟件, 2015, 36(12):89-92.
[11] 盧浩洋,陳世平. 基于包簇映射的云計算資源分配框架[J]. 計算機應用,2016,36(10):2704-2709.
[12] Kansal A, Zhao F, Liu J, et al. Virtual machine power metering and provisioning[C]// Acm Symposium on Cloud Computing. ACM, 2010:39-50.
[13] K. Rybina and A. Schill, "Estimating energy consumption during live migration of virtual machines," 2016 IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom), Varna, 2016, pp. 1-5.
[14] Buyya R, Beloglazov A, Abawajy J. Energy-Efficient management of data center resources for cloud computing: A vision, architectural elements, and open challenges. arXiv preprint arXiv:1006.0308. 2010.
[15] Beloglazov A, Buyya R. Energy efficient resource management in virtualized cloud data centers. In: Proc. of the 2010 10th IEEE/ACM Int’l Conf. 831. on Cluster, Cloud and Grid Computing. IEEE Computer Society, 2010. 826 [doi: 10.1109/CCGRID. 2010.46]
[16] Buyya R, Ranjan R, Calheiros R N. Modeling and simulation of scalable Cloud computing environments and the CloudSim toolkit: Challenges and opportunities[C]// International Conference on High PERFORMANCE Computing & Simulation. IEEE, 2009:1-11.
[17] 羅亮, 吳文峻, 張飛. 面向云計算數據中心的能耗建模方法[J]. 軟件學報, 2014(7):1371-1387.
[18] Y. Julien and J. A. Sobrino, "CloudSim: A fair benchmark for comparison of methods for times series reconstruction from cloud and atmospheric contamination," 2015 8th International Workshop on the Analysis of Multitemporal Remote Sensing Images (Multi-Temp), Annecy, 2015, pp. 1-4.
Resource Redistribution Algorithm Based on Glowworm Swarm Optimization
LIANG Ci1, CHEN Shi-ping1,2
(1. School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China; 2. Network and Information Center Office, University of Shanghai for Science and Technology, Shanghai 200093, China)
To solve the problem of high energy consumption and low resource utilization on data center, a resource redistribution scheme based on the glowworm swarm optimization algorithm under the package-cluster framework is proposed. The scheme adopts first fit algorithm in initial allocation of virtual machine. And then uses hierarchical idea of package-cluster mapping framework to degrade problem scale and combines with the glowworm swarm optimization algorithm to drift the packages of the clusters with the lowest dynamic drift energy consumption when the resource utilization is lower than the preset threshold in the clusters. At the same time, closes down these clusters to reduce energy consumption and improve resource utilization. The constructed resource redistribution scheme is simulated in the cloudsim platform. The results show that this scheme has good performance in reducing energy consumption and improving resource utilization.
Data center; Package-cluster; Glowworm swarm optimization; Packet drift; Resource redistribution
TP391
A
10.3969/j.issn.1003-6970.2018.09.008
國家自然科學基金資助項目(61472256、61170277);上海市一流學科建設項目(S1201YLXK);上海理工大學科技發展基金(16KJFZ035、2017KJFZ033);滬江基金(A14006)
梁慈(1993-),女,碩士,主要研究方向:計算機網絡、云計算;陳世平(1964-),男,博士,教授,博士生導師,主要研究方向:計算機網絡、云計算、分布式計算。
本文著錄格式:梁慈,陳世平. 基于螢火蟲優化算法的資源再分配方法研究[J]. 軟件,2018,39(9):35-41