Network Coding-Based Protection of Many-to-One Wireless Flows

This paper addresses the problem of survivability of many-to-one flows in wireless networks, such as wireless mesh networks (WMNs) and wireless sensor networks (WSNs). Traditional protection schemes are either resource-hungry like the (1 + 1) protection scheme, or introduce a delay and interrupt the network operation like the (1 : N) protection scheme. In this paper, we present a network coding-based protection technique that overcomes the deficiencies of the traditional schemes. We derive and prove the necessary and sufficient conditions for our solution on a restricted network topology. Then we relax these connectivity requirements and show how to generalize the sufficient and necessary conditions to work with any other topology. We also show how to perform deterministic coding with {0,1} coefficients to achieve linear independence. Moreover, we discuss some of the practical considerations related to our approach. Specifically, we show how to adapt our solution when the network has a limited min-cut; we therefore define a more general problem that takes this constraint into account, which prove to be NP-complete. Furthermore, we discuss the decoding process at the sink, and show how to make use of our solution in the upstream communication (from sink to sources). We also study the effect of the proposed scheme on network performance. Finally, we consider the implementation of our approach when all network nodes have single transceivers, and we solve the problem through a greedy algorithm that constructs a feasible schedule for the transmissions from the sources.