Broadcast-efficient protocols for mobile radio networks

The main contribution of this work is to present elegant broadcast-efficient protocols for permutation routing, ranking, and sorting on single-hop Mobile Radio Networks with $p$ stations and $k$ radio channels, denoted by ${\rm MRN} (p,k)$. Clearly, any protocol performing these tasks on $n$ items must perform $n\over k$ broadcast rounds because each item must be broadcast at least once. We begin by presenting an optimal off-line permutation routing protocol using $n\over k$ broadcast rounds for arbitrary $k$, $p$, and $n$. Further, we show that optimal on-line routing can be performed in $n\over k$ broadcast rounds, provided that either $k=1$ or $p=n$. We then go on to develop an on-line routing protocol that takes $2{n\over k}+k-1$ broadcast rounds on the ${\rm MRN} (p,k)$, whenever $k\leq \sqrt{p\over 2}$. Using these routing protocols as basic building blocks, we develop a ranking protocol that takes $2{n \over k}+o({n\over k})$ broadcast rounds as well as a sorting protocol that takes $3{n \over k}+o({n\over k})$ broadcast rounds, provided that $k\in o(\sqrt{n})$ and $p=n$. Finally, we develop a ranking protocol that takes $3{n \over k}+o({n\over k})$ broadcast rounds, as well as a sorting protocol that takes $4{n \over k}+o({n\over k})$ broadcast rounds on the ${\rm MRN} (p,k)$, provided that $k \leq\sqrt{p\over 2}$ and $p\in o(n)$. Featuring very low proportionality constants, our protocols offer a vast improvement over the state of the art.