Low Complexity Soliton Like Network Coding For A Resource Limited Relay

Network coding (NC) is an optimal data dissemination technique where intermediate nodes linearly combine incoming packets. To recover a network-coded message, a sink must use a Gaussian elimination decoder, but this high-complexity decoder may not be acceptable in resource-constrained applications like sensor networks. A good alternative to Gaussian elimination is for the sink to apply the well-known belief propagation (BP) algorithm; however, the performance and complexity of BP decoding is dependent on the statistics of the linearly-combined packets. In this work, we propose two protocols that address this issue by applying fountain coding paradigms to network codes. For a two-source, single-relay, and single-sink network, named the Y-network, if the relay can network-code incoming packets while maintaining the key properties of the fountain code, then BP decoding can be applied efficiently to recover the original message. Particularly, the sink should see a Soliton-like degree distribution for efficient BP decoding. The first protocol, named Soliton-like rateless coding (SLRC), recognizes that certain encoded packets are essential for BP decoding to perform well. Therefore, the relay protects these important packets by immediately forwarding them to the sink. It can be shown analytically that the proposed scheme is resilient to nodes leaving the transmission session. Through simulations, the SLRC scheme is shown to perform better than buffer-and-forwarding, and the Distributed LT code. Although SLRC achieves good performance, the degree distribution seen by the sink is non-optimal and assumes that a large number of packets can be buffered, which may not always be possible. Extending SLRC, we propose the Improved Soliton-like Rateless Coding (ISLRC) protocol. Assuming a resource-constrained relay, the available resources at the relay are effciently utilized by performing distribution shaping; packets are intelligently linearly combined. The aggregate degree distribution for the worst case is derived and used in performing an asymptotic error analysis using an AND-OR tree analysis. Simulation results show that even under the worst case scenario of ISLRC, better performance can be achieved compared to SLRC and other existing schemes.