Bit Reversal Broadcast Scheduling for Ad Hoc Systems^*

Abstract

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 properties 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 2^k 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.

Published in Proceedings of 6th International Conference on Internet and Distributed Computing Systems, IDCS 2013, Hangzhou, China, October 28-30, 2013, Lecture Notes in Computer Science, vol. 8223, Springer-Verlag 2013, pp. 223-237.

^* Supported by project "Detectors and sensors for measuring factors hazardous to environment -- modeling and monitoring of threats", financed by the European Union via the European Regional Development Fund and the Polish state, Operational Programme Innovative Economy 2007-2013. Ref. No. POIG.01.03.01-02-002/08-00.

Conference paper