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

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

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

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

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

0引言

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

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

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

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

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

1興趣簇劃分策略

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

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

將網(wǎng)絡(luò)拓?fù)淇醋鲆粋€(gè)無(wú)向隨機(jī)圖，它由若干個(gè)節(jié)點(diǎn)及兩兩節(jié)點(diǎn)之間的邊組成，某個(gè)節(jié)點(diǎn)的度即為到達(dá)該節(jié)點(diǎn)的邊的條數(shù)。本文給出如下定義：

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

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

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

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

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

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

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

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

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

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

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

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

2．1興趣相似性度量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3性能評(píng)估與模擬實(shí)驗(yàn)

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

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

3．1搜索成功率

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

3．2平均搜索開(kāi)銷

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

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

3．3平均路徑長(zhǎng)度

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

4結(jié)束語(yǔ)

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

參考文獻(xià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)劃分算法對(duì)Gnutella中資源定位機(jī)制的改進(jìn)［J］. 上海交通大學(xué)學(xué)報(bào)，2004，38(12):2109-2110.

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

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