Leader Election Algorithms for Multi-channel Wireless Networks.

We study the leader election problem in single-hop multi-channel wireless networks with single-antenna radio nodes. The objective is to elect leaders for all channels on which one or more nodes in the network can operate. We assume that nodes do not have collision detection capability. In this paper, we propose three algorithms for leader election: one deterministic and two randomized. The deterministic algorithm executes for at most 2N + M ⎡logM ⎤ time slots and guarantees leader election for all the channels, where M is the size of the universal channel set available to the nodes and N is the size of the label space used to assign unique labels to the nodes. The randomized algorithms guarantee that a leader is elected for all the channels with probability at least 1 − 1/f within ]> and O(M log(n _max ) log(Mf)) time slots, respectively, where n _max is the maximum number of nodes operating on any channel in the network. To the best of our knowledge, this is the first work on leader election in single-antenna multi-channel radio networks. [ABSTRACT FROM AUTHOR]