Randomized initialization protocols for ad hoc networks

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 n of stations is known beforehand, an n-station, single-channel AHN can be initialized with probability exceeding 1 - 1/n, in en + O(root logn) 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 1-1/n, in 10n/3 + O(root nInn) time slots. Using this protocol as a stepping stone, we then present an initialization protocol for the n-station, k-channel AHN with collision detection that terminates with probability exceeding 1 - 1/n, In 10n/3k + O(root uInn/k) 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 erecting a leader in an n-station, single-channel AHN can be completed with probability exceeding 1 - 1/n, in fewer than 11.37(logn)(2) + 2.39 log n time slots. This reader 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 1 - 1/n, in fewer than 5.67n + (O root nInn) 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 proability exceeding 1 - 1/n in fewer than 5.67n/k + O(root nInn/k) time slots; whenever k less than or equal to n/(log n)(5).