**
Near-Optimal Radio Use For Wireless Network Synchronization
**

*
Milan Bradonjic, Eddie Kohler, Rafail Ostrovsky
*

**
Abstract:
**

In this paper we consider the model of communication where
wireless devices can either switch their radios off to save energy
(and hence, can neither send nor receive messages), or switch
their radios on and engage in communication. The problem has been extensively studied in practice, in the setting such as deployment and clock synchronization of wireless sensor networks.
See, for example,[31,41,33,29,40]The goal in these papers is different from the classic problem of radio broadcast, i.e. avoiding interference. Here, the goal is instead to
minimize the use of the radio for both transmitting and receiving, and for most of the time to shut the radio down completely, as the radio even
in listening mode consumes a lot of energy.
Somewhat surprisingly, in the theoretical community, this model has not been studied.
We distill a clean theoretical formulation of minimizing radio use and present near-optimal solutions.
Our base model ignores issues of communication interference,
although we also extend the model to handle this requirement. %as well.
We assume that nodes intend to communicate
periodically, or according to some time-based schedule.
Clearly, perfectly synchronized devices could switch their radios
on for exactly the minimum periods required by their joint
schedules.
The main challenge in the deployment of wireless networks is to \emph{synchronize} the devices'
schedules, given that their initial schedules may be offset
relative to one another (even if their clocks run at the same
speed).
In this paper we study how frequently the devices must switch on
their radios in order to both synchronize their clocks and
communicate. In this setting, we significantly improve previous results, and show optimal use of the radio for two processors
and near-optimal use of the radio for synchronization of an
arbitrary number of processors.
In particular, for two processors we prove {** deterministic **} matching \Theta\left(\sqrt{n}\right) upper and lower
bounds on the number of times the radio has to be on, where n is
the discretized uncertainty period of the clock shift between the
two processors. (In contrast, all previous results for two processors are
randomized, e.g.~\cite{palchaudhuri04},~\cite{moscibroda06}).
For m=n^\beta processors (for any positive \beta < 1) we prove
\Omega(n^{(1-\beta)/2}) is the lower bound on the number of times
the radio has to be switched on (per processor), and show a nearly
matching (in terms of the radio use)
\~{O}(n^{(1-\beta)/2}) randomized
upper bound per processor, (where \~{O} notation hides {\em poly-log}(n) multiplicative term) with failure probability exponentially
close to 0. For \beta \geq 1 our algorithm runs with at most
{\em poly-log)(n) radio invocations per
processor.
Our bounds also hold in a radio-broadcast model where
interference must be taken into account.

**comment:**
ALGOSENSORS-2009

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |