Object scheduling in broadcast systems for energy-limited clients

摘要

Broadcast systems are popular in push-based information distribution environments, where subscribing clients are randomly switched on. The main problem in these systems is to construct a periodic (cyclic) schedule, where in every cycle each information object is transmitted several times, depending on its size and popularity. Existing algorithms consider memory-less clients and construct optimal schedules that optimize the aggregate access delay for objects; thus, they minimize client energy consumption. In this work, we analyze broadcast systems with memory equipped (caching) clients. We change the scheduling optimization criterion to include actual object reception time and thus, we provide a more realistic model for estimation of actual client power consumption. We prove that caching clients achieve reduced object reception time, leading to improved energy consumption. We give a simple proof that perfect periodicity in object transmission within scheduling cycles is necessary for optimal schedule, and calculate the conditions that optimal schedulers must satisfy. Since perfect periodicity is an NP-hard problem, we propose and analyze heuristic schedule modifications in order to achieve perfect periodicity for the more popular objects; heuristics include object transmission interleaving, preemptive transmission and exchange of object transmission order.