基于動態遺傳算法的云計算任務節能調度策略研究

鐘瀟柔　翟健宏

摘 要：云計算的飛速發展造成了許多大型數據中心的建立，海量的數據中心會消耗巨大的電力能源，導致操作成本以及二氧化碳排放量的升高。為了解決這一問題，本文提出了一種基于遺傳算法的新型多目標動態調度算法，將任務的執行時間及數據中心的能耗作為優化目標，充分考慮云環境的動態性，根據任務長度以及資源計算能力將任務分配給資源。本文將該算法與一些著名的云調度模型進行對比，實驗結果證明，本文提出的多目標動態遺傳算法可以有效利用于云環境，并在減少任務執行時間和能耗方面具有一定優勢。

關鍵字：云計算；任務調度；節能；遺傳算法

中圖分類號：TP391.41 文獻標識號：A 文章編碼：2095-2163（2015）03-

Energy-efficient Cloud Task Scheduling Research based on Dynamic Genetic Algorithm

ZHONG Xiaorou， ZHAI Jianhong

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract： The rapid development of cloud computing has led to the establishment of large-scale data centers. Such data centers consume enormous amounts of electric energy results in high operating cost and carbon dioxide emissions. With the aid of traditional genetic algorithm， the paper presents a new multi-objective dynamic scheduling algorithm， which considers cloud environment dynamics and reduces total execution time and power consumption. The new algorithm assigns the jobs to the resources according to the job length and resources capacities. After that， the paper evaluates this algorithm with some famous cloud scheduling algorithm， and the experiments show the efficiency of the proposed approach in terms of execution time， power consumption in cloud environment.

Key words： Cloud Computing Scheduling； Energy-efficient； Genetic Algorithm

0 引 言

云計算是分布式計算、網格計算、效用計算和自主計算發展融合的技術研究成果[1]。在云計算中，用戶不必感知服務處于基礎設施的哪一部分，只需通過云基礎設施范式來使用服務并支付相關服務的費用。云基礎設施即根據“按需付費”的原則向用戶提供共享的資源及服務。

調度算法主要用來減少任務的執行時間以及執行消耗[2]。具體來說，算法中的調度旨在處理如何將資源合理分配給任務的問題。一個好的調度算法應該考慮到系統的負載平衡以及可用資源的總執行時間。調度器則應根據任務長度以及資源計算能力來為任務分配資源[3]。

近年來，在云任務調度領域，一些智能方法的使用引起了多方的高度關注。其中，遺傳

算法就是一個著名的人工智能方法。傳統的遺傳算法模擬生物進化的過程，由一系列染色體組成的種群開始，通過選擇、交叉、變異操作，逐步選擇適應度高的個體以求得最優解[4]。基于此，本文充分考慮任務的動態特點[5]，并設定多個優化目標，提出了一種新型的多目標動態遺傳算法調度策略， 同時運用了CloudSim-3.0仿真工具，切通過與CloudSim自帶調度算法的對照比較，驗證了本文所提出的算法在動態環境中的有效性。

1 模型建立

1.1 任務期望完成時間模型

通過分析CloudSim自帶的樣例程序可得，CloudSim默認一個任務所需的執行時間等于任務的指令長度除以處理該任務的虛擬機的執行速度。

根據上述結論，定義一個矩陣time[i][j]，表示任務j在虛擬機i上所需的執行時間，顯然time[i][j]=MI[j]/MIPS[i]。在初始化矩陣time前，首先將任務按照MI的大小降序排列，而將虛擬機按MIPS的大小升序排列，重新排序后矩陣time的行號和任務id不再一一對應，列號和虛擬機id的對應關系也隨之改變。初始化后，矩陣time的每一行、每一列的元素值都是降序排列的，而后即以time為一個優化目標做遺傳選擇。這一方式的最終結果表明：任務越復雜，利用更快的虛擬機進行處理的需求就越發明確，以解決復雜任務造成的瓶頸，從而降低所有任務的總執行時間。

1.2 基礎設施能耗模型

近年來，一些研究工作[6]表明服務器的能量消耗和CPU利用率之間可準確表述為一種線性關系。不同類型的處理器，線性關系也有所不同。設當前動態環境中有 臺虛擬機，運行時間是離散的且可以分割為N個時間塊，每個時間塊是1秒，當前總能耗設為 ， 為第j臺虛擬機的當前狀態，則：

（1）

（2）

其中， 是虛擬機處于空閑狀態時的最小能耗， 是負載處于峰值時的最大能耗，Utilization則指虛擬機當前的資源利用率。資源提供者會根據物理機的總能耗實行付費。該基礎設施的總能耗計算如下所示：

（3）

其中， 是時間序列。主機的資源計算能力以及虛擬機的資源利用率的特征則由CPU性能而決定并優化。

1.3 動態性能模型

在靜態環境中，資源以及任務是事先可預知的。而在動態環境中，資源和任務可能隨時增減。因此，提前設計固定的性能指標并不適用于動態環境，為此動態CloudSim可用計算單元（compute unit）來衡量虛擬機資源。不同的主機的計算單元可以提供不同數量的計算能力。本動態模型使用指數分布模擬性能改變，用戶根據每小時發生的狀態變化平均數給出一個速率參數來決定下一個性能改變來臨的時間間隔。由指數分布決定的性能改變是隨機且無記憶性的，因為對任意隨機參數T都遵循如下關系：

（4）

概率密度函數如下：

（5）

其中，λ是單位時間單元內發生狀態變化的次數。

2 多適應度的動態遺傳調度算法

2.1 染色體編碼與解碼

染色體用來定義遺傳算法嘗試解決問題的各種可能答案。本課題采用資源--任務的間接編碼方式。染色體的長度為任務的數量，染色體中的每個基因的取值為該位置號對應的任務分配到資源上的具體編號。設有M個用戶，N個資源，第t個用戶提交的任務數量為：cloudletNum（t）。則任務的總數量CloudletNum為：

（6）

綜上可知，根據任務順序對這些任務進行編號，即第i個用戶提交的第j個Cloudlet的序號m為：

（7）

2.2 適應度函數

在遺傳算法中，適應度函數用于評價個體的優劣程度，根據適應度對個體進行選擇，可以保證適應性能較好的個體將有更多的可能繁殖后代，即使優良特性得以遺傳。本課題考慮兩個優化目標：任務的完成時間和基礎設施的能量消耗，故設定適應度函數如下：

設當前種群集合為 ，種群中每個染色體 代表一種可行的調度方案，基于該調度方案執行所有任務所需的時間為 ， 可根據具體調度方案依照時間矩陣 求得。為此當前種群中全部染色體所需的完成任務的總時間函數可表述為：

（8）

當前種群中，第i個染色體的適應度函數為：

（9）

根據1.2提出的能耗模型計算可得到能耗矩陣EEC。具體計算則如式（10）和（11）所示：

（10）

（11）

其中， 表示任務分配序列為x的染色體對應的基礎施設能量消耗， 表示種群總能耗。故染色體x的能耗適應度函數為：

（12）

綜合考慮時間消耗以及能量消耗，本研究提出加權的雙適應度改進遺傳算法，加權雙適應度函數如下：

（13）

其中， 和 分別為時間消耗和能量消耗的權重，且 。

2.3初始種群生成

設種群規模為SCALE，任務總數為m，資源數為N，則種群初始化可描述為：由系統隨機產生SCALE個染色體，染色體長度為m，基因的取值范圍[1，N]，可在此范圍中隨機取值。

為了符合云計算環境的動態特點，還需做出如下改進：

（1）服務器的增減：計算節點離開，則資源狀態不可用，從染色體中刪除該資源占用的基因位；計算節點加入，狀態由不可用變為可用，在當前染色體中加入新的基因位。

（2）新任務的加入：在當前任務調度完成，占用主機資源執行，有新任務加入時，采用繼承思想調度策略。繼承思想是指當函數從 轉變為 時，函數 收斂得到的最優種群pop-1將保留下來作為函數 的初始種群進行動態尋優，從而得到新的最優種群pop-2。

2.4 選擇、交叉和變異算子

選擇算子是遺傳算法對個體適應度的評價方式，也是實現種群優良基因繼承的基本方式，具體方法是：分別計算種群中每一個體的適應度，選出適應度較高的個體遺傳至子類。

Srinivas[7]等人提出了一種自適應遺傳算法（Adaptive GA，AGA），該算法可根據種群的進化情況來動態地調整交叉概率Pc和變異概率Pm，以達到克服過早收斂及加快搜索速度的目的，根據其原理，建立表達式如下：

（14）

其中， 、 、 、 是（0，1）區間的常數，具體取值根據實際情況而定， 為群體中最大適應度值， 為每代群體平均適應度值， 為要交叉的兩條個體中較大的適應度值，f為要變異個體的適應度值，分別計算每兩條個體的 和 ，并用其中較大值作為最終的 。交叉算子具體步驟如下：

Step 1：將m條個體兩兩分成[m/2]組，作為交叉父代；

Step 2：根據公式（14）確定最終的交叉概率 ；

Step 3：對于每一組交叉父代，分別產生一個隨機數 ，0< <1；

Step 4：若 ：子代個體用父代個體代替

Step 5：若 ：

Step 6：在[0，m]區間產生隨機數 作為交叉位置，m為染色體長度；

Step 7：根據遺傳交叉算子計算產生后代；

Step 8：重復step3-7，直到遍歷所有染色體組。

由于采用浮點數編碼而非二進制編碼，交換之后，還需消除其中重復的基因，避免生成無效染色體，具體方法如下：查找新生成的任務序列中是否有重復的元素，若有，則用還未在該順序表中出現的任務序號替換重復出現的第一個位置元素。

變異運算，指個體染色體編碼串中某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。為避免產生無效染色體，本課題采用插入變異算子，即在當前染色體中選取兩個基因座，并將其中的一個基因座插入到另一個基因座之后或之前。

2.5 再選擇策略

在處理大數據時，遺傳算法龐大的種群規模以及較高的迭代循環次數均將造成極大的內存和時間消耗。所以，選擇遺傳算法用于調度實現時，其研究重心就是盡可能地減少迭代次數，并盡可能快地達到最優解。基于此一目的，本文將采用再選擇策略，即將選擇運算得到的種群和交叉變異得到的種群，各自選擇最優秀的那一半個體進行組合，從而得到一個新的種群，如此即保證了優秀個體在交叉變異后流失數量的降低。具體執行步驟如下：

Step 1：選擇運算得到的種群1和交叉變異得到的種群2分為兩組；

Step 2：計算每一個體的適應度值；

Step 3：對種群1使用冒泡排序法得到適應度值由大到小的排列；

Step 4：對種群2使用冒泡排序法得到適應度值由大到小的排列；

Step 5：在種群1和種群2中各自擇取最優的一半，組成優勢種群。

3 實驗結果分析

本研究采用CloudSim-3.0仿真工具。CloudSim-3.0仿真機制默認“先綁定，再執行”的一套流程：在仿真準備階段，用戶向數據中心代理提交環境配置信息（HOST配置、VM配置、Cloudlet配置等）以及Cloudlet調度策略等信息，并由數據中心代理按照用戶要求的調度策略提前將云任務綁定到相應的虛擬機，而后各個虛擬機統一開始執行云任務。

CloudSim仿真時默認的Cloudlet分配策略是順序分配，這種方法盡量保證了每個虛擬機運行相同數量的任務即平攤負載，但卻未能考慮到任務的需求及虛擬機之間的差別。而貪心算法則考慮到了虛擬機以及任務之間的差異，為此通過優化負載平衡以達到減小任務執行時間的目的。本組實驗配置環境信息具體表述如1所示。

表1 實驗環境配置

Tab.1 experiment configuration

數據中心 物理機配置 虛擬機配置

CPU 2 000MIPs 500-2 000MIPs

RAM 2 048MB 2 048MB

STORAGE 100 000MB 10 000MB

BANDWIDTH 500-1 000M 500-1 000M

調度策略 TimeShared SpaceShared

任務配置 單核CPU，長度5 000-25 000MI

任務數量 {10，100，200，300，，400，500，600，700，800，900，1 000}

虛擬機數量 50

數據中心數量 1

主機數量 20

圖1是數量分別為{100，200，300，400，500，600，700，800，900，1 000}的十組實驗的對比結果，橫軸為任務集序號，縱軸為總執行時間。由圖1可以看出，貪心算法和本課題提出的多適應度動態遺傳算法要顯著優于順序調度方法，且隨著任務數量的增加，本課題提出的多適應度動態遺傳算法在減少執行時間方面的優勢則愈加明顯。

圖2為基于三種調度算法的基礎設施能耗對比結果。由圖2可以看出，在三種算法中，本課題提出的DGA算法消耗的能量普遍最小，且隨著任務數量的增多，其節能優勢也愈加突出。

圖1 執行時間對比結果

Fig.1 Execution time comparison

圖2 能量消耗對比結果

Fig.2 Power consumption comparison

4 結束語

為了解決動態云環境中節能調度的問題，本文提出了一種多適應度的動態節能的改進遺傳調度算法，該算法充分考慮云環境的動態性，并綜合設定了任務的執行時間以及基礎設施的能量消耗多個優化目標。實驗表明本文的調度算法可有效應用于云計算環境，并在減少任務執行時間以及能耗方面具有相當優勢，并且該優勢還將隨著任務數量的增加而更加突顯。

參考文獻：

[1] ARMBRUSTM， FOX A， GRIFFITHR， etal. Above the Clouds： A Berkeley view of cloud computing. http：//www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.pdf . 2010.

[2] Buyya R， Beloglazov A， Abawajy J. Energy-efficient management of data center resources for cloud computing： A vision， architectural elements， and open challenges[C]//Proc of the 2010 Int Conf on Parallel and Distributed Processing Techniques and Applications， Las Vegas， USA： PDPTA， 2010：1-12.

[3] MEZMAZ M， MELAB N， KESSACI Y， et al. A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems[J]. Journal of Parallel and Distributed Computing， 2011，71（11）：1497-1508.

[4] AII S， SAIT S M， BENTON M S T. GSA： Scheduling and allocation using Genetic Algorithm[C]// Proc.EURO-DAC '94， Grenoble， France： IEEE Computer Society， 1994： 84-89.

[5] LI K. Performance analysis of power-aware Task scheduling algorithms on multiprocessor computers with dynamic voltage and speed[J].IEEE Trans on Parallel and Distributed Systems，2008，19（11）：1484-1497.

[6] KUSIC D， KEPHART J O， HANSON J E， et al. Power and performance management of virtualized computing environments via lookahead control[J]. Cluster Computing ，2009， 12（1）：1-15.

[7] SRINVAS M， PATNAIK L M. Adaptive probabilities of crossover and mutation in Genetic Algorithm for the electrical districting problem[J]. Annals of Operations Research，2003（121）：33-35.