基于改進型加權質心算法的井下人員定位

楊 鵑，韓雪松

(承德石油高等專科學校計算機與信息工程系，河北 承德 067000)

基于改進型加權質心算法的井下人員定位

楊 鵑，韓雪松

(承德石油高等專科學校計算機與信息工程系，河北 承德 067000)

節點定位技術可用于井下人員位置的確定，在日常作業監控和人員調度中起到非常重要的作用。采用無線傳感網絡的通信技術，基于傳統加權型質心算法，添加了區域判定的改進型定位算法，設計了井下人員定位系統。為驗證算法的有效性，用matlab軟件模擬仿真了算法的執行，結果表明能夠提高系統的定位精度，可用于復雜工作環境的井下監控系統中。

無線傳感網絡;節點定位;定位算法;

無線網絡節點定位技術設計主要包括兩方面的內容:錨節點的布置和定位算法的選擇。無線傳感器網絡節點自身都有接收信號強弱指示功能(RSSI)，節點間可定時發送/接收信號幀，節點的位置由唯一標識的地址表示［1-2］。無線網絡定位系統可用現有的設備發送和接收RSSI信號，無須添加額外的設備，實現起來較為容易。然而煤礦井下巷道中，礦井環境非常復雜，電磁波信號衰減嚴重，路徑損耗無法實現準確計算，不適用于采用單一的RSSI測距技術。本文在加權型質心定位算法的基礎上，改進了算法的后期計算工作，有效的提高了定位的精度，是井下節點定位中比較可行的方法。

1 定位方案

定位方案分為固定錨節點和移動錨節點兩種形式，采用位置已知的錨節點進行定位，通常錨節點的數量與定位的精度是成正比的，定位精度要求越高，需要的錨節點的數量就要求越多，本文設計的定位系統主要針對于井下人員的定位，井下工作環境非常復雜，通信干擾較多，且信號傳輸的過程中多徑衰落現象嚴重，不利于信號的遠距離傳輸。主要是由于以下原因造成的:

1)井下內部安放了多種機電設備、運輸導軌，煤和矸石隨處可見，空間內部相比于室外狹窄許多。

2)墻壁、空氣中的粉塵顆粒以及空氣中的水分都會吸收電磁波，其中濕度對電磁波損耗的影響最大，電磁損耗會隨著濕度和電磁波頻率的增加而嚴重增加［3］。巷道墻壁不平、粗糙會造成電磁波的路徑損耗，出現多徑衰落現象，電磁波傳輸損耗大。

3)巷道路徑復雜多變，彎道和岔路會造成信號的反射、衍射，造成接收信號的誤差。

4)機電設備的使用使得巷道內部噪聲較大，且電磁波信號在巷道壁的反射和折射也會造成接收信號里包含了許多的干擾信號，電磁干擾過大。

井下復雜的工作環境顯然不適宜采用移動的錨節點進行節點定位，故本文采用固定錨節點的方式進行節點定位。由于井下環境的復雜多變，考慮到耗電的問題，運算復雜的定位方法不易采用。傳統的加權型質心算法，其運算簡單，系統耗電量低，適用于井下的定位工作。

2 定位算法

2.1 加權型質心定位算法

無線網絡系統中錨節點定期向外發送信號幀，未知節點接收到該信號幀后，兩者之間可實現網絡通信。傳統的質心定位算法［4-5］是一種免測距的算法，將與未知節點實現網絡通信的錨節點的位置組成多邊形，取該多邊形的質心作為算法的位置估計，該算法的執行取決于網絡的連通性和節點間的距離大小。與未知節點通信的錨節點的數量越多，定位的精度越準確。節點間不需協調，網絡拓展易于實現。為提高定位精度，往往要增加系統錨節點的個數，減少錨節點間的距離，這會造成系統成本的大幅度的增加。并且質心定位算法適用于網絡節點分布均勻的環境下，這樣計算的定位誤差較小，否則定位誤差會大大增加。為了解決這一問題，加權型的質心定位算法應運而生，該算法將節點間的距離的倒數作為計算的權值添加到計算公式中，將節點間距離的影響體現到具體的計算中，提高了算法的定位精度。錨節點距離未知節點的距離越近，其對未知節點的坐標的影響越大，因而將節點間的距離值的倒數作為質心定位算法的偏移權值。加權的質心定位算法的計算公式如(1)。

式中，xi和yi作為錨節點的di坐標，為錨節點和未知節點的距離值，x、y作為質心定位的估計坐標點。

2.2 RSSI測距技術

質心型定位算法中的距離值需要采用RSSI測距技術來確定。RSSI測距技術的核心思想是錨節點向外發射已知信號強度的信號，未知節點接收該信號，根據接收到的信號強度和系統環境的路徑損耗來計算未知節點的距離。各未知節點接收錨節點信號時的信號強度如公式(2)。

其中路徑損耗是與無線網絡的工作環境相關的，現有的路徑損耗的方法有經驗法和曲線擬合法。經驗法需要對未知環境的估計足夠準確，事實上往往偏差很大。曲線擬合法往往要對實際環境進行測試，再經過計算獲得實際的路徑損耗，計算量很大。

考慮到井下環境的復雜性，本系統的RSSI與距離的公式計算采用遮蔽型，如公式(3)。

式中:λ—路徑損耗系數，一般取2～5;ξ—隨機數，符合高斯分布，平均值為0，其標準差一般取4～10;d0—參考距離;d—估計距離;Pr(d0)—參考距離的接收信號強度;Pr(d)—估計距離的接收信號強度;

2.3 定位算法的設計

在加權質心算法的基礎上，很多文獻根據應用的需求提出了不同的改進方法。文獻［6］提出了一種基于RSSI修正的算法，該算法在首先利用RSSI算法取得未知節點的估計坐標后，重新計算估計坐標到錨節點的距離值，根據再將測距技術獲得的未知節點與錨節點之間的距離值相比較，校正節點位置。對通信半徑內的所有錨節點的估計坐標進行修正，再將修正后的坐標采用質心算法進行計算。文獻［1］提出了選用錨節點定位最近的四個錨節點進行質心定位算法的定位，該方法錨節點密度越大，定位精度越高。文獻［7］提出了多質心定位算法，該算法首先將網絡當中的信標信號得到的廣播信息值排序R-set={RSSI1，RSSI2，…RSSIn}轉化成距離排序信號集合D-set，求出距離值與最小的距離值的差值集合△d-set，求取△d-set集合的平均值，將錨節點大于平均值的節點集合距離集合中取距離值相差最小的三個節點，用傳統的質心心算法計算出該錨節點的三角形坐標。將新產生的錨節點與距離值小于平均值的錨節點組合成多邊形，再用加權質心算法計算出新的未知節點的坐標。該算法的使用要求錨節點的數量較多，增加了系統的成本。

根據現有文獻的技術，本文考慮到井下環境的復雜程度，將加權型質心算法的進行采用區域改進型的后期處理，求取定位最小誤差，找到最優的定位點。區域改進型的加權質心定位算法具體的過程如下所示。

1)錨節點定期地向周圍發送信號，包括信號強度和ID編號。

2)未知節點接收周圍錨節點發送的信號，確定周圍與之具有網絡連通的錨節點以及其發送到未知節點的RSSI信號值，建立未知節點與錨節點的RSSI值的組合R-set:(R1，R1，…，Rm)，以及按照RSSI組合的順序建立的與未知節點連通的錨節點的序號集合M-set:(m1，m2，…，mm)以及錨節點的位置集合 X-set:(x1，x2，…，xm)，Y-set:(y1，y2，…，ym)。將 R-set、X-set和 Y-set代入加權型質心算法的計算公式，求取未知節點的估計點坐標O(x，y)。

3)建立未知節點的估計區域，以O點為中心，0.5ξR為坐標的邊界，如圖1所示。本系統默認的模擬仿真運算中，將0.5ξR設定為1。

4)本定位算法的設計中定位誤差計算如公式(4)。

式中di代表未知節點與錨節點間的實際距離，d'i代表估計坐標與錨節點間的距離值;仿真計算時，d'i由節點間的距離值表示，di根據RSSI信號發送和接收的公式，計算求得。分別求取O點以及估計區域頂點與錨節點序號集合的錨節點的定位誤差，分別由ΔO、Δ1、Δ2、Δ3、Δ4表示。如果ΔO＜=min(Δ1，Δ2，Δ3，Δ4)，則認為該估計坐標為最小誤差的定位點，O點坐標為最終的估計坐標值，結束此次判定。如果 ΔO ＞min(Δ1，Δ2，Δ3，Δ4)，則判定 O 點為非最佳定位點，選擇 Δ1，Δ2，Δ3，Δ4 的最小點作為新的估計坐標點O，按照圖1重新進行估計區域的確定，重復執行上述的過程。根據系統誤差的情況，可設定重復執行的循環閾值，超過閾值大小，則退出循環執行的操作，將當前的估計坐標點作為定位坐標的結果，本文設定循環閾值為5。

3 仿真設計

3.1 仿真環境的設置

為了驗證算法的有效性，采用MATLAB軟件對算法進行仿真。假設將網絡設置于100 m×10 m的區域內，該區域的左下角坐標(0，0)，區域內采用無線載波信號頻率為2.4 GHz，節點的通信半徑理論上設定為18 m，實際中由于路徑損耗的原因，大約12米左右。為了驗證算法的有效性，實際作業中的電磁干擾、電磁波反射和折射、濕度的干擾以及氣候的影響由均值為0，標準差為5的高斯分布的隨機噪聲表示。錨節點的布局如圖2所示。

3.2 定位精度的比較

1)不同定位算法的定位精度的比較。該精度的比較的仿真環境采用圖2的布局方式，相同橫坐標的錨節點間的距離相差為10，不同橫坐標的錨節點間橫坐標相差為5。隨機選定未知節點的坐標，固定橫坐標的大小，調整縱坐標的值比較不同的定位算法在不同的坐標下，定位誤差的變換情況。比較的結果如圖3所示。區域改進型的定位算法相比于加權型定位算法在定位誤差的準確度方面有了較大的提高，并且從曲線變換情況看，加權型質心算法的定位誤差與未知節點的未知有很大的關系，兩側誤差值較大，已經達到了18%左右，而在中心位置的誤差卻較低，大約在3% ～8%左右。區域改進型的算法，從曲線的變換情況可以看出，定位誤差最大大約有9%，最小可達到3%左右，定位精度的提高是比較明顯的。兩種質心算法的定位誤差有一部分曲線是重合的，這說明在此坐標點上首次估計的未知坐標點就是最小誤差點，所以定位誤差大小是一致的。

2)定位距離對定位算法的影響。采用區域改進型的質心定位算法，調整錨節點間的定位距離，觀察定位誤差的變化情況。以錨節點間的橫坐標的大小表示錨節點的距離，比較的結果如如圖4所示。節點距離的調整對于定位誤差的影響并沒有明顯的體現出來。本系統設定的實際通信半徑大小為12，在任意的一個未知節點的定位過程中，與之通信的錨節點的個數至少為3個，這就保證了算法的準確程度，所以距離為5和距離為10的定位結果并沒有較大的出入。如果將錨節點間的距離設定為15，則定位誤差會大大增加，這是由于與之通信的錨節點的個數有時會少于3個。故在本算法的定位設計中，在保證與未知節點通信的錨節點個數不低于3個的情況下，選擇最大的距離值布局錨節點的位置，提高系統的性價比。

4 總結

本文在加權型質心算法的基礎上，改進了算法的處理過程，添加了區域估計，比較最小誤差，尋求最佳的定位估計點。由定位的仿真結果圖可以看出定位誤差大大的減少了，適用于環境復雜的井下作業。

［1］于慧霞.WSN中基于RSSI的加權質心定位算法的改進［J］.電子測試，2012(1):28-32.

［2］郭秀才，滕以金，竇美玲.井下人員定位跟蹤檢測系統［J］.兵工自動化，2009，28(4):58-63.

［3］蔡翠翠.礦井無線通信的抗多徑關鍵技術研究［D］.合肥:安徽理工大學，2012.

［4］陳茂聰，田華.移動無線傳感器網絡定位算法研究［J］.通信技術，2011，44(6):70-75.

［5］R.Behnke，D.＂fimmermann，“AWCL:Adaptive Weighted Centroid Localization as anefficient improvement of coarse grained localization，”5th Workshop on PositioningNavigation and Commumcation，PP.243-250，March 2008.

［6］王偉，陳岱，周勇.基于測距修正和位置修正的RSSI定位算法［J］.計算機工程與設計，2011，32(2):409-415.

［7］劉京.WSN中質心定位算法和基于移動錨節點的定位算法研究［D］.鄭州:鄭州大學，2008.

Underground Personnel Positioning Based on Improved Weighted Centroid Algorithm

YANG Juan，HAN Xue-song

(Department of Computer and Information Engineering，Chengde Petroleum College，Chengde 067000，Hebei，China)

Node location technology can be used to determine the mine personnel position，which plays a very important role in job monitoring and scheduling.This article adopts the communication technology of wireless sensor network.Based on the traditional weighted centroid algorithm，the improved localization algorithm is added to determine area.Mine personnel positioning system is designed in this article.To verify the validity of the algorithm，the paper uses matlab software to simulate the process，the compared result shows that the algorithm can improve the positioning accuracy of the system，and we can use it in the complex working environment of mine monitoring system.

wireless sensor network;node localization;positioning algorithm

TP216

A

1008-9446(2014)04-0057-04

2013-12-25

楊鵑(1979-)，女，黑龍江雙鴨山人，承德石油高等專科學校計算機與信息工程系講師，控制理論與控制工程碩士，研究方向為信息融合與無線網絡。