Randomized initialization protocols for packet radio networks
Tatsuya Hayashi, Koji Nakano, Stephan Olariu · 2003
The main contribution of this work is to propose efficient randomized leader election and initialization protocols for Packet Radio Networks (PRN, for short). As a result of the initialization protocol, the n stations of a PRN are assigned distinct integer IDs from 1 to n. The results include protocols to: (1) initialize the single-channel PRN with the collision detection (CD) capability in O(n) rounds with probability at least 1-1/(2/sup n/); (2) initialize the k-channel PRN with CD capability in O(n/k) rounds with probability at least 1-1/n, whenever k/spl les/n/3 log n; (3) elect a leader on the single-channel PRN with no CD in O((log n)/sup 2/) broadcast rounds with probability at least 1-1/n; (4) initialize the single-channel PRN with no CD in O(n) rounds with probability at least 1-1/(2/spl radic/n); (5) initialize the k-channel PRN with no CD in O(n/k) broadcast rounds with probability at least 1-1/n, whenever k/spl les/n/(4(log n)/sup 2/).