CHAPTER 3

RESOURCE ALLOCATION IN OFDMA-BASED MULTI-TIER CELLULAR NETWORKS

With the adoption of OFDMA as the radio access technology in the current and next-generation wireless networks such as the WiMAX and LTE/LTE-Advanced networks, radio resource allocation for OFDMA-based cellular networks has become a very important research topic. Early works in this area have focused on the single-cell scenario where resource allocations under different fairness criteria such as max–min and proportional fairness were considered for DL [1-8], and UL [9-10]. Since these resource allocation problems are mixed integer programs, various low-complexity algorithms have been developed most of which are based on decomposed sub-channel and power allocation solution. More recently, there have been some works that proposed resource allocation algorithms considering multi-cell coordination and interference management where sub-channels are reused over the cells [11-16]. In general, resource and interference management problems for OFDMA-based networks are NP-hard under most fairness criteria [17]. Therefore, finding optimal solutions for these resource allocation problems typically involves exponential computational complexity. As a result, most low complexity resource allocation algorithms for OFDMA-based wireless networks seek to achieve sub-optimal but efficient solutions considering various QoS and fairness constraints.

In the multi-tier context, simple spectrum allocation methods [18-20] have been proposed. Again, RRM in the multi-tier heterogeneous cellular network (HetNet) must address the differentiated spectrum access priorities, more diverse QoS requirements of different tiers, and also the tier association problem.

In this chapter, we first review some existing works on resource allocation for OFDMA-based homogeneous cellular wireless networks. Then, we present an exemplary resource allocation design for OFDMA-based HetNets. Specifically, a max–min fair resource allocation framework with macrocell protection is described for OFDMA-based two-tier HetNets. We then reveal the optimal structure of the problem and present an optimal algorithm to resolve it. A distributed and low complexity algorithm using an adaptive weight-based sub-channel allocation is also described. Then, we summarize the chapter and discuss some potential research directions.

3.1 RESOURCE ALLOCATION FOR OFDMA-BASED HOMOGENEOUS NETWORKS

We present some important resource allocation techniques and existing algorithms for single-cell OFDMA networks. In such networks, the key difference between the DL and UL resource allocation lies in the power constraints where there is a single- power constraint at the BS for the DL while each individual user imposes one corresponding power constraint in the UL. Moreover, the employment of an appropriate solution approach to solve the underlying problem usually depends on the fairness constraint imposed in the resource allocation problem. Solving a resource allocation problem requires to determine how to allocate sub-channels and the corresponding power levels to users considering the fairness and power constraints. To perform such resource allocation, either continuous or discrete rate models are assumed, which are described in the following.

3.1.1 Physical-Layer Model

The rate model describes how the achievable rate on a particular sub-channel varies with the allocated power or the corresponding SINR. One common rate model widely used in the resource allocation literature specifies the relationship between rate and SINR as follows:

(3.1)

where r is the normalized rate in b/s/Hz (i.e., the spectral efficiency) or the number of “bits” per OFDM symbol for discrete rates, γ denotes the SINR (or SNR if there is no interference), and β denotes the gap to capacity. In particular, the parameter β can be approximated when the adaptive modulation using MQAM is employed as where denotes the target BER value [21]. Using (3.1) and this relationship for β, we can express the required SINR for a particular normalized rate r as follows:

(3.2)

Although this formula can be used for both continuous and discrete rate, more accurate calculation can be performed if the explicit BER expression for the discrete rate adaptation is given. For example, suppose that MQAM modulation is adopted for communication on each sub-channel where the constellation size s for is chosen from a predetermined set . Let be the required SINR value to guarantee acceptable performance in terms of BER when a constellation size s is adopted on a particular sub-channel. To determine , let be the expression of BER with respect to SINR when the constellation size s is adopted. Then, the SINR must satisfy the following requirement when the constellation size s is employed

(3.3)

where denotes the inverse function of the BER function , and is the target BER value.

3.1.2 Downlink Single-Cell Resource Allocation

DL resource allocation for single-cell OFDMA systems with user rate requirements to minimize the total transmission power is one of earliest problems considered in this context [1]. In fact, the DL resource allocation for single-cell OFDMA under max–min fairness criterion is closely related to this problem. These two problems are referred to as margin adaptation (MA) and rate adaptation (RA) problems, respectively [5]. To describe formulations for these problems, suppose there are N users and K sub-channels in the considered cell. Let us denote the channel gain from the BS to user i on sub-channel n as hni and the noise power at user i on each sub-channel n as . Then, the SNR achieved by user i on sub-channel n can be expressed as follows:

(3.4)

where pni is the transmission power at the BS to user i on sub-channel n. Using this relationship, we can find the required transmission power to achieve a particular rate rni as follows:

(3.5)

where is the required SNR to support rate rni given in Section 3.1.1. Let ani represent the sub-channel allocation variables where ani=1 if sub-channel n is allocated for user i and ani=0, otherwise. For brevity, we use a vector a to represent all sub-channel allocation variables for all users over all sub-channels.

Margin adaptive optimization: In the MA optimization problem, each user i requires to achieve a particular rate Ri. The MA optimization problem can be formulated as follows:

(3.6)

(3.7)

(3.8)

In this formulation, we aim to minimize the total transmission power in (3.6) subject to the rate constraints in (3.7). In addition, it is required that each sub-channel can only be allocated to exactly one user (3.8).

Rate adaptive optimization: The RA optimization can be formulated as follows:

(3.9)

(3.10)

(3.11)

where we aim to maximize the minimum rate achieved by all users in (3.9) (i.e., max–min fairness) and represents the power budget at the BS. Here, represents the rate achieved by user i. Moreover, it is required that the total transmission power at the BS is smaller or equal to its power budget in (3.10). Finally, we also impose the sub-channel allocation constraints in (3.11) as in the MA optimization problem.

Relationship Between MA and RA optimization problems: The optimal solution of the RA problem can be obtained by using the optimal solution of the MA problem. Specifically, suppose we know how to find the optimal solution of the MA problem for any set of required rates of all users. Now, suppose all users require to achieve the same rate R. Then, we can find the optimal solution of the RA problem by finding the maximum common rate R that can be achieved with the maximum power budget of the BS. This can be obtained by iteratively applying the solution of the MA problem. We describe an iterative algorithm for the discrete and integer rate adaptation in the following algorithm [5]. We assume that users can achieve only integer normalized rate on each allocated sub-channel, which can be realized by adaptive modulation in practice.

For the continuous rate, a similar algorithm can be developed by slowly increasing the common rate R in step 4 of the above algorithm as long as the power constraint at the BS is still satisfied. Specifically, we update the common rate in each step as where is a predetermined small number. Due to the above relationship between the MA and RA optimization problems, it is sufficient to consider only the MA optimization problem.

Algorithm 3.1 RA OPTIMIZATION VIA RECURSIVELY SOLVING MA PROBLEM

Efficient and low complexity algorithm for MA problem: The MA problem can be transformed into an integer linear program (ILP) by combing the sub-channel and rate allocation variables ani and rni into one single variable [5]. Therefore, we can obtain the optimal solution of the MA problem by using any available ILP solver such as CPLEX. However, computation time needed to solve such ILP can be very large, which may prevent it from being useful in practice. Therefore, a low complexity algorithm that can find an efficient solution for the MA problem is more desirable. There are several such algorithms that have been proposed in the literature [1,3–5]. In fact, a low complexity algorithm developed by relaxing integer sub-channel allocation variables to real variables and solving the Karush–Kuhn–Tucker (KKT) conditions of the corresponding relaxed problem was the first proposed in the literature [1]. Other greedy algorithms with comparable performance but lower complexity were later proposed in [3,4].

Low complexity algorithms typically aim to determine an efficient sub-channel allocation solution in the first step and power allocation is performed in the second step for the given sub-channel allocation. In the following, we describe the sub-channel allocation technique proposed in [5]. This solution approach is developed based on the observation that the number of bits (i.e., normalized discrete rate) loaded on different sub-channels for any particular user is roughly the same in optimality. This observation was indeed verified through numerical studies in [5]. Now, suppose that user i is allocated mi sub-channels and the rate achieved on each allocated sub-channel is equal to ri. Then, the MA optimization problem (3.6–3.8) can be rewritten as follows:

(3.12)

(3.13)

(3.14)

The constraints (3.13) come from the constraints (3.7) where we have used the following relationship Ri=miri. For given channel gains, the quantities pni(ri) in the objective function (3.12) can be considered as known sub-channel assignment weights. Hence, the optimization problem (3.12–3.14) is a transportation problem whose optimal solution can be obtained by solving the corresponding relaxed linear program (LP) [22,23]. Therefore, we can obtain the sub-channel allocation solution for all users if we can determine the value ri of each user i. To fulfil this task, we estimate the average required transmission power to support a particular rate ri for user i as follows:

(3.15)

where and are the average channel gain and noise power of each user i over all sub-channels, respectively. Then, the MA optimization problem (3.6–3.8) can be simplified to

(3.16)

(3.17)

Note that the rate on every assigned sub-channel for user i is assumed to be equal to ri. Therefore, Ri/ri gives the number of sub-channels required to support rate Ri for user i. The constraint (3.17) holds since there are K sub-channels to be shared among all users. To solve the problem (3.16–3.17), we define xi=1/ri and obtain the following equivalent optimization problem

(3.18)

(3.19)

For practical systems, the power-rate function is convex. Therefore, the optimization problem (3.18–3.19) is convex, whose optimal solution can be found from the KKT conditions. Specifically, we can write the Lagrangian for this problem as follows:

(3.20)

where λ represents the Lagrange multiplier. Differentiate with respect to xi and set the result to zero we obtain

(3.21)

Using this set of N equations together with the constraint on the number of sub-channels, that is,

(3.22)

we can find the optimal values of and . It is difficult to find closed-form expressions for these optimal variables since these equations involve non-linear functions. However, we can employ the vector-based Newton’s method to find its solution [24]. Once we have determined , we are able to calculate . Then, we can find the sub-channel allocation solution by solving the transportation problem (3.12–3.14). Note that the right-hand side of the constraints (3.13) must be integer numbers; therefore, we must round the quantities to the corresponding integer number.

The procedure presented above allows us to determine a feasible sub-channel allocation for all users. To complete the resource allocation, we have to perform power allocation for all sub-channels based on the obtained sub-channel allocation solution. In fact, optimal power allocation can be performed by using the well-known bit-loading algorithm if the rate is discrete [1,5]. Recall that Ri denotes the required rate of user i. Also, let Si be the set of sub-channels allocated for user i. The bit-loading algorithm is presented in the following. For the continuous rate, the power allocation can be performed by a water-filling type algorithm. Examples of such power allocation algorithms can be found in [6,8].

Algorithm 3.2   BIT LOADING ALGORITHM

DL Resource Allocation Under Other Fairness Criteria: While max–min fairness provides essentially the same throughput performance for all users, it may harm the total network throughput if there are some users in very poor channel conditions. There are some existing works that attempt to perform DL resource allocation under other fairness constraints. In [6], the total throughput maximization problem is considered subject to the constraints that achievable rates of all users satisfy predetermined ratios as well as the BS power constraint. A greedy iterative sub-channel allocation algorithm is developed under uniform power allocation over sub-channels where the user with minimum ratio between its current rate and required rate is allocated the best available sub-channel in each iteration. Then, the transmission power is allocated for the obtained sub-channel allocation solution considering both power and rate constraints by solving the KKT conditions of the corresponding optimization problem. Again, a numerical method based on iterative Newton’s algorithm is employed to solve the set of non-linear equations obtained from the KKT conditions.

In [8], a general DL resource allocation problem for utility maximization is considered. In the following, we describe a low complexity solution approach proposed in this work. Let Ui(Ri) be the utility achieved by user i for a data rate Ri. Then, the utility maximization problem can be written as follows:

(3.23)

(3.24)

(3.25)

where pni(rni) is the required power to support rate rni by user i on sub-channel n, which is given in (3.15), and is the achieved rate of user i. In general, the utility functions can be chosen to be a concave and increasing function that enables fair spectrum sharing among users under certain criteria such as α-fairness [35]. Define the total utility as where a denotes the sub-channel allocation vector whose elements are the sub-channel allocation variables ani. For a certain power allocation solution such as uniform power allocation over sub-channels, the following must hold for concave utility functions

(3.26)

where is the gradient of Ua) with respect to a, which can be expressed as follows:

(3.27)

where

(3.28)

In [8], the sub-channel allocation is developed so that satisfies the following condition

(3.29)

Then, the result in (3.26) implies that this sub-channel allocation solution satisfies

(3.30)

which means that is an optimal solution for the considered resource allocation problem. Let Si be the set of sub-channels allocated for user i. Then, the optimality condition (3.26) implies the following

(3.31)

where . For the system with two users, an optimal sub-channel allocation based on this optimality condition can be obtained as follows. We first sort the sub-channel n in the increasing values of rn2/rn1 to form a set of sub-channels . Then, there exists an index so that the optimal sub-channel allocation sets for the two users are and . By comparing the total utility achieved by all possible K+1 allocation solutions, the optimal one can be obtained. Based on the optimal solution for two users, an efficient sub-channel allocation for N>2 users can be developed by iteratively updating the sub-channel allocations for any two users.

Given a sub-channel allocation solution, we can perform power allocation again to enhance the system performance. For discrete-rate systems, a greedy bit-loading algorithm, which is similar to that used in the MA problem, can be developed as follows. We iteratively increase the current rate on one “best” sub-channel to the next rate (i.e., loading one more bit) in each iteration. Specifically, the best sub-channel n is the one that achieves maximum where and represent the increase in utility and transmission power due the bit-loading operation. In addition, only the rate updates that can maintain the power constraint at the BS are considered in each iteration. For concave utility functions, this greedy power allocation can be shown to be optimal. For continuous-rate systems, the power allocation must solve the following optimization problem

(3.32)

(3.33)

where no sub-channel allocation constraint is needed since the sub-channel allocation solution is assumed to be given. The KKT conditions of this non-linear and convex problem give the optimal power allocation for the users

(3.34)

where ; λ and must satisfy the following

(3.35)

This is a utility-based water-filling to obtain the optimal power solution [8], whose detailed implementation is described in the algorithm presented in the next page.

3.1.3 Uplink Single-Cell Resource Allocation

UL resource allocation problems in OFDMA-based systems is more challenging than the DL counterparts in general. This is because multiple power constraints for individual users must be imposed for the UL while there is a single BS power constraint for the DL. There are some existing works on the UL resource allocation for throughput and utility maximization, which are in [9,10], respectively. Given that the throughput maximization problem is a special case of the utility maximization problem, in the following, we describe the low complexity algorithm proposed in [10].

Algorithm 3.3   Iterative Water-Filling Based Power Allocation

Denote by Ui(Ri) the utility achieved by user i and Pi the maximum power budget of user i for UL transmission. Then, the UL resource allocation problem for utility maximization can be formulated as follows:

(3.39)

(3.40)

(3.41)

where (3.40) describes the power constraint for each user and (3.41) captures the sub-channel allocation constraints. Here, and denote the sub-channel and power allocation variables, respectively. Also, denotes the total achievable rate of user i over all allocated sub-channels. Since this is a mixed integer and non-linear optimization problem, finding its global optimal solutions would require exponential computation efforts. Therefore, the KKT necessary conditions are used to develop an efficient but sub-optimal sub-channel allocation solution [10]. Specifically, given a power allocation solution, it is necessary that a sub-channel n must be allocated to user as follows:

(3.42)

In addition, if a sub-channel allocation solution for all users is given, then the optimal power allocation for continuous-rate systems is the standard water-filling algorithm, that is,

(3.43)

where is determined so that

(3.44)

In fact, is called the water level of user i. By employing these sub-channel allocation criteria and the optimal water-filling power allocation, we can develop a low complexity resource allocation for UL utility maximization. This algorithm can be modified slightly for discrete-rate systems by using a standard bit-loading algorithm for power allocation in the last step.

Algorithm 3.4   UPLINK RESOURCE ALLOCATION FOR UTILITY MAXIMIZATION

3.1.4 Resource Allocation for Homogeneous Multi-Cell OFDMA Networks

Resource allocation problems for OFDMA-based cellular networks in the multi-cell environment are very difficult to solve even in a centralized setting. In fact, solving such problems requires to determine the joint sub-carrier (or sub-channel) and power allocation for all users in different cells to optimize a predetermined objective function subject to power and other constraints. There are closely related but simpler spectrum management problems in the context of DSL where each subscriber line can utilize all sub-carriers and power allocation for the sub-carriers must be determined to optimize the chosen objective function (e.g., weighted sum-rate maximization). These DSL spectrum management problems are challenging since the rate region is not convex, which implies that the underlying optimization problems are not convex optimization problems. However, it was discovered in [25,26] that solving the corresponding dual problem can help obtain the optimal solution if the number of sub-carriers is sufficiently large. This result was proved rigorously later in [17]. Other efficient algorithm based on successive convex approximation has been recently proposed in [27] to tackle the non-convexity of the spectrum management problem.

The resource allocation for OFDMA-based multi-cell wireless networks involves optimization over integer sub-channel allocation and continuous power allocation variables. There are several low complexity algorithms that are proposed to solve the underlying mixed integer non-linear resource allocation problems in the literature [11–13]. In this section, we describe a dual-based low complexity algorithm proposed in [12] which is proved to converge and achieve local optimality.

We proceed by presenting the system model and problem formulation. We consider an OFDMA-based cellular network where users in different cells share K sub-channels using full frequency reuse. Suppose there are M cells where the set of users in cell m is denoted as whose cardinality is Nm. Also, associations between users and their BSs are assumed to be fixed during the resource allocation. Denote the channel gain from BS to user i and the noise power at user over sub-channel n as hnm,i and , respectively. Also, let pnm be the transmission power by BS m on sub-channel n. Then, we can express the SINR achieved by user i associated with BS m over sub-channel n as follows:

(3.45)

The corresponding achieved rate of user i in cell m on sub-channel n is

(3.46)

Then, the DL multi-cell resource allocation problem for weighted sum rate maximization can be formulated as follows:

(3.47)

(3.48)

where i(m, n) denotes the user in cell m that is allocated sub-channel n, wi(m,n) is the weight of user i(m, n), and denotes the maximum power budget of BS m. For brevity, the optimization variables are expressed in the compact form p and i, respectively.

Low complexity dual-based algorithm: We first obtain the necessary optimality condition of this optimization problem. First, optimal sub-channel allocation must satisfy the following for a given feasible power allocation vector p:

(3.49)

To obtain additional optimality condition, we construct the Lagrangian as follows:

(3.50)

where are the Lagrange multipliers and λ is the corresponding vector capturing all individual . Then, the KKT conditions can be expressed as follows:

(3.51)

(3.52)

(3.53)

(3.54)

where

(3.55)

The conditions in (3.51) is obtained by setting the derivative of with respect to pnm to zero. To develop dual-based algorithm, we need to define the dual function as follows:

(3.56)

Then, the dual problem can be defined as follows:

(3.57)

In general, the optimal dual objective function gives an upper bound of the objective function f(p, i) in (3.47). However, they are approximately the same if the number of sub-channels is sufficiently large [26]. Therefore, solving the dual problem (3.57) can provide an efficient solution for the considered resource allocation problem. The low complexity algorithm can be developed by iteratively and sequentially solving the primal problem (3.56) for fixed and the dual problem (3.57) for fixed p and i. We describe how to solve these problems in the following. The dual function can be rewritten as follows:

(3.58)

Therefore, the optimal solution of this primal problem can be obtained by solving K per-sub-channel problems as follows:

(3.59)

where pn and in capture power and sub-channel allocation decisions on sub-channel n. This per-sub-channel problem is still very complex to solve since it is a mixed integer non-linear optimization problem. To overcome this challenge, we optimize power and sub-channel allocation in separate steps. In addition, power allocation is performed by using a low complexity iterative coordinate ascent search, which is also employed in the DSL context [26]. Let and be the power and sub-channel allocation in a previous iteration, respectively. Then, the coordinate ascent search algorithm works as follows. We first keep and unchanged but optimize . Then, we use the previous values of and to optimize and so on. For a particular cell m, this one- dimensional optimization problem can be written as follows:

(3.60)

(3.61)

After the power optimization is performed based on the above coordinate ascent search, the sub-channel allocation solution is determined according to (3.49).

We now describe how to solve the dual problem in (3.57) by using the ellipsoid method. The idea is to form an ellipsoid which contains at least one optimal solution . Then, by updating the sub-gradient of the dual function iteratively based on which we can determine the new ellipsoids whose size reduces over iterations. First, it can be verified that the sub-gradient d of the dual function has its components that can be expressed as follows:

(3.62)

An ellipsoid with center and with the shape defined by a positive semidefinite matrix A0 can be defined as follows:

(3.63)

It is shown in [12] that the optimal must lie within an ellipsoid formed with the following parameters

(3.64)

where is the dual variable that solves (3.57) when only BS m is active and . The ellipsoid algorithm then updates in iteration t as follows:

(3.65)

(3.66)

(3.67)

where the sub-gradient vector dt is calculated as in (3.62) at . This low complexity resource allocation algorithm is summarized in the following algorithm.

Algorithm 3.5DUAL-BASED MULTI-CELL RESOURCE ALLOCATION FOR WEIGHTED SUM-RATE MAXIMIZATION

Algorithm initialization and signaling reduction: Since the underlying resource allocation problem is a mixed integer non-convex optimization problem, the proposed low complexity can only achieve a local optimal solution. Therefore, good initialization helps improve the performance achieved at convergence. In [12], an initial solution is chosen based on binary power control [28]. Specifically, under this binary power control scheme, BS m transmits with power if it is active on sub-channel n or with power qnm=0, otherwise. Then, the initial power and sub-channel allocations on sub-channel n are chosen as follows:

(3.68)

In general, the resource allocation algorithm presented above requires centralized implementation since the channel gains between all BSs and users must be known by a central controller to run the algorithm. However, the required feedback and signaling can be reduced by employing simpler sub-channel allocation as follows [12]. Each user i in cell m reports to BS m the following SINR information

(3.69)

Then, the sub-channel allocation is determined based on these estimated SINR as follows:

(3.70)

This sub-channel allocation is fixed and the proposed power control algorithm can be employed to determine transmission powers on all sub-channels. Under this reduced signaling scheme, sub-channel allocation is determined locally by each BS and only scheduled users on each sub-channel need to send their corresponding channel gains to the controller to perform power control. Therefore, the signaling overhead can be reduced significantly. It is shown in [12] that this simpler algorithm only results in slightly lower performance compared to the algorithm presented before.

An UL resource allocation problem for OFDMA cellular networks in the multi-cell context is more complicated to solve than the DL counterpart. This is because power constraints for individual users in any cell must be satisfied besides other fairness and sub-channel allocation constraints. There are quite few existing low complexity algorithms developed for UL resource allocation that can guarantee to achieve even local optimality performance. An example of such existing works is the one given in [16] where several auction based resource allocation algorithms are proposed.

3.2 FAIR RESOURCE ALLOCATION FOR TWO-TIER OFDMA NETWORKS

In general, resource allocation for OFDMA-based HetNets requires to determine joint sub-channel and power allocation as well as to protect macro users from the transmissions of femto users. Moreover, it is desirable to achieve fair resource sharing among femto users by exploiting the wireless capacity beyond what is needed to support QoS requirements of macro users. In this section, we will illustrate a max–min radio resource allocation framework for two-tier OFDMA HetNets with robust macro users’ protection [29].

We consider an OFDMA-based two-tier macrocell–femtocell network where users of both tiers share the spectrum comprising K sub-channels. We assume that there are Nf femto users served by (M−1) FBSs, which are underlaid by one macrocell serving Nm macro users. Let be the set of users in the kth cell, that is, they are served by BS k of the corresponding tier. For convenience, let represent the set of macro users and denote the set of all femto users. In addition, let and be the sets of all users and BSs, respectively. Then, we have and and where BS 1 is assumed to be the MBS.

We consider fixed BS association for all users of both tiers in the network (i.e., each user is served by a fixed BS in the corresponding tier). Let denote the BS serving user i and let be the set of all orthogonal sub-channels. We assume that there is no interference among transmissions on different sub-channels. We consider a system with full-frequency reuse where all K sub-channels are allocated for users in all cells of either tier. To describe the sub-channel assignments, let be the sub-channel assignment matrix for all N users over K sub-channels where

(3.71)

We assume that a sub-channel can be allocated to at most one user in any cell. Then, we have

(3.72)

These constraints will be applied to the UL resource allocation problem studied in the following.

To model the rate and SINR relationship, suppose that MQAM modulation with square signal constellations (i.e., where ) is employed. According to [30], the BER of the scheme with Gray encoding can be approximated as follows:

(3.73)

where stands for the Q-function, , and is the SINR. Using the result in (3.3), the target SINR for the modulation scheme can be calculated as follows:

(3.74)

where recall that is the target BER value. Suppose ideal Nyquist data pulses are used where the symbol rate on each sub-channel is equal to B where B is the bandwidth of one sub-channel. Then, if modulation scheme is employed, the spectral efficiency per one Hz of the system bandwidth is (b/s/Hz).

3.2.1 Uplink Resource Allocation Problem

Let pni represent the transmission power of user i over sub-channel n in the UL where . We impose the following constraints on the total transmission power of each individual user

(3.75)

where Pi is the maximum transmission power of user i. Similar to the sub-channel assignments, we define as an power allocation matrix where . For convenience, we also define partitions of sub-channel assignment and power allocation matrices and as follows. In particular, let represent the sub-channel assignment and power assignment matrices for users in cell k over K sub-channels, respectively.

Let hni,j and be the channel gain from user j to BS and the noise power at BS over sub-channel n, respectively. Then, for a given sub-channel assignment and power allocation solution, that is, given and , the SINR achieved at BS bi due to the transmission of user i over sub-channel n can be written as follows:

(3.76)

where is the effective interference corresponding to user i on sub-channel n, which is defined as follows:

(3.77)

We assume that sub-channel assignments for macro users have been determined by a certain mechanism and fixed while power allocation over the corresponding sub-channels for macro users are updated to cope with the CTI due to transmissions of femto users. That means is fixed while we need to determine and the corresponding power allocation solution.

To protect the QoS of the licensed macro users, we wish to maintain a predetermined target SINR for each of its assigned sub-channel n. Specifically, we have the following constraints for the macro users

(3.78)

where , which is calculated as in (3.74).

For femto users, we assume that they all employ for a predetermined sf. Then, the spectral efficiency (bits/s/Hz) achieved by femto user i on one sub-channel is

(3.79)

where and , which is calculated as in (3.74). Note that the femto users in all femtocells are assumed to employ the same constellation size sf although this assumption can be relaxed to the adaptive rate scenario. In practice, we would choose since femto users can achieve higher transmission rates on each sub-channel than that of macro users thanks to their shorter distance to the associated FBS. This is indeed equivalent to . In the analysis, we use the same notation to refer to the required target SINR of femto users or macro users where for and for . Now, we can express the total spectral efficiency achieved by user i for given sub-channel assignment and power allocation matrices and as follows:

(3.80)

To impose the max–min fairness for femto users associated with the same FBS, we define the following minimum spectral efficiency for femtocell k

(3.81)

The UL resource allocation problem for femto users can be formulated as follows:

(3.82)

(3.83)

where the minimum spectral efficiency at femtocell k, that is, , is given in (3.81). Therefore, this UL resource allocation problem aims to maximize the total min spectral efficiency of all femtocells subject to sub-channel assignment constraints, maximum power constraints, and protection constraints for macro users. Note that the SINR constraints for femto users are embedded in the calculation of femto spectral efficiency in (3.79). The resource allocation problem (3.82)–(3.83) can be transformed into a standard mixed integer program. Therefore, this resource allocation problem is NP-hard. In the following, we study the feasibility of a particular sub-channel assignment solution, which reveals the optimal structure of the optimization problems (3.82) and (3.83) based on which we develop optimal and suboptimal low complexity algorithms.

3.2.2 Feasibility of a Sub-Channel Assignment Solution

The resource allocation problem (3.82)–(3.83) involves finding a joint sub-channel assignment and power allocation solution. For a certain sub-channel assignment solution represented by matrix satisfying the sub-channel assignment constraints (3.72), we can indeed find its “best” power allocation and verify its feasibility with respect to the constraints in (3.83). In particular, we wish to satisfy the SINR constraints for femto users and macro users in (3.79) and (3.78), respectively. Specifically, for each sub-channel n we need to satisfy the SINR constraints for both macro users and femto users who are allocated this sub-channel.

Now, let denote the set of users of both tiers who are assigned sub-channel n and cn=|Sn| be the number of elements in set Sn. Then, the SINR constraints for users in set Sn, that is, , can be rewritten in a matrix form by using the SINR expression in (3.76) as follows:

(3.84)

where with , is identity matrix, , and is a matrix defined as follows:

(3.85)

According to the Perron–Frobenius theorem, there exists a non-negative power allocation solution for users that are allocated sub-channel n if and only if the maximum eigenvalue of , that is, spectrum radius , is less than 1 [30]. In addition, the Pareto-optimal power allocation for users in Sn (i.e., minimum power vector in the element-wise sense) can be expressed as [30]

(3.86)

In addition, this Pareto-optimal power allocation can be achieved at equilibrium by employing the following iterative Foschini–Miljanic [30] power updates

(3.87)

where and Rni(t) are the SINR and effective interference achieved by user i in iteration t, respectively. We state one important result for a given sub-channel assignment solution that satisfies the sub-channel assignment constraints (3.72) in the following lemma.

Lemma 3.1. Suppose that we can find a finite Pareto-optimal power allocation solution on each sub-channel n for a particular sub-channel assignment matrix , which is given in (3.86) (i.e., the spectrum radius ). Then, the underlying sub-channel assignment represented by is feasible if and only if these Pareto-optimal power allocation vectors satisfy the power constraints in (3.75).

Proof:The Pareto-optimal power allocation solution on each sub-channel n requires the minimum powers in the element-wise sense for all users, who are assigned sub-channel n, to meet their SINR requirements. Therefore, the considered sub-channel assignment solution is feasible if and only if the corresponding Pareto-optimal power allocation solutions on all sub-channels n satisfy the power constraints in (3.75). Therefore, we have completed the proof of the lemma.     

Since the number of possible sub-channel assignments is finite, the result in this lemma paves the way for developing an optimal exhaustive search algorithm, which is presented in the following.

3.2.3 Optimal Algorithm and Its Complexity Analysis

Based on the results in the previous section, we can find the optimal solution for the resource allocation problem (3.82)–(3.83) by performing exhaustive search as follows. For a fixed and feasible 1, let be the list of all potential sub-channel assignment solutions that satisfy the sub-channel assignment constraints (3.72) and the fairness condition: for all femto users . We sort the list in the decreasing order of to obtain the sorted list . Then, the feasibility of each sub-channel assignment solution in the list can be verified as presented in Section 3.2.2. Among all feasible sub-channel assignments, the feasible solution achieving the highest value of the objective function (3.82) and its corresponding power allocation solution given in (3.86) correspond to the optimal solution of the optimization problem (3.82)–(3.83).

The complexity of the exhaustive search algorithm can be determined by finding the number of the elements in the list and the complexity involved in the feasibility verification for each of them. The number of the elements in (i.e., the number of potential sub-channel assignments) is the product of the number of potential sub-channel assignments for all femtocells that satisfy the “fairness condition.” Therefore, the number of potential sub-channel assignments can be calculated as follows:

(3.88)

where represents for the largest integer less than or equal to K/Nk and denotes the “m-choose-n” operation. According to Section 3.2.2, the complexity of the feasibility verification for each potential sub-channel assignment mainly depends on the eigenvalue calculation of the corresponding matrix and solving the linear system to find the power allocation solution for each sub-channel. It requires computation complexity of O(M3) to calculate the eigenvalues of [31] and O(M3) to obtain by solving a system of linear equations [32]. Therefore, the complexity of the optimal exhaustive search algorithm is , which is exponential in the numbers of sub-channels and FBSs.

3.2.4 Sub-Optimal and Distributed Algorithm

To resolve the exponential complexity of the centralized optimal algorithm presented in Section 3.2.3, we develop a low complexity resource allocation algorithm which can be implemented in a distributed manner. As implied by (3.79) and (3.80), the total spectral efficiency achieved by each femto user i is equal to the product of rf and the number of assigned sub-channels given that the femto user can find feasible power allocation solutions on all assigned sub-channels. Since we wish to maximize the total minimum spectral efficiency of all femtocells, an efficient resource allocation algorithm would attempt to assign the maximum and equal number of sub-channels to femto users in each femtocell and to perform Pareto-optimal power allocation for all users on each sub-channel so that they meet the SINR constraints in (3.79) and (3.78).

Note that if an efficient sub-channel assignment solution can be determined then one can employ the distributed Foschini–Miljanic power control updates (3.87) on all sub-channels to find the power allocation solution. However, there can be two scenarios where a particular sub-channel assignment is not feasible. The first scenario is for the case where there not exist any power allocation that can support the SINR constraints (3.79) and (3.78) (i.e., we have for some “infeasible” sub-channel n). In this case the Foschini–Miljanic power control updates (3.87) will increase the transmission power on the “infeasible” sub-channel n to infinity [31,32] (i.e., the power update diverges). The second scenario corresponds the case where Foschini–Miljanic power control updates (3.87) converge but the power constraints for some users (3.75) are violated.

Based on these observations, we develop an iterative resource allocation algorithm in which we update the sub-channel assignment for femto users over iterations based on estimated transmission powers on their sub-channels given by the Foschini–Miljanic power control updates (3.87). Specifically, we represent the quality of a sub-channel assignment for a pair of sub-channel and femto user by a weight, which is proportional to the estimated transmission power. Moreover, the sub-channel assignment for all femto users in each femtocell is performed so that the minimum total weight is achieved. This sub-channel assignment attempts to attain an efficient and low power sub-channel assignment solution. In addition, we reduce the number of sub-channels allocated for femto users in the femtocell in which the total minimum weight is too large since this implies that the SINR constraints (3.79) and (3.78) or power constraints (3.75) are likely to be violated. This aims to prevent the system from falling into the two infeasible sub-channel assignment scenarios described above.

The proposed resource allocation algorithm employs an iterative weight-based sub-channel assignment that is performed in parallel at all femtocells. The weight for each sub-channel and femto user pair is defined as the multiplication of the estimated transmission power and a scaling factor capturing the “quality” of the corresponding sub-channel assignment. In addition, the scaling factor is updated over iterations so that it becomes larger if the corresponding assignment results in violations of the SINR constraints for femto users and/or macro users.

Each user i in cell k estimates the transmission power on sub-channel n in each iteration t of the algorithm. User i first estimates the effective interference on sub-channel n at the beginning of iteration t, denoted as Rni(t), which is given in (3.77). Then, it calculates the required transmission power by using the Foschini–Miljanic power update formula given in (3.87) as follows:

(3.89)

Then, femto user i in cell k updates the assignment weight as where the scaling factor is defined as follows:

(3.90)

where denotes the number of sub-channels assigned for each femto user in femtocell k, is a factor, which helps maintain SINR constraints of macro users (i.e., it is increased if assigning sub-channel n to femto user i tends to result in violation of the SINR constraint of the corresponding macro user), and are another factors which are set to larger values if the assignment of sub-channel n for femto user i tends to require transmission power larger than the average power per sub-channel (i.e., ) and the maximum power budget (i.e., Pi), respectively. We will set as where in the proposed algorithm. Given the weights defined for each femto user i, femtocell k finds the sub-channel assignment for its femto users by solving the following problem

(3.91)

This problem aims to find a sub-channel assignment matrix for which each femto user in femtocell k is assigned sub-channels with the minimum total weight. Therefore, by assigning a larger weight wni for bad sub-channel assignments, the sub-channel assignment solution returned by (3.91) would be efficient.

The optimization problem in (3.91) can be transformed into the standard matching problem (say between “jobs” and “employees”) as follows. Suppose we create virtual “employees” for each femto user in femtocell k, then we can consider the matching problem between virtual “employees” (virtual femto users) and K “jobs” (sub-channels). In particular, femto user i is equivalent to virtual femto users . Let the edge () between sub-channel n and virtual femto user iu represent the assignment of that sub-channel to the corresponding femto user. Then, the weight of the edge is equal to wni. After performing this transformation, the sub-channel assignment solution of the problem in (3.91) can be found by using the standard Hungarian algorithm (i.e., Algorithm 14.2.3 given in [33]). After running the Hungarian algorithm, if there exists a virtual femto user iu, , being matched with sub-channel n, then we set ani=1; otherwise, we set ani=0. For further interpretation of the proposed algorithm, let Wk(t) denote the total minimum weight due to the optimal solution of (3.91). Sub-channel assignment for femtocell k is illustrated in Figure 3.1, which is also described in Figure 3.2.

The main operations of the proposed algorithm in one iteration can be summarized as follows.

• Each macro user calculates its transmission power based on current effective interference levels by using the Foschini–Miljanic power update formula (3.89). If its power constraint is still satisfied, the macro user updates its transmission powers on assigned sub-channels accordingly (steps 5–6). In contrast, if the power constraint of any macro user is violated, the MBS will inform all FBSs which find the femto user creating the largest interference for the victim macro user and increase the parameter by a factor of 2 (steps 7–10).
• Each femtocell which has any femto power constraints being violated in the previous iteration solves the sub-channel assignment problem (3.91) with the current weight values. If the total minimum weight is larger than V times the total maximum powers of all femto users, the target number of sub-channels is decreased by one (steps 19–20).
• Each femto user that has its SINR constraint satisfied updates its transmission power on the assigned sub-channels (steps 24–25). In contrast, any femto user that has its SINR constraint violated increases its parameter by a factor of 2 for the assigned sub-channel requiring the largest transmission power (steps 26–29). In addition, we set for this femto user (step 30) so that the algorithm will update the sub-channel assignments in the next iteration.

The proposed algorithm can be implemented distributively. In fact, except for steps 7–10, each BS of either tier can collaborate with its associated users to conduct all required tasks in other steps. Moreover, the required tasks in steps 7–10 can be performed by allowing the MBS and FBSs coordinate with each other by using the wired backhaul link.

Convergence Analysis: The convergence of the proposed algorithm is stated in the following proposition.

The proposed algorithm converges to a feasible solution of the optimization problem (3.82)–(3.83).

Algorithm 3.6 DISTRIBUTED UPLINK RESOURCE ALLOCATION

Proof: To prove this proposition, we will consider two possible scenarios. For the first scenario, there exists an iteration after which the scaling factors for sub-channel assignment weights given in (3.90) do not change. Then it can be verified that after this iteration the sub-channel assignment solution will remain unchanged. In addition, the proposed algorithm simply updates transmission powers for all users on their assigned sub-channels by using the Foschini–Miljanic power updates (steps 6 and 25). Therefore, the authors in [30] have shown that these power updates indeed converge, which implies the convergence of the proposed algorithm.

Now suppose that the scaling factors vary over iterations. We will prove that the system will ultimately evolve into the first scenario discussed above. First, it can be verified that the power given in (3.89) is lower bounded by . Therefore, if the scaling factors keep increasing over iterations, then the total weight Wk(t) returned by the assignment problem in (3.91) will increase over iterations as well. Therefore, there exist some femtocells k that decrease their number of assigned sub-channels over iterations (steps 19–21). Since the initial values of all are finite, this process will terminate after a finite number of iterations. Then, the system will be in the first scenario discussed above; therefore, the proposed algorithm converges. Therefore, we have completed the proof of the proposition.     

Complexity Analysis

It is observed that the major complexity of the proposed algorithm is involved in solving the sub-channel assignment by using the Hungarian method in step 18. According to Theorem 14.2.4. of [33], the complexity of the Hungarian algorithm is O(K3). Therefore, the complexity of the proposed algorithm is for each iteration. However, the local sub-channel assignments can be performed in parallel at all (M−1) femtocells. Therefore, the run-time complexity of the algorithm is O(K3) multiplied by the number of required iterations, which is quite moderate according to the simulation results (i.e., tens of iterations).

The considered resource allocation problem and its resulting distributed algorithm can be extended for DL communication as follows. Specifically, the max–min fair resource allocation for the DL can be formulated similarly where the UL power constraints in (3.75) for individual users can be replaced by the corresponding power constraints at BSs of both network tiers. The optimal and suboptimal algorithms proposed in this section can be modified to account for these new power constraints. In particular, the sub-channel assignment weights defined in (3.90) used in the suboptimal algorithm may need to be modified to capture these new power constraints accordingly.

3.2.5 Numerical Examples

We present illustrative numerical results for the proposed algorithms using two different networks, which have a small and large number of femtocells and users, respectively. The network setting and user placement for the simulations are illustrated in Figure 3.3, where macro and femto users are randomly located inside circles of radii of r1=1000 m and r2=30 m, respectively. The channel gains hnij are generated by considering both Rayleigh fading, which is represented by an exponentially distributed random variable with the mean value of one, and the path-loss , where dij is the distance from user j to BS i, (Ai, Bi) are set as (36, 40) and (35, 35) for MBS and FBSs, respectively, C=20 and fc=2.5 GHz. Wl is the wall-loss parameter and nij is the number of walls between BS i and user j. The noise power is set as , .

To obtain simulation results, we use two modulation schemes ( and ) for macro users and five modulation schemes (, , , and ) for femto users. Moreover, we choose the target BER whose target SINRs corresponding to different modulation schemes, which can be calculated by using (3.74), are given in Table 3.1. Each simulation result is obtained by taking the average over 20 different runs where for each run, users are randomly located and a feasible sub-channel allocation matrix for macro users is chosen so that each macro user is assigned sub-channels. The maximum powers of femto and macro users are denoted as and in the figures, respectively.

Table 3.1 Target SINRs for different constellation sizes with target BER

In Figure 3.4, we show the total minimum spectral efficiency of all femtocells (i.e., the optimal objective value of (3.82)) versus the constellation size of femto users (sf) for the small network due to both optimal and sup-optimal algorithms. Clearly, for the low constellation sizes (i.e., low target SINRs), the low complexity algorithm can achieve almost the same spectral efficiency as the optimal one while for higher values of sf, it results in just slightly lower spectral efficiency than that due to the optimal one. Moreover, when we increase the value of parameter V, a slightly better performance can be achieved.

In Figures 3.5 and 33.6, we plot the total femtocell minimum spectral efficiency versus the maximum power of femto users () and macro users (), respectively, for different modulation levels of macro users (the modulation scheme of femto users is 256-QAM). These figures show that the total minimum spectral efficiency increases with the increases in maximum power budgets, or . However, this value is saturated as the maximum power budgets or become sufficiently large. In addition, as the number of macro users increases, the total femtocell minimum spectral efficiency increases thanks to the better diversity gain offered by the macro tier.

3.3 CHAPTER SUMMARY AND OPEN RESEARCH DIRECTIONS

In this chapter, we have discussed various OFDMA-based resource allocation problems and described some important design techniques that can be employed to devise efficient algorithms to solve the underlying problems. In particular, DL and UL resource allocations under different design objectives and fairness criteria have been described for both single-cell and multi-cell scenarios of single-tier wireless cellular networks. Then, we have presented an example of resource management design for a two-tier OFDMA-based macrocell–femtocell network. In general, adaptive radio resource allocation for OFDMA HetNets is a fertile research area with many open research problems. Some of the potential research directions are presented in the following.

• The resource allocation formulation and algorithms presented for the two-tier OFDMA HetNets in the last section of this chapter restrict the same rate on all sub-channels in each femtocell. In general, better performance can be achieved if optimal rate adaptation is performed on each sub-channel where transmission rates on different sub-channels can be varied depending on their channel gains. Here, either continuous or discrete rate adaptation can be considered. Development of efficient and low complexity resource allocation algorithms for DL and UL transmissions considering various fairness and protection constraints for macro users is an important but challenging area, which requires further studies. Moreover, if the BSs and users of different tiers are equipped with multiple antennae, then joint beamforming and resource allocation can be performed to further enhance the network performance. There are some existing algorithms, which are proposed for multi-antenna OFDMA single-tier wireless cellular networks [33,34]. For the HetNet setting, it would be desirable to have more flexible resource allocation algorithms that can protect macro users and enable controllable capacity sharing among different network tiers.
• In OFDMA-based two-tier HetNets, development of a flexible joint BS association and resource allocation framework is an important research problem. In particular, it is desirable that such a framework enables off-loading of any desirable amount of traffic from the macro-tier to the femto-tier for efficient load balancing and capacity sharing between the two network tiers. In practice, the femto tier may be able to provide much larger capacity than that of the macro-tier thanks to its small cell structure. In addition, user connections to the femto-tier may involve much cheaper or even free services. Therefore, there can be great benefits in off-loading more traffic to the femto-tier as long as minimum QoS requirements of femto users can be maintained. Also, distributed BS association and resource allocation algorithms, which are scalable and require only low signaling overhead, are strongly desired.

REFERENCES

1. C. Y. Wong, R. S. Cheng, K. B. Letaief, and R. D. Murch, “Multiuser OFDM with adaptive subcarrier, bit, and power allocation,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 10, pp. 1747–1758, October 1999.

2. J. Jang and K. B. Lee, “Transmit power adaptation for multiuser OFDM systems,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 2, pp. 171–178, February 2003.

3. D. Kivanc, G. Li, and H. Liu, “Computationally efficient bandwidth allocation and power control for OFDMA,” IEEE Transactions on Wireless Communications, vol. 2, no. 6, pp. 1150–1158, November 2003.

4. M. Ergen, S. Coleri, and P. Varaiya, “QoS aware adaptive resource allocation techniques for fair scheduling in OFDMA based broadband wireless access systems,” IEEE Transactions on Broadcasting, vol. 49, no. 4, pp. 362–370, December 2003.

5. I. Kim, I. S. Park, and Y. H. Lee, “Use of linear programming for dynamic subcarrier and bit allocation in multiuser OFDM,” IEEE Transactions on Vehicular Technology, vol. 35, no. 4, pp. 1195–1207, July 2006.

6. Z. Shen, J. G. Andrews, and B. L. Evans, “Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints,” IEEE Transactions on Wireless Communications, vol. 4, no. 6, pp. 2726–2737, November 2005.

7. G. Song and Y. Li, “Cross-layer optimization for OFDM wireless networks – Part I: Theoretical framework,” IEEE Transactions on Wireless Communications, vol. 4, no. 2, pp. 614–624, March 2005.

8. G. Song and Y. Li, “Cross-layer optimization for OFDM wireless networks – Part II: Algorithm development,” IEEE Transactions on Wireless Communications, vol. 4, no. 2, pp. 625–634, March 2005.

9. K. Kim, Y. Han, and S.-L. Kim, “Joint subcarrier and power allocation in uplink OFDMA systems,” IEEE Communications Letters, vol. 9, no. 6, pp. 526–528, June 2005.

10. C. Y. Ng and C. W. Sung, “Low complexity subcarrier and power allocation for utility maximization in uplink OFDMA systems,” IEEE Transactions on Wireless Communications, vol. 7, no. 5, pp. 1667–1675, May 2008.

11. G. Li and H. Liu, “Downlink radio resource allocation for multi-cell OFDMA system,” IEEE Transactions on Wireless Communications, vol. 5, no. 12, pp. 3451–3459, December 2006.

12. L. Venturino, N. Prasad, and X. Wang, “Coordinated scheduling and power allocation in downlink multicell OFDMA networks,” IEEE Transactions on Vehicular Technology, vol. 58, no. 6, pp. 2835–2848, July 2009.

13. R. Y. Chang, Z. Tao, J. Zhang, and C.-C. J. Kuo, “Multicell OFDMA downlink resource allocation using a graphic framework,” IEEE Transactions on Vehicular Technology, vol. 58, no. 7, pp. 3494–3507, September 2009.

14. Z. Han, Z. Ji, and K. J. R. Liu, “Non-cooperative resource competition game by virtual referee in multi-cell OFDMA networks,” IEEE Journal on Selected Areas in Communications, vol. 25, no. 6, pp. 1079–1090, August 2007.

15. T. Wang and L. Vanderdorpe, “Iterative resource allocation for maximizing weighted sum min-rate in downlink cellular OFDMA systems,” IEEE Transactions on Signal Processing, vol. 59, no. 1, pp. 223–234, January 2011.

16. K. Yang, N. Prasad, and X. Wang, “An auction approach to resource allocation in uplink OFDMA systems,” IEEE Transactions on Signal Processing, vol. 57, no. 11, pp. 4482–4496, November 2009.

17. Z.-Q. Luo and S. Zhang, “Dynamic spectrum management: Complexity and duality,” IEEE Journal of Selected Topics in Signal Processing, vol. 2, no. 1, pp. 57–73, February 2008.

18. Y. Sun, R. P. Jover, and X. Wang, “Uplink interference mitigation for OFDMA femtocell networks,” IEEE Transactions on Wireless Communications, vol. 11, no. 2, pp. 614–625, February 2012.

19. Z. Lu, T. Bansal, and P. Sinha, “Achieving user-level fairness in open-access femtocell based architecture,” IEEE Transactions on Mobile Computing, vol. 12, no. 10, pp. 1943–1954, October 2013.

20. Y.-S. Liang, W.-H. Chung, G.-K. Ni, I.-Y. Chen, H. Zhang, and S.-Y. Kuo, “Resource allocation with interference avoidance in OFDMA femtocell networks,” IEEE Transactions on Vehicular Technology, vol. 61, no. 5, pp. 2243–2255, June 2012.

21. A. J. Goldsmith and S. G. Chua, “Variable-rate variable-power MQAM for fading channels,” IEEE Transactions on Communications, vol. 45, no. 10, pp. 1218–1230, October 1997.

22. W. L. Winston, Operations Research: Applications and Algorithms. 4th edition. Belmont, CA: Duxbury, 2004.

23. L. A. Wolsey, Integer Programming. New York: Wiley, 1998.

24. K. E. Atkinson, An Introduction to Numerical Analysis. New York: Wiley, 1998

25. R. Cendrillon, W. Yu, M. Moonen, J. Verlinden, and T. Bostoen, “Optimal multiuser spectrum balancing for digital subscriber lines,” IEEE Transactions on Communications, vol. 54, no. 5, pp. 922–933, May 2006.

26. W. Yu and R. Liu, “Dual methods for non-convex spectrum optimization of multicarrier systems,” IEEE Transactions on Communications, vol. 54, no. 7, pp. 1310–1322, July 2006.

27. J. Papandriopoulos and J. S. Evans, “SCALE: A low-complexity distributed protocol for spectrum balancing in multiuser DSL networks,” IEEE Transactions on Information Theory, vol. 55, no. 8, pp. 3711–3724, November 2009.

28. A. Gjendemsj, D. Gesbert, G. E. Oien, and S. G. Kiani, “Binary power control for sum rate maximization over multiple interfering links,” IEEE Transactions on Wireless Communications, vol. 7, no. 8, pp. 3164–3173, August 2008.

29. V. N. Ha and L. B. Le, “Fair Resource Allocation for OFDMA Femtocell Networks with Macrocell Protection,” IEEE Transactions on Vehicular Technology, to appear.

30. G. J. Foschini and Z. Miljanic, “A simple distributed autonomous power control algorithm and its convergence,” IEEE Transactions on Vehicular Technology, vol. 42, no. 4, pp. 641–646, November 1993.

31. N. Bambos, S. C. Chen, and G. J. Pottie, “Channel access algorithms with active link protection for wireless communication networks with power control,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 583–597, October 2000.

32. M. Andersin, Z. Rosberg, and J. Zander, “Gradual removals in cellular PCS with constrained power control and noise,” Wireless Networks, vol. 2, pp. 27–43, 1996.

33. G. Zheng, K. K. Wong, and T. S. Ng, “Throughput maximization in linear multiuser MIMO-OFDM downlink systems,” IEEE Transactions on Vehicular Technology, vol. 57, no. 3, pp. 1993–1998, May 2008.

34. E. Bjornson, N. Jalden, M. Bengtsson, and B. Ottersten, “Optimality properties, distributed strategies, and measurement-based evaluation of coordinated multicell OFDMA transmission,” IEEE Transactions on Signal Processing, vol. 59, no. 12, pp. 6086–6101, December 2011.

35. J. Mo and J.Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556–567, October 2000.

1. The sub-channel assignment solution for macro users corresponding to is feasible if there exists a power allocation solution that satisfies the constraints in (3.78) when there is no femto tier.