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).