煤礦環境下無線傳感器定位技術的算法研究

何維斌

現在，我國大部分煤礦安全系統的傳感器基本上都是采用有線方式架構，但這些傳統的監測方法和思路存在許多不足，相當程度上影響了正常檢測井下信息以及礦難的搜救展開，因此，開發無線傳感器網絡監控系統非常緊迫。

1 無線傳感器網絡的定位機制

在無線傳感器網絡系統中，常常把定位機制劃分為：基于距離的定位機制和基于非測距的定位機制。在基于距離的定位機制中，根據測量節點間距離或方位，可采用的方法有接受信號強度指示器 RSSI［1］(Received Signal Strength Indicator)，到達時間 TOA(Time Of Arrival)，到達時間差 TDOA［2］(Time Difference On Arrival)，到達角 AOA［3］(Angle Of Arrival)等?；赥OA的定位精度高，但要求節點間保持精確的時間同步;RSSI是隨著實際情況變化而變得很不穩定的方法;TDOA方法受限于超聲波傳播距離有限和非視距傳輸問題對超聲波信號傳播的影響;AOA也受外界環境影響，而且需要額外硬件。因此，本文主要基于非測距定位算法來進行分析。

2 基于非測距的典型定位算法

2.1 APIT 定位算法［4］

APIT定位算法的基本思想為：首先未知節點選擇3個信標節點，要求是這3個節點是能夠與未知節點互通信息的，然后檢測此未知節點是在所選3個節點組成的三角形內部還是外部;然后再選擇其它不同的3個信標節點做同樣的檢測;如此窮盡檢測，直到取得所需的精度值，假如未知節點在所得三角形內部，就把此三角形質心坐標作為未知節點的位置坐標。

APIT算法的特點：由于采用的是窮盡檢測，因此，誤差概率比較小，但是此算法要求較大密度的信標節點，因此較為復雜。

2.2 DV －Hop 定位算法［5］

DV－Hop定位算法采用的是網絡中的距離向量路由算法的基本思想。其原理是：首先計算出未知節點與信標節點的最小跳數，然后估算平均每跳的距離，進而讓最小跳數乘以平均每跳距離，這樣就可得未知節點與信標節點之間的距離，最后采用極大似然估計法的思想可得未知節點的坐標。

2.3 Amorphous定位算法［6］

Amorphous定位算法的使用需要滿足兩個條件，分別為：全部的信標節點和未知節點有效通信半徑基本相同而且是已知值、無線傳感器網絡設置區內節點密度相當大或網絡連通性較優。它是利用最大似然估計法的思想得到未知節點坐標。

2.4 質心定位算法［7］

質心定位算法的基本思想為：利用了找多邊形的質心思想，首先是確定某一范圍，然后讓信標節點規律性的給鄰近節點發送廣播信息分組，當未知節點收到各個信標節點信息分組信號值大于門限值時，就可以通過節點坐標公式得出此未知節點的坐標。質心定位算法具有許多優點，例如，信標節點的數目固定，而且它們傳送信號范圍也是相互疊合的，這樣就不再需要信標節點和未知節點之間去協調，質心算法實現起來相當簡單，而且精確度較高。

3 兩種環境四種算法定位性能的仿真分析

3.1 煤礦通道環境下定位性能分析

狹長的煤礦通道環境下，由于受實際情況限制，仿真環境設定如下：傳感器節點分布區域為二維平面［0，100］×［0，5］m2，將信標節點錯位分布于該區域的左右兩邊，未知節點隨機分布在該區域，信標節點總數(AQ)為20個;未知節點總數(NQ)100個;通信半徑(DC)50 m。由Matlab隨機生成100個點(作為未知節點)分布在的仿真區域內，20個信標節點，完成的WSN節點分布見圖1。

圖1 WSN節點分布示意圖

煤礦通道環境狹長而結構復雜，在這樣環境下，對異常情況進行精確定位，需要從多方面進行考慮，來找出一種更適于這種環境的定位技術。因此，根據定位算法的性能影響因素，從以下方面來分析：

1)距離估算誤差的影響。

DV－Hop和Amorphous算法是采用不同方法對節點間距離估算，定位受距離誤差影響較大;APIT定位算法和質心定位算法無需知道此距離，因此，定位時基本上不受距離估算誤差的影響。以下通過MATLAB仿真實驗來分析距離估算誤差對Amorphous定位算法、質心定位算法和APIT定位算法定位性能的影響。

選擇對Amorphous定位算法、APIT定位算法、質心定位算法做1 000次MATLAB仿真，可以得到比較真實的結論，下面給出通信半徑(DC)為50 m，信標節點為10，以上算法距離估算誤差對平均定位誤差影響的仿真結果，見圖2。

圖2 距離估算誤差對定位性能的影響仿真

由圖2可知：距離估算誤差對APIT算法和質心算法的定位誤差影響相當小，但對Amorphous定位算法的影響較大?？傻贸鼋Y論：當要求定位精度較高時，不宜采用Amorphous定位算法。

2)信標節點密度的影響。

在WSN定位系統中，錨節點(即信標節點)與普通終端節點相比較，硬件成本明顯較高，但是大量地設置信標節點卻能顯著的減少定位誤差;為了提高定位精度，常常會增加錨節點，這樣一來，系統成本相應地提高。因此，錨節點布設的多少也會影響系統定位的性能。下面是以信標節點密度作為因素來參考，給出錨節點密度的計算公式：

式中：

DA—錨節點密度;

AQ—錨節點的數量;

NQ—未知節點的數量。

根據質心算法和APIT算法理論，質心算法是求解多邊形的質心來估計真實未知節點的坐標;而APIT算法求解多個三角形共交區域的質心來估計未知節點的坐標，見圖3。

圖3 質心估計和APIT估計坐標同真實坐標的位置比較

在未知節點M周圍有A、B、C、D四個信標節點，由質心算法可得到四邊形ABCD的質心為M1;而根據APIT算法原理，可找到未知節點M在△ABC和△BCD的共交區域△BEC中，再求解出△BEC的質心M2。此時，明顯可以看出M2比M1到真實坐標M的誤差要大的多。因此，可以得出APIT需要在信標節點密集的情況下，盡可能的減小共交區域，而且需信標節點分布均勻，才能達到好的定位性能。下面通過仿真來驗證上面的結論。

仿真條件同上所設狹長的通道環境。信標節點數目有 5 種情況：6、10、16、20、30 個信標，未知節點總數為100(NQ=100)。為了得到較為真實的結論，對APIT定位算法和質心定位算法隨機做1 000次MATLAB仿真，去除APIT失效情況，得到平均定位誤差。算法仿真結果見圖4。

圖4 信標節點密度對定位性能影響的仿真

從仿真圖中可以看出，APIT算法比質心定位算法受信標節點密度影響大，因此，APIT算法在信標節點不密集的情況下，定位誤差明顯增大。實際應用中，常常需要在信標節點不密集的情況下解決定位問題，如發生礦難。質心定位算法的定位誤差受信標節點密度影響較小，所以，質心定位算法比APIT算法更具有實際應用價值。

根據以上的分析和仿真驗證，證實了在煤礦通道環境下進行定位，質心算法比其他三種算法都有效。

3.2 煤礦井下密集型環境下定位性能分析

在煤礦井下密集型環境中，由于定位范圍較大，未知節點密度高，信標節點少，因此環境設置如下：［0，100］×［0，100］m2的二維區域，錨節點(即信標節點)在該區域是均勻分布的，未知節點在該區域是隨機分布的，錨節點總數(即信標節點總數)為12個(即AQ=12)，未知節點總數為200個(NQ=200)，完成后的WSN節點分布，見圖5所示。

在井下密集型節點環境下，由于特殊情況使信標節點數減少，如何還能夠利用剩余的信標節點進行有效的定位，這就需要找出一種定位技術可以在這種情況下有較好的定位性能。針對幾種典型算法做以下分析。

1)定位覆蓋率的分析。

圖5 傳感器網絡節點分布示意圖(100 m×100 m)

根據APIT算法特性，該算法雖然誤差概率相對較小，然而因定位區域需要細分和未知節點與參考節點必須為相鄰的需求，為此，該算法對參考節點密度要求相對較高。因此，在較少信標節點情況下一般定位效果不好。下面通過仿真實驗，分析信標節點密度對APIT、質心算法、DV－hop算法定位覆蓋率的影響情況。

仿真環境如上所設，信標節點數目有5種情況：12、20、30、42、56，假設未知節點總數為200 個(即 NQ=200)，通信半徑為30 m。一共做1 000次MATLAB仿真，這樣可得知此算法失效的總數量，計算定位覆蓋率。仿真分析見圖6。

圖6 三種算法定位覆蓋率比較示意圖

從圖6可以看出，當信標節點密度不夠時，在煤礦井下密集型環境下APIT算法的定位覆蓋率不到30%。定位的盲區較大，明顯不能滿足定位的要求，因此，APIT不適用于應用在此環境下進行定位。

2)信標節點密度對定位精度影響。

根據DV－hop算法原理，此算法需要計算平均每跳的距離和未知節點與信標節點的最小跳數，然后利用最小跳數乘以平均每跳距離，這樣能得到未知節點與信標節點之間的距離，再利用最大似然估計法的思想可得到未知節點的坐標。因此，這種算法能夠根據有限的幾個信標節點，計算最小跳數和平均每跳距離來求解未知節點坐標。需要的信標節點較少，是一個可擴展的算法，對于各向同性的密集網絡，也能夠達到適當的定位精度。

為了驗證以上的分析結論，下面在不同信標節點密度下，來對DV－hop和質心算法的定位性能進行分析。仿真環境設置同上節。1 000次仿真結果求平均值，見圖7。

圖7 信標節點密度不同時兩種算法定位性能比較

從圖7可看出，DV－hop算法定位性能受信標節點密度影響不大，在信標節點為12的很少情況時，也能夠對200個未知節點進行較好的定位，誤差在10 m左右。而質心算法盡管在信標節點為56時，定位誤差只有5.7 m;但信標節點為12和20的較少情況下，定位誤差高達16 m。

因此，從以上分析可以證實DV－hop算法更適用于煤礦井下密集型環境，信標節點較少的情況。

4 結論

在無線傳感器網絡的定位技術研究中，最重要的性能指標是定位誤差。而影響定位誤差的主要因素有：距離估算誤差、信標節點密度、定位覆蓋率等方面。

本文主要在煤礦通道和煤礦井下平臺兩種環境下，對定位算法進行研究。通過對以上距離估算誤差、信標節點密度、定位覆蓋率這些方面進行分析并仿真，分別驗證了質心算法最適于煤礦通道環境，而DV－hop算法則適用于煤礦井下密集型網絡的定位?？蔀閷嶋H應用中，根據不同環境選擇相適合的定位技術提供一定的參考。

［1］ 馬祖長，孫怡寧.無線傳感器網絡節點的定位算法［J］.計算機工程，2004，30(7)：13－14.

［2］ 孫利民，李建中.無線傳感器網絡［M］.北京：清華大學出版社，2005：3－25.

［3］ Doherty L，Pister K，and Ghaoui L.Convex position estimation in wireless sensor networks.Proc.of the IEEE INFOCOM［M］.Anchorage，AK，USA，2001：1655 －1663.

［4］ 楊 維，李 澎，孫繼平.類矩形礦井巷道中UHF寬帶電磁波統計信道建模［J］.煤炭學報，2008，33(4)：467－472.

［5］ 史 龍，王福豹.無線傳感器網絡自身定位算法研究［D］.西安：西北工業大學碩士論文，2006.

［6］ Priyantha N B，Balakrishnam H.Anchor－ Free Distributed Localization in Sensor Networks［M］.MIT Lab for Computer Science，2003.

［7］ Nagpal R，Shrobe H.Bachrach J.Organizing a global coordinate system from local information on an ad hoc sensor network［A］.Zhao F，Guibas L.Proceedings of the 2nd International Workshop on Information Processing in Sensor Networks.Berlin，Germany：Springer－ Verlag，2003：333 －348.