袁 鑫,吳曉平,2*,王國英,2

(1.浙江農(nóng)林大學(xué)信息工程學(xué)院,浙江 臨安 311300;2.浙江省林業(yè)智能監(jiān)測與信息技術(shù)研究重點實驗室,浙江 臨安 311300)

?

線性最小二乘法的RSSI定位精確計算方法*

袁 鑫1,吳曉平1,2*,王國英1,2

(1.浙江農(nóng)林大學(xué)信息工程學(xué)院,浙江 臨安 311300;2.浙江省林業(yè)智能監(jiān)測與信息技術(shù)研究重點實驗室,浙江 臨安 311300)

基于接收信號強度指示(RSSI)定位模型,提出了一種目標(biāo)節(jié)點位置的精確計算方法。將RSSI定位問題所描述的非線性優(yōu)化函數(shù)轉(zhuǎn)化為線性最小二乘法估計問題,將定位結(jié)果直接用代數(shù)解表示。分別提出了目標(biāo)節(jié)點信號發(fā)射強度已知和未知下的非約束線性最小二乘(ULLS)定位方法。同時對非約束線性最小二乘法下的參數(shù)進一步優(yōu)化,提出了約束線性最小二乘法以提高定位精度。仿真驗證了該定位計算方法的有效性,測試了不同信號強度噪聲對定位誤差的影響。結(jié)果同時表明,約束線性最小二乘法比非約束線性最小二乘法的定位誤差更小,非常接近于定位結(jié)果的克拉美羅下界值(CRLB)。

無線傳感器網(wǎng)絡(luò);定位;無線信號強度;線性最小二乘法

無線傳感器網(wǎng)絡(luò)(WSNs)是通過將大量具有傳感器單元、數(shù)據(jù)處理單元及通信模塊的微小智能節(jié)點密集地散布在感知區(qū)域,節(jié)點間以自組織方式構(gòu)成的無線通信網(wǎng)絡(luò)。無線傳感器網(wǎng)絡(luò)能夠?qū)崟r監(jiān)測、感知和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境或監(jiān)測對象的信息,并對這些信息進行處理,從而為遠程用戶提供詳盡而準(zhǔn)確的信息[1]。采用無線傳感器網(wǎng)絡(luò)進行信息收集和處理,這些數(shù)據(jù)必須和位置信息相結(jié)合才有意義,甚至有時需要傳感器節(jié)點發(fā)回單純的位置信息[2-4]。無線傳感器網(wǎng)絡(luò)以其廉價的無線通信組網(wǎng)而區(qū)別于其他無線通訊技術(shù)。從應(yīng)用角度來講,節(jié)點定位是無線傳感器網(wǎng)絡(luò)中最為重要和傳統(tǒng)的問題,研究具有低成本、高精度的無線傳感器網(wǎng)絡(luò)定位系統(tǒng)是該領(lǐng)域的主要問題之一。傳統(tǒng)的測距定位方法,如到達時間(TOA)[5-6]、到達時間差(TDOA)[7]、到達角度(AOA)[8]等能獲取較高的定位精度,但需要額外的測距硬件設(shè)施,增加了定位成本,且節(jié)點間的測距易受環(huán)境、節(jié)點硬件、網(wǎng)絡(luò)攻擊等各種因素的干擾。以節(jié)點的連通性、網(wǎng)絡(luò)拓撲為基礎(chǔ)的非測距定位方法[9]亦能定位節(jié)點坐標(biāo),但定位精度不高,限制了其使用范圍。

數(shù)據(jù)感知與信號傳輸是無線傳感器網(wǎng)絡(luò)節(jié)點的基本內(nèi)容,節(jié)點間以電磁波的形式進行相互通信,無線信號強度隨傳輸路徑的延長而衰減。在無線傳感器網(wǎng)絡(luò)領(lǐng)域,接受信號強度指示(RSSI)距離測量被認(rèn)為是一種具有較高性價比的方法。RSSI定位方法無需額外硬件,實現(xiàn)簡單,具備低功耗、低成本等特點,應(yīng)用十分廣泛[10-11]。最大可能(ML)估計方法能達到定位結(jié)果的克拉美羅下界(CRLB),文獻[12]將ML估計方法應(yīng)用于能量定位模型,并提出了相應(yīng)的多目標(biāo)定位實現(xiàn)方法。為改進強噪聲對定位結(jié)果的嚴(yán)重干擾,根據(jù)RSSI定位模型Wang等[13]提出了半正定(SDP)放松的方法以精確定位目標(biāo)位置,但由于SDP方法進行了約束放松,定位精度沒能達到CRLB,且SDP定位方法的計算復(fù)雜度較高。亦有文獻將定位模型所描述的非線性優(yōu)化函數(shù)轉(zhuǎn)化為其他數(shù)學(xué)模型問題,如Ho等[14]將非線性過程轉(zhuǎn)化為線性方程,提出了一種線性代數(shù)解法亦能精確目標(biāo)節(jié)點位置,但該計算方法未考慮目標(biāo)節(jié)點發(fā)射強度未知下的最優(yōu)估計結(jié)果。雖然ML方法的定位精度較高,但計算復(fù)雜度較大,基于自校正RSSI測距模型Coluccia[15]提出了一種低復(fù)雜度的ML定位方法。

ML估計方法的數(shù)值解法有可能產(chǎn)生局部最優(yōu)解,導(dǎo)致定位結(jié)果不穩(wěn)定。本文針對無線信號強度RSSI的定位模型,提出了目標(biāo)節(jié)點信號發(fā)射強度已知和未知兩種情況下的目標(biāo)節(jié)點位置的精確代數(shù)計算方法。該定位計算方法以ML估計方法所描述的非線性優(yōu)化函數(shù)為出發(fā)點,將非線性優(yōu)化函數(shù)轉(zhuǎn)化為線性最小二乘估計問題,并將定位結(jié)果直接用代數(shù)解表示,以提高定位結(jié)果的穩(wěn)定性。在建立的非約束線性最小二乘(ULLS)法的求解基礎(chǔ)上,利用向量元素間的相互約束關(guān)系,推導(dǎo)了約束線性最小二乘(CLLS)的計算方法,提高了定位精度。

本文第1部分首先介紹了RSSI定位模型;第2部分推導(dǎo)了RSSI模型定位結(jié)果CRLB下界值;第3部分推導(dǎo)了目標(biāo)節(jié)點信號發(fā)射強度已知和未知兩種情況下的ULLS和CLLS定位計算方法;第4部分為仿真與分析;最后部分為結(jié)論。

1 RSSI定位模型

假設(shè)在二維坐標(biāo)平面上分布著N個信標(biāo)節(jié)點,信標(biāo)節(jié)點i位置坐標(biāo)為xi=[xiyi]T(i=1,2,…,N)。設(shè)x=[xy]T表示被定位目標(biāo)節(jié)點坐標(biāo),目標(biāo)節(jié)點與信標(biāo)節(jié)點i間的無線接收信號強度為pi。假設(shè)節(jié)點間的RSSI測距服從對數(shù)衰減模型,則節(jié)點間RSSI信號強度pi與相對距離的有關(guān)系式

pi=p0-10βlgdi+εi

(1)

(2)

式(2)所描述的非線性最小平方問題可以采用數(shù)值計算方法求解,如高斯牛頓迭代法或Levenberg-Marquardt(LM)算法迭代求解。采用數(shù)值計算方法時,可能會陷入局部最優(yōu),使定位結(jié)果發(fā)散。為此將式(2)描述的非線性優(yōu)化函數(shù)轉(zhuǎn)化為線性最小二乘估計問題,其定位結(jié)果采用代數(shù)解表示,提高定位結(jié)果的可靠性。

2 定位結(jié)果CRLB

CRLB為模型待估目標(biāo)位置x的無偏估計提供了誤差方差的下界,x滿足cov(x)≥F-1,這里F為待估參數(shù)x的FIM(Fisher Information Matrix)的表示。以對數(shù)衰減模型描述的信號強度與節(jié)點間距離關(guān)系,與待定位節(jié)點的發(fā)射信號強度p0有關(guān)。下面分別根據(jù)發(fā)射信號強度p0已知和未知兩種不同情況下的定位結(jié)果CRLB進行分析。

2.1 已知發(fā)射信號強度p0

當(dāng)p0已知時,則矩陣F可以表示為

(3)

(4)

則根據(jù)CRLB無偏估計下界理論有

(5)

2.2 未知發(fā)射信號強度p0

由于發(fā)射信號強度p0未知,矩陣F可以表示為

(6)

(7)

3 線性最小二乘法定位

下面分別根據(jù)發(fā)射信號強度p0已知和未知兩種不同情況下采用線性最小二乘法計算目標(biāo)節(jié)點坐標(biāo)x。

3.1 已知發(fā)射信號強度p0

對式(1)進行變換,改寫為

(8)

式(8)中,i=1,2,…,N。對式(8)右邊采用泰勒級數(shù)展開,忽略高階項,將式(8)再變換為

(9)

(10)

式(10)中,i=1,2,…,N。令z=[xyx2+y2]T,可將式(10)寫成線性矩陣形式

Az=b+α

(11)

根據(jù)線性最小二乘平方原理,參數(shù)z的無偏估計值為

z=(ATWαA)-1ATWαb

(12)

(13)

式(13)中,i,j=1,2,…N。

假設(shè)參數(shù)z的估計誤差為Δz,其值為

Δz=(ATWαA)-1ATWαα

(14)

估計誤差Δz的方差為

cov(Δz)=(ATWαA)-1

(15)

從參數(shù)z提取出z(1:2)即為被定位目標(biāo)節(jié)點坐標(biāo)。上述求解過程并未考慮向量z=[xyx2+y2]T中各元素的相互約束關(guān)系,把該計算方法稱為已知發(fā)射信號強度p0下RSSI定位問題的非約束線性最小二乘(ULLS)方法。式(7)得到了被定位目標(biāo)節(jié)點坐標(biāo)的近似估計值,可利用向量z=[xyx2+y2]T元素間的相互約束關(guān)系計算其目標(biāo)節(jié)點位置坐標(biāo)精確值。被定位目標(biāo)節(jié)點坐標(biāo)的真實值假設(shè)為xo=[xoyo]T,則有以下關(guān)系式

(16)

式(16)中z(k)、Δz(k)表示了向量z、Δz的第k個元素,k=1,2,3。將式(16)表示為線性矩陣形式

Guo=h+β

(17)

根據(jù)線性最小二乘平方原理,向量uo的無偏估計為
u=(GTWβG)-1GTWβh

(18)

式(18)中維度為3×3的矩陣Wβ值為Wβ=E(βTβ)-1=[LTcov(Δz)L]-1=L-1ATWαAL-1

(19)

由于uo=[xo2yo2]T,則被定位目標(biāo)節(jié)點坐標(biāo)的精確估計值x為

(20)

將以式(20)表示的計算過程考慮了參數(shù)z中元素間的相互約束關(guān)系,進一步優(yōu)化了定位結(jié)果,將此過程稱為已知發(fā)射信號強度p0下RSSI定位問題的約束線性最小二乘(CLLS)方法。

3.2 未知發(fā)射信號強度p0

發(fā)射信號強度p0因節(jié)點的電池和天線增益不同而有所區(qū)別。下面就發(fā)射信號強度p0未知情況下的線性計算問題進行改進。

將式(9)變換為

(21)

Czρ=d+α

(22)

同樣根據(jù)線性最小二乘平方原理,參數(shù)zρ的無偏估計值為

zρ=(CTWαC)-1CTWαd

(23)

式(23)中維度為N×N的矩陣Wα為最小平方權(quán)重系數(shù),其值計算同式(13)。由于在計算權(quán)重系數(shù)Wα?xí)r,需要發(fā)射信號強度p0。可預(yù)先設(shè)置Wα為單位矩陣,近似地求解發(fā)射信號強度p0,然后以p0近似值計算Wα,再以式(23)精確計算參數(shù)zρ。同樣從參數(shù)zρ提取出zρ(1:2)即為被定位目標(biāo)節(jié)點坐標(biāo)。此計算過程為未知發(fā)射信號強度p0下RSSI定位問題的非約束線性最小二乘(ULLS)方法。

同樣地可利用向量z=[xyx2+y2]T元素間的相互約束關(guān)系計算目標(biāo)節(jié)點坐標(biāo)的精確值,具體計算過程可參考式(14)～式(20),此計算過程稱為未知發(fā)射信號強度p0下RSSI定位問題的約束線性最小二乘(CLLS)方法。

4 仿真分析

根據(jù)發(fā)射信號強度p0已知和未知兩種不同情況下的線性最小二乘ULLS和CLLS定位計算方法,采用MATLAB軟件進行了算法仿真實現(xiàn)。假設(shè)被定位目標(biāo)節(jié)點與每個信標(biāo)節(jié)點間的信號強度噪聲都服從均值為0,方差為δ2的高斯分布,仿真測試了不同計算方法下的定位結(jié)果。為評價文中不同算法下的定位效果,目標(biāo)節(jié)點的定位精度采用均方誤差(MSE)定位誤差判斷。

4.1 已知發(fā)射信號強度p0下的定位結(jié)果

無線傳感器網(wǎng)絡(luò)節(jié)點部署在100 m×100 m區(qū)域內(nèi),在該區(qū)域內(nèi)將5個信標(biāo)節(jié)點位置坐標(biāo)預(yù)先設(shè)置在(20,30),(15,80),(40,15),(70,10),(15,90),將被定位目標(biāo)節(jié)點坐標(biāo)預(yù)先設(shè)置在(50,50)點。同時預(yù)先設(shè)置p0=-45 dB,路徑衰減指數(shù)β=2。調(diào)整信號強度噪聲,即調(diào)整參數(shù)δ2從0.12到12之間變化,即調(diào)整10lg(δ2)從-20 dB到0 dB之間變化,仿真測試了不同計算方法下的MSE定位誤差。對每種定位算法下的MSE定位誤差仿真運行1 000次,采用1 000次運行結(jié)果的平均MSE定位誤差評價定位算法的定位精度,圖1(a)繪出了ULLS和CLLS兩種不同算法下的定位誤差隨噪聲變化關(guān)系。從圖1(a)可見,隨著20lg(δ2)的增加,即信號強度噪聲的增大,平均MSE定位誤差也隨之增大,20lg(MSE)定位誤差與信號強度噪聲20lg(δ2)之間有近似線性關(guān)系。當(dāng)信號強度噪聲等于-20 dB時,ULLS方法的定位誤差20lg(MSE)為-3.9 dB,而CLLS方法的定位誤差10lg(MSE)為-14.1 dB。相比于ULLS方法,CLLS方法的定位誤差有較大減少,非常接近于定位結(jié)果的CRLB下界值。

圖1 已知發(fā)射信號強度p0下的定位結(jié)果

設(shè)定信號強度噪聲δ2為0.12,圖1(b)繪出了1 000次隨機測試下兩種不同計算方法下定位結(jié)果的累積分布函數(shù)曲線(CDF)。顯然ULLS方法的定位誤差較大,而CLLS方法能有效改進定位誤差。ULLS方法下90%定位結(jié)果MSE小于1.6 m2,而對于CLLS方法下90%的定位結(jié)果平方誤差小于0.5 m2。

4.2 未知發(fā)射信號強度p0下的定位結(jié)果

無線傳感器網(wǎng)絡(luò)節(jié)點部署在100 m×100 m區(qū)域內(nèi),在該區(qū)域內(nèi)將6個信標(biāo)節(jié)點位置坐標(biāo)預(yù)先設(shè)置在(20,30),(15,80),(40,15),(70,10),(15,90),(80,20),將被定位目標(biāo)節(jié)點坐標(biāo)預(yù)先設(shè)置在(50,50)點。同樣地預(yù)先設(shè)置p0=-45 dB(計算過程中假設(shè)p0為未知數(shù)),路徑衰減指數(shù)β=2。調(diào)整信號強度噪聲,即調(diào)整參數(shù)δ2從0.12到12之間變化,即調(diào)整10lg(δ2)從-20 dB到 0dB之間變化,仿真測試了兩種不同計算方法下的MSE定位誤差。對每種定位算法下的MSE定位誤差仿真運行1 000次,采用1 000次運行結(jié)果的平均MSE定位誤差評價定位算法的定位精度,圖2(a)繪出了ULLS和CLLS兩種不同算法下的定位誤差隨噪聲變化關(guān)系。從圖2(a)可見,隨著20lg(δ2)的增加,即信號強度噪聲的增大,平均MSE定位誤差也隨之增大,20lg(MSE)定位誤差與信號強度噪聲20lg(δ2)之間有近似線性關(guān)系。當(dāng)信號強度噪聲等于-20 dB時,ULLS方法的定位誤差20lg(MSE)為4.5 dB,而CLLS方法的定位誤差10lg(MSE)為-12.4 dB。相比于ULLS方法,CLLS方法的定位誤差有較大減少,非常接近于定位結(jié)果的CRLB下界值。

圖2 未知發(fā)射信號強度p0下的定位結(jié)果

設(shè)定δ2為0.12,圖2(b)繪出了1 000次隨機測試下兩種不同計算方法下定位結(jié)果的累積分布函數(shù)曲線(CDF)。顯然ULLS方法的定位誤差較大,而CLLS方法能有效改進定位誤差。ULLS方法下90%定位結(jié)果MSE小于4.3 m2,而對于CLLS方法下90%的定位結(jié)果平方誤差小于0.6 m2。

4.3 不同定位算法下的定位結(jié)果比較

以優(yōu)化函數(shù)描述的最大可能性(ML)估計方法可以采用數(shù)值計算方法求解,但易于陷入局部最優(yōu),導(dǎo)致定位結(jié)果發(fā)生嚴(yán)重偏差。以LM數(shù)值算法計算式(2)所描述的優(yōu)化函數(shù),將此方法稱為ML-LM定位方法。在100 m×100 m區(qū)域內(nèi)隨機生成將6個信標(biāo)節(jié)點,將被定位目標(biāo)節(jié)點坐標(biāo)預(yù)先設(shè)置在(50,50)點。仿真運行1 000次,采用1 000次運行結(jié)果的平均MSE定位誤差評價定位算法的定位精度。調(diào)整參數(shù)δ2從0.12到12之間變化,圖3繪出了在3種不同計算方法下MSE的比較結(jié)果。由該圖可見,ML-LM計算方法的平均MSE較大,而ULLS和CLLS方法的定位結(jié)果較穩(wěn)定。通過觀察ML-LM計算方法下的定位結(jié)果,發(fā)現(xiàn)有部分結(jié)果嚴(yán)重偏離(50,50)點,歸結(jié)其原因是由于定位計算過程中陷入了局部最優(yōu)。相比于ULLS方法,CLLS方法的定位誤差都有所減少。

圖3 不同定位算法下的定位結(jié)果比較

5 結(jié)論

本文介紹了RSSI定位模型下的目標(biāo)節(jié)點位置精確定位方法,該方法以信號強度RSSI的對數(shù)衰減模型為基礎(chǔ)。提出了發(fā)射信號強度p0已知和未知兩種不同情況下的線性最小二乘ULLS和CLLS計算方法,以代數(shù)計算方法表示了目標(biāo)節(jié)點的精確位置坐標(biāo)。相比于ML-LM數(shù)值計算方法,ULLS和CLLS方法避免了數(shù)值解法中的局部最優(yōu)問題,其代數(shù)計算方法的定位結(jié)果更加穩(wěn)定,具有較好的定位精度。CLLS方法利用了向量間的相互約束關(guān)系,其定位結(jié)果非常接近于CRLB下界值。

[1] Mo Lufeng,He Yuan,Liu Yunhao,et al. Canopy Closure Estimates with GreenOrbs:Sustainable Sensing in the Forest[C]//Proceedings of the 7th International Conference on Embedded Networked Sensor Systems,SenSys 2009:99-112.

[2]Yang Zheng,Liu Yunhao. Understanding Node Localizability of Wireless Ad Hoc and Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2012,11:1249-1260.

[3]蔡紹濱,高振國,潘海為,等. 帶有罰函數(shù)的無線傳感器網(wǎng)絡(luò)粒子群定位算法[J]. 計算機研究與發(fā)展,2012,49(6):1228-1234.

[4]Zhao Jizhong,Xi Wei,He Yuan,et al. Localization of Wireless Sensor Networks in the Wild:Pursuit of Ranging Quality[J]. IEEE Transactions on Networking. 2013,12(1):311-323.

[5]Ismail Guvenc,Chia-Chin Chong. A Survey on TOA Based Wireless Localization and NLOS Mitigation Techniques[J]. IEEE Communications Surveys and Tutorials. 2009,11(3):107-124.

[6]Junyang Shen,Andreas F Molisch,Jussi Salmi. Accurate Passive Location Estimation Using TOA Measurements[J]. IEEE Transactions on Wireless Communications. 2012,11(6):2182-2192.

[7]Ho K C,Xu Wenwei. An Accurate Algebraic Solution for Moving SourceLocation Using TDOA and FDOA Measurements[J]. IEEE Transactions on Signal Processing. 2004,52(9):2453-2463.

[8]Dragos Niculescu,Badri Nath. Ad Hoc Positioning System(APS)Using AoA[C]//Proceeding of the IEEE Infocom. 2003,3:1734-1743.

[9]Zhang Shigeng,Cao Jiannong,Chen Lijun,etc. Accurate and Energy-Efficient Range-Free Localization for Mobile Sensor Networks[J]. IEEE Transactions on Mobile Computing. 2010,9(6):897-910.

[10]吳曉平,陸炳斌,沈浩. 基于RSSI定位模型的非視距關(guān)系識別方法[J]. 傳感技術(shù)學(xué)報,2013,26(11):1584-1589.

[11]Robin Wentao Ouyang,Albert Kai-Sun Wong,Chin-Tau Lea. Received Signal Strength-Based Wireless Localization via Semidefinite Programming:Noncooperative and Cooperative Schemes[J]. IEEE Transactions on Vehicular Technology,2010,59(3):1307-1318.

[12]Sheng Xiaohong,Hu Yuhen. Maximum Likelihood Multiple-Source Localization Using Acoustic Energy Measurements with Wireless Sensor Networks[J]. IEEE Transactions on Signal Processing,2005:53(1):44-53.

[13]Wang Gang,Yang Kehu. A New Approach to Sensor Node Localization Using RSS Measurements in Wireless Sensor Networks[J]. IEEE Transactions on Wireless Communications,2011,10(5):1389-1395.

[14]So H C,Lin L. Linear Least Squares Approach for Accurate Received Signal Strength Based Source Localization[J]. IEEE Transactions on Signal Processing,2011,59(8):4035-4040.

[15]Angelo Coluccia. Reduced-Bias ML-Based Estimators with Low Complexity for Self-Calibrating RSS Ranging[J]. IEEE Transactions on Wireless Communications. 2013,12(3):1220-1230.

吳曉平(1977-),男,浙江金華人,博士,研究方向為無線傳感器網(wǎng)絡(luò)與分布式計算。作為主要技術(shù)骨干完成2項國家自然科學(xué)基金,1項國家973課題。在國內(nèi)外重要會議及期刊上發(fā)表論文十多篇,其中SCI收錄3篇,wuxipu@gmail.com。

AccurateComputationApproachofRSSI-BasedLocalizationwithLinearLeastSquareMethod*

YUANXin1,WUXiaoping1,2*,WANGGuoying1,2

(1.School of Information Engineering,Zhejiang A&F University,Lin’an Zhejiang 311300,China; 2.Zhejiang Provincial Key Laboratory of Forestry Intelligent Monitoring and Information Technology,Lin’an Zhejiang 311300,China)

Based on the localization model with received signal strength indication(RSSI),an accurate localization computation approach of target node position is proposed. Transforming the nonlinear optimization function depicted by RSSI localization model as the estimation problem of linear least square method,the localization results are directly represented as algebraic solutions. The localization approaches of unconstrained linear least square(ULLS)method are proposed with known and unknown transmission power of target node. The parameters of ULLS method are further optimized,then the constrained linear least square(CLLS)method is put forward to improve the localization accuracy. The simulations demonstrate the validity of the localization computation method and test the impacts of signal strength noises on localization error. The results also show that the localization error of CLLS method is less than that of ULLS method and very close to the Cramer-Rao low bound(CRLB)of localization error.

wireless sensor networks;localization;received signal strength indication;linear least square

項目來源:國家自然科學(xué)基金重大項目(61190114);國家自然科學(xué)青年基金項目(61303236);浙江省教育廳科研項目(Y201328700);浙江農(nóng)林大學(xué)科研發(fā)展基金人才啟動項目(2013FR086)

2014-05-23修改日期:2014-08-29

10.3969/j.issn.1004-1699.2014.10.020

TP393.0

:A

:1004-1699(2014)10-1412-06