Concatenated Random Parity Forwarding in Large-Scale Multi-Hop Relay Networks

We present concatenated random parity forwarding technique that enables the network coding gain to increase with each additional hop in wireless networks of multiple sources, multiple relays, and single destination. It is a multi-hop based relay cooperation approach that concatenates the parity bits generated by the relay nodes in the previous hops with those in the next hop. The increased network coding gain allows the nodes closer to the destination to reduce their transmit power. This feature is particularly useful in compensating their increased energy consumption from relaying more data. The proposed approach also improves in efficiency as the network scale increases, which is desirable in building a large-scale network. The parity bits are generated independently and randomly at the relays from some finite field, and forwarded to the next node. This makes the protocol overhead minimal in coordinating the relay nodes and enables a decentralized network operation. Also, it allows relay nodes to be easily added with little overhead as the network scale increases. We analyze the probability of decoding error and the network throughput as a function of the the number of hops and network configurations.