[發明專利]大規模非結構化P2P網絡中的資源搜索方法

無效

• 申請號: 200710035303.7
• 申請日: 2007-07-09
• 公開（公告）號: CN101087305A
• 公開（公告）日: 2007-12-12
• 發明（設計）人: 張一鳴;盧錫城;李東升;劉鋒
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: H04L29/06
• 分類號: H04L29/06;G06F17/30
• 代理公司: 湖南省國防科學技術工業辦公室專利中心
• 代理人: 李傳中

技術領域

本發明涉及計算機網絡中的資源搜索方法，尤其是支持大規模網絡中的高性能資源搜索方法。

背景技術

P2P(peer-to-peer)網絡是近年來興起的一種網絡。在P2P網絡中，各節點在邏輯上是對等的，沒有客戶端和服務器之分，各個節點之間可以直接進行通信和交互。目前，P2P網絡在科學研究、電子商務、電子政務和軍事應用等重要領域都有著廣闊的應用。為了實現資源的有效共享和綜合利用，P2P網絡用戶需要對符合要求的資源進行搜索，資源搜索是P2P網絡的關鍵技術之一。

根據資源組織模式，P2P網絡通常可分為兩種：結構化(Structured)P2P網絡和非結構化(Unstructured)P2P網絡。非結構化P2P網絡由于其簡單性和易用性，目前在Internet上得到了大量應用。本發明針對非結構化P2P網絡中的資源搜索技術。

最初的非結構化P2P網絡資源搜索技術(如泛洪、隨機漫步等)屬于“盲搜索”(blind?search)方法，每一步的搜索方向具有很大的盲目性，導致當資源請求節點距離資源共享節點較遠時，無法迅速搜索到所需資源。因此，目前的資源搜索方法通常由各節點預先對資源信息進行發布、傳播和維護，在資源搜索過程中，資源搜索消息根據中間節點所維護的信息來選擇轉發的方向，進而發現資源。

目前非結構化P2P網絡中的資源搜索問題可以抽象為：如何將大規模的資源信息進行發布和維護，以及如何在資源搜索過程中利用上述資源信息迅速發現資源。

在非結構化P2P網絡中，在各節點之間并沒有類似于DHT的P2P網絡拓撲結構，發布和維護資源信息需要消耗大量的存儲空間和網絡帶寬。因此，目前通常基于Bloom?Filter(BF)技術，使用一個位向量通過較小的存儲開銷來概率地表示一個節點的所有元素。每個節點都維護一個“鄰居表”，保存相關鄰居節點的BF信息。在資源定位時，每個節點根據其“鄰居表”將資源定位消息轉發到最接近目標資源的鄰居節點上，直到最終到達目標節點。

評價資源搜索方法性能的重要參數包括搜索延遲、搜索開銷和維護開銷等。搜索延遲是指為滿足一次資源搜索請求，搜索消息在網絡中轉發的邏輯跳步數；搜索開銷是指為滿足一次資源搜索請求，網絡中產生的搜索消息總數；維護開銷是指每個節點維護本節點和鄰居節點資源信息所需的存儲開銷。為取得良好的實用性能，資源搜索方法應該兼顧多個方面的特性。但這幾個性能特性之間存在沖突，給P2P網絡的廣泛應用帶來困難。

發明內容

本發明所要解決的技術問題在于：針對大規模非結構化P2P網絡中資源信息的維護開銷較小時，搜索延遲和搜索開銷較大的難題，提出了一種在資源信息維護開銷受限的條件下，具有低搜索延遲和低搜索開銷的資源搜索方法。

為了解決上述技術問題，本發明的技術方案為：在資源信息的發布和維護過程中，各節點根據不同鄰居節點的要求對收到的BF信息在丟棄一定比例后進行轉發并保存在鄰居BF表中；在資源搜索過程中，各中間節點計算目標資源與鄰居BF表表項的相似度，并根據BF信息的分布情況，進行多個消息之間相互協同的并行搜索。具體包括：

(1)鄰居BF表：每個度數為d的節點維護了一個d行c列的鄰居BF表T，表中每一個表項是一個Bloom?Filter向量。表項T_ij(1≤i≤d，1≤j＜c)維護了通過第i個鄰居且從信息發布節點經過j步到達本節點的資源信息；表項T_ic(1≤i≤d)則維護了通過第i個鄰居且從信息發布節點經過c步或c步以上到達本節點的資源信息。

(2)資源信息的發布和維護：信息發布節點使用BF表示本地資源信息并發布。在資源信息的發布與傳播過程中，中間節點收到BF信息后，按照各鄰居節點的要求對信息進行丟棄后傳播。

(3)相似度：設資源x對應的Bloom?Filter位向量為U，鄰居BF表中T_N，j^A表項的Bloom?Filter向量為V，使用Like(x，T_N，j^A)表示資源x與T_N，j^A表項的相似度：