Algebraic data retrieval algorithms for multi-channel wireless data broadcast

摘要

Wireless data broadcast is an important data dissemination method for distributing public information to mobile users. Due to the exponentially increasing number of mobile network users, it is necessary to develop efficient data retrieval protocols for end users to download data items effectively. In this paper, we concentrate on investigating scheduling algorithms for retrieving a set of data items from a multichannel wireless data broadcast system. As we know, the most important issues in mobile computing are energy efficiency and query response efficiency. However, in data broadcast the objectives of reducing access latency and energy cost can be contradictive to each other. Consequently, we define a new problem named Minimum Constraint Data Retrieval Problem (MCDR). We prove that MCDR is NP-hard, and then show a fixed parameter tractable algorithm which can balance two factors together. It has computational time O(2~k(hnt)O~(1)), where n is the number of channels, k is the number of required data items, t is the maximal time slot, and h is the maximal number of channel switches.