位置服務(wù)中對移動物體的時空索引

摘 要：在TPR*tree的基礎(chǔ)上提出了DTPR*tree索引結(jié)構(gòu)， 引進(jìn)了事務(wù)時間和有效時間。它能索引移動物體過去、當(dāng)前和未來的位置信息，支持基本位置查詢和空間約束查詢，有很好的空間、查詢和更新效率。

關(guān)鍵詞：位置服務(wù); 時空索引; 移動物體

中圖分類號：TP392文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2007)06-0058-03

隨著電子消費(fèi)產(chǎn)品、移動通信的發(fā)展和精確定位技術(shù)的出現(xiàn)，為隨時隨地保持在線的用戶提供位置服務(wù)將成為一種新的移動增值業(yè)務(wù)。

基于這些原因，許多新的時空索引技術(shù)被提出來。

時空索引支持的查詢分為如下兩類：①基本位置信息查詢，要求返回移動物體在任何時刻或任何時間間隔內(nèi)的位置信息；②空間約束查詢，包括時間戳查詢、時間范圍查詢和移動窗口查詢。時間戳查詢獲得在某個時間點上滿足空間約束的物體集；時間范圍查詢獲得在某個時間間隔內(nèi)滿足空間約束的物體集；移動窗口查詢獲得在某個時間間隔內(nèi)與一個移動區(qū)域相交的物體。通常的空間約束就是一個物體必須屬于某個矩形區(qū)域。一般能支持上述查詢的索引技術(shù)也能支持更復(fù)雜的查詢。 

然而，還沒有一個單獨的索引結(jié)構(gòu)能夠索引移動物體的過去、當(dāng)前和未來的位置信息，并有很好的空間、查詢和更新效率。本文提出DTPR*tree (Double Time Parameterized R*tree) 索引技術(shù)， 引進(jìn)事務(wù)時間和有效時間，用TPR*tree來支持當(dāng)前和未來查詢，采用單鏈表來支持過去查詢。為了敘述方便，本文主要討論在二維空間內(nèi)持續(xù)移動的物體。

1 相關(guān)工作

對移動物體的索引技術(shù)主要有兩種：用來索引物體的當(dāng)前和未來的位置信息［1，2］；用來索引物體過去的歷史位置信息［3－5］。前一種索引技術(shù)的代表是TPRtree(TimeParameteri￣zed Rtree)［1，2，6］家族。后來Patel等人［7］ 提出了一種叫做STRIPES的索引技術(shù)，采用雙重轉(zhuǎn)換技術(shù)［8］把在n維空間做線性運(yùn)動的點對象表示為二維空間中的點，以高的空間開銷為代價支持有效查詢和更新。

Historical Rtree (HRtree) ［3］在每次更新時構(gòu)造一個新的Rtree，能夠有效地支持時間戳查詢。但它蛻化為一個靜態(tài)查詢，信息冗余，導(dǎo)致很高的存儲空間，時間范圍查詢性能低下。

2 DTPR*tree 索引

2.1 TPRtree 索引

在TPRtree中，一個移動物體通常表示為：①最小邊界矩形 MBR OR 表示其在參考時間0 時的位置；②速度邊界矩形 (VBR)OV={OV1-， OV1+， OV2-， OV2+ }。其中OVi-(OVi+) 分別用來描述OR沿著第i維(1≤i≤ 2)的速度下界和上界。圖1(a)表示了四個移動物體a、b、c、d的MBR和VBR；箭頭(數(shù)值)表示速度的方向和值；負(fù)值表示速度方向與數(shù)軸正方向相反。a的VBR aV={1，1，1，1} (前面兩個數(shù)值表示沿x軸)， b、c、d 的VBR分別表示為bV={-2，-2，-2，-2}， cV={-2，0，0，2}， dV={-1，-1，1，1}。非葉子節(jié)點也用一個MBR 和一個VBR 來表示， MBR (VBR) 包含其孩子節(jié)點的MBR(VBR)。圖1(a)中，所有的物體聚成兩個非葉子節(jié)點N1和N2；VBR分別為N1V={-2，1，-2，1} 和dV={-1，-1，1，1} (方向標(biāo)示如圖)。

2.2TPR*tree索引

2.2.1 插入操作

給定一個待插入的條目e，TPR*tree先通過Choose Path算法找到將會容納e的葉子節(jié)點N。如果N已滿，則N中一系列的條目將會通過Pick Worst算法移出并重新插入；任何在重新插入后仍然溢出的葉子節(jié)點將會用Node Split算法產(chǎn)生節(jié)點分裂，從而新的節(jié)點將會增加到父節(jié)點上，這可能又會導(dǎo)致父節(jié)點溢出，將用類似的方法處理。 

（1）Choose Path。當(dāng)多個分支有相同的(0)衰減時，TPRtree使用的貪心算法性能低下。在TPR*tree中，選擇路徑算法維持一個優(yōu)先隊列QP來記錄到目前為止探測到的候選路徑的衰減值，然后找出衰減最小的插入路徑。

（2）Pick Worst。插入條目到一個已滿的節(jié)點會導(dǎo)致溢出，從而要移出部分條目并重新插入。在TPRtree中，通常都是移出離質(zhì)心距離最遠(yuǎn)的條目，但這種方法并不能減小溢出節(jié)點的MBR。Pick Worst 算法返回移出會減小父節(jié)點MBR 的條目集合。一個簡單的方法就是在每一維每個方向上排序，然后選擇能最大減小父節(jié)點掃描區(qū)域面積的一個組合。 

（3）Node Split。與在TPRtree中一樣，不同之處就是節(jié)點的周長要定義為相應(yīng)的轉(zhuǎn)換矩形的掃描區(qū)域周長。

2.2.2 刪除操作

為了刪除一個物體e，刪除算法首先找到包含e的葉子節(jié)點。具體來說，一個節(jié)點被訪問，當(dāng)它的MBR 包含e的MBR，并且它的VBR包含e的VBR，直到找到e為止。一個改進(jìn)的活動緊繃技術(shù)就是當(dāng)一個被訪問的節(jié)點要回寫磁盤時，緊繃其MBR。

2.3DTPR*tree 索引

現(xiàn)在詳細(xì)介紹DTPR*tree 的結(jié)構(gòu)和相關(guān)算法，目標(biāo)是捕獲并索引現(xiàn)實世界中的物體在任何時刻的位置信息。

假設(shè)移動物體在一個位置采樣到達(dá)時通過無線網(wǎng)絡(luò)向數(shù)據(jù)庫報告它們的運(yùn)動信息，主要包括當(dāng)前的位置信息和速度。當(dāng)物體的速度改變時或位置偏離原來的位置超過一個既定的閾值時產(chǎn)生更新操作。

在DTPR*tree索引中，使用 DTPR*tree來記錄移動物體當(dāng)前和預(yù)期未來信息。對每個物體使用一個單鏈表來記錄直到最近更新時的歷史位置信息；單鏈表限定為只能從頭部插入。圖3(a)顯示了當(dāng)前到未來的DTPBRtree；(b)顯示如何支持過去的查詢。

2.3.1 DTPR*tree中的節(jié)點表示

2.3.2 更新算法

3 性能分析

采用 DTPR*tree索引結(jié)構(gòu)能夠查詢移動物體歷史、當(dāng)前和未來的位置信息，并有很好的時間和空間效率。主要歸因于以下因素：①使用單獨的索引結(jié)構(gòu)，物體的位置信息存儲沒有冗余。②引入了事務(wù)時間和有效時間，支持動態(tài)數(shù)據(jù)集和歷史信息。③移動物體的運(yùn)動軌跡用線性函數(shù)模擬。與常量函數(shù)相比，這種表示減少了更新次數(shù)。實驗證明模擬汽車運(yùn)動時數(shù)據(jù)量減少到原來的三分之一，節(jié)省了存儲空間而能確保正確性。④由于TPR*tree 是一種可實用的索引結(jié)構(gòu)，在其上擴(kuò)展，具有實用性。

4 結(jié)束語

定位技術(shù)、無線通信技術(shù)和消費(fèi)電子的快速發(fā)展，使得跟蹤大量持續(xù)移動物體的位置成為可能。本文提出的DTPR*tree 索引結(jié)構(gòu)能夠在一維、二維、三維空間內(nèi)有效地索引移動物體過去、當(dāng)前和未來的位置信息，并支持多種查詢類型。它是一種可應(yīng)用的時空索引技術(shù)。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。