Average case analysis‐based protocols to initialize packet radio networks
Jean‐Frédéric Myoupo, Loÿs Thimonier, Vlady Ravelomanana · Wireless Communications and Mobile Computing · 2003
Abstract 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/lnk 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/lnn. 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/3lnn, n/lnn]. Copyright © 2003 John Wiley & Sons, Ltd.