Open AccessAverage case analysis‐based protocols to initialize packet radio networks
Author(s) -
Myoupo JeanFréderic,
Thimonier Loys,
Ravelomanana Vlady
Publication year - 2003
Publication title -
wireless communications and mobile computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.42
H-Index - 64
eISSN - 1530-8677
pISSN - 1530-8669
DOI - 10.1002/wcm.127
Subject(s) - computer science , probabilistic logic , network packet , protocol (science) , channel (broadcasting) , computer network , algorithm , probabilistic analysis of algorithms , discrete mathematics , mathematics , medicine , alternative medicine , pathology , artificial intelligence
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. in1, 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 ]. Copyright © 2003 John Wiley & Sons, Ltd.