[發(fā)明專利]云計算數(shù)據(jù)中心兼顧能耗與訪問延遲的虛擬機分配方法

在審

• 申請?zhí)枺?/td>: 201710457206.0
• 申請日: 2017-06-16
• 公開（公告）號: CN107360210A
• 公開（公告）日: 2017-11-17
• 發(fā)明（設(shè)計）人: 蔣嶷川;司景霞;張友紅
• 申請（專利權(quán)）人: 佛山科學(xué)技術(shù)學(xué)院
• 主分類號: H04L29/08
• 分類號: H04L29/08;G06F9/455;G06F9/50
• 代理公司: 廣州嘉權(quán)專利商標(biāo)事務(wù)所有限公司44205
• 代理人: 王國標(biāo)

1.云計算數(shù)據(jù)中心兼顧能耗與訪問延遲的虛擬機分配方法，其特征在于：包括以下步驟：

(1)模型抽象；

所述模型抽象方法如下：

(1.1)將云計算數(shù)據(jù)中心抽象成一個由n個計算節(jié)點和m個數(shù)據(jù)節(jié)點通過網(wǎng)絡(luò)連接構(gòu)成的無向網(wǎng)，用四元組表示：CDC＝CN,DN,D₁,D₂，其中計算節(jié)點集合和數(shù)據(jù)節(jié)點集合分別表示為CN＝{cn₁,cn₂,…,cn_n}和DN＝{dn₁,dn₂,…,dn_m}；每個計算節(jié)點cn_i∈CN擁有c_i個虛擬機，即計算節(jié)點cn_i的最大計算能力為c_i，其中c_i∈N；每個計算節(jié)點cn_i∈CN的可用虛擬機個數(shù)為u_i，其中u_i≤c_i；用[x]代表整數(shù)集合{1,2…x}；D₁＝[d_i,j]_n×m表示計算節(jié)點和數(shù)據(jù)節(jié)點之間的數(shù)據(jù)訪問延遲矩陣，表示計算節(jié)點之間的數(shù)據(jù)訪問延遲矩陣；將用戶的任務(wù)表示為一組待虛擬機處理的數(shù)據(jù)節(jié)點集合DN′＝dn′₁,dn′₂,…,dn′_j,…,dn′_s，s≤m；

(1.2)當(dāng)任務(wù)到達時，系統(tǒng)即為請求處理的每一個數(shù)據(jù)節(jié)點分配一個虛擬機，即每一個請求處理的數(shù)據(jù)節(jié)點需要一個虛擬機處理其數(shù)據(jù)；一個有效的虛擬機分配策略可以表示為P＝ec,d,X，其中，ec表示分配策略P的能耗，y_i表示計算節(jié)點cn_i的開啟狀態(tài)，如果計算節(jié)點cn_i分配了虛擬機，y_i＝1，否則y_i＝0；d表示分配策略P的最大數(shù)據(jù)訪問延遲；X＝[x_i,j]表示計算節(jié)點集合CN和數(shù)據(jù)節(jié)點集合DN′之間的一個映射，其中x_i,j表示二進制變量；如果計算節(jié)點cn_i的虛擬機分配給數(shù)據(jù)節(jié)點dn′_j，x_i,j＝1，否則x_i,j＝0；這個映射必須滿足以下兩個基本條件：

對每個計算節(jié)點cn_i∈CN，分配給數(shù)據(jù)節(jié)點的虛擬機不能超出計算節(jié)點cn_i的虛擬機總數(shù)：

對任意一個數(shù)據(jù)節(jié)點dn′_j∈DN′,有且只有一個虛擬機來處理它的數(shù)據(jù)：

(1.3)要保證所得分配策略的最大數(shù)據(jù)訪問延遲為d，分配策略需要滿足以下約束條件：

開啟的計算節(jié)點和對應(yīng)的分配虛擬機資源的數(shù)據(jù)節(jié)點之間的數(shù)據(jù)訪問延遲不大于最大數(shù)據(jù)訪問延遲d：

任意一對開啟的計算節(jié)點之間的數(shù)據(jù)訪問延遲不大于最大數(shù)據(jù)訪問延遲d：

其中，二進制決策變量x_i,j和y_i之間的約束關(guān)系：

(2)數(shù)據(jù)訪問延遲矩陣線性化；

所述數(shù)據(jù)訪問延遲矩陣線性化過程如下：將計算節(jié)點和數(shù)據(jù)節(jié)點之間的數(shù)據(jù)訪問延遲矩陣和計算節(jié)點之間的數(shù)據(jù)訪問延遲矩陣中的元素降序排列，存儲在一維數(shù)據(jù)數(shù)組中；

(3)在當(dāng)前閾值約束下，尋找計算節(jié)點和數(shù)據(jù)節(jié)點的候選集，以及計算計算節(jié)點的實際能力；

在當(dāng)前閾值約束下，尋找計算節(jié)點和數(shù)據(jù)節(jié)點的候選集，以及計算計算節(jié)點的實際能力過程如下：在當(dāng)前閾值約束下，對于每一個計算節(jié)點cn_i，查找所有的數(shù)據(jù)節(jié)點；如果存在數(shù)據(jù)節(jié)點dn_j和計算節(jié)點cn_i的數(shù)據(jù)訪問延遲不大于當(dāng)前閾值，就將數(shù)據(jù)節(jié)點dn_j加入計算節(jié)點cn_i的候選集C(cn_i)；

對于每一個數(shù)據(jù)節(jié)點dn_j，查找所有的計算節(jié)點；如果存在計算節(jié)點cn_i和數(shù)據(jù)節(jié)點dn_j的數(shù)據(jù)訪問延遲不大于當(dāng)前閾值，就將計算節(jié)點cn_i加入數(shù)據(jù)節(jié)點dn_j的候選集；

計算節(jié)點的實際能力rc_i的計算公式如下：

rc_i＝min{c_i,|C(cn_i)|}；

其中，|·|表示集合C(cn_i)的基數(shù)，min{a,b}表示a和b的最小值；

(4)在當(dāng)前閾值約束下，尋找中心節(jié)點集CenterNode和鄰居節(jié)點集S；

在當(dāng)前閾值約束下，尋找中心節(jié)點集CenterNode和鄰居節(jié)點集S步驟如下：首先將當(dāng)前實際能力最大的計算節(jié)點加入中心節(jié)點集合，然后，將與該節(jié)點的數(shù)據(jù)訪問延遲不大于當(dāng)前閾值的計算節(jié)點加入中心節(jié)點集合；計算節(jié)點集合CN關(guān)于中心節(jié)點集CenterNode的補集即是鄰居節(jié)點集S；

(5)虛擬機分配和分配策略的更新；

所述虛擬機分配和分配策略的更新步驟如下：

(5.1)對中心節(jié)點集CenterNode中的每一個計算節(jié)點執(zhí)行以下操作：

(5.1.1)將中心節(jié)點集CenterNode中的當(dāng)前計算節(jié)點cn_i加入集合V，將鄰居節(jié)點集S中與計算節(jié)點cn_i的數(shù)據(jù)訪問延遲不大于閾值的計算節(jié)點加入集合V；集合U存放所有的數(shù)據(jù)節(jié)點；

(5.1.2)當(dāng)集合V和集合U都不為空時，貪心選擇出實際能力最大的計算節(jié)點cn_l^v；將集合V中實際能力rc_l^v最大的計算節(jié)點cn_l^v的一個虛擬機分配給集合U中候選集最小的數(shù)據(jù)節(jié)點；更新集合V和集合U，重復(fù)上述過程；當(dāng)集合V或集合U為空時，執(zhí)行步驟(5.2)，否則執(zhí)行步驟(5.3)；

(5.2)如果經(jīng)過步驟(5.1.2)所有的數(shù)據(jù)節(jié)點均獲得一個虛擬機，計算該局部分配策略的評估值并更新全局分配策略，評估值的計算方法如下：

(5.2.1)首先分別將當(dāng)前分配策略的能耗和最大數(shù)據(jù)訪問延遲通過Max-Min標(biāo)準(zhǔn)化方法映射成在區(qū)間[0,1]中的值，其公式為：

其中，x_max和x_min分別表示變量x的最大值和最小值；

(5.2.2)然后，通過一個權(quán)重系數(shù)w將標(biāo)準(zhǔn)化的能耗和數(shù)據(jù)訪問延遲轉(zhuǎn)化為一個目標(biāo)評估值，其公式為：

value＝w·f(ec)+(1-w)·f(d)；

(5.2.3)分配策略的更新規(guī)則為：如果當(dāng)前分配策略的評估值小于全局分配策略的評估值，就用當(dāng)前分配策略替換全局分配策略；

(5.3)如果經(jīng)過步驟(5.1.2)存在一個數(shù)據(jù)節(jié)點沒有獲得虛擬機，則當(dāng)前的全局分配策略即為最終求解得到的分配策略；

其中，所述閾值為最大數(shù)據(jù)訪問延遲。