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