Multiobjective optimization of fractional frequency reuse for irregular OFDMA macrocellular deployments

Telecommunication Systems manuscript No. (will be inserted by the editor) Multiobjective Optimization of Fractional Frequency Reuse for Irregular OFDMA Macrocellular Deployments David González G ·Mario García-Lozano ·Silvia Ruiz ·María A. Lema · DongSeop Lee Received: date / Accepted: date Abstract Interference mitigation has been identified as a key challenge for emerging cellular technologies based on Orthogonal Frequency Division Multiple Access (OFDMA), such as LTE. In this context, static Intercell Interference Coordination including Fractional Frequency Reuse (FFR) have been adopted by mobile operators as a good alternative to improve the Quality of Service (QoS) at cell edges. Nevertheless, recent results made evident the need for additional research efforts as default FFR configurations only offer tradeoffs in which spectral efficiency is severely penalized. Moreover, the performance of such baseline designs has been showed to be poor in realistic cellular deployments featuring irregular cell patterns. This paper solves this problematic by introducing a novel multiobjective optimization framework based on evolutionary algorithms that jointly takes into account system capacity, cell edge performance, and energy consumption. With respect to important reference schemes, the proposed algorithm succeeds in finding FFR configurations achieving gains between 10% and 40% in terms of system capacity while simultaneously improving cell edge performance up to 70%. Keywords Fractional Frequency Reuse, FFR, Long Term Evolution, LTE, Multiobjective Optimization. 1 Introduction One of the most important technical challenges of emerging cellular systems, such as Long Term Evolution (LTE) and LTE-Advanced (LTE-A), is to guarantee uniform levels of Quality of Service (QoS) to their users [2]. Both LTE David González G. Department of Communications and Networking (COMNET), School of Electrical Engineering, Aalto University, Finland. E-mail: da[email protected] and LTE-A employ Orthogonal Frequency Division Multiple Access (OFDMA) as access technology for the downlink due to its flexibility for resource allocation [4], and because OFDMA provides intrinsic orthogonality to the users within the same cell, which translates into an almost null level of intracell interference. However, Intercell Interference (ICI) remains as an issue, and indeed, it is the main capacity-limiting factor in OFDMA-based cellular networks, especially when high frequency reuse (to achieve higher spectral efficiency) is intended. In order to deal with this problem, several approaches have been proposed along the last few years including Intercell Interference Coordination (ICIC). In addition, new and more sophisticated strategies for future 4G and 5G networks such as Coordinated Multipoint (CoMP) [21] and enhancedICIC (eICIC) [20] are being extensively studied. Nevertheless, given the fast pace at which LTE has been deployed and trialled [14], there is an increasing interest of mobile operators for feasible and effective schemes aiming at improving the QoS of users close to cell edges. Static ICIC including Fractional Frequency Reuse (FFR) has been highly valued by mobile operators because these schemes are easy to implement and there is no need for intercell signaling overhead. In particular, FFR is well-known for its ability to provide high levels of Signal to Interference plus Noise Ratio (SINR) to cell edge users due to the higher frequency reuse applied to them. However, the performance of FFR in realistic deployments featuring irregular cellular layouts is poor according to results reported in [15]. This issue has been also pointed out in [6], where the authors remarked the need for additional research efforts in this direction since no simple reuse pattern can be easily derived for such scenarios. Therefore, in order to make FFR really attractive to mobile operators, it is a design requirement not only mitigating Intercell Interference (ICI) at cell edges but 2 David González G et al. Fig. 1 Operational principle of fractional frequency reuse. also avoiding over-penalize the spectral efficiency. And lastly, but not less important, to improve the energy efficiency [8]. In order to deal with these conflicting criteria, this article introduces a novel multiobjective approach, based on the evolutionary approach, aiming at optimizing FFR to make it suitable for realistic deployments. The proposed scheme allows simultaneous optimization of several metrics: spectral efficiency and cell edge performance, while minimizing the power expenditure. Basically, the solution optimizes the operational parameters of FFR locally at each cell. The idea is to compensate the irregularities of realistic deployments by considering average propagation conditions of each cell and its impact on the neighbor ones. The results show that the proposed algorithm is effective, feasible, and it clearly outperforms baseline designs and previous proposals. The rest of the article is organized as follows: the next section establishes the context of this study with an overview of FFR and a description of the problem. Section 3 presents related literature and remarks how the proposal presented in this article advances the state of the art. The system model and proposed framework, including an introduction to multiobjective and evolutionary optimization, are described in Sections 4 and 5, respectively. The numerical results and evaluation setting are presented in Section 6. Section 7 includes calibration, convergence and complexity aspects. Finally, conclusions and future work close the paper in Section 8. 2 Background and Motivation 2.1 Fractional frequency reuse The main target of FFR, as any other ICIC technique, is to improve the radio channel quality of cell edge users. To do this, FFR first classifies users according to their average radio channel quality (by means of a SINR threshold STH ) as inner ( I ) or cell edge ( E ) users, and next, it applies different frequency reuse factors and power levels to each group in order to homogenize the SINR. In this manner fairness among users is improved. It is worth mentioning that, according to [17] and [26], the choice of STH has a great impact on the performance of FFR. Figure 1 depicts the operational principle of FFR: applying higher frequency reuse factor to cell edge users. Note that, although this classification is usually regarded as a geographical distinction, in practice it is a Fig. 2 Regular frequency reuse patterns in cellular networks. radio condition given by SINR measurements based on pilot signals. The parameters β and α control the bandwidth and power allocated to each class of users, respectively. In preliminary evaluations of FFR [28] (using 3 rd Generation Partnership (3GPP) models, i.e., hexagonal layouts) only baseline designs were employed 1 . As it will be shown shortly, these approach is far from optimal in realistic deployments. 2.2 Performance on irregular layouts: an open issue In order to better understand the origin of the problem addressed herein, it is required to remark the role of frequency reuse on the capacity of cellular networks. To do this, an illustrative analysis is provided. Figure 2 shows the typical reuse pattern for different frequency reuse factors when a regular/hexagonal cellular layout is considered. By taking into account that, 1) channel gains are given exclusively by propagation losses (inversely proportional to the distance to the power of σ , the attenuation coefficient), 2) the effect of the background noise is negligible, and 3) ε is a very small number ( ε·R≈0 ); it is easy to show that the expressions corresponding to the SINR for a user xi ( i=1 for cell center and i=2 for cell edge) can be approximated to the following expressions: γr1 x1≈(ε)−σ 6·√3−σ;γr3 x1≈(ε)−σ 6·(3)−σ;γr7 x1≈(ε)−σ 6·√21−σ γr1 x2≈1 2+3·(2)−σ+2·1 2√28−σ+4·√7−σ γr3 x2≈1 (2)−σ+(4)−σ+2·1 2√28−σ+2·1 2√52−σ γr7 x2≈1 Dint,r7 Dint,r7≈(4)−σ+(5)−σ+1 2√52−σ +··· 1 Baseline designs refer to settings in which the operational parameters of FFR ( STH,α and β ) are uniformly applied to all cells of the network. Multiobjective Optimization of Fractional Frequency Reuse for Irregular OFDMA Macrocellular Deployments 3 (a) Cell center SINR (b) Cell center capacity (c) Cell edge SINR (d) Cell edge capacity Fig. 3 Average quality at cell edge/center for different frequency reuse factors. Thus, γrk xi is the SINR of user xi subject to frequency reuse factor k as a function of the propagation loss exponent σ . From Figures 3a and 3b, it can be seen that the improvement on the average quality experienced by central users due to higher frequency reuse factors (3 and 7) does not compensate the loss in terms of spectral efficiency. Hence, for central users, a frequency reuse factor 1 is the best choice. On the other hand, looking at Figures 3c and 3d, it is evident that frequency reuse factor 3 is the best choice for cell edge users as it maximizes capacity. Therefore, it can be concluded that for regular layouts, in particular for tri-sectorial deployments, a simple reuse pattern suffices to successfully tradeoff between spectral efficiency and cell edge performance, i.e., full reuse for central zones and reuse 3 for cell edges. The same reasoning can be applied to any other reuse pattern and network geometry. From a practical perspective, this result is due to the fact that in synthetic scenarios, sectors using the same subbands are geometrically aligned, thus minimizing ICI. Now, the attention is focused on realistic networks where cellular layouts are irregular. In such scenarios, propagation conditions vary significantly from cell to cell and the azimuths are not aligned. This results in very different amounts of ICI at different cells. As a consequence, cell edges are very dissimilar in terms of size and average SINR levels. Thus, it can be thought that applying simple and/or regular resource allocation patterns to realistic deployments leads to suboptimal performances as certain degree of local optimization (at cell level) is required to compensate the differences previously explained. In order to further support the previous reasoning, numerical results obtained from LTE system level simulations are provided. Figure 4 shows average figures corresponding to spectral efficiency and percentile 5 of users’ rate ( r ) for LTE trials conducted both in synthetic (Syn, perfectly hexagonal) and realistic (Rea1 and Rea2) deployments after applying FFR. The description of both simulation scenarios and the LTE setting can be found in [16]. Note that in these trials, common values for α , β , and STH are applied to all cells. Main system parameters include: –System bandwidth: 18 MHz, –Available power per cell: 43 dBm, Fig. 4 Performance of reference schemes in synthetic and realistic scenarios. –Users per cell: 45, –Scheduling policy: Proportional fair. These results basically show that while in synthetic cellular layouts, baseline designs can effectively tradeoff between spectral efficiency and cell edge performance with respect to reference schemes, such as full reuse and hard reuse 3; in case of cellular networks with irregular cell patterns, the performance of FFR is far from optimal, and indeed, it is strictly worse than full reuse both from efficiency and fairness point of view. Therefore, and according to the conclusions in [6], the need for optimization is established. In the next section, a survey of related literature is presented aiming at clarifying how the proposal presented herein advances the state of the art. 3 Related Work Up to now, a great interest have been placed on FFR, and consequently, several improvements has been proposed. Representative examples including [1,5,11,19,32,37] are basically focused on small networks featuring hexagonal geometry. These contributions propose different types of bandwidth and power re-allocations operating at a very short time scale under the assumption of full/perfect knowledge of users’ radio channels both in time and frequency, which is unfeasible in real systems. In addition, very often these dynamic schemes are coupled to specific/complex short term resource allocation policies to perform the final resource pairing to users. In practical systems, such as LTE, scheduling is vendor specific, and hence, it is desirable, as far as possible, to 4 David González G et al. keep ICIC decoupled to other Radio Resource Management (RRM) functionalities. Therefore, in order to design feasible ICIC solutions, proposed strategies should be 1) decoupled from other network entities, and 2) focused on minimizing average interference levels [35]. In real systems, small scale (short term) fading effects [27] are managed by other functionalities, such as instantaneous power control, adaptive channel state feedback mechanisms, adaptive modulation and coding, and frequency selective scheduling. To accomplish the previous target, FFR should be mainly focused on the network-specific geometry and average ICI conditions. Moreover, performance must be analyzed from as many perspectives as possible, i.e., taking into account several performance metrics to conveniently assess existing tradeoffs. To best of authors’ knowledge, one of the few works fulfilling most of the previous design guidelines is the excellent contribution done by Chen and Yuan in [6]. The approach followed in [6] is generic enough in the sense that it 1) considers realistic networks with irregular cell patterns, and 2) allows a long term (average) characterization of the SINR based on large scale fading effects. In [6], the performance metric is defined as the sum of the contributions of every single area element, and hence, the method does not rely on other specific assumptions, such as a certain scheduling policy. However, there are some aspects in [6] that can be improved. 1. The performance assessment is only based on one single performance metric: the cell edge throughput. Although, at a glance this metric could result adequate, in the particular context of FFR it has some drawbacks. First, the definition provided by Chen and Yuan for this metric only takes into account the pixels labeled as cell edge, i.e., the ones in which the pilot (wideband) SINR is smaller than STH . A better approach for realistic networks is to consider the whole network coverage area once FFR is applied and then focus on the resulting achievable data rate at pixel level, because, due to the change in the frequency reuse factor and bandwidth for each zone, the final distribution of achievable data rates at pixel level does not necessarily match the corresponding SINR distribution [17]. Second, it is well-known the fact that cell edge performance and overall spectral efficiency are conflicting objectives [25,26], and hence, in order to provide a better overview of this tradeoff, both performance metrics must be jointly considered. 2. The algorithm proposed in [6] produces one single bandwidth allocation subject to fixed network-wide values for STH , β , and the number of subbands available for cell edges K . However, mobile operators are more interested in a set of FFR configurations rather than one single network setting so that they can react effectively to network dynamics, such as (repetitive) load variations. In addition, it is also clear that defining common (global) parameters clearly leads to suboptimal performances since in realistic deployments cells are quite different in terms of ICI and coverage; in fact, the algorithm proposed in [6] does not give any clue about how to select such operational parameters, and therefore, a large number of trials (to account for different values of β and STH ) needs to be done in order to find useful FFR configurations. Thus, in the light of these observations, this paper proposes a novel FFR optimization framework for realistic networks featuring irregular cell layouts. In order to address the previous aspects and effectively deal with the nature of the problem under consideration, the proposed algorithm is multiobjective and it is based on the evolutionary approach [7]. In Section 5, the rationale of this choice is provided. In this manner, FFR design has been successfully addressed by means of a novel framework which is unique in the sense that it: – formulates the problem considering not only global network wide design variables but also local ones in order to take advantage of cell’s local features, and hence, achieve better adaptability. – generates, due to its multiobjective nature, a wide range of FFR configurations providing more flexibility to operators to adapt their networks (without any computational cost nor excessive intercell signaling) to time varying conditions. These solutions represent FFR settings that simultaneously optimize spectral efficiency and cell edge performance, while reducing transmission power over the air interface. – introduces a compact mathematical formulation that can be used to efficiently evaluate different configurations in terms of any arbitrary set of performance metrics that can also be defined by the mobile operator. 4 System Model In this work, the downlink of an OFDMA based cellular system composed of L cells is considered. The system bandwidth, BSYS , is available at each cell and it is divided in NSC allocable subcarriers spaced 15 kHz. The total available power per cell is PCell max . The coverage zone is composed of A small area elements within which, the average received power and SINR, are constant. The average received power in each pixel (from each cell), the matrix RP∈RA×L , is computed according to: RP=G·diag(pPS),(1) where G∈RA×L corresponds to the Long Term Channel Gain (LTCG) matrix containing large scale fading effects. The vector pPS ∈RL is the average pilot transmit power at each cell. In practice, the matrix G is usually available from Multiobjective Optimization of Fractional Frequency Reuse for Irregular OFDMA Macrocellular Deployments 5 propagation studies required during the planning stage of the network. A pixel a(ath row in RP) is served by cell l?, if: l?=argmax l RP(a,l).(2) Based on Equations 1 and 2, the binary coverage matrices S and Sc∈RA×L can be obtained. Thus, if a pixel a is served by cell l? , then S(a,l?) = 1 . Sc is the binary complement of S . The set of cells is divided in three subsets based on their antenna azimuth ϕ . Therefore, a cell belongs to subset Cj (j∈J={0,1,2}) according to the following rule: j=   0,for 0◦≤ϕ<120◦, 1,for 120◦≤ϕ<240◦, 2,for 240◦≤ϕ<360◦. (3) In the same manner, pixels are divided in three subsets Aj such that, a pixel is element of Aj , if is served by a cell of type j∈J . Note that ∑∀j∈J|Aj|=A and ∑∀j∈J|Cj|=L . 5 Proposed Multiobjective Framework From an operator’s perspective, FFR design and optimization is a problem in which the interest is placed not only in guaranteeing certain levels of QoS to users but also in maximizing spectral efficiency and, if possible, do it at the lowest cost. Thus, designing a flexible scheme able to tradeoff among these conflicting criteria is an important design target [15]. For this reason, the performance assessment is based on the following criteria that need to be simultaneously satisfied: 1. Maximization of the average cell capacity: f1[Mbps]. 2. Maximization of the capacity of the worst percentile 5 of the network coverage area (typically users at cell edge): f2 [Mbps]. Note that the area corresponding to this percentile can be geographically distributed among the coverage of different cells. 3. Minimization of the transmission power: f3 . By considering this metric, the proposed algorithm not only reduces Operation Expenditures (OPEX) directly but also maximizes network energy efficiency [8]. 5.1 Multiobjective optimization: a bird’s eye view The task of joint optimization of the previous performance indicators ( f1 , f2 , and f3 ) can be successfully addressed by means of multiobjective techniques. Multiobjective Optimization (MO) is the discipline focused on the resolution of problems in which desirable solutions involve simultaneous optimization of conflicting criteria or objectives [29]. The target of MO is to find a subset of good solutions X? from a set X , according to a set of criteria, F ( |F|= m≥2 ), typically expressed as mathematical functions, the so-called objective functions. Thus, F={fi:Rn→R,i= 1,...,m} , where fi represents the ith objective function. In general, an optimal solution could imply the minimization of one function fi∈F and the maximization of another one fj∈F,(i6=j) . Thus, the notion of optimality acquires especial relevance in this context. An optimal solution is a vector x? which optimizes each objective function f∈F , i.e., f(x?) = [ f? 1f? 2··· f? m]. Nevertheless, this situation rarely happens in practice due to the conflicting nature of different criteria, and so, additional elements need to be introduced. A central concept of the theory of MO is the Pareto dominance [34]. A solution x1 is preferred to (dominates in the Pareto sense) another solution x2 , ( x1x2 ), if x1 is better than x2 in at least one criterion and no worse with respect to the remaining ones. x1x2⇔fi(x1)≤fi(x2),∀i∈{1,2,...,m} ∧ ∃j∈{1,2,...,m} | fj(x1)<fj(x2). Bearing in mind this important concept, it is possible to formalize a definition of optimality. A solution x? is Pareto optimal (and hence, element of X? ), if and only if, there does not exists a solution x∈X , such that x dominates x? . The set X?is called Pareto Front (PF). x?∈X?⇔6∃ x∈X|x?≺x. 5.2 Multiobjective problem formulation In the context of the optimization framework presented in this study, several network configurations featuring Pareto efficiency with respect to f1 , f2 , and f3 are required to be found. The optimization is performed by fine tuning the operational parameters of FFR locally at each cell. To be more precise, the main idea is defining cell edges independently at each cell by means of cell local thresholds, i.e., Sl TH,l=1,2,···,L , subject to an additional network-wide design variable ( β , see Figure 1) that is applied uniformly to all cells. The parameter β must be the same in each cell in order to guarantee full reuse for central pixels and reuse 3 for cell edge zones. The parameter α , is kept fixed as an input parameter applied to the whole network. The reason is twofold. On the one hand, the performance of FFR is basically independent of this figure as long as 1) it is applied globally in the network, and 2) average ICI levels are significantly higher than the noise power, i.e., interference-limited systems [17], the case of study herein. On the other hand, defining α as cell local design variable would duplicate the complexity of the problem with marginal gains from the cell edge performance point of view as this parameter only affects inner ( I ) pixels. The genotype (structure) of the solutions is shown in Figure 5. Thus, the MO problem can be written as follows: minimize f(x) = [ −f1(x)−f2(x)f3(x) ]T,(4) subject to: Sl TH =x(l)∈[Slow,Sup]∀l∈{1,2,...,L}, β=x(L+1)∈[βlow,βup ],Slow <Sup,βlow <βup , 6 David González G et al. Traditional approach Proposed framework Static ICIC Detailed RRM functionalities modelling: CSI, HARQ, Scheduling, Power control, Call admision, etc. Statistical model: Average values oriented assumptions Simple numerical analysis Static ICIC Global performance metrics Static ICIC Evaluation Ranking SelectionReproduction Initial Population Compute objective functions of individuals Use objective values and additional metrics to establish a total order among individuals. Apply selection criteria. Create new individuals from the mating pool. Randomly generated individuals. Fig. 5 Genothype of individuals (FFR settings) used in this study. where the constants: Slow,Sup,βlow, and βup are used to define the bounds of the design variables. f1 , f2 , and f3 correspond to the objective functions (performance metrics) representing average cell capacity, cell edge performance, and normalized energy consumption, respectively. The parameter α was selected considering a minimum received power of −110dBm at each pixel. 5.3 Metaheuristics and evolutionary optimization In FFR optimization, there are two aspects that must be taken into account: 1) the nature of the problem, and 2) the mathematical structure of the objectives functions previously mentioned 2 . To be precise, the domain (search space) created by the design variables is a n -dimensional space where n is proportional to the number of cells, and whose objective space (or image defined by the objective functions) is not only highly non-linear, non-convex, but also full of discontinuities and local optima [36]. In FFR optimization, discontinuities in f1 and f2 occur, for instance, due to variations of STH , when a pixel changes its classification from I to E , and vice versa. Certain algorithms, such as Simplex [12], are susceptible to be trapped in local optima, while other optimizations techniques, such as Sequential Quadratic Programming based methods [13], require convexity (a very strong assumption for this problem) to guarantee convergence. Moreover, traditional constrained optimization, in which only one objective function is optimized subject to a set of constraints on the remaining ones, limits the visibility of the whole objective space, and hence, the tradeoff between performance criteria can not be analyzed completely as significant parts of the whole Pareto Front are lost. Summarizing, the problem of interest requires of an optimization tool fulfilling the following set of features: – It must be able to find good solutions by efficiently exploring the search space. – It should be able to operate/handle efficiently multiple criteria with a large number of design variables. – Do not have strong requirements on objectives functions such as linearity, convexity, or differentiability. Multiobjective evolutionary algorithms (MOEAs) [7] fulfill the previous requirements, and hence, its usage in FFR optimization for large and irregular networks has been studied. 2 The definition and evaluation of the objective functions f1 , f2 , and f3is presented in Subsection 5.4. Traditional approach Proposed framework Static ICIC Detailed RRM functionalities modelling: CSI, HARQ, Scheduling, Power control, Call admision, etc. Statistical model: Average values oriented assumptions Simple numerical analysis Static ICIC Global performance metrics Static ICIC Fig. 6 Operational cycle of evolutionary algorithms. MOEAs are a class of nature-inspired metaheuristics 3 that simulate the process of natural evolution, as it is illustrated in Figure 6. In MOEAs, a population of individuals (candidate solutions) is iteratively modified by means of two basic principles: selection and variation. While selection tries to imitate the battle for reproduction among living beings, variation mimics their inherent ability of creating new (better adapted) individuals through recombination and mutation. In this study, a well-known MOEA has been employed: The Non-dominated Sorting Genetic Algorithm II ( NSGA-II ) [9]. This algorithm provides means to accomplish desired features in the context of evolutionary optimization, such as elitism, fast convergence, and good distribution. An in-depth treatment of the matter can be found in [29] and [3]. 5.4 Proposed algorithm The proposed methodology is presented in Algorithm 1. Intermediate steps are explained along the following points. 5.4.1 Average SINR evaluation (AvgSINR()) This function computes the average SINR matrix Ψ0∈RA×L as follows: Ψ0= [(SG)·pPS ][[(ScG)·pPS]⊕η],(5) where  ,  , and ⊕ indicate Hadamard (pointwise) operations and ηis the noise power. 5.4.2 Type of server classification (TypeOfServer()) This function computes a vector t∈NA where each element (representing one pixel) indicates the type of the serving transmitter according to Equation 3. 5.4.3 Segmentation (Segmentation()) This procedure pulls out from G,S,Sc , and Ψ0 the rows whose corresponding value in t is equal to j,∀j∈J . In other words, once instructions 3-5 in Algorithm 1 are executed, each one of these matrices is segmented in |J| submatrices 3 Metaheuristics are high level (generic) procedures that can be applied to solve a wide range of optimizations problems [18,22,24]. Multiobjective Optimization of Fractional Frequency Reuse for Irregular OFDMA Macrocellular Deployments 7 Algorithm 1: FFR Optimization. input : L,pPS,α,G,S,Sc,Slow,Sup,βlow,βup,η vϕ∈RL: Azimuth vector ONSGA-II: Set of calibration parameters. output : X?: Pareto Front (nondominated solution); // Step 1: Average SINR evaluation; 1Ψ0←AvgSINR(η,pPS,G,S,Sc); // Step 2: Type of server classification; 2t←TypeOfServer(vϕ,S); // Step 3: Segmentation; 3for each j∈Jdo 4{Gj,Sj,Sc j,Ψ0 j}←Segmentation(t,j,G,S,Sc,Ψ0); 5end // Step 4: Pareto front estimation; 6X?←NSGA(ONSGA-II); ( Sj , Sc j , Gj , and Ψ0 j ), each of them having L columns but a different number of rows, and so: Sj,Sc j,Gj,Ψ0 j∈R|Aj|×L,∀j∈J.(6) Function CharacPowFFR(·) input :L,pSC max,α output :Pser,Pint 1pE←pSC max,pI←α·pSC max; 2Pser ←"pEpE··· pE pIpI··· pI#T 3Pbase int ←   pEpI0pI0pI 0pIpEpI0pI 0pI0pIpEpI    4Pint ←h(Pbase int )T 1(Pbase int )T 2··· (Pbase int )T L/3iT 5.4.4 Pareto Front estimation The estimation of the Pareto Front is done by means of the algorithm NSGA-II (the function NSGA() in the pseudo-code of Algorithm 1). In order to do that, NSGA() requires the execution of two functions that are implicitly called when objective function values are calculated: CharacPowFFR() and ObjFunc() . The Function CharacPowFFR() generates the matrices ( Pint ∈RL×6and Pser ∈RL×2 ) used to compute SINR values associated to data channels. It’s definition can be read in the corresponding pseudo-code. In addition, the Function ObjFunc() computes the vector f containing the objective function values by means of matrix operations as shown in the corresponding pseudo-code. In line 4 of ObjFunc() , the Function Class() computes the binary classification matrices Cj∈R|Aj|×2,∀j∈J which indicate the class (either I : for S≥STH , or E : for S<STH ) to which each pixel belongs to. The Function RelCov() , in line 6, computes the Function ObjFunc(·) input :B,G,S,Sc,Ψ0,Pser,Pint,β,α output :f 1sTH ←x(0 : L−1); 2B←[ ((1−β)/3)·BSYS β·BSYS ]; 3for each j∈Jdo 4Cj←Class(Sj,sTH,Ψ0 j); 5end 6Φ←RelCov(S1,...,S|J|,C1,...,C|J|); 7f1←0,f2←0,ˆ r←[ ]; 8for each j∈Jdo 9˜ Pint ←Pint(:,2j: 2j+1); 10 Ψj←h[(SjGj)·Pser ]hh(Sc jGj)·˜ Pinti⊕ηiiCj; 11 Λj←LinkPer(Ψj); 12 f1←f1+B·(ΛT j·Sj)Φ·1; 13 r←Sj·(ΦT·diag(B))Λj·1; 14 ˆ r←[ˆ r rT]; 15 end 16 f2←Percentile(ˆ r); 17 f3←((1−β)/3)+(α·β); 18 f←[−f1/L−f2f3]T; matrix Φ∈R2×L containing the number of pixels classified as E and I at each cell. In line 9, ˜ Pint is created by selecting two columns of Pint depending on the value of j , and therefore, SINR values are computed in line 10. In line 11, the Function LinkPer() computes, for each element of Φ , a nondecreasing function of the SINR (the link performance model). Shannon bound has been used: Γ(S) = Log2(1+S) [bps/Hz].(7) The expression B·h(ΛT j·Sj)Φi∈RL in line 12 corresponds to a vector indicating the capacity in bps associated to each cell of type j∈J , and hence, the scalar f1 accumulates the network capacity once the loop is completed. In the same manner, the instructions in lines 13 and 14 subsequently create a vector of A elements representing the capacity of every single pixel in bps such that the Function Percentile() , in line 16, gets the sum of the worst 5% of the elements in ˆ r . Therefore, the capacity corresponding to the worst percentile 5 of the network coverage ( f2 ) is obtained. The normalized energy consumption f3 is computed as a function of βand αas indicated in line 17. 6 Performance Assessment 6.1 Evaluation setting and benchmarks A cellular network with system bandwidth BSYS =5.4MHz has been considered. The total available power per cell PCell max is equal to 43 dBm. The simulation scenario is a realistic deployment covering the city of Vienna and its surroundings. The digital elevation model and cell parameters have been obtained from the MORANS initiative [33]. The cellular layout is composed of L= 60 tri-sectorial cells and the evaluation area corresponds to a urban subarea of 2.75 × 2.625 km 2 8 David González G et al. Fig. 7 Realistic urban scenario employed as test case. Table 1 Evaluation setting Parameter Value Population size 200 Max number of generations 2000 Crossover probability 1.0 Mutation probability 1/(L+1) Design variables type Real variables Slow/Sup [-4.0 3.0] βlow/βup [dB] [0.3 0.5] α/η/A0.40 / -125 dBm / 288750 pPS 18.4 dBm Fig. 8 SINR characterization of the simulation scenario. with a pixel resolution of 5 × 5 m 2 . The propagation model is the COST 231-Walfish-Ikegami, which is a fast empirical prediction model for urban scenarios allowing an accurate radio characterization of this type of environments. Figure 7 shows the cellular layout and the resulting propagation pattern, for one site as reference. The list of calibration parameters (for NSGA-II) together with the simulation setting are shown in Table 1. Recall that calibration and simulation parameters depend, in general, on mobile operators’ preferences. Additional aspects about calibration and convergence of NSGA-II for this particular problem are provided in Section 7. Benchmarks can be classified in three groups: 1. Reference schemes : To put the results in perspective, two generic (but highly important) reference schemes are considered: Full Frequency Reuse and Hard Reuse 3, xFR and xHR3, respectively. (a) 3D view (b) 2D view ( f1vs f2) (c) 2D view ( f1vs f3) (d) 2D view ( f2vs f3) Fig. 9 Representations of the Pareto front X?and reference schemes. 2. Bandwidth proportionality : The schemes xi SA correspond to this approach. A common SINR threshold STH guarantees that the number of users of each class ( E and I ) is proportional on average to its allocated bandwidth. Figure 8 shows the required classification threshold for different values of β . Implementation was done according to the guidelines originally suggested in [15], but considering the cellular deployment (test case) used herein. 3. Subband Allocation : The schemes xi SA correspond to the best configurations found by means of the subband allocation (local search) algorithm proposed in [6]. Note that since this algorithm requires as input the number of subbands for cell edges ( K ), β , and STH , a total number of 160 trials 4 were performed in order to find the FFR configurations achieving best results with respect to each performance metric. The configuration and performance of the benchmarks are shown in Table 2. 6.2 Numerical results Figure 9 shows some representations of the resulting Pareto front X? (nondominated solutions) obtained through Algo4 The search space was obtained after an initial trial and error procedure required to localize the region of interest, i.e., K×β× STHdB ={3,4}×{0.300,0.325,0.350,···,0.500}×{−4,−3,···,5}. Multiobjective Optimization of Fractional Frequency Reuse for Irregular OFDMA Macrocellular Deployments 9 Table 2 Reference schemes: configuration and performance. xFR xHR3 x1 BD x2 BD x3 BD x4 BD x1 SA x2 SA x3 SA β0.50 0.40 0.33 0.25 0.35 0.35 0.40 STH [dB] -0.92 -0.08 0.69 1.92 2.00 1.00 0.00 K344 f19.31 7.87 7.70 7.60 7.51 7.64 9.85 8.94 8.03 f28.38 5.38 8.16 7.84 7.65 7.26 5.5 7.03 8.35 f31.00 0.333 0.367 0.360 0.355 0.350 0.425 0.369 0.471 Fig. 10 Achievable gains. rithm 1. Figure 9a corresponds to a 3D visualization of X?. However, in order to have an initial qualitative perspective, 2D profiles 5 are shown in Figures 9b, 9c, and 9d. In these profiles, the performance achieved by each benchmark is indicated with red lines (see Table 2). Clearly, the proposed algorithm always succeeds in finding FFR configurations outperforming each benchmark (plotted in red) in at least one pair of objective functions. Focusing first in the important case of full reuse, xFR , Figure 9b indicates that no solution in X? is able to dominate xFR from the perspective of f1 and f2 , meaning that FFR only offers a tradeoff with respect to full reuse; the same situation obtained in synthetic/hexagonal grids. Recall that, the peformance of baseline designs was strictly worse than full reuse in realistic deployments, see Figure 4. However, by means of the FFR configurations obtained through Algorithm 1 , it is also possible to extend the spectral efficiency vs. cell edge performance tradeoff even to realistic deployments, as it has been shown herein. This result clearly proves the effectiveness of Algorithm 1, which makes possible to enhance the performance of FFR in realistic deployments, and even more, attain this tradeoff (with respect to xFR) by saving some power over the air interface. Therefore, in order to provide such quantitative perspective, Figure 10 shows the gains that can be obtained (with 5 Note that 2D profiles are generated by projecting the Pareto Front onto the f1 - f2 , f1 - f3 , and f2 - f3 planes. They are an alternative representation providing better insights about the tradeoff between each pair of objective functions. respect to each benchmak) by the solutions in X? . By analyzing the 2D profiles and the information shown in Figure 10 jointly, the merit of the proposed framework with respect to each benchmark can be clearly appreciated. For instance, with respect to full reuse ( xFR ), Figure 9b shows that only a tradeoff can be obtained, i.e., f1 and f2 can not be simultaneously improved by any configuration in X? . However, no matter which configuration is selected, the transmission power is reduced up to 65% with respect to xFR . A similar analysis also holds for the rest of benchmarks. Note also that, the performance of xHR3 is, as expected, poor in irregular layouts, thus confirming the results previously presented in Figure 4. Indeed, almost all the elements in X? dominate xHR3 from the perspective of f1 and f2 , achieving gains of around 30% and 70% respectively. However, xHR3 features the lowest energy consumption, and hence, no solution achieves gains in terms of f3 . Nevertheless, as it can be seen in Figures 9c and 9d, the energy consumption of the the elements of X? is basically in the same order of magnitude that xHR3 , and hence, this marginal loss is compensated by far through the gains in terms of f1and f2. Finally, the rest of baseline designs are all dominated, in terms of all performance metrics, by a subset of elements in X? , meaning that there is no point in using these designs in place of optimized FFR by means of Algorithm 1. Gains in terms of f1 range from 10% to 45%, while the ones with respect to f2 range from 10% to 30%. Therefore, as a result, the effectiveness of the proposed scheme has been demonstrated from the perspective of system level performance metrics. Another important point of view is cell level performance. Figure 11 shows the statistic of f1 , f2 , and f3 for the network configurations in X? . In addition, cell level version of these metrics, fc 1 , fc 2 and fc 3 , are also shown. In order to simplify the analysis and for the sake of clarity, the following discussion is strictly focused on the important case of full reuse, xFR . However, a similar analysis also holds for the rest of benchmarks. The results indicate that 43% and 20% of the elements in X? outperform xFR in terms of f1 and f2 , respectively. In addition, an average energy saving of 65% is also obtained. Note that the distribution of f3 is the same as fc 3 . Moreover, looking at fc 1 and fc 2 , it is clear that the proposed framework brings to mobile operators a wide range of possibilities to