基于小世界與興趣相關(guān)度的P2P網(wǎng)絡(luò)搜索研究

雷 勇，李 薇

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

非結(jié)構(gòu)化P2P系統(tǒng)應(yīng)用較為廣泛。由于非結(jié)構(gòu)化P2P系統(tǒng)采用洪泛(Flooding)搜索機制，查詢從一個節(jié)點以廣播方式傳播到其他節(jié)點，直到查找到查詢結(jié)果，從而導(dǎo)致每次查詢都產(chǎn)生大量的網(wǎng)絡(luò)流量，對網(wǎng)絡(luò)造成很大的負擔(dān)，影響了非結(jié)構(gòu)化P2P系統(tǒng)的可擴展性。

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

1 相關(guān)理論

1.1 小世界

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

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

1.2 節(jié)點興趣相關(guān)度

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

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

2 構(gòu)建具有小世界特性的覆蓋網(wǎng)絡(luò)

2.1 覆蓋網(wǎng)自組織

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

圖1 覆蓋網(wǎng)絡(luò)結(jié)構(gòu)圖

定義 1描述信息（descriptor）：包含節(jié)點的地址、節(jié)點的興趣相關(guān)度、節(jié)點的興趣域。

定義2節(jié)點的興趣相關(guān)度：定義為節(jié)點與其鄰居節(jié)點存儲的資源信息的相關(guān)程度的值。

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

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

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

2.2 節(jié)點的加入

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

2.3 節(jié)點的退出

當(dāng)有節(jié)點退出P2P網(wǎng)絡(luò)時，節(jié)點發(fā)送退出消息給其鄰居節(jié)點。鄰居節(jié)點收到退出消息后，在自身視圖中尋找申請退出網(wǎng)絡(luò)的節(jié)點的IP地址，找到后在其視圖中刪除此節(jié)點的記錄，刷新視圖信息。

非結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓撲結(jié)構(gòu)是松散的，節(jié)點失效對于非結(jié)構(gòu)化P2P網(wǎng)絡(luò)影響較小。

2.4 節(jié)點的動態(tài)維護

非結(jié)構(gòu)化P2P網(wǎng)絡(luò)具有自組織性和擴展性。為了能夠隨時間的變化而存在，在此選取（tail、rand、push）協(xié)議執(zhí)行覆蓋網(wǎng)絡(luò)的節(jié)點間的動態(tài)通信，通過節(jié)點間通信來維護非結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)拓撲，使其具有小世界特性。

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

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

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

3 搜索算法構(gòu)造

3.1 具有小世界特性的P2P網(wǎng)絡(luò)的特點

本文第二小節(jié)挖掘節(jié)點之間的興趣相關(guān)度，采用動態(tài)構(gòu)造和擇優(yōu)連接兩種策略來構(gòu)造具有小世界特性的P2P覆蓋網(wǎng)絡(luò)。網(wǎng)絡(luò)表現(xiàn)出如下特點：節(jié)點興趣相關(guān)度高的節(jié)點將產(chǎn)生聚類；節(jié)點的本地文檔內(nèi)容基本穩(wěn)定；節(jié)點感興趣的內(nèi)容基本穩(wěn)定，即節(jié)點經(jīng)常發(fā)送自己感興趣的查詢請求；查詢易于在聚類中滿足，減少查詢傳播的次數(shù)，從而減少查詢開銷。

3.2 節(jié)點接收查詢消息

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

節(jié)點轉(zhuǎn)發(fā)查詢消息；}

3.3 節(jié)點轉(zhuǎn)發(fā)查詢消息

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

4 實驗

4.1 實驗方法

實驗在一臺PC上完成，由Peersim軟件模擬產(chǎn)生具有小世界特性的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)。查詢算法的測試文檔集采用80-20原則分布在網(wǎng)絡(luò)的各個節(jié)點上，文檔不會重復(fù)出現(xiàn)。實驗參數(shù)如表1所示。

表1 仿真實驗的參數(shù)設(shè)置

4.2 實驗結(jié)果與分析

為了測試基于興趣相關(guān)度與小世界搜索算法的有效性,將本文算法與Gnutella網(wǎng)絡(luò)flooding算法進行了對比實驗。

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

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

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

圖3 平均訪問的節(jié)點數(shù)與返回文檔的關(guān)系

圖4 搜索產(chǎn)生的消息數(shù)隨TTL變化的曲線

[1]雷霆，余鎮(zhèn)危.基于復(fù)雜網(wǎng)絡(luò)理論的計算機網(wǎng)絡(luò)拓撲研究[J].計算機工程與應(yīng)用，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]湯大權(quán)，賀明科，孟慶崧.基于冪律分布和小世界特性的無結(jié)構(gòu)P2P網(wǎng)絡(luò)中搜索方法研究[J].計算機研究與發(fā)展，2007，44(9)：1566-1571.

[5]鄒洵.基于小世界特性的網(wǎng)格資源發(fā)現(xiàn)算法[J].現(xiàn)代計算機，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.