Abstract:
A method for wireless multicasting with beamforming includes dividing single lobe beam patterns into groups, each group being a composite beam pattern, the dividing being according to one of an equal power partition configuration and an asymmetric power partition configuration; and transmitting the information with the composite beam pattern.

Description:
[0001]    This application claims the benefit of U.S. Provisional Application No. 61/312,910, entitled “Wireless Multicasting with Switched Beamforming Antennas”, filed on Mar. 11, 2010, U.S. Provisional Application No. 61/450,901, entitled “SVC-Based Multicast Streaming with Beamforming Antennas”, filed Mar. 9, 2011, and this application is related to U.S. patent application Ser. No. ______, entitled “Scalable Video Multicast with Non-Overlapping Beamforming Antennas”, filed Mar. 11, 2011, all of which whose contents are incorporated by reference herein. 
     
    
     FIELD OF THE INVENTION 
       [0002]    The present invention relates generally to wireless communications, and more particularly, to wireless multicasting with beamforming antennas. 
       BACKGROUND OF THE INVENTION 
       [0003]    Wireless multicast/broadcast is becoming increasingly important for efficient dissemination of streaming video as well as common data because the shared nature of wireless medium provides a natural support of wireless multicast and broadcast. However, one limitation of the wireless multicast is that the multicast transmission rate is limited by the mobile terminal with the lowest signal strength in the multicast group. 
         [0004]    Beamforming antennas have been widely used to boost the received signal strength in unicast scenarios by concentrating the signal energy in a specific direction at a client. If beamforming can be applied to boost the received power at the weakest client of a multicast group, it can potentially improve the performance of wireless multicast significantly. Nevertheless, it is challenging to apply beamforming technologies to multicast/broadcast transmissions because there is an inherent tradeoff between multicasting and beamforming. While beamforming increases the signal energy on a particular direction, it also reduces the energy on other directions, thereby restricting the wireless broadcast advantage. 
         [0005]    An attempt has been made to address the integrated issue of multicasting and beamforming by using a combination of an omni-directional transmission in a first step, followed by one or more multiple single-lobe beamforming transmission in the second step to cover the clients left behind from the omni-directional transmission. 
         [0006]    There has been provided a rigorous formulation of the switched beamforming multicasting problem as dividing the beam patterns into multiple partition/group and then sequentially transmitting each group of beam patterns. The objective of this formulation is to minimize the total transmission delay. Two power allocation problems have also been considered: an Equal power EQP model, where the power is evenly distributed among different beams in a given group, and an Asymmetric Power ASP model, where the power distribution across different beams is asymmetric and can be optimally chosen to maximize the minimum SNR in each beam. Also considered were two cases in each model depending on whether the rate is a continuous or discrete function of the SNR values and provide processes for all cases. However, these prior attempts, dividing beam patterns into groups and determining the weight of each antenna for the transmission to the group, need improved efficiency and better performance techniques for dividing the user groups. 
         [0007]    Accordingly, there is a need for improved multicasting with beamforming antennas. 
       SUMMARY OF THE INVENTION 
       [0008]    In one aspect of the invention, a method for wireless multicasting with beamforming includes dividing single lobe beam patterns of information into groups, each group being a composite beam pattern, the dividing being according to one of an equal power partition configuration and an asymmetric power partition configuration; and transmitting the information with the composite beam pattern. In a preferred embodiment, the equal power partition configuration includes obtaining an aggregate delay of first sorted beams responsive to an iterative determination, and sorting the beam patterns in decreasing order of their effective signal-to-noise-ratios (SNR), where the effective SNR of a beam pattern refers to the SNR of the worst user under that beam when all power is applied to the beam. Assume that (σ 1 , σ 2 , . . . , σK) is the list of beams sorted in the decreasing order of their effective SNRs. Preferably, the equal power partition model includes determining an initial condition S 1 =T({σ 1 }) and letting k=2, with Sk being the cost and being recursively computed as S k =min 1≦j≦k (S j−1 +T({σ j , . . . , σ k })), T ({σj+1, . . . , σk}) being the transmission delay of the last group and being calculated using the following relationship 
         [0000]    
       
         
           
             
               
                 T 
                  
                 
                   ( 
                   
                     { 
                     
                       
                         σ 
                         
                           j 
                           + 
                           1 
                         
                       
                       , 
                       … 
                        
                       
                           
                       
                       , 
                       
                         σ 
                         k 
                       
                     
                     } 
                   
                   ) 
                 
               
               = 
               
                 W 
                 + 
                 
                   L 
                   
                     R 
                      
                     
                       ( 
                       
                         
                           γ 
                           
                             σ 
                             k 
                           
                         
                         / 
                         
                           ( 
                           
                             k 
                             - 
                             j 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    with W being the switching delay, L being a packet length, γ σ     k    being an effective SNR of beam σ k , and R being an SNR-rate table. 
         [0009]    In an alternative aspect of the invention, an apparatus for wireless multicasting with beamforming includes means for dividing single lobe beam patterns of information into groups, each group being a composite beam pattern, the dividing being responsive to one of an equal power partition configuration and an asymmetric power partition configuration; and means for transmitting the information with the composite beam pattern responsive to the means for dividing. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0010]    These and other advantages of the invention will be apparent to those of ordinary skill in the art by reference to the following detailed description and the accompanying drawings. 
           [0011]      FIG. 1  is an exemplary diagram illustrating a switched beamforming system, in accordance with the invention. 
           [0012]      FIG. 2  is an exemplary diagram illustrating a wireless system overview of multicast scheduling utilizing beamforming antennas, in accordance with the invention. 
           [0013]      FIG. 3  is a diagram of the inventive multicasting with beamforming, in accordance with the invention. 
           [0014]      FIG. 4  is a diagram of beamforming multicasting under an Equal Power Partition EQP model, in accordance with the invention. 
           [0015]      FIG. 5  is a diagram of beamforming multicasting under an Asymmetric Power Partition ASP model, in accordance with the invention. 
           [0016]      FIG. 6  is a mapping table for conversion of the beam partition problem to a generalized-cost-variable-size bin packing (GVCS-BP) problem, in accordance with the invention. 
           [0017]      FIG. 7  is diagram of a Most Efficient Bins First MEBF technique, in accordance with the invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0018]    The invention is directed to the problem of wireless multicasting with switched beamforming antennas,  100  in  FIG. 3 . In order to exploit both the wireless broadcast advantage and beamforming technologies, the invention divides the single-lobe beam patterns into one or multiple groups and lets each composite pattern comprise a group&#39;s single-lobe beam patterns. Then, the same data is transmitted to each composite pattern sequentially. The major issue of how to divide the single-lobe beam patterns into groups, and how to determine the weight/power of each single-lobe beam pattern in a composite one is addressed as follows: Under the EQP (equal power partition) model, the invention develops a dynamic-programming based optimal solution and under the ASP (asymmetric power partition) model, the invention converts the problem to a generalized bin-packing problem and then obtains several approximation solutions. The inventive technique leads to 1) reduced transmission time for a given multicast transmission data, 2) reduced total delay of multicasting and better robustness and 3) improved robustness of system (see  FIG. 3 ). 
         [0019]    In order to exploit both the wireless broadcast advantage and beamforming technologies, the invention employs new methods for scheduling beamforming transmissions for multicast traffic  100 . The basic idea is to divide the (single-lobe) beam patterns into groups where each group represents a composite beam pattern and the same data is transmitted with each composite beam pattern sequentially. For example, referring  FIG. 1  and  FIG. 2 , there are 4 users  120  (clients) in beam patterns  113 ,  114 ,  116 ,  118 , respectively. Remaining beam patterns  111 ,  112 ,  117  and  118  have no users. Each color representing one transmission group in the example scheduling. 
         [0020]    In order to multicast a data to all these users, one possible transmission strategy is to divide the four (single-lobe) beam patterns into 3 groups, wherein the first group comprises beams  113  and  114 , the second one comprises  116 , and the third one comprises  118 . Then the base station (Access point) transmits the same data to the first group using a composite beam pattern combining patterns  113  and  114 , then to the second group (beam pattern  116 ) and then to the third group (beam pattern  118 ). The data rate for each transmission group may be different to minimize the total transmission delay. 
         [0021]    The major issue that needs to be solved is how to divide the beam patterns as well as how to assign the weight/power on each beam within a transmission group. The objective is to minimize the total transmission time of L bytes of data, i.e., minimize 
         [0000]    
       
         
           
             
               
                 ∑ 
                 
                   g 
                   = 
                   1 
                 
                 G 
               
                
               
                 ( 
                 
                   W 
                   + 
                   
                     L 
                     
                       R 
                       g 
                     
                   
                 
                 ) 
               
             
             , 
           
         
       
     
         [0000]    where G is the total number beam groups (to be optimized), W is the switching delay, L is the packet size, R g  is the optimal transmission rate of group g. 
         [0022]    Within each group, the transmit power on each single-lobe pattern may be equal or different, which results in two different models: EQP (Equal power partition) model  200  and ASP (Asymmetric power partition) model  300 , respectively. 
         [0023]    Under the EQP model  200 , the transmit power on each single-lobe beam pattern is equal. If the total transmit power is P and there are K single-lobe patterns in a group, each single-lobe pattern receives a power of P/K. The proposed method of beamforming multicasting under EQP is optimal and is based on dynamic programming. 
         [0024]    The dynamic programming method relies on the following recursive equations. Assume that (σ 1 , σ 2 , . . . , σK) is the list of beams sorted in the decreasing order of their effective SNRs, where the effective SNR of a beam is the SNR of the user with the worst channel condition under that beam when all power is applied to the beam. Denote S k  as the cost (i.e., total transmission time) of the optimal partition of beams (σ 1 , σ 2 , . . . , σK). S k  can be recursively computed as 
         [0000]        S   k =min 1≦j≦k ( S   j−1   +T ({σ j , . . . , σ k }))  (1)
 
         [0000]    where T ({σj+1, . . . , σk}) is the transmission delay of the last group and is calculated using Eq. (2): 
         [0000]    
       
         
           
             
               
                 
                   
                     T 
                      
                     
                       ( 
                       
                         { 
                         
                           
                             σ 
                             
                               j 
                               + 
                               1 
                             
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             σ 
                             k 
                           
                         
                         } 
                       
                       ) 
                     
                   
                   = 
                   
                     W 
                     + 
                     
                       L 
                       
                         R 
                          
                         
                           ( 
                           
                             
                               γ 
                               
                                 σ 
                                 k 
                               
                             
                             / 
                             
                               ( 
                               
                                 k 
                                 - 
                                 j 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where W is the switching delay, L is the packet length, γ σ     k    is the effective SNR of beam σk, R is the snr-rate table. The initial condition is 
         [0000]        S 1 =T ({σ1})  (3)
 
         [0025]    The blocks of  FIG. 4  show the detailed inventive steps under the EQP model  200 . For each user, find the best beam pattern that can be served and assign each user to its best beam pattern. See  210 . For each beam pattern, find the minimum SNR signal-to-noise-ratio of all users that are assigned to it in the previous step. This is referred to as the minimum SNR as the effective SNR of the beam pattern. See  220 . Sort the beams in the decreasing order of their SNR. Denoting the resulting permutations as (σ 1 , σ 2 , . . . , σK). See  230 . Then Compute S 1 =T({σ 1 }), using Eq. (3), let k=2. See  240 . Compute S k  using Eq. (1), let k=k+1. See  250 . S k  is computed for K iterations to return the optimal cost R K . See  260 . 
         [0026]    Under the ASP (Asymmetric Power Splitting) model  300 , each beam may be assigned with a different power to minimize the total transmission delay. In order to solve the problem, the invention first converts the problem to a generalized-cost-variable-size bin-packing (GCVS-BP) problem  400 . The invention then applies existing processes and also employs new processes  500 ,  600 ,  700  to solve the GCVS-BP problem. The high level flow diagram is depicted in  FIG. 5 . 
         [0027]    The high level flow diagram for conversion of the beamforming problem into a bin packing problem under the ASP model is depicted in  FIG. 5 . For each user, find the best beam pattern it can be served. The process assigns each user to its best beam pattern. See  210 . For each beam pattern, find the minimum SNR of all users that are assigned to it in the previous step. We call this minimum SNR as the effective SNR of the beam pattern. See  220 . Convert the beam multicast problem to a GCVS-BP problem. See  400 . Apply existing or new generalized bin-packing algorithms to solve the converted GCVS-BP. See  500 . Map the items in each bin in the bin-packing solution to a group of beams for simultaneous transmission to obtain a beam multicast solution. See  800 . 
         [0028]    Conversion of the multicast problem to a GCVS-BP problem is accomplished by applying the mapping depicted in  FIG. 6 . Shown in the mapping table are variables in a beam multicast situation converted to variables in the GCVS-BP situation. 
         [0029]    The inventive process applies a known algorithm IFFD  600  to solve the converted GCVS-BP problem  500 . The process also employs an inventive MEBF (Most Efficient Bins First) technique to solve the problem. The inventive MEBF technique  700  is illustrated in the diagram of  FIG. 7 . Optionally, the process sorts the items in the order of decreasing sizes. See  710 . Then the process computes the set of bin types T which have the lowest cost-size ratio among those with equal or larger sizes. See  720 . The process then packs items with size s m  to bin type k j  εT such that B k     j   ≧s m &gt;B k     j+1    using a first-fit manner. See  730 . The process packs all at least half-empty bins to the largest one that is at least half-empty. See  740 . The process then re-packs every bin using a bin that has the smallest cost but can hold all objects in the corresponding original bin. See  750 . Lastly, the process converts the bin-packing solution back to a solution for multicasting scheduling with beamforming antennas. See  800 . 
         [0030]    It is anticipated, however, that departures may be made therefrom and that obvious modifications will be implemented by those skilled in the art. It will be appreciated that those skilled in the art will be able to devise numerous arrangements and variations, which although not explicitly shown or described herein, embody the principles of the invention and are within their spirit and scope.