基于GPS車輛跟蹤系統(tǒng)的移動對象數(shù)據(jù)庫應用研究

1、基于GPS車輛跟蹤系統(tǒng)的移動對象數(shù)據(jù)庫應用研究摘 要 本文結合GPS車輛實時跟蹤應用系統(tǒng)，利用移動對象數(shù)據(jù)庫技術，對移動車輛的運動空間及時間進行分割，建立了移動目標數(shù)據(jù)庫的數(shù)據(jù)模型、數(shù)據(jù)結構以及索引結構，實現(xiàn)實時更新車輛位置信息，有效地回放移動車輛的歷史行駛軌跡，預測車輛將來的運動路線。 關鍵詞 移動對象數(shù)據(jù)庫；數(shù)據(jù)模型；數(shù)據(jù)結構；索引結構；片斷樹 近年來移動對象數(shù)據(jù)庫成為一個研究熱點，許多的應用中提出了對連續(xù)移動對象的存儲、查詢和處理需求，如：交通管理，運輸和供應鏈管理等。移動對象數(shù)據(jù)庫主要針對移動目標（比如運動車輛），實現(xiàn)實時更新車輛位置信息，有效地回放移動車輛的歷史行駛軌跡路線，預測車輛

2、將來的運動,提供車輛行駛目的地的信息。為了建立一個實時跟蹤大量移動車輛以及查詢移動車輛的歷史運動路線的應用，利用它們通常運動在城市公路網(wǎng)上這一特點，本文研究了移動對象數(shù)據(jù)庫在車輛交通管理中的應用，提出了一種對車輛當前和將來位置的索引方法和基于此索引方法的查詢。該方法以時間片斷（采樣時間間隔）與空間塊片斷（公路網(wǎng)段）的移動對象數(shù)據(jù)模型和索引方法為基礎，為連續(xù)的移動對象建立索引結構，對交通路段網(wǎng)絡中的移動車輛,設計以及實現(xiàn)車輛位置信息的數(shù)據(jù)庫系統(tǒng)。1 數(shù)據(jù)模型 GPS車輛位置信息實時跟蹤系統(tǒng)主要包括：已經(jīng)注冊過的車輛，數(shù)據(jù)處理中心，終端用戶或用戶服務器以及通訊路徑。電子地圖是將地圖以數(shù)字形式存儲于

3、計算機中，利用電子地圖將 GPS 得來的坐標通過地圖匹配找到對象所在的路徑。系統(tǒng)的工作原理為：車輛是行駛在公交網(wǎng)中的現(xiàn)實存在的車輛。車輛接受來自GPS衛(wèi)星的GPS信號，從而確定它的物理位置，物理位置被轉換為UTM系統(tǒng)數(shù)據(jù)庫中的坐標，通過無線網(wǎng)絡周期性的更新位置信息。數(shù)據(jù)中心存儲車輛的靜態(tài)屬性和車輛的實時位置信息，同時保存著每輛車的歷史數(shù)據(jù)，數(shù)據(jù)中心還提供在線客戶的應用以及用戶處理查詢得到的數(shù)據(jù)。 該方法提出一種全新的數(shù)據(jù)模型，車輛用點來表示,忽略其形狀及大小，公交網(wǎng)由一系列的相互交叉的公路段表示,每個公路段都有唯一的編號。車輛的行駛軌跡通過一系列的點表示,表示格式為( t， Rid，d ，v

4、)： t 表示車輛在給定位置的時間 Rid 表示車輛所在公路段的編號 d 表示車輛當前位置到起始位置的距離 v 表示車輛的當前行駛速度 空間被劃分為互不重疊的區(qū)域單元,并采用適當?shù)目臻g索引進行索引化,移動對象在每個區(qū)域運動中運動的時間間隔被采集并索引化。 在應用了該方法的移動車輛數(shù)據(jù)庫中，空間被分為公路段。公路段采用片斷樹結構進行索引。移動車輛在公路段產(chǎn)生的時間間隔采用平衡間隔樹來進行索引。采用這種索引方案的移動車輛數(shù)據(jù)庫系統(tǒng)會更靈活，便于系統(tǒng)升級，因為公路段，時間間隔以及這些索引結構能夠很簡單的分配給不同的處理器，內(nèi)存以及服務器進行處理。 汽車的運動是連續(xù)的，將汽車的位置與速度信息化為一些具

5、體的采樣點。數(shù)據(jù)的精度與系統(tǒng)的承載量是相互平衡的，取樣的間隔越短，運動汽車的數(shù)據(jù)就越是精確，數(shù)據(jù)庫中的數(shù)據(jù)也越多。對公路網(wǎng)，車輛，車輛的狀況以及時間建立模塊，公路網(wǎng)由公路段組成， 公路段具備以下2個條件：任何2個公路段不相交以及公路段間的交點既是起點也是終點。車輛的屬性，分3種：靜態(tài)屬性，間斷變化（離散）屬性，連續(xù)變化屬性： （1）靜態(tài)屬性的數(shù)據(jù)結構：vehicle_attributes_static Vid : integer; make : string; model : string; year :integer; （2）間斷變化屬性vehicle_attributes_discrete

6、 ownership : owner_i:string,t_i:time, color : color_i:string,t_i:time, use : use_i:string,t_i:time, destination :dest_i:location,t_i:time,location zone : integer; easting : real; northing : real; Address :string; （3）連續(xù)變化屬性vehicle_attributes_dynamic Road_id : integer; time : time; velocity : real; di

7、stance :real; easting : real; northing :real; 汽車的運動由它在各采樣點上的位置，速度來定義。這些值被實時記錄并更新。兩個采樣點之間的運動狀態(tài)是這樣描述的： 汽車的加速度為a，兩個時間點t1與t2 之間的時刻為 t，與時間點對應的為位置 p1和 p2,速度為 v，離路段起點的距離為 d，滿足如下的計算： 把加速度考慮進來，減少了存儲數(shù)據(jù)的大小?？梢哉J為在這些采樣點上，加速度在隨后的采樣點上是一樣的，不考慮速度的變化。 汽車將其位置與運動信息以某個中心頻率發(fā)送給中心站，中心站將這些數(shù)據(jù)信息收集起來，但不是每一次的更新都會記錄在數(shù)據(jù)庫中，只有在這些關鍵數(shù)

8、據(jù)影響到了在鄰近地區(qū)的運動估測時，才會被記錄下來并存入數(shù)據(jù)庫中。根據(jù)汽車正在行駛的路況，速度，速度的改變量，下面的兩種情況下，數(shù)據(jù)更新是可以忽略的： （1） 汽車在最后一次更新的相同路段 （2） 與最后一次更新相比，速度的改變在某個很小的變化范圍內(nèi)，或者加速度在某個很小的變化范圍內(nèi)。 在某種情況下，一個采樣點必須插入到汽車兩次更新之間。如果兩次連續(xù)的更新表明汽車已經(jīng)走出了此路段進入另外一個路段，就需要在這兩個路段的交叉處計算并添加一個合適的采樣點。所使用的算法與估測同一路段上兩個已知樣點間的運動是相似的。2 數(shù)據(jù)結構 為了使跟蹤系統(tǒng)高效運行，必須對路段數(shù)據(jù)模型進行不同的操作處理。 公路段的定義

9、是這樣的：road_segment Road_Id :integer; Start_easting :real; Start_northing : real; End_easting : real; End_northing : real; Length : real; Speed_limit: real; Time_of_birth : time; Time_of_death : time; Next *road_segment 這條記錄中的每個參數(shù)要求大小一致，除了最后一個參數(shù)。最后一個參數(shù)定義了依據(jù)地圖當前路段的下一個路段。大多說情況下，會有3到4個路段，直前方，左邊，右邊，有時候會是U

10、形轉彎。因此，給Next參數(shù)設置4個單元比較合理，每條記錄的大小就是相同的了，就可以利用一個數(shù)組來存儲這一條數(shù)據(jù)。在特殊情況下，多于或者少于4個單元，假設單元數(shù)為x，處理規(guī)則如下：（1）當x小于4時，在第（x+1）到第4個單元中添0；（2）當x大于4時，前兩個單元與一般情況下一樣，設置第3單元為0，第4單元指向第3單元到第x單元的存儲地址，最后一位設為空。 同一條路上的兩個路段方向相反時，可以共享除了Next參數(shù)的所有信息。如果我們把每一個有向路段的信息都存儲起來就會有數(shù)據(jù)冗余。 公路網(wǎng)信息可以為給定點或者街道地址定位路段。有時候還需要尋找路徑，回復范圍咨詢，顯示汽車的運動情況。選擇一個片斷樹

11、作為路段的索引結構。多維樹結構可以跟蹤歷史記錄以及路段當前的狀況。汽車的靜態(tài)以及更新的離散數(shù)據(jù)可以用一張常規(guī)表存儲在數(shù)據(jù)庫管理系統(tǒng)中。3 索引化結構 物體的運動空間被分為基本的空間塊，各個空間塊互相獨立。空間分割是很靈活的，主要由數(shù)據(jù)庫系統(tǒng)所支持的各種查詢類型的頻率決定的。對每個對象而言，時間被分為時間間隔，在每個時間間隔內(nèi)，對象屬于一個空間塊。根據(jù)空間塊來劃分形成的時間間隔組成不同的子集。根據(jù)相應的時間塊對每個時間間隔的集合進行索引，對空間塊的索引與對時間間隔的索引是各自單獨進行的，二者索引結構互不依賴，彼此之間可以相同或相似或者完全不同。空間分割算法沒有什么限制，只要空間中的每一個點被分配

12、到唯一的一個分隔區(qū)中就行。當汽車在一條路段上運動時，時間被分成很多個間隔，空間被分割為很多個單向的路段。索引結構包括處理路段以及與路段相關的時間的結構。對時間間隔（時間片斷）和路段（空間塊）的索引結構是以最開始的片斷樹為基礎的。平衡片斷樹用來索引汽車在同一路段上移動的時間間隔，還有一個時間間隔樹與每個路段相關。一個修改的片斷樹是用來索引路段的。片段樹最開始是用在2維空間中一組線段的范圍查詢，描述如下：給出二維空間中n條不交的直線(x11,y11),(x12,y12), (x21,y21).(xi1,yi1),(xi2,yi2).(xn1,yn1),(xn2,yn2)，片段樹很適于索引靜態(tài)的輸入

13、數(shù)據(jù)組，片斷樹不支持頻繁的插入和刪除操作。 在移動車輛的位置信息跟蹤系統(tǒng)中，索引化結構分為2個方面：對公交網(wǎng)進行索引和對移動車輛的跟蹤進行索引。 不同的汽車之間以及一輛汽車與一個靜態(tài)位置之間的距離與相對位置是由汽車的地理位置和公路段的設計決定的。有些查詢窗口，比如距離查詢涉及地圖中的給定區(qū)域，可能需要在查詢回復之前就查找給定區(qū)域內(nèi)的所有公路段，因為每輛汽車的移動軌跡已經(jīng)為時間間隔范圍查詢設置好了，那么建立一個遍歷所有汽車軌跡的主索引結構用于空間/位置的查詢就很有意義了。為此，每輛汽車在公路段上行駛的時間間隔被設計為基本的數(shù)據(jù)單元，對應的索引結構叫做時間間隔樹，它的建立與每個公路段有關。對給定空

14、間范圍與時間間隔的查詢首先要進入公路網(wǎng)瀏覽查詢，提取給定空間范圍內(nèi)的所有公路段，然后進入與這些包含公路段相關的時間片斷樹，得到給定時間間隔內(nèi)行駛在這些公路上的所有汽車。 （1） 對公路段進行索引 系統(tǒng)中當有兩個公路段有一個交叉點時，二者要分成兩個片斷存儲在數(shù)據(jù)庫系統(tǒng)中。分點就是交叉的那個點。當在3維空間中沒有交叉點但在2維空間里有一個交叉點時，就可以用到分點，比如一條高速公路與本地的一條公路交叉時，在3維空間里，他們之間是沒有交叉點的。對于2個或者多個具有相同終點坐標的情況，就不需要按照前面描述的那樣更改索引結構。對某一點查詢時，如果查詢點恰好處在交叉點時，所有以該點為交叉點的公路段都應被查詢

15、出來。對一個矩形區(qū)域范圍進行查詢時，只要有一個點在這個范圍內(nèi)的所有片斷都被包括進來。對建立樹結構的預處理基本上與標準片斷樹是相同的。建樹的時間與空間復雜度需事先分析，且保持不變。 （2） 對車輛的運動進行索引 索引結構中，汽車移動的基本單元是由汽車行駛在同一路段的持續(xù)時間。片段樹結構用來索引汽車行駛在同一路段的時間間隔。時間間隔對應的空間片段樹叫做時間間隔樹。 對汽車定位信息跟蹤系統(tǒng)進行在線更新時間間隔樹只需要一種插入操作，當進入一個路段時，時間間隔的起點要發(fā)送并記錄在樹中；當離開一個路段時，時間間隔要明確的加入樹結構中。 插入的時間點或者時間間隔總是在x軸的右邊，相對樹中已經(jīng)存在的數(shù)據(jù)，它們

16、是最新的。在一個平衡時間間隔樹中，數(shù)據(jù)類涉及到結點，樹，以及被稱為結點定位器的輔助數(shù)據(jù)結構，共同反映樹中最實時的結點。 結點，樹葉或者無葉結點，在時間間隔樹中是通過從a點到b點的時間間隔來定義的，假設具有相同時間間隔a，b的汽車車號Vid的集合為S，表示為（a，b,Vid，.） 時間間隔樹與平衡二進制樹是互相關聯(lián)的，樹中的每一個節(jié)點都由3個指針與它們的父結點，左結點，右結點相連。 結點定位器包含一個指向時間間隔樹中一個結點的指針r，時間指針t，以及樹中指針結點的層次為l，結點的層次是從葉結點依次向上的，葉結點的層次為0。4 查詢處理 移動對象數(shù)據(jù)庫的查詢類型一般包括： (1) 實時查詢所有或部

17、分移動車輛運動信息； (2) 查詢部分移動車輛在過去,現(xiàn)在的運動信息或者預測將來的運動信息； (3) 按時間段查詢指定公路上的移動車輛,并將他們的運行狀況顯示出來； (4) 按時間段和給定的地區(qū)范圍,回放車輛的歷史行駛軌跡路線； (5) 返回在規(guī)定時間內(nèi)到達規(guī)定地點的車輛信息； (6) 預計某時間段內(nèi)移動車輛的運動； 為了使查詢的結果中包含將來的時間，那么預測車輛的可能移動軌跡是不可少的。在這種預測中最重要的技術就是車輛的行駛路線。 5 結論 本文主要針對移動車輛實時跟蹤GPS導航系統(tǒng)的數(shù)據(jù)存儲與處理，以行駛在公路網(wǎng)上的移動車輛為研究對象，建立了移動對象數(shù)據(jù)庫的數(shù)據(jù)模型和索引結構，該模型可以大大提高數(shù)據(jù)的精度和查詢處理的效率，不僅可以對歷史數(shù)據(jù)進行挖掘，還可以更精確的預測車輛未來的運行狀態(tài)。參考文獻1 王惠南. GPS導航原理與應用 . 科學出版社,2003.82 于秀蘭,陳瀅,丁曉誠.一種基于道路網(wǎng)絡的移動目標數(shù)據(jù)庫模型. 軟件學報,2003, 14 (9):1600-1607.3 Dongseop Kwon, Sangjun Lee, Wonik Choi, Sukho Lee .An adaptive hashing