孫娟娟，禹繼國

（曲阜師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，山東 日照 276826）

0 引言

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

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

1 相關(guān)工作

動(dòng)態(tài)查詢是無結(jié)構(gòu)P2P網(wǎng)絡(luò)中采用的查詢技術(shù)，該方法使用較少的節(jié)點(diǎn)就能夠到達(dá)目標(biāo)節(jié)點(diǎn)。查詢發(fā)起者在一個(gè)小的TTL值內(nèi)通過“刺探”過程將查詢信息發(fā)送給網(wǎng)絡(luò)中的一些節(jié)點(diǎn)并由此開始查詢過程?！按烫健辈樵兊哪繕?biāo)是對(duì)定位到的資源評(píng)估其受歡迎程度[2]。

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

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

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

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

2.1 ML-Chord的結(jié)構(gòu)

圖1 ML-Chord的結(jié)構(gòu)示意

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

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

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

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

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

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

表1 參數(shù)定義

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

3 性能分析

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

4 結(jié)語

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

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