Network coding based schemes for imperfect wireless packet retransmission problems : A divide and conquer approach

NC (Network Coding) provides a new approach to packet retransmission problems in wireless networks, which are named as WPRTPs (Wireless Packet Retransmission Problems) in this paper. Some research has been conducted on P-WPRTPs (Perfect WPRTPs) where, for one receiver, a packet is either being requested by or already known to it. However, very few efforts are focused on IP-WPRTPs (Imperfect WPRTPs) where, for one receiver, a packet can be neither requested by nor already known to it. In this paper, we focus on IP-WPRTPs. Firstly, a WPRTP reduction theorem for simplifying WPRTPs is proposed and proved. Then, the upper and lower bounds of the number of necessary packet transmissions in optimal NC-based solutions to IP-WPRTPs are analyzed. Next, a scheme named as IP-WPRTP-DC (Divide and Conquer based scheme for IP-WPRTPs) is proposed based on the WPRTP reduction theorem using a divide and conquer approach. Extensive simulations show that the IP-WPRTP-DC scheme is effective in saving the number of packet transmissions for solving IP-WPRTPs. © 2010 Springer Science+Business Media, LLC.