Network Information Flow with Correlated Data

Speaker: Joao Barros


Wireless sensor networks, i.e. networks of tiny, low-cost devices with limited sensing, processing and transmission capabilities, have sparked a fair amount of interest in information theory problems involving correlated information sources and large-scale wireless networks. In the first part of this talk, we will model the sensor network as directed graph G with M+1 nodes, each of which observes a distinct source U(i), i=0,…,M. The sources U(0),U(1),…., U(M) are correlated in the sense that they are generated according to the joint probability distribution p(u(0),u(1),…,u(M)). We assume that each edge e(i,j) in G, represents a discrete memoryless channel of capacity C(i,j) over which nodes i and j can communicate, such that after multiple rounds of communication the data collector node 0 is able to provide a perfect reconstruction of all the source data. The goal of the problem is to characterize the conditions on the sources and the channels under which this reconstruction is possible. For this setup, we will present a complete solution. The proof, which uses classical network flow methods offers two fundamental insights: (a) Separate source/channel coding is optimal in any network where theinterference is dealt with at the MAC layer by creating independent links between nodes. (b) In such networks, the properties of Shannon information are exactly identical to those of water in pipes – information is a flow. The second part of this talk will be entirely dedicated to the practical implications of this result. After presenting an optimal protocol stack for this class of sensor networks, we will discuss the tractability of a natural network decision problem and give an example of information theoretically optimal routing. Joint work with Sergio D. Servetto, Cornell University

Full presentation