无线广播环境下的空间范围查询处理

摘要：为实现无线广播环境下快速且低能耗的空间范围查询，提出了一种基于网格空间索引的范围查询处理算法（RQGSI）。该算法在服务器端对空间数据对象建立网格空间索引以缩短调谐时间，并按Hilbert曲线填充顺序对划分后的网格进行调度以优化访问时间；在客户端设计了查询处理算法对数据对象进行过滤和剪枝；最后，通过模拟实验验证了RQGSI算法的性能。实验结果表明，RQGSI算法比基于R树的索引（RI）算法在调谐时间上降低约10%，在访问时间上原文为“提升”但按意思是否应为“降低”？是改为“降低"

降低约8%，RQGSI算法可以实现更快且更低能耗的范围查询。

关键词：无线广播；空间范围查询；网格空间索引；调谐时间；Hilbert曲线；访问时间

中图分类号： TP311.13 文献标志码：A

英文摘要

Abstract：In order to realize fast and energyefficient spatial range query in wireless broadcast environment， a Range Query based on Grid Spatial Index （RQGSI） algorithm was proposed. On the server， grid spatial index was established for all data objects to shorten tuning time， and then the meshed grid was scheduled according to the Hilbert curve filling order to optimize access time. On the client， the query processing algorithm was designed for filtering and pruning the data objects. Finally， the simulation experiments verified the performance of the proposed RQGSI. The experimental results show that， compared with the Rtree Index （RI） algorithm， the RQGSI algorithm reduces tuning time by about 10%， decreases原文为increases，应改为decreases

access time approximately by 8%， and it can achieve faster and lower energy consumption range query.

英文关键词

Key words：

wireless broadcast； spatial range query； grid spatial index； tuning time； Hilbert curve； access time

0 引言

文献[5]提出了gridpartition索引应用于无线数据广播环境下的最近邻查询，有效地减少了用户的调谐时间。文献[6]提出了一种可调节的分布式索引结构，并提出了有效的最近邻查询处理算法，同时优化了调谐时间和访问延时。文献[7]提出了基于Rtree的索引树结构来支持k近邻查询，该方法虽能优化调谐时间，但访问延时过长。文献[8]在 Rtree 结构中增加一些有用信息，通过广播修改的 Rtree 索引结构来完成k近邻查询，该方法在减少调谐时间的同时也保证了较短的访问时间。文献[9]提出了一种新的时空查询处理算法来支持连续k近邻查询，有效地节省了移动设备的能量。然而以上算法都不能很好地适用于范围查询。文献[10] 虽提出了一种线性的完全分布式的结构可以支持范围查询，但该方法访问效率不高。因此如何实现周期广播环境下快速且低能耗的空间范围查询是当前亟待解决的问题。

1 相关知识

1.1 （1，m）索引分布

（1，m）索引分布是数据广播索引技术中最常见的索引分布模式，该模式将一个周期内的数据平均分为m个数据段，在每个数据段前面附加一个索引段，如图1所示。

2.2 算法思想

RQGSI算法分为服务器端索引及调度算法和客户端查询算法两部分。在服务器端对数据对象建立网格空间索引，并按Hilbert曲线填充规则调度网格，在客户端设计查询处理算法进行过滤和剪枝。算法具体由3个阶段组成：

1）对数据对象建立网格空间索引，并将索引按（1，m）方式插入到各数据段前端。

2）对划分后的网格按Hilbert曲线填充规则进行调度，各网格内所有对象逐个调度，即同一网格内的数据对象放在本周期内的连续位置。

3） 客户端根据自己所在位置和查询半径有选择性地侦听广播信道，过滤掉不在查询范围内的对象，获取初始结果集，然后进行剪枝，求得最终精确访问对象集合。

2.3 算法设计

2.3.1 网格空间索引

本文已将空间数据对象的地理位置转换为对应的二维直角坐标系坐标。所有对象初始都位于一个大正方形范围内，正方形的左下角坐标为（xmin，ymin），右上角的坐标为（xmax，ymax），网格边长为h。将整个区域分为s×s个网格，令S=s×s。图4显示了例1中4×4的网格划分。

按以上方法在服务器端对数据对象建立网格索引，建立后的索引按（1，m）模式进行分布，即将一个周期内的数据对象先等分为m段，然后在各数据段之前附加一个索引段，索引段包含网格划分信息和S个指针，其中网格划分信息包括（xmin，ymin）、（xmax，ymax）以及网格的边长h，而指针指向各网格的下一次广播时间。通过网格空间索引，客户端可以很快获得与查询区域有关联的网格到达时间，过滤掉查询区域之外的网格，从而进一步优化调谐时间。

2.3.2 广播调度方法

由于无线数据广播只能线性地顺序访问，而 Hilbert 曲线具有降低维度及数据聚类的最优特性，因此将划分后的网格按照 Hilbert 曲线的填充顺序进行调度，使得大部分在空间相邻的对象在线性的广播信道上也能保持相邻关系。具体过程如下：记划分后的网格数目为S，根据公式n=lb S/2，求得Hilbert曲线的阶n，然后按n阶填充曲线的顺序广播所有网格。而对于每个网格内的数据对象采用逐个广播的方式，各数据对象皆含有即将广播索引段的下一次广播时间。

服务器端通过以上方法对数据对象进行广播，使得处于查询范围内的数据对象尽可能出现在同一周期内的连续位置，从而缩短了用户的访问时间。

2.3.3 客户端查询算法

给定一个查询点的位置及查询半径，客户端查询处理算法如算法1所示。

算法1 SRQ算法。

输入 查询点位置q.l，查询半径r，数据对象集合O；

输出 查询范围内的所有对象集合C。

1）侦听广播信道，如是数据对象信息（其中包含最近广播索引段的到达时间），则转入休眠状态直到下一网格索引信息到来时再进入广播信道。

2）获取网格索引信息。

3）计算以q为中心、以r为半径的区域范围所关联的全部网格，称之为候选网格。

4）将候选网格按广播时间先后顺序排序，并建立一个对象数组。

5）从第一个候选网格开始对每个网格进行如下操作：

①移动设备保持休眠状态；

②当网格被广播时客户端进入信道；

③获取网格中的全部对象放入数组。

6）对于数组中的每个对象做以下操作：

判断对象与查询点的距离dist（o.l，q.l）是否超过半径r，如果dist（o.l，q.l）≤r，则将其放入结果集C；否则对下一个对象进行判断。

7）返回结果集C。

SRQ算法主要包括以下3个步骤：

步骤1 侦听广播信道，获取第一份网格索引，根据查询点q的坐标和查询区域半径r，计算出与查询区域有交叉的网格作为候选网格，从而过滤掉查询范围之外的网格。通过该索引的指针数组，用户获得了所有候选网格的下一次广播时间。

步骤2 客户端将所有候选网格按广播时间先后顺序排序，然后等待第一个候选网格被广播，在等待过程中移动设备保持休眠状态。当第一个候选网格到来时用户侦听广播信道，获得该网格的所有对象。重复以上过程，直到获得所有候选网格的候选对象。

步骤3 客户端计算所有候选对象的位置与查询点的距离，如对象距离查询点超过查询半径则进行剪枝，从而得到最终精确查询结果集。

3 实验

这部分通过模拟实验评估RQGSI的算法性能。选择一种基于R树的空间索引RI方法进行对比，此方法采用R树来划分和索引数据对象，各节点按层次遍历的顺序广播。选取数据广播系统中访问时间（Access Time，AT）和调谐时间（Tuning Time，TT）两个最重要的性能指标作为评价标准。

3.2 实验结果及分析

3.2.1 实验1：网格划分S的影响

假设有1000个数据项，查询半径为0.05D，其中D为整个地图的直径。从图6可以看出，RQGSI索引的TT和AT都优于RI算法。在TT上，通过RQGSI索引的网格索引部分，用户可以很快过滤掉不在查询范围内的对象；在AT上，RQGSI采用的是部分索引m次分布模式，且按Hilbert曲线填充顺序调度网格使得用户需访问的数据对象尽可能连续地被广播，比RI层次组织模式的数据聚集性强。由于RI索引结构与网格划分大小无关，因此图中RI方法的TT和AT保持不变。

3.2.2 实验2：数据对象个数N的影响

设定查询半径为0.05D，S=64。由图7（a）可见，两种算法的调谐时间都有所增加，但RQGSI索引的TT优于RI方法，这是由于RQGSI不仅在服务器端对TT进行了优化，而且在客户端对查询对象进行了过滤和剪枝，从而进一步缩短了TT。在图7（b）中，数据对象个数的增加必然会加大广播周期的长度，延长用户的访问时间。虽然两个算法访问时间都有所增加，但RQGSI算法采用了Hilbert曲线填充规则进行调度，因此与RI算法相比，RQGSI算法的访问效率更高。

3.2.3 实验3：查询半径r的影响

4 结语

为了实现无线广播环境下快速且低能耗的空间范围查询，提出了一种基于网格空间索引的范围查询处理算法。算法在服务器端设计了网格空间索引结构及（1，m）索引分布模式来缩短调谐时间；为提高访问效率，对划分后的网格按Hilbert曲线填充规则进行了调度；在客户端设计了查询处理算法以进一步优化调谐时间。模拟实验考察了算法的调谐时间和访问时间，并与RI算法进行比较。实验结果表明本文算法与RI算法相比在调谐时间上降低约10%，在访问时间上降低原文为“提升”应改为降低

约8%。下一步研究将考虑关键字因素，以更好地适用于范围查询应用。

参考文献：

[3]MOURATIDIS K， YIU M L， PAPADIAS D， et al. Continuous nearest neighbor monitoring in road networks [C]// Proceedings of the 2006 32nd International Conferences on Very Large Data Bases. New York： ACM， 2006： 43-54.

[4]HUANG YK， CHEN ZW， LEE C. Continuous knearest neighbor query over moving objects in road network [C]// Proceedings of the 2009 Joint International Conferences on AsiaPacific Web and WebAge Information Management， LNCS 5446. Berlin： Springer， 2009： 27-38.

[8]LIU CM， FU SY. Effective protocols for kNN search on broadcast multidimensional index trees [J]. Information Systems， 2008， 33（1）： 18- 35.

[9]PARK K， CHOO H， VALDURIEZ P. A scalable energyefficient continuous nearest neighbor search in wireless broadcast systems [J]. Wireless Networks， 2010， 16（4）： 1011-1031.