吴保磊  夏士雄

（中国矿业大学 计算机科学与技术学院，江苏 徐州 221116）

 

    摘  要　在语义Web服务组合涉及异构环境时，根据用户需求发现所需要的Web服务是一项关键的技术。本文以煤矿信息查询系统为应用背景，基于二分图最佳匹配算法提出了一种Web服务分级发现算法，通过计算异构环境中不同Web服务间的参数来完成不同服务的语义匹配，并讨论了分级发现算法的运行实例。

    关键词　异构环境；语义Web；服务发现

 

    Web服务发现是Web服务系统架构中的一个重要组成部分^[1]，是Web服务发展的关键技术。所谓Web服务发现，指的是用户以某种方式在不同类型的Web服务中找到其需要的服务，以执行Web服务请求^[2]。现有的Web服务发现方法分为句法级服务发现和语义级服务发现两大类^[3]。句法级服务发现通过关键字匹配进行服务搜索。这种发现机制着重对服务的接口和实现细节进行定义，不支持对服务功能和行为的语义描述，因此实现起来较为简单，但查全率和查准率较低。语义级服务发现有效利用语义信息和领域本体，实现Web服务的自动语义匹配和搜索，具有查准率较高的特点。当前的语义Web服务研究大多基于单本体或单一数据环境。但在一个领域中，不同的领域专家对于同一事物可能采用不同的属于和方法，因此就会产生多个领域本体。另外就是当服务发现涉及到不同领域时，服务的请求和发布有可能采用不同的方式来描述的，此时就要考虑异构环境下语义信息的匹配问题。

    本文在国家自然科学基金项目《煤矿安全监测数据解析整合模型研究及应用》支持下，针对异构环境下的语义Web服务发现问题，在煤矿（矿山）信息查询系统中采用基于二分图匹配的分级发现策略，利用领域本体解决异构数据的综合利用与共享，并通过实验表明了本文方法的有效性。

    本体是关于领域内概念的明确的共享形式化说明^[4]。将本体定义为元组O=（C，A，RT，R，H），其中：

    （1）C 表示领域内的概念集合，c∈C 表示其中一个概念；每个领域本体具有一个根概念ROOT。

    （2）A表示概念属性集合，概念c∈C 的属性集合记为A_c={a_ci|i=1，…，|A_c|}，|A_c| 表示概念属性数目。

    （3）H 表示概念层次集合，H⊆C×C，（c_i，c_j）∈H表示c_i 为c_j 的子概念，H 为有向无环图。

    （4）RT 为语义关系类型集合，RT=RT_d∪RT_u，RT_d 为预定义关系类型集合，RT_d={SameAs，Disjo int With，Equivalent}，RT_u 为用户定义关系类型集合。

    （5）R 表示概念之间的非层次关系集合，每个关系r∈R表示为r={c_i，c_j，rt}，其中c_i，c_j∈C，rt∈RT，表示概念c_i、c_j 之间存在rt 关系。

    一个语义Web服务模型可定义为元组SWD=<SN，SD，IS，OS，QoS，O_d>，其中：

    （1）SN为语义Web服务的名称。

    （2）SD={sd₁，sd₂，…，sd_n}为语义Web服务的描述，sd_n为概念的集合。

    （3）IS={is₁，is₂，…，is_n}为语义Web服务的输入，is_n代表服务的各输入参数。

    （4）OS=<os₁，os₂，…，os_n>为语义Web服务的输出，os_n代表服务的各输出参数。

    （5）QoS =<Time，Cost，Reliability>为服务质量的非功能描述，包括调用服务所需的时间、费用、可靠性等。

    （6）O_d 为语义Web服务提供方的领域本体，语义Web服务模型中的概念均来源于该本体。

此外，定义语义Web服务请求为元组SWR=<RN，RD，IR，OR，RQoS，O_r>，各变量含义与语义Web服务描述框架相似。

    相关度指概念之间相关的程度。相关性与相似性相比较，相似意味着词汇所表达的概念在某些特征方面有重合，而相关性则表明概念间具有相似性，但概念所表达的一些特征不直接重合。因此，相似只是相关的一个特殊方面。例如提升机与钢丝绳相关但不相似，而提升机与罐笼绞车在功能上相似但不紧密相关。参考文献[5]，本文采用一个在[0，1]区间取值的实数来表示度量的结果，该实数的取值0（1）表示两个概念完全不相关。具体方法采用Hirst-St-Onge语义相关度算法^[6，7]，其基本思想是：当两个词在WordNet同义词集（synset）中有一条较短的路径相连时，在语义上就具有较大的相关度。当此路径不存在时，RelHS（w1，w2）=0。计算公式为：

    RelHS（w₁，w₂）=c-len（w₁，w₂）-k*turns（w₁，w₂）                   

（1）

    其中，c和k是两个常参数，turns（w₁，w₂）代表在synset中的路径转向次数，len（w₁，w₂）是路径长度。

    语义相似度是指概念间自身语义的相似程度，即考虑概念的含义来计算相似度，语义相关度和语义相似度成正比关系。本文采用WordNet语义词典来计算概念的语义相似度。其基本思想是：两个单词通过上位关系连接的距离越近，他们的相似度就越大；反之他们的相似度越小。如果它们在有限上位层次中没有共同的父结点，则Sim_d（w1，w2）=0。参考文献[8]，给出语义相似度计算公式为：

    Sim_d（s₁，s₂）=2*logP（s）/（logP（s₁）+ logP（s₂））                     

（2）

    其中，p（s）=count（s）/total表示在WordNet中词义结点s及其子结点所包含的单词个数在整个词典中所占的比例，total是WordNet的单词总数。另外w₁∈s₁，w₂∈s₂，表示单词w₁和w₂分别位于结点s₁和s₂中，结点s是s₁和s₂的公共祖先结点。令s（w₁）={s_1i|i=1，2，…，m}和s（w₂） ={s_1j|j=1，2，…，n}分别表示单词w₁和w₂的所有词义，则两个单词的相似度定义为它们之间语义相似度的最大值：

Sim_d（w1，w2）=max（Sim_d（s_1i，s_2j）），s_1i∈s（w₁），s_2j∈s（w₂）                                 （3）

    分级发现算法的基本思想是：根据前面概念相关度的定义，利用式（1）对服务请求SWR中的RN与候选语义Web服务SWD中的SN进行概念相关度计算，筛选掉与服务请求无关的Web服务。如果相关度为0，则不再进行相似度的计算，否则利用式（3）对SWR与SWD进行SD与RD的语义相似度计算，并采用基于二分图的输入输出参数匹配算法IOMatch来衡量SWR与SWD的相似度；再利用QoS和RQoS对发现的结果进行排序，将最优结果排在最前。

    SWR与SWD 的输入输出参数匹配的实质是：SWR 与SWD的or_n与os_m之间进行匹配计算；SWD与SWR 的is_n与ir_m（n≤m）之间进行匹配计算。从而保证SWD 能尽可能满足SWR的所有要求，而SWR 也能提供SWD 所需的输入。

    输入输出参数匹配问题可以转化为二分图的最佳匹配问题，即求一个集合X={x₁，x₂，…，x_n}到集合Y={y₁，y₂，…，y_m}（n≤m）的二分匹配，使得和式∑sim（x，y）取得最大值。sim（x，y）是任一属于X的本体概念x与任一属于Y的本体概念y之间的语义相似度，满足0≤sim（x，y）≤1。但因二分图的最佳匹配问题是针对|X|=|Y|（即n=m）的匹配，无法直接应用于n≤m的情况，因此需将二分图最佳匹配的定义进行扩充，即给定一个带权二分图G=（X，Y，E）和G的一个匹配M（本体概念集合X、Y表示图的点，E为∀x∈X、∀y∈Y亮点<x，y>所连的边集，并给该边一个权重W_xy=sim（x，y）），二分图满足条件|X|≤|Y|，M是G的一个最佳扩展匹配，当且仅当：①若|X|=|Y|，M是G的最佳匹配；②若|X|＜|Y|，M是覆盖集合X中的所有节点，且权和最大的匹配。此定义可通过反证法证明，此处限于篇幅，证明略。

    Kuhn-Munkres（KM）算法^[9]是一个经典的用于求解二分图的最佳匹配的高效算法，它通过求解二分图的等价子图的完备匹配来获得二分图的最佳匹配，其正确性源于定理：二分图的等价子图的完备匹配即为G的最佳匹配。基于KM算法，本文提出SWR与SWD的输入输出参数匹配算法IOMatch。

    //算法名称：IOMatch

    输入：G=（X，Y，E） and |X|≤|Y|

    输出：G的最优扩展匹配

    （1） If（|X|=|Y|）{

    （2） 调用KM算法计算G的最优匹配M；

    （3） }ELSE{

    （4） 利用如下计算将G（X，Y，E）变换到G’（X’，Y，E’）：

    X’=X∪Z，Z={z₁，z₂，…，z_k}（k=|Y|-|X|），

    E’=E∪{<z_i，y_j>|1≤i≤|Z|，1≤j≤|Y|，Wz_iy_j=0}；

    （5） 利用KM算法计算G’的最佳匹配M’；

    （6） 从M’中去除E’’={<z_i，v_j>|z_i∈Z}，将M’变换为M；}

    （7） RETURN M.

    在IOMatch算法基础上，本文给出分级发现算法GradeFinder如下：

    输入： SWR，SWD_n

    输出： 排过序的SWD₁，SWD₂，…，SWD_n

    （1） for each SWD_n do{

    （2） If{RelHS（RN，SN_n）=c-len（RN，SN_n）-k*turns（RN，SN_n）}=0

    （3） return 0；

    （4） else{

    （5） 调用IOMatch算法计算二分图（OR，OS）的最大权匹配，并求出最大相似度和∑sim（OR，OS）_i，i=1，2，…，n；

    （6） 调用IOMatch算法计算二分图（IS，IR）的最大权匹配，并求出最大相似度和∑sim（IS，IR）_j，j=1，2，…，n；

    （7）根据（RelHS（RN，SN）* ∑sim（OR，OS）_i +（1- RelHS（RN，SN））*∑sim（IS，IR）_j）的值对SWD_n进行大小排序；

    （8）对SWD_n 按Qos的值进行大小排序；

    （9） return 按大小排过序的SWD_n；}}

    算法分析：第2-4行，计算SWR与SWD_n的名称概念相关度，如果不相关算法终止；第5-6行计算输出与输入参数的最大相似度和，计算方法相同匹配顺序相反；第7行，按第2行和第5-6行的结果对SWD_n 进行与SWR的相似度排序；第8行，对SWD_n 按Qos的综合开销值进行排序，最后将排过序的SWD_n 按从大到小的顺序输出，算法结束。

    在应用中开发了一个煤矿（矿山）信息查询系统。在此系统中设定一个通过网络接收查询请求，并将满足请求的服务翻译成用户所请求的语言的服务功能。即接收一段文本，将其翻译成英文并通过SMS（Short Message Service，短消息服务）发送译文到一个指定手机号码。目标是一步组合完成，产生适应服务请求中非功能属性（如花销，反应时间等）要求的服务组合方案。本例中，为服务请求定义了两个主要的目标：GoalOnt#translate和GoalOnt#sendSMS。表1列出了一组被发现的服务SWD_n，具有单独的输入、输出和非功能属性语义类型和值，并按照非功能属性对候选服务进行了排序。

Service	Input	Output	NF Properties
SWD1	LanguageOnt#Language LanguageOnt#English LanguageOnt#Text	LanguageOnt#EnglishText	NFPOnt#Cost 1
SWD3	TelecomOnt#PhoneNum LanguageOnt#Text	TelecomOnt#AckSMS	NFPOnt#Cost 1
SWD5	TelecomOnt#AckSMS	TelecomOnt#SuccessProcess	NFPOnt#Cost 1
SWD4	TelecomOnt#PhoneNum LanguageOnt#Text	TelecomOnt#AckSMS	NFPOnt#Cost 3
SWD2	LanguageOnt#French LanguageOnt#English LanguageOnt#Text	LanguageOnt#EnglishText	NFPOnt#Cost 4

    表2给出了系统组合后的服务列表。