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 http://resolver.caltech.edu/CaltechAUTHORS:CRIieeeacmtn06
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:CRIieeeacmtn06
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.
|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, http://www.mics.org), 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|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||09 Oct 2006|
|Last Modified:||26 Dec 2012 09:05|
Repository Staff Only: item control page