基于R樹移動對象預測位置查詢

胡國建 張 祺 夏圣凱

（浙江海洋學院數理與信息學院 浙江 舟山 316000）

0 引言

移動計算、無線通訊和定位技術的快速發展使得跟蹤和管理實際生活中的移動對象軌跡成為了現實。隨著移動通信、移動定位技術的迅速發展和移動終端設備（如車載、手持設備等）的不斷普及，越來越多的應用（如車載導航、智能交通、實時監控、作戰指揮控制等）要求在移動過程中實現對地理空間信息的實時獲取。移動對象軌跡是物體在某一個時間段內所經過的路線。對于移動對象在一定時間內的預測位置查詢處理技術成為了當前涉及移動對象軌跡信息的時空數據庫研究領域的重點與熱點之一。

傳統的B樹已經不能完全的滿足于社會進步，人們需求。R樹在數據庫等領域做出的功績是非常顯著的。它把B樹的思想很好的擴展到了多維空間，采用了B樹分割空間的思想，并在添加、刪除操作時采用合并、分解結點的方法，保證樹的平衡性。對移動對象位置查詢索引方法大體分為兩類：一類為對歷史位置的提取；一類為對當前位置提取和對將來位置的預測。它很好的解決了在高維空間搜索等問題。在BiN-tree中，引入對象標識輔助索引，搜索B tree，直接獲取被更新對象在TPN-tree中的存取路徑（對象的更新數據可簡化為（Old，P，V）），然后執行刪除和插入操作。能夠有效而又簡單的解決移動對象預測位置的查詢。

移動對象是指對象的空間數據隨時間的變化而連續變化的對象，它主要可以分為移動點（moving point）和移動區域（moving region）。移動點是指隨時間而變化的空間對象的位置 （position）。對移動點的查詢主要是要確定移動對象的位置。移動區域是指隨時間而變化的空間對象的位置及其形狀。對移動區域的查詢主要是要確定在特定時間內移動對象的位置或形狀。

移動對象數據庫通常管理著數量非常龐大的移動對象。在查詢處理時如果逐個掃描所有的移動對象顯然將會極大地影響系統的性能。移動對象的索引方法通常借鑒于空間數據索引技術，不同之處在于移動對象的索引中有一維必然是時間維。已提出的移動對象索引方法主要分為兩類：1）索引移動對象過去與當前的位置；2）索引移動對象當前與將來的位置。[1]基于R-tree的移動對象索引技術。

迄今為止，一些好的關于移動對象索引技術的綜述已被給出。例如，Gaede等[12]給出了一個關于空間數據庫中各種多維訪問方法的綜述；Mokbel等[13]給出了一個關于已有的各種時空訪問方法的綜述。根據各種時空訪問方法所支持的查詢類型與時間，Mokbel等將時空索引方法分成兩類：索引過去、索引現在與預測將來位置，并對每類方法進行了簡單討論。另外，他們還簡單地介紹了一些開放的并且可利用的索引工具，例如，數據庫系統的通用查找樹 （Generalized Search Tree for Database Systems，GiST）和空間劃分的通用查找搜索樹（Space-partitioning Generalized Search Tree，SP-GiST）等，這些索引工具可以幫助我們實現各種不同的時空訪問方法。最近，Manolopoulos等系統性給出了一個基于R-tree及其變體的移動對象索引方法的綜述。他們詳細討論了R-tree及其變體的適用性，精確的代價模型，諸如并發控制、恢復以及并行處理等的實現問題等，并且還介紹了由一些數據庫開發商所實現的R-tree及其變體。雖然他們給出了一個好的基于R-tree及其它的變體的各種移動對象索引技術的綜述，但是卻沒有考慮基于四叉樹（quadtree）的移動對象索引技術和其它的移動對象索引技術；下面我們將分別對三類移動對象索引技術及其各自相應的移動對象索引方法分別進行簡單的討論。[4]

1 預測索引方法

自從1984年Guttma n提出R-樹以后，人們以此為基礎，針對不同的時空操作需求提出了各種改進方案，逐漸形成R樹家族。其中，對移動對象位置查詢索引方法大體分為兩類：一類為對歷史位置的提取；一類為對當前位置提取和對將來位置的預測。

1.1 擴展TPR-tree使其支持對象標識查詢——ETPR_tree ETPR-tree更新算法

我們假定Old是所有移動對象的唯一標識，即不同對象的Oid不同。更新結構為（Oid，（P…，V…））更新算法分為3個步驟：

步驟1：對象標識Oid查詢。

步驟2：刪除過時的對象。

步驟3：插入更新后的對象。

對象標識Oid查詢以更新對象的標識Oid為索引樹的查找目標，確定此對象在樹葉子結點中的位置。顯然只需要用IdBR指示樹的搜索方向，計算僅涉及一個維度（見算法1）。刪除和插入處理與TRP-tree類似。

算法1：對象標識查詢算法

1.2 雙索引結構——R-tree

解決TPR-tree不能有效支持對象標識查詢缺陷的另一種方法是采用雙索引結構：構建以Oid為關鍵字 （key）的B+-tree作為輔助索引，原有的TPR-tree結構和相應算法不變。在B+-tree中，葉子結點中的每一條目記錄對象標識與此對象在TPR-tree的相應位置，即（Oid，ptr），其結構如圖1所示。

圖1 R-Tree索引結構

在BiN-tree中，引入對象標識輔助索引，搜索B+-tree，直接獲取被更新對象在TPN-tree中的存取路徑（對象的更新數據可簡化為（Old，P，V）），然后執行刪除和插入操作（見算法2）、R-tree的更新計算復雜度及結點訪問數（I/O量）明顯低于TPN-tree。當然，B+-tre的同步更新會產生附加的I/O量，但其I/O量較小（等于B+-tree的高度）。算法2的復雜度為O（H+H2）次I/O，其中H和H2分別為B+-tree與TPN-tree的高度。

算法2：BiN-tree更新算法

1.3 索引現在與將來

二元變換：Kollios等使用二元變換 （Duality transformation）把在時空域上的移動對象的跡線轉換到二維空間上的點。該索引方法的主要設計思想是用方程式xt=at+b來表示一個二維空間中的點 （a，b），其中a代表速度并作為水平維；而b代表參考位置并作為垂直維。由于移動對象雜亂的分布在二元空間上，所以基于kd樹（kd-tree）的空間索引方法被用來代替R-tree。由于在初始的時空空間里的矩形區域查詢被轉換成在二元速度位置空間里的多邊形區域查詢，所以由Goldstein等提出的算法可被用來有效的處理區域查詢。

TPR-tree：Saltenis等提出了基于R*-tree的索引技術，稱為時參R（TimeParameterized R-tree，TPR-tree）。TPR-tree能有效的索引在一維，二維，三維空間中的移動點對象的現在與預測的將來位置。TPR-tree考慮移動對象的速度與方向來預測移動對象在不久將來的大致位置[2]。并且通過考慮在樹結構中可計算的位置來減少時間函數的頻繁更新問題。同時，TPR-tree的更新算法也能使其自動的調整以適應于一個動態變化的數據集。

PR-tree：參數化R樹 （Parametric R-tree，PR-tree）與TPR-tree類似，但是PR-tree考慮用參數化矩形來表示移動對象的空間區域。每個參數化矩形都有一個時間間隔來表示移動對象運動的開始時間和結束時間。與TPR-tree考慮連續運動的對象不同，PR-tree還考慮移動對象的結束時間。因此，一個移動對象在空間上用一個多邊形來表示而不是連續的運動跡線。給定運動的結束時間，一系列的移動對象可以用可計算的多邊形來表示。

MP-tree：Lee等提出了一棵移動點樹（Moving Point Tree，MP-tree），它是一個用來索引移動點對象數據的基于R-tree的索引方法。MP-tree使用投影操作（projection operation）來有效的支持諸如時間片查詢與區域查詢等的查詢操作。但是使用投影操作帶來的一個缺點就是當結點被輸入時需要花費更多的時間來進行投影操作的存儲，而優點則是能有效的處理分裂與查詢操作，并且具有高效的空間利用率。另外，通過鏈表的使用，MP-tree還可以有效的處理基于跡線的查詢。[2]

2 預測查詢方法

R-tree樹的構造以下面2個觀察為基礎。1）大部分移動對象在大部分時間內是在某個地理范圍內或其附近運動的，如海上船舶。我們將這種運動速度較慢的移動對象定義為自由移動對象；2）移動對象的運動一般與地理環境相關。船舶移動對象通常以無規則等線狀運動，由于海島、燈塔、航道等地理環境信息很少發生改變，因此，我們能利用空間面狀和線狀目標這一個相對穩定的因素來建立索引空間的靜態部分。同時，將移動對象與其所處的地理對象相關聯，針對移動對象構造索引空間的動態部分。通過減少索引結構的動態變化來降低更新代價，并實現對移動對象的快速檢索。在持續移動對象的位置跟蹤和不久的將來位置預測系統中（如智能導航），一般在移動對象上安裝定位設備（GPS），這些定位設備能有效地記錄移動物體的運動狀態（如當前所處的位置坐標、運動的速度和方向等信息）。

2.1 在對將來位置的預測

指數平滑法[5]：雖然單個移動對象的運動是不斷發生改變的，但是由于運動的連續性，移動對象當前時刻的運動。速度是和它在前幾個時刻的運動速度密切相關的。因此，可以根據移動對象歷史時間戳的空間位置來計算移動對象在每個歷史時間段內的運動速度，然后利用歷史速度數據來預測該對象下一時刻的運動速度。并由此計算出移動對象在將來時刻的空間位置，R預測索引表達如圖2。

圖2 R預測索引表達

圖3 R樹預測的目錄

本應用中預測時間范圍限制在當前時刻以后的10min內，因此，采用需求數據少、跟蹤能力較強的指數平滑法（Exponential Smoothing，ES）來實現移動對象將來時刻的位置預測。在指數平滑法中，預測成功的關鍵是平滑系數A的選擇。a的大小規定了在新預測值中新數據和原預測值所占的比例，代表了預測模型對時間序列數據變化的反應速度和對預測模型修勻誤差的能力，R樹預測的目錄如圖3。本文采用如下公式來確定平滑系數a：

其中：

式中：Vt表示當前時刻t速度的觀測值；Vt－1（i=1，2，，，n）表示t時刻之前的第i個時刻的速度；n為計算a時選取的觀測值的個數。n值過大計算代價高，n值過小不能正確反映數據變化。在本應用中，選取某移動對象在某段道路上的當前時刻前的10個時間戳位置來計算a值。K為預測時選擇的當前時間戳之前的時間戳的數量，可以根據下式計算：

K=（2-a）/a

2.2 將來時間戳的位置預測

對于“查詢移動對象M（at，bt）在距現在時刻t不久的下一時刻t+1的位置（at＋1，bt＋1）”的將來時刻查詢，其方法如下：

（1）首先，找到移動對象M所關聯的空間目標，若是面狀目標，則M是類靜止對象，根據采用ES方法進行將來時間戳的速度預測計算其在t時刻的運動速度Vt，則移動對象M在t+1時刻的位置范圍可如下計算：

（2）若移動對象M所關聯的目標是路段目標S，則M是快速運動對象。首先，根據采用ES方法進行將來時間戳的速度預測計算其在t時刻的運動速度Vt，計算M在時間間隔△t內的移動距離d=Vt△t，判斷M是否仍然在現有的路段內，若在的話，M在t+1時刻的位置如下計算：

其中：（As，Bs，），（At，Bt）為路段L的起點和終點坐標。

若M不在現有的路段內，則首先依據所設定的運動規則（如最短路徑規則、首次匹配規則等），判斷移動對象M將經過的路段，計算經過每條路段所需的時間，并最終確定時刻t+1時M所在的路段L′，再計算其在t+1時刻的位置：

其中：（A′s，B′s），（A′t，B′）為路段L′的起點和終點坐標；t′為M途經路段（除L′外）所需時間之和。[3]

3 性能分析

R-tree用C++編程實現，以TPR-tree源代碼為基礎，并做了適當修改和擴充，因此，我們利用TPR-tree的數據生成器來模擬移動對象的運動。TPN-tree的數據生成器通過給定一些參數來模擬物體在二維空間的運動，生成均勻分布或非均勻分布的數據集。利用此生成器模擬10000個移動對象（如汽車）在范圍為1000×1000km。交通路線網絡中的運動。此路線網絡目的地數目（ND）為20，每個移動對象的運動速度在0km/min和3km/min間均勻分布（加速、減速和最大最小速度），運動方向隨機，速度更新平均時間間隔UI=60min（更新時間間隔在0和2UI間均勻分布），總時長為600min，查詢窗口w分別為0、30、60、120、240、480生成6組性能測試混合事務工作流。對BiN-tree執行上述6組事務流（更新操 作分別為 97837，98671，98767，97985，97345和 98757次），其平均I/0次數基本上不變動。執行2400次窗口查詢的平均I/0次數也是基本不變動。[3]

4 結束語

在本文提出R樹的計算方法實用并針對于移動對象預測位置的查詢，并且引用指數平滑方法實現了移動對象運動信息未知情況下的將來時刻的位置的預測查詢。R-tree結構能在保證查詢性能的前提下，還能有效地解決TPR—tree的更新缺陷。由于R—tree并不改變TPR-tree原有的算法和結構（對對象標識建立B+-tree索引），因此這種建立輔助索引的方法可以應用到現有的其他索引結構中，解決其存在的更新缺陷。對于移動對象位置預測查詢很有效果。

［1］Chen L，Ozsu M T，Oria V.Robust and fast similarity search for moving object trajectories.In Proc.the ACM SIGMOD Int.Conf.on Management of Data，Baltimore，Maryland[M].2005：491-502.

［2］趙卿松，盧炎生.移動對象位置預測的索引方法[C].2006：5-6

［3］詹平，郭菁，郭薇.基于時空索引結構的移動對象將來時刻位置預測[J].2007：6-7.

［4］李春.移動對象軌跡的最近鄰居查詢研究[D].2007：65-68.

［5］唐炎森.確定平滑系數的新方法[J].統計與信息論壇，1997（3）：15-18.