PlayNCool: Opportunistic Network Coding for Local Optimization of Routing in Wireless Mesh Networks

This paper introduces PlayNCool, an opportunistic protocol with local optimization based on network coding to increase the throughput of a wireless mesh network (WMN). PlayNCool aims to enhance current routing protocols by (i) allowing random linear network coding transmissions end-to-end, (ii) recoding at intermediate nodes, and more importantly (iii) the identification and selection of helpers for each individual link. PlayNCool is easy to implement, compatible with existing routing protocols, and relies on simple intuition and closed-form, local optimization techniques. The intuition behind our protocol is that each helper to a link in a multi-hop path reinforces that link by listening to coded packets transmitted in the link and by judiciously choosing when to start transmitting to make the data exchange faster and more efficient. This paper pays special attention to techniques to determine how much a helper should wait before springing into action based on channel conditions for the optimization of a single link, i.e., the helper will play it cool by only speaking after it has heard enough to be truly useful. These techniques constitute a key feature of PlayNCool and are applicable in large scale mesh networks. We show that PlayNCool can provide gains of more than 3x in individual links, which translates into a large end-to-end throughput improvement, and that it provides higher gains when more nodes in the network contend for the channel at the MAC layer, making it particularly relevant for dense mesh networks.