On the Packet Decoding Delay of Linear Network Coded Wireless Broadcast.

We apply linear network coding (LNC) to broadcast a block of data packetsfrom one sender to a set of receivers via lossy wireless channels, assumingeach receiver already possesses a subset of these packets and wants the rest.We aim to characterize the average packet decoding delay (APDD), which reflectshow soon each individual data packet can be decoded by each receiver onaverage, and to minimize it while achieving optimal throughput. To this end, wefirst derive closed-form lower bounds on the expected APDD of all LNCtechniques under random packet erasures. We then prove that these bounds areNP-hard to achieve and, thus, that APDD minimization is an NP-hard problem. Wethen study the performance of some existing LNC techniques, including randomlinear network coding (RLNC) and instantly decodable network coding (IDNC). Weproved that all throughput-optimal LNC techniques can approximate the minimumexpected APDD with a ratio between 4/3 and 2. In particular, the ratio of RLNCis exactly 2. We then prove that all IDNC techniques are only heuristics interms of throughput optimization and {cannot guarantee an APDD approximationratio for at least a subset of the receivers}. Finally, we proposehyper-graphic linear network coding (HLNC), a novel throughput-optimal andAPDD-approximating LNC technique based on a hypergraph model of receivers'packet reception state. We implement it under different availability ofreceiver feedback, and numerically compare its performance with RLNC and aheuristic general IDNC technique. The results show that the APDD performance ofHLNC is better under all tested system settings, even if receiver feedback isonly collected intermittently.