Communication and energy efficient routing protocols for single-hop radio networks

In this paper, we study the important problems of message routing, sorting, and selection in a radio network. A radio network consists of stations where each station is a hand-held device. We consider a single-hop radio network where it is assumed that each station is within the transmission range of every other station. Let RN(p,k)RN(p,k) stand for a single-hop network that has pp stations and kk communication channels. The best known prior algorithm for sorting takes 4nk+o(nk) broadcast rounds on a RN(p,k)RN(p,k). In this paper, we present a randomized algorithm that takes only 3nk+o(nk) broadcast rounds with high probability. For the selection problem, we present a randomized selection algorithm that takes O(pk) rounds on a RN(p,k)RN(p,k) with high probability. The best known prior algorithms for the n/pn/p-relations routing problem take nearly 2n/k2n/k time slots (i.e., broadcast rounds). An important open question has been if there exist algorithms that take only close to n/kn/k time slots. Note that a trivial lower bound for routing is n/kn/k. The existence of such algorithms will be highly relevant, especially in emergencies and time-critical situations. In this paper, we answer this question by presenting a randomized algorithm that takes nearly n/kn/k rounds on the average. We also present a deterministic algorithm that takes nearly n/kn/k rounds. These routing algorithms are also shown to be energy efficient.

► We present efficient algorithms for routing on single-hop radio networks.
► Our routing algorithm matches the lower bound closely.
► We also present efficient sorting and selection algorithms.
► Energy efficiency is also taken into account.
► The communication cost model that we propose should be of interest as well.