Bit Reversal Broadcast Scheduling for Ad Hoc Systems

                   Marcin Kik, Maciej Gebala, Miroslaw Kutylowski

                   Wroclaw University of Technology
                   
We consider the scenario where a broadcaster sends messages to an ad
hoc subset of receivers. We assume that once a receiver becomes active, it must
receive all messages directed to it.
The problem considered in this paper is minimization of the energy usage for
the receiver. As most of the energy is spent for the receiver’s antenna, our goal is
to minimize the time period, when this antenna is active.
In this paper we present and analyze RBO broadcast scheduling protocol that
attempts to minimize the extra energy usage due to receiving messages that in fact
are not meant for the receiver. While RBO scheme enjoys such important proper-
ties like correctness in case of transmission failures and ease of implementation,
estimating extra energy cost requires a lot of effort.
In this paper we present tight upper bounds for this extra energy together with
a rigorous proof. Namely, for a broadcast cycle of length 2k we show that the
overhead is limited to 2k + 3 extra messages, while there are cases where the
overhead is 2k − 1 extra messages. As it is hard to imagine how to break this
upper bound, RBO might be a good choice for broadcast scheduling, when energy
efficiency and ease to implementation are concerned.

Keywords: broadcast, ad hoc system, scheduling, energy cost, upper bound.

presented as invited paper at IDCS'2013