(桂林航天工業(yè)學(xué)院自動(dòng)化系，廣西 桂林 541004)

0 引言

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

文獻(xiàn)[9]將離未知節(jié)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)作為修正節(jié)點(diǎn)；文獻(xiàn)[10]提出優(yōu)選信標(biāo)節(jié)點(diǎn)進(jìn)行加權(quán)質(zhì)心；文獻(xiàn)[11]根據(jù)信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離關(guān)系，調(diào)整加權(quán)系數(shù)；文獻(xiàn)[12]對信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的接收信號強(qiáng)度指示(received signal strength indication,RSSI)測距進(jìn)行加權(quán)平均。以上方法都是以RSSI測距為基礎(chǔ)，增加質(zhì)心算法和距離權(quán)重，測距誤差和距離權(quán)重直接影響定位精度。本文提出一種對距離權(quán)重和測距誤差進(jìn)行雙修正的質(zhì)心定位算法，提高定位性能。

1 算法模型

1.1 加權(quán)質(zhì)心算法

利用權(quán)重因子體現(xiàn)各信標(biāo)節(jié)點(diǎn)對質(zhì)心位置的影響程度，反映它們之間的內(nèi)在關(guān)系。

信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的質(zhì)心關(guān)系如圖1所示。圖1中，B1(XB1,YB1)、B2(XB2,YB2)、B3(XB3,YB3)分別為三個(gè)信標(biāo)節(jié)點(diǎn)，D為未知節(jié)點(diǎn)。

圖1 加權(quán)質(zhì)心示意圖

(1)

(2)

(3)

(4)

(5)

1.2 距離權(quán)重修正模型

利用加權(quán)質(zhì)心定位算法，可以獲得未知節(jié)點(diǎn)的一個(gè)位置預(yù)測，但是這種預(yù)測的位置僅反映質(zhì)心三角形中未知節(jié)點(diǎn)和兩個(gè)信標(biāo)節(jié)點(diǎn)總的距離關(guān)系。實(shí)際上，兩個(gè)信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的實(shí)際距離不可能是完全一致的，且對未知節(jié)點(diǎn)的權(quán)重影響也該是有差異的。離未知節(jié)點(diǎn)越近的信標(biāo)節(jié)點(diǎn)獲得的距離權(quán)重越大，離未知節(jié)點(diǎn)越遠(yuǎn)的信標(biāo)節(jié)點(diǎn)獲得的距離權(quán)重越小。

為了完善距離權(quán)重差異化的作用，提出的改進(jìn)算法首先修正距離權(quán)重，增加權(quán)重修正系數(shù)K1、K2、K3。

修正后，信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離和權(quán)重修正系數(shù)成反比。

坐標(biāo)權(quán)重修正式如下：

(6)

(7)

綜合x，y坐標(biāo)，可得距離權(quán)重修正式：

(8)

1.3 測距誤差修正模型

達(dá)到距離權(quán)重修正模型的修正效果，必須要有預(yù)測測距的基礎(chǔ)，而實(shí)際應(yīng)用中由于環(huán)境影響和硬件限制的原因，RSSI測距不能保證足夠的精確，測距誤差較大。針對這一問題，改進(jìn)算法從修正信標(biāo)測距入手，減小RSSI測距誤差影響。

(9)

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

修正節(jié)點(diǎn)誤差修正示意圖如圖2所示。

圖2 修正節(jié)點(diǎn)誤差修正示意圖

取離未知節(jié)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)作為修正節(jié)點(diǎn)。從圖2可以發(fā)現(xiàn)，距離未知節(jié)點(diǎn)D最近的信標(biāo)節(jié)點(diǎn)為B0，則將其作為修正節(jié)點(diǎn)。

由于B0和B1都是信標(biāo)節(jié)點(diǎn)，可以根據(jù)實(shí)際坐標(biāo)精確得到兩者之間的實(shí)際距離dB1B0。

(10)

(11)

αB1B0替代未知節(jié)點(diǎn)D與信標(biāo)節(jié)點(diǎn)B1之間的誤差因子αDB1：

αB1B0=αDB1

(12)

得到未知節(jié)點(diǎn)D與信標(biāo)節(jié)點(diǎn)B1修正測距值：

(13)

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

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

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

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

2 算法步驟

質(zhì)心定位算法的具體步驟如下。

① 信標(biāo)節(jié)點(diǎn)周期性發(fā)送節(jié)點(diǎn)ID、自身位置信息P。

② 未知節(jié)點(diǎn)統(tǒng)計(jì)可通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)集合ωΒ={Β1,Β2，…,Βn}，并選取同一個(gè)信標(biāo)節(jié)點(diǎn)的多次RSSI均值作為當(dāng)前信標(biāo)節(jié)點(diǎn)與自身通信的RSSI值。

④ 未知節(jié)點(diǎn)選擇集合ωΒ中RSSI值最大的三個(gè)信標(biāo)節(jié)點(diǎn)構(gòu)成質(zhì)心三角形，結(jié)合距離權(quán)重系數(shù)得到權(quán)重修正預(yù)測位置。

⑥ 將修正誤差因子代入測距誤差修正式，得到基于距離權(quán)重和測距誤差雙修正的質(zhì)心算法，最終得到較為精確的未知節(jié)點(diǎn)位置。

3 仿真結(jié)果與分析

利用Matlab仿真試驗(yàn)平臺比較改進(jìn)算法與傳統(tǒng)加權(quán)質(zhì)心算法的性能。節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的區(qū)域內(nèi)，未知節(jié)點(diǎn)的位置隨機(jī)產(chǎn)生，信標(biāo)節(jié)點(diǎn)均勻隨機(jī)分布。

從以下三個(gè)方面來衡量改進(jìn)算法的效果。

① 以預(yù)測位置和實(shí)際位置的差異來衡量，距離權(quán)重和測距誤差雙修正質(zhì)心算法的節(jié)點(diǎn)位置仿真結(jié)果如圖3所示，加權(quán)質(zhì)心算法節(jié)點(diǎn)位置仿真結(jié)果如圖4所示。

從圖3和圖4可以看出，距離權(quán)重和測距誤差雙修正質(zhì)心算法得到的未知節(jié)點(diǎn)的預(yù)測位置與實(shí)際位置之間的距離明顯小于加權(quán)質(zhì)心定位算法。

圖3 雙修正質(zhì)心算法仿真圖

圖4 加權(quán)質(zhì)心算法仿真圖

② 從權(quán)重修正系數(shù)對平均定位誤差的影響程度來衡量。定位誤差指的是通過定位計(jì)算得到的未知節(jié)點(diǎn)的估計(jì)位置與實(shí)際位置的偏差。這種偏差可以用兩者之間的歐氏距離除以節(jié)點(diǎn)的通信半徑來衡量，最后，利用平均定位誤差來衡量定位算法的優(yōu)劣。

平均定位誤差與修正系數(shù)關(guān)系圖如圖5所示。

圖5 平均定位誤差與修正系數(shù)關(guān)系圖

計(jì)算節(jié)點(diǎn)定位誤差為：

(14)

對N個(gè)未知節(jié)點(diǎn)的定位誤差求平均，得到平均定位誤差：

(15)

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

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

測距誤差與定位誤差關(guān)系圖如圖6所示。

圖6 測距誤差與定位誤差關(guān)系圖

從圖6可以看出，隨著測距誤差的增大，未知節(jié)點(diǎn)的平均定位誤差也隨之增加，這是因?yàn)闇y距誤差的增加使得距離權(quán)重影響誤差加大，造成定位精度下降。采用距離權(quán)重和測距誤差雙修正質(zhì)心算法可以減少測距誤差帶來的影響。測距誤差越大，其誤差修正的作用就越強(qiáng)。

4 結(jié)束語

本文在加權(quán)質(zhì)心定位算法的基礎(chǔ)上，利用距離模型對距離權(quán)重進(jìn)行調(diào)節(jié)，為距離權(quán)重匹配修正系數(shù)。利用修正節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的RSSI測距誤差因子，校正未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的RSSI測距誤差因子，強(qiáng)化了信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)間距的權(quán)重影響，減少了RSSI測距帶來的誤差影響，提高了未知節(jié)點(diǎn)的定位精度。

質(zhì)心定位算法不需要節(jié)點(diǎn)之間進(jìn)行復(fù)雜的協(xié)調(diào)過程，算法復(fù)雜度也只比質(zhì)心算法略有增加，具有良好的可擴(kuò)展性，可以滿足傳感器網(wǎng)絡(luò)中對位置精度不太苛刻的應(yīng)用。

[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] 溫立.無線傳感器網(wǎng)絡(luò)定位技術(shù)研究[D].上海：復(fù)旦大學(xué),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] 程偉,史浩山,王慶文.基于差分修正的傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J].系統(tǒng)仿真學(xué)報(bào),2012,24(2)：389-393.

[10]趙昭,陳小惠.無線傳感器網(wǎng)絡(luò)中基于RSSI的改進(jìn)定位算法[J].傳感技術(shù)學(xué)報(bào)，2009,22(3):391-394.

[11]胡詠梅,張歡.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法[J].計(jì)算機(jī)工程與科學(xué),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.