Transcript Apweb220PPt - NEC Laboratories America

Mining Lines in the Sand: On Trajectory
Discovery From Untrustworthy Data in
Cyber-Physical System
Lu-An Tang, Xiao Yu, Quanquan Gu, Jiawei
Han, Alice Leung, Thomas La Porta
2015/7/18
Outline
Introduction
Mining Dots in the Sand: Detecting Intruder Appearances
Connecting Dots as Lines: Tracking Intruder Trajectories
Experiments
2015/7/18
2
Introduction
Cyber Physical System: Integrate physical devices (e.g.,
sensors, cameras) with cyber components to form a
situation aware analytical system
Important application in military and civil fields: monitor
the designated region and detect the trajectories of bypassing objects (intruders)
Igloo White: Use UGS (Unattended Ground Sensors) to
detect enemy infantry and vehicle
REMBASS: REmotely Monitored BAttlefield Sensor System
Ground Tactical System, etc
2015/7/18
3
The Scenario: Mining Lines in the Sand
Deploy larger number of sensors in the battlefield
Collect seismic, acoustic and magnetic signals from the environment
Discover the trajectories of intruders passing the region
gateway sensors
sensors
transmitting the
(i.e., sand)
sensor records to
seismic, acoustic and the data center
magnetic sensors
intruder o2
intruder o1
intruder o2
2015/7/18
intruder o1
data center
analyzing the
sensor records and
mining the lines
4
The Problem Statement
Input: sensor network S={s1, s2, … sn}; sensor data arrives
by time, R ={R1, R2, …, Rm}
Output: a set of intruder trajectories {L1, L2, … Lk}
Li = {pi,1, …, pi,j}, a sequence of intruder appearances
Mining lines in the sand = Mining dots in the sand +
Connecting dots as lines
Sub-Task 1: detecting intruder appearances (i.e., position) in
every timestamp
Sub-Task 2: composing the trajectories from detected
positions
2015/7/18
5
Challenges: Untrustworthy Data and Target Tracking
Untrustworthy data:
Low cost, energy saving sensors are not reliable
Generate both false positives and false negatives
Maintain a sensor reliability model over the streaming data
Multiple Target Tracking:
Sensors do not know any identity information of the intruders
Multiple intruders, number is unknown in advance
2015/7/18
6
Brief Survey of Related Studies
Sensor network optimization: find an optimal deployment
plan, diagonal to our work
Maximize coverage [Cevher09, Wimalajeewa10]
Minimize energy [Hung10]; Shorten acting time [Wang11]
Maximum likelihood localization [Shen05]
Transfer learning based localization [Pan08]
Energy-efficient tracking [Chen09, Ghica10]
Karlman filtering based tracking [Djuric08]
Markov-chain Monte-carlo based tracking [Qian09]
2015/7/18
7
Summary of Related Works
Method
Function
Goal
Additional
Info.
Untrustworth
y data
Sensor
optimization
detection
energy saving
deploy
none
Yes
ML
localization
detection
intruder
position
energy
number
No
Transfer
Learning
detection
intruder
position
training
set
Yes
Ener. Eff.
Tracking
tracking
energy saving
deploy
none
Yes
Par. Filter
MCMC
tracking
intruder
trajectory
position,
speed, etc
No
LiSM
detection and
tracking
intruder
trajectory
none
Yes
2015/7/18
8
The System Framework
Appearance Miner
Streaming
Data
Construct
Monitoring
Graph
Integrate
Trajectory
Generator
Intruder
Appearances
Match
Cone Model
Reliability
Model
Feedback
Candidate
Trajectories
Trajectory Validator
Output
Sensor
Network
2015/7/18
Trustworthy
Trajectories
9
Outline
Introduction
Mining Dots in the Sand: Detecting Intruder Appearances
Connecting Dots as Lines: Tracking Intruder Trajectories
Experiments
2015/7/18
10
Mining Dots in the Sand
Input: sensor network S={s1, s2, … sn}; sensor dataset, Rj,
in time tj
Output: detected intruder appearances in tj: Pj={p1,j, p2,j …,
pk,j}
r2,1
intruder
position
o1
(100, 100)
s2
s1
s3
r1,1
r7,1
s7
2015/7/18
r3,1
o1
r4,1
s4
r5,1
s6
s5
record
center
radius
r1,1
(97,109)
10
r2,1
(95,123)
10
r3,1
(105,107)
7
r4,1
(105,99)
8
r5,1
(125,84)
7
r7,1
(92,98)
6
11
Constructing the Watching Network
Clustering the detection records
Responding sensor: has a detection nearby
Non-responding sensor: no detection or
the detection is far away
p2,1
r2,1
s1
s2
s1
s3
r1,1
r4,1
r7,1
s7
2015/7/18
s5
r1,1
s3
r3,1
s4
s4
r5,1
p3,1
s6
p1,1
r3,1
p1,1
r2,1
s2
p2,1
p3,1
r7,1
s5
r4,1
s6
s7
r5,1
12
Calculating the Detection Confidence
The confidence of the detected appearances are calculated
based on the linked sensor’s reliability scores
s1
s2
p1,1
s3
s4
p2,1
p3,1
2015/7/18
s5
s6
s7
13
Outline
Introduction
Related Works
Mining Dots in the Sand: Detecting Intruder Appearances
Connecting Dots as Lines: Tracking Intruder Trajectories
Experiments
2015/7/18
14
The Tracking Framework
The sensor data arrives by time
The system maintains a trajectory candidate set along the
streaming data
Matching the newly detected appearances with existing
candidates, the best matched ones are added to the candidates
Initializing new candidates from non-matched appearances
Validating the trajectory candidates
2015/7/18
15
Matching Trajectory Candidate Lk with Appearance pi.j
pi,j is a newly detected intruder appearance at tj
Candidate Lk={pk,1, pk,2…, pk,j-1}
 ( pi, j  Lk )   ( pi, j )P( pi , j , Lk )
The probability P(pi,j, Lk) shows how likely that the
position of pi,j is the move of Lk at tj
Predict Lk’s possible move, see whether pi,j is close to
the prediction
2015/7/18
16
The Prediction Cone Model
Retrieve the ω-recent points of Lk
Calculate the mean and deviation of moving speed and direction
Construct a cone model to predict next move of Lk
Assumption: the moving speed and direction are in the normal
distribution
(v  3 (v),   3 ( ))
(v  3 (v),   3 ( ))
p1,j
p2,j
{v, σ(v), θ, σ(θ)}
pk,j-4
pk,j-5
2015/7/18
pk,j-3
pk,j-2
pk,j-1
p3,j
(v  3 (v),   3 ( )) (v  3 (v),   3 ( ))
17
Calculating the Probability
Suppose pk,j is the next appearance of Lk
Estimate the speed and direction between [tj-1, tj] as
Compare the estimated speed/direction with the parameters
of recent trajectory and calculate the matching probability
2015/7/18
18
More Details of the Cone Model
When the trajectory is not long enough (e.g., newly
generated candidates), the cone model releases the
constraint on the direction and uses a default speed (e.g.,
average speed of other intruders)
The cone degenerates to be a round disk
p1,j
p2,j
pk,j-2
2015/7/18
pk,j-1
p3,j
19
Validate the Trajectory Candidates
Efficiency Problem: Too many false positive candidates
Observation: The real intruder moves in a continuous
manner and the trajectory grows longer over time, the false
positive appearances are unlikely to be connected
Trajectory Expectation Ej(Lk): How likely Lk to be a real
trajectory at tj
E j ( Lk ) 
2015/7/18

pk ,i Lk
 ( pi , j )   (t j  t1 )
20
Feedback to Update the Sensor Reliability
A candidate trajectory is removed from memory
False positive trajectory
The intruder appearances are false positive
Punish the responding sensors
A candidate trajectory is reported as a true result
Punish the non-responding (false negative) sensor
2015/7/18
21
An Example to Illustrate the Process
……
Sensor
Reliability
Model
Trajectory
Candidates
Trajectory
Candidates
Trajectory
Candidates
……
feedback
2015/7/18
22
Outline
Introduction
Mining Dots in the Sand: Detect Intruder Appearances
Connecting Dots as Lines: Track Intruder Trajectories
Experiments
2015/7/18
23
Experiment Setup
Dataset
Intruder
Sensor. #
D1
D2
D3
D4
10
20
30
40
225
2500
3600
10,000
Reading.
#
2.9*105
6.1*105
1.3*106
3.5*106
False
alarm%
10%
20%
40%
50%
false
negative%
5%
10%
20%
30%
Real trajectories, synthetic sensor readings
Compare Intruder-Miner (IM) to: TruAlarm(TA) and
Maximum likelihood localization (ML)
Compare Line-Miner (LM) to: Track kNN method (TN)
and Karlman Filtering based tracking (KF) with the same
detection results of IM
2015/7/18
24
Intruder Detection Results: Efficiency
Sensor number
IM costs only 10-20% time of ML and TA
Reason: The sensor network are partitioned and the input data
size is reduced
2015/7/18
25
Intruder Detection Results: Effectiveness
LM
IM KL
ML TNTA
LM
IM
100%
100%
100%
100%
80%
80%
80%
80%
60%
60%
60%
60%
40%
40%
40%
40%
20%
20%
20%
20%
0%
0%
0%
KL
ML TN
TA
D1
D2
D3
D4
D1 D2 Precision
D3 D4
(a) Detecting
0%
D1
D2
D3
D4
D2 Recall
D3 D4
(b)D1
Detecting
Ground truth: the points of real trajectories; Detection result: the
points of intruder appearances
Valid detection: dist(pground, pdetect) < distance threshold (maximum
detection range)
Precision= | Valid |/|Result|; Recall = | Valid |/|Ground|;
2015/7/18
26
Intruder Tracking Result: Effectiveness
LM
KL
LM
TN
100%
100%
80%
80%
60%
60%
40%
40%
20%
20%
0%
0%
D1
D2
D3
D4
(a) Tracking Precision
D1
KL
D2
TN
D3
D4
(b) Tracking Recall
Valid segment: p1,1p1,2, p1,1 and p1,2 are both valid detection and
belongs to the same intruder
Precision= |Valid |/|Result|; Recall = |Valid |/|Ground|;
TN: poor performance by only choosing among the k-nearest ones
KL: low precision due to lack of verification process
2015/7/18
27
Tuning Parameter: The Recent Traj. Length ω
ω is the length of Lk’s recent points for prediction model
Too small/large ω  poor prediction
2015/7/18
28
Tuning Parameter: The Decay Factor β
β is the parameter to filter false positives in candidate
trajectories
Increasing β, higher precision, lower recall
Setup β according to the false positive ratio
2015/7/18
29
Conclusion and Future Work
Propose an integrated framework to detect and track the
intruders from untrustworthy sensor data
Employ watching networks to build the relationships
between sensors and intruders
Match the trajectories and detections by a cone model
Future Work:
Extend the method to more complex scenarios, e.g., the road
network
Interactive mining and validation
Thank you very much!
Any Questions?
2015/7/18
30
References
[Cevher09] Volkan Cevher and Lance M. Kaplan. 2009. Acoustic sensor network design
for position estimation. ACM Trans. Sen. Netw. 5, 3, Article 21 (June 2009)
[Wimalajeewa10] Thakshila Wimalajeewa and Sudharman K. Jayaweera. 2010. Impact
of mobile node density on detection performance measures in a hybrid sensor network.
Trans. Wireless. Comm. 9, 5 (May 2010), 1760-1769
[Hung10] Chih-Chieh Hung and Wen-Chih Peng. 2011. Optimizing in-network aggregate
queries in wireless sensor networks for energy saving. Data Knowl. Eng. 70, 7 (July
2011), 617-641.
[Wang10] Yun Wang , Zhengdong Lun, Impact of Deployment Point Arrangement on
Intrusion Detection in Wireless Sensor Networks, Proceedings of the 2010 IEEE
International Symposium on Modeling, Analysis and Simulation of Computer and
Telecommunication Systems
[Wang11] Yun Wang and Zhengdong Lun. 2011. Intrusion detection in a K-Gaussian
distributed wireless sensor network. J. Parallel Distrib. Comput. 71, 12
2015/7/18
31
References
[Chen09]Min-Xiou Chen and Yin-Din Wang. 2009. An efficient location tracking
structure for wireless sensor networks. Comput. Commun. 32, 13-14 (August 2009),
1495-1504.
[Ghica10] Oliviu Ghica, Goce Trajcevski, Fan Zhou, Roberto Tamassia, and Peter
Scheuermann. 2010. Selecting tracking principals with epoch awareness. In Proceedings
of the 18th SIGSPATIAL International Conference on Advances in Geographic
Information Systems (GIS '10)
[Shen05] Xiaohong Sheng and Yu-Hen Hu. 2005. Maximum likelihood multiple-source
localization using acoustic energy measurements with wireless sensor networks. Trans.
Sig. Proc. 53, 1
[Djuric08] P.M. Djuric, M. Vemula, and M.F. Bugallo. 2008. Target Tracking by Particle
Filtering in Binary Sensor Networks. Trans. Sig. Proc. 56, 6 (June 2008)
[Qian09] Qian Yu and Gerard Medioni. 2009. Multiple-Target Tracking by
Spatiotemporal Monte Carlo Markov Chain Data Association. IEEE Trans. Pattern Anal.
Mach. Intell. 31, 12 (December 2009)
2015/7/18
32