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

姜 凱

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

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

姜 凱

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

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

云計算；任務調度；離散和聲搜索算法

0 引言

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

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

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

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

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

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

(1)

云計算調度算法的任務是設法找到一個調度方案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

(2)按照微調擾動和隨機選擇規則，在[0,1]之間產生一個隨機數τ2，如果τ2

(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 不同任務數量下總任務完成時間

從圖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.

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

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

2015-11-05)

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