Pull-based broadcasting with timing constraints
Qiu Fang, Susan V. Vrbsky, Hui-Chuan Chen, Yu Dang · International Journal of Parallel Emergent and Distributed Systems · 2005
The rapid growth in wireless and mobile computing has resulted in an increase in applications that would benefit from a broadcast system that considers timing constraints. Previously proposed scheduling algorithms for broadcast systems aim to minimize the mean access time, while our goal in this paper is to identify scheduling algorithms for broadcast systems that ensure requests meet their deadlines. We consider a pull-based approach in which users send explicit requests for data to a server. There are several well-known scheduling algorithms for real-time systems in non-mobile environments, and previous work in real-time mobile systems has utilized these scheduling algorithms to minimize missed deadlines. However, we demonstrate that traditional real-time algorithms do not always perform the best in a mobile environment and may perform worse than some non-real-time strategies. In this paper, we present a model of a pull-based real-time broadcast system and an analysis of the system as a Markov decision process (MDP). We also propose an efficient scheduling algorithm, called aggregated critical requests-β (ACR-β), which is designed for timely delivery of data to mobile clients. Our results indicate that ACR-β outperforms existing algorithms when timing constraints and the benefits of broadcasting are considered.