How to Tune Sparse Network Coding over Wireless Links

Despite their high computational complexity, Random Linear Network Coding (RLNC) techniques have been shown to offer a good robustness against packet erasure wireless channels. Some approaches have been recently proposed to reduce such computational burden, for both encoder and decoder elements. One of those are the so-called Tunable Sparse Network Coding (TSNC) techniques, which advocate limiting the number of packets that are combined to build a coded packet. They also propose dynamically adapting the corresponding sparsity level, as the transmission evolves, although an optimum tuning policy has not been yet found. In this paper we present a TSNC implementation that exploits a novel analytical model to estimate the probability of generating an innovative packet (linearly independent combination), given the current status at the decoder. Taking advantage of the model's accuracy, the proposed scheme offers a better trade-off between computational complexity and network performance. Furthermore, we broaden the analysis of TSNC techniques by thoroughly assessing their behavior over wireless networks using the ns-3 platform. The results yield a remarkable complexity reduction (approx. 3.33x less complexity), without jeopardizing network performance.