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

　　關(guān)鍵詞：云計(jì)算；任務(wù)調(diào)度；離散和聲搜索算法

0引言

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

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

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

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

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

　　在云計(jì)算環(huán)境下，用戶是以按需租用的形式使用系統(tǒng)資源的。一般來說，在保證資源得到充分利用的前提下，任務(wù)處理時(shí)間越短越好，這樣用戶需要支付的費(fèi)用就越少，得到的服務(wù)質(zhì)量也就越高。在云計(jì)算系統(tǒng)中，用戶數(shù)量大大多于虛擬計(jì)算資源數(shù)，如果沒有合理的調(diào)度方案，很容易產(chǎn)生死鎖，造成系統(tǒng)利用率低下。為便于分析問題，將云計(jì)算調(diào)度問題抽象為將n個(gè)相互獨(dú)立的子任務(wù)，分配到m個(gè)可用計(jì)算資源（即虛擬機(jī)）上執(zhí)行（m<n），調(diào)度的目標(biāo)是得到一個(gè)盡可能小的總?cè)蝿?wù)完成時(shí)間。云計(jì)算任務(wù)調(diào)度的數(shù)學(xué)模型描述：（1）用tj(j=1,2,…,n)表示第j個(gè)需要調(diào)度的子任務(wù)，n為任務(wù)數(shù)，各個(gè)子任務(wù)間是相互獨(dú)立的；（2）用vmi(i=1,2,…,m)表示第i個(gè)虛擬機(jī)，m為虛擬機(jī)數(shù)；（3）規(guī)定每個(gè)子任務(wù)只能分配且僅分配給一個(gè)虛擬機(jī)并執(zhí)行；（4）用time(tj,vmi)表示任務(wù)tj在虛擬機(jī)vmi上的執(zhí)行時(shí)間。那么對(duì)于一個(gè)給定的調(diào)度方案X，總?cè)蝿?wù)完成時(shí)間應(yīng)該為：

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

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

　　2.1基本和聲搜索算法

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

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

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

　　2.2.1和聲編碼及其初始化

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

　　假設(shè)要將n個(gè)子任務(wù)分配到m個(gè)虛擬機(jī)上執(zhí)行，則n個(gè)子任務(wù)依次編號(hào)為0~n-1，m個(gè)虛擬機(jī)編號(hào)依次為0~m-1。如果用長(zhǎng)度為n的數(shù)組Xi表示一個(gè)和聲，則滿足i∈［0,n－1］且Xi∈［0,m－1］。

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

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

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

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

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

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

　　（1）基于記憶考慮和隨機(jī)選擇規(guī)則，算法首先在［0,1］之間產(chǎn)生一個(gè)隨機(jī)數(shù)τ1，如果τ1<HMCR，則xnew(j)在HM內(nèi)的記憶空間產(chǎn)生；否則，按照初始化時(shí)的規(guī)則隨機(jī)產(chǎn)生。其中，HMCR為和聲記憶庫(kù)考慮概率，是預(yù)設(shè)的一個(gè)參數(shù)；xnew(j)為xnew的第j維。

　?。?）按照微調(diào)擾動(dòng)和隨機(jī)選擇規(guī)則，在［0,1］之間產(chǎn)生一個(gè)隨機(jī)數(shù)τ2，如果τ2<PAR,則xnew(j)按照公式（2）和（3）進(jìn)行微調(diào)擾動(dòng)：

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

　　2.2.4和聲記憶庫(kù)的更新

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

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

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

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

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

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

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

3仿真實(shí)驗(yàn)分析

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

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

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

4結(jié)論

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

　　參考文獻(xiàn)

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

　?。?］ 劉鵬.云計(jì)算［M］ .北京：電子工業(yè)出版社，2011.

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

　?。?］ 陳海燕.基于多群智能算法的云計(jì)算任務(wù)調(diào)度策略［J］.計(jì)算機(jī)科學(xué),2014,41(6A):8386.

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