$k$-shot Broadcasting in Ad Hoc Radio Networks

Abstract

We study distributed broadcasting protocols with few transmissions (`shots') in radio networks where the topology is unknown. In particular, we examine the case in which a bound $k$ is given and a node may transmit at most $k$ times during the broadcasting protocol. Initially, we focus on oblivious algorithms for $k$-shot broadcasting, that is, algorithms where each node decides whether to transmit or not with no consideration of the transmission history. Our main contributions are (a) a lower bound of $\Omega (n^2/k)$ on the broadcasting time of any oblivious $k$-shot broadcasting algorithm and (b) an oblivious broadcasting protocol that achieves a matching upper bound, namely $O(n^2/k)$, for every $k\le \sqrt{n}$ and an upper bound of $O(n^{3/2})$ for every $k>\sqrt{n}$. We also study the general case of adaptive broadcasting protocols where nodes decide whether to transmit based on all the available information, namely the transmission history known by each. We prove a lower bound of $\Omega \left(n^{\frac{1+k}{k}}\right)$ on the broadcasting time of any protocol by introducing the \emph{transmission tree} construction which generalizes previous approaches.

21 pages, 2 figures, preliminary version presented in CATS 2011: 161-168