Multi-Sender Index Coding for Collaborative Broadcasting: A Rank-Minimization Approach
- 21 October 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 67 (2) , 1452-1466
Abstract
We consider a Multi-Sender Unicast Index-Coding (MSUIC) problem, where in a broadcast network, multiple senders collaboratively send distinct messages to multiple receivers, each having some subset of the messages a priori. The aim is to find the shortest index code that minimizes the total number of coded bits sent by the senders. In this paper, built on the classic single-sender minrank concept, we develop a new rank-minimization framework for MSUIC that explicitly takes into account the sender message constraints and minimizes the sum of the ranks of encoding matrices subject to the receiver decoding requirements. This framework provides a systematic way to construct multi-sender linear index codes and to study their capability in achieving the shortest index codelength per message length (i.e., the optimal broadcast rate). In particular, we establish the optimal broadcast rate for all critical MSUIC instances with up to four receivers and show that a binary linear index code is optimal for all, except 15 instances with four receivers. We also propose a heuristic algorithm (in lieu of exhaustive search) to solve the rank-minimization problem. The effectiveness of the algorithm is validated by numerical studies of MSUIC instances with four or more receivers.Keywords
Funding Information
- Australian Research Council (FT140100219, DP150100903)
This publication has 28 references indexed in Scilit:
- Index coding and network coding via rank minimization2015
- A matrix completion approach to linear index coding problem2014
- Data Dissemination With Side Information and FeedbackIEEE Transactions on Wireless Communications, 2014
- Graph theory versus minimum rank for index coding2014
- Index coding via random coding2014
- On the capacity region for index coding2013
- Local graph coloring and index coding2013
- Polynomial Time Algorithm for Min-Ranks of Graphs with Simple Tree StructuresAlgorithmica, 2013
- Informed-source coding-on-demand (ISCOD) over broadcast channels2002
- Orthogonal representations over finite fields and the chromatic number of graphsCombinatorica, 1996