Randomized initialization protocols for ad hoc networks
Koji Nakano, Stephan Olariu · IEEE Transactions on Parallel and Distributed Systems · 2000
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 1 to n. Our main contribution is to propose efficient randomized initialization protocols for AHNs. We begin by showing that if the number 1 n of stations is known beforehand, an n-station, single-channel AHN can be initialized with probability exceeding 1 n,inen‡ p O … n log n† time slots, regardless of whether the AHN has collision detection capability. We then go on to show that even if n is not 1 known in advance, an n-station, single-channel AHN with collision detection can be initialized with probability exceeding 1 n,in