A Caltech Library Service

Network correlated data gathering with explicit communication: NP-completeness and algorithms

Cristescu, Răzvan and Beferull-Lozano, Baltasar and Vetterli, Martin and Wattenhofer, Roger (2006) Network correlated data gathering with explicit communication: NP-completeness and algorithms. IEEE/ACM Transactions on Networking, 14 (1). pp. 41-54. ISSN 1063-6692. doi:10.1109/TNET.2005.863711.

See Usage Policy.


Use this Persistent URL to link to this item:


We consider the problem of correlated data gathering by a network with a sink node and a tree-based communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. For source coding of correlated data, 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 present an approximation algorithm that provides a tree transmission structure with total cost within a constant factor from the optimal.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2006 IEEE. Reprinted with permission. Manuscript received March 16, 2004; revised March 10, 2005. [Posted online: 2006-02-21] This work was supported in part by the National Competence Center in Research on Mobile Information and Communications Systems (NCCR-MICS,, a center supported by the Swiss National Science Foundation under Grant number 5005-67322. Parts of this work have been presented at the 23rd Conference of the IEEE Communications Society (INFOCOM 2004), Hong Kong, and at the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2003), Annapolis, MD.
Subject Keywords:Conditional coding, correlated data gathering, distributed algorithms, NP-completeness, routing tree, sensor networks, traveling salesman
Issue or Number:1
Record Number:CaltechAUTHORS:CRIieeeacmtn06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5305
Deposited By: Archive Administrator
Deposited On:09 Oct 2006
Last Modified:08 Nov 2021 20:24

Repository Staff Only: item control page