第1卷第2期 智能系统学报 Vol.1№2 2006年10月 CAAI Transactions on Intelligent Systems 0ct.2006 基于有限状态自动机的服务组合模型 蒋运承12，汤庸2，邓培民 (1.广西师范大学计算机科学与信息工程学院，广西桂林541004：2.中山大学计算机科学系，广东广州510275) 摘要：分析了目前服务计算的研究现状和存在的问题，在D Berardi和A Wombacher的基础上提出了一种带条件 的有限状态自动机模型cFSA(Finite State Automata with condition),并给出了基于cFSA的服务理论模型.在该服 务理论模型的基础上提出了一种基于有限状态自动机的服务组合形式化模型，并给出了该模型的代数性质和实现 方法 关键词：有限状态自动机：带条件的有限状态自动机：服务计算：服务组合 中图分类号：TP18文献标识码：A文章编号：1673-4785(2006)02-004810 A service composition model based on finite state automata JIANG Yumcheng'2,TANG Yong?,DENG Pei-min' (1.College of Computer Sciences and Information Engineering,Guangxi Normal University,Guilin 541004,China;2.De- partment of Computer Sciences,Sun Yasen University,Guangzhou 510275,China) Abstract:The existing conditions and problems of service computing are analyzed,and based on the work of D Berardi and A Wombacher,a kind of finite state automata with condition cFSA(Finite State Automata with condition)is presented,and the service theory model based on cFSA is presented too.Based on this model,the formal theory model of service composition based on finite state automata with condition cFSA is studied.The algebraic property and implementing method of the service composition model are studied. Key words :finite state automata;finite state automata with condition;service computing;service composition 面向服务的计算山(service-oriented compu- Microsoft将WSFL和LANG结合起来提出了服 ting)是一种新的分布式计算范型，它以服务作为开 务组合语言BPEL4WSo1,蒋运承研究了面向服务 发应用或提供问题解决方案的基本元素.而服务是 质量的服务匹配算法山等. 一种自描述的、平台无关的计算元素，它支持分布式 但是，目前e-Service的研究中，主要将服务看 应用的快速和低价组合.例如，目前的Web服务2)、 成是一个无状态的动作，事实上这是不充分的，服务 语义Web服务)或基于主体的服务4等都是面向应该是一个有状态的动作序列1)，这方面已有研 服务的计算范型，文中统称为服务或e-Service. 究.例如，D.Berardi用有限状态自动机来建立Web 目前国内外对e-Service进行了深入研究，W3C 服务的理论模型，但D.Berardi的工作只研究了服 提出了Web服务描述语言WSDL I5I,D Martin基 务描述与有限状态自动机的转换问题，没有研究基 于OWL提出了语义Web服务本体OWL-s),史 于有限状态自动机的服务匹配和组合问题】.A 忠植利用描述逻辑理论来描述主体服务)，蒋运承 Wombacher研究了基于有限状态自动机的Web服 提出了主体服务描述语言SDL SINI4,并且这些服 务商业过程的匹配问题，但A Wombacher也没有 务描述语言都有相应的服务匹配算法.BM根据工 研究基于有限状态自动机的服务组合问题).本文 作流的思想提出了Web服务流语言WSFLI81,Mi 进一步研究了基于有限状态自动机的服务组合问 crosoft提出了服务组合语言LANG),BM和 题 收稿日期：200602-23. 1 服务理论模型 基金项目：国家自然科学基金资助项目(60373081)；广东省自然科 学重点基金资助项目(04105503) 为了用有限状态自动机来描述服务，下面先给 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 1 卷第 2 期 智 能 系 统 学 报 Vol. 1 №. 2 2006 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2006 基于有限状态自动机的服务组合模型 蒋运承1 ,2 ,汤 庸2 ,邓培民1 (1. 广西师范大学 计算机科学与信息工程学院 ,广西 桂林 541004 ; 2. 中山大学 计算机科学系 ,广东 广州 510275) 摘 要 :分析了目前服务计算的研究现状和存在的问题 ,在 D Berardi 和 A Wombacher 的基础上提出了一种带条件 的有限状态自动机模型 cFSA ( Finite State Automata with condition) ,并给出了基于 cFSA 的服务理论模型. 在该服 务理论模型的基础上提出了一种基于有限状态自动机的服务组合形式化模型 ,并给出了该模型的代数性质和实现 方法. 关键词 :有限状态自动机 ;带条件的有限状态自动机 ;服务计算 ;服务组合 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2006) 0220048210 A service composition model based on finite state automata J IAN G Yun2cheng 1 ,2 , TAN G Yong 2 , DEN G Pei2min 1 (1. College of Computer Sciences and Information Engineering , Guangxi Normal University , Guilin 541004 , China ; 2. De2 partment of Computer Sciences , Sun Ya2sen University , Guangzhou 510275 , China) Abstract :The existing conditions and problems of service comp uting are analyzed , and based on t he work of D Berardi and A Wombacher , a kind of finite state automata with condition cFSA (Finite State Automata with condition) is presented , and t he service theory model based on cFSA is presented too. Based on this model , t he formal theory model of service compo sition based on finite state automata with condition cFSA is st udied. The algebraic property and implementing met hod of t he service composition model are studied. Keywords :finite state automata ; finite state automata with condition ; service computing ; service composition 收稿日期 :2006202223. 基金项目 :国家自然科学基金资助项目(60373081) ; 广东省自然科 学重点基金资助项目(04105503) . 面向服务的计算[1 ] ( service2oriented comp u2 ting) 是一种新的分布式计算范型 ,它以服务作为开 发应用或提供问题解决方案的基本元素. 而服务是 一种自描述的、平台无关的计算元素 ,它支持分布式 应用的快速和低价组合. 例如 ,目前的 Web 服务[2 ] 、 语义 Web 服务[3 ] 或基于主体的服务[4 ] 等都是面向 服务的计算范型 ,文中统称为服务或 e2Service. 目前国内外对 e2Service 进行了深入研究 ,W3C 提出了 Web 服务描述语言 WSDL [5 ] ,D Martin 基 于 OWL 提出了语义 Web 服务本体 OWL2S [6 ] ,史 忠植利用描述逻辑理论来描述主体服务[7 ] ,蒋运承 提出了主体服务描述语言 SDLSIN [4 ] ,并且这些服 务描述语言都有相应的服务匹配算法. IBM 根据工 作流的思想提出了 Web 服务流语言 WSFL [ 8 ] ,Mi2 cro soft 提出了服务组合语言 XLAN G [9 ] , IBM 和 Microsoft 将 WSFL 和 XLAN G结合起来提出了服 务组合语言 BPEL4WS [10 ] ,蒋运承研究了面向服务 质量的服务匹配算法[11 ]等. 但是 ,目前 e2Service 的研究中 ,主要将服务看 成是一个无状态的动作 ,事实上这是不充分的 ,服务 应该是一个有状态的动作序列[12213 ] ,这方面已有研 究. 例如 ,D. Berardi 用有限状态自动机来建立 Web 服务的理论模型 ,但 D. Berardi 的工作只研究了服 务描述与有限状态自动机的转换问题 ,没有研究基 于有限状态自动机的服务匹配和组合问题[12 ] . A Wombacher 研究了基于有限状态自动机的 Web 服 务商业过程的匹配问题 ,但 A Wombacher 也没有 研究基于有限状态自动机的服务组合问题[13 ] . 本文 进一步研究了基于有限状态自动机的服务组合问 题. 1 服务理论模型 为了用有限状态自动机来描述服务 ,下面先给
第2期 蒋运承，等：基于有限状态自动机的服务组合模型 ·49· 出一些基本概念 的状态转换，并且交互可用二元组来表示 finite state automata,FSA)是一个五元组(Q,∑， 定义2（服务弱形式化模型）2！给定一个服务 6,,),其中？是一个有穷集合，叫做状态集：∑ e-Service,则e-Service可以表示为一个有限状态自 是一个有穷集合，叫做字母表：6：Q×∑Q是转移 动机FSA,并且FSA是一个六元组(Q,1,O,6, 函数；φ∈Q是起始状态；F二Q是接收状态集 仰，可，其中Q是一个有穷集合，是FSA的状态集， e-Service可以看成是一个软件“黑箱”，它可以 其中状态表示客户与e-Service交互序列中的历史 与客户交互，包括3步：1)客户通过发送输入命令 记录：I是输入命令input-command的有穷集合 (input-command)调用e-Service;2)输入命令激发 O是输出消息output-message的有穷集合，IXO e-Service的内部计算(internal-computation);3) 是FSA的字母表：6：QX1×O→Q是转移函数，即 客户得到e-Service的输出消息(output-mes 给定一个状态，根据,FSA能够转移到另一个状态；∈Q是 command,internal-computation,output-mes- 起始状态；F∈Q是接收状态集，即用户能够与e sage>表示.由于采用“黑箱”的方法，交互可用二元 Service结束交互的状态集， 组来表示. 图1是一个基于有限状态自动机的股票交易服 因而可用有限状态自动机来描述e-Service,即 务2 e-Service的每次交互可以看成是有限状态自动机 buy/displayedResults userData/checkedAccount continue/displayedStock Data stop/emailNotification userData/not ValidClient sell/displayedResults 图1股票交易服务 Fig.1 Stock service 股票交易服务的形式化模型可以定义为 定义3（命题逻辑公式）命题逻辑公式按下列 FSA=(Q,1,O,6,m,F),其中状态集Q= 规则生成： {o,s1,s,s3,4};输入命令集合I=fuserData, 1)常量true和false是命题逻辑公式： continue,buy,sel,stop},输出消息集合O= 2)命题变元是命题逻辑公式： /checkedAccount,notValidClient,displayedStock- 3)如果中是命题逻辑公式，则中也是命题逻辑 Data,displayedResults,emailNotification,字母表 公式： IXO =f userData/checkedAccount,userData/ 4如果中和μ是命题逻辑公式，则中“和中V not ValidClient,continue/displayedStockData, μ也是命题逻辑公式： buy/displayedResults,sell/displayedResults, 5)命题逻辑公式只能由上述规则生成： stop/emailNotification以，转移函数6为：0 Xuser 定义4（条件）条件是由状态和命题逻辑公式 Data/checkedAccount -si,so X userData/ 通过联结词组成的表达式，形式定义如下： not ValidClient-s4,s Xcontinue/displayedStock- 假设Q是有限状态自动机状态的集合，E是命 Data-s2,s2 Xbuy/displayedResults -s2.s2 Xsell/ 题逻辑公式的集合，or和and是条件联结词，则条 displayedResults -s2,s Xstop/emailNotification 件按下列规则生成： ;0∈Q是起始状态，接收状态集F={g,4}. l)p、q∈Q,则porq和p and g是条件： 服务组合是根据组合算子来实现的，而有些组 2)p∈Q,e∈E,则p and e是条件（如果e= 合算子（如If-Them Else算子）涉及到条件，因而需 true,则简写为pl: 要一种新的自动机的定义 3)如果a和a是条件，则a and a和aora 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
出一些基本概念. 定义 1 (有限状态自动机) 有限状态自动机 (finite state automata , FSA) 是一个五元组( Q , ∑, δ, q0 , F) ,其中 Q 是一个有穷集合 ,叫做状态集; ∑ 是一个有穷集合 ,叫做字母表;δ: Q ×∑→Q是转移 函数; q0 ∈Q 是起始状态; F ΑQ 是接收状态集. e2Service 可以看成是一个软件“黑箱”,它可以 与客户交互 ,包括 3 步 :1) 客户通过发送输入命令 (inp ut command) 调用 e2Service ;2) 输入命令激发 e2Service 的内部计算 (internal comp utation) ; 3) 客户 得到 e2Service 的输出消 息 ( outp ut mes2 sage) . 因此 ,e2Service 交互可以用 3 元组 表示. 由于采用“黑箱”的方法 ,交互可用二元 组 来表示. 因而可用有限状态自动机来描述 e2Service ,即 e2Service 的每次交互可以看成是有限状态自动机 的状态转换 ,并且交互可用二元组 来表示. 定义 2 (服务弱形式化模型) [12 ] 给定一个服务 e2Service ,则 e2Service 可以表示为一个有限状态自 动机 FSA ,并且 FSA 是一个六元组 ( Q , I , O , δ, q0 , F) ,其中 Q 是一个有穷集合 ,是 FSA 的状态集 , 其中状态表示客户与 e2Service 交互序列中的历史 记录; I 是输入命令 inp ut command 的有穷集合; O 是输出消息 outp ut message 的有穷集合 , I ×O 是 FSA 的字母表;δ: Q ×I ×O →Q 是转移函数 ,即 给定一个状态 , 根据 ,FSA 能够转移到另一个状态; q0 ∈Q 是 起始状态; F Α Q 是接收状态集 , 即用户能够与 e2 Service 结束交互的状态集. 图 1 是一个基于有限状态自动机的股票交易服 务[12 ] . 图 1 股票交易服务 Fig. 1 Stock service 股票交易服务的形式化模型可以定义为 FSA = ( Q , I , O , δ, s0 , F) ,其中状态集 Q = { s0 , s1 , s2 , s3 , s4 } ;输入命令集合 I = { userData , continue , buy , sell , stop } , 输出消 息集合 O = { checkedAccount , notValidClient , displayedStock2 Data , displayedResults , emailNotification} ,字母表 I ×O = { userData/ checkedAccount , userData/ notValidClient , continue/ displayedStockData , buy/ displayedResults , sell/ displayedResults , stop/ emailNotification} ; 转移函数δ为 : s0 ×user2 Data/ checkedAccount → s1 , s0 × userData/ notValidClient →s4 , s1 ×continue/ displayedStock2 Data →s2 , s2 ×buy/ displayedResults →s2 , s2 ×sell/ displayedResults →s2 , s2 ×stop/ emailNotification →s3 ;s0 ∈Q 是起始状态;接收状态集 F = { s3 ,s4 } . 服务组合是根据组合算子来实现的 ,而有些组 合算子(如 If2Then2Else 算子) 涉及到条件 ,因而需 要一种新的自动机的定义. 定义 3 (命题逻辑公式) 命题逻辑公式按下列 规则生成 : 1) 常量 true 和 false 是命题逻辑公式 ; 2) 命题变元是命题逻辑公式 ; 3) 如果φ是命题逻辑公式 ,则┓φ也是命题逻辑 公式; 4) 如果φ和μ是命题逻辑公式 ,则φ∧μ和φ∨ μ也是命题逻辑公式; 5) 命题逻辑公式只能由上述规则生成. 定义 4 (条件) 条件是由状态和命题逻辑公式 通过联结词组成的表达式 ,形式定义如下 : 假设 Q 是有限状态自动机状态的集合 , E 是命 题逻辑公式的集合 ,or 和 and 是条件联结词 ,则条 件按下列规则生成 : 1) p、q ∈Q ,则 p or q 和 p and q 是条件; 2) p ∈Q , e ∈E, 则 p and e 是条件 (如果 e = true ,则简写为 p) ; 3) 如果 c1 和 c2 是条件 ,则 c1 and c2 和 c1 or c2 第 2 期 蒋运承 ,等 :基于有限状态自动机的服务组合模型 · 94 ·
·50· 智能系统学报 第1卷 也是条件； e-Service结束交互的状态集；QC:QXC是状态的条 4)条件只能由上述规则生成： 件集 条件的语义解释是：条件porq表示状态p和 图2是一个基于带条件的有限状态自动机的旅 g只选择一个；条件p and g表示状态p,g都选择： 游购票服务，定义为： 条件p and e表示当e的值为真时才选择状态p;对 cFSA=(Q,1,O,6,m,F,QCg,其中状态集Q= 于复杂条件a and c和aora类似进行解释. 0,n,2,3,y,s,6,}:输入命令集合I=fuser- 定义5（带条件的有限状态自动机）带条件的 Data,continue,buy,stop},输出消息集合O= 有限状态自动机(inite state automata with condi- checkedAccount,notValidClient,displayed Ticket tion,cFSA)是一个六元组(Q,∑，6，，F,Qg,其 -Data,displayedResults,emailNotification, 中Q是一个有穷集合，叫做状态集；Σ是一个有穷 IXO={userData/checkedAccount,userData/ 集合，叫做字母表，6：Q×∑×QC→Q是转移函数： not Valid -Client,continue/displayed TicketData, p∈Q是起始状态；FSQ是接收状态集；QC:Q×C buy/displayed -Results,stop/emailNotification: 是状态的条件集 转移函数6为：so XuserData/checkedAccount Xha- 定义6（服务形式化模型）给定一个服务 sAir Ticket -st,so XuserData/checkedAccount X e-Service,则e-Service可以表示为一个带条件的有hasAir Ticket,so XuserData/not ValidClient X 限状态自动机cFSA,并且cFSA是一个七元组(g,true→s,s X continue/displayedStockData X I,O,6,m,F,QCg,其中Q是一个有穷集合，是true,Xbuy/displayed-Results Xtrue→4， cFSA的状态集，其中状态表示客户与e-Service交 ss Xbuy/displayedResults Xtrue -ss,s X stop/ 互序列中的历史记录或条件判断记录：1是输入命 emailNotification Xtrue -s6.ss Xstop/emailNotifi- 令input-command的有穷集合，O是输出消息 cation Xtrue→；so∈Q是起始状态；接收状态集 output-message的有穷集合，IXO是cFSA的字 F={3,%,5}:状态条件集QC是：状态So的条件 母表；6：Q×1X0×QC→Q是转移函数，即给定一 S and hasAir Ticket or S2 and 个状态，根据 hasAir Ticket)orS,状态s,2,s4,s的条件都 和条件，cFSA可以转移到另一个或几个状态；∈ 是true,而s3,%,m没有带条件. Q是起始状态；F三Q是接收状态集，即用户能够与 (s and hasAirTicket)or(s:and-hasAirTicket)or s; buy/displayedResults continue/displayedTicketData stop/emailNotification userData/checkedAccount userData/checkedAccount continue/displayedTicketData stop/emailNotification user Data/not ValidClient buy/displayedResults 图2旅游购票服务 Fig.2 Travel book service 2服务组合模型 fs455,输入命令集s=fos,s …is/,输出消息集0s=f0505,5/,字 2.1 简单结构的服务组合模型 母表10s,=fim5ios5,ios,转移函数 假设服务eS.的形式化模型cFSAes,=(Qs, =1④s,④5,8，接收状态集F=f55, es,0s,④，Sos,F,Cs),其中状态集Qs= ss},状态条件集QCs为：ss∈Qs八s年 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
也是条件; 4) 条件只能由上述规则生成. 条件的语义解释是 :条件 p or q 表示状态 p 和 q 只选择一个;条件 p and q 表示状态 p , q 都选择; 条件 p and e 表示当 e 的值为真时才选择状态 p ;对 于复杂条件 c1 and c2 和 c1 or c2 类似进行解释. 定义 5 (带条件的有限状态自动机) 带条件的 有限状态自动机 (finite state automata wit h condi2 tion , cFSA) 是一个六元组 ( Q , ∑,δ, q0 , F, QC) ,其 中 Q 是一个有穷集合 ,叫做状态集; ∑是一个有穷 集合 ,叫做字母表;δ: Q ×∑×QC →Q 是转移函数; q0 ∈Q 是起始状态; F Α Q 是接收状态集; QC: Q ×C 是状态的条件集. 定义 6 (服务形式化模型) 给定一个服务 e2Service ,则 e2Service 可以表示为一个带条件的有 限状态自动机 cFSA , 并且 cFSA 是一个七元组( Q , I , O ,δ, q0 , F, QC) , 其中 Q 是一个有穷集合 , 是 cFSA的状态集 ,其中状态表示客户与 e2Service 交 互序列中的历史记录或条件判断记录; I 是输入命 令 inp ut command 的有穷集合 , O 是输出消息 outp ut message 的有穷集合 , I ×O 是 cFSA 的字 母表;δ: Q ×I ×O ×QC →Q 是转移函数 ,即给定一 个状态 ,根据 和条件 ,cFSA 可以转移到另一个或几个状态 ; q0 ∈ Q 是起始状态; F ΑQ 是接收状态集 ,即用户能够与 e2Service 结束交互的状态集 ; QC:Q ×C 是状态的条 件集. 图 2 是一个基于带条件的有限状态自动机的旅 游购票服务 ,定义为 : cFSA = ( Q , I , O ,δ,s0 , F, QC) ,其中状态集Q = { s0 ,s1 ,s2 ,s3 ,s4 ,s5 ,s6 , s7 } ;输入命令集合 I = { user2 Data , continue , buy , stop } , 输出消息集合 O = {checkedAccount , notValidClient , displayedTicket 2Data , displayedResults , emailNotification} , 字母 表 I ×O = { userData/ checkedAccount , userData/ notValid 2Client , continue/ displayedTicketData , buy/ displayed 2Results , stop/ emailNotification } ; 转移函数δ为 :s0 ×userData/ checkedAccount ×ha2 sAir Ticket →s1 , s0 ×userData/ checkedAccount × ┓ hasAir Ticket →s2 , s0 ×userData/ notValidClient × true →s3 , s1 ×continue/ displayedStockData × true →s4 , s4 ×buy/ displayed 2Results ×true →s4 , s5 ×buy/ displayedResults ×true →s5 , s4 × stop/ emailNotification ×true →s6 , s5 ×stop/ emailNotifi2 cation ×true →s7 ; s0 ∈Q 是起始状态; 接收状态集 F = { s3 ,s6 ,s7 } ;状态条件集 QC 是 :状态 S0 的条件 是 ( S1 and hasAir Ticket ) or ( S2 and ┓ hasAir Ticket) or S3 ,状态 s1 , s2 , s4 , s5 的条件都 是 true ,而 s3 , s6 , s7 没有带条件. 图 2 旅游购票服务 Fig. 2 Travel book service 2 服务组合模型 2. 1 简单结构的服务组合模型 假设服务 eSi 的形式化模型 c FS AeS i = ( QeS i , IeS i , OeS i ,δeS i , S0 eS i , FeS i , QCeS i ) , 其中状态集 QeS i = { s0 eS i ,s1 eS i , …, sn eS i } , 输入命令集 IeS i = { i0 eS i , i1 eS i , …, imeS i } ,输出消息集 OeS i = { o0 eS i , o1 eS i , …, ok eS i } ,字 母表 IeS i ×OeS i = { io0 eS i , io1 eS i , …, iot eS i } , 转移函数 δeS i = {δ0 eS i ,δ1 eS i , …,δh eS i } ,接收状态集 FeS i = { su eS i , …,sv eS i } ,状态条件集 QCeS i 为 : Πsi eS i ∈QeS i ∧si eS i | · 05 · 智 能 系 统 学 报 第 1 卷
第2期 蒋运承，等：基于有限状态自动机的服务组合模型 ·51· Fs,5s的条件是qCs 0ms,0,0%},字母表1ses,es XOstes1sy= 1)组合算子Sequence表示2个服务可以连续 les XOes Ules XOes2 =(ias ioes,ioes, 执行，即第1个服务的输出是第2个服务的输入，因 i0,i0s,转移函数④s=,U,= 而服务eS,和eS,通过算子Sequence组合成一个 1④。，8，，4，…8s},起始状态 新的服务的条件是eS,的一个接受状态是eS的起 始状态，即3ss∈F=(5,5s/,使得 S0s=6,接收状态集Fs=F,U ss=0s成立.服务Sequence(eS,eSa)的形式化 F5mes=f%,5s,5线’5-5es= 模型cFSAstes,)定义如下： …55*1”55气…55，状 CFS Astes)=(Ostes e)Istes)),Ostes), 态条件集QCe,y=QCs,UQCs,即 &es,0ss,F压e,QCss,其中状态 s6∈sesy八sge年Fs,如果 集0sesy=0sU0s则5={sss，” 5的=s则ss的条件是9G;如果 5,5},输入命令集1 ste5:53=1s,U 5s=5s则ss的条件是g95 ls,={osh,i的0i，…i线，输出 图3是将服务eS!和eS通过算子Sequence组 合成一个新的服务的例子 消息集O5e1=0s1U0s={0s,0s,”01 (s and c)or s:and-c)or s (h andd)or (t:and d or h 访 o/p e 9 (a)服务eS b)服务eS: (s and ci)or s2 and-c)or (1 and d,)or I:and-d)or h a/b o/p (e)服务Sequence(eS,es:) 图3通过算子Sequence的服务组合 Fig.3 Service composition through sequence 2)组合算子Alternative表示2个服务只能执 cFSAA(eS)=(Qa(es )IAfeS,Oafes) 行其中的1个，因而任何2个服务eS和eS:都能 es,0es,Bs,Qes,其中状态 够通过算子Alternative组合成一个新的服务，该服 Qates5)=Qes:UQes:Usto tes(stotes 务需要在服务eS:和eS2前增加一个带条件的新的 起始状态，如图4所示. 4，”55,…55,号，输入命令 服务Alternative(eS,eS,)的形式化模型 集1es=sUls,Ue=fo线，s，…is cFSA4es,y定义如下： shs,is,y,输出消息集Os= 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
FeS i ,si eS i 的条件是 qci eS i . 1) 组合算子 Sequence 表示 2 个服务可以连续 执行 ,即第 1 个服务的输出是第 2 个服务的输入 ,因 而服务 eS1 和 eS2 通过算子 Sequence 组合成一个 新的服务的条件是 eS1 的一个接受状态是 eS2 的起 始状态 , 即 ϖsweS 1 ∈FeS 1 = { su eS 1 , …, sv eS 1 } , 使得 sweS 1 = s0 eS 2 成立. 服务 Sequence (eS1 , eS2 ) 的形式化 模型 c FS A S (eS 1 ,eS 2 ) 定义如下 : c FS A S (eS 1 ,eS 2 ) = ( QS (eS 1 ,eS 2 ) , IS (eS 1 ,eS 2 ) ) , OS (eS 1 ,eS 2 ) , δS (eS 1 ,eS 2 ) , s0 S (eS 1 ,eS 2 ) , FS (eS 1 ,eS 2 ) , QCS (eS 1 ,eS 2 ) , 其中状态 集 QS (eS 1 ,eS 2 ) = QeS 1 ∪QeS 2 - s0 eS 2 = { s0 eS 1 , s1 eS 1 , …, sn eS 1 , s1 eS 2 , …, sn eS 2 } , 输入命令集 IS (eS 1 ,eS 2 ) = IeS 1 ∪ IeS 2 = { i0 eS 1 , i1 eS 1 , …, imeS 1 , i0 eS 2 , i1 es 2 , …, imeS 2 } ,输出 消息集 OS (eS 1 ,eS 2 ) = OeS 1 ∪OeS 2 = { o0 eS 1 , o1 eS 1 , …, ok eS 1 , o0 eS 2 , o1 es 2 , …, ok eS 2 } , 字母表 IS (eS 1 ,eS 2 ) ×QS (eS 1 ,eS 2 ) = IeS 1 ×OeS 1 ∪IeS 2 ×OeS 2 = { io0 eS 1 , io1 eS 1 , …, iot eS 1 , io0 eS 2 , …, iot eS 2 } , 转移函数 δS (eS 1 ,eS 2 ) =δeS 1 ∪δeS 2 = {δ0 es 1 δ1 eS 1 , …,δh eS 1 ,δ0 eS 2 ,δ1 eS 2 , …,δh eS 2 } , 起始状态 S0 S (eS 1 ,eS 2 ) = s0 eS 1 , 接 收 状 态 集 FS (eS 1 ,eS 2 ) = FeS 1 ∪ FeS 2 - sweS 1 = { su eS 1 , …, sv eS 1 , su eS 2 , …, sv eS 2 } - sweS 1 = { su eS 1 , …,sw - 1 eS 1 , sw + 1 eS 1 , …, sv eS 1 , su eS 2 , …, sv eS 2 } ,状 态 条 件 集 QCS (eS 1 ,eS 2 ) = QCeS 1 ∪ QCeS 2 , 即 Πsi S (eS 1 ,eS 2 ) ∈QS (eS 1 ,eS 2 ) ∧si S (eS 1 ,eS 2 ) | FS (eS 1 ,eS 2 ) , 如果 si S (eS 1 ,eS 2 ) = si eS 1 则 si S (eS 1 ,eS 2 ) 的 条 件 是 qci eS 1 ; 如 果 si S (eS 1 ,eS 2 ) = si eS 2 则 si S (eS 1 ,eS 2 ) 的条件是 qci eS 2 . 图 3 是将服务 eS1 和 eS2 通过算子 Sequence 组 合成一个新的服务的例子. 图 3 通过算子 Sequence 的服务组合 Fig. 3 Service composition through sequence 2) 组合算子 Alternative 表示 2 个服务只能执 行其中的 1 个 ,因而任何 2 个服务 eS1 和 eS2 都能 够通过算子 Alternative 组合成一个新的服务 ,该服 务需要在服务 eS1 和 eS2 前增加一个带条件的新的 起始状态 ,如图 4 所示. 服务 Alternative ( eS1 , eS2 ) 的 形 式 化 模 型 c FS A A (eS 1 ,eS 2 ) 定义如下 : c FS A A (eS 1 ,eS 2 ) = ( QA (eS 1 ,eS 2 ) , IA (eS 1 ,eS 2 ) , OA (eS 1 ,eS 2 ) , δA (eS 1 ,eS 2 ) , s0 A (eS 1 ,eS 2 ) , FA (eS 1 ,eS 2 ) , QCA (eS 1 ,eS 2 ) , 其中状态 集 QA (eS 1 ,eS 2 ) = QeS 1 ∪QeS 2 ∪st0 A (eS 1 ,eS 2 ) = { st0 A (eS 1 ,eS 2 ) , s0 eS 1 ,s1 eS 1 , …, sn eS 1 , s0 eS 2 , s1 eS 2 , …, sn eS 2 ,ε} ,输入命令 集 IA (eS 1 ,eS 2 ) = IeS 1 ∪IeS 2 ∪ε= { i0 eS 1 , i1 eS 1 , …, imeS 1 , i0 eS 2 , i1 eS 2 , …, imeS 2 ,ε} , 输 出 消 息 集 OA (eS 1 ,eS 2 ) = 第 2 期 蒋运承 ,等 :基于有限状态自动机的服务组合模型 · 15 ·
·52· 智能系统学报 第1卷 服务Choice(eS,…,eS.)的形式化模型 CFS A cMes,,es)定义如下： cFSA cles,=(Qates,,Icfes,, Oatess,ates Fares Soates ACavtes,esy其中状态集Qaes,“e=Q,UU Qs.Ushates,5=(stoaless5 5的，6,6。，s,输入命令集1a,= 图4通过算子Alternative的服务组合 Ies U.U les Ue=f ios 1,ites imes toes Fig.4 Service composition through alternative 45，…ia,号，输出消息集0aes,5=0,U as Uos,Ue=faso.os UOes,Ue=(o 0,,字母表1 stes XOsts Uf=es,X 0s,,字母表1aesX0aeU{= Oes Ulesz XOs:U!gg=(ias ias ioes les XOes U...U Ies,XOs,Ufee =ias ios i0sio6:io,9g,转移函数s=④U i0,ioms,i0es.,i0s,,转移函数 s,U{s面，xqe Xtrue%s5面65X Bales.s=ds U...uos.Uf shates,m xex erue0s}=(④s,s,6,, true→s，”sha6s,sXqe Xtrue→s,}= A3面es,X6 Xtrue5面e5X9eX ④，4，…，4，…85s true→/，起始状态为s面，5，接收状态集 ge Xtrue一s,”5hales,xge Xtrue→ FAe)=Fs UFes =f smes Sves s ,,起始状态为s和，，接收状态集 s/,状态条件集QCe=ocs,Uoas,U Fates5)Fes U..U Fs,=(sxes.Stes, (orms,即s∈QyΛs年 ss,5s,,状态条件集QCals=QCsU Bes,如果s=6则5s的条件是 uocs U(andand or q心：如果=5则s的条件是 and.and s.s,）. 4)组合算子Condition表示只有满足一定的条 qcs如果=5而s,则s的条件是 件才执行某个服务，因而服务Condition(中，eS)需 (Ss,0r50s. 要增加1个带条件的新的起始状态，如图6所示， 3)组合算子Choice是组合算子Alternative的 推广，算子Choice表示从n个服务中选择m个服务 执行(m≤n).因而服务Choice(m,n,eS,…,eSn) (简写为Choice(eS,…,eS.)需要增加一个带条 件的新的起始状态，如图5所示。 (Sp and..and s) or ...or 图6通过算子Condition的服务组合 (and..and Su） Fig.6 Service composition through condition 服务Condition(中，es)的形式化模型 CFSAard.es定义如下： CFSAco(t.es (Ocord.es)Icord.es,Ocord.es), fey,Faey,oey,QColt.),其中状态集 Qolt.e Qes Usate =(ar5ts .Sres 输入命令集1ay=1sUe={ios,is,”ims,号， 图5通过算子Choice的服务组合 输出消息集Oaey=OsUe={os,0s,”0ms Fig.5 Service composition through Choice 号，字母表1 rt.es XOcrd.es U{号=Ies XOesL{ 号={i0s,i0s,i0s,以，转移函数as= 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 4 通过算子 Alternative 的服务组合 Fig. 4 Service composition through alternative OeS 1 ∪OeS 2 ∪ε= { o0 eS 1 , o1 eS 1 , …, ok eS 1 , o0 eS 2 , o1 eS 2 , …, ok eS 2 ,ε} ,字母表 IS (eS 1 ,eS 2 ) ×QS (eS 1 ,eS 2 ) ∪{ε/ε} = IeS 1 × OeS 1 ∪IeS 2 ×OeS 2 ∪{ε/ε} = { io0 eS 1 , io1 eS 1 , …, iot eS 1 , io0 eS 2 , io1 eS 2 , …, iot eS 2 ,ε/ε} ,转移函数δA(eS 1 ,eS 2 ) =δeS 1 ∪ δeS 2 ∪{ st0 A (eS 1 ,eS 2 ) ×ε/ε×true →s0 eS 1 , st0 A (eS 1 ,eS 2 ) ×ε/ ε×true →s0 eS 2 } = {δ0 eS 1 ,δ1 eS 1 , …,δh eS 2 ,δ0 eS 2 ,δ1 eS 2 , …, δh eS 2 ,st0 A (eS 1 , eS 2 ) ×ε/ε×true →s0 eS 1 , st0 A (eS 1 ,eS 2 ) ×ε/ε× true →s0 eS 2 } , 起始状态为 st0 A (eS 1 , eS 2 ) , 接收状态集 FA (eS 1 , eS 2 ) = FeS 1 ∪FeS 2 = { su eS 1 , …, sv eS 1 , su eS 2 , …, sv eS 2 } , 状态条件集 QCA (eS 1 ,eS 2 ) = QCeS 1 ∪QCeS 2 ∪ (s0 eS 1 or s0 eS 2 ) ,即 Πsi A (eS 1 ,eS 2 ) ∈QA (eS 1 ,eS 2 ) ∧si A (eS 1 ,eS 2 ) | FA (eS 1 ,eS 2 ) ,如果 si A (eS 1 ,eS 2 ) = si eS 1 则 si A (eS 1 ,eS 2 ) 的条件是 qci eS 1 ; 如 果 si A (eS 1 ,eS 2 ) = si eS 2 则 si A (eS 1 ,eS 2 ) 的 条 件 是 qci eS 2 ;如果 si A (eS 1 ,eS 2 ) = st0 A (eS 1 ,eS 2 ) 则 si A (eS 1 ,eS 2 ) 的条件是 (s0 eS 1 or s0 eS 2 ) . 3) 组合算子 Choice 是组合算子 Alternative 的 推广 ,算子 Choice 表示从 n 个服务中选择 m 个服务 执行( m ≤n) . 因而服务 Choice ( m , n , eS1 , …,eSn ) (简写为 Choice (eS1 , …,eSn ) ) 需要增加一个带条 件的新的起始状态 ,如图 5 所示. 图 5 通过算子 Choice 的服务组合 Fig. 5 Service composition through Choice 服务 Choice ( eS1 , …, eSn ) 的 形 式 化 模 型 c FS A Ch (eS 1 , …,eS n ) 定义如下 : c FS A Ch (eS 1 , …,eS n ) = ( QCh (eS 1 , …,eS n ) , ICh (eS 1 , …,eS n ) , OCh (eS 1 , …,eS n ) ,δCh (eS 1 , …,eS n ) , FCh (eS 1 , …,eS n ) , S0Ch (eS 1 , …,eS n ) , A CCh (eS 1 , …,eS n ) 其中状态集 QCh (eS 1 , …,eS n ) = QeS 1 ∪…∪ QeS n ∪st0 Ch (eS 1 , …,eS n ) = { st0 Ch (eS 1 , …,eS n ) , s0 eS 1 , s1 eS 1 , …, sn eS 1 , …,s0 eS n ,s1 eS n , …,sn eS n } ,输入命令集 ICh(eS 1 , …,eS n ) = IeS 1 ∪…∪IeS n ∪ε= { i0 eS 1 } , i1 eS 1 …, imeS 1 , …, i0 eS 1 , i1 eS 1 , …, imeS 1 n ,ε} ,输出消息集 OCh (eS 1 , …,eS n ) = OeS 1 ∪ …∪OeS n ∪ε= { o0 eS 1 , o1 eS 1 , …, omeS 1 , …, o0 eS n , o1 eS n , …, omeS n ,ε} ,字母表 ICh(eS 1 , …,eS n ) ×OCh (eS 1 , …,eS n ) ∪{ε/ε} = IeS 1 ×OeS 1 ∪…∪IeS n ×OeS n ∪{ε/ε} = { io0 eS 1 , io1 eS 1 , …, iot eS 1 , …, io0 eS n , io1 eS n , …, iot eS n ,ε/ε} , 转移函数 δCh (eS 1 , …,eS n ) =δeS 1 ∪…∪δeS n ∪{ st0 Ch (eS 1 , …,eS n ) ×ε/ε× true →s0 eS 1 , …, st0 Ch (eS 1 , …,eS n ) ×ε/ε×true →s0 eS n } = {δ0 eS 1 ,δ1 eS 1 , …,δh eS 2 ,δ0 eS 2 ,δ1 eS 2 , …,δh eS 2 ,st0 A (eS 1 ,eS 2 ) × ε/ε×true →s0 eS 1 , …, st0 Ch (eS 1 , …,eS n ) ×ε/ε×true → s0 eS n } , 起 始 状 态 为 st0 Ch (eS 1 , …,eS n ) , 接 收 状 态 集 FCh (eS 1 ,eS 2 ) = FeS 1 ∪…∪FeS n = { su eS 1 , …, sv eS 1 , …, su eS n , …, sv eS n } ,状态条件集 QCCh (eS 1 , …,eS n ) = QCeS 1 ∪ …∪QCeS n ∪( (s0 eS 1 , and …and s0 eSm ) or …or (s0 eS( n - m) and …and s0 eS n ) ) . 4) 组合算子 Condition 表示只有满足一定的条 件才执行某个服务 ,因而服务 Condition (φ,eS) 需 要增加 1 个带条件的新的起始状态 ,如图 6 所示. 图 6 通过算子 Condition 的服务组合 Fig. 6 Service composition through condition 服 务 Condition (φ, eS) 的 形 式 化 模 型 c FS A Co(φ, eS) 定义如下 : c FS A Co(φ,eS) = ( QCo(φ,eS) , ICo(φ,eS) , OCo(φ,eS) , δCo(φ,eS) , FCo(φ,eS) , s0 Co(φ,eS) , QCCo(φ,eS) ) , 其 中 状 态 集 QCo(φ,eS) = QeS ∪s0 Co(φ,eS) = { s0 Co(φ,eS) , s0 eS , s1 eS , …, sn eS } , 输入命令集 ICo(φ,eS) = IeS ∪ε= { i0 eS , i1 eS , …, imeS ,ε} , 输出消息集 OCo(φ, eS) = OeS ∪ε= { o0 eS , o1 eS , …, omeS , ε} ,字母表 ICo(φ,eS) ×OCo(φ, eS) ∪{ε/ε} = IeS ×OeS ∪{ε/ ε} = { io0 eS , io1 eS , …, iot eS ,ε/ε} , 转移函数δCo(φ,eS) = · 25 · 智 能 系 统 学 报 第 1 卷
第2期 蒋运承，等：基于有限状态自动机的服务组合模型 ·53 Bs Ufsoam xee xtrue s0s=1ds.6s.6s, QCrs,y),其中状态集Qres,s=Qs,U amXy extrues.},起始状态为og,接收 sUye=fy0,,”5 状态集=Fs=Fs=(5s,5s},状态条件集 5s,5},输入命令集1s=1s,U QCay=OCs U(sos and吵 5)组合算子If-Then Else根据条件判断从2个 les Ue=ios ites imes foes 服务中选择1个执行，因而服务If-Then Else 输出消息集0g®，=0s,U0s,Ue={ms, (中，eS,,eS)需要增加1个带条件的新的起始状 00m00,y,字母表 态，如图7所示 Iit.es S XOu(tes es Ufgg les XOs Ules,X Os Ufee=(ios,ios iovs icsi (s amd or (t and-) i0,号，转移函数6r=,U,U fX到eX中一s·0yXeX中一 s}={④6,6s，8,8。,88 画西XEX中一0，g他的X到eX中一 ,起始状态为5，接收状态集 Frrtes=Fis U Fes =f sues Sves Sues 图7通过算子If-Therr Else的服务组合 s/,状态条件集QC®s=QCs,UQCs,U Fig.7 Service composition through If-Them Else ((sos andor (so and). 服务If-Then-Else(中，eS,eS,)的形式化模型 6)组合算子Iteration表示1个服务重复执行 CFSA es,y定义如下： 多次(n次)，因而服务Iteration(n,eS)需要在服 CFSAy(tes es2)=Or(ees es),Iides es), 务es的每个接收状态前增加1个带条件的判断状 Oytes es)reesFrtes 态，即判断服务eS是否执行完n次，如图8所示. (s and great(n))or (s,and-grea(n)》 a/b (s;and great(n))or (so and great(n)) E/e (a)服务es (b)服务Iteraton(n,eS) 图8通过算子Iteration的服务组合 Fig.8 Service composition Through Iteration 服务Iteration(n,eS)的形式化模型 &s Ufshs Xe xe'great (n Ufs's Xioxs X CFSA nim.s定义如下： great(W→sus}U…U{s's xeexgreat(nl→ CFSA ntn.es)Onin.es,In(n.es,On(n.es),Ou(n.e, Ufs's Xiors Xgreat (n)-s ves=ds. Fafn.e,aes,QCxw.9,其中状态集Qnta.e= ④s,As,ssxee xgreat(W→0as,ssX Qs Ufs'tes,ss}=fSo。,Si。,Sn。,ss, iovs Xgreat(w→ss,'s'ies Xeexgreat(nml一 s4s},输入命令集1h1a9=1sUE={os,s, ag,'s Xios Xgreat(W→ss/,起始状态为 is,,输出消息集0aa=OsUe={as,0s, aes,接收状态集Faay=Fs=f5s,…5s}, oms,号，字母表In(m.c59 XOw(.yU(g=1 es XOes U 状态条件集Cnn9=QCsU(and great {9号=fi0s,i0s,；i0s,9号，转移函数ms= (n))or (ss and great (n)))((so and 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
δeS ∪{ s0 Co(φ,eS) ×ε/ε×true →s0 eS } = {δ0 eS ,δ1 eS , …,δh eS , s0 Co(φ,eS) ×ε/ε×true →s0 eS } ,起始状态为 s0 Co(φ,eS) ,接收 状态集 = FCo(φ,eS) = FeS = { su eS , …, sv eS } ,状态条件集 QCCo(φ,eS) = QCeS ∪(s0 eS andφ) . 5) 组合算子 If2Then2Else 根据条件判断从 2 个 服务 中 选 择 1 个 执 行 , 因 而 服 务 If2Then2Else (φ, eS1 , eS2 ) 需要增加 1 个带条件的新的起始状 态 ,如图 7 所示. 图 7 通过算子 If2Then2Else 的服务组合 Fig. 7 Service composition through If2Then2Else 服务 If2Then2Else (φ, eS1 ,eS2 ) 的形式化模型 c FS A If (φ,eS 1 ,eS 2 ) 定义如下 : c FS A If (φ,eS 1 ,eS 2 ) = ( QIf (φ, eS 1 ,eS 2 ) , IIf (φ, eS 1 ,eS 2 ) , OIf (φ,eS 1 ,eS 2 ) ,δIf (φ, eS 1 ,eS 2 ) ,s0 If (φ,eS 1 ,eS 2 ) , FIf (φ,eS 1 ,eS 2 ) , QCIf (φ,eS 1 ,eS 2 ) ) , 其 中 状 态 集 QIf (φ,eS 1 ,eS 2 ) = QeS 1 ∪ QeS 2 ∪s0 If (φ,eS 1 ,eS 2 ) = { s0 If (φ,eS 1 ,eS 2 ) , s0 eS 1 , s1 eS 1 , …, sn eS 1 , s0 eS 2 ,s1 eS 2 , …, sn eS 2 } ,输入命令集 IIf (φ,eS 1 ,eS 2 ) = IeS 1 ∪ IeS 2 ∪ε= { i0 eS 1 , i1 eS 1 , …, imeS 1 , i0 eS 2 , i1 eS 2 , …, imeS 2 ,ε} , 输出消息集 OIf (φ, eS 1 ,eS 2 ) = OeS 1 ∪OeS 2 ∪ε= { o0 eS 1 , o1 eS 1 , …, ok eS 1 , o0 eS 2 , o1 eS 2 , …, ok eS 2 , ε} , 字 母 表 IIf (φ,eS 1 ,eS 2 ) ×OIf (φ,eS 1 ,eS 2 ) ∪{ε/ε} = IeS 1 ×OeS 1 ∪IeS 2 × OeS 2 ∪{ε/ε} = { io0 eS 1 , io1 eS 1 , …, iot eS 1 , io0 eS 2 , io1 eS 2 , …, iot eS 2 ,ε/ε} , 转移函数δIf (φ,eS 1 ,eS 2 ) =δeS 1 ∪δeS 2 ∪ { s0 If (φ,eS 1 ,eS 2 ) ×ε/ε×φ→s0 eS 1 , s0 If (φ,eS 1 ,eS 2 ) ×ε/ε×┓φ→ s0 eS 2 } = {δ0 eS 1 ,δ1 eS 1 , …,δh eS 2 ,δ0 eS 2 ,δ1 eS 2 , …,δh eS 2 , s0 If (φ,eS 1 ,eS 2 ) ×ε/ε×φ→s0 eS 1 , s0 If (φ,eS 1 ,eS 2 ) ×ε/ε×┓φ→ s0 eS 2 } , 起 始 状 态 为 s0 If (φ,eS 1 ,eS 2 ) , 接 收 状 态 集 FIf (φ,eS 1 ,eS 2 ) = FeS 1 ∪FeS 2 = { su eS 1 , …, sv eS 1 , su eS 2 , …, sv eS 2 } , 状态条件集 QCIf (φ,eS 1 ,eS 2 ) = QCeS 1 ∪QCeS 2 ∪ ( (s0 eS 1 andφ) or (s0 eS 2 and ┓φ) ) . 6) 组合算子 Iteration 表示 1 个服务重复执行 多次( n 次) ,因而服务 Iteration ( n , eS) 需要在服 务 eS 的每个接收状态前增加 1 个带条件的判断状 态 ,即判断服务 eS 是否执行完 n 次 ,如图 8 所示. 图 8 通过算子 Iteration 的服务组合 Fig. 8 Service composition Through Iteration 服 务 Iteration ( n , eS) 的 形 式 化 模 型 c FS A It ( n,eS) 定义如下 : c FS A It ( n, eS) = QIt ( n, eS) , IIt ( n, eS) , OIt ( n,eS) ,δIt ( n,eS) , FIt ( n, eS) , s0 It ( n,eS) , QCIt ( n, eS) , 其 中 状 态 集 QIt ( n, eS) = QeS ∪{ s′u eS , …, s′v eS } = { S0 es , S1 es , …, S n es , s′u eS , …, s′u eS } ,输入命令集 IIt ( n,eS) = IeS ∪ε= { i0 eS , i1 eS , …, imeS ,ε} ,输出消息集 OIt ( n,eS) = OeS ∪ε= { o0 eS , o1 eS , …, omeS ,ε} ,字母表 IIt ( n,eS) ×OIt ( n, eS) ∪{ε/ε} = IeS ×OeS ∪ {ε/ε} = { io0 eS , io1 eS , …, iot eS ,ε/ε} ,转移函数δIt( n,eS) = δeS ∪{ s′u eS ×ε×ε┓ great ( n) →s0 It ( n,eS) } ∪{ s′u eS ×iou eS × great ( n) →su eS } ∪…∪{ s′v eS ×ε/ε×┓ great ( n) → s0 It ( n,eS) } ∪{ s′v eS ×iov eS ×great ( n) →s veS } = {δ0 eS , δ1 eS , …,δh eS , s′u eS ×ε/ε×┓ great ( n) →s0 It ( n,eS) , s′u eS × iou eS ×great ( n) →su eS , …, s′v eS ×ε/ε×┓ great ( n) → s0 It ( n,eS) ,s′v eS ×iov eS ×great ( n) →sv eS } , 起始状态为 s0 It ( n,eS) ,接收状态集 FIt ( n,eS) = FeS = { su eS , …, sv eS } , 状态条件集 QCIt ( n,eS) = QCeS ∪( (s0 It ( n,eS) and ┓ great ( n) ) or ( su eS and great ( n) ) ) ∪…∪( (s0 It ( n,eS) and 第 2 期 蒋运承 ,等 :基于有限状态自动机的服务组合模型 · 35 ·
·54· 智能系统学报 第1卷 "great(n)or (s.s and great(n)). (中，eS)需要在服务eS的每个接收状态前增加1个 7)组合算子Repeat-Until表示执行某个服 带条件的判断状态，即判断服务es是否满足条件 务，直到满足一定的条件，因而服务Repeat-Until 中，如图9所示. (s and or (s and-) a/b (s,and or (suand-p） E/E (a)服务es (b)服务Repeat_Untikp.eS) 图9通过算子Repeat-Until的服务组合 Fig.9 Service composition through Repeat-Until 服务Repeat-Until(中，eS)的形式化模型 ssXe人中0ua9,s's Xiors中s},起始 CFSA RUrhe定义如下： 状态为0us,接收状态集F则=Fs={5s CFSA RU(e.es ORu(d.es)IRu(d.es),ORu(d.es), Ss},状态条件集QCue9=QCsU(0S 可ur,Fauy,ury,QCus),其中状态集 and or (ss and)U((so and or Qwure.es Qes Ufs hes,stes=(s0s Stes,Sns (ss and). s6,…ss},输入命令集1mey=1sUe=f而s, 8)组合算子Repeat-While表示当满足某个条 es,is,y,输出消息集Ouey=OsUe= 件就执行服务，直到该条件不满足为止，可以看出， {s,0s,0ms,,字母表IuA9XOU®esU 组合算子Repeat-While是组合算子Condition和 e les XOes Ugg=(ias,ios,ios., 组合算子Repeat-Until的结合，因而服务Repeat- 转移函数y=④s Uls'ts xgex中0侧y}U While(中，eS)需要增加1个带条件的新的起始状 fs'sXi0sXφ→ss}U…U{s's XgEx中一 态，并在服务es的每个接收状态前增加一个带条件 0uas}U{ssXi0sX中→ss}={6s,④s, 的判断状态，如图10所示」 8s,ssX9中→0uag,5sXi0sX中→Ss, (sand-p)） or (rs,and) a/b (s and-)or (rs,and c/t c/ E/E (a)服务cs (b)服务Repeat._whle(p.eS) 图I0通过算子Repeat-While的服务组合 Fig.10 Service composition through Repeat_While 服务Repeat-While(中，eS)的形式化模型 8ry,Fn,0we,QCe),其中状态集 CFSA RW(.eS)定义如下： Our(d.es Qes Ufs 4s,stes Uso gares =150e Stes, C FSA RW快ey=（QRr(仲e,IRw(.es,ORw体.ey, 5,5s,5s,0m9},输入命令集 1994-2008 China Academic Journal Electronie Publishing House.All rights reserved.http://www.cnki.net
┓ great ( n) ) or (sv eS and great ( n) ) ) . 7) 组合算子 Repeat Until 表示执行某个服 务 ,直到满足一定的条件 ,因而服务 Repeat Until (φ, eS) 需要在服务 eS 的每个接收状态前增加 1 个 带条件的判断状态 ,即判断服务 eS 是否满足条件 φ,如图 9 所示. 图 9 通过算子 Repeat Until 的服务组合 Fig. 9 Service composition through Repeat Until 服务 Repeat Until (φ, eS) 的形式化模型 c FS A RU (φ, eS) 定义如下 : c FS A RU (φ,eS) = ( QRU (φ,eS) , I RU (φ, eS) , ORU (φ,eS) , δRU (φ,eS) , FRU (φ, eS) , s0 RU (φ,eS) , QCRU (φ,eS) ) , 其中状态集 QRU (φ,eS) = QeS ∪{ s′u eS , …, s′v eS } = { s0 eS , s1 eS , …, sn eS , s′u eS , …,s′v eS } ,输入命令集 I RU (φ,eS) = IeS ∪ε= { i0 eS , i1 eS , …, imeS ,ε} , 输出消息集 ORU (φ,eS) = OeS ∪ε= { o0 eS , o1 eS , …, omeS ,ε} , 字母表 I RU (φ,eS) ×ORU (φ,eS) ∪ {ε/ε} = IeS ×OeS ∪{ε/ε} = { io0 eS , io1 eS , …, iot eS ,ε/ε} , 转移函数δRU (φ,eS) =δeS ∪{ s′u eS ×ε/ε× ┓φ→s0 RU ( n,eS) } ∪ { s′u eS ×iou eS ×φ→su eS } ∪…∪{ s′v eS ×ε/ε× 」φ→ s0 RU ( n,eS) } ∪{ s′v eS ×iov eS ×φ→sv 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 RU ( n,eS) , s′v eS ×iov eS ×φ→sv eS } ,起始 状态为 s0 RU (φ,eS) , 接收状态集 FRU (φ,eS) = FeS = { su eS , …,sv eS } ,状态条件集 QCRU (φ,eS) = QCeS ∪ ( (s0 RU (φ,eS) and 」φ) or (su eS andφ) ) ∪…∪( (s0 RU (φ,eS) and 」φ) or (sv eS andφ) ) . 8) 组合算子 Repeat While 表示当满足某个条 件就执行服务 ,直到该条件不满足为止 ,可以看出 , 组合算子 Repeat While 是组合算子 Condition 和 组合算子 Repeat Until 的结合 ,因而服务 Repeat While (φ, eS) 需要增加 1 个带条件的新的起始状 态 ,并在服务 eS 的每个接收状态前增加一个带条件 的判断状态 ,如图 10 所示. 图 10 通过算子 Repeat While 的服务组合 Fig. 10 Service composition through Repeat While 服务 Repeat While (φ, eS) 的形式化模型 c FS A RW (φ,eS) 定义如下 : c FS A RW (φ,eS) = ( QRW (φ,eS) , I RW (φ,eS) , ORW (φ,eS) , δRW (φ,eS) , FRW (φ, eS) , s0 RW (φ,eS) , QCRW (φ, eS) ) , 其中状态集 QRW (φ,eS) = QeS ∪{ s′u eS , …,s′v eS } ∪s0 RW (φ,eS) = { s0 eS ,s1 eS , …, sn eS , s′u eS , …, s′v eS , s0 RW (φ,eS) } , 输 入 命 令 集 · 45 · 智 能 系 统 学 报 第 1 卷
第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.net
I 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 ·
·56· 智能系统学报 第1卷 则利用2.1和2.2节介绍的服务组合方法可得 Sequence(eS,Sequence(eS2,eS,)是相同的，如 服务Sequence(Sequence(eS,,eS),eS,)和服务 图12所示： n/ 图l2服务Sequence(Sequence(eS!,eS),eS,)和Sequence(eSi,Sequence(eS,,cS) Fig.12 Service Sequence(Sequence(eSI,eS2),eS3)and Sequence(eSI ,Sequence(eS2,eS3)) 所以Sequence(Sequence(eSi,eS),eS:)= 输入：需要组合的原子服务、组合服务描述说明 Sequence(eSi,Sequence(eS,eS).证毕 CSD 3实现与分析 输出：一个带条件的有限状态自动机 1)从组合服务描述说明C$D中读取第一个组 因为通过任意组合算子所得到的组合服务仍然 合算子CS,并取出组合算子CS的参数PS 是1个带条件的有限状态自动机（见2.3节的性质 2)如果PS中不含组合算子，则按2.1节介绍 10),所以任何组合服务都可以转化为1个有限状态 的对组合算子C$的组合方法进行服务组合，得到 自动机来实现.关键问题是如何将几个服务转化为 一个带条件的有限状态自动机cFSA,并result= 1个基于有限状态自动机的组合服务.由于服务组 cFSA,Goto 6). 合算子操作的封闭性，可以利用递归的方法来实现 3)从PS中取出组合服务描述说明CSD的子描 这种转化.例如，服务Repeat-While(中，Sequence 述SCSD (eS,eS)可以转化为图13所示的有限状态自动 4)递归调用ServicesTocFSA(SCSD),得到结 机，即首先将服务eS,和服务eS,进行Sequence组 果mresult 合，得到服务Sequence(eS,eS),然后再对服务 5)按2.1节介绍的对组合算子CS的组合方法 Sequence(eS!,eS,)进行Repeat-While组合 对结果mresult进行服务组合，得到一个带条件的 用Java语言实现了将几个服务转化为1个基 有限状态自动机，假设结果是result. 于有限状态自动机的组合服务算法ServicesTocF- 6)返回result. SA,算法Services TocFSA描述如下： 7)算法结束」 算法：服务组合算法Services TocFSA (a)服务es (b)服务eS (s and-)or (hand-p）or (rs and (rs and g/h (and-)or (rs and) E/E (c)服务组合 图I3服务Repeat-While(中，Sequence(eSi,eS,) Fig.13 Service Repeat_While(,Sequence(eS ,eS2) 由于算法ServicesTocFSA能够将几个服务转 化成一个有限状态自动机，从而可以根据转化后得 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
则利用 2. 1 和 2. 2 节介绍的服务组合方法可得 服务 Sequence (Sequence ( eS1 , eS2 ) , eS3 ) 和服务 Sequence (eS1 , Sequence ( eS2 , eS3 ) ) 是相同的 ,如 图 12 所示 : 图 12 服务 Sequence (Sequence (eS1 ,eS2 ) ,eS3 )和 Sequence (eS1 ,Sequence (eS2 ,eS3 ) ) Fig. 12 Service Sequence (Sequence (eS1 ,eS2 ) ,eS3 ) and Sequence (eS1 ,Sequence (eS2 ,eS3 ) ) 所以 Sequence (Sequence ( eS1 , eS2 ) , eS3 ) = Sequence (eS1 , Sequence (eS2 , eS3 ) ) . 证毕. 3 实现与分析 因为通过任意组合算子所得到的组合服务仍然 是 1 个带条件的有限状态自动机 (见 2. 3 节的性质 10) ,所以任何组合服务都可以转化为 1 个有限状态 自动机来实现. 关键问题是如何将几个服务转化为 1 个基于有限状态自动机的组合服务. 由于服务组 合算子操作的封闭性 ,可以利用递归的方法来实现 这种转化. 例如 ,服务 Repeat While (φ, Sequence (eS1 , eS2 ) ) 可以转化为图 13 所示的有限状态自动 机 ,即首先将服务 eS1 和服务 eS2 进行 Sequence 组 合 ,得到服务 Sequence ( eS1 , eS2 ) ,然后再对服务 Sequence (eS1 , eS2 ) 进行 Repeat While 组合. 用 J ava 语言实现了将几个服务转化为 1 个基 于有限状态自动机的组合服务算法 ServicesTocF2 SA ,算法 ServicesTocFSA 描述如下 : 算法 :服务组合算法 ServicesTocFSA 输入 :需要组合的原子服务、组合服务描述说明 CSD 输出 :一个带条件的有限状态自动机 1) 从组合服务描述说明 CSD 中读取第一个组 合算子 CS ,并取出组合算子 CS 的参数 PS. 2) 如果 PS 中不含组合算子 ,则按 2. 1 节介绍 的对组合算子 CS 的组合方法进行服务组合 ,得到 一个带条件的有限状态自动机 cFSA ,并 result = cFSA , Goto 6) . 3) 从 PS 中取出组合服务描述说明 CSD 的子描 述 SCSD. 4) 递归调用 ServicesTocFSA (SCSD) ,得到结 果 mresult. 5) 按 2. 1 节介绍的对组合算子 CS 的组合方法 对结果 mresult 进行服务组合 ,得到一个带条件的 有限状态自动机 ,假设结果是 result. 6) 返回 result. 7) 算法结束. 图 13 服务 Repeat While (φ,Sequence (eS1 ,eS2 ) Fig. 13 Service Repeat While (φ,Sequence (eS1 ,eS2 ) 由于算法 ServicesTocFSA 能够将几个服务转 化成一个有限状态自动机 ,从而可以根据转化后得 · 65 · 智 能 系 统 学 报 第 1 卷
第2期 蒋运承，等：基于有限状态自动机的服务组合模型 ·57 到的有限状态自动机来执行新的组合服务 1.0 EB/OL ]http :/www 3.ibm.com/software/solu 基于有限状态自动机的服务组合具有高效性， tions/webservices/pdf/WSFL.pdf,May,2001. 因为算法ServicesTocFSA是多项式时间，也就是 [9]THATTE S.XLANG:Web services for business 说，将几个服务转化为一个基于有限状态自动机的 process design[EB/OL ]http /www.gotdotnet.com/ 组合服务能在多项式时间内完成；而组合服务执行 team/xml wsspecs/xlang c/default.htm,November 12,2005. 的时间依赖于具体的服务】 [10]ANDREWS T,CURBERA F,DHOLAKIA H,et al 4结束语 Business process execution language for Web services Version 1.1 EB/OL ]http://www 106.ibm.com/ 针对目前服务计算的理论基础研究中存在的问 developer -works/webservices/library/ws bpel, 题，在D Berardi和A Wombacher的基础上研究了 November 10,2005. 基于有限状态自动机的服务组合问题.针对服务组 [11]蒋运承，史忠植.Qo$驱动的主体服务匹配[U].小型 合的需求和特点，首先提出了一种带条件的有限状 微型计算机系统，2005,26(4)：687-692. 态自动机模型cFSA,并给出了基于cFSA的服务理 JIANG Yuncheng,SHI Zhongzhi.Quality of service 论模型.在基于cFSA的服务理论模型的基础上提 driven agent service matchmaking[J].Mini-Micro Sys- tems,2005,26(4):687.692 出了一种基于有限状态自动机的服务组合的形式化 (12]BERARDI D,ROSA F D,SANTIS L D,et al.Finite 理论模型，并给出了该模型的代数性质和实现方法， state automata as conceptual model for e-Services [J ] 进一步工作主要有：研究基于有限状态自动机的服 Journal of Design Process Science:Transactions of 务组合的优化问题和验证问题等 the SDPS,Society for Process Design Sciences, 参考文献： 2003,7:21-30. [13]WOMBACHER A,FANKHAUSER P,MAHLEKO [1]PAPAZOGLOU M P,GEORGA KOPOULOS D.Serive B,et al.Matchmaking for business processes based on oriented computing [J ]Communcications of the ACM, choreographies[J].International Journal of Web Serv- 2003,46(10):25.65. ices,2004,1(4):1545-7362 [2]DIETER F,CHRISTOPH B.The Web service model- 作者简介： ing framework WSMF [J].Electronic Commerce Re- 蒋运承，男，1974年生，博士，副教 search and Applications,2002,1(2):113-137. 授，2004年毕业于中国科学院计算技术研 [3]MCLLRAITH S,SON T C,ZENG H.Semantic Web serv- 究所，现为中山大学计算机科学系博士 ices[]IEEE Intelligent Systems,2001,16(2):46-53. 后.主要研究方向为描述逻辑、语义Wb [4]蒋运承，张海俊，董明楷，史忠植.多主体系统中的动 和多Agent系统.主持和参加国家和省市 态服务匹配[J].电子学报，2004,32(3)：457-461 自然科学基金项目、863计划项目7项.在 JIANG Yuncheng,ZHANG Haijun,DONG Mingkai, 中国科学、软件学报、计算机学报等刊物上发表论文20余 SHI Zhongzhi.Dynamic service matchmaking in multi- 篇」 agent system[J ]Acta Electronica Sinica,2004,32(3): 汤席，男，1964年生，博士，教 457.461. 授，博士生导师.主要研究方向为时态数 [5]CHINNICI R,MOREAU J J,RYMAN A,et al.Web 据库、知识工程、软件工程、CSCW.主持 services description language(WSDL)Version 2.0 Part 和参加国家和省市自然科学基金、重点 1:core language EB/OL ]http://www.w3.org/TR/ 攻关、重大科技专项及地方合作项目20 wsd20/,2005-08-21. 余项.出版著作8部，科研成果获全国和 [6]MARTIN D,AN KOL EKAR A,BURSTEIN M,et al. 省厅级科技进步奖、优秀论文奖和优秀CAI软件等奖励12 OWL -S 1.I release EB/OL ]http://www.daml. 项.发表论文50余篇 org/services/owl-s/1.1/,November 26,2004. 邓培民，男，1950年生，教授，硕士 [7]史忠植，蒋运承，张海俊，董明楷.基于描述逻辑的主 生导师，毕业于广西师范大学.主要研 体服务匹配[J].计算机学报，2004,27(5)：625-635. 究方向为自动机理论及应用、计算机代 SHI Zhongzhi,JIANG Yuncheng,ZHANG Haijun, 数.主持和参加国家和省市自然科学基 DONG Mingkai.Agent service matchmaking based on 金项目3项.在计算机学报、数学进展等 description logic [J ]Chinese Journal of Computers, 刊物上发表论文20余篇」 2004,27(5):625.635. [8]LEYMANN F.Web services flow language (WSFL)Version 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
到的有限状态自动机来执行新的组合服务. 基于有限状态自动机的服务组合具有高效性 , 因为算法 ServicesTocFSA 是多项式时间 ,也就是 说 ,将几个服务转化为一个基于有限状态自动机的 组合服务能在多项式时间内完成 ;而组合服务执行 的时间依赖于具体的服务. 4 结束语 针对目前服务计算的理论基础研究中存在的问 题 ,在 D Berardi 和 A Wombacher 的基础上研究了 基于有限状态自动机的服务组合问题. 针对服务组 合的需求和特点 ,首先提出了一种带条件的有限状 态自动机模型 cFSA ,并给出了基于 cFSA 的服务理 论模型. 在基于 cFSA 的服务理论模型的基础上提 出了一种基于有限状态自动机的服务组合的形式化 理论模型 ,并给出了该模型的代数性质和实现方法. 进一步工作主要有 :研究基于有限状态自动机的服 务组合的优化问题和验证问题等. 参考文献 : [ 1 ]PAPAZO GLOU M P , GEORGA KOPOULOS D. Serive2 oriented computing [J ]. Communcications of the ACM , 2003 , 46 (10) : 25 - 65. [2 ] DIETER F , CHRISTOPH B. The Web service model2 ing framework WSMF [J ]. Electronic Commerce Re2 search and Applications , 2002 , 1 (2) : 113 - 137. [3 ] MCLLRAITH S , SON T C , ZENG H. Semantic Web serv2 ices[J ]. IEEE Intelligent Systems , 2001 , 16(2) : 46 - 53. [4 ] 蒋运承 , 张海俊 , 董明楷 , 史忠植. 多主体系统中的动 态服务匹配[J ]. 电子学报 , 2004 , 32 (3) : 457 - 461. J IAN G Yuncheng , ZHAN G Haijun , DON G Mingkai , SHI Zhongzhi. Dynamic service matchmaking in multi2 agent system[J ]. Acta Electronica Sinica , 2004 , 32 (3) : 457 - 461. [5 ] CHINNICI R , MOREAU J J , R YMAN A , et al . Web services description language (WSDL) Version 2. 0 Part 1 : core language [ EB/ OL ]. http :/ / www. w3. org/ TR/ wsdl20/ , 2005 - 08 - 21. [6 ] MARTIN D , AN KOL EKAR A , BURSTEIN M , et al . OWL - S 1. 1 release [ EB/ OL ]. http :/ / www. daml. org/ services/ owl - s/ 1. 1/ , November 26 , 2004. [7 ] 史忠植 , 蒋运承 , 张海俊 , 董明楷. 基于描述逻辑的主 体服务匹配[J ]. 计算机学报 , 2004 , 27 (5) : 625 - 635. SHI Zhongzhi , J IAN G Yuncheng , ZHAN G Haijun , DON G Mingkai. Agent service matchmaking based on description logic [J ]. Chinese Journal of Computers , 2004 , 27 (5) : 625 - 635. [8 ] LEYMANN F. Web services flow language (WSFL) Version 1. 0 [ EB/ OL ]. http :/ / www - 3. ibm. com/ software/ solu2 tions/ webservices/ pdf/ WSFL. pdf , May , 2001. [ 9 ] THA TTE S. XLAN G: Web services for business process design[ EB/ OL ]. http :/ / www. gotdotnet. com/ team/ xml_ wsspecs/ xlang - c/ default. htm , November 12 , 2005. [10 ] ANDREWS T , CURBERA F , D HOLA KIA H , et al . Business process execution language for Web services Version 1. 1 [ EB/ OL ]. http :/ / www - 106. ibm. com/ developer - works/ webservices/ library/ ws - bpel , November 10 , 2005. [11 ] 蒋运承 , 史忠植. QoS 驱动的主体服务匹配[J ]. 小型 微型计算机系统 , 2005 , 26 (4) : 687 - 692. J IAN G Yuncheng , SHI Zhongzhi. Quality of service driven agent service matchmaking[J ]. Mini2Micro Sys2 tems , 2005 , 26 (4) : 687 - 692. [12 ] BERARDI D , ROSA F D , SAN TIS L D , et al . Finite state automata as conceptual model for e2Services[J ]. Journal of Design & Process Science : Transactions of the SDPS , Society for Process & Design Sciences , 2003 , 7 : 21 - 30. [13 ] WOMBACHER A , FAN KHAUSER P , MA HL EKO B , et al . Matchmaking for business processes based on choreographies[J ]. International Journal of Web Serv2 ices , 2004 , 1 (4) : 1545 - 7362. 作者简介 : 蒋运承 , 男 , 1974 年生 , 博士 , 副教 授 , 2004 年毕业于中国科学院计算技术研 究所 , 现为中山大学计算机科学系博士 后. 主要研究方向为描述逻辑、语义 Web 和多 Agent 系统. 主持和参加国家和省市 自然科学基金项目、863 计划项目 7 项. 在 中国科学、软件学报、计算机学报等刊物上发表论文 20 余 篇. 汤 庸 , 男 , 1964 年生 , 博士 , 教 授 , 博士生导师. 主要研究方向为时态数 据库、知识工程、软件工程、CSCW. 主持 和参加国家和省市自然科学基金、重点 攻关、重大科技专项及地方合作项目 20 余项. 出版著作 8 部 , 科研成果获全国和 省厅级科技进步奖、优秀论文奖和优秀 CAI 软件等奖励 12 项. 发表论文 50 余篇. 邓培民 , 男 , 1950 年生 , 教授 , 硕士 生导师 , 毕业于广西师范大学. 主要研 究方向为自动机理论及应用、计算机代 数. 主持和参加国家和省市自然科学基 金项目 3 项. 在计算机学报、数学进展等 刊物上发表论文 20 余篇. 第 2 期 蒋运承 ,等 :基于有限状态自动机的服务组合模型 · 75 ·