|
| Robust Message-Passing for Distributed Inference (DISTIN) |
| 1. Goals |
Develop robust, efficient message-passing algorithms for effective inference, learning and control in wireless sensor networks and other distributed systems. These algorithms must perform the global inference and optimization tasks required by sensor network applications, while being robust to network losses and failures, and limiting communication and power requirements. Our efficient method is leveraged by powerful representation and inference approaches from probabilistic graphical models, and by novel networking and message passing algorithms (cross-layer optimizations) in a comprehensive study on the tradeoffs among delay - energy efficiency – accuracy (approximation rate), and - computational complexity.
Figure 1: Fire-Alarm System using Wireless Sensor Networks and Distributed Inference
|
| 2. Why Distributed Inference (DISTIN) is so important? |
We could adopt a centralized approach to inference in which the sensor measurements are "downloaded" from the network and then analyzed at some central location. While this approach is appropriate in some cases, there are three reasons we may prefer a distributed approach to inference: first, we can leverage parallelism by making use of the computational resources at each node; second, distributed inference reduces communication because nodes can transmit compact summaries instead of all of their measurements; and finally, distributed inference enables distributed action because each node of the network obtains the any-time posterior distribution of its variables. |
| 3. Why Graphical Models & Message-Passing Approach to DISTIN? |
Several reasons underlie the choice of graphical models for addressing distributed fusion problems in sensor networks.
- First, a graphical model is well suited to capture the structure of a sensor network, which consists of nodes (for sensing, communication, and computation) as well as connections between the nodes (for modeling statistical dependencies and/or communication links).
- Second, there has recently been significant progress in the development and analysis of scalable inference algorithms on graphs. This includes recent work on analyzing and understanding the behavior of well-known classes of local message-passing algorithms on graphs that contain loops. There has also been considerable progress in developing new message-passing algorithms with superior convergence and accuracy properties; in some cases these algorithms have provable guarantees of convergence to optimal answers.
- Third, the algorithms commonly used for performing estimation in graphical models involve parallel message-passing operations that are not only efficient and scalable but also well suited to parallel realization via physically distributed processors, with any-time approximations, a crucial requirement in sensor network applications.
- Finally, graphical models provide a suitable framework for the development and analysis of communication-constrained versions of message-passing algorithms, which are of considerable interest in the context of sensor networks given their severe power and energy limitations.
Figure 2: Probabilistic modeling of the inference problem and its physical deployment |
| 4. Uniqueness |
The distributed inference in WSN under communication constraints is a topic of much current interest. A formal method to support efficient distributed inference in different applications must be developed. However, most existing inference architectures for sensor networks are often ad hoc, not efficient for large-scale, energy and bandwidth constrained WSN. Most of them lack one or some of the following research thrusts that we propose:
- We propose to apply the recent modeling and computational methodology of probabilistic graphical models and message-passing to exploit the locality structure of the probabilistic inferences problems, and its distributive properties to yield efficient distributed inference architecture.
- We propose to analyze the convergence and correctness of message-passing algorithms, a challenging problem of high impact on its own, in the context of specific DISTIN applications. The connection between message-passing fixed points and stationary points in solving the inference problems with loopy graphs will also be investigated.
- At lower layer supports for DISTIN (cross-layer optimization), we propose to study (self-organizing) hybrid structures, which can combine the advantages of (ad hoc) in-network processing and data fusion, e.g. cluster-based approach with intra-cluster data fusion at the cluster heads and inter-cluster randomize gossip between cluster heads. We also consider developing de-synchronization mechanisms for efficient, collision-free message-passing.
- We propose to analyze the robustness of the message-passing algorithms in practical conditions (communication failures, asynchronous update, message error, and message-censoring), in a comprehensive study on the tradeoffs among delay - energy efficiency – accuracy (approximation rate), and - computational complexity of the proposed DISTIN architecture. This will pave the way for practical implementation of DISTIN.
- Finally, we propose a framework for implementing/mapping between the graphical models on each node to the distributed environment of WSN. This results in a macro-programming language for tasking DISTIN in WSN.
Figure 3: The proposed software architecture on a sensor node for DISTIN |
| 5. Broad Impacts |
-
Inference is an indispensable building block for decision-making tasks. For example, target detection and tracking is an important task in many ubiquitous applications like u-lifecare (to track elderly people), smart spaces (to track users), farm-surveillance (to track animals), transportation (to track cars and traffic), battlefield (to detect and track tanks), etc. (Fig. 4a) Thus by accomplishing the research goals in this proposal, we believe to provide a robust, energy-efficient, scalable architecture for DISTIN applications, which in turn will have great effects on many application domains: Health-care systems, Smart homes; Transportation systems; Precision Agriculture (Fig. 4b); Defense systems; Structural Health Monitoring; and WSN itself (optimization issues e.g. minimum-cost clustering, resource allocation, flow control, etc.)
 |
 |
Figure 4a: Target Tracking |
Figure 4b: Precision Agriculture |
-
Though this proposal targets wireless sensor networks, the proposed framework and fundamental research apply largely to general ad hoc networks as well, e.g. swarm of robots. They can even be extended to support virtual counterparts of physical objects distributed over the Internet to cooperate on a joint task through information exchange. If we think of wireless networks as a new kind of computer systems, DISTIN framework can serve as an effective macro-programming language for them. The proposed work lies in the interface of networking, communications, and computing, heavily replying on the knowledge in information theory, communication theory, Bayesian inference, graph theory and models, and communication/computation/information complexity. It has the potential to advance the theory and practice of these areas, and contribute to the evolvement of next generation wireless networks.
|
|
|
|
|
|
|
|
