基于改进蚁群算法的网格资源调度

　增刊　　　　　　　　　　　　　黄文明等:基于改进蚁群算法的网格资源调度113

素,如

Tk(0)=

aTp(0)+bTb(0)+cTd,a+b+c=1

(2)

7个步骤.

1)用户提交任务,并插入到任务队列中等待调

其中a、b、c分别表示资源节点的处理能力信息素、通信能力信息素和可信度信息素在整个初始信息素中所占的比重.2.2.2　路径选择机制系统初始化完毕后,根据各资源节点上的信息素,利用式(3)计算出节点分配到任务的概率,此概率随着资源信息素的改变而改变,是蚂蚁选择下一个节点的参考值.

Pk(t)=

1η2

μμ

[Tu(t)]1×[ηu]2

μ

μ

度,同时系统为每个任务设置优先级,按照优先级

的高低进行分配任务,原则是优先级高的任务先调度.优先级随着任务的长度变化而变化,长度越长的任务其优先级越高,长度越短的任务其优先级越低.

2)利用式(2)初始化网格各资源节点的初始信

u

　k和u为未访问节点

息素,同时也对禁忌表tabuk进行初始化,把资源节点的ID号都存入到相应的禁忌表中.

3),(3),ID号从禁忌表4)当任务正常分配给资源,并且禁忌表不为空时,利用式(4)进行局部信息素更新.

5)当资源节点已经接受的任务被执行完毕,并且禁忌表为空时,如果任务成功返回,统计执行结果,利用式(1)对节点的可信度进行更新,并采用式(5)对节点信息素进行全局实时更新.式(5)中,ΔTk=CeK,同时再次对禁忌表进行重新初始化.

6)如果任务返回失败,则启动重调度机制,将失败任务重新插入任务队列中,等待重新分配.对禁忌表进行重新初始化,并利用式(1)对节点的可信度进行更新,同样也采用全局更新机制(如式(5)所示,且ΔTk=CpK)对该节点的信息素进行更新.

7)重复第3)～第6)步骤,直到所有任务都被成功执行,达到预定要求为止.

0其中,Pk(t);Tk(t)k在;ηk=

Tk(0),它表示节点k的固有属性;参数

μ1和μ2为用于调节Tk(t)与ηk之间的权重,当μ1变小时,算法收敛速度较快,当μ2变小时,算法收敛速度较慢.2.2.3　局部更新机制当任务被分配到某个资源节点上时,资源的信息素会随之发生改变,可以根据蚁群经过路径所耗资源量,利用信息素局部更新机制对节点进行更新,信息素浓度为

d

ρTol+ΔTkk

new

(4)Tk=

ΔTk=-K

其中,ρ为信息素的持久性;K为任务运算量和通信量.

信息素局部更新机制可以适当地减少路径上的信息素,有利于蚁群探索不同的路径,增加解的多样性,增大获得最优解的概率.2.2.4　全局更新机制

3　仿真结果与性能分析

在网格资源调度中,min2min算法具有较好的

性能和算法复杂度,它主要是优先对完成时间最小的任务进行调度.min2min算法一般作为调度算法的评测基准.仿真实验主要是对改进蚁群算法和传统的min2min算法在资源利用率和任务提交成功率两方面进行比较,以验证改进蚁群算法的优越性.

资源的属性设置如表1所示.

在GridSim仿真平台中,首先随机生成10个资源,再随机产生30、60、100、150和180个任务,并把每个任务依次提交至网格系统中进行调度.

在任务数量不断增加的情况下,改进蚁群算法和min2min算法在资源利用率方面的比较如图1所示.

当资源节点完成任务并返回时,进行资源信息素全局更新,信息素浓度为

newold

(5)Tk=ρTk+ΔTk

当任务成功返回时,ΔTk=CeK.其中Ce为奖励因子,表示成功经验增加,一般取值为0.6.当任务返回失败时,ΔTk=CpK,其中Cp为惩罚因子,表示失败经验增加,一般取值为-1.2.2.3　基于改进蚁群算法的网格资源调度的流程

基于改进蚁群算法的网格资源调度的流程包括