Multi-sender index coding for collaborative broadcasting: a rank-minimization approach

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.