Completion Delay of Random Linear Network Coding in Wireless Broadcast Networks

Dr. SU Rina
University of Science and Technology Beijing
Hosted by Department of Information Engineering, CUHK
Tuesday, 23 May, 2023
Room 833, Ho Sin Hang Engineering Building

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.


Rina Su received the B. Eng. degree in communication engineering from Jilin University in 2016 and the M.Eng. degree in electronic and communication engineering from Inner Mongolia University in 2018. She will receive the D. Eng. degree in communication engineering from University of Science and Technology Beijing in June 2023. She is currently visiting Department of Computer Science, City University of Hong Kong as a research assistant. She has published 3 papers in IEEE TCOM and TVT, and delivered paper oral presentation at IEEE ISIT and ICC. Her research interests include network coding and wireless communication.