基于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，进行了迭代模拟测试和相关性能分析，提高了电力勘察设计信息系统的性能。本文后续工作将进一步对电力勘察设计信息系统的多专题地图进行空间操作和空间分析时，出现有多个节点同时出现超载的情况进行深入研究。