Header menu link for other important links
An efficient randomized routing protocol for single-hop radio networks
S. Rajasekaran, , R. Ammar, N. Lownes
Published in
Pages: 160 - 167
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. In a single-hop network 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 problems of sorting and selection have been studied on RN(p, k). For these problems it is assumed that there are n/p elements to start with at each station. At the end of sorting, the least n/p elements should be in the first station, the next smallest n/p elements should be in the second station, and so on. The best known prior algorithm for sorting takes 4n/k +o (n/k) broadcast rounds on a RN(p, k). In this paper we present a randomized algorithm that takes only 3n k + o (n/k) broadcast rounds with high probability. For the selection problem, it is known that the maximum or minimum element can be found in O(log n) rounds on a RN(n, 1), provided broadcast conflicts can be resolved in O(1) time. The problem of general selection has not been addressed. In this paper we present a randomized selection algorithm that takes O (p k) rounds on a RN(p, k) with high probability. An important message routing problem that is considered in the literature is one where there are n/p packets originating from each station and there are n/p packets destined for each station. The best known routing. © 2010 IEEE.
About the journal
Published in
Open Access
Impact factor