基于Ｐ２Ｐ網絡搜索技術研究
來源:用戶上傳
作者: 王艷輝
提要在P2P系統中，資源分散在各個節點上，節點頻繁的加入或退出，P2P系統處于不斷的變化之中。本文主要分析P2P網絡的基本概念以及目前P2P的幾種搜索技術各自的特點及性能。
一、P2P技術簡介
?。ㄒ唬└拍罴疤卣?。P2P是peer to peer的縮寫，是一種用于不同用戶PC機之間共享他們所擁有的空閑軟硬件資源（處理能力、存儲能力、網絡連接能力、可共享文件等），可以不經過中心節點直接互相訪問和交換信息的技術。它打破了傳統的C/S式，在對等網絡中，每個節點都具備客戶機和服務器的雙重特性，可以同時作為服務使用者和服務提供者。與其他網絡模型相比較，P2P有分散化、可擴展性和健壯性好、高性能等優點。P2P技術目前的主要應用：文件共享與交換、協同工作、搜索引擎、分布計算、智能代理。
（二）P2P與C/S的區別。每個對等點具有相同的地位，同時扮演著服務器和客戶端兩個角色，還具有路由和緩沖的功能。P2P中每個結點可以很容易加入系統中，其中任一結點可以利用網絡上其他對等體的信息資源、理器周期、速緩存和磁盤空間，P2P是基于內容的尋址方式。P2P模式最主要的優點就是資源的高度利用率，所有節點的資源總和構成了整個網絡的資源，整個網絡可以被用作具有海量存儲能力和巨大計算處理能力的超級計算機。而且對等點越多，網絡性能越好，網絡隨著規模的增大而越穩固。信息在網絡設備節點間直接流動，高速即時，降低中轉服務成本。但P2P也有些不足，P2P不易管理，對等點可以隨意的加入或退出，會造成網絡帶寬和信息存在的不穩定。
二、P2P的幾種搜索技術
?。ㄒ唬㏄2P搜索的幾種基本方式
1、Index集中式架構。存在一個提供索引功能的節點，這個節點的索引儲存了資源所在的位置信息，給定資源的某種查詢條件，索引可以迅速找出符合條件的資源及其所在的位置
2、Hash分布式結構。這種方式要求每一個資源都可以通過某種hash算法找到一個唯一的地址，發布資源時資源不是保存在本地，而是保存在這個資源hash后的地址所對應的節點中。
3、Flooding分布式架構。這種方式要求每個節點都有查詢本地資源的能力，每個節點都有d個鄰居，這些節點之間通過鄰居關系構成一個連通的網絡。查詢時通過向鄰居廣播查詢請求來遍歷整個網絡進行查找。其特點就是節點覆蓋率高。
根據拓撲結構的關系可以將P2P研究分為4種形式：中心化拓撲、全分布式非結構化拓撲、全分布式結構化拓撲（也稱作DHT網絡）和半分布式拓撲。
（二）基于集中式索引的搜索。這種搜索引擎的資源分布在世界各地，而作為搜索引擎的服務器（集群）只有一個或少量幾個。使用該模型作為搜索方法的一個典型系統是Napster，在這樣的系統中存在一個中央服務器存放其他節點所共享資源的一個索引，任何一個注冊的節點都要向中央服務器傳送自己所共享資源的索引，節點搜索資源時，將帶有所搜索資源標識的搜索請求發送到中央服務器，中央服務器檢索資源索引，告知資源請求者擁有該資源的節點的標識，然后資源請求者直接去訪問資源擁有者節點下載所請求的文件或者使用其資源。這種方式并不是純粹的P2P模型，因為它需要一個中央服務器，中央索引模型的優點在于搜索速度比較快，并且搜索全面，其他節點可以動態地將信息傳至服務器，所以索引更新的速度也比較快，搜索過程中所需要的消息量小，節省了網絡帶寬。其缺點在于中央服務器的能力限制了節點的數量，系統的可伸縮性不夠，并且一旦中央服務器失敗，整個系統就無法運行，容錯性不高，還可能涉及到版權、法律等方面的問題。
（三）基于全分布式非結構化的搜索。全分布式非結構化拓撲搜索的典型方法是FLOODING。與集中目錄不同，泛洪請求式沒有中央目錄服務器，用戶的請求通過所有連接的節點傳遞，這些節點或者響應請求，或者在不能滿足請求時，交該請求向與自己相連的其他節點廣播，直到請求得到響應為止。FLOODING的模式雖然簡單，但是擁有高魯棒性、高可擴展性、簡便易行等種種優點，是天生的P2P搜索方式。但是它也存在問題：就是會產生大量冗余消息，特別是當網絡規模比較大，節點之間連通度比較高的時候。在實際的P2P網絡中，冗余消息增加了節點處理負擔，也會占用大量網絡帶寬。解決這個問題就是在消息中加入TTL，TTL是time-to-time的縮寫，每個消息的生存時間就是TTL的值，消息每經過一次轉發，TTL就減一，當TTL等于0時就表明這個消息的壽命到頭了，系統就會丟棄這個消息。引入TTL機制雖然可以解決消息在環內的無限循環問題，但是帶來了另一個問題：TTL的取值太小，很多查詢客戶端的節點就無法查到；TTL值太大，就會造成大量環內的無用消息泛濫，加重網絡負擔。隨著網絡規模的擴大，TTL值不得不增加，相應的無用消息的數量也呈指數增長。另一種解決環的思路是想辦法構造一棵以查詢起點為根的生成樹，消息沿著可生成樹發送，自然不會造成網絡擁塞。為了解決消息爆炸的問題，對FLOODING方式進行的一些改進方案。1、隨機漫步法，節點隨機選取N個鄰居節點，把請求消息轉發給這些相鄰結點，然后這些鄰居節點將請求消息隨機地向它的一個相鄰節點進行轉發，此可大大減少消息的產生數量。2、逐步加深法，這種搜索策略是在初始階段，給TTL一個很小的值，如果在TTL減為0時還沒有搜索到資源，則給TTL重新賦更高的值，這種策略可以減少搜索的直徑。
?。ㄋ模┗谌植际紻HT的搜索
1、分布式散列表（DHT）。DHT的基本設計思想是：在P2P中使用一個足夠大的ID空間，系統中的所有節點和數據均具有唯一的ID標志，每個節點和數據的ID是通過散列函數。即NodeID=Hash(Node)；DataID=Hash(Data)，這樣系統系統中所有節點就通過NodeID映射到了ID空間，將空間分割成若干個子空間，每個節點負責一個子空間；數據保存在負責DataID所在的子空間的節點上，系統中的每個節點需要按照一定的策略維護其PX部分節點的信息表(即路由表)以便進行查找、定位和路由。
Chord使用相容散列為每個節點和數據分配m位的ID。節點按照NodeID mod 2m的順序連成一個環型拓撲結構。而數據k存放在第一個滿足NodeID≥DataID的節點上，此節點稱為該數據的后繼節點，記作sucessor(k)，在一個節點數N的系統中，每個節點維護其他O(log(N))個節點的信息，這些信息存儲在一個稱為Finger Table的路由表中，在節點n的Finger Table中，第i項包含節點s的信息。其中，s=successor(n+2i-1)，1
轉載注明來源:http://www.hailuomaifang.com/2/view-413444.htm
