Average case analysis-based protocols to initialize packet radio networks
We propose two randomized protocols by which n (n not known) initially identical stations of a Packet Radio Network (PRN) are assigned ID numbers from 1 to n to distinguish them. They run regardless of the number of stations per channel. The first one is a naive protocol and is derived from recursive probabilistic divide-and-conquer techniques. It requires n/ln k broadcast rounds, where k is the number of communication channels. The second solution needs the well-known prefix sums algorithm and we show that in this scenario the described protocol terminates in 0(n/k) broadcast rounds on the average case whenever k less than or equal to n/ln n. These results are obtained by means of the average case analysis of algorithms, using probabilistic generating functions and formal methods. Surprisingly, our last protocol performs as well as the efficiency-oriented protocol of Hayashi et al. in [1,2], which depends on the number of stations per channel. And moreover, it can handle the case where k is an element of [n/3 Inn, n/ln n]. Copyright (C) 2003 John Wiley Sons, Ltd.
broadcast communication model wireless networks personal communication systems mobile computing parallel algorithms