河海大學碩士研究生論文 摘要 基于移動對象位置的服務( l o c a t i o nb a s e ds e i c e ，l b s ) 是智能交通系統(tǒng) ( h l t e l l i g e n c et r a n s p o n a t i o ns y s t e m ，i t s ) 中的重要組成部分。其中，最優(yōu)路徑 選擇、實時路況查詢、周邊目標查詢等各類l b s 服務均要求l b s 系統(tǒng)的時空數(shù) 據(jù)庫系統(tǒng)具備實時快速存取移動對象( 主要指車輛) 位置數(shù)據(jù)的能力。但由于車 輛位置數(shù)據(jù)受路網(wǎng)限制分布且時刻變化，不適合采用傳統(tǒng)的時空數(shù)據(jù)索引結構對 其進行管理。為解決此問題，本文在l b s 系統(tǒng)框架下，提出了基于復合索引結 構的城市道路網(wǎng)環(huán)境下的移動對象索引結構。 復合索引結構是常見的用于管理路網(wǎng)下移動對象位置數(shù)據(jù)的索引形式，影響 其效率的因素包括路網(wǎng)規(guī)模、移動對象的更新頻率等。其中，路網(wǎng)的劃分方式則 是最直接、關鍵的因素，這是因為路網(wǎng)的劃分方式直接決定了復合索引的規(guī)模以 及移動對象的更新模式。為此，本文集中探討了兩種路網(wǎng)劃分方式：路段劃分及 路口區(qū)域劃分。本文首先提出路段劃分的方式，以減少移動對象的更新頻率。但 由于l b s 系統(tǒng)被部署在非實時的數(shù)據(jù)通信環(huán)境下，因此本文又提出了一種新的 路網(wǎng)劃分單元：一路口區(qū)域( c r o s sr e 西o n ，c r ) ，從而能在l b s 環(huán)境下更精確地 對移動對象位置進行判斷?；谶@兩種不同的路網(wǎng)劃分方式，本文分別對應提出 r r t r e e 與c r - t r e e 兩種不同的路網(wǎng)管理結構來作為復合索引的上層結構。 通過實驗對上述兩種路網(wǎng)劃分方式進行比較后發(fā)現(xiàn)，盡管c r t r e e 在索引空 間的需求上遠超過r r t r e e 。但由于基于路口區(qū)域的劃分方式解決了l b s 環(huán)境下 無法進行實時數(shù)據(jù)傳輸?shù)谋撞?，能夠更準確地對車輛位置進行判斷，同時在查詢 效率上的表現(xiàn)也優(yōu)于路段劃分方式，因此更適用于路網(wǎng)下的移動對象數(shù)據(jù)管理。 關鍵詞：基于位置服務，復合索引結構，路網(wǎng)劃分方式，r r - t r e e ，c r - t r e e 河海大學碩士研究生論文 一一一 a b s t r a c t l o c a t i o nb a s e ds e n ，i c e s ( l b s ) i sa ni m p o r t a m p a no fi n t e l l i g e l l c et r a n s p o r t a t i o n s y s t 鋤( i t s ) m 觚yl b sa p p l i c a t i o n ss u c hl i k ec h o o s i n go p t i m a lp a t h ，q u e 咖n g r e a l 。t l m et r a m cm 士o m a t i o no rt a 瑪e t sa r o u n da 1 1n e e dl b s ss p a t i o t e m p o r a ld a t a b a s e t oa c c e s sm o v i n g o b j e c t s p o s i t i o nd a t aq u i c k l y ：s i n c et h o s ed a t aa r ec o n s t r a i n e db v 廿1 er o a dn e t 、) l ，o r k ，a 1 1 dc h a l l g e dq u i c k 堍缸a d i t i o n a ls p a t i o t e m p o m li n d e x e sa r eh a r d l v t 0 m a l l a g et h 鋤t i l 盱e f o r e ，w ep r o p o s et h es t m c t u r e sf o rm o v i n go b j e c t si nr o a d n e t 、v o r kb a s e do nc o m p o s i t es t m c t u r e1 1 1 1 d 叫y i n gt h e 觸m eo f l b si nt h i sp a p 睨 ln ec o n l p o s l t es t m c t i l r ei st h em o s tc o 姍o nf o 肋f o r m a n a 百n gm o v i n go b j e c t s r e a l t l m ep o s i 廿o n su n d 甜y i n gr o a dn e t w o r k t h es i z eo ft h er o a dn e 時o r ko rm e 丘明u 饑c yo fo b j e c t s u p d a t e sc o u l da 1 1a 虢c ts t m c t i l r e sp e r f o n l l a l l c e b u tt h ek e v f a c t o ri st h ed i v i d i n gm e t h o df o rr o a dn e 撕o r k ，b e c a u s e i td e t e m l i n e sb o t ht h es i z eo f t h es t n l c t u r e 鋤dt h eu p d a t ep a t t e mo fo b j e c t sd i r e c t l y f o r t h a t ，i nt 1 1 i sp a p e r ，w e d i s c u s s 咖d i n 抵td i v i d i n gm e t h o d sf o rr o a dn e t w o r k ：d i v i d eb ys e 至即e n t sa n d d 1 v 1 d eb yc r o s sr e 百o n w ef i r s tp r o p o s et h ed i v i d i n gm e t h o db ys e g m 鉍t b e c a u s ei t c o u l dl o w e rt h eu p d a t ef e q u e n c yo fo b j e c t s b u ta st h el b s s y s t e mi sd i s p o s e di na n o n r e a l t l m ed a t ac o m m u n i c a | i o n e n v i r o n m e n t ，w ep r o p o s ea n o t h e rn e wb a s i c e l 鋤e l l tc a l l e dc r o s sr e g i o n ( c r ) t od i v i d et h er o a dn e 觚o r k ，s ot h a tt h ej u d 舯e n tf o r o b j e c t s p o s i t i o n sc o u l db em o r ea c c u r a t e b a s e do nt h e s e 觚od i f 五玎e n t d i v i d i n 2 m e t h o d sf o rm er o a dn e t w o r k ，w ep r 叩o s et w os t n l c n j r e sr e s p e c t i v e l yf o rm a l l a 西n g r o a dn e m o r kt ob et h e u p p e rs t n l c t u r eo ft h ec o m p o s i t es t m c t u r e ih r o u 曲t h ec o m p 撕s o nb e t w e e nt h e s et w od i 毹r e n td i v i d i n gm e t h o d s ，w ef i n d t h a ta l t h o u g hc r - t t e en e e d sm o r es t o r a g es p a c e ，i tc o u i ds o l v et h en o n r e a l t i m e p r o b l e n lc a u s e d b yl b s ，a n dq u 叫q u i c k e rm a nt h em e t h o dw i t hs e 腫e n t ，s oi t i s m o r es u l t a b l et l o rt h em a n a g e m e n to ft h e m o v i n go b j e c t sb a s e do nr o a dn e t w o r k k e yv r d s ：l o c a t i o nb a s e ds e n ，i c e ( l b s ) ，c o m p o s i t e s t r u c t u r e ，d i v i d i n gm e t h o d f o rr o a dn e 鉚o r k ，r r t r e e ，c r - t r e e i i 學位論文獨創(chuàng)性聲明： 本人所呈交的學位論文是我個人在導師指導下進行的研究工作 及取得的研究成果。盡我所知，除了文中特別加以標注和致謝的地方 外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果。與我一同工 作的同事對本研究所做的任何貢獻均已在論文中作了明確的說明并 表示了謝意。如不實，本人負全部責任。 論文作者( 簽名) 聾塑l 圳紛 ( 注：手寫親筆簽名) 學位論文使用授權說明 岳月 f 7 1 日 河海大學、中國科學技術信息研究所、國家圖書館、中國學術期 刊( 光盤版) 電子雜志社有權保留本人所送交學位論文的復印件或電 子文檔，可以采用影印、縮印或其他復制手段保存論文。本人電子文 檔的內容和紙質論文的內容相一致。除在保密期內的保密論文外，允 許論文被查閱和借閱。論文全部或部分內容的公布( 包括刊登) 授權河 海大學研究生院辦理。 論文作者( 簽名) ：二墼堡氐撕莎年 ( 注：手寫親筆簽名) 月1 1 日 河海大學碩上研究生論文第一章緒論 第一章緒論 在我國，伴隨著城市化進程的日益加快，各大中城市的城區(qū)面積正在不斷擴 張；與此同時，社會經(jīng)濟建設的迅速發(fā)展也使得城市中私用與公用汽車保有量也 在不斷增加。面對雙重壓力，各城市管理部門都在不斷加大建設與完善城市交通 系統(tǒng)的力度，與此同時，對于智能化交通系統(tǒng)( i n t e l l i g e n c et r a i l s p o r 眥i o ns y s t e m ， i t s ) 的研究也逐漸興起。智能化交通系統(tǒng)最初是在以監(jiān)控為主體的交通工程( 包 括交通管理) 基礎上發(fā)展起來的，開始只進行道路和車輛智能化的研究，目前其 研究范圍已逐漸涉及到鐵路、水運及航空等各種交通方式，并逐漸形成一整套為 用戶及交通管理部門提供道路交通信息的新型交通系統(tǒng)。在i t s 中，其“智能化 主要體現(xiàn)在以下3 個方面： ( 1 ) 車輛依靠自身智能在道路上安全自由地行駛，在陌生地方不致迷失方向。 ( 2 ) 道路依靠自身的智能將交通流調整至最佳狀態(tài)，縮短行車時間，減少阻塞。 ( 3 ) 交通控制管理中心依靠系統(tǒng)的智能對道路和車輛的狀態(tài)進行實時監(jiān)控，及 時處理事故，保障道路暢通。 這其中，盡管各道路自身的離散式調整與交通控制中心的集中式調整這兩種 調整方式均能夠實現(xiàn)對城市路網(wǎng)中交通流的管理與疏導，但由于交通控制中心處 于城市智能化交通系統(tǒng)的核心位置，除了能夠從路網(wǎng)整體狀態(tài)的角度出發(fā)設計出 更為合理的調整方案之外，也能夠全方位地為行駛在路網(wǎng)中的車輛提供各種交通 信息的服務，因此備受各級交通管理部門的青睞。 為了使交通控制中心能夠更好地進行集中式的路況調整，則需要其對交通道 路網(wǎng)中的各項數(shù)據(jù)進行快速存取，因此一個準確高效的數(shù)據(jù)庫系統(tǒng)就成了交通控 制中心中不可獲取的部分，這也是本文所要關注的重點問題。 1 1 研究背景 交通控制中心在對當前路網(wǎng)狀態(tài)進行分析后，依據(jù)移動對象的具體位置提供 的信息支持被稱為基于位置服務( l o c a t i o nb a s e ds e r v i c e ，l b s ) 。l b s 是建立在 定位基礎上的服務，其具體含義與工作原理在不同的行業(yè)背景下各有不同?？傮w 而言，l b s 是在地理信息平臺的支持下，提供給用戶各類位置相關服務。在i t s 的背景下，如最優(yōu)路徑選擇、實時路況查詢、周邊目標查詢等均屬于l b s 。以下 本文對于l b s 的描述，若無特殊說明，均是指在i t s 環(huán)境下所提供的l b s 服務。 河海大學碩士研究生論文 第一章緒論 l b s 的具體工作原理是：移動對象( 車輛、行人等所有基于路網(wǎng)行進的物體) 通過g p s 等定位設備獲取用戶當前位置后，通過移動通信網(wǎng)( w l a n 、3 g 等) 實時地把這一位置信息上傳至交通控制管理中心，實現(xiàn)了交通控制管理中心對于 全局路網(wǎng)下交通狀態(tài)的掌握與控制；而面對移動對象所發(fā)出的服務請求( 路況查 詢與預測、最優(yōu)路徑選擇等) ，中心服務器可依據(jù)當前路網(wǎng)的整體狀態(tài)，并配合 氣象、市政交通建設等多種信息進行統(tǒng)一規(guī)劃，給予用戶合理的建議，進而實現(xiàn) 對交通狀態(tài)的疏導與管理。 時空數(shù)據(jù)庫系統(tǒng)是l b s 中的關鍵部分。一方面，它所需管理的移動對象數(shù) 據(jù)量十分龐大，據(jù)不完全統(tǒng)計，預計至“十一五 末期，南京市的汽車保有量 將達到6 0 萬輛，上海則將超過1 5 0 萬輛，而北京目前的汽車保有量就已超過了 3 0 0 萬輛；而另一方面，車輛的高速移動性又決定了這些移動對象數(shù)據(jù)只有通 過頻繁的更新才能使數(shù)據(jù)庫系統(tǒng)準確了解它們的位置變化，根據(jù)截止至2 0 0 l 的 統(tǒng)計數(shù)據(jù)，在上海市2 2 ，4 1 3 個路口中，平均每分鐘通過一個路口的車輛數(shù)量就 高達3 3 輛【l 】?？梢娭挥胁捎煤线m的數(shù)據(jù)索引對能夠對這些數(shù)量龐大且更新頻率 高的數(shù)據(jù)進行有效地存儲與管理。除此之外，位置信息數(shù)據(jù)由于不同于一般數(shù) 據(jù)的分布特點( 如數(shù)據(jù)的多維分布、動態(tài)性等) 以及有別于普通數(shù)據(jù)庫的操作 ( 如歷史軌跡查詢，預測區(qū)域查詢等) ，決定了只有研究新的基于時空數(shù)據(jù)的數(shù) 據(jù)管理結構，包括時空數(shù)據(jù)索引結構，時空數(shù)據(jù)查詢方法等，才能夠為各類l b s 提供有效的數(shù)據(jù)支持。 時空數(shù)據(jù)是指分布在多維空間下，并隨時間變化的數(shù)據(jù)。在l b s 系統(tǒng)中， 時空數(shù)據(jù)庫被部署在系統(tǒng)架構的中心服務器部分，主要用于存儲與管理中心服務 器所接收到的，路網(wǎng)下各移動對象的實時位置數(shù)據(jù)。這些數(shù)據(jù)分布在城市路網(wǎng)中， 且隨著移動對象的運動而持續(xù)更新，因此符合時空數(shù)據(jù)的特點。同時，由于在路 網(wǎng)環(huán)境下，移動對象的運動軌跡取決于路網(wǎng)的分布情況，即任何對象的運動范圍 均不可超出道路范圍以外，因此在本文中此類分布在路網(wǎng)中的時空數(shù)據(jù)被稱為受 限時空數(shù)據(jù)。 但是在現(xiàn)有的時空數(shù)據(jù)庫，特別是時空數(shù)據(jù)索引的研究中，其研究主體并不 是路網(wǎng)下的移動對象，而是歐氏空間下的移動對象。在海中航行的輪船、在空中 飛行的飛機，以及在城市中任意運動的手機終端等均屬于歐氏空間下移動對象的 范疇。在歐氏空間中，對象的移動軌跡是線性的、不受約束的，即移動對象在兩 次更新之間保持勻速直線運動狀態(tài)，只有當對象的運動速度( 方向或速率) 發(fā)生 變化時，才會向數(shù)據(jù)庫提交更新。這些數(shù)據(jù)在本文中被稱為非受限時空數(shù)據(jù)。 受限時空數(shù)據(jù)較非受限時空數(shù)據(jù)的主要不同在于： ( 1 ) 受限時空數(shù)據(jù)的運動狀態(tài)受到路網(wǎng)分布的約束，非受限時空數(shù)據(jù)在速度不變 2 河海人學碩上研究生論文第一章緒論 化的情況下則保持勻速直線運動狀態(tài)； ( 2 ) 受限時空數(shù)據(jù)間的距離測算也受到路網(wǎng)分布的約束，非受限時空數(shù)據(jù)的距離 測算即為直線最短距離。 以上這些區(qū)別給l b s 的時空數(shù)據(jù)庫系統(tǒng)帶來兩點主要問題： ( 1 ) 受限時空數(shù)據(jù)具有較高的更新密度。這是因為移動對象在路網(wǎng)中行進時，由 于道路的約束，導致其前進速度( 本文中主要考慮速度方向，速率假設不變) 不斷發(fā)生改變，需要實時地向中心服務器來提交自己的位置變化信息，以使 得中心服務器能夠準確地了解各移動對象在道路網(wǎng)中的分布狀況，為各類位 置服務提供有效的數(shù)據(jù)支持。但這種高密度的數(shù)據(jù)更新操作不僅會給中心服 務器的時空數(shù)據(jù)庫帶來巨大的計算壓力，也給通信網(wǎng)絡帶來巨大的數(shù)據(jù)負 載。 ( 2 ) 受限時空數(shù)據(jù)的距離測算信賴于道路網(wǎng)的分布。時空數(shù)據(jù)索引是依據(jù)時空數(shù) 據(jù)間距離的遠近對數(shù)據(jù)進行聚類索引的方法，由于道路網(wǎng)的存在，兩個在具 有較短直線距離的移動對象可能由于分處不同道路，而導致其間道路距離很 長。因此無法采用傳統(tǒng)的歐氏空間下時空索引結構來對受限時空數(shù)據(jù)進行索 引管理。 針對第一個問題，l b s 系統(tǒng)特別引入了移動對象追蹤模塊，以使得系統(tǒng)能夠 在較低密度的更新水平上，盡可能精確地獲取移動對象的位置變化。追蹤技術的 研究是受限時空數(shù)據(jù)索引研究的重要前提。丹麥奧爾堡大學的c s j e n s e n 等人在 2 0 0 4 年提出了一種基于道路網(wǎng)的移動對象追蹤系統(tǒng)【2 】，并提出了三種追蹤策略： 基于點的追蹤、基于向量的追蹤和基于路段的追蹤。其中尤以基于路段的追蹤策 略能夠在保證追蹤精度的前提下提供最低密度的更新操作請求，因此在各類l b s 研究中被廣泛使用，也是本文研究的基礎。 本文的研究重點是解決上述中的第二個問題，即如何在考慮路網(wǎng)分布的情況 下對實時的受限時空數(shù)據(jù)進行管理，并提出一種新的適用于道路網(wǎng)環(huán)境下移動對 象實時位置信息管理的受限時空索引，給出其結構和操作描述，并通過實驗來證 明其正確性和優(yōu)越性。 1 2 研究現(xiàn)狀 數(shù)據(jù)索引是現(xiàn)代數(shù)據(jù)庫系統(tǒng)中的重要組成部分。在處理大量的數(shù)據(jù)記錄時， 通過對索引結構進行查詢操作，就可以將屬性的值轉換為相應記錄的地址或地址 集，可以達到快速地存取數(shù)據(jù)的目的。目前就索引結構的研究情況如表1 1 所示。 在早期的關系數(shù)據(jù)庫系統(tǒng)中，當數(shù)據(jù)記錄的候選鍵是一個列字段時，可采用 3 河海大學碩士研究生論文第一章緒論 b t r e e 對此列的記錄值進行索引；而當數(shù)據(jù)記錄的候選鍵是由多個列字段組成時， 則采用級聯(lián)索引的形式，此時組成候選鍵的列順序不同，所形成的級聯(lián)索引也大 相徑庭。 在處理時空數(shù)據(jù)時，數(shù)據(jù)記錄的鍵是由n 個空間列字段以及1 個時間列字 段共同組成的，其中n 是指物體運動時所處的空間維度，n 1 。由于這n + 1 個 列字段之間彼此沒有先后順序，如果采用傳統(tǒng)的級聯(lián)索引的方式，則數(shù)據(jù)庫系統(tǒng) 在處理窗口查詢、時間片查詢等空問或時空查詢時，將會產(chǎn)生查詢效率低、占用 空間大，甚至完全無法利用索引結構等諸多不良后果。因此只有利用時空索引結 構才能有效地解決時空數(shù)據(jù)的索引問題。 表1 1 已有索引結構研究關系 索引結構 一維 b - t 陽培 基于良t r e e 的級聯(lián)索引 時空索引結構 靜態(tài)r - 1 托黔、r _ t r e e 、r _ t i e e 、q u 釵l _ k 國、b sp - t 伯母 多維 非受限空間 受限空間 歷史位置 3 dr _ 1 托e 。t b n e e 。e l c 軌跡索引 動態(tài) 當前位置 2 + 3r ，r b e e l u r - 。e t c 復合索引 當前未來位置t p r q 啪。嗍r - 1 確。如 在現(xiàn)有關于時空數(shù)據(jù)索引結構的研究中，可依據(jù)物體的運動狀態(tài)分為兩個大 類，即靜態(tài)物體的位置索引與動態(tài)物體的位置索引。靜態(tài)物體的位置索引是指對 分布在多維空間中的靜態(tài)物體( 如建筑物、道路等) 的位置數(shù)據(jù)進行索引；而動 態(tài)物體的位置索引則是指對運動在多維空間中的物體( 如車輛、飛機等) 位置數(shù) 據(jù)進行索引。通常情況下，時空數(shù)據(jù)索引多指后一種索引結構，而前一種索引結 構則被稱為空間數(shù)據(jù)索引。 在空間數(shù)據(jù)索引的研究中，其原理多是通過自上而下、逐級地劃分地理空間 的方法，形成樹狀的索引結構。比較常見的方法包括基于空間劃分的網(wǎng)格方式， 如q u a dt r e e m 2 ，2 5 1 、b s p t r e e 【2 6 2 8 1 、k d t r e e 【2 9 刪、l b t r e e 【2 7 1 等，以及基于 空間對象區(qū)域的層疊外包方式，典型的有r 饑e 【2 0 1 ，以及其諸多變體r + t r e e l 2 3 4 1 、 r 一t r e e 【博j 等。 在時空數(shù)據(jù)索引的研究中，又依據(jù)物體的運動時域不同劃分為三類：對移動 對象歷史位置信息的索引，對移動對象當前位置信息的索引以及對移動對象當前 與未來的位置信息的索引。其中對移動對象歷史數(shù)據(jù)的索引有助于快速查詢移動 對象的歷史運動軌跡，以便對物體運動特性進行統(tǒng)計分析并挖掘出規(guī)律信息，此 4 河海大學碩+ 研究生論文第一章緒論 類中典型的結構有3 dr 1 r e e 【17 1 、m r t r e e i l 9 】、t b t r e e 【1 4 1 等。對移動對象當前位 置的索引則主要用于了解與追蹤物體的實時運動狀態(tài)，以便對現(xiàn)實世界進行模 擬，此類中典型的結構有2 + 3r t r e e 【1 5 l 、l u r 1 r e e 【1 2 】等。對移動對象當前及未來 位置進行索引的結構根據(jù)運動物體的當前位置及運動狀態(tài)，可以對物體的運動趨 勢進行預測。由于此類結構獨特的預測查詢功能( 如：查詢在未來時刻t 區(qū)域r 中 可能存在的物體) 可以為許多l(xiāng) b s 服務提供基礎支持，因而此類索引結構是現(xiàn)在 研究的熱點，也是本文所要闡述的重點。 按照索引方法的不同，對移動對象當前及未來位置的索引結構也可分為三 類：直觀地索引物體運動軌跡的方法，如p m r t r e e 【1 6 i ；將時空域轉換至新空間 的轉換方法，如s t 砌p e s 【6 】的二重轉換方法；參數(shù)化空間方法，即利用隨時間變 化的矩形框將運動物體進行外包，再加以索引的方法。參數(shù)化空間方法是目前使 用最廣的針對移動對象當前及未來位置進行索引的方法，其中最為突出的研究成 果當屬t p l 0 1 r e e 州，它引入了速度矩形框( v e l o c i t yb o u l l d i n gr e c t a n g l e ，v b r ) 的概念可對物體的運動情況加以描述，而其變體t p r 母t r e e 【8 j 由于引入了重插隊 列，提高了結構插入和分裂算法的效率，更是受到了廣泛的使用。 前述的諸多時空索引結構都以非受限時空數(shù)據(jù)作為研究的主體，由于受限時 空數(shù)據(jù)基于道路網(wǎng)而分布并行進，因此其索引方法與上述方法存在著很多不同。 按研究方法的不同，受限時空數(shù)據(jù)的索引可分為兩類：軌跡索引與復合式索 引。軌跡索引針對移動對象在受限空間下的歷史移動軌跡進行索引的方法，如 c 1 1 r i s t i a l ls j e n s e n 等人在2 0 0 3 曾提出通過對移動對象歷史軌跡建模，再利用已 有d b m s 系統(tǒng)管理的方法【9 】，此類方法著重分析歷史受限時空數(shù)據(jù)。復合索引結 構可用于管理實時數(shù)據(jù)索引，它由兩部分組成：上層的空間索引與下層的時空索 引集合。復合索引在管理路網(wǎng)下的移動對象時，其上層部分將路網(wǎng)依據(jù)一定的規(guī) 則劃分為不同的單元，并利用空間索引方法對這些單元進行索引；而依據(jù)上層的 劃分規(guī)則，移動對象集也被劃分為若干個互不相交的子集，每個子集中的移動對 象均行進在相同的路網(wǎng)單元中，并被同一個時空索引所管理。當移動對象從一個 路網(wǎng)單元中駛出，并駛入另一個路網(wǎng)單元時，則此對象的時空數(shù)據(jù)就會被從前一 個路網(wǎng)單元的時空索引中刪除，并插入到當前新的路網(wǎng)單元的時空索引結構中 去。由于復合索引結構比較直觀地反映了路網(wǎng)中移動對象的運動狀態(tài)，且不需要 對其上層索引結構做太多的更新操作( 路網(wǎng)相對靜止，變化少) ，同時，通過將 一個大規(guī)模的時空數(shù)據(jù)集劃分為若干格小規(guī)模的時空數(shù)據(jù)子集，降低了結構的維 護成本，也提高了查詢與更新的效率，因此，復合索引結構【3 】在受限時空數(shù)據(jù)的 索引中使用廣泛，如f n r - t r e e 【1 1 1 、i m t f n 【5 1 、m o n t r e e f 7 1 、i o n r 1 r e e 【4 】均采用 了此種結構。本文的主要工作也是基于復合索引結構的。 5 河?；饘W碩j 二研究生論文第一章緒論 1 3 本文的主要工作 本文以受限空間時空數(shù)據(jù)為研究主體，以復合索引結構為基本方法，針對路 網(wǎng)下移動對象的運動特點，對路網(wǎng)的劃分方式進行了討論，分別提出了基于路段 ( s e g m e n t ) 和基于路口區(qū)域( c r o s sr e g i o n ，c r ) 兩種基本路網(wǎng)單元，對路網(wǎng) 進行劃分，并分別建立了l m t r e e 和c r t r e e 來作為復合索引的上層靜態(tài)索引部 分。本文所做的主要工作如下： ( 1 ) 對路網(wǎng)進行形式化描述，提出路段的概念，以及路段連接的方法，對r r t r e e 以及下層時空索引結構進行描述，同時指出其在運行過程中所存在的問題。 ( 2 ) 對路口區(qū)域進行形式化描述，并指出利用c r 作為新的路網(wǎng)劃分單元有助于 改進現(xiàn)有結構的不足。提出以c r 為基本索引單元的空間索引結構c r t r e e ， 給出其結構及基本算法的描述。 1 4 論文的章節(jié)安排 本文中各章節(jié)安排如下： 第二章介紹l b s 框架。主要分析其框架結構，以及所涉及的關鍵技術，闡 明受限時空數(shù)據(jù)索引在l b s 中的地位。由于追蹤系統(tǒng)是受限時空數(shù)據(jù)庫的關鍵 前提，因此對不同的追蹤策略進行了分析比較。 第三章對路網(wǎng)及其元素進行了形式化的定義，并提出基于路段的路網(wǎng)劃分方 法，以及改進的路網(wǎng)連接算法，以減少路段數(shù)量。同時還提出了以路段作為基本 索引單元構建了路網(wǎng)索引結構i m t r e e ，并利用i 墩t r e e 作為上層結構，設計實 現(xiàn)了基于路段的復合時空數(shù)據(jù)索引結構n c o t r e e 。 第四章對基于路段路網(wǎng)劃分方式進行分析，指出將路網(wǎng)劃分成獨立的路段元 素并索引后，會存在索引不準確以及更新效率不高的問題。因此本文提出了另一 種新的路網(wǎng)劃分單元，路口區(qū)域，并給出路口區(qū)域的形式化定義。同時基于路口 區(qū)域構建了另一種路網(wǎng)索引結構c r t r e e ，給出其各類元素及操作算法的描述， 并對如何構建合適的管理同一路口區(qū)域內移動對象數(shù)據(jù)的時空索引進行了討論。 第五章對本文所涉及的相關內容進行實驗論證。主要對路段劃分和路口區(qū)域 劃分這兩種不同的路網(wǎng)劃分方式進行做索引空間大小、索引準確性以及查詢效率 上的比較，指出各自的優(yōu)勢及缺陷。 第六章對本文所做的工作進行總結，并指出后續(xù)的研究方向。 6 河海人學碩_ j 研究生論文第二章基于位置服務系統(tǒng)及其關鍵技術 第二章基于位置服務系統(tǒng)及其關鍵技術 在現(xiàn)有的智能交通系統(tǒng)中，其智能性主要體現(xiàn)在車輛自我導航與道路自適應 的調節(jié)等功能上。就裝配有g i s 導航設備的車輛而言，它可通過設備來指示自身 的位置，也可計算出前往目標位置的距離最短路徑。 但這種方式存在有兩點不足：一是導航設備必須裝載有所在城市的電子地 圖，而且如果城市道路網(wǎng)由于某種原因而被短期或長期的更改，這種更改也無法 反映到已經(jīng)發(fā)布的電子地圖上；二是導航設備無法反饋道路上的交通狀況。在決 定如何最為便捷地前往目標地址的計算中，距離上的長短僅僅是考量的因素之 一，而道路上交通流狀況則更為重要。當導航設備為車輛選擇了一條距離最短的 路徑后，如果該路徑上的交通狀況十分擁堵，則經(jīng)過此路徑來到達目標地址的時 間很可能會比經(jīng)過更一條距離更長但交通狀況良好的路徑所要花費的時間要長 的多。相同的，在道路的自適應調節(jié)上，盡管在當前的某些道路上可以通過攝像 頭、感應器等設備來監(jiān)測交通流狀況，繼而通過調節(jié)交通燈等設備來疏導道路。 但這種調節(jié)是局部性的，而非整體性的。 因此，如果要解決上述現(xiàn)有技術的局限性，就必須要在城市交通系統(tǒng)中設立 集中式的交通管理中心，對整體路網(wǎng)中的實時交通狀態(tài)進行分析，并結合其它一 些交通相關信息來動態(tài)設置各類交通設施，對移動車輛提供各類l b s ，以達到調 整路網(wǎng)狀態(tài)的目的。 2 1l b s 系統(tǒng) 2 1 1l b s 系統(tǒng)框架 l b s 系統(tǒng)由定位系統(tǒng)、移動對象客戶端、無線通信網(wǎng)絡和中心服務器四部分 組成，其體系結構圖如圖2 1 所示： 在l b s 系統(tǒng)中，移動對象客戶端通常安裝在車輛上，作為l b s 的終端設備， 它需要能夠獲知自身的位置，并將位置數(shù)據(jù)與服務請求等數(shù)據(jù)通過通信網(wǎng)絡傳輸 給中心服務器，同時也可從通信網(wǎng)絡接收來自于中心服務器的服務反饋數(shù)據(jù)。因 此，它必須要裝置有定位終端設備以進行自身定位，無線通信設備以進行數(shù)據(jù)傳 輸，以及便攜式計算設備以進行必要的數(shù)據(jù)處理。 定位系統(tǒng)可由衛(wèi)星定位系統(tǒng)或移動電信定位系統(tǒng)來充當。衛(wèi)星定位系統(tǒng)是利 7 河海大學碩士研究生論文第二章基于位置服務系統(tǒng)及其關鍵技術 用多個部署在太空中的定位衛(wèi)星和若干個地面站組成，通過移動對象所持有的定 位終端，可以確定對象在地球上所處的位置及海拔高度等，其定位精度在1 0 米 左右。由于衛(wèi)星定位終端代價昂貴，普及度不高，因此也可選擇移動電信定位系 統(tǒng)來進行定位。移動電信定位系統(tǒng)是利用移動通信網(wǎng)結合用戶的移動終端設備 ( 如手機等) 進行定位的系統(tǒng)，這種定位的精度在5 0 2 0 0 米左右。 圖2 1 基于位置服務( l o c a t i o nb a s e ds e r v i c e ，l b s ) 系統(tǒng)框架 無線通信網(wǎng)絡是為了便于移動對象客戶端與中心服務器進行數(shù)據(jù)傳輸?shù)拿?體。它可以通過移動通信網(wǎng)，如g p r s 、c d m a 、t d s c d m a 、w i m a ) ( 等2 g 或 3 g 技術來構建，也可通過如w 廿i ，w i f i 等無線局域網(wǎng)技術來實現(xiàn)。 中心服務器是提供l b s 的核心所在。為了能提供準確有效的位置服務，如 最優(yōu)路徑查詢、周邊交況預測、路網(wǎng)調度等，它需要配置有強大的數(shù)據(jù)計算能力， 良好的通訊網(wǎng)絡，從而可以實現(xiàn)與眾多終端設備的交互或和其它資源的互連，以 便能獲取各類信息并進行相應的管理與分析。中心服務器由以下四部分組成： l b s 服務接口、追蹤系統(tǒng)、地理信息系統(tǒng)與時空數(shù)據(jù)庫。l b s 服務接口主要用 于接收來自客戶端的服務請求，并將位置信息發(fā)往追蹤系統(tǒng)，將服務信息發(fā)往地 理信息系統(tǒng)，并將服務反饋傳送給客戶端。追蹤系統(tǒng)在接收到客戶的位置信息后， 將相關數(shù)據(jù)寫入時空數(shù)據(jù)庫，并告知客戶端當前的追蹤范圍，以便減少數(shù)據(jù)更新 的次數(shù)。地理信息系統(tǒng)則服務具體的服務請求處理，并從時空數(shù)據(jù)庫中獲取必要 的數(shù)據(jù)支持。時空數(shù)據(jù)庫用于存儲客戶端的位置數(shù)據(jù)等地理信息系統(tǒng)會用到的數(shù) 據(jù)內容，以便提供支持，其中的時空數(shù)據(jù)索引則主要用于管理客戶端的位置數(shù)據(jù)， 以便進行快速的查詢與處理。 國 河海大學碩士研究生論文第二章基于位置服務系統(tǒng)及其關鍵技術 2 1 2l b s 關鍵技術 2 1 2 1 空間定位技術 空間定位技術使得移動對象客戶端能夠持續(xù)獲取自己在路網(wǎng)中的位置，這是 所有基于位置服務所需要的基礎數(shù)據(jù)。在現(xiàn)有技術下，衛(wèi)星定位技術與移動電信 定位技術是較為常見的。 衛(wèi)星定位技術，如美國的g p s 技術，歐州的“伽利略”計劃，我國的“北 斗 計劃都屬于此類技術。該技術由三大部分組成：空間定位衛(wèi)星系統(tǒng)、地面監(jiān) 控系統(tǒng)、用戶定位信號接收機。用戶只需配備專用的定位信號接收機，即可獲知 自己所處的位置。這種定位技術的優(yōu)勢在于：全天候，不受任何天氣的影響；全 球覆蓋( 高達9 8 ) ；三維定速定時高精度；快速、省時、高效率；應用廣泛、 多功能；可移動定位。g p s 能提供2 0 3 0 米的定位精度，定位時間在3 0 秒至1 分鐘之內。由于這種方案需要有配有專用的信號接收裝置，因此價格稍顯昂貴， 不易普及。 移動電信定位技術提供了一種較為簡便的定位手段，它利用g s m 移動通信 網(wǎng)的蜂窩技術來實現(xiàn)位置信息的查詢。這是因為g s m 無線通信網(wǎng)是由許多像蜜 蜂蜂窩一樣的小區(qū)構建而成的，每個小區(qū)都有自己的編號，通過手機所在小區(qū)的 識別號就可以知道手機所在區(qū)域。其主要定位手段有： ( 1 ) c o o ( c e l lo f o r i g i n ) 定位技術。c o o 定位技術即基于c e l l i d ( 小區(qū)識別號) 的定位技術。它通過采集移動臺所處的小區(qū)識別號來確定用戶的位置。這種 技術的定位精度取決于所在小區(qū)的半徑，如在市區(qū)，基站密度較高，c o o 定 位精度可以達到2 0 0 米左右；而在郊區(qū)，基站密度較低，c o o 定位精度只能 達到一兩公里。 ( 2 ) 增強觀測時差技術( e 1 1 1 1 a n c e do b s e r v e dt i m ed i 髓r e n c e ，e o t d ) 。e o t d 是 通過放置位置接收器或參考點實現(xiàn)的，這些參考點分布在較廣的區(qū)域內的許 多站點上，作為位置測量單元( l o c a t i o nm e a s u r e m e n tu n i t ，l m u ) 以覆蓋無 線網(wǎng)絡。每個參考點都有一個精確的定時源，當具有e o t d 功能的手機和 位置測量單元接收到來自至少3 個基站信號時，從每個基站到達手機和位置 測量單元的時間差將被計算出來，這些差值可以被用來產(chǎn)生幾組交叉雙曲 線，并由此估計出手機的位置。e o t d 方案可以提供比c o o 高得多的定位 精度，約在5 0 1 5 0 米左右。但這種方案對手機和網(wǎng)絡的要求較高，實現(xiàn)也比 較復雜。 9 河海人學碩+ 研究生論文 第二章基于位置服務系統(tǒng)及j e 關鍵技術 ( 3 ) 此外，類似t d o a 、t o a 、a o a 、t a 等技術均屬于移動電信定位技術的范 疇。移動電信技術由于采用普及度很廣的移動電話作為定位的終端設備，因 此方便推廣，但定位精度較低。 2 1 2 2 追蹤技術 盡管移動對象客戶端借助定位技術能夠持繼獲知自身在路網(wǎng)中的位置，但是 作為l b s 核心部件的中心服務器卻無法實時地更新路網(wǎng)中移動對象的準確位置。 其問題首先在于移動對象的數(shù)量巨大，如前文1 1 節(jié)所述，北京市目前的汽車保 有量就已超過3 0 0 萬輛。其次無線通信網(wǎng)絡的帶寬十分有限，最新的t d s c d m a 技術，其最高數(shù)據(jù)傳輸率也僅有2 8 m b p s ，而類似的w c d m a 、c d m a2 0 0 0 等 其最高速率也僅有2 m b p s ，這種有限的帶寬資源是無法支撐大數(shù)據(jù)量、高頻率的 數(shù)據(jù)更新操作的。因此如何能夠使中心服務器在降低移動對象更新頻率的同時， 又能保證其所管理的對象位置是較為精確的呢? 追蹤技術的出現(xiàn)使得這一問題 的解決成為可能。具體的追蹤技術，以及不同的追蹤策略的比較將在后述做更為 詳細的說明。 2 1 2 3 地理信息處理技術 地理信息服務技術針對不同區(qū)域和城市的基礎的地圖數(shù)據(jù)，簡稱電子地圖， 提供對電子地圖的管理、發(fā)布、地理分析、地理編碼、路徑搜索等諸多功能。除 此之外，地理信息處理技術還能利用時空數(shù)據(jù)庫中所管理的移動對象時空數(shù)據(jù)， 模擬當前路網(wǎng)中的交通狀態(tài)，加以分析，亦可結合其它交通相關信息的分析，來 對未來一段時間內的交通狀態(tài)進行預測，以期為移動對象提供盡可能全面與豐富 的l b s 內容。 系統(tǒng)分為數(shù)據(jù)庫管理、地理信息引擎、地理信息服務3 個層次。其中數(shù)據(jù)庫 管理負責管理運營平臺的所有數(shù)據(jù)。地理信息引擎實現(xiàn)對底層數(shù)據(jù)庫的管理、操 作，并支持基于平臺的二次開發(fā)，一般采用成熟的地理信息平臺軟件和功能軟件。 地理信息服務分為地理信息核心服務和地理信息應用服務框架兩個部分，其中核 心服務是在地理信息引擎的基礎上提供的地理信息發(fā)布、地理信息分析、路徑搜 索、地理編碼等核心服務功能；應用服務框架是在綜合各種地理信息核心服務的 基礎上提供的應用服務框架，包括城市黃頁服務、個人導航服務、公交換乘服務、 朋友位置查找服務、地址查找服務等。其核心功能有： ( 1 ) 地圖發(fā)布引擎：根據(jù)用戶的需要生成適用于不同終端的地圖。所發(fā)布的地圖 1 0 河海大學碩士研究生論文第二章基于位置服務系統(tǒng)及其關鍵技術 有矢量、柵格或混合模式。 ( 2 ) 地理分析引擎：根據(jù)經(jīng)緯度定位地圖及相關查詢功能。例如可以根據(jù)經(jīng)緯度 查出一定范圍內地圖的基本信息( 區(qū)、街道、大廈) ；可以根據(jù)2 個點的經(jīng) 緯度給出距離信息及乘車信息；可以根據(jù)經(jīng)緯度查詢到一些基本的黃頁信息 ( 如a t m 機、餐館、卡拉o k 、銀行等) 。 ( 3 ) 地理編碼引擎：地理編碼服務器轉換基于字符串的地址( 如門牌號碼) ，使 之成為地圖上準確的經(jīng)緯度點。要提供上述服務，l b s 空間數(shù)據(jù)庫除了包含 電子地圖數(shù)據(jù)庫外，還必須提供地理編碼數(shù)據(jù)庫。 ( 4 ) 路徑搜索引擎：根據(jù)給定的2 個點的位置尋找兩點間距離最短路徑或者時間 最短路徑，并產(chǎn)生描述推薦路線的街道圖形和包括預計路程長度及時間在內 的文字描述，該服務可用于個人導航和車載導航以及其它行業(yè)的應用。根據(jù) 用戶的請求，服務引擎能夠在圖形路線介紹和文字指南中重點標示出娛樂場 所、路標、交通事故和道路狀況( 施工、天氣影響、路面狀況等) 。 2 1 2 4 空間數(shù)據(jù)庫技術 空間數(shù)據(jù)庫存儲和管理是l b s 服務平臺的關鍵部分。l b s 空間數(shù)據(jù)可以在 大型商用關系數(shù)據(jù)庫管理系統(tǒng)的基礎上構建，以便實現(xiàn)空間實體幾何數(shù)據(jù)和屬性 數(shù)據(jù)的一體化存儲，充分利用數(shù)據(jù)庫本身的管理能力實現(xiàn)海量空間數(shù)據(jù)的存儲和 管理。如中國聯(lián)通的l b s 服務平臺采用了o r a c l es p a t i a l 來管理和存儲空間數(shù)據(jù)。 除了空間數(shù)據(jù)存儲、空間分析、空間查詢等基本功能外，空間數(shù)據(jù)庫系統(tǒng)還必須 實現(xiàn)以下功能。 ( 1 ) 多比例尺圖庫管理：即建立金字塔型的多級比例尺區(qū)域索引和圖層索引表。 ( 2 ) 元數(shù)據(jù)管理：通過元數(shù)據(jù)對分布在各個場所信息資源做有效管理與共享。 ( 3 ) 數(shù)據(jù)安全管理：數(shù)據(jù)中心能夠在數(shù)據(jù)交換時保障數(shù)據(jù)安全。 ( 4 ) 數(shù)據(jù)遠程協(xié)同工作管理與數(shù)據(jù)同步：重點解決多級服務器之間的動態(tài)數(shù)據(jù)復 制問題與數(shù)據(jù)遠程調用問題，實現(xiàn)空間數(shù)據(jù)操作的主要功能，數(shù)據(jù)版本控制。 2 2 追蹤技術分析 合適的位置追蹤系統(tǒng)是l b s 的重要組成部分。交通控制管理部門的中心服 務器只有在盡可能準確地獲取路網(wǎng)中所有移動對象的實時位置的前提之下，才能 夠對當前路網(wǎng)中的具體交通情況做出準確的判斷，并進行有效的規(guī)劃以提供相應 的服務。由于中心服務器在l b s 中處于被動接收的位置，即它不能夠主動收集 河海大學碩士研究生論文 第二章基于位置服務系統(tǒng)及其關鍵技術 移動對象位置數(shù)據(jù)，而只能被動接收移動對象所上傳的信息。若移動對象能夠在 行進過程中，不間斷地向中心服務器報告位置自然是保證數(shù)據(jù)精確的最佳途徑。 但如2 2 2 節(jié)所述，由于移動對象數(shù)量巨大，而無線通信網(wǎng)絡的帶寬有限，導致 中心服務器無法通過持續(xù)更新的方式，實時地掌握轄域內移動對象的精確位置。 因此需要使用合適的追蹤技術來推算移動對象的可能位置，使得在不降低用戶位 置的精確度的前提下，盡可能地減少更新位置操作的頻率。因此只有采用合適的 移動對象位置追蹤系統(tǒng)，使得中心服務器通過低密度的數(shù)據(jù)更新方式也能夠準確 地獲知各移動對象的實時位置是保障l b s 有效性的重要前提。 基于這一目的，丹麥奧爾堡大學的c s j e n s e n 等人在2 0 0 4 年提出了一種基 于道路網(wǎng)的移動對象追蹤系統(tǒng)。本節(jié)將重點對這一追蹤系統(tǒng)進行描述，并分析數(shù) 種不同的追蹤策略：基于點的追蹤、基于向量的追蹤以及基于路段的追蹤。在對 這幾種追蹤策略進行比較后，則將引出本文的研究方向。 2 2 1 基于道路網(wǎng)的移動對象追蹤系統(tǒng) 圖2 2 給出了c s j e n s e n 等人所提出的移動對象追蹤流程，這也是大多數(shù)l b s 系統(tǒng)中所使用的方法。這個系統(tǒng)的基本思想是，在追蹤系統(tǒng)獲得某一客戶端的實 時位置后，可依據(jù)對象當前的位置與速度，決定采用某種追蹤策略來對對象進行 追蹤定位，并將選定的追蹤策略反饋給客戶端，由客戶端計算出對應的預測范圍。 所謂預測范圍是指，系統(tǒng)認為該用戶的運動軌跡在將來某段時間內不會超出的某 個區(qū)域。因此當客戶端獲得預測范圍后，它只需在每次獲得實時位置信息時，將 當前位置與預測范圍進行比較，若其依舊在預測范圍內運動時，就不需要向中心 服務器提交更新，若超出了預測范圍，則需要提交更新，以獲得新的預測范圍。 整個系統(tǒng)按照c s 架構部署，分為左右兩個部分。圖左側為客戶端部分，即 安裝在l b s 系統(tǒng)的移動對象客戶端部分的軟件，而右側則為服務端部分，即是 l b s 系統(tǒng)的中心服務器的追蹤系統(tǒng)部分?？蛻舳耸紫葟亩ㄎ辉O備獲得其位置信 息，然后將其位置數(shù)據(jù)發(fā)送給服務端。服務端得到位置數(shù)據(jù)后，首先對時空數(shù)據(jù) 庫進行更新，繼而依據(jù)客戶端的位置、速度等信息來決定適用的追蹤策略，并將 此追蹤策略反饋給客戶端。若選用的是基于路段的追蹤策略時，則需計算出對象 所在路段的標號。在獲取服務端的追蹤策略后，客戶端會計算出相應的預測范圍。 在后續(xù)過程中，客戶端在每次獲取實時位置的同時，都要將實時位置與預測范圍 進行比較。如果這兩個位置差超出了給定的精度要求，客戶端產(chǎn)生一更新請求給 服務端，如果沒有，則等待下一個定位時刻的到來。這個過程一直進行直到客戶 端終止追蹤服務為止。 1 2 河海大學碩士研究生論文第二章基于位置服務系統(tǒng)及其關鍵技術 服務端 h 撇愀h 犍怒紛 審j 感多 l ，離f 毽 圖2 2 追蹤系統(tǒng)框架結構 2 2 2 不同的移動對象追蹤策略 常見的移動對象追蹤策略有三種：基于點的追蹤策略( p o i m b a s e dt r a c k i n g ) 【2 】；基于向量的追蹤策略( v e c t o r - b a s e dt r a c k i n g ) 【1 0 】；基于路段的追蹤策略 ( s e g m e n t b a s e dt r a c k i n g ) 【2 1 。這些追蹤策略在對位置數(shù)據(jù)的追蹤流程上，與圖 2 2 描述的追蹤流程相