Team for Research in
Ubiquitous Secure Technology

Citation
O. Patrick Kreidl, Alan S. Willsky. "An Efficient Message-Passing Algorithm for Optimizing Decentralized Detection Networks". 2006 IEEE Conference on Decision and Control, December, 2006.

Abstract
A promising feature of emerging wireless sensor networks is the opportunity for each spatially-distributed node to measure its local state and transmit only information relevant to effective global decision-making. An equally important design objective, as a result of each node's finite power, is for measurement processing to satisfy explicit constraints on, or perhaps make selective use of, the distributed algorithmic resources. We formulate this dual-objective design problem within the Bayesian decentralized detection paradigm, modeling resource constraints by a directed acyclic network with low-rate, unreliable communication links. Existing team theory establishes when necessary optimality conditions reduce to a convergent iterative algorithm to be executed "offline" (i.e., before measurements are processed). Even so, this offline algorithm has exponential complexity in the number of nodes and its distributed implementation assumes a fully-connected communication network. We state conditions by which the offline algorithm admits an efficient "message-passing" interpretation, featuring linear complexity in the number of nodes and a natural distributed implementation. We experiment with a simulated network of binary detectors, applying the message-passing algorithm to optimize the achievable tradeoff between global detection performance and network-wide online communication. The empirical analysis also exposes a design tradeoff between constraining in-network processing to preserve resources (per online measurement) and then having to consume resources (per offline reorganization) to maintain effective detection performance.

Electronic downloads

• http://web.mit.edu/~opk/www/res.html

• HTML

  O. Patrick Kreidl, Alan S. Willsky. <a
  href="http://www.truststc.org/pubs/263.html"
  >An Efficient Message-Passing Algorithm for Optimizing
  Decentralized Detection Networks</a>, 2006 IEEE
  Conference on Decision and Control, December, 2006.

• Plain text

  O. Patrick Kreidl, Alan S. Willsky. "An Efficient
  Message-Passing Algorithm for Optimizing Decentralized
  Detection Networks". 2006 IEEE Conference on Decision
  and Control, December, 2006.

• BibTeX

  @inproceedings{KreidlWillsky06_EfficientMessagePassingAlgorithmForOptimizingDecentralized,
      author = {O. Patrick Kreidl and Alan S. Willsky},
      title = {An Efficient Message-Passing Algorithm for
                Optimizing Decentralized Detection Networks},
      booktitle = {2006 IEEE Conference on Decision and Control},
      month = {December},
      year = {2006},
      abstract = {A promising feature of emerging wireless sensor
                networks is the opportunity for each
                spatially-distributed node to measure its local
                state and transmit only information relevant to
                effective global decision-making. An equally
                important design objective, as a result of each
                node's finite power, is for measurement processing
                to satisfy explicit constraints on, or perhaps
                make selective use of, the distributed algorithmic
                resources. We formulate this dual-objective design
                problem within the Bayesian decentralized
                detection paradigm, modeling resource constraints
                by a directed acyclic network with low-rate,
                unreliable communication links. Existing team
                theory establishes when necessary optimality
                conditions reduce to a convergent iterative
                algorithm to be executed "offline" (i.e., before
                measurements are processed). Even so, this offline
                algorithm has exponential complexity in the number
                of nodes and its distributed implementation
                assumes a fully-connected communication network.
                We state conditions by which the offline algorithm
                admits an efficient "message-passing"
                interpretation, featuring linear complexity in the
                number of nodes and a natural distributed
                implementation. We experiment with a simulated
                network of binary detectors, applying the
                message-passing algorithm to optimize the
                achievable tradeoff between global detection
                performance and network-wide online communication.
                The empirical analysis also exposes a design
                tradeoff between constraining in-network
                processing to preserve resources (per online
                measurement) and then having to consume resources
                (per offline reorganization) to maintain effective
                detection performance. },
      URL = {http://www.truststc.org/pubs/263.html}
  }
  

Posted by O. Patrick Kreidl on 16 Jul 2007.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.