P2P網(wǎng)絡(luò)中主流搜索算法的分析比較

《P2P網(wǎng)絡(luò)中主流搜索算法的分析比較》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、P2P中主流搜索算法研究報(bào)告（中南大學(xué)信息科學(xué)與工程學(xué)院林建華）摘要:對等(P2P)網(wǎng)絡(luò)是實(shí)現(xiàn)下一代互聯(lián)網(wǎng)的重要組成部分。對等網(wǎng)絡(luò)的可用性依賴于對網(wǎng)絡(luò)上數(shù)據(jù)的高效的查找和提取方法,如何高效的定位和搜索P2P網(wǎng)絡(luò)上的資源是P2P網(wǎng)絡(luò)實(shí)現(xiàn)的最為關(guān)鍵的問題。本文首先從P2P的定義出發(fā),深入介紹了幾種主流的算法與協(xié)議并對每種協(xié)議進(jìn)行了討論。關(guān)鍵詞:P2P網(wǎng)絡(luò);;搜索算法AnalysisandCompareofMainstreamDHTSearchArithmeticinP2PnetworkAbstract:Coordinated(P2P)thenetworkistherea

2、lizationnextgenerationInternetimportantconstituent.Thepeer-to-peernetworkuabilityreliesontothedatahighlyeffectivesearchandwithdrawsthemethodtothenetworkin,howdoesthehighlyeffectivelocalizationansearchintheP2PnetworktheresourcesistheP2Pnetworkrealizationmostessentialquestion.Thisarticle

3、firstembarksfromtheP2PdefinitionthoroughlyintroducedseveralkindofmainstreamsDHTalgorithmsandtheagreementandhavecarriedonthediscussiontoeachkindoagreement.Keywords:P2PNetwork;DHT;SearchingArithmetic1引言對等網(wǎng)絡(luò)(Peer-to-Peer，簡稱P2P)是目前非常熱門的應(yīng)用，自1999年以來，P2P的研究一直是國外知名學(xué)府(如美國麻省理工學(xué)院，加州大學(xué)伯克利分校和萊斯大學(xué)等)

4、以及知名企業(yè)的研發(fā)機(jī)構(gòu)(如微軟，諾基亞的研究院)關(guān)注的重點(diǎn)。它甚至被美國《財(cái)富》雜志稱為改變因特網(wǎng)發(fā)展的四大新技術(shù)之一，被認(rèn)為是代表無線寬帶互聯(lián)網(wǎng)未來的關(guān)鍵技術(shù)。2、P2P對現(xiàn)有搜索的意義???　對于現(xiàn)有搜索服務(wù)而言，P2P技術(shù)不僅僅是簡單的節(jié)約了服務(wù)器成本和提升了搜索速度，更重要的價(jià)值在于促進(jìn)了搜索的多元化和權(quán)力、責(zé)任、義務(wù)的分解。通過合理可行的模式，將P2P技術(shù)與搜索服務(wù)結(jié)合一體，意味著在現(xiàn)有的建立統(tǒng)一的搜索索引數(shù)據(jù)庫的思路之外，還可以引進(jìn)另外兩條思路，一是在互聯(lián)網(wǎng)進(jìn)行全面分散備份和無機(jī)備份、分散索引和無機(jī)索引的思路，二是在互聯(lián)網(wǎng)只索引而無備份的思路，此兩條新路

5、線的本質(zhì)精神，在于將搜索的格局有目前的統(tǒng)而死、一而全轉(zhuǎn)變?yōu)榉侄?、多而散，是一條發(fā)動(dòng)全網(wǎng)力量參與開展搜索自讀物的全息思路。3．非結(jié)構(gòu)化P2P搜索算法　　按照搜索策略，可以分為兩大類：盲目搜索和啟發(fā)式搜索。盲目搜索通過在網(wǎng)絡(luò)中傳播查詢信息并且把這些信息不斷擴(kuò)散給每個(gè)節(jié)點(diǎn)。通過這種洪泛方式來搜索想要的資源。而啟發(fā)式搜索在搜索的過程中利用一些已有的信息來輔助查找過程。由于信息搜索對資源的存儲(chǔ)有一些知識(shí)，所以信息搜索能夠比較快的找到資源。3.1Flooding搜索方法在最初的Gnutella協(xié)議中，使用的是Flooding方法，在網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都不知道其他節(jié)點(diǎn)的資源。當(dāng)它

6、要尋找某個(gè)文件，把這個(gè)查詢信息傳遞給它的相鄰節(jié)點(diǎn)，如果相鄰節(jié)點(diǎn)含有這個(gè)資源，就返回一個(gè)QueryHit的信息給Requester。如果它相鄰的節(jié)點(diǎn)都沒有命中這個(gè)被查詢文件，就把這條消息轉(zhuǎn)發(fā)給自己的相鄰節(jié)點(diǎn)。這種方式像洪水在網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)流動(dòng)一樣，所以叫做Flooding搜索。由于這種搜索策略是首先遍歷自己的鄰接點(diǎn)，然后再向下傳播，所以又稱為寬度優(yōu)先搜索方法（BFS）。如圖所示：搜索的節(jié)點(diǎn)一開始TTL=3，它每傳播一次TTL減1，如果TTL減到0還沒有搜索到資源，則停止。如果搜索到資源則返回目標(biāo)機(jī)器的信息以用來建立連接。在搜索過程中可能出現(xiàn)循環(huán)，但是由于有TTL控制，

7、所以這個(gè)循環(huán)不會(huì)永遠(yuǎn)進(jìn)行下去，當(dāng)TTL=0的時(shí)候自然結(jié)束。圖1Flooding方法示意圖3.2IterativeDeepening搜索方法迭代遞增是Flooding方法的改進(jìn)，策略循環(huán)遞增TTL（TimetoLive）值，這個(gè)值用來控制Flooding的搜索深度。跟Flooding搜索方法給TTL賦一個(gè)較大的值不同，這種方法在初始階段，給TTL一個(gè)很小的值，如果在TTL減為0，還沒有搜索到資源，則給TTL重新賦更高的值。這種策略可以減少搜索的半徑，但是在最壞的情況下，延遲很大，如果P2P網(wǎng)絡(luò)內(nèi)重復(fù)資源豐富，這種方法在不影響搜索質(zhì)量的基礎(chǔ)上將減少網(wǎng)絡(luò)內(nèi)的查詢流量，