面向路網(wǎng)的移動對象間的連續(xù)狀態(tài)查詢算法的研究與實(shí)現(xiàn).pdf

1、隨著基于用戶位置的服務(wù)(Location-Based Service，LBS)研究的日益深入，用戶對LBS的需求日趨豐富。例如在智能交通領(lǐng)域，自動駕駛技術(shù)不僅需要解決普通的位置定位技術(shù)，更重要的是要持續(xù)監(jiān)測車與周圍車輛以及道路上其他物體之間的距離遠(yuǎn)近關(guān)系，保證安全行駛?，F(xiàn)有的查詢處理技術(shù)，如范圍查詢、最近鄰查詢和連續(xù)范圍查詢等，僅僅關(guān)注某一時刻查詢點(diǎn)與被查詢點(diǎn)之間的位置關(guān)系，無法滿足用戶對移動對象之間的連續(xù)狀態(tài)查詢服務(wù)的需求。移動對象間

2、狀態(tài)查詢是指移動對象查詢自身與周圍其他移動對象之間越來越遠(yuǎn)或者越來越近的位置關(guān)系。已有的移動對象間狀態(tài)查詢算法主要包括樸素的狀態(tài)查詢算法與移動對象間的連續(xù)狀態(tài)查詢算法，均是基于歐氏空間，難以直接應(yīng)用于路網(wǎng)環(huán)境。本文提出了面向路網(wǎng)的移動對象間連續(xù)狀態(tài)查詢中的關(guān)鍵算法。針對大規(guī)模的移動對象的應(yīng)用場景，移動對象間的連續(xù)狀態(tài)查詢算法面臨著兩大挑戰(zhàn):一方面如何快速地對海量移動對象定位;另一方面如何在路網(wǎng)環(huán)境下高性能地計算海量移動對象間的距離。針對

3、上述問題，本文做了以下兩方面工作:
　　針對快速定位移動對象位置的問題，本文提出了三種移動對象定位算法?；诼范蝿澐值囊苿訉ο蠖ㄎ凰惴ㄍㄟ^對較長路段進(jìn)行劃分，對子路段構(gòu)造MBRs，建立R樹索引，有效地減少了MBRs之間的重疊區(qū)域和MBRs對無效區(qū)域的覆蓋。基于網(wǎng)格R樹的移動對象定位算法將網(wǎng)格定位的高效性與R樹搜索的高效性結(jié)合起來?；诼肪W(wǎng)拓?fù)涞囊苿訉ο蠖ㄎ凰惴ǎ昧寺肪W(wǎng)拓?fù)浣Y(jié)構(gòu)與基于網(wǎng)格R樹的移動對象定位算法相結(jié)合。實(shí)驗(yàn)對比表明

4、:三種定位算法的性能均優(yōu)于基于R樹的移動對象定位算法。
　　路網(wǎng)環(huán)境下，大規(guī)模移動對象間的距離計算成為制約移動對象間的連續(xù)狀態(tài)查詢的瓶頸。因此，本文從工程角度提出基于距離查詢表的移動對象間距離序列計算算法(calculating distance sequence based on Distance Query Table，DQT)，滿足了移動對象間的連續(xù)狀態(tài)查詢處理的實(shí)時性要求。針對距離查詢表需要內(nèi)存空間較大的問題，對距離查詢表

5、進(jìn)行了空間優(yōu)化，提出了基于空間受限距離查詢表的移動對象間距離序列計算算法(calculating distance sequence based on Limited Space Distance Query Table,LSDQT)。實(shí)驗(yàn)對比表明:兩種算法時間性能均優(yōu)于基于最短路徑算法移動對象間距離序列計算算法。算法LSDQT雖然在計算速度上比DQT算法慢了一個數(shù)量級，但空間受限距離查詢表所需的內(nèi)存空間僅為距離查詢表的1％，LSDQT