Gossiping in multihop radio networks

Gossiping is when each node in the network has some information that it needs to communicate to every other node in the network. Updating of routing information in communication networks and exchange of data in control networks that use a form of distributed control, where status data from every node needs to be made available at every other node in the network, are some of the practical applications of gossiping. A gossip scheduling algorithm is used to schedule the transmissions times of the nodes and the message to be transmitted by them at these times. A good gossip scheduling algorithm should be computationally feasible and provide a schedule that achieves gossip quickly. We investigate and propose gossip algorithms for multihop radio networks. Assuming slotted operation of a single frequency multihop radio network with unit length messages and a node transmitting at most one message in each slot, we propose three gossip scheduling algorithms for general topologies: collision-free, centralised-spanning-tree and gather-scatter gossip scheduling algorithms. Of these three our experimental results indicate that the gather-scatter algorithm is possibly among the best gossip scheduling algorithm for multihop radio networks. For all these three algorithms we have measured the performance (the number of slots to achieve gossip) using an experimental model that is a realistic representation of real-life radio networks. We also overview our results for gossip schedule lengths in complete graph, star, ring and bus topologies