一種基于遺傳神經網絡的煤礦井下定位算法

逄明祥，王善培，李 乾，程學珍

（1.山東科技大學a.電子信息工程學院；b.電氣與自動化工程學院，山東青島 266590；2.中車青島四方車輛研究所有限公司，山東青島 266011）

0 引言

煤炭作為我國的第一大能源，對于國民生產和經濟具有重要意義。近年來煤礦生產安全事故頻發，引起全社會的高度關注［1-3］。提高我國煤礦的信息化程度，成為保障煤礦安全生產的重要手段，其中煤礦井下人員定位系統是煤礦信息化建設的重要組成部分，煤礦井下定位算法［4-6］的研究也成為重要課題。

煤礦井下定位算法大致可分為基于測距的和非測距的算法兩大類［7-9］。非測距定位算法主要是依據網絡的連通性來實現對待測點的定位，如質心算法、DVHop、APIT 等常見算法［10-14］；測距定位算法主要是通過測量信標節點與待測未知節點之間的距離或角度來實現定位，如TOA、TDOA、RSSI 等算法。TOA 測距定位算法主要有：基于改進均值濾波和參數擬合的礦井TOA幾何定位方法［15］、基于WiFi 和計時誤差抑制的TOA煤礦井下目標定位算法［16］、基于WiFi 信號二次擴頻的礦井TOA測距方法［17］和基于測距值二次重構的彎曲巷道目標定位方法［18］，該類定位方法很難實現目標點與基站之間的時間同步［19］，造成測距誤差。在復雜的井下環境中，NLOS 是造成無線定位誤差的主要原因［20］。本文提出的利用遺傳神經網絡來擬合TDOA測量值和目標點坐標值之間的映射關系，依靠神經網絡強大的非線性映射能力來減小TDOA測量值中包含的NLOS 誤差所造成的定位誤差，基于Chan-Taylor算法，將遺傳神經網絡算法與Taylor 算法相結合，進一步提高定位精度。

1 基于遺傳神經網絡的超寬帶井下定位算法

1.1 遺傳算法的數學模型

遺傳算法的具體實施過程包括編碼、產生初始群體、計算個體適應度、復制、交換、突變、反復迭代、種植等操作。設G 為遺傳算法迭代次數。需要確定一組初始權值和閾值的編碼方式以及字符串長度L，這里采用實數編碼方式。對輸入的種群進行初始化，確定群體規模M。以此計算群體中各個個體的適應度。在室內定位時，輸入訓練樣本，以輸出結果與樣本期望值的誤差平方和倒數作為適應度，誤差越小，適應度越大，據此評價權值和閾值的優劣。適應度函數為：

式中：N為輸出層神經元個數；Xpj為第p個輸入樣本在第j個神經元的實際值，Opj則為第p個輸入樣本在第j個神經元的輸出值。

通過式（1）計算出適應度值，根據計算結果依次執行復制、交換、突變等操作。

步驟1復制操作。設復制概率為Pt，j為復制次數，根據適應度的大小，選擇個體進行復制，并加入下一代新群體中，直到復制個體數達到Pt·M 時停止。同時刪除適應度較低的個體，將剩余個體加入下一代群體之中，并保持群體規模為M不變。

步驟2交換操作。設交換概率為Pe，根據適應度選擇2 個個體進行交換操作，然后將交換后的2 個個體代替原個體插入群體之中，交換次數滿足Pe·M時停止。

步驟3突變操作。突變操作針對的是個體編碼中的字符，設突變概率為Pm，則發生突變的字符數量為Pm·L·M。經過以上這3 步操作產生新一代群體之后，重新計算個體適應度，重復上述操作，不斷優化初始確定的連接權值和閾值，直到訓練的樣本誤差滿足定位要求時停止迭代。遺傳算法優化BP 神經網絡的具體流程如圖1 所示。

圖1 遺傳神經網絡的工作流程圖

1.2 BP神經網絡的定位模型

神經網絡種類繁多，本文以BP 神經網絡作為基礎。BP神經網絡雖然應用比較廣泛，但仍然存在許多不足，主要有收斂速度慢，網絡極易陷入局部極值點，以及對于初始權值、閾值的選擇缺乏依據等［21-23］。為克服BP神經網絡不足，可利用遺傳算法優化BP神經網絡的初始權值和閾值，來提高神經網絡算法的性能。遺傳算法［24］是一種以優化變量的遺傳編碼為運算和搜索對象的算法，它根據適應度信息來指導搜索，具有很強的全局優化能力。

神經網絡主要由輸入層、隱含層、輸出層組成，在輸入層輸入的是帶有非視距誤差的TDOA 測量值，輸出層輸出的是目標點的坐標值。確定神經網絡模型的難點主要在于隱含層的層數和隱含層神經元數量以及各層激勵函數和訓練函數的選擇，目前并沒有具體理論上的指導。結合仿真經驗考慮，一層隱含層的神經網絡就能夠很好地滿足算法需求，并且一層隱含層的網絡結構比較簡單，訓練時間較短，比較容易實現，所以隱含層數確定為1。對于隱含層神經元數量的確定也比較棘手，通過大量的實驗，人們總結出了估算隱含層神經元數量的方法［25］：

式中：INnum、Onum分別為輸入層和輸出層的節點個數；Hnum為隱含層神經元數量；n 為1～10 之間的任意值。其中對于隱含層的激勵函數，采用Sigmoid 函數f1（x）tan h（x），對于輸出層激勵函數，采用線性函數f2（x）=kx。

在本模型的仿真中，輸入層為各定位基站與目標點的TDOA測量值，本文設定共7 個基站，所以輸入層節點為6 個，輸出層為目標點坐標值，根據仿真分析和上述公式，設定隱含層神經元個數為17 個，整個神經網絡為6：17：2 的結構。圖2 為煤礦井下非視距環境中的神經網絡定位模型。

圖2 用于井下定位的BP神經網絡模型

1.3 基于TDOA的Taylor算法模型

Taylor算法［26］是一種遞歸算法，其數學原理是在初始值處對非線性方程組進行泰勒級數展開轉化為線性方程［27］，利用加權最小二乘法估計目標節點的位置，使用新的估計值作為初始值重復以上步驟，直到得到滿足所需誤差精度的最終結果。

假定在二維平面上任意的分布著M 個定位基站（base station，BS），設第i 個基站BSi位置為（xi，yi），其中BS1為參考基站，待定位點MS 坐標為（x，y），和BSi之間的距離為ri，第i個定位基站和參考基站之間的測量距離差為ri，1，信號傳輸速度為c。當定位過程存在測距誤差時：

式中：Ri，1為目標節點與各基站的TDOA真實值；ni，1為目標節點與各基站的TDOA測距誤差。假設目標節點真實坐標為（^x，^y），估計坐標的誤差表示為（σx，σy），那么估計坐標（x，y）表示為：

將式（4）在初始點（x0，y0）處進行一階泰勒展開得：

式（7）的矩陣式為

式中：

對式（8）作加權最小二乘估計得：

式中，Q 為TDOA 測量誤差的協方差矩陣。假設誤差門限為ε，如果迭代運算之后的結果與初值滿足：

此時的結果就是要求的目標節點的估計坐標。

Taylor需要一個比較精確的初始值才能夠保證算法得收斂，但在目標節點未知的情況下往往很難提供這個初始位置，這種情況下Taylor 算法不僅計算量比較大，而且不能保證收斂。將遺傳神經網絡定位算法結合使用，將遺傳神經網絡的輸出作為Taylor 算法的初始坐標進行迭代計算，來獲取更高的定位精度。

2 仿真與分析

為了驗證遺傳神經網絡定位算法（GA-BP）的定位性能，采用Matlab 軟件進行算法仿真，并與幾種傳統的室內定位算法進行比較。假設一段煤礦井下巷道長為40 m，寬為5 m，巷道中設置7 個基站。其中參考基站BS0位于巷道中央，坐標設置為（0，0），單位為cm，則定位基站坐標按照蜂窩式結構分別設置為：BS1（1 000，250），BS2（2 000，0），BS3（1 000，-250），BS4（-1 000，-250），BS5（-2 000，0），BS6（-1 000，250）。定位目標節點的位置則是在巷道范圍內隨機產生。在井下環境中NLOS引起的測距誤差一般服從高斯、Delta 或者均勻分布，在仿真中假設其服從（0，σ2）高斯分布。

在巷道范圍的環境下隨機獲取2 000 個目標點坐標，分別計算6 個定位基站關于目標點的TDOA 數據作為訓練樣本，代入遺傳神經網絡中，結合目標點真實坐標對其進行訓練。對于遺傳算法部分，設定遺傳算法的群體規模為50，最大遺傳代數為10，變異率為0.001，交叉率為0.6。

通過測定若干組隨機目標節點在NLOS 環境下的TDOA數據，輸入訓練好的遺傳神經網絡模型中來獲得定位結果。

圖3 是遺傳神經網絡定位算法與傳統的Chan 算法在σ取值為0.1 情況下的定位性能比較，由1 000次獨立位置估計得到。Chan 算法是簡單實用的定位算法，在視距環境下具有比較好的定位性能。此時NLOS導致的TDOA 測量誤差非常小，近似于視距傳播。圖中橫坐標為定位誤差，縱坐標為累積分布函數（Cumulative distribution function，CDF）。累積分布函數是指定位誤差在某個設定好的閾值之內的定位次數占總的定位次數的比例，可直觀看出定位系統在某種精度下的定位成功率。由圖可見，在測距誤差較小的情況下，Chan算法的定位性能明顯好于GA-BP算法。

圖3 σ為0.1時的定位性能

當TDOA測距誤差的增大，算法的定位性能會受到不同程度的影響。圖4 是在σ的取值為0.7 情況下的兩種算法的定位性能比較，此時的Chan 算法性能低于遺傳神經網絡算法，說明在較高的TDOA 測量誤差的環境下，Chan算法的定位性能會有明顯下降。

圖4 σ為0.7時的定位精度

圖5 是Chan算法和GA-BP算法隨著測距誤差的增大其定位性能的變化情況。其中橫坐標為a，縱坐標為定位算法的均方根誤差。為了減小計算量，圖中均方根誤差（RMSE）值由100 次獨立位置估計計算獲得。由圖5 可見，Chan算法在TDOA測量誤差比較小的情況下具有較高的定位精度，但是隨著TDOA 測量誤差的提高，其定位精度迅速下降，證明在非視距傳播條件下，Chan算法定位性能很差。而遺傳神經網絡算法的定位性能明顯更好，即使是在比較大的TDOA 測量誤差的情況下，其定位精度的變化也比較平穩，證明了遺傳神經網絡起到了減小TDOA 測量誤差的作用，能夠很好地擬好TDOA測量數據與目標節點坐標之間的映射關系。

圖5 Chan算法與GA-BP算法的RMSE曲線圖

對Chan-Taylor 協同算法進行仿真，并與Chan 算法、遺傳神經網絡算法進行比較。Chan-Taylor 協同算法是結合Chan算法和Taylor 算法二者優點的一種定位算法，該算法將Chan 算法的結果作為初始值代入Taylor算法來獲得更高的定位精度，如圖6 所示。

圖6 4種算法的RMSE曲線對比圖

由圖可見，Chan-Taylor 算法相較于Chan 算法定位性能確實有所提升，尤其是在TDOA 測量誤差很小的情況下，其定位精度非常高，但是隨著TDOA測量誤差的提高，其整體變化趨勢與Chan 算法類似，在測量誤差較高的情況下遺傳神經網絡算法結合Taylor算法能夠獲得更好的定位精度。

參考Chan-Taylor協同算法，將遺傳神經網絡算法與Taylor算法相結合（GA-BP-Taylor）達到提高定位精度的目的。最終4 種算法的均方根誤差（RMSE）值見表1。由表1 可見，遺傳神經網絡結合Taylor 算法確實能夠獲得更好的定位效果。

表1 4 種算法的RMSE值cm

3 結語

本文提出了一種基于遺傳神經網絡和Taylor算法相結合的井下定位算法。該算法利用遺傳算法優化神經網絡，克服了其易陷入局部最優的缺點，依靠神經網絡逼近任意非線性映射的能力和較快的學習特性來擬合TDOA測量值和目標點坐標值之間的映射關系，減小非視距傳播造成的TDOA 測量誤差，有效地克服諸如Chan算法之類的常用定位算法易受NLOS 影響的缺陷。仿真結果表明，該算法對于非視距環境下的測距誤差具有明顯的抑制性能，與傳統定位算法相比具有更高的定位精度和更好的穩定性。