劉 衛(wèi)，劉金嶺

（1.昆明理工大學(xué) 計(jì)算機(jī)中心，云南 昆明 650024；2.淮陰工學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 淮安 223003）

分布式P2P網(wǎng)絡(luò)中基于方向搜索算法研究

劉 衛(wèi)1，劉金嶺2

（1.昆明理工大學(xué) 計(jì)算機(jī)中心，云南 昆明 650024；2.淮陰工學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 淮安 223003）

針對Flooding算法及其改進(jìn)算法的理念提出了P2P網(wǎng)絡(luò)中基于方向的搜索算法，該算法動態(tài)生成一棵以搜索源點(diǎn)為根的搜索樹，在每一次的搜索過程中，每個(gè)節(jié)點(diǎn)都能沿著搜索方向進(jìn)行，這樣可以避免節(jié)點(diǎn)被重復(fù)地搜索。有效地避免了搜索過程中冗余搜索報(bào)文的產(chǎn)生，節(jié)省了網(wǎng)絡(luò)帶寬，提高了效率和網(wǎng)絡(luò)性能。通過二維空間的數(shù)字?jǐn)?shù)據(jù)和圖像數(shù)據(jù)這兩種實(shí)驗(yàn)結(jié)果的分析并進(jìn)行了仿真實(shí)驗(yàn)，該算法充分體現(xiàn)了在搜索過程中的有效性及可操作性。

分布式；P2P網(wǎng)絡(luò)；拓?fù)浣Y(jié)構(gòu)；方向搜索

目前人們已經(jīng)意識到P2P技術(shù)[1]在網(wǎng)絡(luò)信息交流、文件交換、分布計(jì)算等方面大有前途。在P2P網(wǎng)絡(luò)上，閑散資源有機(jī)會得到利用，所有節(jié)點(diǎn)的資源總和構(gòu)成了整個(gè)網(wǎng)絡(luò)的資源，整個(gè)網(wǎng)絡(luò)可以被用作具有海量存儲能力和巨大計(jì)算處理能力的超級計(jì)算機(jī)。P2P技術(shù)的另一個(gè)優(yōu)勢是開發(fā)出強(qiáng)大的搜索工具，使用戶深度搜索成為可能，為互聯(lián)網(wǎng)的信息搜索提供了全新的解決方法。運(yùn)用P2P技術(shù)進(jìn)行深度搜索，無需通過WEB服務(wù)器，可以不受信息格式和計(jì)算機(jī)設(shè)備的種種限制，達(dá)到傳統(tǒng)目錄式搜索引擎無可比擬的深度，理論上將包括網(wǎng)絡(luò)上所有開放的信息資源。采用P2P技術(shù)，搜索范圍將在幾秒鐘內(nèi)以幾何級數(shù)增長，幾分鐘內(nèi)就可搜遍幾百萬臺PC上的資源。文獻(xiàn)[2]中給出了分布式結(jié)構(gòu)化網(wǎng)絡(luò)中的Chord搜索算法，其優(yōu)點(diǎn)是算法簡單，性能較好，缺點(diǎn)是隨著節(jié)點(diǎn)規(guī)模的不斷增大，節(jié)點(diǎn)的性能差異會影響系統(tǒng)效率。Flooding算法[3]是分布式P2P網(wǎng)絡(luò)中的一個(gè)基本搜索算法。Flooding搜索算法的優(yōu)點(diǎn)是路由算法簡單且易于實(shí)現(xiàn)；缺點(diǎn)是每一次路由都要進(jìn)行全網(wǎng)遍歷，從而加重網(wǎng)絡(luò)負(fù)擔(dān)，降低搜索效率，限制網(wǎng)絡(luò)擴(kuò)展，使得路由算法容易受到攻擊。正是由于目前P2P網(wǎng)絡(luò)搜索中存在的一系列缺陷，很多研究人員在該領(lǐng)域中做了大量工作，在Flooding算法基礎(chǔ)上出現(xiàn)了一些改進(jìn)算法，如文獻(xiàn)[4]中提到的Modified-BFS、PartialMinFlood等。這些改進(jìn)后的算法在某些特定條件下確實(shí)提高了搜索效率，進(jìn)而提高了網(wǎng)絡(luò)的整體性能。然而，這些改進(jìn)算法中為了實(shí)現(xiàn)某些方面的改進(jìn)而在其他方面付出了昂貴的代價(jià)，主要體現(xiàn)在如下幾個(gè)方面：1）算法過于復(fù)雜，難以實(shí)現(xiàn)；2）算法限制條件太多，實(shí)際網(wǎng)絡(luò)中難以滿足要求；3）對算法的改進(jìn)非常有限。這些算法在目前P2P網(wǎng)絡(luò)中均沒有得到應(yīng)用。文中在現(xiàn)有的研究基礎(chǔ)上，給出了一種基于方向的搜索算法 （記為：Direct_Search），該算法充分利用了網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)的信息，從源節(jié)點(diǎn)到網(wǎng)絡(luò)拓?fù)淇臻g的每一個(gè)方向做平行搜索。在Direct_Search算法中，搜索樹[5]的生成要求網(wǎng)絡(luò)中各節(jié)點(diǎn)知道P2P網(wǎng)絡(luò)的拓?fù)湫畔?，因此該算法的?shí)現(xiàn)需要相應(yīng)的P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的支持。

1 Direct_Search算法的P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)構(gòu)建

分布式結(jié)構(gòu)化 P2P網(wǎng)絡(luò)研究的重點(diǎn)在如何有效地查找信息上。大部分結(jié)構(gòu)化P2P網(wǎng)絡(luò)都采用分布式散列表DHT[6]的資源定位方式。

為了將分布式 P2P網(wǎng)絡(luò)中的資源分布結(jié)構(gòu)化，以利于有效地查找信息，分布式散列表 DHT采取了以下的方法[6]：

1）按照一定的規(guī)則為每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)分配一個(gè)唯一的節(jié)點(diǎn)標(biāo)示符（Node ID），按照散列算法為每個(gè)節(jié)點(diǎn)的資源對象產(chǎn)生一個(gè)唯一的資源對象標(biāo)識符（Object ID）；

2）Node ID與Object ID通過散列函數(shù)將被映射到同一個(gè)分布式散列表中；

3）將分布式散列表分割成不連續(xù)的散列塊，每個(gè)節(jié)點(diǎn)配置一個(gè)散列塊，并且每個(gè)節(jié)點(diǎn)要負(fù)責(zé)維護(hù)屬于自己的散列塊；

4）通過分布式散列表來查找節(jié)點(diǎn)所需要的資源，定位到資源所在的節(jié)點(diǎn)位置；通過特定的路由算法在節(jié)點(diǎn)之間建立連接路徑。

Direct_Search算法在執(zhí)行搜索過程中，會動態(tài)的差生一棵搜索樹，搜索樹的產(chǎn)生要求網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)知道自身在P2P網(wǎng)絡(luò)中的拓?fù)湫畔ⅰＮ闹兴惴ǖ膶?shí)現(xiàn)設(shè)計(jì)了一個(gè)基于笛卡爾坐標(biāo)的P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。該結(jié)構(gòu)的拓?fù)淇臻gS與n維向量空間V十分相似。

筆者對于加入P2P網(wǎng)絡(luò)的節(jié)點(diǎn)按一定的算法映射成n拓?fù)淇臻gS中的一個(gè)點(diǎn)。S中的每個(gè)點(diǎn)都有自己的坐標(biāo)（x1，x2，…，xn），任意兩點(diǎn) N1（x1，x2，…，xn）和 N2（y1，y2，…，yn）的歐式距離d定義為：

對于加入P2P網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)分配一個(gè)坐標(biāo)，該坐標(biāo)唯一對應(yīng)P2P網(wǎng)絡(luò)拓?fù)淇臻gS中的一個(gè)點(diǎn)，節(jié)點(diǎn)與節(jié)點(diǎn)之間的距離定義為與節(jié)點(diǎn)對應(yīng)的點(diǎn)與點(diǎn)之間的歐式距離d。在區(qū)域分布中充分考慮節(jié)點(diǎn)分布的均勻性，所以被添加到P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)將會在n維空間S中通過Hash算法被映射成相應(yīng)的點(diǎn)。

1.1 基本概念

由于在網(wǎng)絡(luò)節(jié)點(diǎn)的加入和退出過程中，需要維護(hù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，為此引出如下超級節(jié)點(diǎn)的定義。

定義1在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中確定唯一個(gè)節(jié)點(diǎn)Super-Node來存儲了該網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中所有節(jié)點(diǎn)的坐標(biāo)、id、ip地址、端口信息等，則稱該節(jié)點(diǎn)Super-Node為該網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的超級節(jié)點(diǎn)。

由于在搜索過程中，節(jié)點(diǎn)的搜索信息量會不斷地增加，這樣會加重Super-Node的負(fù)載量，本文中Super-Node只負(fù)責(zé)存儲節(jié)點(diǎn)加入和離開的信息。

定義2設(shè)N是拓?fù)淇臻gS中的一個(gè)節(jié)點(diǎn)，稱與N相距最遠(yuǎn)鄰居節(jié)點(diǎn)間的距離r為N的視覺搜索半徑；與節(jié)點(diǎn)N之間的距離小于視覺搜索半徑的節(jié)點(diǎn)集合所在區(qū)域稱為N的視覺搜索區(qū)域。如果在某個(gè)搜索區(qū)域內(nèi)，沒有鄰居節(jié)點(diǎn)的存在，則定義這個(gè)搜索區(qū)域的視覺半徑為0。

n維坐標(biāo)的拓?fù)淇臻g S中節(jié)點(diǎn)N的搜索區(qū)域是一個(gè)圓錐體，該圓錐體的頂點(diǎn)即為搜索源節(jié)點(diǎn)，每個(gè)進(jìn)入該搜索區(qū)域的節(jié)點(diǎn)在進(jìn)行搜索的過程中都要對這個(gè)圓錐體搜索區(qū)域負(fù)責(zé)。二維空間的搜索區(qū)域是個(gè)扇形區(qū)，該扇形的頂點(diǎn)為搜索源節(jié)點(diǎn)。

1.2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的節(jié)點(diǎn)加入和移出

當(dāng)節(jié)點(diǎn)Nj申請加入網(wǎng)絡(luò)時(shí)，首先要訪問超級節(jié)點(diǎn)Super-Node，并將自己的信息告知Super-Node。Super-Node隨即為節(jié)點(diǎn)Nj在網(wǎng)絡(luò)空間S中分配位置坐標(biāo)，同時(shí)將節(jié)點(diǎn)Nj的位置信息和鄰居列表信息發(fā)給節(jié)點(diǎn)Nj。Nj加入網(wǎng)絡(luò)后，要判斷是否在其鄰居節(jié)點(diǎn)Ni的搜索區(qū)域內(nèi)，如果節(jié)點(diǎn)Nj在其鄰居節(jié)點(diǎn)Ni的視覺搜索區(qū)域內(nèi)，節(jié)點(diǎn)Nj的信息將會被加入到進(jìn)該視覺搜索區(qū)域的鄰居列表中。如果鄰居列表中的節(jié)點(diǎn)個(gè)數(shù)大于m個(gè)（其中m為鄰居列表存儲搜索信息的最大節(jié)點(diǎn)數(shù)），那么該視覺搜索區(qū)域內(nèi)遠(yuǎn)離節(jié)點(diǎn)Nj的節(jié)點(diǎn)信息將會被超級節(jié)點(diǎn)刪除，隨即超級節(jié)點(diǎn)將通知相應(yīng)的節(jié)點(diǎn)修改其自身的鄰居節(jié)點(diǎn)信息。

當(dāng)節(jié)點(diǎn)要申請移出網(wǎng)絡(luò)時(shí)，該節(jié)點(diǎn)首先要告知Super-Node。Super-Node隨即移去節(jié)點(diǎn)的信息，這時(shí)移去節(jié)點(diǎn)在視覺搜索區(qū)域內(nèi)的鄰居節(jié)點(diǎn)所保存的信息將會有所變動。因?yàn)橐粋€(gè)節(jié)點(diǎn)的移去，網(wǎng)絡(luò)需要進(jìn)行調(diào)整，意味著在視覺搜索區(qū)域內(nèi)的其他節(jié)點(diǎn)會被加入，來保證二叉樹的網(wǎng)絡(luò)結(jié)構(gòu)。Super-Node會為被加入的節(jié)點(diǎn)分配新的位置坐標(biāo)，同時(shí)Super-Node存儲的鄰居列表信息也要實(shí)時(shí)地做出更新來保持網(wǎng)絡(luò)拓?fù)涞臏?zhǔn)確性。

1.3 搜索方向機(jī)搜索區(qū)域

基于方向搜索設(shè)計(jì)的目的是避免節(jié)點(diǎn)被重復(fù)搜索。在每一次的搜索過程中，每個(gè)節(jié)點(diǎn)都要沿著搜索方向進(jìn)行。一個(gè)節(jié)點(diǎn)沿著其搜索方向進(jìn)行搜索的區(qū)域我們稱為該節(jié)點(diǎn)負(fù)責(zé)的搜索區(qū)域。n維拓?fù)淇臻gS中的節(jié)點(diǎn)N的搜索區(qū)域是一個(gè)以搜索源點(diǎn)為頂點(diǎn)的錐體，在搜索過程中，每個(gè)參與節(jié)點(diǎn)分別負(fù)責(zé)一個(gè)錐體搜索區(qū)域。下面以二維空間為例，說明搜索方向和搜索區(qū)域的確定。在二維拓?fù)淇臻gS中，搜索區(qū)域是一個(gè)以搜索源點(diǎn)為中心的扇形，搜索沿著遠(yuǎn)離搜索源點(diǎn)的方向進(jìn)行。如圖1所示。

圖1 搜索方向和搜索區(qū)域示意圖Fig.1 Schematic diagram of direction search and searching area

1.4 下一跳基于方向搜索節(jié)點(diǎn)的選擇

當(dāng)前節(jié)點(diǎn)的下一跳基于方向搜索節(jié)點(diǎn)的計(jì)算是比較關(guān)鍵的步驟。計(jì)算的方法是：從當(dāng)前節(jié)點(diǎn)的鄰居列表里取出一個(gè)鄰居節(jié)點(diǎn)N，根據(jù)該鄰居節(jié)點(diǎn)的坐標(biāo)和當(dāng)前節(jié)點(diǎn)的搜索區(qū)域的邊界平面方程，計(jì)算出該鄰居節(jié)點(diǎn)是否在當(dāng)前節(jié)點(diǎn)的搜索區(qū)域中。如果該鄰居節(jié)點(diǎn)N在當(dāng)前節(jié)點(diǎn)的搜索區(qū)域中，則進(jìn)一步根據(jù)該鄰居節(jié)點(diǎn)的坐標(biāo)和當(dāng)前節(jié)點(diǎn)的搜索方向直線方程判斷該鄰居節(jié)點(diǎn)K是否在當(dāng)前節(jié)點(diǎn)的搜索方向上。如果在搜索方向上，則該鄰居節(jié)點(diǎn)符合條件，是當(dāng)前節(jié)點(diǎn)的下一跳搜索節(jié)點(diǎn)。否則，該鄰居節(jié)點(diǎn)不是當(dāng)前節(jié)點(diǎn)的下一跳搜索節(jié)點(diǎn)。

2 分布式P2P網(wǎng)絡(luò)中基于方向的搜索算法Direct_Search

Direct_Search的設(shè)計(jì)思想是把 P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)映射到二維空間坐標(biāo)的平面上，在這個(gè)二維空間坐標(biāo)上的每個(gè)節(jié)點(diǎn)都會被分配一個(gè)二維空間坐標(biāo)，以此來標(biāo)注其在空間中的位置。在整個(gè)算法中只設(shè)置一個(gè)超級節(jié)點(diǎn)，想要進(jìn)入 P2P網(wǎng)絡(luò)的每一個(gè)節(jié)點(diǎn)首先要和超級節(jié)點(diǎn)進(jìn)行通信，在通信的過程中超級節(jié)點(diǎn)會為該節(jié)點(diǎn)在 P2P網(wǎng)絡(luò)的應(yīng)用層分配一個(gè)二維坐標(biāo)。同時(shí)，Direct_Search在P2P網(wǎng)絡(luò)中的資源定位也是以節(jié)點(diǎn)被分配的坐標(biāo)為基礎(chǔ)的。把這個(gè)二維空間坐標(biāo)平面分成4個(gè)象限，該算法是以搜索源節(jié)點(diǎn)作為根節(jié)點(diǎn)，以4個(gè)象限內(nèi)的節(jié)點(diǎn)作為葉節(jié)點(diǎn)，并在每個(gè)象限內(nèi)生成一棵二叉樹，搜索過程根據(jù)二叉樹模型進(jìn)行搜索，這一想法在 Direct_Search能夠有效地避免發(fā)送重復(fù)的搜索消息而造成冗余所帶來的網(wǎng)絡(luò)高負(fù)載。同時(shí)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都被設(shè)置了若干個(gè)鄰居節(jié)點(diǎn)，其只能從它的鄰居節(jié)點(diǎn)獲取搜索消息，并不需要整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)的所有消息，這一想法使得 Direct_Search具有很好的可擴(kuò)展性和穩(wěn)定性，同時(shí)能夠很好地適應(yīng) P2P網(wǎng)絡(luò)的動態(tài)變化。在整個(gè)搜索過程中，搜索的起點(diǎn)是搜索的源節(jié)點(diǎn)。該算法充分地利用網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)的信息，從源節(jié)點(diǎn)到網(wǎng)絡(luò)拓?fù)淇臻g的每一個(gè)方向做平行搜索。Direct_Search算法流程如圖2所示。

圖2 Direct_Search算法執(zhí)行的流程圖Fig.2 Direct_search algorithm on execution flowchart

Direct_Search算法在二維空間內(nèi)的搜索算法描述如下：

1）從搜索源節(jié)點(diǎn)出發(fā)，搜索開始。搜索源節(jié)點(diǎn)根據(jù)其鄰居節(jié)點(diǎn)的存儲信息和一些搜索參數(shù)計(jì)算下一個(gè)被搜索的節(jié)點(diǎn)，下一個(gè)被搜索的區(qū)域以及下一個(gè)被搜索節(jié)點(diǎn)所負(fù)責(zé)的搜索方向，然后跳轉(zhuǎn)至步驟2）。

2）如果經(jīng)過步驟1）計(jì)算出的下一跳節(jié)點(diǎn)的數(shù)量為0，則跳轉(zhuǎn)至步驟4）；如果經(jīng)過步驟 1）計(jì)算的下一跳節(jié)點(diǎn)的數(shù)量不為 0，則搜索消息將被發(fā)送給這些“下一跳節(jié)點(diǎn)”，然后跳轉(zhuǎn)至步驟3）。

3）接收到搜索消息的節(jié)點(diǎn)進(jìn)行本地文件搜索，搜索到符合條件的文件，搜索結(jié)果將被返回至搜索源節(jié)點(diǎn)，然后跳轉(zhuǎn)至步驟4）；搜索不到符合條件的文件，那么就會執(zhí)行步驟1）中的搜索操作，計(jì)算出的結(jié)果生成搜索文件，發(fā)送給下一跳節(jié)點(diǎn)。

4）搜索在現(xiàn)有節(jié)點(diǎn)負(fù)責(zé)的搜索區(qū)域內(nèi)結(jié)束。

5）搜索在各個(gè)搜索區(qū)域內(nèi)都被完成時(shí)，整個(gè)搜索結(jié)束。

3 Direct_Search 算法在二維空間內(nèi)的模擬實(shí)驗(yàn)及結(jié)果分析

本次模擬實(shí)驗(yàn)的主要目的是對Direct_Search算法在搜索執(zhí)行過程中的覆蓋率進(jìn)行定量分析，從而驗(yàn)證該算法的正確性和可行性，同時(shí)因?yàn)樵谒惴▓?zhí)行的整個(gè)過程中沒有涉及到P2P網(wǎng)絡(luò)通信協(xié)議的模擬情況，為了達(dá)到簡潔高效更加直觀的驗(yàn)證該算法，文中是Intel Core i3主頻為2.93 GHz的雙核處理器、內(nèi)存為4 GB、操作系統(tǒng)為Windows XP Server Pack3、開發(fā)語言C++的機(jī)器上進(jìn)行的，通過編寫程序來模擬算法搜索執(zhí)行過程，獲取實(shí)驗(yàn)數(shù)據(jù)的。

3.1 模擬實(shí)驗(yàn)結(jié)果分析

在對Direct_Search算法的五次模擬實(shí)驗(yàn)過程中，不考慮網(wǎng)絡(luò)的邊緣節(jié)點(diǎn)，在網(wǎng)絡(luò)中設(shè)置了10 000個(gè)搜索節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)設(shè)定存儲了48個(gè)鄰居節(jié)點(diǎn)的信息，即取m=48。實(shí)驗(yàn)數(shù)據(jù)如表1所示。搜索覆蓋率S_C用式（2）表示。

表1 Direct_Search算法的五次模擬實(shí)驗(yàn)數(shù)據(jù)Tab.1 Direct_search algorithm of five times simulation experiment data

表1中的實(shí)驗(yàn)數(shù)據(jù)說明了Direct_Search算法的搜索覆蓋率在95%左右。

3.2 Direct_Search算法的搜索過程仿真實(shí)驗(yàn)

圖3顯示了采用Direct_Search算法進(jìn)行搜索的仿真過程。圖中的星號代表網(wǎng)絡(luò)節(jié)點(diǎn)，星號下邊的數(shù)字是該節(jié)點(diǎn)的id。該圖顯示的是從圖的右上方節(jié)點(diǎn)向左下方節(jié)點(diǎn)進(jìn)行的搜索過程。兩個(gè)節(jié)點(diǎn)之間有連線，表示在搜索過程中，其中一個(gè)節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)的下一跳節(jié)點(diǎn)。圖中有些節(jié)點(diǎn)是孤立節(jié)點(diǎn)，既沒有直線把它和別的節(jié)點(diǎn)連起來。這些孤立節(jié)點(diǎn)就是在搜索中被忽略的節(jié)點(diǎn)。在圖3中，許多節(jié)點(diǎn)只有上一跳節(jié)點(diǎn)，沒有下一跳的節(jié)點(diǎn)。這表示在搜索過程中，這些節(jié)點(diǎn)沒有在自己的搜索區(qū)域中找到符合條件的下一跳節(jié)點(diǎn)，搜索在這些節(jié)點(diǎn)處中斷。在搜索過程中，參與搜索的節(jié)點(diǎn)所負(fù)責(zé)的搜索區(qū)域?yàn)樯刃?。在搜索中斷處，那些比?dāng)前節(jié)點(diǎn)距離搜索源點(diǎn)更遠(yuǎn)的、在搜索區(qū)域中的節(jié)點(diǎn)，是無法被搜索到的。

圖3 Direct_Search搜索過程仿真實(shí)驗(yàn)圖Fig.3 Experimental graph of direct_search process in simulation

4 結(jié)束語

最近幾年，P2P技術(shù)得到了極大的發(fā)展，P2P技術(shù)作為一種應(yīng)用日益廣泛的技術(shù)，其功能﹑性能逐漸得到人們的重視。由于P2P運(yùn)行環(huán)境比較復(fù)雜，所以到目前為止，在國際上還沒有一個(gè)通用P2P搜索方法。筆者根據(jù)Flooding算法及其改進(jìn)算法的理念提出了P2P網(wǎng)絡(luò)中基于方向的搜索算法—Direct_Search算法，講述了Direct_Search算法的基本思想，設(shè)計(jì)的詳細(xì)過程，并對其進(jìn)行了模擬實(shí)驗(yàn)以及實(shí)驗(yàn)結(jié)果分析。由于P2P網(wǎng)絡(luò)的搜索是現(xiàn)今研究的一個(gè)熱點(diǎn)，P2P網(wǎng)絡(luò)的搜索方面的研究還在探索中，尤其在資源搜索效率和準(zhǔn)確定位方面還有很大的改善空間。

[1]劉金嶺.基于P2P網(wǎng)絡(luò)的AVL索引樹范圍查詢研究[J].微電子學(xué)與計(jì)算機(jī)，2011，28（2）:11-14.

LIU Jin-ling.Study of the AVL-index tree range query based on P2P networks[J].Microelectronics and Computer，2011，28（2）:11-14.

[2]劉金嶺.基于Chord覆蓋網(wǎng)絡(luò)索引結(jié)構(gòu)的多屬性查詢[J].微電子學(xué)與計(jì)算機(jī)，2011，28（3）:104-107.

LIU Jin-ling.An index structure based on chord overlay network of multi-attribute query[J].Microelectronics and Computer，2011，28（3）:104-107.

[3]Kim H，Kim Y.Restricted path flooding scheme in distributed P2P overlay networks[C]//ICISS 2008:International Conference on Information Science and Security Proceedings，2008:58-61.

[4]Gkantsid I S C，Miha I LM，Saber I A.Hybrid search schemes for unstructured peer-to-peer networks[C]//Proc of IEEE INFOCOM.Miami:IEEE Press，2005:1526-1537.

[5]吳艾，劉心松，郝堯，等.P2ST:基于帶權(quán)搜索樹的P2P搜索模型[J].計(jì)算機(jī)科學(xué)，2007，34（8）:64-68.

WU Ai， LIU Xin-song， HAO Yao， et al.P2ST:A weighted search tree based P2P searching model[J].Computer Science，2007，34（8）:64-68.

[6]李士寧，夏貽勇，杜艷麗.對等網(wǎng)絡(luò)中DHT搜索算法綜述[J].計(jì)算機(jī)應(yīng)用研究，2008，25（6）:1611-1615.

LI Shi-ning， XIA Yi-yong， DU Yan-li.Survey of DHT search algorithm in peer-to-peer network [J].Application Research of Computers，2008，25（6）:1611-1615.

Based on research of direction algorithm research in distributed P2P network

Flooding algorithm and its improved algorithm based on the concept of P2P networks is proposed based on the direction of the search algorithm,which dynamically generate a source point to search for the root of the search tree,the search along the search tree,the search process effectively avoided redundant search packets in the production,save network bandwidth and improve the efficiency and network performance.By two-dimensional digital data and image data analysis of the two experimental results fully reflected the algorithm in the search process for effectiveness and feasibility

distributed； P2P networks； topology； direction search

TP393

A

1674－6236（2011）24-0078-04

2011-10-12 稿件編號：201110048

武漢工程大學(xué)青年基金（Q200802）

劉 衛(wèi)（1965—），女，云南昆明人，副教授。研究方向：網(wǎng)絡(luò)結(jié)構(gòu)/數(shù)據(jù)挖掘。LIU Wei1，LIU Jin-ling2

（1.Computer Center,Kunming University of Science and Technology,Kunming650024,China；

2.Computer Engineering Faculty,Huaiyin Institute of Technology,Huaian223003,China）