Randomized initialization protocols for packet radio networks

Publisher Website
Google Scholar
Abstract
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 from1 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/2n ; (2) initialize the k-channel PRN with CD capability in O( n/k ) rounds with probability at least 1 - 1/n , whenever k = n/3 log n ; (3) elect a leader on the single-channel PRN with no CD in O((log n)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/2vn ; (5) initialize the k-channel PRN with no CD in O( n/k ) broadcast rounds with probability at least 1 - 1/n , whenever k = n/4(log n)2.

This publication has 5 references indexed in Scilit: