General Network Coding Conditions in Multi-Hop Wireless Networks

Network coding is known as a promising approach to improve wireless network throughput. However, it is only applicable when different flows are routed through a certain coding structure. One of the fundamental issues is to accurately identify the coding structures and optimally utilize the coding nodes. In this paper, we formally establish general coding conditions to identify multiple coding nodes along a path, while most of the existing approaches may ignore the coding opportunities or bring in potential negative impact on other flows. The general coding condition is further augmented with a flow selection mechanism, which determines the set of flows to be coded at a coding node. Not only native packet but also encoded packet could be involved in the selection mechanism. Combination of the proposed coding conditions and the flow selection mechanism ensures that all the flows involved in coding can be properly decoded at the destinations. We implement the proposed coding conditions and flow selection mechanism over the AODV protocol, and efficiency of the proposed techniques is demonstrated with NS2 simulations, compared to the existing coding conditions.