Date Added: Jul 2012
Broadcasting with network coding mixes different packets to minimize the number of transmissions, which improves the energy efficiency of wireless networks. On the other hand, delaying the transmissions increases coding opportunities at the intermediate nodes, but increases the delay of the packets. In this paper, the authors consider these two contradicting factors and study the problem of minimizing the number of transmissions in wireless networks while meeting the deadlines of different packets. They show that this problem is NP-complete; therefore, they provide a heuristic to solve the problem.