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

　　關鍵詞：云計算；任務調度；離散和聲搜索算法

0引言

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

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

　　和聲搜索算法(Harmony Search，HS)是新近提出的一種啟發式優化算法。該算法的結構比較簡單，而且容易實現，在多維函數優化、車間調度等問題中取得了較好的結果，已經成為智能優化算法領域的又一個研究熱點。

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

1云計算任務調度問題的數學模型

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

　　云計算調度算法的任務是設法找到一個調度方案X，使得總任務完成時間最小。

2基于離散和聲搜索的云計算任務調度算法

　　2.1基本和聲搜索算法

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

　　2.2云計算任務調度算法的實現

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

　　2.2.1和聲編碼及其初始化

　　由于云計算調度本身是離散優化問題，為簡化計算過程，新算法采用“任務虛擬機”間接離散編碼方式，即一個和聲的編碼長度為子任務個數，每一位編碼的位置代表對應的子任務，每一位編碼的數值代表分配的虛擬機編號。

　　假設要將n個子任務分配到m個虛擬機上執行，則n個子任務依次編號為0~n-1，m個虛擬機編號依次為0~m-1。如果用長度為n的數組Xi表示一個和聲，則滿足i∈［0,n－1］且Xi∈［0,m－1］。

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

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

　　2.2.2適應度函數

　　適應度函數是優化的目標，和聲搜索算法正是以適應度函數為目標函數，在解空間中不斷迭代尋找最優解，并以此為依據來對種群中的個體進行評價。因此，適應度函數的選擇對于利用好和聲搜索算法至關重要。考慮到計算的復雜性，新算法以公式（1）作為適應度函數。

　　2.2.3新和聲的產生

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

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

　　（2）按照微調擾動和隨機選擇規則，在［0,1］之間產生一個隨機數τ2，如果τ2<PAR,則xnew(j)按照公式（2）和（3）進行微調擾動：

　　上述兩公式中，PAR是算法的聲音調微調概率，也是一個預設的參數，τ3和τ4是［0,1］之間的隨機數。

　　2.2.4和聲記憶庫的更新

　　產生新和聲后，算法隨后要更新和聲記憶庫。更新和聲記憶庫的依據是適應度函數值的優劣，即如果產生的新和聲xnew所對應的函數值優于原來和聲記憶庫中函數值最差的和聲xw所對應的適應度值,則用新的和聲xnew替換xw，否則不再替換。

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

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

　　Step2：初始化和聲記憶庫。按照2.2.1節的方法產生初始和聲記憶庫，并使用公式（1）計算每個和聲的適應度函數值。

　　Step3：產生新的和聲。對和聲記憶庫中的每一個和聲，利用2.2.3節提出的記憶考慮、微調擾動、隨機選擇規則產生新和聲xnew。

　　Step4：和聲記憶庫更新。將新產生的解xnew與HM內的最差解進行比較，如果新解優于最差解，則進行替換。

　　Step5：判斷是否終止。若當前迭代次數達到NI則終止；否則轉向Step3繼續執行。

3仿真實驗分析

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

　　實驗中設置的虛擬機數為10，隨機產生50、100、500、1 000、1 500和2 000個任務進行調度，旨在考察不同規模情況下新算法DHS的調度性能。其中，每個虛擬機的CPU數量、內存大小、MIPS、網絡帶寬等指標由MATLAB隨機生成。為保證實驗具有可比性，前一輪實驗產生的任務要包含在后一輪實驗的任務當中。對比算法采用輪詢調度算法（RR）和MinMin算法。為盡可能減少誤差，保證實驗結果的準確性，每次實驗連續運行20次，取平均值作為實驗數據。實驗得到的各種算法的總任務完成時間如圖1所示。

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

4結論

　　一個好的任務調度算法能夠顯著提高云計算系統的性能。本文在基本和聲搜索算法的基礎上，從編碼方式、新和聲產生方式等方面對其進行了改進，提出一種基于離散和聲搜索的云計算任務調度算法DHS。最后進行了仿真實驗。實驗表明，新提出的DHS算法在處理大規模任務時的性能顯著優于輪詢、MinMin等經典算法。

　　參考文獻

　　［1］ 王波,張曉磊.基于粒子群遺傳算法的云計算任務調度研究［J］.計算機工程與應用,2015,51(6):8488.

　　［2］ 劉鵬.云計算［M］ .北京：電子工業出版社，2011.

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

　　［4］ 陳海燕.基于多群智能算法的云計算任務調度策略［J］.計算機科學,2014,41(6A):8386.

　　［5］ 徐忠勝,沈蘇彬.一種云計算資源的多目標優化的調度方法［J］.微型機與應用,2015,34(13):1720.