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

　　關(guān)鍵詞：云計算；任務(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<n），調(diào)度的目標(biāo)是得到一個盡可能小的總?cè)蝿?wù)完成時間。云計算任務(wù)調(diào)度的數(shù)學(xué)模型描述：（1）用tj(j=1,2,…,n)表示第j個需要調(diào)度的子任務(wù)，n為任務(wù)數(shù)，各個子任務(wù)間是相互獨立的；（2）用vmi(i=1,2,…,m)表示第i個虛擬機，m為虛擬機數(shù)；（3）規(guī)定每個子任務(wù)只能分配且僅分配給一個虛擬機并執(zhí)行；（4）用time(tj,vmi)表示任務(wù)tj在虛擬機vmi上的執(zhí)行時間。那么對于一個給定的調(diào)度方案X，總?cè)蝿?wù)完成時間應(yīng)該為：

　　云計算調(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)于最差解，則進行替換，用這種方式來不斷更新和聲記憶庫。算法不斷進行迭代，直至達到指定的最大迭代次數(shù)。

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

　　和其他啟發(fā)式算法一樣，和聲搜索算法也是問題依賴的?；竞吐曀阉魉惴ú捎眠B續(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：

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

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

　　上述兩公式中，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ù)達到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ù)規(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)典算法。

　　參考文獻

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

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

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

　?。?］ 陳海燕.基于多群智能算法的云計算任務(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.