覃事剛，姜 慧，黃波英

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

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

覃事剛，姜 慧，黃波英

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

為了解決Web服務(wù)間自適應(yīng)調(diào)用關(guān)聯(lián)的問題，運(yùn)用形式概念分析FCA的相關(guān)知識，設(shè)計(jì)了一種Web服務(wù)關(guān)聯(lián)語議索引WSSI系統(tǒng).該系統(tǒng)對任意給定的Web服務(wù)集合掘挖服務(wù)間隱含的邏輯關(guān)系，構(gòu)造Web服務(wù)關(guān)聯(lián)語義索引，為組合服務(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 引 言

語義Web服務(wù)發(fā)現(xiàn)是Web服務(wù)的一個重要領(lǐng)域，其熱點(diǎn)主要集中在基于語義的Web服務(wù)發(fā)現(xiàn)，以基于DAML-S語言的語義匹配[1]、基于過程本體論的服務(wù)發(fā)現(xiàn)方法[2]、基于數(shù)學(xué)特定領(lǐng)域的Web服務(wù)匹配算法[3]、多主體服務(wù)環(huán)境MAGE(Multi-Agent-Environment)[4]等為主要代表，其服務(wù)發(fā)現(xiàn)過程都是客戶根據(jù)需求在服務(wù)注冊機(jī)構(gòu)中心單個的查找，然后組合成客戶需求的服務(wù)流.很明顯，這些方法都是發(fā)現(xiàn)單個的服務(wù)，在現(xiàn)實(shí)生活中，服務(wù)之間是可能存在某些隱含的關(guān)聯(lián)，建立基于這種關(guān)聯(lián)的Web服務(wù)語義索引(WSSI: Web Service-associated Semantics Index)，實(shí)現(xiàn)客戶的組合服務(wù)請求的多服務(wù)組合發(fā)現(xiàn)，對提高服務(wù)發(fā)現(xiàn)效率、減輕網(wǎng)絡(luò)負(fù)載具有重要的意義.本文在現(xiàn)有的研究基礎(chǔ)上開發(fā)出了一種Web服務(wù)關(guān)聯(lián)語義索引(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)者在其中某一個機(jī)構(gòu)得到服務(wù)的同時，也可以享受到其他機(jī)構(gòu)提供的服務(wù).可以看出，Web服務(wù)之間的邏輯關(guān)系雖然不明顯，但確實(shí)是存在的，需要通一定的方法抽象成能被計(jì)算機(jī)識別的Web服務(wù)關(guān)聯(liá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)知識，在給定的背景下確定該背景的概念格有很多方法.文獻(xiàn)[6]提出了Web服務(wù)形式背景WsK(Gws,Msg, K)下構(gòu)造出相應(yīng)該的概念格的方法，該方法給出了Web服務(wù)形式背景WsK(Gws,Msg, K)的相關(guān)知識，該形式背景只表示了消息與Web服務(wù)之間的關(guān)系，但是不能清楚的反應(yīng)出輸入消息、Web服務(wù)和返回消息之間的關(guān)系.因此，就把Web服務(wù)形式背景WsK(Gws,Msg, K)分解再定義成兩個形式背景：input-WsK和output-WsK.再針對這兩個形式背景：input-WsK和output-WsK分別構(gòu)造輸入消息服務(wù)格input-WsK和輸出消息服務(wù)格output-WsK.由此可見，要確定概念格尋找形式概念是關(guān)鍵，而尋找形式概念是可以在形式背景的背景圖Gk中查找所有的最大完全二部圖來實(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) (對象擴(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) .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表2 TOutput_WsL表

表3 TWSSI表

表3 TWSSI表

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

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

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

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

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

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

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

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

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

WSSI的實(shí)驗(yàn)分析將采用與基于Web服務(wù)圖測試系統(tǒng)(WSG Test Platform)[7]相同的實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)數(shù)據(jù)，并通過對相同的服務(wù)請求在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注冊中心隨機(jī)抽取9個Web服務(wù)數(shù)據(jù)集，每個服務(wù)集總數(shù)分別為：300、600、900、1200、1600、2000、2400、2700、3000，在每個服務(wù)集上數(shù)據(jù)集上隨機(jī)選擇30個服務(wù)組成的服務(wù)流E-workflow[8]請求.實(shí)驗(yàn)結(jié)果如圖7所示.

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

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

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

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

從結(jié)果可以看出，WSSI存在以下優(yōu)勢：WSSI與WSG的構(gòu)建方法相比，WSSI的頂點(diǎn)不是單個的Web服務(wù)，而是同類的Web服務(wù)集，其構(gòu)造過程轉(zhuǎn)換為對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)時間，隨著服務(wù)數(shù)量越多，速度明顯提高.

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

4 總結(jié)

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