On adaptive deterministic gossiping in ad hoc radio networks

We study deterministic algorithms for gossiping problem in ad hoc radio networks. The gossiping problem is a communication task in which each node of the network possesses a unique single message that is to be communicated to all other nodes in the network. The efficiency of a communication algorithm in radio networks is very often expressed in terms of: max-eccentricity D, max-indegree Δ, and size (number of nodes) n of underlying graph of connections. The max-eccentricity D of a network is the maximum of the lengths of shortest directed paths from a node u to a node v, taken over all ordered pairs (u, v) of nodes in the network. The max-indegree Δ of a network is the maximum of indegrees of its nodes.We propose a new method that leads to several improvements in deterministic gossiping. It combines communication techniques designed for both known as well as unknown ad hoc radio networks. First we show how to subsume the O(Dn)-time bound yield by the Round-Robin procedure proposing a new Õ(√Dn)-time gossiping algorithm. Our algorithm is more efficient than the known Õ(n3/2)-time gossiping algorithms [3, 6], whenever D = O(nα) and α < 1. For large values of max-eccentricity D, we give another gossiping algorithm that works in time O(DΔ3/2 log3 n) which subsumes the O(DΔ2 log3 n) upper bound presented in [4].