On the Packet Decoding Delay of Linear Network Coded Wireless Broadcast

We apply linear network coding (LNC) to broadcast a block of data packets from one sender to a set of receivers via lossy wireless channels, assuming that each receiver already possesses a subset of these packets (through previous systematic transmissions) and wants the rest. We aim to characterize the average packet decoding delay (APDD), which reflects how soon each data packet can be decoded by each receiver on average, and to minimize it without sacrificing throughput. To this end, we first derive closed-form lower bounds on the expected APDD of LNC techniques. We then prove that determining whether these lower bounds are tight is NP-hard and so is APDD minimization. We then prove that every throughput-optimal LNC technique can approximate the minimum expected APDD with a ratio between 4/3 and 2 and that this ratio is exactly 2 for random LNC (RLNC). We also show that instantly decodable network coding (IDNC) techniques cannot approximate APDD due to suboptimal throughput. Finally, we propose hypergraphic LNC (HLNC), a novel throughput-optimal and APDD-approximating technique based on a hypergraphic model of receivers. Our simulations show that the APDD of HLNC significantly outperforms existing techniques, including RLNC, under all considered settings without any sacrifice on throughput.