一種基于語義的分布式云服務(wù)發(fā)現(xiàn)方法*

王文豐，韓龍哲，李沛武，李嵐，劉天元

(1. 江西省水信息協(xié)同感知與智能處理重點實驗室∥南昌工程學(xué)院， 江西 南昌 330099； 2. 南昌工程學(xué)院信息工程學(xué)院，江西 南昌 330099； 3. 南昌大學(xué)軟件學(xué)院，江西 南昌 330047)

云服務(wù)是面向云計算提供的一系列服務(wù)程序，它可以為云計算用戶解決其想要解決的問題。隨著云服務(wù)的普及，云服務(wù)提供者便應(yīng)運而生。云服務(wù)提供者能夠讓用戶挑選出自己滿意的云服務(wù)，但云服務(wù)的挑選過程卻是相當費時和費力的[1]。因云服務(wù)規(guī)范是異構(gòu)和非標準化的，導(dǎo)致了語義互操作性問題。此外，用戶對云服務(wù)的QoS保證要求更加嚴格。因此，云服務(wù)技術(shù)的難點在于如何發(fā)布最有效且具有低成本的服務(wù)，而又能保證最佳的服務(wù)質(zhì)量。向云用戶提供令人滿意的服務(wù)，是高可擴展的服務(wù)發(fā)現(xiàn)技術(shù)的根本。對于云服務(wù)發(fā)現(xiàn)，一個難點就是服務(wù)消費者的定位服務(wù)，尤其是當該服務(wù)獨立發(fā)布的時候[2]。

在這種情況下，服務(wù)發(fā)現(xiàn)成功的關(guān)鍵是可用性、可訪問性的有效服務(wù)注冊。由于集中服務(wù)注冊方法會存在單點失效、網(wǎng)絡(luò)擁堵和性能瓶頸等問題，P2P網(wǎng)絡(luò)必須探索一種有效的服務(wù)發(fā)現(xiàn)機制[3]。P2P的容錯性和可擴展性解決了云環(huán)境中服務(wù)發(fā)現(xiàn)問題；同時，隨著云服務(wù)的發(fā)展，分布式服務(wù)注冊也促進了P2P的可擴展性和容錯性發(fā)展。在P2P系統(tǒng)中，研究人員已經(jīng)對目前主流的服務(wù)發(fā)現(xiàn)技術(shù)進行了一定的研究[4]。研究發(fā)現(xiàn)，在基于分布式的結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)中發(fā)布和查詢服務(wù)可以解決集中式注冊的問題[5]，這是因為在結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)中存在一個分布式哈希表，它能夠支持關(guān)鍵字的存儲和檢索，如put(key, value)和get(key)操作。因此，結(jié)構(gòu)化P2P覆蓋網(wǎng)中的用戶能夠更加有效地發(fā)現(xiàn)服務(wù)，并且發(fā)現(xiàn)服務(wù)的時間也可以減少到O(logn)。然而結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)也存在一個缺點，即它只支持精確匹配的查詢，而且維護其拓撲結(jié)構(gòu)也是需要相當大的開銷。如對等點和服務(wù)經(jīng)常會頻繁地加入和退出，占據(jù)了系統(tǒng)很大的開銷[6]。另外，由于云服務(wù)描述沒有任何標準格式，所以精確匹配的查詢方式可能無法查詢到相關(guān)的所有服務(wù)。與結(jié)構(gòu)化P2P相比，非結(jié)構(gòu)化P2P模型可以更好地模擬現(xiàn)實世界的問題。在非結(jié)構(gòu)化P2P系統(tǒng)中，對等點加入時不需要事先了解它的拓撲結(jié)構(gòu)[5]。非結(jié)構(gòu)化P2P系統(tǒng)的拓撲結(jié)構(gòu)存在一定的隨機性[7]，因此非結(jié)構(gòu)化P2P系統(tǒng)的搜索方法不能采用Hash函數(shù)，但它可以采用靈活性的數(shù)據(jù)定位搜索方法并支持非精確搜索。泛洪技術(shù)及其變種[8-10]就是非結(jié)構(gòu)化P2P系統(tǒng)中一種代表性的搜索方法，它被廣泛用于處理非結(jié)構(gòu)化P2P系統(tǒng)中的消息路由。然而非結(jié)構(gòu)化P2P系統(tǒng)也存在一個主要的缺點，即如果對等點之間的聯(lián)系經(jīng)常改變，在本地索引存儲的統(tǒng)計數(shù)據(jù)就會變得無效。為了克服結(jié)構(gòu)化和非結(jié)構(gòu)化P2P系統(tǒng)中的缺點，語義覆蓋網(wǎng)絡(luò)便應(yīng)運而生。在語義覆蓋網(wǎng)絡(luò)中，相似的對等點之間建立語義邊，以提高搜索精度，改善搜索結(jié)果[11]。語義覆蓋網(wǎng)絡(luò)是一種語義相關(guān)對等點相連的虛擬網(wǎng)絡(luò)，通過集成語義，可以提供更有效的多維查詢[12-15]。

語義覆蓋網(wǎng)絡(luò)(SONs)[11]提高了P2P系統(tǒng)的搜索質(zhì)量，在語義覆蓋網(wǎng)絡(luò)中，把服務(wù)描述相似的對等點組織在一起，提供一組服務(wù)描述，以確保服務(wù)發(fā)現(xiàn)的成功。因此，在搜索時查詢只需轉(zhuǎn)發(fā)到相應(yīng)的對等點即可，從而減少了通信開銷，提高了成功率。本文旨在探討云服務(wù)發(fā)現(xiàn)方法，通過探索云本體(cloud ontology, CO)來描述云服務(wù)，提高語義覆蓋網(wǎng)絡(luò)的服務(wù)發(fā)現(xiàn)成功率。同時，本文也研究了使用語義覆蓋網(wǎng)絡(luò)在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中高效轉(zhuǎn)發(fā)查詢機制。本文提出了基于語義覆蓋網(wǎng)絡(luò)的服務(wù)發(fā)現(xiàn)方法(SD-CSR)，該具有良好的可擴展性和適應(yīng)性。由于它的分布式特性，所以在服務(wù)發(fā)現(xiàn)過程中，對等點只考慮其本地信息和它的鄰居信息。并根據(jù)對等點之間的相似性，利用語義描述的服務(wù)來計算這種相似性。

1 基于語義的分布式云服務(wù)發(fā)現(xiàn)方法

一般地，云本體是利用網(wǎng)絡(luò)中的所有對等點來存儲和檢索的云服務(wù)描述。云本體CO由云概念C= {C1,C2,C3, ,Cn}組成，其中包括n個概念和與這些概念有關(guān)的聯(lián)系。服務(wù)注冊根據(jù)不同的服務(wù)類別分散到各個區(qū)域中，每個區(qū)域保持本地本體的副本。用戶查詢被轉(zhuǎn)發(fā)到最相關(guān)的區(qū)域，由能力表添加到每個區(qū)域。能力表中保存了服務(wù)類別的興趣點。

1.1 對等點聚類

為了減少查詢處理時間和網(wǎng)絡(luò)流量，提出了聚類服務(wù)的概念，它產(chǎn)生于基于語義描述的每個區(qū)域[11]。在本文中，用本體論的概念作為對等聚類的基礎(chǔ)。具有語義描述服務(wù)的對等點，最初聚集到一些代表不同層次服務(wù)集的固定簇數(shù)Ci(1≤i≤m)中。隨后，每個區(qū)域都存在對等點的簇。一個服務(wù)描述D由以下部分組成：類別、服務(wù)描述屬性、供應(yīng)商信息和QoS，可以表示為D= {CCi,SD_Attributes,Provider_info,QoS_facets}。其中，CCi∈Service_category_class。每個集群管理節(jié)點中存在一個集群信息表{Peer_id,current_status,last_update_info}，它表示集群注冊的云服務(wù)，并構(gòu)建集群內(nèi)和集群之間的路由。集群管理節(jié)點還保存另外一個表，稱為鄰居集群表。它提供了另一個相關(guān)集群中對等點的信息，該信息與該集群中的對等點具有語義相似性。該表用一個三元組{neighbor_cluster_manager_id,neighbor_peer_id,stauts}表示，它保留了一組集群描述(CD)，CD包括了簇標識符Ci、屬性向量Ai，屬于集群的對等點{P}和集群M，例如：CDi=(Ci,Ai, {P},M)。而，M中的對等點作為每個集群的質(zhì)心。

1.2 語義覆蓋網(wǎng)絡(luò)的創(chuàng)建與維護

在集群中，可以通過查找語義相關(guān)的對等點來降低查詢成本，并提高服務(wù)發(fā)現(xiàn)的質(zhì)量。一般情況下，其他集群的對等點可以提供相應(yīng)的響應(yīng)服務(wù)請求。由于其他集群的對等節(jié)點能夠提供相應(yīng)的響應(yīng)服務(wù)請求，因此在語義覆蓋網(wǎng)絡(luò)中，可以很方便地查詢所有相關(guān)的對等點，并保證簇間的連通性，從而實現(xiàn)每個對等點獲得其鄰居的信息。對等點保持兩種與鄰居相連的語義邊：① 內(nèi)部節(jié)點的語義邊：連接屬于同一個群集內(nèi)的對等點；② 外部節(jié)點的語義邊：連接屬于不同集群的對等點，實現(xiàn)語義可達節(jié)點之間的語義聯(lián)系。特別地，內(nèi)部對等語義邊涉及在同一集群上發(fā)布的一對類似服務(wù)。內(nèi)部對等邊定義為元組{peer_id,semantic_similarity,status,time}。外部對等邊定義為元組{cluster_id,neighbor_peer,semantic_similarity,status,time}。這里，鏈接的對等點被稱為語義鄰居。一個對等的語義邊連接著一個本地服務(wù)與對等的語義鄰居上發(fā)布的服務(wù)。一個對等點Pi是對等點Pj面向服務(wù)描述Si的語義鄰居，如果對等點Pj有一個服務(wù)描述Sj，則Si和Sj通過對等點間的語義連接。在任意兩個對等點間存在以下四種關(guān)系：

(1)精確：兩個對等點提供相同的功能。如，sim(Px,Py)=1。

(2)延伸：一個對等點提供額外的功能給其他對等點。如，sim(Px,Py)∈(0, 1)，如果S1提供了額外的功能給S2，則S1延伸S2。

(3)相交：在對等點提供的功能之間存在一個非空的交集(重疊)。如，sim(Px,Py)∈(0, 1)。

(4)失配：沒有共同之處。如，sim(Px,Py)=0。每個區(qū)域都可以表示為一個元組(C,P,LL,NL)，其中C= {c1, .,cn}是一組有限的集群，每個集群是一組有限的自治節(jié)點P。LL?P×P是一組本地邊的集合，每條邊(Pi,Pj)∈LL表示同一集群內(nèi)的對等點Pi和Pj之間存在直接連接。NL?P×P是一組鄰居邊的集合，其中每條邊(Pi,Pj)∈NL表示不同集群內(nèi)的對等點Pi和Pj之間存在間接連接。圖1給出了一個區(qū)域的元素。

圖1 區(qū)域的元素Fig.1 Elements of zone

外部語義邊根據(jù)探測請求的答復(fù)情況進行連接，如果對等點Px發(fā)送到Py一定數(shù)量的探測請求沒有應(yīng)答，則認為語義鄰居Py是不可達的。在這種情況下，移除連接Px和Py的外部邊。發(fā)布/取消服務(wù)就是采用類似的方式進行管理的。表1展示了對等點內(nèi)部邊的建立過程，表2則顯示了對等點外部邊的建立過程。

表1 對等點內(nèi)部邊的發(fā)現(xiàn)算法Table 1 Algorithm of intra-peer link discovery of peer

表2 對等點外部邊的發(fā)現(xiàn)算法Table 2 Algorithm of inter-peer link discovery of peer

在語義覆蓋網(wǎng)絡(luò)有效地創(chuàng)建后，主要關(guān)心如何利用他們在規(guī)定時間內(nèi)提高搜索性能。獲取滿足用戶請求的一組服務(wù)的過程稱為服務(wù)發(fā)現(xiàn)。服務(wù)請求被發(fā)送到區(qū)域管理器能力表上。它是對發(fā)布在集群上的語義服務(wù)接口進行匹配和轉(zhuǎn)發(fā)給潛在的集群Cx的服務(wù)描述進行查詢。內(nèi)部節(jié)點的語義邊在對等點Px∈Cx上匹配服務(wù)描述的請求，用來修剪相關(guān)服務(wù)集和減輕服務(wù)比較的數(shù)量。外部對等語義邊用于轉(zhuǎn)發(fā)請求給遠程相關(guān)的語義鄰居對等點Px。在這種方式中，只有相關(guān)的節(jié)點進行并行搜索，從而減少網(wǎng)絡(luò)擁堵和尋找的服務(wù)時間。表3和表4分別顯示了對等點內(nèi)部語義邊和外部語義邊的建立過程。

在表5的算法中，當發(fā)現(xiàn)滿足請求的服務(wù)后才停止搜索，而請求轉(zhuǎn)發(fā)到語義鄰居實現(xiàn)相應(yīng)的服務(wù)。重復(fù)這一過程直到：1)沒有其他對等點的請求可以被傳播；2)請求消息的生存時間(Time-To-Live)下降為零。區(qū)域管理器為每個服務(wù)請求分配一個唯一標識符和時間。為了避免重復(fù)請求的泛濫，每當對等點收到請求時，它會將服務(wù)標識符存儲在指定的生存時間內(nèi)。已被匹配的群集管理器在TTL時間周期內(nèi)處于封閉狀態(tài)，并將所有相關(guān)服務(wù)的列表轉(zhuǎn)發(fā)給區(qū)域管理器。每個區(qū)域管理器有一個QoS過濾器，以更進一步過濾掉不相關(guān)的服務(wù)。當來自不同群集的一組服務(wù)到達區(qū)域管理器時，它將根據(jù)QoS和信任程度對服務(wù)描述和用戶請求進行第二級篩選。將不同的列表組合成一個列表，其中包含降序排序的服務(wù)，并將結(jié)果提交給用戶。

表3 對等點內(nèi)部語義邊的維護算法Table 3 Algorithm of intra semantic link maintaince of peer

表4 對等點外部語義邊的維護算法Table 4 Algorithm of inter semantic link maintaince of peer

表5 服務(wù)發(fā)現(xiàn)算法Table 5 Algorithm of discovery of services

2 實驗結(jié)果與分析

本節(jié)通過實驗分析SD-CSR方法的基本性能。所有的模擬實驗在模擬器Neurogrid[16]進行，該模擬器隨機生成一個了N個對等點和NS個服務(wù)的P2P網(wǎng)絡(luò)。服務(wù)S1和S2之間的匹配根據(jù)以下概率分布進行設(shè)置：P(S1精確S2)= 5%，P(S1不匹配S2)= 45%，P(S1擴展S2)= 15%，P(S2擴展S1)= 15%和P(S1相交S2)= 20%。為證明本文SD-CSR方法的有效性，我們與Gnutella協(xié)議[17]進行了實驗對比。Gnutella是一個用于分布式搜索和數(shù)字資源共享的協(xié)議，盡管支持傳統(tǒng)的客戶機/服務(wù)器架構(gòu)，但Gnutella協(xié)議是點對點、非中心的模型。為了體現(xiàn)Gnutella協(xié)議的簡單性，采用了一種盲目的搜索機制—洪泛。在該機制中，對等點在TTL時間半徑內(nèi)進行洪泛查詢。

TTL決定了一個查詢可以被轉(zhuǎn)發(fā)到網(wǎng)絡(luò)的最大次數(shù)。TTL值越高，響應(yīng)請求的對等點的數(shù)量就越高。在模擬實驗中，TTL被設(shè)置為1和15之間。設(shè)T∈N+為TTL初始值。如果所有潛在的對等點，提供相關(guān)的服務(wù)在TTL時間內(nèi)不能被導(dǎo)航，結(jié)果就可能不完整。在具有N個對等點的非結(jié)構(gòu)化P2P語義網(wǎng)絡(luò)中，所有相關(guān)服務(wù)匹配的查詢請求能夠通過對等點集P在T內(nèi)被導(dǎo)航。設(shè)v是被轉(zhuǎn)發(fā)到對等點集P中一個對等點的請求概率|P≤T|，則在T內(nèi)到所有相關(guān)節(jié)點的概率(Pt)[18]為：

V|P|·(1-v)j-|P|+V|P|;

otherwise,Pr=0

(1)

在最壞情況下，|P|=T，且對于任意的p∈P，都有一個相關(guān)的服務(wù)匹配查詢，這將產(chǎn)生一個通用下界v(|P|)。命中率是由分布式搜索策略檢索到的服務(wù)數(shù)量的比率，如果所有的服務(wù)都在一個對等節(jié)點上可得。當命中率較高時，分布式搜索將更加成功。命中率取決于TTL值，命中率的結(jié)果如圖2所示。通過設(shè)置TTL參數(shù)的不同值，可以改善命中率；當TTL增大時，命中率值會合理上升。從圖2可以看出，即使在低的TTL值，SD-CSR方法也要優(yōu)于Gnutella。這是因為與對等點的語義聯(lián)系有助于低數(shù)量的請求轉(zhuǎn)發(fā)到潛在的對等點。

圖2 命中率與TTLFig.2 Hit ratio and TTL

召回是現(xiàn)有相關(guān)結(jié)果數(shù)和相關(guān)結(jié)果總數(shù)的比率。圖3顯示了一個召回與不同數(shù)量的服務(wù)返回時的情形。與TTL類似，SD-CSR的召回率明顯高于Gnutella，因為所有潛在的對等點都通過語義邊聚集在同一個語義覆蓋網(wǎng)絡(luò)中。

圖3 召回率分析Fig.3 Analysis of recall ratio

圖4 召回率與TTLFig.4 Recall ratio and TTL

從圖4可以看出，召回率隨著跳數(shù)的增加而上升。當TTL大于7，對SD-CSR系統(tǒng)的召回率均在90%以上，滿足要求。

執(zhí)行時間是用戶接收到請求服務(wù)并進行應(yīng)答所需的時間。分析表明：SD-CSR與Gnutella協(xié)議相比，在執(zhí)行時間上明顯減少；且，Gnutella協(xié)議執(zhí)行時間隨著對等點的數(shù)量呈線性增長。這是因為Gnutella協(xié)議利用的是基本的洪泛算法，執(zhí)行時間較大。如圖5所示，SD-CSR的執(zhí)行時間較小。這是由于語義匹配技術(shù)大大減少了執(zhí)行時間。SD-CSR和Gnutella的效率，如圖6所示。因?qū)Φ赛c基于語義鏈接被聚集到一組中，這樣服務(wù)匹配可以限制到相關(guān)組中，所以SD-CSR可以減少大量的發(fā)現(xiàn)時間。

圖5 執(zhí)行時間比較Fig.5 Comparison of execution time

圖6 執(zhí)行時間和返回服務(wù)的數(shù)量Fig.6 Execution time and number of sevices returned

3 結(jié) 論

如何在分布式和異構(gòu)環(huán)境中發(fā)現(xiàn)云服務(wù)是解決云計算的主要挑戰(zhàn)之一。本文采用語義覆蓋網(wǎng)絡(luò)實現(xiàn)了云服務(wù)發(fā)現(xiàn)的探索性研究，通過分布式服務(wù)注冊表，把服務(wù)定制在基于語義概念和本體共享邊的覆蓋網(wǎng)絡(luò)中,并在對等點間建立語義鏈接，由對等點提供語義豐富的服務(wù)和對等點之間持有類似服務(wù)的鏈接，保證快速探索語義覆蓋網(wǎng)絡(luò)的目標和合法傳播查詢給合適的對等點。最后，利用基于本體的查詢策略，以提高發(fā)現(xiàn)結(jié)果。實驗結(jié)果表明：與Gnutella相比，無論是在發(fā)現(xiàn)過程的性能和效率方面，SD-CSR都具有明顯的優(yōu)勢。