Finding Coding Opportunities in the Air

Proposed recently, COPE, a promising network coding architecture for wireless mesh networks (WMN) efficiently increases the throughput of wireless networks. COPE, however, only handles XOR coding opportunities. In this paper, we find coding opportunities other than XOR. We formulate the status of a router in a WMN as a directed graph. Based on the graph, we propose a practical algorithm of finding coding opportunities, which corresponds to finding cycles in a graph. The computational complexity of our algorithm is O(n²), with n as the length of packet queue of a router. We simulate our algorithm with COPE architecture, and numerical results show that our algorithm increases the average coding gain by as large as 8.7%, compared to XOR coding.