Feedback-assisted random linear network coding in wireless broadcast

The paper focuses on the reliable delivery of a stream of packets from a sender to a set of receivers over a lossy broadcast channel with limited receiver feedback. To facilitate efficient data transfer, the packets are grouped into generations. For each generation, we employ a two-phase coding scheme that transmits uncoded packets in the first phase and coded packets in the second phase. We assume that the packet reception status of receivers after the first phase is known through feedback. To enable tunable tradeoff between throughput, computational load, and packet decoding delay, we partition each generation into sub-generations, such that each coded packet is a linear combination of packets that belong to the same sub-generation. We focus on the optimal sub-generation partitioning problem which limits the number of transmissions required to deliver all packets that belong to each sub-generation. We show that this problem is NP-complete and present a heuristic algorithm for its solution. Our simulation results indicate that the proposed algorithm outperforms existing alternative solutions.