一种基于合作博弈的网格虚拟组织形成方法

网格计算中, 有两类参与者:用户和网格服务提供者。用户提交应用程序, 服务提供者组合资源来执行用户程序。服务提供者通过组成虚拟组织来对动态的、单个的程序提供必需的资源。

合作博弈模拟决策者之间的交互。将网格服务提供者看作是决策者, 用Myerson的合作结构体作为合作联盟的基础, 把虚拟组织联盟模型化为合作联盟问题。这样就能利用合作博弈模型来研究、分析虚拟组织的形成。

基于模型提出一个资源管理系统——虚拟组织联盟管理器。它不仅可以跨网格复制, 允许用户、服务提供者同本地的副本交互;而且还管理着服务提供者之间的信息交换, 便于有效形成虚拟组织联盟进而选择一个虚拟组织来完成程序的执行。

1 虚拟组织形成

基于列表调度方法, 设计了一个启发学习法。它假设联盟的整个成本最小, 就使服务提供者的收益最大。用启发学习法计算出给定合作联盟S的最低成本, 从而得到最低成本映射关系。

算法1 (最小成本算法) 。

在以上算法中, 针对合作联盟S中的服务提供者, 用完全多项式时间G A P算法来计算 (1+ε) , 0<ε<1。若假定P是成本范围, d是时间范围, 那么针对合作联盟S计算映射πS, 要满足以下条件。

计算的结果, 映射将在截止期限和支付的 (1+ε) 倍之内。最小成本算法用一个简单的启发学习法找到了最低成本映射关系。启发学习法的原理如下:在所有未分配任务中, 若任务是最低成本分配, 且分配不导致G超过截止期限, 则任务被安排给。对每个任务Ti, i=1, 2, …, n, 存在一个优先队列TQi, 对任意i和j, 按非递减成本来排序元组。

由最小成本算法确定的映射πs可能会使某些服务提供者得不到任务。可以将这些服务提供者从合作联盟中删除, 不会影响映射或成本, 相反会增加合作联盟中活动成员的收益。

2联盟管理器框架

利用上述合作联盟模型, 可以形成虚拟组织联盟, 我们还提出了一个资源管理系统——虚拟组织联盟管理器。虚拟组织联盟管理器作为一个网格中间件, 用来管理用户和服务提供者的程序和资源, 并负责调度资源来完成程序。它不仅被网格实现支持, 还可以跨网格系统进行复制, 允许用户和服务提供者跟本地拷贝进行交互。

对于G`h, h=1, 2, …, k, 为了选择他的首选虚拟组织, 在2 k个可能的合作联盟中, 他必须通过映射计算来确定每个合作联盟的值。这些计算不仅耗时, 而且还耗费成本, 但却得不到回报。因此, 服务提供者需要用启发学习法来缩短计算时间以增加收益。这就导致服务提供者之间不可能共享算法。但对一个服务提供者来说, 把自己的首选虚拟组织和关联映射公开, 是非常有利的。这样, 该虚拟组织中的其他成员就可方便、快速地估算是否该联盟也是自己的首选联盟。

没有好办法能让服务提供者在一个有限的时间内确定他的首选虚拟组织。但仍然有两种方法可采用: (1) 通过检查包含很少 (小于k) 服务提供者的所有可能的虚拟组织, 可以计算出服务提供者的首选虚拟组织; (2) 先随机产生一个虚拟组织, 然后把服务提供者作为它的一个成员来计算。

每个服务提供者都会把他的首选虚拟组织和映射信息传给虚拟组织联盟管理器, 然后被公开给其他人。一旦两个服务提供者都同意时, 链接就建立。链接形成后, 联盟管理器就得到满足条件的虚拟组织集合, 其中值为0的虚拟组织将被删除。最后, 联盟管理器从剩下的虚拟组织集合中随机选择一个来完成程序。下面描述了虚拟组织形成过程中的协议。

协议1 (虚拟组织形成过程) 。

阶段1:初始化。

(1) 服务提供者通知联盟管理器, 准备就绪。

(2) 用户提交程序给联盟管理器。

(3) 联盟管理器通知服务提供者, 有程序等待执行。

阶段2:提交。

(1) 对未处理的程序, 服务提供者G估算成本和时间。

阶段3:虚拟组织形成。

(1) 联盟管理器分派成本和时间集合给那些已提交的服务提供者:

(2) 联盟管理器公开一个随机的排序规则。

(3) 服务提供者执行逆序归纳法, 计算策略组合。

(4) 联盟管理器逐个通过排序规则, 在每个链接上, 联盟管理器把当前虚拟组织形成的状态通知给跟链接关联的服务提供者, 这样服务提供者就可声明是接受或拒绝该链接。当两个服务提供者都接受时, 链接就形成。

(5) 虚拟组织的集合被确定。

(6) 联盟管理器删除那些值为0的虚拟组织。

(7) 联盟管理器从剩余的虚拟组织集合中随机选择一个虚拟组织S。

(8) 虚拟组织S来执行该程序。

3 结语

本文为自治的网格服务提供者之间形成虚拟组织提出了一个模型, 并描述了虚拟组织形成的过程。最后, 提出了一个管理虚拟组织联盟的资源管理系统——虚拟组织联盟管理器。

摘要：网格计算中, 需要资源组合起来执行程序。网格服务提供者作为计算资源的拥有者, 必须形成虚拟组织才能提供组合资源。虚拟组织中的每个服务提供者都想最大化自身的利益, 网格服务提供者之间的资源组合可看作是博弈论中的合作联盟问题。基于博弈论中的合作结构体, 提出了一种框架来模型化合作联盟问题。利用这种框架设计出一种资源管理系统, 来支持网格服务提供者之间虚拟组织的形成。

关键词：网格计算,资源组合,虚拟组织,合作博弈,合作联盟