D0I:10.13374/j.issnl00I63.2006.12.043 第28卷第12期 北京科技大学学报 Vol.28 No.12 2006年12月 Journal of University of Science and Technology Beijing Dec.2006 基于模糊Petri网和本体的网格服务发现 翟正利小2)杨扬) 1)北京科技大学倍息工程学院，北京1000832)临沂师范学院信息学院，临沂276005 摘要给出了一个多Agent松散耦合的网格服务发现框架.在该框架中把Agent分为三类：服 务Agent,需求Agent和服务发现Agent.提出以模糊Petn网作为服务描述语言的规范，用以发布 或请求服务，用可能性变迁表示一个服务或一个需求，输入库所代表在提供（或请求）服务前需要 成立的前提条件，输出库所表示提供（或获得）服务后成立的条件，用可能性与必然性来量化一个 服务Agmt能对一个请求提供相关服务的信心程度.最后基于本体论给出了一个支持部分匹配的 服务匹配算法，并用一个车辆维修服务系统的例子进行了说明 关键词网格服务：服务发现：多Agent;服务描述语言：模糊Petn网：本体：服务匹配 分类号TP393.01 随着互联网技术的迅速发展和应用，以及对 OIL描述Wb服务并给出了一个对应相似度的 广域分布的资源之间的共享和协同需求的增加， 计算方法，然而该方法没有考虑不确定性，不能支 网格技术[山成为近年来分布式系统领域中一个 持部分匹配，存在明显的缺陷 研究热点 2 由于网格环境下各种资源具有广域分布、异 网格服务发现的多Agent框架 构、动态变化、数量巨大、由不同的管理策略控制 在本文中，基于模糊Petri网和本体给出了一 等特点，这样的环境需要有一种不依赖集中控制 个网格服务发现的多Agent框架（见图1）·在该 的、分布式、可扩展、能适应资源动态变化并且定 框架中，Agent分三类：服务Agent提供服务（如 位性能好的资源发现机制.OGSA[)将网格技术 资源、信息、软件、设备、特定领域的问题求解能力 与Wb服务融为一体，认为一切（包括资源）都是 等)；需求Agent请求特定的服务；服务发现A~ 服务，因此资源发现就归结为服务发现，服务发 gent通过匹配机制在网格环境中为需求Agent发 现在服务提供者和消费者之间起着重要作用，是 现相关的服务Agent,需求Agent和对应的服务 网格研究中的核心技术， Agent进行通讯并决定是否订购它们的服务 1 相关工作 需求Agent 需求Agent 请求服务 返回结果 请求服务 目前，一些资源（服务）发现方案大都基于关 (SDL+Ontology) 回结果(SDL+Ontology 键字匹配，如MDS,Match Maker,UDDI等，关键 服务发现Agents (匹配机制) 词匹配有一个主要缺点，即查准率和查全率不高， 发布/取消发布服务(SDL+Ontology) 为了克服关键词匹配的缺点，业界已有不少相关 服务Agent 研究，文献[3]提出了用语义Wb描述语言 提供服务/服务组合 DAML描述服务，使用Prolog语言作为推理语言 服务Agent 的服务发现系统，根据预定义的服务属性的本体 图1基于多Aget的网格服务发现框架 属性值来发现服务，文献[4]提出以DAML S语 Fig.1 Grid service discovery based on multi-agent 言描述服务，通过服务的属性和接口的输入输出 概念匹配，得到匹配结果，文献[5]使用DAML十 框架的核心在于如何执行嵌入在服务发现 Agent中的服务匹配机制，服务匹配的过程涉及 收稿日期：2005-09-14修回日期：2006-04-10 以下几个方面： 基金项目：国家自然科学基金资助项目(No,90412012和No (1)服务描述语言提供发布和请求服务的 60673160) 作者简介：翟正利(1972一)男，讲师，博士 规范；
基于模糊 Petri 网和本体的网格服务发现 翟正利12） 杨 扬1） 1） 北京科技大学信息工程学院北京100083 2） 临沂师范学院信息学院临沂276005 摘 要 给出了一个多 Agent 松散耦合的网格服务发现框架．在该框架中把 Agent 分为三类：服 务 Agent、需求 Agent 和服务发现 Agent．提出以模糊 Petri 网作为服务描述语言的规范用以发布 或请求服务用可能性变迁表示一个服务或一个需求输入库所代表在提供（或请求）服务前需要 成立的前提条件输出库所表示提供（或获得）服务后成立的条件用可能性与必然性来量化一个 服务 Agent 能对一个请求提供相关服务的信心程度．最后基于本体论给出了一个支持部分匹配的 服务匹配算法并用一个车辆维修服务系统的例子进行了说明． 关键词 网格服务；服务发现；多 Agent；服务描述语言；模糊 Petri 网；本体；服务匹配 分类号 TP393∙01 收稿日期：20050914 修回日期：20060410 基金项目：国家自然科学基金资助项目（No．90412012和 No． 60673160） 作者简介：翟正利（1972—） 男讲师博士 随着互联网技术的迅速发展和应用以及对 广域分布的资源之间的共享和协同需求的增加 网格技术［1］ 成为近年来分布式系统领域中一个 研究热点． 由于网格环境下各种资源具有广域分布、异 构、动态变化、数量巨大、由不同的管理策略控制 等特点．这样的环境需要有一种不依赖集中控制 的、分布式、可扩展、能适应资源动态变化并且定 位性能好的资源发现机制．OGSA ［2］将网格技术 与 Web 服务融为一体认为一切（包括资源）都是 服务因此资源发现就归结为服务发现．服务发 现在服务提供者和消费者之间起着重要作用是 网格研究中的核心技术． 1 相关工作 目前一些资源（服务）发现方案大都基于关 键字匹配如 MDSMatchMakerUDDI 等．关键 词匹配有一个主要缺点即查准率和查全率不高． 为了克服关键词匹配的缺点业界已有不少相关 研究．文献 ［3］ 提出了用语义 Web 描述语言 DAML 描述服务使用 Prolog 语言作为推理语言 的服务发现系统根据预定义的服务属性的本体 属性值来发现服务．文献［4］提出以 DAML—S 语 言描述服务通过服务的属性和接口的输入输出 概念匹配得到匹配结果．文献［5］使用 DAML＋ OIL 描述 Web 服务并给出了一个对应相似度的 计算方法然而该方法没有考虑不确定性不能支 持部分匹配存在明显的缺陷． 2 网格服务发现的多 Agent 框架 在本文中基于模糊 Petri 网和本体给出了一 个网格服务发现的多 Agent 框架（见图1）．在该 框架中Agent 分三类：服务 Agent 提供服务（如 资源、信息、软件、设备、特定领域的问题求解能力 等）；需求 Agent 请求特定的服务；服务发现 Agent 通过匹配机制在网格环境中为需求 Agent 发 现相关的服务 Agent需求 Agent 和对应的服务 Agent 进行通讯并决定是否订购它们的服务． 图1 基于多 Agent 的网格服务发现框架 Fig．1 Grid service discovery based on mult-i agent 框架的核心在于如何执行嵌入在服务发现 Agent 中的服务匹配机制．服务匹配的过程涉及 以下几个方面： （1） 服务描述语言提供发布和请求服务的 规范； 第28卷 第12期 2006年 12月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．28No．12 Dec．2006 DOI:10．13374／j．issn1001－053x．2006．12．043
Vol.28 No.12 翟正利等：基于模糊Petri网和本体的网格服务发现 .1197. (2)本体标记语言解释一个Agent提供或请 L,,A…Ar,广g<1不能同时成立情况下，式(2) 求的服务描述中用到的术语的语义； 变成： (3)基于语义的服务匹配机制为需求Agent Na=mini N(AA)N. 搜索相关服务； Ig=I(nArzA...)q (4) (4)服务组合通过集成几个不同的服务来满 足需求 当几个结论相同的规则被激发时，这些导出 的具有不同置信水平的结论(q,(,)(=1, 3 基于模糊Petri网的服务描述语 …,n)应该被聚集为一个结论(q,(g1, 言(FPN-SDL) +)·该聚集可视为逻辑加法，由此可得： 3.1可能性推理 Na+=max[Na,N...Na] Dubois和Prade可提出了用可能性和必然性 +1=mar[,呢，…，] (5) 测度描述古典命题的不确定性模型.基于他们的 3.2模糊Petri网(FPN) 可能性和必然性测度提出了不确定信息的表示和 Petri网[8]1是一个加权有向二分图，由两类结 推理机制 点一库所（用圆表示）和变迁（用矩形表示）一 为了表示不确定信息，一个可能性命题表示 组成，弧只能存在于不同类型结点之间. 如下： 一个典型的Petri网解释方式，是将一个库所 r,(N, (1) 视为一个状态（条件），一个变迁视为一个状态与 其中r表示一个古典命题，N表示必然性的下 状态间的因果关系，而一个token在某一个库所 界，L表示可能性的上界（即N(r)≥N,Ⅱ(r)≤ 内可视为宣称该库所代表的状态成立的一个事 L),可能性命题“r,(N,亚)”是指说命题r是错 实，然而，真实世界的问题是常常伴随着不确定 的可能程度最多等于1一N;同时，说命题r是对 的信息·例如：(1)状态间的因果关系是不确定 的可能程度最多等于Ⅱ 的：(2)对描述真实状态的事实的信心并不完全 包含多个前提的推理规则的通式表示如下： 为考虑上述情形，定义模糊Petri网如下 (g1rzA…rn4(N6AA.Ar.qlA…r)g 定义l(模糊Peti网)模糊Petri网定义为 五元组 rl, (N) FPN=(P,Tp,F,W,Mo) (6) r2, (N2,2) 其中P=p1(r)p2(r2),…,pm(rm)是库所的有 限集，Pi代表一个古典命题ri,Tp={tu(N1, In (Nr.n) 山)t2(N2,2),…,tn(Nn,L)是可能性变迁 Na.ng) 的有限集，t代表状态间的因果联系，而N代表 (2) 必然性测度的下界，凸代表可能性测度的上界来 为了推出Ng和L,使用Nilsson提出的 指出对该因果联系的不确定性.F三(PXTP)U Possibilistic entailment方法从一个带有关联可 (Tp×P)是弧集.W:F→1,2,3，…}是一个权 能性的命题集推导出一个带有关联可能性的新命 重函数.Mo={M(p1),M(p2),,M(Pn)是一 题，在执行Possibilistic entailment之后，得到如下 个初始标识，其中M(P:)是库所p:中的可能性 结论： token(附有必然性和可能性)数目· Ng=minimax{Ne,As,Ar,)gl-Π]， 定义2（发生规则）使能的可能性变迁的发 max[1-eA…rgV]} 生从其每个输入库所移走可能性token并在其每 个输出库所中加入新的可能性token,附加在新 =max min[ token上的必然性和可能性测度值基于可能性推 min[LeA,A…Ar,广g'1-N,]} 理进行计算， (3) 3.3以FPN作为服务描述语言的基础 在上式中，N,=min[N,Ng,N,],L= 使用模糊Petri网作为服务描述语言的基础 min[,L,,L].在·<1和 并称其为FPN-SDL,用于Agent在一个网格环境
（2） 本体标记语言解释一个 Agent 提供或请 求的服务描述中用到的术语的语义； （3） 基于语义的服务匹配机制为需求 Agent 搜索相关服务； （4） 服务组合通过集成几个不同的服务来满 足需求． 3 基于模糊 Petri 网的服务描述语 言（FPN-SDL） 3∙1 可能性推理 Dubois 和 Prade ［6］提出了用可能性和必然性 测度描述古典命题的不确定性模型．基于他们的 可能性和必然性测度提出了不确定信息的表示和 推理机制． 为了表示不确定信息一个可能性命题表示 如下： r（ NrΠr） （1） 其中 r 表示一个古典命题Nr 表示必然性的下 界Πr 表示可能性的上界（即 N（r）≥ NrΠ（r）≤ Πr）．可能性命题“r（ NrΠr）”是指说命题 r 是错 的可能程度最多等于1— Nr；同时说命题 r 是对 的可能程度最多等于 Πr． 包含多个前提的推理规则的通式表示如下： （r1∧r2∧…∧r n）→q （ N（r1∧r2∧…∧r n ）→qΠ（r1∧r2∧…∧r n ）→q） r1 （ Nr1 Πr1 ） r2 （ Nr2 Πr2 ） r n （ Nr n Πr n ） q （ NqΠq） （2） 为了推出 Nq 和 Πq使用 Nilsson 提出的 Possibilistic entailment ［7］ 方法从一个带有关联可 能性的命题集推导出一个带有关联可能性的新命 题．在执行Possibilistic entailment 之后得到如下 结论： Nq＝min｛max｛N（r1∧r2∧…∧r n ）→q1—Πr ］ max ［1—Π（r1∧r2∧…∧r n ）→qNr ］｝ Πq＝max｛min［Π（r1∧r2∧…∧r n ）→qΠr ］ min［Π（r1∧r2∧…∧r n ）→q1— Nr ］｝ （3） 在上式中Nr＝min［ Nr1Nr2…Nr n ］Πr＝ min ［ Πr1Πr2…Πr n ］． 在 Πr ＜ 1 和 Π（r1∧r2∧…∧r n ）→q＜1不能同时成立情况下式（2） 变成： Nq＝min｛N（r1∧r2∧…∧r n ）→qNr｝ Πq＝Π（r1∧r2∧…∧r n ）→q （4） 当几个结论相同的规则被激发时这些导出 的具有不同置信水平的结论（q（ N i qΠi q））（ i＝1 …n ） 应 该 被 聚 集 为 一 个 结 论 （q（ N n＋1 q Πn＋1 q ））．该聚集可视为逻辑加法由此可得： N n＋1 q ＝max ［ N 1 qN 2 q…N n q ］ Πn＋1 q ＝max ［Π1 qΠ2 q…Πn q ］ （5） 3∙2 模糊 Petri 网（FPN） Petri 网［8］是一个加权有向二分图由两类结 点———库所（用圆表示）和变迁（用矩形表示）——— 组成弧只能存在于不同类型结点之间． 一个典型的 Petri 网解释方式是将一个库所 视为一个状态（条件）一个变迁视为一个状态与 状态间的因果关系而一个 token 在某一个库所 内可视为宣称该库所代表的状态成立的一个事 实．然而真实世界的问题是常常伴随着不确定 的信息．例如：（1）状态间的因果关系是不确定 的；（2）对描述真实状态的事实的信心并不完全． 为考虑上述情形定义模糊 Petri 网如下． 定义1（模糊 Petri 网） 模糊 Petri 网定义为 五元组 FPN＝（PTpFWM0） （6） 其中 P＝｛p1（r1）p2（r2）…p m（r m）｝是库所的有 限集p i 代表一个古典命题 riTP ＝｛t1（ N1 Π1）t2（ N2Π2）…t n （ NnΠn）｝是可能性变迁 的有限集t j 代表状态间的因果联系而 Nj 代表 必然性测度的下界Πj 代表可能性测度的上界来 指出对该因果联系的不确定性．F⊆（ P× TP）∪ （ TP×P）是弧集．W∶F→｛123…｝是一个权 重函数．M0＝｛M（p1）M（p2）…M（p n）｝是一 个初始标识其中 M（p i）是库所 p i 中的可能性 token（附有必然性和可能性）数目． 定义2（发生规则） 使能的可能性变迁的发 生从其每个输入库所移走可能性 token 并在其每 个输出库所中加入新的可能性 token附加在新 token 上的必然性和可能性测度值基于可能性推 理进行计算． 3∙3 以 FPN 作为服务描述语言的基础 使用模糊 Petri 网作为服务描述语言的基础 并称其为 FPN-SDL用于 Agent 在一个网格环境 Vol．28No．12 翟正利等： 基于模糊 Petri 网和本体的网格服务发现 ·1197·
,1198 北京科技大学学报 2006年第12期 下的发布、请求和匹配服务等动作.可能性变迁 开发一个本体不仅包括使用本体标记语言， 表示一个服务或一个需求，输入库所代表在提供 也应该包含通过类分层来建立概念（类）之间的关 (或请求)服务前需要成立的前提条件，输出库所 系.例1中，需要有两个类的分层来表示有关Ve- 表示提供（或获得）服务后成立的条件，如例1 hicle和World的类之间的关系（见图4） 所示， World Vehicle 例1假设一个技工在北京工作，专门维修 0.8 0.90.8 0.80.80.7T0.9USA China Japan 有篷货车，其服务可用图2(a)中所示的服务A- Bus Truch Van Car 0.910.7 0.5 gent表示.假设有一个人，其卡车在天津出现故 Beijing Tianjin Shanghai 障并请求修理服务，其需求可用图2(b)所示的需 图4 Vehicle和World的类分层 求Agent表示， Fig.4 Class hierarchies of Vehicle and World 在图2中，变量)（或》）是一个实际输入 输出需要匹配的表达式，被附加到可能性变迁的 4 FPN-SDL的匹配机制 输入/输出弧上 一 旦服务发现Agent收到请求，就通过服务 IP ( 服务 IP,() 需求 so(1,) t1,1) 匹配机制在其服务注册处为请求查找相关的服 OP,(q) OP(q2) <y 务，为了支持部分匹配，使用可能性和必然性来 ○ P(红) P()9 表示对一个服务Agent能为需求Agent提供相关 ○：有篷货车<0出现故障○卡车y出现故障 <它的位置在北京 炉的位置在天津 服务的信心程度， 9:有蕴货车<x>维修正常 9P故障消除 (a) (b) 4.1两个类之间的可能性和必然性测度 为了基于语义比较服务和需求，匹配机制通 图2 PN-SDL示例.(a)服务Agent;(b)需求Aget 过计算两个类在类分层中的相似度来量化置信度 Fig-2 FPN-SDL for (a)Service agent and (b)Request agent (也就是可能性和必然性)， 3.4SDL的本体 定义3（邻接的超类和子类的相似度）对两 本体(ontology)定义了用户在共享信息时所 个邻接的超类和子类(c1,c2)都赋予一个惟一的 使用的一种通用词汇，用以定义某领域内的概念、 相似度S(c1,c2),范围从0到1. 概念与概念间的相关性.在这里通过分层(hier- 例如，在图4中，类Vehicle和Van之间的相 archy)的方法，建立类和子类的关系，去发现他们 似度赋值为0.7. 在语义上的关联性， 定义4（两类的最小公共超类）令类1和 用DAML十OIL作为一个本体语言来对类 c2的最小公共超类记为CS(c1,c2),有： (子类)的概念和有关服务、用户约束的关系进行 CS(c1,c2)=glsu(g,cI)Asu(g.c2)A 编码，主要是因为它有良好定义的模型理论语义 (Hc≠g)(su(c,c1)Asu(c,c2)→su(c,g) 和公理化描述.如图3所示，例1中类Van是 (7) Vehicle的子类，并且和类Truck是不相交的，其 其中su(x,y)是谓词，表示x是y的超类 主要属性是有一个封闭的盒子似的外观 CS(c1,c2)指出了包含c1和c2的最特殊的 daml:Class rdf:ID="Van? 类.如果两个类c1和c2位于两个不同的类分层 (oiled :creationData 10:30:30 15.06.200 /oiled:creationData 中，则CS(c1,c2)不存在 (rdfs:subClassOf rdfs:resource=#vehicle/rdfs:subClass0 daml:disjoint With rdfs:resourceTruck)/daml:disjoint With 定义5（任意两个类的相似度）令类c1和 〈rdfs:subClassO0 c2的相似度记为S(c1,c2),有： daml:Restriction) (1)S(c1,c2)=S(c1,CS(c1,c2)XS <daml:onProperty rdfs:resource=#hasEnclosedBox-likeLook (c2,CS(c1,c2)); 〈/daml:onProperty) (2)S(c1,c2)=1,如果c1=c2; </daml:Restriction 〈/rds:subClassOf (3)S(c1,c2)=0,如果CS(c1,c2)不存在. 〈/daml:Class 例如，在图4中，S(Van,Truck)=0.7X 图3藉由DAML十OL表示的类Van的本体 0.8. Fig-3 Ontology of class Van depicted by DAML+OIL 根据Ruspinif1o]提出的一致性和蕴含性的概
下的发布、请求和匹配服务等动作．可能性变迁 表示一个服务或一个需求输入库所代表在提供 （或请求）服务前需要成立的前提条件输出库所 表示提供（或获得）服务后成立的条件．如例1 所示． 例1 假设一个技工在北京工作专门维修 有篷货车．其服务可用图2（a）中所示的服务 Agent 表示．假设有一个人其卡车在天津出现故 障并请求修理服务其需求可用图2（b）所示的需 求 Agent 表示． 在图2中变量〈x〉（或〈y〉）是一个实际输入 输出需要匹配的表达式被附加到可能性变迁的 输入／输出弧上． 图2 FPN-SDL 示例．（a） 服务 Agent；（b） 需求 Agent Fig．2 FPN-SDL for （a） Service agent and （b） Request agent 3∙4 SDL 的本体 本体（ontology）定义了用户在共享信息时所 使用的一种通用词汇用以定义某领域内的概念、 概念与概念间的相关性．在这里通过分层（hierarchy）的方法建立类和子类的关系去发现他们 在语义上的关联性． 用 DAML＋OIL 作为一个本体语言来对类 （子类）的概念和有关服务、用户约束的关系进行 编码主要是因为它有良好定义的模型理论语义 和公理化描述［9］．如图3所示例1中类 Van 是 Vehicle 的子类并且和类 Truck 是不相交的其 主要属性是有一个封闭的盒子似的外观． 〈daml：Class rdf：ID＝“Van”〉 〈oiled：creationData〉10：30：3015．06．2005〈／oiled：creationData〉 〈rdfs：subClassOf rdfs：resource＝＃vehicle〉〈／rdfs：subClassOf〉 〈daml：disjointWith rdfs：resource＝＃Truck〉〈／daml：disjointWith〉 〈rdfs：subClassOf〉 〈daml：Restriction〉 〈daml：onProperty rdfs：resource＝＃hasEnclosedBox-likeLook〉 〈／daml：onProperty〉 〈／daml：Restriction〉 〈／rdfs：subClassOf〉 〈／daml：Class〉 图3 藉由 DAML＋OIL 表示的类 Van 的本体 Fig．3 Ontology of class Van depicted by DAML＋OIL 开发一个本体不仅包括使用本体标记语言 也应该包含通过类分层来建立概念（类）之间的关 系．例1中需要有两个类的分层来表示有关 Vehicle 和 World 的类之间的关系（见图4）． 图4 Vehicle 和 World 的类分层 Fig．4 Class hierarchies of Vehicle and World 4 FPN-SDL 的匹配机制 一旦服务发现 Agent 收到请求就通过服务 匹配机制在其服务注册处为请求查找相关的服 务．为了支持部分匹配使用可能性和必然性来 表示对一个服务 Agent 能为需求 Agent 提供相关 服务的信心程度． 4∙1 两个类之间的可能性和必然性测度 为了基于语义比较服务和需求匹配机制通 过计算两个类在类分层中的相似度来量化置信度 （也就是可能性和必然性）． 定义3（邻接的超类和子类的相似度） 对两 个邻接的超类和子类（ c1c2）都赋予一个惟一的 相似度 S（ c1c2）范围从0到1． 例如在图4中类 Vehicle 和 Van 之间的相 似度赋值为0∙7． 定义4（两类的最小公共超类） 令类 c1 和 c2 的最小公共超类记为 CS（ c1c2）有： CS（ c1c2）＝｛g｜su（ gc1）∧su（ gc2）∧ （∀c≠g）（su（ cc1）∧su（ cc2）→su（ cg））｝ （7） 其中 su（ xy）是谓词表示 x 是 y 的超类． CS（ c1c2）指出了包含 c1 和 c2 的最特殊的 类．如果两个类 c1 和 c2 位于两个不同的类分层 中则 CS（ c1c2）不存在． 定义5（任意两个类的相似度） 令类 c1 和 c2 的相似度记为 S（ c1c2）有： （1） S （ c1c2）＝ S （ c1CS （ c1c2））× S （ c2CS（ c1c2））； （2） S（ c1c2）＝1如果 c1＝c2； （3） S（ c1c2）＝0如果 CS（ c1c2）不存在． 例如在图4中S （VanTruck） ＝0∙7× 0∙8． 根据 Ruspini ［10］提出的一致性和蕴含性的概 ·1198· 北 京 科 技 大 学 学 报 2006年第12期
Vol.28 No.12 翟正利等：基于模糊Petri网和本体的网格服务发现 .1199 念，定义两个类之间的一致性和蕴含性来量化对 一个服务并转步骤(1) 一个服务能完成请求的信心程度 (3)计算服务的输出库所能推出需求的输出 定义6（两个类的一致性）令类c1和c2的 库所的可能性Ⅱ=C(ce→ca)和必然性N= 一致性记为C(c1→c2),有： I(ce→ca).这一步计算对服务Agent在所有前 (1)C(c1→c2)=1,如果CS(c1,c2)存在； 提条件都成立时能胜任需求的信心程度 (2)C(c1→c2)=0,如果CS(c1,c2)不存在， (4)对服务的输入库所IPk(rk)和需求的输 实际上，两个类的一致性可以被视为可能性， 入库所IP(r)中提到的类c:,和c,在类分层中 因此，把两个类之间的可能性定义为一致性，即 找到其位置；如果c,和c,有相同的类分层，则计 Π(c1→cz)=C(c1>cz) 定义7（两个类的蕴含性）记类c1蕴含c2 算需求的输入库所能推出服务的输入库所的可能 的程度为I(c1→c2),有： 性Π(c,→c,)和必然性N(c,→c,),也就是说， (1)I(c1→c2)=1,如果CS(c1,c2)=c2; (c,→c)=C(c,→c),N(c,→c)=I(c,→ (2)1(c1→c2)=S(c1,c2),如果c1和c2在 c),其中k=1,…,n和l=n十1，…，n十m,这 同一个类分层中且CS(c1,c2)≠c2; 一步是根据现状，计算对满足该服务所需前提条 (3)I(c1→c2)=0,如果c1和c2不在同一个 件的信心程度 类分层中. (5)如果任何一对(c,c.)都不在相同的类 例如，在图4中，I(Van→Vehicle)=l,I(Ve- 分层中，也就是说，当前的服务不满足需求，则选 hicle Van)=0.7,I(Van->Truck)=0.56. 择另外的服务并转步骤(1)· 实际上，两个类之间的蕴含程度可被视为必 (6)在需求的所有输入库所中插入确定的 然性，即N(c1→c2)=I(c1→cz)· token,即(N,Ⅱ)=(1,1)，代表当前的前提条件， 4.2匹配算法 然后通过变迁t。~tm+3(其输入库所是需求的输 考虑图5中的一个服务与一个需求，需求有 入库所，输出库所是服务的输入库所)来执行可能 m个输入库所来描述在没有得到服务之前的情 性推理，其中变迁t4~1+3上都附加了从步骤(4) 况，用以下的算法选择一个有n个输入库所的服 中导出的可能性和必然性程度 务去匹配需求(n≤m) (T)通过确定的服务变迁1来执行可能性推 P-( 需求 理.导出的可能性和必然性程度代表我们对该服 每 °t(1,) 务能在部分匹配前提条件的情况下被执行的信心 IP( OP(q) 程度，然后通过变迁t3(它的输入库所是服务的 <y> 输出库所，输出库所需求的输出库所)来执行可能 @ P《) 9y 性推理，其中变迁t3被附加上了从步骤(3)导出 的可能性和必然性程度，最后导出的可能性和必 IP (, 服务 然性程度就是对该服务能实现需求的总体信心程 t1,1) 度 N.) P 例2重新考虑例1，其匹配过程如图6所 OP(q) t(N几) 示，首先，对在服务和需求的输出库所中提及的 类Van和Truck,基于类的属性在图4的类分层 图5服务匹配需求示意图 中找到合适的位置，第二步，因为在Truck和 Fig.5 Matching request with service Van之间的相似性为0.56，(0P1(qm)→0P2(q2) 的可能性和必然性程度计算为(0.56,1)，第三 算法： 步，对于在服务和需求的输入库所中提到的类 (1)对在服务和需求的输出库所OP1(q印)和 Van、Beijing、Truck和Tianjin,在图4的类分层中 OPz(q2)中提到的类ca,和ce,基于语法和语义匹 基于类的属性找到合适的位置，第四步，(IP3(3) 配在类分层中找到它们的位置 IP1(r1)和IP4(r4)→IP2(r2))的必然性和可能 (2)如果类c和c,位于两个不同的类分层 性程度分别计算为(0.56,1)和(0.63,1)，表示 中，也就是说，他们属于不同的本体，则选择另外 对满足该服务前提条件的信心程度，最后，依次
念定义两个类之间的一致性和蕴含性来量化对 一个服务能完成请求的信心程度． 定义6（两个类的一致性） 令类 c1 和 c2 的 一致性记为 C（ c1→c2）有： （1） C（ c1→c2）＝1如果 CS（ c1c2）存在； （2） C（ c1→c2）＝0如果 CS（ c1c2）不存在． 实际上两个类的一致性可以被视为可能性 因此把两个类之间的可能性定义为一致性即 Π（ c1→c2）＝C（ c1→c2）． 定义7（两个类的蕴含性） 记类 c1 蕴含 c2 的程度为 I（ c1→c2）有： （1） I（ c1→c2）＝1如果 CS（ c1c2）＝c2； （2） I（ c1→c2）＝S（ c1c2）如果 c1 和 c2 在 同一个类分层中且 CS（ c1c2）≠c2； （3） I（ c1→c2）＝0如果 c1 和 c2 不在同一个 类分层中． 例如在图4中I（Van→Vehicle）＝1I（Vehicle→Van）＝0∙7I（Van→Truck）＝0∙56． 实际上两个类之间的蕴含程度可被视为必 然性即 N（ c1→c2）＝I（ c1→c2）． 4∙2 匹配算法 考虑图5中的一个服务与一个需求需求有 m 个输入库所来描述在没有得到服务之前的情 况用以下的算法选择一个有 n 个输入库所的服 务去匹配需求（ n≤ m）． 图5 服务匹配需求示意图 Fig．5 Matching request with service 算法： （1） 对在服务和需求的输出库所 OP1（q1）和 OP2（q2）中提到的类 cq1和 cq2基于语法和语义匹 配在类分层中找到它们的位置． （2） 如果类 cq1和 cq2位于两个不同的类分层 中也就是说他们属于不同的本体则选择另外 一个服务并转步骤（1）． （3） 计算服务的输出库所能推出需求的输出 库所的可能性 Π＝ C（ cq2→ cq1 ）和必然性 N ＝ I（ cq2→cq1 ）．这一步计算对服务 Agent 在所有前 提条件都成立时能胜任需求的信心程度． （4） 对服务的输入库所 IP k （r k）和需求的输 入库所 IP l（rl）中提到的类 cr k和 cr l在类分层中 找到其位置；如果 cr k和 cr l有相同的类分层则计 算需求的输入库所能推出服务的输入库所的可能 性 Π（ cr l→cr k ）和必然性 N（ cr l→cr k ）也就是说 Π（ cr l→cr k ）＝C（ cr l→cr k ）N（ cr l→cr k ）＝ I（ cr l→ cr k ）其中 k＝1…n 和 l＝ n＋1…n＋ m．这 一步是根据现状计算对满足该服务所需前提条 件的信心程度． （5） 如果任何一对（ cr lcr k ）都不在相同的类 分层中也就是说当前的服务不满足需求则选 择另外的服务并转步骤（1）． （6） 在需求的所有输入库所中插入确定的 token即（ NΠ）＝（11）代表当前的前提条件 然后通过变迁 t n～t n＋3（其输入库所是需求的输 入库所输出库所是服务的输入库所）来执行可能 性推理其中变迁 t4～t n＋3上都附加了从步骤（4） 中导出的可能性和必然性程度． （7） 通过确定的服务变迁 t1 来执行可能性推 理．导出的可能性和必然性程度代表我们对该服 务能在部分匹配前提条件的情况下被执行的信心 程度．然后通过变迁 t3（它的输入库所是服务的 输出库所输出库所需求的输出库所）来执行可能 性推理其中变迁 t3 被附加上了从步骤（3）导出 的可能性和必然性程度．最后导出的可能性和必 然性程度就是对该服务能实现需求的总体信心程 度． 例2 重新考虑例1其匹配过程如图6所 示．首先对在服务和需求的输出库所中提及的 类 Van 和 Truck基于类的属性在图4的类分层 中找到合适的位置．第二步因为在 Truck 和 Van 之间的相似性为0∙56（OP1（q1）→OP2（q2）） 的可能性和必然性程度计算为（0∙561）．第三 步对于在服务和需求的输入库所中提到的类 Van、Beijing、Truck 和 Tianjin在图4的类分层中 基于类的属性找到合适的位置．第四步（IP3（r3） →IP1（r1））和 IP4（r4）→IP2（r2））的必然性和可能 性程度分别计算为（0∙561）和（0∙631）表示 对满足该服务前提条件的信心程度．最后依次 Vol．28No．12 翟正利等： 基于模糊 Petri 网和本体的网格服务发现 ·1199·
,1200 北京科技大学学报 2006年第12期 触发概率变迁t4,t5,t1和t3并由此得到该服务 必然性是0.72.最后，可以选择技工C来完成该 Agent能满足需求的必然性和可能性程度为 服务，因为他具有最高的完成需求的必然性， (0.56,1),也就是说，有可能该技工会到天津并 修好故障的卡车，尽管他擅长于修理有篷货车；然 5结论 而他能完成该需求的必然性只是0.56. 本文提出了一个网格服务发现的、集成了模 需求 糊Petri网和本体论的多Agent框架，在该框架 Pr） 1,1) OPx(q) 中，Agent被分为三类：服务Agent提供诸如资 源、设施、人员、特定领域的问题求解能力等等的 IP 服务；需求Agent请求某些特定的服务；服务发现 服务 Agent通过匹配机制为需求Agent找到合适的服 t1,1) 务Agent.提出了一个基于模糊Petri网的服务描 述语言(FPN-SDL),作为发布和请求服务的规 IP ( t0.63,1) 0P.(9) 范，并用可能性和必然性量度来量化服务能胜任 需求的信心程度，同时，提出了一个基于语义并 图6用服务来匹配需求的示例 融合了类分层的服务匹配机制，所给出的匹配机 Fig.6 Example of matching request with service 制通过使用可能性和必然性程度代表服务能胜任 需求的置信度，从而能支持部分匹配， 例3在例1中再考虑一个更为复杂的情 况：对该请求有三个可能的服务，除了前面提到 参考文献 的技工（记为技工A以示区分）在北京工作，擅长 [1】都志辉，陈渝，刘鹏.网格计算.清华大学出版社，2002 修理有篷货车；技工B在上海工作，专修卡车：技 [2]Foster I.Kesselman C.Nick J.et al.Grid services for dis- 工C在天津工作，擅长修理小轿车， tributed system integration.IEEE Comput,2002.35(6):37 对于技工B的情况，因为该技工正好完全胜 [3]Chakraborty D.Perich F.Avancha S,et al.Dreggie:Seman- 任此需求，所以(OP1(q1)·OP2(q2)的可能性和 tic service discovery for mcommerce applications/Proceed- ings of the Workshop on Reliable and Secure Applications in 必然性程度计算为(1,1)，(IP3(r3)P1(r1))和 Mobile Environment.New Orleans:IEEE Computer Society. (IP4(r4)→P2(r2)的必然性和可能性程度分别 2001:28 计算为(1,1)和(0.35,1).依次触发概率变迁 [4]Payne T R.Paolucci M.Sycara K.Advertising and matching t4,t5,t1和t3并由此得到技工B能满足需求的必 DAMLS service descriptions/Proceedings of the Internation- al Semantic Web Working Symposium.Amsterdam:IOS 然性和可能性程度为(0.35,1)·也就是说，有可 Press,2001:411 能该技工会到天津并修好故障的卡车；然而他会 [5]Gonzales-Castillo J.Trastour D.Bartolini C.Deseription log 去天津的必然性只是0.35. ics for matchmaking of services//Proceedings of Workshop on 对于技工C的情况，因为在卡车和小轿车之 Application of Description Logics.Vienna:IEEE Computer 间的相似性为0.72，(0P1(q1)→0Pz(q2)的可能 Society.2001:74 [6]Dubois D,Prade H.The three semantics of fuzy sets.Fuzy 性和必然性程度计算为(0.72,1)，(IP3(r3)→ Sets Syst,1997,90(2):141 IP1(r1))和(IP4(r4)IP2(r2)的必然性和可能性 [7]Nilsson N J.Probabilistic logic.Artif Intell,1986.28 (1):71 程度分别计算为(0.72,1)和(1,1).依次触发概 [8]Murata T.Petri nets:properties,analysis and applications. 率变迁t4,t5,t1和t3并由此得到技工C能满足需 Proc IEEE,1989,77(4):541 求的必然性和可能性程度为(0.72,1)，换句话 [9]Mellraith S A.Son T C.Zeng H.Semantic web services. IEEE Intell Syst.2001,16(2):46 说，技工C有修好故障卡车的可能性.因为他擅 [10]Ruspini E H.On the semantics of fuzzy logic,Int J Approxi- 长修理小轿车而不是卡车，所以他能完成需求的 mate Reasoning.1991.5:45
触发概率变迁 t4t5t1 和 t3 并由此得到该服务 Agent 能满足需求的必然性和可能性程度为 （0∙561）．也就是说有可能该技工会到天津并 修好故障的卡车尽管他擅长于修理有篷货车；然 而他能完成该需求的必然性只是0∙56． 图6 用服务来匹配需求的示例 Fig．6 Example of matching request with service 例3 在例1中再考虑一个更为复杂的情 况：对该请求有三个可能的服务．除了前面提到 的技工（记为技工 A 以示区分）在北京工作擅长 修理有篷货车；技工 B 在上海工作专修卡车；技 工 C 在天津工作擅长修理小轿车． 对于技工 B 的情况因为该技工正好完全胜 任此需求所以（OP1（q1）→OP2（q2））的可能性和 必然性程度计算为（11）．（IP3（r3）→IP1（r1））和 （IP4（r4）→IP2（r2））的必然性和可能性程度分别 计算为（11）和（0∙351）．依次触发概率变迁 t4t5t1 和 t3 并由此得到技工 B 能满足需求的必 然性和可能性程度为（0∙351）．也就是说有可 能该技工会到天津并修好故障的卡车；然而他会 去天津的必然性只是0∙35． 对于技工 C 的情况因为在卡车和小轿车之 间的相似性为0∙72（OP1（q1）→OP2（q2））的可能 性和必然性程度计算为（0∙721）．（IP3（r3）→ IP1（r1））和（IP4（r4）→IP2（r2））的必然性和可能性 程度分别计算为（0∙721）和（11）．依次触发概 率变迁 t4t5t1 和 t3 并由此得到技工 C 能满足需 求的必然性和可能性程度为（0∙721）．换句话 说技工 C 有修好故障卡车的可能性．因为他擅 长修理小轿车而不是卡车所以他能完成需求的 必然性是0∙72．最后可以选择技工 C 来完成该 服务因为他具有最高的完成需求的必然性． 5 结论 本文提出了一个网格服务发现的、集成了模 糊 Petri 网和本体论的多 Agent 框架．在该框架 中Agent 被分为三类：服务 Agent 提供诸如资 源、设施、人员、特定领域的问题求解能力等等的 服务；需求 Agent 请求某些特定的服务；服务发现 Agent 通过匹配机制为需求 Agent 找到合适的服 务 Agent．提出了一个基于模糊 Petri 网的服务描 述语言（FPN-SDL）作为发布和请求服务的规 范并用可能性和必然性量度来量化服务能胜任 需求的信心程度．同时提出了一个基于语义并 融合了类分层的服务匹配机制．所给出的匹配机 制通过使用可能性和必然性程度代表服务能胜任 需求的置信度从而能支持部分匹配． 参 考 文 献 ［1］ 都志辉陈渝刘鹏．网格计算．清华大学出版社2002 ［2］ Foster IKesselman CNick Jet al．Grid services for distributed system integration．IEEE Comput200235（6）：37 ［3］ Chakraborty DPerich FAvancha Set al．Dreggie：Semantic service discovery for m-commerce applications∥ Proceedings of the Workshop on Reliable and Secure Applications in Mobile Environment．New Orleans：IEEE Computer Society 2001：28 ［4］ Payne T RPaolucci MSycara K．Advertising and matching DAML-S service descriptions∥Proceedings of the International Semantic Web Working Symposium． Amsterdam： IOS Press2001：411 ［5］ Gonzales-Castillo JTrastour DBartolini C．Description logics for matchmaking of services∥Proceedings of Workshop on Application of Description Logics．Vienna：IEEE Computer Society2001：74 ［6］ Dubois DPrade H．The three semantics of fuzzy sets．Fuzzy Sets Syst199790（2）：141 ［7］ Nilsson N J．Probabilistic logic．Artif Intell198628（1）：71 ［8］ Murata T．Petri nets：propertiesanalysis and applications． Proc IEEE198977（4）：541 ［9］ McIlraith S ASon T CZeng H．Semantic web services． IEEE Intell Syst200116（2）：46 ［10］ Ruspini E H．On the semantics of fuzzy logicInt J Approximate Reasoning19915：45 ·1200· 北 京 科 技 大 学 学 报 2006年第12期