基于模擬退火算法的云計算資源調度模型

袁曉林　施化吉

摘要摘要：針對云計算平臺的特征，提出基于模擬退火算法建立云計算資源調度模型。模擬退火算法在保證用戶公平性的前提下，以縮短總任務的完成時間及提高用戶滿意度為目標。通過仿真實驗，在相同硬件環(huán)境下對比分析模擬退火算法與傳統(tǒng)遺傳算法的資源調度性能。結果表明，模擬退火算法在收斂速度和用戶滿意度方面均優(yōu)于傳統(tǒng)遺傳算法，更加適應云計算環(huán)境。

關鍵詞關鍵詞：云計算；模擬退火算法；資源調度模型；算法仿真

DOIDOI：10.11907/rjdk.143838

中圖分類號：TP311.5

文獻標識碼：A文章編號文章編號：16727800（2015）002006803

基金項目基金項目：

作者簡介作者簡介：袁曉林（1987-），男，山西長治人，江蘇大學計算機科學與通信工程學院碩士研究生，研究方向為軟件工程。

0引言

云計算是近年來信息科學領域的研究熱點，集成了網(wǎng)格計算、并行處理等多種技術，通過網(wǎng)絡將各種資源打包成服務，為各類用戶提供多種可用資源和服務，這樣要求云計算資源分配方式能夠滿足不同用戶的需求，使用戶能夠獲得良好的服務質量，因此設計性能優(yōu)異、科學合理的云計算資源調度算法至關重要＼[2＼]。

已有許多學者對云計算資源調度問題進行了相應研

究。張雨等＼[3＼]提出了一種融合遺傳算法與蟻群算法的混合調度算法，認為其能有效完成云計算任務調度；卓濤等＼[4＼]利用基于改進人工蜂群算法的云計算資源調度模型，改善了傳統(tǒng)資源調度算法存在的缺陷，提高了云計算資源利用率，并且大幅度減少了任務的完成時間；封良良等＼[5＼]利用于改進粒子群的任務調度算法，采用間接編碼方式對每個子任務占用的資源進行編碼，給出解碼方式，定義了考慮時間和成本的適應度函數(shù)，確立了粒子位置和速度的更新方法，認為在相同的條件設置下，該算法的總任務完成時間和總任務完成成本小于傳統(tǒng)粒子群優(yōu)化算法。然而，這些調度算法均存在各自的不足，如在不同云計算環(huán)境下算法性能差異性大、易陷入局部最優(yōu)，或者在搜索效率上有待提高。

模擬退火算法（Simulated Annealing， SA） 最早由N·Metropolis等人于1953年提出，1983 年，S·Kirkpatrick等嘗試將退火思想運用于組合優(yōu)化算法設計，如今模擬退火算法已成功應用于組合優(yōu)化、生產(chǎn)調度、控制工程等領域。模擬退火算法是一種允許在一定限度內接受非最優(yōu)解，從而有效避免陷入局部最優(yōu)解的優(yōu)化算法＼[6＼]。本文將基于帶記憶功能的模擬退火算法，構建云計算資源調度模型，以期獲得較高的作業(yè)調度效率。

1云計算任務調度模型

1.1任務調度模型

云計算系統(tǒng)在保證資源得到最大利用的同時，盡可能為用戶提供高質量服務，但云計算系統(tǒng)資源有限，經(jīng)常出現(xiàn)資源競爭現(xiàn)象，只能采用資源調度算法將任務合理進行分配，從而防止出現(xiàn)一個資源被多個任務爭搶的現(xiàn)象。云計算平臺任務調度模型結構如圖1所示。

圖1云計算平臺任務調度模型結構

1.2任務調度算法評價指標

云計算的單個用戶任務可用十元數(shù)組表示，如式（1）：

T={ID，PE，L，Input，ET，EBW，EF，EP，J}（1）

式（1）中，J為該任務的用戶完成離散度。J直接決定云計算平臺完成執(zhí)行該任務后用戶的滿意度。當J>0時，該用戶對任務需求的實際獲取值要大于期待值；反之，當J<0時，該用戶對任務需求的實際獲取值要小于期待值。|J|越小，表明云計算系統(tǒng)為用戶提供可以接受的服務的同時，所調用的資源越少，即表明采用的云計算任務調度算法越優(yōu)化。

2模擬退火算法

2.1模擬退火算法基本原理

模擬退火算法源于對固體退火過程的模擬，先將固體加溫，在熔融溫度下，固體粒子能量的非均勻性被破壞，并會達到新的平衡，系統(tǒng)能量增大；然后讓其徐徐降溫，讓系統(tǒng)在每一溫度下都達到平衡值，系統(tǒng)能量也逐漸降低；當溫度達到結晶溫度后，固體結晶，系統(tǒng)能量達到最小值。

2.2算法執(zhí)行

設組合優(yōu)化問題的一個解i及其目標函數(shù)f（i）分別與固體的一個微觀狀態(tài)i及其能量E（i）等價。令隨算法進程遞減的控制參數(shù)t擔當固體退火過程中溫度T的角色，溫度由一個冷卻進度表控制。

在某控制參數(shù)T（稱為溫度）下，當前解為i，對應的目標函數(shù)為E（i），在鄰域產(chǎn)生新解j，對應的目標函數(shù)為E（j），模擬退火算法接受新解j的準則稱為Metropolis準則，可描述如下：若E（j）

若E（j）>E（i），如果e（E（i）-E（j））/T>rand（0，1），則也以j取代i作為當前解；

其它條件下，以i作為當前解。

其中，rand（0，1）為0～1之間均勻分布的隨機數(shù)。

溫度由冷卻進度表控制，由高到低逐漸下降至接近0，可賦予一個初值T0，衰減函數(shù)，終值Tf，也可以用一組數(shù)列Ti取代衰減函數(shù)。產(chǎn)生新解并且進行一次Metropolis判斷的過程稱為一次嘗試，在某個相同溫度下進行的若干次嘗試序列稱為一個Mapkob鏈，若干個Mapkob鏈序列組成一個完整的模擬退火過程。

模擬退火算法的收斂速度取決于參數(shù)和Mapkob鏈長度的選擇。此外，Metropolis算法的有效實現(xiàn)亦是關鍵所在。

2.3算法優(yōu)化

模擬退火算法的有效實現(xiàn)需要控制參數(shù)的合理選擇，為了提高算法優(yōu)化效果，對原方法作了一些改進：

（1）模擬退火算法如果要真正收斂于全局最優(yōu)，則需要溫度的徐徐下降，并在每一個溫度下達到平衡，最終溫度要趨近于零。如此則Mapkob鏈無限長，這是在實際情況中無法達到的。為克服此問題，可多次退火尋優(yōu)或者多次加溫退火（即當溫度降到最低時，升溫然后繼續(xù)退火）。

（2）往往搜索到一個較好的解，但是由于溫度較高將其舍去，因而最后解往往比舍棄的解更差。本文算法記錄了所有嘗試的最優(yōu)解，在最后退火結束時如果記憶中舍去的解比退火最后解更優(yōu)，則將其作為全局最優(yōu)解。這在程序結束時進行，以避免破壞退火進程。

（3）在退火過程中，有時幾乎接近最優(yōu)解，然而溫度過高，搜索過程可能離開此處向其它方向搜索，從而失去全局最優(yōu)解。而在某一局部尋找局部最優(yōu)正是局部搜索法的特點，因此在退火的某一時段，在某個解周圍進行局部搜索，局部搜索結束后在暫停處繼續(xù)退火進程，將會提高解的質量。需要注意的是，局部搜索階段必須設置一個終止規(guī)則，因為計算機雙精度數(shù)據(jù)有效位數(shù)很大，目標函數(shù)可能由于不斷地減小而陷入死循環(huán)。

3實驗仿真與結果分析

本文基于MATLAB軟件模擬的云計算環(huán)境，對傳統(tǒng)遺傳算法與模擬退火算法進行仿真實驗，在相同硬件環(huán)境下對比這兩種算法，并分析實驗結果。云計算完成全部任務的總時間和全部任務完成后任務完成離散度是仿真實驗中主要考慮的兩個評價因素。

本文采用的模擬退火算法和傳統(tǒng)遺傳算法均是參數(shù)最優(yōu)化估計的非線性算法。仿真實驗結果顯示，模擬退火算法在任務完成時間和用戶滿意度兩個方面均優(yōu)于傳統(tǒng)遺傳算法。實驗中對兩種算法在5臺虛擬機構成的云計算平臺上對100個云計算任務的任務調度性能進行了分別測試，實驗仿真時的各項參數(shù)如表1所示，實驗仿真結果如圖2、圖3所示。

表1仿真實驗主要參數(shù)

算法[]參數(shù)及取值

[]種群大小N=200

傳統(tǒng)遺傳算法[]k1=0.450

[]k2=0.880

[]k3=0.075

[]起始溫度T=200℃

模擬退火算法[]終止溫度T=1.0℃

[]退火系數(shù)K=0.950

在云計算平臺執(zhí)行所有用戶任務的總時間上，兩種算法總任務完成時間相近，模擬退火算法略優(yōu)。同時，實驗結果證明，模擬退火算法能夠更快達到收斂，并有效避免

陷入局部最優(yōu)解的現(xiàn)象。結果表明，模擬退火算法能夠在一定的范圍內接受惡化解，有效防止遺傳算法容易出現(xiàn)的陷入局部最優(yōu)解現(xiàn)象，提高云計算作業(yè)任務調度算法的總體性能。在用戶對云計算平臺所提供服務的用戶滿意度上，由于模擬退火算法有效避免了局部收斂現(xiàn)象，其最終任務完成離散度較傳統(tǒng)遺傳算法小。

圖3用戶任務完成離散度分布

4結語

本文提出利用帶有記憶功能的模擬退火算法建立云計算資源調度模型。該算法針對基于云計算平臺的多用戶多任務特征，對不同任務調用的計算資源進行優(yōu)化分配，以縮短總任務的完成時間，并增加用戶滿意度。仿真實驗結果表明，該算法在滿足用戶要求的同時能夠縮短總任務的完成時間，是云計算平臺下的一種有效調度算法。

參考文獻參考文獻：

＼[1＼]過敏意.綠色計算：內涵及趨勢＼[J＼].計算機工程， 2010，36（10）： 17.

＼[2＼]DAI W，MILENKOVIC O.Subspace pursuit for compressive sensing signal reconstruction＼[J＼].IEEE Transactions on Information Theory， 2009， 55（5）：22302249.

＼[3＼]張雨，李芳，周濤.云計算環(huán)境下基于遺傳蟻群算法的任務調度研究＼[J＼].計算機工程與應用，2014（6）：5155.

＼[4＼]卓濤，詹穎.改進人工蜂群算法的云計算資源調度模型＼[J＼].微電子學與計算機，2014（7）：147150，155.

＼[5＼]封良良，張?zhí)?，賈振紅，等.云計算環(huán)境下基于改進粒子群的任務調度算法＼[J＼].計算機工程，2013（5）：183186，191.

＼[6＼]遆鳴，陳俊杰，強彥.基于模擬退火的Map Reduce調度算法＼[J＼].計算機工程，2012（19）：4548.

責任編輯（責任編輯：孫娟）