無線廣播環(huán)境下的空間范圍查詢處理

無線播送環(huán)境下的空間范圍查詢處理摘要：為實現(xiàn)無線播送環(huán)境下快速且低能耗的空間范圍查詢，提出了一種基于網(wǎng)格空間索引的范圍查詢處理算法〔RQGSI〕。該算法在效勞器端對空間數(shù)據(jù)對象建立網(wǎng)格空間索引以縮短調(diào)諧時間，并按Hilbert曲線填充順序?qū)澐趾蟮木W(wǎng)格進展調(diào)度以優(yōu)化訪問時間；在客戶端設(shè)計了查詢處理算法對數(shù)據(jù)對象進展過濾和剪枝；最后，通過模擬實驗驗證了RQGSI算法的性能。實驗結(jié)果說明，RQGSI算法比基于R樹的索引〔RI〕算法在調(diào)諧時間上降低約10%，在訪問時間上原文為“提升〞但按意思是否應(yīng)為“降低〞？是改為“降低降低約8%，RQGSI算法可以實現(xiàn)更快且更低能耗的范圍查詢。關(guān)鍵詞：無線播送；空間范圍查詢；網(wǎng)格空間索引；調(diào)諧時間；Hilbert曲線；訪問時間中圖分類號：TP311.13文獻標志碼：A英文摘要Abstract：Inordertorealizefastandenergyefficientspatialrangequeryinwirelessbroadcastenvironment，aRangeQuerybasedonGridSpatialIndex〔RQGSI〕algorithmwasproposed.Ontheserver，gridspatialindexwasestablishedforalldataobjectstoshortentuningtime，andthenthemeshedgridwasscheduledaccordingtotheHilbertcurvefillingordertooptimizeaccesstime.Ontheclient，thequeryprocessingalgorithmwasdesignedforfilteringandpruningthedataobjects.Finally，thesimulationexperimentsverifiedtheperformanceoftheproposedRQGSI.Theexperimentalresultsshowthat，paredwiththeRtreeIndex〔RI〕algorithm，theRQGSIalgorithmreducestuningtimebyabout10%，decreases原文為increases，應(yīng)改為decreasesaccesstimeapproximatelyby8%，anditcanachievefasterandlowerenergyconsumptionrangequery.英文關(guān)鍵詞Keywords：wirelessbroadcast；spatialrangequery；gridspatialindex；tuningtime；Hilbertcurve；accesstime0引言文獻[5]提出了gridpartition索引應(yīng)用于無線數(shù)據(jù)播送環(huán)境下的最近鄰查詢，有效地減少了用戶的調(diào)諧時間。文獻[6]提出了一種可調(diào)節(jié)的分布式索引構(gòu)造，并提出了有效的最近鄰查詢處理算法，同時優(yōu)化了調(diào)諧時間和訪問延時。文獻[7]提出了基于Rtree的索引樹構(gòu)造來支持k近鄰查詢，該方法雖能優(yōu)化調(diào)諧時間，但訪問延時過長。文獻[8]在Rtree構(gòu)造中增加一些有用信息，通過播送修改的Rtree索引構(gòu)造來完成k近鄰查詢，該方法在減少調(diào)諧時間的同時也保證了較短的訪問時間。文獻[9]提出了一種新的時空查詢處理算法來支持連續(xù)k近鄰查詢，有效地節(jié)省了挪動設(shè)備的能量。然而以上算法都不能很好地適用于范圍查詢。文獻[10]雖提出了一種線性的完全分布式的構(gòu)造可以支持范圍查詢，但該方法訪問效率不高。因此如何實現(xiàn)周期播送環(huán)境下快速且低能耗的空間范圍查詢是當前亟待解決的問題。1相關(guān)知識1.1〔1，m〕索引分布〔1，m〕索引分布是數(shù)據(jù)播送索引技術(shù)中最常見的索引分布形式，該形式將一個周期內(nèi)的數(shù)據(jù)平均分為m個數(shù)據(jù)段，在每個數(shù)據(jù)段前面附加一個索引段，如圖1所示。2.2算法思想RQGSI算法分為效勞器端索引及調(diào)度算法和客戶端查詢算法兩局部。在效勞器端對數(shù)據(jù)對象建立網(wǎng)格空間索引，并按Hilbert曲線填充規(guī)那么調(diào)度網(wǎng)格，在客戶端設(shè)計查詢處理算法進展過濾和剪枝。算法詳細由3個階段組成：1〕對數(shù)據(jù)對象建立網(wǎng)格空間索引，并將索引按〔1，m〕方式插入到各數(shù)據(jù)段前端。2〕對劃分后的網(wǎng)格按Hilbert曲線填充規(guī)那么進展調(diào)度，各網(wǎng)格內(nèi)所有對象逐個調(diào)度，即同一網(wǎng)格內(nèi)的數(shù)據(jù)對象放在本周期內(nèi)的連續(xù)位置。3〕客戶端根據(jù)自己所在位置和查詢半徑有選擇性地偵聽播送信道，過濾掉不在查詢范圍內(nèi)的對象，獲取初始結(jié)果集，然后進展剪枝，求得最終準確訪問對象集合。2.3算法設(shè)計2.3.1網(wǎng)格空間索引本文已將空間數(shù)據(jù)對象的地理位置轉(zhuǎn)換為對應(yīng)的二維直角坐標系坐標。所有對象初始都位于一個大正方形范圍內(nèi)，正方形的左下角坐標為〔xmin，ymin〕，右上角的坐標為〔xmax，ymax〕，網(wǎng)格邊長為h。將整個區(qū)域分為s×s個網(wǎng)格，令S=s×s。圖4顯示了例1中4×4的網(wǎng)格劃分。按以上方法在效勞器端對數(shù)據(jù)對象建立網(wǎng)格索引，建立后的索引按〔1，m〕形式進展分布，即將一個周期內(nèi)的數(shù)據(jù)對象先等分為m段，然后在各數(shù)據(jù)段之前附加一個索引段，索引段包含網(wǎng)格劃分信息和S個指針，其中網(wǎng)格劃分信息包括〔xmin，ymin〕、〔xmax，ymax〕以及網(wǎng)格的邊長h，而指針指向各網(wǎng)格的下一次播送時間。通過網(wǎng)格空間索引，客戶端可以很快獲得與查詢區(qū)域有關(guān)聯(lián)的網(wǎng)格到達時間，過濾掉查詢區(qū)域之外的網(wǎng)格，從而進一步優(yōu)化調(diào)諧時間。2.3.2播送調(diào)度方法由于無線數(shù)據(jù)播送只能線性地順序訪問，而Hilbert曲線具有降低維度及數(shù)據(jù)聚類的最優(yōu)特性，因此將劃分后的網(wǎng)格按照Hilbert曲線的填充順序進展調(diào)度，使得大局部在空間相鄰的對象在線性的播送信道上也能保持相鄰關(guān)系。詳細過程如下：記劃分后的網(wǎng)格數(shù)目為S，根據(jù)公式n=lbS/2，求得Hilbert曲線的階n，然后按n階填充曲線的順序播送所有網(wǎng)格。而對于每個網(wǎng)格內(nèi)的數(shù)據(jù)對象采用逐個播送的方式，各數(shù)據(jù)對象皆含有即將播送索引段的下一次播送時間。效勞器端通過以上方法對數(shù)據(jù)對象進展播送，使得處于查詢范圍內(nèi)的數(shù)據(jù)對象盡可能出如今同一周期內(nèi)的連續(xù)位置，從而縮短了用戶的訪問時間。2.3.3客戶端查詢算法給定一個查詢點的位置及查詢半徑，客戶端查詢處理算法如算法1所示。算法1SRQ算法。輸入查詢點位置q.l，查詢半徑r，數(shù)據(jù)對象集合O；輸出查詢范圍內(nèi)的所有對象集合C。1〕偵聽播送信道，如是數(shù)據(jù)對象信息〔其中包含最近播送索引段的到達時間〕，那么轉(zhuǎn)入休眠狀態(tài)直到下一網(wǎng)格索引信息到來時再進入播送信道。2〕獲取網(wǎng)格索引信息。3〕計算以q為中心、以r為半徑的區(qū)域范圍所關(guān)聯(lián)的全部網(wǎng)格，稱之為候選網(wǎng)格。4〕將候選網(wǎng)格按播送時間先后順序排序，并建立一個對象數(shù)組。5〕從第一個候選網(wǎng)格開場對每個網(wǎng)格進展如下操作：①挪動設(shè)備保持休眠狀態(tài)；②當網(wǎng)格被播送時客戶端進入信道；③獲取網(wǎng)格中的全部對象放入數(shù)組。6〕對于數(shù)組中的每個對象做以下操作：判斷對象與查詢點的間隔dist〔o.l，q.l〕是否超過半徑r，假設(shè)dist〔o.l，q.l〕≤r，那么將其放入結(jié)果集C；否那么對下一個對象進展判斷。7〕返回結(jié)果集C。SRQ算法主要包括以下3個步驟：步驟1偵聽播送信道，獲取第一份網(wǎng)格索引，根據(jù)查詢點q的坐標和查詢區(qū)域半徑r，計算出與查詢區(qū)域有穿插的網(wǎng)格作為候選網(wǎng)格，從而過濾掉查詢范圍之外的網(wǎng)格。通過該索引的指針數(shù)組，用戶獲得了所有候選網(wǎng)格的下一次播送時間。步驟2客戶端將所有候選網(wǎng)格按播送時間先后順序排序，然后等待第一個候選網(wǎng)格被播送，在等待過程中挪動設(shè)備保持休眠狀態(tài)。當?shù)谝粋€候選網(wǎng)格到來時用戶偵聽播送信道，獲得該網(wǎng)格的所有對象。重復(fù)以上過程，直到獲得所有候選網(wǎng)格的候選對象。步驟3客戶端計算所有候選對象的位置與查詢點的間隔，如對象間隔查詢點超過查詢半徑那么進展剪枝，從而得到最終準確查詢結(jié)果集。3實驗這局部通過模擬實驗評估RQGSI的算法性能。選擇一種基于R樹的空間索引RI方法進展比照，此方法采用R樹來劃分和索引數(shù)據(jù)對象，各節(jié)點按層次遍歷的順序播送。選取數(shù)據(jù)播送系統(tǒng)中訪問時間〔AccessTime，AT〕和調(diào)諧時間〔TuningTime，TT〕兩個最重要的性能指標作為評價標準。3.2實驗結(jié)果及分析3.2.1實驗1：網(wǎng)格劃分S的影響局部，用戶可以很快過濾掉不在查詢范圍內(nèi)的對象；在AT上，RQGSI采用的是局部索引m次分布形式，且按Hilbert曲線填充順序調(diào)度網(wǎng)格使得用戶需訪問的數(shù)據(jù)對象盡可能連續(xù)地被播送，比RI層次組織形式的數(shù)據(jù)聚集性強。由于RI索引構(gòu)造與網(wǎng)格劃分大小無關(guān)，因此圖中RI方法的TT和AT保持不變。3.2.2實驗2：數(shù)據(jù)對象個數(shù)N的影響設(shè)定查詢半徑為0.05D，S=64。由圖7〔a〕可見，兩種算法的調(diào)諧時間都有所增加，但RQGSI索引的TT優(yōu)于RI方法，這是由于RQGSI不僅在效勞器端對TT進展了優(yōu)化，而且在客戶端對查詢對象進展了過濾和剪枝，從而進一步縮短了TT。在圖7〔b〕中，數(shù)據(jù)對象個數(shù)的增加必然會加大播送周期的長度，延長用戶的訪問時間。雖然兩個算法訪問時間都有所增加，但RQGSI算法采用了Hilbert曲線填充規(guī)那么進展調(diào)度，因此與RI算法相比，RQGSI算法的訪問效率更高。3.2.3實驗3：查詢半徑r的影響4結(jié)語為了實現(xiàn)無線播送環(huán)境下快速且低能耗的空間范圍查詢，提出了一種基于網(wǎng)格空間索引的范圍查詢處理算法。算法在效勞器端設(shè)計了網(wǎng)格空間索引構(gòu)造及〔1，m〕索引分布形式來縮短調(diào)諧時間；為進步訪問效率，對劃分后的網(wǎng)格按Hilbert曲線填充規(guī)那么進展了調(diào)度；在客戶端設(shè)計了查詢處理算法以進一步優(yōu)化調(diào)諧時間。模擬實驗考察了算法的調(diào)諧時間和訪問時間，并與RI算法進展比擬。實驗結(jié)果說明本文算法與RI算法相比在調(diào)諧時間上降低約10%，在訪問時間上降低原文為“提升〞應(yīng)改為降低約8%。下一步研究將考慮關(guān)鍵字因素，以更好地適用于范圍查詢應(yīng)用。參考文獻：2022JointInternationalConferencesonAsiaPacificWebandWebAgeInformationManagement，LNCS5446.Berlin：Springer，2022：27-38.[8]LIUCM，F(xiàn)USY.EffectiveprotocolsforkNNsearchonbroadcastmultidimensionalindextrees[J].Inf