侯寧寧,李燈熬,趙菊敏

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

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

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

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

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

1.1 GNSS信號特征提取分析

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

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

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

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

1.2 k-means算法

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

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

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

1.3 核k-means聚類算法

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

2)聚類。計(jì)算每條記錄與質(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ù)點(diǎn)從空間輸入映射到高維特征空間。在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為樣本集,?指圈乘運(yùn)算。得到核函數(shù):

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

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

2 粒子濾波定位算法

步驟1粒子初始化處理。對GPS接收機(jī)輸出的原始測量值進(jìn)行初始化處理,接收機(jī)輸出的原始偽距集ρ=[ρ1,ρ2,…,ρN]T和經(jīng)接收機(jī)計(jì)算得到的參考位置y,用來初始化位置候選點(diǎn)。使用該方法實(shí)現(xiàn)位置估計(jì),需要4顆及以上GNSS衛(wèi)星提供的原始偽距測量值。首先分配位置候選點(diǎn)P(i)=(x(i),y(i)),i為候選點(diǎn)的編號。用隨機(jī)分布在參考位置的二維高斯分布粒子來表示候選點(diǎn)。在先前的估計(jì)位置x(t-Δt)也要放置粒子,t為選取的位置候選點(diǎn)對應(yīng)的采樣時(shí)間。在重采樣期間,選擇正態(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)過非視距排除后重新選擇的偽距觀測量個(gè)數(shù)。

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

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

3 基于UL-PF算法

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

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

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

式中:S(i)代表時(shí)間序列分析和核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)的偽距觀測量,選擇位置候選點(diǎn)和粒子初始化處理,將第2節(jié)介紹的GNSS信號分類結(jié)果作為NLOS信號檢測結(jié)果,用來參與后續(xù)偽距差的計(jì)算;然后,將優(yōu)化后的粒子濾波器用來優(yōu)化接收機(jī)定位結(jié)果,同時(shí),核kmeans聚類算法更新粒子權(quán)重用來評估位置候選點(diǎn);最后,將優(yōu)化后衛(wèi)星導(dǎo)航系統(tǒng)的偽距觀測量,參與最終的定位結(jié)果解算。

4 實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)環(huán)境

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

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

4.2 定位性能對比

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

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

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

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

4.3 算法性能對比

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

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

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

為進(jìn)一步證明本文提出的UL-PF算法性能,圖5為復(fù)雜環(huán)境和空曠環(huán)境中定位誤差。復(fù)雜環(huán)境中,傳統(tǒng)粒子濾波(particle filter,PF)算法定位誤差平均值約為6m,UL-PF算法平均值在3m左右,并且波動(dòng)幅度較小,定位性能較為穩(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和擴(kuò)展卡爾曼濾波(extended Kalman filter,EKF)算法進(jìn)行對比。圖6(a)顯示了使用單個(gè)LEO衛(wèi)星的平均定位精度的仿真結(jié)果。縱軸表示平均定位精度。測量數(shù)據(jù)中含有大量的NLOS數(shù)據(jù),導(dǎo)致傳統(tǒng)算法定位精度較差,收斂時(shí)間較長。當(dāng)測量時(shí)間達(dá)到350s時(shí),傳統(tǒng)方法的精度逐漸收斂到6m左右。與傳統(tǒng)算法相比,基于非監(jiān)督學(xué)習(xí)NLOS排除的定位方法大大降低了NLOS誤差的影響,使定位精度顯著提高,收斂時(shí)間縮短當(dāng)測量時(shí)間達(dá)到200s時(shí),定位精度約為6m;當(dāng)測量時(shí)間達(dá)到400s時(shí),定位精度收斂到約3m。

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

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

5 結(jié) 論

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

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

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

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