Web服務(wù)關(guān)聯(lián)語(yǔ)義索引WSSI系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)*

覃事剛，姜 慧，黃波英

(湖南電氣職業(yè)技術(shù)學(xué)院 科技處, 湘潭 411101)

Web服務(wù)關(guān)聯(lián)語(yǔ)義索引WSSI系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)*

覃事剛，姜 慧，黃波英

(湖南電氣職業(yè)技術(shù)學(xué)院 科技處, 湘潭 411101)

為了解決Web服務(wù)間自適應(yīng)調(diào)用關(guān)聯(lián)的問(wèn)題，運(yùn)用形式概念分析FCA的相關(guān)知識(shí)，設(shè)計(jì)了一種Web服務(wù)關(guān)聯(lián)語(yǔ)議索引WSSI系統(tǒng).該系統(tǒng)對(duì)任意給定的Web服務(wù)集合掘挖服務(wù)間隱含的邏輯關(guān)系，構(gòu)造Web服務(wù)關(guān)聯(lián)語(yǔ)義索引，為組合服務(wù)發(fā)現(xiàn)提供可靠的接口，并進(jìn)行了相關(guān)的實(shí)驗(yàn)分析.實(shí) 驗(yàn) 證 明 了 該系統(tǒng)的有效性. 關(guān)鍵詞：Web服務(wù)；隱式關(guān)聯(lián)；WSSI

0 引 言

語(yǔ)義Web服務(wù)發(fā)現(xiàn)是Web服務(wù)的一個(gè)重要領(lǐng)域，其熱點(diǎn)主要集中在基于語(yǔ)義的Web服務(wù)發(fā)現(xiàn)，以基于DAML-S語(yǔ)言的語(yǔ)義匹配[1]、基于過(guò)程本體論的服務(wù)發(fā)現(xiàn)方法[2]、基于數(shù)學(xué)特定領(lǐng)域的Web服務(wù)匹配算法[3]、多主體服務(wù)環(huán)境MAGE(Multi-Agent-Environment)[4]等為主要代表，其服務(wù)發(fā)現(xiàn)過(guò)程都是客戶根據(jù)需求在服務(wù)注冊(cè)機(jī)構(gòu)中心單個(gè)的查找，然后組合成客戶需求的服務(wù)流.很明顯，這些方法都是發(fā)現(xiàn)單個(gè)的服務(wù)，在現(xiàn)實(shí)生活中，服務(wù)之間是可能存在某些隱含的關(guān)聯(lián)，建立基于這種關(guān)聯(lián)的Web服務(wù)語(yǔ)義索引(WSSI: Web Service-associated Semantics Index)，實(shí)現(xiàn)客戶的組合服務(wù)請(qǐng)求的多服務(wù)組合發(fā)現(xiàn)，對(duì)提高服務(wù)發(fā)現(xiàn)效率、減輕網(wǎng)絡(luò)負(fù)載具有重要的意義.本文在現(xiàn)有的研究基礎(chǔ)上開(kāi)發(fā)出了一種Web服務(wù)關(guān)聯(lián)語(yǔ)義索引(WSSI)系統(tǒng)，具有Web服務(wù)發(fā)現(xiàn)、組合及組合發(fā)現(xiàn)等功能.

1 WSSI系統(tǒng)的理論基礎(chǔ)

1.1 Web服務(wù)間的隱式邏輯關(guān)系是存在的

現(xiàn)實(shí)中，很多服務(wù)之間的關(guān)系并不明顯然，但在特定的背景下，這些服務(wù)是很有可能存在某種關(guān)聯(lián)的，例如圖1所示，假設(shè)酒店、火車站、超市、電影院、旅行社等商業(yè)機(jī)構(gòu)之間存在一定的合作關(guān)系，那么消費(fèi)者在其中某一個(gè)機(jī)構(gòu)得到服務(wù)的同時(shí)，也可以享受到其他機(jī)構(gòu)提供的服務(wù).可以看出，Web服務(wù)之間的邏輯關(guān)系雖然不明顯，但確實(shí)是存在的，需要通一定的方法抽象成能被計(jì)算機(jī)識(shí)別的Web服務(wù)關(guān)聯(lián)圖(見(jiàn)圖2).

圖1 現(xiàn)實(shí)生活中的服務(wù)關(guān)系

圖2 服務(wù)隱式關(guān)系的抽象結(jié)構(gòu)

1.2 Web服務(wù)形式背景下的概念格

根據(jù)形式概念分析FCA[5]的相關(guān)知識(shí)，在給定的背景下確定該背景的概念格有很多方法.文獻(xiàn)[6]提出了Web服務(wù)形式背景WsK(Gws,Msg, K)下構(gòu)造出相應(yīng)該的概念格的方法，該方法給出了Web服務(wù)形式背景WsK(Gws,Msg, K)的相關(guān)知識(shí)，該形式背景只表示了消息與Web服務(wù)之間的關(guān)系，但是不能清楚的反應(yīng)出輸入消息、Web服務(wù)和返回消息之間的關(guān)系.因此，就把Web服務(wù)形式背景WsK(Gws,Msg, K)分解再定義成兩個(gè)形式背景：input-WsK和output-WsK.再針對(duì)這兩個(gè)形式背景：input-WsK和output-WsK分別構(gòu)造輸入消息服務(wù)格input-WsK和輸出消息服務(wù)格output-WsK.由此可見(jiàn)，要確定概念格尋找形式概念是關(guān)鍵，而尋找形式概念是可以在形式背景的背景圖Gk中查找所有的最大完全二部圖來(lái)實(shí)現(xiàn)的.

定義1二分圖G=(A,B,E)，有km1,n1(A1,B1) ∈G和km2,n2(A2,B2) ∈G，我們定義km1,n1(km2,n2=(A1,B1) ( (A2,B2)=(A1∪A2,B1∩B2)=km3,n3(A3,B3) (對(duì)象擴(kuò)展運(yùn)算，其中km3,n3∈G且滿足f(A3)=B3)km1,n1(km2,n2=(A1,B1) ( (A2,B2)=(A1,∩A2,B1∪B2)=km3,n3(A3,B3)(屬性擴(kuò)展運(yùn)算，其中km3,n3∈G且滿足k(B3)=A3) .

對(duì)象擴(kuò)展運(yùn)算和屬性擴(kuò)展運(yùn)算是我們?cè)诮o定的二分圖G(A,B,E)中尋找最大完全二分圖的基本操作.

定義2 如果集合S是由其子集Y按照某種規(guī)則生成的，我們稱Y是S的生成集，并且稱Y中的元素為生成元，記為e.

我們要討論的集合S是二分圖G中所有完全二分圖組成的集合，運(yùn)算規(guī)則是對(duì)象擴(kuò)展運(yùn)算或?qū)傩詳U(kuò)展運(yùn)算，生成集Y中的元素是也是完全二分圖，但是不是最大完全二分圖，其集合中的元素e可以由二分圖G中其中的某頂點(diǎn)集中的頂點(diǎn)確定，在構(gòu)造生成集時(shí)，可根據(jù)二分圖G的不同頂點(diǎn)集構(gòu)造兩個(gè)不同的生成集Y，所以S的生成集不是唯一的.

由二分圖GYA,B,E)構(gòu)造格L的過(guò)程：輸入二分圖G,初始化生成集Y；對(duì)Y進(jìn)行擴(kuò)展為新的集合S；對(duì)S進(jìn)行優(yōu)化，轉(zhuǎn)換對(duì)應(yīng)的形式概念集合K；對(duì)K的概念元素按外延或內(nèi)涵排序構(gòu)造格，并填寫(xiě)概念表;輸出結(jié)果.

1.3 WSSI的構(gòu)建過(guò)程

對(duì)給定的一個(gè)Web服務(wù)，先只考慮輸入消息、服務(wù)名和輸出消息，描述為WS(in,ws,out)，其中ws為服務(wù)名稱，in ={ msg1, msg2,…,msgm}是該Web服務(wù)輸入消息的集合,out ={msg1, msg2,…,msgk}表示返回消息集合，它是一個(gè)三元組，對(duì)給定的Web服務(wù)集U={WS1, WS2, WS3……，WSn}，當(dāng)n=5時(shí)可以用如圖3所示.

圖3 Web服務(wù)與消息的分配圖

在圖3中，第一層代表輸入消息，中間代表Web服務(wù)名，第三層代表輸出消息，輸入消息層與服務(wù)層之間的邊表示多個(gè)服務(wù)名具有相同的多個(gè)輸入消息，同樣，輸出消息層與服務(wù)層之間的邊表示多個(gè)服務(wù)名具有相同的多個(gè)輸入消息，調(diào)用服務(wù)層的Web服則需要輸入第一層的輸入消息，服務(wù)調(diào)用完成后返回第三層的輸出消息.現(xiàn)在，我們蓋住圖的下半部分即輸出消息集合，看圖的上半部分就成了一個(gè)典型的二分圖；同樣，我們蓋住圖的上半部分即輸出消息集合，看圖的下半部分也是一個(gè)典型的二分圖，描述了服務(wù)集合中服務(wù)與輸入消息之間的關(guān)系.如果事物對(duì)象為Web服務(wù)，事物屬性為輸入/輸出消息，則直觀表述了Web服務(wù)與輸入/輸出消息之間的聯(lián)系，具有以下優(yōu)點(diǎn)：用可視化的二元關(guān)系描述對(duì)象(Web服務(wù)集)與屬性(輸入/輸出消息集)之間的關(guān)系，方便揭示W(wǎng)eb服務(wù)間的潛在語(yǔ)義聯(lián)系. 下面，在兩個(gè)二元關(guān)系中就可以對(duì)具有共同輸入消息屬性的Web服務(wù)對(duì)象分組，對(duì)具有共同輸出消息屬性的Web服務(wù)對(duì)象分組，如果存在輸出消息集合等于輸入消息集合的具有共同輸出消息屬性的Web服務(wù)分組oW和具有共同輸入消息屬性的Web服務(wù)分組iW,則oW與iW之間存在關(guān)聯(lián)關(guān)系，其對(duì)應(yīng)的Web服務(wù)之間的隱含關(guān)系就被挖掘出來(lái)，Web服務(wù)關(guān)聯(lián)圖的構(gòu)建步驟如下：①將給定的Web服務(wù)集W分解為兩個(gè)二元組：Wi和Wo.其中, Wi表示W(wǎng)eb服務(wù)集與輸入消息之間的二元關(guān)系， Wo表示W(wǎng)eb服務(wù)集與輸出消息之間的二元關(guān)系；②對(duì)Wi進(jìn)行分組(條件: Web服務(wù)對(duì)象具有共同輸入消息屬性)；③對(duì)Wo進(jìn)行分組(條件:具有共同輸出消息屬性的Web服務(wù)對(duì)象)；④通過(guò)Wi×Wo構(gòu)造Web服務(wù)關(guān)聯(lián)圖Gws；⑤對(duì)Gws進(jìn)行約簡(jiǎn)，并輸出約簡(jiǎn)后的Gws.

2 WSSI系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

Web服務(wù)關(guān)聯(lián)語(yǔ)義索引(WSSI)系統(tǒng)(如圖4所示)由兩大部分組成：WS Collector和語(yǔ)義索引系統(tǒng).WS Collector的主要作用是從互聯(lián)網(wǎng)上搜集盡可能多的Web服務(wù)，并注冊(cè)到UDDI注冊(cè)中心，為語(yǔ)義索引系統(tǒng)構(gòu)建Web服務(wù)關(guān)聯(lián)語(yǔ)義索引提供豐富的Web服務(wù)，其核心為基于聚焦搜索的Web服務(wù)搜索引擎.語(yǔ)義索引系統(tǒng)的功能是對(duì)已在UDDI注冊(cè)中心注冊(cè)的Web服務(wù)進(jìn)行形概念分析，挖掘出Web服務(wù)之間的隱含關(guān)系，并以相關(guān)的概念格作為理論工具，構(gòu)建Web服務(wù)關(guān)聯(lián)語(yǔ)義索引(WSSI)，為組合服務(wù)的發(fā)現(xiàn)提供可靠的接口.

2.1 UDDI注冊(cè)中心數(shù)據(jù)結(jié)構(gòu)的擴(kuò)展

UDDI注冊(cè)中心是基于UDDI協(xié)議實(shí)現(xiàn)的，主要提供Web接口和API接口.本文在UDDI的基礎(chǔ)上增加三個(gè)新的數(shù)據(jù)結(jié)構(gòu)：TInput_WsL、TOutput_WsL和TWSSI?(TInput_WsL存儲(chǔ)輸入消息服務(wù)格Input_WsL，TOutput_WsL存儲(chǔ)輸入消息服務(wù)格Output_WsL，TWSSI?存儲(chǔ)Web服務(wù)關(guān)聯(lián)語(yǔ)義索引WSSI)，TInput_WsL、TOutput_WsL和TWSSI?在UDDI注冊(cè)中心的數(shù)據(jù)表分別如表1、表2和表3所示.

圖4 Web服務(wù)關(guān)聯(lián)語(yǔ)義索引(WSSI)的體系結(jié)構(gòu)圖

列名數(shù)據(jù)類型不能為空默認(rèn)值說(shuō)明Input-WsC＿KeyVARCHAR(45)√PrimarykeyExtensiontextnullIntensiontextnull

表2 TOutput_WsL表

表3 TWSSI表

表3 TWSSI表

列名數(shù)據(jù)類型不能為空默認(rèn)值說(shuō)明Input-WsC＿KeyVARCHAR(45)√ReferencekeyfromTInput＿WsLOutput-WsC＿KeyVARCHAR(45)√ReferencekeyfromTOutput＿WsLSem＿RelationInt(4)√0Senmanticrelationvalue

其中表1中的Input-WsC_Key和表2的Output-WsC_Key為UDDI注冊(cè)中心分配給Input-WsC和Out-WsC的唯一ID號(hào)，Extension和Intension字段為Web服務(wù)或消息的集合.表3中的Sem_Relation的值表示兩個(gè)Input-WsC和Out-WsC之間的語(yǔ)義關(guān)系.

2.2 WSSI構(gòu)建算法及分析

根據(jù)前面的知識(shí)可得，在已知輸入消息服務(wù)格和返回消息服務(wù)格的前提下，構(gòu)建Web服務(wù)關(guān)聯(lián)語(yǔ)義索引(WSSI)的過(guò)程實(shí)質(zhì)就是在與輸入消息服務(wù)格和返回消息服務(wù)格相對(duì)應(yīng)的兩個(gè)本體間尋找映射集.第一步需要實(shí)現(xiàn)概念格的構(gòu)造(見(jiàn)圖5),第二步在概念格的基礎(chǔ)上構(gòu)建索引(見(jiàn)圖6).

算法1的核心變成了在二分圖查找所有的最大完全二分圖.假設(shè)以二分圖G(A,B,E)中的頂點(diǎn)集A構(gòu)造的生成集Y中的元素個(gè)數(shù)為n(或是|A|=n)，如果生成集Y中的元素ei(Ai,Bi)，其中|Y|=|A|，滿足，|Ai|=1，|Bi|=|B|-1,即任意的兩個(gè)ei，有且只有|Bi|-1個(gè)元素b∈ Bi相同.如果把某個(gè)e0(A0,B0)且|A0|=1擴(kuò)展成e’(A’,B’)且|A’|=|A|-1需要執(zhí)行f(n-1)時(shí)間，循環(huán)對(duì)每個(gè)ei進(jìn)行擴(kuò)展的時(shí)間和為f(n(n-1)),此時(shí)的時(shí)間復(fù)雜度為：O(f(n(n-))=O(n2).

算法2為 Web服務(wù)關(guān)聯(lián)語(yǔ)義索引構(gòu)建算法,假設(shè)|A|=n,|B|=m,則計(jì)算一次ai∈A和bj∈B的語(yǔ)義關(guān)系Rij的時(shí)間為1，則該算法的復(fù)雜度為O(n*m).

圖5 概念格構(gòu)造算法

圖6 Web服務(wù)關(guān)聯(lián)語(yǔ)義索引構(gòu)建算法

3 實(shí)驗(yàn)分析

WSSI的實(shí)驗(yàn)分析將采用與基于Web服務(wù)圖測(cè)試系統(tǒng)(WSG Test Platform)[7]相同的實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)數(shù)據(jù)，并通過(guò)對(duì)相同的服務(wù)請(qǐng)求在WSSI和WSG中從服務(wù)組合效率和服務(wù)發(fā)現(xiàn)響應(yīng)效率兩方面進(jìn)行比較.

硬件環(huán)境：CPU為 奔騰4 3.0GHz,內(nèi)存為512MB，Windows XP操作系統(tǒng).

實(shí)驗(yàn)數(shù)據(jù)：從UDDI注冊(cè)中心隨機(jī)抽取9個(gè)Web服務(wù)數(shù)據(jù)集，每個(gè)服務(wù)集總數(shù)分別為：300、600、900、1200、1600、2000、2400、2700、3000，在每個(gè)服務(wù)集上數(shù)據(jù)集上隨機(jī)選擇30個(gè)服務(wù)組成的服務(wù)流E-workflow[8]請(qǐng)求.實(shí)驗(yàn)結(jié)果如圖7所示.

1)WSSI與WSG的構(gòu)建效率比較:

從圖7(a)可以看出， 在服務(wù)總數(shù)比較小的兩種邏輯結(jié)構(gòu)的構(gòu)建時(shí)間幾乎差不多，但隨著服務(wù)總數(shù)的增多，WSIRG的構(gòu)建時(shí)間明顯小于WSG的時(shí)間,體現(xiàn)了新方法的優(yōu)勢(shì).

2)服務(wù)發(fā)現(xiàn)時(shí)間的比較:

從圖7(b)可看出，隨著服務(wù)集的規(guī)模不斷擴(kuò)大，基于WSSI的服務(wù)發(fā)現(xiàn)的耗費(fèi)時(shí)間與WSG發(fā)現(xiàn)的耗費(fèi)時(shí)間差值越來(lái)越大.

從結(jié)果可以看出，WSSI存在以下優(yōu)勢(shì)：WSSI與WSG的構(gòu)建方法相比，WSSI的頂點(diǎn)不是單個(gè)的Web服務(wù)，而是同類的Web服務(wù)集，其構(gòu)造過(guò)程轉(zhuǎn)換為對(duì)Web服務(wù)按給定條件分類劃分為不同的頂點(diǎn)集，理論上構(gòu)建WSSI的算法復(fù)雜度為O(n4)，但實(shí)驗(yàn)證明在實(shí)際情況中幾乎不可能達(dá)到或是接近最壞情況.反觀其WSG的頂點(diǎn)數(shù)遠(yuǎn)大于WSSI，因此，基于WSSI的服務(wù)發(fā)現(xiàn)的耗費(fèi)時(shí)間，隨著服務(wù)數(shù)量越多，速度明顯提高.

圖7 實(shí)驗(yàn)結(jié)果比較

4 總結(jié)

WSSI是一種Web服務(wù)間存在的某種語(yǔ)義關(guān)聯(lián)關(guān)系的抽象結(jié)構(gòu)，通過(guò)對(duì)Web服務(wù)的語(yǔ)義關(guān)聯(lián)關(guān)系的深入挖掘，開(kāi)發(fā)了一套Web服務(wù)關(guān)聯(lián)語(yǔ)義索引 (WSSI)系統(tǒng)，設(shè)計(jì)了形式背景下的概念格的構(gòu)造算法和基于本體的WSSI構(gòu)建算法,并與基于斷言關(guān)系的WSG進(jìn)行比較實(shí)驗(yàn).結(jié)果證明WSSI明顯優(yōu)勢(shì)于WSG，更加有利于提高服務(wù)發(fā)現(xiàn)效率.

[1] M. Paolucci, J.Soudry, N.Srinivasan, K. Sycara. A Broker for OWL-S Web Services[J]. Multiagent Systems, Artificial Societies, and Simulated Organizations, Springer,2004, 13:79-98.

[2] Mark Klein, Abraham Bernstein.Searching for Services on the semantic Web Using Process Ontologies[C].In:Proceedings of the International Semantic Web Working Symposium(SWWS).Amsterdam:IOS Press,2001,159-172.

[3] O Caprotti，M Dewar，D Turi.Mathematical Service Matching Using Description Logic and OWL[C]. Mathematical Knowledge Management, Third International Conference, Mkm, Bialowieza, Poland, September,2004, 3119:73-87.

[4] 史忠植,蔣運(yùn)承，等．基于描述邏輯的主體服務(wù)匹配[J].計(jì)算機(jī)學(xué)報(bào)， 2004, 27(5)：625-635.

[5] 甘特爾,威 爾,馬 垣，等. 形式概念分析[M]. 北京：科學(xué)出版社，2007.[6] 覃事剛,劉建勛,秦祖澤.Web服務(wù)關(guān)聯(lián)圖構(gòu)造方法[J]. 計(jì)算機(jī)集成制造系統(tǒng),2011,(8):1670-1676.

[7] 巢 煉．基于圖理論的Web服務(wù)發(fā)現(xiàn)方法研究[D]．湖南：湘潭大學(xué)碩士學(xué)位論文,2007.

[8] J. Cardoso and A. Sheth. Semantic E-Workflow Composition[J]. Journal of Intelligent Information Systems，2003，21(3):191-225.

Design and Implementation of Web Service-associated Semantics Index System

QIN Shi-gang， JIANG Hui， HUANG Bo-ying

(Department of Science and Technology, Hunan Electrical College of Technology, Xiangtan, 411101， China)

This paper proposes a novel WSSI system to construct Web Services-associated Semantics Index from the perspective of deep mining of the hidden relationship between mutual Web Services. In the system, by using the theory of Formal Concept Analysis, it defines the system framework and basic functions, designs some key problem’s solving algorithms and provides reliable interface for composite service discovery. Related experiments are done in the end and the simulation results show the effectiveness.

Web Services; implicit link; WSSI

2016-07-13

湖南省科技計(jì)劃項(xiàng)目(2014GK3004)；湖南省教育廳科研項(xiàng)目(13C160).

覃事剛(1979-)，男，碩士，講師，研究方向：服務(wù)計(jì)算與云計(jì)算研究.

TP393

A

1671-119X(2016)04-0046-05