Graphical Model-based Approaches to Target Tracking in Sensor Networks: An Overview of Some Recent Work and Challenges
---
paper_title: Probabilistic Networks and Expert Systems

paper_content:

From the Publisher: ::: Probabilistic expert systems are graphical networks that support the modelling of uncertainty and decisions in large complex domains, while retaining ease of calculation. Building on original research by the authors over a number of years, this book gives a thorough and rigorous mathematical treatment of the underlying ideas, structures, and algorithms, emphasizing those cases in which exact answers are obtainable. The book will be of interest to researchers and graduate students in artificial intelligence who desire an understanding of the mathematical and statistical basis of probabilistic expert systems, and to students and research workers in statistics wanting an introduction to this fascinating and rapidly developing field. The careful attention to detail will also make this work an important reference source for all those involved in the theory and applications of probabilistic expert systems.
---
paper_title: Distributed fusion in sensor networks: a graphical models perspective

paper_content:

This paper presents an overview of research conducted to bridge the rich field of graphical models with the emerging field of data fusion for sensor networks. Both theoretical issues and prototyping applications are discussed in addition to suggesting new lines of reasoning.
---
paper_title: Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues

paper_content:

Preface * 1 Probability Review * 2 Discrete Time Markov Models * 3 Recurrence and Ergodicity * 4 Long Run Behavior * 5 Lyapunov Functions and Martingales * 6 Eigenvalues and Nonhomogeneous Markov Chains * 7 Gibbs Fields and Monte Carlo Simulation * 8 Continuous-Time Markov Models 9 Poisson Calculus and Queues * Appendix * Bibliography * Author Index * Subject Index
---
paper_title: Tree consistency and bounds on the performance of the max-product algorithm and its generalizations

paper_content:

Finding the maximum a posteriori (MAP) assignment of a discrete-state distribution specified by a graphical model requires solving an integer program. The max-product algorithm, also known as the max-plus or min-sum algorithm, is an iterative method for (approximately) solving such a problem on graphs with cycles. We provide a novel perspective on the algorithm, which is based on the idea of reparameterizing the distribution in terms of so-called pseudo-max-marginals on nodes and edges of the graph. This viewpoint provides conceptual insight into the max-product algorithm in application to graphs with cycles. First, we prove the existence of max-product fixed points for positive distributions on arbitrary graphs. Next, we show that the approximate max-marginals computed by max-product are guaranteed to be consistent, in a suitable sense to be defined, over every tree of the graph. We then turn to characterizing the nature of the approximation to the MAP assignment computed by max-product. We generalize previous work by showing that for any graph, the max-product assignment satisfies a particular optimality condition with respect to any subgraph containing at most one cycle per connected component. We use this optimality condition to derive upper bounds on the difference between the log probability of the true MAP assignment, and the log probability of a max-product assignment. Finally, we consider extensions of the max-product algorithm that operate over higher-order cliques, and show how our reparameterization analysis extends in a natural manner.
---
paper_title: Distributed fusion in sensor networks: a graphical models perspective

paper_content:

This paper presents an overview of research conducted to bridge the rich field of graphical models with the emerging field of data fusion for sensor networks. Both theoretical issues and prototyping applications are discussed in addition to suggesting new lines of reasoning.
---
paper_title: Constructing free-energy approximations and generalized belief propagation algorithms

paper_content:

Important inference problems in statistical physics, computer vision, error-correcting coding theory, and artificial intelligence can all be reformulated as the computation of marginal probabilities on factor graphs. The belief propagation (BP) algorithm is an efficient way to solve these problems that is exact when the factor graph is a tree, but only approximate when the factor graph has cycles. We show that BP fixed points correspond to the stationary points of the Bethe approximation of the free energy for a factor graph. We explain how to obtain region-based free energy approximations that improve the Bethe approximation, and corresponding generalized belief propagation (GBP) algorithms. We emphasize the conditions a free energy approximation must satisfy in order to be a "valid" or "maxent-normal" approximation. We describe the relationship between four different methods that can be used to generate valid approximations: the "Bethe method", the "junction graph method", the "cluster variation method", and the "region graph method". Finally, we explain how to tell whether a region-based approximation, and its corresponding GBP algorithm, is likely to be accurate, and describe empirical results showing that GBP can significantly outperform BP.
---
paper_title: Distributed data association for multi-target tracking in sensor networks

paper_content:

Associating sensor measurements with target tracks is a fundamental and challenging problem in multi-target tracking. The problem is even more ::: challenging in the context of sensor networks, since association is coupled ::: across the network, yet centralized data processing is in general ::: infeasible due to power and bandwidth limitations. Hence efficient, distributed solutions are needed. We propose techniques based on graphical models to efficiently solve such data association problems in sensor networks. Our approach scales well with the number of sensor nodes in the network, and it is well--suited for distributed implementation. Distributed inference is realized by a message--passing algorithm which requires iterative, parallel exchange of information among neighboring nodes on the graph. So as to address trade--offs between inference performance and communication costs, we also propose a communication--sensitive form of message--passing that is capable of achieving near--optimal performance using far less communication. We demonstrate the effectiveness of our approach with experiments on simulated data.
---
paper_title: A Distributed Algorithm for Managing Multi-target Identities in Wireless Ad-hoc Sensor Networks

paper_content:

This paper presents a scalable distributed algorithm for computing and maintaining multi-target identity information. The algorithm builds on a novel representational framework, Identity-Mass Flow, to overcome the problem of exponential computational complexity in managing multi-target identity explicitly. The algorithm uses local information to efficiently update the global multi-target identity information represented as a doubly stochastic matrix, and can be efficiently mapped to nodes in a wireless ad hoc sensor network. The paper describes a distributed implementation of the algorithm in sensor networks. Simulation results have validated the Identity-Mass Flow framework and demonstrated the feasibility of the algorithm.
---
paper_title: Data association based on optimization in graphical models with application to sensor networks

paper_content:

We propose techniques based on graphical models for efficiently solving data association problems arising in multiple target tracking with distributed sensor networks. Graphical models provide a powerful framework for representing the statistical dependencies among a collection of random variables, and are widely used in many applications (e.g., computer vision, error-correcting codes). We consider two different types of data association problems, corresponding to whether or not it is known a priori which targets are within the surveillance range of each sensor. We first demonstrate how to transform these two problems to inference problems on graphical models. With this transformation, both problems can be solved efficiently by local message-passing algorithms for graphical models, which solve optimization problems in a distributed manner by exchange of information among neighboring nodes on the graph. Moreover, a suitably reweighted version of the max-product algorithm yields provably optimal data associations. These approaches scale well with the number of sensors in the network, and moreover are well suited to being realized in a distributed fashion. So as to address trade-offs between performance and communication costs, we propose a communication-sensitive form of message-passing that is capable of achieving near-optimal performance using far less communication. We demonstrate the effectiveness of our approach with experiments on simulated data.
---
paper_title: Distributed data association for multi-target tracking in sensor networks

paper_content:

Associating sensor measurements with target tracks is a fundamental and challenging problem in multi-target tracking. The problem is even more ::: challenging in the context of sensor networks, since association is coupled ::: across the network, yet centralized data processing is in general ::: infeasible due to power and bandwidth limitations. Hence efficient, distributed solutions are needed. We propose techniques based on graphical models to efficiently solve such data association problems in sensor networks. Our approach scales well with the number of sensor nodes in the network, and it is well--suited for distributed implementation. Distributed inference is realized by a message--passing algorithm which requires iterative, parallel exchange of information among neighboring nodes on the graph. So as to address trade--offs between inference performance and communication costs, we also propose a communication--sensitive form of message--passing that is capable of achieving near--optimal performance using far less communication. We demonstrate the effectiveness of our approach with experiments on simulated data.
---
paper_title: Distributed Group Management in Sensor Networks: Algorithms and Applications to Localization and Tracking

paper_content:

The tradeoff between performance and scalability is a fundamental issue in distributed sensor networks. In this paper, we propose a novel scheme to efficiently organize and utilize network resources for target localization. Motivated by the essential role of geographic proximity in sensing, sensors are organized into geographically local collaborative groups. In a target tracking context, we present a dynamic group management method to initiate and maintain multiple tracks in a distributed manner. Collaborative groups are formed, each responsible for tracking a single target. The sensor nodes within a group coordinate their behavior using geographically-limited message passing. Mechanisms such as these for managing local collaborations are essential building blocks for scalable sensor network applications.
---
paper_title: Information-driven dynamic sensor collaboration

paper_content:

This article overviews the information-driven approach to sensor collaboration in ad hoc sensor networks. The main idea is for a network to determine participants in a "sensor collaboration" by dynamically optimizing the information utility of data for a given cost of communication and computation. A definition of information utility is introduced, and several approximate measures of the information utility are developed for reasons of computational tractability. We illustrate the use of this approach using examples drawn from tracking applications.
---
paper_title: Distributed data association for multi-target tracking in sensor networks

paper_content:

Associating sensor measurements with target tracks is a fundamental and challenging problem in multi-target tracking. The problem is even more ::: challenging in the context of sensor networks, since association is coupled ::: across the network, yet centralized data processing is in general ::: infeasible due to power and bandwidth limitations. Hence efficient, distributed solutions are needed. We propose techniques based on graphical models to efficiently solve such data association problems in sensor networks. Our approach scales well with the number of sensor nodes in the network, and it is well--suited for distributed implementation. Distributed inference is realized by a message--passing algorithm which requires iterative, parallel exchange of information among neighboring nodes on the graph. So as to address trade--offs between inference performance and communication costs, we also propose a communication--sensitive form of message--passing that is capable of achieving near--optimal performance using far less communication. We demonstrate the effectiveness of our approach with experiments on simulated data.
---
paper_title: An Efficient Message-Passing Algorithm for Optimizing Decentralized Detection Networks

paper_content:

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 multi-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 under which the offline algorithm admits an efficient message-passing interpretation, featuring linear complexity 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 detection performance.
---
paper_title: Loopy belief propagation: Convergence and effects of message errors

paper_content:

Belief propagation (BP) is an increasingly popular method of performing approximate inference on arbitrary graphical models. At times, even further approximations are required, whether due to quantization of the messages or model parameters, from other simplified message or model representations, or from stochastic approximation methods. The introduction of such errors into the BP message computations has the potential to affect the solution obtained adversely. We analyze the effect resulting from message approximation under two particular measures of error, and show bounds on the accumulation of errors in the system. This analysis leads to convergence conditions for traditional BP message passing, and both strict bounds and estimates of the resulting error in systems of approximate BP message passing.
---
paper_title: A robust architecture for distributed inference in sensor networks

paper_content:

Many inference problems that arise in sensor networks require the computation of a global conclusion that is consistent with local information known to each node. A large class of these problems---including probabilistic inference, regression, and control problems---can be solved by message passing on a data structure called a junction tree. In this paper, we present a distributed architecture for solving these problems that is robust to unreliable communication and node failures. In this architecture, the nodes of the sensor network assemble themselves into a junction tree and exchange messages between neighbors to solve the inference problem efficiently and exactly. A key part of the architecture is an efficient distributed algorithm for optimizing the choice of junction tree to minimize the communication and computation required by inference. We present experimental results from a prototype implementation on a 97-node Mica2 mote network, as well as simulation results for three applications: distributed sensor calibration, optimal control, and sensor field modeling. These experiments demonstrate that our distributed architecture can solve many important inference problems exactly, efficiently, and robustly.
---
paper_title: Distributed data association for multi-target tracking in sensor networks

paper_content:

Associating sensor measurements with target tracks is a fundamental and challenging problem in multi-target tracking. The problem is even more ::: challenging in the context of sensor networks, since association is coupled ::: across the network, yet centralized data processing is in general ::: infeasible due to power and bandwidth limitations. Hence efficient, distributed solutions are needed. We propose techniques based on graphical models to efficiently solve such data association problems in sensor networks. Our approach scales well with the number of sensor nodes in the network, and it is well--suited for distributed implementation. Distributed inference is realized by a message--passing algorithm which requires iterative, parallel exchange of information among neighboring nodes on the graph. So as to address trade--offs between inference performance and communication costs, we also propose a communication--sensitive form of message--passing that is capable of achieving near--optimal performance using far less communication. We demonstrate the effectiveness of our approach with experiments on simulated data.
---

Title: Graphical Model-based Approaches to Target Tracking in Sensor Networks: An Overview of Some Recent Work and Challenges

Section 1: Introduction
Description 1: This section introduces sensor networks, the role of graphical models, and the context of target tracking in sensor networks.

Section 2: Graphical Models
Description 2: This section provides an overview of graphical models, focusing on Markov Random Fields and their relevance to sensor networks.

Section 3: Inference in Sensor Networks
Description 3: This section discusses how inference tasks are structured in sensor networks using graphical models and the importance of information structure.

Section 4: Inference Tasks in Target Tracking
Description 4: This section introduces key tasks in target tracking such as source localization and data association, and their graphical model representations.

Section 5: Sensor Characterization
Description 5: This section describes sensor measurement models and the general process of sensor characterization in the context of target tracking.

Section 6: Source Localization
Description 6: This section explores methodologies for localizing targets using sensor networks, including graphical models for multi-target scenarios.

Section 7: Data Association
Description 7: This section delves into the data association problem, particularly in multi-sensor, multi-target tracking and the use of graphical models for resolution.

Section 8: Track Maintenance
Description 8: This section covers the maintenance of tracks including initiation, updating, and finalization in a distributed sensor network environment.

Section 9: Discussion
Description 9: This section discusses the challenges and considerations in applying graphical models to sensor networks, especially under communication and energy constraints.