Auction based resource allocation in wireless systems

Abstract

Systems and methods to assign one or more resources in a multi-user cellular Orthogonal Frequency-Division Multiple Access (OFDMA) uplink includes specifying a resource allocation problem for one or more resources; converting the resource allocation problem into an assignment problem; solving the assignment problem through an auction; and allocating one or more resources to cellular users to maximize a system utility.

1. A method to assign power, sub-carrier(s), modulation and coding scheme(s) resources in a multi-user system with one or more cells, comprising:
 specifying a resource allocation problem for allocating the resources; 
 converting the resource allocation problem into an assignment problem; 
 solving the assignment problem through an auction process; 
 allocating the resources to cellular users to maximize a system utility; and 
 determining a single cell type 1 resource allocation according to 
 
       
         
           
             
               max 
               ⁢ 
               
                 
                   ∑ 
                   k 
                 
                 ⁢ 
                 
                   
                     w 
                     k 
                   
                   ( 
                   
                     
                       ∑ 
                       i 
                     
                     ⁢ 
                     
                       
                         
                           c 
                           ~ 
                         
                         ki 
                       
                       ⁢ 
                       
                         α 
                         ki 
                       
                     
                   
                   ) 
                 
               
             
           
         
         such that Σ k  α ki≦ 1, ∀i, ñ kl ≦Σ i  α ki ≦ñ ku , ∀k; α ki  ε{0,1}, where 
         W k  comprises a weight factor of a user k, 
         {tilde over (c)} ki  comprises a throughput when assigning a subcarrier i to the user k, 
         α ki  comprises an indicator on whether the subcarrier i is allocated to the user k, 
         ñ kl  comprises a lower bound on the total subcarriers assigned to the user k, and 
         ñ ku  comprises an upper bound on the total subcarriers assigned to the user k. 
       
     
     
       2. The method of  claim 1 , comprising determining a multi-cell type 1 resource allocation according to 
       
         
           
             
               max 
               ⁢ 
               
                 
                   ∑ 
                   j 
                 
                 ⁢ 
                 
                   
                     ∑ 
                     
                       k 
                       i 
                     
                   
                   ⁢ 
                   
                     
                       w 
                       
                         k 
                         j 
                       
                     
                     ( 
                     
                       
                         ∑ 
                         l 
                       
                       ⁢ 
                       
                         
                           c 
                           
                             
                               k 
                               j 
                             
                             ⁢ 
                             l 
                           
                         
                         ⁢ 
                         
                           α 
                           
                             
                               k 
                               j 
                             
                             ⁢ 
                             l 
                           
                         
                       
                     
                     ) 
                   
                 
               
             
           
         
         such that Σ k     j    α k     j     l +Σ k     i     ε       j    α {circumflex over (k)}     ij     l ≦1,  l,j; n k     j     l ≦Σ l  α k     j     l ≦n k     j     u , k j , j; α {circumflex over (k)}     ij     l =α k     i     l , l, k i  ε   j , j;α k     j     l  ε{0,1}, l,k j ,j, where 
         w kj  comprises a weight factor of a user in a jth cell, 
         c kjl  comprises a throughput when assigning a subcarrier l to a user k in a cell j, 
         α kjl  comprises an indicator of whether the subcarrier l is allocated to the user k in cell j, and 
         n kjl  comprises a lower bound of the total subcarriers assigned to the user k in cell j. 
       
     
     
       3. A method to assign power, sub-carrier(s), modulation and coding scheme(s) resources in a multi-user system with one or more cells, comprising specifying a resource allocation problem for allocating the resources;
 converting the resource allocation problem into an assignment problem; 
 solving the assignment problem through an auction process; 
 allocating the resources to cellular users to maximize a system utility; and 
 directing the resources using the auction process resulting in a largest increase in the system utility, 
 removing a sub-carrier allocated to a user in a cell if a weighted rate of the user on the sub-carrier is less than one of the corresponding weighted rates of users in adjacent cells and the number of subcarriers assigned to the cell is greater than a minimum bandwidth constraint. 
 
     
     
       4. The method of  claim 3 , comprising receiving as input a per-user power level, one or more bandwidth constraints, a constellation set, an outer code penalty, and channel gain information. 
     
     
       5. The method of  claim 3 , wherein the assignment problem comprises a symmetric assignment problem. 
     
     
       6. The method of  claim 3 , comprising determining a sub-carrier assignment for each user. 
     
     
       7. The method of  claim 6 , wherein the subcarrier assignment is determined under fixed per-user per subcarrier power, practical modulation and coding scheme(s) and per-user bandwidth constraint(s). 
     
     
       8. The method of  claim 3 , comprising removing a sub-carrier allocated to a user in adjacent cells if a weighted rate of a user on the sub-carrier in a given cell is greater than corresponding weighted rates of other users in adjacent cells or if the number of subcarriers assigned to the user is equal to a minimum bandwidth constraint. 
     
     
       9. The method of  claim 3 , wherein the resource comprises one or more resources in an Orthogonal Frequency-Division Multiple Access (OFDMA) uplink. 
     
     
       10. The method of  claim 3  comprising selecting and assigning one or more sub-carriers to a user from a set of users which have not been selected yet that results in the largest increase in the system utility. 
     
     
       11. A method to assign power, sub-carrier(s), modulation and coding scheme(s) resources in a multi-user system with one or more cells, comprising:
 specifying a resource allocation problem for allocating the resources; 
 converting the resource allocation problem into an assignment problem; 
 solving the assignment problem through an auction process; 
 allocating the resources to cellular users to maximize a system utility; 
 performing a carrier assignment with constant bandwidths for a set {n 1 , . . ., n K } and constant power level P k  /n k , where n k  denotes the number of subcarriers allocated to user k; 
 selecting a subcarrier with the smallest reward for a user k j  and assigning the selected subcarrier to all other users except user k j , and 
 performing equal power allocation for the user over assigned sub-carriers to obtain a weighted sum rate.