JOINTLOCALIZATION ANDCLOCKSYNCHRONIZATIONFOR WIRELESS SENSOR NETWORKS Sundeep PrabhakarChepuri,Geert Leus, andAlle-Janvan der Veen Faculty ofElectrical Engineering,MathematicsandComputerScience DelftUniversityofTechnology,2628CD Delft, TheNetherlands E-mail: [email protected],[email protected],[email protected]. 3 1 0 ABSTRACT metricaltime-stampingandpassivelistening(ATPL)protocol 2 wasproposedin[5]forjointclocksynchronizationandrang- A fully-asynchronousnetwork with one target sensor and a n ing. Subsequently, the estimated pairwise distances can be fewanchors(nodeswithknownlocations)isconsidered.Lo- a usedasaninputtotheleast-squares(LS)basedrange-squared J calizationandsynchronizationaretraditionallytreatedastwo separate problems. In this paper, localization and synchro- methodforlocalization. Jointestimationofthepositionand 4 theclockparametersofasensorbasedonthetwo-waytime- nization is studied under a unified framework. We present stamp exchange protocol has been considered in [6], where ] a new model in which time-stamps obtained either via two- T ansynchronousnetworkisconsideredwhereonlythesensor way communication between the nodes or with a broadcast I nodesuffersfromclock-skewsandclock-offsetsandthe an- . based protocol can be used in a simple estimator based on s chors are assumed to be synchronized. In [7], localization c least-squares(LS) to jointly estimate the position of the tar- [ getnode as well as all the unknownclock-skewsand clock- ofthesensornodeinafully-asynchronousnetworkhasbeen offsets. TheCrame´r-Raolowerbound(CRLB)isderivedfor studied,wherethemainfocusisonlocalizationbutalsocer- 1 tain approximations of the clock parameters are required to v theconsideredproblemandisusedasabenchmarktoanalyze solvetheproblem. 2 theperformanceoftheproposedestimator. 0 In this paper, we again consider fully-asynchronousnet- 7 IndexTerms— Clocksynchronization,clock-skew,clock- workconsistingofonesensoranda fewanchors,andinves- 0 offset,localization,wirelesssensornetworks. tigatelocalizationandclocksynchronizationundera unified . 1 framework.Weproposealineardatamodelforjointlocaliza- 0 1. INTRODUCTION tionandclocksynchronization. Thedatamodelisgenericin 3 thesensethatitcanbeusedwitheitherthetwo-wayranging 1 Localization and clock synchronizationare two key compo- protocol or the ATPL protocol. This is used in an estima- : v nents of any self-organizing location-aware wireless sensor torbasedonLStojointlyestimatethepositionofthesensor Xi network(WSN).AWSNenablesdistributedinformationpro- nodeandalltheunknownclock-skewsandclock-offsets.The cessingtaskslikedatasampling,informationfusion,andother Crame´r-RaoLowerBound(CRLB)isderivedfortheconsid- r a time-based tasks [1]. Every node in the network has an au- eredproblemandisusedasabenchmarktoanalyzetheper- tonomousclock.TheseindividualclocksinaWSNdriftfrom formanceoftheproposedestimators. each other due to imperfections in the oscillator, aging and Notation: otherenvironmentalvariations.Itisessentialtocalibratethese Upper(lower)boldfacelettersareusedformatrices(column imperfections from time to time to achieve a network-wide vectors);(·)T denotestransposition;⊙(⊘)referstoelement- timecoherence. Aplethoraofalgorithmsforclocksynchro- wise matrix or vector product (division); (.)⊙2 denotes the nization can be found in [2]. For the data to be meaning- element-wisematrixorvectorsquaring;bdiag(.)ablockdi- ful,thelocationwherethedataisacquiredisoftenrequired. agonalmatrixwith the matricesin its argumenton the main Computingthelocationofthenodesis commonlycalledlo- diagonal;1 (0 )denotestheN ×1vectorofones(zeros); N N calization,andisawell-studiedtopic[3]. I isanidentitymatrixofsizeN;E(.)denotestheexpecta- N Even though localization and clock synchronization are tionoperation;⊗istheKroneckerproduct. tightly coupled, traditionally they are treated as two sepa- rate problems. Recently, foran anchorlessand a fullyasyn- chronousnetwork,agloballeast-squares(GLS)estimatorbased 2. NETWORKMODEL on a two-way time-stamp exchange protocol for joint clock synchronization and ranging has been proposed in [4]. Ex- We consider a fully-asynchronousnetwork with M anchors ploitingthebroadcastnatureofthewirelessmedium,anasym- andonesensor(node0)asshowninFig.1. We assumeone θ∈R11×1 A∈R3K×11 n∈R9×1 c z }|0 { z t01 1K −t10 −1K 0K 0}|K 0K 0K e10 0K 0K { c1 zn}0|1{ (5)  t02 1K 0K 0K −t20 −1K 0K 0K 0K e02 0K  c2 = n02 .  t03 1K 0K 0K 0K 0K −t30 −1K 0K 0K e03  c3 n03 τ0 A∈R3K×9 θ∈R9×1 t∈R3K×1 n∈R9×1 c z ttt000321 111KKK −00tKK10 −001KKK −0}0t|KK20 −001KKK e001KK0 e000KK2 e000KK3 { zτcc}012|0{ =−z −00tKK30 }−|001KKK c3{ + znnn}000|123{ . (6) nodeM 3. PROBLEMFORMULATION node3 (cM=[1,0]T,xM) (c3?,x3) Inthispaper,wefocusonthetwo-waycommunicationproto- Sensor node2 colforderivingthedatamodel. Thetransmissionandrecep- Anchor tiontime-stampsarerecordedindependentlyatlocaltimeco- (c2?,x2) ordinatesbothduringtheforwardandthereverselinks. The (c0n?,oxd0e?0) time-stamp recorded at the ith node when the kth iteration (c1?,x1n)ode1 messagedepartstothejthnodeisdenotedbyTi(jk),andupon arrivalofthecorrespondingmessage,thejthnoderecordsthe Fig. 1: An illustration of the network model, together with time-stampT(k).Forthesakeofgenerality,wedonotputany theknowandunknownparameters. Lightshadedlinesrefer ji constraintsonthesequenceofforwardlinksandreverselinks tothepassivelisteninglinks. orthenumberoftime-stampsrecorded[4,5]. The time-of-flightfor a line-of-sight(LOS) transmission ofthenodeshasarelativelystableclockoscillatorandisused betweentheithnodeandthejthnodecanbedefinedasτ = as a clock reference. All the other nodessuffer from clock- ij ν−1d , where ν denotes the speed of a wave in a medium. skewsandclock-offsets.Thenetworkmodelconsideredhere ij Using(2),τ canbewrittenintermsofthelocalclockcoor- isthesameasthemodelconsideredin[5]. ij dinatesas Allthenodesaredistributedoveranl-dimensionalspace, with l = 2 (plane) or l = 3 (3-D space). Let the vector τ =(α T(k)+β )−(α T(k)+β )+n(k) (4) x ∈ Rl×1 denote the coordinatesof the ith node. The co- ij j ji j i ij i ij i ordinates of all the anchors are collected in a matrix X = [x ,x ,...,x ] ∈ Rl×M. Theunknowncoordinatesofthe where n(ijk) denotes the aggregate measurementerror on the 1 2 M time-stamps. sensorarecollectedinx . Thedistancebetweentheithnode 0 InallthereareK time-stampsrecordedateachnodeand andthejthnodeisdenotedby thetime-stampsrecordedattheithnodearecollectedint = ij dij =dji =kxi−xjk2 = kxik2−2xTi xj +kxjk2 [Ti(j1),Ti(j2),...,Ti(jK)]T ∈ RK×1. Thedirection(forwardor q (1) reverse)ofthekthlinkisdenotedbye(k),wheree(k) =1for ij ij Letti bethelocaltimeattheithnodeandtbetherefer- transmissionfromnodeitonodej ande(k) = −1fortrans- encetime.Wethenassumethattherelationbetweenthelocal ij missionfromnodej to nodei. The directioninformationis timeandthereferencetimecanbegivenbyafirst-orderaffine collected in a vector e = [e(1),e(2),...,e(K)]T ∈ RK×1. clockmodel[4], ij ij ij ij Theerrorvectorisdenotedbyn =[n(1),n(2),...,n(K)]T ∈ ij ij ij ij ti =ωit+φi ⇔ t=αiti+βi (2) RK×1. whereω ∈R istheclock-skew,φ ∈Ristheclock-offset, Forthesakeofexposition,weconsidertheexampleofa i + i α =ω−1andβ =−ω−1φ arethesynchronizationparame- networkwith M = 3 anchorsand one sensor (node0) with i i i i i a of two-way communication protocol between each of the tersoftheithnode.Withoutlossofgenerality,weuseanchor sensor-anchorpairs. Lettheclockparameterscorresponding M as absolute time reference, i.e., [ω ,φ ] = [1,0]. The M M unknown synchronization parameters are collected in α = to the ith node be collected in a vector ci = [αi,βi] and [α0,α1,...,αM−1]T andβ =[β0,β1,...,βM−1]T.Theun- τ0 = [τ0,1,τ0,2,...,τ0,M]T ∈ RM×1. The pairwise dis- known clock-skews and clock-offsets are respectively given tances of the sensor to each anchor will be d0 = ντ0. We by can now write (4) for all the K time-stamps collected in a ω =1 ⊘α and φ=−β⊘α. (3) matrix-vector form shown in (5) on top of this page. Mov- M ingtheknowncolumnscorrespondingtoc = [1,0]T (clock Nodes in the network can communicate with each other 3 reference) to one side, we can re-write (5) shown in (6) on eitherviaatwo-waycommunicationprotocol[4]oranATPL topofthispage. Thegeneralizationof(6)foranyM > 2is protocol[5]asillustratedinFig.1. straightforward. usingLSasfollows IncaseweadoptthebroadcastbasedATPLprotocol,the matrixAwillhaveadditionalrowscorrespondingtothepas- pˆ =(X¯TX¯)−1X¯T(dˆ ⊙dˆ −q) (10) 0 0 sive listening links [5]. The detailed derivationof the linear provided M ≥ l + 1 such that the matrix X¯ is tall. The datamodelfortheATPLprotocolcanbefoundin[5]. anchor positions can be designed such that the matrix X¯ is Thegeneralizedlinearmodelforeitherthetwo-waycom- left-invertible. municationorATPLprotocolcanbewrittenas 5. THEJOINTESTIMATOR Aθ =t+n (7) whereA ∈ RKM×3M, θ ∈ R3M×1, t ∈ RKM×1, andn ∈ Althoughclocksynchronizationandlocalizationproblemsare RKM×1 with the structures detailed in (6) for the two-way tightlycoupled,theyhaveanon-linearrelationascanbeseen communicationprotocolorin[5]fortheATPLprotocol. in(9).Incasewewanttolocalizethesensorandalsoestimate The aim of this work is to estimate the position x of alltheunknownclockparametersinonelinearstep,wehave 0 thetargetnodealongwithalltheunknownclockparameters. tolinearizetherelationbetweentheclockparametersandthe Thepositionofthetargetnodex canbecomputedusingthe position. 0 rangeestimatesobtainedbysolving(7). Thisispresentedas In orderto do such a jointlocalization and synchroniza- atwo-stepapproachinthenextsection,whereinthefirststep tion,weexploitthelinearrelationbetweentherange-squared we estimate the unknownclockparametersandthe pairwise measurements and the coordinates of the sensor. Instead of distancesofthesensortoeachanchor,andusethisestimated squaringthe estimated pairwise distancesin the second step pairwisedistancestocomputethepositionofthetargetnode as in Section 4.2, we linearize the problem by squaring the in the second step. Alternatively, we can formulate a single linear modelin (7), and this is the main contributionof this estimationproblemtojointlycomputethepositionofthetar- paper.Aunifiedframeworkforlocalizationandsynchroniza- getnodeaswellasalltheunknownclockparametersandthis tionisessentialforapplicationsinWSNssuchasjointtrack- isthemaincontributionofthispaper. ingofthepositionandtheclock-parameters,fore.g.,usinga standardKalmanfilter. 4. TWO-STEPAPPROACH Hadamardsquaringthedatamodelin(7)wouldresultin alinearmodelandisgivenby In the two-step approach,we first solve for all the unknown clockparametersand the pairwise distancesof the sensor to (Aθ)⊙(Aθ)=(t+n)⊙(t+n) (11) eachanchorandthenusetherangeestimatesinaLSestimator andcanbefurthersimplifiedto tocomputethelocation. 4.1. Jointsynchronizationandranging:stepI (AT ◦AT)T(θ⊗θ)=(t+n)⊙(t+n) (12) For K ≥ 3, matrix A is tall and left-invertible. Hence, the The linear modelin (12) doesnot have a uniquesolution as unknownparametersinθcanbeestimatedusingLS,i.e., thesystemmatrix(AT◦AT)T isaKM×9M2matrixwhich θˆ =(ATA)−1ATt. (8) isgenerallyfatandthusnotleft-invertible.However,thiscan besolvedwithcertainapproximationsoftheclockparameters Subsequently,theclock-skewsω,clock-offsetsφcanbeob- asin[7]. tainedusingtherelationin(3),andthepairwisedistancesof An alternative approach to linearizing the problem is by thesensortoeachanchorusingtherelationdˆ =ντˆ . 0 0 takingtheKroneckorproductofthemeasurements,i.e., 4.2. Localizationfromestimatedpairwisedistances:stepII (Aθ)⊗(Aθ)=(t+n)⊗(t+n). (13) Pairwisedistancesformamajorinputtoanylocalizationscheme. Usingthepairwisedistanceestimatesobtainedin(8),theco- UsingthematrixpropertyPC⊗QE = (P⊗Q)(C⊗E), ordinates of the sensor node can be estimated using range- wecanfurthersimplify(13)tothefollowinglinearmodel squaredlocalizationalgorithms. Letusdefineavectorq=[kx1k2,kx2k2,...,kxMk2]T ∈ A¯ θ¯ RM×1. Using (1), we can writethe pairwise distanceof the (A⊗A)(θ⊗θ)=(t+n)⊗(t+n) sensortoeachanchorinavectorformas z }| {z }| { (14) ¯t w d0⊙d0 =q−2XTx0+kx0k21M =t⊗t+n⊗n+t⊗n+n⊗t (9) =X¯p+q, z}|{ z }| { whereA¯ ∈ RK2M2×9M2,andw ∈ RK2M2×1 isthenewer- wherep=[xT,kx k2]T andX¯ =[−2XT,1 ]∈RM×(l+1). rorvector.IfthematrixAisfullcolumn-rank,thenitfollows 0 0 M Subsequently,thecoordinatesofthesensorcanbeestimated thatthematrixA¯ isalsofullcolumn-rank. Wenowintroducetwonewvariablestoresolvetheclock unbiasedestimatorϕˆ¯ itfollowsfromtheCRLBtheoremthat parameters without ambiguity after the squaring operation. E(ψˆ¯ψˆ¯T) ≥ F−1 where F is the Fisher informationmatrix. Fortheithnode,wedefinethevariables If the error vector n is Gaussian distributed with a variance σ2,thenFcanbecomputedasF=σ−2JTJ,whereJisthe γ ,α2 and δ ,α β , (15) i i i i i Jacobianmatrixgivenby and collect parameters corresponding to the ith node in the ∂(Aθ−t) vector ¯ci = [γi,δi]T. The clock-skew ωi ∈ R+ is always J= ∂ϕ¯ =[Jω Jφ Jx0]∈RKM×(2M+l) positiveandtheclock-offsetφ ∈ Rcanbeeitherpositiveor i (21) negative. Asaresult,recoveringclock-offsetsfromβ2 with- i withsub-blocks outambiguitieswouldbedifficult.Hence,wemakeuseofthe cross-termδi = αiβi torecovertheclock-offset. Forallthe Jω =−A(Sα−Sβ⊙1KMφT)⊘(1KMωT)⊙2, nodesinthenetworkwehave¯c=[¯cT0,¯cT1,¯cT2,...,¯cTM−1]T. Jφ =−ASβ⊘1KMωT, (22) Ltheeteunstdrieefisnoefaθ¯p,esrumchuttahtaiotnΠmθ¯at=rix[¯cΠT,∈τ⊙R29TM,2z×T9]MT.2Htheartes,otrhtes Jx0 =ν−1TSτ0D, 0 seinsttrioefstohfethneuivseacntcoerpza∈ramReLtze×rs1ewxictlhuLdizng=c¯9aMnd2τ−⊙32Mfr,ocmonθ¯- wcohleurmenSsαo,fSAβ,caonrrdesSpτo0ndairnegsteoleαct,ioβn,manadtriτces, rtoesspeelcetcivtetlhye. 0 0 andisoflessinterest. TheM ×lderivativematrixDisdefinedas Wecannowre-write(14)asfollows A¯ΠT(S¯cc¯+ν−2Sdd⊙02+Szz)=¯t+w (16) [D]i,j =(cid:20)∂∂dx00(cid:21)i,j = [kxx0]0j−−x[xiki2]j (23) where S¯c, Sd, and S¯z are the selection matrices to select columns of A¯ΠT corresponding to c¯, d⊙2, and z, respec- 7. NUMERICALEXAMPLE 0 tively.Substituting(9)in(16),weget Anetworkwithonetargetsensorand5anchorsisconsidered. A¯ΠT(S¯c¯c+ν−2SdX¯ap+Szz)=¯t−A¯ΠTν−2Sdq+w. Boththetargetnodeandanchornodesaredeployedrandomly (17) withinarangeof100m.Theclock-skewsωandclock-offsets Wenextcollecttheunknownsinthevectorψ =[¯cT,pT,zT]T φ are uniformly distributed in the range [1 −100ppm,1+ ∈ RL×1 whereL = 2M +l+1+Lz andthecolumnscor- 100ppm] and[−1s,1s],respectively. We use anobservation respondingtotheunknownsinthematrix interval of 100s during which the clock parameters are as- A˜ =[A¯ΠTS¯c,ν−2A¯ΠTSdX¯,A¯ΠTSz]∈RK2M2×L, stiummee-dstatombpes.fiTxheed.erWroeruvseectνor=is3a0s0summ/esdatnodbreeGcoarudssKian=d1is0- (18) andthemeasurementsinthevector˜t=¯t−ν−2A¯ΠTSdq∈ tributed with a variance σ2. The simulations are averaged RK2M2×1. over1000independentMonteCarloexperiments. The generalized linear model for joint localization and synchronizationisthengivenby 100 2−step (two−way) A˜ψ =˜t+w (19) Joint estimator (two−way) RCRB (two−way) 2−step (ATPL) TheunknownparametersinϕcanbeestimatedusingLS,i.e., 10−1 JRoCinRt LeBs t(imATaPtoLr) (ATPL) m] ψˆ =(A˜TA˜)−1A˜T˜t. (20) E ( x) [0 S M Hence, theunknownpositionx is obtainedbysolving(20) R 0 10−2 and the unknown clock-skews and clock-offsets can be ob- tainedusing(15)and(3)withoutanyambiguities. Alternatively, a weighted least-squares (WLS) estimator insteadof(10)takingtheestimationerrorin(8)oraWLSes- 10−130 −6 10−7 10−8 10−9 σ2 [s] timatorinsteadof(20)pre-whiteningthenoisewispossible. However,thisisnotfurtherdetailedinthispaper. Fig.2:RMSEoftheestimatedsensorcoordinates. 6. CRAME´R-RAOLOWERBOUND Inthispaper,weanalyzetheperformanceoftheproposed estimatorsintermsoftherootmeansquareerror(RMSE)of We now derive the CRLB for jointly estimating the clock- theestimatedsensorposition,clock-skews,andclock-offsets skewsω,theclock-offsetsφ,andthecoordinatesofthesen- fordifferentvaluesofσ2. We providetheresultsfora)two- sor node x , i.e., ψ¯ = [ωT,φT,xT]T based on (7). For an waycommunicationprotocol[4]b)ATPLprotocol[5]. 0 0 10−4 parametersandthepositionwhichisanimportantapplication inaWSN. 10−5 8. CONCLUSIONS ω ) 2−step (two−way) E ( joint estimator (two−way) We have considered a fully-asynchronousnetwork with one S RCRB (two−way) M R 2−step (ATPL) sensor and a few anchors. In this paper, we have addressed 10−6 joint estimator (ATPL) RCRLB (ATPL) a problem in which we estimate all the unknown clock pa- rameters as well as the position of the target node. Loca- tion of the node can be estimated with a two-step approach 10−170 −6 10−7 10−8 10−9 using the range estimates. To avoid this two-step approach, σ2 [s] we have proposed a generic linear data model for joint lo- calizationandclocksynchronization. Anestimatorbasedon Fig.3:RMSEoftheestimatedclock-skews. LSto jointly estimate the positionofthe targetsensor node, alongwithalltheunknownclock-skewsandclock-offsetshas 10−2 beenpresented. Theproposedestimatorforclock-skewsand 2−step (two−way) joint estimator (two−way) clock-offsetsisasymptoticallyefficientandmeetstheCRLB, RCRB (two−way) 2−step (ATPL) however,thepositionestimatesdonotasymptoticallyachieve 10−3 jRoCinRt eLsBt i(mAaTtPorL )(ATPL) theCRLB. φE ( ) [s]10−4 9. REFERENCES S M R [1] N.M. Freris, H. Kowshik, and P. R. Kumar, “Funda- 10−5 mentalsoflargesensornetworks:Connectivity,capacity, clocks,andcomputation,” Proc.oftheIEEE,vol.98,no. 101−60 −6 10−7 10−8 10−9 11,pp.1828–1846,nov.2010. σ2 [s] [2] Yik-ChungWu, Q. Chaudhari,andE.Serpedin, “Clock Fig.4: RMSEoftheestimatedclock-offsets. synchronizationofwirelesssensornetworks,” IEEESig- nalProcess.Mag.,vol.28,no.1,pp.124–138,jan.2011. Fig. 2showstheRMSE oftheestimatedsensorposition [3] F. Gustafsson and F. Gunnarsson, “Mobile positioning computedusing a) the two-step approach, i.e., LS estimator using wireless networks: possibilities and fundamental (10) with the range estimates of (8) as the input, and b) the limitationsbasedonavailablewirelessnetworkmeasure- proposed joint estimator. The root CRLB (RCRLB) is also ments,” IEEESignalProcess.Mag.,vol.22,no.4,pp.41 providedfor both the considered protocols. The ATPL pro- –53,july2005. tocol performsbetter than the two-way communicationpro- [4] R. T. Rajan and A.-J. van der Veen, “Joint rangingand tocoldue to the additionalpassive listening links [5]. How- clock synchronizationfor a wireless network,” in Proc. ever,boththeestimatorsforlocalizationareinaccurateasthe 4thIEEEInternationalWorkshoponComputationalAd- dependencies with the nuisance parameters are not consid- vancesinMulti-SensorAdaptiveProcessing(CAMSAP), ered,andthiscanberesolvedusingaconstrainedWLSsolu- dec.2011,pp.297–300. tions[7]. Fig. 3andFig. 4showtheRMSEoftheestimatedclock- [5] S.P.Chepuri,R.Rajan,G.Leus,andA.-J.vanderVeen, skewsandclock-offsets. TheATPLprotocolagainperforms “Jointclocksynchronizationandranging: Asymmetrical better than the two-way communication protocol. In addi- time-stampingand passivelistening,” IEEESignalPro- tion,boththeestimatorsforclock-skewsandclock-offsetsare cess.Lett.,vol.20,no.1,jan2013. asymptoticallyefficient,andmeettheCRLB. [6] JunZhengandYik-ChungWu, “Jointtimesynchroniza- Thelocationofthetargetnodecanbeobtainedwithatwo- tionandlocalizationofanunknownnodeinwirelesssen- step approachusing the range estimates obtained from joint sornetworks,” IEEETrans.SignalProcess.,vol.58,no. synchronizationandranging.Alternatively,wecanformulate 3,pp.1309–1320,march2010. localization and synchronization under a unified framework as a single linear problem. However, this results in a larger [7] YiyinWang,XiaoliMa,andG.Leus,“Robusttime-based systemtosolveandiscomputationallylessattractivethanthe localization for asynchronous networks,” IEEE Trans. two-stepapproach.Thelinearmodelofthejointsynchroniza- Signal Process., vol. 59, no. 9, pp. 4397 –4410, sept. tionandlocalizationcanbeusedforjointtrackingoftheclock 2011.