權重和誤差雙修正的質心定位算法

(桂林航天工業學院自動化系，廣西 桂林 541004)

0 引言

節點定位算法主要基于測距和非測距[1-3]。基于測距是通過測量節點間的距離或角度，使用三邊(角)測量或最大似然估計法[4]計算。例如：接收信號強度法[5]、信號傳輸時間(差)法、信號角度法等。基于非測距是依據網絡連通性等信息計算，例如：質心算法[6]、APIT算法[7]、DV-hop算法[8]等。

文獻[9]將離未知節點最近的信標節點作為修正節點；文獻[10]提出優選信標節點進行加權質心；文獻[11]根據信標節點與未知節點的距離關系，調整加權系數；文獻[12]對信標節點與未知節點的接收信號強度指示(received signal strength indication,RSSI)測距進行加權平均。以上方法都是以RSSI測距為基礎，增加質心算法和距離權重，測距誤差和距離權重直接影響定位精度。本文提出一種對距離權重和測距誤差進行雙修正的質心定位算法，提高定位性能。

1 算法模型

1.1 加權質心算法

利用權重因子體現各信標節點對質心位置的影響程度，反映它們之間的內在關系。

信標節點與未知節點的質心關系如圖1所示。圖1中，B1(XB1,YB1)、B2(XB2,YB2)、B3(XB3,YB3)分別為三個信標節點，D為未知節點。

圖1 加權質心示意圖

(1)

(2)

(3)

(4)

(5)

1.2 距離權重修正模型

利用加權質心定位算法，可以獲得未知節點的一個位置預測，但是這種預測的位置僅反映質心三角形中未知節點和兩個信標節點總的距離關系。實際上，兩個信標節點與未知節點的實際距離不可能是完全一致的，且對未知節點的權重影響也該是有差異的。離未知節點越近的信標節點獲得的距離權重越大，離未知節點越遠的信標節點獲得的距離權重越小。

為了完善距離權重差異化的作用，提出的改進算法首先修正距離權重，增加權重修正系數K1、K2、K3。

修正后，信標節點與未知節點的距離和權重修正系數成反比。

坐標權重修正式如下：

(6)

(7)

綜合x，y坐標，可得距離權重修正式：

(8)

1.3 測距誤差修正模型

達到距離權重修正模型的修正效果，必須要有預測測距的基礎，而實際應用中由于環境影響和硬件限制的原因，RSSI測距不能保證足夠的精確，測距誤差較大。針對這一問題，改進算法從修正信標測距入手，減小RSSI測距誤差影響。

(9)

誤差因子αDBi的取值直接影響測距誤差。如果能找到離未知節點足夠近的信標節點作為修正節點，得到修正節點與其他任意一個信標節點的真實距離和RSSI測距，那么就可以得到關于這個修正節點的誤差因子。由于未知節點和這個修正節點位置很接近，測距誤差影響幾乎相同，所以可以利用修正節點的誤差因子代替未知節點的誤差因子。

修正節點誤差修正示意圖如圖2所示。

圖2 修正節點誤差修正示意圖

取離未知節點最近的信標節點作為修正節點。從圖2可以發現，距離未知節點D最近的信標節點為B0，則將其作為修正節點。

由于B0和B1都是信標節點，可以根據實際坐標精確得到兩者之間的實際距離dB1B0。

(10)

(11)

αB1B0替代未知節點D與信標節點B1之間的誤差因子αDB1：

αB1B0=αDB1

(12)

得到未知節點D與信標節點B1修正測距值：

(13)

同理可得另外兩個誤差因子αB2B0、αB3B0。

將誤差因子αB1B0、αB2B0、αB3B0代入距離權重修正式，得到測距誤差修正公式：

在同等測距誤差影響下，誤差因子αBiB0的修正可以有效修正測距誤差的影響。

在實際環境中，如果未知節點與某一個(或幾個)信標節點的通信范圍超出了修正節點與信標節點的通信范圍，那么就找不到對應的修正誤差因子。這種情況下，就需要尋找次修正節點來保證未知節點與信標節點、修正節點與信標節點的通信范圍是有交集的。如果仍然找不到交集，則取消修正。兩次修正可以降低未修正測距誤差的概率。同理，如果對精度要求嚴格，可以進行多次修正節點嘗試。

2 算法步驟

質心定位算法的具體步驟如下。

① 信標節點周期性發送節點ID、自身位置信息P。

② 未知節點統計可通信范圍內的信標節點集合ωΒ={Β1,Β2，…,Βn}，并選取同一個信標節點的多次RSSI均值作為當前信標節點與自身通信的RSSI值。

④ 未知節點選擇集合ωΒ中RSSI值最大的三個信標節點構成質心三角形，結合距離權重系數得到權重修正預測位置。

⑥ 將修正誤差因子代入測距誤差修正式，得到基于距離權重和測距誤差雙修正的質心算法，最終得到較為精確的未知節點位置。

3 仿真結果與分析

利用Matlab仿真試驗平臺比較改進算法與傳統加權質心算法的性能。節點隨機分布在100 m×100 m的區域內，未知節點的位置隨機產生，信標節點均勻隨機分布。

從以下三個方面來衡量改進算法的效果。

① 以預測位置和實際位置的差異來衡量，距離權重和測距誤差雙修正質心算法的節點位置仿真結果如圖3所示，加權質心算法節點位置仿真結果如圖4所示。

從圖3和圖4可以看出，距離權重和測距誤差雙修正質心算法得到的未知節點的預測位置與實際位置之間的距離明顯小于加權質心定位算法。

圖3 雙修正質心算法仿真圖

圖4 加權質心算法仿真圖

② 從權重修正系數對平均定位誤差的影響程度來衡量。定位誤差指的是通過定位計算得到的未知節點的估計位置與實際位置的偏差。這種偏差可以用兩者之間的歐氏距離除以節點的通信半徑來衡量，最后，利用平均定位誤差來衡量定位算法的優劣。

平均定位誤差與修正系數關系圖如圖5所示。

圖5 平均定位誤差與修正系數關系圖

計算節點定位誤差為：

(14)

對N個未知節點的定位誤差求平均，得到平均定位誤差：

(15)

為了簡化模型仿真，這里假設權重修正系數K1=K2=K3=K，平均定位誤差隨著權重修正系數的改變而不斷變化。在K=5附近，達到最小平均定位誤差。

③ 為了方便衡量測距誤差對定位誤差的影響，取測距誤差范圍在REi∈[0,+30%]變化。如果將待測區域劃分成若干個范圍比較小的子網絡(例如：5 m×5 m)，那么可以認為子網絡內的測距誤差因子是不變的。

測距誤差與定位誤差關系圖如圖6所示。

圖6 測距誤差與定位誤差關系圖

從圖6可以看出，隨著測距誤差的增大，未知節點的平均定位誤差也隨之增加，這是因為測距誤差的增加使得距離權重影響誤差加大，造成定位精度下降。采用距離權重和測距誤差雙修正質心算法可以減少測距誤差帶來的影響。測距誤差越大，其誤差修正的作用就越強。

4 結束語

本文在加權質心定位算法的基礎上，利用距離模型對距離權重進行調節，為距離權重匹配修正系數。利用修正節點與信標節點的RSSI測距誤差因子，校正未知節點與信標節點的RSSI測距誤差因子，強化了信標節點與未知節點間距的權重影響，減少了RSSI測距帶來的誤差影響，提高了未知節點的定位精度。

質心定位算法不需要節點之間進行復雜的協調過程，算法復雜度也只比質心算法略有增加，具有良好的可擴展性，可以滿足傳感器網絡中對位置精度不太苛刻的應用。

[1] Jonathan B,Adam M,Adam M.Localization in sensor networks[M].Handbook of Sensor Networks:Algorithms and Architectures.USA:Wiley-Interscience,2005:277-310.

[2] Rampatzis A,Lygeros J,Manesis S.A survey of applications of wireless sensors and wireless sensor networks[C]∥Proceedings of the 2005 IEEE International Symposium on,Mediterrean Conference on Control and Automation,2005:719-724.

[3] Akyildiz I,Su W,Sankarasvbramaniam Y.A survey on sensor networks[J].IEEE Communications Magazine,2011,40(8):102-l14.

[4] 溫立.無線傳感器網絡定位技術研究[D].上海：復旦大學,2008:34-37.

[5] Luthy K A,Grant D,henderson T C.Leveraging RSSI for robotic reapair of disconnected wireless sensor networks[C]//2007 IEEE International Conference on Robotics and Automation.Rome,Italy,2007:10-14.

[6] Nirupama B,John H,Deborah E.GPS less low cost out door localization for very small devices[J].IEEE Personal Communications,2000,7(5):28-34.

[7] Niculescu D,Nath B.DV based positioning in Ad Hoc networks[J].Journal of Telecommunication Systems,2003,22(4):267-280.

[8] He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]//ACM International Conference on Mobile Computing and Networking(MobiCom).San Diego,California,USA:ACM Press,2003:81-95.

[9] 程偉,史浩山,王慶文.基于差分修正的傳感器網絡加權質心定位算法[J].系統仿真學報,2012,24(2)：389-393.

[10]趙昭,陳小惠.無線傳感器網絡中基于RSSI的改進定位算法[J].傳感技術學報，2009,22(3):391-394.

[11]胡詠梅,張歡.一種改進的無線傳感器網絡質心定位算法[J].計算機工程與科學,2012,34(2)：45-49.

[12]Blumenthal J,Grossmann R,Golatowski F,et al.Weighted centroid localization in Zigbee-based sensor networks[C]//IEEE International Symposium on Intelligent Signal Processing,WISP 2007.USA:IEEE,2007:1-6.