Approximation Algorithm for Scheduling Real_time Multicast Flows in Wireless LANs

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. In this paper, we study the problem of efficient scheduling of real- time multicast flows. 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, the association strategy for which each user is restricted to receive flows only from its associated AP and the non-association strategy 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 furthermore is hard to approximate in general. We propose simple algorithms for scheduling the multicast flows from the APs, with provable performance bounds. More specifically, for unit-disk interference graphs we present three constant-factor approximation algorithms for the association strategy and two approximation algorithms with logarithmic ratios for non-association strategy. In addition, we evaluate the performance of the proposed solutions using simulations and clearly demonstrate that our algorithms yield efficient multicast scheduling.