提高Ｐ２Ｐ下ｔｏｐｋ搜索性能的研究
2009-01-01 00:00:00張連寬楊波唐屹
計算機應用研究 2009年1期
(1.華南農業大學 a.數學系；b.信息學院， 廣州 510642； 2.廣州大學 數學系， 廣州 510405）
摘 要：分析了P2P中節點資源分布特點。根據搜索條件，在資源匹配度的基礎上提出了節點匹配度的概念。基于節點匹配度與資源的small world分布特征提出topk資源的搜索、評價算法。該算法使搜索能夠在整個網絡內進行，并朝資源匹配高的范圍傳播。在提高搜索效率、節約網絡帶寬的同時，保證了最終獲取的k個資源是最匹配的。根據搜索條件選擇廣播匹配節點的方法有效地平衡了搜索、評價的帶寬和計算資源。
關鍵詞：對等網絡; topk搜索; small world模型; 節點匹配度
中圖分類號：TP311； TP393 文獻標志碼：A
文章編號：10013695(2009)01026204
Improve topk query in peertopeer system
ZHANG Liankuan1a，YANG Bo1b，TANG Yi2
(1.a.Dept. of Mathematics，b.College of Information， South China Agricultural University， Guangzhou 510642， China；2.Dept. of Mathematics， Guangzhou University， Guangzhou 510405， China）
Abstract:This paper analysed the character of resource distributing in P2P system. According to the query， based on document match degree，proposed the concept of peer match degree， and based on peer match degree and small world character of resource，proposed a new arithmetic to search and rank resource.The arithmetic could search resource in all network， and make searching toward high matching degree field.The arithmetic ensure the resource， which selected at last， is topk resource.According to the query，select peer match degree can balance bandwidth and computing power.
Key words:P2P system; topk query; small world model; peer match degree
P2P（peertopeer）網絡已成為互聯網中資源共享的重要形式。P2P網絡中，由于每個節點單元所共享的資源數量與形式，以及組成P2P網絡的節點規模沒有限制，共享的資源十分豐富。對P2P網絡中的資源搜索并進行topk排序具有重要意義。所謂topk搜索是在資源搜索時，返回k個最匹配的結果，也就是只返回k個用戶最滿意的資源。P2P網絡中的節點可以自由地加入或退出，節點鄰居關系的隨意性，網絡所呈現的無組織、動態變化狀態使得研究具有挑戰性，成果較少。文獻[1]中將查詢廣播給所有鄰居節點，網絡帶寬消耗大，范圍有限。GLOSS[2]和CORI[3]對文檔集進行選擇，選取其中包含相關文檔最多的前k個文檔集發送查詢。但搜索范圍也是局部的，并不能保證獲取的是topk結果。pSearch[4]結合hash表進行P2P索引，但需要一些全局性的統計信息，建立、維護整個網絡的hash表示困難。為了減少帶寬的消耗，并減少查詢信息的碰撞，文獻[5~8]中提出根據節點的運算能力與帶寬設置超點專用于信息的查詢。一個節點要加入系統首先要向超點提出申請。這不是一種純P2P的網絡，在自由的P2P 網絡中，超點的帶寬與計算消耗較大，往往難以實現，僅限于部門內部使用。目前的研究存在著帶寬消耗大、搜索范圍小、搜索效率低下、計算復雜、評價困難等缺陷。為解決這些問題，根據搜索條件提出節點匹配度的概念。根據節點匹配度以及資源分布的small world特征提出了topk搜索、評價算法。提出的算法具有擴大搜索范圍、節約網絡資源、提高搜索效率、平衡節點計算資源等優點。
1 P2P的small world 現象及特征
S. Milgram在20世紀60年代做了一個著名的尋找認識鏈的實驗。實驗的任務是讓堪薩斯州的任意一個人將一個包裹通過彼此相互認識的中間人傳遞給馬薩諸塞州的任意一個人，研究所需要的路徑長度（中間人的個數）。實驗的結果是所需的中間人大約六七人。這就是著名的six degrees of separation[9]法則。Milgram 將這種現象稱為small world 現象。
近年來，人們對各種P2P網絡進行了研究，Freenet系統[10]、Gnutella系統［11］、發送郵件的關系[12]、網頁之間的超鏈接關系[13]、PGP使用關系[14]等均具有上述現象，small world在P2P網絡中普遍存在。
P2P中的small world現象主要表現為三個特征：
a)一個節點的鄰居數相對于整個網絡的節點數是微小的。
b)節點的鄰居不是在整個網絡中平均擴散的。事實上，鄰居關系傾向于共同的地域、背景、興趣等。Milgram將這種特征稱為高聚類性（highly clustered）。
c)任何兩個節點之間均存在一條較短的路徑相連接。
目前人們對small world網絡的結構提出了不同的模型，但一般認為small world網絡是介于結構網絡與隨機網絡之間的一種網絡[15]，如圖1所示。
2 P2P中的topk資源搜索
本文提出的topk搜索環境是在具有small world特征的P2P網絡中進行的。文獻[16]通過模擬傳染病的傳播，證實疾病的傳播更容易、更快速地在整個small world網絡中擴散。意識到這一點，Zhang Hui等人[17]基于small world特征改進了Freenet的搜索方法，但仍然采用貪心算法，效率較低。
進行topk搜索資源的查詢條件，通常是幾個關鍵字、短語、句子等。在具有small world特征的P2P中，資源的搜索條件如下：
a)每個節點知道鄰居的一些情況，如愛好、背景，可能含有的資源，但并不知道整個網絡的規模和鄰居間關系，以及資源的分布等情況；
b)節點并不知道鄰居的鄰居資源情況；
c)網絡中鄰居的關系是動態變化的，節點中資源的分布也是動態變化的。
在文獻[18]中，為了在P2P中獲取某個確定節點的信息，如一個節點的公鑰證書，尋找路徑時采取了查詢鄰居的鄰居方法獲取較快的查找路徑。而在topk搜索中，匹配資源在哪些節點內是不明確的。如何根據查詢條件，獲取最匹配的資源，基于P2P的small world特征能夠快速地在整個網絡內傳播的功能，提出盡可能地在資源匹配高的范圍內搜索滿足條件的資源的算法，再對滿足條件的資源進行排序。方法描述如下：(a)查詢信息的發起者以廣播的形式向其所有鄰居查詢匹配資源。(b)每一個鄰居接到查詢信息后再以廣播的形式向其所有鄰居查詢匹配資源，以這種方式在一個小范圍內進行廣播搜索。(c)廣播結束后，在廣播的搜索路徑內，選擇節點匹配度最高的終節點作為起點，再次廣播查詢。(d)每次廣播結束后，均選擇k個最匹配資源返回給信息查詢的始發者。為了防止信息的重復查詢，在查詢信息發起時，給查詢信息設定一個標記。如果一個節點已接收過查詢標記，當再次接收查詢信息時，將放棄接收。關于節點匹配度以及資源匹配的計算將在本文第3章闡明。
在查詢時設定廣播生存期R和深度搜索生存期TTL，即進行廣播的次數。當TTL結束時，搜索結束，對返回的結果進行topk排序。
基本函數：
Broadcas_query(U，P，Q，T，TTL，ID)
功能：局部范圍內廣播。
參數：U查詢信息的始發者，P目前廣播的始發者，Q查詢條件，T目前廣播的層數，TTL目前深度生存期，ID查詢的標記。
Get_next_broadcas_peer(Tail_PsR，Q)
功能：獲取下次廣播的始發節點。
參數：Q查詢信息。Tail_PsR廣播末節點及其資源集合。
Get_Top_result（All_PsR，Q）
功能：選出k個匹配最高的資源。
參數：Q查詢條件信息，All_PsR節點及其資源集合。
下面用算法描述搜索方法。
假如搜索信息的發起者為節點U，搜索的條件Q。算法主要廣播的嵌套。
算法1 Topk資源搜索算法
P.Broadcas_Query(U，W，Q，T，TTL，ID) /* P執行節點*/
if received ID then quit;
if(TTL==0) thenreturn finished;
if(T==0)then sendPrTo(PsR，W，1);return;
if(0 sendPrTo(PsR，W，0); for each P’s neighbors Pi T=T-1; Pi.Broadcas_Query(U，W，Q，T，TTL，ID); if(T==R) All_PsR=; Tail_PsR=; Top_PsR=; for each P’s neighbors Pi T=T-1; Pi.Broadcas_Query(U，P，Q，T，TTL，ID)； Wait for Broadcas finish Get All_PsR and Tail_ PsR Top_PsR= Get_Top_Result (All_PsR，Q); SendTopResTo(Top_PsR，U); V= Get_Next_Broadcas_Peer(Tail_PsR，Q); T=R; V.Broadcas_Query(U，V，Q，T，TTL，ID)； 算法1首先根據搜索標記判斷是否已經接收到搜索請求，如果接收過，則放棄，然后判斷正處于什么階段。如果TTL為零表示整個搜索生存期結束。若T為零則表示本次廣播生存期結束時期，通過函數sendPrTo(PsR，W，1)將本節點的匹配資源返回本輪廣播的始發者，并通過函數末參數1告知是廣播尾節點。若0 算法2 獲取下次廣播的始發節點算法 Get_Next_Broadcas_Peer(Tail_PsR，Q) for each ofTail_PsR ‘sPeer Pi Pi .Score = get_Peer_Score(Pi. Res，Q); W=maxpi(pi#8226;Score) return W ; 算法2選擇所有尾節點中節點匹配度最大的節點。其中get_Peer_Score(Pi.Res，Q)為獲取節點匹配度，計算方法將在資源的topk排序中闡明。 算法3 獲取topk資源 Get_Top_Result（All_PsR，Q） for each of All_PsR′s Peer Pi for each ofP′isResource Di， j Di， j.Score= Get_Res_Score(Di， j，Q); Top_PsR =Get_MaxK_ Score_Res(D1，1.Score， D1，2.Score，…，Di， j.Score， …) ; return top_PsR; 算法3從資源集從選擇k個最匹配資源。其中Get_Res_Score(Di， j，Q)為資源匹配度，計算方法將在topk排序中闡明。 3 Topk匹配排序計算 在資源的搜索算法中，資源的排序和廣播基點的選擇需要根據資源匹配度與節點匹配度判斷。下面介紹這兩種匹配度的計算方法。 31 資源的匹配度計算 計算單個資源的匹配度采用的是TFIDF方法。TFIDF是一種有效的對集中式資源集進行排序的方法。TFIDF將搜索條件分成幾個關鍵字。計算匹配程度考慮以下因素： a)關鍵字的詞頻越高，越符合搜索要求； b)各關鍵字的權重不同，越專業的關鍵字權重越大。 對單一資源來說，詞頻計算較簡單，統計關鍵字出現的次數除以總字數。專業度的計算是資源總數除以出現關鍵字資源數，再取對數。具體計算關鍵字的權重如下： W(t，d)=log(N/ni+0.01)/t∈d[tf(t，d)×log(N/ni)+0.01]2 其中：W(t，d)為詞t在資源d中的權重，tf(t，d)為詞t在資源d中的詞頻，N為資源集的總數，ni是資源集中出現詞t的資源數，分母為歸一化因子。 假設搜索條件含有n個關鍵字，資源d的匹配度為 sim(Q，d)=ni=1W(ti，d)tf(ti，d) 32 節點的匹配度計算 在深度優先與廣度優先的交互迭代中，每次廣播結束后要選擇下一個廣播的基點，選擇的目的是希望在以后的廣播中找出更多匹配高的資源。主要從以下兩個因素考慮： a)節點含有資源的匹配程度與數量； b)含有鄰居的個數。 選擇的標準是含有高匹配資源數量多、鄰居數多的節點。節點含有較多的高匹配資源，直觀上，這個節點具有與查詢資源相關的背景（工作、愛好等）。根據small world理論的高聚類性，其鄰居很可能也具有這樣的背景，含有較多的高匹配資源。選擇鄰居個數多是希望搜索能夠快速地擴散。 節點的資源匹配度為所有資源匹配值之和： simRs(Q，p)=ni=1sim(Q，dp，i) 節點匹配度： simPeer(Q，p)=simRs(Q，p)×m 其中：m為鄰居數，由于節點關系的高聚類性，其鄰居的資源匹配度與其相近，P節點匹配值乘以m大體能夠放映下次廣播時獲取的匹配資源程度。 4 模擬實驗 下面通過實驗說明傳播方式，用一百個節點作模擬實驗，采用文獻[19]提出了一種small world模型。考慮到節點關系的對稱性、平等性，P2P網絡的結構仍采用環狀結構。兩個節點的背景越相似，其位置就越接近，根據small world特征，它們是鄰居的概率越大。如果節點u、v的距離dis(u，v)，這兩個節點是鄰居的概率是dis(u，v)-r，這里r為一個常數。實驗中取1.75。鄰居間的關系如圖2所示。 文獻[19]證實，生成的鄰居關系圖具有較好的samll world特征：高聚類性、低特征長度、Power分布，較符合P2P下節點間的鄰居關系。 在關系圖中，近距離的節點，鄰居概率大，但也有少量遠距離的鄰居。這種鄰居關系叫做捷徑（shortcuts）。捷徑具有使信息快速在整個網絡內傳播的功能。 在實驗中，廣播的生存期設為2。假定27號節點要進行topk搜索。首先將搜索信息發給其所有的鄰居，如圖3（a）所示。其鄰居收到查詢請求后，將信息發送給所有的鄰居，如圖3(b)所示。27號節點選擇廣播內最匹配的k個資源，第一次廣播結束。根據搜索條件選擇節點匹配度最高的節點，實驗中選擇了76號節點。再以76號節點為基點進行第二次廣播。兩次廣播后搜索的路徑如圖4所示。 實驗中證實，廣播階段是在局部范圍內進行的，但有少量的捷徑將搜索信息傳播到遠距離的鄰居。當較遠距離的鄰居具有較多高匹配節點時，將被選為廣播基點。資源的查詢朝著高匹配資源范圍內傳播。 5 性能與代價分析 Topk資源的搜索是采用廣度與深度結合的算法。廣播的范圍越大，獲取的資源越多，但是網絡的負擔越重。在實現時可根據網絡資源的實際情況設定廣播的生存期。根據small world理論，一個節點的鄰居間是鄰居的概率比較大，在搜索時，一個節點有可能多次收到查詢請求。本文的算法通過檢查搜索標記放棄重復請求，可節約網絡資源，也有利于下次廣播的基點突破小范圍內，使搜索快速在整個網絡內傳播。實驗也證實了這一點。搜索范圍的大小還根據深度優先生存期的設置。深度優先的每個階段的廣播僅限于小范圍內，深度優先的生存期可以設置得較大。 在選擇下次廣播的基點時，選擇節點匹配度高，這樣的節點含有較多的高匹配度資源。根據small world的高聚類性，其鄰居可能也有較多的高匹配資源。采用這樣的搜索算法，能夠在整個網絡內進行，并朝資源匹配高的范圍方向傳播。 在處理信息方面，在每次廣播結束后，廣播中心節點要選擇這個范圍內的topk個資源。處理的資源量與廣播的范圍以及資源量有關。選擇后將最匹配的k個資源返回始發者。若深度優先的生存期為TTL，則始發者將對收到的k×TTL個資源中選擇k個最匹配資源。算法能夠保證最后選擇的k個資源是所有搜索范圍內最匹配的。 在一般的P2P網絡中，固定的超點處理信息負擔沉重。而本文采取的搜索算法廣播基點的選擇是根據搜索的條件作判斷的。不同的節點含有的資源類型不同，只有當查詢和其含有的較多資源類型一致時才會被選擇到擔任廣播基點。搜索的多樣性、資源、網絡的動態性使廣播中心節點的選擇分散化，可以有效地平衡信息處理任務。 6 結束語 根據搜索條件及P2P中資源分配的特點，提出了基于節點匹配度的廣度優先與深度優先結合的資源搜索、評價的方法。新的方法使搜索信息快速在整個網絡內擴散并朝最有可能獲取高匹配資源的范圍進行。根據搜索條件選擇廣播基點有效地平衡了信息處理的負擔。 參考文獻： ［1］ ZHANG W，LI J Z，GAO H，et al.KNN query processing in peertopeer multimedia database[J].Computer Science，2002，29(8):190193. [2]GRAVANO L，GARCIAMOLINA H，TOMASIC A.The effectiveness of GLOSS for the text database discovery problem[C]//Proc of ACM SIGMOD Int’l Conf on Management of Data.New York:ACM Press，1994:126137. [3]CALLAN J P，LU Z H，CROFT W B.Searching distributed collections with inference networks[C]//Proc of the 18th Annual Int’l ACM SIGIR Conf on Research and Development in Information Retrieval Seattle.New York: ACM Press，1995:2128. [4]TANG C Q，YU Z H，MAHALINGAM M.pSearch: Information retrieval in structured overlays[C]//Proc ofACM SIGCOMM Computer Communication Review.New York:[s.n.]，2003:8994. [5]BALKE W T，NEJDL W，SIBERSKI W，et al. Progressive distributed topk retrieval in peertopeer networks[C]//Proc of the 21st International Conference on Data Engineering.Washington DC:IEEE Computer Society，2005:174185. [6]NEJDL W，WOLPERS M，SIBERSKI W，et al.Superpeerbased routing and clustering strategies for RDFbased peertopeer networks[C]//Proc of International World Wide Web Conf.New York: ACM Press ，2003:536543. [7]SCHLOSSER M，SINTEK M，DECKER S，et al.Hyper cuphypercubes，ontologies and efficient search on P2P networks[C]//Proc ofWorkshop on Agents and P2P Computing.Bologna:[s.n.]，2002:133134. [8]YANG B，GARCIAMOLINA H.Designing a superpeer network[C]//Proc of the 19th International Conference on Data Engineering.Bangalore:[s.n.]，2003:4960. [9]MILGRAM S.The small world program[J].Psychology Today，1967，1:6067. [10]ORAM A.Peertopeer:harnessing the power of disruptive technologies[M].Sebastopol:O’Reilly Media，2001. ［11］JOVANOVIC M A.Modeling largescale peertopeer networks and a case study of Gnutella[D].Cincinnati:University of Cincinnati，2000. [12]DODDS P S，MUHAMAD R，WATTS D J.An experimental study of search in global social networks[J].Science，2003，301(5634):827829. [13]ADAMIC L.The small world Web[C]//Proc of the European Conf on Digital Libraries.London:SpringerVerlag，1999:443452. [14]CAPKUN S，BUTTYAN L，HUBAUX J P.Small worlds in security systems:an analysis of the PGP certificate graph[C]//Proc of ACM New Security Paradigms.New York:ACM Press，2002:2835. [15]WATTS.Small worlds[M].Princeton:Princeton University Press，1999. [16]ALBERTLASZLO B.Linked[M]. [S.l.]:Plume，2003. [17]ZHANG Hui，GOEL A，GOVINDAN R.Using the small world modal to improve freenet performance[C]//Proc of International Journal of Computer and Telecommunications Networking.New York: Elsevier NorthHolland，2004:555574. [18]TANG Yi，ZHANG Liankuan.INFO:an improving strategy for searching the small world networks[C]//Proc of IEEE/WIC/ACM International Conference Web.Washington DC:IEEE Computer Society，2005:5457. [19]張連寬，唐屹.基于small world模型的提高網絡安全性的方法研究[J].計算機工程與應用，2005，41（13）:133136.
