云計(jì)算Hadoop平臺(tái)中基于遺傳算法的高校師資培訓(xùn)管理

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

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

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

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

1 ?問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

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

為了保證調(diào)度任務(wù)過(guò)程在進(jìn)行遺傳算法構(gòu)造時(shí)對(duì)象的整體性和完整性，防止出現(xiàn)調(diào)度任務(wù)的變化出現(xiàn)局部數(shù)據(jù)丟失的情況，選擇交叉操作的概率必須滿(mǎn)足式（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]值很小，則可以進(jìn)一步優(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ùn)算還未達(dá)到算法計(jì)算的最優(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)過(guò)遺傳算法將調(diào)度任務(wù)的對(duì)象進(jìn)行選取迭代計(jì)算后，可以得到調(diào)度任務(wù)在某個(gè)時(shí)間段內(nèi)所需資源對(duì)象的位置變化情況，而在位置變化訓(xùn)練過(guò)程中，粒子群算法有獨(dú)特的優(yōu)勢(shì)，因此采用粒子群算法對(duì)其全局尋優(yōu)能力進(jìn)行了改進(jìn)。將調(diào)度任務(wù)的對(duì)象設(shè)為粒子群的粒子，設(shè)第[i]個(gè)粒子為[xi=（xi1，xi2，…，xiN）]，其飛行速度為[vi=（vi1，vi2，…，viN）]，在三維空間內(nèi)分布的最優(yōu)點(diǎn)為[pi=（pi1，pi2，…，piN）]，群里所有粒子的分布最優(yōu)點(diǎn)為[pg=（pg1，pg2，…，pgN）]。那么任務(wù)對(duì)象在變化過(guò)程中，對(duì)象的速度和位置可表示為[6]：

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 ?CloudSim平臺(tái)

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

4.2 ?評(píng)估指標(biāo)

實(shí)驗(yàn)采用時(shí)間跨度和加速比兩個(gè)指標(biāo)評(píng)價(jià)算法性能[12?13]：

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

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

[Speedup=T1Tp] （16）

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

4.3 ?結(jié)果對(duì)比

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

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

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

5 ?結(jié) ?論

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

參考文獻(xiàn)

[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] 李會(huì).基于云計(jì)算的高校教育資源共享服務(wù)平臺(tái)構(gòu)建研究[J].赤峰學(xué)院學(xué)報(bào)，2015（15）：29?31.

[5] 高慶磊，丁利群，滿(mǎn)樂(lè)，等.試論基于云計(jì)算的高校數(shù)據(jù)中心的設(shè)計(jì)與實(shí)現(xiàn)[J].工程建設(shè)與設(shè)計(jì)，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] 劉桂開(kāi)，高蕾.基于彈性定額值的分組輪詢(xún)調(diào)度算法[J].計(jì)算機(jī)科學(xué)，2013，40（8）：72?78.

[8] 林貞，李正權(quán).一種多源協(xié)作網(wǎng)絡(luò)中輪詢(xún)節(jié)點(diǎn)選擇算法[J].中國(guó)計(jì)量大學(xué)學(xué)報(bào)，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] 孟令通，朱洪淵，蔣祖華，等.基于遺傳算法的平板車(chē)調(diào)度優(yōu)化方法[J].哈爾濱工程大學(xué)學(xué)報(bào)，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.

作者簡(jiǎn)介：邢莉莉（1985—），女，河北滄州人，碩士研究生，講師，研究方向?yàn)閷W(xué)前教育理論、計(jì)算機(jī)教學(xué)。