本发明涉及高速车辆定位技术领域，特别指一种基于手机信令路网匹配的高速车辆位置识别方法。
背景技术：
随着我国城市化建设的不断发展，高速路网的智慧科学化运营越来越受到关注，目前高速路网上车辆位置的识别，主要通过路边固定的检测器进行数据采集，或者通过车载全球定位系统进行数据采集，存在成本高、需要大量人力维护、采集的数据有一定局限性等的缺陷。对高速车辆进行位置识别后，还需要利用地图匹配算法将识别的位置匹配到地图上的方法。
传统上存在如下几种地图匹配算法：
1、基于几何分析的地图匹配算法，利用高速路网的空间几何信息，仅仅考虑高速路网的形状，将所有待匹配定位点或将定位点连接成曲线轨迹点，然后在高速路网中搜索最相似的路段作为匹配路段。但是，该算法忽略路段彼此间的连通性，受高速路网上节点密度及分布影响，当某个gps点的匹配错误可能会引起一系列的错误匹配，在复杂路况下容易造成错误识别，算法稳定性较差。
2、基于拓扑分析的地图匹配算法，全面分析前进方向、速度和道路网连通性等信息，基于道路网拓扑关系，通过历史匹配信息对实际高速路网信息进行模式判别。假定某一时间点车辆行驶在道路路段a上，考虑道路连通性、车速等条件，在随后时间点，车辆仅可能行驶在道路路段b、c、d上，不可能行驶在道路路段e、f上。但是，该算法易受道路网拓扑关系质量的影响，如果空间拓扑关系范围大且复杂，其匹配性能将下降。
3、基于概率统计的地图匹配算法，给每个gps样本点设定一个椭圆或矩形的置信区域，并根据gps的点在置信区域内的位置之间的距离获得概率值，根据概率值的大小来决定最佳匹配路径。但是，该算法计算开销大，满足不了实时性和大众对gps系统的要求。
4、高级路网匹配算法，采用先进的技术手段，例如使用卡尔曼滤波、模糊逻辑模型、隐式马尔科夫模型等，这些高级路网匹配算法的准确率普遍较高，例如基于贝叶斯推理的匹配算法，使用多假设技术，为置信区域内所有路段产生伪测量值，路网拓扑分析(连接，方向和道路设计参数)与伪测量值一起被用来为每个车辆推导出一组假设及概率值。但是，该算法是基于初始匹配的方法，初始输入的值很大程度影响随后匹配的性能，存在错匹配的可能性，受复杂路网、采样率等影响因素较大，仍然表现不佳。
因此，如何提供一种基于手机信令路网匹配的高速车辆位置识别方法，实现提升高速车辆位置识别的准确度以及稳定性，降低识别成本，成为一个亟待解决的问题。
技术实现要素：
本发明要解决的技术问题，在于提供一种基于手机信令路网匹配的高速车辆位置识别方法，实现提升高速车辆位置识别的准确度以及稳定性，降低识别成本。
本发明是这样实现的：一种基于手机信令路网匹配的高速车辆位置识别方法，包括如下步骤：
步骤s10、获取路测车的车载终端在目标路段行驶时的行车轨迹、基站信息以及信令序列集a；
步骤s20、基于所述行车轨迹以及基站信息对信令序列集a进行清洗，得到信令序列集b；
步骤s30、基于所述行车轨迹对信令序列集b进行同方向的两两组合，得到正向序列组和逆向序列组；
步骤s40、利用needleman-wunsch算法，从所述正向序列组和逆向序列组中分别找出正向最长公共子序列和逆向最长公共子序列；
步骤s50、利用动态规划算法，从所述正向最长公共子序列和逆向最长公共子序列中分别找出最短公共超序列，进而得到正向经纬度切换序列z和逆向经纬度切换序列n；
步骤s60、获取用户终端的信令序列集c，对所述信令序列集c进行清洗后得到信令序列集d，基于所述信令序列集d得到经纬度切换序列q；
步骤s70、将所述经纬度切换序列q分别与正向经纬度切换序列z和逆向经纬度切换序列n进行轨迹相似度计算，得到用户终端的实时位置；
步骤s80、基于所述基站信息将实时位置匹配到目标路段上。
进一步地，所述步骤s10中，所述行车轨迹包括正向行车轨迹以及逆向行车轨迹；所述基站信息至少包括基站名称以及经纬度；所述信令序列集a包括车载终端在目标路段上接收到信号的各信令以及各信令对应的基站名称，各所述基站名称基于信令的切换时间进行顺序排序。
进一步地，所述步骤s20具体为：
基于所述行车轨迹以及基站信息对信令序列集a进行包括连续点剔重、aba切换以及飘远点剔除的清洗，得到信令序列集b；
所述信令序列集b的正向切换序列为z(1,p){x1,x2,...,xp}，逆向切换序列为n(m,1){xm,xm-1,...,x1}；其中xp和xm均表示基站，p和m均表示基站的编号，且均为正整数。
进一步地，所述步骤s30具体为：
基于正向行车轨迹对信令序列集b进行两两组合得到正向序列组{(z1,z2),(z1,z3),...,(zi,zj)}，基于逆向行车轨迹对信令序列集b进行两两组合得到逆向序列组{(n1,n2),(n1,n3),...,(ni,nj)}；其中i和j均为正整数，且i＜j；zi表示第i个正向切换序列，zj表示第j个正向切换序列，ni表示第i个逆向切换序列，nj表示第j个逆向切换序列。
进一步地，所述步骤s40具体为：
利用needleman-wunsch算法，从所述正向序列组中找出正向最长公共子序列lcs(zi,zj)，从所述逆向序列组中找出逆向最长公共子序列lcs(ni,nj)。
进一步地，所述步骤s50具体为：
利用动态规划算法，从所述正向最长公共子序列找出最短公共超序列scs(lcs(z1,z2),lcs(z1,z3),...,lcs(zi,zj))，进而得到正向经纬度切换序列z；从所述逆向最长公共子序列找出最短公共超序列scs(lcs(n1,n2),lcs(n1,n3),...,lcs(ni,nj))，进而得到逆向经纬度切换序列n。
进一步地，所述步骤s60具体为：
获取用户终端的信令序列集c，对所述信令序列集c进行包括连续点剔重、aba切换以及飘远点剔除的清洗后得到信令序列集d，基于所述信令序列集d得到经纬度切换序列q。
进一步地，所述步骤s70具体为：
设定一相似度阈值δ；将所述经纬度切换序列q与正向经纬度切换序列z进行轨迹相似度计算：
将所述经纬度切换序列q与逆向经纬度切换序列n进行轨迹相似度计算：
其中sim(z,q)表示正向相似度，sim(n,q)表示逆向相似度；
当sim(z,q)＞δ且sim(z,q)＞sim(n,q)时，搭载用户终端的车辆为正向行驶，将当前接收信令对应基站的经纬度作为用户终端的实时位置；
当sim(n,q)＞δ且sim(n,q)＞sim(z,q)时，搭载用户终端的车辆为逆向行驶，将当前接收信令对应基站的经纬度作为用户终端的实时位置；
当sim(z,q)＝sim(n,q)＞δ时，无法判断搭载用户终端的车辆的行驶方向，将当前接收信令对应基站的经纬度作为用户终端的实时位置；
当sim(z,q)＜δ或者sim(n,q)＜δ时，剔除相应数据。
进一步地，所述步骤s80具体为：
基于所述基站信息的经纬度确定实时位置，并通过欧氏距离计算所述实时位置与目标路段的距离，进而将所述实时位置匹配到目标路段上。
本发明的优点在于：
1、通过路测车的信令序列集构造正向经纬度切换序列z和逆向经纬度切换序列n，相对于通过距离圈选基站，道路基站的采样率更高，后期再融入用户终端的信令序列集，持续迭代优化正向经纬度切换序列z和逆向经纬度切换序列n，降低了路测车信令序列集的异常影响，进而极大的提升了高速车辆位置识别的稳定性。
2、通过needleman-wunsch算法计算两两序列间的最长公共子序列，使训练集信息利用率最大化，再利用动态规划算法从最长公共子序列中求解最短公共超序列，由于最短公共超序列包含所有序列组中的公共子序列关系，极大的提升了正向经纬度切换序列z和逆向经纬度切换序列n的覆盖率和准确度。
3、通过计算经纬度切换序列q与正向经纬度切换序列z和逆向经纬度切换序列n的轨迹相似度，即评估用户终端的轨迹与经纬度切换序列的相似度，采用needleman-wunsch算法将较为复杂的地图匹配算法转换成数据挖掘中的序列比对算法，比较两个给定序列(文本)之间的差异，降低了计算成本，由于初始输入值仅有经纬度切换序列，序列之间是相互独立的，降低了初始输入值的影响，削弱了随后匹配的影响，极大的提升了稳定性。
4、通过信令来匹配的高速车辆位置，相对于利用路边固定的检测器或者通过车载全球定位系统，建设维护成本低、实施部署周期短、数据获取实时性高，易于实现全路网的高速车辆的识别监测。
附图说明
下面参照附图结合实施例对本发明作进一步的说明。
图1是本发明一种基于手机信令路网匹配的高速车辆位置识别方法的流程图。
图2是本发明正向经纬度切换序列z的效果示意图。
图3是本发明信令序列集清洗的对比图。
具体实施方式
本申请实施例中的技术方案，总体思路如下：首先，通过对目标路段进行大量路测，对获取的信令序列集进行分析，采用needleman-wunsch算法进行正向经纬度切换序列z和逆向经纬度切换序列n的识别；其次，从运营商获取用户终端的信令序列集c，进行连续点剔重、aba切换以及飘远点剔除的清洗后，得到信令序列集d；再次，根据道路匹配算法及轨迹相似度对用户终端进行识别和区分，筛选出在目标路段不同方向上移动的用户终端；最后，根据实时位置与目标路段的对应关系，将用户终端实时状态下所在的实时位置匹配在目标路段上，实现用户终端(高速车辆)与目标路段的对应。
请参照图1至图3所示，本发明一种基于手机信令路网匹配的高速车辆位置识别方法的较佳实施例，包括如下步骤：
步骤s10、获取路测车的车载终端在目标路段行驶时的行车轨迹、基站信息以及信令序列集a；
步骤s20、基于所述行车轨迹以及基站信息对信令序列集a进行清洗，得到信令序列集b；
例如路测车刚进入目标路段时，接收到基站a1的信令，离开目标路段时，接收到基站an的信令，则信令序列集a为a1→a2→...→an；对信令序列集a进行清洗后，得到信令序列集b：b1→b2→...→bn。
步骤s30、基于所述行车轨迹对信令序列集b进行同方向的两两组合，得到正向序列组和逆向序列组；
步骤s40、利用needleman-wunsch算法，从所述正向序列组和逆向序列组中分别找出正向最长公共子序列和逆向最长公共子序列；
步骤s50、利用动态规划算法，从所述正向最长公共子序列和逆向最长公共子序列中分别找出包含所有序列组中的公共子序列关系的最短公共超序列，进而得到正向经纬度切换序列z和逆向经纬度切换序列n；
步骤s60、获取用户终端的信令序列集c，对所述信令序列集c进行清洗后得到信令序列集d，基于所述信令序列集d得到经纬度切换序列q；具体实施时，可同时获取距离基站预设半径范围内的信令，对多个用户终端同时进行位置识别；由于所述信令序列集c存在大量噪音，因此需要进行清洗，清洗后每个用户终端仅保留当前时刻最近10个位置点构造经纬度切换序列；
步骤s70、将所述经纬度切换序列q分别与正向经纬度切换序列z和逆向经纬度切换序列n进行轨迹相似度计算，得到用户终端的实时位置；
步骤s80、基于所述基站信息将实时位置匹配到目标路段上。
所述步骤s10中，所述行车轨迹包括正向行车轨迹以及逆向行车轨迹；所述基站信息至少包括基站名称以及经纬度；所述信令序列集a包括车载终端在目标路段上接收到信号的各信令以及各信令对应的基站名称，各所述基站名称基于信令的切换时间进行顺序排序。
所述步骤s20具体为：
基于所述行车轨迹以及基站信息对信令序列集a进行包括连续点剔重、aba切换以及飘远点剔除的清洗，得到信令序列集b；
所述信令序列集b的正向切换序列为z(1,p){x1,x2,...,xp}，逆向切换序列为n(m,1){xm,xm-1,...,x1}；其中xp和xm均表示基站，p和m均表示基站的编号，且均为正整数。所述正向切换序列即路测车在目标路段由起点至终点的序列，逆向切换序列即路测车在目标路段由终点至起点的序列。
所述步骤s30具体为：
基于正向行车轨迹对信令序列集b进行两两组合得到正向序列组{(z1,z2),(z1,z3),...,(zi,zj)}，基于逆向行车轨迹对信令序列集b进行两两组合得到逆向序列组{(n1,n2),(n1,n3),...,(ni,nj)}；其中i和j均为正整数，且i＜j；zi表示第i个正向切换序列，zj表示第j个正向切换序列，ni表示第i个逆向切换序列，nj表示第j个逆向切换序列。
所述步骤s40具体为：
利用needleman-wunsch算法，从所述正向序列组中找出正向最长公共子序列lcs(zi,zj)，从所述逆向序列组中找出逆向最长公共子序列lcs(ni,nj)。
needleman-wunsch算法的基本思想是：当匹配两个序列时，找出这两个序列中都存在，并且最长的子序列，子序列的元素不需要连续出现，但出现顺序一致，如序列x＝{p1,p2,p3,p4},y＝{p1,p3,p2}，那么其公共子序列为{p1,p3}。作为序列比对的基础算法，needleman-wunsch算法用于对全局范围内动态寻求最长公共子序列。
令x＝{x1,x2,...,xm}，y＝{y1,y2,...,yn}为两个序列，z＝{z1,z2,...,zk}为x和y的任意lcs。
如果xm＝yn，则zk＝xm＝yn且zk-1是xm-1和yn-1的一个lcs。
如果xm≠yn，那么zk≠xm，意味着z是xm-1和y的一个lcs。
如果xm≠yn，那么zk≠yn，意味着z是x和yn-1的一个lcs。
可以看出，两个序列的lcs问题包含两个序列前缀的lcs，因此lcs问题具有最优子结构性质。在设计递归算法时，递归算法具有子问题重叠的性质。
设c[i,j]表示xi和yj的最长公共子序列lcs的长度。如果i＝0或j＝0，即一个序列长度为0时lcs的长度为0，根据lcs问题的最优子结构性质，可得如下公式：
在求最长公共子序列的过程中，needleman-wunsch算法是在以上递归关系的基础上，对待匹配序列中每一个元素进行比对，通过建立基于lenlcs评分矩阵来表示序列匹配长度，然后更新矩阵元素，最终利用回溯求得最长公共子序列lcs。
所述步骤s50具体为：
利用动态规划算法，从所述正向最长公共子序列找出最短公共超序列scs(lcs(z1,z2),lcs(z1,z3),...,lcs(zi,zj))，进而得到正向经纬度切换序列z；从所述逆向最长公共子序列找出最短公共超序列scs(lcs(n1,n2),lcs(n1,n3),...,lcs(ni,nj))，进而得到逆向经纬度切换序列n。
所述步骤s60具体为：
获取用户终端的信令序列集c，对所述信令序列集c进行包括连续点剔重、aba切换以及飘远点剔除的清洗后得到信令序列集d，基于所述信令序列集d得到经纬度切换序列q。
连续点剔重即针对同一用户终端的信令按时间排序，对连续的同一个位置出现的多条信令进行合并，仅保留第一条信令。
aba切换即针对同一用户终端按时间排序的信令，在两个位置(位置a、位置b)之间来回切换时(比如：aba切换)，对一个aba切换组，仅保留第一条信令。
飘远点剔除即根据三角关系或余弦30度规则进行漂移位置识别，识别用户终端的信令中信号漂移位置点，将漂移位置点作为异常位置点过滤掉。
所述步骤s70具体为：
设定一相似度阈值δ；将所述经纬度切换序列q与正向经纬度切换序列z进行轨迹相似度计算：
将所述经纬度切换序列q与逆向经纬度切换序列n进行轨迹相似度计算：
其中sim(z,q)表示正向相似度，sim(n,q)表示逆向相似度；
当sim(z,q)＞δ且sim(z,q)＞sim(n,q)时，搭载用户终端的车辆为正向行驶，将当前接收信令对应基站的经纬度作为用户终端的实时位置；
当sim(n,q)＞δ且sim(n,q)＞sim(z,q)时，搭载用户终端的车辆为逆向行驶，将当前接收信令对应基站的经纬度作为用户终端的实时位置；
当sim(z,q)＝sim(n,q)＞δ时，无法判断搭载用户终端的车辆的行驶方向，将当前接收信令对应基站的经纬度作为用户终端的实时位置；
当sim(z,q)＜δ或者sim(n,q)＜δ时，剔除相应数据。
所述步骤s80具体为：
基于所述基站信息的经纬度确定实时位置，并通过欧氏距离计算所述实时位置与目标路段的距离，进而将所述实时位置匹配到目标路段上。
综上所述，本发明的优点在于：
1、通过路测车的信令序列集构造正向经纬度切换序列z和逆向经纬度切换序列n，相对于通过距离圈选基站，道路基站的采样率更高，后期再融入用户终端的信令序列集，持续迭代优化正向经纬度切换序列z和逆向经纬度切换序列n，降低了路测车信令序列集的异常影响，进而极大的提升了高速车辆位置识别的稳定性。
2、通过needleman-wunsch算法计算两两序列间的最长公共子序列，使训练集信息利用率最大化，再利用动态规划算法从最长公共子序列中求解最短公共超序列，由于最短公共超序列包含所有序列组中的公共子序列关系，极大的提升了正向经纬度切换序列z和逆向经纬度切换序列n的覆盖率和准确度。
3、通过计算经纬度切换序列q与正向经纬度切换序列z和逆向经纬度切换序列n的轨迹相似度，即评估用户终端的轨迹与经纬度切换序列的相似度，采用needleman-wunsch算法将较为复杂的地图匹配算法转换成数据挖掘中的序列比对算法，比较两个给定序列(文本)之间的差异，降低了计算成本，由于初始输入值仅有经纬度切换序列，序列之间是相互独立的，降低了初始输入值的影响，削弱了随后匹配的影响，极大的提升了稳定性。
4、通过信令来匹配的高速车辆位置，相对于利用路边固定的检测器或者通过车载全球定位系统，建设维护成本低、实施部署周期短、数据获取实时性高，易于实现全路网的高速车辆的识别监测。
虽然以上描述了本发明的具体实施方式，但是熟悉本技术领域的技术人员应当理解，我们所描述的具体的实施例只是说明性的，而不是用于对本发明的范围的限定，熟悉本领域的技术人员在依照本发明的精神所作的等效的修饰以及变化，都应当涵盖在本发明的权利要求所保护的范围内。
1.一种基于手机信令路网匹配的高速车辆位置识别方法，其特征在于：包括如下步骤：
步骤s10、获取路测车的车载终端在目标路段行驶时的行车轨迹、基站信息以及信令序列集a；
步骤s20、基于所述行车轨迹以及基站信息对信令序列集a进行清洗，得到信令序列集b；
步骤s30、基于所述行车轨迹对信令序列集b进行同方向的两两组合，得到正向序列组和逆向序列组；
步骤s40、利用needleman-wunsch算法，从所述正向序列组和逆向序列组中分别找出正向最长公共子序列和逆向最长公共子序列；
步骤s50、利用动态规划算法，从所述正向最长公共子序列和逆向最长公共子序列中分别找出最短公共超序列，进而得到正向经纬度切换序列z和逆向经纬度切换序列n；
步骤s60、获取用户终端的信令序列集c，对所述信令序列集c进行清洗后得到信令序列集d，基于所述信令序列集d得到经纬度切换序列q；
步骤s70、将所述经纬度切换序列q分别与正向经纬度切换序列z和逆向经纬度切换序列n进行轨迹相似度计算，得到用户终端的实时位置；
步骤s80、基于所述基站信息将实时位置匹配到目标路段上。
2.如权利要求1所述的一种基于手机信令路网匹配的高速车辆位置识别方法，其特征在于：所述步骤s10中，所述行车轨迹包括正向行车轨迹以及逆向行车轨迹；所述基站信息至少包括基站名称以及经纬度；所述信令序列集a包括车载终端在目标路段上接收到信号的各信令以及各信令对应的基站名称，各所述基站名称基于信令的切换时间进行顺序排序。
3.如权利要求1所述的一种基于手机信令路网匹配的高速车辆位置识别方法，其特征在于：所述步骤s20具体为：
基于所述行车轨迹以及基站信息对信令序列集a进行包括连续点剔重、aba切换以及飘远点剔除的清洗，得到信令序列集b；
所述信令序列集b的正向切换序列为z(1,p){x1,x2,...,xp}，逆向切换序列为n(m,1){xm,xm-1,...,x1}；其中xp和xm均表示基站，p和m均表示基站的编号，且均为正整数。
4.如权利要求1所述的一种基于手机信令路网匹配的高速车辆位置识别方法，其特征在于：所述步骤s30具体为：
基于正向行车轨迹对信令序列集b进行两两组合得到正向序列组{(z1,z2),(z1,z3),...,(zi,zj)}，基于逆向行车轨迹对信令序列集b进行两两组合得到逆向序列组{(n1,n2),(n1,n3),...,(ni,nj)}；其中i和j均为正整数，且i＜j；zi表示第i个正向切换序列，zj表示第j个正向切换序列，ni表示第i个逆向切换序列，nj表示第j个逆向切换序列。
5.如权利要求1所述的一种基于手机信令路网匹配的高速车辆位置识别方法，其特征在于：所述步骤s40具体为：
利用needleman-wunsch算法，从所述正向序列组中找出正向最长公共子序列lcs(zi,zj)，从所述逆向序列组中找出逆向最长公共子序列lcs(ni,nj)。
6.如权利要求1所述的一种基于手机信令路网匹配的高速车辆位置识别方法，其特征在于：所述步骤s50具体为：
利用动态规划算法，从所述正向最长公共子序列找出最短公共超序列scs(lcs(z1,z2),lcs(z1,z3),...,lcs(zi,zj))，进而得到正向经纬度切换序列z；从所述逆向最长公共子序列找出最短公共超序列scs(lcs(n1,n2),lcs(n1,n3),...,lcs(ni,nj))，进而得到逆向经纬度切换序列n。
7.如权利要求1所述的一种基于手机信令路网匹配的高速车辆位置识别方法，其特征在于：所述步骤s60具体为：
获取用户终端的信令序列集c，对所述信令序列集c进行包括连续点剔重、aba切换以及飘远点剔除的清洗后得到信令序列集d，基于所述信令序列集d得到经纬度切换序列q。
8.如权利要求1所述的一种基于手机信令路网匹配的高速车辆位置识别方法，其特征在于：所述步骤s70具体为：
设定一相似度阈值δ；将所述经纬度切换序列q与正向经纬度切换序列z进行轨迹相似度计算：
将所述经纬度切换序列q与逆向经纬度切换序列n进行轨迹相似度计算：
其中sim(z,q)表示正向相似度，sim(n,q)表示逆向相似度；
当sim(z,q)＞δ且sim(z,q)＞sim(n,q)时，搭载用户终端的车辆为正向行驶，将当前接收信令对应基站的经纬度作为用户终端的实时位置；
当sim(n,q)＞δ且sim(n,q)＞sim(z,q)时，搭载用户终端的车辆为逆向行驶，将当前接收信令对应基站的经纬度作为用户终端的实时位置；
当sim(z,q)＝sim(n,q)＞δ时，无法判断搭载用户终端的车辆的行驶方向，将当前接收信令对应基站的经纬度作为用户终端的实时位置；
当sim(z,q)＜δ或者sim(n,q)＜δ时，剔除相应数据。
9.如权利要求1所述的一种基于手机信令路网匹配的高速车辆位置识别方法，其特征在于：所述步骤s80具体为：
基于所述基站信息的经纬度确定实时位置，并通过欧氏距离计算所述实时位置与目标路段的距离，进而将所述实时位置匹配到目标路段上。
技术总结