基于二分圖匹配的語義web 服務(wù)發(fā)現(xiàn)方法

《基于二分圖匹配的語義web 服務(wù)發(fā)現(xiàn)方法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、鄧水光等:基于二分圖匹配的語義Web服務(wù)發(fā)現(xiàn)方法1基于二分圖匹配的語義Web服務(wù)發(fā)現(xiàn)方法*SupportedbytheNationalKeyTechnologyR&DProgramundergrantNo.2006BAH02A01(國家科技支撐計(jì)劃);theNationalNaturalScienceFoundationofChinaunderGrantNo.60603025andNo.60503018(國家自然科學(xué)基金);theNationalHigh-TechResearchandDevelopmentPl

2、anofChinaunderGrantNo.2006AA01Z171(國家高技術(shù)研究發(fā)展計(jì)劃(863));鄧水光,尹建偉+,李瑩,吳健,吳朝暉(浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,浙江杭州310027)摘要:如何從大規(guī)模服務(wù)集合中快速而準(zhǔn)確的發(fā)現(xiàn)目標(biāo)服務(wù)是應(yīng)用Web服務(wù)技術(shù)的關(guān)鍵?，F(xiàn)有基于語義的Web服務(wù)發(fā)現(xiàn)方法應(yīng)用實(shí)施難度大且效果存在較大提升空間。本文首先提出了Web服務(wù)注冊的信息模型，該模型不受限于具體的Web服務(wù)模型和表達(dá)語言，支持接口語義標(biāo)注和接口依賴關(guān)系的申明。進(jìn)而提出了基于二分圖匹配的語義Web服務(wù)發(fā)現(xiàn)方

3、法，通過對二分圖最佳匹配進(jìn)行擴(kuò)展，將服務(wù)匹配問題轉(zhuǎn)化成二分圖的擴(kuò)展最佳匹配的求解問題，支持服務(wù)接口之間的依賴關(guān)系，從而提高服務(wù)發(fā)現(xiàn)的效果。一系列仿真實(shí)驗(yàn)表明該方法不僅能較大提高服務(wù)發(fā)現(xiàn)的召回率和準(zhǔn)確率，而且還能以線性時(shí)間復(fù)雜度滿足用戶請求。關(guān)鍵詞:面向服務(wù)的計(jì)算、Web服務(wù)、服務(wù)發(fā)現(xiàn)、二分圖匹配中圖法分類號:TP393　　　文獻(xiàn)標(biāo)識(shí)碼:A1引言Web服務(wù)是一種基于網(wǎng)絡(luò)環(huán)境的自適應(yīng)、自描述、模塊化的應(yīng)用程序，因其具備良好的互操作能力和可重用性而在電子商務(wù)、應(yīng)用集成、流程管理等領(lǐng)域中扮演越來越重要的角色[1]。近年

4、來，隨著Web服務(wù)相關(guān)標(biāo)準(zhǔn)的持續(xù)完善和支持Web服務(wù)開發(fā)的軟件平臺(tái)的不斷成熟，Web服務(wù)已經(jīng)成為互聯(lián)網(wǎng)中最為重要的一種計(jì)算資源和軟件資產(chǎn)。而Web服務(wù)數(shù)量的不斷增長，使得用戶難以從大規(guī)模服務(wù)集合中自動(dòng)、快速、準(zhǔn)確的搜索出目標(biāo)服務(wù)。目前，Web服務(wù)發(fā)現(xiàn)吸引了國內(nèi)外眾多學(xué)者的關(guān)注，成為面向服務(wù)的計(jì)算(ServiceOrientedComputing)領(lǐng)域中的關(guān)鍵問題[2]。由于傳統(tǒng)的基于UDDI(UniversalDescription,Discovery,andIntegration)的服務(wù)注冊與發(fā)現(xiàn)機(jī)制僅支持對

5、服務(wù)語法層面的操作，一方面在服務(wù)注冊階段無法準(zhǔn)確刻畫服務(wù)能力，另一方面在服務(wù)發(fā)現(xiàn)過程中因僅提供基于關(guān)鍵字的服務(wù)匹配策略，因此服務(wù)發(fā)現(xiàn)效果無法滿足用戶要求。特別是在服務(wù)數(shù)量劇增的情況下，用戶急需一種自動(dòng)、快速和準(zhǔn)確的服務(wù)發(fā)現(xiàn)機(jī)制。而語義Web服務(wù)的提出，使得Web服務(wù)發(fā)現(xiàn)的研究進(jìn)入了一個(gè)新的階段。由于語義Web服務(wù)采用領(lǐng)域本體準(zhǔn)確刻畫了服務(wù)功能及其屬性，因此基于語義的Web服務(wù)發(fā)現(xiàn)通過語義推理能自動(dòng)準(zhǔn)確的完成服務(wù)匹配，從而提高服務(wù)發(fā)現(xiàn)的效果。目前，眾多的基于語義的Web服務(wù)發(fā)現(xiàn)的方法被提出來[3-13]，這些方法

6、在一定程度上提高了Web服務(wù)發(fā)現(xiàn)的準(zhǔn)確率、召回率和自動(dòng)化程度，但普遍存在如下兩個(gè)問題：1)應(yīng)用實(shí)施難度較大。這是由于這些方法均是建立在全新的語義Web服務(wù)模型和描述語言的基礎(chǔ)上，如DAML-S/OWL-S、WSMO/WSML或者WSDL-S等。這些方法在特定的服務(wù)模型和應(yīng)用場景中均取得較好的效果，但基于這些新的語義Web模型和語言的服務(wù)數(shù)量少之又少；而另一方面，WSDL(WebServiceDescriptionLanguage)作為Web服務(wù)描述規(guī)范而被廣泛采用，出現(xiàn)了大量的基于WSDL的Web服務(wù)，因此在應(yīng)

7、用當(dāng)前這些方法之前，需要將WSDL轉(zhuǎn)化成目標(biāo)服務(wù)模型和語言，因此增大了方法應(yīng)用的難度和復(fù)雜度。2)方法還存在較大的提升空間。這是由于這些方法均遵循了文獻(xiàn)[3]中的服務(wù)匹配原則，即一個(gè)服務(wù)描述鄧水光等:基于二分圖匹配的語義Web服務(wù)發(fā)現(xiàn)方法1s被一個(gè)用戶請求描述r成功匹配，當(dāng)且僅當(dāng)滿足：a)s能夠提供r中的所有輸出；b)r能夠提供s中的所有輸入。后繼很多基于語義的服務(wù)發(fā)現(xiàn)方法均在該文獻(xiàn)的基礎(chǔ)上有所改進(jìn)[4][7][13][17]，但均接受了這一成功匹配的原則。雖然這種匹配原則較為自然，但這一原則過于嚴(yán)謹(jǐn)，在很多情

8、況下將導(dǎo)致很多滿足用戶要求的服務(wù)被過濾掉?？紤]這樣一個(gè)例子：服務(wù)s接收兩個(gè)輸入a和b產(chǎn)生兩個(gè)輸出o和p；而用戶請求r包含一個(gè)輸入a和一個(gè)輸出o。根據(jù)上述成功匹配的原則，由于r不能提供輸入b，即s和r不滿足第二條原則，因此服務(wù)s不滿足需求r。然而在服務(wù)s中可能輸入b對輸出o是可選的。在這種情況下，服務(wù)s顯然滿足r。再以一個(gè)真實(shí)的天氣預(yù)報(bào)服務(wù)http://www.webservicex.c