煤礦環(huán)境下無(wú)線傳感器定位技術(shù)的算法研究

何維斌

現(xiàn)在，我國(guó)大部分煤礦安全系統(tǒng)的傳感器基本上都是采用有線方式架構(gòu)，但這些傳統(tǒng)的監(jiān)測(cè)方法和思路存在許多不足，相當(dāng)程度上影響了正常檢測(cè)井下信息以及礦難的搜救展開(kāi)，因此，開(kāi)發(fā)無(wú)線傳感器網(wǎng)絡(luò)監(jiān)控系統(tǒng)非常緊迫。

1 無(wú)線傳感器網(wǎng)絡(luò)的定位機(jī)制

在無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)中，常常把定位機(jī)制劃分為：基于距離的定位機(jī)制和基于非測(cè)距的定位機(jī)制。在基于距離的定位機(jī)制中，根據(jù)測(cè)量節(jié)點(diǎn)間距離或方位，可采用的方法有接受信號(hào)強(qiáng)度指示器 RSSI［1］(Received Signal Strength Indicator)，到達(dá)時(shí)間 TOA(Time Of Arrival)，到達(dá)時(shí)間差 TDOA［2］(Time Difference On Arrival)，到達(dá)角 AOA［3］(Angle Of Arrival)等。基于TOA的定位精度高，但要求節(jié)點(diǎn)間保持精確的時(shí)間同步;RSSI是隨著實(shí)際情況變化而變得很不穩(wěn)定的方法;TDOA方法受限于超聲波傳播距離有限和非視距傳輸問(wèn)題對(duì)超聲波信號(hào)傳播的影響;AOA也受外界環(huán)境影響，而且需要額外硬件。因此，本文主要基于非測(cè)距定位算法來(lái)進(jìn)行分析。

2 基于非測(cè)距的典型定位算法

2.1 APIT 定位算法［4］

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

APIT算法的特點(diǎn)：由于采用的是窮盡檢測(cè)，因此，誤差概率比較小，但是此算法要求較大密度的信標(biāo)節(jié)點(diǎn)，因此較為復(fù)雜。

2.2 DV －Hop 定位算法［5］

DV－Hop定位算法采用的是網(wǎng)絡(luò)中的距離向量路由算法的基本思想。其原理是：首先計(jì)算出未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，然后估算平均每跳的距離，進(jìn)而讓最小跳數(shù)乘以平均每跳距離，這樣就可得未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離，最后采用極大似然估計(jì)法的思想可得未知節(jié)點(diǎn)的坐標(biāo)。

2.3 Amorphous定位算法［6］

Amorphous定位算法的使用需要滿足兩個(gè)條件，分別為：全部的信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)有效通信半徑基本相同而且是已知值、無(wú)線傳感器網(wǎng)絡(luò)設(shè)置區(qū)內(nèi)節(jié)點(diǎn)密度相當(dāng)大或網(wǎng)絡(luò)連通性較優(yōu)。它是利用最大似然估計(jì)法的思想得到未知節(jié)點(diǎn)坐標(biāo)。

2.4 質(zhì)心定位算法［7］

質(zhì)心定位算法的基本思想為：利用了找多邊形的質(zhì)心思想，首先是確定某一范圍，然后讓信標(biāo)節(jié)點(diǎn)規(guī)律性的給鄰近節(jié)點(diǎn)發(fā)送廣播信息分組，當(dāng)未知節(jié)點(diǎn)收到各個(gè)信標(biāo)節(jié)點(diǎn)信息分組信號(hào)值大于門限值時(shí)，就可以通過(guò)節(jié)點(diǎn)坐標(biāo)公式得出此未知節(jié)點(diǎn)的坐標(biāo)。質(zhì)心定位算法具有許多優(yōu)點(diǎn)，例如，信標(biāo)節(jié)點(diǎn)的數(shù)目固定，而且它們傳送信號(hào)范圍也是相互疊合的，這樣就不再需要信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)之間去協(xié)調(diào)，質(zhì)心算法實(shí)現(xiàn)起來(lái)相當(dāng)簡(jiǎn)單，而且精確度較高。

3 兩種環(huán)境四種算法定位性能的仿真分析

3.1 煤礦通道環(huán)境下定位性能分析

狹長(zhǎng)的煤礦通道環(huán)境下，由于受實(shí)際情況限制，仿真環(huán)境設(shè)定如下：傳感器節(jié)點(diǎn)分布區(qū)域?yàn)槎S平面［0，100］×［0，5］m2，將信標(biāo)節(jié)點(diǎn)錯(cuò)位分布于該區(qū)域的左右兩邊，未知節(jié)點(diǎn)隨機(jī)分布在該區(qū)域，信標(biāo)節(jié)點(diǎn)總數(shù)(AQ)為20個(gè);未知節(jié)點(diǎn)總數(shù)(NQ)100個(gè);通信半徑(DC)50 m。由Matlab隨機(jī)生成100個(gè)點(diǎn)(作為未知節(jié)點(diǎn))分布在的仿真區(qū)域內(nèi)，20個(gè)信標(biāo)節(jié)點(diǎn)，完成的WSN節(jié)點(diǎn)分布見(jiàn)圖1。

圖1 WSN節(jié)點(diǎn)分布示意圖

煤礦通道環(huán)境狹長(zhǎng)而結(jié)構(gòu)復(fù)雜，在這樣環(huán)境下，對(duì)異常情況進(jìn)行精確定位，需要從多方面進(jìn)行考慮，來(lái)找出一種更適于這種環(huán)境的定位技術(shù)。因此，根據(jù)定位算法的性能影響因素，從以下方面來(lái)分析：

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

DV－Hop和Amorphous算法是采用不同方法對(duì)節(jié)點(diǎn)間距離估算，定位受距離誤差影響較大;APIT定位算法和質(zhì)心定位算法無(wú)需知道此距離，因此，定位時(shí)基本上不受距離估算誤差的影響。以下通過(guò)MATLAB仿真實(shí)驗(yàn)來(lái)分析距離估算誤差對(duì)Amorphous定位算法、質(zhì)心定位算法和APIT定位算法定位性能的影響。

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

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

由圖2可知：距離估算誤差對(duì)APIT算法和質(zhì)心算法的定位誤差影響相當(dāng)小，但對(duì)Amorphous定位算法的影響較大。可得出結(jié)論：當(dāng)要求定位精度較高時(shí)，不宜采用Amorphous定位算法。

2)信標(biāo)節(jié)點(diǎn)密度的影響。

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

式中：

DA—錨節(jié)點(diǎn)密度;

AQ—錨節(jié)點(diǎn)的數(shù)量;

NQ—未知節(jié)點(diǎn)的數(shù)量。

根據(jù)質(zhì)心算法和APIT算法理論，質(zhì)心算法是求解多邊形的質(zhì)心來(lái)估計(jì)真實(shí)未知節(jié)點(diǎn)的坐標(biāo);而APIT算法求解多個(gè)三角形共交區(qū)域的質(zhì)心來(lái)估計(jì)未知節(jié)點(diǎn)的坐標(biāo)，見(jiàn)圖3。

圖3 質(zhì)心估計(jì)和APIT估計(jì)坐標(biāo)同真實(shí)坐標(biāo)的位置比較

在未知節(jié)點(diǎn)M周圍有A、B、C、D四個(gè)信標(biāo)節(jié)點(diǎn)，由質(zhì)心算法可得到四邊形ABCD的質(zhì)心為M1;而根據(jù)APIT算法原理，可找到未知節(jié)點(diǎn)M在△ABC和△BCD的共交區(qū)域△BEC中，再求解出△BEC的質(zhì)心M2。此時(shí)，明顯可以看出M2比M1到真實(shí)坐標(biāo)M的誤差要大的多。因此，可以得出APIT需要在信標(biāo)節(jié)點(diǎn)密集的情況下，盡可能的減小共交區(qū)域，而且需信標(biāo)節(jié)點(diǎn)分布均勻，才能達(dá)到好的定位性能。下面通過(guò)仿真來(lái)驗(yàn)證上面的結(jié)論。

仿真條件同上所設(shè)狹長(zhǎng)的通道環(huán)境。信標(biāo)節(jié)點(diǎn)數(shù)目有 5 種情況：6、10、16、20、30 個(gè)信標(biāo)，未知節(jié)點(diǎn)總數(shù)為100(NQ=100)。為了得到較為真實(shí)的結(jié)論，對(duì)APIT定位算法和質(zhì)心定位算法隨機(jī)做1 000次MATLAB仿真，去除APIT失效情況，得到平均定位誤差。算法仿真結(jié)果見(jiàn)圖4。

圖4 信標(biāo)節(jié)點(diǎn)密度對(duì)定位性能影響的仿真

從仿真圖中可以看出，APIT算法比質(zhì)心定位算法受信標(biāo)節(jié)點(diǎn)密度影響大，因此，APIT算法在信標(biāo)節(jié)點(diǎn)不密集的情況下，定位誤差明顯增大。實(shí)際應(yīng)用中，常常需要在信標(biāo)節(jié)點(diǎn)不密集的情況下解決定位問(wèn)題，如發(fā)生礦難。質(zhì)心定位算法的定位誤差受信標(biāo)節(jié)點(diǎn)密度影響較小，所以，質(zhì)心定位算法比APIT算法更具有實(shí)際應(yīng)用價(jià)值。

根據(jù)以上的分析和仿真驗(yàn)證，證實(shí)了在煤礦通道環(huán)境下進(jìn)行定位，質(zhì)心算法比其他三種算法都有效。

3.2 煤礦井下密集型環(huán)境下定位性能分析

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

在井下密集型節(jié)點(diǎn)環(huán)境下，由于特殊情況使信標(biāo)節(jié)點(diǎn)數(shù)減少，如何還能夠利用剩余的信標(biāo)節(jié)點(diǎn)進(jìn)行有效的定位，這就需要找出一種定位技術(shù)可以在這種情況下有較好的定位性能。針對(duì)幾種典型算法做以下分析。

1)定位覆蓋率的分析。

圖5 傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布示意圖(100 m×100 m)

根據(jù)APIT算法特性，該算法雖然誤差概率相對(duì)較小，然而因定位區(qū)域需要細(xì)分和未知節(jié)點(diǎn)與參考節(jié)點(diǎn)必須為相鄰的需求，為此，該算法對(duì)參考節(jié)點(diǎn)密度要求相對(duì)較高。因此，在較少信標(biāo)節(jié)點(diǎn)情況下一般定位效果不好。下面通過(guò)仿真實(shí)驗(yàn)，分析信標(biāo)節(jié)點(diǎn)密度對(duì)APIT、質(zhì)心算法、DV－h(huán)op算法定位覆蓋率的影響情況。

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

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

從圖6可以看出，當(dāng)信標(biāo)節(jié)點(diǎn)密度不夠時(shí)，在煤礦井下密集型環(huán)境下APIT算法的定位覆蓋率不到30%。定位的盲區(qū)較大，明顯不能滿足定位的要求，因此，APIT不適用于應(yīng)用在此環(huán)境下進(jìn)行定位。

2)信標(biāo)節(jié)點(diǎn)密度對(duì)定位精度影響。

根據(jù)DV－h(huán)op算法原理，此算法需要計(jì)算平均每跳的距離和未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，然后利用最小跳數(shù)乘以平均每跳距離，這樣能得到未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離，再利用最大似然估計(jì)法的思想可得到未知節(jié)點(diǎn)的坐標(biāo)。因此，這種算法能夠根據(jù)有限的幾個(gè)信標(biāo)節(jié)點(diǎn)，計(jì)算最小跳數(shù)和平均每跳距離來(lái)求解未知節(jié)點(diǎn)坐標(biāo)。需要的信標(biāo)節(jié)點(diǎn)較少，是一個(gè)可擴(kuò)展的算法，對(duì)于各向同性的密集網(wǎng)絡(luò)，也能夠達(dá)到適當(dāng)?shù)亩ㄎ痪取?/p>

為了驗(yàn)證以上的分析結(jié)論，下面在不同信標(biāo)節(jié)點(diǎn)密度下，來(lái)對(duì)DV－h(huán)op和質(zhì)心算法的定位性能進(jìn)行分析。仿真環(huán)境設(shè)置同上節(jié)。1 000次仿真結(jié)果求平均值，見(jiàn)圖7。

圖7 信標(biāo)節(jié)點(diǎn)密度不同時(shí)兩種算法定位性能比較

從圖7可看出，DV－h(huán)op算法定位性能受信標(biāo)節(jié)點(diǎn)密度影響不大，在信標(biāo)節(jié)點(diǎn)為12的很少情況時(shí)，也能夠?qū)?00個(gè)未知節(jié)點(diǎn)進(jìn)行較好的定位，誤差在10 m左右。而質(zhì)心算法盡管在信標(biāo)節(jié)點(diǎn)為56時(shí)，定位誤差只有5.7 m;但信標(biāo)節(jié)點(diǎn)為12和20的較少情況下，定位誤差高達(dá)16 m。

因此，從以上分析可以證實(shí)DV－h(huán)op算法更適用于煤礦井下密集型環(huán)境，信標(biāo)節(jié)點(diǎn)較少的情況。

4 結(jié)論

在無(wú)線傳感器網(wǎng)絡(luò)的定位技術(shù)研究中，最重要的性能指標(biāo)是定位誤差。而影響定位誤差的主要因素有：距離估算誤差、信標(biāo)節(jié)點(diǎn)密度、定位覆蓋率等方面。

本文主要在煤礦通道和煤礦井下平臺(tái)兩種環(huán)境下，對(duì)定位算法進(jìn)行研究。通過(guò)對(duì)以上距離估算誤差、信標(biāo)節(jié)點(diǎn)密度、定位覆蓋率這些方面進(jìn)行分析并仿真，分別驗(yàn)證了質(zhì)心算法最適于煤礦通道環(huán)境，而DV－h(huán)op算法則適用于煤礦井下密集型網(wǎng)絡(luò)的定位。可為實(shí)際應(yīng)用中，根據(jù)不同環(huán)境選擇相適合的定位技術(shù)提供一定的參考。

［1］ 馬祖長(zhǎng)，孫怡寧.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位算法［J］.計(jì)算機(jī)工程，2004，30(7)：13－14.

［2］ 孫利民，李建中.無(wú)線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，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寬帶電磁波統(tǒng)計(jì)信道建模［J］.煤炭學(xué)報(bào)，2008，33(4)：467－472.

［5］ 史 龍，王福豹.無(wú)線傳感器網(wǎng)絡(luò)自身定位算法研究［D］.西安：西北工業(yè)大學(xué)碩士論文，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.