Dai Receives NSF Award for Wireless Network Node Belief Propagation Research

September 01, 2007


Dr. Huaiyu Dai has been awarded $62,299 from the National Science Foundation for research on Wireless Network Node Collaboration through Belief Propagation. 

The award will run from September 1st, 2007 to August 31st, 2008.

Intellectual Merit: Wireless sensor network is taking an increasingly important role in our life, for which collaboration among sensor nodes is crucial for its success. In anticipated applications, a centralized solution is either not available or infeasible due to resource constraint and application demand. Therefore, cooperative schemes that are distributed, self-organized, scalable, and energy-efficient, are much desired for sensor networks.

This project proposes to employ belief propagation (BP) in wireless sensor networks, to provide a systematic and yet flexible framework to facilitate in-network cooperative processing. Belief propagation is a computing algorithm operating on graphical models, while in sensor networks there is a communication graph reflecting connectivity topology. We are interested in the scenario when the computing graph meets the communication graph. On the one hand, belief propagation facilitates distributed computing and inference in sensor networks. On the other hand, the application of belief propagation in wireless sensor networks is subject to severe communication constraints.  On addressing this interaction, the fact that sensor networks are application driven brings a new angle into research.

Our proposed research comprises the following three main thrusts.

  1. Convergence and correctness of the BP algorithm on general graphs, a challenging problem of high impact on its own, will be studied in the context of specific applications. The connection between BP fixed points and stationary points of some constrained minimization problems will also be pursued, and protocol designs will be jointly considered with theoretical study.
  2. The influence of communication constraints will be explored with respect to message representation, message error and message scheduling, culminating in a comprehensive study on the tradeoffs among energy efficiency, accuracy, computational complexity, and delay.
  3. The synergy of generalized belief propagation (GBP) with sensor networks, an almost brand-new area, will be explored. We will particularly study efficient methods of region partitioning for GBP, which is still more an art than a science. We also propose to study hybrid structures which can combine the advantages of in-network processing and data fusion.

Broader Impacts: Though this proposal targets wireless sensor networks, the proposed framework and fundamental research apply largely to general ad hoc networks as well. They can even be extended to virtual scenarios where a set of 'sensors' distributed over the Internet cooperate on a joint task through information exchange. If we think of wireless networks as a new kind of computer systems, belief propagation can serve as an effective 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.

The PI will seek to incorporate material inspired by this work (at an appropriate level) into the undergraduate and graduate curricula at North Carolina State University. Various channels will be utilized to disseminate research findings to industry and the broader public.