無結構對等網搜索機制研究

摘要：無結構對等網絡由于搜索的靈活性和對動態環境的適應性，得到了廣泛的應用，已經成為對等網絡的主流。本文研究了目前已有的無結構對等網絡的搜索算法，指出了搜索算法的特點和不足，總結了無結構對等網絡需要解決的問題。

關鍵詞：無結構對等網；搜索算法；洪泛

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)25-1436-03

Summarization of Searching Algorithms of Unstructured P2P Network

FU Zhi-qiang

(Department of Computer Science and Engineering Zhongkai University of Agricultural and Technology， Guangzhou 510225， China)

Abstract: The unstructured P2P network is widely applied and becomes the mainstream in this field Because of its flexibility on query patterns and adaptability to dynamic environments. This dissertation analyses the searching algorithm of P2P network in detail and studies the searching algorithm for the P2P network. It concludes the problems that searching algorithm of unstructured P2P network should be resolved.

Key words: Unstructured Peer-to-Peer Network;searching algorithm;flooding

1 引言

對等網絡(Peer-to-Peer Network， P2P)又稱點對點技術，簡稱為P2P網絡。它是一種網絡模型，由大量高度動態的節點組成。在這種網絡模型中的節點都是對等的，它們可以以任意方式加入或離開網絡，具有相同的責任與能力，并協同完成任務。對等點之間通過邏輯上直接互連，動態共享資源。

P2P網絡資源存在形式對搜索提出新要求，高效的資源搜索機制是P2P技術的研究重點[1]。無結構對等網絡由于搜索的靈活性和對動態環境的適應性，得到了廣泛的應用，本文指出了每種搜索算法的應用領域和不足，為高性能的P2P搜索算法的提出奠定基礎。

2 對等網絡分類

對等網絡分類方法有很多種，根據對等網絡的結構可以將其分為有結構對等網絡和無結構對等網絡。有結構對等網絡是指網絡的結構固定的，這類網絡中提供了文件ID和文件存貯位置之間的映射關系，從而保證有效路由，并保證最終找到目標節點[2-4]。有結構對等網絡的搜索算法主要采用的方法是分布式哈希表技術 (Distributed Hash Table，DHT)。在DHT中不用維護每個節點以及整個網絡的信息，只是在每個節點中存儲其鄰居節點的信息。現在大多采用DHT方式的對等網絡缺乏Internet中大規模真實部署的實例，成功應用還比較少見。而無結構對等網絡中，節點之間是任意連接的。無結構對等網絡由于搜索的靈活性和對動態環境的適應性，得到了廣泛的應用，已經成為對等網絡的主流。

3 無結構對等網絡

無結構對等網絡中沒有服務器來幫助共享內容的查詢，是通過鄰居節點之間的轉發方式來完成的。下面詳細介紹幾種算法的搜索過程：

3.1 Gnutella洪泛算法

Gnutella洪泛算法是典型的無結構對等網絡的盲搜索算法之一，在P2P網絡中，對等點通過泛洪算法向網絡中其它對等點發布廣播消息來實現端查找與發現功能。某個節點所發出的查找請求將不斷的在網絡中擴散，最終會到達網絡上所有的節點。人們為了限制廣播范圍，搜索消息被設置了一個初始的TTL(Time-To-Live)值，TTL用來控制消息在網絡上存留的時間，一條消息將不會在網上被無限次的轉發。

Gnutella突出的優點是實現簡單。由于Gnutella以洪泛的方式發送請求，因此查詢的命中率高，并且部分節點失效時不影響整個系統，具有較好的魯棒性。然而正是由于使用了洪泛的方式傳播消息，消耗了網絡中大量帶寬。雖然加入TTL域后節省了一部分帶寬資源，但又會出現“短路”的情況，即查找的資源雖然在網絡中存在，但由于超出了TTL值而無法定位到該資源。

3.2 K-Random-Walker算法

K-Random-Walker算法是盲搜索算法中采用了漫游類策略的典范[5]。在這種算法中請求節點開始時可以決定發送查詢信息的數量，并且在每一次查詢時都可以控制，每輪的查詢規模不會改變。

在K-Random-Walker算法中，通過并行k個漫游查詢消息來提高查詢的速度。當節點發起查詢時，發出k個查詢信息，而每個收到查詢信息的節點將隨機的選擇自己的一個鄰居，并將該查詢信息轉發給鄰居節點。此算法中還采用了周期返回檢測策略來實現查詢截止。節點在收到查詢消息時，先檢查該消息的標志是否為0，若不為0則該節點任意選擇一個其對應的鄰居節點轉發查詢消息，并將其值減1；若為0，則向請求點發送查詢滿足檢測消息并等待檢測結果的返回。當請求點收到檢測結果時，如果結果已滿足查詢要求時，就停止該次查詢過程；如果結果仍不滿足，就重新設置一個查詢消息的標志初始值，并重復剛才的算法過程重新進行一次漫游查詢過程。隨機步算法查詢過程如圖1所示。

■

圖1隨機步算法查詢過程

3.3 QAA(Query Agent Algorithm)算法

QAA (Query Agent Algorithm)算法在查詢過程中不斷地探測感知網絡情況，并依據其所獲得的信息指導后續的子查詢，從而達到更細致地控制查詢過程，降低冗余開銷的目的[6]。

QAA算法的具體實現過程如圖2所示，每個想要發起查詢的節點首先生成一個查詢代理，隨后由查詢代理完全負責查詢工作。查詢代理通過發起子查詢來執行實際的查詢工作，而子查詢的工作則被簡化為將查詢消息快速分發給多個節點，以確保較高的查詢速度。查詢代理收集所有子查詢結果，并評估網絡相關信息，在查詢結果不能滿足查詢條件時轉移到新的節點上發起新的子查詢，如此重復，直至結果滿足或查詢代理TTL超時。

QAA算法在查詢過程中通過查詢子代理控制了查詢的冗余開銷，并且在已有的查詢結果離目標較遠、查詢不容易滿足時，設置足夠大的子查詢規模；而己有結果離目標越接近，允許的子查詢規模越小。并且由于每次子查詢都是在不重復的節點上發起，自然地避免了消息重復問題。

■

圖2 QAA算法查詢過程

3.4 基于連通支配集的廣播算法BCDS

基于連通支配集的廣播算法BCDS (Broadcast based on connected Dominating Set)根據節點對收到消息的處理行為，將網絡中的節點分為轉發節點和接收節點[7]。通過減少轉發節點的數量，來減少消息的復制，從而減少冗余消息。該算法將P2P拓撲看作一個無向圖，P2P網絡中的節點看作是圖中的結點， P2P節點間的連接看作是圖中的邊。用G(V，E)來表示這個無向圖，其中V是結點集合，E是邊集合。如果兩個結點u和v間存在一個直接的連接，則稱u和v是鄰居。G(V，E)中的一個結點集合C可以稱為CDS(Connected Dominating Set，連通支配集)，它滿足條件G(V，E)中的所有結點要么在C中，要么是C結點的鄰居，而且由集合C導出的子圖是連通的。一個無向圖的CDS是不惟一的。屬于集合C中的結點稱為支配結點。在這里，支配結點也叫做轉發節點，它負責轉發廣播消息給它的鄰居。

在基于洪泛的廣播算法中，每個節點就是轉發節點，因此，生成大量的復制消息。通過減少轉發節點的數量來降低復制消息的數量。這個問題可轉化為在圖中找到一個最小連通支配集(minimum CDS)。從而得到一種分布式算法，每個節點維持它的兩跳(two-hop)拓撲信息，近似求出最小連通支配集。

3.5 蟻群算法

蟻群算法是一種新穎的進化類系統優化方法。此算法根據螞蟻覓食行為的特性，通過螞蟻釋放信息素的正反饋機制來指導搜索前進的方向，從而盡快地得到更好的搜索輸出[8]。

蟻群系統是自然界中一個典型的群體智能系統。用于尋找最短路徑的蟻群算法設計虛擬的“螞蟻”――人工蟻，讓它們搜索不同路線，并留下會隨時間逐漸消失的虛擬“信息素”。根據“信息素較濃的路線更近”的原則，即可選擇出最佳路線。基于蟻群算法機制的搜索算法的主要思想是，查詢消息包可以看作是螞蟻，搜索的目標視為食物，存在搜索目標的節點就是食物源。當源節點發出搜索請求時，就相當于派出螞蟻到網絡中尋找食物。網絡中的節點都維護一張信息素表，當螞蟻到達時，先看節點是否有需要的食物，如果有就返回一個命中消息包(可看作派出一只找到食物的螞蟻沿原路返回源節點，沿途釋放信息素，即修改節點的信息素表)。負責搜索食物的螞蟻，根據節點中的信息素濃度，選擇離目標近的鄰居繼續爬行，直到TTL減為0。通過螞蟻釋放信息素的這樣的正反饋的機制，可以實現高效的搜索。

3.6 基于興趣域的搜索算法

基于興趣域的搜索方案的一個基本假設是搜索請求可以以較高的概率被擁有相同興趣的節點滿足。如果一個節點可以滿足前一個搜索請求，那么它滿足當前搜索請求的概率也比較高；進一步，如果某個節點在過去的某一段時間內比其他節點能夠更好的滿足當前節點的搜索請求，那它滿足當前搜索請求的概率也比較高。

對于一個大型對等網絡系統來說，用戶存儲的信息并不是毫無關聯的。根據系統中每個節點存儲文檔內容的不同，這些節點可以被分成若干類。又因為用戶所共享的文件和查詢請求在一定程度上代表了用戶的興趣，那么可以把興趣域建立在這些分類之上。通過分析P2P網絡中本地節點存儲的共享文檔和該節點發出的查詢請求中的關鍵字來建立興趣域的。下面給出三個概念：本地資源關鍵字表LRK(Local Resource Keyword)、本地查詢關鍵字表LQK(Local Query Keyword)和朋友列表（Friend List）。LRK(Local Resource Keyword)本地資源關鍵字表：如果節點具有某種興趣，那么該節點很可能存儲反映該興趣的文件或者文檔，這就是本地資源，本地資源所包含的關鍵字隱含了該節點的興趣。預先分配節點的本地資源，同時創建LRK。此外，當節點收到其他節點的響應時就會更新自己的LRK表，把不在自己的LRK表中的關鍵字添加到列表中。

LRK的作用有兩個：一是節點加入非結構化P2P系統時，更新其他節點的朋友列表；二是節點收到查詢后，用于快速檢索本地是否有查詢的結果。LQK(Local Query Keyword)本地查詢關鍵字表：如果用戶對某種內容感興趣，它發出的查詢請求中就會隱含這種關鍵字。每當節點發出查詢請求時就會更新自己的LQK集，如果發出的查詢消息中包含的關鍵字不在LQK中，則把關鍵字添加到LQK中。節點通過比較關鍵字集來判斷興趣、查找朋友列表并且創建興趣域。

4 結論

通過對無結構對等網絡搜索算法的研究，發現其自身還存在著一些問題。對于無結構的對等網，需要考慮查詢截止問題。當用戶需要在P2P網絡中獲取信息時，他們預先并不知道這些信息會在那個節點上存儲，因此，在無結構P2P網絡中，信息搜索的算法難免帶有一定的盲目性。還要考慮冗余開銷。由于算法沒有提供有效的查詢截止算法，不能及時地停止查詢，帶來了大量的查詢冗余開銷。本文指出了無結構對等網絡搜索算法的特點和不足，為高性能的P2P搜索算法的提出奠定基礎。

參考文獻：

[1] 周文莉，吳曉非. P2P技術綜述[J].計算機工程與設計，2006，1:77-78.

[2] Jordan R. Why Gnutella can't scale[EB/OL].http://www.org/gnutella.html.

[3] Zhao B.y， Huang L，Stribling J，Rhea.S.C.JosePh，A.D，Kubiatowicz J.D，Tapestry:A Resilient Global-Scale Overlay for Service Deployment.Selected Aieas in Communications，IEEE Journal on，Volume:22，Issue:l，Jan.2004 Pgaes:41-53.

[4] Sripanid kulchai K，Maggs B，Zhang H. Efficient Content Location Using Interest-Based Locality in Peer-to-Peer Systems.In Proc. of the INFOCOM'2003.

[5] Crespo A，Garcia-Molina H. Routing indices for peer-to-peer systems.In Proc.of the 28th Conference on Distributed Computing Systems，July 2002.

[6] 吳宇，虞淑瑤，宋成. 自適應P2P網絡搜索算法[J].計算機工程，2006.3(19):41.

[7] Qianbing Zheng，WeiPeng，Yongwen Wang. An Efficient Broadcast Algorithm Based on Connected Dominating Set in Unstructured Peer-to-Peer Network.IN:X.zhou et al. Wise 2004，LNCS 3306，Berlin Heidelberg:Spring-Verlag，2004，724-729.

[8] 李士勇，等.蟻群算法及其應用[M].哈爾濱工業大學出版社，2004.