A radio network (RN for short) is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations run on batteries and expends power while broadcasting/receiving a data packet. Thus, the most important measure to evaluate protocols on the radio network is the number of awake time slots, in which a station is broadcasting/receiving a data packet. We also assume that the stations are identical and have no unique ID number, and no station knows the number n of the stations. For given n keys one for each station, the ranking problem asks each station to determine the number of keys in the RN smaller than its own key. The main contribution of this paper is to present an optimal randomized ranking protocol on the k-channel RN. Our protocol solves the ranking problem, with high probability, in O(+log n) time slots with every station being awake for at most O(log n) time slots. We also prove that any randomized ranking protocol is required to run in expected Ω(+log n) time slots with at least one station being awake for expected Ω(log n) time slots. Therefore, our ranking protocol is optimal.

In this work we present an energy efficient leader election protocol for anonymous radio network populated with n mobile stations. Previously, Nakano and Olariu have presented a leader election protocol that terminates, with probability exceeding 1- (f ≥ 1), in log log n+o(log log n)+O(log f) time slots [14]. As the above protocol works under the assumption that every station has the ability to transmit and monitor the channel at the same time, it requires every station to be equipped with two transceivers. This assumption, however, is unrealistic for most mobile stations due to constraints in cost, size, and energy dissipation. Our main contribution is to show that it is possible to elect a leader in an anonymous radio network where each station is equipped with a single transceiver. Quite surprisingly, although every station has only one transceiver, our leader election protocol still runs, with probability exceeding 1- (f ≥ 1), in log log n+o(log log n)+O(log f) time slots. Moreover, our leader election protocol needs only expected O(n) total awake time slots, while Nakano and Olariu's protocol needs expected O(nlog log n) total awake time slots. Since every leader election protocol needs at least Ω(n) awake time slots, our leader election protocol is optimal in terms of the expected awake time slots.