基于蟻群算法的云計算聯(lián)盟資源調(diào)度

陳冬林，姚夢迪，桂雁軍，陳 玲

(1．武漢理工大學(xué)經(jīng)濟學(xué)院，湖北 武漢 430070;2．福建新奇特車業(yè)服務(wù)有限公司，福建 福州 350002)

云計算聯(lián)盟主要是指通過整合不同的云服務(wù)提供商來為用戶提供服務(wù)，因而提供給用戶的是統(tǒng)一的資源［1］。不同的云服務(wù)供應(yīng)商組成云計算聯(lián)盟，實現(xiàn)各個云平臺之間的資源共享和合作，同時使資源的發(fā)布、尋找，以及部署等資源管理工作更加高效地執(zhí)行。因此通過優(yōu)化資源配置的資源管理模式使各供應(yīng)商的代價最小成為了云計算聯(lián)盟體系結(jié)構(gòu)設(shè)計的目標。

現(xiàn)有關(guān)于云計算聯(lián)盟的研究主要包括兩個方面:①云計算聯(lián)盟體系結(jié)構(gòu)的研究，提出了云計算聯(lián)盟體系需要滿足分布式結(jié)構(gòu)、松散耦合、高可擴展性、資源快速發(fā)現(xiàn)、跨云平臺實現(xiàn)的需求，以解決云計算中的技術(shù)問題;②單云環(huán)境下資源調(diào)度策略的研究，主要針對在商業(yè)化的云計算服務(wù)提供商中，如 Amazon［2］，IBM［3］等的調(diào)度策略各不相同，且其商業(yè)模式已較為成熟的情況，而在理論研究方面，單一云供應(yīng)商環(huán)境在不同的調(diào)度約束條件(時間、費用、QoS、負載均衡、能耗及多目標等)下運用了不同的調(diào)度算法(傳統(tǒng)算法和啟發(fā)式智能算法)。目前，對云計算聯(lián)盟環(huán)境下資源調(diào)度研究較少，尚未有較為成熟的理論體系。

BRUNEO等［4］研究了在多個云服務(wù)提供商情況下的基于云代理的資源調(diào)度模型，代理為多個云之間提供最優(yōu)的調(diào)度機制及提供統(tǒng)一的管理接口，調(diào)度評價指標包括了價格、性能、硬件指標，以及負載均衡。YANG提出了一種面向商業(yè)的“聯(lián)合云計算模型”，該模型的主要特性是其“商業(yè)層”可以最大化用戶滿意度、提供商利益以及資源利用率［5］。DANILO等提出了一種既能滿足云協(xié)調(diào)器又能擴展設(shè)計的多云環(huán)境下的架構(gòu)體系［6－9］。MICHAEL 認為單云環(huán)境下數(shù)據(jù)中心的負載率達到60%～80%時即認為達到負載均衡，此時數(shù)據(jù)中心資源的利用率最高，低于該閥值時資源利用率降低，而高于該閥值時無法為用戶提供可靠的服務(wù)［10］。

出于更實際的商業(yè)意義，筆者以云聯(lián)盟環(huán)境下資源調(diào)度作為業(yè)務(wù)背景，在云供應(yīng)商資源負載均衡的前提下，研究實現(xiàn)云供應(yīng)商利益最大化的資源調(diào)度算法問題。

1 云計算聯(lián)盟調(diào)度問題建模

基于云計算聯(lián)盟協(xié)調(diào)器的資源調(diào)度架構(gòu)包括云用戶、云服務(wù)供應(yīng)商和云聯(lián)盟協(xié)調(diào)器3個部分。云服務(wù)供應(yīng)商由一系列提供存儲、基礎(chǔ)設(shè)施、平臺和軟件在內(nèi)的各種不同服務(wù)供應(yīng)商組成。不同的云服務(wù)供應(yīng)商提供的資源是異構(gòu)的，即資源參數(shù)、性能各不相同。云計算聯(lián)盟能夠幫助用戶從云供應(yīng)商中選擇適合自己的資源。

1．1 問題描述

筆者首先對于云計算聯(lián)盟環(huán)境下資源調(diào)度模型進行描述、分析和建模，然后從云供應(yīng)商角度選擇合適的資源調(diào)度算法，完成任務(wù)到虛擬機再到數(shù)據(jù)中心的調(diào)度，使得在資源負載均衡的條件下實現(xiàn)云供應(yīng)商利益最大化的目標。

1．2 數(shù)學(xué)模型構(gòu)建

云供應(yīng)商的資源包括數(shù)據(jù)中心、物理主機和虛擬機，這些資源需要通過具體指標對其進行定義及量化。數(shù)據(jù)中心指標如表1所示。主機指標如表2所示。虛擬機指標如表3所示。

表1 云計算數(shù)據(jù)中心指標

表2 主機指標

表3 虛擬機指標

2 供應(yīng)商利益最大化資源調(diào)度蟻群算法

在供應(yīng)商利益最大化的資源調(diào)度方法中，筆者考慮的是供應(yīng)商的總成本最低，包括執(zhí)行成本和傳輸成本。但由于一個任務(wù)選擇不同供應(yīng)商造成的執(zhí)行成本的差異與傳輸成本相比可忽略不計，因此筆者主要考慮從任務(wù)所在節(jié)點到云供應(yīng)數(shù)據(jù)中心的傳輸成本。此外，還考慮到數(shù)據(jù)中心的負載率，以保證整個數(shù)據(jù)中心的正常運行。因此本文綜合傳輸成本與數(shù)據(jù)中心的負載率兩個條件對資源進行調(diào)度與部署。

假設(shè)任務(wù)數(shù)量為m，虛擬機的數(shù)量為n，云供應(yīng)商數(shù)據(jù)中心數(shù)量為k，調(diào)度過程分為兩步，首先為任務(wù)尋找合適的虛擬機，主要考慮到用戶的預(yù)期時間;然后實現(xiàn)從任務(wù)到數(shù)據(jù)中心的調(diào)度，主要考慮任務(wù)到數(shù)據(jù)中心的傳輸成本與資源負載率。

(1)任務(wù)—虛擬機。用戶在提交任務(wù)時會給出預(yù)期完成時間，虛擬機執(zhí)行任務(wù)的時間如式(1)所示，任務(wù)到時間的部署是根據(jù)用戶的期望完成時間來選擇虛擬機模板。要求用戶的預(yù)期時間大于任務(wù)的理論完成時間，同時若有多個虛擬機模板滿足用戶的要求，選擇完成時間離用戶期望時間最近的虛擬機模板執(zhí)行任務(wù)，如式(1)所示。

(2)任務(wù)—數(shù)據(jù)中心?；诠?yīng)商利益最大化的蟻群算法建模矩陣ACO如式(2)所示，其中矩陣的行代表任務(wù)，矩陣的列代表數(shù)據(jù)中心。矩陣中的值aij為第i個任務(wù)選擇第j個數(shù)據(jù)中心，從ACO矩陣中的每一行選擇一個節(jié)點，最終生成一條最優(yōu)路徑。

步驟1 算法初始化。其包括參數(shù)的設(shè)置及初始化、距離矩陣的生成和螞蟻的生成。

步驟2 尋找初始節(jié)點。在蟻群算法中，初始節(jié)點的生成通常是隨機的，即螞蟻為第一個任務(wù)尋找合適資源的過程是隨機的。

步驟3 為下一個任務(wù)尋找節(jié)點。該過程包括:①計算螞蟻移動各待選節(jié)點的移動概率;②輪盤賭選擇下一個節(jié)點。

步驟4 計算路徑長度。傳統(tǒng)的蟻群算法是對該路徑上所有節(jié)點對應(yīng)的距離疊加得到總的距離長度。筆者考慮負載情況，通過增加負載系數(shù)對總長度進行修正，從而控制解的收斂方向。

負載率及修正系數(shù)計算。根據(jù)得到的路徑確定任務(wù)所選擇的數(shù)據(jù)中心，然后計算按照當前路徑部署后各數(shù)據(jù)中心的負載情況，負載率如式(3)所示。

部署完后的負載率等于當前負載率加上增加負載率。式(4)、式(5)分別表示本次調(diào)度完成后的內(nèi)存及存儲負載率。

負載率對求解過程的影響表現(xiàn)在通過修正系數(shù)改變總距離長度，從而影響信息素的增加。修正系數(shù)函數(shù)如式(6)所示，當部署完后數(shù)據(jù)中心的負載率還低于其低閾值Loadmin，此時修正系數(shù)為1，負載率不影響任務(wù)的調(diào)度情況;而當部署完以后數(shù)據(jù)中心負載率高于閾值Loadmax時，修正系數(shù)值為∞;當負載率介于兩個閾值之間時，負載率越高修正系數(shù)越大。

路徑長度計算。在計算路徑時引入修正系數(shù)，通過引入修正系數(shù)改善該條路徑所產(chǎn)生的信息素。

步驟5 保存最優(yōu)值。初始時刻將生成的第一個解存入最佳值中，當新生成的路徑更短時，替換掉原有最優(yōu)值，直至找到全局最優(yōu)解。

步驟6 更新信息素矩陣。在t+n時刻信息素節(jié)點ij上的信息素等于t時刻該節(jié)點殘留的信息素，加上在n時間內(nèi)經(jīng)過該節(jié)點的所有螞蟻在經(jīng)過該節(jié)點時的路徑的倒數(shù)和，如式(8)所示。

3 算例與結(jié)果分析

3．1 實驗數(shù)據(jù)

仿真數(shù)據(jù)主要包括任務(wù)、虛擬機和數(shù)據(jù)中心3個部分，如表4～表6所示。

3．2 核心代碼分析

筆者在CloudSim軟件中實現(xiàn)了基于蟻群算法的云計算聯(lián)盟環(huán)境下供應(yīng)商成本最優(yōu)的調(diào)度。除了CloudSim軟件包外，自定義了Ant、ACO及ACOcloudsim文件。

表4 任務(wù)數(shù)據(jù)

表5 虛擬機模板數(shù)據(jù)

表6 數(shù)據(jù)中心數(shù)據(jù)

Ant類中定義了3個方法，init(double［］［］pheromone1)方法用來初始化螞蟻;selectNextNode(double［］［］distance1)方法用來為螞蟻尋找下一個節(jié)點，即為下一個任務(wù)尋找合適的虛擬機;calculateTourLength()方法用來計算路徑長度，就是所有任務(wù)部署完以后傳輸費用總和。

ACO類中定義了taskTovm()方法為用戶尋找適合的虛擬機;initAnt()方法生成定義的螞蟻數(shù)量;initACO()方法為蟻群算法ACO的初始化過程;updatePheromone()方法進行信息素矩陣的更新;printOptimal()方法打印得到的最優(yōu)路徑和最優(yōu)距離;solve()方法通過最大運行代數(shù)MAX_GEN、螞蟻數(shù)量 antNum，以及任務(wù)數(shù)量taskNumber 3個變量控制循環(huán)次數(shù)，在循環(huán)內(nèi)調(diào)用 selectNextNode(double［］［］distance1)、updatePheromone()、initAnt()方法，并最終調(diào)用打印方法printOptimal()輸出最優(yōu)值。

3．3 運行結(jié)果分析

執(zhí)行代碼后，得到運行結(jié)果如下:經(jīng)過計算，任務(wù)尋找適合的虛擬機可得到{1 2 0 1 0 1 2 0 1 2};通過蟻群算法為任務(wù)尋找云供應(yīng)商數(shù)據(jù)中心可得到{1 3 2 0 1 2 4 0 2 5}，解析后可得到具體的部署方案。

DC0:{T3→VM1，T7→VM0}

DC1:{T0→VM1，T4→VM0}

DC2:{T2→VM0，T5→VM1，T8→VM1}

DC3:{T1→VM2}

DC4:{T6→VM2}

DC5:{T9→VM2}

此時，供應(yīng)商傳輸任務(wù)的總成本為214．07元，而按照隨機算法任意選取的任務(wù)尋找到的數(shù)據(jù)中心得到﹛0 1 2 3 4 5 0 1 2 3﹜，所需要的傳輸任務(wù)的總成本為217．31元，表明在部署后實現(xiàn)了供應(yīng)商利益最大化，此時任務(wù)及數(shù)據(jù)中心部署完成后各數(shù)據(jù)中心負載率與部署前的對比如圖1所示。通過圖1可知，在未進行資源調(diào)度部署前，數(shù)據(jù)中心的負載一般為40% ～60%，造成了數(shù)據(jù)中心資源的空閑，在進行部署后負載率均在60%～80%之間，根據(jù)伯克利實驗室對于負載率的研究，當負載率達到60% ～80%之間時，實現(xiàn)了云計算聯(lián)盟中所有數(shù)據(jù)中心的負載均衡，提高了數(shù)據(jù)中心資源調(diào)度的效率。

圖1 數(shù)據(jù)中心負載率對比圖

4 結(jié)論

筆者在國內(nèi)外研究現(xiàn)狀的基礎(chǔ)上，提出了云聯(lián)盟環(huán)境下的資源調(diào)度模型，對云計算聯(lián)盟環(huán)境下的云供應(yīng)商進行建模，然后從供應(yīng)商利益最大化，即成本最低的角度開展研究工作，探索云計算聯(lián)盟環(huán)境下的資源調(diào)度策略，使得云供應(yīng)商在滿足用戶需求的前提下實現(xiàn)利益最大化。

［1］ HASSAN M M，HUH E N．Overview of cloud computing and motivation of the work［M］．New York:Springer，2013:1 －12．

［2］ MARSTON S，LI Z ，BANDYOPADHYAY S，et al．Cloud computing — the business perspective［J］．Decision Support Systems，2011，51(1):176 －189．

［3］ KESSACI Y，MELAB N，TALBI E G．A paretobased metaheuristic for scheduling HPC applications on a geographically distributed cloud federation［J］．Cluster Computing，2012(1):1－18．

［4］ BRUNEO D，LONGO F，PULIAFITO A．Modeling energy－aware cloud federations with SRNs［M］．Heidelberg:Springer，2012:277 －307．

［5］ YANG X Y，NASSER B，SURRISGE M，et al．A business－oriented cloud federation model for realtime online interactive applications［J］．Future Generation Computer Systems，2012，28(8):1158 －1167．

［6］ DANILO A，SARA C，MICHELE C．Dual timescale distributed capacity allocation and load redirect algorithms for cloud systems［J］．Journal of Parallel and Distributed Computing，2012，72(6):796 －808．

［7］ VICTOR T，ANNA T，ALEXANDER B．Resource selection algorithms for economic scheduling in distributed systems［J］．Procedia Computer Science，2011，30(4):2267－2276．

［8］ SAURABH K G，CHEE S Y，ARUN A，et al．Environment－conscious scheduling of HPC applications on distributed cloud － oriented data centers［J］．J Parallel Distrib Comput，2011，71(24):732 －749．

［9］ 華夏渝，鄭駿，胡文心．基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法［J］．華東師范大學(xué)學(xué)報:自然科學(xué)版，2010，2(1):127 －134．

［10］ MICHAEL A，ARMANDO F，REAN G．Above the clouds:a berkeley view of cloud computing［J］．UC Berkeley Reliable Adaptive Distributed System Laboratory，2009，30(10):5－6．