湯 巖， 聶 萌

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

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

湯 巖1， 聶 萌2

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

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

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

0 引 言

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

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

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

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

1 問題描述

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

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

Bj={i|anchoricancommunicatewithtargetj},

(1)

Cj={i|targeticancommunicatewithtargetj}.

(2)

(3)

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

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

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

1.1EDM描述

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

(4)

(5)

其中，ζij=4dijnij表示零均值的高斯噪聲，標(biāo)準(zhǔn)偏差為4dijσij。

(6)

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

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

(7)

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

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

(8)

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

1.2 βj的估計

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

(9)

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

(10)

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

(11)

(12)

2 仿 真

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

(13)

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

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

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

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

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

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

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

8個錨節(jié)點(diǎn)和6個目標(biāo)節(jié)點(diǎn)的坐標(biāo)分別為

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)絡(luò)下RMSE隨誤差的變化曲線Fig 2 RMSE vs error in a fully connected structured network

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

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

圖3 EDM對8個目標(biāo)節(jié)點(diǎn)的定位(σ=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)絡(luò)環(huán)境下的RMSE性能曲線。從圖4可知，RAND-MLE的RMSE隨σ變化波動性大。而EDM表示較高的穩(wěn)定性。同圖2相比，非全連通的網(wǎng)絡(luò)致使RMSE性能下降。

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

3 結(jié) 論

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

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