Efficient scheduling for relay-aided broadcasting with random network codes

We investigate efficient scheduling algorithms for a relay-aided broadcasting system using random network codes, where our objective is to maximize the transmission efficiency. The broadcast from a base-station (BS) is divided into an information phase and a redundancy phase, where the half-duplex relay assists in the redundancy phase. Time-division transmission is used over packet-erasure channels, where the erasure probabilities of the BS-to-relay and relay-to-user links are lower than the BS-to-user links. Following the information phase, each user provides feedback on the status of received packets to the BS and the relay, which in turn both generate redundancy packets for the redundancy phase. To improve efficiency, we formulate a scheduling problem for the transmissions of redundancy packets from the BS and the relay. We consider two scenarios; namely instantaneous feedback after each redundancy packet, and feedback after multiple redundancy packets. In the first case the schedule is determined using a greedy algorithm, while in the second case the schedule is determined using dynamic programming. To determine the performance with instantaneous feedback, we develop an analytic approach based on a Markov chain. Numerical results show that the transmission efficiency of the dynamic programming algorithm is close to the performance of the greedy algorithm, but requires significantly less feedback.