RBO Protocol: Broadcasting Huge Databases for Tiny Receivers

Details RBO Protocol: Broadcasting Huge Databases for Tiny Receivers RBO Protocol: Broadcasting Huge Databases for Tiny Receivers

2011-08-25

arxiv.org/abs/1108.5095v1

Computer Science

Data Structures and Algorithms

Scientific paper

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 $\log_2 n$-bit variables, where $n$ is the total number of messages in the sequence. The total number of the required receptions is at most $2\log_2 n +2$ in the model with perfect synchronization. The basic procedure of RBO (computation of the time slot for the next required reception) requires only $O(\log^3 n)$ bit-wise operations. We propose implementation mechanisms for realistic model (with imperfect synchronization), for operating systems (such as e.g. TinyOS).

Affiliated with

Also associated with

No associations

Rating

RBO Protocol: Broadcasting Huge Databases for Tiny Receivers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with RBO Protocol: Broadcasting Huge Databases for Tiny Receivers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and RBO Protocol: Broadcasting Huge Databases for Tiny Receivers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-319223