Data management and retrieval for wireless data broadcast systems.

摘要

Wireless data broadcast has many advantages, which makes it suitable for distributing public information to a large number of mobile clients. There are many mobile services in which clients need to download multiple data items per request. In the first part of this thesis, we focus on investigating the complexity and approximation algorithms for the data retrieval problem in a multi-channel data broadcast environment. We formally define the minimum cost data retrieval (MCDR) problem which aims at downloading a set of data items from multiple channels with minimum cost. We further define the minimum switching data retrieval (MSDR) problem which concerns only the number of channel switchings, and the largest number data retrieval (LNDR) problem with the objective of downloading the largest number of requested data items in a given time duration. All these problems are proven to be NP-hard. We present an O(logn)-factor approximation for MSDR, which can be extended to solve MCDR. We also propose two 1/2-approximation algorithms for LNDR. For a special case of LNDR, we provide an optimal solution based on dynamic programming. With the advance of the fourth-generation wireless communication system, mobile devices may embed MIMO antennae to setup multi-connections to a base station. We extend the retrieval scheduling problem to a more complicated parallel retrieval scheduling problem in the second part. We also propose two greedy heuristics named Least Switch Data Retrieval Protocol and Best First Data Retrieval Protocol as its solutions. To the best of our knowledge, this is the first work to deal with data retrieval with MIMO antennae for wireless data broadcast.;The last part of this thesis discusses how to apply full-text search to documents transmitted through wireless communications. We propose a novel data streaming scheme (Basic-Hash) with hash-based indexing and inverted list techniques to facilitate energy and latency efficient full-text search in wireless data broadcast. We further extend the proposed scheme by merging the hashed word indices in order to reduce the total access latency (Merged- Hash). The performances of Basic-Hash and Merged-Hash are validated both theoretically and empirically.