Efficient Scheduling Algorithms for Disseminating Dependent Data in Wireless Mobile Environments
Chuan-Ming Liu, Kun-Feng Lin · 2005
In wireless mobile environments, data broadcasting is an effective approach to disseminate information to mobile clients. In some applications, the access pattern of all the data can be represented by a DAG. In this paper, we explore how to efficiently generate the broadcast schedule in a wireless environment for the data set having a DAG access pattern. Such a broadcast schedule not only minimizes the access latency but also is a linear ordering of the DAG. Minimized access latency ensures the quality of service (QoS). We prove that it is NP-hard to find an optimal broadcast schedule and provide two heuristics, MOA and RTS. After giving an analysis for these two heuristics on the latency and complexity, we implement both heuristics to compare their performance. The experimental results show that MOA is more efficient than RTS in terms of the access latency and time complexity.