Network Source Coding

Author:

Razvan Cristescu

Introduction

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. We consider the minimization of cost functions which are the product of a function of the rate and a function of the path weight. We consider both the data gathering scenario, which is relevant in sensor networks, and general traffic matrices, relevant for general networks. Two coding strategies are analyzed: Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult.

Main contributions

This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure.
For the Slepian-Wolf setting, we derived a closed form solution and an efficient distributed approximation algorithm with a good performance. The minimization is achieved by jointly optimizing (a) the transmission structure, which we show consists in general of a superposition of trees from each of the source nodes to its corresponding sink nodes, and (b) the rate allocation across the source nodes, which is done by Slepian-Wolf coding. We show that the overall minimization can be achieved in two concatenated steps. First, the optimal transmission structure has to be found, which in general amounts to finding a Steiner tree and second, the optimal rate allocation has to be 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, we fully characterize the optimal transmission structure and we also provide a closed form solution for the optimal rate allocation. For the general case of an arbitrary traffic matrix, we prove that the problem of finding the optimal transmission structure is NP-complete. We also analyze the design of decentralized algorithms in order to obtain exactly or approximately the optimal rate allocation, depending on the scenario. For the particular case of single-sink data gathering, we provide experimental results showing a good performance in terms of approximation ratios.
For the explicit communication case, we proved that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms. We consider a joint entropy based coding model with explicit communication where coding is simple and the transmission structure optimization is difficult. We first formulate the optimization problem definition in the general case and then we study further a network setting where the entropy conditioning at nodes does not depend on the amount of side information, but only on its availability. We prove that even in this simple case, the optimization problem is NP-hard. We propose some efficient, scalable, and distributed heuristic approximation algorithms for solving this problem and show by numerical simulations that the total transmission cost can be significantly improved over direct transmission or the shortest path tree. We also compare the average case performance of our heuristic approximation algorithms with a strict approximation algorithm proposed in the literature, showing the superior average performance of our algorithms.
Further, we compared asymptotically, for dense networks, the total costs associated with Slepian-Wolf coding and explicit communication, by finding their corresponding scaling laws and analyzing the ratio of their respective costs. In some simplified scenarios, we compare asymptotically (large networks) the total costs associated with Slepian-Wolf coding and explicit communication by finding their corresponding scaling laws and analyzing the ratio of their respective costs. We also provide the specific conditions on the correlation structure which determine the different cases of asymptotic behaviors. We argue that, for large networks and under certain conditions on the correlation structure, ‘intelligent’, but more complex Slepian-Wolf coding provides unbounded gains over the widely used straightforward approach of opportunistic aggregation and compression by explicit communication.

 

Current and Future Research

In our current research we study the problem of network transmission where th correlated data at nodes is coded lossy. Further research is focused on the dual problem of power efficient sensor placement.

Collaborations

Martin Vetterli, Baltasar Beferull-Lozano.

Period

October 2001 – September 2004.

Funding

SNF project number 21-61831.00 and the Swiss National Competence Center in Research for Mobile Information and Communication Systems.

Major publications

T. Ajdler, R. Cristescu, P.L. Dragotti, M. Gastpar, I. Maravic and M. Vetterli, Distributed Signal Processing and Communications: on the Interaction of Sources and Channels, IEEE Conference on Acoustics, Speech and Signal Processing, Vol. 4, pp. 852-855, 2003.
[detailed record] [bibtex]

R. Cristescu and M. Vetterli, Power Efficient Gathering of Correlated Data: Optimization, NP-Completeness and Heuristics, Proc. MobiHoc, Vol. 7, Nr. 3, pp. 31-32, 2003.
[detailed record] [bibtex]

R. Cristescu, B. Beferull-Lozano and M. Vetterli, Networked Slepian-Wolf: Theory and Algorithms, EWSN, pp. 44-59, 2004.
[detailed record] [bibtex]

D. Ganesan, R. Cristescu and B. Beferull-Lozano, Power-Efficient Sensor Placement and Transmission Structure for Data Gathering under Distortion Constraints, Proceedings of the Third International Symposium on Information Processing in Sensor Networks (IPSN), pp. 142-150, 2004.
[detailed record] [bibtex]

R. Cristescu, B. Beferull-Lozano and M. Vetterli, On Network Correlated Data Gathering, INFOCOM, Vol. 4, pp. 2571-2582, 2004.
[detailed record] [bibtex]

R. Cristescu, B. Beferull-Lozano and M. Vetterli, Scaling Laws for Correlated Data Gathering, IEEE International Symposium on Information Theory (ISIT), pp. 472, 2004.
[detailed record] [bibtex]

R. Cristescu, B. Beferull-Lozano and M. Vetterli, Networked Slepian-Wolf: Theory, Algorithms and Scaling Laws, IEEE Transactions on Information Theory, Vol. 51, Nr. 12, pp. 4057-4073, 2005.
[detailed record] [bibtex]

R. Cristescu, B. Beferull-Lozano, M. Vetterli and R. Wattenhofer, Network Correlated Data Gathering with Explicit Communication: NP-Completeness and Algorithms, IEEE/ACM Trans. on Networking, Vol. 14, Nr. 1, pp. 41-54, 2006.
[detailed record] [bibtex]

R. Cristescu, Efficient decentralized communications in sensor networks, Ph.D. Thesis, 2004.
[detailed record] [bibtex]