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

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

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

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

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

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