基于TW-TOA的面向合作傳感器網絡多節點定位方案

湯 巖， 聶 萌

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

基于TW-TOA的面向合作傳感器網絡多節點定位方案

湯 巖1， 聶 萌2

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

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

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

0 引 言

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

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

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

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

1 問題描述

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

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

Bj={i|anchoricancommunicatewithtargetj},

(1)

Cj={i|targeticancommunicatewithtargetj}.

(2)

(3)

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

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

在實際的場景中，假定目標節點i向另一個目標節點j發送測距請求，節點j收到并回復。如果節點i收到該回復就發送最終的數據包。在這個過程中，獲取到了2個TW-TOA的測量值。若是錨節點向目標節點發送測距請求，目標節點不僅回復測距消息，同時也要發送與其他目標節點的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，并構建目標函數，如式(8)所示

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

(8)

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

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 仿 真

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

(13)

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

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

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

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

圖1 分布式全連通的網絡下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：本次實驗考慮結構化網絡，由6個目標節點和8個錨節點構成，并且網絡是全連通狀態。

8個錨節點和6個目標節點的坐標分別為

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.

仿真結果如圖2所示。

圖2 結構化全連通的網絡下RMSE隨誤差的變化曲線Fig 2 RMSE vs error in a fully connected structured network

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

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

圖3 EDM對8個目標節點的定位(σ=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在結構化非全連通的網絡環境下的RMSE性能曲線。從圖4可知，RAND-MLE的RMSE隨σ變化波動性大。而EDM表示較高的穩定性。同圖2相比，非全連通的網絡致使RMSE性能下降。

圖4 結構化非全連通的網絡下RMSE隨誤差的變化曲線Fig 4 RMSE vs error in a nun-fully connected distributed network

3 結 論

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

[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-),女,黑龍江哈爾濱人,碩士,講師,主要研究領域為概率統計、車載網。