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

无线播送环境下的空间范围查询处理摘要：为实现无线播送环境下快速且低能耗的空间范围查询，提出了一种基于网格空间索引的范围查询处理算法〔RQGSI〕。该算法在效劳器端对空间数据对象建立网格空间索引以缩短调谐时间，并按Hilbert曲线填充顺序对划分后的网格进展调度以优化访问时间；在客户端设计了查询处理算法对数据对象进展过滤和剪枝；最后，通过模拟实验验证了RQGSI算法的性能。实验结果说明，RQGSI算法比基于R树的索引〔RI〕算法在调谐时间上降低约10%，在访问时间上原文为“提升〞但按意思是否应为“降低〞？是改为“降低降低约8%，RQGSI算法可以实现更快且更低能耗的范围查询。关键词：无线播送；空间范围查询；网格空间索引；调谐时间；Hilbert曲线；访问时间中图分类号：TP311.13文献标志码：A英文摘要Abstract：Inordertorealizefastandenergyefficientspatialrangequeryinwirelessbroadcastenvironment，aRangeQuerybasedonGridSpatialIndex〔RQGSI〕algorithmwasproposed.Ontheserver，gridspatialindexwasestablishedforalldataobjectstoshortentuningtime，andthenthemeshedgridwasscheduledaccordingtotheHilbertcurvefillingordertooptimizeaccesstime.Ontheclient，thequeryprocessingalgorithmwasdesignedforfilteringandpruningthedataobjects.Finally，thesimulationexperimentsverifiedtheperformanceoftheproposedRQGSI.Theexperimentalresultsshowthat，paredwiththeRtreeIndex〔RI〕algorithm，theRQGSIalgorithmreducestuningtimebyabout10%，decreases原文为increases，应改为decreasesaccesstimeapproximatelyby8%，anditcanachievefasterandlowerenergyconsumptionrangequery.英文关键词Keywords：wirelessbroadcast；spatialrangequery；gridspatialindex；tuningtime；Hilbertcurve；accesstime0引言文献[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=lbS/2，求得Hilbert曲线的阶n，然后按n阶填充曲线的顺序播送所有网格。而对于每个网格内的数据对象采用逐个播送的方式，各数据对象皆含有即将播送索引段的下一次播送时间。效劳器端通过以上方法对数据对象进展播送，使得处于查询范围内的数据对象尽可能出如今同一周期内的连续位置，从而缩短了用户的访问时间。2.3.3客户端查询算法给定一个查询点的位置及查询半径，客户端查询处理算法如算法1所示。算法1SRQ算法。输入查询点位置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树来划分和索引数据对象，各节点按层次遍历的顺序播送。选取数据播送系统中访问时间〔AccessTime，AT〕和调谐时间〔TuningTime，TT〕两个最重要的性能指标作为评价标准。3.2实验结果及分析3.2.1实验1：网格划分S的影响局部，用户可以很快过滤掉不在查询范围内的对象；在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%。下一步研究将考虑关键字因素，以更好地适用于范围查询应用。参考文献：2022JointInternationalConferencesonAsiaPacificWebandWebAgeInformationManagement，LNCS5446.Berlin：Springer，2022：27-38.[8]LIUCM，FUSY.EffectiveprotocolsforkNNsearchonbroadcastmultidimensionalindextrees[J].Inf