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 O(n /k) broadcast rounds on the average case whenever k ≤ 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 ∈ [n/3ln_n, n/ln_n].