鄧有林

摘 要： 針對大型Web網(wǎng)絡(luò)數(shù)據(jù)中心資源共享存在資源分配失衡和利用率低等問題，提出基于多維資源協(xié)調(diào)聚合的分組遺傳資源挖掘算法。將Web網(wǎng)絡(luò)數(shù)據(jù)中心資源共享矛盾看成是多維資源聚合數(shù)學(xué)模型，通過基于模糊邏輯的多維協(xié)同適應(yīng)度函數(shù)對關(guān)鍵算子實(shí)施選擇和多屬性決策優(yōu)化，提升工作效率和求解質(zhì)量。最后通過分組遺傳虛擬機(jī)調(diào)度算法得到最佳虛擬機(jī)調(diào)度結(jié)果，實(shí)現(xiàn)數(shù)據(jù)中心資源的均衡分配。實(shí)驗(yàn)結(jié)果表明，該算法能夠提升數(shù)據(jù)中心資源綜合利用率，運(yùn)行效率較高，可完成資源的均衡分配。

關(guān)鍵詞： Web網(wǎng)絡(luò)； 分組遺傳； 數(shù)據(jù)挖掘； 中心資源； 概率排序； 運(yùn)行效率

中圖分類號(hào)： TN911.1?34； TP308 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）03?0120?04

Abstract： The resource sharing of large Web network data center has imbalance resource allocation and low utilization rate. Therefore， a grouping genetic resources mining algorithm based on multidimensional resource coordination aggregation is put forward. Taking the resource sharing contradiction of Web network data center as the mathematic model of multidimensional resource aggregation， the multidimensional coordination fitness function based on fuzzy logic is used to select the key operator and optimize the multi?attribute decision?making， which can improve the working efficiency and solution quality. The best virtual machine scheduling result is obtained by means of the grouping genetic virtual machine scheduling algorithm to realize the equilibrium allocation of the data center resources. The experimental results indicate that the proposed algorithm can improve the comprehensive utilization of data center resources and realize the equilibrium allocation of resources， and has high running efficiency.

Keywords： Web network； grouping inheritance； data mining； center resource； probabilistic ranking； running efficiency

隨著信息技術(shù)的快速發(fā)展，大型Web網(wǎng)絡(luò)的應(yīng)用價(jià)值也逐漸提升，其中，數(shù)據(jù)中心是網(wǎng)絡(luò)信息服務(wù)的關(guān)鍵平臺(tái)?？焖侔l(fā)展的信息導(dǎo)致網(wǎng)絡(luò)以及業(yè)務(wù)應(yīng)用逐漸向具有大量服務(wù)器以及大型數(shù)據(jù)中心轉(zhuǎn)移，導(dǎo)致數(shù)據(jù)中心規(guī)模不斷提高，使得其中的異構(gòu)應(yīng)用同統(tǒng)一資源池共享間的矛盾不斷加深，使得資源使用率降低。因此，尋求有效的方法實(shí)現(xiàn)大型Web網(wǎng)絡(luò)數(shù)據(jù)中心資源高效挖掘，提升資源綜合利用率，具有重要應(yīng)用價(jià)值。本文提出基于多維資源協(xié)同聚合的分組遺傳資源挖掘算法，實(shí)現(xiàn)大型Web網(wǎng)絡(luò)數(shù)據(jù)中心資源的高效挖掘。

1 多維資源協(xié)調(diào)聚合的分組遺傳資源挖掘算法

1.1 多維資源聚合數(shù)學(xué)模型

本文算法將Web網(wǎng)絡(luò)數(shù)據(jù)中心的異構(gòu)應(yīng)用同統(tǒng)一資源池共享間的矛盾看成是多維資源聚合數(shù)學(xué)模型。設(shè)置用來描述大型Web網(wǎng)絡(luò)數(shù)據(jù)中心待調(diào)度的應(yīng)用數(shù)量，調(diào)度個(gè)應(yīng)用，這些應(yīng)用通過虛擬機(jī)完成資源的分配。因此，可將應(yīng)用看成虛擬機(jī)申請，用描述。數(shù)據(jù)中心包含臺(tái)物理服務(wù)器，為虛擬機(jī)提供資源服務(wù)。設(shè)置機(jī)器集為。因?yàn)榇笮蚖eb網(wǎng)絡(luò)數(shù)據(jù)中心中存在的調(diào)度資源種類繁多，本文向多維資源聚合數(shù)學(xué)模型中融入資源維度的概念。

如果對種類資源的需求量是，則其申請向量是。服務(wù)器在不同維度中擁有的資源量也存在較高的差異，表示資源提供的服務(wù)性能向量，其可描述網(wǎng)絡(luò)數(shù)據(jù)中心不同維度中服務(wù)器的資源量。服務(wù)器在資源種類維度的綜合利用率為。調(diào)度方案的輸出是一個(gè)分配矩陣用于描述該方案向服務(wù)器中劃分該虛擬機(jī)

將上述分析的問題看成是組合優(yōu)化過程中的裝箱問題，對其進(jìn)行多維建模[1]。將大型Web網(wǎng)絡(luò)中心資源挖掘的多維聚合問題映射成多維協(xié)同的可變向量裝箱模型。

式（1）的目標(biāo)是在多維環(huán)境下確保最小化啟用物理服務(wù)器多維資源的均衡分配，確保多維資源綜合利用率的最大化。式（2）可確保各物理服務(wù)器資源分配低于其最大容量。式（3）確保虛擬機(jī)申請實(shí)例僅被調(diào)度一次。

1.2 多維資源協(xié)同聚合的分組遺傳虛擬機(jī)調(diào)度算法

基于1.1節(jié)的分析能夠看出，大型Web網(wǎng)絡(luò)數(shù)據(jù)中心資源的虛擬機(jī)調(diào)度是一種決策過程，需要分析多維資源間的均衡調(diào)度，實(shí)現(xiàn)最大化綜合利用率、最小化物理機(jī)使用數(shù)的目標(biāo)。為了解決上述分析的可變向量裝箱模型，提出基于多維資源協(xié)同聚合的分組遺傳虛擬機(jī)調(diào)度算法，得到最佳虛擬機(jī)調(diào)度結(jié)果，并基于分組遺傳算法框架，通過基于模糊邏輯的多維協(xié)同適應(yīng)度函數(shù)，對關(guān)鍵算子實(shí)施基于概率選擇以及多屬性決策的優(yōu)化，提升調(diào)度算法的效率和求解質(zhì)量[2]。endprint

用于描述服務(wù)器內(nèi)種類的資源利用率，表示服務(wù)器中全部資源的平均利用率，則服務(wù)器的綜合利用率為其表達(dá)式為：

為了向優(yōu)質(zhì)解內(nèi)反饋多維協(xié)同的均衡調(diào)度結(jié)果，設(shè)置基因評(píng)估參量其包括服務(wù)器綜合利用率和資源利用率的多維方差[3]。

依照對基因評(píng)估參數(shù)的描述，基因評(píng)估值高說明對應(yīng)的綜合資源利用率高、對應(yīng)的不同維度間的利用率偏差低，進(jìn)而確保各基因具有多維協(xié)同的聚合效應(yīng)。

1.2.1 基于模糊邏輯的多維協(xié)同適應(yīng)度函數(shù)

基于多維間的協(xié)同關(guān)系確保多維資源的均衡性，使得資源綜合利用率最高，確保啟用物理機(jī)的數(shù)量最小化。通常具有最高適應(yīng)度函數(shù)值的個(gè)體將基因遺傳到后代的概率更高，因此，應(yīng)確保優(yōu)質(zhì)個(gè)體基因的性能也是優(yōu)良的，通過適應(yīng)度函數(shù)綜合分析啟用物理機(jī)數(shù)量和多維資源的均衡度[4]。

從式（5）能夠獲取單個(gè)基因位的評(píng)估參量，進(jìn)而得到單個(gè)服務(wù)器的綜合利用率和資源均衡度。由多個(gè)基因位組成的個(gè)體染色體（虛擬機(jī)調(diào)度的可行解），應(yīng)先設(shè)置分析個(gè)體優(yōu)劣的兩個(gè)關(guān)鍵指標(biāo)，也就是物理機(jī)需求量以及多維資源的均衡度，將其當(dāng)成調(diào)度過程的宏觀均衡指標(biāo)。

設(shè)置代表的二元真值，虛擬機(jī)調(diào)度分配方案的矩陣秩為，也就是需要進(jìn)行調(diào)度的服務(wù)器量，這時(shí)的宏觀均衡指標(biāo)為：

本文通過基于Max?Min原則的加權(quán)模糊邏輯決策手段，對雙因素評(píng)估進(jìn)行匯總和量化分析。

設(shè)置以及是成員變量以及的權(quán)重[5]，兩個(gè)成員變量的隸屬度是以及，隸屬度的真值同兩個(gè)變量的隸屬函數(shù)值一致，能夠得到Max?Min加權(quán)模糊邏輯的真值公式為：

將上述得到的真值運(yùn)算結(jié)果當(dāng)成多維分組遺傳算法內(nèi)的適應(yīng)度函數(shù)值，選擇算子基于該適應(yīng)度函數(shù)值分析種群內(nèi)個(gè)體優(yōu)劣，獲取新群體。

1.2.2 選擇算子機(jī)理

遺傳算法通過選擇算子將父代種群內(nèi)的優(yōu)質(zhì)個(gè)體遺傳到子代種群中。選擇算子基于1.2.1節(jié)獲取的適應(yīng)度函數(shù)值評(píng)估各個(gè)體，再基于相應(yīng)的方式對個(gè)體實(shí)施排序和選擇處理[6]。采集擁有高適應(yīng)度值的個(gè)體，能夠確保算法收斂到局部最佳解，無法獲取全局最佳解。因此，本文通過輪盤賭選擇法基于個(gè)體的選擇概率運(yùn)算累積概率，選擇最佳個(gè)體。

通過式（7）描述的適應(yīng)度函數(shù)運(yùn)算出單個(gè)個(gè)體的適應(yīng)度和種群適應(yīng)度的總和。通過占總和比例的方法運(yùn)算獲取種群內(nèi)各個(gè)體的相對適應(yīng)度值，將該適應(yīng)度值當(dāng)成相應(yīng)個(gè)體的選擇概率，則第個(gè)個(gè)體的累積概率是。形成0～1間的隨機(jī)數(shù)同進(jìn)行對比分析[7]，如果有則采用第個(gè)個(gè)體。如此循環(huán)輪獲取個(gè)子代個(gè)體。該種選擇方法運(yùn)行效率高，可確保向后代遺傳擁有最高適應(yīng)度值的個(gè)體。

1.2.3 基于概率排序的交叉位選擇優(yōu)化

本文算法采用依據(jù)概率排序的交叉位選擇優(yōu)化方法，基于父代染色體的各基因評(píng)估值，融入可控產(chǎn)生的概率函數(shù)，在確保高評(píng)估值基因的前提下，實(shí)現(xiàn)全局搜索的隨機(jī)性[8]。

對染色體中各基因依據(jù)評(píng)估值進(jìn)行降序排列獲取用于描述處于第位的基因（服務(wù)器）的評(píng)估值。用于描述該染色體在解區(qū)域相關(guān)聯(lián)的驅(qū)動(dòng)服務(wù)器量。因此，設(shè)置各基因成為交叉位的被選擇概率滿足的分布函數(shù)為：

式中用于描述排序基因的選擇概率。

能夠看出擁有高評(píng)估值的基因被選擇運(yùn)行交叉處理的概率也高，該種選擇模式能夠確保全局檢索穩(wěn)定地繼承父代有效模式，形成優(yōu)良個(gè)體。本文基于經(jīng)驗(yàn)設(shè)置可變參數(shù)值為2。

1.3 多維資源協(xié)調(diào)聚合的分組遺傳資源挖掘算法流程

本文資源挖掘算法開始運(yùn)行時(shí)，應(yīng)對種群實(shí)施初始化設(shè)置，對Web網(wǎng)絡(luò)數(shù)據(jù)中心內(nèi)的候選虛擬機(jī)進(jìn)行隨機(jī)排列，采用多維優(yōu)先適應(yīng)算法向服務(wù)器分配虛擬機(jī)，循環(huán)種群規(guī)模次產(chǎn)生原始種群。當(dāng)算法停止規(guī)范符合設(shè)置的迭代次數(shù)時(shí)輸出具有最佳適應(yīng)度函數(shù)值的個(gè)體[9]，最終通過解碼變換獲取最佳虛擬機(jī)調(diào)度結(jié)果，實(shí)現(xiàn)Web網(wǎng)絡(luò)數(shù)據(jù)中心資源的均衡挖掘。詳細(xì)流程如圖1所示。

2 仿真實(shí)驗(yàn)

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

為了驗(yàn)證本文算法能夠提升大型Web網(wǎng)絡(luò)數(shù)據(jù)中心的資源利用率，通過實(shí)驗(yàn)檢測本文算法和服務(wù)器聚合算法挖掘網(wǎng)絡(luò)資源的性能。服務(wù)器聚合算法是一種優(yōu)先適應(yīng)啟發(fā)式方法。實(shí)驗(yàn)采用的服務(wù)器具有8 GHz主頻、4核CPU、16 GB內(nèi)存。虛擬機(jī)內(nèi)各維資源相互獨(dú)立，設(shè)置工作負(fù)載規(guī)模分別是200，400，600，800和1 200個(gè)虛擬機(jī)的5種實(shí)例。設(shè)置本文算法中的原始種群數(shù)量是50，算法運(yùn)行200代，交叉算子概率是20%，變異算子概率是0.5%。

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

實(shí)驗(yàn)檢測本文算法和服務(wù)器聚合算法承載不同數(shù)量虛擬機(jī)所需要的物理機(jī)器數(shù)量，結(jié)果用圖2描述。從中可得，在Web網(wǎng)絡(luò)數(shù)據(jù)中心承載不同數(shù)量虛擬機(jī)的工作負(fù)載下，本文算法所需的物理機(jī)器數(shù)量始終小于服務(wù)器聚合算法，主要是因?yàn)楸疚乃惴ň哂休^高的多維均衡性，可獲取最佳的資源投入性能，承載相同虛擬機(jī)申請時(shí)所需的物理機(jī)器更少，降低了建設(shè)成本。

多維資源環(huán)境中，不同種類資源的利用率均衡化能夠?qū)崿F(xiàn)綜合利用率的最大化。綜合利用率可描述物理機(jī)器使用量高低對多維協(xié)同挖掘的依賴性。實(shí)驗(yàn)檢測本文算法和服務(wù)器聚合算法對于多維資源的綜合利用率情況，用圖3描述。能夠得出，本文算法比服務(wù)器聚合算法的綜合利用率高，其在提升Web網(wǎng)絡(luò)數(shù)據(jù)中心資源利用率方面具有較強(qiáng)的促進(jìn)功能。

實(shí)驗(yàn)檢測不同挖掘算法的適應(yīng)度函數(shù)值用圖4描述。能夠得出，本文算法形成的調(diào)度方案的適應(yīng)度函數(shù)值最大，可實(shí)現(xiàn)資源的均衡分配。

實(shí)驗(yàn)檢測本文挖掘算法對大規(guī)模問題的擴(kuò)展性能，本文挖掘算法對原始種群的平均運(yùn)算時(shí)間以及獲取新種群的平均運(yùn)算時(shí)間的匯總結(jié)果，用圖5描述。從中可以得出，隨著虛擬機(jī)數(shù)量的不斷提升，本文算法獲取新種群的平均運(yùn)算時(shí)間不斷降低，說明本文算法在支撐大型Web網(wǎng)絡(luò)數(shù)據(jù)中心資源調(diào)度時(shí)具有較顯著的時(shí)間優(yōu)勢以及較高的運(yùn)行效率。endprint

3 結(jié) 論

本文提出基于多維資源協(xié)調(diào)聚合的分組遺傳資源挖掘算法，解決大型Web網(wǎng)絡(luò)數(shù)據(jù)中心的異構(gòu)應(yīng)用同統(tǒng)一資源池共享間存在的矛盾，通過基于多維資源協(xié)調(diào)聚合的分組遺傳虛擬機(jī)調(diào)度算法得到最佳虛擬機(jī)調(diào)度結(jié)果，完成數(shù)據(jù)中心資源的均衡分配，提升數(shù)據(jù)中心資源綜合利用率。

參考文獻(xiàn)

[1] 趙蓉英，魏明坤.網(wǎng)絡(luò)計(jì)量學(xué)與Web挖掘?qū)Ρ妊芯縖J].情報(bào)雜志，2016，35（3）：131?136.

ZHAO Rongying， WEI Mingkun. A comparative study on Webometrics and Web mining [J]. Journal of intelligence， 2016， 35（3）： 131?136.

[2] 張麗曄，彭健，鄭小鵬，等.試驗(yàn)數(shù)據(jù)統(tǒng)一訪問技術(shù)研究與實(shí)現(xiàn)[J].計(jì)算機(jī)仿真，2014，31（9）：319?322.

ZHANG Liye， PENG Jian， ZHENG Xiaopeng， et al. Research and implementation of test data unified access technology [J]. Computer simulation， 2014， 31（9）： 319?322.

[3] 劉匯丹，諾明花，馬龍龍，等.Web藏文文本資源挖掘與利用研究[J].中文信息學(xué)報(bào)，2015，29（1）：170?177.

LIU Huidan， NUO Minghua， MA Longlong， et al. Mining Tibetan Web text resources and its application [J]. Journal of Chinese information processing， 2015， 29（1）： 170?177.

[4] 趙雪琴，付媛媛.云計(jì)算環(huán)境下大規(guī)模Web服務(wù)故障診斷技術(shù)研究[J].計(jì)算機(jī)測量與控制，2014，22（9）：2760?2762.

ZHAO Xueqin， FU Yuanyuan. Research on fault diagnosis for massive Web services in cloud computing [J]. Computer measurement & control， 2014， 22（9）： 2760?2762.

[5] 胡文紅，孫欣欣.基于時(shí)間序列的數(shù)據(jù)挖掘技術(shù)在城市內(nèi)澇災(zāi)害中的應(yīng)用研究[J].科技通報(bào)，2016，32（6）：229?231.

HU Wenhong， SUN Xinxin. Study of data mining technology in application of city water logging based on time series [J]. Bulletin of science and technology， 2016， 32（6）： 229?231.

[6] 王曙霞，熊曾剛.海量數(shù)據(jù)干擾下的危險(xiǎn)Web數(shù)據(jù)挖掘技術(shù)研究[J].微電子學(xué)與計(jì)算機(jī)，2016（2）：87?91.

WANG Shuxia， XIONG Zenggang. Huge amounts of data under the interference of dangerous Web data mining technology research [J]. Microellectronics and computer， 2016（2）： 87?91.

[7] 趙蓉英，譚潔，陳晨，等.基于社會(huì)標(biāo)簽共現(xiàn)分析的Web資源聚合流程研究[J].情報(bào)理論與實(shí)踐，2014，37（7）：111?115.

ZHAO Rongying， TAN Jie， CHEN Chen， et al. Research on Web resource aggregation process based on social tagging co?occurrence analysis [J]. Information theory and practice， 2014， 37（7）： 111?115.

[8] 陸菲菲，郭得科，方興，等.數(shù)據(jù)中心網(wǎng)絡(luò)高效數(shù)據(jù)匯聚傳輸算法[J].計(jì)算機(jī)學(xué)報(bào)，2016，39（9）：1750?1762.

LU Feifei， GUO Deke， FANG Xing， et al. Efficient data aggregation transfers in data center networks [J]. Chinese journal of computers， 2016， 39（9）： 1750?1762.

[9] 高芹，陳亞.數(shù)據(jù)挖掘中一種高效的聚類通用框架研究[J].科學(xué)技術(shù)與工程，2014，14（16）：112?118.

GAO Qin， CHEN Ya. Research on an efficient clustering ge?neral framework in data mining [J]. Science technology and engineering， 2014， 14（16）： 112?118.endprint