基于Ｐ２Ｐ網絡的資源搜索技術研究

鄭　磊

[摘要]對P2P資源搜索的拓撲結構和資源搜索算法等相關知識作較詳細的介紹,對基于不同P2P結構的搜索算法作簡單的對比和分析。并針對現有搜索算法存在的問題,提出一些解決的設想,最后對影響搜索算法的因素和解決的方法進行歸納。

[關鍵詞]P2P資源搜索

中圖分類號:TP3文獻標識碼:A文章編號:1671-7597(2009)0920068-01

一、引言

P2P即端到端網絡應用,又稱為對等連接或對等網絡,是一種新的通信模式,P2P網絡中的節點是對等的,且每個peer能同時充當服務器和客戶端。

在P2P網絡中,不存在中心服務器,所有的節點既是客戶機,享用其他節點提供的服務,同時又充當服務器,為其他節點提供服務。P2P對等的節點之間進行直接的連接與共享,因此搜索無需通過Web服務器,也可不受任何信息文檔格式和宿主設備的限制,可以達到傳統搜索引擎無可比擬的深度,理論上可以包括網絡上所有的信息資源。現階段互連網上大量資源被閑置,沒有被充分利用,P2P搜索技術可以幫助人們方便地找到所需資源。

二、P2P資源搜索技術

為了在P2P網絡中有效的發現資源,人們對P2P搜索技術做了大量的研究。目前主要從P2P網絡的結構以及采用的算法兩方面進行研究。P2P網絡可分為兩類:結構化網絡和非結構化網絡。在結構化網絡中每個結點存儲的信息與網絡拓撲結構有關,通過映射完成,查找采用基于DHT分布式散列路由搜索算法。而非結構化網絡則與網絡拓撲無關,其結點可任意存儲信息,查找采用基于廣度優先的搜索算法及其改進算法。

(一)結構化P2P網絡的資源搜索技術

結構化P2P網絡是指像CAN、Chord、Tapestry之類的點對點的網絡。這類網絡中每個節點都有固定的地址,整個網絡具有相對穩定和規則的拓撲結構。依賴拓撲結構,可以給網絡的每一個節點指定一個邏輯地址,并把地址和節點對應起來。動態散列表是大多數結構化P2P網絡所采取的資源定位方式。首先將網絡中的每一個節點分配虛擬地址(VID),同時用一個關鍵字(KEY)來表示其可提供的共享內容。取一個散列函數,這個函數可以將KEY轉換成一個散列值H(KEY)。網絡中節點相鄰的定義是散列值相鄰。發布信息的時候就把(KEY,VID)二元組發布到具有和H(KEY)相近地址的節點上去,其中VID指出了文檔的存儲位置。資源定位的時候,就可以快速根據H(KEY)到相近的節點上獲取二元組(KEY,VID),從而獲得文檔的存儲位置。不同的DHT算法決定了P2P網絡的邏輯拓撲,比如CAN就是一個N維向量空間,而CHORD是一個環形拓撲,TAPESTRY則是一個網狀的拓撲。

基于DHT這類結構搜索算法最大的問題是DHT的維護機制較為復雜,尤其是結點頻繁加入退出造成的網絡波動,極大地增加了DHT的維護代價。這類搜索算法存在的另外一個問題是DHT僅支持精確關鍵詞匹配查詢,無法支持內容、語義等復雜查詢。這是由于其采用相容散列函數根據精確關鍵詞進行對象的定位與發現,散列函數總是試圖保證生成的散列值均勻隨機分布,結果兩個內容相似度很高但不完全相同的對象被生成了完全不同的散列值,存放到了完全隨機的兩個結點上。目前在DHT基礎上開展帶有語義的資源管理技術的研究還非常少。也正是由于DHT的精確關鍵詞映射的特性決定了無法和信息檢索等領域的研究成果結合,才阻礙了基于DHT的P2P系統的大規模應用。

(二)非結構化P2P網絡的資源搜索技術

非結構化P2P網絡指的是以Gnutella為典型代表的一類網絡。Gnutella

是更加純粹的P2P系統,因為它沒有中央索引服務器,每臺機器在Gnutella

網絡中是真正的對等關系。非結構化P2P網絡的搜索技術按照搜索策略可以分為兩大類:盲目搜索和啟發式搜索。盲目搜索通過在網絡中傳播查詢信息并且把這些信息不斷擴散給每個節點,采用泛洪方式來搜索想要的資源。而啟發式搜索在搜索的過程中利用一些己有的信息來輔助查找過程,因此能較快找到所需的資源。

1.Flooding搜索方法。在最初的Gnutella協議中,使用的是Flooding,又稱為寬度優先搜索方法。在網絡中,一個節點向所有鄰居節點廣播查詢消息,鄰居節點再向自己的鄰居節點廣播,這個過程不斷進行下去,像洪水在網絡中各個節點流動一樣,所以叫做Flooding搜索。搜索的節點開始給TTL。賦一初值,它每傳播一次TTL減1,如果TTL減到0還沒有搜索到資源,則停止。如果搜索到資源則返回目標機器的信息以用來建立連接。在搜索過程中可能出現循環,當TTL=0的時候循環自然結束。該算法的特點:路由算法比較簡單,易于實現。每次路由都是全網遍歷,增加了網絡的負擔,搜索的效率不高,網絡擴展性差,路由算法容易被攻擊。

2.Modified-BFS方法。該算法的路由機制大部分跟Flooding搜索方法相同,即采用全網遍歷的搜索形式。不同處在于,源只是隨機的選取一定比例的相鄰節點作為查詢信息的發送目標,而不是發送給所有相鄰節點。相比于Flooding方法來說,是以時間換取空間的有效嘗試。該算法的特點:減少了路由消息,降低了網絡負載,降低了網絡的覆蓋,因此可能需要發費更長的時間才能到達定位的目標節點。

3.Random Walk搜索方法。該算法進一步加強對節點路由消息的擴散程度的控制,主要體現在擴散程度和擴散范圍兩個方面都有所改進。請求者發出K個查詢請求給隨機挑選的K個相鄰節點。然后每個查詢信息在以后的漫步過程中直接與請求者保持聯系,詢問是否還要繼續下一步。如果請求者同意繼續漫步,則又開始隨機選擇下一步漫步的節點,否則中止搜索。

4.Gnutella2的搜索方法。為了減少系統中的路由消息,這種算法采用了超級節點和葉子節點的兩級節點的分類方法,將系統分成了兩級網絡。超級節點存儲著離它最近的葉子節點的文件信息并定期互相更新,超級節點互相連接形成一個核心網絡。當葉子節點需要查詢文件時,它首先從它連接的超級節點的索引中尋找,如果找到了文件,則直接根據文件所存儲的機器的IP地址建立連接,否則,超級節點把這個查詢請求發給它連接的其他超級節點,直到得到想要的資源。該算法的特點:超級節點負責了大部分的路由功能,降低了葉子節點的負載,從而縮短了查詢的延時。但由于超級節點的存在,安全性較差,當超級節點受到攻擊或失效時易造成網絡的癱瘓。

5.基于移動Agent的搜索方法。該算法將移動Agent和P2P路由人工智能技術進行了結合,簡單的說,移動Agent是一個能在異構網絡中自主地從一臺主機遷移到另一臺主機,并可與其他Agent或資源進行交互的程序。Agent非常適合在網絡環境中來幫助用戶完成信息檢索的任務。當有節點需要搜索的時候,它發送一個移動Agent給它相鄰的節點,移動Agent記錄著它的一些搜索的信息。當這個Agent到達一臺新的機器上,然后在這個機器上進行資源搜索任務,如果這臺機器上沒有它想要的資源,則它把這些搜索的信息傳給它的鄰節點,如果找到資源,則返回給請求的機器。該算法的特點:在用戶的個性化管理方面有著相當的優勢,可根據用戶的需求進行分類、整理、分析用戶的愛好,幫助用戶查找其感興趣的信息。但其實現較為復雜,由于Agent的運行增加了節點的負載,搜索時延差別較大。

對于非結構的P2P網絡路由技術,其本質就是通過一種方法盡可能少地覆蓋網絡中的節點,以達到遍歷搜索的目的。這就要求:消息路由過程中必要的動態終止,消息的重復必須盡可能減少,消息搜索遍歷過程中下一步覆蓋的節點數要盡量少。

三、P2P資源搜索技術研究的挑戰

目前P2P搜索技術中,兩個重要的研究成果分別是基于Small World理論的非結構化搜索算法和基于DHT的結構化搜索算法。尤其是DHT及其搜索技術為資源的組織與查找提供了一種新的方法,在近年來的P2P研究領域成為熱點。隨著P2P系統實際應用的發展,物理網絡中影響路由的一些因素開始影響P2P搜索算法的效率。

P2P資源搜索方法要實現的搜目標包括:減少搜索過程中產生的消息數量,減少節點維護的路由索引或數據索引大小,保證系統的容錯性、可擴展性,維持節點之間的負載平衡等。雖然目前新的P2P搜索方法不斷的涌現,但其在資源搜索效率、準確定位和復雜查詢等方面還有很大的改善空間,在具體的應用實現上仍有較長的路要走。基于P2P技術的搜索引擎要達到現在集中式的搜索引擎(如Google、百度)這樣廣泛的使用還需要一段長時間的努力。如何將資源搜索方法結合實際需求進行改進及推廣應用將是需要進一步研究和解決的問題性地做好這項工作,才能更好地為用戶服務,為企業獲取最大的效益。

參考文獻:

[1]DietterichAT G,Lathrop R H,Lozano-Pérez P T.Solving the multiple-instance problem with axis-parallel rectangles[J].Artificial Intelligence,1997,89(1-2):31-71.

[2]O Maron,T Lozano-Perez.A framework for multiple-instance learning[C].Advances in Neural Information Processing Systems.MIT Press,1998.

[3]Wang J.,Zucker J.-D.Solving the multiple-instance problem:A lazy learning approach.In:Langley P.eds.Proc.of the 17th In-ternational Conference on Machine Learning,San Francisco,2000,341-349.

[4]趙戰斌,對等網絡(P2P)討研究,福建電腦,2007,(1).

[5]李莉、韓慧健,無結構P2P網絡資源搜索方法研究,網絡與通信,2007,(1).

[6]楊天路等,P2P網絡技術原理與系統開發案例,北京:人民郵電出版社,2007.