無線廣播環境下的空間範圍查詢處理
數據技術
作者：馬小琴 彭秀芬 楊利
摘要：為實現無線廣播環境下快速且低能耗的空間範圍查詢，提出了一種基於網格空間索引的範圍查詢處理算法（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 引言
移動通信技術的快速發展和移動設備的廣泛普及，促進了位置相關服務的產生和發展。位置相關查詢是支持位置相關服務的一項關鍵技術，已受到國內外學者的普遍關注，是數據庫領域的一個研究熱點[1-2]。但目前的位置相關查詢處理方法主要基於按需訪問模式，對服務器處理能力及網絡帶寬有嚴格要求，隻能適用於輕負載係統[3-4]。而周期廣播是服務器端主動地通過無線信道將信息廣播給用戶，允許任意數量的用戶同時訪問數據庫，且不必提交用戶信息到服務器，從而具有保護用戶隱私的特性。因此，一些學者開始研究周期廣播環境下的位置相關查詢。
文獻[5]提出了gridpartition索引應用於無線數據廣播環境下的最近鄰查詢，有效地減少了用戶的調諧時間。文獻[6]提出了一種可調節的分布式索引結構，並提出了有效的最近鄰查詢處理算法，同時優化了調諧時間和訪問延時。文獻[7]提出了基於Rtree的索引樹結構來支持k近鄰查詢，該方法雖能優化調諧時間，但訪問延時過長。文獻[8]在 Rtree 結構中增加一些有用信息，通過廣播修改的 Rtree 索引結構來完成k近鄰查詢，該方法在減少調諧時間的同時也保證了較短的訪問時間。文獻[9]提出了一種新的時空查詢處理算法來支持連續k近鄰查詢，有效地節省了移動設備的能量。然而以上算法都不能很好地適用於範圍查詢。文獻[10] 雖提出了一種線性的完全分布式的結構可以支持範圍查詢，但該方法訪問效率不高。因此如何實現周期廣播環境下快速且低能耗的空間範圍查詢是當前亟待解決的問題。
針對以上問題，本文提出一種基於網格空間索引的範圍查詢處理（Range Query based on Grid Spatial Index，RQGSI）算法。該算法在服務器端先將所有數據對象建立網格空間索引，並按（1，m）模式[11]分布索引信息以降低調諧時間，然後采用Hilbert曲線[12]填充規則廣播各網格以縮短訪問時間。客戶端進行範圍查詢時，根據其位置信息和查詢半徑對數據對象進行過濾和剪枝求得最終查詢結果集，從而進一步優化調諧時間。
1 相關知識
1.1 （1，m）索引分布
（1，m）索引分布是數據廣播索引技術中最常見的索引分布模式，該模式將一個周期內的數據平均分為m個數據段，在每個數據段前麵附加一個索引段，如圖1所示。
1.2 Hilbert曲線
Hilbert曲線是空間填充曲線的一種，有效地實現了從多維空間到一維空間的轉換，具有最優的數據聚類特性，即在有效地降低空間維度的同時極大地保證了在多維源空間中相鄰對象在目的一維空間中也相鄰的關係。基本的Hilbert曲線的構造過程如下：首先將一個正方形分割為4個小正方形，接著從左下角的小正方形開始，畫一條線經過所有小正方形，最後到達右下角，該線就為1階Hilbert曲線，如圖2（a）所示。然後將這個正方形分成16個小正方形，同理，從左下角出發遍曆所有的格子最後到達右下角，得到2階Hilbert曲線，如圖2（b）所示。無限多次地迭代後，曲線經過了方格上所有的點，從而得到完整的Hilbert曲線。
Hilbert曲線按照以上填充方法，將整個數據空間劃分為若幹單元格，每個單元格大小相等，並且互不重疊。然後為每個單元格配備一個具有特殊意義的唯一標識符，代表空間中特定的目標對象，從而實現多維空間對象到一維線性目標的一一映射。
2.2 算法思想
RQGSI算法分為服務器端索引及調度算法和客戶端查詢算法兩部分。在服務器端對數據對象建立網格空間索引，並按Hilbert曲線填充規則調度網格，在客戶端設計查詢處理算法進行過濾和剪枝。算法具體由3個階段組成：
1）對數據對象建立網格空間索引，並將索引按（1，m）方式插入到各數據段前端。