Minimum Latency Broadcast in the SINR Model: A Parallel Routing and Scheduling Approach
Shiliang Xiao, Jun Pei, Xinwei Chen, Wenbin Wang · IEEE Communications Letters · 2014
We study the minimum latency data broadcast problem under the signal-to-interference-plus-noise-ratio (SINR) model, which is known to capture wireless interference more accurately and realistically than the widely used graph-based models. Previous work mainly involves building a broadcast tree first and then computing interference-aware TDMA schedules for the links on the tree. Observing that the separation of routing and scheduling may lead to unsaturated transmissions in each time slot, we develop a polynomial-time heuristic algorithm, namely PRS, by advocating a parallel way of constructing routing and transmission schedules. Theoretical analysis indicates that PRS generates correct schedules under the SINR constraints. Simulation results demonstrate that PRS outperforms state-of-the-art algorithms in terms of broadcast latency under various network conditions.