近年來隨著社會經濟的飛速發(fā)展，公路交通的復雜性和擁擠度與日俱增，現有的交通運輸管理與服務手段已不能適應交通運輸的需求，這已成為長期以來困擾發(fā)展中國家和發(fā)達國家的問題。因此，車載導航應運而生，在一些發(fā)達國家，車載導航已成為大眾生活的輔助品。但是在中國由于技術、資金以及成本等原因，我國的車載導航市場還是處于發(fā)展初期。車載導航系統(tǒng)是集中應用了自動定位技術、地理信息系統(tǒng)與數據庫技術、計算機技術、無線通信技術的高科技綜合系統(tǒng)。目前國內市場上的車載終端技術不夠完備，市場化程度低，真正達到消費者要求的并不多見。隨著對導航系統(tǒng)信息服務能力要求的進一步提高、終端硬件成本的不斷下降以及操作系統(tǒng)的不斷升級，選擇一款易于開發(fā)、維護和升級，并且兼容性強的操作系統(tǒng)來支撐終端硬件系統(tǒng)的運行就顯得異常重要。

　　由嵌入式Linux和Java虛擬機構成的Android操作系統(tǒng)，為嵌入式移動設備帶來全新的開放系統(tǒng)解決方案。本文在眾多的操作系統(tǒng)中選擇 Android作為車載導航的系統(tǒng)終端軟件，因為Android是開源的操作系統(tǒng)，有利于開發(fā)人員理解平臺框架，降低移動終端設備的價格，同時也便于軟件的開發(fā)、維護和升級。

　　1　Android操作系統(tǒng)介紹

　　Google公司于2007年11月發(fā)布的Android操作系統(tǒng)，是一款建立在Linux操作系統(tǒng)2.6版本內核之上的手機操作系統(tǒng)平臺。 Google公司是這樣定義Android操作系統(tǒng)的，它是首個專門為移動終端打造的真正意義上的開源且系統(tǒng)完整的移動平臺，而且不存在不同設備上的兼容性問題。

　　Android平臺由操作系統(tǒng)、中間件、用戶界面和應用軟件組成。Linux內核層用來提供系統(tǒng)的底層服務，位于硬件和其他軟件層之間，采用 YAFFS2文件系統(tǒng)。Android運行庫包含一組核心庫和Dalvik虛擬機，Android提供豐富的類庫支持且大部分為開源代碼，如采用嵌入式數據庫SQLite。應用框架層為Android開發(fā)人員提供了訪問框架應用程序接口的全部權限，采用結構化設計簡化了組件之間的重用。在應用程序層，Android本身附帶了一些核心的應用程序，大大簡化了Android應用程序的開發(fā)。

　　因此，利用Android操作系統(tǒng)作為車載導航終端的應用平臺，由于操作系統(tǒng)與軟件免費，導航終端更便宜；同一平臺克服格式問題，功能更多元化；使用者決定功能，比個人電腦更人性化、更貼近消費者。

　　2　系統(tǒng)框架設計

　　本系統(tǒng)是一款以三星公司的S3C6410處理器為核心的嵌入式開發(fā)板，先開發(fā)Bootloader引導程序，接著在此基礎上移植Linux內核，然后制作Android文件系統(tǒng)；在移植好Android操作系統(tǒng)后，進行車載導航功能的開發(fā)，任務集中在通過GPS實時獲取路徑，使用地圖匹配算法校正定位模塊的定位誤差，采用最短路徑導航規(guī)劃算法進行導航，通過語音提示實現路徑的引導，并且通過電子地圖配合Android系統(tǒng)軟件的API接口，同時它還具有不斷升級的地圖庫，并能按照用戶的需求進行各種信息查詢，真正實現一個體積小、耗電少、成本低并且人機界面友好的嵌入式操作系統(tǒng)平臺。系統(tǒng)框架圖如圖1所示。

　　圖1　系統(tǒng)框架圖

　　利用Android操作系統(tǒng)在ARM硬件平臺上實現車載導航終端各功能模塊的整合，配合相應的串口驅動、液晶屏驅動等完成指定的功能，如對接收到的數據進行處理，計算所在位置的經度、緯度、海拔、速度和時間等，并且采用地圖匹配算法進行定位誤差校正，自主導航路徑規(guī)劃采用Dijkstra算法，實現最短路徑導航。GPS系統(tǒng)具有全天候、全球覆蓋、三維定速、定時、高精度、快速、省時、高效率、應用廣泛、多功能等特點，因此可廣泛應用于陸地、海洋以及航空航天等。電子地圖的使用，直觀地將豐富的城市地圖、全國的公路網圖、加油站、便利商店、政府機關、餐館、醫(yī)院、停車場等信息同步地在LCD液晶顯示屏上顯示出來，方便中高端使用人員進行查詢參考。

　　3　車載定位導航系統(tǒng)軟件設計

　　在車載導航系統(tǒng)軟件設計過程中，利用了Android軟件平臺的5大功能模塊，分別為Android應用程序層、應用框架層、普通函數庫、 Java程序運行環(huán)境和Linux內核層。在應用程序層利用Android的各種組件API接口開發(fā)了針對車載導航的GPS、電子地圖的Java應用程序，并在內核層提供了相應串口以及液晶屏等其他的底層驅動。

　　3.1　GPS定位模塊軟件設計

　　Android操作系統(tǒng)支持GPS APILBS，可以通過集成GPS芯片或外接GPS設備來接收衛(wèi)星信號，通過GPS全球定位系統(tǒng)中至少3顆衛(wèi)星和原子鐘來獲取當前設備的坐標數據。對于定位功能而言，穩(wěn)定性好是重中之重，而Android實現了這一點。Android提供了許多定位相關的類以及相關的函數，使得開發(fā)人員可以靈活應用。使用位置信息管理類LocationManager進行GPS定位，使用Criteria類來實現自定義定位功能。當然在設計的導航系統(tǒng)中，我們希望所實現的 GPS設備盡可能省電，定位盡可能精確，并且需要獲取運動物體的速度。因此，設置的Criteria對象如下所示：

　　Criteria mCriteria=new Criteria（）;

　　mCriteria.setAccuracy（Criteria.ACCURACY_FINE）; /*經緯度是否精確提供*/

　　mCriteria.setAltitudeRequired（false）; /*是否提供高度信息*/

　　mCriteria.setBearingRequired（false）; /*是否提供航向信息*/

　　mCriteria.setCostAllowed（true）; /*費用*/

　　mCriteria.setPowerRequirement（Criteria.POWER_LOW）; /* 設置低電量參數*/

　　mCriteria.setSpeedRequired（true）; /* 是否獲取當前物體的速度*/

　　接著將Criteria的參數傳遞給LocationManager對象。然后啟動GPS定位功能，LocationManager對象就開始通過自身的函數來獲取經緯度和其他一些數據。其獲取數據的方法如下所示：

　　① 對于經緯度，getLatitude（）返回維度數據，getLongitude（）返回經度數據；

　　② 對于方向，hasBearing（）判斷是否有方向數據，而getBearing（）則以度為單位返回其值；

　　③ 對于海拔高度，hasAltitude（）判斷是否有海拔數據，而getAltitude下則以m為單位返回海拔數據；

　　④ 對于速度，hasSpeed（）判斷是否有速度值，而getSpeed（）則以m/s為單位返回速度值。

　　⑤ 最后，LocationManager對象返回的數據及時地更新在電子地圖上，并且隨著物體和時間位置的變化，開發(fā)者可以利用LocationManager，使用定位監(jiān)聽器LocationListener根據時間和物體移動距離進行數據更新。

　　3.2　地圖匹配算法設計

　　地圖匹配以某個車輛位置點或某段車行軌跡曲線作為待匹配樣本，以該點或該軌跡曲線附近的所有道路上的位置點或道路曲線作為模板，通過待匹配樣本或模板間的匹配，選擇相似度最高的匹配樣本或模板作為匹配結果。最后根據匹配結果校正定位模塊的定位誤差。車載導航系統(tǒng)中將車輛定位顯示在電子地圖上時，應該根據車輛的行駛方向，將車輛定位顯示于某一道路上。但是，由于各種誤差（主要是定位技術的誤差），電子地圖上顯示的車輛會偏離實際的道路，失去其導航的功能；而地圖匹配這一軟件技術能校正定位技術的誤差，使車輛位置準確地顯示在電子地圖上。

　　可用來判斷車輛當前可能在哪條路段上行駛的信息主要有3個：當前車輛定位點距候選路段的投影距離、車輛當前行駛方向與候選路段方向的夾角以及候選路段與前一匹配路段的幾何拓撲關系。一般來講，投影距離和方向夾角越小的候選路段成為匹配路段的可能性越大，反之亦然。此外，與前一匹配路段相同或拓撲相連的候選路段成為匹配路段的可能性大，其余的可能性小。車輛在行駛的過程中，把GPS原始定位點向各待匹配路段作投影，可計算GPS原始定位點與待匹配路段之間的最短距離ri（i=1，…，n）；另外車輛行駛方向與各待匹配路段之間的夾角θi（i=1，…，n）也可以得到，進而計算各待匹配路段的匹配值 λi（i=1，…，n）。

　　地圖匹配算法在進行匹配時的步驟如下：

　　① 通過特征提取把所有的待匹配路段分析、描述，提取出相應的匹配因子。

　　圖2　距離與夾角示意圖

　　② 計算定位點P到各個待匹配路段的最短距離。距離與夾角示意圖如圖2所示。其中r1、r2為要求的最短距離；α1、α2為所求夾角。根據匹配規(guī)則，依次計算定點P到各個待匹配路段的匹配值。

　　③ 把匹配值中最小的路段作為最終匹配路段，并把在此路段上距離原始定位點最近的點作為最終匹配點。

　　3.3　電子地圖顯示模塊設計

　　利用Android平臺開發(fā)導航地圖過程中，主要采用Android提供的MapView和MapActivity兩個類實現。其中 MapView是一個展示地圖的視圖，它可以獲取鍵盤事件來支持地圖的移動和縮放功能，地圖可以以不同的形式來顯示，如街景模式、衛(wèi)星模式等，通過 setSatellite（boolean） 、setTraffic（boolean）和setStreetView（boolean） 方法，同時也支持多層Overlay的使用。可以在地圖上畫坐標、寫地名、畫圖片等。

　　MapView只能通過MapActivity來建立，因為MapView需要在后臺使用文件系統(tǒng)和網絡。所有這些線程需要在Activity的生命周期中被控制。

　　如何利用電子地圖功能將GPS模塊定位得到的經緯度信息在地圖上顯示出來呢？地球上的任何一個地點都可以利用經緯度來表示。在Android的類庫中，Point類代表了一個地點的經緯度，函數格式為：Pointment（int latitudeE6，int longitudeE6）。E6是微度，即度數乘以1000 000。如果要指定地圖地點，須傳遞一個Point類到地圖中。然后調用setMapLocationCenter方法將地圖移動到合適的位置，最后調用 MapController對象的animateTo方法將該坐標位置設置為地圖的中心點。在實際應用中，可以使用zoomTo（int）縮放到需要的級別，同時利用mapView.toggleSatellite（）和mapView.toggleTraffic（）來獲得衛(wèi)星圖和路況圖。

　　3.4　最短導航路徑規(guī)劃算法設計

　　求解最短路徑問題的算法中，Dijkstra算法是國內外公認的比較成功的算法，該算法通用性強，而且編程實現簡單，是目前理論上比較完善、應用最廣泛的最短路徑分析算法。Dijkstra算法按路徑長度的遞增次序，逐條產生最短路徑。

　　Dijkstra算法的基本思想是：設從頂點V0出發(fā)，搜索從它到其他頂點的最短路徑。把有向圖中的頂點集V分為兩個集合，已求出最短路徑的頂點集合S，尚未確定最短路徑的頂點集合V-S（定義為T）；按最短路徑長度遞增的順序逐個把集合T中的頂點加到集合S中，直到和出發(fā)點V0有路徑相通的所有頂點都包含在集合S中。在整個過程中，V0到集合S中各頂點的最短路徑長度都不大于V0到集合T中的任意頂點的最短路徑長度。

　　設帶權有向圖G={V，E}，V={V0，V1，…，Vn-1}，用帶權的鄰接矩陣Arcs表示圖G；Arcs［i］［j］表示弧《 Vi，Vj》上的權值，S表示已求得的從V0出發(fā)的最短路徑終點的集合；向量D的每個分量D［i］表示當前求得的從始點V0到每個終點Vi的最短路徑的長度，算法描述如下：

　　① 初始化集合S、向量D。S={V0}，D［i］=Arcs［0］［i］（i=0，1，…，n-1）。

　　② 選擇Vj，使得D［j］=min{D［i］|Vi∈V-S}，S=S∪{Vi}。

　　③ 修改從V0出發(fā)到集合V-S上任意節(jié)點Vk的最短路徑長度。若D［k］》D［j］+Arcs［j］［k］，則修改D［k］為D［k］=D［j］+Arcs［j］［k］。

　　④ 重復②、③操作n-1次，即可求得從V0到其余各頂點Vi的最短路徑長度。

　　Dijkstra算法的時間復雜度是O（n2）。

　　在實際應用中往往只需要搜素從某一源點到某一或某幾個特定終點的最短路徑，用Dijkstra算法求解，此問題與求源點到其余各頂點的最短路徑的時間復雜度相同，也為O（n2）。

　　4　性能測試分析

　　基于Android操作系統(tǒng)和ARM微處理器進行設計的車載導航系統(tǒng)，利用Android通用框架和與設備無關的應用程序開發(fā)平臺，實現了車載導航的軟件總體架構。圖3為車輛定位顯示的應用程序窗口。截圖所示范圍為廈門軟件園附近，箭頭為汽車所在位置。在實現的導航設備中，對導航設備的定位精度、電子地圖顯示速度以及在最短路徑導航規(guī)劃所需的時間進行性能測試。

　　圖3　車輛定位顯示的應用程序窗口

　　（1） 定位精度測試

　　現在國內民用較好的產品的導航定位精度基本控制在5~10 m，不太好的設備可能達到幾十米甚至幾百米，本次設計的導航終端經測試，定位精度約為7 m。

　　（2） 電子地圖顯示時間測試

　　當導航設備接收到GPS數據后，如果使用本地電子地圖顯示當前位置的時間為1 s之內；如果連網下載電子地圖，顯示當前位置的時間為3 s之內。

　　（3） 最短路徑導航路徑規(guī)劃距離測試

　　通過最短路徑規(guī)劃后，測出從廈門到福州的最短路徑是261 km，如果是普通的大路優(yōu)先算法則是292 km；接著測試從廈門到北京的最短路徑距離為2 106 km，如果是普通的大路優(yōu)先算法，距離則是2 312 km。

　　結語

　　利用車載導航系統(tǒng)的設計方案，并結合Android系統(tǒng)特性設計的嵌入式系統(tǒng)可嵌入到手機、PDA、POS機、機頂盒、數字電視、家庭媒體播放器等其他終端設備，具有很好的可移植性和可擴展性。在移動導航終端的應用中，以GPS導航為代表的綜合信息管理平臺將是未來移動終端通信及導航產品的發(fā)展趨勢，而Android系統(tǒng)在導航終端的應用將會逐步成熟和發(fā)展，產品價格也將最終接近大眾消費水平，屆時導航產品將成為人們休閑、娛樂、旅游探險的必備工具。