Completion Delay of Random Linear Network Coding in Wireless Broadcast Networks

In the classical wireless broadcast network, random linear network coding (RLNC) is known to asymptotically approach the optimal completion delay, or equivalently, throughput with increasing field size. However, the high decoding complexity over a large field hinders the potential applicability of RLNC. To address this issue, we introduce a new method, based on circular-shift operations, to design RLNC schemes which avoid multiplications over large GF(2L). The new RLNC schemes turn out to have a much better trade-off between completion delay and decoding complexity.

We next consider the completion delay performance of RLNC in the full-duplex relay broadcast network, which is a generalization of the classical wireless broadcast. In order to explore the fundamental performance limit of RLNC in terms of completion delay, we propose a scheme named perfect RLNC with buffer, whose expected completion delay can serve as the lower bound for all RLNC schemes. We obtain closed-form formulae as well as recursive expressions of the expected completion delay, both at a single receiver and for the whole system.

In addition, for an existing perfect RLNC scheme known as FBPF (Fewest Broadcast Packets First) designed for the full-duplex relay broadcast network, it does not take buffer size into consideration, so it may involve unnecessary buffer and diminish the practicability. To solve this issue, we generalize FBPF to consider the buffer size as a new parameter, and present a criterion on the optimal selection of the buffer size. Moreover, in the special case that the buffer size is 0, we obtain a closed-form formula of the expected completion delay both at a single receiver and for the whole system.