broadcasting dependent data with minimized access latency in a multi-channel environment
Data broadcasting is an effective way to disseminate information to clients in wireless environment. We consider how to efficiently generate the broadcast schedule on multiple channels when the data set has a DAG access pattern. It is NP-complete to find an optimal broadcast schedule which not only minimizes the latency but is a topological ordering which preserves the data dependency. We rule out a condition for the input DAGs under which one can generate an optimal broadcast schedule in linear time and propose a linear time algorithm to generate the schedule under such a condition. For general DAGs, we provide three heuristics: the first one uses the overall access probability of each vertex; the second one considers the total access probability of the posterior vertices of a vertex; the third one combines the above two heuristics. We analyze these three heuristics and compare them through experiments.
broadcasting latency multiple channels dag np-hard