基于马尔科夫链的北斗行驶记录仪数据存储算法研究

陈石平,马利滨,徐伟强

(广州海格通信集团股份有限公司,广东 广州 510656)

基于马尔科夫链的北斗行驶记录仪数据存储算法研究

陈石平,马利滨,徐伟强

(广州海格通信集团股份有限公司,广东 广州 510656)

摘要：介绍了北斗行驶记录仪的组成和功能,对定时1 s和定时60 s报送或存储进行了对比和优劣分析,根据道路匹配特性,给出了一种基于马尔科夫链的北斗行驶记录仪数据存储算法,将马尔科夫链上的节点(拐点)作为记录仪存储或传输的位置点,通过采集车辆状态信息和定位模块输出信息对“拐点”计算方法进行分析和推导,并通过多次实际跑车测试,测试结果表明:与定时1 s报送或存储相比,节省率可达到90%以上,大大节省了存储空间或者通信费用,具有较好的使用效果。

关键词：马尔科夫链;北斗定位模块;记录仪;拐点

doi:10.13442/j.gnss.1008-9268.2015.03.010

中图分类号：TP391

文献标志码：码： A

文章编号：号： 1008-9268(2015)03-0042-04

收稿日期：2015-02-10

作者简介

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引言

北斗(汽车)行驶记录仪(以下简称“记录仪”),又称黑匣子,是对车辆行驶速度、位置、时间、里程以及有关车辆行驶的状态信息进行记录、存储并可通过接口实现数据输出的数字式电子记录装置。记录仪的使用,对遏止疲劳驾驶、车辆超速等交通违法行为,保障车辆行驶安全以及道路交通事故的分析鉴定具有重要的作用[1]。西方发达国家早在70年代就开始在汽车上强制安装、使用GPS汽车行驶记录仪。我国于2004年7月起,开始在全国营运客车等车辆上逐步开始应用。

1记录仪

北斗卫星导航系统已经覆盖亚太地区运行,国内各行业的北斗二号项目开展迅速,面对北斗卫星导航系统难得的发展机遇,国内各行业的北斗二号示范工程如火如荼的开展,北斗卫星导航产业必将迎来大规模发展。从国家安全战略、国家经济利益上考虑,国家必将全力推广北斗卫星导航系统,将会逐步采用北斗定位模块代替原来纯GPS定位模块。

目前国内记录仪包括微处理器、数据存储器、北斗(BD/GPS)定位模块[2]、车辆状态信息采集模块、无线通信模块、实时时钟、数据通信接口等[3]。

记录仪采集信息包括卫星定位模块的时间、经度、纬度、速度、方向、高程(技术规范[4]还增加伪距、DOP、信噪比、有效卫星数等),以及车速传感器、制动信号、左转向、右转向、近光、远光等车辆状态信息。对采集的信息记录在数据存储器上(也可以通过GPRS/CDMA等无线通信方式上传至监控中心),主要的数据记录功能有:位置信息记录不少于360 h、行驶速度记录不少于48 h、事故疑点记录不少于100条、超时驾驶记录不少于100条、安装参数记录、日志记录等,其中以位置信息记录时间最长,消耗的存储器空间最多。

在行驶状态下,报送或存储的要求:定时报送1 s～60 s、定距报送不大于1 000 m、以及按设置参数的定时定距报送。以定时报送为例,报送或存储不少于360 h,每次存储或者传输数据量是一样的。

一般城市道路呈网格形状,存在大量的“T”路口、“十”字路口、弯道、U形转弯处等“拐点”(节点)特性,而且每条道路长短不一,短则几十米,长则达数公里。假如汽车行驶速率60 km/h,若定时60 s报送数据,则60 s内行驶1 km可能已经拐过几个路口或是掉头,间距1 km内只报送(存储)1次数据显然不能匹配地图道路或者存在数条道路可以通过造成路径“多义性”;若定时1 s(一般的卫星定位模块输出信息频率为1 Hz)报送,间距1 km内则需要报送(存储)60次数据,需要大量的无线通信流量或存储资源,对拥有大量车辆的监控中心的处理造成很大的压力。定时1 s报送与定时60 s报送对比如表1所示。

联系人： 陈石平 E-mail: oldslam@126.com

表1　定时1 s报送与定时60 s报送对比

从表1分析可知,两种单纯的定时报送均存在不足之处,需要在成本和性能之间进行折中处理,如根据采集车辆的相关信息和北斗定位模块输出信息,对报送的时间间隔进行自适应处理的研究显得尤为重要。

车辆行驶过程中会经过“T”路口、“十”字路口等复杂路段,因此将“拐点”信息记录在数据存储器上显得十分重要,且能很好地进行道路匹配,而对于“拐点”之间不记录的位置信息(两拐点之间位置信息接近直线)也不会影响轨迹匹配道路。

2马尔科夫链

马尔可夫过程[5]由俄国数学家马尔可夫于1907年提出和研究的一类随机过程,至今已经成为内容丰富、理论完整、应用广泛的一门数学分支,其应用领域涉及计算机、通信、自动控制等方面。其特性为:在已知目前状态(现在)的条件下,它未来的演变(将来)不依赖于它以往的演变(过去)。高联雄等人(2009年)提出基于马尔科夫链模型去衡量公共交通网络中的关键枢纽点(hub)的重要性[6],然后推出道路转移概率和最后评价解决方案的独特性。论文[7]研究了车辆出行道路状态转移过程具有马尔科夫属性,证实该过程是一个时间齐次马尔科夫链,交通网络中车辆连续行驶的路段转移过程就是一个马尔科夫过程,并给出了车辆出行道路转移过程的马尔科夫链模型。

将交通网络中的车辆行驶所在道路看做为一个状态空间,并且汽车行驶中的道路转移过程用道路“拐点”来表示。对车辆运行的过程可以表达为连续离散时间t={i,i+1,i+2,i+3,…}的一个序列X={Pi,Pi+1,Pi+2,…},其中小写字母就是i时刻的状态,即汽车行驶所在道路经纬度信息Pi=Pi(x,y),状态空间Φ={Pi,Pi+1,Pi+2,…}.汽车所在道路对于过去状态的条件概率分布p仅是上一时刻状态的一个函数,即p={X(ti+2)|X(ti+1)=Pi+1,X(ti)=Pi}=p{X(ti+2)|X(ti+1)=Pi+2}.

3拐点算法研究

与一般公路和高速公路相比,城市交通系统中的弯道、U形转弯处、交叉路口等数量众多,交通网络错综复杂。城市交通网络是一个典型的由节点和边构成的网络,它由道路物理网络与交通需求网络的结合而形成,其中道路可以抽象为边,道路“T” 路口、“十”字路口、弯道、U形转弯处等为节点,大量的节点和边组成了交通网络构架。因此,我们根据交通系统的复杂网络特性,构建以“拐点”(节点)为记录位置点,即将马尔科夫链上的节点(“拐点”)作为记录仪存储或传输的位置点进行研究。

3.1　预处理

众所周知,汽车行驶速度都有限,高速公路一般限速120km/h(市区快速路限速80km/h)即车速最高为34m/s.目前北斗定位模块的定位精度为10m,输出定位信息频率为1Hz,汽车行驶1s,北斗定位模块在1s间隔内产生的漂移距离一般不会超过(34+10)m,定位漂移距离如超过44m就可认为无效定位数据,这样就可以将无效定位数据过滤掉。

3.2　采集车辆状态信息计算“拐点”

记录仪可以实时采集车速传感器、制动信号、左转向、右转向、近光、远光等车辆状态信息。拐点算法如下:

1) 车辆启动后,行驶开始(车辆从静止状态转变为行驶状态:速度大于0km/h且持续10s以上,可以通过采集车速传感器信号即可)后,记录第11s的位置信息作为一个拐点。

2) 正常行驶过程中,记录仪采集不到车辆的制动信号,一旦采集到制动信号(如等红灯或其它特殊情况),实时采集的车速传感器速度信号逐渐变小,记录速度保持为零(车辆从行驶状态转变为静止状态:速度等于0km/h且持续10s以上)的第11s位置信息作为一个拐点。

3) 弯道的拐角较大时(如“T”路口、“十”字路口、U形转弯处等),车辆一般会开启转向信号(左转或右转),记录仪采集到汽车转向信号,统计期间的坐标位置的平均值(也可以选取中间时间点所对应的位置)作为拐点。

4) 记录一个拐点后,车辆行驶超过60s无拐点,则记录第60s(定时报送不超过60s)的位置信息作为下一个拐点。

3.3　采集北斗定位信息计算“拐点”

目前记录仪上传信息有(t,x,y,v,θ)等,分别代表时间、纬度、经度、速率、方向角,在tis(其中1≤i≤n,n为自然数)时对应的纬度xi、经度yi、速率vi、方向角θi,即对应经纬度坐标为Pi=(xi,yi),定义拐角阈值Δθth=Δθi+l=|θi+l-θi|(2≤l≤60)为(i+l)s与is方向角之差。

对于“T”路口、“十”字路口、U形转弯处等“拐点”,拐角特性比较明显,拐角数值较大,加上采集车辆状态信息比较容易计算。对于弯道来说,拐角阈值Δθth难于认定,拐角阈值Δθth太小,则不可避免地会记录大量无用位置信息;拐角阈值Δθth太大会遗漏很多关键位置信息。道路拐角的阈值大小,显得很重要。经过多次测试比较,在本算法中:取拐角Δθth=10°,即Δθth=Δθi+l=|θi+l-θi|<10°(1≤l≤10)持续时间在10 s以上则认为直线行驶,拐角Δθi+l=|θi+l-θi|≥10°(1≤l≤3)持续时间在3 s以上则认为弯道行驶,150°<Δθi+l=|θi+l-θi|≤180 °(1≤l≤3)持续时间在3 s以上则认为掉头(如U形转弯)。

弯道的拐角较小时,此时车辆一般不会开启转向信号(左转或右转),必须根据北斗定位模块的输出信息进行相关处理,假设:1≤i≤h≤k≤n,1≤i≤h≤m≤n,根据求道路特性求拐点。具体如下:

车辆行驶后,记录仪定位并获取时间、纬度、经度、速率、方向角等信息,行驶轨迹如图1所示,若P1处记录第1个拐点T1,在第is(包括第is)之前一直保持直线行驶即Δθi=|θi-θ1|<10°,其中(2≤i≤60),在(i+1)s时记录仪采集拐角Δθi+1=|θi+1-θ1|≥10°且持续时间超过3 s,即Δθi+l=|θi+l-θ1|≥10°,其中(1≤l≤3),直线P1Pi延长至Pi′点,在(i+l)s(其中1≤l≤3)时均有Δθi+l=∠Pi′PiPi+l=|180 °-∠P1PiPi+l|≥10 °,则认为Pi为第2个拐点T2.

图1　采集北斗定位信息判断“拐点”

依据上述方法寻找第3个拐点:在第hs(包括第hs)之前一直保持直线行驶即Δθh=|θh-θi|<10°(1≤h≤60),在(j+1)s时记录仪采集拐角Δθh+1=|θh+1-θi|≥10°且持续时间超过3 s,即Δθh+l=|θh+l-θi|≥10°,其中(1≤l≤3),如图1所示,直线PiPh延长至Ph′点,在(h+l)(1≤l≤3)s时均有Δθh+l=∠Ph′PhPh+l=|180°-∠PiPhPh+l|≥10°,则认为Ph为第3个拐点T3.

以此类推,可计算出第4个拐点T4、第5个拐点T5…,直至行驶结束第m个拐点Tm.

4试验测试

对上述计算算法编写相关软件代码。车上放置两台装有北斗定位模块(组合定位模式下,定位性能与GPS模块相当)的记录仪(编号为记录仪A、记录仪B),其中一台记录仪A实时采集数据,采集频率为1Hz;另外一台记录仪B使用上述算法寻找拐点,将采集到的拐点信息并存储。两台设备进行对比测试,行车路线:海珠区(图中A处)→越秀区、天河区(图中B处)→萝岗区(图中C、D处),其中从A处开始,在B处由于处于天河区高楼密集造成短时不能定位或者定位误差较大,C处为U型转弯处,D处静止后停止采集数据。记录仪A实时采集数据,行驶3 589s,采到3 589个数据位置信息,将位置数据信息导入卫星地图,行驶轨迹如图2所示,在城市中行驶轨迹能较好的匹配道路,说明北斗定位模块定位较好,精度较好。

图2　定时1 s报送行驶轨迹图

记录仪B使用上述算法,共记录150个拐点数据,记录仪B存储空间仅为记录仪A存储空间4.2%,节省率95.8%,大大节省了存储空间或者通信费用,并将这些拐点导入到卫星地图,行驶轨迹基本能匹配道路,道路匹配特性略逊于记录仪A。此外通过多次试验结果表明,与定时1s报送相比,根据道路特性不同,可以获得不同节省率:道路较直时(拐点较少),节省率最大,理论可以达(1-1/60)×100%=98.3%;道路存在“T”路口、“十”字路口、U形转弯处时(拐点较多),节省率也可达到90%,达到了较好的效果。

5结束语

针对目前北斗卫星导航系统的大力发展以及记录仪的推广,使用国产定位效果良好的北斗双模定位模块,结合马尔科夫过程的特性,提出一种基于马尔科夫链的北斗行驶记录仪数据存储算法,对算法进行介绍、分析和推导,并通过多次实际跑车测试,测试表明:与定时1s报送或存储相比,节省率也可达到90%以上,大大节省了存储空间或者通信费用,具有较好的使用效果。

参考文献

[1]国家质量监督检验检疫总局.GB/T19056-2012 汽车行驶记录仪[S]. 中国标准出版社,2012.

[2]潘未庄，陈石平，牛明超，等.一款北斗/GPS双模定位模块设计与实现[J].全球定位系统，2014,39(2):34-38.

[3]中华人民共和国交通运输部交通运输部.JT/T794-2011道路运输车辆卫星定位系统车载终端技术要求[S].中国标准出版社，2011.

[4]交通运输部.道路运输车辆卫星定位系统北斗兼容车载终端技术规范[S].中国标准出版社,2013.

[5]毛用才,胡奇英.随机过程[M].西安:西安电子科技大学出版社,2004:101-131.

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

[7]吴迪.基于马尔科夫链的交通网络道路权重计算方法研究[D].长春:吉林大学,2011.

陈石平(1981-),男,工程师,现主要从事北斗导航产品的研究与设计。

马利滨(1967-),男,高级工程师,主要从事北斗导航产品系统与设计。

徐伟强(1985-),男,工程师，主要从事北斗导航产品软件设计。

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