基于核函數法及粒子濾波的煤礦井下定位算法研究*

崔麗珍，李 蕾，員曼曼，李 璋

(內蒙古科技大學信息工程學院，內蒙古包頭014010)

近年來，定位導航系統不管是在軍用還是民用領域中都有著廣泛的成功應用，這種基于位置的服務LBS(Location-Based Service)包含了個人安全服務、交通導航系統以及本地信息服務等。隨著普適計算的推廣，作為物聯網重要的支撐技術之一，無線定位技術在“感知煤礦”中的應用越來越得到學術界的關注。煤礦巷道一般深處地下幾百米到幾十千米，因此地面上廣為使用的GPS(Global Positioning System)在井下完全失效。伴隨著無線傳感器網絡的迅猛發展，無線傳感器節點為煤礦井下特殊復雜的信道環境［1］中人員及設備提供準確實時的位置信息服務逐漸成為可能。

自20世紀末以來，國內外井下監控系統中采用的無線信號有紅外、超聲波、射頻信號。井下環境受到嚴重的多徑效應和陰影效應的影響，信號到達接收端具有不同的時延和入射角，利用傳輸時間TOA(Time of Arrival)和到達角度AOA(Angle of Arrival)參數估計誤差相對較大［2］，且分別需要精確的時間同步和天線陣列。相比較下，RSSI由射頻芯片本身提供，方便獲取，利用相關濾波算法可以降低巷道中多徑、遮蔽效應帶來的誤差，因此，基于RSSI的煤礦井下定位技術目前受到較大關注。

煤礦井下巷道是一個狹長的電磁傳播受限環境，其中風墻、風橋、風門等設施對無線信號傳輸有一定的影響，其程度取決于設施的構成材料，而井下巷道具體環境也不盡相同，因此射頻信號的傳輸也變得復雜無章。故本文提出一種應用在煤礦井下基于核函數與粒子濾波的指紋匹配定位算法。

1 相關研究

目前，無線定位技術已成為國內外學者研究熱點之一，并且在室內環境、煤礦井下的定位研究中做了一定工作。由微軟公司較早提出的室內定為系統RADAR［3］，利用了最鄰近法和K鄰近法指紋匹配技術，還考慮墻壁對射頻信號傳播的影響，提出了室內無線信號衰減模型，該系統定位運算效率高，但在實際應用中定位的精度相對較低。文獻［4］利用接收信號強度對WLAN中用戶進行定位，提出了基于概率的核函數法和直方圖法，并與確定型最鄰近定位算法做出比較，通過實際試驗證明基于概率方法更具備魯棒性，定位精度更高。文獻［5］將粒子濾波目標追蹤與貝葉斯濾波相結合，采用了機器訓練方法得到似然函數，對比了核函數法、最鄰近法、K鄰近法與Viterbi-like算法，實驗數據表明利用核函數法的結果進行粒子濾波追蹤性能更優越。對于煤礦井下定位技術的研究，中國礦業大學物聯網研究中心在文獻［6-7］中通過對井下信息采集，利用手指模將貝葉斯公式法與最鄰近法融合的算法，實際定位中平均誤差3.3 m，小于K鄰近法5.8 m的誤差。

本文將從如下幾個部分闡述所提出定位算法:第2部分介紹幾種定位算法;第3部分詳細介紹了基于核函數及粒子濾波定位算法的原理;第4部分對本文算法設置實驗，對結果進行分析;最后進行了總結。

2 定位算法

定位算法首先需要建立無線信號與距離或位置間的映射關系。一種是根據信號衰減與傳輸距離間關系建立起路徑損耗模型，通常有自由空間模型、Shadowing模型［8］、“分區依賴”模型［9］等，再將接收到信號強度轉換成傳輸距離;另一種基于信號強度與位置間一一對應關系建立數據庫，采用匹配算法確定節點坐標。前者的優點在于無需建立數據庫，在某種環境中建立起的模型不必因信標節點的改變而改變，但現實中信號接收強度受外界干擾較大導致定位精度低，后者建立的關系數據庫會因信標節點位置的改變而重新建立，但具備較高的定位精度。考慮到煤礦井下各種設施、線纜、金屬管道繁多，巷道結構、形狀及道壁表面有一定差別，本文采用基于位置指紋匹配的定位算法。

2.1 指紋匹配算法

指紋匹配法利用接收信號強度作為位置的標記，主要包括兩個階段:離線訓練階段和在線定位階段［10］。在離線訓練階段，首先布置一個或多個信標節點，然后在待測區域內合理分配多個訓練點，最后順序測得訓練點上節點接收所有信標節點發射的信號強度值，將其作為指紋信息與位置信息一同存入數據庫中。在實時定位階段，由多個信標節點測量到的RSSI值構建指紋信息，并與之前離線訓練階段數據庫中的指紋信息進行匹配處理，最終得到未知節點位置。

對于估計最終目標的位置，有多種指紋匹配法，根據匹配指紋信息的特征可分為確定型定位方法和基于概率的定位方法。

2.2 確定型定位方法

在確定型定位過程中，未知節點的指紋信息直接與數據庫中的信息進行比對，利用曼哈頓距離或歐幾里得距離求出最接近的一個或幾個數據庫中的指紋作為匹配結果。常用的算法有:最鄰近法NN(Nearest Neighbor)、K鄰近法KNN(K Nearest Neighbors)、K加權鄰近法KWNN(K Weighted Nearest Neighbors)。

KWNN算法中，K值為任意值，根據具體實際定位效果選取。當K=1，權值W=1時，為NN算法，當K個數據的權值W都為1/K時(即樣本的質心)，為KNN算法。若用歐幾里得距離表示相似度，該算法可表示為:

式中，r(pos，i)表示在位置pos處第i個信標接收未知節點的信號強度，s(j，i)表示在訓練點j處的第i個信標接收的信號強度，dj表示未知節點與訓練點j的近似程度，Wj和(Xj，Yj)分別是訓練點j所占權重和坐標，(X，Y)為最終估計位置。

2.3 基于概率型方法

在未知節點位置不變情況下，即使發射信號強度相同，由于井下環境影響或一些人為因素干擾，也會導致信標節點接收到的信號強度產生波動，因此，采用指紋信息的概率更能準確表示未知節點所在位置。該方法基于每個訓練點RSSI分布先驗假設和該分布的統計特征［11］，在線定位階段利用貝葉斯估計計算目標位置的后驗概率，最后選擇最大后驗概率的訓練點作為估計位置。由貝葉斯準則可知:

最大后驗概率取決于似然函數和先驗概率，若p(lk)相同(即先驗概率不偏向任何一個特殊位置)，則最大后驗概率取決于似然函數。一般情況，似然函數可采用基于高斯分布的接收信號強度統計模型［7］即:

由于煤礦井下環境受多徑衰落、陰影效應、粉塵等因素干擾，RSSI具有很強的時變性，高斯分布并不能很準確的反映出RSSI分布規律，故本文采用核函數作為似然函數。

3 核函數及粒子濾波定位算法

3.1 核函數法

核函數法將每個訓練點上的每個樣本數據賦予一個以自身為“核心”的函數，等權重的所有樣本對應核函數的總和為在該位置處的概率密度分布。以核函數法構造的似然函數模型可以更精確地表示RSSI概率密度分布情況，其函數模型可以表示為:

式中，K(*，Rn)為核函數，Ns為樣本數，Rn為數據庫中第n個樣本的RSSI指紋。核函數有均勻核函數(Uniform kernel)、Epanechnikov核函數、高斯核函數(Gaussian kernel)［5］等，通常選用高斯核函數:

式中，σ決定了核函數的寬度。在先驗概率相同情況下，綜合式(5)、式(6)、式(8)、式(9)便可得到基于核函數法位置估計:

3.2 粒子濾波

在煤礦井下為了獲得更加精準的目標位置，平滑運動軌跡，采用基于核函數的指紋匹配算法后提出了相應的濾波算法。卡爾曼濾波是線性系統中常用的方法，但在巷道這種多干擾因素的環境中，適用于非線性系統的粒子濾波無疑是更好的選擇。粒子濾波［13］是一種數據融合算法，在定位過程中對輸入的觀測值同系統狀態估計值相融合，它通過蒙特卡洛仿真實現遞歸貝葉斯濾波，關鍵思想是用一組帶有相關權重的隨機樣本來遞歸表示所需的后驗密度函數，再利用這些樣本和其權重計算估計［12］。粒子濾波不再均勻地把樣本空間離散化，樣本的數量足夠大時，根據蒙特卡洛仿真中重要性采樣原理，后驗密度函數可以由式(12)近似:

式中，X0:k是在k時刻樣本集表示系統狀態，Z1:k是k時刻觀測量集合，N是采樣點總數，δ(·)為Dirac函數，wi

k是k時刻第i個采樣點的權重，用遞推的貝葉斯估計表示為:

利用上式實現權重更新;

(4)歸一化權重:

式中，μl服從在［0，1］上的均勻分布，通過上式進行搜索找到m，并對Xmk進行復制;

(6)將上步中結果作為k時刻的最優估計輸出，k+1時刻重復以上步驟。

3.3 算法設計

本文提出了在貝葉斯估計框架下基于核函數指紋匹配的位置估計算法與粒子濾波相結合的定位算法。室內定位中，通常訓練和測試路線均選在了室內中線上［5］，由于模擬井下實驗中節點部署與之不同，采集訓練點、測試點的路線并不重合，只采用核函數法和粒子濾波會帶來縱向較大的誤差。本文充分考慮到實際情況中測試與訓練路徑不相同的情況，為了進一步提高定位精度，引入鄰近的K個樣本對核函數法進行改進。首先，利用基于貝葉斯估計的核函數法計算并取出概率最大的K個信息;其次，求其對應的樣本指紋與在線采集的指紋的歐幾里得距離;然后，將該距離作為權重，計算目標位置;最后，將目標位置作為觀察值利用粒子濾波算法平滑追蹤處理，其算法流程圖如圖1所示。

圖1 算法流程圖

4 算法實現及結果分析

4.1 實驗環境設置

在模擬煤礦井下巷道環境進行了實驗，選取一段32 m×2.4 m的區域，如圖2所示。將定位區域均勻的劃分出80個網格，每個網格范圍為80 cm×80 cm，其中訓練點取在空心點處，考慮到現實中不可能采集到全部位置的指紋信息，故將測試點選在中間實心點處。本實驗將人體對射頻信號的遮擋造成的信號強度衰減和干擾考慮進去，在采集RSSI指紋信息過程中均將1個測試節點佩戴在人員腰部，區域的兩端分別布置了4個信標節點，其射頻信號均可覆蓋定位區域。

圖2 模擬井下實驗設置

離線訓練階段，在每個訓練點處收集50組數據，其中每組數據包含4個信標節點接收到的RSSI值，并把這些值存入終端數據庫中，該表命名為sample，其格式為(id，x_coordinate，y_coordinate，RSSI_1，RSSI_2，RSSI_3，RSSI_4)，即 id 序號、橫縱坐標、4個RSSI值。在線定位階段，未知節點發送數據包，信標節點接收到RSSI值后發送到協調器并上傳到終端，終端調取數據庫開始執行上文所述定位算法，最后通知管理人員未知節點坐標信息，具體流程如圖3所示。

圖3 指紋定位系統流程圖

4.2 結果與分析

實驗中所使用訓練數據都是離線訓練階段采集的訓練樣本，主要從靜止目標、動態目標定位兩方面討論。

對靜止目標進行定位，選用了確定型定位中NN法、KWNN法和基于貝葉斯估計定位中似然函數采用高斯模型和核函數法的定位算法。假設在下一時刻所在位置與上一時刻位置無關條件下，即基于貝葉斯估計算法的后驗概率只依賴似然函數，核函數法中令σ=1。

圖4對4種定位算法的誤差累計分布進行了對比，核函數法的定位誤差明顯優于其他算法，最大誤差6.2 m，平均誤差1.705 m，而采用高斯分布模型的算法不適用于模擬煤礦井下環境，在KWNN算法中，當K=3優于K=4的條件，確定型算法中NN效果最不好，最大誤差達到8.8 m。

圖4 靜態目標定位誤差累計分布函數

對于動態目標定位，比較了采用基于核函數及Markov轉移矩陣的定位算法［2］和本文提出的基于核函數及粒子濾波的定位算法。

由圖5可知采用核函數法及粒子濾波的定位算法結果中有90%誤差在2 m內，其中對核函數法計算出的結果取2個較大后驗概率的位置進行了加權作為觀測量。在粒子濾波算法中，進行1 000次蒙特卡洛實驗，初值在坐標(0，120)處，以 vx=1.6 m/s，vy=0 m/s向前做直線運動，0.5 s采樣一次，橫縱軸方向上的測量協方差設為200和40，定位效果如圖6所示。

圖5 動態目標定位誤差的累計分布圖

圖6 粒子濾波定位結果

5 結論

在煤礦井下環境中，將基于核函數法的匹配算法及粒子濾波相結合應用于無線傳感器網絡中目標定位，降低了因環境對接收信號強度的影響而造成誤差，巷道環境進行實驗中將無線傳感器節點佩戴在人員腰部，考慮到了人體對信號的遮蔽效應。井下實驗結果表明，核函數法定位精度高于確定型指紋匹配算法和基于高斯模型的貝葉斯估計算法，本文提出的粒子濾波算法在動態追蹤方面，同基于Markov轉移矩陣的算法相比，減少了計算量并且精度有所提高。本文的研究對于煤礦井下定位有一定的理論和指導意義。

［1］ 崔麗珍，于洤.基于ZigBee自適應通信在礦井瓦斯監控系統中的設計與實現［J］.礦業安全與環保，2012，39(2):19-21.

［2］ 趙方，羅海勇，林權，等.基于核函數法及馬爾可夫鏈的節點定位算法［J］.通信學報，2010，11:195-204.

［3］ Bahl P，Padmanabhan V N.RADAR:An In-Building RF-Based User Location and Tracking System［C］//Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies.Piscataway，NJ，USA:IEEE，2000.775-784.

［4］ Roos T，Myllym?ki P，Tirri H，et al.A Probabilistic Approach to WLAN User Location Estimation［J］.International Journal of Wireless Information Networks，2002，9(3):155-164.

［5］ Zhang V Y，Wong A K.Kernel Based Particle Filtering for Indoor Tracking in WLANs［J］.Journal of Network and Computer Applications，2012，35(6):1807-1817.

［6］ 劉曉文，張秀均，郝麗娜，等.基于WI-FI的井下定位算法研究［J］.傳感技術學報，2012，06:854-858.

［7］ 郝麗娜，張秀均，郁萬里，等.基于 RSS手指模的煤礦井下WLAN 定位方法［J］.傳感器與微系統，2012，09:46-49.

［8］ Ali S，Nobles P.A Novel Indoor Location Sensing Mechanism for IEEE 802.11 b/g Wireless LAN［C］//Positioning，Navigation and Communication，2007.WPNC’07.4th Workshop on.IEEE，2007:9-15.

［9］ Rappaport T S.Wireless Communications Principles and Practice［M］.New Jersey:Prentice Hall PTR，2003.

［10］趙方，羅海勇，馬嚴，等.基于公共信標集的高精度射頻指紋定位算法［J］.計算機研究與發展，2012(2):243-252.

［11］徐勇軍.物聯網實驗教程［M］.北京:機械工業出版社，2011.

［12］ Arulampalam M S，Maskell S，Gordon N，et al.A Tutorial on Particle Filters forOnlineNonlinear/Non-Gaussian Bayesian Tracking［J］.SignalProcessing，IEEE Transactions on，2002，50(2):174-188.

［13］李紅春，趙曉光，譚民.無線傳感器網絡中基于粒子濾波的人員跟蹤方法［J］.傳感技術學報，2012(6):807-814.

［14］ 胡士強，敬忠良.粒子濾波算法綜述［J］.控制與決策，2005(4):361-365，371.