基于模板的服务工作流的优化组合方法

D0I:10.13374/.issn1001-053x.2012.10.016 第34卷第10期 北京科技大学学报 Vol.34 No.10 2012年10月 Journal of University of Science and Technology Beijing 0ct.2012 基于模板的服务工作流的优化组合方法 颉 斌四 杨扬宋京王磊 北京科技大学计算机与通信工程学院，北京100083 ☒通信作者，E-mail:xiebin@usth.ed.cn 摘要研究了网络环境下基于模板的服务工作流的优化组合算法.该算法将服务优化组合问题转化为服务工作流模板的 优化组合问题，既极大程度地复用历史服务工作流模板以减少组建新工作流的工作量，又通过优化使得服务工作流结构更为 合理，缩短了服务工作流的执行时间.通过使用Ptmi网对网络流媒体课件制作服务工作流进行建模，并对比优化前后服务工 作流模型的SPNP性能分析结果，证明了优化算法的有效性 关键词网络服务：工作流软件：模板匹配：算法：Petri网 分类号TP393 Service workflow optimization and composition method based on templates XIE Bin,YANG Yang,SONG Jing,WANG Lei School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China XCorresponding author,E-mail:xiebin@ustb.edu.cn ABSTRACT An optimization and composition algorithm based service workflow templates in network environment was proposed in this paper.The algorithm turns the problem of service optimization and composition into a problem of service workflow templates,thus it can largely reuse history workflow templates and decrease the buildup work of new workflow templates.In the algorithm,optimization makes the structure of the service workflow more reasonable and the execution time shortened.A network stream media courseware- making service workflow as an example was modeled with a Petri net.The comparison of SPNP performance analysis results of the service workflow between pre-optimization and post-optimization proves the algorithm's effectiveness. KEY WORDS web services;workflow management software:template matching:algorithms;Petri nets 近年来，对工作流的研究成为计算机科学领域 将服务作为优化组合对象，没有考虑重用己有的服 的一个研究热点，工作流技术已被广泛地应用于办 务工作流模板，所以组建工作流的工作量很大.文 公自动化、业务流程重组和业务流程管理等领域. 献B]研究了基于模板的Wb服务组合模型，能够 服务工作流将工作流中的任务以服务的形式实现， 较准确地得到服务组合需要的Wb服务及工作流 是Wb服务与工作流相结合的产物，其抽象业务逻 模板，这样通过复用历史模板减小组建工作流的工 辑模型由多个服务节点组成，是一种半自动的服务 作量；然而组建的工作流规模庞大，结构复杂，执行 组合方式四.随着网络的不断发展，网络提供的服 时间过长.文献4]提出了一个基于抽象模板的语 务种类越来越多，服务组合方式千差万别，这就会导 义Wb服务组合框架，当不存在一个满足用户请求 致网络环境下的服务工作流出现组建工作量大、结 的模板时，可以实现对模板的自动修改；它虽然实现 构复杂和规模庞大等问题. 了对模板自动修改的功能，减少了工作量，但是只考 目前关于服务工作流优化组合方法研究己经有 虑匹配一个模板，灵活性不高.文献5]提出了基于 大量研究成果.文献2]基于排队论的知识提出了 Petri网的过程优化算法：虽然它在一定程度上化简 一种服务工作流的优化算法，该算法将费用、响应时 了工作流模型，但是考虑的组合对象是服务，组建工 间和排队顾客数作为限制条件，通过对可选服务的 作流的工作量大 选择使得工作流的服务利用率得到优化；但该算法 目前大多数关于工作流模板查找与匹配的研究 收稿日期：201108-30 基金项目：国家自然科学基金资助项目(61070182：60873192：61170209)

第 34 卷 第 10 期 2012 年 10 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 10 Oct． 2012 基于模板的服务工作流的优化组合方法 颉 斌! 杨 扬 宋 京 王 磊 北京科技大学计算机与通信工程学院，北京 100083 !通信作者，E-mail: xiebin@ ustb． edu． cn 摘 要 研究了网络环境下基于模板的服务工作流的优化组合算法． 该算法将服务优化组合问题转化为服务工作流模板的 优化组合问题，既极大程度地复用历史服务工作流模板以减少组建新工作流的工作量，又通过优化使得服务工作流结构更为 合理，缩短了服务工作流的执行时间． 通过使用 Petri 网对网络流媒体课件制作服务工作流进行建模，并对比优化前后服务工 作流模型的 SPNP 性能分析结果，证明了优化算法的有效性． 关键词 网络服务; 工作流软件; 模板匹配; 算法; Petri 网 分类号 TP393 Service workflow optimization and composition method based on templates XIE Bin!，YANG Yang，SONG Jing，WANG Lei School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China !Corresponding author，E-mail: xiebin@ ustb． edu． cn ABSTRACT An optimization and composition algorithm based service workflow templates in network environment was proposed in this paper． The algorithm turns the problem of service optimization and composition into a problem of service workflow templates，thus it can largely reuse history workflow templates and decrease the buildup work of new workflow templates． In the algorithm，optimization makes the structure of the service workflow more reasonable and the execution time shortened． A network stream media courseware￾making service workflow as an example was modeled with a Petri net． The comparison of SPNP performance analysis results of the service workflow between pre-optimization and post-optimization proves the algorithm's effectiveness． KEY WORDS web services; workflow management software; template matching; algorithms; Petri nets 收稿日期: 2011--08--30 基金项目: 国家自然科学基金资助项目( 61070182; 60873192; 61170209) 近年来，对工作流的研究成为计算机科学领域 的一个研究热点，工作流技术已被广泛地应用于办 公自动化、业务流程重组和业务流程管理等领域． 服务工作流将工作流中的任务以服务的形式实现， 是 Web 服务与工作流相结合的产物，其抽象业务逻 辑模型由多个服务节点组成，是一种半自动的服务 组合方式［1］． 随着网络的不断发展，网络提供的服 务种类越来越多，服务组合方式千差万别，这就会导 致网络环境下的服务工作流出现组建工作量大、结 构复杂和规模庞大等问题． 目前关于服务工作流优化组合方法研究已经有 大量研究成果． 文献［2］基于排队论的知识提出了 一种服务工作流的优化算法，该算法将费用、响应时 间和排队顾客数作为限制条件，通过对可选服务的 选择使得工作流的服务利用率得到优化; 但该算法 将服务作为优化组合对象，没有考虑重用已有的服 务工作流模板，所以组建工作流的工作量很大． 文 献［3］研究了基于模板的 Web 服务组合模型，能够 较准确地得到服务组合需要的 Web 服务及工作流 模板，这样通过复用历史模板减小组建工作流的工 作量; 然而组建的工作流规模庞大，结构复杂，执行 时间过长． 文献［4］提出了一个基于抽象模板的语 义 Web 服务组合框架，当不存在一个满足用户请求 的模板时，可以实现对模板的自动修改; 它虽然实现 了对模板自动修改的功能，减少了工作量，但是只考 虑匹配一个模板，灵活性不高． 文献［5］提出了基于 Petri 网的过程优化算法; 虽然它在一定程度上化简 了工作流模型，但是考虑的组合对象是服务，组建工 作流的工作量大． 目前大多数关于工作流模板查找与匹配的研究 DOI:10.13374/j.issn1001-053x.2012.10.016

·1214· 北京科技大学学报 第34卷 是基于语义的a.本文研究的主要内容是在获得 流模板的服务性质分析，本文将模板之间的关系归 了匹配的服务工作流模板集合之后，如何根据模板 纳为输入依赖关系、输入/输出依赖关系、资源依赖 集合中服务工作流模板之间的关系，在服务工作流 关系和资源冲突关系四种，定义如下 执行过程中动态的优化组合服务工作流模板. 定义1输入依赖关系：假设两个服务工作流 1 服务工作流模板 模板WFTemplate:和WFTemplate,nput:和Input; 分别是它们的输入信息，如果Iput:=Input,则 1.1服务工作流模板定义 WFTemplate:和WFTemplate,为输入依赖关系. 目前，对于服务工作流模板，已有一些学者给出 当两个服务工作流模板间存在输入依赖关系 了模型定义：文献B]将服务工作流模板定义为一 时，它们的输入是相同的，为了节省两个服务工作流 个四元组WorkFlowTemplate=.Identity是模板的唯一标识： 并，其输出结果为两个模板输出结果的并集. Description是对模板的描述，它是一个五元组De 定义2输入/输出依赖关系：假设两个服务工 scription =Fields,Input,Output,Function,Type 作流模板WFTemplate:和WFTemplate,Input,/ >,描述的是模板涉及的领域、输入/输出信息、服务 Output,.、nput,/Output.是它们的输入输出信息，如果 功能语义以及模板类型：ServiceSet描述组成此模板 3 Input,∈Output,则WFTemplate;和WFTemplate 的服务集ServiceSet=,它包 为输入/输出依赖关系 括服务集合Services及服务关系集合Relations;Qof 当两个服务工作流模板间存在输入/输出依赖 为衡量此流程的服务质量.文献4]定义抽象工作 关系时，它们执行的先后顺序是固定的，不能颠倒也 流模板为一个五元组AT=,Dom描述抽象模板中的抽象服务所使用的领域 流无法执行. 本体；Des是模板的功能性文字描述：Func=,是抽象模板所需要的输入、输出、执 模板WFTemplate:和WFTemplate,Res:和Res,分 行前件以及执行效果；S是一组组成模板的抽象服 别是它们执行所需要的资源，如果Res:nRes,≠g, 务；R是抽象服务之间的关系 则WFTemplate:和WFTemplate,为资源依赖关系. 通过对比分析，发现以上两个服务工作流模板 定义4资源冲突关系：假设两个服务工作流 定义内容大致相同，本文在定义服务工作流模板的 模板WFTemplate:和WFTemplate,存在资源依赖关 时候借鉴了以上两种定义方法.考虑到本文研究的 系，且在服务工作流执行的过程中，[StartTime:, 内容与语义无关，所以删除了上面定义中关于语义 EndTime:]∩StartTime,EndTime]≠☑，则WFTem- 的部分：同时，由于要研究的服务工作流模板间关系 plate;和WFTemplate;为资源冲突关系.其中 包括资源间的关系，所以在定义中加入了资源的属 StartTime表示服务工作流模板执行开始时间，End- 性，于是有了本文关于服务工作流模板的定义： Time表示服务工作流模板执行结束时间， WFTemplate = 时，不能够将两模板并行执行，否则会引发资源冲 (1)D是服务工作流模板的唯一标识 突，使得两者关系变为资源冲突关系，从而会影响组 (2)Function描述了服务工作流模板的功能 合的服务工作流的性能 (3)Input/.Output描述了服务工作流模板的输 2基于模板的服务工作流的优化组合算法 入输出信息 (4)Res描述了执行服务工作流模板所需要的 网络环境处于不断变化之中，服务可能随时加 资源 入或退出网络，服务能力也处于不断变化之中，这样 (S)ServiceSet描述组成服务工作流模板的服 就要求服务工作流必须能够适应服务的动态变化 务集ServiceSet=,它包括服 同时，虽然根据推理组合模板而成的服务工作流逻 务集合Services以及服务关系集合Relations. 辑上是正确的，但是结构上并不是最优的.所以，在 (6)Q0s是服务工作流模板的服务质量 服务工作流执行过程中动态优化组合服务工作流十 1.2服务工作流模板间的关系 分必要. 定义了服务工作流模板之后，通过对服务工作 Petri网是一种可以用来对具有并发、异步、不

北 京 科 技 大 学 学 报 第 34 卷 是基于语义的［4，6］． 本文研究的主要内容是在获得 了匹配的服务工作流模板集合之后，如何根据模板 集合中服务工作流模板之间的关系，在服务工作流 执行过程中动态的优化组合服务工作流模板． 1 服务工作流模板 1. 1 服务工作流模板定义 目前，对于服务工作流模板，已有一些学者给出 了模型定义: 文献［3］将服务工作流模板定义为一 个四 元 组 WorkFlowTemplate = ＜ Identity，Descrip￾tion，ServiceSet，Qof ＞ ． Identity 是模板的唯一标识; Description 是对模板的描述，它是一个五元组 De￾scription = ＜ Fields，Input，Output，Function，Type ＞ ，描述的是模板涉及的领域、输入/输出信息、服务 功能语义以及模板类型; ServiceSet 描述组成此模板 的服务集 ServiceSet = ＜ Services，Relations ＞ ，它包 括服务集合 Services 及服务关系集合 Relations; Qof 为衡量此流程的服务质量． 文献［4］定义抽象工作 流模板为一个五元组 AT = ＜ Dom，Des，Func，S，R ＞ ，Dom 描述抽象模板中的抽象服务所使用的领域 本体; Des 是模板的功能性文字描述; Func = ＜ In， Out，pre，eff ＞ ，是抽象模板所需要的输入、输出、执 行前件以及执行效果; S 是一组组成模板的抽象服 务; R 是抽象服务之间的关系． 通过对比分析，发现以上两个服务工作流模板 定义内容大致相同，本文在定义服务工作流模板的 时候借鉴了以上两种定义方法． 考虑到本文研究的 内容与语义无关，所以删除了上面定义中关于语义 的部分; 同时，由于要研究的服务工作流模板间关系 包括资源间的关系，所以在定义中加入了资源的属 性，于是有了本文关于服务工作流模板的定义: WFTemplate = ＜ ID，Function，Input /Output， Res，ServiceSet，Qos ＞ ． ( 1) ID 是服务工作流模板的唯一标识． ( 2) Function 描述了服务工作流模板的功能． ( 3) Input /Output 描述了服务工作流模板的输 入输出信息． ( 4) Res 描述了执行服务工作流模板所需要的 资源． ( 5) ServiceSet 描述组成服务工作流模板的服 务集 ServiceSet = ＜ Services，Relations ＞ ，它包括服 务集合 Services 以及服务关系集合 Relations． ( 6) Qos 是服务工作流模板的服务质量． 1. 2 服务工作流模板间的关系 定义了服务工作流模板之后，通过对服务工作 流模板的服务性质分析，本文将模板之间的关系归 纳为输入依赖关系、输入/输出依赖关系、资源依赖 关系和资源冲突关系四种，定义如下． 定义 1 输入依赖关系: 假设两个服务工作流 模板 WFTemplatei 和 WFTemplatej ，Inputi 和 Inputj 分别是 它 们 的 输 入 信 息，如 果 Inputi = Inputj ，则 WFTemplatei和 WFTemplatej 为输入依赖关系． 当两个服务工作流模板间存在输入依赖关系 时，它们的输入是相同的，为了节省两个服务工作流 模板间数据传输的时间和费用，可以将它们进行合 并，其输出结果为两个模板输出结果的并集． 定义 2 输入/输出依赖关系: 假设两个服务工 作 流 模 板 WFTemplatei 和 WFTemplatej ，Inputi / Outputi、Inputj /Outputj 是它们的输入输出信息，如果 Inputi ∈ Outputj ，则 WFTemplatei 和 WFTemplatej 为输入/输出依赖关系． 当两个服务工作流模板间存在输入/输出依赖 关系时，它们执行的先后顺序是固定的，不能颠倒也 不能并行，否则会引起逻辑上的错误而使服务工作 流无法执行． 定义 3 资源依赖关系: 假设两个服务工作流 模板 WFTemplatei 和 WFTemplatej ，Resi 和 Resj 分 别是它们执行所需要的资源，如果 Resi∩Resj≠$， 则 WFTemplatei 和 WFTemplatej 为资源依赖关系． 定义 4 资源冲突关系: 假设两个服务工作流 模板 WFTemplatei 和 WFTemplatej 存在资源依赖关 系，且在服务工作流执行的过程中，［StartTimei， EndTimei ］∩［StartTimej ，EndTimej ］≠$，则 WFTem￾platei 和 WFTemplatej 为 资 源 冲 突 关 系． 其 中 StartTime表示服务工作流模板执行开始时间，End￾Time 表示服务工作流模板执行结束时间． 当两个服务工作流模板间存在资源依赖关系 时，不能够将两模板并行执行，否则会引发资源冲 突，使得两者关系变为资源冲突关系，从而会影响组 合的服务工作流的性能． 2 基于模板的服务工作流的优化组合算法 网络环境处于不断变化之中，服务可能随时加 入或退出网络，服务能力也处于不断变化之中，这样 就要求服务工作流必须能够适应服务的动态变化． 同时，虽然根据推理组合模板而成的服务工作流逻 辑上是正确的，但是结构上并不是最优的． 所以，在 服务工作流执行过程中动态优化组合服务工作流十 分必要． Petri 网是一种可以用来对具有并发、异步、不 ·1214·

第10期 颉斌等：基于模板的服务工作流的优化组合方法 ·1215· 确定和分布式等特点的系统进行图形化数学建模和 模板1 模板2 分析的工具，它注重表示系统的状态转换以及状态 转换关系，因此能够很好地描述系统的动态变化特 性.同时，WMC所定义的六种工作流原语都能很 oioioioio 好地映射成Petri网的表达形式，所以本文选用Petri 网对服务工作流进行建模分析.Petri网D-可以描 述成一个三元组PN=(P,T,F).其中：P={P, P2,…,Pn},是有穷位置集合；T={t1,2…,tm}, ololo1o1o 是有穷变迁集合；PnT≠O(二元性)；PUT≠O(网 图2任务回滚优化 非空)：FC(P×T)U(T×P),是弧的集合（弧仅在 Fig.2 Optimization of task rollback 于P与T的元素之间)；dom(F)Ucod(F)=PUT (没有孤立元素). 赖关系（见定义1）且模板的Rs相同的服务工作流 用Petri网的位置表示工作流任务发生的条件， 模板进行合并，这样可以节省任务交接的时间和成 用变迁表示任务的执行，用标识表示工作流实例，这 本，用Petri网表示如图3所示. 样就能够使用Petri网对服务工作流进行建模. 模板1模板2 下面，借助于基于Petri网的服务工作流模型， 对基于模板的服务工作流的优化组合算法进行介 绍，其具体步骤如下 12 (1)查看服务工作流模板集中各个模板 图3服务工作流模板合并 WFTemplate的服务集ServiceSet是否有相同的服 Fig.3 Mergence of the service workflow template 务，如有则合并.这样可以保证整个服务工作流的 一致性及防止某一服务在工作流中多次重复出 (4)查询当前网络服务状态，对于不存在输入/ 现，提高服务工作流的执行效率，用Petri网表示如 输出依赖关系（见定义2）且不存在资源依赖关系 图1. (见定义3和定义4)的服务工作流模板，并行执行 以节省执行时间，用Petri网表示如图4所示. 模板1 模板2 oioioioio 模板1模板2 Tv-1 图4服务工作流模板并行 Fig.4 Parallelization of the service workflow template 图1相同服务合并 Fig.I Mergence of the same services (5)在服务工作流执行任务过程中，扫描任务 定义，判断任务能否进行拆分回.如果能拆分，则根 (2)查看服务工作流模板集中各个模板是否含 据任务拆分服务工作流模板.若模板拆分所得的分 有任务回滚.任务回滚是指当任务的输入不正确导 支之间不存在输入/输出依赖关系且不存在资源依 致任务无法向下执行的情况，这样就需要回滚到输 赖关系，则并行执行这些模板分支以节省时间，用 入环节，返回执行前的状态.对于这种情况，任务不 Petri网表示如图5所示. 应仅仅回滚到本模板的输入环节，而是需要回滚到 (6)服务工作流执行过程中反复执行(1)~ 上一模板的执行环节，这样才能纠正上一模板的输 (5),直至服务工作流执行结束 出错误，也就能保证本模板输入的正确性，从而防止 总的来看，经过上述方法优化后，服务工作流的 自动生成的服务工作流执行时陷入死循环，用Petri 结构更为合理.下文将以制作网络流媒体课件服务 网表示如图2所示. 工作流为例来说明基于模板的服务工作流的优化组 (3)查询当前网络服务状态，对于存在输入依 合算法的有效性

第 10 期 颉 斌等: 基于模板的服务工作流的优化组合方法 确定和分布式等特点的系统进行图形化数学建模和 分析的工具，它注重表示系统的状态转换以及状态 转换关系，因此能够很好地描述系统的动态变化特 性． 同时，WfMC 所定义的六种工作流原语都能很 好地映射成 Petri 网的表达形式，所以本文选用 Petri 网对服务工作流进行建模分析． Petri 网［7--8］可以描 述成一个三元组 PN = ( P，T，F) ． 其中: P = { p1， p2，…，pm } ，是有穷位置集合; T = { t1，t2，…，tm } ， 是有穷变迁集合; P∩T≠$( 二元性) ; P∪T≠$( 网 非空) ; F( P × T) ∪( T × P) ，是弧的集合( 弧仅在 于 P 与 T 的元素之间) ; dom( F) ∪cod( F) = P∪T ( 没有孤立元素) ． 用 Petri 网的位置表示工作流任务发生的条件， 用变迁表示任务的执行，用标识表示工作流实例，这 样就能够使用 Petri 网对服务工作流进行建模． 下面，借助于基于 Petri 网的服务工作流模型， 对基于模板的服务工作流的优化组合算法进行介 绍，其具体步骤如下． ( 1) 查看服务工作流模板集中各个模板 WFTemplate的服 务 集 ServiceSet 是否有相同的服 务，如有则合并． 这样可以保证整个服务工作流的 一致性及防止某一服务在工作流中多次重复出 现，提高服务工作流的执行效率，用 Petri 网表示如 图 1． 图 1 相同服务合并 Fig． 1 Mergence of the same services ( 2) 查看服务工作流模板集中各个模板是否含 有任务回滚． 任务回滚是指当任务的输入不正确导 致任务无法向下执行的情况，这样就需要回滚到输 入环节，返回执行前的状态． 对于这种情况，任务不 应仅仅回滚到本模板的输入环节，而是需要回滚到 上一模板的执行环节，这样才能纠正上一模板的输 出错误，也就能保证本模板输入的正确性，从而防止 自动生成的服务工作流执行时陷入死循环，用 Petri 网表示如图 2 所示． ( 3) 查询当前网络服务状态，对于存在输入依 图 2 任务回滚优化 Fig． 2 Optimization of task rollback 赖关系( 见定义 1) 且模板的 Res 相同的服务工作流 模板进行合并，这样可以节省任务交接的时间和成 本，用 Petri 网表示如图 3 所示． 图 3 服务工作流模板合并 Fig． 3 Mergence of the service workflow template ( 4) 查询当前网络服务状态，对于不存在输入/ 输出依赖关系( 见定义 2) 且不存在资源依赖关系 ( 见定义 3 和定义 4) 的服务工作流模板，并行执行 以节省执行时间，用 Petri 网表示如图 4 所示． 图 4 服务工作流模板并行 Fig． 4 Parallelization of the service workflow template ( 5) 在服务工作流执行任务过程中，扫描任务 定义，判断任务能否进行拆分［9］． 如果能拆分，则根 据任务拆分服务工作流模板． 若模板拆分所得的分 支之间不存在输入/输出依赖关系且不存在资源依 赖关系，则并行执行这些模板分支以节省时间，用 Petri 网表示如图 5 所示． ( 6) 服务工作流执行过程中反复执行( 1) ～ ( 5) ，直至服务工作流执行结束． 总的来看，经过上述方法优化后，服务工作流的 结构更为合理． 下文将以制作网络流媒体课件服务 工作流为例来说明基于模板的服务工作流的优化组 合算法的有效性． ·1215·

·1216· 北京科技大学学报 第34卷 所示.其详细执行过程为：视频上传T和视频图像 模板分支1 处理T,合并为图7中T,图片上传T和图片处理T4 合并为图7中T,且这两部分工作优化为并行执 0lo0→01 行，片头素材上传T,和片头制作T,合并为图7中 T·相应地，图7中的T3、T、T6、T,、T和T,分别对 应图6中的TTgT,T、T2和T3·当素材格式不 模板分支： 正确时，进行任务回滚优化，如图7中的3· 图5服务工作流模板拆分 表1优化前Ptmi网模型主要变迁描述 Fig.5 Splitting of the service workflow template Table 1 Transition description of the Petri net model before optimization 变迁 描述 变迁 描述 To T 3服务工作流的应用 登录网站 视频上传 T2 视频格式转换 Ts 图片上传 3.1网络流媒体课件制作流程建模 Ta 图片处理 T 图片插入视频 片头素材上传 T1 片头制作 本文以网络流媒体课件制作过程为实例，对网 Ts 导出片头 Ta 导出片头声音 络流媒体课件制作服务工作流进行Petri网建模分 Tio 素材上传 素材格式不正确 析，通过对比优化前后服务工作流的吞吐量和响应 素材格式正确 统一调节 Te 渲染合成 T 生成账单 时间来证明优化算法的有效性 网络流媒体课件制作服务工作流主要流程为：首 先，利用软件将MOD格式的录像转换为MPEG格式； 其次，利用辅助工具Photoshop制作视频背景图片，将 制作好的背景图片插入视频；再次，利用FLASH对片 头进行制作，导出片头(SWF格式)及片头声音(WAV 格式)：最后，利用绘声绘影软件对片头、片头声音、视 频背景图片及视频进行渲染合成 对于用户提交的制作网络流媒体课件服务工作 流的请求，服务工作流引擎经过推理分析得到了包 含视频格式转换、图片处理、图片插入视频、片头制 作和渲染合成几个历史服务工作流模板的模板集 合，推理机根据语义组建的服务工作流的Petri网模 图7优化后服务工作流的Pti网模型 型如图6所示.表1给出了上图Petri网模型主要变 Fig.7 Petri net model of the service workflow after optimization 迁的描述. 3.2性能分析 00000o00 SPNPD@是由美国Duke大学Kishor S Trivedi教 授所领导的研究小组研究和开发的，目前己经成为一 个较成熟的随机Petri网分析求解软件.在SPNP中， 稳定状态下每个变迁的吞吐量和每个位置的平均标 记数量都是可由软件自动算出.本文将Petri网模型 的起始位置含有的标志数设为10，每个变迁速率设 为1.当服务工作流请求到达速率在1~6个·s时， 通过对SPNP仿真结果的统计和计算，得出优化前后 服务工作流吞吐量和响应时间的对比图如图8所示 对比发现，服务工作流的吞吐量变化不大. 图6优化前服务工作流的Petri网模型 图9对比了服务工作流优化前后的响应时间， Fig.6 Petri net model of the service workflow before optimization 对比发现当服务工作流请求到达速率在1~ 使用基于模板的服务工作流优化组合算法对图 6个·s范围内变化时，服务工作流的系统响应时 6所示Petri网模型进行优化后，得到的模型如图7 间有较大的变化.优化后服务工作流响应时间可大

北 京 科 技 大 学 学 报 第 34 卷 图 5 服务工作流模板拆分 Fig． 5 Splitting of the service workflow template 3 服务工作流的应用 3. 1 网络流媒体课件制作流程建模 本文以网络流媒体课件制作过程为实例，对网 络流媒体课件制作服务工作流进行 Petri 网建模分 析，通过对比优化前后服务工作流的吞吐量和响应 时间来证明优化算法的有效性． 网络流媒体课件制作服务工作流主要流程为: 首 先，利用软件将 MOD 格式的录像转换为 MPEG 格式; 其次，利用辅助工具 Photoshop 制作视频背景图片，将 制作好的背景图片插入视频; 再次，利用 FLASH 对片 头进行制作，导出片头( SWF 格式) 及片头声音( WAV 格式) ; 最后，利用绘声绘影软件对片头、片头声音、视 频背景图片及视频进行渲染合成． 对于用户提交的制作网络流媒体课件服务工作 流的请求，服务工作流引擎经过推理分析得到了包 含视频格式转换、图片处理、图片插入视频、片头制 作和渲染合成几个历史服务工作流模板的模板集 合，推理机根据语义组建的服务工作流的 Petri 网模 型如图 6 所示． 表 1 给出了上图 Petri 网模型主要变 迁的描述． 图 6 优化前服务工作流的 Petri 网模型 Fig． 6 Petri net model of the service workflow before optimization 使用基于模板的服务工作流优化组合算法对图 6 所示 Petri 网模型进行优化后，得到的模型如图 7 所示． 其详细执行过程为: 视频上传 T1和视频图像 处理 T2合并为图7 中 T1，图片上传 T3和图片处理 T4 合并为图 7 中 T2，且这两部分工作优化为并行执 行，片头素材上传 T6 和片头制作 T7 合并为图 7 中 T4 ． 相应地，图 7 中的 T3、T5、T6、T7、T8和 T9分别对 应图 6 中的 T5、T8、T9、T11、T12和 T13 ． 当素材格式不 正确时，进行任务回滚优化，如图 7 中的 t3 ． 表 1 优化前 Petri 网模型主要变迁描述 Table 1 Transition description of the Petri net model before optimization 变迁 描述 变迁 描述 T0 登录网站 T1 视频上传 T2 视频格式转换 T3 图片上传 T4 图片处理 T5 图片插入视频 T6 片头素材上传 T7 片头制作 T8 导出片头 T9 导出片头声音 T10 素材上传 t2 素材格式不正确 t3 素材格式正确 T11 统一调节 T12 渲染合成 T13 生成账单 图 7 优化后服务工作流的 Petri 网模型 Fig． 7 Petri net model of the service workflow after optimization 3. 2 性能分析 SPNP ［10］是由美国 Duke 大学 Kishor S Trivedi 教 授所领导的研究小组研究和开发的，目前已经成为一 个较成熟的随机 Petri 网分析求解软件． 在 SPNP 中， 稳定状态下每个变迁的吞吐量和每个位置的平均标 记数量都是可由软件自动算出． 本文将 Petri 网模型 的起始位置含有的标志数设为 10，每个变迁速率设 为 1． 当服务工作流请求到达速率在 1 ～ 6 个·s － 1 时， 通过对 SPNP 仿真结果的统计和计算，得出优化前后 服务工作流吞吐量和响应时间的对比图如图 8 所示． 对比发现，服务工作流的吞吐量变化不大． 图 9 对比了服务工作流优化前后的响应时间， 对比发现当服务工作流请求到达速率在 1 ～ 6 个·s － 1 范围内变化时，服务工作流的系统响应时 间有较大的变化． 优化后服务工作流响应时间可大 ·1216·

第10期 颉斌等：基于模板的服务工作流的优化组合方法 ·1217· 6.0 组合优化问题转化为历史服务工作流模板组合优化 5.8 墨优化前 5.6 ☑优化后 问题，提出了基于模板的服务工作流的优化组合算 法.为了证明优化算法的有效性，以网络流媒体课 5.2 5.0 件制作服务工作流为实例，使用Petri网对其进行建 4.8 模，通过对比优化前后服务工作流模型的SPNP性 46 4 能分析结果，发现优化后服务工作流的吞吐量变化 请求到达速率（个·） 不大，但是响应时间较优化前可大幅降低，从而证明 图8优化前后服务工作流吞吐量对比图 了优化算法的有效性. Fig.8 Service workflow throughput comparison between pre-optimi- zation and postoptimization 参考文献 27 [1]Hu C H.Wu M,Liu G P,et al.Approach to constructing web 25 圆优化前 service workflow based on business spanning graph.J Softcare, 三2B ☑优化后 2007,18(8):1870 21 (胡春华，吴敏，刘国平，等.一种基于业务生成图的W山服 19 务工作流构造方法.软件学报，2007,18(8)：1870) 17 Eckert J,Schulte S,Repp N,et al.Queuing-based capacity plan- 4 5 ning approach for Web service workflows using optimization algo- 请求到达速率（个·） rithms /2008 Second IEEE International Conference on Digital 图9优化前后服务工作流响应时间对比图 Ecosystems and Technologies.Phitsanulok,2008:313 Fig.9 Service workflow responding time comparison between preop- [3] Ling H Y.Realization of Web Services Composition System Based on timization and post-optimization Workflow Template [Dissertation].Wuhan:Wuhan University of Science and Technology,2009 幅降低，从而证明了优化算法的有效性 (凌海洋.基于工作流模板的Wb服务组合系统实现[学位论 为验证所提算法较其他同类算法的有效性，本 文].武汉：武汉科技大学，2009) 文设计了与传统Petri网网格工作流在服务组合执 [4] Hu J,Feng Z Y.Semantic web service composition framework 行效率上的对比实验.同样，当服务工作流请求到 based on abstract template.Comput Appl,00929(11):3150 达速率在1~6个·s-时，通过SPNP仿真，得出服务 (胡佳，冯志勇.一种基于抽象模板的语义W山服务组合框 架.计算机应用，2009,29(11)：3150) 组合执行时间如图10所示 [5] Zhou J B,Ling H,Xu Z C.Petri net-based workflow optimization 40 analysis.Chin J Manage Sci,2005,13(3):50 图传统Pelri (周江波，凌鸿，胥正川.基于Ptr网的工作流优化分析.中 ☑本文算法 30 国管理科学，2005,13(13)：50) [6]Chen F.Dynamic Semantic Web Serrice Composition Model and 20 Achierement Based on Workflow [Dissertation].Wuhan:Hua- zhong University of Science and Technology,2007 (陈飞.基于工作流的语义W山服务动态组合模型及实现 [学位论文].武汉：华中科技大学，2007) 请求到达速率从个·s少 ] Lin C.Stochastic Petri Nets and Performance Evaluation of Sys- 图10服务组合执行效率对比 tems.2nd Ed.Beijing:Tsinghua University Press,2005 Fig.10 Comparison of execution efficiency of service composition (林闯.随机Ptr网和系统性能评价.2版.北京：清华大学 出版社，2005) 依据图10可以看出，本文提出的基于模板的服 四 Schimm G.Mining exact models of concurrent workflows.Comput 务组合优化算法在执行时间上大大优于传统的Peti 1md,2004,53(3):265 网网格工作流服务组合，尤其是在服务请求增多时， 9] Hu Z G,Zhao R F,Chen R,et al.Research on grid service work- 其执行效率对比优势更为明显. flow model based on dynamic colored Petri net.J Chin Comput Ss,2007,28(7):1205 4结论 (胡志刚，赵瑞芳，谌任，等.基于动态有色P如网的网格服务工 作流模型的研究.小型微型计算机系统，2007,28(7)：1205) 本文结合网络环境下服务的特点，研究了服务 [10]Reibman A,Smith R,Trivedi K.Markov and Markov reward 工作流模板模型及服务工作流模板间的关系.为了 model transient analysis:an overview of numerical approaches. 极大程度地复用己有历史服务工作流模板，将服务 Eur J Oper Res,1989,40(2):257

第 10 期 颉 斌等: 基于模板的服务工作流的优化组合方法 图 8 优化前后服务工作流吞吐量对比图 Fig． 8 Service workflow throughput comparison between pre-optimi￾zation and post-optimization 图 9 优化前后服务工作流响应时间对比图 Fig． 9 Service workflow responding time comparison between pre-op￾timization and post-optimization 幅降低，从而证明了优化算法的有效性． 为验证所提算法较其他同类算法的有效性，本 文设计了与传统 Petri 网网格工作流在服务组合执 行效率上的对比实验． 同样，当服务工作流请求到 达速率在 1 ～ 6 个·s － 1 时，通过 SPNP 仿真，得出服务 组合执行时间如图 10 所示． 图 10 服务组合执行效率对比 Fig． 10 Comparison of execution efficiency of service composition 依据图 10 可以看出，本文提出的基于模板的服 务组合优化算法在执行时间上大大优于传统的Petri 网网格工作流服务组合，尤其是在服务请求增多时， 其执行效率对比优势更为明显． 4 结论 本文结合网络环境下服务的特点，研究了服务 工作流模板模型及服务工作流模板间的关系． 为了 极大程度地复用已有历史服务工作流模板，将服务 组合优化问题转化为历史服务工作流模板组合优化 问题，提出了基于模板的服务工作流的优化组合算 法． 为了证明优化算法的有效性，以网络流媒体课 件制作服务工作流为实例，使用 Petri 网对其进行建 模，通过对比优化前后服务工作流模型的 SPNP 性 能分析结果，发现优化后服务工作流的吞吐量变化 不大，但是响应时间较优化前可大幅降低，从而证明 了优化算法的有效性． 参 考 文 献 ［1］ Hu C H，Wu M，Liu G P，et al． Approach to constructing web service workflow based on business spanning graph． J Software， 2007，18( 8) : 1870 ( 胡春华，吴敏，刘国平，等． 一种基于业务生成图的 Web 服 务工作流构造方法． 软件学报，2007，18( 8) : 1870) ［2］ Eckert J，Schulte S，Repp N，et al． Queuing-based capacity plan￾ning approach for Web service workflows using optimization algo￾rithms / / 2008 Second IEEE International Conference on Digital Ecosystems and Technologies． Phitsanulok，2008: 313 ［3］ Ling H Y． Realization of Web Services Composition System Based on Workflow Template ［Dissertation］． Wuhan: Wuhan University of Science and Technology，2009 ( 凌海洋． 基于工作流模板的 Web 服务组合系统实现［学位论 文］． 武汉: 武汉科技大学，2009) ［4］ Hu J，Feng Z Y． Semantic web service composition framework based on abstract template． J Comput Appl，2009，29( 11) : 3150 ( 胡佳，冯志勇． 一种基于抽象模板的语义 Web 服务组合框 架． 计算机应用，2009，29( 11) : 3150) ［5］ Zhou J B，Ling H，Xu Z C． Petri net-based workflow optimization analysis． Chin J Manage Sci，2005，13( 3) : 50 ( 周江波，凌鸿，胥正川． 基于 Petri 网的工作流优化分析． 中 国管理科学，2005，13( 13) : 50) ［6］ Chen F． Dynamic Semantic Web Service Composition Model and Achievement Based on Workflow ［Dissertation］． Wuhan: Hua￾zhong University of Science and Technology，2007 ( 陈飞． 基于工作流的语义 Web 服务动态组合模型及实现 ［学位论文］． 武汉: 华中科技大学，2007) ［7］ Lin C． Stochastic Petri Nets and Performance Evaluation of Sys￾tems． 2nd Ed． Beijing: Tsinghua University Press，2005 ( 林闯． 随机 Petri 网和系统性能评价． 2 版． 北京: 清华大学 出版社，2005) ［8］ Schimm G． Mining exact models of concurrent workflows． Comput Ind，2004，53( 3) : 265 ［9］ Hu Z G，Zhao R F，Chen R，et al． Research on grid service work￾flow model based on dynamic colored Petri net． J Chin Comput Syst，2007，28( 7) : 1205 ( 胡志刚，赵瑞芳，谌任，等． 基于动态有色 Petri 网的网格服务工 作流模型的研究． 小型微型计算机系统，2007，28( 7) : 1205) ［10］ Reibman A，Smith R，Trivedi K． Markov and Markov reward model transient analysis: an overview of numerical approaches． Eur J Oper Res，1989，40( 2) : 257 ·1217·