孫娟娟，禹繼國

（曲阜師范大學 計算機科學學院，山東 日照 276826）

0 引言

無結構P2P網(wǎng)絡一般采用洪泛法進行資源定位。該方法在查詢受歡迎文件時非常有效，但在查詢稀有文件時效率不高；結構化P2P網(wǎng)絡一般利用分布式哈希表來定位資源。該方法在查詢稀有文件時比較有效，但在進行多關鍵字查詢或者區(qū)間查詢時效率比較低。鑒于它們的優(yōu)缺點，P2P網(wǎng)絡中的混合查詢機制引起了越來越多研究者的關注。

文獻[1]將現(xiàn)有P2P混合查詢策略分成兩類：第一類是基于檢測的簡單混合策略。該策略首先執(zhí)行洪泛，如果在一個預定的時間內沒有返回足夠多的查詢結果，就將其作為一個DHT再次發(fā)起查詢過程，直到查詢內容最終被定位到；第二類是采用閑聊方式利用收集到的聚集信息來估算文件的受歡迎程度，并且通過在相關文件數(shù)目上設定閾值以確定是采用洪泛還是采用DHT。

1 相關工作

動態(tài)查詢是無結構P2P網(wǎng)絡中采用的查詢技術，該方法使用較少的節(jié)點就能夠到達目標節(jié)點。查詢發(fā)起者在一個小的TTL值內通過“刺探”過程將查詢信息發(fā)送給網(wǎng)絡中的一些節(jié)點并由此開始查詢過程。“刺探”查詢的目標是對定位到的資源評估其受歡迎程度[2]。

文獻[3]中，Lu等在Chord[4]的基礎上，提出了多層次P2P資源共享模型 ML-Chord。該模型中的所有資源基于一個選擇的本體被分成不同的類別，每一個類別對應一個覆蓋層；同時選出能力強的節(jié)點作為橋節(jié)點連接到所有Chord環(huán)上，所有橋節(jié)點組成一個Chord環(huán)。

動態(tài)查詢是在無結構P2P網(wǎng)絡中采用的查詢技術，采用這種查詢方法可以使用較少的節(jié)點就可以達目標節(jié)點。查詢發(fā)起者在一個小的 TTL內通過把查詢信息發(fā)送給網(wǎng)絡中的一些節(jié)點開始搜索過程。這個“刺探”查詢的目標是對定位到的資源。這個“刺探”查詢的目標是對定位到的資源評估其受歡迎程度。一種結合動態(tài)查詢的搜索算法應用在了無結構P2P網(wǎng)絡中[5],將動態(tài)查詢應用到無結構的洪泛[6]比文獻[5]中的查詢方法取得了更好的搜索效率。

文獻[5]中，Talia等在Chord上將動態(tài)查詢技巧與文獻[7]提出的有效廣播算法結合。查找過程是首先進行一個刺探階段，如果在刺探階段已得到足夠多的查詢結構，則終止查詢。否則，根據(jù)刺探階段得到的數(shù)據(jù)估算文件的受歡迎程度作為調整洪泛范圍的依據(jù)。

2 ML-Chord中動態(tài)查詢的執(zhí)行

2.1 ML-Chord的結構

圖1 ML-Chord的結構示意

若系統(tǒng)中有C個類別覆蓋層，則整個邏輯覆蓋網(wǎng)中有T=C+1個邏輯覆蓋層。圖1中所示的節(jié)點和雖然標識符不同，但它們是同一個節(jié)點，即相同的節(jié)點位于兩個覆蓋層上，這也意味著該節(jié)點需要維護兩套路由表。

2.2 動態(tài)查詢過程

由于P2P用戶常在本地空間上存儲相似文件，如圖2所示：查詢與a和b相關的文件，與a有關的文件廣泛存儲在系統(tǒng)中的節(jié)點上，而與b有關的文件之存儲在少量節(jié)點上，若按照計算得到。然而，Pa的值應大于Pb的值，由此出現(xiàn)了文件受歡迎程度誤差偏大的情況。

圖2 系統(tǒng)中文件分布舉例

2.3 ML-Chord中的動態(tài)查詢算法

對于給定的一棵二項式樹，它的性質：①Bi中的節(jié)點數(shù)是2i；②Bi的深度為i；③Bi中在l層上的節(jié)點數(shù)目通過二項式系數(shù)及動態(tài)查詢算法需要用到的參數(shù)得到。表1給出了相關的參數(shù)定義。

表1 參數(shù)定義

首先，將當前查找到的資源數(shù)目Rc賦值為0，當接收到一個查詢應答時Rc的數(shù)目就會增加1，集合U初始化為節(jié)點中存儲的與資源 R屬于同一類別的覆蓋層的路由表內所有的獨一無二的指針數(shù)。將Hi設置為N(U), N(U)與網(wǎng)絡中可以查詢到的主機數(shù)目相一致，從集合U中選擇出第一個需要訪問的子集V,集合U隨之做相應更新。

3 性能分析

現(xiàn)在考慮一般情況：假設匹配的資源在節(jié)點間均勻分布，在刺探階段可以得到資源受歡迎程度的準確估計，大多數(shù)的查詢只需要 2次迭代（其中包括刺探階段）。這種情況下，最大的查詢時間是刺探查詢時間和覆蓋最深子樹的迭代查詢時間，即TS=TH×((L+2)+(DU+2))，又Du=log2(N-1)，得到同理，若普通節(jié)點只加入一次覆蓋層且所有節(jié)點在覆蓋層上均勻分布，查詢的時間復雜度為

4 結語

這里將動態(tài)查詢部署在多層次結構化 P2P系統(tǒng)ML-Chord上，節(jié)點根據(jù)查詢資源的類別選擇執(zhí)行動態(tài)查詢，或者由能力更高的橋節(jié)點代為執(zhí)行。動態(tài)查詢的優(yōu)點在于允許執(zhí)行任意類型的查詢，可以根據(jù)文件的受歡迎程度調整查詢范圍，減少了網(wǎng)絡負載。更改后的文件受歡迎程度的簡單估算方法提高了計算準確性，有效地提高了查詢效率。

[1] CHEN Hanhua, JIN Hai, LIU Yunhao, et al.Difficulty-aware Hybrid Search in Peer-to-peer Networks[C].USA:IEEE,2009:71-82.

[2] VLADIMIR VISHNEVSKY, ALEXANDER SAFONOV, MIKHAIL YAKIMOV, et al.Alexander D.Gelman.Scalable Blind Search and Broadcasting over Distributed Hash Tables[J].Computer Communications, 2008, 31(02): 292-303.

[3] LU Juilin, HUANG Yungfa, LU Shuchiu.ML-Chord: A Multi-Layered P2P Resource Sharing Model[J].Network and Computer Applications, May 2009, 32(03):578-588.

[4] STOICA I, MORRIS R, KARGER D, et al.Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications[C].[EB/OL].(2006-11-24) [2009-12-23].http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf.

[5] FISK A.Gnutella Dynamic Query Protocol v0.1[EB/OL].(2003-05-12) [2009-12-23]. http://www9.limewire.com/developer/dynamic_query.html.

[6] JIANG H, JIN S.Exploiting Dynamic Querying Like Flooding Techniques in Unstructured Peer-to-peer Networks[C].USA:IEEE,2005:1121-1123.

[7] SAMEH EL A, LUC ONANA ALIMA, PER BRAND, et al.Efficient Broadcast in Structured P2P Networks[EB/OL].(2009-11-10)[2009-12-23].http://soda.swedish-ict.se/2811/

[8] PAOLO TRUNFIO, DOMENICO TALIA.Implementing Dynamic Querying Search in k-ary DHT-based Overlays[C].[s.l.]:Computer Science, 2008:275-286.

[9] DOMENICO TALIA, PAOLO TRUNFIO.Dynamic Querying in Structured Peer-to-Peer Networks, Submitted for Publication[EB/OL](2008-11-02)[2009-12-23].Available at:http://grid.deis.unical.it/papers/pdf/DQ-DHT.pdf.