基于短信的智能導行系統模型及設計摘要隨著社會科技的發展，人們的出行條件得到了極大的發展，隨處可見小汽車在柏油路上呼嘯而去。但隨著車輛的增多也帶來了許多的問題。這個時候車載導航作為一個輔助駕駛技術發揮著重要的作用，于此同時隨著互聯網與物聯網的快速發展，汽車導航系統必將發揮出更大的作用。因此我們有必要去了解其主要構造及其原理。正所謂數據為王，車載導航系統也有著許多的數據需要處理，運用好的數據處理技術能顯著提高車載導航的數據處理效率，提升性能。本論文先后論述了國內外先進的數據處理技術以及車載導航的系統概述以及車載導航路徑規劃模塊及相應的算法。本論文通過利用卡爾曼濾波技術對構建的小車位置信息進行處理并對比分析，然后利用遺傳算法先后完成一個多路徑的路徑選擇優化以及單一路徑的確立。通過仿真我們可以得出，經卡爾曼濾波處理后小車位置更加準確，且狀態波動小，較為穩定，能夠顯著的提高定位精度，在導航數據處理方面發揮著重要作用。遺傳算法具有隨機性以及一定的方向性，它可以通過多次迭代使得種群向目標函數逼近，從而獲得最優解，在最優路徑規劃方面發揮則重要作用。關鍵詞：車載導航系統；數據處理技術；卡爾曼濾波；路徑規劃目錄TOC\o"1-3"\h\u8078第一章緒論 緒論從出生落地后開始爬行到慢慢直立行走，每個人都在向著目標點移動前行，即使很遠很累也沒有人會放棄，畢竟終點有我們想得到的，到達一個又一個終點，一個又一個終點連接起來就會一直通向遠方。但畢竟有時候真的路途遙遠，對于人這個“懶得”的生物來說總會想到辦法解決，從馬車到現在的汽車、輪船、飛機、火車以及高鐵等都是因為“懶”而出現的。但有了這些工具可不是就一勞永逸了，正確利用這些工具也是一件長遠沒有終點的長征。有了馬車，你還需要訓練拉車的馬朝著你的目標正確前行,有了汽車你也還需要正確的駕駛汽車在固定路線行駛。但無論是人身體力行的不行亦或者是借助交通工具在出行，都不能忽視一件重要的事情，那就是出發點與目的地之間的路線。古代人出遠門總會詢問外出過的老人，詢問路線記住標志性建筑和地理位置幫助識別路線，行在路中感覺路線不確定時也會詢問當地人以獲得正確路線；在借助馬通行后，有一個成語叫做老馬識途，因為馬兒經常走那段路對其記憶清晰，故能清楚的知道路線，除了老馬識途外還有投石問路，這就是沒有辦法的時候的一種尋求內心安穩的一種方法。后來聰明的人們發明了地圖，根據地理探測及經驗把已知的地理位置信息全部濃縮在一張圖上，明確的幫我們畫下來正確的路線，但紙質地圖保持、識別等方面也存在一定的缺陷。隨著社會的發展，我們引來了互聯網、大數據時代，先后發明了電子地圖，在衛星發射成功后，借助衛星和電子地圖人們發明了導航系統，幫助我們查詢、識別路線。各種交通工具的出現以及互聯網時代的不斷發展，讓人們已經不再局限于一地工作、游玩了。總會去遠方出差或者游玩。這個時候導航就發揮其強大的功能了。而作為現代交通工具的汽車為我們的出行帶來了便利，作為其配置之一的車載導航也發揮著巨大的作用。隨著社會科技的發展，車輛產業也是蓬勃發展，往些年可能得具備雄厚的資本條件以及社會地位才能擁有一輛屬于自己的車，但現在社會只要用于一定的經濟條件即可用于自己的車，這個標準明顯變低了，擁有一輛車已經并不是那么困難了。汽車為人們帶來了許多的便利，縮短了出行時間，加快了生活節奏提高了生活效率。但車輛數量的劇增也帶來了許多的問題，如交通堵塞、安全事故頻發等問題，對人們的正常生活造成了極大的影響。這個時候一個能幫助人們快速、安全到達目的地的輔助駕駛技術就非常必要了，而車載導航系統正好具備這一功能。現在的車載導航能夠在行駛中提供很多導航信息給駕駛員，現在它在民用和軍事領域方面中使用的都比較多，比如汽車導航，機器人導航還有無人駕駛之類。當然現在物聯網的飛速發展，汽車導航在以后的生活里將也會越來越重要。車輛導航一般是利用衛星導航和自身配備的傳感器完成任務。衛星導航常常用在車輛導航上。它有很高的定位精度，產生的誤差也不會因為時間造成累積，但是它會容易被干擾還有屏蔽，這些會導致它不能完全進行自主導航。SINS是自主導航設備，它能隨時輸出載體的各種參數。它一般會被用來當車輛定位和導航。但它的缺點就是因為時間的增加，產生的誤差也會提高。里程計是一種輔助的傳感器，它能測量車輛行駛速度還有距離，而且不會被電磁信號干擾，它有強自主性，成本也不高，但是它沒有辦法提供姿態的相關信息，要和其它傳感器一起使用。所以，我們把上面說的三種方法的缺點進行改善，就能得到高精度的導航參數，這樣可以加強車輛導航效果幫助駕駛人更好的行駛，優缺點互補結合后的導航，具有較高的應用價值和長期的發展前景。這是一個數據為王的時代，車載導航完成任務離不開數據的處理，因此了解國內外先進的數據處理技術，完成數據的處理至關重要。通過先進的數據處理完成車輛導航任務可以提高導航效率，助力導航事業的發展。

國內外現狀對于車載導航是借助衛星導航系統實現的，因此了解目前國內外的衛星導航系統是非常重要的。此外導航的數據處理是導航完成的一個核心。因此本章就目前國內外的衛星導航系統以及數據處理技術就行一個介紹以及原理闡述。衛星導航系統簡介當前看來國內外的衛星導航系統可以分為四個大類，一是俄羅斯的格洛納斯系統，二是歐盟的伽利略系統，三是我國的北斗系統，四是美國的全球定位導航系統。美國研制的GPS系統是當下全球適用范圍最廣的一個衛星導航系統了嗎，起初是由美國五角大樓設計和開發的，如果發生了戰爭，美國可以在特定區域關閉系統相關信息服務。GPS是第一個任何人都能用的成熟的全球定位和導航衛星系統。GPS在定位和導航上的作用比較多，像是車輛、船舶這些物體。再比如說：船舶海上航行和進港引水；飛機路線指導及機場降落；個人通訊終端（手機，PDA還有電子地圖等）；自動駕駛汽車導航；除了這些，還有各種等級的大地測量，控制測量等。該系統有三個部分，即空間部分、地面部分以及使用終端用戶部分。——空間部分:21顆主要衛星與3顆備用衛星組成整個導航定位網絡系統的，并且大致分布在6個運行軌道上，在赤道平面上是呈現55度角的等距排列，它的高度在20202km。每一個軌道上存在4顆衛星，每顆衛星圍繞地球旋轉的周期大約是12小時。衛星接收地面站發送的衛星時鐘校正設置，電離層糾正設置還有一些其他的導航消息，這樣才能向用戶反饋準確的PPS和SPS。導航衛星會向用戶的終端設備進行數據的傳輸，里面包含著實時導航數據、測距碼以及實時時刻等。——地面部分：地面部分包括1個主控制站、1個備份主控站、4注入站、7個AFSCN遠程跟蹤站、6個美空軍監測站、10個美NGA監測站（2017年數據）。主控制站：負責系統的整體控制，提供時間基準（配備原子鐘），對監測傳過來的數據統籌運算處理，然后再針對各個運行衛星的星歷表進行衛星鐘的偏差校正以及電離層參數等的調教，再將更新數據通過傳輸機構發送到注入站點，再發給每個衛星。監測站：配置幾個環境數據傳感器、一臺原子鐘、用戶的接收機還有一個信息處理器。它要做的就是記錄各個衛星時間精度，每隔1.5秒就要測量可見所有衛星的距離，收集當地有關環境天氣的數據等。注入站:在主控站和衛星之間提供一個接口，并將導航信息，星歷這些數據用1754~1854MH的頻段注入到每個衛星里。——用戶部分：接收信號顯示信息。圖2.1GPS導航示意圖該系統的原理其實就是通過探測衛星和地面用戶終端設備之間的距離差，然后再通過整個衛星網絡進行校正與核對，為了實現這個基本方式，就必須借助星歷表來進行時間的運算，從而得知明確衛星的具體位置，然后再將衛星的位置信息與時間數據進行匯總計算，從而算出PR，也就是用戶的終端設備距離衛星的實際距離，精確到米這個單位。導航定位系統在正常運轉的時候，衛星會對對面的接收站與用戶終端設備進行隨機碼的電信號傳輸。該定位系統用的偽碼分為兩種，一種是民用的C/A碼，另一種是軍方使用的用于保密性質的P(Y)碼。C/A碼為1.023MHz，周期僅僅只有一毫秒，碼間距是1微秒，也就是說電碼之間的距離只有三百米。Y碼源于P碼，能夠充分實現保密的需要，定位系統的電碼內容通常囊括時鐘的校正以及電離層偏差等一系列數據信息。其通過衛星信號進行調制，在50b/s基礎頻率上進行數據傳輸，整個電碼內容也有好幾部分，比如有三個數據塊、遙測碼和轉換碼，這個當中最為關鍵的就是星歷數據了，因為用戶的終端設備只需要通過接受衛星與自己的時刻數據就可以計算出自己與該衛星之間的距離，然后結合星歷數據推導出自己所處的位置，此外，還需要借助WGS-84大地坐標系。于是乎，GPS導航系統主要作用是能夠發射導航與定位數據，除此之外，由于用戶終端接收裝置的限制，時鐘無法與衛星時鐘做到完全一致完全同步，所以說，在大地坐標系的三維坐標x、y、z之外，要再引一個，然后使用四個方程式進行四個未知數的計算，所以說，如果要確定某個接收終端的位置，就必須要接收得到來自四個不同的衛星的傳輸電碼。GPS有下面這些特點：（1）全天;（2）全球覆蓋;（3）三維立體定位;（4）高效率及時定位；（5）具備多功能特點；（6）抗干擾性能好、保密性強。估計很少有人會知道一個歷史，就是俄羅斯的格洛納斯系統的研制遠遠早于美國的GPS定位系統，所以這也是后來美蘇冷戰時期美國政府加緊建設自己的衛星定位系統的原因之一。后來由于前蘇聯的解體，格洛納斯定位系統的運轉還有發展都被影響，于是發展速度就比GPS慢了許多，普及度也比不上GPS。但是到了新世紀，俄羅斯的格洛納斯系統也在慢慢恢復原來的“統治地位”，其作用也不斷地顯現。格洛納斯衛星導航系統的研制主要得益于軍方的投入，除了具備與美國的導航系統一樣的導航與定位之外，還能夠為海軍的艦艇、空軍的飛機以及導彈部隊的導彈進行精確制導，為全軍部隊的軍事行動和武器之間的協調提供機制化的便利條件，同樣的，通過衛星來提供定位在各個國家經濟領域的應用越來越多，像是大地和海洋測繪、石油與地質勘探、地震預測以及社會管理等多方面。格洛納斯的出現也威脅到了美國GPS的統治地位，消除了用戶使用的擔憂，為用戶提供保障。格洛納斯使用了與GPS系統類似的運行衛星數量，它還比美國的全球定位系統多了一顆用于數據備份的衛星，我們隨時都能夠觀測到任何一個軌道上的四顆衛星，其無線電信號也同樣發射的是兩種類別的偽碼，軍用和民用服務其都能提供。它是全球首個以民用為基礎的全球衛星導航定位系統。2008年開始運行以后，全世界用戶都能用更多標準的接收器從衛星里得到更多的信號，在很大程度上提升了定位的精確度，這是直接方便于用戶群體的。多種衛星制導系統給我們帶來了使用的便利與更加穩定精確的定位數據，它們相互制約互相競爭，也在相互借鑒與提升，能夠為國際定位導航產業提供堅實的技術保障。以“伽利略”命名的衛星導航系統是整個歐洲第一個衛星導航系統，它以高精度與穩定性著稱，并且真正實現了民用而非軍方化管理，能夠執行遍布全球的導航指令，實現全球化的定位功能。此外，該系統還能夠與其它不同的系統配套使用，未來很多用戶能夠充分實現多終端接收器的多元化定位服務，通過多種衛星定位系統來進行導航。伽利略衛星定位系統與現有衛星定位系統最大的不同就是它可以實現實時高精度數據傳輸，在任何極端條件與環境下都能夠保證定位數據的可靠與穩定，能夠及時地向用戶反饋定位信息或者說錯誤的定位信息，其自我糾錯能力十分強悍。伽利略定位系統與其它系統相比，最大的優點就是高精確性，其定位范圍可以精確到一米之內，其先進性與可靠性一目了然。該系統可以分為五個板塊，即衛星板塊、全球設施板塊、地區設施板塊、終端用戶板塊以及服務中心板塊。空間板塊由30顆近地衛星組建而成，并且均勻分布在三個運行軌道上，且軌道高度達到兩萬千米級別，與赤道的傾斜角為56度，最為重要的是，在每個軌道上都有一個備用衛星，一旦出現某個工作衛星失效或者出現故障，備用衛星就會緊急替補上去，保證整個系統的運作效能不變，而出現問題的衛星則會被推升到高于原軌道三百千米的新軌道上運行，所以，如此的空間布局足以為全球提供穩定且廣泛的定位導航服務了。地面部分則是以監控系統、測控系統、時間同步系統以及系統管理中心四大部分構建而成，其中兩個控制中心都在歐洲，二十九個之多的傳感器站點分布于全世界各個地區，同樣的，5個S波段上行站點與10個C波段上行站點能夠為衛星和地面的控制中心提供數據傳輸的保障功能，通過通信網絡建立兩者之間的連接，此外，伽利略系統的地面部分還可以與薩爾薩特系統一起為救援搜救提供定位服務，能夠額外提供商業增值。數據處理技術理論數據濾波是當下最先進得一種數據處理方法，主要用于去除噪聲以及實際數據的恢復處理。在明確測量方差的前提下，卡爾曼濾波能夠憑借測量數據來評估動態系統的實況。由于卡爾曼濾波能夠方便計算機的編程工作，對于實際采集的數據可實時處理和更新。卡爾曼濾波的出現是現代濾波理論建立的標志之一，其是由美國科學家R.E.Kalman在上個世紀六十年代所設想的一種呈線性特征的最小方差離散濾波器，在之后的科技發展與進步過程中，該科學家與R.S.Bucy立足于連續系統的理論，提出了卡爾曼濾波的設想，最終形成最后的理論，所以完整的卡爾曼濾波理論也正式誕生了，但是其在線性隨機系統中也會有一定的局限性特征。上世紀六十年代末，Sunahara、Bucy等總結出了卡爾曼濾波擴展理論，拓展了原理論的應用范圍，使得該理論可以在非線性系統中也能有很好的表現，否則就會導致誤差與離散現象的出現。到了新世紀，基于卡爾曼擴展理論的基礎上，Uhlmann和Julier重新總結得出了無跡卡爾曼濾波理論，即UKF，這個濾波算法摒棄了雅可比矩陣，拋開了系統的限制條件，大大提升了原理論的精確程度。（1）標準卡爾曼濾波(KF)標準卡爾曼濾波是一種線性最小方差的算法，能夠利用實時數據進行動態的數據處理，是當下最先進最廣泛的一種計算方法。現狀假定具有有一系統，如下：上式中：是時刻的n維狀態向量；是k時刻的m維觀測向量；時刻到k時刻的n×n維狀態轉移矩陣；為k時刻的m×n維觀測矩陣；為k-1時刻加在系統上的r維隨機干擾向量；為k時刻的m維觀測噪聲。按卡爾曼濾波要求，假定{}和{}是互不相關的零均值的正態隨機序列，并且有：上式中，是系統噪聲，觀測噪聲的方差矩陣，在卡爾曼濾波中要求為已知值的非負定陣，要求為已知值的正定陣，且初始狀態的一階、二階統計特征取為和，卡爾曼濾波要求和是已經知道的常量，且它們是互不相關的。根據卡爾曼濾波方程得：（2）擴展卡爾曼濾波（EKF）通常情況下的擴展卡爾曼濾波只適用于非線性系統，它的狀態預估與實際測量是沒有任何辦法憑借前一步狀態序列的線性表達式來表達，這個時候就不能夠一味地使用過去常用的卡爾曼濾波技術進行預估了，就必須要采用擴展卡爾曼濾波理論來解決。首先定義離散線性模型下的系統狀態方程以及觀測方程為：式中：為k時刻的動力系統的狀態向量；為已知的系統的輸入值；是系統的觀測值；為系統的過程噪聲；為系統的狀態轉移矩陣；為已知輸入的位置矩陣；為已知輸入作用于觀測值的位置矩陣；為觀測矩陣；為系統的觀測噪聲。同時和應該滿足高斯白噪聲的條件。非線性系統狀態方程以及觀測方程一般表達為：式中：和則是系統狀態方程和觀測方程的非線性表達，因此在前序列點處，進行一階泰勒展開，可以得到：式中的和是二階以上的泰勒級數，可以略去。我們定義狀態轉移函數和感測矩陣的雅可比矩陣（一階偏導數組成的矩陣）如下：于是可以改寫為：式中，當已知的時候，和都是確定的常數序列，而和矩陣中的值也是唯一確定的，因此此方程的因變量和自變量就建立了線性關系，則式（1-9）和（1-10）就近似為了和式（1-7）以及（1-8）相同形式的線性關系式了，此時再用標準的卡爾曼濾波方法對其進行估算。人工神經網絡是根據人體大腦信息處理結構進行簡化、運算以及建模而得出的一種數據處理的方式方法。其通過自動非線性系統進行層次順序的互聯，其中的物質中介就是大規模的神經元物質。根據信息的不同特性，通過改變各個神經元之間的連接方式來構成新的結構，最終達到處理的效果。按不同的方式可以將人工神經網絡分為多個類型。如下表所示：表2.1人工神經網絡的分類分類依據分類時間特性連續型和離散型工作方式確定性和隨機性模型結構前饋型網絡和反饋型網絡學習環境監督學習與非監督的學習上個世紀八十年代中期，Rumelharthe和MeClelland等就已經提出了一種反向傳播網絡的構想，其屬于前饋型神經網絡系統，整個學習過程是通過兩個部分組成的，一是正向傳遞，二是誤差的反向傳遞。它的原理是在一次計算過程在中通過誤差的反向傳遞完成處理，最后在計算每一層的誤差的基礎上進行數據的最后模擬，得出處理結論。在第二部分中，憑借著某種算法，能夠使得誤差值不斷縮小，其原理就是校正網絡參數進行誤差的更新與改進，直到誤差的上升趨勢保持穩定，此時此刻的誤差最小，系統準確性最高，整個結構組織也達到最優。BP神經網絡通常有三個部分組成，分別為輸入層、中間層和輸出層。這個當中輸出層和輸入層只有一個，中間層也叫做隱含層可以有多個，每層之間的神經元是相互隔絕的，該神經網絡系統常見的有三層，如圖2-2所示。圖2.2三層BP神經網絡結構圖在三層BP神經網絡中，定義輸入向量為，若加入一個，此時就可以認為在此神經網絡的隱藏層神經元上引入了闕值量；隱藏層輸出向量可設定為，若加入，則能夠將該層的神經元組織中帶入一個新的闕值量，于是，輸出層的輸出向量就可以設置成，，期望輸出向量設定為。輸入層與隱藏層之間的權值矩陣用v來表示，，其中向量表示神經網絡中中間層的第j個神經元所指向的權向量。權值矩陣以W表示，，其中向量表示神經網絡中輸出層第j個神經元所指的權向量。在神經網絡系統中，每個層面的信號存在著以下關聯：第一，在輸出層的角度，有，，其次，對于隱藏層，有：,上面式中，轉移函數f(x)均為單極性Sigmoid函數：當網絡中輸出值與期望輸出不等時，則存在輸出誤差E，定義如下：將式（1-20）的誤差定義式展開至隱藏層，有：繼續展開至輸入層，有由式（1-22）我們可以看出，此網絡的輸入誤差其實是各層權值和的函數，因此想達到誤差E不斷較小的目的，我們只需要調整各個權值即可，在調整的過程中應該保證權值的調整量和誤差E的負梯度之間成正比，即：,;,上面兩式中的負號表示梯度下降，其中常數可以表示為比例系數，其所反映的是學習速度的具體參考值，所以可以得出一個結論，該神經網絡算法也就是誤差梯度下降算法，屬于δ學習規則范疇。式（1-23）與式（1-24）僅僅能夠表現出權值的調整邏輯，還不夠形成具體的式子，所以在整個推導算式上，假設對隱藏層均有；；對輸出層均有;對于輸出層而言，式可以寫成：對于隱藏層，式可以寫成：對輸出層和隱藏層各自定義一個誤差信號，令：綜合式與式，可以將權值調整式改為：綜合式與式，可以將的權值調整式改為：其實就是誤差修正規則（delta法則）。要完成此權值調整量的計算推導過程則只需要計算出誤差信號和即可。

車載導航系統概述車載導航系統的發展車載導航系統是由許多安裝在車輛上的硬件和軟件系統組合構成，是智能汽車的重要組成部分。車載導航系統涉及多領域的科學技術，比如通信、電氣以及軟件工程等。車載導航定位可以上溯到上古時期的指南車與計里鼓車，這些古人發明的車具備指引方向的功能，計里鼓車除了指向外還具備累計路程的功能。分別如圖2-1所示。圖3.1指南車（左）和計里鼓車（右）人類進入現代文明后的原始的車載導航儀是在車載收音機時代被引入的，與上世紀三十年代被一家意大利公司發明出來。那個時候導航其實就是將一份紙質地圖卷好然后采用特殊方式使其自動跟新位置，因此勉強可以稱之為導航吧。它的原理很簡單：事先把一份卷好的紙質的人工地圖裝進車里的一個小盒子里，這樣駕駛員就可以通過車上一個小小的屏幕看見地圖，獲得提示，它的特殊之處就是在于地圖在汽車行駛過程中會根據汽車的移動而慢慢展開幫助駕駛員跟新地圖，匹配當前位置信息，這就是車載導航系統的雛形了。圖3.2leterAvto導航儀這款導航儀的核心是滾動式地圖，在汽車駕駛中自動顯示當地地圖是通過汽車與地圖之間的連接布線實現的。圖3.3lterAvto滾動地圖1966年，DAIR——一款無需借助衛星的導航輔助系統被美國的通用汽車研究室開發出來。1977年，本田公司開發出了自家汽車導航系統，它能夠追蹤慣性導航（依據速度和軌道來決定狀態）和汽車的方向性轉變。到了盒式磁帶播放器時代，磁帶成為了聲音數據儲存的新方式。在上個世紀八十年代，一家名叫Blaupunkt的公司率先發明應用了第一臺語音車載系統，然而，那個年代同樣還沒有衛星定位，因此使用導航并不方便，它必須要車主手動分別輸入起點和終點的地理數據。在前期準備完成后，車載語音系統會輔助駕駛者運算出應該駕駛的具體路線，再通過技術人員設置出的語音進行播報提示進而告訴駕駛員如何到達行程的目標。同樣出于技術原因，導航只能使用基于車輛的速度來計算出車輛此時所處的大致位置，以確定車輛是否整處于正確路線以及正確位置。邁入CD時代后，導航也取得了巨大的發展。在1989年，歐洲的一家技術公司，名為博世公司，首次推出了第一款能夠實現工業量產的車載導航儀，即TravelPilotIDS，不同于以往的車載導航定位系統，此裝置大大提升了路線的精確程度，系統的地圖數據都是遵照國家標準進行設置的，在CD時代，該導航載體能夠實現數據儲存的最大化。隨著GPS技術的不斷發展與成熟，在上世紀九十年代，該公司發布了一款具有定位功能的新式車載導航系統，這一系統的出現代表著導航的發展真正的邁入正軌，朝著如今的智能導航系統這一方向不斷前進。因此這款導航系統在車載導航系統的發展史上占據著非常重要的地位。迄今為止，很多車載智能導航系統還在使用GPS定位(也有些后裝的汽車導航系統使用的是GPS+北斗雙模)，但是在操作和使用功能上都得到了極大的改善，不僅僅是車載系統上的應用，在移動設備上手導航也變得越來越普遍，而且車聯時代的趨勢也越發明顯了。可以說我們進入了智能導航的時代。導航系統組成按不同的功能可以將一個車載導航系統簡單的劃分為下圖所示的這些模塊。圖3.4車載導航系統系統各模塊組成GPS數據處理模塊主要是對接受到的衛星進行處理，是其誤差變小，定位結果更加精確，它的主要構成是GPS接收機。該接收機可以完成數據的預處理，數據解析以及坐標轉換等多個功能。其基本原理如圖2-4所示：GPS衛星信號按照GPS天線→低噪放大器→濾波器→GPS接收機的路線進行處理傳輸，形成有效的數據，然后再通過串口與其他應用軟件部分進行連接并完成數據的交換。圖3.5GPS衛星接收機的工作原理導航地圖數據庫中將電子地圖以一種特定的格式預先定義并存儲好，可以為車輛導航系統提供道路位置、所處坐標、地理信息特征以及基礎設施等多種重要的信息。另外，可以通過某些方法來實現更新以及維護事先存儲好的導航電子地圖數據庫信息。地圖匹配模塊即判斷當前位置與地圖是否和電子地圖里邊的位置一致，識別出準確的位置以及前進方向。如果電子地圖的位置坐標精度較高，那么此技術將會進一步提高系統的定位精度，提高更多的可靠的數據信息，協助車載導航系統完成路線的正確引導。汽車導航模塊是憑借全球定位系統進行的模塊數據處理，再通過安裝在汽車中的諸多傳感器進行數據輸出的，以判斷數據的正確與否，確定其實時位置，使系統準確及時地確定車輛當前位置所處的路段及其將遇到的十字街道，最具代表性的就是無線電定位技術以及慣性制導技術等。路線引導模塊即引導車輛正確行駛，安全高效的到達終點。它利用導航電子地圖數據庫的位置信息與當前的位置信息進行一個比較，不斷更新，生成實時的交通路線信息，并產生相應的行車指令，以確保車輛能按照正確的路線到達目的地。無線通信模塊主要通過通信網絡完成交通信息的一個實時互換功能，使車載導航系統和道路網絡的工作更安全、更高效。地理信息引擎模塊其實就是一個接口，連接著電子地圖數據庫，通過這個接口我們可以查看地圖，并可以進行縮放操作，此外他還會進行實時更新，幫助我們更好的完成駕駛。路線制定模塊說白了就是輔助駕駛人員進行路線的提前制定，使得駕駛目標便捷化與安全化。它的規劃依靠電子地圖中的各種信息，它會結合用戶關心的因素，例如通行費、路線復雜程度、用時多少以及車流量等規劃處不同的路線讓用用戶進行選擇。并且在規劃路線時，它的路線信息也會根據實時交通信息進行更新讓用戶實時可以選擇自己最需要的路線進行行駛安全，高效的到達目的地。人機交互界面是汽車導航系統與外界交互的一個界面。駕駛者可以在汽車導航系的人機交互界面輸入各種操作指令，例如信息查詢、地圖顯示、路線引導以及路線規劃等以獲取所需要的信息。同時，汽車的導航系統通過可視化的屏幕進行語音提示路線導航等實時活動，從而將實時信息呈現在用戶面前，其中就包括了電子地圖展示以及車輛位置信息等。

路徑規劃路徑規劃概述路徑規劃在車載導航系統中占據著非常重要的地位，通過特定的算法為用戶提供從起點到終點之間的規劃合理的路線以供用戶選擇。汽車導航系統中路徑規劃起著連接作用，它基于電子數字地圖以及信號通信，依靠來自路網的實時交通信息來規劃從車輛當前所處位置到達用戶目的地的之間的行車路線，幫助用戶到達目的地。路徑規劃通常使用費用、距離時間等參考因素來規劃處行駛成本最低的路線。路徑規劃的劃分通常為兩種，即動態路徑規劃和靜態路徑規劃。在最短路徑規劃問題上，科學家迪杰斯特拉（Dikstra）在上世紀六十年代提出了Dikstra算法，迪杰斯特拉解決了有向圖中最短路徑的問題這是他最大的貢獻。Lee算法是較早用于電路的路徑追蹤。Hart等人提出的A*算法是典型的啟發式搜索算法，但此算法存在也有著本身的局限性，著名科學家Floyd解決了部分問題，他于1962年提出了Floyd算法。路徑規劃算法Dikstra算法Dikstra算法結果準確，性能穩定能夠實時適應網絡結構的改變，是處理路徑規劃時最常用的算法之一。使用此 算法一定能夠找到一條最優的路徑，它從起點出發掃描路網中的所有節點，按照路線長度大小的順序搜索，直到找到一條通往目標點的最短路徑截止。但也正式因為此算法的這種搜索模式當遇見路網節點很多時的情況時它的效率也會相應的降低。（1）算法的基本思想從起點出發搜索整個路網，用迭代的方法找一條起點和終點間的最短路徑。在這里設V是節點集，T是缺乏短路徑的節點集合，S是已具備短路徑的節點集合，所以就是T=V-S。設cost[i,j]代表邊<>上的權值，若與之間不相通，則。表示已找到的起點與某一節點之間的最小權值。初始狀態時，，則從開始到其他節點之間的最短長度為。具體求解過程如下：1、選擇，使得//從集合T中求得一條到長度最短的節點，并將該節點存放入集合S中，即。2、若，則//對于新加入的集合S中的節點，修改節點到T中的節點的最短路徑長度3、重復步驟2的工作N-1此。（3）算法的基本流程圖算法的基本流程圖如圖4-1所示：圖4.1Dikstra算法的基本流程圖下面看一個例子：如圖3-2所示的路徑。圖4.2路徑示意圖表4.1Dikstra算法計算流程圖中頂點余下的頂點A(-,0)b(a,2）c(-,∞)d(a,6)e(-,∞)B(a,2)c(b,2+3)d(b,2+1)e(-,∞)D(b,3)C(b,5)e(d,3+3)C(b,5)E(d,6)E(d,6)結束到各頂點的最短路徑：從a到b：a-b，長度為2。從a到d：a-b-c，長度為3.從a到c：a-b-c，長度為5.從a到e：a-b-d-e,長度為6.Floyd算法是動態規劃方案，可以解決有著多對頂點的有向圖中兩點的最短路徑問題。權值為負的邊也可以在該算法中存在，算法運行的時間復雜度為。算法考慮的是最短路徑上的中間頂點，簡單路徑上的中間頂點是除和以外上的任意一個頂點，即任何屬于集合的頂點。Floyd算法的主要思想是，G的節點，有這樣一個V的子集對任意節點i，獲取節點i到j之間的全部路徑，并且路徑之間的節點都屬于V的子集。假使兩點間權值最小的路徑使P，Floyd算法用路徑P和起點的關系，關鍵在P里有沒有中間節點k。（1）如果最短路徑P中沒有k，那么P全部節點都在中。由于集合是集合的子集，所以從節點i到j的最短路徑P，其中的全部中間節點都歸屬與第一個集合區域的范疇，同樣也是第二個集合的最短路徑。（2）要是最短路徑P里有k，則將P分解，如圖4-3所示。假設是從節點i到節點K的最短路徑，且的全部節點都在中。由于節點k不屬于的中間節點，因此是從節點i到節點k的最短路徑。且所有節點均屬于集合.且的全部路徑節點都在集合中。同理是從節點k到節點j之間的最短路徑。圖4.3路徑P的分解Floyd算法的流程圖如圖4.4所示：圖4.4Floyd算法流程圖在Matlab中進行編程可以根據Floyd算法流程圖完成。下面是該算法的部分核心算法：fork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,k)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendend利用Floyd算法可以直接找到任意兩個點之間路徑最短的線路，但是其計算量特別大，在權值為負以及交通網絡過于復雜時此算法不適應。遺傳算法是隨機的搜索算法，有一定方向性，J.Holland教授經過模仿生物進化的想法，把相同的概念用到智能算法里，提出了新的人工智能算法。它利用和生物差不多的變異、交叉還有選擇等運算來提高個體適應性。這種算法有著強擴展性，容易和別的算法相結合，操作起來簡單等優點廣泛，在很多都能用。遺傳算法的那些需要改善的問題得出的和目標函數呼應的適應度函數，種群開始初始化，評估，算出適應度，遺傳操作還有進行選擇。它最好的獲取方法是，經過多次迭代使種群靠近目標函數。遺傳算法流程圖像下面的圖展示的一樣（GEN指的是當前代數；M代表種群規模，i代表種群數量。）圖4.5遺傳算法流程圖(1)遺傳算法的主要步驟遺傳算法歸屬于隨機優化系統，其是通過基因的改變進行優化狀態的實現的，其主要幾個步驟分別為：1)群體格式化；2)計算每個個體的適應值；3)選擇操作：按照“優勝劣汰，適者生存”的原則，個體適應度是高是低和遺傳給下一代的概率是正向相關。經常用輪盤賭算法的辦法來選擇，也就是說讓表示群體的適應度函數值的總和，表示群體中第i個染色體的適應度值，則其適應度值所占的份額剛好與其產生后代的能力相對應。4)交叉運算：同特定的方式交換部分基于，使已經完成配對的兩個染色體變成兩個新的染色體；和別的進化算法比，遺傳算法產生新個體的方法是依靠交叉算子。在交叉前會隨機配對把種群里每個個體進行配對。通常用的交叉方式有：順序交叉、循環交叉、單點交叉、多點交叉、雙點交叉、算術交叉、均勻交叉等。5)變異操作：把變異算子用在種群中。用等位基因代替個體染色體編碼鏈中的某個位點遺傳值，這樣就能形成新的個體。6）判斷條件是否結束，若沒有結束則返回步驟2，否則結束。（2)遺傳算法的運行參數種群規模：規模小，收斂快但會降低種群的多樣性，；編碼長度：編碼長度取決于問題解的精度，精度越高，編碼越長；變異概率：變異概率小的話，那么變異操作產生新個體還有壓制早熟現象的能力都會比較差；變異概率過高，隨機性過大，一般取值范圍為。交叉概率：交叉概率太大容易讓種群已經形成的結構遭到破壞，讓后讓搜索有很大的隨機性；概率小的話發現新個體的速度又會太慢，選擇的值在。終止進化代數：結束算法的一個條件，通常選。

仿真驗證本章節主要利用Matlab軟件仿真驗證兩個部分：（1）實現卡爾曼濾波對車輛導航定位的處理，對比分析軌跡圖以及誤差大小。（2）利用遺傳算法對車輛導航路徑就行一個簡單規劃，簡單模擬車輛是如何實現路徑規劃的。（本次實驗使用的是MatlabR2019a版本）卡爾曼濾波對導航定位的處理本次仿真驗證通過構造一個實際應用的例子來實現。假設有一輛汽車在開闊的場地上行駛，GPS會測量汽車實時位置相對于選定參考點的位置的橫縱坐標，然后通過這些坐標來描述觀測結果，估計該汽車的實時位置。狀態向量，觀測向量。狀態轉移方程和觀測方程分別為：這里給定GPS縱坐標測量的噪聲方差為2（單位為），噪聲均值為0；橫坐標測量的噪聲方差為2，噪聲均值為0；采樣時間點為500個，采樣間隔秒。車輛的初始狀態為（-20；20；10；100），四個狀態量的噪聲的方差分別為（0.01；0.01；0.05；0.05）.仿真實驗結果如下：圖5.1車輛軌跡對比圖圖5.2車輛橫向對比圖圖5.3車輛縱向對比圖從上述三個圖可以看出，與直接利用GPS觀測所獲得的結果相比經過卡爾曼濾波后所獲得的估計狀態狀態波動小，較為穩定且更加的準確，更貼合在實際的日常生活中我們駕駛汽車的過程。本次實驗，直接觀察最后定位平均方誤差在1.7m，利用卡爾曼濾波技術確認定位均方誤差大概在0.5m，這可以表示卡爾曼濾波處理可以獲得更高的定位精度，在這方面的數據處理中效果較好。遺傳算法實現車輛路徑規劃仿真步驟如下：建立一個有十一個節點的路徑圖，如下圖所示：圖5.4路徑規劃圖運行程序我們可以得到以下輸出內容：表5.1最短路徑距離匯總表distance{i,j}12345678910111027136105121114220531483109123750741567694137047961110135314403729811664173045658710859740921485366259078991210711962701210119610851810311141291311849230（1）距離矩陣：Outdistance（i,j），其中i代表起點，j代表終點(2)輸出路徑經過節點：outpath{i,j}，其中i代表起點，j代表終點表5.2最短路徑經過節點統計表path{i,j}12345678910111,21,31,41,2,51,2,5,61,4,71,2,5,81,2,5,6,91,4,7,1022,122,5,6,32,1,42,52,5,62,5,6,72,5,82,5,8,92,5,8,9,1033,13,6,5,233,13,6,53,63,6,73,6,5,83,6,93,6,7,1044,14,1,24,344,1,2,54,1,2,5,64,74,1,2,5,84,7,10,94,7,1055,2,15,25,6,35,2,1,455,65,6,75,85,8,95,6,71066,5,2,16,5,26,36,5,2,1,46,566,76,5,86,96,7,1077,4,17,6,5,27,6,37,47,6,57,677,10,9,87,10,97,1088,5,2,18,5,28,5,6,38,5,2,1,48,58,5,68,9,10,788,98,9,1099,6,5,2,19,8,5,29,6,39,10,7,49,8,59,69,10,79,899,101010,7,4,110,9,8,5,210,7,6,310,7,410,7,6,510,7,610,710,9,810,9101111,9,10,7,4,111,8,5,211,9,6,311,9,10,7,411,8,511,9,611,9,10,711,811,911,9,10從上述兩個表我們可以直觀的看出在具有多路徑選擇規劃時的最短距離即最優路徑經過的節點。如在此路徑圖中節點1與節點3之間的最短路徑距離是，而路線則有以及兩條，則選擇了經過節點最少的路徑，同理節點8到節點11。本次實驗主要目的是確立一條連接31個城市之間的路線圖，通過對比分析遺傳算法的優勢。首先假設31座城市的位置坐標如圖5-5所示：圖5.531座城市的分布圖下面截取了程序運行過程中不同時刻的圖，并進行分析對比：圖5.6最優解和當前解對比圖圖5.7第1步（左）以及第13步（右）的路徑規劃圖圖5.8第32步（左）以及第54步（右）路徑規劃圖圖5.9第89步（左）以及第117步（右）路徑規劃圖圖5.10第150步（左）和第186步（右）路徑規劃圖圖5.11不同運行次數下最終路徑規劃結果圖從程序運行過程以及結果分析，我們可以得出以下結論：1.隨著程序的不斷運行當前解和最優解的數值都成下降趨勢，并且由快速下降到逐漸趨于平緩。2.不同次數運行情況下的結果有所不同。3.在運行過程中最短路徑并不是每次都在降低的，總體趨勢是越來越短但也會存在過程中的比最終結果更優。由此可以看出遺傳算法在處理問題時具有隨機性以及一定的方向性。它通過多次迭代使得種群向目標函數逼近，從而獲得最優解。

結論本次畢業設計針對車載導航的數據處理，在此選取卡爾曼濾波對實驗車輛就行一個GPS定位處理，以及遺傳算法完成路徑的規劃得出以下結論。1、經過卡爾曼濾波處理后所獲得的估計狀態的狀態波動小，較為穩定且更為準確，與實際的日常生活中我們駕駛汽車的過程跟貼合。即通過卡爾曼濾波處理可以使得定位精度更高。2、遺傳算法在處理問題時具有隨機性以及一定的方向性。它通過多次迭代使得種群向目標函數逼近，從而獲得最優解。隨著迭代次數的增加遺傳算法得到的最優解的數值總體成下降趨勢（中途可能出現上升再下降的情況），并且由快速下降到逐漸趨于平緩。本次設計最初的大方向是導航的數據處理技術研究，結合當前社會汽車的發展以及查閱相關文獻確定了最終的方向：車載智能導航系統的數據處理技術研究。然后開始著手此次任務。進度安排大體如下：(1)因為導航通常借助的是衛星