嵌入式GIS地图格式设计优化

摘要

　　随着嵌入式计算的不断发展，NAND 作为一种高效的存储设备越来越多的被运用到嵌入式环境中，由于各种硬件和软件性能的不断提高使得GIS 也得以在嵌入式环境中得到广泛运用。GIS 中决定查询性能的是地图空间数据的索引方式，目前普遍采用的是基于磁盘的 R-Tree 变种索引，本文在此基础上提出了一种更高效的 R-Tree 变种索引 Rd-Tree，并根据 NAND Flash 的读写特性对索引树的更新方式做出优化。

　　本文的主要工作包括以下两点：

　　(1) 在分析 Ro-Tree 的基础上，提出了一种新的索引结构 Rd-Tree。

　　Ro-Tree 提出了外部节点的概念，就是将节点中离其它孩子节点都比较远的孩子作为外部节点，然后放到上一级节点中，藉此来优化节点的质量，减少节点之间的重叠区域。Rd-Tree 是一种基于节点密度的索引结构，节点密度是衡量节点性质的一个指标，Rd-Tree 的核心思想就是将密度相近的点组织在一起，而在现实世界中，这些密度相近的节点往往在物理上也是相近的。Rd-Tree 在以下几方面对 Ro-Tree 做了改进：一是改进了插入过程中对外部节点的识别算法，在 Rd-Tree 中如果将一个子节点插入父节点后并不引起父节点密度的降低，我们认为该节点并不是一个外部节点，该识别算法不仅从逻辑上更契合外部节点定义而且优化了节点的质量，减少了节点中的外部节点数量；二是优化了删除过程，当在删除过程中节点向下溢出时，通过从父节点借入一个外部节点来防止无意义的重新插入；三是提高了查询效率，由于减少了外部节点数量，因此在查询过程中需要比较的次数也会相应减少，对于经典的区域查询，对比 Ro-Tree 本文在实验部分获得了 20%的效率提高。

　　(2) 根据 NAND Flash 的物理特性引入了日志更新机制。由于 NAND是一种 write-once 设备，直接在原文件上进行更新操作会在 NAND 中产生大量的垃圾数据，降低 NAND 使用空间进而导致垃圾回收时的频繁擦除操作。因此本文将地图数据分为源数据文件和更新数据文件，将地图的更新以日志的形式全部追加到更新数据文件的尾部，每次打开地图时，将更新数据提交到源数据上，在内存中生成一棵新的索引树。考虑到效率，本文还研究了地图的紧缩操作，即当更新数据比较多的时候地图重建过程会比较长，将更新提交后的新索引树写回到 NAND 作为新的源数据文件，并删除更新数据文件。本文对地图紧缩的时机也做了探讨。

　　通过本文的研究，使得对空间数据的索引更高效，对 NAND 的使用更加优化，延长了 NAND 的使用寿命并减少了文件系统的垃圾回收次数。

　　关键词：NAND、 Ro树、Rd树、地理信息系统、日志更新

ABSTRACT

　　With development of Embedded computing, NAND is pervasive in this environment as an efficient storage device. Benefiting from the enhancement of hardware & software performance, GIS is popular in the Embedded platform. In GIS, the performance is mostly determined by the index structure of space data, and now the general index structure is variants of R-Tree based on hard disk. This paper introduces a more efficient variants of R-Tree, and do some optimization works directed towards unique Read & Write feature of NAND Flash.

　　This paper includes two major parts:

　　(1) Introduces a new index structure Rd-Tree derived from Ro-Tree. Ro-Tree introduces the conception of outlier object which is far away from any other objects in the node. By moving the outlier objects from a node to its parent node, it can decrease the overlapping area between children nodes. Rd-Tree is an index structure based on node density which is an important index to measure the node quality. The main idea of Rd-Tree is organizing the nodes with similar features together. In reality, the nodes with similar features are often adjacent with each other. Rd-Tree improves Ro-Tree through such aspects: First improving the outlier object differentiation algorithm in inserting process, in Rd-Tree we do not treat a node as an outlier if after its insertion the node density of parent node is not decreased. This algorithm improves the node quality and decreases the number of outlier objects.

　　Second optimizing the deleting process, when a node underflows in the deleting process, Rd-Tree borrows a outlier object from parent node to prevent meaningless reinserting operation. Third improving the searching efficiency,as Rd-Tree decreasing the number of outlier objects, the comparing times in the searching process will be less. For example, for the classical range query,Rd-Tree is with 20 percent gain to Ro-Tree.

　　(2) Imports the journal mechanism according to physical features of NAND Flash. NAND is a kind of write-once device, updating the source data will produce large sum of garbage pages, in turn, decrease the available space and cause frequent garbage collection operation which will erase the NAND.

　　So in this paper, we divide the map into index data file and update data file,and the update is appended to the update data file as journal. Each time we open the map, the update will be committed to the index and then generate a new index in memory. With consideration of efficiency, we study the  compaction of map, when the update data is too large the rebuilding process will be long, in such situation we write the new index tree to the NAND and delete the original index data and update data.

　　KEY WORDS：NAND, Ro-Tree, Rd-Tree, GIS, Journal

　　GIS(Geographic Information System)地理信息系统指通过计算机技术将空间信息采集、组织、抽象化，再通过人们可以感知的方式将数据重现并加以利用的统称。

　　GIS 已不是什么新鲜概念，从上个世纪中叶开始人们就开始研究，而且随着计算机技术的发展，GIS也日益成熟并投入商用，目前在 PC机上 GIS业发展出一个比较完整的体系。

　　近几年来，由于手持设备性能的不断提升，尤其是人们对终端导航的巨大需求，为嵌入式 GIS 的蓬勃发展奠定了坚实的基础。目前也有很多针对嵌入式手持设备开发的导航软件，大体上有两种：一种是基于 web 服务的导航系统；一种是作为独立终端的导航系统。

　　目前国际上比较出名的手持终端的导航软件主要有 Google 公司的 Google Map，RoadmapGPS 公司的 Roadmap。Google Map 是基于 web 服务的导航终端，Roadmap则是不依赖于任何服务端的导航终端。

　　由于嵌入式设备在物理功能和计算环境方面受到某些限制，任何运行于这种受限环境中的程序也要做相应的优化，因此我们并不能单纯地把已有的基于 PC 的应用移植到手持设备上，而是要根据手持设备的特性来进行优化。

　　Flash Memory 根据实现技术和架构可以分为 AND, NAND, NOR 等几种[21]，以NOR 和 NAND 为主流。NOR 技术由 intel 与 1988 年提出，接着第二年 1989 年，东芝公司提出了 NAND 技术，当时 NAND 是为了存储，NOR 是为了代码的本地执行。

　　NOR Flash 读取速度快、代码可以在片上执行、功耗低、稳定性高；NAND Flash 与NOR Flash 相比写速度更快，而且芯片面积小适于生产大容量的 Flash，NANDFlash(以下简称 NAND)的擦除速度也比 NOR Flash 要快很多。由于 NAND 的这些特点使得 NAND能够在嵌入式环境中得到广泛的应用。

　　NAND 由块(block)组成，每个块又包含若干个(一般是 32 或者 64)个页(page)，NAND 以块为擦除单位，以页为读写单位，NAND 的随机读写效率很低，另外NAND 是一种一次写(write once)设备，即写时以页为单位，写好之后如果再修改这个页，需要将页所在的块重新擦除一次，然后再写该页。这种特性决定了对 NAND的管理不同于磁盘。对 NAND 的使用也要做相应的优化。

　　地图格式，顾名思义，就是指地图在存储设备中的组织形式与结构。相同的地图数据可以有多种不同的索引组织方式，从最简单的一维索引 B 树再到多维索引的R-Tree，不同的索引结构带来不同的操作方式和查询效率。

　　目前比较常用的地图格式有以下几种：例如国外的 MapInfo 公司的地图格式，GarMin 公司的地图格式，还有一些用于国际上数据交换的格式如 kiwi[22]、GDF[23]等格式，国内的超图公司也有自己定义的数据格式。以上这些地图格式的实现细节有些是不公开的，但是绝大部分的地图格式都是采用了 Gutman 在 1984 年提出的 R-Tree[14]这种索引结构，有些使用了 R-Tree 的变种如优先级树[2]、R*-Tree[12]、Ro-Tree(R*-Tree with outlier Handling objects)[4]、Hilbert R-Tree(using fractals)[10],有的则使用了四叉树 QuadTree[16]，有的使用了 grid[13]、hB-Tree[11]、Cell-Trees[18]，但是很少有使用 B+-Tree[7]，因为 B+-Tree 作为一个一维键值的索引树并不适用于具有多维属性的空间数据。

　　R*-Tree 将插入和删除过程中的溢出节点重新插入到树中，借此来对树节点进行优化，R*-Tree 与 R-Tree 相比性能有显着的提高；Hilbert R-Tree 对节点中的孩子根据 Hilbert 分形算法进行排序，但是要消耗额外的排序时间，并且对数据降维使用，导致查询过程比较复杂；QuadTree 的删除过程比较耗费时间，而且只支持二维数据，不支持更高维的数据；其它几种索引结构对于多维操作不如 R-Tree 便捷，因此目前被广泛采用的仍是 R-Tree的变种。

　　迄今为止，公认最高效的索引结构是 Ro-Tree，Ro-Tree 的核心思想是将地理上与其它节点(索引结构的基本单位)相距比较远的节点作为外部节点进行特殊处理。与其它 R-Tree 变种相比取得了不错的效率提升，但是 Ro-Tree 的一个不足之处是并没有提出一种很好的鉴别外部节点的方法，导致父节点中的外部节点过多，降低了查询的效率。

　　上面所述的这些地图格式都是以磁盘作为存储设备，索引中节点信息以磁盘上的扇区为单位来存储，对节点的更新也是在对应扇区上进行操作，由于磁盘是以扇区为基本读写单位，因此这种直接修改的方式比较高效，但是这种更新方式并不适用于具有 write-once 特性的 NAND 。在 NAND中运用基于磁盘的地图更新机制会造成 NAND 中垃圾数据的急剧增加，增加了垃圾回收的次数和 NAND 的擦除次数，进而缩短 NAND的使用寿命。

　　本文的研究目标主要分为两个部分：一是在 R-Tree 的基础上设计一种新的变种Rd-Tree，使用该索引结构可以获得更高的查询效率，对索引结构的优化是独立于存储设备的，即该索引结构无论是对磁盘还是 NAND 都能够运用；一是设计一种类似日志系统的地图更新方式，使得对地图的更新都以日志的形式追加到地图文件尾部，这样就避免了对原有地图文件的直接修改，因而也就减少了对 NAND的擦除次数。

　　本文的主要研究内容还包括索引结构之间的性能比较和新的地图更新方式带来的性能提升分析，以及对新的更新方式带来的负面影响的研究与探讨，并提出可行的解决方案。

　　嵌入式GIS地图格式设计与实现：

节点 R 插入前状态图

节点 C1,C2 插入 R 后 R-Tree 效果图

地图存储结构图

地图重建过程

地图紧缩过程

区域查询平均时间对比

目录

　　第一章 绪论
　　　　1.1 研究背景
　　　　　　1.1.1 嵌入式 GIS 的发展
　　　　　　1.1.2 Nand Flash 的广泛应用
　　　　　　1.1.3 目前地图格式的不足
　　　　1.2 本文的研究目标及内容
　　　　1.3 本文的主要结构
　　　　1.4 本章小结
　　第二章 关键技术
　　　　2.1 通用空间数据索引
　　　　　　2.1.1 K-D 树
　　　　　　2.1.2 Quad Tree
　　　　　　2.1.3 R-Tree
　　　　　　2.1.4 R*-Tree
　　　　　　2.1.5 R0-Tree
　　　　　　2.1.6 Hilbert R-Tree
　　　　2.2 文件系统对 Flash 文件的处理与优化
　　　　　　2.2.1 Nand Flash 的物理结构
　　　　　　2.2.2 Nand 读写特性
　　　　　　2.2.3 FTL 及其作用
　　　　　　2.2.4 Yaffs2 对 Flash 的优化
　　　　2.3 本章小结
　　第三章 地图格式设计与实现
　　　　3.1 新的索引结构 Rd‐Tree
　　　　3.2 新的更新机制日志更新
　　　　3.3 地图的存储结构
　　　　3.4 地图的重建过程
　　　　3.5 地图的紧缩
　　　　3.6 关键数据结构
　　　　　　3.6.1 内存索引结构
　　　　　　3.6.2 NAND 索引结构
　　　　　　3.6.3 更新项数据结构
　　　　3.7 地图操作实现
　　　　　　3.7.1 插入图元
　　　　　　3.7.2 修改图元
　　　　　　3.7.3 删除图元
　　　　　　3.7.4 地图的重建过程
　　　　　　3.7.5 地图的紧缩
　　　　3.8 本章小结
　　第四章 地图格式优化效率验证
　　　　4.1 构建试验环境
　　　　4.2 试验流程
　　　　　　4.2.1 修改 yaffs2
　　　　　　4.2.2 生成地图数据
　　　　　　4.2.3 验证 Rd-Tree
　　　　　　4.2.4 验证新的更新方式
　　　　　　4.2.5 输出实验数据
　　　　4.3 试验结果分析与小结
　　　　　　4.3.1 索引树比较结果
　　　　　　4.3.2 更新方式比较结果
　　　　　　4.3.3 实验小结
　　　　4.4 地图格式应用
　　第五章 结束语
　　参 考 文 献
　　致 谢

（如您需要查看本篇毕业设计全文，请您联系客服索取）