毕业论文-基于Petri网的Web服务组合验证研究

1、南京邮电大学 毕 业 设 计（论 文） 题 目基于Petri网的Web服务组合验证研究专 业信息安全学生姓名班级学号指导教师指导单位计算机学院、软件学院 日期：2014年3月10日至2014年6月13日毕业设计（论文）原创性声明 本人郑重声明：所提交的毕业设计（论文），是本人在导师指导下，独立进行研究工作所取得的成果。除文中已注明引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。 论文作者签名： 日期： 年 月 日摘 要近年来Web服务的理论和技术取得了长足的发展，其保证互操作性的协议栈

2、下层在学术界和工业界已基本达成一致。Web服务的价值在于服务重用，新兴的Web服务组合正是主要的重用手段。然而基于流程的Web服务组合建模是一个复杂且易出错的过程。如果流程定义在投入运行之后被发现有错，则修复错误的代价相当高。因此，在建模阶段进行有效的过程验证时十分必要的。此外Web服务组合可能存在不必要的流程设计而影响执行效率。本课题分析了基于Petri网建模的优势，给出基于Petri网的Web服务的形式化定义和描述，对Web服务组合进行建模及元素映射，给出Petri网模型生成算法并对组合服务模型的可达性、安全性、有界性与活性等特性进行验证分析。从而达到对基于Petri网的Web服务组合的验

3、证。关键词：Web服务；Petri网；服务组合；服务组合验证全套设计加扣3012250582ABSTRACTWeb Services offer a new paradigm for distributed computing on the World 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 tole

4、rance for run time errors, as repairing them at service operation time is usually costly. The development of such Web services 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

5、 flow design which can lead to low performance. Then reduction is needed. The advantages were discussed for modeling web services composition using Petri net in this thesis. Based on Petri net theory, the formal definition and graphic description were proposed for web services and their composition;

6、 the element mapping process was also illustrated. Then an algorithm was proposed to construct the Petri net model for web services composition. The reachability, safeness, boundness and liveness of the model were also validated. To achieve the verification of web service composition based on Petri

7、net.Key words: Web services; Petri net; Services composition; Services composition verification目 录第一章绪论11.1 研究背景11.2 研究目的31.3 研究现状41.4 结构安排4第二章 相关技术探究62.1 Web服务概述62.1.1 Web服务的定义62.1.2 Web服务的特点62.1.3 Web服务的结构模型72.1.4 Web服务核心标准和协议栈72.1.5 Web服务的应用领域92.2 Web服务组合92.2.1 Web服务组合的定义92.2.2 基于BPEL4WS的Web服务组合1

8、02.3 Petri 网10第三章 基于Petri网的Web服务组合123.1 基于Petri网的Web服务定义123.2 Web 服务组合的代数描述133.3 Petri网模型生成算法153.4 应用Petri网验证Web服务组合16第四章 基于Petri网的Web服务组合的实例分析194.1 Cygwin194.1.1 Cygwin概述194.1.2 Cygwin组成和工作机制194.1.3 Cygwin安装与配置204.2 BPEL2oWFN234.2.1 BPEL2oWFN的介绍234.2.2 BPEL2oWFN在Cygwin平台上的编译244.2.3 BPEL2oWFN在Cygwin

9、平台上的安装264.3 LOLA274.3.1 LOLA的介绍274.3.2 LOLA在Cygwin平台上的编译274.3.3 LOLA在Cygwin平台上的安装294.4 对实际的Web服务组合进行结构验证30结束语35致 谢36参考文献37南京邮电大学2014届本科生毕业设计（论文）第1章 绪论1.1 研究背景Web服务作为一种新型的分布式构件模型已经在电子商务、企业应用集成等领域扮演着越来越重要的角色，特别是Web服务的组合技术，因其能实现服务的重用和增值而成为学术界和工业界关注的焦点。服务组合是将服务看成构件而进行重用的技术，能在现有的服务中选取特定的服务，组合成新的服务来满足用户的需

10、求。近年来Web服务的理论和技术取得了长足的发展，其保证互操作性的协议栈下层在学术界和工业界已基本达成一致。然而Web服务的价值在于服务重用，新兴的Web服务组合正是主要的重用手段。Web服务技术遵循面向服务架构(SOA：Service-Oriented Architecture)将网络上的成员划分为Web服务的需求者、提供者和中介者三种角色。并且以各项基于XML的标准协议达成异构平台间的整合：利用简单对象访问协议(SOAP)执行、发布和查询服务，以Web服务描述语言(WSDL)描述服务的应用程序接口，并且通过统一描述发现与整合规范(UDDI)为服务需求者和提供者提供代理机制。近年来，通过许多

11、现存Web服务的协同组合产生一个新的Web服务以达成特定目的的行为被称之为Web服务组合，产生的组合服务也可以作为构成其它组合服务的一个基础服务。通过Web服务组合可以实现出具备更多功能更有价值的企业流程，通过基础Web服务的组合可以创造出更多更有价值的企业应用服务。许多的企业组织也将它们的核心服务包装成Web服务的形式放在网络上供服务需求者使用，例Google的搜寻服务、Amazon的书籍查询服务等。如此通过面向服务架构中介机制的透明化特性，Web服务组合便可以跨越企业组织将各个不同企业所提供的Web服务加以组合创造出新的增值性Web服务。从Web服务组合使用者的观点来看，Web服务组合的需

12、求规范可以划分为面向过程的规范(POS；Process Oriented Specification)和面向接口的规范(IOS；Interface Oriented Specification)两种。POS规范包含许多抽象化的Web服务组件(以服务的功能为基础并不需要实际指定由那一个服务负责执行)配合企业应用逻辑以工作流程的概念描述这些Web服务间的协同关系；IOS规范只需要Web服务组合使用者针对所需求的Web服务组合提供输入和输出的信息，至于Web服务组合中要包含那些基于Petri网的Web服务组合的验证与化简Web服务组件，要以什么样的结构组合这些服务，使用者并不需要知道。这两种Web服

13、务组合需求规范必须以不同的方法来达成，采用POS规范的Web服务组合最好是由企业逻辑模型配合工作流程的规划来实现Web服务的组合协同；而采用IOS规范的Web服务组合则需通过自动化程序组合方法的使用来达成Web服务的组合协同。就Web服务组合发展来看，采用POS规范也就是利用工作流程的概念来规划Web服务的组合协同仍然是目前最通用的方法，许多的Web服务汇编语言例如BPEL4WS、WSFL、WSCL、XLANG、BPML、BPSS、WSCI、Wf-XML、JDF、PIPs等也都采用工作流程的概念作为协同Web服务组合运作的方法。 然而目前的Web服务组合仍存在着许多问题有待解决，主要包括以下几

14、点：l Web服务组合的开发问题以工作流程为基础的Web服务组合开发和管理需要具备特定的知识且耗费大量的程序撰写时间。目前虽然有许多的Web服务汇编语言但是在开发上仍然需要以编辑文件的方式来开发Web服务组合，然而这是非常费时且没有效率的。因此许多的研究都发展出Web服务组合的开发平台来方便组合服务开发者的开发工作，例如：Self-Serv、eFlow、FUSION、SCET等。l Web服务组合的挑选问题由于在Web服务的架构下，通过UDDI中介机制每个服务提供者都可以将服务注册到中介者上，因此在进行Web服务组合时，对于同样的工作任务可能有许多的Web服务都可以达成，也因此产生Web服务在

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

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

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

18、目的本课题理解Petri网相关知识及其在Web服务组合中应用，分析基于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服务组合流程设计的正确性。l 改善Web服务组合的执行效率本课题将七个流程简化规则应用在Web服务组合的简化上，这些简化规则可以在不影响Web服务组合原有功能的前提下，转换Web服务组合

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

21、Web服务是语义网的一个关键应用研究领域，Web服务的激增和语义网技术的发展，为多样的Web服务组合提供了便利。语义网技术提供了计算机可判断的Web内容和性能标记，推动了服务的自动发现和服务组合。目前Web服务及其组合的形式化描述和验证是语义Web服务中一个重要的研究方向，现有的许多Web服务及其组合描述语言都是半形式化的，容易出错和不容易检测，正确性难以保证，需要有形式化的方法来验证Web服务组合模型。模型的正确性是指模型结构上的正确性，即是安全、有界、无死锁等。Petri网作为一种基于状态的形式化建模方法，具有直观、形象且有严格语义和数学分析之优点，是数据和控制流的抽象和形式化建模方法。本

22、文采用Petri网对Web服务组合进行正确性验证。1.4 结构安排第一章、绪论 绪论部份描述本课题的研究背景、研究目的和本文的工作，并且说明本论文的结构安排。第二章、相关技术探讨本章为相关技术的概述 主要目的是为本课题所做工作提供相关的基础知识。第一节概述Web服务，包括Web服务的定义、Web服务的特点、Web服务的结构模式、Web服务的核心标准和协议栈及Web服务的目前应用领域。第二节Web服务组合，主要是对Web服务组合的定义进行说明，特别介绍了基于BPEL4WS的Web服务组合。第三节着重阐述了Petri的相关理论。第三章、基于Petri-Net的Web服务组合 本章描述本课题所提出的

23、基于Petri-Net的Web服务组合验证。共分为四个小节，第一节说明Web服务组合的定义。第二小节用代数描述了Web服务组合。第三小节阐述了Petri网模型生成算法。最后一节重要介绍应用Petri网验证Web服务组合，如分析Petri网可采用可达树法、不变量分析、约简等方法。第四章、基于Petri网的Web服务组合的实例分析 本章阐述基于Petri-Net的Web服务组合验证的实例分析，以实现第三章提出的Web服务组合验证概念。本章共分为四个小节，首先阐述本次课题实现基于的平台，即Cygwin平台，包括它的一些概述，它的组成与工作机制以及最重要的安装与环境的配置。第二、三部分描本课题实现的两

24、个很重要的工具，BPEL2WFN和LOLA，用两小节分别对它们进行了介绍以及在Cygwin平台上的编译与安装、调试。第四部分详细描述对一个实际的Web服务组合进行结构验证。第二章 相关技术探究2.1 Web服务概述2.1.1 Web服务的定义随着技术的进步，Web的角色从信息的容器逐渐发展成为提供Web服务的载体，Web服务建立在面向服务的体系结构(Service-Oriented Architecture，SOA)基础之上。SOA为最新的分布式计算技术，可以将软件组件(包括来自不同系统的程序函数、对象和进程)发布为服务。 根据万维网协会(World Wide Web Consortium，W

25、3C)的定义，一个Web服务是指通过统一资源标志符(Universal Resource Identifier，URI)标志的一个软件系统，其公共接口和绑定方式是通过可扩展标记语言（eXtensible Markup Language，XML）来定义和描述的。其他软件系统可以发现Web服务的定义，然后可以按照定义所规定的方式与这个Web服务进行交互。这种交互使用基于XML的消息，通过网络传输协议来进行。2.1.2 Web服务的特点从外部的使用者的角度而言，Web服务是一种部署在Web服务器上的对象或组件，它具备以下特征：封装性：Web服务是一种部署在Web上的对象，自然具备对象的良好封装性，对

26、于使用者而言，他能且仅能看到该对象提供的功能列表。互操作性：任何 Web Service 都可以与其它 Web Service 进行交互，Web服务通过SOAP实现相互间的访问，这样就避免了在 CORBA，DCOM 和其它协议等等不同协议之间转换的麻烦。还因为可以使用任何语言来编写Web服务，开发者无需更改他们的开发环境就可生产和使用Web服务，同时还可以在新的Web服务中使用己有的Web服务而不必考虑Web服务的实现语言，运行环境等具体实现细节。普遍性：Web服务使用HTTP和XML进行通信。因此，任何支持这些技术的设备都可以拥有和访问Web服务。相信在未来，Web服务将普遍应用于社会生活的

27、各个领域。易实现性：Web Service背后的概念易于理解，并且来自微软和SUN等这样的供应商的免费工具箱能够让开发者快速创建和部署自己的Web服务。松散耦合：这一特性源于对象/组件技术，当一个Web服务的实现发生变更的时候，调用者将不会受到任何影响。对于调用者来说，只要Web服务的调用界面不变，Web Service 实现的任何变更对他们来说都是透明的，甚至是当Web Service的实现平台从J2EE迁移到了.NET或者是相反的迁移流程，用户都可以对此一无所知。 标准性：使用开放的标准协议进行描述、传输和交换。这些标准协议具有完全免费的规范，以便由任意方进行实现。一般而言，绝大多数规范将

28、最终由W3C 或OASIS(Organization for the Advancement of Structured Information Standards，结构化标准信息推进组织)等权威组织作为最终版本的发布方和维护方。 2.1.3 Web服务的结构模型Web服务本身是跨平台的、独立的、模块化的应用，能够通过网络，特别是WWW来描述、发布、定位以及调用。根据W3C的标准提议，一个典型的Web服务体系结构基于三种角色(服务提供者、服务发现代理和服务请求者)之间的交互。交互涉及发布、查找和绑定操作。这些角色和操作一起作用于Web服务构件。服务提供者定义Web服务的服务描述并把它发布到服务

29、请求者或服务注册中心。服务请求者使用查找操作来从本地或服务发现代理检索服务描述，然后使用服务描述与服务提供者进行绑定并调用Web服务实现或同它交互。服务提供者和服务请求者角色是逻辑结构，因而服务可以表现两种特性。图2.1表示了这些操作、提供这些操作的组件及它们之间的交互。Web服务代理 查找注册Web服务提供者Web服务请求者 绑定图2.1 Web 服务体系构架模型2.1.4 Web服务核心标准和协议栈要以一种可互操作的方式执行发布、发现和绑定这三个操作，必须有一个包含每一层标准的Web服务协议栈作为Web服务标准化组织，W3C Web服务体系架构工作组(W3C Web Services Ar

30、chitecture Working Group)在概念层面上提出了一组Web服务的协议栈，图2.2展示了这个Web服务协议栈。对各层稍作粗略的解释如下：图2.2 Web 服务体系结构协议栈 服务发现和集成与UDDI服务发现与集成的目标是根据请求者的要求发现合适的Web服务，并将该Web服务的服务描述返回给请求者，然后请求者可能将该服务动态集成到应用中。该层可使用的模式有多种。UDDI作为广泛使用的规范是其中的一种。UDDI(Universal Description， Discovery and Integration，通用描述、发现和集成)是基于XML的规范。它是为使软件能够在网络自动发现

31、服务并通过提供必要的转换自动同服务集成在一起而设计的。UDDI报文附加在SOAP协议之上，SOAP负责调用网上的服务。Web服务描述层与WSDL服务描述层的目标是帮助Web服务描述其功能。在这层上WSDL( Web Services Description Language，Web服务描述语言)作为 W3C推荐的服务描述语言得到广泛的应用，也使事实上的工业标准。WSDL用来描述网络服务或终端(endpoint)的一种XML语言，它用于定义Web服务：以及如何调用它们(描述Web服务的属性，例如它做什么，它位于哪里和怎样调用它)。消息层与SOAP消息层的作用是将Web服务消息独立于特定的传输协议

32、。作为W3C唯一推荐的消息层协议，也是事实上的工业标注，SOAP(Simple Object Access Protocol，简单对象访问协议)是一个基于XML的报文协议，用于访问网上的服务。SOAP可以运行在任何其它传输协议上。比如可以使用HTTP，SMTP，JMS等协议来传递SOAP消息。各种传输层之间基于Petri网的Web服务组合的验证与化简的报头是不同的，但XML有效负载保持相同。SOAP用XML将消息编码，因此在调用过程的任何一步都很容易地处理消息。另外，调试SOAP消息的方便性使各种SOAP执行能快速聚合在一起，达到大范围的协同工作。最后各种针对SOAP的扩展使Web服务获得更多

33、的特性，比如安全性等等。XML(eXtensible Markup Language，可扩展标记语言)是Internet上数据表示和数据交换的一种标准。它是一种元语言，可以用来定义和描述结构化数据，它是Web服务得以实现的语言基础。Web服务的其它协议规范都是以XMI的形式来描述和表达的。在Web服务技术中，SOAP消息作为各种传输协议的有效载荷，被用来发送与接受。迄今为止，在Web服务中使用的最广泛的传输协议协议是HTTP，当然也可以使用其它传输层协议，如FTP、SMTP等。2.1.5 Web服务的应用领域Web服务基本上覆盖了传统分布计算技术的应用领域。作为目前最典型的异构分布技术，Web

34、服务在应用程序跨平台和跨网络进行通信的时候是非常有用的。Web服务适用于应用程序集成、B2B集成、代码和数据重用，以及通过Web进行客户端和服务器的通信的场合。下面是几个Web服务主要的应用领域：(1)跨越防火墙的通信。与COM，CORBA等集成技术不同，Web服务一开始就是针对Internet的集成。他们采用XML的一系列标准，并且能够以HTTP作为传输层协议，这让它获得了穿越防火墙的能力。(2)应用系统集成。通过Web服务，应用程序可以用标准的方法把功能和数据暴露出来，供其它的应用程序使用。用Web服务来实现集成的最大好处在于可以轻易实现互操作性。只要把你的商务逻辑暴露出来，成为Web服务

35、，你就可以让任何指定的合作伙伴轻松的调用你的商务逻辑，而不管他们的系统在什么平台上运行，使用的是什么开发语言。这样就大大减少了花在集成的上的时间和成本。(3)软件重用。目前，软件重用有一个严重的限制，即重用仅限于代码，而数据不能被重用。因为可以很轻易的发布组件甚至源代码，但要发布数据就没那么容易了，除非那些数据都是不会经常变化的静态数据。而Web服务则允许在重用代码的同时，重用代码后面的数据。2.2 Web服务组合 2.2.1 Web服务组合的定义随着Web服务技术的日益成熟，越来越多的稳定易用Web服务共享在网络上。但单个的Web服务能够提供的功能有限，为了更加充分地利用共享的Web服务，有

36、必要将共享的Web服务组合起来，提供更为强大的服务功能，加快系统开发的速度，快速满足用户需求。Web服务组合方法从组合方案生成方式来分有两大类:静态组合和动态组合。静态组合意味着请求者应在组合计划实施前创建一个抽象的过程模型。抽象的过程模型包括任务的集合以及任务间的数据依赖关系，每个任务包含一个查询的子句，用来查找完成任务的真正的Web服务。因此这里的自动仅指Web服务的选择和绑定是由程序自动完成的。静态组合中最常用的是用图来描述过程模型。而动态组合不仅自动地选择、绑定Web服务，同时更重要的是自动地创建过程模型。这需要请求者指定一些约束关系，包括Web服务间的依赖关系、用户的偏爱等。2.2.

37、2 基于BPEL4WS的Web服务组合BPEL4WS( Business Process Execution Language for Web Services，Web服务的商业流程执行语言)是专为整合Web服务而制定的一项规范标准。BPEL4WS的作用是将一组现有的服务整合起来，从而定义一个新的Web服务。它能够将Web服务调用、操作数据、抛出故障或终止一个流程等不同的活动连接起来，从而创造出复杂的流程，这些活动可以嵌套到结构化活动中，结构化活动定义了活动的运行方式和控制流程。BPEL4WS可将一组现有的服务整合起来，从而定义一个新的Web服务。BPEL4WS流程是一个流程图，用来表达特定业

38、务的处理逻辑和算法，流程的每一步称为一个活动。BPEL4WS主要利用WSDL使得服务的动态绑定成为可能，但它没有提供具体方式来选取动态绑定时需要调用的服务，并且BPEL4WS不支持在应用运行时的流程模型的调整。与类似BPEL4WS这样来表达业务流程的还有BPEL等。查找Web服务时需要搜索巨大的服务空间，比较、匹配满足条件的服务，因此用来组建组合服务的方法复杂、动态以致难以手工处理。为了自动地开发组合服务，需要同软件开发方法一样的系统的方法来分析需求，将需求所涉及的活动模型化。改变服务开发方法使其适应服务组合开发的好处是我们能够深入了解组建服务组合流程以致更好地管理其实现。2.3 Petri

39、网Petri网是对离散并行系统的数学表示。Petri网最早是由德国学者Carl Adam Petri博士在1962 年提出来的，适合于描述异步的、并发的计算机系统模型。Petri网既有严格的数学表述方式，也有直观的图形表达方式，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提供坚实的概念基础。 一个Petri网是一个有向连通图，其节点分别称为库所和变迁，每个库所代表一种资源，而库所中的托肯数表示资源的数量，当变迁t的所有输入库所中都至少含有一个托肯时(标识M)，t就可以发生，记为Mt。变迁发生的结果是从每个输入库所中移除若干个托肯，而给每个输出库所移入若干个托肯。此时到达标识M记为M

40、tM。 一个经典的Petri的数学表达如下：Net(S，T;F)STSTFSTTSdom(F)cod(F)ST其中S是库所（状态）的集合，T为变迁（事件）的集合。在形式化表达中，通常用圆圈或椭圆表示库所，用方框或粗杠表示变迁，用箭头表示流关系的图形的示例，如图2.3：图2.3Petri网中的形式化表达Petri网是一个良好的过程建模方法，在库所中添加表示状态信息的托肯分布，并按引发规则使得变迁引发驱动状态演变，从而反映系统动态运行过程。采用Petri网来建立模型有许多优点，主要有两个：其一是其图形化的描述比较容易让用户理解系统模型，其二是可以利用Petri网对模型进行形式分析和验证。第三章 基

41、于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)，其中：l Id：Web服务的唯一的标识；l SName：Web服务的名称；l Desc：服务的描述；l SOnto：服务的领域本体，包括对服务所属领域类型的语义描述及参数及操作的语义描述；分类领域本体用来过滤掉不相关的不同服务领域的服务，

42、组织服务到服务的所属分类。l URL：服务的调用；l Oper：服务的操作集。定义3.2 服务网的定义。一个服务网SN定义为五元组，用来对服务的动态行为进行建模：SN=(P，T，W，i，o)，其中：P：有限库所集，代表Web服务的状态，P=p1，p2，.，pn；T：有限变迁集，代表服务中的操作(operation)及服务之间的操作，T=t1，t2，.，tn；W：(PT)(TP)，是有向弧的集合，表示服务状态和操作之间的关系；i：输入库所，i=xPT|(x，i)W=；o：输出库所，o=xPT|(o，x)W=。库所i被认为是服务S的初始标识，当有一个托肯在库所i中时，执行服务S，当有一个托肯在库所

43、o中时，被认为终止服务S。用标识函数表示系统状态，另外对系统状态的演变过程进行描述，就可以对Web服务组合系统的静态特性、动态特性进行全面的建模。系统动态演变过程的描述是和Petri网的运行规则对应的：(1)tT在标识M可触发当且仅当对于任何pP，M(p)I(p，t)；(2)若tT在标识M下可触发，按照激活规则产生新标识M，M(p)=M(p)+W(p，t)-W(t，p)。M被称为M的直接可达标识，M称为M0的可达标识当且仅当在以上运行规则下，存在一个变迁的触发序列t1，t2，.，tn，使得模型标识从M0转换到M，所有M0的可达标识称为Petri网PN的可达集。3.2 Web 服务组合的代数描述

44、Web服务组合组件由原子服务和控制结构两部分组成。控制结构如：顺序、并行、选择、循环等，本文采用Petri网对控制流精确描述。在定义3.1的和定义3.2的基础上，Web服务组合可通过类BNF范式的符号进行定义。代数操作符的语法如下：S：=X|S1S2|S1S2|S1S2|S|S1cS2(1)X表示一个原子服务或空服务(即一个服务没有执行任何操作)；(2)S1S2表示一个组合服务是顺序执行S1和S2后形成的；(3)S1S2表示一个组合服务是执行S1或S2后形成的(不可兼或)；(4)S1S2表示一个组合服合是按S1和S2顺序执行或按S2和S1顺序执行后形成的，等价于S1S2S2S1；(5)S表示一

45、个组合服务是由S循环执行次后形成的；(6)S1CS2表示一个组合服务是由S1和S2并发执行后形成的，在并发执行中间两个服务间可能会有通信。组合的Web服务可以通过上述的代数表达式获得。定义3.3服务组合模型是合理的，必须满足以下基本要求：(1)每个模型都存在一个输入库所i和一个输出库所O；(2)每个变迁库所都在一条从输入库所i到输出库所O的路径上；(3)在任何情况下，服务组合总能最终终止，在终止的时候，只有输出库所中有托肯，而其它库所是没有托肯存在的；(4)在组合模型中没有死组合的存在，即任何一个组合都有执行的可能。根据以上四个要求，我们给出组合模型的图形化表示。采用Petri网建模时，指定服

46、务的操作为变迁，服务的状态为库所，基于Petri网的Web服务建模方法中最小的组合单元是原子服务。在服务组合中将子服务(原子服务或组合服务)的操作当作事件(变迁)，子服务S1和S2的操作执行使得服务的状态(库所)发生了改变。任何时刻一个服务可以处于如下状态：非实例状态(notinstantiated)、准备好状态(ready)、运行状态(running)、挂起状态(suspended)和完成状态(finished)。本文服务组合中处于ready状态的服务被组合，当服务处于finished状态时表示服务被组合成功。(1)组合服务S1S2的Petri网图形化表示如图3.1所示。图3.1 组合服务S

47、1S2(2)组合服务S1S2的Petri网图形化表示如图3.2所示。图3.2 组合服务S1S2(3) 组合服务S1S2的Petri网图形化表示如图3.3所示。图3.3 组合服务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，2

48、n)，再执行S后形成的组合服务。其中从n个原子服务中选择最优的原子服务的过程将根据价格，递交时间和可靠性能等因素通过选用一个等级标准来判断。图3.6 组合服务(S1S2.Sn)S3.3 Petri网模型生成算法在服务组合时需要通过Petri网的分析技术来对组合服务进行验证分析，Petri网模型生成算法的生成算法如下：Step1.确定待组合的Web服务数、各服务的操作以及控制流；Step2.产生一个的初始服务状态，并加上一个标记，作为初始子网；Step3.forj=1toM/*待组合服务中有j个操作模块*/a.按控制流选择一个操作模块；b.给每个操作分配一个随机操作时间，操作时间满足指数分布的概

49、率分布；c.将操作连接到已存在的子网中去。Step4.endStep5.endStep6.为每种服务状态创建相应的状态位置；Step7.使用如下方法将服务状态加入到操作中去：a.选择一个服务状态位置；b.按控制流将此状态分配给相应的服务操作，分配时用输出弧将状态位置和操作位置的输入变迁相连，用输入弧将状态和操作位置的输出变迁相连；c.重复Step7，直到按控制流所有操作位置都分配了服务状态。在程序实现中，算法程序的输出就是产生的服务组合的Petri网模型，它们是用伴随矩阵L+和L-、初始标识M0、终止标识Mf和操作时间向量来描述的。3.4 应用Petri网验证Web服务组合分析Petri网可采

50、用可达树法、不变量分析、约简等方法，其中可达树分析法直观简捷，可方便地分析系统的可达性、有界性、活性等各种动态特性，Petri网的大部分特性可以由可到达树来进行验证。我们通过结合可到达树的构造和正确性的检查来实现流程模型的验证过程。可到达树的基本思想就是将可到达的标识作为节点，变迁的触发作为连接弧，来构造一棵树。我们的算法就是在构造树的过程中，检查服务组合的状态和其中库所的托肯数目以实现流程模型的验证。当服务组合时只关心系统可能的状态时，可达标识集可以满足这类问题的要求。给定Petri网中的一个标识M，该网络的可达标识表示为M。给定一个以M0 M0为初始标识的Petri网N，我们可以从M0 (

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

52、组合的正确性。定义3.4 可达性:若从初始标识M0出发触发一个变迁序列产生标识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网所有

53、的状态都是可达的。定义3.8前进性：每次触发都将逐步推向终态，可达树中不会出现无论的循环。同时具有上述5个性质的Petri网不会出现停滞不前的状态，执行中所处的状态及等待的消息是有限的，不会出现死锁。本文给出如下两个Web服务组合的正确性的分析。(1)组合服务S1S2的正确性分析下面通过对图3.4所示的组合服务S1S2的构造可达树，以分析该服务组合的正确性，可达树如图3.7所示。Mi=i，ready1，ready2，finished1，finished2，p，o图3.7 组合服务S1S2的可达树 该组合服务是完全可达的。从M0开始的状态可达集R(M0)= M0, M1 ,M2 , M3 , M

54、4 , M5 , M6。状态集MS= M0, M1 ,M2 , M3 , M4 , M5 , M6。因此，对任一个标记MiMS，均有MiR(M0)，即组合服务S1S2中任一个状态都是从M0可达。该组合服务具有界性。在可达树中，每一个位置上的托肯数从未超过1。因此该组合服务是安全的。该组合服务是活性的。从可达树可以看出，从M0开始，TiT(T是所有变迁的集合)都至少可以被从M0开始的激发序列激发一次。因此，该组合服务的Petri网是活性的。该组合服务具有完整性。由可达树可见，组合服务的所有状态都从M0可达并且可以激发转移到终止状态M6。该组合服务具有前进性。在可达树中，任意状态之间没有出现无意义

55、的循环。(2)组合服务S1CS2的正确性分析构造组合服务S1CS2的可达树如图3.8所示。Mi=i，ready1，ready2，finished1，finished2，m，o图3.8 组合服务S1C S2的可达树 组合服务是完全可达的。从M0开始的状态可达集R(M0)= M0, M1 ,M2 , M3 , M4 , M5 , M6, M7。状态集MS= M0, M1 ,M2 , M3 , M4 , M5 , M6, M7 。因此，对任一个标记MiMS，均有MiR(M0)，即组合服务S1CS2中任一个状态都是从M0可达。 该组合服务是有界的。在可达树中，每一个位置上的托肯数从未超过2。因此该组合

56、服务是有界的，其上界为2。 该组合服务是活性的。从可达树可以看出，从M0开始，TiT(T是所有变迁的集合)都至少可以被从M0开始的激发序列激发一次。因此，该组合服务的Petri网是活性的。 该组合服务具有完整性。由可达树可见，组合服务的所有状态都从M0可达并且可以激发转移到终止状态M7。 该组合服务具有前进性。在可达树中，任意状态之间没有出现无意义的循环。同理，对S1S2、S1S2及S的类似分析，可知，这些服务组合同时满足对可达性、有界性、活性、完整性和前进性的要求。第四章 基于Petri网的Web服务组合的实例分析4.1 Cygwin4.1.1 Cygwin概述Cygwin是一个在windo

57、ws平台上运行的类UNIX模拟环境，是cygnus Solutions公司开发的自由软件。它对于学习UNIX/Linux操作环境，或者从UNIX到Windows的应用程序移植，或者进行某些特殊的开发工作，尤其是使用GNU工具集在Windows上进行嵌入式系统开发，非常有用。Cygwin是许多软件的集合，最初由Cygnus Solutions开发，用于各种版本的Microsoft Windows上，运行UNIX类系统。Cygwin的主要目的是通过重新编译，将POSIX系统（例如Linux、BSD，以及其他Unix系统）上的软件移植到Windows上。Cygwin移植工作在Windows NT、Windows 2000、Windows XP以及Windows Server 2003上比较好，在Windows 95和Windows 98上，相对差劲一些。Cygwin由Red Hat等负责维护。Cygwin始于1