Controlled Gossiping in Ad Hoc Networks

Gossiping, a probabilistic algorithm for network-wide broadcasting, can significantly reduce the number of transmissions in one-to-all message spread. Based on the Continuum Percolation Theory, we develop a novel analytical model of gossiping for wireless ad hoc networks. This model provides an intuitive way for setting the gossiping probability, so that a gossip achieves high degree of network coverage with limited number of transmissions. We also propose and study a distributed gossiping scheme, in which nodes set their gossiping probabilities according to locally acquired information. Both gossiping schemes are demonstrated to be scalable; i.e., for fixed network area, the expected number of gossip transmissions does not depend on the number of nodes in the network. The analytical results are verified via simulations of large ad hoc networks.