鄭　磊

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

[關鍵詞]P2P資源搜索

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

一、引言

P2P即端到端網(wǎng)絡應用,又稱為對等連接或?qū)Φ染W(wǎng)絡,是一種新的通信模式,P2P網(wǎng)絡中的節(jié)點是對等的,且每個peer能同時充當服務器和客戶端。

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

二、P2P資源搜索技術(shù)

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

(一)結(jié)構(gòu)化P2P網(wǎng)絡的資源搜索技術(shù)

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

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

(二)非結(jié)構(gòu)化P2P網(wǎng)絡的資源搜索技術(shù)

非結(jié)構(gòu)化P2P網(wǎng)絡指的是以Gnutella為典型代表的一類網(wǎng)絡。Gnutella

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

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

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

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

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

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

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

對于非結(jié)構(gòu)的P2P網(wǎng)絡路由技術(shù),其本質(zhì)就是通過一種方法盡可能少地覆蓋網(wǎng)絡中的節(jié)點,以達到遍歷搜索的目的。這就要求:消息路由過程中必要的動態(tài)終止,消息的重復必須盡可能減少,消息搜索遍歷過程中下一步覆蓋的節(jié)點數(shù)要盡量少。

三、P2P資源搜索技術(shù)研究的挑戰(zhàn)

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

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

參考文獻:

[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]趙戰(zhàn)斌,對等網(wǎng)絡(P2P)討研究,福建電腦,2007,(1).

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

[6]楊天路等,P2P網(wǎng)絡技術(shù)原理與系統(tǒng)開發(fā)案例,北京:人民郵電出版社,2007.