肖彭燕

(上海海洋大學(xué)信息學(xué)院，上海 201306)

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展，特別是SOA[1]技術(shù)的出現(xiàn)，為web服務(wù)奠定了實(shí)現(xiàn)基礎(chǔ)。近年來(lái)，魚(yú)類分類的信息化工作也得到了很大的發(fā)展。由于單個(gè)服務(wù)提供的功能有限，組合已有的服務(wù)可以滿足用戶更多的需求。為了有效共享，重用這些服務(wù)，需要一種機(jī)器能理解的知識(shí)表達(dá)方法。本體能夠幫助解決這些知識(shí)表達(dá)的問(wèn)題，利用知識(shí)共享，信息集成，語(yǔ)義Web[2]和Web服務(wù)等技術(shù)可以有效地集成魚(yú)類分類信息。

為此，筆者在領(lǐng)域本體的背景下，基于魚(yú)類分類的一個(gè)例子，提出了一個(gè)高效的服務(wù)組合算法。該算法在搜索過(guò)程中，引入啟發(fā)式函數(shù)，該函數(shù)使服務(wù)組合搜索過(guò)程可以根據(jù)已有的web服務(wù)經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整，從而能夠更好地適應(yīng)網(wǎng)絡(luò)不穩(wěn)定性。由于評(píng)判服務(wù)組合方法好壞的標(biāo)準(zhǔn)不僅要求組合的服務(wù)在功能上滿足服務(wù)請(qǐng)求，而且還要求服務(wù)組合效率能得到保證，故設(shè)置一個(gè)滿意度閥值，即只要找到一個(gè)局部最優(yōu)解，在功能上滿足服務(wù)請(qǐng)求，即可作為搜索結(jié)果。這大大減少了服務(wù)搜索范圍，降低了服務(wù)組合時(shí)間，提高了服務(wù)組合效率。

1 語(yǔ)義Web和本體技術(shù)

在語(yǔ)義Web中，各種資源被賦予了明確的語(yǔ)義信息，計(jì)算機(jī)可以分辨和識(shí)別這些語(yǔ)義信息，并對(duì)其自動(dòng)進(jìn)行解釋、交換和處理。語(yǔ)義Web的體系結(jié)構(gòu)一共有7層，見(jiàn)圖1。

圖1 語(yǔ)義Web體系結(jié)構(gòu)

語(yǔ)義Web需要能夠?qū)eb文檔中的術(shù)語(yǔ)含義進(jìn)行形式化描述。本體作為表達(dá)知識(shí)的共享概念模型，已日漸成為知識(shí)工程，知識(shí)管理，智能信息集成，信息檢索等多個(gè)領(lǐng)域的重要組成部分。收集各種魚(yú)類信息[3]，如魚(yú)類名稱、生態(tài)照片、生態(tài)影片、瀕危魚(yú)種、魚(yú)類分布、魚(yú)類標(biāo)本、魚(yú)類電子書(shū)、疾病防治診斷等資料，對(duì)獲得的信息進(jìn)行詳細(xì)分析，從中提取知識(shí)，通過(guò)多種知識(shí)表示元素將這些概念之間的關(guān)聯(lián)表達(dá)出來(lái)，這些知識(shí)表示元素就是元本體，分為概念、屬性、關(guān)系、函數(shù)等。為了讓機(jī)器理解上述的概念和關(guān)系，需對(duì)這些魚(yú)類信息進(jìn)行形式化描述，即采用具體的本體描述語(yǔ)言來(lái)編寫本體，OWL[4]本體描述語(yǔ)言作為W3C的官方標(biāo)準(zhǔn)語(yǔ)言，用來(lái)描述Web文檔和應(yīng)用中內(nèi)在的類和關(guān)系。用OWL語(yǔ)言描述漁業(yè)領(lǐng)域本體，生成OWL格式的文件節(jié)選見(jiàn)圖2。

圖2 魚(yú)類信息OWL格式文件節(jié)選

對(duì)于OWL格式的文件，可利用Jena提供的API進(jìn)行解析，轉(zhuǎn)換成相應(yīng)的Java類，并生成類的屬性與方法，進(jìn)而可使用Java編程，處理用戶需求。

2 基于語(yǔ)義的服務(wù)組合的思想

OWL把一個(gè)Web服務(wù)認(rèn)為是一個(gè)過(guò)程，將服務(wù)之間的匹配計(jì)算轉(zhuǎn)換為輸入、輸出之間擴(kuò)展語(yǔ)義匹配。因此，給出服務(wù)的定義如下：（1）一個(gè)Web服務(wù)可以表示為 WS（In，Out），其中 In={I1，I2，…，Ii}是服務(wù)的輸入?yún)?shù)的集合，Out={O1，O2，…，On}是服務(wù)的輸出參數(shù)的集合；（2）一個(gè)服務(wù)組合是滿足服務(wù)請(qǐng)求的一個(gè)服務(wù)序列，表示為〈WS1，WS2，…，WSn〉。

基于語(yǔ)義的Web服務(wù)動(dòng)態(tài)組合過(guò)程以基于領(lǐng)域本體的服務(wù)間概念相似度為基礎(chǔ)，找出與服務(wù)請(qǐng)求中有語(yǔ)義關(guān)聯(lián)的后繼服務(wù)，繼續(xù)找出該后繼服務(wù)的后繼服務(wù)，依此類推，直到某個(gè)后繼服務(wù)是目標(biāo)服務(wù)，從而得到服務(wù)序列，該序列就是服務(wù)組合的結(jié)果。由于一個(gè)服務(wù)可能存在多個(gè)語(yǔ)義相關(guān)的后繼服務(wù)，因此這些語(yǔ)義相關(guān)的服務(wù)就構(gòu)成了一個(gè)服務(wù)組合圖。以魚(yú)類分類系統(tǒng)為例說(shuō)明這一服務(wù)組合過(guò)程：假設(shè)魚(yú)類分類系統(tǒng)中存在各種Web服務(wù)，如魚(yú)類名稱服務(wù)、魚(yú)類分布服務(wù)、魚(yú)類生態(tài)影片服務(wù)、魚(yú)類疾病診斷服務(wù)、魚(yú)類經(jīng)濟(jì)價(jià)值服務(wù)等，為了完成用戶各種需求，需要組合這些服務(wù)：當(dāng)用戶輸入魚(yú)類名稱，要求輸出的結(jié)果為其經(jīng)濟(jì)價(jià)值，通過(guò)一系列的服務(wù)組合，即可得到目標(biāo)服務(wù)；如果用戶的需求發(fā)生改變，要求輸入魚(yú)類名稱，輸出治療方案，只需修改輸入輸出參數(shù)即可，不必重新編寫代碼來(lái)滿足用戶需求。過(guò)程描述見(jiàn)圖3。

圖3 魚(yú)類服務(wù)組合圖

圖3中，方框表示輸入、輸出參數(shù)，橢圓表示服務(wù)，有向邊相連的兩個(gè)服務(wù)表示兩者之間存在語(yǔ)義關(guān)聯(lián)。

3 基于語(yǔ)義的Web服務(wù)組合的算法

3.1 代價(jià)樹(shù)深度優(yōu)先搜索與啟發(fā)式函數(shù)

代價(jià)樹(shù)深度優(yōu)先搜索的思想描述如下，從剛剛擴(kuò)展的節(jié)點(diǎn)之后繼節(jié)點(diǎn)中選擇一個(gè)代價(jià)最大的節(jié)點(diǎn)為下一個(gè)搜索目標(biāo)，并進(jìn)行擴(kuò)展或判斷。為了提高響應(yīng)時(shí)間，在服務(wù)組合過(guò)程中，對(duì)在此算法的基礎(chǔ)上進(jìn)行改進(jìn)，設(shè)置一個(gè)滿意度閾值，只要滿足一定條件（如用戶滿意度），即可作為搜索結(jié)果。為了進(jìn)一步提高組合的效率，在搜索過(guò)程中引入啟發(fā)式函數(shù) h（x）。

由于網(wǎng)絡(luò)的不穩(wěn)定性，一個(gè)服務(wù)可能由于各種原因調(diào)用不成功，定義Suc（w）表示該web服務(wù)執(zhí)行的成功次數(shù)，F(xiàn)ail（w）表示該web服務(wù)執(zhí)行失敗的次數(shù)。h（x）的初始值為 1|x=0，h（x）的計(jì)算見(jiàn)式（1）、式（2）。

其中，式（1）表示第i次調(diào)用該web服務(wù)后，第i+1次成功執(zhí)行情況下的h（x）的值；式（2）表示第i次調(diào)用該web服務(wù)后，第i+1次執(zhí)行失敗情況下的h（x）的值。

從定義可知，對(duì)于某個(gè)web服務(wù)，調(diào)用成功的次數(shù)越多，h（x）的值越大，反之，若調(diào)用失敗的次數(shù)越多，則h（x）值越小?？紤]到web服務(wù)執(zhí)行的頻率，如一個(gè)web服務(wù)執(zhí)行成功50次和執(zhí)行失敗51次之間的差距是很小的，因此h（x）的調(diào)整量呈指數(shù)級(jí)的衰減，h（x）的取值范圍在0到2之間。

3.2 算法描述

條件：設(shè)置棧route、search，棧元素?cái)?shù)據(jù)類型為字符串，分別用來(lái)存儲(chǔ)解路徑和搜索路徑。為方便起見(jiàn)，在每個(gè)服務(wù)中添加布爾型標(biāo)記flag，flag為false時(shí)表示該弧線未被搜索到,否則表示該弧線已被搜索過(guò)，flag的使用防止了搜索時(shí)重復(fù)走已經(jīng)走過(guò)的路。初始化滿意度函數(shù) U（s）=1，Success（w）=0，F(xiàn)ail（w）=0。輸入：服務(wù)請(qǐng)求WSr=（Ir，Or），服務(wù)組合滿意度ζ。輸出：服務(wù)組合序列〈WS1，WS2，…，WSn〉。

算法執(zhí)行步驟如下。（1）初始化棧route=null。（2）判斷是否有與服務(wù)請(qǐng)求輸入?yún)?shù)相匹配的服務(wù)，即是否有弧相連接（是否有后繼服務(wù)）。若有，則按從小到大的順序依次存入earch[WSr]，并且令flag=0。（3）取出首元素 WSi=search[WSr]。若 WSi為空，則 goto 6；否則，若 WSi調(diào)用成功，則 Success（w）++，調(diào) 整 h（x），入棧 router，令 flag=1，、U（s）+=weight﹡h（x），并重新調(diào)整 search[WSr]的順序，再分別把WSi所有的后繼服務(wù)的權(quán)值及更新后的啟發(fā)式函數(shù)h（x）值之和按從小到大的順序依次入棧search[WSi]；若WSi調(diào)用不成功，則Fail（w）++，調(diào)整h（x），進(jìn)而重新調(diào)整 search[WSr]的順序。（4）判斷服務(wù)WSi是否是目標(biāo)服務(wù)狀態(tài)，若是目標(biāo)服務(wù)，則判斷 U（s）是否≥ξ，若成立，則 goto 6，否則 goto 5；若不是目標(biāo)服務(wù)，goto 2。（5）刪除棧router中的首元素，并從棧search[gettop（router）]中讀取第一個(gè)flag=0的元素WSj，若WSj為null，則繼續(xù)刪除棧router中首元素，并從相應(yīng)的首元素的棧數(shù)組中搜索第一個(gè)flag=0的元素WSk，直到WSk不為null，將 WSk 入棧 router，goto 2。（6）若 router為 null，則服務(wù)組合失??；若router不為null，則服務(wù)組合成功，遍歷棧router中的服務(wù)即可。

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)環(huán)境部署在一臺(tái)CPU為Intel（R）Pentium（R）Dual T2410@2.00GHz、內(nèi)存為2.00GB的PC機(jī)上，操作系統(tǒng)為Windows XP,開(kāi)發(fā)工具為E－clipse，開(kāi)發(fā)語(yǔ)言為Java，OWL解析工具為Jena提供的API。9個(gè)數(shù)據(jù)集的服務(wù)數(shù)量分別為500、700、900、1 100、1 300、1 500、1 700、1 900、2 100，取平均組合時(shí)間作為結(jié)果。將本算法與另一種啟發(fā)式的web service組合算法（BF*[6]）以及簡(jiǎn)單的遍歷方式（simple）對(duì)比，進(jìn)行算法性能的評(píng)估，得到的實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 本文算法與BF*，simple算法服務(wù)組合效率比較

由圖4可以看出，就時(shí)間效率而言，研究采用的算法比BF*、simple都要好。BF*算法的性能變化波動(dòng)較大，這與其啟發(fā)式規(guī)則有關(guān)，而研究采用的算法，隨著web服務(wù)數(shù)量的增長(zhǎng)，曲線緩慢上升，服務(wù)組合時(shí)間的增長(zhǎng)幅度相對(duì)較小。

通過(guò)實(shí)驗(yàn)分析，可以看出研究采用的算法具有以下的優(yōu)點(diǎn)：（1）語(yǔ)義性；（2）能在保證組合質(zhì)量的前提下，高效的進(jìn)行服務(wù)組合；（3）動(dòng)態(tài)適應(yīng)性，每次服務(wù)組合過(guò)程后，通過(guò)對(duì)相應(yīng)的路徑的啟發(fā)式函數(shù)值進(jìn)行更新，為下次服務(wù)選擇提供依據(jù)。

5 總結(jié)

通過(guò)對(duì)魚(yú)類信息的Web服務(wù)組合，可以滿足用戶各種各樣的需求，而不用重新編寫代碼來(lái)實(shí)現(xiàn)，提高了系統(tǒng)的效率。由于現(xiàn)有的服務(wù)標(biāo)準(zhǔn)和協(xié)議僅限于語(yǔ)法的層次，沒(méi)有語(yǔ)義功能，所以研究在基于領(lǐng)域本體的背景下，生成了一個(gè)服務(wù)組合圖?；谠搱D，在搜索的過(guò)程中，采用代價(jià)樹(shù)的深度優(yōu)先搜索方式，并引入啟發(fā)式函數(shù)，使其在搜索過(guò)程中根據(jù)已有的web服務(wù)組合經(jīng)驗(yàn)，淘汰較差的web services，提高了系統(tǒng)的自適應(yīng)性。下一步將重點(diǎn)研究更好的啟發(fā)式函數(shù)計(jì)算方法，充分利用服務(wù)組合，實(shí)現(xiàn)基于SOA技術(shù)的魚(yú)類分類信息系統(tǒng)構(gòu)建。

[1] 邢少敏，周伯生.SOA研究進(jìn)展[J].計(jì)算機(jī)科學(xué)，2008，35（9）：13-20.

[2] Tim Berners-Lee,James Hendler,Ora Lassila.The Semantic Web[J].Scientific American（S0036-8733），2001，284（5）：34-43.

[3] 成慶泰,鄭葆珊.中國(guó)魚(yú)類系統(tǒng)檢索 [M].北京：科學(xué)出版社，1987.

[4] Smith M K,Welty C,McGuinness DL.OWL Web ontology guide[EB/OL].http://www.w3.org/TR/owl-guide/，2004.

[5] 潘謙紅，王 炬.基于屬性論的文本相似度計(jì)算[J].計(jì)算機(jī)學(xué)報(bào)，1999，22（6）：651-655.

[6] 方賢進(jìn)，李龍澍.多模式匹配算法的優(yōu)化研究 [J].軟件時(shí)空，2007，（03）：211.