基于云计算的流媒体任务调度算法*

杨 戈 ，吴俊言

（1.北京师范大学珠海分校 智能多媒体技术重点实验室，广东 珠海 519087；2.北京大学深圳研究生院 深圳物联网智能感知技术工程实验室，广东 深圳 518055）

0 引言

随着计算机时代的发展，用户的基数正在不断扩大，而对应的在线视频的量级也正逐步扩展，为解决点对点的在线视频的服务器的速度和带宽问题，以及大量的视频资源带来服务器计算负载问题，增加其负载而带来了“云计算”[1]。

云计算分为3 层，分别是IaaS（基础设施即服务）、Paas（平台即服务）和SaaS（软件即服务）[2]。储存资源管理是计算机资源管理的一部分，侧重于计算机的节点的高效性和节点的整体负载均衡。无论是一般的云计算，还是快速发展的移动云计算，云增效模式是最常见的云计算模式[3]。因而在云计算方面，最主要研究的是计算机资源、负载均衡的实现和任务调度的分配等方面。在任务调度方面，文献[4]提出了一种面向多目标的两阶段任务调度算法，具有让任务匹配最小时间资源的偏好，重调度阶段，实现负载均衡；文献[5]提出了针对P2P（对等网络，即对等计算机网络）结构上的用数据副本来进行管理，从而提高数据访问的效率和系统容错功能。文献[6]中提出了一种基于任务调度的模板策略，通过任务集合求出任务量模版，并依据模板对调度算法进行任务调度的TTS（基于模板的任务调度策略）策略。该算法从全局的角度计算出调度模板，有目标地实现了调度同时充分考虑了通信开销。

而对于计算机资源管理方面，文献[7]研究了虚拟云桌面上的动态调度应用，文献[8]中提出了一种关于网络感知的计算资源下的对虚拟机的放置算法。

本文在针对于云计算任务调度的基础上提了一种贪心蚁群算法（Greedy And Ant Colony Algorithm，GAAC），它避免了贪心算法在任务数较大情况下的搜索能力不足及局部搜索能力低下，以及蚁群算法在初始阶段的搜索能力低下的缺点，同时充分考虑了在全局情况下的云计算的流媒体任务调度。

1 云计算资源调度模型

云计算中的资源调度可通过以下的模型表示：

式中，fi（yi）表示效率函数。为了能够达到云计算的资源调度的优化要求，要求云计算资源调度所消耗资源的为最小值即mini

∑fi（yi），其花费、时间和能量三方面达到最小值。C（i，j）表示任务i在资源j的花费，E（i，j）表示任务i在资源j的能量消耗，T（i，j）表示任务i在资源j的时间消耗。

式中，yi表示完成任务i的所需要的资源总和其中表示的是任务i 和虚拟机j 之间的关系。本文主要从时间消耗最小上解决云计算的效率优化问题。

2 GAAC 算法

GAAC 算法是在现今的任务调度贪心算法的后期融入了蚁群算法的特点。GAAC 算法同时具有贪心算法任务量较少时，负载均衡，能实现较好的局部优化和蚁群算法任务量较多时具有的学习机制和迭代优化的特点，即GAAC 算法同时具备了贪心算法和蚁群算法的原理特点。

2.1 GAAC 算法实现

对于其中的贪心算法，学者们对任务调度及贪心算法进行了大量的研究[9-12]。而在文献[6]中，贪心法则为：按物品的价值大小排序，选择剩下的容量最大的背包，装最大件的物品，直到所有的背包都装满物品为止。将该方法类比到云计算的任务调度问题下，提出贪心算法下的任务调度优化方法。

而对应于云计算调度，则是进行任务和虚拟机排序，按照虚拟机执行任务的能力和速度按大到小进行排序，然后再按照任务的大小同时进行排序，检索最大的任务在哪个虚拟机运行得最快，然后完成分配，再进行下一个任务的分配，依次类推直到任务分发完毕。

而GAAC 算法在任务量较大的后期则是具备仿生原理，它依据蚂蚁群寻找食物的原则而模拟而成的一种最短路径的智能算法[13]，而其具体步骤如下：

（1）初始化，首先设定相关参数；

（2）将m 个蚂蚁随机放在各个食物上，每个食物至多分布一个蚂蚁，并将m 修改禁忌表Jk；

（3）所有蚂蚁根据概率转换公式和选择下一食物，并将该元素（食物）移动到该蚂蚁个体的禁忌表中；

（4）所有蚂蚁遍历完n 个食物后在所经过的路径上根据信息更新公式更新所有信息素，并记录本次迭代过程重点最优路径和最优路径长度；

（5）清空禁忌列表Jk，重复步骤（3）和（4），直到每一个蚂蚁都完成Nmax次遍历所有食物，最后输出的路径为最优路径。

而对应在任务调度中则是将食物替换成云计算中的各个节点的虚拟机，而其蚂蚁获得的路径则是对应任务分配给虚拟机的分法，而蚂蚁获得的路径的长度，则为分配好后所花费的总时间。算法通过其中的学习机制，不断迭代从而找到任务调度中的最短路径，进而实现路径的最优化。

2.2 GAAC 算法流程

由于蚁群算法的受信息素引导，需要较多次数的学习和迭代，才能形成较好的优化，对应在任务调度算法上则需要较多的任务量。而在起初阶段，由于任务数（对应蚁群中的食物点）较少，正反馈的尚不健全，无法形成良好的学习机制，从而无法得到较优解。相反，贪心算法由于不具备学习机制，在前期所耗时较少，但在后期任务数较大时，由于学习机制的缺失，优化效果较差，而GAAC 算法正是将这两种算法融合形成的新算法。

设贪心算法所完成的时间为tasktime（t）a，蚁群算法所完成的时间为tasktime（t）b。通过比较可以得出两种算法在云任务的实现时间，则判断tasktime（t）a=tasktime（t）b=γ所对应的任务数值，求得大约为：

（1）当tasktime（t）a

①将任务按由大到小的顺序降序排列（MI），并将虚拟机按按小到大升序排列（MIPS），所消耗的时间为T，它们之间满足公式：T=MI/MIPS。

②将最后一列对应的虚拟机分配给矩阵中行号为0的任务。

（2）tasktime（t）a>tasktime（t）b，此时即采用蚁群算法，其路径概率的选择和信息素更新选择如下：

图1 GAAC 算法流程图

3 仿真实验

本文运用了云计算的模拟平台Cloudsim，通过Cloudsim实现云环境的模拟配置，达到异构的云环境。

3.1 软硬件

实验使用的物理机和硬软件配置如表1 所示。

表1 硬件及软件配置

3.2 仿真结果

通过修改Datacenterbroker 类加入了自定义的多任务状态的贪心算法和GAAC 算法，并在里面写入了传统的轮转算法进行对比，进行仿真对比分析，仿真实验参数如表2 所示。

表2 仿真实验参数

图2 显示了异构平台下，虚拟机数为5 个时，任务个数由0 个增加到2 500 个时，GAAC 算法与贪心算法、轮转算法和蚁群算法的任务集合完成时间的对比。由于轮转算法的优化效果较差，因此其耗时明显较多于贪心算法和GAAC 算法。从图中可看出在任务个数大于500时4 种算法的差异，贪心算法的用时和GAAC 算法重合，原因是在γ 小于1 000 时，GAAC 算法采用的是贪心算法的原理，但是GAAC 算法的用时明显少于蚁群算法和轮转算法。但随着任务个数的增加，贪心算法和GAAC算法的用时明显开始减少，而至任务数约为1 000 时，GAAC 算法的用时开始明显比贪心算法少。其原因是γ大于1 000 时，GAAC 算法采用的是蚁群算法的原理，在迭代学习次数较大，训练集较大，训练时间较长的情况下进行，由于迭代学习的原因，此时的任务调度实现了更好的优化，因此相对应的用时更少。而蚁群算法和GAAC 算法在约为1 000 个任务之后时间几乎一致，但由于任务具有随机性设置的原因，示例图中的时间上仍有些许的不吻合。但GAAC 算法总体的任务调度时间少于贪心算法和轮转算法，且在前期也优于蚁群算法。即GAAC 从总体的任务优化效果而言，相对优于轮转算法、贪心算法和蚁群算法。

图2 任务调度算法对比1

针对表3 仿真实验参数，图3 显示了异构平台下，虚拟机数为50 个，任务个数由0 个增加到2 500 个时，GAAC 算法与贪心算法、轮转算法和蚁群算法的任务集合完成时间的对比。此时可以看出，γ 所对应的值约为800，在γ 小于800 时，GAAC 算法采用的是贪心算法的原理，相对于蚁群算法，其优化效果大约为40%，而相对于轮转算法其优化效果大约为22%，这是由于GAAC算法前期采用的是现今的贪心算法，其在任务数较少时，能有较好的局部优化效果，而蚁群由于迭代和学习机制尚未健全，因此其时间优化相对较差于轮转算法和贪心算法；而在γ 大于800 时，由于具有蚁群算法的学习和迭代机制的原因，GAAC 算法和蚁群算法接近吻合，但由于每次任务的随机性，并没有重合在一起。GAAC算法由于在现今的贪心算法中融入了采用了蚁群算法的原理，在γ 大于800 时，相对于现今的贪心算法优化效果大概为33%。可以看出GAAC 算法在总体上相对于贪心算法和轮转算法的优化效果更好。

图3 任务调度算法对比2

表3 仿真实验参数

针对表4 仿真实验参数，图4 所示为虚拟机个数为100 个时任务调度算法的对比，此时的γ 值约为900，在γ 小于900 时，GAAC 算法相对于轮转算法其优化效果大约为20%，对于蚁群算法其优化效果大约为34%；而在γ 大于900 时，GAAC 算法相对于贪心算法，其优化效果大约为25%。

图4 任务调度算法对比3

表4 仿真实验参数

随着任务数的增大优化的时间在不断扩大，这是因为随着算法学习与迭代次数的增大，其优化结果越来越倾向于局部最优。即是用GAAC 算法进行云计算任务调度时，考虑了以任务执行时间为优化目标，同时也考虑以负载均衡为优化目标，从而通过局部最优实现全局最优而实现了任务调度的时间和负载的均衡，达到了云计算中的任务调度优化的效果。

4 结论

优化的任务调度算法能高效地提升云计算的性能，从而大大提升云计算的算力、用户响应时间等[14]。本文是基于模拟的Cloudsim 云计算环境通过对现有的两种较常用的云计算算法进行不同的任务时间数的比较，并将由于不同任务数这两种算法所具有的不同优点结合而形成了新的GAAC 算法，可以看出GAAC 算法实现了基本的时间优化和初步的负载平衡，并解决了蚁群算法任务数较低、学习次数较低而导致的优化效果较差和Greedy 算法后期由于没有迭代机制而优化效率较差的问题。但是GAAC 后期，由于学习机制和大量的训练的原因会导致计算开销大，并容易陷入局部优化、过早收敛而非全局最优化的结果。而现今对于云计算的任务调度算法有诸如ACO、遗传、退火算法和两种或多种算法之间的融合实现优化，其能更好地优化其云计算中局部最优和过早收敛的问题。而在云计算中，诸如云平台中数据迁移的开销、引入安全性约束条件、服务间资源、资源共享等问题的提出和解决，都将再进一步地优化现今的云计算算法，从而实现更好的算力，降低用户响应时间等问题，这些都需对云计算的任务调度算法进一步完善和改进。