On-demand data broadcast (ODDB) has attracted increasing interest due to its efficiency of disseminating information in many real-world applications such as mobile social services, mobile payment and mobile e-commerce. In an ODDB system, the server places client requested data items received from the uplink to a set of downlink channels for downloading by the clients. Most existing work focused on how to allocate client requested data items to multiple channels for efficient downloading, but did not consider the time constraint of downloading which is critical for many real-world applications. For a set of requests with deadlines for downloading, this paper proposes an effective algorithm to broadcast data items of each request within its specified deadline using multiple channels under the well-known 2-conflict constraint: two data items conflict if they are broadcast in the same time slot or two adjacent time slots in different channels. Our algorithm adopts an approach of allocating most urgent and popular data item first (UPF) for minimizing the overall deadline miss ratio. The performance of the UPF method has been validated by extensive experiments on real-world data sets against three popular on-demand data broadcast schemes.
- Download deadline
- On-demand data broadcast