云数据中心任务调度算法建模与仿真

摘要：随着云计算技术的快速发展，云数据中心资源调度问题作为提高云资源利用率和优化任务执行时间的关键环节，受到广泛关注。文章对云计算任务调度问题进行建模，研究遗传算法和蚁群算法两种启发式优化算法，并在CloudSim环境下对两种算法进行实现和仿真。仿真过程中，以不同的任务数量和迭代次数为变量，对比两种算法在时间效率上的表现。实验结果表明，遗传算法和蚁群算法在特定条件下均能有效提升云计算任务调度的效率，且在文章仿真环境中，遗传算法的表现优于蚁群算法。

关键词：任务调度；GA；ACO；Cloudsim

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2025）04-0088-04 开放科学（资源服务） 标识码（OSID） ：

0 引言

云计算[1]作为一种提供按需计算资源的新型服务模式，已经成为信息技术领域的重要分支。在云计算环境中，任务调度是确保资源高效利用和快速响应用户需求的核心问题。任务调度模型的设计直接关系到云服务的性能和成本效益。因此，研究和开发高效的任务调度算法对于云数据中心的可持续发展至关重要。

传统的任务调度算法，如先来先服务、时间片轮转法等，在云数据中心的资源利用效率上存在明显不足。近年来，智能调度算法被广泛应用于云数据中心任务调度过程中[2-5]，以提升数据中心资源利用率、缩短任务执行时间，并实现更有效的负载均衡。然而，调度问题是一个NP完全（NP-complete） 问题，对于这类问题，不存在任何一种算法能够在多项式时间内找到问题的最优解。遗传算法（Genetic Algorithm，GA） [4]和蚁群算法（Ant Colony Optimization，ACO） [5]是两种基于自然界现象的启发式算法，它们在解决优化问题方面显示出了巨大的潜力。遗传算法模拟了自然选择和遗传机制，而蚁群算法则模仿了蚂蚁寻找食物的路径选择行为。这两种算法在解决复杂问题时具有较好的全局搜索能力和鲁棒性。本文利用CloudSim平台，对遗传算法和蚁群算法进行了详细的算法建模，并从时间效率和迭代次数两个角度设计了仿真实验来评估这两种算法在云计算任务调度中的性能。

1 云数据中心任务调度问题

在云计算的任务调度过程中，用户的任务请求N 往往被划分成n 个大小不等且相互独立的子任务[6]，云计算资源的分配是将这n 个相互独立的子任务分配给m个虚拟机（m＜n），图1为云计算任务分配的模拟图。

虚拟机VM的集合可以表示为V = { v1，v2，...vm }，任务Task的集合T = {n1，n2...nn }，中，vi（v=1，2，...m）表示第i个虚拟机资源，nj（j=1，2，...n）表示第j 个独立的子任务。在调度过程中，虚拟机资源和子任务集合的映射关系可用布尔矩阵N 来表示，如式（1） 所示。

其中，当元素Nij的值为1时，表示任务i 运行在虚拟机j 上，根据不同的任务调度算法和不同的目标函数，最后得到矩阵N 是不同的。

2 任务调度算法模型

2.1 遗传算法

遗传算法是由John Holland在20世纪70年代提出的一种模拟自然选择和遗传机制的优化算法，常用于解决复杂的优化问题，它通过模拟自然界的进化过程来搜索问题的最优解[7]。算法的流程如下。

2.1.1 选择编码策略

本文采用任务的直接实数编码方式[8]，假设有m个虚拟机VM的集合为V = { v1，v2，...vm }，任务数量为n，任务Task的集合为T = { t1，t2...tn }，则遗传算法编码中染色体的基因串长度为任务的总数n，染色体的基因值为虚拟机的编号i（1 ≤ i ≤ m），以下面的染色体序列为例：

{6，5，4，4，1，3，4，...，3，m - 3，m - 2，m }

该染色体序列表示第1个任务分配到第6个虚拟机资源上，第2个任务分配到第5个虚拟机资源上，第3、第4个任务分配到第4个资源上，第n-1个任务分配到第m-2个资源上，第n 个任务分配到第m 个资源上。这种编码方式是遗传算法应用到CloudSim仿真中的最常用编码方式，编码简单，易于理解。

2.1.2 定义适应度函数

从用户的视角来看，任务的完成时间是首要考虑因素，因此将适应度函数定义为用户的等待时间（即任务运行时间） ，以最小完成时间为适应度函数。在本文中，任务的完成时间与任务运行时间和任务的映射时间相关，具体而言，其大小与指令长度以及虚拟机的带宽和运算速度相关，可由公式（2） 表示：

式中：Ti，j 表示任务i 在虚拟机资源j 上的执行时间，tl和tf分别表示任务i 的指令长度和文件大小，vm和vb表示虚拟机j 的带宽和运算速度。假设虚拟机j 上一共分配有n 个任务，则虚拟机j 完成这些任务的时间可以表示为：

由于不同的虚拟机上分配的任务数量不同，因此完成时间最长的虚拟机所需的时间则表示在这种编码方式下完成所有任务所需的最短时间，可以表示为：

Tmin = max（Tj ） （1≤j≤m） （4）

当任务的执行时间越小时，算法的适应度越大，因此当适应度值越大时，此时遗传算法染色体序列越好。适应度函数的定义如公式（5） 所示：

F = 1 ／Tmin （5）

2.1.3 确定遗传策略

本文所使用的遗传算法在基础遗传算法的3种算子上做了适当调整，将选择和交叉两种操作合并。这样能够在缩短迭代时间的同时保持种群的搜索范围。选择过程中采用轮盘赌法，根据染色体的适应度进行选择，生成两个临时染色体S1 和S2。具体而言，首先计算总适应度totalScore，然后随机生成一个小于to⁃talScore的值slice，遍历种群并累加染色体适应度，当累加值超过slice时，选择当前染色体。随后对选中的染色体进行交叉操作，通过随机生成两个交叉点a 和b，交换S1 与S2 在交叉区间内的基因，从而生成具有新组合特征的子代染色体S3 和S4。此区间交叉操作的核心机制如图2所示。

变异是通过对当前种群的遍历，根据变异率P 和变异步长进行随机变异，以扩大种群的搜索范围。变异操作有助于增加种群的多样性，防止算法过早收敛到局部最优解。

2.1.4 初始化

规定种群大小为popSize，随机初始化生成第一代种群P；计算种群P 中每个个体染色体的适应度值；按照遗传策略，运用选择（交叉） 和变异算子作用于群体，形成下一代群体；当满足迭代次数时，程序结束。

2.2 蚁群算法

蚁群算法（Ant Colony Optimization，ACO） 是由Marco Dorigo等人于1991年提出的一种启发式算法[5]。蚁群的个体之间通过信息素进行交流，通过简单个体组成群体完成复杂的工作，从而达到寻找最优解的目的[9]。这种正反馈机制使得蚂蚁能够发现并利用最短的路径到达食物源。以下是本文蚁群算法实现的参数设置和基本流程。

2.2.1 初始化

设置算法参数，包括信息素矩阵、蚂蚁数量、参数α（信息素的重要程度） 、参数β（启发式因子的重要程度） 、信息素蒸发率等，如表1所示。初始化各条路径上的信息素浓度，随机放置一定数量的蚂蚁到问题的解空间中。

2.2.2 状态转移规则

每只蚂蚁从当前位置出发，采用轮盘法，根据信息素浓度和启发式信息计算每个任务在不同虚拟机上运行的概率，如式（6） 所示。根据轮盘赌策略选择适应度函数值较大的个体，作为下一个位置。这个过程将生成一个完整的路径，即任务的调度方案。

式中：pk ij （t）为t时刻第k只蚂蚁选择任务i在虚拟机j 上运行的概率大小；τij （t） 是任务i 在虚拟机j 上运行的信息素浓度大小，其值由信息素浓度矩阵得到；α和β 作为信息素和启发因子的影响程度，可根据实际情况调整，本文视两者影响程度相同，取相等的值；Dij （t）作为概率p的第二个影响因子（即启发式影响因子） ，代表t 时刻任务i 在虚拟机j 上运行所需的时间代价，其计算方式为虚拟机j 上所有任务的执行时间与任务i 映射在虚拟机j 上的时间之和，可由公式（7） 表示：

式中：vm和vb表示编号为j 的虚拟机的带宽和运算速度，tif和tl 表示任务i 的文件大小和指令长度，T 表示在t 时刻虚拟机j 上的所有任务的指令长度之和。假设在t 时刻虚拟j 上任务数量为n，则T 的表示为：

2.2.3 更新禁忌列表（Tabu List）

为了增加搜索的多样性，为每个蚂蚁设置禁忌列表tabu，tabuk（k=1，2，...，m）为第k 只蚂蚁的禁忌列表[10]，将已经选择的路径（虚拟机资源） 加入禁忌列表中，避免蚂蚁在接下来的迭代中选择重复的任务。

2.2.4 计算解的质量

根据问题的目标函数计算蚂蚁所构建路径的质量。通过计算每一代蚂蚁所通过路径的时间，判断蚂蚁是否找到更优的解。任务的完成时间与遗传算法的计算方式一致，均与任务执行时间和任务的映射时间相关，如遗传算法中公式（2） 所示。

2.2.5 更新信息素

根据t 时刻蚂蚁所找到的解的质量，计算每只蚂蚁新发出的信息素浓度并求和。同时，应用信息素的挥发机制，减少所有路径上的信息素浓度，以避免算法过早收敛，更新方式如公式（9） 所示。

τij （t + 1） = （1 - ρ）τij + Δτij （t） （9）

式中：τij （t + 1）为更新后的信息素浓度矩阵，1-ρ是信息素的残留系数，Δτij （t）用来计算所有蚂蚁个体更新的信息素之和，其计算方式为：

Δτk ij （t）表示在t 时刻第k 只蚂蚁的信息素变化量，由下式计算得到：

式中：tourk ij （t） 为t 时刻第k 只蚂蚁在这一次迭代过程中走的路径所用的总时间。

3 性能对比

实验采用CloudSim 5.0模拟云计算环境。Cloud⁃Sim是由墨尔本大学的Buyya教授带领研究团队推出的一款云计算仿真工具[11]。通过重写DatacenterBro⁃ker类中的bindCloudletToVm方法，根据不同算法最后得到的虚拟机与子任务的映射序列，将各个子任务分配给其对应的虚拟机，随后开始仿真。仿真环境中虚拟机和任务的参数设置如表2所示。

实验一在相同虚拟机数量下对GA、ACO和FCFS 算法的任务完成时间进行比较分析。实验中虚拟机数量固定为5个，GA和ACO算法的迭代次数设定为100次，任务的指令数和长度按照表2所给的任务参数范围进行限定。实验随机生成10、25、50、100、200 和400个任务，为防止出现偶然误差，在每个任务量下进行100次实验并取平均值，得到其平均完成时间。实验结果汇总于表3，任务完成时间如图3所示。

由实验一可以看出，传统的FCFS调度策略在大任务量的情况下耗时较大。两种智能算法在迭代100 次的情况下且任务量少于100时，任务的完成时间相差不大；在任务量超过100时，本文中的遗传算法的寻优能力略优于蚁群算法，体现出一种任务量越多，遗传算法的性能越好的趋势。通过对表3实验数据的分析，发现遗传算法的最优解和最差解的区间比蚁群算法小，蚁群算法的波动较大。这是因为遗传算法利用种群和遗传操作（如交叉、变异） 来探索解空间，通常能保持较为稳定的进化过程，从而使最优解和最差解的区间较小。相反，蚁群算法通过模拟蚂蚁的行为和信息素更新来进行搜索，虽然在局部搜索中具有较高的灵活性和适应性，但其信息素的随机性和更新机制可能导致解的波动较大。信息素的分布不均和更新策略可能导致算法在不同迭代中经历较大的变化，从而使最优解和最差解的区间出现较大的波动。

实验二在虚拟机环境下，任务数量固定为1000 个，通过调整迭代次数来评估两种算法的收敛性。每种迭代设置下进行了100次独立实验，并取其平均值，实验结果如图4所示。