基于QoS約束的改進語義Web服務(wù)發(fā)現(xiàn)方法

許國鵬 馬良荔 馮澤波

1 引言

目前，SOA（Service Oriented Architecture）架構(gòu)被廣泛應(yīng)用在軟件設(shè)計領(lǐng)域，同時，Web服務(wù)作為實現(xiàn)SOA架構(gòu)的主流技術(shù)手段，發(fā)展迅速?；ヂ?lián)網(wǎng)平臺上，各種形式功能的服務(wù)應(yīng)用呈幾何級數(shù)增長，實現(xiàn)相同功能的服務(wù)數(shù)量也越來越多。如何高效、準確和快速地從海量服務(wù)中篩選出滿足用戶需求的Web服務(wù)，提高服務(wù)發(fā)現(xiàn)查全率和查準率，成為當前服務(wù)發(fā)現(xiàn)領(lǐng)域研究的重點。

目前，Web服務(wù)發(fā)現(xiàn)方法主要分為兩類：一類是基于語法的服務(wù)發(fā)現(xiàn)方法，代表性的是傳統(tǒng)的UDDI服務(wù)發(fā)現(xiàn)算法［1］；一類基于語義的服務(wù)發(fā)現(xiàn)方法，代表性的是OWL-S/UDDI等級匹配算法［2］。前者是基于關(guān)鍵字的精確匹配，原理簡單，但這種語法級的匹配過程無法保證查全率和查準率；后者引入本體概念，使服務(wù)描述多了語義信息，通過服務(wù)概念間的包含關(guān)系進行匹配等級劃分，匹配效率有所提高，但是每個領(lǐng)域都需要建立相應(yīng)的本體，工作量較大，匹配精度不足的特點也較突出［3］。

針對服務(wù)發(fā)現(xiàn)算法，國內(nèi)外學(xué)者進行了很多相關(guān)研究。王新穎等［4］將改進的BM算法作為單純語義服務(wù)發(fā)現(xiàn)不足后的補充，有效解決了由于概念歧義而導(dǎo)致的匹配失效問題。Chukmol［5］采用層次分析的思想，將服務(wù)匹配過程分解成不同子任務(wù)，建立匹配代理模型。馬秀軍等［6］將信息內(nèi)容語義相似度計算的思想，與服務(wù)的IO語義匹配相結(jié)合，提高了服務(wù)發(fā)現(xiàn)的查全率。

本文分析了OWL-S/UDDI等級匹配算法的優(yōu)缺點，并從提高服務(wù)發(fā)現(xiàn)查全率和查準率的角度，提出基于QoS約束的改進語義Web服務(wù)發(fā)現(xiàn)方法，分階段進行服務(wù)匹配篩選。

2 OWL-S/UDDI等級匹配算法

語義Web服務(wù)發(fā)現(xiàn)算法的研究很多，其中比較經(jīng)典的是OWL-S/UDDI等級匹配算法，該算法建立在服務(wù)本體概念模型的基礎(chǔ)之上，通過概念的上下級包含關(guān)系進行邏輯推理，得到四種匹配結(jié)果，實現(xiàn)服務(wù)發(fā)現(xiàn)。

OWL-S/UDDI等級匹配算法通過構(gòu)建服務(wù)本體層次樹（如圖1）進行簡單的邏輯推理，確定匹配對象的包含關(guān)系，匹配對象主要是ServiceProfile中的服務(wù)輸入輸出信息，將兩個服務(wù)概念匹配結(jié)果分為4個級別［1］：

圖1 本體層次樹

1）Exact：用戶請求輸出與服務(wù)輸出完全等價或用戶請求輸出是服務(wù)輸出的直接子類；

2）Plug-in：服務(wù)輸出包含用戶請求輸出；

3）Subsume：服務(wù)請求輸出包含服務(wù)輸出；

4）Fail：其他情況。

這四種服務(wù)匹配結(jié)果按照匹配程度降序排列：

Exact＞Plug-in＞Subsume＞Fail

等級匹配算法的優(yōu)點是在匹配過程中加入了服務(wù)的語義描述，進行邏輯推理，提高了服務(wù)匹配的查全率和查準率。然而，由于該算法僅僅只是考慮概念間的上下級包含關(guān)系，匹配精度劃分不明確，無法反映同一等級內(nèi)兩個服務(wù)的具體匹配程度。

3 改進的語義Web服務(wù)發(fā)現(xiàn)方法

為了進一步提高服務(wù)發(fā)現(xiàn)的效率，本文采用三級策略分階段進行服務(wù)匹配過程。

首先根據(jù)服務(wù)語義標注的精度選擇，可以把Web服務(wù)形式化表示為一個六元組。

定義1 Web服務(wù)六元組

式中，包含六個元素，Name表示W(wǎng)eb服務(wù)的名稱；Category表示W(wǎng)eb服務(wù)所屬領(lǐng)域類別；Description表示W(wǎng)eb服務(wù)的功能描述；Input={i1,i2,i3,…,im}、Output={o1,o2,o3,…,on}分別表示W(wǎng)eb服務(wù)的輸入、輸出參數(shù)集合；QoS表示W(wǎng)eb服務(wù)的非功能性描述。

根據(jù)Web服務(wù)的形式化定義，可以把語義Web服務(wù)匹配過程分為三個階段［7］。

3.1 基本描述匹配

根據(jù)服務(wù)信息的特點，基本描述匹配依據(jù)Web服務(wù)六元組中Name（服務(wù)名稱）、Category（服務(wù)類別）和Description（服務(wù)描述）三元素進行關(guān)鍵字匹配，完成服務(wù)發(fā)現(xiàn)的初步篩選，實現(xiàn)如下：

1）全部服務(wù)集 W={WS1,WS2,WS3,…,WSn}，WSi為單個服務(wù)；β1,β2,β3分別為服務(wù)屬性Name、Category和Description匹配的閾值；服務(wù)候選集S初始為空；sim(X,Y)即X、Y的匹配程度；候選服務(wù)信息Namew、Categoryw和Descriptionw，請求服務(wù)信息NameR、CategoryR和DescriptionR。

2）For WSi∈全部候選集W

If（（sim（Namew，NameR）＞ β1）&&（sim（Categoryw，CategoryR）＞ β2）

&&（sim（Descriptionw，DescriptionR）＞β3））

將WSi加入到服務(wù)候選集S中

End if

End For

Return服務(wù)候選集S

通過基本描述匹配，劃分服務(wù)的類別，縮小服務(wù)篩選范圍，重點是匹配閾值的選取，其直接影響候選服務(wù)集的大小。

3.2 功能匹配

在基本描述匹配縮小候選服務(wù)集的基礎(chǔ)上，依據(jù)服務(wù)的輸入輸出（IO）進行功能匹配。

定義2 Web服務(wù)的IO相似度

式（1）中，SR、SW分別表示請求服務(wù)和提供服務(wù)；simIO(SR,SW)表示兩個服務(wù)的IO相似度；IR=(IR1,IR2,…,IRk)，IW=(IW1,IW2,…,IWj)分別表示服務(wù)SR、SW的輸入?yún)?shù)集；OR=(OR1,OR2,…,ORt)，OW=(OW1,OW2,…,OWh)表示服務(wù)SR、SW的輸出參數(shù)集；k、j、t、h均為任意正整數(shù)；simIn(IR,IW)表示服務(wù) 輸 入 的 相 似 度 ，其 權(quán) 重 為 α(0≤α≤1)；simOut(OR,OW)表示服務(wù)輸出的相似度，其權(quán)重為β(0≤β≤1)，且 α+β=1。如果用戶對權(quán)值沒有要求，則采用默認的平均權(quán)值，即α=β=0.5。

Web服務(wù)的IO相似度由輸入?yún)?shù)相似度和輸出參數(shù)相似度加權(quán)計算得到，權(quán)重α、β根據(jù)對輸入、輸出參數(shù)考慮的重要程度確定。

在本文中，采用編輯距離和本體概念相似度相結(jié)合的方法，從語法和語義兩方面來綜合考慮計算輸入輸出參數(shù)語義相似度。

定義3 編輯距離［8］

指一個字符串轉(zhuǎn)化為另一個字符串所需進行的最少編輯操作（刪除、插入、替換等）次數(shù)。

采用基于編輯距離的方法計算參數(shù)的相似度為

式（2）中，c1、c2分別為進行比較的參數(shù)； ||c1、 ||c2分別為參數(shù)字符串c1、c2的長度；ed(c1,c2)表示字符串c1轉(zhuǎn)換到c2的最小操作次數(shù)。

基于編輯距離的相似匹配只考慮拼寫上的差異，但是有些字符串拼寫上完全不同，卻具有相同或相似的含義。因此，在計算服務(wù)輸入輸出相似度時還需要考慮語義。

本文中使用本體描述服務(wù)的IO，層次樹中概念節(jié)點深度來衡量服務(wù)IO參數(shù)之間的相似度。基于Wu等提出的LCS算法［9］，IO參數(shù)語義相似度計算方法，公式為

式（3）中，depth函數(shù)表示本體層次樹中從根節(jié)點到當前節(jié)點的深度；LCS表示參數(shù)c1、c2所代表的節(jié)點的最小公共超集。根據(jù)式（2）～（3），得到參數(shù)c1、c2的相似度可以表示為

其中，μ、γ分別為基于編輯距離計算相似度和基于本體概念節(jié)點深度計算相似度兩種方法的權(quán)重，μ+γ=1。權(quán)重大小的選擇沒有固定的模式，需要根據(jù)具體的應(yīng)用環(huán)境選擇。

由于一般服務(wù)的IO都具有多個參數(shù)，因此要計算每個參數(shù)的相似度；并且每個服務(wù)參數(shù)的順序不盡相同，難以確定哪些參數(shù)是對應(yīng)的，故請求服務(wù)和提供服務(wù)的每一個參數(shù)都要配對計算相似度，構(gòu)建相似度矩陣如下：

其中，SI、SO分別為服務(wù)輸入、輸出相似度矩陣；SIkj表示請求服務(wù)輸入?yún)?shù)集中參數(shù)IRk和提供服務(wù)輸入?yún)?shù)集中參數(shù)IWj的相似度，SOth表示請求服務(wù)輸出參數(shù)ORt和提供服務(wù)輸出參數(shù)集中參數(shù)Owh的相似度。

以服務(wù)輸入相似度矩陣為例，遍歷相似度矩陣，取相似度最大的SIkj，并將SIkj所在行和列從矩陣中刪除，在余下的矩陣中繼續(xù)重復(fù)此操作，直至矩陣為空，得到一個最大相似度序列SI1,SI2,…,SIn(n=min(k,j))，則Web服務(wù)輸入相似度為

同理，由服務(wù)輸出相似度矩陣可得一個最大相似度序列 SO1,SO2,…,SOm(m=min(t,h))，則Web服務(wù)輸出相似度為

綜合式（1）～（7），可得到請求服務(wù)和提供服務(wù)的IO相似度simIO(SR,SW)。通過相似度與選取閾值的比較，進一步得到功能相同或相近的候選服務(wù)集。

3.3 QoS約束

服務(wù)質(zhì)量（Quality of Service，QoS）是Web服務(wù)的非功能性描述，反映了服務(wù)滿足用戶需求的能力。完成Web服務(wù)的功能匹配后，再通過QoS建立量化評價機制，對Web服務(wù)候選集進行QoS排序，最終得到滿足用戶需求的服務(wù)集。

QoS衡量服務(wù)的標準有很多，包括安全性、吞吐量、可靠性、可用性、響應(yīng)時間等，有些標準對Web服務(wù)而言是積極的，有些是消極的，不同領(lǐng)域?qū)Ψ?wù)的QoS衡量標準沒有統(tǒng)一的規(guī)定，要求不盡相同。用戶在調(diào)用服務(wù)時，不僅關(guān)注服務(wù)的功能屬性，還對服務(wù)的QoS屬性提出了要求，不同用戶在不同環(huán)境和應(yīng)用場合下對Web服務(wù)的QoS需求偏好也不盡相同。

本文以響應(yīng)時間、可用性、可靠性、信譽度四方面建模描述Web服務(wù)的QoS屬性［10］。

定義4 Web服務(wù)QoS模型

1）其中，s是一個服務(wù)。QoS(s)是Web服務(wù)的服務(wù)質(zhì)量綜合評估；Qtime(s)，Qava(s)，Qrel(s)，Qrep(s)分別為響應(yīng)時間、可用性、可靠性、信譽度衡量函數(shù)。

2）響應(yīng)時間：從開始對一個Web服務(wù)發(fā)出調(diào)用請求到收到執(zhí)行結(jié)果的時間。包括服務(wù)通信時間T1和服務(wù)執(zhí)行時間T2，響應(yīng)時間T=T1+T2。

3）可用性：表示一個Web服務(wù)調(diào)用返回成功結(jié)果的概率。

4）可靠性：表示一個Web服務(wù)正常運行的概率，可以用公式表示為

其中MTTF(t)表示服務(wù)的平均無故障時間，MTTR(t)表示服務(wù)的平均修復(fù)時間。

5）信譽度：表示一個Web服務(wù)的可信賴程度，反映了大眾用戶對調(diào)用服務(wù)后的感性評價，分級定義優(yōu)劣。

由于四個QoS屬性量綱不同，為了能夠綜合考慮服務(wù)的QoS，首先需要將Qtime(s),Qava(s),Qrel(s),Qrep(s)進行歸一化處理，得到各屬性在［0，1］范圍內(nèi)的表示。=( )Qtime(s),Qava(s),Qrel(s),Qrep(s)為QoS歸一化處理的屬性向量，=( )w1,w2,w3,w4為用戶對以上QoS關(guān)注程度的權(quán)重向量，w1+w2+w3+w4=1 ，w1、w2、w3、w4取值根據(jù)用戶偏好，默認情況下w1=w2=w3=w4=0.25；則服務(wù)綜合QoS評價函數(shù)可表示為

Web服務(wù)的綜合QoS值范圍在［0，1］之間，越接近1，則說明服務(wù)的服務(wù)質(zhì)量越高，越滿足用戶的需求。根據(jù)服務(wù)綜合QoS值對服務(wù)候選集進行排序，結(jié)果返回給用戶供其選擇滿足需求的服務(wù)。

4 實驗結(jié)果和分析

4.1 實驗環(huán)境

為了驗證本文中方法的可行性和有效性，通過實驗以查全率和查準率兩個指標衡量Web服務(wù)發(fā)現(xiàn)算法的性能。

查全率：指查詢返回符合查詢條件的服務(wù)數(shù)量與查詢返回服務(wù)總數(shù)量之間的比率；

查準率：指查詢返回符合查詢條件的服務(wù)與測試樣本集中符合查詢條件的服務(wù)的比率。

本實驗環(huán)境為：操作系統(tǒng)Windows XPSP3，應(yīng)用程序開發(fā)與編輯工具為：Visual Studio 2008，實驗中使用的服務(wù)和本體基于開源的服務(wù)測試集OWLS-TC4，選取教育領(lǐng)域100個，旅游領(lǐng)域100個，經(jīng)濟領(lǐng)域200個，共400個服務(wù)，并根據(jù)本文中建立的服務(wù)模型，擴展服務(wù)OWL-S描述文件，完善服務(wù)描述，形成最終的服務(wù)測試候選集。為了簡化過程，實驗中服務(wù)每個匹配階段所用的閾值統(tǒng)一默認設(shè)為0.5。將傳統(tǒng)的UDDI服務(wù)發(fā)現(xiàn)方法、OWL-S/UDDI等級匹配方法和本文的改進匹配方法進行實驗比較。

4.2 實驗結(jié)果和分析

實驗結(jié)果如圖2所示，得到三種Web服務(wù)發(fā)現(xiàn)方法在不同服務(wù)請求下的平均查準率和查全率。

圖2 查準率和查全率比較

實驗結(jié)果表明，由于UDDI基于關(guān)鍵字的匹配方法沒有考慮服務(wù)的語義信息，具有很大的局限性，查全率和查準率較差；OWL-S等級匹配方法匹配過程提供了服務(wù)的語義信息，查全率和查準率有了一定程度的提升，但由于匹配精度不夠，查詢效果還有待提高；本文中的改進匹配方法實現(xiàn)服務(wù)的多層篩選，能夠有效剔除多余的服務(wù)，服務(wù)的查準率得到有效提高，并在服務(wù)篩選中加入了QoS約束控制，為用戶選擇滿足需求的服務(wù)提供了參考，查詢效果優(yōu)于其他兩種方法。

5 結(jié)語

隨著Web服務(wù)技術(shù)的廣泛應(yīng)用，傳統(tǒng)的服務(wù)發(fā)現(xiàn)方法已不能滿足用戶的需求。本文通過分析OWL-S/UDDI服務(wù)發(fā)現(xiàn)方法的優(yōu)缺點，提出了基于QoS約束的Web服務(wù)發(fā)現(xiàn)改進算法，分階段完成服務(wù)匹配過程，最后根據(jù)用戶偏好綜合評估服務(wù)QoS值，對候選服務(wù)集進行排序以供選擇。該方法能夠有效提高服務(wù)的查全率和查準率，為后續(xù)服務(wù)的選擇組合奠定基礎(chǔ)。下一步將逐步完善匹配策略以及QoS數(shù)據(jù)庫的建立、反饋維護機制，進一步提高服務(wù)發(fā)現(xiàn)效率。

［1］王旭輝，姚世軍，焦志勇，等.基于UDDI的Web服務(wù)發(fā)現(xiàn)研究［J］.計算機與現(xiàn)代化，2009（2）：31-34.

WANGXuhui，YAOShijun，JIAOZhiyong，et al.Web Service Discovery Research based on UDDI［J］.Computer&Modern，2009（2）：31-34.

［2］尹輝，季桂樹，袁鳳璋.語義Web服務(wù)匹配算法的研究［J］.網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2008（9）：35-36，75.

YIN Hui，JI Guishu，YUAN Fengzhang．Research on Semantic Web Service Matching Algorithm［J］.Network Security Technology and Application，2008（9）：35-36，75.

［3］王繼東，張瑜，戴耀文.一種改進的語義Web服務(wù)等級匹配算法［J］.自動化技術(shù)與應(yīng)用，2010（2）：31-34.

WANG Jidong，ZHANG Yu，DAI Yaowen.An Improved Semantic Web Service Level Matching Algorithm［J］.Automation Technology&Applications，2010（2）：31-34.

［4］王新穎，何克清，熊偉，等.基于語義和改進BM算法的Web服務(wù)發(fā)現(xiàn)［J］.小型微型計算機系統(tǒng)，2015，36（4）：717-720.

WANG Xinying，HE Ke-qing，IONG Wei，et al.Web Service Discovery based on Semantic and Improved BM Algorithm［J］.Small Miniature Computer Systems，2015，36（4）：717-720.

［5］CHUKMOL U.A framework for Web service discovery：service's reuse，quality，evolution and user's data handling［C］//Proc of the 2nd SIGMOD Workshop on Innovative Database Research.Vancouver：ACM Press，2008：13-18.

［6］馬秀軍，陳繼東，李坤.基于IO與信息內(nèi)容的語義Web服務(wù)發(fā)現(xiàn)［J］.計算機系統(tǒng)應(yīng)用，2016（2）：141-145.

MA Xiujun，CHEN Jidong，LIKun.Semantic Web Service Discovery Based on IO and Information Content［J］.Computer System Application，2016（2）：141-145.

［7］李慶云，魏娟杰.基于多層匹配篩選的Web服務(wù)發(fā)現(xiàn)模型的研究［J］.計算機應(yīng)用與軟件，2010，27（6）：142-144.

LI Qingyun，WEI Juanjie.Research on Web Service Discovery Model based on Multi-layer Matching and Filtering［J］.Computer Applications and Software，2010，27（6）：142-144.

［8］姜華，韓安琪，王美佳，等.基于改進編輯距離的字符串相似度求解算法［J］.計算機工程，2014，40（1）：222-227.

JIANG Hua，HAN Anqi，WANG Meijia，et al.Algorithm for Solving String Similarity Based on Improved Editing Distance［J］.Computer Engineering，2014，40（1）：222-227.

［9］Wu Z，Palmer M.Web semantics and lexical selection［C］//Proc of the 32nd Annual Meeting of the Association for Computational Linguistics，New Mexico State University，Las Cruce，New Mexico，1994：133-138.

［10］楊勝文，史美林.一種支持QoS約束的Web服務(wù)發(fā)現(xiàn)模型［J］.計算機學(xué)報，2005，28（4）：589-594.

YANG Shengwen，SHI Meilin.A Web Service Discovery Model Supporting QoSConstraint［J］.Journal of Computer Science，2005，28（4）：589-594.