A two-tier hierarchical architecture is proposed in [24] for WiMAX uplink scheduling. In the higher hierarchy, strict prioritization is used to direct the traffic into the four queues, according to its type. Then, each queue is scheduled according to a particular algorithm, i.e.,

the scheduling list.

**3.5.7 Reinforcement Learning**

states is denoted by S, then Π: S→A.

**3.5.8 Hierarchical/hybrid algorithms**

making them hierarchical in nature.

whether traffic in the corresponding queue *i q* [24].

queuing, in which case the number of states is acceptable.

delay, so a throughput maximizing algorithm might be preferred.

This section presents the simulation results for the algorithms scheduling. For testing performance of algorithms, the introduced algorithms are implemented in the NS-2 (Network Simulator) [20] and WiMAX module [21] that is based on the WiMAX NIST module [20].The MAC implementation contains the main features of the 802.16 standard, such as downlink and uplink transmission. We have also implemented the most important MAC signalling messages, such as UL-MAP and DL-MAP, authentication (PKM), capabilities (SBC), REG (Registration), DSA (Dynamic Service Addition), and DSC (Dynamic Service Change). The implemented PHY is OFDM.

Table 1. Slot size for OFDM PHY

The current implementation also supports differencing MCSs (Moulding Code Scheme). Table 1 shows present slot size for different modulations and channel coding types.

Scheduling Algorithm and Bandwidth Allocation in WiMAX 99

In particular, we consider several comparable scheduling algorithms, including WRR, EDF, and TRS which is a representative WiMAX scheduling algorithm and has been patented and

Besides packet drop rate and throughput that have been studied in analysis, we are also interested in the fairness performance, which is measured by Jain's Fairness Index [22]

1 2

*fx x x*

( , ,... )

2

2 1

(1)

*MRi* (2)

*i i*

1

*n x*

*i n n*

Where xi is the normalized throughput of connection i, and n is the total number of connections. Each SS establishes a number of connections to the BS in our simulation. We consider ten rtVR connections and ten nrtVR connections. Each type of connection is

*THi Xi*

ie, with Thi and MRRi stand for the connection i's actual data rate and reserved data rate, respectively. The Jain's Fairness Index ranges between 0 and 1. The higher the index, the better the fairness. If Thi = MRRi for all i, or in other words, every connection obtains its reserved data rate, then xi = 1 for all i, and Jain's Fairness Index equals 1. All simulations

**UGS**

12345

**Traffic load**

Figures 7, 8 show delay packets as a function of the traffic load submitted to the network. The data packets are generated by a streaming multimedia application. The diagram of UGS scheduling algorithm by considering delay is linear where its throughput is increasing. As mentioned above, the UGS traffic request is the highest priority. If a packet is available in this type of traffic it will be sent in no time. For accurate performance evaluation, we adopt

the WiMAX physical layer standard OFDM\_BPSK\_1\_2 in our simulations. [24]

( )

*x*

*n i*

well received).

defined as follows:

associated with an MRR and a delay budget.

0 0.2 0.4 0.6 0.8 1

**Latency**

Fig. 7. Latency versus traffic

and analytic calculations are done using NS2 simulator.

We present a simulation scenario to study thoroughly the proposed scheduling solution. The scenario will present a multi-service case, in which a provider has to support connections with different 802.16 classes and traffic characteristics.

The purpose of this scenario is to ensure that the scheduler at the BS takes the service class into account and allocates slots based on the QoS requirements and the request sizes sent by SSs. Another purpose is to test that the scheduler at the BS takes the MAC overhead into account. Table 1 presents information about which applications are active at scenario.

Regardless of the simulation scenario, the general parameters of the 802.16 network are the same (see Table 2). There is one BS that controls the traffic of the 802.16 network. The physical layer is OFDM. The BS uses the dynamic uplink/downlink slot assignment for the TDD mode. Both the BS and all SSs use packing and fragmentation in all simulation scenarios. The MAC level uses the largest possible PDU size. ARQ is turned off; neither the BS nor SSs use the CRC field while sending packets.

Table 2. WiMAX parameter

We consider a general scenario, where n rtVR and/or nrtVR connections are established. Connection i has an arrival rate of ¸i, a delay budget of i, and a minimum reserved bandwidth of MRRi. For the sake of analytic tractability, we assume that the data arrival forms a Poisson process and all queues have infinite size. Other types of traffic (such as the more practical bursty traffic) are studied through simulations.

The main parameters of the simulation are represented in Table 3. Effects of these parameters are similar over results of all scheduling algorithms. Moreover, producers of this WiMAX module have used these values for testing performance of their simulator.

Table 3. Main parameters of the simulation

We present a simulation scenario to study thoroughly the proposed scheduling solution. The scenario will present a multi-service case, in which a provider has to support

The purpose of this scenario is to ensure that the scheduler at the BS takes the service class into account and allocates slots based on the QoS requirements and the request sizes sent by SSs. Another purpose is to test that the scheduler at the BS takes the MAC overhead into account. Table 1 presents information about which applications are active at scenario.

Regardless of the simulation scenario, the general parameters of the 802.16 network are the same (see Table 2). There is one BS that controls the traffic of the 802.16 network. The physical layer is OFDM. The BS uses the dynamic uplink/downlink slot assignment for the TDD mode. Both the BS and all SSs use packing and fragmentation in all simulation scenarios. The MAC level uses the largest possible PDU size. ARQ is turned off; neither the

connections with different 802.16 classes and traffic characteristics.

**Value Parameter**  OFDM PHY 7MHz Bandwidth

400 Frame per Second TDD Duplexing mode OFF ARQ/CRC

We consider a general scenario, where n rtVR and/or nrtVR connections are established. Connection i has an arrival rate of ¸i, a delay budget of i, and a minimum reserved bandwidth of MRRi. For the sake of analytic tractability, we assume that the data arrival forms a Poisson process and all queues have infinite size. Other types of traffic (such as the

The main parameters of the simulation are represented in Table 3. Effects of these parameters are similar over results of all scheduling algorithms. Moreover, producers of this

WiMAX module have used these values for testing performance of their simulator.

Propagation model Two Ray Ground Antenna model Omni antenna

**Parameter Value**  Frequency band 5 MHz

Antenna height 1.5 m Transmit power 0.25 Receive power threshold 205e-12 Frame duration 20 ms Cyclic prefix (CP) 0.25 Simulation duration 100 s

BS nor SSs use the CRC field while sending packets.

more practical bursty traffic) are studied through simulations.

Table 3. Main parameters of the simulation

Table 2. WiMAX parameter

In particular, we consider several comparable scheduling algorithms, including WRR, EDF, and TRS which is a representative WiMAX scheduling algorithm and has been patented and well received).

Besides packet drop rate and throughput that have been studied in analysis, we are also interested in the fairness performance, which is measured by Jain's Fairness Index [22] defined as follows:

$$f(\mathbf{x}\_1, \mathbf{x}\_2, \dots \mathbf{x}\_n) = \frac{\left(\sum\_{i=1}^n \mathbf{x}\_i\right)^2}{n \sum\_{i=1}^n \mathbf{x}\_i^2} \tag{1}$$

Where xi is the normalized throughput of connection i, and n is the total number of connections. Each SS establishes a number of connections to the BS in our simulation. We consider ten rtVR connections and ten nrtVR connections. Each type of connection is associated with an MRR and a delay budget.

$$X\dot{i} = \frac{T\text{Hi}\dot{i}}{M\text{Ri}}\tag{2}$$

ie, with Thi and MRRi stand for the connection i's actual data rate and reserved data rate, respectively. The Jain's Fairness Index ranges between 0 and 1. The higher the index, the better the fairness. If Thi = MRRi for all i, or in other words, every connection obtains its reserved data rate, then xi = 1 for all i, and Jain's Fairness Index equals 1. All simulations and analytic calculations are done using NS2 simulator.

Fig. 7. Latency versus traffic

Figures 7, 8 show delay packets as a function of the traffic load submitted to the network. The data packets are generated by a streaming multimedia application. The diagram of UGS scheduling algorithm by considering delay is linear where its throughput is increasing. As mentioned above, the UGS traffic request is the highest priority. If a packet is available in this type of traffic it will be sent in no time. For accurate performance evaluation, we adopt the WiMAX physical layer standard OFDM\_BPSK\_1\_2 in our simulations. [24]

Scheduling Algorithm and Bandwidth Allocation in WiMAX 101

Figure 10 shows the latency as a function of rtVR+nrtVR traffic load. We verify that the TRS

Figure 11 shows the latency as a function of rtVR traffic load. We verify that the mSIR

In figure 12, the protocols have been compared on the base of throughput. As you see,

scheduler provides a decrease in the latency.

Fig. 10. Latency versus Simulation Time

Fig. 11. Latency versus Simulation Time

TRS+RR throughput is greater than all.

scheduler provides a decrease in the latency.

Fig. 8. Throughput versus traffic

The fairness of the scheduling algorithms under bursty traffic is shown in figure 9. As we can see, WRR always maintains almost high fairness, while the fairness of EDF algorithm is the worst among the four algorithms. This is due to the fact that some real time packets rtVR connections are dropped under high burstiness, and thus the throughput of rtVR decreases. [30], [31]

Fig. 9. Fairness versus Simulation Time

**UGS**

300 800 1400 1900 2400 2900 3400

The fairness of the scheduling algorithms under bursty traffic is shown in figure 9. As we can see, WRR always maintains almost high fairness, while the fairness of EDF algorithm is the worst among the four algorithms. This is due to the fact that some real time packets rtVR connections are dropped under high burstiness, and thus the throughput of rtVR decreases.

**rtVR**

EDF WRR

TRS+mSIR

10 30 50 70 90

**Simulation Time**

**Traffic Load**

**Throughput**

Fig. 8. Throughput versus traffic

Fig. 9. Fairness versus Simulation Time

0.88 0.9 0.92 0.94 0.96 0.98 1 1.02

**Fairness**

[30], [31]

Figure 10 shows the latency as a function of rtVR+nrtVR traffic load. We verify that the TRS scheduler provides a decrease in the latency.

Fig. 10. Latency versus Simulation Time

Figure 11 shows the latency as a function of rtVR traffic load. We verify that the mSIR scheduler provides a decrease in the latency.

Fig. 11. Latency versus Simulation Time

In figure 12, the protocols have been compared on the base of throughput. As you see, TRS+RR throughput is greater than all.

Scheduling Algorithm and Bandwidth Allocation in WiMAX 103

[10] A. Parekh and R. Gallager(1992). *A Qeneralized Processor Sharing Approach to Flow Control: The Single Node Case*, in Proc. IEEE INFOCOM , pp. 915–924. [11] J. Bennet and H. Zhang(1996). *WF2Q: Worst-Case Fair Weighted Fair Queueing, Procceding*

[12] S. Golestani (1994). *A Self-Clocked Fair Queueing Scheme for Broadband Applications*,

[15] S. Belenki (2000). *Traffic management in QoS networks: Overview and suggested*

[16] M.Shreedhar and G.Varghese(June 1996). Efficient Fair Queuing using Deficit Round R

[17] T. Al\_Khasib, H. Alnuweiri, H. Fattah and V. C. M. Leung(2005). Mini round robin:

Cmmunications, IEEE International Conference on ICC, pp. 363\_368 Vol. 1. [18] Nortel Networks,Introduction to quality of service (QoS)(September 2008), Nortel NetworksWebsite, 2003. [Online]. Accessed on 1st of September 2008. [19] C.F. Ball, F. Treml, X. Gaube, and A. Klein(September 2005). Performance Analysis of

Indoor and Mobile Radio Communications, PIMRC 2005, Berlin, 11 – 14. [20] QoS-included WiMAX Module for NS-2 Simulator. First International Conference on

[22] D. M. C. R. Jain andW. Hawe(1984). A Quantitative Measure of Fairness and

[23] J. Hall , P. Mars(December 1998). Satisfying QoS with a Learning Based Scheduling

[24] M.Taghipoor,G Tavassoli and V.Hosseini(April 2010). Gurantee QoS in WiMAX Networks with learning automata, ITNG 2010 Las Vegas, Nevada, USA. 12-14 [25] Ajay Chandra V. Gummalla, John o. Limb.Wireless Medium Access Control Protocols,

[26] Q. Liu, X. Wang, and G. Giannakis(May 2006). A Cross-Layer Scheduling Algorithm

[27] D. Niyato and E. Hossain ( Dec. 2006). Queue-aware Uplink Banwidth Allocation and

[28] A. Shejwal and A. Parhar(2007). Service Criticality Based Scheduling for IEEE 802.16 WirelessMAN, in Proc. 2nd IEEE Int. Conf. AusWreless, , pp. 12–18.

with QoS Support in Wireless Networks, IEEE Trans. Veh. Tech., vol. 55, no. 3, pp.

Rate Control for Polling Service in IEEE 802.16 Broadband Wireless Networks,

bin, IEEE/ACM Transactions on Networking, vol. 1, pp. 375‐385.

*multiplexing in a general purpose ATM switch chip*, Selected Areas in

enhanced frame\_based scheduling algorithm for multimedia networks, IEEE

Temporary Removal Scheduling applied to mobile WiMAX Scenarios in Tight Frequency Reuse, the 16th Annual IEEE International Symposium On Personal

Simulation Tools and Techniques for Communications Networks and Systems,

Discriminationfor Resource Allocation in Shared Systems, dEC Research Report,

[13] R. Jain, lecture notes ( 2007), A Survey of Scheduling Methods, University of Ohio. [14] M. Katevenis, S. Sidiropoulos and C. Courcoubetis(1991). *Weighted round robin cell*

*of IEEE INFOCOM*, 1996, pp. 120–128.

*improvements*, Tech. Rep.

Procceding of IEEE INFOCOM, pp. 636–646.

Communications, IEEE Journal on 9(8), pp. 1265\_1279.

SIMUTools 2008, Marseille,France, March 3-7,2008. [21] The network simulator ns-2(September 2007). Available from :

Algorithm, School of Engineering, University of Durham,.

IEEE Trans. Mobile Comp., vol. 5, no. 8, pp. 668–679.

http://www.isi.edu/nsnam/ns/.

IEEE Communications Surveys, 2000.

TR-301.

839–847.

Fig. 12. Throughput

## **5. References**

**Throughput**

NIST\_TRS TRS RR RR+mSIR

[1] IEEE Standard for Local and Metropolitan Area Networks—Part 16: Air Interface for

[2] IEEE Standard for Local and Metropolitan Area Networks—Part 16: Air Interface for

Bands, 2005, IEEE802.16e.. Available from: http://www.ieee802.org/16/. [3] Aura Ganz, Zvi Ganz, Kitti Wongthavarawat(18 September 2003). *Multimedia Wireless*

[4] Overcoming Barriers to High-Quality Voice over IP Deployments (2003), Intel

[5] DiffServ-The Scalable End-to-End Quality of Service Model (August 2005), Cisco

[6] WiMAX – Delivering on the Promise of Wireless Broadband (Second Quarter 2006), Xcell

[7] M. Katavenis, S. Sidiropoulos, and C. Courcoubetis. *Weighted Round-Robin Cell*

[8] M. Shreedhar and G. Varghese (1995), *Efficient Fair Queueing Using Deficit Round Robin*, in

[9] A. Demeres, S. Keshav, and S. Shenker(1989). *Analysis and Simulation of A Fair Queueing*

*Multiplexing in A General-Purpose ATM Switch Chip*, IEEE J. Sel. Areas Commun.,

*Networks: Technologies, Standards, and QoS, Prentice Hall Publisher*.

Fixed Broadband Wireless Access Systems, 2004, IEEE802.16. Available from :

Fixed Broadband Wireless Access Systems—Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8

Fig. 12. Throughput

Whitepaper.

Whitepaper.

Journal - Issue 57.

http://www.ieeefor 802.org/16/.

vol. 9, no. 8, pp. 1265–1279, Jan. 1991.

Proc. IEEE SIGCOMM, pp. 231–242. 135.

*Algorithm*, in Proc. IEEE SIGCOMM, pp. 1–12.

**5. References**

NIST\_TRS TRS RR

EDF 1 0.998 WRR 0.998 0.998 LTRS 0.99 0.99

0.31 0.6 0.7

10 30

**0**

**5**

Nassar Ksairi *HIAST, Damascus*

*Syria*

**Downlink Resource Allocation and Frequency**

Throughout this chapter we consider the *downlink* of a cellular WiMAX network where a number of base stations need to communicate simultaneously with their respective active users 1. Each of these users has typically a certain Quality of Service (QoS) requirement that needs to be satisfied. To that end, base stations dispose of limited wireless resources (subcarriers and transmit powers) that should be shared between users. They also have some amount of Channel State Information (CSI) about users' propagation channels available, if existent, typically via feedback. The problem of determining the subset of subcarriers assigned to each user and the transmit power on each of these subcarriers is commonly referred to as the *resource allocation problem*. This problem should be solved such that all the QoS exigencies

Of course, the resource allocation problem has several formulations depending on i) the particular QoS-related objective function which we adopt (*e.g.,* achievable rate, transmission error probability . . .) and ii) the channel model that we assume in relation with the available CSI. These CSI-related channel models will be discussed in Section 2 while the different

Since the set of subcarriers available for the whole WiMAX system is limited, it is typical that some subcarriers are reused at the same time by different base stations. Such base stations will generate multicell interference. Therefore, resource allocation parameters should, in principle, be determined in each cell in such a way that the latter multicell interference does not reach excessive levels. This fact highlights the importance of properly planning the so-called *frequency-reuse scheme* of the network. A frequency-reuse scheme answers the question whether the whole set of subcarriers should be available for allocation in all the cells of the network (meaning better spectral-usage efficiency but higher levels of intercell interference) or whether we should make parts of it exclusive to certain cells (leading thus to less efficiency in spectral usage but to lower levels of interference on the exclusive subcarriers). Note that frequency-reuse planning is intimately related to resource allocation since it decides the subset of subcarriers that will be available for allocation in each cell of the network. Refer

1 We assume that the set of active users in the network is determined in advance by the schedulers at the base stations. We also assume that base stations has for each active user an infinite backlog of data to

formulations of the resource allocation problem will be covered in Section 4.

**1. Introduction**

are respected.

to Sections 4 and 5 for more details.

be transmitted

**Reuse Schemes for WiMAX Networks**

## **Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks**

Nassar Ksairi *HIAST, Damascus Syria*

#### **1. Introduction**

104 Quality of Service and Resource Allocation in WiMAX

[29] H. Chen, thesis (spring 2008). Scheduling and Resource Optimization in Next Generation Hetergeneous Wireless Networks, University of Luoisiana. [30] Jafari, Saeid. M., Taghipour, M. and Meybodi, M. R.(2011). Bandwidth Allocation in

[31] Jafari, Saeid. M., Taghipour, M. and Meybodi, M. R. (2011).Bandwidth Allocation in

Vol. 15, No. 4, pp. 525-531.

15, No. 4, pp. 576-583.

Wimax Networks Using Reinforcement Learning, World Applied Sciences Journal

Wimax Networks Using Learning Automata, World Applied Sciences Journal Vol.

Throughout this chapter we consider the *downlink* of a cellular WiMAX network where a number of base stations need to communicate simultaneously with their respective active users 1. Each of these users has typically a certain Quality of Service (QoS) requirement that needs to be satisfied. To that end, base stations dispose of limited wireless resources (subcarriers and transmit powers) that should be shared between users. They also have some amount of Channel State Information (CSI) about users' propagation channels available, if existent, typically via feedback. The problem of determining the subset of subcarriers assigned to each user and the transmit power on each of these subcarriers is commonly referred to as the *resource allocation problem*. This problem should be solved such that all the QoS exigencies are respected.

Of course, the resource allocation problem has several formulations depending on i) the particular QoS-related objective function which we adopt (*e.g.,* achievable rate, transmission error probability . . .) and ii) the channel model that we assume in relation with the available CSI. These CSI-related channel models will be discussed in Section 2 while the different formulations of the resource allocation problem will be covered in Section 4.

Since the set of subcarriers available for the whole WiMAX system is limited, it is typical that some subcarriers are reused at the same time by different base stations. Such base stations will generate multicell interference. Therefore, resource allocation parameters should, in principle, be determined in each cell in such a way that the latter multicell interference does not reach excessive levels. This fact highlights the importance of properly planning the so-called *frequency-reuse scheme* of the network. A frequency-reuse scheme answers the question whether the whole set of subcarriers should be available for allocation in all the cells of the network (meaning better spectral-usage efficiency but higher levels of intercell interference) or whether we should make parts of it exclusive to certain cells (leading thus to less efficiency in spectral usage but to lower levels of interference on the exclusive subcarriers).

Note that frequency-reuse planning is intimately related to resource allocation since it decides the subset of subcarriers that will be available for allocation in each cell of the network. Refer to Sections 4 and 5 for more details.

1 We assume that the set of active users in the network is determined in advance by the schedulers at the base stations. We also assume that base stations has for each active user an infinite backlog of data to be transmitted

formulation being associated with a different model for coefficients *Hc*

In this chapter, we consider three signal models for these coefficients.

The general OFDMA signal model given by (1) does not specify whether the channel coefficients {*Hk*(*n*, *m*)}*k*,*n*,*m* associated with each user *k* are known at the base stations or not.

Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks 107

known (thus deterministic) at both the base station side and the receiver side on all the subcarriers *n* ∈ {0... *N* − 1}. Note that **this assumption implicitly requires that each receiver** *k* **feedbacks to the base station the values of the channel coefficients** *Hc*

For the sake of simplicity, it is also often assumed in the literature that the above

transmission of a codeword 2 *i.e.,* ∀*m* ∈ {0, 1, . . . , *T* − 1}. Under these assumptions, a transmission to user *k* at rate *Rk* nats/sec/Hz is possible from the information-theoretic point of view with negligible probability of error provided that *Rk* < *Ck*, where *Ck* denotes the channel capacity associated with user *k*. If we assume that the noise-plus-interference

*k* (*n*, *m*) remain constant (*Hc*

process *wk*(*n*, *m*) in (1) is zero-mean Gaussian-distributed3 with variance *σ*2

log

1 + *Pk*,*n*

where N*k*, we recall, is the subset of subcarriers (N*k* ⊂ {0, 1, . . . , *N*}) assigned to user *k*, and where *Pn*,*k* is the power transmitted by the base station on subcarrier *n* ∈ N*k i.e.,*

subcarrier *n* are time-varying, unknown at the base station side and perfectly known at the receiver side. We can thus think of {*Hk*(*n*, *m*)}*m* as a random process with a certain statistical distribution *e.g.,* Rayleigh, Rice, Nakagami, etc. We also assume that this process undergo **fast fading** *i.e.,* the coherence time of the channel is much smaller than the duration *T* of transmission of a codeword. It is thus reasonable to model {*Hk*(*n*, *m*)}*m* as an independent identically distributed (i.i.d) random ergodic process for each *n* ∈ {0... *N* − 1}. Finally, **we assume that the parameters of the distribution of this process** *i.e.,* **its mean, variance** ...**, are known at the base station, typically via feedback**.

3 Eventhough the noise-plus-interference *wk*(*n*, *m*) is not Gaussian in general, approximating it as a Gaussian process is widely used in the literature (see for instance Gault et al. (2005); S. Plass et al. (2004; 2006)). The reason behind that is twofold: first, the Gaussian approximation provides a lower bound on the mutual information, second it allows us to have an analytical expression for the channel

> *σ*2 *k*

 ,

*k* (*n*, *m*) associated with each user *k* on any

models are summarized in the following subsection.

**2.1 Theoretical CSI-related channel models:**

1. **Full CSI: Deterministic channels**. In this model, channel coefficients *Hc*

**on all the assigned subcarriers** *n*.

channel capacity *Ck* (in nats/sec/Hz) is given by

*Ck* = 1

2. **Statistical CSI: Random ergodic (fast-fading) channels**. In this model, we assume that coefficients *Hc*

*N* ∑ *n*∈N*k*

2 A codeword typically spans several OFDM blocks *i.e.,* several time indexes *m*

deterministic coefficients *Hc*

*Pk*,*n* = **E**

capacity.

*k* (*n*, *m*)

*k* (*n*)) during the

*k* , then the

*k* (*n*, *m*) for each user *k* are assumed to be perfectly

*k* (*n*, *m*) = *Hc*

The rest of the chapter is organized as follows. In Section 2, the different kinds of CSI feedback models are presented and their related channel models are discussed. The issue of frequency reuse planning (which is intimately related to cellular resource allocation) is discussed in Section 3. Each different channel model leads to a different formulation of the resource allocation problem. These formulations are addressed in Section 4. Finally, Section 5 deals with the determination of the so-called *frequency-reuse factor*.

### **2. Feedback for resource allocation: Channel State Information (CSI) and channel models**

Consider the downlink of an OFDMA-based wireless system (such as a WiMAX network) and denote by *N*, *K* the total number of subcarriers and of active users, respectively. Assume that the subcarriers are numbered from 1 to *N* and that the active users of the network are numbered from 1 to *K*. The network comprises a certain number of cells that are indexed using the notation *c*. Each cell *c* consists of a base station communicating with a group of users as shown in Figure 1. The signal received by user *k* at the *n*th subcarrier of the *m*th

Fig. 1. WiMAX network

OFDM block (*m* being the time index) is given by

$$y\_k(n,m) = H\_k^c(n,m)s\_k(n,m) + w\_k(n,m),\tag{1}$$

where *sk*(*n*, *m*) is the transmitted symbol and where *wk*(*n*, *m*) is a random process which is used to model the effects of both thermal noise and intercell interference. Finally, *Hc k* (*n*, *m*) refers to the (generally complex-valued) coefficient of the propagation channel between the base station of cell *c* and user *k* on subcarrier *n* at time *m*.

Assume that the duration of transmission is equal to *T* OFDM symbols *i.e., m* ∈ {0, 1, . . . , *T* − 1}. Denote by N*k* the subset of subcarriers (N*k* ⊂ {1, 2, . . . , *N*}) assigned to user *k*. The codeword destined to user *k* is thus the |N*k*| × *T* matrix

$$\mathbf{S}\_{k} = \begin{bmatrix} \mathbf{s}\_{k}(0), \mathbf{s}\_{k}(1), \dots, \mathbf{s}\_{k}(T-1) \end{bmatrix} \\ \tag{2}$$

where each |N*k*| × 1 column-vector *sk*(*m*) is composed of the symbols {*sk*(*n*, *m*)}*n*∈N*k* transmitted during the *m*th OFDM block on subcarriers N*k*.

Depending on the amount of feedback sent from users to the base stations, coefficients *Hc k* (*n*, *m*) can be modeled either as deterministic or as random variables. As stated in Section I, different formulations of the resource allocation problem exist in the literature, each formulation being associated with a different model for coefficients *Hc k* (*n*, *m*). These channels models are summarized in the following subsection.

#### **2.1 Theoretical CSI-related channel models:**

The general OFDMA signal model given by (1) does not specify whether the channel coefficients {*Hk*(*n*, *m*)}*k*,*n*,*m* associated with each user *k* are known at the base stations or not. In this chapter, we consider three signal models for these coefficients.

#### 1. **Full CSI: Deterministic channels**.

2 Will-be-set-by-IN-TECH

The rest of the chapter is organized as follows. In Section 2, the different kinds of CSI feedback models are presented and their related channel models are discussed. The issue of frequency reuse planning (which is intimately related to cellular resource allocation) is discussed in Section 3. Each different channel model leads to a different formulation of the resource allocation problem. These formulations are addressed in Section 4. Finally, Section 5 deals

**2. Feedback for resource allocation: Channel State Information (CSI) and channel**

Consider the downlink of an OFDMA-based wireless system (such as a WiMAX network) and denote by *N*, *K* the total number of subcarriers and of active users, respectively. Assume that the subcarriers are numbered from 1 to *N* and that the active users of the network are numbered from 1 to *K*. The network comprises a certain number of cells that are indexed using the notation *c*. Each cell *c* consists of a base station communicating with a group of users as shown in Figure 1. The signal received by user *k* at the *n*th subcarrier of the *m*th

where *sk*(*n*, *m*) is the transmitted symbol and where *wk*(*n*, *m*) is a random process which is used to model the effects of both thermal noise and intercell interference. Finally, *Hc*

refers to the (generally complex-valued) coefficient of the propagation channel between the

Assume that the duration of transmission is equal to *T* OFDM symbols *i.e., m* ∈ {0, 1, . . . , *T* − 1}. Denote by N*k* the subset of subcarriers (N*k* ⊂ {1, 2, . . . , *N*}) assigned to user *k*. The

where each |N*k*| × 1 column-vector *sk*(*m*) is composed of the symbols {*sk*(*n*, *m*)}*n*∈N*k*

Depending on the amount of feedback sent from users to the base stations, coefficients

*k* (*n*, *m*) can be modeled either as deterministic or as random variables. As stated in Section I, different formulations of the resource allocation problem exist in the literature, each

*k* (*n*, *m*)*sk*(*n*, *m*) + *wk*(*n*, *m*), (1)

*Sk* = [*sk*(0), *sk*(1),..., *sk*(*T* − 1)] , (2)

*k* (*n*, *m*)

with the determination of the so-called *frequency-reuse factor*.

**models**

Fig. 1. WiMAX network

*Hc*

OFDM block (*m* being the time index) is given by

base station of cell *c* and user *k* on subcarrier *n* at time *m*.

codeword destined to user *k* is thus the |N*k*| × *T* matrix

transmitted during the *m*th OFDM block on subcarriers N*k*.

*yk*(*n*, *m*) = *Hc*

In this model, channel coefficients *Hc k* (*n*, *m*) for each user *k* are assumed to be perfectly known (thus deterministic) at both the base station side and the receiver side on all the subcarriers *n* ∈ {0... *N* − 1}. Note that **this assumption implicitly requires that each receiver** *k* **feedbacks to the base station the values of the channel coefficients** *Hc k* (*n*, *m*) **on all the assigned subcarriers** *n*.

For the sake of simplicity, it is also often assumed in the literature that the above deterministic coefficients *Hc k* (*n*, *m*) remain constant (*Hc k* (*n*, *m*) = *Hc k* (*n*)) during the transmission of a codeword 2 *i.e.,* ∀*m* ∈ {0, 1, . . . , *T* − 1}. Under these assumptions, a transmission to user *k* at rate *Rk* nats/sec/Hz is possible from the information-theoretic point of view with negligible probability of error provided that *Rk* < *Ck*, where *Ck* denotes the channel capacity associated with user *k*. If we assume that the noise-plus-interference process *wk*(*n*, *m*) in (1) is zero-mean Gaussian-distributed3 with variance *σ*2 *k* , then the channel capacity *Ck* (in nats/sec/Hz) is given by

$$\mathcal{C}\_k = \frac{1}{N} \sum\_{n \in \mathcal{N}\_k} \log \left( 1 + P\_{k,n} \frac{|H\_k^{\varepsilon}(n)|^2}{\sigma\_k^2} \right) \dots$$

where N*k*, we recall, is the subset of subcarriers (N*k* ⊂ {0, 1, . . . , *N*}) assigned to user *k*, and where *Pn*,*k* is the power transmitted by the base station on subcarrier *n* ∈ N*k i.e., Pk*,*n* = **E** |*sk*,*n*| 2 .

#### 2. **Statistical CSI: Random ergodic (fast-fading) channels**.

In this model, we assume that coefficients *Hc k* (*n*, *m*) associated with each user *k* on any subcarrier *n* are time-varying, unknown at the base station side and perfectly known at the receiver side. We can thus think of {*Hk*(*n*, *m*)}*m* as a random process with a certain statistical distribution *e.g.,* Rayleigh, Rice, Nakagami, etc. We also assume that this process undergo **fast fading** *i.e.,* the coherence time of the channel is much smaller than the duration *T* of transmission of a codeword. It is thus reasonable to model {*Hk*(*n*, *m*)}*m* as an independent identically distributed (i.i.d) random ergodic process for each *n* ∈ {0... *N* − 1}. Finally, **we assume that the parameters of the distribution of this process** *i.e.,* **its mean, variance** ...**, are known at the base station, typically via feedback**.

2 A codeword typically spans several OFDM blocks *i.e.,* several time indexes *m*

3 Eventhough the noise-plus-interference *wk*(*n*, *m*) is not Gaussian in general, approximating it as a Gaussian process is widely used in the literature (see for instance Gault et al. (2005); S. Plass et al. (2004; 2006)). The reason behind that is twofold: first, the Gaussian approximation provides a lower bound on the mutual information, second it allows us to have an analytical expression for the channel capacity.

**3. Frequency reuse schemes and the frequency reuse factor: Definition and**

As we stated earlier, management of multicell interference is one of the major issues in cellular networks design and administration. This management is intimately related to the so-called *frequency-reuse scheme* adopted in the network. Indeed, choosing a frequency-reuse scheme means determining the subset of subcarriers that are available for allocation in each cell (or sector) of the network. In some reuse schemes, the whole set of subcarriers is available for allocation in all the cells of the network, while in others some subsets of subcarriers are made

Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks 109

Many reuse schemes have been proposed in the literature, differing in their complexity and in their **repetitive pattern** *i.e.,* the number of cells (or sectors) beyond which the scheme is repleted. In this chapter, we only **focus on three-cell (or three-sector) based reuse schemes**. Indeed, the level of interference experienced by users in a cellular network is related to the

*α* = number of subcarriers reused by three adjacent cells

Where *N* is the total number of subcarriers in the system. In *sectorized networks i.e.,* networks with 120 ◦-directive antennas at their base stations (see Figure 2), the definition of *α* becomes

*α* = number of subcarriers reused by three adjacent sectors

Note that in Figure 2, sectors 3,4,5 form the basic pattern of the reuse scheme that is repleted

*N* . (4)

*N* . (5)

**relation to resource allocation**

value of parameter *α* defined as

throughout the network.

Fig. 2. A sectorized cellular network

exclusive to certain cells and prohibitted for others.

Note that since the channel coefficients {*Hk*(*n*, *m*)}*m* are time-varying in this model, then each single codeword encounters a large number of channel realizations. In this case, it is a well-known result in information theory that transmission to user *k* at rate *Rk* nats/sec/Hz is possible with negligible probability of error provided that *Rk* < *Ck*, where *Ck* denotes here the channel *ergodic* capacity associated with user *k* and given (in the case of zero-mean Gaussian distributed noise-plus-interference processes *wk*(*n*, *m*) with variance *σ*2 *k* ) by

$$\mathbb{C}\_{k} = \mathbb{E}\left[\log\left(1 + P\_{k,n}\frac{|H\_{k}^{\mathbb{C}}(n,m)|^{2}}{\sigma\_{k}^{2}}\right)\right].$$

Here, expectation is taken with respect to the distribution of the random channel coefficients *Hc k* (*n*, *m*).

#### 3. **Statistical CSI: Random nonergodic (slow-fading) channels**.

In this case, channel coefficients *Hk*(*n*, *m*) = *Hk*(*n*) are assumed to be fixed during the whole transmission of any codeword, but nonetheless random and unknown by the base stations. This case is usually referred to as the **slow fading** case. It arises as the best fitting model for situations where the channel coherence time is larger than the transmission duration. We also **assume that the parameters of the distribution of the random variables** *Hk*(*n*) *i.e.,* **their mean, variance** ...**, are known at the base station via feedback**.

In contrast to the ergodic case, there is usually no way for the receiver in the nonergodic case to recover the transmitted information with negligible error probability. Assume that the base station needs to send some information to user *k* at a data rate *Rk* nats/sec/Hz. The transmitted message (if the transmitted symbols *sk*(*n*, *m*) are from a Gaussian codebook) can be decoded by the receiver provided that the required rate *Rk* is less than the mutual information between the source and the destination *i.e.,* provided that 1 *N* ∑*n*∈N*k* log 1 + *Pk*,*n* |*Hk*(*n*)| 2 *σ*2 *k* > *Rk*. If the channels realization *Hk*(*n*) is such that

$$\frac{1}{N} \sum\_{n \in \mathcal{N}\_k} \log \left( 1 + P\_{k,n} \frac{|H\_k(n)|^2}{\sigma\_k^2} \right) \le R\_{k,n}$$

then the transmitted message cannot be decoded by the receiver. In this case, user *k* link is said to be in *outage*. The event of outage occurs with the following probability:

$$P\_{O,k}(R\_k) \stackrel{\triangle}{=} \Pr\left[\frac{1}{N} \sum\_{n \in \mathcal{N}\_k} \log\left(1 + P\_{k,n} \frac{|H\_k(n)|^2}{\sigma\_k^2}\right) \le R\_k\right].\tag{3}$$

Probability *PO*,*k*(*Rk*) is commonly referred to as the *outage probability* associated with user *k*. In the context of communication over slow fading channels as described above, it is of clear interest to minimize the outage probability associated with each user.

It is worth mentioning that the above distinction between deterministic, ergodic and nonergodic channel was originally done in I. E. Telatar (1999) for Multiple-Input-Multiple-Output (MIMO) channels. We present in the sequel the main existing results on resource allocation for each one of the above signal models.

4 Will-be-set-by-IN-TECH

Gaussian distributed noise-plus-interference processes *wk*(*n*, *m*) with variance *σ*2

1 + *Pk*,*n*

Here, expectation is taken with respect to the distribution of the random channel

In this case, channel coefficients *Hk*(*n*, *m*) = *Hk*(*n*) are assumed to be fixed during the whole transmission of any codeword, but nonetheless random and unknown by the base stations. This case is usually referred to as the **slow fading** case. It arises as the best fitting model for situations where the channel coherence time is larger than the transmission duration. We also **assume that the parameters of the distribution of the random variables** *Hk*(*n*) *i.e.,* **their mean, variance** ...**, are known at the base station via**

In contrast to the ergodic case, there is usually no way for the receiver in the nonergodic case to recover the transmitted information with negligible error probability. Assume that the base station needs to send some information to user *k* at a data rate *Rk* nats/sec/Hz. The transmitted message (if the transmitted symbols *sk*(*n*, *m*) are from a Gaussian codebook) can be decoded by the receiver provided that the required rate *Rk* is less than the mutual information between the source and the destination *i.e.,* provided that

1 + *Pk*,*n*

log

said to be in *outage*. The event of outage occurs with the following probability:

then the transmitted message cannot be decoded by the receiver. In this case, user *k* link is

Probability *PO*,*k*(*Rk*) is commonly referred to as the *outage probability* associated with user *k*. In the context of communication over slow fading channels as described above, it is of clear

It is worth mentioning that the above distinction between deterministic, ergodic and nonergodic channel was originally done in I. E. Telatar (1999) for Multiple-Input-Multiple-Output (MIMO) channels. We present in the sequel the main

> *σ*2 *k*

> *Rk*. If the channels realization *Hk*(*n*) is such that

*σ*2 *k*

≤ *Rk* ,

≤ *Rk*

. (3)

*σ*2 *k*

1 + *Pk*,*n*

 .

*Ck* = **E**

3. **Statistical CSI: Random nonergodic (slow-fading) channels**.

coefficients *Hc*

**feedback**.

1

*N* ∑*n*∈N*k* log

 1 + *Pk*,*n* |*Hk*(*n*)| 2 *σ*2 *k*

*PO*,*k*(*Rk*)

1 *N* ∑ *n*∈N*k*

= Pr 1 *N* ∑ *n*∈N*k*

log

interest to minimize the outage probability associated with each user.

existing results on resource allocation for each one of the above signal models.

*k* (*n*, *m*).

 log

Note that since the channel coefficients {*Hk*(*n*, *m*)}*m* are time-varying in this model, then each single codeword encounters a large number of channel realizations. In this case, it is a well-known result in information theory that transmission to user *k* at rate *Rk* nats/sec/Hz is possible with negligible probability of error provided that *Rk* < *Ck*, where *Ck* denotes here the channel *ergodic* capacity associated with user *k* and given (in the case of zero-mean

*k* ) by

## **3. Frequency reuse schemes and the frequency reuse factor: Definition and relation to resource allocation**

As we stated earlier, management of multicell interference is one of the major issues in cellular networks design and administration. This management is intimately related to the so-called *frequency-reuse scheme* adopted in the network. Indeed, choosing a frequency-reuse scheme means determining the subset of subcarriers that are available for allocation in each cell (or sector) of the network. In some reuse schemes, the whole set of subcarriers is available for allocation in all the cells of the network, while in others some subsets of subcarriers are made exclusive to certain cells and prohibitted for others.

Many reuse schemes have been proposed in the literature, differing in their complexity and in their **repetitive pattern** *i.e.,* the number of cells (or sectors) beyond which the scheme is repleted. In this chapter, we only **focus on three-cell (or three-sector) based reuse schemes**. Indeed, the level of interference experienced by users in a cellular network is related to the value of parameter *α* defined as

$$\alpha = \frac{\text{number of subcarriers resused by three adjacent cells}}{N}. \tag{4}$$

Where *N* is the total number of subcarriers in the system. In *sectorized networks i.e.,* networks with 120 ◦-directive antennas at their base stations (see Figure 2), the definition of *α* becomes

$$\alpha = \frac{\text{number of subcarriers resused by three adjacent sectors}}{N} \,. \tag{5}$$

Note that in Figure 2, sectors 3,4,5 form the basic pattern of the reuse scheme that is repleted throughout the network.

Fig. 2. A sectorized cellular network

considered negligible. The received signal model for some user *k* in cell *c* on each subcarrier *n*

Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks 111

where process *wk*(*n*, *m*) contains **only thermal noise**. It can thus be modeled in this case as AWGN with distribution CN(0, *σ*2). Of course, the single-cell assumption is simplifying and unrealistic in real-world cellular networks where intercell interference prevails. However, in some cases one can manage to use the results of single-cell analysis as a tool to tackle the more interesting and demanding multicell problem (see for example N. Ksairi & Ciblat (2011);

Although having full (per-subcarrier) CSI at the base stations is quite unrealistic in practice as we argued in Section 2, many existing works on resource allocation for OFDMA systems resorted to this assumption. We give below the main results in the literature on resource

Consider the problem of maximizing the sum of all users achievable rates, first in a **single-cell context** (focus for example on cell *c*). This maximization should be done such that the spent power does not exceed a certain maximum value and such that the OFDMA orthogonal subcarrier assignment constraint (no subcarrier can be assigned to more than one user) is

to user *k* on subcarrier *n*. Let *P*max designates the maximal power that the base station is allowed to spend. The maximal sum rate should thus be computed under the following

It is known Tse & Visawanath (2005) that the maximum sum rate is achieved provided that

*sk*(*m*) for *m* ∈ {0, 1, . . . , *T* − 1} is an i.i.d process, and

{*Pk*,*n*}*n*∈N*k*

where *sk*(*m*), we recall, is the vector composed of the symbols {*s*(*n*, *m*)}*n*∈N*k* transmitted to user *k* during the *m*th OFDM symbol. It follows that the maximum sum rate *C*sum of the

∑*k*∈*c* 1

subject to subcarrier assignment orthogonality constraint and to (6)

Solving the above optimization problem provides us with the optimal resource allocation which maximizes the sum rate of the system. It is known from Jang & Lee (2003); Tse & Visawanath (2005), that the solution to the above problem is the so-called *multiuser water-filling*. According to this solution, the optimal subcarrier assignment {N*k*}*k*∈*c* is such

*N* ∑*n*∈N*k* log

1 + |*Hc k* (*n*)| 2 *σ*2 *Pk*,*n*

2] for any *n* ∈ N*k* as the power allocated

, (7)

 ,

*Pk*,*n* ≤ *P*max . (6)

*k* (*n*, *m*)*sk*(*n*, *m*) + *wk*(*n*, *m*),

*y*(*n*, *m*) = *Hc*

**4.1 Full-CSI resource allocation (deterministic channels)**

respected. Recall the definition of *Pk*,*n* = **E**[|*sk*(*n*, *m*)|

*sk*(*m*) ∼ CN

downlink OFDMA single cell system can be written as

*C*sum = max{N*k*,*Pk*,*n*}*k*∈*c*,*n*∈N*k*

allocation in the case of full CSI, mainly for the sake of completeness.

∑ *k*∈*c*

0, diag

the codeword *Sk* = [*sk*(0), *sk*(1), . . ., *sk*(*T* − 1)] of each user is chosen such that

∑ *n*∈N*k*

can thus be written as

N. Ksairi & Hachem (2010a)).

**1) Sum rate maximization**

constraint:

that:

Parameter *α* is called the *frequency reuse factor*. If *α* = 1, then each base station can allocate the totality of the available *N* subcarriers to its users. This policy is commonly referred to as the *all-reuse scheme* or as the *frequency-reuse-of-one scheme*. Under this policy, all users of the system are subject to multicell interference. If *α* = 0, then no subcarriers are allowed to be used simultaneously in the neighboring cells. This is the case of an *orthogonal reuse scheme*. In such a scheme, users do not experience any multicell interference.

If *α* is chosen such that 0 < *α* < 1, then we obtain the so-called *fractional frequency reuse*, see WiMAX Forum (2006). According to this frequency reuse scheme, the set of available subcarriers is partitioned into two subsets. One subset contains *αN* subcarriers that can be reused within all the cells (sectors) of the system and is thus subject to multicell interference. The other subset contains the remaining (1 − *α*)*N* subcarriers and is divided in an orthogonal way between the different cells (sectors). Such subcarriers are thus protected from interference.

The larger the value of *α*, the greater the number of available subcarriers for each base station and the higher the level of multicell interference. There is therefore a tradeoff between the number of available subcarriers (which is proportional to *α*) and the severity of the multicell interference. This tradeoff is illustrated by Figure 3. Generally speaking, the characterization

Fig. 3. Tradeoff between interference and number of available subcarriers

of the latter tradeoff is a difficult problem to solve. Most of the approaches used in the literature to tackle this problem were based on numerical simulations. Section 5 is dedicated to the issue of analytically finding the best value of *α* without resorting to such numerical approaches.

In the sequel, we assume that the frequency-reuse scheme (or the frequency-reuse factor) has already been chosen in advance prior to performing resource allocation. While Section 5 is dedicated to the issue of finding the best value of *α*.

### **4. Downlink resource allocation for WiMAX cellular networks**

In this section, we give the main existing results on the subject of downlink resource allocation for WiMAX networks. We present the literature on this subject by classifying it with respect to the specific signal models (full-CSI channels, statistical-CSI fast-fading channels, statistical-CSI slow-fading channels).

It is worth noting that many existing works on cellular resource allocation resort to the so-called **single-cell assumption**. Under this simplifying assumption, intercell interference is considered negligible. The received signal model for some user *k* in cell *c* on each subcarrier *n* can thus be written as

$$y(n,m) = H\_k^c(n,m)s\_k(n,m) + w\_k(n,m) \; .$$

where process *wk*(*n*, *m*) contains **only thermal noise**. It can thus be modeled in this case as AWGN with distribution CN(0, *σ*2). Of course, the single-cell assumption is simplifying and unrealistic in real-world cellular networks where intercell interference prevails. However, in some cases one can manage to use the results of single-cell analysis as a tool to tackle the more interesting and demanding multicell problem (see for example N. Ksairi & Ciblat (2011); N. Ksairi & Hachem (2010a)).

#### **4.1 Full-CSI resource allocation (deterministic channels)**

Although having full (per-subcarrier) CSI at the base stations is quite unrealistic in practice as we argued in Section 2, many existing works on resource allocation for OFDMA systems resorted to this assumption. We give below the main results in the literature on resource allocation in the case of full CSI, mainly for the sake of completeness.

#### **1) Sum rate maximization**

6 Will-be-set-by-IN-TECH

Parameter *α* is called the *frequency reuse factor*. If *α* = 1, then each base station can allocate the totality of the available *N* subcarriers to its users. This policy is commonly referred to as the *all-reuse scheme* or as the *frequency-reuse-of-one scheme*. Under this policy, all users of the system are subject to multicell interference. If *α* = 0, then no subcarriers are allowed to be used simultaneously in the neighboring cells. This is the case of an *orthogonal reuse scheme*. In

If *α* is chosen such that 0 < *α* < 1, then we obtain the so-called *fractional frequency reuse*, see WiMAX Forum (2006). According to this frequency reuse scheme, the set of available subcarriers is partitioned into two subsets. One subset contains *αN* subcarriers that can be reused within all the cells (sectors) of the system and is thus subject to multicell interference. The other subset contains the remaining (1 − *α*)*N* subcarriers and is divided in an orthogonal way between the different cells (sectors). Such subcarriers are thus protected

The larger the value of *α*, the greater the number of available subcarriers for each base station and the higher the level of multicell interference. There is therefore a tradeoff between the number of available subcarriers (which is proportional to *α*) and the severity of the multicell interference. This tradeoff is illustrated by Figure 3. Generally speaking, the characterization

of the latter tradeoff is a difficult problem to solve. Most of the approaches used in the literature to tackle this problem were based on numerical simulations. Section 5 is dedicated to the issue of analytically finding the best value of *α* without resorting to such numerical

In the sequel, we assume that the frequency-reuse scheme (or the frequency-reuse factor) has already been chosen in advance prior to performing resource allocation. While Section 5 is

In this section, we give the main existing results on the subject of downlink resource allocation for WiMAX networks. We present the literature on this subject by classifying it with respect to the specific signal models (full-CSI channels, statistical-CSI fast-fading channels,

It is worth noting that many existing works on cellular resource allocation resort to the so-called **single-cell assumption**. Under this simplifying assumption, intercell interference is

such a scheme, users do not experience any multicell interference.

Fig. 3. Tradeoff between interference and number of available subcarriers

**4. Downlink resource allocation for WiMAX cellular networks**

dedicated to the issue of finding the best value of *α*.

statistical-CSI slow-fading channels).

from interference.

approaches.

Consider the problem of maximizing the sum of all users achievable rates, first in a **single-cell context** (focus for example on cell *c*). This maximization should be done such that the spent power does not exceed a certain maximum value and such that the OFDMA orthogonal subcarrier assignment constraint (no subcarrier can be assigned to more than one user) is respected. Recall the definition of *Pk*,*n* = **E**[|*sk*(*n*, *m*)| 2] for any *n* ∈ N*k* as the power allocated to user *k* on subcarrier *n*. Let *P*max designates the maximal power that the base station is allowed to spend. The maximal sum rate should thus be computed under the following constraint:

$$\sum\_{k \in c} \sum\_{n \in \mathcal{N}\_k} P\_{k,n} \le P\_{\text{max}} \,. \tag{6}$$

It is known Tse & Visawanath (2005) that the maximum sum rate is achieved provided that the codeword *Sk* = [*sk*(0), *sk*(1), . . ., *sk*(*T* − 1)] of each user is chosen such that

$$\begin{aligned} \mathbf{s}\_k(m) &\text{ for } m \in \{0, 1, \dots, T - 1\} \text{ is an i.i.d process, and} \\ \mathbf{s}\_k(m) &\sim \mathfrak{CN}\left(\mathbf{0}, \text{diag}\left(\{P\_{k,n}\}\_{n \in \mathbb{N}\_k}\right)\right), \end{aligned} \tag{7}$$

where *sk*(*m*), we recall, is the vector composed of the symbols {*s*(*n*, *m*)}*n*∈N*k* transmitted to user *k* during the *m*th OFDM symbol. It follows that the maximum sum rate *C*sum of the downlink OFDMA single cell system can be written as

 $\mathsf{C}\_{\text{sum}} = \max\_{\{\mathcal{N}\_k, P\_{k,n}\}\_{k \in \iota, n \in \mathcal{N}\_k}} \sum\_{k \in \mathcal{C}} \frac{1}{N} \sum\_{n \in \mathcal{N}\_k} \log\left(1 + \frac{|H\_k^{\epsilon}(n)|^2}{\sigma^2} P\_{k,n}\right),$  subject to subcarrier assignment orthogonality constraint and to (6)

Solving the above optimization problem provides us with the optimal resource allocation which maximizes the sum rate of the system. It is known from Jang & Lee (2003); Tse & Visawanath (2005), that the solution to the above problem is the so-called *multiuser water-filling*. According to this solution, the optimal subcarrier assignment {N*k*}*k*∈*c* is such that:

ensure some level of fairness among users, one can use the maximization of a weighted sum

Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks 113

In a **single-cell scenario** (focus on cell *c*), the maximal weighted sum rate *C*weighted sum is given

where *Rk* is the data rate achieved by user *k*, and where the maximization is with respect to the resource allocation parameters and the distribution of the transmit codewords **S***k*. Weights *μk* in (10) should be chosen in such a way to compensate users with bad channel states. As in the sum rate maximization problem, it can be shown that the weighted sum rate is maximized with random Gaussian codebooks *i.e.,* when (7) holds. The optimal resource allocation parameters can thus be obtained as the solution to the following optimization

*N* ∑*n*∈N*k* log

subject to the subcarrier assignment orthogonality constraint and to (6) .

The above optimization problem is of combinatorial nature since it requires finding the optimal set N*k* of subcarriers for each user *k*. It cannot thus be solved using convex

For each subchannel assignment {N*k*}1≤*k*≤*K*, the powers *Pk*,*n* can be obtained by the so called multilevel water filling Hoo et al. (2004) with a computational cost of the order of O(*N*) operations. On the other hand, finding the optimal subcarrier assignment requires an exhaustive search and a computational complexity of the order of *KN* operations. The overall computational complexity is therefore O(*NKN*). In order to avoid this exponentially complex solution, the authors of Seong et al. (2006) state that solving the dual of the above problem (by Lagrange dual decomposition for example) entails a negligible duality gap. This idea is inspired by a recent result Yu & Lui (2006) in resource allocation for multicarrier DSL

In a **multicell scenario**, the weighted sum rate maximization problem can be written (in case

*μk*

subject to the OFDMA orthogonality constraint and to (8) ,

Here, *μk* is the weight assigned to user *k*. Since no exact solution has yet been found for the above problem, only suboptimal (with respect to the optimization criterion) approaches exist. The approach proposed in M. Pischella & J.-C. Belfiore (2008) consists in performing resource allocation via two phases: First, the users and subcarriers where the power should be set to zero are identified. This phase is done with the simplifying assumption of uniform power allocation. In the second phase, an iterative distributed algorithm called Dual Asynchronous Distributed Pricing (DADP) J. Huang et al. (2006) is applied for the remaining users under

*N* ∑*n*∈N*k* log

1 + *Pk*,*n*

 ,

the transmitted symbols of all the base stations are from Gaussian codebooks) as

∑*c* ∑*k*∈*c*

1 + *Pk*,*n*

 ,

*k*∈*c*

*μkRk* , (10)

*C*weighted sum = max ∑

of users achievable rates as the criterion of optimization of the resource allocation.

∑*k*∈*c μk*

max{N*k*,*Pk*,*n*}*k*∈*c*,*n*∈N*k*

max{N*k*,*Pk*,*n*}*c*,1≤*k*≤*Kc*,*n*∈N*k*

by:

problem:

optimization techniques.

applications.

high SINR assumption.

Each subcarrier *n* ∈ {1, 2, . . . , *N*} is assigned to the user *k*∗ *n* satisfying *k*∗ *n* = arg max*k* |*Hc k* (*n*)|.

The powers {*Pk*∗ *n*,*n*}1≤*n*≤*N* can finally be determined by water filling:

$$P\_{k\_n^\*n} = \left(\frac{1}{\lambda} - \frac{\sigma^2}{|H\_{k\_n^\*}^c(n)|^2}\right)^+.$$

where *λ* is a Lagrange multiplier chosen such that the power constraint (6) is satisfied with equality:

$$\sum\_{n=1}^{N} \left( \frac{1}{\lambda} - \frac{\sigma^2}{|H\_{k\_n^\*}^c(n)|^2} \right)^+ = P\_{\text{max}} \ . $$

In a **multicell scenario**, the above problem becomes that of maximizing the sum of data rates that can be achieved by the users of the network subject to a total network-wide power constraint

$$\sum\_{c} \sum\_{k \in c} \sum\_{n \in \mathcal{N}\_k} P\_{k,n} \le P\_{\text{max}} \,. \tag{8}$$

In case the transmitted symbols of all the base stations are from Gaussian codebooks, the sum rate maximization problem can be written as

$$\max\_{\{\mathcal{N}\_k, P\_{k, \eta}\}\_{1 \le k \le K, n \in \mathcal{N}\_k}} \sum\_{\mathcal{C}} \sum\_{k \in \mathcal{C}} \frac{1}{N} \sum\_{n \in \mathcal{N}\_k} \log \left( 1 + P\_{k, n} \frac{|H\_k^{\varepsilon}(n)|^2}{\sigma\_k^2} \right)$$

$$\text{subject to the OFDM orthogonality constraint and to (8).} \tag{9}$$

In contrast to the single cell case where the exact solution has been identified, no closed-form solution to Problem (9) exists. An approach to tackle a variant of this problem with per subcarrier peak power constraint (*Pk*,*n* ≤ *P*peak) has been proposed in Gesbert & Kountouris (2007). The proposed approach consists in performing a decentralized algorithm that maximizes an upperbound on the network sum rate. Interestingly, this upperbound is proved to be tight in the asymptotic regime when the number of users per cell is allowed to grow to infinity. However, the proposed algorithm does not guaranty fairness among the different users.

A heuristic approach to solve the problem of sum rate maximization is adopted in Lengoumbi et al. (2006). The authors propose a centralized iterative allocation scheme allowing to adjust the number of cells reusing each subcarrier. The proposed algorithm promotes allocating subcarriers which are reused by small number of cells to users with bad channel conditions. It also provides an interference limitation procedure in order to reduce the number of users whose rate requirements are unsatisfied.

#### **2) Weighted sum rate maximization**

In a wireless system, maximizing the sum rate does not guaranty any fairness between users. Indeed, users with bad channels may not be assigned any subcarriers if the aforementioned multiuser water-filling scheme is applied. Such users may have to wait long durations of time till their channel state is better to be able to communicate with the base station. In order to 8 Will-be-set-by-IN-TECH

where *λ* is a Lagrange multiplier chosen such that the power constraint (6) is satisfied with

In a **multicell scenario**, the above problem becomes that of maximizing the sum of data rates that can be achieved by the users of the network subject to a total network-wide power

In case the transmitted symbols of all the base stations are from Gaussian codebooks, the sum

In contrast to the single cell case where the exact solution has been identified, no closed-form solution to Problem (9) exists. An approach to tackle a variant of this problem with per subcarrier peak power constraint (*Pk*,*n* ≤ *P*peak) has been proposed in Gesbert & Kountouris (2007). The proposed approach consists in performing a decentralized algorithm that maximizes an upperbound on the network sum rate. Interestingly, this upperbound is proved to be tight in the asymptotic regime when the number of users per cell is allowed to grow to infinity. However, the proposed algorithm does not guaranty fairness among the different

A heuristic approach to solve the problem of sum rate maximization is adopted in Lengoumbi et al. (2006). The authors propose a centralized iterative allocation scheme allowing to adjust the number of cells reusing each subcarrier. The proposed algorithm promotes allocating subcarriers which are reused by small number of cells to users with bad channel conditions. It also provides an interference limitation procedure in order to reduce the number of users

In a wireless system, maximizing the sum rate does not guaranty any fairness between users. Indeed, users with bad channels may not be assigned any subcarriers if the aforementioned multiuser water-filling scheme is applied. Such users may have to wait long durations of time till their channel state is better to be able to communicate with the base station. In order to

∑ *n*∈N*k*

∑*c* ∑*k*∈*c* 1

+

*N* ∑*n*∈N*k* log

subject to the OFDMA orthogonality constraint and to (8) , (9)

*n*,*n*}1≤*n*≤*N* can finally be determined by water filling:

 1 *λ* − *σ*2 |*Hc k*∗ *n* (*n*)|2 *n* satisfying *k*∗

*Pk*,*n* ≤ *P*max . (8)

+ ,

= *P*max .

 1 + *Pk*,*n* *n* = arg max*k* |*Hc*

*k* (*n*)|.

Each subcarrier *n* ∈ {1, 2, . . . , *N*} is assigned to the user *k*∗

*Pk*∗ *n*,*n* =

*N* ∑ *n*=1

rate maximization problem can be written as

whose rate requirements are unsatisfied.

**2) Weighted sum rate maximization**

max{N*k*,*Pk*,*n*}1≤*k*≤*K*,*n*∈N*k*

 1 *λ* − *σ*2 |*Hc k*∗ *n* (*n*)|2

∑*c* ∑ *k*∈*c*

The powers {*Pk*∗

equality:

constraint

users.

ensure some level of fairness among users, one can use the maximization of a weighted sum of users achievable rates as the criterion of optimization of the resource allocation.

In a **single-cell scenario** (focus on cell *c*), the maximal weighted sum rate *C*weighted sum is given by:

$$\mathcal{C}\_{\text{weighted sum}} = \max \sum\_{k \in \mathcal{c}} \mu\_k \mathcal{R}\_k \,\,\,\tag{10}$$

where *Rk* is the data rate achieved by user *k*, and where the maximization is with respect to the resource allocation parameters and the distribution of the transmit codewords **S***k*. Weights *μk* in (10) should be chosen in such a way to compensate users with bad channel states. As in the sum rate maximization problem, it can be shown that the weighted sum rate is maximized with random Gaussian codebooks *i.e.,* when (7) holds. The optimal resource allocation parameters can thus be obtained as the solution to the following optimization problem:

$$\max\_{\{\mathcal{N}\_{k}, P\_{k, \mathfrak{t}}\}\_{k \in \iota, \mathfrak{c} \in \mathcal{N}\_{k}}} \sum\_{k \in \mathcal{C}} \frac{\mu\_{k}}{\mathcal{N}} \sum\_{n \in \mathcal{N}\_{k}} \log \left( 1 + P\_{k, \mathfrak{t}} \frac{|H\_{k}(n)|^{2}}{\sigma^{2}} \right),$$
 subject to the subcarrier assignments orthogonality constraint and to (6).

The above optimization problem is of combinatorial nature since it requires finding the optimal set N*k* of subcarriers for each user *k*. It cannot thus be solved using convex optimization techniques.

For each subchannel assignment {N*k*}1≤*k*≤*K*, the powers *Pk*,*n* can be obtained by the so called multilevel water filling Hoo et al. (2004) with a computational cost of the order of O(*N*) operations. On the other hand, finding the optimal subcarrier assignment requires an exhaustive search and a computational complexity of the order of *KN* operations. The overall computational complexity is therefore O(*NKN*). In order to avoid this exponentially complex solution, the authors of Seong et al. (2006) state that solving the dual of the above problem (by Lagrange dual decomposition for example) entails a negligible duality gap. This idea is inspired by a recent result Yu & Lui (2006) in resource allocation for multicarrier DSL applications.

In a **multicell scenario**, the weighted sum rate maximization problem can be written (in case the transmitted symbols of all the base stations are from Gaussian codebooks) as

$$\max\_{\{\mathcal{N}\_k, P\_{k, \boldsymbol{\eta}}\}\_{\boldsymbol{c}, 1 \le k \le K} \le \boldsymbol{c}} \sum\_{k \in \mathcal{C}} \sum\_{\boldsymbol{k} \in \mathcal{N}\_k} \frac{\mu\_k}{\sum\_{\boldsymbol{n} \in \mathcal{N}\_k} \log \left(1 + P\_{\boldsymbol{k}, \boldsymbol{\eta}} \frac{|H\_{\boldsymbol{k}}^{\boldsymbol{c}}(\boldsymbol{n})|^2}{\sigma\_{\boldsymbol{k}}^2} \right)}{\text{subject to the OFDM orthogonality constraint and to (8)}.$$

Here, *μk* is the weight assigned to user *k*. Since no exact solution has yet been found for the above problem, only suboptimal (with respect to the optimization criterion) approaches exist. The approach proposed in M. Pischella & J.-C. Belfiore (2008) consists in performing resource allocation via two phases: First, the users and subcarriers where the power should be set to zero are identified. This phase is done with the simplifying assumption of uniform power allocation. In the second phase, an iterative distributed algorithm called Dual Asynchronous Distributed Pricing (DADP) J. Huang et al. (2006) is applied for the remaining users under high SINR assumption.

*real-world wireless communication systems. Even if the wireless system allows that amount of feedback, it is not clear yet whether the benefit obtained by this additional complexity would outweigh the additional costs due to the resulting control traffic Sta´czak et al. (2009). For these reasons, most of the above mentioned resource allocation techniques which assume perfect CSI have not been adopted in*

Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks 115

**Remark 2.** *So far, it was assumed throughout the previous subsection that all the subcarriers* {1, 2, . . . , *N*} *are available to the users of each cell* i.e., *a frequency reuse of one is assumed. Resource*

Several works such as Brah et al. (2007; 2008); I.C. Wong & B.L. Evans (2009); Wong & Evans (2007) consider the problem of ergodic sum-rate and ergodic weighted sum-rate maximization in WiMAX-like networks. However, these works do not provide analytical solutions to these optimization problems. Instead, they resort to suboptimal (and rather computationally-complex) *duality techniques*. This is why we focus in the sequel on a **special case** of the average-rate resource allocation problem where closed-form characterization of the *optimal* solution has been provided in N. Ksairi & Ciblat (2011); N. Ksairi & Hachem (2010a;b). In particular, we highlight the methodology adopted in these recent works and which consists in using the single-cell results as a tool to solve the more involved multicell allocation problem. Consider the the **downlink of a sectorized WiMAX cellular system composed of hexagonal cells** as shown in Figure 2. Assume that the **fractional frequency reuse (FFR) scheme** illustrated in Figure 4 is adopted. Due to this scheme, a certain subset of subcarriers I ⊂ {1, 2, . . . , *N*} (I as in Interference) is reused in the three cells. If user *k* modulates such a subcarrier *n* ∈ I, process *wk*(*n*, *m*) will contain both thermal noise and multicell interference. Recall the definition of the reuse factor *α* given by (5) as the ratio between the number of

**4.2 Average-rate multicell resource allocation in the case of (statistical-CSI fast-fading**

*allocation under fractional frequency reuse is addressed in the next subsection.*

*practice.*

**channels)**

Fig. 4. Frequency reuse scheme

reused subcarriers and the total number of available subcarriers:

*α* = card(I) *N* .

#### **3) Power minimization with individual rate constraints**

Now assume that each user *k* has a data rate requirement equal to *Rk* in a **signel-cell scenario** (we focus on cell *c*). The subcarriers N*k* and the transmit powers {*Pk*,*n*}*n*∈N*k* assigned to user *k* should thus be chosen such that the following constraint is satisfied:

$$R\_k < \mathbb{C}\_k = \frac{1}{N} \sum\_{n \in \mathcal{N}\_k} \log \left( 1 + P\_{k,n} \frac{|H\_k(n)|^2}{\sigma^2} \right) \tag{11}$$

and such that the total transmit power is minimal. Here, *Ck* is the maximal rate per channel use that can be achieved by user *k* when assigned N*k* and {*Pk*,*n*}*n*∈N*k* . This maximal rate is achieved for each user by using random Gaussian codebooks as in (7). The resource allocation problem can be formulated in this case as follows:

$$\min\_{\{\mathcal{N}\_{k}, \mathcal{R}\_{k, \mathfrak{r}}\}\_{k \in \mathcal{L} \times \mathcal{N}\_{k}}} \sum\_{k \in \mathcal{L}} \sum\_{n \in \mathcal{N}\_{k}} P\_{k,n}$$
 such that the subcarrier assignments orthogonality constraint and (11) are satisfied.

Some approaches to solve this combinatorial optimization problem can be found in Kivanc et al. (2003). However, these approaches are heuristic and result in suboptimal solutions to the above problem.

In order to avoid the high computational complexity required for solving combinatorial optimization problems, one alternative consists in relaxing the subcarrier assignment constraint by introducing the notion of subcarrier time-sharing as in Wong et al. (1999). According to this notion, each subcarrier *n* can be orthogonally time-shared by more than one user, with each user *k* modulating the subcarrier during an amount of time proportional to *γk*,*n*. Here, {*γk*,*n*}*k*,*n* are real number from the interval [0, 1] satisfying

$$\forall n \in \{1, 2, \ldots, N\}, \sum\_{k=1}^{K} \gamma\_{k, \mathbb{N}} \le 1. \tag{12}$$

The rate constraint of user *k* becomes

$$R\_k < \sum\_{n=1}^{N} \gamma\_{k,n} \log \left( 1 + P\_{k,n} \frac{|H\_k(n)|^2}{\sigma^2} \right) \,. \tag{13}$$

The optimal value of the new resource allocation parameters can be obtained as the solution to the following optimization problem:

$$\min\_{\{\gamma\_{k,n}P\_{k,n}\}\_{1\le k\le K,1\le n\le N}} \Sigma\_{k=1}^{K} \sum\_{n=1}^{N} \gamma\_{k,n} P\_{k,n}$$
 such that constraints (12) and (13) are satisfied.

The above problem can be easily transformed into a convex optimization problem by a simple change of variables. One can therefore use usual convex optimization tools to find its solution.

**Remark 1.** *It is worth mentioning here that the assumption of per-subcarrier full CSI at the transmitters is quite unrealistic in practice. First of all, it requires large amounts of feedback messages from the different users to their respective base stations, which is not practically possible in most* 10 Will-be-set-by-IN-TECH

Now assume that each user *k* has a data rate requirement equal to *Rk* in a **signel-cell scenario** (we focus on cell *c*). The subcarriers N*k* and the transmit powers {*Pk*,*n*}*n*∈N*k* assigned to user *k*

> log

and such that the total transmit power is minimal. Here, *Ck* is the maximal rate per channel use that can be achieved by user *k* when assigned N*k* and {*Pk*,*n*}*n*∈N*k* . This maximal rate is achieved for each user by using random Gaussian codebooks as in (7). The resource allocation

such that the subcarrier assignment orthogonality constraint and (11) are satisfied.

Some approaches to solve this combinatorial optimization problem can be found in Kivanc et al. (2003). However, these approaches are heuristic and result in suboptimal solutions to

In order to avoid the high computational complexity required for solving combinatorial optimization problems, one alternative consists in relaxing the subcarrier assignment constraint by introducing the notion of subcarrier time-sharing as in Wong et al. (1999). According to this notion, each subcarrier *n* can be orthogonally time-shared by more than one user, with each user *k* modulating the subcarrier during an amount of time proportional

> *K* ∑ *k*=1

1 + *Pk*,*n*

*k*=1 ∑*N*

*n*=1 *γk*,*nPk*,*n*

1 + *Pk*,*n*

∑*k*∈*c* ∑*n*∈N*k Pk*,*n*

. (13)

, (11)

*σ*2

**3) Power minimization with individual rate constraints**

should thus be chosen such that the following constraint is satisfied:

*N* ∑ *n*∈N*k*

min{N*k*,*Pk*,*n*}*k*∈*c*,*n*∈N*k*

to *γk*,*n*. Here, {*γk*,*n*}*k*,*n* are real number from the interval [0, 1] satisfying

*N* ∑ *n*=1

*Rk* <

∀*n* ∈ {1, 2, . . . , *N*},

*γk*,*n* log

min{*γk*,*n*,*Pk*,*n*}1≤*k*≤*K*,1≤*n*≤*N* ∑*K*

The optimal value of the new resource allocation parameters can be obtained as the solution

such that constraints (12) and (13) are satisfied.

The above problem can be easily transformed into a convex optimization problem by a simple change of variables. One can therefore use usual convex optimization tools to find its solution. **Remark 1.** *It is worth mentioning here that the assumption of per-subcarrier full CSI at the transmitters is quite unrealistic in practice. First of all, it requires large amounts of feedback messages from the different users to their respective base stations, which is not practically possible in most*

*Rk* < *Ck* = 1

problem can be formulated in this case as follows:

the above problem.

The rate constraint of user *k* becomes

to the following optimization problem:

*real-world wireless communication systems. Even if the wireless system allows that amount of feedback, it is not clear yet whether the benefit obtained by this additional complexity would outweigh the additional costs due to the resulting control traffic Sta´czak et al. (2009). For these reasons, most of the above mentioned resource allocation techniques which assume perfect CSI have not been adopted in practice.*

**Remark 2.** *So far, it was assumed throughout the previous subsection that all the subcarriers* {1, 2, . . . , *N*} *are available to the users of each cell* i.e., *a frequency reuse of one is assumed. Resource allocation under fractional frequency reuse is addressed in the next subsection.*

#### **4.2 Average-rate multicell resource allocation in the case of (statistical-CSI fast-fading channels)**

Several works such as Brah et al. (2007; 2008); I.C. Wong & B.L. Evans (2009); Wong & Evans (2007) consider the problem of ergodic sum-rate and ergodic weighted sum-rate maximization in WiMAX-like networks. However, these works do not provide analytical solutions to these optimization problems. Instead, they resort to suboptimal (and rather computationally-complex) *duality techniques*. This is why we focus in the sequel on a **special case** of the average-rate resource allocation problem where closed-form characterization of the *optimal* solution has been provided in N. Ksairi & Ciblat (2011); N. Ksairi & Hachem (2010a;b). In particular, we highlight the methodology adopted in these recent works and which consists in using the single-cell results as a tool to solve the more involved multicell allocation problem.

Consider the the **downlink of a sectorized WiMAX cellular system composed of hexagonal cells** as shown in Figure 2. Assume that the **fractional frequency reuse (FFR) scheme** illustrated in Figure 4 is adopted. Due to this scheme, a certain subset of subcarriers I ⊂ {1, 2, . . . , *N*} (I as in Interference) is reused in the three cells. If user *k* modulates such a subcarrier *n* ∈ I, process *wk*(*n*, *m*) will contain both thermal noise and multicell interference. Recall the definition of the reuse factor *α* given by (5) as the ratio between the number of

Fig. 4. Frequency reuse scheme

reused subcarriers and the total number of available subcarriers:

$$\mathfrak{a} = \frac{\text{card}(\mathfrak{I})}{N} \text{ .}$$

or frequency hopping (which are both supported in the WiMAX standard 5). Finally, let *σ*2

Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks 117

*σ*2 if *n* ∈ P*c*

and user *k* of cell *A* at subcarrier *n* and OFDM block *m*. Of course, the average channel gains

Now, let *gk*,I (resp. *gk*,P) be the channel Gain-to-Noise Ratio (GNR) for user *k* in band I (resp.

user *k* given th interference levels generated by base stations *B*, *C* are equal to *QB*,I, *QC*,I

The ergodic capacity associated with *k* in the whole band is equal to the sum of the ergodic capacities corresponding to both bands I and P*A*. For instance, the part of the capacity

1 + *Pk*,P

where factor *γk*,P traduces the fact that the capacity increases with the number of subcarriers which are modulated by user *k*. In the latter expression, the expectation is calculated with

*gk*,P*Z*, where *Z* is a standard exponentially-distributed random variable. Finally, the ergodic

Assume that user *k* has an *average* rate requirement *Rk* (nats/s/Hz). This requirement is

5 In WiMAX, one of the types of subchannelization *i.e.,* grouping subcarriers to form a subchannel, is *diversirty permutation*. This method draws subcarriers pseudorandomly, thereby resulting in

|*HC k* (*n*, *m*)|

*k* (*QB*,I, *QC*,I) *gk*,P = *ρk*

*k* (*QB*,I, *QC*,I) is the variance of the noise-plus-interference process associated with

|*HA k* (*n*, *m*)| 2

*k* (*m*,*n*)| 2

*σ*2

+ *γk*,P**E**

 ,

log

(*γk*,I*Pk*,I + *γk*,P*Pk*,P) (19)

*Rk* < *Ck*(*γk*,I, *γk*,P, *Pk*,I, *Pk*,P, *QB*,I, *QC*,I). (18)

*k* (*n*, *m*)) represents the channel between base station *B* (resp. *C*)

2 *QC*

1 if *n* ∈ I

depend on the position of user *k* via the

*σ*2 ,

*σ*2 has the same distribution as *ρk*

1 + *gk*,P*Pk*,P*Z*

(16)

*σ*2 *Z* =

. (17)

2 *QB* 1 + **E**

|*HC k* (*n*, *m*)| 2

*σ*2

designate the variance of the thermal noise. Putting all pieces together:

|*HB k* (*n*, *m*)|

*gk*,I(*QB*,I, *QC*,I) = *ρk*

**E**

where *HB*

path loss model.

P*c*), namely

where *σ*2

respectively.

**E** |*HA k* (*n*, *m*)| |*wk*(*n*, *m*)|

*σ*2

*k* (*n*, *m*) (resp. *HC*

2 , **E** |*HB k* (*n*, *m*)| 2 and **E**

respect to random variable |*HA*

*γk*,I**E**

Finally, the quantity *Qc* defined by

capacity in the whole bandwidth is equal to

log

2 =

*k* = *σ*2 + **E**

corresponding to the protected band P*A* is equal to

*γk*,P**E**

*Ck*(*γk*,I, *γk*,P, *Pk*,I, *Pk*,P, *QB*,I, *QC*,I) =

satisfied provided that *Rk* is less that the ergodic capacity *Ck i.e.,*

 log

*k* (*m*,*n*)| 2 *σ*2 . Now, |*HA*

1 + *gk*,I(*QB*,I, *QC*,I)*Pk*,I*Z*

*Qc* = ∑ *k*∈*c*

interference averaging as explained in Byeong Gi Lee & Sunghyun Choi (2008)

Note that I contains *αN* subcarriers. The remaining (1 − *α*)*N* subcarriers are shared by the three sectors in an orthogonal way, such that each base stations *c* has at its disposal a subset P*c* (P as in Protected) of cardinality 1−*α* 3 *N*. If user *k* modulates a subcarrier *n* ∈ P*c*, then process *wk*(*n*, *m*) will contain only thermal noise with variance *σ*2. Finally,

$$\mathcal{I} \cup \mathcal{P}\_A \cup \mathcal{P}\_B \cup \mathcal{P}\_C = \{0, 1, \dots, N - 1\}\text{ .}$$

Also assume that **channel coefficients** {*Hc k* (*n*, *m*)}*n*∈N*k* **are Rayleigh distributed and have the same variance** *ρc k* = **E** |*Hc k*(*n*, *m*)| 2 , ∀*n* ∈ N*k*. This assumption is realistic in cases where the propagation environment is **highly scattering**, leading to decorrelated Gaussian-distributed time-domain channel taps. Under all the aforementioned assumptions, it can be shown that the ergodic capacity associated with each user *k* **only** depends on the **number of subcarriers** assigned to user *k* in subsets I and P*c* respectively, rather than on the **specific** subcarriers assigned to *k*.

The resource allocation parameters for user *k* are thus:

i) The sharing factors *γk*,I, *γk*,P defined by

$$\gamma\_{k,\mathcal{I}}^{\varepsilon} = \mathsf{card}(\mathcal{I} \cap \mathsf{N}\_{k}) / N \qquad \gamma\_{k,\mathcal{P}}^{\varepsilon} = \mathsf{card}(\mathcal{P}\_{\mathcal{C}} \cap \mathsf{N}\_{k}) / N \,. \tag{14}$$

ii) The powers *Pk*,I, *Pk*,P transmitted on the subcarriers assigned to user *k* in I and P*c* respectively.

We assume from now on that *γk*,I and *γk*,P can take on any value in the interval [0, 1] (not necessarily integer multiples of 1/*N*).

**Remark 3.** *Even though the sharing factors in our model are not necessarily integer multiples of* 1/*N, it is still possible to practically achieve the exact values of γk*,I*, γk*,P *by simply exploiting the time dimension. Indeed, the number of subcarriers assigned to user k can be chosen to vary from one OFDM symbol to another in such a way that the* average *number of subcarriers in subsets* I*,* P*c is equal to γk*,I*N, γk*,P*N respectively. Thus the fact that γk*,I*, γk*,P *are not strictly integer multiples of* 1/*N is not restrictive, provided that the system is able to grasp the benefits of the time dimension. The particular case where the number of subcarriers is restricted to be the same in each OFDM block is addressed in N. Ksairi & Ciblat (2011).*

The sharing factors of the different users should be selected such that

$$\sum\_{k \in \mathfrak{c}} \gamma\_{k, \mathcal{I}} \le \mathfrak{a} \qquad \sum\_{k \in \mathfrak{c}} \gamma\_{k, \mathcal{P}} \le \frac{1 - \mathfrak{a}}{\mathfrak{3}}.\tag{15}$$

We now describe the adopted model for the multicell interference. Consider one of the non protected subcarriers *n* assigned to user *k* of cell *A* in subset I. Denote by *σ*2 *k* the variance of the additive noise process *wk*(*n*, *m*) in this case. This variance is assumed to be constant w.r.t both *n* and *m*. It only depends on the position of user *k* and the average powers 4 *QB*,I = ∑*k*∈*B γk*,I*Pk*,I and *QC*,I = ∑*k*∈*C γk*,I*Pk*,I transmitted respectively by base stations *B* and *C* in I. This assumption is valid in OFDMA systems that adopt random subcarrier assignment

4 The dependence of interference power on only the average powers transmitted by the interfering cells rather than on the power of each single user in these cells is called *interference averaging*

12 Will-be-set-by-IN-TECH

Note that I contains *αN* subcarriers. The remaining (1 − *α*)*N* subcarriers are shared by the three sectors in an orthogonal way, such that each base stations *c* has at its disposal a subset

I ∪ P*A* ∪ P*B* ∪ P*C* = {0, 1, . . . , *N* − 1} .

propagation environment is **highly scattering**, leading to decorrelated Gaussian-distributed time-domain channel taps. Under all the aforementioned assumptions, it can be shown that the ergodic capacity associated with each user *k* **only** depends on the **number of subcarriers** assigned to user *k* in subsets I and P*c* respectively, rather than on the **specific** subcarriers

ii) The powers *Pk*,I, *Pk*,P transmitted on the subcarriers assigned to user *k* in I and P*c*

We assume from now on that *γk*,I and *γk*,P can take on any value in the interval [0, 1] (not

**Remark 3.** *Even though the sharing factors in our model are not necessarily integer multiples of* 1/*N, it is still possible to practically achieve the exact values of γk*,I*, γk*,P *by simply exploiting the time dimension. Indeed, the number of subcarriers assigned to user k can be chosen to vary from one OFDM symbol to another in such a way that the* average *number of subcarriers in subsets* I*,* P*c is equal to γk*,I*N, γk*,P*N respectively. Thus the fact that γk*,I*, γk*,P *are not strictly integer multiples of* 1/*N is not restrictive, provided that the system is able to grasp the benefits of the time dimension. The particular case where the number of subcarriers is restricted to be the same in each OFDM block is*

process *wk*(*n*, *m*) will contain only thermal noise with variance *σ*2. Finally,

2

*k*,I = card(I ∩ N*k*)/*N γc*

The sharing factors of the different users should be selected such that

*γk*,I ≤ *α* ∑

protected subcarriers *n* assigned to user *k* of cell *A* in subset I. Denote by *σ*2

rather than on the power of each single user in these cells is called *interference averaging*

*k*∈*c*

We now describe the adopted model for the multicell interference. Consider one of the non

the additive noise process *wk*(*n*, *m*) in this case. This variance is assumed to be constant w.r.t both *n* and *m*. It only depends on the position of user *k* and the average powers 4 *QB*,I = ∑*k*∈*B γk*,I*Pk*,I and *QC*,I = ∑*k*∈*C γk*,I*Pk*,I transmitted respectively by base stations *B* and *C* in I. This assumption is valid in OFDMA systems that adopt random subcarrier assignment

4 The dependence of interference power on only the average powers transmitted by the interfering cells

*γk*,P ≤

1 − *α*

∑ *k*∈*c* 3 *N*. If user *k* modulates a subcarrier *n* ∈ P*c*, then

*k* (*n*, *m*)}*n*∈N*k* **are Rayleigh distributed and have the**

*k*,P = card(P*c* ∩ N*k*)/*N* . (14)

3 . (15)

*k* the variance of

, ∀*n* ∈ N*k*. This assumption is realistic in cases where the

P*c* (P as in Protected) of cardinality 1−*α*

Also assume that **channel coefficients** {*Hc*

i) The sharing factors *γk*,I, *γk*,P defined by *γc*

necessarily integer multiples of 1/*N*).

*addressed in N. Ksairi & Ciblat (2011).*

The resource allocation parameters for user *k* are thus:

*k* = **E**

**same variance** *ρc*

assigned to *k*.

respectively.

or frequency hopping (which are both supported in the WiMAX standard 5). Finally, let *σ*2 designate the variance of the thermal noise. Putting all pieces together:

$$\begin{cases} |w\_k(n,m)|^2 \Big| = \\ \sigma\_k^2 = \sigma^2 + \mathbb{E}\left[|H\_k^B(n,m)|^2\right]Q\_1^B + \mathbb{E}\left[|H\_k^C(n,m)|^2\right]Q\_1^C \text{ if } n \in \mathcal{I} \end{cases} \tag{16}$$

where *HB k* (*n*, *m*) (resp. *HC k* (*n*, *m*)) represents the channel between base station *B* (resp. *C*) and user *k* of cell *A* at subcarrier *n* and OFDM block *m*. Of course, the average channel gains **E** |*HA k* (*n*, *m*)| 2 , **E** |*HB k* (*n*, *m*)| 2 and **E** |*HC k* (*n*, *m*)| 2 depend on the position of user *k* via the path loss model.

Now, let *gk*,I (resp. *gk*,P) be the channel Gain-to-Noise Ratio (GNR) for user *k* in band I (resp. P*c*), namely

$$\mathbf{g}\_{k,\mathcal{I}}(\mathbf{Q}\_{B,\mathcal{I}\prime}\mathbf{Q}\_{\mathbb{C},\mathcal{I}}) = \frac{\rho\_k}{\sigma\_k^2(\mathbf{Q}\_{B,\mathcal{I}\prime}\mathbf{Q}\_{\mathbb{C},\mathcal{I}})} \qquad \mathbf{g}\_{k,\mathcal{P}} = \frac{\rho\_k}{\sigma^2} \ \mathbf{J}$$

where *σ*2 *k* (*QB*,I, *QC*,I) is the variance of the noise-plus-interference process associated with user *k* given th interference levels generated by base stations *B*, *C* are equal to *QB*,I, *QC*,I respectively.

The ergodic capacity associated with *k* in the whole band is equal to the sum of the ergodic capacities corresponding to both bands I and P*A*. For instance, the part of the capacity corresponding to the protected band P*A* is equal to

$$\gamma\_{k, \mathcal{P}} \mathbb{E}\left[\log\left(1 + P\_{k, \mathcal{P}} \frac{|H\_k^A(n, m)|^2}{\sigma^2}\right)\right] \neq 0$$

where factor *γk*,P traduces the fact that the capacity increases with the number of subcarriers which are modulated by user *k*. In the latter expression, the expectation is calculated with respect to random variable |*HA k* (*m*,*n*)| 2 *σ*2 . Now, |*HA k* (*m*,*n*)| 2 *σ*2 has the same distribution as *ρk σ*2 *Z* = *gk*,P*Z*, where *Z* is a standard exponentially-distributed random variable. Finally, the ergodic capacity in the whole bandwidth is equal to

$$\begin{array}{c} \mathbb{C}\_{k}(\gamma\_{k,\mathcal{I}},\gamma\_{k,\mathcal{P}},P\_{k,\mathcal{I}},P\_{k,\mathcal{P}},Q\_{\mathcal{B},\mathcal{I}},Q\_{\mathcal{C},\mathcal{I}}) = \\ \gamma\_{k,\mathcal{I}}\mathbb{E}\left[\log\left(1+g\_{k,\mathcal{I}}(Q\_{\mathcal{B},\mathcal{I}},Q\_{\mathcal{C},\mathcal{I}})P\_{k,\mathcal{I}}Z\right)\right] + \gamma\_{k,\mathcal{P}}\mathbb{E}\left[\log\left(1+g\_{k,\mathcal{P}}P\_{k,\mathcal{P}}Z\right)\right] \ . \end{array} \tag{17}$$

Assume that user *k* has an *average* rate requirement *Rk* (nats/s/Hz). This requirement is satisfied provided that *Rk* is less that the ergodic capacity *Ck i.e.,*

$$\mathcal{R}\_k < \mathbb{C}\_k \left( \gamma\_{k, \mathcal{I}\prime} \gamma\_{k, \mathcal{P}\prime} P\_{k, \mathcal{I}\prime} P\_{k, \mathcal{P}\prime} Q\_{\mathcal{B}, \mathcal{I}\prime} Q\_{\mathcal{C}, \mathcal{I}} \right) \,. \tag{18}$$

Finally, the quantity *Qc* defined by

$$Q\_{\mathcal{C}} = \sum\_{k \in \mathcal{c}} (\gamma\_{k,\mathcal{I}} P\_{k,\mathcal{I}} + \gamma\_{k,\mathcal{P}} P\_{k,\mathcal{P}}) \tag{19}$$

5 In WiMAX, one of the types of subchannelization *i.e.,* grouping subcarriers to form a subchannel, is *diversirty permutation*. This method draws subcarriers pseudorandomly, thereby resulting in interference averaging as explained in Byeong Gi Lee & Sunghyun Choi (2008)

a given user *k* in this cell, we designate by (*xk*, *yk*) its coordinates in the Cartesian coordinate system whose origin is at the position of base station *A* and which is illustrated in Figure 5. In

Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks 119

the proposed allocation scheme, user *k* modulates in the interference subset I if and only if

Inversely, the user modulates in the interference-free subset P*A* if and only if

that the separating curves are carefully chosen as will be discussed later on.

the cell and its users are protected from multicell interference.

*yk* < *dθ A* (*xk* ).

*yk* ≥ *dθ A* (*xk*) Therefore, we have defined in each sector two geographical regions: the first is around the base station and its users are subject to multicell interference; the second is near the border of

The resource allocation parameters {*γk*,P, *Pk*,P} for the users of the three protected regions can be easily determined by solving three **independent** convex resource allocation problems. In solving these problems, there is no interaction between the three sectors thanks to the absence of multicell interference for the protected regions. The closed-form solution to these problems

However, the resource allocation parameters {*γk*,I, *Pk*,I} of users of the non-protected interior regions should be **jointly** optimized in the three sectors. Fortunately, a **distributed iterative** algorithm is proposed in N. Ksairi & Ciblat (2011) to solve this joint optimization problem. This iterative algorithm belongs to the family of **best dynamic response** algorithms. At each iteration, we solve in each sector a single-cell allocation problem given a fixed level of multicell interference generated by the other two sectors in the previous iteration. The mild conditions for the convergence of this algorithm are provided in N. Ksairi & Ciblat (2011). Indeed, it is shown that the algorithm converges for all realistic average data rate requirements provided

**Determination of the separation curves and asymptotic optimality of the proposed scheme** It is obvious that the above proposed resource allocation algorithm is **suboptimal** since it forces a "binary" separation of users into protected and non-protected groups. Nonetheless, it has been proved in N. Ksairi & Ciblat (2011) that this binary separation is **asymptotically**

Fig. 5. Separation curve in cell *A*

is given in N. Ksairi & Ciblat (2011).

denotes the average power spent by base station *c* during one OFDM block.

Table 1. Some notations for cell *c*

#### **Optimization problem**

The joint resource allocation problem that we consider consists in minimizing the power that should be spent by the three base stations *A*, *B*, *C* in order to satisfy all users' rate requirements:

$$\min\_{\{\gamma\_{k,\mathcal{I}},\gamma\_{k,\mathcal{P}},P\_{k,\mathcal{I}},P\_{k,\mathcal{P}}\}\_{k=1\ldots k}} \sum\_{c=A,B,\subset} \sum\_{k\in c} \gamma\_{k,\mathcal{I}} P\_{k,\mathcal{I}} + \gamma\_{k,\mathcal{P}} P\_{k,\mathcal{P}}$$

$$\text{subject to constraints (15) and (18)}.\tag{20}$$

This problem is not convex with repsect to the resource allocation parameters. It cannot thus be solved using convex optimization tools. Fortunately, it has been shown in N. Ksairi & Ciblat (2011) that a resource allocation algorithm can be proposed that is **asymptotically optimal** *i.e.,* the transmit power it requires to satisfy users' rate requirements is equal to the transmit power of an **optimal** solution to the above problem **in the limit of large numbers of users**. We present in the sequel this allocation algorithm, and we show that it can be implemented in a distributed fashion and that it has relatively low computational complexity.

#### **Practical resource allocation scheme**

In the proposed scheme we force the users near the cell's borders (who are normally subject to sever fading conditions and to high levels of multicell interference) to modulate uniquely the subcarriers in the protected subset P*c*, while we require that the users in the interior of the cell (who are closer to the base station and suffer relatively low levels on intercell interference) to modulate uniquely subcarriers in the interference subset I.

Of course, we still need to define a **separating curve** that split the users of the cell into these two groups of interior and exterior users. For that sake, we define on **R**5 + × **R** the function

$$(\theta, \mathfrak{x}) \mapsto d\_{\theta}(\mathfrak{x})$$

where *x* ∈ **R** and where *θ* is a set of parameters6. We use this function to define the separation curves *dθ A* , *dθB* and *dθC* for cells *A*, *B* and *C* respectively. The determination of parameters *θA*, *θB* and *θC* is discussed later on. Without any loss of generality, let us now focus on cell *A*. For

6 The closed-form expression of function *dθ* (*x*) is provided in N. Ksairi & Ciblat (2011).

a given user *k* in this cell, we designate by (*xk*, *yk*) its coordinates in the Cartesian coordinate system whose origin is at the position of base station *A* and which is illustrated in Figure 5. In

Fig. 5. Separation curve in cell *A*

14 Will-be-set-by-IN-TECH

P*c* subset of interference-free subcarriers that are exclusively reserved for cell *c*

The joint resource allocation problem that we consider consists in minimizing the power that should be spent by the three base stations *A*, *B*, *C* in order to satisfy all users' rate

min{*γk*,I,*γk*,P,*Pk*,I,*Pk*,P}*k*=1...*K* ∑*c*=*A*,*B*,*C* ∑*k*∈*c γk*,I*Pk*,I + *γk*,P*Pk*,P

This problem is not convex with repsect to the resource allocation parameters. It cannot thus be solved using convex optimization tools. Fortunately, it has been shown in N. Ksairi & Ciblat (2011) that a resource allocation algorithm can be proposed that is **asymptotically optimal** *i.e.,* the transmit power it requires to satisfy users' rate requirements is equal to the transmit power of an **optimal** solution to the above problem **in the limit of large numbers of users**. We present in the sequel this allocation algorithm, and we show that it can be implemented in

In the proposed scheme we force the users near the cell's borders (who are normally subject to sever fading conditions and to high levels of multicell interference) to modulate uniquely the subcarriers in the protected subset P*c*, while we require that the users in the interior of the cell (who are closer to the base station and suffer relatively low levels on intercell interference) to

Of course, we still need to define a **separating curve** that split the users of the cell into these

(*θ*, *x*) �→ *dθ* (*x*)

where *x* ∈ **R** and where *θ* is a set of parameters6. We use this function to define the separation curves *dθ A* , *dθB* and *dθC* for cells *A*, *B* and *C* respectively. The determination of parameters *θA*, *θB* and *θC* is discussed later on. Without any loss of generality, let us now focus on cell *A*. For

a distributed fashion and that it has relatively low computational complexity.

two groups of interior and exterior users. For that sake, we define on **R**5

6 The closed-form expression of function *dθ* (*x*) is provided in N. Ksairi & Ciblat (2011).

modulate uniquely subcarriers in the interference subset I.

subject to constraints (15) and (18) . (20)

+ × **R** the function

denotes the average power spent by base station *c* during one OFDM block.

*Qc*,I, *Qc*,P power transmitted by base station *c* in bands I, P*A* resp.

*Rk* rate requirement of user *k* in nats/s/Hz *Ck* ergodic capacity associated with user *k gk*,I, *gk*,P GNR of user *k* in bands I, P*A* resp.

*γk*,I, *γk*,P sharing factors of user *k* in bands I, P*c* resp. *Pk*,I, *Pk*,P power allocated to user *k* in bands I, P*A* resp.

*Qc* total power transmitted by base station *c*

Table 1. Some notations for cell *c*

**Practical resource allocation scheme**

**Optimization problem**

requirements:

I subset of reused subcarriers that are subject to multicell interference

the proposed allocation scheme, user *k* modulates in the interference subset I if and only if

$$y\_k < d\_{\theta^A}(\mathfrak{x}\_k)\,.$$

Inversely, the user modulates in the interference-free subset P*A* if and only if

$$y\_k \ge d\_{\theta^A}(\mathfrak{x}\_k)$$

Therefore, we have defined in each sector two geographical regions: the first is around the base station and its users are subject to multicell interference; the second is near the border of the cell and its users are protected from multicell interference.

The resource allocation parameters {*γk*,P, *Pk*,P} for the users of the three protected regions can be easily determined by solving three **independent** convex resource allocation problems. In solving these problems, there is no interaction between the three sectors thanks to the absence of multicell interference for the protected regions. The closed-form solution to these problems is given in N. Ksairi & Ciblat (2011).

However, the resource allocation parameters {*γk*,I, *Pk*,I} of users of the non-protected interior regions should be **jointly** optimized in the three sectors. Fortunately, a **distributed iterative** algorithm is proposed in N. Ksairi & Ciblat (2011) to solve this joint optimization problem. This iterative algorithm belongs to the family of **best dynamic response** algorithms. At each iteration, we solve in each sector a single-cell allocation problem given a fixed level of multicell interference generated by the other two sectors in the previous iteration. The mild conditions for the convergence of this algorithm are provided in N. Ksairi & Ciblat (2011). Indeed, it is shown that the algorithm converges for all realistic average data rate requirements provided that the separating curves are carefully chosen as will be discussed later on.

#### **Determination of the separation curves and asymptotic optimality of the proposed scheme**

It is obvious that the above proposed resource allocation algorithm is **suboptimal** since it forces a "binary" separation of users into protected and non-protected groups. Nonetheless, it has been proved in N. Ksairi & Ciblat (2011) that this binary separation is **asymptotically**

transmit power when the asymptotically optimal separating curves are used, is compared in Figure 7 to the performance of an all-reuse scheme (*α* = 1) that has been proposed in Thanabalasingham et al. (2006). It is worth mentioning that the reuse factor *α* assumed for our algorithm in Figure 7 has been obtained using the procedure described in Section 5. It is clear from the figure that a significant gain in performance can be obtained from applying a carefully designed FFR allocation algorithm (such as ours) as compared to an all-reuse scheme. The above comparison and performance analysis is done assuming a 3-sector network. This

Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks 121

Fig. 7. Performance of the proposed algorithm vs total rate requirement per sector compared

assumption is valid provided that the intercell interference in one sector is mainly due to only the two nearest base stations. If this assumption is not valid (as in the 21-sector network of Figure 8), the performance of the proposed scheme will of course deteriorates as can be seen in Figure 9. The same figure shows that the proposed scheme still performs better than an

Recall from Section 2 that the relevant performance metric in the case of slow-fading channels is the outage probability *PO*,*k* given by (3) (in the case of Gaussian codebooks and

log

Where *Rk* is the rate (in nats/s/Hz) at which data is transmitted to user *k*. Unfortunately, no closed-form expression exists for *PO*,*k*(*Rk*). The few works on outage-based resource

For example, consider the problem of maximizing the sum of users' data rates *Rk* under a total power constraint *P*max such that the outage probability of each user *k* does not exceed a

1 + *Pk*,*n*

> *σ*2 *k*

≤ *Rk* .

to the all-reuse scheme of Thanabalasingham et al. (2006)

all-reuse scheme, especially at high data rate requirements.

Gaussian-distributed noise-plus-interference process) as

= Pr 1 *N* ∑ *n*∈N*k*

*PO*,*k*(*Rk*)

certain threshold *�k*:

**4.3 Outage-based resource allocation (statistical-CSI slow-fading channels)**

allocation for OFDMA resorted to **approximations** of the probability *PO*,*k*(*Rk*).

**optimal** in the sense that follows. Denote by *Q*(*K*) subop the total power spent by the three base stations if this algorithm is applied. Also define *Q*(*K*) *T* as the total transmit power of an optimal solution to the original joint resource allocation problem. The suboptimality of the proposed resource allocation scheme trivially implies

$$\mathcal{Q}\_{\text{subop}}^{(K)} \ge \mathcal{Q}\_T^{(K)}$$

The asymptotic behaviour of both *Q*(*K*) subop and *Q*(*K*) *T* as *K* → ∞ has been studied7 in N. Ksairi & Ciblat (2011). In the asymptotic regime, it can be shown that the configuration of the network, as far as resource allocation is concerned, is completely determined by i) the **average** (as opposed to **individual**) data rate requirement *r*¯ and ii) a function *λ*(*x*, *y*) that characterizes the asymptotic "density" of users' geographical positions in the coordination system (*x*, *y*) of their respective sectors. To better understand the physical meaning of the density function *λ*(*x*, *y*), note that it is a constant function in the case of uniform distribution of users in the cell area..

Interestingly, one can find values for parameters *θA*, *θB* and *θC* (characterizing the separatin curves *dθ A* , *dθB* , and *dθC* respectively) that i) depend only on the average rate requirement *r*¯ and on the asymptotic geographical density of users and ii) which satisfy

$$\lim\_{K \to \infty} Q\_{\text{subopt}}^{(K)} = \lim\_{K \to \infty} Q\_T^{(K)} \stackrel{\text{(def)}}{=} Q\_T \dots$$

In other words, one can find separating curves *dθ A* , *dθB* , and *dθC* such that the proposed suboptimal allocation algorithm is **asymptotically optimal** in the limit of large numbers of users. We plot in Figure 6 these asymptotically optimal separating curves for several values of the average data rate requirement 8. The performance of the proposed algorithm *i.e.,* its total

Fig. 6. Asymptotically optimal separating curves

7 In this asymptotic analysis, a technical detail requires that we also let the total bandwidth *B* (Hz) occupied by the system tend to infinity in order to satisfy the sum of users' rate requirements ∑*K k*=1 *rk* which grows to infinity as *K* → ∞. Moreover, in order to obtain relevant results, we assume that as *K*, *B* tends to infinity, their ratio *B*/*K* remains constant

8 In all the given numerical and graphical results, it has been assumed that the radius of the cells is equal to *D* = 500m. The path loss model follows a Free Space Loss model (FSL) characterized by a path loss exponent *s* = 2. The carrier frequency is *f*0 = 2.4*GHz*. At this frequency, path loss in dB is given by *ρdB*(*x*) = 20 log10(*x*) + 100.04, where *x* is the distance in kilometers between the BS and the user. The signal bandwidth *B* is equal to 5 MHz and the thermal noise power spectral density is equal to *N*0 = −170 dBm/Hz.

16 Will-be-set-by-IN-TECH

solution to the original joint resource allocation problem. The suboptimality of the proposed

subop ≥ *Q*(*K*) *T*

Ciblat (2011). In the asymptotic regime, it can be shown that the configuration of the network, as far as resource allocation is concerned, is completely determined by i) the **average** (as opposed to **individual**) data rate requirement *r*¯ and ii) a function *λ*(*x*, *y*) that characterizes the asymptotic "density" of users' geographical positions in the coordination system (*x*, *y*) of their respective sectors. To better understand the physical meaning of the density function *λ*(*x*, *y*), note that it is a constant function in the case of uniform distribution of users in the cell area.. Interestingly, one can find values for parameters *θA*, *θB* and *θC* (characterizing the separatin curves *dθ A* , *dθB* , and *dθC* respectively) that i) depend only on the average rate requirement *r*¯

*Q*(*K*)

and on the asymptotic geographical density of users and ii) which satisfy

subopt = lim

*K*→∞ *Q*(*K*) *T*

In other words, one can find separating curves *dθ A* , *dθB* , and *dθC* such that the proposed suboptimal allocation algorithm is **asymptotically optimal** in the limit of large numbers of users. We plot in Figure 6 these asymptotically optimal separating curves for several values of the average data rate requirement 8. The performance of the proposed algorithm *i.e.,* its total

7 In this asymptotic analysis, a technical detail requires that we also let the total bandwidth *B* (Hz) occupied by the system tend to infinity in order to satisfy the sum of users' rate requirements ∑*K*

which grows to infinity as *K* → ∞. Moreover, in order to obtain relevant results, we assume that as *K*, *B*

8 In all the given numerical and graphical results, it has been assumed that the radius of the cells is equal to *D* = 500m. The path loss model follows a Free Space Loss model (FSL) characterized by a path loss exponent *s* = 2. The carrier frequency is *f*0 = 2.4*GHz*. At this frequency, path loss in dB is given by *ρdB*(*x*) = 20 log10(*x*) + 100.04, where *x* is the distance in kilometers between the BS and the user. The signal bandwidth *B* is equal to 5 MHz and the thermal noise power spectral density is equal to

(def) = *QT* .

lim *K*→∞ *Q*(*K*)

Fig. 6. Asymptotically optimal separating curves

tends to infinity, their ratio *B*/*K* remains constant

*N*0 = −170 dBm/Hz.

subop and *Q*(*K*)

subop the total power spent by the three base

*T* as the total transmit power of an optimal

*T* as *K* → ∞ has been studied7 in N. Ksairi &

*k*=1 *rk*

**optimal** in the sense that follows. Denote by *Q*(*K*)

stations if this algorithm is applied. Also define *Q*(*K*)

resource allocation scheme trivially implies

The asymptotic behaviour of both *Q*(*K*)

transmit power when the asymptotically optimal separating curves are used, is compared in Figure 7 to the performance of an all-reuse scheme (*α* = 1) that has been proposed in Thanabalasingham et al. (2006). It is worth mentioning that the reuse factor *α* assumed for our algorithm in Figure 7 has been obtained using the procedure described in Section 5. It is clear from the figure that a significant gain in performance can be obtained from applying a carefully designed FFR allocation algorithm (such as ours) as compared to an all-reuse scheme. The above comparison and performance analysis is done assuming a 3-sector network. This

Fig. 7. Performance of the proposed algorithm vs total rate requirement per sector compared to the all-reuse scheme of Thanabalasingham et al. (2006)

assumption is valid provided that the intercell interference in one sector is mainly due to only the two nearest base stations. If this assumption is not valid (as in the 21-sector network of Figure 8), the performance of the proposed scheme will of course deteriorates as can be seen in Figure 9. The same figure shows that the proposed scheme still performs better than an all-reuse scheme, especially at high data rate requirements.

#### **4.3 Outage-based resource allocation (statistical-CSI slow-fading channels)**

Recall from Section 2 that the relevant performance metric in the case of slow-fading channels is the outage probability *PO*,*k* given by (3) (in the case of Gaussian codebooks and Gaussian-distributed noise-plus-interference process) as

$$P\_{O,k}(\mathcal{R}\_k) \stackrel{\triangle}{=} \Pr\left[\frac{1}{N} \sum\_{n \in \mathcal{N}\_k} \log\left(1 + P\_{k,n} \frac{|H\_k^c(n)|^2}{\sigma\_k^2}\right) \le \mathcal{R}\_k\right].\ldots$$

Where *Rk* is the rate (in nats/s/Hz) at which data is transmitted to user *k*. Unfortunately, no closed-form expression exists for *PO*,*k*(*Rk*). The few works on outage-based resource allocation for OFDMA resorted to **approximations** of the probability *PO*,*k*(*Rk*).

For example, consider the problem of maximizing the sum of users' data rates *Rk* under a total power constraint *P*max such that the outage probability of each user *k* does not exceed a certain threshold *�k*:

In M. Pischella & J.-C. Belfiore (2009), the problem is tackled in the context of MIMO-OFDMA systems where both the base stations and the users' terminals have multiple antennas. In the approach proposed by the authors to solve this problem, **the outage probability is replaced with an approximating function**. Moreover, subcarrier assignment is performed **independently** (and thus suboptimally) in each cell assuming equal power allocation and equal interference level on all subcarriers. Once the subcarrier assignment is determined, multicell power allocation *i.e.,* the determination of *Pk*,*n* for each user *k* is done thanks to an iterative allocation algorithm. Each iteration of this algorithm consists in solving the power allocation problem separately in each cell based on the current level of multicell interference. The result of each iteration is then used to update the value of multicell interference for the next iteration of the algorithm. The convergence of this iterative algorithm is also studied by the authors. A solution to Problem (21) which performs **joint** optimization of subcarrier

Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks 123

In S. V. Hanly et al. (2009), a min-max outage-based multicell resource allocation problem is solved assuming that there exists a genie who can instantly return the outage probability of any user as a function of the power levels and subcarrier allocations in the network. When this restricting assumption is lifted, only a suboptimal solution is provided by the authors.

• All the resource allocation schemes presented in this chapter assume that the transmit symbols are from Gaussian codebooks. This assumption is widely made in the literature, mainly for tractability reasons. In real-world WiMAX systems, Gaussian codebooks are not practical. Instead, discrete modulation (*e.g.* QPSK,16-QAM,64-QAM) is used. The adaptation of the presented resource allocation schemes to the case of dynamic Modulation and Coding Schemes (MCS) supported by WiMAX is still an open area of research that has been addressed, for example, in D. Hui & V. Lau (2009); G. Song & Y. Li (2005); J. Huany

• The WiMAX standard provides the necessary signalling channels (such as the CSI feedback messages (CQICH, REP-REQ and REP-RSP) and the control messages DL-MAP and DCD) that can be used for resource allocation, as explained in Byeong Gi Lee & Sunghyun Choi

• The smallest unity of band allocation in WiMAX is **subchannels** (A subchannel is a group of subcarriers) **not** subcarriers. Moreover, WiMAX supports transmitting with different powers and different rates (MCS schemes) on different subchannels as explained in Byeong Gi Lee & Sunghyun Choi (2008). This implies that the per-subcarrier full-CSI schemes presented in Subsection 4.1 are not well adapted for WiMAX systems. They should thus be first modified to per-subchannel schemes before use in real-world WiMAX networks. However, the average-rate statistical-CSI schemes of Subsection 4.2 are compatible with

The selection of the frequency reuse scheme is of crucial importance as far as cellular network design is concerned. Among the schemes mentioned in Section 3, fractional frequency reuse (FFR) has gained considerable interest in the literature and has been explicitly recommended

(2008), but does not oblige the use of any specific resource allocation scheme.

the subchannel-based assignment capabilities of WiMAX.

**5. Optimization of the reuse factor for WiMAX networks**

**4.4 Resource allocation for real-world WiMAX networks: Practical considerations**

assignment and power allocation is yet to be provided.

et al. (2005); R. Aggarwal et al. (2011).

Fig. 8. 21-sector system model and the frequency reuse scheme

Fig. 9. Comparison between the proposed allocation algorithm and the all-reuse scheme of Thanabalasingham et al. (2006) in the case of 21 sectors (25 users per sector) vs the total rate requirement per sector

max{N*k*,*Pk*,*n*}1≤*k*≤*K*,*n*∈N*k* ∑*c* ∑*k*∈*c Rk*

subject to the OFDMA orthogonality constraint and to (8) and *PO*,*k*(*Rk*) ≤ *k* . (21)

18 Will-be-set-by-IN-TECH

4 5 6 7 8 9 10 11 12 13 101

Proposed algorithm

∑*c* ∑*k*∈*c Rk*

subject to the OFDMA orthogonality constraint and to (8) and *PO*,*k*(*Rk*) ≤ *k* . (21)

Algorithm of [Thanaalasingham et. al]

D=500 m, B=5 MHz

r T (Mbps)

Fig. 9. Comparison between the proposed allocation algorithm and the all-reuse scheme of Thanabalasingham et al. (2006) in the case of 21 sectors (25 users per sector) vs the total

max{N*k*,*Pk*,*n*}1≤*k*≤*K*,*n*∈N*k*

Fig. 8. 21-sector system model and the frequency reuse scheme

102

rate requirement per sector

Total transmit power (mW)

103

104

In M. Pischella & J.-C. Belfiore (2009), the problem is tackled in the context of MIMO-OFDMA systems where both the base stations and the users' terminals have multiple antennas. In the approach proposed by the authors to solve this problem, **the outage probability is replaced with an approximating function**. Moreover, subcarrier assignment is performed **independently** (and thus suboptimally) in each cell assuming equal power allocation and equal interference level on all subcarriers. Once the subcarrier assignment is determined, multicell power allocation *i.e.,* the determination of *Pk*,*n* for each user *k* is done thanks to an iterative allocation algorithm. Each iteration of this algorithm consists in solving the power allocation problem separately in each cell based on the current level of multicell interference. The result of each iteration is then used to update the value of multicell interference for the next iteration of the algorithm. The convergence of this iterative algorithm is also studied by the authors. A solution to Problem (21) which performs **joint** optimization of subcarrier assignment and power allocation is yet to be provided.

In S. V. Hanly et al. (2009), a min-max outage-based multicell resource allocation problem is solved assuming that there exists a genie who can instantly return the outage probability of any user as a function of the power levels and subcarrier allocations in the network. When this restricting assumption is lifted, only a suboptimal solution is provided by the authors.

### **4.4 Resource allocation for real-world WiMAX networks: Practical considerations**

#### **5. Optimization of the reuse factor for WiMAX networks**

The selection of the frequency reuse scheme is of crucial importance as far as cellular network design is concerned. Among the schemes mentioned in Section 3, fractional frequency reuse (FFR) has gained considerable interest in the literature and has been explicitly recommended

Fig. 10. 3-sectors system model

Ciblat (2011)

It is worth noting that the limit value *QT* **only** depends on i) the above-mentioned asymptotic state of the network *i.e.,* on the average rate *r*¯ and on the asymptotic

Downlink Resource Allocation and Frequency Reuse Schemes for WiMAX Networks 125

*K*→∞ *Q*(*K*)

*T* (*α*) .

geographical density *λ* and ii) on the value of the reuse factor *α*.

*α*opt = arg min*α* lim

In practice, we propose to compute the value of *QT* = *QT*(*α*) for several values of *α* on a grid in the interval [0, 1]. In Figure 11, *α*opt is plotted as function of the average data rate requirement *r*¯ for the case of a network composed of cells with radius *D* = 500m assuming uniformly distributed users' positions. Also note that complexity issues are of few importance, as

Fig. 11. Asymptotically optimal reuse factor vs average rate requirement. Source:N. Ksairi &

It is thus reasonable to select the value *α*opt of the reuse factor as

for WiMAX in WiMAX Forum (2006), mostly for its simplicity and for its promising gains. For these reasons, we give special focus in this chapter to this reuse scheme.