R-Code: Network coding-based reliable broadcast in wireless mesh networks

Broadcast is an important communication primitive in wireless mesh networks (WMNs). Applications like network-wide software updates require reliable broadcast to ensure that every node in the network receives the information completely and correctly. With underlying unreliable wireless links, a key challenge in implementing reliable broadcast in WMNs is to achieve 100% information reception rate at every node with high communication efficiency and low latency. Recently, network coding has emerged as a promising coding scheme in terms of communication efficiency especially for one to many communication patterns. In this paper, we put forward R-Code, a network coding-based reliable broadcast protocol. We introduce a guardian-ward relationship between neighboring nodes that effectively distributes the responsibility of reliable information delivery - from the global responsibility of the source to the localized responsibilities of guardians to their corresponding wards. We use a link quality-based minimum spanning tree as a backbone to guide the selection of guardians adaptively and the transmission of coded packets accordingly. Opportunistic overhearing is also utilized to improve the performance of the protocol. Extensive simulation results show that R-Code achieves 100% packet delivery ratio (PDR), while enjoying significantly less transmission overhead and shorter broadcast latency, compared with a state-of-the-art reliable broadcast protocol, AdapCode. (C) 2010 Elsevier B.V. All rights reserved.