移動環(huán)境下位置相關查詢關鍵技術研究.pdf

1、隨著無線通訊技術與定位技術的不斷發(fā)展，對移動對象的跟蹤和定位變得越來越可行。一些新的應用，如交通控制、生物保護、氣象監(jiān)視等都涉及到對連續(xù)移動對象的存儲、查詢與處理需求，這就需要移動對象數據庫技術提供支持。移動對象數據庫是指對移動對象的位置及其它相關信息進行表示與處理的數據庫。位置相關的查詢則是移動數據庫系統(tǒng)最重要的功能之一。位置相關的查詢（LDQ：Location Dependent Query）是指查詢結果依賴于移動用戶的當前位置的查

2、詢。同一個查詢請求，提交的地點不同，返回的結果也可能將不同。傳統(tǒng)的空間數據庫是基于靜態(tài)對象的，沒有時間維度的信息，這意味著所有的屬性都保持它們上一次顯式更新時的值。而在移動數據庫中，移動對象的位置隨時間連續(xù)改變。為了實現對移動對象數據庫中大量移動對象的時空信息的有效組織和管理，就必須研究適合于移動對象數據庫的高效的索引結構與查詢算法。TPR-tree是當前流行的用于查詢移動對象當前及將來某一時刻位置信息的索引結構。由于加入了速度矢量屬性

3、，與傳統(tǒng)的空間索引結構相比TPR-tree更能適應移動對象存儲與查詢的需求。
　　 本文分析了移動環(huán)境下的最近鄰查詢方法，對移動環(huán)境下支持位置相關查詢的常用時空索引TPR-tree的索引結構、構建過程與更新算法進行了研究，在此基礎上給出了TPR-tree的最近鄰查詢算法。對于同一結點下的移動對象，如果其速度比較接近，TPR-tree的查詢效率較高，但是TPR-tree在構建時忽視了同一方向上速度間存在的大小差異，使通過計算得到的

4、結點的包含矩形從某時刻開始不再是其子結點的最小包含矩形，因而可能導致產生大量對于查詢無用的區(qū)域，以致造成查詢效率的降低。針對這一問題，本文在TPR-tree的基礎上提出了一種改進的時空索引結構：VCTPR-tree。VCTPR-tree可以徹底消除這些無用的區(qū)域產生的可能性，從而使查詢時使用的剪枝效率接近最優(yōu)化。具體來說，VCTPR-tree通過引入速度改變時間序列，使結點的包含矩形始終保持為其子結點的最小包含矩形。性能分析顯示，與TP