基于有限狀態機對GPS數據快速提取的研究

天津理工大學電子信息工程學院 王 江 姜道連重慶郵電大學自動化學院 楊成成 王皓辰

?

基于有限狀態機對GPS數據快速提取的研究

天津理工大學電子信息工程學院 王 江 姜道連
重慶郵電大學自動化學院 楊成成 王皓辰

【摘要】本文提出一種基于有限狀態機的GPS數據過濾與清理方法，提高GPS系統中數據的質量。結合u-blox公司的NEO-6M模組以及ST公司提供的Cortex-M3內核的芯片，主要敘述怎樣使用有限狀態機對GPS數據進行快速分析、識別以及提取。在大量的GPS數據中快速識別提取所需的數據，很大程度上提高了解析的準確性與快速性，降低漏讀、多讀、誤讀帶來的誤差。體現出在信息的提取處理過程中有限狀態機思想的優越性，這種方法對數據處理具有很高的實用價值，在大數據時代的今天顯得愈加重要。

【關鍵詞】有限狀態機；數據處理；GPS；Cortex-M3

0　引言

近年來，GPS廣泛滲入軍用、商用、民用、實驗室等各個領域，信息時代發展的今天離不開導航系統。某些實驗室已經加緊導航系統的研發，只要涉及到有關信息的產品的研發，就會涉及到數據處理，由于原始的GPS數據包含的信息比較多，數據量大，它包括了地理定位信息，推薦定位信息，地面速度信息，GPS定位信息，當前衛星信息，可見衛星信息等多種數據類型的信息。對于有些簡單應用來說，并不是所有數據都是必須的，所以，我們需要從大量的數據中提取出核心數據。然而有限狀態機方法就是使用簡單而有效的技術手段從大量的GPS信息中快速甄別、提取關鍵有用的數據，它的狀態是有限的，各狀態之間相互轉移，構成整個狀態機系統。

1　GPS

GPS（全球定位系統）由美國軍方研制，是一種具有全時段、全天候、全方位的高精度衛星導航系統，抗干擾性好，保密能力強。它的數據主要包含以下六大信息類型：$GPGGA、$GPGLL、$GPGSV $GPGSA、$GPRMC、$GPVTG［1］。可見GPS芯片在正常工作狀態下更新一次衛星傳送來的數據包所包含內容繁多，很多信息對于多數應用系統來說都是冗余信息，快速識別提取關鍵的有用信息是研究的核心。

2　有限狀態機

FSM描述了特定算法，是計算機科學、離散系統和數學建模的有力工具，能夠簡化系統的復雜性，我們可以假定系統是在某個狀態下，由于狀態的固定性，在有限的時間里，固定狀態從前驅狀態向后繼狀態轉移。有限狀態機的工作方式是在事件驅動的基礎上建立的，包括了狀態→轉移→事件→動作四個要素。

3　主系統設計

NEO-6M模組與Cortex-M3內核的嵌入式主控單元通過UART接口連接，從數據包中提取出有用信息再與應用層軟件共享，這里為了驗證有限狀態機方法的實際效果，將主控單元再與USB-TTL模塊通過UART接口連接，USB-TTL模塊通過USB口與電腦連接，用于測試提取數據的結果。快速識別并提取GPS數據的主系統示意圖如圖1所示。

圖1　系統硬件連接示意圖

GPS模塊設計：

模塊采用u-blox公司的NEO-6M模組，默認采用NMEA-0183協議輸出定位數據，通過UBX協議對其進行配置，搜星能力強，追蹤靈敏度高達-161dBm，數據輸出時，刷新頻率可以最高達到5Hz，其原理圖如圖2所示。

圖2　GPS接收機原理圖

4　GPS數據識別與提取

4.1GPS數據格式

GPS數據幀主要有幀頭、幀尾和幀內數據組成，由于數據幀的不同，幀頭也不同，常用的主要有$GPGGA、$GPGSA、$GPGSV和$GPRMC。以$GPRMC幀為例，結構及各字段如下［2］：

GPRMC，102020.00，A，3903.45973，N，11708.02472，E，0.043，350.33，031214，-6.2，E，A*7A

$GPRMC，＜1＞，＜2＞，＜3＞，＜4＞，＜5＞，＜6＞，＜7＞，＜8＞，＜9＞，＜10＞，＜11＞，＜12＞*hh＜CR＞＜LF＞

＜1＞UTC時間、＜2＞定位狀態、＜3＞緯度、＜4＞緯度半球、＜5＞經度、＜6＞經度半球、＜7＞地面速率、＜8＞地面航向、＜9＞UTC日期、＜10＞磁偏角、＜11＞磁偏角方向、＜12＞模式指示［2］。

4.2接收與解析數據

本系統中，NEO-6M模組實時更新當前定位的數據，再通過UART串口發送給Cortex-M3內核的處理器，當狀態處于啟動標識符時，立即啟動解析提取功能。通過在大量數據間的狀態轉移，對數據信息進行區分，經過幀結構、字段分析等過程，最終快速得到所需要的數據。本系統狀態轉移圖如圖3所示。

圖3　狀態轉換圖

4.2.1幀結構分析

根據接收到的數據，進行信息檢索分析。s1狀態分析出“$”，自動轉到下一狀態分析出“G”，以此原理，直到找到$GPRMC這一幀數據，然后進入數據提取狀態，其中s1-s6為幀結構分析，s7-s10為字段分析。

4.2.2字段分析

在幀結構分析的基礎上，進行信息提取，通過計算逗號的個數，提取出UTC時間，緯度，經度，UTC日期等相關核心信息。字段分析狀態機圖如3圖所示，檢索數據，根據原數據中逗號個數進行匹配，如匹配成功，則將逗號后面內容保存到數組中，遇到相應標志時，轉移到發送狀態，將數據數據共享到應用層軟件，否則返回繼續檢索。UTC時間發送指令由第1個逗號觸發，緯度發送指令由第3個逗號觸發，經度發送指令由第5個逗號觸發，UTC日期發送指令由第9個逗號觸發，這一系列的狀態轉移均由相應程序控制自動完成，極大提高了識別數據的速度。

其中s0為初始狀態，成功提取到$字符時，自動轉移到s1狀態，s2為成功提取到G字符狀態，s3為成功提取到P字符狀態，s4為成功提取到R字符狀態，s5為成功提取到M字符狀態，s6為成功提取到C字符狀態，s7為成功提取到UTC時間狀態，s8為成功提取緯度狀態，s9為成功提取經度狀態，s10為成功提取日期狀態，s11為顯示提取到的數據狀態。其中seg_count1、seg_count3、seg_count5、seg_count9是逗號計數信號，seg_countA、seg_countV分別為數據有效和無效信號。RI、TI為接收和發送觸發信號。

4.3大地——高斯坐標變換

由于現行的GPS系統基本采用WGS-84坐標系，為了將提取出來的數據顯示到數字地圖上，必須把大地坐標，過程如下：→本地高斯坐標。

下面給出高斯投影正算公式：

5　系統實現及測試

當解析成功后，主控單元將識別并提取的信息提供給應用層軟件使用，如顯示、存儲、計算等。為了對系統算法進行簡單驗證，這里將檢測結果通過UART發送到上位機進行顯示，來驗證算法的有效性和可靠性，通過實驗驗證得到如圖4的實時提取數據示意圖，經過反復實驗和數據分析，本文提出的利用有限狀態機提取GPS數據信息得到實際驗證，不僅消耗資源少，而且快速有效，同時也給類似序列檢測的問題提供了一種行之有效的技術手段。

圖4　驗證結果的截圖

6　結語

GPS定位系統，作為全球衛星定位系統，在滿足軍事用途的同時，也在不斷加緊民用化，科研化的進程。本文研究了解決識別GPS數據慢的問題，為以后的學術應用，生活導航奠定了堅實的基礎。此文的研究方案性能穩定，消耗系統資源少。對于其他工程設計具有一定參考價值。本文采用有限狀態機法，能夠快速識別提取出所需的GPS數據。取代了人工對GPS數據的分析，達到快速而精準獲取信息的目的，該方法在科技研究領域有較好的應用前景。

參考文獻

［1］李文斌.基于.NET平臺的車輛監控系統設計與應用［D］.杭州電子科技大學，2014.

［2］杜楠.基于嵌入式系統的GPS車輛導航的設計與實現［D］.哈爾濱工程大學，2012.

［3］朱華炳，馮霄，董伯麟.基于有限狀態機的STEP-NC加工程序信息提取技術的研究［J］.現代制造工程，2012，No.38712：44-47+65.

［4］王君剛，王解先，陳俊平等.U-Blox 6接收機解碼與定位測試［J］.測繪通報，2015，No.46411：24-27.

［5］潘宗鵬，柴洪洲，劉軍等.基于部分整周模糊度固定的非差GPS精密單點定位方法［J］.測繪學報，2015，v.4411：1210-1218.

［6］丁鎖妹.北斗衛星導航系統觀測數據的可用性分析［D］.大連理工大學，2014.

［7］羅元劍，姜建國，王思葉等.基于有限狀態機的RFID流數據過濾與清理技術［J］.軟件學報，2014，v.2508：1713-1728.

王江（1994—），男，貴州畢節人，大學本科在讀，主要從事單片機的研究、信號處理的研究。

姜道連（1972—），男，安徽泗縣人，講師，主要從事信息信號處理，嵌入式技術等方面的教學研究。

楊成成（1993—），男，貴州畢節人，大學本科在讀，主要從事單片機、過程控制的研究。

王皓辰（1994—），男，陜西寶雞人，大學本科在讀，主要從事單片機、自動控制的研究。

Research on Fast GPS Data Extraction Based on FSM

WANG Jiang1，JIANG Dao-lian1，YANG Cheng-cheng2， WANG Hao-chen2

（1.School of Electronic Information Engineering，Tianjin University of Technology，Tianjin 300384，China；2.School of Automation and Electrical Engineering，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

Key Words：Finite-state machine；data processing；GPS；Cortex-M3

Abstract：A method of GPS data filtering and cleaning based on finite-state machine is put forward in this paper，which can improve the quality of data in GPS system.In combination with the NEO-6M module of u-blox Company and the chip with Cortex-M3 core provided by ST Company，how finite-state machine is utilized to rapidly analyze，identify and extract GPS data is mainly discussed in this paper.The realization of rapidly identifying and extracting required data from a mass of GPS data has greatly raised the accuracy and speed of analysis，and reduced error due to omissive reading，excessive reading or misreading.The advantages of the finite-state machine thought in the process of information extraction and processing have been reflected.This method is of high practical value to data processing，and it is especially important in the age of big data.

作者簡介：