Data broadcasting for dependent information using multiple channels in wireless broadcast environments

• Showing that the considered AFBML Problem is NP-complete.
• A linear-time algorithm to generate an optimal broadcast schedule for a conditioned weighted DAG.
• Three heuristics with analysis to arrange vertices to multiple channels for general weighted DAGs.
• Discussing the three proposed heuristics with simulation experiments.

Data broadcasting is an effective approach to disseminating information to mobile clients and has attracted much research attention in recent years. In many applications, the access pattern among the data can be represented by a weighted DAG. In this paper, we consider the problem of efficiently generating the broadcast schedules on multiple channels when the data set has a DAG access pattern. We show that it is NP-hard to find an optimal broadcast schedule which not only minimizes the latency but also satisfies the ancestor property that retains the data dependency. We further derive a condition for the input DAGs under which one can generate an optimal broadcast schedule in linear time and propose an algorithm to generate the schedule. Due to the NP-completeness, we provide three heuristics for general DAGs based on the level of a vertex in the input DAGs and each heuristic uses a different policy to place vertices into the broadcast channels. There are two categories for the policies. The first category mainly considers the probability for a process to stop at a considered vertex. The second category takes the vertices which are affected most when assigning a vertex into consideration. We analyze and discuss these heuristics. A short experimental simulation is given for supporting and validating the discussion. In particular, the experimental results indicate that roughly considering the whole posterior vertices of each vertex is not precise and may not lead to good results and considering the vertices affected most when assigning a vertex will help reducing the latency.