正在加载图片...
第12期 郝卫东等：基于运行时间权矩阵的网格服务匹配问题的优化解 ,1283 何等，因此，建立独立于资源提供者和资源消费者 是当且仅当对所有的S三V1有如下表达式成立： 的匹配服务，形成服务网格的简化三元模型，该模 Isl≤Ir(S)I (1) 型包括如下部分 其中，R(S)={v∈V2u:∈V1,且(vi,v)是网格 Jobmanager(作业管理器)：服务网格的服务消 G的一条边}. 费者代理，它作为终端用户的入口，提供作业提交、 证明：根据Hall定理，由于G是一个有向偶图， 查询和删除等的处理接口· 因此在G中存在完备匹配的充分必要条件就是 Servicemanager(服务管理器)：服务网格的服务 式(1) 提供者代理.它管理资源，并负责调度合适的作业 为了便于用计算机程序实现完备匹配的判断， 到该资源上运行 给出如下定理 Matchmaker(匹配器)：其功能是通过某种算法 定理2设存在网格G只V1,V2,E,W)符合 寻找消费者和提供者之间可能的匹配，并通知匹配 定义1，令D1表示作业集合V1中顶点的最小度， 的各方进行绑定操作. D2表示服务集合V2中顶点的最大度，那么存在满 下面从图论0]的角度给出上述网格三元模型 足定义2的完备匹配的充分必要条件是当且仅当 的定义 0KD2≤D1 (2) 令有向带权偶图G=V,E,W),其中顶点集 证明：先证必要性，设M是G中从V1到V2 V={v1,2,…,vn},边集E={e1,e2,…,em{,对 的一个完备的匹配，则有V1中的p=V1个顶点 于G中任意一条边(u1,)都存在实数心∈W与 与V2中对应的g=「V2个顶点构成匹配的边集， 之对应，称W为权集，必可将V分成两个子集V1 由定义2知0<p≤q· 和V2,并且满足V1∩V2=0,V1UV2=V,使得 又由于V1中p个顶点至少关联pD1条边，而 G中任意一条边e(e时=(vi,)∈E)的两个端点， V2中q个顶点至多关联qD2条边，若要存在从V1 一个属于V1(如v:∈V1),另一个属于V2(如v∈ V2) 到V2的一个完备的匹配，则必然有pD1≥gD2· 又由于D2>0,D1>0系统才有意义，所以 根据上面的描述，给出服务网格的定义如下， 0<D2≤D1· 定义1定义网格G为有向带权偶图G= 再证充分性，设网格作业S三V1,由于作业集 (V1,V2,E,)的形式，其中用V1表示网格作业 合V1中顶点的最小度是D1,因此对任何属于V1 集合，V2表示网格服务集合，记网格作业集合的作 的网格作业子集S,其中的顶点至少与D1S条边 业个数为p=V1,网格服务集合中的服务个数为 相邻，即D1S给出了S中顶点关联的边数的下 q=Vz;E表示网格作业和网格服务之间可能存 界估计值， 在的匹配；W表示网格作业和网格服务之间某个匹 配的数量指标，本文中赋予它作业完成时间的含义， 设R(S)=∈Vzv:∈V1,且(ui,)是网 格G的一条边，由于服务集合V2中顶点的最大 即0：∈W表示在服务j上完成作业i所花费的时 间，其中=1,2，…，p;=1,2,…,q 度是D2,因此对任何属于V1的网格作业子集S, 定义2设存在网格GV1,V2,E,W)符合 最多有D2R(S)条边与R(S)中的顶点关联，所 定义1，若存在E*三E,使得E*中任意两边均不相 以D2R(S)给出了S中顶点关联的边数的上界 邻，则称E为G中的一个匹配.若在E中再加 估计值 上任意一条边e,E*U1el中必存在着相邻的边，则 因此，比较这两个估计值可得如下不等式： 称E为G中极大匹配，G中边数最多的匹配称为 D1S≤D2R(S) (3) 最大匹配，其元素个数称为G的匹配数，若E*是 已知0<Dn2≤D1,有： 一个最大匹配，且|E*I=min V1,|V2I{,则称 DzR(S)|≤D1lR(S)l (4) M为G中的一个完备匹配， 根据式(3)有： 在上述定义的基础上，根据Hal定理o),可得 D1lsl≤D2R(S)l≤D1lR(S)l,(5) 如下定理， 推出|S|≤|R(S).根据定理1得存在从作 定理1设存在网格G只V1,V2,E,W)符合 业V1到服务V2的完备匹配 定义1，若存在网格作业S二V1,则存在满足定义2 特别地，当D2=D三t≥1时定理2仍成立， 的与之对应的网格服务的完备匹配的充分必要条件 称其为t条件.何等．因此建立独立于资源提供者和资源消费者 的匹配服务形成服务网格的简化三元模型．该模 型包括如下部分． Jobmanager（作业管理器）：服务网格的服务消 费者代理．它作为终端用户的入口提供作业提交、 查询和删除等的处理接口． Servicemanager（服务管理器）：服务网格的服务 提供者代理．它管理资源并负责调度合适的作业 到该资源上运行． Matchmaker（匹配器）：其功能是通过某种算法 寻找消费者和提供者之间可能的匹配并通知匹配 的各方进行绑定操作． 下面从图论［10］的角度给出上述网格三元模型 的定义． 令有向带权偶图 G＝〈V EW〉其中顶点集 V ＝｛v1v2…v n｝边集 E＝｛e1e2…em｝对 于 G 中任意一条边（ vivj）都存在实数 wij∈ W 与 之对应称 W 为权集必可将 V 分成两个子集 V1 和 V2并且满足 V1∩ V2＝∅V1∪ V2＝ V 使得 G 中任意一条边 eij（eij＝（ vivj）∈ E）的两个端点 一个属于 V1（如 vi∈ V1）另一个属于 V2（如 vj∈ V2）． 根据上面的描述给出服务网格的定义如下． 定义1 定义网格 G 为有向带权偶图 G ＝ 〈V1V2EW〉的形式．其中用 V1 表示网格作业 集合V2 表示网格服务集合记网格作业集合的作 业个数为 p＝｜V1｜网格服务集合中的服务个数为 q＝｜V2｜；E 表示网格作业和网格服务之间可能存 在的匹配；W 表示网格作业和网格服务之间某个匹 配的数量指标本文中赋予它作业完成时间的含义 即 wij∈ W 表示在服务 j 上完成作业 i 所花费的时 间其中 i＝12…p；j＝12…q． 定义2 设存在网格 G＝〈V1V2EW〉符合 定义1若存在 E ∗⊆ E使得 E ∗中任意两边均不相 邻则称 E ∗为 G 中的一个匹配．若在 E ∗ 中再加 上任意一条边 eE ∗∪｛e｝中必存在着相邻的边则 称 E ∗为 G 中极大匹配．G 中边数最多的匹配称为 最大匹配其元素个数称为 G 的匹配数．若 E ∗是 一个最大匹配且｜E ∗｜＝min｛｜V1｜｜V2｜｝则称 M 为 G 中的一个完备匹配． 在上述定义的基础上根据 Hall 定理［10］可得 如下定理． 定理1 设存在网格 G＝〈V1V2EW〉符合 定义1若存在网格作业 S⊆ V1则存在满足定义2 的与之对应的网格服务的完备匹配的充分必要条件 是当且仅当对所有的 S⊆ V1 有如下表达式成立： ｜S｜≤｜R（ S）｜ （1） 其中R（ S）＝｛vj∈ V2｜vi∈ V1且（ vivj）是网格 G 的一条边｝． 证明：根据 Hall 定理由于 G 是一个有向偶图 因此在 G 中存在完备匹配的充分必要条件就是 式（1）． 为了便于用计算机程序实现完备匹配的判断 给出如下定理． 定理2 设存在网格 G＝〈V1V2EW〉符合 定义1令 Dv1表示作业集合 V1 中顶点的最小度 Dv2表示服务集合 V2 中顶点的最大度那么存在满 足定义2的完备匹配的充分必要条件是当且仅当 0＜ Dv2≤ Dv1 （2） 证明：先证必要性．设 M 是 G 中从 V1 到 V2 的一个完备的匹配则有 V1 中的 p＝｜V1｜个顶点 与 V2 中对应的 q＝｜V2｜个顶点构成匹配的边集 由定义2知0＜ p≤q． 又由于 V1 中 p 个顶点至少关联 pDv1条边而 V2 中 q 个顶点至多关联 qDv2条边若要存在从 V1 到 V2 的一个完备的匹配则必然有 pDv1≥qDv2． 又由于 Dv2＞0Dv1＞0系统才有意义所以 0＜ Dv2≤ Dv1． 再证充分性．设网格作业 S⊆ V1由于作业集 合 V1 中顶点的最小度是 Dv1因此对任何属于 V1 的网格作业子集 S其中的顶点至少与 Dv1｜S｜条边 相邻即 Dv1｜S｜给出了 S 中顶点关联的边数的下 界估计值． 设 R（ S）＝｛vj∈ V2｜vi∈ V1且（ vivj）是网 格 G 的一条边｝由于服务集合 V2 中顶点的最大 度是 Dv2因此对任何属于 V1 的网格作业子集 S 最多有 Dv2｜R（ S）｜条边与 R（ S）中的顶点关联所 以 Dv2｜R（ S）｜给出了 S 中顶点关联的边数的上界 估计值． 因此比较这两个估计值可得如下不等式： Dv1｜S｜≤ Dv2｜R（ S）｜ （3） 已知0＜ Dv2≤ Dv1有： Dv2｜R（ S）｜≤ Dv1｜R（ S）｜ （4） 根据式（3）有： Dv1｜S｜≤ Dv2｜R（ S）｜≤ Dv1｜R（ S）｜ （5） 推出｜S｜≤｜R（ S）｜．根据定理1得存在从作 业 V1 到服务 V2 的完备匹配． 特别地当 Dv2＝ Dv1≡ t≥1时定理2仍成立 称其为 t 条件． 第12期 郝卫东等： 基于运行时间权矩阵的网格服务匹配问题的优化解 ·1283·