Paper Info
Title
Broadcasting dependent data with minimized access latency in a multi-channel environment
Abstract
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.
Year
DOI
Venue
2006
10.1145/1143549.1143711
IWCMC
Keywords
Field
DocType
dag access pattern,total access probability,broadcast schedule,dependent data,overall access probability,multi-channel environment,general dags,input dags,access latency,data dependency,data broadcasting,optimal broadcast schedule,linear time,np hard,latency,dag,broadcasting
Broadcasting,Data dependency,Latency (engineering),Computer science,Topological sorting,Computer network,Communication channel,Theoretical computer science,Heuristics,Dissemination,Time complexity,Distributed computing
Conference
ISBN
Citations 
PageRank 
1-59593-306-9
2
0.39
References 
Authors
13
2
Name
Order
Citations
PageRank
Kun-Feng Lin1141.26
Chuan-Ming Liu233427.88