电子材料张治宾7

1、毕业设计（）性本人郑重：所提交的毕业设计（），是本人在导师指导下，独立进行研究工作所取得的成果。除文中已注明的内容外，本毕业设计（论文）不包含任何其他个人或集体已经或撰写过的成果。对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。作者签名：日期：年月日摘要近年来 Web 服务的理论和技术取得了长足的发展，其保证互操作性的协议栈下层在学术界和工业界已基本达成一致。Web 服务的价值在于服务重用，新兴的 Web 服务组合正是主要的重用。然而基于流程的 Web 服务组合建模是一个复杂且易出错的过程。如果流程定义在投入运行之后被发现有错，则修复错误的代价相当高。因此，在建模阶段

2、进行有效的过程验证时十分必要的。此外 Web 服务组合可能存在不必要的流程设计而影响执行效率。本课题分析了基于 Petri 网建模的优势，给出基于 Petri 网的 Web 服务的形式化定义和描述，对 Web 服务组合进行建模及元素，给出 Petri 网模型生成算法并对组合服务模型的可达性、安全性、有界性与活性等特性进行验证分析。从而达到对基于 Petri 网的 Web 服务组合的验证。：Web 服务；Petri 网；服务组合；服务组合验证ABSTRACTWeb Services offer a new paradigm for distributed computing on the Wor

3、ld Wide Web. Web services composition allows us to combine a number of existing Web services into a new, value-added Web service. Mission critical Web services have little tolerance for run time errors, as repairing them at service operation time is usually costly. The development of such Web servic

4、es requires thorough verification at the design stage in order to detect and correct errors as early as possible. Moreover, lots of web services compositions may have redundant flow design which can lead to lowperformance. Then reduction is needed.The advantages were discussed for ming web services

5、composition usingPetri net in this thesis. Based on Petri net theory, the formal definition and graphic description were proposed for web services and their composition; the elementmapping process was also illustrated. Then an algorithm was proposed to constructthe Petri net mfor web services compos

6、ition. The reachability, safeness,boundness and liveness of the mwere also validated. To achieve the verificationof web service composition based on Petri net.Key words: Web services; Petri net; Services composition; Services compositionverification目录第一章1.4绪论1研究背景研究目的研究现状结构安排. 1. 3. 4. 4第二章

7、 相关技术探究52.1 Web 服务概述52.1.1 Web 服务的定义52.1.2 Web 服务的特点52.1.3 Web 服务的结构模型62.1.4 Web 服务标准和协议栈62.1.5 Web 服务的应用领域82.2 Web 服务组合82.2.1 Web 服务组合的定义82.2.2 基于 BPEL4WS 的 Web 服务组合92.3 Petri 网9第三章 基于Petri 网的 Web 服务组合113.1 基于 Petri 网的Web 服务定义113.2 Web 服务组合的代数描述123.3 Petri 网模型生成算法143.4 应用 Petri 网验证Web 服务组合15第四章基于Pe

8、tri 网的 Web 服务组合的实例分析184.1 Cygwin184.1.1 Cygwin 概述184.1.2 Cygwin 组成和工作机制184.1.3 Cygwin 安装与配置194.2 BPEL2oWFN214.2.1 BPEL2oWFN 的介绍214.2.2 BPEL2oWFN 在 Cygwin 平台上的编译234.2.3 BPEL2oWFN 在 Cygwin 平台上的安装244.3 LOLA254.3.1 LOLA 的介绍254.3.2 LOLA 在 Cygwin 平台上的编译254.3.3 LOLA 在 Cygwin 平台上的安装264.4 对实际的 Web 服务组合进行结构验证

9、27结束语33致谢34参考文献35第一章绪论1.1 研究背景Web 服务作为一种新型的分布式构件模型已经在电子商务、企业应用集成等，特别是 Web 服务的组合技术，因其能实现服务领域扮演着越来越重要的的重用和增值而成为学术界和工业界关注的焦点。服务组合是将服务看成构件而进行重用的技术，能在现有的服务中选取特定的服务，组新的服务来满足用户的需求。近年来 Web 服务的理论和技术取得了长足的发展，其保证互操作性的协议栈下层在学术界和工业界已基本达成一致。然而 Web 服务的价值在于服务重用，新兴的 Web 服务组合正是主要的重用。Web 服务技术遵循面向服务架构(SOA：Service-Orien

10、ted Architecture)将网络上的成员划分为 Web 服务的需求者、提供者和中介者三种于 XML 的标准协议达成异构平台间的整合：利用简单对象。并且以各项基协议(SOAP)执行、发布和服务，以 Web 服务描述语言(WSDL)描述服务的应用程序接口，并且通过统一描述发现与整合规范(UDDI)为服务需求者和提供者提供制。近年来，通过许多现存 Web 服务的协同组合产生一个新的 Web 服务以达成机特定目的的行为被称之为 Web 服务组合，产生的组合服务也可以作为其它组合服务的一个基础服务。通过 Web 服务组合可以实现出具备功能更有价值的企业流程，通过基础 Web 服务的组合可以创造出

11、更有价值的企业应用服务。许多的企业组织也将它们的服务包装成 Web 服务的形式放在网络上供服务需求者使用，例的搜寻服务、Amazon 的书籍服务等。如此通企业组织将各过面向服务架构中介机制的透明化特性，Web 服务组合便可以个不同企业所提供的 Web 服务加以组合创造出新的增值性 Web 服务。从 Web 服务组合使用者的观点来看，Web 服务组合的需求规范可以划分为面向过程的规范(POS；Process Oriented Specification)和面向接口的规范(IOS； Interface Oriented Specification)两种。POS 规范包含许多抽象化的 Web 服务组

12、件(以服务的功能为基础并不需要实际指定由那一个服务负责执行)配合企业应用逻辑以工作流程的概念描述这些 Web 服务间的协同关系；IOS 规范只需要 Web服务组合使用者所需求的 Web 服务组合提供输入和输出的信息，至于 Web服务组合中要包含那些基于 Petri 网的 Web 服务组合的验证与化简 Web 服务组件，要以什么样的结构组合这些服务，使用者并不需要知道。这两种 Web 服务组合需求规范必须以不同的方法来达成，采用 POS 规范的Web 服务组合最好是由企业逻辑模型配合工作流程的来实现 Web 服务的组合协同；而采用 IOS 规范的 Web 服务组合则需通过自动化程序组合方法的使用

13、来达成 Web 服务的组合协同。就 Web 服务组合发展来看，采用 POS 规范也就是利用工作流程的概念来Web 服务的组合协同仍然是目前最通用的方法，许多的 Web 服务汇编语言例如 BPEL4WS、WSFL、WSCL、XLANG、BPML、BPSS、WSCI、Wf-XML、JDF、PIPs 等也都采用工作流程的概念作为协同 Web 服务组合的方法。然而目前的 Web 服务组合仍存在着许多问题有待解决，主要包括以下几点：lWeb 服务组合的开发问题以工作流程为基础的 Web 服务组合开发和管理需要具备特定的知识且耗费大量的程序撰写时间。目前虽然有许多的 Web 服务汇编语言但是在开发上仍然需

14、要以编辑文件的方式来开发 Web 服务组合，然而这是非常费时且没有效率的。因此许多的研究都发展出 Web 服务组合的开发平台来方便组合服务开发者的开发工作，例如：Self-Serv、eFlow、FUSION、SCET 等。lWeb 服务组合的挑选问题由于在 Web 服务的架构下，通过 UDDI 中介机制每个服务提供者都可以将服务到中介者上，因此在进行 Web 服务组合时，对于同样的工作任务可能有许多的 Web 服务都可以达成，也因此产生 Web 服务在挑选上的问题。而对Web 服务组合而言，就不单单只是单一 Web 服务的挑选问题，因为随着参与组合的 Web 服务数量的增加，出现的排列组合可行

15、方案就会以倍数成长。这样的问题，许多研究从 Web 服务的质量上着手，所谓的 Web 服务质量指的是Web 服务的执行时间、可靠度、价格等非功能特性，通过这些非功能特性的评估， 让开发者有选择的依据。lWeb 服务的组合能力问题Web 服务要彼此组合必须输出结果与输入参数的数据类型能够互相配合，并且数据的意义要相同，否则 Web 服务组合执行的结果将是不正确的，而这样的特性被称之为 Web 服务的组合能力。目前有许多的研究采用 DAML-S 配合本体知识的方式定义 Web 服务输入参数及输出结果的语意描述，在组合时便通过语意描述的比对来Web 服务的组合能力。lWeb 服务组合的验证问题无论

16、Web 服务组合的开发者是通过组合平台的设计或是程序撰写的方式来开发 Web 服务组合，在设计 Web 服务组合的流程时都有可能发生流程设计上的问题例如：死锁、不可达性等这些问题不容易在 Web 服务组合的设计阶段看出，而要等到 Web 服务组合实际执行时这些问题才会发生，但这时很可能已经产生无法弥补的错误。因此在 Web 服务组合实际执行前必须Web 服务组合的流程设计进行验证的工作。然而目前尚未有研究提及 Web 服务组合的验证应该包含那些步骤做哪些事。大部分的相关研究仅止于对 Web 服务组合进行建模而已，至于建模完成后要如何验证，以及其验证的标准要如何制定都尚未提及。因此本课题将上述

17、Web 服务组合验证的相关问题进行探讨并提出具体的方法。目前 Web 服务及其组合的形式化描述和验证是语义 Web 服务中一个重要的研究方向，现有的许多 Web 服务及其组合描述语言都是半形式化的，容易出错和不容易检测，正确性难以保证。模型的正确性是指模型结构上的正确性，即是安全、有界、无死锁等。Petri 网作为一种基于状态的形式化建模方法，具有直观、形象且有严格语义和数学分析之优点，是数据和流的抽象和形式化建模方法。Petri 网理论作为组合 Web 服务的一个主要机制，可以用来快速组合创建功能更强大的 Web 服务。1.2 研究目的本课题理解 Petri 网相关知识及其在 Web 服务组

18、合中应用，分析基于 Petri网的 Web 服务组合方法，并对其进行验证。根据以上的出现的问题探讨可以发现，Web 服务组合在实际执行前若过验证将可能发生死锁、不可达性、不能满足安全性等问题，这些流程设计问题必须通过建模工具的模拟分析，否则将难以在 Web 服务组合的设计阶段察觉。并且 Web 服务组合开发者的 Web 服务组合流程设计可能过于繁杂而不够简单明了，造成 Web 服务组合的执行效率低落。为解决以上的问题，本课题提出一个基于 Petri-Net 的 Web 服务组合验证及简化方法，以达成以下两项目的：l确保 Web 服务组合流程设计的正确性为避免 Web 服务组合实际执行时才发生

19、Web 服务互相等待输入消息产生死锁等的问题造成 Web 服务组合使用客户的不满和降低 Web 服务组合提供者的声誉，本课题提出一个 Web 服务组合的验证方法，以 Petri-Net 模型化Web 基于Petri 网的 Web 服务组合的验证与化简服务组合开发者设计的 Web 服务组合流程，通过 Petri-Net 的流程状态模拟分析能力，预先发现由于 Web 服务组合的错误设计所造成的死锁、不可达性、非安全性等问题，以确保 Web 服务组合流程设计的正确性。lWeb 服务组合的执行效率本课题将七个流程简化规则应用在 Web 服务组合的简化上，这些简化规则可以在不影响 Web 服务组合原有功

20、能的前提下，转换 Web 服务组合流程中过于繁杂且不必要的流程设计。通过 Web 服务组合流程的简化将可以减少由于繁杂的流程设计所造成的时间浪费达到提升 Web 服务组合执行效率的效果。此外，为实践基于 Petri-Net 的 Web 服务组合验证及简化方法，本课题提出一个Web 服务组合验证及简化实现架构。通过Web 服务汇编语言PNML(Petri-Net Markup Language)的转换完成 Web 服务组合的 Petri-Net 建模，并利用覆盖树、关联矩阵等常见的 Petri-Net 分析方法验证死锁、可达性和安全性等性质，最后以流程简化规则配合 Web 服务组合代数方法的运用

21、完成 Web 服务组合流程简化的工作，达到高效的验证效果。1.3 研究现状Web 服务是语义网的一个关键应用研究领域，Web 服务的激增和语义网技术的发展，为多样的 Web 服务组合提供了便利。语义网技术提供了计算机可判断的 Web 内容和性能标记，推动了服务的自动发现和服务组合。目前 Web 服务及其组合的形式化描述和验证是语义 Web 服务中一个重要的研究方向，现有的许多 Web 服务及其组合描述语言都是半形式化的，容易出错和不容易检测，正确性难以保证，需要有形式化的方法来验证 Web 服务组合模型。模型的正确性是指模型结构上的正确性，即是安全、有界、无死锁等。Petri 网作为一种基于状

22、态的形式化建模方法，具有直观、形象且有严格语义和数学分析之优点，是数据和流的抽象和形式化建模方法。本文采用 Petri 网对 Web 服务组合进行正确性验证。1.4 结构安排第一章、绪论 绪论部份描述本课题的研究背景、研究目的和本文的工作，并且说明本的结构安排。第二章、相关技术探讨本章为相关技术的概述 主要目的是课题所做工作提供相关的基础知识。第一节概述 Web 服务，包括 Web 服务的定义、Web 服务的特点、Web 服务的结构模式、Web 服务的标准和协议栈及 Web 服务的目前应用领域。第二节 Web 服务组合，主要是对 Web 服务组合的定义进行说明， 特别介绍了基于 BPEL4WS

23、 的 Web 服务组合。第三节着重阐述了 Petri 的相关理论。第三章、基于 Petri-Net 的 Web 服务组合 本章描述本课题所提出的基于Petri-Net 的 Web 服务组合验证。共分为四个小节，第一节说明 Web 服务组合的定义。第二小节用代数描述了 Web 服务组合。第三小节阐述了 Petri 网模型生成算法。最后一节重要介绍应用 Petri 网验证 Web 服务组合，如分析 Petri 网可采用可达树法、不变量分析、约简等方法。第四章、基于 Petri 网的 Web 服务组合的实例分析 本章阐述基于 Petri-Net 的 Web 服务组合验证的实例分析，以实现第三章提出的

24、 Web 服务组合验证概念。本章共分为四个小节，首先阐述本次课题实现基于的平台，即 Cygwin 平台，包括它的一些概述，它的组成与工作机制以及最重要的安装与环境的配置。第二、三部分描本课题实现的两个很重要的工具，BPEL2WFN 和 LOLA，用两小节分别对它们进行了介绍以及在 Cygwin 平台上的编译与安装、调试。第四部分详细描述对一个实际的 Web 服务组合进行结构验证。第二章相关技术探究2.1 Web 服务概述2.1.1 Web 服务的定义随着技术的进步，Web 的从信息的容器逐渐发展成为提供 Web 服务的载体，Web 服务建立在面向服务的体系结构(Service-Oriented

25、 Architecture，SOA) 基础之上。SOA 为最新的分布式计算技术，可以将软件组件(包括来自不同系统的程序函数、对象和进程)发布为服务。根据万维网(World Wide Web Consortium，W3C)的定义，一个 Web 服务是指通过统一标志符(Universal Resource Identifier，URI)标志的一个软件系统，其公共接口和绑定方式是通过可扩展标记语言（eXtensible Markup Language， XML）来定义和描述的。其他软件系统可以发现 Web 服务的定义，然后可以按照定义所规定的方式与这个Web 服务进行交互。这种交互使用基于XML 的

26、消息，通过网络传输协议来进行。2.1.2 Web 服务的特点从外部的使用者的角度而言，Web 服务是一种部署在 Web 服务器上的对象或组件，它具备以下特征：封装性：Web 服务是一种部署在 Web 上的对象，自然具备对象的良好封装性，对于使用者而言，他能且仅能看到该对象提供的功能列表。互操作性：任何 Web Service服务通过 SOAP 实现相互间的都可以与其它 Web Service 进行交互，Web，这样就避免了在 CORBA，DCOM 和其它协议等等不同协议之间转换的麻烦。还因为可以使用任何语言来编写 Web 服务， 开发者无需更改他们的开发环境就可生产和使用 Web 服务，同时还

27、可以在新的Web 服务中使用己有的 Web 服务而不必考虑 Web 服务的实现语言，运行环境等具体实现细节。普遍性：Web 服务使用 HTTP 和 XML 进行通信。因此，任何支持这些技术的设备都可以拥有和生活的各个领域。Web 服务。相信在未来，Web 服务将普遍应用于易实现性：Web Service 背后的概念易于理解，并且来自微软和 SUN 等这样工具箱能够让开发者快速创建和部署的 Web 服务。的供应商的松散耦合：这一特性源于对象/组件技术，当一个 Web 服务的实现发生变更的时候，调用者将 受到任何影响。对于调用者来说，只要 Web 服务的调用界面不变，Web Service 实现的

28、任何变更对他们来说都是透明的，甚至是当 WebService 的实现平台从 J2EE 迁移到了.NET 或者是相反的迁移流程，用户都可以对此一无所知。标准性：使用开放的标准协议进行描述、传输和交换。这些标准协议具有完全的规范，以便由任意方进行实现。一般而言，绝大多数规范将最终由 W3C 或 OASIS(Organization for the Advancement of Structured Information Standards，结构化标准信息推进组织)等权威组织作为最终版本的发布方和维护方。2.1.3 Web 服务的结构模型Web 服务本身是跨平台的、的、模块化的应用，能够通过网络，

29、特别是WWW 来描述、发布、服务体系结构基于三种以及调用。根据 W3C 的标准提议，一个典型的 Web(服务提供者、服务发现和服务请求者)之间的交互。交互涉及发布、查找和绑定操作。这些件。和操作一起作用于 Web 服务构服务提供者定义 Web 服务的服务描述并把它发布到服务请求者或服务中心。服务请求者使用查找操作来从本地或服务发现检索服务描述，然后使用服务描述与服务提供者进行绑定并调用 Web 服务实现或同它交互。服务提供者和服务请求者是逻辑结构，因而服务可以表现两种特性。图 2.1 表示了这些操作、提供这些操作的组件及它们之间的交互。查找绑定图 2.1 Web 服务体系构架模型2.1.4 W

30、eb 服务标准和协议栈要以一种可互操作的方式执行发布、发现和绑定这三个操作，必须有一个包含每一层标准的 Web 服务协议栈作为 Web 服务标准化组织，W3C Web 服务体系架构工作组(W3C Web Services Architecture Working Group)在概念层面上提出了一组 Web 服务的协议栈，图 2.2 展示了这个 Web 服务协议栈。对各层稍作粗略的解释如下：Web 服务提供者Web 服务请求者Web 服务图 2.2 Web 服务体系结构协议栈服务发现和集成与 UDDI 服务发现与集成的目标是根据请求者的要求发现合适的 Web 服务，并将该 Web 服务的服务描述

31、返回给请求者，然后请求者可能将该服务动态集成到应用中。该层可使用的模式有多种。UDDI 作为广泛使用的规范是其中的一种。UDDI(Universal Description， Discovery and Integration，通用描述、发现和集成)是基于 XML 的规范。它是为使软件能够在网络自动发现服务并通过提供必要的转换自动同服务集成在一起而设计的。UDDI 报文附加在SOAP 协议之上，SOAP 负责调用网上的服务。Web 服务描述层与 WSDL 服务描述层的目标是帮助 Web 服务描述其功能。在这层上 WSDL( Web Services Description Language，W

32、eb 服务描述语言)作为W3C 推荐的服务描述语言得到广泛的应用，也使事实上的工业标准。WSDL 用来描述网络服务或终端(endpoint)的一种 XML 语言，它用于定义 Web 服务：以及如何调用它们(描述 Web 服务的属性，例如它做什么，它位于哪里和怎样调用它)。消息层与 SOAP 消息层的作用是将 Web 服务消息于特定的传输协议。作为 W3C 唯一推荐的消息层协议，也是事实上的工业标注，SOAP(Simple ObjectAccess Protocol，简单对象协议)是一个基于 XML 的报文协议，用于网上的服务。SOAP 可以运行在任何其它传输协议上。比如可以使用 HTTP，SM

33、TP， JMS 等协议来传递 SOAP 消息。各种传输层之间基于 Petri 网的 Web 服务组合的验证与化简的报头是不同的，但 XML 有效负载保持相同。SOAP 用 XML 将消息编码，因此在调用过程的任何一步都很容易地处理消息。另外，调试 SOAP消息的方便性使各种 SOAP 执行能快速聚合在一起，达到大范围的协同工作。最SOAP 的扩展使 Web 服务获得后各种的特性，比如安全性等等。XML(eXtensible Markup Language，可扩展标记语言)是 Internet 上数据表示的一种标准。它是一种元语言，可以用来定义和描述结构化数据，它和是 Web 服务得以实现的语言

34、基础。Web 服务的其它协议规范都是以 XMI 的形式来描述和表达的。在 Web 服务技术中，SOAP 消息作为各种传输协议的有效载荷，被用来发送与接受。迄今为止，在 Web 服务中使用的最广泛的传输协议协议是 HTTP，当然也可以使用其它传输层协议，如 FTP、SMTP 等。2.1.5 Web 服务的应用领域Web 服务基本上覆盖了传统分布计算技术的应用领域。作为目前最典型的异构分布技术，Web 服务在应用程序跨平台和跨网络进行通信的时候是非常有用的。Web 服务适用于应用程序集成、B2B 集成、代码和数据重用，以及通过 Web 进行客户端和服务器的通信的场合。下面是几个 Web 服务主要的

35、应用领域：(1)始就是的通信。与 COM，CORBA 等集成技术不同，Web 服务一开Internet 的集成。他们采用 XML 的一系列标准，并且能够以 HTTP作为传输层协议，这让它获得了穿越的能力。(2)应用系统集成。通过 Web 服务，应用程序可以用标准的方法把功能和数出来，供其它的应用程序使用。用 Web 服务来实现集成的最大好处在于据可以轻易实现互操作性。只要的商务逻辑出来，成为 Web 服务，你就可以让任何指定的合作伙伴轻松的调用你的商务逻辑，而不管他们的系统在什么平台上运行，使用的是什么开发语言。这样就大大减少了花在集成的上的时间和成本。(3)软件重用。目前，软件重用有一个严重

36、的限制，即重用仅限于代码，而数据不能被重用。因为可以很轻易的发布组件甚至源代码，但要发布数据就没那么容易了，除非那些数据都是经常变化的静态数据。而 Web 服务则在重用代码的同时，重用代码后面的数据。2.2Web 服务组合2.2.1 Web 服务组合的定义随着 Web 服务技术的日益成熟，越来越多的稳定易用 Web 服务共享在网络上。但单个的 Web 服务能够提供的功能有限，为了更加充分地利用共享的 Web 服务，有必要将共享的 Web 服务组合起来，提供更为强大的服务功能，加快系统开发的速度，快速满足用户需求。Web 服务组合方法从组合方案生成方式来分有两大类:静态组合和动态组合。静态组合意

37、味着请求者应在组合计划实施前创建一个抽象的过程模型。抽象的过程模型包括任务的集合以及任务间的数据依赖关系，每个任务包含一个的子句，用来查找完成任务的真正的 Web 服务。因此这里的自动仅指 Web 服务的选择和绑定是由程序自动完成的。静态组合中最常用的是用图来描述过程模型。而动态组合不仅自动地选择、绑定 Web 服务，同时更重要的是自动地创建过程模型。这需要请求者指定一些约束关系，包括 Web 服务间的依赖关系、用户的偏爱等。2.2.2 基于BPEL4WS 的 Web 服务组合BPEL4WS( Business Process Execution Language for Web Servic

38、es，Web 服务的商业流程执行语言)是专为整合 Web 服务而制定的一项规范标准。BPEL4WS 的作用是将一组现有的服务整合起来，从而定义一个新的 Web 服务。它能够将Web 服务调用、操作数据、抛出故障或终止一个流程等不同的活动连接起来，从而创造出复杂的流程，这些活动可以嵌套到结构化活动中，结构化活动定义了活动的运行方式和流程。BPEL4WS 可将一组现有的服务整合起来，从而定义一个新的 Web 服务。BPEL4WS 流程是一个流程图，用来表达特定业务的处理逻辑和算法，流程的每一步称为一个活动。BPEL4WS 主要利用 WSDL 使得服务的动态绑定成为可能，但它没有提供具体方式来选取动

39、态绑定时需要调用的服务，并且 BPEL4WS 不支持在应用运行时的流程模型的调整。与类似 BPEL4WS 这样来表达业务流程的还有 BPEL 等。查找 Web 服务时需要搜索巨大的服务空间，比较、匹配满足条件的服务，因此用来组建组合服务的方法复杂、动态以致难以手工处理。为了自动地开发组合服务，需要同软件开发方法一样的系统的方法来分析需求，将需求所涉及的活动模型化。改变服务开发方法使其适应服务组合开发的好处是我们能够深入了解组建服务组合流程以致更好地管理其实现。2.3 Petri 网Petri 网是对离散并行系统的数学表示。Petri 网最早是由德国学者 Carl Adam Petri 博士在

40、1962 年提出来的，适合于描述异步的、并发的计算机系统模型。Petri 网既有严格的数学表述方式，也有直观的图形表达方式，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提供坚实的概念基础。一个 Petri 网是一个有向连通图，其节点分别称为库所和变迁，每个库所代，而库所中的托肯数表示的数量，当变迁 t 的所有输入库所中都表一种至少含有一个托肯时(标识 M)，t 就可以发生，记为M>t。变迁发生的结果是从每个输入库所中移除若干个托肯，而给每个输出库所移入若干个托肯。此时到达标识 M记为M>tM。一个经典的 Petri 的数学表达如下：Net(S，T;F)STSTFS

41、15;T T×S dom(F)cod(F)ST 其中 S 是库所（状态）的集合，T 为变迁（）的集合。在形式化表达中，通常用圆圈或椭圆表示库所，用方框或粗杠表示变迁，用箭头表示流关系的图形的示例，如图 2.3：s1t1t2s6s2s3s4s5t4t3s->t两种弧t->ss7图 2.3Petri 网中的形式化表达Petri 网是一个良好的过程建模方法，在库所中添加表示状态信息的托肯分布，并按规则使得变迁驱动状态演变，从而反映系统动态运行过程。采用 Petri 网来建立模型有许多优点，主要有两个：其一是其图形化的描述比较容易让用户理解系统模型，其二是可以利用 Petri 网

42、对模型进行形式分析和验证。第三章基于 Petri 网的 Web 服务组合3.1 基于 Petri 网的 Web 服务定义为了应用 Petri 网验证 Web 服务，需将 Petri 网元素与 Web 服务的元素相对应，以达成用 Petri 网形式化地描述 Web 服务组合。基于 Petri 网的 Web 服务定义如下。定义 3.1 Web 服务定义。一个 Web 服务 S 定义为六元组：S=(Id，SName，Desc，SOnto，URL，Oper)， 其中：llllId：Web 服务的唯一的标识； SName：Web 服务的名称； Desc：服务的描述；SOnto：服务的领域本体，包括对服务

43、所属领域类型的语义描述及参数及操作的语义描述；分类领域本体用来过滤掉不相关的不同服务领域的服务，组织服务到服务的所属分类。llURL：服务的调用；Oper：服务的操作集。定义 3.2 服务网的定义。一个服务网 SN 定义为五元组，用来对服务的动态行为进行建模：SN=(P，T，W，i，o)，其中：P：有限库所集，代表 Web 服务的状态，P=p1，p2，.，pn；T：有限变迁集，代表服务中的操作(operation)及服务之间的操作，T=t1， t2，.，tn；W：(P×T) (T×P) ，是有向弧的集合，表示服务状态和操作之间的关系； i：输入库所，i=xPT|(x，i)W

44、=； o：输出库所，o=xPT|(o，x)W=。库所 i 被认为是服务 S 的初始标识，当有一个托肯在库所 i 中时，执行服务S，当有一个托肯在库所 o 中时，被认为终止服务 S。用标识函数表示系统状态， 另外对系统状态的演变过程进行描述，就可以对 Web 服务组合系统的静态特性、动态特性进行全面的建模。系统动态演变过程的描述是和 Petri 网的运行规则对应的：(1) tT 在标识 M 可触发当且仅当对于任何 pP，M(p)I(p，t)；(2) 若 t T 在标识 M 下可触发， 按照激活规则产生新标识 M' ， M(p)=M'(p)+W(p，t)-W(t，p)。M'

45、被称为 M 的直接可达标识，M 称为 M0 的可达标识当且仅当在以上运行规则下，存在一个变迁的触发序列 t1，t2，.，tn，使得模型标识从 M0 转换到 M，所有 M0 的可达标识称为 Petri 网 PN 的可达集。3.2 Web 服务组合的代数描述Web 服务组合组件由原子服务和结构两部分组成。结构如：顺序、并行、选择、循环等，本文采用 Petri 网对流精确描述。在定义 3.1 的和定义 3.2 的基础上，Web 服务组合可通过类 BNF 范式的符号进行定义。代数操作符的语法如下：S：=X|S1S2|S1S2|S1S2|S|S1cS2(1)X 表示一个原子服务或空服务(即一个服务没有执

46、行任何操作)； (2)S1S2 表示一个组合服务是顺序执行 S1 和 S2 后形成的； (3)S1S2 表示一个组合服务是执行 S1 或 S2 后形成的(不可兼或)；(4) S1S2 表示一个组合服合是按 S1 和 S2 顺序执行或按 S2 和 S1 顺序执行后形成的，等价于 S1S2S2S1；(5) S 表示一个组合服务是由 S 循环执行 次后形成的；(6) S1CS2 表示一个组合服务是由 S1 和 S2 并发执行后形成的，在并发执行中间两个服务间可能会有通信。组合的 Web 服务可以通过上述的代数表达式获得。定义 3.3 服务组合模型是合理的，必须满足以下基本要求：(1) 每个模型都存在

47、一个输入库所 i 和一个输出库所 O；(2) 每个变迁库所都在一条从输入库所 i 到输出库所 O 的路径上；(3) 在任何情况下，服务组合总能最终终止，在终止的时候，只有输出库所中有托肯，而其它库所是没有托肯存在的；(4) 在组合模型中没有死组合的存在，即任何一个组合都有执行的可能。根据以上四个要求，我们给出组合模型的图形化表示。采用 Petri 网建模时， 指定服务的操作为变迁，服务的状态为库所，基于 Petri 网的 Web 服务建模方法中最小的组合单元是原子服务。在服务组合中将子服务(原子服务或组合服务)的操作当作(变迁)，子服务 S1 和 S2 的操作执行使得服务的状态(库所)发生了改

48、变。任何时刻一个服务可以处于如下状态：非实例状态(notinstantiated)、准备好状态(ready)、运行状态(running)、挂起状态(suspended)和完成状态(finished)。本文服务组合中处于ready状态的服务被组合，当服务处于finished状态时表示服务被组功。(1)组合服务 S1S2 的 Petri 网图形化表示如图 3.1 所示。图 3.1 组合服务 S1S2(2)组合服务 S1S2 的 Petri 网图形化表示如图 3.2 所示。图 3.2 组合服务 S1S2(3) 组合服务 S1S2 的 Petri 网图形化表示如图 3.3 所示。图 3.3 组合服务

49、S1S2(4) 组合服务 S 的 Petri 网图形化表示如图 3.4 所示。图 3.4 组合服务 S(5) 组合服务 S1CS2 的 Petri 网图形化表示如图 3.5 所示，两个子服务间有可能有信息通信，库所 m 用来存放通信信息。图 3.5 组合服务 S1cS2对于一些更复杂的服务组合操作，可以由上述基本操作可复杂的服务组合操作。如(S1S2Sn)S，其 Petri 网图形化表示如图 3.6 所示。该组合服务表示先执行原子服务集合中的某个 Si(i1，2n)，再执行 S 后形成的组合服务。其中从 n 个原子服务中选择最优的原子服务的过程将根据价格，递交时间和可靠性能等因素通过选用一个等

50、级标准来。图 3.6 组合服务(S1S2.Sn)S3.3 Petri 网模型生成算法在服务组合时需要通过Petri 网的分析技术来对组合服务进行验证分析，Petri网模型生成算法的生成算法如下：Step1.确定待组合的 Web 服务数、各服务的操作以及流；Step2.产生一个的初始服务状态，并加上一个标记，作为初始子网； Step3.forj=1toM/*待组合服务中有 j 个操作模块*/a.按流选择一个操作模块；b.给每个操作分配一个随机操作时间，操作时间满足指数分布的概率分布； c.将操作连接到已存在的子网中去。Step4.end Step5.endStep6.为每种服务状态创建相应的状态

51、位置； Step7.使用如下方法将服务状态加入到操作中去：a.选择一个服务状态位置；b.按流将此状态分配给相应的服务操作，分配时用输出弧将状态位置和操作位置的输入变迁相连，用输入弧将状态和操作位置的输出变迁相连；c.重复 Step7，直到按流所有操作位置都分配了服务状态。在程序实现中，算法程序的输出就是产生的服务组合的 Petri 网模型，它们是用伴随矩阵和、初始标识、终止标识和操作时间向量 来描述的。3.4 应用 Petri 网验证 Web 服务组合分析 Petri 网可采用可达树法、不变量分析、约简等方法，其中可达树分析法直观简捷，可方便地分析系统的可达性、有界性、活性等各种动态特性，Pe

52、tri 网的大部分特性可以由可到达树来进行验证。我们通过结合可到达树的构造和正确性的检查来实现流程模型的验证过程。可到达树的基本思想就是将可到达的标识作为节点，变迁的触发作为连接弧，来构造一棵树。我们的算法就是在构造树的过程中，检查服务组合的状态和其中库所的托肯数目以实现流程模型的验证。当服务组合时只关心系统可能的状态时，可达标识集可以满足这类问题的要求。给定 Petri 网中的一个标识 M，该网络的可达标识表示为M>。给定一个以M0 M0 为初始标识的 Petri 网 N，我们可以从 M0 (根结点)开始计算得到与使能变迁一样多的新标识。从这些新的标识，又可得到的标识，重复进行这个过程

53、的结果可得到一棵可达树。节点就是从 M0 产生的后继标识，弧代表从从初态 M0 开始的所有可能一个标识到另一个标识的变迁激发。可达树到达的状态，结点代表 M0 及其可达的后继，其中树根为 M0，树叶对应着系统的终态，弧代表相应的变迁。从树根到某结点的路径代表着从初态变迁到该状态。利用可达树算法生成可达树后，任何发生序列都可通过在图上执行搜索获得。Web 服务组合的正确终止对于组合服务非常重要，通过 Petri 网对活性和有界性的验证来决定服务是否正常结束，通过是否具有完全可达性、完整性和前进性来验证 Web 服务组合的正确性。定义 3.4 可达性:若从初始标识 M0 出发触发一个变迁序列产生标

54、识 Mr，则称 Mr 是从 M0 可达的。所有从 M0 可达的标识的集合称为可达标识集或可达集，记为 R(M0)。定义 3.5有界性:给定 PN 以及其可达集 R(M0)，对于位置 pP，若 0mR(M0):M(p)k，则称 p 是 k 有界的，此处 k 为正整数；若 Petri 网的所有位置都是 k 有界的，则 Petri 网是 k 有界。定义 3.6 活性：对于一个变迁 tT，在任一个标识 MR 下，若存在某一变迁序列 Ser，该变迁序列的触发使得此变迁 t 可触发，则称该变迁是活的。若一个 Petri 网的所有变迁都是活的，则称该 Petri 网是活的。定义 3.7 完整性：Petri

55、网所有的状态都是可达的。定义 3.8前进性：每次触发都将逐步推向终态，可达树中循环。出现无论的同时具有上述 5 个性质的 Petri 网出现停滞不前的状态，执行中所处的状态及等待的消息是有限的，的正确性的分析。出现死锁。本文给出如下两个 Web 服务组合(1)组合服务 S1S2 的正确性分析下面通过对图 3.4 所示的组合服务 S1S2 的构造可达树，以分析该服务组合的正确性，可达树如图 3.7 所示。图 3.7 组合服务 S1S2 的可达树 该组合服务是完全可达的。从 M0 开始的状态可达集 R(M0)= M0, M1 ,M2 ,M3 , M4 , M5 , M6。状态集 MS= M0, M1 ,M2 , M3 , M4 , M5 , M6。因此，对任一个标记 MiMS，均有R(M0)，即组合服务 S1S2 中任一个状态都是从 M0 可达。该组合服务具有界性。在可达树中，每一个位置上的托