Wireless Index Coding Through Rank Minimization

Index coding, initially introduced within theoretical computer science to address a specialized class of problems, has gained significant interest within communications and networking communities in recent years. Index coding has been shown to be analogous to a large class of challenging wired network coding and wireless multi-terminal problems, the latter class being of primary interest in this paper. Here, a (relaxed) rank minimization based analytic framework is presented for wireless index coding, which represents a first step in a systematic algorithmic approach to index coding for practical use. Further, the paper demonstrates its applicability over a real-world wireless testbed. The scheme operates at the network layer, and can be understood as a (non-trivial) generalization of existing principles of random linear network coding. Experimental results demonstrate that, for a class of network topologies, the rank-minimized index coding system presents a throughput gain of 50 to 100 percent greater than random linear coding for this system.