Flow Based XOR Network Coding for Lossy Wireless Networks

The broadcast nature of wireless links makes wireless networks an attractive environment for intersession network coding. Most intersession network coding protocols exploit this property, but ignore the diversity among the links by turning off coding when the channels are lossy. Other protocols deal with the packets separately - not as members of flows - which makes the intersession network coding problem with lossy links untractable. In this paper, we use a different approach by looking at flows or batches instead of individual packets. We characterize the capacity region of the 2-hop relay network when the coding operations are limited to XOR. The 2-hop relay network represents all of the local intersession network coding opportunities in large multihop networks. The characterization is in terms of linear equations. We also provide a coding scheme that can achieve the capacity with almost zero feedback overhead. Simulation results show that our scheme enhances the throughput by 82% while maintaining fairness among the flows compared to the intersession network coding protocols that deal with the packets separately.