移動(dòng)環(huán)境下位置相關(guān)查詢關(guān)鍵技術(shù)研究.pdf

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

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

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

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