Effi cient Algorithm for Data Retrieval Problem with Multi-Item Request in Wireless Data Broadcast

Abstract

Data retrieval problem in wireless data broadcast is an efficient way to assist disseminating public information. It refers that a set of data items is orderly broadcast at multiple parallel channels and the client with multiple requested data items retrieves these parallel channels to download their required information at the minimized access latency. In other words, the client finds an optimal data retrieval sequence to download all data items such that the access latency is minimized. Currently, many schemes have been proposed to study on this data retrieval problem with single request which includes multiple data items. However, the best results with lower time complexity are not found in this problem. In this paper, we define the data retrieval problem denoted as DRMR problem. We analyze the necessity by topological sorting to address the DRMR problem. In addition, we propose an algorithm to find annear-optimal data retrieval sequence for requested data items. Through three groups of experiments, we verify the performance of the proposed scheme on a critical metric: access latency. All of these experiments show that the proposed algorithm can obtain the best performance among all existing algorithms as far as we know.