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

邢翠芳++劉瑜++楊玫

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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é)點(diǎn)都以一種對(duì)等的方式共享處理器計(jì)算能力、網(wǎng)絡(luò)帶寬、存儲(chǔ)空間等網(wǎng)絡(luò)資源，其廣泛應(yīng)用于分布式計(jì)算、文件共享、協(xié)同工作、資源搜索、智能代理等應(yīng)用領(lǐng)域。與傳統(tǒng)網(wǎng)絡(luò)相比，P2P網(wǎng)絡(luò)技術(shù)為用戶提供了更加簡(jiǎn)單快捷的交流方式，提高了整個(gè)網(wǎng)絡(luò)資源的利用率，實(shí)現(xiàn)了網(wǎng)絡(luò)資源的充分共享，已日益成為研究和應(yīng)用的熱點(diǎn)。從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ò)各有特點(diǎn)，可分別適用于不同需求的P2P 系統(tǒng)。

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

1 R2SB2N算法簡(jiǎn)介

1.1 R2SB2N算法的基本思想

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

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

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

3 小結(jié)

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

一跳節(jié)點(diǎn)的查詢消息進(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ì)算機(jī)工程與應(yīng)用，2009，45（20）：122-172.