无线数据广播环境中路网最近邻居节点的查询技术分析

《无线数据广播环境中路网最近邻居节点的查询技术分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第1口引言在的回溯问题也大大增加了用户的数据获取时间。而预计算的思想的引入，将成功的把数据广播环境和字问数据查询有效的结合一起来。本文详细介绍了这些方法的设计动机、相应的结构和算法设计、及所用到的技术和优化方法。首先，在服务器端通过基于Voronoi图的算法转换数据。使得用户能够快速定位被查询点t并且减少广播数据的冗余信息。在调度策略上采用Hilbert曲线来保持数据的空间邻近关系。用户通过侦听信道，下载自己所在道路两个路口的相关信息从而得到晟近邻居节点信息(例如离自己最近的加油站)。本文提出的方法在为用

2、户提供高效查询的情况下有效减少了访问时间。而且．从理论分析和实验结果两方面对这些解决方案进行了性能评估。此外，相关问题拓展和今后研究工作。空间数据管理和数据广播的结合领域是一个丰富的研究领域，结合目前已有的工作，我们对相关的问题和解决思路进行了拓展，从实际应用角度对大规模空间管理技术进一步展开研究和探讨．试探性的提出一些研究方向和初步想法，确立了今后的一些研究内容和具体工作。I．5．文章结构论文所选的课题关注无线数据广播环境下最近邻居节点查匈技术，全文的中心内容针对大规模用户数量，提出结合无线数据广播技术

3、．在路网环境中进行最近邻居节点查询。该方法使用基于Voronoi图的算法转化路网信息，将处理后的路网信息作为广播数据，不仅提高了用户的查询效率，还减少广播数据中的冗余信息。在数据调度上，采用Hilbert曲线对数据排序．从而保持广播数据的空间临近性。本文共分7章，全文的内容和章节安排如下：第1章“引言”，该部分介绍了空间数据查询技术的研究背景、传统无线数据广播的基本问题和性能指标、两类技术结合的新特点以及介绍了本文的主要工作内容。第2章“背景知识”，该部分的主要内容是介绍了空间查询技术的常用索引结构、无线

4、数据广播相比C／S模式的优势．以及其相应的支持空间数据查询的新模式。第3章“路网数据组织转化”，该部分分别介绍了在路网中进行空间最近邻居节点查询的研究问题和动机分析，针对该类查询在数据广播环境中适台的数据结构形式以及基本的弱客户端式的NearestNei曲bor查询方法。第4章“调度策略和查询方式”，该部分提出了基于边的调度算法EBA、基于点的广播算法PBA和基于Voronoi格的广播算法VBA三种方式，并给出了相应理论分析和实验结果分析，得出VBA方法采用Voronoi图的算法转化路网信章引言了进一第2

5、${}最自J识第2章背景知识本章节主要对当前字问查询技术和无线数据广播工作进行简要介绍，然后回顾和讨论近期在两个领域做的一些相关工作。2．1．多维空间索引技术近些年移动牖控系统、地理信息系统、传感器网络、卫星圈像处理等应用的出现使得窄阁数据库受到了极大的关注。但是一般的空间数据位置信息部有二维或者三维的坐标数据。这相比一股的关系数据库存储和查询开销要大报多。在传统数据库中常通过建立索引机制可以帮助快速查匍到所请求的数据，如B+树、Hash索引。但是这些都足一维索引，不再适合空间数据库'9---维乃至多维的

6、空间数据。所以必须为空间数据库建立一套专门的索引机制——空间索引mⅡ”I。所谓空间索引就是指在存储空间数据时依据空间对象的位置或空间对象之间的某种空间关系，来建立一种有顺序的数据结构来方便用户的查向、插入，删除和更改操作。在目前已经被提出的空问索引技术中，比较典型的技术有R—tree、四叉树、网格文件等。下面会依次介绍这些空间索引技术。由于索引类型种类繁多，针对不同环境和不同类型下的查询，例如最近邻居节点查询(NN查询)，最近k个邻居节点查询(kNN)，在有阻挡环境下的最近邻居节点查询(ONN查询)等，需

7、要优化基础索引类型或者混合几种索引来提供高效查询。在本章中也会简单介绍空间查询的类别。2．1．1．基于B树的空间索引R—treeI”堤B树在多维空间的扩展，由于其优秀的查询性能，也常被用于索引其它多维数据。R．tree像B．tree一样，是一个高度甲街的树型结构且完全动态，插入、删除、查询可以交叉进行，不需要定期的全局数据重维。R-tree中存在两类节点，一类是l叶子节点，一类是中间节点。其中MBR(MinimumBound

8、ingRectangle)是该空问对象在k维空间中的最小边界矩形MBR=(Io，Il，⋯I川)，n标示空间的维度，I．标示在i维度上空间对象的坐标闭区间[a,b]；tuple—dentitier是该空间对象的唯一标示；child—pointer是指向子树根节点的指针。背矗Ⅻ*图22Rcrcc结构示意国“图2l是一棵二维R—tree空间平面对象分布图，圈2．2是数据对象的分布所对应的R-tree结构示意。在图2l中有19个区域，