基于R樹(shù)移動(dòng)對(duì)象預(yù)測(cè)位置查詢(xún)

胡國(guó)建 張 祺 夏圣凱

（浙江海洋學(xué)院數(shù)理與信息學(xué)院 浙江 舟山 316000）

0 引言

移動(dòng)計(jì)算、無(wú)線通訊和定位技術(shù)的快速發(fā)展使得跟蹤和管理實(shí)際生活中的移動(dòng)對(duì)象軌跡成為了現(xiàn)實(shí)。隨著移動(dòng)通信、移動(dòng)定位技術(shù)的迅速發(fā)展和移動(dòng)終端設(shè)備（如車(chē)載、手持設(shè)備等）的不斷普及，越來(lái)越多的應(yīng)用（如車(chē)載導(dǎo)航、智能交通、實(shí)時(shí)監(jiān)控、作戰(zhàn)指揮控制等）要求在移動(dòng)過(guò)程中實(shí)現(xiàn)對(duì)地理空間信息的實(shí)時(shí)獲取。移動(dòng)對(duì)象軌跡是物體在某一個(gè)時(shí)間段內(nèi)所經(jīng)過(guò)的路線。對(duì)于移動(dòng)對(duì)象在一定時(shí)間內(nèi)的預(yù)測(cè)位置查詢(xún)處理技術(shù)成為了當(dāng)前涉及移動(dòng)對(duì)象軌跡信息的時(shí)空數(shù)據(jù)庫(kù)研究領(lǐng)域的重點(diǎn)與熱點(diǎn)之一。

傳統(tǒng)的B樹(shù)已經(jīng)不能完全的滿(mǎn)足于社會(huì)進(jìn)步，人們需求。R樹(shù)在數(shù)據(jù)庫(kù)等領(lǐng)域做出的功績(jī)是非常顯著的。它把B樹(shù)的思想很好的擴(kuò)展到了多維空間，采用了B樹(shù)分割空間的思想，并在添加、刪除操作時(shí)采用合并、分解結(jié)點(diǎn)的方法，保證樹(shù)的平衡性。對(duì)移動(dòng)對(duì)象位置查詢(xún)索引方法大體分為兩類(lèi)：一類(lèi)為對(duì)歷史位置的提??；一類(lèi)為對(duì)當(dāng)前位置提取和對(duì)將來(lái)位置的預(yù)測(cè)。它很好的解決了在高維空間搜索等問(wèn)題。在BiN-tree中，引入對(duì)象標(biāo)識(shí)輔助索引，搜索B tree，直接獲取被更新對(duì)象在TPN-tree中的存取路徑（對(duì)象的更新數(shù)據(jù)可簡(jiǎn)化為（Old，P，V）），然后執(zhí)行刪除和插入操作。能夠有效而又簡(jiǎn)單的解決移動(dòng)對(duì)象預(yù)測(cè)位置的查詢(xún)。

移動(dòng)對(duì)象是指對(duì)象的空間數(shù)據(jù)隨時(shí)間的變化而連續(xù)變化的對(duì)象，它主要可以分為移動(dòng)點(diǎn)（moving point）和移動(dòng)區(qū)域（moving region）。移動(dòng)點(diǎn)是指隨時(shí)間而變化的空間對(duì)象的位置 （position）。對(duì)移動(dòng)點(diǎn)的查詢(xún)主要是要確定移動(dòng)對(duì)象的位置。移動(dòng)區(qū)域是指隨時(shí)間而變化的空間對(duì)象的位置及其形狀。對(duì)移動(dòng)區(qū)域的查詢(xún)主要是要確定在特定時(shí)間內(nèi)移動(dòng)對(duì)象的位置或形狀。

移動(dòng)對(duì)象數(shù)據(jù)庫(kù)通常管理著數(shù)量非常龐大的移動(dòng)對(duì)象。在查詢(xún)處理時(shí)如果逐個(gè)掃描所有的移動(dòng)對(duì)象顯然將會(huì)極大地影響系統(tǒng)的性能。移動(dòng)對(duì)象的索引方法通常借鑒于空間數(shù)據(jù)索引技術(shù)，不同之處在于移動(dòng)對(duì)象的索引中有一維必然是時(shí)間維。已提出的移動(dòng)對(duì)象索引方法主要分為兩類(lèi)：1）索引移動(dòng)對(duì)象過(guò)去與當(dāng)前的位置；2）索引移動(dòng)對(duì)象當(dāng)前與將來(lái)的位置。[1]基于R-tree的移動(dòng)對(duì)象索引技術(shù)。

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

1 預(yù)測(cè)索引方法

自從1984年Guttma n提出R-樹(shù)以后，人們以此為基礎(chǔ)，針對(duì)不同的時(shí)空操作需求提出了各種改進(jìn)方案，逐漸形成R樹(shù)家族。其中，對(duì)移動(dòng)對(duì)象位置查詢(xún)索引方法大體分為兩類(lèi)：一類(lèi)為對(duì)歷史位置的提?。灰活?lèi)為對(duì)當(dāng)前位置提取和對(duì)將來(lái)位置的預(yù)測(cè)。

1.1 擴(kuò)展TPR-tree使其支持對(duì)象標(biāo)識(shí)查詢(xún)——ETPR_tree ETPR-tree更新算法

我們假定Old是所有移動(dòng)對(duì)象的唯一標(biāo)識(shí)，即不同對(duì)象的Oid不同。更新結(jié)構(gòu)為（Oid，（P…，V…））更新算法分為3個(gè)步驟：

步驟1：對(duì)象標(biāo)識(shí)Oid查詢(xún)。

步驟2：刪除過(guò)時(shí)的對(duì)象。

步驟3：插入更新后的對(duì)象。

對(duì)象標(biāo)識(shí)Oid查詢(xún)以更新對(duì)象的標(biāo)識(shí)Oid為索引樹(shù)的查找目標(biāo)，確定此對(duì)象在樹(shù)葉子結(jié)點(diǎn)中的位置。顯然只需要用IdBR指示樹(shù)的搜索方向，計(jì)算僅涉及一個(gè)維度（見(jiàn)算法1）。刪除和插入處理與TRP-tree類(lèi)似。

算法1：對(duì)象標(biāo)識(shí)查詢(xún)算法

1.2 雙索引結(jié)構(gòu)——R-tree

解決TPR-tree不能有效支持對(duì)象標(biāo)識(shí)查詢(xún)?nèi)毕莸牧硪环N方法是采用雙索引結(jié)構(gòu)：構(gòu)建以O(shè)id為關(guān)鍵字 （key）的B+-tree作為輔助索引，原有的TPR-tree結(jié)構(gòu)和相應(yīng)算法不變。在B+-tree中，葉子結(jié)點(diǎn)中的每一條目記錄對(duì)象標(biāo)識(shí)與此對(duì)象在TPR-tree的相應(yīng)位置，即（Oid，ptr），其結(jié)構(gòu)如圖1所示。

圖1 R-Tree索引結(jié)構(gòu)

在BiN-tree中，引入對(duì)象標(biāo)識(shí)輔助索引，搜索B+-tree，直接獲取被更新對(duì)象在TPN-tree中的存取路徑（對(duì)象的更新數(shù)據(jù)可簡(jiǎn)化為（Old，P，V）），然后執(zhí)行刪除和插入操作（見(jiàn)算法2）、R-tree的更新計(jì)算復(fù)雜度及結(jié)點(diǎn)訪問(wèn)數(shù)（I/O量）明顯低于TPN-tree。當(dāng)然，B+-tre的同步更新會(huì)產(chǎn)生附加的I/O量，但其I/O量較?。ǖ扔贐+-tree的高度）。算法2的復(fù)雜度為O（H+H2）次I/O，其中H和H2分別為B+-tree與TPN-tree的高度。

算法2：BiN-tree更新算法

1.3 索引現(xiàn)在與將來(lái)

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

TPR-tree：Saltenis等提出了基于R*-tree的索引技術(shù)，稱(chēng)為時(shí)參R（TimeParameterized R-tree，TPR-tree）。TPR-tree能有效的索引在一維，二維，三維空間中的移動(dòng)點(diǎn)對(duì)象的現(xiàn)在與預(yù)測(cè)的將來(lái)位置。TPR-tree考慮移動(dòng)對(duì)象的速度與方向來(lái)預(yù)測(cè)移動(dòng)對(duì)象在不久將來(lái)的大致位置[2]。并且通過(guò)考慮在樹(shù)結(jié)構(gòu)中可計(jì)算的位置來(lái)減少時(shí)間函數(shù)的頻繁更新問(wèn)題。同時(shí)，TPR-tree的更新算法也能使其自動(dòng)的調(diào)整以適應(yīng)于一個(gè)動(dòng)態(tài)變化的數(shù)據(jù)集。

PR-tree：參數(shù)化R樹(shù) （Parametric R-tree，PR-tree）與TPR-tree類(lèi)似，但是PR-tree考慮用參數(shù)化矩形來(lái)表示移動(dòng)對(duì)象的空間區(qū)域。每個(gè)參數(shù)化矩形都有一個(gè)時(shí)間間隔來(lái)表示移動(dòng)對(duì)象運(yùn)動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間。與TPR-tree考慮連續(xù)運(yùn)動(dòng)的對(duì)象不同，PR-tree還考慮移動(dòng)對(duì)象的結(jié)束時(shí)間。因此，一個(gè)移動(dòng)對(duì)象在空間上用一個(gè)多邊形來(lái)表示而不是連續(xù)的運(yùn)動(dòng)跡線。給定運(yùn)動(dòng)的結(jié)束時(shí)間，一系列的移動(dòng)對(duì)象可以用可計(jì)算的多邊形來(lái)表示。

MP-tree：Lee等提出了一棵移動(dòng)點(diǎn)樹(shù)（Moving Point Tree，MP-tree），它是一個(gè)用來(lái)索引移動(dòng)點(diǎn)對(duì)象數(shù)據(jù)的基于R-tree的索引方法。MP-tree使用投影操作（projection operation）來(lái)有效的支持諸如時(shí)間片查詢(xún)與區(qū)域查詢(xún)等的查詢(xún)操作。但是使用投影操作帶來(lái)的一個(gè)缺點(diǎn)就是當(dāng)結(jié)點(diǎn)被輸入時(shí)需要花費(fèi)更多的時(shí)間來(lái)進(jìn)行投影操作的存儲(chǔ)，而優(yōu)點(diǎn)則是能有效的處理分裂與查詢(xún)操作，并且具有高效的空間利用率。另外，通過(guò)鏈表的使用，MP-tree還可以有效的處理基于跡線的查詢(xún)。[2]

2 預(yù)測(cè)查詢(xún)方法

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

2.1 在對(duì)將來(lái)位置的預(yù)測(cè)

指數(shù)平滑法[5]：雖然單個(gè)移動(dòng)對(duì)象的運(yùn)動(dòng)是不斷發(fā)生改變的，但是由于運(yùn)動(dòng)的連續(xù)性，移動(dòng)對(duì)象當(dāng)前時(shí)刻的運(yùn)動(dòng)。速度是和它在前幾個(gè)時(shí)刻的運(yùn)動(dòng)速度密切相關(guān)的。因此，可以根據(jù)移動(dòng)對(duì)象歷史時(shí)間戳的空間位置來(lái)計(jì)算移動(dòng)對(duì)象在每個(gè)歷史時(shí)間段內(nèi)的運(yùn)動(dòng)速度，然后利用歷史速度數(shù)據(jù)來(lái)預(yù)測(cè)該對(duì)象下一時(shí)刻的運(yùn)動(dòng)速度。并由此計(jì)算出移動(dòng)對(duì)象在將來(lái)時(shí)刻的空間位置，R預(yù)測(cè)索引表達(dá)如圖2。

圖2 R預(yù)測(cè)索引表達(dá)

圖3 R樹(shù)預(yù)測(cè)的目錄

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

其中：

式中：Vt表示當(dāng)前時(shí)刻t速度的觀測(cè)值；Vt－1（i=1，2，，，n）表示t時(shí)刻之前的第i個(gè)時(shí)刻的速度；n為計(jì)算a時(shí)選取的觀測(cè)值的個(gè)數(shù)。n值過(guò)大計(jì)算代價(jià)高，n值過(guò)小不能正確反映數(shù)據(jù)變化。在本應(yīng)用中，選取某移動(dòng)對(duì)象在某段道路上的當(dāng)前時(shí)刻前的10個(gè)時(shí)間戳位置來(lái)計(jì)算a值。K為預(yù)測(cè)時(shí)選擇的當(dāng)前時(shí)間戳之前的時(shí)間戳的數(shù)量，可以根據(jù)下式計(jì)算：

K=（2-a）/a

2.2 將來(lái)時(shí)間戳的位置預(yù)測(cè)

對(duì)于“查詢(xún)移動(dòng)對(duì)象M（at，bt）在距現(xiàn)在時(shí)刻t不久的下一時(shí)刻t+1的位置（at＋1，bt＋1）”的將來(lái)時(shí)刻查詢(xún)，其方法如下：

（1）首先，找到移動(dòng)對(duì)象M所關(guān)聯(lián)的空間目標(biāo)，若是面狀目標(biāo)，則M是類(lèi)靜止對(duì)象，根據(jù)采用ES方法進(jìn)行將來(lái)時(shí)間戳的速度預(yù)測(cè)計(jì)算其在t時(shí)刻的運(yùn)動(dòng)速度Vt，則移動(dòng)對(duì)象M在t+1時(shí)刻的位置范圍可如下計(jì)算：

（2）若移動(dòng)對(duì)象M所關(guān)聯(lián)的目標(biāo)是路段目標(biāo)S，則M是快速運(yùn)動(dòng)對(duì)象。首先，根據(jù)采用ES方法進(jìn)行將來(lái)時(shí)間戳的速度預(yù)測(cè)計(jì)算其在t時(shí)刻的運(yùn)動(dòng)速度Vt，計(jì)算M在時(shí)間間隔△t內(nèi)的移動(dòng)距離d=Vt△t，判斷M是否仍然在現(xiàn)有的路段內(nèi)，若在的話，M在t+1時(shí)刻的位置如下計(jì)算：

其中：（As，Bs，），（At，Bt）為路段L的起點(diǎn)和終點(diǎn)坐標(biāo)。

若M不在現(xiàn)有的路段內(nèi)，則首先依據(jù)所設(shè)定的運(yùn)動(dòng)規(guī)則（如最短路徑規(guī)則、首次匹配規(guī)則等），判斷移動(dòng)對(duì)象M將經(jīng)過(guò)的路段，計(jì)算經(jīng)過(guò)每條路段所需的時(shí)間，并最終確定時(shí)刻t+1時(shí)M所在的路段L′，再計(jì)算其在t+1時(shí)刻的位置：

其中：（A′s，B′s），（A′t，B′）為路段L′的起點(diǎn)和終點(diǎn)坐標(biāo)；t′為M途經(jīng)路段（除L′外）所需時(shí)間之和。[3]

3 性能分析

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

4 結(jié)束語(yǔ)

在本文提出R樹(shù)的計(jì)算方法實(shí)用并針對(duì)于移動(dòng)對(duì)象預(yù)測(cè)位置的查詢(xún)，并且引用指數(shù)平滑方法實(shí)現(xiàn)了移動(dòng)對(duì)象運(yùn)動(dòng)信息未知情況下的將來(lái)時(shí)刻的位置的預(yù)測(cè)查詢(xún)。R-tree結(jié)構(gòu)能在保證查詢(xún)性能的前提下，還能有效地解決TPR—tree的更新缺陷。由于R—tree并不改變TPR-tree原有的算法和結(jié)構(gòu)（對(duì)對(duì)象標(biāo)識(shí)建立B+-tree索引），因此這種建立輔助索引的方法可以應(yīng)用到現(xiàn)有的其他索引結(jié)構(gòu)中，解決其存在的更新缺陷。對(duì)于移動(dòng)對(duì)象位置預(yù)測(cè)查詢(xún)很有效果。

［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］趙卿松，盧炎生.移動(dòng)對(duì)象位置預(yù)測(cè)的索引方法[C].2006：5-6

［3］詹平，郭菁，郭薇.基于時(shí)空索引結(jié)構(gòu)的移動(dòng)對(duì)象將來(lái)時(shí)刻位置預(yù)測(cè)[J].2007：6-7.

［4］李春.移動(dòng)對(duì)象軌跡的最近鄰居查詢(xún)研究[D].2007：65-68.

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