覃事刚，姜 慧，黄波英

(湖南电气职业技术学院 科技处, 湘潭 411101)

Web服务关联语义索引WSSI系统的设计与实现*

覃事刚，姜 慧，黄波英

(湖南电气职业技术学院 科技处, 湘潭 411101)

为了解决Web服务间自适应调用关联的问题，运用形式概念分析FCA的相关知识，设计了一种Web服务关联语议索引WSSI系统.该系统对任意给定的Web服务集合掘挖服务间隐含的逻辑关系，构造Web服务关联语义索引，为组合服务发现提供可靠的接口，并进行了相关的实验分析.实 验 证 明 了 该系统的有效性. 关键词：Web服务；隐式关联；WSSI

0 引 言

语义Web服务发现是Web服务的一个重要领域，其热点主要集中在基于语义的Web服务发现，以基于DAML-S语言的语义匹配[1]、基于过程本体论的服务发现方法[2]、基于数学特定领域的Web服务匹配算法[3]、多主体服务环境MAGE(Multi-Agent-Environment)[4]等为主要代表，其服务发现过程都是客户根据需求在服务注册机构中心单个的查找，然后组合成客户需求的服务流.很明显，这些方法都是发现单个的服务，在现实生活中，服务之间是可能存在某些隐含的关联，建立基于这种关联的Web服务语义索引(WSSI: Web Service-associated Semantics Index)，实现客户的组合服务请求的多服务组合发现，对提高服务发现效率、减轻网络负载具有重要的意义.本文在现有的研究基础上开发出了一种Web服务关联语义索引(WSSI)系统，具有Web服务发现、组合及组合发现等功能.

1 WSSI系统的理论基础

1.1 Web服务间的隐式逻辑关系是存在的

现实中，很多服务之间的关系并不明显然，但在特定的背景下，这些服务是很有可能存在某种关联的，例如图1所示，假设酒店、火车站、超市、电影院、旅行社等商业机构之间存在一定的合作关系，那么消费者在其中某一个机构得到服务的同时，也可以享受到其他机构提供的服务.可以看出，Web服务之间的逻辑关系虽然不明显，但确实是存在的，需要通一定的方法抽象成能被计算机识别的Web服务关联图(见图2).

图1 现实生活中的服务关系

图2 服务隐式关系的抽象结构

1.2 Web服务形式背景下的概念格

根据形式概念分析FCA[5]的相关知识，在给定的背景下确定该背景的概念格有很多方法.文献[6]提出了Web服务形式背景WsK(Gws,Msg, K)下构造出相应该的概念格的方法，该方法给出了Web服务形式背景WsK(Gws,Msg, K)的相关知识，该形式背景只表示了消息与Web服务之间的关系，但是不能清楚的反应出输入消息、Web服务和返回消息之间的关系.因此，就把Web服务形式背景WsK(Gws,Msg, K)分解再定义成两个形式背景：input-WsK和output-WsK.再针对这两个形式背景：input-WsK和output-WsK分别构造输入消息服务格input-WsK和输出消息服务格output-WsK.由此可见，要确定概念格寻找形式概念是关键，而寻找形式概念是可以在形式背景的背景图Gk中查找所有的最大完全二部图来实现的.

定义1二分图G=(A,B,E)，有km1,n1(A1,B1) ∈G和km2,n2(A2,B2) ∈G，我们定义km1,n1(km2,n2=(A1,B1) ( (A2,B2)=(A1∪A2,B1∩B2)=km3,n3(A3,B3) (对象扩展运算，其中km3,n3∈G且满足f(A3)=B3)km1,n1(km2,n2=(A1,B1) ( (A2,B2)=(A1,∩A2,B1∪B2)=km3,n3(A3,B3)(属性扩展运算，其中km3,n3∈G且满足k(B3)=A3) .

对象扩展运算和属性扩展运算是我们在给定的二分图G(A,B,E)中寻找最大完全二分图的基本操作.

定义2 如果集合S是由其子集Y按照某种规则生成的，我们称Y是S的生成集，并且称Y中的元素为生成元，记为e.

我们要讨论的集合S是二分图G中所有完全二分图组成的集合，运算规则是对象扩展运算或属性扩展运算，生成集Y中的元素是也是完全二分图，但是不是最大完全二分图，其集合中的元素e可以由二分图G中其中的某顶点集中的顶点确定，在构造生成集时，可根据二分图G的不同顶点集构造两个不同的生成集Y，所以S的生成集不是唯一的.

由二分图GYA,B,E)构造格L的过程：输入二分图G,初始化生成集Y；对Y进行扩展为新的集合S；对S进行优化，转换对应的形式概念集合K；对K的概念元素按外延或内涵排序构造格，并填写概念表;输出结果.

1.3 WSSI的构建过程

对给定的一个Web服务，先只考虑输入消息、服务名和输出消息，描述为WS(in,ws,out)，其中ws为服务名称，in ={ msg1, msg2,…,msgm}是该Web服务输入消息的集合,out ={msg1, msg2,…,msgk}表示返回消息集合，它是一个三元组，对给定的Web服务集U={WS1, WS2, WS3……，WSn}，当n=5时可以用如图3所示.

图3 Web服务与消息的分配图

在图3中，第一层代表输入消息，中间代表Web服务名，第三层代表输出消息，输入消息层与服务层之间的边表示多个服务名具有相同的多个输入消息，同样，输出消息层与服务层之间的边表示多个服务名具有相同的多个输入消息，调用服务层的Web服则需要输入第一层的输入消息，服务调用完成后返回第三层的输出消息.现在，我们盖住图的下半部分即输出消息集合，看图的上半部分就成了一个典型的二分图；同样，我们盖住图的上半部分即输出消息集合，看图的下半部分也是一个典型的二分图，描述了服务集合中服务与输入消息之间的关系.如果事物对象为Web服务，事物属性为输入/输出消息，则直观表述了Web服务与输入/输出消息之间的联系，具有以下优点：用可视化的二元关系描述对象(Web服务集)与属性(输入/输出消息集)之间的关系，方便揭示Web服务间的潜在语义联系. 下面，在两个二元关系中就可以对具有共同输入消息属性的Web服务对象分组，对具有共同输出消息属性的Web服务对象分组，如果存在输出消息集合等于输入消息集合的具有共同输出消息属性的Web服务分组oW和具有共同输入消息属性的Web服务分组iW,则oW与iW之间存在关联关系，其对应的Web服务之间的隐含关系就被挖掘出来，Web服务关联图的构建步骤如下：①将给定的Web服务集W分解为两个二元组：Wi和Wo.其中, Wi表示Web服务集与输入消息之间的二元关系， Wo表示Web服务集与输出消息之间的二元关系；②对Wi进行分组(条件: Web服务对象具有共同输入消息属性)；③对Wo进行分组(条件:具有共同输出消息属性的Web服务对象)；④通过Wi×Wo构造Web服务关联图Gws；⑤对Gws进行约简，并输出约简后的Gws.

2 WSSI系统的设计与实现

Web服务关联语义索引(WSSI)系统(如图4所示)由两大部分组成：WS Collector和语义索引系统.WS Collector的主要作用是从互联网上搜集尽可能多的Web服务，并注册到UDDI注册中心，为语义索引系统构建Web服务关联语义索引提供丰富的Web服务，其核心为基于聚焦搜索的Web服务搜索引擎.语义索引系统的功能是对已在UDDI注册中心注册的Web服务进行形概念分析，挖掘出Web服务之间的隐含关系，并以相关的概念格作为理论工具，构建Web服务关联语义索引(WSSI)，为组合服务的发现提供可靠的接口.

2.1 UDDI注册中心数据结构的扩展

UDDI注册中心是基于UDDI协议实现的，主要提供Web接口和API接口.本文在UDDI的基础上增加三个新的数据结构：TInput_WsL、TOutput_WsL和TWSSI?(TInput_WsL存储输入消息服务格Input_WsL，TOutput_WsL存储输入消息服务格Output_WsL，TWSSI?存储Web服务关联语义索引WSSI)，TInput_WsL、TOutput_WsL和TWSSI?在UDDI注册中心的数据表分别如表1、表2和表3所示.

图4 Web服务关联语义索引(WSSI)的体系结构图

列名数据类型不能为空默认值说明Input-WsC＿KeyVARCHAR(45)√PrimarykeyExtensiontextnullIntensiontextnull

表2 TOutput_WsL表

表3 TWSSI表

表3 TWSSI表

列名数据类型不能为空默认值说明Input-WsC＿KeyVARCHAR(45)√ReferencekeyfromTInput＿WsLOutput-WsC＿KeyVARCHAR(45)√ReferencekeyfromTOutput＿WsLSem＿RelationInt(4)√0Senmanticrelationvalue

其中表1中的Input-WsC_Key和表2的Output-WsC_Key为UDDI注册中心分配给Input-WsC和Out-WsC的唯一ID号，Extension和Intension字段为Web服务或消息的集合.表3中的Sem_Relation的值表示两个Input-WsC和Out-WsC之间的语义关系.

2.2 WSSI构建算法及分析

根据前面的知识可得，在已知输入消息服务格和返回消息服务格的前提下，构建Web服务关联语义索引(WSSI)的过程实质就是在与输入消息服务格和返回消息服务格相对应的两个本体间寻找映射集.第一步需要实现概念格的构造(见图5),第二步在概念格的基础上构建索引(见图6).

算法1的核心变成了在二分图查找所有的最大完全二分图.假设以二分图G(A,B,E)中的顶点集A构造的生成集Y中的元素个数为n(或是|A|=n)，如果生成集Y中的元素ei(Ai,Bi)，其中|Y|=|A|，满足，|Ai|=1，|Bi|=|B|-1,即任意的两个ei，有且只有|Bi|-1个元素b∈ Bi相同.如果把某个e0(A0,B0)且|A0|=1扩展成e’(A’,B’)且|A’|=|A|-1需要执行f(n-1)时间，循环对每个ei进行扩展的时间和为f(n(n-1)),此时的时间复杂度为：O(f(n(n-))=O(n2).

算法2为 Web服务关联语义索引构建算法,假设|A|=n,|B|=m,则计算一次ai∈A和bj∈B的语义关系Rij的时间为1，则该算法的复杂度为O(n*m).

图5 概念格构造算法

图6 Web服务关联语义索引构建算法

3 实验分析

WSSI的实验分析将采用与基于Web服务图测试系统(WSG Test Platform)[7]相同的实验环境和实验数据，并通过对相同的服务请求在WSSI和WSG中从服务组合效率和服务发现响应效率两方面进行比较.

硬件环境：CPU为 奔腾4 3.0GHz,内存为512MB，Windows XP操作系统.

实验数据：从UDDI注册中心随机抽取9个Web服务数据集，每个服务集总数分别为：300、600、900、1200、1600、2000、2400、2700、3000，在每个服务集上数据集上随机选择30个服务组成的服务流E-workflow[8]请求.实验结果如图7所示.

1)WSSI与WSG的构建效率比较:

从图7(a)可以看出， 在服务总数比较小的两种逻辑结构的构建时间几乎差不多，但随着服务总数的增多，WSIRG的构建时间明显小于WSG的时间,体现了新方法的优势.

2)服务发现时间的比较:

从图7(b)可看出，随着服务集的规模不断扩大，基于WSSI的服务发现的耗费时间与WSG发现的耗费时间差值越来越大.

从结果可以看出，WSSI存在以下优势：WSSI与WSG的构建方法相比，WSSI的顶点不是单个的Web服务，而是同类的Web服务集，其构造过程转换为对Web服务按给定条件分类划分为不同的顶点集，理论上构建WSSI的算法复杂度为O(n4)，但实验证明在实际情况中几乎不可能达到或是接近最坏情况.反观其WSG的顶点数远大于WSSI，因此，基于WSSI的服务发现的耗费时间，随着服务数量越多，速度明显提高.

图7 实验结果比较

4 总结

WSSI是一种Web服务间存在的某种语义关联关系的抽象结构，通过对Web服务的语义关联关系的深入挖掘，开发了一套Web服务关联语义索引 (WSSI)系统，设计了形式背景下的概念格的构造算法和基于本体的WSSI构建算法,并与基于断言关系的WSG进行比较实验.结果证明WSSI明显优势于WSG，更加有利于提高服务发现效率.

[1] M. Paolucci, J.Soudry, N.Srinivasan, K. Sycara. A Broker for OWL-S Web Services[J]. Multiagent Systems, Artificial Societies, and Simulated Organizations, Springer,2004, 13:79-98.

[2] Mark Klein, Abraham Bernstein.Searching for Services on the semantic Web Using Process Ontologies[C].In:Proceedings of the International Semantic Web Working Symposium(SWWS).Amsterdam:IOS Press,2001,159-172.

[3] O Caprotti，M Dewar，D Turi.Mathematical Service Matching Using Description Logic and OWL[C]. Mathematical Knowledge Management, Third International Conference, Mkm, Bialowieza, Poland, September,2004, 3119:73-87.

[4] 史忠植,蒋运承，等．基于描述逻辑的主体服务匹配[J].计算机学报， 2004, 27(5)：625-635.

[5] 甘特尔,威 尔,马 垣，等. 形式概念分析[M]. 北京：科学出版社，2007.[6] 覃事刚,刘建勋,秦祖泽.Web服务关联图构造方法[J]. 计算机集成制造系统,2011,(8):1670-1676.

[7] 巢 炼．基于图理论的Web服务发现方法研究[D]．湖南：湘潭大学硕士学位论文,2007.

[8] J. Cardoso and A. Sheth. Semantic E-Workflow Composition[J]. Journal of Intelligent Information Systems，2003，21(3):191-225.

Design and Implementation of Web Service-associated Semantics Index System

QIN Shi-gang， JIANG Hui， HUANG Bo-ying

(Department of Science and Technology, Hunan Electrical College of Technology, Xiangtan, 411101， China)

This paper proposes a novel WSSI system to construct Web Services-associated Semantics Index from the perspective of deep mining of the hidden relationship between mutual Web Services. In the system, by using the theory of Formal Concept Analysis, it defines the system framework and basic functions, designs some key problem’s solving algorithms and provides reliable interface for composite service discovery. Related experiments are done in the end and the simulation results show the effectiveness.

Web Services; implicit link; WSSI

2016-07-13

湖南省科技计划项目(2014GK3004)；湖南省教育厅科研项目(13C160).

覃事刚(1979-)，男，硕士，讲师，研究方向：服务计算与云计算研究.

TP393

A

1671-119X(2016)04-0046-05