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-ϵ)-approximation algorithm for any ϵ >; 0. For discrete rate functions under ASP, we develop an Asymptotic Polynomial-Time Approximation Scheme (APTAS), an asymptotic (3/2+ β)-approximation solution (where β ≥ 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, whereKis 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.

In this paper we investigate the issue of exploiting switched beamforming antennas to improve multicast transmission in wireless networks. Under the practical assumptions that different beams may have arbitrary overlapping patterns and that each user can receive data at different rates under different beams, we formulate the problem as minimizing the total multicast delay subject to the constraint that all users need to be covered. We prove that the problem is NP-hard and propose a greedy algorithm that achieves log(J) approximation guarantee where J is the number of clients. Measurements in both indoor and outdoor experiments validate our assumptions on the beamforming model. Trace-driven simulations based on these measurements show significant improvement over previous schemes and corroborate our analytical results.

Wireless multicast based video delivery is constrained by the user with the lowest channel quality within a multicast group. Beamforming increases the SINR at the clients thereby increasing the minimum channel quality among the users that form the multicast group. Thus it can be utilized to enhance the wireless multicast video transmission. In this paper, we investigate how to exploit switched beamforming antennas to improve wireless multicast based video transmission in indoor environments. The fundamental problem to be solved is the selection and scheduling of beams to be used to cover different subsets of users within the multicast group. We consider both multi-resolution videos and multi-layered videos and formulate the problem as maximizing the total utility of all multicast clients subject to a total delay constraint, where the utility is a general measure of video quality or user-satisfaction. We prove that it is NP-hard to have a (1-1/e+ε)-approximation solution to this problem for any ε >; 0, under both multi-resolution and multi-layered video models. For the multi-resolution video model, we develop a unified approximation algorithm with a parameter k that controls both the algorithm complexity and the approximation factor. For k = 0, 1, 2, 3, we prove that the proposed algorithm achieves an approximation guarantee close to 0.31, 0.38, 0.55, and 0.63, respectively. For the multi-layered video model, we propose a similar heuristic solution. The proposed algorithms are evaluated with both hypothetical video sequences and real video sequences using channel data collected in an indoor wireless testbed. Evaluation results show that the proposed algorithms have much better performance than naive multicast algorithms for scheduling the beams.

Using beamforming antennas to improve wireless multicast transmissions has received considerable attention recently. The work in proposes to partition all single-lobe beams into groups and to form composite multi-lobe beam patterns to transmit multicast traffic. The key challenge left is, how to partition the beams into multiple groups in order to minimize the total multicast delay. This work makes significant progress in both algorithmic and analytic aspects of the problem. We prove that, under the asymmetric power split (ASP) model, it is NP-hard to have (3/2 - ε)-approximation algorithm for any ε >; 0. We then develop an APTAS, an asymptotic (3/2 + β)-approximation solution (where β ≥ 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. Extensive trace-driven simulations based on real-world channel measurements corroborate our analytical results by showing significant improvement compared to state of the art algorithms.