Concatenated Random Parity Forwarding in Multi-source Multi-hop Wireless Networks

We present concatenated random parity forwarding technique that enables the network coding gain to increase with each additional hop in wireless multi-hop networks of multiple sources, multiple relays, and single destination. The increased network coding gain allows the nodes closer to the destination to reduce their transmit power. This feature is particularly useful in many-to-one type multi-hop wireless networks, where nodes located closer to the destination are expected to relay more data, and hence consume more energy. The proposed approach can compensate for this increased energy consumption by the enhanced network coding gain for the nodes closer to the destination. 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. The presented model incorporates random distribution of nodes in the network. We analyze the probability of decoding error and the network coding gain as a function of the the number of hops and network configurations.