侯寧寧,李燈熬,趙菊敏

(1.太原理工大學(xué) 信息與計算機學(xué)院,太原 030024; 2.山西省空間信息網(wǎng)絡(luò)工程技術(shù)研究中心,太原 030024;3.太原理工大學(xué) 大數(shù)據(jù)學(xué)院,太原 030024)

非視距和多徑信號是影響全球衛(wèi)星導(dǎo)航系統(tǒng)(global navigation satellite system,GNSS)定位精度困難大的誤差源之一。反射或非視距信號與直接視距信號結(jié)合時,會產(chǎn)生不必要的多徑效應(yīng),仍然是誤差的主要來源[1-2]。多徑不能通過差分技術(shù)去除,從而限制了多徑易發(fā)區(qū)域的定位精度[3-4]。檢測和抑制非視距(non line of sight,NLOS)方法主要分為3類:基于天線方面的雙極化天線[5],基于接收機方面的先進接收機設(shè)計和傳感器集成[6],基于導(dǎo)航處理器方面的三維建筑模型[7]。由于現(xiàn)實環(huán)境中非視距信號的復(fù)雜性,他們都需要外部硬件或最新的地圖,這些昂貴的或不實際的大眾市場應(yīng)用程序,僅使用單一的檢測方法無法達到滿意的效果。

近年來,一些學(xué)者提出利用機器學(xué)習(xí)方法區(qū)分非視距信號。文獻[8]提出使用支持向量機識別視距/非視距(line of sight/non line of sight,LOS/NLOS)場景。文獻[9]提出了一種新的基于有監(jiān)督機器學(xué)習(xí)算法的LOS/NLOS分類方法。上述研究都是基于監(jiān)督學(xué)習(xí)的GNSS信號分類方法,需事先對學(xué)習(xí)樣本進行標(biāo)記,因此,需要借助額外的硬件或軟件。無監(jiān)督學(xué)習(xí)是一種對不含標(biāo)記的數(shù)據(jù)建立模型的機器學(xué)習(xí)方法。文獻[10]提出一種無監(jiān)督機器學(xué)習(xí)的數(shù)據(jù)聚類方法,將測量數(shù)據(jù)分為LOS信號和NLOS信號。文獻[11]提出采用“高斯混合模型的期望最大化”的無監(jiān)督機器學(xué)習(xí)方法,對LOS和NLOS分量進行分類,但2種方法均應(yīng)用于室內(nèi)無線信號,借鑒該思路可以將無監(jiān)督學(xué)習(xí)對信號的分類應(yīng)用于GNSS信號,同時為了解決傳統(tǒng)k-means算法對簇中心敏感的問題,使用了核k-means聚類算法,旨在提高GNSS設(shè)備在復(fù)雜環(huán)境下的定位精度,可以避免額外軟硬件的使用,提高運算效率。對于定位優(yōu)化部分,本文提出無監(jiān)督學(xué)習(xí)-粒子濾波(unsupervised learning-particle filtering,UL-PF)算法為提高定位精度做2次保障。

聚類是一種無監(jiān)督的學(xué)習(xí)分組技術(shù),其提供了一種自動形成相似事物聚類的方法,這就像自動分類[12]。粒子濾波是一種視覺跟蹤工具,依賴于蒙特卡羅鏈框架和貝葉斯估計,適用于非線性和非高斯系統(tǒng)[13]。文獻[14]提出采用粒子濾波方法結(jié)合行人航位推算算法和磁性指紋圖譜有效提高室內(nèi)定位的精度和效率。文獻[15]提出了一種基于遺傳算法的簡化粒子濾波方法。文獻[16]提出了一種改進蒙特卡羅定位算法的概率激光定位方法,通過加入卡爾曼濾波后的GNSS信息來增強粒子權(quán)值,從而提高自主車輛定位精度。文獻[17]根據(jù)粒子的狀態(tài)值將采樣粒子集合的狀態(tài)空間劃分為可變大小的可數(shù)測度空間,實驗結(jié)果表明,在空間域?qū)Σ蓸恿Ｗ舆M行簡單的啟發(fā)式劃分后,性能有顯著的提高。因而可以進一步研究一種挖掘采樣粒子空間分布相關(guān)信息的有效方法。

對于定位優(yōu)化部分,本文使用通過聚類算法優(yōu)化的粒子濾波方法,為提高定位精度做二次保障。首先,提出了一種基于核k-means聚類算法的采樣粒子狀態(tài)空間分割方法,該方法考慮了采樣粒子在狀態(tài)空間分布中的內(nèi)在相似性。其次,探索在每個聚類中選擇一個粒子作為重要粒子,利用時間序列相關(guān)技術(shù)提高重采樣粒子集的多樣性。最后,通過偽距殘差似然函數(shù)有效性檢驗,證明了該算法重采樣的粒子集與原始粒子集來自同一分布。實驗結(jié)果表明,與傳統(tǒng)粒子濾波算法相比,所提算法能獲得更準確的估計。

1 GNSS信號核k-means聚類算法

1.1 GNSS信號特征提取分析

使用無監(jiān)督學(xué)習(xí)對GNSS信號進行分類的關(guān)鍵是從原始觀測數(shù)據(jù)中提取主要特征。原始數(shù)據(jù)一般包含偽距、載波相位、載噪比和多普勒頻移等,他們都與GNSS信號類型有著密切的聯(lián)系。而任何單一特征都不可能對GNSS信號進行有效的分類,因此,需要通過不同特征的組合來提高分類的準確性。

1)載噪比。一般來說,LOS載噪比較高,而NLOS載噪比較低。在城市峽谷環(huán)境中,經(jīng)過光滑的建筑物表面反射后,NLOS信號的強度可能與LOS強度相當(dāng),這種情況下,僅利用載噪比已經(jīng)難以將二者區(qū)分開來。

2)偽距殘差。當(dāng)觀測環(huán)境較好時,偽距殘差偏大的對應(yīng)NLOS,但當(dāng)觀測環(huán)境不好時,可見衛(wèi)星少于4顆時,此時的觀測方程不再超定,偽距殘差為0,不足以作為區(qū)分指標(biāo)。

3)衛(wèi)星高度角。通常情況下,LOS衛(wèi)星的高度角較大,而城市峽谷環(huán)境中,可見衛(wèi)星能見度差,LOS衛(wèi)星被高樓遮擋,衛(wèi)星高度角也比較大,因此使用衛(wèi)星高度角可能出現(xiàn)誤判,還會破壞衛(wèi)星的幾何分布。

1.2 k-means算法

對于復(fù)雜環(huán)境下GNSS接收機接收到的衛(wèi)星信號一般分為LOS、多徑和NLOS信號3類,每一類信號都與載噪比、偽距殘差和衛(wèi)星高度角有一定的內(nèi)在聯(lián)系。根據(jù)這一特性,本文采用核kmeans算法進行信號的聚類,當(dāng)其中樣本離聚類中心最近時,即歸為該類。對于給定的一組樣本集X={x1,x2,…,xN},xN={rn,vn,en}為標(biāo)準化載噪比、偽距殘差和衛(wèi)星高度角組成的特征向量,N為樣本數(shù),n為樣本的特征向量下標(biāo),k-means算法將其劃分為M個簇C1,C2,…,CM,使得每個數(shù)據(jù)點與其最近的聚類中心的滿足平方歐幾里得距離和最小,即

式中:xi為樣本,i為樣本編號;I為M個簇中選取的樣本數(shù)據(jù)集;k為簇的編號;mk為均值向量,表達式為

k-means算法的缺點是:最終的分類結(jié)果取決于集群中心的起始位置,且星團是線性分開的。為了克服這個問題,選擇使用核k-means聚類算法[18]。核k-means聚類算法通過使用k-means算法中包含N個數(shù)據(jù)大小的初始位置的確定性全局,一次動態(tài)添加一個聚類中心[19]。

1.3 核k-means聚類算法

1)初始化。在數(shù)據(jù)集中隨機選取K作為初始質(zhì)心cp,1≤p≤K,p為樣本數(shù)量,K為數(shù)據(jù)集的數(shù)量。

2)聚類。計算每條記錄與質(zhì)心之間的相似度sim(ri,cp),并將記錄ri分配給相似的cp質(zhì)心。

4)終止條件。所有舊質(zhì)心的矩陣為Θ=[c1,c2,…,cK]T,1≤p≤K,所有新質(zhì)心的矩陣為Θ′=[c′1,c′2,…,c′K]T,下一步,歐幾里得距離為

式中:vp,i和v′p,i分別為cp和c′p的質(zhì)心元素。

核k-means聚類算法是k-means算法的推廣,通過非線性變換Φ數(shù)據(jù)點從空間輸入映射到高維特征空間。在k-means算法核中,由于重疊數(shù)據(jù)在新的維度空間中可以是線性的,因此,期望數(shù)據(jù)能夠很好地分開[18]。

用核k-means聚類算法約簡的目標(biāo)函數(shù)等同于特征中的分組誤差,如下[19]:

式中:Kii、Kij和Kjl分別為對應(yīng)樣本ii、ij、jl的徑向基函數(shù)的核函數(shù),本文選擇徑向基函數(shù)(RBF),B-Spline核定義在區(qū)間[-1,1]上。由遞歸公式給出:

式中:p∈X且Bi+1=B?B0,X為樣本集,?指圈乘運算。得到核函數(shù):

使用徑向基函數(shù)核k-means聚類算法,通過式(3)～式(8),所有的GNSS信號都被歸類到不同的集群,k-fold將樣本數(shù)據(jù)劃分為m個部分,復(fù)雜環(huán)境中GNSS信號通常分為LOS、多徑和NLOS共3類,因此選擇k-fold=3。由于衛(wèi)星與終端的距離保持在一定的范圍內(nèi),LOS環(huán)境中同步的峰值信噪比(PSNR)也會相應(yīng)保持在一個區(qū)間內(nèi)。采用無監(jiān)督機器學(xué)習(xí)的數(shù)據(jù)聚類方法,將實測數(shù)據(jù)分為LOS、NLOS和多徑信號。圖1為基于核kmeans聚類算法的GNSS信號的仿真分類結(jié)果。圖1(a)為分類前只能已知目前存在3種信號,但無法判別和區(qū)分,圖1(b)為加入特征向量提取后的聚類方法可以識別3種信號分別對應(yīng)的分類,藍色為多徑,紅色為LOS,綠色為NLOS,橫軸為偽距殘差ρ,縱軸為PSNR。NLOS的PSNR為負值,多徑與LOS的PSNR為正值,而且多徑的偽距殘差大于LOS。結(jié)果表明,在二維狀態(tài)空間中,按一定的度量被分成3個簇。不同的分類結(jié)果以不同的顏色顯示,可以看到具有特定屬性的信號聚類在一起,而不是簡單的分割。最后,利用本節(jié)所述的信號分類方法,便可見判定衛(wèi)星信號是LOS還是NLOS傳播,需從偽距觀測量中剔除該衛(wèi)星的信號。將受NLOS效應(yīng)干擾嚴重的衛(wèi)星剔除,獲得精度更高的偽距觀測量,為后續(xù)優(yōu)化定位算法做準備。

圖1 基于核k-means算法的GNSS信號仿真分類結(jié)果Fig.1 GNSS signal simulation classification results based on kernel k-means algorithm

2 粒子濾波定位算法

步驟1粒子初始化處理。對GPS接收機輸出的原始測量值進行初始化處理,接收機輸出的原始偽距集ρ=[ρ1,ρ2,…,ρN]T和經(jīng)接收機計算得到的參考位置y,用來初始化位置候選點。使用該方法實現(xiàn)位置估計,需要4顆及以上GNSS衛(wèi)星提供的原始偽距測量值。首先分配位置候選點P(i)=(x(i),y(i)),i為候選點的編號。用隨機分布在參考位置的二維高斯分布粒子來表示候選點。在先前的估計位置x(t-Δt)也要放置粒子,t為選取的位置候選點對應(yīng)的采樣時間。在重采樣期間,選擇正態(tài)分布生成粒子,一半粒子的分布為N(y(t),Σ0),Σ0表示正態(tài)分布粒子的均值,另一半粒子的分布為N(x(t-Δt),ΣΔt)。在城市環(huán)境定位場景中,行人在1s內(nèi)發(fā)生劇烈位置變化的可能性極低,因此,可以利用歷元x(t-Δt)的位置信息。

式中:Nsim為經(jīng)過非視距排除后重新選擇的偽距觀測量個數(shù)。

步驟3評估候選點位置。偽距相似性決定每個候選點的似然函數(shù)α(i)(t)(i=1,2,…,NP),似然函數(shù)計算如下:

步驟4輸出定位結(jié)果。對所有有效樣本不同時刻位置P(i)(t)加權(quán)平均,為最終粒子濾波校正位置提出的方法的定位結(jié)果為

3 基于UL-PF算法

本節(jié)工作是利用核k-means聚類算法進一步研究采樣粒子的空間分布特征,然后在每個聚類中通過時間和序列分析選擇一些被稱為重要粒子的粒子,以增強重采樣粒子的多樣性。核kmeans聚類算法通過研究采樣粒子的空間分布特征,通過時間和序列分析選擇一些重要粒子,以增強粒子濾波重采樣粒子的多樣性,能夠緩解粒子退化,將優(yōu)化后粒子濾波算法用來后續(xù)評估候選點位置,可以提高衛(wèi)星導(dǎo)航系統(tǒng)的定位精度。

2)使用核k-means聚類算法將候選粒子集劃分為帶有Np個粒子的聚類gk:

3)選擇每個類中下一次篩選的重要粒子:

式中:S(i)代表時間序列分析和核k-means選擇結(jié)果。

4)將第1步中復(fù)制的粒子設(shè)置為相同的權(quán)重:

綜上所述,本文的優(yōu)化定位過程如下:首先,使用北斗衛(wèi)星導(dǎo)航系統(tǒng)(beidou navigation satellite system,BDS)衛(wèi)星導(dǎo)航系統(tǒng)的偽距觀測量,選擇位置候選點和粒子初始化處理,將第2節(jié)介紹的GNSS信號分類結(jié)果作為NLOS信號檢測結(jié)果,用來參與后續(xù)偽距差的計算;然后,將優(yōu)化后的粒子濾波器用來優(yōu)化接收機定位結(jié)果,同時,核kmeans聚類算法更新粒子權(quán)重用來評估位置候選點;最后,將優(yōu)化后衛(wèi)星導(dǎo)航系統(tǒng)的偽距觀測量,參與最終的定位結(jié)果解算。

4 實驗結(jié)果

4.1 實驗環(huán)境

實驗過程使用u-blox NEO-M8N GNSS接收器和SIS600B1L1中頻采樣器采集數(shù)據(jù),實驗設(shè)備如圖2(a)、(b)、(d)所示,測試數(shù)據(jù)的采集地點選擇山西太原小店區(qū)太航小區(qū),這一區(qū)域是城市環(huán)境中常見的雙側(cè)街道環(huán)境,實驗環(huán)境如圖2(c)所示。

圖2 實驗條件與數(shù)據(jù)采集Fig.2 Experimental conditions and data acquisition

4.2 定位性能對比

仿真基于BDS衛(wèi)星的星歷數(shù)據(jù),行人動態(tài)數(shù)據(jù)集的軌跡圖及按照本文算法的信號分類結(jié)果如圖3所示。圖3(a)表示分類前的候選點分布圖,圖3(b)根據(jù)分類結(jié)果評估位置候選點,在A、B區(qū)域沒有受到跨街街道的影響,LOS衛(wèi)星可見數(shù)目較多,由于受到四周高樓遮擋,在C、D、E橫街區(qū)域接收到NLOS衛(wèi)星較多。核k-means聚類算法更準確的確認采樣點,識別出NLOS衛(wèi)星,則排除該采樣點,從而提高粒子濾波算法定位精度。

圖3 位置候選點分布及分類結(jié)果Fig.3 Distribution of location candidate points and classification results

圖4為動態(tài)場景下定位誤差對比。A、B段LOS衛(wèi)星較多,定位效果較好,A段誤差比B段大,是因為A段建筑物周圍還有樹木遮擋。C、D、E段NLOS衛(wèi)星較多,未剔除NLOS干擾前誤差 甚至高達25m,而且誤差曲線不規(guī)則不光滑,嚴重影響定位精度。確定C、D、E段信號分類結(jié)果后,將剔除NLOS衛(wèi)星再進行計算,而剔除NLOS后的誤差在5m左右,表明NLOS信號會給定位帶來一定程度的系統(tǒng)誤差,正確地去除NLOS能夠有效地緩解這種系統(tǒng)誤差。

圖4 動態(tài)場景中剔除NLOS前后定位誤差Fig.4 Positioning error before and after NLOS elimination in dynamic scene

4.3 算法性能對比

表1給出了核k-means聚類算法與現(xiàn)有的監(jiān)督機器學(xué)習(xí)算法、k-最近鄰(KNN)、樸素貝葉斯(NB)、決策樹(DT)和最小二乘支持向量機(LSSVM)的計算復(fù)雜度和性能比較。為簡單起見,使用運行時間來度量計算復(fù)雜度。仿真中,分別生成500個LOS波形和500個NLOS波形來訓(xùn)練有監(jiān)督機器學(xué)習(xí)算法,不同算法的性能對比如表1所示。

表1 不同算法對比Table1 Comparison of different algorithms

從表1中可以看出,無監(jiān)督機器學(xué)習(xí)核kmeans聚類算法與有監(jiān)督機器學(xué)習(xí)算法相比,在性能上有一定的差異,但由于沒有訓(xùn)練階段,所以不需要訓(xùn)練數(shù)據(jù)。核k-means聚類算法只需要最先進的監(jiān)督機器學(xué)習(xí)LS-SVM所需的44%的運行時間,但其實現(xiàn)了LS-SVM算法幾乎相同的NLOS檢測準確度。

為進一步證明本文提出的UL-PF算法性能,圖5為復(fù)雜環(huán)境和空曠環(huán)境中定位誤差。復(fù)雜環(huán)境中,傳統(tǒng)粒子濾波(particle filter,PF)算法定位誤差平均值約為6m,UL-PF算法平均值在3m左右,并且波動幅度較小,定位性能較為穩(wěn)定?？諘绛h(huán)境中,傳統(tǒng)粒子濾波算法定位誤差平均3m左右,UL-PF算法平均在1.5m左右。

圖5 不同環(huán)境下本文算法與傳統(tǒng)算法定位誤差對比Fig.5 Comparison of positioning errors between the proposed algorithm and traditional algorithms in different environments

圖6將本文算法與傳統(tǒng)算法、PF和擴展卡爾曼濾波(extended Kalman filter,EKF)算法進行對比。圖6(a)顯示了使用單個LEO衛(wèi)星的平均定位精度的仿真結(jié)果?？v軸表示平均定位精度。測量數(shù)據(jù)中含有大量的NLOS數(shù)據(jù),導(dǎo)致傳統(tǒng)算法定位精度較差,收斂時間較長。當(dāng)測量時間達到350s時,傳統(tǒng)方法的精度逐漸收斂到6m左右。與傳統(tǒng)算法相比,基于非監(jiān)督學(xué)習(xí)NLOS排除的定位方法大大降低了NLOS誤差的影響,使定位精度顯著提高,收斂時間縮短當(dāng)測量時間達到200s時,定位精度約為6m;當(dāng)測量時間達到400s時,定位精度收斂到約3m。

圖6 不同算法的收斂時間和區(qū)位概率對比Fig.6 Comparison of convergence time and location probability of different algorithms

圖6(b)顯示了城市場景中的位置概率。由于衛(wèi)星定位精度和定位成功率與測量誤差密切相關(guān),本文算法對測量數(shù)據(jù)中的非視距信號進行分類排除,可以有效降低非視距信號誤差的影響,提高定位成功率。如圖6(b)所示,本文算法的成功定位概率明顯高于其他2種算法,在定位誤差為7m時,定位成功率可達99%,而傳統(tǒng)算法在定位誤差為10m時,定位成功率可分別達到97%和99%。

5 結(jié) 論

針對城市環(huán)境中非視距效應(yīng)問題,本文介紹了一種基于無監(jiān)督學(xué)習(xí)和粒子濾波的非視距信號檢測方法,進而通過優(yōu)化的粒子濾波器來優(yōu)化定位結(jié)果,為提高精度提供2次保障。實驗結(jié)果表明,剔除NLOS信號影響后,能有效提高平均定位精度和縮短算法收斂時間。

1)與傳統(tǒng)方法相比,基于非監(jiān)督學(xué)習(xí)NLOS排除的終端定位方法定位精度顯著提高,收斂時間縮短,當(dāng)測量時間達到200s時,定位精度約為6m;當(dāng)測量時間達到400s時,定位精度收斂到約3m。

2)所提方法的成功定位概率明顯高于粒子濾波和擴展卡爾曼濾波2種方法,在定位誤差為7m時,定位成功率可達99%,而傳統(tǒng)方法在定位誤差為10m時,定位成功率可分別達到97%和99%。

盡管本文針對緩解NLOS效應(yīng)已經(jīng)有一定研究成果,但仍有需要深化和改進的方面。機器學(xué)習(xí)方法對于不同的數(shù)據(jù)集場景有著不同的分類效果,本文只采用低速動態(tài)的行人數(shù)據(jù)集進行實驗,還需進一步研究接收機處于車輛實時高速動態(tài)環(huán)境下場景變化對分類效果的影響,此外,針對GNSS信號的載噪比,偽距殘差和衛(wèi)星高度角的樣本數(shù)據(jù)集,還需選擇更加合理的特征向量歸一化方法。本文所開展的研究具有一定的社會價值,可以應(yīng)用于駕考系統(tǒng)、智慧城市及無人駕駛等方面,加快城市現(xiàn)代化進程建設(shè)。