中国指挥与控制学会会刊 
1998年,美国海军水面战中心首次提出“全舰计算环境”(Total Ship Computing Environment,TSCE)的概念。TSCE是支持开放式体系结构的美军新一代水面舰艇系统集成技术[1],由基础设施和各种领域应用组成,将舰艇各类运算操作、基础数据等集成计算,对所有计算资源统一调度管理。随着科学技术的进步,传统的信息化武器装备在设计上难以满足作战能力的需求,需要对舰艇信息装备系统架构进行重新设计,借鉴TSCE技术,探索新一代舰艇一体化信息系统集成技术——公共计算环境(Common Computing Environment,CCE)。公共计算环境是基于虚拟机技术和云计算技术的新一代舰艇信息系统集成技术,能有效将舰艇电子信息设备硬件、机架、服务器和通信媒介等整合到公共网络核心中,实现基础设施的虚拟化管理,并创建一个统一的计算环境。公共计算环境的结构特征主要有以下几点:1)资源集中部署,统一管理;2)全舰采用统一的结构框架;3)具有较强的可裁剪、可扩展能力[2]。
公共计算环境是一种云环境,虚拟机技术和云计算技术的应用提高了计算资源的利用率,其中,任务调度中的完成时间和负载均衡对公共计算环境的整体性能有重要影响。任务分配中,优化完成时间,可以提升公共计算环境中任务的处理效率。优化负载均衡,将任务从利用率高的资源中分配给利用率低的资源,确保没有单个资源被淹没或未被充分利用,以达到较高的吞吐率和较好的资源利用率[3]。
云资源具有动态性、多样性和复杂性,这些资源的管理是一项复杂的工作。多虚拟机系统上的任务调度问题是NP完全问题,因此,许多研究人员提出了启发式和元启发式算法来解决这个问题,其中,启发式算法包含聚类算法、调度算法以及其他算法等[4]。在众多启发式算法和元启发式算法中,本文选择了蚁群优化算法(Ant Colony Optimization,ACO)求解云环境中的任务调度问题。蚁群优化算法是解决NP完全问题的有效方法,如旅行商问题、图着色问题、车辆路径问题、调度问题等[5⇓-7]。蚁群优化算法从蚁群寻找食物的自然行为中获得灵感,并利用蚂蚁生活中的搜索范围、所处环境、觅食、移动、避障以及散播信息素等规律来找出最优解[8]。本文使用改进的蚁群优化算法,在可用资源集上调度独立任务,并结合非支配遗传算法(Non-dominated Sorting Genetic Algorithms-Ⅱ,NSGA-Ⅱ)中的非支配排序思想进行多目标优化,实现负载均衡,减少最大完成时间。
1 问题模型
公共计算环境本质为云环境,任务调度中的完成时间和负载均衡是影响整体性能的重要因素。本文旨在云环境任务调度中,保持负载均衡的同时,减少最大完成时间。独立的任务调度问题中,每个任务由计算成本表示,单位为百万指令(MI),每个虚拟机由处理能力表示,单位为百万指令/s(MIPS)。在本研究中,对所提出的算法进行了一些假设:
1)待处理事件包括一组独立任务;
2)任务没有最迟完成时间或优先级;
3)虚拟机之间没有优先级;
4)虚拟机上任务的执行时间可以被估计;
5)每台虚拟机实行先到先服务的策略。
设m表示系统中可用的一组虚拟机,每个虚拟机每次与一个任务关联。每个任务执行花费一定的时间,可以用任务的计算成本和虚拟机的处理能力进行评估。完成任务所花费的时间用CT表示,即完成时间。
1)任务定义
T={t1,t2,…tn}表示一组任务,n为任务数。每个任务都有任务标识号(Tid)和计算成本(ci)。
2)虚拟机定义
虚拟机集定义为VM={M1,M2,M3,…Mm},虚拟机数为m。每台虚拟机由机器号(Mid)和处理能力(cj)组成。
3)执行时间的计算
执行时间的估计用ET(ti,Mj)表示,表示虚拟机j执行任务i的估计时间。它是通过将任务i的计算成本ci除以虚拟机j的处理能力cj得出。
4)适应度函数一
任务的总完成时间用分配给不同机器的所有任务中的最大完成时间表示,即Makespan。该适应度函数计算如下:
Makespan=max(CT(ti,Mj))
CT(ti,Mj)=StartTimei+ET(ti,Mj)
其中,StartTime是虚拟机可用时任务的开始时间。
5)适应度函数二
为了获得最小的完成时间,必须更好地利用资源。为了获得更好的负载均衡水平,选择迄今为止利用率最低的资源。平均资源利用率和负载均衡水平函数为
AvgRU=
其中,RUi是单个虚拟机i的资源利用率,m是虚拟机数。
6)负载均衡等级β
β=[1- ]×100%
其中,RUi是每个虚拟机的资源利用率,m是机器数,β是负载均衡级别。当β等于100%时,虚拟机获得最优的负载均衡水平。用负载均衡等级函数β来描述负载均衡水平,其是算法评价指标之一。
本文提出了一种面向完成时间与负载均衡的任务调度算法,以提升资源的充分利用率,提高吞吐量。具体将专注于以下两个目标的优化,即最大完成时间(Makespan)和负载均衡水平。
2 面向完成时间与负载均衡的蚁群算法(TL-ACO)
面向完成时间与负载均衡的蚁群算法(TL-ACO)是对云环境中独立任务调度的算法,其目标是实现高负载均衡并减少任务完成时间。蚁群算法的核心思路是模拟蚁群的搜索行为。当一群蚂蚁寻找食物时,它们会分泌出一种特殊的化学物质,称为信息素。首先,蚂蚁随机开始寻找食物,当找到食物来源时,它们会将信息素洒在路径上,蚂蚁通过感应土壤上的信息素来追踪前一只蚂蚁食物来源的踪迹。随着这个过程的继续,路径上积累了大量的信息素,通过信息素的指引,大多数蚂蚁会选择迄今为止最好的路径[9]。基于蚁群算法基本原理,结合NSGA-Ⅱ中非支配排序思想对多目标进行优化,本文提出基于面向完成时间与负载均衡的蚁群算法(TL-ACO),算法具体定义如下:
1)初始化信息素
信息素τ0的初始值在信息素矩阵中取0.5,代表每条路径信息素相同。当蚂蚁沿着路径行进时,它会不断更新信息素轨迹,提供给下一只蚂蚁使用。信息素矩阵的值对每个蚂蚁都是不同的。
2)概率计算
在初始化该算法的所有参数后,每只蚂蚁k(k=1,…,N。N为总蚂蚁数),通过执行n个步骤(n是总任务数)构造一个巡逻,其中应用了概率转移规则。假设一共n个任务和m个虚拟机,第k只蚂蚁的虚拟机j(VMj)执行任务i的概率 为
=
其中,ηij是启发因子,一般取值为任务ti在虚拟机Mj上花费的全部时间的倒数。τij表示任务ti选择虚拟机Mj的信息素值。α表示信息素启发系数,代表信息素的重要程度。β表示启发因子的重要程度。allowk表示蚂蚁下一步允许选择的虚拟机。
3)信息素更新
在完成构建巡逻后,每只蚂蚁k在路径上留下相应的信息素,其数值计算为
Δτ=
其中,Δτ是信息素的最小变化值,最大完成时间采用式(1)进行计算。
4)局部信息素
依据最高概率将任务i分配到虚拟机j上,则路径ij上的局部信息素τij更新为
=(1-ρ)* +Δτ
其中,ρ表示信息素蒸发系数,Δτ表示信息素变化量。
5)全局信息素
当所有蚂蚁都构建好相应的解,即每次算法迭代之后,要对全局信息素进行更新。更新规则如下:
←(1-ξ)* +ξΔτ0
其中,ξ是全局信息素蒸发系数,Δτ0是上一次全局“最优蚂蚁”的信息素变化量。
6)非支配排序
NSGA-Ⅱ是印度科学家Deb于2002年提出的遗传算法衍生算法,其创新性地提出了适应度计算与非支配排序,将种群划分为非支配Pareto前沿[9]。为解决多目标问题,可以对两个目标适应度函数执行非支配排序。设两个目标个体为p与q,Sp为个体p支配个体的集合,np为支配个体p的个体数。如果p支配q,则将q添加到由p支配的集合;否则,增加p的被支配计数np。如果np=0,则p属于第一前沿,分配为级别1。然后更改Sp中的被支配个体,使其被支配计数n减1,如此时n=0,将其添加到下一个前沿。基于这种排序,可以形成最优解的Pareto前沿。
7)多目标蚁群算法的改进策略
蚁群算法中,概率选择公式(5)是算法的关键,决定蚂蚁在节点路径的选择方向,进而影响整个蚂蚁的路径。而路径启发因子ηij是决定路径选择概率 的主要因素之一,从这个角度出发,针对启发因子进行改进,可以提升蚁群算法的性能。在传统的蚁群算法中,启发因子ηij一般取值为任务ti在虚拟机Mj上花费的全部时间的倒数,计算公式为
ηij=
由公式(2)可计算任务ti在虚拟机Mj上花费的全部时间CT(ti,Mj),该启发因子任务分配中更倾向于选择计算能力更高的虚拟机,这会使得一些虚拟机负载严重,另一些虚拟机可能没有分配任何任务,从而导致资源利用不足,影响任务执行效率。针对这一问题,本文对启发因子进行改进,提出虚拟机负载修正系数ω。
ω=
其中,RUj为第j个虚拟机的资源利用率,AvgRU为当前所有虚拟机的平均资源利用率,由公式(3)计算得出。虚拟机负载修正系数ω小于1,代表当前虚拟机负载低于平均负载,可以更好地执行计算任务。负载修正系数ω大于1,则代表相对过载。
本文对启发因子ηij进行优化,将虚拟机负载修正系数ω应用到启发因子的计算中,进而影响整个概率的计算。改进后的启发因子ηij计算如下:
ηij=
虚拟机负载越低,执行时间越短,使得启发因子越大,被选择的概率越大。更改后的启发因子会使得蚂蚁优先选择计算能力更高和利用率最低的虚拟机,以最终获得最小完成时间和更好的负载均衡水平。
8)面向完成时间与负载均衡的蚁群算法
基于以上条件,本文提出的多目标蚁群算法步骤如下:
Step 1:初始化算法各参数,设置最大迭代次数IMAX;
Step 2:取一只蚂蚁携带m个任务,置于初始出发点;
Step 3:根据概率公式(5)计算蚂蚁下一步的路径方向,即将任务分配给虚拟机,直到完成所有任务的分配;
Step 4:根据公式(2)更新任务的完成时间(CT);
Step 5:对每只蚂蚁计算适应度函数,根据公式(1)和(4)计算最大完成时间(Makespan)和负载均衡水平β;
Step 6:根据公式(7)更新映射任务的信息素值,提供给下一个蚂蚁使用;
Step 7:重复执行Step 2到Step 6,直到所有蚂蚁已全部巡逻完毕;
Step 8:构造每只蚂蚁适应度函数的局部解;
Step 9:根据公式(8)更新全局信息素的解;
Step 10:对得到的解,执行非支配排序;
Step 11:若迭代次数小于最大迭代次数IMAX,转步骤二;
Step 12:返回最优解,并根据最优解将任务分配给VM。
该算法的目的是通过蚁群算法找到虚拟机与任务之间的最优映射,减少完成时间并实现负载均衡,从而提高系统的平均资源利用率。人工蚂蚁首先按照确定的顺序放置任务。每个蚂蚁将任务映射到特定虚拟机后,都可以产生信息素和启发因子,之后的蚂蚁根据公式(5),基于高概率规则将任务映射到虚拟机。先前蚂蚁将信息素值进行更新,提供给后续的蚂蚁使用。当每个任务都映射到特定虚拟机时,就构成了蚁群算法关于完成时间和负载均衡水平的局部解。每次迭代后,用信息素矩阵更新全局解,再将遗传算法(NSGA-Ⅱ)中的非支配排序思想应用于优化多目标解,以生成最优解的Pareto前沿。重复过程至最大迭代次数后,在全局解中找到最优解。
3 实验结果与分析
CloudSim是墨尔本大学Rajkumar Buyya教授推出的一款云计算仿真平台,可以模拟云计算基础设施,实现对云计算中任务调度的仿真[10]。公共计算环境作为一种云环境,可以采用CloudSim作为仿真实验平台,验证所提出面向完成时间与负载均衡的蚁群算法(TL-ACO)的有效性,同时将该算法与当今流行的NSGA-Ⅱ进行性能比较。
本节中的实验在Win10操作系统下采用基于Java平台的CloudSim仿真软件进行仿真和测试,并从负载均衡和完成时间两个方面对算法性能进行了评估。具体的仿真实验环境如表1 所示。
表1 仿真实验环境Tab.1 Simulation experiment environment |
| 实验环境 | 参数 |
|---|---|
| 操作系统 | Windows 10旗舰版 |
| 处理器 | Intel(R) Core(TM) i7-7700 CPU@2.80GHZ |
| 安装内存 | 8 GB |
| 系统类型 | 64位操作系统 |
| Java版本 | 1.80_181 |
| Eclipse版本 | 4.3.2 |
| CloudSim版本 | 4.0 |
在实验中,假设任务皆为独立任务,任务之间没有相互依赖。用于模拟分析的参数详见表2 ,其中,信息素启发系数α、期望启发因子系数β和蒸发率ρ的配置是关键,文献[11]中实验得到比较恰当的配置为1、5、0.5,本文也通过实验验证了取以上值时效果较好。经过实验,人工蚂蚁数量达到10以上时,结果改良不是很大,迭代次数达到5时候,结果已经趋于稳定,故分别取值为10、5。为了模拟真实的任务调度,设置相应的资源数与随机的任务大小,其中,任务、虚拟机和数据中心数详见表3 。
表2 蚁群算法参数Tab.2 Parameters of ACO |
| 参数 | 数值 | 参数 | 数值 |
|---|---|---|---|
| α | 1 | ξ | 0.1 |
| β | 5 | IMAX | 5 |
| ρ | 0.5 | Ants | 10 |
| τ | 0.5 |
表3 CloudSim平台相关类参数Tab.3 CloudSim toolkit parameter |
| 核心类 | 属性 | 数值 |
|---|---|---|
| 任务 | 任务大小 | 1 00030 000 |
| 任务数 | 10100 | |
| 网络 | 传输速率 | 2001 000 |
| 虚拟机(VM) | 虚拟机数 | 530 |
| 处理能力(MIPS) | 1001 000 | |
| 数据中心 | 数据中心数 | 10 |
| 主机数 | 26 |
实验中,只考虑了不依赖于其他任务的独立任务调度。根据负载均衡等级和完成时间来评估性能,将本文提出的多目标蚁群算法(TL-ACO)与多目标优化算法NSGA-Ⅱ进行性能比较。通过改变任务和虚拟机器的数量,在不同情况下展示两者算法的性能,用任务的执行时间来描述最大完成时间,用公式(4)计算负载均衡等级β,来描述负载均衡水平,β越大,表明系统负载均衡度越好,在100%时达到最优。
为模拟现实中遇到的轻量级模型任务调度,选取任务数为10、50、100,虚拟机数为5、10、15,进行实验,每次实验都在相同环境下运行20次,并取平均值作为算法的最终性能评价。图13 显示了负载均衡和完成时间之间的最优解的Pareto前沿。
结果表明,在不同的任务与虚拟机条件下,相比NSGA-Ⅱ,TL-ACO的负载均衡等级更高,任务的完成时间更少。
4 结束语
本文提出了一种优化最大完成时间和负载均衡的多目标任务调度算法。该算法使用改进蚁群优化算法获得局部最优解,应用非支配排序获得Pareto前沿解集,表示云环境中完成时间和负载均衡之间的权衡,从而达到较高的吞吐率和较好的资源利用率。最后使用CloudSim平台对所提出的调度算法进行了仿真,评估不同任务与虚拟机数时的性能表现。最终得到以下结论:
1) 算法考虑负载均衡性,在启发因子中加入负载修正系数,实现对状态转移概率函数的优化;
2) 设计适应度函数,提出负载均衡等级,实现对任务最大完成时间和负载均衡等级的评估;
3) 融合非支配排序思想,对多目标进行优化,得到Pareto前沿解集;
4) 实验评估了迭代次数、蚂蚁数量、信息素启发系数,期望启发因子系数和蒸发率的影响,并确定了其最佳值;
5) 结果表明,所提出的任务调度TL-ACO算法与NSGA-Ⅱ相比性能更优异。
该算法在实验中只考虑了理想环境下不依赖于其他任务的独立任务调度。实际应用中,任务之间往往相互关联,有优先级之分,未来的改进工作应考虑此因素。