Efficient Data Retrieval Algorithms for Avoiding 2-Slot Conflicts in Wireless Data Broadcast
Ping He and Hong Shen
Given a set of data items that are broadcast in multiple wireless channels, where each channel has the same broadcast pattern over a time period, and a set of client’s requested data items, the data retrieval problem requires to find a sequence of channel accesses to retrieve the requested data items among the channels such that the total access latency is minimum, where both channel access (to retrieve a data item) and channel switch are assumed to take a single time slot. As an important problem of information retrieval in wireless networks, data retrieval arises in many applications such as e-commerce and ubiquitous data sharing. During data retrieval conflicts arise for channel switching when the requested data items are broadcast in the same time slot or adjacent time slots across two channels, which we call 2-slot conflict as they occur in two contiguous time slots. Although various solutions are proposed for resolving single (same) slot conflicts, little work is known for resolving 2-slot conflicts. This paper proposes an efficient algorithm for solving the data retrieval problem under 2-slot conflicts in single antenna and multiple antennae respectively. Our algorithm adopts a novel approach to convert a wireless data broadcast system into a DAG, and applies the greedy set cover algorithm to solve this problem. We have validated the effectiveness and efficiency of our algorithm through implementation in a simulation environment, and show that our algorithm outperforms the known methods.
Keywords: Wireless communication, data retrieval, indexing, data schedule, data broadcast, mobile computing