﻿ 求解云计算资源调度的免疫算法 Research on Resource Scheduling Model and Algorithms of Cloud Computing

Operations Research and Fuzziology
Vol. 09  No. 04 ( 2019 ), Article ID: 32923 , 6 pages
10.12677/ORF.2019.94036

Research on Resource Scheduling Model and Algorithms of Cloud Computing

Tian Liu, Geng Lin, Yanzhen Li, Jia Liu

Department of Mathematics, Minjiang University, Fuzhou, China

Received: Oct. 21st, 2019; accepted: Nov. 5th, 2019; published: Nov. 12th, 2019

ABSTRACT

With the rapid development of the information society, cloud computing has been infiltrating into all walks of life, becoming the main way to deal with massive information data. Task scheduling is the core of cloud computing research, and the efficiency of its algorithm plays a decisive role in the execution efficiency of platform users’ tasks and the utilization efficiency of system resources. Aiming at the resource scheduling problem of cloud computing, this paper proposes a dynamic task scheduling algorithm based on artificial immune theory for cloud computing. The experimental results show that the immune algorithm is able to effectively improve the efficiency of cloud computing resource scheduling.

Keywords:Cloud Computing, Immune Algorithm, Task Scheduling

1. 引言

2. 免疫算法

1) 分析问题。对任务调度所研究的问题进行研究分析，构造实验的目标函数，模拟免疫系统中抗原产生形式。设计合理的目标函数表达式。

2) 产生初始抗体群。初始种群的生成需要两个步骤：一是随机生成N个个体，二是从记忆库里随机选取m个个体组成初始群体。即初步的解集，而每个个体对应任务调度的解。

3) 抗体识别抗原。按照个体的期望繁殖力p来进行评价对前两步骤中得到的抗体逐一进行评价。

4) 形成父代群体。按照繁殖率p对初始群体进行降序排列，父代群体取其中前N个个体组成。同时将前m个个体放入记忆库里。

5) 要对抗体适应度计算判断是否满足所设定的约束，满足则结束，否则执行下一步。

6) 抗体的繁殖——新群体的产生。对第四步取得的计算结果进行分析，然后对形成的抗体群体执行选择、交叉、变异等遗传变异步骤。以此得到一个新群体。再从记忆库若干解，与新群体一起构成总群体 [3]。

7) 执行第3步。

Figure 1. Immune algorithm flowchart

2.1. 基于免疫算法的任务调度模型

${A}_{v}=\frac{1}{{F}_{v}}=\frac{1}{\underset{i\in N}{\sum }\underset{j\in {M}_{i}}{\sum }{w}_{i}{d}_{ij}{Z}_{ij}-C\underset{i\in N}{\sum }\mathrm{min}\left(\underset{j\in {M}_{i}}{\sum }{Z}_{ij}-1.0\right)}$ (2-1)

${S}_{v,s}=\frac{{k}_{v,s}}{L}$ (2-2)

${C}_{v}=\frac{1}{N}\underset{i\in N}{\sum }{S}_{v,s}$ (2-3)

$p=\alpha \frac{{A}_{v}}{\sum {A}_{v}}+\left(1-\alpha \right)\frac{{C}_{v}}{\sum {C}_{v}}$ (2-4)

2.2. 任务调度模型求解

3. 实验仿真结果与分析

3.1. 实验假设

1) 本实验目标为计算任务时间的需求即任务最小完成时间，因此仅将完成任务的时间长短作为唯一考量。

2) 本实验仅考虑任务的大小和任务调度的难度，不考虑能耗以及其他因素带来的影响。

3.2. 初始条件

1) 随机生成了31个任务(Case)数据，每个数据为二维向量，意在表示任务的两个参数：任务的大小和任务调度的难度。

2) 考虑实验需要，随机生成6台虚拟机(Machine)，将CPU容量和内存大小作为虚拟机的两个参数，默认硬盘大小一致且满足实验需要。

3) 根据任务调度的模型，按照上述免疫算法的基本流程进行求解，设置如下参数：将种群规模(sizepop)设为60，记忆库容量(overbest)设为15，迭代次数(max)设为100，变异概率(pumtation)设为0.4，交叉概率(pcross)设为0.5，虚拟机数(length)设为6，多样性评价参数(assessment)设为0.95。

3.3. 终止条件

1) 迭代次数达到最大化(本实验迭代次数最高为120)。

2) 连续20代完成任务的总时间基本不变，认为算法基本收敛，求得任务调度方案以及总时间。

3.4. 实验结果分析

Figure 3. Diagram of experimental results

4. 结论

Research on Resource Scheduling Model and Algorithms of Cloud Computing[J]. 运筹与模糊学, 2019, 09(04): 307-312. https://doi.org/10.12677/ORF.2019.94036

1. 1. 程克非, 罗江华, 兰文富, 刘锐. 云计算基础教程[M]. 北京: 人民邮电出版社, 2018.

2. 2. 王磊, 潘进, 焦李成. 免疫算法[J]. 电子学报, 2008, 28(7): 74-78.

3. 3. Burnet, F.M. (1959) The Clonal Selection Theory of Acquired Im-munity. Cambridge University Press, Cambridge．

4. 4. 陈仁. 免疫学基础[M]. 北京: 人民卫生出版社, 1982.

5. 5. Bersini, H. and Varela, F. (1990) Hints for Adaptive Problem Solving Gleaned from Immune Network. The Proceedings of the Workshop on Parallel Problem Solving from Nature, Dortmund, 1990, 343-354.

6. 6. Cooke, D.E. and Hunt, J.E. (year) Recognizing Promoter Sequences Using an Artificial Immune System. Proceedings Intelligent Systems in Molecular Biology, Cambridge, 1995, 89-97.

7. 7. Toma, N., Endo, S., Yamada, K., et al. (2000) The Im-mune Distributed Competitive Problem Solver with Major Histocompatibility Complex and Immune Network. The Conference on Systems, Man and Cybernetics, Nashville, 2000: 1865-1870.

8. 8. Coello, C.A. and Cortes, N.C. (2002) An Approach to Solve Multi-Objective Optimization Problem Based on an Artificial Immune System. Proceedings of the First International Conference on Artificial Immune System, Inglaterra, 2002, 212-221.

9. 9. Xu, J. and Fortes, J. (2010) Multi-Objective Virtual Machine Placement in Virtualized Data Environments. Proceedings of 2010 IEEE/ACM International Conference on Green Computing and Communications, Hangzhou, 18-20 December 2010, 179-188. https://doi.org/10.1109/GreenCom-CPSCom.2010.137

10. 10. 杨镜, 吴磊, 吴德安, 王晓敏, 刘念伯. 云平台下动态任务调度人工免疫算法[J]. 计算机应用, 2014, 34(2): 351-356.