基于改進(jìn)Kriging插值的煤礦井下定位算法

朱恒軍, 王冠鈺, 張 靚

( 1. 齊齊哈爾大學(xué) 通信與電子工程學(xué)院，黑龍江 齊齊哈爾 161006; 2. 黑龍江交通職業(yè)技術(shù)學(xué)院 鐵道機(jī)車學(xué)院，黑龍江 齊齊哈爾 161000 )

0 引言

掌握井下人員、車輛、設(shè)備的位置信息不但利于煤礦企業(yè)高效生產(chǎn)，而且能在發(fā)生礦難時(shí)快速施救，減少損失[1]。傳統(tǒng)的射頻識(shí)別定位技術(shù)已不能滿足井下定位在精度、穩(wěn)定性、效率方面越來越高的要求。無線傳感器網(wǎng)絡(luò)技術(shù)以能耗低、成本低、無線自組織通信、擴(kuò)展性強(qiáng)等特點(diǎn)，在煤礦井下的定位應(yīng)用逐漸成為研究熱點(diǎn)[2]。

在與無線傳感器網(wǎng)絡(luò)定位技術(shù)對應(yīng)的定位算法中，位置指紋定位算法具有受環(huán)境干擾小、精度高等優(yōu)點(diǎn)，更加適合井下環(huán)境應(yīng)用。在離線階段構(gòu)建位置指紋數(shù)據(jù)庫時(shí)需采集大量位置指紋，以保證定位精度，耗費(fèi)大量人力、物力。根據(jù)改進(jìn)的路徑衰減模型，Kubota R等估計(jì)位置指紋[3]； Racko J等運(yùn)用線性和Delaunay插值對位置指紋進(jìn)行估計(jì)[4]；Germán M等采用線性向量回歸方法對位置指紋進(jìn)行估計(jì)[5]。在環(huán)境干擾較小的情況下，這些算法對位置指紋的估計(jì)性能良好，且實(shí)現(xiàn)簡單，但在井下巷道復(fù)雜環(huán)境下，位置指紋的估計(jì)精度大幅下降。劉輝元等采用距離倒數(shù)加權(quán)估計(jì)插值點(diǎn)位置指紋[6]；張夢丹等提出一種線性插值法重構(gòu)離線指紋庫[7]；劉文遠(yuǎn)等將整個(gè)室內(nèi)環(huán)境劃分為多個(gè)環(huán)路快速分割地圖，獲取射頻指紋并構(gòu)建位置指紋數(shù)據(jù)庫[8]。根據(jù)采樣點(diǎn)之間的相對位置關(guān)系，三種算法結(jié)合位置指紋對插值點(diǎn)進(jìn)行估值，在井下復(fù)雜信號(hào)傳播環(huán)境下，信號(hào)衰落不僅與位置有關(guān)，還受環(huán)境因素影響，位置指紋估計(jì)精度較低。王永星等提出一種基于Kriging插值算法的RSS指紋數(shù)據(jù)快速生成方法[9]，通過變異函數(shù)對信號(hào)傳播環(huán)境進(jìn)行描述，考慮環(huán)境影響，但在擬合變異函數(shù)時(shí)運(yùn)用最小二乘法容易陷入局部最優(yōu)。王紅軍等利用支持向量回歸法擬合變異函數(shù)，提高插值精度。兩種算法提高變異函數(shù)擬合精度，進(jìn)而提高插值的精度[10]。

為解決井下定位中存在的逐點(diǎn)采集位置指紋工作量較大的問題，在保留Kriging空間插值優(yōu)點(diǎn)的基礎(chǔ)上，引入灰狼優(yōu)化算法。首先通過采集的位置指紋構(gòu)建實(shí)驗(yàn)變異函數(shù)，綜合分組和差分進(jìn)化策略對灰狼優(yōu)化算法進(jìn)行改進(jìn)，優(yōu)化變異函數(shù)參數(shù)的選取，提高由實(shí)驗(yàn)變異函數(shù)擬合理論變異函數(shù)的精度，進(jìn)而提高對其它位置指紋估計(jì)精度和定位精度。在實(shí)現(xiàn)減少采集工作量目標(biāo)的同時(shí)，實(shí)現(xiàn)通過采集部分位置指紋估計(jì)所有位置指紋的功能，以達(dá)到提升位置指紋的插值精度和井下定位精度的效果。

1 位置指紋匹配定位算法

因所處井下巷道不同位置，信號(hào)的多徑結(jié)構(gòu)不同，稱每個(gè)位置獨(dú)特的多徑信號(hào)為位置指紋。定位過程包含位置指紋數(shù)據(jù)庫構(gòu)建和在線匹配定位[11]。基于位置指紋的匹配定位原理和流程見圖1。

圖1 基于位置指紋的匹配定位原理和流程Fig.1 Positioning fingerprint based on matching positioning principle and process

位置指紋數(shù)據(jù)庫構(gòu)建是在定位區(qū)域內(nèi)設(shè)置若干基于位置指紋的匹配定位參考點(diǎn)，將每個(gè)參考點(diǎn)的實(shí)際位置和接收到的無線信號(hào)信息存入數(shù)據(jù)庫[12]。因接收信號(hào)強(qiáng)度RSSI測量方便，無需額外硬件，大多選擇記錄RSSI。理論上，定位區(qū)域內(nèi)的參考點(diǎn)越密集，目標(biāo)定位精度越高。然而煤礦井下巷道狹長，干擾較多，為保證位置指紋定位精度不受影響，需大量部署參考點(diǎn)，耗費(fèi)大量人力用于采集采樣點(diǎn)位置指紋。

在線匹配定位階段，將未知節(jié)點(diǎn)的位置指紋與數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行比較，尋找最相似參考點(diǎn)，用匹配定位算法計(jì)算未知節(jié)點(diǎn)位置。最常用的KNN定位算法，將歐氏距離最小的K個(gè)參考點(diǎn)位置坐標(biāo)求取均值作為未知節(jié)點(diǎn)的位置坐標(biāo)[13]。

在煤礦井下復(fù)雜環(huán)境中，將環(huán)境溫度、濕度、粉塵，空間狹窄，管道縱橫等因素對信號(hào)的干擾，作為位置指紋在定位中使用，以使算法抗環(huán)境干擾能力增強(qiáng)，工作更穩(wěn)定，更適于井下定位。

2 構(gòu)建位置指紋數(shù)據(jù)庫

采用Kriging插值算法，在充分考慮區(qū)域化變量間的相關(guān)性后，對每一個(gè)區(qū)域化變量賦予一定的權(quán)重因數(shù)，最后進(jìn)行加權(quán)平均估計(jì)預(yù)測區(qū)域[14]。受井下環(huán)境中多徑效應(yīng)對信號(hào)的影響，不能簡單根據(jù)信號(hào)衰減模型計(jì)算RSSI值。Kriging插值算法既利于分析采樣點(diǎn)和待估點(diǎn)的相對位置和RSSI值，又利于通過變異理論從整體信號(hào)空間變異結(jié)構(gòu)角度，考量已知點(diǎn)間的關(guān)系及其對插值位置的影響，插值結(jié)果更準(zhǔn)確、更符合真實(shí)環(huán)境。插值點(diǎn)RSSI值計(jì)算公式為

(1)

式中：Z*(x0)為插值點(diǎn)的RSSI值;Z(xi)為第i個(gè)參考點(diǎn)xi處的RSSI值;λi為第i個(gè)采樣點(diǎn)對插值點(diǎn)的權(quán)重因數(shù)。Kriging插值算法的關(guān)鍵是計(jì)算權(quán)重因數(shù)。

通過變異函數(shù)描述空間距離為h的兩個(gè)位置指紋之間的相關(guān)性，根據(jù)N個(gè)采樣點(diǎn)位置指紋進(jìn)行計(jì)算，則變異函數(shù)r(h)為

(2)

在實(shí)際應(yīng)用中，很難得到所有點(diǎn)之間的變異函數(shù)，常采用采樣點(diǎn)的變異函數(shù)對變異函數(shù)模型進(jìn)行擬合，其中球狀模型應(yīng)用最為廣泛，有

(3)

式中：C0、C和a為變異函數(shù)的參數(shù)，其中C0為塊金值，C為偏基臺(tái)值，a為變程。

在保證對待估點(diǎn)Z*(x0)的估計(jì)滿足無偏性和最小方差性的情況下，解得權(quán)重因數(shù)為

λ=A-1γ0,

(4)

3 改進(jìn)Kriging插值定位算法

3.1 普通灰狼優(yōu)化算法

通過Kriging插值算法估計(jì)部分位置指紋可減輕采集工作量。由于位置指紋的估計(jì)精度影響井下定位精度，為進(jìn)一步提升位置指紋估計(jì)精度，達(dá)到提高井下定位精度的目的，引入灰狼優(yōu)化算法優(yōu)化變異函數(shù)的C0、C和a三個(gè)參數(shù)?；依莾?yōu)化算法是由Mirjalili S等提出的、一種通過模擬灰狼的社會(huì)等級和狩獵行為的新型群體智能優(yōu)化算法[15]。該算法具有結(jié)構(gòu)簡單、參數(shù)設(shè)置少、容易實(shí)現(xiàn)、收斂精度高和收斂速度快等特點(diǎn)。

灰狼優(yōu)化算法實(shí)現(xiàn)步驟：

(5)

其誤差越小，擬合效果越好。將灰狼按適應(yīng)度值從小到大排序，前三名分別設(shè)置為α、β和δ狼，其余為ω狼。

(2)更新灰狼個(gè)體位置。由α、β和δ狼引導(dǎo)ω狼進(jìn)行追捕獵物，即對每組解進(jìn)行更新，有

(6)

(7)

(8)

式(6-8)中：t為當(dāng)前的迭代次數(shù);X(t+1)為更新后灰狼的位置;Dα、Dβ和Dδ分別為其它灰狼ω與α、β和δ的距離，且

Dj=|ClXj(t)-Xω(t)|,

(9)

其中j=α,β,δ；Al和Cl(l=1,2,3)的計(jì)算公式為

Al=2ar1-a,

(10)

Cl=2r2,

(11)

式(10-11)中：a從2線性遞減到0；r1和r2為區(qū)間[0,1]的隨機(jī)數(shù)。

3.2 改進(jìn)灰狼優(yōu)化算法

灰狼優(yōu)化算法與其它貪婪算法一樣，求解優(yōu)化問題時(shí)易出現(xiàn)早熟、易陷入局部最優(yōu)等缺陷[16]，提出綜合分組策略和差分進(jìn)化策略對灰狼優(yōu)化算法進(jìn)行改進(jìn)。

首先，將整個(gè)灰狼種群按適應(yīng)度排序分為兩組。第一組適應(yīng)度好的種群，按照灰狼優(yōu)化算法對灰狼個(gè)體進(jìn)行更新；第二組適應(yīng)度差的種群，先采用差分進(jìn)化算法對狼群進(jìn)行變異，增強(qiáng)全局搜索能力，再進(jìn)行灰狼優(yōu)化。并且，隨著迭代次數(shù)的增加，逐漸增大第一組種群的個(gè)數(shù)，逐漸減少第二組種群的個(gè)數(shù)。在迭代前期能夠避免早熟和陷入局部最優(yōu)，在迭代后期利于減少變異次數(shù)，提高搜索速度。

差分進(jìn)化算法步驟:

(1)變異操作。在由變異函數(shù)的C0、C和a三個(gè)參數(shù)構(gòu)成的灰狼種群中隨機(jī)選取兩個(gè)不同的灰狼，將其位置求差進(jìn)行縮放后再與待變異的灰狼進(jìn)行合成。第k個(gè)灰狼變異個(gè)體uk(t)為

uk(t)=Xp1+F(Xp2-Xp3),

(12)

式中：Xp1、Xp2、Xp3為灰狼種群中隨機(jī)選擇的三個(gè)不相同個(gè)體;F為[0,1]之間的縮放比例因子。

(2)交叉操作。將原有灰狼個(gè)體Xk(t)與變異后產(chǎn)生的個(gè)體uk(t)的第j個(gè)參數(shù)進(jìn)行交換，增加種群的多樣性，即

(13)

式中：CR為取值[0,1]之間的交叉概率；rand(m,n)是[m,n]上均勻分布的隨機(jī)函數(shù)。

(3)選擇操作。通過差分機(jī)制可保證子代個(gè)體至少不比當(dāng)前個(gè)體差。選取適應(yīng)度值較好的個(gè)體:

(14)

3.3 井下定位算法

通過優(yōu)化的Kriging插值算法進(jìn)行井下定位步驟:

(1)人工多次采集采樣點(diǎn)位置指紋。通過高斯濾波剔除由環(huán)境干擾造成的異常值，可得比較穩(wěn)定的位置指紋，并記錄采樣點(diǎn)的位置信息。

(2)將采樣點(diǎn)的位置指紋和位置信息通過式(2)構(gòu)建實(shí)驗(yàn)變異函數(shù)數(shù)據(jù)集。

(3)初始化灰狼個(gè)體位置，即C0、C和a三個(gè)參數(shù)，并計(jì)算每個(gè)灰狼個(gè)體的適應(yīng)度值。根據(jù)適應(yīng)度值將灰狼個(gè)體劃分為兩組：第一組適應(yīng)度好的灰狼個(gè)體，按式(5-10)更新自身位置；第二組適應(yīng)度差的灰狼個(gè)體，先按式(11-13)進(jìn)行差分變異，灰狼個(gè)體再按式(5-10)更新自身位置。判斷是否達(dá)到迭代次數(shù)，如果沒有，則調(diào)整每組灰狼的個(gè)體數(shù)量，并且重復(fù)這一過程；如果達(dá)到迭代次數(shù)后，則輸出C0、C和a三個(gè)參數(shù)。

(4)將C0、C和a三個(gè)參數(shù)代入式(3)，構(gòu)建理論變異函數(shù)。

(5)根據(jù)式(1)、式(3)、式(4)估計(jì)插值點(diǎn)的位置指紋。

(6)采集井下人員的位置指紋，采用KNN匹配算法計(jì)算井下人員位置。

采用改進(jìn)的灰狼優(yōu)化算法，優(yōu)化Kriging插值位置指紋井下定位算法流程見圖2。

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)區(qū)域選擇長為80.0 m、寬為4.0 m，高為3.0 m的狹長通道模擬井下巷道環(huán)境。采用CC2530模塊作為信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)，在通道兩端和中心分別布置5個(gè)信標(biāo)節(jié)點(diǎn)，距地面1.8 m，以實(shí)驗(yàn)區(qū)域的長、寬、高為坐標(biāo)系的x、y、z軸。由于巷道長度遠(yuǎn)大于寬高，故寬高可忽略不計(jì)，在巷道中央每隔1.0 m設(shè)置一個(gè)采樣點(diǎn)。每個(gè)采樣點(diǎn)采樣100次，將求取均值作為位置指紋實(shí)際值。采用MATLAB軟件對算法進(jìn)行測試，井下節(jié)點(diǎn)部署實(shí)驗(yàn)環(huán)境見圖3。

圖2 Kriging插值位置指紋井下定位算法流程Fig.2 Kriging interpolation location fingerprint downhole localization algorithm flow

4.2 實(shí)驗(yàn)結(jié)果

首先，分析不同數(shù)量的采樣點(diǎn)，采用改進(jìn)Kriging插值算法估計(jì)位置指紋的誤差，定義相對估計(jì)誤差e，即

(15)

分別從采樣點(diǎn)集合中隨機(jī)選取20%～80%數(shù)量的位置指紋估計(jì)剩余的位置指紋，計(jì)算RSSI估計(jì)誤差，重復(fù)實(shí)驗(yàn)10次，將求取均值作為最終誤差。為比較不同算法的插值性能和檢驗(yàn)算法的改進(jìn)效果，選擇有代表性的IDW插值、普通Kriging插值和改進(jìn)Kriging插值算法生成位置指紋的誤差。不同算法生成RSSI位置指紋實(shí)驗(yàn)結(jié)果見圖4。

由圖4可知，隨著已知位置指紋數(shù)量的增加，位置指紋估計(jì)誤差逐漸減小，當(dāng)位置指紋數(shù)量超過50%時(shí)，估計(jì)誤差下降緩慢；改進(jìn)Kriging插值算法估計(jì)誤差小于普通Kriging插值算法的，也小于IDW插值算法的，表明改進(jìn)Kriging插值算法可以提升位置指紋插值精度，更加接近實(shí)際采集值。

改進(jìn)Kriging插值算法在不同數(shù)量采樣點(diǎn)的位置指紋估計(jì)誤差和運(yùn)算時(shí)間見表1。由表1可知，當(dāng)采樣點(diǎn)數(shù)量超過50%時(shí)，估計(jì)誤差下降緩慢，但算法的運(yùn)行時(shí)間即運(yùn)算量不斷增加，因此選擇采集50%的位置指紋估計(jì)剩余的位置指紋。

當(dāng)采樣點(diǎn)數(shù)量為50%時(shí)，比較隨機(jī)選取采樣點(diǎn)與隔點(diǎn)均勻選取采樣點(diǎn)對位置指紋估計(jì)的影響，實(shí)驗(yàn)結(jié)果見表2。由表2可知，相對于隨機(jī)采樣，均勻采樣位置指紋估計(jì)誤差更小，并且采用改進(jìn)Kriging插值算法時(shí)，隔點(diǎn)采集50%位置指紋估計(jì)剩余50%位置指紋估計(jì)誤差最小。

表1 改進(jìn)Kriging插值算法估計(jì)誤差與運(yùn)算時(shí)間

圖3 井下節(jié)點(diǎn)部署Fig.3 Underground node deployment

Table 2 Influence of different sampling methods on relative estimation error%

其次，分析不同插值算法對定位精度的影響。選擇節(jié)點(diǎn)估計(jì)坐標(biāo)與節(jié)點(diǎn)實(shí)際坐標(biāo)間距離的均方根誤差E作為評判標(biāo)準(zhǔn)，有

(16)

分別采用IDW插值、普通Kriging插值、改進(jìn)Kriging插值算法和逐點(diǎn)采集位置指紋，構(gòu)建位置指紋數(shù)據(jù)庫，在定位區(qū)域內(nèi)，隨機(jī)采集50個(gè)未知節(jié)點(diǎn)的位置指紋，采用KNN算法進(jìn)行定位并計(jì)算定位誤差。重復(fù)實(shí)驗(yàn)20次，將求取均值作為最終誤差。4種算法的定位結(jié)果見圖5，定位誤差結(jié)果見表3。

圖4 不同算法生成RSSI位置指紋誤差Fig.4 Different algorithms generate RSSI fingerprint error

圖5 不同算法的定位結(jié)果Fig.5 Localization results of different algorithms

誤差類別逐點(diǎn)采集改進(jìn)Kriging插值普通Kriging插值IDW插值平均誤差/m2.552.723.033.27誤差方差0.870.951.051.86

由圖5和表3可知，改進(jìn)Kriging插值算法定位誤差最接近逐點(diǎn)采集構(gòu)建數(shù)據(jù)庫定位誤差，相比于普通Kriging和IDW插值算法，改進(jìn)Kriging算法進(jìn)一步提升定位精度，且誤差波動(dòng)最小，定位性能更加穩(wěn)定。在采用隔點(diǎn)采集位置指紋情況下，通過改進(jìn)Kriging插值算法構(gòu)建完整位置指紋數(shù)據(jù)庫定位性能，最接近逐點(diǎn)采集構(gòu)建位置指紋數(shù)據(jù)庫，在節(jié)省位置指紋采集工作量的同時(shí)，相對于普通Kriging和IDW插值算法，其插值精度和定位精度有大幅提升。

5 結(jié)論

(1)在采集部分位置指紋的基礎(chǔ)上，首先利用Kriging插值算法估計(jì)全部位置指紋；然后改進(jìn)灰狼優(yōu)化算法，優(yōu)化Kriging插值算法的變異函數(shù)參數(shù)；最終提出基于改進(jìn)Kriging插值的煤礦井下定位算法。

(2)該算法在定位時(shí)只需隔點(diǎn)采集位置指紋，就可以估計(jì)全部位置指紋，提高位置指紋的采集效率，與普通Kriging和IDW插值算法相比，改進(jìn)Kriging插值算法提升位置指紋估計(jì)精度和定位精度，更加適合在煤礦井下定位過程中應(yīng)用。