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

Ping He ； Hong Shen ； Shuli Luan

《網際網路技術學刊》 18卷3期 (2017/05) Pp. 601-611

https://doi.org/10.6138/JIT.2017.18.3.20131029

摘要

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.

關鍵字

Mobile computing ； Data broadcast ； Indexing ； Data schedule ； Data retrieval