Random network coding based optimal scheme for wireless packet retransmission problems

Network coding (NC) provides a new approach to solve wireless packet retransmission problems (WPRTPs). The property that the number of retransmitted packets of optimal NC-based schemes for a perfect WPRTP (P-WPRTP) equals to the maximum number of requested packets of a receiver was proposed and proved. Based on random network coding (RNC) technology, an optimal scheme for P-WPRTPs named as random network coding based optimal scheme(RNCOPT) was proposed where coefficients in network coding matrix are randomly selected from a pre-determined Galois field except for its element zero. Network coding matrix re-creation mechanism was used to guarantee a 100% success probability of decoding. Format of assembled packets and operation process of senders in RNCOPT were described. Simulation results show that, when receiver number and packet number are both 30, number of retransmitted packets in RNCOPT reduces about 32% when compared with traditional scheme where NC is not used, but meanwhile a typical NC-based scheme CliqueNC shows little performance gain.