Wireless data broadcast is a
popular data dissemination method in mobile computing environments because of
its capability of concurrently disseminating data to multiple users. In this
paper, we study the data retrieval scheduling problem for multi-item requests
in multi-channel broadcast environments. To maximize the number of downloads
given a deadline; we define a problem called largest number data retrieval
(LNDR). We prove the decision problem of LNDR is NP-hard, and we investigate
approximation algorithm for it. We also define another problem called minimum
cost data retrieval (MCDR), which aims at downloading a set of requested data
items with the least response time and energy consumption. We prove MCDR is
NP-hard to approximate to within any non-trivial factor. Therefore, we
investigate heuristic algorithm for it. Finally we provide simulation results
to demonstrate the practical efficiency of the proposed algorithms.
No comments:
Post a Comment