基于不確定性分析的移動(dòng)對(duì)象軌跡估計(jì)技術(shù)

侯瑞峰+彭敦陸

摘要：移動(dòng)對(duì)象軌跡已成為當(dāng)前移動(dòng)對(duì)象研究中關(guān)注的熱點(diǎn)。移動(dòng)對(duì)象的軌跡數(shù)據(jù)中存在著多種不確定性，如位置不確定性和時(shí)間不確定性。目前對(duì)于汽車軌跡的位置不確定性研究，多數(shù)都是針對(duì)當(dāng)有軌跡點(diǎn)缺失時(shí)，如何確定兩個(gè)汽車行駛軌跡點(diǎn)間可能經(jīng)過的具體地點(diǎn)，而專門針對(duì)汽車在兩個(gè)軌跡點(diǎn)間可能經(jīng)過的路徑，相關(guān)研究還不多。首先在詳細(xì)闡述汽車運(yùn)動(dòng)軌跡中不確定性的基礎(chǔ)上，建立了一個(gè)基于橢圓的路網(wǎng)模型，然后綜合考慮即時(shí)車流量和汽車通過路徑花費(fèi)的時(shí)間，提出了一個(gè)對(duì)可選路徑的評(píng)分算法。利用該算法可以在部分軌跡數(shù)據(jù)丟失的情況下，較好地估計(jì)移動(dòng)對(duì)象的真實(shí)路徑。實(shí)驗(yàn)結(jié)果證明了該算法的有效性。

關(guān)鍵詞關(guān)鍵詞：汽車軌跡；移動(dòng)對(duì)象；不確定性；軌跡估計(jì)

DOIDOI：10.11907/rjdk.162788

中圖分類號(hào)：TP3-0文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）004000105

基金項(xiàng)目基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目（61003031）；上海市工程中心建設(shè)項(xiàng)目（GCZX14014）

作者簡介作者簡介：侯瑞峰（1990-），男，河南新鄉(xiāng)人，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院碩士研究生，研究方向?yàn)槠囓壽E數(shù)據(jù)、位置推薦；彭敦陸（1974-），男，上海人，博士，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院教授，研究方向?yàn)榇髷?shù)據(jù)管理、Web數(shù)據(jù)管理、位置服務(wù)。0引言

無線網(wǎng)絡(luò)通信技術(shù)和全球定位技術(shù)的不斷發(fā)展，為人們研究移動(dòng)對(duì)象的運(yùn)動(dòng)規(guī)律提供了越來越多的技術(shù)支持。目前，在面向移動(dòng)對(duì)象的位置服務(wù)技術(shù)中，汽車作為一種只能在路網(wǎng)中移動(dòng)的特殊對(duì)象，對(duì)其軌跡的研究也得到了人們重視。眾所周知，汽車在行駛過程中，由于受到多種因素影響，會(huì)導(dǎo)致獲得的汽車運(yùn)動(dòng)軌跡數(shù)據(jù)存在一定程度上的不確定性，這種不確定性會(huì)影響后期數(shù)據(jù)分析的準(zhǔn)確性。因此，人們針對(duì)汽車移動(dòng)軌跡的不確定性進(jìn)行了大量研究。導(dǎo)致汽車軌跡數(shù)據(jù)存在時(shí)空不確定性的原因很多，主要包括數(shù)據(jù)采集過程中產(chǎn)生的不確定性、軌跡數(shù)據(jù)記錄過于稀疏（如汽車以60km/h的速度行駛，每2min記錄一次汽車位置，這輛汽車在兩個(gè)連續(xù)的軌跡點(diǎn)之間行駛的路程則是2 000m）、數(shù)據(jù)傳輸過程中帶來的不確定性等[1]。在汽車運(yùn)動(dòng)軌跡中，最普遍的不確定性是時(shí)空不確定性[2]。時(shí)空不確定性又可分為空間不確定性和時(shí)間不確定性。

汽車軌跡的空間不確定性，又稱為位置不確定性，在汽車的兩個(gè)相鄰軌跡點(diǎn)之間，不能確定這輛汽車經(jīng)過的具體位置。如圖1（a）所示，p1和p2是一輛汽車一條軌跡數(shù)據(jù)中的兩個(gè)相鄰軌跡點(diǎn)，在兩個(gè)軌跡點(diǎn)之間，不能確定汽車的行駛路徑。

汽車軌跡的時(shí)間不確定性：由于汽車的位置是每隔一段時(shí)間記錄一次，所以汽車經(jīng)過其運(yùn)動(dòng)軌跡中的一個(gè)指定位置（非記錄點(diǎn)）的準(zhǔn)確時(shí)間不能確定。如圖1（b）所示，p1和p3是一輛汽車的一條軌跡數(shù)據(jù)中的兩個(gè)相鄰軌跡點(diǎn)，已知這輛汽車在p1和p3之間是直行的，所以會(huì)經(jīng)過點(diǎn)p2。但是不能確定這輛汽車經(jīng)過p2的準(zhǔn)確時(shí)間，因?yàn)檫@輛汽車在p1和p3之間不一定是勻速行駛的。

1相關(guān)研究

目前國內(nèi)外研究者在估算產(chǎn)生不確定性軌跡數(shù)據(jù)的汽車經(jīng)過每條可選路徑的概率時(shí)，大多采用簡單平均概率的方法——經(jīng)過某條可選路徑的概率等于1除以可選路徑總數(shù)[3]，而沒有考慮各條可選路徑的特殊性和實(shí)時(shí)路況條件，如各條路徑的長度和道路擁堵情況等。但是，在兩個(gè)相鄰的軌跡點(diǎn)間，如何評(píng)估汽車可能經(jīng)過的位置點(diǎn)，人們提出了一些有價(jià)值的模型和方法。

橢圓模型：Pfoser和Tryfona[46]提出了一個(gè)基于最大速度的橢圓模型。假設(shè)各條道路都有一個(gè)對(duì)應(yīng)的最大速度，代表汽車在道路上行駛的最高限速，則在汽車運(yùn)動(dòng)軌跡的兩個(gè)相鄰軌跡點(diǎn)之間，汽車可能經(jīng)過的位置限定在一個(gè)橢圓內(nèi)。此橢圓的焦點(diǎn)為這兩個(gè)軌跡點(diǎn)對(duì)應(yīng)的位置，長軸等于兩個(gè)軌跡點(diǎn)的時(shí)間差與最大速度的乘積。如圖2（a）所示，焦點(diǎn)F1與F2是這兩個(gè)相鄰軌跡點(diǎn)對(duì)應(yīng)的位置。

網(wǎng)格模型：文獻(xiàn)[7]和文獻(xiàn)[8]中提出了一個(gè)網(wǎng)格模型。如圖2（b）所示，設(shè)定若干個(gè)大小相等的正方形網(wǎng)格，汽車在兩個(gè)相鄰的軌跡點(diǎn)之間可能經(jīng)過的位置，限定在連接這兩個(gè)軌跡點(diǎn)的線段穿過的網(wǎng)格內(nèi)。但是確定這些網(wǎng)格的尺寸是一個(gè)復(fù)雜的問題，因?yàn)榫W(wǎng)格尺寸直接影響到評(píng)估汽車可能經(jīng)過的位置點(diǎn)的準(zhǔn)確度和計(jì)算量。

緩沖區(qū)模型： Trajcevski和Tamassia等在文獻(xiàn)[9]中提出了一個(gè)緩沖區(qū)模型。如圖2（c）所示，給汽車設(shè)定一個(gè)緩沖區(qū)閾值，汽車在兩個(gè)相鄰軌跡點(diǎn)之間可能經(jīng)過的位置，限定在一個(gè)連接這兩個(gè)軌跡點(diǎn)的緩沖區(qū)內(nèi)。

受限網(wǎng)絡(luò)模型：在文獻(xiàn)[10]和文獻(xiàn)[11]中，作者把汽車的運(yùn)動(dòng)軌跡數(shù)據(jù)映射到路網(wǎng)上，然后把汽車可能經(jīng)過的位置限制在路網(wǎng)的道路上。如圖2（d）所示，受限網(wǎng)絡(luò)模型使汽車可能經(jīng)過的位置點(diǎn)范圍得到了很大程度的壓縮。

2算法

2.1定義

定義1軌跡：一條汽車軌跡T是由一輛汽車一次行駛產(chǎn)生的位置點(diǎn)所組成的一個(gè)序列。每一個(gè)位置點(diǎn)（如點(diǎn)p）的數(shù)據(jù)包含了經(jīng)緯度坐標(biāo)和時(shí)間戳p.t等屬性。即：T：p1→p2→...→pn，其中pi.t

參考文獻(xiàn)：[1] PROSER D， JENSEN C. Capturing the uncertainty of movingobject representations [C]. Hong Kong：Springer， 1999：111131.

[2] ZHENG YU. Computing with spatial trajectories [M]. Compting with Spatial Trajectories. Springer Publishing Company： Incorporated， 2011.

[3] CHENG R， KALASHNIKOV D， PRABHAKAR S. Evaluating probabilistic queries over imprecise data [J]. Proceedings of Acm Sigmod，2003：551562.

[4] PROSER D， TRYFONA N. Capturing fuzziness and uncertainty of moving objects representation [M]. Berlin Heidelberg： Springer， 2001：112126.

[5] HORNSBY K， EGENHOFER M J. Modeling moving objects over multiple granularities [J]. Annals of Mathematics&Artificial Intelligence， 2002， 36（12）：177194.

[6] KUIJPERS B， OTHMAN W. Trajectory databases：Data models， uncertainty and complete query languages [J]. Journal of Computer & System Sciences， 2010， 76（7）：538560.[7] LIU HECHEN， SCHNEIDER M. Querying moving objects with uncertainty in spatiotemporal databases [C]. Database Systems for Advanced Applicationsinternational Conference， 2011：357371.

[8] PELEKIS N， KOPANAKIS I， KOTSIFAKOS E， et al. Clustering trajectories of moving objects in an uncertain world [C]. Ninth IEEE International Conference on Data Mining， 2009：417427.

[9] ZHANG MEIHUI， CHEN SU， JENSEN C， et al. Effectively indexing uncertain moving objects for predictive queries [J]. Proceedings of the VLDB Endowment， 2009，2（1）：11981209.

[10] DING ZHIMING， GUTING RH. Uncertainty management for network constrained moving objects [M]. Berlin Heidelberg： Springer， 2004：411421.

[11] DING ZHIMING. UTRtree： an index structure for the full uncertain trajectories of networkconstrained moving objects [C]. Ninth International Conference on Mobile Data Management， 2008：3340.

[12] 衛(wèi)澤，李厚樸.顧及高程時(shí)計(jì)算兩點(diǎn)間大地距離的實(shí)用方法[J]. 艦船電子工程，2011，31（8）：5255.[13] 韓京清. 自抗擾控制技術(shù)[J]. 前沿科學(xué)， 2007（1）：2432.（責(zé)任編輯：黃 ?。?