基于Android的車載導(dǎo)航系統(tǒng)的研究與設(shè)計(jì)

摘要：為了縮短嵌入式車載導(dǎo)航系統(tǒng)開發(fā)進(jìn)程，提高系統(tǒng)維護(hù)和升級(jí)能力，研究了Android平臺(tái)的特點(diǎn)及車載導(dǎo)航系統(tǒng)的性能需求。建立以Android操作系統(tǒng)、GPS技術(shù)為核心的車載導(dǎo)航系統(tǒng)終端軟件。此軟件對(duì)系統(tǒng)平臺(tái)的實(shí)時(shí)路徑獲取、地圖匹配算法校正定位模塊的誤差、地圖的顯示更新以及采用Dijkstra算法實(shí)現(xiàn)最短路徑的導(dǎo)航規(guī)劃都進(jìn)行了詳細(xì)的分析。實(shí)驗(yàn)結(jié)果表明，開發(fā)人員基于Android的通用框架編寫的車載系統(tǒng)的應(yīng)用軟件，便于在不同平臺(tái)間移植和升級(jí)。
關(guān)鍵詞：Android；車載導(dǎo)航；全球定位系統(tǒng)；電子地圖；Dijkstra算法

引言
    近年來(lái)隨著社會(huì)經(jīng)濟(jì)的飛速發(fā)展，公路交通的復(fù)雜性和擁擠度與日俱增，現(xiàn)有的交通運(yùn)輸管理與服務(wù)手段已不能適應(yīng)交通運(yùn)輸?shù)男枨?，這已成為長(zhǎng)期以來(lái)困擾發(fā)展中國(guó)家和發(fā)達(dá)國(guó)家的問(wèn)題。因此，車載導(dǎo)航應(yīng)運(yùn)而生．在一些發(fā)達(dá)國(guó)家，車載導(dǎo)航已成為大眾生活的輔助品。但是在中國(guó)由于技術(shù)、資金以及成本等原因，我國(guó)的車載導(dǎo)航市場(chǎng)還是處于發(fā)展初期。車載導(dǎo)航系統(tǒng)是集中應(yīng)用了自動(dòng)定位技術(shù)、地理信息系統(tǒng)與數(shù)據(jù)庫(kù)技術(shù)、計(jì)算機(jī)技術(shù)、無(wú)線通信技術(shù)的高科技綜合系統(tǒng)。目前國(guó)內(nèi)市場(chǎng)上的車載終端技術(shù)不夠完備，市場(chǎng)化程度低，真正達(dá)到消費(fèi)者要求的并不多見(jiàn)。隨著對(duì)導(dǎo)航系統(tǒng)信息服務(wù)能力要求的進(jìn)一步提高、終端硬件成本的不斷下降以及操作系統(tǒng)的不斷升級(jí)，選擇一款易于開發(fā)、維護(hù)和升級(jí)，并且兼容性強(qiáng)的操作系統(tǒng)來(lái)支撐終端硬件系統(tǒng)的運(yùn)行就顯得異常重要。
    由嵌入式Linux和Java虛擬機(jī)構(gòu)成的Android操作系統(tǒng)，為嵌入式移動(dòng)設(shè)備帶來(lái)全新的開放系統(tǒng)解決方案。本文在眾多的操作系統(tǒng)中選擇Android作為車載導(dǎo)航的系統(tǒng)終端軟件，因?yàn)锳ndroid是開源的操作系統(tǒng)，有利于開發(fā)人員理解平臺(tái)框架，降低移動(dòng)終端設(shè)備的價(jià)格，同時(shí)也便于軟件的開發(fā)、維護(hù)和升級(jí)。

1 Android操作系統(tǒng)介紹
    Google公司于2007年11月發(fā)布的Android操作系統(tǒng)，是一款建立在Linux操作系統(tǒng)2．6版本內(nèi)核之上的手機(jī)操作系統(tǒng)平臺(tái)。Google公司是這樣定義Android操作系統(tǒng)的，它是首個(gè)專門為移動(dòng)終端打造的真正意義上的開源且系統(tǒng)完整的移動(dòng)平臺(tái)，而且不存在不同設(shè)備上的兼容性問(wèn)題。
    Android平臺(tái)由操作系統(tǒng)、中間件、用戶界面和應(yīng)用軟件組成。Linux內(nèi)核層用來(lái)提供系統(tǒng)的底層服務(wù)，位于硬件和其他軟件層之間，采用YAFFS2文件系統(tǒng)。Android運(yùn)行庫(kù)包含一組核心庫(kù)和Dalvik虛擬機(jī)，Android提供豐富的類庫(kù)支持且大部分為開源代碼，如采用嵌入式數(shù)據(jù)庫(kù)SQLite。應(yīng)用框架層為Android開發(fā)人員提供了訪問(wèn)框架應(yīng)用程序接口的全部權(quán)限，采用結(jié)構(gòu)化設(shè)計(jì)簡(jiǎn)化了組件之間的重用。在應(yīng)用程序?qū)?，Android本身附帶了一些核心的應(yīng)用程序，大大簡(jiǎn)化了Android應(yīng)用程序的開發(fā)。
    因此，利用Android操作系統(tǒng)作為車載導(dǎo)航終端的應(yīng)用平臺(tái)，由于操作系統(tǒng)與軟件免費(fèi)，導(dǎo)航終端更便宜；同一平臺(tái)克服格式問(wèn)題，功能更多元化；使用者決定功能，比個(gè)人電腦更人性化、更貼近消費(fèi)者。

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

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

3 車載定位導(dǎo)航系統(tǒng)軟件設(shè)計(jì)
    在車載導(dǎo)航系統(tǒng)軟件設(shè)計(jì)過(guò)程中，利用了Android軟件平臺(tái)的5大功能模塊，分別為Android應(yīng)用程序?qū)印?yīng)用框架層、普通函數(shù)庫(kù)Java程序運(yùn)行環(huán)境和Linux內(nèi)核層。在應(yīng)用程序?qū)永肁ndroid的各種組件API接口開發(fā)了針對(duì)車載導(dǎo)航的GPS、電子地圖的Java應(yīng)用程序，并在內(nèi)核層提供了相應(yīng)串口以及液晶屏等其他的底層驅(qū)動(dòng)。
3．1 GPS定位模塊軟件設(shè)計(jì)
    Android操作系統(tǒng)支持GPS API-LBS，可以通過(guò)集成GPS芯片或外接GPS設(shè)備來(lái)接收衛(wèi)星信號(hào)，通過(guò)GPS全球定位系統(tǒng)中至少3顆衛(wèi)星和原子鐘來(lái)獲取當(dāng)前設(shè)備的坐標(biāo)數(shù)據(jù)。對(duì)于定位功能而言，穩(wěn)定性好是重中之重，而Android實(shí)現(xiàn)了這一點(diǎn)。Android提供了許多定位相關(guān)的類以及相關(guān)的函數(shù)，使得開發(fā)人員可以靈活應(yīng)用。使用位置信息管理類LocationManager進(jìn)行GPS定位，使用Critcria類來(lái)實(shí)現(xiàn)自定義定位功能。當(dāng)然在設(shè)計(jì)的導(dǎo)航系統(tǒng)中，我們希望所實(shí)現(xiàn)的GPS設(shè)備盡可能省電，定位盡可能精確，并且需要獲取運(yùn)動(dòng)物體的速度。因此，設(shè)置的Criteria對(duì)象如下所示：
   
    接著將Criteria的參數(shù)傳遞給LocationManager對(duì)象。然后啟動(dòng)GPS定位功能，LocationManager對(duì)象就開始通過(guò)自身的函數(shù)來(lái)獲取經(jīng)緯度和其他一些數(shù)據(jù)。其獲取數(shù)據(jù)的方法如下所示：
    ①對(duì)于經(jīng)緯度，getLatitude()返回維度數(shù)據(jù)，getLongitude()返回經(jīng)度數(shù)據(jù)；
    ②對(duì)于方向，hasBearing()判斷是否有方向數(shù)據(jù)，而getBearing()則以度為單位返回其值；
    ③對(duì)于海拔高度，hasAltitude()判斷是否有海拔數(shù)據(jù)，而getAltitude下則以m為單位返回海拔數(shù)據(jù)；
    ④對(duì)于速度，hasSpeed()判斷是否有速度值，而getSpeed()則以m／s為單位返回速度值。
    ⑤最后，LocationManager對(duì)象返回的數(shù)據(jù)及時(shí)地更新在電子地圖上，并且隨著物體和時(shí)間位置的變化，開發(fā)者可以利用Location Mana ger，使用定位監(jiān)聽器Location Listener根據(jù)時(shí)間和物體移動(dòng)距離進(jìn)行數(shù)據(jù)更新。
3．2 地圖匹配算法設(shè)計(jì)
    地圖匹配以某個(gè)車輛位置點(diǎn)或某段車行軌跡曲線作為待匹配樣本，以該點(diǎn)或該軌跡曲線附近的所有道路上的位置點(diǎn)或道路曲線作為模板，通過(guò)待匹配樣本或模板間的匹配，選擇相似度最高的匹配樣本或模板作為匹配結(jié)果。最后根據(jù)匹配結(jié)果校正定位模塊的定位誤差。車載導(dǎo)航系統(tǒng)中將車輛定位顯示在電子地圖上時(shí)，應(yīng)該根據(jù)車輛的行駛方向，將車輛定位顯示于某一道路上。但是，由于各種誤差(主要是定位技術(shù)的誤差)，電子地圖上顯示的車輛會(huì)偏離實(shí)際的道路，失去其導(dǎo)航的功能；而地圖匹配這一軟件技術(shù)能校正定位技術(shù)的誤差，使車輛位置準(zhǔn)確地顯示在電子地圖上。[!--empirenews.page--]
    可用來(lái)判斷車輛當(dāng)前可能在哪條路段上行駛的信息主要有3個(gè)：當(dāng)前車輛定位點(diǎn)距候選路段的投影距離、車輛當(dāng)前行駛方向與候選路段方向的夾角以及候選路段與前一匹配路段的幾何拓?fù)潢P(guān)系。一般來(lái)講，投影距離和方向夾角越小的候選路段成為匹配路段的可能性越大，反之亦然。此外，與前一匹配路段相同或拓?fù)湎噙B的候選路段成為匹配路段的可能性大，其余的可能性小。車輛在行駛的過(guò)程中，把GPS原始定位點(diǎn)向各待匹配路段作投影，可計(jì)算GPS原始定位點(diǎn)與待匹配路段之間的最短距離ri(i=1，…，n)；另外車輛行駛方向與各待匹配路段之間的夾角θi(i=1，…，n)也可以得到，進(jìn)而計(jì)算各待匹配路段的匹配值λi(i=1，…，n)。
    地圖匹配算法在進(jìn)行匹配時(shí)的步驟如下：
    ①通過(guò)特征提取把所有的待匹配路段分析、描述，提取出相應(yīng)的匹配因子。
    ②計(jì)算定位點(diǎn)P到各個(gè)待匹配路段的最短距離。距離與夾角示意圖如圖2所示。其中r1、r2為要求的最短距離；a1、a2為所求夾角。根據(jù)匹配規(guī)則，依次計(jì)算定點(diǎn)P到各個(gè)待匹配路段的匹配值。

    ③把匹配值中最小的路段作為最終匹配路段，并把在此路段上距離原始定位點(diǎn)最近的點(diǎn)作為最終匹配點(diǎn)。
3．3 電子地圖顯示模塊設(shè)計(jì)
    利用Android平臺(tái)開發(fā)導(dǎo)航地圖過(guò)程中，主要采用Androld提供的MapView和MapActivity兩個(gè)類實(shí)現(xiàn)。其中MapView是一個(gè)展示地圖的視圖，它可以獲取鍵盤事件來(lái)支持地圖的移動(dòng)和縮放功能，地圖可以以不同的形式來(lái)顯示，如街景模式、衛(wèi)星模式等，通過(guò)setSatellite(boolean)、setTraffic(boolean)和setStreetView(boolean)方法，同時(shí)也支持多層Overlay的使用?？梢栽诘貓D上畫坐標(biāo)、寫地名、畫圖片等。MapView只能通過(guò)MapActivity來(lái)建立，因?yàn)镸apView需要在后臺(tái)使用文件系統(tǒng)和網(wǎng)絡(luò)。所有這些線程需要在Activity的生命周期中被控制。
    如何利用電子地圖功能將GPS模塊定位得到的經(jīng)緯度信息在地圖上顯示出來(lái)呢?地球上的任何一個(gè)地點(diǎn)都可以利用經(jīng)緯度來(lái)表示。在Andro id的類庫(kù)中，Point類代表了一個(gè)地點(diǎn)的經(jīng)緯度，函數(shù)格式為：Pointment(intIatitudeE6，int longitudeE6)。E6是微度，即度數(shù)乘以1000 000。如果要指定地圖地點(diǎn)，須傳遞一個(gè)Point類到地圖中。然后調(diào)用setMapLocationCenter方法將地圖移動(dòng)到合適的位置，最后調(diào)用MapCont roller對(duì)象的animateTo方法將該坐標(biāo)位置設(shè)置為地圖的中心點(diǎn)。在實(shí)際應(yīng)用中，可以使用zoomTo(int)縮放到需要的級(jí)別，同時(shí)利用mapVie  w．toggleSatellite()和mapView．toggle-Traffic()來(lái)獲得衛(wèi)星圖和路況圖。
3．4 最短導(dǎo)航路徑規(guī)劃算法設(shè)計(jì)
    求解最短路徑問(wèn)題的算法中，Dijkstra算法是國(guó)內(nèi)外公認(rèn)的比較成功的算法，該算法通用性強(qiáng)，而且編程實(shí)現(xiàn)簡(jiǎn)單，是目前理論上比較完善、應(yīng)用最廣泛的最短路徑分析算法。Dijkstra算法按路徑長(zhǎng)度的遞增次序，逐條產(chǎn)生最短路徑。
    Dijkstra算法的基本思想是：設(shè)從頂點(diǎn)V0 出發(fā)，搜索從它到其他頂點(diǎn)的最短路徑。把有向圖中的頂點(diǎn)集V分為兩個(gè)集合，已求出最短路徑的頂點(diǎn)集合S，尚未確定最短路徑的頂點(diǎn)集合V-S(定義為T)；按最短路徑長(zhǎng)度遞增的順序逐個(gè)把集合T中的頂點(diǎn)加到集合S中，直到和出發(fā)點(diǎn)V0有路徑相通的所有頂點(diǎn)都包含在集合S中。在整個(gè)過(guò)程中，V0到集合S中各頂點(diǎn)的最短路徑長(zhǎng)度都不大于V0到集合T中的任意頂點(diǎn)的最短路徑長(zhǎng)度。
    設(shè)帶權(quán)有向圖G={V，E}，V={V0，V1，…，Vn-1}，用帶權(quán)的鄰接矩陣Arcs表示圖G；Arcs[i][j]表示弧<Vi，Vj>上的權(quán)值，S表示已求得的從V0 出發(fā)的最短路徑終點(diǎn)的集合；向量D的每個(gè)分量D[i]表示當(dāng)前求得的從始點(diǎn)V0到每個(gè)終點(diǎn)Vi的最短路徑的長(zhǎ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=SU{Vi}。
    ③修改從V0出發(fā)到集合V-S上任意節(jié)點(diǎn)Vk的最短路徑長(zhǎng)度。若D[k]>D[j]+Arcs[j][k]，則修改D[k]為D[k]=D[j]+Arcs[j][k]。
    ④重復(fù)②、③操作n-1次，即可求得從V0到其余各頂點(diǎn)Vi的最短路徑長(zhǎng)度。
    Dijkstra算法的時(shí)間復(fù)雜度是O(n2)。在實(shí)際應(yīng)用中往往只需要搜素從某一源點(diǎn)到某一或某幾個(gè)特定終點(diǎn)的最短路徑，用Dijkstra算法求解，此問(wèn)題與求源點(diǎn)到其余各頂點(diǎn)的最短路徑的時(shí)間復(fù)雜度相同，也為O(n2)。[!--empirenews.page--]

4 性能測(cè)試分析
    基于Android操作系統(tǒng)和ARM微處理器進(jìn)行設(shè)計(jì)的車載導(dǎo)航系統(tǒng)，利用Android通用框架和與設(shè)備無(wú)關(guān)的應(yīng)用程序開發(fā)平臺(tái)，實(shí)現(xiàn)了車載導(dǎo)航的軟件總體架構(gòu)。

    圖3為車輛定位顯示的應(yīng)用程序窗口。截圖所示范圍為廈門軟件園附近，箭頭為汽車所在位置。在實(shí)現(xiàn)的導(dǎo)航設(shè)備中，對(duì)導(dǎo)航設(shè)備的定位精度、電子地圖顯示速度以及在最短路徑導(dǎo)航規(guī)劃所需的時(shí)間進(jìn)行性能測(cè)試。
    (1)定位精度測(cè)試
    現(xiàn)在國(guó)內(nèi)民用餃好的產(chǎn)品的導(dǎo)航定位精度基本控制在5～10 m，不太好的設(shè)備可能達(dá)到幾十米甚至幾百米，本次設(shè)計(jì)的導(dǎo)航終端經(jīng)測(cè)試，定位精度約為7 m。
    (2)電子地圖顯示時(shí)間測(cè)試
    當(dāng)導(dǎo)航設(shè)備接收到GPS數(shù)據(jù)后，如果使用本地電子地圖顯示當(dāng)前位置的時(shí)間為1 s之內(nèi)；如果連網(wǎng)下載電子地圖，顯示當(dāng)前位置的時(shí)間為3 s之內(nèi)。
    (3)最短路徑導(dǎo)航路徑規(guī)劃距離測(cè)試
    通過(guò)最短路徑覘劃后，測(cè)出從廈門到福州的最短路徑是261 km，如果是普通的大路優(yōu)先算法則是292 km；接著測(cè)試從廈門到北京的最短路徑距離為2 106 km，如果是普通的大路優(yōu)先算法，距離則是2312km。

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