許文慶

(1.福州理工學院，福建 福州 350506;2.福州理工學院移動通信和 物聯(lián)網(wǎng)福建省高校工程研究中心，福建 福州 350506)

0 引言

近年來隨著大數(shù)據(jù)和云計算等新技術的協(xié)同[1]推進，基于云計算環(huán)境下的數(shù)據(jù)中心網(wǎng)絡在節(jié)點數(shù)量和數(shù)據(jù)規(guī)模上變得更加錯綜復雜.這使得整個云環(huán)境在系統(tǒng)可靠性、擴展性、成本可控性等諸多方面受到嚴峻的挑戰(zhàn).科學的虛擬資源調(diào)度策略作為云計算環(huán)境的核心技術，不僅可以應對傳統(tǒng)網(wǎng)絡的“僵化”[2]問題，對全新的應用服務和網(wǎng)絡協(xié)議實施評估，也有利于改善云計算環(huán)境中數(shù)據(jù)中心的能耗度、資源沖突、載荷均衡及用戶服務質(zhì)量(QoS)等一系列問題[3].所謂的虛擬資源調(diào)度是指通過為云計算環(huán)境下的數(shù)據(jù)中心物理主機節(jié)點重載程度展開評估，并將其中的虛擬機科學地遷置到數(shù)據(jù)中心中其他最合適的目標物理宿機上.此舉意在為虛擬機的遷移做鋪墊，從而最小化服務成本和資源開銷,最大化整個云計算系統(tǒng)的服務效益，同時也便于服務供應商良好地對數(shù)據(jù)中心進行管理.如此看來，對虛擬機資源實施科學高效地遷置就成了當前云計算環(huán)境下數(shù)據(jù)資源管理的核心問題之一.

對云計算系統(tǒng)中虛擬機實施遷置的關鍵在于使參與虛擬資源調(diào)度的物理主機節(jié)點規(guī)模最小，使參與虛擬資源調(diào)度的物理主機節(jié)點資源使用率最高，避免整個云計算數(shù)據(jù)中心的載荷分布失衡進而真正實現(xiàn)能源的綠色[4]管理.尤其在當前云計算和大數(shù)據(jù)協(xié)同并進的形式下，日益凸顯的能源問題再次引發(fā)學術界的熱議.并因此圍繞以能耗管理為目標的云計算系統(tǒng)虛擬機安置問題展開一系列相關研究.對于虛擬機的安置可視為裝箱問題來討論，因此對于該問題的求解可考慮通過啟發(fā)式算法來解決,譬如，遺傳算法.但是文獻[5]的研究結果表明該算法在編碼效率中表現(xiàn)出的科學性有待改進.因此若將該算法用于筆者所提的分組問題的求解，那么在虛擬機實施安置過程中將無法得到全局最佳值.這勢必造成虛擬機遷移效率劣化等一系列惡性循環(huán)問題，最終導致安置管理方案的失效.為了優(yōu)化云計算系統(tǒng)中數(shù)據(jù)中心的物理主機資源利用率，改善能耗的管理效率，文獻[6]提出了多目標安置優(yōu)化思路.先是通過描述多目標優(yōu)化模型極力提高物理資源使用率，將能耗最小化.然后使用經(jīng)過改良的多適應函數(shù)遺傳算法來并行優(yōu)化多個目標.該算法思想相對于傳統(tǒng)的遺傳算法，在安置管理方面的科學效益較為顯著.然而此思路的編碼對象僅為虛擬機，編碼長度較為冗繁，算法復雜度不占優(yōu)勢.因此也不適用于筆者提出的復雜分組問題的求解.為進一步使算法在分組[7]求解問題中具備更好的適應性，文獻[8]對上述改良的多適應函數(shù)遺傳算法做了持續(xù)優(yōu)化.在秉承遺傳算法在云環(huán)境數(shù)據(jù)中心資源使用率方面發(fā)揮優(yōu)勢的基礎上，對遺傳算法中3個步驟均做了延伸思考.顯然此舉促進遺傳算法性能上升了一個臺階.然而從實際成效來看，該研究在至關重要的交叉步驟、變異步驟中卻未能保證總是把優(yōu)質(zhì)的基因保留下來.從理論上看這樣的思路在科學性方面稍顯不足，而實際實驗成效也應驗了算法收斂較早.據(jù)此，可以預測該項持續(xù)改進的算法研究用于應對筆者提出的復雜分組求解問題收效甚微.

鑒于當前主流研究始終未能在資源利用率、效能安置、復雜分組問題求解中尋求到一個科學的平衡解，筆者圍繞云計算環(huán)境下數(shù)據(jù)中心中以優(yōu)化為目標，規(guī)劃一個兼顧效能和極優(yōu)解的虛擬機安置策略.

1 遷置優(yōu)化算法數(shù)學模型

云計算環(huán)境下的數(shù)據(jù)中心基礎設施由若干個物理服務器經(jīng)由拓撲結構連接而成.為了最大化云計算系統(tǒng)中物理服務器的資源使用率和最小化基礎設施的能耗等問題，在物理服務器中實施虛擬機高效部署顯得至關重要，這也是遷置虛擬機的目標所在.所謂高效部署指從x個物理服務器形成的集合PM=[pm1,pm2,pm3,…,pmx]中篩選出合適的目的物理服務器用于響應y個虛擬機形成的虛擬機集合VM=[vm1,vm2,vm3,…,vmy]提出的遷置請求.部署過程不僅要使參與遷置作業(yè)的物理服務器規(guī)模最小，更要使遷置的部署過程具有最佳的魯棒性.由于云計算系統(tǒng)的邊緣用戶請求呈現(xiàn)多樣化，云計算對象的數(shù)據(jù)較大，故用于響應遷置請求的物理服務器集合所提供的資源類型和容量也需多元化[9].所提供的計算響應資源包括：帶寬(GBs/day)、中央處理器(MIPS)、內(nèi)存(GB)等.令第k個物理服務器中用于響應虛擬遷置計算請求的t類資源容量為sk-t，則PM=[pm1,pm2,pm3,…,pmx]中所能提供的資源大小記作Sk=[sk-1,sk-2,sk-3,…,sk-t].同時，令第l個虛擬機提請的資源要求為d1-t，則VM=[vm1,vm2,vm3,…,vmy]所提請的資源要求記作Dl=[dl-1,sl-2,sl-3,…,sl-t].為響應遷置優(yōu)化算法中關于物理服務器規(guī)模最小化的宗旨，遷置過程可描述為：

(1)

其中，二進制數(shù)參量Jk=0，說明第k個物理服務器為關機睡眠；Jk=1則表示參與高效遷置部署作業(yè)中.NWPM指參與高效遷置部署作業(yè)的物理服務器規(guī)模.令云環(huán)境數(shù)據(jù)中心物理服務器使用率為u，算得高效遷置部署的目標函數(shù)為：

(2)

p(u)=u·(1-r)·PH+r·PH.

(3)

則在時間T范圍內(nèi)整個云環(huán)境下的數(shù)據(jù)中心能耗度為：

(4)

(5)

于是，求得第k個物理服務器的失衡度為

(6)

整個云環(huán)境數(shù)據(jù)中心載荷失衡度為

(7)

要規(guī)避云計算系統(tǒng)中物理服務器載荷失衡問題實現(xiàn)高效遷置部署目標，要求最小化NBDC參數(shù)值.

2 算法部署設計

正如引言所述，云數(shù)據(jù)中心虛擬機的遷移部署可用集裝箱問題來應對.通過梳理傳統(tǒng)研究方案的不足可知，高效的遺傳算法在編碼長度和搜索長度方面都應該是簡短的.所以在為空間內(nèi)個體搜索求解值的時候要采用小的染色體編碼方法來表征，從而避免染色體的長度問題導致遷置部署的效能性[12].故筆者考慮用分組表征方法.

傳統(tǒng)的遺傳算法研究方案為了較快地生成第二代染色體,往往直接鎖定那些適配值較高的染色體，該思想下的搜索解通常由于收斂過早導致所求解不具備全局普適性.為避免此類情形再次出現(xiàn)，筆者首先為個體逐一分析其適配值，再通過輪詢方式計算出個體的命中率進而篩選出優(yōu)質(zhì)[13]的個體，即所謂的優(yōu)勝劣汰.按照此思路，首先給出第k個個體Jk的命中率：

(8)

式中的Mk指Jk的匹配值.所謂的輪詢適配即指通過一個圓形模型將種群的數(shù)量和個體命中率劃分出x個區(qū)域，則第k個區(qū)域的角度為：

(9)

可見，Mk和anglek所對應的扇形區(qū)域呈正比.再通過累計方式計算圓形模型滾動過的弧度即可求解出第n個個體的命中率，記作：

(10)

現(xiàn)引入一個服從區(qū)間[0,1]分布的隨機均衡系數(shù)δ，用于求解最適合用作第一代染色體的個體.將此求解過程函數(shù)表征為：

(11)

為使CH2 nd染色體能夠延續(xù)到CH1 st個體中優(yōu)質(zhì)的基因，算法需先對CH1 st個體基因展開分析，評估函數(shù)記作：

(12)

若算得評估值越小，則表明該個體基因的失衡問題越凸顯，非優(yōu)質(zhì)基因；反之，則為優(yōu)質(zhì)基因.然后根據(jù)評估值的權重選擇用于交錯的基因.從而使得CH2 nd能夠可靠地延續(xù)到CH1 st優(yōu)質(zhì)的基因.極大地提高了物理服務器接受虛擬機高效遷置部署的科學性，克服了傳統(tǒng)研究關于基因隨機繼承引發(fā)的灰色效應[14].

具體實施過程為:首先定義兩個首代染色體CH1 st-A和CH1 st-B;然后對CH1 st-A中的個體服務器展開基因質(zhì)量評估，將Ek值較大的個體嵌入CH1 st-B序列中的任意點使之生成CH2 nd序列;接著開始遍歷CH2 nd序列串中的個體服務器直至計算出含有相同編號虛擬機的個體服務器，并將其剔除.若因剔除而孤立了某些虛擬機則綜合采用優(yōu)先適應算法[15]對其實施遷置.

遷置優(yōu)化算法的目標旨在最小化NWPM從而節(jié)約云計算系統(tǒng)數(shù)據(jù)中心服務器的耗能.基于此思想，本次變種算子研究使用剔除已用過的服務器以及變種后不具備依賴性的虛擬機，也就是所求的解中缺少某個虛擬機而需采用優(yōu)先適應算法對其實施返填的方式,以避免出現(xiàn)更大規(guī)模的擴散.關于服務器剔除的選取標準，主要參照基因評估函數(shù)的評估值Ek.若該值越小，表明該物理服務器中的虛擬機安置欠缺科學性，被剔除的概率越高；反之被保留的概率越高.此舉目的在于將劣化變種事件約束在適配值較低的服務器個體上.

為了使高效遷置部署算法在迭代計算期間更好地評估染色體個體的優(yōu)質(zhì)狀況，現(xiàn)引入適配參量M用于考量策略收斂快慢程度.為貫徹遷置優(yōu)化算法思想，所引入的適配參量除了要顧及物理服務器資源使用率外,也應最小化被喚醒的服務器規(guī)模.故該參量具有較大權重，關系到所得解的科學性，表征為：

(13)

3 遷置優(yōu)化算法實施

根據(jù)上述設計的算法方案，本次研究的算法思路為首先結合虛擬機提請的遷移請求得出X個排列.然后使用優(yōu)先適應機制得到X個不同的安置方法.每歷經(jīng)一次迭代式計算便對X個序列串實施編碼、選擇、交叉、變異等處理，使CH1 st優(yōu)質(zhì)的基因傳播到CH2 nd.隨著循環(huán)迭代計算的持續(xù)深入，所有個體的適配參量M的權重值都將增加直至搜索到科學解.整個遷置優(yōu)化方案的具體實施過程如下:步驟1,實施基于分組的基因編碼；步驟2,隨機化方式將種群進行初始化，并將迭代[16]次數(shù)置零；步驟3,根據(jù)所引入的適配評估函數(shù)依次計算出種群內(nèi)的個體適配參量值；步驟4,使用輪詢方式實施選擇作業(yè)，選出兩個首代染色體CH1 st-A和CH1 st-B;步驟5,根據(jù)優(yōu)質(zhì)基因評估函數(shù)的計算值獲取優(yōu)質(zhì)個體，然后放在任意交叉處生成CH2 nd序列，并參照適配參量值篩選出變種的個體;步驟6,根據(jù)基因評估函數(shù)剔除劣質(zhì)基因實施變種;步驟7,結合個體的適配參量值篩選出染色體CH1 st和染色體CH2 nd中最優(yōu)質(zhì)的個體,用作下一輪的迭代計算，同時迭代計數(shù)執(zhí)行加1操作.

4 效益評估

4.1 實驗環(huán)境

部署遷置優(yōu)化算法的測評平臺是在Cloudsim云模擬平臺[17]上.為使該平臺更好地適應于遷置優(yōu)化算法的評估,需事先將六個類進行相關擴展.一般而言,云計算系統(tǒng)通?？商峁M足各種需求的物理主機服務器，所以用于實施測評的物理主機服務器資源容量等配置也需要多樣化.相關研究[18]顯示，當物理主機服務器的中央處理器處于閑置休眠狀態(tài)時所消耗的能源可達到滿載狀態(tài)時能耗的七成，所對應的功耗約220 W.為了考查遷置優(yōu)化算法相對于傳統(tǒng)研究方案中遺傳算法和優(yōu)先適應機制在應對虛擬機提請安置計算請求方面的優(yōu)勢，同時體現(xiàn)資源計算請求的多元化，本次測試分別設立了[100,200,300,400,500,600]6種不同載荷規(guī)模分布的虛擬機反復運行測試30次，再統(tǒng)計測試數(shù)據(jù)的均值.同時假設每個物理主機服務器容納4個虛擬機.虛擬機的配置分別是：帶寬(度量單位：GBs/day)∈[1,2,2,4]、中央處理器(度量單位：MIPS)∈[1K,2K,3K,5K]、內(nèi)存(度量單位：GB)∈[4,8,16,24].

4.2 效益分析

目前許多關于遺傳算法的延伸研究都是在傳統(tǒng)遺傳算法基礎上優(yōu)化而來，正如文獻[6,8]研討的兩種改進型研討方案.因此業(yè)界經(jīng)常將遺傳算法作為參照標準用于衡量各類改進算法的實施成效.此外，優(yōu)先適應機制是一種常用作部署虛擬機安置的啟發(fā)式算法.基于此，筆者通過4個指標對比遺傳算法、優(yōu)先適應機制、遷置優(yōu)化算法來凸顯各自方案效益.

圖1和圖2描述了3種研究方案在受理虛擬機提請安置計算請求時整個云計算環(huán)境下的數(shù)據(jù)中心資源調(diào)度情況.所統(tǒng)計的數(shù)據(jù)主要考查在安置請求規(guī)模逐漸遞增的情形下3種研究方案實施調(diào)度計算期間的性能差異性以及性能總體趨勢.根據(jù)前文方案設計的思想以及方案實施的過程所述可知，相對于遺傳算法和優(yōu)先適應機制，遷置優(yōu)化算法在實施虛擬機安置時不僅考慮到目標物理宿機選取(即：優(yōu)質(zhì)基因分析)的合理性，還考慮到了編碼和交叉環(huán)節(jié)中盡可能地減少CH2 nd染色體(即：物理主機服務器節(jié)點)的冗余規(guī)模.遷置優(yōu)化算法的這些思想均填補了傳統(tǒng)遺傳算法和優(yōu)先適應機制的改進空間.因此從圖1、2所收集的數(shù)據(jù)不難看出，部署策略曲線走勢表現(xiàn)出了與遺傳算法和優(yōu)先適應機制的相對性優(yōu)勢.顯著地提高了云計算數(shù)據(jù)中心綜合資源使用率，最小化被喚醒的物理主機服務器參與到策略中.由于每個物理主機服務器資源有限，故隨著提請安置計算請求的虛擬機的規(guī)模持續(xù)增加，勢必要有更多物理主機服務器被喚醒參與到響應計算請求的行列中.這種規(guī)律是所有研究方案都會存在的.所以圖2所示的3條曲線走勢呈線性遞增.隨著負載增加，遷置部署策略在編碼、選取、遺傳環(huán)節(jié)的優(yōu)勢愈加明顯，因此資源使用情況愈發(fā)良好.故圖1所示曲線在虛擬機規(guī)模達到300個后效益更加凸顯.

云計算系統(tǒng)中物理機負載失衡與否也是考量優(yōu)化成效的重要指標.圖3所示曲線即表述了在發(fā)起遷置請求虛擬機規(guī)模保持相同的前提下，3種研究方案所表現(xiàn)出的載荷失衡嚴重程度.對于優(yōu)先適應機制而言，其思想為首先按照資源請求數(shù)量對虛擬機實行降序排序，一旦找到符合作為目的物理宿機要求的物理主機便開始停止后續(xù)搜尋，既便所求解具備全局性也極具偶然性.遺傳算法通過編碼、選擇等4個環(huán)節(jié)雖然在一定程度上促進了云計算系統(tǒng)數(shù)據(jù)中心的服務性能，但受限于編碼環(huán)節(jié)的復雜和冗余困擾而不具備普適性[19].因此這2種研究方案存在的問題很容易使負載集中于某些特定的物理主機服務器上引發(fā)負載失衡問題.而本文研究目標正是將這些欠周之處作為遷置優(yōu)化算法的改造空間.

圖2 3種方案的服務器喚醒情況

圖3 3種方案的失衡情況

相對而言，實施遷置優(yōu)化算法后云計算數(shù)據(jù)中心參與遷置虛擬機的物理主機服務器規(guī)模最小，且該算法在重載情形下的資源使用率最優(yōu).而節(jié)能成效高低與否完全取決于整個云數(shù)據(jù)中心參與工作的物理主機數(shù)量以及主機內(nèi)所定義的各類資源利用率.相對于遷置優(yōu)化算法而言，遺傳算法和優(yōu)先適應機制下被激活的工作主機服務器數(shù)量較多，加之相對較低的資源利用率所造成的浪費，都需要為此付出較高的能源代價.甚至于相關研究[20]也表明了虛擬機放置過程中云計算數(shù)據(jù)中心若無法應對物理主機節(jié)點載荷隨機波動和動態(tài)虛擬放置請求時，物理主機將出現(xiàn)頻繁開關機.這必然使得原本凸顯的能耗問題被進一步加劇.據(jù)此分析，占相對優(yōu)勢的遷置優(yōu)化算法所對應的能源消耗最低.正如圖4所示的數(shù)據(jù)曲線走勢，充分說明了該問題.隨著虛擬安置請求的增加，用于響應該計算的開銷資源也需同步增加，需要為開銷和主機供給更多的能源.故曲線走勢依舊總體呈現(xiàn)遞增趨勢.

圖4 3種方案的能源消耗情況

5 結論

筆者從科學的角度為云計算環(huán)境中的虛擬機構思一種遷置優(yōu)化算法以實現(xiàn)高效率的資源調(diào)度.該算法在總結傳統(tǒng)研究方案改進空間的基礎上，以綠色指標為導向探討了一種通過對優(yōu)質(zhì)的物理主機節(jié)點展開科學性評估后再用于高效地實施虛擬機遷置請求.測試表明，所研究的算法在應對云計算資源調(diào)度中具有切實的有效性與可行性.