Back
to Publications
- Title
- Network Information Flow with Correlated Sources
- Authors
- J. Barros, S. D. Servetto.
- Status
- IEEE Transactions on Information Theory, Vol. 52, No. 1, pp. 155-170, January 2006. (original title: The Sensor Reachback Problem)
- Abstract
- Consider the following network communication setup, originating in a sensor networking application we refer to as the "sensor reachback" problem. We have a directed graph G=(V,E), where V = {v_0,v_1,...,v_n} and E \subseteq V \times V. If (v_i,v_j) \in E, then node i can send messages to node j over a discrete memoryless channel (\mathcal{X}_{ij}, p_{ij}(y|x), \mathcal{Y}_{ij}), of capacity C_{ij}. The channels are independent. Each node v_i gets to observe a source of information U_i (i=0...M), with joint distribution p(U_0,U_1,...,U_M). Our goal is to solve an incast problem in G: nodes exchange messages with their neighbors, and after a finite number of communication rounds, one of the M+1 nodes (v_0 by convention) must have received enough information to reproduce the entire field of observations (U_0,U_1,...,U_M), with arbitrarily small probability of error. In this paper, we prove that such perfect reconstruction is possible if and only if
H(U_S|U_{S^c}) < \sum_{i\in S,j\in S^c} C_{ij},
for all S \subseteq {0...M}, S \neq \emptyset, 0 \in S^c. Close examination of our achievability proof reveals that in this setup, Shannon information behaves as a classical network flow, identical in nature to the flow of water in pipes. This "information as flow" view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of implementing codes using a layered protocol stack.
- More:
- Download preprint (pdf file).
- Previous conference papers:
- J. Barros, S. D. Servetto. Coding Theorems for the Sensor Reachback Problem with
Partially Cooperating Nodes. American Mathematical
Society (AMS), Discrete
Mathematics and Theoretical Computer Science (DIMACS) series on Network
Information Theory.
- J. Barros, S. D. Servetto. Reachback Capacity with Non-Interfering Nodes.
In the Proceedings of the IEEE International Symposium on Information
Theory (ISIT), Yokohama, Japan, June-July 2003.
- J. Barros, S. D. Servetto. On the Capacity of the Reachback Channel in Wireless
Sensor Networks. In the Proceedings of the IEEE Workshop
on Multimedia Signal Processing (special session on "Signal Processing
for Wireless Networks"), US Virgin Islands, December 2002. Invited
paper.
- Conference papers dealing
with a related rate/distortion
problem:
- J. Barros, S. D. Servetto. On the Rate/Distortion Region for Separate Coding of
Correlated Sources. In the Proceedings of the IEEE
International Symposium on Information Theory (ISIT), Yokohama, Japan,
June-July 2003.
- J. Barros, S. D. Servetto. An Inner Bound for the Rate/Distortion Region of the
Multiterminal Source Coding Problem. In the Proceedings
of the 37th Annual Conference on Information Sciences and Systems
(CISS), Baltimore, MD, March 2003.