交通路網(wǎng)中移動(dòng)對(duì)象的QMon-tree索引技術(shù)研究.pdf

1、隨著移動(dòng)4G的普及以及大數(shù)據(jù)時(shí)代的到來(lái),在基于位置服務(wù)的功能基礎(chǔ)上，產(chǎn)生了眾多具有定位功能的無(wú)線手持終端，這些革命性變化讓人們的生活出行越來(lái)越方便。移動(dòng)對(duì)象通過(guò)無(wú)線設(shè)備主動(dòng)或被動(dòng)向移動(dòng)對(duì)象數(shù)據(jù)庫(kù)(moving objects database，MOD)傳送當(dāng)前位置信息,信息用戶通過(guò)MOD所提供的接口可以查詢移動(dòng)對(duì)象的歷史、現(xiàn)在和未來(lái)位置信息。MOD強(qiáng)大的市場(chǎng)實(shí)用性，以至其在交通管理、基于位置的服務(wù)等領(lǐng)域有著廣泛的應(yīng)用。目前，市場(chǎng)上較成熟

2、的索引模型對(duì)于交通網(wǎng)絡(luò)中移動(dòng)對(duì)象索引絕大多數(shù)采用分別建立索引樹來(lái)實(shí)現(xiàn)，其對(duì)道路網(wǎng)絡(luò)的索引常常不能滿足查詢的效率。故針對(duì)移動(dòng)對(duì)象索引的研究變得具有實(shí)際價(jià)值。
　　本文深入分析了現(xiàn)有基于交通網(wǎng)絡(luò)中移動(dòng)對(duì)象的索引模型，然后分別研究了典型交通路網(wǎng)模型和移動(dòng)對(duì)象索引技術(shù)，在考慮實(shí)際路網(wǎng)不規(guī)則性的同時(shí)，充分利用四叉樹結(jié)構(gòu)特點(diǎn)，提出了一種改進(jìn)的面向路網(wǎng)中移動(dòng)對(duì)象索引結(jié)構(gòu)QMon-tree（Quad-Moving Objects in Netwo

3、rks Tree）。QMon-tree結(jié)構(gòu)為：上層為一個(gè)改進(jìn)的四叉樹網(wǎng)格平面空間索引結(jié)構(gòu)，外加一個(gè)鏈表，中間是一層2DR-tree，底部由移動(dòng)對(duì)象hash部分組成。上層改進(jìn)的四叉樹機(jī)制用來(lái)索引整個(gè)道路網(wǎng)絡(luò)所在的平面空間區(qū)域，通過(guò)引入基于密度的聚類算法將路網(wǎng)空間劃分成多級(jí)子索引空間，并對(duì)應(yīng)于每個(gè)四叉樹葉子結(jié)點(diǎn)，其子結(jié)點(diǎn)設(shè)有閥值；鏈表用于存儲(chǔ)道路真實(shí)信息，每條路段分別指向下層2DR-tree森林；中間層2DR-tree中結(jié)點(diǎn)按時(shí)間順序存放著

4、移動(dòng)對(duì)象軌跡的位置信息，該層主要負(fù)責(zé)移動(dòng)對(duì)象的歷史與現(xiàn)在信息的索引；移動(dòng)對(duì)象 hash部分由 hash表和動(dòng)態(tài)單向循環(huán)鏈表組成，主要負(fù)責(zé)索引移動(dòng)對(duì)象未來(lái)時(shí)刻的位置信息。對(duì)移動(dòng)對(duì)象將來(lái)位置預(yù)測(cè)使用分段三次插值算法，并將獲取的離散軌跡點(diǎn)進(jìn)行連續(xù)化，從而提高對(duì)位置預(yù)測(cè)的精確度。通過(guò)仿真及模擬實(shí)驗(yàn)結(jié)果表明，QMon-tree索引結(jié)構(gòu)能夠有效降低四叉樹的高度，從而提高道路網(wǎng)絡(luò)搜索的速度，使得查詢效率變得更加高效，同時(shí)通過(guò)分段三次曲線擬合將來(lái)位置軌