一种VRS最优格网点快速查找方法及系统与流程

一种vrs最优格网点快速查找方法及系统
技术领域
1.本发明涉及卫星导航技术领域，尤其涉及一种vrs最优格网点快速查找方法及系统。


背景技术：

2.目前国内各个省都有提供基于vrs技术的cors服务，也就是为接入的定位终端提供一个附近的虚拟参考站进行差份定位。为了满足海量用户的需求，部分地区的cors服务将采取提前生成格网化的vrs数据，保存在系统中，并进行实时更新，当定位终端接入时，提供满足需求的格网点。一般选取的格网点是最近的格网点，这样就需要将定位终端的上传坐标和格网点坐标进行一一比对来找到最近的格网点。
3.cors服务中格网点的数量很大，一般10km一个格网点，一个地区的格网点可能多达上万。定位终端实时定位时，cors服务根据数据坐标一一比对，十分耗时。当定位规模逐渐增长时，服务系统每次进行的比对的时间复杂度将会达到o(格网点数量*定位终端数量)，将会影响到服务系统的服务能力和质量。


技术实现要素：

4.针对现有技术存在的问题，本发明提供一种vrs最优格网点快速查找方法及系统，针对最优格网点查询进行优化，在牺牲少量存储的情况下，单个定位终端匹配坐标的时间复杂度达到o(1)，不随着格网点增长而增长。
5.为达到上述目的，本发明提供了一种vrs最优格网点快速查找方法，包括：
6.生成指定地区的vrs格网点坐标列表，各个格网点之间间距为5～10km；
7.对所有所述vrs格网点的坐标进行转换以二维坐标投影至坐标系格子中；
8.每个坐标系格子作为一个哈希桶，采用链表连接各个坐标系格子；
9.根据用户终端上传的纬度、经度和高程坐标，计算得到对应的坐标系格子，根据得到对应坐标系格子，查找链表找到有效的坐标系格子；
10.有效的坐标系格子对应的vrs格网点中选择最优格网点，将所述最优格网点的坐标返回给用户终端。
11.进一步地，坐标进行转换，包括把xyz地固坐标转换为大地坐标系blh。
12.进一步地，以二维坐标投影至坐标系格子中，包括坐标系格子二维坐标(x,y)＝f(b,l)：
13.x＝(l
–
minl)/scale_x
14.y＝(b
–
minb)/scale_y
15.其中，b为纬度值，l为经度值，minl为vrs格网点中经度值的最小值，minb为vrs格网点中纬度值的最小值，scale_x为经度方向划分坐标系格子的间距，scale_y为纬度方向划分坐标系格子的间距。
16.进一步地，根据用户终端上传的纬度b、经度l和高程h计算二维坐标(x0,y0)；
17.根据二维坐标(x0,y0)以及用户终端上传的时间，查找链表找到有效的坐标系格子，包括：
18.根据坐标系格子的间距，计算空间上距离二维坐标(x0,y0)距离dis满足距离阈值要求的坐标系格子,作为有效坐标系格子；一个坐标系格子里面包含若干格网点，每个格网点都存在一个更新时间。
19.进一步地，选择最优格网点包括：
20.对有效的坐标系格子内的每个格网点计算综合值：
21.d(st)＝dis dis(t)
22.dis是用户终端上传的坐标到该格网点的距离；
23.dis(t)是该格网点的更新时间与用户终端上传的时间t0的时间差换算成的距离；
24.选择d(st)最小时对应的vrs格网点作为最优格网点。
25.另一方面提供一种vrs最优格网点快速查找系统，包括：
26.vrs格网点坐标列表生成模块，生成指定地区的vrs格网点坐标列表，各个格网点之间间距为5～10km；
27.坐标系格子生成模块，对所有所述vrs格网点的坐标进行转换以二维坐标投影至坐标系格子中；
28.链表生成模块，每个坐标系格子作为一个哈希桶，采用链表连接各个坐标系格子；
29.有效的坐标系格子查找模块，根据用户终端上传的纬度、经度和高程坐标，计算得到对应的坐标系格子，根据得到对应坐标系格子以及用户终端上传的时间，查找链表找到有效的坐标系格子；
30.最优格网点输出模块，由有效的坐标系格子对应的vrs格网点中选择最优格网点，将所述最优格网点的坐标返回给用户终端。
31.进一步地，坐标系格子生成模块进行坐标进行转换包括：把xyz地固坐标转换为大地坐标系blh。
32.进一步地，坐标系格子生成模块，生成坐标系格子二维坐标(x,y)＝f(b,l)：
33.x＝(l
–
minl)/scale_x
34.y＝(b
–
minb)/scale_y
35.其中，b为纬度值，l为经度值，minl为vrs格网点中经度值的最小值，minb为vrs格网点中纬度值的最小值，scale_x为经度方向划分坐标系格子的间距，scale_y为纬度方向划分坐标系格子的间距。
36.进一步地，有效的坐标系格子查找模块，根据用户终端上传的纬度b、经度l和高程h计算二维坐标(x0,y0)；
37.根据二维坐标(x0,y0)以及用户终端上传的时间，查找链表找到有效的坐标系格子，包括：
38.根据坐标系格子的间距，计算空间上距离二维坐标(x0,y0)距离dis满足距离阈值要求的坐标系格子,作为有效坐标系格子；一个坐标系格子里面包含若干格网点，每个格网点都存在一个更新时间。
39.进一步地，最优格网点输出模块，选择最优格网点包括：
40.对有效的坐标系格子内的每个格网点计算综合值：
41.d(st)＝dis dis(t)
42.dis是用户终端上传的坐标到该格网点的距离；
43.dis(t)是该格网点的更新时间与用户终端上传的时间t0的时间差换算成的距离；
44.选择d(st)最小时对应的vrs格网点作为最优格网点。
45.本发明的上述技术方案具有如下有益的技术效果：
46.(1)本发明针对最优格网点查询进行优化，在牺牲少量存储的情况下，单个定位终端匹配坐标的时间复杂度达到o(1)，不随着格网点增长而增长。查找最优格网点速度快。节省时间和格网点数目有关，对于1000个格网点，传统的暴力比较平均需要500次比较，而本发明的比较方式平均需要10次比较，效率提高了50倍。
47.(2)随着目前物联网、无人驾驶等技术的发展，实时定位的终端数目将会越来越多，cors服务作为目前卫星导航方面成熟度和精度最高的技术之一，受到的需求越来越高。cors服务系统在海量终端接入时，查询最优格网点的速度决定了系统的服务能力。采用本发明的vrs最优格网点快速查找方式，提高了cors服务系统的服务能力。
附图说明
48.图1是用户终端cors接入的流程图；
49.图2是vrs格网点生成示意图；
50.图3为格网点二维索引示意图；
51.图4为索引结构图；
52.图5为vrs最优格网点快速查找流程图；
53.图6为vrs最优格网点快速查找系统组成示意图。
具体实施方式
54.为使本发明的目的、技术方案和优点更加清楚明了，下面结合具体实施方式并参照附图，对本发明进一步详细说明。应该理解，这些描述只是示例性的，而并非要限制本发明的范围。此外，在以下说明中，省略了对公知结构和技术的描述，以避免不必要地混淆本发明的概念。
55.用户终端cors接入的流程图如图1所示。用户终端上传概略经纬度和高程至cors服务接入系统，cors服务接入系统查询最优网格点，返回给定位终端。vrs格网点数据由cors计算系统实时更新。
56.一般最优的格网点是指距离用户终端上传的坐标最近而且时间上比较接近的格网点。这里蕴含两个概念：第一是距离近，第二是时间上接近。两者综合考虑，取最优。实际中，根据经验，距离大于20km的格网点认为不合格，时间大于20s的也是认为无效，本发明中称为无效格网点。
57.结合图5，提供一种vrs最优格网点快速查找方法，包括如下步骤：
58.(1)生成指定地区的vrs格网点坐标列表，各个格网点之间间距为5～10km。
59.cors系统部署在一个地区时，根据这地区分布的基准站，可以事先生成vrs格网点坐标列表，如图2。vrs格网点坐标列表是根据基准站插值生成的。
60.(2)对所有所述vrs格网点的坐标进行转换以二维坐标投影至坐标系格子中。
61.程序初始化时，对事先作备好的所有vrs格网点的坐标进行转换，把xyz地固坐标转换为大地坐标系blh，b纬度、l经度和高程h。由于格网点都是规范的大致间距相等，每个格网点经验上看，至少5～10km差距。根据b和l，以大约0.1
°
为间距，以二维坐标建立简单投影到坐标系格子中(实际情况可以根据不同地区调整间距)，如图3。
62.坐标系格子(x,y)计算公式如下：
63.x＝(l
–
min_l)/scale_x
64.y＝(b
–
min_b)/scale_y
65.可以简写成(x,y)＝f(b,l)
66.其中scale_x为经度方向划分坐标系格子的间距，scale_y为纬度方向划分坐标系格子的间距。
67.对所有的格网点坐标进行上述处理，可以得到一个二维数组索引表，如图4。采用二维的坐标系格子对应存储三维大地坐标系blh。根据映射关系二维的坐标系格子查找对应三维大地坐标系blh。
68.(3)每个坐标系格子作为一个哈希桶，采用链表连接各个坐标系格子。
69.把每个坐标系格子点看成一个哈希桶(hash bucket)，里面包含的格网点使用链表连接，每次只要找到坐标系格子，那么查找的时候只需要遍历极少数的点即可。
70.(4)根据用户终端上传的纬度、经度和高程坐标，计算得到对应的坐标系格子，根据得到对应坐标系格子以及用户终端上传的时间，查找链表找到有效的坐标系格子。
71.当用户终端接入时，会上传坐标(b,l,h)以及时间t_user,根据映射函数f，可以得到(x,y)＝f(b,l)，直接找到对应的链表，在链表中一一比较找到最优即可。如果一个格子比较，找不到有效值，查找的最优格网点依然不能满足阈值，，则返回错误给用户。
72.(5)有效的坐标系格子对应的vrs格网点中选择最优格网点返回给用户终端。
73.对于有效格网点，选取的时候按照如下原则：
74.d(st)＝dis dis(t)
75.其中dis是用户终端上传的坐标到该格网点的距离。
76.dis(t)是该格网点的更新时间与用户终端上传的时间t0的时间差换算成的距离，时间差为1s可以认为是1km。
77.最后得到的综合d(st)最小值即为最优格网点，这个值可能还是超过阈值，就是上一步所说的找不到有效值。
78.重复步骤(4)至(5)为各个用户终端提供服务。
79.另一方面提供一种vrs最优格网点快速查找系统，结合图6，包括vrs格网点坐标列表生成模块、坐标系格子生成模块、链表生成模块、有效的坐标系格子查找模块以及最优格网点输出模块。
80.vrs格网点坐标列表生成模块，生成指定地区的vrs格网点坐标列表，各个格网点之间间距为5～10km。
81.坐标系格子生成模块，对所有所述vrs格网点的坐标进行转换以二维坐标投影至坐标系格子中。坐标系格子以大约0.1
°
为间距。
82.进一步地，坐标系格子生成模块进行坐标进行转换包括：把xyz地固坐标转换为大地坐标系blh。
83.坐标系格子生成模块，生成坐标系格子二维坐标(x,y)＝f(b,l)：
84.x＝(l
–
minl)/scale_x
85.y＝(b
–
minb)/scale_y
86.其中，b为纬度值，l为经度值，minl为vrs格网点中经度值的最小值，minb为vrs格网点中纬度值的最小值，scale_x为经度方向划分坐标系格子的间距，scale_y为纬度方向划分坐标系格子的间距。
87.链表生成模块，每个坐标系格子作为一个哈希桶，采用链表连接各个坐标系格子。
88.有效的坐标系格子查找模块，根据用户终端上传的纬度、经度和高程坐标，计算得到对应的坐标系格子，根据得到对应坐标系格子以及用户终端上传的时间，查找链表找到有效的坐标系格子。
89.有效的坐标系格子查找模块，根据用户终端上传的纬度b、经度l和高程h计算二维坐标(x0,y0)；
90.根据二维坐标(x0,y0)以及用户终端上传的时间，查找链表找到有效的坐标系格子，包括：
91.根据坐标系格子的间距，计算空间上距离二维坐标(x0,y0)距离dis满足距离阈值要求的坐标系格子,作为有效坐标系格子；一个坐标系格子里面包含若干格网点，每个格网点都存在一个更新时间。
92.最优格网点输出模块，由有效的坐标系格子对应的vrs格网点中选择最优格网点，将其坐标返回给用户终端。
93.最优格网点输出模块，选择最优格网点包括：
94.对有效的坐标系格子计算综合值：
95.d(st)＝dis dis(t)
96.dis是用户终端上传的坐标到该格网点的距离；
97.dis(t)是该格网点的更新时间与用户终端上传的时间t0的时间差换算成距离dis(t)，时间差为1s认为是1km；
98.选择d(st)最小时对应的vrs格网点作为最优格网点。
99.综上所述，本发明提供一种vrs最优格网点快速查找方法及系统，生成指定地区的vrs格网点坐标列表，各个格网点之间间距为5～10km；对所有vrs格网点的坐标进行转换以二维坐标投影至坐标系格子中；每个坐标系格子作为一个哈希桶，采用链表连接各个坐标系格子；根据用户终端上传的纬度、经度和高程坐标，计算得到对应的坐标系格子，根据得到对应坐标系格子，查找链表找到有效的坐标系格子；有效的坐标系格子对应的vrs格网点中选择最优格网点返回给用户终端。本发明针对最优格网点查询进行优化，在牺牲少量存储的情况下，单个定位终端匹配坐标的时间复杂度达到o(1)，不随着格网点增长而增长，大幅提高了查找最优格网点的速度。
100.应当理解的是，本发明的上述具体实施方式仅仅用于示例性说明或解释本发明的原理，而不构成对本发明的限制。因此，在不偏离本发明的精神和范围的情况下所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。此外，本发明所附权利要求旨在涵盖落入所附权利要求范围和边界、或者这种范围和边界的等同形式内的全部变化和修改例。