Patent Abstract:
A method for scheduling transmissions in wireless network includes receiving information ranging from conventional data to real-time streaming applications into a basestation of an OFDMA wireless relay network and scheduling transmission of the information from the basestation by influencing adaptive frame segmentation and access hop reuse in the transmission of the information for achieving higher transmission flow of the information, Where the scheduling is formulated as an integer program, the scheduling includes solving a linear programming relaxation of the integer program and rounding to integral allocations with allocation to at least one of a subset of wireless users and subsets of relays in the network for obtaining frame segmentation and reuse. Where the scheduling is formulated by following a bisection approach to guide adaptation of the frame segmentation, the scheduling determines a subset of users with maximum flow per unit resource for a given frame segmentation and the resulting flow from current and previous scheduling being used to guide adaptation of frame segmentation towards convergence.

Full Description:
This application claims the benefit of U.S. Provisional Application No. 61/368,402, entitled, “Scheduling Algorithms for Adaptive Resource Usage in OFDMA Relay Networks”, filed Jul. 28, 2010, of which the contents of both are incorporated herein by reference. 
    
    
     BACKGROUND OF THE INVENTION 
     The present invention relates generally to broadband and wireless communications and more particularly to a scheduling method for adaptive resource usage in orthogonal frequency-division multiple access OFDMA wireless relay networks. 
     There has been an increasing demand to provide ubiquitous mobile access for a multitude of services ranging from conventional data to real-time streaming applications. To meet such requirements, existing cellular systems need enhancement to provide improved data rates and connectivity. Adding less sophisticated and less expensive “relay” stations (RS) to the network helps improve the throughput and coverage in the network. 
     Unlike conventional cellular networks, the throughput performance of relay networks is closely tied to maximizing the network flow (throughput capacity) over the two hops of the network. This is however dependent on how well the available OFDMA resources are utilized on the two hops of the network. The upcoming relay standards in next generation broadband access technologies like WiMAX allow for two design features to accomplish this: (i) adaptive frame segmentation, and (ii) access hop reuse. While prior art has focused on designing scheduling algorithms for leveraging diversity and reuse across hops, they have not focused on designed scheduling methods that optimize adaptive frame segmentation and reuse within the access hop to efficiently utilize OFDMA resources. 
     Prior scheduling works in OFDMA relays have focused largely on leveraging diversity gains. One prior work considered spatial reuse across relay and access hops, but did not consider reuse within the access hop. Further, none of these works have studied the impact of adaptive frame segmentation coupled with access hop reuse on the network capacity through design of efficient scheduling algorithms with performance guarantees. 
     Accordingly, there is a need for an improved unicast throughput performance of relay-assisted OFDMA cellular networks through efficient usage of OFDMA resources. 
     BRIEF SUMMARY OF THE INVENTION 
     The invention is directed to a method for scheduling transmissions in wireless network including receiving information ranging from conventional data to real-time streaming applications into a basestation of an OFDMA wireless relay network; and scheduling transmission of the information from the basestation by influencing adaptive frame segmentation and access hop reuse in the transmission of the information for achieving higher transmission flow of the information, the scheduling including where the scheduling is formulated as an integer program, solving linear programming relaxation of the integer program with allocation to at least one of subset of wireless users and subsets of relays in the network for obtaining a fractional frame segmentation, where the scheduling is formulated by following a bisection approach to guide adaptation of the frame segmentation, the scheduling determining a bottleneck in the scheduling transmission for a given fractional frame segmentation and the resulting flow from current and previous scheduling being guided for adaptation towards convergence. 
     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. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1A  is a block diagram representing adaptive resource usage scheduler with scheduling components  100 ,  200 , and  300  at a basestation, in accordance with the invention; 
         FIG. 1  is a diagram of an linear programming (LP)-based scheduler with high performance LSAR 1  component  100  with high performance, in accordance with the invention; 
         FIG. 2  is a diagram of an LP-based scheduler with low complexity LSAR 2  component  200 , in accordance with the invention; and 
         FIG. 3  is a diagram of a greedy scheduler GSAR component  300 , in accordance with the invention; 
     
    
    
     DETAILED DESCRIPTION 
     The present invention is directed to the problem of designing scheduling methods to optimize frame segmentation and access hop reuse, which is a non-deterministic polynomial-time (NP) hard problem. Hence, the invention provides for an efficient scheduling method with good worst-case performance guarantees and near-optimal performance in practice. It also provides a simple greedy process with good performance that makes it conducive for implementation at the base station 
     Referring now  FIG. 1A , a basestation BS scheduler, responsive to user rates, provides a transmission schedule based on adaptive frame segmentation and access hop reuse. The scheduler employs an LP-based scheduler with high performance LSAR 1  ( 100 ) detailed in  FIG. 1 , an LP-based scheduler with low complexity LSAR 2  ( 200 ) detailed in  FIG. 2 , and a greedy scheduler GSAR ( 300 ) detailed in  FIG. 3 . For purposes of discussion, LP denotes linear programming and SAR denotes per-frame scheduling for adaptive resource usage and LSAR denotes linear programming schedule for adaptive resource usage. 
     Referring now to  FIG. 1 , diagram for the LP-based scheduler with high performance LSAR 1  ( 100 ), the scheduling problem is formulated as an integer program using subset allocation as variables  101 . 
     
       
         
           
             PSAR 
             ⁢ 
             
               : 
             
             ⁢ 
             
                 
             
             ⁢ 
             Maximize 
             ⁢ 
             
                 
             
             ⁢ 
             
               
                 ∑ 
                 
                   s 
                   = 
                   1 
                 
                 
                    
                   S 
                    
                 
               
               ⁢ 
               
                 F 
                 s 
               
             
           
         
       
       
         
           
             
               s 
               . 
               t 
               . 
             
             , 
             
                 
             
             ⁢ 
             
               
                 
                   
                     ∑ 
                     
                       k 
                       ∈ 
                       s 
                     
                   
                   ⁢ 
                   
                     
                       w 
                       
                         k 
                         , 
                         s 
                       
                       rel 
                     
                     ⁢ 
                     
                       X 
                       s 
                     
                   
                 
                 ≥ 
                 
                   F 
                   s 
                 
               
               ; 
               
                 ∀ 
                 
                   s 
                   ∈ 
                   S 
                 
               
             
           
         
       
       
         
           
             
               
                 
                   ∑ 
                   
                     k 
                     ∈ 
                     s 
                   
                 
                 ⁢ 
                 
                   
                     w 
                     
                       k 
                       , 
                       s 
                     
                     acc 
                   
                   ⁢ 
                   
                     Y 
                     s 
                   
                 
               
               ≥ 
               
                 F 
                 s 
               
             
             ; 
             
               ∀ 
               
                 s 
                 ∈ 
                 S 
               
             
           
         
       
       
         
           
             
               
                 
                   ∑ 
                   s 
                 
                 ⁢ 
                 
                   X 
                   s 
                 
               
               ≤ 
               
                 γ 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 N 
               
             
             ; 
             
               
                 X 
                 s 
               
               ∈ 
               
                 { 
                 
                   0 
                   , 
                   1 
                   , 
                   … 
                   ⁢ 
                   
                       
                   
                   , 
                   
                     γ 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     N 
                   
                 
                 } 
               
             
           
         
       
       
         
           
             
               
                 
                   ∑ 
                   s 
                 
                 ⁢ 
                 
                   Y 
                   s 
                 
               
               ≤ 
               
                 
                   ( 
                   
                     T 
                     - 
                     γ 
                   
                   ) 
                 
                 ⁢ 
                 N 
               
             
             ; 
             
               
                 Y 
                 s 
               
               ∈ 
               
                 { 
                 
                   0 
                   , 
                   1 
                   , 
                   … 
                   ⁢ 
                   
                       
                   
                   , 
                   
                     
                       ( 
                       
                         T 
                         - 
                         γ 
                       
                       ) 
                     
                     ⁢ 
                     N 
                   
                 
                 } 
               
             
           
         
       
       
         
           
             where 
             , 
             
               γ 
               ∈ 
               
                 { 
                 
                   0 
                   , 
                   1 
                   , 
                   … 
                   ⁢ 
                   
                       
                   
                   , 
                   T 
                 
                 } 
               
             
             , 
             
               S 
               = 
               
                 { 
                 
                   
                     S 
                     1 
                   
                   × 
                   
                     S 
                     2 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   … 
                   × 
                   
                     S 
                     R 
                   
                 
                 } 
               
             
           
         
       
     
     Where N and T are the total number of channels and time slots, resulting in NT tiles in total for allocation; Xs and Ys indicate the # tiles allocated to subset s on relay and access hops respectively; a subset corresponds to a set of users with at most one user being picked from each relay; Fs is the weighted flow obtained subset s, which is given by the minimum flow resulting from the relay and access hops; S i  denotes the set of users associated with relay i (including a null user). 
     The weighted flow for a user in a subset (if user belongs to subset) on the access hop is given by: w k,s   acc =w k r k,s   acc , where w k  is the weight of the user taking into account fairness and quality of service QoS, while r k,s   acc  is the rate of the user in the presence of interference from other users in the subset who will be scheduled in tandem with the user, reusing the same allocated tiles. 
     The weighted flow for a user in a subset (if user belongs to subset) on the relay hop is given by: determining the relative fraction of time a user needs to be active in the subset on the relay hop to deliver a given flow from the access hop: 
                 w     k   ,   s     rel     =       w     k   ,   s     acc         ∑     j   ∈   s       ⁢       w     j   ,   s     acc       w   j   rel             ,         
where w k,s   acc =w k r k,s   acc .
 
     Solve the LP relaxation of the above integer program to obtain optimal fractional frame segmentation γ*. 
     Then the scheduler  102  re-solves the LP relaxation of the above integer program with fixed integral γ=floor(γ*). Let output be Xs* and Ys*. 
     The scheduler continues  103  to round fractional allocations on access hop to the smallest integer larger than itself: Ŷ s =┌Y s *┐, ∀s; determine additional τ tiles needed over (T−γ)N: τ=Σ s Ŷ s −(T−γl)N store corresponding subsets in Γ: [Γ(1), . . . , Γ(τ)] 
     The scheduler  104  removes τ tiles yielding the smallest flow from the existing access hop allocation: Γ: Ŷ s =Ŷ s −1, ∀sεΓ. 
     The scheduler  105  determines flow for each user from access hop subset allocations; update user flow and fractional allocation on relay hop. The scheduler updates relay hop and allocation for each subset and user according to: 
     
       
         
           
             
               
                 X 
                 s 
                 * 
               
               = 
               
                 
                   min 
                   ⁢ 
                   
                     { 
                     
                       
                         F 
                         s 
                         * 
                       
                       , 
                       
                         
                           ∑ 
                           
                             k 
                             ∈ 
                             s 
                           
                         
                         ⁢ 
                         
                           
                             w 
                             
                               k 
                               , 
                               s 
                             
                             acc 
                           
                           · 
                           
                             
                               Y 
                               ^ 
                             
                             s 
                           
                         
                       
                     
                     } 
                   
                 
                 
                   
                     ∑ 
                     
                       k 
                       ∈ 
                       s 
                     
                   
                   ⁢ 
                   
                     w 
                     
                       k 
                       , 
                       s 
                     
                     rel 
                   
                 
               
             
             , 
             
               
                 ∀ 
                 s 
               
               ; 
               
                 
                   Z 
                   k 
                   * 
                 
                 = 
                 
                   
                     
                       ∑ 
                       
                         s 
                         : 
                         
                           k 
                           ∈ 
                           s 
                         
                       
                     
                     ⁢ 
                     
                       
                         w 
                         
                           k 
                           , 
                           s 
                         
                         rel 
                       
                       ⁢ 
                       
                         X 
                         s 
                         * 
                       
                     
                   
                   
                     w 
                     k 
                     rel 
                   
                 
               
             
             , 
             
               ∀ 
               k 
             
           
         
       
     
     The scheduler  106  converts fractional allocations to integral ones by assigning a tile to a user with probability equal to the user&#39;s fractional allocation; obtain output flow: 
     Let Z k,I *=└Z k *┘, Z k,Q *=Z k *−Z k,I *. 
     Assign integral allocations to respective users: {circumflex over (Z)} k =Z k,I *, ∀k. 
     With remaining η tiles: η=γ l N−Σ k Z k,I *; 
     For η tiles, assign a tile to user k: {circumflex over (Z)} k ={circumflex over (Z)} k +1 with probability Z k,Q *. 
     Output flow: C(γ l )=Σ k  min{{circumflex over (Z)} k ; Z k *}w k   rel    
     The scheduler  107  then re-solves the LP relaxation with fixed γ=floor(γ*)+1; Repeat steps  103 - 106  to obtain another schedule. Lastly the scheduler  108  outputs the better of the schedules (higher flow) among those corresponding to γ=floor(γ*) and γ=floor(γ*)+1. 
     Turning now to  FIG. 2  diagram for the LP-based scheduler for adaptive resource usage with low complexity LSAR 2 ( 200 ), the scheduler  201  formulates the scheduling problem as an integer program using both subset and user allocation as variables. CSAR denotes low complexity schedule of adaptive resource usage. 
     
       
         
           
             CSAR 
             ⁢ 
             
               : 
             
             ⁢ 
             
                 
             
             ⁢ 
             Maximize 
             ⁢ 
             
               
                 ∑ 
                 k 
               
               ⁢ 
               
                 F 
                 k 
               
             
           
         
       
       
         
           
             
               subject 
               ⁢ 
               
                   
               
               ⁢ 
               to 
             
             , 
             
               
                 
                   
                     w 
                     k 
                     rel 
                   
                   ⁢ 
                   
                     X 
                     k 
                   
                 
                 ≥ 
                 
                   F 
                   k 
                 
               
               ; 
               
                 ∀ 
                 k 
               
             
           
         
       
       
         
           
             
               
                 
                   ∑ 
                   
                     a 
                     : 
                     
                       
                         R 
                         ⁡ 
                         
                           ( 
                           k 
                           ) 
                         
                       
                       ∈ 
                       s 
                     
                   
                 
                 ⁢ 
                 
                   
                     w 
                     
                       k 
                       , 
                       s 
                     
                     acc 
                   
                   ⁢ 
                   
                     Y 
                     
                       k 
                       , 
                       s 
                     
                   
                 
               
               ≥ 
               
                 F 
                 k 
               
             
             ; 
             
               ∀ 
               k 
             
           
         
       
       
         
           
             
               
                 
                   ∑ 
                   k 
                 
                 ⁢ 
                 
                   X 
                   k 
                 
               
               ≤ 
               
                 γ 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 N 
               
             
             ; 
             
               
                 X 
                 k 
               
               ∈ 
               
                 
                   { 
                   
                     0 
                     , 
                     1 
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       γ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       N 
                     
                   
                   } 
                 
                 ⁢ 
                 
                   { 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         
                           
                             ∑ 
                             
                               
                                 k 
                                 : 
                                 
                                   R 
                                   ⁡ 
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                               
                               = 
                               r 
                             
                           
                           ⁢ 
                           
                             Y 
                             
                               k 
                               , 
                               s 
                             
                           
                         
                         ≤ 
                         
                           Y 
                           s 
                         
                       
                       ; 
                       
                         ∀ 
                         
                           r 
                           ∈ 
                           s 
                         
                       
                     
                     , 
                     
                       
                         ∀ 
                         
                           s 
                           ∈ 
                           
                             
                               ℛ 
                               ⁢ 
                               
                                 
 
                               
                               ⁢ 
                               
                                 
                                   ∑ 
                                   s 
                                 
                                 ⁢ 
                                 
                                   Y 
                                   s 
                                 
                               
                             
                             ≤ 
                             
                               
                                 ( 
                                 
                                   T 
                                   - 
                                   γ 
                                 
                                 ) 
                               
                               ⁢ 
                               N 
                             
                           
                         
                       
                       ; 
                       
                         Y 
                         s 
                       
                     
                     , 
                     
                       
                         Y 
                         
                           k 
                           , 
                           s 
                         
                       
                       ∈ 
                       
                         
                           { 
                           
                             0 
                             , 
                             1 
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               
                                 ( 
                                 
                                   T 
                                   - 
                                   γ 
                                 
                                 ) 
                               
                               ⁢ 
                               N 
                             
                           
                           } 
                         
                         . 
                         
                           
 
                         
                         ⁢ 
                         where 
                       
                     
                     , 
                     
                       γ 
                       ∈ 
                       
                         { 
                         
                           0 
                           , 
                           1 
                           , 
                           … 
                           ⁢ 
                           
                               
                           
                           , 
                           T 
                         
                         } 
                       
                     
                     , 
                     
                       ℛ 
                       = 
                       
                         { 
                         
                           Subsets 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           of 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           relays 
                         
                         } 
                       
                     
                   
                 
               
             
           
         
       
     
     The key difference between the formulations in LSAR 1  of  FIG. 1  and LSAR 2  of  FIG. 2  is that LSAR 2  considers only subsets of relays instead of subsets of users in LSAR 1 . This significantly reduces the # subsets and hence complexity from O(K^R) to O(R^R). However, for each subset allocation (Ys), there could be multiple users sharing the subset allocation within each relay in the subset (Y(k,s)). 
     The procedure to determine the optimal frame segmentation is similar to that in LSAR 1 . Hence, steps  201 ,  202 ,  207  and  208  are similar to steps  101 ,  102 ,  107  and  108 . The difference lies in how the fractional allocations from the LP relaxation of the above formulation are converted to integral allocations. This is discussed in the following steps  203 - 206 . 
     Step  203 , the scheduler rounds fractional allocations to subsets of relays on access hop to the smallest integer larger than itself; determine additional τ tiles needed over (T−γ)N: Ý s =┌Y s *┐, let {circumflex over (Z)} s =Ŷ s  rem=Σ s Ŷ s −(T−γ)N. 
     In step  204   a  the scheduler determines integral allocation for users given a subset allocation; apply greedy rounding yielding smallest loss during integral tile allocation. Integral allocation within each relay with Ŷ s  as input: Output Ŷ k,s , ∀(k): R(k)=r, ∀rεs. 
     In step  204  the scheduler determines marginal loss due to one tile from each subset; remove a tile from subset yielding the smallest marginal loss—update the subset&#39;s marginal loss; repeat till τ tiles have been removed. Similarly obtain integral allocation with {circumflex over (Z)} s =Ŷ s −1 as input: Output {circumflex over (Z)} k,s , ∀k: R(k)=r, ∀rεs. Determine flow loss from one tile: ΔL s =Σ rεs Σ k:R(k)=r (Y k,s −Z k,s )w k,s   acc . The remaining step  204  substeps include the following recursive sequence: 
     while rem=0 do
         Determine ŝ=arg min s {ΔL s }   Reduce ŝ allocation by a tile: Ŷ ŝ =Ŷ ŝ −1; Update rem=rem−1   Update integral allocation for subset ŝ with Ŷ ŝ  as input:   Output Ŷ k,ŝ , ∀k: R(k)=r, ∀rεŝ   Update integral allocation for ŝ with {circumflex over (Z)} ŝ =Ŷ ŝ −1 as input: Output {circumflex over (Z)} k,ŝ , ∀k: R(k)=r, ∀rεŝ   Update marginal loss for ŝ: ΔL s =Σ rεŝ Σ k:R(k)−r (Ŷ k,ŝ −{circumflex over (Z)} k,ŝ )w k,ŝ   acc          

     In step  205  the scheduler determines flow for each user from access hop allocations in different subsets; update user flow and fractional allocation on relay hop. Based on access hop integral flow, update relay hop user allocation per 
                 X   k   *     =       min   ⁢     {         ∑     s   :       R   ⁡     (   k   )       ∈   s         ⁢       w     k   ,   s     acc     ⁢     Y     k   ,   s           ,     F   k   *       }         w   k   rel         ,         
Δk; Update {circumflex over (X)} k =┌X k *┐.
 
     In step  206  the scheduler converts fractional allocations to integral ones similar to user integral allocation given a subset allocation on access hop. Obtain integral allocation by removing Σ k {circumflex over (X)} k −γN tiles the smallest flow value from {{circumflex over (X)} k }. 
     Turning now to  FIG. 3 , diagram for the greedy scheduler for adaptive resource usage GSAR ( 300 ), steps  301 ,  302 ,  307  follow a bisection approach to guide the adaptation of frame segmentation. It determines the bottleneck hop for a given γ and the resulting flow from current and previous schedules to guide the adaptation towards convergence. Sub-steps of  301  include: 
     
       
         
               
               
               
             
           
               
                   
               
             
             
               
                   
                 while cur_flow ≧ α · prev_flow do 
                   
               
               
                   
               
               
                   
                  
         γ   =       t   l     +     ⌊       (       t   u     -     t   l       )     2     ⌋         ,     prev_flow   =   cur_flow         
 
                   
               
               
                   
               
               
                   
                 Initialize available tiles for allocation on relay and access hops. 
                   
               
               
                   
                  C r  = γN, C a  = (T − γ)N 
                   
               
               
                   
                 Obtain the schedule and resulting flow for fixed γ 
                   
               
               
                   
                  if C r  = 0 then bot = 0 else bot = 1 
                   
               
               
                   
                  if bot = 0 then t l  = γ else t u  = γ 
                   
               
               
                   
                 end while 
               
               
                   
               
             
          
         
       
     
     In step  303  the GSAR considers only subsets of relays and for every relay subset, it determines a corresponding subset of users as follows. 
     
       
         
           
             ℛ 
             = 
             
               { 
               
                 Subset 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 of 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 relays 
               
               } 
             
           
         
       
       
         
           
             
               Map 
               ⁢ 
               
                   
               
               ⁢ 
               
                 ℛ 
                 ⟶ 
                 
                   ℛ 
                   m 
                 
               
               ⁢ 
               
                 : 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 ∀ 
                 s 
               
             
             = 
             
               
                 
                   { 
                   
                     
                       r 
                       1 
                     
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       r 
                       p 
                     
                   
                   } 
                 
                 ∈ 
                 
                   ℛ 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   define 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     m 
                     s 
                   
                 
               
               = 
               
                 
 
               
               ⁢ 
               
                 
                   
                     { 
                     
                       
                         k 
                         1 
                       
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         k 
                         p 
                       
                     
                     } 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   where 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     k 
                     i 
                   
                 
                 = 
                 
                   
                     argmax 
                     
                       
                         k 
                         : 
                         
                           R 
                           ⁡ 
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                       = 
                       
                         r 
                         i 
                       
                     
                   
                   ⁢ 
                   
                     { 
                     
                       
                         
                           w 
                           k 
                           rel 
                         
                         ⁢ 
                         
                           w 
                           
                             k 
                             , 
                             s 
                           
                           acc 
                         
                       
                       
                         
                           w 
                           k 
                           rel 
                         
                         + 
                         
                           w 
                           
                             k 
                             , 
                             s 
                           
                           acc 
                         
                       
                     
                     } 
                   
                 
               
             
           
         
       
     
     Then it selects the subset (of users) on access hop delivering maximum flow per unit tile based on remaining unallocated tiles in each hop. 
     
       
         
               
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                   
                 Determine access flow from c α  (min{a, C a }) tiles for 
                   
               
               
                   
                   
                 subset s: f s   acc  = Σ kεm     s    f k,s   acc  = Σ kεm     s    c a w k,s   acc   
                   
               
               
                   
                   
                 Obtain tiles on relay hop to support f s   acc  flow: c s,r  = 
                   
               
               
                   
                   
               
               
                   
                   
                 
                   
                     
                       
                         
                           Σ 
                           
                             k 
                             ∈ 
                             
                               m 
                               s 
                             
                           
                         
                         ⁢ 
                         
                           ⌈ 
                           
                             
                               
                                 c 
                                 a 
                               
                               · 
                               
                                 
                                   w 
                                   
                                     k 
                                     , 
                                     s 
                                   
                                   acc 
                                 
                                 
                                   w 
                                   k 
                                   rel 
                                 
                               
                             
                             - 
                             
                               E 
                               k 
                             
                           
                           ⌉ 
                         
                       
                     
                   
                 
                   
               
               
                   
                   
               
               
                   
                   
                 if c s,r  ≦ C r  then 
                   
               
               
                   
                   
               
               
                   
                   
                  
         f   s   rel     =         Σ     k   ∈     m   s         ⁢           ⁢     f     k   ,   s     rel       =       Σ     k   ∈     m   s         ⁢     ⌈         c   a     ·       w     k   ,   s     acc       w   k   rel         -     E   k       ⌉     ⁢     w   k   rel             
 
                   
               
               
                   
                   
               
               
                   
                   
                 else 
                   
               
               
                   
                   
                  Re-calculate user flow (f k,s   rel  ≦ f k,s   acc ) to maximize relay 
                   
               
               
                   
                   
                  flow (f s   rel ) for given c s,r  = C r  tiles 
                   
               
               
                   
                   
                 end if 
                   
               
               
                   
                   
               
               
                   
                   
                 
                   
                     
                       
                         
                           Determine 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             s 
                             ^ 
                           
                         
                         = 
                         
                           arg 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               max 
                               s 
                             
                             ⁢ 
                             
                               
                                 { 
                                 
                                   
                                     
                                       Σ 
                                       
                                         k 
                                         ∈ 
                                         
                                           m 
                                           s 
                                         
                                       
                                     
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     min 
                                     ⁢ 
                                     
                                       { 
                                       
                                         
                                           f 
                                           
                                             k 
                                             , 
                                             s 
                                           
                                           rel 
                                         
                                         , 
                                         
                                           f 
                                           
                                             k 
                                             , 
                                             s 
                                           
                                           acc 
                                         
                                       
                                       } 
                                     
                                   
                                   
                                     
                                       c 
                                       
                                         s 
                                         , 
                                         r 
                                       
                                     
                                     + 
                                     
                                       c 
                                       a 
                                     
                                   
                                 
                                 } 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                   
                   
               
             
          
         
       
     
     In step  304  the GSAR, for selected subset and its users, allocates Ca tiles on access hop and corresponding # tiles on relay hop to sustain the flow on access hop, taking into account excess resource from previous allocations 
     
       
         
           
             
               
                 Access 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 hop 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 allocations 
                 ⁢ 
                 
                   : 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   Y 
                   
                     k 
                     , 
                     
                       s 
                       ^ 
                     
                   
                 
               
               = 
               
                 
                   Y 
                   
                     k 
                     , 
                     
                       s 
                       ^ 
                     
                   
                 
                 + 
                 
                   c 
                   a 
                 
               
             
             , 
             
               ∀ 
               
                 k 
                 ∈ 
                 
                   m 
                   
                     s 
                     ^ 
                   
                 
               
             
           
         
       
       
         
           
             
               Relay 
               ⁢ 
               
                   
               
               ⁢ 
               hop 
               ⁢ 
               
                   
               
               ⁢ 
               allocations 
               ⁢ 
               
                 : 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 X 
                 k 
               
             
             = 
             
               
                 X 
                 k 
               
               + 
               
                 
                   ⌈ 
                   
                     
                       
                         f 
                         
                           k 
                           , 
                           
                             s 
                             ^ 
                           
                         
                         rel 
                       
                       
                         w 
                         k 
                         rel 
                       
                     
                     - 
                     
                       E 
                       k 
                     
                   
                   ⌉ 
                 
                 · 
                 
                   ∀ 
                   
                     k 
                     ∈ 
                     
                       m 
                       
                         s 
                         ^ 
                       
                     
                   
                 
               
             
           
         
       
     
     In step  305 , after allocation, the scheduler updates excess resource for users that receive more allocation than required to support the access hop flow 
     
       
         
           
             
               Update 
               ⁢ 
               
                   
               
               ⁢ 
               
                 E 
                 k 
               
             
             = 
             
               
                 ⌈ 
                 
                   
                     
                       f 
                       
                         k 
                         , 
                         
                           s 
                           ^ 
                         
                       
                       rel 
                     
                     
                       w 
                       k 
                       rel 
                     
                   
                   - 
                   
                     E 
                     k 
                   
                 
                 ⌉ 
               
               - 
               
                 ( 
                 
                   
                     
                       f 
                       
                         k 
                         , 
                         
                           s 
                           ^ 
                         
                       
                       rel 
                     
                     
                       w 
                       k 
                       rel 
                     
                   
                   - 
                   
                     E 
                     k 
                   
                 
                 ) 
               
             
           
         
       
     
     In step  306 , the GSAR Update tiles remaining for allocation on both the hops. Repeat steps  303 - 306  until no tiles remain for allocation on either of the hops.
 
 C   a   =C   a   −c   a   ; C   r   =C   r   −c   ŝ,r  
 
     From the foregoing it can be seen that the present invention provides a number of benefits: a near-optimal solution for adaptive frame segmentation and access hop reuse; an alternate solution that significantly reduces running time complexity compared to the previous solution, while also providing a good performance in practice; a greedy solution with fast running times and good average case performance; and applies to the case where users have both backlogged and finite buffers and also for the uplink. 
     The foregoing is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the patent laws. It is to be understood that the embodiments shown and described herein are only illustrative of the principles of the present invention and that those skilled in the art may implement various modifications without departing from the scope and spirit of the invention. Those skilled in the art could implement various other feature combinations without departing from the scope and spirit of the invention.

Technology Classification (CPC): 7