非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的一種改進搜索算法

葉培順

(榆林學(xué)院信息工程學(xué)院，陜西 榆林 719000)

0 引言

P2P網(wǎng)絡(luò)是目前非常流行的網(wǎng)絡(luò)技術(shù)，它的出現(xiàn)對于分布式計算乃至整個因特網(wǎng)的發(fā)展都是一次技術(shù)上的革新，也是一次重大的機遇和挑戰(zhàn)，因此從P2P技術(shù)誕生的那天起，關(guān)于P2P技術(shù)的研究及應(yīng)用就成為熱點。P2P網(wǎng)絡(luò)最大的特點是網(wǎng)絡(luò)拓撲結(jié)構(gòu)的疏松性，即網(wǎng)絡(luò)節(jié)點的加入和離開隨意性很強［1-2］，因此對網(wǎng)絡(luò)中節(jié)點的定位及網(wǎng)絡(luò)資源的搜索技術(shù)成為P2P網(wǎng)絡(luò)中最關(guān)鍵的技術(shù)。

P2P網(wǎng)絡(luò)從網(wǎng)絡(luò)結(jié)構(gòu)的角度可以分為結(jié)構(gòu)化P2P網(wǎng)絡(luò)和非結(jié)構(gòu)化P2P網(wǎng)絡(luò)兩種，結(jié)構(gòu)化P2P網(wǎng)絡(luò)中其網(wǎng)絡(luò)結(jié)構(gòu)受某些節(jié)點的集中控制，而非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中所有節(jié)點完全是動態(tài)不受約束的［3-5］。網(wǎng)絡(luò)結(jié)構(gòu)的不同，所用的資源定位及搜索算法自然不同，非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中節(jié)點可以不受約束地自由地加入和離開網(wǎng)絡(luò)，即其網(wǎng)絡(luò)體系結(jié)構(gòu)是分布的、松散的，網(wǎng)絡(luò)結(jié)構(gòu)不可預(yù)測，從而原始的洪泛法便成為主要的搜索算法［6-7］。洪泛法的優(yōu)點是算法思想簡單，但是一個致命的缺陷是會產(chǎn)生冗余的查詢數(shù)據(jù)包(下文中簡稱查詢包)，大量的冗余查詢信息可能成為網(wǎng)絡(luò)瓶頸而限制網(wǎng)絡(luò)的性能，比如網(wǎng)絡(luò)中資料利用率的下降和搜索效率的降低［8-10］。

為了在P2P網(wǎng)絡(luò)中有效定位資源，研究P2P搜索的問題主要從兩個方面進行:一是通過改變P2P網(wǎng)絡(luò)結(jié)構(gòu)，達到提高搜索效率的目的，而另一種是優(yōu)化一些現(xiàn)有的搜索方法。在本文中，首先分析在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中冗余的查詢包出現(xiàn)的原因，進而提出優(yōu)化算法(稱之為分段搜索本文算法)來減少或部分消除冗余查詢包，然后對算法進行實驗?zāi)M。最后，將通過實驗數(shù)據(jù)說明優(yōu)化后的效果。

1 非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的冗余分析

1.1 產(chǎn)生冗余的原因

搜索過程中之所以產(chǎn)生冗余查詢包，是因為網(wǎng)絡(luò)中存在環(huán)。如圖1～圖4所示的具有4個節(jié)點的網(wǎng)絡(luò)中，圖1是一個樹形結(jié)構(gòu)，沒有環(huán)，查詢信息由節(jié)點A直接傳送到C、D、B，不會產(chǎn)生冗余查詢包;圖2中C、D間有環(huán)路，它們之間所傳送的查詢信息便成為網(wǎng)絡(luò)中的冗余包;圖3中具有雙環(huán);圖4是一個復(fù)雜的全網(wǎng)狀結(jié)構(gòu)(全連通圖)，圖中虛線箭頭指向的節(jié)點均會收到冗余查詢包。

圖1 樹形結(jié)構(gòu)

圖2 單環(huán)結(jié)構(gòu)

圖3 雙環(huán)結(jié)構(gòu)

圖4 全網(wǎng)狀結(jié)構(gòu)

根據(jù)以上的分析，可以看到，在網(wǎng)絡(luò)中，當節(jié)點的數(shù)目相同時，節(jié)點的平均度數(shù)是影響冗余查詢包數(shù)量的唯一因素。在最好的情況下，所有的節(jié)點構(gòu)成一棵樹，在樹搜索過程中不會產(chǎn)生任何冗余查詢包。最壞的情況是所有的節(jié)點和邊組成全連通圖，這樣的網(wǎng)絡(luò)會產(chǎn)生大量冗余數(shù)據(jù)包，因為它存在很多環(huán)。

1.2 減少冗余的方法

根據(jù)以上分析，可以得出結(jié)論，減少P2P網(wǎng)絡(luò)中的冗余數(shù)據(jù)包的理想方法是減少循環(huán)直到完全消除網(wǎng)絡(luò)中所有的環(huán)路。如果能夠建立一棵生成樹從根節(jié)點發(fā)動搜索，可以完全消除網(wǎng)絡(luò)回路從而完全消除在網(wǎng)絡(luò)上的冗余數(shù)據(jù)包［11-12］。

由于P2P網(wǎng)絡(luò)的動態(tài)變化，節(jié)點的加入和離開的不確定性，節(jié)點擁有的各種網(wǎng)絡(luò)資源不同，節(jié)點的網(wǎng)絡(luò)處理能力也不同，因此使用當前的活動節(jié)點為根節(jié)點來建立生成樹是不可能的。然而，可以通過優(yōu)化原始的洪泛搜索來減少冗余查詢包，從而消除或部分消除冗余。

2 對洪泛法優(yōu)化的策略

2.1 優(yōu)化網(wǎng)絡(luò)拓撲

為了減少冗余查詢包，一個簡單的方法是讓每個節(jié)點維護在R跳之內(nèi)的鄰居節(jié)點信息，以此建立一棵生成樹［13-14］。這將確保在R跳之內(nèi)每個節(jié)點只接收一次查詢包，從而不產(chǎn)生冗余查詢消息。

在實際應(yīng)用中，為了減少節(jié)點建立網(wǎng)絡(luò)拓撲信息所支付的維護費用，可以使每個節(jié)點維護節(jié)點信息于相對小的范圍(R值較小)。在本文提出的算法中，讓每個節(jié)點在2跳范圍內(nèi)維護網(wǎng)絡(luò)拓撲信息，也就是每個節(jié)點需要記錄它的鄰居節(jié)點N(V)和它的鄰居的鄰居節(jié)點N(N(V))。

2.2 建立節(jié)點的前向列表

源節(jié)點首先構(gòu)建其前向列表，然后發(fā)送查詢信息給它的鄰居節(jié)點，當收到查詢信息后，利用拓撲信息，位于源節(jié)點前向列表中的節(jié)點構(gòu)建自己的前向列表，具體策略如下:

在圖5中，假設(shè)Vi為源節(jié)點，發(fā)送查詢包給Vj，Vj處理查詢并建立自己的前向列表N(Vj);當Vj建立N(Vj)時，它會選擇集合B(Vj，Vi)，也就是N(Vj)–(N(Vj)∩N(Vi))中的一些節(jié)點加入N(Vj);當Vj傳送查詢時，將查詢信息發(fā)給B(Vj，Vi)中所有節(jié)點(洪泛法將查詢發(fā)給所有N(Vj)中節(jié)點);如:Vi發(fā)查詢給Vj和Vk，由于Vk∈N(Vi)，因此Vj不會再將查詢發(fā)給Vk，可以消除像圖2中那樣的環(huán)。

圖5 2跳內(nèi)的網(wǎng)絡(luò)拓撲信息

按此策略構(gòu)建前向列表時存在這樣一個問題:假設(shè)Vj和Vm∈N(Vi)，Vj和Vm傳送查詢給各自的鄰居，由于 Vq∈N(Vj)，Vq∈N(Vm)，因此 Vj和 Vm 都會發(fā)查詢消息給Vq，結(jié)果產(chǎn)生如圖2中的冗余。對此解決的辦法是:從Vj和Vm中選擇IP地址較小者傳送查詢給Vq，另一個則不做任何動作。

3 分段搜索算法設(shè)計

3.1 建立網(wǎng)絡(luò)拓撲

每個節(jié)點執(zhí)行一個簡單算法，建立一個節(jié)點在兩跳之內(nèi)的拓撲信息，算法中N(I)代表節(jié)點I的鄰居，N(N(I))是節(jié)點I鄰居的鄰居，也就是說集合N(N(I))中的所有節(jié)點距離I兩跳之遠，如節(jié)點I收到一個來自節(jié)點J的HELLO message(節(jié)點J加入網(wǎng)絡(luò))，它執(zhí)行以下算法更新網(wǎng)絡(luò)拓撲:

Step1 Add the ID of node J to the neighbor nodes set of node I，namely set N(I);

Step2 Add the ID of node J neighbor nodes to the set N(N(I));

Step3 Eliminate the common elements of set N(I)and set N(N(I))from set N(N(I))，namely N(N(I))=N(N(I))–(N(N(I))N(I)).

為了反映網(wǎng)絡(luò)的動態(tài)變化，當節(jié)點J離開網(wǎng)絡(luò)時，執(zhí)行以下算法:

Step1 Eliminate the ID of node J from the neighbor nodes set of node I，namely set N(I);

Step2 Eliminate the common elements of set N(J)and set N(N(I))from set N(N(I))，namely N(N(I))=N(N(I))–(N(N(I))N(J)).

3.2 分段搜索算法

首先用洪泛法進行模擬實驗，記錄每一跳下信息覆蓋率和冗余信息，得到閾值T(節(jié)點平均度數(shù)較小時為4，節(jié)點平均度數(shù)較大時為3)和發(fā)送的總跳數(shù)H。算法描述如下:

(1)Set the hop of the current forwarding stage is h.If h is less than the threshold value T，the current node will forward the search news to all of its neighbor nodes，but not to the node that forwarding the current search news to it.

(2)If the hop h is equivalent to or greater than the threshold value T，and suppose the current node Vi has received the message that forwarded from its neighbor node Vj，then node Vi constructs its own forward-list as follows:

Step1 Check the value of h.If h is equivalent to H，turn to step 5;otherwise go to step 2;

Step2 Check whether node Vi is in the forwardlist of node Vj.If it is in，go to step 3;otherwise turn to step 5;

Step3 Construct the forward-list F(Vi)of node Vi:

3.1 Initialize the forward-list of node Vi with NULL，namely F(Vi)={U}.Judge whether the node Vi is a leaf node.If Vi is a leaf node，turn to step 5;otherwise go to step 3.2;

3.2 Construct the set N(Vi)–(N(Vj)N(Vi))according to the topology information within two hops that node Vi knows.For a certain node in set N(Vj)–(N(Vj)N(Vi))，if it has neighbor nodes in set F(Vj)–{Vi}，join the node to set NIP(Vi).Then dispose the nodes in set N(Vi)–(N(Vj)N(Vi))one by one according to the following rules:

3.2.1 If the node is not in the set NIP(Vi)，join the node to the forward-list F(Vi)of node Vi;otherwise goto step 3.2.2;

3.2.2 If the node is in the set NIP(Vi)，then it has one or more neighbor nodes in the set F(Vj)–{Vi}.Find the smallest IP address node V in those neighbor nodes，and compare the IP address of the node V with that of node Vi.If the IP address of node Vi is smaller，join the current node to node Vi forward-list F(Vi);otherwise do nothing;

Step4 So far the node Vi forward-list F(Vi)is constructed completely.The node Vi will forward the search news only to the nodes in its forward-list F(Vi);

Step5 The end.

4 實驗仿真結(jié)果與分析

首先用原始的洪泛法，在同一網(wǎng)絡(luò)環(huán)境中不斷改變節(jié)點的平均度數(shù)，記錄不同的條件下網(wǎng)絡(luò)中所產(chǎn)生的冗余查詢包，然后用3.2節(jié)中提出的算法做相同的工作，最后得出結(jié)論:在網(wǎng)絡(luò)條件相同的情況下搜索過程所產(chǎn)生的查詢?nèi)哂喟?，分段搜索算法遠遠少于洪泛法。表1和表2分別給出了在不同的跳數(shù)和不同的節(jié)點平均度情況下洪泛法和分段法在搜索過程中所產(chǎn)生的冗余包，圖6為兩種算法的冗余信息對照結(jié)果。

表2 分段搜索算法搜索產(chǎn)生的冗余包

圖6 冗余信息對照圖

5 結(jié)束語

在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，洪泛法因其節(jié)點信息覆蓋率高，查詢反饋快，成為基本的搜索算法，然而洪泛法最大的問題在于搜索過程中產(chǎn)生大量的查詢?nèi)哂喟?，過度地消耗了網(wǎng)絡(luò)資源。本文對洪泛法進行了研究，在查詢達到最大跳數(shù)H過程中，對當前每一跳的信息覆蓋率和冗余信息予以分析，進而對洪泛法加以改進得出分段搜索算法。在此改進算法中，每個節(jié)點定期發(fā)出HELLO message，這和傳統(tǒng)洪泛法相比增加了處理HELLO message的網(wǎng)絡(luò)開銷，但是分段搜索可以明顯減少查詢中冗余信息的產(chǎn)生，因此認為處理HELLO message的網(wǎng)絡(luò)開銷是值得付出的。

［1］馬文明，孟祥武，張玉潔.面向非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的雙向隨機漫步搜索機制［J］.軟件學(xué)報，2012，23(4):894-911.

［2］楊正華，丁雷，孟凡斌，等.非結(jié)構(gòu)化P2P資源搜索策略研究［J］.微計算機信息，2012，28(2):102-104.

［3］王亞民，趙顯亮.一種基于小世界理論的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)文本檢索算法［J］.圖書情報工作，2011，55(5):113-117.

［4］邵國金，高俊，曾家國.基于文件分類的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)搜索算法［J］.河南師范大學(xué)學(xué)報:自然科學(xué)版，2011，39(5):165-168，175.

［5］崔來中，吳建平，江勇，等.一種非結(jié)構(gòu)化P2P流媒體系統(tǒng)拓撲構(gòu)建算法［J］.清華大學(xué)學(xué)報:自然科學(xué)版，2011，51(12):1819-1823.

［6］許曉東，程建國，朱士瑞.非結(jié)構(gòu)化P2P僵尸網(wǎng)絡(luò)魯棒性分析［J］.計算機應(yīng)用，2011，31(12):3343-3345.

［7］劉丹，謝文君.非結(jié)構(gòu)化P2P網(wǎng)絡(luò)下的空間范圍查詢［J］.計算機工程與應(yīng)用，2010，46(30):89-91，94.

［8］姚全珠，李薇，孔偉.非結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)通信協(xié)議研究［J］.計算機工程與應(yīng)用，2011，47(7):99-102.

［9］王建勇，龔伏廷，李玉玲.非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中減少冗余的搜索策略［J］.計算機工程與應(yīng)用，2010，46(36):122-125.

［10］Rhea S，Wells C，Eaton P，et al.Maintenance-free global data storage［J］.IEEE Internet Computing，2001，5(5):40-49.

［11］Lamport L，Shostak R，Pease M.The Byzantine generals problem［J］.ACM Transactions on Programming Languages and Systems，1982，4(3):382-401.

［12］Emil S，Robert M.Security considerations for peer-to-peer distributed Hash tables［C］//Proceedings of the First International Workshop on Peer-to-Peer Systems.2002:261-269.

［13］Ratnasamy S，Shenker S，Stoica I.Routing algorithms for DHTs:Some open questions［C］//Proceedings of the First International Workshop on Peer-to-Peer Systems.2002:45-52.

［14］Castro M，Druschel P，Kermarrec A M，et al.SCRIBE:A large-scale and decentralized application-level multicast infrastructure［J］.IEEE Journal of Selected Areas in Communications，2002，20(8):1489-1499.