基于TW-TOA的面向合作傳感器網(wǎng)絡多節(jié)點定位方案

湯 巖， 聶 萌

(1.東北農(nóng)業(yè)大學 理學院，黑龍江 哈爾濱 150030；2.積成電子股份有限公司 ，山東 濟南 250100)

基于TW-TOA的面向合作傳感器網(wǎng)絡多節(jié)點定位方案

湯 巖1， 聶 萌2

(1.東北農(nóng)業(yè)大學 理學院，黑龍江 哈爾濱 150030；2.積成電子股份有限公司 ，山東 濟南 250100)

針對合作傳感器網(wǎng)絡的定位問題，提出在未知節(jié)點周轉(zhuǎn)時間 (TATs)條件下估計多個目標節(jié)點位置的方案。在該方案中，每個目標節(jié)點能與多個錨節(jié)點、其他目標節(jié)點通信，并測量它們間的雙向到達時間 (TW-TOA)值，其包括在信道終端的處理時延?；谶@些測量值，對目標節(jié)點位置和TATs進行最大似然估計 (MLE)，而這產(chǎn)生了非凸優(yōu)問題，為此，將其近似轉(zhuǎn)化為非線性最小二乘問題。最后，通過歐氏距離矩陣 (EDM)對多個目標節(jié)點位置和TATs的值進行估計。仿真結(jié)果表明：提出的方案具有良好的定位精度。在不同的場景下，提出的方案的均方根誤差逼近克萊姆—拉奧下限 (CRLB)。

合作傳感器網(wǎng)絡； 定位； 周轉(zhuǎn)時間； 雙向到達時間； 歐氏距離矩陣； 克萊姆—拉奧下限

0 引 言

無線傳感器網(wǎng)絡 (wireless sensor networks,WSNs)應用時均需要對傳感器節(jié)點進行精確的定位[1]。在噪聲測量環(huán)境中，常采用雙向到達時間 (two-way time of arrival,TW-TOA)方案進行估計節(jié)點的位置。TW-TOA要求錨節(jié)點Anchor(已知位置坐標的節(jié)點)向目標節(jié)點發(fā)送測距請求，并且目標節(jié)點收到之后進行回復。目標節(jié)點在收到請求時會產(chǎn)生反應時間，稱為周轉(zhuǎn)時間 (turn-around times，TATs)，并將其存入回復的數(shù)據(jù)包中。若不考慮目標節(jié)點的TATs，請求信號的發(fā)送和接收所經(jīng)歷的時間正比于目標節(jié)點與錨節(jié)點間的距離[2]。然而，在實際環(huán)境中，節(jié)點的TATs是不容忽略的，并且部分目標節(jié)點可能通過報告錯誤的TATs欺騙錨節(jié)點。為此，定位算法就應考慮節(jié)點的TATs。

在非合作式的傳感器網(wǎng)絡，目標節(jié)點只能與錨節(jié)點進行通信[3]。這限制了目標節(jié)點與目標節(jié)點的通信連接，為此，提出合作式定位方案。在合作式定位方案中，目標節(jié)點不僅與目標節(jié)點，還與錨節(jié)點通信。因此，不僅目標節(jié)點與錨節(jié)點間的到達時間(times-of-arrival,TOA)需要測量，而且目標節(jié)點與目標節(jié)點間的TOA也需要測量。

通過TOA測量值，建立定位方程組。在異步網(wǎng)絡中，常采用封閉式的最小二乘 (least squares,LS)估計算法對單個的目標節(jié)點進行定位。文獻[4]提出非對稱測距(asymmetric trip ranging,ATR)方案。在ATR中，錨節(jié)點不僅能與目標節(jié)點通信，而且能夠監(jiān)聽其他錨節(jié)點與目標節(jié)點的通信。文獻[5]提出了異步位置測量方案,該方案通過到達時間差(time difference of arrival，TDOA)，并采用LS算法對室內(nèi)單個的目標節(jié)點進行位置估計。文獻[6]采用聯(lián)合同步，提出廣義的LS算法估計目標節(jié)點的位置。文獻[7]針對合作網(wǎng)絡中，提出基于LS的TW-TOA和TDOA的混合算法，對節(jié)點位置和TATs的估計。然而，這些方案沒有考慮到目標節(jié)點間的TW-TOA的測量值，這些測量值可提供定位精度。

為此，針對合作網(wǎng)絡并未知TATs的環(huán)境下， 對多個目標節(jié)點進行定位方案進行研究。在未知TATs的情況下，需采用最大似然估計(maximum likelihood estimator,MLE)算法。通過MLE解決非線性、非凸優(yōu)問題。然而，通過MLE解決非凸優(yōu)問題，計算復雜，并且計算量大。因此，需將MLE問題轉(zhuǎn)為近似非線性最小二乘 (nonlinear least squares,NLS)問題。然后，再通過歐氏距離矩陣 (Euclidean distance matrix,EDM)將NLS問題轉(zhuǎn)為凸優(yōu)問題。通過這種方式，將非凸優(yōu)問題轉(zhuǎn)為凸優(yōu)問題，從而使得目標節(jié)點的TATs成為冗余參數(shù)，也就是未知TATs，不影響多個目標節(jié)點的位置估計。

1 問題描述

本節(jié)闡述通過TW-TOA測量，并未知目標節(jié)點位置和TATs的合作定位問題。

估計者需要2個TW-TOA的測量集數(shù)據(jù)：目標節(jié)點與錨節(jié)點 (target-to-anchor,T2A)、目標節(jié)點與目標節(jié)點 (target-to-target,T2T)。假定N個目標節(jié)點、M個錨節(jié)點。N個目標節(jié)點的位置sj∈Rl，且j∈S={1,2,…,N}。M個錨節(jié)點的位置αi∈Rl，且i∈A={N+1,N+2,…,N+M}。此外，定義2個節(jié)點集Bj,Cj，定義如式(1)、式(2)所示

Bj={i|anchoricancommunicatewithtargetj},

(1)

Cj={i|targeticancommunicatewithtargetj}.

(2)

(3)

其中,Tj表示目標節(jié)點j的迂回時間TATs。如果i∈Cj，則dij=‖si-sj‖；若i∈B，則dij=‖ai-sj‖。此外，nij表示獨立同分布的零均值高斯隨機變量，且標準偏差σij[1]。

依據(jù)式(3)，存在l×N+N個未知元素待估計，包括目標節(jié)點位置和迂回時間TATs分別為S=[s1,……,sN]∈Rl×N,T=[T1,…,TN]T∈RN。

在實際的場景中，假定目標節(jié)點i向另一個目標節(jié)點j發(fā)送測距請求，節(jié)點j收到并回復。如果節(jié)點i收到該回復就發(fā)送最終的數(shù)據(jù)包。在這個過程中，獲取到了2個TW-TOA的測量值。若是錨節(jié)點向目標節(jié)點發(fā)送測距請求，目標節(jié)點不僅回復測距消息，同時也要發(fā)送與其他目標節(jié)點的TW-TOA測量值。

1.1EDM描述

注意式(3)，將右邊的Tj移至等式左邊，并等式兩邊同時平方，可得式(4)

(4)

(5)

其中，ζij=4dijnij表示零均值的高斯噪聲，標準偏差為4dijσij。

(6)

如果矩陣E滿足式(7)，矩陣E屬于EDM矩陣[8,9]

Eii=0,Eij≥0,-JEJ>0.

(7)

引入變量K=[K1,…,KN]T，并構(gòu)建目標函數(shù)，如式(8)所示

subject toE∈ζ,E(A)=A,

(8)

為了解決這個問題，向目標函數(shù)添加正則項[10]改變大的Kj值，然而，該方式帶來大的計算量。另一種解決辦法：通過常量βj限定Kj的上限。βj的設定見1.2節(jié)。

1.2 βj的估計

針對Kj，需合理估計βj的值。若i∈Bj，dij=‖ai-sj‖，移除式(5)中的噪聲項ζij，可得式(9)

(9)

對式(9)進行整理[11～13]

(10)

此外，設定向量bj、矩陣Hj，致使bj=Hjyj。如果Hj為列滿秩，通過LS算法對sj,Tj進行估計，如式(11)所示

(11)

(12)

2 仿 真

本節(jié)通過VC++軟件對提出的算法進行仿真，將提出的算法記為EDM，并分析EDM性能。將均方根誤差 (root mean-square error,RMSE)作為性能指標，如式(13)

(13)

此外，為了分析位置估計的難度，針對每個噪聲方差，描繪了在已知TATs、未知TATs環(huán)境下的誤差曲線的克萊姆—拉奧下限 (Cramer-Rao lower bound,CRLB)[2]，并分別記為CRLB-Known-T,CRLB。

同時，為了提出的算法與MLE進行比較，引用Matlab軟件的庫里的函數(shù)lsqnonlin。將提出算法輸出作為該函數(shù)初始值，此算法記為EDM-MLE。若隨機初始化，記為RAND-MLE。此外，進一步地分析TATs對提出算法EDM，將已知TATs的EDM算法，記為EDM-Known-T。

在仿真過程中，TATs從[1，100]ns中隨機取值，噪聲服從獨立同分布的高斯白噪聲，且方差σij=σ∈[0.01,18]m。

1)實驗1：本次實驗考慮全連通的分布網(wǎng)絡，即所有的錨節(jié)點、目標節(jié)點均在通信范圍內(nèi)。仿真區(qū)域為[-80,80]m×[-80,80]m，8個錨節(jié)點、6個目標節(jié)點，仿真結(jié)果如圖1所示。

圖1 分布式全連通的網(wǎng)絡下RMSE隨誤差的變化曲線Fig 1 RMSE vs error in a fully connected distributed network

從圖1可知，提出的算法EDM具有較高的定位精度，遠高于RAND-MLE，略低于CRLB-Known-T。這主要是因為EDM未知TATs，導致其定位精度的下降。但是其與已知EDM-Known-T方案僅低了約1m。

2)實驗2：本次實驗考慮結(jié)構(gòu)化網(wǎng)絡，由6個目標節(jié)點和8個錨節(jié)點構(gòu)成，并且網(wǎng)絡是全連通狀態(tài)。

8個錨節(jié)點和6個目標節(jié)點的坐標分別為

ai∈{[±50,±50]T,[00,±70]T,[±70,0]T}m,

si∈{[±20,40]T,[0,±40]T,[0,0]T,[20,-40]T}m.

仿真結(jié)果如圖2所示。

圖2 結(jié)構(gòu)化全連通的網(wǎng)絡下RMSE隨誤差的變化曲線Fig 2 RMSE vs error in a fully connected structured network

如圖2所示，在結(jié)構(gòu)化全連通網(wǎng)絡下，提出的算法EDM也表現(xiàn)出良好的定位精度。從圖2可知，EDM-MLE逼近CRLB。與圖1(實驗1)不同是，RAND-MLE的RRSE近似于CRLB。這主要是因為RAND-MLE的目標函數(shù)具有唯一最小值。

3)實驗3:本次實驗針對結(jié)構(gòu)化非連通網(wǎng)絡進行仿真，并且σ=10m。圖3中三角形表示顯示錨節(jié)點，方塊表示目標節(jié)點，圓形表示提出的算法EDM對目標節(jié)點的位置估計。從圖3可知，在σ=10的情況下，提出的算法還是較準確在估計目標節(jié)點的位置。

圖3 EDM對8個目標節(jié)點的定位(σ=10 m)Fig 3 Localization of eight target nodes by EDM (σ=10 m)

圖4顯示了RAND-MLE,EDM,EDM-MLE,EDM-Known-T,CRLB和CRLB-Known-T在結(jié)構(gòu)化非全連通的網(wǎng)絡環(huán)境下的RMSE性能曲線。從圖4可知，RAND-MLE的RMSE隨σ變化波動性大。而EDM表示較高的穩(wěn)定性。同圖2相比，非全連通的網(wǎng)絡致使RMSE性能下降。

圖4 結(jié)構(gòu)化非全連通的網(wǎng)絡下RMSE隨誤差的變化曲線Fig 4 RMSE vs error in a nun-fully connected distributed network

3 結(jié) 論

針對無線傳感網(wǎng)絡的定位問題展開分析，并提出基于TW-TOA的EDM的多節(jié)點定位算法。該算法利用錨節(jié)點與目標節(jié)點間TW-TOA值，對目標節(jié)點位置和TATs進行MLE，并將MLE產(chǎn)生非凸優(yōu)問題轉(zhuǎn)為為凸優(yōu)問題，最后，利用通EDM算法估計多個目標節(jié)點位置和TATs的值。仿真結(jié)果表明：提出的定位算法能準確地估計節(jié)點位置。

[1]SahinogluZ,GezicSI,GuvencI.Ultra-widebandpositioningsytems:Theoreticallimits,rangingalgorithmsandprotocols[M].Cambridge:CambridgeUniversityPress,2008.

[2]PatwariN,HeroA,PerkinsM,etal.Relativelocationestimationinwirelesssensornetworks[J].IEEETransactionsonSignalProcessing,2013,51(8):2137-2148.

[3]CheungKW,SoHC,MaWK,etal.Aconstrainedleastsquaresapproachtomobilepositioning:Algorithmsandoptimality[C]∥EURASIPJournalonAppliedSignalProcessing,2006:1-6.

[4]WangY,MaX,LeusG.Robusttimebasedlocalizationforasynchronousnetworks[J].IEEETransactionsonSignalProcessing,2011,59(9):4397-4410.

[5]ZhouY,LawCL,GuanYL,etal.IndoorellipticallocalizationbasedonasynchronousUWBrangemeasurement[J].IEEETransactionsonSignalProcessing,2011,60(1):248-257.

[6]ZhengJ,WuYC.Jointtimesynchronizationandlocalizationofanunkownnodeinwirelesssensornetworks[J].IEEETransactionsonSignalProcessing,2010,58(3):1309-1320.

[7]GholamiMR,GeziciS,StromEG.ImprovedpositionestimationusinghybridTW-TOAandTDOAincooperativenetworks[J].IEEETransactionsonSignalProcessing,2010,60(7):3770-3785.

[8]BoydS,VandenbergheL.Convexoptimization[M].Cambridge:CambridgeUniversityPress,2004.

[9]EkimPO,GomesJ,XavierJ,etal.Robustlocalizationofnodesandtime-recursivetrackinginsensornetworksusingnoisyrangemeasurements[J].IEEETransactionsonSignalProcessing,2011,59(8):3930-3942.

[10]DattorroJ.ConvexoptimizationandEuclideandistancegeome-try[M].PaloAlto:MebooPublishers,2005.

[11]BiswasP,LiangT,TohK,etal.Semi-definiteprogrammingapproachesforsensornetworklocalizationwithnoisydistancemeasurements[J].IEEETransactionsonAutomationScienceandEngineering,2006,3(4):360-371.

[12]Oguz-EkimP,GomesJ,XavierJ,etal.ML-basedsensornetworklocalizationandtracking:Batchandtime-recursiveapproache-s[C]∥EU-SIPCO’09,Glasgow,Scotland,2009:45-52.

[13]BiswasP,LiangT,WangT,etal.Semi-definiteprogrammingbasedalgorithmsforsensornetworklocalization[J].ACMTransactionsonSensorNetworks(TOSN),2006,2(2):188-220.

[14]ZhouY,LawCL,GuanYL.LocalizationofpassivetargetbasedonUWBbackscatteringrangemeasurement[C]∥ProcofIEEEICUWB,2009:145-149.

[15]SharpI,YuK,GuoYJ.GDOPanalysisforpositioningsystemdesign[J].IEEETransonVehTechnol,2009,58(7):3371-3382.

Scheme of TW-TOA-based multiple node localization in cooperative sensor network

TANG Yan1, NIE Meng2

(1.College of Science,Northeast Agricultural University,Harbin 150030,China;2.Integrated Electronic Systems Lab Co Ltd,Jinan 250100,China)

Aiming at localization problem of cooperative sensor network,propose scheme to estimate multiple nodes positions in the presence of unknown turn-around times(TATs).In the adopted scheme,each target node can communicate with several anchor nodes and other target nodes,and two-way times-of-arrival between them are measured,which includes processing delays at both channel endpoints.The maximum likelihood estimates (MLE) of positions of target node and turn-around times(TATs) is carried out based on those measurement value,which generate non-convex optimization problem,it is approximated transform to nonlinear least squares problem.Finally,positions and TATs of multiple target nodes are estimated jointly by solving Euclidean distance matrix.Simulation result show that the proposed method has good localization precision,under different scenes,RMSE of the proposed scheme approach the Cramer-Rao lower bound (CRLB).

cooperative sensor network; localization; turn-around times(TATs); two-way times-of-arrival(TW-ToA); Euclidean distance matrix(EDM); Cramer-Rao lower bound(CRLB)

10.13873/J.1000—9787(2014)08—0127—04

2014—05—15

TP 393

A

1000—9787(2014)08—0127—04

湯 巖(1979-),女,黑龍江哈爾濱人,碩士,講師,主要研究領域為概率統(tǒng)計、車載網(wǎng)。