2007 11 Kusy B

Tracking Mobile Nodes Using RF Doppler Shifts Branislav Kusy Computer Science Department Stanford University

Akos Ledeczi, Xenofon Koutsoukos Institute for Software Integrated Systems Vanderbilt University

Tracking Mobile Objects

Problem definition: keep track of location and velocity of “cooperating” moving objects continuously over time.

Our Contributions • We propose a novel tracking algorithm that utilizes RF Doppler shifts • We develop a technique allowing us to measure RF Doppler shifts using low cost hardware • Mica2: 8MHz CPU and 9kHz sampling rate

• We evaluate our algorithm both experimentally and in simulation

Utilizing Doppler Effect • Single receiver allows us to measure relative speed.

Utilizing Doppler Effect • Multiple receivers allow us to calculate location and velocity of the tracked node.

Doppler Effect • Assume a mobile source transmits a signal with frequency f, and f’ is the frequency of received signal

f’ = f + Δf Δf = - v / λf v is relative speed of source and receiver source Jose Wudka, physics.ucr.edu

λf is wavelength of the transmitted signal

Can we Measure Doppler Shifts?

Acoustic signals Radio signals (mica2) Radio signals (telos)

Typ. freq

Dopp. Shift (@ 1 m/s)

1-5 kHz

3-15 Hz

433 MHz

1.3 Hz

2.4 GHz

8 Hz

Intriguing option: if we can utilize radio signals, no extra HW is required Solution: radio interfereometry

Measuring Doppler shift We use radio interferometry to measure Doppler frequency shifts with 0.21 Hz accuracy. 430MHz+300 Hz T

430MHz A

Si

300Hz+ Δfi,T

• 2 nodes T, A transmit sine waves @430 MHz f T, f A • Node Si receives interference signal (in stationary case) fi = fT – f A • T is moving, fi is Doppler shifted fi = fT – fA + Δfi,T

Beat frequency is estimated using the RSSI (onesignal. problem: we don’t know the

value fT-fA accurately)

Formalization We want to calculate both location and velocity of node T from the measured Doppler shifts. Unknowns: • Location, velocity of T, and fT-fA x=(x,y,vx,vy,f^) Knowns (constraints): • Locations (xi,yi) of nodes Si • Doppler shifted frequencies fi c=(f1,…,fn) Function H(x)=c: f4 = fT – fA + Δf4 = fT – fA + v4/λT

Non-linear system of equations!

Tracking as Optimization Problem Non-linear Least Squares (NLS) • Minimize objective function ||H(x) – c|| • What’s the effect of measurement errors? Experiment: • 1 mobile transmitter • 8 nodes measure fi Figure shows objective function for fixed (x,y) coordinates

Improving Accuracy State Estimation: Kalman Filter • Measurement error is Gaussian • Model dynamics of the tracked node (constant speed) • Accuracy improves, but maneuvers are a problem Experiment: • tracked node moves on a line and then turns • KF requires 6 rounds to converge back.

Resolving EKF Problems Combine Least Squares and Kalman Filter • Run standard KF algorithm • Detect maneuvers of the tracked node • Update KF state with NLS solution

Dilemma: how much to trust our measurements

Tracking Algorithm Infrastructure nodes record Doppler shifted beat frequency. Doppler shifted frequencies

Extended Kalman filter Location & Velocity

Calculate location and velocity using Kalman filter.

Maneuve r detection No

Run a simple maneuver detection algorithm.

Yes

Location & Velocity

Non-linear least squares

NLS Location & Velocity

Update EKF

Updated Location & Velocity

If maneuver is detected, calculate NLS solution and update EKF state. Show location on the screen.

Experimental Evaluation Vanderbilt football stadium • 50 x 30 m area • 9 infrastructure XSM nodes • 1 XSM mote tracked • position fix in 1.5 Non-maneuvering case seconds

14

Experimental Evaluation Vanderbilt football stadium • 50 x 30 m area • 9 infrastructure XSM nodes • 1 XSM mote tracked • position fix in 1.5 Maneuvering case seconds

Only some of the tracks are shown for clarity.

15

Conclusions • Introduced novel tracking algorithm that utilizes Doppler shift measurements only • Doppler shifts can be accurately measured using radio interferometry • Improved EKF performance in maneuvering case • Feasibility of our approach shown experimentally