[發明專利]基于改進的遺傳算法的云計算資源調度實現方法

有效

• 申請號: 201610057638.8
• 申請日: 2016-01-27
• 公開（公告）號: CN105740051B
• 公開（公告）日: 2019-03-22
• 發明（設計）人: 竹翠;仇瑞琪
• 申請（專利權）人: 北京工業大學
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/50;G06N3/12
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 沈波

1.基于改進的遺傳算法的云計算資源調度實現方法，其特征在于：

隨著云計算的發展，數據中心規模越大，能耗問題和資源利用率成為最主要的制約因素，因此在滿足用戶需求的基礎上，如何設計合理的資源調度方法，提高資源利用率，降低能耗成為迫切需要解決的問題，也是目前云計算發展的瓶頸之一；

因此本方法提出基于改進的遺傳算法的云計算資源調度實現方法，該方法將遺傳算法進行改進，并應用到云計算資源調度中；將SLA約束和能耗約束作為適應度函數，使得虛擬機在物理機上創建時能夠找到最合適的放置策略，改進后的遺傳算法在滿足用戶需求基礎上，節約能耗，最大程度產生最優的經濟效益；

基于遺傳算法的調度資源模型建立，遺傳算法是一種借鑒生物界自然選擇和遺傳機制的啟發式搜索算法，在解決多目標問題上它可以在大規模的解空間中尋找到高質量的解決方案；在搜索的過程中，得到解空間的最優解，經過迭代的過程發現新的個體，將局部最優解和新的個體結合起來，來完成尋找全局最優解的目標；在遺傳算法中，用種群來表示一個解空間，用其中的染色體來表示一條具體的解決方案，用適應度函數來衡量染色體的質量；在云計算虛擬資源中，設計遺傳算法時需要對擬分配的虛擬資源進行分析，具體分析過程如下：

(1)編碼和種群初始化：本方法中采用的編碼方式是實數編碼，染色體的長度為即將創建虛擬機的個數，染色體{...host_i...}中第i個元素的值為host_i＝m，含義為第i臺虛擬機創建在編號為m的主機上；不斷的隨機產生新的染色體并加入到種群中，直到種群大小達到預設值；

(2)適應度函數：選擇合適的適應度函數，根據適應度函數評估每個染色體的適應度，也就是根據適應度函數衡量該條調度方案的質量；

(3)判斷：判斷當前解是否滿足要求或是否已經達到迭代次數；如果是，則終止計算，返回最優解；否則轉向步驟(4)；

(4)選擇、交叉、變異：根據既定規則選擇出一部分解，并對這部分解進行基因操作交叉、變異，得到新的解，將新的解加入到種群中，轉向步驟(3)進行判斷；

具體實施算法如下：

1)初始化種群時，隨機產生染色體，對產生的染色體進行約束；主機Host的資源包括CPU、內存、網絡帶寬、存儲資源的集合，上述集合能抽象描述為下式(1)，其中Host_res為Host的總資源，CPU_res代表Host中的CPU資源，Ram_res代表內存資源，Bw_res代表網絡帶寬資源，Stor_res代表存儲資源；

Host_res＝[CPU_res,Ram_res,Bw_res,Stor_res] (1)

一個Host所占用的資源是分配在上邊的所有VM所占用的資源的總和，VM_i表示在資源調度下第i個虛擬機，用戶選擇一共創建多少臺虛擬機；

在隨機產生的染色體策略中，當在一個Host上即將創建VM時，從Host總的資源中減去VM所需的資源，當其中的任意一項小于零，說明此染色體中當前的Host資源已被全部占用，則這條染色體不在最優解的范圍內，從種群中剔除；這樣的約束能夠保障整個種群的質量，避免VM之間的資源競爭而導致的云服務性能下降或VM創建不成功；

2)適應度函數的選擇對于整個遺傳算法來說至關重要，種群個體的適應度函數值越大說明該個體更容易適應環境；本方法中的調度目標是在保障用戶的滿意度即不違反SLA約束的基礎上，使得能耗降低，云服務供應商取得更大的收益；將適應度函數設計為下式(2)；

Fitness＝Income_total-w1*Energy_total-w2*SLA_totalPenal (2)

其中，Fitness是適應度函數，w1,w2為各項的權重；Income_total代表著根據不同的云任務計算得到不同的收入，由于對于某個固定的調度任務來說所得到的收入是相同的，所以在計算個體的適應度值時，個體的適應度值簡化為零；Energy_total代表著完成調度任務所消耗的全部能耗，用虛擬機從開始創建到結束的時間差來衡量能耗的多少；SLA_totalPenal是在調度中如果違反SLA約束的代價花費，SLA就是指當VM隨時訪問所需的所有MIPS時Host都能夠百分之百提供，用來衡量VM可用性的百分比；如果虛擬機所期待得到的MIPS小于給它分配的，即違反SLA約束；SLA_totalPenal通過下式(3)得到：

其中的MIPS_{totalAllocated}表示所有已經分配的MIPS的值，MIPS_totalMissed表示未及時分配給VM的MIPS的值；

整體的能耗越小，證明虛擬機在創建的時候越集中在某些Host上，這樣必然會使整個系統的資源使用率升高；違反SLA的次數越少，用戶的體驗越好，任務會在更短的時間內完成；從這兩個角度來衡量種群中個體的質量是全面而合理的。