Broadcast scheduling for information distribution

Broadcast data delivery is encountered in many applications where there is a need to disseminate information to a large user community in a wireless a symmetric communication environment. In this paper, we consider the problem of scheduling the data broadcast such that average response time experienc ed by the users is low. In a push-based system, where the users cannot plac e requests directly to the server and the broadcast schedule should be dete rmined based solely on the access probabilities, we formulate a determinist ic dynamic optimization problem, the solution of which provides the optimal broadcast schedule. Properties of the optimal solution are obtained and th en we propose a suboptimal dynamic policy which achieves average response t ime close to the lower bound. The policy has low complexity, it is adaptive to changing access statistics, and is easily generalizable to multiple bro adcast channels. In a pull-based system where the users may place requests about information items directly to the server, the scheduling can be based on the number of pending requests for each item. Suboptimal policies with good performance are obtained in this case as well. Finally, it is demonstr ated by a numerical study that as the request generation rate increases, th e achievable performance of the pull- and push-based systems becomes almost identical.