【文章內(nèi)容簡介】 研究者證明 O(logN)甚至O(logN/loglogN)的平均路徑長度也不能滿足狀態(tài)變化劇烈的網(wǎng)絡(luò)應(yīng)用 的需求。新的搜索算法受到這種折衷關(guān)系制約的根本原因在于 DHT 對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的確定性認(rèn)識(shí)。 2. 語義查詢和 DHT 的矛盾 現(xiàn)有 DHT 算法由于采用分布式散列函數(shù)，所以只適合于準(zhǔn)確的查找，如果要支持目前Web 上搜索引擎具有的多關(guān)鍵字查找的功能，還要引入新的方法。主要的原因在于 DHT 的工作方式。 基于 DHT 的 P2P 系統(tǒng)采用相容散列函數(shù)根據(jù)精確關(guān)鍵詞進(jìn)行對象的定位與發(fā)現(xiàn)。散列函數(shù)總是試圖保證生成的散列值均勻隨機(jī)分布，結(jié)果兩個(gè)內(nèi)容相似度很高但不完全相同的對象被生成了完全不同的散列值，存放到了完全隨機(jī)的兩個(gè)結(jié)點(diǎn)上 。因此， DHT 可以提供精確匹配查詢，但是支持語義是非常困難的。 目前在 DHT 基礎(chǔ)上開展帶有語義的資源管理技術(shù)的研究還非常少。由于 DHT 的精確關(guān)鍵詞映射的特性決定了無法和信息檢索等領(lǐng)域的研究成果結(jié)合，阻礙了基于 DHT 的 P2P 系統(tǒng)的大規(guī)模應(yīng)用。 二、非結(jié)構(gòu)化 P2P 網(wǎng)絡(luò)的搜索技術(shù) 1. 小世界模型 (Small World)對 P2P 搜索技術(shù)的影響 非結(jié)構(gòu)化 P2P 搜索技術(shù)一直采用洪泛轉(zhuǎn)發(fā) (Flooding)的方式，與 DHT 的啟發(fā)式搜索算法相比，可靠性差，對網(wǎng)絡(luò)資源的消耗較大。最新的研究從提高搜索算法的可靠性和 尋找隨機(jī)圖中的最短路徑兩個(gè)方面展開。也就是對重疊網(wǎng)絡(luò) (Overlay Network)的重新認(rèn)識(shí)。其中，小世界模型特征和冪規(guī)律證明實(shí)際網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)既不是非結(jié)構(gòu)化系統(tǒng)所認(rèn)識(shí)的一個(gè)完全隨機(jī)圖，也不是 DHT 發(fā)現(xiàn)算法采用的確定性拓?fù)浣Y(jié)構(gòu)。實(shí)際網(wǎng)絡(luò)體現(xiàn)的冪規(guī)律分布的含義可以簡單解釋為在網(wǎng)絡(luò)中有少數(shù)結(jié)點(diǎn)有較高的 “度 ”，多數(shù)結(jié)點(diǎn)的 “度 ”較低。度較高的結(jié)點(diǎn)同其他結(jié)點(diǎn)的聯(lián)系比較多，通過它找到待查信息的概率較高。 Small world 模型的特性：網(wǎng)絡(luò)拓?fù)渚哂懈呔奂群投替湹奶匦?。在符?Small World特性的網(wǎng)絡(luò)模型 中，可以根據(jù)結(jié)點(diǎn)的聚集度將結(jié)點(diǎn)劃分為若干簇 (Cluster)，在每個(gè)簇中至少存在一個(gè)度最高的結(jié)點(diǎn)為中心結(jié)點(diǎn)。大量研究證明了以 Gnutella 為代表的 P2P 網(wǎng)絡(luò)符合 Small World 特征，也就是網(wǎng)絡(luò)中存在大量高連通結(jié)點(diǎn)，部分結(jié)點(diǎn)之間存在 “短鏈 ”現(xiàn)象。 圖 2 Gnutella 重疊網(wǎng)絡(luò)的 Small World 現(xiàn)象 因 此， P2P搜索算法中如何縮短路徑長度的問題變成了如何找到這些 “短鏈 ”的問題。尤其是在 DHT 搜索算法中，如何產(chǎn)生和找到 “短鏈 ”是搜索算法設(shè)計(jì)的一個(gè)新的思路。 Small World特征的發(fā)現(xiàn)和引入會(huì)對 P2P 搜索算法產(chǎn)生重大影響。 2. 非結(jié)構(gòu)化 P2P 搜索算法 按照搜索策略，可以分為兩大類：盲目搜索和啟發(fā)式搜索。盲目搜索通過在網(wǎng)絡(luò)中傳播查詢信息并且把這些信息不斷擴(kuò)散給每個(gè)節(jié)點(diǎn)。通過這種洪泛方式來搜索想要的資源。而啟發(fā)式搜索在搜索的過程中利用一些已有的信息來輔助查找過程。由于信息搜索對資源的存儲(chǔ)有一些知識(shí)，所以信息 搜索能夠比較快的找到資源。 ? Flooding 搜索方法 在最初的 Gnutella協(xié)議中，使用的是 Flooding方法，在網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都不知道其他節(jié)點(diǎn)的資源。當(dāng)它要尋找某個(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 控制，所以這個(gè)循環(huán)不會(huì)永遠(yuǎn)進(jìn)行下去，當(dāng) TTL=0 的時(shí)候自然結(jié)束。 圖 3Flooding 方法示意圖 ? ModifiedBFS 方法 這種方法是在寬度優(yōu)先方法 Flooding上面作了一定修改。跟 Flooding 搜索方法不同，搜索源只是隨機(jī)的選取一定比例的相鄰節(jié)點(diǎn)作為查詢信息的發(fā)送目標(biāo)，而不是發(fā)送給所有相鄰節(jié)點(diǎn)。相比于 Flooding 方法來說，是以時(shí)間換取空間的有效嘗試。 ? Iterative Deepening 搜索方法 迭代遞增是 Flooding 方法的改進(jìn)，策略循環(huán)遞增 TTL（ Time to Live）值，這個(gè)值用來控制Flooding 的搜索深度。跟 Flooding 搜索方法給 TTL賦一個(gè)較大的值不同，這種方法在初始階段，給 TTL 一個(gè)很小的值，如果在 TTL減為 0，還沒有搜索到資源，則給 TTL重新賦更高的值。這種策略可以減少搜索的半徑，但是在最壞的情況下，延遲很大，如果 P2P 網(wǎng)絡(luò)內(nèi)重復(fù)資源豐富，這種方法在不影響搜索質(zhì)量的基礎(chǔ)上將減少網(wǎng)絡(luò)內(nèi)的查詢流量，在有的文獻(xiàn)中亦稱為 Expanding Ring（擴(kuò)展環(huán)搜索）。 圖 4 Iterative Deepening 過程 ? Random Walk 搜索方法 : 在隨機(jī)漫步中，請求者發(fā)出 K 個(gè)查詢請求給隨機(jī)挑選的 K 個(gè)相鄰節(jié)點(diǎn)。然后每個(gè)查詢信息在以后的漫步過程中直接與請求者保持聯(lián)系，詢問是否還要繼續(xù)下一步。如果請求者同意繼續(xù)漫步，則又開始隨機(jī)選擇下一步漫步的節(jié)點(diǎn)，否則中止搜索。 圖 5 Random Walk 效果圖 ? Gnutella2 的搜索方法 Gnutella2 建立 SuperNode,它存儲(chǔ)著離它最近的葉子節(jié)點(diǎn)的文件信息，這些 SuperNode,再連通起來形成一個(gè) Overlay ，它首先從它連接的SuperNode的索引中尋找，如果找到了文件，則直接根據(jù)文件所存儲(chǔ)的機(jī)器的 IP 地址建立連接，如果沒有找到，則 SuperNode 把這個(gè)查詢請求發(fā)給它連接的其他超級節(jié)點(diǎn)，直到得到想要的資源 ,KaZaa， POCO 等都是基于這種超級節(jié)點(diǎn)的思想。 圖 6 Gnutella2 的 SuperNode 節(jié)點(diǎn)圖 ? 基于移動(dòng) Agent 的搜索方法 移動(dòng) Agent 是一個(gè)能在異構(gòu)網(wǎng)絡(luò)中自主地從一臺(tái)主機(jī)遷移到另一臺(tái)主機(jī)，并可與其他 Agent或資源進(jìn)行交互的程序。 Agent非常適合在網(wǎng)絡(luò)環(huán)境中來幫助用戶完成信息檢索的任務(wù)?，F(xiàn)在意大利的一些研究人員在移動(dòng) Agent 結(jié)合 P2P方面做了一些 前沿的研究，其中的一些想法，就是通過在 P2P 軟件中嵌入 Agent 的運(yùn)行時(shí)環(huán)境。當(dāng)有節(jié)點(diǎn)需要搜索的時(shí)候，它發(fā)送一個(gè)移動(dòng) Agent 給它相鄰的節(jié)點(diǎn)，移動(dòng) Agent 記錄著它的一些搜索的信息。當(dāng)這個(gè) Agent到達(dá)一臺(tái)新的機(jī)器上，然后在這個(gè)機(jī)器上進(jìn)行資源搜索任務(wù)，如果這臺(tái)機(jī)器上沒有它想要的資源，則它把這些搜索的信息傳給它的鄰節(jié)點(diǎn)，如果找到資源，則返回給請求的機(jī)器。 ? Query Routing 方法 這種方法是一種啟發(fā)式搜索方法。首先每個(gè) Peer 給本節(jié)點(diǎn)的資源做索引，并且紀(jì)錄相鄰節(jié)點(diǎn)的資源信息，當(dāng)查詢到達(dá)的時(shí)候，可以查 詢路由表直接定位到資源的位置，而不需要再次轉(zhuǎn)發(fā)查詢信息。 圖 7Query Routing 方法 三、 P2P 搜索技術(shù)研究的挑戰(zhàn) P2P 搜索技術(shù)中最重要的研究成果應(yīng)該是基于 Small World 理論的非結(jié)構(gòu)化搜索算法和基于 DHT 的結(jié)構(gòu)化搜索算法。尤其是 DHT 及其搜索技術(shù)為資源的組織與查找提供了一種新的方法，在近年來的 P2P 研究領(lǐng)域成為熱點(diǎn)。 隨著 P2P系統(tǒng)實(shí)際應(yīng)用的發(fā)展，物理網(wǎng)絡(luò)中影響路由的一些因素開始影響 P2P 發(fā)現(xiàn)算法的效率。一方面，實(shí)際網(wǎng)絡(luò)中結(jié)點(diǎn)之間體現(xiàn)出較大的差異，即異質(zhì)性。由于客戶機(jī) /服務(wù)器模式在 Inter 和分布式領(lǐng)域十幾年的應(yīng)用和大量種類的電子設(shè)備的普及，如手提電腦、移動(dòng)電話或 PDA。這些設(shè)備在計(jì)算能力、存儲(chǔ)空間和電池容量上差別很大。另外，實(shí)際網(wǎng)絡(luò)被路由器和交換機(jī)分割成不同的自治區(qū)域，體現(xiàn)出嚴(yán)密的層次性。 另一方面，網(wǎng)絡(luò)波動(dòng)的程度嚴(yán)重影響搜索算法的效率。網(wǎng)絡(luò)波動(dòng)（ Churn）包括結(jié)點(diǎn)的加入、退出、失敗、遷移、 并發(fā)加入過程、網(wǎng)絡(luò)分割等。 DHT 的發(fā)現(xiàn)算法如 Chord、 CAN 等都是考慮網(wǎng)絡(luò)波動(dòng)的最差情況下的設(shè)計(jì)與實(shí)現(xiàn)。由于每個(gè)結(jié)點(diǎn)的度數(shù)盡量保持最小，這樣需要響應(yīng)的成員關(guān)系變化的維護(hù)可以比較小，從而可以快速恢復(fù)網(wǎng)絡(luò)波動(dòng)造成的影響。但是每個(gè)結(jié)點(diǎn)僅有少量路由狀態(tài)的代價(jià)是發(fā)現(xiàn)算法的高延時(shí)，因?yàn)槊恳淮尾檎倚枰?lián)系多個(gè)結(jié)點(diǎn)，在穩(wěn)定的網(wǎng)絡(luò)中這種思路是不必要的。 同時(shí)，作為一種資源組織與發(fā)現(xiàn)技術(shù)必然要支持復(fù)雜的查詢，如關(guān)鍵詞、內(nèi)容查詢等。盡管信息檢索和數(shù)據(jù)挖掘領(lǐng)域提供了大量成熟的語義查詢技術(shù)，由于 DHT 精確關(guān)鍵詞映射的特性阻礙了 DHT 在復(fù)雜查詢方面的應(yīng)用。 P2P 搜索方法一直是研究的熱點(diǎn)。一些新的搜索方法不斷的涌現(xiàn)，但是，在資源搜索效率和準(zhǔn)確定位方面還有很大的改善空間，以及基于 P2P 技術(shù)的搜索引擎要達(dá)到現(xiàn)在集中式的搜索引擎 Google，百度這樣廣泛使用還需要一段長時(shí)間的努力。 PeertoPeer 的應(yīng)用研究、面臨的問題與前景展望 一、國外公司與研究機(jī)構(gòu)研究情況 近年來，隨著 Napster、 KaZaa、 BT、 eMule這樣的基于 P2P 技術(shù)的文件共享軟件在 Inter上迅速傳播， P2P 技術(shù)在國際國內(nèi)都引發(fā)了研究的新熱潮。國外開展 P2P 研究的學(xué)術(shù)團(tuán)體主要包括 P2P工作組（ P2PWG）、全球網(wǎng)格論壇 (GGF)以及各高校的研究小組。 P2P工作組成立的主要目的是希望加速 P2P 計(jì)算基礎(chǔ)設(shè)施的建立和相應(yīng)的標(biāo)準(zhǔn)化工作。 P2