  Many ad hoc routing protocols are based on some variant of flooding. Despite
various optimizations, many routing messages are propagated unnecessarily. We
propose a gossiping-based approach, where each node forwards a message with
some probability, to reduce the overhead of the routing protocols. Gossiping
exhibits bimodal behavior in sufficiently large networks: in some executions,
the gossip dies out quickly and hardly any node gets the message; in the
remaining executions, a substantial fraction of the nodes gets the message. The
fraction of executions in which most nodes get the message depends on the
gossiping probability and the topology of the network. In the networks we have
considered, using gossiping probability between 0.6 and 0.8 suffices to ensure
that almost every node gets the message in almost every execution. For large
networks, this simple gossiping protocol uses up to 35% fewer messages than
flooding, with improved performance. Gossiping can also be combined with
various optimizations of flooding to yield further benefits. Simulations show
that adding gossiping to AODV results in significant performance improvement,
even in networks as small as 150 nodes. We expect that the improvement should
be even more significant in larger networks.
