下载文档原格式
一种基于Web服务的工作流过程模型本文将介绍一种基于Web服务的工作流程模型，该模型集成了多种信息化技术，能够有效提高工作效率和质量，为企业提供了一种全新的数字化管理方式。
1. 引言随着信息技术的快速发展，企业管理方式也在发生着巨大的变革。
工作流程管理是其中一个重要领域，通过对企业内部各项工作流程的优化和整合，可以提高工作效率和质量，降低管理成本，并最终提升企业竞争力。
本文将介绍一种基于Web服务的工作流程模型，这种模型将多种信息化技术集成在一起，使得企业的工作流程管理更加便捷、高效和数字化。
2. Web服务的基础知识Web服务是一种通过网络连接的应用程序接口，提供了一种在不同平台和系统之间交换数据的标准方式。
Web服务通常通过HTTP协议进行通信，使用XML格式的数据进行数据交换。
每个Web服务都有唯一的服务描述文件，描述了服务如何被调用、输入和输出参数等信息。
Web服务通常使用SOAP （Simple Object Access Protocol）或REST（Representational State Transfer）作为通讯协议。
3. 工作流程模型的基础知识工作流程模型是描述工作流程的一种抽象方法，通常由一组关联的活动（也称为任务、步骤等）和它们之间的条件依赖关系组成。
工作流程模型可以用于描述各种复杂的工作流程，如企业内部的业务流程、文档审批流程等。
4. 基于Web服务的工作流程模型基于Web服务的工作流程模型是将Web服务和工作流程管理结合在一起的一种管理方式。
该模型的核心思想是将每个任务和活动转化为一个Web服务，并通过定义不同的服务调用顺序和参数，来描述整个工作流程。
4.1. 工作流程设计首先需要定义整个工作流程需要包含哪些任务和活动。
对于每个任务和活动，需要定义其输入、输出和执行方式。
然后，将每个任务和活动转化为一个Web服务，并将其发布到互联网上。
每个Web服务需要定义其服务描述文件，包括服务名称、服务类型、输入参数、输出参数、服务地址等信息。
一种基于泛化-特化关系模式的业务服务实例化方法
张鹏;王菁;赵小伟
【期刊名称】《计算机学报》
【年(卷),期】2008(31)8
【摘要】业务服务作为业务活动具体实现的一种抽象表示,在业务层上解决了业务用户可用及领域可复用的问题,然而,业务服务在落实到具体的物理服务时缺少一种规范化的实例化方法,因此,文中提出了一种基于泛化-特化关系模式的业务服务实例化方法.通过泛化-特化关系的判定,最终用户定制的表达个性化需求的业务服务能够发现它的邻近上界业务服务,并且基于泛化-特化关系模式的应用,业务服务只需要在它的邻近上界业务服务的公共实例集合中去匹配.实验表明,这种实例化方法能够很好地减少业务服务实例化中的冗余匹配,提高业务服务实例化的效率.
【总页数】12页(P1319-1330)
【作者】张鹏;王菁;赵小伟
【作者单位】山东科技大学信息科学与工程学院,山东青岛,266510;中国科学院计算技术研究所网格与服务计算研究中心,北京,100190;山东科技大学信息科学与工程学院,山东青岛,266510
【正文语种】中文
【中图分类】TP311
【相关文献】
1.一种利用继承关系的业务服务实例化方法 [J], 张鹏;韩燕波;王菁;陈旺虎;丁维龙;高晶
2.一种基于业务生成图的Web服务工作流构造方法 [J], 胡春华;吴敏;刘国平;徐德智
3.一种基于服务关系与效能的Web服务选择方法 [J], 荀鹏;简江涛;周丽涛
4.一种基于UML 2.0活动图的Web服务业务流程测试方法 [J], 宋朝云;张峻
5.一种基于微服务的检察业务服务封装方法 [J], 陆懿帆;曹芮浩;王俊丽;闫春钢因版权原因，仅展示原文概要，查看原文内容请购买。
web服务的工作流程
Web服务的工作流程。
Web服务是指通过网络进行交互的一种服务，它可以为用户提
供各种功能和信息。
它的工作流程通常包括以下几个步骤：
1. 客户端发送请求，用户在浏览器中输入网址或点击链接，客
户端（通常是浏览器）向服务器发送请求。
请求中包括了用户需要
的资源或服务的信息，比如网页、图片、视频等。
2. 服务器接收请求，服务器接收到客户端发送的请求后，开始
处理这个请求。
服务器通常会根据请求的内容和类型来确定如何处
理这个请求。
3. 处理请求，服务器根据请求的内容和类型，可能需要进行数
据库查询、数据处理、业务逻辑处理等操作，以生成需要的响应。
4. 生成响应，服务器处理完请求后，会生成一个包含所需资源
或服务的响应。
这个响应可能是一个网页、一段数据、一个文件等。
5. 发送响应，服务器将生成的响应发送给客户端，客户端接收到响应后进行解析和显示。
如果是网页，浏览器会根据响应的内容来渲染页面并呈现给用户。
6. 客户端显示响应，客户端接收到响应后，根据其内容进行显示。
用户可以在浏览器中看到所需的网页、图片、视频等。
整个流程中，涉及到了客户端和服务器之间的通信、请求的处理和响应的生成等环节。
通过这些步骤，Web服务可以为用户提供各种功能和信息，使得用户可以方便地获取所需的资源和服务。
这也是Web服务能够成为人们日常生活和工作中不可或缺的一部分的原因之一。
workflow-bpmn-modeler 详解
Workflow-BPMN-Modeler 是一个基于Web 的BPMN（Business Process Model and Notation，业务流程建模标准）建模工具，它允许用户通过图形化界面设计和编辑业务流程模型。
以下是Workflow-BPMN-Modeler 的一些详解：
1. 图形化建模：Workflow-BPMN-Modeler 提供了图形化的界面，用户可以通过拖拽、连接节点等方式创建和编辑业务流程模型。
这种图形化的建模方式使得用户可以直观地理解和设计复杂的业务流程。
2. 支持BPMN 标准：Workflow-BPMN-Modeler 遵循BPMN 标准，用户可以使用BPMN 中定义的各种符号、事件、网关、任务等元素来描述业务流程的各个环节和流转逻辑。
3. 可扩展性：Workflow-BPMN-Modeler 通常具有一定的可扩展性，用户可以根据自己的需求添加自定义的元素、属性或者扩展功能，以适应特定的业务场景。
4. 与工作流引擎集成：Workflow-BPMN-Modeler 通常可以与工作流引擎进行集成，用户可以通过建模工具设计的业务流程模型直接部署到工作流引擎中执行，实现业务流程的自动化执行和监控。
5. 多人协作：Workflow-BPMN-Modeler 通常支持多人协作，多个用户可以同时对同一个业务流程模型进行编辑和评论，以支持团队协作和建模过程中的沟通与交流。
总的来说，Workflow-BPMN-Modeler 是一个强大的工具，用于帮助用户设计、编辑和管理业务流程模型，它可以提高业务流程的可视化程度、可理解性和可执行性，是企业业务流程管理和自动化的重要工具之一。
基于工作流的Ｗｅｂ 服务组合综述 ０ 引言 近年来，随着分布式对象技术和基于ＸＭＬ 的Ｗｅｂ 服务技术的迅速发展，一种基于Ｗｅｂ服务的分布式计算模式正在成为互联网时代实现数据共享的有效手段。
Ｗｅｂ 服务是基于网络的、分布式的、自描述的、模块化的组件，它执行特定的任务，遵循一定的技术规范，提供了面向Ｉｎｔｅｒｎｅｔ 应用的统一服务注册、发现、绑定和集成机制，成为广域环境下实现互操作的一种主要机制，得到产业界和学术界的广泛认可。
然而单个的Ｗｅｂ 服务提供的功能有限，只有通过对已有的单个Ｗｅｂ 服务进行组合，其潜力才能发挥出来。
Ｗｅｂ 服务组合的目的是建立由相互合作的单独的服务组成的复杂的Ｗｅｂ 服务，实现更强大的功能，完成更复杂的任务。
为了实现数据和资源的共享，人们通过长期的研究发现，Ｗｅｂ 服务组合问题和工作流系统有着许多共同的特征：它们具有相同的生命周期，即组合流程建模阶段与流程运行阶段，在建模阶段均需要指定数据流和控制流，在运行阶段都由执行引擎负责解析流程定义并生成实例，通过调用外部应用或者服务进行执行。
工作流技术的最大优点是实现了应用逻辑和过程的分离，在过程逻辑的建立过程中可以不考虑应用和资源的异构性，但是没有解决分布式异构环境中资源的互操作问题，而Ｗｅｂ 服务恰好提供了对分布式异构资源的互操作能力；同时工作流技术提供了对服务运行的协调、监控和管理能力，为Ｗｅｂ 服务提供了一条可行、有效的路径。
因此，一种基于工作流的Ｗｅｂ 服务组合成为未来进行事务处理的发展趋势。
１ Ｗｅｂ 服务基本架构 从面向应用的角度描述了典型的Ｗｅｂ 服务组合的实现框架。
该架构由三种角色和三个基本操作构成。
三种角色分别是服务提供者、服务使用者和服务代理，而三个基本操作分别是注册、发现和绑定。
服务提供者创建服务，并将其发布到服务注册中心供使用者查找和使用。
当服务使用者需要完成特定的业务逻辑是就到服务注册中心去查询能够完成相应功能要求的Ｗｅｂ 服务，然后通过服务绑定直接与服务提供者通信，实现服务的调用，完成相应的事务。
一种基于W eb、Java和CORBA技术的工作流管理系统结构*鲍敢峰,朱鹏,尤晋元(上海交通大学计算机工程与科学系)摘要基于W eb的工作流管理系统受到商业界的广泛关注.但目前常用的W eb技术难以解决现代分布式应用中存在的诸多问题.本文提出的工作流管理系统结构综合利用了W eb、Java和CORBA技术,以W eb技术作为客户与服务器的通信基础,以Java进行Internet编程,以CORBA简化分布系统的设计,在Petri网模型的协调下,很好地实现了工作流管理..关键词工作流管理; W eb; Java;公共对象请求代理体系结构中图法分类号TP 311Architecture ofWorkflow ManagementSystemBased onWeb,Java and CORBA TechnologyBao Ganfeng,Zhu Peng,You JinyuanDepartment ofComputerScience& Engineering, Shanghai Jiaotong University, ChinaAbstract TheW eb-based workflow mangement systems received a lot of attention because of theirwide application in the commercial area. But currently adoptedW eb technology can not solve manyproblems in distributed application. The article puts forward a distributedworkflow management sys-tem architecture, which adoptsW eb technology as the communication infrastructure between clientand server, Java as the language to program in Internet,CORBA to simplify the complexity of dis- tributed systems. A workflow management system based on Petri netsmodel has been implemented.Ithas shown the effectiveness of the architecture.Key words workflow management; W eb; Java; common object request broker architecture (CORBA)随着网络的普及,计算机的主要用途转向支持组织或商务过程.最初,应用软件在操作系统之上开发,但随着应用规模的增大,应用软件通过数据库管理系统可避免过多涉及繁杂的数据管理工作.应用中往往包含大量工作流管理问题,例如:任务分配、工作调度和控制、人与资源的协调等.因而有必要引入工作流管理的概念,通过跟踪工作流的各种活动状态,自动地协调由人或应用软件完成的任务.工作流管理系统是通过软件管理和执行工作流的通用系统,俗称商务操作系统[1].其中过程的运行顺序取决于计算机中所存储的工作流逻辑.目前,基于W eb的分布工作流管理系统引起普遍的关注[2],其优点是以浏览器作为客户端软件,可减少对用户进行客户端软件的培训难度.但是随着应用的不断深入,W eb技术一些严重的缺点也暴露了出来.例如,W eb只适合处理静态客户,采用非类型安全(non-type safe)的交互,W eb服务器容易出现性能“瓶颈”,不适合复杂和大规模的应用等.结合W eb、Java和CORBA技术,本文提出了一种基于分布工作流管理系统结构.1W eb、Java和CORBA集成的工作流管理分布式计算环境CORBA(CommonObjectRequestBrokerArchitecture)是OMG发起和制订的分布式对象计算标准[3],其目的是在分布异构环境下实现信息和资源的共享.OMG采用OMA(ObjectMenagementAr-chitecture)以达到融合分布式处理和面向对象方法的目的,它提供了对象的创建、保持、定位和通信的标准方法,位于操作系统和支持RPC的通信传输层之上,是一种通用的对象模型.所有的对象请求都由对象代理(ORB)中转.请求者可以指定服务的提供者或交给ORB决定.所有的客户请求均遵守一种标准格式,因而增强了模块性并降低了模块间的耦合.CORBA有坚实的标准和规范作为后盾,适合于大规模混合式的网络分布系统,适合于企业应用,它为不同的语言提供了良好的互操作性,也为新型语言使用大量原有代码提供了一个解决方案.与其他分布对象计算环境相比,CORBA技术上也比较成熟.Java是一种与平台无关的安全的编程语言[4],可为W eb开发Applet.Applet是一种可在W eb 页面中运行的小型应用,其在下载后可与用户交互并在客户机上完成预定的任务. Java代码能以一种安全的方式在远程主机上运行,能有效地支持在W eb的网络环境上开发分布式应用.CORBA和Java技术从不同的角度克服了W eb的缺点,但是,单独使用CORBA或Java技术开发Internet上的分布应用还有不少问题.综合CORBA和Java的集成技术将能互相取长补短. Java 解决了CORBA缺乏Internet编程支持的缺点.CORBA为Java程序员提供了与实现无关的接口、访问用其他语言实现的对象能力、位置透明性(location transparency)、丰富的CORBAservices和CORBAfacili-ties等.综上所述,W eb、Java和CORBA集成的分布计算环境是解决工作流管理问题的一种很好方案.2工作流过程的Petri网模型工作流过程模型主要有两种:基于活动的模型和基于对话的模型[5],但这两种模型都不能显式地描述系统运行状态. Petri网模型能有效克服这一缺点,同时, Petri网是一种图形语言,能直观地反映并行、同步和共享等现象,适合描述具有并行行为或操作的系统.Petri网的另一特点是具有精确的语义和严格的数学基础,其理论结果十分丰富.Petri网[6]定义为四元组PN= (P,T,F,M0),其中:P为位置的非空有限集;T为变迁的非空有限集,且P∩T= ;F为边的非空有限集,F (P×T)∪(T×P);M0为初始标志.对x∈P∪T,它的前置集和后置集分别定义为·x= {y|y∈P∪T∧(y,x)∈F},x·= {y|y∈P∪T∧(x,y)∈F}.Petri网是一种可运行的图,用它指导工作流的实施显得十分自然.为了采用结构化的设计思想,需要从实际应用中提炼工作流的基本Petri网结构,这些基本Petri网结构具有对工作流管理应用充分的描述能力.工作流的Petri网模型是位置对应于条件(状态),变迁对应于工作项(任务).工作流过程模型由且仅由一些基本Petri网结构组成.工作流的基本Petri网结构应具备以下两个条件: (1)该结构具有唯一的输入和输出位置,即存在两个位置pin和pout,使得·pin= ,pout·= .其中输入位置中的标志代表未处理的工作项,输出位置中的标志代表处理过的工作项.(2)不存在多余的工作项和条件,即不允许悬空的位置和变迁.若增加变迁t′,使得·t′= {pout},t′·= {pin},则扩充后的Petri网中存在连接任意两结点的路径.以上两个条件只是基本Petri网结构的最小约束条件,实际运用中采用基本Petri网结构仍可能定义出具有诸如死锁等缺陷的模型.这需要通过对Petri网的分析加以解决.3基于W eb、Java和CORBA技术的工作流管理系统的结构3.1系统结构基于W eb、Java和CORBA技术的工作流系统结构由引擎、活动管理器、活动代理、过程定义和管理监视工具组成.活动是应用的运行实例,可由应用软件和人完成,系统通过活动代理与外界通信.工作流管理系统与活动代理的耦合是松散的,这样可减小对原有软件的修改或包装.活动管理器控制活动代活动管理器与引擎交互获取全局控制信息.任务或引擎可以是集中、分布或混合的.(1)集中结构.以进程启动引擎,引擎含多线程,每个线程对应于一个活动管理器.为增强系统的通用性,活动管理器根据活动的描述(前后条件等)通过CORBA接口激发活动代理,具体的系统结构见图1.(2)分布结构.每个分布结点(计算机或终端等)内含有一个引擎.引擎内包含管理内部活动的知识(即Petri网模型).结点内活动激发的依赖关系只能通过引擎与活动管理器交互解决,结点间活动激发的依赖关系通过引擎间的通信进行协调.各引擎含有工作流执行状态的信息,管理监视工具中存放所有结点工作流执行状态的信息.任何引擎均可从管理监视工具获取其他引擎的状态,或进行运行状态恢复.该结构反映了工作流应用本质的分布特征,避免了集中结构中可能出现的引擎“瓶颈”问题,并且某结点的故障不影响其他结点.3.2系统结构的实现结合Petri网模型,本文提出一种基于W eb、Java和CORBA技术的工作流管理系统结构的实现方案.Netscape同V isibroker合作在其4. 0及以上版本的浏览器中实现了JavaORB.客户机只需采用Netscape 4. 0及以上版本,不必安装其他特殊软件.客户活动代理(JavaApplet)通过http协议下载到客户浏览器.客户活动代理转移到客户端后,可以用CORBA定义的接口与CORBA服务器交互完成其任务(见图2).图1工作流系统的体系结构Fig. 1The architecture ofworkflowsystem图2工作流系统体系结构的一种实现Fig. 2An implementation of the architecture ofworkflowsystemPetri网是一种图形语言.为了便于存储,需要定义一种能有效地支持模型运行的文本描述语言.其定义分两部分:①描述Petri网的结构,支持工作流模型;②描述任务分配,支持工作流运行.这种分离的优点是任务分配的变化不影响Petri网过程模型,因而提高了过程的重用.Petri网的结构描述如下:place(placeName, tokenCount, time); transition(transitionName, event, condition); input(transition-Name, placeNamesList); output(transitionName, placeNamesList).任务分配的描述为: task-distribution(AgentName, transitionNameList).基于W eb、Java和CORBA技术的工作流管理引擎的控制机制分内外两种:(1)引擎内的控制机制.引擎中存储着运行状态,根据工作流的Petri网模型和运行状态能够确定可以激发的变迁,引擎调度函数可以依此激发活动管理器.活动结束后将影响状态,状态的变化又触发引擎调度函数.(2)引擎间的通信机制.引擎间的通信也可能导致状态的改变.引擎间通信的通信原语主要有set-WorkItem、getWorkItem、split和merge.接受到setWorkItem原语的结点将在工作流模型的某位置放置工作项(即标志);发送getWorkItem原语的结点向接受结点请求获取工作项.该实现方案中各引擎能处理不完整的模型,所有引擎中的模型组合后能构成一个完整的模型.为了进行动态配置,调节分布比例,引入split和merge原语.Merge原语把另一结点的工作流模型叠加进来,引入新的状态数据,并定义相关线程: split原语把本结点工作流模型的某些部分分配到另一结点上,撤消转移部分对应的线程或其他资源,并改变原结点的运行状态.引擎间通信原语用CORBA接口定义为:89第10期鲍敢峰,等:一种基于W eb、Java和CORBA技术的工作流管理系统结构能“瓶颈”,不适合复杂和大规模的应用等.结合W eb、Java和CORBA技术,本文提出了一种基于分布工作流管理系统结构.1W eb、Java和CORBA集成的工作流管理分布式计算环境CORBA(CommonObjectRequestBrokerArchitecture)是OMG发起和制订的分布式对象计算标准[3],其目的是在分布异构环境下实现信息和资源的共享.OMG采用OMA(ObjectMenagementAr-chitecture)以达到融合分布式处理和面向对象方法的目的,它提供了对象的创建、保持、定位和通信的标准方法,位于操作系统和支持RPC的通信传输层之上,是一种通用的对象模型.所有的对象请求都由对象代理(ORB)中转.请求者可以指定服务的提供者或交给ORB决定.所有的客户请求均遵守一种标准格式,因而增强了模块性并降低了模块间的耦合.CORBA有坚实的标准和规范作为后盾,适合于大规模混合式的网络分布系统,适合于企业应用,它为不同的语言提供了良好的互操作性,也为新型语言使用大量原有代码提供了一个解决方案.与其他分布对象计算环境相比,CORBA技术上也比较成熟.Java是一种与平台无关的安全的编程语言[4],可为W eb开发Applet.Applet是一种可在W eb 页面中运行的小型应用,其在下载后可与用户交互并在客户机上完成预定的任务. Java代码能以一种安全的方式在远程主机上运行,能有效地支持在W eb的网络环境上开发分布式应用.CORBA和Java技术从不同的角度克服了W eb的缺点,但是,单独使用CORBA或Java技术开发Internet上的分布应用还有不少问题.综合CORBA和Java的集成技术将能互相取长补短. Java 解决了CORBA缺乏Internet编程支持的缺点.CORBA为Java程序员提供了与实现无关的接口、访问用其他语言实现的对象能力、位置透明性(location transparency)、丰富的CORBAservices和CORBAfacili-ties等.综上所述,W eb、Java和CORBA集成的分布计算环境是解决工作流管理问题的一种很好方案.2工作流过程的Petri网模型工作流过程模型主要有两种:基于活动的模型和基于对话的模型[5],但这两种模型都不能显式地描述系统运行状态. Petri网模型能有效克服这一缺点,同时, Petri网是一种图形语言,能直观地反映并行、同步和共享等现象,适合描述具有并行行为或操作的系统.Petri网的另一特点是具有精确的语义和严格的数学基础,其理论结果十分丰富.Petri网[6]定义为四元组PN= (P,T,F,M0),其中:P为位置的非空有限集;T为变迁的非空有限集,且P∩T= ;F为边的非空有限集,F (P×T)∪(T×P);M0为初始标志.对x∈P∪T,它的前置集和后置集分别定义为·x= {y|y∈P∪T∧(y,x)∈F},x·= {y|y∈P∪T∧(x,y)∈F}.Petri网是一种可运行的图,用它指导工作流的实施显得十分自然.为了采用结构化的设计思想,需要从实际应用中提炼工作流的基本Petri网结构,这些基本Petri网结构具有对工作流管理应用充分的描述能力.工作流的Petri网模型是位置对应于条件(状态),变迁对应于工作项(任务).工作流过程模型由且仅由一些基本Petri网结构组成.工作流的基本Petri网结构应具备以下两个条件: (1)该结构具有唯一的输入和输出位置,即存在两个位置pin和pout,使得·pin= ,pout·= .其中输入位置中的标志代表未处理的工作项,输出位置中的标志代表处理过的工作项.(2)不存在多余的工作项和条件,即不允许悬空的位置和变迁.若增加变迁t′,使得·t′= {pout},t′·= {pin},则扩充后的Petri网中存在连接任意两结点的路径.以上两个条件只是基本Petri网结构的最小约束条件,实际运用中采用基本Petri网结构仍可能定义出具有诸如死锁等缺陷的模型.这需要通过对Petri网的分析加以解决.3基于W eb、Java和CORBA技术的工作流管理系统的结构3.1系统结构基于W eb、Java和CORBA技术的工作流系统结构由引擎、活动管理器、活动代理、过程定义和管理监视工具组成.活动是应用的运行实例,可由应用软件和人完成,系统通过活动代理与外界通信.工作流管理系统与活动代理的耦合是松散的,这样可减小对原有软件的修改或包装.活动管理器控制活动代88上海交通大学学报第32卷稿日期: 1998-06-08*“九五”国家科技项关项目资助(96-737-01-05)鲍敢峰:男, 1971年生,博士生,邮编: 200030一种基于W eb、Java和CORBA技术的工作流管理系统结构*鲍敢峰,朱鹏,尤晋元(上海交通大学计算机工程与科学系)摘要基于W eb的工作流管理系统受到商业界的广泛关注.但目前常用的W eb技术难以解决现代分布式应用中存在的诸多问题.本文提出的工作流管理系统结构综合利用了W eb、Java和CORBA技术,以W eb技术作为客户与服务器的通信基础,以Java进行Internet编程,以CORBA简化分布系统的设计,在Petri网模型的协调下,很好地实现了工作流管理..关键词工作流管理; W eb; Java;公共对象请求代理体系结构中图法分类号TP 311Architecture ofWorkflow ManagementSystemBased onWeb,Java and CORBA TechnologyBao Ganfeng,Zhu Peng,You JinyuanDepartment ofComputerScience& Engineering, Shanghai Jiaotong University, ChinaAbstract TheW eb-based workflow mangement systems received a lot of attention because of theirwide application in the commercial area. But currently adoptedW eb technology can not solve manyproblems in distributed application. The article puts forward a distributedworkflow management sys-tem architecture, which adoptsW eb technology as the communication infrastructure between clientand server, Java as the language to program in Internet,CORBA to simplify the complexity of dis- tributed systems. A workflow management system based on Petri netsmodel has been implemented.Ithas shown the effectiveness of the architecture.Key words workflow management; W eb; Java; common object request broker architecture (CORBA)随着网络的普及,计算机的主要用途转向支持组织或商务过程.最初,应用软件在操作系统之上开发,但随着应用规模的增大,应用软件通过数据库管理系统可避免过多涉及繁杂的数据管理工作.应用中往往包含大量工作流管理问题,例如:任务分配、工作调度和控制、人与资源的协调等.因而有必要引入工作流管理的概念,通过跟踪工作流的各种活动状态,自动地协调由人或应用软件完成的任务.工作流管理系统是通过软件管理和执行工作流的通用系统,俗称商务操作系统[1].其中过程的运行顺序取决于计算机中所存储的工作流逻辑.目前,基于W eb的分布工作流管理系统引起普遍的关注[2],其优点是以浏览器作为客户端软件,可减少对用户进行客户端软件的培训难度.但是随着应用的不断深入,W eb技术一些严重的缺点也暴露了出来.例如,W eb只适合处理静态客户,采用非类型安全(non-type safe)的交互,W eb服务器容易出aceNodeTalkPrim itive {∥The definition of data types…∥The definition of operationsboolean setW orkItem (in Place p, in Token work-item);boolean getW orkItem (in Token work-item);boolean split (in Nodem, in PetriNet net);booleanmerge (in PetriNet net);};boolean型返回值用以判断该原语是否成功地执行.上述原语的区别是: setWorkItem和getWorkItem原语只涉及结点间单个工作项的转移; split和merge原语处理部分工作流模型的转移.应该保证原语执行的原子性.4结语W eb、CORBA和Java技术从不同的角度提供了构造工作流管理系统的手段.这些技术各有优缺点,因此需要一种能综合这些技术的体系结构.结合W eb、Java和CORBA技术,本文提出一种分布工作流管理系统结构.该方案以W eb为构造工作流管理系统提供客户和服务器的通信基础,以Java构造可迁移的代理,以CORBA解决互操作等分布系统中的问题.同时,该系统结构克服了W eb技术的缺点,并很好地解决了分布系统的动态配置问题.参考文献1Sherth. Report from the NSF workshop on workflow and process automation in information system s. ACM SoftwEng Notes, 1997, 22(1): 28～382M iller JA, Sheth A P, KochutK J,et al. The future ofW eb-based workflows. http: //LSDIS. cs. uga. edu3ObjectM anagementG roup. The common object request broker: architecture and specification 2. 0. http: //www.omg. org4Naughton P. Java handbook. New York: M cG raw-Hill, Inc, 1996.5GeorgakopoulosD, HornickM. An overview ofworkflow management: from processmodeling toworkflow automa-tion in frastructure. Distributed and ParallelDatabase, 1995, 3: 119～1536ReisigW. Perti nets: an introduction. New York: Springer-Verlag, 1985.下期发表论文摘要预报对称正交铺层剪切圆柱壳在外压作用下的屈曲和后屈曲张建武,束永平,李奇(上海交通大学机械工程学院)摘要给出了对称正交铺层剪切圆柱壳广义大挠度Donnell方程.采用位移型摄动技术构造出计及横向剪切圆柱壳的屈曲和后屈曲渐近级数解,运用奇异摄动技术研究了圆柱壳两端部狭窄区内的边界层效应,并构造了与边界条件匹配的边界层一致有效渐近解.应用获得的当前解计算了在侧向外压作用下三层正交铺设圆柱壳的屈曲载荷并与实验值作了比较,两者十分接近.讨论了Batdorf数和初始几何缺陷对圆柱壳屈曲与后屈曲性态的影响。
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.18, No.8, August 2007, pp.1870−1882 DOI: 10.1360/jos181870 Tel/Fax: +86-10-62562563© 2007 by Journal of Software. All rights reserved.∗一种基于业务生成图的Web服务工作流构造方法胡春华1,2+, 吴敏1, 刘国平1,3, 徐德智11(中南大学信息科学与工程学院,湖南长沙 410083)2(湖南商学院计算机与电子工程系,湖南长沙 410205)3(School of Electronics, University of Glamorgan, Pontypridd CF37 1DL, UK)An Approach to Constructing Web Service Workflow Based on Business Spanning GraphHU Chun-Hua1,2+, WU Min1, LIU Guo-Ping1,3, XU De-Zhi11(School of Information Science and Engineering, Central South University, Changsha 410083, China)2(Department of Computer and Electronic Engineering, Hu’nan Business College, Changsha 410205, China)3(School of Electronics, University of Glamorgan, Pontypridd CF37 1DL, UK)+ Corresponding author: Phn: +86-731-8832649, Fax: +86-731-8689238, E-mail: huchunhua777@, Hu CH, Wu M, Liu GP, Xu DZ. An approach to constructing Web service workflow based on businessspanning graph. Journal of Software, 2007,18(8):1870−1882. /1000-9825/18/1870.htmAbstract: Based on the fact that Web service dynamically changes and rapidly increases in the Internet, auser-oriented service workflow constructing model is proposed. The same or similar function services areaccumulated into a kind of service set in this model, which is organized by the spanning tree, and the businessspanning graph is formed according to workflow’s business logic relation. At the same time, on the basis ofredefining the position, velocity, addition, subtraction and multiplication of particle swarm algorithm, combiningwith the cross and mutation operations in genetic algorithm, the QoS (quality of service)scheduling algorithm basedon hybrid particle swarm optimization algorithm (HPSOA) is designed to satisfy different multi-QoS demands whenWeb service rapidly increases. Experimental results demonstrate that the constructing model could effectively shieldthe physical varieties and differences of Web service, and preferably combine the Web service resource in theInternet. It is suitable for the application demands in the virtual computing environment.Key words: Web service; workflow; business spanning graph; QoS (quality of service) scheduling; HPSOA (hybridparticle swarm optimization algorithm)摘要: 针对互联网中Web服务具有动态变化且迅速增长的特点,提出了一种面向用户需求的服务工作流构造模型.该模型将功能相同或相似的服务聚集成一类服务集合,每类服务集合采用生成树的方式组织,并依据工作流的业务逻辑关系形成业务生成图;同时,在重定义粒子群算法的位置、速度、加/减法和乘法的基础上,结合遗传算法中的∗Supported by the National Natural Science Foundation of China under Grant No.60674016 (国家自然科学基金); the NationalHigh-Tech Research and Development Plan of China under Grant No.2006AA04Z172 (国家高技术研究发展计划(863)); the NationalScience Fund for Distinguished Young Scholars of China under Grant No.60425310 (国家杰出青年科学基金); the Natural ScienceFoundation of Hu’nan Province of China under Grant No.05JJ40118 (湖南省自然科学基金)Received 2007-02-28; Accepted 2007-04-26胡春华等:一种基于业务生成图的Web服务工作流构造方法1871交叉、变异操作,设计了基于混合粒子群的QoS(quality of service)调度方法,保证在可选服务不断增长时能够满足用户的个性化需求.实验结果表明,该模型能够有效地屏蔽组成工作流的Web服务物理上的变化与差异,较好地组合了Internet中的Web服务资源,适合于虚拟计算环境的应用要求.关键词: Web服务;工作流;业务生成图;QoS(quality of service)调度;混合粒子群算法中图法分类号: TP311文献标识码: AWeb服务技术通过采用WSDL,UDDI和SOAP等基于XML的标准和协议,解决了异构分布式计算以及代码与数据重用等问题,具有高度的互操作性、跨平台性和松耦合的特点[1].但在实际应用中,单项Web服务一般仅提供某些单一功能,通常无法满足复杂的应用需求.因此,将单一Web服务组合成功能更强大的服务以满足不同用户的应用需求已成为一个新的研究热点.Web服务工作流(又称为服务组合)是实现互联网中服务资源协同工作的一个重要手段,将多项服务组装成一个具有更大粒度的增值服务或系统,满足上层的应用访问或其他需要[2].服务工作流是一种半自动服务组合方式,首先要由用户根据需求建立适合具体应用需求的工作流业务逻辑模型.该模型由多个服务节点组成,各服务节点包含具体的功能需求描述[3].开放的互联网环境中同时存在着数量众多、功能相同或相近、服务质量(quality of service,简称QoS)等非功能特性各异的服务.如何从这些异常丰富且动态变化的Web服务中选择满足各服务节点功能需求的具体服务,形成一个切实可行的工作流实例来完成用户的个性化需求,成为服务工作流研究的关键问题.本文称其为服务工作流路径选择问题.对该问题的研究主要包括两个方面:1) 从功能需求的角度在不断变化的Web服务中找出符合要求的Web服务集;2) 功能相同或相似的Web服务其服务质量差异很大,需要从符合要求的服务集中找出满足用户QoS需求的服务实例.目前,使用工作流作为一个分布式活动的协调引擎,或作为一个服务合成建模和定义的工具对Web服务进行组合的研究已有不少.其中,Cross-Flow[4]和Sword[5]等研究项目致力于为企业提供一个动态的服务查找、发现与运行时动态绑定的服务合成平台,通过WSFL,LANG与BPEL4WS等服务合成语言为服务组合提供了一个统一建模和定义的工具.SciDAC-SDM项目[6,7]将用业务术语描述的抽象工作流与底层的由服务组成的执行工作流严格加以区分,并借用与数据库协调技术相类似的方法将抽象工作流转换成执行工作流.文献[8]利用事务的概念扩展了DAML-S本体中的过程模型,并提出了一个事务工作流本体概念的服务组织模型(transaction workflow ontology,简称TWFO).在以上这些研究中,从工作流业务领域到服务环境的映射只能进行静态的转换,不能根据服务的实时QoS状况,在执行时选取令用户满意的服务实例.eFlow[9]等服务工作流系统对组合服务的选择过程采用基于QoS局部最优的调度方法.这些方法中,各服务节点对应的具体Web服务实例选择是相互独立的,并不能解决服务工作流的QoS全局优化问题.文献[10,11]将服务的多个QoS约束参数通过线性加权转化为一个单目标函数,利用线性规划的基本原理来解决服务选择的QoS全局最优化调度问题.文献[2,3]利用遗传算法等非线性优化的仿生算法求解QoS全局最优化调度问题,取得的效果不错.但这些研究存在两点不足:1) 未能将Web服务的QoS全局最优化调度求解与服务动态变化的实际结合起来;2) 当网络中可选的Web服务迅速增加时,QoS调度的时间收敛性很难满足用户的实时性需求.针对以上问题,本文在课题组前期工作的基础上[12]提出了一种基于业务生成图的工作流构造模型.该模型聚集了多个功能相同或者相似的Web服务集合,每个服务集合采用生成树的方式进行组织,并依据工作流间的“上下游”逻辑关系组成业务工作流图;同时,用户可以依据自身的个性化需求对业务逻辑进行裁剪与限定、形成个性化定制模型;最后通过设计基于混合粒子群的QoS调度算法,消除互联网中可选服务迅速增加的影响,找出满足应用需求的工作流执行路径.实验与理论分析表明:该模型能够对动态的Web服务进行有效组合,对工作流执行路径的查找具有良好的时间收敛性,适合于虚拟计算环境的应用要求.1 服务定义及逻辑工作流模型描述本节首先给出Web服务和用户逻辑工作流结构的严格定义,而用户逻辑工作流定义后的实际运行是将其1872 Journal of Software 软件学报 V ol.18, No.8, August 2007映射到实际网络和服务实例的执行过程,因此在第2节中给出基于业务生成图的工作流构造模型组织结构,最后在第3节给出基于QoS 的工作流调度算法.工作流由一系列Web 服务的调用来完成,下面首先给出Web 服务的定义.定义1. Web 服务(WS)可以定义为一个三元组:WS =(D ,F ,Q ).1) D 是服务的基本定义与描述,即服务ID 、服务名称、服务的商业实体以及服务的文本描述;2) F 是服务功能描述,包括服务的接口参数Parameter 、前置条件Precondition 和后置条件PostCondition;3) Q 是对服务非功能属性的描述.它的质量模型可以定义为QoS (WS )={QoS (tim ),QoS (cos ),QoS (cap ),QoS (ava ),QoS (rep )},其中,QoS (tim )为所用的时间,QoS (cos )为所需的费用,QoS (cap )为计算能力,QoS (ava )表示服务的可用性,QoS (rep )表示服务的声誉度.对于QoS 可能有不同的定义,但不影响本文的主要结论,而且目前的大多数Web 服务描述语言都自发地遵循(D ,F ,Q ),比如OWL-S 等.定义2. 工作流业务逻辑模型(workflow business logic model,简称WBLM)是指组成工作流的各类服务相互关联而形成的逻辑结构图.需要指出的是,模型中的服务是指一种服务类型,而不是具体的服务实例,属于此类型的服务实例均可以完成此类型所代表的活动.图1所示为某工作流实例. Start W 6: W 1Control link End W 3⊕TrueFalse ?∝ W 2True False W 4 W 5True True ≡:Fig.1 A workflow business logic model图1 工作流业务逻辑模型工作流业务逻辑模型描述为WBLM =(MODELS ,CL ,DD ),其中:1) MODELS ={W 1,W 2,…,W n }为服务类型的集合,其中,W 1,…,W n 表示工作流的n 个参与服务类型;2) CL ⊆MODELS ×MODELS ×ϕ为控制连接(control link)的集合.对于〈W i ,W j ,ϕ〉∈CL ,控制结构运算符ϕ定义为从W i 到W j 的控制转换关系.基本服务通过若干控制结构可组合成服务工作流.工作流使用的控制结构运算符依据BPEL(businessprocess executable language)的定义共有5个,分别用sequence,switch,while,flow 和pick 来表示顺序、选择、循环、并行及事件选择这些逻辑关系.3) DD ⊆W ×W ×ψ为数据依赖(data dependency)的集合.对于〈W i ,W j ,ψ〉∈DD ,数据依赖函数ψ定义为从W j .input到W i .output 的函数依赖关系,并称W j 关于ψ数据依赖于W i ,记作W i ψW j .目前,支持对服务流程进行描述和定义的协议标准包括BPEL4WS,BPML 和OWL-S 等,它们的目标是将服务流程定义和具体的服务实现相分离,但本身并不具备依据多样化、个性化和动态业务需求匹配服务的功能[1].本文采用BPEL4WS 来描述工作流业务逻辑模型,主要基于如下两方面原因:(1) 它遵循了通用的标准,采用标准的XML 语言,能为其他系统所用;(2) 以其为基础,具体的个性化定制在调度模型中实现,以弥补其个性化定制能力较弱的不足.2 基于业务生成图的工作流模型构造本节主要论述基于业务生成图的工作流模型构造.服务工作流组成部分中有关QoS 调度策略是本文研究的重点,在第3节中单独加以论述.2.1 业务生成图的形成场景下面给出Web 服务组织模型的几个基本定义.胡春华等:一种基于业务生成图的Web服务工作流构造方法1873定义3. 服务可替代关系:若某应用能在服务WS i上满足性能要求,又能在服务WS j上得到性能满足,则称服务WS i可替代服务WS j,记为Sim(WS i,WS j).目前,相似服务的匹配大多采用基于本体的语义匹配方法.定义4. Web服务生成树(Web services spanning tree,简称WSST)是一类性能相同或者相似Web服务的有效集合.一棵服务生成树用无权无向图来表示,即G=(V,E),其中,V=n,是树中服务节点数,节点能提供功能相同的服务;E=m,即树的边数.对于服务生成树WSST k的任意两服务(WS i,WS j),都有Sim(WS i,WS j).定义5. Web业务生成图(Web business spanning graph,简称WBSP)是依据工作流的业务逻辑关系,由多棵生成树组合成的图,可以用G=(T,E)表示,其中,T=WSST(Web服务生成树的集合),是生成图中构成工作流的各个Web服务生成树;E=〈T i,T j〉,即生成图中两棵生成树之间依据接口和业务逻辑的流程关系形成的边,T i树中服务的输出是T j树中服务的输入,即在工作流路径中,T i服务的“下游”是T j.互联网中服务资源异常丰富,同时存在大量的功能相同或相近的服务.根据Web服务在网络中发布的信息,可以采用文献[10,13]提供的策略对其属性进行计算,将某类功能相同(相似)的服务找出,限于篇幅,本文不再赘述;然后组织网络中某类相同(相似)服务Sim(WS i,WS j)形成一棵生成树,每一棵树设定一个令牌节点[14]来负责树中所有信息的维护.如网络中产生新的服务后,也可以通过如下的简单策略申请加入到服务生成树(WSST)中: Step 1. 服务提供者以服务的参数向SRS发出加入申请报文(Join_Probe),申请加入WSST.Step 2.SRS接收到申请报文(Join_Probe)后,根据服务的统一编址方法确定此服务所属的权威负责解析SRS节点,此SRS在表中查找此服务所属的WSST的地址,返回给申请服务加入者(joiner)相关WSST中的服务节点地址,或者是此类服务还没有服务注册.Step 3. 如果joiner得到的是WSST地址,则继续Step 4;否则,他自己成为此类WSST的第1个节点,也是令牌节点,则加入过程结束.Step 4.joiner向WSST连接加入,它首先发出报文(还是Join_Probe),当WSST中某节点v接收到探测加入报文Join_Probe时,则返回给发起者肯定应答报文(Ack_For_Probe),表示通过此节点加入到WSST中.Step 5.WSST中的节点接收了新服务的加入,接收节点v向此类树中拥有令牌的节点发起通告报文,表示树中增加了一个服务.Step 6. 在与树内节点的交互过程中,将树内邻居节点Semi-adjacent项以及QoS相关项填充.Step 7. 令牌的节点在下一次广播报文中通告树中所有节点.业务生成图的形成需要在工作流语义环境下进行.基本思想是,在工作流业务逻辑的支持下,工作流起始服务对应的生成树发起业务生成图的形成请求,它首先依据工作流的语义关系得知其“下游”的服务类,然后向SRS查询得到其“下游”的生成树地址,进而将“下游”服务联系起来.经过反复的查询与连接过程,从而形成业务生成图,具体构造业务生成图的算法如下:算法1. 业务生成图的构造算法.Step 1. 工作流起始服务通过工作流模式得知“下游”服务的参数,以此向SRS发出查询此服务的查询申请报文(Query_Probe).Step 2. SRS接收到查询申请报文(Query_Probe)后,根据服务的统一编址方法确定此服务所属的权威负责解析SRS节点,此节点在表中查找该服务所属的WSST地址,返回给查询服务者WSST中的服务节点地址;或者是空,表示还没有此服务.Step 3. 如果发起者得到的是WSST地址,则继续Step 4;否则,过程结束.Step 4. 发起者向WSST连接加入,它首先发出报文(还是Join_Probe),当WSST中某节点v接收到探测加入报文Join_Probe时;向令牌节点转发,由令牌节点返回给发起者肯定应答报文(Ack_For_Probe).Step 5. 发起者根据得到的信息填充如下几个字段信息:next-adjacent;link-band[],int link-capac[].这时,“上下游”关系已经建立.Step 6. 新加入WSST中的令牌节点接收上游传过来的工作流模式,决定是否继续重复以上步骤,直至工作流关系建立.1874 Journal of Software软件学报 V ol.18, No.8, August 20072.2 业务生成图的工作流模型服务工作流构造模型(service workflow constructing model,简称SWCM)如图2所示,由两个有机部分组成:服务注册系统(service registrations system,简称SRS,见图2左上)和Web服务工作流生成图(service workflowspanning graph,简称SWSG,见图2中右).User Relay requestto SPTLogic workflowFig.2 An availability model of Web service workflow图2 服务工作流可用性模型1) 服务注册系统(SRS):主要起到索引服务作用,类似于DNS系统,存储的是某类服务对应的服务生成树地址.与文献[15]中提出的主动分布式Web服务注册系统的区别是:在文献[15]中主要是利用与DNS类似的服务注册系统(SRS),服务提供者直接向SRS注册.由于本文采用生成图的方式来组织工作流所对应的服务,因此在服务的组织上,并不需要每一个服务提供者直接向SRS注册,而是对于一棵生成树而言,选中其中一个作为令牌节点,由其来负责整棵树与SRS的服务信息维护,这样,对于广域网中的一类服务只需要一个节点与SRS交互,大幅度减少了SRS中服务信息维护的负载压力,而且避免了由于服务的动态产生,直接注册方法产生的系统维护与通信压力过大的问题.2) Web服务工作流生成图:组织网络中某类相同或相似服务Sim(WS i,WS j)形成一棵生成树,设定一个令牌节点来负责树中所有信息的维护.为了保持生成树的鲁棒性,对令牌节点采用冗余策略;同时,使令牌节点与SRS间存在定时的交互动作TTL(time to live),目的是让SRS知道树还“活着”,它由令牌节点在TTL交互时将树内信息报告给SRS;同时,依据工作流业务逻辑关系,将服务间的“上下游”对应的生成树之间关联起来(图2中的灰色箭头边所示),形成服务工作流生成图.图2中右侧所示的用户逻辑工作流到实际服务工作流路的映射由本文的QoS调度算法来完成,而逻辑工作流的描述用上一节的定义2来实现.整个工作流交互过程如图2所示.首先,用户向服务注册系统(SRS)发起服务工作流请求,SRS接收到请求后,依据用户XML描述(见第3.3节)的工作流起始服务类型转发到对应的服务生成树,再依据第4节提出的混合粒子群调度算法依次遍历业务生成图,返回给用户一条最佳的工作流执行路径,执行工作流;如果未找到合适的路径,则用户可以降低QoS级别与服务生成树进行QoS协商,再进行查找,直到协商成功或者失败为止.采用业务生成图的原因有以下几点:(1) 采用生成树来保持动态信息维护,能够有效减少服务直接与SRS 交互所带来的负载压力,虽然内部服务动态性很大,从而使系统的稳定性大大提高;(2) 可通过生成树中节点的个数表示提供此类服务的数目;(3) 组织成生成树后,工作流逻辑到服务实例的映射变得方便且迅速,只需查询SRS中生成树的地址,就能找到实际的服务集合;(4) 生成树是一种分布式且自我维护的组织结构,只要存在类似的服务就不会出现因服务动态变化而使服务工作流不可用的现象.2.3 工作流个性化定制个性化定制模型是提供给用户一种定制个性化工作流的方法,采用XML语言来定制个性化的工作流.这是胡春华等:一种基于业务生成图的Web服务工作流构造方法1875一种普遍采用的方法,如WSFLOW.它主要包含3个方面的定制工作,在XML中可以采用3个节来表示,分别是业务模式定制、执行模式定制、QoS参数定制.1) 业务模式定制是指对业务逻辑模式进行裁剪.在采用XML描述时,首先描述控制符(在service-control 节中),然后描述服务类(在service-model节中),这时,可以对业务逻辑进行定制.其中,defaultmodel表示服务类型,如果有多个业务逻辑流程,则可以用allow为真或者假来选择或不选择此业务流程.2) 执行模式定制是指对服务类到服务实例映射关系的定制与限定.在〈instance〉节中描述,用〈allow instance=“*”/〉表示可以映射到任意的服务实例(即服务提供商),用〈deny instance=“.”/〉表示不能映射的服务实例,如工作流不希望经过某些特定区域,则在此描述.3) QoS参数定制是指对映射的服务实例,如定义1中所定义的其他非功能性QoS属性的限定,表示将来调度时选择的服务实例必须满足的QoS要求,在〈QoS〉节表示,如用〈time<10/〉表示要求将来选择的服务实例的执行时间小于10.另外,在全局定制节部分〈globalization〉也可以定义整个工作流的QoS要求,用户还可以定制对不同QoS的偏向性,这是在〈Weight〉节中,对不同的QoS指标设置不同的权重来表示的.下面给出采用XML定制的例子.〈service-control〉〈!--定义业务逻辑的控制符--〉〈mode=“flow”/〉〈!--定制服务类部分--〉〈service-model〉〈defaultmodel=“A”/〉〈!--服务模式为A类服务--〉〈allow=“true”/〉〈!--允许此服务模式--〉〈instance〉〈!--对服务实例的定制部分--〉〈allow instance=“*”/〉〈!--允许映射的服务实例(服务提供商)--〉〈deny instance=“.”/〉〈!--不允许映射的服务实例--〉〈/instance〉〈QoS〉… 〈!--对QoS参数的定制部分--〉〈/QoS〉/service-model〉… 〈!--定制其他服务类部分--〉/service-control〉… 〈!--其他定制部分--〉〈globalization〉〈!--工作流全局定制部分--〉〈QoS〉〈!--对全局QoS参数的定制部分--〉〈time<110/〉〈!--工作流总的执行时间小于110--〉〈price<350/〉〈!--工作流总的执行费用小于350--〉〈capacity<75/〉〈!--工作流总的计算能力大于75--〉〈availability<0.7/〉〈!--工作流总的可靠性大于0.7--〉〈reputation<80/〉〈!--工作流总的信誉大于80--〉〈/QoS〉〈Weight〉〈!--对不同QoS指标的权重定制--〉〈W time=0.3/〉〈!--工作流执行时间权重为0.3--〉〈W price=0.2/〉〈!--工作流执行费用权重为0.2--〉〈/weight〉… 〈!--对其他全局定制部分--〉1876 Journal of Software 软件学报 V ol.18, No.8, August 2007由上例可知:用户对工作流服务质量的要求为tim <110,pri <350,cap >75,ava >0.7,rep >80.3 基于混合粒子群算法的QoS 调度互联网中同时存在大量功能相同(相近)、服务质量(QoS)各异的Web 服务,经过如图2所示的服务组织模型,可以将功能相同(相近)的服务进行有效组织,完成用户所需要的基本功能;但功能相同(相近)的Web 服务,其QoS 相差很大,如何从中找出“最佳”QoS 的服务实例来构造服务工作流满足用户的需求,将是本节需要解决的问题.QoS 调度实际上就是依据用户个性化定制的工作流,在业务生成图内,从服务质量各异的服务候选中选取“最佳”QoS 服务实例的过程,也即服务工作流中“最佳”执行路径的形成过程.3.1 混合粒子群算法随着Internet 中Web 服务的迅猛增长,服务注册系统中心(SRS)和服务生成树的可选服务都将迅速增加.对于QoS 调度,穷举法因候选服务众多已难以满足需要,遗传算法同样也显得力不从心.例如,图1所示的某服务工作流系统,6个服务类(W 1,W 2,...,W 6)中,若每个服务类有10个候选服务,则穷举法的搜索空间为106,穷举法显然不再适合,遗传算法的时间收敛性不强的弱点也逐渐显现出来.这种非线性组合的优化问题是一类NP 难问题,而粒子群算法(PSOA)在多目标优化中已广泛应用,且收敛性强,所以,本文利用粒子群算法对构造模型进行QoS 调度,以满足用户的相关要求.粒子群算法[16]首先由Kennedy 和Eberhart 于1995年提出,是一种基于迭代的进化计算方法,其本质是利用本身信息、局部较优信息和全局较优信息来指导粒子下一步迭代的位置.对于求解“最佳”QoS 路径问题,其当前位置是基本路径,若按基本粒子群算法,其速度难以表达.因此,通过重定义粒子群算法中的位置、速度、加、减和乘法操作,并将遗传算法的交叉、变异思想引入粒子群算法中,形成混合粒子群算法(hybrid particle swarmoptimization algorithm,简称HPSOA)进行求解.在每次迭代中,既考虑粒子群算法的本身信息、局部较优信息和全局较优信息,又进行类似于遗传算法中的交叉、变异操作,以获得“最佳”QoS 执行路径.下面给出重新定义后混合粒子算法的速度与位置操作符.设12{,,...,}m m m n X x x x =表示服务工作流路径的一个解,其中,m 为某生成树中Web 服务个数,n 为网络中生成 树的棵数.将SRS 中各点按从左到右、从上到下的顺序自然排序,然后按此顺序将每个待选点作为数组的一个元素,当元素x i 为1时,表示相应的点被选入该条路径中;否则,该点不在该条路径中.粒子位置的重新定义:X =(x 1,x 2,…,x m ) (1) 这里,粒子位置X 表示问题的一个解,包括m 个元素,每个元素的取值有两个:0和1,1表示相应的点被选入该条路径中,0则相反.例如,X (1,0,0,1,0,1,0,1)表示一条经过第1,4,6,8个节点的路径.粒子速度的重新定义:V =(v 1,v 2,…,v m ) (2)粒子速度V 表示路径的改进方向,即根据速度提示的位置和元素对原来路径进行替换,其元素取值有3个:−1,0,1.−1指示要替换的链路的起始位置和结束位置,0和1表示新的路径选择的点.例如:V (0,0,−1,0,1,0,−1,0)表示原路径中从第3个点到第7个点间的链路进行替换,因为第3个元素和第7个元素的值为−1,3和7分别表示要替换路径的起点位置和结束位置.第4,5,6个元素的值表示新的路径把原来的路径中相应的一段链路替换为经过第5个点的路径(第5个元素为1).“加法”(⊕)的重新定义:A ⊕B ,假设B 中第i 个元素和第j 个元素为−1,则把A 中第i +1到第j −1的元素替换为B 中相应位置的数值.例如,有X (1,1,1,1,1,1,0,1)和V (0,0,−1,0,1,0,−1,0),这样,X ⊕V =(1,1,1,0,1,0,0,1).“加法”实际上是实现了遗传算法中的“交叉”操作,把原路径的一段链路替换成新的链路,而替换的方向是由局部较优信息和全局较优信息指导的.“减法”()的重新定义:A B ,把A 和B 中数值相同的那个位置标记为−1,如果有多个−1,随机选取两个,结果只保留两个−1,两个−1间的数值为A 相应位置的数值,其他位置为0.如有X e e 1(1,0,0,1,0,1,0,0)和X 2(1,1,1,0,1,1,0,0),。
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.18, No.8, August 2007, pp.1870−1882 DOI: 10.1360/jos181870 Tel/Fax: +86-10-62562563© 2007 by Journal of Software. All rights reserved.∗一种基于业务生成图的Web服务工作流构造方法胡春华1,2+, 吴敏1, 刘国平1,3, 徐德智11(中南大学信息科学与工程学院,湖南长沙 410083)2(湖南商学院计算机与电子工程系,湖南长沙 410205)3(School of Electronics, University of Glamorgan, Pontypridd CF37 1DL, UK)An Approach to Constructing Web Service Workflow Based on Business Spanning GraphHU Chun-Hua1,2+, WU Min1, LIU Guo-Ping1,3, XU De-Zhi11(School of Information Science and Engineering, Central South University, Changsha 410083, China)2(Department of Computer and Electronic Engineering, Hu’nan Business College, Changsha 410205, China)3(School of Electronics, University of Glamorgan, Pontypridd CF37 1DL, UK)+ Corresponding author: Phn: +86-731-8832649, Fax: +86-731-8689238, E-mail: huchunhua777@, Hu CH, Wu M, Liu GP, Xu DZ. An approach to constructing Web service workflow based on businessspanning graph. Journal of Software, 2007,18(8):1870−1882. /1000-9825/18/1870.htmAbstract: Based on the fact that Web service dynamically changes and rapidly increases in the Internet, auser-oriented service workflow constructing model is proposed. The same or similar function services areaccumulated into a kind of service set in this model, which is organized by the spanning tree, and the businessspanning graph is formed according to workflow’s business logic relation. At the same time, on the basis ofredefining the position, velocity, addition, subtraction and multiplication of particle swarm algorithm, combiningwith the cross and mutation operations in genetic algorithm, the QoS (quality of service)scheduling algorithm basedon hybrid particle swarm optimization algorithm (HPSOA) is designed to satisfy different multi-QoS demands whenWeb service rapidly increases. Experimental results demonstrate that the constructing model could effectively shieldthe physical varieties and differences of Web service, and preferably combine the Web service resource in theInternet. It is suitable for the application demands in the virtual computing environment.Key words: Web service; workflow; business spanning graph; QoS (quality of service) scheduling; HPSOA (hybridparticle swarm optimization algorithm)摘要: 针对互联网中Web服务具有动态变化且迅速增长的特点,提出了一种面向用户需求的服务工作流构造模型.该模型将功能相同或相似的服务聚集成一类服务集合,每类服务集合采用生成树的方式组织,并依据工作流的业务逻辑关系形成业务生成图;同时,在重定义粒子群算法的位置、速度、加/减法和乘法的基础上,结合遗传算法中的∗Supported by the National Natural Science Foundation of China under Grant No.60674016 (国家自然科学基金); the NationalHigh-Tech Research and Development Plan of China under Grant No.2006AA04Z172 (国家高技术研究发展计划(863)); the NationalScience Fund for Distinguished Young Scholars of China under Grant No.60425310 (国家杰出青年科学基金); the Natural ScienceFoundation of Hu’nan Province of China under Grant No.05JJ40118 (湖南省自然科学基金)Received 2007-02-28; Accepted 2007-04-26胡春华等:一种基于业务生成图的Web服务工作流构造方法1871交叉、变异操作,设计了基于混合粒子群的QoS(quality of service)调度方法,保证在可选服务不断增长时能够满足用户的个性化需求.实验结果表明,该模型能够有效地屏蔽组成工作流的Web服务物理上的变化与差异,较好地组合了Internet中的Web服务资源,适合于虚拟计算环境的应用要求.关键词: Web服务;工作流;业务生成图;QoS(quality of service)调度;混合粒子群算法中图法分类号: TP311文献标识码: AWeb服务技术通过采用WSDL,UDDI和SOAP等基于XML的标准和协议,解决了异构分布式计算以及代码与数据重用等问题,具有高度的互操作性、跨平台性和松耦合的特点[1].但在实际应用中,单项Web服务一般仅提供某些单一功能,通常无法满足复杂的应用需求.因此,将单一Web服务组合成功能更强大的服务以满足不同用户的应用需求已成为一个新的研究热点.Web服务工作流(又称为服务组合)是实现互联网中服务资源协同工作的一个重要手段,将多项服务组装成一个具有更大粒度的增值服务或系统,满足上层的应用访问或其他需要[2].服务工作流是一种半自动服务组合方式,首先要由用户根据需求建立适合具体应用需求的工作流业务逻辑模型.该模型由多个服务节点组成,各服务节点包含具体的功能需求描述[3].开放的互联网环境中同时存在着数量众多、功能相同或相近、服务质量(quality of service,简称QoS)等非功能特性各异的服务.如何从这些异常丰富且动态变化的Web服务中选择满足各服务节点功能需求的具体服务,形成一个切实可行的工作流实例来完成用户的个性化需求,成为服务工作流研究的关键问题.本文称其为服务工作流路径选择问题.对该问题的研究主要包括两个方面:1) 从功能需求的角度在不断变化的Web服务中找出符合要求的Web服务集;2) 功能相同或相似的Web服务其服务质量差异很大,需要从符合要求的服务集中找出满足用户QoS需求的服务实例.目前,使用工作流作为一个分布式活动的协调引擎,或作为一个服务合成建模和定义的工具对Web服务进行组合的研究已有不少.其中,Cross-Flow[4]和Sword[5]等研究项目致力于为企业提供一个动态的服务查找、发现与运行时动态绑定的服务合成平台,通过WSFL,LANG与BPEL4WS等服务合成语言为服务组合提供了一个统一建模和定义的工具.SciDAC-SDM项目[6,7]将用业务术语描述的抽象工作流与底层的由服务组成的执行工作流严格加以区分,并借用与数据库协调技术相类似的方法将抽象工作流转换成执行工作流.文献[8]利用事务的概念扩展了DAML-S本体中的过程模型,并提出了一个事务工作流本体概念的服务组织模型(transaction workflow ontology,简称TWFO).在以上这些研究中,从工作流业务领域到服务环境的映射只能进行静态的转换,不能根据服务的实时QoS状况,在执行时选取令用户满意的服务实例.eFlow[9]等服务工作流系统对组合服务的选择过程采用基于QoS局部最优的调度方法.这些方法中,各服务节点对应的具体Web服务实例选择是相互独立的,并不能解决服务工作流的QoS全局优化问题.文献[10,11]将服务的多个QoS约束参数通过线性加权转化为一个单目标函数,利用线性规划的基本原理来解决服务选择的QoS全局最优化调度问题.文献[2,3]利用遗传算法等非线性优化的仿生算法求解QoS全局最优化调度问题,取得的效果不错.但这些研究存在两点不足:1) 未能将Web服务的QoS全局最优化调度求解与服务动态变化的实际结合起来;2) 当网络中可选的Web服务迅速增加时,QoS调度的时间收敛性很难满足用户的实时性需求.针对以上问题,本文在课题组前期工作的基础上[12]提出了一种基于业务生成图的工作流构造模型.该模型聚集了多个功能相同或者相似的Web服务集合,每个服务集合采用生成树的方式进行组织,并依据工作流间的“上下游”逻辑关系组成业务工作流图;同时,用户可以依据自身的个性化需求对业务逻辑进行裁剪与限定、形成个性化定制模型;最后通过设计基于混合粒子群的QoS调度算法,消除互联网中可选服务迅速增加的影响,找出满足应用需求的工作流执行路径.实验与理论分析表明:该模型能够对动态的Web服务进行有效组合,对工作流执行路径的查找具有良好的时间收敛性,适合于虚拟计算环境的应用要求.1 服务定义及逻辑工作流模型描述本节首先给出Web服务和用户逻辑工作流结构的严格定义,而用户逻辑工作流定义后的实际运行是将其1872 Journal of Software 软件学报 V ol.18, No.8, August 2007映射到实际网络和服务实例的执行过程,因此在第2节中给出基于业务生成图的工作流构造模型组织结构,最后在第3节给出基于QoS 的工作流调度算法.工作流由一系列Web 服务的调用来完成,下面首先给出Web 服务的定义.定义1. Web 服务(WS)可以定义为一个三元组:WS =(D ,F ,Q ).1) D 是服务的基本定义与描述,即服务ID 、服务名称、服务的商业实体以及服务的文本描述;2) F 是服务功能描述,包括服务的接口参数Parameter 、前置条件Precondition 和后置条件PostCondition;3) Q 是对服务非功能属性的描述.它的质量模型可以定义为QoS (WS )={QoS (tim ),QoS (cos ),QoS (cap ),QoS (ava ),QoS (rep )},其中,QoS (tim )为所用的时间,QoS (cos )为所需的费用,QoS (cap )为计算能力,QoS (ava )表示服务的可用性,QoS (rep )表示服务的声誉度.对于QoS 可能有不同的定义,但不影响本文的主要结论,而且目前的大多数Web 服务描述语言都自发地遵循(D ,F ,Q ),比如OWL-S 等.定义2. 工作流业务逻辑模型(workflow business logic model,简称WBLM)是指组成工作流的各类服务相互关联而形成的逻辑结构图.需要指出的是,模型中的服务是指一种服务类型,而不是具体的服务实例,属于此类型的服务实例均可以完成此类型所代表的活动.图1所示为某工作流实例. Start W 6: W 1Control link End W 3⊕TrueFalse ?∝ W 2True False W 4 W 5True True ≡:Fig.1 A workflow business logic model图1 工作流业务逻辑模型工作流业务逻辑模型描述为WBLM =(MODELS ,CL ,DD ),其中:1) MODELS ={W 1,W 2,…,W n }为服务类型的集合,其中,W 1,…,W n 表示工作流的n 个参与服务类型;2) CL ⊆MODELS ×MODELS ×ϕ为控制连接(control link)的集合.对于〈W i ,W j ,ϕ〉∈CL ,控制结构运算符ϕ定义为从W i 到W j 的控制转换关系.基本服务通过若干控制结构可组合成服务工作流.工作流使用的控制结构运算符依据BPEL(businessprocess executable language)的定义共有5个,分别用sequence,switch,while,flow 和pick 来表示顺序、选择、循环、并行及事件选择这些逻辑关系.3) DD ⊆W ×W ×ψ为数据依赖(data dependency)的集合.对于〈W i ,W j ,ψ〉∈DD ,数据依赖函数ψ定义为从W j .input到W i .output 的函数依赖关系,并称W j 关于ψ数据依赖于W i ,记作W i ψW j .目前,支持对服务流程进行描述和定义的协议标准包括BPEL4WS,BPML 和OWL-S 等,它们的目标是将服务流程定义和具体的服务实现相分离,但本身并不具备依据多样化、个性化和动态业务需求匹配服务的功能[1].本文采用BPEL4WS 来描述工作流业务逻辑模型,主要基于如下两方面原因:(1) 它遵循了通用的标准,采用标准的XML 语言,能为其他系统所用;(2) 以其为基础,具体的个性化定制在调度模型中实现,以弥补其个性化定制能力较弱的不足.2 基于业务生成图的工作流模型构造本节主要论述基于业务生成图的工作流模型构造.服务工作流组成部分中有关QoS 调度策略是本文研究的重点,在第3节中单独加以论述.2.1 业务生成图的形成场景下面给出Web 服务组织模型的几个基本定义.胡春华等:一种基于业务生成图的Web服务工作流构造方法1873定义3. 服务可替代关系:若某应用能在服务WS i上满足性能要求,又能在服务WS j上得到性能满足,则称服务WS i可替代服务WS j,记为Sim(WS i,WS j).目前,相似服务的匹配大多采用基于本体的语义匹配方法.定义4. Web服务生成树(Web services spanning tree,简称WSST)是一类性能相同或者相似Web服务的有效集合.一棵服务生成树用无权无向图来表示,即G=(V,E),其中,V=n,是树中服务节点数,节点能提供功能相同的服务;E=m,即树的边数.对于服务生成树WSST k的任意两服务(WS i,WS j),都有Sim(WS i,WS j).定义5. Web业务生成图(Web business spanning graph,简称WBSP)是依据工作流的业务逻辑关系,由多棵生成树组合成的图,可以用G=(T,E)表示,其中,T=WSST(Web服务生成树的集合),是生成图中构成工作流的各个Web服务生成树;E=〈T i,T j〉,即生成图中两棵生成树之间依据接口和业务逻辑的流程关系形成的边,T i树中服务的输出是T j树中服务的输入,即在工作流路径中,T i服务的“下游”是T j.互联网中服务资源异常丰富,同时存在大量的功能相同或相近的服务.根据Web服务在网络中发布的信息,可以采用文献[10,13]提供的策略对其属性进行计算,将某类功能相同(相似)的服务找出,限于篇幅,本文不再赘述;然后组织网络中某类相同(相似)服务Sim(WS i,WS j)形成一棵生成树,每一棵树设定一个令牌节点[14]来负责树中所有信息的维护.如网络中产生新的服务后,也可以通过如下的简单策略申请加入到服务生成树(WSST)中: Step 1. 服务提供者以服务的参数向SRS发出加入申请报文(Join_Probe),申请加入WSST.Step 2.SRS接收到申请报文(Join_Probe)后,根据服务的统一编址方法确定此服务所属的权威负责解析SRS节点,此SRS在表中查找此服务所属的WSST的地址,返回给申请服务加入者(joiner)相关WSST中的服务节点地址,或者是此类服务还没有服务注册.Step 3. 如果joiner得到的是WSST地址,则继续Step 4;否则,他自己成为此类WSST的第1个节点,也是令牌节点,则加入过程结束.Step 4.joiner向WSST连接加入,它首先发出报文(还是Join_Probe),当WSST中某节点v接收到探测加入报文Join_Probe时,则返回给发起者肯定应答报文(Ack_For_Probe),表示通过此节点加入到WSST中.Step 5.WSST中的节点接收了新服务的加入,接收节点v向此类树中拥有令牌的节点发起通告报文,表示树中增加了一个服务.Step 6. 在与树内节点的交互过程中,将树内邻居节点Semi-adjacent项以及QoS相关项填充.Step 7. 令牌的节点在下一次广播报文中通告树中所有节点.业务生成图的形成需要在工作流语义环境下进行.基本思想是,在工作流业务逻辑的支持下,工作流起始服务对应的生成树发起业务生成图的形成请求,它首先依据工作流的语义关系得知其“下游”的服务类,然后向SRS查询得到其“下游”的生成树地址,进而将“下游”服务联系起来.经过反复的查询与连接过程,从而形成业务生成图,具体构造业务生成图的算法如下:算法1. 业务生成图的构造算法.Step 1. 工作流起始服务通过工作流模式得知“下游”服务的参数,以此向SRS发出查询此服务的查询申请报文(Query_Probe).Step 2. SRS接收到查询申请报文(Query_Probe)后,根据服务的统一编址方法确定此服务所属的权威负责解析SRS节点,此节点在表中查找该服务所属的WSST地址,返回给查询服务者WSST中的服务节点地址;或者是空,表示还没有此服务.Step 3. 如果发起者得到的是WSST地址,则继续Step 4;否则,过程结束.Step 4. 发起者向WSST连接加入,它首先发出报文(还是Join_Probe),当WSST中某节点v接收到探测加入报文Join_Probe时;向令牌节点转发,由令牌节点返回给发起者肯定应答报文(Ack_For_Probe).Step 5. 发起者根据得到的信息填充如下几个字段信息:next-adjacent;link-band[],int link-capac[].这时,“上下游”关系已经建立.Step 6. 新加入WSST中的令牌节点接收上游传过来的工作流模式,决定是否继续重复以上步骤,直至工作流关系建立.1874 Journal of Software软件学报 V ol.18, No.8, August 20072.2 业务生成图的工作流模型服务工作流构造模型(service workflow constructing model,简称SWCM)如图2所示,由两个有机部分组成:服务注册系统(service registrations system,简称SRS,见图2左上)和Web服务工作流生成图(service workflowspanning graph,简称SWSG,见图2中右).User Relay requestto SPTLogic workflowFig.2 An availability model of Web service workflow图2 服务工作流可用性模型1) 服务注册系统(SRS):主要起到索引服务作用,类似于DNS系统,存储的是某类服务对应的服务生成树地址.与文献[15]中提出的主动分布式Web服务注册系统的区别是:在文献[15]中主要是利用与DNS类似的服务注册系统(SRS),服务提供者直接向SRS注册.由于本文采用生成图的方式来组织工作流所对应的服务,因此在服务的组织上,并不需要每一个服务提供者直接向SRS注册,而是对于一棵生成树而言,选中其中一个作为令牌节点,由其来负责整棵树与SRS的服务信息维护,这样,对于广域网中的一类服务只需要一个节点与SRS交互,大幅度减少了SRS中服务信息维护的负载压力,而且避免了由于服务的动态产生,直接注册方法产生的系统维护与通信压力过大的问题.2) Web服务工作流生成图:组织网络中某类相同或相似服务Sim(WS i,WS j)形成一棵生成树,设定一个令牌节点来负责树中所有信息的维护.为了保持生成树的鲁棒性,对令牌节点采用冗余策略;同时,使令牌节点与SRS间存在定时的交互动作TTL(time to live),目的是让SRS知道树还“活着”,它由令牌节点在TTL交互时将树内信息报告给SRS;同时,依据工作流业务逻辑关系,将服务间的“上下游”对应的生成树之间关联起来(图2中的灰色箭头边所示),形成服务工作流生成图.图2中右侧所示的用户逻辑工作流到实际服务工作流路的映射由本文的QoS调度算法来完成,而逻辑工作流的描述用上一节的定义2来实现.整个工作流交互过程如图2所示.首先,用户向服务注册系统(SRS)发起服务工作流请求,SRS接收到请求后,依据用户XML描述(见第3.3节)的工作流起始服务类型转发到对应的服务生成树,再依据第4节提出的混合粒子群调度算法依次遍历业务生成图,返回给用户一条最佳的工作流执行路径,执行工作流;如果未找到合适的路径,则用户可以降低QoS级别与服务生成树进行QoS协商,再进行查找,直到协商成功或者失败为止.采用业务生成图的原因有以下几点:(1) 采用生成树来保持动态信息维护,能够有效减少服务直接与SRS 交互所带来的负载压力,虽然内部服务动态性很大,从而使系统的稳定性大大提高;(2) 可通过生成树中节点的个数表示提供此类服务的数目;(3) 组织成生成树后,工作流逻辑到服务实例的映射变得方便且迅速,只需查询SRS中生成树的地址,就能找到实际的服务集合;(4) 生成树是一种分布式且自我维护的组织结构,只要存在类似的服务就不会出现因服务动态变化而使服务工作流不可用的现象.2.3 工作流个性化定制个性化定制模型是提供给用户一种定制个性化工作流的方法,采用XML语言来定制个性化的工作流.这是胡春华等:一种基于业务生成图的Web服务工作流构造方法1875一种普遍采用的方法,如WSFLOW.它主要包含3个方面的定制工作,在XML中可以采用3个节来表示,分别是业务模式定制、执行模式定制、QoS参数定制.1) 业务模式定制是指对业务逻辑模式进行裁剪.在采用XML描述时,首先描述控制符(在service-control 节中),然后描述服务类(在service-model节中),这时,可以对业务逻辑进行定制.其中,defaultmodel表示服务类型,如果有多个业务逻辑流程,则可以用allow为真或者假来选择或不选择此业务流程.2) 执行模式定制是指对服务类到服务实例映射关系的定制与限定.在〈instance〉节中描述,用〈allow instance=“*”/〉表示可以映射到任意的服务实例(即服务提供商),用〈deny instance=“.”/〉表示不能映射的服务实例,如工作流不希望经过某些特定区域,则在此描述.3) QoS参数定制是指对映射的服务实例,如定义1中所定义的其他非功能性QoS属性的限定,表示将来调度时选择的服务实例必须满足的QoS要求,在〈QoS〉节表示,如用〈time<10/〉表示要求将来选择的服务实例的执行时间小于10.另外,在全局定制节部分〈globalization〉也可以定义整个工作流的QoS要求,用户还可以定制对不同QoS的偏向性,这是在〈Weight〉节中,对不同的QoS指标设置不同的权重来表示的.下面给出采用XML定制的例子.〈service-control〉〈!--定义业务逻辑的控制符--〉〈mode=“flow”/〉〈!--定制服务类部分--〉〈service-model〉〈defaultmodel=“A”/〉〈!--服务模式为A类服务--〉〈allow=“true”/〉〈!--允许此服务模式--〉〈instance〉〈!--对服务实例的定制部分--〉〈allow instance=“*”/〉〈!--允许映射的服务实例(服务提供商)--〉〈deny instance=“.”/〉〈!--不允许映射的服务实例--〉〈/instance〉〈QoS〉… 〈!--对QoS参数的定制部分--〉〈/QoS〉/service-model〉… 〈!--定制其他服务类部分--〉/service-control〉… 〈!--其他定制部分--〉〈globalization〉〈!--工作流全局定制部分--〉〈QoS〉〈!--对全局QoS参数的定制部分--〉〈time<110/〉〈!--工作流总的执行时间小于110--〉〈price<350/〉〈!--工作流总的执行费用小于350--〉〈capacity<75/〉〈!--工作流总的计算能力大于75--〉〈availability<0.7/〉〈!--工作流总的可靠性大于0.7--〉〈reputation<80/〉〈!--工作流总的信誉大于80--〉〈/QoS〉〈Weight〉〈!--对不同QoS指标的权重定制--〉〈W time=0.3/〉〈!--工作流执行时间权重为0.3--〉〈W price=0.2/〉〈!--工作流执行费用权重为0.2--〉〈/weight〉… 〈!--对其他全局定制部分--〉1876 Journal of Software 软件学报 V ol.18, No.8, August 2007由上例可知:用户对工作流服务质量的要求为tim <110,pri <350,cap >75,ava >0.7,rep >80.3 基于混合粒子群算法的QoS 调度互联网中同时存在大量功能相同(相近)、服务质量(QoS)各异的Web 服务,经过如图2所示的服务组织模型,可以将功能相同(相近)的服务进行有效组织,完成用户所需要的基本功能;但功能相同(相近)的Web 服务,其QoS 相差很大,如何从中找出“最佳”QoS 的服务实例来构造服务工作流满足用户的需求,将是本节需要解决的问题.QoS 调度实际上就是依据用户个性化定制的工作流,在业务生成图内,从服务质量各异的服务候选中选取“最佳”QoS 服务实例的过程,也即服务工作流中“最佳”执行路径的形成过程.3.1 混合粒子群算法随着Internet 中Web 服务的迅猛增长,服务注册系统中心(SRS)和服务生成树的可选服务都将迅速增加.对于QoS 调度,穷举法因候选服务众多已难以满足需要,遗传算法同样也显得力不从心.例如,图1所示的某服务工作流系统,6个服务类(W 1,W 2,...,W 6)中,若每个服务类有10个候选服务,则穷举法的搜索空间为106,穷举法显然不再适合,遗传算法的时间收敛性不强的弱点也逐渐显现出来.这种非线性组合的优化问题是一类NP 难问题,而粒子群算法(PSOA)在多目标优化中已广泛应用,且收敛性强,所以,本文利用粒子群算法对构造模型进行QoS 调度,以满足用户的相关要求.粒子群算法[16]首先由Kennedy 和Eberhart 于1995年提出,是一种基于迭代的进化计算方法,其本质是利用本身信息、局部较优信息和全局较优信息来指导粒子下一步迭代的位置.对于求解“最佳”QoS 路径问题,其当前位置是基本路径,若按基本粒子群算法,其速度难以表达.因此,通过重定义粒子群算法中的位置、速度、加、减和乘法操作,并将遗传算法的交叉、变异思想引入粒子群算法中,形成混合粒子群算法(hybrid particle swarmoptimization algorithm,简称HPSOA)进行求解.在每次迭代中,既考虑粒子群算法的本身信息、局部较优信息和全局较优信息,又进行类似于遗传算法中的交叉、变异操作,以获得“最佳”QoS 执行路径.下面给出重新定义后混合粒子算法的速度与位置操作符.设12{,,...,}m m m n X x x x =表示服务工作流路径的一个解,其中,m 为某生成树中Web 服务个数,n 为网络中生成 树的棵数.将SRS 中各点按从左到右、从上到下的顺序自然排序,然后按此顺序将每个待选点作为数组的一个元素,当元素x i 为1时,表示相应的点被选入该条路径中;否则,该点不在该条路径中.粒子位置的重新定义:X =(x 1,x 2,…,x m ) (1) 这里,粒子位置X 表示问题的一个解,包括m 个元素,每个元素的取值有两个:0和1,1表示相应的点被选入该条路径中,0则相反.例如,X (1,0,0,1,0,1,0,1)表示一条经过第1,4,6,8个节点的路径.粒子速度的重新定义:V =(v 1,v 2,…,v m ) (2)粒子速度V 表示路径的改进方向,即根据速度提示的位置和元素对原来路径进行替换,其元素取值有3个:−1,0,1.−1指示要替换的链路的起始位置和结束位置,0和1表示新的路径选择的点.例如:V (0,0,−1,0,1,0,−1,0)表示原路径中从第3个点到第7个点间的链路进行替换,因为第3个元素和第7个元素的值为−1,3和7分别表示要替换路径的起点位置和结束位置.第4,5,6个元素的值表示新的路径把原来的路径中相应的一段链路替换为经过第5个点的路径(第5个元素为1).“加法”(⊕)的重新定义:A ⊕B ,假设B 中第i 个元素和第j 个元素为−1,则把A 中第i +1到第j −1的元素替换为B 中相应位置的数值.例如,有X (1,1,1,1,1,1,0,1)和V (0,0,−1,0,1,0,−1,0),这样,X ⊕V =(1,1,1,0,1,0,0,1).“加法”实际上是实现了遗传算法中的“交叉”操作,把原路径的一段链路替换成新的链路,而替换的方向是由局部较优信息和全局较优信息指导的.“减法”()的重新定义:A B ,把A 和B 中数值相同的那个位置标记为−1,如果有多个−1,随机选取两个,结果只保留两个−1,两个−1间的数值为A 相应位置的数值,其他位置为0.如有X e e 1(1,0,0,1,0,1,0,0)和X 2(1,1,1,0,1,1,0,0),。
