基于改進Kriging插值的煤礦井下定位算法

朱恒軍, 王冠鈺, 張 靚

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

0 引言

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

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

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

1 位置指紋匹配定位算法

因所處井下巷道不同位置，信號的多徑結構不同，稱每個位置獨特的多徑信號為位置指紋。定位過程包含位置指紋數據庫構建和在線匹配定位[11]。基于位置指紋的匹配定位原理和流程見圖1。

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

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

在線匹配定位階段，將未知節點的位置指紋與數據庫中的數據進行比較，尋找最相似參考點，用匹配定位算法計算未知節點位置。最常用的KNN定位算法，將歐氏距離最小的K個參考點位置坐標求取均值作為未知節點的位置坐標[13]。

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

2 構建位置指紋數據庫

采用Kriging插值算法，在充分考慮區域化變量間的相關性后，對每一個區域化變量賦予一定的權重因數，最后進行加權平均估計預測區域[14]。受井下環境中多徑效應對信號的影響，不能簡單根據信號衰減模型計算RSSI值。Kriging插值算法既利于分析采樣點和待估點的相對位置和RSSI值，又利于通過變異理論從整體信號空間變異結構角度，考量已知點間的關系及其對插值位置的影響，插值結果更準確、更符合真實環境。插值點RSSI值計算公式為

(1)

式中：Z*(x0)為插值點的RSSI值;Z(xi)為第i個參考點xi處的RSSI值;λi為第i個采樣點對插值點的權重因數。Kriging插值算法的關鍵是計算權重因數。

通過變異函數描述空間距離為h的兩個位置指紋之間的相關性，根據N個采樣點位置指紋進行計算，則變異函數r(h)為

(2)

在實際應用中，很難得到所有點之間的變異函數，常采用采樣點的變異函數對變異函數模型進行擬合，其中球狀模型應用最為廣泛，有

(3)

式中：C0、C和a為變異函數的參數，其中C0為塊金值，C為偏基臺值，a為變程。

在保證對待估點Z*(x0)的估計滿足無偏性和最小方差性的情況下，解得權重因數為

λ=A-1γ0,

(4)

3 改進Kriging插值定位算法

3.1 普通灰狼優化算法

通過Kriging插值算法估計部分位置指紋可減輕采集工作量。由于位置指紋的估計精度影響井下定位精度，為進一步提升位置指紋估計精度，達到提高井下定位精度的目的，引入灰狼優化算法優化變異函數的C0、C和a三個參數。灰狼優化算法是由Mirjalili S等提出的、一種通過模擬灰狼的社會等級和狩獵行為的新型群體智能優化算法[15]。該算法具有結構簡單、參數設置少、容易實現、收斂精度高和收斂速度快等特點。

灰狼優化算法實現步驟：

(5)

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

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

(6)

(7)

(8)

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

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

(9)

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

Al=2ar1-a,

(10)

Cl=2r2,

(11)

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

3.2 改進灰狼優化算法

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

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

差分進化算法步驟:

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

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

(12)

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

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

(13)

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

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

(14)

3.3 井下定位算法

通過優化的Kriging插值算法進行井下定位步驟:

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

(2)將采樣點的位置指紋和位置信息通過式(2)構建實驗變異函數數據集。

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

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

(5)根據式(1)、式(3)、式(4)估計插值點的位置指紋。

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

采用改進的灰狼優化算法，優化Kriging插值位置指紋井下定位算法流程見圖2。

4 實驗及結果分析

4.1 實驗環境

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

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

4.2 實驗結果

首先，分析不同數量的采樣點，采用改進Kriging插值算法估計位置指紋的誤差，定義相對估計誤差e，即

(15)

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

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

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

當采樣點數量為50%時，比較隨機選取采樣點與隔點均勻選取采樣點對位置指紋估計的影響，實驗結果見表2。由表2可知，相對于隨機采樣，均勻采樣位置指紋估計誤差更小，并且采用改進Kriging插值算法時，隔點采集50%位置指紋估計剩余50%位置指紋估計誤差最小。

表1 改進Kriging插值算法估計誤差與運算時間

圖3 井下節點部署Fig.3 Underground node deployment

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

其次，分析不同插值算法對定位精度的影響。選擇節點估計坐標與節點實際坐標間距離的均方根誤差E作為評判標準，有

(16)

分別采用IDW插值、普通Kriging插值、改進Kriging插值算法和逐點采集位置指紋，構建位置指紋數據庫，在定位區域內，隨機采集50個未知節點的位置指紋，采用KNN算法進行定位并計算定位誤差。重復實驗20次，將求取均值作為最終誤差。4種算法的定位結果見圖5，定位誤差結果見表3。

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

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

誤差類別逐點采集改進Kriging插值普通Kriging插值IDW插值平均誤差/m2.552.723.033.27誤差方差0.870.951.051.86

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

5 結論

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

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