中心導航系統終端地圖預取和更新策略研究

石向亭，秦 俊，陳思國，牟賀銘，余雪崗，曲良東

（吉林大學計算機科學與技術學院 符號計算與知識工程教育部重點實驗室，吉林 長春130012）

0 引 言

導航系統目前正經歷著由傳統自主導航到中心導航［1－3］轉變的過程。在單車自主導航中，為駕駛員提供引路服務時，是依據靜態存儲在本地的地理信息進行的路徑規劃；而中心導航系統的優勢在于車載終端可以通過網絡實時地獲得導航中心所提供的相關信息服務［4］和地圖單元數據，其中包括基于實時交通路況的導航［5－6］。從而達到對于駕駛員來說，他們都可以使用實時路況導航服務，這將使導航系統的使用方式達到徹底的改變。更重要的是，從交通系統的整體來看，中心導航存在著傳統單車自主導航所不可比擬的優勢，即其具有引導車輛避開擁堵路段的交通疏導功效。

地圖數據單元不必全部存儲在車載導航終端。只要系統定義好導航中心與車載終端之間進行數據交換的協議，即可通過網絡對終端所需地圖數據進行在線下載，從而降低了車載終端設計和實現的復雜度，使其成為一個人機接口 （human machine interface，HMI）而存在；同時，目前中國快速發展的路網和路邊POI（point of interest）與此種設計理念也達到極大的契合，中心導航的基本系統框架如圖1所示。然而如何解決地圖數據網絡傳輸延時問題，保證終端系統能夠實時的使用地圖數據和實時顯示地圖是中心導航系統亟待解決的問題。

圖1 中心導航的基本系統框架

地圖的分塊存儲［7］、分層加載［8］、分區索引［9］和基于二級緩存的地圖顯示［10］等方法被很多研究這提出，這些方案使地圖數據的存儲、傳輸和顯示效率達到了一定的提高。通過對以方案的分析，選擇使用地圖分塊存儲和地圖顯示二級緩存的方法以達到滿足嵌入式系統內存小、運算慢得特點，同時還可以提高地圖傳輸和顯示效率，另外對地圖數據進行的預取和更新策略也是在電子地圖分塊存儲的基礎上提出來的，結合基于雙緩存的局部地圖刷新機制保證車載終端電子地圖顯示的實時性。

1 車載終端與系統服務器之間的通信

按照地圖分塊策略，服務器將矢量地圖數據按橫向和縱向分塊存儲，每一個分塊地圖包含所有的圖層。每一個分塊為 “地圖單元”，每一個地圖單元將分配一個編號，為“地圖單元號”。為了方便終端使用地圖單元，每個地圖單元數據在經過投影變換轉為平面坐標 （其中原點在左上角）后存儲到數據庫中，同時存儲該地圖單元經緯度范圍以及地圖單元號。服務器建立了經緯度坐標和地圖單元號之間的對應關系，并利用地圖單元號索引機制提高地圖塊查找效率。服務器有個模塊專門處理實時的交通信息［11］，并集成到分塊地圖數據庫中。

車載終端系統分為數據管理模塊、地圖繪制模塊和顯示模塊：①數據管理模塊，負責地圖數據請求、存儲和刪除；②地圖繪制模塊，負責繪制地圖數據和備用緩存的更新；③顯示模塊，負責地圖畫面刷新。車載終端系統啟動時，首先由數據管理模塊與服務器建立連接，傳輸地圖數據。

1.1 地圖傳輸協議

協議的設計保障了服務器和車載終端之間地圖數據的實時和有效傳輸，同時傳輸層的TCP協議是可靠的傳輸協議，因此終端和服務器間建立的TCP連接，一方面可以使數據傳輸認為是可靠的，另一方面也避免了在設計應用層協議時再次考慮可靠傳輸的問題。兩者之間協議包括數據請求協議和數據發送協議。

1.1.1 地圖單元請求協議

請求報文主要包括地圖數據初始化報文和地圖數據更新報文，其結構見圖2。其中 “類型標識”用來區分兩類報文，傳輸地圖數表示終端向服務器請求的數據單元數量，經緯度坐標表示終端的位置。下面進行詳細介紹。

圖2 地圖數據請求報文

類型標識為1時，表示終端系統請求進行地圖數據初始化，這時所需地圖單元數為25。為什么需要傳輸25個地圖單元，將在第2部分詳解。終端通過GPS（global positioning system）接收機獲得自身經緯度坐標［12］，發送給服務器。服務器首先查找包含這一坐標的地圖單元，然后查找以該地圖單元為中心的5行5列的25個地圖單元，服務器將按照上北下南的方向，從左到右從上到下，依次傳1－25張地圖單元數據到終端。類型標識為2時，表示終端向中心系統請求進行地圖數據更新。主要包括需要更新的地圖單元數及相應的地圖數據。

1.1.2 地圖單元發送協議

響應車載終端的地圖數據請求報文之后，服務器端向其傳輸所請求的地圖數據，發送數據報文的協議主要由地圖頭部和地圖元素兩個部分組成。

（1）地圖頭部

每塊地圖所表示的范圍由邊界經緯度定義，此范圍主要用來判斷車輛是否在此塊地圖單元中。每塊地圖數據單元的分層數用地圖層數記錄，便于車載終端控制地圖數據的接收。其結構如圖3所示。

圖3 地圖數據單元頭部

（2）地圖數據元素

各種地圖數據元素的在網絡中的傳輸格式見圖4。

地圖單元當前層數據傳輸結束用標識0表示。

傳送數據元素為點時，用標識1表示；此時不發送點的個數這一選項；接下來的兩個短整型，表示了該點相對此塊地圖邊界的偏移量；標注的字節數由標注長度n來表示，為0時表示當前點元素沒有標注；該點元素的顏色和樣式用屬性字段表示。

圖4 地圖元素數據格式

傳送數據元素為線時，用標識2表示；若點的個數為2，則表示該地圖元素為線段；若大于2，則表示該元素為折線，并且該項記錄了此折線所包含的點的數目；接下來的字段是該元素中點的坐標以及此元素的標注；當前的路況信息則由其屬性指示出來。

傳送數據元素是一個區域時，用標識3時；點的個數表明了該區域的邊界線所包含點的數量；接下來的字段是該元素中點的坐標以及此區域的相關標注；所繪制區域的樣式和顏色用屬性字段表示。

1.2 地圖數據的組織

車載終端系統定義了地圖數據單元結構體，對從服務器端接收到的每塊地圖數據都作為獨立的單元進行存儲，方便了車載終端的管理。每個結構體都存儲該塊地圖的頭部和圖層數據，每個圖層數據又包含多種地圖數據元素，為了提高空間的使用率，采用鏈表的存儲方式來保存數量不固定的圖層及其中數據元素信息。

本系統參照了MIF［13］中地圖的格式對點、線段、折線和區域4種圖形對象進行了定義，具體結構如：

（1）坐標點結構體。定義了指示其平面位置的x和y；以及指向下一個坐標點的指針，以便存儲不同數據元素中點的坐標信息。

struct GP｛

int px；

int py；

struct GP＊pnext；｝

（2）點結構體。定義了表示該點具體位置信息的坐標點結構體，以及存儲標注的字符串指針，以及指向下一個點結構體的指針。

struct Point｛

struct GP pgp；

char＊plabel；

struct Point＊pnext；｝

（3）線段結構體。定義了表示該線段起止位置的起止點坐標結構體，存儲標注的指針，和指向下一線條段的指針。

struct Line｛

struct GP lstart；

struct GP lend；

char＊llabel；

struct Line＊lnext；｝

struct Pline｛

int pointnum；

struct GP＊pgp；

char＊plable；

struct Pline＊pnext；｝

（5）區域結構體。定義了該區域所包含節點數，坐標點結構體鏈表，中心坐標，存儲標注的指針，以及指向下一個區域的指針。

struct Region｛

那是我最后一次看到萬姐，背著一個比她身體還要大的包袱。老公要下樓幫她攔輛出租車，卻被她攔住了，一個人搖搖欲墜地向樓下走去。我這才發現，原來她住在我家時，竟然做了那么多的衣服。

int pointnum；

struct GP＊rgp；

struct GP rcenter；

char＊rlable；

struct Region＊rnext；｝

1.3 建立地圖單元

車載終端系統根據協議依次接收多個地圖數據單元，終端將接收的地圖單元存儲到地圖數據單元結構體。圖5指示了終端接收地圖數據單元的具體流程。

2 地圖數據的預取和更新

空間相關性是地圖數據單元所具有的特點，因此當某一塊地圖數據單元被車輛使用時，在其周圍的其它地圖單元數據也有很大機率被使用。車載終端系統的接收、存儲、繪制、預取，以及更新都是以地圖數據單元為基本單位進行的，這樣做不僅提高了預取和更新的效率，而且使已下載地圖的使用效率有所提高。在進行了測算，并經過實際的上車實驗后，確定終端系統任意時刻都存儲25塊地圖數據單元。具體的邏輯存儲結構如圖6所示，其中每個地圖數據單元均為正方形，當車輛在13號地圖數據單元的中央行駛時，在終端上可能顯示的地圖范圍由灰色區域指出，占整個地圖數據的36%；當車輛在其內漫游時，可能使用到的區域如黑色和灰色區域所示，占整個地圖數據的64%；預取的地圖數據由剩余白色區域所示，占地圖數據的36%。當車輛行駛出13號地圖單元時，則需進行地圖數據的更新操作。考慮終端系統地圖數據更新的時間為t，T是車輛從13號單元行駛到周圍任一單元中心線上時間，當T＞t時，即可保證地圖的實時顯示。

2.1 地圖數據單元初始化

如圖6所示，初始化時終端系統存儲25塊地圖數據單元。為了在車載終端顯示地圖時使車輛的移動方向始終向上，就需要更大的空間對地圖數據進行存儲。本系統中所使用的觸摸屏分辨率是640＊480，其對角線為800，根據以上分析，當車輛在中間行駛時，其可能用到的地圖單元數為9，即每塊地圖單元繪制后的像素寬度至少為屏幕對角線長度的1／3，最后系統采取繪制后地圖數據像素的寬度為300以便于計算，為了降低地圖數據繪制的難度，采取實際長度一米用一個像素表示，因此，300m＊300m為本系統所使用的地圖數據單元的大小；中心服務器也采用這一標準進行地圖數據劃分，以達到簡化的目的。終端將接收的25塊地圖數據單元存儲到一個由5＊5的二維數組指針鏈接起來的地圖數據單元結構體中，并且根據各自所在二維數組中行和列的位置，計算出該地圖單元由平面坐標轉為屏幕坐標的X偏移量和Y偏移量。車載終端對其所接收的每個地圖數據單元都進行遍歷，將其中的各地圖元素的坐標與其所在地圖單元的偏移量相加，之后以 （750，750）為旋轉中心，以車輛行駛的角度為旋轉角度進行旋轉變換，并將得到的結果繪制大小為1500＊1500的備用緩沖區HDC中。

圖5 建立地圖單元流程

圖6 地圖數據邏輯存儲結構

2.2 動態刷新地圖和更新地圖數據

為了在導航過程中顯示好的車輛移動效果需要對畫面不斷進行刷新，同時為了降低地圖數據繪制時間，保證顯示的實時性，本系統最后采用的局部刷新機制是基于雙緩存的［10］，這樣可以使得終端在任意時刻使用地圖都不需要重新繪制，而僅僅是將所需要的地圖拷貝到正確位置即可，提高了地圖刷新的速度。地圖數據和備用緩存的更新只有在車輛形式出13號地圖單元才會發生。

2.2.1 動態刷新地圖數據

終端系統采取地圖向著車輛行駛的反向移動，而保持車輛不動的顯示在屏幕的中間位置。系統所使用的備用緩沖區橫縱坐標范圍均為0到1500。刷新地圖操作如下：

（1）初始運行時，利用函數BitBlt以 （750，750）為中心將大小為640＊480的畫面從備用HDC拷貝到當前主窗口HDC。

（2）每隔1s獲得車輛GPS坐標，首先同過道路匹配［14］對GPS坐標進行校正，從而判斷出車輛當前所處地圖數據單元的編號，即可根據相應公式對當前坐標進行投影變換，所得的平面坐標再加上該地圖單元的X偏移量和Y偏移量得出坐標，并依據車輛行駛角度計算出其旋轉之后的坐標，即可得進行顯示地圖的操作。如果坐標為 （650，705），則利用BitBlt函數以 （650－320，705－240）、（650＋320，705＋240）為矩形邊界點拷貝640＊480的畫面到主窗口HDC。

（3）當車輛的行駛角度變化小于5o時，不必進行地圖重繪，否則利用新的行駛角度對緩沖區進行重繪；這樣極大的降低了地圖繪制次數。

（4）如果車輛在13號地圖單元內行駛時，重復 （2）操作，否則觸發 （5）操作。

（5）更新地圖數據單元，并且重繪備用HDC。

2.2.2 地圖數據和備用HDC的更新

由于系統是以單元為單位對地圖數據進行存儲，為了提高地圖利用率，當需要更新地圖數據和重繪備用HDC時也都是按單元進行的。如果車輛駛出13號地圖單元，將定義一個以當前所處單元為中心的5＊5矩陣，對此矩陣內沒有數據的單元進行請求更新操作。下面以車輛駛入18號地圖單元為例對更新過程進行介紹：

（1）車輛行駛到18號地圖單元，將對25個地圖單元以此為中心進行更新操作，并丟棄原有的1、2、3、4、5共5張地圖。

（2）將原來地圖編號為6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25的地圖向上方移動一個單元的距離，變為1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20。

（3）之后向服務器請求21、22、23、24、25號地圖單元。如果當前車輛行駛方向變化小于5°，則將備用HDC中對應的圖像利用BitBlt函數整體向上移動，同時將21、22、23、24、25地圖單元旋轉之后的位置用空白矩形進行填充，并在此繪制更新之后的地圖數據；當行駛方向變化大于5度時，則根據當前的25塊地圖數據和車輛行駛方向對備用HDC重新進行旋轉繪制。

其它情況下更新過程類似，當車輛駛入19、17、9、7號地圖單元，會更新9塊地圖數據，即重用原有64%的數據；當駛入18、14、12、8號地圖單元時，會對5塊地圖數據進行更新操作，而重用原有數據的80%。如果車輛不在當前地圖內，系統將重新初始化。

3 實驗和分析

采用仿真測試和上車測試兩種實驗方法進行測試，以驗證本系統所采取預取策略的有效性。上車測試時，車輛的當前坐標利用GPS接收機實時獲取，并對其進行存儲；仿真測試則是利用軟件以某一特定速度模擬產生存儲的GPS坐標，以獲得車輛在不受路況環境影響而勻速行駛時的數據，其它環境兩者相同，并使用CDMA進行網絡通信。

實驗所使用的環境配置如下：①CPU是以ARM920T為核心的32位RISC微處理器S3C2410；②64Mbytes 32位SDRAM以及16Mbytes16位FLASH；③10M／100M自適應以太網接口；④一個GPS接收機。一個分辨率為640＊480的10.1英寸觸摸屏及其接口和RS232接口；一個CDMA模塊；一個TFT LCD接口和標準20針JTAG調試接口；以及實時時鐘 （RTC）單元。車載終端的操作系統是內核版本號為2.4.18－rmk7的 ARM－Linux，同時選取嵌入式圖形軟件［15］MiniGUI繪制地圖。使用某市地圖，其覆蓋面積約為20.43km＊19.83km，數據分為五層，總量為93.3M。實驗環境如圖7所示。

圖7 實驗環境

測試數據如下：①更新地圖單元中使用的數目占更新總數的比例，即為命中率HR （hit ratio）；②系統初始化后預取次數與從初始化完成到當前預取完成時間的商，即地圖單元預取頻率 MPR （map prefetch ratio）；③系統接收總數據量與更新時間的商，即單位時間更新數據量UTDM（unit time update amount）；④更新地圖時間與地圖單元總數的商，即更新地圖單元的平均時間MUAT （map update average time）。其中，更新時間即為接收、繪制和刪除地圖數據的時間之和。表1給出了一些測試數據。

表1 測試數據

上車主要測試了當車速介于 （15～36km／h和36～66 km／h）兩個不同的區間時系統的性能，分別在市區和靠近郊區的區域進行實驗；為了使仿真實驗的行駛軌跡與上車實驗大體相同，根據上車實驗兩種情況下的GPS坐標進行仿真實驗，并將速度分別設置為28.8km／h和46.8km／h。

在所得實驗數據中，地圖數據單元的命中率基本上處于0.6235～0.7333之間。測試使用地圖數據單元的平均數據量約等于UTDM與MUAT的乘積，由此可以得出當車速V較慢時，其經過的區域數據量較大，反之數據量則較小；這與上車測試中市區測試時車速較慢且數據量較大，以及靠近郊區測試時車速較大且數據量較小相對應。地圖單元數據量的大小與單位時間內傳輸的數據量也相互影響；若地圖單元數據量傳輸較大，則在一定程度上可以提高網絡帶寬的利用率，從而使UTDM也相對較高；同時對比測試數據中的UTDM列發現，仿真測試時單位時間更新數據量比上車測試時大，可知車速的大小在某種程度上會影響到CDMA的傳輸。同時，速度V越快，則相應MPR就越高，由此可知速度與更新頻率成正比關系，且兩者的商在數值上接近1100。

實驗分析：T＝S／V為本系統的預取時間，其中S是預取距離，V為車輛的行駛速度。由公式可知：當S固定時，車速越大則時間越小。當網絡傳輸速率固定時，更新地圖單元數和其數據量與地圖更新時間t成正比。更新地圖單元數有9和5兩種情況，假設其為9，以800＊800為使用范圍進行分析得到S＞＝200m；選擇表1中最大的MUAT作為參考值，則可得出當車速V＜＝ （S／（n×MUAT））時，即可得到滿足。根據此公式及相關實驗數據可知，若要保證T＞t成立，速度V最大為158km／h，這一速度遠大于車輛在市區內行駛時的速度。如果某個地圖單元數據量較大，就說明其包含道路的路況信息較為復雜，此時車速必然比正常情況小，從而使T更大，亦可實時地顯示地圖信息。通過以上分析可得結論：本文的策略可以保障終端系統地圖顯示實時性。

4 結束語

本文提出通過網絡下載電子地圖時，使用對地圖進行分塊傳輸和存儲的方法提高傳輸效率和使用效率，以此為基礎，提出了預取和更新地圖數據的策略。當需要對地圖數據進行更新時，為了保障實時地顯示地圖，采用在繼續使用原有數據的同時對地圖數據進行預取的方法。經過實驗證明此方法可以保證地圖實時顯示。這種方法為中心導航的方式提供了基礎，但在如何根據現有地圖和車輛位置相結合進行地圖數據的預取、預取數據大小設置、以及提高地圖單元命中率方面，還存在更多的研究，以更好地保障地圖實時顯示。

［1］HU Jiyong.Design and development of vehicular wireless terminal in network－based central navigation［D］.Xiamen：Xiamen University，2009：13－19 （in Chinese）.［胡繼勇.車輛聯網式中心導航系統車載無線終端的研發 ［D］.廈門：廈門大學，2009：13－19.］

［2］YANG Xuejun.Research on algorithms and implement software about the central－type navigation system ［D］.Changchun：Jilin University，2006：4－14 （in Chinese）.［楊學軍.中心式導航算法的研究和應用軟件的實現 ［D］.長春：吉林大學，2006：4－14.］

［3］SHAO Yuning.Research on several key technologies of vehicle electronic map for real－time car navigation ［D］.Guangzhou：Guangdong University of Technology，2008：9－26 （in Chinese）.［邵于寧.實時車載導航系統中的電子地圖若干關鍵技術研究 ［D］.廣州：廣東工業大學，2008：9－26.］

［4］WANG Wenchuan，XIA Hongshan.Study on the embedded－GIS for VNS and its implementation ［D］.Nanjing：Nanjing University of Aeronautics and Astronautics，2005：12－35 （in Chinese）.［王文川，夏洪山.面向車載導航的嵌入式GIS研究與實現 ［D］.南京：南京航空航天大學，2005：12－35.］

［5］LI Xu.Research on the key techniques of vehicular sensor networks and applications ［D］.Shanghai：Shanghai Jiaotong University，2009：44－50 （in Chinese）.［李旭.車載傳感器網絡的應用及關鍵技術研究 ［D］.上海：上海交通大學，2009：44－50.］

［6］XU Li.Performance evaluation of vehicle－based mobile sensor networks for traffic monitoring［J］.IEEE Transactions on Vehicular Technology，2009，58 （4）：1647－1653.

［7］WU Xueling，LI qingquan，REN Fu.Bidirectional A＊algorithm based on hierarchical and block data or organization ［J］.Journal of Geomatics，2006，31 （8）：1－3 （in Chinese）. ［武雪玲，李清泉，任福.基于分層分塊數據組織的雙向A＊算法［J］.測繪信息工程，2006，31 （8）：1－3.］

［8］LI Jianyuan.Study of hierarchical path guidance algorithm and strategies ［D］Xi’an：Shanxi Normal University，2007：16－20（in Chinese）.［李建元.分層路徑誘導算法與策略研究 ［D］西安：陜西師范大學，2007：16－20.］

［9］XU Jinghai，LI Qingquan，SONG Ying，et al.Research on map displayment based on Kiwi data format ［J］.Geomatics and Information Science of Wuhan University，2005，30 （10）：867－869（in Chinese）.［徐敬海，李清泉，宋鶯，等.基于Kiwi數據格式的地圖顯示研究 ［J］.武漢大學學報信息科學版，2005，30 （10）：867－869.］

［10］MA Yaming，ZHANG Yajun，ZHANG Ruisheng.Study on fast displaying strategies of vector map based on VxWorks［J］.Journal of Geomatics Science and Technology，2009，26（4）：300－304 （in Chinese）. ［馬亞明，張亞軍，張瑞生.嵌入式GIS中矢量地圖快速顯示策略研究 ［J］.測繪科學技術學報，2009，26 （4）：300－304.］

［11］XIA Kai，WEI Chao.Study on real－time navigation data model based on ESRI shapefile ［C］.International Conference on Embedded Software and Systems Symposia，2008：174－178.

［12］GUO Baoqing，TANG Tao，YU Zujun.Train position with map matching based on GPS and track information ［J］.Journal of Electronic Measurement and Instrument，2007，21（1）：49－52 （in Chinese）. ［郭保青，唐濤，余祖俊.基于GPS與軌道信息的地圖匹配列車定位算法 ［J］.電子測量與儀器學報，2007，21 （1）：49－52.］

［13］LIU Yang.The design and implementation of vehicle navigation system GIS based on QTE ［D］.Chongqing：Chongqing University，2009：15－19 （in Chinese）.［劉洋.基于 QTE的GIS車載導航系統的設計與實現 ［D］.重慶：重慶大學，2009：15－19.］

［14］DING Lu，CHEN Jiabin，SONG Chunlei.New map－matching algorithm and real－time parameter correction for land vehicle navigation system ［J］.Chinese Journal of Scientific Instrument，2008，29 （3）：658－661 （in Chinese）. ［丁露，陳家斌，宋春雷.車輛導航系統地圖匹配算法及實時參數修正［J］.儀器儀表學報，2008，29 （3）：658－661.］

［15］LI Xusheng，LI Bing，QU Shangyong，et al.Application and research of the MiniGUI based on the ARM－Linux ［J］.Journal of Xihua University，2008，27 （3）：64－68 （in Chinese）. ［李旭升，李兵，曲尚勇，等.ARM－Linux的 MiniGUI的應用研究［J］.西華大學學報，2008，27 （3）：64－68.］