| Wireless data broadcasting is an efficient way to disseminate data to a large number of users in the mobile communication environments. In many applications, such as stock quotes, flight schedules and traffic reports, the users may want to download multiple data items at one time and the application may require the support of a multichannel architecture. In this dissertation, we study the problem of downloading a set of data items from multiple wireless broadcasting channels. We divide the data retrieval problem into different situations to carry on the analysis. To maximize the number of downloads given a deadline, we study the Largest Number Data Retrieval (LNDR) problem. We prove that the decision LNDR problem is NP-hard, and we propose an approximation algorithm for it with provable performance ratio. To minimize the response time for downloading a set of data items, we study the Least Time Data Retrieval (LTDR) problem. We develop a deterministic algorithm and a randomized algorithm for different cases of LTDR. To minimize the power consumption for downloading a set of data items, we study the Minimum Cost Data Retrieval (MCDR) problem. When only considering the power consumption in channel switching, we prove that MCDR has a polynomial time O(log k)-factor approximation solution where k is the number of requested data items and there exists no polynomial time o(log k)-factor approximation solution for MCDR, unless P ≠ NP. When considering the power consumption in both doze model and channel switching, we prove that MCDR is NP-hard to approximate to within any nontrivial factor, and we propose a heuristic algorithm to reduce the power consumption. We also provide simulation results to demonstrate the practical efficiency of the proposed algorithms. The simulation results show that significantly better performances can be obtained by using our data retrieval scheduling methods at the client side. |
