浅谈Web服务组合

　　Web服务（Web Service）是基于XML和HTTPS的一种服务，其通信协议主要基于SOAP，服务的描述通过WSDL，通过UDDI来发现和获得服务的元数据。

近年来，基于XML的Web服务技术迅速发展，为互联网应用提供了一种共享数据的有效手段。Web服务的高效执行方式，Web服务与其他成熟技术的有机结合以及Web服务的组合是解决现实应用问题的重要技术。

Web服务是一种自包含、自描述、模块化的程序，它吸收了分布式计算、Grid计算和XML等各种技术的优点，解决了异构分布式计算以及代码与数据重用等问题，具有高度的互操作性、跨平台性和松耦合性，引起了世界范围内学术界和工业界的极大兴趣[1-2]。

Web service平台需要一套协议来实现分布式应用程序的创建。任何平台都有它的数据表示方法和类型系统。要实现互操作性，Web service平台必须提供一套标准的类型系统，用于沟通不同平台、编程语言和组件模型中的不同类型系统。在传统的分布式系统中，基于界面(interface)的平台提供了一些方法来描述界面、方法和参数（译注：如COM和COBAR中的IDL语言）。同样的，Web service平台也必须提供一种标准来描述Web service，让客户可以得到足够的信息来调用这个Web service。，我们还必须有一种方法来对这个Web service进行远程调用。这种方法实际是一种远程过程调用协议(RPC)。为了达到互操作性，这种RPC协议还必须与平台和编程语言无关。下面几个小节就简要介绍了组成Web service平台的这三个技术。

Web服务所执行的功能可以是从简单的请求到复杂的商业过程中的任何事，然而单个Web服务的功能有限，难以满足实际应用中的多种多样的需求，因此，为了更加充分地利用共享的Web服务，有必要将共享的Web服务组合起来，提供功能更为强大的服务。Web服务组合是个非常复杂的问题[4-7]，它涉及到Web服务的描述、Web服务的发现[8]、Web服务的选择[9]、Web服务的匹配、Web服务的调度[10-11]、服务质量(QoS)[12-13]等一系列问题。

　1 基于图的Web服务组合模型

Web 服务是一种新的重要的应用程序。Web 服务是一段可以用 XML 发现、描述和访问的代码。在这一领域有许多活动，但有三种主要的用于 Web 服务的 XML 标准：

SOAP：初是简单对象访问协议（Simple Object Access Protocol），SOAP 定义一个 XML 文档格式，该格式描述如何调用一段远程代码的方法。我的应用程序创建一个描述我希望调用的方法的 XML 文档，并传递给它所有必需的参数，然后应用程序通过网络将该 XML 文档发送给那段代码。代码接收 XML 文档、解释它、调用我请求的方法，然后发回一个描述结果的 XML 文档。SOAP 规范版本 1.1 位于 w3.org/TR/SOAP/。请访问 w3.org/TR/ 以了解 W3C 中 SOAP 相关的所有活动。

WSDL：Web 服务描述语言（Web Services Description Language）是一个描述 Web 服务的 XML 词汇表。编写一段接收 WSDL 文档然后调用其以前从未用过的 Web 服务的代码，这是可能的。WSDL 文件中的信息定义 Web 服务的名称、它的方法的名称、这些方法的参数和其它详细信息。您可以在 w3.org/TR/wsdl（结尾没有斜杠符号）找到的 WSDL 规范。

UDDI：统一描述、发现和集成（Universal Description, Discovery, and Integration）协议向 Web 服务注册中心定义 SOAP 接口。如果您有一段代码希望作为 Web 服务部署，UDDI 规范定义如何将您的服务描述添加至注册中心。如果您在寻找一段提供某种功能的代码，UDDI 规范定义如何查询注册中心以找到您想要的信息。有关 UDDI 的所有资料来源都可以在 uddi.org 找到。

组合服务是通过一系列数据流和控制流联系在一起的基本服务，研究Web服务组合问题，也就是研究如何找到一组需要调用的Web服务，以及以何种方式进行调用这些Web服务。图论中的点可以代表基本服务，边可以代表Web服务的调用，再把QoS属性参数[12-13]也加入图中，这样就可以用1个带有权值的有向图来表示服务的组合问题，可以根据图论中的算法和服务的属性参数，在图中寻找的服务组合方案。

把组合Web服务问题看成在1个带有权值的有向图G=(V，E)中寻找路径的问题，其中V代表Web上服务的集合，E代表Web上两个服务之间的连接的集合。另外定义n为图中节点的数量，e代表图中边的数量，也就是n=|V|，e=|E|。

每个Web服务被表示为图中的一个节点(node)，Web服务的QoS参数(如响应时间、费用、可靠性、可用性等)可表示为节点的权值。然而有关图的算法通常把权值定义在边上，而不是在节点上，所以本研究把原来在节点上属性的权值(响应时间T，费用C，可靠性R，可用性A等)转移到边上。

基于图的Web服务组合模型构造如下：

(1)图中的每一个节点代表一个Web服务。

(2)在图开始处加一个开始节点，在结束时加一个结束节点。

(3)同一列的节点代表是同一个服务社区的服务。

(4)图中边代表该边的前驱节点所代表的Web服务可以调用该边后继节点所代表的Web服务。

(5)边上的权值代表该边后继节点所代表的Web服务的QoS的综合参数。

构造的Web服务组合模型图，它有4个服务社区：第1个服务社区有4个候选服务，第2个服务社区有2个候选服务，第3个服务社区有4个候选服务，第四个服务社区有3个候选服务，边上的值是边后继节点所代表服务的QoS的综合参数。

符号的含义：

(1)Si：代表一个服务社区，它是一个自治的系统，包含着多个功能相同或相似但非功能(例如价格、响应时间等)不同的的单个Web服务。

(2)Sij：是一个基本Web服务，它在Web服务社区Si中，其中j是社区为了标识Web服务的标记。

(3)S：起始节点，代表组合服务的开始。

(4)D：目标节点，代表组合服务的结束。

　2 基于图的Web服务组合算法

要从图中找出S到D的路径，并能够同时满足多种QoS约束的可行路径。本文主要考虑多重(k≥2)路径约束(也称为多约束)的情况。由于多约束的QoS是NP完全问题，为此，研究人员设计了很多启发式算法。然而这些算法往往具有很大的局限性：(1)计算复杂度过高，无法应用到实际环境中；(2)算法性能较差，不能找到实际存在的可行路径；(3)算法只是针对某些特殊情况而设计，不具有普遍性。

本文则将多种QoS度量转化为单一的权值，然后用几种算法对整个图进行计算短路径。使用加权公平队列，费用、响应时间、可用性和可靠性都可以转化为函数中的参数，不再彼此独立。这样，原来多约束的NP完全问题就可以简化为多项式的复杂度。

在此介绍几种算法求解满足约束条件的方案。

(1)扩散法。该算法可以找出所有可能执行组合的路径，其思想是从源点开始，通过逐个询问图中的其他节点，逐步逼近并达到目标节点。首先使用广度优先的方法，在多条路径中寻找可行路径，在询问抵达目标节点之前，不能断定可行路径。为了避免回路和扩散重复信息，节点需要记录大量探测数据。

扩散算法在节点比较少的情况下可以用来寻找满足约束条件的解决方案，但当节点较多时，它的时间复杂度会呈指数级上升，所以在大规模问题时不为人们所接受。

(2)Dijkstra算法。在经典的图论问题中，可以使用Dijkstra算法计算图中任意2个节点的短路径[4]。本研究把该算法的思想应用在服务组合过程中，求解从S到D的路径，并且使服务质量函数。具体求解步骤如下：

①首先进行初始化，用d[v]表示从服务开始到调用到服务v的质量函数值，由于刚开始，所以除了服务开始节点s外，所有的节点d[v]都设为无穷大，d[s]=0；p[v]表示调用服务v节点的服务节点，开始时都没有调用，所以p[v]都设置为未定义。

②设置1个集合S，表示已经找到的符合要求的服务节点，一开始设置为空集合；设置1个集合Q，表示所有的服务节点，当算法找到1个符合要求的节点时，则把该节点从Q中删除，加入到S集合中。

③当集合Q不空时，从集合中找出参数的服务节点u，并且把它加到集合S中，对于每个u服务可以调用的服务，如果d[v]大于d[u]与w[u，v]的总和，则把d[u]与w[u，v]的总和赋值给d[v]，同时把p[v]设置为u。

④回到步骤3，直到Q集合为空时，算法结束。

具体算法，在这个算法中，边上的权值不能是负值，如果存在负值的话，在选取值时，就会出错。

Dijkstra算法从图中节点入手进行寻找解决方案，另外还可以从图中的边入手开始寻找。

(3)Bellman-Ford算法。是求解单源点的短路径问题的一种算法。单源点的短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的短路径。

Bellman-Ford算法如图3所示，它和Dijkstra算法很相似，但Dijkstra算法中的权值不能为负，因为如果有负值，则出现负循环时，就找不到路径，Bellman-Ford算法比它多了检查的步骤(行10－12)，这样如果权值为负值，会返回错误。Bellman-Ford算法可以在伪多项式时间内完成。

Web服务能够较好地解决异构应用之间、松散耦合环境下的互操作、集成和协作问题，成为国内外软件技术研究的重要方向。Web服务的组合是正在兴起的新技术，它将彻底改变提供电子商务和客户软件应用的方式，是国内外在信息集成、软件工程等领域的关注的焦点，也是Web服务技术的主要发展方向之一。

本文主要关注Web服务的组合，将QoS参数属性作为图的权值，提出了基于图的Web服务组合建模，使用扩散算法、Dijkstra算法、Bellman-Ford等算法在模型中寻找组合的路径，并将各个算法进行比较，为Web服务的组合做好了理论准备。

Web服务是处在动态的互联网上，在过去几年里Web上提供的Web服务数量急剧增多，通过人工在巨大的Web服务仓库中发现人们需要的服务是不现实的，所以服务的自动发现是服务调度的前提，我们会继续对服务的自动发现、服务的组合模型、服务的自动组合做进一步研究。