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

陳平安,孫運(yùn)全,張超虎

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

1 引言

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

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

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

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

2.1 隨機(jī)森林回歸

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

2.2 BAS算法

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

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

(1)

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

(2)

(3)

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

(4)

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

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ù)類(lèi)型,分別是搜索者,追隨者以及探索者,對(duì)于搜索者來(lái)說(shuō),任務(wù)是在可行解集內(nèi)找到最優(yōu)解,根據(jù)天牛須搜索算法尋優(yōu),位置更新如式(7)所示

(7)

追隨者天牛跟隨搜索者天牛,尋找當(dāng)前全局最優(yōu)解周?chē)臐撛诘淖顑?yōu)解,位置更新如式(9)所示

(8)

(9)

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

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

(10)

(11)

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

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

2.4 MBAS-RFR算法

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

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

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

(12)

(13)

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

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

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

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

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

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

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

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

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

圖1 井下巷道模型

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

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

(14)

圖1所示井下巷道中,待定位節(jié)點(diǎn)采集的信號(hào)強(qiáng)度來(lái)自均勻分布的6個(gè)AP節(jié)點(diǎn),巷道分區(qū)并選出區(qū)域中心點(diǎn)后,此時(shí)可利用改進(jìn)歐氏距離公式來(lái)判斷待測(cè)點(diǎn)與中心點(diǎn)的相似度,從而判斷出待定位點(diǎn)所屬區(qū)域,但分區(qū)匹配模型存在不足,因?yàn)槲纯紤]每個(gè)AP節(jié)點(diǎn)對(duì)待定位點(diǎn)的影響程度,距離AP節(jié)點(diǎn)越近,信號(hào)越強(qiáng);因此可以通過(guò)判定所測(cè)信號(hào)強(qiáng)弱來(lái)判斷待定位點(diǎn)所處的大致區(qū)域。故本文提出一種可變權(quán)重的歐氏距離公式,可根據(jù)信號(hào)強(qiáng)度大小判斷待定位點(diǎn)所在大致區(qū)域,進(jìn)而對(duì)此間區(qū)域改進(jìn)歐式距離的計(jì)算進(jìn)行適當(dāng)加權(quán)處理,可變權(quán)重歐氏距離公式如(15)所示

(15)

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

1)當(dāng)信號(hào)強(qiáng)度特征最強(qiáng)三個(gè)對(duì)應(yīng)AP節(jié)點(diǎn)為相鄰關(guān)系時(shí)

(16)

式中,max(ri)為某測(cè)試點(diǎn)中的最強(qiáng)信號(hào)強(qiáng)度特征,min(ri)為某測(cè)試點(diǎn)中的最弱信號(hào)強(qiáng)度特征。

2)當(dāng)最強(qiáng)信號(hào)特征的前兩個(gè)對(duì)應(yīng)AP節(jié)點(diǎn)為相鄰關(guān)系且最強(qiáng)信號(hào)特征前三個(gè)對(duì)應(yīng)AP節(jié)點(diǎn)僅橫跨三個(gè)區(qū)域時(shí)

(17)

式中,max3(ri)是ri中降序排列第三的信號(hào)強(qiáng)度特征。

3)其它

ωi=1

(18)

3.2 余弦相似度模型

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

(19)

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

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

(20)

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

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

4 井下定位算法流程

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

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

圖2 本文算法流程圖

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)設(shè)計(jì)

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

(21)

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

表1 部分訓(xùn)練數(shù)據(jù)(信號(hào)強(qiáng)度單位:dBm)

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

圖3 巷道測(cè)試模型

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

5.2 MBAS算法加入前定位模型性能評(píng)估

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

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

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

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

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

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

5.3 MBAS算法加入后定位模型性能評(píng)估

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

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

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

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

圖7 定位模型性能對(duì)比圖

6 結(jié)論

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