基于綠色云計算平臺的等價黃金分割資源分配優(yōu)化算法研究

王詠梅，施培蓓，劉 磊，周媛媛

（1.合肥師范學(xué)院 計算機學(xué)院，安徽 合肥 230031；2.合肥市公安信息中心，安徽 合肥 230001；3.安徽大學(xué) 計算機學(xué)院，安徽 合肥 230036）

1 引言

在信息技術(shù)的高速發(fā)展過程中，隨著企業(yè)用戶和數(shù)據(jù)的爆炸式增長，能源效率已經(jīng)成為一個突出的矛盾.如何減少碳排放和節(jié)約成本已成為大數(shù)據(jù)運營商越來越關(guān)注的問題[1].隨著云計算的計算服務(wù)向普及化方向發(fā)展，對云計算的需求不斷擴大，需要建立大規(guī)模的數(shù)據(jù)中心，而數(shù)據(jù)中心的運行維護需要消耗大量的能量[2].保證云計算系統(tǒng)的高性能，提高資源利用率，降低能耗已成為亟待解決的問題.綠色云計算為云計算技術(shù)的發(fā)展提供了契機，它通過構(gòu)建合理的資源分配環(huán)境和高效的任務(wù)執(zhí)行環(huán)境來降低能耗、提高效率，以達到節(jié)能環(huán)保的目的[3].資源分配是綠色云計算的關(guān)鍵技術(shù)之一.目前，資源分配的研究主要集中在通過平衡數(shù)據(jù)中心的負(fù)載來提高整體性能這一方面.這些研究沒有把如何降低系統(tǒng)的能耗充分考慮進去.在資源配置過程中優(yōu)化資源分配策略可以減少服務(wù)器產(chǎn)生的熱量，降低散熱成本，從而提高系統(tǒng)的穩(wěn)定性和延長硬件[4,5]壽命.資源利用率的提高能有效節(jié)約能源，降低二氧化碳的排放，對緩解溫室效應(yīng)具有一定的貢獻，對整個生態(tài)環(huán)境保護也具有重要意義，它符合當(dāng)今社會的“綠色IT”概念.因此，研究綠色云計算環(huán)境下的資源分配優(yōu)化策略具有重要的理論意義.

2 國內(nèi)外資源配置優(yōu)化策略的現(xiàn)狀

隨著云計算技術(shù)的蓬勃發(fā)展，谷歌、Amazon、IBM等大公司紛紛開發(fā)了自己的云計算平臺，而云計算相關(guān)技術(shù)的研究與實現(xiàn)也呈現(xiàn)出快速發(fā)展的趨勢.作為云計算的關(guān)鍵技術(shù)，資源配置仍處于研究階段，到目前為止，還沒有一個統(tǒng)一的行業(yè)標(biāo)準(zhǔn)[6].國內(nèi)外研究有代表性的有：

文獻[7]采用了演化博弈的方式對整個云計算市場進行建模分析，最終通過動態(tài)演化整個市場可以達到演化穩(wěn)定.但是作者只是考慮了資源的價格，忽略了用戶所關(guān)心的QoS問題.S.S.Manvi等人最早提出了面向市場的云計算架構(gòu)，以及基于該架構(gòu)的云計算資源分配方式[8].M.Macia等人采用遺傳算法解決云計算市場中的定價問題，使得每一個云服務(wù)提供商能在整個市場中制定合理的服務(wù)價格[9].S.AT等人提出了基于市場機制的資源分配策略[10]，通過利用市場機制來尋找資源需求與分配的平衡點.但以上策略都側(cè)重在運用市場機制方面對各種角色進行優(yōu)化，對資源的分配方式?jīng)]有提出具體的方案.

Shuai Ding等人通過動態(tài)分配虛擬機到服務(wù)器，證明了在保證服務(wù)質(zhì)量的前提下可以通過虛擬機的遷移和關(guān)閉空閑服務(wù)器來降低功耗[11].S.T.Maguluri等人將虛擬資源分配問題建模為多維背包問題，并找到服務(wù)器執(zhí)行單位事務(wù)功耗的最優(yōu)點[12].文獻[13]提出了一種基于云計算虛擬機初始分配的節(jié)能算法，設(shè)計了一種基于網(wǎng)絡(luò)感知的虛擬機再調(diào)度算法.這些研究側(cè)重從虛擬化應(yīng)用方面考慮如何充分發(fā)揮虛擬化技術(shù)的優(yōu)勢，以實現(xiàn)硬件資源利用的最大化.

在資源分配算法的設(shè)計方面，為了實現(xiàn)資源分配的負(fù)載均衡，F(xiàn)lorin Pop等人設(shè)計了一種基于遺傳算法的能量感知優(yōu)化模型和資源分配策略[3].Y.J.Chiang等人提出一種高效的綠色能耗控制資源分配方法[14]，但均沒有充分考慮到資源分配中的能耗優(yōu)化問題.J.T.Tsai等人提出了一種基于差分進化算法的云計算資源分配方法(IDEA)，實驗證明了該算法比其他云計算資源分配方法具有更優(yōu)的效率，但是該算法只考慮帶寬占用、網(wǎng)絡(luò)負(fù)載和響應(yīng)時間等因素對云端資源分配的影響[15],沒有充分考慮系統(tǒng)能耗情形下，如何構(gòu)建動態(tài)能耗優(yōu)化模型、資源分配優(yōu)化模型的問題.

針對上述綠色云計算環(huán)境下的資源分配問題，本文提出了一個等價黃金分割資源分配優(yōu)化算法(Equivalent Golden Partition Resource Allocation Optimization,EGPRAO)，該算法能實現(xiàn)全局和局部搜索的平衡，在構(gòu)建合理的資源分配環(huán)境和高效的任務(wù)執(zhí)行環(huán)境方面，該算法比目前已有的資源分配策略具有更低能耗、更高效率的優(yōu)點.

3 等價區(qū)間劃分與黃金分割策略

為了避免算法陷入局部最優(yōu)值，實現(xiàn)全局和局部搜索的平衡，本文將算法的初始種群構(gòu)建為一種等價區(qū)間劃分優(yōu)化模型.其目的是盡可能地將冗余個體劃分為一個區(qū)間塊，然后對不同的區(qū)間塊進行不同的操作，從而指導(dǎo)相關(guān)算法算子進行引導(dǎo)搜索.圖1描述的是該算法的種群等效區(qū)間劃分模型流程圖.

在圖1中,N表示等價區(qū)間劃分的個數(shù),a表示種群中個體最小的適應(yīng)度值,b表示種群中個體最大的適應(yīng)度值,c表示種群中個體平均的適應(yīng)度值.

黃金分割策略是利用區(qū)間消去法的原理，通過不斷縮小單峰區(qū)間長度，即每次迭代都消去一部分不含極小值點的區(qū)間，使搜索區(qū)間不斷縮小，從而逐漸逼近目標(biāo)函數(shù)極小值點的一種優(yōu)化方法.黃金分割策略是直接尋優(yōu)法，通過直接比較區(qū)間上點的函數(shù)值的大小來判斷區(qū)間的取舍，這種方法具有計算簡單，收斂速度快等優(yōu)點.

黃金分割策略是基于選擇區(qū)間內(nèi)計算點的位置，它具有以下通用的策略：

（1）點α1和α2相對于區(qū)間[a,b]的邊界要對稱分布，即區(qū)間[a,α1)的區(qū)間大小和(α2,b]的區(qū)間大小相等.

（2）每次計算一個新點，要求保留的區(qū)間長度l與原區(qū)間長度L之比等于被消去的區(qū)間長度L-l與保留區(qū)間長度之比，即滿足以下條件：

4 等價黃金分割資源分配優(yōu)化算法

本文設(shè)計的等價黃金分割資源分配優(yōu)化算法的實現(xiàn)步驟如下：Step 1. 在[a,b]內(nèi)取兩點 α1和 α2,使

α1=a+0.382×(b-a),α2=a+0.618×(b-a)

Step 2. 計算 f1=f(α1)，f2=f(α2).

Step 3. 當(dāng) f1＜f2時，消去區(qū)間(α2,b].同時，令 b=α2，α2=α1，f1=f2.令 α1=a+0.382×(b-a)，f1=f(α1).

Step 4.當(dāng)f1≥f2時，消去區(qū)間 [a,α1).同時，令 a=α1，α2=α1，f1=f2.令 α2=a+0.618×(b-a)，f2=f(α2).

Step 5.當(dāng)b-a≤δ，算法結(jié)束；否則，返回到Step 3.

5 實驗測試與結(jié)果分析

為了驗證本文設(shè)計的EGPRAO算法的可行性和優(yōu)越性，從算法的執(zhí)行時間、資源分配的能耗和資源平均利用率三個方面設(shè)計了不同的目標(biāo)函數(shù)，利用實驗仿真平臺CloudSim，進行仿真測試實驗.考慮到單個數(shù)據(jù)中心的數(shù)據(jù)具有一定的不確定性，該綠色云計算平臺設(shè)置了8個數(shù)據(jù)中心，每個數(shù)據(jù)中心包含10GB的RAM和2TB的存儲，8核CPU,每個CPU的計算能力是10000MIPS.文獻[15]的IDEA算法在多種不同平臺環(huán)境下都取得了較好的實驗結(jié)果，因此，在相同的測試條件下本文將EGPRAO算法與文獻[15]的IDEA算法進行性能對比，實驗結(jié)果分別如圖2、圖3和圖4所示.

圖2 兩種不同資源分配算法的執(zhí)行時間比較

圖3 兩種不同資源分配算法的能耗函數(shù)比較

圖2顯示的兩種不同資源分配算法的執(zhí)行時間函數(shù)對比結(jié)果，圖3顯示的是兩種不同資源分配算法的能耗函數(shù)對比結(jié)果，圖4顯示的是兩種不同資源分配算法的資源平均利用率函數(shù)對比結(jié)果.

圖4 兩種不同資源分配算法的資源平均利用率函數(shù)比較

通過圖2-4的實驗結(jié)果，我們不難看出：在執(zhí)行時間、能耗優(yōu)化和資源平均利用率等方面，本文設(shè)計的EGPRAO算法比傳統(tǒng)的IDEA算法表現(xiàn)出更良好的性能.

6 結(jié)論

信息技術(shù)日新月異的變化，導(dǎo)致人類對云計算技術(shù)的應(yīng)用越來越普及.本文針對綠色云計算中日益嚴(yán)重的能耗問題，設(shè)計了一種新的資源分配算法.該算法利用黃金分割策略和等價區(qū)間劃分優(yōu)化模型資源的優(yōu)點，能實現(xiàn)全局和局部搜索的平衡.在構(gòu)建合理的資源分配環(huán)境和高效的任務(wù)執(zhí)行環(huán)境方面，該算法具有更低能耗、更高效率的優(yōu)點.在CloudSim測試平臺中，該算法取得了比較理想的實驗結(jié)果.