Source author record

Marcin Kik

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Networking and Internet Architecture Discrete Mathematics Databases

Catalog footprint

Research overview

3works

5topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2012arXiv

Notes on Bit-reversal Broadcast Scheduling

This report contains revision and extension of some results about RBO [arXiv:1108.5095]. RBO is a simple and efficient 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 specified interval of the key values $[K', K"]$ . RBO receives at most $2 k + 1$ other frames' keys before receiving the first key from $[K', K"]$ or noticing that there are no such keys in the broadcast cycle. As a simple corollary, $4 k + 2$ is upper bound the number of keys outside $[K', K"]$ that will ever be received. In unreliable network the expected number of efforts to receive such frames is bounded by $(8 k + 4) / p + 2 (1 - p) / p^2$ , where $p$ is probability of successful reception, and the reception rate of the requested frames is $p$ -- the highest possible. The receiver's protocol state consists of the values $k$ , $K'$ and $K"$ , one wake-up timer and two other $k$ -bit variables. Its only nontrivial computation -- the computation of the next wake-up time slot -- can be performed in $O (k)$ simple operations, such as arithmetic/bit-wise operations on $k$ -bit numbers, using only constant number of $k$ -bit variables.

preprint2012arXiv

One-side Energy costs of the RBO receiver

Let $n = 2^k$ be the length of the broadcast cycle of the RBO broadcast scheduling protocol (see [arXiv:1108.5095] and [arXiv:1201.3318]). Let $lb$ and $ub$ be the variables of the RBO receiver as defined in [ arXiv:1201.3318 ]. We show that the number of changes of $lb$ (the "left-side energy") is not greater than $k + 1$ . We also show that the number of changes of $rb$ (the "right-side energy") is not greater than $k + 2$ . Thus the "extra energy" (defined in [arXiv:1201.3318]) is bounded by $2 k + 3$ . This updates the previous bound from [arXiv:1201.3318], which was $4 k + 2$ .

preprint2011arXiv

RBO Protocol: Broadcasting Huge Databases for Tiny Receivers

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).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.