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

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

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

1 研究現(xiàn)狀

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

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

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

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

圖1 染色體生成圖

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

圖2 染色體示意圖

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

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

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

圖3 遺傳算法流程圖

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

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

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

相反，解碼的過(guò)程就將(i+1)×m+(j+1)×n維向量的前(i+1)×m對(duì)應(yīng)的每i+1個(gè)二進(jìn)制數(shù)表示成十進(jìn)制數(shù)，后(j+1)×n對(duì)應(yīng)的每j+1個(gè)二進(jìn)制數(shù)表示成十進(jìn)制數(shù)。最終將染色體轉(zhuǎn)化為一個(gè)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}。

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

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

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

0號(hào)虛擬機(jī)VM0:{T2，T7}

1號(hào)虛擬機(jī)VM1:{T4，T5}

2號(hào)虛擬機(jī)VM2:{T1，T3}

3號(hào)虛擬機(jī)VM3:{T0，T6}

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

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

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

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

3．1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

CSP0:{VM0:T0，T4}

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

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

4 結(jié)論

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

圖4 遺傳算法進(jìn)化過(guò)程

圖5 執(zhí)行費(fèi)用對(duì)比圖

［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］ 林國(guó)龍，黃莉，丁一，等．基于云計(jì)算的云采購(gòu)成本結(jié)構(gòu)優(yōu)勢(shì)研究［J］．武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2013，35(6):912 －916．