Abstract:
Systems and methods are disclosed for transmission with a plurality of base stations (BSs) in a wireless cellular data network where one BS communicates with neighboring BSs by determining a binary or discrete new power level on each subchannel to determine a weighted sum modified rates of a BS and in-neighbor BSs; and resolving concurrent power update in each BS in a distributed manner.

Description:
[0001]    This application claims priority to Provisional Application Ser. No. 61/079,489 filed Jul. 10, 2008, the content of which is incorporated by reference. 
     
    
     BACKGROUND 
       [0002]    3G/4G wireless systems are characterized by high-speed downlink and uplink data services. In such systems, interference between different cells is an important issue. Fractional frequency reuse is a traditional (even though suboptimal) approach to multi-cell interference mitigation. For example, in a ⅓ fractional frequency reuse system, only ⅓ of the frequency band is allocated to each cell/sector. Static fractional frequency planning reduces interference and, hence, improves coverage at the price of reducing the total system throughput per unit of frequency resources (i.e., Hz), compared to the full frequency re-use scheme. In addition, frequency diversity and multi-cell diversity cannot be fully exploited. 
         [0003]    Recently, base station (BS) coordination has emerged as a promising tool for inter-cell interference mitigation. If neighboring base stations can communicate through high-speed wireline links, they can jointly decide what power level each base station should choose on each frequency band in order to improve the network weighted sum-rate. Previous work in this area typically relies on centralized or semi-centralized optimization process. Some distributed schemes also exist for interference mitigation. However, one scheme can only be employed to maximize the total throughput and cannot be generalized to the weighted sum-rate case. Another process assumes that power is a continuous variable and requires the channel gain from all other BSs to the selected user in each BS, and thus requires more communication overhead. Yet another scheme employs simulated annealing to optimize the system throughput. While simulated annealing can guarantee the asymptotic optimality, it is at the price of infinitely-long convergence time. Other works have focused on distributed processes for fixed-bit-rate traffic that do not exploit multi-channel selectivity. 
       SUMMARY 
       [0004]    Systems and methods are disclosed for transmission with a plurality of base stations (BSs) in a wireless cellular data network where one BS communicates with neighboring BSs to determine a binary or discrete new power level on each subchannel to maximize a weighted sum rates of a BS and in-neighbor BSs; and to resolve concurrent power update in each BS in a distributed manner. 
         [0005]    Advantages of the embodiments may include one or more of the following. The schemes are distributed, provide proportional fairness, require less overhead, and obtain higher throughput than conventional schemes. In resolving the concurrent power update, the system spreads the processing workload associated with the power update processing tasks to all BSes and each BS performs the concurrent power update as part of the group. For example, in each iteration n, each BS decides its new transmission power on each sub-channel in order to maximize the weighted sum of the modified rates and the summation is taken over itself and the set of in-neighbors. 
         [0006]    The system advantageously performs inter-cell interference mitigation in wireless cellular data networks. The processes guarantee convergence to a state where no base station can change its status to improve the system weighted throughput (given the status of the other base stations). When base stations can communicate with their neighboring base stations, the system optimizes the network weighted sum-rate via cooperative power control. The weights account for different priorities of the mobile terminals, and can be periodically updated to maintain proportional fairness. Two distributed embodiments can be used for inter-cell coordination which converge to a state where no base station can change its status to improve the weighted throughput of the network. Numerical results show that these process achieve a significant rate gain, especially for cell-edge users (about 20%), compared to a conventional proportional fair scheduling process without inter-cell coordination. The distributed processes require limited feedback and achieve most of the performance gain within few iterations. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]      FIG. 1A  shows an exemplary wireless system in accordance with one aspect of the present invention. 
           [0008]      FIG. 1B  shows the relationship between a BS b and its in-neighbor and out-neighbor set. 
           [0009]      FIG. 2  shows an exemplary process for handling the basic scheme of interference mitigation with discrete power levels. 
           [0010]      FIGS. 3A-3B  shows exemplary processes for performing Prioritized interference mitigation. 
           [0011]      FIGS. 4A-4B  shows exemplary processes for performing Randomized interference mitigation. 
           [0012]      FIG. 5A-5B  shows exemplary flow-charts of enhancements A and B to the embodiments of  FIGS. 3A-3B  and  FIGS. 4A-4B , respectively. 
           [0013]      FIG. 5C  shows various embodiments to perform interference mitigation. 
           [0014]      FIG. 6  shows an exemplary 7-cell network which is simulated to provide a performance companson. 
           [0015]      FIG. 7  shows exemplary plots of achieved throughput and relative performance improvements for the average rate. 
           [0016]      FIG. 8  shows the average convergence time of the Randomized scheme and the Prioritized scheme. 
           [0017]      FIG. 9  shows the average user rate achieved in each iteration of the Randomized scheme and the Prioritized scheme. 
           [0018]      FIG. 10  shows an exemplary plot of average user rate and actual number of reported interfering BSs vs. maximum number of reported interfering BSs. 
           [0019]      FIG. 11  shows an exemplary plot of average user rate and actual number of reported interfering BSs vs. the value β. 
           [0020]      FIG. 12  shows an exemplary plot of average throughput and convergence time of the enhanced schemes. 
       
    
    
     DESCRIPTION 
       [0021]      FIG. 1A  shows an exemplary wireless system in accordance with one aspect of the present invention. In  FIG. 1A , mobile users (block  15 ) are served by multiple BSs (blocks  12 ,  13 ,  14 ) on multiple sub-channels, which are connected via high-speed router, gateway or controller (block  11 ). The proposed schemes reside in the base stations (blocks  12 ,  13 ,  14 ) and are designed to mitigate interference among different BSs. The system maximizes a weighted sum rate of each link, where the rate of each link is defined to be r=log 2 (1+SINR/Γ), where Γ represents the gap between practical coding schemes and the Shannon capacity. 
         [0022]    In the system of  FIG. 1A , each sub-channel has a subset of power levels with which a BS can choose to transmit and the subset of power levels for different sub-channel in each BS may be different. The subset of power levels includes zero, which indicates that BS may choose not to transmit on that sub-channel. If the subset of power levels only contains a zero, the BS cannot transmit on that sub-channel (this corresponds to the sub-channels not assigned to the BS for ⅓ frequency reuse). In the discussion below, “subchannel” should be viewed as the minimum allocation block in the frequency domain. For example, in some systems such as LTE, RB (resource block) is the minimum frequency allocation unit, so “subchannel” should be viewed as RB in those systems. 
         [0023]    The system of  FIG. 1A  provides distributed interference mitigation in OFDMA-based cellular networks. There are M base stations transmitting to a set of N wireless users on a set of C subchannels. Each user chooses a base station based only on the long-term average signal strength. Each base station can transmit on each subchannel with multiple discrete power levels, namely, a 0 P, a 1 P 0 , . . . , a K P 0 , where 0=a 0 &lt; . . . &lt;a K ≦1. Note that the elements in the set {a 0 , . . . , a K } as well as its cardinality can be dependent on the BS and the sub-channel. For convenience, the dependence is not explicitly denoted. 
         [0024]    The maximum power a K P 0  that can be used on a sub-channel by a BS can be determined using any suitable slow power-control algorithm. The number of power levels allowed for a BS on a sub-channel is constrained by the complexity and latency constraints as well as the limit imposed on the signaling overhead. A suitable P 0  as well as {a 0 , . . . a K } is determined for each sub-channel and BS. 
         [0025]    The data rate on subchannel c from BS b to user j can be modeled by the Shannon&#39;s formula if it is active on subchannel c: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       r 
                       bjc 
                     
                     = 
                     
                       log 
                        
                       
                         ( 
                         
                           1 
                           + 
                           
                             
                               SINR 
                               bjc 
                             
                             Γ 
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where Γ represents the gap between the practical coding schemes and the Shannon capacity, and SINR bjc  is the signal-to-interference-plus-noise ratio (SINR) defined as 
         [0000]    
       
         
           
             
               
                 
                   
                     S 
                      
                     
                         
                     
                      
                     I 
                      
                     
                         
                     
                      
                     N 
                      
                     
                         
                     
                      
                     
                       R 
                       bjc 
                     
                   
                   = 
                   
                     
                       
                         
                           P 
                           0 
                         
                          
                         
                           χ 
                           bc 
                         
                          
                         
                           G 
                           bjc 
                         
                       
                       
                         
                           N 
                           0 
                         
                         + 
                         
                           
                             ∑ 
                             
                               s 
                               ≠ 
                               b 
                             
                           
                            
                           
                               
                           
                            
                           
                             
                               P 
                               0 
                             
                              
                             
                               χ 
                               sc 
                             
                              
                             
                               G 
                               sjc 
                             
                           
                         
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    In Eq. (2), χ bc  is the power boosting function which takes value on the discrete set {a 0 , a 1 , . . . a K }, G bjc  is the channel gain (including antenna gain, path loss, shadowing and fast fading) from BS b to user j on subchannel c, N 0 /2 is the power spectral density of thermal noise. 
         [0026]    The system maximizes the weighted sum-rate in each time slot: 
         [0000]    
       
         
           
             
               
                 
                   
                     max 
                      
                     
                       
                         ∑ 
                         
                           b 
                           , 
                           c 
                         
                       
                        
                       
                         
                           w 
                           j 
                         
                          
                         
                           r 
                           bjc 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the controlling parameters are the power boosting functions χ bc  and the user assignment function j=j(b,c) for b=1, . . . , M and c=1, . . . , C. The user weight w j  can change over time. For example, in the proportional fair scheduling method, w j =1/{circumflex over (r)} j  where {circumflex over (r)} j  is the average throughput achieved by user j. 
         [0027]    The following notations are defined for subsequent references. The Interference and Noise to Signal Ratio (INSR) is defined as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       I 
                        
                       
                           
                       
                        
                       N 
                        
                       
                           
                       
                        
                       S 
                        
                       
                           
                       
                        
                       
                         R 
                         bjc 
                       
                     
                     = 
                     
                       
                         
                           N 
                           0 
                         
                         
                           
                             P 
                             0 
                           
                            
                           
                             G 
                             bjc 
                           
                         
                       
                       + 
                       
                         
                           ∑ 
                           
                             s 
                             ≠ 
                             b 
                           
                         
                          
                         
                             
                         
                          
                         
                           
                             χ 
                             sc 
                           
                            
                           
                             
                               G 
                               sjc 
                             
                             
                               G 
                               bjc 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    and individual ISR is defined as 
         [0000]    
       
         
           
             
               I 
                
               
                   
               
                
               S 
                
               
                   
               
                
               
                 R 
                 sbjc 
               
             
             = 
             
               
                 
                   G 
                   sjc 
                 
                 
                   G 
                   bjc 
                 
               
               . 
             
           
         
       
     
         [0028]    The set of out-neighbor of a BS b on subchannel c, denoted as NB out (b,c), consists of up to K BSs with the highest interference such that ISR sbjc ≧β, where s is the candidate out-neighbor BS and j=j(b,c) is the user selected by BS b on subchannel c. If BS b is an out-neighbor of BS s on a subchannel, BS s is called an in-neighbor of BS b on the same subchannel. In other words, the set of in-neighbor of BS b on subchannel c, NB in (b,c) is defined as NB in (b,c)={s: b ∈ NB out (s,c)}. The two-hop neighbor set of b, is defined as 
         [0000]        NB 2( b )={ s : there exists a subchannel  c  such that  NB   in ( b,c )∩ NB   in ( s,c )≠φ}.   (5) 
         [0000]      FIG. 1B  shows the relationship between a BS b and its in-neighbor and out-neighbor set. As shown in  FIG. 1B , NB out (b,c) is the set of BSs that create strong interference to BS b on subchannel c, and NB in (b,c) is the set of BSs that was strongly interfered by BS b on subchannel c. In our algorithms, each BS b only keeps track of the status of its out-neighbors. Therefore, it can only compute its modified rate  r   bjc  on each subchannel c by assuming that those BSs that are not in NB in (b,c) are transmiting using full power: 
         [0000]    
       
         
           
             
               
                 
                   
                     r 
                     bjc 
                   
                   = 
                   
                     
                       log 
                       2 
                     
                      
                     
                       ( 
                       
                         1 
                         + 
                         
                           
                             χ 
                             
                               b 
                               , 
                               c 
                             
                           
                           
                             Γ 
                             · 
                             
                               
                                 
                                   I 
                                    
                                   
                                       
                                   
                                    
                                   N 
                                    
                                   
                                       
                                   
                                    
                                   S 
                                    
                                   
                                       
                                   
                                    
                                   R 
                                 
                                 _ 
                               
                               bjc 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where  INSR   bjc  is the modified interference and noise to signal ratio defined as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         I 
                          
                         
                             
                         
                          
                         N 
                          
                         
                             
                         
                          
                         S 
                          
                         
                             
                         
                          
                         R 
                       
                       _ 
                     
                     bjc 
                   
                   = 
                   
                     
                       
                         N 
                         0 
                       
                       
                         
                           P 
                           0 
                         
                          
                         
                           G 
                           bjc 
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           
                             
                               s 
                               ≠ 
                               b 
                             
                             , 
                           
                           
                             s 
                             ∉ 
                             
                               
                                 NB 
                                 out 
                               
                                
                               
                                 ( 
                                 
                                   b 
                                   , 
                                   c 
                                 
                                 ) 
                               
                             
                           
                         
                       
                        
                       
                           
                       
                        
                       
                         
                           G 
                           sjc 
                         
                         
                           G 
                           bjc 
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           s 
                           ∈ 
                           
                             
                               NB 
                               out 
                             
                              
                             
                               ( 
                               
                                 b 
                                 , 
                                 c 
                               
                               ) 
                             
                           
                         
                       
                        
                       
                           
                       
                        
                       
                         
                           χ 
                           sc 
                         
                          
                         
                           
                             
                               G 
                               sjc 
                             
                             
                               G 
                               bjc 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0029]    The system of  FIG. 1A  provides distributed inter-cell mitigation via coordinated power control in OFDMA-based multi-carrier systems. The system maximizes the weighted sum-rate where the weights account for different priority of mobile users and can be dynamically updated to maintain user fairness. The system employs a discrete power control model wherein each BS can transmit using one of the multiple power levels. 
         [0030]      FIG. 1B  shows the relationship between a BS b and its in-neighbor and out-neighbor set. NB_out(b) is the set of BSs that create strong interference to BS b, NB_in is the set of BSs that are strongly interfered by BS b. As discussed in more details below, a basic scheme embodiment can be used to provide distributed inter-cell interference mitigation, and this basic scheme can be enhanced with a prioritized scheme embodiment, a randomized scheme embodiment, and/or enhanced scheme embodiments. The basic scheme aims at reducing the interference without considering the issue of concurrent updates. It is a basic foundational block in which the prioritized and the randomized schemes can be added. 
         [0031]    One issue in any distributed power control problem is the concurrent update of the status of each BS. For example, if two neighboring BSs are interfering with each other, they may simultaneously decide to switch off: in this case, no rate improvement is achieved. To circumvent this drawback, two embodiments are provided: Prioritized embodiment and Randomized embodiment. The Prioritized embodiment requires that during each time slot no two base stations that are two-hop neighbors (as defined in Eq. (5)) be allowed to change their status simultaneously. In the Randomized embodiment, each base station is allowed to change its status with certain transition probability. The Prioritized scheme converges within finite iterations and the Randomized scheme converges with probability one to a state where no BS can change its status to improve the weighted sum modified rate. While multi-carrier systems are discussed herein, single-carrier systems can also benefit from the present solution by considering only one subchannel. Binary power control is a special case of the embodiment with multiple discrete power levels. 
         [0032]    The prioritized scheme and the randomized scheme solve the issue of concurrent updates and make use of the basic scheme. Enhanced schemes are provided to further improve the performance and can be applied to either the prioritized or the randomized scheme. Numerical results show that the proposed distributed processes achieve a significant rate gain over a conventional proportional fair scheduling process without inter-cell cooperation; in particular, the total system throughput using binary power control is improved by about 5%, while the throughput improvement for cell-edge users using binary power control is about 20%. The distributed process can even outperform previously proposed centralized strategies. In addition, the Randomized embodiment converges very fast, achieving most of the aforementioned rate gain within two iterations. Finally, both embodiments require a small amount of feedback. Providing information for the two strongest interfering BSs on each subchannel is sufficient to achieve most of the performance gain. 
         [0033]      FIG. 2  shows an exemplary process for handling the basic scheme of interference mitigation with multiple discrete power levels. First, the process performs initialization. Initially, each BS b assumes that all BS transmit using maximum power a k P 0  on each subchannel, and selects on each subchannel c the user j=j(b,c) that maximizes the weighted rate w j  r bjc . Based on the interference information from the selected user, each BS b computes its out-neighbor set NB out (b,c) on each subchannel and sends a message containing the following information to its out-neighbors (block  332 ): 
         [0034]    i) The weight of selected user j on each subchannel, 
         [0035]    ii) its modified INSR  INSR   bjc  on each subchannel c, 
         [0036]    iii) the individual ISR ISR b′bjc  for each selected out-neighbor on each subchannel c. 
         [0037]    When a BS receives all such messages from its neighbors, it can construct its in-neighbor set NB in (b,c) on each subchannel c. Note that the in-neighbor sets and out-neighbor sets can be made static and semi-static in order to reduce the initial message exchange. 
         [0038]    After initialization, the process runs iteratively to update the power status of each BS (Blocks  333 - 337 ). In each iteration n, each BS b decides its new transmission power on each subchannel c in order to maximize the weighted sum of the modified rates and the summation is taken over itself and the set of in-neighbors. In order words, the power boosting level χ bc  of BS b on subchannel c is chosen to maximize 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         s 
                         ∈ 
                         
                           
                             { 
                             b 
                             } 
                           
                           ⋃ 
                           
                             
                               NB 
                               
                                 i 
                                  
                                 
                                     
                                 
                                  
                                 n 
                               
                             
                              
                             
                               ( 
                               
                                 b 
                                 , 
                                 c 
                               
                               ) 
                             
                           
                         
                       
                     
                      
                     
                         
                     
                      
                     
                       
                         w 
                         
                           j 
                            
                           
                             ( 
                             
                               s 
                               , 
                               c 
                             
                             ) 
                           
                         
                       
                        
                       
                         
                           r 
                           _ 
                         
                         
                           
                             sj 
                              
                             
                               ( 
                               
                                 s 
                                 , 
                                 c 
                               
                               ) 
                             
                           
                            
                           c 
                         
                       
                     
                   
                   = 
                   
                     
                       
                         w 
                         
                           j 
                            
                           
                             ( 
                             
                               b 
                               , 
                               c 
                             
                             ) 
                           
                         
                       
                        
                       
                         
                           log 
                           2 
                         
                         ( 
                         
                           1 
                           + 
                           
                             
                               χ 
                               bc 
                             
                             
                               Γ 
                                
                               
                                 
                                   
                                     I 
                                      
                                     
                                         
                                     
                                      
                                     N 
                                      
                                     
                                         
                                     
                                      
                                     S 
                                      
                                     
                                         
                                     
                                      
                                     R 
                                   
                                   _ 
                                 
                                 bjc 
                               
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           s 
                           ∈ 
                           
                             
                               NB 
                               
                                 i 
                                  
                                 
                                     
                                 
                                  
                                 n 
                               
                             
                              
                             
                               ( 
                               
                                 b 
                                 , 
                                 c 
                               
                               ) 
                             
                           
                         
                       
                        
                       
                           
                       
                        
                       
                         
                           w 
                           
                             j 
                              
                             
                               ( 
                               
                                 s 
                                 , 
                                 c 
                               
                               ) 
                             
                           
                         
                          
                         
                           
                             log 
                             2 
                           
                           ( 
                           
                             1 
                             + 
                             
                               
                                 
                                   χ 
                                   
                                     s 
                                     , 
                                     c 
                                   
                                   
                                     ( 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                                 / 
                                 Γ 
                               
                               
                                 
                                   
                                     
                                       I 
                                        
                                       
                                           
                                       
                                        
                                       N 
                                        
                                       
                                           
                                       
                                        
                                       S 
                                        
                                       
                                           
                                       
                                        
                                       R 
                                     
                                     _ 
                                   
                                   
                                     
                                       sj 
                                        
                                       
                                         ( 
                                         
                                           s 
                                           , 
                                           c 
                                         
                                         ) 
                                       
                                     
                                      
                                     c 
                                   
                                 
                                 + 
                                 
                                   I 
                                    
                                   
                                       
                                   
                                    
                                   S 
                                    
                                   
                                       
                                   
                                    
                                   
                                     
                                       R 
                                       bsjc 
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           χ 
                                           bc 
                                         
                                         - 
                                         
                                           χ 
                                           bc 
                                           
                                             ( 
                                             
                                               n 
                                               - 
                                               1 
                                             
                                             ) 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where χ bc   (n−1)  is the power status in the previous iteration n−1. 
         [0039]    Each BS b will then inform its in-neighbors about its new power boosting levels χ bc  and re-computes its updated interference and noise to power ratio  INSR   bj(b,c)c  on each subchannel c and sends to its out-neighbors ( 336 - 337 ). 
         [0040]    The process terminates when no BS can improve the weighted sum rate as defined in Eq. (8) or a maximum number of iterations is reached. 
         [0041]    The system of  FIG. 2  handles distributed interference mitigation in multi-cell networks. For each subchannel, there is a (possibly different) subset of power levels with which a BS can choose to transmit. The subset of power levels for a subchannel at a particular BS can contain a single positive value (in which case, the BS can only transmit with a fixed power specified by the single positive power level in the subset). The subset of power level normally contains a value 0 which, if selected, indicates that the BS does not transmit on the given subchannel. 
         [0042]    One issue with the above basic scheme is the concurrent update if every BS updates its status without considering that other BSs may also change their status simultaneously. For example, assume that there are only M=2 base stations and one subchannel. If they interfere with each other and both decide to switch off, then the system gets a total rate 0. At the next iteration, both of them will decide to be active. As a result, the process will never stop. To resolve this issue, two approaches are described next. 
         [0043]    In one embodiment referred to as the Prioritized scheme, a limitation is imposed that no two neighbor BSs which are two-hop neighbors (as defined in Eq. (5)) can update their power status at a time. To this end, the system assigns a priority and a time-stamp to each BS. To reduce overhead, the priority and time-stamp are assumed to be common to all subchannels at each base station. The priority of each base station is generated either randomly or using some system parameters (such as the total queue length or the total achieved rate). The system also assumes that all BSs receive a different priority. The time-stamp of each BS is set to zero initially. At each iteration, every BS b still computes the new  INSR   bjc  defined in Eq. (7) and sends it to all out-neighbors. Next it checks its time stamp and priority; if all two-hop neighbors have either a larger time stamp or the same time stamp but lower priority, BS b runs the remaining part of the iteration (i.e., computing its new power status to maximize the weighted sum rate in Eq. (8), notifying its in-neighbors about its status change, and notifying its out-neighbors about its INSR values). Then the BS b increments its time-stamp and reports the new time-stamp to its two-hop neighbors. 
         [0044]      FIG. 3A  shows one exemplary process for performing the Prioritized scheme embodiment. The process of  FIG. 3A  first performs initialization by defining a priority and a timestamp for each BS ( 101 ). The process computes and sends out  INSR   bjc  (and w j , ISR sbjc  if it is the first iteration) ( 102 ). Next, the process checks if no two-hop neighbor has a smaller timestamp or the same timestamp but higher priority ( 103 ). If so, the process runs the remaining part of the iteration (decides new status, update in-neighbors and out-neighbors) and then increments the timestamp ( 104 ). In  103 , if there are neighbors that meet the condition in  103 , the process waits for the next iteration ( 105 ) and loops back to  102 . 
         [0045]    In  FIG. 3A , the timestamp is initially all set to 0 and the priority can be either randomly generated or based on some system parameters such as total queue length or total received throughput in each cell. In each iteration, a BS b checks its two-hop neighbors. If any two-hop neighbor either has a smaller timestamp or the same timestamp but higher priority, BS b does not change its status. Otherwise, the BS b updates its status according to the basic scheme, and increments its timestamp and reports the new timestamp to its two-hop neighbors. 
         [0046]      FIG. 3B  shows another implementation of the prioritized scheme. In this implementation, the initialization of the process ( 40 ) is similar to block  332  of  FIG. 2 , with the addition that the priority and the timestamp are defined for each BS. Next, in block  41 , each BS b computes  INSR   b,j(b,f)f  and sends to out-neighbors. If this is the first iteration, BS b also sends w j  and the individual ISR ISR s,b,j(b,c),c  for each out-neighbor BS s. The process then checks whether any two-hop neighbors have a smaller timestamp or the same timestamp but higher priority (block  42 ). If so, the process waits for the next iteration and loops back to block  41 . Alternatively, f no such two-hop neighbor exists, each BS b decides its new status on each subchannel c to maximize the weighted sum rates in Eq. (8) (block  333 ). The termination conditions are checked in block  43  and if satisfied, the process stops. Unless the stopping conditions are satisfied, BS b reports its new power status to its in-neighbors, increments its timestamp, and reports the new timestamp to the two-hop neighbors (block  44 ). 
         [0047]    The Prioritized scheme converges (terminates) within finite steps. There are several special cases (or variants) that satisfy the requirement in the Prioritized scheme. For example, if the base station status is updated sequentially (i.e, at most one BS may update its status at each iteration), or if any two BSs that are two-hop neighbors cannot change their status simultaneously, the process converges. A simple variant that converges within finite steps is the following. Each BS computes its new status to maximize the weighted sum-rates. All BSs that are two-hop neighbors exchange the respective (possibly quantized) gains in the weighted system rate that can be obtained if they are allowed to update. Only the BS with the highest respective gain is allowed to update and ties are broken using any pre-determined rule such as allowing the BS with the lowest index or highest priority to update. 
         [0048]    In another approach, the issue of concurrent update is resolved using a probabilistic approach. This scheme is the Randomized scheme embodiment.  FIG. 4A  shows one implementation of the randomized scheme. At each iteration, each BS runs the interference mitigation process without changing its activity status ( 200 ). The process checks if changing status is needed ( 201 ). If the interference-mitigation process suggests decreasing the power level on subchannel c, the BS will change its power level on that subchannel with probability p 1 &gt;0 ( 203 ). Instead, if the process suggests increasing the power level on subchannel c, then the BS will change its power level with probability p 2 &gt;0 ( 204 ). Otherwise, the base station maintains the previous state. 
         [0049]    In one variant, p 1  and p 2  may depend on the respective gain in the weighted sum rates if the power level of a BS is updated. In fact, a finite table of probability values versus gain value range that each BS can use can be computed and this table can be BS and sub-channel dependent. 
         [0050]      FIG. 4B  shows a flow-chart of another implementation of the Randomized distributed interference mitigation process. In block  50 , the process performs initialization (i.e., select users in each subchannel, create in-neighbor and out-neighbor set). The next step is the same as the Block  41  in  FIG. 3B . Each BS b computes  INSR   b,j(b,c),c  and sends it to out-neighbors. If this is the first iteration, BS b also sends w j  and the individual ISR ISR sbjc  for each out-neighbor BS s. In block  51 , each BS b computes its new power status on each subchannel c to maximize the weighted sum rate in Eq. (8), but the BS does not actually change its status. Each BS b then checks whether the new power level differs from the old one in block  52 . If so, it further checks whether the new power level is lower than the present one in block  53 . If so, the BS changes to the new power level with probability p 1 &gt;0 and if not, the BS changes to the new power level with probability p 2 &gt;0. Then each BS determines whether the terminating conditions are satisfied (block  43 ). If so, the process exits. Alternatively, he BS b reports its new status to its in-neighbors in block  336  and the process loops back to block  41  to continue. 
         [0051]    An exemplary pseudo-code for the process of  FIG. 4B  is as follows: 
         [0000]    
       
         
               
             
               
             
           
               
                   
               
               
                 Randomized interference mitigation scheme: 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Each BS first selects the user on each subchannel to maximize weighted 
               
               
                 data rate and then in each iteration, each BS updates its power on each 
               
               
                 subchannel as if neighboring BSs&#39; transmission power is fixed. 
               
               
                 Initialization: 
               
               
                 Each BS b selects the user (block 50) on each subchannel that has the 
               
               
                 maximum weighted data rate w j  r j  where the user rate r j  is defined by 
               
               
                 r = log 2 (1 + SINR/Γ), computes its out-neighbor set on each subchannel 
               
               
                 and sends to each out-neighbor BS the following information on each 
               
               
                 subchannel c (block 41): 
               
               
                 a) its total modiefied INSR  INSR   b,j,c  on the subchannel c, 
               
               
                 b) the individual ISR ISR s,b,j,c  for each out-neighbor BS s. 
               
               
                 c) The weight w j  of the selected user on subchannel c. 
               
               
                 When a BS receives messages from neighboring BSs, it can construct its 
               
               
                 in-neighbor set NB in (b, c) on each subchannel. 
               
               
                 Iteration: Each iteration includes three steps. 
               
               
                 i) Each BS b computes its optimal power to maximize the weighted sum 
               
               
                 rate T b,c  of itself and its in-neighbors on subchannel c (block 51) assuming 
               
               
                 that neighboring BSs do not change their transmission power: 
               
               
                   
               
               
                 
                   
                     
                       
                         
                           T 
                           
                             b 
                             , 
                             c 
                           
                         
                         = 
                         
                           
                             
                               w 
                               
                                 j 
                                  
                                 
                                   ( 
                                   
                                     b 
                                     , 
                                     c 
                                   
                                   ) 
                                 
                               
                             
                              
                             
                               
                                 r 
                                 _ 
                               
                               
                                 b 
                                 , 
                                 
                                   j 
                                    
                                   
                                     ( 
                                     
                                       b 
                                       , 
                                       c 
                                     
                                     ) 
                                   
                                 
                                 , 
                                 c 
                               
                             
                           
                           + 
                           
                             
                               ∑ 
                               
                                 s 
                                 ∈ 
                                 
                                   NB_in 
                                    
                                   
                                     ( 
                                     
                                       b 
                                       , 
                                       c 
                                     
                                     ) 
                                   
                                 
                               
                             
                              
                             
                                 
                             
                              
                             
                               
                                 w 
                                 
                                   j 
                                    
                                   
                                     ( 
                                     
                                       s 
                                       , 
                                       c 
                                     
                                     ) 
                                   
                                 
                               
                                
                               
                                 
                                   r 
                                   _ 
                                 
                                 
                                   s 
                                   , 
                                   
                                     j 
                                      
                                     
                                       ( 
                                       
                                         s 
                                         , 
                                         c 
                                       
                                       ) 
                                     
                                   
                                   , 
                                   c 
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                   
               
               
                 Let T b,c  be the optimal value (where the transmission power is chosen from 
               
               
                 the subset of allowed transmission power for BS b on subchannel c) and 
               
               
                 T b,c   0  be the value with the current power level. If T b,c  &gt; (1 + Δ)T b,c   0 , 
               
               
                 BS b changes its transmission power on subchannel c to the optimal power 
               
               
                 level with a probability p. This probability p may depend on whether the 
               
               
                 transmission power is increased or decreased. If the optimal power is less 
               
               
                 than the current power, we change the power level to the optimal value 
               
               
                 with probability p 1  and otherwise change the power with probability p 2 . 
               
               
                 ii) Each BS notifies its in-neighbors about its new transmission power on 
               
               
                 each subchannel if updated. 
               
               
                 iii) When a BS receives the new transmission power from its out- 
               
               
                 neighbors, it re-computes its total modified INSR  INSR   b,j,c  and sends 
               
               
                 back to its out-neighbors. 
               
               
                   
               
             
          
         
       
     
         [0052]    In the Randomized scheme, multiple BSs can simultaneously change their status at each iteration, and there is a non-zero probability that they all switch off on a given subchannel. The value of the objective function (3) is not guaranteed to be non-decreasing at each iteration. Nonetheless, the Randomized scheme will converge with probability 1 to a terminating state, which is a state where changing the activity status of any single BS cannot improve the weighted sum of modified rates. 
         [0053]    In the aforementioned basic Randomized or Prioritized scheme, the user on each subchannel of each cell is selected assuming that all other cells are active and is fixed during the execution of the interference mitigation process. Two possible enhancements can be done where the user selection is updated during the execution of the interference mitigation process:
       A) The user on each subchannel is re-selected after each iteration of the basic process.   B) The user on each subchannel is re-selected after the randomized/prioritized process converges.
 
Each enhancement can be applied to both Prioritized and Randomized schemes. In all cases, users are re-selected to improve the modified rate in each cell and user re-selection does not affect the rate calculation in other cells. In both enhancements, it is best to fix the out-neighbor sets and in-neighbor sets (e.g., based on average power and interference levels). In this case, since the user re-selection monotonically improves the system weighted modified rate, the above enhancements do not affect the convergence of the process.
       
 
         [0056]      FIG. 5A  and  FIG. 5B  show exemplary flow-charts of Enhancements A and B to the embodiments of  FIGS. 3A-3B  and  FIGS. 4A-4B , respectively. In either enhancement, initialization is done (block  70 ). Next, in block  72 , the system executes the main iteration section in the Prioritized scheme (blocks  41 ,  42 ,  333 ,  43 ,  44 ) or the Randomized scheme (blocks  41 ,  51 - 55 ,  43 ,  336 ). 
         [0057]    For enhancement A, the process of  FIG. 5A  re-selects users on each subchannel in each BS to improve the weighted modified rate in each cell (block  74 ). The process then reports to out-neighbors for each re-selected user about the total INSR, weight of user, and the individual ISR (block  76 ). 
         [0058]    Alternatively, for enhancement B, the process of  FIG. 5B  executes the Prioritized scheme or the Randomized scheme as in  FIG. 3A-B  or  4 A-B in block  82 . Next, in block  84 , the enhancement B re-selects users on each subchannel in each BS to improve the weighted modified rate in each cell. 
         [0059]    When the user is changed on a subchannel of a cell, the set of out-neighbors on that subchannel in the cell is updated and need to be informed. Thus, for either enhancement, the processes of  FIGS. 5A and 5B  report to in-neighbors about its new power status (block  78 ). For the Prioritized scheme, the new timestamp is sent to two-hop neighbors if it is changed. Therefore, the above enhanced scheme A requires more communication overhead than the enhanced scheme B. However, enhancement B takes longer time to converge. 
         [0060]    In all the aforementioned processes, the BS can have multiple power levels on each subchannel. A special case is binary power control, in which the BS can only be either on or off in each subchannel. The procedures for the binary power control are identical except that the there are only two possible power levels to pick. Namely, χ bc =0 or 1. The procedure for binary power control is discussed in Provisional Application 61/079,489 filed Jul. 10, 2008, the content of which is incorporated by reference. 
         [0061]      FIG. 5C  shows various embodiments to perform interference mitigation. In one variation, BSs can perform interference mitigation using average channel conditions and interference levels rather than instantaneous ones. In another variation, not all BSs need to actively perform interference mitigation at all time. Instead, each BS (called source BS) can continuously monitor its own interference situation, decide to mitigate interference, and then collect interference information and related parameters from the MSs and the neighbor cells. Then the source BS decides which neighbor BSs are the out-neighbor BSs and sends them necessary information to compute the weighted rate at the source BS if changing their interference parameters (i.e., power levels). The out-neighbor BSs are the set of BSs that may need to control their power, and are thus called target BSs. Each target BS decides whether to change its power settings based on the procedures described in this document and sends back the response to the source BSs. 
         [0062]    The performance of the interference mitigation strategies has been tested through Monte-carlo simulations. A 7-cell network is simulated, as shown in  FIG. 6 . Each cell has three sectors. The cell radius is set to 1000 meters and mobile devices are dropped uniformly in the circle covering the shaded area but at least 50 meters away from any BS. Wrap-around topology is used. Thus, any mobile receives signals from the nearest 7 image cells. In  FIG. 6 , the 7 grey cells are simulated and wraparound is assumed. The arrows show the 6 image cells of a shaded cell C. Simulations are based on the 802.16m evaluation methodology document for A 10 MHz channel bandwidth but only 30 subchannels are simulated. The main system parameters are summarized in Table 1. 
         [0000]                                                    TABLE 1               System parameters                                    Number of BS   7           Number of sectors in each BS   3           Number of subcarriers (C)   30           Number of users (N)   100                Transmit power   46   dBm           Noise power spectrum density   −174   dBm/Hz           Channel bandwidth   10   MHz           BS antenna gain   17   dB           MS antenna gain   0   dB           cable loss   2   dB           Penetration loss   10   dB           Noise figure   5   dB                        
The BS-to-user channel undergoes pathloss, shadow fading and fast fading. The long-term channel gain from BS/sector i to user j is modeled as
 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       g 
                       ij 
                     
                     = 
                     
                       
                         G 
                         0 
                       
                       · 
                       
                         
                           s 
                           ij 
                         
                         
                           
                             L 
                             ij 
                           
                           · 
                           
                             
                               A 
                               ij 
                             
                              
                             
                               ( 
                               θ 
                               ) 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the pathloss model L ij  (in dB) used for the simulation is 
         [0000]        L ( d )=36.2+35log 10   d,    (20) 
         [0000]    where d is the distance between the BS and the user. The radiation pattern A(θ) (in dB) of the antenna in each sector is 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       A 
                        
                       
                         ( 
                         θ 
                         ) 
                       
                     
                     = 
                     
                       min 
                        
                       
                         ( 
                         
                           
                             12 
                              
                             
                               
                                 ( 
                                 
                                   θ 
                                   
                                     θ 
                                     
                                       3 
                                        
                                       
                                           
                                       
                                        
                                       d 
                                        
                                       
                                           
                                       
                                        
                                       B 
                                     
                                   
                                 
                                 ) 
                               
                               2 
                             
                           
                           , 
                           
                             A 
                             m 
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where θ 3 dB =70° is the 3 dB beamwidth and A m =20 dB is the maximum attenuation. The effect of shadowing S ij  is modeled as a log-normal distribution with standard deviation of 8 dB and inter-BS correlation coefficient of 0.5. G 0  captures the combined gain of the BS/MS antenna gain, the noise figure, cable loss, and penetration loss. G 0  s set to 0 dB in the simulations. 
         [0063]    The maximum Doppler spread of the fast fading component is assumed to be 10 Hz for all users. The six-path ITU Pedestrian B model is used; the path delay and the power delay profile are given by 
         [0000]      Delay(ns)=[200 800 1200 2300 3700] 
         [0000]      Power (dB)=[−3.9 −4.8 −8.8 −11.9 −11.7 −27.7]. 
         [0064]    The user weight in each iteration is based the proportional fairness scheduling , which is the inverse of the exponential moving average of the achieved sum-rates on all subchannels. Unless specified, other parameters are set as follows: Γ=1, K=6 and β=0.01(i.e., −20 dB). The simulation results presented here is only for binary power control (i.e., the power status on each subchannel can be only either on or off). Better performance is expected with multiple power levels. 
         [0065]    All simulations are executed for 1000 time slots and 10 simulation runs are executed with different random seeds in each run. The throughput reported is the time averaged user throughput divided by the number of subchannels in the system. The throughput reported is calculated based on Eq. (1) and (3), and each BS computes the modified user rates based on Eq. (7). 
         [0066]    In the first part of the simulations, the users in each cell are selected at the beginning of each time slot assuming that all cells are active and the user selection is fixed during the same time slot. 
         [0067]      FIG. 7A  shows the achieved average user rate for the proposed Prioritized and Randomized distributed schemes and for the references strategies. For clarity, users are sorted in the order of the throughput they receive: with 100 users in each run and 10 simulation runs, 1000 data points are generated. Since the performance improvement of the other schemes over the conventional PFS scheme is not clear, the 1000 data points are divided into 100-point bins in the order of their throughput: the k-th bin contains the data points from the (100(k−1)+1 th  to the (100 k) th  highest throughput. 
         [0068]      FIG. 7B  shows a plot of the percentage of the average rate improvement of the other three schemes over the PFS scheme. As shown in  FIG. 7B , for about 30% of users (which are mostly cell-edge users) the average throughput improves by 15-20%; for more than 80% of users, the average throughput improves by over 5%. This comes at the price of no more than 5% throughput drop for the top 10% users that receive the highest throughput. The system&#39;s distributed processes slightly outperform the centralized scheme. The greedy centralized process provides the best throughput for cell-edge users, but worst throughput for inner users. 
         [0069]    The convergence of the proposed distributed process is analyzed next.  FIG. 8  shows the number of iterations required to achieve convergence at each run. As expected, the Prioritized process requires a larger number of iterations to converge, since only a limited number of BSs update their status at each iteration. Instead, the Randomized scheme takes on the average only 6 iterations to converge. 
         [0070]    Next, a throughput analysis is done for the Randomized scheme and the Prioritized scheme stopped after a maximum number of iterations is executed.  FIG. 9  shows the average user throughput as the maximum number of iterations increases for each scheme. Remarkably, the Randomized process achieves most of the throughput improvement with only two iterations. 
         [0071]    In both the Prioritized and the Randomized scheme, each BS reports at most K strongest interfering BSs in each subchannel.  FIG. 10  shows how the value of K affects the overall performance while setting β=0.01. As the maximum number of reported interfering BSs increases, the average actual number of reported interfering BSs (and thus the communication overhead) and the average user throughput both increase. However, remarkably, reporting the two most significant interfering BSs is already sufficient to achieve most of the rate gain. 
         [0072]    In both the Prioritized and the Randomized schemes, each BS only reports an interfering BS if the ratio of the interfering BSs signal to the serving BSs signal is greater than a threshold β. The following discussion shows how the threshold β affects the average user throughput while the maximum number of reported interfering BSs K is set to 6.  FIG. 11  shows the tradeoff between the user throughput and the value β. With a decreasing value β, the average number of reported interfering BSs (the overhead) increases while the average user throughput also increases. But further reducing β beyond −20 dB from the signal value has limited improvement of the user throughput. 
         [0073]    The benefits of the enhanced schemes are discussed next where the users are re-selected during the process execution. Because the Randomized scheme achieves almost exactly the same throughput as the Prioritized scheme but converges much faster, only the enhanced Randomized scheme is considered. Similar to  FIG. 7B , the data points of time-average user throughput are sorted and grouped into 10 bins to show the average throughput improvement over PFS in  FIG. 12 . It can be seen that both enhanced schemes further improve the cell-edge user throughput by an additional 2-4%. However, the enhanced scheme 2 takes much longer time to converge than the basic Randomized scheme and the enhanced scheme 1. The enhanced scheme 1 achieves the shortest convergence time because an improved user selection makes the system closer to the terminating states. 
         [0074]    The foregoing system provides inter-cell interference mitigation via coordinated power control in wireless cellular data networks. Two iterative distributed processes can be used to maximize the network weighted sum-rate. The schemes converge to a state where no single BS can change its status to improve the weighted throughput. Simulation results indicate that the proposed process improve the global system throughput by about 5% and the throughput of cell-edge users by almost 20%.