Systems, methods, and media for reducing femtocell interference

Systems, methods, and media for reducing femtocell interference are provided. In some embodiments, systems for reducing femtocell interference are provided, the systems comprising: at least one hardware processor that: estimates a total path loss between a macrocell user (MU) and a mobile base station (MBS); estimates a path loss from the MU user to a femtocell access point (FAP); determines whether the MU can meet a first target signal to interference plus noise ratio (SINR); determines whether a transmission from the MU will prevent a femtocell user (FU) of the FAP from achieving a second target SINR; and restricts the MU to using subcarriers not used by the FAP when it is determined that the MU cannot meet the first target SINR and/or it is determined that the transmission from the MU will prevent the FU from achieving the second target SINR.

TECHNICAL FIELD

Systems, methods, and media for reducing femtocell interference are provided.

BACKGROUND

In recent years, wireless operators have been experiencing a steadily increasing demand for higher data rates and better quality of service due to the constant growth in the number of active wireless terminals. One significant challenge is how to improve the indoor coverage. Studies show that over 50% of all voice calls and more than 70% of data traffic originate from indoors. Therefore, indoor coverage providing high data rate and quality-of-service (QoS) is a key issue in developing next-generation wireless systems. However, adding macrocell base station (MBS) to meet the growing indoor service demands is very expensive. Instead, femtocells using femtocell access points (FAPs) have been proposed as a new system architecture to tackle this problem.

An FAP is a simple, low-power and low-cost base station installed at a user's premise, e.g., house, office, warehouse, etc., that provides a femtocell for local access to the network by means of some cellular technology (e.g., 2G, 3G). Using femtocells benefits both users and operators. Due to the proximity between the transmitter and receiver, indoor users experience better signal quality and communicate with higher throughput. Moreover, indoor users transmit less power when being in the range of the FAP, resulting in prolonged battery life and reduced interference to the macrocell. When indoor users (e.g., the ones in their own apartments) are connected to an FAP, there are fewer indoor users transmitting in the macrocell and the overall capacity and QoS of the network improves. From the operator's point of view, femtocells can improve spectrum reuse and provide high network capacity and spectral efficiency. In addition, given that FAPs are typically paid for and maintained by the owners, the overall network cost is reduced.

On the other hand, despite these advantages, femtocells bring about multiple new challenges in terms of network architecture, interference management and synchronization. In particular, interference problems between macrocells and femtocells can become a major issue that requires new solutions due to the extra degrees of complexity in comparison with standard cellular networks.

Accordingly, new systems, methods, and media for reducing femtocell interference are provided.

SUMMARY

Systems, methods, and media for reducing femtocell interference are provided. In some embodiments, systems for reducing femtocell interference are provided, the systems comprising: at least one hardware processor that: estimates a total path loss between a macrocell user (MU) and a mobile base station (MBS); estimates a path loss from the MU user to a femtocell access point (FAP); determines whether the MU can meet a first target signal to interference plus noise ratio (SINR); determines whether a transmission from the MU will prevent a femtocell user (FU) of the FAP from achieving a second target SINR; and restricts the MU to using subcarriers not used by the FAP when it is determined that the MU cannot meet the first target SINR and/or it is determined that the transmission from the MU will prevent the FU from achieving the second target SINR.

In some embodiments, methods for reducing femtocell interference are provided, the methods comprising: estimating, using at least one hardware processor, a total path loss between a macrocell user (MU) and a mobile base station (MBS); estimating, using the at least one hardware processor, a path loss from the MU user to a femtocell access point (FAP); determining, using the at least one hardware processor, whether the MU can meet a first target signal to interference plus noise ratio (SINR); determining, using the at least one hardware processor, whether a transmission from the MU will prevent a femtocell user (FU) of the FAP from achieving a second target SINR; and restricting, using the at least one hardware processor, the MU to using subcarriers not used by the FAP when it is determined that the MU cannot meet the first target SINR and/or it is determined the transmission from the MU will prevent the FU from achieving the second target SINR.

In some embodiments, non-transitory computer-readable media containing computer-executable instructions that, when executed by a processor, cause the hardware processor to perform a method for reducing femtocell interference are provided, the method comprising: estimating a total path loss between a macrocell user (MU) and a mobile base station (MBS); estimating a path loss from the MU user to a femtocell access point (FAP); determining whether the MU can meet a first target signal to interference plus noise ratio (SINR); determining whether a transmission from the MU will prevent a femtocell user (FU) of the FAP from achieving a second target SINR; and restricting the MU to using subcarriers not used by the FAP when it is determined that the MU cannot meet the first target SINR and/or it is determined the transmission from the MU will prevent the FU from achieving the second target SINR.

DETAILED DESCRIPTION

With femtocells overlaying on top of a traditional cellular deployment, one can expect to encounter three types of uplink interference: macrocell user (MU) to femtocell access point (FAP) interference, femtocell user (FU) to macrocell base station (MBS) interference, and FU to FAP interference, as illustrated inFIGS. 1a,1b, and1c, respectively.

In OFDMA-based systems such as mobile WiMax, power control can be employed for the uplink. Power control can be used to ensure (when possible) that a given MU is transmitting enough power to achieve a minimum signal-to-interference-plus-noise-ratio (SINR) at the MBS receiver given the current channel condition, which can be measured by the system periodically. If an MU is located far away from the MBS, the power control algorithm can set its transmitted power to a high level to meet the target SINR value.

As depicted inFIG. 1a, however, if an MU102happens to be in the vicinity of a femtocell104using the same subcarrier and also far away from an MBS106, then its signal could be high enough to propagate through the walls of a building where an FAP108is deployed and generate interference. In fact, it is indeed on the macrocell edge where femtocells are most necessary and useful, so this kind of interference is expected to be very frequent.

Due to frequency reuse among femtocells, it is possible that a FU112in a femtocell114may use the same subcarrier as an MU116, and thus the FU may interfere with a macrocell118, as depicted inFIG. 1b. In order to overcome the interference from an FU112to an MBS120, the MBS can measure the interfered subcarrier and apply uplink power control on MU116, which will determine that it needs to transmit higher power in order to reach its target SINR at the receiver. This increase of the transmission power may worsen MU to FAP interference.

In accordance with some embodiments, to treat the uplink interference problem in orthogonal frequency-division multiple-access (OFDMA)-based femtocell networks with partial co-channel deployment, mechanisms for mitigating inter-tier interference are provided. In accordance with some embodiments, femto-interfering macrocell users can be required to use only some dedicated subcarriers, and non-interfering macrocell users can use either the dedicated subcarriers or shared subcarriers, which can also be used by femtocell users. Mechanisms for allocating subcarriers based on auction algorithms for macrocell users and femtocell users to independently mitigate intra-tier interferences are also provided in some embodiments.

An example of femtocells and macrocell coexistence in a two-tier network200is illustrated inFIG. 2. In such a network, femtocells202are in one tier and a macrocell204is in another tier. The femtocells overlay on top of the macrocell forming a hierarchical cell structure. At distances D1206and D2208from MBS210(which can be any suitable distances), two groups (or any other suitable number) of twenty five femtocells (or any other suitable number) can be arranged in square grids (e.g., in a residential neighborhood) of area D2=10000 m2(or any other suitable size), with five femtocells (or any other suitable number) per dimension. The radius of each femtocell can be RFC=10 m (or any other suitable size). The FAPs can be located in the center of their corresponding femtocells. The coverage radius of the macrocell can RMC=500 m (or any other suitable size).

Given a total number of available subcarriers N, Nssubcarriers can be shared by the FUs and the MUs, and the remaining (N−Ns) subcarriers can be used by MUs only. The transmitting power of a MU can be denoted as PMUand PminMU<=PMU<=PmaxMUby using power control according to the measurement of each subcarrier channel state. Owing to the small radius of the femtocell, and FU and MU being the same type of terminal, the transmission power of an FU, PFU, can be constant and PFU=PminMU.

In accordance with some embodiments, MU power control, and channel selection can be used to mitigate interference between MUs212and FAPs214and between FUs216and MBSs210. In order to do so, an MU can first use power control to improve its SINR in order to satisfy its QoS requirement. If the MU cannot reach its minimum SINR requirement (e.g., due to it being a long distance from its MBS and/or interference from one or more FUs), it can switch to a dedicated subcarrier. If the MU can meet its target SINR, then it can be checked whether or not the MU's transmission power is strong enough to interfere with its nearest co-channel FU. If the position of the MU is close enough to an FAP to interfere with the co-channel FU, the MU can use a dedicated subcarrier. Otherwise the MU can use a shared subcarrier.

More particularly, for example, such a process300can be performed as shown inFIG. 3. As illustrated, after process300begins at302, for a given MU m, an estimate of the total path loss to its MBS (χmMU) can be made at304. Next, at306, an estimate of the path loss to the MU's closest active FAP (χmMF) can be made by measuring the Reference Signal Received Power (RSRP) of the active FAPs in the downlink. Then, at308, it can be determined whether the MU can meet its target SINR by using power control. If so, then, at310, process300can determine whether the transmission power of this MU may cause its closest FUs' SINR to drop below the FUs' minimum requirements. If it is determined at310that the FUs in the closest femtocells can satisfy their SINR requirements, then, at312the MU can be designated as a regular user and as able to use either the shared subcarriers or the dedicated subcarriers. Otherwise, if it is determined at either at308or310that the MU or an FU, respectively, cannot meet its minimum SINR, the MU can be designated as a femto-interfering user and can be restricted to using only dedicated subcarriers at314. After designating an MU as a regular user or a femto-interfering user at312or314, respectively, process300can terminate at316.

As another example, to designate an MU as a “regular user” or a “femto-interfering user,” a scenario in which an FU is at the edge of the femtocell can be considered. In this scenario, one can assume that the estimated distance from the MU to the closest FAP is dMFbased on the RSRP measurement. Then, to prevent an MU from interfering with an FU in the closest femtocell, the SINRs of the MU and the FU can be required to satisfy the following constraints:

PFUis the output power of the FU;

GFis the gain of the FU;

PMUis the output power of the MU;

GMis the gain of the MU;

W accounts for the noise power;

χFUdenotes the path loss from the FU to its FAP;

χMUdenotes the path loss from the MU to its MBS;

γminFUis the minimum SINR requirement for the FU;

γminMUis the minimum SINR requirement for the MU;

IMFis the interference from the MU to the FAP;

IFFis the interference from FUs in other femtocells to a given FU; and

IFMis the interference from FUs to the MU.

IMF, the interference from the MU to the FAP, can be given by

IMF=PMU⁢GFχMF(3)
where PMUis the transmit power of the MU, GFis the antenna gain of the FAP, and χMFis the path loss from the MU to the FAP and is related to dMF.

IFF, the interference from FUs in other femtocells to a given FU, can be caused by FUs in adjacent femtocells as well as by FUs in non-adjacent femtocells in some embodiments. When intra-tier subcarrier allocation across adjacent femtocells is performed as described below, the impact of adjacent femtocells on IFFcan be ignored in some embodiments. In such embodiments, IFFcan be estimated based on the interference that would be caused by a scenario in which the FUs in the four closest, non-adjacent femtocells (e.g., femtocells220,222,224, and226ofFIG. 2) use the same subcarrier as the given FU (e.g., femtocell228ofFIG. 2). In such a scenario, interference from the interfering FUs can be given by:

IFF=4⁢PFU⁢GFAχFF(4)
where χFFaccounts for the path loss from one of the interfering FUs (e.g., in one of femtocells220,222,224, and226ofFIG. 2) to the FAP of the given FU (e.g., the FAP in femtocell228ofFIG. 2), which path loss χFFcan be calculated using the distance of 3RFC(as shown inFIG. 2).

IFM, the interference from FUs to the MU, can be given by

IFM=∑i∈Mint⁢⁢PFU⁢GFχiFM(5)
where Mintindicates the set of interfering FUs to the MU, and χiFMis the path loss from the ith FU in Mintto the MBS. The interference can be estimated by performing uplink measurements of RSRP by the MBS.

Taking equalities in (1) and (2), and using (3)-(5), χMUcan be solved for and the maximum path loss from MU to its MBS, χmaxMU, with the constraints of (1) and (2) obtained as follows:

All the parameters on the right-hand side of (6) are constants except for the two variables χMFand IFM. Thus, χmaxMUis primarily affected by the path loss from the MU to its closest FAP, χMF, and the interference from the FUs to the MBS, IFM. Due to frequency reuse among femtocells, the value of IFMis mainly related to the minimum distance from FUs to the MBS and the active probability of femtocells, which varies more slowly than χMF. Therefore, different MUs have different χmaxMUdue to their different locations. The MU with a larger distance from its closest FAP will have a larger χmaxMU.

Any suitable path loss model(s) can be used for making these determinations in some embodiments. For example, in some embodiments, a path loss model based on suburban deployment of FAPs located in single-floor houses/buildings can be used. In this model, the path loss between an FU and an FAP, where the FU is inside a different house that the FAP, can be calculated as:
χ=max(15.3+37.6 log10d,38.46+20 log10d)+0.7dindoor+nwLw+X.(7)
The pass loss between an FU and an FAP, where the FU is inside the same house as the FAP, can be calculated as:
χ=38.46+20 log10d+0.7dindoor+X.(8)
The pass loss between an MU and an FAP, where the MU is outside, and the path between an FU and an MBS, where the FU is inside a house, can be calculated as:
χ=max(15.3+37.6 log10d,38.46+20 log10d)+0.7dindoor+nwLw+X.(9)
The pass loss between an MU and an MBS, where the MU is outside, can be calculated as:
χ=15.3+37.6 log10d+X.(10)
In equations (7)-(10): d is the transmitter-receiver separation in meters; dindooris the indoor distance in meters; Lwis the penetration loss through external walls, generally assumed to be 15 dB; and nwis the number of penetrated walls. Using an intra-tier interference mitigation scheme among femtocells (as described below) we can assume that nw>=2 for the path loss χFF. In some embodiments, a general normal distribution with a standard deviation of 4 dB can be used for the shadow fading X(dB) for the pass loss between an FU and an FA, where the FU is inside the same house as the FAP, and a general normal distribution with a standard deviation of 8 dB can be used for the shadow fading X(dB) for other path losses.

Once χmaxMUhas been determined, an MU whose path loss to its MBS is less than its corresponding χmaxMUcan be classified as a regular user and enabled to use either a dedicated subcarrier or a shared subcarrier. An MU whose path loss to its MBS is greater than its corresponding χmaxMUcan be classified as a femto-interfering user and restricted to using only a dedicated subcarrier.

As described above, subcarriers can be allocated to MUs based on whether those MUs are determined to be regular users or femto-interfering users. Any suitable technique for allocating subcarriers can be used in some embodiments. For example, in some embodiments, subcarriers can be allocated based on the following:
max{amnMU}Σm=1Mωm(Σn=1NcmnMUamnMU),
s.t. amnMUε{0,1},
ΣmamnMU<=1,∀n,
ΣnamnMU=km,∀m,
amnMU=0,∀nεFs,∀mεUint(11)
where:M is the number of MUs;ωmis a priority or weighting factor for the mth MU;cmnMUdenotes the data rate for MU in on subcarrier n;amnMUis an indicator variable such that amnMU=1 if the nth subcarrier is allocated to the mth MU, otherwise amnMU=0;Fsis the set of shared subcarriers;Uintis the set of femto-interfering users;Each subcarrier is only assigned to one user; andThe mth MU requires to be allocated kmsubcarriers and Σmkm<=N.

If the nth subcarrier for MU m has SINR γmnMU, assuming a 3 dB gap to theoretical rate; then its rate can be estimated as

The second constraint in (11) indicates that any subcarrier can be allocated to at most one MU to avoid intra-cell interference. The third constraint in (11) defines the number of subcarriers allocated to an MU m is km. Finally, the last constraint in (11) prevents the femto-interfering MUs Uintfrom occupying the shared subcarriers.

Note that here the STNR values may incorporate the short-term channel fading effects and are assumed to be perfectly calculated by the MBS at the beginning of each iteration (i.e., at the beginning of each frame) by performing uplink measurements of RSRP of FUs (i.e., the interference from FUs) and subcarrier channel state.

In some embodiments, the optimization problem given by (11) can be translated into a special 0-1 combinatorial optimization problem by introducing a dummy user with index=m=0, such that c0,nMU=0, ∀n, and the number of its allocated subcarriers k0=N−Σm=1Mkm, with the understanding that any subcarrier assigned to the dummy user is not used for data transmission. The mth user can be divided into km“sub-users” and an indicator variable ãm,l,nMU, l=1, 2, . . . , kmcan be defined such that ãm,l,nMU=1 if the nth subcarrier is allocated to the lth sub-user of the mth user. In addition, let {tilde over (ω)}m,lωmand {tilde over (c)}m,l,nMUcmnMU, l=1, 2, . . . , km. Thus the original optimization problem (11) can be converted to the following:
max{ãm,l,nMU}Σm=0MΣlkm{tilde over (ω)}m,l(Σn=1N{tilde over (c)}m,l,nMUãm,l,nMU),
s.t. ΣmΣlãm,l,nMU=1,∀n
Σnãm,l,nMU=1,∀m,l,
ãm,l,nMU={0,1},
ãm,l,nMU=0,∀nεFs,∀mεUint,  (13)
which is a symmetric assignment problem. Such an assignment problem can be solved efficiently using an auction algorithm in some embodiments.

Assuming a set of prices {rm, n=1, . . . , N}, a total number of objects N, and a positive scalar ε, a player m can be defined as being happy with the object nmif the profit (i.e., reward minus price) of assigning object nmto player m is within ε from a maximum profit. For example, this relationship can be represented as:
fmnm−rnm>=maxn{fmn−rn}−ε,  (14)
where:

fmnmdenotes the reward of object nmto player m; and

rnmrepresents the current price of object nm.

If an object nmassigned to player m does not satisfy the inequality (14), player m is defined as being unhappy. For problem (13), the reward denotes the data throughput of each subcarrier for every sub-user and the price is an increasing variable during the auction process.

An example of an auction process for solving (13) that can be used in some embodiments is shown inFIGS. 4aand4b.

Turning toFIG. 4a, after process400has begun at402, the process can initialize ε, the happiness of sub-users, and subcarrier prices at404. For example, any suitable a can be selected, all sub-users (except for the dummy sub-users) can be set as being unhappy, and the price for every subcarrier rncan be set to zero.

Next, at406, process400can choose an unhappy femto-interfering sub-user from the set of femto-interfering sub-users Uint. The process can next calculate the chosen sub-user's maximum profit and other femto-interfering sub-users' maximum profit, and identify the best subcarrier (nm,l) with the maximum profit for the sub-user, at408. These maximum profits can be calculated in any suitable manner. For example, the chosen sub-user's maximum profit can be calculated as φm,l,nm,l=maxn(fm,l,n−rn). As another example, the other sub-users' maximum profit can be calculated as φm,l,nm,l=maxn,n≠nm,l(fm,l,n−rn). fm,l,ncan be calculated as being equal to {tilde over (c)}m,l,nMU, as described above. At410, the best subcarrier nm,lcan be allocated to the chosen sub-user (m,l).

It can next be determined if this best subcarrier has already been allocated to another femto-interfering subuser (m,l) at412, and if so, that allocation can be removed at414. Then, at416, process400can determine if sub-user (m,l) was previously assigned to a subcarrier, and if so, at418, allocate that subcarrier to the other femto-interfering sub-user (m,l).

If it is determined at412that the subcarrier was not allocated to another sub-user or it is determined at416that the other subcarrier was not allocated to the chosen sub-user, or after allocating the other subcarrier to the other sub-user at418, process400can then proceed to420at which it can update the price of the best subcarrier nm,l. This updating of the price can be performed in any suitable manner. For example, in some embodiments, the price rnm,lcan be updated as follows: rnm,l=rnm,l+(φm,l,nm,l−φm,l,nm,l)+ε.

Next, at422, process400can set the chosen sub-user as being happy and can determined whether the other sub-user (if any) is happy by determining whether fm,l,nm,l−rnm,l>=maxn{fm,l,n−rn}−ε.

As shown inFIG. 4b, at428, process400can choose an unhappy regular sub-user from the set of regular sub-users Ureg. The process can next calculate the chosen sub-user's maximum profit and other regular sub-users' maximum profit, and identify the best subcarrier (nm,l) with the maximum profit for the sub-user, at430. These maximum profits can be calculated in any suitable manner. For example, the chosen sub-user's maximum profit can be calculated as φm,l,nm,l=maxn(fm,l,n−rn). As another example, the other sub-users' maximum profit can be calculated as φm,lnm,l=maxn,n≠nm,l(fm,l,n−rn). fm,l,ncan be calculated as being equal to {tilde over (c)}m,l,nMU, as described above. At432, the best subcarrier nm,lcan be allocated to the chosen sub-user (m,l).

It can next be determined if this best subcarrier has already been allocated to another regular subuser ({tilde over (m)},{tilde over (l)}) at434, and if so, that allocation can be removed at436. Then, at438, process400can determine if sub-user (m,l) was previously assigned to a subcarrier, and if so, at440, allocate that subcarrier to the other regular sub-user ({tilde over (m)},{tilde over (l)}).

If it is determined at434that the subcarrier was not allocated to another sub-user or it is determined at438that the other subcarrier was not allocated to the chosen sub-user, or after allocating the other subcarrier to the other sub-user at440, process400can then proceed to442at which it can update the price of the best subcarrier nm,l. This updating of the price can be performed in any suitable manner. For example, in some embodiments, the price rnm,lcan be updated as follows: rnm,l=rnm,l+(φm,l,nm,l−φm,l,ñm,l)+ε.

Next, at444, process400can set the chosen sub-user as being happy and can determined whether the other sub-user (if any) is happy by determining whether f{tilde over (m)},{tilde over (l)},n{tilde over (m)},{tilde over (l)}−rn{tilde over (m)},{tilde over (l)}>=maxn{f{tilde over (m)},{tilde over (l)},n−rn}−ε.

Then, at446, process400can determine whether all regular sub-users are happy. If not, the process can choose a next unhappy regular sub-user at448and loop back to430. Otherwise, process400can continue to450at which it can allocate remaining subcarriers to dummy sub-users and to452at which the process can terminate.

For any arbitrarily fixed ε, this auction algorithm process can converge to an allocation that yields a total reward within Nε from the optimal objective function value of (13). A larger ε produces a worse approximation to the optimal allocation but faster convergence; while a smaller ε results in a better approximation to the optimal allocation but slower convergence.

In some embodiments, the designation of MUs as femto-interfering or regular can be updated at any suitable time. For example, the designation of MUs as femto-interfering or regular can be updated periodically, in response to any suitable metric, etc. In some embodiments, the channel quality of the subcarriers can similarly be updated at any suitable time (e.g., periodically, in response to a suitable metric, etc.) and then the subcarrier allocation re-performed.

In some embodiments, intra-tier subcarrier allocation to the femtocells can be performed in a distributed manner. In some embodiments, such an allocation can be made by a femtocell observing SINR for subcarriers available to it and by selecting those subcarriers with higher values.

More particularly, in some embodiments, such a subcarrier allocation process can be formulated as follows:

pqdenote the pth user (or FU) in the qth femtocell;

P is the total number of FUs;

Q is the number of FAPs in a macrocell;

ωpqis a priority or weighting factor for user pq;

cpqndenotes the obtainable throughput for the pth FU in the qth femtocell on the nth subcarrier; and

apqnis an indicator variable, such that apqn=1 if the nth subcarrier is allocated to the pth FU in the qth femtocell.

The second constraint in (15) indicates that one given frequency can be allocated to at most one FU in the same femtocell to avoid intra-cell interference. The third constraint in (15) indicates that the number of subcarriers one FU can be allocated to is kpq.

cpqncan be estimated based on the SINR of the subcarrier in some embodiments. More particularly, for example, if the nth subcarrier for FU p in the qth femtocell has SINR γpqnFU, assuming a 3 dB gap to theoretical rate, then its rate can be estimated as

cpq⁢n=log(1+γpq⁢nF⁢U2)⁢⁢(bits⁢/⁢channel⁢⁢use).
The SINR of a subcarrier can be estimated by performing an interference measurement on the subcarrier by an FAP using the FAP's sniffer capability.

The optimization problem in (15) can be translated into a symmetric assignment problem by introducing dummy users as follows:

In some embodiments, an auction algorithm, such as that described above, can be used to solve this symmetric assignment problem. As with the auction process described above, assuming a set of prices {rn, n=1, . . . , N}, a total number of objects N, and a positive scalar ε, a player p can be defined as being happy with the object npif the profit (i.e., reward minus price) of assigning object npto player p is within ε from a maximum profit. For example, this relationship can be represented as:
fpnp−rnp≧=maxn{fpn−rn}−ε,  (17)
where:

fpnpdenotes the reward of object npto player p; and

rnprepresents the current price of object np.

If an object npassigned to player p does not satisfy the inequality (17), player p is defined as being unhappy. For problem (17), the reward denotes the data throughput of each subcarrier for every sub-user and the price is an increasing variable during the auction process.

An example of an auction process for solving (16) that can be used in some embodiments is shown inFIG. 5.

Turning toFIG. 5, after process500has begun at502, the process can initialize ε, the happiness of sub-users, and subcarrier prices at504. For example, any suitable ε can be selected, all sub-users (except for the dummy sub-users) can be set as being unhappy, and the price for every subcarrier rncan be set to zero.

Next, at506, process500can choose an unhappy sub-user from the set of sub-users. The process can next calculate the chosen sub-user's maximum profit and other sub-users' maximum profit, and identify the best subcarrier (np,l) with the maximum profit for the sub-user, at508. These maximum profits can be calculated in any suitable manner. For example, the chosen sub-user's maximum profit can be calculated as φp,l,np,l=maxn(fp,l,n−rn). As another example, the other sub-users' maximum profit can be calculated as φp,l,ñp,l=maxn,n≠np,l(fp,l,n−rn). fp,l,ncan be calculated as being equal to {tilde over (c)}p,l,n, as described above. At510, the best subcarrier np,lcan be allocated to the chosen sub-user (p,l).

It can next be determined if this best subcarrier has already been allocated to another subuser (p,l) at512, and if so, that allocation can be removed at514. Then, at516, process500can determine if sub-user (p,l) was previously assigned to a subcarrier, and if so, at518, allocate that subcarrier to the other sub-user (p,l).

If it is determined at512that the subcarrier was not allocated to another sub-user or it is determined at516that the other subcarrier was not allocated to the chosen sub-user, or after allocating the other subcarrier to the other sub-user at518, process500can then proceed to520at which it can update the price of the best subcarrier np,l. This updating of the price can be performed in any suitable manner. For example, in some embodiments, the price rnp,lcan be updated as follows: rnp,l=rnp,l+(φp,l,np,l−φp,l,ñp,l)+ε.

Next, at522, process500can set the chosen sub-user as being happy and can determined whether the other sub-user (if any) is happy by determining whether f{tilde over (p)},{tilde over (l)},n{tilde over (p)},{tilde over (l)}−rn{tilde over (p)},{tilde over (l)}>=maxn{f{tilde over (p)},{tilde over (l)},n−rn}−ε.

Then, at524, process500can determine whether all sub-users are happy. If not, the process can choose a next unhappy sub-user at526and loop back to508. Otherwise, process500can terminate at528.

In some embodiments, each FAP can periodically estimate the quality of the allocated subcarriers and update the subcarrier allocation if necessary. This periodic estimation and updating can be performed independently and asynchronously of periodic estimation and updating by other FAPs. For example, each iteration of subcarrier allocation update can be performed every t+Δt seconds in each femtocell, where Δt is a random back-off time that is uniformly distributed.

In some embodiments, in performing this subcarrier allocation, the interference caused by a given FU to non-neighboring FAPs can be ignored.

In some embodiments, rather than performing subcarrier allocation separately, subcarrier allocation to the femtocells can be performed in a joint manner. Such an allocation process can involve message exchanges between adjacent femtocells during each iteration to coordinate the allocation.

In such an allocation, “virtual” users can be used to capture interactions between adjacent femtocells. Every FU in a femtocell can generate a virtual user at each adjacent femtocell. Each virtual user can be allocated the same subcarriers as its corresponding FU. This way, the multi-cell subcarrier allocation problem can be decomposed into a group of single cell frequency allocation problems in which the interference between users in different femtocells is represented by constraints between its own users and the corresponding virtual users.

In some embodiments, such a multi-cell subcarrier allocation problem can be formulated as follows:

pqdenote the pth user (or FU) in the qth femtocell;

P is the total number of FUs;

Q is the number of FAPs in a macrocell;

ωpqis a priority or weighting factor for user pq;

cpqn, denotes the obtainable throughput for the pth FU in the qth femtocell on the nth subcarrier;

apqnis an indicator variable, such that apqn=1 if the nth subcarrier is allocated to the pth FU in the qth femtocell;

Sqrepresent the q-th femtocell's interference user set containing all the users in its adjacent femtocells;

every user pi,i≠qεSqcan generate interference to the qth femtocell; and

{tilde over (p)}iqdenotes the virtual user generated for the qth femtocell by the FU piin the adjacent ith femtocell.

The first three constraints in (18) are equivalent to those for the single-cell case in (15). The fourth constraint in (18) models the effect of inter-femtocell interference.

Note that the problem in (18) is feasible if and only if Σpqkpq+ΣpiεSqkpi<=NS.

A greedy algorithm process can be used to solve this problem in some embodiments. In a first step of such a process, an auction method can be independently performed for resource allocation in every femtocell while ignoring the constraint that each user and its corresponding virtual user(s) must share the same resource. The reward for allocating a subcarrier in a cell to any of its users can be acquired based on the SINR and cpqn, while the reward for allocating a subcarrier in a cell to any virtual user is set as zero in the first step, so no cell will allocate any resource to its virtual users. In the second step, we ensure that every user occupies the same subcarriers as its corresponding virtual user(s), by trading subcarriers in a greedy fashion.

An example of such a process for allocating subcarriers is illustrated inFIG. 6. As shown, after beginning at602, process600can obtain the set Sqfor each femtocell q at604. Next, an auction algorithm can be run to perform a subcarrier allocation for every femtocell at606. Any suitable auction algorithm can be used. For example, the auction algorithm described above for distributed intra-tier femtocell subcarrier allocation can be used in some embodiments.

Process600can next select the first femtocell at608. Then, at610, the subcarrier allocation results for each user in Sq and femtocell q can be collected, and the conflicting subcarriers (Cq) which are simultaneously occupied by the users in Sq and femtocell q can be identified.

At612, process600can determine if there are any conflicting subcarriers in the femtocell. If not, then process600can branch to632where it can be determined if there are anymore femtocells to be processed. Otherwise, process600can proceed to614where the first conflicting subcarrier in the femtocell can be selected.

Next, at616, it can be determined whether the weighted rate (ωpqn) of the assigned user in femtocell q is less than that of any user in Sq. If so, then the subcarrier can be removed from allocation to corresponding user in femtocell q at618, and the maximum weighted rate subcarrier from the remaining subcarriers which are not occupied by the femtocell q and the users in Sq can be allocated to this corresponding user in femtocell q at620. Otherwise, the subcarrier can be removed from allocation to the corresponding users in Sq at622, and the maximum weighted rate subcarrier for each of these users can be found from their corresponding remaining subcarriers which are not allocated to these users' femtocells and the interference user set Sq.

After completing620or624, the updated subcarrier allocation results of each user in Sq can be provided to the corresponding FAP.

Then, at628, process600can determine whether the current conflicting subcarrier is the last conflicting subcarrier for the present femtocell. If not, process600can select the next conflicting subcarrier at630and branch back to616. Otherwise process600can determine if the current femtocell is the last femtocell at632. If not, then process600can select the next femtocell at634and then branch back to610. Otherwise, process600can terminate at636.

The mechanisms and processes described herein for controlling power and allocating subcarriers in macrocells and femtocells can be used in any suitable networks incorporating macrocells and/or femtocells in some embodiments. For example, in some embodiments, these mechanisms and processes can be used in OFDMA networks. More particularly, these mechanisms and processes can be used, for example, in WiMax-OFDMA networks using any suitable modulation, such as QPSK, 16-QAM and 64-QAM (for example).

The mechanisms and processes described herein for controlling power and allocating subcarriers in macrocells and femtocells can be implemented in any suitable hardware that is part of or connected to a macrocell or femtocell in some embodiments. For example, these mechanisms and/or processes can be implemented in any of a general purpose device such as a computer or a special purpose device such as a client, a server, mobile terminal (e.g., mobile phone), etc. Any of these general or special purpose devices can include any suitable components such as a hardware processor (which can be a microprocessor, digital signal processor, a controller, etc.), memory, communication interfaces, display controllers, input devices, etc.