黃金鳳

(福建船政交通職業(yè)學(xué)院，福建 福州 350007)

0 引言

現(xiàn)有的云數(shù)據(jù)中心環(huán)境主要是由物理服務(wù)器組成。近年來，由于“互聯(lián)網(wǎng)+”和大數(shù)據(jù)等各類技術(shù)的推廣而產(chǎn)生的海量數(shù)據(jù)，加劇了云數(shù)據(jù)中心環(huán)境的負(fù)載。這對(duì)云環(huán)境中的物理計(jì)算資源響應(yīng)度而言無疑是一個(gè)嚴(yán)峻的挑戰(zhàn)。虛擬服務(wù)器節(jié)點(diǎn)計(jì)算資源被業(yè)界視為解決該問題的最佳途徑之一，也就是一個(gè)物理服務(wù)器節(jié)點(diǎn)可根據(jù)云端用戶提請(qǐng)的任務(wù)請(qǐng)求規(guī)模在某一時(shí)刻為該任務(wù)釋放虛擬計(jì)算資源。為使云環(huán)境中的虛擬計(jì)算資源更高效地服務(wù)于云用戶任務(wù)請(qǐng)求，遺傳算法成為研究熱點(diǎn)。諸如，杜艷明等[1]構(gòu)思了一種基于業(yè)務(wù)優(yōu)先級(jí)的云任務(wù)調(diào)度算法，該算法旨在充分利用遺傳算法優(yōu)質(zhì)基因選擇的思路，為不同優(yōu)先級(jí)的云任務(wù)適配最合適的虛擬資源節(jié)點(diǎn)，以開展基于QoS約束的海量數(shù)據(jù)云計(jì)算，但并未提及云任務(wù)的時(shí)間代價(jià)控制思路。為解決該問題，鄭迎鳳等[2]設(shè)計(jì)了一種基于時(shí)效的云任務(wù)分配算法，該算法通過優(yōu)化遺傳算法迭代效率，降低迭代計(jì)算頻率，同時(shí)設(shè)計(jì)最小化云任務(wù)計(jì)算在時(shí)間上的目標(biāo)函數(shù)，來縮短云任務(wù)的執(zhí)行時(shí)間，然而卻忽略了云環(huán)境中不同的虛擬服務(wù)器節(jié)點(diǎn)，因個(gè)體差異可能導(dǎo)致任務(wù)在接受云計(jì)算后的反饋時(shí)間也存在差異性。針對(duì)此不足，侯松[3]提出了一種基于雙層約束的遺傳算法(IGA)，該算法在交叉變異環(huán)節(jié)引入測(cè)算因子，為云用戶任務(wù)引入多云環(huán)境。通過調(diào)度多個(gè)虛擬資源節(jié)點(diǎn)來平衡云系統(tǒng)負(fù)載并降低云任務(wù)的執(zhí)行時(shí)間，但依舊未顧及單個(gè)虛擬服務(wù)器節(jié)點(diǎn)計(jì)算資源在特定時(shí)間內(nèi)響應(yīng)該云任務(wù)而引發(fā)的損耗問題。顯然相關(guān)主流研究在基于遺傳算法優(yōu)勢(shì)的基礎(chǔ)上，即便做出了改進(jìn)也僅是片面地解決了云任務(wù)計(jì)算的時(shí)效性和資源的均衡性，甚至針對(duì)收斂過早的情形也未展開相關(guān)探討，這難以實(shí)質(zhì)性地提高云計(jì)算提供商的效益。為此本文在經(jīng)典的遺傳算法基礎(chǔ)上提出一種基于效益的虛擬云計(jì)算研究(PVC)。

1 效益模型

為使效益最大化，云數(shù)據(jù)中心通常將待計(jì)算的云業(yè)務(wù)分化成多個(gè)彼此無關(guān)的子模塊，并使虛擬服務(wù)器上的虛擬計(jì)算[4]資源分別映射至各個(gè)子模塊，待各子模塊經(jīng)過虛擬計(jì)算響應(yīng)后再整體輸出虛擬云計(jì)算值。然而，云數(shù)據(jù)中心環(huán)境內(nèi)各物理服務(wù)器計(jì)算性能的差異特征所引發(fā)的虛擬計(jì)算資源差異化，導(dǎo)致了云數(shù)據(jù)中心受理子模塊的云計(jì)算時(shí)間成本不一。并且基于差異特征的虛擬服務(wù)器在特定時(shí)間內(nèi)通過映射其虛擬資源來計(jì)算一個(gè)子模塊所引發(fā)的損耗代價(jià)也不盡相同。顯然，云計(jì)算提供商獲取良好收益的思想是使虛擬服務(wù)器為多個(gè)不相關(guān)的子模塊同時(shí)提供虛擬計(jì)算資源。

將t和p分別表示虛擬服務(wù)器v執(zhí)行子模塊m所需的時(shí)間成本和損耗代價(jià)，將pv表征為v的個(gè)體成本，則損耗代價(jià)記為

p=tpv.

(1)

假設(shè)云端用戶向云數(shù)據(jù)中心環(huán)境提請(qǐng)的云業(yè)務(wù)規(guī)模為K，云業(yè)務(wù)的子模塊規(guī)模為x，第c個(gè)云業(yè)務(wù)中的子模塊m的數(shù)據(jù)長度為Lcm，虛擬服務(wù)器規(guī)模為y，第v個(gè)虛擬服務(wù)器所能提供的虛擬計(jì)算能力為Cv，于是有1≤m≤x、1≤v≤y。進(jìn)而求得時(shí)間成本的值為

(2)

(3)

假設(shè)虛擬服務(wù)器承載云業(yè)務(wù)的成本為pvt，可得云用戶提請(qǐng)的云業(yè)務(wù)待響應(yīng)代價(jià)為

(4)

2 云計(jì)算方案構(gòu)建

對(duì)于云計(jì)算提供商而言，效益最大化才是其投資的最大目標(biāo)。因遺傳[5]算法具有普適性評(píng)估、優(yōu)勝劣汰、交叉變異等優(yōu)勢(shì),使得該算法在部署海量任務(wù)的云計(jì)算時(shí)，可在云系統(tǒng)能耗、云資源博弈、云帶寬配置[6]等方面表現(xiàn)出良好成效。但即便如此，遺傳算法依然因其固有的某些缺陷使其應(yīng)用在復(fù)雜的云任務(wù)計(jì)算中無法發(fā)揮應(yīng)有的優(yōu)化作用。諸如，傳統(tǒng)意義上的遺傳算法對(duì)于初代染色體的序列依賴度較高，以致于收斂太早搜索成效太低。顯然這樣的情形并不利于云計(jì)算提供商精確地測(cè)評(píng)云計(jì)算執(zhí)行時(shí)間成本和損耗代價(jià)等事務(wù)性指標(biāo)?；诖?，本文研究一種基于云任務(wù)受理成本和時(shí)間約束的高效益云計(jì)算方案，整個(gè)方案流程如圖1所示。

首先隨機(jī)創(chuàng)建一個(gè)規(guī)模為N的種群，通過為每一個(gè)個(gè)體開展普適性評(píng)估來提取出位列所有種群前5%的優(yōu)質(zhì)個(gè)體遺傳到后代繼續(xù)用作種群，同時(shí)設(shè)計(jì)輪詢機(jī)制對(duì)剩余的95%個(gè)體開展擇優(yōu)選用。然后讓兩個(gè)隨機(jī)個(gè)體執(zhí)行交叉，從而獲得全新的子代個(gè)體種群。在此期間優(yōu)質(zhì)個(gè)體將被保留，劣質(zhì)個(gè)體將被淘汰。最后通過設(shè)計(jì)變異適應(yīng)函數(shù)來評(píng)估個(gè)體的普適性。此舉旨在預(yù)防優(yōu)質(zhì)個(gè)體發(fā)生劣變。

云數(shù)據(jù)中心環(huán)境創(chuàng)建g個(gè)染色體。每個(gè)染色體的長度為x，即云任務(wù)的子模塊規(guī)模。根據(jù)前文描述，每個(gè)子模塊將由虛擬服務(wù)器為其映射一個(gè)虛擬計(jì)算資源。于是本次編/解碼環(huán)節(jié)的設(shè)計(jì)便是基于虛擬計(jì)算資源和待計(jì)算的云任務(wù)之間一種關(guān)于映射關(guān)系的編/解碼設(shè)計(jì)。染色體的基因參量不超過虛擬資源規(guī)模y。比如，虛擬服務(wù)器為染色體3、2、4、5、3、4、1、3、5、2、1、2、3映射五個(gè)虛擬計(jì)算資源。則五個(gè)虛擬計(jì)算資源節(jié)點(diǎn)所映射的子模塊分別為v1={7,11}、v2={2,10,12}、v3={1,5,8,13}、v4={3,6}、v5={4,9}。不難統(tǒng)計(jì)出五個(gè)虛擬服務(wù)器的虛擬計(jì)算資源所要計(jì)算的云任務(wù)數(shù)量分別是2、3、4、2、2。

為從根源上提升后代遺傳基因質(zhì)量，算法需引入普適性指標(biāo)，從初代開始評(píng)估最適合用作繼承的個(gè)體。由于本研究目標(biāo)在于提升云計(jì)算服務(wù)提供商的效益，故將待計(jì)算的云業(yè)務(wù)受理時(shí)長和受理代價(jià)作為普適性的目標(biāo)函數(shù)。受理云業(yè)務(wù)計(jì)算的損耗代價(jià)普適性目標(biāo)函數(shù)值和種群個(gè)體損耗代價(jià)成反比。這一過程表示如下：

(5)

圖1 高效益云計(jì)算方案流程

倘若云數(shù)據(jù)中心受理云業(yè)務(wù)的時(shí)間成本較低，則損耗代價(jià)普適性目標(biāo)值越大；倘若云數(shù)據(jù)中心受理云業(yè)務(wù)的時(shí)間成本太高，則目標(biāo)值A(chǔ)α越小。因此，損耗代價(jià)普適性目標(biāo)值和云業(yè)務(wù)受理時(shí)長息息相關(guān)。令云數(shù)據(jù)中心受理云業(yè)務(wù)的最大時(shí)長為TH，則受理云業(yè)務(wù)計(jì)算的時(shí)間成本普適性目標(biāo)函數(shù)記作：

(6)

同理，當(dāng)云數(shù)據(jù)中心受理該云業(yè)務(wù)時(shí)間成本越低，該方案所對(duì)應(yīng)的時(shí)間成本普適性目標(biāo)值A(chǔ)α越大；反之，若該受理方案對(duì)應(yīng)的Aα值越小，意味著該方案值并非全局最優(yōu)解。

但由于算法在遺傳后期的迭代計(jì)算中會(huì)使個(gè)種群個(gè)體逐漸趨于一致。這樣的情形容易引發(fā)所求解僅局限于某一個(gè)局部范圍內(nèi)，若推廣到云數(shù)據(jù)中心將導(dǎo)致該解在整個(gè)云數(shù)據(jù)中心環(huán)境下缺乏普適性。為避免該情形定義差異化因子d作為遺傳后期的個(gè)體區(qū)分。根據(jù)前文所述,云業(yè)務(wù)的子模塊數(shù)據(jù)長度即為基因長度，記作n?；蚍讲钣涀鳎?/p>

Δz=Jmz-Jvz,

(7)

其中，Jmz和Jvz表示位于相同位置的兩個(gè)基因的值。

則有

(8)

由于云計(jì)算服務(wù)提供商的效益是基于時(shí)間成本和損耗代價(jià)的約束來實(shí)現(xiàn)，同時(shí)為了避免優(yōu)質(zhì)個(gè)體的偶然性對(duì)全局事件的影響，首先淘汰普適性參量較大的前3‰個(gè)體，然后將緊隨其后的5%個(gè)體選作次代種群個(gè)體，再采用輪詢算法篩選余下的個(gè)體。鑒于部分染色體基因在優(yōu)勝劣汰環(huán)節(jié)遭遇不可避免的舍棄，并由此引發(fā)種群粒子規(guī)模的頻繁波動(dòng)，算法在部署前需選用一些普適性較為貼近的個(gè)體作為補(bǔ)充以保持種群個(gè)體規(guī)模相對(duì)穩(wěn)定。將所篩選出來的個(gè)體和交叉變異后的個(gè)體組建出一代新的個(gè)體種群。

(9)

(10)

3 云計(jì)算實(shí)施方案

根據(jù)前文云業(yè)務(wù)部署步驟，以效益為目標(biāo)實(shí)施云計(jì)算時(shí)，應(yīng)由云數(shù)據(jù)中心環(huán)境產(chǎn)生初代粒子個(gè)體并開展個(gè)體普適性評(píng)估，隨后啟動(dòng)優(yōu)勝劣汰執(zhí)行交叉變異最終收斂出一個(gè)全局最佳值。據(jù)此思路，云計(jì)算實(shí)施步驟如下：

4 實(shí)驗(yàn)分析與論證

4.1 實(shí)驗(yàn)設(shè)置

部署遺傳算法時(shí)，首先要將種群規(guī)模初始化為N=45。云數(shù)據(jù)中心服務(wù)器將所要受理的云業(yè)務(wù)劃分為1 500個(gè)子模塊，即x=1 500個(gè)。并為其映射15個(gè)虛擬計(jì)算資源，即y=15。迭代計(jì)算頻次上限至200次。其次，交叉和變異環(huán)節(jié)中的各參量初始化為o1=30×10-1，o2=3，o3=3×10-2，o4=3×10-2，pth=2×10-2。為凸顯本文所研究PVC算法的先進(jìn)性，本次選用前文所述的IGA算法作為對(duì)比。通過考察兩個(gè)算法受理云業(yè)務(wù)計(jì)算的時(shí)間成本和損耗[10]代價(jià)來驗(yàn)證PVC算法方案的科學(xué)性。

4.2 實(shí)驗(yàn)結(jié)果分析

圖2所示曲線為兩種改進(jìn)型遺傳算法在受理云用戶提請(qǐng)的云業(yè)務(wù)計(jì)算時(shí)所產(chǎn)生的損耗代價(jià)情況。整個(gè)云業(yè)務(wù)被劃分成1 500個(gè)子任務(wù)模塊，分別由IGA算法和PVC算法來受理。兩種算法在迭代計(jì)算初始所產(chǎn)生的資源損耗代價(jià)較為接近。隨著迭代頻次遞增兩種算法下的損耗代價(jià)均有不同程度下降。但由于PVC算法引入了損耗代價(jià)普適性函數(shù)用于評(píng)估個(gè)體值在全局范圍內(nèi)的適應(yīng)性，并且在交叉變異環(huán)節(jié)進(jìn)一步優(yōu)化了繼承的基因，這恰好是IGA算法所不具備的優(yōu)勢(shì)。故隨著迭代頻次逐漸增加，PVC算法下的云資源損耗代價(jià)曲線降幅趕超IGA的降幅。至此，PVC算法表現(xiàn)出了相對(duì)優(yōu)勢(shì)。

圖2 受理云業(yè)務(wù)計(jì)算的損耗代價(jià)

圖3 受理云業(yè)務(wù)計(jì)算的時(shí)間成本

圖3所示曲線為兩種改進(jìn)型遺傳算法在受理云用戶提請(qǐng)的云業(yè)務(wù)計(jì)算時(shí)所需的時(shí)間成本情況。由圖中曲線不難看出，兩種算法在對(duì)云環(huán)境中的1 500個(gè)子任務(wù)開展虛擬云計(jì)算所消耗的時(shí)間成本各不相同。總體而言，算法的時(shí)間成本均和迭代計(jì)算頻次成反比。這是由于兩個(gè)算法都是基于遺傳算法思想演進(jìn)而來。遺傳算法思想是通過迭代計(jì)算方式不斷進(jìn)化出優(yōu)質(zhì)后代收斂出較好的值，從而降低算法后續(xù)計(jì)算的復(fù)雜度。從圖中曲線可以看出，受理業(yè)務(wù)的云計(jì)算初期兩種算法的時(shí)間成本相差無幾。但隨著云計(jì)算頻次的增加，兩種基于遺傳算法的優(yōu)勢(shì)均得到明顯體現(xiàn)，所產(chǎn)生的時(shí)間成本均顯著下降。相比之下，本文研究的PVC算法在實(shí)施云業(yè)務(wù)計(jì)算時(shí)更好地做到了對(duì)時(shí)間成本的把控。究其原因是PVC算法針對(duì)種群個(gè)體單獨(dú)設(shè)計(jì)了時(shí)間成本普適性評(píng)估函數(shù)。同時(shí)，PVC算法在交叉變異環(huán)節(jié)再次開展優(yōu)質(zhì)個(gè)體基因的評(píng)測(cè)，為后續(xù)收斂速度和精度均奠定了良好的基礎(chǔ)，該設(shè)計(jì)理念正是IGA算法所欠缺的。故本組測(cè)試論證了PVC算法的相對(duì)優(yōu)勢(shì)。

5 結(jié)語

本文圍繞云數(shù)據(jù)中心環(huán)境開展云業(yè)務(wù)計(jì)算時(shí)引發(fā)的計(jì)算時(shí)間和計(jì)算代價(jià)問題提出一種新型云計(jì)算方案，根據(jù)該方案設(shè)計(jì)的普適性評(píng)估機(jī)制、優(yōu)勝劣汰機(jī)制和擇優(yōu)變異機(jī)制均在一定程度上提升了子代個(gè)體的遺傳質(zhì)量。從實(shí)驗(yàn)數(shù)據(jù)不難看出，子代個(gè)體的普適性函數(shù)值具有良好的全局性，同時(shí)云環(huán)境下大量子任務(wù)的虛擬云計(jì)算指標(biāo)也驗(yàn)證了本文算法方案的優(yōu)勢(shì)。這些良好的表現(xiàn)使得本文算法在部署海量業(yè)務(wù)的虛擬云計(jì)算時(shí)，可有效地降低云數(shù)據(jù)中心的損耗代價(jià)，壓縮云計(jì)算時(shí)間成本，這無疑可為云計(jì)算服務(wù)提供商帶來可觀的效益。