基于Ontology的Web服务组合方法，本文主要内容关键词为：组合论文,方法论文,Ontology论文,Web论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
【分类号】TP393
1 引言
随着Web服务和Ontology等各项技术，特别是语义Web本体标记语言OWL[1]的迅猛发展和逐步完善，人们对利用Ontology来智能化地整合各种Web服务资源的前景充满希望。而Web服务组合作为这一整合过程中的关键技术之一，从一开始就受到众多研究人员的广泛关注，并且随着Ontology相关技术的推广，从语义层次上进行Web服务组合的技术已成为Web服务发展的一个新亮点。
Web服务组合方法的研究工作主要来自两个领域：一个是人工智能领域，另一个是形式化方法和自动推理领域。人工智能以及形式化方法和自动推理这两个领域的工作既互相交叉，又互为补充。来自人工智能领域中的工作包括构建用于Web服务描述的本体，以便更好地支持Web服务资源的智能化整合。人工智能领域中的研究人员也从人工智能规划(AI Planning)的角度提出了一系列的面向Web服务功能的Web服务组合（规划）方案[3-5]。来自形式化方法和自动推理领域的工作除了面向Web服务行为的服务组合（验证）方法[6,7]，也不乏借鉴自动化程序综合(Program Synthesis)[8]和模型检验(Model Checking)的方法[9]。
本文以整合来自上述两个领域的Web服务组合方法为目标，以基于Web服务行为功能的组合方法为蓝本，辅以Ontology进行Web服务组合，来提供功能上和行为上都能满足用户的组合服务。
2 现有的Web服务组合技术探讨
2.1 基于人工智能规划的组合方法
这类方法的基本思想是使用人工智能规划中的动作来对Web服务进行建模，利用人工智能中的规划算法来进行Web服务组合。人工智能规划的理论基础是情景演算，但是具体的人工智能规划算法则是多种多样的，有采用逻辑程序等自动推理工具的规划算法[3-5]，有采用模型检验的规划算法[9]，还有利用图的各种搜索算法的规划算法[10]，也不乏利用机器学习来加速图搜索的规划算法。文献[3]是这类方法的先行者，它把Web服务看作AI规划中的动作，因而Web服务组合的过程就是产生计划的过程。其所采用的规划算法是在逻辑程序Golog上改进而来的，而Golog是采用逻辑编程语言Prolog来实现情景演算的。文献[4]提出的基于HTN(Hierarchical Task Network)规划算法的服务组合的方案以及文献[5]采用的基于描述逻辑的服务组合方法也是沿用这样的思路。
在情景演算中，动作由动作的前提条件和效应所刻画，而动作的前提条件和效应是参与动作的个体的一组状态构成的，动作的执行将使得某些个体处于新的状态之中。例如，在经典的积木世界里面，使用手臂举起物体ob的动作Pickup可用PDDL(Planning Domain Definition Language)描述如下：
(:action pickup
:parameters(?ob)
:precondition(and(clear?ob)(arm-empty))
:effect(and(holding?ob)(not(arm-empty))(when(on-table?oL)(not(on-table?ob))))
)
不难发现，基于人工智能规划的Web服务组合方法至少存在以下不足：
(1)针对经典规划问题提出的情景演算仅能产生由一组顺序动作构成的计划，因而Golog（及其变种ConGolog）在处理Web服务的非不确定性和并发性时的行为更像是一个解释器，而不是一个规划产生器。也就是说，基于人工智能规划的Web服务组合方法无法产生能够与Web服务的非确定性和并发性相适应的组合服务。
(2)Web服务的行为特性和经典规划中的动作的行为特性是非常不一样的，这使得规划算法难以在Web服务组合中得到实用。因为Web服务的执行通常会导致新的个体产生，这些个体通常作为Web服务执行的结果返回给用户；而在经典规划中，参与规划的个体不会在规划的过程中产生或消失，动作执行只是导致个体的状态发生变化。
2.2 基于Web服务行为的组合方法
基于Web服务行为的组合方法能够克服基于人工智能规划的Web服务组合方法中上述的缺点，但是它又无法在Web服务功能上满足用户的需求。下面先介绍这一方法，然后在第3部分对它进行改进。
Web服务的行为通常借助自动机或进程代数进行表述。例如，一个接收Search消息然后发送Result消息的Web服务S可以用图1(a)中的进程代数公式来刻画：
图1 刻画一组Web服务行为的进程代数公式
如果不区分消息前缀“？”和“！”在意义上的不同，那么图1(a)中的各式同时也刻画了一个自动机，它的字母表为｛?search,!result｝，状态集为｛S[,0],S[,1]｝，并且S[,0]既是初始状态也是终止状态。由此可见，可以把进程代数看作自动机这个普遍理论中的一个特例。文献[6]讨论了如何使用进程代数进行Web服务验证，文献[7]除给出了使用自动机从服务行为的角度对Web服务进行组合的方案外，还利用了动态命题逻辑(Propositional Dynamic Logics,PDL)对刻画Web服务行为的自动机进行编码。（从这个编码过程中，可以看到，只要增添一组刻画τ动作的PDL公式，该方案同样适用于进程代数。）
为方便下文叙述，笔者在图1(b)和图1(c)中给出了另外一个Web服务R和我们所要获取的组合服务Q。现在让我们在自动机S、R的基础上构造一个“组合”自动机Q，并使用PDL对这个“组合”自动机进行编码。设u是由所有原子程序的并构成的程序，即u=?search∪？filter∪！result。由于“组合”自动机中所有的动作都来自于自动机S和R，笔者用命题变量Moved[,s]和Moved[,R]分别来模拟自动机S和R在“组合”自动机中的动作，即：
图2 一组刻画Web服务的自动机的PDL编码
不难看出，基于Web服务行为的组合方法并不检查消息接收和发送的内容，因此，基于Web服务行为的组合方法可能会产生功能上并不符合用户需求的组合服务。假设图1(a)中的Search（查找）消息和图1(b)中的Filter（过滤）消息接收不同的消息参数，即Search消息的参数类型为Publication（出版物），而Filter消息的参数类型为Book（书籍）。如果图1(c)中的Search和Filter消息的参数类型为Newspaper（报纸），那么上述Web服务的组合方法产生的组合服务虽然行为上没有问题，但是功能上并不能满足用户的需要。因为用户需要的组合服务Q查找和过滤的内容是报纸，而不是书籍或泛泛而论的出版物。
3 改进的Web服务组合方法
3.1 基本思路
如上文所述，基于Web服务行为的组合方法无法在功能上满足用户的需求，但是如果能够把消息的参数类型与领域本体中的概念联系起来，并在服务组合时加以考虑，那么就能保证产生的组合服务不仅在行为上能够满足用户的需求，而且在功能上也能够满足用户的需求。
仔细观察图1(a)。不难看出，S[,l]代表了Web服务S接收消息Search之后的状态。如果S[,1]能够反映消息Search所接收的参数类型，那么，就可以保证产生的组合服务不仅在行为上能够满足用户的需求，而且在功能上也能够满足用户的需求。假设图1(a)中的Search消息的参数类型为Publication（出版物），我们只要把图2(a)中的第一个PDL公式
如果不把PDL公式像Publication这样的命题词与领域本体中的概念联系起来的话，这样的改进收益是不明显的。通过把Web服务的参数类型与领域本体中的概念对应起来，就能够利用Ontology在语义层面上进行Web服务组合。可以从Web服务的语义匹配方法中得到一些有用的提示来联系这些命题词与领域本体中的概念。
Web服务组合和Web服务匹配的联系是非常密切的。实际上，如果把服务组合当作一个状态搜索过程的话，那么服务匹配就相当于这个搜索过程之中筛选合适的后继状态的步骤。
3.2 Web服务输入参数的类型匹配
在文献[11]中，Pao阐述了基于DAML-S①的输入、输出参数类型的上下位匹配的思想。文献[12]进一步发掘了参数类型之间的重叠关系，提出了部分匹配的算法；文献[2]针对Web服务数量巨大的特点，在文献[12]的基础上设计了基于矩阵②的高效匹配算法以及前向搜索的服务组合算法。下面简单介绍基于Pao方法的一类服务匹配方法的原理。
从输入、输出的角度来看待Web服务和查询，一个Web服务S能够满足一个查询Q意味着：对于查询Q提供的所有输入，Web服务S必须都能够接受；对于查询Q所要求的所有输出，Web服务S必须至少满足其中之一。根据类型之间是否存在互相包含或相交的关系，我们可以定义一个Web服务S能够满足一个查询Q的程度，他们分别是（按从高到低的顺序）：Exact,Plugln,Subsume和Overlap[2,11,12]。
假设有4个出版物在线查询的Web服务为S[,1]，S[,2]，S[,3]和S[,4]，S[,1]接受所有中文书籍和中文报纸的查询，S[,2]接受所有中文出版物的查询，S[,3]接受所有中文书籍的查询，S[,4]接受所有报纸的查询（参看图3和图4）。如果你期望服务组合产生的Web服务必须能够处理所有中文书籍和中文报纸的查询，那么从输入的角度看，服务S[,1]满足你的查询的程度是Exact；服务S[,2]满足你的查询的程度是Plugln，因为中文书籍和中文报纸都属于中文出版物；服务S[,3]满足你的查询的程度是Subsume，因为你还期望能够进行中文报纸的查询；服务S[,4]满足你的查询的程度是Overlap，因为中文书籍和中文报纸的并集与服务S[,4]所接受的报纸不存在简单的包含与被包含的关系，但你确实可以进行中文报纸的查询。
图3 一个基于输入参数匹配的Web服务矩阵的图示
图4 一个关于出版物的领域本体
根据上面的分析知道，仅仅是在Subsume或Overlap程度上满足匹配的Web服务是无法单独满足确切需要的。为此，它必须与其他Web服务“相加”，并且保证这些相加的Web服务必须能够囊括查询提供的输入。这正是文献[2]中的服务组合算法的基本出发点，该算法通过一个矩阵对服务进行初步的组合以得到一个在Exact或Plugln程度上满足查询的组合Web服务。该矩阵的维度由需要匹配的输入参数的个数决定，矩阵中的元素是一组Web服务，它们在矩阵的各维上的投影是这些Web服务中对应于该维的输入参数所能接受的类型。在上述例子中，需要匹配的输入参数个数只有一个，即查询的出版物，可用图3的坐标轴来示意这个一维矩阵（向量）。由图3可以看出，将S[,3]和S[,4]组合在一起也能够在Plugln程度上满足查询。
3.3 利用Ontology改进Web服务组合方法
Ontology中领域本体的各个概念间的关系可以用一组PDL公式来刻画[13]。例如，图4中关于出版物的领域本体，可以由下面的一组PDL公式来刻画领域中概念的上下位关系：
[u](Book→Publication)；
[u](Newspaper→Publication)；
[u](ChineseBook→Book)；
[u](ChineseNewspaper→Newspaper).
如果还要进一步限定Book和Newspaper是两个不同的概念，还可以用以下公式表示：
通过公式满足性检验器（例如，文献[14]和文献[15])，可以得到，如果图1(c)中的Search和Filter消息的参数类型为ChineseNewspaper（中文报纸），那么这一组PDL公式将无法满足；也就是说，不存在这样的组合服务，它不仅在行为上能够满足用户的需求而且在功能上也能够满足用户的需求，即对中文报纸进行查询和过滤。
从上面这个简单的例子我们可以看出，利用Ontology改进第2.2节中基于Web服务行为的组合方法，不仅能保证产生的组合服务不仅在行为上能够满足用户的需求，而且在功能上也能够满足用户的需求。改进第2.2节中的Web服务组合方法的步骤有：
(1)对领域本体中每一对构成上下位关系的概念C和D，用一个PDL公式[u]C→D表示之；对领域本体中各个概念的其他约束用PDL公式加以刻画；事实上，所有这些用于刻画领域本体的各个概念之间的关系的PDL公式可以由描述领域本体的OWL文件直接转换获得[13]。
(2)对每个Web服务输入消息inputMessage，它的输入参数类型（也即对应的领域概念）为T，保证Web服务接收消息inputMessage之后都具有一个类型为T的对象；即是说，在描述Web服务行为的自动机的PDL编码中，把相应的PDL公式[inputMcssage]…改写为[inputMessage]T∧…。
利用现成的公式满足性检验器（例如文献[14]和文献[15])检验这组PDL公式的可满足性，如果这组PDL公式是可满足的，那么存在不仅在行为上能够满足用户的需求而且在功能上也能够满足用户的需求的组合服务。
4 结语
本文着重讨论了如何利用Ontology改进基于Web服务行为的Web服务组合方法，以产生不仅在行为上能够满足用户的需求而且在功能上也能够满足用户的需求的组合服务。本文讨论的重点放在利用自动机进行Web服务组合的那一类方法，但是本文所讨论的方法同样适应于利用进程代数进行Web服务组合的那一类方法。后续的工作将进一步把本文的方法应用到利用进程代数进行Web服务组合的那一类方法中去。
收稿日期：2006-10-09
收修改稿日期：2006-11-08
注释：
①已演变成为现在的OWL-S。
②作者在原文中使用的术语是table-base，但是这样的说法容易使没有数据库背景的读者产生误会。