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

• Published in: Journal of parallel and distributed computing 2012-06, Vol.72 (6), p.819-826
• Main Authors: Rajasekaran, Sanguthevar, Fiondella, Lance, Sharma, Dolly, Ammar, Reda, Lownes, Nicholas
• Format: Article
• Language: English
• Subjects: Message routing; Radio networks; Randomized algorithms; Searching; Selection; Sorting
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2012.03.004

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) stand for a single-hop network that has p stations and k communication channels. The best known prior algorithm for sorting takes 4nk+o(nk) broadcast rounds on a 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) with high probability. The best known prior algorithms for the n/p-relations routing problem take nearly 2n/k time slots (i.e., broadcast rounds). An important open question has been if there exist algorithms that take only close to n/k time slots. Note that a trivial lower bound for routing is n/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/k rounds on the average. We also present a deterministic algorithm that takes nearly n/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.