[發(fā)明專利]云計(jì)算環(huán)境下基于VHAM-R模型的虛擬機(jī)放置遺傳優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201811079838.9
• 申請(qǐng)日: 2018-09-17
• 公開（公告）號(hào): CN109447264B
• 公開（公告）日: 2021-11-23
• 發(fā)明（設(shè)計(jì)）人: 陸佳煒;趙偉;李杰;吳涵;肖剛;高燕煦
• 申請(qǐng)（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號(hào): G06F9/455
• 分類號(hào): G06F9/455;G06N3/12
• 代理公司: 杭州斯可睿專利事務(wù)所有限公司 33241
• 代理人: 王利強(qiáng)

1.一種云計(jì)算環(huán)境下基于VHAM-R模型的虛擬機(jī)放置遺傳優(yōu)化方法，其特征在于，所述方法包括以下步驟：

第一步：對(duì)于虛擬機(jī)放置問(wèn)題提出以下的形式化描述，過(guò)程如下：

1.1定義放置環(huán)境，數(shù)據(jù)中心存在物理主機(jī)集合PM＝{pm₁，pm₂，...，pm_n}，其中主機(jī)數(shù)量為n，需要放置的虛擬機(jī)集合VM＝{vm₁，vm₂，...，vm_m}，其中虛擬機(jī)數(shù)量為m，假設(shè)虛擬機(jī)數(shù)量m大于或等于主機(jī)n，定義虛擬機(jī)放置組集合P＝{p₁，p₂，...，p_h}，h為放置組的數(shù)量；

1.2定義資源狀態(tài)，對(duì)于給定的虛擬機(jī)vm_i，定義為虛擬機(jī)vm_i所需的CPU資源，為虛擬機(jī)vm_i所需的內(nèi)存資源，V_i-pes為虛擬機(jī)vm_i的CPU利用率，W_i-ram為虛擬機(jī)vm_i的內(nèi)存利用率，對(duì)于給定的主機(jī)pm_j，定義為主機(jī)pm_j當(dāng)前的CPU空閑資源，為主機(jī)pm_j的內(nèi)存空閑資源，U_j-pes為主機(jī)pm_j的CPU利用率，U_j-ram為主機(jī)pm_j的內(nèi)存利用率，則定義主機(jī)pm_j的資源利用率U_j為：

U_j＝αU_j-pes+βU_j-ram

0＜α＜1，0＜β＜1，且α+p＝1；

定義Tag_ij為當(dāng)前時(shí)刻t，主機(jī)pm_j滿足虛擬機(jī)vm_i的資源要求，即

1.3主機(jī)可用性，一個(gè)節(jié)點(diǎn)的可用性是指節(jié)點(diǎn)在整個(gè)服務(wù)時(shí)間內(nèi)任意時(shí)刻的工作概率，對(duì)于任意網(wǎng)絡(luò)組件i，其可用性A_i通過(guò)以下公式計(jì)算獲得：

其中MTTF代表平均故障時(shí)間，MTTR代表平均修復(fù)時(shí)間，假定服務(wù)器可用性的值是已知的，且各服務(wù)器之間的可用性是相互獨(dú)立互不相關(guān)的；

1.4計(jì)算電能消耗，在一個(gè)擁有n臺(tái)運(yùn)行的物理主機(jī)的云數(shù)據(jù)中心，對(duì)于任意物理主機(jī)pm_j∈PM，在某一時(shí)刻t的電源能耗如下公式所示：

其中c_j為靜態(tài)能耗標(biāo)記，f_j(t)為t時(shí)刻主機(jī)pm_j的CPU頻率，CPU利用率為U_j-pes(t)，k為常量系數(shù)，即電源能耗在一定程度上是基于CPU利用率的線性模型，

1.5定義虛擬機(jī)放置，VM集合通過(guò)放置組p_k∈P，選擇對(duì)應(yīng)的物理主機(jī)集合中的主機(jī)完成放置映射，并且需要滿足放置過(guò)程中的多種約束條件，定義虛擬機(jī)放置矩陣M_k[i][j]，若M_k[i][j]＝1則表示放置組p_k將虛擬機(jī)j放置在物理主機(jī)i上，反之，若M_k[i][j]＝0，表示放置組p_k中，虛擬機(jī)j未放置在物理主機(jī)i上；

第二步：對(duì)虛擬機(jī)放置設(shè)定約束條件及優(yōu)化目標(biāo)，過(guò)程如下：

2.1對(duì)于云環(huán)境下的虛擬機(jī)放置問(wèn)題，既要考慮滿足虛擬機(jī)資源的需求，又要考慮如何減少數(shù)據(jù)中心的能耗、資源的高效利用，此外還要考慮放置請(qǐng)求的可用性問(wèn)題；因此，需要在考慮范圍內(nèi)的約束有：服務(wù)器節(jié)點(diǎn)的最大使用數(shù)量最少、能耗最低、負(fù)載較均衡和放置請(qǐng)求的可用性較高，提出以下約束條件：

2.1.1放置約束，任意虛擬機(jī)vm_i，在同一放置組下，其能且只能放置在一個(gè)服務(wù)器節(jié)點(diǎn)上；

約束表示：

對(duì)于其中放置組p_k∈P；

同一放置組內(nèi)，都認(rèn)為單個(gè)虛擬機(jī)只能在一個(gè)服務(wù)器節(jié)點(diǎn)上進(jìn)行部署運(yùn)行；

2.1.2資源約束，對(duì)于任何服務(wù)器節(jié)點(diǎn)來(lái)說(shuō)，其各個(gè)資源類型的消耗應(yīng)不能超過(guò)上限，定義服務(wù)器pm_j的CPU和內(nèi)存容量分別為和表示；

約束表示：

對(duì)于有

參數(shù)r為常量系數(shù)，服務(wù)器節(jié)點(diǎn)需要預(yù)留一部分的資源保證其自身的正常運(yùn)轉(zhuǎn)，r≤1；

2.1.3可達(dá)性約束，定義函數(shù)F(m，n，D)用于表示節(jié)點(diǎn)間通信的可達(dá)性，對(duì)于任意鏈接(m，n)∈L，如果點(diǎn)m和n的通信延遲至多為D，則函數(shù)F(m，n，D)返回1，否則返回0；

2.2虛擬機(jī)放置問(wèn)題的優(yōu)化目標(biāo)眾多，選取可用性及能耗兩方面對(duì)虛擬機(jī)放置問(wèn)題進(jìn)行優(yōu)化研究；

2.2.1可用性優(yōu)化

假設(shè)用戶請(qǐng)求由具有相關(guān)通信要求的n個(gè)不同的VM對(duì)之間的虛擬機(jī)組成，將其放置在同一個(gè)服務(wù)器節(jié)點(diǎn)pm_j不止一次不能提高放置的可用性，因?yàn)楫?dāng)pm_j失敗時(shí)，所有放置在pm_j上的虛擬機(jī)將同時(shí)失敗，因而，需要盡量將vm_i放置在不同的節(jié)點(diǎn)上以增加可用性；用H_i來(lái)表示放置虛擬機(jī)vm_i的最大節(jié)點(diǎn)數(shù)，即H_i表示vm_i可以放置的最大服務(wù)器節(jié)點(diǎn)數(shù)量；定義用于表示該n個(gè)虛擬機(jī)中，單個(gè)虛擬機(jī)所需節(jié)點(diǎn)數(shù)最大為H；

虛擬機(jī)放置的可用性定義和計(jì)算可以分成三種：?jiǎn)我环胖谩⑼耆Ｗo(hù)放置和部分受保護(hù)放置；

2.2.1.1單一放置

單一放置指每個(gè)虛擬機(jī)都只放在一個(gè)服務(wù)器節(jié)點(diǎn)上，即H＝1，在單一放置的情況下，如果n個(gè)服務(wù)器節(jié)點(diǎn)的可用性分別為A₁，A₂，...，A_n，k個(gè)虛擬機(jī)(n≤k)放置于此n個(gè)節(jié)點(diǎn)之上，則此虛擬機(jī)放置方案的可用性可用A_p表示，定義如下：

由于請(qǐng)求包含k個(gè)虛擬機(jī)，因此計(jì)算可用性時(shí)需要考慮k個(gè)虛擬機(jī)均在運(yùn)行的概率；

2.2.1.2完全保護(hù)放置

完全保護(hù)放置指對(duì)于任意虛擬機(jī)均由放置組p_i(1≤i≤H)放置在H個(gè)不同節(jié)點(diǎn)上；因此，可以認(rèn)為一個(gè)完全保護(hù)放置方案P可由H個(gè)單一放置方案構(gòu)成，且在各個(gè)單一放置方案內(nèi)，虛擬機(jī)對(duì)之間都應(yīng)該滿足放置、資源和通信可達(dá)性約束；

完全保護(hù)放置方案的可用性為在服務(wù)的生命周期內(nèi)，存在至少一個(gè)放置組工作的概率，可用性計(jì)算如下式所示：

2.2.1.3部分保護(hù)放置

部分保護(hù)放置指存在虛擬機(jī)vm_i∈VM，被放置在少于H個(gè)不同節(jié)點(diǎn)上，即兩個(gè)或者更多個(gè)放置組將虛擬機(jī)vm_i放置在相同的節(jié)點(diǎn)上，且存在某個(gè)虛擬機(jī)vm_j∈VM，使得H＞1，在部分保護(hù)的放置情況下，若一個(gè)虛擬機(jī)放置在少于H個(gè)節(jié)點(diǎn)上，可以認(rèn)為這個(gè)虛擬機(jī)由多個(gè)放置組共同放置；無(wú)法直接通過(guò)2.2.1.2中的公式計(jì)算其可用性，因?yàn)榉胖昧斯蚕淼奶摂M機(jī)的服務(wù)器節(jié)點(diǎn)的可用性會(huì)被計(jì)算兩次；為了處理該類放置情況，重新定義操作符·；假設(shè)存在n個(gè)節(jié)點(diǎn)pm₁，pm₂，...，pm_n，它們的可用性分別為A₁，A₂，...，A_n；對(duì)于可用性為A_x的節(jié)點(diǎn)pm_x，給出如下關(guān)于操作符·的定義：

則根據(jù)上述中的公式，定義為不同集合間的·操作，保護(hù)放置的可用性通過(guò)如下公式計(jì)算獲得：

2.2.2能耗優(yōu)化

根據(jù)1.4中的公式，在T時(shí)間段內(nèi)，物理主機(jī)pm_j的總耗能表示為：

因此，由以下公式得，在T時(shí)間段內(nèi)，數(shù)據(jù)中心的服務(wù)器總能耗E^T為各運(yùn)行的服務(wù)器的能耗之和：

第三步：創(chuàng)建模型

基于第二步中給出的虛擬機(jī)放置的約束條件和優(yōu)化目標(biāo)，建立基于Rendezvous哈希算法的虛擬分層結(jié)構(gòu)模型VHAM-R，用于優(yōu)化和決策虛擬機(jī)對(duì)主機(jī)的選擇過(guò)程，步驟如下：

3.1初始化主機(jī)集合PM，虛擬機(jī)集合VM，虛擬機(jī)最多放置組數(shù)量H，主機(jī)節(jié)點(diǎn)的可用性集合A，若主機(jī)數(shù)量n小于4進(jìn)入步驟3.2，否則進(jìn)入步驟3.3；

3.2主機(jī)數(shù)量n小于4，即無(wú)法滿足構(gòu)建最小雙層虛擬結(jié)構(gòu)的數(shù)量2*2時(shí)，定義其對(duì)應(yīng)每個(gè)主機(jī)具有一個(gè)分配權(quán)重得分集合W_i＝{w_i1，w_i2，...，w_ik}其中，k≥n，定義w_ij為虛擬機(jī)vm_i在主機(jī)pm_j上的權(quán)重得分，w_ij＝h(vm_i，pm_j)，其中函數(shù)h(vm，pm)為Rendezvous哈希算法中約定的哈希函數(shù)，然后通過(guò)h(vm_i，pm_j)將虛擬機(jī)vm_i分配給權(quán)重w_ij最大的主機(jī)pm_j，如果主機(jī)pm_k的性能是其他主機(jī)的h倍，則將pm_k等額分成h份，現(xiàn)在虛擬機(jī)分配到該主機(jī)上的概率是其他主機(jī)的h倍；

3.3主機(jī)數(shù)量n≥4，對(duì)主機(jī)簇群劃分，首先選擇一個(gè)常數(shù)z，即每個(gè)簇中的主機(jī)數(shù)為z，將主機(jī)集合按照c＝ceiling(n/z)，其中ceiling函數(shù)表示將n除以z的值向上舍入為最接近的整數(shù)，C₀＝{cpm₁，cpm₂，...，cpm_z}，C₁＝{cpm_z+1，cpm_z+2，...，cpm_2z}，...直至每個(gè)主機(jī)都?xì)w屬于一個(gè)簇，每個(gè)簇為虛擬分層結(jié)構(gòu)中的最底層節(jié)點(diǎn)；

第四步：基于VHAM-R模型的遺傳算法操作改進(jìn)，過(guò)程如下：

4.1為求解虛擬機(jī)放置到服務(wù)器節(jié)點(diǎn)的過(guò)程，提出基于主機(jī)節(jié)點(diǎn)簇的分組編碼方式，P為放置組表示個(gè)體，C_i表示主機(jī)簇C_i對(duì)應(yīng)為染色體，每個(gè)主機(jī)簇上的主機(jī)對(duì)應(yīng)為基因；

4.2選擇操作通過(guò)自己設(shè)定的適應(yīng)度函數(shù)，對(duì)種群中含有優(yōu)良基因的個(gè)體進(jìn)行選擇，以數(shù)據(jù)中心能耗以及虛擬機(jī)放置可用性為優(yōu)化目標(biāo)；選擇操作的過(guò)程為：

4.2.1當(dāng)H＝1時(shí)，對(duì)于每個(gè)個(gè)體，都對(duì)應(yīng)了一種虛擬機(jī)放置情況，因此，其可用性按照單一放置進(jìn)行計(jì)算，即對(duì)于個(gè)體P，其放置可用性其中該個(gè)體包含n個(gè)基因；

4.2.2當(dāng)H＞1的情況時(shí)，對(duì)于該H個(gè)個(gè)體的可用性需要按照受保護(hù)放置的計(jì)算方式來(lái)處理；

4.2.2.1對(duì)于任意虛擬機(jī)vm_i∈VM，均由放置組p_i放置在H個(gè)不同節(jié)點(diǎn)上，1≤i≤H，即對(duì)于H個(gè)個(gè)體，每個(gè)基因上的各個(gè)虛擬機(jī)均不相同，此情況下，該H個(gè)放置組的可用性按照完全保護(hù)放置的計(jì)算方式來(lái)處理；

4.2.2.2若存在虛擬機(jī)vm_i∈VM，兩個(gè)或者更多個(gè)個(gè)體中，虛擬機(jī)vm_i被放置在相同基因上，此情況下，該H個(gè)放置組的可用性按照部分保護(hù)放置的計(jì)算方式來(lái)處理；

4.2.3結(jié)合數(shù)據(jù)中心能耗優(yōu)化，給出以下遺傳算法的適應(yīng)度函數(shù)：

其中，E_min為T時(shí)間段內(nèi)數(shù)據(jù)中心能耗的最小值；為單個(gè)個(gè)體的能耗；當(dāng)H＝1時(shí)，可用性以單一放置方式計(jì)算；當(dāng)H＞1時(shí)，可用性計(jì)算分為完全保護(hù)放置和部分保護(hù)放置，其中x為數(shù)量為H的個(gè)體群；對(duì)于個(gè)體或個(gè)體群x，若能使數(shù)據(jù)中心能耗越低、可用性越高，則適應(yīng)度函數(shù)的值就越大，優(yōu)良基因遺傳到下一代的被選擇概率越高；

4.3遺傳算法中的交叉操作是模擬生物界中個(gè)體之間的交配過(guò)程，通過(guò)交配達(dá)到父代之間基因的重組，從而使子代獲得包含優(yōu)秀基因的新染色體，產(chǎn)生更優(yōu)秀的后代；交叉操作的過(guò)程為：

4.3.1首先挑選兩個(gè)需要交配的父代，命名為X、Y，隨機(jī)挑選X父代中包含一個(gè)或多個(gè)基因的某一節(jié)點(diǎn)簇作為需要交叉的部分，將該節(jié)點(diǎn)簇即其中所有基因插入到Y(jié)父代交叉點(diǎn)位置中，此時(shí)，將會(huì)產(chǎn)生包含X、Y父代基因的新的子代；

4.3.2在完成基因插入之后，由于本發(fā)明使用基于主機(jī)簇的染色體分組編碼方式，可能會(huì)出現(xiàn)相同的主機(jī)簇，若出現(xiàn)該種情況，則將插入的基因合并到原先的主機(jī)簇中；

4.3.3若出現(xiàn)不同的主機(jī)節(jié)點(diǎn)上存在相同的兩個(gè)虛擬機(jī)的情況，將先前包含相同的虛擬機(jī)的主機(jī)節(jié)點(diǎn)暫時(shí)從染色體編碼中剔除；

4.3.4被暫時(shí)的剔除主機(jī)節(jié)點(diǎn)上，可能包含未被其他主機(jī)部署的虛擬機(jī)節(jié)點(diǎn)，針對(duì)這種情況，需要為這些虛擬機(jī)重新編碼至主機(jī)節(jié)點(diǎn)中，選擇染色體中使得滿足約束條件的且能耗最低可用性最高的基因完成分配；

4.3.5若所有基因均不符合要求，則按照VHAM-R模型重新生成新基因片段，互換兩個(gè)父代個(gè)體，重復(fù)交叉過(guò)程可以生成第二個(gè)子代個(gè)體；

4.4遺傳算法中的變異操作，變異操作的過(guò)程為：

4.4.1通過(guò)變異函數(shù)來(lái)確定需要變異的個(gè)體染色體基因，如下公式所示：

其中U_j-pes、U_j-ram分別為主機(jī)的CPU、內(nèi)存利用率，為設(shè)定的參數(shù)；

4.4.2選擇f_c(j)較小的基因進(jìn)行刪除，使得每次刪除的都是利用率較低的較差基因，

4.4.3將該基因上的虛擬機(jī)通過(guò)4.3交叉操作的方法重新進(jìn)行編碼插入到其他基因中。

2.如權(quán)利要求1所述的云計(jì)算環(huán)境下基于VHAM-R模型的虛擬機(jī)放置遺傳優(yōu)化方法，其特征在于，所述步驟3.3中，對(duì)主機(jī)簇群劃分的過(guò)程為：

3.3.1虛擬葉子節(jié)點(diǎn)扇區(qū)以及虛擬分層結(jié)構(gòu)深度確定，選擇虛擬分層結(jié)構(gòu)中每個(gè)子節(jié)點(diǎn)扇區(qū)的葉子數(shù)f，f為一位整數(shù)，選擇合適的f和z會(huì)使得到的算法效益和負(fù)載均衡度和期望較相近；根據(jù)節(jié)點(diǎn)扇區(qū)的葉子數(shù)f以及主機(jī)簇個(gè)數(shù)c，可以得到虛擬分層結(jié)構(gòu)的深度d：

f^d≥c

其中d是最小正整數(shù)，求出d使得上述公式成立；

3.3.2各虛擬葉子節(jié)點(diǎn)扇區(qū)編號(hào)，采用自然編號(hào)對(duì)每個(gè)扇區(qū)分別統(tǒng)一編號(hào)，從0，1，2，...，f-1；

3.3.3對(duì)于某一虛擬機(jī)vm_i，對(duì)于任意一個(gè)虛擬節(jié)點(diǎn)s，都有一個(gè)對(duì)應(yīng)的權(quán)重w_is＝h(vm_i，s)，h(vm_i，s)內(nèi)包含約定的哈希函數(shù)，在虛擬分層結(jié)構(gòu)的每一層葉子扇區(qū)，都可通過(guò)h(vm_i，s)計(jì)算各虛擬節(jié)點(diǎn)權(quán)重，選擇得分最高的節(jié)點(diǎn)繼續(xù)向下分層，直到選擇至最底層的真實(shí)主機(jī)節(jié)點(diǎn)簇Cx；

3.3.4當(dāng)虛擬機(jī)vm_i選中真實(shí)主機(jī)節(jié)點(diǎn)簇C_x后，在進(jìn)行真實(shí)節(jié)點(diǎn)選擇時(shí)，假設(shè)對(duì)于任意在真實(shí)節(jié)點(diǎn)簇C_x中的主機(jī)節(jié)點(diǎn)cpm_xz+j，都有一個(gè)對(duì)應(yīng)的權(quán)重得分W_i(xz+j)＝H(vm_i，cpm_xz+j)*Tag_i(xz+j)，若Tag為false，則為0，若為true默認(rèn)為1；其中，將虛擬機(jī)vm_i分配給主機(jī)cpm_xz+j之后，H(vm_i，cpm_xz+j)為在相同T時(shí)間段內(nèi)，E_old與分配虛擬機(jī)vm_i后的真實(shí)主機(jī)節(jié)點(diǎn)簇C_x的總體能耗的比值，與主機(jī)pm_xz+j的資源利用率U_xz+j與1的差方和對(duì)應(yīng)權(quán)重常數(shù)的乘積以及主機(jī)可用性與系數(shù)乘積的和：

其中E_xz+j為T時(shí)間段內(nèi)主機(jī)cpm_xz+j的能耗，E_old是指相同T時(shí)間段內(nèi)，未分配新虛擬機(jī)時(shí)，真實(shí)主機(jī)節(jié)點(diǎn)簇C_x的能耗；α、β、γ是表示三者的權(quán)重；A_xz+j為主機(jī)cpm_xz+j的可用性；

3.3.5循環(huán)步驟3.3.3-3.3.4，直至所有虛擬機(jī)vm_i最終會(huì)選擇使權(quán)重得分W_i(xz+j)最高的主機(jī)節(jié)點(diǎn)完成分配。