基于馬爾科夫鏈的北斗行駛記錄儀數(shù)據(jù)存儲(chǔ)算法研究

陳石平,馬利濱,徐偉強(qiáng)

(廣州海格通信集團(tuán)股份有限公司,廣東 廣州 510656)

基于馬爾科夫鏈的北斗行駛記錄儀數(shù)據(jù)存儲(chǔ)算法研究

陳石平,馬利濱,徐偉強(qiáng)

(廣州海格通信集團(tuán)股份有限公司,廣東 廣州 510656)

摘要：介紹了北斗行駛記錄儀的組成和功能,對(duì)定時(shí)1 s和定時(shí)60 s報(bào)送或存儲(chǔ)進(jìn)行了對(duì)比和優(yōu)劣分析,根據(jù)道路匹配特性,給出了一種基于馬爾科夫鏈的北斗行駛記錄儀數(shù)據(jù)存儲(chǔ)算法,將馬爾科夫鏈上的節(jié)點(diǎn)(拐點(diǎn))作為記錄儀存儲(chǔ)或傳輸?shù)奈恢命c(diǎn),通過采集車輛狀態(tài)信息和定位模塊輸出信息對(duì)“拐點(diǎn)”計(jì)算方法進(jìn)行分析和推導(dǎo),并通過多次實(shí)際跑車測(cè)試,測(cè)試結(jié)果表明:與定時(shí)1 s報(bào)送或存儲(chǔ)相比,節(jié)省率可達(dá)到90%以上,大大節(jié)省了存儲(chǔ)空間或者通信費(fèi)用,具有較好的使用效果。

關(guān)鍵詞：馬爾科夫鏈;北斗定位模塊;記錄儀;拐點(diǎn)

doi:10.13442/j.gnss.1008-9268.2015.03.010

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：碼： A

文章編號(hào)：號(hào)： 1008-9268(2015)03-0042-04

收稿日期：2015-02-10

作者簡(jiǎn)介

Abstract:First introduced the Beidou recorder composition and function, timing 1 s and the timing 60 s transmit or storage were compared and analyzed the advantages and disadvantages, the paper according to the matching characteristics of the road gives a Markov chain based Beidou recorder data storage algorithm,use node("knee point ")of Markov chain as the position point of recorder storage or transmission, gathering information about the vehicle status and location module outputs information on the "knee" calculation algorithms for analysis and derivation, and by numerous practical car tests, tests show that: compared with the timing 1s to transmit or storage, saving rate can reach more than 90%, greatly saves storage space or communication cost, has good use effect.

0引言

北斗(汽車)行駛記錄儀(以下簡(jiǎn)稱“記錄儀”),又稱黑匣子,是對(duì)車輛行駛速度、位置、時(shí)間、里程以及有關(guān)車輛行駛的狀態(tài)信息進(jìn)行記錄、存儲(chǔ)并可通過接口實(shí)現(xiàn)數(shù)據(jù)輸出的數(shù)字式電子記錄裝置。記錄儀的使用,對(duì)遏止疲勞駕駛、車輛超速等交通違法行為,保障車輛行駛安全以及道路交通事故的分析鑒定具有重要的作用[1]。西方發(fā)達(dá)國(guó)家早在70年代就開始在汽車上強(qiáng)制安裝、使用GPS汽車行駛記錄儀。我國(guó)于2004年7月起,開始在全國(guó)營(yíng)運(yùn)客車等車輛上逐步開始應(yīng)用。

1記錄儀

北斗衛(wèi)星導(dǎo)航系統(tǒng)已經(jīng)覆蓋亞太地區(qū)運(yùn)行,國(guó)內(nèi)各行業(yè)的北斗二號(hào)項(xiàng)目開展迅速,面對(duì)北斗衛(wèi)星導(dǎo)航系統(tǒng)難得的發(fā)展機(jī)遇,國(guó)內(nèi)各行業(yè)的北斗二號(hào)示范工程如火如荼的開展,北斗衛(wèi)星導(dǎo)航產(chǎn)業(yè)必將迎來大規(guī)模發(fā)展。從國(guó)家安全戰(zhàn)略、國(guó)家經(jīng)濟(jì)利益上考慮,國(guó)家必將全力推廣北斗衛(wèi)星導(dǎo)航系統(tǒng),將會(huì)逐步采用北斗定位模塊代替原來純GPS定位模塊。

目前國(guó)內(nèi)記錄儀包括微處理器、數(shù)據(jù)存儲(chǔ)器、北斗(BD/GPS)定位模塊[2]、車輛狀態(tài)信息采集模塊、無線通信模塊、實(shí)時(shí)時(shí)鐘、數(shù)據(jù)通信接口等[3]。

記錄儀采集信息包括衛(wèi)星定位模塊的時(shí)間、經(jīng)度、緯度、速度、方向、高程(技術(shù)規(guī)范[4]還增加偽距、DOP、信噪比、有效衛(wèi)星數(shù)等),以及車速傳感器、制動(dòng)信號(hào)、左轉(zhuǎn)向、右轉(zhuǎn)向、近光、遠(yuǎn)光等車輛狀態(tài)信息。對(duì)采集的信息記錄在數(shù)據(jù)存儲(chǔ)器上(也可以通過GPRS/CDMA等無線通信方式上傳至監(jiān)控中心),主要的數(shù)據(jù)記錄功能有:位置信息記錄不少于360 h、行駛速度記錄不少于48 h、事故疑點(diǎn)記錄不少于100條、超時(shí)駕駛記錄不少于100條、安裝參數(shù)記錄、日志記錄等,其中以位置信息記錄時(shí)間最長(zhǎng),消耗的存儲(chǔ)器空間最多。

在行駛狀態(tài)下,報(bào)送或存儲(chǔ)的要求:定時(shí)報(bào)送1 s～60 s、定距報(bào)送不大于1 000 m、以及按設(shè)置參數(shù)的定時(shí)定距報(bào)送。以定時(shí)報(bào)送為例,報(bào)送或存儲(chǔ)不少于360 h,每次存儲(chǔ)或者傳輸數(shù)據(jù)量是一樣的。

一般城市道路呈網(wǎng)格形狀,存在大量的“T”路口、“十”字路口、彎道、U形轉(zhuǎn)彎處等“拐點(diǎn)”(節(jié)點(diǎn))特性,而且每條道路長(zhǎng)短不一,短則幾十米,長(zhǎng)則達(dá)數(shù)公里。假如汽車行駛速率60 km/h,若定時(shí)60 s報(bào)送數(shù)據(jù),則60 s內(nèi)行駛1 km可能已經(jīng)拐過幾個(gè)路口或是掉頭,間距1 km內(nèi)只報(bào)送(存儲(chǔ))1次數(shù)據(jù)顯然不能匹配地圖道路或者存在數(shù)條道路可以通過造成路徑“多義性”;若定時(shí)1 s(一般的衛(wèi)星定位模塊輸出信息頻率為1 Hz)報(bào)送,間距1 km內(nèi)則需要報(bào)送(存儲(chǔ))60次數(shù)據(jù),需要大量的無線通信流量或存儲(chǔ)資源,對(duì)擁有大量車輛的監(jiān)控中心的處理造成很大的壓力。定時(shí)1 s報(bào)送與定時(shí)60 s報(bào)送對(duì)比如表1所示。

聯(lián)系人： 陳石平 E-mail: oldslam@126.com

表1　定時(shí)1 s報(bào)送與定時(shí)60 s報(bào)送對(duì)比

從表1分析可知,兩種單純的定時(shí)報(bào)送均存在不足之處,需要在成本和性能之間進(jìn)行折中處理,如根據(jù)采集車輛的相關(guān)信息和北斗定位模塊輸出信息,對(duì)報(bào)送的時(shí)間間隔進(jìn)行自適應(yīng)處理的研究顯得尤為重要。

車輛行駛過程中會(huì)經(jīng)過“T”路口、“十”字路口等復(fù)雜路段,因此將“拐點(diǎn)”信息記錄在數(shù)據(jù)存儲(chǔ)器上顯得十分重要,且能很好地進(jìn)行道路匹配,而對(duì)于“拐點(diǎn)”之間不記錄的位置信息(兩拐點(diǎn)之間位置信息接近直線)也不會(huì)影響軌跡匹配道路。

2馬爾科夫鏈

馬爾可夫過程[5]由俄國(guó)數(shù)學(xué)家馬爾可夫于1907年提出和研究的一類隨機(jī)過程,至今已經(jīng)成為內(nèi)容豐富、理論完整、應(yīng)用廣泛的一門數(shù)學(xué)分支,其應(yīng)用領(lǐng)域涉及計(jì)算機(jī)、通信、自動(dòng)控制等方面。其特性為:在已知目前狀態(tài)(現(xiàn)在)的條件下,它未來的演變(將來)不依賴于它以往的演變(過去)。高聯(lián)雄等人(2009年)提出基于馬爾科夫鏈模型去衡量公共交通網(wǎng)絡(luò)中的關(guān)鍵樞紐點(diǎn)(hub)的重要性[6],然后推出道路轉(zhuǎn)移概率和最后評(píng)價(jià)解決方案的獨(dú)特性。論文[7]研究了車輛出行道路狀態(tài)轉(zhuǎn)移過程具有馬爾科夫?qū)傩?證實(shí)該過程是一個(gè)時(shí)間齊次馬爾科夫鏈,交通網(wǎng)絡(luò)中車輛連續(xù)行駛的路段轉(zhuǎn)移過程就是一個(gè)馬爾科夫過程,并給出了車輛出行道路轉(zhuǎn)移過程的馬爾科夫鏈模型。

將交通網(wǎng)絡(luò)中的車輛行駛所在道路看做為一個(gè)狀態(tài)空間,并且汽車行駛中的道路轉(zhuǎn)移過程用道路“拐點(diǎn)”來表示。對(duì)車輛運(yùn)行的過程可以表達(dá)為連續(xù)離散時(shí)間t={i,i+1,i+2,i+3,…}的一個(gè)序列X={Pi,Pi+1,Pi+2,…},其中小寫字母就是i時(shí)刻的狀態(tài),即汽車行駛所在道路經(jīng)緯度信息Pi=Pi(x,y),狀態(tài)空間Φ={Pi,Pi+1,Pi+2,…}.汽車所在道路對(duì)于過去狀態(tài)的條件概率分布p僅是上一時(shí)刻狀態(tài)的一個(gè)函數(shù),即p={X(ti+2)|X(ti+1)=Pi+1,X(ti)=Pi}=p{X(ti+2)|X(ti+1)=Pi+2}.

3拐點(diǎn)算法研究

與一般公路和高速公路相比,城市交通系統(tǒng)中的彎道、U形轉(zhuǎn)彎處、交叉路口等數(shù)量眾多,交通網(wǎng)絡(luò)錯(cuò)綜復(fù)雜。城市交通網(wǎng)絡(luò)是一個(gè)典型的由節(jié)點(diǎn)和邊構(gòu)成的網(wǎng)絡(luò),它由道路物理網(wǎng)絡(luò)與交通需求網(wǎng)絡(luò)的結(jié)合而形成,其中道路可以抽象為邊,道路“T” 路口、“十”字路口、彎道、U形轉(zhuǎn)彎處等為節(jié)點(diǎn),大量的節(jié)點(diǎn)和邊組成了交通網(wǎng)絡(luò)構(gòu)架。因此,我們根據(jù)交通系統(tǒng)的復(fù)雜網(wǎng)絡(luò)特性,構(gòu)建以“拐點(diǎn)”(節(jié)點(diǎn))為記錄位置點(diǎn),即將馬爾科夫鏈上的節(jié)點(diǎn)(“拐點(diǎn)”)作為記錄儀存儲(chǔ)或傳輸?shù)奈恢命c(diǎn)進(jìn)行研究。

3.1　預(yù)處理

眾所周知,汽車行駛速度都有限,高速公路一般限速120km/h(市區(qū)快速路限速80km/h)即車速最高為34m/s.目前北斗定位模塊的定位精度為10m,輸出定位信息頻率為1Hz,汽車行駛1s,北斗定位模塊在1s間隔內(nèi)產(chǎn)生的漂移距離一般不會(huì)超過(34+10)m,定位漂移距離如超過44m就可認(rèn)為無效定位數(shù)據(jù),這樣就可以將無效定位數(shù)據(jù)過濾掉。

3.2　采集車輛狀態(tài)信息計(jì)算“拐點(diǎn)”

記錄儀可以實(shí)時(shí)采集車速傳感器、制動(dòng)信號(hào)、左轉(zhuǎn)向、右轉(zhuǎn)向、近光、遠(yuǎn)光等車輛狀態(tài)信息。拐點(diǎn)算法如下:

1) 車輛啟動(dòng)后,行駛開始(車輛從靜止?fàn)顟B(tài)轉(zhuǎn)變?yōu)樾旭偁顟B(tài):速度大于0km/h且持續(xù)10s以上,可以通過采集車速傳感器信號(hào)即可)后,記錄第11s的位置信息作為一個(gè)拐點(diǎn)。

2) 正常行駛過程中,記錄儀采集不到車輛的制動(dòng)信號(hào),一旦采集到制動(dòng)信號(hào)(如等紅燈或其它特殊情況),實(shí)時(shí)采集的車速傳感器速度信號(hào)逐漸變小,記錄速度保持為零(車輛從行駛狀態(tài)轉(zhuǎn)變?yōu)殪o止?fàn)顟B(tài):速度等于0km/h且持續(xù)10s以上)的第11s位置信息作為一個(gè)拐點(diǎn)。

3) 彎道的拐角較大時(shí)(如“T”路口、“十”字路口、U形轉(zhuǎn)彎處等),車輛一般會(huì)開啟轉(zhuǎn)向信號(hào)(左轉(zhuǎn)或右轉(zhuǎn)),記錄儀采集到汽車轉(zhuǎn)向信號(hào),統(tǒng)計(jì)期間的坐標(biāo)位置的平均值(也可以選取中間時(shí)間點(diǎn)所對(duì)應(yīng)的位置)作為拐點(diǎn)。

4) 記錄一個(gè)拐點(diǎn)后,車輛行駛超過60s無拐點(diǎn),則記錄第60s(定時(shí)報(bào)送不超過60s)的位置信息作為下一個(gè)拐點(diǎn)。

3.3　采集北斗定位信息計(jì)算“拐點(diǎn)”

目前記錄儀上傳信息有(t,x,y,v,θ)等,分別代表時(shí)間、緯度、經(jīng)度、速率、方向角,在tis(其中1≤i≤n,n為自然數(shù))時(shí)對(duì)應(yīng)的緯度xi、經(jīng)度yi、速率vi、方向角θi,即對(duì)應(yīng)經(jīng)緯度坐標(biāo)為Pi=(xi,yi),定義拐角閾值Δθth=Δθi+l=|θi+l-θi|(2≤l≤60)為(i+l)s與is方向角之差。

對(duì)于“T”路口、“十”字路口、U形轉(zhuǎn)彎處等“拐點(diǎn)”,拐角特性比較明顯,拐角數(shù)值較大,加上采集車輛狀態(tài)信息比較容易計(jì)算。對(duì)于彎道來說,拐角閾值Δθth難于認(rèn)定,拐角閾值Δθth太小,則不可避免地會(huì)記錄大量無用位置信息;拐角閾值Δθth太大會(huì)遺漏很多關(guān)鍵位置信息。道路拐角的閾值大小,顯得很重要。經(jīng)過多次測(cè)試比較,在本算法中:取拐角Δθth=10°,即Δθth=Δθi+l=|θi+l-θi|<10°(1≤l≤10)持續(xù)時(shí)間在10 s以上則認(rèn)為直線行駛,拐角Δθi+l=|θi+l-θi|≥10°(1≤l≤3)持續(xù)時(shí)間在3 s以上則認(rèn)為彎道行駛,150°<Δθi+l=|θi+l-θi|≤180 °(1≤l≤3)持續(xù)時(shí)間在3 s以上則認(rèn)為掉頭(如U形轉(zhuǎn)彎)。

彎道的拐角較小時(shí),此時(shí)車輛一般不會(huì)開啟轉(zhuǎn)向信號(hào)(左轉(zhuǎn)或右轉(zhuǎn)),必須根據(jù)北斗定位模塊的輸出信息進(jìn)行相關(guān)處理,假設(shè):1≤i≤h≤k≤n,1≤i≤h≤m≤n,根據(jù)求道路特性求拐點(diǎn)。具體如下:

車輛行駛后,記錄儀定位并獲取時(shí)間、緯度、經(jīng)度、速率、方向角等信息,行駛軌跡如圖1所示,若P1處記錄第1個(gè)拐點(diǎn)T1,在第is(包括第is)之前一直保持直線行駛即Δθi=|θi-θ1|<10°,其中(2≤i≤60),在(i+1)s時(shí)記錄儀采集拐角Δθi+1=|θi+1-θ1|≥10°且持續(xù)時(shí)間超過3 s,即Δθi+l=|θi+l-θ1|≥10°,其中(1≤l≤3),直線P1Pi延長(zhǎng)至Pi′點(diǎn),在(i+l)s(其中1≤l≤3)時(shí)均有Δθi+l=∠Pi′PiPi+l=|180 °-∠P1PiPi+l|≥10 °,則認(rèn)為Pi為第2個(gè)拐點(diǎn)T2.

圖1　采集北斗定位信息判斷“拐點(diǎn)”

依據(jù)上述方法尋找第3個(gè)拐點(diǎn):在第hs(包括第hs)之前一直保持直線行駛即Δθh=|θh-θi|<10°(1≤h≤60),在(j+1)s時(shí)記錄儀采集拐角Δθh+1=|θh+1-θi|≥10°且持續(xù)時(shí)間超過3 s,即Δθh+l=|θh+l-θi|≥10°,其中(1≤l≤3),如圖1所示,直線PiPh延長(zhǎng)至Ph′點(diǎn),在(h+l)(1≤l≤3)s時(shí)均有Δθh+l=∠Ph′PhPh+l=|180°-∠PiPhPh+l|≥10°,則認(rèn)為Ph為第3個(gè)拐點(diǎn)T3.

以此類推,可計(jì)算出第4個(gè)拐點(diǎn)T4、第5個(gè)拐點(diǎn)T5…,直至行駛結(jié)束第m個(gè)拐點(diǎn)Tm.

4試驗(yàn)測(cè)試

對(duì)上述計(jì)算算法編寫相關(guān)軟件代碼。車上放置兩臺(tái)裝有北斗定位模塊(組合定位模式下,定位性能與GPS模塊相當(dāng))的記錄儀(編號(hào)為記錄儀A、記錄儀B),其中一臺(tái)記錄儀A實(shí)時(shí)采集數(shù)據(jù),采集頻率為1Hz;另外一臺(tái)記錄儀B使用上述算法尋找拐點(diǎn),將采集到的拐點(diǎn)信息并存儲(chǔ)。兩臺(tái)設(shè)備進(jìn)行對(duì)比測(cè)試,行車路線:海珠區(qū)(圖中A處)→越秀區(qū)、天河區(qū)(圖中B處)→蘿崗區(qū)(圖中C、D處),其中從A處開始,在B處由于處于天河區(qū)高樓密集造成短時(shí)不能定位或者定位誤差較大,C處為U型轉(zhuǎn)彎處,D處?kù)o止后停止采集數(shù)據(jù)。記錄儀A實(shí)時(shí)采集數(shù)據(jù),行駛3 589s,采到3 589個(gè)數(shù)據(jù)位置信息,將位置數(shù)據(jù)信息導(dǎo)入衛(wèi)星地圖,行駛軌跡如圖2所示,在城市中行駛軌跡能較好的匹配道路,說明北斗定位模塊定位較好,精度較好。

圖2　定時(shí)1 s報(bào)送行駛軌跡圖

記錄儀B使用上述算法,共記錄150個(gè)拐點(diǎn)數(shù)據(jù),記錄儀B存儲(chǔ)空間僅為記錄儀A存儲(chǔ)空間4.2%,節(jié)省率95.8%,大大節(jié)省了存儲(chǔ)空間或者通信費(fèi)用,并將這些拐點(diǎn)導(dǎo)入到衛(wèi)星地圖,行駛軌跡基本能匹配道路,道路匹配特性略遜于記錄儀A。此外通過多次試驗(yàn)結(jié)果表明,與定時(shí)1s報(bào)送相比,根據(jù)道路特性不同,可以獲得不同節(jié)省率:道路較直時(shí)(拐點(diǎn)較少),節(jié)省率最大,理論可以達(dá)(1-1/60)×100%=98.3%;道路存在“T”路口、“十”字路口、U形轉(zhuǎn)彎處時(shí)(拐點(diǎn)較多),節(jié)省率也可達(dá)到90%,達(dá)到了較好的效果。

5結(jié)束語(yǔ)

針對(duì)目前北斗衛(wèi)星導(dǎo)航系統(tǒng)的大力發(fā)展以及記錄儀的推廣,使用國(guó)產(chǎn)定位效果良好的北斗雙模定位模塊,結(jié)合馬爾科夫過程的特性,提出一種基于馬爾科夫鏈的北斗行駛記錄儀數(shù)據(jù)存儲(chǔ)算法,對(duì)算法進(jìn)行介紹、分析和推導(dǎo),并通過多次實(shí)際跑車測(cè)試,測(cè)試表明:與定時(shí)1s報(bào)送或存儲(chǔ)相比,節(jié)省率也可達(dá)到90%以上,大大節(jié)省了存儲(chǔ)空間或者通信費(fèi)用,具有較好的使用效果。

參考文獻(xiàn)

[1]國(guó)家質(zhì)量監(jiān)督檢驗(yàn)檢疫總局.GB/T19056-2012 汽車行駛記錄儀[S]. 中國(guó)標(biāo)準(zhǔn)出版社,2012.

[2]潘未莊，陳石平，牛明超，等.一款北斗/GPS雙模定位模塊設(shè)計(jì)與實(shí)現(xiàn)[J].全球定位系統(tǒng)，2014,39(2):34-38.

[3]中華人民共和國(guó)交通運(yùn)輸部交通運(yùn)輸部.JT/T794-2011道路運(yùn)輸車輛衛(wèi)星定位系統(tǒng)車載終端技術(shù)要求[S].中國(guó)標(biāo)準(zhǔn)出版社，2011.

[4]交通運(yùn)輸部.道路運(yùn)輸車輛衛(wèi)星定位系統(tǒng)北斗兼容車載終端技術(shù)規(guī)范[S].中國(guó)標(biāo)準(zhǔn)出版社,2013.

[5]毛用才,胡奇英.隨機(jī)過程[M].西安:西安電子科技大學(xué)出版社,2004:101-131.

[6]GAOLianxiong,LIANGHong.Hubnodesidentificationinpublictransportnetworksusingmarkovchainmodel[C]//IEEEICMA, 2009; 334-339.

[7]吳迪.基于馬爾科夫鏈的交通網(wǎng)絡(luò)道路權(quán)重計(jì)算方法研究[D].長(zhǎng)春:吉林大學(xué),2011.

陳石平(1981-),男,工程師,現(xiàn)主要從事北斗導(dǎo)航產(chǎn)品的研究與設(shè)計(jì)。

馬利濱(1967-),男,高級(jí)工程師,主要從事北斗導(dǎo)航產(chǎn)品系統(tǒng)與設(shè)計(jì)。

徐偉強(qiáng)(1985-),男,工程師，主要從事北斗導(dǎo)航產(chǎn)品軟件設(shè)計(jì)。

The Research of Beidou Recorder Data Storage

Algorithm Based Markov Chain

CHEN Shiping,MA Libin,XU Weiqiang

(GuangzhouHaigeCommunicationsGroupInconrporatedCompany,Guangzhou510656,China)

Key words: Markov chain; Beidou locating module; data recorder; knee