基于節(jié)點(diǎn)興趣非結(jié)構(gòu)化P2P網(wǎng)絡(luò)搜索機(jī)制研究

莊 偉

(南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210023)

0 引 言

在互聯(lián)網(wǎng)技術(shù)發(fā)展的初期階段，計(jì)算機(jī)網(wǎng)絡(luò)模型主要是Client/Server(客戶端/服務(wù)器)模式，在這種模式中，由于計(jì)算機(jī)計(jì)算存儲(chǔ)性能均較低，節(jié)點(diǎn)工作主要依賴于中央服務(wù)器。中央服務(wù)器是整個(gè)網(wǎng)絡(luò)的核心部分，是網(wǎng)絡(luò)中資源或者服務(wù)的提供方，這種模式對中央服務(wù)器的要求很高并且使中央服務(wù)器的負(fù)載較大，一般只適用于中小規(guī)模的網(wǎng)絡(luò)。隨著互聯(lián)網(wǎng)技術(shù)、計(jì)算機(jī)存儲(chǔ)能力的快速發(fā)展和網(wǎng)絡(luò)資源的急劇增加，中小規(guī)模的網(wǎng)絡(luò)已經(jīng)不能滿足用戶的需求，用戶對于網(wǎng)絡(luò)技術(shù)的要求也越來越高，在此基礎(chǔ)上，一種新型的P2P對等網(wǎng)絡(luò)應(yīng)運(yùn)而生[1]。P2P網(wǎng)絡(luò)淡化了中央服務(wù)器的概念，P2P網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的地位和作用都是相同的，且每個(gè)節(jié)點(diǎn)既能向其他節(jié)點(diǎn)進(jìn)行資源或者服務(wù)的請求，又可以享受其他節(jié)點(diǎn)提供的服務(wù)。

目前P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可根據(jù)耦合程度分為結(jié)構(gòu)化P2P網(wǎng)絡(luò)[2]和非結(jié)構(gòu)化P2P網(wǎng)絡(luò)[3]。結(jié)構(gòu)化P2P網(wǎng)絡(luò)主要有Tapesrtry[4]、Chord[5]等，網(wǎng)絡(luò)中所有節(jié)點(diǎn)按照某種結(jié)構(gòu)進(jìn)行有序組織形成一種結(jié)構(gòu)規(guī)則的網(wǎng)絡(luò)。每個(gè)節(jié)點(diǎn)只存儲(chǔ)特定的信息或者特定信息的索引，當(dāng)用戶需要在結(jié)構(gòu)化網(wǎng)絡(luò)中搜索信息時(shí)，必須知道這些信息可能存在于哪些節(jié)點(diǎn)中。但結(jié)構(gòu)化P2P網(wǎng)絡(luò)維護(hù)成本較大，并且節(jié)點(diǎn)之間的物理結(jié)構(gòu)比較容易破壞，所以結(jié)構(gòu)化P2P網(wǎng)絡(luò)不適用于大規(guī)模網(wǎng)絡(luò)部署[6]。非結(jié)構(gòu)化P2P網(wǎng)絡(luò)主要有Gnutella[7]等，在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)只存儲(chǔ)自身的信息。當(dāng)用戶需要從非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中搜索信息時(shí)，用戶預(yù)先并不知道該信息存儲(chǔ)在哪些節(jié)點(diǎn)上。非結(jié)構(gòu)化P2P網(wǎng)絡(luò)采用的都是基于洪泛算法的消息傳遞機(jī)制，洪泛算法搜索成功率不高并且在消息傳遞過程中會(huì)產(chǎn)生大量的冗余消息，因此非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中資源的定位和搜索性能的提高是關(guān)鍵問題。

針對非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的搜索問題，文獻(xiàn)[8]提出了洪泛算法。當(dāng)一個(gè)成員節(jié)點(diǎn)請求資源時(shí)，會(huì)向所有鄰居節(jié)點(diǎn)發(fā)送請求查詢包，并給出查詢深度TTL，鄰居節(jié)點(diǎn)收到查詢包后，首先搜索本節(jié)點(diǎn)的資源，若未找到查詢請求需要的資源則轉(zhuǎn)發(fā)給自己的所有鄰居節(jié)點(diǎn)，以此類推，直到找到資源或者TTL為0為止。文獻(xiàn)[9]利用無標(biāo)度網(wǎng)絡(luò)度分布的冪率特性，在搜索過程中將查詢請求傳遞給度值最大的鄰居節(jié)點(diǎn)。文獻(xiàn)[10]采用只傳遞給一定比例的相鄰節(jié)點(diǎn)的策略，在彼此相似度較高節(jié)點(diǎn)之間建立關(guān)聯(lián)，節(jié)點(diǎn)之間相似度高則更有可能包含查詢請求需要的資源。文獻(xiàn)[11]提出將節(jié)點(diǎn)中內(nèi)容的受歡迎程度與節(jié)點(diǎn)的度值相結(jié)合作為確定資源搜索路徑的搜索算法。文獻(xiàn)[12]提出通過完全二叉樹重新組建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)并利用二叉樹的特性提高資源搜索的效率。

研究表明，非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都會(huì)表現(xiàn)出一定的興趣傾向，而當(dāng)兩個(gè)節(jié)點(diǎn)之間的興趣傾向相近時(shí)，這兩個(gè)節(jié)點(diǎn)所包含的資源之間也會(huì)相應(yīng)地表示出一種相關(guān)性[13-14]。文中考慮了非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)與網(wǎng)絡(luò)中節(jié)點(diǎn)之間的興趣傾向，引入興趣二叉搜索樹的概念，通過節(jié)點(diǎn)之間的興趣相似度構(gòu)建多個(gè)搜索二叉樹，將興趣傾向相近的節(jié)點(diǎn)組建成一棵搜索二叉樹。當(dāng)節(jié)點(diǎn)在資源搜索時(shí)可以將查詢請求轉(zhuǎn)發(fā)給與自己直接相連的節(jié)點(diǎn)，這樣有利于減少網(wǎng)絡(luò)搜索過程中的冗余消息，同時(shí)有利于提高資源搜索的成功率。

1 基于興趣的二叉搜索樹

1.1 節(jié)點(diǎn)興趣相似度的計(jì)算

1.1.1 節(jié)點(diǎn)的興趣域

在非結(jié)構(gòu)化P2P中，每個(gè)節(jié)點(diǎn)存儲(chǔ)的資源信息都會(huì)表現(xiàn)出對某個(gè)領(lǐng)域的興趣傾向，文中采用經(jīng)典的向量空間模型(vector space model，VSM)[15]表示節(jié)點(diǎn)的興趣域。向量空間模型利用關(guān)鍵詞在資源中出現(xiàn)的次數(shù)構(gòu)成向量來表示節(jié)點(diǎn)的興趣域模型，是信息獲取領(lǐng)域中的一種經(jīng)典算法。采用特征向量的形式表示節(jié)點(diǎn)的興趣域，可以將節(jié)點(diǎn)之間相似度的比較轉(zhuǎn)化為特征向量之間相似度的比較。

節(jié)點(diǎn)興趣域的表示方法：選取節(jié)點(diǎn)資源中出現(xiàn)次數(shù)最多的k個(gè)關(guān)鍵詞，關(guān)鍵詞ki在節(jié)點(diǎn)中的權(quán)值取為關(guān)鍵詞ki在節(jié)點(diǎn)所包含資源中出現(xiàn)的次數(shù)。

1.1.2 節(jié)點(diǎn)興趣相似度

節(jié)點(diǎn)中的數(shù)據(jù)用VSM模型表示出來后，會(huì)通過相似度函數(shù)來計(jì)算兩個(gè)向量之間的相似程度。文中使用皮爾遜相關(guān)系數(shù)[16]來衡量兩個(gè)向量之間的相似程度。對于節(jié)點(diǎn)X和節(jié)點(diǎn)Y，節(jié)點(diǎn)的興趣域通過VSM模型分別表示為X={xi1,xi2,…,xim}，Y={yj1,yj2,…,yjm}，其節(jié)點(diǎn)之間的相似度通過皮爾遜相關(guān)系數(shù)表示為：

Simx,y=

(1)

其中，N為X與Y中相同元素的個(gè)數(shù)。將Simx,y取絕對值，即可將興趣相似度范圍限制為[0,1]。相似度Simx,y計(jì)算出的數(shù)值越高，表示節(jié)點(diǎn)之間的興趣相似度越大，反之越小。當(dāng)節(jié)點(diǎn)X與節(jié)點(diǎn)Y之間的資源完全相同時(shí)，Simx,y的值為1。

1.2 二叉搜索樹

二叉搜索樹是指或者為空樹，或者具有如下性質(zhì)的二叉樹：如果它的左子樹不為空，則左子樹上的所有節(jié)點(diǎn)的值都小于其根節(jié)點(diǎn)的值；如果它的右子樹不為空，則右子樹上的所有節(jié)點(diǎn)的值都大于其根節(jié)點(diǎn)的值，并且它的左右子樹也分別為二叉搜索樹；不允許存在重復(fù)的節(jié)點(diǎn)。

1.3 興趣二叉搜索樹的構(gòu)建

根據(jù)二叉搜索樹的結(jié)構(gòu)特征，在構(gòu)建興趣二叉搜索樹非結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時(shí)，首先要確定二叉搜索樹的根節(jié)點(diǎn)。在確定根節(jié)點(diǎn)之后，其他節(jié)點(diǎn)依據(jù)與根節(jié)點(diǎn)的興趣相似度的值在興趣二叉搜索樹中確定自己的位置。在構(gòu)建過程中，為了保證二叉搜索樹的性質(zhì)，興趣二叉搜索樹應(yīng)滿足如下性質(zhì)：左孩子與根節(jié)點(diǎn)的相似度應(yīng)該小于根節(jié)點(diǎn)中設(shè)定的相似度閾值；右孩子與根節(jié)點(diǎn)的相似度應(yīng)該大于根節(jié)點(diǎn)中設(shè)定的相似度閾值。在興趣二叉搜索樹中允許存在重復(fù)節(jié)點(diǎn)，文中右孩子與根節(jié)點(diǎn)的相似度可以相等。

興趣搜索二叉樹的構(gòu)建步驟如下：

(1)確定二叉搜索樹的根節(jié)點(diǎn)。在建立基于興趣二叉搜索樹非結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)時(shí)，從根節(jié)點(diǎn)開始構(gòu)建。根節(jié)點(diǎn)的選取應(yīng)該綜合考慮節(jié)點(diǎn)的負(fù)載能力、節(jié)點(diǎn)的計(jì)算能力、穩(wěn)定性和帶寬等多方面因素。為了模擬仿真，將網(wǎng)絡(luò)中的節(jié)點(diǎn)按照興趣相似度等分為N個(gè)興趣塊，并在每個(gè)興趣塊中創(chuàng)建二叉搜索樹，其中N是所創(chuàng)建的二叉搜索樹的個(gè)數(shù)，即為根節(jié)點(diǎn)的數(shù)目。

(2)根節(jié)點(diǎn)向網(wǎng)絡(luò)中的普通節(jié)點(diǎn)發(fā)送廣播，廣播中需要包含根節(jié)點(diǎn)自身的興趣域R，在普通節(jié)點(diǎn)接收到根節(jié)點(diǎn)的廣播后會(huì)計(jì)算自身與根節(jié)點(diǎn)之間的興趣相似度Similarity，并且將Similarity按照其大小進(jìn)行排序，選擇計(jì)算獲得的Similarity值最大的兩個(gè)節(jié)點(diǎn)向該根節(jié)點(diǎn)發(fā)送請求加入的信息，該信息中包含計(jì)算獲得的Similarity值。

(3)根節(jié)點(diǎn)接收到兩個(gè)普通節(jié)點(diǎn)的請求加入的信息后，會(huì)分別將該信息中包含的Similarity值與根節(jié)點(diǎn)本身設(shè)定的閾值相比較，如果該Similarity值大于設(shè)定的閾值，則將該普通節(jié)點(diǎn)作為根節(jié)點(diǎn)的右孩子節(jié)點(diǎn)，否則作為根節(jié)點(diǎn)的左孩子節(jié)點(diǎn)；如果Similarity的值等于設(shè)定的閾值，則將該普通節(jié)點(diǎn)作為根節(jié)點(diǎn)的右孩子節(jié)點(diǎn)。

(4)根節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)分別再發(fā)送廣播，重復(fù)第二步，直到所有節(jié)點(diǎn)都被分配到相應(yīng)的二叉搜索樹中。

在構(gòu)造興趣二叉搜索樹的過程中，節(jié)點(diǎn)被分為兩類，一類是根節(jié)點(diǎn)，另一類是普通節(jié)點(diǎn)。對于兩類不同的節(jié)點(diǎn)，節(jié)點(diǎn)中存儲(chǔ)的信息也不相同。

根節(jié)點(diǎn)作為一個(gè)搜索二叉樹中的超級(jí)節(jié)點(diǎn)，應(yīng)該維護(hù)并存儲(chǔ)整棵搜索二叉樹的有關(guān)信息，所以根節(jié)點(diǎn)應(yīng)該存儲(chǔ)的信息如下：

(1)子節(jié)點(diǎn)IDS：記錄該根節(jié)點(diǎn)的所有子節(jié)點(diǎn)的ID。

(2)根節(jié)點(diǎn)IDS：記錄網(wǎng)絡(luò)中其他根節(jié)點(diǎn)的ID。

(3)本地資源：記錄本節(jié)點(diǎn)可以被搜索到的資源。

(4)興趣域：記錄整棵樹的興趣域。當(dāng)查詢包需要的資源不在根節(jié)點(diǎn)的興趣域但是在該孩子節(jié)點(diǎn)中搜索到的時(shí)候，則將查詢包加入根節(jié)點(diǎn)的興趣域中。在初始時(shí)，興趣域僅存儲(chǔ)根節(jié)點(diǎn)的本地資源，隨著搜索的進(jìn)行會(huì)動(dòng)態(tài)更新興趣域。

普通節(jié)點(diǎn)應(yīng)該存儲(chǔ)的信息如下：

(1)本地資源：記錄本節(jié)點(diǎn)可以被搜索到的資源。

(2)興趣相似度：記錄本節(jié)點(diǎn)與根節(jié)點(diǎn)之間的興趣相似度的值。

2 搜索算法

當(dāng)基于興趣二叉搜索樹的非結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)創(chuàng)建完成后，資源在興趣二叉搜索樹上的搜索分為兩個(gè)階段：第一階段是在與查詢請求相似度最高的興趣二叉樹中搜索；第二階段在興趣二叉搜索樹中沒有搜到所需要的資源后，將查詢請求根據(jù)興趣轉(zhuǎn)發(fā)因子轉(zhuǎn)發(fā)到其他興趣二叉樹中搜索。

2.1 興趣二叉搜索樹內(nèi)部查詢

在創(chuàng)建基于興趣二叉搜索樹的非結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)后，節(jié)點(diǎn)資源的搜索首先會(huì)直接根據(jù)查詢資源的興趣傾向在相應(yīng)的二叉搜索樹中查詢。在相應(yīng)興趣二叉搜素樹中搜索資源的步驟如下：

(1)查詢請求包Q向所有的根節(jié)點(diǎn)發(fā)送廣播搜索請求，選擇與查詢請求包Q興趣相似度值最大的節(jié)點(diǎn)作為開始搜索的起始節(jié)點(diǎn)。

(2)在根節(jié)點(diǎn)中查詢搜索本地資源，查找成功則直接返回結(jié)果，否則轉(zhuǎn)到第3步。

(3)根據(jù)興趣二叉搜索樹的特點(diǎn)，選擇根節(jié)點(diǎn)的右孩子節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)，如果該節(jié)點(diǎn)的右孩子節(jié)點(diǎn)不存在則不進(jìn)行轉(zhuǎn)發(fā)。

(4)如果接收到查詢請求的所有節(jié)點(diǎn)均被訪問過，則直接跳轉(zhuǎn)到第6步，否則跳至第5步。

(5)查詢節(jié)點(diǎn)的本地資源，如果查找成功則返回結(jié)果，否則跳轉(zhuǎn)到第6步。

(6)判斷生存時(shí)間TTL的值，如果TTL已經(jīng)減小到0，則表示搜索結(jié)束，否則跳轉(zhuǎn)到第3步。

2.2 興趣二叉搜索樹之間查詢

當(dāng)在某個(gè)興趣二叉搜索樹中沒有查詢到所需要的資源時(shí)，需要考慮跳轉(zhuǎn)到下一個(gè)興趣二叉搜索樹，對于下一個(gè)興趣二叉搜索樹的選取，文中綜合考慮了查詢反饋情況和兩個(gè)根節(jié)點(diǎn)之間的興趣相似度情況，提出了興趣轉(zhuǎn)發(fā)因子的概念。

2.2.1 查詢反饋比

在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)搜索過程中，考慮到以前歷史的查詢結(jié)果，返回查詢反饋?zhàn)疃嗟墓?jié)點(diǎn)更有可能包含搜索需要的資源。所以，選擇查詢反饋比最高的節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)是一個(gè)相對較好的選擇。

定義1：假設(shè)節(jié)點(diǎn)peer的一個(gè)鄰居節(jié)點(diǎn)為neighbour，則將節(jié)點(diǎn)neighbour的反饋包數(shù)與節(jié)點(diǎn)peer的所有鄰居節(jié)點(diǎn)總的反饋包數(shù)的比值稱作查詢反饋比：

Simback=QueryHitsneighbour/∑QueryHitspeers

(2)

其中，QueryHitsneighbour表示鄰居節(jié)點(diǎn)neighbour的反饋包數(shù)；∑QueryHitspeers表示所有鄰居節(jié)點(diǎn)的反饋包數(shù)。

在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都保存一個(gè)PeerList[17]的列表結(jié)構(gòu)，其中包含了節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)對查詢反饋的響應(yīng)信息。該列表結(jié)構(gòu)如圖1所示。

Peer_IDTotalQueryFeedbackQueryFeedbackQueryRequest

圖1 PeerList列表結(jié)構(gòu)

其中，Peer_ID是節(jié)點(diǎn)所有鄰居節(jié)點(diǎn)的ID；Total Query Feedback是節(jié)點(diǎn)獲得所有鄰居節(jié)點(diǎn)的總反饋包數(shù)目；Query Feedback是從Peer_ID返回的反饋包數(shù)目；Query Request是節(jié)點(diǎn)發(fā)送到Peer_ID的請求包數(shù)。

PeerList列表結(jié)構(gòu)會(huì)隨著搜索的進(jìn)行不斷地動(dòng)態(tài)更新，更新方法如下：如果節(jié)點(diǎn)為被請求節(jié)點(diǎn)，則查找該節(jié)點(diǎn)本地資源，如找到需要資源，則返回一個(gè)查詢反饋包，否則傳遞請求資源，并更新該節(jié)點(diǎn)PeerList中Query Request的值。如果節(jié)點(diǎn)接受查詢反饋包，則更新節(jié)點(diǎn)PeerList中Total Query Feedback和對應(yīng)鄰居節(jié)點(diǎn)的Query Feedback的值。

2.2.2 興趣轉(zhuǎn)發(fā)因子

興趣轉(zhuǎn)發(fā)因子Sim是綜合考慮查詢反饋比Simback和節(jié)點(diǎn)興趣相似度Simx,y的一個(gè)參數(shù)。Sim越高的節(jié)點(diǎn)更有可能包含搜索所需要的資源。

Sim=αSimback+βSimx,y

(3)

其中，α+β=1。

在節(jié)點(diǎn)搜索過程中，下一個(gè)興趣二叉搜索樹選取的方法是計(jì)算所有根節(jié)點(diǎn)中興趣轉(zhuǎn)發(fā)因子并選擇結(jié)果最大的根節(jié)點(diǎn)代表的興趣二叉搜索樹作為下一個(gè)需要進(jìn)行資源搜索的興趣二叉樹。

通過使用節(jié)點(diǎn)的興趣轉(zhuǎn)發(fā)因子作為興趣二叉搜索樹跳轉(zhuǎn)的依據(jù)，興趣二叉搜索樹之間轉(zhuǎn)發(fā)查詢請求的步驟為：

(1)如果在根節(jié)點(diǎn)R的興趣二叉搜索樹中未找到所需要的資源，則計(jì)算與其他根節(jié)點(diǎn)之間的興趣轉(zhuǎn)發(fā)因子，選擇興趣轉(zhuǎn)發(fā)因子最大的節(jié)點(diǎn)進(jìn)行查詢請求的轉(zhuǎn)發(fā)。

(2)將計(jì)算獲得的興趣轉(zhuǎn)發(fā)因子從大到小排序，選擇興趣轉(zhuǎn)發(fā)因子最大的根節(jié)點(diǎn)作為下一個(gè)需要進(jìn)行搜索的興趣二叉搜索樹。

(3)跳轉(zhuǎn)到第1步。

3 仿真分析

為了評(píng)價(jià)算法的優(yōu)劣，實(shí)驗(yàn)采用PeerSim1.0.5仿真模擬器，運(yùn)用Java編程建立仿真環(huán)境。在此環(huán)境下，對傳統(tǒng)的搜索算法與文中提出的搜索算法進(jìn)行分析比較。為了增加仿真的真實(shí)性，非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的根節(jié)點(diǎn)和資源的分布都遵循Zipf分布。網(wǎng)絡(luò)中共產(chǎn)生10 000個(gè)節(jié)點(diǎn)，選取100個(gè)根節(jié)點(diǎn)，查詢的生成時(shí)間設(shè)置為10，通過以下兩個(gè)衡量標(biāo)準(zhǔn)對文中算法與傳統(tǒng)洪泛算法進(jìn)行分析比較。

3.1 搜索成功率

非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中資源的搜索成功率計(jì)算方法為：

(4)

實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 搜索成功率對比曲線

從圖中可以看出，文中算法的搜索成功率總體高于傳統(tǒng)的洪泛算法的搜索成功率，并且隨著搜索跳數(shù)的增加，文中算法搜索成功率也隨之增加。這是由于文中搜索算法在搜索過程中構(gòu)建了興趣二叉搜索樹，節(jié)點(diǎn)在選擇下一跳節(jié)點(diǎn)時(shí)選擇的是更可能包含搜索所需要資源的節(jié)點(diǎn)進(jìn)行消息的轉(zhuǎn)發(fā)，并且在搜索過程中不斷更新節(jié)點(diǎn)的興趣域，使得節(jié)點(diǎn)與查詢包的相似度越來越大，減少了不必要的跳轉(zhuǎn)，提高了搜索成功率。

3.2 平均路徑長度

平均路徑長度是指在多次搜索中的搜索路徑的平均值，可以用來衡量搜索過程中的時(shí)延問題。在搜索過程中，平均路徑長度越大，表明搜索的路徑越長，搜索的響應(yīng)時(shí)間也就越長，搜索過程中的時(shí)延也就越大。所以在搜索過程中，搜索到所需要資源的平均路徑長度越小越好。

實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 平均路徑長度對比曲線

從圖中可以看出，文中算法的平均路徑長度會(huì)隨著搜索次數(shù)的增加不斷下降，而傳統(tǒng)的洪泛算法則基本不受影響。這是由于在傳統(tǒng)的搜索算法中，搜索次數(shù)的增加并不會(huì)引起節(jié)點(diǎn)內(nèi)容的改變，每次搜索都相當(dāng)于一次新的搜索，而在文中搜索算法中，一方面將網(wǎng)絡(luò)中興趣傾向相近的節(jié)點(diǎn)構(gòu)建成二叉搜索樹，使得節(jié)點(diǎn)資源在搜索時(shí)可以在更少的跳數(shù)之內(nèi)找到資源，另一方面如果在某興趣二叉搜索樹中找到資源，則會(huì)將該資源添加到該興趣二叉搜索樹的興趣域中，即文中算法可以充分利用歷史搜索結(jié)果，以后搜索遇到相同資源時(shí)可以直接返回結(jié)果。

4 結(jié)束語

針對非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中節(jié)點(diǎn)連接的隨機(jī)性，提出了一種基于興趣二叉搜索樹的非結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，將內(nèi)容相似度較大的節(jié)點(diǎn)構(gòu)建成一棵二叉搜索樹，利用二叉搜索樹的特性，提高了搜索效率。通過PeerSim仿真，與傳統(tǒng)的洪泛算法相比，該算法可以大大提高資源的搜索成功率，減少搜索的平均路徑。

參考文獻(xiàn)：

[1] TEWARI S,KLEINROCK L.Proportional replication in peer-to-peer networks[C]//International conference on computer communications.[s.l.]:IEEE,2006:1-12.

[2] 王學(xué)龍，張 璟.P2P關(guān)鍵技術(shù)研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2010,27(3):801-805.

[3] GAETA R,GRANGETTO M.Identification of malicious no-des in peer-to-peer streaming:a belief propagation-based technique[J].IEEE Transactions on Parallel & Distributed Systems,2013,24(10):1994-2003.

[4] ZHAO B Y,KUBIATOWICZ J D,JOSEPH A D.Tapestry:an infastructure for fault-tolerant wide-area location and routing[R].California:University of California at Berkeley,2001.

[5] 王 挺,吳曉軍,張玉梅.基于遺傳算法的雙向搜索Chord算法[J].計(jì)算機(jī)應(yīng)用研究,2016,33(1):46-49.

[6] FURNESS J, KOLBERG M. Considering complex search techniques in DHTs under churn[C]//Proceedings of the 2011 IEEE consumer communications and networking conference.Washington DC,USA:IEEE Computer Society,2011:559-564.

[7] ADYA A,BOLOSKY W J,CASTRO M,et al.Farsite:federated,avail-able,and reliable storage for an incompletely trusted environment[J].ACM SIGOPS Operating Systems Review,2002,36(SI):1-14.

[8] FERREIRA R A,RAMANATHAN M K,AWAN A,et al.Search with probabilistic guarantees in unstructured peer-to-peer networks[C]//Proceedings of the fifth IEEE international conference on peer-to-peer computing.Washington DC,USA:IEEE Computer Society,2005:165-172.

[9] ADAMIC L A,LUKOSE R M,PUNIYANI A R,et al.Search in power-law networks[J].Physical Review E,2001,64(4):046135.

[10] RAMANATHAN M K, KALOGERAKI V, PRUYNE J.Finding good peers in peer-to-peer networks[C]//Proceedings of the 16th international symposium on parallel and distributed processing.Washington DC,USA:IEEE Computer Society,2011:24.

[11] TAKEDA D,SUGAWARA S.A content searching scheme using popularity and link degree of nodes in unstructured P2P networks with cache routers[C]//International conference on complex,intelligent,and software intensive systems.Washington DC,USA:IEEE Computer Society,2016:590-594.

[12] 何 可,吳曉軍,張玉梅.基于節(jié)點(diǎn)興趣的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(9):102-107.

[13] 譚義紅,陳治平,林亞平.基于興趣挖掘的非結(jié)構(gòu)化P2P搜索機(jī)制研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用,2006,26(5):1164-1166.

[14] HSIAO H C,SU H W.On optimizing overlay topologies for search in unstructured peer-to-peer networks[J].IEEE Transactions on Parallel and Distributed Systems,2012,23(5):924-935.

[15] BUCKLEY C.Implementation of the smart information retrieval system[R].Ithaca,NY,USA:Cornell University,1985.

[16] STIGLER S M.Francis Galton’s account of the invention of correlation[J].Statistical Science,1989,4(2):73-79.

[17] 劉 璇.非結(jié)構(gòu)化P2P網(wǎng)絡(luò)基于馬爾科夫鏈的資源搜索算法研究[D].北京:北京交通大學(xué),2015.