葉培順

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

0 引言

P2P網(wǎng)絡(luò)是目前非常流行的網(wǎng)絡(luò)技術(shù)，它的出現(xiàn)對(duì)于分布式計(jì)算乃至整個(gè)因特網(wǎng)的發(fā)展都是一次技術(shù)上的革新，也是一次重大的機(jī)遇和挑戰(zhàn)，因此從P2P技術(shù)誕生的那天起，關(guān)于P2P技術(shù)的研究及應(yīng)用就成為熱點(diǎn)。P2P網(wǎng)絡(luò)最大的特點(diǎn)是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的疏松性，即網(wǎng)絡(luò)節(jié)點(diǎn)的加入和離開(kāi)隨意性很強(qiáng)［1-2］，因此對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的定位及網(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é)點(diǎn)的集中控制，而非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中所有節(jié)點(diǎn)完全是動(dòng)態(tài)不受約束的［3-5］。網(wǎng)絡(luò)結(jié)構(gòu)的不同，所用的資源定位及搜索算法自然不同，非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中節(jié)點(diǎn)可以不受約束地自由地加入和離開(kāi)網(wǎng)絡(luò)，即其網(wǎng)絡(luò)體系結(jié)構(gòu)是分布的、松散的，網(wǎng)絡(luò)結(jié)構(gòu)不可預(yù)測(cè)，從而原始的洪泛法便成為主要的搜索算法［6-7］。洪泛法的優(yōu)點(diǎn)是算法思想簡(jiǎn)單，但是一個(gè)致命的缺陷是會(huì)產(chǎn)生冗余的查詢(xún)數(shù)據(jù)包(下文中簡(jiǎn)稱(chēng)查詢(xún)包)，大量的冗余查詢(xún)信息可能成為網(wǎng)絡(luò)瓶頸而限制網(wǎng)絡(luò)的性能，比如網(wǎng)絡(luò)中資料利用率的下降和搜索效率的降低［8-10］。

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

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

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

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

圖1 樹(shù)形結(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ò)中，當(dāng)節(jié)點(diǎn)的數(shù)目相同時(shí)，節(jié)點(diǎn)的平均度數(shù)是影響冗余查詢(xún)包數(shù)量的唯一因素。在最好的情況下，所有的節(jié)點(diǎn)構(gòu)成一棵樹(shù)，在樹(shù)搜索過(guò)程中不會(huì)產(chǎn)生任何冗余查詢(xún)包。最壞的情況是所有的節(jié)點(diǎn)和邊組成全連通圖，這樣的網(wǎng)絡(luò)會(huì)產(chǎn)生大量冗余數(shù)據(jù)包，因?yàn)樗嬖诤芏喹h(huán)。

1.2 減少冗余的方法

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

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

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

2.1 優(yōu)化網(wǎng)絡(luò)拓?fù)?/h3>

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

在實(shí)際應(yīng)用中，為了減少節(jié)點(diǎn)建立網(wǎng)絡(luò)拓?fù)湫畔⑺Ц兜木S護(hù)費(fèi)用，可以使每個(gè)節(jié)點(diǎn)維護(hù)節(jié)點(diǎn)信息于相對(duì)小的范圍(R值較小)。在本文提出的算法中，讓每個(gè)節(jié)點(diǎn)在2跳范圍內(nèi)維護(hù)網(wǎng)絡(luò)拓?fù)湫畔ⅲ簿褪敲總€(gè)節(jié)點(diǎn)需要記錄它的鄰居節(jié)點(diǎn)N(V)和它的鄰居的鄰居節(jié)點(diǎn)N(N(V))。

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

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

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

圖5 2跳內(nèi)的網(wǎng)絡(luò)拓?fù)湫畔?/p>

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

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

3.1 建立網(wǎng)絡(luò)拓?fù)?/h3>

每個(gè)節(jié)點(diǎn)執(zhí)行一個(gè)簡(jiǎn)單算法，建立一個(gè)節(jié)點(diǎn)在兩跳之內(nèi)的拓?fù)湫畔ⅲ惴ㄖ蠳(I)代表節(jié)點(diǎn)I的鄰居，N(N(I))是節(jié)點(diǎn)I鄰居的鄰居，也就是說(shuō)集合N(N(I))中的所有節(jié)點(diǎn)距離I兩跳之遠(yuǎn)，如節(jié)點(diǎn)I收到一個(gè)來(lái)自節(jié)點(diǎn)J的HELLO message(節(jié)點(diǎn)J加入網(wǎng)絡(luò))，它執(zhí)行以下算法更新網(wǎng)絡(luò)拓?fù)?

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ò)的動(dòng)態(tài)變化，當(dāng)節(jié)點(diǎn)J離開(kāi)網(wǎng)絡(luò)時(shí)，執(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 分段搜索算法

首先用洪泛法進(jìn)行模擬實(shí)驗(yàn)，記錄每一跳下信息覆蓋率和冗余信息，得到閾值T(節(jié)點(diǎn)平均度數(shù)較小時(shí)為4，節(jié)點(diǎn)平均度數(shù)較大時(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 實(shí)驗(yàn)仿真結(jié)果與分析

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

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

圖6 冗余信息對(duì)照?qǐng)D

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

［9］王建勇，龔伏廷，李玉玲.非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中減少冗余的搜索策略［J］.計(jì)算機(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.