  This paper is concerned with the problem of broadcasting information from a
source node to every node in an ad-hoc network. Flooding, as a broadcast
mechanism, involves each node forwarding any packet it receives to all its
neighbours. This results in excessive transmissions and thus a high energy
expenditure overall. Probabilistic forwarding or gossiping involves each node
forwarding a received packet to all its neighbours only with a certain
probability $p$. In this paper, we study the effect of introducing redundancy,
in the form of coded packets, into a probabilistic forwarding protocol.
Specifically, we assume that the source node has $k$ data packets to broadcast,
which are encoded into $n \ge k$ coded packets, such that any $k$ of these
coded packets are sufficient to recover the original $k$ data packets. Our
interest is in determining the minimum forwarding probability $p$ for a
"successful broadcast", which we take to be the event that the expected
fraction of network nodes that receive at least $k$ of the $n$ coded packets is
close to 1. We examine, via simulations and analysis of a number of different
network topologies (e.g., trees, grids, random geometric graphs), how this
minimum forwarding probability, and correspondingly, the expected total number
of packet transmissions varies with the amount of redundancy added. Our
simulation results indicate that over network topologies that are highly
connected, the introduction of redundancy into the probabilistic forwarding
protocol is useful, as it can significantly reduce the expected total number of
transmissions needed for a successful broadcast. On the other hand, for trees,
our analysis shows that the expected total number of transmissions needed
increases with redundancy.
