基于GPS列车定位系统的快速地图匹配算法研究.pdf

2 0 1 1 年 1 1 月 第4 7卷第 1 1期 铁 道 通 信 信 号 RAI L WAY S I GNA L U NG & C 0MMU NI C A n0 N N o v e mb e r 2 0 1 1 Vo 1 ． 4 7 No ． 1 1 基于 GP S列车定位系统的 快速地图匹配算法研究 殷燕如 刘金乐 摘要：针对传统地图匹配算法计算量大，搜索速度慢的缺点，引入道路网络分块思想，综合运 用最小方向差异及铁路的连通性确定最佳 匹配路段 ，用直接投影法计算列车当前位置，并对识别 的路段设置距 离和方向条件闽值 ，进行地 图匹配的完备性检测 ，建立误 匹配的检测和修正体 系， 从而提高匹配的精度通过与传统地图匹配算法的比较，该地图匹配算法具有搜索速度快、计算 量小、耗 时少的特点，且与铁路 网络的复杂程度无关 关键词 ：列车定位 ；地 图匹配；网络分块；路段 匹配 Ab s t r a c t ：A i m a t t h e s h o r t c o mi n g s o f l a r g e c o mp u t a t i o n l o a d a n d s l o w s e a r c h i n g s p e e d o f t r a d i t i o n a l ma p ma t c h i n g a l g o r i t h ms ，a n e w me t h o d o f p a rt i t i o n i n g r o a d n e t w o r k i n t o g 打 d s i s i n t r o d u c e d ． Amo n g w h i c h t h e b e s t ma t c h i n g r o u t e s a r e d e t e r mi n e d b y b o t h t h e l e a s t d i f f e r e n c e s i n d i r e c t i o n a n d t h e c o n n e c t i v i t y o f r a i l — w a y s ，a n d t h e t r a i n g c u r r e n t p o s i t i o n s a r e c a l c u l a t e d b y d i r e c t p r o j e c t i o n me t h o d ．I n o r d e r t o i mp r o v e t h e p r e c i s i o n o f ma t c h i n g，a n mi s ma t c h d e t e c t i o n a n d c o r r e c t i o n s y s t e m w a s e s t a b l i s h e d t o c h e c k t h e c o rn— p l e t e n e s s o f ma p ma t c h i n g b y s e t t i n g t h e d i s t a n c e a n d d i r e c t i o n c o n d i t i o n t h r e s h o l d s o f t h e b e s t s e g me n t ． Co mp a r e d wi t h t h o s e t r a d i t i o n a l ma p ma t c h i n g a l g o r i t h ms ， t h i s ma p ma t c h i n g a l g o ri t h m b a sed o n d p a r - t i t i o n h a s s u c h a d v a n t a g e s a s f a s t s e a r c h，l o w c o mp u t a t i o n l o a d，a n d l e s s t i me c o n s u mp t i o n，a n d i n d e — pe n d e n c y o f t h e c o mp l e x de g r e e o f r a i l wa y n e t wo r k． Ke y wo r d s ：T r a i n l o c a t i n g；Ma p ma t c h i n g ；Gr i d p a rt i t i o n；S e g me n t ma t c h i n g 随着 G P S技术的发展 ，以及全面 向民用开放 ， 采用 G P S技术 的列车定位系统实现列车的精确定 位，是当前铁路运输发展的趋势之一。

然而，如果 没有专用仪器 或地图，即使通过 G P S获得地理经 纬度，工作人员也无法获得列车精确的位置G I S ( G e o g r a p h i c I n f o r ma t i o n s y s t e m)具 有采集 、管 理 、 分析、输出各种地理信息的能力， 并支持空间数据 的管理因此 ，在列 车定 位系统 中将 G P S与 G I S 技术结合， 用地图匹配技术进行位置修正， 是一种 减小定位误差的有效方法 1 传统算法计算量分析 目前 ，不少学者对于地图匹配提出了若干种算 法，如基于最短距离算法、相关性算法、基于模糊 逻辑算法等这些算法各有优势，但在搜索候选径 兰州交通大学自动化与电气工程学院硕士研究生， 7 3 0 0 7 0 兰州 西安铁路局安康电务段助理工程师，7 2 5 0 0 0 陕西安康 收稿日 期：2 0 1 1 - 0 8 4 3 4 —6 0 一 路时需要在整个数据库中进行搜索例如 ，二站间 有 ／7, 条线路，传统算法是计算待匹配点距所有线路 的距离，将距离最短的线路作为候选路径；再通过 计算待匹配点与候选路径上 m个路段点的距离， 选择距离最近的二点问路段作为匹配路段 ，在匹配 路段上经过插值计算得到列车位置。

由此可见 ，为 确定列车位置，传统算法至少要进行 m次距离计 算，( 2 m 一 3 )次比较和一次插值 ( 当 凡= 1 时) 当 ／／, 数量增大或 m数量增加时，其计算量增大、 搜索速度下降的问题将越发突出 针对这一问题 ，本文在传统地图匹配算法中引 人道路网络分块思想，结合铁路网特点，设计了一 种基于列车 G P S定位系统的快速地图匹配算法， 从而减少计算量，加快搜索速度，提高匹配算法的 实时性 2 网格划分及数据库的设计 网格划分是将包含候选径路的区域划分为方 格 ，其 目的是获取网格系数 ，从而进行快速索引 RAI L WAY S I GNAL L I N G ＆ C 0MMUN I C AT 1 0N Vo 1 ． 4 7 No ． 1 l 2 0 1 1 由于 G P S接收 的数据属 于大地 坐标 ，本文将 铁路网络沿经纬度进行网格化分块假设将某区域 内铁路线路划分为M× N个网格，记为 G r id ( M× N ) ，其中， M和 Ⅳ分别表示网格的行数和列数，网 格的第 i 行和第 ． U 记为 G r i d ( √ )，每个网格以其 左上角坐标作为该网格的网格系数，保存于数据库 中以便索引。

铁路线路一般为曲线，上面所划分的每个网格 只包含整条铁路线路的一部分 ，网格中所包含的这 部分铁路有可能是弯的，也有可能是直的，或者是 交叉的为了方便确定匹配路段，沿铁路线选点， 构造一系列线段 ，以直线线段逼近曲线特别是在 比较平直的线路上减少数据点的个数，在道岔口拐 弯处 等 加 大 数 据 点 的 个 数 因 此 ，每 个 网 格 G r i d ( ， )中应记录该 网格所 包含路径 的线段端点 数据、整数公里标点、道岔点等，这些点统称为标 识点 图 1为网格划分示意图 图 1 网格划分示意 图 如图 1 所示 ，该区域中有 3条线路 ，其中 2条 实线分别为 L 、L ，方 向为公里标增 大方 向；虚 线为 ，沿公里标减小方 向，用实线 与虚线 ( 即 公里标的增减 )分别代 表 了某 区间铁 路 的上下行 线路网格中的空心圆点代表沿线路设置的标识 点，实心圆点 P代表从 G P S接收机上获得的列车 位置把线路中各个标识点的属性、坐标、经纬度 及所在网格等信息记录下来 ，就构成 了整个 G I S线 路地理数据库 3 列车定位匹配算法 3 ． 1 定位匹配算法 列车定位匹配算法首先要解决匹配路段 的筛选 和识别 。

为了提高匹配正确度 ，本文对路段筛选采 用分级识别 ，以此确定 匹配路段 3 ． 1 ． 1 待匹配定位点到相应网格的快速索引 由 G P S接 收机接 收到 的数据 属于 大地坐标 ， 即经纬度先根据接收 到的定位点 P的经纬度计 算该点的网格系数， 再根据网格系数，索引到包含 P点的网格 ，即进行初级 匹配本文设置的经纬度 间隔为 0 ． 0 1 假设 ，参考区域的经纬度为 ( e ， n ) ，从 G P S接收机上获得的 P点坐标为 ( e ， n) ， 则可通过式 ( 1 )获得 P点的网格系数 ( e—e ) ／ 0 · 0 =( 一n 0 ) ／ 0 ． 0 1 应当注意的是，若 P 是第 1 个定位点或匹配算 法遇到异常 ，则候选路 段的选取必须 先 由 P找到 与其对应 的网格 G r i d ( i， ． )，然后将 与该网格相 邻的其他若干网格一并作为匹配候选 网格 ，进而将 这些候选网格包含的路段初步确定为候选路段 列车定位中匹配算法可能遇到的异常主要是指 G P S 工作不正常或输出数据不可靠，或是列车低速 行驶时产生数据漂移 ，可以根据列车行驶速度是否 出现异常来判断。

出现异常时 ，可依据列车行驶的 历史轨迹推测列车当前可能的位置 3 ． 1 ． 2 匹配路径的确定 得到 P点 的网格 系数 后 ，该 网格 中所包 含的 路径均作为 P 点的候选路径若该网格中只有 1 条 路经 ，则该路径就为匹配路径 ；若包含的路径多于 1 条 ，则需进行二级匹配本文采用最小方 向差异 原则 ，并结合历史匹配线路来确定最可能的匹配路 径 ，如图 2 ( a )所示 假设索 引到的网格 中有 3 条候选路径 S： { L ， i=1 ， 2， 3 }，3条路径的方向 记为 { ， i =1 ， 2 ， 3 }，点P为待匹配定位点，点 Q 为前一时刻的匹配点设列车的运行方向为 ，则 其方 向差为 ： Ah e a d i n g =l 一0 l ( 2 ) 图 2 ( b )给出 3条候选路径与列车运行的角 度差，根据 最小角度差异 原则，并结合历史 匹配 点，可确定 L ， 为匹配路径 3 ． 1 ． 3 列车定位点的计算 确定 了最佳匹配路径 L 】 后 ，就在 L 上寻找一 一61 一 一 一 一 一 一 一 一 ＼_l 一 ． ／ ，／ ．． _． ． ． ．． ～ ～ 一 _ _ 斗十 一 ～ ～． N 心 ¨ ．- ¨ 铁道通信信号2 0 1 1 年第 4 7卷第 1 1 期 I ?’ ． 。

_ 、 V ^ Ll ( b) 图 2 最小方 向差异原则 点作为列车的当前位置本文采用直接投影法确定 列车的当前位置 坐标匹配示意图如图 3所示 ，二 Il_j <_ ／ ： 、： ＼ 、 x B ， Y B ／ ， 、 一 t 、 、 ＼ 、 f P( X p ，Y p ) ／ ＼ 当列车行驶在 P点时 ，以点 P为圆心 ，以 G P S 测量误差为半径 ，确定 此时 P点对应的行驶路段 是 L 上的 L A B 段设路段 L 的斜率为 ，投影点 P 的 坐 标 为 ( ， ) ，则 根 据 公 式( 3) 、 ( 4 ) 、 ( 5 )可 以得到投影 点的坐标 ，即列 车当前 位置 ⋯c t a n ㈩ 舢=堕 ( 4 ) Y e o ：垫 ( 5 ) 一 + l 应当注意的是， 在实际的投影过程中，可能投 影点不段 L ，这时将 L 上距离待匹配点最 近的线段端点作为最终的线路匹配点 3 ． 2 地图匹配完备性检测 由于定位数据 、铁路网数据库多少都会存在误 差，以及算法本身的不足，使得错误匹配总是不可 一6 2 一 避免。

特别是在路段识别的过程 中，若前面匹配错 误的话将会导致后面的 配也出现错误因此需要 实时对匹配结果进行检测 ，以便及时发现错误的匹 配路段本文利用距离和方向条件检测来发现错误 匹配 设接收到的 G P S定位点坐标为 ( ， y ) ，定 位点航向为 ~ O G P S；投影点坐标为 ( x 阳， l ， P ) ，投 影所在直线段的方向为 ，则距离检测公式和方 向条件检测公式分别为 d =~ ／ ( X P —X P 0 ) +( P — P 0 ) ≤D ( 6 ) i=C O S ( q ~ c P S一 )≤ ( 7 ) 其中D ， 是距离检测阈值， 为方向条件检测阈值 具体实现时，先进行距离检测和方向检测只 要有一个条件未通过时 ，则判定匹配错误 ，此时重 新进行线路识别 ，并对此次匹配的前面的定位点在 新的识别路段上重新进行匹配匹配算法的执行步 骤如下 1 ．接收 G P S定位数据 2 ．判断定位数据是否有效 ，若无效删除 ，重 新接收 3 ．根据 G P S 定位数据计算其 网格系数并索引 至网格 ，即进行初级匹配 4 ．判断网格 中的候选路径数 目，若 唯一 ，则 直接将其作为匹配路径，然后转第 6 步。

5 ．用最小方 向差异原则及连接性拓扑检查进 行二级匹配 ，确定匹配路径 6 ．计算列车定位点 7 ．进行地图匹配完备性检测结束本次匹配 4 快速匹配算法计算量分析 在前面已经分析过传统算法的计算量，若二站 间只有 1条线路 (n =1 ) ，该线路 上的标 识点个 数为 m个 ，则需要进行 m次距离计算 ，( 2 m 一 3 ) 次距离比较和一次插值才能得到列车位置从快速 匹配算法步骤中可以看出，当 凡=1时，快速地图 匹配算法只需要进行 2 次计算就可以得到列车位置 ( 一次为计算网格系数，一次为计算投影点位置) 若二站间的线路数大于 1条，传统算法 的计算量还 要增加，快速匹配算法则需增加夹角计算和比较 一般情况下 ／7 , 不会大于 4，那么最多会增加 4次夹 角计算量和6次夹角量比较 ( 下转第7 6 页) 一 、、 ～ 、 ● 、 ●～ 一 - 、、▲、 、 、、、 、、 ～ 、 铁道通信信号2 0 1 1 年第 4 7卷第 1 1 期 2 2 0 V 交流 电源 电源检测信 电源设各检 号拾取设备 测汇聚设备 图3 在红外线机房增设电源监控检测设备 源是否正常，正常则可能是通信通道或红外线设备 有故障。

红外线中心也可向通信段提出申请 ， 建立 自己的电源监控中心，这样就可以随时通知电力工 区和通信部门进行抢修处理 解决方案 4 可 以 将 方 案 2和 方 案 3同 时 使 用 ， 效 果 会 更好 随着铁路改造和新线的建设，红外线的通信通 道已经光纤化 ，终端连接采用 2 Mb ／ s 线路 ，只要 选 择2 条2 Mb ／ S 线 路 ， 在 其 中的红 外线通 道 相关 时隙及发送设备中设计此功能电路，就 可通过红外线中心的检测设备实现通道 远程诊断同样 T D C S 、微 机监测及 电 力远动系统通道的远程诊断均可采用此 方法 在原有地区电缆线路 的基础上增设 1条 光 缆 线 路 ，红 外 线 检 测 设 备 用 2 Mb ／ s 接 口连接 ；联 系 用实 回线 连接 此方案简单易行 ，对于全路红外 线设备抢修极为重要 ，产生的效益也是 可观的，但方案牵扯到红外线设备及通 信传输室、通信工区，在考虑行车安全的前提下， 需要相关部门配合实施 参考文献 [ 1 ] 王毅， 魏元玲 ． T D C S网络通道间断故障分析及排除 [ J ] ．铁道通信信号， 2 0 1 0 ( 1 ) ： 5 5 ． [ 2 ] 赵艳 ， 许锦江 ． T D C S车站设备数据传输故障的探讨 [ J ] ．铁道通信信号， 2 0 1 0 ( 2 ) ： 5 5 ． [ 3 ] 陈靖 ．开展双路由保护， 确保铁路业务网络安全畅通 [ J ] ．铁道通信信号， 2 0 1 0 ( 4 ) ： 7 2 ． [ 4 ] 李红 ． 浅谈传输 中存在的典型误码故障处理[ J ] ．铁 道通信信号 ， 2 0 1 0 ( 8 ) ： 8 3 ． [ 5 ] 范春妍 ． 小交换用户话机自振铃问题处理 [ J ] ．铁道 通信信号， 2 0 1 0 ( 1 1 ) ： 7 5 ． ( 责任编辑：诸红) ( 上接第 6 2页) 从 2种算法的计算量理论分析比较中可以看 出，快速匹配算法能提高搜索速度、减少计算量。

需要说 明的是 ，本文只是提 出了一种理论 的可能 性 ，实践中的各种问题还需要根据具体情况进行研 究分析 5 结论 本文 以现有地图匹配算法为基础，结合列车运 行特点 ，引入了道路 网络分块的思想 ，在初级匹配 时提高了搜索径路速度，解决了传统匹配算法计算 量大、耗时长的缺点 ；并充分利用 了列车运动的连 续特性、实际路网的拓扑特性，以及列车定位点的 投影距离和方向夹角信息， 筛选路段信息，简化了 匹配算法， 建立了地图匹配完备性模型，提高了地 图匹配的正确率通过对算法计算量进行的理论分 析可知，快速匹配算法与传统算法相比，更能快 速 、有效 、准确地辅助列车定位 ，因此具有一定的 参考价值 参考文献 [ 1 ] 邬伦， 刘瑜， 马修军等． 地理信息系统——原理， 方法 和应用[ M] ． 北京： 科学出版社 ， 2 0 0 5 ． [ 2 ] K i m S ， K i m J H ．A d a p t i v e f u z z y — n e t w o r k — b a s e d C— me a s u r e ma p ma t c h i n g a l g o r i t h m f o r N a v i g a t i o n s y s t e m [ J ] ．I E E E T r a m O R I E ， 2 0 0 1 ． [ 3 ] 常菲， 浦争艳 ， 李明禄， 等． 综合地图匹配定位技术研 究[ J ] ． 计算机工程与应用， 2 0 0 4， 1 9 ： 2 0 0— 2 0 2 ． [ 4 ] 彭飞， 柳重堪， 张其善． 基于模糊逻辑 的 G P S ／ D R组合 导航系统地图匹配算法[ J ] ． 遥测遥控， 2 0 0 1 ， 2 2 ( 1 ) ： 3 2—3 6 ． [ 5 ] 付梦印， 李杰， 邓志红． 一种适于车辆导航系统的快速 地图匹配算法[ J ] ． 北京理工大学学报， 2 0 0 5 ， 2 5( 3 ) ： 2 2 5—2 2 9 ． ( 责任编辑：诸红) 。