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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step 4.當(dāng)f1≥f2時(shí)，消去區(qū)間 [a,α1).同時(shí)，令 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 實(shí)驗(yàn)測(cè)試與結(jié)果分析

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

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

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

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

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

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

6 結(jié)論

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