基于興趣聚類的網(wǎng)格資源發(fā)現(xiàn)算法

摘要：為了更有效地解決網(wǎng)格資源的搜索和定位問題，提出一種以P2P形式實現(xiàn)的、基于興趣聚類的非集中式網(wǎng)格資源發(fā)現(xiàn)算法。算法采用被動學(xué)習(xí)方式，通過用戶的訪問歷史抽取節(jié)點的興趣屬性，將節(jié)點按照興趣屬性劃分為多個簇，資源發(fā)現(xiàn)請求在簇內(nèi)朋友節(jié)點之間傳播，查找失敗后，將請求路由到與其興趣最相似的其他簇內(nèi)。仿真測試表明，算法穩(wěn)定高效，相比傳統(tǒng)算法在低開銷情況下性能有顯著的提高。

關(guān)鍵詞：網(wǎng)格；資源發(fā)現(xiàn)；興趣聚類；相似度

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2007)11-0274-04

0引言

隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展和應(yīng)用，網(wǎng)格技術(shù)已成為近年來分布式計算領(lǐng)域中的一個研究熱點。網(wǎng)格能使用戶共享和訪問廣域網(wǎng)中多種類型的大量資源，并且具有動態(tài)性、異構(gòu)性、自治性等特點。在網(wǎng)格環(huán)境中如何快速有效地進行資源定位，同時降低網(wǎng)絡(luò)帶寬消耗，保證系統(tǒng)的可擴展性和容錯性，是一個關(guān)鍵問題。

基于P2P形式的網(wǎng)格中所有節(jié)點都是對等的，節(jié)點具有相同的責(zé)任和能力，通過直接互連實現(xiàn)資源和服務(wù)的全面共享。目前，在網(wǎng)格資源的查找效率和可擴展性方面展開了許多工作，當前的一些廣域分布式系統(tǒng)對研究資源發(fā)現(xiàn)機制具有重要的借鑒意義，其中最流行的應(yīng)用是非結(jié)構(gòu)化P2P環(huán)境下的資源共享。Gnutella[1]采用廣播式發(fā)送和轉(zhuǎn)發(fā)查詢請求，其查全率和查準率高且具有魯棒性，但訪問節(jié)點多，占用大量帶寬，可擴展性差。文獻[2]中，查詢者生成k個查詢消息，在節(jié)點之間依次轉(zhuǎn)發(fā)傳遞，這樣的每個消息被稱為walker，搜索算法稱為random walks。Random walks占用網(wǎng)絡(luò)帶寬少，但查詢結(jié)果差，且隨意性強。以上的搜索機制在選擇搜索路徑時都沒有采用較好的選擇策略。如果事先能夠判斷哪些節(jié)點更有可能包含符合檢索的資源，區(qū)分選擇最有可能滿足查詢的節(jié)點進行轉(zhuǎn)發(fā)，則必將提高網(wǎng)絡(luò)的搜索效率。

當前有許多工作著重于提高查詢消息的轉(zhuǎn)發(fā)效率，即依據(jù)自身已有的鄰居節(jié)點信息和資源信息，有區(qū)別地選擇最有可能滿足查詢的節(jié)點進行轉(zhuǎn)發(fā)查詢。文獻[3]根據(jù)power－law拓撲，總是選擇具有最大度的節(jié)點進行轉(zhuǎn)發(fā)。文獻[4]首先根據(jù)一定的標準判斷兩個查詢的相似性，然后轉(zhuǎn)發(fā)給最近滿足相似查詢的鄰居節(jié)點。文獻[5]通過增加路由表中資源狀態(tài)與路由方向的關(guān)聯(lián)度，有效提高了用戶資源請求被轉(zhuǎn)發(fā)到可滿足資源的概率。但總的來說，這些工作都只是為了快速發(fā)現(xiàn)目標資源，未能對資源進行有效的組織，可能會導(dǎo)致大量的網(wǎng)絡(luò)開銷。

研究發(fā)現(xiàn)，網(wǎng)格中對等和動態(tài)變化性與現(xiàn)實世界中的社會具有一定的相似性[6]。每個節(jié)點的使用者都具有一定的興趣和愛好，如果兩個節(jié)點具有相同或相似的興趣愛好，則它們很有可能會進行連接和資源互換，這些節(jié)點往往呈現(xiàn)出興趣聚類的特征。無結(jié)構(gòu)P2P網(wǎng)絡(luò)中優(yōu)化搜索的一個基本思路是將用戶按照興趣分類，搜索限制在相關(guān)類別內(nèi)傳播，這樣可以大幅度提高搜索的成功率，降低搜索開銷。

本文提出的網(wǎng)格資源發(fā)現(xiàn)算法ICDiscovery（interest－clustering based grid resource discovery），通過用戶的訪問歷史抽取節(jié)點的興趣屬性，將網(wǎng)格中的節(jié)點按照興趣關(guān)系進行劃分和聚類，形成若干個興趣簇。資源搜索請求首先在簇內(nèi)進行轉(zhuǎn)發(fā)，如果查找失敗，則將請求轉(zhuǎn)發(fā)到與其興趣最相似的其他簇內(nèi)。查詢范圍從網(wǎng)絡(luò)中的所有節(jié)點數(shù)降低到簇內(nèi)的節(jié)點數(shù)，提高了網(wǎng)絡(luò)的魯棒性和擴展性。模擬實驗表明，該算法以其高成功率、低帶寬消耗和很小的響應(yīng)時間顯著提高了搜索性能，而且對用戶的訪問行為體現(xiàn)出良好的適應(yīng)性。

1興趣簇劃分策略

1．1Small－world網(wǎng)絡(luò)基本原理

著名的Stanley Milgram實驗發(fā)現(xiàn)，通過平均六人次的熟人傳遞就可以把社會中任意兩個人聯(lián)系起來，這種現(xiàn)象稱為small－world現(xiàn)象。目前對于small－world的一個較為合理的解釋是，若網(wǎng)絡(luò)中兩點間的平均距離L隨網(wǎng)絡(luò)規(guī)模大小（節(jié)點數(shù)N）呈對數(shù)增長，則當節(jié)點數(shù)增加很快，網(wǎng)絡(luò)呈現(xiàn)某種拓撲結(jié)構(gòu)時，L變化相對緩慢，僅利用局部信息就可以有效地找到短鏈。這個發(fā)現(xiàn)為分布式信息查找提供了契機。

將網(wǎng)絡(luò)拓撲看做一個無向隨機圖，它由若干個節(jié)點及兩兩節(jié)點之間的邊組成，某個節(jié)點的度即為到達該節(jié)點的邊的條數(shù)。本文給出如下定義：

定義1聚集度。已知以定點v為根，深度為l的BFS（breadth first search）樹，則該頂點的橫向邊的數(shù)目Cv滿足關(guān)系：max(Cv)=C2k-(k-1)，k為BFS樹的所有頂點，則一個圖的聚集度為其所有頂點v的Cv值的平均值，即C(l)=average(Cv)。

定義2特征路徑長。已知一個無向圖G，任意兩點(u，v)間最短路徑的邊數(shù)為num(u，v)，則其特征路徑長為L=average[num(u，v)]，即某網(wǎng)絡(luò)的特征路徑長L定義為所有任意兩點間最短路徑的邊數(shù)的平均值。

Small－world網(wǎng)絡(luò)有兩個特點：任意兩個節(jié)點間的特征路徑短；聚集系數(shù)大。前者表明借助small－world查找只有很小的網(wǎng)絡(luò)延遲；后者表明借助網(wǎng)絡(luò)可以指引節(jié)點快速發(fā)現(xiàn)最短路徑。

1．2構(gòu)造基于small－world的興趣簇

筆者提出一種非結(jié)構(gòu)網(wǎng)絡(luò)環(huán)境下的被動興趣相似度學(xué)習(xí)算法，通過用戶的訪問歷史抽取節(jié)點的興趣屬性來作為中間學(xué)習(xí)結(jié)果；把整個網(wǎng)絡(luò)中分布的節(jié)點按照興趣關(guān)系劃分為若干個區(qū)域，使興趣相近的節(jié)點在網(wǎng)絡(luò)中比較接近。其算法描述如下：

a）原始節(jié)點在底層網(wǎng)絡(luò)中廣播自己的搜索請求。

b）如果某個資源節(jié)點滿足節(jié)點查詢請求，那么就創(chuàng)建一條本節(jié)點到資源節(jié)點的虛擬連接，虛擬連接間接地表明了兩個節(jié)點的訪問興趣相同或相近。

c）具有相同興趣的節(jié)點逐漸聚集成一個聯(lián)系緊密的簇。

將每個興趣簇中的路由交換節(jié)點作為簇節(jié)點，負責(zé)引導(dǎo)節(jié)點加入網(wǎng)絡(luò)和轉(zhuǎn)發(fā)消息路由。每個簇擁有一個系統(tǒng)分配的聚類中心，它是聚集度最高的簇節(jié)點。聚類中心就是該簇的出入口，負責(zé)簇內(nèi)節(jié)點的管理，外界節(jié)點通過聚類中心獲取簇中節(jié)點的興趣屬性。將每一簇看做一個興趣。

將聚類中心進行連接構(gòu)成了系統(tǒng)模型的主干網(wǎng)絡(luò)。這樣系統(tǒng)中就形成了兩層網(wǎng)絡(luò)體系結(jié)構(gòu)：上層是由各個聚類中心組成的索引網(wǎng)絡(luò)，下層是由資源節(jié)點組成的P2P網(wǎng)絡(luò)。上層索引網(wǎng)絡(luò)將各個簇串聯(lián)起來，建立可索引結(jié)構(gòu)，如圖1所示。聚類中心節(jié)點保存著相鄰簇的中心節(jié)點的信息。

根據(jù)網(wǎng)絡(luò)模型形成的small－world和冪規(guī)律特征，對資源的定位與搜索將主要通過簇節(jié)點進行。搜索請求充分利用簇節(jié)點的路由表信息，在相應(yīng)簇內(nèi)的朋友節(jié)點之間進行轉(zhuǎn)發(fā)，使得資源定位不再以盲目擴散方式進行，從根本上改善了定位搜索效率和網(wǎng)絡(luò)的可擴展性。

2基于興趣聚類的網(wǎng)格資源發(fā)現(xiàn)算法

2．1興趣相似性度量

本體（ontology）是描述概念及概念之間關(guān)系的概率模型，通過概念分析和建模，把現(xiàn)實世界中的本體抽象為一組概念和概念之間的關(guān)系。定義本體為一棵IS－A樹來表示用戶興趣。本體樹中每個節(jié)點表示一個獨立的概念，子節(jié)點是父節(jié)點的一個子概念。一條從根節(jié)點到任一非根節(jié)點的路徑，代表在語義概念上逐步細化的過程。

由于節(jié)點的興趣都是動態(tài)的，而且隨機變化，使用概率樹來表示用戶興趣的概率分布。概率樹是一種用來揭示具有層次結(jié)構(gòu)的本體隨機輸出的數(shù)學(xué)結(jié)構(gòu)，如圖2所示。樹的根表示為興趣本體的初始隨機變量，父節(jié)點的子節(jié)點表示父節(jié)點的隨機輸出，子節(jié)點本身也是作為其下一層概率樹的父節(jié)點，作為子樹的初始隨機變量。

圖2所示的概率樹語義上的意義為：用戶A對資源B的興趣概率為0.8，對資源C的興趣概率為0.2。在給定資源B的情況下，用戶對資源B的子類D的興趣概率為0.9，對子類E的興趣概率為0.1。在給定資源C的情況下，用戶對資源C的子類F和G有興趣的概率均為0.5。而且還有如下規(guī)則：

a）概率樹中如果存在從節(jié)點X到節(jié)點Y之間的有向通路，則從X到Y(jié)之間的概率為有向通路上的所有有向邊的概率乘積。

b）如果概率樹中不存在從節(jié)點X到節(jié)點Y之間的有向通路，則從X到Y(jié)之間的概率P(Y|X)=0。

簇內(nèi)節(jié)點定期將其興趣屬性和訪問頻率發(fā)送給聚類中心節(jié)點。中心節(jié)點統(tǒng)計本簇各興趣屬性的資源訪問頻率的分布情況和節(jié)點數(shù)量，獲取節(jié)點滿足各種查詢的概率指標，形成本簇的興趣概率樹。相鄰簇的中心節(jié)點定期同步數(shù)據(jù)，并分析節(jié)點興趣屬性與滿足查詢概率之間的關(guān)系，設(shè)計相應(yīng)的消息轉(zhuǎn)發(fā)策略。

2．2簇節(jié)點信息表的構(gòu)建

將各個簇節(jié)點與聚集在其周圍的對等節(jié)點抽象為一個統(tǒng)一的共享資源對等節(jié)點，與簇內(nèi)其他的簇節(jié)點形成對等連接關(guān)系。每個簇節(jié)點都保存著一張路由表，分為本地信息索引表LI（local index）和鄰居信息索引表NI（neighbor index）兩部分。LI表中記錄共享資源對等節(jié)點的興趣屬性和資源索引；NI表中記錄相鄰的共享資源對等節(jié)點興趣屬性和資源索引。對資源的定位與搜索將主要通過查詢簇節(jié)點的路由表信息進行。每個簇節(jié)點將自己擁有的信息周期性地預(yù)路由到自己的鄰居節(jié)點上去，這個過程通過廣播的方式實現(xiàn)，據(jù)此刷新其鄰居信息索引表NI。利用預(yù)路由策略可以很好地通過減少跳數(shù)來縮短查詢時間，減少搜索時廣播方式帶來的巨大消息查詢請求。

2．3資源發(fā)現(xiàn)路由

相關(guān)研究證明，路由節(jié)點的轉(zhuǎn)發(fā)能力（處理速度和轉(zhuǎn)發(fā)帶寬）越強，經(jīng)該節(jié)點轉(zhuǎn)發(fā)的流量就越多，因而其聚集度也越來越高。聚集度高的節(jié)點與其他節(jié)點的聯(lián)系比較多，通過它查找待查資源的概率也比較高。本文按照優(yōu)先查找節(jié)點所在興趣聚類的原則，采用最大聚集度優(yōu)先[9]的方法將資源請求消息在簇內(nèi)進行轉(zhuǎn)發(fā)。如果查找請求不能被滿足，則返回到上層索引網(wǎng)絡(luò)，計算相鄰簇中心節(jié)點之間的興趣相似度，進行語義對比，將資源請求路由到與其興趣最相似的興趣簇內(nèi)。其具體算法步驟如下：

a）將節(jié)點的資源請求（query）發(fā)送給與其相連的簇節(jié)點，分析得出查詢內(nèi)容的興趣值，查找本地信息索引表LI。若存在匹配的興趣屬性，則將查詢請求轉(zhuǎn)發(fā)給相應(yīng)的資源節(jié)點，返回一個查詢命中包（queryHit）。如果請求在共享資源對等節(jié)點內(nèi)不能被滿足，則執(zhí)行b）。

b）簇節(jié)點通過查詢鄰居信息索引表NI，將資源請求轉(zhuǎn)發(fā)到相鄰的聚集度最高的簇節(jié)點，按照a）的方法進行查找。如果查找失敗，按照同樣的方法尋找聚集度次高的簇節(jié)點，進行查詢信息的轉(zhuǎn)發(fā)，直到資源查找請求遍布到本簇所有的簇節(jié)點；若仍未命中，則轉(zhuǎn)至c），進行簇間查找。

c）首先查詢中心節(jié)點的鄰居信息索引表NI，獲得鄰居中心節(jié)點的興趣概率樹，應(yīng)用式（2）計算query與各個鄰居中心節(jié)點的興趣概率樹的KL距離，比較得出與query最相似的興趣簇，轉(zhuǎn)發(fā)該請求。若在該簇內(nèi)命中，返回queryHit信息。否則，繼續(xù)按照以上方法進行相鄰簇間的查找，直到TTL減為0，查找結(jié)束。

根據(jù)簇的形成過程特征，每個節(jié)點掌握著大量的簇內(nèi)節(jié)點興趣屬性信息，節(jié)點間有很大的相識系數(shù)。因此，在簇內(nèi)部找到滿足請求的資源的概率很大，節(jié)點出現(xiàn)跨簇查找的概率很小。資源查找一般都能在前兩個步驟內(nèi)完成，查找范圍也從網(wǎng)絡(luò)中的所有節(jié)點降低到簇內(nèi)的節(jié)點數(shù)，減小了遠距離交互的節(jié)點數(shù)目，有效防止了請求洪。

算法基于本體距離和興趣相似度來衡量相鄰簇中的節(jié)點與查詢間的語義相關(guān)程度，即能滿足查詢的概率。因此本文的資源發(fā)現(xiàn)算法適合節(jié)點對任意主題內(nèi)容的資源進行查找，具有自適應(yīng)性。

3性能評估與模擬實驗

本文的仿真實驗采用MIT基于Java的主動網(wǎng)絡(luò)協(xié)議開發(fā)工具ANTS，拓撲結(jié)構(gòu)通過Internet拓撲模擬工具BRITE（Boston university representative Internet topology generator）產(chǎn)生，拓撲節(jié)點分布滿足small－world網(wǎng)絡(luò)和冪規(guī)律特征，實現(xiàn)了主動P2P協(xié)議代理。網(wǎng)格規(guī)模定為N=103個節(jié)點，每個簇中的節(jié)點數(shù)為N=40，網(wǎng)格系統(tǒng)中簇的個數(shù)為N/M=25（假設(shè)每個簇中的節(jié)點數(shù)相同）。同時假設(shè)每個節(jié)點提供相同數(shù)量的資源，每種資源在網(wǎng)格系統(tǒng)中的數(shù)量相同，這樣保證了資源在網(wǎng)格中的均勻分布。

筆者對比了本文提出的資源搜索方案ICDiscovery與Gnutella中采用五個隨機步的搜索方案（random walks），終止條件都設(shè)置為TTL=8。系統(tǒng)中所有節(jié)點使用有20個子類的標準興趣本體，隨機生成每個節(jié)點的興趣概率樹。為了簡化實驗，假設(shè)概率樹不變。

3．1搜索成功率

搜索成功率表示成功搜索的比例。在本文基于興趣聚類的網(wǎng)格模型中，初始節(jié)點之間沒有任何朋友關(guān)系，只能通過廣播的方式發(fā)現(xiàn)自己所需的資源。隨著時間的增長，節(jié)點間通過不斷學(xué)習(xí)，形成了比較穩(wěn)定的興趣聚類。路由查找算法采用 最大聚集度優(yōu)先和最大相似度優(yōu)先的策略，比采用random walks更具有優(yōu)越性。從圖3中可以看出，ICDiscovery算法的平均搜索成功率可以達到85%左右，高出random walks方案的50%約25個百分點。使用random walks進行資源搜索的成功率始終不高，而且不是十分穩(wěn)定。

3．2平均搜索開銷

搜索開銷表示搜索涉及的平均節(jié)點總數(shù)，該指標一定程度上代表了搜索的計算開銷和消息開銷。應(yīng)用ICDiscovery算法進行資源查找時，節(jié)點首先將搜索請求發(fā)送給自己的朋友節(jié)點，查詢范圍從網(wǎng)絡(luò)中的所有節(jié)點數(shù)降低到簇內(nèi)的節(jié)點數(shù)，大幅度減小了搜索開銷。圖4中比較了兩個搜索方案的平均搜索開銷。

在返回消息數(shù)目相同的情況下，ICDiscovery的搜索開銷要比random walks低得多。隨著返回消息數(shù)目的增加，這種差距會越來越明顯。如果增加每個簇中朋友節(jié)點的數(shù)量，算法性能還會進一步提高。

3．3平均路徑長度

本文提出的資源發(fā)現(xiàn)策略中，搜索請求不再采用盲目擴散的方式，每一步僅轉(zhuǎn)發(fā)到一個最可能滿足的節(jié)點。仿真實驗結(jié)果表明，該算法平均資源定位路徑長度為2.3，小于使用random walks的平均路徑長度4.9。由此可見，將大規(guī)模節(jié)點在邏輯上劃分為小區(qū)域，由大規(guī)模的網(wǎng)絡(luò)消息擴散變?yōu)榇貎?nèi)小規(guī)模擴散，顯著減少了資源查找的平均路徑長度。

4結(jié)束語

本文針對網(wǎng)格資源的查找和定位問題進行研究，提出了基于small－world模型和興趣聚類的網(wǎng)格資源發(fā)現(xiàn)算法ICDisco－very。將網(wǎng)格空間的節(jié)點按照興趣屬性分為多個簇，搜索請求在簇內(nèi)傳播，節(jié)點出現(xiàn)跨簇請求的概率很小。查詢范圍從網(wǎng)絡(luò)中的所有節(jié)點數(shù)降低到簇內(nèi)的節(jié)點數(shù)，大大減輕了網(wǎng)絡(luò)的壓力，有效地防止了請求洪，提高了網(wǎng)絡(luò)的魯棒性和擴展性，使其具有更高的性能指標。仿真測試表明，ICDiscovery算法穩(wěn)定高效，具有良好的搜索效率和可擴展性。

參考文獻：

［1］

Gnutella website［EB/OL］. [2006-08-28].http://gnutella.wego.com/.

［2］LV Qin，CAO Pei， COHEN E，et al.Search and replication in unstructured peer－to－peer networks[C]//Proc of International Confe－rence on Supercomputing.New York:ACM Press，2002:110－114.

［3］ADAMIC L A，LUKOSE R M，PUNIYANI A R，et al.Search in power－law networks［J］.Physical Review，2001，E64(46135):719-720.

［4］REN Yi，SHA Cao－feng，QIAN Wei－ning，et al.Explore the \"small world phenomena\" in pure P2P information sharing systems[C]//Proc of the 3rd Int’l Symp on Cluster Computing and the Grid.Wa－shington D C:IEEE Computer Society， 2003:232-239.

[5]GONG Yi－li，LI Wei，SUN Yu－zhong，et al.A C/S and P2P hybrid resource discovery framework in grid environments［C］//Proc of International Conference on Parallel Processing.Washington D C:IEEE Computer Society， 2005:261-268.

[6]ADRIANA I，MATEI R，IAN F.Locating data in (small－world) peer－to－peer scientific collaborations［C］//Proc of the 1st International Workshop on Peer－to－Peer Systems.Berlin:Springer－Verlag，2002:232-241.

[7]WATTS D J，DODDS P S，NEWMAN M E J.Identity and search in social networks［J］. Science，2002，296(5571) :1302－1305.

[8]薛廣濤，賀小箭，賈兆慶，等. 使用興趣子網(wǎng)劃分算法對Gnutella中資源定位機制的改進［J］. 上海交通大學(xué)學(xué)報，2004，38(12):2109-2110.

[9]黃道穎，黃建華，莊雷，等.基于主動網(wǎng)絡(luò)的分布式P2P網(wǎng)絡(luò)模型［J］. 軟件學(xué)報，2004，15(7) :1084－1085.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”