Distributed
Coding of
Correlated Sources and Applications in Sensor Networks |
Joint Compression-Routing for Networks |
Introduction
:
![]() ![]() An integral part of optimizing resources in communication networks is routing of information. In this work we consider the problem of minimizing the communication cost for a general multi-hop network with correlated sources and multiple sinks. A typical multi-hop network is shown in the figure. This problem is a very recent and exciting development within this project and forms the preliminary basis for a new project funded by NSF under grant CCF-1016861. As part of the new project, we will be fully pursuing this and related directions. Let a network G be given with N source nodes, M sinks and |V | − N −M intermediate nodes. Each edge e is a network link whose communication cost depends on the edge weight we. Source node i observes random variable Xi. Each sink Sj requests for a subset of sources represented by Vj . Conversely each source Vi is to be reconstructed at a subset of sinks denoted by Si. Our objective is to design joint coding-routing schemes to minimize the overall network cost (calculated given the set of link rates and edge weights) for reconstruction of source information at appropriate sinks. For the single sink scenario, it has been shown that this problem can be decoupled, without loss of optimality, into two separate subproblems of distributed source coding and finding the optimal routing (transmission structure). It has further been established that, under certain assumptions, such decoupling also applies in the general case of multiple sinks and arbitrary network demands. We showed that these assumptions are significantly restrictive, and further provided examples to substantiate the loss, including settings where removing the assumptions yields unbounded performance gains. An approach to solving the unconstrained problem, where routing and coding cannot be decoupled, was derived based on Han and Kobayashi’s achievability region for multi-terminal coding. Related publications: K. Viswanatha, E. Akyol, and K.Rose, "Towards Optimum Cost in Multi-hop Networks with Arbitrary Network Demands ", Proc. IEEE International Symposium on Information Theory (ISIT), June 2010. ![]() |
Dispersive
Information Routing:
![]() Related publication: K. Viswanatha, E. Akyol, and K. Rose, "Lossy Common Information of Two Dependent Random Variables", To appear in Proc. IEEE Symp. Information Theory (ISIT), July, 2012. K. Viswanatha, E. Akyol, and K. Rose, "An Optimal Transmit-Receive Rate Tradeoff in Gray-Wyner Network and Its Relation to Common Information", Proc. IEEE Information Theory Workshop (ITW), October 2011. ![]() K. Viswanatha, E. Akyol, and K. Rose, "An Achievable Rate Region for Distributed Source Coding and Dispersive Information Routing", Proc. IEEE International Symposium on Information Theory (ISIT), July 2011. ![]() K. Viswanatha, E. Akyol, K. Rose, “On optimum communication cost for joint compression and dispersive information routing,” Proc. IEEE Information Theory Workshop (ITW), August 2010. ![]() |
Dispersive Information Router
Design:
![]() We showed using synthetically generated Gaussian sensor grids that, dispersive information routing gains about 1 dB in distortion over conventional routing. Equivalently, we gain about 1 dB in cost for a fixed distortion. Related publication: K. Viswanatha, E. Akyol, S. Ramaswamy and K.Rose, "Distributed source coding and dispersive information routing: an integrated approach with networking and database applications,” European Signal Processing Conference (EUSIPCO), (invited), special session on Distributed Source Coding, August 2010. ![]() |
Multiple Descriptions Coding: ![]() Related publication: E. Akyol, K. Viswanatha and K. Rose, "Combinatorial Message Sharing and Random Binning for Multiple Descriptions Coding," To appear in IEEE Int. Symp. Information Theory (ISIT), July 2012. K. Viswanatha, E. Akyol, and K. Rose, "A Strictly Improved Achievable Region for Multiple Descriptions Using Combinatorial Message Sharing", Proc. IEEE Information Theory Workshop (ITW), October 2011. ![]() K. Viswanatha, E. Akyol, and K. Rose, "Combinatorial Message Sharing for a Refined Multiple Descriptions Achievable Region", Proc. IEEE International Symposium on Information Theory (ISIT), July 2011. ![]() |