Leader Election for Multi-Channel Radio Networks - Dependent versus
                     Independent Trials

         Z.Golebiewski, M.Klonowski, M.Koza, M.Kutylowski


We consider scheduling access to a shared radio channel in networks where a 
set of stations tries to get the exclusive right to transmit over a shared radio 
channel. A frequent strategy to solve this problem is that each station independently
tosses an asymmetric coin and transmits in case of tails. The trials are executed 
some number of times and the first station  that sends alone in a trial gets the right
to broadcast over the shared channel. 

We consider here a multi-channel case: during one time slot a~station may transmit on 
$k$ different channels.  In this case trials can be arranged in two slightly different ways.
The first method is that in each trial a station decides whether to participate in it;
if it is so, then the station decides independently for each channel whether to transmit on it.
According to the second method a station makes one decision whether to send and if 
the decision is positive it chooses a SINGLE channel for transmission. The second method 
guarantees a limited energy cost for each station  but, as we show, turns out 
to be inferior regarding success probability and energy efficiency

We consider these algorithms for a realistic number of stations. We analyze subtle 
differences between  both algorithms regarding success probability.

Topic: 
Wireless communications
Keywords:
 radio channel access, leader election

accepted for: 
The First International Workshop on Computer Networks & Communications (CoNeCo-2009)
IEEE Computer Society Press,

This work was partially supported by EU within
the 7th Framework Programme under contract 215270 (FRONTS)