摘 ?要： 如何在提高云計算服務(wù)資源調(diào)度效率的同時盡量降低工作能耗，成為當(dāng)前必須解決的問題。因此，提出一種基于遺傳算法的云計算資源調(diào)度方法，適用于高校師資培訓(xùn)資源管理。首先，搭建基于云服務(wù)的高校教師師資培訓(xùn)系統(tǒng)模式;其次，利用具有較強NP問題解決能力的遺傳算法設(shè)計大規(guī)模集群的資源調(diào)度方法，并采用粒子群算法對其全局尋優(yōu)能力進行改進;最后，設(shè)計了由質(zhì)量和成本構(gòu)成的雙指標(biāo)約束適應(yīng)度函數(shù)。CloudSim平臺的Hadoop實驗仿真結(jié)果顯示，提出的遺傳云計算資源調(diào)度方法在約束條件下獲得了最佳的調(diào)度結(jié)果。

關(guān)鍵詞： 云計算; 遺傳算法; Hadoop; 資源調(diào)度; 平衡性; 調(diào)度策略

中圖分類號： TN02?34; TP393 ? ? ? ? ? ? ? ? ? ? 文獻標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）01?0157?04

Management of college teacher training based on genetic algorithm

in cloud computing of Hadoop platform

XING Lili

Abstract： How to improve the efficiency of cloud computing service resource scheduling while minimizing the energy consumption of the work as far as possible has become an issue that must be solved at present. Therefore， a cloud computing resource scheduling method based on genetic algorithm is proposed， which is suitable for the management of college teacher training resources. First of all， a cloud service based teacher training system model for college teachers is established. Secondly， a large?scale cluster resource scheduling method is designed by genetic algorithm with powerful NP problem solving ability， and its global optimization ability is improved by particle swarm optimization. Finally， a dual?index constrained fitness function consisting of quality and cost is designed. The Hadoop experimental simulation results of CloudSim platform show that the proposed genetic cloud computing resource scheduling method obtains the best scheduling results under the constraint conditions.

Keywords： cloud computing; genetic algorithm; Hadoop; resource scheduling; balance; scheduling strategy

0 ?引 ?言

自2007年以來，云計算已經(jīng)逐漸成為各個行業(yè)領(lǐng)域爭相構(gòu)建的戰(zhàn)略方向。許多基于云計算的產(chǎn)品和服務(wù)不斷被推出，計算機行業(yè)的規(guī)模和涉及的領(lǐng)域也隨之不斷拓張。云計算輔助教學(xué)（Cloud Computing Aided Instruction，CCAI）已經(jīng)成為了廣大高校和教師搭建現(xiàn)代化、信息化和個性化教學(xué)的新手段，從技術(shù)上有效提高了教學(xué)的質(zhì)量[1?2]。CCAI模式的特點十分有利于高校師資培訓(xùn)的信息化管理，降低了資金投入和維護成本，提高了網(wǎng)絡(luò)安全性，有助于構(gòu)建個性化教學(xué)環(huán)境。實際推廣應(yīng)用結(jié)構(gòu)顯示通過CCAI模式可以有效解決當(dāng)前高校師資培訓(xùn)面臨的空間限制和資源匱乏問題[3]。

近期基于CCAI模式的教學(xué)資源管理得到了較多的關(guān)注。例如，文獻[4]提出了基于云計算的高校教育資源共享服務(wù)平臺構(gòu)建研究，實現(xiàn)了按需為教師及學(xué)生提供個性化數(shù)字資源。文獻[5]討論了基于云計算的高校數(shù)據(jù)中心的設(shè)計與實現(xiàn)方案。但是，如何在提高云計算服務(wù)資源調(diào)度效率的同時盡量降低工作能耗，成為當(dāng)前必須解決的問題[5]。因此，本文提出一種基于遺傳算法的云計算資源調(diào)度方法，以便用于高校師資培訓(xùn)資源管理。Hadoop實驗仿真結(jié)果顯示，提出的遺傳云計算資源調(diào)度方法在多個約束條件下，獲得了較好的時間跨度和加速比性能。

1 ?問題描述

目前CCAI模式下如何對云計算平臺中存儲的異構(gòu)大量資源進行合理的調(diào)度是當(dāng)前急需解決的主要問題。即盡可能地提高工作效率、保證任務(wù)調(diào)度質(zhì)量，并同時盡量降低工作能耗，成為云計算任務(wù)調(diào)度領(lǐng)域研究的熱點問題。傳統(tǒng)的云計算任務(wù)調(diào)度算法包括[6]輪詢算法（Round?Robin，RR）和隨機分配算法（Random?Allocation，RA）。文獻[7]提出一種基于彈性定額值的分組輪詢調(diào)度算法，保證了數(shù)據(jù)流的公平性。文獻[8]提出一種多源協(xié)作網(wǎng)絡(luò)中輪詢節(jié)點選擇算法，通過利用率來提供更好的系統(tǒng)性能。但是上述算法在處理異構(gòu)性、動態(tài)性和大規(guī)模性的虛擬數(shù)字資源時表現(xiàn)不夠理想。

工作流程和任務(wù)調(diào)度問題的本質(zhì)是非確定多項式（Non?Deterministic Polynomial，NP）問題。而遺傳算法在處理NP問題時體現(xiàn)出優(yōu)異的性能，具有較強的整體搜索能力和優(yōu)化能力[9?10]。因此，研究人員開始將遺傳算法應(yīng)用于該領(lǐng)域中。例如，文獻[11]提出一種基于遺傳算法的制造車間車輛調(diào)度優(yōu)化方法，提高了車輛的運輸效率。研究顯示，云計算資源調(diào)度可以被視為NP問題，因此，本文提出一種基于遺傳算法的云計算資源調(diào)度方法。

2 ?云服務(wù)高校教師師資培訓(xùn)系統(tǒng)模式

CCAI模式下的高校教師師資培訓(xùn)系統(tǒng)需要滿足全天候、全地域和全連接的要求。本文采用C/S模式構(gòu)建網(wǎng)絡(luò)教學(xué)資源的服務(wù)系統(tǒng)架構(gòu)，所有數(shù)據(jù)均存儲在數(shù)據(jù)服務(wù)器中，如圖1所示。培訓(xùn)教師在校園中的教室或者辦公室內(nèi)，通過校園網(wǎng)上傳或者訪問網(wǎng)絡(luò)教學(xué)服務(wù)器。校內(nèi)的學(xué)生可以在宿舍或者圖書館通過校園網(wǎng)訪問學(xué)習(xí)資源。而校外的人員通過因特網(wǎng)也可以遠程訪問培訓(xùn)學(xué)習(xí)資源，實現(xiàn)了有限教學(xué)資源的高效共享，打破了地理空間限制，降低了人力和物力投入成本。

3 ?云環(huán)境下基于遺傳算法的培訓(xùn)資源調(diào)度

3.1 ?基于遺傳算法的資源調(diào)度設(shè)計

如前面所述，面對云計算平臺中存儲的異構(gòu)、動態(tài)和大規(guī)模教學(xué)資源時，傳統(tǒng)的云計算任務(wù)調(diào)度算法的性能較差，平衡性和工作效率較低。因此，本文采用遺傳算法來實現(xiàn)云計算資源的調(diào)度。首先，假設(shè)資源調(diào)度任務(wù)中具有[m]個主機[H]，且這些主機上安裝了[n]個虛擬機[V]，利用編碼映射對每個遺傳個體進行編碼{[k0，k1，k2，…，kn-1]}。如圖2所示，虛擬機與主機映射關(guān)系中，序列長度為5，那么[V]的0～5的編號為{1，0，2，0，2}，序列中的編號為主機[H]的編號，然后初始化生成種群。

設(shè)某個調(diào)度任務(wù)的組成對象總量為[N]，則[N]個組成對象單個的適應(yīng)度為[fi]，那么，第[i]個對象被挑中進化的概率為：

[P=fii=1Nfi， ? ?i=1，2，…，N] ?（1）

設(shè)調(diào)度任務(wù)在某個時間段內(nèi)從最初時間到最后時間的位置變化為[δ（H）]。而遺傳算法的選擇交叉和變化的概率[9]分別為[Pc]和[Pm]，則下一代屬于調(diào)度任務(wù)動態(tài)過程的期望值為：

[E[m（H，t+1）]≥ ? ? ? ? ? m（H，t）?f（H，t）f（t）1-Pcδ（H）L-1-Ο（H）Pm] （2）

式中：[Ο（H）]為任務(wù)動態(tài)階數(shù);[L]為任務(wù)傳輸最遠距離; [m（H，t）]為下一代屬于調(diào)度任務(wù)傳輸需要的對象個數(shù);[f（H，t）]和[f（t）]分別為下一代屬于調(diào)度任務(wù)需要的對象的適應(yīng)度和均值適應(yīng)度[11]。

為了保證調(diào)度任務(wù)過程在進行遺傳算法構(gòu)造時對象的整體性和完整性，防止出現(xiàn)調(diào)度任務(wù)的變化出現(xiàn)局部數(shù)據(jù)丟失的情況，選擇交叉操作的概率必須滿足式（3）：

[Ps≥1-Pcδ（H）L-1] （3）

那么，根據(jù)式（2）和式（3）可得：

[E[m（H，t+1）]≥m（H，t）?f（H，t）f（t）-Pcδ（H）L-1] （4）

[E[m（H，t+1）]≥ ? ? ? ? m（H，t）?f（H，t）f（t）?1-Pcδ（H）L-1（1-Pm）Ο（H）] （5）

在式（5）中，一般[Pm]值很小，則可以進一步優(yōu)化式（5），得到：

[（1-Pm）Ο（H）≈1-Ο（H）?Pm] （6）

則有：

[1-Pcδ（H）L-1（1-Ο（H）?Pm）≥ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1-Pcδ（H）L-1-Ο（H）?Pm] （7）

若[f（H，t）f（t）>C]，[C]為常量，則表示運算還未達到算法計算的最優(yōu)解，設(shè)[K]為：

[K=C?1-Pcδ（H）L-1-Ο（H）?Pm] （8）

若[K]>1，則有：

[E[m（H，t+1）]≥m（H，t）?K] ?（9）

由此可遞推得：

[E[m（H，t+1）]≥m（H，0）?K] （10）

經(jīng)過遺傳算法將調(diào)度任務(wù)的對象進行選取迭代計算后，可以得到調(diào)度任務(wù)在某個時間段內(nèi)所需資源對象的位置變化情況，而在位置變化訓(xùn)練過程中，粒子群算法有獨特的優(yōu)勢，因此采用粒子群算法對其全局尋優(yōu)能力進行了改進。將調(diào)度任務(wù)的對象設(shè)為粒子群的粒子，設(shè)第[i]個粒子為[xi=（xi1，xi2，…，xiN）]，其飛行速度為[vi=（vi1，vi2，…，viN）]，在三維空間內(nèi)分布的最優(yōu)點為[pi=（pi1，pi2，…，piN）]，群里所有粒子的分布最優(yōu)點為[pg=（pg1，pg2，…，pgN）]。那么任務(wù)對象在變化過程中，對象的速度和位置可表示為[6]：

[vk+1id=ωvkid+c1r1（pkid-xkid）+c2r2（pkgd-xkid）] （11）

[xk+1id=xkid+rvk+1id] ? （12）

式中：[r1]和[r2]表示加速系數(shù);[ω]表示上時間段的速度系數(shù);[c1，c2∈rand[0，1]]。

3.2 ?適應(yīng)度函數(shù)設(shè)計

為了在提高工作效率的前提下，盡量達到性能平衡，降低工作能耗，本文將服務(wù)質(zhì)量約束和能耗約束相結(jié)合來構(gòu)建適應(yīng)度函數(shù)。其中，虛擬機的總服務(wù)質(zhì)量違例[Qtotal]的計算方式如下：

[Qtotal=1-MIPStotal_L-MIPStotal_MMIPStotal_L] ?（13）

式中：[MIPStotal_L]和[MIPStotal_M]分別為所有已經(jīng)分配的每秒百萬條指令和沒有按時分配給[V]的每秒百萬條指令。

系統(tǒng)總能耗[E]的計算方式如下：

[E=i=0m-1Hosti] （14）

式中：[Hosti]為云計算調(diào)度中第[i]臺主機的能耗。采用由質(zhì)量和成本構(gòu)成的雙指標(biāo)約束作為適應(yīng)度函數(shù)的原則，因此，適應(yīng)度函數(shù)Fitness的定義如下：

[Fitness=1-a?Qtotal-b?E] ?（15）

式中[a]和[b]分別為服務(wù)質(zhì)量違例和總能耗對應(yīng)的權(quán)值。

4 ?系統(tǒng)的實現(xiàn)和測試

4.1 ?CloudSim平臺

為了驗證提出算法的性能，在云計算仿真軟件CloudSim中采用Hadoop?0.20.2對RR 算法、RA算法和本文提出算法進行對比實驗。算法迭代的次數(shù)為50次，設(shè)置適應(yīng)度函數(shù)權(quán)值[a=b][=0.5]，種群數(shù)量=100，虛擬機[V=]20，主機[H=]25。

4.2 ?評估指標(biāo)

實驗采用時間跨度和加速比兩個指標(biāo)評價算法性能[12?13]：

1） 時間跨度：在多工作流調(diào)度中，時間跨度定義為第一個工作流開始的時間點和最后一個工作流完成執(zhí)行的時間點之間所經(jīng)歷的時間。

2） 加速比：加速比是串行執(zhí)行時間與并行執(zhí)行時間的比值，其計算公式如下：

[Speedup=T1Tp] （16）

式中：[T1]為串行執(zhí)行時間;[Tp]為有[p]個處理器時的并行執(zhí)行時間。

4.3 ?結(jié)果對比

三種云計算資源調(diào)度算法的時間跨度和加速比對比結(jié)果分別如圖3和圖4所示。

由圖3，圖4可以看出，隨著任務(wù)調(diào)度工作數(shù)量的增加，三種調(diào)度算法的時間跨度和加速比均不斷增加。但是，當(dāng)處理相同數(shù)量的任務(wù)調(diào)度工作流時，RA算法的時間跨度最大且加速比最低，這是因為RA算法將用戶的請求隨機分配給可用的服務(wù)器。

相比于RA算法、RR算法，本文算法的性能均有所提高，這是因為其將用戶的請求輪流分配給系統(tǒng)。綜合結(jié)果可以看出，本文通過全局尋優(yōu)能力突出的粒子群優(yōu)化遺傳算法，得到了最佳的任務(wù)分配結(jié)果，從而獲得了明顯的優(yōu)勢，即具有最小的時間跨度和最大的加速比。

5 ?結(jié) ?論

本文提出了一種基于粒子群優(yōu)化遺傳算法的云計算資源調(diào)度方法，以便用于高校師資培訓(xùn)資源管理。CloudSim平臺的Hadoop實驗仿真結(jié)果顯示，相比于傳統(tǒng)的RA算法和RR算法，提出的云計算資源調(diào)度方法在雙約束條件下，獲得了較好的時間跨度和加速比性能，具有明顯的優(yōu)勢。但是，系統(tǒng)的穩(wěn)定性有待分析，此外，需要針對MapReduce架構(gòu)進行并行化運行設(shè)計，將在后續(xù)研究中對上述問題繼續(xù)開展分析。

參考文獻

[1] XUE K， HONG J， MA Y， et al. Fog?aided verifiable privacy preserving access control for latency?sensitive data sharing in vehicular cloud computing [J]. IEEE network， 2018， 32（3）： 7?13.

[2] CHEN H， SHEN J. Denoising of point cloud data for computer?aided design， engineering， and manufacturing [J]. Engineering with computers， 2018， 34（3）： 523?541.

[3] JUNG Y H， PETRACCA M， CARLONI L P. Cloud?aided design for distributed embedded systems [J]. IEEE design & test， 2014， 31（3）： 32?40.

[4] 李會.基于云計算的高校教育資源共享服務(wù)平臺構(gòu)建研究[J].赤峰學(xué)院學(xué)報，2015（15）：29?31.

[5] 高慶磊，丁利群，滿樂，等.試論基于云計算的高校數(shù)據(jù)中心的設(shè)計與實現(xiàn)[J].工程建設(shè)與設(shè)計，2015（8）：126?128.

[6] ELLINGSON S R， BAUDRY J. High?throughput virtual molecular docking with AutoDockCloud [J]. Concurrency & computation： practice & experience， 2014， 26（4）： 907?916.

[7] 劉桂開，高蕾.基于彈性定額值的分組輪詢調(diào)度算法[J].計算機科學(xué)，2013，40（8）：72?78.

[8] 林貞，李正權(quán).一種多源協(xié)作網(wǎng)絡(luò)中輪詢節(jié)點選擇算法[J].中國計量大學(xué)學(xué)報，2013，24（3）：284?289.

[9] TAVAKKOLI?MOGHADDAM R， SAFARI J， SASSANI F. Reliability optimization of series?parallel systems with a choice of redundancy strategies using a genetic algorithm [J]. Reliability engineering & system safety， 2008， 93（4）： 550?556.

[10] VOLKANOVSKI A， MAVKO B， BOSEVSKI T， et al. Genetic algorithm optimization of the maintenance scheduling of gene?rating units in a power system [J]. Reliability engineering & system safety， 2008， 93（6）： 779?789.

[11] 孟令通，朱洪淵，蔣祖華，等.基于遺傳算法的平板車調(diào)度優(yōu)化方法[J].哈爾濱工程大學(xué)學(xué)報，2018，39（3）：554?560.

[12] AZIZA H， KRICHEN S. Bi?objective decision support system for task?scheduling based on genetic algorithm in cloud computing [J]. Computing， 2018， 100（2）： 65?91.

[13] CHEN W H， XIE G Q， LI R F， et al. Efficient task scheduling for budget constrained parallel applications on heterogeneous cloud computing systems [J]. Future generation computer systems， 2017， 74： 1?11.

作者簡介：邢莉莉（1985—），女，河北滄州人，碩士研究生，講師，研究方向為學(xué)前教育理論、計算機教學(xué)。