云環(huán)境下基于改進(jìn)遺傳算法的虛擬機(jī)調(diào)度策略

1、云環(huán)境下基于改進(jìn)遺傳算法的虛擬機(jī)調(diào)度策暁摘要：針對(duì)云環(huán)境下服務(wù)器內(nèi)部多種資源間分配不均衡問題，提出了一種多 維資源協(xié)同聚合的虛擬機(jī)調(diào)度算法mcca。該算法在分組遺傳算法的基礎(chǔ) 上，采用模糊邏輯及基于資源利用率多維方差的控制參量，設(shè)計(jì)適應(yīng)度函 數(shù)指導(dǎo)搜索解空間。算法使用基于輪盤賭法的選擇方法，并對(duì)交叉和變異 等進(jìn)行了優(yōu)化，以實(shí)現(xiàn)快速有效地獲取近似最優(yōu)解。在cloudsim環(huán)境下 進(jìn)行了仿真，實(shí)驗(yàn)結(jié)果表明該算法對(duì)均衡多維資源分配和提高資源綜合利 用率具有一定的優(yōu)勢(shì)。關(guān)鍵詞：云計(jì)算；虛擬機(jī)；多維均衡；分組遺傳算法屮圖分類號(hào)：tp301文獻(xiàn)標(biāo)志碼：avirtual machine deployment

2、 strategy based onimproved genetic algorithm in cloud computing environinentzabstract：aiming at improving the resource utilization of data center by bala need usage of mu it iple resources, a schedul ing al gor ithm based on group genetic algorithm for multi-dimensional resources coorclination was p

3、roposed to solve the virtual machine deploymentproblem. to guide the solution searching, a fuzzy logic based multi-dimensional fitness function was raised. meanwhile , innovative optimization of crossover and mutation was put forward to improve the solution quality the results of simulation in cloud

4、sim environment prove that using the proposed algorithm can obtain better multi-dimensional resources performance and higher resource utilization rate.key words：cloud computi ng； virtual machine； mul ti-dimensi on al balanci ng； group genetic algorithmo引言隨著信息技術(shù)和網(wǎng)絡(luò)應(yīng)用的快速發(fā)展，云計(jì)算作為一種全新的計(jì)算模 式，已越來越受到工業(yè)界和學(xué)術(shù)

5、界的關(guān)注，有代表性的云計(jì)算實(shí)例有 amazon的彈性云、ibm藍(lán)云、google的云計(jì)算等。各云計(jì)算服務(wù)提供商為 了提高綜合競(jìng)爭(zhēng)力，不斷通過資源的調(diào)度整合來提高資源的利用率。虛擬 機(jī)調(diào)度作為云計(jì)算資源配置中的關(guān)鍵技術(shù)通過以虛擬機(jī)為封裝單 元，將虛擬機(jī)映射到物理機(jī)器上來實(shí)現(xiàn)應(yīng)用的負(fù)載均衡。由于虛擬機(jī)對(duì)資 源的需求是多元且不同的，分別對(duì)應(yīng)著不同維度的資源類型，如cpu、內(nèi) 存、i/o和網(wǎng)絡(luò)帶寬等，為了獲得資源利用的最大化，可將該問題描述為 多維向量裝箱問題1。由于問題的np-hard性質(zhì)2,需耍找到一個(gè)近似 最優(yōu)解，以實(shí)現(xiàn)資源的高效均衡分配。很多學(xué)者針對(duì)裝箱問題及其變體展開了大量的研究。文獻(xiàn)3通過

6、隨機(jī)裝箱優(yōu)化來處理虛擬化數(shù)據(jù)中心節(jié)點(diǎn)的整合，但只考慮了 cpu的資源, 沒有處理多維資源的約束；文獻(xiàn)4采用多維資源間的最大最小公平原則 來提高云環(huán)境下系統(tǒng)資源的綜合利用率；文獻(xiàn)5以最小化服務(wù)器數(shù)量為 優(yōu)化目標(biāo)，涵蓋了多維資源間的約束條件，提出了一種面向多維資源配置 的通用數(shù)學(xué)模型。通過分析發(fā)現(xiàn)，現(xiàn)有的人多數(shù)研究耍么只考慮了單約束 條件下的問題，或是簡(jiǎn)單地將單維資源約束擴(kuò)充為多維資源約束，沒有體 現(xiàn)多維資源間的共存和依賴關(guān)系，因而不能通過多維資源的協(xié)同聚合來提 高資源的綜合利用率。本文在分組遺傳算法的基礎(chǔ)上，提出了一種多維資 源協(xié)同聚合的虛擬機(jī)調(diào)度算法mcca,通過引入基因評(píng)估參數(shù)來衡量服務(wù)器

7、資源的綜合利用率，設(shè)計(jì)“最大一最小”加權(quán)模糊邏輯真值傳遞策略的適 應(yīng)度函數(shù)來促進(jìn)算法快速有效地收斂。另外，為了獲得算法的近似最優(yōu)解, 在選擇和變異操作中進(jìn)行了優(yōu)化。最后通過云仿真計(jì)算器cloudsim6進(jìn) 行了仿真，仿真結(jié)果表明本文算法均衡了服務(wù)器資源的分配，減少了隱性 資源浪費(fèi)現(xiàn)象，提高了資源的綜合利用率。1調(diào)度算法模型假設(shè)有n個(gè)虛擬機(jī)調(diào)度請(qǐng)求，定義為n二vmillwiwn,另有m臺(tái)可 用的物理服務(wù)器，定義為帖psillwiwm。虛擬機(jī)需物理服務(wù)器上的多 維資源來實(shí)行運(yùn)算，定義虛擬機(jī)i對(duì)j類型資源的需求量為qi, j,則該 虛擬機(jī)對(duì)資源的請(qǐng)求向量為qi二qi, 1 qi, 2qi, k。同樣

8、，定義物 理服務(wù)器i能提供j類型的資源容量為ci, j,其能提供的資源容量向量 為ci二ci, lei, 2ci, k o用ui, j表示服務(wù)器i在資源類型j維 度的利用率，將虛擬機(jī)放置的目標(biāo)和約束定義如下：目標(biāo)函數(shù):目標(biāo)函數(shù)表示啟動(dòng)最少的物理服務(wù)器以獲得最大的多維資源利用率， 約束條件確保了服務(wù)器被分配的資源不超過其容量上限。由于ui, j表示服務(wù)器i在資源類型j維度的利用率，用i表示服 務(wù)器i上所有資源的平均利用率，如式(3)o同時(shí)，定義基因評(píng)估參數(shù)入 i,它山服務(wù)器資源的平均利用率及資源利用率的多維方差兩部分構(gòu)成， 用以確定染色體中各個(gè)基因是否具有較高的多維協(xié)同聚合關(guān)系，計(jì)算方法 如式(

9、4)。從基因評(píng)估參數(shù)的定義可以看出，更高的基因評(píng)估值意味著服務(wù)器具冇較小的維度間利用率偏差和更高的綜合資源利用率，這樣 就可以保證染色體的各個(gè)基因盡可能地具有多維協(xié)同的聚合效應(yīng)。2算法實(shí)現(xiàn)如上所述，本文在設(shè)計(jì)算法時(shí)重點(diǎn)考慮多維資源之間的均衡調(diào)度，以 實(shí)現(xiàn)最小化服務(wù)器使用數(shù)量和最大化多維資源綜合利用率的冃標(biāo)?；诜?務(wù)器聚合思想的虛擬機(jī)調(diào)度屬于組合優(yōu)化屮的裝箱問題，而傳統(tǒng)的二維和 三維裝箱問題作為一維裝箱問題的空間泛化，不適用于解決多維聚合的資 源調(diào)度問題7。同時(shí)，傳統(tǒng)的遺傳算法由于編碼等問題對(duì)于分組問題的 適應(yīng)性很差8。因此，本文提出了一種改進(jìn)的分組遺傳算法來求解虛擬 機(jī)的調(diào)度問題。該算法在分

10、組遺傳算法的基礎(chǔ)上，采用模糊邏輯及基于資 源利用率多維方差的控制參量，設(shè)計(jì)算法搜索函數(shù)指導(dǎo)搜索解空間。另外 算法采用了基于輪盤賭法的選擇優(yōu)化，并對(duì)交叉和變異等進(jìn)行了優(yōu)化，以 快速有效地獲取近似最優(yōu)解，其算法流程如圖1所示。2. 1基因編碼在分組遺傳算法中，染色體中的每個(gè)基因代表一個(gè)服務(wù)器，基因的值 是服務(wù)器上裝載的虛擬機(jī)集合，也即虛擬機(jī)的一個(gè)分組，如圖2所示，a、 b代表服務(wù)器，15代表虛擬機(jī)，染色體的編碼為：ab (a： 1, 4, b： 2, 3, 5)。這樣編碼的好處是染色體的基因位數(shù)由服務(wù)器的數(shù)量決左， 不會(huì)造成編碼的長(zhǎng)度過長(zhǎng)，從而影響計(jì)算的效率。另分組編碼在交叉和變 異等操作中不會(huì)破

11、壞服務(wù)器的硬約朿條件。2.2適應(yīng)度函數(shù)適應(yīng)度函數(shù)的選取對(duì)遺傳算法能否找到最優(yōu)解以及算法的收斂速度 起著重要作用。為了達(dá)到啟動(dòng)物理服務(wù)器最小化和實(shí)現(xiàn)資源綜合利用率最 人化的目標(biāo)，適應(yīng)度函數(shù)的設(shè)計(jì)應(yīng)綜合考慮啟用物理機(jī)器的數(shù)量和多維資 源的均衡程度。前面定義了單一基因位的評(píng)估參量入i,反映了單個(gè)服務(wù) 器的資源利用率和多維均衡度。對(duì)于由多個(gè)基因位組成的染色體個(gè)體，評(píng) 估染色體個(gè)體優(yōu)劣的重要因素就是物理機(jī)的需求數(shù)量和多維資源的均衡 度。為了便于描述多維資源的均衡度，將基因評(píng)估參量的90%置信區(qū)間值 定義為個(gè)體的宏觀均衡指標(biāo)。假設(shè)t(x)表示邏輯表達(dá)式x的二元真值， r(71)表示分配方案乳的矩陣秩，則方

12、案h的宏觀均衡指標(biāo)為：由于宏觀均衡指標(biāo)和物理機(jī)的需求數(shù)量這兩個(gè)評(píng)佔(zhàn)參量分別具有不 同的量綱和數(shù)量級(jí)，很難判斷它們対問題可行解的影響程度，因此采用 max-min原則的加權(quán)模糊邏輯理論來對(duì)雙因素評(píng)估進(jìn)行整合和量化描述 9。分別記bm為宏觀均衡指標(biāo)，nas為物理機(jī)的需求數(shù)量，它們的權(quán)重 為wl和w2,其成員變量隸屬度為t (bm)和t (nas),隸屬度的真值等于 各成員變量的隸屈函數(shù)值，則多維分組遺傳算法的適應(yīng)度函數(shù)為：t (y) =1-2.3選擇選擇操作一般是從每次迭代產(chǎn)生的個(gè)體中選擇適應(yīng)度值較高的個(gè)體 進(jìn)入下一代種群屮，但若僅挑選適應(yīng)度高的個(gè)體容易使解陷入局部最優(yōu)， 因此采用輪盤賭法來選擇個(gè)

13、體。首先根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)個(gè)體的適應(yīng) 度值和種群的適應(yīng)度總和，然后計(jì)算個(gè)體的適應(yīng)度值在總和中所占的比 例，以此作為該個(gè)體的選擇概率ps (ai),再計(jì)算第k個(gè)個(gè)休的累計(jì)選擇 概率p*s (ak) 隨后產(chǎn)生一個(gè)0至1之間的隨機(jī)數(shù)e,若p*s (ak-1) <e<p*s (ak),則選擇第k個(gè)個(gè)體。這種選擇算法隨機(jī)性較強(qiáng)，并能保證 適應(yīng)度值高的個(gè)體能有較高的概率進(jìn)入到下一代種群中。2.4交叉交叉算子在遺傳進(jìn)化過程中起到全局搜索的重要作用，如每次迭代中 選擇評(píng)估值最優(yōu)的基因進(jìn)行交叉，則容易使算法陷入局部最優(yōu)，出現(xiàn)早熟 收斂現(xiàn)象；如隨機(jī)選擇交叉位則會(huì)造成全局搜索效率的下降，因此引入可

14、調(diào)參數(shù)的概率函數(shù)在保證較高評(píng)估值基因優(yōu)勢(shì)的基礎(chǔ)上制造全局搜索隨 機(jī)性。首先將染色體中的基因按照評(píng)估參量值進(jìn)行排序，定義排在第6位 的基因被選擇為交叉位的概率為p ( 0 ),服從如式(7)所示的分布函數(shù), 根據(jù)經(jīng)驗(yàn)，e的取值為2。可以看出評(píng)估值較高的基因具有較大的概率被 選擇為交叉位，同時(shí)概率的隨機(jī)性保證了全局搜索的性能。p ( 0 )0- e ； e 0 (7)選擇交叉位進(jìn)行交叉操作z后，去掉含有相同虛擬機(jī)的服務(wù)器編碼， 同時(shí)采用首次適應(yīng)遞減法(first fit decreasing, fed) 10方式冋填因消除服務(wù)器而失去從屬關(guān)系的虛擬機(jī)。2.5變異變異算子賦予個(gè)體以很小的概率產(chǎn)生轉(zhuǎn)變

15、，使個(gè)體更加逼近最優(yōu)解。 變異算了使得遺傳算法具冇局部的隨機(jī)搜索能力，同時(shí)保持了種群的多樣 性，以防止出現(xiàn)非成熟收斂。為了保證局部的搜索能力，變異率不能過大, 如果變異率大于0. 5%,遺傳算法就退化成隨機(jī)搜索，因此設(shè)置變異概率函 數(shù)如下：式中：fmax為種群中最大的適應(yīng)度值，favg為每代群體的平均適應(yīng) 度值，f為要變異的個(gè)體適應(yīng)度值。當(dāng)適應(yīng)度函數(shù)值較大（ffavg）時(shí), 應(yīng)該讓pm較小，防止適應(yīng)度函數(shù)值較大的個(gè)體被破壞；當(dāng)適應(yīng)度函數(shù)值 較?。╢favg）時(shí)，應(yīng)該讓pm較大以開辟新的搜索區(qū)域。在本文中設(shè)定 kl二0.003, k2二0.0042。通過引入自適應(yīng)變異概率函數(shù)，根據(jù)種群適應(yīng)度 的

16、情況調(diào)整變異概率，不僅提高了最優(yōu)解的收斂速度，同時(shí)使得算法不易 陷入早熟情況。2. 6終止條件本文根據(jù)最優(yōu)跨度適應(yīng)度函數(shù)值的標(biāo)準(zhǔn)差來決定算法的終止，如式（9）所示：3仿真實(shí)驗(yàn)本文采用云計(jì)算仿真工具cloudsim進(jìn)行仿真，為了驗(yàn)證多維聚合算 法mcca的有效性，通過與該領(lǐng)域最新提出的多維資源調(diào)度算法drf4以 及常用服務(wù)器聚合算法ffd進(jìn)行比較。實(shí)驗(yàn)運(yùn)行的工作負(fù)載實(shí)例綜合 feitelsonll和mishra12等參數(shù)設(shè)置,同時(shí)將工作負(fù)載規(guī)模分為100、 300、500、800及1000個(gè)虛擬機(jī)五個(gè)實(shí)例，每個(gè)實(shí)例中的算法均運(yùn)行30次取平均值作為性能分析的依據(jù)。物理服務(wù)器的使用數(shù)量是衡量服務(wù)器聚

17、合算法性能的重要指標(biāo)omcca優(yōu)勢(shì)資源公平法(dominant resource fairness, drf)和ffd算法在物理服務(wù)器消耗方面的性能比較如圖3所 示。由圖中可以看到，由于mcca達(dá)到了較好的多維均衡性，因此不論何 種規(guī)模的工作負(fù)載，都能夠獲得最優(yōu)的資源投入性能。通過分析發(fā)現(xiàn)，mcca 相比drf、ffd算法分別節(jié)省5%和12.2%的服務(wù)器使用量。據(jù)統(tǒng)計(jì)，服務(wù) 器等硬件投入占到數(shù)據(jù)中心資金總投入的60%,該優(yōu)化結(jié)果相當(dāng)于在虛擬 化基礎(chǔ)上又節(jié)省近10%的資金投入，同時(shí)較少的運(yùn)行機(jī)器消耗更少的電能, 有助于實(shí)現(xiàn)數(shù)據(jù)中心的高密度、低成木良性發(fā)展。mcca之所以能夠減少服 務(wù)器使用數(shù)量，

18、是山于其在調(diào)度中綜合考慮了虛擬機(jī)的資源需求特性以及 服務(wù)器的各維資源容量，通過虛擬機(jī)的多維合理聚合使服務(wù)器的空余資源 達(dá)到均衡，為后續(xù)虛擬機(jī)的調(diào)度提供了更多的可能性，最終實(shí)現(xiàn)服務(wù)器各 維資源物盡其用，相應(yīng)地減少了服務(wù)器的需求數(shù)量。除了物理服務(wù)器的使用數(shù)量，系統(tǒng)資源的綜合利用率也是衡量調(diào)度算 法性能優(yōu)劣的重要依據(jù)。圖4是mcca、drf和ffd算法在多維資源綜合利 用率方面的比較。由圖中可以看到，mcca相比drf、ffd算法獲得了 6. 8% 13.1%的提高，并且mcca算法具有較小的標(biāo)準(zhǔn)差，表明算法在穩(wěn)定性方面 具冇一定的優(yōu)勢(shì)。由于mcca在虛擬機(jī)調(diào)度過程屮注重調(diào)節(jié)服務(wù)器多維資 源之間利用

19、率的增長(zhǎng)比率，每次調(diào)度虛擬機(jī)時(shí)盡量滿足服務(wù)器多維資源之 間的互補(bǔ)關(guān)系，防止出現(xiàn)因一種或幾種資源過早飽和而抑制其他資源使用 的現(xiàn)象，所以從整體上提高了資源的綜合利用率。4結(jié)語隨著云計(jì)算的出現(xiàn)，數(shù)據(jù)中心資源的虛擬化以及多用戶應(yīng)用的異構(gòu) 化，使得服務(wù)器內(nèi)部多種資源間分配越來越不均衡，嚴(yán)重影響了系統(tǒng)資源 的使用效率。本文在分組遺傳算法框架的基礎(chǔ)上，進(jìn)行了模糊邏輯的多維 搜索函數(shù)設(shè)計(jì)，提出了一種高效的基于多維資源協(xié)同聚合的虛擬機(jī)調(diào)度算 法，實(shí)現(xiàn)了數(shù)據(jù)中心資源的高效均衡分配。最后，通過與該領(lǐng)域最新提出 的多維資源調(diào)度算法drf和經(jīng)典聚合調(diào)度算法fed比較，證明了該調(diào)度算 法的有效性和高效性。參考文獻(xiàn)：1

20、hyser c, mckee b, gardner r, et al. autonomic virtual machine placement in the data center, hpl-2007-189rsl： iip labs, 2007.2 michael r g, david s j. computers and intractability： a guide to the theory of np-completenessm. san francisco： w. h. freeman publishers, 19793 chen m, zhang h, su y, et al.

21、effective vm sizing in virtualized data centersc/ proceedings of the 12th ifip/ieee international symposium on integrated network management. piscataway： ieee, 2011： 594-6014 ghodsi a, zaharta m, konwtnskt a, et al. dominant resource fairness : fair allocation of heterogeneous resources in datacente

22、rsc/ proceedings of the 8th usenix conferenee onnetworked systems design and implementation. berkley: usenixassociation, 2011： 2-35 speitkamp b, bichler m. a mathematical programming approach for server consolidation problems in virtualized data centersj teee transactions on services computing, 2010

23、, 3 (4)： 266-27&6 calheiros r n, ranjan r, de rose c a f, et al. cloudsim： a novel framework for modeling and simulation of cloud computing infrastructures and serviceseb/ol. 2013-06-03. http :/www. cloudbus org/rcports/cloudsini-icpp2009. pdf7 amossen r r, ptstnger 0. multi-dimensional bin packingproblems with guillotine constraintsj computers and operations research, 2010,37 (11)：1999-2006.8 falkenauer e, delchambre a. a genetic algorithm for bin packing and li