Date Added: Feb 2010
In this paper, the authors consider the problem of minimizing the mean completion delay in wireless broadcast for instantly decodable network coding. They first formulate the problem as a Stochastic Shortest Path (SSP) problem. Although finding the packet selection policy using SSP is intractable, they use this formulation to draw the theoretical properties of efficient selection algorithms. Based on these properties, they propose a simple online selection algorithm that efficiently minimizes the mean completion delay of a frame of broadcast packets, compared to the random and greedy selection algorithms with a similar computational complexity. Simulation results show that their proposed algorithm indeed outperforms these random and greedy selection algorithms.