CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:CRIieeetit05

[img]
Preview
PDF
See Usage Policy.

516Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:CRIieeetit05

Abstract

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
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 (http://www.mics.org), 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
Record Number:CaltechAUTHORS:CRIieeetit05
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:CRIieeetit05
Alternative URL:http://dx.doi.org/10.1109/TIT.2005.858980
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1553
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:30 Jan 2006
Last Modified:26 Dec 2012 08:44

Repository Staff Only: item control page