基于Grid GIS的空間負載平衡遷移算法研究

趙曉暉 張飛舟2

（1.國核電力規劃設計研究院，北京100095；2.北京大學遙感與地理信息系統研究所，北京100871）

1 引言

隨著信息技術、衛星遙感遙測技術、地理信息系統（GIS）的飛速發展，利用GIS為勘察到的各類信息建立數據庫，搭建電力線路系統的信息應用平臺，可以實現對這些龐大信息進行高效管理、深度挖掘、綜合分析和廣泛應用，優化電力線路的路徑選取和桿塔位的設計，縮短電力線路工程的勘測設計工期，減少電力線路工程投資，提升項目的復用率，有效促進電力勘測設計中測量設備和測量手段的完善，極大提高電力工程勘察設計技術水平。

電力勘察設計信息系統中的信息類型多樣，海量數據存儲復雜，為了實現對空間數據的快速查詢、多維分析、清晰展示和各種專題地圖的制圖、查找、分析、輸出等一系列功能，需要電力勘察設計信息系統具有良好的系統性能［1］。然而，負載平衡設備費用較為昂貴，為了有效控制企業硬件投資費用，達到降本增效的目的，本文提出利用軟件方法來改善系統性能。

網格地理信息系統（Grid GIS）是利用網格技術將多臺地理信息服務器構建成一個網絡環境，實現地理信息網格調度、負載平衡和快速的地理信息服務，已經成為GIS新的發展方向。同時，專題地圖的劃分角度多種多樣，劃分粒度不斷精細，多專題地圖的空間疊合操作也日益頻繁。例如，輸變電線路上的桿塔位設計，在綜合考慮該輸變電線路區域的水系、植被、交通網、境界線、地貌等地理要素的情況下，需要對地質圖、水文圖、土壤圖等多個專題地圖進行疊加分析。這些專題地圖存儲在系統中的不同節點上，需要空間負載平衡方案確定在哪些節點上進行疊合哪些專題地圖，是否需要遷移專題地圖，以及如何選擇遷移的目標節點以便能夠快速有效地進行相應的空間分析和空間操作等。盡管Grid GIS不斷地調控空間負載，但由于系統中節點加入、退出的隨意性和多專題地圖之間的高交互率，系統經常面臨空間負載的再分配問題。因此，如何有效地處理好多專題地圖的相關空間操作，保證Grid GIS中的空間負載合理調配和有效遷移，是空間負載平衡研究的難點和重點。

本文以專題地圖作為空間負載的研究對象，緊密結合空間數據存儲，提供以專題地圖為基礎的更實用的空間服務。同時，根據不同的空間負載狀況、Grid GIS環境的動態多變、空間數據的復雜多變和專題地圖的交互多變等空間特性，提出了基于多專題地圖的空間負載平衡遷移算法，分析了空間負載遷移條件和子算法調用的優先級，并詳細描述了算法程序。通過實驗模擬迭代測試，給出空間負載平衡遷移算法的相關性能分析，促進電力勘測設計信息系統性能的提高。

2 相關研究概述

2.1 Grid GIS

網格地理信息系統（Grid GIS）是使用網格技術，借助地理信息服務器來構建網格環境，實現在分布式GIS中網格調度、資源管理和地理信息服務［2-5］。GridGIS有效地解決了空間數據的多源性、海量性、異構性和時空性等問題，在廣域范圍內無縫集成空間數據，協同處理各種空間計算和空間分析任務，全面共享空間數據，支持跨平臺的數據轉換，向用戶提供基本的網格系統服務和專門的地理服務。

2.2 空間負載平衡

空間負載平衡算法結合空間信息的地理特性，來合理和透明地分配系統中的空間負載，提高處理器的利用率和系統的執行效率，以達到系統綜合性能最優，主要分為空間靜態負載平衡方法和空間動態負載平衡方法［6-8］。空間數據自身的復雜性和專題地圖劃分粒度的細化日益增加GridGIS處理空間數據的難度，使系統中的一些節點處于超載，一些節點處于空閑，不能很好的利用系統中的有效空閑資源。這就需要在Grid GIS中使用空間負載平衡進行合理調度和分配資源。

3 基于GridGIS的空間負載平衡遷移算法

在GridGIS系統運行過程中，節點根據自己的空間負載狀況進行決策。本文劃分空間負載狀況為輕載、正常和超載三個狀態，并假定所有節點都是正常加入和正常離開系統。但是，由于空間數據的特殊性、GridGIS環境的高動態性和專題地圖的多交互性等復雜因素，導致GridGIS中的節點會發生空間負載超載的狀況，需要進行空間負載平衡遷移。本文依據不同的空間負載狀況提出基于Grid GIS的空間負載平衡算法，分為空間任務遷移算法、空間數據遷移算法、空間計算遷移算法和空間環境遷移算法四個子算法。在綜合考慮時間開銷、內存開銷、磁盤I／O狀況變化和專題地圖數據變化情況等方面對負載遷移的影響，本文認為在進行負載遷移時，對四種空間負載遷移子算法執行的優先順序遵循先空間任務遷移，再空間數據遷移，再空間計算遷移，最后空間環境遷移。

3.1 基于GridGIS的空間任務遷移算法

當節點發現自己超載時，它首先會發送超載消息，并請求轉移其上的空間任務，主動調用空間任務遷移決策。空間任務遷移算法的程序描述如下：

migrateSpatiaITask O

｛

／*初始化節點空間任務隊列*／

queue qtask_do←null；／／正在執行的空間任務隊列

queue qtask_wait←null；／／正在等待的空間任務隊列

cost←δ；／／節點空間代價量（即節點上正在執行的專題圖層數據量和該節點所承受的最大空間負載量的比值）

qmax←umax；／／節點能接受的空間任務數

／*更新節點空間任務隊列*／

num←size（qtask_do）+size（qtask_wait）；

if arrivc（ncw_task）thcn／／新空間任務到達

if（num=o）then

qtask_do add（new_task）；

if（num＜qmax）then

if（cos＜50%）then

qtask_do.add（new_task）；

else

qtask_wait.add（new_task）；

clsc

send messages to the directory central node；

refuse to receive new spatial task until num＜qmax；

if finish（task）then

qtask do remove（task）；／／空 間 任 務 完 成離開

／*超載申請空間任務遷移*／

if（load_state≥I0）then

send“overload”message to the directory central node；

rcccivc the abstract information of undcrload nodcs；

compute spatial cost gains among underload nodes；

record those underload nodes satisfying conditions of spatioal cost gains；

Io cate Load O；

if（exist Replica）then

send the task to underload nodes；

else

migrateSpatialDataO；／／調用空間數據遷移算法

｝

3.2 基于GridGIS的空間數據遷移算法

在節點發現自己超載，無法執行空間任務遷移，必須執行空間數據遷移，主要解決如下幾種典型情況下的數據遷移：

（1）超載節點上的專題地圖數據具有多個空間副本，但副本所在節點或者不能再接受其他空間任務，或者也同樣處于超載狀態；

（2）超載節點上的專題地圖數據沒有空間副本存在；

（3）節點上的專題地圖數據沒有空間副本存在，但節點由于某種原因正在申請離開。

在執行空間數據遷移算法時，需要遷移專題地圖和與該專題地圖相關的空間任務。如果一個節點上的幾個專題地圖同時進行空間數據遷移，當遷移的目標節點相同時，只需要順序執行每個專題地圖的遷移；當遷移的目標節點不同時，采用多線程機制來進行遷移。如果不同節點上的幾個專題地圖同時遷移到同一個目標節點，那么在目標節點上也執行多線程機制來接收空間數據。空間數據遷移算法的程序描述如下：

migrateSpatiaITask O

｛

／*初始化相關信息*／

／／節點專題地圖信息表，m表示節點上專題地圖總數

array［m］［］larer_info←layer_id，content，datatype，mbr，isReplica，replicanum；

／／目錄中心節點的節點信息表，n表示系統中的節點總數

／／目錄中心節點是記錄系統中各個節點的一些重要參數信息

array［n］［］node_info←node_id，costclass，mbr，isReplica，replicanum；

／／目錄中心節點的輕載節點表，k表示系統中的輕載節點總數

array［k］［］underload_node_info←node_id；

／／節點正在執行遷移的專題地圖數

migrate Layer Num←0；

／／*空間數據遷移*／

if（layer_info.isReplica=false）then

send“query”messages to the directory central node；

get underload nodes；

compute spatial cost gains among underload nodes；

record those underloadnodes satisfying conditions of spatial cost gains；

locateLoad O；

if（migrate Layer Num=0）then

migrate the layer，

else if（migrateLayer Num=1）then

create multithread and migrate the layer，

else

join multithread and migrate the layer，

else

send“query replicas”messages to the directory central node；

get replica nodes；

compute spatial cost gains among replica nodes；

record those replica nodes satisfying conditions of spatial cost gains；

locateLoad O；

if（migrate Layer Num=0）then

migrate the layer，

else if（migrateLayer Num=1）then

create multithread and migrate the layer，

else

join multithread and migrate the layer，

｝

在進行空間數據遷移時，由于受到帶寬的影響，有些專題地圖不能一次傳輸到遷移目標節點，需要切分專題地圖。為了切分處理盡可能地簡單化，本文采用規則切分的方法分割專題地圖，保證切分后的子專題地圖邊界是規則的。同時，為了能夠統一處理不同的幾何形狀，本文采用最小外包矩形（MBR）來表示每個專題地圖和切分后子專題地圖的空間范圍，有利于在空間數據遷移傳輸完成之后，合并子專題地圖。

3.3 基于Grid GIS的空間計算遷移算法

隨著空間計算的執行使空間負載狀況變壞，節點需要執行空間計算遷移。在Grid GIS中，涉及到的空間計算類型多種多樣，有些空間計算非常復雜。本文主要研究針對空間疊加分析相關的空間計算遷移，而對于其它類型的空間分析（如緩沖區分析、網絡分析、數字高程模型分析等）相關的空間計算遷移不進行討論。但是，由于專題地圖疊加分析所進行的空間計算，造成節點空間負載變化非常復雜，故本文只考慮在進行疊加分析的過程中，只有一個節點出現超載現象，其他參與執行的節點上的空間負載狀況良好，忽略專題地圖的空間數據類型差異和不同空間數據類型在進行疊加分析處理的差異。

本文將一個節點在疊加分析的過程中出現超載現象時的專題地圖狀況分為如下兩類：

（1）需要的多個專題地圖恰好都在一個節點A上，但此時節點A的空間負載狀況隨著疊加分析的進行，出現超載；

（2）需要的多個專題地圖分散在不同的節點上，并且在節點A上的專題地圖（至少是兩個專題地圖）參與執行疊加操作，但此時隨著疊加分析的進行，節點A出現空間負載超載。

對于第（1）種情況，超載節點要先查看參與執行的幾個專題地圖是否存在冗余空間副本，以及此時冗余空間副本所在節點的空間負載狀況，然后決定遷移方案。

對于第（2）種情況，本文設定其他參與執行疊加操作的節點都沒有超載節點上的任何一個專題地圖。超載節點要先查看共同參與執行疊加操作的其他節點是否可以接受它的空間計算遷移。如果其他節點中有多個節點可以接受空間計算遷移，那么超載節點選擇當前空間負載最小的節點作為遷移目標節點，然后調用空間負載平衡定位算法，確定該遷移目標節點的位置，只執行空間數據遷移。如果其他節點都不能接受空間計算遷移，那么超載節點會向目錄中心節點請求空間計算遷移，并優先查找是否具有遷移專題地圖副本的可行節點。如果沒有可行的副本節點，超載節點會向目錄中心節點查詢當前空間負載最小的輕載節點。如果有可行的副本節點，選取原則與第（1）種情況相同。

空間計算遷移算法的程序描述如下：

migrateSpatialComputeO

｛

1.／*初始化相關信息*／

2.／／要遷移的m個專題地圖

3.array［m］layer←layer1_id，layer2_id，...，layerm_id；

4.／／目錄中心節點返回的n個可行副本節點

5.array［n］［］replicanode_info←node_id，layer_id，node_load_state；

6.／／目錄中心節點的輕載節點表

7.array［k］［］underload_node_info←node_id，node_load_state；

8.／／參與執行空間計算的s個節點

9.array［s］performnode←node1_id，node2_id，...，nodes_id，；

10.／*空間計算遷移*／

11.if（all the migrating layers in the overload node）then

12.if（exist replicas of the migrating layers）then

13.send messages to the directory central node；

14.get replicanode_info；

15.if（replica node accepts new tasks）then

16.choose replica node having minimum node_load_state in replica_node_info according to the replica nodes priority；

17.locateLoad O；

18.migrate spatial computing content；

19.else

20.send messages to the directory central node；

21.get a underload node having minimum node_load_state；

22.locateLoad O；

23.migrate spatial computing content；

24.else

25.get a underload node having minimum node_load_state；

26.locate LoadeO；

27.migrate spatial computing content；

28.else

29.if（perform node accepts new tasks）then

30.locateLoad O；

31.migrateSpatiaIDataO；

32.else

33.perform the codes between line 12 and line 27；

｝

3.4 基于GridGIS的空間環境遷移算法

4 實驗分析

當某個節點發現自己處于超載狀況或者該節點要離開系統，它會請求進行空間負載遷移，但此時系統中輕載節點和該節點的運行環境是異構的。同時，在該節點上正在執行的和待處理的空間操作都是依賴于它的運行環境，導致即使輕載節點具有該節點上專題地圖的副本，也不能執行空間操作，需要進行空間環境遷移。很顯然，空間環境遷移的開銷代價高，容易引起一致性問題。本文只關注與空間操作相關的軟件宿主環境，而且認為相關聯的所有軟件程序具有良好的可移植性和平臺無關性。

在進行空間環境遷移時，本文把空間操作相關的軟件宿主環境、空間計算程序、專題地圖數據和相關空間計算的中間結果以整體打包壓縮方式進行遷移。由于遷移量較大和帶寬受限使遷移不能一次傳輸完成，本文將壓縮后的空間遷移負載進行切塊，塊的大小選擇依據具體的帶寬情況，但要保證每塊可以一次遷移完成。另一方面，本文不考慮遷移目標節點是否具有該節點的專題地圖副本，減少請求任務完成的等待時間。然而，在遷移目標節點執行完該空間操作后，它會刪除這些遷移負載來釋放自己被占用的空間資源。因此，在刪除之前，遷移目標節點會先確定是否有相關的遷移負載副本存在。如果副本存在，那么它就立即執行刪除操作；否則，它選擇暫時保留，當該節點輕載或者重新加入系統后，再執行刪除操作。空間環境遷移算法的程序描述如下：

mograteSpatoa；Emvorpment O

｛

／*初始化相關信息*／

／／目錄中心節點的輕載節點表，k表示系統中的輕載節點總數

array［k］［］underload_node_info←node_id，node_load_state，environmenttype；

／／申請遷移的節點

array［］migrate_node_node_id，node_load_state，environmenttype；

／*空間環境遷移*／

if（migrate_node.environmenttype≠underload_node_info.environmenttype）then

choose the underload node which has the minimum node_load_state；

locateLoadO；

migrate all the migrating contents in the type of compressed packages；

｝

Nebula系統是一個網格空間計算任務處理系統，能夠協同處理海量的空間信息，實現空間計算能力的有效分配和管理，提出了基于域的網格節點架構［9］。SLBM系統是為Nebula系統提供性能監測，合理調配Nebula中的空間負載。本文提出了一個基于Nebula的空間負載平衡遷移模擬系統（SLBM），模擬了Nebula中一個節點在t時刻出現超載，需要SLBM系統執行空間數據遷移的過程，給出模擬測試的相關性能分析。

表1 t時刻的節點模擬信息

空間數據遷移模擬測試選取10個同構節點、6個專題地圖、3個域，采用多次重復迭代的方法進行實驗。假設節點的空間負載狀況是由節點空間代價量所決定的。在t時刻，節點模擬信息如表1所示，專題地圖模擬信息如表2所示，系統模擬域如圖1所示。對于專題地圖模擬信息中空間數據量級別v，本文假設為10個級別（用正整數表示），每10M為一個級別。

表2 t時刻的專題地圖模擬信息

假設專題地圖D引起節點n9超載，SLBM系統執行如下操作：

（1）節點n9向其所在域I目錄報告超載，請求執行空間任務task_a遷移；

（2）域I目錄發現域I內沒有D的副本后，把節點n9的空間任務遷移請求轉發給系統目錄，同時通知節點n9等待接收系統目錄的查詢返回結果；

（3）系統目錄查詢專題地圖信息表（見表1），查找到D的副本節點n8和n6存在，再在節點信息表（見表2）中，查看節點n8和n6的當前空間負載狀況，發現節點n6雖然沒有超載，但已經滿負荷運行，不能再接受新的空間任務；同時，發現節點n8也不能再接受新的空間任務；然后，通知節點n9不能執行空間任務遷移；

（4）節點n9再次向域I發出空間數據遷移請求；

（5）域I目錄發現在域內節點中只有節點n1可以執行，把節點n1的IP地址傳給節點n9；

（6）節點n9主動連接節點n1，執行空間數據遷移操作。

在進行空間數據遷移時，網絡帶寬是影響空間數據傳輸速率的關鍵因素之一。因此，本文模擬測試在帶寬為2M的局域網和帶寬為100M的廣域網兩種情況下，單節點接收遷移專題地圖D的傳輸時間，并且假定其他節點的運行狀況不影響帶寬。在帶寬一定和單節點接收的情況下，本文模擬測試了遷移空間數據量與傳輸時間的關系，如圖1所示。

從圖1中可以看到，在進行空間數據遷移時，帶寬越大，遷移空間數據的傳輸時間越少。因此，當空間數據遷移量小于20M時，本文認為局域網和廣域網都可以執行空間遷移任務；但是，當空間數據遷移量大于20M時，本文認為廣域網執行空間遷移任務明顯優于局域網。為了更好地執行空間遷移任務，應盡可能地增大網絡帶寬。

此外，當多個節點接收空間數據遷移時，由于帶寬需要同時分配給多個節點，無論帶寬采取何種分配方式，每個節點平均能夠占有的帶寬就會大幅減少。例如，在帶寬為100M的網絡中，如果有10個節點同時接收空間數據遷移，那么每個節點平均獲取的帶寬為10M，遷移空間數據的傳輸時間就會增大10倍。很顯然，空間數據遷移效率降低較大。特別是，如果空間數據遷移量也同時增多，那么空間數據遷移效率將更低，傳輸時間可能達到無法預測的狀況。因此，當多個節點同時接收空間數據遷移時，參與的節點數和遷移的空間數據量尤為重要，并且應該根據具體的應用環境進行二者的權衡。

5 結語

本文結合了Grid GIS的異構性和電力勘察設計工程中多專題地圖的交互性，提出了基于多專題地圖的空間負載平衡遷移算法，依據不同的空間負載狀況，給出了遷移條件和遷移原則，提出了空間任務遷移、空間數據遷移、空間計算遷移和空間環境遷移四個子算法，構建了基于Neb-ula的空間負載平衡遷移模擬系統SLBM，進行了迭代模擬測試和相關性能分析，提高了電力勘察設計信息系統的性能。本文后續工作將進一步對電力勘察設計信息系統的多專題地圖進行空間操作和空間分析時，出現有多個節點同時出現超載的情況進行深入研究。