一種基于HSFC的云資源定位算法

杜曉鋒,陳世平

(1.上海理工大學 光電信息與計算機工程學院,上?！?00093;2.上海理工大學 信息化辦公室,上?！?00093)

?

一種基于HSFC的云資源定位算法

杜曉鋒1,陳世平2

(1.上海理工大學 光電信息與計算機工程學院,上海200093;2.上海理工大學 信息化辦公室,上海200093)

摘要針對云計算環(huán)境下,云資源的模糊查詢問題,提出了一種云資源定位算法。該算法建立在雙層Chord環(huán)模型上,同時結合Hilbert空間填充曲線(HSFC),實現多維屬性的降維,進而完成云資源的定位。另外,該算法將整個資源空間劃分成多個資源區(qū)間,并提出鄰居區(qū)間的概念,通過鄰居區(qū)間,可較好地實現云資源的模糊查詢,此外該算法還為每個屬性設置屬性權值,以此減少網絡請求數量。實驗表明,該算法不但能有效解決云資源的模糊查詢,且能降低查詢時延,提高查詢效率。

關鍵詞云計算;資源定位;Hilbert空間填充曲線

云計算是一種以互聯網為基礎,以服務的方式動態(tài)易擴展地提供虛擬化資源的計算方式。與傳統(tǒng)的計算模型不同,其無需用戶親自管理資源,而是以服務的方式直接提供給用戶。因此,對于云資源的快速定位就成了云計算的關鍵技術之一。所謂云資源定位就是根據用戶提出的資源屬性類型和值的組合,快速找到滿足要求的資源,這是一種多屬性區(qū)間查找方式。

為實現快速有效的云資源定位,需要改變傳統(tǒng)的網絡結構模式,目前,將云計算和對等網絡技術相結合構成云對等網絡是一種比較常見的方法。云對等網絡由常年穩(wěn)定在線的云服務器構成。因此,每個節(jié)點都具有較強的處理能力,較大的存儲空間,極好的穩(wěn)定性。進而,在研究對云資源的快速定位時,節(jié)點的處理能力,存儲空間以及節(jié)點失效等問題已無需過多考慮。

1相關研究

傳統(tǒng)的P2P資源定位系統(tǒng)實現多屬性區(qū)間查找的方法大致有3類:

(1)采用特定的網絡拓撲結構,比如文獻[1～2]中的MAMSO和文獻[3]中的MAHO,其均設計了復雜的網絡拓撲結構,這些結構自身能夠支持多屬性查找。然而,其結構過于復雜,維護開銷過高,也不具備良好的可擴展性;

(2)采用多層網絡模型,比如文獻[4～8],這些系統(tǒng)都采用分層的P2P網絡結構,逐層進行單一屬性查找,將多屬性查找拆分成多個單屬性查找。最終,將多個查詢結果集做交集運算。這種查詢方式會帶來較大的網絡負載和查詢延時;

(3)應用空間填充曲線將多維屬性映射到一維索引空間,然后再結合與之相適應的P2P網絡結構,以此來實現多屬性查找,比如文獻[9]中的Squid和文獻[10]的OID,以及文獻[11]。

針對以上研究,該文提出了一種基于Hilbert空間填充曲線的云資源定位對等網絡系統(tǒng),該系統(tǒng)采用雙層Chord網絡,結合Hilbert曲線,同時結合鄰居資源等機制,著力研究多屬性模糊查詢問題。

2系統(tǒng)設計

2.1相關定義

下面給出系統(tǒng)中將會用到的一些術語的形式化定義:

定義1資源對象。具有個屬性的云資源對象用數據向量集合D={(A1,V1),(A2,V2),…,(Ai,Vi),…,(An,Vn)}表示,其中Ai表示描述資源某一特征的屬性,Vi是對應屬性Ai的屬性值。

定義2資源編碼表。將屬性類型組合相同的資源聚集在一起,形成資源簇,再將資源簇內的每個維度屬性的值都用m元組的編碼進行劃分,從而形成一張多維資源編碼表。

2.2系統(tǒng)拓撲結構

該系統(tǒng)采用雙層Chord模型。第一層為超環(huán)層,實現資源類型信息的索引。超環(huán)上每一個超級節(jié)點對應一種資源類型組合,根據資源類型組合匹配到對應的超級節(jié)點,進入對應的子環(huán)層,由于子環(huán)層是具有同一種資源類型組合的資源簇,資源簇的規(guī)模相對于整個對等網絡是較小的,所以查詢效率較高,如圖1所示。

圖1　系統(tǒng)網絡拓撲圖

然而,當資源類型種類較多時,所產生的資源類型組合也就越多,可達到2n-1,其中n是資源種類個數,為避免超環(huán)過于龐大,該文采用屬性域子集的方式。如定義3所示,關鍵在于p的取值,當p取較小,而n較大時,p?2n,就能大幅縮小超環(huán)的規(guī)模,即減少資源簇子環(huán)的數量,提高了查詢效率。

由于每個屬性組合被查詢的概率是不一樣的,可參考文獻[12],因此令查詢全集QS={q1,q2,…,qp-1,qp,…,qk},其中qi表示對某一子查詢,k表示查詢總數。對于1≤p≤k,有P(q1)≥P(qp)≥P(qk),該文將前p-1個查詢對應的屬性域子集單建索引,每一個屬性域子集對應超環(huán)層的一個超節(jié)點,而其他k-p+1查詢子集對應的屬性域子集合并成一個屬性域子集,只對應超環(huán)的一個超級節(jié)點,因此超環(huán)上只會有p個節(jié)點,超環(huán)規(guī)模得到大幅減小。

2.3HSFC編碼

為提高資源檢索效率,該文將每個維度的屬性值均分成若干段,形成一個多維資源空間,然后利用空間填充曲線將多維資源降維,使之映射到單維資源環(huán)上,而Hilbert[13]曲線具有最好數據聚集特性,故該文采用了Hilbert空間填充曲線(Hilbert Space-Filling Curve,HSFC)編碼。

將一個d維空間看作一個d維的立方體,并將其切分為nd個相同的子立方體,n是屬性的維度,Hilbert曲線就是一條依次連接兩個相鄰子立方體中心點的折線,空間中每個子立方體都被折線穿過一次,且只穿過一次。如圖2(a)所示,為一個2維空間的Hilbert曲線,其中n=2,d=2;同時,可將其進行l(wèi)次翻轉變化得到nl×d個子空間Hilbert曲線,如圖2(b)所示,是由圖2(a)經過兩次翻轉變化得到的,其中n=2,d=2,l=2。

圖2　Hilbert填充曲線圖

每個資源簇就是一個資源空間,資源簇內每種屬性就是資源空間的一個維度,n維屬性就形成一個n維空間。每個維度的屬性再被劃分為r個區(qū)間,這樣便形成了rn個多維區(qū)間。每個資源簇保存一張資源編碼表。比如一個資源簇上的資源有兩個屬性:內存和帶寬。其屬性值被劃分成4個區(qū)間,用2 bit來編碼,比如,內存有1 GB,2 GB,3 GB,4 GB,編碼為00,10,10,11,帶寬有100 Mbit·s-1,200 Mbit·s-1,300 Mbit·s-1,400 Mbit·s-1,編碼為00,01,10,11。對于內存=2 GB,帶寬=200 Mbit·s-1的資源,若用表示內存=2 GB,用(01)2表示帶寬=200 Mbit·s-1,則資源R屬性值的鍵值用(0101)2表示。如圖3所示,其中黑色陰影部分就表示資源R。

圖3　二維屬性資源編碼圖

資源編碼表中的資源編碼可以和HSFC碼相互轉化。如圖2(b)的橫軸表示帶寬,縱軸表示內存,圖3所示的資源編碼表與之對應,則圖3中的資源R(0101)2可轉化為相應的HSFC編碼(0010)HSFC,圖2(b)中的曲線是將圖3中的資源編碼表轉化為HSFC值所形成的一維Hilbert曲線,實現了降維的目的。然后再將Hilbert曲線首尾相連,應用到Chord環(huán)上。節(jié)點的加入和離開還是依照Chord的規(guī)則,而資源的檢索則結合了HSFC碼和Chord的相關規(guī)則。

2.4鄰居區(qū)間

一個維的資源簇空間會被劃分個多維區(qū)間。除了在空間邊界上的多維區(qū)間,其他的多維區(qū)間在任意維度上都有兩個相鄰的區(qū)間,這些區(qū)間便是鄰居區(qū)間。如圖3所示,黑色陰影表示的資源區(qū)間(0101)2擁有4個鄰居區(qū)間,即斜陰影表示的(0001)2,(0100)2,(1001)2,(0110)2。將鄰居區(qū)間的資源稱為鄰居資源,將每個資源區(qū)間的資源和其鄰居資源部署在該資源區(qū)間對應的節(jié)點上,這樣當系統(tǒng)檢索到某一個節(jié)點時,不但能獲得該節(jié)點對應的資源區(qū)間的資源,還能獲得其鄰居資源,這對于模糊查詢是有較大幫助的,而系統(tǒng)中的節(jié)點均是性能極強的云服務器,所以暫時無需考慮多部署資源對于節(jié)點性能的影響。鄰居區(qū)間對應的節(jié)點稱為鄰居節(jié)點,當然,鄰居節(jié)點也會有其自身的鄰居節(jié)點。每個節(jié)點都保存了鄰居節(jié)點的信息,方便在本節(jié)點找不到符合要求的資源時,查找鄰居節(jié)點。

3資源查找

由于用戶請求的資源往往要比實際能夠滿足用戶需求所需的最低資源要求更高,所以系統(tǒng)在找不到完全滿足請求的資源時,提供比請求要求稍低的資源也能滿足用戶需求。因此,該文為屬性設置一個權重W,取值為0或1。0表示請求中該屬性的值為最低要求,假如提供比該值更小的資源,將不能滿足用戶的需求。1則相反,表示即使提供比要求的屬性值稍小的資源,也能滿足需求。這能進一步減少網絡請求數,加快查詢速度。

3.1查詢算法

(1)節(jié)點N接收到查詢請求Q,若N是葉節(jié)點,則N將請求提交到超環(huán),然后在超環(huán)上匹配請求Q中的屬性類型組合,找到相應的超級節(jié)點,若節(jié)點N是超級節(jié)點,則直接在超環(huán)上查找與請求Q屬性類型組合對應的超級節(jié)點。若在超環(huán)上未找到與請求Q屬性類型組合對應的超級節(jié)點,則返回查詢失敗。否則進行步驟(2);

(2)若在超環(huán)上找到了與請求Q中屬性類型組合相適應的超級節(jié)點,則進入與該超級節(jié)點相連的葉環(huán)中進行進一步查詢。首先根據請求Q的屬性值信息查詢屬性資源編碼表,確定屬性資源區(qū)間編碼,再將其轉化成HSFC編碼,然后根據Chord算法定位到提供該資源的節(jié)點,若在節(jié)點上找到了滿足請求Q的資源,則將節(jié)點的IP提供給用戶,讓節(jié)點和用戶直接通信,獲取資源。由于該文是將某一個資源區(qū)間及其鄰居資源部署在同一個節(jié)點上,所以這里查找一個節(jié)點不但能查找與該節(jié)點本身對應的資源區(qū)間,還能查詢其鄰居資源,這就增加了在該節(jié)點查詢成功的機率。若在該節(jié)點找不到適合的資源,即與該節(jié)點本身對應的資源區(qū)間的資源不足,且其鄰居資源也不足,則轉入步驟(3);

(3)當在某個節(jié)點沒有找到請求的資源時,節(jié)點根據請求中每個屬性的權值,選擇有可能擁有滿足請求資源的鄰居節(jié)點轉發(fā)請求,比如某個屬性權值為0,則只需向在這一屬性維度上值增長方向的鄰居節(jié)點轉發(fā)請求,而在這個屬性維度上值降低方向上的鄰居節(jié)點可忽略,由此便減少了網絡請求,加快了查詢速度。然后重復步驟(2)。此時,由于每個鄰居區(qū)間都有自己的鄰居區(qū)間,所以查詢到的資源區(qū)間進一步增多,查詢成功的幾率進一步增大。若進一步重復步驟(3),能查詢到的資源區(qū)間會越來越多,但沒有必要。因此,該文最多只重復兩次步驟(3)。如果進行了兩次步驟(3)之后還沒有找到滿足請求的資源,則返回失敗。

假設圖1中節(jié)點接收到一個請求,其中內存為2 GB,帶寬為200 Mbit·s-1,兩者的權值都為0,LN0首先將請求通過SN1提交到超環(huán),匹配到超級節(jié)點SN1是內存和帶寬這兩個屬性組合對應的超級節(jié)點,則進入SN1超級節(jié)點所在的葉環(huán),首先查找圖3所示的資源編碼表,發(fā)現內存為2 GB,帶寬為200 Mbit·s-1對應的資源區(qū)間是(0101)2,接著轉化成HSFC編碼,為圖2(b)中(0010)HSFC,然后根據Chord算法找到對應的葉節(jié)點,假設是LN2,此時已經查找了資源區(qū)間(0001)2,(0100)2,(1001)2,(0110)2,(0110)2,發(fā)現節(jié)點上沒有滿足的資源,則查找鄰居節(jié)點,由于兩個屬性的權值均為0,只需要查找資源編碼表中(0110)2,(1001)2對應的節(jié)點,LN2將請求(0110)2,(1001)2對應的節(jié)點,這就能夠查找到資源區(qū)間(0010)2,(0111)2,(1010)2,(1101)2,(1000)2,即圖3中豎線陰影表示的資源區(qū)間,最后在其中找到了滿足要求的資源,將節(jié)點IP提交給用戶,否則將請求轉發(fā)給(0110)2和(1001)2對應的鄰居節(jié)點。

3.2性能分析

由于整個網絡均是按照Chord組織的,所以不過多分析系統(tǒng)的查找復雜度,該文著重分析將某個資源區(qū)間及其鄰居資源部署在同一個節(jié)點上,以及屬性權值對于資源查找的影響。

定義查找范圍比μ為某一節(jié)點發(fā)出一次請求后總共所查詢到的資源編碼表中資源區(qū)間的數量和資源編碼表中總的資源區(qū)間數量的比值。在發(fā)出請求數量相同的情況下,能查詢到的資源區(qū)間數越多,則在該步請求時查詢成功的可能性越大,即查詢速度越快,所以該文使用μ來分析資源查詢的性能。

假設屬性維度為n,每個屬性維度的值區(qū)間個數為r,當不將鄰居資源部署在同一個節(jié)點上時,假設某一個資源區(qū)間有2n個鄰居區(qū)間,則該資源區(qū)間對應的節(jié)點發(fā)出第一次請求有

當將鄰居資源部署在同一個節(jié)點上時,且某個資源區(qū)間及其鄰居區(qū)間都有2n個鄰居區(qū)間,則該資源區(qū)間對應的節(jié)點發(fā)出第一次請求有

該資源區(qū)間對應的節(jié)點發(fā)出第二步請求有

由此可見,將鄰居資源部署在同一個節(jié)點上,只是稍微增加了一點云服務器的負擔,但卻使得在相同的網絡請求數下,能夠查找到的資源區(qū)間數量乘n倍增長,資源查找的速度和成功率都得到提升。

另外,假設n維屬性中有w個屬性加上了屬性權值,則在第一個節(jié)點查找失敗時,該節(jié)點所需要發(fā)出的網絡請求數是

L=w+2(n-w)=2n-w

當n=w,即所有屬性都加上了權值,則最多能將網絡請求數減少一半。

將鄰居資源部署在同一個節(jié)點上使得在相同網絡請求數下,資源查找性能得以優(yōu)化,又通過屬性權值使網絡請求數減少,在兩種因素的作用下,資源查找性能得到較大優(yōu)化。

4實驗

實驗環(huán)境為CPU3.40GHz,內存2GB,Linux操作系統(tǒng),JDK1.6,在1.0.5版本的PeerSim上用Java實現的一個模擬環(huán)境。

實驗1對比將鄰居資源部署在同一節(jié)點上前后網絡平均查詢時延,以驗證將鄰居資源部署在同一節(jié)點上對于系統(tǒng)性能的優(yōu)化。屬性維度為4,并且不為屬性加上權值,網絡節(jié)點數為1 000個,1 500個,2 000個,2 500個,3 000個和3 500個,網絡超節(jié)點都為10個,每個屬性維度分8個屬性值區(qū)間。如圖4所示,折線1表示將鄰居資源部署在同一節(jié)點之前,折線2表示將鄰居資源部署在同一節(jié)點之后,可以看出,將鄰居資源部署在同一節(jié)點上可加快資源查找速度。

圖4　將鄰居資源部署在同一節(jié)點前后查詢時延變化

實驗2驗證屬性權值對于減少查找時延的影響。網絡節(jié)點數為3 000個,屬性種類個數為1個到10個,每個屬性權值的個數為0～5個。同時,將鄰居資源部署在同一個節(jié)點上,每組實驗做10次,取平均值,得到結果如圖5所示。因一個屬性只加一個權值,所以權值個數大于屬性維度的情況是不存在的,在圖5中用虛線表示。由圖5可看出,平均查詢延時隨著屬性維度的增加快速增長。同時可看出,在屬性維度相同的情況下,屬性權值個數越多,平均查詢時延越小,而且當屬性維度和權值個數相同時,降低查詢時延的效果最佳。

圖5　屬性權值與查詢時延關系圖

5結束語

該文提出了一種基于HSFC的資源定位系統(tǒng),主要是將資源區(qū)間及鄰居區(qū)間的資源部署在一個節(jié)點上以提高在相同請求步數下資源查找效率,同時為屬性加上權值,以減少網絡請求,從而提高資源查找效率。但該文的屬性權值過于簡單,只有0和1兩種,可通過細化屬性權值的設置來加強屬性重要性的區(qū)分度。同時,該文是將某個資源區(qū)間在每個維度上相鄰的資源區(qū)間定義為鄰居資源區(qū)間,可以進一步探討鄰居資源區(qū)間的定義,使得部署在同一節(jié)點上的鄰居資源更加合理有效。

參考文獻

[1]Bharambe A R,Agrawal M,Seshan S.Mercury:supporting scalable multi-attribute range queries[C].Portland,OR:ACM/SIGCOMM 2004 Conference on Computer Communications,2004.

[2]YoufuY U,LAI Huanchou.A semi-strucured overlay for multi-attribute range queries in cloud computing[C].Hong Kong,China:IEEE 13th International Conference on Computational Science and Engineering (CSE 2010),2010.

[3]LAI Kuanchou,YU Youfu.A scalable multi-attribute hybrid overlay for range queries on the cloud.[J].Information System Fontier,2012(14):895-908.

[4]Papadakis H,Trunfio P,Talia D,et al.Design and implementation of a hybrid p2p-based grid resource discovery system[C].Heraklion,Greece:Joint Workshop on Making Grids Works,2007.

[5]Yang Min,Yang Yuanyuan.An efficient hybrid peer-to-peer system for distributed data sharing[J].IEEE Transactions on Computers,2010,59(9):1158-1171.

[6]李釗偉,陳世平.支持多維查找的資源共享設計[J].計算機應用研究,2013,30(7):2056-2059,2084.

[7]張明英,胡德敏,高麗萍,等.基于結構化對等網絡的云資源查詢算法[J].計算機應用研究,2015,32(2):532-535.

[8]余星,胡德敏.基于P2P網絡的云資源多維查詢算法[J].計算機應用研究,2014,31(10):3061-3064.

[9]Schmidt C,Parashar M.Flexible information discovery in decentralized distributed systems[C].Seattle,WA:12th IEEE International Symposium on High-Performance Distributed Computing,2003.

[10]Memon F,Tiebler D,Tomsu M,et al.OID:Optimized information discovery using space filling curves in P2P overlay networks[C].Melbourne,Australia:14th International Conference on Parallel and Distributed Systems,2008.

[11]Lawder J K,King Pjh.Using space-filling curves for multi-dimensional indexing[C].Exter,England:17th British National Conference on Databases (BNCOD 17),2000.

[12]Klemn A,Lindemann C,Vernon K,et al.Characterizing the query behavior in peer-to-peer file sharing systems[C].New York:the 4th ACM SIGCOMM Conference on Internet Measurement,2004.

[13]Moon B,Jagadish H V,Faloutsos C,et al.Analysis of theclustering properties of the hilbert space-filling curve[J].IEEE Transactions on Knowledge and Data Engineering,2001,13(1):124-141.

An HSFC-based Cloud Source Discovery Algorithm

DU Xiaofeng1,CHEN Shiping2

(1.School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China;2.Information Office,University of Shanghai for Science and Technology,Shanghai 200093,China)

AbstractA cloud resource discovery algorithm is proposed for the fuzzy query of cloud resource in cloud computing.Based on a hierarchical Chord model and combined with Hilbert Space Filling Curve (HSFC),this algorithm realizes dimensionality reduction of multidimensional attributes and then completes cloud source discovery.In addition,the source space is divided into several multidimensional intervals,and the concept of neighbor interval is put forward,with which the fuzzy query of cloud resource is resolved.Every attribute is given a weight to reduce requests in the network.The experimental results show that the algorithm not only resolves the fuzzy query of cloud resource,but also reduces delay as much as possible to improve query efficiency.

Keywordscloud computing;source discovery;HSFC

中圖分類號TP391

文獻標識碼A

文章編號1007-7820(2016)04-032-05

doi:10.16180/j.cnki.issn1007-7820.2016.04.009

作者簡介:杜曉鋒(1990—),男,碩士研究生。研究方向:計算機網絡。陳世平(1964—),男,教授,博士生導師。研究研究方向:計算機網絡。

基金項目:國家自然科學基金資助項目(61170277;61472256);上海市教委科研創(chuàng)新重點基金資助項目(12zz137);上海市一流學科建設基金資助項目(S1201YLXK)

收稿日期:2015- 09- 11