基于分區(qū)匹配和MBAS-RFR的定位算法

陳平安,孫運全,張超虎

(江蘇大學電氣信息工程學院,江蘇 鎮(zhèn)江 210031)

1 引言

截止2018年年底,我國已探明煤炭儲量居全球第三位,盡管我國煤礦安全開采水平逐漸提升,但煤礦事故時常發(fā)生[1],為了提高煤礦井下安全生產(chǎn)水平、減少煤礦事故帶來的人員財產(chǎn)損失,因此需要進一步研究井下人員定位技術(shù)。

目前井下人員定位技術(shù)大多基于射頻識別(Radio Frequency Identification,RFID)技術(shù)開發(fā),但存在精度低的問題,而基于接受信號強度指示[2](Received Signal Strength Indication,RSSI)的定位技術(shù)功耗小,成本低,近年來獲得了大力發(fā)展及推廣,在基于RSSI的定位方法中,位置指紋定位無需測距,該方法通過建立RSSI與位置坐標的非線性映射關(guān)系來推斷出待定位點的位置坐標。適合井下復(fù)雜環(huán)境中定位。近年來基于位置指紋[3]定位算法已有大量研究,宋明智[4]等將遺傳算法與隨機森林相結(jié)合,解決了奇點問題;余修武[5]等將巷道分區(qū),以信號強度確定其大致區(qū)域然后利用PSO算法定位,但在信號強度波動性大的情況下可能會存在誤判情況;趙建國[6]等逐步縮小待定位點的定位區(qū)域,最后利用KNN算法實現(xiàn)最終定位,提高了定位速度,但不適合于指紋庫較小的場景;崔麗珍[7]等采用粒子群算法優(yōu)化神經(jīng)網(wǎng)絡(luò),建立了RSSI和位置的非線性關(guān)系。吳雪敏[8]等通過RSSI判斷判斷待測節(jié)點所屬區(qū)域,然后利用改進雞群優(yōu)化算法實現(xiàn)具體定位,提高了定位精度,但電磁信號具有波動性,粗定位階段判斷所屬區(qū)域會出現(xiàn)誤判進而影響后續(xù)定位精度。

以上研究表明智能優(yōu)化算法可有效提高模型精度并且利用區(qū)域劃分思想應(yīng)用于井下人員定位中可有效縮小定位范圍,改善定位效果。本文提出了一種基于分區(qū)匹配和MBAS-RFR的井下人員定位模型,首先根據(jù)AP節(jié)點對井下巷道劃分區(qū)域,將離線指紋庫中符合條件的指紋數(shù)據(jù)作為每個區(qū)域的中心參考點,利用改進加權(quán)歐氏距離結(jié)合余弦相似度模型綜合判斷待定位點的所屬區(qū)域,最后通過MBAS(Multitask Beetle Antennae Swarm,多任務(wù)天牛群)-RFR(Random Forest Regression,隨機森林回歸)模型進行具體定位。

2 MBAS-RFR算法實現(xiàn)

2.1 隨機森林回歸

隨機森林(Random Forest,RF)算法是Breiman提出的一種以裝袋法(Bagging)為核心思想的集成算法[9],由多個決策樹組成,隨機森林回歸(Random Forest Regression,RFR)即是由多棵回歸樹組成的一種用于回歸問題預(yù)測的算法,它克服了決策樹容易過擬合的問題,具有回歸性能好,訓練速度快等優(yōu)點。

2.2 BAS算法

天牛須搜索(BAS,Beetle Antennae Search)算法是Jiang等[10]人提出的一種新型高效的智能優(yōu)化算法,天牛須搜索算法原理實際是天牛覓食的過程。天牛須搜索算法具體過程如下:

1)設(shè)置天牛朝向,天牛的朝向向量是隨機的

(1)

2)根據(jù)天牛朝向計算天牛左右須的位置

(2)

(3)

3)計算左右須氣味濃度函數(shù)值并進一步更新天牛的位置

(4)

4)更新天牛左右須間距和搜索步長

dt=0.95·dt-1+0.01

(5)

δt=0.95·δt-1

(6)

2.3 MBAS算法

多任務(wù)天牛群算法(MBAS,Multitask Beetle Antennae Swarm)是一種借鑒了人工蜂群(ABC,Artificial Bee Colony)算法中蜂群結(jié)構(gòu)并結(jié)合了天牛須搜索算法(BAS)的啟發(fā)式算法[11],該算法原理如下:定義種群數(shù)量為N的天牛群,天牛群分為三種任務(wù)類型,分別是搜索者,追隨者以及探索者,對于搜索者來說,任務(wù)是在可行解集內(nèi)找到最優(yōu)解,根據(jù)天牛須搜索算法尋優(yōu),位置更新如式(7)所示

(7)

追隨者天牛跟隨搜索者天牛,尋找當前全局最優(yōu)解周圍的潛在的最優(yōu)解,位置更新如式(9)所示

(8)

(9)

式(9)中,LF是追隨者的搜索步長。

探索者天牛以固定步長移動,防止系統(tǒng)陷入局部最優(yōu),如式(11)所示

(10)

(11)

當達到最大迭代次數(shù)后,終止尋優(yōu),輸出全局最優(yōu)解。

MBAS算法實現(xiàn)了從單只天牛尋優(yōu)到群體天牛尋優(yōu)的轉(zhuǎn)變,并且將天牛群分成不同任務(wù)類型進行高效尋優(yōu),極大程度克服了單只天牛尋優(yōu)易陷入局部最優(yōu)的不足,改善了算法的穩(wěn)定性及尋優(yōu)效果。

2.4 MBAS-RFR算法

MBAS-RFR算法基本思想是利用MBAS算法對RFR的參數(shù)進行尋優(yōu),對RFR算法影響最大的參數(shù)主要為決策樹數(shù)量以及樹深度,因此利用MBAS算法上述參數(shù)進行迭代尋優(yōu)。具體流程如下:

1)初始化MBAS算法參數(shù),設(shè)置種群數(shù)sizepop,最大迭代次數(shù)T,追隨者、探索者搜索步長等。

2)將優(yōu)化目標RFR得出的定位平均誤差作為天牛個體適應(yīng)度值,如式(13)所示

(12)

(13)

3)計算天牛個體適應(yīng)度值,將個體按適應(yīng)度值升序處理,適應(yīng)度最小個體為當前最優(yōu)個體。

4)將天牛群體分為三種任務(wù)類型,按適應(yīng)度升序排列依次為搜索者、追隨者、探索者。

5)根據(jù)相關(guān)公式分別對追隨者搜索者探索者群體進行方向和位置上的更新

6)分別計算三類天牛群體的適應(yīng)度值

7)判斷當前最小適應(yīng)度值與上次迭代最小適應(yīng)度值大小關(guān)系,從中選取當前最優(yōu)個體。

8)重復(fù)步驟3)至步驟7)直至最大迭代次數(shù)結(jié)束。

9)將MBAS算法輸出的最優(yōu)解作為RFR最優(yōu)參數(shù),同時用對應(yīng)訓練集樣本訓練RFR,建立井下定位算法模型。

3 改進分區(qū)匹配模型

在具體定位前,首先需要根據(jù)AP節(jié)點對井下巷道進行等距離分區(qū),如圖1所示,其中,Bb、Cc、Dd、Ee將巷道分為五個等距區(qū)域并從離線數(shù)據(jù)中選出每個區(qū)域的中心點,在線階段,通過衡量待定位點的信號強度與中心點信號強度的相似度特征,將待定位點進行分區(qū),分區(qū)匹配效果的好壞直接關(guān)系到具體定位階段的定位效果,一般采用歐氏距離模型衡量兩個n維向量的距離大小[12],但在實際的井下巷道環(huán)境中電磁環(huán)境容易受到多徑效應(yīng)以及非視距因素等干擾,傳統(tǒng)歐氏距離分區(qū)匹配模型會受到一定程度影響,因此,應(yīng)針對井下復(fù)雜環(huán)境對歐氏距離分區(qū)匹配模型進行適當改進。

圖1 井下巷道模型

3.1 改進加權(quán)歐氏距離模型

受井下環(huán)境影響,井下巷道電磁信號波動較大,波動較大的信號數(shù)據(jù)所表示的實際位置不穩(wěn)定,故應(yīng)該增大實際計算出的歐式距離來表達不穩(wěn)定度,方差反映了數(shù)據(jù)的波動性,故將多次測量的信號強度數(shù)據(jù)取方差處理,將方差引入到歐式距離計算中去。故改進歐氏距離模型如式(14)所示

(14)

圖1所示井下巷道中,待定位節(jié)點采集的信號強度來自均勻分布的6個AP節(jié)點,巷道分區(qū)并選出區(qū)域中心點后,此時可利用改進歐氏距離公式來判斷待測點與中心點的相似度,從而判斷出待定位點所屬區(qū)域,但分區(qū)匹配模型存在不足,因為未考慮每個AP節(jié)點對待定位點的影響程度,距離AP節(jié)點越近,信號越強;因此可以通過判定所測信號強弱來判斷待定位點所處的大致區(qū)域。故本文提出一種可變權(quán)重的歐氏距離公式,可根據(jù)信號強度大小判斷待定位點所在大致區(qū)域,進而對此間區(qū)域改進歐式距離的計算進行適當加權(quán)處理,可變權(quán)重歐氏距離公式如(15)所示

(15)

式中,ωi表示權(quán)重值,根據(jù)AP節(jié)點相鄰程度改變,ωi具體取值如下:

1)當信號強度特征最強三個對應(yīng)AP節(jié)點為相鄰關(guān)系時

(16)

式中,max(ri)為某測試點中的最強信號強度特征,min(ri)為某測試點中的最弱信號強度特征。

2)當最強信號特征的前兩個對應(yīng)AP節(jié)點為相鄰關(guān)系且最強信號特征前三個對應(yīng)AP節(jié)點僅橫跨三個區(qū)域時

(17)

式中,max3(ri)是ri中降序排列第三的信號強度特征。

3)其它

ωi=1

(18)

3.2 余弦相似度模型

余弦相似度通過向量的內(nèi)積空間夾角余弦值來衡量向量之間的相似性程度,余弦值越接近1,兩個向量越相似[13]。余弦相似度模型如式(19)所示

(19)

3.3 改進加權(quán)歐氏距離結(jié)合余弦相似度

針對單一模型分區(qū)匹配衡量指標不全面導(dǎo)致精度不理想的問題。本文在前人研究基礎(chǔ)[14]上將改進后的歐氏距離模型與余弦相似度模型結(jié)合如式(20)所示

(20)

式中,di為改進加權(quán)歐氏距離,cos(ra,rb)為余弦相似度。σ是一個隨機較小值,防止分母為0。

由式(20)可知,當兩個向量的改進加權(quán)歐氏距離越小并且余弦相似度值越大時,此時改進分區(qū)匹配模型值越大,說明兩個向量之間的相似度越高。

4 井下定位算法流程

本文算法流程有兩個階段,首先離線階段多次采集指紋數(shù)據(jù)取均值,準備好位置指紋庫,根據(jù)AP節(jié)點來劃分井下巷道區(qū)域,每個區(qū)域的定位模型訓練數(shù)據(jù)采用本區(qū)域和相鄰區(qū)域部分訓練集數(shù)據(jù),建立MBAS-RFR算法定位模型。

在線階段,利用改進加權(quán)歐氏距離結(jié)合余弦相似度模型將接收到的實時位置指紋數(shù)據(jù)與中心參考點進行匹配,將實時位置指紋數(shù)據(jù)進行分區(qū)處理,然后,在每一個區(qū)域中,利用MBAS-RFR定位模型根據(jù)待定位點RSS數(shù)據(jù)計算出對應(yīng)位置坐標。算法流程如圖2所示。

圖2 本文算法流程圖

5 實驗分析

5.1 實驗設(shè)計

本文采用射線跟蹤法[15]-[17]模擬井下巷道信號模型,生成訓練測試用的位置指紋數(shù)據(jù),實驗平臺基于Python語言搭建,電腦配置為Core i5處理器、8GB內(nèi)存。利用ITU傳播模型來模擬井下信號衰減變化,如式(21)所示

(21)

式中,d為AP節(jié)點和待測節(jié)點的實際距離;d0為參考距離,RSSI(d0)為參考距離接收到的信號強度指示;Xσ是均值為0的高斯隨機噪聲,n為信號衰減指數(shù)。多次測量信號強度數(shù)據(jù)取均值構(gòu)建位置指紋數(shù)據(jù)庫包括693組離線訓練數(shù)據(jù)、50組在線測試數(shù)據(jù),部分訓練數(shù)據(jù)見表1。

表1 部分訓練數(shù)據(jù)(信號強度單位:dBm)

實驗?zāi)M50m×4m的井下巷道模型,在其中均勻分布六個AP節(jié)點。巷道通過AP節(jié)點劃分區(qū)域并在每個區(qū)域隨機分布測試點數(shù)據(jù),如圖3所示。

圖3 巷道測試模型

實驗主要內(nèi)容是加入MBAS優(yōu)化算法前后三種定位模型性能對比。對定位模型性能的評判指標為平均定位誤差和不同距離誤差距離下的置信概率。

5.2 MBAS算法加入前定位模型性能評估

為了能直觀地展示本文提出的定位算法性能,使用同樣的訓練數(shù)據(jù)和測試數(shù)據(jù)代入不同定位模型。并對其結(jié)果進行對比分析,其中包括隨機森林回歸(RFR),歐氏距離分區(qū)匹配模型結(jié)合隨機森林回歸(E-RFR)和改進分區(qū)匹配模型結(jié)合隨機森林回歸(IE-RFR)。使用的數(shù)據(jù)是在同一環(huán)境中采集的測量數(shù)據(jù)。部分定位結(jié)果圖4所示。

圖4 優(yōu)化前定位模型性能對比圖

根據(jù)圖4、表2分析,結(jié)合了分區(qū)匹配算法的兩種定位模型平均誤差分別降低了20.33%和26.97%,這說明了分區(qū)匹配模型能夠有效降低定位誤差;其中,相比于E-RFR定位模型,IE-RFR算法模型定位誤差最小,定位精度更高,這說明本文提出的改進分區(qū)匹配算法分區(qū)匹配效果更好,更有利于保證后續(xù)階段的定位精度。

表2 優(yōu)化前定位模型平均誤差

圖5分析可知,IE-RFR算法在誤差1.5m以內(nèi)置信概率為62%,而E-RFR和RFR則分別為54%和38%,進一步說明了IE-RFR算法相比另外兩種模型定位精度更高。

圖5 優(yōu)化前定位模型置信概率對比

5.3 MBAS算法加入后定位模型性能評估

相較于未加入優(yōu)化算法前,由圖6和表3分析可知,三種定位模型的平均誤差均有所降低且定位波動性降低;這說明了MBAS優(yōu)化算法提高了定位模型的穩(wěn)定性并降低了定位誤差;相比于另外兩種模型,本文算法的平均定位誤差分別降低了29.22%及15.76%,且定位穩(wěn)定性最好。

表3 加入優(yōu)化算法后定位模型平均誤差

圖6 加入優(yōu)化算法后模型性能對比

圖7分析可知,本文算法在誤差1.5m內(nèi)的置信概率是66%,而EMBAS-RFR和MBAS-RFR定位模型分別只有56%和60%,本文算法在1.5米內(nèi)的準確率要高10%和6%,這說明改進加權(quán)歐氏距離結(jié)合余弦相似度模型結(jié)合MBAS-RFR定位模型具有更好的定位精度和定位穩(wěn)定性且該定位精度能夠滿足井下人員定位要求。

圖7 定位模型性能對比圖

6 結(jié)論

針對井下環(huán)境復(fù)雜以及電磁信號波動導(dǎo)致井下人員定位精度低的問題,本文提出了基于分區(qū)匹配和多任務(wù)天牛群優(yōu)化隨機森林的井下人員定位算法。首先使用改進加權(quán)歐氏距離結(jié)合余弦相似度的分區(qū)匹配模型對待定位節(jié)點進行分區(qū)處理,隨后利用MBAS-RFR算法進行具體定位,本文分區(qū)匹配算法保證了后續(xù)具體定位階段的精度,有效降低了定位誤差,多任務(wù)天牛群算法有效的提高了定位的穩(wěn)定性和精度。下一步將研究不同巷道類型對于定位精度的影響及模型優(yōu)化。