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

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

(1.浙江農林大學信息工程學院,浙江 臨安 311300;2.浙江省林業智能監測與信息技術研究重點實驗室,浙江 臨安 311300)

?

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

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

(1.浙江農林大學信息工程學院,浙江 臨安 311300;2.浙江省林業智能監測與信息技術研究重點實驗室,浙江 臨安 311300)

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

無線傳感器網絡;定位;無線信號強度;線性最小二乘法

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

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

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

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

1 RSSI定位模型

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

pi=p0-10βlgdi+εi

(1)

(2)

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

2 定位結果CRLB

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

2.1 已知發射信號強度p0

當p0已知時,則矩陣F可以表示為

(3)

(4)

則根據CRLB無偏估計下界理論有

(5)

2.2 未知發射信號強度p0

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

(6)

(7)

3 線性最小二乘法定位

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

3.1 已知發射信號強度p0

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

(8)

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

(9)

(10)

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

Az=b+α

(11)

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

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

(12)

(13)

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

假設參數z的估計誤差為Δz,其值為

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

(14)

估計誤差Δz的方差為

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

(15)

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

(16)

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

Guo=h+β

(17)

根據線性最小二乘平方原理,向量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,則被定位目標節點坐標的精確估計值x為

(20)

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

3.2 未知發射信號強度p0

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

將式(9)變換為

(21)

Czρ=d+α

(22)

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

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

(23)

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

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

4 仿真分析

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

4.1 已知發射信號強度p0下的定位結果

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

圖1 已知發射信號強度p0下的定位結果

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

4.2 未知發射信號強度p0下的定位結果

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

圖2 未知發射信號強度p0下的定位結果

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

4.3 不同定位算法下的定位結果比較

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

圖3 不同定位算法下的定位結果比較

5 結論

本文介紹了RSSI定位模型下的目標節點位置精確定位方法,該方法以信號強度RSSI的對數衰減模型為基礎。提出了發射信號強度p0已知和未知兩種不同情況下的線性最小二乘ULLS和CLLS計算方法,以代數計算方法表示了目標節點的精確位置坐標。相比于ML-LM數值計算方法,ULLS和CLLS方法避免了數值解法中的局部最優問題,其代數計算方法的定位結果更加穩定,具有較好的定位精度。CLLS方法利用了向量間的相互約束關系,其定位結果非常接近于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]蔡紹濱,高振國,潘海為,等. 帶有罰函數的無線傳感器網絡粒子群定位算法[J]. 計算機研究與發展,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定位模型的非視距關系識別方法[J]. 傳感技術學報,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-),男,浙江金華人,博士,研究方向為無線傳感器網絡與分布式計算。作為主要技術骨干完成2項國家自然科學基金,1項國家973課題。在國內外重要會議及期刊上發表論文十多篇,其中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

項目來源:國家自然科學基金重大項目(61190114);國家自然科學青年基金項目(61303236);浙江省教育廳科研項目(Y201328700);浙江農林大學科研發展基金人才啟動項目(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