Weak communication in single-hop radio networks -- 
Adjusting algorithms to industrial standards
 
Tomasz Jurdzinski, Miroslaw Kutylowski, Jan Zatopianski
 

Quite  often  algorithms  designed  for   no-collision-detection   radio
networks  use a hidden form of collision detection: it is assumed that a
station can simultaneously send and listen. Then, if it cannot hear  its
own  message,  then apparently the message has been scrambled by another
station sending at the same time.

Industrial  standard  IEEE 802.11 says that a station can either send or
listen to a radio channel at a given time, but not  both.  In  order  to
relate  the industrial standard and theoretical algorithms we consider a
\textit{weak} radio network model with no collision detection in which a
station  cannot  simultaneously  send  and receive signals. Otherwise we
talk about strong model.

In  this  paper  we  consider  a measure called energy cost (or ``power
consumption'') which is equal to the maximum over all  stations  of  the
number of steps in which the station is sending or listening.

We show that computational power of weak  and  strong  single-hop  radio
networks  differ  substantially in the deterministic case: deterministic
leader election requires Omega(log n) energy cost in the weak model  and
can be solved {by a practical algorithm} with O(sqrt(log n)) energy cost
in the strong model. On the other hand,  we  present  a  very  efficient
randomized  simulation  of  strong  radio  networks  by  weak ones, with
preprocessing that requires O(n) steps and has energy cost O(loglog n).