趙曉暉,方 裕,趙家敏,馬 艷

(1.國核電力規(guī)劃設(shè)計(jì)研究院,北京 100094;2.北京大學(xué)遙感與地理信息系統(tǒng)研究所,北京 100871）

一種基于GridGIS的空間負(fù)載平衡算法

趙曉暉1,方 裕2,趙家敏1,馬 艷1

(1.國核電力規(guī)劃設(shè)計(jì)研究院,北京 100094;2.北京大學(xué)遙感與地理信息系統(tǒng)研究所,北京 100871）

空間數(shù)據(jù)的廣泛應(yīng)用需要高效的架構(gòu)來管理,以增加空間數(shù)據(jù)的可用性。網(wǎng)格地理信息系統(tǒng)(GridGIS）支持快速的空間數(shù)據(jù)檢索,允許用戶在任何地方隨時(shí)透明地訪問數(shù)據(jù),容易引起空間負(fù)載失衡。該文提出一種基于GridGIS的空間負(fù)載平衡算法——TLB-Cho rd,采用動(dòng)態(tài)負(fù)載平衡思想,使用基于Chord算法的樹結(jié)構(gòu),實(shí)現(xiàn)了一個(gè)空間負(fù)載平衡模擬系統(tǒng),展示了TLB-Cho rd在GridGIS中更加適用于空間數(shù)據(jù)。

GIS;網(wǎng)格計(jì)算;GridGIS;負(fù)載平衡;Cho rd

0 引言

隨著 GIS的快速發(fā)展和廣泛應(yīng)用,空間數(shù)據(jù)的交互在分布式環(huán)境中更加頻繁,這需要有效的系統(tǒng)架構(gòu)來管理,以便更好地增加空間數(shù)據(jù)的可用性。網(wǎng)格計(jì)算借助網(wǎng)絡(luò)技術(shù),整合分散在不同地方的空閑資源,提供更好的、適于大規(guī)模資源的共享和協(xié)作,改善資源的利用率。傳統(tǒng)的 GIS技術(shù)結(jié)合網(wǎng)格計(jì)算,產(chǎn)生了網(wǎng)格地理信息系統(tǒng)(GridGIS）;GridGIS打破了空間的限制,可以跨平臺獲取空間數(shù)據(jù)。GridGIS中節(jié)點(diǎn)的連接方式會(huì)影響系統(tǒng)的執(zhí)行效率。如果系統(tǒng)只是簡單地連接各個(gè)節(jié)點(diǎn),不考慮各個(gè)節(jié)點(diǎn)的處理能力差異,則不能充分發(fā)揮 GridGIS優(yōu)勢,導(dǎo)致繁忙節(jié)點(diǎn)負(fù)載失衡,而空閑節(jié)點(diǎn)未被有效使用,最終引起整個(gè)系統(tǒng)的負(fù)載失衡和性能下降。因此,節(jié)點(diǎn)連接模式在 GridGIS的空間負(fù)載調(diào)控中不容忽視。

另一方面,GridGIS中的節(jié)點(diǎn)具有高動(dòng)態(tài)性,可以自由加入和退出,這使 GridGIS中如何有效地分配空間任務(wù)和利用空間資源變得至關(guān)重要。另外,如果分布在系統(tǒng)中的節(jié)點(diǎn)經(jīng)常超載或異常失效,那么存儲在其上的空間數(shù)據(jù)不能保證被高概率的訪問,就會(huì)影響GridGIS整體性能,甚至造成整個(gè)系統(tǒng)癱瘓。因此,空間負(fù)載平衡研究是 GridGIS中提高系統(tǒng)性能最為關(guān)鍵的問題。

本文借助經(jīng)典的Chord算法思想搭建節(jié)點(diǎn)的樹結(jié)構(gòu),結(jié)合GridGIS的特點(diǎn)和空間數(shù)據(jù)的特性,提出一種基于 GridGIS的空間負(fù)載平衡算法——TLBCho rd算法,實(shí)現(xiàn)空間負(fù)載在各個(gè)節(jié)點(diǎn)上的合理分配與空間數(shù)據(jù)共享,減少空間負(fù)載失衡現(xiàn)象的出現(xiàn),改善系統(tǒng)性能。

1 相關(guān)研究概述

1.1 GridGIS

網(wǎng)格是一種分布式計(jì)算基礎(chǔ)設(shè)施,能夠集成不同的資源,進(jìn)行資源共享,解決動(dòng)態(tài)、多機(jī)構(gòu)的虛擬組織中的問題[1-3];網(wǎng)格的出現(xiàn)加速了信息處理,隨之也在許多領(lǐng)域廣泛應(yīng)用,著名的網(wǎng)格項(xiàng)目有Info rmation Power Grid[4]、NEESgrid[5]和 SpaceGrid[6]。顯然,對于地理分散的復(fù)雜信息,網(wǎng)格提供了一種計(jì)算和數(shù)據(jù)管理的平臺。因此,當(dāng)網(wǎng)格在 GIS中應(yīng)用時(shí),GridGIS也就自然而然地產(chǎn)生了。

GridGIS使用網(wǎng)格技術(shù)構(gòu)建網(wǎng)格環(huán)境,借助在分布式GIS環(huán)境中的地理信息服務(wù)器和地理信息服務(wù),處理和共享空間信息,支持跨平臺的信息轉(zhuǎn)換,向用戶提供基本的網(wǎng)格系統(tǒng)服務(wù)和專業(yè)的地理服務(wù)。Wang等提出了一種 GridGIS軟件平臺體系架構(gòu)[7],包括5個(gè)層次:網(wǎng)格資源層、網(wǎng)格運(yùn)行環(huán)境層、網(wǎng)格系統(tǒng)服務(wù)層、領(lǐng)域支持層和應(yīng)用層。網(wǎng)格資源層處理和共享空間信息,允許在不同操作系統(tǒng)之間進(jìn)行資源交互;網(wǎng)格運(yùn)行環(huán)境層主要對網(wǎng)格中的專門服務(wù)進(jìn)行開發(fā)、部署、發(fā)布和環(huán)境應(yīng)用;網(wǎng)格系統(tǒng)服務(wù)層實(shí)現(xiàn)基本的網(wǎng)格系統(tǒng)服務(wù);領(lǐng)域支持層通過網(wǎng)格空間數(shù)據(jù)訪問和集成中間件提供方便的空間信息、數(shù)據(jù)處理和共享;應(yīng)用層提供嵌入式 GIS、網(wǎng)絡(luò)GIS、專業(yè) GIS和桌面 GIS的 GridGIS接口。Grid-GIS遵從網(wǎng)格標(biāo)準(zhǔn)和地理空間信息標(biāo)準(zhǔn),并使這些標(biāo)準(zhǔn)具有普適性。

1.2 空間負(fù)載平衡

雖然 GridGIS能夠有效地集成和管理空間數(shù)據(jù),但由于每個(gè)機(jī)器節(jié)點(diǎn)的處理速度各不相同,容易引起空間負(fù)載失衡問題。因此,空間負(fù)載平衡在GridGIS中至關(guān)重要,有助于提高系統(tǒng)性能,實(shí)現(xiàn)資源共享,增強(qiáng)延展性和可用性,減少時(shí)間消耗。

空間負(fù)載平衡算法結(jié)合空間信息的地理特性和常用的負(fù)載平衡思想,主要分為空間靜態(tài)負(fù)載平衡方法 (SSLBM）和空間動(dòng)態(tài)負(fù)載平衡方法(SDLBM）[8-10]。SSLBM假定系統(tǒng)中有P個(gè)節(jié)點(diǎn),將整個(gè)空間劃分為P個(gè)子部分(每個(gè)節(jié)點(diǎn)負(fù)責(zé)一個(gè)子部分）;然后,SSLBM把空間等分為T個(gè)矩形,使用Hash函數(shù)把每個(gè)矩形映射到各個(gè)節(jié)點(diǎn)上。這樣,某些分離的區(qū)域可能分配到同一個(gè)節(jié)點(diǎn)。SDLBM在系統(tǒng)運(yùn)行階段以自適應(yīng)的方式平衡節(jié)點(diǎn)上的負(fù)載,但不能解決節(jié)點(diǎn)異構(gòu)問題。

在GridGIS中,空間負(fù)載平衡算法需要處理異構(gòu)性、資源共享、可擴(kuò)展性、高延遲性和系統(tǒng)狀態(tài)的實(shí)時(shí)變更。GridGIS中相互連接的網(wǎng)絡(luò)有不同的平臺和完全不同的性能,而且提交到系統(tǒng)中的任務(wù)形式和規(guī)則不同,這些特征使空間負(fù)載平衡問題更加復(fù)雜。通常,有3個(gè)主要方法:重新劃分資源、可分負(fù)載理論(DL T）和預(yù)測[11]。重新劃分資源把問題域當(dāng)做一幅圖,通過負(fù)載的調(diào)配來減少子區(qū)域間的失衡和最小化切割邊界;DL T采用任意方式劃分負(fù)載,但以線性方式將負(fù)載分配到各個(gè)節(jié)點(diǎn)上;根據(jù)對未來估算的實(shí)際代價(jià)和通信代價(jià),預(yù)測方法建立性能預(yù)測模型。上述方法在某種程度上能夠改善系統(tǒng)性能,但不能有效解決空間負(fù)載失衡問題。因此,本文提出一種空間負(fù)載平衡算法,在 GridGIS中使用基于Cho rd的樹結(jié)構(gòu)來改善執(zhí)行性能和維持系統(tǒng)中的空間負(fù)載平衡狀態(tài)。

2 基于GridGIS的空間負(fù)載平衡算法

2.1 基于樹結(jié)構(gòu)的Chord算法

2.1.1 Chord[12]在大型網(wǎng)絡(luò)中,哈希函數(shù)廣泛應(yīng)用在映射和訪問分布式數(shù)據(jù)上。目前,有很多實(shí)現(xiàn)分布式哈希算法的方法,本文主要研究Chord算法。該算法是一種在分布式網(wǎng)絡(luò)中存儲關(guān)鍵值對的分布式查詢服務(wù),采用相容哈希函數(shù)的變體將關(guān)鍵值分配給 Cho rd服務(wù)器節(jié)點(diǎn),使負(fù)載易于達(dá)到平衡。Chord算法以分布式方法確定存儲在數(shù)據(jù)項(xiàng)中的節(jié)點(diǎn)。本文在第3章利用Cho rd算法思想連接不同的節(jié)點(diǎn)。

2.1.2 基于Cho rd的樹結(jié)構(gòu) 本文提出的算法體系結(jié)構(gòu)由3部分組成:虛擬根節(jié)點(diǎn)、中間任務(wù)管理器和普通節(jié)點(diǎn)。虛擬根節(jié)點(diǎn)具有唯一性,負(fù)責(zé)協(xié)調(diào)GridGIS中的相關(guān)空間任務(wù),并由任務(wù)管理器按順序選擇生成。從物理角度上看,虛擬根節(jié)點(diǎn)和任務(wù)管理器是相同的;從邏輯角度上看,虛擬根節(jié)點(diǎn)比任務(wù)管理器具有更多的權(quán)利。由于任務(wù)管理器是以樹結(jié)構(gòu)進(jìn)行連接,虛擬根節(jié)點(diǎn)最初由整體上具有最少負(fù)載的任務(wù)管理器擔(dān)當(dāng)。本文基于二叉樹的思想,以一種相對平均的方式劃分任務(wù),這樣,虛擬根節(jié)點(diǎn)有兩個(gè)子任務(wù)管理器節(jié)點(diǎn),并且這兩個(gè)節(jié)點(diǎn)具有在最佳距離內(nèi)的最輕負(fù)載量。一旦替換虛擬根節(jié)點(diǎn),樹中任務(wù)管理器節(jié)點(diǎn)的位置就會(huì)被自動(dòng)改變;但任務(wù)管理器節(jié)點(diǎn)的物理位置不會(huì)改變。如果虛擬根節(jié)點(diǎn)超載,它會(huì)發(fā)送消息給兩個(gè)子任務(wù)管理器節(jié)點(diǎn),第一個(gè)返回接收消息的子任務(wù)管理器節(jié)點(diǎn)將接管超載的工作量。如果虛擬根節(jié)點(diǎn)不能工作,首先發(fā)現(xiàn)這種狀況的子任務(wù)管理器節(jié)點(diǎn)就會(huì)成為虛擬根節(jié)點(diǎn)并通知其他任務(wù)管理器。虛擬根節(jié)點(diǎn)使用全局負(fù)載平衡思想,監(jiān)控、分配和調(diào)整每個(gè)任務(wù)管理器節(jié)點(diǎn)的負(fù)載。

任務(wù)管理器可以在任何時(shí)候加入和離開 Grid-GIS,提供空間負(fù)載信息和狀態(tài),依據(jù)普通節(jié)點(diǎn)所處的實(shí)際地理位置信息,任務(wù)管理器劃分并選擇歸屬于自己的普通節(jié)點(diǎn)。同一個(gè)任務(wù)管理器中節(jié)點(diǎn)間的距離小于不同任務(wù)管理器中的節(jié)點(diǎn)距離,這樣,一旦某個(gè)任務(wù)管理器出現(xiàn)負(fù)載失衡,不會(huì)引起整個(gè)系統(tǒng)范圍內(nèi)的網(wǎng)絡(luò)擁塞,避免了單點(diǎn)故障。在任務(wù)管理器中的空間資源副本信息只存儲在同一個(gè)任務(wù)管理器下的節(jié)點(diǎn)中,即使有一個(gè)節(jié)點(diǎn)失靈,同一個(gè)任務(wù)管理器下的其他節(jié)點(diǎn)仍然可以正常工作。

所有普通節(jié)點(diǎn)的連接是以一種類似Chord結(jié)構(gòu)的形式進(jìn)行,每個(gè)普通節(jié)點(diǎn)的空間副本存儲在其他臨近節(jié)點(diǎn)上,而且普通節(jié)點(diǎn)間的距離小于某個(gè)閾值。Chord算法將普通節(jié)點(diǎn)組成一個(gè)環(huán)狀,使空間數(shù)據(jù)可以快速地查詢和檢索,提高性能和效率。當(dāng)某個(gè)普通節(jié)點(diǎn)超載時(shí),它能使用Cho rd中的關(guān)鍵字發(fā)現(xiàn)有副本的其他普通節(jié)點(diǎn),并轉(zhuǎn)換當(dāng)前任務(wù)到這些節(jié)點(diǎn)上。依據(jù)普通節(jié)點(diǎn)的性能和數(shù)據(jù)量,任意一個(gè)普通節(jié)點(diǎn)將具有其他普通節(jié)點(diǎn)的部分副本或整個(gè)副本。每個(gè)普通節(jié)點(diǎn)都有自己的前趨節(jié)點(diǎn)或后繼節(jié)點(diǎn)。當(dāng)某個(gè)普通節(jié)點(diǎn)的負(fù)載超過其最大負(fù)載值時(shí),其前趨節(jié)點(diǎn)將未完成的任務(wù)轉(zhuǎn)換到另一個(gè)普通節(jié)點(diǎn),而其后繼節(jié)點(diǎn)向與其連接的其他普通節(jié)點(diǎn)廣播超載消息。對于矢量數(shù)據(jù),本文考慮普通節(jié)點(diǎn)所在系統(tǒng)的性能;對于柵格數(shù)據(jù),本文把實(shí)際的地理圖形分割和合并作為主要因素。

虛擬根節(jié)點(diǎn)、任務(wù)管理器和普通節(jié)點(diǎn)都有自己的記錄表,使用哈希函數(shù)來映射這些節(jié)點(diǎn)的標(biāo)識。虛擬根節(jié)點(diǎn)的記錄表有相關(guān)的地理信息和CPU信息以及任務(wù)管理器的摘要信息;任務(wù)管理器的記錄表存儲各自內(nèi)部普通節(jié)點(diǎn)的相關(guān)內(nèi)容;普通節(jié)點(diǎn)的記錄表包括其負(fù)載信息、副本信息、系統(tǒng)性能等。如果系統(tǒng)發(fā)生負(fù)載失衡,系統(tǒng)能夠及時(shí)遷移任務(wù),盡可能減少系統(tǒng)宕機(jī)時(shí)間。

2.2 TLB-Cho rd算法

依照上節(jié)提出的結(jié)構(gòu),基于Chord的樹結(jié)構(gòu)負(fù)載平衡算法(TLB-Chord）劃分為3個(gè)負(fù)載平衡層級。1）在普通節(jié)點(diǎn)層,根據(jù)當(dāng)前負(fù)載值,每個(gè)普通節(jié)點(diǎn)決定是否調(diào)用負(fù)載平衡操作。普通節(jié)點(diǎn)會(huì)在給定的時(shí)間間隔內(nèi)自動(dòng)更新負(fù)載信息,監(jiān)控是否出現(xiàn)負(fù)載失衡;一旦負(fù)載失衡出現(xiàn),普通節(jié)點(diǎn)或者發(fā)起局部的負(fù)載平衡算法,或者向其任務(wù)管理器通知當(dāng)前超載信息。2）在任務(wù)管理器層,負(fù)載平衡只關(guān)注任務(wù)管理器。只有當(dāng)普通節(jié)點(diǎn)層負(fù)載失衡時(shí),才會(huì)使用任務(wù)管理器層的負(fù)載平衡算法。任務(wù)管理器需要維護(hù)其內(nèi)部的普通節(jié)點(diǎn),并和其他任務(wù)管理器進(jìn)行交互。由于每個(gè)任務(wù)管理器了解在其控制區(qū)域中的全局狀態(tài),任務(wù)管理器可以均分在其內(nèi)部的超載量。3）只有當(dāng)任務(wù)管理器層的負(fù)載平衡算法失敗時(shí),系統(tǒng)才會(huì)執(zhí)行虛擬根節(jié)點(diǎn)層的負(fù)載平衡算法。虛擬根節(jié)點(diǎn)是一個(gè)虛擬的任務(wù)管理器,它的參數(shù)和任務(wù)管理器的參數(shù)一致,減少了 TLB-Cho rd算法程序的參數(shù)量和復(fù)雜性,并具有任務(wù)管理器信息和全局信息。在虛擬根節(jié)點(diǎn)層,本文只關(guān)注系統(tǒng)全局的記錄表。

TLB-Cho rd算法在用戶要求或給定的時(shí)間間隔內(nèi)執(zhí)行,其采用動(dòng)態(tài)負(fù)載平衡思想,結(jié)合了局部負(fù)載平衡算法和全局負(fù)載平衡算法。TLB-Chord算法按照普通節(jié)點(diǎn)內(nèi)、任務(wù)管理器內(nèi)、全局的順序制定局部負(fù)載平衡的優(yōu)先級,有效降低了普通節(jié)點(diǎn)間和任務(wù)管理器之間的信息量,減少了系統(tǒng)開銷。TLBChord算法程序描述如下:

3 實(shí)驗(yàn)分析

本文使用 TLB-Chord算法,在小規(guī)模 GridGIS測試環(huán)境中構(gòu)建空間負(fù)載平衡模擬系統(tǒng)[13,14];該模擬系統(tǒng)使用10臺計(jì)算機(jī)(7臺是普通節(jié)點(diǎn),3臺是任務(wù)管理器）,這些計(jì)算機(jī)具有相同的存儲容量,并且都安裝了Globus Toolkit 4.0.5。7個(gè)普通節(jié)點(diǎn)標(biāo)號為1～7,3個(gè)任務(wù)管理器依次命名為A、B、C。本文設(shè)定任務(wù)管理器A包括普通節(jié)點(diǎn)1、2,B包括普通節(jié)點(diǎn)3、4、5、6,C包括普通節(jié)點(diǎn)7。任務(wù)管理器C具有最少的負(fù)載,成為虛擬根節(jié)點(diǎn)。TLB-Cho rd算法被封裝為網(wǎng)格服務(wù)來解決空間負(fù)載失衡問題。

本文以河流分布作為地理測試應(yīng)用,并將該河流分布的空間數(shù)據(jù)均分為7個(gè)連續(xù)區(qū)域。本文采用節(jié)點(diǎn)常規(guī)連接方式和 TLB-Cho rd算法中節(jié)點(diǎn)連接方式,進(jìn)行對比實(shí)驗(yàn),并不斷迭代這個(gè)實(shí)驗(yàn)10次以上,以便獲取可靠的測試結(jié)果。本文將節(jié)點(diǎn)常規(guī)連接方式的算法稱為普通算法,其系統(tǒng)中的10個(gè)節(jié)點(diǎn)按照自然順序依次連接起來組成一個(gè)環(huán)形,7個(gè)連續(xù)區(qū)域依次分配給普通算法中的節(jié)點(diǎn)1～7,而節(jié)點(diǎn)8、9和10為空閑節(jié)點(diǎn)。TLB-Chord算法將7個(gè)連續(xù)區(qū)域也依次分配給上述的7個(gè)普通節(jié)點(diǎn)。設(shè)定普通算法和 TLB-Cho rd算法中的7個(gè)節(jié)點(diǎn)都分別具有其他節(jié)點(diǎn)的全部副本(表1）。在用戶不斷查詢后,一些區(qū)域變成熱點(diǎn)區(qū)域,空間負(fù)載失衡出現(xiàn)。假設(shè)兩種算法中同步出現(xiàn)節(jié)點(diǎn)5超載,需要遷移節(jié)點(diǎn)5上的空間任務(wù)或空間數(shù)據(jù),但此時(shí)節(jié)點(diǎn)3、4、6、7也已經(jīng)滿負(fù)荷運(yùn)行,不能再接受其他空間任務(wù)和空間數(shù)據(jù)。

表1 各節(jié)點(diǎn)副本分配Table 1 The duplicating partition of peers

在這種情況下,普通算法通常通過消息傳遞機(jī)制,由節(jié)點(diǎn)5向其相鄰節(jié)點(diǎn)傳遞超載消息,請求遷移空間任務(wù)或空間數(shù)據(jù),但由于其相鄰節(jié)點(diǎn)4、6也是滿負(fù)荷運(yùn)行,它們又發(fā)消息給其鄰居節(jié)點(diǎn)3、7;同樣,節(jié)點(diǎn)3、7再向其相鄰節(jié)點(diǎn)發(fā)消息。此時(shí),節(jié)點(diǎn)2返回消息給節(jié)點(diǎn)3,告知具有節(jié)點(diǎn)5的空間數(shù)據(jù)副本,并可以接受節(jié)點(diǎn)5的空間任務(wù)遷移;節(jié)點(diǎn)8返回消息給節(jié)點(diǎn)7,告知可以接受節(jié)點(diǎn)5的空間數(shù)據(jù)遷移。節(jié)點(diǎn)3和節(jié)點(diǎn)7再把消息按節(jié)點(diǎn)5的請求路徑返回給節(jié)點(diǎn)5,節(jié)點(diǎn)5決定選擇遷移到節(jié)點(diǎn)2,還是遷移到節(jié)點(diǎn)8。由于空間任務(wù)的遷移量遠(yuǎn)小于空間數(shù)據(jù)的遷移量,節(jié)點(diǎn)5再按照請求路徑,發(fā)出空間任務(wù)遷移消息到節(jié)點(diǎn)2,完成遷移操作。

在TLB-Chord算法中,每個(gè)節(jié)點(diǎn)可以通過查詢Cho rd關(guān)鍵字獲取具有存儲自己副本的節(jié)點(diǎn)信息。因此,當(dāng)TLB-Chord算法中節(jié)點(diǎn)5出現(xiàn)超載時(shí),節(jié)點(diǎn)5通過相鄰節(jié)點(diǎn)存儲的Chord關(guān)鍵字,直接找到節(jié)點(diǎn)2具有自己的空間數(shù)據(jù)副本,然后向節(jié)點(diǎn)2請求空間任務(wù)遷移;節(jié)點(diǎn)2返回接收消息給節(jié)點(diǎn)5,完成遷移操作。

盡管兩種算法都采用了空間任務(wù)遷移且遷移代價(jià)相同,但其通信代價(jià)和時(shí)間開銷差別很大。本文在帶寬為2 M的局域網(wǎng)中進(jìn)行模擬測試,普通算法和TLB-Chord算法的網(wǎng)絡(luò)測試環(huán)境和空間測試數(shù)據(jù)都相同,采用空間任務(wù)遷移前的平均響應(yīng)時(shí)間作為評價(jià)因素(圖1）。本文中的空間任務(wù)遷移前的平均響應(yīng)時(shí)間是指節(jié)點(diǎn)5接收到遷移目標(biāo)節(jié)點(diǎn)2所需的時(shí)間開銷。從測試結(jié)果可以看出,在單個(gè)節(jié)點(diǎn)進(jìn)行空間任務(wù)遷移時(shí),TLB-Cho rd算法的執(zhí)行效率比普通算法的執(zhí)行效率好,即使在傳遞相同的消息數(shù)量時(shí),TLB-Chord算法也比普通算法的時(shí)間開銷少。另外,在普通算法進(jìn)行節(jié)點(diǎn)5的遷移請求消息傳遞過程中,如果節(jié)點(diǎn)3、4、6和7中的某個(gè)節(jié)點(diǎn)也發(fā)生超載,就會(huì)引起系統(tǒng)擁塞,甚至系統(tǒng)癱瘓。然而, TLB-Cho rd算法由于采用Cho rd算法的節(jié)點(diǎn)連接方式和三級調(diào)控負(fù)載算法,可以及時(shí)處理節(jié)點(diǎn)超載狀況,減少負(fù)載失衡,盡可能地避免系統(tǒng)擁塞,改善系統(tǒng)性能。

圖1 時(shí)間開銷比較Fig.1 The comparison of time costs

4 結(jié)語

本文提出了基于 GridGIS的空間負(fù)載平衡算法——TLB-Chord,該算法采用混合結(jié)構(gòu),結(jié)合了基于樹的粗粒度和基于Chord算法的細(xì)粒度的負(fù)載平衡策略以及消息傳遞機(jī)制,減少了系統(tǒng)的停機(jī)時(shí)間,提高了處理空間數(shù)據(jù)的系統(tǒng)性能。本文構(gòu)建了基于TLB-Cho rd算法的空間負(fù)載平衡模擬系統(tǒng),展示了TLB-Chord算法更適于GridGIS中的空間數(shù)據(jù)。

[1] FOSTER I.What is the Grid?A three point checklist[J].Grid Today,2002,1(6）:32-36.

[2] FOSTER I,KESSELMAN C,TUECKE S.The anatomy of the Grid:Enabling scalable virtual organizations[J].Supercomputer Applications,2001,5(3）:200-222.

[3] FOSTER I,KESSELMAN C,N ICK J,et al.The physiology of the Grid:An open Grid services architecture for distributed systems integration[EB/OL].Open Grid Service Infrastructure WG,Global Grid Forum,2002.http://www.globus.org/alliance/publications/papers/ogsa.pdf.2010-12-31.

[4] EIGENMANN R,VOSSJ M.Towards a compilation paradigm for computational applications on the information power Grid [J].Mathematics and Computers in Simulation,2000,54(4-5）:307-320.

[5] SPENCERB,FINHOLT T,FOSTER I,etal.Neesgrid:A distributed collaboratory for advanced earthquake engineering experiment and simulation[EB/OL].Proceedings of the 13th World Conference on Earthquake Engineering,http://citeseerx.ist. psu.edu/view doc/dow nload doi=10.1.1.2.6552&rep= rep1&type=pdf.2010-12-31.

[6] ZHUGE H.Resource space Grid:Model,method and platform[J]. Concurrency and Computation:Practice and Experience,2004, 16(14）:1385-1413.

[7] WANG J Q,XUE Y,JIANG Y X,et al.Design of GridGIS architecture[A].ISPA 2006[C].2006,LNCS 4331,628-636.

[8] YAN K Q,WANG SC,CHANGC P,et al.A hybrid load balancing policy underlying Grid computing environment[J].Computer Standards&Interfaces,2007,29(2）:161-173.

[9] AN IRBAN M,GODA K,KITSUREGAWA M.Effective loadbalancing viamigration and replication in spatial grids[J].Database and Expert System Applications,2003,2736:202-211.

[10] 趙曉暉,方裕,趙家敏,等.空間負(fù)載平衡探討[J].地理與地理信息科學(xué),2011,27(3）:7-11.

[11] L I YW,LAN Z L.A survey of load balancing in Grid computing[A].CIS 2004[C].2004.280-285.

[12] STOCIA I,MORRIS R,KARGER D,et al.Chord:A scalable Peer-to-Peer lookup service for internet app lications[A].ACM SIGCOMM 2001[C].2001.149-160.

[13] 方金云,何建邦.網(wǎng)格GIS體系結(jié)構(gòu)及其實(shí)現(xiàn)技術(shù)[J].地球信息科學(xué),2002(4）:36-42.

[14] 阮曉青,周義倉.數(shù)學(xué)建模引論[M].北京:高等教育出版社, 2005.

A Load Balancing Algorithm for Spatial Data in GridGIS ZHAO Xiao-hui1,FANG Yu2,ZHAO Jia-min1,MA Yan1

(1.State N uclear Electric Pow er Planning Design&Research Institute,Beijing 100094;
2.Institute of Remote Sensing&GIS,Peking University,Beijing 100871,China）

The w ide app lication of spatial data needs an efficient framewo rk to manage them and increase the availability of spatial data in geographical applications.The emergence of Grid computing coup led w ith Geographic Information System s(GIS） p rovides an excellent framework:GridGIS,w hich supports fast spatial data retrieval and allow s its users to transparently access data from anyw here at any time.GridGIS also causes spatial load unbalancing.This paper p resents a new load balancing algorithm(TLB-Chord）,w hich adop ts the tree structure based on the classical Cho rd algo rithm to imp rove system perfo rmance and increase the availability of spatial data.First,the relative researchesof GridGISand spatial load balancing are summarized.Secondly,the special thoughtsof the TLB-Chord algorithm are given.The paper discusses how to construct the tree structure based on Cho rd,divides the peers in the system into three kinds:the only virtual root peer,some task managers and many no rmal peers,and gives each kind of peers how to wo rk.Then,it is introduced that the TLB-Cho rd algo rithm has three levels to imp lement the spatial load balancing:the basic level composed by no rmal peers,themiddle level including task managers and the high level having the root peer.The algo rithm begins from the basic level.Once it fails to adjust the load,the algorithm w ill perfo rm themiddle level.If themiddle level also fails,the algorithm w ill adop ts the high level.Thirdly,a spatial load balancing simulation system is given and the TLB-algorithm(peers connected in Chord based on the tree structure）and the common algo rithm (peers connected in the physical o rder based on a ring structure）are compared through the testing environment in GridGIS, w hich uses the iterative way,and show s the TLB-Cho rd algorithm can imp rove the system performance better.

Geographic Info rmation System s;Grid computing;GridGIS;load balancing;Chord

P208

A

1672-0504(2011）04-0036-05

2011-02-22;

2011-04-27

趙曉暉(1979-）,女,博士研究生,研究方向?yàn)榭臻g分布式計(jì)算。E-mail:zxhsmile@gmail.com