A Caltech Library Service

Networked Slepian-Wolf: theory, algorithms, and scaling laws

Cristescu, Răzvan and Beferull-Lozano, Baltasar and Vetterli, Martin (2005) Networked Slepian-Wolf: theory, algorithms, and scaling laws. IEEE Transactions on Information Theory, 51 (12). pp. 4057-4073. ISSN 0018-9448. doi:10.1109/TIT.2005.858980.

See Usage Policy.


Use this Persistent URL to link to this item:


Consider a set of correlated sources located at the nodes of a network, and a set of sinks that are the destinations for some of the sources. The minimization of cost functions which are the product of a function of the rate and a function of the path weight is considered, for both the data-gathering scenario, which is relevant in sensor networks, and general traffic matrices, relevant for general networks. The minimization is achieved by jointly optimizing a) the transmission structure, which is shown to consist in general of a superposition of trees, and b) the rate allocation across the source nodes, which is done by Slepian-Wolf coding. The overall minimization can be achieved in two concatenated steps. First, the optimal transmission structure is found, which in general amounts to finding a Steiner tree, and second, the optimal rate allocation is obtained by solving an optimization problem with cost weights determined by the given optimal transmission structure, and with linear constraints given by the Slepian-Wolf rate region. For the case of data gathering, the optimal transmission structure is fully characterized and a closed-form solution for the optimal rate allocation is provided. For the general case of an arbitrary traffic matrix, the problem of finding the optimal transmission structure is NP-complete. For large networks, in some simplified scenarios, the total costs associated with Slepian-Wolf coding and explicit communication (conditional encoding based on explicitly communicated side information) are compared. Finally, the design of decentralized algorithms for the optimal rate allocation is analyzed.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2005 IEEE. Reprinted with permission. Manuscript received December 27, 2003; revised May 25, 2005. Posted online: 2005-11-21. This work was supported in part by the National Competence Center in Research on Mobile Information and Communications Systems (, a center supported by the Swiss National Science Foundation under Grant 5005-67322. The material in this paperwas presented in part at INFOCOM 2004, Hong Kong, China, March 2004; the European Workshop on Sensor Networks, 2004, Berlin, Germany, January 2004; and the IEEE International Symposium on Information Theory, Chicago, IL, June/July 2004. Communicated by G. Sasaki, Associate Editor for Communication Networks.
Subject Keywords:Terms—Energy efficiency, linear programming, sensor networks, shortest path tree, Slepian–Wolf coding
Issue or Number:12
Record Number:CaltechAUTHORS:CRIieeetit05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1553
Deposited By: Archive Administrator
Deposited On:30 Jan 2006
Last Modified:08 Nov 2021 19:11

Repository Staff Only: item control page