基于Ｐ２Ｐ網(wǎng)絡(luò)的資源搜索技術(shù)研究

鄭　磊

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

[關(guān)鍵詞]P2P資源搜索

中圖分類號:TP3文獻(xiàn)標(biāo)識碼:A文章編號:1671-7597(2009)0920068-01

一、引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn):

[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)絡(luò)(P2P)討研究,福建電腦,2007,(1).

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

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