Transcript Spatio-temporal sensing in WSNs

Institute for Software Integrated Systems
Vanderbilt University
Shooter Localization
with
Wireless Sensor Networks
Akos Ledeczi
Associate Professor
[email protected]
Evolution
 Many single-channel acoustic sensors
 2003-2005
 Designed for urban operation:


Multipath elimination
Multiple simultaneous shot resolution
 1-meter 3D accuracy within network
 No classification
 DARPA NEST Program
 Few multi-channel acoustic sensors






2005-2006
Helmet-mounted, 4-channel acoustic sensor node
Single sensor operation: localization
Networked operation: trajectory and caliber estimation and weapon classification
1-degree bearing accuracy
DARPA ASSIST Program
 Few single-channel acoustic sensors





2010Mobile phone-based system
Single sensor operation: miss distance and range estimation*
Networked operation: trajectory and caliber estimation and weapon classification
DARPA Transformative Applications Program
Copyright © 2004-2011, Vanderbilt University
2
Wireless Sensor Network-Based
Countersniper System
Copyright © 2004-2011, Vanderbilt University
3
RITS: Routing Integrated Time Synch
 reactive protocol, synchronizes after the event was registered (postfacto)
 maintains the age of event instead of the global time and computes
the local time of event at the data fusion node
 power efficient, virtually no communication overhead, can be highly
accurate
Tevent
time
node1
average time synchronization error histogram
Δt1
30%
time
percentage
25%
node2
20%
Δt2
15%
time
10%
Δt3
node3
5%
0%
0
2
3
5
6
8
10
11
13
time
synchronization error (microseconds)
- ~50 node experiment
- 4.4 μs average error, 74 μs maximum error
in the test of 200 rounds
sink
Δt1 + Δt2 + Δt3
sink
Copyright © 2004-2011, Vanderbilt University
Troot
Tevent = Troot - Δt1 - Δt2 - Δt3
4
Sensor Fusion
Shot #1 @ (x1,y1,T1)
t3
d3
Shot #2 @ (x2,y2,T2)
f(x,y)
t1
d1
?
Echo #1 @ (x3,y3,T1)
d4
t4
d2
t2
t3 – d3/v
t4 – d4/v
t2 – d2/v
sliding window
time
3
Shot time estimate T
t1 – d1/v
0
1
f(x,y) = [max number of ticks in window] = 3
Copyright © 2004-2011, Vanderbilt University
5
Experiments at McKenna MOUT site at
Ft. Benning
 Sep 2003: Baseline system
 Apr 2004: Multishot resolution
B1
NORTH
Church
 60 motes covered a 100x40m area
 Network diameter: ~7 hops
 Used blanks and Short Range Training
Ammunition (SRTA)
 Hundreds of shots fired from ~40 different
locations
 Single shooter, operating in semiautomatic and
burst mode in 2003
 Up to four shooters and up to 10 shots per
second in 2004
 M-16, M-4, no sniper rifle
 Variety of shooter locations (bell tower, inside
buildings/windows, behind mailbox, behind car,
…) chosen to absorb acoustic energy, have limited
line of sight on sensor networks
 1 meter average 3D accuracy (0.6m in 2D)
 Hand placed motes on surveyed points (sensor
localization accuracy: ~ 0.3m)
Copyright © 2004-2011, Vanderbilt University
6
2.5D Display, Single shot
Red circle:
 Shooter position
White dot:
 Sensor node
Small blue dot:
 Sensor Node that
detected current shot
Cyan circle:
 Sensor Node whose
data was used in
localization
Yellow Area:
 Uncertainty
Copyright © 2004-2011, Vanderbilt University
7
2.5D Display, Multiple Shots
Red circle:
 Shooter position
White dot:
 Sensor node
Small blue dot:
 Sensor Node that
detected current shot
Cyan circle:
 Sensor Node whose
data was used in
localization
Yellow Area:
 Uncertainty
Copyright © 2004-2011, Vanderbilt University
8
Shooter Localization
VIDEO
Copyright © 2004-2011, Vanderbilt University
9
Soldier-Wearable Shooter Localization System
DARPA IPTO ASSIST
3-axis compass
Optional
laptop display
Microphones
Zigbee
&
Bluetooth
Bluetooth
PDA display
Zigbee
Muzzle blast
Shockwave
Zigbee
Copyright © 2004-2011, Vanderbilt University
Bluetooth
Acoustic Sensor Board
 Detect TOA and AOA of ballistic shockwave and
muzzle blast using a single board
 Acoustic sensor board:
 4 acoustic channels w/ high-speed AD converters
 FPGA for signal processing
 3-axis digital compass
 Bluetooth
 MicaZ connectivity
Copyright © 2004-2011, Vanderbilt University
11
Software Architecture
 PC/PDA (Java/Ewe)
 User interface
 Local/central sensor fusion
 Location information from
external GPS
 Sensor Board (VHDL/assembly)
 Custom DSP IP cores (detection)
 Soft processor macros (digital
compass, debug & test interface)
 Communication bridge
 Shared memory paradigm
 Mote (nesC/TinyOS):
 Data sharing across nodes
 Time synchronization
 Application Configuration &
Management (from a central
point)
Copyright © 2004-2011, Vanderbilt University
12
Single Sensor Results
 Independent evaluation by NIST at
Aberdeen in 2006
 Localization rate for single sensors:
 range < 150m: 42%
 Range < 80m: 61%
 Percentage of shots not localized by
at least one single sensor alone
(range < 150m): 13%
 Accuracy:
 0.9 degree in azimuth
 5 m in range
Blue dots: sensors
Black squares: targets
Black line: trajectory estimate
Black dot: shooter position estimate
White arrows: single sensor shooter estimates
Copyright © 2004-2011, Vanderbilt University
13
Sensor Fusion
 Localization: Single sensor: simple
analytical formula to compute shooter
location based on Time of Arrival (ToA)
and Angle of Arrival (AoA) of both
shockwave and muzzle blast.
 Localization: Multi-sensor: all available
detections are utilized in a
multiresolution search of a discrete
multi-dimensional consistency function.
Consistency function specifies how
many observations agree on a given
point in space and time.
 Online caliber estimation based on
measured ballistic shockwave length
and miss distance given by the
computed trajectory estimate.
 Online weapon classification based on
estimated caliber and muzzle velocity
that is computed using the projectile
velocity over the sensor web and the
estimated range.
Copyright © 2004-2011, Vanderbilt University
14
Multi-Sensor Results
Localization Results
 Independent evaluation by NIST at
Aberdeen in 2006
 Shots between 50 and 300m w/ 6
different weapons (3 calibers)
 Trajectory was highly accurate
 Big range error at >200m was due to
a bug in the muzzle blast detection
 Caliber estimation was almost
perfect (rates are relative to
localized shots, not all shots).
Classification Results
Sensors located on surveyed points with small position error.
Manual orientation and then automatic calibration used. No mobility.
 Classification for 4 out of 6 six
weapons were excellent
 At longer ranges it started to
degrade as it needs range estimate,
i.e. muzzle blast detections
 M4 and M249 was too similar to
each other and the test was the first
time the system encountered these
weapons
15
Copyright © 2004-2011, Vanderbilt University
Test in Georgia in 2009
VIDEO
Copyright © 2004-2011, Vanderbilt University
16
Motivation for New Approach
 Traditional WSN approach:
 Many single channel sensors distributed in the
environment
 Too many nodes needed
 Wearable sensor approach:
 Few multi-channel sensors
 Needs to track self-orientation: Hard!
What can be done with a few single-channel sensors?
Copyright © 2004-2011, Vanderbilt University
17
SOLOMON: Shooter Localization with Mobile Phones
DARPA Transformative Apps Program


Phone
Network

Muzzle blast

Shockwave
Phone
Network
Copyright © 2004-2011, Vanderbilt University
Accurate miss distance estimation
using a single microphone (i.e.
phone) by measuring the
shockwave length. Estimated
accuracy: 1-2m.
Accurate range estimation using a
single microphone (i.e. phone)
utilizing the miss distance and the
TDOA of the shockwave and the
muzzle blast: Estimated accuracy:
5%.
Novel consistency function-based
sensor fusion technique enables
localization of shooter with as few
as 5 phones even in the presence
of GPS and other errors.
Custom headset will provide better
performance offloading the
computationally intensive
operations from the phone
increasing battery life.
18
Miss Distance Estimation in Standalone
Operation
Relation between shockwave length (N-wave duration in the time
domain) and miss distance [Whitham52]:
T: shockwave length
M: Mach speed of the bullet
b: miss distance
c: speed of sound
d: bullet caliber
l: bullet length
Miss distance can be computed from the shockwave length, with
assumptions on the weapon (caliber, length and speed of bullet):
b: miss distance
T: shockwave length
k: weapon coefficient
Using 168 shockwave detections of AK-47 shots fired from 50 to 130m
from sensors, with miss distances ranging from 0 to 28m, the average
absolute miss distance error is 1m.
Copyright © 2004-2011, Vanderbilt University
19
Range Estimation in Standalone Operation
Range can be calculated using the miss distance, a
projectile speed and the TDOA of the shockwave and the
muzzle blast.
SM:
QM:
P:
SP:
PM:
α:
range
miss distance
origin of shockwave heard at M
at the speed of bullet
at the speed of sound
shockwave cone angle
Phone
Shooter
Using 168 AK-47 shot detections from ranges between 50 and
130 m gathered at Aberdeen in 2006 the average range
estimate has ~5% error.
Copyright © 2004-2011, Vanderbilt University
20
Custom Headset





High quality application-specific microphone with higher maximum sound pressure and faster recovery
(Knowles VEK-H-30108)
Higher sampling rate for better shockwave length and miss distance estimation
Off-loading the signal processing algorithm from the phone using a low-power ARM-Cortex
microcontroller
 real-time signal processing with lower jitter and latency
 better performance/power ratio
Wired and/or wireless phone interface supporting any Android handset device
 Bluetooth interface with Android 2.0 and later
 Analog signaling on the headset audio interface using software modems on both sides
Integrated temperature sensor for more accurate speed of sound estimation
Copyright © 2004-2011, Vanderbilt University
21
Networked Operation
1. Multilateration: find an initial shooter position estimate using muzzle blast TDOAs

optional
2. Trajectory search: minimize an error function in a predefined search space



Inputs:
 shockwave TDOAs
 shockwave length
Optimized parameters:
 trajectory
 weapon coefficient
Side effects:
 Bullet speed is computed
 Miss distances are available
3. Final shooter localization: constrained triangulation using range estimates
4. Weapon classification using weapon coefficient and bullet speed
No known weapon assumption.
Copyright © 2004-2011, Vanderbilt University
22
Error Function: Miss distance consistency




Optimize the weapon coefficient for the trajectory
 What is the best weapon coefficient for the evaluated trajectory?
 How good is the match?
 Which trajectory has the best match?
Miss distance is proportional to the fourth power
of the shockwave length.
Miss distance is linearly related to weapon
coefficient.
MSE of the n best miss distances is used as a
metric for the trajectory (n=5 is good in practice)
Copyright © 2004-2011, Vanderbilt University
.M
.M
2
1
.M
3
Error function: Cone angle consistency



Pairwise shockwave TDOA-based trajectory angle consistency
Given a trajectory, the shockwave TDOA of two nodes can be used to
compute the shockwave cone angle.
We compute the shockwave cone angle for all pairs of nodes, and use the
variance of the most consistent subset of size n as the metric (n=5 is good
in practice).
Mi: microphone i position
Bi: position of bullet when shockwave
reaches microphone i
Qi: point on trajectory closest to
microphone i
bi: miss distance
c: speed of sound
α: shockwave cone angle
Δt: shockwave TDOA
The multiple of the miss distance-based and the cone angle-based consistency metric is minimized.
Copyright © 2004-2011, Vanderbilt University
24
Final Shooter Localization





Trajectory is known at this point
Miss distances are also known
Bullet speed is also known
Range to each sensor can be estimated without the known weapon
assumption!
Constrained trilateration using ranges and the known trajectory
Multilateration
Trilateration
Copyright © 2004-2011, Vanderbilt University
Composite
25
Classification



Based on weapon coefficient and projectile speed, the bullet coefficient
(caliber and length) is estimated
Based on bullet coefficient, range and speed, the muzzle velocity can be
estimated (using an approximate deceleration profile)
Caliber and muzzle velocity is characteristic of rifles
12.70mm
M107
7.62mm
T: shockwave length
v: bullet speed (over network)
M: Mach speed of the bullet
b: miss distance
c: speed of sound
d: bullet caliber
l: bullet length
AK47
M240
M16
M4 & M249
Copyright © 2004-2011, Vanderbilt University
5.56mm
26
Evaluation
Out of 108 shots, 107 trajectories could
be computed. Average trajectory angle
error is 0.1 degree, with standard
deviation of 1.3 degrees. Absolute
trajectory angle error is 0.8 degree.
Out of 108 shots, 104 shooter positions
could be computed. Average position
error is 2.96m, which is better than the
5.45m error with the previous, multichannel system.
27
Copyright © 2004-2011, Vanderbilt University
Results from a single soldier’s POV
Average individual bearing error is
0.75 degree.
Average range error is 0.2m, with
standard deviation of 3.3m. Average
absolute range error is 2.3m.
Copyright © 2004-2011, Vanderbilt University
28
Questions?
More information:
[email protected]
Sallai, J., Ledeczi, A., Volgyesi, P.: “Acoustic Shooter Localization with a Minimal Number of
Single-Channel Wireless Sensor Nodes” SenSys 2011
Volgyesi, P., Balogh, G., Nadas, A, Nash, C., Ledeczi, A.: “Shooter Localization and Weapon
Classification with Soldier-Wearable Networked Sensors” MobiSys 2007
Ledeczi, A. et al.: “Countersniper System for Urban Warfare,” ACM Transactions on Sensor
Networks, Vol. 1, No. 2, pp. 153-177, November, 2005
Copyright © 2004-2011, Vanderbilt University
29