Minimizing the Access Time of Multi-item Requests in Wireless Data Broadcast Environments

Wireless data broadcast is an efficient way to disseminate data to a large number of users in mobile communication environments. In many applications, such as stock quotes, flight schedules and traffic news, the users may want to download multiple data items at one time and the applications may require the support of multi-channel architectures. This paper studies the problem of retrieving a set of data items from multiple wireless broadcasting channels such that all the requested data items can be downloaded with the least access time, namely Least Time Data Retrieval (LTDR). On one hand, we find that it is NP-hard to approximate this problem to within any non-trivial factor even if there are only two channels. On the other hand, we find that there exists a polynomial time (1+1/1-α)-approximation solution for an LTDR instance L if the optimal solution of L requirers τ time slots and (1-α)kT ≤ τ ≤ kT, where k is a positive integer, α is an arbitrary constant between 0 and 1, and T is the least common multiple of cycle lengths for all channels. We also derive a lower bound of polynomial time approximation for L matching that upper bound under the well known assumption P ≠ NP. To improve the practical efficiency of the approximation solution, a heuristic is exhibited and tested by simulations.

I. Introduction

In wireless broadcasts, data items are disseminated cyclically via a set of wireless channels. Clients (or users) can access the available channels and download any data items of interests. Compared with point-to-point data communications, wireless data broadcasts allow a large number of mobile clients to access data simultaneously, and thus are more scalable and flexible [25]. Generally, there are two major performance concerns for wireless data broadcast systems. One is tuning time and the other is access time. Tuning time is the performance criterium to evaluate the energy efficiency; while access time, defined as the time duration from the moment a request is submitted to the moment all the requested data items are downloaded, reflects the response delay. In this study, we assume the broadcasting time of requested data items are known, and we study the data retrieval scheduling for multi-item requests from the clients' point of view. The objective is to minimize the access time of a given request. Actually, there are three factors that affect the access time of requests: 1)

Consider the network's point of view, a straightforward way to minimize the average access time is to increase the system throughput. The Orthogonal Frequency-Division Multiplexing (OFDM) technique makes efficiently broadcasting data through multiple channels possible [27]. Over the past decade, multi-channel models gained more popularity for wireless data disseminations (see e.g. [9], [10], [12], [15], [16], [17], [19], [20], [21], [22], [23], [26], [27], [29]).

2)

Consider the server's point of view, since all the data items are disseminated cyclically via a set of channels, different broadcasting schedules will result in different expected access time. There have been intensive research efforts on data scheduling at the server side with respect to minimizing the expected access time (see e.g. [2], [7], [9], [12], [15], [16], [17], [19], [21], [23]).

3)

Consider the client's point of view, when downloading multiple data items from multiple channels, clients probably need switchings among channels, which will cause possible conflicts [20], [26]. Therefore, besides data scheduling at the server side, data retrieval scheduling at the client side is also an important issue [20], [26], [29], [30], [31], [32].