复杂环境下BDS场景精度等级聚类模型

范亚军，王 萍，郁文贤，何 迪

复杂环境下BDS场景精度等级聚类模型

范亚军1，王 萍1，郁文贤2，何 迪2

（1. 东华大学信息科学与技术学院，上海 200051；2. 上海交通大学电子信息与电气工程学院，上海 200040）

针对实际复杂场景下北斗卫星导航系统（BDS）导航定位精度不足问题，提出一种基于美国国家海洋电子协会（NMEA）协议的BDS自适应场景迭代自组织数据分析技术(ISODATA)聚类算法,以辅助BDS终端针对不同场景采取合适精度的补偿策略，即从实时NMEA报文提取与BDS定位相关的环境特征指标进行场景聚类分析，依据BDS精度等级对导航场景进行自动分类和精度匹配,并采用有监督的k近邻算法（kNN）对ISODATA场景聚类结果的准确度进行评估。实验结合（上海）复杂城市环境下的实际路测数据，提取BDS导航场景聚类模型结果及相应的匹配精度等级，给出谷歌（Google）地图上再现7类典型场景下不同路段对应的12种自动聚类匹配精度，以及相应的定位精度偏差均值。实验结果表明：此聚类方法的均方误差多次迭代后效果明显优于其他聚类方法，根据本次路测可识别的精度聚类等级范围（最近0.02 m、最远约3 m）给出精度补偿的相对应的建议，也验证了模型的有效性。

北斗卫星导航系统；导航场景聚类；定位精度聚类等级；NMEA报文；自适应场景聚类算法

0 引言

北斗卫星导航系统（BeiDou navigation satellite system, BDS）作为中国科技发展重要战略之一，受到广泛重视。顺应国家的军民融合[1]政策，BDS导航加快空间卫星部署的同时，也加快了BDS终端民用化商用进程。面对未来智能交通[2]、无人驾驶等系统对于高精度导航定位的需求，BDS导航定位的精度是备受研究关注的核心问题，尤其是实际复杂的地面应用环境对BDS终端的挑战。而对精度影响较大的因素有多种：文献[3]介绍了通过对电离层的检测并对比BDS和全球定位系统（global positioning system, GPS），BDS对电离层的检测并补偿可以有效地提升定位精度；文献[4]介绍了通过对载波相位多径效应的抑制来提升定位精度；文献[5]讨论了通过多全球卫星导航系统（global navigation satellite system, GNSS）的组合实施精确定位；文献[6]基于惯导对BDS和GPS模糊度固定的研究以提高载波相位观测的准确性；文献[7]通过手机惯导进行地下定位的研究；文献[8]基于车路协同，在弱收星或无收星的路段通过路边单元与车载单元通信的方式实时播报定位信息以获得高精度定位。

由于实际导航环境复杂，各种因素综合影响BDS导航精度，单一的精度补偿辅助方法并不能完全解决各种场景下BDS定位精度问题，近来，多源融合导航[9-11]采用不同技术的数据融合来共同辅助定位导航，实现高精度定位导航，已成为BDS实际应用的发展趋势。然而，现场路测表明，由于缺乏对不同场景下BDS精度自动识别、分类的手段，融合定位系统的实际应用效果不能很好地与实际环境相匹配。

为辅助BDS导航设备选择合适的精度补偿策略，加强BDS实际应用精度的评测，对BDS导航环境提供科学的场景分类依据十分重要。本文提出一种复杂环境下BDS导航场景精度等级自动聚类的科学建模方法，结合美国国家海洋电子协会（The National Marine Electronics Association, NMEA）通讯协议设计了BDS参数化迭代自组织数据分析技术（iterative self-organizing data analysis techniques algorithm, ISODATA）聚类算法[12-15]，以期较通常的聚类方法更好地提高模型匹配精度，获得更精确的精度识别效果，实现实际导航场景精度等级的自动识别。

1 BDS导航场景聚类模型

基于真实场景的BDS路测数据建立场景聚类模型，总体流程如图1所示。

图1 场景聚类模型设计流程

首先对标准的BDS NMEA协议报文中提取5类对BDS导航精度影响较大的指标作为场景聚类特征属性，具体指标定义如表1所示。

表1 场景指标

基于以上5类指标对样本点赋予这5类属性，并配置一个场景标签属性，则样本点可表征为

其中每个样本点属于1个聚类中心。

对于样本点进行ISODATA算法的处理以及精度计算，并进行场景和精度的匹配；然后对此聚类模型进行性能评估。

2 基于ISODATA的自适应场景聚类

2.1 ISODATA算法原理

ISODATA相较于传统k均值聚类算法（k-means clustering algorithm, k-means）可以更加有效地实行聚类，并可以对实际应用情况下聚类中心数目不确定性给出科学的表征。而现场实测的BDS数据受环境影响，其精度具有随机且离散的特征，因此ISODATA可变值的特点有助于提升BDS数据无监督聚类的准确性和灵活性。

ISODATA算法称为是迭代自组织数据分析法，此算法可以在整个聚类过程中根据各个类的实际状况动态调整聚类中心的数目。

ISODATA基于方差对类进行衡量，如果其中某个类方差较大即离散程度较大，则进行分裂操作，增加聚类中心数目；如果2类聚类中心距离很近则进行合并操作，减少聚类中心数目。

2.2 场景聚类

本文采用ISODATA聚类算法对BDS路测数据依据定位精度的不同效果进行自动分类，以获取BDS场景聚类模型。建模的方法如下：

1）参数初始化，预期的聚类中心为

执行IOSDATA分裂操作流程：

计算每个聚类中心的簇内样本方差

待拆分的簇分类2个子簇，其中心向量分别为

中心向量拆分完毕后，再对所有样本进行重新划分，并再次计算簇的匹配度和样本的准确率。

执行IOSDATA合并操作流程：

计算剩余簇中心向量两两之间的距离，以矩阵表示聚类中心间的距离，其中

6）多次迭代，待均方误差达到稳定时结束迭代，对每次迭代后的样本集进行准确率计算。

2.3 聚类匹配性能评估

使用有监督的k近邻法（k-nearest neighbor, kNN）分类方式对ISODATA这种无监督聚类模型进行匹配性能评估。

对于待测试样本选取其欧式距离最近的个样本点作为评估参考，的定义为

式中为总样本数目。

从最近的个样本中出现频次最多的聚类标签作为评估标签。通过评估标签和原先聚类标签做对比，观察待测聚类样本标签匹配正确率，匹配正确率高的聚类模型较优。

2.4 聚类定位精度

每个样本数据利用其经纬度坐标对应该点处

3 实验及结果分析

3.1 现场测试仪表和环境

现场测试由上海北斗导航创新研究院合作支持，测试路线覆盖上海徐家汇地区的空旷、树林、河边、城市街区、高架、隧道、跨江大桥等多种场景，路线长度不少于120km。路测采集如图2所示。

图2 数据采集基本流程

通过对射频信号的采集并回放基于协议解析的数据报文，从中提取可用指标用于场景聚类分析。

测试车车顶安装天线装置，接收射频信号馈入车内的2套BDS采集设备，一套为存储波形数据的Spirent设备，一套为实时采集分析输出的NovAtel设备，最后将卫星波形数据转化为卫星数据的标准输出数据。测试采集车如图3所示。

图3 测试数据采集设备

3.2 BDS测试样本的聚类结果分析

对上述样本集合采用ISODATA算法进行聚类。

聚类后的场景数目如图4所示。ISODATA聚类算法在迭代10次以后将场景类别数目自适应调整为12个，聚类结果见图5所示，仅列出2个场景的示例。ISODATA算法基本实现了场景的显著分割。

图4 ISODATA算法聚类后的场景数

图5 ISODATA算法聚类后的部分簇分布

图6列出了分别经过1到10次迭代后2类算法的簇内样本均方误差的平均值。在小样本的聚类结果中，基本经过3次迭代后，簇内的样本均方误差变化幅度明显减小，经过10次迭代后均方误差已经达到基本不变。从图中可以看出，在多次迭代后，ISODATA的聚类算法的样本均方误差相较于k-means会有所降低。

图6 k-means和ISODATA的均方误差对比

3.3 聚类模型匹配准确率的KNN评估

通过对迭代10次、样本聚类稳定后的k-means聚类样本集和ISODATA聚类样本集分别取1/3的样本作为训练样本，并用剩下的2/3的样本点进行kNN训练，并得出2类聚类算法得出的样本集的场景分类准确率（如表2所示）。

表2 k-means和ISODATA训练比对结果

由上表可以看出，经ISODATA聚类后的样本集的kNN分类准确率较传统k-means标签的准确率提升更为明显。

3.4 场景聚类模型结果

表3为聚类结束后自适应生成的12个场景类别的样本精度误差平均值，场值与精度的对比如图7所示。表4给出典型路段的环境描述。

从表3和图7的对照可以看出虽然于指标和对应精度之间有密切的关系，但还是有部分差异存在，基本上在指标较好的情况下其定位精度也较为优良。

表3 场景定位精度对比表

图7 场景指标均值与精度对比

表4 典型路段参考环境

虽然标定设备在不同路段会存在不同程度的误差，但是从相对误差来看，的确在遮挡严重的路段上定位精准度有所下降。

3.5 场景的精度补偿策略

现场路测样本回放后的BDS数据聚类的谷歌（Google）地图还原结果如图8所示，将聚类后自适应生成的12个场景的样本集分别叠加到地图中可以明显发现，在一些拐弯处，高楼和树荫遮挡处场景会较为恶劣，相应的导航定位效果也会变差很多。

图8 ISODATA算法样本聚类结果

对不同的场景类别和典型路段采用不同定位补偿策略，例如：在定位效果较好的开阔地（场景1~2），现有的导航结合实时动态载波相位差分（real time kinematic, RTK）技术在无恶劣天气影响的情况下基本可以实现分米级的定位效果；对于在较为轻微的遮挡下（场景3~5）使用GNSS配合RTK也可实现分米级的定位，但效果较开阔地略差一点，不过依旧可以显示高精度的定位导航服务；但对于树荫或高楼遮挡的情况下（场景6~9），会出现间歇性的卫星失锁，再重捕获卫星会出现周跳，可以通过惯导在短时间内的高精度补偿性能实现部分失锁状态的定位及周跳修复，对于在隧道高架下等基本无收星的情况下（场景10~12）可以通过惯导加路边单元的实时位置播报实现较高精度的导航定位。

4 结束语

基于k-means算法的k值存在不确定性以及对海量数据处理的速度较慢，提出了IOSDATA算法来优化聚类的性能：以BDS的实测数据来进行聚类，多次迭代后形成较为合理的场景分类；将地理位置精度和测试样本点的分类结果进行对比，测算方差。实验结果表明，ISODATA聚类算法相较于普通k-means聚类算法样本的匹配度更高。在较高的匹配度下，场景分类更为准确，BDS接收机仅从接收的卫星数据就可以测算出当前输入哪类场景，是哪些典型的路段，对于这些典型的路段可以采取对应的BDS高精度技术来弥补相应恶劣场景下的精度缺陷，以实现多场景下的自适应高精度导航。

[1] 李龄, 宋超. 强通信导航装备军民融合维修保障建设的几点思考[J]. 机电信息, 2018(30): 159-160.

[2] 刘小洋, 伍民友. 车联网: 物联网在城市交通网络中的应用[J]. 计算机应用, 2012, 32(4): 900-904. DOI: 10. 3724/SP. J. 1087. 2012. 00900.

[3] TANG W, JIN L, XU K. Performance analysis of ionosphere monitoring with BeiDou CORS observational data[J]. Journal of Navigation, 2014, 67(3): 511-522.

[4] LI Xingxing, GE Maorong, DAI Xiaolei, et al. Accuracy and reliability of multi-GNSS real-time precise positioning: GPS, GLONASS, BeiDou, and Galileo [EB/OL]. [2019-03-16].https://www.researchgate.net/profile/Xingxing_Li3/ publication/273770086_Accuracy_and_reliability_of_multi-GNSS_real-time_precise_positioning_GPS_GLONASS_ BeiDou_and_Galileo/links/554d26110cf21ed2135f5e73/Accuracy-and-reliability-of-multi-GNSS-real-time-precise-positioning-GPS-GLONASS-BeiDou-and-Galileo.pdf.

[5] YE S , CHEN D , LIU Y, et al. Carrier phase multipath mitigation for BeiDou navigation satellite system[J]. GPS Solutions, 2015, 19(4): 545-557.

[6] HAN H, WANG J, WANG J, et al. Reliable partial ambiguity resolution for single-frequency GPS/BDS and INS integration[J]. GPS Solutions, 2016, 21(1): 1-14.

[7] 袁德宝, 张帆宇扬, 周振青, 等. 结合手机惯性传感器的地下定位算法研究[J]. 测绘通报, 2018(9): 8-12.

[8] 罗文慧, 董宝田, 王泽胜. 基于车路协同的车辆定位算法研究[J]. 西南交通大学学报, 2018, 53(5): 1072-1077, 1086. DOI: 10. 3969/j. issn. 0258-2724. 2018. 05. 026.

[9] 段睿, 张小红, 朱锋. 多源信息融合的组合导航自适应联邦滤波算法[J]. 系统工程与电子技术, 2018, 40(2): 267-272.

[10] 赵万龙, 孟维晓, 韩帅. 多源融合导航技术综述[J]. 遥测遥控, 2016, 37(6): 54-60.

[11] 张成才, 岳建平. 北斗/GPS组合相对定位及精度分析[J]. 地理空间信息, 2018, 16(8): 30-33. DOI: 10. 3969/j. issn. 1672-4623. 2018. 08. 008.

[12] HU Jinqiu, ZHANG Laibin, WANG Zhaohui, et al. Application of an improved ISODATA method to pipeline leak detection[J]. Petroleum Science, 2007, 4(2): 97-104.

[13] 路敦利, 宁芊, 臧军. 基于BP神经网络决策的KNN改进算法[J]. 计算机应用, 2017, 37(增刊2): 65-67, 88.

[14] 朱付保, 谢利杰, 汤萌萌, 等. 基于模糊C-Means的改进型KNN分类算法[J]. 华中师范大学学报(自然科学版), 2017, 51(6): 754-759.

[15] 陈海彬, 郭金玉, 谢彦红. 基于改进K-means聚类的kNN故障检测研究[J]. 沈阳化工大学学报, 2013, 27(1): 69-73.

Clustering model of BDS scene accuracy level in complex environment

FAN Yajun1, WANG Ping1, YU Wenxian2, HE Di2

（1. School of Information Science and Technology, Donghua University, Shanghai 200051, China；2. School of Electronics, Information and Electrical Engineering, Shanghai Jiao Tong University, 200040, China）

Aiming at the problem of insufficient positioning accuracy of Beidou navigation in real complex scenes, a BDS adaptive scene ISODATA clustering algorithm based on NMEA protocol is proposed to assist BDS terminal to adopt appropriate compensation strategy for different scenarios.That is, the scene feature clustering is extracted from the real-time NMEA message and the environmental feature indicators related to BDS positioning, and the navigation scene is automatically classified and matched according to the BDS accuracy level, and the supervised KNN method is used to accurately cluster the ISODATA scene. The experiment combines the actual road test data in complex urban environment (Shanghai), extracts the results of the BDS navigation scene clustering model and the corresponding matching accuracy level, and gives 12 kinds of automatic clustering corresponding to different road segments in 7 typical scenes reproduced on google map. Matching accuracy, and the corresponding positioning accuracy deviation mean. The experimental results show that the mean square error of this clustering method is obviously better than other clustering methods after multiple iterations. According to the accuracy of the road test, the clustering level range (the nearest 0.02 meters, the farthest is about 3 meters) The corresponding recommendations for accuracy compensation also verify the validity of the model.

BeiDou navigation satellite system; navigation scene clustering; positioning accuracy clustering level; NMEA message; adaptive scene clustering algorithm

P228

A

2095-4999(2019)04-0064-06

范亚军，王萍，郁文贤，等.复杂环境下BDS场景精度等级聚类模型[J].导航定位学报,2019,7(4): 64-69.（FAN Yajun, WANG Ping, YU Wenxian, et al.Clustering model of BDS scene accuracy level in complex environment[J].Journal of Navigation and Positioning, 2019, 7(4): 64-69.）

10.16547/j.cnki.10-1096.20190412.

2019-04-26

范亚军（1995—），男，江苏泰州人，硕士生，研究方向为北斗车道级高精度定位。

王萍（1973—），女，河南人，博士后，教授，研究方向为5G车联网方向。