On Deterministic Linear Network Coded Broadcast and Its Relation to Matroid Theory
arXiv:1406.5860
Abstract
Deterministic linear network coding (DLNC) is an important family of network coding techniques for wireless packet broadcast. In this paper, we show that DLNC is strongly related to and can be effectively studied using matroid theory without bridging index coding. We prove the equivalence between the DLNC solution and matrix matroid. We use this equivalence to study the performance limits of DLNC in terms of the number of transmissions and its dependence on the finite field size. Specifically, we derive the sufficient and necessary condition for the existence of perfect DLNC solutions and prove that such solutions may not exist over certain finite fields. We then show that identifying perfect solutions over any finite field is still an open problem in general. To fill this gap, we develop a heuristic algorithm which employs graphic matroids to find perfect DLNC solutions over any finite field. Numerical results show that its performance in terms of minimum number of transmissions is close to the lower bound, and is better than random linear network coding when the field size is not so large.
arXiv commentOrigin work accepted by ITW, 5 pages, 8 figures
References in corpus (4)
- On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks
- Generation of Innovative and Sparse Encoding Vectors for Broadcast Systems with Feedback
- Online network coding for optimal throughput and delay -- the three-receiver case
- On Throughput and Decoding Delay Performance of Instantly Decodable Network Coding