一種有效的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源搜索策略

邢翠芳++劉瑜++楊玫

摘要： 針對非結(jié)構(gòu)化P2P網(wǎng)絡(luò)基本洪泛算法中冗余消息數(shù)過多、搜索效率低等問題，提出了一種新資源搜索策略R2SB2N，該算法通過在節(jié)點中引入鄰居-鄰居節(jié)點表來存儲當(dāng)前節(jié)點鄰居的鄰居信息，同時結(jié)合鄰居節(jié)點的活躍程度和資源命中數(shù)，利用轉(zhuǎn)移公式轉(zhuǎn)發(fā)查詢消息。仿真結(jié)果表明，新策略可以降低消息冗余率，提高資源搜索成功率，是一種有效的資源搜索策略。

關(guān)鍵詞：P2P；flooding；R2SB2N；資源搜索；TTL

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）17-0229-02

A Efficient Resource Search Mechanic for Unstructured Peer-to-Peer Networks

XING Cui-fang， LIU Yu， YANG Mei

（Department of Basic Sciences， Naval Aeronautical And Astronautical University， Yantai 264000， China）

Abstract： For the problem of the unstructured peer-to-peer networks that there are too many redundant messages and the search efficiency is too low in traditional algorithms，the article proposed a resource searching mechanic which named R2SB2N.The new algorithm introduced neighbor-neighbor node information，meanwhile considered of neighbor nodesactiveness and resource hit numbers to forward search messages.Experimental results show that the new strategy can reduce the message redundancy rate and improve the resource search success rate which is an efficient resource search mechanic.

Key words： P2P； flooding； R2SB2N； Resource Search； TTL

P2P網(wǎng)絡(luò)是當(dāng)前比較流行的資源共享網(wǎng)絡(luò)，網(wǎng)絡(luò)中的所有節(jié)點都以一種對等的方式共享處理器計算能力、網(wǎng)絡(luò)帶寬、存儲空間等網(wǎng)絡(luò)資源，其廣泛應(yīng)用于分布式計算、文件共享、協(xié)同工作、資源搜索、智能代理等應(yīng)用領(lǐng)域。與傳統(tǒng)網(wǎng)絡(luò)相比，P2P網(wǎng)絡(luò)技術(shù)為用戶提供了更加簡單快捷的交流方式，提高了整個網(wǎng)絡(luò)資源的利用率，實現(xiàn)了網(wǎng)絡(luò)資源的充分共享，已日益成為研究和應(yīng)用的熱點。從P2P網(wǎng)絡(luò)結(jié)構(gòu)劃分，P2P網(wǎng)絡(luò)分為兩類：結(jié)構(gòu)化網(wǎng)絡(luò)和非結(jié)構(gòu)化網(wǎng)絡(luò)。當(dāng)然也有一些介于二者之間的混合架構(gòu)，但是其搜索方式仍然是前兩種網(wǎng)絡(luò)的混合。結(jié)構(gòu)化網(wǎng)絡(luò)和非結(jié)構(gòu)化網(wǎng)絡(luò)各有特點，可分別適用于不同需求的P2P 系統(tǒng)。

非結(jié)構(gòu)化P2P網(wǎng)絡(luò)主要采用洪泛機(jī)制通過廣播方式進(jìn)行資源定位。某個節(jié)點要定位資源，首先把請求傳播到所有相鄰結(jié)點，這些鄰居節(jié)點再向它自己的鄰居傳播請求，直到找到所需要的資源或者達(dá)到預(yù)先確定的層次為止。在設(shè)計上每條查找消息都帶有全局唯一標(biāo)識，防止對同樣的查找消息進(jìn)行多次響應(yīng)。該算法傳播速度較快，覆蓋范圍較廣，同時也會產(chǎn)生大量冗余查詢消息，造成網(wǎng)絡(luò)流量的急劇增加，消耗大量帶寬，網(wǎng)絡(luò)負(fù)擔(dān)較重，導(dǎo)致算法的搜索速度慢且搜索效率低[1]。因此，本文提出一種改進(jìn)的基于鄰居-鄰居節(jié)點的資源搜索策略R2SB2N。

1 R2SB2N算法簡介

1.1 R2SB2N算法的基本思想

在改進(jìn)的R2SB2N搜索策略中，引入了鄰居-鄰居節(jié)點信息，同時綜合考慮鄰居節(jié)點的活躍度和資源命中數(shù)，按照轉(zhuǎn)移公式，對發(fā)往鄰居節(jié)點的查詢消息進(jìn)行一定條件的限制，選擇更有可能包含目標(biāo)資源的鄰居節(jié)點進(jìn)行轉(zhuǎn)發(fā)，可以將查詢消息發(fā)送到最可能具有響應(yīng)節(jié)點的目標(biāo)區(qū)域。具體來說，在R2SB2N搜索策略中，網(wǎng)絡(luò)中的每個節(jié)點除了需要維護(hù)本地資源信息表、熱點文件緩存表、鄰居節(jié)點活躍度表NAT之外，還需要增加一張鄰居-鄰居節(jié)點表NNT。本地資源信息表主要維護(hù)本地資源，依據(jù)此表可以進(jìn)行資源信息的查詢；熱點文件緩存表主要存放近期訪問頻率比較高的熱點資源，可以從該表中獲取每個熱點資源的URL地址，以便節(jié)省下一次搜索的時間和開銷[2]。鄰居節(jié)點活躍度表NAT是一張二維表，主要記錄每個節(jié)點的活躍程度和資源命中數(shù)，如表1所示。

表中的n表示鄰居節(jié)點個數(shù)，NATi1存儲鄰居節(jié)點i的活躍程度，如果該節(jié)點在近期活躍度高其值就越大，接收查詢消息的能力就較強(qiáng)；NATi0存儲鄰居節(jié)點i的資源命中數(shù)，資源命中數(shù)代表節(jié)點成功命中查詢請求的次數(shù)。鄰居節(jié)點活躍度表中新近一段時間內(nèi)鄰居節(jié)點的情況和作為歷史記錄信息的查詢成功次數(shù)，這兩條信息對下一跳節(jié)點的轉(zhuǎn)發(fā)具有指導(dǎo)作用，它們將共同決定查詢消息的下一跳節(jié)點，這樣可以將查詢消息發(fā)送到目標(biāo)有可能存在的區(qū)域，提高了搜索的效率和命中率。鄰居-鄰居節(jié)點表也是一張二維表，記錄每個鄰居節(jié)點的鄰居節(jié)點，如表2所示。表中第一列為當(dāng)前節(jié)點N的鄰居節(jié)點，n為鄰居節(jié)點個數(shù)，Ni為節(jié)點N的第i個鄰居節(jié)點，第二列為Ni的鄰居節(jié)點。R2SB2N算法仍然采用TTL值來記錄網(wǎng)絡(luò)中查詢消息的生命周期，每個查詢消息在產(chǎn)生時，都要設(shè)定一個TTL上限值，查詢過程中如果在某節(jié)點中未找到目標(biāo)資源，則該查詢消息的TTL值減1，若發(fā)現(xiàn)了目標(biāo)資源，則該查詢消息的TTL保持原值，目的是讓具有高命中率的查詢消息能夠訪問更多的網(wǎng)絡(luò)節(jié)點，提高資源搜索的命中率，當(dāng)TTL值為0時，查詢消息自動銷毀。TTL值的計算方法為公式（1）：

圖1是消息冗余率隨TTL值變化的趨勢圖。從圖中可以看出， flooding算法和R2SB2N算法的消息冗余率都隨著TTL值的增加而變大，但是R2SB2N算法的消息冗余率變化曲線總是位于flooding算法下方，其值始終小于flooding算法。正是因為在R2SB2N算法中引入了鄰居-鄰居節(jié)點表，在轉(zhuǎn)發(fā)查詢消息時，首先依據(jù)鄰居-鄰居節(jié)點表中的信息檢查是否有存在路由環(huán)路的鄰居節(jié)點，然后選擇滿足條件的鄰居作為下一跳節(jié)點，進(jìn)而達(dá)到控制冗余消息數(shù)量的目的。而圖2是查詢成功率隨TTL值變化的趨勢圖。flooding算法和R2SB2N算法的查詢成功率都隨著TTL值的增加而變大，并且R2SB2N算法的查詢成功率變化曲線總是位于flooding算法上方，其值始終大于flooding算法。正是因為在轉(zhuǎn)發(fā)查詢消息時，R2SB2N算法依據(jù)NAT表中鄰居節(jié)點的活躍程度和資源命中數(shù)兩個指標(biāo)，同時按照轉(zhuǎn)移公式，對發(fā)往下一跳節(jié)點的查詢消息做了一定條件的限制，使只有滿足條件的鄰居節(jié)點能夠接收查詢消息，有效地指導(dǎo)了搜索路徑的生成，提高了信息搜索的成功率。

3 小結(jié)

本文對非結(jié)構(gòu)P2P網(wǎng)絡(luò)的洪泛算法進(jìn)行改進(jìn)，提出R2SB2N算法。通過在節(jié)點中引入鄰居-鄰居節(jié)點表，對發(fā)往下

一跳節(jié)點的查詢消息進(jìn)行一定的限制，防止網(wǎng)絡(luò)中路由環(huán)路的產(chǎn)生。仿真結(jié)果表明，該算法在一定程度上減少了查詢消息的數(shù)量，可以降低消息冗余率，降低網(wǎng)絡(luò)帶寬的消耗，提高消息搜索的成功率。

參考文獻(xiàn)：

[1] 張莉.基于非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的資源搜索算法研究[D].南京：南京郵電大學(xué)，2009.

[2] Guangwei Fang， Xiao Zheng.Improving Query Mechanisms for Unstructured Peer-to-Peer Networks[C].P.Bond（Ed.）：ChinacomBiz 2008，CCIS 26，pp.60–67，2009.

[3] 楊林，張永勝，邢長明. 無結(jié)構(gòu)P2P網(wǎng)絡(luò)中的信息檢索算法[J].計算機(jī)工程與應(yīng)用，2009，45（20）：122-172.