WSNs中基于測(cè)距修正和擬牛頓法的節(jié)點(diǎn)定位算法

孫 豫

(駐馬店職業(yè)技術(shù)學(xué)院信息工程學(xué)院，河南 駐馬店 463000)

0 引言

隨著通信技術(shù)的迅速發(fā)展，無(wú)線(xiàn)傳感網(wǎng)絡(luò)(wireless sensor networks，WSNs)[1]已在環(huán)境監(jiān)測(cè)、軍事和醫(yī)療等領(lǐng)域廣泛應(yīng)用。WSNs中節(jié)點(diǎn)具有感測(cè)、通信能力。這些節(jié)點(diǎn)感測(cè)環(huán)境數(shù)據(jù)，如溫度、濕度，并將所感測(cè)的數(shù)據(jù)傳輸至控制中心，以便控制中心進(jìn)行處理。然而，只有明確了節(jié)點(diǎn)位置信息，其感測(cè)的數(shù)據(jù)才可能具有意義。因此，定位是WSNs的關(guān)鍵技術(shù)。

測(cè)距定位和非測(cè)距定位算法是主要的兩類(lèi)定位算法。不失一般性，基于測(cè)距定位算法精度高于非測(cè)距定位算法。常見(jiàn)的測(cè)距算法有：基于接收信號(hào)強(qiáng)度指標(biāo)(received signal strength indication, RSSI)[2]、基于信號(hào)到達(dá)角度(angle of arrival, AoA)[3]、基于信號(hào)到達(dá)時(shí)間(time of arrival, ToA)[4]。與ToA和AoA不同，基于RSSI測(cè)距無(wú)需額外的測(cè)量設(shè)備，易實(shí)施。因此，基于RSSI測(cè)距定位受到廣泛關(guān)注。

為了提高基于RSSI測(cè)距定位的精度，對(duì)RSSI值進(jìn)行濾波處理。文獻(xiàn)[5]提出雙標(biāo)簽定位算法。該算法采用兩個(gè)水平或者垂直定位標(biāo)簽，利用這兩個(gè)標(biāo)簽所采集的RSSI值進(jìn)行測(cè)距，進(jìn)而降低RSSI因環(huán)境影響而產(chǎn)生的波動(dòng)。然而，該算法需要額外部署一個(gè)標(biāo)簽，增加了硬件成本。

近期，由于微處理器數(shù)據(jù)處理速率和能力的提升，節(jié)點(diǎn)能夠在較短時(shí)間內(nèi)處理一定量的數(shù)據(jù)。因此，一些智能優(yōu)化算法被用于節(jié)點(diǎn)定位。例如，文獻(xiàn)[6]運(yùn)用人工神經(jīng)網(wǎng)絡(luò)對(duì)RSSI進(jìn)行預(yù)處理，降低測(cè)量RSSI值誤差，進(jìn)而提高測(cè)距精度，為后續(xù)定位提供準(zhǔn)確的測(cè)距數(shù)據(jù)。文獻(xiàn)[7]運(yùn)用獅群優(yōu)化算法估計(jì)節(jié)點(diǎn)位置。該算法的定位精度嚴(yán)重依賴(lài)于測(cè)距精度。若測(cè)距誤差大，界定了搜索區(qū)域存在偏差，這就降低了定位誤差。同時(shí)，節(jié)點(diǎn)端執(zhí)行智能優(yōu)化算法增加了節(jié)點(diǎn)能耗。

為此，提出基于測(cè)距修正和擬牛頓法節(jié)點(diǎn)定位(ranging correction and quasi-Newton method-based localization, RCNL)算法。RCNL算法先通過(guò)多次測(cè)量收/發(fā)兩端間RSSI值，再利用正態(tài)濾波對(duì)RSSI值進(jìn)行處理，剔除誤差較大的RSSI值，然后進(jìn)入定位階段。定位階段細(xì)分為兩個(gè)子階段：在第一個(gè)子階段，未知節(jié)點(diǎn)利用RSSI測(cè)距，并利用這些測(cè)距構(gòu)建搜索區(qū)域，再利用Bounding-box算法估計(jì)未知節(jié)點(diǎn)的位置，此次所估計(jì)的值為初始位置；在第二個(gè)子階段，運(yùn)用擬牛頓法校正初始位置的偏差，提高定位精度。性能分析表明，相比于同類(lèi)算法，RCNL算法降低了歸一化定位誤差，提高了定位精度。

1 RCNL算法

1.1 RCNL算法概述

RCNL算法先對(duì)RSSI值進(jìn)行濾波，再依據(jù)RSSI值估計(jì)收/發(fā)兩端間距離(測(cè)距)。然后，依據(jù)這些測(cè)距數(shù)據(jù)作為Bounding-box算法的輸入，輸出為對(duì)未知節(jié)點(diǎn)的位置估計(jì)(初始位置)?？紤]牛頓迭代法收斂速度依賴(lài)于初始值，將未知節(jié)點(diǎn)的初始位置作為擬牛頓法的初始值，再由擬牛頓法估計(jì)未知節(jié)點(diǎn)的位置。圖1給出RCNL算法的總體框架。

圖1 RCNL算法框圖

1.2 RSSI預(yù)處理

接收端記錄接收信號(hào)的RSSI值，基于RSSI測(cè)距原理，利用RSSI值估算與發(fā)送端間距離，依據(jù)Shadowing的傳播模型，可得收/發(fā)兩端間距離關(guān)于RSSI值的關(guān)系式[8]：

(1)

式中：Pr表示接收端記錄接收信號(hào)的RSSI值；Pt表示發(fā)射端傳輸功率；d0表示參考距離，通常取d0=1m；PL(d0)表示在參考距離條件下的路徑損耗功率；χ表示測(cè)距噪聲，其服從高斯分布。在理想測(cè)距環(huán)境，χ=0；d表示收/發(fā)兩端間距離，如圖2所示。

圖2 信號(hào)傳輸模型

考慮到RSSI值易受外界影響，對(duì)RSSI值進(jìn)行預(yù)處理，濾除偏差大的RSSI值，進(jìn)而提高測(cè)距精度。多次測(cè)量的RSSI值應(yīng)呈正態(tài)分布。利用正態(tài)分布的3σ原則[9]，可知信號(hào)分布在(u-σ,u+σ)區(qū)域內(nèi)的概率約為0.652 6。其中u表示均值；σ為方差。

為此，RCNL算法先引用正態(tài)濾波策略濾除不在(u-σ,u+σ)區(qū)域內(nèi)的RSSI值, 獲取較準(zhǔn)確的RSSI值。盡管引用正態(tài)濾波策略濾除了不準(zhǔn)確的RSSI值，但其增加了算法的復(fù)雜度，將在2.5節(jié)中分析算法的復(fù)雜度。

然后，計(jì)算這組RSSI值的均值：

(2)

(3)

1.3 基于Bounding-box算法估計(jì)未知節(jié)點(diǎn)初始位置

Bounding-box算法也稱(chēng)包圍盒算法，其是通過(guò)測(cè)量與錨節(jié)點(diǎn)間距離，并利用距離確定未知節(jié)點(diǎn)可能存在的矩形區(qū)。未知節(jié)點(diǎn)在多個(gè)矩形區(qū)域的重疊區(qū)域的概率最大。將重疊區(qū)域中心位置作為未知節(jié)點(diǎn)的估計(jì)位置。由于Bounding-box算法實(shí)施簡(jiǎn)單，RCNL算法引用該算法估計(jì)未知節(jié)點(diǎn)位置?？紤]到Bounding-box算法定位精度不高，只將由Bounding-box算法估計(jì)的節(jié)點(diǎn)位置作為擬牛頓法的初始值[10]。

圖3 基于Bounding-box算法示意圖

1.4 基于擬牛頓法的節(jié)點(diǎn)位置修正

1.4.1 BFGS擬牛頓法

作為一種廣泛應(yīng)用的擬牛頓迭代法，BFGS算法是由Broyden, Fletcher, Goldfard和Shanno四人提出的牛頓法改進(jìn)算法。BFGS算法通過(guò)迭代方式求解問(wèn)題[11]。

令f表示關(guān)于未知變量的函數(shù)；X(x,y)表示未知變量。利用BFGS擬牛頓法通過(guò)式(4)求解變量X：

(4)

利用由正定矩陣B定義為Hessian矩陣的逆矩陣，即H-1=B。B的第k次迭代的值Bk為：

該橋東西兩側(cè)人行道鋪裝均存在縱向裂縫，這主要是由于人行道下板梁間未設(shè)鉸縫連接，板梁間拼縫反射到人行道鋪裝表面所致。此外，人行道鋪裝還存在局部網(wǎng)裂和破損。

Bk+1=Bk+ΔBk

(5)

(6)

式中：

sk=Xk+1-Xk

(7)

yk=f′(Xk+1)-f′(Xk)

(8)

1.4.2 基于誤差最小化的目標(biāo)函數(shù)的構(gòu)建

為了降低定位誤差，將最小化定位誤差作為目標(biāo)函數(shù)：

f(x,y)=minE(x,y)

(9)

對(duì)E(x,y)展開(kāi)，整理可得：

(10)

(11)

將式(11)代入式(1)，可得非約束優(yōu)化問(wèn)題。然后，利用BFGS算法迭代求解式(9)。求解步驟為：

步驟一，對(duì)參數(shù)進(jìn)行初始化。由Bounding-box算法估計(jì)未知節(jié)點(diǎn)的位置，并將此位置作為X的初值；設(shè)置誤差閾值ξ和最大迭代次數(shù)Nmax；將迭代次數(shù)k賦予0。

步驟三，設(shè)置步長(zhǎng)γk，并更新Xk+1：Xk+1=Xk+γkdk。

步驟五，依據(jù)式(5)進(jìn)行迭代運(yùn)算，再執(zhí)行k=k+1。

步驟六，判斷k是否達(dá)到最大迭代次數(shù)Nmax，若達(dá)到，就結(jié)束迭代，否則跳轉(zhuǎn)到第二步。圖4給出了BFGS算法求解目標(biāo)函數(shù)的主要流程。

圖4 基于BFGS算法求解目標(biāo)函數(shù)的主流程

2 性能分析

2.1 仿真環(huán)境

利用Matlab軟件建立仿真平臺(tái)，分析RCNL算法的定位誤差。 在100 m×100 m區(qū)域內(nèi)部署100～225個(gè)未知節(jié)點(diǎn)，10～30個(gè)錨節(jié)點(diǎn)。所有節(jié)點(diǎn)的通信半徑在25～40 m變化。具體的仿真參數(shù)如表1所示。

表1 仿真參數(shù)

選擇王宇鵬等[12]提出的基于稀疏傅里葉RSSI測(cè)距的低復(fù)雜RSSI定位算法(spare fourier-RSSI positioning, SFRP)和文獻(xiàn)[13]提出的基于DV-hop的改進(jìn)算法(IDV-hop)，并分析它們的歸一化定位誤差性能：

(12)

2.2 定位誤差隨錨節(jié)點(diǎn)數(shù)的變化情況

圖5給出歸一化定位誤差隨錨節(jié)點(diǎn)數(shù)的變化曲線(xiàn)，其中節(jié)點(diǎn)總數(shù)為100，通信半徑為25 m，錨節(jié)點(diǎn)數(shù)范圍為10～30。

圖5 歸一化定位誤差隨錨節(jié)點(diǎn)數(shù)的變化情況

由圖可知，定位誤差隨錨節(jié)點(diǎn)數(shù)的增加而下降。這符合預(yù)期：網(wǎng)絡(luò)內(nèi)錨節(jié)點(diǎn)數(shù)越多，未知節(jié)點(diǎn)從錨節(jié)點(diǎn)獲取的測(cè)距數(shù)據(jù)越多，這有利于提高測(cè)距精度。同時(shí)，錨節(jié)點(diǎn)數(shù)越多，錨節(jié)點(diǎn)分布密度也越高，這也提高了測(cè)距精度。測(cè)距精度越高，定位誤差就越小。

此外，相比于SFRT和IDV-Hop算法， 提出的RCNL算法降低了平均定位誤差，分別下降約2%和6%，原因在于：RCNL算法既從測(cè)距階段和定位階段進(jìn)行了優(yōu)化。通過(guò)加權(quán)正態(tài)濾波濾除了偏差大的RSSI值，提高了測(cè)距精度；結(jié)合Bounding-box法和擬牛頓迭代法定位，提高了定位精度。

2.3 定位誤差隨通信半徑的變化情況

圖6繪制了歸一化定位誤差隨通信半徑的變化情況，其中節(jié)點(diǎn)數(shù)為100，錨節(jié)點(diǎn)數(shù)為15，節(jié)點(diǎn)通信半徑范圍為15～35 m。

圖6 歸一化定位誤差隨通信半徑的變化情況

從圖6的曲線(xiàn)走勢(shì)可知，增加節(jié)點(diǎn)的通信半徑可有效地降低定位誤差，定位精度得到提升。這符合預(yù)期。通信半徑越大，節(jié)點(diǎn)間的通信跳數(shù)減少，測(cè)量RSSI的誤差降低，提高了測(cè)距精度。

相比于SFRT和IDV-Hop算法，RCNL算法仍保持低的定位誤差。這是因?yàn)镽CNL算法先利用Bounding-box算法搜索未知節(jié)點(diǎn)的位置，并將此位置作為BFGS擬牛頓法的初始值進(jìn)行迭代，進(jìn)而對(duì)該位置進(jìn)行修正，從而提高了未知節(jié)點(diǎn)位置的精度。

2.4 定位誤差隨節(jié)點(diǎn)數(shù)的變化情況

最后討論未知節(jié)點(diǎn)數(shù)對(duì)定位誤差的影響。圖7給出歸一化定位誤差隨節(jié)點(diǎn)數(shù)的變化情況，其中錨節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)比例為15%，節(jié)點(diǎn)數(shù)范圍為100～225，通信半徑為30 m。

圖7 歸一化定位誤差隨節(jié)點(diǎn)數(shù)的變化情況

從圖7曲線(xiàn)走勢(shì)可知，最初，節(jié)點(diǎn)數(shù)的增加使定位誤差迅速下降。但當(dāng)節(jié)點(diǎn)數(shù)增加至約160時(shí)，定位誤差不再隨節(jié)點(diǎn)數(shù)的增加而下降。原因在于：最初，盡管節(jié)點(diǎn)數(shù)在增加，但節(jié)點(diǎn)數(shù)仍較少，錨節(jié)點(diǎn)數(shù)在增加，這有利于增加定位精度。但當(dāng)節(jié)點(diǎn)數(shù)增加至一定量后，相對(duì)于未知節(jié)點(diǎn)數(shù)的分布密度，錨節(jié)點(diǎn)的分布密度下降。

2.5 算法的復(fù)雜度

用算法的運(yùn)行時(shí)間表征算法的復(fù)雜度。運(yùn)行時(shí)間越長(zhǎng)，算法越復(fù)雜。在聯(lián)想小新Air14，系統(tǒng)為Windows10，處理器為Intel i5，內(nèi)存容量為16 GB的PC機(jī)上運(yùn)行定位算法。

實(shí)驗(yàn)參數(shù)：通信半徑為30 m；未知節(jié)點(diǎn)數(shù)為150，錨節(jié)點(diǎn)數(shù)為30。最大的迭代次數(shù)為100。表2給出RCNL算法、SFRT和IDV-Hop算法的運(yùn)行時(shí)間。從表2可知，提出的RCNL算法的運(yùn)行時(shí)間高于SFRT和IDV-Hop算法。原因在于：RCNL算法執(zhí)行Bounding-box算法和BFGS擬牛頓法，增加了運(yùn)行時(shí)間。RCNL算法的運(yùn)算時(shí)間達(dá)到45.2 s。參照文獻(xiàn)[14]，在室外空曠地區(qū)GPS的平均定位時(shí)間約156 s。相比于GPS系統(tǒng)，RCNL算法的45.2 s定位時(shí)間可接受。

表2 算法的運(yùn)行時(shí)間

綜上分析可知，RCNL算法具有較高的定位精度，但其復(fù)雜度也較高，定位時(shí)間達(dá)到45.2 s。即RCNL算法以高的復(fù)雜度為代價(jià)，得到高的定位精度。高的復(fù)雜度使RCNL算法不能及時(shí)地估計(jì)節(jié)點(diǎn)的位置，無(wú)法適用于實(shí)時(shí)性要求高的應(yīng)用場(chǎng)景。

3 結(jié)論

為了降低基于RSSI測(cè)距的節(jié)點(diǎn)定位誤差，提出基于測(cè)距修正和擬牛頓法節(jié)點(diǎn)定位 RCNL算法。RCNL算法通過(guò)正態(tài)濾波剔除誤差較大的RSSI值，提升測(cè)距精度。并利用Bounding-box算法和擬牛頓法估計(jì)節(jié)點(diǎn)位置，提高了定位精度。

然而，提出的RCNL算法的復(fù)雜度仍偏高，后期將進(jìn)一步優(yōu)化RCNL算法，在保證定位精度的同時(shí)，降低算法的復(fù)雜度，縮短定位時(shí)間，拓展RCNL算法的應(yīng)用場(chǎng)景。