Energy-Efficient Size Approximation of Radio Networks
with no Collision Detection
Tomasz Jurdzinski, Miroslaw Kutylowski, Jan Zatopianski
Algorithms for radio networks are studied in two scenarios:
(a) the number of active stations is known (or approximately known)
(b) the number of active stations is unknown. In the second (more
realistic) case it is much harder to design efficient algorithms.
For this reason, we design an efficient randomized algorithm for a
single-hop radio network that approximately counts the number of its
active stations. With probability higher than 1-1/n, this approximation
is within a constant factor, the algorithm runs in poly-logarithmic time
and its energy cost is o(loglog n). This improves the previous O(log n)
bound for energy. In particular, our algorithm can be applied to improve
energy cost of known leader election and initialization protocols
(without loss of time efficiency).