使用倒排索引优化服务发现

《使用倒排索引优化服务发现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1使用倒排索引优化面向组合的服务发现Web服务是一种自包含、自描述、模块化的新应用，可以通过网络发布、定位和调用[1]。近年来，随着Web服务相关标准的持续完善和支持Web服务的软件平台的不断成熟，Web服务在商业、金融和旅游等领域得到了广泛应用。随之而来的，是发布在网络上的服务呈现出爆炸性增长，这也使得如何以快速、准确和高效的方式发现目标服务成为一个迫切需要解决的问题。基于UDDI[2]的服务发现机制使用关键字匹配技术，往往导致服务发现精度不够甚至失败，因此，近年来，国内外研究学者围绕基于语义的服务发现展开了广泛的研究。Paolucci等人[3]提出了第一个通过匹配

2、服务档案的基于语义的服务发现算法。Bansal和Vidal[4]提出了第一个通过分析服务模型的服务发现算法。由于语义的引入，本体的推理能力在服务发现中得到了灵活应用。史忠植等人[5]提出基于描述逻辑的主体服务匹配算法，马应龙等人[6]提出使用分布式描述逻辑扩展描述异构本体并使用优先分布式知识库描述本体的进化和更新。这些服务匹配策略通常是通过顺序扫描服务库中所有注册服务的方式来实现的，这种方法也被称为顺序查找。使用这样的方法之前，服务库中的服务信息未做任何形式的预处理。当执行服务查询时，每个注册服务都与服务请求进行匹配比较。这种方法相对直观、容易实现，但是当服务库中的服

3、务数量达到一定数量级别的时候，这种查找方法的效率就成为受制约的瓶颈问题。另一方面，大部分的服务匹配策略只检查单个服务是否能满足服务请求。例如，假设服务库中仅有一个扫描服务和一个打印服务，而服务请求需要一个复印服务。许多现有的服务匹配算法将返回失败结果，因为服务库中没有服务能独立地满足该请求。然而，我们可以先通过扫描服务将纸质文件转化为电子文件，然后通过打印服务再将得到的电子文件转化为纸质文件，从而实现了复印服务的功能。对于在服务发现中融入服务组合，已有一些研究工作有所涉及。AntonioBrogi等人[7]提出了一个面向组合的服务发现算法。该算法首先为服务库中的所有原

4、子服务建立关系图，然后对于每个请求，算法通过分析该图来决定是否能通过组合服务来满足该请求。该方法的潜在缺点在于其算法的高度复杂性，因为文中给出的仅有两个服务的服务库的构造和分析已经十分复杂，并且没有实验数据能表明该方法的效率。L.Aversano等人[8]也提出了一个通过组合来优化现有服务发现的算法。该算法使用后向链的思想来验证是否能通过组合服务来匹配请求。它以效率为代价，提高了发现可用服务的可能性，因为它需要经常顺序扫描服务库中的所有服务。XiaoqinXie等人[9]提出了面向组合、基于与或图的服务搜索方法。该方法通过启发函数降低搜索空间，但是它还需要进一步的实验

5、评估来验证它的适应性和可行性。基于以上分析，本文引入倒排索引的概念，一种面向单词的索引机制，为所有注册服务的输出建立倒排索引。对于所有输出，都建立一个服务列表，来记录在服务库中所有能产生该输出的服务。倒排索引可以快速地定位候选服务。基于这种机制，提出一个面向组合的服务匹配算法。该算法由原子级服务发现和组合级服务发现组成。原子级服务发现检查服务库中是否存在原子服务能独立地满足服务请求，而组合级服务发现，作为原子级发现的补充，检查是否能即时组合原子服务来满足服务请求。根据OWL-S[10]规范，Web服务被划分为原子和合成服务。原子服务对应于通过一次交互完成的服务，而合成

6、服务对应于需要多个动作完成的服务。由于原子服务和合成服务的不同特性和不同侧重，我们将针对原子服务和针对合成服务的发现策略区分开来。本文的服务发现策略针对于原子服务。余下部分组织如下：第一节介绍如何为服务库建立倒排索引。第二节提出面向组合的服务发现算法。第三节是仿真实验和结果分析。最后是总结和展望。1建立倒排索引对于原子服务库，我们可以把1服务看成一个原子的、不可分解的过程，也就是通常所说的黑盒视图[3]。在这种视角下，一个服务等同于一个操作，所有的内部过程被屏蔽，只有输入/输出接口对外暴露。因此，我们在做服务匹配时，可以着重关注OWL-S服务档案的接口描述部分。相应地

7、，服务和服务请求可以定义成如下所示：定义1.服务是对服务所支持的一个操作的抽象描述，可以表示为一个三元组，其中：（1）N表示服务名称，作为服务的唯一标识。（2）是服务的输入集合，其中每个输入都用本体进行标注。（3）是服务的输出集合，其中每个输出都用本体进行标注。定义2.服务请求是对接口需求的抽象描述，可以表示为二元组，其中：（1）是可以提供的输入集合，其中每个输入都用本体进行标注。（2）是需要的输出集合，其中每个输出都用本体进行标注。传统的服务匹配策略是，通过顺序扫描所有注册服务，每个服务都与服务请求进行匹配比较。而判定一个服务是否能满足服务请求，算