Approximation Algorithms for Scheduling Real-Time Multicast Flows in Wireless LANs
Yigal Bejerano, Dongcheol Lee, Pratik Kumar Sinha, L. Zhang · 2008
In recent years, numerous large-scale Wireless LANs (WLAN) have been deployed all over the world. However, the shortage of non-interfering channels makes it a challenge for WLANs to efficiently support real-time multicast services. We study the problem of efficient scheduling ofreal-timemulticastflows. For mitigating interferences, we allow access-points (APs) to transmit simultaneously only if they are mutually non-interfering and our objective is minimizing the fraction of time used by the APs for servicing the multicast flows. We introduce two multicast strategies, theassociationstrategyfor which each user is restricted to receive flows only from its associated AP and thenon-associationstrategy for which a user may also decode transmissions from other APs in its vicinity. Under both strategies, the scheduling problem of minimizing the multicast service time is NP-hard and we propose simple approximation algorithms with provable performance bounds. Our simulations clearly demonstrate that the proposed algorithms yield efficient multicast scheduling.