UC Riverside

The challenges of gossiping and broadcasting in ad-hoc radio networks have been well-studied.Broadcasting, or one-to-all exchange, is dissemination of a message from a single source node to all other nodes in the network. Gossiping, or all-to-all exchange, is the dissemination of a message from each node to all other nodes in the network. Many-to-all exchange, on the other hand, has gone relatively unstudied in ad-hoc radio networks. We refer to this challenge as \textit{multi-broadcasting}. Due to the unstudied nature of multi-broadcasting, the fastest previously known deterministic algorithm was the $\Tilde{O}(n^{4/3})$ proposed in \cite{Gasieniec_etal_det_gossip_04}. If a network has a set $Q$ of nodes with messages where $|Q| = q < n$, we provide three different deterministic multi-broadcasting protocols under three different models. The first assumes knowledge of both the set $Q$ and the value $q$ and runs in time $O(qn\log n\log\log n)$. The second only assumes knowledge of the value of $q$, and runs in time $O(qn\log^3n)$. The final model has the same assumptions as the second model, with the additional knowledge that the nodes of $Q$ are at most a distance $\sigma$ apart. Under this model, multi-broadcasting can be completed in time $O(q^2\sigma\Delta\log^2n)$. Lastly, we provide a protocol that can determine the correct value of $q$ in $O(\log n)$ time, thus the need for knowledge of $q$ under the second and third models is not necessary at a small additional cost in runtime.