基于語義網絡的分層DHT*

嚴 華 云

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

?

基于語義網絡的分層DHT*

嚴 華 云

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

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

語義網絡；分層DHT；對等網；Chord

分布式哈希表作為一種結構化對等網，在諸多領域有廣泛的應用，如文件共享、分布式計算、數據發布等。Chord[1](P149-160)是DHT的一種典型代表。DHT中Chord是一種高效且易實現的結構化對等網。針對Chord結構，研究者提出了多種改進以提高路由效率：

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

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

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

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

一、相關工作

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

2-Chord結構是在Chord的基礎上進行的改進，它將Chord的finger表改為了對稱的雙向finger表，即保留標準Chord finger表的奇數項，刪除偶數項，并將奇數項對折到反方向上。

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

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

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

圖1　2-Chord 結構及節點1的finger表及查詢

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

二、基于語義的分層DHT

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

圖2　語義網絡的一個例子

(一)基于語義的分層DHT結構

本文提出了一種基于語義網絡的分層DHT結構，其結構如圖3所示：

圖3　基于語義網絡的分層DHT (其中每一個子區域Ai以2-Chord結構組織)

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

(二)Finger表結構

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

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

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

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

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

因此對于某節點m，其finger表為：

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

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

(三)路由

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

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

(1)根據查詢詞及其所屬語義網絡計算散列值：

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

(2)獲取節點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表示從節點n上溯到Li層的超級節點；

(6)i=i+1， 轉4；

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

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

路由查詢時，先看查詢詞是否在本地區域，如不在，則將查詢發送到其超級節點；當該超級節點接收到該請求后，看查詢詞是否為其所在區域的某一個超級節點所管轄，如該查詢不在該超級節點區域管轄范圍內，則繼續向上層的超級節點轉發該查詢請求，直到找到某一層的某超級節點管轄該查詢，則由該超級節點將該查詢請求轉發到其所轄的管理該關鍵詞的節點上，如此這般，就能得到路由查詢結果。

三、實驗模擬

實驗中采用的模擬器為PeerSim,本節的仿真以2-Chord為基準，不失一般性。實驗中假設分層DHT的層數為2層，并假設分層DHT的語義區域數為10。下面對分層DHT與2-Chord進行了全面的比較。

圖4　平均路由跳數與節點數的關系

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

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

HDHT2、HDHT3和HDHT4的平均路由跳數都比2-Chord的小，即其路由效率比2-Chord高；并且隨著本地查詢比例的增加其路由效率變得更高。這是因為HDHT2、HDHT3和HDHT4的查詢關鍵詞處于本地子區域的比例比均勻分布查詢時的大，而在本地區域查詢其路由范圍變小，因此其路由效率更高些。并且隨著本地查詢的比例增加，其所需平均路由跳數變小，從而進一步提高了其路由效率；極限情況是所有查詢都在本地區域進行，這樣所有查詢都不需要經過其上層超級節點的中轉，從而每一個查詢時的節點范圍由2-Chord的所有節點變為了HDHT的部分節點，這樣必然會大幅提高路由效率。

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

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

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

四、結　論

本文在2-Chord的基礎上，考慮到用戶對查詢的偏好問題，提出了一種基于語義的DHT結構(HDHT)，其中每個子區域(按語義關系分區)按2-Chord的方式組織，每個區域有一個節點被選為超級節點，超級節點間也可按語義關系組織成區域并按2-Chord結構方式組織。從實驗結果可知，HDHT的平均路由跳數得到了較大的降低；特別隨著用戶查詢的偏好更關注于其所在的本地區域時，HDHT的平均路由跳數得到了更大的降低。本文提出的結構路由效率也比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] 嚴華云,關佶紅,詹衛華,等.非對稱雙向Base-k Chord [J].電信科學,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年度湖州師范學院出國訪學項目的研究成果之一。

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

G712

A

1672-2388(2016)01-0001-05