Network coding-based protection of wireless mesh networks

Survivability of wireless mesh networks (WMNs) is a crucial issue that has not received enough attention in the literature. In this paper, we present a network coding-based protection scheme that overcomes the deficiencies in traditional proactive and reactive protection mechanisms. Proactive schemes ((1+1) protection) provide instantaneous recovery, but are resource-hungry. While reactive schemes ((1:N) protection) are efficient (in terms of used resources), but impose a delay and interrupt the network operation. Our approach provides protection to many-to-one flows at the speed of proactive protection, but at the cost of reactive protection. We derive the necessary and sufficient conditions for our solution on a restricted network topology, and then we adapt our solution to take into account general topologies. We also show how to perform deterministic network coding with {0,1} coefficients to achieve independence between linear combinations. Moreover, we discuss some practical considerations related to our network performance. Finally, we consider the implementation of our approach when all network nodes have single transceivers, where we solve the problem through a greedy algorithm that constructs a sub-optimal feasible schedule for the sources transmissions.