對等網(wǎng)二叉模型構(gòu)造及搜索算法研究

摘 要: 針對P2P網(wǎng)絡(luò)中資源查找及其自身存在的問題，本文提出了一種分布式二叉樹索引模型，通過度量網(wǎng)絡(luò)中結(jié)點屬性相似性，對所有結(jié)點進行漸近分組，形成層次性邏輯二叉樹覆蓋網(wǎng)絡(luò)。在信息搜索時，查詢只路由到相關(guān)的結(jié)點上，減少了信息搜索時的平均搜索路徑長度，從而改善搜索效率。

關(guān)鍵詞: P2P網(wǎng)絡(luò) 二叉樹索引模型 搜索算法

1.引言

對等(又稱P2P，Peer to Peer)模型由于其結(jié)構(gòu)靈活和能夠充分利用邊緣資源等特點得到了迅速發(fā)展，其主要應(yīng)用于分布環(huán)境下的資源共享，特別是文件共享，最典型的代表如BT和NaPster[1]。在文件共享類的應(yīng)用中，對P2P拓撲(或稱為P2P模型)和不同拓撲上資源定位算法的研究是較為關(guān)鍵的問題。目前P2P網(wǎng)絡(luò)系統(tǒng)的搜索算法，一種是基于無結(jié)構(gòu)的，一種是基于有結(jié)構(gòu)的。有結(jié)構(gòu)P2P網(wǎng)絡(luò)有時被稱為第二代對等網(wǎng)絡(luò)，因為它有更好的可擴展性，更快的查找速度，控制層面上需要更少的額外開銷，所以近年來逐漸成為人們研究的熱點問題。但在實際網(wǎng)絡(luò)中P2P網(wǎng)絡(luò)強動態(tài)性決定了難以實現(xiàn)對等點之間的互相快速定位，且節(jié)點之間在計算、存儲能力等方面的差異也造成了節(jié)點地位的不平等[2，3]，因此這種按照邏輯網(wǎng)絡(luò)設(shè)計的算法可能會增加網(wǎng)絡(luò)帶寬消耗和請求響應(yīng)時間。

本文改進已有的研究成果，提出了分布式二叉樹索引模型，將搜索限制在與查詢內(nèi)容相關(guān)的局部結(jié)點集中，為有組織的P2P系統(tǒng)提供了一種基于復(fù)雜查詢條件的、能有效搜索數(shù)據(jù)對象的方法。

2.系統(tǒng)模型構(gòu)造

2.1參數(shù)定義

定義1:P是組成對等網(wǎng)絡(luò)的所有計算機的集合，peer∈P，是網(wǎng)絡(luò)中的某臺機器。

定義2:設(shè)P2P網(wǎng)絡(luò)系統(tǒng)中所有結(jié)點集合為P={pi 1≤i≤N}，數(shù)據(jù)對象集合為A={aj 1≤j≤M}，屬性值集合為W={Wk 1≤k≤L}，M為數(shù)據(jù)對象的總數(shù)，L為屬性值的總數(shù)，每個結(jié)點pi的數(shù)據(jù)對象集合記為A(pi)。

2.2二叉樹搜索模型構(gòu)造

在實際應(yīng)用中，每個結(jié)點包含的數(shù)據(jù)對象具有特定的屬性值t。從某個結(jié)點發(fā)出的搜索請求與特定的數(shù)據(jù)屬性相關(guān)，也與發(fā)出請求的結(jié)點相關(guān)。將含有相似度高的屬性值結(jié)點盡可能組織起來將有助于搜索。

信息瓶頸方法提供了一種好的相似性度量[4]。兩個變量x1和x2之間的相似度，可由x1和x2條件下y的分布，即p對結(jié)點pi的數(shù)據(jù)對象集合A(pi)進行聚類，那么每個數(shù)據(jù)對象中屬性值的條件分布為:p(w|a)=，其中n(w|a)為屬性w在數(shù)據(jù)對象a中的出現(xiàn)次數(shù)。數(shù)據(jù)對象中兩個屬性tk和ts之間的相似性度量為:

預(yù)先設(shè)定的相似度閾值為△R，根據(jù)P2P網(wǎng)絡(luò)中的數(shù)據(jù)對象的屬性相似性，將系統(tǒng)中結(jié)點逐步進行層次化的分組歸類。最頂層包含整個系統(tǒng)，接下來的每一層都是對上一層的細化。定義細化后的結(jié)構(gòu)為一棵二叉樹，用T表示一棵二叉樹，Sim(tk，ts)小于△R，加入左子樹，否則加入右子樹。這樣得到一種在概念特征上逐漸具體，用于對結(jié)點屬性值進行漸近分組的層次性二叉樹結(jié)構(gòu)。

網(wǎng)絡(luò)中每個節(jié)點都有一個160bit的ID值作為標識符。節(jié)點ID的生成，各種具體的應(yīng)用軟件有不同的實現(xiàn)方法，一般是選擇一個不重復(fù)的值進行SHA-1計算，這個值可以是用戶的IP地址，或者只是簡單地隨機生成。在網(wǎng)絡(luò)中，所有節(jié)點都被當作二叉樹的一個結(jié)點，并且每一個節(jié)點的位置都由其ID值的最短前綴惟一的確定。如果分別用0和1代表二叉樹的左子樹、右子樹，那么一個結(jié)點標識符的前H位惟一地確定了一條從邏輯樹根結(jié)點到葉子域的路徑。具有相同路徑的結(jié)點組成一個葉子域，彼此之間具有更多的相似屬性。二叉邏輯樹是一種基于節(jié)點屬性的虛擬結(jié)構(gòu)，和混合體系結(jié)構(gòu)的P2P不同，邏輯樹只是通過屬性體現(xiàn)，不需要維護相應(yīng)的連接。

3.搜索算法

3.1基于二叉樹覆蓋網(wǎng)絡(luò)搜索算法

每個結(jié)點根據(jù)其標識屬性與邏輯樹上一個確定的葉子域相對應(yīng)，一條從根結(jié)點到葉子的路徑標志了該葉子域內(nèi)成員的屬性。從虛擬根節(jié)點出發(fā)到該虛擬葉子節(jié)點的邊的序列即為節(jié)點P的路徑，記作path(P)，使用二進制數(shù)標識路徑:節(jié)點P∈Peers，Path(P)=b1，…，bn，bi{0，1}。

如圖1所示，虛線包含的部分就是不同的葉子域，共有四個域，由上到下各層的前綴分別為1，01，000，0010。

假設(shè)P表示邏輯樹T的任意一個結(jié)點，h表示結(jié)點P的深度[5]。共同前綴相同的結(jié)點具有相同的深度，且深度是本結(jié)點在邏輯樹中前綴的字符個數(shù)。如圖1節(jié)點A、B具有共同的前綴100，前綴字符個數(shù)3，即它們的深度為3。

根據(jù)在小世界社會網(wǎng)絡(luò)中成員之間的連接概率p是相對層次距離h的函數(shù)，p=e-αh，其中α=0.92。漸近分組的層次性二叉樹結(jié)構(gòu)，層次越深，結(jié)點連接的可能性越大，相似度越大。

3.2資源查詢策略

若用戶向結(jié)點pi提交查詢信息Q時，設(shè)預(yù)先設(shè)定的相似度閾值為△r，則整個搜索過程如下。

(1)pi檢索本地數(shù)據(jù)對象，若與Q匹配，則向用戶返回結(jié)果，一次查詢結(jié)束。

(2)若本地數(shù)據(jù)中找不不到所查詢的資源，則計算Q與上層父結(jié)點屬性的相似度，然后選擇相似度大于△r的值，向?qū)?yīng)的結(jié)點發(fā)送查詢消息。依次路由，直到在TTL時間內(nèi)找到的所要查詢的信息，并返回給結(jié)點pi。如圖2(1)實線箭頭表示查詢過程，虛線箭頭表示返回查詢結(jié)果過程。

(3)若pi的下層鄰居結(jié)點中包含相似度大于△r的屬性值，則依次路由，直到在TTL時間內(nèi)找到包含有與Q相似度大于△r主題的結(jié)點，返回查詢結(jié)果。如圖2(2)所示，否則返回步驟(2)。

(4)包含Q的結(jié)點向pi返回查詢結(jié)果。查詢結(jié)果是結(jié)點IP地址的集合，這些結(jié)點的屬性和查詢相匹配。

二叉樹覆蓋網(wǎng)資源搜索偽代碼

1)BW_Location (Node n，Request r)

//if n is the request?謖s initiator，Check n?謖s attributeList

2)Forword_Request (n.s， r) // Forword the Request to n?謖s father Peer

3)Match=Check_attrlist (s.w， r)

// if matched， Check_attrlist( ) returns the ID of the destination，else returns NULL

4)If Match

Check_Childlist (n.w，r)// Forward the request to destination

5)Else

6)Forword_Request(Match， r)

//Forward the request to the next hop

4.結(jié)語

本文提出了一種漸近分組的層次性邏輯二叉樹結(jié)構(gòu)，依據(jù)P2P網(wǎng)絡(luò)中結(jié)點屬性相似性，將其組織在一起構(gòu)成邏輯覆蓋網(wǎng)絡(luò)。在信息搜索時，查詢只路由到相關(guān)的結(jié)點上，從而改善了搜索效率。實驗結(jié)果表明，屬性相似邏輯二叉樹網(wǎng)絡(luò)，可以減少信息搜索時的平均搜索路徑長度，提高搜索的成功率。

參考文獻:

[1]FreeNet.http://freenet.sourceforge.net.

[2]Geoffrey F.Peer-to Peer networks[J]Computing in science engineering 2001，6，75- 77.

[3]Watts D J，Dodds PS，Newman ME J.Identity and search in social networks. Science， 2002， 296:1302~1305.

[4]傅向華，馮博琴.主題驅(qū)動的P2P分布式信息搜索機制研究[J]小型微型計算機系統(tǒng)，2006.4.

[5]馮國富，姜玉泉，張金城，顧慶，陳道蓄.一種基于多重覆蓋的結(jié)構(gòu)化P2P搜索[J].計算機科學(xué)，2008.35，(2).