監(jiān)測煤礦的一種無線傳感器網(wǎng)絡(luò)節(jié)點定位算法

薛 霞，孫 勇

(1.西北大學 信息學院，陜西 西安710127;2.北京理工大學電子安全工程系，北京100081)

0 引言

我國煤礦安全技術(shù)與裝備水平低，事故隱患多。由于無線傳感器網(wǎng)絡(luò)(WSNs)可應(yīng)用于布線和電源供給困難的區(qū)域、人員不能到達的區(qū)域和一些臨時場合［1～4］。因此，本文將WSNs應(yīng)用于煤礦安全監(jiān)測，這將有效地提高了煤礦安全生產(chǎn)的監(jiān)測水平，并且減少了事故隱患［5］。在煤礦安全監(jiān)測中，需要知道采集的數(shù)據(jù)信息所對應(yīng)的具體區(qū)域位置，如對瓦斯突出，只有快速確認瓦斯突出的具體地點，才能及時采取相應(yīng)的措施，防止事故發(fā)生。因此，研究節(jié)點定位是WSNs的一項重要支撐技術(shù)。

1 WSNs在煤礦安全監(jiān)測中的基本定位機制

節(jié)點定位是依靠傳感器網(wǎng)絡(luò)中少量錨節(jié)點的位置信息確定監(jiān)測區(qū)域中其他未知節(jié)點的位置坐標，在傳感器節(jié)點間建立起一定的空間關(guān)系。根據(jù)節(jié)點是否已知自身的位置，把傳感器節(jié)點分為錨節(jié)點和未知節(jié)點。在WSNs中，錨節(jié)點(anchor node)是已知自身精確的位置，且能夠協(xié)助未知節(jié)點進行定位;未知節(jié)點(unknown node)是需要進行定位的節(jié)點。在一個節(jié)點的通信半徑內(nèi)，直接通信的節(jié)點稱為鄰居節(jié)點。一個節(jié)點擁有的鄰居節(jié)點數(shù)量稱為網(wǎng)絡(luò)連通度。

根據(jù)定位機制的不同，將WSNs自身定位算法分為兩類:基于測距(range-based)的定位方法和無需測距(rangefree)的定位方法［6］。前者需要測量未知節(jié)點與錨節(jié)點之間的距離或者角度信息，然后使用三邊測量法、三角測量法或極大似然估計法計算未知節(jié)點的位置。后者無需距離或角度信息，僅根據(jù)網(wǎng)絡(luò)的連通性、跳段估算距離等信息來確定節(jié)點的位置，具有低功耗、低成本的優(yōu)勢，且不需硬件支持［7，8］。NiculescuD等人提出的DV-Hop節(jié)點定位算法［9，10］不需要提供額外的硬件，節(jié)點間的通信量低。在煤礦中，WSNs節(jié)點通常按需隨機分布，因此，節(jié)點的分布不均勻，且不能保證節(jié)點的密度。故在煤礦安全監(jiān)測中，采用DV-Hop節(jié)點定位算法是一個可選的方案。本文通過對DV-Hop算法的進一步改進，使得改進后的DV-Hop節(jié)點定位算法成為煤礦安全監(jiān)測的一個理想方案。

圖1為WSNs的煤礦安全監(jiān)測區(qū)域，陰影節(jié)點表示未知節(jié)點，空心節(jié)點表示錨節(jié)點，錨節(jié)點個數(shù)至少必須是3。未知節(jié)點根據(jù)附近的錨節(jié)點或已定位的未知節(jié)點之間的通信，使用某種定位算法計算自己的坐標位置。

圖1 無線傳感器網(wǎng)絡(luò)中煤礦監(jiān)測的的錨節(jié)點和未知節(jié)點Fig 1 Anchor nodes and unknown nodes of WSNs for coal mine safety monitoring

2 DV-Hop算法及其改進

2.1 基本的定位算法

DV-Hop算法，是美國路特葛斯大學(Rutgers University)的Niculescu D等人利用距離矢量路由(distance vector routing)和GPS定位原理，提出的其中一種分布式定位算法，它由3個階段組成。

第1階段，利用距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點獲得自己到錨節(jié)點的跳數(shù)(distance in hops)。錨節(jié)點向距離自己跳數(shù)為1的鄰居節(jié)點廣播自身坐標信息與跳數(shù)信息(初始跳數(shù)值為0)。接收節(jié)點僅記錄自己到每個錨節(jié)點的最小跳數(shù)，然后將跳數(shù)值加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點。

第2階段，獲得了其他錨節(jié)點坐標信息和它們之間的跳距信息，錨節(jié)點計算平均每跳距離，然后，將這個跳距矯正值(correction)廣播到網(wǎng)絡(luò)中。錨節(jié)點i的平均每跳距離為

其中，錨節(jié)點 i，j的坐標分別為(xi，yi)，(xj，yj)，hij為錨節(jié)點i與j(i≠j)之間的跳數(shù)。

錨節(jié)點將平均每跳距離廣播至網(wǎng)絡(luò)中，未知節(jié)點僅記錄接收到的第1個平均每跳距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點。未知節(jié)點接收到平均每跳距離后，根據(jù)記錄的跳數(shù)，可以計算出到每個錨節(jié)點的距離。

第3階段，當未知節(jié)點獲得3個或3個以上錨節(jié)點的距離時，利用三邊測量法或極大似然估計法計算自身坐標位置。

圖1所示的情形推廣到了更一般的情況，極大似然估計法是三邊測量法的推廣。假設(shè)有n個錨節(jié)點，其位置坐標為(xi，yi)(i=1，2，...，n)，未知節(jié)點坐標為(x，y)，要求錨節(jié)點數(shù)n≥3;di為第i個錨節(jié)點與未知節(jié)點間的距離，根據(jù)平面內(nèi)兩點間的歐式距離公式，得到以下方程組為

在式(2)中，將前n－1個等式分別減去第n個等式，整理成Ax=b的線性方程組形式。其中

使用標準最小二乘法，求得未知節(jié)點坐標x的估計^x。

2.2 改進后的定位算法

DV-Hop算法用錨節(jié)點之間的平均每跳距離代替未知節(jié)點到錨節(jié)點的平均每跳距離，未知節(jié)點和錨節(jié)點之間的距離用每跳跳距×跳數(shù)表示。對未知節(jié)點進行定位時，只考慮了離未知節(jié)點最近的一個錨節(jié)點估計的平均每跳距離，然而單個錨節(jié)點估計的平均每跳距離值無法準確地反映整個網(wǎng)絡(luò)的實際平均每跳距離。為了減小誤差、進一步提高定位精度，對上面算法進行了改進。改進后的定位算法由以下4個步驟組成:

1)通過路由協(xié)議，每個錨節(jié)點采用廣播方式，將其錨節(jié)點的位置、跳數(shù)以及到錨節(jié)點的每跳距離和廣播給其他節(jié)點。當某個錨節(jié)點接收到其他錨節(jié)點的信息時，便可根據(jù)兩者的位置計算出兩者之間的實際距離。根據(jù)實際距離與每跳距離和的差值，計算錨節(jié)點i，j之間的總距離誤差校正值Eij。

設(shè)錨節(jié)點i的平均每跳距離為HopDisi，錨節(jié)點i，j(i≠j)之間總共有n跳，dij表示錨節(jié)點 i，j間的每跳距離和，Dij表示錨節(jié)點i，j間的實際距離。計算總距離誤差校正值Eij

其中，dij=HopDisi×n ，

2)各個未知節(jié)點到錨節(jié)點的距離不同，距離誤差也不同。因此，應(yīng)該采用不同的誤差校正值進行計算。設(shè)錨節(jié)點i，j間的跳數(shù)為n，計算i到j(luò)的平均每跳誤差校正值eij

各個錨節(jié)點在網(wǎng)絡(luò)中廣播自己到其他錨節(jié)點的跳數(shù)和距離誤差校正值。因此，錨節(jié)點獲得了其他所有錨節(jié)點的總距離誤差校正值和平均每跳誤差校正值。每個接收到此數(shù)據(jù)的節(jié)點將此信息記錄到一張表中，然后繼續(xù)向其鄰居廣播(重復(fù)的數(shù)據(jù)包丟棄)。經(jīng)過了總距離誤差校正和平均每跳誤差校正后，意味著找到了一條到達錨節(jié)點的更短路徑。

3)經(jīng)過步驟1和步驟2的廣播，未知節(jié)點得到了距離自己最近的3個錨節(jié)點的距離誤差校正值，利用這些校正值，獲得自己到錨節(jié)點的距離和計算自己到各個錨節(jié)點的實際距離。

設(shè)未知節(jié)點u在錨節(jié)點i與j之間，N表示未知節(jié)點u到錨節(jié)點i的跳數(shù)，未知節(jié)點u到錨節(jié)點i的每跳距離和用HopDisi×N表示，eij表示i到j(luò)的平均每跳誤差校正值(公式(4))。計算未知節(jié)點u到錨節(jié)點i的實際距離Dui為

4)利用三邊測量法計算自己的位置坐標。

通過以上的改進算法，鄰居節(jié)點只接收節(jié)點轉(zhuǎn)發(fā)的一個具有最小跳數(shù)的信息，同時丟棄其他節(jié)點的轉(zhuǎn)發(fā)信息。因此，丟棄的這些節(jié)點無法進行定位計算，從而減少了平均定位誤差。

3 仿真實驗

利用Matlab7.0對DV-Hop算法和本文算法進行了仿真實驗。假設(shè)某一煤礦安全監(jiān)測局部無線傳感器網(wǎng)絡(luò)區(qū)域為200m×200m的正方形區(qū)域，隨機分布400個節(jié)點，其中，錨節(jié)點數(shù)為30，節(jié)點通信距離為15 m。每種性能的仿真都隨機運行20次，然后取其平均值。

3.1 錨節(jié)點數(shù)與平均定位誤差

在仿真區(qū)域內(nèi)隨機分布了400個節(jié)點，如圖2所示，錨節(jié)點數(shù)量較小時，誤差較大;錨節(jié)點數(shù)增加后，定位誤差快速降低。仿真結(jié)果顯示，在錨節(jié)點數(shù)量較少的情況下，平均定位誤差大約降低了30%。改進算法的平均定位誤差小于DV-Hop算法，因為改進算法隨著錨節(jié)點數(shù)的增加，節(jié)點的距離誤差得到了校正。

圖2 錨節(jié)點數(shù)與平均定位誤差Fig 2 Number of anchor nodes and average localization error

3.2 錨節(jié)點數(shù)與定位覆蓋

DV-Hop定位算法和改進算法的覆蓋率如圖3所示。隨著錨節(jié)點數(shù)的增加，改進算法的定位覆蓋范圍快速達到了100%。在DV-Hop算法中，當錨節(jié)點數(shù)較少時，有的節(jié)點由于不能找到至少3個錨節(jié)點，故不能用三邊測量法計算坐標位置，因此，覆蓋率只有63%左右。從圖中可以看出:改進算法在定位覆蓋率方面明顯高于DV-Hop算法。

圖3 定位覆蓋率Fig 3 Localization coverage rate

3.3 錨節(jié)點數(shù)與通信量

在仿真區(qū)域內(nèi)隨機分布了400個節(jié)點，如圖4所示，隨著錨節(jié)點數(shù)的增加，2種算法的數(shù)據(jù)包總量都增大，但改進算法的增長低于DV-Hop算法，是因為不可定位節(jié)點沒有參與計算，從而大大降低了節(jié)點之間的通信開銷。

圖4 錨節(jié)點數(shù)量與數(shù)據(jù)包總量Fig 4 Number of anchor nodes and total quantity data pack

3.4 節(jié)點數(shù)與平均定位誤差

在仿真區(qū)域內(nèi)，隨機分布了1000個節(jié)點，取30個為錨節(jié)點。在不同節(jié)點數(shù)的情況下，觀察DV-Hop算法和改進算法的平均定位誤差。如圖5所示:本文算法的平均定位誤差小于DV-Hop算法。在節(jié)點數(shù)量為1000的情況下，本文算法的定位誤差大約是DV-Hop算法的55%左右。平均定位誤差降低，是因為本文算法中的不可定位節(jié)點不會參與定位計算。

圖5 節(jié)點數(shù)與平均定位誤差Fig 5 Number of nodes and average localization error

4 結(jié)論

本文介紹了一種改進后的WSNs節(jié)點定位算法。實際距離用節(jié)點間的跳數(shù)×平均每跳距離代替，通過引入距離誤差校正值，并且考慮了跳數(shù)的影響，同時在路徑上實行距離校正，實現(xiàn)了節(jié)點的精確定位。改進后的DV-Hop算法不僅降低了平均定位誤差，同時也提高了定位覆蓋率。仿真實驗證明了該方法的有效性。這種新的WSNs節(jié)點定位方法解決了類似煤礦這種場景的定位需求，為煤礦的瓦斯突出問題提出了一種新的理想解決方案。

［1］Akyildiz IF，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks［J］.IEEE Communications Magazine，2002，40(8):102－114.

［2］尚志軍，曾 鵬，于海斌.無線傳感器網(wǎng)絡(luò)節(jié)點定位問題［J］.計算機科學，2004，31(10):35－38.

［3］Langendoen K，Reijers N.Distributed localization in wireless sensor networks:A quantitative comparison［J］.Computer Networks，2003，43(4):499－518.

［4］Sohrabi K，Gao J，Ailawadhi V，et al.Protocols for self-organization of a wireless sensor network［J］.IEEE Personal Communications，2000，7(5):16－27.

［5］楊 維，馮錫生，程時昕，等.新一代全礦井無線信息系統(tǒng)理論與關(guān)鍵技術(shù)［J］.煤炭學報，2004，29(4):506－509.

［6］He T，Huang C D，Blum B M.Range-free localization schemes in large scale sensor networks［C］∥Proceedings of the 9th Annual International Conference on Mobile Computing and Networking.San Diego:ACM Press，2003:81－95.

［7］王福豹，史 龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學報，2005，16(5):857－868.

［8］彭 剛，曹元人，孫利民.無線傳感器網(wǎng)絡(luò)節(jié)點定位機制的研究［J］.計算機工程與應(yīng)用，2004，40(35):27－29.

［9］Niculescu D，Nath B.Ad Hoc positioning systems［J］.IEEE Communications Society，2001，5:2926－2931.

［10］Niculescu D，Nath B.DV-based positioning in Ad Hoc networks［J］.Journal of Telecommunication Systems，2003，22(1/4):267－280.