1、南京郵電大學碩士學位論文基于非結構化P2P網絡的資源搜索算法研究姓名：張莉申請學位級別：碩士專業：計算機應用技術指導教師：宗平20090308南京郵乜大學碩研究生學位論殳摘要摘要近年來，隨著對等網絡（，）規模、信息量和用戶量的飛速增長，技術成為人們研究與關注的焦點。在網絡中，節點既是客戶機，享用其他節點提供的服務，同時又充當服務器，為其他節點提供服務。網絡中的節點都是對等的，節點之間進行直接的連接與共享。然而，所有系統都面臨一個難題，即如何在缺少集中控制的、大規模的、分布式的網絡中找到并定位信息。現有的系統的信息檢索機制也存在著種種不足：基于結構化網絡的檢索效率雖然很高，然而由于構造過于嚴格，

2、難以在上普及，而且對復雜查詢的支持能力比較差；非結構化網絡實現簡單，是網絡的主要實現方式，但是由于搜索的盲目性，其檢索效率又普遍低下。本文在深入研究網絡拓撲結構和搜索算法的基礎上，重點研究基于非結構化網絡的搜索算法的改進，提出了一種改進的資源搜索算法。該算法通過興趣相似的分析引入節點相似度，將節點關系分組為鄰居節點、朋友節點和捷徑節點，使節點搜索有不同優先級：同時引入螞蟻算法，將節點相似度映射為信息素，采用正反饋的方式來用搜索結果修正節點相似度。仿真實驗的結果表明，該算法有效地約束了搜索范圍，提高了資源搜索的搜索成功率、減少了搜索時間和網絡流量。關鍵字：，非結構化，興趣相似，螞蟻算法，資源搜索

3、南京郵乜大學碩研宄牛學位論義（），；，：，南京郵電大學學位論文原創性聲明本人聲明所呈交的學位論文是我個人在導師指導下進行的研究工作及取得的研究成果。盡我所知，除了文中特！）以標注和致謝的地方外，論文中不包含其他人已經發表或撰寫過的研究成果，也不包含為獲得南京郵電大學或其它教育機構的學位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均己在論文中作了明確的說明并表示了謝意。研究生簽名：塑當日期：南京郵電大學學位論文使用授權聲明南京郵電大學、中國科學技術信息研究所、國家圖書館有權保留本人所送交學位論文的復印件和電子文檔，可以采用影印、縮印或其它復制手段保存論文。本文電子文檔的內容和紙

4、質論文的內容相一致。除在保密期內的保密論文外，允許論文被查閱和借閱，可以公布（包括刊登）論文的全部或部分內容。論文的公布（包括刊登）授權南京郵電大學研究生部辦理。研究生簽名：拯蜀導師簽名：日期：翊蘭：！南京郵電大學碩上研宄生學位論遷第章引言研究背景第一章引言計算機對等互連網（，）技術是目前流行于計算機網絡技術研究領域的一個熱點。互連網在早期階段，由于當時計算機的處理能力、存儲空間以及網絡帶寬等的限制，互連網并沒有采用模式，而是采用的客戶務器（）模式。現在，由于計算機和網絡的性能發生了飛躍性的提高，同時由于模式自身的不足，學術界和企業界開始關注技術。網絡具有集中式服務網絡所缺乏的優勢：可擴展性強

5、、容錯性好、成本低、充分利用分布資源。在網絡中，不存在中心服務器，所有的節點既是客戶機，享用其他節點提供的服務，同時又充當服務器，為其他節點提供服務【】。中的節點都是對等的，節點之間進行直接的連接與共享。模式能讓互連網上的閑散資源得到充分的利用，網絡的容錯性能也大大提高。成功的典范是和。在網絡中，信息的傳播更加迅速，同時也優化了網絡的帶寬利用情況。目前，技術己被應用于文件共享、分布式計算、協同工作、即時通訊等許多領域，對計算機技術的應用產生了重要影響引。由于網絡系統蘊含著巨大的技術潛力和商業價值，網絡系統以及應用迅速在中蔓延，其流行已經掀起了學術研究的熱潮。關于的系統結構、基于的應用、自組織特

6、征、搜索與查找、流量和性能評估等等領域，已經有了較多的研究工作成果。目前技術研究的一個重要問題是資源搜索。研究網絡的搜索技術具有重要的理論意義和實用價值。從理論意義上講，網絡資源的存在形式對搜索技術提出了新的要求。網絡上的資源內容豐富多樣，其分布具有極大的分散性。同時由于節點的自由加入或退出，網絡的資源還處于不斷的動態變化之中。因此的搜索技術和現有的搜索技術有很大的不同。從實用價值上講，在應用短短幾年的發展時間里，它成為了占用流量的主要應用類型，根據年月美國的統計，文件交換已經占美國流量的以上，而年這一數據僅為左右。根據專家預測，這一比例在未來幾年還將繼續上升。現階段互連網上大量資源被閑置，沒

7、有充分的被利用，搜索技術可以幫助人們方便的找到各種資源，提高資源的利用率，南京郵電大學碩上研究生學位論遷第一章引言實現資源的充分共享。同時搜索技術可以幫助人即時找到協作對象，能夠進行跨越地理位置障礙的協同工作。系統支持大量用戶的能力，己經開始顯示出技術優勢：它能夠以較低的成本快速地部署強大的、大規模的分布式應用。因此，研究的搜索技術具有重要的現實意義。研究現狀根據網絡結構的不同，現有的檢索方法主要包括三類【】：集中式的搜索機制，基于結構化網絡的搜索和基于非結構化網絡的搜索。傳統的搜索方法使用集中式搜索，其典型應用是。和網頁搜索引擎類似，使用中央目錄服務器保存節點信息和資源信息，搜索時需要訪問中

8、央目錄服務器獲取相關節點信息，最后節點直接連接交換資源。顯而易見，中央目錄服務器是整個系統的關鍵，承擔了大部分信息保存和交流的功能；服務器一旦癱瘓整個系統將崩潰。因此的服務器容易形成瓶頸，成本過高，現在己不是系統發展的主流技術方法。結構化網絡使用的搜索方法主要是（）搜索，在結構化的分布式網絡上使用分布式哈希表定位。結構化網絡包括、等。在這類網絡中，每個節點都有固定的編址，整個網絡具有相對穩定而規則的拓撲結構，因而表現出對網絡中路由的指導性和網絡中節點和數據管理的較強控制力。目前搜索的相關研究也比較活躍，提出了的變種】和，以及的變種】等。但是，結構化系統也有較大的缺陷：對于網絡拓撲結構的確定性認

9、識，使得想要獲取更短的路徑長度必然導致度數（鄰居數）的增加，也將造成大度數鄰居關系的維護復雜度增加，也不滿足狀態劇烈的網絡應用的需求；哈希函數將兩個內容相似度很高但不完全相同的資源生成完全不同的哈希值，存放到完全隨機的兩個節點上，因而具有精確關鍵詞映射的特性，但是支持語義比較困難，無法與信息檢索等領域的研究成果結合，阻礙了基于的系統的大規模應用。非結構化的網絡中每個節點之間是比較松散的關系，網絡沒有確定的拓撲結構。在搜索資源的時候主要采用泛洪算法進行消息轉發。最有名的應用是】，采用的是廣播式的泛洪搜索機制。由于中的節點數服從“”規律（冪率分布），即少數的節點擁有很高的連接度，導致“小世界現象，

10、因此的搜索機制南京郵大學碩上研究生學位論史第一章引言能較快發現目的節點，面對網絡的動態變化也體現較好的容秘始日匕，力。非結構化網絡下的泛洪搜索速度較慢，采用廣播式的查詢使得網絡負擔較重，容易造成網絡擁塞；另外搜索具有定的盲目性，一般不提供性能保證，查詢也可能沒有結果。但是非結構化的網絡拓撲結構簡單，易于實現，也能夠適應大規模分布式應用的發展。針對泛洪搜索性能較差，研究者提出了些改進方法，如隨機泛測、迭代泛洪、隨機漫步【川和等。針對泛洪搜索的盲目性，也提出了非結構化網絡下的啟發式搜索算法，如節點索引】、基于興趣的搜索【、混合搜索【】等。現實網絡中的一些實際情況使得準確迅速地定位資源成為一個難題。

11、文檔隨機分布在網絡節點中，相鄰節點存儲的內容并不相似，為了保障搜索效果，就必須遍歷比較多的節點，從而加大了網絡帶寬壓力，也使節點由于需要頻繁處理搜索而負擔較重；網絡中存儲熱點內容的節點被頻繁訪問而消耗較多的主機資源和帶寬，需要調動網絡更多節點分擔負載；網絡節點的動態變化性較強，需要系統具有較高的可擴展性。資源搜索定位方法的優劣直接關系系統的性能和可擴展性。現有的資源定位機制無論是非結構化網絡還是結構化網絡，都存在不足【】【】。因此，研究搜索速度快、成本低、分布性好、支持多關鍵詞搜索，帶寬要求小的資源搜索方法對于應用的進一步發展具有很重要的意義。搜索技術是最近幾年的研究熱點，具有以下趨勢：發展興

12、趣關系網絡，使得具有相近共享興趣的節點在網絡上距離較近，這也反映了人類社會中的小世界現象；引入相對成熟的信息檢索技術，提高搜索的效率；研究結構化和非結構化的改進技術，將兩者結合形成新的技術；研究和人類社會網絡相結合的網絡，使其具有更安全的身份認證、更高效的組內協作等特性。本文工作與組織結構本文的主要研究工作有：（）在對現有網絡資源定位機制的深入研究基礎上，針對非結構化網絡的搜索算法，提出了一種改進的資源搜索算法。（）算法通過興趣相似的分析引入節點相似度，將節點關系分組為鄰居節點、朋友節點和捷徑節點，使節點搜索有不同優先級；同時引入螞蟻算法，將節點相似度映射為信息素，采用正反饋的方式來用搜索結果

13、修正節點相似度。（）通過模擬實驗測試其性能，仿真實驗的結果表明，算法有效地約束了搜南京郵電大學碩研生學位論丈第一章引言索范圍，提高了資源搜索的搜索成功率、減少了搜索時間和網絡流量。（）本文的研究工作有助于解決當前網絡資源搜索機制的不足，更好地進行資源定位，促進網絡資源共享的發展。本文的組織結構如下：第一章論述了本文研究工作的背景與國內外研究現狀，并對本文的研究工作和論文的組織結構做出了說明。第二章介紹了的發展與主要特點等，著重描述了的網絡拓撲結構，以及相關的應用。第三章分析了集中式的搜索技術、結構化的搜索技術、非結構化的搜索技術等，并分別從用戶角度和網絡角度討論了搜索技術的評價方法。第四章提出

14、了一種基于興趣相似和正反饋的資源搜索改進策略，重點說明中的元數據表示資源、節點相似度、節點分組和結果正反饋等關鍵實現技術，以及節點的加入退出和搜索路由算法的設計方法。第五章給出了改進的算法的仿真實驗，通過試驗驗證了算法的正確性和有效性，說明了算法在資源搜索性能上有較大的提高。第六章總結了本文的研究工作，展望了下一步改進和發展的方向。的發展第二章系統應用最初出現時和現在并不相同，事實上可以認為它是若干不同技術以及流行趨勢的產物。兩種趨勢導致了應用技術研究的迅速發展：首先是某些新技術與軟件工程結合，形成了一種將工作分散的趨勢。計算正是這種分散工作趨勢的自然結果。其次從工程的角度看來，在企業應用集成

15、等因素的驅動下，過去十年漸漸形成一種從集中的單機系統轉向分布式系統的趨勢。在集中式的應用中進行控制是相對容易的，這一點在一定程度上抑制了分布式潮流的發展。然而隨著互聯網的發展，以及商務交易方式的日益流行，全面的分布式計算也就成為一種商業需求。對功能強大的網絡計算機的需求以及昂貴的帶寬開銷，進一步影響了分布式計算的發展。雖然最初被設計為文件交換應用，但機制能夠被用來訪問任何種類的分布式資源，并為基于的應用提供新的可能性。除了技術方面之外，社會因素也是一個重要原因。毫無疑問，人們現在對計算技術的熱切關注起源于、，以及這些家族的其他成員產品。這些產品將技術中的一部分下放到客戶端用戶的手中，使得人們越

16、來越關注技術的強大功能。的發展可分為以下三個階段：第一代的文件交換服務以和獨領風騷，其技術是建立一個大型的集中化索引，對網絡上所有的可用資源進行追蹤。這種方法雖然相當有效率，讓使用者可以存取到龐大的資源，但同時發生了最著名的官司：美國唱片業協會（）代表多家唱片公司以違反版權保護法為由把公司推上法庭，歷時三年最終將告倒，法院最終判定侵權。第二代的分散式服務以國外的和國內迅速崛起的為代表。這種方式在電腦間發送搜索請求，一直到找到文件為止，然后再將信息傳回搜索者的電腦。這種技術一開始相當不便，特別是數以百萬計的搜索要求在網絡上的每一臺電腦間來回發送時，在高峰時段往往造成網絡大塞車。后來通過隨機方式選

17、出品質較優的用戶作為節點服務器，用戶可從節點服務器上獲得，下載方法也越來越進步。但與第代軟件命運截然不同的是，美國法院認為，這種分散式的應用是合法的，這種軟件的散播者并未直接控制網絡上所出現的行為。第三代的網絡則是以、等為代表，比以前更為分散化。它采用“分散式雜湊表”的方法，基本上是對網絡上某一特定時刻的文件進行快照（），然后將這些信息分散到整個網絡里。為了找到特定的文件，搜索的要求先到達網絡上的任何一臺電腦，然后這臺電腦就會再將它轉到另一臺有更多文件信息的電腦，第三臺電腦可能就擁有文件本身，或者也可能再繼續轉到其他有正確信息的電腦。整個過程有點像依照線索循序問路而找到正確方向，而不是路上隨便

18、抓人問路。每個網絡相關信息，會隨電腦及文件的加入而持續更新。于年向哈佛學生及買下這項技術。這兩位前哈佛學生表示，他們的技術只要跳三至四次就可以在幾百萬臺電腦的網絡里找到任何文件，不管這個文件多么稀有。這種技術也讓一些應用有了新的前景，例如網絡電話。這種有效率的網絡路由技術可用于快速連接網絡電話，但也給傳統電信運營商帶來了沖擊。的特點一般講，具有以下特劇（）分散化網絡中的資源和服務分散在所有節點上，信息的傳輸和服務的實現都直接在節點之間進行，可以無需中間環節和服務器的介入，避免了可能的瓶頸。即使是在混合中雖然在查找資源、定位服務或安全檢驗等環節需要集中式服務器的參與，但主要的信息交換最終仍然在節

19、點中間直接完成這樣就大大降低了對集中式服務器的資源和性能要求。（）可擴展性在傳統的架構中，系統能夠容納的用戶數量和提供服務的能力主要受服務器的資源限制。為支持互聯網上的大量用戶，需要在服務器端使用大量高性能的計算機，鋪設大帶寬的網絡。為此等技術紛紛上陣。在此結構下，集中式服務器之間的同步、協同等處理產生了大量的開銷，限制了系統規模的擴展。在網絡中，隨著用戶的加入不僅服務的需求增加了，系統整體的資源和服務能力也在同步地擴充，始終能較容易地滿足用戶的需要。即使在諸如等混合型架構中，由于大部分處理直接在節點之間進行，大大減少了對服務器的依賴，因而能夠方南京郵電大學碩研冗生學位論遷第二章系統便地擴展到

20、數百萬個以上的用戶。而對于純來說，整個體系是全分布的，不存在瓶頸。理論上其可擴展性幾乎可以認為是無限的。（）健壯性在互聯網上隨時可能出現異常情況，網絡中斷、網絡擁塞、節點失效等各種異常事件都會給系統的穩定性和服務持續性帶來影響。在傳統的集中式服務模式中，集中式服務器成為整個系統的要害所在，一旦發生異常就會影所有用戶的使用。架構則天生具有耐攻擊、高容錯的優點。由于服務是分散在各個節點之間進行的，部分節點或網絡遭到破壞對其它部分的影響很小。而且模型一般在部分節點失效時能夠自動調整整體拓撲，保持其它節點的連通性。事實上，網絡通常都是以自組織的方式建立起來的，并允許節點自由地加入和離開。一些模型還能夠

21、根據網絡帶寬、節點數、負載等變化不斷地做自適應式的調整。（）隱私性隨著互聯網的普及和計算存儲能力飛速增長，收集隱私信息正在變得越來越容易。隱私的保護作為網絡安全性的一個方面越來越被大家所關注。目前的通用協議不支持隱藏通信端地址的功能。攻擊者可以監控用戶的流量特征，獲得地址。甚至可以使用一些跟蹤軟件直接從地址追蹤到個人用戶。在網絡中，由于信息的傳輸分散在各節點之間進行而無需經過某個集中環節，用戶的隱私信息被竊聽和泄漏的可能性大大縮小。此外。目前解決隱私問題主要采用中繼轉發的技術方法，從而將通信的參與者隱藏在眾多的網絡實體之中。在傳統的一些匿名通信系統中，實現這一機制依賴于某些中繼服務器節點。而在

22、中，所有參與者都可以提供中繼轉發的功能，因而大大提高了匿名通訊的靈活性和可靠性，能夠為用戶提供更好的隱私保護。（）高性能性能優勢是被廣泛關注的一個重要原因。隨著硬件技術的發展，個人計算機的計算和存儲能力以及網絡帶寬等性能高速增長。而在目前的互聯網上，這些普通用戶擁有的節點只是以客戶機的方式連接到網絡中，僅僅作為信息和服務的消費者，游離于互聯網的邊緣。對于這些邊際節點的能力來說，存在極大的浪費。采用架構可以有效地利用互聯網中散布的大量普通節點，將計算任務或存儲資料分布到所有節點上。利用其中閑置的計算能力或存儲空間，達到高性能計算和海量存儲的目的。這與當前高性能計算機中普遍采用的分布式計算的思想是

23、一致的。但通過利南京郵電大學碩上研究生學位論殳第二章系統用網絡巾的大量空閑資源，可以用更低的成本提供更高的計算和存儲能力。的網絡拓撲結構節點之間的拓撲結構一直是確定系統類型的重要依據。目前互聯網絡中廣泛使用集中式、層次式等拓撲結構。本身是世界上最大的非集中式的互聯網絡，但是九十年代所建立的一些網絡應用系統大都是完全的集中式系統，許多應用都是運行在集中式的服務器系統上。集中式拓撲機構系統目前面臨著過量存儲負載、拒絕服務（，）攻擊、網絡帶寬限制等一些難以解決的問題。系統主要采用非集中式的拓撲結構，改變了網絡“內容”所在的位置，使其從“中心”走向“邊緣”，也就是說內容不再存在于主要的服務器上，而是存

24、在于所有用戶的機上。使得重新煥發活力，不再是被動的客戶端，而是具有服務器和客戶端雙重特征的設備。實際上，模式也不一定是完全無中心的。它可分為純粹和混合兩類。純粹是指所有參與的計算機都是對等點，各對等點之間直接通信，自始至終都沒有中心服務器對對等點之間的信息交換進行控制、協調或者處理。混合式則依賴中心服務器執行一些功能。拓撲結構是指分布式系統中各個計算單元之間的物理或者邏輯的互聯關系。根據結構關系可以將系統細分為四種拓撲形式】：（）中心化拓撲（）（）全分布式非結構化（）（）全分布式結構化拓撲（）（）半分布式拓撲（）中心化拓撲中心化拓撲最大的優點是維護簡單，資源發現效率高。各節點之間可以直接建立連

25、接，但網絡的構建需要服務器，通過集中認證，建立索引機制。然而這里的服務器僅用于輔助對等節點之間建立連接，一旦連接成功，服務器不再起作用，對等節點之間直接進行通信。這不同于模式中的服務器，也可以認為是弱化了服務器的作用。這種網絡模式和純分散式網絡相比，易于發現網絡節點，易于管理且安全性較好。由于資源的發現依賴中心化的目錄系統，發現算法靈活高效并能夠實現復雜的查詢。南京郵乜大學碩上研究生學位論迎第二幸系統然而這種對等網絡模型也類似模式，存在以下問題：（）中央索引服務器的癱瘓容易導致整個網絡的崩潰，因此可靠性和安全性較低。（）隨著網絡規模的擴大，對中央索引服務器進行維護和更新的費用將急劇增加，所需成

26、本較高。（）中央索引服務器的存在常引起版權問題上的糾紛，服務提供商會被追究法律責任。（）對小型網絡而言，中心化拓撲模型在管理和控制方面占一定優勢。但鑒于其存在的上述缺陷，該模型并不適合大型網絡應用。中心化拓撲結構是第一代網絡采用的結構模式，經典案例就是著名的共享軟件。全分布式非結構化拓撲全分布式非結構化拓撲的網絡是在重疊網絡（）中采用了隨機圖的組織方式，節點度數付出規律（冪次法則），從而能夠較快發現目的節點，面對網絡的動態變化體現了較好的容錯能力，因此具有較好的可用性。同時可以支持復雜的查詢，如帶有規則表達式的多關鍵詞查詢，模糊查詢等。采用這種拓撲結構最典型的案例就是。和最大的區別在于是更加純

27、粹的系統，因為它沒有中心索引服務器，每臺機器在網絡中是真正的對等關系，既是客戶端優勢服務器。在文件檢索方面，它與也不同。在網絡發展的初期，它主要采用基于完全隨機圖的泛洪搜索算法。由于非結構化網絡將重疊網絡認為是一個完全隨機圖，節點之間的鏈路沒有遵循某些預先定義的拓撲結構來構建。這些系統優點是容錯性較好，支持復雜的查詢，受節點頻繁加入和退出系統的影響小。缺點是查詢的結果可能不完全，查詢速度較慢，采用泛洪查詢的系統對網絡帶寬的消耗非常大，并由此帶來可擴展性差等問題。全分布式結構化拓撲全分布式結構化拓撲的網絡主要是采用分布式散列表（，）技術來組織網絡中的節點。是個由廣域范圍大量節點共同維護的巨大散列

28、南京郵電大學預研宄生學位論文第二章系統表。散列表被分割成不連續的塊，每個節點被分配給一個屬于自己的散列塊，并成為這個散列塊的管理者。通過加密散列函數，一個對象的名字或者關鍵詞被映射為位或者位的散列值。類結構能夠自適應節點的動態加入或者退出，有良好的可擴展性、魯棒性、節點分配的均勻性和自組織能力。由于重疊網絡采用了確定性拓撲結構，可以提供精確的發現。只要目的節點存在與網絡中，總能發現它，發現的準確性得到了保證，經典的案例是、和。半分布式拓撲半分布式拓撲結構，也即混合模式。它吸取了中心化結構和全分布式非結構化拓撲的優點，選擇在處理、存儲、帶寬等方面性能較高的節點作為超級節點，在各個超級節點上存儲了

29、系統中其他部分節點的信息，發現算法僅在超級節點之間轉發，超級節點再將查詢請求轉發給適當的葉子節點。半分布式也是一個層次式結構，超級節點之間構成一個高速轉發層，超級節點和所負責的普通節點構成若干層次。采用這種結構的最典型的案例就是。半分布式拓撲結構如圖所示。的應用圖的拓撲結構目前，技術的應用主要體現在以下幾個方面：（）文件共享技術使任意兩臺相連接的計算機直接共享文檔、多媒體和其它文件成為可能。利用技術，計算機之間可以進行直接交互，而不需要使用任何臺中央服務器。在南京郵電大學碩上研亢生學位論疋第二章系統網絡中，對等機通過不同的查詢機制定位含有所需資源的其它對等機后，將直接與其建立連接，并下載所需文

30、件。和就是將文件共享技術投入應用的最好例子。（）分布式計算分布式計算（）是技術的另一個重要特征。簡單的說，分布式計算就是把原來需要超級計算機處理的龐大任務進行分塊，并通過位于系統控制中心的調度軟件對分塊任務進行調度和管理，分發給許多普通計算機來執行其具體運算操作，操作完成后再將結果返回給控制中心。（）協作系統協作系統（）構成了完全另外一種類型的網絡，即一群一起工作的用戶相互間共享著不同的資源，但他們通過協同工作完成一項共同的任務。與文件共享形式不同，協作系統中的一個用戶可以在同一時刻將一個信息多點傳送到若干個用戶。適用于這種應用的最佳架構仍在研究之中。（）電子商務基于技術的直接性和易擴展性，該

31、模式很適用于用戶之間的商品買賣，目前它主要可以被應用于金融服務、電子商務集市和廣告行銷等。（）以為基礎的深度搜索引擎技術的另一個優勢是開發出強大的搜索工具。技術使用戶能夠深度搜索文檔，而且這種搜索無需通過服務器，也可以不受信息文檔格式和宿主設備的限制，可達到傳統目錄式搜索引擎（只能搜索到一的網絡資源）無可比擬的深度【引。本章小結本章主要介紹了系統的基本概念，包括的發展過程、系統的特點、的網絡拓撲結構和的相關應用。重點分析了的四種網絡拓撲結構：中心化拓撲、全分布式非結構化拓撲、全分布式結構化拓撲和半分布式拓撲，并指出了四種拓撲結構的優點和缺陷。南京郵電大學碩上研究生學位論遷第三章搜索算法搜索算法

32、第三章搜索算法根據網絡結構的不同，現有的檢索方法主要包括三類：集中式的搜索機制，基于結構化網絡的搜索和基于非結構化網絡的搜索【】【。集中式搜索集中式的搜索機制主要用于中心化拓撲結構的網絡。】是第一個通過獲得大規模應用并取得巨大成功的對等網絡系統，其成功得益于其采用的基于中央目錄服務器的集中式對等網絡結構。基于中央目錄服務器的對等網絡搜索模型工作方式如圖所示。圖中每個節點向中央目錄服務器提交本地存儲的文檔目錄，并由目錄服務器編制文檔的索引。節點向中央目錄服務器發起搜索請求，并由目錄服務器檢索本地文檔索引后返回存儲匹配文檔的節點地址。文檔的下載直接在搜索請求的發起節點和期望文檔的存儲節點之間進行，

33、不再通過中央目錄服務器。圖。基于中央目錄月艮務器的搜索模型以為例，所有節點共享的文檔目錄存儲在個中央目錄服務器上。新加入的節點將其要共享的文檔目錄上傳到目錄服務器，并由該服務器對這些目錄信息進行索引。節點查找和下載文檔的過程如下，基于中央目錄服務器的搜索模型如圖所示。（）當節點需要查找某個文檔時，該節點向中央服務器提交查詢請求，指明欲查詢文檔的某些屬性，例如作者、關鍵字等。（）中央服務器通過檢索存儲的目錄索引，找到共享該文檔的所有節點，并返回它南京郵巾大學碩上研充生學位論艾第三章搜索算法們的地址列表。（）節點通過比較返回列表中各個節點操作完成的時間，選擇一個時延最小的節點。（）節點直接連接節點

34、并完成文檔下載，這一過程不再通過中央目錄服務器。從上面的過程可以看到，由于采用了中央目錄服務器，可以提供快速準確的搜索服務。搜索的方式也可以很靈活，其靈活程度和準確度取決于用戶提供給目錄服務器的文檔目錄信息的詳實程度。但是這種結構的最大缺陷在于可擴展性不高，集中式的中央目錄服務器容易成為系統的瓶頸。的另外一個缺陷是安全性較差，密碼以明文傳輸，沒有認證機制，不能提供匿名。結構化網絡的搜索結構化網絡指的是、之類的網絡。在這類網絡中，每個節點都有固定的編址，整個網絡具有相對穩定而規則的拓撲結構，依據拓撲結構，可以給網絡的每個節點指定一個邏輯的地址，并把地址和節點的位置對應起來。給定某個地址，拓撲結構

35、保證只需要通過（）珧就能路由到具有相應地址的節點上去（是網絡中的節點數）。結構化網絡可以用來有效地存儲分布的信息，網絡中存儲的信息可以用，這個二元組來惟一定位，其中是信息的索引，是存儲該信息的節點。，分布地存儲在結構化網絡中，每個節點存儲那些和自己地址相近的二元組。這樣，要查找某個索引為的信息，只需要路由到地址和相近的節點就可以獲得，的二元組，從而定位目標信息，就像平常在哈希表中查找數據一樣，所以稱為分布式的哈希表（，）。提供了一個分布式容錯查找和路由基礎平臺，在此平臺基礎之上，可以開發各種應用。的思想來源于。在中，節點使用自己所知道的鄰近節點表，按照目的來逐步傳遞消息。基于的思想，加入了容錯

36、機制，從而可適應的動態變化的特點。為適應網絡的動態特性，作了很多改進，增加了額外的機制實現了網絡的軟狀態（），并提供了自組織、魯棒性、可擴展性和動態適應性，當網絡高負載且有失效節點時候性能有限降低，消除了對全局信息的依賴、根節點易失效和彈性差的問題。】是微軟研究院提出的可擴展的分布式對象定位和路由協議，可用于構建大規南京郵電大學碩研究生學位論定第三章搜索算法模的系統。如圖所示，在中，每個節點分配一個位的節點標識符號（），所有的節點標識符形成了一個環形的空間，范圍從到，節點加入系統時通過散列節點地址在位空間中隨機分配。如圖是的消息路由。圖拶的消息路由啪圖的拓撲形狀項目誕生于美國的麻省理工學院。如

37、圖所示，它的目標是提供一個適合于環境的分布式資源發現服務，它通過使用技術使得發現指定對象只需要維護（）長度的路由表。在技術中，網絡節點按照一定的方式分配一個唯一節點標識符（），資源對象通過散列運算產生一個唯一的資源標識符（），且該資源將存儲在節點與之相等或者相近的節點上。需要查找該資源時，采用同樣的方法可定位到存儲該資源的節點。因此的主要貢獻是提出了一個分布式查找協議，該協議可將指定的關鍵字（）映射到對應的節點（）。從算法來看，是相容散列算法的變體。圖是的拓撲形狀。（）耍，目采用多維的標識符空間來實現分布式散南京郵電大學碩：宄牛學位論殳第三幸搜索算法列算法。將所有節點映射到一個維的笛卡爾空間中

38、，并為每個節點盡可能均勻的分配塊區域。采用的散列函數通過對（，）對中的進行散列運算，得到笛卡爾空間中的一個點，并將（，）對存儲在擁有該點所在區域的節點內。采用的路由算法相當直接和簡單，知道目標點的坐標后，就將請求傳給當前節點四鄰中坐標最接近目標點的節點。是一個具有良好可擴展性的系統，給定個節點，統維數為，則路由路徑長度為（），每節點維護的路由表信息和網絡規模無關為（）。這類結構最大的問題是的維護機制較為復雜，尤其是節點頻繁加入退出造成的網絡波動（）會極大增加的維護代價。另外僅支持精確關鍵詞匹配查詢，無法支持內容或語義等復雜查詢。非結構網絡的搜索“非結構”是和結構化網絡相對而言的。非結構網絡中每

39、個節點之間是比較松散的關系，節點的加入和離開僅需遵循一些簡單的規則。非結構網絡中每個節點保存各自共享的文檔，由于不再存在中央目錄服務器，每個節點對本地保存的文檔進行索引，并轉發或應答其他節點的搜索請求。由于采用完全分布式的網絡拓撲，非結構網絡避免了集中式網絡中中央目錄服務器帶來的系統瓶頸的問題。但由于非結構網絡中缺乏有效的搜索機制，大多數算法采用泛洪或類似泛洪的盲目搜索方式【，導致在網絡中產生過度的流量，同樣影響了系統的可擴展性。在非結構化網絡內進行搜索的技術分為兩類【】【：（）不利用任何文檔分布信息的盲搜索（），通過在網絡中傳播查詢信息并且把這些信息不斷擴散給每個節點，通過泛洪方式找到想要的

40、資源，典型系統如；（）并用網絡中文檔分布信息的啟發式搜索（），在搜索過程中將利用已有的一些信息來輔助查找，所以能夠比較快找到資源，典型系統如。常見的一些非結構化網絡的搜索算法如下：（）泛洪搜索（）在現在的網絡中，泛洪搜索使用比較廣泛。對等網絡系統，就是采用泛洪算法檢索路由。在網絡中，每個節點都不知道其他節點的資源。如是個用于文檔共享的當它要尋找某個文件，把這個查詢南京郵電大學碩上研究生學位論迎第三章搜索算法消息傳遞給它的相鄰節點，如果相鄰節點含有這個資源，就返回一個的消息給。如果它相鄰的節點都沒有命中這個被查淘文件，就把這條消息轉發給自己的相鄰節點。這種方式下查詢消息像洪水在網絡中各個節點流動

41、，所以叫做搜索。為了限制搜索的范圍，消息被設置了一個初始的值。如圖所示：搜索的節點一開始，它每傳播一次減，如果減到還沒有搜索到資源，則停止。如果搜索到資源則返回目標機器的信啟以用來建立連接。在搜索過程中可能出現循環，但是由于有控制，所以這個循環不會永遠進行下去，當的時候自然結束。圖是基于泛洪的搜索模型。圖基于泛洪的搜索模型這種搜索策略是首先遍歷自己的鄰接點，然后再向下傳播，所以又稱為寬度優先搜索算法（）。泛洪算法有一系列優點，使得在現在也有極強的生命力：（）節點覆蓋率高。一項研究表明，在網絡中，采用泛洪方式，能夠搜索到的節點（在中為）。這是因為在泛洪中，隨著跳數的增加，節點個數呈指數級增加；（

42、）健壯性好。一個節點出現故障或者是退出，對其余節點幾乎沒有影響。因為在泛洪中，每個節點要向所有鄰居節點發送消息，查詢消息能夠通過節點之間所有可能的路徑被傳送；（）響應時間快。泛洪中節點是并行的方式向鄰居節點發送查詢消息的，所以相應地響應時間縮短了。泛洪算法也有其明顯的缺陷【。隨著網絡規模不斷擴大，網絡節點的不斷增多，泛洪方式發送消息將造成網絡流量的急劇增加，從而導致網路中部分低帶寬節點因網絡資源過載而失效，查詢結果可能不完全，查詢速度將變慢，并由此帶來可擴展性差等問題。因此有較多研究對泛洪算法進行改進。（）搜索方法這種方法是在寬度優先方法上面作了一定修改。跟搜索方法不同，南京郵屯大學碩上研究生

43、學位論艾第三章搜索算法搜索源只是隨機的選取一定比例的相鄰節點作為查詢信息的發送目標，而不是發送給所有相鄰節點。相比于方法來說，是以時間換取空間的有效嘗試。（）搜索方法迭代泛洪【】是方法的改進，策略循環遞增（）值，這個值用來控制的搜索深度。跟搜索方法給賦一個較大的值不同，這種方法在初始階段，給一個很小的值，如果在減為，還沒有搜索到資源，則給重新賦更高的值。當查詢的結果滿足要求或者已經到達最大的深度限制，過程結束。在泛洪中，隨著深度的增加，節點個數指數增加。因此，如果能夠在在小于最大深度限制內找到滿意結果，和直接以最大深度進行泛洪搜索比較起來，就不必查詢很多節點，節省大量的資源消耗。在好的情況下，

44、迭代泛洪能夠減少搜索的半徑，大量減少查詢的節點個數，從而減少搜索的資源開銷。如果網絡內重復資源豐富，這種方法在不影響搜索質量的基礎上將減少網絡內的查詢流量，在有的文獻中亦稱為（擴展環搜索）。但是在最壞的情況下，迭代泛洪可能要進行到最后一次迭代，這時迭代泛洪就比直接泛洪更糟糕，因為多次迭代在網絡上發送了大量的查詢消息，占用了網絡帶寬，也給節點增加了處理負擔，消息響應延遲很大。（）搜索方法隨機漫步】中，請求者發出個查詢請求給隨機挑選的個相鄰節點。然后每個查詢信息在以后的漫步過程中直接與請求者保持聯系，詢問是否還要繼續下一步。如果請求者同意繼續漫步，則又開始隨機選擇下一步漫步的節點，否則中止搜索。（

45、）的搜索方法建立，它存儲著離它最近的葉子節點的文件信息，這些，再連通起來形成一個當葉子節點需要查詢文件，它首先從它連接的的索引中尋找，如果找到了文件，則直接根據文件所存儲的機器的地址建立連接，如果沒有找到，則把這個查詢請求發給它連接的其他超級節點，直到得到想要的資源，、等都是基于這種超級節點的思想。（）基于移動的搜索方法移動是一個能在異構網絡中自主地從一臺主機遷移到另一臺主機，并可與其他或資源進行交互的程序。非常適合在網絡環境中來幫助用戶完成信息檢索的任務。現在意大利的一些研究人員在移動結合方面做了一些前沿的南京郵電大學碩上研亢生學位論迎第三章搜索算法研究，其中的一些想法，就是通過在軟件中嵌入

46、的運行時環境。當有節點需要搜索的時候，它發送一個移動給它相鄰的節點，移動記錄著它的一些搜索的信息。當這個到達一臺新的機器上，然后在這個機器上進行資源搜索任務，如果這臺機器上沒有它想要的資源，則它把這些搜索的信息傳給它的鄰節點，如果找到資源，則返回給請求的機器。（）方法】方法是一種啟發式搜索方法。節點除了給本節點的資源做索引外，還要建立跳距離內的鄰居節點的數據索引。稱為索引半徑，是一個系統變量。當時，節點只建立自己的數據索引。節點收到查詢請求時，可以代替跳距離內的鄰居節點處理查詢請求。采用這種方法，查詢很少一部分節點就相當于查詢了許多節點，可以直接定位到資源的位置，而不需要再次轉發查詢信息。在這種搜索策略下，處理查詢請求的節點大大減少了，因此總的處理時間減少了。但是在網