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
Khanna and Zhou @cite_6 proposed a sophisticated version of the index tree aimed at minimizing mean access and tuning time, for given probability of each data record being requested. The broadcast cycle contains multiple copies of data items, so that spacing between copies of each item is related to the optimal spacing, minimizing mean access time derived in @cite_18 . However the keys are not arbitrary. The key of the item is determined by its probability of being requested.
@cite_18 @cite_6
1691711714 2048152400
With the increasing popularity of portable wireless computers, mechanisms to efficiently transmit information to wireless clients are of significant interest. The environment under consideration is asymmetric in that the information server has much more bandwidth available, as compared to the clients. In such environments, often it is not possible (or not desirable) for the clients to send explicit requests to the server. It has been proposed that in such systems the server should broadcast the data periodically. One challenge in implementing this solution is to determine the schedule for broadcasting the data, such that the wait encountered by the clients is minimized. A broadcast schedule determines what is broadcast by the server and when. In this paper, we present algorithms for determining broadcast schedules that minimize the wait time. Broadcast scheduling algorithms for environments subject to errors, and systems where different clients may listen to different number of broadcast channels are also considered. Performance evaluation results are presented to demonstrate that our algorithms perform well. We consider the problem of efficient information retrieval in asymmetric communication environments where multiple clients with limited resources retrieve information from a powerful server who periodically broadcasts its information repository over a communication medium. The cost of a retrieving client consists of two components: (a) access time, defined as the total amount of time spent by a client in retrieving the information of interest, and (b) tuning time, defined as the time spent by the client in actively listening to the communication medium, measuring a certain efficiency in resource usage. A probability distribution is associated with the data items in the broadcast, representing the likelihood of a data item's being requested at any point of time. The problem of indexed data broadcast is to schedule the data items interleaved with certain indexing information in the broadcast so as to minimize simultaneously the mean access time and the mean tuning time. Prior work on this problem thus far has focused only on some special cases. In this paper we study the indexed data broadcast problem in its full generality and design a broadcast scheme that achieves a mean access time of at most (1.5+?) times the optimal and a mean tuning time bounded by O(logn).