基于分區匹配和MBAS-RFR的定位算法

陳平安,孫運全,張超虎

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

1 引言

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

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

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

2 MBAS-RFR算法實現

2.1 隨機森林回歸

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

2.2 BAS算法

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

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

(1)

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

(2)

(3)

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

(4)

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

dt=0.95·dt-1+0.01

(5)

δt=0.95·δt-1

(6)

2.3 MBAS算法

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

(7)

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

(8)

(9)

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

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

(10)

(11)

當達到最大迭代次數后,終止尋優,輸出全局最優解。

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

2.4 MBAS-RFR算法

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

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

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

(12)

(13)

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

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

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

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

7)判斷當前最小適應度值與上次迭代最小適應度值大小關系,從中選取當前最優個體。

8)重復步驟3)至步驟7)直至最大迭代次數結束。

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

3 改進分區匹配模型

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

圖1 井下巷道模型

3.1 改進加權歐氏距離模型

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

(14)

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

(15)

式中,ωi表示權重值,根據AP節點相鄰程度改變,ωi具體取值如下:

1)當信號強度特征最強三個對應AP節點為相鄰關系時

(16)

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

2)當最強信號特征的前兩個對應AP節點為相鄰關系且最強信號特征前三個對應AP節點僅橫跨三個區域時

(17)

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

3)其它

ωi=1

(18)

3.2 余弦相似度模型

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

(19)

3.3 改進加權歐氏距離結合余弦相似度

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

(20)

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

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

4 井下定位算法流程

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

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

圖2 本文算法流程圖

5 實驗分析

5.1 實驗設計

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

(21)

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

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

實驗模擬50m×4m的井下巷道模型,在其中均勻分布六個AP節點。巷道通過AP節點劃分區域并在每個區域隨機分布測試點數據,如圖3所示。

圖3 巷道測試模型

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

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

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

圖4 優化前定位模型性能對比圖

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

表2 優化前定位模型平均誤差

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

圖5 優化前定位模型置信概率對比

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

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

表3 加入優化算法后定位模型平均誤差

圖6 加入優化算法后模型性能對比

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

圖7 定位模型性能對比圖

6 結論

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