云環(huán)境中基于混合和聲算法的資源調(diào)度方案

李遠(yuǎn)征，佟國香

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海200093)

?

云環(huán)境中基于混合和聲算法的資源調(diào)度方案

李遠(yuǎn)征，佟國香

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海200093)

隨著信息技術(shù)的日趨成熟，任務(wù)、資源也呈幾何倍數(shù)增長，對(duì)資源調(diào)度效率的要求不斷提高，如何提高資源調(diào)度效率也成為了當(dāng)前研究的熱點(diǎn)。為此，文中針對(duì)調(diào)度策略提出了一種混合和聲算法，加入遺傳算法交叉操作和動(dòng)態(tài)PAR方法，擴(kuò)大基本和聲算法的搜索范圍并防止其陷入局部最優(yōu)，以達(dá)到最短時(shí)間跨度的目的。通過Cloudsim云仿真平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，該算法明顯減少了任務(wù)平均完成時(shí)間，有效提高了資源調(diào)度效率。

云計(jì)算; 資源調(diào)度; 和聲算法; 遺傳交叉操作; Cloudsim

LI Yuanzheng, TONG Guoxiang

(School of Photoelectric Information and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

云計(jì)算通過虛擬化技術(shù)[1-3]，將異構(gòu)的硬件軟件資源整合成云資源池，根據(jù)用戶需求進(jìn)行調(diào)度及分配，但由于云計(jì)算資源具有開放、異構(gòu)、并行、海量數(shù)據(jù)及用戶等特點(diǎn)，如何高效地進(jìn)行資源調(diào)度是云計(jì)算發(fā)展過程中必須解決的關(guān)鍵問題[4-7]。

傳統(tǒng)的調(diào)度方法如包括OLB、輪循調(diào)度算法、Min-Min算法、MCT算法、禁忌搜索等,這些方法具有原理簡單、易實(shí)現(xiàn)的特點(diǎn),但處理大規(guī)模復(fù)雜問題時(shí)性能不佳[8]。為此，本文提出一種混合和聲算法資源調(diào)度的方案，并利用Cloudsim云仿真平臺(tái)和其他算法加以比較，來證明本方案的可行性。

1 云資源調(diào)度模型

1.1 虛擬機(jī)資源描述

虛擬機(jī)資源集合VM={vm1, vm2, vm3, …,vmn}，其中各虛擬機(jī)可以統(tǒng)一表示為VMi={vmid,mips,size,ram,bw,pesNumber}。其中，vmid、mips、size、ram、bw、pesNumber分別表示虛擬機(jī)ID、每秒百萬條指令、存儲(chǔ)空間大小、內(nèi)存空間大小、帶寬和核數(shù)。

1.2 用戶任務(wù)描述

設(shè)云環(huán)境中有用戶任務(wù)集合中有n個(gè)任務(wù):Task={task1, task2, task3,…. taskn}，其中，每個(gè)任務(wù)可簡單統(tǒng)一表示為taski={Length,Filesize,Outputsize}。其中Length表示其任務(wù)長度，F(xiàn)ilesize表示為輸入任務(wù)文件大小，Outputsize表示輸出文件大小。

1.3 調(diào)度過程描述

圖1 云環(huán)境下任務(wù)資源調(diào)度模型

云計(jì)算中資源調(diào)度可分為兩部分：第一部分為任務(wù)與虛擬機(jī)之間的分配調(diào)度；第二部分為虛擬機(jī)與主機(jī)之間的匹配。本文所解決的是第一部分的分配策略，即用戶任務(wù)與虛擬資源的調(diào)度策略。

2 混合和聲算法

和聲搜索算法(Harmony Search, HS)算法首先由韓國學(xué)者 Geem 等人于 2001年提出的一種現(xiàn)代啟發(fā)式算法。[9]和聲算法通過模擬音樂家即興創(chuàng)作不斷調(diào)整嘗試來達(dá)到最美和聲的過程進(jìn)行尋優(yōu)。

雖然基本的和聲搜索算法(HS)具有優(yōu)秀的優(yōu)化性能，但是其利用步長微調(diào)的策略不能有效的調(diào)節(jié)解向量的結(jié)構(gòu)，容易陷入局部最優(yōu)。為此，本文在和聲算法的基礎(chǔ)上加入了遺傳算法的交叉操作，同時(shí)提出了一種動(dòng)態(tài)調(diào)節(jié)PAR的方法。

2.1 遺傳算法交叉操作的加入

遺傳算法(GA)作為經(jīng)典的啟發(fā)式算法，已被廣泛應(yīng)用[10]，交叉更是其核心部分，為提高和聲記憶庫中解的多樣性，本文將這個(gè)步驟加入和聲算法。其基本操作原理為，當(dāng) rand

2.2 動(dòng)態(tài)參數(shù)PAR的設(shè)計(jì)

基因調(diào)整概率PAR是和聲搜索算法中的重要參數(shù)，一般來說，當(dāng)PAR值較小時(shí)，算法的局部搜索能力比較強(qiáng)。[11]反之，當(dāng)PAR較大時(shí)，算法具有較大的搜索范圍。所以，本文所使用的PAR設(shè)計(jì)方案為

(1)

混合和聲算法的步驟可以歸納為以下幾步：

步驟1 對(duì)混合和聲算法需要使用的參數(shù)進(jìn)行初始化。主要參數(shù)包括問題的維數(shù)N，每一維參數(shù)N的取值范圍[xL,xH] ，和聲記憶庫的范圍HMS，記憶庫取值概率HMCR，微調(diào)步長bw，音調(diào)微調(diào)概率PAR;

步驟2 和聲記憶庫初始化。和聲記憶庫存儲(chǔ)了HMS個(gè)和聲初始解，用矩陣HM表示如下

(2)

步驟3 生成新的和聲向量。新的和聲向量即為新的解向量，新解的產(chǎn)生規(guī)則如下

(3)

(4)

步驟4 更新和聲記憶庫。

步驟5 重復(fù)步驟3和步驟4，直到滿足條件或者滿足迭代次數(shù)。

具體實(shí)現(xiàn)過程如圖2所示。

圖2 混合和聲算法流程圖

3 混合和聲算法的應(yīng)用

和聲算法和其他啟發(fā)式算法一樣，對(duì)于不同問題所采用的編碼方式以及適應(yīng)度函數(shù)都有所不同。本文采用實(shí)數(shù)編碼方式進(jìn)行編碼，并將該和聲組合適應(yīng)度函數(shù)的值放到每個(gè)和聲組合最后一位，執(zhí)行任務(wù)的時(shí)間跨度作為適應(yīng)度函數(shù)進(jìn)行設(shè)計(jì)。

3.1 編碼規(guī)則設(shè)計(jì)

圖3 第i組和聲序列

以圖3為例，該數(shù)組表示和聲庫中的第i組和聲序列。每個(gè)框中的數(shù)字代表第i個(gè)任務(wù)對(duì)應(yīng)的虛擬機(jī)編號(hào)，即第1個(gè)任務(wù)由5號(hào)虛擬機(jī)處理，第2個(gè)任務(wù)由3號(hào)虛擬機(jī)處理，第3個(gè)任務(wù)由2號(hào)虛擬機(jī)處理，以此類推。此外，最后一列數(shù)組數(shù)值Fit(i)表示該和聲序列的適應(yīng)度值。

3.2 適應(yīng)度函數(shù)設(shè)計(jì)

在云模型中，因?yàn)樵瀑Y源調(diào)度能耗等問題都與任務(wù)處理完成時(shí)間有著直接的聯(lián)系，所以本方法以調(diào)度處理時(shí)間為適應(yīng)度函數(shù)來進(jìn)行調(diào)度策略的研究。VM[i]表示第i個(gè)虛擬機(jī)資源，task[j]表示第j個(gè)任務(wù)。那么第j個(gè)任務(wù)在第i個(gè)虛擬機(jī)上運(yùn)行的時(shí)間用式(5)表示

Tij→(VM[i],task[j])

(5)

適應(yīng)度函數(shù)可以寫作

(6)

4 仿真實(shí)驗(yàn)

因?yàn)闃?gòu)建實(shí)際的云平臺(tái)成本高、效率低，所為簡化云平臺(tái)的建設(shè)與測(cè)試過程，澳大利亞墨爾本大學(xué)云計(jì)算與分布式系統(tǒng)實(shí)驗(yàn)室開發(fā)了CloudSim仿真軟件。本方案采用云仿真平臺(tái)Cloudsim對(duì)混合和聲算法進(jìn)行驗(yàn)證。

為符合實(shí)際情況，本實(shí)驗(yàn)設(shè)置了不同大小的虛擬機(jī)、任務(wù)以及多種帶寬。具體實(shí)驗(yàn)參數(shù)如表1所示。

表1 實(shí)驗(yàn)平臺(tái)參數(shù)

表2 混合和聲算法參數(shù)設(shè)置

本實(shí)驗(yàn)分別在相同虛擬機(jī)個(gè)數(shù)以及相同任務(wù)個(gè)數(shù)兩種情況下進(jìn)行。

實(shí)驗(yàn)1 設(shè)定虛擬機(jī)個(gè)數(shù)為5，任務(wù)數(shù)量分別為10,20,30,40,50,60,70,80,90,100。分別使用混合和聲算法(HHS)和蟻群算法(ACO)進(jìn)行對(duì)比。由圖4可以明顯的看到隨著任務(wù)個(gè)數(shù)的增加，混合和聲算法花費(fèi)的時(shí)間不僅一直小于蟻群算法，并且隨著任務(wù)數(shù)量的增加，兩種算法的運(yùn)行時(shí)間差越來越大。

圖4 不同任務(wù)個(gè)數(shù)各調(diào)度方法所需時(shí)間

圖5 不同虛擬機(jī)個(gè)數(shù)各調(diào)度方法所需時(shí)間

實(shí)驗(yàn)2 設(shè)定任務(wù)數(shù)量為100個(gè)，虛擬機(jī)的數(shù)量分別為6,7,8,9,10,11,12,13,14,15。由圖5發(fā)現(xiàn)，隨著虛擬機(jī)個(gè)數(shù)的增加，混合和聲算法和蟻群算法運(yùn)行時(shí)間均有所浮動(dòng)，但混合和聲算法調(diào)度策略花費(fèi)的時(shí)間還是要遠(yuǎn)小于蟻群算法。

5 結(jié)束語

本文提出一種混合和聲調(diào)度算法，通過實(shí)驗(yàn)證明該算法可縮短時(shí)間跨度，提高調(diào)度效率。但本文僅是采用了運(yùn)行時(shí)間這一適應(yīng)度函數(shù)進(jìn)行約束，在實(shí)際應(yīng)用中影響分配效率的因素還有很多，下一步工作是結(jié)合多種約束條件進(jìn)行算法的應(yīng)用與研究。

[1] 儲(chǔ)雅,馬廷淮,趙立成.云計(jì)算資源調(diào)度:策略與算法[J].計(jì)算機(jī)科學(xué),2013(11):8-13.

[2] 李艦鋒,彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用,2011, 31(1):184-186．

[3] Mahdavi M, Fesanghary M, Damangir E. An improved harmony search algorithm for solving optimization problems[J].Applied Mathematics and Computation,2007,188(2):1567-1579.

[4] Tang M,Pan S. A hybrid genetic algorithm for the energy-efficient virtual machine placement problem in data centers[J].Neural Processing Letters, 2014,41(2):211-221.[5] Beloglazov A,Abawajy J,Buyya R.Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J].Future Generation Computer Systems,2012,28(5):755-768.

[6] 吳國芳.云環(huán)境中基于布谷鳥搜索算法的多目標(biāo)任務(wù)調(diào)度方案[J].計(jì)算機(jī)應(yīng)用研究,2015,9(9):2674-2677.

[7] Calheiros R N，Ranjan R，Beloglazov A,et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software Practice & Experience,2011,41(1):23-50

[8] 李鋒華.基于蟻群算法的云計(jì)算資源負(fù)載均衡調(diào)度算法研究[D].昆明:云南大學(xué),2013．

[9] 劉曉茜.云計(jì)算數(shù)據(jù)中心結(jié)構(gòu)及其調(diào)度機(jī)制研究[D].合肥：中國科學(xué)技術(shù)大學(xué),2011.

[10] Andrew J Younge,Gregor Von Laszewski,Wang Lizhe,et al.Efficient resource management for cloud computing environments[C].Noven:International Conference on Green Computing,2010.

[11] Calheiros R N,Ranjan R,Beloglazov A，et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software Practice & Experience,2010,41(1):23-50.

[12] 李若平.學(xué)習(xí)型和聲搜索算法及其在0_1背包問題中的應(yīng)用[J].控制與決策，2013,28(2):205-210.

Resource Scheduling Based on Hybrid Harmony Search Algorithm in Cloud Environment

The exponential growth of tasks and resources in the information industry asks for more efficient resource scheduling. In this paper, we presents a hybrid algorithm harmony scheduling algorithm by combining the crossover of genetic algorithm and the dynamic PAR method to expand the search range of basic harmony search algorithm and preventing falling into local optimum, thus achieving the shortest time. Cloudsim simulation shows this algorithm can significantly reduce the average schedule time.

cloud computing; resource scheduling; crossover of genetic algorithm; harmony search; Cloudsim

2016- 01- 05

李遠(yuǎn)征(1990-)，男，碩士研究生。研究方向：啟發(fā)式算法等。

10.16180/j.cnki.issn1007-7820.2016.10.015

TP391

A

1007-7820(2016)10-051-04