基于相似度特征的Web服务匹配算法

王慧英，周恺卿，周 辉

(1.重庆工程学院 计算机与物联网学院，重庆 400056；2.吉首大学 信息科学与工程学院，湖南 吉首 416000；3.湖南中医药大学，湖南 长沙 410208)

1 引言

由于Web服务技术的高速发展与标准服务的出现，互联网内中的Web服务数量越来越多，质量越来越高，因此怎样从海量互联网服务内搜索和用户要求一致的Web服务就变成了广受关注的一个问题。所谓服务发现就是凭借Web服务请求者的需求，从众多Web服务内搜索出可以满足请求者Web服务的过程。Web服务匹配即将服务请求者所需要的服务描述和已有的进行对比，以搜索是否存在已有的Web服务。目前，Web服务的描述文件主要是以调用操作的形式对Web服务进行处理，缺乏对Web服务功能的描述，其服务注册机制凭借服务注册信息与关键词进行匹配服务，但这种服务匹配机制并不能全面满足用户需求。

针对上述问题，提出一种基于Petri网和QOS计算的Web服务模糊匹配算法，以期提升Web服务模糊匹配效果。

2 Petri网和QOS计算下Web服务模糊匹配

2.1 Web服务过程模型的Petri网转换

OWL-S表示Web服务的过程模型，该模型具有三种主要方向即：控制流、状态转移与信息转换。信息转化用IO描述，也为Web服务的输出与输入；状态转移利用PE描述，也表示Web服务的某种状态；而控制流代表互相合作时所有服务间的时序关系，因此可以将OWL-S看作一种流程模型，其描述了包含服务之间存在的执行顺序关系，因此能够通过该模型将Web服务转换成Petri网表示。

2.2 Web服务的相似度计算

Petri网即一种有向图，本文在计算Petri网的相似度时，考虑了网络架构、节点与变迁的语义标准[1]。

设定∑i={S1，T1，F1}和∑j={S2，T2，F2}分别表示服务webi与webj过程模型形式化的Petri网，映射M1：T1→T2即从∑i节点集到∑j节点集的部分单映射，集合sumt即依靠映射M1中每一个节点集合构成。P1表示集合sumt内的节点占据∑i和∑j内节点总量的比值。

(1)

同理，映射M3：F1→F2代表∑i库所变迁集至∑j库所库所集的部分单映射[2]，集合sump通过映射M3内存在的全部库所构成，P2代表集合sump内库所变迁集占∑i与∑j内库所总量的比值。

(2)

映射M3：F1→F3代表∑i流集合至∑j流集合的部分单映射，集合sume通过映射M3内所存在的全部流构成，P3代表集合sume内的流占∑i与∑j内流总量的比值。

(3)

其中，P4代表映射M1与M2内所有节点的平均语义[3]相似度，而Sim(n1，n2)能够被描述成节点n1和n2的语义相似度。

(4)

(5)

通过式(4)与(5)计算，能够得到webi与webj的模型相似度是：

S(∑i，∑j)=ω1×P1+ω2×P2+ω3×P3+ω4×P4

(6)

式中，ω1，ω2，ω3，ω4(ω1+ω2+ω3+ω4=1)代表权重。

计算∑i与∑j的节点集、变迁集与流集[4]间具有多种映射，是为了便于查找Petri网内库所与变迁坐标之间的关联，库所、流与变迁间的映射能够通过以下方法获得：

1)通过服务webi与webj的Petri网模型∑i与∑j生成Petri网的语言表达式：

L(∑i)=Str+StrΩ+…+Strjm+…+Strjp

(7)

L(∑j)=Stj1r+Strj2+…+Strjn+…+Strjq

(8)

式中，Strjm、Strjn均为利用变迁语义[5]表示的本体字符串。

2)将字符串集合A={Stri1，Stri2，…，Strip}与B={Strj1，Strj2，…，Strjq}内的字符串当作定点，使用式(9)计算字符串间存在的语义相似度。同时依靠该相速度当做边的权重，组建带权二分图，利用二分图最优匹配方法，得到最优匹配子图

(9)

3)对最优匹配子图内的响应速度超过某种阈值的字符串Strjm、Strjn，凭借字符串间的编辑距离[6]方法对其进行处理，在此过程中需要考虑字符的前后位置关系，以此获得其最差公共子串str，并分别记录str内的所有字符在Strjm、Strjn内相应坐标的字符a、b，把a、b在Petri网内相应的变迁(Ta，Tb)融入映射M1内。

4)针对M1内的所有映射(Ta，Tb)，依靠变迁Ta，Tb相应的输入参数集合ina、inb内的参数当作顶点，以参数间的语义相似度当做边的权重，组建带全二分图，在此基础上以获得参数的最优匹配子图[7]，把最优匹配子图内语义相似度超过s的参数(x，y)融入映射M2内，并将链接Ta和x的流f1以及链接Tb和y的流f2构成的流(f1，f2)映射至M3内，以此处理Ta、Tb相应的输出参数集合outa与outb。

2.3 Web服务Qos指标选择

Web服务的Qos指标较多且复杂，对大多数用户来说，一方面，他们通常只关注其中的一些指标，但是服务的总体质量是通过多个指标得出的；另一方面，他们通常并不存在专业的Web服务知识，所以不能要求他们对所有Qos指标给出合理的反馈以及请求。因此本文提出一种能够同时有效地考虑这两种情况的Web服务模糊匹配方法，即融合了专家意见与用户偏好的Web服务Qos选择方法。

专家通过直觉模糊语言变量对Web服务的所有Qos指标进行评测，将其结果储存到数据中心内。Web服务功能选择为用户供给一种待选服务列表，用户通过直觉模糊语言变量表述对服务Qos的期望，算法把用户的偏好作用到专家意见内，构成一种新的评测矩阵，同时对评测矩阵进行集成[8]，最后为服务的Qos获得一种评分，用户在结束服务之后，还能够对服务质量进行总体评测，形成第二次评分，Qos选择算法综合上述两种评分，进而为用户选择综合评分最高的服务。

2.3.1 专家对服务Qos的评测

本文通过直觉模糊语言变量对Web服务的Qos指标进行评测，专家对服务Qos的评测流程如下所示：

1)通过描述关键性的语言变量，对Qos指标的关键程度进行评测，以构成一种评测矢量：

(10)

2)通过描述优劣性的语言变量[9]，对所有Web服务的Qos指标表现状况进行评测，以构成一种评测矩阵。

(11)

3)依靠相似度运算专家的意见权重，给出Web服务的Qos总体评测的结果，需要尽可能地映射多数专家的意见，所以假如专家的意见都非常相似，就说明意见越有分量，也表明其权重更高。

拟定x，y代表两种模糊值，二者的直觉模糊数为x=[μx，vx]，y=[μy，vy]其海明距离为：

(12)

其相似度为：

(13)

(14)

(15)

4)综合专家的意见

Qos指标关键程度的意见：

W={W1，W2，…，Wk，…，Wn}

(16)

Qos指标满意程度矩阵如下：

(17)

2.3.2 用户偏好对服务原则的评测

用户偏好会在服务选择过程中影响专家综合意见结果，包括Qos指标的关键程度W与所有服务的Qos指标的满意程度G。如果用户对第k种指标给出了自身的意见，就能够认定其关键程度是Ik，同时利用该思想计算Vk，Ik与Vk等不同的语言变量，其能够对W与G产生以下影响：

Wk=Wk∨Ik=[max(μWk，μIk)，min(vWk，vIk)]

(18)

这样，用户所关注的Qos指标会被得到一定程度的重视，并且假如服务的Qos指标能够满足用户要求，其评测评分就会被增加，但如果Qos指标不能满足客户要求，其评测评分也会被相应减小。

依靠以下方法获得服务的Qos综合排名：

W={W1，W2，…，Wn}反映了结合专家建议以及用户偏好的Qos关键程度整体意见，对Wi进行非模糊化处理获得ωi，ωi映射了第i种指标的权重。

根据指标权重，则存在G′ij=ωj×G′11，其表示映射了指标j对服务i的贡献，G′i代表服务i的整体表现。则存在：

(19)

(20)

式中，L(x)=1-μx-vx，L(y)=1-μy-vy，m种候选服务的排序适量e={e1，e2，…，em}，其运算过程如下所示：

(21)

2.4 Web服务模糊匹配

拟定请求服务SR={OR={oi}，IR={ij}}，广告服务SA={OA={oi}，IA={ij}}。概念的相似度是非对称的，因此以一个网络请求服务当做例子。其中网络请求结果是服务的输出，在提供的服务输出是请求服务输出的直接子类时，服务是匹配的，在某种意义上来说，服务的输出以及输出正好呈现相反方向。假如请求服务输入即供给服务输入的直接子类，也就是用户所拥有的数据是所提供的服务所需要输入的一种具体表现，所以也是匹配的；另一方面，假如请求服务输入总量不超过提供服务输入总量，服务可能不会满足需求，而假如请求服务的输出总量没超过提供服务的总量，则不会干扰为用户提供其所需要的服务内容。最后，因为用户最后的目的即获取所需服务，所以通常状态下服务的输出匹配程度对整体服务的匹配程度会起到更大的作用。基于上述分析，本文提出以下方法来计算两种服务的相似度：

Sim(SA，SR)=wi·maxBipart(IR，IA)

(22)

其中，|IA|，|IR|和|OA|，|OR|分别代表广告服务和请求服务的输出以及输入概念总量。wi和wo代表输入与输出概念机相似度对整体服务相似度的影响权重。

依靠权重结合用户对Web服务的评分，以完成对Web服务模糊匹配的目的。

3 实验证明

为了证明所提算法的有效性，进行实验，实验的测试环境是：Intel Pentiuym4，2.8GHz，512MB RAM。Windows XP与J2SDK1.5，实验程序通过Java语言开发，鉴于当前没有相关标准平台与数据集，因此每个Web候选服务的服务质量参数与语义匹配值是依靠随机方法产生的。对Web服务数为5，10，15，20，25，30的服务组合流程进行实验，所有Web服务都存在4中Qos指标值，具体的指标值会放在一定范围中随机生成。拟定6种不同的Web服务数的服务组合流程，所有服务流程都会采用所提算法运行10次，平均时间耗费结果如图1所示。

图1 所提算法匹配的时间耗费

通过图1能够看出，使用所提算法在Web服务数为5时，其耗时最低，随着Web服务数的增多，算法在时间耗费上的数值也会不断提升，但其提升的速度并不算高。这是因为所提算法，会依靠通过对Qos指标的选择，来减少算法在获取Qos指标时的时间，以此进一步提升算法了的整体运行效率。

对于上述6种不同Web服务数的服务组合流程，所有流程通过所提算法进行1000次，所得到的匹配结果最靠近的平均比例如图2所示。

图2 不同的Web服务数匹配最近似比

通过图2的结果能够看出，服务组合流程匹配结果最靠近最优解的比率在97.3%以上，能够使Web服务匹配能够达到最大值，同时Qos指标满足用户的需求，可以很好的实了Web服务的模糊匹配。

4 结束语

为了使用户的Web服务过程更为便捷，提出一种基于Petri网和QOS计算的Web服务模糊匹配算法，实验结果表明该算法有着匹配效率较高的优点。为了进一步为用户提供个性化服务，未来的工作会尝试设计更为有效的服务匹配方法，融合动态描述逻辑的推理功能与可判断性，进一步优化语义匹配方法，以更好的推动Web服务的动态组合，以期可以进一步提升用户满意度，促进Web服务领域的进一步发展。