吴　芳　朱尚明

(华东理工大学计算机科学与工程系　上海 200237)



基于功能划分图的Web服务组合规划和最优选择

吴芳朱尚明*

(华东理工大学计算机科学与工程系上海 200237)

扩展Web服务类型的组合方式、实现服务的无缝组合和提高服务组合的可靠性是当今Web服务组合的研究热点。针对Web服务类型组合方式多样性和无缝服务组合问题，根据请求服务的功能划分图来计算可用于服务组合的候选服务类型，动态规划各种服务类型的组合方式，并提出第一级服务类型的装配算法。针对服务组合的可靠性问题，将Web服务自身对运行环境的要求和自身的优先条件表示为上下文，并提出相应的局部最优选择算法和全局最优选择算法，以找到真实的、具有高可靠性的服务组合。最后，通过仿真实验验证了第一级服务类型装配算法、局部最优和全局最优选择算法的性能。

Web服务组合功能划分图第一级服务装配算法局部最优选择算法全局最优选择算法

0　引　言

随着互联网以及云计算技术的发展，越来越多的Web服务出现在互联网以及云计算平台上。Web服务是可以跨越整个Web被发布、定位以及调用的自包含、自描述的模块化应用。如何有效地组合分布于Internet中的各类Web服务，实现服务之间的无缝集成，形成功能丰富的企业级服务流程，已经成为Web服务发展过程中的一个重要步骤。Web服务组合的研究正是在这种背景下被提出来，并吸引了学术界和工业界的广泛关注。Web服务组合作为一种应用模式，可以在保证Web服务的质量和服务独立性以及满足用户约束的前提下，发现一组服务并将其组合成一个新的、功能更加复杂的服务[1]。

Web服务组合是针对Web服务进行资源管理与整合的重要技术和手段。然而，随着Web服务的迅速增长，通过逐一匹配请求服务的单个抽象功能来进行服务组合的方式对Web服务的利用率变得越来越低。互联网环境千差万别，不同的Web服务正常运行的环境也不一样，在服务选择阶段，仅仅通过运行成功率这一统计性标量已不足以选择到真实环境下高可靠性的服务。实现Web服务的无缝组合和提高服务的可靠性、扩展性已成为当今Web服务组合研究领域的热点问题[2,3]。

本文在Web服务组合方式规划上将针对组合方式的多样性和无缝性问题，提出一种基于请求服务功能划分图的动态Web服务组合方法。在组合服务的选择上将针对服务的可靠性问题，提出带约束上下文的局部最优选择算法和全局最优选择算法。目前云平台上的Web服务既有独立的集成软件，也有适用于工业流程的组件，本文提出的算法对这两类应用场景都适用。

1　相关工作

目前对Web服务组合技术的研究可以分为两类：基于工作流的服务组合和基于人工智能规划的服务组合[4]。例如，文献[5-9]介绍了基于工作流图的动态服务组合和选择算法，其思想是根据流程图逐步选择最优的服务，将最优服务组合和选择问题转换为求最优路径问题。文献[1]介绍了基于人工智能的服务组合优化方法，通过统计特征来把握候选服务的全局特性，使用遗传算法求出最优解。随着互联网以及云计算技术的发展，越来越多的Web 服务出现在互联网上，只逐个匹配请求服务的各个抽象功能来确定候选服务，并从中选择和组合出Web服务已经不能满足当前的需要了。为扩展Web服务组合的方式，很多学者都把目标放在扩大候选服务类型集上，文献[2]提出了服务内扩展和服务外扩展方法，文献[10]采用聚类技术和结构化服务发现相结合的方法来为Web服务归类，文献[11]采用计算流程相似度来查找所需候选服务。服务类型集的扩大必然引起组合方式的多样性，在最优服务组合选取上，文献[3]采用嵌套组合的方法，文献[12]则提出了基于相似度的模糊预测的方法，文献[13]和文献[14]也各提出一种模型来力求最大限度找到能组合出满足用户需求的候选服务并将它们装配起来。但是，这些方法都不能完整表现出服务间的关系。因此，对于包含多个请求服务的抽象功能的候选服务，其服务组合方式也就不确定，从而产生了无缝组合问题。Web服务的无缝组合就是如何完整和正确地将候选服务装配成满足请求服务要求的服务组合。

Web服务千差万别，其对运行环境的要求也各有不同，Web服务组合面临多样性的问题。文献[2]提出了服务约束-感知机制来确保Web服务在正确的环境中运行，但是文献[2]在初始化及预包装上没有提出相应的算法，而且深度优先的图算法的复杂度很高。文献[15]提出了用上下文来表述服务特殊要求的方法，其思想是后退一步来查验当前选择的服务是否是最优的，是则继续到下一步，否则在退后一步的前提下选择最优。然而这个算法只适用于功能呈顺序关系，不能满足请求服务的功能间呈非顺序关系的情况。

本文提出的Web服务组合和选择方法分为两个阶段：(1)基于请求服务的功能划分图来计算出所有可用于服务组合的候选服务类型，同时通过精确匹配来确定出各个类型的候选服务集，并规划出各种服务类型组合方式；(2)查找各个组合方式下的最优服务组合，比较产生最优的服务组合。考虑到各个Web服务会受环境的影响，本文采用上下文结构来表述每个具体Web服务或服务组合自身对运行环境的要求和自身具有的优先条件，并提出基于这种上下文的局部最优选择算法和全局最优选择算法来找出高可执行性的最优服务组合。

2　Web服务组合方式规划

目前，在Web服务的识别上有基于输入和输出参数的[4]，还有基于功能语义描述的[2]，本文采用解析请求服务的输入和输出参数来确定单个服务的类别。对于用户的请求服务，如何抽象出其包含的各个功能和它们之间的关系，以及每个功能对应的参数，目前已有很多研究。本文将在确定出请求服务的各个抽象功能、各个抽象功能的输入和输出参数以及请求服务的功能划分图的基础上，进行Web服务组合的研究。

服务不仅具有功能特性，还有输入、输出参数的差别[9]。本文采用分级思想，对于在功能及相应功能的输入、输出参数上都完全或部分符合请求的服务采用第一级服务组合；对于在功能上满足请求服务的某个功能，但是在输入、输出参数上却不满足相应要求的服务采用第二级服务组合。本文重点研究第一级服务组合。

2.1基本概念

为便于理解Web服务的组合方式，首先介绍本文定义的几个基本概念。

定义1请求服务的功能关系：指请求服务的各个功能间的行为关系和数据关系。

一般，功能间的行为关系分为顺序关系和并行关系两种，且呈顺序关系的两个功能才可能有数据关系。本文通过匹配输入参数和输出参数来抽象各个功能，而各个参数又反映了功能间的数据关系。因此，也可以通过匹配输入和输出参数来确定出整个功能间的关系。

定义2请求服务的功能划分图：指反映请求服务的各个抽象功能及各个抽象功能间关系的图，图有两个虚拟节点表示开始与结束，其他节点表示请求服务的抽象功能，抽象功能节点间的边表示抽象功能间的功能关系。

定义3第一级服务：指一个Web服务能满足一个或多个Web请求服务的抽象功能，这些抽象功能间的关系必须与请求服务的功能关系一致。同时其输入参数和输出参数也满足请求服务在这些功能上的参数约束。

定义4第二级服务：指一个Web服务能满足某一个请求服务的抽象功能，但其输入参数和输出参数无法满足请求服务在这个功能上的参数约束。第二级服务只涉及一个请求服务的抽象功能，所以没有功能关系的限制。

匹配技术、分类技术和装配技术是形成Web服务组合的三项关键技术[16]。匹配Web服务的过程也是搜索候选Web服务的过程，为了匹配出上述所提到的第一级服务，可以在匹配Web服务的过程中，将Web服务分为完全匹配服务、部分匹配服务、约束不匹配服务和完全不匹配服务。

定义5完全匹配服务：指一个服务的输入参数类型满足请求服务的所有输入参数类型，且服务的输出参数类型也满足请求服务的所有输出参数类型。同时，这个服务的输入参数和输出参数在取值上满足请求服务的约束。

定义6部分匹配服务：指一个服务的输入参数和输出参数在类型上分别部分匹配请求服务的输入参数和输出参数，且这些匹配的输入参数与输出参数在取值上也与请求服务的相应参数一致。

定义7约束不匹配服务：指一个服务的输入参数类型和输出参数类型都完全或部分出现在请求服务的输入参数和输出参数中，但是它们不都满足其对应的参数约束。

定义8完全不匹配服务：指不满足上述三类中任意一类的服务。

完全匹配服务和部分匹配服务归为第一级服务，用于后续的服务组合和选择技术，至于完全不匹配服务则直接舍弃。

2.2服务组合规划

规划服务组合分为3个阶段：

• 构造请求服务的功能划分图；

• 匹配、分类第一级服务，产生第一级服务类型；

• 装配第一级服务类型，产生抽象服务类型组合。

1) 构造功能划分图

将整个请求服务中的各个功能看作一个节点，先设定两个虚拟节点，即开始节点和终结节点，之后将这些节点初始化为一个有向图，这里称其为请求服务的功能划分图。

定义深度为功能划分图的最大路径长度，宽度为功能划分图中所有功能节点的最大直接后继服务节点数量。功能划分图的构造方法如下：

(1) 功能节点依照功能间的行为关系进行连接，若两个功能之间的行为关系是并行或不相邻的先后关系，则它们不需要连接；若它们的行为关系为顺序且相邻，则依照它们的先后顺序用有向边连接。

(2) 开始节点用有向边指向所有无前驱的节点，所有无后继节点指向终结节点。

2) 匹配、分类第一级服务

这一阶段的目的是搜索符合要求的第一级服务并将它们分类，由此产生各个第一级服务类型。为便于理解，对第一级服务类型作如下定义：

定义9第一级服务类型：第一级服务经第一级组合的分类阶段产生的抽象服务类型。

根据初始化后的功能划分图，标记图中的各分支和各抽象服务相对于各个分支所在的位置，并确定各分支间的隶属关系。之后，通过将各个服务与这个有向图对比来对服务进行分类。

已知第一级服务都能部分产生目标输出，且它们对应的节点之间有关联表示后者节点的输入依赖前者节点的输出，可得出以下推论：

推论1对于一个抽象服务功能，当其输入不能完全由一个第三方提供的服务决定时，则这个第三方提供的服务一定不包括这个抽象服务功能。

推论2一个无输入依赖的抽象服务功能，其前驱节点一定是开始节点。

推论3一个第三方提供的服务如果包含两个或多个在不同分支但它们的分支却隶属于同一分支A的抽象服务功能，记这两个或多个抽象服务功能所在的分支为B类分支，则这个第三方提供的服务必然包含分支A上的服务功能及其在B类分支上的直接后继抽象服务功能。

推论4一个第三方提供的服务所涉及到的抽象服务功能中，如果有其所在分支隶属于同一个分支的，则它们在请求服务功能划分图中的位置必是连续的。

将请求服务的功能划分图的开始节点留下，终结节点删去。根据上述4个推论可知，每个第一级服务类型对应到请求服务功能划分图中就是一个树，因此，每个第一级服务类型都可以由一个树结构来表示。

3) 第一级服务类型装配算法

第一级服务类型对应的装配算法简称第一级装配算法。其具体过程分为两阶段：分层阶段和装配阶段。

已知第一级服务类型的表示是一个树结构，本文根据各个第一级服务类型表示树的根节点来分层，即第一级服务类型所属的层数就是其表示树的根节点在请求服务功能划分图中的层数。

计算请求服务功能划分图中，求各个抽象服务节点的层数的方法如下：先求出请求服务功能划分图中从开始节点到终结节点的所有路径；接着，计算各个路径上的抽象服务在这个路径上的位置，设定开始节点的位置为0，其直接后继节点的位置为1，就这样依次加1得到各个路径上的各个抽象服务的位置；最后，对于每个抽象服务，取在经过自己的所有路径上的最大位置数作为自己的层数。

装配阶段就是依次对第0层的各个服务类型进行装配来得到它们的所有服务类型组合方式，进而得到请求服务所对应的所有服务类型组合方式，具体算法流程见图1所示。

图1　第一级装配算法流程图

(1) 初始化队列Queue：设Queue为一个先进先出队列，将属于0层的所有Web服务类型都封装为Web服务类型组合并依次放入Queue中。

(2) 装配一个缺少的服务类型：按层次数从小到大来找到服务类型组合A所需的第一个服务类型，并将这个服务类型装配到A上。

毛泽东作为一位出色的政治家诗人，其诗词作品始终洋溢着乐观的革命精神，饱含着深厚的人民情怀，蕴藏着巨大的精神力量。在他的众多诗词作品中，《菩萨蛮·大柏地》一词尤其引起笔者关注。一是因为这首词在一定的程度上反映了毛泽东领导工农红军开辟、创建和巩固中央红色政权的历史过程；二是因为笔者好奇，是什么样的力量能让毛泽东在逆境中始终昂扬着乐观豪迈的革命精神，从而抒写出恢弘大气的壮丽诗篇？古人云：诗言志。意谓诗词的创作是诗人理想抱负、感情意志的自然流露，最能反映诗人的内心世界。下面，笔者试着联系这首词背后的历史细节来探究毛泽东的革命情怀。

3　最优Web服务组合选择算法

Web服务组合选择阶段则是根据请求服务的服务质量、客户偏好等非功能属性，选择出最优的、真实的服务组合。文献[17] 提出了服务质量标准和相应的计算公式，探讨了对于确定的Web服务类型组合方式，求其最优服务组合解的方法。本文将Web服务组合的非功能属性分为完全依赖属性和部分依赖属性，用多领域决策来产生集成函数，通过集成函数的权值来表现请求服务的非功能性属性。最优Web服务组合选择算法就是选择出分数最高的服务组合的算法。

定义10完全依赖属性：由Web服务组合中的所有Web服务计算得到的属性，即服务组合在此属性上的值是所有Web服务在此属性上的值运算得到的。

定义11部分依赖属性：由Web服务组合中的部分Web服务计算得到的属性，即服务组合在此属性上的值是通过某种规则选出部分Web服务，由它们在这个属性上的值经过运算得到的。

从定义10和定义11可知，例如花费就是完全依赖属性，消耗的时间就为部分依赖属性。本文采用整数规划的思想，将所有非功能性属性的计算公式都转化为和的形式。这样，整个服务组合的分数就是整个服务组合在各个非功能属性项上的值乘以相应的权值之后将这些项进行累加。当Web服务或Web服务组合在这些属性上的值是相互独立时，对于完全依赖属性，其在整个Web服务组合上的值为这个Web服务组合所包含的所有Web服务在这个属性上的值的和；对于部分依赖属性，求解其在整个Web服务组合上的值实质上是一个关键路径问题，只不过具体问题依属性而不同。

由定义10、定义11知，完全依赖属性和部分依赖属性是没有逻辑联系的，而在部分依赖属性上选择出最优服务须得形成所有服务组合，这样问题就转换成图的最优路径选择问题。由文献[5]知，这是一个NP-hard问题，因此本文采取只根据完全依赖属性选择最优服务组合，在计算分数时会考虑整体的属性分数。

对于完全依赖属性，求解其在整个Web服务组合上的最优解问题实际上是个贪心问题，用贪心算法得到的最优完全依赖属性解在现实环境中并不保证一定能运行。另外，不是所有Web服务或服务组合在这些属性上的取值都是独立的，Web服务或服务组合间可能有优先条件，所以本文采用上下文来表示Web服务或服务组合在这些属性上的关联和它们自身对运行环境的要求。在3.1节和3.2节将介绍结合上下文来求解最优完全依赖属性服务组合的局部最优算法和全局最优算法。

3.1带约束上下文的局部最优选择算法

一般来说，一个Web服务的自身运行限制是与其前驱服务相关的，而其与其相邻服务的优先条件也可以表示为受其前驱服务的限制。因此，每个Web服务的约束上下文都可以表示为对其后继服务有限制。

带约束上下文的局部最优算法的实质就是逐层地找出满足上一层选出服务的约束条件的本层最优服务组合。考虑到会有没有后继服务的服务被选中而造成“无解”的情况，这里引入失败回退机制，具体算法过程如下：

2) 选择出满足前驱层的当前层最优服务组合，如果没有，则更新服务状态并回退至前驱层；如果存在则进入第3)步。

3) 判断当前层是否为最后一层，是则退出算法；否则设下一层为当前层，接着执行第2)步。

3.2带约束上下文的全局最优选择算法

带约束上下文的全局最优算法结合了动态规划思想和上述的局部最优算法，因此也带有失败回退的机制，具体算法过程如下：

1) 初始化：与局部最优算法的初始化过程一样。

2) 计算当前层的局部最优解。

3) 将上步得出的结果与第0层到当前层的前驱层筛选出的全局最优服务作对比，若完全一样则进入第4)步，否则进入第5)步。

4) 筛选出只在当前层上，比第2)步选出的当前层服务组合更优秀的服务组合，并依次找出包含这些服务组合的从0层到当前层的最优子结构；之后通过对比这些解找出0层到当前层的最优子结构，接着进入第6)步。

5) 找到开始出现变化的层数，更新服务状态，设开始出现变化的层为当前层，进入第2)步。

6) 判断当前层是否为最后一层，是则退出算法；否则记下一层为当前层，重新进入第2)步。

4　实验及性能分析

4.1实验环境

为验证上述算法的性能，本文进行了仿真实验。仿真实验采用的开发环境如下：操作系统为Windows7 32位操作系统，算法开发语言为C++，采用Microsoft Visual C++6.0为开发工具。用链表结构存储请求服务功能划分图，用树结构表示第一级服务类别，并为每个服务类别添加一个唯一的标识符。建立Composition类来模拟符合请求服务的单个服务组合，在Composition类中使用一个vector容器类型的成员变量来存储组成这个服务组合的所有服务类型的标识。

对第一级装配算法，分别采用单线程和多线程两种计算方式，以功能划分图的深度和宽度作为标量，以功能数、服务类型数、组合方式数、装配时间等作为服务类型装配算法的性能指标，进行了仿真试验。对选择算法，以最优服务组合的分数和花费时间作为服务组合选择算法的性能指标，进行了仿真实验。

4.2第一级服务类型装配算法性能分析

为验证第一级装配技术受请求服务功能划分图的影响，深度和宽度是反映请求服务功能划分图的复杂度的两个重要标量。表1给出了宽度为2时功能数、第一级服务类型数、组合方式数、装配时间等指标随深度的变化情况。从表1中可以看出，当深度从1增加到3时，第一级服务类型数量的变化比第一级服务类型组合方式数量的变化明显要大，采用多线程计算方式比单线程计算方式耗费的时间明显要少。

表1　深度对性能指标的影响(宽度为2)

表2给出了深度为2时功能数、第一级服务类型数、组合方式数、装配时间等指标随宽度的变化情况。从表2中可以看出，当宽度从1增加到3时，第一级服务类型数量的变化比第一级服务类型组合方式的数量变化要小，采用多线程计算方式比单线程计算方式耗费的时间要少，但差值不大。

表2　宽度对性能指标的的影响(深度为2)

对比表1和表2可以得出，服务类型数量更易受宽度的影响，而服务类型组合方式数量更易受深度的影响。另外，多线程计算方式更适合装配深度较大的请求服务。

图2是深度为1，宽度从1到10变化时，分别用单线程和多线程计算方式所得的处理时间对比图。从图2中可以看出，宽度达到一定值时，用多线程产生的开销已经远大于装配的开销，使得多线程计算方式在处理效果上还不如单线程。

图2　宽度对计算时间影响图

4.3局部最优和全局最优选择算法性能分析

这部分实验采用单线程、单机计算方式。为验证Web服务组合选择算法在约束上下文条件下的性能，实验用后继匹配率来表示满足服务约束的后继服务占有情况，即后继匹配率=满足服务的后继服务数量/后继服务的整体数量。设定整个服务组合的满分为100，选择算法负责选择分数最高的服务组合。由表1知，当请求服务功能划分图的深度(路径长度)为2(不包含初始节点)、宽度为2时，最大请求服务的功能数为6，服务类型数为28，服务类型组合方式数为32。图3给出了这种情况下后继匹配率为0.5，每种服务类型的候选服务数量取10～100间的10倍数离散点时，分别用局部最优选择算法和全局最优选择算法所得的服务组合的分数情况。图4给出了对应的局部最优选择算法和全局最优算法所花费的时间情况。从图3和图4可以看出，全局最优算法在效果上略优于局部最优算法，但是其花费的时间要比局部最优选择算法大得多，而且易受候选服务数量的影响。

图3　局部最优和全局最优选择算法的分数对比

图4　局部最优和全局最优选择算法的花费时间对比

5　结　语

本文通过构造请求服务的功能划分图，来计算用于Web服务组合的服务类型并规划出相应的服务类型组合方式。结合后退一步上下文算法以及动态规划思想，将非功能属性分类求解，并通过计算局部最优来缩小计算范围的方法，来简化局部最优和全局最优选择问题的复杂度。最后通过仿真实验，分析了功能划分图对第一级装配算法的影响，以及局部最优选择算法和全局最优选择算法的性能。

[1] 刘恒，张公让，吴曼.基于分布估计算法的Web服务组合优化[J].计算机技术与发展，2014，24(6)：10-14.

[2] PengWei Wang，ZhiJun Ding，ChangJun Jiang，et al.Constraint-Aware Approach to Web Service Composition[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems，2014，44(6)：770-784.

[3] Incheon Park，Wuhui Chen，Michael N.Huhns.A Scalable Architecture for Automatic Service Composition[J].IEEE Transactions on Services Computing，2014，7(1)：82-95.

[4] 赵明雪，赵文栋，彭来献，等.基于业务抽象规划的分布式动态服务组合算法[J].计算机工程，2014，40(4)：37-41,47.

[5] Liangzhao Zeng，Boualam Benatallah，Anne H H Ngu，et al.QoS-Aware Middleware for Web Services Composition[J].IEEE Transactions on Software Engineering，2004，30(5)：311-327.

[6] Dongnei Liu，Zhiqing Shao，Caizhu Yu，et al.A Heuristic QoS-Aware Service Selection Approach to Web Service Composition[C]//Eighth IEEE/ACIS International Conference on Computer and Information Science：IEEE Computer Society，2009:1184-1189.

[8] Shuiguang Deng，Longtao Huang，Wei Tan，et al.Top-k Automatic Service Composition:A Parallel Framework for Large-Scale Service Sets[J].IEEE Transactions on Automation Science and Engineering，2014，11(3)：891-905.

[9] Cristima Bianca Pop，Viorica Rozina Chifu，Ioan Salomie，et al.Ant-inspired Technique for Automatic Web Service Composition and Selection[C]//2011 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2010)：IEEE Computer Society ，2010:449-455.

[10] 赵文栋，田畅，彭来献.CBSD：一种基于Chord的模糊服务发现方法[J].计算机科学，2014，41(1)：172-177.

[11] 贺兴亚，王海艳.基于Petri网的组件服务发现方法[J].计算机技术与发展，2014，24(7)：136-140.

[12] Jinjun Cheng，Cong Liu，MengChu Zhou，et al.Automatic Composition of Semantic Web Services Based on Fuzzy Predicate Petri Nets[J].Automation Science and Engineering，2015，12(2)：680-689.

[13] Yang Jie，Zhou Xianzhong，Wang Jiacun，et al.A Novel Method for Web Service Composition Based on Extended BDI[C]//2014 IEEE 11th International Conference on Networking,Sensing and Control，2014：310-315.

[14] Xuanzhe Liu，Gang Huang，Junfeng Zhao，et al.Data-Driven Composition for Service-Oriented Situational Web Applications[J].IEEE Transactions on Services Computing，2014，8(1)：2-16.[15] Hong Qing Yu，Stephan Reiff-Marganiec.A Backwards Composition Context Based Service Selection Approach for Service Composition[C]//2009 IEEE International Conference on Services Computing (SCC)：IEEE Computer Society，2009:419-426.

[16] Rajesh Karunamurthy，FerhatKhendek，Roch H Glitho.A Novel Architecture for Web Service Composition[J].Journal of Network and Computer Applications，2012，35(2)：787-802.

[17] Rajeswari M，Sambasivam G，Balaji N，et al.Appraisal and Analysis on Various Web Service Composition Approaches Based on QoS Factors[J].Journal of King Saud University-Computer and Information Sciences，2014，26(1)：143-152.

WEB SERVICE COMPOSITION PLANNING AND OPTIMAL SELECTION BASED ON FUNCTION PARTITION MAP

Wu FangZhu Shangming*

(Department of Computer Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

To expand the composition mode of Web service types,implement seamless Web service composition and improve the reliability of service composition are the focuses of current Web service composition research.Considering the diversity of Web service composition modes and the seamless service composition issue,we calculate the candidate service types applicable to the service composition based on the function partition map of service,dynamically plan the composition mode of various service types,and propose an assembly algorithm of the first stage service type.Aiming at the reliability issue of service composition,we express the operating environment required by Web service itself and the preferential conditions of its own as the context,and propose the correlated local optimum and global optimum selection algorithms to find the real service composition with high reliability.Finally,we verify the performances of the assembly algorithm of first stage service type,the local optimum and the global optimum selection algorithms through simulation experiments.

Web service compositionFunction partition mapAssembly algorithm of first stage service typeLocal optimum selection algorithmGlobal optimum selection algorithm

2015-05-22。计算机与法律复合应用型人才培养基础案例库建设项目(A-3101-14-17-172103)。吴芳，硕士生，主研领域：计算机网络与应用。朱尚明，教授。

TP393

A

10.3969/j.issn.1000-386x.2016.09.003