王 哲,何宗澤，韓 嘯

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

?

研究簡報

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

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

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

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

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

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

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

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

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

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

1 P2P系統(tǒng)模型

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

2 基于標簽的文件篩選技術

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

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

2.2 標簽集包含關系 令T1,T2?T是標簽集的兩個子集.在σ下,若T2的優(yōu)先順序是T1優(yōu)先順序的一個前綴,則T2包含T1,記為T1?σT2.例如,T={t1,t2,…,t9},且σ(ti)<σ(ti+1),其中1≤i≤8.在σ下,假設T1={t1,t2,t3},T2={t1,t2},因為T2的優(yōu)先順序t1,t2是T1優(yōu)先順序t1,t2,t3的前綴,則T2包含T1；假設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包含關系的函數(shù)Inclusion(T1,T2)描述如下：

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

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

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

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

3 文件上傳算法

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

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

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

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

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

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

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

5 方案性能評估

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

5.1 判別樹 令T={t1,t2,…,tn}是一個標簽集,σ是定義在集合T上的標簽序列.設計方案中,中間層的每個子服務器都與T的子集T′相對應,且存在一個子服務器,它與序列σ下包含T′的標簽集相關.該模式可由如下樹型結構表示：

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

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

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

4)每個葉子節(jié)點對應于一個與子服務器相關的標簽集,若葉子節(jié)點在其父節(jié)點最左邊,則由子服務器充當其父節(jié)點.

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

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

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

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

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

[1] 翟曉萍,張順頤,李君.一種分層的P2P網(wǎng)絡模型 [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].北京:北京大學,2014.(ZHAO Limin.Research on P2P System Based on Chord Lookup Method [D].Beijing:Peking University,2014.)

[3] 劉維光,陳立偉.一種基于DHT的P2P搜索方法 [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搜索技術 [J].科技信息,2007(30):50.(PEI Yunxia,ZHANG Yue.Analysis of P2P Search Technology [J].Science &Technology Information,2007(30):50.)

[5] 李運娣,馮勇.基于DHT的P2P搜索定位技術研究 [J].計算機應用研究,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.

(責任編輯：韓 嘯)

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—),男,漢族,碩士,講師,從事計算機網(wǎng)絡技術的研究,E-mail:20862282@qq.com.通信作者：韓 嘯(1981—),男，漢族，博士研究生，編輯，從事計算機網(wǎng)絡技術的研究,E-mail:hanxiao@jlu.edu.cn.

國家自然科學基金青年基金(批準號：61300147).

TP316.4

：A

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