Reliable broadcast transmission in wireless networks based on network coding

Recently, XOR based network coding has been applied to the loss recovery of reliable broadcast transmission in wireless networks, where the source can XOR multiple lost packets with distinct receivers together into one packet and transmits this combined packet in one retransmission, resulting in a significant improvement on transmission efficiency. The problem of finding the optimal XOR coding set that minimizes the overall number of transmissions for loss recovery has been proved to be NP-hard. In this paper, we propose an efficient heuristic algorithm based on vertex coloring for giving an approximately optimal solution to address the problem, and then apply this heuristic algorithm into the existing XOR-based retransmission schemes. Simulation results are given to demonstrate superior performance of our algorithm over previously proposed works.