摘  要： 如何在提高云计算服务资源调度效率的同时尽量降低工作能耗，成为当前必须解决的问题。因此，提出一种基于遗传算法的云计算资源调度方法，适用于高校师资培训资源管理。首先，搭建基于云服务的高校教师师资培训系统模式;其次，利用具有较强NP问题解决能力的遗传算法设计大规模集群的资源调度方法，并采用粒子群算法对其全局寻优能力进行改进;最后，设计了由质量和成本构成的双指标约束适应度函数。CloudSim平台的Hadoop实验仿真结果显示，提出的遗传云计算资源调度方法在约束条件下获得了最佳的调度结果。

关键词： 云计算; 遗传算法; Hadoop; 资源调度; 平衡性; 调度策略

中图分类号： TN02?34; TP393                     文献标识码： 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年以来，云计算已经逐渐成为各个行业领域争相构建的战略方向。许多基于云计算的产品和服务不断被推出，计算机行业的规模和涉及的领域也随之不断拓张。云计算辅助教学（Cloud Computing Aided Instruction，CCAI）已经成为了广大高校和教师搭建现代化、信息化和个性化教学的新手段，从技术上有效提高了教学的质量[1?2]。CCAI模式的特点十分有利于高校师资培训的信息化管理，降低了资金投入和维护成本，提高了网络安全性，有助于构建个性化教学环境。实际推广应用结构显示通过CCAI模式可以有效解决当前高校师资培训面临的空间限制和资源匮乏问题[3]。

近期基于CCAI模式的教学资源管理得到了较多的关注。例如，文献[4]提出了基于云计算的高校教育资源共享服务平台构建研究，实现了按需为教师及学生提供个性化数字资源。文献[5]讨论了基于云计算的高校数据中心的设计与实现方案。但是，如何在提高云计算服务资源调度效率的同时尽量降低工作能耗，成为当前必须解决的问题[5]。因此，本文提出一种基于遗传算法的云计算资源调度方法，以便用于高校师资培训资源管理。Hadoop实验仿真结果显示，提出的遗传云计算资源调度方法在多个约束条件下，获得了较好的时间跨度和加速比性能。

1  问题描述

目前CCAI模式下如何对云计算平台中存储的异构大量资源进行合理的调度是当前急需解决的主要问题。即尽可能地提高工作效率、保证任务调度质量，并同时尽量降低工作能耗，成为云计算任务调度领域研究的热点问题。传统的云计算任务调度算法包括[6]轮询算法（Round?Robin，RR）和随机分配算法（Random?Allocation，RA）。文献[7]提出一种基于弹性定额值的分组轮询调度算法，保证了数据流的公平性。文献[8]提出一种多源协作网络中轮询节点选择算法，通过利用率来提供更好的系统性能。但是上述算法在处理异构性、动态性和大规模性的虚拟数字资源时表现不够理想。

工作流程和任务调度问题的本质是非确定多项式（Non?Deterministic Polynomial，NP）问题。而遗传算法在处理NP问题时体现出优异的性能，具有较强的整体搜索能力和优化能力[9?10]。因此，研究人员开始将遗传算法应用于该领域中。例如，文献[11]提出一种基于遗传算法的制造车间车辆调度优化方法，提高了车辆的运输效率。研究显示，云计算资源调度可以被视为NP问题，因此，本文提出一种基于遗传算法的云计算资源调度方法。

2  云服务高校教师师资培训系统模式

CCAI模式下的高校教师师资培训系统需要满足全天候、全地域和全连接的要求。本文采用C/S模式构建网络教学资源的服务系统架构，所有数据均存储在数据服务器中，如图1所示。培训教师在校园中的教室或者办公室内，通过校园网上传或者访问网络教学服务器。校内的学生可以在宿舍或者图书馆通过校园网访问学习资源。而校外的人员通过因特网也可以远程访问培训学习资源，实现了有限教学资源的高效共享，打破了地理空间限制，降低了人力和物力投入成本。

3  云环境下基于遗传算法的培训资源调度

3.1  基于遗传算法的资源调度设计

如前面所述，面对云计算平台中存储的异构、动态和大规模教学资源时，传统的云计算任务调度算法的性能较差，平衡性和工作效率较低。因此，本文采用遗传算法来实现云计算资源的调度。首先，假设资源调度任务中具有[m]个主机[H]，且这些主机上安装了[n]个虚拟机[V]，利用编码映射对每个遗传个体进行编码{[k0，k1，k2，…，kn-1]}。如图2所示，虚拟机与主机映射关系中，序列长度为5，那么[V]的0～5的编号为{1，0，2，0，2}，序列中的编号为主机[H]的编号，然后初始化生成种群。

设某个调度任务的组成对象总量为[N]，则[N]个组成对象单个的适应度为[fi]，那么，第[i]个对象被挑中进化的概率为：

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

设调度任务在某个时间段内从最初时间到最后时间的位置变化为[δ（H）]。而遗传算法的选择交叉和变化的概率[9]分别为[Pc]和[Pm]，则下一代属于调度任务动态过程的期望值为：

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

式中：[Ο（H）]为任务动态阶数;[L]为任务传输最远距离; [m（H，t）]为下一代属于调度任务传输需要的对象个数;[f（H，t）]和[f（t）]分别为下一代属于调度任务需要的对象的适应度和均值适应度[11]。

为了保证调度任务过程在进行遗传算法构造时对象的整体性和完整性，防止出现调度任务的变化出现局部数据丢失的情況，选择交叉操作的概率必须满足式（3）：

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

那么，根据式（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]值很小，则可以进一步优化式（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]为常量，则表示运算还未达到算法计算的最优解，设[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）

经过遗传算法将调度任务的对象进行选取迭代计算后，可以得到调度任务在某个时间段内所需资源对象的位置变化情况，而在位置变化训练过程中，粒子群算法有独特的优势，因此采用粒子群算法对其全局寻优能力进行了改进。将调度任务的对象设为粒子群的粒子，设第[i]个粒子为[xi=（xi1，xi2，…，xiN）]，其飞行速度为[vi=（vi1，vi2，…，viN）]，在三维空间内分布的最优点为[pi=（pi1，pi2，…，piN）]，群里所有粒子的分布最优点为[pg=（pg1，pg2，…，pgN）]。那么任务对象在变化过程中，对象的速度和位置可表示为[6]：

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

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

式中：[r1]和[r2]表示加速系数;[ω]表示上时间段的速度系数;[c1，c2∈rand[0，1]]。

3.2  适应度函数设计

为了在提高工作效率的前提下，尽量达到性能平衡，降低工作能耗，本文将服务质量约束和能耗约束相结合来构建适应度函数。其中，虚拟机的总服务质量违例[Qtotal]的计算方式如下：

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

式中：[MIPStotal_L]和[MIPStotal_M]分别为所有已经分配的每秒百万条指令和没有按时分配给[V]的每秒百万条指令。

系统总能耗[E]的计算方式如下：

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

式中：[Hosti]为云计算调度中第[i]台主机的能耗。采用由质量和成本构成的双指标约束作为适应度函数的原则，因此，适应度函数Fitness的定义如下：

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

式中[a]和[b]分别为服务质量违例和总能耗对应的权值。

4  系统的实现和测试

4.1  CloudSim平台

为了验证提出算法的性能，在云计算仿真软件CloudSim中采用Hadoop?0.20.2对RR 算法、RA算法和本文提出算法进行对比实验。算法迭代的次数为50次，设置适应度函数权值[a=b][=0.5]，种群数量=100，虚拟机[V=]20，主机[H=]25。

4.2  评估指标

实验采用时间跨度和加速比两个指标评价算法性能[12?13]：

1） 时间跨度：在多工作流调度中，时间跨度定义为第一个工作流开始的时间点和最后一个工作流完成执行的时间点之间所经历的时间。

2） 加速比：加速比是串行执行时间与并行执行时间的比值，其计算公式如下：

[Speedup=T1Tp] （16）

式中：[T1]为串行执行时间;[Tp]为有[p]个处理器时的并行执行时间。

4.3  结果对比

三种云计算资源调度算法的时间跨度和加速比对比结果分别如图3和图4所示。

由图3，图4可以看出，随着任务调度工作数量的增加，三种调度算法的时间跨度和加速比均不断增加。但是，当处理相同数量的任务调度工作流时，RA算法的时间跨度最大且加速比最低，这是因为RA算法将用户的请求随机分配给可用的服务器。

相比于RA算法、RR算法，本文算法的性能均有所提高，这是因为其将用户的请求轮流分配给系统。综合结果可以看出，本文通过全局寻优能力突出的粒子群优化遗传算法，得到了最佳的任务分配结果，从而获得了明显的优势，即具有最小的时间跨度和最大的加速比。

5  结  论

本文提出了一种基于粒子群优化遗传算法的云计算资源调度方法，以便用于高校师资培训资源管理。CloudSim平台的Hadoop实验仿真结果显示，相比于传统的RA算法和RR算法，提出的云计算资源调度方法在双约束条件下，获得了较好的时间跨度和加速比性能，具有明显的优势。但是，系统的稳定性有待分析，此外，需要针对MapReduce架构进行并行化运行设计，将在后续研究中对上述问题继续开展分析。

参考文献

[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] 李会.基于云计算的高校教育资源共享服务平台构建研究[J].赤峰学院学报，2015（15）：29?31.

[5] 高庆磊，丁利群，满乐，等.试论基于云计算的高校数据中心的设计与实现[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] 刘桂开，高蕾.基于弹性定额值的分组轮询调度算法[J].计算机科学，2013，40（8）：72?78.

[8] 林贞，李正权.一种多源协作网络中轮询节点选择算法[J].中国计量大学学报，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] 孟令通，朱洪渊，蒋祖华，等.基于遗传算法的平板车调度优化方法[J].哈尔滨工程大学学报，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—），女，河北沧州人，硕士研究生，讲师，研究方向为学前教育理论、计算机教学。