Randomized parity forwarding in large-scale cooperative broadcast network

We present a randomized cooperative broadcasting technique that is flexible to topology changes and robust to transmission errors in large-scale wireless networks. A single source sends a common message (codeword) to all nodes, and those nodes that decode the message correctly then generate a parity bit (a partial information on the message) and broadcast it to the remaining nodes. The remaining nodes integrate the original codeword from the source with the network-generated parity bits to construct a lower rate, and thus more powerful, error correcting code. The protocol overhead is significantly reduced by allowing each node to randomly generate a parity bit independent of other nodes. We show that the probability of decoding error decreases exponentially with the number of nodes in the network, and that the performance degradation relative to the deterministic parity generation (that requires a centralized coordination of nodes) becomes smaller as the number of nodes increases. We also show that the proposed approach enables all nodes to correctly receive the message within the first cooperation stage if the number of nodes is sufficiently large. Hence, the proposed approach is promising for applications in large-scale wireless broadcast networks.