Transcript sensor target

Wireless Distributed Sensor
Tracking: Computation and
Communication
Bart Selman, Carla Gomes, Scott Kirkpatrick,
Ramon Bejar, Bhaskar Krishnamachari,
Johannes Schneider
Intelligent Information Systems Institute, Cornell
University & Hebrew University
Autonomous Negotiating Teams
Principal Investigators' Meeting, Dec. 17, 2001
Outline
Overview of our approaches
Ants - Challenge Problem (Sensor Array)

Exact methods
 Determination of the phase diagram


Results from physical model (annealing)
Distributed CSP model
Dynamic Bayesian networks
Conclusions: Steps to application
Overview of Approaches
We develop heuristics more powerful than
greedy, not compromising speed
Exact methods tuned for domain structure
Overall theme --- Identification of domain
structural features
 tractable vs. intractable subclasses
 phase transition phenomena
 backbone
Goal:
 Principled, controlled, hardness-aware systems
IISI, Cornell University
ANTs Challenge Problem
Multiple doppler radar sensors track moving
targets
Energy limited sensors
Communication
constraints
Distributed computation
Dynamic system
IISI, Cornell University
Models
Start with a simple graph model
Refine in stages to approximate the real situation:
 Static weakly-constrained model
 Add communication, target range constraints
 Physical model allows full range of real
constraints, incorporate target acquisition…
 Distributed constraint satisfaction model
Goals:
 Algorithms that scale for this problem
 Understand the sources of complexity
IISI, Cornell University
Initial Assumptions
Each sensor can only track one target
at a time
3 sensors are required to track a target
IISI, Cornell University
Initial Graph Model
The initial model presented is a bipartite
graph, and this problem can be solved using
a maximum flow algorithm in polynomial time
Results incorporated into framework
developed by Milind Tambe’s group at ISI,
USC
Joint work in progress
Sensor
Target
nodes
nodes
IISI, Cornell University
Constrained Graph Model
communication links
sensors
targets
possible solution
IISI, Cornell University
Description of Experiments
Create
communication
graph
based
on
range
Combine
Create
Create
Place
Start
visibility
sensors
visibility
the
with
communication
square
and
graph
graph
targets
area
based
based
with
randomly
and
on
on visibility
radar
unit
radar
sides
in
range
range
area
graphs
RRC
sensor
target
C
R
Limit cases
IISI, Cornell University
Phase Transition w.r.t.
Communication Range:
Probability( all targets tracked )
Experiments with a configuration of 9 sensors and 3
targets such that there is a communication channel
between two sensors with probability p
Insights into the design
and operation of sensor
networks w.r.t.
communication range
Communication edge probability p
Special case:
all targets are
visible to all
sensors
IISI, Cornell University
Phase Transition w.r.t.
Radar Detection Range
Probability( all targets tracked )
Experiments with a configuration of 9 sensors and 3
targets such that each sensor is able to detect targets
within a range R
Insights into the design
and operation of sensor
networks w.r.t.
radar detection range
Special case:
all nodes can
communicate
Normalized Radar Range R
Communication vs. Radar Range
vs. Performance
The full picture
Performance and Phase Boundaries
Natural units: sensors/target, sensors within range of
a target, sensors communicating with a sensor
19 sensors, 5 targets
Phase diagram for the sensor array
3D phase diagram is bounded by:



3+ sensors/target
3+ sensors within range of each target
2+ one-hop neighbors for each sensor
Physical model (and annealing)
Represent acquisition and tracking goals in terms of a
system objective function
Define such that each sensor, with info from its 1-hop
neighbors, can determine which target to track
Potential per target depends on # of sensors tracking
More on annealing
Target Cluster (TC) is >2 1-hop sensors tracking the
same target – enough to triangulate and reach a
decision on response.
Classic technique – Metropolis method simulates
asynchronous sensor decision, thermal annealing
allows broader search (with uphill moves) than
greedy, under control of annealing schedule.
Our results on the unconstrained problem validate
the objective function, converge with as few as three
iterations per sensor.
Moving targets, tracking and acquisition
100 sensors, t targets (t=5-30) incident on the array,
curving at random. Movies of 100 frames for each of
several values of (sensors in range)/target and (1hop neighbors)/sensor. Sensors on a regular lattice,
with small irregularities. Between each frame a
“bounce,” or partial anneal using only a low
temperature, is performed to preserve features of the
previous solution as targets move.
Moving Targets -- Movies
Conventions:

Targets

Target range

Sensors
 Sector
active

Target Clusters

Coverage
Analyzing the movies
Summary frames:
easy case (10 targets)
hard case (30 targets)
color code: red (1 TC), green (2 TCs), blue (3 TCs), purple (4TCs) , …
Examples of physical model solutions
See www.cs.huji.ac.il/~jsch/beautifulmovies/movies.html
(these are 12-20MB animated gif files, so I will run my examples from
local copies)
Three lattices (hex, square, triangular)
Target detection range = 1.5, 2, 3, 4x nngbr dist.
Avg. # of neighboring sensors from 4.5 (hex) to 7 (triangular)
examples:
Analysis of physical model results
When t targets arrive at once, perfect tracking can
take time to be achieved.
Target is considered “tracked” when a TC of 3+
sensors keeps it in view continuously.
We analyze each movie for longest continuous period
of coverage of each target, report minimum and
average over all targets.
Results with moving targets
Target visibility range and targets/sensor bounds seen:
IISI, Cornell University
Distributed Computational Model
In a Distributed Constraint Satisfaction
Problem (DCSP), variables and constraints
are distributed among multiple agents. It
consists of:



A set of agents 1, 2, … n
A set of CSPs P1, P2, … Pn , one for each agent
There are intra-agent constraints and inter-agent
constraints
IISI, Cornell University
DCSP Models
With the DCSP models, we study both
per-node computational costs as well as
inter-node communication costs
DCSP algorithms: DIBT (Hamadi et al.)
and ABT (Yokoo et al.)
IISI, Cornell University
Communication vs. Radar Range
vs. Computation
Computational Complexity: total
computation cost for all agents
Communication Complexity: total
number of messages sent by all agents
Communication range / Sensor (radar) range
provides 3rd dimension.
These measures can vary for the same
problem when using different DCSP models
Average Complexity
Probability of Tracking
• 5 targets and 17 sensors
IISI, Cornell University
(target-centered)
Mean computational cost
Average Complexity
Probability of Tracking
• 5 targets and 17 sensors
IISI, Cornell University
(target-centered)
Mean communication cost
Next Steps
Physical Model
Increased realism in the objective function



Energy costs of excessive coverage – handoff policy
Sector switching – delay and energy costs
Geometrical constraints for accurate tracking
Continuous asynchronous tracking

More accurate model of target acquisition
Optimize to reduce communication costs
Realistic criterion for successful tracking
Specialize to a plausible, full-scale deployed system
Dynamic Bayesian Model
Joint work with Matt Thomas, AFRL
Create dynamic Bayes network (with
probabilistic information about domain state)
within traditional influence diagram.
Use this approach to handle turning off
sensors as much as possible for energy
conservation.
IISI, Cornell University
Dynamic DCSP Model
Further refinement of the model:
incorporate target mobility
The graph topology changes with time
What are the complexity issues when
online distributed algorithms are
used?
Summary
IISI, Cornell University
Summary
Graph-based and physical models capture
the ANTs challenge domain
Results on the tradeoffs between:
Computation, Communication, Radar range,
and Performance are captured in phase diagram.
Results enable a more principled and
efficient design of distributed sensor networks.
Techniques handle realistic constraints, fast enough for
use in real distributed system.
Collaborations / Interactions
ISI: Analytic Tools to Evaluate Negotiation
Difficulty

Design and evaluation of SAT encodings for
CAMERA’s scheduling task.
ISI: DYNAMITE

Formal complexity analysis DCSP model (e.g.,
characterization of tractable subclasses).
UMASS: Scalable RT Negotiating Toolkit

Analysis of complexity of negotiation protocols.
IISI, Cornell University
The End