MATLAB Software for Modeling, Optimization and Simulation of
Decentralized Detection Networks
O. Patrick Kreidl
This page illustrates a MATLAB implementation of the models and
algorithms described in the CDC 2006
Paper, using a simple 10-node example.
The following animations may require an XVid plug-in (first
tell me more about the model and its visualization).
- Watch convergent iterations
(450kb) of the efficient message-passing algorithm for
offline strategy optimization. The magenta and blue arrows
indicate the forward "likelihood propagation" and backward "cost-to-go
propagation," respectively, within each successive iteration. The
initial strategy is a simple heuristic one, in which each node uses
its local models to interpret each communicated symbol as the correct
value of the transmitter's local state. We see that this heuristic
strategy leads to a catastrophic failure in performance, in the sense
that link-use-rate is nonzero yet the achieved node-error-rate is
greater than that achieved by the myopic strategy. In contrast, the
message-passing algorithm starts with the same local models and
iteratively finds a processing strategy that uses the limited
communication in a "most informative yet resourceful" way, achieving a
monotonic tradeoff between increasing link-use-rate from zero and
decreasing node-error-rate from its myopic value.
- Watch repeated simulations
(2650kb) of the optimized decentralized strategy for online
measurement processing. In each simulation, the square marker for each
node indicates the measurement likelihood for whether the (hidden)
local state is red or green, using pure yellow to indicate a least
informative local measurement; the circular marker for each "gateway"
node indicates the local state estimate (and nodes without a circular
marker are "communication-only" nodes). The arrows on each link are
similarly color-coded, using pure yellow to indicate the absence of
communication; so, any link with a non-yellow arrow at the transmitter
but a yellow arrow at the receiver represents a symbol
erasure.
- Watch graceful
degradation (250kb) towards the myopic strategy as we increase the
weight on network communication penalty relative to the gateway
detection penalty. An arrow turns from red to green in correspondence
with decreasing link-use-rate, and an arrow colored black specifically
indicates zero use rate. The animation shows the links turning off in
an order that exploits the heterogeneous aspects of the 10-node model.
For example, the first link to turn off disconnects only the node that
(i) is the furthest distance from a gateway node and (ii) measures a
local state process weakly-correlated with the state processes local
to all other nodes; as another example, the last two links to turn off
are between the gateway node with the highest local measurement noise
and its two neighbors.
Simple 10-Node
Example
(a) |
(b) |
(c)
|
(a) A randomly-generated spatial configuration with sparse
connectivity, where each circular marker indicates a sensor node and
each edge indicates a pair of nodes for which direct
interaction (either statistical or through communication or both) is
feasible.
(b) A (directed) probabilistic graphical model based on the
spatial configuration in (a). Each circular marker indicates a node's
a-priori "belief" in whether its local state variable is red or
green. Each edge indicates a pairwise correlation between the two
state variables, which is green'ish, yellow and red'ish for
negatively-correlated, uncorrelated and positively-correlated states,
respectively. In this example, each node's prior "belief" is that its
local state is marginally-uniform yet positively-correlated with the
states local to its neighbors.
(c) A (directed) communication network topology, along with the
nodes' sensing/communication/estimation capabilities, based on the
spatial configuration of (a). Each square marker indicates a node's
measurement noise, using green'ish, yellow or red'ish to indicate a
low, nominal or high noise level, respectively; similarly, each edge
indicates the link's erasure probability, using green'ish and red'ish
to denote above and below, respectively, the median value of 0.5. In
our example, all but four nodes have nominal measurement noise (two
have low noise and two have high noise) and all erasure probabilities
take the value 0.1. The arrow for each link indicates its use-rate
under a particular transmission rule, with red'ish, green'ish
and black denoting frequently, infrequently and never, respectively;
each circular marker indicates a "gateway" node, meaning its local
state estimate is of interest, with interior indicating its error-rate
(green'ish or red'ish when error rate it below or above the value
0.25) under a particular fusion rule. Specifically shown is the
myopic strategy, in which all links have zero use-rate and each
gateway node simply estimates its local state as if in isolation.
Finally, it is worth noting that the communication graph in (c) is not
identical to that in (b), the difference being that the link
connecting the two closest nodes in (b) is NOT present in (c). This
means that the most-accurate sensor (i.e., the green'est square) can
infuence the gateway nodes' final decisions only indirectly through a
relay with the least-accurate sensor (i.e., the red'est square).