杜曉鋒,陳世平

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

?

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

杜曉鋒1,陳世平2

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

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

關(guān)鍵詞云計算;資源定位;Hilbert空間填充曲線

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

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

1相關(guān)研究

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

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

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

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

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

2系統(tǒng)設(shè)計

2.1相關(guān)定義

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

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

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

2.2系統(tǒng)拓撲結(jié)構(gòu)

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

圖1　系統(tǒng)網(wǎng)絡(luò)拓撲圖

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

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

2.3HSFC編碼

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

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

圖2　Hilbert填充曲線圖

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

圖3　二維屬性資源編碼圖

資源編碼表中的資源編碼可以和HSFC碼相互轉(zhuǎn)化。如圖2(b)的橫軸表示帶寬,縱軸表示內(nèi)存,圖3所示的資源編碼表與之對應(yīng),則圖3中的資源R(0101)2可轉(zhuǎn)化為相應(yīng)的HSFC編碼(0010)HSFC,圖2(b)中的曲線是將圖3中的資源編碼表轉(zhuǎn)化為HSFC值所形成的一維Hilbert曲線,實現(xiàn)了降維的目的。然后再將Hilbert曲線首尾相連,應(yīng)用到Chord環(huán)上。節(jié)點的加入和離開還是依照Chord的規(guī)則,而資源的檢索則結(jié)合了HSFC碼和Chord的相關(guān)規(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ū)間對應(yīng)的節(jié)點上,這樣當系統(tǒng)檢索到某一個節(jié)點時,不但能獲得該節(jié)點對應(yīng)的資源區(qū)間的資源,還能獲得其鄰居資源,這對于模糊查詢是有較大幫助的,而系統(tǒng)中的節(jié)點均是性能極強的云服務(wù)器,所以暫時無需考慮多部署資源對于節(jié)點性能的影響。鄰居區(qū)間對應(yīng)的節(jié)點稱為鄰居節(jié)點,當然,鄰居節(jié)點也會有其自身的鄰居節(jié)點。每個節(jié)點都保存了鄰居節(jié)點的信息,方便在本節(jié)點找不到符合要求的資源時,查找鄰居節(jié)點。

3資源查找

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

3.1查詢算法

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

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

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

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

3.2性能分析

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

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

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

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

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

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

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

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

當n=w,即所有屬性都加上了權(quán)值,則最多能將網(wǎng)絡(luò)請求數(shù)減少一半。

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

4實驗

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

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

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

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

圖5　屬性權(quán)值與查詢時延關(guān)系圖

5結(jié)束語

該文提出了一種基于HSFC的資源定位系統(tǒng),主要是將資源區(qū)間及鄰居區(qū)間的資源部署在一個節(jié)點上以提高在相同請求步數(shù)下資源查找效率,同時為屬性加上權(quán)值,以減少網(wǎng)絡(luò)請求,從而提高資源查找效率。但該文的屬性權(quán)值過于簡單,只有0和1兩種,可通過細化屬性權(quán)值的設(shè)置來加強屬性重要性的區(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]李釗偉,陳世平.支持多維查找的資源共享設(shè)計[J].計算機應(yīng)用研究,2013,30(7):2056-2059,2084.

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

[8]余星,胡德敏.基于P2P網(wǎng)絡(luò)的云資源多維查詢算法[J].計算機應(yīng)用研究,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—),男,碩士研究生。研究方向:計算機網(wǎng)絡(luò)。陳世平(1964—),男,教授,博士生導師。研究研究方向:計算機網(wǎng)絡(luò)。

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

收稿日期:2015- 09- 11