RBO protocol

by Marcin Kik   mki1967@gmail.com 

RBO is a protocol for broadcasting huge databases to tiny (battery powered) receivers (e.g. sensors).
Such receivers have limited energy resources and small amount of memory. 
They are equipped with radios that consume lot of energy when switched on.
The task of the RBO is to find a messages/frames with specific keys (attributes) in a very long stream of messages rebroadcast repeatedly by the base station.
During this search RBO can switch
the radio on and of. 

Let   k be a non-negative integer and let n = 2k.
For x in {0, ..., n-1},  let revBitsk(x) denote the number obtained by reversing the k bits of binary representation of x.
This is called bit-reversal of x.
The following image is a graph of the permutation y=revBits5
(x)  (i.e. of the bit-reversal permutation).
(Note that the y-axis is directed downwards.)

There is embeded "binary search tree"  in the graph:

Consider the structure of the binary search tree:
  1. Level zero contains single point (0,0).
  2. For l>0, level l contains 2l-1 points (x,y) with y in [2l-1 , 2l-1].
  3. For l>0, min { x  |  (x,y) is on level l } = 2k-l.
  4. For l>1,  min { x'-x  |  (x,y) and (x',y') are on level l and x<x' } = 2k-l+1.
  5. If (x',y') on level l is the left child of (x,y), then x'=x-2k-l.
  6. If (x'',y'') on level l is the right child of (x,y), then x''=x+2k-l.

Moreover each level of the tree has (recursively) the same structure.
The following image shows the binary search trees on the first level of recursion.

These properties of bit-reversal can be used for a simple and efficient periodic broadcast scheduling protocol 
for periodic tramission of large sets of data-records  labeled by some "keys" for the recivers that want to receive
only the records with some specific "keys".
(The "keys" do not have to be unique.)

The number of the records for transmission is an integer power of two. (We can duplicate  some records if necessary.)

The broadcasting server sorts the sequence of data-records by the "keys", and 
broadcasts this sorted sequence permuted by the bit-reversal permutation periodically (i.e. in a round-robin fashion).
(Each period of such transmission may last for a long time ...)

Each receiver, at arbitrary time moment may start the procedure to receive a record (or records)
with some specific "key".
The procotcol ensures that its radio-receiver has to be switched on only for receptions of short samples of the transmitted data
and yet it receives the nearest transmission of the requested record.
(If n is the size of the set of records then the number of the keys that need to be received to locate the searched one is
at most  2 log2 n+2.)

In the following revk( t )  denotes revBitsk( t mod 2k ).

The following figure describes operations of the RBO broadcaster and of the RBO receiver:

Below are some code  fragments from the prototype simultation implementation in Java. (The implementation on emulated TinyOS/NesC enviroment)

Bit-reversal function:

    public static int revBits(int k, int x)
    // reverse of k lowest bits
    int y= (x&1);
    for(int i=1; i<k; i++)
        y= y<<1;
        x= x>>1;
        y= (y | (x&1));
    return y;

nextSlotInk( t, r1,r2) = (t + min{ d>0  :  r1<= revBits( (t+d) mod 2k ) <= r2 }) mod 2k     is the number (modulo 2k) of the next slot with the rank in [r1 , r2].
Computations of nextSlotIn:

If   2k /  (r2-r1) is small, then we can naively check time slots:  (t+1) mod 
2k,     (t+2) mod  2k,   ...

    public static int naiveNextSlotIn(int k, int t, int r1, int r2)
    // (t+min{d>0 : r1<= revBits( (t+d)mod 2^k   ) <=r2}) mod 2^k
    // we assume 0<=r1<=r2< 2^k
    int mask=(1<<k)-1; // 2^k-1
    t=((t+1) & mask);  // (t+1) mod 2^k
    int r=revBits(k, t);
    while(r<r1 || r2<r)
        t=((t+1) & mask);
        r=revBits(k, t);
    return t;

If   r2-r1 is small, the we can naively check time slots:   revBitsk(r1), revBitsk(r1+1), ..., revBitsk(r2)

    public static int reverseNextSlotIn(int k, int t, int r1, int r2)
    // (t+min{d>0 : r1<= revBits( (t+d)mod 2^k   ) <=r2}) mod 2^k
    // we assume 0<=r1<=r2< 2^k
    int n=(1<<k);
    int t1=revBits(k, r1);
    int globalMin=t1;
    int minAfter=(t1>t)? t1: n;
    for(int r=r1+1; r<=r2; r++)
        t1=revBits(k, r);
        if(t1<globalMin) globalMin=t1;
        if(t1>t && t1<minAfter) minAfter=t1;
    if(minAfter<n) return minAfter;
    else return globalMin;

If both
r2-r1  and 2k /  (r2-r1)  are large, then the following algorithm is much more efficient (new version explained in http://arxiv.org/abs/1201.3318):

    public static int nextIn(int k, int t, int r1, int r2) // new version
    // (t+min{d>0 : r1<= revBits(k, (t+d)mod 2^k   ) <=r2}) mod 2^k 
    // we assume 0<=r1<=r2< 2^k 
        int twoToK=(1<<k); // 2^k
  int modMaskK= twoToK-1; // 2^k-1
        int t1,x1,x2, stepDivMask; 
  int twoToL=1;
  int stepLMinusOne=modMaskK;
  int tNext=((t+1)&modMaskK); 
  while(twoToL<twoToK && (t1&twoToL)==0) 
                stepDivMask=((~stepLMinusOne) & modMaskK);
                x2= (x1 | stepDivMask );
       }while( r1>x2 || r2<x1 || ((r1-x1+stepLMinusOne)&stepDivMask)>((r2-x1)&stepDivMask) ); 
  int s= (twoToK>>1); // 2^(k-1)
        while(x1<r1 || x1>r2)
  if(x1<r1) x1=x1+s;
  else x1=x1-s;
  return revBits(k, x1); // this result is modulo 2^k

The following figure contains more readable pseudocode of this algoritm:

The implementation in Go Programming Language of NSI has been placed in: https://github.com/mki1967/rbo

The following figure illustrates that nsik(t-1, 9,7) = nextIn(k, t-1, 9, 7) = 18, for k=5 and t=6: