METHOD, OF DYNAMIC RESOURCE ALLOCATIONS IN WmELESS SYSTEMS

Field of the Invention The present invention generally relates to a method of dynamic resource allocations in wireless systems.

Background of the Invention

In wireless communications, users situated relatively far from a base station that serves them are generally more susceptible to interference from neighboring base stations and to signal attenuation. As a consequence, such users may experience relatively low signal-to-interference-and-noise ratios (SINRs). The relatively distant users are referred to as "cell edge users" or as users with "poor geometry." It will be understood that when one user is said to be more "distant" from the base station than another, what is meant does not depend solely on geographical distance, but also to susceptibility to other factors leading to attenuation and interference.

Several techniques with different degrees of complexity can be considered for out-of-cell interference mitigation in orthogonal frequency division multiple access (OFDMA) systems. Most of these schemes involve transmitting in any given cell over a portion of the spectrum that is smaller than the entire available bandwidth while neighboring cells employ a different portion of the spectrum. The primary goal of many of these techniques is to enhance the cell edge users' spectral efficiency and throughput at the expense of average sector throughput, or in some cases, with improved sector throughput as well. The interference mitigation schemes differ primarily in how the bandwidth occupied and transmitted power in a given sector are determined, and whether it is adapted as a function of the users being served, and whether it is coordinated across different cells.

For example, some schemes involve coordinated scheduling across multiple cells, in which bandwidth allocations are jointly determined across the cells on a per scheduling interval basis. Such schemes typically involve significant signaling between base stations, thus making them difficult to implement. Other schemes are based on static frequency partitioning or distributed coordination that do not involve signaling between base stations.

In an OFDMA system the transmission band is divided into a number of sub- carriers and information is transmitted by modulating each of the sub-carriers. Furthermore, time is divided into slots consisting of a number of OFDM symbols and transmissions are scheduled to users by assigning frequency resources (e.g., a set of logical sub-carriers) on specific slots. The logical sub-carriers are mapped to physical sub-carriers for transmission. The mapping can change from time to time and is referred to as frequency hopping. Frequency hopping is done to achieve interference averaging.

In OFDMA systems that support fractional frequency reuse (FFR) for interference mitigation, frequency and time resources (within an interlace period or frame that repeats periodically) are divided into several resource sets. Frequency hopping of sub-carriers is restricted to be within the sub-carriers of a resource set so that users scheduled on a certain resource set experience interference only from users scheduled in neighboring sectors in the same resource set. Each resource set is typically reserved for a certain reuse factor and is associated with a particular transmission power profile. For example, resource set 1 may be reserved for good geometry users in all sectors and resource set 2, 3, 4 for bad geometry users in sectors 1, 2, 3, respectively, in each cell resulting in 1/3 reuse for bad geometry users and universal reuse for good geometry users. Thus, fractional frequency reuse is achieved.

Fixed fractional frequency reuse does not adapt to traffic dynamics in the sense that the frequency reuse achieved is not adjusted based on interference conditions experienced by the users. Instead of a fixed partition of the available bandwidth leading fixed frequency reuse, it is possible to achieve dynamic frequency reuse through prioritized use of sub-carriers in the adjacent sectors. Interference avoidance is achieved by assigning different priority orders in the neighboring sectors so that when transmitting to cell edge users using sub-channelization, the neighboring interfering sectors transmit on different sub-carriers. Such a scheme was described in Das et al., "Interference mitigation through intelligent scheduling", Proc. Asilomar Conference on Signals and Systems, Asilomar, CA, November 2006 . For such an approach it is necessary to do frequency planning to determine the priorities and also dynamically adjust the thresholds under which users are assigned to different resource sets.

It is known that reuse patterns, such as the 1:3 reuse pattern of FIG. 1, are useful for reducing interference between neighboring sectors. As seen in FIG. 1, each cell (e.g., shown as hexagonal units 102, 104, 106) of a network is divided, according to a 1 :3 reuse pattern, into respective α, β, and γ sectors. The three classes of sectors are geographically distributed in such a way that, ideally, two sectors of the same class (e.g., characterized by the same subcarrier frequency) do not share a common edge. As a consequence, interference can be reduced by assigning mutually disjoint sets of subcarriers to the respective sector classes. In such a situation, the three sector classes may be said to be "mutually orthogonal" with respect to their use of subcarriers. In the figure, the respective sets of sub-bands, each of which contains sets of subcarriers, are denoted as fi, f ₂ , and f ₃ .

Summary of Invention

One embodiment of the present invention provides a method of dynamic allocation of resources in a wireless network with a number of base stations each associated with a number of reception areas, the method includes: each base station adaptively allocating resources to one or more users in each associated reception area based at least in part on one local optimization objective for each associated reception area and a channel quality indicator from the one or more users, the allocation of resources being done independently of other base stations, and interference is minimized between neighboring reception area through automatic resource reuse across the number of reception areas without resource planning prior to allocating the resources by each base station.

Another embodiment provides a method of dynamic allocation of resources in a wireless network with a number of base stations each having respective associated reception areas, the method includes: a base station adaptively allocating resources to one or more users in at least one associated reception area based at least in part on one local optimization objective and a channel quality indicator from the one or more users, the allocation of resources being done independently of other base stations, in which interference is minimized between neighboring reception areas through automatic resource reuse in the at least one associated reception area without resource planning prior to allocating the resources by the base station.

Brief Description of the Figures

The teachings of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which: Figure 1 is a schematic illustration of a fractional frequency reuse pattern;

Figure 2 is a schematic illustration of a method for allocating resources for constant bit rate traffic flow;

Figure 3 is a flow chart illustrating one embodiment of an algorithm for use with constant bit rate traffic; Figures 4A-B are results for a three-sector simulation using the algorithm for constant bit rate traffic;

Figure 5 is flow chart illustrating one embodiment of an algorithm for power allocations to sub-bands in best effort traffic flows; and

Figure 6 is a flow chart illustrating one embodiment of another algorithm for use in conjunction with the algorithm of Figure 5 for scheduling best effort traffic.

To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures.

Detailed Description The present invention provides a method for dynamic resource allocation to implement resource reuse, including fractional frequency reuse (FFR) and timeslot reuse, in wireless systems for maximizing system capacity and/or coverage. Specifically, each base station servicing its associated cell or sectors makes allocation decisions independently, i.e., without coordination with other base stations, or direct information of how band assignments are done in other base stations. The algorithm used for resource allocation is adaptive, e.g., resource allocation is done based in part on feedback received from mobile units or users, allowing for dynamic resource reuse such as frequency and timeslot reuse. Although frequency reuse may be used as examples in the following discussions, it is understood that the embodiments of the invention also apply generally to resource reuse.

Those skilled in the art will understand that a base station may serve a cell of a wireless network as a single, integral geographical unit, or the cell may be subdivided into sectors which are served independently of one another. The term "reception

area" will be used to denote the smallest independent geographical unit served by a base station. Thus, depending on the specific circumstances, a reception area may be a cell, or it may be a sector or other geographical unit. In the following discussion, cells will be referred to in some places, and sectors in others. Such terminology should not be understood as limiting, because the principles to be described below may be applied irrespective of whether the pertinent reception area is a cell, a sector, or some other geographical unit.

Those skilled in the art will understand further that various formats for wireless communication include a relatively long time window which is subdivided into shorter time windows during each of which, for example, one user is served. Without limitation, the term "frame" will be adopted herein to denominate such a longer time window, and the term "slot" or "timeslot" to denominate the shorter time window. In particular, as used herein, the term "timeslot" encompasses "subframes" as a specific example. It is further understood that resource planning, as used herein, includes frequency and timeslot planning performed offline (i.e., not real-time), and that "planning" also includes offline assignment of priorities for using different resources in different sectors, cells or reception areas in general. Although discussions of various examples may refer to frequency reuse or planning, it is understood that the methods and algorithms of the present invention also apply generally to resource allocations and reuse.

According to embodiments of the invention, each base station of a cell (sector or reception area) allocates its mobile units or users to the frequency bands based, at least in part, on a local optimization objective and a channel quality indicator, e.g., the level of interference the mobile unit receives in each of the bands. Examples of an optimization objective may include a minimization of the total power usage, minimization of the total weighted power usage (where power in one band may weigh more than in the other), a linear combination of power and frequency bandwidth, and so on. Although examples below may be discussed with respect to resource allocations at the sector level, e.g., taking into account only local optimization objectives and constraints within each sector, embodiments of the invention can also be extended and applied to resource allocations at the cell level, e.g., by taking into

account transmissions in other sectors of a cell being serviced by a specific base station.

The band allocation algorithm (or more generally, resource allocation algorithm), of a given base station is oblivious to, or independent of, how allocation is done by other base stations. Unlike conventional band assignment approaches, no explicit resource planning, e.g., frequency and/or timeslot planning, e.g., a priori band assignment performed offline or separately from the algorithm is needed.

However, the cells' optimization objectives and/or their parameters such as weighting factors can be set up in such a way that the resulting system-wide allocation of mobile units to the bands follows a very efficient FFR for improved performance, without the use of frequency planning. In other words, an efficient FFR happens "automatically", as a result of the implementation of the method of the present invention, without frequency assignments being done in advance. Furthermore, the FFR "induced" by the algorithm adapts, also "automatically", to the changing cell layout and/or mobile unit distribution and service requirements. Thus, interference between neighboring reception areas are minimized through automatic resource reuse across a number of reception areas.

Illustrative embodiments are discussed in the context of sub-carrier and power allocation in downlink of cellular systems based on orthogonal frequency division mulitple access (OFDMA) that achieve out-of-cell or out-of-sector interference avoidance through dynamic fractional frequency reuse, and algorithms are provided for both constant bit rate traffic such as Voice over Internet Protocol (VoIP) and variable bit rate best effort traffic such as web browsing. The algorithms are adaptive and adjust the resource allocation to time varying channel conditions and traffic patterns to maximize performance. Unlike conventional approaches, these algorithms do not require any a priori frequency planning for achieving fractional reuse, although frequency planning may be used to enhance performance.

Although embodiments of the present invention are discussed for OFDMA systems, they are generally applicable to multichannel code division multiple access (CDMA) systems and other multichannel wireless systems.

In one embodiment, a "shadow scheduling" algorithm is used by a base station to optimize a local objective in real time, in a computationally efficient manner. The shadow scheduling algorithm has been mathematically proven to indeed optimize the local objective.

For illustrative purpose, an OFDMA system with J sub-bands is used in this example. (Sub-bands are logical. Physically, a sub-band is an arbitrary fixed subset of sub-carriers, possibly from across the entire band.) For simplicity, a resource set is considered to consist only of frequency domain sub-bands defined in all timeslots. However, the algorithms described below can readily be extended to more general resource sets. Furthermore, in this example, all sub-bands are assumed to have the same number of sub-carriers, referred to as capacity c. In general, however, the sub- bands may have different number of sub-carriers.

Embodiments of the present invention provide algorithms suitable for use with both constant bit rate (CBR) traffic and best effort (BE) traffic, as discussed below.

As used herein, a constant bit rate (CBR) type traffic flow refers to a data flow in which, in general, a certain amount of data needs to be delivered to a mobile user at regular, typically fixed length, time intervals, and typically with the specified, low delay requirement. It is also possible to allow for some variations in the amount of data within each interval and/or variations in the interval duration. A voice-over-IP (VoIP) is a standard example of a CBR data flow.

A best effort (BE) type traffic flow refers to a data flow in which, in general, the system has freedom to choose the amount of data delivered to the user, typically with non-strict, or even non-existent, delay requirements. The system objective with respect to BE users is to allocate resources to them in a fair fashion. A typical example of a BE flow is a large file download. Some BE flows, however, may have explicit or implicit average rate requirements, over relatively large time intervals (of the order of 1 second or more). A typical example is an audio/video stream.

Algorithm for CBR Traffic

In the algorithm for use with CBR traffic, for each sub-band j, there is a parameter a _t > 0, which is the "unit cost of power" for the power used on this sub- band. The default values may be aj = 1. (For the purposes of "inducing" fractional frequency reuse (FFR), power usage on some carriers may be made more expensive, e.g., by setting a _j > 1.)

Let I denote the number of CBR-type traffic flows, which may, for example, be VoIP. The set of these flows is in fact not constant, and instead, varies with time. But the set changes relatively slowly. Assume also that each activity period ("talk

spurt") is a separate flow. Let m, _j denote the number of sub-carriers that flow i needs to be allocated if it is assigned to sub-band j. Also, let p _g denote a "medium-term" (e.g., over the order of 1 second intervals) average transmit power that will need to be allocated to flow i, if flow i is assigned to sub-band j. Both m _y and p _υ are estimated based on feedback received from users within a sector — or more generally, a reception area, at certain predetermined intervals, e.g., one skilled in the art will know how m, _j and p, _j can be computed from one or more channel quality indicators (CQI), such as signal-to-interference-and-noise (SINR) ratio that captures the effect of interference, from users' feedback. Since both m, _j and p, _j are determined by a medium-term (e.g., about 1 second intervals) average channel quality received for each resource set, they change relatively slowly and there is no need for frequent channel quality information feedback. In addition, m _g and p _y are typically highly correlated, since they both depend on the channel quality (although this feature is not required for the algorithm described below). For the purpose of this discussion, CBR-type flows, with tight delay requirements, are given absolute priority over other traffic types. Their assignment to the sub-bands has an objective of minimizing the total cost of power. (If all a, = 1, the objective is to minimize total power usage. In this case, if m _y and p _y indeed have strongly positive correlation, the total sub-carrier usage is also reduced as well.) The constraints are the sub-band capacities c and the total available power p* on all sub- bands. Formally, if A(J) is the set of flows assigned to sub-band j, the desired assignment A=(A(J)) seeks to minimize the term shown in Eq. (1) below, subject to the two constraints shown in Eq. (2) and (3): subject to the following conditions:

Eq. (2) ∑ ∑ ^P 'J ^{≤ P} " ^»

Eq- O) ∑ % ^≤ N _j ι ^eA(j)

The optimization problem can be understood as trying to minimize power and subcarrier usage, and leave as much resource as possible to other traffic types. An additional, implicit objective is to "shift" power used by the sector to its "cheaper" sub-bands, and thus minimize the interference this sector creates on its more

"expensive" sub-bands. Thus, the sub-band(s) that are typically assigned to bad geometry users in the sector are provided at a lower cost, while sub-bands that will typically be used by bad geometry users in interfering neighboring sectors are provided at a higher cost. This can be thought of as trying to create a soft frequency reuse pattern, which induces a good system-wide FFR.

Note that while the optimization objective Eq. (1) is a reasonable one, it is certainly not the only reasonable, "individual" sector objective to induce an efficient system-wide FFR. For example, one may try to explicitly include sub-carrier usage into the objective. It is contemplated that other objectives may also be acceptable. In addition, in assigning users to sub-bands, the algorithm may also incorporate one or more of the following features, e.g., avoiding frequent reassignment of CBR-type flows (to reduce the downlink signaling overhead), or providing a simple way to adapt automatically to an "evolving" set of users and their "evolving" service requirements my and py. Figure 2 illustrates schematically a method of assigning sub-bands to users or

CBR traffic flows. It is understood that assigning a "sub-band" to a user or flow means that a set of sub-carriers in that sub-band is assigned to that user or flow, but not the entire sub-band itself. The method 200 begins in step 202 by assigning a sub- band, j, to each user or traffic flow i, while initializing two parameters used for keeping track of two constraints: a power constraint and the number of subcarriers required for flow i, if flow i is assigned to carrier j. In step 204, in each time interval selected for band assignment update (e.g., may be a time slot), for a given flow i, identify a sub-band j* that will satisfy a local optimization objective. In this example, the objective is one of minimizing a term that is indicative of power and subcarrier usage for flow i.

After j has been identified, a determination is made as to whether the minimized power and subcarrier usage provides a significant gain compared to the power and subcarrier usage under the initial sub-band assignment, as shown in step 206. If the gain satisfies a predetermined criterion, e.g., if the power and subcarrier usage savings exceeds a predetermined threshold, then sub-band j* can be assigned to flow i. Otherwise, flow i retains its initial sub-band j. This sub-band assignment based on the local optimization objective is done for all users or traffic flows at each suitable time interval.

If the integrality constraints in Eq. (1) - Eq. (3) are relaxed, which is reasonable if one assumes that m. _j is typically much smaller than c, then Eq. (1) - Eq. (3) is a linear program and the following simple "shadow scheduling" algorithm provably solves it, as shown by Stolyar, "Maximizing Queuing Network Utility subject to Staility: Greedy Primal-Dual Algorithm" in Queueing Systems, vol. 50, pp. 401-457 (2005).

Figure 3 shows a flow chart of an algorithm for implementing the method 200. In the shadow algorithm 300, initialization of two parameters Z, Q ₁ and initial assignment of sub-bands are performed in block 302. Z represents a virtual ("ficticious") queue that keeps track of the total power constraint of Eq. (2), while Q, represents a virtual queue for each sub-band j to keep track of the constraint Eq. (3). A small parameter, βi>0 is also provided for controlling a tradeoff between responsiveness of the algorithm and its accuracy. In one embodiment, βi is equal to 0.01. For example, the initial state can be: βiQ, = 1 for all j and Z=O. Although a good choice of initial state is important, it is not crucial.

In block 304, the time slot for sub-band allocation is advanced to the next slot, and a first user (or traffic flow) is selected by setting the user index i to 1 , as shown in block 306. In block 308, a comparison is made as to whether the flow index i is less than or equal to the total number of flows I. If the answer is "yes", then the method proceeds to block 310, which identifies a sub-band j , belonging to a resource set B(i) assigned to user i, that would minimize a term W _υ . Wy is indicative of a power and subcarrier usage, and in this example, is given by: Eq. (4) W, _j = a _jPlJ + β.Qm. _j + β,Z _PlJ In Eq. (4), the first term a _j Py represents a cost of power, the second term is indicative of the sub-band capacity constraint, and the third term is indicative of the total power constraint. In another embodiment, in particular in the case when all parameters a _} are equal, the third term is omitted from W _y , so that the minimization in block 310 is done only for the sum of the first two terms. In one embodiment, a, is equal to 1 for all j, and βi is equal to 0.01.

In block 312, parameters Q* and Z are updated according to: Q y= Q _j ⁺ m,, and Z = Z + p _ψ This can be interpreted as "routing" one unit of flow i traffic to queue j, and consuming amount p _υ of power.

In decision block 314, a query is performed to evaluate the gain resulting from the sub-band j* assignment. Specifically, the term, W _y * for the j* sub-band, is compared with Wy for the initial sub-band j according to the equation: W _1J * < (1- δ) W, _j (i) shown in block 314, with a predetermined parameter δ being used in this comparison step. If the answer is "yes", e.g., the gain is considered sufficient to justify a sub-carrier re-assignment, then flow i is re-assigned to sub-band j*, as shown in block 316. Otherwise, flow i retains its existing sub-band j.

By providing a "gain threshold" as a criterion, one can avoid frequent re- assignments of sub-bands. That is, flow i is re-assigned from its current sub-band j$B(i) to another sub-band k£B(i) only if the gain satisfies the criterion determined by:

Z _k Pa ⁺ β,Z p _lk < (1-δ) (a ₇ p _y + βiQ _/ m,, + βiZ p _tJ ) The assessment as to whether to re-assign a sub-band can be done by obtaining a difference or a ratio between the term Wy _* (with a re-assigned sub-band j*) versus the term W, _j (with the current sub-band j), and comparing the difference or ratio to a predetermined threshold value.

In block 318, the flow index i is increased by one for the next user or flow. The process is repeated starting from blocks 308 for all traffic flows i.

After all flows i have been processed for sub-band assignment, as determined by a "no" answer in block 308, parameters Q ₁ and Z are set to appropriate values as shown in blocks 320 and 322, respectively. In block 320, for each j, Q is updated by: Q, = max{Q, - c, 0}, i.e., Q, is set to the larger of either Q, - c, or 0. In block 322, Z is updated by Z = {Z - p, 0}. The entire process then repeats for the subsequent time slot, as shown in block 304. The above algorithm provides a simple and robust way of performing sub- band assignments. For example, if the initial estimates of m _y and p, _j are reasonable, then even the initial assignment of a flow i would be reasonable. If, however, the "new" flow is in fact a new talk spurt of an existing "session", the last estimated values of m _y and p _l} can be used as new estimates. Even if a bad initial assignment has been made, it can be improved by subsequent reassignments as estimates of m, _j and p, _j get better. Moreover, even though the algorithm solves the problem Eq. (I)- Eq. (3) assuming set of flows and all m, _j and p _υ are constant, it is robust with respect to m, _j and p _y changing with time, if such changes are relatively slow. Thus, the

algorithm "tracks" the optimal solution of Eq. (I)-Eq. (3) as m^ and py change, by doing simple updates of variables in each step.

In this example, the optimization objective and constraints are considered for resource allocations at the sector level. However, in general, the m^ and pij can also be estimated at the cell level by taking into account transmissions in other sectors of a cell.

Furthermore, the algorithm induces "good" FFR, namely, low-geometry flows in neighboring interfering sectors will avoid interference from each other by moving to different sub-bands. High geometry users in neighboring sectors will be able to share same sub-bands. This happens automatically through implementation of the algorithm, i.e., without any frequency planning, and results in aggregate system capacity improvement.

FIGS. 4A-B illustrate results for a simulation involving three sectors and three sub-bands using the algorithm of FIG. 3. FIG. 4 A shows a plot of the average transmit power versus the sub-band index Q= 1, 2 and 3) for each of the three sectors, indicating clearly the resulting FFR pattern, which is automatically induced by the resource allocation method of the present invention. FIG. 4B shows a plot of the number of sub-carriers assigned versus the sub-band index Q=I, 2 and 3) for each of the three sectors, also indicating that an efficient FFR pattern is automatically induced.

Algorithm for Best Effort Traffic Flows

For Best Effort traffic type, a different method is used. One embodiment involves a two-part process, which can be implemented using two algorithms run by each sector (or more generally, run by each reception area). The first algorithm is referred to as a shadow algorithm, which determines a good power allocation and constantly updates the power allocation p _j (where j=l,..., J) to each of the sub-bands j, subject to the total power constraint X _j P _j ≤ P ^* - Th ^e second algorithm is referred to as the actual scheduling algorithm, which assigns each sub-band according to the power allocation provided by the shadow algorithm, and determines which user is scheduled in each sub-band in each time-slot.

Although the example below illustrates resource allocations based on local optimization at the sector level, it can also be extended to resource allocations and optimization at the cell level.

Figure 5 shows a flow chart for one example of the shadow algorithm 500. The shadow algorithm performs "virtual scheduling" of users within a reception area, e.g., a sector, for transmission so as to solve the problem of: max ∑j Uj(Xj ^(v) ), i.e., maximizing the utility for all users, where Ui(Xi ^(v) ) determines a "utility" of user i as a function of the average transmission data rate Xi ^(v) that is provided by the shadow algorithm to this user, subject to the constraint that the average total power used is at most p ^* . (The superscript ^(v) is used to denote a virtual quantity assigned by the shadow algorithm.) Ui is generally a concave, non-decreasing function of Xj _.

A fixed parameter p ^** > p ^* /J is provided, such that in any time slot and in any sub-band j, the allocated power can be either p ^** or 0. The assumption of the shadow algorithm is that at most one user can be scheduled in a given sub-band in any time slot.

The algorithm maintains a virtual ("ficticious") queue Z to keep track of the total power constraint, and also maintains and updates current values of a user's transmission data rate X/ ^v ^ and current average power usage p/ ^v ^ in each sub-band.

In block 502, parameters Z and Xj ^(v) are initialized, and an initial power allocation is made to each sub-band j according to p/ ^v) = p ₀ , where p _o is an initial power value. For example, the initial state may be Z = 0 and Xj ^(v) =xo for all i, where xo>O and is a fixed constant. In one embodiment, xo is equal to 1.

In block 504, the time slot (or another selected time interval) for power allocation update is advanced to the next slot, and in block 506, a first sub-band j is selected by setting the index j to 1. In block 508, a comparison is made as to whether the sub-band index j is less than or equal to the total number of sub-bands J.

If the answer is "yes", then the method proceeds to block 510, which identifies a user i that will satisfy an optimization objective for sub-band j in the current time slot. In this example, the objective is one of maximizing a term, hy, which is equal to U'j(Xi ^(v) )rij(p") - β ₂ ^(v) Z p ^** , where U'; is a derivative of Ui, and ry(p ^** ) denotes an instantaneous transmission data rate within a timeslot that user i will get, if user i is scheduled for transmission in sub-band j with power p ^** , and with all sub-carriers (within this sub-band) allocated to the transmission. The instantaneous rate rj _j (p ^** ) is

estimated by the algorithm based on users' feedback, e.g., one or more CQIs received from users at certain predetermined time intervals. In another embodiment, the algorithm may be extended to the cell level by requiring that the ry terms take into account only out-of-cell (not out-of-sector) interferences and obtaining power allocation for each sector and then jointly assigning users within a cell for all sectors. U'j(Xi ^(v) ) represents the user's current marginal utility, i.e., the increase of user utility per unit increase of its average rate x/ ^v) . Then, the first term represents the increase in system utility if user i is to be served at the instantaneous data rate of η _j in the given timeslot. The product β ₂ ^(v) Z in the second term represents a current cost of power usage, and the second term β ₂ ^(v) Zp ^** represents the power cost to the system if power p ^** is allocated.

The small positive parameter, β ₂ ^(v) , controls the tradeoff between responsiveness of the algorithm and its accuracy. The value of β ₂ ^ is set in advance, and not adjustable within the algorithm. For example, in one embodiment, β ₂ ^(v) is equal to 0.01, and p ^** is set equal to 1.5p ^* .

In block 512, a determination is made as to whether hj _*j is less than zero or not. If the answer is "yes" (i.e., hj» _j is negative), then block 514 sets the values for Xi ^(v) and _P j ^(v) according to: Xj ^(v) = (l-β ₃ ^(v) ) Xj ^(v) for each user i, and p/ ^v) = (l-β ₃ ^(v) ) p/ ^v) . β ₃ ^(v) ) is another small positive parameter, controlling the tradeoff between responsiveness of the algorithm and its accuracy. In one embodiment, β ₃ ^(v) is equal to 0.001.

If the answer in block 512 is "no", the algorithm proceeds to block 516, in which the following power allocation p/ ^v) and transmission rate allocations are made.

Z = Z + p**,

Xi* ^(v) = β ₃ ^(v) ri*j(p") + (l-β ₃ ^(v) ) Xj* ^(v) for the chosen user i\ and Xi ^(v) = (l-p3 ^(v) ) Xi ^(v) for all other users.

That is, the average data rate for user i* is different from the data rates for other users. In block 518, Z is updated according to Z=max{Z-p7j, 0}, which means that

Z is decremented by p ^* /J, the maximum allowed average (across sub-bands) power usage per sub-band, but Z is not allowed to go below 0. In block 520, the sub-band index is increased by 1, and the algorithm repeats from block 508. The power

allocation, p/ ^v) , generated by this scheduling algorithm is provided for use in the second algorithm related to actual scheduling.

FIG. 6 shows a flow chart for one example of the actual scheduling algorithm 600. In block 602, the average transmission data rate X, is initialized for each user i. For example, the initial state may be: X ₁ = xo for all i, where xo is a fixed positive constant. In one embodiment, xo is equal to 1. In block 604, the time slot is advanced to the next slot. In block 606, the actual power is allocated to each sub-band j according to the values provided by the shadowing algorithm of FIG. 5. The actual algorithm schedules one or more users in a given sub-band in each slot. The goal of the algorithm is to maximize the utility for all users, i.e., solve the problem: max∑,U,(X,), where X ₁ is the average actual rate given to user i (by actual algorithm). For simplicity, FIG. 6 shows one embodiment of the actual algorithm that schedules at most only one user in a given sub-band in any slot. In general, however, one or more users may be assigned to each sub-band within each timeslot. The sub-band index j is set to 1 in block 608. In block 610, a comparison is made as to whether the sub-band index j is less than or equal to the total number of sub-bands J. If the answer is "no", the algorithm proceeds to block 604 for processing of the next time slot. If the answer is "yes", then the method proceeds to block 612, which identifies a user i that will satisfy a local optimization objective. In this example, the objective is one of maximizing the term Lf ₁ (X ₁ ) r _l} (p _} ), which represents the utility of user i in sub-band j, with an instantaneous data rate r _υ . If the first user does not have enough bits to be sent, a second user can be scheduled in the same sub-band.

In block 614, the transmission data rate for user i is set to X ₁ * = β ₄ r,«,(P _j ) + (1- β ₄ ) X ₁ * for the chosen user i , and Xi = (l-β ₄ ) Xi for all other users. In block 616, the sub-band index is increased by 1, and the algorithm proceeds to block 610 to see if all sub-bands j have been processed. β ₄ is another small positive parameter, controlling the tradeoff between responsiveness of the algorithm and its accuracy. In one embodiment, β ₄ is equal to 0.005. As illustrated herein, embodiments of the present invention provide a method of dynamic resource allocations that adapts to changes in system layout or user distribution such that fractional frequency reuse can be efficiently implemented to avoid or minimize interference between neighboring sectors. Unlike conventional

methods, the present method does not require any a priori resource planning such as frequency or timeslot planning. Instead, frequency band assignments are done dynamically and in real-time. Furthermore, each base station performs resource allocations independently of other base stations, e.g., does not require any direct signaling exchange with other base stations, and resource allocations are determined based at least in part on one local optimization objective (for the reception area, e.g., cell or sector, that it services) and a channel quality indicator or feedback from one or more users or mobile units. Based on the channel quality indicators received from one or more users in the reception area, estimates of relevant parameters can be arrived at for use in algorithms for resource allocations.

While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.