AbstractÐAd hoc networks are self-organizing entities that are deployed on demand in support of various events including collaborative computing, multimedia classroom, disaster-relief, search-and-rescue, interactive mission planning, and law enforcement operations. One of the fundamental tasks that have to be addressed when setting up an ad hoc network (AHN, for short) is initialization. This involves assigning each of the n stations in the AHN a distinct ID number (e.g., a local IP address) in the range from I to n. Our main contribution is to propose efficient randomized initialization protocols for AHNs. We begin by showing that if the number n of stations is known beforehand, an n-station, single-channel AHN can be initialized with probability exceeding I À I n , in en y n log n p time slots, regardless of whether the AHN has collision detection capability. We then go on to show that even if n is not known in advance, an n-station, single-channel AHN with collision detection can be initialized with probability exceeding I À I n , in IHn Q y n ln n p time slots. Using this protocol as a stepping stone, we then present an initialization protocol for the n-station, kchannel AHN with collision detection that terminates with probability exceeding I À I n , in IHn Qk y n ln n k q time slots. Finally, we look at the case where the collision detection capability is not present. Our first result in this direction is to show that the task of electing a leader in an n-station, single-channel AHN can be completed with probability exceeding I À I n , in fewer than IIXQUlog n P PXQW log n time slots. This leader election protocol allows us to design an initialization protocol for the n-station, single-channel AHN with no collision detection that terminates with probability exceeding I À I n , in fewer than SXTUn y n ln n p time slots, even if n is not known beforehand. We then discuss an initialization protocol for the n-station, k-channel AHN with no collision detection that terminates with probability exceeding I À I n , in fewer than SXTU n k y n ln n k q time slots, whenever k n log n Q .
A similar mechanism is employed in REF , bearing the difference that the probability is conditioned on the number of stations in the network and the probing message is sent regardless of the channel state.
Randomized Initialization Protocols for Ad Hoc Networks
IEEE Transactions on Parallel and Distributed Systems
Computer Science