Profit-based scheduling and channel allocation for multi-item requests in real-time on-demand data broadcast systems

On-demand broadcast is a widely accepted approach for dynamic and scalable wireless information dissemination systems. With the proliferation of real-time applications, minimizing the request deadline miss ratio in scheduling multi-item requests has become an important task in the current architecture. In this paper, we prove the NP-hardness of broadcast scheduling of real-time multi-item requests in both single- and multi-channel environments. Furthermore, we propose two profit-based scheduling algorithms, PVC and SSA, for single- and multi-channel scheduling, respectively, both of which utilize our new concept "profit" of pending items and "opportunity cost" of pending requests. To the best of our knowledge, it is also the first time to introduce opportunity cost, which is derived from economics, into on-demand broadcast scheduling. Based on the scheduling result of PVC for pending requests, SSA is proposed to allocate selected items of scheduled requests to available channels. Finally, simulation results show great improvement in comparison with traditional algorithms. In general, PVC for single channel scheduling is superior to the best of other algorithms in terms of request deadline miss ratio. For multi-channel scheduling, SSA has larger advantage with increasing number of channels in terms of request deadline miss ratio than the best of other algorithms. © 2011 Elsevier B.V. All rights reserved.