基于稀疏栅格优化的蜂窝车联网定位算法

夏小涵，蔡超，邱佳慧，杨静远，张香云，肖然

1.中国联合网络通信有限公司智网创新中心，北京100048

2.生态环境部核与辐射安全中心，北京100082

3.爱立信（中国）通信有限公司，北京100102

车联网作为5G发展的重要方向之一受到了广泛关注。目前，车联网主要涉及三大业务应用：交通安全、交通效率和信息服务[1]。不同的业务场景，对于车联网的定位技术要求也不同，如交叉路口碰撞预警、紧急制动预警、车速引导、紧急避让等。其中，高精度定位是实现无人驾驶或远程驾驶的必要前提，同时因车路环境的特殊性，而对其定位要求也更加严格[2]。

车联网的高精度定位关键技术主要包括：基于实时动态（real time kinematic,RTK）差分系统的全球导航卫星系统（global navigation satellite system,GNSS）定位、传感器与高精地图匹配定位、蜂窝网定位及同步。基于蜂窝网的室外定位技术主要包含基于测距模型的定位技术和基于位置指纹的定位技术[3]。指纹定位技术通过采集到的真实终端信号信息来构建指纹库，直接根据终端上报的最小化路测（minimized driving test,MDT）信息训练指纹定位模型，同时利用机器学习的方式进行匹配定位。该技术相对于传统的基于小区ID的基站定位方案具有更高的定位精度和发展性[4]。但指纹库的定位预估精度对原始数据的依赖较高，同时数据库的建立也需要消耗较多的算力和维护成本。因此，指纹定位技术在车联网场景中仍面临着一些问题和挑战。由于车辆位置的特殊性和集中性，车联网系统很容易产生聚集的指纹矩阵，进而在指纹栅格划分时浪费大量的计算资源。同时车联网环境的低时延、高可靠性响应要求车联网算法需要有更快和更精确的响应[5]。

本文提出了一种基于稀疏栅格优化的车联网定位方案。首先考虑到车辆行驶路线及停靠位置的特点，直接栅格化会导致地图上出现大量的空白区域，即稀疏指纹栅格。本文采用统计信息网格（statistical information grid,STING）算法聚类的方法来代替原有栅格化，从而在计算上避免大量无意义的栅格分类。定位的业务场景决定了其在使用数据分析算法时，可选择涉及距离度量模型的机器学习算法或擅于多参分析的树形算法。从计算时延的角度考虑，采用极端梯度提升（extreme gradient boosting,XGBoost）算法代替常用的K值最近邻算法。在保证精度的基础上尽量减少计算时延，确保定位算法在车联网中的实时性和可靠性，并提高兼容性。

1 基于稀疏栅格优化的车联网定位系统分析

3GPP 38.885[6]中定义了V2X的PC5空口通信协议。如前文所述，传统指纹定位在计算资源、时延等方面难以直接应用于车路协同场景。在车联网环境中，车辆往往集中于道路、路侧、路口、停车场等地，信号采样会产生明显聚集特征，容易产生稀疏的栅格结构。针对车联网系统的特殊的稀疏栅格结构，本文用STING算法对于稀疏栅格进行优化，剔除部分空白栅格和误差栅格，为后续指纹匹配计算节省分类资源。

STING是一种基于网格的多分辨率的聚类技术，它将输入对象的空间区域划分成矩形单元，空间可以用分层和递归方法进行划分。这种多层矩形单元对应不同的分辨率，并且形成了一个层次结构：每个高层单元都被划分成低一层的单元。每个网格单元的属性的统计信息（均值、最大值、最小值等）作为统计参数预先进行计算和存储。对于查询处理和其他数据分析任务，这些统计参数均为可用参数[7]。

在基于指纹的定位算法中，STING算法可用来替代原始的区域栅格化方法，剔除稀疏栅格和离散点。根据不同精度需求，算法会将栅格映射为多级别的矩形单元并形成层次结构，高层的栅格单元将由更细粒度的低层单元组成。通过栅格中的属性统计信息，进行查询回答。保留满足需求的栅格单元，不满足需求的则被剔除，从而达到不同精度的栅格聚类及稀疏栅格优化效果。

相对于其他聚类方法，STING算法对于栅格优化拥有一些独特的优点[8-9]：

1）基于网格的计算独立于查询，存储于每个单元的统计信息提供了单元中数据汇总信息，不依赖于查询，极大提高了计算速度。

2）通过该算法更有利于进行后续增量更新和并行处理。

3）STING扫描一次数据库即开始计算单元的统计信息。假设整个聚类时间复杂度为O(n)，则在层次结构建立之后，查询处理时间为O(t)。由于t为最底层单元的数据，远小于n。整体算法的计算效率会得到较大提升。

基于STING算法的稀疏栅格优化过程如图1所示。

图1 STING栅格优化流程Figure 1 Grid optimization by STING

近年来，随着机器计算和硬件处理性能的提升，机器学习已成为模型化处理大数据场景的常用方案之一。稀疏栅格优化可有效节省定位算法中数据匹配的计算资源。在指纹定位算法中，KNN/WKNN算法作为常用的指纹定位算法，已被多次应用[9-10]。由于源数据的数据漂移，在遇到数据缺失情况时，这种涉及样本距离度量模型的机器学习算法会导致较差的预测结果。为了避免上述问题，本文基于算法实时性和精确度的考虑，对比了KNN和XGBoost算法在指纹定位中的性能。同时基于卡尔曼滤波方式减少测试误差，增加数据的可信度。

XGBoost是大规模并行提升树的工具。在数据建模中，经常采用聚集方法通过将数百个分类准确率较低的树模型组合起来，成为一个准确率较高的预测模型。该模型将不断迭代，每次迭代生成一颗新的树。但在数据集较复杂时，可能需要几千次迭代运算，这将造成巨大的计算瓶颈。XGBoost完成了回归树的并行构建并在原有梯度提升树算法基础上加以改进，极大地提升了模型训练速度和预测精度[11]。基于XGBoost的指纹定位方案流程图如图2所示。

图2 蜂窝车联网场景下的指纹定位方案流程图Figure 2 Flowchart of f ingerprint location scheme in C-V2X

2 基于稀疏栅格优化的新型指纹定位技术

2.1 基于STING算法的车联网稀疏栅格优化

通过对车联网中的指纹标签采样与位置的分析可以看出，指纹标签数据集中在路、路口等区域。对于此数据的栅格化形成了明显的稀疏栅格矩阵，如图3所示。

图3 蜂窝车联网指纹标签打点分布图Figure 3 Distribution map of f ingerprint tags in C-V2X

稀疏栅格只包含较少的有用信息，但需占用与信息栅格同等的算力，这就造成了较大的资源浪费。根据STING聚类算法，可以从栅格矩阵分块方面加以优化。整个方案可分为数据清洗、栅格区域构建、稀疏栅格优化、指纹库构建、模型参数优化等功能子模块。

2.1.1 数据清洗

数据清洗对指纹定位的精确性至关重要。数据清洗的标准包括：1）有明确的特征信息；2）缺失信息尽可能少；3）无明显离散特征。满足上述特征的数据将作为训练模型。

2.1.2 栅格区域构建

STING算法会针对不同的分辨率设置多个级别的矩形栅格。构建过程如下：

1）首先划分一些层次，按层次划分网格。对最高层栅格，可以设置整层作为单个栅格进行处理。高层每个栅格单元划分为多个低一层的单元。划分中止条件取决于层数、分辨率、固定查询条件，最后同一栅格内的数据点形成一个簇。栅格分层图如图4所示。

图4 STING栅格分层Figure 4 Grid layer used in STING

2）计算最底层单位栅格的统计信息（如均值、最大值、最小值）。最底层的单元参数直接由数据计算，父栅格统计信息由其对应的子栅格计算，计算公式如下：

式中：n为栅格标签数目，通过采样点的经纬度来统计；m为栅格属性的平均值，由于标签值的单位差异过大，采用主特征值作为栅格属性，这里采用部分基站公参和主邻小区参考信号功率作为目标参数，在一定程度上也起到深层数据清洗的作用；s为栅格属性的标准差；min为栅格属性的最小值；max为栅格属性的最大值。栅格中统计信息distribution为栅格中属性值符合的分布类型，如正态分布、均匀分布、指数分布。

父栅格分布类型计算如下：

假定dist为对应子栅格多数的分布类型，计算conf；

若disti̸=dist,mi≈m,si≈s，则conf=conf+ni；

若disti̸=dist,mi!≈m，或si!≈s，则conf=n；

若disti=dist,mi≈m,si≈s，则conf=conf+0；

若disti=dist,mi!≈m，或si≈s，则conf=n；

3）从最底层逐层计算上一层每个父单元格的统计信息，直到最顶。

4）根据密度阈值标记稠密网格。

2.1.3 稀疏栅格优化

车联网的指纹定位标签包括指纹库的特征值和标签的统计属性。数量、均值、偏差、分布、最值等会被预先计算存储，作为栅格的查询问答。

通过计算的属性值及约束条件，从最顶层开始根据查询结果将每一个栅格标记为是否相关。获取上层的处理结果后，下层处理相关的栅格。逐层处理直至最底层或查询结果得到满足。

此外，最底层的单元参数也可直接由数据计算获得，若分布类型已知，则用户可直接指定。较高层栅格分布类型可以根据其对应的底层单元，用阈值过滤的结果进行计算。若底层分布类型彼此不同，则高层分布类型为空。

在计算趋于底层的过程中，数据粒度趋向于0。整体聚集结果趋向于高斯白噪下的基于密度的空间聚类（density-based spatial clustering of applications with noise,DBSCAN）的结果，这样通过计数和大小信息，可以近似识别稠密的栅格簇。

2.1.4 模型预测定位与修正

利用已建立的模型对测试数据进行预测，比较预测结果与实际终端位置信息，从而可得模型预测的准确度的量化结果。根据对终端位置预测的位置结果，可以闭环地修正训练模型，调整模型的训练参数，从而强化模型的预测能力。修订模型与预测结果是闭环反馈关系，因此在该闭环中能够有效地完成模型的校正，提升模型的预测准确度。

2.2 基于XGBoost的车联网指纹定位技术

本节主要介绍基于XGBoost的车联网指纹定位算法。通过对位置-信号强度库的直接训练来获得指纹库，并由该模型直接预测输出待定位目标的实际位置。

车联网的采样指纹定位标签作为指纹库的特征值，包括服务基站ID、服务基站公参、主小区CQI、主小区RSRP、临小区CQI、临小区RSRP、次临小区CQI、次临小区RSRP等。由于不同参数值对定位结果的影响力度不同，因而特征值需要设置不同的权重。

通过机器学习算法可以学习栅格位置和指纹标签之间的映射关系，构建高精度的指纹库如表1所示。

表1 指纹库特征表格Table 1 Table of f ingerprint feature

前文提到，定位场景决定了该场景在进行数据分析时，适合选择涉及距离度量模型的机器学习算法，如KNN/WKNN算法；或擅于多参分析的树形算法，如XGBoost算法。KNN算法会在库中遍历寻找距离目标节点最近的K个标签，取平均作为目标节点的预测值。考虑到计算效率，本文选择用基于KD树的欧氏距离KNN算法作为对比。

作为一种多决策树的分类器，XGBoost算法本质上依然遵循了梯度提升决策树（gradient boosting decision tree,GBDT）算法，但将速度和效率发挥到了极致。其基础为梯度提升决策树的思想，XGBoost采用串行方式使各个基分类器之间有依赖。将基分类器层层叠加，每一层在训练时对前一层基分类器分错的样本给予更高的权重。最后，根据各层分类器结果的加权得到最终结果[12-13]。

使用的XGBoost的目标函数如下：

式中：N为决策树数目；l为损失函数；Ω为正则项；C为常数；ft(xi)为回归树；yi为第i个样本真实值，该样本在第t轮的模型预测值。

用泰勒展开对目标函数进行处理，令偏导分别为

目标函数可以转化为

算法最终目的是学习ft使目标函数最小，这主要依赖于每个数据点在误差函数上的一阶和二阶导数。损失函数l揭示了训练误差，文中采用了Logistic损失函数。而正则函数Ω(fk)表示树的复杂度的函数，其中k为分类树的数量。正则函数Ω(fk)的值越小，复杂度越低，泛化能力越强，其表达式为

式中：T为叶子节点的数目；w为叶子节点的分数。从直观上看，目标要求预测误差尽量小，且叶子节点T尽量少（γ控制叶子节点的数目），节点数值w尽量不极端（λ控制叶子节点的分数不会过大），防止过拟合。

整个学习过程如图5所示，可以分为回归树构建、回归树分裂、分裂停止。

图5 蜂窝车联网指纹定位的XGBoost树结构Figure 5 XGBoost tree structure in C-V2X f ingerprint location

1）回归树构建

在指纹学习的过程中，选取Logistic损失函数，以指纹特征值构建回归树。回归树的复杂度和正则项有关，包含了两部分：叶节点数目和叶节点得分数的二范数平方。正则项对于这2个参数分别加以限制，是为了避免出现过拟合的结果。这样式(2)和式(3)去掉对于目标函数无影响的损失函数和常数部分，目标函数可以转化为

式中：Ij={i|q(xi)=j}为每个叶节点的样本集合。式中包含了T个相互独立的单变量二次函数。令。对目标函数做凸优化可得目标函数最优解为

以上完成对目标函数最优解求值。O的最优解代表的树结构最好，这样就完成了回归树目标函数的构建。

2）回归树分裂

回归树由每个节点不断分裂形成整颗树。在车联网的指纹定位中，标签特征决定了分裂复杂程度，而栅格数目决定了分类的数目。在每个节点，回归树都需要对标签字段做处理来进行树的分裂。

分裂节点的方法采用贪婪算法。从树深度为0开始，对每一节点都遍历所有的特征，包括服务小区信息、主小区CQI、主小区RSRP、临小区CQI、临小区RSRP等。此后对每类特征值先按照该特征里的值进行排序，再通过线性扫描该特征进而确定最好的分割点，最后对所有特征进行分割，选择增益最高的特征组，这样就完成了一次分裂。

由回归树函数可以获得每个节点对于树的增益贡献及复杂度代价。假设根据某点将树分为左子树和右子树。整个树分裂后可以获得的增益为

即左右子树的增益贡献之和除去不分裂的原始增益，以及引入新叶节点的复杂度代价。通过枚举获得Ggain的最大值，即完成了本层的树分裂。

当引入的分裂带来的增益小于设定阀值时，回归树可以忽略该分裂，完成预剪枝。从而降低整体的结构复杂度。

3）分裂停止

为了限制树过深，防止过拟合的情况出现，算法设定了分裂阈值。当分裂增益小于分裂阈值时，分裂停止。由分裂树增益可得设定的阈值为

分裂停止的条件如下：

a）当树生长带来的增益小于复杂度代价时，停止建树。

b）设定超参数最大树深，当超过时则停止建立决策树，避免树太深导致学习局部样本，引起过拟合。

c）设定超参数最小样本权重。当样本权重和小于设定参数时则停止建树。

通过XGBoost对原始指纹标签进行学习后，可以根据新的用户特征获取其最大相似坐标，从而完成定位目的。

3 实验仿真结果分析

本节将对整个系统进行仿真实验，并相对于原始GNSS坐标给出量化的比对指标，进而确定算法精度，仿真参数说明如表2所示。

表2 仿真系统参数Table 2 Parameters of simulation system

选定一个包含十字路口的区域对于车联网定位进行分析，数据源来自于中国联通车联网定位测试数据。分别对正常栅格化KNN定位、稀疏栅格化KNN定位和稀疏栅格化XGBoost定位的指纹定位进行对比。

首先对清洗完的数据进行处理。由于车辆运动的特征，一般在路口区域的数据会较为密集，快速道路上的数据则比较零散。训练数据库的位置源于GNSS坐标，因此仍然存在一定的位置漂移。清洗后的数据和栅格关系如图6所示。

图6 清洗后的OBU测试数据Figure 6 Cleaned position data of OBU

选择同样的栅格粒度对栅格进行优化。优化指标为栅格的元素数目、栅格均值、栅格数值分布，优化前后栅格对应的区域如图7所示。

图7 栅格区域对比Figure 7 Comparison of grid area

在正常栅格和稀疏栅格中，分别用KNN算法和XGBoost算法，所获得的结果如图8所示。

图8 不同机器学习算法预测结果对比Figure 8 Comparison of location results using different machine learning algorithms

在稀疏化的过程中会出现因栅格元素不足或数据异常导致元素被再次清洗的情况，也就是原始数据的深度清洗。因此稀疏化之后对应的数据源，较之前的数据源更为集中，定位精度也会提高。但由此可能会带来区域外的数据误差或定位误差，这些则需要利用修正聚类参数的方法以及足够数量的实时性源数据来弥补。

表3 不同机器学习算法性能分析Table 3 Performance analysis in different machine learning algorithms

从定位结果可以看出，在定位精度上稀疏栅格中的算法性能优于正常栅格。这一部分原因是由于聚类导致的误差数据减少；另一部分原因则是因为可选栅格减少，栅格区域外的数据变少。在运行时间上由于栅格数目大幅度减少，算法运行时间会有较大缩减。在稀疏栅格中，KNN算法和XGBoost算法精度差距不大。而在时间上，优化参数后的XGBoost算法计算时间最短，可以有效提高定位实时性。

从预测结果可以看出，在数据较为密集的区域预测值和实际值表现出比较好的聚类属性。但在数据稀少的位置，预测结果仍然有较大的误差。另外从图9可以看出，主服务小区的信号质量是定位的重要依据。而对于服务基站ID的参数，没有得到合适的权重配比。该参数隶属于类别属性，可能需要在机器学习以外的过程处理。在定位结果上，对车位置判断较为准确，已经可以满足车联网通知类业务的需求，但对于车道级判断还有所欠缺。此外涉及的核心网网元和信令流程，在算法中处理不够全面，可以在定位流程中进一步考虑。

图9 定位标签特征权重图Figure 9 Weight diagram of location label feature

4 结语

本文介绍了车路协同场景下的基于稀疏栅格优化的指纹定位算法。通过分析车联网定位的特征，提出了一种基于稀疏栅格优化的指纹定位方案，用减少同粒度栅格数量的方法大幅降低了机器学习算法的处理时延，保障了定位的实时性。同时对比XGBoost算法和KNN算法在指纹定位中的表现，确定使用XGBoost算法来获得更低的计算时延和较高的定位精度。最后通过数据仿真，验证了用稀疏栅格优化的XGBoost指纹定位算法在车联网场景中时延和精度方面的优势，为车联网指纹定位提供了一种优化方案。相较于实际应用场景，数十米的定位精度还较难达到某些严苛的应用场景需求，如碰撞预警等，但已可用于通知类应用。此外，由于目前在城市高楼环境中采集数据且无效数据较多，数据源本身存在较严重的漂移现象，影响了定位效果。未来的工作将集中在提高数据源数量质量，优化特征参数类别和超参数等方面，通过更大规模的数据训练和算法参数优化，进一步提高定位精度。