用戶利益最大化的云計算聯(lián)盟資源調(diào)度

陳 玲，陳冬林，桂雁軍，吳 鐘

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

云計算是繼水、電、氣和通信之后的第5效用［1］，學(xué)術(shù)界和世界IT巨頭紛紛研究云計算技術(shù)，對其商業(yè)應(yīng)用進行開發(fā)，出現(xiàn)了Amazon彈性云EC2和存儲云S3、Google App存儲云、微軟Azure的PaaS等公共云［2］。隨著云計算的不斷發(fā)展，企業(yè)和用戶對于云計算的發(fā)展也更加關(guān)注，使用云供應(yīng)商服務(wù)的企業(yè)和個人用戶也越來越多。單一云供應(yīng)商資源有限，當(dāng)用戶數(shù)量不斷增加時，單一云供應(yīng)商無法滿足所有用戶的請求也無法保證提供給用戶資源的服務(wù)質(zhì)量，再加上提供云服務(wù)的供應(yīng)商數(shù)量不斷增加，促使各個云供應(yīng)商之間合作以及云計算聯(lián)盟形成［3］。

1 研究現(xiàn)狀

現(xiàn)有的對云計算聯(lián)盟環(huán)境下資源調(diào)度研究較少，尚未有較為成熟的理論體系。TORDSSONA研究了在多個云服務(wù)提供商情況下的基于云代理的資源調(diào)度模型，該模型中包含了用戶、代理和供應(yīng)商3種角色，代理的任務(wù)為多個云之間提供最優(yōu)的調(diào)度機制并提供統(tǒng)一的管理接口，調(diào)度評價指標(biāo)包括了價格、性能、硬件指標(biāo)，以及負(fù)載均衡［4］。YANG提出了一種面向商業(yè)的“聯(lián)合云計算模型”，在該模型中多個獨立的基礎(chǔ)設(shè)施提供商能夠?qū)崿F(xiàn)無縫地合作以提供可擴展的IT設(shè)施和QoS保證的多用戶實時在線交互應(yīng)用(realtime online interactive applications，ROIA)，該模型的主要特性是其“商業(yè)層”在確保安全性的同時觸發(fā)多供應(yīng)商的按需資源分配，因而可以最大化用戶滿意度、提供商利益以及資源利用率［5］。CALHEIROS［6］認(rèn)為，單一的數(shù)據(jù)中心使得資源的可用性受到限制，提出了一種既能滿足云協(xié)調(diào)器又能擴展設(shè)計的多云環(huán)境下的架構(gòu)體系。LARSSON定義了一種云計算聯(lián)盟下的調(diào)度模型，通過啟發(fā)式算法為虛擬機遷移找到最佳候選人。同時，為了協(xié)助調(diào)度器并提供統(tǒng)一的數(shù)據(jù)，提出了一種分布式數(shù)據(jù)監(jiān)測模型［7］。文獻［8］認(rèn)為云計算聯(lián)盟是使云計算得到廣泛應(yīng)用并使其實現(xiàn)價值的唯一方法［9］，提出了基于P2P的云計算聯(lián)盟架構(gòu)，給出了其市場結(jié)構(gòu)。

筆者提出基于用戶利益最大化的云計算聯(lián)盟資源調(diào)度方法，并通過遺傳算法實現(xiàn)資源調(diào)度策略。同時基于CloudSim實現(xiàn)了云計算聯(lián)盟資源調(diào)度方法，對云計算聯(lián)盟環(huán)境下的資源調(diào)度研究從學(xué)術(shù)走向?qū)嶋H應(yīng)用具有一定的意義。

2 用戶利益最大化的資源調(diào)度遺傳算法

筆者采用任務(wù)－虛擬機、虛擬機－數(shù)據(jù)中心的間接編碼方式，對虛擬機部署到云供應(yīng)商進行編碼。染色體的長度為任務(wù)加虛擬機的數(shù)量，染色體中前半部分每個基因的取值為該位置對應(yīng)的虛擬機編號，后半部分基因的取值為該位置對應(yīng)的云供應(yīng)商編號，如圖1所示。

圖1 染色體生成圖

在整個調(diào)度過程中有m個任務(wù)，n個虛擬機，k個云供應(yīng)商，則染色體的長度為m+n，即由m+n個基因組成染色體串。第1到第m個基因依次表示第0到第m－1個任務(wù)，基因上的值表示任務(wù)所被部署到的虛擬機的編號。第m+1到第m+n個基因表示第0到第n－1個虛擬機，基因上的值表示虛擬機所被部署到的云供應(yīng)商的編號。在產(chǎn)生初始種群時，每一個染色體中的基因編號VMi和CSPj都是隨機產(chǎn)生的，經(jīng)過交叉、變異算子后，任務(wù)可能被部署到任何虛擬機上，而虛擬機也可能被部署到可用的數(shù)據(jù)中心上，因此最優(yōu)解一定對應(yīng)某一個染色體編碼。假設(shè)有8個任務(wù)，4個虛擬機，2個云供應(yīng)商，則染色體長度為12，前8個基因取值為0～3之間的隨機數(shù)，而后4個基因取值為0～1之間的整數(shù)。如隨機產(chǎn)生如下的染色體:{3，2，0，2，1，1，3，0，0，1，0，1}，其示意圖如圖2所示。

圖2 染色體示意圖

由圖2可知，任務(wù)T2和T7被部署到虛擬機VM0上，任務(wù)T4和T5被部署到虛擬機VM1上，任務(wù)T1和T3被部署到虛擬機VM2上，任務(wù)T0和T6被部署到虛擬機VM3上;而VM0和VM2被部署到數(shù)據(jù)中心CSP0上，VM1和VM3被部署到數(shù)據(jù)中心CSP1上。

筆者使用遺傳算法來實現(xiàn)用戶利益最大化的資源調(diào)度求解，算法流程圖如圖3所示。

(1)參數(shù)定義。首先定義算法執(zhí)行過程中所需要的參數(shù)，如種群大小，編碼前/后基因長度，最大遺傳代數(shù)，當(dāng)前遺傳代數(shù)，編碼前/后種群，適應(yīng)度值，交叉率，變異率，最佳染色體，最佳適應(yīng)度值，最低費用。

圖3 遺傳算法流程圖

(2)初始種群的生成。取種群規(guī)模為S，染色體長度即維度為m+n，任務(wù)數(shù)為m，虛擬機數(shù)為n，云供應(yīng)商數(shù)為k，則初始化過程即由系統(tǒng)隨機產(chǎn)生S條染色體，其中前m個基因值為［0，n－1］之間的任一整數(shù)，后n個基因值為［0，k－1］之間的任一整數(shù)，在初始化時系統(tǒng)直接生成的是二進制種群，因而在其后只需要進行解碼操作。

(3)染色體解碼。筆者采用的是二進制編碼，即將可行解空間轉(zhuǎn)化為用0，1表示的二進制字符串。任務(wù)數(shù)為m，虛擬機數(shù)為n，云供應(yīng)商數(shù)為k，即染色體的前m個基因的取值介于0～n－1之間，后n位的基因取值介于0～k－1之間。在編碼時，若i，j滿足，則將染色體中前m個基因中的每個分向量用一個i+1位的二進制數(shù)表示，后n個基因中的每個分向量用一個j+1位的二進制數(shù)表示。編碼過后的染色體長度由編碼前的m+n變成(i+1)×m+(j+1)×n位。

例如，對染色體{3，2，0，2，1，1，3，0，0，1，0，1}進行編碼，前8個基因每個基因用一個2位的二進制數(shù)表示，后4個基因每個基因用一個1位的二進制數(shù)表示。編碼后的染色體將變成{11 10 00 10 01 01 11 00 00 01 00 01}。

相反，解碼的過程就將(i+1)×m+(j+1)×n維向量的前(i+1)×m對應(yīng)的每i+1個二進制數(shù)表示成十進制數(shù)，后(j+1)×n對應(yīng)的每j+1個二進制數(shù)表示成十進制數(shù)。最終將染色體轉(zhuǎn)化為一個m+n維向量。例如將上述的編碼后染色體{11 10 00 10 01 01 11 00 00 01 00 01}解碼后將得到{3，2，0，2，1，1，3，0，0，1，0，1}。

解碼過程是為了得到資源的利用情況，通過解碼可獲得云供應(yīng)商資源上虛擬機的部署情況和虛擬機上任務(wù)的部署情況，將上述染色體解碼為:

0號云供應(yīng)商CSP0:{VM0，VM2}

1號云供應(yīng)商CSP1:{VM1，VM3}

0號虛擬機VM0:{T2，T7}

1號虛擬機VM1:{T4，T5}

2號虛擬機VM2:{T1，T3}

3號虛擬機VM3:{T0，T6}

(4)適應(yīng)度值計算。遺傳算法適應(yīng)度函數(shù)的選取直接影響到遺傳算法的收斂速度與最優(yōu)解的查找，通過適應(yīng)度函數(shù)計算出每個個體的適應(yīng)度值，值較大的個體遺傳到下一代的概率較大，而值較小的個體遺傳到下一代的概率就小一些，因此適應(yīng)度函數(shù)的選取十分關(guān)鍵。筆者算法的調(diào)度目標(biāo)是使用戶總的費用達到最小，因此其適應(yīng)度函數(shù)為總費用函數(shù)，總費用越低，得到的適應(yīng)值越高。定義執(zhí)行費用的適應(yīng)度函數(shù)如式(1)和式(2)所示。

式中:i為第i個任務(wù);n為任務(wù)數(shù)量;i→j為從任務(wù)到虛擬機的映射;i→j→k為從任務(wù)到虛擬機到云供應(yīng)商的兩層映射;lengthi為任務(wù)i的長度;mipsi→j為i所選擇的虛擬機的MIPS的大小;costPerSecondi→j→k為任務(wù)最重時所部署的虛擬機的PE價格，其他同理類推。

(5)遺傳操作。遺傳操作過程包括選擇、交叉、變異3個步驟。筆者定義的交叉率為50%，即全部的染色體中有50%的染色體參與交叉過程;變異率為3%，即發(fā)生變異的染色體基因數(shù)占總的染色體數(shù)的3%。

3 用戶利益最大化資源調(diào)度策略實現(xiàn)

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

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

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

3．2 調(diào)度算法

筆者在CloudSim包下實現(xiàn)了基于遺傳算法的云計算聯(lián)盟環(huán)境下用戶利益最大化的調(diào)度實現(xiàn)。除了CloudSim包外，自定義了GA及GACloudsim文件。

在GA類中定義了初始化inialPops、解碼decodePopulation、計算適應(yīng)度值 calculatefitness、選擇 select、交叉cross、變異mutation、遺傳操作process等方法。

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

(1)遺傳算法中定義的變量主要包括染色體長度、遺傳代數(shù)、種群大小、種群、交叉率和變異率等。

(2)初始化后數(shù)據(jù)中任務(wù)數(shù)量為10，虛擬機數(shù)量為6，因而染色體長度為16，在編碼過程中前10個基因每個基因上的值編碼為3位的二進制數(shù);后6位基因上基因值編碼為2位的二進制數(shù)。因為編碼后的二進制基因長度為42。為了方便生成，在實現(xiàn)過程中首先將初始生成的若干條編碼后的0－1字符染色體，在計算適應(yīng)度值時再將字符染色體轉(zhuǎn)換為二進制數(shù)染色體。

(3)解碼部分是將生成的0－1字符串種群解碼為十進制種群以計算種群適應(yīng)值。解碼過程首先將字符串編碼種群轉(zhuǎn)化為二進制數(shù)種群，然后再解碼為十進制種群，該過程分為兩個步驟，首先對任務(wù)部分染色體基因三位二進制數(shù)解碼為一位十進制數(shù);而虛擬機部分基因則兩位二進制數(shù)解碼為一位十進制數(shù)，最終生成十進制染色體種群。

(4)計算適應(yīng)度值是在種群生成后根據(jù)適應(yīng)度函數(shù)對種群中的每條染色體進行適應(yīng)度值的計算，適應(yīng)度值越高，該染色體在其后的遺傳操作中被保存下來的概率越高。在計算費用過程中涉及價格的搜尋過程，如最終得到的最佳染色體為數(shù)組bestChrom［］，那么對任務(wù)i，其部署的虛擬機為bestChrom［i］，而該虛擬機部署到的數(shù)據(jù)中心為bestChrom［bestChrom［i］+10］。通過這樣一個搜尋過程可得到計算過程中需要的各種參數(shù)值。

(5)在整個遺傳算法執(zhí)行過程中，除了初始化在最開始執(zhí)行一次外，在解碼、計算適應(yīng)度值、選擇、交叉、變異等過程中要根據(jù)遺傳代數(shù)循環(huán)執(zhí)行。

在DatacenterBroker類中自定義了bindCloudletToVms方法用來實現(xiàn)從任務(wù)到虛擬機的調(diào)度，在該方法中需要調(diào)用到GA中最終生成的最佳染色體bestChrom［］結(jié)果。

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

經(jīng)過迭代計算，找到了一個可行最優(yōu)解{0 2 2 2 0 3 2 3 3 5 0 2 1 2 1 2}，圖4顯示了在遺傳算法計算過程中得到總執(zhí)行費用的值，從圖4中可以看到，隨著運行代數(shù)的增加，費用逐漸收斂，越來越接近最優(yōu)解，最終最優(yōu)解為20 592．53。通過圖5對比可知，云計算聯(lián)盟能夠幫助用戶大大降低總執(zhí)行費用。解析后可得到具體的部署方案為:

CSP0:{VM0:T0，T4}

CSP1:{VM2:T1，T2，T3，T6}

CSP2:{VM3:T5，T7，T8}，{VM5:T9}

4 結(jié)論

筆者從用戶的角度探討通過云計算聯(lián)盟對用戶任務(wù)進行調(diào)度。云計算聯(lián)盟資源池中聚集了多個云供應(yīng)商的價格、質(zhì)量等各不相同的資源，用戶可以選擇更適合自己的資源，同時用戶也可以將多個任務(wù)部署在多個不同的云供應(yīng)商的資源上，從而降低用戶在使用云計算時的成本，而這一點是目前單一環(huán)境下云計算供應(yīng)商所不能實現(xiàn)的。

圖4 遺傳算法進化過程

圖5 執(zhí)行費用對比圖

［1］ BUYYA R，CHEE S Y．Cloud computing and emerging IT platforms:vision，hype and reality for relivering computing as the 5th utility［J］．Future Generation Computer Systems，2009，25(3):599 －616．

［2］ ZHANG Q，CHENG L．Cloud computing:state－ ofthe － art and research challenges［J］．Journal Internet Servvices and Application，2010(1):7－18．

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

［4］ TORDSSONA J，MONTERO R S，RAFAEL M V，et al．Cloud brokering mechanisms for optimized placement of virtual machines acrossmultiple providers［J］．Future Generation Computer Systems，2012，28(2):358 －367．

［5］ YANG X Y，NASSER B，SURRIDGE 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］ CALHEIROS R N，RANJAN R，BELOGLAZOV A．Cloudsim:a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［R］．［S．l．］:［s．n．］，2009．

［7］ LARSSON L，HENRIKSSON D，ELMROTH E．Scheduling and monitoring of internally structured services in cloud federations［C］∥2011 IEEE Symposium on Computers and Communications(ISCC)，IEEE．［S．l．］:［s．n．］，2011:173 －178．

［8］ FANIYI F，BAHSOON R，THEODOROPOULOS G．A dynamic data－driven simulation approach for preventing service level agreement violations in cloud federation［J］．Procedia Computer Science，2012(9):1167－1176．

［9］ 林國龍，黃莉，丁一，等．基于云計算的云采購成本結(jié)構(gòu)優(yōu)勢研究［J］．武漢理工大學(xué)學(xué)報:信息與管理工程版，2013，35(6):912 －916．