Recently, there has been a growing interest of using network coding to improve the performance of wireless networks, for example, authors of proposed the practical wireless network coding system called COPE, which demonstrated the throughput gain achieved by network coding. However, COPE has two fundamental limitations: (1) the coding opportunity is crucially dependent on the established routes and (2) the coding structure in COPE is limited within a two-hop region only. The aim of this paper is to overcome these limitations. In particular, we propose DCAR, the distributed coding-aware routing mechanism which enables: (1) the discovery for available paths between a given source and destination and (2) the detection for potential network coding opportunities over much wider network region. One interesting result is that DCAR has the capability to discover high throughput paths with coding opportunities, while conventional wireless network routing protocols fail to do so. In addition, DCAR can detect coding opportunities on the entire path, thus eliminating the ¿two-hop¿ coding limitation in COPE. We also propose a novel routing metric called coding-aware routing metric (CRM) which facilitates the performance comparison between ¿coding-possible¿ and "coding-impossible¿ paths. We implement the DCAR system in ns-2 and carry out extensive evaluation. We show that when comparing to the coding mechanism in, DCAR can achieve much higher throughput gain.

Network coding is an attracting technology that has been shown to be able to improve the throughput of wireless networks. However, there still lacks fundamental understanding on how network coding works under realistic scenarios. In this paper, we examine the performance of a recently proposed network coding system under a realistic wireless physical layer and practical random access mechanisms. We propose a key performance measure called “encoding number”-the number of packets that can be encoded via network coding in each transmission. We provide an upper bound on the encoding number for the general coding topology, and derive the average encoding number and system throughput for a general class of random access mechanisms. Based on the practical coding system, we also derive a tighter upper bound on the throughput gain for a general wireless network. Our results are of fundamental value for coding-related MAC/Routing protocol design and analysis.

The practical network coding system proposed in (S. Katti et al., 2006) has two fundamental limitations: 1) the coding opportunity is crucially dependent on the established routes; 2) the coding structure is limited within a two-hop region. To overcome these limitations, we propose DCAR, the first distributed coding-aware routing mechanism which combines (a) the discovery for available paths between a given source and destination, and (b) the detection for potential network coding opportunities. DCAR has the potential to find high throughput paths with coding opportunities while conventional routing fails to do so. In addition, DCAR can detect coding opportunities on the entire path, thus eliminating the "two-hop" coding limitation in (S. Katti et al., 2006). We also propose a novel routing metric called "CRM" (coding-aware routing metric) which facilitates the comparison between coding-possible and coding-impossible paths. We implement the DCAR system in NS-2 and conduct extensive evaluation, which shows that DCAR achieves 7% to 20% throughput gain over the coding system in [1].

While the practical coding scheme has been shown to be able to improve throughput of wireless networks, there still lacks fundamental understanding on how the coding scheme works under realistic settings, namely, when it operates on a realistic physical layer and the medium access is controlled by some random access methods. In this paper, we provide a formal analysis on the performance of the practical coding scheme under such realistic settings. The key performance measure is the encoding number, i.e., the number of packets that can be encoded by a coding node in each transmission. We provide an upper bound on the encoding number for the general coding topology, and derive the average encoding number and system throughput for a general class of random access mechanisms. Based on the practical coding scheme, we also derive a tighter upper bound on the throughput gain for a general wireless network. Our results can be particularly useful for coding-related MAC/Routing protocol design and analysis.

Network coding has been shown to be able to improve the throughput of wireless networks. The authors have established fundamental understanding on how the coding scheme works under a realistic physical layer and practical link-scheduling algorithms. In the future, they aim at a complete system solution to incorporate network coding into the MAC and routing protocols, which can achieve higher efficiency in using potential coding opportunities and provide higher throughput. The results can serve as the prototype for future design of wireless networks embracing the network coding technology.