位置服務中對移動物體的時空索引

摘 要：在TPR*tree的基礎上提出了DTPR*tree索引結構， 引進了事務時間和有效時間。它能索引移動物體過去、當前和未來的位置信息，支持基本位置查詢和空間約束查詢，有很好的空間、查詢和更新效率。

關鍵詞：位置服務; 時空索引; 移動物體

中圖分類號：TP392文獻標志碼：A

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

隨著電子消費產品、移動通信的發展和精確定位技術的出現，為隨時隨地保持在線的用戶提供位置服務將成為一種新的移動增值業務。

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

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

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

1 相關工作

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

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

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；箭頭(數值)表示速度的方向和值；負值表示速度方向與數軸正方向相反。a的VBR aV={1，1，1，1} (前面兩個數值表示沿x軸)， b、c、d 的VBR分別表示為bV={-2，-2，-2，-2}， cV={-2，0，0，2}， dV={-1，-1，1，1}。非葉子節點也用一個MBR 和一個VBR 來表示， MBR (VBR) 包含其孩子節點的MBR(VBR)。圖1(a)中，所有的物體聚成兩個非葉子節點N1和N2；VBR分別為N1V={-2，1，-2，1} 和dV={-1，-1，1，1} (方向標示如圖)。

2.2TPR*tree索引

2.2.1 插入操作

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

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

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

（3）Node Split。與在TPRtree中一樣，不同之處就是節點的周長要定義為相應的轉換矩形的掃描區域周長。

2.2.2 刪除操作

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

2.3DTPR*tree 索引

現在詳細介紹DTPR*tree 的結構和相關算法，目標是捕獲并索引現實世界中的物體在任何時刻的位置信息。

假設移動物體在一個位置采樣到達時通過無線網絡向數據庫報告它們的運動信息，主要包括當前的位置信息和速度。當物體的速度改變時或位置偏離原來的位置超過一個既定的閾值時產生更新操作。

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

2.3.1 DTPR*tree中的節點表示

2.3.2 更新算法

3 性能分析

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

4 結束語

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

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