Wireless Multicast Scheduling With Switched Beamforming Antennas
Using beamforming antennas to improve wireless multicast transmissions has received considerable attention recently. A recent work proposes to partition all single-lobe beams into groups and to form composite multilobe beam patterns to transmit multicast traffic. Depending on how the power is split among the individual beams constituting a composite beam pattern, two power models are considered: 1) equal power split (EQP), and 2) asymmetric power split (ASP). This paper revisits the key challenge-beam partitioning in the beamforming-multicast problem-and makes significant progress in both algorithmic and analytic aspects of the problem. Under EQP, we propose a low-complexity optimal algorithm based on dynamic programming. Under ASP, we prove that it is NP-hard to have (3/2 - epsilon)-approximation algorithm for any epsilon > 0. For discrete rate functions under ASP, we develop an Asymptotic Polynomial-Time Approximation Scheme (APTAS), an asymptotic (3/2 + beta)-approximation solution (where beta >= 0 depends on the wireless technology), and an asymptotic 2-approximation solution to the problem by relating the problem to a generalized version of the bin-packing problem. In retrospect, we also obtain an asymptotic 2-approximation solution for the generalized bin-packing problem, which is of independent interest. For continuous rate functions under ASP, we develop sufficient conditions under which the optimal number of composite beams is 1, K, and arbitrary, respectively, where K is the total number of single-lobe beams. Both experimental results and simulations based on real-world channel measurements corroborate our analytical results by showing significant improvement compared to state-of-the-art algorithms.
wireless multicast scheduling beamforming bin-packing multiple-input-multiple-output (mimo) power allocation