姜 凱

(聊城大學(xué) 東昌學(xué)院 ，山東 聊城 252000)

基于離散和聲搜索的云計算任務(wù)調(diào)度研究

姜 凱

(聊城大學(xué) 東昌學(xué)院 ，山東 聊城 252000)

云計算任務(wù)調(diào)度是云計算最重要的問題之一。為解決云計算調(diào)度問題，提出一種基于改進和聲搜索的調(diào)度算法。該算法采用離散形式編碼，以總的任務(wù)完成時間為優(yōu)化目標(biāo)，并對標(biāo)準(zhǔn)和聲搜索算法中新和聲產(chǎn)生方式進行了改進。最后，在CloudSim平臺上進行了仿真實驗。實驗結(jié)果表明，新提出的算法具有較好的調(diào)度性能。

云計算；任務(wù)調(diào)度；離散和聲搜索算法

0 引言

云計算的概念自2007年提出以來，迅速受到產(chǎn)業(yè)界和學(xué)術(shù)界的高度關(guān)注。以Google、Amazon、IBM和微軟為代表的IT巨頭紛紛推出自己的云計算產(chǎn)品。與此同時，許多國際學(xué)術(shù)會議也將云計算作為重要的討論話題。作為一種成功的商業(yè)計算服務(wù)模式，云計算能夠?qū)⒂嬎闳蝿?wù)分布在大量由計算機構(gòu)成的資源池上，使得用戶能夠通過按需租用的方式獲取其提供的計算力、存儲空間和信息服務(wù)[1]。這些虛擬計算資源通常是一些大型服務(wù)器集群，包括計算服務(wù)器、存儲服務(wù)器和寬帶資源等[2]。當(dāng)用戶需要使用某些資源時，可以動態(tài)地向云計算系統(tǒng)提出申請，以支持各種應(yīng)用程序的運轉(zhuǎn)。在收到任務(wù)請求后，系統(tǒng)調(diào)度中心要及時分配資源。通常情況下，云計算的用戶數(shù)量非常大，且系統(tǒng)本身是動態(tài)的、異構(gòu)的。因此，如何設(shè)計一個高效的任務(wù)調(diào)度算法，既能夠滿足用戶的要求，又使得運行成本最小，成為云計算系統(tǒng)的核心問題之一。

云計算任務(wù)調(diào)度本質(zhì)上是一個組合優(yōu)化問題。對于該類問題，很多研究學(xué)者采用啟發(fā)式方法進行求解，取得了不錯的結(jié)果。文獻[3]利用離散粒子群結(jié)合模擬退火算法解決云調(diào)度問題，以降低總的綜合執(zhí)行成本為目標(biāo)，提出一種混合算法，取得了不錯的結(jié)果。文獻[4]則將遺傳算法和蟻群優(yōu)化算法結(jié)合起來，提出一種基于多群智能算法的云計算任務(wù)調(diào)度策略。而文獻[5]則提出一種多目標(biāo)優(yōu)化調(diào)度策略，試圖同時滿足多個資源調(diào)度優(yōu)化目標(biāo)。

和聲搜索算法(Harmony Search，HS)是新近提出的一種啟發(fā)式優(yōu)化算法。該算法的結(jié)構(gòu)比較簡單，而且容易實現(xiàn)，在多維函數(shù)優(yōu)化、車間調(diào)度等問題中取得了較好的結(jié)果，已經(jīng)成為智能優(yōu)化算法領(lǐng)域的又一個研究熱點。

目前，和聲搜索算法還沒有被應(yīng)用到云計算任務(wù)調(diào)度問題。因此，本文嘗試將改進的和聲搜索算法應(yīng)用于云計算任務(wù)調(diào)度問題，并通過實驗來驗證該算法調(diào)度性能。

1 云計算任務(wù)調(diào)度問題的數(shù)學(xué)模型

在云計算環(huán)境下，用戶是以按需租用的形式使用系統(tǒng)資源的。一般來說，在保證資源得到充分利用的前提下，任務(wù)處理時間越短越好，這樣用戶需要支付的費用就越少，得到的服務(wù)質(zhì)量也就越高。在云計算系統(tǒng)中，用戶數(shù)量大大多于虛擬計算資源數(shù)，如果沒有合理的調(diào)度方案，很容易產(chǎn)生死鎖，造成系統(tǒng)利用率低下。為便于分析問題，將云計算調(diào)度問題抽象為將n個相互獨立的子任務(wù)，分配到m個可用計算資源(即虛擬機)上執(zhí)行(m

(1)

云計算調(diào)度算法的任務(wù)是設(shè)法找到一個調(diào)度方案X，使得總?cè)蝿?wù)完成時間最小。

2 基于離散和聲搜索的云計算任務(wù)調(diào)度算法

2.1 基本和聲搜索算法

和聲搜索算法是Geem等人受音樂家創(chuàng)作過程的啟發(fā)，于2001年提出的一種元啟發(fā)式全局優(yōu)化算法。在該算法中，解空間中的每個解為一個“和聲” ，它實際上是一個N維的實數(shù)矢量。算法首先產(chǎn)生一個規(guī)模為HMS的初始種群，稱為初始的和聲記憶庫(Harmony Memory，HM)。初始種群以隨機的方式產(chǎn)生，產(chǎn)生的所有初始和聲組成和聲記憶庫；接著，和聲搜索算法根據(jù)記憶考慮、微調(diào)擾動、隨機選擇這三個規(guī)則產(chǎn)生一個新的候選解xnew，然后將xnew與HM內(nèi)的最差解進行比較，如果新解優(yōu)于最差解，則進行替換，用這種方式來不斷更新和聲記憶庫。算法不斷進行迭代，直至達(dá)到指定的最大迭代次數(shù)。

2.2 云計算任務(wù)調(diào)度算法的實現(xiàn)

和其他啟發(fā)式算法一樣，和聲搜索算法也是問題依賴的。基本和聲搜索算法采用連續(xù)編碼方式，不能直接用于解決離散優(yōu)化問題。因此，為解決云計算任務(wù)調(diào)度問題，必須對基本和聲搜索算法從和聲編碼、適應(yīng)度函數(shù)定義、算子設(shè)計等多個方面進行改進，使之適合云計算任務(wù)調(diào)度問題。

2.2.1 和聲編碼及其初始化

由于云計算調(diào)度本身是離散優(yōu)化問題，為簡化計算過程，新算法采用“任務(wù)-虛擬機”間接離散編碼方式，即一個和聲的編碼長度為子任務(wù)個數(shù)，每一位編碼的位置代表對應(yīng)的子任務(wù)，每一位編碼的數(shù)值代表分配的虛擬機編號。

假設(shè)要將n個子任務(wù)分配到m個虛擬機上執(zhí)行，則n個子任務(wù)依次編號為0～n-1，m個虛擬機編號依次為0～m-1。如果用長度為n的數(shù)組Xi表示一個和聲，則滿足i∈[0,n-1]且Xi∈[0,m-1]。

例如，要將6個子任務(wù)(T0,T1,T2,T3,T4,T5)分配到4個虛擬機(V0,V1,V2,V3)上執(zhí)行，如果某個個體編碼為[2,1,0,3,2,3]，則表示子任務(wù)T2分配給虛擬機V0，子任務(wù)T1分配給虛擬機V1，子任務(wù)T0和T4分配給虛擬機V2，子任務(wù)T3和T5分配給虛擬機V3。在此基礎(chǔ)上，很容易就可以求出總?cè)蝿?wù)完成時間。

和聲庫的規(guī)模為HMS，算法在初始化時，首先按照上述規(guī)律隨機生成一個長度為n的和聲，然后重復(fù)進行HMS次，得到一個HMS×n矩陣，組成初始和聲記憶庫。

2.2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是優(yōu)化的目標(biāo)，和聲搜索算法正是以適應(yīng)度函數(shù)為目標(biāo)函數(shù)，在解空間中不斷迭代尋找最優(yōu)解，并以此為依據(jù)來對種群中的個體進行評價。因此，適應(yīng)度函數(shù)的選擇對于利用好和聲搜索算法至關(guān)重要?？紤]到計算的復(fù)雜性，新算法以公式(1)作為適應(yīng)度函數(shù)。

2.2.3 新和聲的產(chǎn)生

產(chǎn)生新和聲這一步驟類似于遺傳算法的選擇、交叉和變異操作，是算法的核心，主要目的是產(chǎn)生新的和聲個體，使得種群向著適應(yīng)度函數(shù)值更優(yōu)的方向進化。由于本算法采用離散的編碼，因此要對基本和聲搜索算法進行改進，采用如下方法來產(chǎn)生一個新的和聲向量xnew：

(1)基于記憶考慮和隨機選擇規(guī)則，算法首先在[0,1]之間產(chǎn)生一個隨機數(shù)τ1，如果τ1

(2)按照微調(diào)擾動和隨機選擇規(guī)則，在[0,1]之間產(chǎn)生一個隨機數(shù)τ2，如果τ2

(2)

(3)

上述兩公式中，PAR是算法的聲音調(diào)微調(diào)概率，也是一個預(yù)設(shè)的參數(shù)，τ3和τ4是[0,1]之間的隨機數(shù)。

2.2.4 和聲記憶庫的更新

產(chǎn)生新和聲后，算法隨后要更新和聲記憶庫。更新和聲記憶庫的依據(jù)是適應(yīng)度函數(shù)值的優(yōu)劣，即如果產(chǎn)生的新和聲xnew所對應(yīng)的函數(shù)值優(yōu)于原來和聲記憶庫中函數(shù)值最差的和聲xw所對應(yīng)的適應(yīng)度值,則用新的和聲xnew替換xw，否則不再替換。

綜上所述，新提出的離散和聲搜索調(diào)度算法(記作DHS算法)的步驟如下：

Step1：算法參數(shù)初始化。設(shè)置和聲記憶庫的大小HMS、和聲記憶庫考慮概率HMCR、聲音調(diào)微調(diào)概率PAR以及最大迭代次數(shù)NI等參數(shù)。

Step2：初始化和聲記憶庫。按照2.2.1節(jié)的方法產(chǎn)生初始和聲記憶庫，并使用公式(1)計算每個和聲的適應(yīng)度函數(shù)值。

Step3：產(chǎn)生新的和聲。對和聲記憶庫中的每一個和聲，利用2.2.3節(jié)提出的記憶考慮、微調(diào)擾動、隨機選擇規(guī)則產(chǎn)生新和聲xnew。

Step4：和聲記憶庫更新。將新產(chǎn)生的解xnew與HM內(nèi)的最差解進行比較，如果新解優(yōu)于最差解，則進行替換。

Step5：判斷是否終止。若當(dāng)前迭代次數(shù)達(dá)到NI則終止；否則轉(zhuǎn)向Step3繼續(xù)執(zhí)行。

3 仿真實驗分析

通過仿真實驗評價和分析本文提出的和聲搜索算法DHS的調(diào)度性能。實驗在墨爾本大學(xué)開發(fā)的云計算仿真平臺CloudSim3.0.3上進行。在實驗時，首先對DataCenterBoker類進行擴展，在該類中添加自己編寫的DHS調(diào)度算法的方法，該方法能夠?qū)崿F(xiàn)DHS算法功能，從而完成對DHS調(diào)度算法的模擬。編程時使用的編程語言為Java，開發(fā)環(huán)境為Eclipse4.4.2和JDK1.8。實驗在CPU 為3.4 GHz、內(nèi)存為4 GB、安裝Windows 7操作系統(tǒng)的主機上進行。由于云計算本身是處于動態(tài)和異構(gòu)環(huán)境下的，為了充分驗證算法的性能，本文設(shè)計了如下實驗。

實驗中設(shè)置的虛擬機數(shù)為10，隨機產(chǎn)生50、100、500、1 000、1 500和2 000個任務(wù)進行調(diào)度，旨在考察不同規(guī)模情況下新算法DHS的調(diào)度性能。其中，每個虛擬機的CPU數(shù)量、內(nèi)存大小、MIPS、網(wǎng)絡(luò)帶寬等指標(biāo)由MATLAB隨機生成。為保證實驗具有可比性，前一輪實驗產(chǎn)生的任務(wù)要包含在后一輪實驗的任務(wù)當(dāng)中。對比算法采用輪詢調(diào)度算法(RR)和Min-Min算法。為盡可能減少誤差，保證實驗結(jié)果的準(zhǔn)確性，每次實驗連續(xù)運行20次，取平均值作為實驗數(shù)據(jù)。實驗得到的各種算法的總?cè)蝿?wù)完成時間如圖1所示。

圖1 不同任務(wù)數(shù)量下總?cè)蝿?wù)完成時間

從圖1可以看出，在任務(wù)規(guī)模不大的情況下，由于各個任務(wù)出現(xiàn)資源競爭的可能性較小，發(fā)生沖突的概率也較小，因此各個算法所得到的總?cè)蝿?wù)完成時間差別不大。但是，隨著任務(wù)數(shù)量不斷增大，各個任務(wù)出現(xiàn)資源競爭的情況顯著增多，調(diào)度的復(fù)雜度也急劇升高。這時，新提出的DHS算法顯著優(yōu)于其他算法，其調(diào)度所需要的總的任務(wù)完成時間在三種算法中是最少的。這主要是因為DHS算法具有良好的全局搜索能力，通過不斷迭代，使種群朝著適應(yīng)度值更優(yōu)的方向進化。這說明，本文提出的DHS算法是可行的，能夠在一定程度上處理不同規(guī)模的云計算調(diào)度問題。

4 結(jié)論

一個好的任務(wù)調(diào)度算法能夠顯著提高云計算系統(tǒng)的性能。本文在基本和聲搜索算法的基礎(chǔ)上，從編碼方式、新和聲產(chǎn)生方式等方面對其進行了改進，提出一種基于離散和聲搜索的云計算任務(wù)調(diào)度算法DHS。最后進行了仿真實驗。實驗表明，新提出的DHS算法在處理大規(guī)模任務(wù)時的性能顯著優(yōu)于輪詢、Min-Min等經(jīng)典算法。

[1] 王波,張曉磊.基于粒子群遺傳算法的云計算任務(wù)調(diào)度研究[J].計算機工程與應(yīng)用,2015,51(6):84-88.

[2] 劉鵬.云計算[M] .北京：電子工業(yè)出版社，2011.

[3] 趙軒,蔚承建,王開，等.離散PSO結(jié)合模擬退火算法解決云調(diào)度問題[J] .微電子學(xué)與計算機,2013,30(5):137-140.

[4] 陳海燕.基于多群智能算法的云計算任務(wù)調(diào)度策略[J].計算機科學(xué),2014,41(6A):83-86.

[5] 徐忠勝,沈蘇彬.一種云計算資源的多目標(biāo)優(yōu)化的調(diào)度方法[J].微型機與應(yīng)用,2015,34(13):17-20.

Study on task scheduling in cloud computing based on discrete harmony search

Jiang Kai

(Dongchang College, Liaocheng University,Liaocheng 252000, China)

Task scheduling is one of the most important issues in cloud computing. In order to solve the problem of cloud computing scheduling, a scheduling algorithm based on improved harmony search is proposed. The new algorithm uses the discrete form of encoding and employs the total task completion time as the optimization objective. At the same time, a new harmony generation method is introduced in the proposed algorithm. Finally, a simulation experiment is carried out on the CloudSim platform. Experimental results show that the new algorithm has better scheduling performance.

cloud computing; task scheduling; discrete harmony search

TP393

A

1674- 7720(2016)03- 0021- 03

姜凱．基于離散和聲搜索的云計算任務(wù)調(diào)度研究[J] .微型機與應(yīng)用，2016，35(3)：21- 23.

2015-11-05)

姜凱(1986-)，男，碩士，助教，主要研究方向：智能優(yōu)化、云計算。