This report contains revision and extension of some results about RBO from [14]. RBO is a simple and ecient broadcast scheduling of n = 2 k uniform frames for battery powered radio receivers. Each frame contains a key from some arbitrary linearly ordered universe. The broadcast cycle a sequence of frames sorted by the keys and permuted by k-bit reversal is transmitted in a round robin fashion by the broadcaster. At arbitrary time during the transmission, the receiver may start a simple protocol that reports to him all the frames with the keys that are contained in a specied
In practical applications, due to imperfect synchronization between the broadcaster and the receiver, the header should also contain either the time-slot number or its bit reversal -- the index of the frame. To enable changing the contents and the length of the sequence of the transmitted keys by the broadcaster, the header may also include the parameter @math , such that @math is the length of the broadcast cycle, and some bits used to notify the receiver that the that the sequence of keys has been changed. For RBO, these issues have been discussed in @cite_7 .
@cite_7
1802425574
We propose a protocol (called RBO) for broadcasting long streams of single-packet messages over radio channel for tiny, battery powered, receivers. The messages are labeled by the keys from some linearly ordered set. The sender repeatedly broadcasts a sequence of many (possibly millions) of messages, while each receiver is interested in reception of a message with a specified key within this sequence. The transmission is arranged so that the receiver can wake up in arbitrary moment and find the nearest transmission of its searched message. Even if it does not know the position of the message in the sequence, it needs only to receive a small number of (the headers of) other messages to locate it properly. Thus it can save energy by keeping the radio switched off most of the time. We show that bit-reversal permutation has "recursive bisection properties" and, as a consequence, RBO can be implemented very efficiently with only constant number of @math -bit variables, where @math is the total number of messages in the sequence. The total number of the required receptions is at most @math in the model with perfect synchronization. The basic procedure of RBO (computation of the time slot for the next required reception) requires only @math bit-wise operations. We propose implementation mechanisms for realistic model (with imperfect synchronization), for operating systems (such as e.g. TinyOS).