基于社会网络的语义Web服务协同

姜 波， 张晓筱

（1.浙江工商大学 计算机与信息工程学院，浙江 杭州 310018；2.浙江大学 计算机科学与技术学院，浙江 杭州 310007）

服务协同是Web服务提供的主要特性，是2个或2个以上的服务通过协同合作进行服务组合，成为一个大粒度的服务来完成一个新的任务。然而，随着Web服务的增多，网络中存在着海量的候选服务，提高服务协同的效率，并从这些海量服务中发现满足用户需要的服务变得愈发关键。

社会网络指将具有相同兴趣爱好、价值观的社会成员通过互动而形成的相对稳定的关系体系，是由许多节点构成的一种社会结构。节点通常指个体或组织，边是指个体或组织之间的联系。在Web服务领域，服务与服务之间相互交互也形成了一个社会网络。该社会网络代表在服务组合环境下发生在用户与服务或者服务与服务之间的所有交互。在一个服务社会网络图中，节点是一个用户，用户可以是服务消费者、服务提供者、领域专家或者服务本身；边表示节点与节点之间的关系。服务社会网络提供了服务结点之间的历史交互行为信息，即具有社会性［1］。结合上述服务协同和社会网络的定义，通过服务协同可以构建一个面向服务的小型社会网络。在该社会网络中，节点用来表示服务，边用来表示服务之间的协同合作关系。在进行服务协同时，社会网络可以根据过往的服务经验，进行服务选择和服务推荐，从而进行更加高效的协同工作。根据用户需求，当前有很多服务并不是完成一个紧耦合的、单一的任务，它需要通过服务协同，即对服务进行选择、整合来协同工作。这就要求服务协同中服务能够“随需应变”，即使得 Web服务能够自动发现、交互、组合。由此，Web服务协同智能化，即服务之间能够自动发现、选择等技术也被关注。

近年来，国内外许多研究机构和学者围绕Web服务组合进行了深入的研究，文献［2］提出并实现了一种基于IO匹配的半自动Web服务组合算法。该算法根据输出优先满足的基准条件，由后往前迭代查找抽象服务，找出满足用户需求的组合模板并保存到模板库中，再结合Web服务组合模板检索算法以快速响应用户查询。

目前，基于社会网络的Web服务组合成为该领域的热点。文献［3］提出了将智能Web服务与社会计算相结合来解决现今Web服务开发和使用过程中出现的设计质量差、开发成本高和不能支持很好的共享等问题，并指出了这些问题的存在让服务共享、服务自动发现、服务重用等变得困难。智能Web服务研究主要是利用人工智能（Artificial Intelligence，简称AI）技术开发智能主体，使服务发现、组合和调停自动化。社会计算为创建社会平台来协同地支持多方面的计算活动和利用AI技术提供了深刻的理解。它们两者的结合解决了上述所提到的关键问题，使用户、社区行为得以更好地理解。

从人工智能关注点上看，已有不少成熟的研究。文献［4］使用有限状态连续时间半马尔可夫决策过程（Semi－Markov Decision Process，简称SMDP）对服务组合进行建模，并给出了服务组合的Q学习优化算法，以获得最优的服务组合策略。从社会网络关注点来看，当前研究主要运用社会网络的特性结合服务组合，进而提出相关的服务组合改进框架。

文献［5］提出了一个服务组合框架（Service Composition Social Network，简称SCSN），该框架基于社会网络的可信（trust）的特性并结合语义服务组合，实现了语义可信服务组合。文献［6］提出了一个服务组合框架（Social Composer，简称SoCo），该框架将社会网络加入到服务组合的过程中，通过对用户社会网络的分析，在用户创建新的服务过程中，为其推荐服务。

本文从社会网络的角度对服务协同进行分析，给出了服务协同与社会网络的联系，同时借鉴文献 ［7］构建一个社会网络。此外，服务选择中服务间的相似度比较是良好服务协同的重要基础，本文提出了一个较新的语义Web服务相似度比较算法，以实现服务更高效的协同。

1 相关概念介绍

1.1 服务协同

服务被认为是一个独立的、松耦合的组件，用户可以根据自身实际需求，选取自己需要的服务进行组合，来完成一个复杂的任务。服务协同则是服务组合过程中2个服务之间涉及的关系之一。本文用实例来说明服务协同的概念。例如，查询杭州明天的天气，需要从互联网上查找My－Location和Weather 2个服务。这是2个功能单一的、小粒度的Web服务，第1个服务实现的是获取所在地的名称，第2个服务则是根据所在地查找明天的天气。只有通过2个服务一起使用，才能满足所要的杭州明天天气的需求。

1.2 语义Web服务相关概念

1.2.1 本体

本体是共享概念模型的明确的形式化规范说明［1］，该定义主要有概念模型、概念共享、明确语义和形式化描述4个方面的含义。概念模型是分析、归纳特定领域内的概念，抽象出客观世界中该领域内的概念得到的概念模型。概念共享，指本体中的概念及其关系是领域内共同认可的知识，反映了该领域内公认的概念集，而不是个人的认知。明确语义需要明确定义领域内概念之间的约束，从而可以明确解释该概念。形式化描述为了使信息可以被计算机“理解”，本体中的概念以及概念间的关系必须被形式化。

领域本体是描述某一具体应用范围内的概念及其关系，如旅游、学校、医药及金融等领域本体概念。

1.2.2 语义 Web服务中的本体

在语义Web服务框架中，本体可以定义为SWS（NP，FP，IP，O）［8］，各个参数定义如下：

（1）SWS代表Web服务的服务名。

（2）NP代表 Web服务的非功能特性，包括服务ID号、服务名、服务类型或者QoS等信息。

（3）FP代表 Web服务的功能特性，包括语法特性、静态语义（消息、操作语义）、服务第三方及动态语义（行为、操作逻辑）等。

（4）IP代表接口特性，可以表示为：Pin∪Pout∪Pprecondition∪Ppostcondition∪Peffect∪…，综合来说，IP是语义Web服务的一个接口特性集合。

（5）O代表本体，并且支持该Web服务。

1.3 服务社会网络

1.3.1 Web服务的局限性

导致Web服务局限性的主要原因有：

（1）对于服务本身，并不知道其用户以及在服务组合过程中与它存在关系的服务。

（2）服务内部的具体实现是不可见的，用户对其使用受到了限制。

（3）在被使用的过程中，只考虑其自身功能和非功能特性，而忽略了外部详细的信息。

社会网络能很好地解决上述Web服务特性引起的一系列问题。在Web服务中加入社会性元素后，服务社会网络记录了服务间的历史交互信息，并且可以预测一个用户或服务感兴趣的其他用户或服务，进而进行服务推荐。

1.3.2 服务社会网络的构建

借鉴文献［7－8］，本文提出了构建一个服务社会网络的步骤。

（1）确定服务社会网络的组件，即节点和边，也就是Web服务和服务之间的交互关系。

（2）服务匹配分析，即通过对2个服务进行功能和非功能特性的比较来确定两者是相似的还是协同合作的。通过前置条件、输入、输出、效果以及服务质量来计算服务相似度并进行分析。

（3）完成社会网络管理的前提条件是选取根节点。选取好根节点后，根据其他节点与根节点间的相似度，把节点从大到小分为强相似度聚类、平均相似度聚类和弱相似度聚类。

（4）初始化边权重评估。2个服务之间边的初始权重为2个服务的相似度，随着社会网络的使用，边的权重自动更新。

（5）导航社会网络。根据服务间3种关系划分，可以有3种度量方式。如服务替代，通过服务所在聚类的特性值计算出服务成本，利用服务成本、服务前置经验及服务非功能特性等来定义服务的选择值。计算出每个服务的选择值，在服务替代发生时，选择值越大的服务被优先考虑。

（6）变化的边权重的评估。根据社会网络中Web服务的3种关系，定义3个不同的更新边权重的公式来更新权值。

2 服务间的交互

服务之间的交互操作包括协同合作（Collab－oration）、替代（Substitution）和竞争（Competition）［1］。

2.1 服务间的关系

服务的协同合作指通过服务选择服务，整合选取的服务进行协同工作来完成一个较大的任务。服务替代指当一个服务失败时，功能及其相似的服务就会替代它。服务竞争指实现相似功能的2个服务间存在竞争，它们在服务选择时具有相同的地位，通过非功能特性来区分。

2.2 基于社会网络的服务协同

从社会网络的角度来考虑服务协同交互关系。若干个服务进行协同完成一个任务的过程可以看成是一个小型的社会网络的应用过程。在该社会网络中，节点是由进行协同交互的服务组成的，边则表示这些服务之间的协同合作关系。这个社会网络记录了每次使用时所有服务间的协同关系，在其他终端用户选择该服务网络中的一个服务进行使用时，则根据历史交互信息，该服务会为用户推荐与其具有协同合作关系的其他服务来方便用户进行选择，提高服务协同的效率。服务选择是服务协同的重要基础，而其关键在于服务的相似度比较。

本文提出了一个基于本体的语义Web服务相似度比较算法，来提高服务匹配效率，进而提高服务选择和协同的效率。

3 基于本体的语义Web服务匹配算法

3.1 概述

结合本体技术的特点，本文提出了一种新的基于本体的语义相似度计算方法。该方法的核心思想是计算基于语义距离的相似度值时引入深度因子和局部密度因子，并综合语义重合度的影响来计算任意2个概念的语义相似程度。

3.2 算法描述

本文基于语义相似度的Web文档聚类算法［9］，并考虑服务功能信息的语义匹配，同时结合本体的概念，以服务中的输入、输出作为主要匹配对象，建立了Web服务语义描述模型。

定义1 Web服务语义描述模型为W＝〈I，O〉，其中，I＝〈I1，I2，…，In〉表示W中n个输入参数的概念矢量，它是Web服务的输入参数相应的本体概念的集合；同样地，O＝〈O1，O2，…，Om〉概念矢量为Web服务W中m个输出参数对应的本体概念的集合。

通过定义语义描述模型，语义服务匹配问题可以抽象为服务请求的语义描述模型W＝〈I，O〉和Web服务库中某服务的语义描述模型W′＝〈I′，O′〉之间的匹配，通过综合计算输入、输出概念矢量I和I′及O和O′之间的相似程度可以实现匹配。

在互联网中，Web服务的提供者和请求者对同一类型的服务往往有不同的理解和需要，反映在Web服务功能上是请求服务和广告服务的输入和输出概念，矢量在维度和顺序上都可能不一致，所以定义同一领域本体库中任意2个概念矢量匹配是形式化定义Web服务匹配的前提。

定义2 同一领域本体库中任意2个概念的相似度计算函数为Sim（C1，C2），其中，C1，C2表示领域本体库中的任意2个概念；Sim（C1，C2）∈［0，1］，其值越大，2个概念越相似。

定义3 设A＝（A1，A2，…，Am），B＝（B1，B2，…，Bm），这2个概念矢量的相关矩阵可以表示为：

上述一系列定义首先把语义Web服务抽象为关于输入、输出参数的语义描述模型，然后基于概念矢量之间的语义相似度值来计算模型之间的匹配，概念矢量之间的匹配通过定义3计算，矢量元素的相似度可以使用定义2计算得到。

3.2.1 语义距离相似度

在信息匹配研究中，概念间的语义距离是计算2个概念语义相似度的重要因素，两者成反比关系。语义距离指在同一个领域本体库中2个概念之间存在的所有关系链中最短的链的长度。通过对领域本体层次结构的分析可以发现，深度越深的2个概念往往越相似。同样，如果某一局部范围内，概念分类越细，那么其中的2个概念就越相似。因此，深度以及局部密度对语义相似度的影响将被引入语义距离的计算。

继续优化移民户收入结构，加速农村劳动力转移步伐，由出台的劳务经济补偿机制带动大量劳务经济兴起，不断带动劳务输出，通过政策引导鼓励农民外出务工，不断利用扶贫培训政策，大力提高农村劳动力素质和专业技能，大力完善劳务派遣制度。

定义4 概念C对应高度权重因子的计算公式为：

可得同一领域本体库中任意2个概念矢量相似度的计算公式为：

本文引入本体树的同支和异支概念计算局部密度因子，如图1所示。

图1 同支和异支概念图

在本体树中，如果概念A是B的祖先或者B是A的祖先，即A、B在同一分支上，称它们为同支概念；如果A和B不在同一分支上，或A和B的最近公共节点不是A或B，则A和B为异支概念。A和B的最近公共父节点R指它们所有共同父节点中深度最深的节点，记为LN（A，B）。根据A、B在本体树中关系的不同，有如下定义。

定义5 概念的局部密度因子 Weight（density），其计算公式为：

（3）式为当A、B为同支概念时，并假设A为B的祖先节点；其中NUM（A→B）指A与B之间的节点数，如图1为5个。（4）式为当A，B为异支概念时，先求出R＝LN（A，B），假设Dep（B）＞Dep（A）的情况下定义的；其中NUM（R→B）指R与B之间的节点数，如图1为9个。

求局部密度因子的实现算法及其对应的流程如图2所示。

定义Weighti为从C1到C2的最短路径上的权值，且它的值与概念的深度因子和局部密度因子密切相关。

定义7 2个概念间的语义距离，其公式为：

定义8 语义距离对应的相似度，其公式为：

图2 局部密度因子算法流程

3.2.2 语义重合度

在计算语义距离时，本文考虑了节点深度以及局部密度的影响，并通过定义8计算基于语义距离的语义相似度。计算综合语义相似度还要考虑语义重合度的影响，语义重合度是2个本体概念的上位概念的相同程度，语义重合度的数值越大，这2个概念的语义相似度也越大。

定义9 语义重合度对应的相似度，其计算公式为：

其中，P（C1）为概念C1的父节点数；P（C1）∩P（C2）为概念C1和概念C2的公共的父节点个数；max（P（C1），P（C2））为概念C1或概念C2的父节点数中的较大者。

定义10 综合语义相似度，其计算公式为：

其中，α为调节因子。调节因子可以根据不同的应用和要求进行调整。

由任意2个概念的相似度Sim（C1，C2）和定义3可以得出任意2个概念矢量相似度，然后定义Web服务输入、输出相似度计算函数。

定义11 Web服务输入、输出相似度计算函数为：

其中，〈I，O〉和〈I′，O′〉分别为服务W和W′的输入、输出；0.5＜γ＜1，因为输出对于用户更重要，而且用户对于输出具有较大的控制权。

本文算法的整个流程如图3所示。

图3 本文算法流程

3.3 实验与结果分析

除了使用基于关键字匹配方法外，本系统还采用3种方法计算基于语义距离的语义相似度，因为基于同一领域本体库的服务集，对于同一个语义服务请求，3种方法计算服务集中的同一个服务与服务请求的语义重合度对语义相似度的影响是相同的。如果只在改进的方法中加入语义重合度的影响，则结果可能不是很客观，所以实验中先用3种不同的基于语义距离的语义相似度计算方法（其中包括本文的算法）进行计算，然后在该算法中引入语义重合度的影响。

3种基于语义距离的语义相似度算法为：

算法1 在定义8的基础上，令Weighti＝1。

算法2 使用GCSM语义距离计算方法［10］，即

其中，LCA（C1，C2）为2节点的最近公共父节点。

算法3 基于语义距离的语义相似度算法。

这3种算法中语义相似度的计算都是基于语义相似度计算公式的，而 Web服务输入、输出相似度计算函数使用定义11中的公式，实验中取γ＝0.6，即输出参数的语义相似度权重为0.6，而输入参数相似度的权重为0.4；取α＝0.7，语义重合度对综合语义相似度的影响的权重为0.3，而基于语义距离的语义相似度的权重为0.7。

在本实验中，随机产生了950个Web服务的语义描述，并在标注框架的指导下，人工标注了50个Web服务，共产生1 000个已发布的 Web服务语义描述，人工描述10个Web服务请求。对每个产生的Web服务请求，实验用上述3种计算方法计算其与每个已发布Web服务语义描述之间基于语义距离的语义相似度，最后对每种方法的返回结果按照相似度值进行排序，匹配系统的界面如图4所示。

图4 语义Web服务匹配系统界面

实验对10个语义Web服务请求分别在测试集中进行匹配，算法1、算法2和算法3在这10个服务请求下，平均查准率和平均查全率之间的关系如图5所示。

图5 3个算法查全率和查准率间的关系

从图5可以看出，算法1在查全率和查准率方面比算法2和算法3差，因为算法1在计算基于距离的语义相似度时权重只是简单地设为1。而算法3在同样的查全率下查准率高于算法2，这是因为算法3在计算基于语义距离的语义相似度时，不仅考虑了深度权重因子的影响，而且还考虑了局部密度权重因子的影响，而算法2只考虑了最近公共父节点的深度以及节点深度的影响，从而影响了算法2的查全率和查准率。

实验结果表明加入语义重合度的影响后，能更好地反映服务匹配程度。本文提出的语义相似度匹配算法在查全率和查准率方面都有所提高。

4 结束语

当前Web服务领域的热点是服务组合，而在服务组合中，服务最重要的关系是服务协同，因此进行服务发现、选择和匹配是服务协同的重点。服务协同的自动化需要智能，语义Web服务的出现解决了该问题，本文对基于社会网络的Web服务协同进行研究，构建了一个服务社交网络使得服务协同能更好地利用服务既往的社交关系，并提出了一个新的语义Web服务匹配算法，该算法在计算服务语义距离时兼顾服务本体深度及局部密度对语义相似度的影响，从而提高了服务查全率和查准率，更好地实现了服务的有效协同。

［1］Maamar Z，Hacid H，Huhns M N.Why web services need social networks［J］.IEEE Computer Science，2011，15（2）：90－94.

［2］杨放春，许广宇.Web服务组合研究与实现［D］.北京：北京邮电大学，2009.

［3］AAAI Spring Symposia at Stanford University.Intelligent Web Services Meet Social Computing［EB／OL］.［2012－03－26］.http：／／vitvar.com／events／aaai－ss12，2012.

［4］柴雪霞，马学森，周 雷，等.基于SMDP模型的 Web服务组合优化方法［J］.合肥工业大学学报：自然科学版，2011，34（10）：1496－1500.

［5］Xie Xiaoqin，Du Bailing，Zhang Zhiqiang.Semantic service composition based on social network［EB／OL］.［2008－04－21］.http：／／keg.cs.tsinghua.edu.cn／SWSM2008／short%20papers／submission＿17.pdf.

［6］Maaradji A，Hacid H，Daigremont J，et al.Towards a social network based approach for services composion［C］／／Proceedings of the 2010IEEE International Conference on Communications（ICC′2010），Cape Town，2010：1－5.

［7］Maamar Z，Faci N，Badr Y，et al.Using social networkds for web service discovery［J］.IEEE Computer Science，2011，15（4）：48－55.

［8］Liu Min，Shen Weiming，Yan Junwei.An weighted ontologybased semantic similarity algorithm for web service［J］.Expert System with Application，2009，36（10）：12480－12490.

［9］李 毅，王 浩，杨 静.基于语义相似度的 Web文档聚类算法［J］.合肥工业大学学报：自然科学版，2009，32（12）：1846－1850.

［10］廉晨思，郑 诚.基于综合本体相似度计算的WEB服务发

现算法［J］.计算机应用与软件，2011，28（2）：88－89.