范亞軍，王 萍，郁文賢，何 迪

復雜環(huán)境下BDS場景精度等級聚類模型

范亞軍1，王 萍1，郁文賢2，何 迪2

（1. 東華大學信息科學與技術學院，上海 200051；2. 上海交通大學電子信息與電氣工程學院，上海 200040）

針對實際復雜場景下北斗衛(wèi)星導航系統(tǒng)（BDS）導航定位精度不足問題，提出一種基于美國國家海洋電子協(xié)會（NMEA）協(xié)議的BDS自適應場景迭代自組織數(shù)據(jù)分析技術(ISODATA)聚類算法,以輔助BDS終端針對不同場景采取合適精度的補償策略，即從實時NMEA報文提取與BDS定位相關的環(huán)境特征指標進行場景聚類分析，依據(jù)BDS精度等級對導航場景進行自動分類和精度匹配,并采用有監(jiān)督的k近鄰算法（kNN）對ISODATA場景聚類結果的準確度進行評估。實驗結合（上海）復雜城市環(huán)境下的實際路測數(shù)據(jù)，提取BDS導航場景聚類模型結果及相應的匹配精度等級，給出谷歌（Google）地圖上再現(xiàn)7類典型場景下不同路段對應的12種自動聚類匹配精度，以及相應的定位精度偏差均值。實驗結果表明：此聚類方法的均方誤差多次迭代后效果明顯優(yōu)于其他聚類方法，根據(jù)本次路測可識別的精度聚類等級范圍（最近0.02 m、最遠約3 m）給出精度補償?shù)南鄬慕ㄗh，也驗證了模型的有效性。

北斗衛(wèi)星導航系統(tǒng)；導航場景聚類；定位精度聚類等級；NMEA報文；自適應場景聚類算法

0 引言

北斗衛(wèi)星導航系統(tǒng)（BeiDou navigation satellite system, BDS）作為中國科技發(fā)展重要戰(zhàn)略之一，受到廣泛重視。順應國家的軍民融合[1]政策，BDS導航加快空間衛(wèi)星部署的同時，也加快了BDS終端民用化商用進程。面對未來智能交通[2]、無人駕駛等系統(tǒng)對于高精度導航定位的需求，BDS導航定位的精度是備受研究關注的核心問題，尤其是實際復雜的地面應用環(huán)境對BDS終端的挑戰(zhàn)。而對精度影響較大的因素有多種：文獻[3]介紹了通過對電離層的檢測并對比BDS和全球定位系統(tǒng)（global positioning system, GPS），BDS對電離層的檢測并補償可以有效地提升定位精度；文獻[4]介紹了通過對載波相位多徑效應的抑制來提升定位精度；文獻[5]討論了通過多全球衛(wèi)星導航系統(tǒng)（global navigation satellite system, GNSS）的組合實施精確定位；文獻[6]基于慣導對BDS和GPS模糊度固定的研究以提高載波相位觀測的準確性；文獻[7]通過手機慣導進行地下定位的研究；文獻[8]基于車路協(xié)同，在弱收星或無收星的路段通過路邊單元與車載單元通信的方式實時播報定位信息以獲得高精度定位。

由于實際導航環(huán)境復雜，各種因素綜合影響B(tài)DS導航精度，單一的精度補償輔助方法并不能完全解決各種場景下BDS定位精度問題，近來，多源融合導航[9-11]采用不同技術的數(shù)據(jù)融合來共同輔助定位導航，實現(xiàn)高精度定位導航，已成為BDS實際應用的發(fā)展趨勢。然而，現(xiàn)場路測表明，由于缺乏對不同場景下BDS精度自動識別、分類的手段，融合定位系統(tǒng)的實際應用效果不能很好地與實際環(huán)境相匹配。

為輔助BDS導航設備選擇合適的精度補償策略，加強BDS實際應用精度的評測，對BDS導航環(huán)境提供科學的場景分類依據(jù)十分重要。本文提出一種復雜環(huán)境下BDS導航場景精度等級自動聚類的科學建模方法，結合美國國家海洋電子協(xié)會（The National Marine Electronics Association, NMEA）通訊協(xié)議設計了BDS參數(shù)化迭代自組織數(shù)據(jù)分析技術（iterative self-organizing data analysis techniques algorithm, ISODATA）聚類算法[12-15]，以期較通常的聚類方法更好地提高模型匹配精度，獲得更精確的精度識別效果，實現(xiàn)實際導航場景精度等級的自動識別。

1 BDS導航場景聚類模型

基于真實場景的BDS路測數(shù)據(jù)建立場景聚類模型，總體流程如圖1所示。

圖1 場景聚類模型設計流程

首先對標準的BDS NMEA協(xié)議報文中提取5類對BDS導航精度影響較大的指標作為場景聚類特征屬性，具體指標定義如表1所示。

表1 場景指標

基于以上5類指標對樣本點賦予這5類屬性，并配置一個場景標簽屬性，則樣本點可表征為

其中每個樣本點屬于1個聚類中心。

對于樣本點進行ISODATA算法的處理以及精度計算，并進行場景和精度的匹配；然后對此聚類模型進行性能評估。

2 基于ISODATA的自適應場景聚類

2.1 ISODATA算法原理

ISODATA相較于傳統(tǒng)k均值聚類算法（k-means clustering algorithm, k-means）可以更加有效地實行聚類，并可以對實際應用情況下聚類中心數(shù)目不確定性給出科學的表征。而現(xiàn)場實測的BDS數(shù)據(jù)受環(huán)境影響，其精度具有隨機且離散的特征，因此ISODATA可變值的特點有助于提升BDS數(shù)據(jù)無監(jiān)督聚類的準確性和靈活性。

ISODATA算法稱為是迭代自組織數(shù)據(jù)分析法，此算法可以在整個聚類過程中根據(jù)各個類的實際狀況動態(tài)調(diào)整聚類中心的數(shù)目。

ISODATA基于方差對類進行衡量，如果其中某個類方差較大即離散程度較大，則進行分裂操作，增加聚類中心數(shù)目；如果2類聚類中心距離很近則進行合并操作，減少聚類中心數(shù)目。

2.2 場景聚類

本文采用ISODATA聚類算法對BDS路測數(shù)據(jù)依據(jù)定位精度的不同效果進行自動分類，以獲取BDS場景聚類模型。建模的方法如下：

1）參數(shù)初始化，預期的聚類中心為

執(zhí)行IOSDATA分裂操作流程：

計算每個聚類中心的簇內(nèi)樣本方差

待拆分的簇分類2個子簇，其中心向量分別為

中心向量拆分完畢后，再對所有樣本進行重新劃分，并再次計算簇的匹配度和樣本的準確率。

執(zhí)行IOSDATA合并操作流程：

計算剩余簇中心向量兩兩之間的距離，以矩陣表示聚類中心間的距離，其中

6）多次迭代，待均方誤差達到穩(wěn)定時結束迭代，對每次迭代后的樣本集進行準確率計算。

2.3 聚類匹配性能評估

使用有監(jiān)督的k近鄰法（k-nearest neighbor, kNN）分類方式對ISODATA這種無監(jiān)督聚類模型進行匹配性能評估。

對于待測試樣本選取其歐式距離最近的個樣本點作為評估參考，的定義為

式中為總樣本數(shù)目。

從最近的個樣本中出現(xiàn)頻次最多的聚類標簽作為評估標簽。通過評估標簽和原先聚類標簽做對比，觀察待測聚類樣本標簽匹配正確率，匹配正確率高的聚類模型較優(yōu)。

2.4 聚類定位精度

每個樣本數(shù)據(jù)利用其經(jīng)緯度坐標對應該點處

3 實驗及結果分析

3.1 現(xiàn)場測試儀表和環(huán)境

現(xiàn)場測試由上海北斗導航創(chuàng)新研究院合作支持，測試路線覆蓋上海徐家匯地區(qū)的空曠、樹林、河邊、城市街區(qū)、高架、隧道、跨江大橋等多種場景，路線長度不少于120km。路測采集如圖2所示。

圖2 數(shù)據(jù)采集基本流程

通過對射頻信號的采集并回放基于協(xié)議解析的數(shù)據(jù)報文，從中提取可用指標用于場景聚類分析。

測試車車頂安裝天線裝置，接收射頻信號饋入車內(nèi)的2套BDS采集設備，一套為存儲波形數(shù)據(jù)的Spirent設備，一套為實時采集分析輸出的NovAtel設備，最后將衛(wèi)星波形數(shù)據(jù)轉(zhuǎn)化為衛(wèi)星數(shù)據(jù)的標準輸出數(shù)據(jù)。測試采集車如圖3所示。

圖3 測試數(shù)據(jù)采集設備

3.2 BDS測試樣本的聚類結果分析

對上述樣本集合采用ISODATA算法進行聚類。

聚類后的場景數(shù)目如圖4所示。ISODATA聚類算法在迭代10次以后將場景類別數(shù)目自適應調(diào)整為12個，聚類結果見圖5所示，僅列出2個場景的示例。ISODATA算法基本實現(xiàn)了場景的顯著分割。

圖4 ISODATA算法聚類后的場景數(shù)

圖5 ISODATA算法聚類后的部分簇分布

圖6列出了分別經(jīng)過1到10次迭代后2類算法的簇內(nèi)樣本均方誤差的平均值。在小樣本的聚類結果中，基本經(jīng)過3次迭代后，簇內(nèi)的樣本均方誤差變化幅度明顯減小，經(jīng)過10次迭代后均方誤差已經(jīng)達到基本不變。從圖中可以看出，在多次迭代后，ISODATA的聚類算法的樣本均方誤差相較于k-means會有所降低。

圖6 k-means和ISODATA的均方誤差對比

3.3 聚類模型匹配準確率的KNN評估

通過對迭代10次、樣本聚類穩(wěn)定后的k-means聚類樣本集和ISODATA聚類樣本集分別取1/3的樣本作為訓練樣本，并用剩下的2/3的樣本點進行kNN訓練，并得出2類聚類算法得出的樣本集的場景分類準確率（如表2所示）。

表2 k-means和ISODATA訓練比對結果

由上表可以看出，經(jīng)ISODATA聚類后的樣本集的kNN分類準確率較傳統(tǒng)k-means標簽的準確率提升更為明顯。

3.4 場景聚類模型結果

表3為聚類結束后自適應生成的12個場景類別的樣本精度誤差平均值，場值與精度的對比如圖7所示。表4給出典型路段的環(huán)境描述。

從表3和圖7的對照可以看出雖然于指標和對應精度之間有密切的關系，但還是有部分差異存在，基本上在指標較好的情況下其定位精度也較為優(yōu)良。

表3 場景定位精度對比表

圖7 場景指標均值與精度對比

表4 典型路段參考環(huán)境

雖然標定設備在不同路段會存在不同程度的誤差，但是從相對誤差來看，的確在遮擋嚴重的路段上定位精準度有所下降。

3.5 場景的精度補償策略

現(xiàn)場路測樣本回放后的BDS數(shù)據(jù)聚類的谷歌（Google）地圖還原結果如圖8所示，將聚類后自適應生成的12個場景的樣本集分別疊加到地圖中可以明顯發(fā)現(xiàn)，在一些拐彎處，高樓和樹蔭遮擋處場景會較為惡劣，相應的導航定位效果也會變差很多。

圖8 ISODATA算法樣本聚類結果

對不同的場景類別和典型路段采用不同定位補償策略，例如：在定位效果較好的開闊地（場景1~2），現(xiàn)有的導航結合實時動態(tài)載波相位差分（real time kinematic, RTK）技術在無惡劣天氣影響的情況下基本可以實現(xiàn)分米級的定位效果；對于在較為輕微的遮擋下（場景3~5）使用GNSS配合RTK也可實現(xiàn)分米級的定位，但效果較開闊地略差一點，不過依舊可以顯示高精度的定位導航服務；但對于樹蔭或高樓遮擋的情況下（場景6~9），會出現(xiàn)間歇性的衛(wèi)星失鎖，再重捕獲衛(wèi)星會出現(xiàn)周跳，可以通過慣導在短時間內(nèi)的高精度補償性能實現(xiàn)部分失鎖狀態(tài)的定位及周跳修復，對于在隧道高架下等基本無收星的情況下（場景10~12）可以通過慣導加路邊單元的實時位置播報實現(xiàn)較高精度的導航定位。

4 結束語

基于k-means算法的k值存在不確定性以及對海量數(shù)據(jù)處理的速度較慢，提出了IOSDATA算法來優(yōu)化聚類的性能：以BDS的實測數(shù)據(jù)來進行聚類，多次迭代后形成較為合理的場景分類；將地理位置精度和測試樣本點的分類結果進行對比，測算方差。實驗結果表明，ISODATA聚類算法相較于普通k-means聚類算法樣本的匹配度更高。在較高的匹配度下，場景分類更為準確，BDS接收機僅從接收的衛(wèi)星數(shù)據(jù)就可以測算出當前輸入哪類場景，是哪些典型的路段，對于這些典型的路段可以采取對應的BDS高精度技術來彌補相應惡劣場景下的精度缺陷，以實現(xiàn)多場景下的自適應高精度導航。

[1] 李齡, 宋超. 強通信導航裝備軍民融合維修保障建設的幾點思考[J]. 機電信息, 2018(30): 159-160.

[2] 劉小洋, 伍民友. 車聯(lián)網(wǎng): 物聯(lián)網(wǎng)在城市交通網(wǎng)絡中的應用[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] 羅文慧, 董寶田, 王澤勝. 基于車路協(xié)同的車輛定位算法研究[J]. 西南交通大學學報, 2018, 53(5): 1072-1077, 1086. DOI: 10. 3969/j. issn. 0258-2724. 2018. 05. 026.

[9] 段睿, 張小紅, 朱鋒. 多源信息融合的組合導航自適應聯(lián)邦濾波算法[J]. 系統(tǒng)工程與電子技術, 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神經(jīng)網(wǎng)絡決策的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

范亞軍，王萍，郁文賢，等.復雜環(huán)境下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車聯(lián)網(wǎng)方向。