一種基于隨機(jī)森林的LOS/NLOS基站識(shí)別方法*

戢靜紅,張振宇,鄧 平

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

0 引 言

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

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

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

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

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

(1)

(2)

(3)

(4)

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

2 基于隨機(jī)森林的分類方法

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

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

圖1 集成分類器框架

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

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

(5)

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

(6)

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

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

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

(7)

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

(8)

3 LOS/NLOS基站識(shí)別算法流程

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

本文識(shí)別算法步驟如下:

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

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

將識(shí)別后的NLOS基站進(jìn)行剔除,再利用剩余的LOS基站進(jìn)行定位,即可得到準(zhǔn)確的移動(dòng)臺(tái)估計(jì)位置。

4 算法仿真與分析

圖2 基站與移動(dòng)臺(tái)布局

4.1 仿真實(shí)驗(yàn)1:分析TOA測量誤差大小對(duì)算法性能的影響

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

表1為距離測量誤差標(biāo)準(zhǔn)差為σ=1 m,5 m,9 m的情況下,本文隨機(jī)森林(RF)算法與KNN算法、文獻(xiàn)[9]中的SVM算法的識(shí)別率比較。

表1 不同TOA測量誤差下算法識(shí)別率

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

4.2 仿真實(shí)驗(yàn)2:分析NLOS誤差大小對(duì)算法性能的影響

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

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

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

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

4.3 仿真實(shí)驗(yàn)3:分析不同NLOS基站個(gè)數(shù)對(duì)算法性能的影響

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

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

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

4.4 仿真實(shí)驗(yàn)4:分析訓(xùn)練樣本大小對(duì)算法性能的影響

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

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

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

4.5 仿真實(shí)驗(yàn)5:分析NLOS樣本占比不同對(duì)算法性能的影響

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

圖5 LOS/NLOS不同比例識(shí)別率比較

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

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

按仿真1生成訓(xùn)練樣本,其LOS/NLOS比例相同;同樣采用10 000個(gè)點(diǎn)為測試樣本,設(shè)置測量誤差為1 m,每一個(gè)NLOS樣本NLOS基站隨機(jī)指定為3個(gè)。

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

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

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

4.7 仿真實(shí)驗(yàn)7:分析不同分類算法計(jì)算復(fù)雜度

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

表3 不同算法計(jì)算復(fù)雜度

5 結(jié) 論

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