戢靜紅,張振宇,鄧 平

(西南交通大學 信息科學與技術(shù)學院,成都 611756)

0 引 言

如何消除電波的非視距(Non-Line-of-Sight,NLOS)傳播對定位精度的不利影響,多年來一直是蜂窩及各種室內(nèi)/室外無線定位系統(tǒng)迫切需要解決的一個難題。目前,對NLOS傳播帶來的誤差進行消除的技術(shù)主要分為兩類:一類是直接對測得的到達時間(Time of Arrival,TOA)等數(shù)據(jù)進行加權(quán)或修正來抑制或減弱NLOS誤差對定位的不利影響;另一類則是通過檢測視距(Line-of-Sight,LOS)環(huán)境和NLOS環(huán)境中傳播信號參數(shù)的不同統(tǒng)計特征來鑒別TOA測量數(shù)據(jù)是否包含有NLOS誤差,然后剔除掉包含NLOS誤差的NLOS基站測量數(shù)據(jù),只采用LOS基站的測量數(shù)據(jù)進行定位[1]。

對于LOS/NLOS基站進行識別的方法有多種。文獻[3]提出利用TOA測量值在先驗概率已知和未知的情況下,采用廣義似然比檢驗和一致最大功效檢驗來鑒別是否有NLOS信號,取得了較好的識別率。文獻[4]提出了一種利用到達角(Angle-of-Arrival,AOA)測量值的NLOS識別方法,先采用Neyman-Pearson(N-P)準則計算判決門限,再進行NLOS識別。文獻[5]提出了一種基于距離殘差檢測(Range Residuals Test,RRT)的識別算法,利用在LOS環(huán)境下基站到移動臺的距離與測量距離的歸一化殘差值服從卡方分布這一特性來完成NLOS基站的識別。文獻[6]提出了一種不需要信道特征的NLOS識別算法,采用距離殘差平方和作為特征來進行訓練,當只有一個NLOS基站時識別率較高,但對于多個NLOS基站的場景并未進行考慮。文獻[7]提出了基于仿射傳播聚類的 LOS/NLOS 環(huán)境識別算法,通過對多重信號分類算法得到空間譜的極值點進行聚類,根據(jù)聚類結(jié)果的分散程度來進行NLOS識別。

近年來出現(xiàn)了一些基于機器學習的識別方法。Nguyen等人[8]基于相關(guān)矢量機(Relevance Vector Machine,RVM)技術(shù),設計了一種有效的分類器來識別NLOS信號,提高了該系統(tǒng)中基于到達時間定位的準確性。文獻[9]提出了一種采用TDOA距離作為特征,通過訓練不同數(shù)目基站組合的分類器,構(gòu)成一個分類器網(wǎng)絡,將測試樣本輸入分類器網(wǎng)絡,層層檢驗,輸出為1時得到全為LOS基站的數(shù)據(jù)。該算法通過分類能得到只有LOS基站的測量值進行定位,但是沒有給出準確的識別率。文獻[10]利用卷積神經(jīng)網(wǎng)絡(Convolutional Neural Network,CNN)來處理信道沖激響應(Channel Impulse Response,CIR)的原始數(shù)據(jù),然后通過訓練分類器來完成NLOS識別。針對高分辨率CIR信息難以采樣的特點,文獻[11]設計了一種遞歸神經(jīng)網(wǎng)絡(Recursive Neural Network,RNN) 模型,它適當?shù)亟M合了跨層信息,如CIR和RSSI,通過訓練數(shù)據(jù)可有效地代替?zhèn)鹘y(tǒng)數(shù)學計算的方法來識別信道條件,即使對于在很短的時間內(nèi)獲得的數(shù)據(jù),該方法也能獲得較高的估計精度。文獻[12]利用從信道沖激響應中提取的特征參數(shù),使用隨機森林(Random Forest,RF)分類算法來處理LOS/NLOS識別問題。在許多應用中,當?shù)讓幽Ｐ碗y以近似或未知時,機器學習方法被認為是比較有效的。為此,本文提出了一種蜂窩網(wǎng)中通過隨機森林進行LOS/NLOS基站識別的方法。RF方法相比文獻[9]中的支持向量機(Support Vector Machine,SVM)方法,可以大大減少計算成本,也不用計算CIR的信息,基于各基站TOA測量值之間的相關(guān)性,利用機器學習方法準確識別出NLOS基站。與文獻[12]方法相比,本文提出的識別方法不需要頻譜分析儀等輔助設備,只需要通過獲取的發(fā)射機與接收機之間的TOA測距值即可實現(xiàn)NLOS信號的識別。

1 距離測量與定位誤差的相關(guān)性

在蜂窩網(wǎng)絡中,假設移動臺(Mobile Station,MS)在二維空間中的坐標為(x,y),基站坐標為(xi,yi),i=1,2,…,N,N表示基站總數(shù),則MS到第i個基站的真實距ri(i=1,2,…,N)為

(1)

(2)

(3)

(4)

本文選擇TOA測量距離作為分類器的輸入特征,利用每一組基站中測量距離在LOS/NLOS場景下的差異,采用隨機森林機器學習分類算法訓練得到每組基站基于這種相關(guān)性的分類器模型,即可實現(xiàn)LOS/NLOS基站的分類。

2 基于隨機森林的分類方法

隨機森林算法是一種著名的集成學習方法,其核心思想是用隨機的方式建立一個森林,該森林由許多決策樹組成,以決策樹為基分類器構(gòu)成大型多分類器。將測試數(shù)據(jù)輸入模型時,對多棵決策樹的輸出類別進行投票得到最終的預測結(jié)果。決策樹其實就是節(jié)點分裂的過程,從根節(jié)點開始不斷向下分裂,直到數(shù)據(jù)集不可再進行分裂,則決策樹停止生長。常見的決策樹分類算法包括ID3算法、C4.5算法和CART算法[13-15],這三種算法分裂規(guī)則分別是基于信息增益、信息增益率和基尼(Gini)指數(shù)。

圖1所示為一個集成分類器工作流程框架,其核心思想是:多個基分類器按規(guī)則組合,最后輸出一個最終測試結(jié)果。每一個基分類器都可以參與決策,對于分類來說,模型的最終結(jié)果由各基分類器投票決定,選用分類結(jié)果票數(shù)最多的類標簽。

圖1 集成分類器框架

本文采用基于CART算法決策的隨機森林算法。通?；嶂笖?shù)較小的屬性會被選為節(jié)點的分裂屬性,基尼指數(shù)越小樣本的“純凈度”越高,越容易從樣本中分離出來。整個分裂過程實際上是使用滿足劃分準則的特征不斷地將數(shù)據(jù)集劃分成純度更高、不確定性更小的子集的過程。

當樣本特征有K類,第k個類別的概率記為pk時,基尼指數(shù)的表達式為

(5)

如果樣本集合D根據(jù)某個特征A被分割為D1和D2兩個部分,那么在特征A的條件下,集合D的基尼指數(shù)定義為

(6)

若基尼指數(shù)值越大,樣本集合的不確定性也就越大,與熵的概念比較類似。

本文中對LOS/NLOS基站的區(qū)分,若采取將每3個基站分為一組的形式,對應的每一個組合都可以得到3個TOA距離測量值。將這3個距離測量值作為隨機森林分類器的特征,分別訓練每一種組合的分類器。同一組基站的測量距離在LOS/NLOS環(huán)境下存在較大差異,本文采用每組基站的測量距離作為特征,通過測量距離與LOS/NLOS環(huán)境的關(guān)系,根據(jù)每個特征的基尼指數(shù)來決定決策樹,然后得到基于這些決策樹的隨機森林分類器,從而進行分類。

在隨機森林算法的測試過程中,每一組觀測值都需要同時通過森林中所有的樹,從其根節(jié)點到相應的葉節(jié)點。算法輸出的預測值是基于每棵樹的多數(shù)投票,投票最多的類即為預測結(jié)果。為了得到算法的輸出預測,根據(jù)測試數(shù)據(jù)集的第i次觀測結(jié)果,樹p(p=1,2,…,P)的預測值表示為yip,在本文的LOS/NLOS二分類問題中,yip的取值為“+1”(LOS)或“-1”(NLOS),整個隨機森林算法的預測輸出為yi,其表達式如下所示:

(7)

分類結(jié)果可通過yi的假設檢驗實現(xiàn),如下式所示:

(8)

3 LOS/NLOS基站識別算法流程

在蜂窩定位系統(tǒng)中,為了能夠確保利用TOA測量距離進行定位,需要假設LOS基站個數(shù)至少為3。在此前提下,通過識別出NLOS基站,丟棄掉NLOS基站的測量數(shù)據(jù),只采用LOS基站測量得到的距離進行定位。

本文識別算法步驟如下:

Step1 在蜂窩定位區(qū)域內(nèi)布置多個位置坐標已知的基站,確定待測目標移動臺在一定范圍內(nèi)移動,測量LOS和NLOS兩種場景下移動臺與基站之間的距離。

Step3 測試時,對于每一個移動臺到各個基站的測量距離進行同樣的組合,作為對應的Ncb個分類器的輸入,輸出“+1”的組合表示該組合為LOS基站組合。由于每個LOS組合中的基站數(shù)會多次出現(xiàn)在各個組合中,因此對輸出為“+1”的組合進行去重取唯一值。如果得到的LOS基站與事先設置的LOS基站一致,則表示正確識別出LOS/NLOS基站。

將識別后的NLOS基站進行剔除,再利用剩余的LOS基站進行定位,即可得到準確的移動臺估計位置。

4 算法仿真與分析

圖2 基站與移動臺布局

4.1 仿真實驗1:分析TOA測量誤差大小對算法性能的影響

仿真中對于每一組分類器都采用移動臺位置區(qū)域內(nèi)均勻生成的2 000個LOS樣本和2 000個NLOS樣本進行訓練,在同樣的移動臺位置區(qū)域內(nèi)隨機生成10 000個與訓練樣本不同的待定位目標點作為測試樣本,測試樣本中LOS和NLOS樣本同樣各占一半,每一個NLOS測試樣本包含的NLOS基站數(shù)量為隨機指定的1～4其中任何一個。隨機森林方法中子樹數(shù)量設置為100,由于隨機森林的特性,分類性能的波動較小。

表1為距離測量誤差標準差為σ=1 m,5 m,9 m的情況下,本文隨機森林(RF)算法與KNN算法、文獻[9]中的SVM算法的識別率比較。

表1 不同TOA測量誤差下算法識別率

表1的結(jié)果表明,本文算法性能優(yōu)于另外兩種算法。隨著TOA測量誤差標準差的增大,三種分類識別算法對于LOS/NLOS基站的識別率下降不明顯,因此可以看出TOA距離測量誤差對于算法性能影響并不大,原因是TOA測量誤差值相對于NLOS誤差來說過小,而本文采用的是各基站組合的測量距離來作為特征進行分類訓練,因此對特征產(chǎn)生的影響較小,因而對于算法的識別性能影響較小。

4.2 仿真實驗2:分析NLOS誤差大小對算法性能的影響

仿真中NLOS誤差服從U(100,BMAX),BMAX表示NLOS誤差最大值;TOA距離測量誤差標準差σ=1 m;訓練和測試樣本產(chǎn)生方式與仿真1相同,每一個NLOS測試樣本中的NLOS基站個數(shù)從1～4隨機指定,測試中LOS和NLOS樣本各占一半。

表2為NLOS誤差最大值分別在200 m,400 m,600 m,800 m,1 000 m情況下三種算法的識別率比較。

表2 不同NLOS誤差下三種算法識別性能

表2的結(jié)果表明,隨著NLOS誤差的增大,KNN和SVM分類算法識別率有一定的下降,而本文RF算法識別率相對穩(wěn)定性能較好。這是由于RF算法分類過程中會通過Gini指數(shù)選擇最優(yōu)的分裂屬性,因此只要NLOS誤差在一定程度上大于測量誤差,即使NLOS誤差值再增大對算法性能的影響也不大,且RF算法由多個分類器構(gòu)成,因此性能比另外兩種分類器更好。

4.3 仿真實驗3:分析不同NLOS基站個數(shù)對算法性能的影響

仿真中訓練樣本與測試樣本與仿真1的產(chǎn)生方式相同。圖3為10 000個測試樣本點中NLOS基站數(shù)為0,1,2,3,4的情況下,三種分類算法識別率的比較。

圖3 不同NLOS基站個數(shù)下三種算法識別率比較

圖3的結(jié)果表明,當NLOS基站個數(shù)增加時本文RF算法與KNN算法的識別率比較穩(wěn)定且識別率都在95%以上,基于SVM的分類算法性能相對較差,隨著NLOS基站個數(shù)增加識別率逐漸下降,受到NLOS基站個數(shù)影響較大。

4.4 仿真實驗4:分析訓練樣本大小對算法性能的影響

仿真中在移動臺位置區(qū)域隨機產(chǎn)生10 000個測試樣本。圖4為訓練樣本大小分別為100,500,1 000,2 000,3 000,4 000的情況下,三種算法的識別性能比較。

圖4 不同訓練樣本數(shù)量算法識別率比較

圖4的結(jié)果表明,隨著訓練樣本數(shù)增加KNN以及SVM算法的識別率也隨之增加,RF分類算法性能相對穩(wěn)定,表現(xiàn)良好。當訓練樣本數(shù)在4 000時,識別率趨于穩(wěn)定。由于本文算法是通過在移動臺位置區(qū)域中進行距離的測量,利用各基站組合中距離在LOS/NLOS下的差異來進行分類訓練,而不是通過采集信道的參數(shù)信息,因此生成訓練集時均勻遍歷整個定位空間,會使得算法擁有更好的性能,若采集的樣本過少,算法性能將會變得很差。

4.5 仿真實驗5:分析NLOS樣本占比不同對算法性能的影響

在實際場景中,LOS和NLOS信號是混合的。圖5為NLOS樣本占測試樣本比例為0.9,0.5,0.1的情況下,不同算法識別性能比較。

圖5 LOS/NLOS不同比例識別率比較

圖5的結(jié)果表明,SVM算法在NLOS樣本占比越大時識別率越低,RF算法以及KNN算法隨著NLOS樣本占的變化識別率變化較小,RF算法性能最好。

4.6 仿真實驗6:分析不同NLOS樣本比例經(jīng)過識別之后再進行定位的定位性能

按仿真1生成訓練樣本,其LOS/NLOS比例相同;同樣采用10 000個點為測試樣本,設置測量誤差為1 m,每一個NLOS樣本NLOS基站隨機指定為3個。

圖6為經(jīng)過不同算法識別之后采用Chan算法定位與未進行識別直接采用Chan算法定位的結(jié)果。

圖6 NLOS占比不同算法定位性能比較

圖6的結(jié)果表明,隨著NLOS樣本占比增加平均定位誤差都在增大,原因是NLOS樣本數(shù)增加會導致算法的識別率有所降低,導致定位誤差增大。其中RF算法進行NLOS識別之后定位誤差最小,性能最優(yōu)。經(jīng)過不同的分類算法對NLOS基站進行識別剔除后,只采用LOS基站進行定位,相比于直接采用Chan算法定位的性能更好,定位精度得到了很大的提高,表明本文所提出的NLOS識別算法能夠準確識別出NLOS基站。

4.7 仿真實驗7:分析不同分類算法計算復雜度

仿真中固定測量誤差為1 m,訓練和測試樣本產(chǎn)生方式與仿真1中相同,每一個NLOS測試樣本中的NLOS基站個數(shù)從1～4隨機指定,測試中LOS和NLOS樣本各占一半,分別測試不同算法從訓練到測試完成的時間開銷,結(jié)果如表3所示。表3中,n代表樣本的總數(shù)量,m代表的是用于分類特征的的維度,而d代表RF算法中決策樹的最大深度。從表中可以看出基于SVM算法的時間復雜度最高,RF算法次之,KNN算法時間復雜度最低。但是從實際運行時間來看KNN算法時間消耗最大,這是由于KNN算法沒有訓練過程,是靠直接計算每個測試樣本到訓練樣本的距離進行分類,更加適用于樣本數(shù)量較少的情況,而本文中樣本數(shù)量較大,因此預測效率較低,運行時間最長。由表3可以看出RF算法實時性比SVM算法更好。綜上所述,基于RF分類的LOS/NLOS算法穩(wěn)定性和時效性都優(yōu)于其他兩種分類算法。

表3 不同算法計算復雜度

5 結(jié) 論

本文提出了一種基于隨機森林機器學習的LOS/NLOS基站識別算法,其優(yōu)點是不需要采集信道特征參數(shù),僅通過發(fā)射機與接收機之間的測量距離作為特征,利用機器學習分類算法來進行NLOS識別。仿真結(jié)果表明,基于隨機森林的分類算法進行分類的識別率要優(yōu)于KNN分類算法和SVM分類算法,且經(jīng)過隨機森林分類算法識別剔除NLOS基站之后再采用Chan算法進行定位與未進行識別直接采用Chan算法定位相比定位性能得到了很大的提高。