协同服务模型及其在电子商务中的应用

D01:10.13374.ism1001053x.2009.06.20 第31卷第5期 北京科技大学学报 Vol.31 No.5 2009年5月 Journal of University of Science and Technology Beijing May 2009 协同服务模型及其在电子商务中的应用 曾 明) 杨扬)王元卓2张静乐) 1)北京科技大学倍息工程学院，北京1000832清华大学计算机系，北京100084 摘要针对协同服务的结构关系和特点，研究了协同服务模型，将协同服务模型分为内部服务模型和外部服务模型，此方 法中可以较好地保护协同服务的内部信息.给出了基于随机Pi网的电子商务背景下企业协同服务中几种最具有代表性的 内部服务模型到外部服务模型之间的转化定理及相应的证明.将该模型分析方法应用于电子商务下单流程分析之中，数值计 算结果说明了该方法的有效性. 关键词随机Pti网：协同服务：内部服务：外部服务：电子商务 分类号TP393.01 Collaborative service model and application in e-commerce ZENG Ming,YANG Yang.WANG Y uan-zhuo2),ZHANGJing-le) 1)School of Information Engincering,University of Science and Techmlogy Beiing.Beijing 100083.Chima 2)Department of Computer Science and Technology.Tsinghua University,Beiing 100084.China ABSTRACT To meet characteristics of collaboration service's structural relationship,a collaborative service mode was studied, w hich is divided into internal and external service modes.This method can well protect collaboration service insider information.Sev- eral equivalent simplification theorems of ty pical collaboration e-commerce service modes based on Stochastic Pe tri-net and ther verifi- cation are provided.This method was applied to e-commerce order process analysis,and numerical results show effective. KEY WORDS stochastic Petri net;oollaborative service:internal service;external servioe;ecommerce 随着网络技术、多媒体技术的发展，多学科专家 网络协同服务最根本的出发点是提高服务效 已经能够克服空间、时间和异种计算机设备等的阻 率，从而提高生产效率，如果能抓住影响服务效率的 碍，可以“虚拟同地”一起工作，形成一种异地协同服 最主要的环节并重点对待，无疑将大大提高服务间 务方式，实现了功能和服务过程的交互.由于网络 协作的效率，缩短服务进度.因此，对协同服务过程 协同服务是跨平台、异构和动态的，并且现实中的应 中关键环节进行提取、分析且优化是实现其初衷的 用一般都非常复杂，为了分散和简化应用逻辑，提高 一个非常重要的方面.但是，目前网络协同服务过 服务的可重用性，单个基本服务或组件服务都不可 程分析与优化等研究方面还存在一些难点，例如面 能做得太复杂，因此需要组合多个简单的服务来满 向协同服务的流程建模·、协同服务系统性能分 足现实中的实际应用.其次不同的服务是基于不 析等，由于大型系统在模型建模之后会出现状态 同的异构系统而建立的，可能是以不同的方式创建、 空间爆炸问题，使得模型在进行性能分析的时候不 用不同程序语言实现以及由不同供应商提供的.为 能在理想的时间内完成，所以本文在模型建模的基 了将松散耦合的、分散的各类服务有机地组织成一 础上进行模型分析以到达期望时间内完成性能分析 个可用系统实现协同服务，使其被更为广泛地接 运算. 受，必须通过组合己有服务来创建新的增值服务来 本文主要研究了基于随机Peti网的协同服务 满足实际应用需求. 模型方法.此方法可以描述复杂的协同服务关系. 收稿日期：200903-26 基金项目：国家自然科学基金资助项目(N0.60673160:No.60803123) 作者简介：曾明(1978一），男，博士研究生；杨扬1955一)，男，教授.博士生导师E-maik yyang@sh.d血.m

协同服务模型及其在电子商务中的应用 曾 明1) 杨 扬1) 王元卓2) 张静乐1) 1) 北京科技大学信息工程学院, 北京 100083 2) 清华大学计算机系, 北京 100084 摘 要 针对协同服务的结构关系和特点, 研究了协同服务模型, 将协同服务模型分为内部服务模型和外部服务模型, 此方 法中可以较好地保护协同服务的内部信息.给出了基于随机 Petri 网的电子商务背景下企业协同服务中几种最具有代表性的 内部服务模型到外部服务模型之间的转化定理及相应的证明.将该模型分析方法应用于电子商务下单流程分析之中, 数值计 算结果说明了该方法的有效性. 关键词 随机 Petri 网;协同服务;内部服务;外部服务;电子商务 分类号 TP393.01 Collaborative service model and application in e-commerce ZENG Ming 1) , Y ANG Yang 1) , WANG Y uan-zhuo 2) , ZHANG Jing-le 1) 1) School of Information Engineering, Universit y of Science and Tech nology Beijing, Beijing 100083, C hina 2) Department of C omput er S cience and Technology, Tsinghua University, Beijing 100084, China ABSTRACT To meet characteristics of collaboration service' s structural relationship, a collabo rative service model was studied, w hich is divided into internal and external service models.This method can well protect collaboration service insider information .Sev￾eral equivalent simplification theorems of ty pical collaboration e-commerce service mo des based on Sto chastic Pe tri-net and their verifi￾cation are provided .This method was applied to e-commerce o rder process analy sis, and numerical results show effective. KEY WORDS stochastic Petri net ;collaborative service;internal service;external service;e-commerce 收稿日期:2009-03-26 基金项目:国家自然科学基金资助项目( No .60673160;No .60803123) 作者简介:曾 明( 1978—) , 男, 博士研究生;杨 扬( 1955—) , 男, 教授, 博士生导师, E-mail:yyang @ustb.edu.cn 随着网络技术、多媒体技术的发展, 多学科专家 已经能够克服空间 、时间和异种计算机设备等的阻 碍, 可以“虚拟同地”一起工作, 形成一种异地协同服 务方式, 实现了功能和服务过程的交互.由于网络 协同服务是跨平台、异构和动态的, 并且现实中的应 用一般都非常复杂, 为了分散和简化应用逻辑, 提高 服务的可重用性, 单个基本服务或组件服务都不可 能做得太复杂, 因此需要组合多个简单的服务来满 足现实中的实际应用.其次, 不同的服务是基于不 同的异构系统而建立的, 可能是以不同的方式创建 、 用不同程序语言实现以及由不同供应商提供的 .为 了将松散耦合的 、分散的各类服务有机地组织成一 个可用系统, 实现协同服务, 使其被更为广泛地接 受, 必须通过组合已有服务来创建新的增值服务来 满足实际应用需求. 网络协同服务最根本的出发点是提高服务效 率, 从而提高生产效率, 如果能抓住影响服务效率的 最主要的环节并重点对待, 无疑将大大提高服务间 协作的效率, 缩短服务进度.因此, 对协同服务过程 中关键环节进行提取 、分析且优化是实现其初衷的 一个非常重要的方面 .但是, 目前网络协同服务过 程分析与优化等研究方面还存在一些难点, 例如面 向协同服务的流程建模[ 1] 、协同服务系统性能分 析[ 2] 等, 由于大型系统在模型建模之后会出现状态 空间爆炸问题, 使得模型在进行性能分析的时候不 能在理想的时间内完成, 所以本文在模型建模的基 础上进行模型分析以到达期望时间内完成性能分析 运算. 本文主要研究了基于随机 Petri 网的协同服务 模型方法 .此方法可以描述复杂的协同服务关系. 第 31 卷 第 5 期 2009 年 5 月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol .31 No.5 May 2009 DOI :10.13374/j .issn1001 -053x.2009.05.020

第5期 曾明等：协同服务模型及其在电子商务中的应用 661。 同时，针对不同的需求将协同服务分为内部服务和 数量的标记时，那么这个变迁就成为一个可实施的 外部服务两类来区别对待.其中，内部服务模型包 变迁.变迁的真正实施从它成为可实施起要经过一 含更多的服务信息和组合关系，可以为网格服务管 个随机的时间.一个可实施的变迁的实施导致从它 理者的资源分配，任务调度提供参考信息：外部服务 所有输入位置中清除相应输入弧上标注数量的标 往往不关心服务的内部细节，而更关心服务的完成 记，在它的每一个输出位置中产生相应输出弧上标 情况，以及所能提供的服务质量(quality of service, 注数量的标记.在输入位置中清除标记和在输出位 QoS).同时，给出了典型的内部服务模式与外部服 置中产生标记是一个不可分割的完整操作.由于变 务间的转化定理，并进行了相应的证明.最后成功 迁的实施会使标记在位置中流动，因此在不同的时 地将该模型方法应用电子商务订单处理及发货流程 刻，标记在各个位置中的分布是不同的，定义这种不 的建模与分析中. 同的分布为标识(marking).标识就相当于系统所 1协同服务模型方法 处的状态(state).另外，随机Petri网在很多方面的 发展己很完备，它已有很多成熟的、有效的软件工 研究协同服务方法主要有三种：基于工作流的 具，可大大简化使用者进行建模和求解的过程，如 动态协同到、基于PI演算4或Petri网)等工具的 ESPN、GreatSPN、SPNP、SURF-2、TOMSPIN和 形式化方法.基于进程代数或Peti网等工具的形 UItraSA N等，因此它是大型复杂系统及服务分析的 式化是协同服务的一种常用方法其中Peti网己成 有力工具9 为对包含通讯、并发、同步和资源共享的系统进行建 2内部服务与外部服务 模的有力工具，使用Peti网来模拟和验证业务流程 组合是另外一种选择.如文献5]提出了一个基于 本文将研究一种更适应于描述协同服务需求的 Pti网的协同服务模型，并通过对10种组合元模 模型方法.在研究的模型中，依照用户对任务的需 型的代数结构与Peti网形式化语义的分析，建立起 求，协同服务是由简单服务共同完成用户的任务 从代数结构模型向Peti网的关系映射，从而为服务 其中，简单服务可以描述一种专门的功能，而多个简 组合过程中属性验证以及一致性检测和优化提供了 单服务组合在一起则构成了一个复杂的协同服务 一种形式化工具.为了更好地描述服务的随机特 每一个简单服务都是这个复杂协同服务的一部分. 性，引入随机Petri网. 因此，将协同服务划分为内部服务和外部服务 随机Petri网以研究模型系统的组织结构和动 两类.内部服务的所有信息将不会对外公布，而外 态行为为目标着眼于系统中可能发生的各种状态 部服务的执行信息和情况则是可以查知的.与外部 变化以及变化之间的关系.它描述的是系统的动态 服务相比内部服务的结构往往比较复杂，并且通常 变化过程.Petm网模型以图形方式表示一个复杂 一些内部服务可以有由外部服务的协同关系通过化 系统，它的结构元素包括位置(place)、变迁(transi- 简得到.用户可以通过外部服务发布的信息了解系 tion)和弧(ac).位置用于描述可能的系统局部状 统可以提供什么质量的服务，以及这些服务需要什 态（条件或状况）.变迁用于描述系统状态改变的事 么样的输入和将会获得什么样的输出.同样，根据 件.弧使用两种方法规定局部状态和事件之间的关 这些输入与输出之间的映射关系，管理人员也可以 系：他们引述事件能够发生的局部状态；由事件所引 更容易地跟踪和监控服务执行的状态，协同关系的 发的局部状态的转换 设计者可以设计出更有效的组合关系.这样的描述 在随机Ptni网模型中，位置可能含有任意数量 类似于一种半黑箱似的操作.另一方面，内部服务 的标记(token).随着事件的发生，标记可以在不同 的执行信息不被外界所知，这也在一定程度上满足 的位置中按照弧的方向流动，从而动态地描述了系 服务安全的要求.同时，外部服务不发生变化时，就 统的不同状态.一个Petri网模型的动态行为是由 不需要告诉用户内部服务发生过哪些细节的改变. 它的实施规则(firing rule)规定的.每个变迁有相应 2.1外部服务模型 的输入位置和输出位置.输入位置定义为所有的与 协同服务指为了完成某一任务目标，由两个或 该变迁之间有弧连接并且弧的方向从位置到变迁的 两个以上服务主体通过一定的信息交换和相互协调 位置（相应弧称为输入弧）.输出位置和它的弧的方 机制，分别完成不同的子任务从而达到最终目标 向与输入位置不同，它是从变迁到位置.如果一个 协同服务主要是描述两个或者多个服务之间进行协 变迁的每个输入位置中至少包含相应输入弧上标注 同一完成某个目标服务，其中外部服务模型简单，描

同时, 针对不同的需求将协同服务分为内部服务和 外部服务两类来区别对待.其中, 内部服务模型包 含更多的服务信息和组合关系, 可以为网格服务管 理者的资源分配, 任务调度提供参考信息;外部服务 往往不关心服务的内部细节, 而更关心服务的完成 情况, 以及所能提供的服务质量( quality of service, QoS) .同时, 给出了典型的内部服务模式与外部服 务间的转化定理, 并进行了相应的证明.最后成功 地将该模型方法应用电子商务订单处理及发货流程 的建模与分析中 . 1 协同服务模型方法 研究协同服务方法主要有三种:基于工作流的 动态协同[ 3] 、基于 PI 演算[ 4] 或 Petri 网[ 5] 等工具的 形式化方法 .基于进程代数或 Petri 网等工具的形 式化是协同服务的一种常用方法, 其中 Petri 网已成 为对包含通讯、并发 、同步和资源共享的系统进行建 模的有力工具, 使用 Petri 网来模拟和验证业务流程 组合是另外一种选择 .如文献[ 5] 提出了一个基于 Petri 网的协同服务模型, 并通过对 10 种组合元模 型的代数结构与 Petri 网形式化语义的分析, 建立起 从代数结构模型向 Petri 网的关系映射, 从而为服务 组合过程中属性验证以及一致性检测和优化提供了 一种形式化工具.为了更好地描述服务的随机特 性, 引入随机 Petri 网 . 随机 Petri 网以研究模型系统的组织结构和动 态行为为目标, 着眼于系统中可能发生的各种状态 变化以及变化之间的关系 .它描述的是系统的动态 变化过程.Petri 网模型以图形方式表示一个复杂 系统, 它的结构元素包括位置( place) 、变迁( transi￾tion) 和弧( arc) .位置用于描述可能的系统局部状 态(条件或状况) .变迁用于描述系统状态改变的事 件.弧使用两种方法规定局部状态和事件之间的关 系:他们引述事件能够发生的局部状态 ;由事件所引 发的局部状态的转换 . 在随机 Petri 网模型中, 位置可能含有任意数量 的标记( token) .随着事件的发生, 标记可以在不同 的位置中按照弧的方向流动, 从而动态地描述了系 统的不同状态 .一个 Petri 网模型的动态行为是由 它的实施规则( firing rule) 规定的.每个变迁有相应 的输入位置和输出位置.输入位置定义为所有的与 该变迁之间有弧连接并且弧的方向从位置到变迁的 位置(相应弧称为输入弧) .输出位置和它的弧的方 向与输入位置不同, 它是从变迁到位置.如果一个 变迁的每个输入位置中至少包含相应输入弧上标注 数量的标记时, 那么这个变迁就成为一个可实施的 变迁.变迁的真正实施从它成为可实施起要经过一 个随机的时间.一个可实施的变迁的实施导致从它 所有输入位置中清除相应输入弧上标注数量的标 记, 在它的每一个输出位置中产生相应输出弧上标 注数量的标记.在输入位置中清除标记和在输出位 置中产生标记是一个不可分割的完整操作 .由于变 迁的实施会使标记在位置中流动, 因此在不同的时 刻, 标记在各个位置中的分布是不同的, 定义这种不 同的分布为标识( marking ) .标识就相当于系统所 处的状态( state) .另外, 随机 Petri 网在很多方面的 发展已很完备, 它已有很多成熟的、有效的软件工 具, 可大大简化使用者进行建模和求解的过程, 如 ESPN 、GreatSPN 、SPNP 、S URF-2 、 TOMSPIN 和 UltraSAN 等, 因此它是大型复杂系统及服务分析的 有力工具[ 6] . 2 内部服务与外部服务 本文将研究一种更适应于描述协同服务需求的 模型方法 .在研究的模型中, 依照用户对任务的需 求, 协同服务是由简单服务共同完成用户的任务. 其中, 简单服务可以描述一种专门的功能, 而多个简 单服务组合在一起则构成了一个复杂的协同服务, 每一个简单服务都是这个复杂协同服务的一部分. 因此, 将协同服务划分为内部服务和外部服务 两类 .内部服务的所有信息将不会对外公布, 而外 部服务的执行信息和情况则是可以查知的 .与外部 服务相比内部服务的结构往往比较复杂, 并且通常 一些内部服务可以有由外部服务的协同关系通过化 简得到 .用户可以通过外部服务发布的信息了解系 统可以提供什么质量的服务, 以及这些服务需要什 么样的输入和将会获得什么样的输出 .同样, 根据 这些输入与输出之间的映射关系, 管理人员也可以 更容易地跟踪和监控服务执行的状态, 协同关系的 设计者可以设计出更有效的组合关系.这样的描述 类似于一种半黑箱似的操作 .另一方面, 内部服务 的执行信息不被外界所知, 这也在一定程度上满足 服务安全的要求.同时, 外部服务不发生变化时, 就 不需要告诉用户内部服务发生过哪些细节的改变. 2.1 外部服务模型 协同服务指为了完成某一任务目标, 由两个或 两个以上服务主体通过一定的信息交换和相互协调 机制, 分别完成不同的子任务从而达到最终目标. 协同服务主要是描述两个或者多个服务之间进行协 同一完成某个目标服务, 其中外部服务模型简单, 描 第 5 期 曾 明等:协同服务模型及其在电子商务中的应用 · 661 ·

。662* 北京科技大学学报 第31卷 述了一个被封装过的服务过程 组合协同服务：由i个并行协同服务经过串联 外部服务：对于某个单独的服务，或不考虑服务 而成每个并行协同服务由n个不同的服务流程并 细节的协同服务，存在输入、处理和输出三个部分， 行执行，并在交互位置触发为m个其他的并行服务 将一个独立的服务通过随机Petri网描述如图I.图 流程，其模型如图5 中p1为该服务的输入，t为服务的处理，p2为处理 后的输出结果 883 图5组合协同服务 图1外部服务 Fig.5 Comprehensive collaborative service Fig.I Exterior service 2.2内部服务模型 3内、外部服务模型间转化方法 内部服务模型包含更多的协同服务信息和细 3.1顺序服务模型转化 节，这里主要研究顺序协同服务、并行协同服务、分 顺序服务模型是指由n个内部服务t1,12,； 支协同服务和组合协同服务等 tm组成并按照前后的秩序顺序执行，对顺序服务 顺序协同服务：多个不同的服务流程通过前后 模型的化简方法如图6 顺序关系产生协同服务为顺序协同服务，模型如 图2.图中pim为服务的输入，pask为服务协同的中 间状态，p为服务的输出结果 图6顺序服务模型到外部服务模型的转化 Fig.6 Conversion fmom a Sequence service model to an external ser vice model 图2顺序协同服务 定理1顺序服务由n个内部服务t1,t2,； Fig.2 Sequence collaborative service tm组成，其关系如图6所示.每个服务的执行速率 并行协同服务：多个不同的协同服务流程，并最 入：(1≤i≤n)是服从指数分布的随机变量，则其等 终通过结束位置交汇产生协同服务，其模型如图3. 价简化模型中的变迁C$表示的外部服务的服务速 率为： 88 6 x=2V. 证明设时间变迁t1,t2,；tm的响应速率 为n个相互独立的随机变量X1,X2,…,Xm,且等价 模型中变迁CS的响应速率为随机变量Y,则： 图3并行协同服务 Y=X1十X2十十Xm, Fig 3 Paralel collaborative service 分支协同服务：在起始位置分叉产生多个不同 太E(Y)=E(X+X++X)= 的协同服务流程，其模型如图4. E(X)+E(X2)+…+E(Xm)= (1) 3.2并行服务模型转化 o K 对应变迁并联结构本文给出了并行服务模型的 性能等价化简，并行服务由两个内部服务t1和2 组成且这两个服务并行执行，对并行服务模型的化 简方法如图7. 图4分支协同服务 定理2并行服务由两个内部服务t1、2和一 Fig.4 Branch collaborative service 个汇总服务tm组成其关系如图7所示.每个服务

述了一个被封装过的服务过程 . 外部服务:对于某个单独的服务, 或不考虑服务 细节的协同服务, 存在输入 、处理和输出三个部分, 将一个独立的服务通过随机 Petri 网描述如图 1 .图 中 p1 为该服务的输入, t 为服务的处理, p2 为处理 后的输出结果. 图 1 外部服务 Fig.1 Exterior service 2.2 内部服务模型 内部服务模型包含更多的协同服务信息和细 节, 这里主要研究顺序协同服务、并行协同服务 、分 支协同服务和组合协同服务等 . 顺序协同服务 :多个不同的服务流程通过前后 顺序关系产生协同服务为顺序协同服务, 模型如 图 2 .图中 pin为服务的输入, ptask为服务协同的中 间状态, p out为服务的输出结果 . 图 2 顺序协同服务 Fig.2 S equence collaborative servi ce 并行协同服务:多个不同的协同服务流程, 并最 终通过结束位置交汇产生协同服务, 其模型如图 3 . 图 3 并行协同服务 Fig.3 Parallel collaborative service 图 4 分支协同服务 Fig.4 Branch collaborative service 分支协同服务 :在起始位置分叉产生多个不同 的协同服务流程, 其模型如图 4 . 组合协同服务:由 i 个并行协同服务经过串联 而成, 每个并行协同服务由 n 个不同的服务流程并 行执行, 并在交互位置触发为 m 个其他的并行服务 流程, 其模型如图 5 . 图 5 组合协同服务 Fig.5 Comprehensive collaborative service 3 内 、外部服务模型间转化方法 3.1 顺序服务模型转化 顺序服务模型是指由 n 个内部服务t 1, t 2, …, t n 组成, 并按照前后的秩序顺序执行, 对顺序服务 模型的化简方法如图 6 . 图 6 顺序服务模型到外部服务模型的转化 Fig.6 Conversion from a Sequence service model to an external ser￾vice model 定理 1 顺序服务由 n 个内部服务 t 1, t 2, …, t n 组成, 其关系如图 6 所示.每个服务的执行速率 λi( 1 ≤i ≤n) 是服从指数分布的随机变量, 则其等 价简化模型中的变迁 CS 表示的外部服务的服务速 率为: λ=1 ∑ n i =1 1/ λi . 证明 设时间变迁 t 1, t 2, …, tn 的响应速率 为n 个相互独立的随机变量X 1, X 2, …, X n, 且等价 模型中变迁 CS 的响应速率为随机变量 Y , 则 : Y =X 1 +X 2 +…+X n, 1 λ =E ( Y ) =E ( X 1 +X 2 +…+Xn ) = E ( X 1) +E( X 2) +…+E ( X n) = ∑ n i =1 1 λi ( 1) 3.2 并行服务模型转化 对应变迁并联结构本文给出了并行服务模型的 性能等价化简, 并行服务由两个内部服务 t 1 和 t 2 组成, 且这两个服务并行执行, 对并行服务模型的化 简方法如图 7 . 定理 2 并行服务由两个内部服务 t 1 、t 2 和一 个汇总服务 tin组成, 其关系如图 7 所示 .每个服务 · 662 · 北 京 科 技 大 学 学 报 第 31 卷

第5期 曾明等：协同服务模型及其在电子商务中的应用 663· (入1十入ut)(入2十入wut) 4) 61-6 2入1入2入ut十入3：（入1+入2） 1ò561-6 6i-6 图7并行服务模型到外部服务模型的转化 Fig.7 Conversion from a parallel service model to an ex temal ser vice mode 图8分支服务模型到外部服务模型的转化 Fig.8 Conversion from a branch service model to an external service 的执行速率入1、入2和入i是服从指数分布的随机变 model 量，则其等价简化模型中的变迁C$表示的外部服 务的服务速率为： 证明设时间变迁11,12，…，1m的响应速率为 入in入12入1+2) n个相互独立的随机变量X1,X2,:Xm,其分布函 A-+X入2+x+(入1+ 数为F:(x)=1一e,由1、2分别和tamr构成的 证明设t1、t2和tim的响应速率为相互独立的 顺序服务其响应时间分别为t1wt、t2u。根据定理1 随机变量X1、X2和Xm,其分布函数为F:(x)=1一 有： 。好，1、2组成并发服务的响应速率为入”. 入1入auL,x2ml=2+入ut 入2入wt 根据文献79，并发结构等效时间变迁1的平 入1owl=入1十入mi 均延时时间 由定理2，并发结构等效时间变迁t的平均延时时 =会va-会++ 间入1out2out为： 入t十入Nut入2u十入aut= 盒三多.+++十 入mi2a=X1 1ot2u(入u十A2 (入1out十入2mJ2-入1mi入2ul= 入1out入2ut(入1out十入2oa） 令n=2,则 λ+入1入2十入3 女太十o A2=X+ (2) 分别将入1ou和2oum代入得到： 根据定理L,由入12和入组成的顺序服务的等 A=2入2+入(A1十入2_ 效时间变迁CS的平均延时时间入为： 入1入2入ul 上=L十1=+十+入（入1十x2 (入1十入ui(入2+入ut) 入入2Xn 入a入1入z入1十2) 2入1入2入ut+入u(入1十入2) 入n入1入2（入1十入2J λ=X(X好+X2十)+入1（入1+2） (3) 证毕. 3.4组合服务模型转化 证毕. 定理4组合服务由k个局部并行服务构成且 3.3分支服务模型转化 每个并行服务由n个内部服务t1,t2,；m组成其 分支服务是由一个分叉服务tm和两个内部服 关系如图9所示.每个服务的执行速率入(1≤ 务t1、t2组成且t分别和1、t2服务串行执行，然 k,1≤≤)是服从指数分布的随机变量，则其等价 后二者又并发执行，分支服务模型的化简方法如 简化模型中的变迁C$表示的外部服务的服务速率 图8. 为： 定理3分支服务关系如图8所示.每个服务 的执行速率入1、入2和入，是服从指数分布的随机 (5) 变量，则其等价简化模型中的变迁C$表示的外部 服务的服务速率为： 其中， 入=2入1十入（入十2 入1入2入ut w=启女2十+

图 7 并行服务模型到外部服务模型的转化 Fig.7 Conversion from a parallel service model to an ex ternal ser￾vice model 的执行速率 λ1 、λ2 和 λin是服从指数分布的随机变 量, 则其等价简化模型中的变迁 CS 表示的外部服 务的服务速率为 : λ= λinλ1λ2( λ1 +λ2) λin( λ2 1 +λ1λ2 +λ2 2) +λ1λ2( λ1 +λ2) . 证明 设 t 1 、t2 和 tin的响应速率为相互独立的 随机变量 X 1 、X 2 和 X in, 其分布函数为Fi( x ) =1 - e -λi x , t 1 、t 2 组成并发服务的响应速率为 λ12 . 根据文献[ 7-9] , 并发结构等效时间变迁 t 的平 均延时时间 λt =1 ∑ n i =1 1/ λi - ∑ n-1 i =1 ∑ n j =i+1 1/ ( λi +λj) + ∑ n-2 i =1 ∑ n-1 j =i+1 ∑ n k =j+1 1/ ( λi +λj +λk ) +…+ ( -1) n -1 ×1 ∑ n i =1 λi , 令 n =2, 则 λ12 = λ2 1 +λ1λ2 +λ2 2 λ1λ2( λ1 +λ2) ( 2) 根据定理 1, 由 λ12和 λin组成的顺序服务的等 效时间变迁CS 的平均延时时间 λ为: 1 λ = 1 λ12 + 1 λin = λin( λ2 1 +λ1λ2 +λ2 2) +λ1λ2( λ1+λ2) λinλ1λ2( λ1+λ2) , λ= λinλ1λ2( λ1 +λ2) λin( λ2 1 +λ1λ2 +λ2 2) +λ1λ2( λ1 +λ2) ( 3) 证毕 . 3.3 分支服务模型转化 分支服务是由一个分叉服务 t out和两个内部服 务 t 1 、t 2 组成, 且 t out分别和 t1 、t 2 服务串行执行, 然 后二者又并发执行, 分支服务模型的化简方法如 图 8 . 定理 3 分支服务关系如图 8 所示 .每个服务 的执行速率 λ1 、λ2 和 λout , 是服从指数分布的随机 变量, 则其等价简化模型中的变迁 CS 表示的外部 服务的服务速率为: λ= 2λ1λ2 +λout( λ1 +λ2) λ1λ2λout - ( λ1 +λout)( λ2 +λout) 2 λ1λ2 λout +λ2 out( λ1 +λ2) ( 4) 图 8 分支服务模型到外部服务模型的转化 Fig.8 Conversion from a branch service model to an external service model 证明 设时间变迁 t 1, t 2, …, t n 的响应速率为 n 个相互独立的随机变量 X 1, X 2, …, Xn , 其分布函 数为 Fi ( x ) =1 -e -λi x , 由 t 1 、t2 分别和 t out构成的 顺序服务其响应时间分别为 t 1out 、t 2out, 根据定理 1 有 : λ1out = λ1λout λ1 +λout , λ2out = λ2 λout λ2 +λout . 由定理 2, 并发结构等效时间变迁 t 的平均延时时 间 λ1out2out为: λ1out2out = λ2 lout +λlout λ2out +λ2 2out λ1out λ2out( λlout +λ2out) = ( λ1out +λ2out) 2 -λ1outλ2out λ1out λ2out( λ1out +λ2out) = 1 λ1out + 1 λ2out - 1 λ1out +λ2out . 分别将 λ1out和 λ2out代入得到 : λ= 2 λ1λ2 +λout( λ1 +λ2) λ1λ2λout - ( λ1 +λout)( λ2+λout) 2λ1 λ2λout +λ2 out( λ1 +λ2) . 证毕. 3.4 组合服务模型转化 定理 4 组合服务由 k 个局部并行服务构成且 每个并行服务由n 个内部服务 t 1, t 2, …, tn 组成, 其 关系如图 9 所示.每个服务的执行速率 λij ( 1 ≤i ≤ k , 1 ≤j ≤n )是服从指数分布的随机变量, 则其等价 简化模型中的变迁 CS 表示的外部服务的服务速率 为 : λ= 1 ∑ n i =1 1 λij ( 5) 其中, λij = ∑ n j =1 1 λij - ∑ n-1 s =1 ∑ n t =s+1 1 λis +λit + 第 5 期 曾 明等:协同服务模型及其在电子商务中的应用 · 663 ·

。664 北京科技大学学报 第31卷 -6ó-16 图9组合服务模型到外部服务模型的转化 Fig.9 Conversion fmom a comprehensive service model to an ex temal service model 2名a++… 1 再由定理1，组合服务的服务速率为： 入= 证明设时间变迁t1,t2,tn的响应速率为 n个相互独立的随机变量X1,X2,,Xm,其分布函 证毕. 数为F(x)=1一e,等价模型中变迁CS的响应 速率为Y,则根据组合服务的定义，可将组合服务 4电子商务中的协同服务分析 中的每一个局部并行服务进行简化，简化后的服务 ECMS(e-commerce management system)是一种 模型其外部服务的服务速率为： 流行的电子商务模式.ECMS使得用户可以直接通 1一十 过网络购买商品，在线运营商可以根据用户订单管 理自己的库存和采购计划，供应商可以根据运营商 是名++ 1 十十(-1)-1 的采购订单及时供货，ECMS为协调用户，电子商务 运营商和供应商提供了有效的保证. 经过简化后的局部并行服务可由一个局部的顺序服 4.1ECMS建模与等价化简 务代替.由于每个局部并行服务之间是串联而成， 以ECMS的下单流程为例，对该流程进行建模 所以对每个局部并行服务进行等价替换之后可以得 和分析. 到一个顺序服务模型每个等价替换的变迁为入 图10为ECMS的下单流程.三个并行的流程 网上客户 下定单 处理订单 是否缺货 缺货 不缺货 给供应商 发补货单 发货 调整采购 数量 供应商 到货 客户收货 处理残次 异常 验货 货物 、确认收货 异常 处理异常 正常 正常 人库 退货 结束 结束 图10ECMS下单流程图 Fig 10 ECMS order pmoess chart

图 9 组合服务模型到外部服务模型的转化 Fig.9 Conversion from a comprehensi ve service model to an ex ternal service model ∑ n -2 s=1 ∑ n -1 t =s+1 ∑ n u =t+1 1 λis +λit +λi u +…+( -1) n -1 1 ∑ n i =1 λi . 证明 设时间变迁 t 1, t 2, …, t n 的响应速率为 n 个相互独立的随机变量X 1, X 2, …, X n, 其分布函 数为 Fi( x ) =1 -e -λi x , 等价模型中变迁 CS 的响应 速率为 Y , 则根据组合服务的定义, 可将组合服务 中的每一个局部并行服务进行简化, 简化后的服务 模型其外部服务的服务速率为 : λij = ∑ n j =1 1 λij - ∑ n -1 s=1 ∑ n t =s+1 1 λis +λit + ∑ n -2 s=1 ∑ n -1 t =s+1 ∑ n u =t+1 1 λis +λit +λi u +…+( -1) n -1 1 ∑ n i =1 λi . 经过简化后的局部并行服务可由一个局部的顺序服 务代替 .由于每个局部并行服务之间是串联而成, 所以对每个局部并行服务进行等价替换之后可以得 到一个顺序服务模型, 每个等价替换的变迁为 λi , 再由定理 1, 组合服务的服务速率为 : λ= 1 ∑ n i =1 1 λij . 证毕. 4 电子商务中的协同服务分析 ECM S( e-commerce management system) 是一种 流行的电子商务模式.ECM S 使得用户可以直接通 过网络购买商品, 在线运营商可以根据用户订单管 理自己的库存和采购计划, 供应商可以根据运营商 的采购订单及时供货, ECMS 为协调用户, 电子商务 运营商和供应商提供了有效的保证. 4.1 ECMS 建模与等价化简 以 ECM S 的下单流程为例, 对该流程进行建模 和分析 . 图 10 为 ECM S 的下单流程.三个并行的流程 图 10 ECMS 下单流程图 Fig.10 ECMS order p rocess chart · 664 · 北 京 科 技 大 学 学 报 第 31 卷

第5期 曾明等：协同服务模型及其在电子商务中的应用 665。 分别对应了门店、物流中心和供应商，对于三种不同 识M∈[Mo>,所有M,Mk∈[Mo>且M∈ 的客户有各自的流程为他们服务，但是对于整个系 [PM,M∈[t⊙M,则有方程： 统三个流程之间既有并行也有分支等系统服务，基 (7) 于下单流程图，利用随机Peti网可以构造如图Il 卫为= 所示的模型. 显然，可以用上式列出n一1个平衡状态方程，再加 上方程∑y=1,即可求解每个可达标识的稳定概 率. 图12ECMS下单流程Ptn网化简模型图 Fig.12 Simpification Petri model of ECMS order process 基于马尔可夫链和状态转换速率，能够制造状 态转换矩阵并获得所有状态的稳定状态概率，从而 可以讨论模型系统的性能参数， 状态M的稳定状态概率使用P[M表示.在 稳定状态下时间变迁t的吞吐量T:可以表示为： PLn T= (8) 其中，H是使能变迁1实施的所有标示集合，入，是 图I1ECMS下单流程Peti网模型 变迁t在标识M下的实施速率. Fig.11 Petri model of ECMS order process 在一般SPN(stochastic Petri net)中，稳定状态 从图11中可以看出，这个系统含有多处上文中 下队列位置p的平均标记数量Dp,可以表示为： 提到的并行、分支等协同服务结构模型.将图11中 Dp=∑iXP[M(p)=可 (9) 的并行、分支和顺序结构利用化简模型替换后的 系统的吞吐量是性能的一个重要参数，变迁： Pti网模型图如图12.可以看出，系统结构己经有 的吞吐量为T,系统的吞吐量T可以表示为： 了较大规模的化简. 42性能分析 T空 (10) 设MC(Markov chain,简称MC)中n个状态的 响应时间是系统的另一个重要性能指标.变迁 稳定状态概率是一个行向量Ⅱ=（π1，π2，；πm, ti的响应时间R:可以表示为： 且每个变迁的延时服从于指数分布函数.根据马尔 (11) 可夫过程有下列线性方程组： Ri=Dp/T Ⅱ×Q=0 在SPWN求解分析软件包SPNP9中，稳定状态 2=1 (6) 下每个变迁的吞吐量和每个位置的平均标记数量都 是系统性能参数测量的基础，可由软件自动计算，仅 解线性方程组，即可得每个可达标识的稳定概 需指明要测量的变迁和位置名即可 率P:(t=o)=π：(1≤≤n).另一方面，对任一标 令化简前后模型图中每个变迁入，的执行速率

分别对应了门店 、物流中心和供应商, 对于三种不同 的客户有各自的流程为他们服务, 但是对于整个系 统三个流程之间既有并行也有分支等系统服务 .基 于下单流程图, 利用随机 Petri 网可以构造如图 11 所示的模型. 图 11 ECMS 下单流程 Petri 网模型 Fig.11 Petri model of ECMS order process 从图 11 中可以看出, 这个系统含有多处上文中 提到的并行 、分支等协同服务结构模型.将图 11 中 的并行 、分支和顺序结构利用化简模型替换后的 Petri 网模型图如图 12 .可以看出, 系统结构已经有 了较大规模的化简. 4.2 性能分析 设M C( Markov chain, 简称 M C) 中 n 个状态的 稳定状态概率是一个行向量 Π=( π1, π2, …, πn ), 且每个变迁的延时服从于指数分布函数 .根据马尔 可夫过程有下列线性方程组: Π×Q =0 ∑ n i =0 πi =1 ( 6) 解线性方程组, 即可得每个可达标识的稳定概 率 Pi( t =∞) =πi( 1 ≤i ≤n) .另一方面, 对任一标 识 Mi ∈ [ M0 >, 所有 Mj , Mk ∈ [ M0 >且 Mi ∈ [ tj >Mj , Mk ∈[ t k >Mi , 则有方程: ∑ j λj πi = ∑k λkπk ( 7) 显然, 可以用上式列出 n -1 个平衡状态方程, 再加 上方程 ∑ λj =1, 即可求解每个可达标识的稳定概 率 . 图 12 ECMS 下单流程 Petri 网化简模型图 Fig.12 S implification Petri model of ECMS order process 基于马尔可夫链和状态转换速率, 能够制造状 态转换矩阵并获得所有状态的稳定状态概率, 从而 可以讨论模型系统的性能参数. 状态 M 的稳定状态概率使用 P[ M] 表示 .在 稳定状态下时间变迁 t 的吞吐量 Tt 可以表示为: Tt =M∑ ∈ H P[ M] λt ( 8) 其中, H 是使能变迁 t 实施的所有标示集合, λt 是 变迁t 在标识M 下的实施速率 . 在一般 SPN ( stochastic Petri net) 中, 稳定状态 下队列位置 p 的平均标记数量Dp, 可以表示为: Dp = ∑ i ×P[ M( p) =i] ( 9) 系统的吞吐量是性能的一个重要参数, 变迁 ti 的吞吐量为 Tt i , 系统的吞吐量 T 可以表示为 : T = ∑ n i =1 Tt i ( 10) 响应时间是系统的另一个重要性能指标 .变迁 ti 的响应时间Ri 可以表示为: Ri =Dp i / Tt i ( 11) 在 SPN 求解分析软件包 SPNP [ 9] 中, 稳定状态 下每个变迁的吞吐量和每个位置的平均标记数量都 是系统性能参数测量的基础, 可由软件自动计算, 仅 需指明要测量的变迁和位置名即可. 令化简前后模型图中每个变迁 λi 的执行速率 第 5 期 曾 明等:协同服务模型及其在电子商务中的应用 · 665 ·

。666· 北京科技大学学报 第31卷 为L,通过改变订单到达速率入r,可以利用SPNP 间和吞吐量上的变化不大，但简化模型运算时间大 得到如图13和图14两幅对比图. 幅降低，这样使得在期望的时间内可以对大型系统 60 进行性能上的模拟，并依此判断系统设计是否合理. % 口化简后模型 040 图原模型 参考文献 20 【刂LinC,Sheng L J,WuJ卫，ctl.An integrative scheme of dif ferentiated service modeing and performance analysis//Poced- ings of 8th International Symposium on Modeling,Analysis and Simulation of Computer and Tekcomm unication Systems. 订单速率s IEEE.2000:441 [2 Lin C.A model of systems with shared resources and analysis of 图13响应时间对比图 approximate peromance.Chin J Comput,1997,20(10):865 Fig 13 Com parison of response time (林闯。一种资源共享系统的模型和近似性能分析.计算机学 报，1997,20(10)：865) 4000 L3习Van der Aalst W M卫.Verification of workflow nets∥App lica-- 一◆一化简后模型 3000 tion and Theory of Petri Nets 1997.LNCS 1248.Berin: 一原模型 Springer-Vedag.1997:407 2000 [4 Liao J.Tan H.Liu J D.Deseribing and verifying web service us ing PI-calculus.Chin J Comput,2005,28(4):635 1000 (廖军，谭浩，刘锦德.基于P演算的Wh服务组合的描述和 验证.计算机学报.2005.28(4)：635) 3 4 订单速率s [5 Rachid H,Boualem B.A Petri net based model for web service composition//Procedings of 14th Australian Database Confer ence on Database Tech nologies.Adelaide,2003:191 图14运算时间对比图 [6 Yamada S.OsakiS.Softw are reliability growth modeling:mod Fig.14 Comparison of computing time ds and assumptions.IEEE Trans Software Eng.1985.SE-I1: 图13对比了模型化简前后的系统响应时间，对 1431 比发现二者订单数量的流入速率在1~6s1范围 【刀LinC.An appmach to performance equiva上nt simplification and analysis of stochastic Petri nets.ACTA Electron Sin,2002. 内，变化不大 30(11):1620 图14对比了模型化简前后SPNP运算所花费 (林闯.一种随机Pdi网性能等价化简与分析方法.电子学 的时间.对比发现当订单的流入速率在1~6s1范 报.2002.30(11)：1620 围内，二者的运算时间有较大的差距，简化模型运算 [8 Lin C.On refinement of model structure for stochastic Petri nets. 时间可大幅降低 J Software.2000.11(1):104 (林闯.随机Pt网模型的精化设计.软件学报，2000,11(1)： 5结论 104) [9 Tian L Q.Performance equivalent simplification of sequent and 针对不同的需求将协同服务模型分为内部服务 parallel transitions in stochastic Petri nets.Acta Electron Sin, 模型和外部服务模型两类来区别对待，并研究了基 2002,30(8):1134 于随机Petri网的几种典型内部服务模型到外部服 (田立勤.随机Pt网模型中变迁的串、并联性能等价化简技 术.电子学报，2002,308)：1134) 务模型之间的等价转化方法.在此基础上，对 [10 Ciaod G,Muppala J.Trivedi K S.SPNP:stochastic Petri net ECMS下单流程进行了建模与模型化简.通过对比 package //Proceedings of 3rd Inter national Workshop on Petri 模型化简前后的性能分析结果，发现二者在响应时 Nets and Performance Models,1989:142

为 1, 通过改变订单到达速率 λo rder, 可以利用 SPNP 得到如图 13 和图 14 两幅对比图. 图 13 响应时间对比图 Fig.13 Com parison of response time 图 14 运算时间对比图 Fig.14 Comparison of computing time 图 13 对比了模型化简前后的系统响应时间, 对 比发现二者订单数量的流入速率在 1 ～ 6 s -1范围 内, 变化不大. 图14 对比了模型化简前后 SPNP 运算所花费 的时间.对比发现, 当订单的流入速率在 1 ～ 6s -1范 围内, 二者的运算时间有较大的差距, 简化模型运算 时间可大幅降低 . 5 结论 针对不同的需求将协同服务模型分为内部服务 模型和外部服务模型两类来区别对待, 并研究了基 于随机 Petri 网的几种典型内部服务模型到外部服 务模型 之间的等价 转化方法 .在此基础 上, 对 ECMS 下单流程进行了建模与模型化简.通过对比 模型化简前后的性能分析结果, 发现二者在响应时 间和吞吐量上的变化不大, 但简化模型运算时间大 幅降低, 这样使得在期望的时间内可以对大型系统 进行性能上的模拟, 并依此判断系统设计是否合理. 参 考 文 献 [ 1] Lin C, Sheng L J, Wu J P, et al.An int egrati ve scheme of dif￾ferentiated service:modeling and performance analysis∥Proceed￾ings of 8th Internationa l Symposium on Modeling , Ana lysis and Simu lation of Compu ter an d Telecomm unication Systems . IEEE, 2000:441 [ 2] Lin C .A model of syst ems with shared resources and analysis of approximate perf ormance.Chin J Compu t, 1997, 20(10) :865 ( 林闯.一种资源共享系统的模型和近似性能分析.计算机学 报, 1997, 20( 10) :865) [ 3] Van der Aalst W M P.Verification of workflow nets ∥App lica￾tion and Theory o f Petri Nets 1997 .LNCS 1248 .Berlin: Springer-Verlag, 1997:407 [ 4] Liao J, Tan H, Liu J D.Describing and verifying web service us￾ing PI-calculus.Chin J Comp ut, 2005, 28( 4) :635 ( 廖军, 谭浩, 刘锦德.基于 PI-演算的 Web 服务组合的描述和 验证.计算机学报, 2005, 28( 4) :635) [ 5] Rachid H, Boualem B .A Petri net based model for w eb service composition∥Procced ings of 14 th A ustralian Database Con fer￾ence on Database Tech nologies.Adelaide, 2003:191 [ 6] Yamada S, Osaki S .Softw are reliabilit y grow th modeling :mod￾els and assumpti ons.IEEE Trans Software E ng, 1985, SE-I1: 1431 [ 7] Lin C .An approach to performance equivalent simplification and analysis of stochastic Petri nets.ACTA E lectron S in, 2002, 30( 11) :1620 ( 林闯.一种随机 Petri 网性能等价化简与分析方法.电子学 报, 2002, 30( 11) :1620) [ 8] Lin C .On refinement of model structure f or stochastic Petri nets. J Sof tware, 2000, 11( 1) :104 ( 林闯.随机 Petri 网模型的精化设计.软件学报, 2000, 11( 1 ) : 104) [ 9] Tian L Q.Performance equivalent simplification of sequent and parallel transitions in st ochastic Petri nets.Acta E lectron Sin , 2002, 30( 8) :1134 ( 田立勤.随机 Petri 网模型中变迁的串、并联性能等价化简技 术.电子学报, 2002, 30( 8) :1134) [ 10] Ciaodo G, Muppala J, Trivedi K S .SPNP:stochastic Petri net package ∥Proceedings of 3 rd Inter national Workshop on Petri Nets and Performance Models, 1989:142 · 666 · 北 京 科 技 大 学 学 报 第 31 卷