基于不確定性分析的移動對象軌跡估計技術

侯瑞峰+彭敦陸

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

關鍵詞關鍵詞：汽車軌跡；移動對象；不確定性；軌跡估計

DOIDOI：10.11907/rjdk.162788

中圖分類號：TP3-0文獻標識碼：A文章編號文章編號：16727800（2017）004000105

基金項目基金項目：國家自然科學基金項目（61003031）；上海市工程中心建設項目（GCZX14014）

作者簡介作者簡介：侯瑞峰（1990-），男，河南新鄉人，上海理工大學光電信息與計算機工程學院碩士研究生，研究方向為汽車軌跡數據、位置推薦；彭敦陸（1974-），男，上海人，博士，上海理工大學光電信息與計算機工程學院教授，研究方向為大數據管理、Web數據管理、位置服務。0引言

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

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

汽車軌跡的時間不確定性：由于汽車的位置是每隔一段時間記錄一次，所以汽車經過其運動軌跡中的一個指定位置（非記錄點）的準確時間不能確定。如圖1（b）所示，p1和p3是一輛汽車的一條軌跡數據中的兩個相鄰軌跡點，已知這輛汽車在p1和p3之間是直行的，所以會經過點p2。但是不能確定這輛汽車經過p2的準確時間，因為這輛汽車在p1和p3之間不一定是勻速行駛的。

1相關研究

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

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

網格模型：文獻[7]和文獻[8]中提出了一個網格模型。如圖2（b）所示，設定若干個大小相等的正方形網格，汽車在兩個相鄰的軌跡點之間可能經過的位置，限定在連接這兩個軌跡點的線段穿過的網格內。但是確定這些網格的尺寸是一個復雜的問題，因為網格尺寸直接影響到評估汽車可能經過的位置點的準確度和計算量。

緩沖區模型： Trajcevski和Tamassia等在文獻[9]中提出了一個緩沖區模型。如圖2（c）所示，給汽車設定一個緩沖區閾值，汽車在兩個相鄰軌跡點之間可能經過的位置，限定在一個連接這兩個軌跡點的緩沖區內。

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

2算法

2.1定義

定義1軌跡：一條汽車軌跡T是由一輛汽車一次行駛產生的位置點所組成的一個序列。每一個位置點（如點p）的數據包含了經緯度坐標和時間戳p.t等屬性。即：T：p1→p2→...→pn，其中pi.t

參考文獻：[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] 衛澤，李厚樸.顧及高程時計算兩點間大地距離的實用方法[J]. 艦船電子工程，2011，31（8）：5255.[13] 韓京清. 自抗擾控制技術[J]. 前沿科學， 2007（1）：2432.（責任編輯：黃 健）