基于反饋的非結構化Ｐ２Ｐ網絡混合搜索算法

摘要：為了提高P2P網絡搜索效率和有效地減少冗余消息，提出一種基于反饋的混合搜索算法，將查詢消息在某些高度數節點處轉發給多個鄰居節點而在其他節點處只轉發給一個鄰居節點，并且在搜索過程中利用先前搜索的反饋信息來指導搜索，以選擇能夠返回最多最近響應結果的鄰居節點轉發消息。算法分析和實驗結果表明，該算法不僅實現了較高的成功率、響應率和搜索效率，還能有效地減少冗余消息，并且具有良好的自適應能力，能快速適應不斷變化的網絡行為。

關鍵詞：對等網絡； 混合搜索； 反饋； 自適應能力

中圖分類號：TP31文獻標志碼：A

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

Gnutella等大多數非結構化P2P網絡采用一種稱為洪泛（flooding）的搜索算法。該算法在搜索時向所有的鄰居節點轉發查詢消息，因此又叫寬度優先搜索（BFS）算法。洪泛搜索算法導致大量呈指數增長的消息產生，冗余消息多，浪費了大量不必要的網絡帶寬，使得Gnutella不可擴展。類似的P2P網絡搜索算法還有iterative deepening[1]和lightFlood[2]等。

現有的大多數P2P網絡搜索算法都致力于減少由洪泛操作產生的冗余消息。這些算法大致可分為兩大類[3]：a)BFSlike算法，如directed BFS[1]、modifiedBFS[4]等，在搜索時只選擇部分鄰居節點轉發消息；b)DFSlike算法，如random walk[5]、APS[6]和preferential walk[7]等，在搜索時僅選擇一個鄰居節點轉發消息。

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

1基于反饋的P2P網絡混合搜索算法

1．1混合搜索策略

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

關鍵問題是如何確定在搜索時使用BFS策略的高度數節點。顯然，不可能采用通過網絡統計所有節點的度數再進行篩選的方法，但一個節點可以很容易地獲知其鄰居節點的度數。因此，本文將那些節點度數不小于其任何一個鄰居節點的度數的節點看成高度數節點，這些節點在搜索時使用BFS策略。

設節點度數為n的節點N，通過函數dmax(N)求取該節點所有鄰居節點度數的最大值，并且引入一個參數p（0

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

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

即當節點N在轉發一條查詢消息時，如果N的節點度數不小于其鄰居節點度數的最大值，則它將該查詢消息轉發給一部分(通過參數p指定)鄰居節點；否則將該查詢消息僅轉發給一個鄰居節點。

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

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

上面討論了混合搜索策略并以之來確定節點轉發消息時所選擇的轉發節點數量h，在此將討論P2P節點如何根據搜索反饋來確定選擇哪h個鄰居節點轉發消息，進而提出一種基于反饋的P2P網絡混合搜索(feedbackbased hybrid searching，FHS)算法。

FHS算法的一個主要思想是選擇能夠快速返回較多響應結果的節點轉發消息。每個搜索節點根據其各個鄰居節點返回的響應(QueryHit)數量及距離分別計算它們每次搜索的搜索反饋，并結合這些鄰居節點先前的搜索反饋來計算（或更新）其平均搜索反饋；在下一次搜索時，選擇h個平均搜索反饋最大的鄰居節點轉發消息。

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

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

其中：Qs(t)表示在第t次搜索通過節點s返回的響應集合。可以看出，當通過s返回的響應數量越多并且距離越近時，fN(s，t)的值越大，表明節點s在本次搜索中的反饋越好。

以上fN(s， t)只能反映節點N的一個鄰居節點s在第t次搜索的反饋情況。為了能夠較好地評價各鄰居節點的整體反饋情況，以便更好地指導下一次搜索，接下來將結合鄰居節點s先前搜索的反饋信息計算（或更新）其前t次搜索的平均搜索反饋

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

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

式（3）能夠較好地跟蹤當前的網絡行為（對象添加/刪除、節點加入/離開）：當網絡環境穩定時，MN(s， t)就會趨向于一個良好的平均值；當網絡環境動態變化時，采用較大的β能夠使MN(s， t)對不斷變化的網絡行為迅速變化，而較小的β則使MN(s， t)緩慢變化。因此，通過式（3）計算出的各鄰居節點的平均搜索反饋能夠較好地預示這些節點在將來搜索的反饋趨勢，因而在FHS算法中將平均搜索反饋作為轉發消息時選擇轉發節點的依據。這使得FHS算法總是能夠適應不斷變化的網絡行為，具有較強的自適應能力。即使環境不斷變化，它也能夠選擇最好的節點（能夠返回最多最近響應）轉發消息。

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

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

在圖1中，黑色粗線箭頭表示查詢消息，虛線箭頭表示響應消息。節點A發出兩條查詢消息進行搜索，且在高度數節點E處查詢消息被轉發給一半（p=1/2）鄰居節點。第一次搜索時節點J、G為響應節點，第二次搜索時網絡行為發生了變化，節點J、G、B、K為響應節點。任一節點X存放的關于鄰居節點Y的索引項用X→Y表示，初始值均設為TTL。各節點的索引值（平均搜索反饋）的變化或更新情況如圖1（b）所示，括號內的值表示索引值更新過程。

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

另外，從圖1(b)中還可以看到，節點B和C在A中的索引A→B和A→C的值在第一次搜索后的值分別為5/3和7/3，而在第二次搜索后迅速上升為29/9和23/9.這是因為在第二次搜索時網絡中經過節點B和C的搜索路徑上增加了兩個響應節點B和K。這再次說明了FHS算法能夠較好地跟蹤且適應當前的網絡行為，具有良好的自適應能力。

2實驗

本文通過實驗對FHS算法的性能進行評估，考察其搜索成功率、響應率（平均每次搜索產生的響應結果數）、產生的冗余消息以及整體性能（搜索效率），并與兩個典型的DFSlike搜索算法random walk及其改進算法APS進行性能比較。

2．1實驗方法

所有實驗均在一臺P4 3.0 GHz處理器、512 MB內存、Windows XP操作系統的PC機上完成。用PeerSim[8]模擬P2P網絡環境，網絡拓撲是基于BRITE[9]產生的10 000個節點的power law模型。其中最大節點度數為315、最小節點度數為4，平均節點度數為8，以上三種搜索算法采用Java語言編程實現并在PeerSim上運行。

實驗中采用100個對象，其拷貝分布和查詢分布服從Zipflike分布，且分別為Zipflike（α=1）和Zipflike（α=0.9）。這一設置符合文獻[10]的調查結果：流行對象的拷貝數量占所有拷貝數量的50%，對它們的查詢次數占所有查詢次數的60%。另外，隨機選擇10%的網絡節點（即1 000個）進行查詢，每個節點進行約2 600次查詢。

各算法參數設定如下：每個查詢節點配置8個查詢消息（超過其鄰居節點數就按所有鄰居節點數計算），搜索深度TTL=10。另外，APS算法的索引初始值設為30；FHS算法的索引初始值設為10，參數β=2/3，p=0.5（即在高度數節點選擇一半鄰居節點轉發消息）。

2．2實驗結果及其分析

圖2和3所示為算法FHS、APS和random walk的成功率和響應率。從中可以看出， FHS算法的成功率比APS算法提高了約10%，而比random walk算法提高了近一倍。另外，在響應率方面，FHS均比APS和random walk算法提高了近一個數量級（典型地，當搜索深度TTL達到10跳時，FHS算法的響應率達到平均每10次搜索產生426個結果，即平均每次搜索產生42.6個結果；APS算法平均每次搜索僅產生3個結果；random walk平均每次搜索僅產生1.1個結果）。這是因為random walk和APS在搜索時均只采用深度優先搜索策略，而且random walk在搜索時采用隨機方式轉發消息，使得查詢消息不能訪問更多更遠的節點，因而成功率和響應率都較低。盡管APS算法在搜索時選擇最有可能返回結果的節點轉發消息，但每個walker（查詢消息）搜到1個結果就停止搜索，因此僅提高了成功率而不能很好地提高響應率。相比之下，FHS算法能夠根據P2P網絡拓撲特性，在某些高度數節點處通過執行寬度優先搜索來訪問更多節點；同時，在搜索過程中選擇能夠返回最多最近響應結果的節點轉發消息，因此不僅提高了成功率而且還提高了響應率。

圖4用消息冗余度（即冗余消息數量占總消息數量的百分比）來比較各種算法在搜索過程中產生的冗余消息。一種有效的搜索算法應該能夠有效地減少冗余消息，即用較少的消息訪問較多的節點并且盡可能確保這些被訪問的節點是能夠提供較多響應結果的節點。在三種算法中，random walk的消息冗余度最大，因為它在搜索過程中隨機轉發消息。FHS算法的消息冗余度較之要小，結合圖2和3可以看出FHS算法能夠有效地減少冗余消息。盡管APS算法的消息冗余度很低，但它是以犧牲響應率作為代價的，因為APS算法為了避免產生過多的消息，讓每個walker搜到一個結果就停止繼續搜索。

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

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

綜上所述，FHS算法通過在高度數節點執行寬度優先搜索且選擇平均反饋最大的鄰居節點來轉發消息獲得了高成功率和高響應率，同時有效地減少冗余消息，提高搜索效率。而且還能夠很好地適應動態網絡行為，展現了良好的自適應能力。

3結束語

本文根據P2P網絡的power law節點度數分布規律和節點在搜索過程中呈現的不同反饋能力，提出了一種基于反饋的P2P網絡混合搜索算法，在搜索過程中采用一種混合搜索策略和利用先前的搜索反饋來指導搜索。算法分析和實驗結果表明，該算法具有高搜索效率、高成功率、高響應率和有效減少冗余消息的特點，并且具有良好的自適應能

力，是一種有效的P2P網絡搜索算法。

參考文獻：

［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.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”