雷 勇，李 薇

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

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

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

1 相關(guān)理論

1.1 小世界

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 節(jié)點(diǎn)的加入

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

2.3 節(jié)點(diǎn)的退出

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

非結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是松散的，節(jié)點(diǎn)失效對(duì)于非結(jié)構(gòu)化P2P網(wǎng)絡(luò)影響較小。

2.4 節(jié)點(diǎn)的動(dòng)態(tài)維護(hù)

非結(jié)構(gòu)化P2P網(wǎng)絡(luò)具有自組織性和擴(kuò)展性。為了能夠隨時(shí)間的變化而存在，在此選?。╰ail、rand、push）協(xié)議執(zhí)行覆蓋網(wǎng)絡(luò)的節(jié)點(diǎn)間的動(dòng)態(tài)通信，通過節(jié)點(diǎn)間通信來維護(hù)非結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)拓?fù)洌蛊渚哂行∈澜缣匦浴?/p>

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)方法

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

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

4.2 實(shí)驗(yàn)結(jié)果與分析

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

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

測試本文算法的搜索效率。通過多次提交查詢請(qǐng)求，統(tǒng)計(jì)訪問節(jié)點(diǎn)的數(shù)量，得到實(shí)驗(yàn)結(jié)果如圖3所示。圖3中，在返回的文檔數(shù)量相同的情況下，本文算法的節(jié)點(diǎn)訪問量遠(yuǎn)遠(yuǎn)低于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é)點(diǎn)在轉(zhuǎn)發(fā)查詢消息時(shí)優(yōu)先轉(zhuǎn)發(fā)給興趣相關(guān)度高的鄰居節(jié)點(diǎn)，有效避免了Gnutella網(wǎng)絡(luò)的洪泛算法中消息轉(zhuǎn)發(fā)的盲目性，減少搜索通信開銷，提高查詢檢索效率。實(shí)驗(yàn)從算法的查全率、通信開銷、覆蓋率三方面證明本文搜索算法的有效性。

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

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

[1]雷霆，余鎮(zhèn)危.基于復(fù)雜網(wǎng)絡(luò)理論的計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)溲芯縖J].計(jì)算機(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].計(jì)算機(jī)研究與發(fā)展，2007，44(9)：1566-1571.

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