監測煤礦的一種無線傳感器網絡節點定位算法

薛 霞，孫 勇

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

0 引言

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

1 WSNs在煤礦安全監測中的基本定位機制

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

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

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

圖1 無線傳感器網絡中煤礦監測的的錨節點和未知節點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階段，利用距離矢量交換協議，使網絡中所有節點獲得自己到錨節點的跳數(distance in hops)。錨節點向距離自己跳數為1的鄰居節點廣播自身坐標信息與跳數信息(初始跳數值為0)。接收節點僅記錄自己到每個錨節點的最小跳數，然后將跳數值加1，并轉發給鄰居節點。

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

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

錨節點將平均每跳距離廣播至網絡中，未知節點僅記錄接收到的第1個平均每跳距離，并轉發給鄰居節點。未知節點接收到平均每跳距離后，根據記錄的跳數，可以計算出到每個錨節點的距離。

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

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

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

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

2.2 改進后的定位算法

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

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

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

其中，dij=HopDisi×n ，

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

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

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

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

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

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

3 仿真實驗

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

3.1 錨節點數與平均定位誤差

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

圖2 錨節點數與平均定位誤差Fig 2 Number of anchor nodes and average localization error

3.2 錨節點數與定位覆蓋

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

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

3.3 錨節點數與通信量

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

圖4 錨節點數量與數據包總量Fig 4 Number of anchor nodes and total quantity data pack

3.4 節點數與平均定位誤差

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

圖5 節點數與平均定位誤差Fig 5 Number of nodes and average localization error

4 結論

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

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

［2］尚志軍，曾 鵬，于海斌.無線傳感器網絡節點定位問題［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］楊 維，馮錫生，程時昕，等.新一代全礦井無線信息系統理論與關鍵技術［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］王福豹，史 龍，任豐原.無線傳感器網絡中的自身定位系統和算法［J］.軟件學報，2005，16(5):857－868.

［8］彭 剛，曹元人，孫利民.無線傳感器網絡節點定位機制的研究［J］.計算機工程與應用，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.