Randomized initialization protocols for ad hoc networks

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 n of stations is known beforehand, an n-station, single-channel AHN can be initialized with probability exceeding 1-(1/n), in en+O(/spl radic/(nlogn)) 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(/spl radic/(n 1n n)) 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(/spl radic/(n 1n n)/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 electing a leader in an n-station, single-channel AHN can be completed with probability exceeding 1-(1/n), in fewer than 11.37(iog n)/sup 2/+2.39 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 1-(1/n), in fewer than 5.67n+O(/spl radic/(n 1n n)) 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 1-(1/n), in fewer than 5.67(n/k)+O(/spl radic/(n 1n n)/k) time slots, whenever k/spl les/n/((log n)/sup 3/).