基于小世界與興趣相關度的P2P網絡搜索研究

雷 勇，李 薇

（中國人民銀行渭南市中心支行，陜西 渭南714000）

非結構化P2P系統應用較為廣泛。由于非結構化P2P系統采用洪泛(Flooding)搜索機制，查詢從一個節點以廣播方式傳播到其他節點，直到查找到查詢結果，從而導致每次查詢都產生大量的網絡流量，對網絡造成很大的負擔，影響了非結構化P2P系統的可擴展性。

本文通過挖掘節點興趣相關度信息，將興趣相同或相似的節點進行聚類(Clustering)，來構造有小世界特性的覆蓋網絡，在搜索路由機制中依賴興趣相關度，使查詢消息在更高效的路由路徑中傳播，避免了消息轉發中的盲目性，減少了查詢消息的通信開銷，從而提高搜索效率。

1 相關理論

1.1 小世界

在復雜網絡[1]中，諸多統計特性中最重要的是小世界特性。有小世界特性的網絡被稱為小世界網絡[2]。一些文獻表明，P2P系統有時會自動演進到一個小世界[3]。

小世界模型基于這樣一個原則：每個節點都表現出某些可以捕捉到的興趣，而興趣相近的節點所保存的內容和提交的查詢也呈現出一定的相關性。通過挖掘節點的興趣相關性，使相關性高的節點在網絡中相距較近，此網絡所表現出的相似特性，就是所謂的小世界特性。這些特性在參考文獻[4-5]中被證明對提高搜索效率是非常有效的。

1.2 節點興趣相關度

本文用節點興趣域表示一個節點的興趣類別和興趣的特征。一個興趣域 D 表示為 D=(d1，d2，d3，…，dn)，其中，dk(k∈(1，n))是非負實數，代表一個興趣類(如計算機、天文、醫學)，用于衡量節點對興趣類的感興趣程度，興趣域向量的長度n取決于興趣類別的數量。其中dk的值為節點共享的每一類資源的數目。

節點興趣相關度，對于兩個興趣域分別為D1(d11，d12，d13， … ，d1k)和 D2(d21，d22，d23， … ，d2k)的 節 點 p1 和 p2來說，它們之間的興趣相關度G的計算公式為：

2 構建具有小世界特性的覆蓋網絡

2.1 覆蓋網自組織

在自組織的網絡中，每個節點僅有關于網絡的局部信息，并對其連接做出局部的判斷，產生一個全局規模無關結構，具有高度的冗余性[6]。本文將非結構化P2P覆蓋網絡抽象為一個節點的集合，每個節點存儲一個視圖（view），用于記錄鄰居節點的信息，此視圖最多有 C條記錄，每條記錄存儲節點的描述信息（descriptor），C是一個固定的值，對覆蓋網絡中所有的節點都是一致的。覆蓋網絡結構如圖1所示。

圖1 覆蓋網絡結構圖

定義 1描述信息（descriptor）：包含節點的地址、節點的興趣相關度、節點的興趣域。

定義2節點的興趣相關度：定義為節點與其鄰居節點存儲的資源信息的相關程度的值。

健身性：在裕固族傳統體育項目中不乏此類項目，例如：頂桿子、拉爬牛等都對身體素質有著嚴格的要求；摔跤、拔腰等對人的思維同樣有積極地作用，這是一種智慧的體現，并不是意味的蠻力。在各民族中，人們在漫長的社會生產勞動實踐中逐步產生、發展各具特色的鍛煉手段。

定義3節點的興趣域：興趣域由向量表示，表征節點的興趣類別和對興趣類別的感興趣程度。一個興趣域D 表示為 D=(d1，d2，d3，…，dn)。

定義4排序函數R()：用來實現將節點的集合按照集合中各個鄰居節點的興趣相關度大小排序。R(n，{p1，…，pm})={，…，}，如果排在的前面，即節點與n的相關度比節點與n的相關度小。

2.2 節點的加入

當有新節點加入到P2P網絡時，節點將自身的文檔摘要信息向網絡發布，得到鄰居節點的應答，計算自身節點與鄰居節點的興趣相關度，利用排序函數R()將計算出的興趣相關度排序，將排在最后的鄰居節點（興趣相關度高）存儲在視圖中。同時在選中的鄰居視圖中添加此新節點的信息記錄。

2.3 節點的退出

當有節點退出P2P網絡時，節點發送退出消息給其鄰居節點。鄰居節點收到退出消息后，在自身視圖中尋找申請退出網絡的節點的IP地址，找到后在其視圖中刪除此節點的記錄，刷新視圖信息。

非結構化P2P網絡拓撲結構是松散的，節點失效對于非結構化P2P網絡影響較小。

2.4 節點的動態維護

非結構化P2P網絡具有自組織性和擴展性。為了能夠隨時間的變化而存在，在此選取（tail、rand、push）協議執行覆蓋網絡的節點間的動態通信，通過節點間通信來維護非結構化P2P覆蓋網絡拓撲，使其具有小世界特性。

采用基于流言機制的通信協議，實現節點通信的節點選擇、視圖傳遞、視圖選取三個過程。

（2）視圖選取（View selection）：在節點之間的視圖記錄通過merge()合并之后，就需要截去多余視圖以滿足視圖中存儲C條記錄的參數限制。視圖選取通過selectView()函數來選取最多有C條記錄的視圖記錄子集來實現。selectView()的參數為rand，即是隨機選擇視圖中的C條記錄。

（3）視圖傳遞（View propagation）：節點被選中后，傳遞視圖信息的操作。傳遞方式為push，即為節點傳遞自身的視圖給選擇的節點。

3 搜索算法構造

3.1 具有小世界特性的P2P網絡的特點

本文第二小節挖掘節點之間的興趣相關度，采用動態構造和擇優連接兩種策略來構造具有小世界特性的P2P覆蓋網絡。網絡表現出如下特點：節點興趣相關度高的節點將產生聚類；節點的本地文檔內容基本穩定；節點感興趣的內容基本穩定，即節點經常發送自己感興趣的查詢請求；查詢易于在聚類中滿足，減少查詢傳播的次數，從而減少查詢開銷。

3.2 節點接收查詢消息

節點收到查詢消息，首先在本地的資源索引列表中檢索,如果找到匹配信息,則返回Response應答消息；如果檢索失敗則判斷查詢消息的TTL值。當TTL值大于0時，節點轉發查詢消息給鄰居節點。

節點轉發查詢消息；}

3.3 節點轉發查詢消息

節點轉發查詢消息，首先判斷查詢消息的TTL值是否大于0，如果是，則遍歷節點視圖記錄并計算出所有鄰居節點興趣相關度的平均值averages。然后將視圖中存儲的鄰居的興趣相關度G與計算出的興趣相關度的平均值進行比較，如果節點的興趣相關度大于等于此平均值，則轉發查詢消息給此鄰居節點。當遍歷完全部視圖記錄后，TTL值減1，完成查詢消息轉發。算法流程如下：

4 實驗

4.1 實驗方法

實驗在一臺PC上完成，由Peersim軟件模擬產生具有小世界特性的非結構化P2P網絡。查詢算法的測試文檔集采用80-20原則分布在網絡的各個節點上，文檔不會重復出現。實驗參數如表1所示。

表1 仿真實驗的參數設置

4.2 實驗結果與分析

為了測試基于興趣相關度與小世界搜索算法的有效性,將本文算法與Gnutella網絡flooding算法進行了對比實驗。

測試本文算法的檢索結果的查全率(recall)。從圖2中可以看出，設置相同的TTL，本文算法比Gnutella的查全率高，同時，TTL的值越大，兩種算法的查全率相差越小。當TTL取值在1～5時，本文算法的查全率都高于Gnutella。當TTL取6或更大時，兩者的查全率基本一致，因為此時查詢已經幾乎覆蓋了網絡中的所有節點。此實驗選取的節點數量為1 000，網絡規模較小，所以在TTL為6時，搜索消息數量更容易遍歷大量的節點，所以查全率結果比較接近100%。

測試本文算法的搜索效率。通過多次提交查詢請求，統計訪問節點的數量，得到實驗結果如圖3所示。圖3中，在返回的文檔數量相同的情況下，本文算法的節點訪問量遠遠低于Gnutella，隨著返回文檔數的增加，這種變化越來越明顯。圖4所示為搜索產生的消息數隨TTL變化的曲線。結果表明，由于本文算法查詢消息的轉發是有指導的，所以設置相同的TTL值，本文算法轉發的消息數明顯少于Gnutella算法。

本文基于興趣相關度和小世界特性，構造了具有小世界特性的覆蓋網絡，引入了基于小世界與興趣相關度的搜索算法，當節點在轉發查詢消息時優先轉發給興趣相關度高的鄰居節點，有效避免了Gnutella網絡的洪泛算法中消息轉發的盲目性，減少搜索通信開銷，提高查詢檢索效率。實驗從算法的查全率、通信開銷、覆蓋率三方面證明本文搜索算法的有效性。

圖3 平均訪問的節點數與返回文檔的關系

圖4 搜索產生的消息數隨TTL變化的曲線

[1]雷霆，余鎮危.基于復雜網絡理論的計算機網絡拓撲研究[J].計算機工程與應用，2007，43(6)：132-135.

[2]WATTS D J，STROGATZ S H.Collective dynamics of“small-world” networks[J].Nature，1998，393(4)：440-442.

[3]AKAVIPAT R，WU L S，MENCZER F.Small world peer networks in distributed Web search[C].Proceedings of the 13th international conference on World Wide Web-Alternate Track Papers Posters.New York：ACM Press，2004：396-397.

[4]湯大權，賀明科，孟慶崧.基于冪律分布和小世界特性的無結構P2P網絡中搜索方法研究[J].計算機研究與發展，2007，44(9)：1566-1571.

[5]鄒洵.基于小世界特性的網格資源發現算法[J].現代計算機，2008(12)：59-62.

[6]ALBERT R，JEONG H，BARABASI A.Error and attack tolerance of complex networks[J].Nature，2000，406(7)：378-382.