Header menu link for other important links
Communication and energy efficient routing protocols for single-hop radio networks
S. Rajasekaran, L. Fiondella, , R. Ammar, N. Lownes
Published in
Volume: 72
Issue: 6
Pages: 819 - 826
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 np-relations routing problem take nearly 2nk time slots (i.e., broadcast rounds). An important open question has been if there exist algorithms that take only close to nk time slots. Note that a trivial lower bound for routing is nk. 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 nk rounds on the average. We also present a deterministic algorithm that takes nearly nk rounds. These routing algorithms are also shown to be energy efficient. © 2012 Elsevier Inc. All rights reserved.
About the journal
Published in
Open Access
Impact factor