Efficient batch and adaptive approximation algorithms for joint multicast beamforming and admission control

Evaggelia Matskani, Nicholas D. Sidiropoulos, Zhi Quan Luo, Leandros Tassiulas

Research output: Contribution to journalArticlepeer-review

70 Scopus citations


Wireless multicasting is becoming increasingly important for efficient distribution of streaming media and location-aware services to mobile and hand-held devices, network management, and software updates over cellular (UMTS-LTE) and indoor/outdoor wireless networks (e.g., 802.11/16). Multicast beamforming was recently proposed as a means of exploiting the broadcast nature of the wireless medium to boost spectral efficiency and meet Quality of Service (QoS) requirements. Infeasibility is a key issue in this context, due to power or mutual interference limitations. We therefore consider the joint multicast beamforming and admission control problem for one or more co-channel multicast groups, with the objective of maximizing the number of subscribers served and minimizing the power required to serve them. The problem is NP-hard even for an isolated multicast group and no admission control; but drawing upon our earlier work for the multiuser SDMA downlink, we develop an efficient approximation algorithm that yields good solutions at affordable worst-case complexity. For the special case of an isolated multicast, Lozano proposed a particularly simple adaptive algorithm for implementation in UMTS-LTE. We identify strengths and drawbacks of Lozano's algorithm, and propose two simple but worthwhile improvements. All algorithms are carefully tested on publicly available indoor/outdoor measured channel data.

Original languageEnglish (US)
Article number5153361
Pages (from-to)4882-4894
Number of pages13
JournalIEEE Transactions on Signal Processing
Issue number12
StatePublished - Dec 2009

Bibliographical note

Funding Information:
Manuscript received June 27, 2008; accepted April 20, 2009. First published June 30, 2009; current version published November 18, 2009. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Subhrakanti Dey. Conference versions of parts of this work appear in the Proceedings of the IEEE CAMSAP, St. Thomas, U.S. Virgin Islands, December 12–14, 2007, and the Proceedings of the IEEE ICASSP, Las Vegas, NV, April 15–20, 2008. The work of E. Matskani and N. D. Sidiropoulos is supported in part by ARL/ERO contract N62558-06-0340, and EC/FP6 project COOPCOM and WIP. The work of Z.-Q. Luo is supported in part by the U.S. NSF Grants DMS-0312416 and DMS-0610037. The work of L. Tassiulas is supported in part by the ARO under Grant W911NF-04-1-0306, and EC/FP6 project WIP.


  • Admission control
  • Beamforming
  • Convex approximation
  • E-MBMS
  • Multicasting
  • NP-hard


Dive into the research topics of 'Efficient batch and adaptive approximation algorithms for joint multicast beamforming and admission control'. Together they form a unique fingerprint.

Cite this