殷君茹,唐小明,李惺穎,卜祥亮

(1.中國林業(yè)科學(xué)研究院 資源信息研究所,北京100091;2.廣西林業(yè)勘測設(shè)計院 3S技術(shù)研究與開發(fā)中心,南寧 530011;3.北京林業(yè)大學(xué) 水土保持學(xué)院,北京 100083)

?

并行環(huán)境下基于圖著色理論的空間數(shù)據(jù)部署

殷君茹1,唐小明1,李惺穎2,卜祥亮3

(1.中國林業(yè)科學(xué)研究院 資源信息研究所,北京100091;2.廣西林業(yè)勘測設(shè)計院 3S技術(shù)研究與開發(fā)中心,南寧 530011;3.北京林業(yè)大學(xué) 水土保持學(xué)院,北京 100083)

在面向計算部署到數(shù)據(jù)節(jié)點端執(zhí)行的分布式并行環(huán)境下,提出一種基于圖著色理論的適用于矢量空間數(shù)據(jù)的部署方法,將空間數(shù)據(jù)粒度的部署問題轉(zhuǎn)化為圖頂點著色的過程,提高了任意空間區(qū)域的信息查詢效率.給出基于圖著色理論的數(shù)據(jù)部署方法,并通過節(jié)點的任務(wù)量進(jìn)一步改進(jìn)算法,使得該算法可實現(xiàn)海量空間數(shù)據(jù)粒度的離散化部署,提高了空間數(shù)據(jù)檢索和查詢的并行化程度,充分利用了并行計算資源.

空間數(shù)據(jù)部署；數(shù)據(jù)粒度；并行環(huán)境；圖著色理論；負(fù)載均衡

并行計算環(huán)境下的空間數(shù)據(jù)部署一般都采用“分而治之”的思想,按照一定的規(guī)則將海量空間數(shù)據(jù)均衡分配存放在多個節(jié)點中,從而達(dá)到多節(jié)點、多處理器協(xié)同工作,提高空間數(shù)據(jù)的快速查詢響應(yīng)和并行分析能力[1-3].

空間數(shù)據(jù)部署(用于任務(wù)劃分和負(fù)載均衡控制)是影響并行地理信息系統(tǒng)(GIS)的關(guān)鍵因素,目前研究多集中在海量事務(wù)性數(shù)據(jù)上,采用主流的分布式文件系統(tǒng)(如GFS,Hadoop,Cassandra,Dynamo和Apache Spark)進(jìn)行管理,按照一致性Hash策略將數(shù)據(jù)均分為大小相同的數(shù)據(jù)塊,并對每個塊進(jìn)行隨機(jī)部署,實現(xiàn)了海量數(shù)據(jù)的均衡分布,卻忽略了數(shù)據(jù)間的關(guān)聯(lián)關(guān)系,導(dǎo)致大量不必要的數(shù)據(jù)傳輸任務(wù)[4].文獻(xiàn)[5-6]基于Hadoop的分布式文件系統(tǒng)HBase實現(xiàn)了對空間數(shù)據(jù)的部署管理,提升了查詢海量空間數(shù)據(jù)的效率,但不能滿足空間數(shù)據(jù)的復(fù)雜查詢；目前高性能并行GIS多采用對象關(guān)系型數(shù)據(jù)庫管理海量空間數(shù)據(jù)[7-10],文獻(xiàn)[11-12]在Oracle Spatial基于空間位置范圍劃分策略的基礎(chǔ)上,分別采用基于Hilbert空間填充曲線和K-平均聚類算法,實現(xiàn)了對原子空間數(shù)據(jù)項的均衡分配,但未考慮特定的多個相鄰區(qū)域空間查詢的并行效率.

在實際應(yīng)用中,通常在特定比例尺下,當(dāng)多用戶并發(fā)訪問或涉及多區(qū)域間的空間信息且這些區(qū)域集中在同一個節(jié)點時,就會導(dǎo)致該節(jié)點過載,同時其他節(jié)點的計算資源空閑,形成對某個節(jié)點較長時間的依賴性,影響系統(tǒng)的整體性能.因此,為提高該場景下的并行計算效率,本文采用基于圖著色理論的空間數(shù)據(jù)部署策略和方法,通過將空間數(shù)據(jù)粒度部署轉(zhuǎn)化為頂點著色模型,利用各節(jié)點的任務(wù)量作為約束條件對算法進(jìn)行修正,使得各節(jié)點數(shù)據(jù)負(fù)載達(dá)到均衡的同時,相鄰空間區(qū)域盡量離散化分布,從而提高查詢的并行化程度,并以遼寧省林地數(shù)據(jù)為例,驗證了該方法的有效性.

1 基于圖著色的空間數(shù)據(jù)部署模型構(gòu)建

由于采用的并行計算策略是在進(jìn)行一次空間查詢時,將任務(wù)調(diào)度至相關(guān)節(jié)點進(jìn)行運(yùn)算,因而系統(tǒng)的響應(yīng)時間由參與計算的節(jié)點數(shù)、各節(jié)點參與計算的數(shù)據(jù)量和節(jié)點之間的數(shù)據(jù)傳輸決定.

定義1系統(tǒng)響應(yīng)時間定義為

其中:T(pi)表示各節(jié)點處理任務(wù)的時間;Tcomm(i)表示由于數(shù)據(jù)傳輸耗費的通訊時間;m表示節(jié)點數(shù)量.由式(1)可知,要提高系統(tǒng)的響應(yīng)數(shù)間,數(shù)據(jù)部署時應(yīng)使各節(jié)點的任務(wù)量分布均衡,以減少各節(jié)點處理任務(wù)的時間差異；數(shù)據(jù)部署后使各節(jié)點的子任務(wù)聯(lián)系盡量少,以減少數(shù)據(jù)傳輸?shù)臅r間消耗.

采用數(shù)據(jù)粒度表示空間數(shù)據(jù)對象經(jīng)一定的劃分規(guī)則得到數(shù)據(jù)表的度量,它直接影響數(shù)據(jù)表的掃描時間和數(shù)據(jù)命中率.對于空間數(shù)據(jù)粒度查詢過程,若所涉及查詢的數(shù)據(jù)粒度盡可能分布在多個節(jié)點上,且相鄰的數(shù)據(jù)粒度不在同一個節(jié)點上,則能充分利用并行資源,提高并行度,并極大降低各節(jié)點子任務(wù)之間的通訊.因此,基于該思想可將數(shù)據(jù)粒度的部署轉(zhuǎn)化為圖著色過程.

1.1基于圖著色的數(shù)據(jù)部署模型構(gòu)建

圖著色是指對圖的每個頂點(邊或面)指定一種顏色,使相鄰的頂點(邊或面)不同色.主要包括頂點著色、邊著色和圖的全著色.經(jīng)過一定的變換,圖的邊著色和全著色都可以等價轉(zhuǎn)化為圖的頂點著色.該問題可描述為：給定無向圖G(V,E),V={v1,v2,…,vn},建立映射C:V→{c1,c2,…,ck},使得對任意的(vi,vj)∈E,C(vi)≠C(vj).因此,本文采用頂點著色為V中的頂點進(jìn)行著色,即在滿足一定條件下,使得任意兩個相鄰頂點的顏色不相同[13].

在分布式存儲的并行體系中,任務(wù)計算和數(shù)據(jù)交換通過節(jié)點和網(wǎng)絡(luò)進(jìn)行,本文僅考慮同構(gòu)網(wǎng)絡(luò),即節(jié)點間的參數(shù)相同,用點集P={p1,p2,…,pm}表示m個節(jié)點.

定義2(數(shù)據(jù)粒度分布圖) 數(shù)據(jù)粒度及其空間相鄰關(guān)系可用一個無向圖G=(V,E)表示,其中:V中的頂點表示數(shù)據(jù)粒度,即V={vi|待分配的所有數(shù)據(jù)粒度i};E中的邊表示數(shù)據(jù)粒度之間的空間相鄰性,即E={(vi,vj)|數(shù)據(jù)粒度的空間相鄰性}.每個頂點v(v∈V)有一個w表示v所表達(dá)的數(shù)據(jù)粒度大小.

定義3(數(shù)據(jù)粒度映射) 用一個映射函數(shù)表示數(shù)據(jù)粒度到計算機(jī)的映射M：V→P,如果頂點l(l∈V)表示的數(shù)據(jù)粒度被部署到節(jié)點p(p∈P)上,則M(l)=p.

定義4(頂點著色的數(shù)據(jù)部署模型) 設(shè)顏色集合C={c1,c2,…,cm},給定數(shù)據(jù)粒度分布圖G(V,E),V={v1,v2,…,vn},建立映射M:V→C,使得對任意的(vi,vj)∈E,C(vi)∩C(vj)=?,且C=P,則M定義的映射關(guān)系由空間拓?fù)溧徑泳仃嘐n×n確定,并有

且當(dāng)E(i,j)=1時,vi與vj不可分配在同一個節(jié)點上.

在數(shù)據(jù)粒度部署中,節(jié)點對應(yīng)于顏色集合C={cm|1≤m≤M}.數(shù)據(jù)部署過程如圖1所示.

圖1 空間數(shù)據(jù)部署過程Fig.1 Spatial data placement

1.2評價指標(biāo)

2 基于圖著色模型的數(shù)據(jù)部署求解方法

本文提出的基于圖著色模型的數(shù)據(jù)部署求解方法過程分為兩個階段：Ⅰ.基于頂點著色算法求得任一相鄰的空間數(shù)據(jù)粒度都不在同一節(jié)點；Ⅱ.動態(tài)統(tǒng)計各節(jié)點的任務(wù)量,并以此修正第Ⅰ階段的分配行為,確定最終的數(shù)據(jù)部署方案.

2.1數(shù)據(jù)部署求解第Ⅰ階段

對于無向圖G(V,E),頂點序列V={v1,v2,…,vn}(n為待分配數(shù)據(jù)粒度總數(shù)),顏色集C={c1,c2,…,cm}, 通過E(i,j)的取值判斷頂點間的空間位置關(guān)系,將其作為一個約束條件,以實現(xiàn)數(shù)據(jù)粒度的離散化分布,算法可描述為：

1)給v1著色,在顏色集C中選擇第1個顏色c1給v1著色,將v1移至已著色頂點集V(k)中,且c1標(biāo)記為已使用顏色;

2)給v2著色,判斷v2與v1的空間位置關(guān)系,如果E(1,2)=0,則用c1為v2著色；否則,從C中去除c1,選擇可著色集中的一個元素c2為v2著色,將v2移至已著色頂點V(k)中,且c2標(biāo)記為已使用顏色;

3)給vi(i≥3)著色,依次判斷vi與V(k)中頂點的空間位置關(guān)系.如果都不相鄰,則從已使用顏色中任選一種顏色ct為vi著色,否則,從C中去除相鄰頂點所著色的顏色,并在剩余可著顏色中選擇一種顏色cm為vi著色,將vi移至已著色的頂點集合中,為頂點vi+1著色,圖2為給頂點vi著色的算法流程;

4)當(dāng)V-V(k)≠?時,轉(zhuǎn)3)；否則,著色完成,生成著色方案C;

5)將每種顏色ck對應(yīng)一個數(shù)據(jù)節(jié)點pk,找出所有著ck顏色的頂點,即所代表的數(shù)據(jù)粒度,部署給該數(shù)據(jù)節(jié)點pk,直到每個數(shù)據(jù)節(jié)點部署完成為止.

該算法的特點是優(yōu)先使用已分配數(shù)據(jù)的節(jié)點,但隨著數(shù)據(jù)粒度逐漸增多,會出現(xiàn)節(jié)點間數(shù)據(jù)分布不均衡的情況,將加重個別節(jié)點的計算負(fù)載,延長系統(tǒng)總體的響應(yīng)時間.

2.2數(shù)據(jù)部署求解第Ⅱ階段

3 實驗分析

3.1實驗數(shù)據(jù)

實驗數(shù)據(jù)為遼寧省2005年度林地數(shù)據(jù),包含小班數(shù)據(jù)共有1 535 720條(小班在行政級別上低于村的林業(yè)管理單元).小班數(shù)據(jù)類型為面狀矢量數(shù)據(jù),共有50個屬性字段,既包括反映森林資源現(xiàn)狀和變化的屬性信息,如權(quán)屬、地類、優(yōu)勢樹種、面積等,也包括反映空間特征的信息,如空間數(shù)據(jù)類型、空間位置坐標(biāo)等.其中縣級行政單位共有124個,經(jīng)實驗分析和數(shù)據(jù)管理的綜合考慮,本文采用縣級單位作為數(shù)據(jù)節(jié)點存儲的數(shù)據(jù)粒度單元,并經(jīng)過一定的拆分和合并,形成以縣為單位的105個數(shù)據(jù)粒度.

3.2實驗環(huán)境

實驗環(huán)境由4臺服務(wù)器組成服務(wù)器集群,服務(wù)器為IBM X3650M4服務(wù)器,CPU為英特至強(qiáng)E5-2609 2.4 GHz,24 GB內(nèi)存,8×600 GB硬盤.主節(jié)點為其中一臺的服務(wù)器,同時該4臺服務(wù)器也充當(dāng)數(shù)據(jù)節(jié)點,每個數(shù)據(jù)節(jié)點由Oracle Spatial提供存儲支持.

3.3遼寧省縣級數(shù)據(jù)粒度部署實例

首先按空間拓?fù)潢P(guān)系生成105×105的空間關(guān)系矩陣,并采用數(shù)據(jù)部署求解第Ⅰ階段中基于頂點著色模型的數(shù)據(jù)粒度部署算法,結(jié)果如圖4所示；采用數(shù)據(jù)部署求解第Ⅱ階段中通過負(fù)載均衡改進(jìn)的算法生成數(shù)據(jù)分布圖,結(jié)果如圖5所示.

1,2,3,4分別表示數(shù)據(jù)節(jié)點1,2,3,4.

1,2,3,4分別表示數(shù)據(jù)節(jié)點1,2,3,4.

由圖4和圖5可見,隨著算法約束條件的增加,空間數(shù)據(jù)在各數(shù)據(jù)節(jié)點上的部署也隨之發(fā)生改變.分別根據(jù)圖4和圖5中統(tǒng)計數(shù)據(jù)節(jié)點的數(shù)據(jù)粒度分布情況,結(jié)果列于表1和表2.

表1 基于頂點著色模型的數(shù)據(jù)節(jié)點記錄數(shù)分布情況Table 1 Vertex coloring based records distribution of data nodes

表2 改進(jìn)算法的數(shù)據(jù)節(jié)點記錄數(shù)分布情況Table 2 Records distribution of data nodes after algorithm improvement

1,2,3,4分別表示數(shù)據(jù)節(jié)點1,2,3,4.

由表1可見:通過每個數(shù)據(jù)節(jié)點的表總數(shù)對比,發(fā)現(xiàn)4個數(shù)據(jù)節(jié)點的表數(shù)量分布不均衡;各數(shù)據(jù)節(jié)點的記錄數(shù)差別較大,存儲量變異系數(shù) C.V1=17.34%.由表2可見：通過每個數(shù)據(jù)節(jié)點的表總數(shù)對比,4個數(shù)據(jù)節(jié)點存儲的表總數(shù)非常均勻;存儲量變異系數(shù)C.V2=4.55%,明顯小于C.V1的值.

實驗結(jié)果表明,通過改進(jìn)算法各數(shù)據(jù)節(jié)點表的數(shù)據(jù)分布更均衡,各數(shù)據(jù)節(jié)點存儲的記錄數(shù)離散程度顯著減少,使得數(shù)據(jù)負(fù)載更趨于均衡.

如圖6所示,當(dāng)進(jìn)行任意區(qū)域的空間數(shù)據(jù)查詢時,數(shù)據(jù)節(jié)點1涉及2個數(shù)據(jù)粒度,數(shù)據(jù)節(jié)點2為3個,數(shù)據(jù)節(jié)點3為3個,數(shù)據(jù)節(jié)點4為3個,這些數(shù)據(jù)粒度不僅離散地分布在4個數(shù)據(jù)節(jié)點上,且各節(jié)點的任務(wù)量趨于均衡.

綜上所述,本文描述了在并行計算環(huán)境下,面對任意空間區(qū)域的信息快速查詢,提出了一種基于圖著色理論的空間矢量數(shù)據(jù)部署方法,將數(shù)據(jù)粒度的部署轉(zhuǎn)化為基于頂點著色模型的圖著色過程,將數(shù)據(jù)粒度間的空間拓?fù)潢P(guān)系和數(shù)據(jù)節(jié)點的存儲量作為約束條件,修正了基于頂點著色模型的數(shù)據(jù)部署算法,并通過實驗證明該方法實現(xiàn)了數(shù)據(jù)節(jié)點間存儲負(fù)載均衡,以及空間位置相鄰數(shù)據(jù)粒度的離散分布,為海量空間矢量數(shù)據(jù)在多數(shù)據(jù)節(jié)點上的均勻部署提供了一種思路,從而能在并行計算時更有效地利用并行計算資源,減少數(shù)據(jù)節(jié)點間的通信,提高了空間數(shù)據(jù)的快速響應(yīng)和并行分析效率.但本文由于在算法中將數(shù)據(jù)節(jié)點間的存儲量和空間拓?fù)潢P(guān)系同時作為約束條件,使得當(dāng)數(shù)據(jù)節(jié)點的個數(shù)選擇不合適時,會出現(xiàn)個別數(shù)據(jù)粒度與所有數(shù)據(jù)節(jié)點沖突,導(dǎo)致無法分配的問題,這需要根據(jù)實際需求進(jìn)行適當(dāng)修正,以優(yōu)先保證存儲負(fù)載均衡.

[1] 王結(jié)臣,王豹,胡瑋,等.并行空間分析算法研究進(jìn)展及評述 [J].地理與地理信息科學(xué),2011,27(6):1-5.(WANG Jiechen,WANG Bao,HU Wei,et al.Review on Parallel Spatial Analysis Algorithms [J].Geography and Geo-Information Science,2011,27(6):1-5.)

[2] 李峙,陳朝暉.空間疊加分析中的分而治之算法研究與應(yīng)用 [J].計算機(jī)工程與應(yīng)用,2009,45(34):230-232.(LI Zhi,CHEN Chaohui.Study and Applications of Divide and Conquer Algorithm in Spatial Overlay Analysis [J].Computer Engineering and Applications,2009,45(34):230-232.)

[3] 宋杰,李甜甜,閆振興,等.數(shù)據(jù)密集型計算中負(fù)載均衡的數(shù)據(jù)布局方法 [J].北京郵電大學(xué)學(xué)報,2013,36(4):76-80.(SONG Jie,LI Tiantian,YAN Zhenxing,et al.Load-Balanced Data Layout Approach in Data-Intensive Computing [J].Journal of Beijing University of Posts and Telecommunications,2013,36(4):76-80.)

[4] 王藝文,蘇森,謝琛甫,等.跨數(shù)據(jù)中心的關(guān)聯(lián)云數(shù)據(jù)部署策略 [J].華中科技大學(xué)學(xué)報:自然科學(xué)版,2013,41(增刊2):48-51.(WANG Yiwen,SU Sen,XIE Chenfu,et al.Dependent Cloud Data Placement on Geo-Datacenters [J].Huazhong University of Science and Technology:Natural Science Edition,2013,41(Suppl 2):48-51.)

[5] 崔鑫.海量空間數(shù)據(jù)的分布式存儲管理及并行處理技術(shù)研究 [D].長沙:國防科學(xué)技術(shù)大學(xué),2010.(CUI Xin.Research on Massive Spatial Data Distributed Storage and Parallel Processing Technology [D].Changsha:National University of Defense Technology,2010.)

[6] 范建永,龍明,熊偉.基于HBase的矢量空間數(shù)據(jù)分布式存儲研究 [J].地理與地理信息科學(xué),2012,28(5):39-42.(FAN Jianyong,LONG Ming,XIONG Wei.Research of Vector Spatial Data Distributed Storage Based on HBase [J].Geography and Geo-Information Science,2012,28(5):39-42.)

[7] 趙春宇.高性能并行GIS中矢量數(shù)據(jù)存取與處理關(guān)鍵技術(shù)研究 [D].武漢:武漢大學(xué),2006.(ZHAO Chunyu.Studying on the Technolgies of Storage and Processing of Spatial Vector Data in High-Performance Parallel GIS [D].Wuhan:Wuhan University,2006.)

[8] 宋效東,竇萬峰,湯國安,等.分布式并行地形分析中數(shù)據(jù)劃分機(jī)制研究 [J].國防科技大學(xué)學(xué)報,2013,35(1):130-135.(SONG Xiaodong,DOU Wanfeng,TANG Guo’an,et al.Research on Data Partitioning of Distributed Parallel Terrain Analysis [J].Journal of National University of Defense Technology,2013,35(1):130-135.)

[9] Jean-Marie A,Lefebvre-Barbaroux S,LIU Zhen.An Analytical Approach to the Performance Evaluation of Master-Slave Computational Model [J].Parallel Computing,1998,24(5/6):841-862.

[10] SUN Xianhe,Gustafsom J L.Towards a Better Parallel Performance Metric [J].Parallel Computing,1991,17(10/11):1093-1109.

[11] 賈婷,魏祖寬,唐曙光,等.一種面向并行空間查詢的數(shù)據(jù)劃分方法 [J].計算機(jī)科學(xué),2010,37(8):198-200.(JIA Ting,WEI Zukuan,TANG Shuguang,et al.New Spatial Data Partition Approach for Spatial Data Query [J].Computer Science,2010,37(8):198-200.)[12] 趙春宇,孟令奎,林志勇.一種面向并行空間數(shù)據(jù)庫的數(shù)據(jù)劃分算法研究 [J].武漢大學(xué)學(xué)報:信息科學(xué)版,2006,31(11):962-965.(ZHAO Chunyu,MENG Lingkui,LIN Zhiyong.Spatial Data Partitioning towards Parallel Spatial Database System [J].Geomatics and Information Science of Wuhan University,2006,31(11):962-965.)

[13] 朱虎,宋恩民,路志宏.求解圖著色問題的最大最小蟻群搜索算法 [J].計算機(jī)仿真,2010,27(3):190-192.(ZHU Hu,SONG Enmin,LU Zhihong.Max-Min Ant Search Algorithm for Solving Graph Coloring Problem [J].Computer Simulation,2010,27(3):190-192.)

(責(zé)任編輯：韓 嘯)

GraphColoringBasedSpatialDataPlacementtowardsParallelComputingSystem

YIN Junru1,TANG Xiaoming1,LI Xingying2,BU Xiangliang3

(1.ResearchInstituteofResourceInformationTechniques,ChineseAcademyofForestry,Beijing100091,China;2.RS,GIS,GPSTechnologyResearch&DevelopmentCenter,GuangxiForestInventory&PlanningInstitute,Nanning530011,China;3.CollegeofSoilandWaterConservation,BeijingForestryUniversity,Beijing100083,China)

An algorithm suitable for spatial vector data placement based on graph coloring theory was presented in the parallel system of computing distributed to data nodes.The deployment problem was transferred into graph vertex coloring problem,and the information query efficiency of any spatial area was thus improved.Moreover,the algorithm based on graph vertex coloring problem was proposed and improved by the task of nodes.This algorithm can achieve discrete deployment of massive spatial data granularity and storage load balance of the nodes,improve the degree of parallelism spatial data retrieval and query,and make full use of parallel computing resources.

spatial data placement;data granularity;parallel computing system;graph coloring theory;load balancing

10.13413/j.cnki.jdxblxb.2015.03.33

2014-10-28.

殷君茹(1986—),女,漢族,博士研究生,從事GIS開發(fā)與應(yīng)用的研究,E-mail:yinjr1986@163.com.通信作者：唐小明(1959—),男,漢族,博士,研究員,博士生導(dǎo)師,從事GIS開發(fā)與應(yīng)用的研究,E-mail:tangxm@caf.ac.cn.

國家高技術(shù)研究發(fā)展計劃863項目基金(批準(zhǔn)號：2012AA102001)和國家林業(yè)公益性行業(yè)科研專項基金(批準(zhǔn)號：201304215).

TP391

：A

：1671-5489(2015)03-0525-06