余學(xué)帆， 王宏志， 韓 博， 曹學(xué)瑤， 胡黃水

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春 130012)

0 引 言

由大量低成本、低功耗的微型無(wú)線(xiàn)傳感器節(jié)點(diǎn)構(gòu)成的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(Wireless Sensor Network， WSN)已經(jīng)廣泛應(yīng)用于環(huán)境監(jiān)測(cè)、軍事、公共安全等領(lǐng)域[1]。在WSN領(lǐng)域，節(jié)點(diǎn)定位技術(shù)已經(jīng)成為WSN研究技術(shù)中重要的支撐技術(shù)之一[2]。

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

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

1 算法模型

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

自由空間傳播損耗模型

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

(1)

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

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

f----信號(hào)頻率。

對(duì)數(shù)-常態(tài)分布模型

(2)

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

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

Xσ----均值為0、方差為σ的高斯隨機(jī)分布函數(shù)。

未知節(jié)點(diǎn)接收信標(biāo)節(jié)點(diǎn)的信號(hào)強(qiáng)度為

RSSI=PS+PA-P(d)，

(3)

式中：RSSI----接收信號(hào)強(qiáng)度;

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

PA----天線(xiàn)增益。

通過(guò)式(1)～式(3)可求未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離d。

2 質(zhì)心定位算法

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

傳統(tǒng)質(zhì)心定位算法是基于節(jié)點(diǎn)的連通性，無(wú)需測(cè)量節(jié)點(diǎn)間距離的定位算法。其原理是未知節(jié)點(diǎn)接收到通信范圍內(nèi)多個(gè)信標(biāo)節(jié)點(diǎn)的廣播信號(hào)，記錄信號(hào)內(nèi)信標(biāo)節(jié)點(diǎn)的ID及坐標(biāo)等相關(guān)信息，并根據(jù)多邊形的質(zhì)心算法來(lái)估計(jì)未知節(jié)點(diǎn)的坐標(biāo)，即

(4)

式中：(x,y)----未知節(jié)點(diǎn)坐標(biāo);

(x1,y1),(x2,y2),…,(xn,yn)----未知節(jié)點(diǎn)通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)坐標(biāo);

n----信標(biāo)節(jié)點(diǎn)數(shù)量。

2.2 加權(quán)質(zhì)心定位算法

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

(5)

式中：(x,y)----未知節(jié)點(diǎn)坐標(biāo);

(x1,y1),(x2,y2),…,(xn,yn)----信標(biāo)節(jié)點(diǎn)坐標(biāo);

di----未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離。

3 IDCL-BR算法

3.1 RSSI預(yù)處理

未知節(jié)點(diǎn)接收到信標(biāo)節(jié)點(diǎn)的廣播信號(hào)，記錄信號(hào)對(duì)應(yīng)的信標(biāo)節(jié)點(diǎn)ID、坐標(biāo)以及RSSI值等信息。但是廣播信號(hào)在實(shí)際傳輸過(guò)程中，受到多徑效應(yīng)、反射、折射等不穩(wěn)定因素的干擾，未知節(jié)點(diǎn)接收的RSSI值誤差較大。因此，通過(guò)下式對(duì)每個(gè)信標(biāo)節(jié)點(diǎn)的一組RSSI值進(jìn)行預(yù)處理。

(6)

式中：RSSIi----第i個(gè)信標(biāo)節(jié)點(diǎn)的RSSI預(yù)處理結(jié)果;

(7)

(8)

式中：m----未知節(jié)點(diǎn)接收到每個(gè)信標(biāo)節(jié)點(diǎn)的RSSI值樣本數(shù)。

3.2 質(zhì)心差分修正

在實(shí)際環(huán)境中，多徑效應(yīng)、反射、折射等環(huán)境因素對(duì)RSSI值的影響較大，通過(guò)預(yù)處理在一定程度上解決了RSSI值的波動(dòng)問(wèn)題，直接采用預(yù)處理后的RSSI值通過(guò)加權(quán)質(zhì)心定位的精度偏低。文中通過(guò)預(yù)處理后的RSSI值計(jì)算信標(biāo)節(jié)點(diǎn)的測(cè)量距離與質(zhì)心，并對(duì)質(zhì)心差分修正以提高定位精度。

假設(shè)點(diǎn)O為未知節(jié)點(diǎn)，A1(x1,y1),A2(x2,y2),…,An(xn,yn)是未知節(jié)點(diǎn)通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)，由RSSI計(jì)算的距離升序排序?yàn)閧d1,d2,d3,d4,…，dn},取距離{d1,d2,d3}，其對(duì)應(yīng)的信標(biāo)節(jié)點(diǎn)為A1、A2、A3，以信標(biāo)節(jié)點(diǎn)A1、A2、A3為圓心，分別以d1、d2、d3為半徑畫(huà)圓，可得到三個(gè)圓的重合區(qū)域，如圖1所示。

圖1 三邊測(cè)量示意圖

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

(9)

其中，(xo1,yo1)為交點(diǎn)O1的坐標(biāo)，同理可求交點(diǎn)O2、O3的坐標(biāo)(xo2,yo2)、(xo3,yo3)，以O(shè)1、O2、O3為頂點(diǎn)作三角形，則△O1O2O3的質(zhì)心M1(xm1,ym1)為

(10)

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

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

(11)

對(duì)質(zhì)心修正

(12)

圖2 差分修正示意圖

通過(guò)對(duì)質(zhì)心坐標(biāo)的差分修正，減小了質(zhì)心與未知節(jié)點(diǎn)的偏差。利用質(zhì)心對(duì)未知節(jié)點(diǎn)進(jìn)行定位的過(guò)程中，距離越近的質(zhì)心對(duì)未知節(jié)點(diǎn)坐標(biāo)確定的影響力越大，可通過(guò)質(zhì)心權(quán)值來(lái)體現(xiàn)。質(zhì)心M1由未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn){A1,A2,A3}的測(cè)量距離確定，則質(zhì)心M1權(quán)值為

(13)

同理，質(zhì)心Mi權(quán)值為

(14)

未知節(jié)點(diǎn)的估計(jì)坐標(biāo)(xbest,ybest)為

(15)

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

(16)

式中：(xo,yo)----未知節(jié)點(diǎn)O的真實(shí)坐標(biāo);

(xbest,ybest)----未知節(jié)點(diǎn)的估計(jì)坐標(biāo)。

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

(17)

3.3 算法步驟

1)信標(biāo)節(jié)點(diǎn)周期性廣播信號(hào)，信號(hào)包含其自身的ID及坐標(biāo)等信息。

2)未知節(jié)點(diǎn)接收到多個(gè)信標(biāo)節(jié)點(diǎn)信號(hào)，記錄信標(biāo)節(jié)點(diǎn)的ID、坐標(biāo)，并對(duì)每個(gè)信標(biāo)節(jié)點(diǎn)的一組RSSI進(jìn)行預(yù)處理。

3)未知節(jié)點(diǎn)通過(guò)傳播損耗模型計(jì)算信標(biāo)節(jié)點(diǎn)的距離，對(duì)距離從小到大排序，并建立距離與信標(biāo)節(jié)點(diǎn)的映射。

4)按順序逐次取三個(gè)距離及對(duì)應(yīng)的信標(biāo)節(jié)點(diǎn)，構(gòu)成如圖1所示重合區(qū)域，計(jì)算重合區(qū)域交點(diǎn)以及交點(diǎn)的質(zhì)心。

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

6)采用加權(quán)質(zhì)心算法對(duì)修正后的質(zhì)心估計(jì)未知節(jié)點(diǎn)的坐標(biāo)。

4 仿真分析

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

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

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

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

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

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

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

隨著信標(biāo)節(jié)點(diǎn)數(shù)變化的平均定位誤差仿真結(jié)果如圖5所示。

圖5 不同信標(biāo)節(jié)點(diǎn)的平均定位誤差

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

5 結(jié) 語(yǔ)

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