Complexity problems in cross-layer optimization for wireless sensor networks have rekindled interest in the quest for a distributed algorithm that would simultaneously handle routing, task assignment, and information fusion, scale gracefully with the network size, and display resilience to node failure. Although various obstacles to this goal remain, belief propagation, and its close cousin expectation propagation, provide many attributes that such a distributed algorithm would require. Indeed, recent works attest to the potential of belief propagation for such tasks as network averaging, node detection, network diagnostics, routing, and even missile defense. This collaborative research project brings together researchers in statistical inference and wireless communications to (i) rephrase random sensor deployment strategies as a sparse dependency structure among parameters; (ii) advance expectation propagation as a distributed algorithm to harmonize many sensor network tasks; (iii) extend convergence results from iterative decoding to inference in sensor networks; and (iv) open novel design and optimization tools in sensor networks as by-products of the work.
In particular, the investigators show how common network inference tasks, including intruder detection, sensor localization, and channel estimation, can be viewed as particular instances of the expectation propagation algorithm passing messages between network nodes. Message passing here consists of soft information exchange, reminiscent of the mature field of iterative decoding. Convergence tools of iterative decoding, including density evolution and EXIT chart analysis, are extended to the network inference problems under consideration. Additional insights and new design tools for sensor networks emerge as natural by-products, ultimately targeting the inference capacity of such networks, and how this capacity may be optimized versus sleep strategies and energy consumption.
Wireless sensor networks are an emerging technology which enable data collection and analysis at large scales via a large number of wireless sensors distributed geographically that process their observations in a decentralized manner. Developers have embraced this technology in a wide variety of applications ranging from environmental monitoring (e.g. forest fire detection) to defense equipment (e.g. battlefield monitoring). In many sensor network designs, the sensors must be both inexpensive and utilize small battery power supplies, and this imposes hard limits on their computational and communications capabilities. This award considered the problem of designing distributed algorithms to analyze data in these networks with specific consideration of these key constraints on computation and communication. In particular, the work concerned the design of collaborative estimation algorithms, in which the nodes in the network communicate with one another to statistically infer unknown quantities from their noisy observations. In these problems, there is a natural relationship between the amount of communications nodes do with another and the accuracy of their estimates. At one extreme, if they do not communicate at all, their estimates perform only as well as afforded by their local observations. At the other extreme, if they communicate so much as to share all of their observations with one another, they can achieve the best possible estimate performance afforded by the entire collection of sensors. The research performed quantified this relationship between the amount of communication and estimate accuracy from a fundamental perspective, identifying the best possible (i.e. highest accuracy) collaborative estimation algorithm performance as a function of amount of communications in the context of several key statistical models and metrics. Once this fundamental relationship between communication and estimate performance had been determined, algorithms were designed to approach the best possible performance while fitting under complexity limitations. Here, techniques from the field of machine learning, in particular belief and expectation propagation, were employed to yield high performance estimates at a low computational cost. A major point of investigation of this machine learning part of the research was a mathematical characterization of the performance and convergence behavior offered by these methods. This award partially supported the studies of two Ph.D. students and three undergraduate students who contributed to the research. The research carried out was published in more than 5 articles in top engineering journals, and more than 15 conference publications, and was presented to the constituent research communities at a large number of conferences and seminars. More details about the work, including the dissertations and other publications, as well as biographical information for the students involved, can be found at Drexel University's Adaptive Signal Processing and Information Theory Research Group's website.
