嚴(yán) 華 云

(湖州師范學(xué)院　信息工程學(xué)院, 浙江　湖州　313000)

?

基于語義網(wǎng)絡(luò)的分層DHT*

嚴(yán) 華 云

(湖州師范學(xué)院信息工程學(xué)院, 浙江湖州313000)

針對Chord結(jié)構(gòu)并未考慮用戶查詢偏好的問題，提出了一種基于語義網(wǎng)絡(luò)的分層DHT以解決該問題。在該分層DHT中，節(jié)點和關(guān)鍵詞按語義關(guān)系組織，節(jié)點選擇自己感興趣的區(qū)域加入，每個區(qū)域選一個穩(wěn)定節(jié)點作為超級節(jié)點，節(jié)點間按語義關(guān)系組織，各個區(qū)域按2-Chord結(jié)構(gòu)組織。在此基礎(chǔ)上提出了相應(yīng)的路由算法，該算法先檢查關(guān)鍵詞是否歸本地區(qū)域管理，否則轉(zhuǎn)發(fā)給上層超級節(jié)點去處理，如此遞歸轉(zhuǎn)發(fā)查詢直至返回查詢結(jié)果。實驗發(fā)現(xiàn)，用戶的查詢關(guān)鍵詞較偏好本地區(qū)域時，分層DHT較2-Chord的路由效率得到了一定提升，這種效果隨著偏好度的增大越發(fā)明顯。

語義網(wǎng)絡(luò)；分層DHT；對等網(wǎng)；Chord

分布式哈希表作為一種結(jié)構(gòu)化對等網(wǎng)，在諸多領(lǐng)域有廣泛的應(yīng)用，如文件共享、分布式計算、數(shù)據(jù)發(fā)布等。Chord[1](P149-160)是DHT的一種典型代表。DHT中Chord是一種高效且易實現(xiàn)的結(jié)構(gòu)化對等網(wǎng)。針對Chord結(jié)構(gòu)，研究者提出了多種改進(jìn)以提高路由效率：

一種是單層Chord變體結(jié)構(gòu)：如F-Chord[2]〗(P89-98)采用斐波那契序列作為finger序列的跨距；2-Chord[3](P72-79)是一種對稱雙向Chord，它維持Chord 的finger表的奇數(shù)項，將偶數(shù)項對折到反方向上，這樣路由表大小雖然不變，但提高了路由效率；Base-k Chord[4](P643-657)的finger表采用k基序列，通過增加finger表長度來提高路由效率；本文作者結(jié)合Base-k Chord和2-Chord提出了雙向Base-k Chord[5](P371-375，該結(jié)構(gòu)有意思的是當(dāng)基數(shù)K為奇數(shù)時其路由效率沒有改變，而基數(shù)K為偶數(shù)時能有效提高路由效率；作者還針對雙向Chord雖然可以雙向查找，但其正反兩個方向的finger跨距相等，在雙向查詢中潛在重合可能較多，從而提出了非對稱雙向Base-k Chord[6](P71-79以提高路由效率。

另一種是分層Chord變體結(jié)構(gòu)：在對等網(wǎng)絡(luò)中，隨著規(guī)模的增長,弱節(jié)點(指計算能力差, 或動態(tài)變化劇烈的節(jié)點)嚴(yán)重地制約了DHT網(wǎng)絡(luò)的性能。為了克服該問題, 研究者提出一些層次DHT網(wǎng)絡(luò), 在這種結(jié)構(gòu)中選擇穩(wěn)定的高性能節(jié)點作為超級節(jié)點, 在超級節(jié)點之間構(gòu)建的上層DHT網(wǎng)絡(luò)，其維護(hù)代價和查找跳數(shù)相對于單層的DHT網(wǎng)絡(luò)更小, 且能有效應(yīng)對DHT網(wǎng)絡(luò)中的churn問題(指節(jié)點頻繁地加入或離開對P2P 網(wǎng)絡(luò)性能造成的嚴(yán)重影響)。文獻(xiàn)[7]是一種分層DHT變體典型結(jié)構(gòu)。

總之，現(xiàn)有各種Chord有如下不足：單層Chord變體(包括Chord、F-Chord、Base-k Chord等)中由于存在弱節(jié)點，嚴(yán)重弱化了DHT網(wǎng)絡(luò)的性能，如網(wǎng)絡(luò)的穩(wěn)定性；分層Chord變體選擇穩(wěn)定的高性能節(jié)點作為超級節(jié)點, 在超級節(jié)點之間構(gòu)建成上層DHT網(wǎng)絡(luò)，這雖然解決了穩(wěn)定問題，但并沒有考慮各節(jié)點的瀏覽偏好，即節(jié)點并非均勻瀏覽各種資源。

針對現(xiàn)有各種Chord存在的不足，本文主要做了如下工作：提出了一種基于2-Chord的分層語義DHT結(jié)構(gòu)，以彌補現(xiàn)有分層DHT沒有考慮節(jié)點的瀏覽偏好問題；通過實驗，將本文方法與2-Chord進(jìn)行性能比較。實驗結(jié)果表明：與現(xiàn)有方法相比，本文提出的分層語義DHT結(jié)構(gòu)的路由效率得到了提升，隨著用戶查詢本地關(guān)鍵詞比率的變大，這種效果更明顯。

一、相關(guān)工作

本文提出的分層語義DHT基于2-Chord[3](P72-79，因此下面先介紹2-Chord。

2-Chord結(jié)構(gòu)是在Chord的基礎(chǔ)上進(jìn)行的改進(jìn)，它將Chord的finger表改為了對稱的雙向finger表，即保留標(biāo)準(zhǔn)Chord finger表的奇數(shù)項，刪除偶數(shù)項，并將奇數(shù)項對折到反方向上。

設(shè)J(i)表示N個節(jié)點的環(huán)中finger表在正、反方向上的第i+1個指針的跨距。

對于front方向和back方向上的finger序列的跨距都為：

J(i)=22i，其中i=0,1,… , [log2N/2] 。

圖1　2-Chord 結(jié)構(gòu)及節(jié)點1的finger表及查詢

圖1是一個節(jié)點空間為64(即N=64)的2-Chord環(huán)。從該圖可以看出其finger序列在兩個方向上是對稱的，其finger表大小和標(biāo)準(zhǔn)Chord的相等，但2-Chord可以雙向查詢，即查詢時在當(dāng)前節(jié)點的2個finger表中選擇離目標(biāo)節(jié)點離距離最近的節(jié)點進(jìn)行路由。文獻(xiàn)[3]中理論分析得出2-Chord相對于標(biāo)準(zhǔn)的Chord提高了路由效率，文獻(xiàn)[6]中用實驗得出了相同的結(jié)果。

二、基于語義的分層DHT

由于用戶在DHT中查詢時，查詢關(guān)鍵詞并非均勻分布，每個用戶查詢時有其偏好。本文引入了語義網(wǎng)絡(luò)(Semantic Networks)，將語義相近的關(guān)鍵詞組織到一起，以使用戶查詢關(guān)鍵詞時效率更高。語義網(wǎng)絡(luò)常常被用作知識表示的一種形式，它是一個有向圖，這個圖的頂點(節(jié)點)代表概念，而邊則用于表示這些概念之間的語義關(guān)系[8](P187-195)。圖2是語義網(wǎng)絡(luò)的一個例子，其中下層節(jié)點和其相連的上層節(jié)點間的關(guān)系是泛化聯(lián)系 (用于表示一種類節(jié)點與更抽象的類節(jié)點之間的聯(lián)系，簡稱AKO)。在語義網(wǎng)絡(luò)中節(jié)點間的關(guān)系還有實體聯(lián)系(用于表示類節(jié)點與所屬實例節(jié)點之間的聯(lián)系，簡稱ISA)，聚集聯(lián)系(用于表示某一個個體與其組成成分之間的聯(lián)系)和屬性聯(lián)系(用于表示個體、屬性及其取值之間的聯(lián)系)。

圖2　語義網(wǎng)絡(luò)的一個例子

(一)基于語義的分層DHT結(jié)構(gòu)

本文提出了一種基于語義網(wǎng)絡(luò)的分層DHT結(jié)構(gòu)，其結(jié)構(gòu)如圖3所示：

圖3　基于語義網(wǎng)絡(luò)的分層DHT (其中每一個子區(qū)域Ai以2-Chord結(jié)構(gòu)組織)

圖3中節(jié)點分為兩類：一類是一般節(jié)點，如N1,N8，N14，N32等；另一類是超級節(jié)點，如SL11，SL12，SL13等。在該結(jié)構(gòu)中，將有共同查詢偏好的節(jié)點組織到同一個語義區(qū)域，即節(jié)點加入時根據(jù)自己的偏好選擇相應(yīng)的語義區(qū)域AL0i加入，在每一個語義區(qū)域中選穩(wěn)定和計算能力強的節(jié)點擔(dān)任超級節(jié)點SL1j；類似的，如果需要將這些超級節(jié)點按語義進(jìn)行分區(qū)組織，并在該區(qū)中選擇穩(wěn)定和計算能力強的節(jié)點成為更上層的超級節(jié)點SL2j；如此類推，可以形成更上層的超級節(jié)點SL3j，SL4j,…。在該結(jié)構(gòu)中，各語義區(qū)域A采用2-Chord結(jié)構(gòu)組織，最上層超級節(jié)點S間也采用2-Chord結(jié)構(gòu)加以組織。假設(shè)該分層DHT中共有K層，則各層按從上到下的層數(shù)分別記為：LK-1,LK-2,…,L1,L0，在語義網(wǎng)絡(luò)中各層的語義詞記為S.Li，節(jié)點加入其中后其標(biāo)識ID為：Hash(S.LK1)|| Hash(S.LK-2)||…|| Hash(S.L1)|| Hash(S.L0),對于其中的Hash(S.Li)，當(dāng)i≥1時Hash(S.Li)表示對i層的語義詞S.Li進(jìn)行散列后的值，當(dāng)i=0時S.L0用節(jié)點的MAC來表示，Hash(S.L0)表示計算節(jié)點的MAC值散列后的值。

(二)Finger表結(jié)構(gòu)

在本文提出的基于語義的分層DHT中，節(jié)點的finger表由兩部分組成：一是其所在層的基于2-Chord結(jié)構(gòu)的雙向finger表，另一個就是指向其超級節(jié)點的finger；對于某超級節(jié)點是由其下層節(jié)點選出來的，則該超級節(jié)點還包含其下層的雙向finger表。

對于一個處于Li層的某(超級)節(jié)點，其由于該節(jié)點的標(biāo)識為：Hash(S.LK-1)|| Hash(S.LK-2)||…|| Hash(S.L1)|| Hash(S.L0)，則取其Li層的散列值(Hash(S.Li))進(jìn)行組織該層的finger表 。

設(shè)某語義層Li中有N個節(jié)點，將這N個節(jié)點組成一個2-Chord環(huán)，設(shè)J(j)表示節(jié)點的finger表在正、反方向上的第j+1個finger項的跨距。

對于front方向和back方向上的finger序列的跨距都為：

J(j)=22j其中i=0,1,… , [log2N/2] 。

因此對于某節(jié)點m，其finger表為：

m.Hash(S.Li)±J(j)=m.Hash(S.Li)±22j

其中j=0,1,… ,[log2N/2] ,m.Hash(S.Li)表示節(jié)點m的標(biāo)識ID的第Li層的散列值 Hash(S.Li)。

(三)路由

分層DHT的路由查詢算法如算法1所示。

算法1n.search(key)(分層DHT的路由算法)

(1)根據(jù)查詢詞及其所屬語義網(wǎng)絡(luò)計算散列值：

key.Hash(S.LK-1)|| Hash(S.LK-2)||…|| Hash(S.L1)|| Hash(key) ；

(2)獲取節(jié)點n的散列值：

n.Hash(S.LK-1)|| Hash(S.LK-2)||…|| Hash(S.L1)|| Hash(MAC)；

(3)i=1；

(4)如果n.Hash (Li)!=key.Hash(Li)；

(5) returnS.Li.search(key) ；//S.Li表示從節(jié)點n上溯到Li層的超級節(jié)點；

(6)i=i+1， 轉(zhuǎn)4；

(7)否則，在Li-1層按2-Chord算法路由, returnS.Li.search(key) ；

//S.Li是節(jié)點n上溯到Li-1層的超級節(jié)點 。

路由查詢時，先看查詢詞是否在本地區(qū)域，如不在，則將查詢發(fā)送到其超級節(jié)點；當(dāng)該超級節(jié)點接收到該請求后，看查詢詞是否為其所在區(qū)域的某一個超級節(jié)點所管轄，如該查詢不在該超級節(jié)點區(qū)域管轄范圍內(nèi)，則繼續(xù)向上層的超級節(jié)點轉(zhuǎn)發(fā)該查詢請求，直到找到某一層的某超級節(jié)點管轄該查詢，則由該超級節(jié)點將該查詢請求轉(zhuǎn)發(fā)到其所轄的管理該關(guān)鍵詞的節(jié)點上，如此這般，就能得到路由查詢結(jié)果。

三、實驗?zāi)M

實驗中采用的模擬器為PeerSim,本節(jié)的仿真以2-Chord為基準(zhǔn)，不失一般性。實驗中假設(shè)分層DHT的層數(shù)為2層，并假設(shè)分層DHT的語義區(qū)域數(shù)為10。下面對分層DHT與2-Chord進(jìn)行了全面的比較。

圖4　平均路由跳數(shù)與節(jié)點數(shù)的關(guān)系

本節(jié)將分層DHT和2-Chord進(jìn)行了實驗比較，實驗中每個節(jié)點管理100個關(guān)鍵詞，即使關(guān)鍵詞均勻分布在各個節(jié)點上，實驗結(jié)果如圖4所示。圖4中，2Chord表示的是在2-Chord結(jié)構(gòu)中的實驗結(jié)果，HDHT表示的是本文提出的方法的結(jié)果。具體的，HDHT1表示的是查詢關(guān)鍵詞有10 %在其所處的子區(qū)域的情況，HDHT2表示的是查詢關(guān)鍵詞有20 %在其所處的子區(qū)域的情況，其它情況依此類推。從圖中實驗結(jié)果可知：

HDHT1大部分的平均路由跳數(shù)都比2-Chord的大，即其路由效率不如2-Chord高。這是因為HDHT1的查詢關(guān)鍵詞處于本地子區(qū)域的比例和均勻分布查詢時的相等，而查詢非本地子區(qū)域時需要經(jīng)過上層超級節(jié)點的中轉(zhuǎn)，因此其路由效率更低些。

HDHT2、HDHT3和HDHT4的平均路由跳數(shù)都比2-Chord的小，即其路由效率比2-Chord高；并且隨著本地查詢比例的增加其路由效率變得更高。這是因為HDHT2、HDHT3和HDHT4的查詢關(guān)鍵詞處于本地子區(qū)域的比例比均勻分布查詢時的大，而在本地區(qū)域查詢其路由范圍變小，因此其路由效率更高些。并且隨著本地查詢的比例增加，其所需平均路由跳數(shù)變小，從而進(jìn)一步提高了其路由效率；極限情況是所有查詢都在本地區(qū)域進(jìn)行，這樣所有查詢都不需要經(jīng)過其上層超級節(jié)點的中轉(zhuǎn)，從而每一個查詢時的節(jié)點范圍由2-Chord的所有節(jié)點變?yōu)榱薍DHT的部分節(jié)點，這樣必然會大幅提高路由效率。

假設(shè)本模型中網(wǎng)絡(luò)的節(jié)點數(shù)為 N，并且模型中分成了 M 個語義區(qū)域，因此每個語義區(qū)域平均有 N/M 個節(jié)點。同時假設(shè)查詢時本地查詢的比率為R(即偏好度)。根據(jù)文獻(xiàn)[3]的推導(dǎo)和文獻(xiàn)[6]的實驗，在2-Chord中路由平均跳數(shù)大約為 log2N/2。本文模型中的本地路由平均跳數(shù)為：log2N/M/2 ，在L1層路由需要的跳數(shù)為 ,于是可得到本文模型在實驗中的路由平均跳數(shù)(APL)為：

Rlog2N/M/2+(1-R)(log2M/2+log2N/M/2)=log2N/M/2+(1-R)log2M/2

上式中等號左邊的第一項表示在本地路由情況,第二項表示查詢不在本地路由的情況，在表達(dá)式中可以看出其APL隨著R的增大而變小，即隨著查詢更偏好本地而使APL值更小，這意味著提高了路由效率。對于多層的情況有類似的推導(dǎo)。極端情況是R=1時,查詢只需要在本地區(qū)域進(jìn)行路由，這樣縮小了查詢范圍，顯然APL會減少。

四、結(jié)　論

本文在2-Chord的基礎(chǔ)上，考慮到用戶對查詢的偏好問題，提出了一種基于語義的DHT結(jié)構(gòu)(HDHT)，其中每個子區(qū)域(按語義關(guān)系分區(qū))按2-Chord的方式組織，每個區(qū)域有一個節(jié)點被選為超級節(jié)點，超級節(jié)點間也可按語義關(guān)系組織成區(qū)域并按2-Chord結(jié)構(gòu)方式組織。從實驗結(jié)果可知，HDHT的平均路由跳數(shù)得到了較大的降低；特別隨著用戶查詢的偏好更關(guān)注于其所在的本地區(qū)域時，HDHT的平均路由跳數(shù)得到了更大的降低。本文提出的結(jié)構(gòu)路由效率也比2-Chord要高。

[1] STOICA I, MORRIS R, LIBEN·NOWELL D,et al.Chord: A Scalable Peer-to-peer Lookup Service Protocol for Internet Applica tions[J]. IEEE/ACM Transactions on Networking,2003(4).

[2] CORDASCO G, GARGANO L, NEGRO A, et al.F-Chord:Improved Uniform Routing on Chord[J]. Networks,2008(4).

[3] CORDASCO G, SALA A. 2-Chord Halved[A].Proceedings of the 2nd International Workshop on Hot Topics in Peer-to-peer Sys tems. San Diego, California,USA,2005.

[4] CHIOLA G, CORDASCO G, GARGANO L, et al.Optimizing the Finger Table in Chord-like DHTs[J]. Concurrency and Computa tion: Practice and experience, April 2008(6).

[5] YAN H Y,GUAN J H,JIANG Y L.Symmetrical bidirectional Base-k Chord and Its Interesting Character[A]. The 5th International Conference on Semantics, Knowledge and Grid,Zhuhai,2009.

[6] 嚴(yán)華云,關(guān)佶紅,詹衛(wèi)華,等.非對稱雙向Base-k Chord [J].電信科學(xué),2010(10).

[8] JASON J.JUNG: An Empirical Study on Optimizing Query Transformation on Semantic Peer-to-peer Networks[J]. Journal of Intel ligent and Fuzzy Systems,2010(3).

A Hierarchical DHT Based on Semantic Networks

YAN Hua-yun

(School of Information Engineering, Huzhou Teachers College, Huzhou313000, China)

Aiming at Chord structure and considering the preferential problems of user query, a hierarchy DHT based on semantic network is proposed to resolve the issue. In this hierarchical DHT, nodes and keywords are organized according to semantic relations, nodes select the areas that are interesting to join in, a stable node of each area is selected as a super node, the organizations are done between nodes according to semantic relationships, and each area is organized according to 2-Chord structure. On this basis, the corresponding routing algorithm is put forward, first, this algorithm checks if keywords belong to this region management, otherwise forward to the upper super-peer to deal with, do this recursive forwarding check, until returning to query results. It was found that, when a user's query keywords prefer local zone, the routing efficiency of hierarchical DHT has some improvement compared with 2-Chord, this effect becomes increasingly obvious with increasing preference.

semantic networks; hierarchical Distribute Hash Table; Peer-to-Peer; Chord

2015-07-29

本文系2015年度湖州師范學(xué)院出國訪學(xué)項目的研究成果之一。

嚴(yán)華云(1972-) ，男，重慶萬州人，副教授，博士，主要從事對等計算和信息檢索研究。

G712

A

1672-2388(2016)01-0001-05