High performance and low complexity scheduling method for adaptive resource usage in OFDMA wireless relay networks

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.

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.

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.

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;

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 .

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:

The scheduler 106 converts fractional allocations to integral ones by assigning a tile to a user with probability equal to the user'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.

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'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

In step 303 the GSAR considers only subsets of relays and for every relay subset, it determines a corresponding subset of users as follows.

Then it selects the subset (of users) on access hop delivering maximum flow per unit tile based on remaining unallocated tiles in each hop.

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

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

In step 305 , after allocation, the scheduler updates excess resource for users that receive more allocation than required to support the access hop flow

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.