基于云计算的空间插值计算.docx

1、基于云计算的空间插值计算分类号：TP311.4 U D C：D10621-407-(2012)5442-0密 级：公 开 编 号：2008041025成都信息工程学院学位论文基于云框架的空间插值计算研究论文作者姓名：王文刚申请学位专业：地理信息系统申请学位类别：理学学士指导教师姓名（职称）：陈军（讲师）论文提交日期：2012年06月 06 日基于云框架的空间插值计算研究摘 要云计算作为一种新兴的技术，已经应用到各个领域。云计算的本质就是通过整合、共享和动态的提供资源来实现IT投资利用率的最大化。在地理信息系统领域，云计算可以用来管理、分析大量的分布式的数据，并且与不同地理位置的用户共享应用成果

2、。传统的空间插值运算模式在数据量很大的情况下，会出现资源占有量大、等待时间长、甚至卡死的状态。针对传统插值计算这个缺点，本研究拟将计算模型构架于云平台上，探讨实现的关键技术，包括云框架的搭建、云端空间数据的组织、空间插值算法等。最后，对基于云框架下的空间插值模式性能进行了测试，证实了在大批量数据的情况下云框架下的插值模式具有更强更快的处理能力，其研究具有很高的理论意义和实践价值。关键词：云计算；空间插值；云GISThe study of Spatial Interpolation under the framework of Cloud ComputingAbstractCloud compu

3、ting as a new technology, has been used in various fields. Cloud computing is the essence through the integration, share and provide resources to realize the maximization rate of the IT investment. In the geographic information system field, cloud computing can be used to management, analysis of lar

4、ge amounts of distributed data, and sharing application results with others in different geographical location. The traditional spatial interpolation mode in the case of very large amount of data, has occuped a large amount of resources, long waiting times, and even stuck state.According to the defe

5、ct of traditional interpolation calculation, this study tries to build cloud platform structure calculation model, discusses the realization of the key technology, including the frame of the cloud structures, and clouds of spatial data organization, the spatial interpolation method, etc. Finally, ba

6、sed on the framework of Cloud Conputing the spatial interpolation model was tested and confirmed in the large quantities of data, its proved that the modal of this paper has stronger faster processing ability, its research has the very high theoretical significance and practical value.Key words: clo

7、ud computing; spatial interpolation; cloudGIS目 录论文总页数：19页1引言 11.1 课题背景 11.2 国内外云GIS研究现状 11.3 研究内容 11.4 研究意义 22空间插值 22.1空间插值概念 22.2空间插值算法实现 33空间插值的Map/Reduce分析 43.1 空间插值的Map/Reduce任务分析 43.2 空间插值的Map/Reduce数据分析 43.3 空间插值的Map/Reduce计算分析 54空间插值的云框架设计 55空间数据在分布式文件系统中的组织 76空间插值的任务调度 76.1 Map/Reduce任务调度过程

8、76.1.1 空间插值的Map/Reduce键值定义 86.2 Map/Reduce中均衡负载调度策略 87空间插值的性能测试 10结 论 11参考文献 12致 谢 13声 明 141引言1.1 课题背景GIS技术出现到现在已经有几十年，随着技术成熟度的不断提高，越来越多的空间数据和非空间数据逐渐被应用在GIS中。近些年来，随着数据采集技术的不断进步，我们得到的数据越来越丰富 1。与此同时，不断增长的海量数据使任何单一的机构都难以保存或者处理。此外，由于GIS系统对这些数据进行空间分析的过程极其复杂，所以对计算机的运算能力要求也很高。鉴于这些情况，传统的GIS系统模型已经逐渐无法满足日益增长的

9、需求。我们需要的是一个可存储、管理、分析、共享海量GIS数据的平台。这个时候，一个像云计算这样的可扩展的、低成本的计算平台对我们来说是一个非常理想的选择。本文提出了一个基于云框架下的空间插值计算的系统架构。首先，提出了一个云计算框架模型，然后讨论起其实现的关键技术。1.2 国内外云GIS研究现状自从2006谷歌公司高级工程师提出了云计算这一计划后，现在已经是全民皆云，人云亦云。随着云计算的不断发展，GIS行业也搭上了云计算的顺风车。ESRI可算是GIS行业的领头羊，在过去一段时间里，Esri已经在VCEs Vblock platform（一个私有云基础设施平台）上成功测试了ArcGIS Ser

10、ver。此外，ArcGIS Server 10.1的设计和构架完全支持云部署，并且经过私有云服务、亚马逊EC2和微软Windows Azure的测试和验证。ESRI将在未来几个月使得ArcGIS Online成为一个完整的软件即服务（SaaS）应用程序。ArcGIS Online将允许用户创建和共享其在云环境中的网络地图和数据，包括存储、管理和托管服务。该系统使用户能够为轻松发布内容为他人使用，解锁所选处理业务，分享知识，从而利用低成本的云基础设施扩展自身的能力。用户可利用新型灵活的和可扩展的部署方式来扩展他们的系统，并通过更广泛的使用地理信息来增加其GIS的价值。近年来。国内云GIS发展也有

11、所成就。超图等国内的GIS厂商已开始与IBM蓝云、红帽Linux、微软DDTK-E等的多个云平台上进行合作，用户也可以用此来构建自己的“私有云”。其次，在超级集群技术，超图推出支持在内网和公网上的分布式异构集群的产品，为支持GIS云的分布式部署和扩展做好了准备。另外，超图新一代GIS平台产品基于共相式GIS技术理念，支持包括Windows、Linux、Unix等各类操作系统，使得可以支持基于不同操作系统所构建的云，让用户也有更多的选择。1.3 研究内容随着GIS技术的不断发展，GIS系统所包含的数据越来越庞大2，GIS对计算机存储数据、处理数据的能力要求越来越高，独个计算机已经无法满足日益增长

12、的需求。随着云计算技术的日益成熟，系统的框架采用云计算的思想，包括数据的存储、大量的数据计算。在 GIS 行业中使用云计算，将会简化 GIS 应用程序部署与管理，降低投资和运行成本，缩短 GIS 项目建设周期，提高 GIS 应用程序和基础设施的灵活性3。根据这些要求，主要的研究内容主要如下：1) 云计算作为一门新兴技术，本文首先探讨云计算的特点；2) 针对空间插值计算，设计系统框架。云框架设计是课题的一个重点难点，包括云端数据的组织管理以及任务调度等；3) 研究在云框架下的插值算法。为了插值结果更精确，需要自己重新实现IDW插值算法；1.4 研究意义本研究将云计算应用到 GIS 领域，重点研究

13、云计算在空间数据插值中应用的方法以及意义。在传统的插值模式中，所有的数据存储、管理、分析处理功能模块都是在单一的终端运行。一般情况下处理的空间数据量比较小，传统模型不但完全可以应对而且效率会很高，但是当所处理的数据量非常大的情况下，就会出现资源占有量大、等待时间长、甚至卡死的状态。相反的，基于云框架下的空间插值模型的计算并非是在单一的终端进行，而是在一个分布式的计算环境下，将插值计算任务交由许多个可连接的节点处理，这样处理的结果是将一个计算任务划分为许多个子任务，由一个计算机集群处理，整个计算机集群共同分担了任务压力。不但避免了单个终端任务繁重，而且可以充分的利用资源。因此，云插值模型增强对海

14、量数据的存储、计算、管理，并且可以最大限度的利用一切资源，节约成本4-6。2空间插值2.1空间插值概念空间插值常用于将离散点的测量数据转换为连续的数据曲面，以便与其它空间现象的分布模式进行比较，它包括了空间内插和外推两种算法。空间内插算法：通过已知点的数据推求同一区域未知点数据。空间外推算法：通过已知区域的数据，推求其它区域数据。如图1所示，空间插值方法主要包括：图1 空间插值分类结构1) 确定性方法确定性插值方法是基于信息点之间的相似程度或者整个曲面的光滑性来创建一个拟合曲面，比如反距离加权平均插值法（IDW）、趋势面法、样条函数法等7。2) 统计学方法地质统计学插值方法是利用样本点的统计规

15、律，使样本点之间的空间自相关性定量化，从而在待预测的点周围构建样本点的空间结构模型，比如克立格（Kriging）插值法7。2.2空间插值算法实现因为在云框架下的插值计算是将需要插值的数据分块进行，因此为了保证在融合插值结果时候每个任务块边缘正确，需要自己实现空间插值算法，在这里选择了IDW反距离加权插值算法。IDW(Inverse Distance Weighted)是一种常用而简便的空间插值方法，它以插值点与样本点间的距离为权重进行加权平均，离插值点越近的样本点赋予的权重越大。 设平面上分布一系列离散点，已知其坐标和值为Xi，Yi, Zi （i =1，2，n）通过式1距离加权值求z点值8。(

16、式1)3空间插值的Map/Reduce分析Map/Reduce为云计算的核心技术，是一种简化的分布式编程模型和高效的任务调度模型。MapReduce模式的思想是将要执行的问题分解成Map(映射)和Reduce(化简)的方式，先通过Map程序将数据切割成不相关的区块，分配（调度）给大量计算机处理，达到分布式运算的效果，再通过Reduce程序将结果汇整输出。在云框架下进行空间插值计算，要使空间插值达到最大的执行效率，必须采用Map/Reduce框架，将插值任务划分为多个Map单元交与云端各节点处理，云节点完成Map任务后，将结果反馈至Reduce节点，完成任务的综合。3.1 空间插值的Map/Re

17、duce任务分析空间插值属于空间计算，插值结果为栅格数据，各栅格像元值代表该位置上的插值结果。考虑到空间插值的特征，可将目标栅格按行列划分为大小相等的子区。设目标栅格行列数分为为Nx和Ny, 子区行列数均为Ns，则应划分的Map数量在X和Y方向依次为： (式2) (式3)一个Map单元的插值计算次数等于子区的像元总数，即为Ns*Ns。空间插值Map任务划分示意如图2所示。图2 空间插值Map任务划分示意各云节点完成Map任务后，得到的为一个子区栅格数据流，该数据流通过网络传输到Reduce任务对应的计算机完成栅格数据的合并过程。 3.2 空间插值的Map/Reduce数据分析云节点要完成分区插

18、值任务，需要提供以下几个方面的原数据：插值方法参数、待插值区域的坐标范围、观测点数据。空间插值原数据量主要在观测点数据。就空间插值原数据量而言，一个插值点包含X,Y坐标信息和观测值Z。如果均采用双精度小数存储，一个插值点需要24个字节的存储空间。假定待插值点个数为10240，则原数据的空间数据存储量为240Kb。在现有的网络带宽下，空间插值原数据量也相对较小。一次空间插值需要提供多个原始的观测点；在IDW中，一个栅格单元的插值计算由最近的几个观测点获得；由于IDW将距离作为选取候选观测点的基本依据，一个Map单元需要的候选观测点不能限于Map子区，为提高插值计算速度，往往将所有待插值点通过网络

19、传至云节点上参与计算。如果只考察单个的数据上传，原数据量在现有带宽条件下基本上可以忽略。但是，如果在Map计算中，均上传原始数据，网络流量就不可忽视了。假定Map任务数量为20，上例中总数据传输量为5.6Mb。因此，合理的做法是，在空间插值计算之前，先将数据上传至各云端的数据节点保存，Map任务由保存数据的节点完成，这样就避免了数据在网络上冗余流动，提高空间插值的执行效率。在云平台上，分布式文件系统可满足空间插值原数据存储的要求。 3.3 空间插值的Map/Reduce计算分析现有的GIS软件如ArcGIS等均提供了空间插值接口，但应用于云端空间插值存在一定的问题。主要原因在于GIS软件提供的

20、插值接口不能明确给出子区的插值方案。利用ArcGIS空间差值接口计算的子区结果是存放于底层组件中，在返回插值结果时候需要从组件中提取结果，效率较低。因此，云空间插值需要从底层重新实现插值算法。在子区插值时不仅要提供所有的原始观测点数据，还要提供待插值总范围以及分区范围。在栅格像元插值时，需要在所有观测点中选取最近的候选点。这样，我们就可以直接取得子区插值结果返回给任务节点，而不需要在计算完成后重新从ArcGIS组件获取结果。4空间插值的云框架设计本研究将系统框架构建于云平台上，利用云计算的超级计算和存储海量数据的能力来搭建一个拥有快速处理大量数据计算能力的系统框架，实现高效的管理分析空间数据的

21、目的，以完成云插值的功能。在该框架下，服务器为云服务中心，由总服务器，任务控制服务器，数据节点组成，完整框架如图3所示。图3 云插值框架结构总服务器负责接收客户端的命令请求、以分布式文件系统的形式存储管理空间数据。云节点是存储空间数据的真实位置。同时，也是进行空间插值计算的任务中心。任务节点在服务器端只要负责分发任务、融合插值计算结果。在云框架下，完整的空间插值计算流程如下：首先，客户端向服务器发送插值命令，然后将需要插值的数据上传至住服务器，存储到分布式文件系统中。任务节点获得存储空间数据的云节点信息，通过Map/Reduce技术将插值计算任务自动分解为多个Map子任务交与云节点处理。等待云

22、节点完成插值任务后，将插值结果返回到任务节点，任务节点将计算结果融合在一起，并将插值结果存储在云端；待插值计算完成后，通知客户端。如果任务成功，客户端通过与主服务器连接直接读取相应的计算结果。如果任务失败，则发送失败消息反馈回客户端，并且处理掉插值任务中生成的临时文件。5空间数据在分布式文件系统中的组织如前所述，空间插值过程仍然需要有分布式文件系统的支持。云GIS环境下的空间数据的特点是海量、异构、多源和动态，这些特点决定了云GIS 环境下的空间数据通常是无序、杂乱的9。云计算是传统分布式计算的发展，是一种新型的网络分布式计算。它在分布式计算基础上，增加了分布式文件系统的支持，从而实现了计算向

23、存储的迁移10。因此，分布式文件系统是云的典型特征。为实现基于云平台的空间插值计算，空间数据也必须存储在分布式文件系统中。本研究按照中心服务器的存储模式存储管理空间数据。 本研究采用中心服务器模式管理整个文件系统，简化系统设计，降低实现难度。总服务器不仅接收消息，也是空间数据的管理中心，它管理分布式文件系统的所有的元数据，真实的数据则分散存储在各云节点中。由于只有一个中心服务器，避免了分布式文件系统的元数据不一致的问题；同时，由于中心服务器掌握了整个分布式文件系统的空间数据的内容信息，通过查询分布式文件系统的元数据而无需与节点交互。具体的元数据是以XML文件形式存储在服务器，其中一个矢量数据在

24、总服务中完整表示如下示例：6621210在XML文件中，XML文件名就是数据名称，Size表示文件大小，其中最重要的DataNodes，包含着所有的存储该数据的节点信息，如及节点IP、端口号。6空间插值的任务调度 在插值任务中，任务调度机制直接影响插值的效率。在本研究提出的云框架中，插值任务调度包括两个方面，包括两个方面，一是Map/Reduce任务调度，二是Map/Reduce负载均衡调度。6.1 Map/Reduce任务调度过程Map/Reduce是云服务的关键计算技术。Map/Reduce分为映射和规约2步，即Map和Reduce。Map/Reduce运行时系统会将资料切割，并分配给不同

25、的运算主机进行处理。在执行Map过程中，系统读入一组键/值(Key/Value)后，透过Map程序产生多组中间运算键值(Intermediate Key/Value)，最后经由重组程序合并具有相同Key的中间运算序列，产生最后的结果。在一次插值任务中，任务节点负责划分Map任务。任务节点将插值数据分块，每块作为一个Map单元，发送给云节点。云节点接受到插值命令后，根据 Map的键/值，执行Map任务，完成一个任务分区上的空间插值，并将插值结果返回到任务节点；当任务节点每接受到一块插值结果后，执行Reduce，将每个分块镶嵌到相应的位置上，最终生成插值结果，供客户端访问。6.1.1 空间插值的M

26、ap/Reduce键值定义 在Map/Reduce的任务调度中，一个Map单元负责一个任务分区的插值结果计算。任务节点在处理插值请求时，为使云节点返回的图像能正确镶嵌在一起，必须为每一个Map任务生成唯一的标记Key，定义如下：struct MapKey Int FID;上定义中，FID表示任务节点为每个Map分块分配的ID号。任务节点必须保证每个Map单元生成的结果都具有唯一个编号。Map过程的Value值用于定义云节点处理的内容，包括插值方法参数、待插值区域的索引号、输出结果大小。由于一个Map对应一块空间数据，云节点返回的插值数据在任务节点中也必须被唯一识别，因此，Reduce的Key在

27、MapKey结构体基础上，增加了每个数据分块融合时所需的索引号，定义如下： struct ReduceKey int FID; int Index;Reduce的Value为图像数据流。在任务节点，中首先生成一个用来融合插值结果的总图，然后根据Index将每个子块数据流镶嵌到总图即可。6.2 Map/Reduce中均衡负载调度策略 云框架下的服务器负责分派节点处理任务以及接受插值结果，子节点负责计算并返回结果。由此，一个Map/Reduce过程中，任务最繁重的地方是在云节点和任务节点上。因此，均衡负载主要是指服务器如何选择任务节点以及任务节点如何选择云节点来执行任务。常用负载指标有CPU利用率

28、、内存使用情况、网络流量、进程响应时间等11。为简化负载均衡调度的模拟，采用CPU利用率、内存使用情况和网络流量三个指标评价节点的负载量。对于一个子任务，云节点内存使用情况、CPU占用率、网络流量与计算区域大小、成正比与栅格相元大小成反比。假设单元任务计算结果的栅格分块的宽度和高度相同为H，对云节点单元任务负载量L按式L=H*H进一步简化，可以综合反映CPU利用率、内存使用情况和网络流量的负载。假定当各云节点空闲时，具有相等的处理能力。设当前有n个正在处理的插值单元任务，采用式1近似评价云节点当前的总负载量L： (式4)根据上面计算，每个云节点跟踪记录当前总负载量L，初始为0。当分配新任务时，

29、L值按式2累加；当结束任务时，L值按式2减去单元任务的负载量。根据总负载量，负载均衡调度的基本思路如下：总服务器接受到客户端的插值命令后，启动固定数量的线程并获取可用的节点列表。每一个线程在一个时间点上负责连接一个特定的节点执行一个单元任务。为提高线程的处理速度，按照节点的处理平均时间最少的原则为线程分配最佳节点，节点处理平均时间初始设置为0，即认为各节点均有相等的处理能力。子节点完成单元任务后，将处理好的子区图像反馈回总服务器，线程标记为空闲并计算对应子节点响应的平均时间，该线程可继续分配下一个单元任务，并按子节点响应平均时间最小的策略重新寻找最佳的节点。为避免节点执行单元任务无效导致插值计

30、算操作阻塞，各线程设置一最大等待时间，当子节点处理时间超过规定时间即标记该节点对该单元任务为无效节点，并从可用的节点中寻找最佳的节点重新执行。当所有可用节点均标记为无效节点，则插值计算失败并反馈给客户端。总服务器插值计算调度流程如图4所示： 图4 调度流程图7空间插值的性能测试 总服为比较测试云插值和传统插值的性能，本研究使用点数据图层做测试，插值点数量933个，采用IDW反距离加权插值算法，输出图像大小为2300*1600，输出格式为tiff，大小为20.9MB。任务节点只有一个，测试中所用的电脑性能有点差异。在云模式中，分别选择（1J；1D）、（1J；2D）、（1J；3D）、（1J；4D）

31、几种测试环境（J表示任务节点，D表示云节点，数字表示数量）。分别记录不同数目节点节点下的插值时间。最后与常规空间插值的时间对比。性能测试结果如表1：表1 插值时间对比从表1可见，当云节点个数为1个的时候，普通插值方式性能要高于云插值模式，这个主要是因为在云插值模式下任务节点要对数据进行任务划分、融合插值结果还有在网络中传输数据流量需要时间；云节点在每次执行任务时都需要重新打开数据并对数据建立索引。相反普通插值模式下数据只需要打开一次，插值结果的融合计算等都在本机，并且不存在网络流量传输，故而效率高。但是在云节点不断增加的情况下，分配到每个节点上的任务数量会相对减少，这样就节省了每次读取数据与建立索引的时间，所以云插值所需时间不断减少。可以看出，云插值具有更强更快的处理能力。结 论本研究针对构建于云框架下的GIS软件模型，以空间插值为研究方向，研究其特性。通过实验证明了基于云框架下的空间插值计算模型在大数据量的情况下随着云节点的增多，处理能力越强，插值速率越快。其研究成果具有一定的理论意义和实践价值。本研究设计的云框架只包含一个云服务器， 然而，在实际运用中，会有很多很多的云服务