CHAPTER 8

RESOURCE ALLOCATION IN CDMA-BASED MULTI-TIER HETNETS

RRM for CDMA wireless cellular networks has been an active research topic over the past several years. To motivate research issues in multi-tier wireless HetNets, we first review some important resource allocation algorithms, which have been proposed for homogeneous wireless networks. Development of distributed power control for CDMA cellular networks is an interesting research topic that has achieved great success so far. In 1993, Foschini and Miljanic proposed one of the most popular power control algorithms, which is usually referred to as Foschini–Miljanic power control algorithm today [1]. This power control scheme can be implemented distributively, which converges to a Pareto-optimal fixed point supporting predetermined target SINRs using minimum transmission powers whenever possible [2]. Following this great discovery, Yates developed an elegant analytical framework in his seminal paper [3], namely the standard function approach, which can be used to establish convergence and to design power control algorithms. It was later shown in [4,5] that the Foschini–Miljanic power control algorithm can be indeed designed by using noncooperative game theory with an appropriate payoff function. The Foschini–Miljanic power control algorithm aims to achieve predetermined target SINRs, which, therefore, does not attain high system throughput in lightly loaded networks. In highly loaded networks, different user removal and admission control strategies were proposed [6–8] to resolve congestion that aims to support the largest number of users with their required QoS.

By using game theory, researchers proposed various distributed power control algorithms considering different design objectives and QoS constraints such as power saving, outage constraints, and multiuser diversity exploitation [4,5 9–15]. In particular, Sung and Leung have proposed an opportunistic power control strategy that guarantees convergence and enables exploitation of multiuser diversity to enhance the system throughput [16,17]. Moreover, they developed a more general framework than that in [3] to prove the convergence of their power control scheme, based on the so-called two-sided scalable functions. The opportunistic power control strategy, however, cannot provide minimum QoS support for users as the Foschini–Miljanic power control scheme. In [18,19], a dynamic joint BS association and power control algorithm was proposed based on the Foschini–Miljanic power control scheme, and its convergence was also established. In this algorithm, each user will iteratively associate with a BS requiring the minimum transmission power while performing the standard Foschini–Miljanic power updates.

Interference and RRM becomes much more complex in the multi-tier heterogeneous cellular network, which must address the following issues.

• Different tiers of the HetNets may have different priorities in accessing the radio spectrum. Therefore, RRM must be performed in such a way that the QoS of users in the prioritized tiers is protected against spectrum access from other tiers of lower priority. For example, in a two-tier macro–femto HetNet, femto users can only be allowed to utilize the leftover capacity beyond what is needed to support the required QoS of macro users.
• Fair spectrum sharing among users and load balancing among different tiers are desired objectives in the resource management. Here, both co-tier interference and CTI must be appropriately resolved to attain high system throughput while providing fairness guarantees for the multi-tier HetNets. Also, optimizing the trade-off between co-channel interference and spectrum reuse gain must be considered in the multicell and multi-tier resource allocation problem to maximize resource utilization and throughput performance.
• Mass deployment of small cells such as femtocells in the future HetNet is needed to provide sufficient wireless capacity for many emerging broadband wireless applications. Hence, development of decentralized resource allocation algorithms that require low coordination overhead and signaling is a crucial research issue. In addition, such decentralized resource allocation algorithms are desired to achieve optimal performance or at least some guaranteed fraction of the optimal performance (e.g., network throughput or network utility).

Most existing works on HetNets focus on approximated performance analysis for large random networks using stochastic geometry [20–23], design of heuristic transmission power setting, or control schemes [20, 24,25]. While the stochastic geometry approach can be useful in quantifying approximate performance of very large HetNets, it would not be sufficient for designing practical and implementable resource allocation algorithms for HetNets. In addition, most existing algorithms do not provide efficient QoS protection mechanisms for prioritized network tiers (e.g., macro tier in a macro–femto two-tier network) and allow autonomous and distributed implementation with strong convergence and performance guarantees. Therefore, a lot of further efforts are needed to resolve open research issues in the coming years.

In this chapter, we present some exemplary resource allocation algorithms for CDMA-based multi-tier HetNets. We will demonstrate how game theory and optimization theory can be employed to devise distributed algorithms with different trade-offs between signaling overhead and efficiency. All presented algorithms provide robust QoS protection for macro users and converge to desirable operating points. Firstly, we review existing literature on resource allocation and QoS support in single-tier homogeneous wireless cellular networks. Secondly, a price-based noncooperative game theory approach is taken to design a dynamic spectrum sharing algorithm for two-tier macro–femto networks under the closed access mode. We describe how different utility and cost functions are chosen for macro and femto users to achieve some desirable design objectives. Thirdly, a general framework for joint BS association and power control for wireless HetNets is presented and its convergence is established for a broad class of power control algorithms satisfying some well-defined properties. We then discuss an efficient hybrid power control (HPC) algorithm for the proposed framework exploiting the advantages of well-known Target-SINR-tracking Power Control (TPC) and Opportunistic Power Control (OPC) power control schemes. An adaptation mechanism for the proposed framework using the HPC algorithm and its application to design a hybrid spectrum access scheme for the two-tier HetNet are also presented. Fourthly, we demonstrate how optimization theory can be employed to devise a distributed Pareto-optimal power control algorithm for two-tier HetNets with QoS protection for macro users in terms of minimum SINR requirements. Fairness among femto users is achieved by formulating the resource allocation problem as a utility maximization problem using a general α-fair utility function. Finally, the chapter ends with summary of the presented algorithms and some future research directions.

8.1 POWER CONTROL AND RESOURCE ALLOCATION TECHNIQUES FOR HOMOGENEOUS CDMA NETWORKS

In CDMA-based wireless cellular networks, simultaneous transmissions of all users occur on the same frequency spectrum. Therefore, inter-user interference can significantly degrade the network performance if not controlled appropriately. Power control is the key technique for interference management and QoS support in CDMA cellular networks. Since interference happens for different users in the same cell and for users in different cells (i.e., intracell interference and ICI), distributed power control algorithms are strongly desired so that users can autonomously adapt their transmission powers to cope with the corresponding received interference. In this section, we review some popular power control algorithms and their design principles, which have been proposed for homogeneous single-tier CDMA cellular networks.

Let pi be the transmission power of user i and be the power of additive white Gaussian noise measured in the spectrum bandwidth at the receiving end of user i. Also, denote the channel gain from the transmitter of user i to his or her receiver by , and that from the transmitter of user j to the receiver of user by hi,j. Then, the received SINR of user i can be written as

(8.1)

where PG is the processing gain of the system.

Note that the first term in the denominator of (8.1) includes both intracell interference and ICI and this SINR expression applies to both UL and DL scenarios. For notational convenience, let where the processing gain PG is absorbed into the channel gain . The received SINR of user i can then be expressed as

(8.2)

Design of power control algorithms would typically consider some SINR constraints for QoS support and fairness among users. We will describe some well-known power control algorithms and their design principles in the following.

8.1.1 Target-SINR-Tracking Power Control

In CDMA-based cellular wireless standards such as IS-95 and WCDMA, a minimum SINR is required at the receiver so that a minimum data rate can be supported. Maintenance of such minimum SINR targets is well-justified for the voice service to achieve a certain desired BER for a given fixed rate. Given a desired threshold for user i, the corresponding SINR constraints can be expressed as

(8.3)

where denotes the set of users. Due to interference coupling among users, the capacity of the CDMA cellular network is limited by the interference. As a result, it may not be possible to support all SINR constraints in (8.3) even if each user has infinite power budget [6–8]. When these SINR constraints are feasible, Foschini and Miljanic have proposed an elegant distributed power control algorithm that converges to a fixed point where each user achieves his or her target SINR exactly [1,2]. The iterative power update in this Foschini–Miljanic algorithm is given as

(8.4)

where pi(t) and denote the transmission power and achieved SINR of user i in iteration t, respectively. In order to update transmission power in each iteration, each user only needs to obtain his or her own current SINR. Therefore, this power control algorithm is fully distributed, which converges very fast to a Pareto-optimal fixed point requiring the minimum power for each user. This algorithm is also referred to as TPC in the literature. Unfortunately, if the SINR constraints (8.3) are not feasible, then the power update (8.4) diverges to the infinite power without convergence. In addition, there is a maximum power constraint for each user in the UL transmission. Let Pi be the maximum UL power budget of user i. Then we have the following power-constrained TPC update rule:

(8.5)

It is known that this power-constrained TPC scheme always converges to an equilibrium for both feasible and infeasible systems. In addition, the transmission powers of some users will converge to their maximum powers in an infeasible system where their target SINRs may not be achieved. One important and interesting related problem here is to determine a minimum subset of users to be removed for an infeasible system so that the target SINRs of the remaining users can be supported. This problem is indeed NP-hard [6]; therefore, determining the set of users of minimum size to remove typically requires exponential computational complexity. To resolve this challenge, several heuristic user removal algorithms were proposed to solve this problem in the literature [6,8]. An elegant distributed Pareto-optimal user removal algorithm was proposed in [26], which was shown to be able to remove a minimum number of users distributively for an infeasible system.

In 1995, Roy Yates proposed an interesting framework to prove the convergence of any iterative power control algorithm of the form pi(t+1)=Ji(p(t)) where t represents the iteration index and Ji(p(t)) denotes the power update function for user i, which is a function of transmission powers of all users in the network. Let J(p(t)) be a vector whose ith element Ji(p(t)) be the power update function corresponding to user i. Yates showed that any such power control algorithm converges to a fixed point under both synchronous and asynchronous power updates if Ji(p(t)) is a standard function that satisfies the following properties.

• Positivity: .
• Monotonicity: If , then .
• Scalability: For all , .

The TPC strategy indeed satisfies these properties. Therefore, its convergence can be established by using the above result. In [16], Sung and Leung extended the Yates’s convergence framework where they showed that any power control algorithm whose power update function satisfies the more general two-sided scalability property converges.

In the works described above, a snapshot channel model is assumed to establish the convergence of the power control algorithms where channel gains are assumed to remain static during the power updates. Extensions of these convergence results to the varying channels have been performed under the stochastic power control framework in [27].

8.1.2 Power Control Design from Game Theoretic View

Game theory has been shown to be a useful tool in designing distributed power control algorithms. In particular, each user can determine his or her transmission power by acting as a player in a noncooperative game. One popular approach within this design framework is to allow each user to iteratively update his or her transmission power as the best response given the transmission powers of other users. There are some design aspects to consider for such a design approach. Firstly, the choice of payoff functions for users plays a central role since it governs the convergence behavior of the underlying power control strategy. Secondly, as the payoff function is given, then investigation of the convergence properties and characterization of possible fixed points are the key research tasks. Specifically, it is often of interest to study the existence and uniqueness of the Nash equilibrium for the game, the efficiency of the Nash equilibrium, and the convergence of the proposed power control strategy. Thirdly, the payoff function needs to be reverse engineered so that the underlying power control strategy can guarantee convergence to an efficient Nash equilibrium and can be easily implemented distributively.

It turns out that several existing power control algorithms can be indeed designed under this noncooperative game framework. Such a game theoretic design view can be illustrated by finding the corresponding payoff function of the underlying game. We describe some important power control algorithms in some detail in the following. Let us start by considering a noncooperative game where the payoff function chosen by each user i is

(8.6)

where represents the SINR of user i given in (8.2) and denotes the target SINR of user i. To find the best response for user i given the transmission powers of other users, we can set the derivative of with respect to pi equal to zero, which gives the necessary optimal condition. After some simple manipulations, we arrive at the following relationship

(8.7)

By using this relationship where the transmission powers in the left-hand side and the right high side correspond to iterations t+1 and t, respectively, we obtain the following iterative power control strategy

(8.8)

which is exactly the well-known TPC scheme presented before.

Consider another noncooperative game with the following payoff function

(8.9)

Again, by setting the derivative of with respect to pi equal to zero, we have following

(8.10)

where denotes the effective interference. From this relationship, we can obtain the following iterative power update strategy

(8.11)

where . This is indeed the OPC algorithm proposed by Leung and Sung in [17]. The more general payoff function of the form Utot,i=Ui(p)−Ci(p) can be chosen to design a power control game where Ui(p) and Ci(p) denote the utility and cost functions, respectively. For example, Ci(p) can represent pricing function that can balance between achievable utility and utilized radio resources. Such price-based power control design has been adopted in many existing works (e.g., see [11–13).

A distributed power control algorithm that realizes the best response typically converges to a Nash equilibrium of the underlying game. However, such a Nash equilibrium may not be the most efficient operating point for the network since there may exist other operating points that strictly dominate it. Achieving a non-dominated operating point may require a centralized power control strategy, which would not be desirable for practical large-scale networks [11]. Fortunately, it is possible to design Pareto-optimal power control algorithms using, for example, optimization theory, even though such algorithms usually require more signaling overhead (e.g., see [28–30]). In particular, distributed resource allocation algorithms can be devised to solve certain network utility maximization problems that can provide fairness among active users.

8.1.3 Joint Base Station Association and Power Control

In practice, users have to choose BSs to connect with in addition to performing power control to achieve the desired QoS in CDMA cellular networks. The BS association and power control tasks can be performed at different or the same time scales. Users can typically make BS association decisions based on some metrics such as channel gains or SINRs corresponding to potential BSs. When the average values of such metrics are employed, BS association decisions are less frequently made, which, therefore, require less signaling overhead, compared with the case where BS association and power control are updated at the same fast time scale.

One elegant dynamic algorithm in which BS association and power control tasks operate at the same time scale aiming to achieve minimum transmission powers was proposed in [18,19] for homogeneous cellular networks. This algorithm can be viewed as an extension of the Foschini–Miljanic power control algorithm where BS association decisions are integrated with the power updates. We describe this algorithm for the UL in the following. To proceed, let bi denote the BS that user i associates with and denote the channel gain from user j to the associated BS bi of user i. Then, the received SINR of user i can then be written as

(8.12)

Suppose each user i wishes to achieve a target SINR of . Then, the transmission power required by user i to achieve this target SINR when it is associated with BS k can be expressed as

(8.13)

where we explicitly indicate the dependence of the transmission power to the associated BS k. It was proposed in [18,19] that the BS association and transmission power are updated in each iteration as

(8.14)

(8.15)

where we neglect the iteration index for simplicity. In practice, each user only needs to choose one BS in a small set of nearby BSs to associate with. Therefore, this algorithm can be implemented in a distributed manner since each user is required to estimate the transmission powers to achieve his or her target SINR corresponding to potential BS associations in each iteration. This BS association and power control algorithm was shown to converge to a fixed point that achieves the target SINRs for all users with minimum transmission power whenever feasible [18,19]. Moreover, such convergence holds under both synchronous and asynchronous updates.

For data-oriented wireless networks, efficient utilization of radio resources to enhance the system throughput would be more relevant than achieving fixed target SINRs for active users. Moreover, for wireless HetNets, it is desirable to design flexible, decentralized BS association and resource allocation mechanisms that can effectively manage interference, provide QoS support for users of different tiers, and enable controllable data off-loading from macrocells to small cells. Therefore, lots of further efforts are needed to fulfill these design objectives.

8.2 GAME THEORETIC BASED POWER CONTROL FOR TWO-TIER CDMA HETNETS

Power control is the main mechanism for interference management and QoS provisioning in CDMA two-tier HetNets, where users of different tiers transmit on the same frequency band. For this kind of network, macro users typically have higher priority in accessing the spectrum; therefore, their minimum QoS performance must be protected against the CTI from the femto tier. Also, distributed power control algorithms with little overhead are desirable since the backhaul links based on wired broadband links such as DSL may have limited capacity. In this section, we demonstrate the design of such a power control algorithm by using a noncooperative game theory approach. Specifically, users in the two tiers will have different payoff functions and each user will iteratively play a so-called best-response strategy, which allows it to maximize its payoff given the current strategies (i.e., transmission power levels) chosen by other users.

We consider a two-tier wireless network where a macrocell serving Nm macro users is underlaid with J femtocells using CDMA. Assume that femtocell i has Ni users and define . The association of the femto users with their closest femto access points is fixed during the runtime of the underlying power and admission control processes. Denote the set of all users by and the set of macro and femto users by and , respectively. For simplicity, we describe the model in the UL scenario even though it is applicable for the DL as well. We consider a snapshot model where the channel gains are assumed to remain unchanged during the runtime of the power and admission control algorithms. Then, the received SINR of user is also given in (8.2) where the first term in the denominator of (8.2) includes both co-tier interference and CTI, that is, aggregated interference from all macro and femto users except the considered user i (which can be either a macro or femto user). We assume that the prioritized macro user requires that for a given desired threshold in order to have his or her ongoing operation robustly protected.

We can employ a utility function and a cost function Ci(pi) to represent the degree of satisfaction of user to the service quality and the cost incurred, respectively. It is the interest of user to maximize his or her own net utility, defined as

(8.16)

In fact, (8.16) is a standard way to define the payoff function for network entities (i.e., wireless users and BSs). Given the transmission powers of other users, such an optimization can be accomplished by dynamic power adaptation performed at individual links.

Assume that is a strictly concave function with respect to pi, whereas C(pi) is convex in that same variable. The necessary condition for maximization of (8.16) can be obtained by taking the derivative of Utot,i, which is also strictly concave in pi, and equating to zero as

(8.17)

Upon noting that , we have

(8.18)

where is the total noise and interference power at the receiving side of user . From (8.18), the optimal target SINR can be derived as

(8.19)

where . By choosing the transmission power satisfying (8.19), user i plays the so-called best response strategy according to the noncooperative game theory. Under such a design, the following iterative power update rule is employed [4]:

(8.20)

where is the actual SINR of user i at iteration t. In fact, (8.20) represents a more general power-control rule compared with the well-known Foschini–Miljanic power update strategy given in (8.4). Specifically, the minimum required SINR on the right-hand side of (8.4) is replaced by an adaptive SINR threshold in (8.19).

In what follows, we will show how to choose appropriate functions and Ci(pi), together with their operating parameters, to design efficient distributed power and admission control algorithms for both macro users and femto users. The key aspect that makes the existing algorithms (such as those in [6,7]) unsuitable for our current purpose is that the minimum SINRs of the prioritized macro users should be maintained all the times. Accordingly, the transmission powers of newly deployed femto users must be properly controlled or, if needed, may even be removed for the sake of protecting the macro users.

8.2.1 Guaranteeing QoS for Macro Users

The work in [4] recommends the use of a sigmoid utility function and a linear cost function. For the current design, by employing similar utility and cost functions for the macro users and via properly tuning their control parameters, we can develop an efficient and robust power control algorithm that is capable of maintaining the minimum SINR requirements for these users. Specifically, we select the following utility and cost functions for a macro user :

(8.21)

(8.22)

Here, bi and ci, respectively, control the steepness and the center of the sigmoid function, whereas a(m)i is the pricing coefficient.

The function in (8.21) naturally captures the value of the service offered to user i. Upon noting that Ui(0)=0, and that is increasing with respect to , it is clear that user i is more and more satisfied with the offered service as the quality, expressed in terms of the achieved SINR , improves. On the other hand, power is itself a valuable system resource. The linear cost in (8.22) is chosen to reflect the expenses of power consumption to the user, while still retaining the simplicity of subsequent analysis. As shown later, the use of dynamic values of a(m)i may significantly affect the resulting equilibrium of the developed algorithms.

Importantly enough, the choice of sigmoid function allows for the design of efficient schemes that guarantee the minimum SINRs imposed by the macro users. Using (8.21) and (8.22), the expression in (8.18) can be rewritten as

(8.23)

From this relationship, it is straightforward to see that the optimal SINR target is

(8.24)

With the utility function defined in (8.21), an analytical form of (8.24) can be obtained as follows [4]:

(8.25)

Now, the line that goes through the origin and is tangent to the utility curve can be expressed as . At the tangent point , it is clear that

(8.26)

Since the cost function in (8.22) can also be rewritten as , it is required that for a nonnegative total utility as shown in Figure 8.1. On the other hand, the necessary and sufficient condition for in (8.25) to achieve is ; otherwise, macro user i simply suppresses his or her transmission and still gains zero total payoff. Therefore, by setting

(8.27)

we can ensure that any active macro user (i.e., whose transmission power is strictly positive) will attain his or her minimum SINR target. In other words, an active macro user i will eventually achieve SINR under this design. Figure 8.2 illustrates this parameter setting and the achievable SINR at the equilibrium. Some manipulations of (8.26) and (8.27) give [4]

(8.28)

Upon substituting this value of ci to (8.25), we finally arrive at

(8.29)

In Figure 8.2, we show the operating range of an active macro user i. With a sufficiently large bi, function becomes very steep; therefore, the resulting of user i will be very close to its SINR threshold . Also clear from Figure 8.2 is that if the minimum required SINRs of all the macro users are feasible, we can make them all active by setting a(m)i sufficiently small. Specifically, given its total received interference and noise power Ii, macro user is active if

(8.30)

We will propose a design example of the utility and cost functions for femto users and the corresponding power and admission control algorithm in the following.

8.2.2 Power Adaptation and Admission Control Algorithm

Given the macro users’ QoS requirements already supported, the specific choice of utility and cost functions for femto users allows us to achieve our design objectives, through which certain user satisfaction metrics can be attained. Notice that if the femto users also wish to maintain their respective QoS requirements, the operation of these users may cause network congestion, hence badly affecting the performance of the macro users. In such cases, the femto users should be penalized by appropriately regulating their operating parameters. We will describe one design example for the femto users. In particular, we will propose a joint power adaptation and admission control algorithm and establish its convergence condition.

Suppose that femto user also requires a minimum SINR to maintain the quality of its applications. While a higher SINR at the receiving end of any femto links implies more reliability and better services, this usually requires more transmission power, which in turn leads to a higher cross-interference induced to the macrocell. Such an observation motivates us to consider the following net utility for femto user i (similar to that in [5]):

(8.31)

Although maximizing the first term on the right-hand side of the above equation, that is, the utility , enforces the SINR of femto user i to be as close as possible to the SINR target , the resulting at the equilibrium may actually be less than . Nevertheless, it has been shown in [5] that by allowing a reasonable deviation from the target SINR, a significant reduction in the transmission power (and hence the resulting interference) can be achieved. Given its lower access priority, this type of soft QoS provisioning is totally acceptable for femto user i. On the other hand, the cost function, Ci(pi)=a(f)ipi, penalizes the expenditure of transmission power, which potentially creates undue interference to the macrocell as well as other femto users. Here, a(f)i is the pricing coefficient of such penalization.

Algorithm 8.1   POWER AND ADMISSION CONTROL ALGORITHM

Now, applying the result in (8.18) to these particular utility and cost functions yields:

(8.32)

Because is a concave function in pi, so is . The power value that globally maximizes Utot,i can thus be computed as

(8.33)

Based upon the power update rule in (8.33), a joint power adaptation and admission control algorithm is now developed that is capable of providing soft QoS for the femto users. In this algorithm, we gradually increase pricing coefficients a(f)i of all active femto users when there exists an active macro user with “soft” SINR target below the required SINR target (i.e., ). This algorithm lends itself to a distributed implementation since each user i only needs to estimate (i) its received interference power Ii(t) and (ii) its own channel gain hi,i(t) in order to update its transmission power in each iteration. In step 12 of the proposed algorithm, if a particular femto user j has his/her SINR falling below the minimum required threshold , it is removed with a small probability α at most once in every T(f) iterations. This conservative user removal scheme is employed to avoid eliminating too many femto users unnecessarily.

Theorem 8.1.Assume that xf−1i(x) is an increasing function, , the proposed algorithm converges to an equilibrium, at which point

(8.34)

(8.35)

Moreover, all active macro users have their SINR satisfying .

Proof: The convergence of the proposed power updates in this case can be proved using the standard function technique [3]. For the macro users, [4] maintains that is a standard function if xf−1i(x) is an increasing function where Ai(p(t)) denotes the corresponding power update function for macro user i. Indeed, this is true if bi is chosen to be sufficiently large.

For the femto users, it has been shown in [5] that the power updates for such users [see (8.33)] satisfy the requirements of a standard function if the following conditions hold for all :

(8.36)

(8.37)

Indeed, conditions in (8.36) and (8.37) can be enforced by the admission control mechanism in the proposed algorithm. If the network is congested enough, the transmission powers of certain users will diverge to some large values, creating a large amount of interference Ii(t) to other users. Note that the power update for satisfies . Therefore, if Ii(t) is sufficiently large so that , femto user i will be removed, which in turn relieves the network congestion. Together with the proper tuning of pricing coefficient a(f)i, (8.36) and (8.37) are eventually satisfied.

Since the power updates of both the macro users and the femto users are standard functions, Algorithm 8.1 converges to an equilibrium. In addition, all active macro users at that equilibrium must also have their SINR .     

Readers can refer to [31] for another design with a different femto payoff function that achieves an efficient femto throughput-power trade-off. In general, the Nash equilibrium achieved by the underlying power control game may not be efficient [11]. However, power control algorithms designed by using the game theoretic approach usually require very low signaling overhead and they can be implemented efficiently in a distributed manner. We will present an alternative Pareto-optimal power control algorithm by using optimization theory in Section 8.4 of this chapter.

8.2.3 Numerical Examples

We present numerical results to illustrate the convergence and performance of the aforementioned power and admission control algorithm. The network setting and user placement in our examples are shown in Figure 8.3, where macro and femto users are randomly deployed inside circles of radii of 500 m and 100 m, respectively. Also, it is assumed that the number of users serviced by individual femto access points is identical. For each network realization, channel gains from the transmitter of user j to the receiver of user i are calculated as d−3ij with dij being their corresponding geographical distance. In addition, other system parameters are chosen as follows: processing gain, PG=100; power of Gaussian noise, ; and in the sigmoid utility function of macro users.

The pricing coefficients of all macro users are set equal to in all simulation results. Moreover, the same initial pricing coefficients a(f)j and scaling parameters k(f)j (denoted as kf in the corresponding figures) are selected for all femto users. The values of SINR targets for macro and for femto users can be found in the caption of every plot. The results presented in each figure correspond to one particular network realization, chosen with the intention to demonstrate certain features of the proposed algorithms.

In Figures 8.4 and 8.5, we display the evolutions of SINRs for all users in the low- and high-load scenarios, respectively. In particular, these figures confirm that the presented algorithm actually converges wherein the SINR requirements of all macro users are met at the equilibrium. Also, the convergence speed appears to be slower when the network becomes more congested. In both scenarios, the algorithm enables macro users to just utilize the right fraction of network capacity to meet their own QoS requirements, leaving the leftover to be shared by femto users. Additionally, Figure 8.4 shows that in the lowly loaded regime, the achieved SINRs of femto users are slightly below their corresponding requirements while performance of all macro users is well protected. When network congestion starts building up, the algorithm smoothly reduces the SINRs of femto users so that macro users can eventually reach their desired SINR targets as can be observed in Figure 8.5. These results confirm that the presented algorithm is able to offer QoS support for femto users to the extent that network capacity allows.

8.3 JOINT BASE STATION ASSOCIATION AND POWER CONTROL FOR CDMA HETNETS

In the multi-tier HetNets, efficient design of BS association and power control algorithms plays a crucial role in achieving desirable QoS and load balancing for users of different tiers. In addition, such design can be deployed to control the desirable level of data off-loading from macro tier to the high-capacity femto tier in two-tier HetNets. It is also the key in developing an open or hybrid access strategy for two-tier macro–femto HetNets based on which macro users can choose one macro base station or femto access point to associate with.

In this section, we consider the joint BS association and power control problem for the UL of a CDMA-based two-tier HetNet. We assume that there are N users, labeled as , transmitting information to M BSs, labeled as , on the same spectrum. The sets of all users and BSs are denoted by and , respectively. Each of these BSs can belong to one of the available cell types (e.g., macrocells, microcells, picocells, and femtocells) in a heterogeneous cellular network. One particular case of interest is the two-tier macro–femto cellular network where and where , denote the sets of macro users and femto users, respectively and , denote the sets of macro base stations and femto access points, respectively. We will consider the general scenario in this section. Assume that each user i communicates with only one BS at any time, which is denoted as . However, users can change their associated BSs over time. Note that if , then users i and j are associated with the same BS. Let Di be the set of BSs that user i can be associated with, which are nearby BSs of user i in practice. Note that we have and . We are interested in developing a base station association (BSA) strategy, which determines how each user i will choose one BS to communicate with based on the channel state information and interference.

Let the transmission power of user i be pi, whose maximum value is Pi, that is, . We arrange transmission powers of all users in a vector, which is denoted as . Let hi,j be the channel power gain from user j to BS , and be the noise power at BS . Then, the SINR of user i at BS bi can be written as

(8.38)

where, for simplicity, we absorb the processing gain PG into as before. Ri(p, bi) is the effective interference of user i, which is defined as

(8.39)

where Ri(p, k) is the effective interference experienced by user i at BS . We will also write Ri(p) instead of Ri(p, bi) when there is no confusion. Suppose that each user i requires the minimum QoS in terms of a target SINR , which is expressed as

(8.40)

Our design objective is to develop distributed joint BSA and power control algorithms that can maintain the SINR requirements in (8.40) (whenever possible) while exploiting the multiuser diversity gain to increase the system throughput. Moreover, we aim to achieve these design objectives for a heterogeneous wireless environment where there are different kinds of users with differentiated QoS targets (e.g., voice and data users) and potentially different cell types (e.g., macrocells, microcells, picocells, and femtocells). In particular, voice users would typically require some fixed target SINR while data users would seek to achieve a higher target SINR for broadband multimedia applications.

8.3.1 Base Station Association and Power Control Algorithm

We develop a general minimum effective interference BSA and power control algorithm and establish its convergence. Specifically, we will focus on a general iterative power control algorithm where each user i in the network performs the following power update pi(t+1)=Ji(p(t)) where t denotes the iteration index and is the power update function (p.u.f.). In fact, according to Sung and Leung [16,17], this kind of iterative power control algorithm converges if its corresponding p.u.f. is a two-sided scalable (2.s.s.) function, which is indeed a more general technique than the standard function approach proposed by Yates in [3]. The challenges involved in designing such a power control algorithm include the following. We have to ensure its p.u.f. is two-sided scalable; it fulfills our design objectives for the heterogeneous cellular network; and it can be implemented in a distributed manner. In addition, we seek to design a power control algorithm that can be integrated with an efficient BSA mechanism. Toward this end, we give the definition of a two-sided scalable function in the following.

Definition 8.1. A p.u.f. is 2.s.s. with respect to p if, for all a>1 and any power vector satisfying , we have

(8.41)

We will consider a joint BSA and power control algorithm where the p.u.f. of the power control scheme satisfies the 2.s.s. property stated in Definition 8.1. Under this design, each user chooses his or her “best” BS and updates its transmission power in the distributed manner. Specifically, the proposed algorithm is described in the following where each user chooses the BS that results in minimum effective interference and updates its power by using a 2.s.s. p.u.f. , where . The proposed algorithm can be implemented distributively with any distributed power control algorithm. To realize the BSA, each user needs to estimate the effective interference levels for different nearby BSs of interest. Then, each user i can choose one BS k in Di with minimum value of Ri(p, k). This algorithm ensures that each user experiences low effective interference and therefore high throughput at convergence.

Algorithm 8.2   Base Station Association and Power Control Algorithm

(8.42)

(8.43)

(8.44)

(8.45)

(8.46)

Note that we have expressed the p.u.f.s with respect to both p and R(p). For the expression with respect to R(p), the ith element of the p.u.f. is denoted as where Ri(p) is the effective interference experienced by user i given in (8.39). Therefore, we have , which depends on both the transmission powers of all users and the BS that each user is associated with. We establish the convergence of this algorithm in the following by utilizing the 2.s.s. function approach. Toward this end, we recall the convergence result for any power control algorithm that employs a bounded 2.s.s. p.u.f. in the following lemma, which was proved in [16].

Lemma 8.1 Assume that J(p) is a 2.s.s. function, whose elements Ji(p) are bounded by zero and Pi, that is, . Consider the iterative power update where t denotes the iteration index. Then, we have the following results.

We are now ready to state one important result for the joint BSA and power control operations described in the proposed algorithm in the following theorem.

Theorem 8.2 Assume J(p) and are arbitrary 2.s.s. p.u.f.s with respect to p and R(p), respectively. Then, the proposed BSA and power control algorithm converges to an equilibrium.

Proof: According to Lemma 8.1, a power control algorithm converges if the corresponding p.u.f. is 2.s.s. Hence, we can prove Theorem 8.2 by showing that the p.u.f. is a 2.s.s. function with respect to p, where and

(8.47)

Recall that we have assumed is 2.s.s. with respect to R(p) and . Therefore, is a 2.s.s. function with respect to . Consequently, the theorem is proved if we can show that the following statement holds. If , then we have

(8.48)

We will prove (8.48) by contradiction. Let bi and be the BSs chosen by user i corresponding to and , respectively. From our assumption for a>1, we have . Performing some simple manipulations, we can obtain

(8.49)

Now suppose that (8.48) is not satisfied for . Then, we must have or . Let us consider these possible cases in the following.

• If , then using the results in (8.49),

  we have

  (8.50)

• Similarly, if , then using the results in (8.49),

  we have

  (8.51)

Both (8.50) and (8.51) indeed result in contradiction to the definition of and , which is given in (8.44). Hence, we have if , which completes the proof of the theorem.     

The result in this theorem implies that if the p.u.f.s J(p) and are 2.s.s., then the BSA strategy described in (8.43) and (8.44) results in a composite 2.s.s. p.u.f., which corresponds to the proposed joint BSA and power control operation. In other words, the proposed BSA scheme preserves the 2.s.s. property of the employed p.u.f.s J(p).

8.3.2 Hybrid Power Control Algorithm

To complete the design for the proposed joint BSA and power control framework, we need to develop a distributed power control strategy, which is employed in (8.46). In general, the performance of a power control algorithm depends on how we design the corresponding 2.s.s. p.u.f. J(p). We will conduct such design by using game theory in the following.

8.3.2.1 Game-Theoretic Formulation

We define a following power control game.

• Players: The set of mobile users .
• Strategies: Each user i chooses transmission power in the set [0, Pi].
• Payoffs: User i is interested in maximizing the following payoff function

(8.52)

where denotes the target SINR for user i. x is a special parameter whose desirable value will be revealed later. and are nonnegative control parameters, that is, , which will be adaptively adjusted to achieve our design objectives.

This game-theoretic formulation arises naturally in the considered heterogeneous wireless network, where mobile users tend to be selfish and only interested in maximizing their own benefits. Using this formulation, we will develop an iterative power control algorithm in which each user maximizes his or her own payoff in each iteration given the chosen power levels from other users in the previous iteration (i.e., each user plays the best response strategy). To devise such an algorithm, each user i chooses the power level, which is obtained by setting the first derivative of the underlying user’s payoff function to zero.

In fact, by maximizing the payoff function given in (8.52), each user i strikes a balance between achieving the SINR target and exploiting its potential favorable channel condition to increase its SINR. In particular, by maximizing , each user i attempts to reach his or her target SINR . Moreover, it can be shown that the best response strategies achieved by maximizing the first term and maximizing are the same, for and 0<x<1, where represents the pricing coefficient of user i. Also, the best-response-based power control scheme with payoff function for x=1/2 is the well-known OPC algorithm [16,17]. In addition, if each user i plays the best-response strategies using Ui(p), where , then we obtain the well-known Foschini–Miljanic TPC algorithm [1]. Therefore, our chosen payoff function in (8.52) aims to design a HPC strategy that exploits the advantages of both OPC and TPC algorithms.

Proposed HPC Algorithm. We are now ready to develop a HPC algorithm corresponding to the payoff function in (8.52). Specifically, we can obtain the power update rule for the HPC algorithm according to the best-response strategy of the underlying payoff function. After some manipulations, we can obtain the following best response under the chosen payoff function (8.52):

(8.53)

Considering the maximum power constraints, the HPC algorithm employs the following iterative power update:

(8.54)

where t denotes the iteration index and IHi(p) is given in (8.53). Here, parameters control the desirable performance of the proposed HPC algorithm. Specifically, by setting , user i actually employs the standard Foschini–Milijanic TPC algorithm to achieve its target SINR while if , user i attempts to achieve a higher SINR.

It can be observed that each user i only needs to calculate or estimate the effective interference Ri(p) to update its power in the proposed HPC algorithm. User i can fulfill this if he or she has information about the total interference and noise power (i.e., the denominator of (8.38)) and the channel power gain according to SINR expression in (8.38), since the current transmission power level pi is readily available. In addition, the channel power gains can be estimated by the BS and sent back to each user by using the pilot signal and any standard channel estimation technique [32]. Moreover, the total interference and noise power for each user can be estimated as follows. Each BS estimates the total receiving power and then broadcasts this value to its connected users. Each user i can calculate the total interference and noise power by subtracting his or her received signal power (i.e., ) from the total receiving power broadcast by the BS. Therefore, calculation of the effective interference only requires the standard channel estimation of and estimation of the total receiving power at the BS. The estimation of the effective interference Ri(p) and, therefore, the proposed power control algorithm given in (8.54) can be implemented in a distributed fashion.

Convergence of HPC Algorithm. We establish the convergence condition for the proposed HPC algorithm by using the “two-sided scalable function” approach given in Definition 8.1. We state a sufficient condition under which the p.u.f. JH(p) in (8.54) is 2.s.s. in the following theorem.

Theorem 8.3 If the parameter x of functions IHi(p) given in (8.53) satisfies , then the p.u.f. JHi(p) given in (8.54) is 2.s.s. Also, the proposed HPC algorithm in (8.54) converges to the Nash equilibrium of the underlying power control game.

Proof: The convergence of the proposed HPC algorithm follows immediately from the results of Lemma 8.1 if we can prove that its p.u.f. . JHN(p)] in (8.54) is 2.s.s. with respect to p. In addition, the resulting equilibrium (i.e., the power vector at convergence) is the Nash equilibrium of the power control game defined in Section 8.3.2.1 since users play the best-response strategy. The detailed proof that JH(p) is 2.s.s. is available in [33].     

The proposed HPC scheme will be employed in the proposed algorithm presented in Section 8.3.1. Note, however, that this proposed HPC scheme can be used as a stand-alone power control algorithm.

8.3.3 Hybrid Power Control Adaptation Algorithm

The equilibrium achieved at convergence by the proposed BSA and power control algorithm depends on several design parameters, namely and for . In what follows, we develop decentralized mechanisms to adjust these parameters so that target SINRs of all users can be achieved whenever possible while attempting to achieve higher SINRs, and therefore, higher system throughput. The proposed adaptive mechanism comprises two updating operations in two different time scales, i.e., running the joint BSA and HPC algorithm to achieve the Nash equilibrium point in the small time scale and updating and for all users to achieve a more desirable Nash equilibrium in the large time scale. Let and be the sets of α and ξ parameters of all users in p.u.f. of the HPC scheme, respectively.

As discussed before, the TPC scheme is a special case of the proposed HPC scheme with for . It is known that the TPC scheme is able to support all the users’ target SINRs expressed in (8.40), as long as the system is feasible (i.e., the SINR requirements in (8.40) can be supported) [8]. However, the TPC scheme fails to achieve high system throughput when the system is feasible and lightly loaded. In addition, the TPC scheme may not be able to support the largest possible number of users when the system is infeasible. Our objective is to develop an adaptive strategy for the proposed HPC algorithm to overcome these limitations of the TPC scheme.

Toward this end, if user i is a voice user who is only interested in maintaining his or her target SINR , then we can simply set in (8.52). For each data user i, we will fix while adaptively updating power and in two different time scales to achieve the design objectives. Specifically, each data user i will run the HPC and BSA algorithms for a given until convergence (i.e., in the small time scale). Then it updates accordingly (i.e., in the large time scale). Now, it can be verified that the best response corresponding to payoff function can be written as

(8.55)

where . To set the value for , suppose that data user i would need to use his or her maximum power Pi to reach the target SINR . Then, the value of can be found by using the result in (8.55) as follows.

(8.56)

where we have substituted to (8.55). We now describe how to update in Δ. In the HPC scheme, the p.u.f. depends on the effective interference Ri(p) and the value of . Let denote the power vector at convergence, which is obtained by running the proposed HPC algorithm for a particular vector α. We illustrate the relationship between and in Figure 8.6 where is a threshold value for the effective interference of user i. We state the relationship between , , and in the following lemma whose proof is available in [33].

Lemma 8.2 Assume that and . Then, we have

It can be seen from Figure 8.6 that if , the HPC curves become closer to the TPC curve as decreases whereas HPC curves become closer to the TPC curve as increases if . This is because IHi(p) in the p.u.f. of the proposed HPC scheme is a weighted sum of those in the TPC and OPC schemes. Recall that our design objectives are to satisfy the SINR requirements for all users expressed in (8.40) (whenever possible) while enhancing the system throughput. Let user i be a supported user (nonsupported user) if his or her SINR is greater than (less than) his or her target SINR, which occurs as his or her effective interference is less (greater) than the threshold , respectively. Note that a supported user i will have his or her SINR greater than the target SINR if . We refer to such a supported user as a potential user in the following. In fact, any potential user i can reduce his or her transmission power to enhance the SINRs of other users (since this reduces the effective interference experienced by other users) as being implied by the results in Lemma 8.2. Therefore, by adjusting , each user i can vary his or her SINR and assist other users in improving their SINRs.

Algorithm 8.3    HYBRID POWER CONTROL ADAPTATION ALGORITHM

We exploit this fact to develop the HPC adaptation algorithm, which is described in the algorithm presented in Section 8.3.3. Let and be the sets of supported and nonsupported users in iteration l, respectively. We use to keep the number of supported users during the course of the algorithm. In each iteration, each user i will run the proposed HPC algorithm and slowly update based on the achieved equilibrium. All data users i initially set to be a sufficiently large value so that we reach the first equilibrium that favors strong users. For each nonsupported user i, we maintain its parameter to be the same to keep its power updating process stable. In addition, user i can save his or her parameter at the instant when the number of nonsupported users decreases and reload this value later as the global update process terminates (in step 4). In addition, design of the “updating process” can be done so that the parameters of supported users are slowly decreased to zero if all nonsupported users cannot be assisted to achieve their target SINRs.

The proposed HPC adaptation algorithm can achieve desirable performance, which is described in the following. Let and be the number of supported users due to the proposed HPC adaptation algorithm and the TPC algorithm, respectively. Then, we have . Also, if the network is feasible (i.e., all SINR requirements can be fulfilled by the TPC algorithm), then all users achieve their target SINRs by using HPC algorithm. Also, there exists feasible users who achieve SINRs higher than the target values under the HPC algorithm. The proofs of these results are given in [33]. This theorem implies that the proposed HPC algorithm achieves better performance than the traditional TPC algorithm for both infeasible and feasible systems. Specifically, the HPC algorithm can support at least the same number of users while it can achieve higher SINRs and therefore higher total throughput than that from the TPC algorithm.

8.3.4 Application to Two-Tier Macrocell–Femtocell Networks

The proposed distributed HPC algorithm can be applied to the two-tier macro–femto network. For the two-tier network using open or hybrid access, macro users are allowed to connect to nearby femto access points to enhance their performance and to reduce the interference to other users in the network. However, macro users’ connections to a particular femto access point without an appropriate control may significantly degrade the throughput of femto users in the underlying femtocell, which would not be desirable. To resolve this issue, we assume that each femto user i has two target SINRs, for example, and where . Femto users can attempt to reach the higher target SINRs as long as the network condition allows. Otherwise, they seek to maintain at least the lower target SINRs when it is possible.

Each femto user i can adaptively track the higher target SINR by taking the following procedure. It employs the proposed HPC algorithm to achieve the lower target SINR in the first phase. If this is successfully fulfilled, it attempts to achieve the higher target SINR in the second phase. To achieve this objective, femto user i simply sets parameters and by using the higher target SINR . Then, it runs the proposed HPC algorithm again. As femto users at a particular femtocell attempt to achieve higher target SINR, the macro users associated with the underlying femtocell have to decrease their transmission powers and therefore achieve lower SINRs. Hence, the proposed HPC algorithm enables us to attain flexible spectrum sharing between femto users and macro users at each femtocell.

8.3.5 Numerical Examples

We present illustrative numerical results to demonstrate the performance of the proposed algorithms. The network setting and user placement for our simulations are illustrated in Figure 8.7, where macro users and femto users are randomly located inside circles of radii of r1=1000 m and r2=50 m, respectively. Assume that there are heavy walls at the boundaries of the femtocells. We fix Nm=10 and randomly choose the number of femto users in each femtocell from one to three. Then, eight users of either tier are set as voice users randomly. The channel power gain hij is chosen according to 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 macro base station and femto access points, respectively. C=20, fc=2.5 GHz. Wl is the wall-loss value. nij is the number of walls between BS i and user j. Other parameters are set as follows (unless stated otherwise): x=0.5; processing gain, PG=128; maximum power, noise power , . We set nij equal to the number of cell boundaries that the corresponding signal traverses and the wall-loss value Wl=12dB. The SINRs presented in all figures are in linear scale except that those in Figure 8.10 are in dB scale.

Figure 8.8 shows the convergence of the HPC algorithm when we set for all users. This figures confirms that HPC algorithm converges to an equilibrium for which some users exactly achieve their target SINRs while others attain SINRs higher than their target values. This set of results corresponds to the feasible system where all SINR requirements can be supported. This figure also shows that the proposed HPC algorithm not only attains all SINR requirements but also enables strong users to achieve high throughput performance.

Figure 8.9 illustrates the average spectral efficiency achieved by different schemes versus the target SINR. Here, the spectral efficiency of user i is calculated as (b/s/Hz). To obtain the results, we randomly generate user locations and obtain results for this fixed topology. We sequentially add more femto users to obtain different points on each curve. For reference, we also present the average spectral efficiency of a TPC max–min scheme in which we slowly increase the target SINR for all users as long as the system is still feasible under the TPC scheme (this scheme is denoted as TPC max–min). As this figure demonstrates, our HPC algorithm attains higher average spectral efficiency than those of both traditional TPC and TPC max–min schemes but lower than that of the OPC algorithm. In particular, when the network is lowly loaded (), our proposed algorithm attains much higher spectral efficiency than those of the traditional TPC and TPC max–min schemes. Moreover, when the network load is higher (), the gaps between our proposed algorithm and the two TPC schemes become smaller. This is because the HPC algorithm attempts to maintain the target SINRs for all users as the TPC schemes.

Figure 8.10 illustrates the number of supported users for different schemes. It can be seen that our proposed HPC algorithm can maintain the SINR requirements for the larger number of users compared with TPC and OPC algorithms. In particular, our proposed algorithm can support roughly the same number of users as the TPC algorithm for low target SINRs. However, our proposed algorithm performs better than the TPC scheme for higher target SINRs. In fact, almost all users utilize the maximum power under the TPC scheme at high target SINRs, which prevent all of them from achieving their target SINRs. On the other hand, in our proposed scheme, nonsupported users tend to use as small transmission power as possible (i.e., high values of ). This enables more users to attain their target SINRs. The figure also shows that the proposed HPC algorithm performs better than the OPC scheme for all values of the target SINR.

8.4 DISTRIBUTED PARETO-OPTIMAL POWER CONTROL FOR TWO-TIER CDMA HETNETS

Resource allocation algorithms developed by using the game theory approach such as those presented in the previous sections may not be efficient in general since the achieved Nash equilibrium may not optimally utilize the radio resources. In fact, distributed optimal resource allocation algorithms can be designed by using optimization theory. Moreover, such design can enable us to achieve fair resource sharing under different fairness criteria by maximizing some particular utility function, for example, the α-fair utility function proposed in [34]. We demonstrate the optimal power control design for two-tier CDMA HetNets in this section where the proposed distributed power control algorithm allows macro users to achieve their target SINRs while enabling femto users to share the leftover capacity in a fair and Pareto-optimal manner. This design is motivated and based on the results in [28], which was originally proposed for homogeneous cellular networks.

We again consider the UL transmissions in a two-tier wireless network, in which Nm macro users establish communication links to its servicing macro base station while Nf femto users also transmit to their respective femto access points. We assume that all the macro users and femto users share the same radio frequency band by CDMA. The closed access mode is considered where the macro users are not permitted to connect to any femto access point. Also the association of any user with his or her own BS is fixed during the runtime of the underlying power control. Without loss of generality, denote the sets of macro users and femto users by and , respectively. The set of all users is then simply whose cardinality is N=Nf+Nm. It is assumed here that the time scale of network topology changes is negligible compared with that of power adaptation.

Denote by bi the serving BS of user , which is either a macro user or a femto user. For brevity, the path between user i and its servicing BS bi shall be referred to as link i. Also, let hk,j be the absolute channel gain from user j to BS k, and define its corresponding normalization as . To represent the normalized channel gain from user j to the serving BS bi of user i, we define an channel matrix H whose (i, j)th entry is

(8.57)

Suppose that user j transmits to his or her serving BS bj, and let be the received power at bj by that transmission. Since is the channel gain from user j to BS bj, it is clear that user j must have transmitted at a power level . At any BS k, this signal appears with a power . The transmission of other user j results in an interference power of to link i. The total interference plus noise at BS bi that serves user on link i can be expressed as

(8.58)

where is the noise power at the receiving end of link i. We assume that . In a matrix form, (8.58) can also be written as

(8.59)

where p and q are vectors whose ith elements are and qi, respectively. Let denote the SINR at link , where PG is the system processing gain. For notational convenience, we define the normalized SINR at link i as . It is then easy to see that

(8.60)

where . By substituting (8.60) to (8.59) and after some simple algebra, we obtain the following [28]:

(8.61)

(8.62)

Since we do not consider totally isolated groups of links that are not interacting with each other, it is practical to assume that both matrices and are primitive.1

Our goal is to devise a jointly optimal power allocation p and SINR assignment for the two types of users (i.e., macro users and femto users) with different service priorities and design objectives. The prioritized macro users with higher access rights demand that their ongoing services be, at least, unaffected regardless of any femtocell deployment. A set of minimum SINRs prescribed by the macro users must therefore be supported in the first place, i.e.,

(8.63)

where is the normalized target SINR corresponding to the actual SINR required by macro user i. Note that a general QoS can be translated to different specific requirements. For instance, a higher value of means that a higher throughput, a lower BER, and a shorter time delay are guaranteed for macro user i.

Our design objective is to maximize the sum utility of all femto users. The utility function (which is typically an increasing function) represents the value that femto user , who is assigned with SINR , contributes to the overall network. The higher the SINR, the greater the contribution. Depending on the type of utility functions, fairness, an important system-wide objective, can also be achieved. Proportional fairness and max–min fairness are among the most common metrics used in practice to characterize how competing users share system resources. The α-fair function proposed by [34] provides a useful means to enforce these two types of fairness, in that it generalizes proportional fairness and includes arbitrarily close approximations of max–min fairness. Specifically, we consider the following utility for femto user :

(8.64)

Here, corresponds to proportional fairness whereas gives max–min fairness.

Let denote the spectral radius of matrix X, that is, the maximum modulus eigenvalue of X. Given channel matrix H, the specific value of indicates whether a certain SINR is supportable or not. In particular, it is required by [2] that for the existence of a feasible power vector . In the limit , an infinite amount of transmission power would be needed to attain . For , the network can be regarded so congested that only removing certain users and/or lowering the SINR targets can help relieve such congestion. Considering a practical non-congested network with attainable target SINRs, we insist that where , for the existence of a feasible solution with .

Given , we are interested in the following problem:

(8.65)

It can be shown that a larger value of corresponds to a larger feasible set, and in turn a potentially higher utility. Therefore, it is desirable to choose to be as close to 1 as possible while ensuring that be supportable.

The problem in (8.65) is not convex because the set is not convex. However, if we let , then its equivalence is actually a convex set [36]. Through such a change of variable and upon denoting , the following equivalent problem of (8.65) is considered instead:

(8.66)

In this case, the utility function becomes

(8.67)

which is increasing, twice-differentiable, and concave with respect to . The problem in (8.66) is a convex optimization program. However, due to the complicated coupling in the feasible region, centralized algorithms are typically needed to resolve this kind of problem. Given the nature of two-tier networks where central coordination and processing are usually inaccessible, we aim at developing optimal solutions that can be distributively implemented by individual users.

8.4.1 Distributed Pareto-Optimal SINR Assignment

We perform the following matrix and vector partitions: ; and

(8.68)

where ; and .

proposition8.1 The optimal solution of (8.66) lies on the following boundary:

(8.69)

Proof: Suppose that at optimality, there is some such that . Since , one can reduce to have without violating the constraint. On the other hand, such a reduction in power leads to a lesser amount of interference perceived by all the femto users. Due to the monotonic property, this implies an increase in , and hence contradicts the assumption of optimality. Therefore, holds. Moreover, it can be proved that at the optimum. This completes the proof.     

Proposition 8.1 implies that the search space for Pareto-optimal SINRs in this case is reduced to simply . To unveil the complicated coupling between and in the relation , the following result is now in order.

Proposition 8.2 Suppose that we are operating on and that . Then, holds, where F is a positive matrix defined as

(8.70)

Proof: Let s be the left eigenvector of with associated eigenvalue . Therefore, , which can also be explicitly expressed as

(8.71)

where and .

By [35, Th. 5.6.9 and Cor. 5.6.16], the assumption ensures that exists and is positive componentwise. After some algebraic manipulations, one arrives at

(8.72)

With F defined in (8.70), the left-hand side of (8.72) is actually . This implies that is also an eigenvalue of . Since is primitive, one must have , from which . Apparently, F is a positive matrix; hence, so is . By Perron’s theorem [35, Th. 8.2.11], is the unique eigenvalue of maximum modulus of .     

The assumption in Proposition 8.2 can be justified by first noting that the channel matrix H is reduced to simply H11 if there is no femtocell deployed, and then applying the condition for the existence of a feasible power vector in that case [2].

Essentially, Propositions 8.1 and 8.2 characterize the following Pareto-optimal SINR boundary:

(8.73)

of the problem in (8.66). For every point on , it is impossible to increase the SINR of any one femto link without simultaneously reducing the SINR of some other femto links.

The finding of F in Proposition 8.2 also reveals that the performance of the femto users depends not only on the structure of the femtocell network (as reflected in H22), but also on the interaction between themselves with the macro users (as represented by H21 and H12). Moreover, the existence of F is conditional upon the particular values of H11 and , that is, . It is somewhat an expected result because macro users have an absolutely higher priority in accessing the radio resource. Such a condition also confirms that femto users can attain their Pareto-optimal SINRs only if the performance of macro users is, at least, unaffected.

The fact that F is a positive matrix is critical, since it paves the way to adapt the load-spillage parametrization [28] to find all points on . Nevertheless, it is important to point out here that, thanks to Propositions 8.1 and 8.2, one has to only deal with matrix F in a Nf-dimensional space instead of the original channel matrix H. Also, note that, F does not need to be primitive in the following result, unlike the strict condition on completely connected (i.e., primitive) matrices specifically required by [28].

Proposition 8.3 For a fixed , an SINR vector lies on the boundary defined in (8.73) if and only if there exist in and such that

(8.74)

(8.75)

Proof: Similar to that of [28, Lem. 3], the idea of this proof is based on Perron’s theorem [35, Th. 8.2.11]. If there is some and satisfying (8.75), then sf is a positive left eigenvector, associated with eigenvalue , of the positive matrix . By Perron’s theorem, is a unique positive eigenvalue with maximum modulus, that is, . Along with in (8.74), the corresponding is on .

Conversely, if , then and . Let sf be the left eigenvector associated with eigenvalue . Again, by Perron’s theorem, and since is a positive matrix.     

Using Proposition 8.3, we can now parameterize all on the boundary as follows. If we let

(8.76)

then (8.75) becomes . From which,

(8.77)

After multiplying the right-hand side of (8.75) by F and using (8.76), it is clear that , that is, vf is a left eigenvector associated with eigenvalue of . Furthermore, it can be shown that [35, Th. 1.3.20].

Once s(i)f is known, the computation of in (8.77) requires v(i)f to be found by (8.76). However, as F involves a matrix inverse operation [see (8.70)], it is not yet straightforward to find v(i)f distributively. Using (8.70), we rewrite (8.76) as

(8.78)

and define such that

(8.79)

Proposition 8.4 Given an initialization , sTm can be realized by the following update:

(8.80)

Proof: By recursively substituting into (8.80) and taking the limit , we have that

(8.81)

Recall that if , then it is clear that . By [35, Th. 5.6.9 and Cor. 5.6.16], exists and is positive componentwise. As such, (8.81) becomes

(8.82)

which is equivalent to (8.79).     

Notice that the ith component of sm[t+1] in (8.80) is actually

(8.83)

for . From (8.57) and upon recalling the partition of H, the update in (8.83) further amounts to

(8.84)

for . Clearly, s(i)m[t+1] consists of the internal component due to other macro users, and the external component due to all femto users, where b0 denotes the MBS.

With known and once has been determined, vf can readily be computed. From (8.78) and (8.79), vTf=sTmH12+sTfH22. Then, its component can be found according to

(8.85)

for . It is worth commenting that the first term of (8.85) amounts to the effects from all macro users, whereas the second term from the femto users within the same femtocell, and the third term from the femto users in all other femtocells.

8.4.2 Distributed Algorithm for Femtocell Utility Maximization and Macrocell SINR Balancing

The above parametrization allows us to find all points on . By fixing and upon applying that parametrization, (8.66) can be solved via an equivalent optimization problem, albeit in the new variable sf. The latter involves finding a direction of sf that leads and p to the optimum of the original problem. With , we propose to update s(i)f as follows.

(8.86)

for , where

(8.87)

Upon recalling that sf is a left eigenvector associated with eigenvalue of , it can be proved that the update of sf in (8.86) and (8.87) actually represents an ascent direction for U(sf) [28]. We also note that the update of macro load s(i)m in (8.84) is totally different from that of femto load s(i)f in (8.86).

Algorithm 8.4   PARETO-OPTIMAL POWER CONTROL ALGORITHM

We present the Pareto-optimal power control algorithm, which is described in the following. It is assumed that the channel gains between the DL and the UL are identical. Here, s(i)m[t+1] in step 4 is computed and managed by macro user . Specifically, each femto access point l is required to broadcast at a constant power. This allows macro user i to also measure all channel gains hl,i=hi,l required for the calculation of . On the other hand, the macro base station communicates the quantity to all macro users, which then permits macro user i to easily compute . Finally, macro user i reports the resulting s(i)m[t+1] back to macro base station for the computation of sm in the next iteration. Note that each femto access point l only needs to broadcast once. In addition, and s(i)m[t+1] can be exchanged locally between macro base station and macro user i over the control channel of link i.

The computation of v(j)f in step 7 can also be done by femto user j. Once sm has been determined (i.e., its update (8.84) has converged), macro base station broadcasts the quantity , again at a constant power. Recall that all summations have already been received at femto user j from all femto access points l (including the one that serves femto user j). Together with the assumption of symmetric DL–UL channel gains, v(j)f can thus be computed according to (8.85). Additionally, the update of s(j)f in step 10 can be accomplished in a completely distributed manner by femto user j with only local information required. Over its own control channel, femto user j then reports the new value of s(j)f to its servicing femto access point bj, to be used in the next iteration.

Theorem 8.4 For a sufficiently small and as , the proposed power control algorithm converges to the globally optimal solution of (8.66).

Proof: Note that the constraints in (8.66) are already satisfied with equality as we are operating on . With multiplier , the Lagrangian of problem in (8.66) is defined as

(8.88)

The KKT condition of (8.66) is simply , which can be shown equivalent to

(8.89)

where vf=[v(i)f] is the left eigenvector of and is the right eigenvector of , both associated with eigenvalue .

At the point of convergence , we have that . It follows from (8.87) that

(8.90)

Manipulating (8.61) and (8.62) and using the matrix/vector partitions specified at the beginning of Section 8.4.1 give , where . It can be shown that

(8.91)

as . Therefore, (8.90) is exactly (8.89) for and in the limit . Since (8.66) is a convex optimization problem, any point that satisfies the KKT conditions is also the global optimum [37].

With known and upon recalling that , the optimal SINR assignments of all femto users are determined according to (8.77). Also recollect that the optimal macrocell SINR is indeed . By Foschini–Miljanic’s algorithm [1], the power allocation that achieves these SINR targets can be found. Together with , gives the global optimum of problem (8.66).     

It can be verified that the distributed Pareto-optimal power control algorithm proposed in this section requires much higher signaling overhead than those developed by the game theory approach in Sections 5 and 9. In fact, the employment of the Foschini–Miljanic power control updates in step 8 given temporary target SINRs for macro and femto users may require a similar level of signaling as the main BSA and/or power control updates in the proposed algorithms in Sections 5 and 9. However, the proposed Pareto-optimal power control algorithm in this section indeed demands to search for s(i)m, s(i)f, and v(i)f (in steps 4, 10, and 7, respectively) based on which the the temporary target SINRs can be determined and achieved by the distributed Foschini–Miljanic power control updates. These two main operations require nested loops and the signaling overhead required by the updates in steps 4, 10, and 7 is quite heavy. Therefore, the Pareto-optimality achieved by the proposed algorithm in this section is indeed penalized by the heavy signaling overhead, which would consume large backhaul capacity. Another distributed power control algorithm for joint utility maximization of both network tiers subject to SINR constraints for macro users can be found in [38].

8.4.3 Numerical Examples

The network setting and user placement in our examples are shown in Figure 8.3, where macro and femto users are randomly deployed inside circles of radii of 1000 m and 50 m, respectively. In particular, we assume that there are Nm=10 macro users, whereas Nf=20 femto users are divided equally among 4 femtocells (i.e., 5 femto users per femtocell). The UL case is considered in all simulations. The absolute channel gain from the transmitter of user j to BS bi that serves user i is calculated as follows.

(8.92)

where is their corresponding geographical distance, and dB is used to represent the extra cross-cell signal loss due to penetration through walls (as femto users are typically deployed indoors).

For simplicity, we consider unit bandwidth. The throughput, normalized over the total bandwidth, is thus expressed in terms of b/s/Hz. Gaussian noise power is taken as . Normalized target SINRs , are assumed equal for all macro users, which are chosen such that . We choose processing gain equal 32 and 3-fair utility function is used, that is, in (8.67) unless stated otherwise. We set the error tolerance for the convergence of the proposed schemes and Foschini–Miljanic’s algorithm as and , respectively.

Figure 8.11 shows that the presented algorithm converges to an equilibrium where the exact target SINR dB obtained for all the macro users. Additionally, femto users are able to achieve quite a large total throughput, which confirms the efficacy of the proposed algorithm. The issue of fairly utilizing the available radio resources can be effectively resolved by regulating α in the utility function. Figure 8.12 shows the minimum and maximum throughput of all the femtocells for different values of α and target SINRs of macro users equal dB. Apparently, as α increases, the femto user whose data rate is the highest (likely due to its advantageous link conditions) sees a decline in its throughput, whereas the femto user with the lowest throughput has its data rate gradually enhanced. For a large value of α, the femto users’ minimum throughput is further expected to reach a plateau, meaning that max–min fairness is realized at that point.

8.5 SUMMARY AND OPEN RESEARCH ISSUES

In this chapter, we have exemplified the design of distributed resource allocation algorithms for CDMA multi-tier HetNets by using game theory and optimization approaches. We demonstrated how the convergence of these algorithms can be established, and discussed their different signaling overhead requirements. There are still various research issues that deserve more research efforts.

• For multi-tier HetNets with multiple antennae, various advanced communication techniques can be applied for efficient interference management and dynamic spectrum sharing. Specifically, if the BSs of each network tier are equipped with multiple antennae, then we can employ the beamforming technique to mitigate both co-tier interference and CTI [39,40]. However, distributed and low-complexity beamforming algorithms are strongly desired to alleviate heavy capacity requirement of the wired backhaul channel due to coordination signaling. Such design can be achieved by adapting available techniques on limited feedback and opportunistic beamforming design originally developed for single-tier networks to the multi-tier HetNet setting. Finally, low-complexity algorithms based on interference alignment idea can be devised for interference control in the wireless HetNets [41–43].
• All models considered in this chapter assume fixed network topology with unvarying number of static users. In practice, users dynamically arrive and leave the network and users may move over space, which result in changes in network topologies. Therefore, design of adaptive and robust resource allocation algorithms that can provide QoS support for dynamic HetNets is an important but challenging research problem to tackle. In addition, admission control at the call level must be jointly designed with resource allocation algorithms to efficiently utilize network resources and to avoid network congestion and QoS deterioration. Rich literature on these research issues available for homogeneous single-tier networks must be revisited and extended to resolve the corresponding issues in the heterogeneous setting.

REFERENCES

1. 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.

2. J. Zander, “Performance of optimum transmitter power control in cellular radio systems,” IEEE Transactions on Vehicular Technology, vol. 41, no. 1, pp. 57–62, February 1992.

3. R. D. Yates, “A framework for uplink power control in cellular radio systems,” IEEE Journal on Selected Areas in Communications, vol. 13, no. 7, pp. 1341–1347, September 1995.

4. M. Xiao, N. B. Shroff, and E. K. P. Chong, “A utility-based power control scheme in wireless cellular systems,” IEEE/ACM Transactions on Networking, vol. 11, no. 2, pp. 210–221, April 2003.

5. S. Koskie and Z. Gajic, “A Nash game algorithm for SIR-based power control in 3G wireless CDMA networks,” IEEE/ACM Transactions on Networking, vol. 13, no. 5, pp. 1017–1026, October 2005.

6. 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.

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

8. M. Rasti and A. R. Sharafat, “Distributed uplink power control with soft removal for wireless networks,” IEEE Transactions on Communications, vol. 59, no. 3, pp. 833–843, March 2011.

9. C. W. Sung and W. S. Wong, “A noncooperative power control game for multirate CDMA data networks,” IEEE Transactions on Wireless Communications, vol. 2, no. 1, pp. 186–194, January 2003.

10. M. Rasti, A. R. Sharafat, and B. Seyfe, “Pareto-efficient and goal-driven power control in wireless networks: A game-theoretic approach with a novel pricing scheme,” IEEE/ACM Transactions on Networking, vol. 17, no. 2, pp. 556–569, April 2009.

11. C. U. Saraydar, N. B. Mandayam, and D. J. Goodman, “Efficient power control via pricing in wireless data networks,” IEEE Transactions on Communications, vol. 50, no. 2, pp. 291–303, February 2002.

12. C. U. Saraydar, N. B. Mandayam, and D. J. Goodman, “Pricing and power control in a multicell wireless data network,” IEEE Journal on Selected Areas in Communications, vol. 19, no. 10, pp. 1883–1892, October 2001.

13. T. Alpcan, T. Baar, R. Srikant, and E. Altman, “CDMA uplink power control as a noncooperative game,” Wireless Networks, vol. 8, no. 6, pp. 659–670, November 2002.

14. W. Yu, G. Ginis, J. M. Cioffi, “Distributed multiuser power control for digital subscriber lines,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 5, pp. 1105–1115, June 2002.

15. T. Alpcan, T. Basar, and S. Dey, “A power control game based on outage probabilities for multicell wireless data networks,” IEEE Transactions on Wireless Communications, vol. 5, no. 4, pp. 890–899, April 2006.

16. C. W. Sung and K. K. Leung, “A generalized framework for distributed power control in wireless networks,” IEEE Transactions on Information Theory, vol. 51, no. 7, pp. 2625–2635, July 2005.

17. K. K. Leung and C. W. Sung, “An opportunistic power control algorithm for cellular network,” IEEE/ACM Transactions on Networking, vol. 14, no. 3, pp. 470–478, June 2006.

18. R. D. Yates and C. Y. Huang, “Integrated power control and base station assignment,” IEEE Transactions on Vehicular Technology, vol. 44, no. 3, pp. 638–644, August 1995.

19. S. V. Hanly, “An algorithm for combined cell-site selection and power control to maximize cellular spread spectrum capacity,” IEEE Journal on Selected Areas in Communications, vol. 13, no. 7, pp. 1332–1340, September 1995.

20. H. S. Dhillon, R. K. Ganti, F. Baccelli, and J. G. Andrews, “Modeling and analysis of K-tier downlink heterogeneous cellular networks,” IEEE Journal on Selected Areas in Communications, vol. 30, no. 3, pp. 550–560, April 2012.

21. P. Xia, V. Chandrasekhar, and J. G. Andrews, “Open vs. closed access femtocells in the uplink,” IEEE Transactions on Wireless Communications, vol. 9, no. 10, pp. 3798–3809, December 2010.

22. V. Chandrasekhar and J. G. Andrews, “Spectrum allocation in tiered cellular networks,” IEEE Transactions on Communications, vol. 57, no. 10, pp. 3059–3068, October 2009.

23. V. Chandrasekhar and J. G. Andrews, “Uplink capacity and interference avoidance for two-tier femtocell networks,” IEEE Transactions on Wireless Communications, vol. 8, no. 7, pp. 3498–3509, July 2009.

24. H. S. Jo, C. Mun, J. Moon, and J.-G. Yook, “Interference mitigation using uplink power control for two-tier femtocell networks,” IEEE Transactions on Wireless Communications, vol. 8, no. 10, pp. 4906–4910, October 2009.

25. H. S. Jo, C. Mun, J. Moon, and J.-G. Yook, “Self-optimized coverage coordination in femtocell networks,” IEEE Transactions on Wireless Communications, vol. 9, no. 10, pp. 2977–2982, October 2010.

26. M. Rasti and A. R. Sharafat, “Pareto and energy-efficient distributed power control with feasibility check in wireless networks,” IEEE Transactions on Information Theory, vol. 57, no. 1, pp. 245–255, January 2011.

27. S. Ulukus and R. D. Yates, “Stochastic power control for cellular radio systems,” IEEE Transactions on Communications, vol. 46, no. 6, pp. 784–798, June 1998.

28. P. Hande, S. Rangan, M. Chiang, and X. Wu, “Distributed uplink power control for optimal SIR assignment in cellular data networks,” IEEE/ACM Transactions on Networking, vol. 16, no. 6, pp. 1420–1433, December 2008.

29. D. Palomar and M. Chiang, “A tutorial on decomposition methods and distributed network resource allocation,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 8, pp. 1439–1451, August 2006.

30. M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle, “Layering as optimization decomposition: A mathematical theory of network architectures,” Proceedings of the IEEE, vol. 95, no. 1, pp. 255–312, January 2007.

31. D. Ngo, L. B. Le, T. Le-Ngoc, E. Hossain, and D. I. Kim, “Distributed interference management in two-tier CDMA femtocell networks,” IEEE Transactions on Wireless Communications, vol. 11, no. 3, pp. 979–989, March 2012.

32. A. A. D’Amico, U. Mengali, and M. Morelli, “Channel estimation for the uplink of a DS-CDMA system,” IEEE Transactions on Wireless Communications, vol. 2, no. 6, pp. 1132–1137, November 2003.

33. V. N. Ha and L. B. Le, “Distributed base station association and power control for heterogeneous cellular networks,” IEEE Transactions on Vehicular Technology, to appear.

34. 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.

35. A. Horn and A. Johnson, Matrix Analysis, 1st edition, Cambridge University Press, 1985.

36. H. Boche and S. Stanczak, “Convexity of some feasible QoS regions and asymptotic behavior of the minimum total power in CDMA systems,” IEEE Transactions on Communications, vol. 52, no. 12, pp. 2190–2197, December 2004.

37. D. P. Bertsekas, Nonlinear Programming, 2nd edition, Boston, MA: Athena Scientific, 1999.

38. D. Ngo, L. B. Le, and T. Le-Ngoc, “Distributed Pareto-optimal power control for utility maximization in femtocell networks,” IEEE Transactions on Wireless Communications, vol. 11, no. 10, pp. 3434–3446, October 2012.

39. K. Huang, J. G. Andrews, and R. W. Heath, “Performance of orthogonal beamforming for SDMA with limited feedback,” IEEE Transactions on Vehicular Technology, vol. 58, no. 1, pp. 152–164, January 2009.

40. W. Choi, A. Forenza, J. G. Andrews, and R. W. Heath, “Opportunistic space-division multiple access with beam selection,” IEEE Transactions on Communications, vol. 55, no. 12, pp. 2371–2380, December 2007.

41. M. A. Maddah-Ali, A. S. Motahari, and A. K. Khandani, “Communication over MIMO X channels: Interference alignment, decomposition, and performance analysis,” IEEE Transactions on Information Theory, vol. 54, no. 8, pp. 3457–3470, August 2008.

42. T. Gou and S. A. Jafar, “Degrees of freedom of the K user MxN MIMO interference channel,” IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6040–6057, December 2010.

43. C. Suh, M. Ho, and D. N. C. Tse, “Downlink interference alignment,” IEEE Transactions on Communications, vol. 59, no. 9, pp. 2616–2626, September 2011.

1. A nonnegative matrix is called primitive if it is irreducible and has only one eigenvalue of maximum modulus [35, Definition 8.5.0].