[發明專利]基于蟻群優化算法的云數據中心中虛擬機放置方法

有效

• 申請號: 201711266803.1
• 申請日: 2017-12-05
• 公開（公告）號: CN108108224B
• 公開（公告）日: 2019-10-01
• 發明（設計）人: 邢煥來;朱菁;葉佳;杜圣東;戴朋林
• 申請（專利權）人: 西南交通大學
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06N3/00
• 代理公司: 成都盈信專利代理事務所(普通合伙) 51245
• 代理人: 崔建中

1.基于蟻群優化算法的云數據中心中虛擬機放置方法，其特征在于，數據中心物理機個數為M，采用胖樹拓撲結構，包括以下步驟：

步驟1 獲取請求創建的虛擬機個數N，獲取每個虛擬機v_i所需的CPU資源和Memory資源獲取虛擬機v_i與虛擬機v_j間通信所需的流量以虛擬機v_i與虛擬機v_j間通信所需的流量累加和計算所耗總流量SumTraffic，計算虛擬機v_i與虛擬機v_j間通信所需的流量與總流量SumTraffic的比值獲取每個物理機p_j的CPU容量及Memory容量

步驟2 根據虛擬機之間通信所需的流量降序生成虛擬機的放置次序列表vmList，根據網絡拓撲生成物理機p_i和物理機p_j之間通信所要經過的交換機個數其中p_i≠p_j；

步驟3 初始化蟻群算法所需的參數α、β、ρ_l、ρ_g及網絡拓撲鏈路負載容量以啟發素η₀和信息素τ₀分別對虛擬機v_i與物理機p_j之間的啟發素η(v_i,p_j)和信息素τ(v_i.p_j)進行初始化，設置算法的最大迭代次數gen_max，當前代數gen＝0,當前螞蟻k＝0；所述α表示信息素的重要程度，β表示啟發素的重要程度，ρ_l表示局部信息素的揮發程度，ρ_g表示全局信息素的揮發程度；

步驟4 選取第k個螞蟻，使用和分別記錄物理機p_j已經占用的CPU和Memory資源，用Place(k)記錄第k個螞蟻所尋得的解，Energy(k)記錄該解所需要的能耗，Place(k,v_i)記錄第k個螞蟻尋得的解中的虛擬機v_i所放置的物理機；

步驟5 根據步驟2所生成的vmList按順序取出虛擬機v_i，按照物理機CPU和Memory以及網絡鏈路的約束條件，獲取能夠放置虛擬機v_i并且不會違背約束條件的物理機列表serverList；

步驟6 依次按順序從步驟5所得的serverList中取出物理機p_j，對虛擬機v_i與物理機p_j之間的啟發素η(v_i,p_j)依據啟發素更新式η₁(v_i,p_j)和啟發素更新式η₂(v_i,p_j)計算出數值η₁和數值η₂，根據已放置的虛擬機數量n以方式更新；

步驟7 在0到1之間隨機生成實數q，若q＜q₀執行步驟8；否則執行步驟10；其中q₀為常數；

步驟8 依次按順序從步驟5所得的serverList中取出物理機p_j，根據虛擬機v_i與物理機p_j之間的啟發素η(v_i,p_j)和信息素τ(v_i.p_j)計算出物理機p_j的乘積因子值獲取最大的物理機乘積因子值Γ_max，并將的物理機p_j從serverList中移除；

步驟9 依次按順序從步驟8所得的serverList中取出物理機p_j，根據啟發素更新式η₃(v_i,p_j)計算出新的物理機乘積因子值獲取新的最大的物理機乘積因子值Γ_max，將虛擬機v_i放置到Γ_max所對應的物理機p_j上，并置Place(k,v_i)＝p_j，跳轉到步驟11；

步驟10 根據虛擬機v_i與物理機p_j之間的啟發素η(v_i,p_j)和信息素τ(v_i,p_j)計算出物理機p_j的輪盤賭選擇概率根據的大小以輪盤賭的形式選擇出要將虛擬機v_i放置的物理機p_j,并置Place(k,v_i)＝p_j；

步驟11 更新虛擬機v_i所選擇放置的物理機p_j所使用的CPU資源和Memory資源以及虛擬機v_i與已放置的虛擬機之間通信所需的每個鏈路負載

步驟12 用局部信息素更新方式更新虛擬機v_i與所選擇放置的物理機p_j之間的信息素τ(v_i.p_j)，若有虛擬機沒有放置，則跳轉到步驟5；否則至步驟13；

步驟13 根據螞蟻k所尋得的解Place(k)，計算解Place(k)的能耗并記錄到Energy(k)；

步驟14 若k小于螞蟻數量K，則k＝k+1并跳轉到至步驟4；否則執行步驟15；

步驟15 根據每只螞蟻k所尋得的解Place(k)及解Place(k)的能耗Energy(k)，計算得出最低能耗Energy_best，并將最低能耗Energy_best對應的解作為全局最優解Place_best；

步驟16 依據Place_best對每個所使用的物理機p_j使用全局信息素更新方式對物理機p_j與其上放置的虛擬機v_i之間的信息素τ(v_i,p_j)進行更新；

步驟17 若當前代數gen小于gen_max，則gen＝gen+1，k＝0，并跳轉至步驟4；否則，執行步驟18；

步驟18 由全局最優解Place_best及計算虛擬機間通信所需網絡總帶寬B_min。

2.根據權利要求1所述的基于蟻群優化算法的云數據中心中虛擬機放置方法，其特征在于，還包括：

步驟16.1 使用螞蟻適應度計算式對螞蟻k所尋得的解Place(k)進行計算得出解的適應度值F_Place(k)，與其余螞蟻j進行信息交流；根據螞蟻k的解的適應度值F_Place(k)和螞蟻j的解的適應度值F_Place(j)產生新的解Place′(k)，若解Place′(k)的能耗Energy'(k)低于解Place(k)的能耗Energy(k)，則用Place′(k)作為螞蟻k所尋得的解；再用解Place′(k)的能耗Energy'(k)與最低能耗Energy_best進行比較，選能耗低者作為最低能耗Energy_best，并將最低能耗Energy_best對應的解作為全局最優解Place_best；對每只螞蟻重復上述步驟，得到最終的最低能耗Energy_best和全局最優解Place_best；

步驟16.2 若全局最優解Place_best被更新，則依據Place_best對每個所使用的物理機p_j使用全局信息素更新方式對物理機p_j與其上放置的虛擬機v_i之間的信息素τ(v_i,p_j)進行更新。