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

112北京邮电大学学报　　　　　　　　　　　　　　　　　第32卷

接网格底层和高层功能的纽带,是协调整个网格系

统有效运转的中枢.一个高效的资源调度策略对于提高网格系统性能尤为重要.因此,在网格技术飞速发展的形势下,网格资源调度技术的研究应受到重视.

率就越大.而其他路径上的信息素会随着时间的推移慢慢挥发,这就形成了一种信息正反馈现象,使得最终所有的蚂蚁都选择走蚁穴到食物源的最短路径.

下面以求解TSP问题为例,说明基本蚁群算法的实现步骤.

1)初始化各个城市(点)之间的路径信息素.2)将m个不同蚂蚁随机放置在n个不同的城市中.

3)每只蚂蚁通过各条路径上的信息素计算出转移概率,,并把选择的5清空禁忌表并返回到第2)步,循环至满足退出条件为止,并输出最优结果.2.2　蚁群算法的改进思想

改进的蚁群算法引入了2个概念:禁忌表ta2buk和资源节点的可信度[627].

1　基于网格的资源调度技术的优势

目前,我国大多数网络都是构建在传统技术的基础上,这样的网络由很多结构复杂的异构子网构成,不同的子网之间需要进行资源的调度、数据互操作和共享,因此,确保信息的安全性成为难题,在一定程度上限制了用户的交流.

与传统的网络相比,基于网格的资源调度技术具有3个优势[3].

1),相对较低.合起来,形成,其工作速度快、效率高、负载均衡.

2)传统网络的资源是存储在某一指定服务器之上,用户要通过服务器对资源进行共享,它的共享空间有限.网格资源调度则可以提供各种广域上分布、本质上异构、归不同人和组织拥有以及动态变化的资源,它的共享空间是整个网络.

3)传统网络需要进行大量的资源和数据交换,而网格资源调度只需要制定高效的策略,把最优或符合要求的资源调度给用户,这样就极大地减少了交换数据的次数.

禁忌表tabuk用来存储蚂蚁未走过的所有资源节点ID号,其中下标k表示此禁忌表是第k只蚂蚁所拥有的.禁忌表的目的是为了避免蚂蚁重复走相同的路径.当蚂蚁寻找下一个节点时,寻找的范围只能局限于禁忌表所存储的节点;当蚂蚁已经访问了某个节点时,该节点就会从此禁忌表中删除.算法通过判断禁忌表是否为空,从而判断蚂蚁是否走完了所有的资源节点.

节点的可信度是对资源节点可靠性的一种评估,可信度越高,表示此节点越可靠、安全,任务则优先分配给可信度高的资源节点.采用网格资源节点实际完成任务调度的成功率来进行量化,即

(1)Td=Ts/Ta

其中,Td为资源节点的可信度;Ta为该节点已经接受的所有任务总数;Ts为节点成功完成的任务数.Ts越大,该资源节点的Td越高,执行任务的错误率就越低,当Ts=Ta时,即节点完成了所有接受的任务,它的可信度为1,说明该资源可靠性和安全性都很高.2.2.1　信息素初始化

在任务分配给资源之前,必须初始化网格系统中各资源节点的信息素.改进蚁群算法选用资源所包含的处理器个数n和其处理能力p(MIPS)、通信能力以及节点的可信度(Td)作为资源的初始信息

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

策略的设计

　　为了对网格系统中的资源进行有效管理,通过

改进基本的蚁群算法,提出了一种基于此改进蚁群算法的网格资源调度策略,它不仅提高了资源的利用率,而且缩短了收敛到最优解的时间.2.1　基本蚁群算法的原理

蚁群算法[425]是由M.Dorigo等在1991年首先提出来的一种源于生物世界的仿生类方法.经过对蚁群觅食行为的研究发现,蚂蚁在觅食的过程中能在其所经过的路径上留下一种叫做信息素(phero2mone)的化学物质,它们通过这种化学物质相互传递信息.蚂蚁一般总倾向于走那些信息素浓度高的路径.这样,某一路径上通过的蚂蚁数目越多,留下的信息素浓度就越高,则后续蚂蚁选择该路径的概