基于反饋的非結(jié)構(gòu)化Ｐ２Ｐ網(wǎng)絡(luò)混合搜索算法

摘要：為了提高P2P網(wǎng)絡(luò)搜索效率和有效地減少冗余消息，提出一種基于反饋的混合搜索算法，將查詢消息在某些高度數(shù)節(jié)點(diǎn)處轉(zhuǎn)發(fā)給多個(gè)鄰居節(jié)點(diǎn)而在其他節(jié)點(diǎn)處只轉(zhuǎn)發(fā)給一個(gè)鄰居節(jié)點(diǎn)，并且在搜索過(guò)程中利用先前搜索的反饋信息來(lái)指導(dǎo)搜索，以選擇能夠返回最多最近響應(yīng)結(jié)果的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息。算法分析和實(shí)驗(yàn)結(jié)果表明，該算法不僅實(shí)現(xiàn)了較高的成功率、響應(yīng)率和搜索效率，還能有效地減少冗余消息，并且具有良好的自適應(yīng)能力，能快速適應(yīng)不斷變化的網(wǎng)絡(luò)行為。

關(guān)鍵詞：對(duì)等網(wǎng)絡(luò)； 混合搜索； 反饋； 自適應(yīng)能力

中圖分類號(hào)：TP31文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)03－0872－04

Gnutella等大多數(shù)非結(jié)構(gòu)化P2P網(wǎng)絡(luò)采用一種稱為洪泛（flooding）的搜索算法。該算法在搜索時(shí)向所有的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢消息，因此又叫寬度優(yōu)先搜索（BFS）算法。洪泛搜索算法導(dǎo)致大量呈指數(shù)增長(zhǎng)的消息產(chǎn)生，冗余消息多，浪費(fèi)了大量不必要的網(wǎng)絡(luò)帶寬，使得Gnutella不可擴(kuò)展。類似的P2P網(wǎng)絡(luò)搜索算法還有iterative deepening[1]和lightFlood[2]等。

現(xiàn)有的大多數(shù)P2P網(wǎng)絡(luò)搜索算法都致力于減少由洪泛操作產(chǎn)生的冗余消息。這些算法大致可分為兩大類[3]：a)BFSlike算法，如directed BFS[1]、modifiedBFS[4]等，在搜索時(shí)只選擇部分鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息；b)DFSlike算法，如random walk[5]、APS[6]和preferential walk[7]等，在搜索時(shí)僅選擇一個(gè)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息。

盡管BFSlike算法通過(guò)適當(dāng)縮小搜索寬度來(lái)減少消息，但其消息數(shù)量仍然呈指數(shù)增長(zhǎng)，冗余消息比例大，因而仍不能有效地減少冗余消息。DFSlike算法雖然能夠顯著地降低消息數(shù)量，但因訪問(wèn)節(jié)點(diǎn)較少而使得響應(yīng)率較低。因此這兩類算法都不能很好地同時(shí)滿足低冗余消息和高響應(yīng)率的要求，使得整體性能不是很高。為此，本文提出一種采用混合搜索策略和反饋機(jī)制的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)搜索算法，將查詢消息在某些高度數(shù)節(jié)點(diǎn)處轉(zhuǎn)發(fā)給一部分鄰居節(jié)點(diǎn)，而在其他節(jié)點(diǎn)處只轉(zhuǎn)發(fā)給一個(gè)鄰居節(jié)點(diǎn)，并且在搜索過(guò)程中利用先前搜索的反饋信息來(lái)指導(dǎo)當(dāng)前搜索、選擇能夠返回最多最近響應(yīng)結(jié)果的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，以有效地減少冗余消息和提高搜索效率。

1基于反饋的P2P網(wǎng)絡(luò)混合搜索算法

1．1混合搜索策略

考慮到大多數(shù)P2P網(wǎng)絡(luò)滿足power law節(jié)點(diǎn)度數(shù)分布特性（即網(wǎng)絡(luò)中存在小部分節(jié)點(diǎn)具有很高的節(jié)點(diǎn)度數(shù)，另外大部分節(jié)點(diǎn)度數(shù)相對(duì)較低），高度數(shù)節(jié)點(diǎn)數(shù)量少，鄰居節(jié)點(diǎn)多，對(duì)高度數(shù)節(jié)點(diǎn)適合使用BFS策略進(jìn)行搜索；而其他節(jié)點(diǎn)度數(shù)較低，鄰居節(jié)點(diǎn)少，對(duì)低度數(shù)節(jié)點(diǎn)適合使用DFS策略進(jìn)行搜索，本文提出一種混合搜索策略：讓P2P網(wǎng)絡(luò)中高度數(shù)節(jié)點(diǎn)在搜索時(shí)使用BFS策略，而讓其他節(jié)點(diǎn)在搜索時(shí)使用DFS策略。

關(guān)鍵問(wèn)題是如何確定在搜索時(shí)使用BFS策略的高度數(shù)節(jié)點(diǎn)。顯然，不可能采用通過(guò)網(wǎng)絡(luò)統(tǒng)計(jì)所有節(jié)點(diǎn)的度數(shù)再進(jìn)行篩選的方法，但一個(gè)節(jié)點(diǎn)可以很容易地獲知其鄰居節(jié)點(diǎn)的度數(shù)。因此，本文將那些節(jié)點(diǎn)度數(shù)不小于其任何一個(gè)鄰居節(jié)點(diǎn)的度數(shù)的節(jié)點(diǎn)看成高度數(shù)節(jié)點(diǎn)，這些節(jié)點(diǎn)在搜索時(shí)使用BFS策略。

設(shè)節(jié)點(diǎn)度數(shù)為n的節(jié)點(diǎn)N，通過(guò)函數(shù)dmax(N)求取該節(jié)點(diǎn)所有鄰居節(jié)點(diǎn)度數(shù)的最大值，并且引入一個(gè)參數(shù)p（0

h=f(N，n)=1if (n

p×nif (n≥dmax(N))（1）

即當(dāng)節(jié)點(diǎn)N在轉(zhuǎn)發(fā)一條查詢消息時(shí)，如果N的節(jié)點(diǎn)度數(shù)不小于其鄰居節(jié)點(diǎn)度數(shù)的最大值，則它將該查詢消息轉(zhuǎn)發(fā)給一部分(通過(guò)參數(shù)p指定)鄰居節(jié)點(diǎn)；否則將該查詢消息僅轉(zhuǎn)發(fā)給一個(gè)鄰居節(jié)點(diǎn)。

在這些少量的高度數(shù)節(jié)點(diǎn)上使用BFS策略進(jìn)行搜索，不僅能夠訪問(wèn)到較多的節(jié)點(diǎn)，而且當(dāng)一個(gè)高度數(shù)節(jié)點(diǎn)執(zhí)行BFS操作后，其大多數(shù)鄰居節(jié)點(diǎn)在收到消息后只能執(zhí)行DFS操作。因此，這種混合搜索策略分散了執(zhí)行消息廣播（或多播）的高度數(shù)節(jié)點(diǎn)的位置，能夠較為有效地避免消息泛濫，同時(shí)還能提高訪問(wèn)節(jié)點(diǎn)數(shù)量。

1．2基于反饋的混合搜索算法

上面討論了混合搜索策略并以之來(lái)確定節(jié)點(diǎn)轉(zhuǎn)發(fā)消息時(shí)所選擇的轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)量h，在此將討論P(yáng)2P節(jié)點(diǎn)如何根據(jù)搜索反饋來(lái)確定選擇哪h個(gè)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，進(jìn)而提出一種基于反饋的P2P網(wǎng)絡(luò)混合搜索(feedbackbased hybrid searching，F(xiàn)HS)算法。

FHS算法的一個(gè)主要思想是選擇能夠快速返回較多響應(yīng)結(jié)果的節(jié)點(diǎn)轉(zhuǎn)發(fā)消息。每個(gè)搜索節(jié)點(diǎn)根據(jù)其各個(gè)鄰居節(jié)點(diǎn)返回的響應(yīng)(QueryHit)數(shù)量及距離分別計(jì)算它們每次搜索的搜索反饋，并結(jié)合這些鄰居節(jié)點(diǎn)先前的搜索反饋來(lái)計(jì)算（或更新）其平均搜索反饋；在下一次搜索時(shí)，選擇h個(gè)平均搜索反饋?zhàn)畲蟮泥従庸?jié)點(diǎn)轉(zhuǎn)發(fā)消息。

典型地，節(jié)點(diǎn)N的一個(gè)鄰居節(jié)點(diǎn)s第t次的搜索反饋fN(s， t)可按如下方法計(jì)算：首先，就s返回的每一個(gè)響應(yīng)x為其賦予一個(gè)相應(yīng)的權(quán)值，這里為TTLdst(s， x)（其中：TTL為搜索深度；dst(s， x)為搜索路徑中節(jié)點(diǎn)s與響應(yīng)x所在節(jié)點(diǎn)的相距跳數(shù)。該權(quán)值反映了響應(yīng)x與節(jié)點(diǎn)s距離的遠(yuǎn)近程度，距離越近，權(quán)值越高）；然后，將所有響應(yīng)權(quán)值的累加和作為節(jié)點(diǎn)s的本次搜索反饋，即

fN(s，t)=∑x∈Qs(t)(TTLdst(s，x))（2）

其中：Qs(t)表示在第t次搜索通過(guò)節(jié)點(diǎn)s返回的響應(yīng)集合。可以看出，當(dāng)通過(guò)s返回的響應(yīng)數(shù)量越多并且距離越近時(shí)，fN(s，t)的值越大，表明節(jié)點(diǎn)s在本次搜索中的反饋越好。

以上fN(s， t)只能反映節(jié)點(diǎn)N的一個(gè)鄰居節(jié)點(diǎn)s在第t次搜索的反饋情況。為了能夠較好地評(píng)價(jià)各鄰居節(jié)點(diǎn)的整體反饋情況，以便更好地指導(dǎo)下一次搜索，接下來(lái)將結(jié)合鄰居節(jié)點(diǎn)s先前搜索的反饋信息計(jì)算（或更新）其前t次搜索的平均搜索反饋

MN(s，t)=β×fN(s，t)+(1-β)×MN(s，t-1)（3）

這里采用指數(shù)加權(quán)平均法來(lái)求節(jié)點(diǎn)N的鄰居節(jié)點(diǎn)s前t次的平均搜索反饋MN(s， t)。其中β(0<β<1)是權(quán)重系數(shù)。可以看出，MN(s， t)由鄰居節(jié)點(diǎn)s第t次的搜索反饋和其先前t-1次的平均搜索反饋按不同比例組成。同時(shí)，將式（3）展開(kāi)還可以看出，它還是鄰居節(jié)點(diǎn)s前t次搜索反饋(fN(s， t)，fN(s， t-1)，…，fN(s， 1))的加權(quán)平均，且時(shí)間上越近的搜索反饋權(quán)重越大。例如，權(quán)重依次為β，(1-β)，β(1-β)，…，β(1-β)t-1。

式（3）能夠較好地跟蹤當(dāng)前的網(wǎng)絡(luò)行為（對(duì)象添加/刪除、節(jié)點(diǎn)加入/離開(kāi)）：當(dāng)網(wǎng)絡(luò)環(huán)境穩(wěn)定時(shí)，MN(s， t)就會(huì)趨向于一個(gè)良好的平均值；當(dāng)網(wǎng)絡(luò)環(huán)境動(dòng)態(tài)變化時(shí)，采用較大的β能夠使MN(s， t)對(duì)不斷變化的網(wǎng)絡(luò)行為迅速變化，而較小的β則使MN(s， t)緩慢變化。因此，通過(guò)式（3）計(jì)算出的各鄰居節(jié)點(diǎn)的平均搜索反饋能夠較好地預(yù)示這些節(jié)點(diǎn)在將來(lái)搜索的反饋趨勢(shì)，因而在FHS算法中將平均搜索反饋?zhàn)鳛檗D(zhuǎn)發(fā)消息時(shí)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)的依據(jù)。這使得FHS算法總是能夠適應(yīng)不斷變化的網(wǎng)絡(luò)行為，具有較強(qiáng)的自適應(yīng)能力。即使環(huán)境不斷變化，它也能夠選擇最好的節(jié)點(diǎn)（能夠返回最多最近響應(yīng)）轉(zhuǎn)發(fā)消息。

在實(shí)現(xiàn)算法時(shí)，F(xiàn)HS讓每個(gè)節(jié)點(diǎn)保存一個(gè)m行n列的二維索引表，每一行索引表示某一搜索對(duì)象，該節(jié)點(diǎn)所有n個(gè)鄰居節(jié)點(diǎn)先前的平均搜索反饋，總共為m個(gè)搜索對(duì)象保存索引（采用LRU策略進(jìn)行替換）。因此，在搜索某一個(gè)對(duì)象時(shí)，節(jié)點(diǎn)只需選擇索引值最大的h個(gè)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息即可。但為了避免節(jié)點(diǎn)在每次搜索時(shí)都選擇同樣的鄰居節(jié)點(diǎn)，這里進(jìn)行如下修改：在執(zhí)行DFS操作的低度數(shù)節(jié)點(diǎn)處采用一種概率搜索，讓索引值越大的鄰居節(jié)點(diǎn)被選擇成為消息接收者的概率越大；在執(zhí)行BFS操作的高度數(shù)節(jié)點(diǎn)處，選擇h-1個(gè)索引值最大的鄰居節(jié)點(diǎn)和1個(gè)隨機(jī)選擇的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息。圖1給出了FHS算法搜索某一對(duì)象的過(guò)程及部分相關(guān)節(jié)點(diǎn)的索引更新過(guò)程。

圖1FHS算法（p=1/2， TTL=3， β=2/3）搜索過(guò)程及相關(guān)索引更新過(guò)程

在圖1中，黑色粗線箭頭表示查詢消息，虛線箭頭表示響應(yīng)消息。節(jié)點(diǎn)A發(fā)出兩條查詢消息進(jìn)行搜索，且在高度數(shù)節(jié)點(diǎn)E處查詢消息被轉(zhuǎn)發(fā)給一半（p=1/2）鄰居節(jié)點(diǎn)。第一次搜索時(shí)節(jié)點(diǎn)J、G為響應(yīng)節(jié)點(diǎn)，第二次搜索時(shí)網(wǎng)絡(luò)行為發(fā)生了變化，節(jié)點(diǎn)J、G、B、K為響應(yīng)節(jié)點(diǎn)。任一節(jié)點(diǎn)X存放的關(guān)于鄰居節(jié)點(diǎn)Y的索引項(xiàng)用X→Y表示，初始值均設(shè)為TTL。各節(jié)點(diǎn)的索引值（平均搜索反饋）的變化或更新情況如圖1（b）所示，括號(hào)內(nèi)的值表示索引值更新過(guò)程。

索引值按如下兩個(gè)步驟進(jìn)行更新：根據(jù)式（3），節(jié)點(diǎn)在向一個(gè)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息時(shí)，將其索引值降為原來(lái)的（1-β）倍；然后等待該鄰居節(jié)點(diǎn)返回搜索結(jié)果，當(dāng)從該鄰居節(jié)點(diǎn)返回一條響應(yīng)消息時(shí)，節(jié)點(diǎn)將由式（2）計(jì)算的響應(yīng)權(quán)值的β倍值累加到該節(jié)點(diǎn)的索引值上，直到該鄰居節(jié)點(diǎn)返回所有響應(yīng)消息，其索引值更新也就相應(yīng)完成。例如圖1中第二次搜索時(shí)節(jié)點(diǎn)B在A中的索引A→B的更新過(guò)程依次為5/9、23/9、29/9。其中5/9是在節(jié)點(diǎn)A向鄰居節(jié)點(diǎn)B轉(zhuǎn)發(fā)查詢消息時(shí)更新的，23/9和29/9分別在B返回第一個(gè)和第二個(gè)（也是最后一個(gè)）響應(yīng)結(jié)果時(shí)更新的。29/9為節(jié)點(diǎn)B在本次搜索中更新的最終索引值，它反映了節(jié)點(diǎn)B在前兩次搜索中的平均搜索反饋。

另外，從圖1(b)中還可以看到，節(jié)點(diǎn)B和C在A中的索引A→B和A→C的值在第一次搜索后的值分別為5/3和7/3，而在第二次搜索后迅速上升為29/9和23/9.這是因?yàn)樵诘诙嗡阉鲿r(shí)網(wǎng)絡(luò)中經(jīng)過(guò)節(jié)點(diǎn)B和C的搜索路徑上增加了兩個(gè)響應(yīng)節(jié)點(diǎn)B和K。這再次說(shuō)明了FHS算法能夠較好地跟蹤且適應(yīng)當(dāng)前的網(wǎng)絡(luò)行為，具有良好的自適應(yīng)能力。

2實(shí)驗(yàn)

本文通過(guò)實(shí)驗(yàn)對(duì)FHS算法的性能進(jìn)行評(píng)估，考察其搜索成功率、響應(yīng)率（平均每次搜索產(chǎn)生的響應(yīng)結(jié)果數(shù)）、產(chǎn)生的冗余消息以及整體性能（搜索效率），并與兩個(gè)典型的DFSlike搜索算法random walk及其改進(jìn)算法APS進(jìn)行性能比較。

2．1實(shí)驗(yàn)方法

所有實(shí)驗(yàn)均在一臺(tái)P4 3.0 GHz處理器、512 MB內(nèi)存、Windows XP操作系統(tǒng)的PC機(jī)上完成。用PeerSim[8]模擬P2P網(wǎng)絡(luò)環(huán)境，網(wǎng)絡(luò)拓?fù)涫腔贐RITE[9]產(chǎn)生的10 000個(gè)節(jié)點(diǎn)的power law模型。其中最大節(jié)點(diǎn)度數(shù)為315、最小節(jié)點(diǎn)度數(shù)為4，平均節(jié)點(diǎn)度數(shù)為8，以上三種搜索算法采用Java語(yǔ)言編程實(shí)現(xiàn)并在PeerSim上運(yùn)行。

實(shí)驗(yàn)中采用100個(gè)對(duì)象，其拷貝分布和查詢分布服從Zipflike分布，且分別為Zipflike（α=1）和Zipflike（α=0.9）。這一設(shè)置符合文獻(xiàn)[10]的調(diào)查結(jié)果：流行對(duì)象的拷貝數(shù)量占所有拷貝數(shù)量的50%，對(duì)它們的查詢次數(shù)占所有查詢次數(shù)的60%。另外，隨機(jī)選擇10%的網(wǎng)絡(luò)節(jié)點(diǎn)（即1 000個(gè)）進(jìn)行查詢，每個(gè)節(jié)點(diǎn)進(jìn)行約2 600次查詢。

各算法參數(shù)設(shè)定如下：每個(gè)查詢節(jié)點(diǎn)配置8個(gè)查詢消息（超過(guò)其鄰居節(jié)點(diǎn)數(shù)就按所有鄰居節(jié)點(diǎn)數(shù)計(jì)算），搜索深度TTL=10。另外，APS算法的索引初始值設(shè)為30；FHS算法的索引初始值設(shè)為10，參數(shù)β=2/3，p=0.5（即在高度數(shù)節(jié)點(diǎn)選擇一半鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息）。

2．2實(shí)驗(yàn)結(jié)果及其分析

圖2和3所示為算法FHS、APS和random walk的成功率和響應(yīng)率。從中可以看出， FHS算法的成功率比APS算法提高了約10%，而比random walk算法提高了近一倍。另外，在響應(yīng)率方面，F(xiàn)HS均比APS和random walk算法提高了近一個(gè)數(shù)量級(jí)（典型地，當(dāng)搜索深度TTL達(dá)到10跳時(shí)，F(xiàn)HS算法的響應(yīng)率達(dá)到平均每10次搜索產(chǎn)生426個(gè)結(jié)果，即平均每次搜索產(chǎn)生42.6個(gè)結(jié)果；APS算法平均每次搜索僅產(chǎn)生3個(gè)結(jié)果；random walk平均每次搜索僅產(chǎn)生1.1個(gè)結(jié)果）。這是因?yàn)閞andom walk和APS在搜索時(shí)均只采用深度優(yōu)先搜索策略，而且random walk在搜索時(shí)采用隨機(jī)方式轉(zhuǎn)發(fā)消息，使得查詢消息不能訪問(wèn)更多更遠(yuǎn)的節(jié)點(diǎn)，因而成功率和響應(yīng)率都較低。盡管APS算法在搜索時(shí)選擇最有可能返回結(jié)果的節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，但每個(gè)walker（查詢消息）搜到1個(gè)結(jié)果就停止搜索，因此僅提高了成功率而不能很好地提高響應(yīng)率。相比之下，F(xiàn)HS算法能夠根據(jù)P2P網(wǎng)絡(luò)拓?fù)涮匦裕谀承└叨葦?shù)節(jié)點(diǎn)處通過(guò)執(zhí)行寬度優(yōu)先搜索來(lái)訪問(wèn)更多節(jié)點(diǎn)；同時(shí)，在搜索過(guò)程中選擇能夠返回最多最近響應(yīng)結(jié)果的節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，因此不僅提高了成功率而且還提高了響應(yīng)率。

圖4用消息冗余度（即冗余消息數(shù)量占總消息數(shù)量的百分比）來(lái)比較各種算法在搜索過(guò)程中產(chǎn)生的冗余消息。一種有效的搜索算法應(yīng)該能夠有效地減少冗余消息，即用較少的消息訪問(wèn)較多的節(jié)點(diǎn)并且盡可能確保這些被訪問(wèn)的節(jié)點(diǎn)是能夠提供較多響應(yīng)結(jié)果的節(jié)點(diǎn)。在三種算法中，random walk的消息冗余度最大，因?yàn)樗谒阉鬟^(guò)程中隨機(jī)轉(zhuǎn)發(fā)消息。FHS算法的消息冗余度較之要小，結(jié)合圖2和3可以看出FHS算法能夠有效地減少冗余消息。盡管APS算法的消息冗余度很低，但它是以犧牲響應(yīng)率作為代價(jià)的，因?yàn)锳PS算法為了避免產(chǎn)生過(guò)多的消息，讓每個(gè)walker搜到一個(gè)結(jié)果就停止繼續(xù)搜索。

圖5比較了各種算法的搜索效率。根據(jù)文獻(xiàn)[11]，搜索效率search efficiency=(queryHits×successRate)/(msgPer￣Node×hopsNumber)。結(jié)合圖2~4可知，random walk算法的成功率和響應(yīng)率都比較低且產(chǎn)生的冗余消息較多，因此搜索效率較低。相比之下，F(xiàn)HS和APS算法搜索效率較高。另外還可以看到，F(xiàn)HS算法的搜索效率在前2~4跳略低于APS算法。這是因?yàn)樵谇?~4跳內(nèi)這兩種算法的成功率和響應(yīng)率較接近，而這期間APS算法產(chǎn)生的消息和冗余消息極少，因而使得搜索效率略高于FHS算法。但是隨著搜索深度遞增，F(xiàn)HS算法的響應(yīng)率和成功率都在不斷增加。從整體上看，F(xiàn)HS算法的搜索效率比APS算法的要高。

圖6和7的結(jié)果描述了隨機(jī)選擇的同一個(gè)節(jié)點(diǎn)的其中四個(gè)鄰居節(jié)點(diǎn)索引值分別在FHS和APS算法中的變化趨勢(shì)。從圖6可以看到，F(xiàn)HS算法的索引值是在某個(gè)平均值附近上下波動(dòng)。這是因?yàn)樵贔HS算法中采用指數(shù)加權(quán)平均法來(lái)更新鄰居節(jié)點(diǎn)索引值。該索引值是由先前的各次搜索反饋按不同權(quán)重的加權(quán)平均值組成，且時(shí)間上越近的權(quán)重越大。這種方法能夠較好地評(píng)估一個(gè)鄰居節(jié)點(diǎn)先前搜索的反饋情況，并且有利于及時(shí)捕捉網(wǎng)絡(luò)動(dòng)態(tài)行為以便迅速進(jìn)行調(diào)整。例如，當(dāng)一個(gè)節(jié)點(diǎn)在本次搜索中不能再很好地反饋?lái)憫?yīng)結(jié)果時(shí)，則由于本次搜索反饋的權(quán)重較大而導(dǎo)致索引值適度降低，以暗示該節(jié)點(diǎn)在將來(lái)可能不再很好地反饋較好的響應(yīng)結(jié)果。APS算法采用一種累加（減）方式更新索引值，每次搜索若有反饋則讓索引值加一個(gè)單位，否則減一個(gè)單位。這使得索引值呈兩種趨勢(shì)：反饋較好的節(jié)點(diǎn)索引值不斷上升；反饋較差的節(jié)點(diǎn)索引值不斷下降直到某個(gè)下限（圖7）。這種方法對(duì)網(wǎng)絡(luò)行為適應(yīng)較慢，因?yàn)楫?dāng)一個(gè)好鄰居節(jié)點(diǎn)不再能夠很好地返回結(jié)果時(shí)，則要經(jīng)過(guò)好幾次搜索才能使它的索引值下降到與其他鄰居節(jié)點(diǎn)一樣，但在此期間，其索引值都將誤導(dǎo)著查詢消息向它轉(zhuǎn)發(fā)。

綜上所述，F(xiàn)HS算法通過(guò)在高度數(shù)節(jié)點(diǎn)執(zhí)行寬度優(yōu)先搜索且選擇平均反饋?zhàn)畲蟮泥従庸?jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)消息獲得了高成功率和高響應(yīng)率，同時(shí)有效地減少冗余消息，提高搜索效率。而且還能夠很好地適應(yīng)動(dòng)態(tài)網(wǎng)絡(luò)行為，展現(xiàn)了良好的自適應(yīng)能力。

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

本文根據(jù)P2P網(wǎng)絡(luò)的power law節(jié)點(diǎn)度數(shù)分布規(guī)律和節(jié)點(diǎn)在搜索過(guò)程中呈現(xiàn)的不同反饋能力，提出了一種基于反饋的P2P網(wǎng)絡(luò)混合搜索算法，在搜索過(guò)程中采用一種混合搜索策略和利用先前的搜索反饋來(lái)指導(dǎo)搜索。算法分析和實(shí)驗(yàn)結(jié)果表明，該算法具有高搜索效率、高成功率、高響應(yīng)率和有效減少冗余消息的特點(diǎn)，并且具有良好的自適應(yīng)能

力，是一種有效的P2P網(wǎng)絡(luò)搜索算法。

參考文獻(xiàn)：

［1］YANG B， GARCIAMOLINA H. Improving search in peertopeer networks[C]//SIVILOTTI P A G. Proc of the 22nd International Conference on Distributed Computing Systems. Los Alamitos， CA: IEEE Computer Society Press， 2002: 514.

［2］JIANG Song， GUO Lei， ZHANG Xiaodong. LightFlood: an efficient flooding scheme for file search in unstructured peertopeer systems[C]//Proc of International Conference on Parallel Processing (ICPP’03). Los Alamitos， CA: IEEE Computer Society Press， 2003: 627－635.

［3］ZHENG Qianbing， WANG Yongwen， LU Xicheng. WCBF: efficient and highcoverage search schema in unstructured peertopeer network[C]//JIN H， PAN Y， XIAO N， et al. Proc of the 3rd International Conference on Grid and Cooperative Computing (GCC 2004)， LNCS 3251. Berlin， Heidelberg: SpringerVerlag， 2004:487－494.

［4］KALOGERALI V， GUNOPULOS D， ZEINALIPOURYAZTI D. A local search mechanism for peertopeer networks[C]//Proc of the 11th International Conference on Information and Knowledge Management (CIKM’02). New York: ACM Press， 2002:300－307.

［5］LV Q， CAO P， COHEN E， et al. Search and replication in unstructured peertopeer networks[C]//Proc of the 16th International Conference on Supercomputing (ICS’02). New York: ACM Press， 2002: 84－95.

［6］TSOUMAKOS D， ROUSSOPOULOS N. Adaptive probabilistic search for peertopeer networks[C]// Proc of the 3rd International Confe￣rence on PeertoPeer Computing (P2P’03). Washington DC: IEEE Computer Society， 2003:102109.

［7］ZHUGE Hai， CHEN Xue， SUN Xiaoping. Preferential walk: towards efficient and scalable search in unstructured peertopeer networks[C]//Special Interest Tracks and Posters of the 14th International Conference on World Wide Web. New York: ACM Press， 2005:882－883.

［8］PeerSim P2P simulator [EB/OL]. [2007－0118]. http://peersim.sourceforge.net/.

［9］BRITE: Boston University representative Internet topology generator [EB/OL]. [2007－0118].http://www.cs.bu.edu/brite/.

［10］CHU J， LANONTE K， LEVINE B N. Availability and locality mea￣surements of peertopeer file systems[C]// FIROIU V， ZHANG Zhili. Proc of the SPIE Vol. 4868， Scalability and Traffic Control in IP Networks Ⅱ. Boston: SPIE， 2002: 310－321.

［11］LIN T N， WANG H P. Search performance analysis in peertopeer networks[C]//Proc of the 3rd International Conference on PeertoPeer Computing (P2P’03). Washington DC: IEEE Compu￣ter Society， 2003:204－205.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”