第2期 蒋运承，等：基于有限状态自动机的服务组合模型 ·55 IRw他ey=lsUe=fios,ies,ims,号，输出消息集 0ws}Uss2 Xiossn X中ss2}U...Uf's tes2Xe到 0Rwey=0sU￡={ams,0is,0ms,,字母表 EX中0ms/Ufs'sn Xic0rsn大中-sn}UfSrs X IRIr(d.es XORr(d.es)UiE e les XOes U{E= eXtrue一02/，起始状态为0gs,接收状态集 ios,ios,…i0s,号，转移函数6wy=sU F=Fs,UFs,·5es,状态条件集QCRs=QCs (s'e xyex-mas}Ufsies Xiow大中ss}U UQGs,U(0sand7吵or(sand)UU Ufs's xgexφ+0mg}U{ssXi0s六中一 (0sand9or(s2and),其中ssn,sa ssU(0masX9 eXtrue→0s}=f④s.As, 表示服务Sequence(eS,eS)的接收状态，s's2 s,ssX到eX中→0a四，ssXi0sX7中ss ssn分别表示ss,ssn前面所增加的条件 51sX到eX中→0wh9,ssXi0sX0→5s 判断状态，ios,表示服务Sequence(eSi,eS)的字 Xe xtrue→0s},起始状态为0why,接 母表，m.s2表示服务Sequence(eS!,eS)的起始状 收状态集Fmr=Fs=(ss,Ss},状态条件 态 QCa=QCs U((so and or (sxs and 2.3代数性质 )((s and or (s.s and 1)服务组合算子Sequence满足结合律 2.2复杂结构的服务组合模型 2)服务组合算子Alternative满足结合律、交换 上面介绍了直接通过算子Sequence、Alterna- 律和幂等律」 tive、Choice、Condition、lf-Then-Else、Iteration、Re 3)服务组合算子Sequence对服务组合算子AI peat-Until或Repeat-While进行服务组合的简 ternative满足分配律 单结构的服务组合模型.几个服务组合算子可以联 4)Choice(1,2,eS,eS2)=Alternative(eSi, 合起来进行复杂结构的服务组合，例如，Repeat- eS2). While(中，Sequence(eS,eS)就是通过算子Se 5)Sequence (Iteration (n,eS),Iteration (m, quence和Repeat-While来进行服务组合的 eS))=Iteration (n+m,es). 由2.1节介绍的简单结构服务组合可知，通过 6)Iteration(n,eS)=Sequence (es....eS) 任意组合算子所得到的组合服务都是1个有限状态 自动机，因而复杂结构的服务组合可以按顺序依次 7)Condition(中，eS)=If-ThenElse(中，es,. 进行.例如，对于服务组合Repeat-While(中，Se 8)f-Them Else(中，eS:,eS2)=f-Then Else quence(eS,,eS),首先将服务eS:和服务eS进 (中，eS,eSi). 行Sequence组合，得到服务Sequence(eS,eS),然 9)Repeat-Until(Φ，eS)=Sequence(eS,Re 后再对服务Sequence(eS,eS.)进行Repeat- peat-While(φ，eS)). While组合.服务Repeat-While(中，Sequence 10)服务组合算子操作是封闭的，即通过任意组 (eS,eS)的形式化模型c FSA RWS定义如下： 合算子所得到的组合服务仍然是1个带条件的有限 cFS A RWS =(QWs IRWS ORws ws FRWS 状态自动机： QCs,其中状态集Qms=(Qs,UQs,·s)U 所有这些性质都可以类似的证明，下面只证明 fss,ss}Us0ms,输入命令集1ms=ks,U 性质1) les,UE,输出消息集ORrs=Os,UOs,UE,字母表为 证明：假设服务eS:eS和eS分别如图11所 IRIrS XORIs Uee les XOes Ules,XOes,U!e 示 ,转移函数6ws=s,Us2U{ss2XeX中→ (a)服务eS, (b)服务cS (c)服务eS: 图11服务eS1,服务eS2,服务eS Fig.11 Service eSi,service eS2,and service eSs 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.netI RW (φ, eS) = IeS ∪ε= { i0 eS , i1 eS , …, imeS ,ε} ,输出消息集 ORW (φ,eS) = OeS ∪ε= { o0 eS , o1 eS , …, omeS ,ε} , 字母表 I RW (φ, eS) ×ORW (φ,eS) ∪{ε/ε} = IeS ×OeS ∪{ε/ε} = { io0 eS , io1 eS , …, iot eS ,ε/ε} ,转移函数δRW (φ,eS) =δeS ∪ {s′u eS ×ε/ε×φ→s0 RW ( n,eS) } ∪{ s′u eS ×iou eS × 」φ→su eS } ∪ …∪{ s′v eS ×ε/ε×φ→s0 RW ( n,eS) } ∪{ s′v eS ×iov eS × 」φ→ sv eS } ∪{ s0 RW ( n,eS) ×ε/ε×true →s0 eS } = {δ0 eS ,δ1 eS , …, δh eS ,s′u eS ×ε/ε×φ→s0 RU ( n,eS) , s′u eS ×iou eS ×┓φ→su eS , …,s′v eS ×ε/ε×φ→s0 RW ( n,eS) , s′v eS ×iov eS ×┓φ→sv eS , s0 RW ( n,eS) ×ε/ε×true →s0 eS } ,起始状态为 s0 RW ( n,eS) ,接 收状态集 FRW (φ,eS) = FeS = { su eS , …, sv eS } ,状态条件 集 QCRW (φ,eS) = QCeS ∪( (s0 RW (φ,eS) and ┓φ) or (su eS and φ) ) ∪…∪( (s0 RW (φ,eS) and ┓φ) or (sv eS andφ) ) . 2. 2 复杂结构的服务组合模型 上面介绍了直接通过算子 Sequence、Alterna2 tive、Choice、Condition、If2Then2Else、Iteration、Re2 peat Until 或 Repeat While 进行服务组合的简 单结构的服务组合模型. 几个服务组合算子可以联 合起来进行复杂结构的服务组合 ,例如 , Repeat While (φ, Sequence (eS1 , eS2 ) ) 就是通过算子 Se2 quence 和 Repeat While 来进行服务组合的. 由 2. 1 节介绍的简单结构服务组合可知 ,通过 任意组合算子所得到的组合服务都是 1 个有限状态 自动机 ,因而复杂结构的服务组合可以按顺序依次 进行. 例如 ,对于服务组合 Repeat While (φ, Se2 quence (eS1 , eS2 ) ) ,首先将服务 eS1 和服务 eS2 进 行 Sequence 组合 ,得到服务 Sequence (eS1 , eS2 ) ,然 后再 对服务 Sequence ( eS1 , eS2 ) 进 行 Repeat While 组 合. 服 务 Repeat While (φ, Sequence (eS1 , eS2 ) ) 的形式化模型 c FS A RWS定义如下 : c FS A RWS = ( QRWS , I RWS , ORWS ,δRWS , FRWS , s0 RWS , QCRWS ,其中状态集 QRWS = ( QeS 1 ∪QeS 2 - s0 eS 2 ) ∪ { s′u eS , …, s′v eS } ∪s0 RWS , 输入命令集 I RWS = IeS 1 ∪ IeS 2 ∪ε,输出消息集 ORWS = OeS 1 ∪OeS 2 ∪ε,字母表为 I RWS ×ORWS ∪{ε/ε} = IeS 1 ×OeS 1 ∪IeS 2 ×OeS 2 ∪{ε/ ε} ,转移函数δRWS =δeS 1 ∪δeS 2 ∪{ s′u eS12 ×ε/ε×φ→ s0 RWS } ∪{ s′u eS12 ×iou eS12 × 」φ→su eS12 } ∪…∪{ s′v eS12 ×ε/ ε×φ→s0 RWS } ∪{ s′v eS12 ×iov eS12 × 」φ→sv eS12 } ∪{ s0 RWS × ε/ε×true →s0 eS12 } , 起始状态为 s0 RWS , 接收状态集 FRWS = FeS 1 ∪FeS 2 - sweS 1 ,状态条件集 QCRWS = QCeS 1 ∪QCeS 2 ∪( (s0 RWS and ┓φ) or (su eS12 and φ) ) ∪…∪ ( (s0 RWS and ┓φ) or (sv eS12 andφ) ) ,其中 su eS12 , …,sv eS12 表示服务 Sequence (eS1 , eS2 ) 的接收状态 , s′u eS12 , …,s′v eS12 分别表示 su eS12 , …, sv eS12 前面所增加的条件 判断状态 , iov eS12 表示服务 Sequence (eS1 , eS2 ) 的字 母表 ,s0 eS12 表示服务 Sequence (eS1 , eS2 ) 的起始状 态. 2. 3 代数性质 1) 服务组合算子 Sequence 满足结合律. 2) 服务组合算子 Alternative 满足结合律、交换 律和幂等律. 3) 服务组合算子 Sequence 对服务组合算子 Al2 ternative 满足分配律. 4) Choice (1 , 2 , eS1 , eS2 ) = Alternative (eS1 , eS2 ) . 5) Sequence (Iteration ( n , eS) , Iteration ( m , eS) ) = Iteration ( n + m , eS) . 6) Iteration ( n , eS) = Sequence (eS , …,eS) n次 . 7) Condition (φ,eS) = If2Then2Else (φ, eS ,ε) . 8) If2Then2Else (φ, eS1 , eS2 ) = If2Then2Else ( ┓φ, eS2 , eS1 ) . 9) Repeat Until (φ, eS) = Sequence (eS , Re2 peat While ( ┓φ, eS) ) . 10) 服务组合算子操作是封闭的 ,即通过任意组 合算子所得到的组合服务仍然是 1 个带条件的有限 状态自动机. 所有这些性质都可以类似的证明 ,下面只证明 性质 1) . 证明 :假设服务 eS1 、eS2 和 eS3 分别如图 11 所 示 : 图 11 服务 eS1 ,服务 eS2 ,服务 eS3 Fig. 11 Service eS1 ,service eS2 ,and service eS3 第 2 期 蒋运承 ,等 :基于有限状态自动机的服务组合模型 · 55 ·