基于RSSI的改進差分修正加權質心定位算法

余學帆， 王宏志， 韓 博， 曹學瑤， 胡黃水

(長春工業(yè)大學 計算機科學與工程學院， 吉林 長春 130012)

0 引 言

由大量低成本、低功耗的微型無線傳感器節(jié)點構成的無線傳感器網絡(Wireless Sensor Network， WSN)已經廣泛應用于環(huán)境監(jiān)測、軍事、公共安全等領域[1]。在WSN領域，節(jié)點定位技術已經成為WSN研究技術中重要的支撐技術之一[2]。

目前的定位技術根據定位方法可分為兩類：基于測距(Range-based)定位算法，通過測量節(jié)點間距離或角度，運用三邊測量或者三角測量法等，主要包括TOA、TDOA、RSSI[3-5]等，基于非測距(Range-free)定位算法，通過網絡連通度來估計未知節(jié)點到信標節(jié)點的距離或未知節(jié)點的坐標，主要包括APIT、DV-Hop以及質心算法等。文獻[6]提出一種將路徑損耗因子根據實測環(huán)境進行動態(tài)修正的三邊質心定位算法，通過修正路徑損耗因子優(yōu)化RSSI，但在三邊定位過程中只計算相交圓交點的均值，沒有考慮交點對質心的影響力;文獻[7]提出采用最小二乘曲線擬合方法估計發(fā)射功率和路徑損耗指數，實現(xiàn)優(yōu)化算法的目的;文獻[8]采用卡爾曼濾波對RSSI進行最優(yōu)化處理，在三邊質心的基礎上采用加權質心算法提高定位精度，但在求質心時，按順序取9個距離構建3個距離組合，距離組合間相差較大，增加定位誤差;文獻[9]根據接收的信號強度設定自適應基準值修正RSSI集合，減少算法的誤差與計算量;文獻[10]以常態(tài)方程代入解得坐標的誤差倒數作為權值提高定位準確性;文獻[11]采用四邊形加權定位結合最小二乘法輔助定位實現(xiàn)精確定位;文獻[12-14]在質心定位的基礎上引入粒子群算法，通過粒子群算法優(yōu)化定位結果，但增加了算法的復雜度。

文中提出一種基于RSSI的改進差分修正加權質心定位算法(Improved differential correction weighted centroid location algorithm based on RSSI， IDCL-BR)，通過預處理后的RSSI計算信標節(jié)點的距離，升序排序后，將前3個距離的質心作為參考節(jié)點，通過參考節(jié)點與信標節(jié)點的位置關系計算差分修正因子，最后對修正后的質心作加權計算未知節(jié)點坐標。從節(jié)點通信半徑、路徑損耗因子、信標節(jié)點個數等方面對算法進行仿真分析，驗證其性能。

1 算法模型

在WSN中，節(jié)點通過收發(fā)信號傳輸自身節(jié)點坐標及數據。在實際環(huán)境中，信號傳輸會受到多徑效應、反射、折射等干擾，從而造成信號衰減。文中采用自由空間傳播損耗模型和對數-常態(tài)分布模型[15]。

自由空間傳播損耗模型

P(d0)=32.4+10klg(d0)+10klg(f)，

(1)

式中:P(d0)----信號傳播距離為d0的路徑損耗;

k----路徑損耗因子，取值為[2,5];

f----信號頻率。

對數-常態(tài)分布模型

(2)

式中：P(d)----信號傳播距離為d的路徑損耗;

d0----參考距離，取d0=1 m;

Xσ----均值為0、方差為σ的高斯隨機分布函數。

未知節(jié)點接收信標節(jié)點的信號強度為

RSSI=PS+PA-P(d)，

(3)

式中：RSSI----接收信號強度;

PS----信號發(fā)射功率;

PA----天線增益。

通過式(1)～式(3)可求未知節(jié)點與信標節(jié)點的距離d。

2 質心定位算法

2.1 傳統(tǒng)質心定位算法

傳統(tǒng)質心定位算法是基于節(jié)點的連通性，無需測量節(jié)點間距離的定位算法。其原理是未知節(jié)點接收到通信范圍內多個信標節(jié)點的廣播信號，記錄信號內信標節(jié)點的ID及坐標等相關信息，并根據多邊形的質心算法來估計未知節(jié)點的坐標，即

(4)

式中：(x,y)----未知節(jié)點坐標;

(x1,y1),(x2,y2),…,(xn,yn)----未知節(jié)點通信范圍內的信標節(jié)點坐標;

n----信標節(jié)點數量。

2.2 加權質心定位算法

通過對質心定位算法研究可知，傳統(tǒng)質心定位算法實施簡單，定位精度誤差較大，沒有體現(xiàn)出信標節(jié)點對未知節(jié)點定位的影響力。由未知節(jié)點到信標節(jié)點間的距離與RSSI值的關系可知，未知節(jié)點接收到的RSSI值越大，則未知節(jié)點與信標節(jié)點距離越近，定位誤差越小；反之，RSSI值越小，未知節(jié)點與信標節(jié)點距離越遠，定位誤差越大。加權質心定位算法基本原理是通過加權因子來體現(xiàn)信標節(jié)點對未知節(jié)點定位的影響力。

(5)

式中：(x,y)----未知節(jié)點坐標;

(x1,y1),(x2,y2),…,(xn,yn)----信標節(jié)點坐標;

di----未知節(jié)點與信標節(jié)點的距離。

3 IDCL-BR算法

3.1 RSSI預處理

未知節(jié)點接收到信標節(jié)點的廣播信號，記錄信號對應的信標節(jié)點ID、坐標以及RSSI值等信息。但是廣播信號在實際傳輸過程中，受到多徑效應、反射、折射等不穩(wěn)定因素的干擾，未知節(jié)點接收的RSSI值誤差較大。因此，通過下式對每個信標節(jié)點的一組RSSI值進行預處理。

(6)

式中：RSSIi----第i個信標節(jié)點的RSSI預處理結果;

(7)

(8)

式中：m----未知節(jié)點接收到每個信標節(jié)點的RSSI值樣本數。

3.2 質心差分修正

在實際環(huán)境中，多徑效應、反射、折射等環(huán)境因素對RSSI值的影響較大，通過預處理在一定程度上解決了RSSI值的波動問題，直接采用預處理后的RSSI值通過加權質心定位的精度偏低。文中通過預處理后的RSSI值計算信標節(jié)點的測量距離與質心，并對質心差分修正以提高定位精度。

假設點O為未知節(jié)點，A1(x1,y1),A2(x2,y2),…,An(xn,yn)是未知節(jié)點通信范圍內的信標節(jié)點，由RSSI計算的距離升序排序為{d1,d2,d3,d4,…，dn},取距離{d1,d2,d3}，其對應的信標節(jié)點為A1、A2、A3，以信標節(jié)點A1、A2、A3為圓心，分別以d1、d2、d3為半徑畫圓，可得到三個圓的重合區(qū)域，如圖1所示。

圖1 三邊測量示意圖

重合區(qū)域的交點為O1、O2、O3，交點O1(xo1,yo1)的坐標由下式可求，

(9)

其中，(xo1,yo1)為交點O1的坐標，同理可求交點O2、O3的坐標(xo2,yo2)、(xo3,yo3)，以O1、O2、O3為頂點作三角形，則△O1O2O3的質心M1(xm1,ym1)為

(10)

同理，按順序逐次取{d2，d3，d4},{d3，d4，d5},…，{dk，dk+1，dn}為半徑，距離對應的信標節(jié)點為圓心畫圓，得到的質心坐標為M2(xm2,ym2)，M3(xm3,ym3)，…，Mk(xmk,ymk)，k=n-2,質心分布如圖2所示。

由上文距離排序可知，{d1，d2，d3}對應的三個信標節(jié)點離未知節(jié)點最近，則其質心M1與未知節(jié)點的誤差相對于其他質心更小，因此，將質心M1作為參考節(jié)點，通過參考節(jié)點與信標節(jié)點的位置關系計算差分修正因子。信標節(jié)點A1,A2,A3,…,An與未知節(jié)點的距離為d1,d2,d3,d4,…,dn，信標節(jié)點與質心M1距離為d11,d12,d13,d14,…,d1n，則差分修正因子為

(11)

對質心修正

(12)

圖2 差分修正示意圖

通過對質心坐標的差分修正，減小了質心與未知節(jié)點的偏差。利用質心對未知節(jié)點進行定位的過程中，距離越近的質心對未知節(jié)點坐標確定的影響力越大，可通過質心權值來體現(xiàn)。質心M1由未知節(jié)點與信標節(jié)點{A1,A2,A3}的測量距離確定，則質心M1權值為

(13)

同理，質心Mi權值為

(14)

未知節(jié)點的估計坐標(xbest,ybest)為

(15)

則未知節(jié)點的定位誤差為

(16)

式中：(xo,yo)----未知節(jié)點O的真實坐標;

(xbest,ybest)----未知節(jié)點的估計坐標。

若節(jié)點通信半徑為R，則平均定位誤差為

(17)

3.3 算法步驟

1)信標節(jié)點周期性廣播信號，信號包含其自身的ID及坐標等信息。

2)未知節(jié)點接收到多個信標節(jié)點信號，記錄信標節(jié)點的ID、坐標，并對每個信標節(jié)點的一組RSSI進行預處理。

3)未知節(jié)點通過傳播損耗模型計算信標節(jié)點的距離，對距離從小到大排序，并建立距離與信標節(jié)點的映射。

4)按順序逐次取三個距離及對應的信標節(jié)點，構成如圖1所示重合區(qū)域，計算重合區(qū)域交點以及交點的質心。

5)前三個距離的質心M1作為參考節(jié)點計算差分修正因子對其他質心進行差分修正，減少質心的位置偏差。

6)采用加權質心算法對修正后的質心估計未知節(jié)點的坐標。

4 仿真分析

為了驗證IDCL-BR算法的性能，采用Matlab實驗平臺，在50 m*50 m的區(qū)域內，隨機分布25個信標節(jié)點與5個未知節(jié)點。從節(jié)點通信半徑、路徑損耗因子、信標節(jié)點個數三個方面對IDCL-BR算法、傳統(tǒng)質心定位算法、三邊質心定位算法[6]以及加權質心定位算法[8]進行仿真實驗對比分析，為了提高算法的穩(wěn)定性，進行了30次實驗，取30次實驗的平均值作為最終結果。

隨著節(jié)點通信半徑變化的平均定位誤差仿真結果如圖3所示。

圖3 不同節(jié)點通信半徑的平均定位誤差

由圖3可見，傳統(tǒng)質心定位算法采用未知節(jié)點通信半徑內的信標節(jié)點坐標直接估算未知節(jié)點坐標，平均定位誤差較大。而三邊質心定位算法、加權質心定位算法、IDCL-BR算法根據接收信號強度對未知節(jié)點進行定位，定位精度明顯優(yōu)于傳統(tǒng)質心定位算法。當通信半徑為10 m時，IDCL-BR算法平均定位誤差高于加權質心定位算法，但隨著通信半徑的增大，未知節(jié)點通信半徑范圍內的信標節(jié)點數量增多，IDCL-BR算法的誤差低于其他三種定位算法。當通信半徑為30 m時，IDCL-BR算法的平均定位誤差只有0.118。

路徑損耗因子k的取值為2.0～5.0，由于傳統(tǒng)質心定位算法只參考信標節(jié)點的位置，路徑損耗因子變化不影響傳統(tǒng)質心定位算法的精度，所以只對比三個算法隨著路徑損耗因子變化的平均定位誤差仿真結果,如圖4所示。

圖4 不同路徑損耗因子的平均定位誤差

由圖4可見，IDCL-BR算法優(yōu)于其他兩種算法，并且當路徑損耗因子為3.0時，IDCL-BR算法的定位誤差最小。

隨著信標節(jié)點數變化的平均定位誤差仿真結果如圖5所示。

圖5 不同信標節(jié)點的平均定位誤差

由圖5可見，在參與定位的信標節(jié)點數量較少的情況下，四種定位算法的定位誤差都較大，傳統(tǒng)質心定位算法的平均定位誤差高達0.493，隨著參與定位的信標節(jié)點數的增加，定位誤差逐漸降低。IDCL-BR算法的定位誤差明顯低于其他三種算法，當信標節(jié)點數為25時，四種算法的定位誤差都達到最小，IDCL-BR算法的平均定位誤差為0.122，傳統(tǒng)質心定位算法的平均定位誤差為0.176，三邊質心定位算法的平均定位誤差為0.146，加權質心定位算法的平均定位誤差為0.134。

5 結 語

提出一種基于RSSI的改進差分修正加權質心定位算法，首先對信標節(jié)點廣播信號的接收強度進行預處理，在一定程度上減小了環(huán)境對定位結果的影響；然后采用改進的差分修正質心算法進行定位，采用逐次構建相交圓計算質心，并將第一個質心作為參考節(jié)點計算差分修正因子對質心進行修正，減少質心的偏差；最后對修正后的質心作加權處理，以距離的倒數平方和作為權值，降低偏差相對較大質心的影響力，從而提高定位精度。從節(jié)點通信半徑、路徑損耗因子、信標節(jié)點數等方面對算法進行仿真分析，IDCL-BR算法在通信半徑為30 m，路徑損耗因子為3.0，信標節(jié)點數為25時，平均定位誤差為0.122，該算法相比其他算法，定位精度與穩(wěn)定性方面更加突出。