基于A(yíng)ndroid的車(chē)載導航系統的研究與設計

　　引言

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

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

　　1　Android操作系統介紹

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

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

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

　　2　系統框架設計

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

　　圖1　系統框架圖

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

　　3　車(chē)載定位導航系統軟件設計

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

　　3.1　GPS定位模塊軟件設計

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

　　Criteria mCriteria=new Criteria();

　　mCriteria.setAccuracy(Criteria.ACCURACY_FINE); /*經(jīng)緯度是否精確提供*/

　　mCriteria.setAltitudeRequired(false); /*是否提供高度信息*/

　　mCriteria.setBearingRequired(false); /*是否提供航向信息*/

　　mCriteria.setCostAllowed(true); /*費用*/

　　mCriteria.setPowerRequirement(Criteria.POWER_LOW); /* 設置低電量參數*/

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

　　接著(zhù)將Criteria的參數傳遞給LocationManager對象。然后啟動(dòng)GPS定位功能，LocationManager對象就開(kāi)始通過(guò)自身的函數來(lái)獲取經(jīng)緯度和其他一些數據。其獲取數據的方法如下所示：

　?、?對于經(jīng)緯度，getLatitude()返回維度數據，getLongitude()返回經(jīng)度數據;

　?、?對于方向，hasBearing()判斷是否有方向數據，而getBearing()則以度為單位返回其值;

　?、?對于海拔高度，hasAltitude()判斷是否有海拔數據，而getAltitude下則以m為單位返回海拔數據;

　?、?對于速度，hasSpeed()判斷是否有速度值，而getSpeed()則以m/s為單位返回速度值。

　?、?最后，LocationManager對象返回的數據及時(shí)地更新在電子地圖上，并且隨著(zhù)物體和時(shí)間位置的變化，開(kāi)發(fā)者可以利用LocationManager，使用定位監聽(tīng)器LocationListener根據時(shí)間和物體移動(dòng)距離進(jìn)行數據更新。

　　3.2　地圖匹配算法設計

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

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

　　地圖匹配算法在進(jìn)行匹配時(shí)的步驟如下：

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

　　圖2　距離與夾角示意圖

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

　?、?把匹配值中最小的路段作為最終匹配路段，并把在此路段上距離原始定位點(diǎn)最近的點(diǎn)作為最終匹配點(diǎn)。

　　3.3　電子地圖顯示模塊設計

　　利用Android平臺開(kāi)發(fā)導航地圖過(guò)程中，主要采用Android提供的MapView和MapActivity兩個(gè)類(lèi)實(shí)現。其中MapView是一個(gè)展示地圖的視圖，它可以獲取鍵盤(pán)事件來(lái)支持地圖的移動(dòng)和縮放功能，地圖可以以不同的形式來(lái)顯示，如街景模式、衛星模式等，通過(guò)setSatellite(boolean) 、setTraffic(boolean)和setStreetView(boolean) 方法，同時(shí)也支持多層Overlay的使用?？梢栽诘貓D上畫(huà)坐標、寫(xiě)地名、畫(huà)圖片等。

　　MapView只能通過(guò)MapActivity來(lái)建立，因為MapView需要在后臺使用文件系統和網(wǎng)絡(luò )。所有這些線(xiàn)程需要在A(yíng)ctivity的生命周期中被控制。

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

　　3.4　最短導航路徑規劃算法設計

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

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

　　設帶權有向圖G={V，E}，V={V0，V1，…，Vn-1},用帶權的鄰接矩陣Arcs表示圖G;Arcs[i][j]表示弧上的權值，S表示已求得的從V0出發(fā)的最短路徑終點(diǎn)的集合;向量D的每個(gè)分量D[i]表示當前求得的從始點(diǎn)V0到每個(gè)終點(diǎn)Vi的最短路徑的長(cháng)度，算法描述如下：

　?、?初始化集合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上任意節點(diǎn)Vk的最短路徑長(cháng)度。若D[k]>D[j]+Arcs[j][k]，則修改D[k]為D[k]=D[j]+Arcs[j][k]。

　?、?重復②、③操作n-1次，即可求得從V0到其余各頂點(diǎn)Vi的最短路徑長(cháng)度。

　　Dijkstra算法的時(shí)間復雜度是O(n2)。

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

　　4　性能測試分析

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

　　圖3　車(chē)輛定位顯示的應用程序窗口

　　(1) 定位精度測試

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

　　(2) 電子地圖顯示時(shí)間測試

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

　　(3) 最短路徑導航路徑規劃距離測試

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

　　結語(yǔ)

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