基于自適應(yīng)遺傳算法的云計(jì)算數(shù)據(jù)中心能耗最小化規(guī)劃模型

姜春磊 史曉杰

1、煙臺(tái)黃金職業(yè)學(xué)院信息工程系 2、山東金寶電子股份有限公司

1 介紹

云計(jì)算提供商在保證高質(zhì)量服務(wù)和客戶(hù)滿(mǎn)意度的同時(shí)，數(shù)據(jù)中心的能耗降低變得異常重要。云計(jì)算利用虛擬化技術(shù)來(lái)實(shí)現(xiàn)更好的資源利用率，并提供動(dòng)態(tài)整合虛擬機(jī)和在計(jì)算資源上實(shí)時(shí)遷移虛擬機(jī)的能力。通過(guò)需求預(yù)測(cè)、熱量管理和溫度感知分配、在服務(wù)器不使用時(shí)關(guān)閉服務(wù)器進(jìn)行動(dòng)態(tài)電源管理等方式以最小化物理計(jì)算資源的功率水平，解決負(fù)載平衡和任務(wù)調(diào)度以最小化云計(jì)算環(huán)境中的能量消耗[1]。

有效的調(diào)度是在特定的時(shí)間將云端用戶(hù)的請(qǐng)求分配給云數(shù)據(jù)中心內(nèi)的可用資源，滿(mǎn)足用戶(hù)的需求，并將一段時(shí)間內(nèi)的總體功耗最小化。此時(shí)，將任務(wù)調(diào)度到云數(shù)據(jù)中心的物理/虛擬資源需要考慮任務(wù)負(fù)載及其需求。除了計(jì)算和存儲(chǔ)的功耗之外，在將任務(wù)分配給物理資源時(shí)，網(wǎng)絡(luò)資源對(duì)性能和功耗都有影響。本文提出了一種用于云數(shù)據(jù)中心動(dòng)態(tài)任務(wù)調(diào)度的自適應(yīng)遺傳算法，旨在開(kāi)發(fā)一個(gè)模型和一個(gè)算法，通過(guò)將傳入的任務(wù)調(diào)度到資源中，以滿(mǎn)足用戶(hù)的需求，并使云數(shù)據(jù)中心的能耗最小化，從而最小化云計(jì)算基礎(chǔ)設(shè)施中的能耗。

2 分析

具有不同參數(shù)和特征的云計(jì)算任務(wù)調(diào)度算法，可以實(shí)現(xiàn)特定的目標(biāo)。例如一種任務(wù)調(diào)度策略，假設(shè)多個(gè)獨(dú)立的任務(wù)組成一個(gè)單一的任務(wù)，在該策略中，數(shù)據(jù)中心由異構(gòu)計(jì)算服務(wù)器集群組成[2]。每個(gè)任務(wù)都有許多操作和已知的順序，可以在一臺(tái)機(jī)器上處理，云節(jié)點(diǎn)一次處理一個(gè)操作。云由多個(gè)服務(wù)提供商組成，每個(gè)服務(wù)提供商管理多個(gè)數(shù)據(jù)中心。遺傳算法已被廣泛用于云計(jì)算中任務(wù)調(diào)度問(wèn)題，對(duì)于云環(huán)境下的能源消耗，使用一個(gè)中央調(diào)度器將任務(wù)分配給服務(wù)器，以最小化服務(wù)器處理時(shí)間，進(jìn)而最小化總能量。

負(fù)載平衡是云計(jì)算中用于最小化能耗的另一種技術(shù)，提出了一種基于優(yōu)先級(jí)的搶占式作業(yè)調(diào)度算法，用于負(fù)載管理，最小化能耗，最大化收益。利用遺傳算法對(duì)云環(huán)境下可用資源和能量消耗的任務(wù)進(jìn)行調(diào)度，該方法通過(guò)最小化云數(shù)據(jù)中心的制造時(shí)間和能耗來(lái)實(shí)現(xiàn)。工作集中在靜態(tài)調(diào)度和特定類(lèi)型的計(jì)算資源，以及這些資源消耗的功率，沒(méi)有考慮其他資源類(lèi)型對(duì)能耗的影響。本文提出了一種自適應(yīng)遺傳算法，它考慮了云計(jì)算中調(diào)度問(wèn)題的動(dòng)態(tài)特性。

3 云計(jì)算環(huán)境分析與模型

云計(jì)算環(huán)境由消費(fèi)者和服務(wù)者兩種類(lèi)型的實(shí)體組成，云提供商是提供要使用的資源或服務(wù)的實(shí)體，云消費(fèi)者是使用云提供商提供的資源或服務(wù)的實(shí)體。云物理計(jì)算資源根據(jù)處理器架構(gòu)、處理器速度、內(nèi)核數(shù)量和內(nèi)存容量進(jìn)行分類(lèi)，可以基于存儲(chǔ)類(lèi)型、存儲(chǔ)容量和速度來(lái)表征存儲(chǔ)資源[3]。

云計(jì)算中任務(wù)以百萬(wàn)條指令為單位的大小；優(yōu)先級(jí)指時(shí)間元素，包含到達(dá)時(shí)間、開(kāi)始時(shí)間、等待時(shí)間和截止時(shí)間；任務(wù)之間的依賴(lài)關(guān)系；任務(wù)調(diào)度搶占。云環(huán)境可以由一個(gè)或多個(gè)服務(wù)提供商管理的單個(gè)或多個(gè)數(shù)據(jù)中心組成，最小化能耗的重點(diǎn)是將一個(gè)云計(jì)算環(huán)境由一個(gè)數(shù)據(jù)中心組成，同時(shí)由一個(gè)服務(wù)提供商擁有。

3.1 云提供商

云提供商負(fù)責(zé)云計(jì)算環(huán)境，它由N個(gè)數(shù)據(jù)中心（DC）組成，其中每個(gè)數(shù)據(jù)中心包含一組資源（R）。

3.2 云消費(fèi)者

來(lái)自消費(fèi)者的任務(wù)可由不同任務(wù)（Tq）組成，每個(gè)任務(wù)可以有不同的能耗和進(jìn)度。

3.3 環(huán)境設(shè)置

云計(jì)算中的調(diào)度問(wèn)題是基于以下假設(shè)建模的：虛擬化用于從物理資源創(chuàng)建多個(gè)實(shí)例；每個(gè)資源（計(jì)算或存儲(chǔ)）可以執(zhí)行多個(gè)任務(wù)；一個(gè)任務(wù)只能由一個(gè)資源執(zhí)行；不搶占任務(wù)（即任務(wù)不能被中斷）；資源的功耗取決于分配給它們的任務(wù)[4]。

消費(fèi)者向云端提交請(qǐng)求，這些請(qǐng)求表示為任務(wù)（即，一個(gè)請(qǐng)求可以由多個(gè)任務(wù)組成），并提交給具有任務(wù)工作流的云編排。資源管理器擁有用于調(diào)度決策的物理和虛擬資源，調(diào)度器基于最小化能量消耗的目標(biāo)，根據(jù)所請(qǐng)求的能力搜索能夠執(zhí)行任務(wù)的資源到可用的能耗資源。調(diào)度器必須考慮所有約束，調(diào)度問(wèn)題可以映射為一個(gè)優(yōu)化問(wèn)題，在這個(gè)優(yōu)化問(wèn)題中，必須做出最小化或最大化目標(biāo)值的最優(yōu)決策。所有的優(yōu)化問(wèn)題都有一個(gè)目標(biāo)函數(shù)來(lái)說(shuō)明要最小化或最大化的值和一組約束條件，這些約束條件約束了問(wèn)題的可能性。在這項(xiàng)工作中，本文提出了一個(gè)整數(shù)線(xiàn)性規(guī)劃模型的問(wèn)題，以盡量減少能源消耗。

3.4 問(wèn)題表述

本文算法關(guān)注執(zhí)行計(jì)劃任務(wù)時(shí)計(jì)算資源消耗的總功率，目標(biāo)函數(shù)考慮了整個(gè)調(diào)度過(guò)程中存儲(chǔ)資源、網(wǎng)絡(luò)資源和冷卻系統(tǒng)的總功耗。計(jì)算資源消耗的總功率隨資源利用率的變化而變化，可使用公式（3）進(jìn)行估算：

模型的優(yōu)化問(wèn)題受條件約束，確保任務(wù)請(qǐng)求的計(jì)算規(guī)格（內(nèi)核數(shù)、CPU速度、內(nèi)存容量和處理器體系結(jié)構(gòu)）在獲得的解決方案中得到滿(mǎn)足。例如，請(qǐng)求具有6個(gè)內(nèi)核和128GB內(nèi)存的虛擬機(jī)（VM）的任務(wù)不能分配給另一個(gè)規(guī)格較低的VM。另外，當(dāng)任務(wù)需要存儲(chǔ)資源時(shí)，該模型在約束中保證它們的需求不會(huì)被違反。因此，不能將任務(wù)分配給存儲(chǔ)容量、存儲(chǔ)類(lèi)型和速度低于請(qǐng)求的資源（即存儲(chǔ)服務(wù)器），確保滿(mǎn)足所需的網(wǎng)絡(luò)帶寬。確保每個(gè)任務(wù)僅由一個(gè)計(jì)算、存儲(chǔ)或網(wǎng)絡(luò)資源執(zhí)行。也即，一個(gè)任務(wù)的執(zhí)行不能在同一類(lèi)型的兩個(gè)資源之間劃分，每個(gè)任務(wù)的開(kāi)始時(shí)間和執(zhí)行時(shí)間滿(mǎn)足截止日期。此外，一個(gè)資源不能在特定的時(shí)間框架內(nèi)執(zhí)行兩個(gè)不同的任務(wù)，確保資源可以在結(jié)束前一個(gè)任務(wù)的執(zhí)行之后開(kāi)始執(zhí)行其中一個(gè)任務(wù)。

4 遺傳算法

本文提出了一種自適應(yīng)遺傳算法來(lái)解決給出的環(huán)境動(dòng)態(tài)特性下的問(wèn)題,所提出的算法從可能染色體的初始種群開(kāi)始，通過(guò)選擇以及交叉和變異復(fù)制算子來(lái)搜索最優(yōu)（或接近最優(yōu)）解。除了適當(dāng)?shù)娜旧w編碼和為所考慮的問(wèn)題專(zhuān)門(mén)設(shè)計(jì)的交叉算子外，我們的遺傳算法還與一個(gè)程序雜交，確定染色體（可能的解決方案）是否可行，如果不可行，染色體被相應(yīng)地懲罰，以減少選擇（或存活）的可能性。自適應(yīng)遺傳算法利用問(wèn)題的前一個(gè)解決方案（調(diào)度）和新的任務(wù)集來(lái)搜索解決方案，使其能夠在動(dòng)態(tài)調(diào)度范式下工作。一組初始任務(wù)的輸入，并從生成染色體或個(gè)體的初始群體開(kāi)始，每個(gè)染色體（或個(gè)體）代表優(yōu)化問(wèn)題的可能解。因此，染色體是一個(gè)基因載體，代表著可能的資源分配任務(wù)。

兩個(gè)連續(xù)的基因代表一個(gè)任務(wù)，后面是分配給這個(gè)任務(wù)的資源。根據(jù)優(yōu)化模型的目標(biāo)函數(shù)，評(píng)估每個(gè)染色體的適合度。然后選擇當(dāng)前群體的最佳染色體進(jìn)行交叉和變異（繁殖），產(chǎn)生新的后代群體。檢查新后代群體的每個(gè)個(gè)體，以確定其是否是問(wèn)題的可行解決方案，即滿(mǎn)足給定的約束條件。不可行的個(gè)體會(huì)受到懲罰，增加他們的適應(yīng)值，這樣他們就不太可能被選擇繁殖，所有創(chuàng)造的種群的個(gè)體樣本都得到了保存。重復(fù)該過(guò)程，直到滿(mǎn)足終止標(biāo)準(zhǔn)。

該算法首先確定接收到的初始任務(wù)集的時(shí)間表,自適應(yīng)遺傳算法在任務(wù)到達(dá)時(shí)處理任務(wù)。每當(dāng)一組新的任務(wù)到達(dá)并且在初始化階段之前，該算法就遍歷接收到的任務(wù)，并根據(jù)請(qǐng)求的能力和可用的資源能力構(gòu)建一個(gè)包含能夠執(zhí)行每個(gè)任務(wù)的所有資源的列表。對(duì)于人口的每個(gè)可能染色體，表示總能量消耗的適應(yīng)度函數(shù)計(jì)算為在特定時(shí)間執(zhí)行染色體中計(jì)劃的任務(wù)時(shí)每個(gè)資源消耗的功率之和。算法首先確定每個(gè)資源開(kāi)始執(zhí)行計(jì)劃給它的任務(wù)的時(shí)間,這個(gè)時(shí)間，即開(kāi)始時(shí)間，取決于上一個(gè)計(jì)劃和當(dāng)前計(jì)劃。如果當(dāng)前計(jì)劃中的一個(gè)資源被分配了兩個(gè)任務(wù)，一個(gè)在上一個(gè)計(jì)劃中，一個(gè)在當(dāng)前計(jì)劃中，則此資源應(yīng)該在執(zhí)行上一個(gè)計(jì)劃中的任務(wù)之后開(kāi)始執(zhí)行當(dāng)前計(jì)劃中的任務(wù)。如果上一個(gè)計(jì)劃中的一個(gè)或多個(gè)任務(wù)需要重新計(jì)劃，即除非收到新的任務(wù)集進(jìn)行計(jì)劃，否則它們不會(huì)開(kāi)始執(zhí)行，則必須釋放這些任務(wù)的資源，因此必須重新計(jì)劃它們的開(kāi)始時(shí)間。

云環(huán)境是動(dòng)態(tài)的，其中的任務(wù)預(yù)先是不知道的。在實(shí)驗(yàn)環(huán)境中，任務(wù)到達(dá)遵循隨機(jī)分布[5]。自適應(yīng)遺傳算法根據(jù)正態(tài)分布等待一段時(shí)間，直到新任務(wù)到達(dá)，然后考慮到舊的調(diào)度和新任務(wù)集的截止時(shí)間，開(kāi)始尋找能量消耗最小的調(diào)度，新的任務(wù)集包括新到達(dá)的任務(wù)和舊計(jì)劃中在新任務(wù)到達(dá)之前未開(kāi)始執(zhí)行的任務(wù)。

5 遺傳算法參數(shù)

由于遺傳算法是不確定的，遺傳參數(shù)不僅影響算法的運(yùn)行時(shí)間，而且影響最優(yōu)算法的質(zhì)量。因此，針對(duì)自適應(yīng)遺傳算法進(jìn)行了實(shí)驗(yàn)，以確定適當(dāng)?shù)姆N群規(guī)模，從而獲得更好的適應(yīng)性。同時(shí)，為了對(duì)不同數(shù)量的任務(wù)和資源進(jìn)行實(shí)驗(yàn)，我們將問(wèn)題規(guī)模進(jìn)行分類(lèi)。

當(dāng)群體規(guī)模較小時(shí)，三種問(wèn)題規(guī)模的自適應(yīng)遺傳算法具有較高的適應(yīng)性，但當(dāng)群體規(guī)模增大時(shí)，適應(yīng)性開(kāi)始下降。當(dāng)種群規(guī)模很大時(shí)，得到最佳解。種群規(guī)模的增加使算法有機(jī)會(huì)得到更好的解決方案，實(shí)現(xiàn)能量較少的調(diào)度。對(duì)于同一批任務(wù)，這些個(gè)體將包含更多的資源選項(xiàng)來(lái)執(zhí)行它們，增加了可行的解決方案的數(shù)量和使能源消耗最小化的解決方案的數(shù)量。

影響遺傳算法獲得的解的質(zhì)量的另一個(gè)因素是代數(shù)，決定了算法何時(shí)收斂，即在算法給出最佳調(diào)度之前產(chǎn)生新后代的代數(shù)。通過(guò)對(duì)三個(gè)問(wèn)題規(guī)模和一定數(shù)量群體規(guī)模進(jìn)行了實(shí)驗(yàn)，以確定最佳適應(yīng)性遺傳算法的世代數(shù)。

6 結(jié)果

為了評(píng)估所提出的自適應(yīng)遺傳算法的性能，我們將其與非能量感知調(diào)度算法先到先服務(wù)進(jìn)行了比較。對(duì)動(dòng)態(tài)云環(huán)境，兩種算法都是在任務(wù)批量到達(dá)時(shí)進(jìn)行調(diào)度，任務(wù)到達(dá)服從隨機(jī)分布。

我們一次系統(tǒng)地改變一個(gè)輸入?yún)?shù)，以評(píng)估它們對(duì)目標(biāo)函數(shù)值的影響。已更改的輸入?yún)?shù)是任務(wù)數(shù)、資源數(shù)和資源類(lèi)型，以跟蹤它們對(duì)能源消耗量的影響。資源數(shù)量的增加對(duì)自適應(yīng)算法調(diào)度所有任務(wù)所用的總時(shí)間有顯著影響，自適應(yīng)遺傳算法的總時(shí)間隨著資源數(shù)量的增加而增加。

7 結(jié)論

在一個(gè)數(shù)據(jù)中心和一個(gè)服務(wù)提供商擁有的動(dòng)態(tài)云環(huán)境中，任務(wù)調(diào)度問(wèn)題目標(biāo)是使云計(jì)算基礎(chǔ)設(shè)施的能耗最小化。該模型將計(jì)算資源、存儲(chǔ)資源、網(wǎng)絡(luò)資源和冷卻系統(tǒng)視為云環(huán)境中消耗能量的實(shí)體，對(duì)云環(huán)境的動(dòng)態(tài)調(diào)度特性，采用批處理策略。自適應(yīng)遺傳算法具備有效性，為每個(gè)問(wèn)題大小提供了最小的能量消耗。云環(huán)境中優(yōu)化能源消耗時(shí)考慮所有資源（計(jì)算、存儲(chǔ)、網(wǎng)絡(luò)資源和冷卻系統(tǒng)）的重要性，研究方向可以是針對(duì)單一供應(yīng)商擁有的分布式數(shù)據(jù)中心和不同供應(yīng)商擁有的分散數(shù)據(jù)中心的能源動(dòng)態(tài)調(diào)度決策。