基于節點興趣非結構化P2P網絡搜索機制研究

莊 偉

(南京郵電大學 自動化學院，江蘇 南京 210023)

0 引 言

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

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

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

研究表明，非結構化P2P網絡中每個節點都會表現出一定的興趣傾向，而當兩個節點之間的興趣傾向相近時，這兩個節點所包含的資源之間也會相應地表示出一種相關性[13-14]。文中考慮了非結構化P2P網絡的拓撲結構與網絡中節點之間的興趣傾向，引入興趣二叉搜索樹的概念，通過節點之間的興趣相似度構建多個搜索二叉樹，將興趣傾向相近的節點組建成一棵搜索二叉樹。當節點在資源搜索時可以將查詢請求轉發給與自己直接相連的節點，這樣有利于減少網絡搜索過程中的冗余消息，同時有利于提高資源搜索的成功率。

1 基于興趣的二叉搜索樹

1.1 節點興趣相似度的計算

1.1.1 節點的興趣域

在非結構化P2P中，每個節點存儲的資源信息都會表現出對某個領域的興趣傾向，文中采用經典的向量空間模型(vector space model，VSM)[15]表示節點的興趣域。向量空間模型利用關鍵詞在資源中出現的次數構成向量來表示節點的興趣域模型，是信息獲取領域中的一種經典算法。采用特征向量的形式表示節點的興趣域，可以將節點之間相似度的比較轉化為特征向量之間相似度的比較。

節點興趣域的表示方法：選取節點資源中出現次數最多的k個關鍵詞，關鍵詞ki在節點中的權值取為關鍵詞ki在節點所包含資源中出現的次數。

1.1.2 節點興趣相似度

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

Simx,y=

(1)

其中，N為X與Y中相同元素的個數。將Simx,y取絕對值，即可將興趣相似度范圍限制為[0,1]。相似度Simx,y計算出的數值越高，表示節點之間的興趣相似度越大，反之越小。當節點X與節點Y之間的資源完全相同時，Simx,y的值為1。

1.2 二叉搜索樹

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

1.3 興趣二叉搜索樹的構建

根據二叉搜索樹的結構特征，在構建興趣二叉搜索樹非結構化P2P覆蓋網絡拓撲結構時，首先要確定二叉搜索樹的根節點。在確定根節點之后，其他節點依據與根節點的興趣相似度的值在興趣二叉搜索樹中確定自己的位置。在構建過程中，為了保證二叉搜索樹的性質，興趣二叉搜索樹應滿足如下性質：左孩子與根節點的相似度應該小于根節點中設定的相似度閾值；右孩子與根節點的相似度應該大于根節點中設定的相似度閾值。在興趣二叉搜索樹中允許存在重復節點，文中右孩子與根節點的相似度可以相等。

興趣搜索二叉樹的構建步驟如下：

(1)確定二叉搜索樹的根節點。在建立基于興趣二叉搜索樹非結構化P2P覆蓋網絡時，從根節點開始構建。根節點的選取應該綜合考慮節點的負載能力、節點的計算能力、穩定性和帶寬等多方面因素。為了模擬仿真，將網絡中的節點按照興趣相似度等分為N個興趣塊，并在每個興趣塊中創建二叉搜索樹，其中N是所創建的二叉搜索樹的個數，即為根節點的數目。

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

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

(4)根節點的左右孩子節點分別再發送廣播，重復第二步，直到所有節點都被分配到相應的二叉搜索樹中。

在構造興趣二叉搜索樹的過程中，節點被分為兩類，一類是根節點，另一類是普通節點。對于兩類不同的節點，節點中存儲的信息也不相同。

根節點作為一個搜索二叉樹中的超級節點，應該維護并存儲整棵搜索二叉樹的有關信息，所以根節點應該存儲的信息如下：

(1)子節點IDS：記錄該根節點的所有子節點的ID。

(2)根節點IDS：記錄網絡中其他根節點的ID。

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

(4)興趣域：記錄整棵樹的興趣域。當查詢包需要的資源不在根節點的興趣域但是在該孩子節點中搜索到的時候，則將查詢包加入根節點的興趣域中。在初始時，興趣域僅存儲根節點的本地資源，隨著搜索的進行會動態更新興趣域。

普通節點應該存儲的信息如下：

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

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

2 搜索算法

當基于興趣二叉搜索樹的非結構化P2P覆蓋網絡拓撲結構創建完成后，資源在興趣二叉搜索樹上的搜索分為兩個階段：第一階段是在與查詢請求相似度最高的興趣二叉樹中搜索；第二階段在興趣二叉搜索樹中沒有搜到所需要的資源后，將查詢請求根據興趣轉發因子轉發到其他興趣二叉樹中搜索。

2.1 興趣二叉搜索樹內部查詢

在創建基于興趣二叉搜索樹的非結構化P2P覆蓋網絡拓撲結構后，節點資源的搜索首先會直接根據查詢資源的興趣傾向在相應的二叉搜索樹中查詢。在相應興趣二叉搜素樹中搜索資源的步驟如下：

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

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

(3)根據興趣二叉搜索樹的特點，選擇根節點的右孩子節點進行消息轉發，如果該節點的右孩子節點不存在則不進行轉發。

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

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

(6)判斷生存時間TTL的值，如果TTL已經減小到0，則表示搜索結束，否則跳轉到第3步。

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

當在某個興趣二叉搜索樹中沒有查詢到所需要的資源時，需要考慮跳轉到下一個興趣二叉搜索樹，對于下一個興趣二叉搜索樹的選取，文中綜合考慮了查詢反饋情況和兩個根節點之間的興趣相似度情況，提出了興趣轉發因子的概念。

2.2.1 查詢反饋比

在非結構化P2P網絡搜索過程中，考慮到以前歷史的查詢結果，返回查詢反饋最多的節點更有可能包含搜索需要的資源。所以，選擇查詢反饋比最高的節點進行消息轉發是一個相對較好的選擇。

定義1：假設節點peer的一個鄰居節點為neighbour，則將節點neighbour的反饋包數與節點peer的所有鄰居節點總的反饋包數的比值稱作查詢反饋比：

Simback=QueryHitsneighbour/∑QueryHitspeers

(2)

其中，QueryHitsneighbour表示鄰居節點neighbour的反饋包數；∑QueryHitspeers表示所有鄰居節點的反饋包數。

在非結構化P2P網絡中，每個節點都保存一個PeerList[17]的列表結構，其中包含了節點的所有鄰居節點對查詢反饋的響應信息。該列表結構如圖1所示。

Peer_IDTotalQueryFeedbackQueryFeedbackQueryRequest

圖1 PeerList列表結構

其中，Peer_ID是節點所有鄰居節點的ID；Total Query Feedback是節點獲得所有鄰居節點的總反饋包數目；Query Feedback是從Peer_ID返回的反饋包數目；Query Request是節點發送到Peer_ID的請求包數。

PeerList列表結構會隨著搜索的進行不斷地動態更新，更新方法如下：如果節點為被請求節點，則查找該節點本地資源，如找到需要資源，則返回一個查詢反饋包，否則傳遞請求資源，并更新該節點PeerList中Query Request的值。如果節點接受查詢反饋包，則更新節點PeerList中Total Query Feedback和對應鄰居節點的Query Feedback的值。

2.2.2 興趣轉發因子

興趣轉發因子Sim是綜合考慮查詢反饋比Simback和節點興趣相似度Simx,y的一個參數。Sim越高的節點更有可能包含搜索所需要的資源。

Sim=αSimback+βSimx,y

(3)

其中，α+β=1。

在節點搜索過程中，下一個興趣二叉搜索樹選取的方法是計算所有根節點中興趣轉發因子并選擇結果最大的根節點代表的興趣二叉搜索樹作為下一個需要進行資源搜索的興趣二叉樹。

通過使用節點的興趣轉發因子作為興趣二叉搜索樹跳轉的依據，興趣二叉搜索樹之間轉發查詢請求的步驟為：

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

(2)將計算獲得的興趣轉發因子從大到小排序，選擇興趣轉發因子最大的根節點作為下一個需要進行搜索的興趣二叉搜索樹。

(3)跳轉到第1步。

3 仿真分析

為了評價算法的優劣，實驗采用PeerSim1.0.5仿真模擬器，運用Java編程建立仿真環境。在此環境下，對傳統的搜索算法與文中提出的搜索算法進行分析比較。為了增加仿真的真實性，非結構化P2P網絡中的根節點和資源的分布都遵循Zipf分布。網絡中共產生10 000個節點，選取100個根節點，查詢的生成時間設置為10，通過以下兩個衡量標準對文中算法與傳統洪泛算法進行分析比較。

3.1 搜索成功率

非結構化P2P網絡中資源的搜索成功率計算方法為：

(4)

實驗結果如圖2所示。

圖2 搜索成功率對比曲線

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

3.2 平均路徑長度

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

實驗結果如圖3所示。

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

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

4 結束語

針對非結構化P2P網絡中節點連接的隨機性，提出了一種基于興趣二叉搜索樹的非結構化P2P覆蓋網絡拓撲結構，將內容相似度較大的節點構建成一棵二叉搜索樹，利用二叉搜索樹的特性，提高了搜索效率。通過PeerSim仿真，與傳統的洪泛算法相比，該算法可以大大提高資源的搜索成功率，減少搜索的平均路徑。

參考文獻：

[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] 王學龍，張 璟.P2P關鍵技術研究綜述[J].計算機應用研究，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].計算機應用研究,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] 何 可,吳曉軍,張玉梅.基于節點興趣的非結構化P2P網絡拓撲結構研究[J].計算機工程與應用,2016,52(9):102-107.

[13] 譚義紅,陳治平,林亞平.基于興趣挖掘的非結構化P2P搜索機制研究與實現[J].計算機應用,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] 劉 璇.非結構化P2P網絡基于馬爾科夫鏈的資源搜索算法研究[D].北京:北京交通大學,2015.