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 客戶端計算所有候選對象的位置與查詢點的距離，如對象距離查詢點超過查詢半徑則進行剪枝，從而得到最終精確查詢結果集。
仍以例1的範圍查詢來舉例說明客戶端查詢算法，服務器端通過圖5的調度和索引方式來廣播數據對象及索引信息，假設某一時刻客戶端偵聽信道，獲得本周期的第一份網格索引，通過網格劃分信息，用戶求得與查詢區域有關聯的候選網格s33，s34，s44，s43及各網格的下一次廣播時間。接著等待第一個候選網格，在第一個候選網格到來之前客戶端保持休眠狀態，待網格到來時讀取數據對象o12和o13。同理，依次讀取數據對象o3，o5，o7，o6，o10，最後客戶端根據自己所在位置求出查詢範圍內的o13，o7及o6，作為查詢結果集返回給用戶。
3 實驗
這部分通過模擬實驗評估RQGSI的算法性能。選擇一種基於R樹的空間索引RI方法進行對比，此方法采用R樹來劃分和索引數據對象，各節點按層次遍曆的順序廣播。選取數據廣播係統中訪問時間（Access Time，AT）和調諧時間（Tuning Time，TT）兩個最重要的性能指標作為評價標準。
3.1 實驗環境
本實驗通過一個模擬器用C++語言來實現移動數據廣播環境下的範圍查詢。模擬器包括3部分：一台服務器、一個無線廣播信道和一組客戶端。服務器組織網格索引信息和數據對象，並周期性地通過一個可靠廣播信道將索引信息和數據對象廣播給客戶端，客戶端能夠識別廣播數據是否是所需數據。實驗采用隨機生成的300個查詢點進行範圍查詢，取300次查詢結果的平均值作為每組實驗的結果。為簡單起見，實驗中假設無線廣播信道帶寬不變（取核實單位2Mb/s，是3G網絡的常見帶寬），因此AT和TT分別用等待的數據大小和下載的數據大小來表示（以核實單位KB為單位）。係統在一個帶有2GB內存和Pentium 2.2GHZ雙核CPU的計算機上運行。
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的影響