P2P文件搜索系統(tǒng)中基于標(biāo)簽的文件搜索方法

王 哲,何宗澤，韓 嘯

(1.吉林省經(jīng)濟(jì)管理干部學(xué)院 發(fā)展規(guī)劃處,長春 130012；2.吉林大學(xué) 儀器科學(xué)與電氣工程學(xué)院，長春 130061；3.吉林大學(xué) 學(xué)報編輯部,長春 130012)

?

研究簡報

P2P文件搜索系統(tǒng)中基于標(biāo)簽的文件搜索方法

王 哲1,何宗澤2，韓 嘯3

(1.吉林省經(jīng)濟(jì)管理干部學(xué)院 發(fā)展規(guī)劃處,長春 130012；2.吉林大學(xué) 儀器科學(xué)與電氣工程學(xué)院，長春 130061；3.吉林大學(xué) 學(xué)報編輯部,長春 130012)

針對點對點(P2P)文件搜索技術(shù)存在網(wǎng)絡(luò)帶寬消耗大和查詢速度慢等問題,為專用的P2P系統(tǒng)設(shè)計一種基于標(biāo)簽的文件搜索方案.該方案給出了將系統(tǒng)底層每個節(jié)點所控制的相關(guān)文件上傳到中間層子服務(wù)器,及將頂層中央服務(wù)器接收到的文件查詢轉(zhuǎn)發(fā)到相關(guān)子服務(wù)器的方法,并運用標(biāo)簽優(yōu)先順序技術(shù)實現(xiàn)了查詢的快速轉(zhuǎn)發(fā).性能評估結(jié)果表明,基于標(biāo)簽的文件搜索方法在轉(zhuǎn)發(fā)查詢過程中,必須檢測的標(biāo)簽個數(shù)由一個很小的常數(shù)界定,從而節(jié)省了系統(tǒng)的網(wǎng)絡(luò)帶寬,提高了文件的搜索速度.

P2P系統(tǒng)；標(biāo)簽；文件搜索

隨著互聯(lián)網(wǎng)應(yīng)用規(guī)模的迅速擴(kuò)大,傳統(tǒng)的客戶機(jī)/服務(wù)器模式(Client/Server,C/S模式)由于存在服務(wù)器端的單點故障、帶寬和性能瓶頸等因素,已滿足不了用戶的需求.為克服C/S模式的缺陷,點對點(Peer-to-Peer,P2P)系統(tǒng)目前已成為計算機(jī)領(lǐng)域的研究熱點之一[1].

P2P充分利用節(jié)點資源,形成一個自組織網(wǎng)絡(luò)[2].每個節(jié)點在網(wǎng)絡(luò)中的地位都對等,既充當(dāng)服務(wù)器為其他節(jié)點提供服務(wù),同時也充當(dāng)客戶機(jī),享用其他節(jié)點提供的服務(wù).在P2P系統(tǒng)中文件搜索任務(wù)是在大規(guī)模、動態(tài)性的P2P網(wǎng)絡(luò)中找到滿足需求的文件,同時僅花費系統(tǒng)可接受的網(wǎng)絡(luò)通訊開銷、單點可接受的計算開銷及用戶可接受的等待時間[3].目前,P2P搜索技術(shù)主要包括如下內(nèi)容：

1)基于中心化拓?fù)涞乃阉?這種搜索方式需要一個中央服務(wù)器存放其他節(jié)點所共享資源的索引,節(jié)點搜索資源時將帶有所搜索資源標(biāo)識的搜索請求發(fā)送到中央服務(wù)器,中央服務(wù)器檢索資源索引,告知資源請求者擁有該資源的節(jié)點標(biāo)識,然后資源請求者再直接訪問資源擁有者的節(jié)點,下載所請求的文件或者使用其資源[4].這種方式的優(yōu)點是搜索全面且速度較快;但中央服務(wù)器的負(fù)載能力制約了節(jié)點的數(shù)量,系統(tǒng)的擴(kuò)展性不夠；一旦中央服務(wù)器崩潰,則整個系統(tǒng)將癱瘓無法運行.

2)基于非結(jié)構(gòu)化拓?fù)涞乃阉?與中心化拓?fù)渌阉鞑煌?這種方式?jīng)]有中央服務(wù)器,用戶的請求以廣播的方式發(fā)給所有節(jié)點,這些節(jié)點若不能滿足請求,則將請求繼續(xù)以廣播的方式發(fā)給與自己相連接的其他節(jié)點,直到請求得到響應(yīng)為止.這種搜索方式的優(yōu)點是簡便易行,且具有較高的魯棒性和可擴(kuò)展性；缺點是網(wǎng)絡(luò)帶寬的消耗巨大.

3)基于結(jié)構(gòu)化拓?fù)涞乃阉?這種方式一般采用支持多關(guān)鍵詞的分布式散列表技術(shù),即一個文件與一個key值相對應(yīng)(一般通過對文件進(jìn)行Hash得到),系統(tǒng)中的每個節(jié)點負(fù)責(zé)保存一定范圍的key值[5].搜索文件時,先用同樣的算法計算出每個key的Hash值,再根據(jù)Hash值找到key對應(yīng)信息的儲存位置,從而快速定位文件的位置.這種搜索方式的優(yōu)點是速度快,但key值出現(xiàn)在文件中的頻率不同,導(dǎo)致節(jié)點存儲信息的不對稱.

1 P2P系統(tǒng)模型

本文針對一個專用的P2P文件搜索系統(tǒng),實現(xiàn)分布式環(huán)境下一種有效的文件搜索設(shè)計方案.該系統(tǒng)采用3層架構(gòu),即由頂層、中間層和底層組成.其中,底層由大量的用戶節(jié)點組成,這些用戶節(jié)點根據(jù)所包含的用戶興趣相似性或地理位置的接近性分成若干個組,每組都對應(yīng)于中間層的一個子服務(wù)器,組內(nèi)的用戶節(jié)點通過一個邏輯鏈路被連接到相對應(yīng)組的子服務(wù)器上；中間層由若干子服務(wù)器組成,即S={S1,S2,…,Sm},主要負(fù)責(zé)處理某組內(nèi)用戶節(jié)點所提交的文件查詢消息,并通過反復(fù)收集用戶節(jié)點所包含的“新”索引信息保持與用戶節(jié)點的集成性；頂層采用一個中央服務(wù)器,主要負(fù)責(zé)文件查詢服務(wù),維護(hù)用戶節(jié)點與子服務(wù)器的對應(yīng)性.

2 基于標(biāo)簽的文件篩選技術(shù)

在P2P文件搜索系統(tǒng)中,中央服務(wù)器包含一組標(biāo)簽,它們被附加到用戶節(jié)點包含的每個文件及子服務(wù)器包含的索引上.令T={t1,t2,…,tn}表示所有標(biāo)簽的集合,則T中每個標(biāo)簽代表實際應(yīng)用中一個對象的關(guān)鍵詞或關(guān)鍵短語.例如,標(biāo)簽“中國”可表示幾個不同的含義,它代表國家的名字或一種文化等.在設(shè)計方案中,文件上附帶的標(biāo)簽集合依據(jù)標(biāo)簽的普及性確定,假設(shè)集合T已由幾個專家和管理者預(yù)先指定.根據(jù)Zipf第一定律,在自然語言的語素庫中,每個單詞出現(xiàn)的頻率與其在頻率表中的排序成反比[6].為了高效地篩選出與標(biāo)簽相關(guān)聯(lián)的文件,應(yīng)避免選擇高頻詞作為T的成員,即T中應(yīng)包含出現(xiàn)頻率較低并具有代表性的標(biāo)簽.

2.1 標(biāo)簽優(yōu)先順序 令σ是從T到{1,2,…,|T|}的一個雙射(|T|表示集合T的基數(shù)),則σ(t)稱為標(biāo)簽t的優(yōu)先級.如果σ(t1)<σ(t2),則在σ下標(biāo)簽t1比標(biāo)簽t2的優(yōu)先級高.由σ定義一個標(biāo)簽序列,稱為標(biāo)簽的一個優(yōu)先順序：σ-1(1),σ-1(2),…,σ-1(|T|),其中σ-1表示函數(shù)σ的逆函數(shù).

2.2 標(biāo)簽集包含關(guān)系 令T1,T2?T是標(biāo)簽集的兩個子集.在σ下,若T2的優(yōu)先順序是T1優(yōu)先順序的一個前綴,則T2包含T1,記為T1?σT2.例如,T={t1,t2,…,t9},且σ(ti)<σ(ti+1),其中1≤i≤8.在σ下,假設(shè)T1={t1,t2,t3},T2={t1,t2},因為T2的優(yōu)先順序t1,t2是T1優(yōu)先順序t1,t2,t3的前綴,則T2包含T1；假設(shè)T3={t2,t3,t4},因為T2的優(yōu)先順序t1,t2是T3優(yōu)先順序t2,t3,t4的前綴,則T2包含T3.若T1σT2,且T2σT1,則T1和T2在σ下沒有可比性.判斷T1,T2包含關(guān)系的函數(shù)Inclusion(T1,T2)描述如下：

1)如果|T1|<|T2|,則函數(shù)返回false并終止;

2)如果T2=?,則函數(shù)返回到true并終止;

3)令t1為T1中優(yōu)先級最高的標(biāo)簽,并且t2為T2中優(yōu)先級最高的標(biāo)簽,令T1∶=T1{t1}且T2∶=T2{t2};

4)如果t1≠t2,則函數(shù)返回到false并終止;否則,執(zhí)行2).

3 文件上傳算法

底層用戶節(jié)點所包含的每個文件都已被用戶添加了標(biāo)簽,每個子服務(wù)器都與標(biāo)簽的一個子集對應(yīng).本文通過標(biāo)簽集合包含關(guān)系將文件和子服務(wù)器相關(guān)聯(lián),當(dāng)文件被重新創(chuàng)建或文件的內(nèi)容被用戶節(jié)點修改時,則將用戶節(jié)點所包含的索引上傳到子服務(wù)器的算法步驟如下：

3)連接子服務(wù)器Si并上傳文件索引給Si.

文件上傳算法由中央服務(wù)器處理,將給定的文件索引傳遞給它的子服務(wù)器,而標(biāo)簽和子服務(wù)器之間的相關(guān)性通過中央服務(wù)器的一個列表進(jìn)行維護(hù).因此,如果一個子服務(wù)器Si在步驟2)中得到確認(rèn),則用戶節(jié)點可立即獲得在Si中的信息,包括它的IP地址和端口號.為降低每個子服務(wù)器的負(fù)載,每個子服務(wù)器只存儲文件的索引,而文件的實際內(nèi)容存儲在各個用戶節(jié)點中；同時,每個用戶節(jié)點都保持所含文件的子服務(wù)器信息,這樣可保證文件索引一旦被用戶節(jié)點修改,就能馬上更新.

4 查詢轉(zhuǎn)發(fā)算法

在專用P2P系統(tǒng)中,頂層的中央服務(wù)器負(fù)責(zé)完成將接收到的相關(guān)文件查詢轉(zhuǎn)發(fā)到一個子服務(wù)器.因此,高效的查詢轉(zhuǎn)發(fā)算法是文件搜索過程的核心技術(shù).令NR為一個系統(tǒng)變量,表示到目前為止所發(fā)現(xiàn)的文件總數(shù),當(dāng)每次發(fā)現(xiàn)一個新文件時,令NR=NR+1,當(dāng)NR達(dá)到預(yù)定值時,搜索過程停止.中央服務(wù)器的查詢轉(zhuǎn)發(fā)算法步驟如下：

3)C連接到子服務(wù)器Si并將q轉(zhuǎn)發(fā)給Si;

4)子服務(wù)器Si接收到查詢q后,進(jìn)行類似于傳統(tǒng)搜索引擎的文件搜索,并把搜索結(jié)果返回給發(fā)出請求的用戶節(jié)點,匹配結(jié)果數(shù)目提交給中央服務(wù)器C;

5 方案性能評估

在設(shè)計方案中,文件搜索效率的高低取決于相關(guān)文件查詢轉(zhuǎn)發(fā)到一個子服務(wù)器的時間長短和速度快慢,本文通過檢測標(biāo)簽的數(shù)目對設(shè)計方案的性能進(jìn)行評估.

5.1 判別樹 令T={t1,t2,…,tn}是一個標(biāo)簽集,σ是定義在集合T上的標(biāo)簽序列.設(shè)計方案中,中間層的每個子服務(wù)器都與T的子集T′相對應(yīng),且存在一個子服務(wù)器,它與序列σ下包含T′的標(biāo)簽集相關(guān).該模式可由如下樹型結(jié)構(gòu)表示：

1)樹的每個節(jié)點與一個標(biāo)簽集相關(guān)聯(lián),令T(u)表示與節(jié)點u相關(guān)聯(lián)的標(biāo)簽集;

2)樹的根節(jié)點與一個空的標(biāo)簽集相關(guān)聯(lián);

3)令t′是T(u)中最低優(yōu)先級的標(biāo)簽,且i′=σ-1(t′),則節(jié)點u沒有子節(jié)點或有n-i′個與標(biāo)簽集T(u)∪{σ(j)}相關(guān)的子節(jié)點,其中i′+1≤j≤n;

4)每個葉子節(jié)點對應(yīng)于一個與子服務(wù)器相關(guān)的標(biāo)簽集,若葉子節(jié)點在其父節(jié)點最左邊,則由子服務(wù)器充當(dāng)其父節(jié)點.

在標(biāo)簽集滿足上述樹型結(jié)構(gòu)的條件下,從客戶端收到的查詢是從根節(jié)點出發(fā)向葉子節(jié)點(包含該查詢的標(biāo)簽集)的搜索過程.因此,中央服務(wù)器識別一個與給定查詢相關(guān)的子服務(wù)器所需的時間與查詢相關(guān)的葉子節(jié)點的深度成比例,即通過計算判別樹的最大深度可評估本文方案的性能.

5.2 評估實例 設(shè)N表示系統(tǒng)中用戶節(jié)點所含文件的總數(shù),pi表示標(biāo)簽ti附加到文件的概率(在Zipf第一定律下,標(biāo)簽ti被附加到文件的概率與(1/i)ε成正比,其中參數(shù)ε稱為Zipf參數(shù)).假設(shè)不同標(biāo)簽間相互獨立,且樹型結(jié)構(gòu)中與節(jié)點相關(guān)聯(lián)的文件數(shù)不超過α×N個,其中α是常數(shù).

例1將一個用戶感興趣的文件賦予較高優(yōu)先級,得到一個優(yōu)先序列σ(ti)<σ(tj)且pi>pj,則每個節(jié)點的孩子節(jié)點(具有最高優(yōu)先級的孩子節(jié)點)與其父節(jié)點的最大(子)集群相關(guān)聯(lián)(稱這種優(yōu)先級最高的孩子節(jié)點為“最左”節(jié)點).因此,判別樹中每層最左節(jié)點將與該層中最大的集群相關(guān)聯(lián),其中從根節(jié)點到該節(jié)點的距離為節(jié)點所在層數(shù).

假設(shè)pi的優(yōu)先序列符合Zipf第一定律,其中:參數(shù)N=10 000;T=100;α∈[0.01,0.1];Zipf參數(shù)ε∈[0.05,0.15].例1和例2的計算結(jié)果分別如圖1(A)和(B)所示.由圖1可見,例2判別樹的最大深度比例1判別樹的最大深度小得多.

圖1 數(shù)值計算結(jié)果Fig.1 Results of numerical evaluation

[1] 翟曉萍,張順頤,李君.一種分層的P2P網(wǎng)絡(luò)模型 [J].電信快訊,2008(10):27-30.(ZHAI Xiaoping,ZHANG Shunyi,LI Jun.Hierarchical P2P Network Model [J].Telecommunications Information,2008(10):27-30.)

[2] 趙麗敏.基于Chord查找算法的P2P系統(tǒng)研究 [D].北京:北京大學(xué),2014.(ZHAO Limin.Research on P2P System Based on Chord Lookup Method [D].Beijing:Peking University,2014.)

[3] 劉維光,陳立偉.一種基于DHT的P2P搜索方法 [J].微計算機(jī)信息,2006,22(3):131-133.(LIU Weiguang,CHEN Liwei.Research of P2P Searching Technology Based on DHT [J].Microcomputer Information,2006,22(3):131-133.)

[4] 裴云霞,張岳.淺談P2P搜索技術(shù) [J].科技信息,2007(30):50.(PEI Yunxia,ZHANG Yue.Analysis of P2P Search Technology [J].Science &Technology Information,2007(30):50.)

[5] 李運娣,馮勇.基于DHT的P2P搜索定位技術(shù)研究 [J].計算機(jī)應(yīng)用研究,2006(10):226-228.(LI Yundi,FENG Yong.Study of Data Search in DHT P2P Networks [J].Application Research of Computers,2006(10):226-228.)

[6] Newman M E J.Power Laws,Pareto Distributions and Zipf’s Law [J].Contemporary Physics,2005,46(5):323-351.

(責(zé)任編輯：韓 嘯)

FileSearchingBasedonTaginaP2PFileSearchSystem

WANG Zhe1,HE Zongze2,HAN Xiao3

(1.DepartmentofDevelopmentPlanning,JilinProvinceEconomicManagementCadreCollege,Changchun130012,China;2.CollegeofInstrumentation&ElectricalEngineering,JilinUniversity,Changchun130061,China;3.EditorialDepartmentofJournalofJilinUniversity,Changchun130012,China)

A tag-based file search method was designd for point to point (P2P)system to solve the large consumption of network bandwidth and slow query problem,which determines a way of uploading associated files held by each peer in the bottom layer to subservers in the middle layer and a way of forwarding a query received by the central server in the top layer to an appropriate subserver relevant to the query.A technique of priority sequence of tags was introduced to realize a quick forwarding of queries.The result of performance evaluation indicates that the number of tags which must be examined in forwarding a given query is bounded by a small constant,so as to save network bandwidth and raise the speed of file searching.

P2P system;tag;file search

10.13413/j.cnki.jdxblxb.2015.03.35

2014-10-13.

王 哲(1981—),男,漢族,碩士,講師,從事計算機(jī)網(wǎng)絡(luò)技術(shù)的研究,E-mail:20862282@qq.com.通信作者：韓 嘯(1981—),男，漢族，博士研究生，編輯，從事計算機(jī)網(wǎng)絡(luò)技術(shù)的研究,E-mail:hanxiao@jlu.edu.cn.

國家自然科學(xué)基金青年基金(批準(zhǔn)號：61300147).

TP316.4

：A

：1671-5489(2015)03-0538-04