Resource Allocation and Performance Evaluation inHeterogeneous and Relay-based Wireless NetworksbyHamidreza BoostanimehrM.A.Sc., The University of British Columbia, 2010B.Sc., Sharif University of Technology, 2008A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August 2014c© Hamidreza Boostanimehr 2014AbstractIn the last decade, the mobile data demand has been exponentially growing. Telecommuni-cation industry finds it increasingly difficult to cope with this exponential growth throughconventional cellular networks with carefully planned high power macro base stations (BSs).Therefore, the densification of BSs through the introduction of low power BSs has been con-sidered for implementation. The combination of macro BSs and low power BSs such as picoand femto BSs as well as relay nodes is referred to as heterogeneous networks (HetNets).HetNets impose major technical challenges in implementation such as severe interferencecases and imbalance of load among macro BSs and low power BSs. One of the problemsthat needs to be re-addressed in the context of HetNets is the cell association problem.Although centralized cell association schemes are important in realizing the potentials ofHetNets, mobile operators are interested in distributed schemes in which network elementsdecide based on their local information. In this thesis, we consider distributed cell associationalgorithms with quality of service provisioning. First, we propose a unified cell associationalgorithm that is particularly designed for downlink. Next, we also consider uplink to havea downlink and uplink aware cell association scheme. The performances of the proposedschemes are examined through numerical simulations.Cooperative relay-based communication combined with orthogonal frequency divisionmultiplexing (OFDM) and its multi access variant, orthogonal frequency division multipleaccess (OFDMA) has gained an immense interest in the last decade. Among all the researchtopics in OFDM relay-based communication, analyzing the outage behavior has been aninvariable concern to researchers. To analyze the outage behavior, most of the researchersignore the correlation between OFDM subchannels, and also assume equal bit allocation onall the subchannels. In this thesis, we analyze the outage behavior of a three-node OFDMrelay-based network when these two assumptions are relaxed. Next, we characterize theglobal outage probability of a multi-user single-relay OFDMA network. Finally, a networkconsisting of a cluster of source-destination pairs and a cluster of relays is considered wherewe propose a low complexity relay allocation scheme. The outage analyses and the relayallocation scheme are examined through numerical simulations.iiPrefacePublications that have been resulted during the conduction of research in this thesis are asfollows:• H. Boostanimehr, V. K. Bhargava. Unified and Distributed QoS-Driven Cell Associa-tion Algorithms in Heterogeneous Networks. First round of revisions submitted to apeer reviewed journal, pages 1–13, Jul. 2014. (Linked to Chapter 2)• H. Boostanimehr, V. K. Bhargava. Distributed and QoS-Driven Cell Association inHetNets to Minimize Global Outage Probability. Accepted to be presented in 2014IEEE GLOBECOM, pages 1–7, Apr. 2014. (Linked to Chapter 2)• H. Boostanimehr, V. K. Bhargava. Joint Downlink and Uplink Aware Cell Associationin HetNets with QoS Provisioning. Submitted to a peer reviewed journal, pages 1–13,May 2014. (Linked to Chapter 3)• H. Boostanimehr, V. K. Bhargava. Outage Capacity Analysis for OFDM Decode-and-Forward Systems in Frequency Selective Rayleigh Fading Channels. IEEE Communi-cations Letters, 16(6):937–940, Jun. 2012. (Linked to Chapter 4)• H. Boostanimehr, V. K. Bhargava. Outage Probability Analysis for Multi-User Single-Relay OFDMA DF Networks in Frequency Selective Rayleigh Fading Channels. IEEECommunications Letters, 18(2):245–248, Feb. 2014. (Linked to Chapter 5)• H. Boostanimehr, V. K. Bhargava. Outage Analysis and Relay Allocation for Multi-stream OFDMA Decode-and-Forward Rayleigh Fading Networks. In Proceedings of2012 IEEE ICCC, pages 630–635. (Linked to Chapter 6)I am the primary researcher and author for all the research contributions made in thisthesis. I conducted the literature review and identified the research problems. Moreover, Iindependently formulated the research problems and carried out the mathematical analysisand simulations. I also wrote the associated manuscripts for publication. My supervisor,Prof. Vijay K. Bhargava, is a co-author for contributions made in all the papers. I consultediiiPrefacehim during the identification and formulation of the research problems. He also providedtechnical and editorial feedback during the preparation of associated manuscripts.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Overview of heterogeneous networks . . . . . . . . . . . . . . . . . . . . . . 31.2 Overview of cooperative communication . . . . . . . . . . . . . . . . . . . . 61.3 Overview of 3GPP LTE standard . . . . . . . . . . . . . . . . . . . . . . . . 81.4 Scope, motivations, and objectives . . . . . . . . . . . . . . . . . . . . . . . 101.4.1 Scope, motivations, and objectives in HetNets . . . . . . . . . . . . . 111.4.2 Scope, motivations, and objectives in relay-based communication . . 151.5 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 Unified and Distributed QoS-Driven Cell Association Algorithms in Het-Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.1.1 The channel model, instantaneous rate, long term rate and outageprobability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.1.2 Rate and outage QoS constraints . . . . . . . . . . . . . . . . . . . . 252.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26vTable of Contents2.2.1 Sum utility of long term rate maximization with rate QoS constraints 272.2.2 Global outage probability minimization with outage QoS constraints 282.3 Cell association phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.3.1 Cell association solution . . . . . . . . . . . . . . . . . . . . . . . . . 302.3.2 Feasibility problem and admission control . . . . . . . . . . . . . . . 332.3.3 Distributed cell association protocol design . . . . . . . . . . . . . . 332.4 RB distribution phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.4.1 Sum utility of rate maximization . . . . . . . . . . . . . . . . . . . . 342.4.2 Global outage probability minimization . . . . . . . . . . . . . . . . 352.5 Numerical simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 362.5.1 Rate cumulative distribution functions . . . . . . . . . . . . . . . . . 372.5.2 The effect of number of femto BSs . . . . . . . . . . . . . . . . . . . 412.5.3 The effect of number of users . . . . . . . . . . . . . . . . . . . . . . 422.5.4 The effect of distributing the remaining RBs . . . . . . . . . . . . . 443 Joint Downlink and Uplink Aware Cell Association in HetNets with QoSProvisioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543.3 Base line cell association solution . . . . . . . . . . . . . . . . . . . . . . . . 563.4 Distributed cell association solution . . . . . . . . . . . . . . . . . . . . . . 573.4.1 Worst case uplink outage probability and the associated required num-ber of RBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583.4.2 Cell association solution . . . . . . . . . . . . . . . . . . . . . . . . . 593.4.3 Distributed cell association scheme design . . . . . . . . . . . . . . . 633.4.4 Feasibility problem and admission control . . . . . . . . . . . . . . . 633.4.5 RB distribution phase . . . . . . . . . . . . . . . . . . . . . . . . . . 653.5 Numerical simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 663.5.1 Rate cumulative distribution functions . . . . . . . . . . . . . . . . . 673.5.2 The effect of number of femto BSs . . . . . . . . . . . . . . . . . . . 713.5.3 The effect of number of users . . . . . . . . . . . . . . . . . . . . . . 723.5.4 The effect of distributing the remaining RBs . . . . . . . . . . . . . 744 Outage Capacity Analysis for OFDM Decode-and-Forward Systems in Fre-quency Selective Rayleigh Fading Channels . . . . . . . . . . . . . . . . . . 784.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79viTable of Contents4.2 Outage probability analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 824.2.1 Special case: i.i.d. OFDM subcarriers . . . . . . . . . . . . . . . . . 854.3 Numerical simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 865 Outage Probability Analysis for Multi-User Single-Relay OFDMA Decode-and-Forward Networks in Frequency Selective Rayleigh Fading Channels 895.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905.2 Global outage probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945.3 Numerical simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 966 Outage Analysis and Relay Allocation for Multi-Stream OFDMA Decode-and-Forward Rayleigh Fading Networks . . . . . . . . . . . . . . . . . . . . 996.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1006.2 Outage probability of a single source-relay-destination link . . . . . . . . . . 1046.3 Problem formulation and proposed relay allocation scheme . . . . . . . . . . 1066.4 Numerical simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 1087 Conclusions and Future Research Directions . . . . . . . . . . . . . . . . . 1137.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1137.2 Future research directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119viiList of Tables2.1 List of key parameters in Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . 223.1 List of key parameters in Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . 50viiiList of Figures1.1 Wireless technology evolution . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 A HetNet composed of macro, pico, and femto BSs and relay nodes . . . . . 41.3 Simplified three-node cooperative model . . . . . . . . . . . . . . . . . . . . 81.4 RB-based structure of resources in LTE . . . . . . . . . . . . . . . . . . . . . 92.1 The CDFs of users’ long term rate for the rate problem in a static setting . . 372.2 The CDFs of users’ instantaneous rate for the rate problem in a stochasticsetting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.3 The CDFs of users’ instantaneous rate for the outage problem and outageprobability of T = 10% in a stochastic setting . . . . . . . . . . . . . . . . . 392.4 The rate gain of the optimal linear program algorithm, the rounding algo-rithm, and our distributed algorithm over maximum SINR algorithm for therate problem in a stochastic setting . . . . . . . . . . . . . . . . . . . . . . . 402.5 The average sum utility of instantaneous rate against number of femto BSsfor the rate problem in a stochastic setting . . . . . . . . . . . . . . . . . . . 422.6 The probability of no users being in outage against number of femto BSs forthe outage problem and outage probability of T = 10% . . . . . . . . . . . . 432.7 The average sum utility of instantaneous rate against number of users for therate problem in a stochastic setting . . . . . . . . . . . . . . . . . . . . . . . 442.8 The probability of no users being in outage against number of users for theoutage problem and outage probability of T = 10% . . . . . . . . . . . . . . 452.9 The average sum utility of instantaneous rate against minimum rate for therate problem showing the effect of distributing the remaining RBs in a stochas-tic setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.10 The probability of no users being in outage against minimum rate for theoutage problem and outage probability of T = 10% showing the effect ofdistributing the remaining RBs . . . . . . . . . . . . . . . . . . . . . . . . . 47ixList of Figures3.1 Downlink rate CDFs for the developed schemes with various wDL and maxi-mum SINR scheme, where γDL = 1.2 bits/s, γUL = 0.6 bits/s, T = 10%, andM = 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683.2 Uplink rate CDFs for the developed schemes with various wUL and maximumSINR scheme, where γDL = 1.2 bits/s, γUL = 0.6 bits/s, T = 10%, and M = 8 693.3 Uplink rate CDFs for the distributed scheme with various M and γUL, andbase line and maximum SINR schemes with various γUL, where wUL = 1 . . 713.4 Downlink average utility of rate against number of femto BSs for the developedschemes with various wDL and maximum SINR scheme, where γDL = 1.2bits/s, γUL = 0.6 bits/s, T = 10%, and M = 10 . . . . . . . . . . . . . . . . 723.5 Uplink average utility of rate against number of femto BSs for the developedschemes with various wUL and maximum SINR scheme, where γDL = 1.2bits/s, γUL = 0.6 bits/s, T = 10%, and M = 10 . . . . . . . . . . . . . . . . 733.6 Downlink average utility of rate against number of users for the developedschemes with various wDL and maximum SINR scheme, where γDL = 1.2bits/s, γUL = 0.6 bits/s, T = 10%, and M = 10 . . . . . . . . . . . . . . . . 743.7 Uplink average utility of rate against number of users for the developedschemes with various wUL and maximum SINR scheme, where γDL = 1.2bits/s, γUL = 0.6 bits/s, T = 10%, and M = 10 . . . . . . . . . . . . . . . . 753.8 Downlink average utility of rate against minimum downlink rate threshold forthe developed schemes with wDL = 1 and T = 10%, showing the effect ofdistributing the rest of RBs in downlink . . . . . . . . . . . . . . . . . . . . 763.9 Uplink average utility of rate against minimum uplink rate threshold for thedeveloped schemes with wUL = 1, T = 10%, M = 10, showing the effect ofdistributing the rest of RBs in uplink . . . . . . . . . . . . . . . . . . . . . . 774.1 System model (a) First time slot (b) Second time slot . . . . . . . . . . . . . 794.2 Outage probability against transmitted SNR when PR = PS for L = 4, 6, 8and i.i.d. subcarriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874.3 Outage probability against transmitted SNR when PR = 0.1·PS for L = 4, 6, 8and i.i.d. subcarriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885.1 System model (a) System configuration (b) OFDMA setup . . . . . . . . . . 905.2 Global outage probability against transmitted SNR when PR = PS for NS =2, 3, 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97xList of Figures5.3 Global outage probability against transmitted SNR when PR = 0.1 · PS forNS = 2, 3, 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 986.1 System model (a) System configuration (b) OFDMA setup . . . . . . . . . . 1016.2 Simulated global outage probability against SNR when Ns = Nr = 4 andNφ = 16, for L = 4, 6, 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1096.3 Simulated global outage probability against SNR when L = 4 and Nφ = 16,for Ns = Nr = 4, 6, 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1106.4 Simulated and analytical global outage probabilities against SNR when L = 4and Ns = Nr = 4 for Nφ = 4, 16. . . . . . . . . . . . . . . . . . . . . . . . . . 111xiList of Abbreviations2G : Second Generation of cellular networks3GPP : 3rd Generation Partnership Project4G : Fourth Generation of cellular networksABS : Almost Blank SubframeAF : Amplify-and-ForwardAMC : Adaptive Modulation CodingAP : Access PointCDF : Cumulative Distribution FunctionCDMA : Code Division Multiple AccessCoMP : COordinated Multi-Point reception and transmissionCSR : Cell Specific Reference signalDF : Decode-and-ForwardEBA : Equal Bit AllocationeICIC : Enhanced Inter-Cell Interference CoordinationeNB : Evolved Node BFCC : Federal Communications CommissionFDMA : Frequency Division Multiple AccessHARQ : Hybrid Automatic Repeat reQuestHeNB : Home Evolved Node BHetNet : HETerogenous NETworksHSPA : High Speed Packet AccessICIC : Inter-Cell Interference Coordinationi.i.d. : Independent and Identically DistributedIP : Internet ProtocolKKT : Karush-Kuhn-TuckerLOS : Line Of SightLTE : Long Term EvolutionLTE-Advanced : Long Term Evolution-AdvancedMIMO : Multiple Input Multiple OutputxiiList of AbbreviationsMRC : Maximum Ratio CombiningN -DFT : N point Discrete Fourier TransformOFDM : Orthogonal Frequency Division MultiplexingOFDMA : Orthogonal Frequency Division Multiple AccessPDF : Probability Distribution FunctionQoS : Quality Of ServiceRB : Resource BlockRN : Relay NodeRNC : Radio Network ControllerRV : Random VariableSC-FDM : Single Carrier-Frequency Division MultiplexingSC-FDMA : Single Carrier-Frequency Division Multiple AccessSINR : Signal to Interference plus Noise RatioSNR : Signal to Noise RatioTDMA : Time Division Multiple AccessUE : User EquipmentxiiiAcknowledgementsFirst and foremost, I would like to thank my supervisor, Prof. Vijay K. Bhargava, for theguidance and support that he has provided. This thesis would not have been possible withouthis suggestions, advice and constant encouragement.Furthermore, I would like to extend my utmost gratitude to my lab mates for creating afriendly environment, in which I could carry out my research project.Finally, heartfelt and deep thanks go to my family, who have always encouraged meand given their unconditional support throughout my studies at the University of BritishColumbia. Without their support, I could not have completed this thesis.xivDedicationTo my parents...xvChapter 1IntroductionIn recent years, the proliferation of intelligent mobile devices that are connected to theInternet has changed the communication paradigms. Nowadays, users can communicatewith each other at any time and through different mediums such as video, voice, instantmessage, and email. Users also are interested in sharing their everyday experiences withtheir circles through social media. The powerful mobile devices make generating data andconsuming data from other users possible. Moreover, the number of machines that areconnected to and controlled through the Internet is increasing everyday, extending the reachof Internet from users to machines [1]. It seems that the world is changing rapidly towardsthe Internet of everything. In fact, it is predicted that by the year 2020 more than 50 billiondevices will be connected to the Internet [2]. The tendency of users to communicate throughall sorts of media, the introduction of social networks and Internet of things, among otherfactors, have created an exponential growth in mobile data demand [3].In order to cope with this exponential growth, the most immediate option seems to beincreasing the spectral efficiency of the point to point communication. However, through therelentless efforts of industrial and academic researchers in recent decades, we are reaching theShannon capacity in link level communication in wireless systems. Migrating from secondgeneration of cellular wireless networks (2G) to today’s fourth generation (4G), the spectralefficiency has been approaching the fundamental limit through the introduction of all sortsof technologies including powerful channel coding schemes, new multiple access schemessuch as code division multiple access (CDMA) [4], orthogonal frequency division multipleaccess (OFDMA) [5], and multiple input multiple output (MIMO) antennas [6] (Fig. 1.1)[7]. Although the air interface in point to point communication keeps on improving, theanticipated improvement is not adequate to support the exponential growth of data demand.Therefore, other venues to improve the network capacity need to be investigated.Data rate is directly proportional to communication bandwidth. Therefore, acquiringmore spectrum seems to be another venue to enhance the capacity of wireless networks.However, the spectrum is highly regulated by Federal Communications Commission (FCC)and is already densely populated by various industries and applications. In fact, the scarcityof spectrum has given rise to technologies such as dynamic spectrum sharing and cognitive1Chapter 1. Introduction015304560 Fundamental limit(((2G3G4GCDMAAMC+HARQOFDM+MIMOOFDM+MIMO CoMP/eICICHeterogeneous NetworksSpectral EfficiencyNetwork EfficiencyWireless technology evolutionFigure 1.1: Wireless technology evolutionradio techniques [8] in the last decade as it is indicated by FCC that the spectrum has notbeen efficiently regulated and it is highly under-utilized in many cases [9]. The scarcityof the spectrum also contributes to making spectrum acquisition for wireless industries un-reasonably costly. As a result, in an attempt to improve the network capacity by ordersof magnitude, the tendency is to reuse the already available spectrum more efficiently byadding more base stations (BSs) to the network. In other words, the focus is to increase thenetwork efficiency rather than the spectrum efficiency to meet this unprecedented mobiledata demand.Conventional cellular networks are composed of several cells. Each cell is served byone BS that is referred to as macro BS. The BSs in conventional cellular networks havehigh transmitting powers and cover large geographical areas. In a cellular network withsparse deployment of macro BSs, adding new macro BSs does not add significant inter-cellinterference, and the frequency spectrum can be reused with considerable gains. However,few factors set back the use of extra macro BSs. One of the factors is the cost of deployingnew macro BSs. In already dense deployment of macro BSs, it is expensive to acquire sitesto install new macro BSs. In addition, the BS itself is an expensive device, and macroBSs require air conditioning on their power amplifier since they have high transmittingpowers in the range of 2 to 40 W. Another factor is that the existence of coverage holes in21.1. Overview of heterogeneous networksthese large cells is expected since the urban environment conditions render the behavior ofwireless channels random. The existence of coverage holes reduces the overall capacity ofthe network by increasing the likelihood of outage. Furthermore, there are hot spots duringcertain times of the day where many mobile users desire to have connectivity with goodquality of service (QoS). Since BSs, including macro BSs, have finite resources to distributeamong their users, all the users in hotspots may not be supported with acceptable QoS andfurther communication outage is resulted. The mentioned challenges of installing new macroBSs, among others, give rise to the idea of deploying low power BSs and relays to cover hotspots and coverage holes with considerably lower cost. Overlaying macro BSs with lowerpower BSs such as pico, femto, and relay stations constitutes what we call a heterogeneouscellular network [10].In the next section, we provide a brief overview of heterogeneous networks (HetNets).Since some parts of the research presented in this thesis address relay-based cooperativecommunication, we will briefly go through the fundamentals of cooperative communicationin Section 1.2. Finally, as the Long Term Evolution (LTE) standard is the most dominantstandard defining 4G and highly correlated to the context of today’s wireless communicationresearch, some key features of this standard are overviewed in Section 1.3.1.1 Overview of heterogeneous networksHetNets can be defined as cellular networks composed of macro BSs overlaid with lowerpower BSs (lower tier BSs or smaller cells), in which the low power BSs are deployed withhigher density. The lower tier BSs can be pico BSs, femto BSs, or relay stations. MacroBSs with their high transmitting power cover large geographical areas, while coverage holesand hot spots are covered by lower tier BSs. The lower tier BSs may be installed outdooror cover indoor environments. Pico BSs usually are meant to be installed outdoor and havetransmitting power in the range of 250 mW up to 2 W. Since the transmitting power isconsiderably low compared to macro BSs, air conditioning the power amplifier at the picoBSs is generally not required. In addition, as pico BSs are smaller in size and require smallerantennas, they are economically efficient to employ. Femto BSs are considered for servingindoor environments such as residential homes or a certain floor in an enterprise building [11].As an example, a WiFi access point (AP) can be considered a femto BS [12]. However, inthe case of WiFi AP, a different air interface is used compared to the air interface of outdoorBSs, and only authorized users may be served by the AP. Such femto BSs with restrictedaccess are referred to as closed femto BSs [12]. As femto BSs are already installed in homes31.1. Overview of heterogeneous networksMacroPicoPicoRelayFemtoWiFi APRelay wireless backhaulFigure 1.2: A HetNet composed of macro, pico, and femto BSs and relay nodesor enterprises, utilizing them leads to significant reduction in cost. In fact, economics of picoand femto BSs have been the main driver of considering their deployment in cellular networks[13]. Macro, pico, and femto BSs are usually connected to the core network through wire orhigh speed optical fibre.There are situations in which installing wired connection to the core network is notfeasible. In these cases, a relay node can be used to extend the coverage of macro BS.Users under the coverage of a relay node communicate to the macro BS through the relaynode. Relay node may use the same spectrum as the one users utilize or may be allocateddedicated spectrum to communicate to the macro BS. Re-using the spectrum for the BS torelay communication is more common. In this case, the relay node is equivalent to a BSfrom the user’s perspective, and the macro BS perceives the relay node as another user [14].The relay-based communication is a special case of a broader topic known as cooperativecommunication 1. In summary, to define HetNets more precisely, the collection of macro,pico, femto, and relay BSs that can be connected to the core network through wired orwireless backhaul is referred to as HetNet [15]. A simplified HetNet is illustrated in Fig. 1.2.As a legacy from conventional cellular networks, the most popular cell association schemein wireless cellular networks is the maximum signal to interference plus noise ratio (SINR)scheme. A cell association scheme is a set of rules that determines which BS serves a partic-ular user. In cellular wireless networks, BSs are constantly transmitting known reference orpilot signals to enable the users to measure some attributes of the downlink, including thereceived SINR. In maximum SINR scheme, each user associates itself to the BS that provides1A brief overview of the fundamentals of cooperative communication is provided in the next section.41.1. Overview of heterogeneous networksthe best SINR. Following this scheme creates an imbalance in HetNets between macro BSsand lower tier BSs. Macro BSs with their high power have large coverage areas and lowertier BSs have boundaries that are relatively close to them. Moreover, BSs usually operatein the same frequency bands to achieve frequency re-use gains (referred to as co-channeldeployment). Small coverage area of low tier BSs leads to underutilization of femto, pico,and relay stations that results in not achieving the expected gains from HetNets. In fact,the performance of co-channel deployment of multi-tier HetNets has been evaluated in earlyresearch [16, 17]. It is concluded in [16, 17] that higher gains would be achievable in Het-Nets, and the main reason that high gains are not reached is that the boundaries defined bylow tier BSs is very close to those BSs. In addition, macro BSs cause significant downlinkinterference on the lower tier BSs that are located in the vicinity of macro BSs.The small coverage area of low tier BSs causes an imbalance in the uplink interference atmacro and lower tier BSs, as well. Let us explain the uplink interference situation throughan example. Assume that a user is standing at a point where the downlink signal to noiseratio (SNR) received from a macro BS with nominal power of 40 dBm is equal to the SNRreceived from a femto BS with nominal power of 20 dBm. Assuming that only path lossis considered in the channel model, we can conclude that upon transmission of the user,the received power at the femto BS is 20 dB higher than the received power at the macroBS. Further assume that this boundary user is served by the macro BS, and 5 dB of powerabove the thermal noise is required by the macro BS to decode the user data correctly. Thisresults in an interference that is 25 dB above the thermal noise power at the femto BS. Thishigh level of interference corrupts the uplink connection of the users associated with thefemto BS severely. Interference management techniques in the scope of 3G cellular networksis presented in [18] to handle the downlink and uplink interference scenarios in macro andfemto deployment of HetNets. In [18], carrier selection and power control by the femtoBS is proposed to handle the downlink interference scenarios, and adaptive attenuation ofunwanted signals from macro user at the femto BS is proposed to cope with the uplinkinterference scenarios.As the conventional maximum SINR cell association scheme creates the aforementioneddrawbacks in HetNets, cell association needs to be done in a more wisely fashion in whichthe imbalance of load among BSs from different tiers and severe interference situations indownlink and uplink are reduced. One simple and yet effective technique to achieve loadbalancing in HetNets that has been envisioned by Third Generation Partnership Project(3GPP) in the context of LTE-Advanced 2 is called cell range expansion [15]. In cell range2LTE-Advanced is the most dominant standard defining 4G wireless systems. The key features of LTEand LTE-Advanced are overviewed in Section 1.3.51.2. Overview of cooperative communicationexpansion, the signal power of lightly loaded BSs are biased so that their coverage areaincreases and more users associate themselves with lightly loaded BSs. Intuitively, low tierBSs are usually under-utilized and cell range expansion is towards offloading the users frommacro BSs to lower tier BSs. However, a negative bias value at low tier BSs can happenwhich indicates that offloading the users to macro or other low tier BSs should occur.In cases which the location of the low tier BS is in the vicinity of the macro BS, highinterference caused by the offloaded macro BS on the downlink of the low tier BS can causelink failure. Therefore, inter-cell interference coordination (ICIC) is needed along with cellrange expansion to realize the offloading gains. In 4G standards, specifically LTE systems, anew structure for resources is used that is suitable for designing flexible resource allocationand ICIC schemes. The air interface of LTE standard is developed based on OFDMA.OFDMA technology makes possible a structure in which the time-frequency spectrum isdivided into orthogonal resource blocks (RBs). The RB-based structure in LTE allows formore flexible resource allocation schemes which result in higher spectral efficiency [19]. Oneway of reducing interference among cells is to use resource partitioning in time, frequency,or space domain [20, 21]. Resource partitioning involves using orthogonal resources in cellsthat potentially interfere with each other. Through RB-based resources, BSs can coordinateso that the interfering BS gives up using parts of resources on certain frequency bands andduring certain times so that the other BS can accomplish its communication with the user.In the context of LTE, this ICIC technique is accomplished through almost blank subframes(ABSs). Cell range expansion along with resource partitioning ICIC through ABS has shownto achieve considerable load balancing and interference avoidance gains [22, 23].1.2 Overview of cooperative communicationDuring the last decade, the focus of wireless communication has been diverging from onlyvoice applications towards applications such as wireless broadband Internet, online gaming,video streaming and many other applications. The data rate hungry nature of new appli-cations has been driving the researchers to work on improving the spectral efficiency of thewireless communication links. MIMO systems are among the most successful technologiesallowing for increasing the data rate by increasing the number of antennas at the transmitterand receiver sides. However, installing multiple antennas is not feasible at all the devices.In order to achieve MIMO gains, antennas must be separated enough so that spatial diver-sity through the reception or transmission of independent copies of the signal is realized.In addition, antennas can be prohibitively bulky devices themselves. Therefore, installing61.2. Overview of cooperative communicationmultiple antennas on small devices such as cell phones and in applications such as sensornetworks can prove infeasible. In order to resolve the prohibitive size of MIMO systems,cooperative communication came to the picture to harvest MIMO gains without installingmultiple antennas. In cooperative communication, users cooperate with each other as relaysto virtually create a MIMO system by transmitting a copy of each other’s signals to thedestination. The geographical separation of cooperative nodes creates enough spatial diver-sity so that the received copies of the signal go through independent fadings. Removing theextra antennas significantly reduces the cost of the system in cooperative communication.The three-terminal cooperation model was first introduced by Van Der Meulen in [24].The three-terminal cooperation model is composed of a source, a relay, and a destination,and is the building block of cooperative and relay-based communication. Then, the infor-mation theoretic aspects of the three-terminal model, including the calculation of Shannoncapacity, have been investigated in [25]. Most of the ideas that came along later on coop-erative communication can be traced back to the work in [25]. The technical complexity ofthe cooperative model at the time made it unattractive to the researches and it has beenabandoned for a while. Then, the evolution of wireless technology made possible the prac-tical implementation of the model and it regained popularity. Cooperative communicationtechniques are being used to improve coverage, enhance capacity and combat shadowing inwireless communication networks such as cellular or mesh networks [26]. As it has beenmentioned before, cooperative communication also introduces spatial diversity by creatingcopies of the signal that have gone through independent channel fadings [27, 28]. Coopera-tive communication through multi-hop transmission can also contribute to energy efficientcommunication by breaking the long point to point distance into several short distance hops[29, 30]. In addition, low power relay nodes are being considered by 3GPP to be imple-mented in LTE-Advanced for planning HetNets efficiently. Relay nodes extend the coverageand capacity of HetNets at the cell boundaries without incurring high site acquisition andbackhaul costs [31].Fig. 1.3 illustrates the procedure in the fundamental three-node cooperation model. Inorder to avoid interference, the relay-based communication usually happens in two orthogonalphases. The orthogonality can be in time domain through time division multiple access(TDMA) or in frequency domain through frequency division multiple access (FDMA), whileTDMA is more popular. In the first phase, the source broadcasts its information signal andboth the relay and destination listen. In the second phase, the relay forwards the wholeor parts of the source message to the destination through one of the fundamental relayingprotocols or variants of them. The destination combines both copies of the received signalto have a more reliable detection. In many cases, there is no line of sight (LOS) between the71.3. Overview of 3GPP LTE standardSource DestinationRelaySourceRelayDestinationa) Phase 1 b) Phase 2Figure 1.3: Simplified three-node cooperative modelsource and destination. Therefore, the destination only relies on the message it has receivedfrom the relay. In this case, the relay is merely used for coverage extension.Two fundamental relaying methods have been defined in [27]: Amplify-and-forward (AF),and decode-and-forward (DF). In AF protocol, the relay simply amplifies and forwards theanalog signal it has received from the source. The destination combines the two copies ofthe signal, for instance using maximum ratio combining (MRC), to have a reliable detection.Naturally, the noise introduced at the relay also gets amplified and sent to the destinationleading to higher noise level.In DF protocol, the relay decodes the message it has received from the source, re-encodesa new one, and then forwards it to the destination. The relay may perform the decode-and-re-encode process in different fashions. For instance, the relay may decode the message fullyand re-encodes a new one, it may add incremental redundancy for better channel coding, orit may decode it symbol by symbol knowing that the full decoding occurs at the destination.This degree of freedom in decode-and-re-encode process at the relay allows for a trade-offbetween performance and complexity [27]. In this thesis, only DF protocol is addressed.1.3 Overview of 3GPP LTE standardThe first release of LTE, referred to as LTE Release-8, has been published in 2009 by 3GPPfor 4G cellular networks [32, 33]. LTE is fully designed on packet-based radio access struc-ture; thus, LTE only supports radio access technologies that provide Internet protocol (IP)-based functionalities. Compared to 3G standards such as 3GPP’s High Speed Packet Access(HSPA), LTE allows for higher peak data rates by scaling the spectrum up to 20 MHz andutilizing higher number of MIMO antennas. LTE Release-8 supports up to 300 Mb/s and 7581.3. Overview of 3GPP LTE standardOne RB 12 OFDM subcarriers 6 or 7 OFDM symbolsOne OFDM subcarrier (15 kHz)One time slot 0.5 ms long 6 or 7 OFDM symbolsOne resource elementFigure 1.4: RB-based structure of resources in LTEMb/s of data rate in downlink and uplink, respectively. In LTE Release-8, up to 4 transmitand receive antennas are anticipated. The downlink of LTE is based on OFDM [5] technol-ogy, and the uplink is based on single carrier-frequency division multiplexing (SC-FDM) [34].OFDM is one of the most attractive techniques to combat frequency selectivity in wide bandchannels. In OFDM, the wide band channel is divided into several narrow band flat fadedsubchannels. OFDMA [35] is the multiple access variant of OFDM in which simultaneousstreams are possible by allocating each user a disjoint subset of available OFDM subchannels3. The multiple access variant of SC-FDM is referred to as single carrier-frequency divisionmultiple access (SC-FDMA) [34]. SC-FDMA has a similar structure and complexity to thoseof OFDMA. However, SC-FDMA results in low peak to average power ratio which is suitablefor mobile devices on which installing complex and high performance power amplifier is notfeasible. Performance comparison of OFDMA and SC-FDMA can be found in [36] and [37].The macro BSs in LTE are referred to as evolved node B (eNB), while pico and femtoBSs are referred to as home eNB (HeNB). Relay stations are denoted by relay node (RN),and the BS that serves the RN is denoted as the donor eNB (DeNB). Finally, the mobileuser is denoted by user equipment (UE). Furthermore, eNBs can directly talk and coordinatewith each other through an interface denoted by X2 interface [38, 39]. In previous standardsdeveloped by 3GPP, a dedicated unit referred to as radio network controller (RNC) used toperform the functionalities regarding coordination among BSs. In LTE, the RNC is removedand its functionalities are transferred to eNBs which use X2 interface to exchange informationregarding load balancing and ICIC.As mentioned before, in LTE, OFDMA technology is used in downlink, and a variationof OFDMA called SC-FDMA is used in uplink. The channel bandwidth is divided into 153In this thesis, OFDM subchannel and OFDM subcarrier are used interchangeably.91.4. Scope, motivations, and objectiveskHz OFDM subcarriers in both downlink and uplink. The number of subcarriers available ateach BS depends on the channel bandwidth that the BS has access to. In LTE, the channelbandwidth is intended to be scalable, and can be for example 1.4, 3, 5, 10, 15, or 20 MHz.The more the channel bandwidth, the higher number of OFDM subcarriers are available atthe BS. The smallest resource structure over which a modulation occurs is called a resourceelement. A resource element spans over one OFDM subcarrier on the frequency axis, and oneOFDM symbol duration on the time axis. The aggregation of 12 adjacent OFDM subcarriersand 6 or 7 OFDM symbols is referred to as an RB. Each RB spans over 180 kHz on thefrequency axis and 0.5 ms on the time axis. An RB is the smallest resource structure thatis given to a user for possible transmission [40]. The number of RBs allocated to each userdepends on the QoS that the user requires. For instance, if a user requires a high data rate,the number of RBs allocated to that user is higher than a user requiring less data rate. TheRB-based structure of the resources in LTE is illustrated in Fig. 1.4.In the downlink of LTE, each antenna port of each eNB constantly transmits a cellspecific reference (CSR) signal [41]. CSR signal is used by UEs for various purposes includingcell search and initial cell association, and downlink channel estimation for demodulationand detection. The CRS symbols are spread over resource elements in a way that robustestimation of time and frequency is possible at the UE.Last but not least, 3GPP released LTE Release-10 in 2011. LTE Release-10 along withlater releases of LTE are also known as LTE-Advanced [33]. The last finalized release ofLTE-Advanced is LTE Release-11 which was closed in 2013. 3GPP is now working on LTERelease-12. The peak data rate requirements in LTE-Advanced are 1 Gb/s and 500 Mb/sin downlink and uplink, respectively. Among the key features that are different in LTE-Advanced compared to the original LTE are supporting higher order of MIMO antennas (upto 8 antennas for downlink and 4 antennas for uplink), introducing carrier aggregation [42],introducing coordinated multi-point reception and transmission (CoMP) [43], enhancing theICIC for deployment of co-channel HetNets, and focusing on RN features [40]. Overall, theseadvancements in LTE-Advanced result in a better user experience.1.4 Scope, motivations, and objectivesThis section is divided into two subsections. In the following subsection, the scope, mo-tivations, and objectives behind the research contributions of this thesis in the context ofHetNets are provided. Subsection 1.4.2 is dedicated to the scope, motivations, and objectivesbehind the research contributions of this thesis in the context of relay-based communication.101.4. Scope, motivations, and objectives1.4.1 Scope, motivations, and objectives in HetNetsHetNets are built upon conventional cellular networks; thus, the research problems in con-ventional cellular networks such as cell association, ICIC, and resource allocation [15] need tobe re-addressed in the context of HetNets. Cell association problem, which is to be addressedin this thesis, is involved with defining a set of rules to determine which BS serves a particu-lar user. Most of the cell association schemes are designed based on the downlink maximumSINR scheme [44]. In maximum SINR scheme, users estimate the downlink SINR from theBSs in their range by listening to the BSs’ reference signals and associate themselves withthe best SINR providing BS. This scheme is not suitable for HetNets mainly because of tworeasons. The first reason is that macro BSs in HetNets have higher transmitting powers andattract more users which leads to imbalance of load among the BSs. The resource budget ofoverpopulated BSs is distributed among more users which translates into lower throughputfor those users. Therefore, load balancing should be achieved in the cell association phasein the context of HetNets. The second reason that renders maximum SINR cell associationscheme unsuited for HetNets rises from the fact that there is an intrinsic asymmetry amonguplink and downlink SINR levels in HetNets [44]. The sources of interference in the downlinkare BSs with considerably high powers, while the sources of interference in the uplink arethe mobile nodes with low levels of power and different geographical distribution. Therefore,an association rule designed for downlink is not necessarily suitable for the uplink, and viceversa.From another perspective, wireless operators are interested in distributed cell associationschemes where nodes decide based on their local measurements of the network, as opposedto centralized schemes where one central node decides for all the other nodes. The requiredmessage passing load in centralized algorithms renders them unappealing for practical im-plementation. The technical simplicity of distributed algorithms motivates us to addressdistributed cell association schemes in this thesis.In cellular networks such as LTE, the BSs are constantly transmitting reference sig-nals that enable the mobile users to measure some attributes of the downlink channel [41].However, mobile users cannot measure the attributes of the uplink channel without com-municating to the BS. Therefore, designing distributed cell association schemes is easier indownlink, while it is a major challenge in uplink. It should also be mentioned that cellassociation problem in downlink, although well-studied for conventional cellular networks,has not been thoroughly addressed in the context of HetNets. These factors motivate us toaddress distributed cell association schemes that can be whether downlink oriented, uplinkoriented, or jointly downlink and uplink aware.111.4. Scope, motivations, and objectivesIn newly emerged standards such as LTE-Advanced, the resources available in the down-link and uplink are broken into smaller building blocks referred to as RBs. An RB occupiesa certain frequency range during a certain time interval. In LTE for instance, one RB spansover 12 OFDM subcarriers and 6 or 7 OFDM symbols, i.e., 180 kHz of bandwidth and 0.5 msof time duration [33]. The number of available RBs at each BS in the downlink and uplinkis proportional to the available bandwidth and scheduling interval at that BS. The numberof RBs allocated to each user on the other hand, depends on the QoS that the user requires.For instance, if the QoS is defined in terms of the data rate that a user requires, more RBsare assigned to a user with higher rate requirement. Distributing the resources in terms ofRBs among users introduces additional degrees of freedom in designing resource allocationschemes that results in higher spectral efficiency [19]. This motivates us to incorporate anRB-based model for the resources in this thesis in the context of cell association in HetNets.Cell association problem in HetNets has drawn plenty of attention recently. The cellassociation problem has mostly been addressed in downlink [45–57], while the uplink, andthe joint downlink and uplink cell association [58] have been barely touched.Formulating the cell association problem naturally falls into the scope of integer or mixedinteger programming since each user is to be mapped to a BS. There are several approachesto cope with these integer programs to achieve load balancing in the cell association phase.Solving the integer program directly by exploiting the structure of the problem [45, 46],relaxing the association constraints and using Lagrange dual decomposition method [47–49], Markov decision process frameworks [50, 51], game theoretic frameworks [52, 53], andstochastic geometry frameworks [54–57] are examples of these approaches among others. Inthe next two paragraphs, we focus on the first two approaches as they are more relevant tothe works presented in this thesis.Authors of [45] focus on flow level downlink cell load balancing and association underspatially inhomogeneous traffic distributions. A unified distributed and iterative algorithmis proposed that adapts to traffic loads and converges to the optimal point. The objectivefunction of the defined optimization problem in [45] can be selected from a family of objec-tive functions; each of which directs the solution towards a rate, throughput, delay, or loadbalanced optimal point. In [46], an online algorithm is developed based on the idea of associ-ating users with BSs that provide the best expected throughput instead of associating userswith the best SINR providing BS. Considerable interference avoidance and load balancinggains are achieved through the online algorithm proposed in [46]. In these two works, theassociation constraints are not relaxed and the proposed algorithms produce binary decisionvariables.In many cases, formulating the cell association problem leads to NP-hard assignment121.4. Scope, motivations, and objectivesproblems. Relaxing the association constraints and applying Lagrange dual decompositionmethod is a popular method to cope with these cases. This is because relaxing the associa-tion constraints usually converts the optimization problem into a convex or linear programfor which efficient algorithms exist. Additionally, dual decomposition methods usually leadto distributed algorithms in which the nodes in the network decide based on their localinformation, as opposed to centralized solutions which require global information access atone central node or all the nodes. Examples of distributed cell association algorithms fordownlink can be found in [47, 48]. In these works, the resources at each BS is distributedevenly among the users associated with that BS. In [47], it is proven that distributing theresources equally among the users connected to a given BS is optimal for a logarithmic objec-tive function. Based on this observation, a distributed algorithm is proposed that convergesto a near optimal point to improve the long term rate. The framework provided in [47] issuitable for environments that undergo slow fading (low mobility environments). Cell rangeexpansion technique by biasing the SINR of lightly loaded BSs to make them more attractiveto the users is also incorporated in the distributed algorithm in [47]. Extending over [47],in [48], the joint optimization of load balancing and enhanced intercell interference coordi-nation (referred to as eICIC by 3GPP) via ABS is considered. Lastly, [49] is another workin which a dynamic cell association and cell range expansion algorithm for load balancingthrough relaxation of association constraints is proposed. The algorithm presented in [49] isin a centralized fashion.Authors of [51] adopt an approach based on Markov decision process to tackle the cellassociation problem, and game theoretic approaches are considered in [52, 53]. Recently,stochastic geometry has been introduced as a mean to analyze the downlink SINR distribu-tion and devise cell association algorithms. It is assumed in such works that the low tierBSs are distributed according to a point Poisson process, then the probability distribution ofdownlink SINR is calculated over space. Examples of this approach can be found in [54–57].Finally, a centralized algorithm has been proposed in [58] to jointly maximize the downlinksystem capacity while minimizing the users’ uplink transmitting powers.At least one of the following shortcomings has been identified in the research worksmentioned in this subsection:• In most of the related works, providing QoS is not considered, and further it is assumedin the system models that the BSs are distributing all the resources among the users.In the case of having QoS constraints, once the users receive enough resources to satisfytheir QoS constraints, the need for expending more resources is eliminated. In addition,allowing the users to use more resources than their QoS requirements translates into131.4. Scope, motivations, and objectivesspending unnecessary power whether by the BS in downlink or user in the uplink.Spending power for extra resources reduces the energy efficiency. Energy efficiency isin particular important at the mobile user side, considering their limited battery life.• All the cell association works mentioned above, including the maximum SINR scheme,are downlink oriented. The only work in which one parameter of uplink is also consid-ered is [58]. The considered parameter is uplink transmit power. The uplink load orinterference on the BS is not considered in [58]. As it has been mentioned earlier, a cellassociation algorithm specifically designed for downlink does not show an acceptableperformance in the uplink.• The distributed cell association schemes are not investigated completely in the liter-ature. This is in particular the case for the uplink since users cannot measure theattributes of uplink by listening to the BS reference signals.• The RB-based structure of the resources is not explicitly considered in the systemmodels.• In most of the related works, only low mobility environments suffering from slow fadingare considered in the system models for designing distributed algorithms. This is thecase since most researchers choose to work with data rate, for which only the long termvariation is measurable at the users by listening to the reference signals of BSs. Linkoutage probability which is a venue to deal with fast fading environments has not beenincorporated in the context of cell association in HetNets.The above shortcomings in the literature motivated us to pursue the following objectivesin the context of cell association in HetNets:1. Designing distributed cell association schemes with QoS provisioning in the downlinkof a HetNet considering that BSs have finite number of RBs as their resource budget.2. Designing distributed cell association schemes in the downlink of a HetNet, that aresuitable for fast fading environments as well as slow fading environments.3. Designing distributed cell association schemes with QoS provisioning in a HetNet whereBSs have finite number of RBs as their resource budget in downlink and uplink, thatare jointly aware of downlink and uplink and yet are not complex and require lowamount of message passing.141.4. Scope, motivations, and objectivesThe contributions in Chapter 2 revolve around the first and second objectives, and thethird objective is addressed in Chapter 3. The contributions made regarding these objectivesare clarified in the beginning of each chapter.1.4.2 Scope, motivations, and objectives in relay-basedcommunicationIntroducing relays to wireless networks opens many interesting research problems. Amongthese problems, analyzing the outage behavior of relay-based systems seems to be one ofthe invariable concerns. Allocating relays to source-destination streams is also among thesetopics, which can be tackled to satisfy different kinds of objectives such as minimizing theglobal outage probability of the system. Authors of [27] first characterized the outage behav-ior of fundamental relaying protocols, namely DF and AF protocols, in high SNR regimes.Closed form solutions to the outage probability have been obtained in [59–61], for AF and DFmulti-hop communication systems assuming no direct link between source and destination.In all the aforementioned works, it is assumed that the channel is suffering from Rayleighflat fading.Data rate hungry applications have driven the wireless industry into using wider frequencychannels which undergo frequency selective fading. OFDM technology is among the bestcandidates combating frequency selectivity by dividing the wide band channel into narrowerflat faded subchannels. In OFDM, the user is free to transmit on all the available subcarriers.Therefore, only one source-destination link can be realized in a specific frequency band andtime slot. The multiple access variant of OFDM on the other hand, OFDMA, allows formultiple simultaneous source-destination links to be realized by limiting the users to occupynon-overlapping subsets of available subcarriers. Analyzing the outage event in OFDM andOFDMA relay systems imposes another challenge upon researchers.In the context of single stream OFDM cooperative communications with single or multiplerelays, most researchers assume that the event of outage occurs if one or more OFDMsubcarriers are in outage [62–64]. This assumption is the result of considering the case ofequal bit allocation (EBA) to all the OFDM subcarriers. However, this case may not capturethe general scenario where the nodes are free to allocate arbitrary number of bits to differentsubcarriers in the modern wireless technologies. For instance, if a subset of subcarriers isenjoying good channel gains, more bits with the same level of power can be assigned to themso that they compensate for other subcarriers which are in deep fade. This motivates us toconsider the general case of arbitrary number of bit allocation to OFDM subcarriers in thelink outage analysis.151.4. Scope, motivations, and objectivesMoreover, most of the analyses evaluating the outage performance rely on the assumptionthat the subcarrier gains are independent and identically distributed (i.i.d) random variables(RVs) [62–65]. It is well known that OFDM subcarrier gains in frequency domain are corre-lated. This motivates us to consider the correlation between the OFDM subcarrier gains inthe link outage analysis.The problem of analyzing the outage behavior of OFDM cooperative networks becomesmore challenging when simultaneous streams are allowed to coexist. Two scenarios arepossible in the case of multi-stream networks. The first case is when multiple users arecommunicating through a single relay to the destination using OFDMA, and the second caseis when multiple relays exist in the network as well as multiple sources. In both of thesemulti-stream cases, the link outage behavior does not capture the global outage behavior ofthe network. Therefore, the global outage probability needs to be defined in some sense andevaluated.Regarding the OFDMA multi-user single-relay case, the simultaneous links are also sta-tistically correlated. This is because all the streams are sharing the channel between therelay and destination. Although these simultaneous streams are realized on disjoint subsetsof OFDM subcarriers, the OFDM subcarriers on the common relay-destination channel arecorrelated with each other. Therefore, on the common relay-destination channel, there isa statistical correlation not only between the subcarriers in each subset, but also amongsubcarriers in different subsets. This causes the simultaneous links realized on these OFDMsubcarriers to be correlated. This also makes the global outage analysis more complex. Tothe best of our knowledge, this correlation has not been detected and addressed in the litera-ture; thus, there is motivation to consider this correlation in the outage analysis of OFDMArelay-based networks with single relay and multiple users.In the case of multiple users and multiple relays, assigning relays to individual source-destination pairs becomes crucial, as well. Regarding the multi-stream scenarios, an immenseamount of research exists on uplink and downlink of cellular systems in which multiple nodesare communicating with a single BS. For instance, in [66], cellular multi-user cooperativenetworks under OFDM modulation are addressed, where a circular cell is divided into equalarea sectors, and one relay serves all the nodes in a each sector. The outage probability of thissystem is also analyzed and used as the performance metric. Compared to cellular systems,non-cellular systems, e.g., ad hoc and mesh topologies, in which simultaneous streams canco-exist among multiple sources and destinations are less explored.The above shortcomings in the literature motivates us to pursue the following objectivesin the context of outage analysis and relay allocation in DF OFDM and OFDMA relay-basedcommunication with Rayleigh frequency selective channels:161.5. Thesis outline1. Analyzing the outage behavior of a three-node DF OFDM cooperative model allowingfor arbitrary number of bits on OFDM subcarriers and correlated OFDM subcarriers.2. Defining the global outage probability in the case of multi-stream DF OFDMA relay-based communication.3. Taking into account the correlation between simultaneous streams in the global outageanalysis in the case of multi-stream single-relay DF OFDMA cooperative model.4. Evaluating the global outage probability and using it as an objective to be optimizedthrough relay allocation to source-destination streams in the case of multi-user multi-relay DF OFDMA cooperative model.The first objective is tackled in Chapter 4. The second and third objectives are addressedin Chapter 5, and the last objective is the topic of Chapter 6. The contributions maderegarding these objectives are clarified in the beginning of each chapter.1.5 Thesis outlineThe rest of this thesis is organized as follows:• Chapter 2 addresses the cell association problem in the downlink of a multi-tier HetNetin which BSs have finite number of RBs available to distribute among their associatedusers. Two problems are defined and treated in Chapter 2: Sum utility of long termrate maximization with long term rate QoS constraints, and global outage probabilityminimization with outage QoS constraints. The first problem is well-suited for lowmobility environments, while the second problem provides a framework to deal withenvironments with fast fading. The defined optimization problems in Chapter 2 aresolved in two phases: Cell association phase followed by the optional RB distributionphase. We show that the cell association phase of both problems have the same struc-ture. Based on this similarity, we propose a unified distributed algorithm with lowlevels of message passing for the cell association phase. This distributed algorithm isderived by relaxing the association constraints and using Lagrange dual decompositionmethod. In the RB distribution phase, the remaining RBs after the cell associationphase are distributed among the users. Simulation results show the superiority of ourdistributed cell association scheme compared to schemes that are based on maximumSINR.171.5. Thesis outline• Chapter 3 addresses the joint downlink and uplink aware cell association problem in amulti-tier HetNet in which BSs have finite number of RBs to distribute among the users.An optimization problem is defined to maximize the sum of weighted utility of longterm data rate in downlink and uplink through cell association and RB distribution,while maintaining QoS. Separate outage QoS constraints are considered for downlinkand uplink of a user. Using outage QoS constraints renders the problem suitable forfast fading environments. We propose a distributed scheme for the cell associationproblem. As users cannot measure the uplink attributes by listening to the referencesignals of BSs, a limited amount of feedback is added to the reference signals of BSs toinform the users of the uplink interference and make the distributed algorithm designpossible. Moreover, by assigning different weights to the downlink and uplink datarates, the proposed scheme can be only downlink oriented, only uplink oriented, orboth downlink and uplink aware. Comparing the proposed scheme with the downlinkoriented SINR scheme, significant uplink rate gains are observed. This is while thegains in downlink rates are also considerable. In the end, the remaining RBs after thecell association phase are distributed among users separately in downlink and uplinkto further improve the rate.It also should be mentioned that Chapter 3 is an extension to Chapter 2, in which uplinkis considered as well as downlink. Therefore, the downlink cell association problemsdefined in Chapter 2 can be developed by shutting down the uplink in Chapter 3 andapplying necessary modifications in the objective functions and the QoS constraints.However, since Chapter 2 is dedicated to cell association in downlink, more in depthremarks and simulations on the behavior of the downlink problems are provided. Onthe other hand, the remarks and simulation results in Chapter 3 are towards therelationship between downlink and uplink.• In Chapter 4, we investigate a DF two-hop relaying system consisting of one source,one relay and one destination, in which OFDM is used. We present an outage prob-ability analysis based on approximating the probability distribution function of thetotal capacity by a Gaussian distribution. Tight approximations on the outage proba-bility assuming correlated OFDM subchannels and arbitrary number of bits on OFDMsubcarriers are found. As a special case, i.i.d. OFDM subchannels are also addressed,where a closed form solution to the variance of the total capacity is obtained, leadingus to even tighter approximations on the outage probability.• In Chapter 5, we study a multi-user single-relay DF OFDMA system, where the channel181.5. Thesis outlinemodel is Rayleigh frequency selective. We provide analytical approximations for theglobal outage probability in the sense that the outage event occurs when at leastone link goes into outage. The main contribution of Chapter 5 is the considerationof the statistical correlation between the link capacities which is created by the relay-destination channel that is common to all the links. The analysis is carried out by fittingthe multi-variate normal distribution to the joint probability distribution function ofthe link capacities.• In Chapter 6, we study a clustered two-hop DF network consisting of a set of source-destination pairs, and a cluster of relays. We consider the case in which channelsare Rayleigh frequency selective, OFDMA is employed, and there is no line of sight(LOS) between source and destination clusters. Approximating the capacity of a singlesource-relay-destination link by a Gaussian RV, the global outage probability of thisnetwork is characterized allowing for correlated OFDM subcarrier gains and arbitrarynumber of bits on each subcarrier. The obtained global probability of outage is usedas an objective function to formulate an optimization problem to allocate relays tosource-destination pairs. The outage probability minimization problem through relayallocation then is converted to a standard assignment problem for which a low com-plexity algorithm based on Hungarian method is proposed. The numerical results showthe precision and effectiveness of our analysis and proposed relay allocation technique.• Conclusions and possible future research directions are discussed in Chapter 7.19Chapter 2Unified and Distributed QoS-DrivenCell Association Algorithms inHetNetsThe accomplished works and research contributions in this chapter are briefly described inthe following.This chapter addresses the cell association problem in the downlink of a multi-tier Het-Net. It is assumed that BSs have finite number of RBs available to distribute among theirassociated users. We investigate distributed algorithms where users and BSs decide basedon their local measurements of the wireless environment. We also focus on providing QoSin terms of minimum achievable long term rate or maximum outage probability.Two problems are defined and treated in this chapter: Sum utility of long term rate max-imization with long term rate QoS constraints, and global outage probability minimizationwith outage QoS constraints. The first problem is well-suited for low mobility environments,and the second problem provides a framework to deal with environments with fast fading.In defining the optimization problems in this chapter, we consider a general scenario whereunity frequency reuse factor and no interference coordination schemes are assumed. Bothproblems are to be optimized through cell and RB association.The defined optimization problems in this chapter are solved in two phases: Cell associa-tion phase followed by the optional RB distribution phase. We show that the cell associationphase for both problems have the same structure. Based on this similar structure, we designand propose a unified distributed algorithm with low levels of message passing and complex-ity for the cell association phase. The distributed cell association algorithm is derived byrelaxing the association constraints and using Lagrange dual decomposition method. Ourdistributed cell association algorithm is QoS-driven since users receive only enough numberof RBs to satisfy their QoS constraints while maximizing the sum utility of rate or mini-mizing the global outage probability. Extensive simulation results that are brought in thischapter show that our distributed cell association scheme outperforms the maximum SINRscheme. For instance, rate gains of up to 2.4x have been observed in the simulations for the202.1. System modelcell edge users in our distributed cell association algorithm over maximum SINR scheme.In the RB distribution phase, the remaining RBs after the cell association phase aredistributed among the users for further improvement of the network performance. However,the RB distribution phase is kept optional since once the users can satisfy their QoS require-ments, expending more resources seems unnecessary. In addition, giving users resourcesbeyond their QoS requirements calls for spending more power which is not appealing fromenergy saving perspectives. We show that the RB distribution phase for the rate problemis a convex program. In fact, RB distribution to maximize the rate has a similar struc-ture to that of the well-known water-filling problem. Therefore, the closed form solution ofthis problem is obtained by writing the Karush-Kuhn-Tucker (KKT) conditions. However,distributing the remaining RBs for the outage problem is a complex non-convex non-linearproblem. Therefore, we propose a sub-optimal greedy algorithm to allocate the remainingRBs to minimize the global outage probability.Before proceeding further into this chapter, it should be pointed out that in the nextchapter, a more general case of downlink and uplink cell association in HetNets is consid-ered. Therefore, defined problems in this chapter can be considered as special case of thegeneral problem in Chapter 3 with different objective functions and QoS constraints. Nev-ertheless, as this chapter is dedicated to downlink, the remarks and simulation results go indepth regarding the behavior of HetNets in downlink, while in Chapter 3, the remarks andsimulation results are more towards realizing the differences in downlink and uplink.The rest of the chapter is organized as follows: In the next section, the chosen systemmodel is described. The cell association problem with QoS constraints is formulated inSection 2.2. Our distributed solution to the cell association problem is presented in Section2.3. Section 2.4 will address distributing the remaining RBs after the cell association phase.In Section 2.5, we examine the performance of our proposed algorithms through numericalsimulations.2.1 System modelThe focus of this chapter is on a downlink HetNet consisting of multiple tiers of BSs, wheredifferent tiers represent different types of BSs. As an example, tier 1 BSs can be macro BSswith high transmit power and large coverage areas. Tier 2 BSs (pico BSs) are regarded assmaller BSs with lower powers compared to tier 1 BSs, but with higher deployment density.Finally, tier 3 BSs (femto BSs) model indoor APs with very small transmit powers.The set of all BSs is denoted by B = {1, . . . , NB}, and the set of all users is denoted by212.1. System modelTable 2.1: List of key parameters in Chapter 2U Set of usersB Set of BSsi User i ∈ Uj BS j ∈ BNj Resource budget of BS jnij # of RBs given to user i by BS jPj Transmitting power of BS jHij = GijFij Channel power gain between user i and BS jGij Large scale component of HijFij Small scale component of Hijλij = 1Gij Exponential parameter of HijSINRij Instantaneous SINR at user i from BS jSINRij Long term SINR at user i from BS jcij Instantaneous RB capacity at user i from BS jc¯ij Long term RB capacity at user i from BS jrij Instantaneous rate at user i from BS jr¯ij Long term rate at user i from BS jP outij Probability of outage when user i is served by BS jγi Rate requirement of user iTi Outage probability requirement of user in¯Rij Minimum # of required RBs of user ifrom BS j for rate QoS constraintn¯Oij Minimum # of required RBs of user ifrom BS j for outage QoS constraint222.1. System modelU = {1, . . . , NU}. The cardinality of B is NB, and the cardinality of U is NU . Each BS j ∈ Bhas a fixed power of Pj W available. All the BSs are assumed to be connected by a high speedbackhaul through which information exchange with negligible delay is possible. In order tofollow RB-based structure of resources in recent standard such as LTE and LTE-Advanced,we asssume that each BS j ∈ B has access to Nj RBs to distribute among its associatedusers. The resource budget of BS j in terms of Nj depends on the available bandwidth andscheduling interval at BS j.2.1.1 The channel model, instantaneous rate, long term rate andoutage probabilityWe denote the positive channel power gain between user i and BSs j by Hij, i.e., the receivedpower at user i from BS j is HijPj. Furthermore, Hij embodies the effects of path loss, lognormal shadowing and antenna gains as large scale fading component (denoted by Gij), andmulti-path Rayleigh fading as small scale fading component (denoted by Fij). By adoptingthese notations we haveHij = GijFij, ∀(i, j) ∈ U × B, (2.1)where (·) × (·) denotes the Cartesian product. The large scale fading component Gij is as-sumed to be constant during one association period, while the small scale fading componentFij fluctuates fast enough so that a mobile user can average it out in its channel measure-ments. Fijs are modelled by statistically independent exponentially distributed RVs withunit variance. They are exponentially distributed since in Rayleigh fading, the envelope ofthe signal is assumed to follow a Rayleigh distribution, and in turn the channel power isexponentially distributed [67]. Fijs are statistically independent random variables since theymodel geographically separated wireless channels which show independent multi-path fadingbehaviours. Based on these assumptions, Hijs are statistically independent exponentiallydistributed random variables with parameter λij, whereλij =1E[Hij]=1Gij, (2.2)where E[·] denotes the expected value. As it is mentioned before, user i can measure Gij(and equivalently λij) for all the BSs j ∈ B.232.1. System modelIn such a setting, the instantaneous SINR seen by user i ∈ U from BS j ∈ B isSINRij =PjHij∑k∈B\{j} PkHik + ∆fN0, (2.3)and the long term SINR that is measured by user i ∈ U from BS j ∈ B [45, 47, 48] isSINRij =PjGij∑k∈B\{j} PkGik + ∆fN0. (2.4)In equations (2.3) and (2.4), the constant ∆f denotes the bandwidth over which an RB isrealized, N0 denotes the thermal noise spectral power, and B\{j} is the set of all BSs exceptBS j.Accordingly, the instantaneous and long term spectral efficiency at user i, if it is servedby BS j, denoted by cij and c¯ij, respectively, can be written ascij = log2(1 + SINRij), (2.5)c¯ij = log2(1 + SINRij). (2.6)Without loss of generality, cij and c¯ij can be regarded as achievable rate and long termachievable rate on an RB. For example, if cij is multiplied by the RB bandwidth and timeduration and divided by the scheduling interval, it will be the achievable rate on one RB.Given that nij RBs are given to user i by BS j, the instantaneous and long term datarates seen by user i arerij = nijcij, (2.7)r¯ij = nij c¯ij. (2.8)The above equations are valid if we assume flat fading on the bandwidth of BSs from users’point of view. The flat fading assumption is made to preserve simplicity in the system model.The study of the frequency selective scenario in which users see different channel gains ondifferent RBs (and in turn, different SINR levels and capacities on different RBs) is left forfuture work.We define the outage event of a single user i served by BS j to be the event wherethe instantaneous rate seen by user i drops below a certain threshold γi. We denote the242.1. System modelprobability of this event by P outij and formally define it asP outij = Pr{rij < γi} = Pr{nij log2(1 +PjHij∑k∈B\{j} PkHik + ∆fN0)≤ γi}, (2.9)where Pr{·} denotes the probability of the input argument. This probability of outage isderived in [68, 69] (an easy to read proof is available in [68]), which isP outij = 1−(e−λij∆fN0PjΓij) ∏k∈B\{j}(λikPkλijPjΓij +λikPk), (2.10)whereΓij = 2γinij − 1. (2.11)Note that P outij is measurable by user i since users can measure λij for all the BSs j ∈ B .Moreover, It can easily be verified that P outij is a strictly decreasing function of nij, i.e., moreRBs improves the outage behaviour.2.1.2 Rate and outage QoS constraintsIn this chapter, we define two QoS constraints, namely, long term rate QoS and outageQoS constraints. We refer to the long term QoS constraint simply as rate QoS constrainthereafter. In the case of rate QoS constraint, each user intends to keep its long term rateabove its requested rate threshold. In the beginning phase of cell association, each user irequests a certain rate QoS class in terms of minimum required long term rate γi. Therefore,if user i is associated with BS j, it is the duty of the BS to satisfy the following rate QoSconstraintr¯ij ≥ γi. (2.12)By substituting (2.8) in the above equation, we havenij ≥γic¯ij. (2.13)252.2. Problem formulationWe indicate the smallest integer greater than the right hand side of the above equation byn¯Rij as followsn¯Rij = dγic¯ije, (2.14)where d·e represents the ceiling function. Inequalities (2.12) and (2.13) and equality (2.14)indicate that if user i requires rate QoS class of minimum rate γi, BS j will be obliged toallocate at least n¯Rij RBs to that user, i.e.,nij ≥ n¯Rij. (2.15)In the case of outage QoS constraint, each user intends to keep its instantaneous rateabove its requested rate threshold with a certain probability. In the beginning of cell associ-ation phase, each user requests a certain outage QoS class. An outage QoS class is defined interms of user’s rate threshold γi, and probability of user’s rate dropping below that thresholdTi. Therefore, if user i is associated with BS j, it is the duty of BS j to satisfy the followingconstraint for that userP outij = Pr{rij ≤ γi} ≤ Ti. (2.16)The probability of outage is given in (2.10) as a function of nij. Since this probability isa strictly decreasing function of nij, a lower bound on nij exists above which the outageQoS constraint is satisfied. Since nijs can take only positive integer values, this lower boundcan easily be found numerically by setting nij = 1 in (2.10) and incrementing it until theconstraint is satisfied. We indicate the smallest integer for which (2.16) is satisfied by n¯Oij.Therefore, if user i requires outage QoS class of rate threshold γi and probability of outageTi, BS j will be obliged to allocate at least n¯Oij RBs to that user, i.e.,nij ≥ n¯Oij. (2.17)The key parameters that are used in this chapter are listed in Table 2.1.2.2 Problem formulationTwo optimization problems are considered in this chapter: Sum utility of long term ratemaximization with rate QoS constraints (referred to as P1), and global outage probabilityminimization with outage QoS constraints (referred to as P2), both through cell association262.2. Problem formulationand RB allocation. We formulate these two problems in the rest of this section. Beforeproceeding further, we define binary association indices xij ∈ {0, 1}, ∀(i, j) ∈ U × B, wherexij = 1 indicates that user i is associated with BS j, and xij = 0 indicates the opposite.2.2.1 Sum utility of long term rate maximization with rate QoSconstraintsIn this problem, the objective is to maximize a function of long term rate while satisfyingthe rate QoS constraints. Since we are working with the notion of long term rate, thisframework is well-suited for environments with users with low mobility so that the channelsremain unchanged in one resource allocation period. We select the sum utility of users’ longterm rate to be our objective function. Utility of rate can be regarded as a measure of user’ssatisfaction with the rate it gets. A utility function, in general, is a strictly increasing andconcave function. For instance, logarithm function is a suitable candidate. However, in orderto preserve generality, the notion of U(·) is used as a general strictly increasing and concaveutility function. The sum utility of long term rate maximization problem with rate QoSprovisioning (P1) isP1 : maximizex,n∑i∈U∑i∈BxijU(r¯ij) (2.18)subject to (RC) :∑i∈Uxijnij ≤ Nj, ∀j ∈ B(AC) :∑j∈Bxij ≤ 1, ∀i ∈ U∑j∈Bxij r¯ij ≥ γi, ∀i ∈ U (2.19)xij ∈ {0, 1}, ∀(i, j) ∈ U × B (2.20)nij ∈ {0, 1, . . . , Nj}, ∀(i, j) ∈ U × B. (2.21)In the above optimization problem, x and n are matrices containing xij and nij elements.Furthermore, the first constraint is referred to as the resource constraint (RC). This con-straint ensures that the number of RBs given to the associated users does not exceed theresource budget of that BS. The second constraint is referred to as association constraint(AC). This constraint guarantees that each user is connected to at most one BS. The thirdconstraint (2.19) is the rate QoS constraint which is derived based on inequality (2.12). Inthe end, constraints (2.20) and (2.21) indicate that the association indices are binary vari-ables, and nijs can take integer values between zero and the maximum number of RBs at272.2. Problem formulationBS j.2.2.2 Global outage probability minimization with outage QoSconstraintsThe motivation behind formulating this problem is to take into account the stochastic be-haviour of wireless channels without adding signalling overhead to the system. Guaranteeinga constant instantaneous rate to users in wireless environments that suffer from fast fading isnot achievable. However, it is possible to guarantee a certain rate with a certain probability,which suggests formulating the problem in the context of outage probability. In the contextof outage probability, the eventual goal is to associate the users with BSs and RBs such thatthe global outage probability is minimized. In order to achieve this goal, the first step is todefine the global outage probability in some sense and evaluate it as a function of systemmodel parameters. We define the global outage event as the event where one or more usersexperience outage, i.e., if at least one user experiences an instantaneous data rate below itsrequested threshold, a global outage will be declared. The outage probability of a singlelink is given in (2.10). Considering that the outage events for different users are statisti-cally independent, it can be argued that the probability of no users experiencing outage is∏i∈U∏j∈B(1− P outij)xij . Therefore, the global outage probability indicated by P̂out isP̂out = 1−∏i∈U∏j∈B(1− P outij)xij . (2.22)Now, we define the global outage probability minimization problem with outage QoS provi-sioning (P2) asP2 : minimizex,n1−∏i∈U∏j∈B(1− P outij)xij (2.23)subject to (RC), (AC), (2.20), (2.21),∏j∈BPr{nijcij ≤ γi}xij ≤ Ti, ∀i ∈ U . (2.24)Comparing the constraints in P2 and P1, the only different constraint is the QoS constraint;in P2 the outage QoS constraint has replaced the rate QoS constraint in P1 for each user.Constraint (2.24) is derived based on inequality (2.16).282.3. Cell association phase2.3 Cell association phaseOptimization problems P1 and P2 are combinatorial problems in x and n which are involvedto solve. In order to make the problem tractable, we solve them in two steps. First, we fixnijs and find association indices xijs. This step is equivalent to solving the associationproblem. In the next step, given the association indices, we solve the optimization problemwith respect to nijs. In this section, we address the association problem, while optimizingwith respect to nijs is addressed in the next section. It should be noted that nijs can not befixed at arbitrary values since the QoS constraints need to be satisfied in the cell associationphase. Therefore, we replace the rate QoS constraints in P1 by nij = n¯Rij, and outage QoSconstraints in P2 by nij = n¯Oij, for all (i, j) ∈ U × B. According to inequalities (2.15) and(2.17), n¯Rij and n¯Oij are the minimum number of RBs required by user i from BS j to satisfythe rate QoS and outage QoS constraints, respectively.From another perspective, if we replace nijs by constant 1 in (RC), it can be shownthat both problems become a two dimensional assignment problem with respect to xijs, andalgorithms such as Hungarian method solves them efficiently [70] in a centralized fashion.However, optimizing over xijs is an NP-hard problem because of the (RC) constraint [71]. Inorder to change the combinatorial nature of the problem into a continuous one, and hopefullya convex program, we relax the constraints (2.20) in both optimization problems, i.e., wereplace constraints (2.20) by 0 ≤ xij ≤ 1 for all (i, j) ∈ U × B.Next, we show that by fixing nijs, problems P1 and P2 become equivalent optimizationproblems. After the aforementioned modifications, problem P1 transforms into problemP1x as followsP1x : maximizex∑i∈U∑j∈BxijaRij (2.25)subject to (RC), (AC),nij = n¯Rij, ∀(i, j) ∈ U × B, (2.26)0 ≤ xij ≤ 1, ∀(i, j) ∈ U × B, (2.27)whereaRij = U(r¯ij) = U(n¯Rij c¯ij).aRij is treated as a constant since n¯Rij is a constant.It seems that the objective function in P2 has a different structure compared to the ob-jective function in P1. However, applying the following changes unifies these two objectivefunctions. Inspecting the objective function (2.23), it can be seen that the first term is a con-292.3. Cell association phasestant and can be removed. Moreover, removing the negative sign changes the minimizationto a maximization problem. Finally, taking the natural logarithm of the objective functiondoes not change the optimum argument and transforms multiplication to addition. Afterthese modifications, problem P2 transforms into problem P2x as followsP2x : maximizex∑i∈U∑j∈BxijaOij (2.28)subject to (RC), (AC),nij = n¯Oij, ∀(i, j) ∈ U × B, (2.29)0 ≤ xij ≤ 1, ∀(i, j) ∈ U × B, (2.30)whereaOij = log(1− P outij).aOij is also treated as a constant since Poutij is a function of nij which is set to n¯Oij.By comparing P1x and P2x, it is trivial that these two optimization problems have thesame structure. Therefore, we remove the superscripts R and O from aRij, aOij, n¯Rij, and n¯Oijand replace them by aij and n¯ij to have the unified optimization problem Px as followsPx : maximizex∑i∈U∑j∈Bxijaij (2.31)subject to∑i∈Uxijn¯ij ≤ Nj, ∀j ∈ B, (2.32)∑j∈Bxij ≤ 1, ∀i ∈ U , (2.33)0 ≤ xij ≤ 1, ∀(i, j) ∈ U × B. (2.34)The objective function of Px is a linear function in xijs, and all the constraints are linearand affine in xijs. Therefore, Px is a convex optimization problem with respect to xijs [72].2.3.1 Cell association solutionIn order to devise a distributed solution to Px, we use a similar approach to the one suggestedin [47], that is employing the Lagrange dual decomposition method [73]. Note that the strongduality property holds for Px, that is the optimum value of Px is equal to the optimumvalue of its Lagrange dual function. According to Slater’s theorem, strong duality holds fora convex optimization problem if Slater’s condition holds for the constraints of that problem.Moreover, if the problem is convex and all the equality and inequality constraints are linear302.3. Cell association phaseand affine, Slater’s condition reduces to feasibility condition [72]. As discussed in the previoussubsection, Px is a convex optimization problem with linear and affine constraints. Therefore,if a set of xijs exists for which Px is feasible, then the strong duality holds. For instance,xij = 0, for all (i, j) ∈ U × B is always a feasible point in Px, thus, strong duality alwaysholds for Px.We define the Lagrangian of Px by taking the resource constraint (2.32) inside the ob-jective function and indicate it by L(x, µ). The Lagrangian of Px isL(x, µ) =∑i∈U∑j∈Bxijaij −∑j∈Bµj(∑i∈Uxijn¯ij −Nj), (2.35)where µjs are Lagrange multipliers associated with resource constraints at BSs. Then, theLagrange dual function represented by g(µ) isg(µ) = supx∑i∈U∑j∈Bxij(aij − µjn¯ij) +∑j∈BµjNj (2.36)subject to 0 ≤ xij ≤ 1, ∀(i, j) ∈ U × B, (2.37)∑j∈Bxij ≤ 1, ∀i ∈ U . (2.38)The strong duality holds, therefore, we can first maximize over x and then minimize over µ.In order to find g(µ) for fixed µjs, we rewrite the Lagrange dual function asg(µ) =∑i∈Ugi(µ) +∑j∈BµjNj, (2.39)where gi(µ) is defined for all i ∈ U asgi(µ) = supxij ,j∈B∑j∈Bxij(aij − µjn¯ij) (2.40)subject to 0 ≤ xij ≤ 1, j ∈ B∑j∈Bxij ≤ 1.It can be seen that for fixed µjs, g(µ) is separable with respect to users i as in (2.40).Therefore, each user i needs to solve the optimization problem (2.40). For a given user i,the objective function in (2.40) is a weighted average of (aij − µjn¯ij), where the weights arebetween 0 and 1 and they sum up to unity. Therefore, (2.40)’s unique solution is yielded bykeeping the maximum argument of (aij − µjn¯ij) over js and diminishing the contribution of312.3. Cell association phaseother elements. We call the term (aij − µjn¯ij) the qualification index of BS j from user’s ipoint of view and indicate it by QIij as followsQIij = aij − µjn¯ij. (2.41)Accordingly, (2.40)’s unique solution for each user i isxij =1 if j = j∗0 if j 6= j∗, ∀i ∈ U , (2.42)wherej∗ = argmaxj∈B(QIij), ∀i ∈ U . (2.43)After finding xijs for fixed µjs, we update the vector µ by using gradient descent method[72]. The partial derivative of the Lagrange dual function with respect to µj is∂L(x, µ)∂µj= Nj −∑i∈Uxijn¯ij, ∀j ∈ B. (2.44)Therefore, the updating rule for µ isµj(t+ 1) =[µj(t)− β(t)(Nj −∑i∈Uxijn¯ij)]+,∀j ∈ B, (2.45)where the operator [·]+ indicates the maximum of the argument of the operator and 0. Weapplied the operator [·]+ on µjs because the Lagrange multipliers are non-negative parameters[72]. Furthermore, β(t) is some step size that satisfies the following two conditionslimt→∞β(t) = 0 , and∞∑t=1β(t) =∞. (2.46)According to proposition 6.3.4 in [74], if the step size β(t) satisfies the above conditions, theconvergence of the gradient descent method will be guaranteed assuming that the associationindices are continuous variables of the form 0 ≤ xij ≤ 1. These conditions do not guaranteethe convergence for the binary association indices. However, we have used β(t) = 0.5/t in oursimulations, and in all cases the distributed algorithm converged in less than 25 iterations;most of the times the convergence was reached in less than 10 iterations.322.3. Cell association phaseWe iteratively update the association variables according to (2.42), and the Lagrangemultipliers according to (2.45), until the convergence is reached. Note that updating rulefor the association variables automatically generates binary values. Consequently, no furtherapproximations is required.2.3.2 Feasibility problem and admission controlIn the cell association procedure described in the previous subsection, the users find theirdesired BS through (2.43). The users are not aware of how many other users are associat-ing themselves with the desired BS and how much resources that BS has access to. As aresult, many users may associate themselves with a BS and exhaust its resources, leading toviolating the resource constraint (2.32). This condition not only affects the convergence ofthe algorithm, but also takes the solution out of the feasible set. As it is described in [72],the Lagrange dual function is an upper bound on the original maximization problem only ifwe are in the feasible set of the problem defined by the constraints. Beyond the feasible set,not only the Lagrange dual function may not be an upper bound on the original problem,but also iterating with gradient descent method may divert the solution from the desiredoptimal point. Therefore, once an iteration is out of the feasible set, it needs to be projectedback to the feasible set, i.e., gradient projection method [75] should be used.In the context of cell association in HetNets, we use a heuristic to project the iterationback to the feasible set once one or more BSs receive association requests from too manyusers. First, we require all the users i ∈ U to sort the BSs in their range in descending orderbased on their qualification index QIij given in (2.41), and send this sorted list to the BS theywant to connect to (BS j∗ in (2.43)). Let us say BS j receives too many association requests,i.e., upon acceptance of all those requests the resource constraint at BS j is violated. Then,BS j finds the users who are consuming the highest number of RBs (highest number of n¯ij),and removes them until its resource constraint is satisfied. BS j sends those removed users’requests to the second best BSs the users have requested. If the resource constraints aresatisfied at all BSs now, the projection is accomplished. Otherwise, this procedure continuesuntil the solution is back to the feasible set. As we have mentioned before, it is assumedthat BSs are connected through a high speed back-haul, and the message passing requiredfor projecting the solution back to the feasible set takes place in negligible time period.Moreover, the admission control described here achieves load balancing in the network sinceit avoids over populating the BSs.332.4. RB distribution phase2.3.3 Distributed cell association protocol designThe proposed distributed algorithm of cell association described in previous sections is sum-marized here:Step 1: Initialization Each BSs j ∈ B initializes its associated Lagrange multiplier µjand broadcasts it in the network.Step 2: User request In this step, all users i ∈ U listen to the pilot signals broadcastedby BSs and measure the SINR from each BS and channel gains between themselves and allthe BSs. Based on these measurements and the desired QoS, user i calculates the numberof RBs it needs from each BS. Then, user i calculates the QIij in equation (2.41) for all theBSs in its range and sorts the BSs in descending order. A request containing this sorted listalong with the required number of RBs from the BSs in the list is sent to the BS with thebest QIij.Step3: User admission BSs process the requests they have received. If BS j canaccommodate all the requests it has received, an admission message is sent to all thosethat find BS j to be the best candidate. Otherwise, BS j forwards the requests from usersconsuming the highest amount of resources to the next best BS the users have requested.This procedure continues until the solution is feasible.Step 4: BS Lagrange multiplier update After all the users are accommodated, BSsupdate their Lagrange multipliers according to (2.45) and broadcast the new multipliers.The algorithm continues by going back to step 2.This algorithm solves the cell association problem in a distributed fashion for eitherof the rate maximization with rate QoS constraints problem, or global outage probabilityminimization with outage QoS constraints problem (P1x or P2x).2.4 RB distribution phaseAfter the cell association phase is completed, some of the BSs may have extra RBs notallocated to any users. In this section, in order to allocate the remaining RBs, given theassociation indices xijs, we solve the optimization problems P1 and P2 for nijs. Beforeaddressing either of P1 and P2, we define Uj as the set of users associated with BS jUj = {i|xij = 1},∀j ∈ B. (2.47)342.4. RB distribution phase2.4.1 Sum utility of rate maximizationAssuming fixed xijs, problem P1 is reduced to the following optimization problem at eachBS jP1n,j : maximizen′ij ,i∈Uj∑i∈UjU(nij c¯ij) (2.48)subject to∑i∈Ujnij = Nj, (2.49)nij = n¯Rij + n′ij, ∀i ∈ Uj, (2.50)where n¯Rij is the number of already allocated RBs to user i by BS j satisfying the rate QoSconstraint of user i, and n′ij is the share of user i from the remaining RBs available at BS j.Moreover, It is implicitly assumed that n′ijs are integer values that satisfy n¯ij ≤ n′ij ≤ Nj. Ifwe assume that n′ij are continuous variables, it can be shown that problem P1n,j is a convexoptimization problem with strong duality property. In fact, P1n,j has a similar structure tothat of the water-filling problem [72]. Therefore, we solve P1n,j using KKT conditions [72].Introducing the Lagrange multiplier ν for the resource constraint (2.49), the solution isn′ij =[1c¯ij(U′)−1( νc¯ij)− n¯Rij]+, ∀i ∈ Uj, (2.51)where ν is the unique solution of the following equation∑i∈Ujmax{1c¯ij(U′)−1( νc¯ij,), n¯Rij}= Nj. (2.52)In addition, (U ′)−1(·) is the inverse of the derivative of U(·) with respect to nij. The solutionof the above equation is unique since U(·) is a concave and strictly increasing function,hence, (U′)−1(·) is a strictly increasing (monotonic) function of ν. This equation can besolved efficiently through a numerical search method. In the end, the optimal solution ofthe P1n,j is rounded to the closest integer value since the procedure described here does notnecessarily produce integer values for nijs.2.4.2 Global outage probability minimizationAssuming fixed xijs, removing the constant 1 in the objective function of P2, flipping thenegative sign to positive sign, and taking the logarithm of the remaining term, P2 reduces352.5. Numerical simulation resultsto the following optimization problem at each BS jP2n,j : maximizen′ij ,i∈Uj∑i∈Ujlog(1− P outij)(2.53)subject to∑i∈Ujnij = Nj, (2.54)nij = n¯Oij + n′ij, ∀i ∈ Uj, (2.55)where n¯Oij is the number of already allocated RBs to user i by BS j satisfying the outageQoS constraint of user i, and n′ij is the share of user i from the remaining RBs available atBS j. The optimization problem P2n,j is a non-convex problem, and finding the closed formsolution to it is involved. However, it can be shown that the objective function in P2n,j isstrictly increasing in nijs. In other words, increasing each of nijs or a subset of nijs increasesthe objective function. As this problem is a monotonic combinatorial optimization problem,applying a greedy algorithm is a natural approach to solving it [76]. We propose a greedyalgorithm where in each iteration one RB is given to the user that benefits the most in termsof the outage probability (the user that has the highest decrement in P outij given in (2.10))until the RBs at BS j are exhausted. At BS j, given that there are Kj = (Nj −∑i∈Ujn¯Oij)RBs left, the algorithm terminates in Kj iterations.2.5 Numerical simulation resultsIn this section, we evaluate the performance of our distributed cell association algorithmand the effects of distributing the remaining RBs through numerical simulations. Threetiers of BSs are considered to exist in the HetNet. The transmitting powers of macro, picoand femto BSs are set to 46, 35 and 20 dBm, respectively. The macro BSs’ locations areassumed to be fixed and for each macro BS, 5 micro BSs, 10 femto BSs, and 200 users arerandomly located in a square area of 1000 m×1000 m, unless stated otherwise. The macroBSs are fixed at the center of each square cell. Regarding the channel model, large scalepath loss and small scale Rayleigh multi-paths fading are considered. The path loss betweenthe macro or pico BSs, and the users is modelled as L(d) = 34 + 40 log10(d), and the pathloss between femto BSs and users is L(d) = 37 + 30 log10(d), where d is the distance betweenusers and BSs in meters. The small scale fading is modelled by statistically independentexponentially distributed RVs with unit variance. The noise power at all the receivers is setto −111.45 dBm, which corresponds to thermal noise at room temperature and bandwidthof 180 kHz (Bandwidth of an RB in LTE standard). The mobile users in their SINR and362.5. Numerical simulation results0 1 2 3 4 5 6 7 8 9 1000.10.20.30.40.50.60.70.80.91Rate (bits/s)Probability Max SINR, rmin=1Distributed, rmin=1Max SINR, rmin=2Distributed, rmin=2Max SINR, rmin=3Distributed, rmin=3Figure 2.1: The CDFs of users’ long term rate for the rate problem in a static settingchannel gain measurements average out the Rayleigh multi-paths fading and see the effects oflarge scale path loss, while their instantaneous rate depends on both the large scale and smallscale fading. The number of RBs available at macro, pico and femto BSs are Nmacro = 200,Npico = 100, and Nfemto = 50. Without loss of generality, the scheduling interval of 1 secondis considered in the simulations.2.5.1 Rate cumulative distribution functionsAs mentioned in [44], when it comes to HetNets, the rate distribution is a more meaningfulmetric compared to SINR or spectral efficiency distribution to compare different schemes.This is because with rate distribution metric, the effect of BS load on the data rate the usersperceive is observable, while this is not the case with SINR or spectral efficiency distributionmetrics.Fig. 2.1 shows the cumulative distribution function (CDF) of the long term rate for themaximum SINR scheme (Maximum SINR scheme is referred to as Max SINR in the rest of372.5. Numerical simulation results0 1 2 3 4 5 6 7 8 9 1000.10.20.30.40.50.60.70.80.91Rate (bits/s)Probability Max SINR, rmin=1Distributed, rmin=1Max SINR, rmin=2Distributed, rmin=2Max SINR, rmin=3Distributed, rmin=3Figure 2.2: The CDFs of users’ instantaneous rate for the rate problem in a stochastic settingthis chapter) and the distributed cell association algorithm for the rate problem in a staticsimulation environment. The simulation environment is static in the sense that Rayleighmulti-path fading is not considered, and only large scale path loss is taken into account.Fig. 2.2 shows the CDFs of instantaneous rate for the Max SINR and the distributed cellassociation algorithm for the rate problem in a stochastic setting where both large scale andsmall scale fading are taken into account. In both figures, the results for the rate thresholdof γ = 1, 2, and 3 bits/s are shown. In the case of Max SINR scheme, some of the BSs mayget overloaded when users associated with a BS require more RBs than the BS budget; thus,those users are needed to be scheduled in the next scheduling interval. The rate reductioncaused by the over-loaded BSs is taken into account in the simulations. As it can be seenin Fig. 2.1, the long term rate of the users never drops below the rate threshold in the caseof the distributed algorithm, while Max SINR algorithm is not able to satisfy the rate QoSconstraints in a static setting. Furthermore, the rate CDFs of the distributed algorithmalways lie below the corresponding CDFs resulted by employing the Max SINR algorithm,382.5. Numerical simulation results0 5 10 1500.10.20.30.40.50.60.70.80.91Rate (bits/s)Probability Max SINR, rmin=0.8Distributed, rmin=0.8Max SINR, rmin=1Distributed, rmin=1Max SINR, rmin=1.2Distributed, rmin=1.2Figure 2.3: The CDFs of users’ instantaneous rate for the outage problem and outage prob-ability of T = 10% in a stochastic settingespecially for the cell edge users (worst 10% users). The rate gain for the cell edge usersobtained by using the distributed algorithm over the Max SINR algorithm increases byincreasing the rate threshold. To be more specific, rate gains of α = 2.4, 1.6, and 1.1 areobserved for minimum thresholds of γ = 3, 2, and 1 bits/s, respectively, in a static setting.Likewise, in a stochastic setting, as it can be seen in Fig. 2.2, the rate CDFs of the distributedalgorithm always lie below the corresponding CDFs obtained by employing the Max SINRalgorithm. In this case, the rate gains for the cell edge users of α = 1.75, 1.3, and 1.08 areobserved for minimum thresholds of γ = 3, 2, and 1 bits/s. However, the instantaneous rateseen by the users can go below the rate threshold since the users’ measurements are basedon the average channel gains, while the instantaneous rate is dictated by both the averagechannel gain and the small scale Rayleigh fading. Since lower rates than the rate thresholdare also achievable, the average rates and the rate gain of the cell-edge users drop in thestochastic setting compared to the static setting.392.5. Numerical simulation results0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.911.11.21.31.41.51.61.71.8ProbabilityRate gain α Optimal, rmin=1Rounded, rmin=1Distributed, rmin=1Optimal, rmin=2Rounded, rmin=2Distributed, rmin=2Optimal, rmin=3Rounded, rmin=3Distributed, rmin=3Figure 2.4: The rate gain of the optimal linear program algorithm, the rounding algorithm,and our distributed algorithm over maximum SINR algorithm for the rate problem in astochastic settingThe CDFs of the instantaneous rate for the Max SINR and the distributed cell associationalgorithm for the outage problem is shown in Fig. 2.3. Only a stochastic setting is consideredfor the outage problem since outage probability cannot be defined in a static setting. Themaximum outage probability is set to T = 10% for all the users. By zooming in this figure,it can be seen that the outage probability for the distributed algorithm and the cases ofγ = 0.8, 1, and 1.2 bits/s is T = 7.9%, 8.4%, and 8.1%, respectively, which are less than therequired outage probability of T = 10%; thus, the outage constraints are always satisfied.This is while the Max SINR algorithm does not necessarily satisfy the outage constraints.Moreover, similar to the rate problem, the CDFs of rate resulted by the distributed algorithmalways lie below the CDFs of rate from the Max SINR algorithm. The rate gain for the celledge users is α = 1.4, 1.23, and 1.1 for minimum thresholds of γ = 1.2, 1, and 0.8 bits/s,respectively.Fig. 2.4 demonstrates the effectiveness of the distributed cell association algorithm for402.5. Numerical simulation resultsthe rate problem in a stochastic setting. The cell association problem Px introduced inSection 2.3 can be solved by three different methods. First one is solving the problemdirectly as a linear program using the simplex method [77]. This method does not necessarilyproduce binary values for the association indices, however, provides an upper bound toall the other methods. We call this method the optimal method. The second method isobtained by rounding the solution of the optimal linear program method to the closestinteger value, producing 0s and 1s for the association indices. We call this method therounding method. Finally, we have the distributed algorithm introduced in this chapter.In Fig. 2.4, the rate gain αa =ra(Probability)rMax SINR(Probability)is plotted against the probability, wherea ∈ {Optimal,Rounding,Distributed}. For instance, at probability 0.2, α of the optimalalgorithm is the ratio of the rate for which 20% of the users experience rates below thatrate when the problem is solved by the optimal algorithm, over the rate for which 20% ofthe users experience rates below that rate when the problem is solved by the Max SINRalgorithm. It can be seen that the rate gains for the optimal and rounding methods areclose, meaning that the solution of the optimal linear program is mostly composed of 0sand 1s. Also, the rate gains of the distributed algorithm is close to the rounding algorithm,which proves the effectiveness of our distributed algorithm. We have observed similar trendsfor the rate problem in a static setting, and outage problem in a stochastic setting.2.5.2 The effect of number of femto BSsThe effects of number of femto BSs per macro BS on the performance of the distributedand Max SINR algorithms are demonstrated in Figures 2.5 and 2.6. In a stochastic setting,Fig. 2.5 shows the average sum utility of instantaneous rate for the rate problem (problemP1x) and rate thresholds of γ = 1, 2, and 3 bits/s, while Fig. 2.6 shows the logarithm of theprobability of no users experiencing outage, log10(1− P̂out), for the outage problem (problemP2x) and rate thresholds of γ = 0.8, 1, and 1.2 bits/s and outage probability of T = 10%. Itcan be seen that the distributed algorithm outperforms the Max SINR algorithm in all thecases. It is also observed that the performance of the distributed algorithm slightly worsensby increasing the number of femto BSs, which is attributed to introducing more interferencein the network.Moreover, for the rate problem in Fig. 2.5, the performance of the Max SINR algorithmfirst improves as the number of femto BSs increases, which is because more resources becomeavailable per unit area and the likelihood of having overloaded BSs decreases. As the numberof femto BSs surpasses a threshold, the performance of Max SINR saturates then worsens,similar to the distributed algorithm, since the effect of more interference dominates the more412.5. Numerical simulation results5 10 15 20 250.911.11.21.31.41.5Number of femto BSsAverage sum utility of rate Distributed, rmin=1Max SINR, rmin=1Distributed, rmin=2Max SINR, rmin=2Distributed, rmin=3Max SINR, rmin=3Figure 2.5: The average sum utility of instantaneous rate against number of femto BSs forthe rate problem in a stochastic settingavailability of resources. As for the outage problem in Fig. 2.6, the performance of theMax SINR algorithm for the cases of γ = 1 and 1.2 bits/s shows a decreasing trend sincethe effect of more available RBs never dominates the interference. However, in the case ofγ = 0.8 bits/s, first the interference worsens the performance and then the availability ofmore resources boosts the performance.2.5.3 The effect of number of usersThe effects of number of users per macro BS on the performance of the distributed and MaxSINR algorithms are demonstrated in Figures 2.7 and 2.8. In a stochastic setting, Fig. 2.7shows the average sum utility of instantaneous rate for the rate problem (problem P1x) andrate thresholds of γ = 1, 2, and 3 bits/s, while Fig. 2.8 shows the logarithm of the probabilityof no users experiencing outage, log10(1− P̂out), for the outage problem (problem P2x) andthreshold rates of γ = 0.8, 1, and 1.2 bits/s and outage probability of T = 10%. It can be422.5. Numerical simulation results5 10 15 20 25−8−7.5−7−6.5Number of femto BSslog10(Probability of no users experiencing outage) Distributed, rmin=0.8Max SINR, rmin=0.8Distributed, rmin=1Max SINR, rmin=1Distributed, rmin=1.2Max SINR, rmin=1.2Figure 2.6: The probability of no users being in outage against number of femto BSs for theoutage problem and outage probability of T = 10%seen that the distributed algorithm outperforms the Max SINR algorithm in all the cases.For the rate problem, as it can be seen in Fig. 2.7, the distributed algorithm keepsthe average sum utility around a constant value, which is because of the load balancing itachieves. The distributed algorithm provides each user with only enough number of RBs tosatisfy the rate constraints. This is why the performance does not vary with the numberof users, and increases with increasing the rate threshold. As for the outage problem inFig. 2.8, log10(1− P̂out) decreases almost linearly. This trend occurs because the distributedalgorithm provides users with only enough number of RBs to keep the outage probability ofeach link slightly below the required outage probability. Besides, more users translates intomore multiplicative terms in 1 − P̂out =∏i∈U∏j∈B(1 − P outij)xij , causing the logarithm of1 − P̂out to decrease almost linearly. In an intuitive fashion, when there are more users inthe system, the likelihood of at least one user going into outage increases. Therefore, theprobability of no users experiencing outage decreases.432.5. Numerical simulation results100 110 120 130 140 150 160 170 180 190 2000.911.11.21.31.41.5Number of usersAverage sum utility of rate Distributed, rmin=1Max SINR, rmin=1Distributed, rmin=2Max SINR, rmin=2Distributed, rmin=3Max SINR, rmin=3Figure 2.7: The average sum utility of instantaneous rate against number of users for therate problem in a stochastic settingAs for the performance of the Max SINR algorithm, increasing the number of usersleads to less availability of resources and decline of the performance in both rate and outageproblems.2.5.4 The effect of distributing the remaining RBsBy far, in all our simulations we have considered only the distributed cell association algo-rithm solving the optimization problem Px. The effect of distributing the remaining RBsafter the cell association phase for the rate (solving P1n,j on top of the cell association prob-lem P1x) and outage (solving P2n,j on top of the cell association problem P2x) problemsis demonstrated in Figures 2.9 and 2.10, respectively. In Fig. 2.9, we can see the averagesum utility of instantaneous rate for the distributed algorithm solving the cell associationproblem, and the distributed algorithm with the remaining RBs, against the rate thresholdin a stochastic setting. In Fig. 2.10, we can see the logarithm of the probability of no442.5. Numerical simulation results100 110 120 130 140 150 160 170 180 190 200−8−7.5−7−6.5−6−5.5−5−4.5−4−3.5Number of userslog10(Probability of no users experiencing outage) Distributed, rmin=0.8Max SINR, rmin=0.8Distributed, rmin=1Max SINR, rmin=1Distributed, rmin=1.2Max SINR, rmin=1.2Figure 2.8: The probability of no users being in outage against number of users for theoutage problem and outage probability of T = 10%users experiencing outage for the distributed algorithm , and the distributed algorithm withthe remaining RBs, against the rate threshold and link outage probability of T = 10%. Inboth figures, the curves corresponding to 150 and 200 users per macro BS are plotted. Thefirst observation on these two figures is that the distributed algorithm with the remainingRBs significantly outperforms the results obtained through the distributed cell associationalgorithm only. Secondly, with lower number of users, the performance of the distributedalgorithm with the remaining RBs improves. This is because for a given rate threshold, thecell association algorithm first provides users with only enough number of RBs to satisfythe QoS constraints. Therefore, less users require less overall number of RBs to have theirQoS constraints satisfied, leaving more RBs unused. More unused RBs trivially translatesinto a stronger boost in the performance after distributing them among the users. Finally,by increasing the rate threshold, the performance of the distributed cell association onlyalgorithm gets close to the performance of the distributed algorithm with the remanning452.5. Numerical simulation results1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 30.911.11.21.31.41.51.61.71.8Minimum rate (bits/s)Average sum utility of rate Distributed with the rest of RBs, NU=150Distributed without the rest of RBs, NU=150Distributed with the rest of RBs, NU=200Distributed without the rest of RBs, NU=200Figure 2.9: The average sum utility of instantaneous rate against minimum rate for the rateproblem showing the effect of distributing the remaining RBs in a stochastic settingRBs. This trend is seen since more RBs are required to satisfy QoS constraints with higherrate thresholds, leaving less overall unused RBs in the network. Distributing less unusedRBs among users leads to a less improvement over distributed cell association algorithm.462.5. Numerical simulation results0.8 0.9 1 1.1 1.2 1.3−8−7−6−5−4−3−2−1Minimum rate (bits/s)log10(Probability of no users experiencing outage) Distributed with the rest of RBs, NU=150Distributed without the rest of RBs, NU=150Distributed with the rest of RBs, NU=200Distributed without the rest of RBs, NU=200Figure 2.10: The probability of no users being in outage against minimum rate for the outageproblem and outage probability of T = 10% showing the effect of distributing the remainingRBs47Chapter 3Joint Downlink and Uplink AwareCell Association in HetNets with QoSProvisioningThe accomplished works and research contributions in this chapter are briefly described inthe following.As an extension to Chapter 2, the main contribution of this chapter is considering bothuplink and downlink in the cell association problem. In this chapter, we address a jointdownlink and uplink cell association problem in a multi-tier HetNet in which BSs have finitenumber of RBs to distribute among the users in the downlink and uplink.An optimization problem is defined to maximize the sum of weighted utility of longterm data rates in downlink and uplink through cell association and RB allocation whilemaintaining QoS for the users. Separate QoS constraints are considered for downlink anduplink of a user. The QoS constraints are defined in the context of outage probability thatis keeping the instantaneous rate above a certain threshold with a certain probability. Usingoutage QoS constraints renders the cell association scheme suitable for environments withhigh mobility and fast fading.The optimization problem is broken into two phases: Cell association phase followed bydistributing the rest of RBs phase. We are interested in providing a distributed scheme to thedownlink and uplink aware cell association phase of the problem, while the RB distributionphase is kept optional for energy saving purposes. As users cannot measure the uplinkattributes such as the uplink interference by listening to the reference signals of BSs, alimited amount of feedback is added to the reference signals of the BSs to inform the usersof the uplink interference and make the distributed algorithm design possible. The amountof feedback introduced to the system is negligible compared to already existing referencesignals in standards such as LTE-Advanced. Moreover, by assigning different weights tothe downlink and uplink rates in the objective of the defined optimization problem, theproposed distributed scheme can be modified to be only downlink oriented, only uplinkoriented, or both downlink and uplink aware. Comparing the proposed scheme with the483.1. System modeldownlink oriented maximum SINR scheme, significant uplink rate gains are observed. Rategains in the downlink are also considerable.In RB distribution phase, the remaining RBs are distributed among the users to increasetheir rates. The RB distribution problem can be decoupled with respect to downlink anduplink. Therefore, the RB distribution problem is broken into downlink and uplink RBdistribution sub-problems. Both of the sub-problems have a similar structure to that of thewater-filling problem. Therefore, their optimal solution is obtained through KKT conditions.It should be mentioned that interference co-ordination, resource partitioning, as well asfrequency selectivity of wide channels are not considered to keep the system model as generalas possible.The rest of the chapter is organized as follows: In the next section, the chosen systemmodel is described. Defining our optimization problem as well as outlining the solutionapproach are brought in Section 3.2. A base line cell association solution is presented inSection 3.3. The distributed cell association scheme and a solution to the RB distributionproblem are presented in Section 3.4. Finally, We examine the performance of our proposedschemes in this chapter through numerical simulations in Section 3.5.3.1 System modelThe network of interest is a multi-tier HetNet composed of a set of BSs B = {1, 2, · · · , NB}and a set of users U = {1, 2, · · · , NU}. An individual BS is indicated by j ∈ B and anindividual user is denoted by i ∈ U . All the BSs are connected through a high speedbackhaul and negotiate with each other with negligible time delay. Furthermore, all BSsconstantly transmit unique pilot signals from which users can estimate the average channelpower gains between themselves and all the BSs in their range.The transmitting power of BS j is assumed to be the constant PBj W while user i iscapable of transmitting at P Ui W of power. Depending on the available bandwidth andscheduling interval at BS j, BS j has NDLj available RBs to distribute among its associatedusers in the downlink and NULj available RBs to distribute among its associated users in theuplink. nDLij indicates the number of RBs given to user i by BS j to be used in downlinktransmission, and nULij represents the number of RBs given to user i by BS j for uplinktransmission. The number of RBs given to a user depends on the QoS level required by thatuser; higher number of RBs improves QoS.493.1. System modelTable 3.1: List of key parameters in Chapter 3U Set of usersB Set of BSsi User i ∈ Uj BS j ∈ BNDLj / NULj Downlink/Uplink budget of BS j#RBs given to user inDLij / nULij from BS j in downlink/uplinkPBj Transmitting power of BS jP Ui Transmitting power of user iHij = GijFij Channel power gain between user i and BS jGij Large scale component of HijFij Small scale component of Hijλij = 1Gij Exponential parameter of HijSINRDLij / Instantaneous SINR at user iSINRULij from BS j / at BS j from user iSINRDLij / Long term SINR at user iSINRULij from BS j / at BS j from user iInstantaneous RB capacity at user icDLij / cULij from BS j / at BS j from user iLong term RB capacity at user ic¯DLij / c¯ULij from BS j / at BS j from user iInstantaneous rate at user irDLij / rULij from BS j / at BS j from user iLong term rate at user ir¯DLij / r¯ULij from BS j / at BS j from user iDownlink/Uplink probabilityPODLij / POULij of outage on link i− jγDLi / γULi Downlink/Uplink rate requirement of user iDownlink/Uplink outage probabilityTDLi / TULi requirement of user iMinimum # of required RBs of user in¯DLij / n¯ULij from BS j in downlink/uplinkWorst case outage probability of user iPˆOUPij connected to BS j in the uplinkMinimum # of RBs to satisfy the worstnˆUPij outage QoS constraint in uplinkrˆUPij Long term rate of user i associated with nˆUPij503.1. System modelThe positive channel power gain between BS j and user i is represented by Hij as inHij = GijFij, ∀(i, j) ∈ U × B, (3.1)where Gij is the large scale slow fading component of the channel capturing the effects of pathloss and shadowing, and Fij represents the small scale fast fading component of the channel.In the above equation, ·× · denotes the Cartesian product of two sets. It is assumed that Gijremains constant during one association period. To model the small scale Rayleigh fading,it is assumed that Fij fluctuates fast during an association period following an exponentialprobability distribution function with variance 1. According to these assumptions, Hij is anexponentially distributed RV with expected value (E[Hij]) of Gij. In other words, Hij is anexponentially distributed RV with parameter λij, whereλij =1E[Hij]=1Gij, ∀(i, j) ∈ U × B. (3.2)User i can estimate the exponential parameter of the channel λij between itself and all theBSs in its range by listening to the pilot signals the BSs transmit.The instantaneous SINR seen by user i from BS j (downlink) and seen by BS j from useri (uplink) are respectively defined asSINRDLij =PBj Hij∑k∈B\{j} PBk Hik + ∆fN0, (3.3)SINRULij =P Ui Hij∑k∈U\{i} PUk Hkj + ∆fN0, (3.4)where ∆f , without loss of generality, is the bandwidth of one RB, N0 is the noise spectralpower, and · \ · is the set minus operation.The instantaneous achievable Shannon capacity is a logarithmic function of SINR. There-fore, the instantaneous achievable Shannon capacities on a single RB in downlink and uplinkarecDLij = log2(1 + SINRDLij ), (3.5)cULij = log2(1 + SINRULij ), (3.6)respectively.Given that user i is connected to BS j, and BS j allocates nDLij and nULij RBs to user ifor its downlink and uplink transmissions, respectively, the instantaneous rates seen by that513.1. System modeluser on the downlink and uplink arerDLij = nDLij cDLij , (3.7)rULij = nULij cULij . (3.8)The above equations are valid if we assume flat fading on the bandwidth of BSs from theusers’ point of view. The flat fading assumption is made to preserve simplicity in the systemmodel. The study of the frequency selective fading scenario where users see different channelgains on different RBs (and in turn, different SINR levels and capacities on different RBs)is left for future work.Associated with the instantaneous SINR, capacity, and rate, we define the long termSINR, capacity, and rate where only the large scale component of the channel power gainsGij is taken into account and the fast fading small scale component Fij is averaged out.Indicating the long term SINR, capacity, and rate by SINR, c¯, and r¯, respectively, theseparameters for user i that is assumed to be connected to BS j in the downlink and uplinkareSINRDLij =PBj Gij∑k∈B\{j} PBk Gik + ∆fN0, (3.9)SINRULij =P Ui Gij∑k∈U\{i} PUk Gkj + ∆fN0, (3.10)c¯DLij = log(1 + SINRDLij ), (3.11)c¯ULij = log(1 + SINRULij ), (3.12)r¯DLij = nDLij c¯DLij , (3.13)r¯ULij = nULij c¯ULij . (3.14)The outage event for user i on its downlink is defined as the event where the instantaneousdownlink rate of that user drops below a certain threshold γDLi . Likewise, the uplink outageevent is the event where the instantaneous uplink rate of user i drops below a threshold γULi .We indicate the probability of outage on downlink by PODLij , while the probability of outageon the uplink is indicated by POULij , wherePODLij = Pr{rDLij ≤ γDLi }, (3.15)POULij = Pr{rULij ≤ γULi }. (3.16)Given the exponential parameters of the channel power gains λij and the number of RBs523.1. System modelgiven to user i by BS j, PODLij and POULij can be calculated analytically using the followingformulas [68, 69]PODLij = 1−(e−λij∆fN0PBjΓDLij) ∏k∈B\{j}( λikPBkλijPBjΓDLij +λikPBk), (3.17)POULij = 1−(e−λij∆fN0PUiΓULij) ∏k∈U\{i}( λkjPUkλijPUiΓULij +λkjPUk), (3.18)whereΓDLij = 2γDLinDLij − 1, (3.19)ΓULij = 2γULinULij − 1. (3.20)We refer the reader to [68] for an easy to read proof validating the results in (3.17) and(3.18). Moreover, inspecting (3.17) and (3.18), it can be observed that PODLij and POULij arestrictly decreasing functions of nDLij and nULij , respectively; more RBs improves the outagebehaviour.Each user requires a certain level of QoS on its downlink and a certain level of QoS on itsuplink. We define the QoS class required by user i on downlink to be the pair (γDLi , TDLi ),where γDLi > 0 is the rate threshold and 0 < TDLi < 1 is the maximum outage probabilityneeded by user i. User i wants its instantaneous rate to drop below γDLi no more than TDLifraction of time. Likewise, The QoS class required by user i on the uplink is defined bythe pair (γULi , TULi ). The reason behind selecting the outage framework to define the QoSconstraints is to tackle the wireless environments with fast fading. It is well-establishedin theory of communication that ensuring a minimum instantaneous rate to users is notachievable in environments with high mobility and fast fluctuations in the channel gains.However, it is possible to provide a certain rate level with a certain outage probabilitydepending on the average channel gains.Assuming that user i is connected to BS j, and BS j has allocated nDLij and nULij RBsto user i to be used in downlink and uplink transmissions, respectively, the downlink anduplink outage QoS constraints of user i arePODLij = Pr{rDLij ≤ γDLi } ≤ TDLi , (3.21)POULij = Pr{rULij ≤ γULi } ≤ TULi . (3.22)533.2. Problem formulationAs it has been mentioned before, the PODLij and POULij are strictly decreasing functionsof number of allocated RBs nDLij and nULij , respectively. Therefore, there is a lower bound onnDLij and a lower bound on nULij above which the outage probability requirements of the user,PODLij < TDLi and POULij < TULi , are satisfied. We indicate these two lower bounds by n¯DLijand n¯ULij , respectively.nDLij ≥ n¯DLij , (3.23)nULij ≥ n¯ULij . (3.24)According to (3.23) and (3.24), if BS j is the serving BS of user i, BS j is obliged to allocate touser i at least n¯DLij RBs for downlink transmission and n¯ULij RBs for uplink transmission. Sincenij can only assume natural numbers, finding these lower bounds can be done by incrementingthe number of RBs one by one and checking whether the outage QoS is satisfied.In the next section, it will be apparent how the joint uplink and downlink cell associationproblem is defined and formulated over the described system model in this section.The key parameters that are used in this chapter are listed in Table 3.1.3.2 Problem formulationIn order to define the cell association problem, we first introduce the NU ×NB binary asso-ciation indices matrix x. xij ∈ {0, 1} is the element on ith row and jth column of matrix x.If xij = 1, user i is associated with BS j, otherwise xij = 0. We also introduce the NU ×NBmatrices nDL and nUL. Matrices nDL and nUL contain nDLij and nULij elements, respectively,which are the number of RBs that BS j allocates to user i in downlink and uplink.Next step is to define the objective of the problem. We select the weighted sum of theutility of downlink and uplink long term data rates as the objective function to be maximized:∑i∈U∑j∈Bxij(wDLi Ui(r¯DLij ) + wULi Ui(r¯ULij )).In the above equation, Ui(·) is an increasing and concave function that models the satisfactionlevel of user i from the rate it gets, whether the rate is in the downlink or uplink. wDLi isthe weight that user i assigns to its satisfaction from the rate it gets in downlink. Similarly,wULi is the weight that user i assigns to its satisfaction from the uplink rate. Without lossof generality, we can assume wDLi > 0, wULi > 0, and wDLi + wULi = 1. If the user is runningdownlink rate hungry applications on its end such as video streaming applications, then it is543.2. Problem formulationreasonable to expect that the weight assigned to downlink wDLi = 1, and in turn, wULi = 0.On the other hand, in applications that crave for uplink rate such as uploading a large file,wULi = 1. In the middle point of these two extremes, applications that require comparablerates on both downlink and uplink lead the user to set wDLi = wULi = 0.5.Finally, considering the finite resource budget of the BSs and also the outage QoS con-straints introduced in (3.21) and (3.22), the joint uplink and downlink cell association withoutage QoS provisioning problem (P) isP : maximizex,nDL,nUL∑i∈U∑j∈Bxij(wDLi Ui(r¯DLij ) + wULi Ui(r¯ULij ))(3.25)subject to C1 :∑i∈UxijnDLij ≤ NDLj , ∀j ∈ B,C2 :∑i∈UxijnULij ≤ NULj , ∀j ∈ B,C3 :∑j∈Bxij ≤ 1, ∀i ∈ U ,C4 :∏j∈B(PODLij)xij ≤ TDLi , ∀i ∈ U ,C5 :∏j∈B(POULij)xij ≤ TULi , ∀i ∈ U ,xij ∈ {0, 1}, ∀(i, j) ∈ U × B, (3.26)nDLij ∈ {0, 1, . . . , NDLj },∀(i, j) ∈ U × B, (3.27)nULij ∈ {0, 1, . . . , NULj },∀(i, j) ∈ U × B. (3.28)In optimization problem P, constraints C1 and C2 are resource budget constraints; theyassure the number of RBs given to users does not exceed the BS budget in the downlink anduplink for all the BSs. The third constraint, C3, allows the users to be connected to at mostone BS at a given time. Constraints C4 and C5 are the outage QoS constraints in downlinkand uplink, respectively. These two constraints are obtained by manipulating inequalities(3.21) and (3.22). Lastly, constraints (3.26), (3.27), and (3.28) keep the association indicesbinary, and the number of RBs given to users integers within the BSs’ budgets.Solving problem P optimally with low complexity is involved since it is a complicatedmixed integer and combinatorial optimization problem over three sets of variables x, nDL,and nUL. In order to reduce the complexity, we approach the problem in two phases. First,by fixing nDL and nUL elements we solve for x, i.e., solving the cell association phase. Notethat assigning nDL and nUL elements to arbitrary integers can violate the QoS constraints.However, nDL and nUL elements need to be assigned to integers that satisfy inequalities (3.23)553.2. Problem formulationand (3.24). In the second phase, we set x to the result of the cell association phase and solvefor nDL and nUL, i.e., the RB distribution phase. In this chapter, we mostly address the cellassociation phase and let the RB distribution phase to be optional.In order to devise a base line solution to the cell association problem, we let nDL andnUL to be the minimum number of required RBs by users to satisfy their QoS constraints,i.e., nDLij = n¯DLij and nULij = n¯ULij , ∀(i, j) ∈ U × B. Then, we solve for x. The centralized baseline cell association solution is presented in the next section.Later in the chapter, we will make it clear how the ability of users to estimate theirminimum number of required RBs helps in devising a distributed cell association scheme.As mentioned in Section 3.1, user i can estimate the average channel gains between itselfand all the BSs in its range by listening to the BSs’ pilot signals. Average channel gains(Gij = 1/λij) and the QoS class that user i requires are enough for user i to be ableto calculate the minimum required number of RBs in downlink (n¯DLij ) for all the BSs inits range using (3.17) and (3.21). However, n¯ULij cannot be estimated by user i given λijbetween itself and all the BSs since the user cannot estimate the interference level createdby other users at a given BS. Only the BS can measure the uplink interference levels. Inorder to devise a distributed scheme, we require the BSs to quantize the uplink interferencelevels with few number of bits and broadcast it along with their other reference signals.Low number of bits to represent the uplink interference level puts negligible message passingoverhead over already existing reference signals of BSs. From this reference signal, the userconservatively estimates the minimum number of required uplink RBs to keep the worst caseQoS constraint satisfied, compensating for the quantization error. Introducing this limitedamount of feedback, we present a distributed cell association scheme in Section 3.4.From another perspective, keeping the allocated number of RBs to users minimum helpspreserving energy by spending less power. Power efficiency is more valuable to the userswith their limited battery lives compared to the BSs. Also, reducing the consumed powercontributes to leaving behind less carbon footprint that is harmful to nature [30]. Powersaving concerns also motivates us to let the RB distribution phase (solving for nDL and nUL)be optional. Moreover, it will be seen in Section 3.4 that after the cell association phase, theRB distribution phase in downlink and uplink can be done separately using the techniquepresented in Subsection 2.4.1 of this thesis.563.3. Base line cell association solution3.3 Base line cell association solutionIn this section, we provide a centralized solution to the cell association phase of problem P.As mentioned in the previous section, we replace the downlink and uplink QoS constraintsin P (C4 and C5) by nDLij = n¯DLij and nULij = n¯ULij , respectively, ∀(i, j) ∈ U × B. Afterapplying this change, an assignment problem that is NP-hard in x is resulted because ofthe resource budget constraints C1 and C2 [71]. Therefore, we propose to relax the binaryconstraint (3.26) to convert the integer program to a convex one. We replace (3.26) by0 ≤ xij ≤ 1,∀(i, j) ∈ U ×B. We call the resulting problem the ideal cell association problemand indicate it by Px as the followingPx : maximizex∑i∈U∑j∈Bxijaij (3.29)subject to∑i∈Uxijn¯DLij ≤ NDLj , ∀j ∈ B,∑i∈Uxijn¯ULij ≤ NULj , ∀j ∈ B,∑j∈Bxij ≤ 1, ∀i ∈ U ,0 ≤ xij ≤ 1, ∀(i, j) ∈ U × B, (3.30)whereaij =(wDLi Ui(r¯DLij ) + wULi Ui(r¯ULij )).The above problem is a linear program in x that can be solved efficiently using well-established methods such as the simplex method [77]. We call the solution obtained bysolving the linear program the ideal solution. Note that the ideal solution may not result inbinary association indices. This can be problematic since it indicates some users are con-nected partially to several BSs. In order to produce binary association indices, we round theideal solution to the closest integer. We call this solution the rounding solution. The valueof the objective function obtained by applying the rounding solution is upper bounded bythe value obtained by plugging in the ideal solution. The rounding solution is used as a baseline solution with which we compare our distributed solution presented in the next section.Moreover, we have observed in our simulations that results of the ideal and roundingsolutions are very close. The rounding solution is always within 5% error margin of the idealsolution, which indicates that the ideal solution is mostly composed of 0s and 1s.573.4. Distributed cell association solution3.4 Distributed cell association solutionIn this section, we present a distributed solution to the cell association phase of problemP. As mentioned in Section 3.2, the ability of users to estimate the number of RBs tosatisfy downline and uplink outage QoS constraints greatly helps in devising a distributedscheme. As for the downlink minimum required number of RBs, we have shown that theusers can estimate the average channel gain between themselves and all the BSs in the rangeby listening to BSs’ unique pilot signals. By applying the average channel gains and therequired QoS class in the downlink determined by the pair (γDLi , TDLi ) in (3.17) and (3.21),users can estimate n¯DLij . However, estimating n¯ULij is not possible at the user end, unless theBSs inform the users of the uplink interference level seen by the BS. In the next subsection,we require the BSs to quantize the uplink interference levels and broadcast them using fewnumber of bits. The users then can estimate the worst case interference level associatedwith the broadcasted quantized interference level, and in turn, the minimum number of RBsrequired to have the uplink QoS satisfied assuming the worst case interference level.3.4.1 Worst case uplink outage probability and the associatedrequired number of RBsWe require the BSs to broadcast the quantized version of the measured uplink interferencelevels along with their other reference signals. Note that the interference at each BS (uplinkinterference) is created by the users that are in the vicinity of and not connected to theinvestigated BS. Therefore, it can be assumed that the interference level for all the usersthat are going to be connected to this BS is identical. Let the interference level at BS j beIULj =∑k∈UjP Uk Hkj, (3.31)where Uj is the set of interfering users at BS j. We also assume that there is a lower andupper bound on the uplink interference level as the followingIULj ∈ [IULmin, IULmax]. (3.32)If BS j uses M bits to quantize the interference level, there are L = 2M different levels inthe interval [IULmin, IULmax]. Then, if BS j measures the interference level to be IULj , it transmits583.4. Distributed cell association solutionlj ∈ {0, 1, · · · , L− 1} as the quantized interference level, wherelj =⌊IULj − IULminIULmax−IULminL⌋. (3.33)In the above equation, b·c represents the floor function that rounds the argument to thelargest integer less than or equal to the argument.Upon receiving the value of lj from BS j by a user, the user assumes that the highest(worst) interference in the lthj level is happening. Indicating this interference level by IˆULj ,we obtainIˆULj = IULmin + (lj + 1)(IULmax − IULminL). (3.34)Replacing the term∑k∈B\i PUk Hkj by IˆULj in (3.4), and in turn, modifying (3.6), (3.8), (3.10),(3.12) and (3.14), the worst case uplink outage probability that is indicated by OˆPULij can bedefined asPˆOULij = Pr{nULij log2( P Ui HijIˆULj + ∆fN0)≤ γULi}. (3.35)In the above definition, the only RV is Hij which is an exponentially distributed RV withparameter λij that is measurable by the user. Therefore, the user can calculate the worstcase outage probability asPˆOULij = 1− e−λijPUi(ΓULij (IˆULij +∆fN0)), (3.36)where ΓULij is given in (3.20). Now, the new uplink outage QoS constraint determined by thepair (γULi , TULi ) is(PˆOULij = Pr{rULij ≤ γULi })≤ TULi . (3.37)By applying (3.36) in (3.37), user i can estimate the minimum number of required RBs tosatisfy the worst case uplink QoS constraint. Indicating this number by nˆULij , we havenˆULij =⌈ γULilog2(1 + PUi /λijIˆULj +∆fN0log( 11−Ti ))⌉. (3.38)In the above equation, d·e represents the ceiling function that rounds the argument to the593.4. Distributed cell association solutionsmallest integer greater than or equal to the argument.It should be noted that nˆULij ≥ n¯ULij , since in the worst case, the user assumes a higherlevel of uplink interference than what it actually is.3.4.2 Cell association solutionAs outlined in Section 3.2, we replace the downlink and uplink QoS constraints in P (C4and C5) by nDLij = n¯DLij and nULij = nˆULij , respectively, ∀(i, j) ∈ U × B. n¯DLij and nˆULij are theminimum number of RBs that user i needs from BS j to have the downlink QoS and uplinkworst case QoS constraints satisfied while they are calculatable at the user end. Similarto the previous section, we relax the association constraints in P by replacing (3.26) with0 ≤ xij ≤ 1, ∀(i, j) ∈ U × B. We relax the association constraints so that the combinatorialnature of the problem transforms into a continuous and convex one. Then the Lagrange dualdecomposition method can be applied to search for a distributed scheme solving the resultingproblem. The resulting cell association problem is indicated by Pˆx as in the followingPˆx : maximizex∑i∈U∑j∈Bxij aˆij (3.39)subject to∑i∈Uxijn¯DLij ≤ NDLj , ∀j ∈ B, (3.40)∑i∈UxijnˆULij ≤ NULj , ∀j ∈ B, (3.41)∑j∈Bxij ≤ 1, ∀i ∈ U , (3.42)0 ≤ xij ≤ 1, ∀(i, j) ∈ U × B, (3.43)whereaˆij =(wDLi Ui(r¯DLij ) + wULi Ui(rˆULij )). (3.44)In the above equation, rˆULij is the long term uplink rate that user i receives assuming theworst case uplink interference level IˆULij and worst case minimum number of required uplinkRBs nˆULij .Similar to problem Px in the previous section, problem Pˆx is a linear optimization prob-lem; therefore, it is also convex [72]. Moreover, it can be shown that Slater’s condition holdsfor Pˆx. Slater’s condition is the necessary and sufficient condition for the strong dualityproperty to hold [72]. The strong duality property of Px implies that the optimum value603.4. Distributed cell association solutionof the Lagrange dual problem is identical to the optimum value of the original problem.Because of the strong duality property of problem Pˆx, and also in an attempt to devisea distributed scheme, we choose to solve this problem using Lagrange dual decompositionmethod [73].The Lagrangian of Pˆx is defined by keeping the constraints (3.42) and (3.43), and takingconstraints (3.40) and (3.41) into the objective function. We also introduce NB × 1 vectorsµDL and µUL that contain the Lagrange multipliers associated with the downlink and uplinkresource constraints of the BSs indicated by µDLj and µULj . The Lagrangian of Pˆx is given byL(x,µDL, µUL) =∑i∈U∑j∈Bxij aˆij −∑j∈BµDLj(∑i∈Uxijn¯DLij −NDLj)+∑i∈U∑j∈Bxij aˆij −∑j∈BµULj(∑i∈UxijnˆULij −NDULj). (3.45)Then, the Lagrange dual function of Pˆx is obtained from the Lagrangian as in the followingg(µDL, µUL) =supx∑i∈U∑j∈Bxij(aˆij − µDLj n¯DLij − µULj nˆULij )+∑j∈BµDLj NDLj +∑j∈BµULj NULj (3.46)subject to 0 ≤ xij ≤ 1, ∀(i, j) ∈ U × B, (3.47)∑j∈Bxij ≤ 1, ∀i ∈ U . (3.48)The Lagrange dual function g(µDL, µUL) can be decoupled with respect to users; therefore,it can be written in the following formg(µDL, µUL) =∑i∈Ugi(µDL, µUL)+∑j∈BµDLj NDLj +∑j∈BµULj NULj , (3.49)where for all users i ∈ U we havegi(µDL, µUL) = supxij ,j∈B∑j∈BxijQIij (3.50)subject to 0 ≤ xij ≤ 1, j ∈ B,613.4. Distributed cell association solution∑j∈Bxij ≤ 1.In the above equation, QIij is called the qualification index of BS j from user i’s point ofview, and it is given byQIij = aˆij − µDLj n¯DLij − µULj nˆULij , ∀(i, j) ∈ U × B. (3.51)If we require the BSs to broadcast their Lagrange multipliers in uplink and downlink,µDL and µUL, along with the quantized uplink interference level and other already existingreference signals, user i can calculate all the terms in QIij. Then, gi(µDL, µUL) in (3.50) canbe solved at the user end. Accordingly, the unique solution to the user’s problem isxij =1 if j = j∗0 if j 6= j∗, ∀i ∈ U , (3.52)wherej∗ = argmaxj∈B(QIij), ∀i ∈ U . (3.53)This procedure automatically produces binary association indices. Therefore, no additionalrounding is required.As for the Lagrange multipliers, we use the gradient descent method [72]. Therefore, weupdate the Lagrange multipliers for all BSs j ∈ B according to the followingµDLj (t+ 1) =[µDLj (t)− β(t)(NDLj −∑i∈Uxijn¯DLij)]+,µULj (t+ 1) =[µULj (t)− β(t)(NULj −∑i∈UxijnˆULij)]+, (3.54)where the terms (NDLj −∑i∈U xijn¯DLij)and (NULj −∑i∈U xijnˆULij)are the partial derivatives ofthe Lagrangian with respect to the downlink and uplink Lagrange multipliers, respectively.In addition, the operator [·]+ returns the maximum of the argument in the operator and 0,and β(t) is a step size that satisfies the following two conditionslimt→∞β(t) = 0 , and∞∑t=1β(t) =∞. (3.55)623.4. Distributed cell association solutionThe above conditions assure the convergence of the gradient descent method if the associationindices are continuous variables of the form 0 ≤ xij ≤ 1, as indicated by proposition 6.3.4 in[74]. Nevertheless, β(t) = 0.5/t is used in our simulations, and in all cases the distributedscheme converged in less than 50 iterations; most of the times the convergence was reachedin less than 25 iterations.3.4.3 Distributed cell association scheme designIn this subsection, we describe the designed cell association scheme based on the analysis inthe previous subsection.Step 1: Initialization All BSs j ∈ B initialize their associated Lagrange multipliers, µDLjand µULj , and broadcast them in the network. The BSs also measure the uplink interferencelevels and quantize them to obtain lj. Each BS j broadcasts lj along with µDLj , µULj , andother reference signals.Step 2: User request All Users i ∈ U listen to BSs and acquire λij, µDLj , µULj , and ljfor all BSs in their range. From these, users calculate n¯DLij , nˆULij , and QIij for all the BSs intheir range. Then, each user i sends an association request to the BS with the best QIij (BSj∗ in (3.53)). The association request contains the required number of RBs in downlink anduplink, n¯DLij , nˆULij .Step3: User admission BSs receive the users’ requests. If BSs can accommodate allthe requests they receive without violating the resource budget constraints, an admissionmessage will be sent to the users. Now, the users are connected to their desired BSs.Step 4: BS Lagrange multiplier update BSs update their Lagrange multipliersaccording to (3.54). BSs also update the uplink interference level according to their newmeasurements. Each BS j broadcasts the new µDLj , µULj , and lj in the network. The schemecontinues by going to step 2.Few remarks on the scheme are as follows:Remark 1 By inspecting (3.44) and (3.51), it can be seen that each user tends tosend an association request to the BS that provides the best utility of rate with the lowerrequired number of RBs. Users also tend to associate with BSs that have lower Lagrangemultipliers (Lagrange multipliers can be interpreted as the price of connecting to a givenBS). By inspecting (3.54), it can be seen that BS j increases its price if the load on BS jincreases. As a result, users are guided towards less populated BSs in the network. Thesemechanisms achieve some levels of load balancing.Remark 2 In this scheme, users receive only enough number of RBs to have their QoSconstraints satisfied. This is in particular important in reducing the energy consumption.633.4. Distributed cell association solutionRemark 3 In step 3, some BSs may not have enough RBs to accommodate all their userrequests. This case is discussed in the next subsection.3.4.4 Feasibility problem and admission controlIn the distributed cell association scheme, the users determine the BS to which they want toconnect through (3.53). This is while the users do not have any information on how manyother users are requesting to connect to that BS, and how many available RBs are left forthe BS to allocate to its users. As a consequence, BSs may violate their resource constraintsin downlink or uplink (constraints (3.40) or (3.41)) upon admitting all the requests theyreceive. In other words, the association indices x is infeasible under such conditions. Apartfrom the fact that the infeasibility of the solution indicates a systematic problem, it alsoaffects the convergence of the gradient descent method from a mathematical point of view.Therefore, at any instance where the solution is infeasible, it needs to be brought back tothe feasible set. This motivates us to use the gradient projection method [75] instead of thegradient descent method.In this chapter, we use a heuristic to project the association solution back to the feasibleset. We add this heuristic as an intermediate step in step 2 of the distributed schemedescribed in the previous subsection. Firstly, we require the users to modify their requestmessages that they send to the BS with the best qualification index QIij∗ , where j∗ is givenin (3.53). The users sort the BSs in their range according to their qualification index QIijin descending order. The request that user i sends to BS j∗ contains this sorted list of BSsaccording to their QIij. The request also contains the number of RBs in downlink and uplinkrequired from each BS in the list.BSs process the requests received from the users. If BS j has enough RBs in the downlinkand uplink to accommodate all the user requests, those users will be admitted to BS j.Otherwise, if the uplink resource budget is violated, BS j forwards the request of users thatconsume the highest number of uplink RBs to the indicated second best BS in the listsuntil the uplink resource constraint is satisfied. The second best BS checks whether it canaccommodate all the user requests it has received. If not, the second best BS forwards therequest of the users consuming the highest number of RBs to the next best BS according tothe list in the users’ requests. The procedure continues until all users are accommodated.The same procedure is performed if the downlink resource budget is violated. If both resourceconstraints in downlink and uplink are violated, the BS separately processes the downlinkand uplink and forwards the requests to the next best BS according to the lists provided inthe users’ requests.643.4. Distributed cell association solutionThis intermediate step achieves further load balancing by avoiding some BSs to getoverpopulated.In the next subsection, we briefly address distributing the rest of the RBs available atthe BSs.3.4.5 RB distribution phaseThe cell association phase of problem P has been addressed in Sections 3.3 and 3.4. Inthis subsection, we use the association indices x from the distributed cell association phasesolution and solve for nDL and nUL to distribute the remaining RBs and further improvethe users’ rates. If we define Uj as the set of users connected to BS j, the RB distributionproblem at each BS j ∈ B, which is indicated by Pn,j, can be written asPn,j : maximizen˜DLij ,n˜ULij ,i∈Uj∑i∈Uj(wDLi Ui(nDLij c¯DLij ) + wULi Ui(nULij c¯ULij ))(3.56)subject to∑i∈UjnDLij ≤ NDLj , (3.57)∑i∈UjnULij ≤ NULj , (3.58)nDLij = n¯DLij + n˜DLij , ∀i ∈ Uj, (3.59)nULij = nˆULij + n˜ULij , ∀i ∈ Uj. (3.60)In problem Pn,j, n¯DLij and nˆULij are the number of already allocated RBs by the distributedcell association scheme in downlink and uplink, respectively. However, n˜DLij and n˜ULij are theextra RBs that are allocated to the users connected to BS j through solving Pn,j. Moreover,It is implicitly assumed that n˜DLij and n˜ULij are integer values that satisfy n¯DLij ≤ n˜DLij ≤ NDLjand nˆULij ≤ n˜ULij ≤ NULj . It is also implicitly assumed that wDLi and wULi are not zero. It canbe seen that problem Pn,j can be decoupled with respect to uplink and downlink. Therefore,problem Pn,j is broken into two sub-problems for each BS j ∈ B: downlink RB distributionproblem (PDLn,j), and uplink RB distribution problem (PULn,j):PDLn,j : maximizen˜DLij ,i∈Uj∑i∈UjwDLi Ui(nDLij c¯DLij ) (3.61)subject to∑i∈UjnDLij ≤ NDLj , (3.62)nDLij = n¯DLij + n˜DLij , ∀i ∈ Uj, (3.63)653.5. Numerical simulation resultsPULn,j : maximizen˜ULij ,i∈Uj∑i∈UjwULi Ui(nULij c¯ULij ) (3.64)subject to∑i∈UjnULij ≤ NULj , (3.65)nULij = nˆULij + n˜ULij , ∀i ∈ Uj. (3.66)If we assume that n˜DLij and n˜ULij are continuous variables, it can be shown that both PDLn,jand PULn,j are convex optimization problems for which strong duality property holds since theobjective functions are composed of concave utility functions and the constraints are affine[72]. In fact, both PDLn,j and PULn,j have a similar structure to that of water-filling problem.Therefore, n˜DLij and n˜ULij can be found using KKT conditions [72]. After writing the KKTconditions for PDLn,j , the number of extra RBs in downlink aren˜DLij =[1c¯DLij(U′i )−1( νDLwDLi c¯DLij)− n¯DLij]+, ∀i ∈ Uj, (3.67)where νDL is the unique solution of the following equation∑i∈Ujmax{1c¯DLij(U′i )−1( νDLwDLi c¯DLij), n¯DLij}= NDLj . (3.68)In addition, (U′i )−1(·) is the inverse of the derivative of Ui(·) with respect to n˜DLij . The solutionof the above equation is unique since Ui(·)s are concave and strictly increasing functions,hence, (U′i )−1(·) and its weighted sum is a strictly increasing (monotonic) function of νDL.This equation can be solved efficiently using a numerical search method. The resulting n˜DLijis then rounded to the closest integer less than or equal to n˜DLij in order to have integernumber of RBs.The number of extra RBs for the uplink users at each BS can be obtained in a similarmanner.3.5 Numerical simulation resultsIn this section, the joint uplink and downlink distributed cell association scheme describedin Section 3.4 is examined through numerical simulations. We consider three tires of BSs. In1000 m×1000 m cells, we fix 1 macro BS at the centre of the cell and randomly locate 5 microBSs, 10 femto BSs, and 200 users in each cell, unless otherwise stated. The transmittingpower of macro BSs, micro BSs, femto BSs, and users are set to 46, 35, 20, and 20 dBm,663.5. Numerical simulation resultsrespectively. The large scale path loss between users and macro BSs is modelled as PL(d) =34 + 40 log10(d), where d is the distance in meters. The large scale path loss between usersand micro or femto BSs is PL(d) = 37 + 30 log10(d). Furthermore, shadowing effect comeson top of the large scale path loss as a lognormal RV with 8 dB of standard deviation,while exponentially distributed RVs with unit variance represent the Rayleigh small scalefading. Considering that RBs in LTE standard are 180 kHz wide in frequency domain, thethermal noise power is set to −111.45 dBm. The RB budget in both downlink and uplink is400, 200, and 100 for macro, micro and femto BSs, respectively. Finally, we assume that aproportionally fair scheduler is implemented at the BSs with scheduling interval of 1 second.In the following, the developed schemes refer to the distributed and base line schemes, whiledownlink oriented scheme refers to the developed schemes with wDL = 1 or the maximumSINR scheme, and uplink oriented scheme refers to either of developed schemes with wUL = 1.3.5.1 Rate cumulative distribution functionsAs mentioned in [44], the rate distribution is a more meaningful metric compared to SINRor spectral efficiency distribution to compare different schemes in HetNets. Therefore, weshow the cumulative distribution function (CDF) of the instantaneous rates in downlink anduplink in Figures 3.1 and 3.2. In these two figures, the rate threshold and outage probabilityrequirement of all users in the downlink and uplink is set to γDL = 1.2 bits/s and γUL = 0.6bits/s and T = 10%. Moreover, The number of uplink interference quantization bits is setto M = 8.In Figures 3.1 and 3.2, the downlink and uplink rate CDF is plotted for 7 cases. Thedownlink and uplink rate CDF of the distributed and base line cell association schemeswith wDL, wUL = 1, 0.5, and 0 comprises 6 curves, and the downlink and uplink rate CDFof the maximum SINR scheme is the seventh case. In the case of wDL = 0, we disregardthe downlink resource constraints to let the developed schemes focus only on the uplink.Therefore, the downlink resource constraints can be violated for some BSs. Similarly, sinceadmission control is not considered in maximum SINR scheme, some BSs may allocate moreRBs than their budget to users in downlink and have the downlink resource constraintsviolated. In these cases, the BS scheduler needs to schedule some users in the next schedulingintervals, leading to some reduction in the perceived data rate by the users. This ratereduction is taken into account in our simulations. The same arguments hold for uplink datarates in the developed schemes with wUL = 0, and maximum SINR scheme.As it can be seen in Fig. 3.1, the distributed and base line schemes with wDL = 1 and0.5 result in downlink rate CDFs that lie below the curve resulted from maximum SINR673.5. Numerical simulation results0 2 4 6 8 10 1200.10.20.30.40.50.60.70.80.91Rate (bit/s)Probability wDL=1, Dist.wDL=1, BaseLinewDL=0.5, Dist.wDL=0.5, BaseLinewDL=0, Dist.wDL=0, BaseLineMax SINRFigure 3.1: Downlink rate CDFs for the developed schemes with various wDL and maximumSINR scheme, where γDL = 1.2 bits/s, γUL = 0.6 bits/s, T = 10%, and M = 8scheme. This implies that the developed schemes outperform maximum SINR scheme inthe downlink when wDL = 1 and 0.5. However, with wDL = 0, both distributed and baseline schemes perform worse than the maximum SINR since developed schemes in this caseare uplink oriented (wUL = 1 when wDL = 0), while maximum SINR is a downlink orientedscheme. Furthermore, since the developed schemes are only downlink oriented with wDL = 1,we observe a better downlink performance compared to the case of wDL = 0.5 in which thedeveloped schemes are both uplink and downlink aware. Another observation on this figureis that the performance of the distributed and base line schemes in downlink is very closewith wDL = 1. As wDL = 1 results in identical optimization problems for the distributed andbase line schemes in downlink, the closeness of the curves obtained from the distributed andbase line schemes shows the precision. The performance obtained from distributed and baseline schemes in downlink for wDL = 0.5 are also close to each other since no quantization hasbeen introduced in the downlink.683.5. Numerical simulation results0 2 4 6 8 10 1200.10.20.30.40.50.60.70.80.91Rate (bit/s)Probability wUL=1, Dist.wUL=1, BaseLinewUL=0.5, Dist.wUL=0.5, BaseLinewUL=0, Dist.wUL=0, BaseLineMax SINRFigure 3.2: Uplink rate CDFs for the developed schemes with various wUL and maximumSINR scheme, where γDL = 1.2 bits/s, γUL = 0.6 bits/s, T = 10%, and M = 8In Fig. 3.2, we can see the uplink counterpart of Fig. 3.1. Similar to downlink, thedeveloped schemes with wUL = 1 show the best performance, which are followed by theperformance of the developed schemes with wUL = 0.5, while the worst uplink performancebelongs to maximum SINR scheme. Also, maximum SINR performs worse in uplink com-pared to its downlink counterpart since this scheme is downlink oriented. The performanceof the distributed and base line schemes with wUL = 0 is somewhat the same as in maximumSINR scheme. However, as opposed to the downlink case, the distributed scheme showshigher rates than those of the base line scheme for the cases of wUL = 1 and 0.5. This isbecause in the distributed scheme, the users see the worst case uplink interference resultedfrom the quantization process. Assuming worst uplink interference, users request for moreRBs to satisfy the worst case uplink QoS constraints.From another perspective, by zooming in at the left bottom corner of Figures 3.1 and3.2, we can verify whether the outage QoS constraints are satisfied. We also can compare693.5. Numerical simulation resultsthe rate of cell edge users. As for the QoS in downlink, the outage probabilities resultedfrom the distributed and base line schemes with minimum rate of γDL = 1.2 bits/s are 9.3%and 8.1% for the cases of wDL = 1 and 0.5, respectively, which are less than the requiredoutage probability of T = 10%. This is while the maximum SINR scheme cannot satisfy thedownlink QoS constraints. As for the QoS in uplink, the outage probabilities of 10%, 11% ,12%, and 14% are observed for the schemes of distributed with wUL = 1 and 0.5, and baseline with wUL = 1 and 0.5, respectively, for γUL = 0.6 bits/s. The outage QoS constraintsare only satisfied for the uplink oriented distributed scheme. This is because the interferencelevel that is reported by the BSs in the uplink is for the time that the new users in thenetwork are not associated yet. After the association process, the uplink interference levelschange depending on the association pattern. The new pattern and resulting interferencelevels change the outage probabilities which cannot be known beforehand at the user end.However, the conservative nature of the distributed scheme leads users closer to satisfyingthe QoS constraints. In fact, by studying Fig. 3.3, we will see that by decreasing the numberof quantization bits we can make the scheme more conservative and get closer to the requiredQoS by the users at the expense of consuming more RBs. It is worth mentioning that theuplink rates resulted from maximum SINR scheme drop below the required rate thresholdwith probability of around 50%. We define the cell edge users as the users that experiencethe lowest 10% rates. In the downlink, the rate gains of up to 1.5 is observed for γDL = 1.2bits/s. In our simulations, we have observed that this rate gain increases by increasing theminimum rate threshold γDL. In the uplink, on the other hand, the gain is more significant.As it can be seen in Fig. 3.2, users experience rates below the minimum value of the rates setin our the simulations (0.1 bits/s) with probability of more than 20%. Therefore, with thecurrent definition of cell edge users, very large uplink rate gains are resulted. If we modifythe definition of cell edge users to users with the worst 40% rates, the uplink rate gain isaround 7 for γUL = 0.6 bits/s. According to our simulations, this gain also increases byincreasing γUL.Fig. 3.3 shows the effects of number of uplink quantization bits M and uplink minimumrate threshold γUL on the uplink rate CDFs. CDF curves for M = 8, and 10, γUL = 0.5, and0.7 bits/s, distributed, base line, and maximum SINR schemes, and wUL = 1 are demon-strated. The depth of quantization M reduces the gap between base line and distributedschemes performance, implying that reducing the number of quantization bits provides higherrates to users at the expense of spending more RBs. Decreasing M also increases the like-lihood of satisfying the uplink QoS constraints. Moreover, increasing minimum uplink ratethreshold γUL increases the gap between developed schemes and maximum SINR scheme,implying that higher rates are provided to users by increasing γUL. This is while SINR703.5. Numerical simulation results0 2 4 6 8 10 1200.10.20.30.40.50.60.70.80.91Rate (bit/s)Probability M=8, γUL=0.5, Dist.M=10, γUL=0.5, DistM=8, γUL=0.7, Dist.M=10,γUL=0.7, Dist.γUL=0.5, BaseLineγUL=0.7, BaseLineγUL=0.5, Max SINRγUL=0.7, Max SINRFigure 3.3: Uplink rate CDFs for the distributed scheme with various M and γUL, and baseline and maximum SINR schemes with various γUL, where wUL = 1scheme does not respond to minimum uplink rate threshold since maximum SINR does nottake into account γUL in finding the cell association pattern. We have observed throughsimulations that minimum rate threshold plays a similar role in downlink rates for the devel-oped schemes as well as the maximum SINR scheme. In downlink, maximum SINR schemeresponds to changing γDL since it is downlink oriented and γDL is considered. However, afigure containing downlink CDF curves for various γDL is not included here.3.5.2 The effect of number of femto BSsFigures 3.4 and 3.5 show the effect of number of femto BSs on the sum utility of rates indownlink and uplink, respectively. The logarithmic utility function of U(x) = log(1 + x) isused in the simulations. In Fig. 3.4, the utility of rate curves in downlink are shown for theschemes of distributed with wDL = 1, 0.5, and 0, base line with wDL = 1, 0.5, and 0.5, andmaximum SINR. Fig. 3.5 contains utility of rate curves in uplink for the same schemes as713.5. Numerical simulation results5 10 15 201.81.922.12.22.32.42.52.62.7Average sum utility of rate in downlinkNumber of femto BSs wDL=1, Dist.wDL=1, Base LinewDL=0.5, Dist.wDL=0.5, Base LinewDL=0, Dist.wDL=0, Base LineMax SINRFigure 3.4: Downlink average utility of rate against number of femto BSs for the developedschemes with various wDL and maximum SINR scheme, where γDL = 1.2 bits/s, γUL = 0.6bits/s, T = 10%, and M = 10in Fig. 3.4.In Fig. 3.4, as expected from previous figures, the downlink oriented versions of thedeveloped schemes show the best performances, followed by the performances of developedschemes with wDL = 0.5. Maximum SINR curve falls between the curves from the developedschemes with wDL = 1 and 0.5, and the uplink oriented version of the developed schemes.Moreover, increasing the number of femto BSs enhances the performance of maximum SINRand developed schemes with wDL = 0, due to more availability of RBs in the network. Thedownlink aware versions of the developed schemes also show a slightly worse performancewith increasing the number of BSs, which is due to introducing more interference in thedownlink by increasing the number of BSs. Similar trends are observed for uplink in Fig.3.5, except that the uplink aware versions of the developed schemes keep the utility arounda constant. This is because increasing the number of BSs does not change the interferencelevels in uplink. In addition, as expected, the distributed scheme outperforms the base line723.5. Numerical simulation results5 10 15 200.40.60.811.21.41.61.82Average sum utility of rate in uplinkNumber of femto BSs wUL=1, Dist.wUL=1, BaseLinewUL=0.5, Dist.wUL=0.5, BaseLinewUL=0, Dist.wUL=0, BaseLineMax SINRFigure 3.5: Uplink average utility of rate against number of femto BSs for the developedschemes with various wUL and maximum SINR scheme, where γDL = 1.2 bits/s, γUL = 0.6bits/s, T = 10%, and M = 10scheme at the expense of consuming more RBs.3.5.3 The effect of number of usersFigures 3.6 and 3.7 show the effect of number of users on the sum utility of rates in downlinkand uplink, respectively. The logarithmic utility function of U(x) = log(1 +x) is used in thesimulations. In Fig. 3.6, the utility of rate curves in downlink are shown for the schemes ofdistributed with wDL = 1, 0.5, and 0, base line with wDL = 1, 0.5, and 0.5, and maximumSINR. Fig. 3.6 contains utility of rate curves in uplink for the same schemes as in Fig. 3.7.As expected, the developed schemes with proper weights outperform the maximum SINRscheme in both downlink and uplink. However, increasing the number of users in the networkworsens the downlink performance of the developed schemes with wDL = 0, and maximumSINR scheme. This is because more users require more RBs, which increases the likelihood733.5. Numerical simulation results100 110 120 130 140 150 160 170 180 190 2001.51.61.71.81.922.12.22.3Average sum utility of rate in downlinkNumber of users wDL=1, Dist.wDL=1, BaseLinewDL=0.5, Dist.wDL=0.5, BaseLinewDL=0, Dist.wDL=0, BaseLineMax SINRFigure 3.6: Downlink average utility of rate against number of users for the developedschemes with various wDL and maximum SINR scheme, where γDL = 1.2 bits/s, γUL = 0.6bits/s, T = 10%, and M = 10of having overloaded BSs in the downlink of developed schemes with wDL = 0 and maximumSINR scheme. However, the downlink aware versions of the developed schemes keep theutility in the downlink around a constant. In the uplink, the same trend is observed forthe developed schemes with wUL = 0 as well as the maximum SINR scheme. However, theuplink aware versions of the developed schemes also show a slightly worse performance withincreasing the number of users, which is due to introducing more interference in the uplinkby increasing the number of users.3.5.4 The effect of distributing the remaining RBsBy far, in all our simulations, we have considered only the base line and distributed cell asso-ciation algorithms solving the optimization problems Px and Pˆx. The effect of distributingthe remaining RBs after the cell association phase for downlink (solving PDLn,j on top of the743.5. Numerical simulation results100 110 120 130 140 150 160 170 180 190 2000.511.52Average sum utility of rate in uplinkNumber of users wUL=1, Dist.wUL=1, BaseLinewUL=0.5, Dist.wUL=0.5, BaseLinewUL=0, Dist.wUL=0, BaseLineMax SINRFigure 3.7: Uplink average utility of rate against number of users for the developed schemeswith various wUL and maximum SINR scheme, where γDL = 1.2 bits/s, γUL = 0.6 bits/s,T = 10%, and M = 10cell association problem Px or Pˆx) and uplink (solving PULn,j on top of the cell associationproblem Px or Pˆx) problems is demonstrated in Figures 3.8 and 3.9, respectively. In Fig.3.8, the downlink average utility of rate against minimum downlink rate threshold γDL forthe developed schemes with wDL = 1 and T = 10% are shown. In Fig. 3.9, the uplinkaverage utility of rate against minimum uplink rate threshold γUL for the developed schemeswith wUL = 1, T = 10%, and M = 10 are plotted. The first observation on these two figuresis that the developed algorithms with the remaining RBs significantly outperform the resultsobtained through the base line and distributed cell association schemes. Furthermore, by in-creasing the rate threshold, the performance of the base line and distributed cell associationschemes get close to the performance of these schemes with the remaining RBs. This trendis seen since more RBs are required to satisfy QoS constraints with higher rate thresholds,leaving less overall unused RBs in the network. Distributing less unused RBs among usersleads to a less improvement over cell association schemes.753.5. Numerical simulation results0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.211.21.41.61.822.22.42.6Average sum utility of rate in downlinkγDL (bits/s) Dist. without rest of RBsBaseLine without rest of RBsDist. with rest of RBsBaseLine with rest of RBsFigure 3.8: Downlink average utility of rate against minimum downlink rate threshold forthe developed schemes with wDL = 1 and T = 10%, showing the effect of distributing therest of RBs in downlink763.5. Numerical simulation results0.2 0.3 0.4 0.5 0.6 0.7 0.811.21.41.61.822.22.4Average sum utility of rate in uplinkγUL (bits/s) Dist. without rest of RBsBaseLine without rest of RBsDist. with rest of RBsBaseLine with rest of RBsFigure 3.9: Uplink average utility of rate against minimum uplink rate threshold for thedeveloped schemes with wUL = 1, T = 10%, M = 10, showing the effect of distributing therest of RBs in uplink77Chapter 4Outage Capacity Analysis for OFDMDecode-and-Forward Systems inFrequency Selective Rayleigh FadingChannelsIn this chapter, we investigate a DF two-hop relaying system consisting of one source, onerelay and one destination, in which OFDM is used in Rayleigh frequency selective channels.The contributions of this chapter are:• We present an outage probability analysis based on approximating the probabilitydistribution function (PDF) of the total capacity by a Gaussian distribution.• Tight approximations on the outage probability assuming correlated OFDM subcarriersas well as arbitrary number of bits on each OFDM subcarrier are found.• As a special case, i.i.d. OFDM subcarriers are also addressed where a closed formsolution to the variance of the total capacity is obtained, leading us to even tighterapproximations on the outage probability.The following notations are used in this chapter. We use | · | to denote magnitude ofa complex argument, and δ(·) and U(·) to represent the unit impulse and step functions.The Cartesian product of two sets is represented by (·) × (·), and defined as the set of allordered pairs whose first element is a member of the left argument, and the second elementis a member of the right argument. Moreover, ·¯ and E[·] indicate the expected value, var(·)symbolizes the variance, cov(·, ·) indicates the covariance of the two arguments, while thePDF of X is denoted by fX(·), and N (0, σ2) and CN (0, σ2) denote the normal, and complexnormal PDFs with zero mean and variance σ2. Vectors and matrices are represented by boldletters, the ith element of vector V is denoted by V(i), diag(·) is a matrix with elementson the main diagonal taken from the elements of the input vector and zeros elsewhere, andtrace(·) is a scalar obtained by adding up the elements on the main diagonal of the inputmatrix.784.1. System model(a) (b)(s)(s)(r)(r)(d)(d)(r)! (d) OFDMsubcarriers(s)! (d) OFDMsubcarriers(s)! (r) OFDMsubcarriersFigure 4.1: System model (a) First time slot (b) Second time slotThe rest of the chapter is organized as follows. In the next section, the used system modelis described. The outage probability analysis is presented in Section 4.2, and the simulationresults are provided in Section 4.3.4.1 System modelIn a wireless OFDM network operating on frequency selective channels, a source node (s)wishes to transmit data to a destination node (d) using the help of a relay node (r), allequipped with only one antenna. The total bandwidth is divided into Nsc frequency subcar-riers such that each subcarrier has a frequency flat response. The power budget at sourceis indicated by Ps, and similarly, Pr denotes the power budget available at relay. Assumingequal power distribution among all the OFDM subcarriers, psn = Ps/Nsc, prn = Pr/Nsc,where psn and prn represent the power on the nth subcarrier at (s) and (r), respectively. Weassume perfect time and frequency synchronization along with a cyclic prefix that is longenough to overcome the channel delay spread. We adopt the two time slot protocol as in[27], where source broadcasts in the first time slot to the relay and destination, and secondtime slot is dedicated to the relay to transmit the source’s data it received in the previoustime slot. The system setup is illustrated in Fig. 4.1.We define the channel impulse responses between the (s)→ (r), (r)→ (d), and (s)→ (d)794.1. System modelas hsr(τ), hrd(τ), and hsd(τ), respectively. Representing the number of channel taps on(s) → (r), (r) → (d), and (s) → (d) channels by Lsr, Lrd, and Lsd, these channels can bemathematically modeled ashsr(τ) =Lsr−1∑l=0hsr(l)δ(τ − l · Tc),hrd(τ) =Lrd−1∑l=0hrd(l)δ(τ − l · Tc),hsd(τ) =Lds−1∑l=0hsd(l)δ(τ − l · Tc), (4.1)where Tc indicates coherence time, and the channel tap coefficients are taken from the fol-lowing Lsr, Lrd and Lsd element random vectorshsr = [hsr(1) hsr(2) . . . hsr(Lsr)]T ,hrd = [hrd(1) hrd(2) . . . hrd(Lrd)]T ,hsd = [hsd(1) hsd(2) . . . hsd(Lsd)]T . (4.2)It is assumed that the channel taps on a particular physical channel are statistically indepen-dent, zero mean, and complex normally distributed RVs. Therefore, channel tap coefiicentvectors hsr, hrd, and hsd are modeled as complex normal vectors with covariance matricesΓsr, Γrd, and Γsd, as followshsr ∼ CN (0,Γsr), hrd ∼ CN (0,Γrd), hsd ∼ CN (0,Γsd), (4.3)whereΓsr = diag [var(hsr(1)). . . var(hsr(Lsr))],Γrd = diag [var(hrd(1)). . . var(hrd(Lrd))],Γsd = diag [var(hsd(1)). . . var(hsd(Lsd))]. (4.4)Having defined the channels in time domain, the Rayleigh OFDM subcarrier gains in fre-quency domain can be modeled as Nsc element vectors, which are obtained by performingNsc-point discrete Fourier transform (Nsc-DFT) on channel tap coefficient vectors,Hsr = [Hsr(1) Hsr(2) . . . Hsr(Nsc)]T = Nsc-DFT{hsr},804.1. System modelHrd = [Hrd(1) Hrd(2) . . . Hrd(Nsc)]T = Nsc-DFT{hrd},Hsd = [Hsd(1) Hsd(2) . . . Hsd(Nsc)]T = Nsc-DFT{hsd}. (4.5)The OFDM subcarrier power gain vectors on (s)→(r), (r)→(d), and (s)→(d) channels areindicated by X, Y, and Z, respectively. These random vectors are formally defined byX = [|Hsr(1)|2 . . . |Hsr(Nsc)|2],Y = [|Hrd(1)|2 . . . |Hrd(Nsc)|2],Z = [|Hsd(1)|2 . . . |Hsd(Nsc)|2]. (4.6)Here, we can deduce that elements of X, Y, and Z are exponentially distributed RVs, sincethe subcarrier gains in frequency domain are Rayleigh distributed [67]. Moreover, elements ofX are identical RVs, thus all associated with exponential parameter λsr. The same argumentholds for Y and Z and their corresponding exponential parameter λrd and λsd. Hence, theelements of X, Y and Z are taken from the following exponential distributionsfX(n)(x) = λsre−λsrx · U(x), ∀n ∈ {1, . . . , Nsc},fY(n)(y) = λrde−λrdx · U(x), ∀n ∈ {1, . . . , Nsc},fZ(n)(z) = λsde−λsdx · U(x), ∀n ∈ {1, . . . , Nsc}, (4.7)where the parameters of these exponential RVs can be obtained as followsλsr =1trace[Γsr], λrd =1trace[Γrd], λsd =1trace[Γsd]· (4.8)Furthermore, the covariances cov(X(n1),X(n2)), cov(Y(n1),Y(n2)), and cov(Z(n1),Z(n2)),can be easily obtained to be [78–80]cov(X(n1),X(n2)) =∣∣∣Lsr−1∑l=0var(hsr(l))e−jˆ2piln1−n2Nsc∣∣∣2,cov(Y(n1),Y(n2)) =∣∣∣Lrd−1∑l=0var(hrd(l))e−jˆ2piln1−n2Nsc∣∣∣2,cov(Z(n1),Z(n2)) =∣∣∣Lsd−1∑l=0var(hsd(l))e−jˆ2piln1−n2Nsc∣∣∣2, (4.9)where jˆ is the imaginary unit√−1. Furthermore, note that cov(X(n1),Y(n2)) = 0, since814.2. Outage probability analysisthey are obtained from two independent events (One represents the (s)→(r) channel, andthe other represents the (r)→(d) channel.) The same results hold for cov(X(n1),Z(n2)), andcov(Y(n1),Z(n2)).Having defined all these parameters, the capacity on the nth OFDM subcarrier is [27]C(n) =12log(1 + min{X(n)PsNscσ2r,Y(n)PrNscσ2d+ Z(n)PsNscσ2d}), (4.10)where σ2r and σ2d are noise variances at (r) and (d). Then, the total capacity isC =1NscNsc∑n=1C(n). (4.11)4.2 Outage probability analysisIn order to characterize the outage probability, the probability distribution of the totalcapacity from (4.11) is needed. As it can be observed in equation (4.11), the total capacityis a summation over subcarrier capacities (C(n)) which are identical, but correlated RVs (See(4.9) and (4.10).) If these RVs were i.i.d., the central limit theorem would assert that thetotal capacity follows a Gaussian distribution. However, although these RVs are correlated,still approximating the total capacity by a Gaussian RV seems to be practical. As a matterof fact, we have observed in our simulation results that Gaussian approximation indeedrepresents the total capacity tightly, even with small number of OFDM subcarriers such asNsc = 8.A Gaussian RV is completely characterized by its mean and variance, which are addressedin the rest of this section. In order to proceed, let us define another set of RVs asV(n) = min{X(n)PsNscσ2r,Y(n)PrNscσ2d+ Z(n)PsNscσ2d}, ∀n ∈ {1, 2, . . . , Nsc}. (4.12)Given the probability distribution functions (PDF) of X(n), Y(n), and Z(n) from (4.7), thePDF of V(n) can be obtained to befV(n)(v) =[αsd(αsr + αrdαsd − αrd)e−(αsr+αrd)v − αrd(αsr + αsdαsd − αrd)e−(αsr+αsd)v]U(v), (4.13)whereαsr =λsr ·Nscσ2rPs, αrd =λrd ·Nscσ2dPs, αsd =λsd ·Nscσ2dPs. (4.14)824.2. Outage probability analysisNote that fV(n)(v) cannot be evaluated from (4.13) if αrd = αsd, which happens rarely dueto the random nature of wireless fading channels. Besides this, by substituting (4.12) into(4.10) we haveE[C] =1NscNsc∑n=1E[C(n)] = E[C(n)]⇒ E[C] =∫ ∞012log(1 + v)fV(n)(v)dv. (4.15)And finally, by calculating the above integral, the expected value of the total capacity isE[C] =12log2(e)[e(αsr+αsd)( αrdαsd − αrd)Ei(− (αsr + αsd))− e(αsr+αrd)( αsdαsd − αrd)Ei(− (αsr + αrd))], (4.16)in which Ei(·) is the exponential integral and defined as Ei(x) =∫ x−∞exp(t)t dt [81].The next step is calculating the variance of total capacity:σ2C = E[(C − C¯)2] = E[C2]− C¯2 =1N2scNsc∑n1=1Nsc∑n2=1E[C(n1)C(n2)]− C¯2. (4.17)According to above equation, calculating E[C(n1)C(n2)] is crucial, however not quite straight-forward, considering that the joint PDF of any two OFDM subcarrier gain in (s)→(r),(r)→(d), or (s)→(d) link (e.g., |Hsr(n1)| and |Hsr(n2)|) follows a bivariate Rayleigh distri-bution (joint PDF of two correlated Rayleigh RVs) obtained in [82, 83]. Therefore, we usethe Delta method [84] to approximate the variance of total capacity.The Delta method, in summary, is a way to approximate the variance and covariance offunctions of RVs through using the Taylor series expansion up to the first degree around themean value of the RVs. To illustrate the concept, we use the Delta method to approximatethe variance of g which is a function of two random variables, t and u, with expected valuesof µt and µu, respectively. The Taylor series expansion of g(t, u) up to the first degree aroundthe expected values of the arguments isg(t, u) ≈ g(µt, µu) +∂g∂t(t− µt) +∂g∂u(u− µu), (4.18)where ∂g∂u denotes the partial derivative of function g with respect to u. Taking the variance834.2. Outage probability analysisof both sides of the above equation yieldsvar(g(t, u))≈(∂g∂t)2var(t) +(∂g∂u)2var(u) + 2∂g∂t∂g∂ucov(t, u). (4.19)Now, we apply the Delta method to approximate the variance of total capacity as followsσ2C ≈Nsc∑n1=1Nsc∑n2=1[∂C∂X(n1)∂C∂X(N2)cov(X(n1),X(n2)) (4.20)+∂C∂Y(n1)∂C∂Y(N2)cov(Y(n1),Y(n2)) +∂C∂Z(n1)∂C∂Z(N2)cov(Z(n1),Z(n2))],where ∂C∂X(n) denotes the partial derivative of total capacity C from (4.11) and (4.10) withrespect to X(n). The derivatives are evaluated at E[X(n)], E[Y(n)], and E[Z(n)], and thusgiven by∂C∂X(n)= βax1+axE[X(n)]axE[X(n)] ≤ ayE[Y(n)] + azE[Z(n)]0 otherwise, (4.21)∂C∂Y(n)= β0 axE[X(n)] ≤ ayE[Y(n)] + azE[Z(n)]ay1+ayE[Y(n)]+azE[Z(n)]otherwise,∂C∂Z(n)= β0 axE[X(n)] ≤ ayE[Y(n)] + azE[Z(n)]az1+ayE[Y(n)]+azE[Z(n)]otherwise,in whichβ =log2(e)2Nsc, ax =PsNscσ2r, ay =PrNscσ2d, az =PsNscσ2d. (4.22)By substituting (4.9) and (4.21) into (4.20), the approximation of the variance is obtained.Having obtained both the mean and variance of the total capacity in (4.16) and (4.20), thetotal capacity now can be described as C ∼ N (C¯, σ2C). Hence, the outage probability isPout = Pr[C < γ] = 1−Q(γ − C¯σC), (4.23)where γ is the threshold rate, and Q(·) is the standard Q-function. Clearly, the outagecapacity (i.e. the maximum capacity that can be supported with probability of failure equal844.2. Outage probability analysisto ) can be written asC = σCQ−1(1− ) + C¯, (4.24)where Q−1(·) is the inverse of Q-function.4.2.1 Special case: i.i.d. OFDM subcarriersIn this subsection, we address the case where the OFDM subcarrier gains are independent aswell as identical. As one possibility, this case happens when channel taps have equal fadingpowers, and the number of channel taps is equal to the number of OFDM subcarriers. Here,the central limit theorem strictly applies, and we expect the capacity to be a Gaussian RV.The mean does not change and it is given by equation (4.16). As for the variance, sincethe C(n)s are independent (i.e. E[C(n1)C(n2)] = E[C(n1)]E[C(n2)],), manipulating (4.17)results inσ2C = E[(C − C¯)2] =1Nscσ2C(n) =1Nsc(E[C(n)2]− ¯C(n)2)(4.25)Then, from equations (4.12) and (4.13) and (4.15)σ2C =1Nsc∫ ∞0(12log(1 + v))2fV(n)(v)dv −C¯2Nsc. (4.26)Calculating the above integral,σ2C =(log2(e))22Nsc[AeaG3,02,3(αsr + αrd∣∣∣∣0, 0−1,−1,−1)−BebG3,02,3(αsr + αsd∣∣∣∣0, 0−1,−1,−1)]− C¯2N(4.27)where G is Meijer G-function [81], andA = αsd(αsr + αrdαsd − αrd), a = αsr + αrd, B = αrd(αsr + αsdαsd − αrd), b = αsr + αsd. (4.28)After calculating the mean and variance of the total capacity, the probability of outage issimilarly given by (4.23).854.3. Numerical simulation results4.3 Numerical simulation resultsWe performed simulations to examine the accuracy of the analytical outage probabilityobtained in the previous section. It is assumed that all the three nodes are on a straightline where (r) node is located in the middle of (s) and (d) nodes. Furthermore, numberof channel taps on all the three channels is L, i.e., Lsr = Lrd = Lsd = L. Without loss ofgenerality, the (s)→(r) and (r)→(d) channel power delay profiles are normalized to 1, and allthe channel taps on these two channels are identical RVs, i.e., var(hsr) and var(hrd) are takenfrom CN (0, 1L). Assuming path loss exponent of 4, the (s)→(d) channel taps are taken fromCN (0, 116·L). In addition, the threshold rate is assumed to be γ = 1 bit/s/Hz, the number ofOFDM subcarriers is Nsc = 32, noise variances σ2r and σ2d are set to 1, and the SNR is thetransmit SNR per OFDM subcarrier.Fig. 4.2 and Fig. 4.3 show the analytical and simulated outage probability versus SNRassuming equal power budgets at (s) and (r) (Pr = Ps), and reduced power budget at (r)(Pr = 0.1 · Ps), respectively. Results for different number of channel taps are illustrated. Asit can be seen, the outage probability obtained by our analysis and simulation are almostidentical in all the cases, demonstrating the precision of our analysis. Moreover, in bothfigures, the lowest curves correspond to the special case of i.i.d. OFDM subcarrier powergains, where the numerically evaluated and analytical results precisely agree. This is becausethe exact variance obtained in (4.27) is used to evaluate the outage probability. We alsoobserve that by increasing the number of channel taps the outage performance improves,which is the result of a better frequency diversity. Another fact that stands out by comparingFig. 4.2 and Fig. 4.3 is that when the power budget at (r) node is reduced, the outageperformance drops. Intuitively, by reducing the power budget at (r), lower levels of overallpower are available, which translates into lower SNRs, and worse probabilities of outage.864.3. Numerical simulation results0 5 10 15 20 25 SNR[dB]Probability of Outage10−1410−1210−1010−810−610−410−210−0 L=4 analyticalL=4 simulatedL=6 analyticalL=6 simulatedL=8 analyticalL=8 simulatedi.i.d. analyticali.i.d. simulatedFigure 4.2: Outage probability against transmitted SNR when PR = PS for L = 4, 6, 8 andi.i.d. subcarriers874.3. Numerical simulation results0 5 10 15 20 25 SNR[dB]Probability of Outage10−1410−1210−1010−810−610−410−210−0 L=4 analyticalL=4 simulatedL=6 analyticalL=6 simulatedL=8 analyticalL=8 simulatedi.i.d. analyticali.i.d. simulatedFigure 4.3: Outage probability against transmitted SNR when PR = 0.1 · PS for L = 4, 6, 8and i.i.d. subcarriers88Chapter 5Outage Probability Analysis forMulti-User Single-Relay OFDMADecode-and-Forward Networks inFrequency Selective Rayleigh FadingChannelsThis chapter is an extension to Chapter 4. In this chapter, we study an uplink multi-user single-relay DF OFDMA system, where a Rayleigh frequency selective channel modelis adopted. We provide analytical approximations for the global outage probability in thesense that the outage event occurs when at least one link goes into outage.In calculating the global outage probability of a multi-user single-relay OFDMA DFnetwork, the contributions of this chapter are:• Realizing that the link capacities are correlated RVs. The statistical correlation be-tween the link capacities is created by the relay-destination channel that is commonto all the links.• Fitting a multi-variate normal distribution to the link capacities and characterizingthe parameters of the fitted distribution.• Proposing a method to approximate the correlation among link capacities.• Obtaining the global outage probability in which the correlation of the link capacities,correlation between OFDM subcarriers, and arbitrary number of bits on each OFDMsubcarrier are considered.Before proceeding further, the used notations in this chapter are clarified. We use | · |to denote magnitude of a complex argument, and δ(·) to represent unit impulse function.Vectors are represented by −→· and matrices by bold letters, the ith element of vector −→V895.1. System model1s R Dis ssN(a) (b)O F D M s u b c a r r i e r sw i t h s u b c a r r i e r sw i t h s u b c a r r i e r sw i t h s u b c a r r i e r sNscNsc OFDM subcar rs1 with N1subcarriersi ith NisubcarriersSSiS SNS wit NNSsubcarriersFigure 5.1: System model (a) System configuration (b) OFDMA setupis denoted by−→V (i), diag(−→· ) is a matrix with elements on the main diagonal taken fromthe elements of the input vector and zeros elsewhere, and trace(·) is a scalar obtained byadding up the elements on the main diagonal of the input matrix. Besides, E[·] symbolizesthe expected value, var(·) indicates the variance, cov(·, ·) indicates the covariance betweenthe two arguments, while N (−→µ ,Q) and CN (−→µ ,Q) denote the multi-variate normal, andcomplex normal PDFs with mean vector −→µ and covariance matrix Q. Finally, G(−→γ ,−→µ ,Q)represents the multi-variate normal CDF, which is the probability of a set of jointly normaldistributed RVs with mean vector −→µ and covariance matrix Q being less than the elementsof vector −→γ .The rest of the chapter is organized as follows. The system model is described in the nextsection. The global outage probability analysis is presented in Section 5.2. Simulation resultsare provided in Section 5.3 to verify the validity of our proposed global outage analysis.5.1 System modelIn an uplink cooperative configuration, where the wireless channels suffer from Rayleighmulti-path fading, NS sources (Si, i ∈ {1, . . . , NS}) are to communicate with one destination905.1. System model(D) through a single relay (R). In order to combat multi-path fading, OFDMA arrangementwith Nsc available subcarriers is adopted, where these subcarriers are partitioned into NSnon-overlapping and not necessarily adjacent subcarrier subsets (φi, i ∈ {1, . . . , NS}), eachwith Nφi subcarriers (i.e.,∑NSi=1Nφi = Nsc). Each subcarrier subset φi is assigned to asingle source Si, or equivalently to a single Si-R-D link, to establish NS links in frequencydomain. The R operates under the well-known two time slot DF scheme. In the 1st time slot,sources Si broadcast on their assigned subcarrier subsets φi, each with a power budget ofPSi , spreading their budgets evenly among their available subcarriers (i.e., source Si allocatesPSi/Nφi to its available subcarriers). Then, the 2nd time slot follows where R decodes themessages, re-encodes them, and forwards the messages of each source Si on its allocatedsubcarrier subset φi. R also allocates its power budget equally among all the subcarriers,putting PR/Nsc on each subcarrier. The system model and the OFDMA setup is illustratedin Fig. 5.1. The line of sight between the source and destination is not shown in Fig. 5.1, notto impair the readability of the figure. Also, as an illustrative example, assume that thereare 2 sources and 4 available OFDM subcarriers. Let us say subcarriers 1 and 3 are allocatedto S1, and subcarriers 2 and 4 are given to S2. In other words, φ1 = {1, 3}, and φ2 = {2, 4}.In the 1st time slot, S1 transmits its OFDM symbols on 1st and 3rd subcarriers, while S2transmits on 2nd and 4th, both distributing their powers equally among the two subcarriersallocated to them. In the 2nd time slot, R decodes the information on 1st and 3rd subcarriersas S1’s information, and re-encodes them and relays them on the same subcarriers in φ1.The relay treats the information received from S2 in the same manner and forwards themon φ2. The power allocated to all the 4 subcarriers at R are also equal.Indicating by Tc the coherence time, the channel tap vectors on r-t channels by−→h rt,and the number of channel taps in these vectors by Lrt, the Rayleigh faded channels in ournetwork are represented ashSiR(τ) =LSiR−1∑l=0−→h SiR(l)δ(τ − lTc), (5.1)hRD(τ) =LRD−1∑l=0−→h RD(l)δ(τ − lTc), (5.2)hSiD(τ) =LSiD−1∑l=0−→h SiD(l)δ(τ − lTc). (5.3)The channel tap vectors are modelled as zero mean complex normal vectors with covariancematrices ΓSiR, ΓRD, and ΓSiD. ΓSiR, ΓRD, and ΓSiD have non-zero elements only on the main915.1. System modeldiagonal which indicates the statistical independence of the channel taps on each physicalchannel:−→h SiR ∼ CN (0,ΓSiR),−→h RD ∼ CN (0,ΓRD),−→h SiD ∼ CN (0,ΓSiD), (5.4)andΓSiR = diag [var(−→h SiR(1)). . . var(−→h SiR(LSiR))],ΓRD = diag [var(−→h RD(1)). . . var(−→h RD(LRD))],ΓSiD = diag [var(−→h SiD(1)). . . var(−→h SiD(LSiD))], (5.5)The OFDM subcarrier gains in the frequency domain are related to time domain channeltap vectors through Nsc point discrete Fourier transform (Nsc- DFT), thus we have−→H SiR = [−→H SiR(1), . . . ,−→H SiR(Nsc)] = Nsc- DFT{−→h SiR},−→HRD = [−→HRD(1), . . . ,−→HRD)] = Nsc- DFT{−→h RD},−→H SiD = [−→H SiD(1), . . . ,−→H SiD(Nsc)] = Nsc- DFT{−→h SiD}, (5.6)and in turn, the Nsc element OFDM subcarrier power gain vectors on Si-R, R-D, and Si-Dphysical channels are4−→X i = [|−→H SiR(1)|2, . . . , |−→H SiR(Nsc)|2],−→Y = [|−→HRD(1)|2, . . . , |−→HRD(Nsc)|2],−→Z i = [|−→H SiD(1)|2, . . . , |−→H SiD(Nsc)|2]. (5.7)It can easily be shown that all the subcarrier power gains on a given physical channel (e.g.,−→X i(n), n ∈ {1, . . . , Nsc}) are identical exponentially distributed RVs. Thus, we associate allthe elements in−→X i with exponential distribution parameter λSiR, elements of−→Y with λRD,4In this chapter, where not indicated, indices i can take any value in {1, . . . , NS}, indices n, n1, and n2refer to OFDM subcarriers, and can take values in {1, . . . , Nsc}.925.1. System modeland elements of−→Z i with λSiD. The exponential distribution parameters are calculated to beλSiR =1trace[ΓSiR], λRD =1trace[ΓRD], λSiD =1trace[ΓSiD]. (5.8)We represent cov(−→X i(n1),−→X i(n2)), cov(−→Y (n1),−→Y (n2)), and cov(−→Z i(n1),−→Z i(n2)), byΘ−→X i(n1, n2),Θ−→Y (n1, n2), and Θ−→Z i(n1, n2), respectively. Due to the random nature of wirelesschannels, OFDM subcarrier power gains on separate physical channels are statistically inde-pendent (e.g., cov(−→X i(n1),−→Y (n2))= 0, or cov(−→X i(n1),−→X j(n2))= 0 for i 6= j). However,the OFDM subcarrier gains on a specific physical channel are correlated as follows [78]Θ−→X i(n1, n2) =∣∣∣LSiR−1∑l=0var(−→h SiR(l))e−jˆ2piln1−n2Nsc∣∣∣2,Θ−→Y (n1, n2) =∣∣∣LRD−1∑l=0var(−→h RD(l))e−jˆ2piln1−n2Nsc∣∣∣2,Θ−→Z i(n1, n2) =∣∣∣LSiD−1∑l=0var(−→h SiD(l))e−jˆ2piln1−n2Nsc∣∣∣2, (5.9)where jˆ is the imaginary unit√−1.Furthermore, by requiring the relay to fully decode the messages, the capacity of theSi-R-D link on the nth OFDM subcarrier, where n ∈ φi is [27]Ci(n) =12log(1 + min{−→X i(n)PSiNφiσ2R,−→Y (n)PRNscσ2D+−→Z i(n)PSiNφiσ2D}), n ∈ φi, (5.10)where σ2R and σ2D are the noise variances at R and D, respectively. The overall capacity ofSi-R-D is obtained by summing the capacities on the subcarriers in φi:Ci =1Nφi∑n∈φiCi(n). (5.11)Coming back to our illustrative example, C1 = 0.5[C1(1) + C1(3)], and C2 = 0.5[C2(2) +C2(4)]. Note that C1 is a function of−→X 1(1),−→X 1(3),−→Z 1(1),−→Z 1(3),−→Y (1), and−→Y (3), whileC2 is a function of−→X 2(2),−→X 2(4),−→Z 2(2),−→Z 2(4),−→Y (2), and−→Y (4). According to the secondequation in (5.9),−→Y (1) and−→Y (3) are correlated with−→Y (2) and−→Y (4), thus C1 and C2 arealso correlated RVs.We indicate the outage probability of a single link Si-R-D by Pout(i) and define it as the935.2. Global outage probabilityprobability of the event where the capacity of the link drops below a certain threshold γi :Pout(i) = Pr[Ci < γi]. (5.12)Finally, the global outage event is defined as the case where at least one link goes into outage.We indicate the probability of this event by P̂out and mathematically define it asP̂out = Pr[C1 < γ1 or . . . Ci < γi or . . . CNS < γNS ]. (5.13)The purpose of this chapter is to characterize P̂out.5.2 Global outage probabilityIn Chapter 4, a tight approximation for the Si-R-D link outage probability defined in (5.12)is provided by fitting a normal probability distribution to the link capacity given in (5.11).The approximation is based on the fact that the link capacity is a summation over OFDMsubcarrier capacities given in (5.10), which are identical but correlated RVs through (5.9). Ifthese RVs were also statistically independent, central limit theorem would readily yield theGaussian distribution to the link capacity. However, regardless of the existing correlation,the central limit theorem has been applied and a tight approximation has been resulted.On the other hand, if the link capacities were statistically independent, one could easilyshow thatP̂out = 1−NS∏i=1(1− Pout(i)). (5.14)However, the link capacities are also correlated RVs through the correlation of the OFDMsubcarriers on the R-D channel. The information received at R from Sis on independent chan-nels is transmitted on a common physical channel to D, and the nonzero cov(−→Y (n1),−→Y (n2))makes Cis correlated. In order to tackle this issue, we approximate the joint probability dis-tribution of Cis by a multi-variate normal distribution. To fully represent a multi-variatenormal distribution, obtaining the mean vector −→µ NS and the covariance matrix QNS×NS aresufficient. The elements of −→µ NS which are the mean values of link capacities are obtained inChapter 4 as follows−→µ NS(i) = E[Ci] =12log2(e)[e(αSiR+αSiD)( αRDαSiD − αRD)Ei(− (αSiR + αSiD))945.2. Global outage probability− e(αSiR+αRD)( αSiDαSiD − αRD)Ei(− (αSiR + αRD))], (5.15)where Ei(·) is the exponential integral and defined as Ei(x) =∫ x−∞exp(t)t dt [81], andαSiR =λSiRNφiσ2RPSi, αRD =λRDNscσ2DPR, αSiD =λSiDNφiσ2DPSi. (5.16)The elements on the main diagonal of QNS×NS which are the variances of Cis are also calcu-lated in Chapter 4. The Delta method [84] is used to approximate the variance of the linkcapacities, due to non-existence of closed form solution for the variances. After the necessarymodifications, the main diagonal elements of QNS×NS areQNS×NS(i, i) = σ2Ci ≈∑n1∈φi∑n2∈φi[∂Ci∂−→X i(n1)∂Ci∂−→X i(n2)Θ−→X i(n1, n2) (5.17)+∂Ci∂−→Y (n1)∂Ci∂−→Y (n2)Θ−→Y (n1, n2) (5.18)+∂Ci∂−→Z i(n1)∂Ci∂−→Z i(n2)Θ−→Z i(n1, n2)], (5.19)where ∂Ci∂−→X i(n), ∂Ci∂−→Y (n), and ∂Ci∂−→Z i(n1)denote the partial derivatives of the link capacity Ci from(5.11) and (5.10) with respect to−→X i(n),−→Y (n) and−→Z i(n), respectively, and these derivativesare evaluated at E[−→X i(n)], E[−→Y (n)], and E[−→Z i(n)] as the following∂Ci∂−→X i(n)= βax,i1+ax,iE[−→X i(n)]ax,iE[−→X i(n)] ≤ ayE[−→Y (n)] + az,iE[−→Z i(n)]0 otherwise, (5.20)∂Ci∂−→Y (n)= β0 ax,iE[−→X i(n)] ≤ ayE[−→Y (n)] + az,iE[−→Z i(n)]ay1+ayE[−→Y (n)]+az,iE[−→Z i(n)]otherwise,∂Ci∂−→Z i(n)= β0 ax,iE[−→X i(n)] ≤ ayE[−→Y (n)] + az,iE[−→Z i(n)]az,i1+ayE[−→Y (n)]+az,iE[−→Z i(n)]otherwise,andβ =log2(e)2Nφi, ax,i =PSiNφiσ2R, ay =PRNscσ2D, az,i =PSiNφiσ2D. (5.21)955.3. Numerical simulation resultsThe rest of the elements of QNS×NS which represent the covariance between Ci and Cjfor i 6= j are also challenging to calculate. Therefore, we again use the Delta method toapproximate these elements:QNS×NS(i, j) = E[(Ci−−→µ NS(i))(Cj−−→µ NS(j))] ≈∑n1∈φi∑n2∈φj[∂Ci∂−→Y (n1)∂Cj∂−→Y (n2)Θ−→Y (n1, n2)].(5.22)Note that in (5.22), only the covariance between the R-D OFDM subcarriers are taken intoaccount, and in (5.17), all the channels are considered. This is because the correlationbetween the link capacities is caused only by the common channel between R and D.Now, defining the NS element threshold vector−→γ NS as −→γ NS = [γ1, . . . , γNS ], the globalprobability of outage isP̂out =∑i1Pout(i1)−∑i1,i2,i1 6=i2T2(i1, i2) + . . .+ (−1)m+1∑i1,...,im,i1 6=i2 6=···6=imTm(i1, . . . , im) + . . .+ (−1)NS+1G(−→γ NS ,−→µ NS ,QNS×NS), (5.23)where all the indices im can take values in {1, . . . , NS}, andTm(i1, . . . , im) = G(−→γ m(i1, . . . , im),−→µ m(i1, . . . , im),Qm×m(i1, . . . , im)). (5.24)In the above equation, −→γ m(i1, . . . , im) and −→µ m(i1, . . . , im) are m element vectors obtainedby removing all the elements except the i1, . . . , im elements from−→γ NS and −→µ NS , respectively,and Qm×m(i1, . . . , im) is an m×m element covariance matrix obtained by removing all therows and columns except the i1, . . . im rows and columns from QNS×NS . As an example, forthe the case of NS = 2 we haveP̂out = Pout(1) + Pout(2)−G(−→γ 2,−→µ 2,Q2×2). (5.25)5.3 Numerical simulation resultsIn this section, we examine the accuracy of our global outage analysis against Monte Carlosimulation. In our simulations, we have considered three cases of NS = 2, 3 and 4, underequal power budgets at the sources and the relay, and a reduced power budget at the relay965.3. Numerical simulation results0 5 10 15 20 2500.10.20.30.40.50.60.70.80.91SNR[dB]Global Probability of Outage NS=2 AnalyticalNS=2 SimulatedNS=3 AnalyticalNS=3 SimulatedNS=4 AnalyticalNS=4 SimulatedFigure 5.2: Global outage probability against transmitted SNR when PR = PS for NS =2, 3, 4by a factor of 10, in Fig. 5.2 and Fig. 5.3, respectively. The number of channel taps onall the links is set to 4. It is assumed that the Si-R distances and the R-D distance are allequal, and the variance of channel taps is set to 1/4 so that the channel powers on Si-R andR-D channels are normalized to 1. The sources are uniformly located on 1/3 arc of a circlewith R at the center and radius of the R-D distance, farthest from the D. Assuming the pathloss exponent of 4, the Si-D channel powers are scaled by the ratio of Si-D distance to Si-Rdistance to the power of 4. It is also assumed that each source is given 16 adjacent OFDMsubcarriers. The noise variances at R and D are set to 1.As it can be seen in both figures, the analytical solution to the global outage probabilityclosely matches the simulated results in all cases. It can also be seen that increasing thenumber of sources worsens the probability of outage. This is because the outage occurswhen at least one link goes into outage, and increasing the number of links increases thelikelihood of this event. By comparing Fig. 5.2 and Fig. 5.3, it is apparent that the outage975.3. Numerical simulation results8 10 12 14 16 18 20 22 2400.10.20.30.40.50.60.70.80.91SNR[dB]Global Probability of Outage NS=2 AnalyticalNS=2 SimulatedNS=3 AnalyticalNS=3 SimulatedNS=4 AnalyticalNS=4 SimulatedFigure 5.3: Global outage probability against transmitted SNR when PR = 0.1 · PS forNS = 2, 3, 4performance is better when the power budgets at the sources and the relay are equal. Thistrend is expected because reducing the power budget at the relay decreases the SNR levelsin the network, which in turn decreases the link capacities and increases the likelihood ofthese capacities dropping below a threshold.98Chapter 6Outage Analysis and Relay Allocationfor Multi-Stream OFDMADecode-and-Forward Rayleigh FadingNetworksIn this chapter, we study a clustered OFDMA two-hop DF network consisting of a set ofsource-destination pairs, and a cluster of relays. We consider the case of no LOS betweensource cluster and the destination cluster, and it is assumed that individual source-relay andrelay-destination channels suffer from Rayleigh frequency selective fading. The contributionsof this chapter are summarized in the following:• The global outage probability of described networks is approximated assuming corre-lated OFDM subcarrier gains on individual source-relay and relay-destination channelsalong with the freedom of allocating arbitrary number of bits to each OFDM subcar-rier. The global outage event is defined as the event where at least one source-relay-destination link goes into outage.• It is also shown that the outage probability on a single source-relay-destination linkdoes not depend on the choice of OFDMA subcarrier subset as long as there is equalnumber of subcarriers in each subset and a given subset is formed from contiguoussubcarriers in the frequency domain.• The problem of relay allocation to minimizing the obtained global outage probabilityis formulated and it is shown it can be converted to a standard assignment problem.Then, a novel and low complexity centralized relay allocation scheme based on Hun-garian method is proposed to minimize the global outage probability. The proposedrelay allocation scheme is based on knowing only some statistical characteristics of thechannel, as opposed to high complexity methods based on having access to full channelstate information.996.1. System modelBefore proceeding further, some notations used in this chapter are clarified. We use | · |to denote magnitude of a complex argument, and δ(·) and U(·) to represent the unit impulseand step functions. The Cartesian product of two sets is represented by (·)× (·), and definedas the set of all ordered pairs whose first element is a member of the left argument, andthe second element is a member of the right argument. Moreover, ·¯ and E[·] indicate theexpected value, var(·) symbolizes the variance, cov(·, ·) indicates the covariance of the twoarguments, while the PDF of X is denoted by fX(·), and N (0, σ2) and CN (0, σ2) denote thenormal, and complex normal PDFs with zero mean and variance σ2. Vectors and matricesare represented by bold letters, the ith element of vector V is denoted by V(i), diag(·) is amatrix with elements on the main diagonal taken from the elements of the input vector andzeros elsewhere, and trace(·) is a scalar obtained by adding up the elements on the maindiagonal of the input matrix.The rest of this chapter is organized as follows. In the following section, the systemmodel is defined. In Section 6.2, The outage probability of a single source-destination streamthrough a relay is obtained. Then, in Section 6.3, we characterize the global probability ofoutage and propose our relay allocation scheme. The performance of our proposed methodis examined through numerical simulations in Section 6.4.6.1 System modelIn a Rayleigh frequency selective wireless environment, Ns sources (si, i ∈ {1, . . . , Ns})wish to communicate to their intended destinations (di, i ∈ {1, . . . , Ns}), establishing Nssource-destination pairs, using the help of Nr relays (rj, j ∈ {1, . . . , Nr}) in between, asshown in Fig. 6.1. Each relay can support only one si-di pair, i.e., at least Ns relays areneeded to support all si-di pairs. It is assumed that there is no LOS between sources anddestinations, and all the nodes are half-duplex, capable of only transmitting or receivingdata at a specific time and frequency band. Therefore, a two time slot OFDMA schemeis employed. The frequency band consisting of Nsc flat faded OFDM subcarriers is dividedinto M non-overlapping subsets of subcarriers {φ1, . . . , φM}, each formed from Nφ contiguousOFDM subcarriers (i.e., M · Nφ = Nsc)5. These OFDMA subcarrier subsets are allocatedto si-di pairs, one to each pair, in order to realize more than one si-di pair at a time. Inthe first time slot, the sources transmit on their allocated OFDMA subset, and relays listen.5In this chapter, all indices i refer to sources, and to be more precise, source-destination pairs, all indicesj refer to relays, and indices n, n1, and n2 refer to the OFDM subcarriers. Where not indicated, indices iand j can take any value in {1, . . . , Ns} and {1, . . . , Nr}, respectively, while n, n1, and n2 can take values in{1, . . . , Nsc}.1006.1. System model1s 1rjr 1d idsdNis ssN rrN scN(a) (b)O F D M s u b c a r r i e r s1w i t h s u b c a r r i e r sMw i t h s u b c a r r i e r smw i t h Ns u b c a r r i e r sN NFigure 6.1: System model (a) System configuration (b) OFDMA setupAssuming that one relay is allocated to each source, in the second time slot, the relaysretransmit the information on the allocated OFDMA subset to the destinations under DFprotocol. We also assume perfect time and frequency synchronization along with a cyclicprefix that is long enough to overcome the channel delay spread.There are 2 · Ns · Nr physical channels in this system, Ns · Nr channels between sourcesand relays, and Ns · Nr channels between relays and destinations, where all these channelsare statistically independent, due to the random nature of multi-paths fading in wirelesschannels. Indicating by Lsirj and Lrjdi the number of channel taps on si-rj and rj-di channels,respectively, the channel impulse responses arehsirj(τ) =Lsirj−1∑l=0hsirj(l)δ(τ − l · Tc),hrjdi(τ) =Lrjdi−1∑l=0hrjdi(l)δ(τ − l · Tc), (6.1)where Tc indicates the coherence time, and the channel tap coefficients are taken from the1016.1. System modelfollowing Lsirj and Lrjdi element random vectorshsirj = [hsirj(1) hsirj(2) . . . hsirj(Lsirj)]T ,hrjdi = [hrjdi(1) hrjdi(2) . . . hrjdi(Lrjdi)]T . (6.2)It is assumed that the channel tap coefficients on a given physical channel are statisticallyindependent, zero mean, and complex normally distributed RVs. Therefore, channel tapcoefficient vectors, hsirj and hrjdi , are modelled as complex normal vectors with covariancematrices Γsirj and Γrjdi , as followshsirj ∼ CN (0,Γsirj) , hrjdi ∼ CN (0,Γrjdi), (6.3)whereΓsirj = diag [var(hsirj(1)). . . var(hsirj(Lsirj))],Γrjdi = diag [var(hrjdi(1)). . . var(hrjdi(Lrjdi))]. (6.4)Having defined the channels in time domain, the Rayleigh OFDM subcarrier gains can bemodelled as Nsc element vectors, which are obtained by performing Nsc-point Discrete FourierTransform (Nsc- DFT) on channel tap coefficient vectors,Hsirj = [Hsirj(1), . . . ,Hsirj(Nsc)] = Nsc- DFT{hsirj},Hrjdi = [Hrjdi(1), . . . ,Hrjdi(Nsc)] = Nsc- DFT{hrjdi}. (6.5)The channel power gain vectors on si-rj and rj-di channels are represented by Xij and Yji,respectively. These two Nsc element vectors are formally defined asXij = [|Hsirj(1)|2, . . . , |Hsirj(Nsc)|2],Yji = [|Hrjdi(1)|2, . . . , |Hrjdi(Nsc)|2]. (6.6)Here, we can deduce that the elements of Xij are exponentially distributed, since the channelgains in frequency are Rayleigh distributed. Moreover, elements of Xij for a specific i and jare identical RVs, thus all associated with exponential parameter λsirj . The same argumentshold for Yji, its elements, and λrjdi . Hence, the elements of Xij and Yji are taken from thefollowing distributionsfXij(n)(x) = λsirje−(λsirj )x · U(x), ∀n ∈ {1, . . . , Nsc},1026.1. System modelfYij(n)(y) = λrjdie−(λrjdi )y · U(y), ∀n ∈ {1, . . . , Nsc}, (6.7)where the exponential distribution parameters are obtained to beλsirj =1trace[Γsirj ], λrjdi =1trace[Γrjdi ]· (6.8)Furthermore, denoting by ΘXsirj (n1, n2) and ΘYrjdi (n1, n2) the cov(Xij(n1),Xij(n2))andcov(Yji(n1),Yji(n2)), respectively, they easily can be obtained to be [78]ΘXsirj (n1, n2) =∣∣∣Lsirj−1∑l=0var(hsirj(l))e−jˆ2piln1−n2Nsc∣∣∣2,ΘYrjdi (n1, n2) =∣∣∣Lrjdi−1∑l=0var(hrjdi(l))e−jˆ2piln1−n2Nsc∣∣∣2, (6.9)where jˆ is the imaginary unit√−1. It should be noted that cov(Xij(n1),Xi´j´(n2))= 0 if i 6= i´or j 6= j´, because in this case, the arguments of cov(., .) are obtained from two independentevents. Following the same reasoning, it is trivial that cov(Xij(n1),Yi´j´(n2))= 0 for all(i, j) ∈ {1, . . . , Ns} × {1, . . . , Nr} and (´i, j´) ∈ {1, . . . , Ns} × {1, . . . , Nr}.Now, let us assume that si with power budget of Psi wants to transmit its information to diusing the help of rj with power budget of Prj . Further, let us assume that this communicationis taking place through mth OFDMA subcarrier set, i.e., si and rj are allowed to use OFDMsubcarriers n ∈ φm. Also, si and rj equally distribute their power budget among their Nφavailable OFDM subcarriers, allocating PsiNφ andPrjNφto each subcarrier in φm, respectively.Having defined these parameters, the capacity of si-rj-di link on the nth OFDM subcarrier,where n ∈ φm, is [27]Cij(n) =12log(1 + min{Xij(n)PsiNφσ2r,Yji(n)PrjNφσ2d}), n ∈ φm, (6.10)where σ2r and σ2d are noise variances at relays and destinations, respectively. Finally, theoverall capacity of si-rj-di link through φm isCmij =1NφmNφ∑n=(m−1)Nφ+1Cij(n). (6.11)In this chapter, the eventual goal is to allocate relays to si-di pairs such that the globaloutage probability of the system is minimized. Hence, obtaining the global outage probability1036.2. Outage probability of a single source-relay-destination linkas the main objective function is one of the crucial steps. On the way to achieving thispurpose, evaluating the outage probability of a single si-rj-di link through φm is of higherpriority. We denote this probability by Pmout(i, j), and analyze it in the next section. Then,in Section 6.3, we formulate the overall outage probability minimization problem throughrelay allocation and propose our solution.6.2 Outage probability of a singlesource-relay-destination linkIn Chapter 4, we have presented an analysis to obtain the outage probability of an OFDM DFrelay system, consisting of one source, one relay, and one destination, in which LOS betweensource and destination is also present. By modifying the system model in Chapter 4 byremoving the LOS and allowing the active nodes to use only a subset of available OFDMsubcarriers, Pmout(i, j) can be characterized. The outline of deriving Pmout(i, j) is describedhere.The event of outage on si-rj-di link occurs if the link’s capacity from (6.11) drops belowa certain threshold γiPmout(i, j) = Pr[Cmij < γi]. (6.12)In order to find Pr[Cmij < γi], the PDF of Cmij is required. According to (6.11) and (6.10),the link capacity Cmij is a summation over identical RVs Cmij (n), where n ∈ φm. If these RVswere statistically independent, the link capacity would be expected to follow a Gaussian PDFaccording to the central limit theorem. But, although the RVs Cmij (n) are correlated through(6.9), still the link’s capacity approximately follows the normal distribution. On the otherhand, to fully characterize a normal RV, calculating the mean and variance is adequate.As for the mean of Cmij , we introduce the following set of RVsVij(n) = min{Xij(n)PsiNφσ2r,Yji(n)PrjNφσ2d},∀n ∈ φm. (6.13)Given the PDFs of Xij(n) and Yji(n) in (6.7), the PDF of the above RVs is calculated to befVij(n)(v) = (αsirj + αsirj)e−(αsirj+αrjsi )v · U(v), (6.14)1046.2. Outage probability of a single source-relay-destination linkwhereαsirj =λsirj ·Nφσ2rPsi, αrjdi =λrjdi ·Nφσ2dPrj· (6.15)By substituting (6.13) into (6.10) we haveE[Cmij ] =1NφmNφ∑n=(m−1)Nφ+1E[Cij(n)] = E[Cij(n)] =∫ ∞012log(1 + v)fVij(n)(v)dv. (6.16)Finally, by calculating the above integral, the mean of Cmij isE[Cmij ] =− log2(e)2e(αsirj+αrjsi )Ei(− (αsirj + αrjsi)), (6.17)in which Ei(·) is the exponential integral and defined as Ei(x) =∫ x−∞exp(t)t dt [81]. Note thatE[Cmij ] is independent of m and n, i.e., choice of φm does not change the mean of a link’scapacity.Considering that the joint PDF of any two OFDM subcarrier gains |Hsirj(n1)| and|Hsirj(n2)|, or |Hrjdi(n1)| and |Hrjdi(n2)|, follows a bivariate Rayleigh distribution [82, 83],obtaining a solution in closed form to the variance of Cmij is not straight-forward. Therefore,we use the delta method [84] to estimate the variance as followsσ2Cmij ≈∑n1∈φm∑n2∈φm[∂Cmij∂Xij(n1)∂Cmij∂Xij(n2)ΘXij(n1, n2) +∂Cmij∂Yji(n1)∂Cmij∂Yji(n2)ΘYji(n1, n2)],(6.18)where∂Cmij∂Xij(n)and∂Cmij∂Yji(n)denote the partial derivatives of link’s capacity Cmij from (6.11) and(6.10) with respect to Xij(n) and Yji(n). The derivatives are evaluated at E[Xij(n)] andE[Yji(n)] as the following∂Cmij∂Xij(n)= βax,i1+ax,iE[Xij(n)]ax,iE[Xij(n)] ≤ ay,jE[Yji(n)]0 otherwise, (6.19)∂Cmij∂Yji(n)= β0 ax,iE[Xij(n)] ≤ ay,jE[Yji(n)]ay,j1+ay,jE[Yji(n)]otherwise,1056.3. Problem formulation and proposed relay allocation schemeandβ =log2(e)2Nφ, ax,i =PsiNφσ2r, ay,j =PrjNφσ2d. (6.20)Inspecting (6.18), it is observed that σ2Cmij is also independent of φm. This is becauseaccording to (6.9), ΘXij(n1, n2) and ΘYji(n1, n2) are functions of OFDM subcarrier spacingn1 − n2. In other words, as long as there is equal number of OFDM subcarriers in eachsubset φm, and these subcarriers are contiguous, choice of φm does not change the meanand variance of link’s capacity. Moreover, since the link’s capacity is modeled as a normalRV which is fully represented by its mean and variance, choice of φm does not affect link’scapacity Cmij , either. Therefore, we omit the index m from Cmij and Pmout(i, j), and replacethem by Cij and Pout(i, j), respectively.Having obtained the mean and variance of Cij in (6.17) and (6.18), the outage probabilityon the si-rj-di link isPout(i, j) = Pr[Cij < γi] = 1−Q(γi − C¯ijσCij), (6.21)in which Q(·) is the standard Q-function.6.3 Problem formulation and proposed relayallocation schemeIn this section, the problem of relay allocation for minimizing the global outage probabilityis formally stated, and a solution based on Hungarian method is proposed. We say themulti-stream system introduced in Section 6.1 is in outage if at least one of the Ns si-dilinks is in outage. In order to obtain an expression for the global outage probability Pout,we introduce relay assignment indices ρij ∈ {0, 1}. The relay j is assigned to si-di pair ifand only if ρij = 1. Moreover, ρij = 1 implies that ρi´j´ = 0 if i 6= i´ or j 6= j´, because a relaycan help at most one si-di pair. Following this definition, and considering the fact that theevents of outage on single si-rj-di links are statistically independent, the probability thatnone of the si-di pairs is in outage can be written in the form of1− Pout =Ns∏i=1Nr∏j=1(1− Pout(i, j))ρij , (6.22)1066.3. Problem formulation and proposed relay allocation schemein which Pout(i, j) is the outage probability on a single si-rj-di link through any of theM OFDMA subcarrier subsets φm, and this probability has been analyzed in Section 6.2.Finally, we are seeking a solution for the following optimization problemminρij1−Ns∏i=1Nr∏j=1(1− Pout(i, j))ρij (6.23)subject to (s.t.)Ns∑i=1ρij ≤ 1, ∀j ∈ {1, . . . , Nr}, (6.24)Nr∑j=1ρij ≤ 1, ∀i ∈ {1, . . . , Ns}, (6.25)ρij ∈ {0, 1},∀(i, j) ∈ {1, . . . , Ns} × {1, . . . , Nr}. (6.26)In this optimization problem, the objective function (6.23) is the global probability of outage,and constraints (6.24), (6.25) and (6.26) guarantee that each relay is at most assigned toone si-di pair. Further, by removing the constant term in (21) and taking the logarithm ofthe right hand side, the optimization problem (6.23)-(6.26) is transformed into the followingoptimization problemmaxρijNs∑i=1Nr∑j=1ρij log(1− Pout(i, j))(6.27)s.t. (6.24), (6.25) and (6.26), (6.28)The above optimization problem is a standard 2-dimensional assignment problem [85]. Toillustrate the nature of this problem, a gain matrix A is introduced, where the elements ofthis matrix areAij = log(1− Pout(i, j)), ∀(i, j) ∈ {1, . . . , Ns} × {1, . . . , Nr}. (6.29)These elements are interpreted as the gain achieved by assigning rj to si-di pair. Now, theproblem of finding ρij such that (6.23) is minimized is reduced to selecting Ns elements fromA, such that only one element is selected from each row and column, and the summationof these elements is maximized. In other words, if Aij is selected, then ρij = 1, and ρij = 0otherwise. This problem can be solved optimally by adopting the Hungarian method [85]with the complexity of O(max(Ns, Nr)3). Forming the gain matrix A requires Ns × Nrcalculations, giving the complexity of O(Ns × Nr); thus, the complexity of our proposedsolution is dominated by the Hungarian method.1076.4. Numerical simulation resultsThe proposed algorithm of relay allocation for minimizing the global outage probabilityis briefly described here. Given the statistical properties of the channel impulse responsesbetween sources and relays, and relays and destination, the outage probability of all si-rj-dilinks can be evaluated through the procedure described in Section 6.2. It is also observedin Section 6.2 that the outage probability of a specific link does not depend on the choiceof OFDMA subcarrier subset φm. Therefore, the need for allocating OFDMA subcarriersubsets to si-di pairs is eliminated, leaving us only with relays to be allocated. In orderto allocate relays, the gain matrix in (6.29) is formed, and then performing the Hungarianmethod on this matrix readily gives us the relay allocation pattern. Finally, the OFDMAsubcarrier subsets φm can be allocated randomly to the si-rj-di links, so that simultaneouscommunication of si-di pairs is not corrupted. This algorithm is evaluated through numericalsimulation in the next section.6.4 Numerical simulation resultsIn this section, the behavior of our system model and the performance of our proposed relayallocation scheme is examined through numerical simulations. In simulations, it is assumedthat the number of channel taps on all the channels is equal, i.e., Lsirj = Lrjdi = L, and thechannel tap coefficients on a given channel have equal variance, while the variance of channeltaps on different channels are not necessarily equal, as the followingvar(hsirj(1))= · · · = var(hsirj(L))= σ2sirj/L,var(hrjsi(1))= · · · = var(hrjsi(L))= σ2rjsi/L. (6.30)Furthermore, the total power of channels, σ2sirj and σ2rjsi , are taken from a uniformly dis-tributed RV between 0 and 1σ2sirj ∼ U [0, 1] , σ2rjsi ∼ U [0, 1]. (6.31)Equal power budgets at all the source and relay nodes is also assumed (Psi = Prj = Ps = Pr),and the threshold rate is set to 1 for all si-di pairs (γi = γ = 1 bit/s/Hz), and noise variancesat relays and destinations are σ2s = σ2r = 1. In addition, the users are allowed to use OFDMAsubcarrier groups of Nφ = 16, and the SNR is the transmit SNR per OFDM subcarrier.In this section, all the demonstrated probabilities, whether analytical or simulated, areprobabilities averaged over 1000 samples of σ2sirj and σ2rjsi in (6.31). In case of analyticalresults, the global outage probability is obtained using (6.23) for each sample of σ2sirj and1086.4. Numerical simulation results0 5 10 15 20 2500.10.20.30.40.50.60.70.80.91SNR[dB]Global Probability of Outage L=4 HungarianL=4 randomL=6 HungarianL=6 randomL=8 HungarianL=8 randomFigure 6.2: Simulated global outage probability against SNR when Ns = Nr = 4 and Nφ =16, for L = 4, 6, 8.σ2rjsi , then the results are averaged. While regarding the simulated results, for each sample ofσ2sirj and σ2rjsi , 1000000 samples of source-relay and relay-destination channels are generatedaccording to (6.3) and (6.4), the number of outage events is counted, and the global outageprobability is calculated. Then the outage probabilities associated with samples of σ2sirj andσ2rjsi are averaged.In Fig 6.2., the simulated global outage probabilities at different SNRs are shown forrandom relay allocation and our proposed relay allocation method. In this figure, keepingthe number of source-destination pairs and relays at Ns = Nr = 4, the number of channeltaps L is varied to study the effects of frequency diversity on the global outage probability.As it can be seen, the proposed relay allocation scheme outperforms random relay allocationsignificantly for all numbers of channel taps, which is due to the improved cooperativediversity in our method. Moreover, increasing the number of channel taps results in better1096.4. Numerical simulation results0 5 10 15 20 2500.10.20.30.40.50.60.70.80.91SNR[dB]Global Probability of Outage Ns=4 HungarianNs=4 randomNs=6 HungarianNs=6 randomNs=8 HungarianNs=8 randomFigure 6.3: Simulated global outage probability against SNR when L = 4 and Nφ = 16, forNs = Nr = 4, 6, 8.performance in both cases in terms of outage probability, which is due to the increasedfrequency diversity.The simulated global outage probabilities at different SNRs for constant L = 4 anddifferent numbers of source-destination pairs are demonstrated in Fig 6.3. Likewise, theresults for random relay allocation and our proposed relay allocation method are shown inthis figure, where our relay allocation algorithm beats the random allocation scheme witha considerable margin. In addition, increasing the number of users worsens the outageperformance. This is because outage event happens even if only one source-destination pairis in outage, which is more likely when more pairs are to be realized. We have observedin our simulations that the analytical outage probabilities agree precisely with simulatedresults for all the cases of random relay allocation and relay allocation based on Hungarianmethod, which demonstrates the precision of our outage analysis. However, the analytical1106.4. Numerical simulation results0 5 10 15 20 2500.10.20.30.40.50.60.70.80.91SNR[dB]Global Probability of Outage Nφ=16 simulated HungarianNφ=16 analytical HungarianNφ=4 simulated HungarianNφ=4 analytical HungarianFigure 6.4: Simulated and analytical global outage probabilities against SNR when L = 4and Ns = Nr = 4 for Nφ = 4, 16.results are not depicted in Fig. 6.2 and Fig. 6.3 to avoid impairing the readability of thefigures. Analytical and simulated results can be compared in Fig. 6.4.The effect of low number of subcarriers in OFDMA subsets is investigated in Fig. 6.4,where we keep both the number of sources and channel taps constant and vary Nφ. In thisfigure, the simulated and analytical outage probabilities with Nφ = 4 and Nφ = 16 areshown where the relays are allocated according to our proposed method. As it is mentionedin Chapter 4, approximating the capacity of a single si-rj-di link by a Gaussian RV resultsin tight approximations of outage probability if the number of OFDM subcarriers is nottoo low. It can be seen in Fig. 6.4 that the simulated and analytical results match whenNφ = 16, while the analytical results slightly deviate from simulated results when Nφ = 4.However, although the analytical approximated outage probability is not exact for Nφ = 4,we can see that the simulated performance of the system is identical to the case of Nφ = 16.1116.4. Numerical simulation resultsWe can deduce here that low number of subcarriers does not provide good approximationsfor the outage probability, but it does not degrade the effectiveness of our relay allocationmethod, either.112Chapter 7Conclusions and Future ResearchDirections7.1 ConclusionsIn this thesis, we have addressed the cell association problem in HetNets, and performanceevaluation as well as relay allocation in relay-based cooperative networks. We have proposedseveral cell association schemes in the context of HetNets, and characterized the outagebehavior of cooperative relay-based systems in a broader system model compared to existingworks in the literature. We also have proposed a relay allocation scheme based on our outageanalysis. In the following, the concluding remarks on the contributions made in this thesisare brought.First, in Chapter 2, we addressed the cell association problem in the downlink of a multi-tier HetNet in which BSs have finite number of RBs available to distribute among theirassociated users. We proposed a QoS-driven distributed cell association algorithm in whichusers receive only enough number of RBs to satisfy their QoS constraints. The algorithmsare derived in two different frameworks. The first one is maximizing the sum utility of longterm rate with long term rate QoS constraints. The second framework is minimizing theglobal outage probability with outage QoS constraints. The algorithm obtained in the firstframework is suitable for environments with slow fading and low mobility users. On the otherhand, the second framework is constructed in the context of outage to design cell associationalgorithms suitable for fast fading environments. It was shown that the cell associationproblem in both frameworks have the same structure. Therefore, a unified cell associationalgorithm was proposed by applying Lagrange dual decomposition method. The option ofdistributing the remaining RBs is also given to the BSs after the cell association phase.Distributing the rest of RBs improves the rates seen by the users significantly at the expenseof consuming more energy and time and frequency resources. The derived algorithms are oflow complexity, and low levels of message passing are required to render them distributed.Extensive simulation results that are brought in Chapter 2 show that our distributed cellassociation scheme outperforms the maximum SINR scheme. For instance, rate gains of up1137.1. Conclusionsto 2.4x have been observed in the simulations for the cell edge users in our distributed cellassociation algorithm over maximum SINR scheme. Most importantly, we provided a generalframework for jointly associating users to BSs and RBs in LTE systems in which frequencyreuse factor of 1 and no interference coordination are assumed.Second, in Chapter 3, we extended the work in Chapter 2 by considering uplink as wellas downlink. In Chapter 3 we addressed a joint downlink and uplink aware cell associationproblem in a multi-tier HetNet in which BSs have finite number of RBs to distribute amongthe users in the downlink and uplink. We proposed a distributed cell association schemeto maximize the downlink and uplink rates while maintaining outage QoS. The QoS is pro-vided in both downlink and uplink by considering separate outage requirements for the userin downlink and uplink. Designing distributed and uplink aware cell association schemesis a major challenge in cellular networks since users cannot measure the uplink attributesincluding the uplink interference at their end. This is while users can measure some of thedownlink attributes by listening to the reference signals that BSs are constantly transmitting.Therefore, we required the BSs to report the uplink interference using few number of bits.Few number of bits incurs negligible load on the already existing reference signals of the BSs.A low complexity distributed scheme is then proposed by introducing this limited amount offeedback and applying Lagrange dual decomposition method. In the proposed scheme, theusers receive only enough number of RBs to satisfy their QoS constraints. Keeping the num-ber of RBs minimum is in particular interesting from energy saving perspectives. Moreover,by assigning different weights to the downlink and uplink rates, the proposed scheme canbe modified to be only downlink oriented, only uplink oriented, or both downlink and up-link aware. By comparing the proposed scheme with the downlink oriented maximum SINRscheme through simulations, significant uplink rate gains are observed. This is while thegains in the downlink rates are also considerable. Furthermore, simulation results verify theintrinsic asymmetries that exist between the attributes of downlink and uplink in HetNets.We also have considered a general system model in designing the distributed downlink anduplink aware cell association schemes, where frequency reuse factor of 1 and no interferencecoordination are assumed.Next, in Chapter 4, we addressed the the outage behavior of the fundamental three-node cooperative model with one source, one relay, and one destination, in which OFDMtechnology is used to combat the frequency selectivity of the channel. We analyzed the outageprobability and outage capacity of this OFDM DF network assuming Rayleigh frequencyselective channel model. In our analysis, the correlation between OFDM subchannels alongwith arbitrary number of bits on each subchannel is considered. The analysis is carried out byfitting a normal distribution to the total capacity of the system. The normal distribution is1147.1. Conclusionsa suitable model for the total capacity of OFDM systems. This is because the total capacityis a summation of capacities on individual OFDM subcarriers which are usually identicalrandom variables. The exact mean and approximated variance of the system capacity areobtained that result in tight approximations on the outage probability of the describedsystems. As a special case, the exact variance of the total capacity is derived for i.i.d. OFDMsubchannels that results in even tighter approximations on the outage probability. Finally,the simulation results demonstrated the precession of our analysis even for low number ofOFDM subchannels.As an extension to Chapter 4, in Chapter 5, we let multiple users to communicate to acommon destination through a single relay. The channel is assumed to be Rayleigh frequencyselective. OFDMA is used as the multiple access scheme to realize multiple source-destinationstreams. We addressed the global outage behavior of this network in the sense that globaloutage occurs if at least one source-destination stream goes into outage. It is observedthat the outage analysis for single source-relay-destination link is similar to the analysisprovided in Chapter 4 if correlated OFDM subchannels and arbitrary number of bits on eachsubchannel are to be accounted for. However, it is observed that the capacity on differentlinks are correlated RVs that complicates the global outage analysis. The correlation iscreated on the relay-destination channel that is common to all the steams. We proposedto fit a multi-variate normal distribution to the link capacities. Then, we approximatedthe covariance between the link capacities to characterize the global outage event. MonteCarlo simulations verified the validity of this analysis for multi-user single-relay OFDMADF networks.Finally, building upon Chapter 4, in Chapter 6, we investigated a clustered two-hopDF network consisting of a set of source-destination pairs, and a cluster of relays. It isassumed that there is no LOS between the source and destination clusters, and only onerelay can help a particular source-destination pair in their communication. The channels areRayleigh frequency selective on which OFDMA is employed to realize multiple simultaneoussource-relay-destination links. Given some statistical parameters of the channels, the eventof global outage is analyzed for the general case of correlated OFDM subcarrier gains, andarbitrary number of bits on each subcarrier. The global outage is again defined as the eventwhere at least one source-destination pair experiences outage. The obtained global outageprobability is then used to formulate a relay allocation optimization problem for which alow complexity solution based on Hungarian method is proposed. It is also shown that theoutage probability on a single source-relay-destination link does not depend on the choice ofOFDMA subcarrier subset if all the subsets consist of equal number of contiguous OFDMsubcarriers. This observation simplified the relay allocation problem by removing the need1157.2. Future research directionsto allocate the OFDMA subcarrier subsets. In the end, the numerical results demonstratedthe precision of the outage analysis, and effectiveness of the relay allocation method.7.2 Future research directionsIn this section, we propose some possible research directions that can be followed from thisthesis:• In our research on cell association problem in HetNets, we have not considered anyICIC. This is while considering resource partitioning, ICIC, and interference avoidanceschemes can potentially enhance the overall user experience. Therefore, consideringthe mentioned techniques on top of the proposed cell association schemes can be apossible research venue.• In the context of cell association in HetNets, we have assumed that the channel isfrequency flat on the bandwidth of the BSs, i.e., the channel gain is identical on all theRBs of a BS at a certain time from user’s point of view. This assumption is made tokeep the system model simple and as general as possible. However, the BSs’ referencesignals are spread over time and frequency on the RBs so that a user can interpolatethe channel gains on all the RBs. Meanwhile, different channel gains on different RBshighly complicates the analysis and designing distributed QoS-based cell associationschemes. As a possible future research direction, the frequency selectivity of channelscan be considered in the context of cell association in HetNets.• In the context of cell association in HetNets, two admission control schemes are pro-posed in Chapters 2 and 3. The proposed admission control schemes are used to projecta potential infeasible solution back to the feasible set. We have used heuristics to de-sign these admission control schemes. Therefore, the dynamics of the optimizationproblems in Chapters 2 and 3 need to be investigated in more depth in search foroptimal admission control schemes.From another perspective, in the proposed admission control schemes, we have notassumed any protocol for the communication of the BSs. However, in LTE-Advanced,BSs exchange information regarding load balancing and ICIC through X2 interface.Therefore, admission control schemes should be designed considering the protocol ofX2 interface as well as the limitations that this interface imposes on the communicationof BSs.1167.2. Future research directions• In our research on cell association problem in HetNets, we have assumed the Rayleighchannel model. However, Rayleigh distribution captures only some characteristics ofthe wireless channel. More comprehensive wireless channel models such as Nakagami-mdistribution should be considered. Also, the performance of the proposed cell associ-ation schemes need to be investigated with empirical channel models through simu-lations and experiments in order to modify these schemes to be suitable for practicalimplementation.• In the context of relay-based cooperative communication, we have analyzed the outagebehavior of OFDM DF relaying system in a Rayleigh fading environment in Chapters4 and 5. However, Rayleigh distribution captures only some characteristics of thewireless channel. More comprehensive wireless channel models such as Nakagami-mdistribution should be considered. The difficulty of considering statistical models suchas Nakagami-m is that the analysis required to characterize the distribution of thetotal capacity becomes more complicated. In addition, OFDM cooperative systemsoperating under different protocols such as AF can be analyzed in the same manner.• In our research on the problem of relay allocation in an OFDMA DF multi-sourcemulti-destination scenario in Chapter 6, it is assumed that the number of OFDM sub-carriers in all OFDMA subcarrier subsets is a constant, i.e., all users are allocatedequal number of OFDM subcarriers. This assumption along with the obligation ofchoosing adjacent subcarriers in the spectrum for each subset result in independenceof the link’s capacity from the choice of OFDMA subset, which reduces one of theproblem’s dimensions. If the OFDMA subcarrier subsets are composed of varyingnumber of subcarriers, or non-contiguous OFDM transmission takes place in the sys-tem, the choice of subcarrier subset will become one of the factors influencing the globaloutage probability. Adding the choice of OFDMA subcarrier subset to allocating re-lays to source-destination streams converts the two dimensional assignment problemwe have encountered in Chapter 6 to a three dimensional assignment problem whichis NP-hard in general [85]. Therefore, devising simplified low-complexity schemes tosolve this complex problem for multi-stream OFDMA relayed systems can be anotherpossible research direction.• In general, in the context of OFDM cooperative communications, employing OFDMtranslates into sending information on parallel subcarriers, where the behavior of eachsubcarrier is an RV, and all the subcarriers show an identical behavior, meaning thatthe RVs associated with these subcarriers are identical. Since channel capacity or bit1177.2. Future research directionsrate is an additive parameter, the total capacity or bit rate is always obtained byadding up the capacities or rates on parallel OFDM subcarriers, resulting in GaussianRVs according to central limit theorem. Devising a unified scheme to approximatethe mean and variance of the resulting capacity or bit rate under any OFDM protocolconsidering general channel distributions is another research venue. As the next step,using the analysis for general distributions, designing distributed algorithms to allocaterelays to source-destination pairs in multi-user scenarios can be considered.118Bibliography[1] G. Wu, S. Talwar, K. Johnson, N. Himayat, and K. D. Johnson. M2M: From mobile toembedded internet. IEEE Communications Magazine, 49(4):36–43, Apr. 2011.[2] LM Ericsson. More than 50 billion connected devices, Feb. 2011.[3] Cisco. Cisco visual networking index: Global mobile data traffic forecast update, 2010- 2015. White Paper, Feb. 2002.[4] A. J. Viterbi. CDMA: Principles of Spread Spectrum Communication. Addison WesleyLongman Publishing Co., Inc., 1995.[5] R. V. Nee and R. Prasad. OFDM for Wireless Multimedia Communications. ArtechHouse, Inc., 1st edition, 2000.[6] D. Gesbert, M. Shafi, D.-S. Shiu, P. J. Smith, and A. Naguib. From theory to practice:An overview of MIMO space-time coded wireless systems. IEEE Journal on SelectedAreas in Communications, 21(3):281–302, Apr. 2003.[7] R. Q. Hu and Y. Qian. Heterogeneous Cellular Networks. Wiley - IEEE Series. Wiley,2013.[8] S. Haykin. Cognitive radio: Brain-empowered wireless communications. IEEE Journalon Selected Areas in Communications, 23(2):201–220, Feb. 2005.[9] Federal Communications Commission. Spectrum policy task force. Rep. ET Docket no.02-135, Nov. 2002.[10] S. Yeh, S. Talwar, G. Wu, N. Himayat, and K. Johnsson. Capacity and coverageenhancement in heterogeneous networks. IEEE Wireless Communications, 18(3):32–38,Jun. 2011.[11] W. Song, H. Jiang, and W. Zhuang. Performance analysis of the WLAN-first schemein cellular/WLAN interworking. IEEE Transactions on Wireless Communications,6(5):1932–1952, May 2007.[12] V. Chandrasekhar, J. G. Andrews, and A. Gatherer. Femtocell networks: A survey.IEEE Communications Magazine, 46(9):59–67, Sep. 2008.[13] H. Claussen, L. T. W. Ho, and L. G. Samuel. Financial analysis of a pico-cellular homenetwork deployment. In Proc. of 2007 IEEE ICC, pages 5604–5609.119Bibliography[14] A. B. Saleh, S. Redana, B. Raaf, and J. Hamalainen. Comparison of relay and pico eNBdeployments in LTE-advanced. In Proc. of 2009 IEEE VTC, pages 1–5.[15] A. Damnjanovic, J. Montojo, Y. Wei, T. Ji, T. Luo, M. Vajapeyam, T. Yoo, O. Song,and D. Malladi. A survey on 3GPP heterogeneous networks. IEEE Wireless Commu-nications, 18(3):10–21, Jun. 2011.[16] T. Nihtila and V. Haikola. HSDPA performance with dual stream MIMO in a combinedmacro-femto cell network. In Proc. of 2010 IEEE VTC, pages 1–5.[17] H. R. Karimi, L. T. W. Ho, H. Claussen, and L. G. Samuel. Evolution towards dynamicspectrum sharing in mobile communications. In Proc. of 2006 IEEE PIMRC, pages 1–5.[18] M. Yavuz, F. Meshkati, S. Nanda, A. Pokhariyal, N. Johnson, B. Raghothaman, andA. Richardson. Interference management and performance analysis of UMTS/HSPA+femtocells. IEEE Communications Magazine, 47(9):102–109, Sep. 2009.[19] S.-M. Cheng, S.-Y. Lien, F.-S. Chu, and K.-C. Chen. On exploiting cognitive radio tomitigate interference in macro/femto heterogeneous networks. IEEE Transactions onWireless Communications, 18(3):40–47, Jun. 2011.[20] A. Khandekar, N. Bhushan, Ji Tingfang, and V. Vanghi. LTE-advanced: Heterogeneousnetworks. In Proc. of 2010 European Wireless Conference, pages 978–982.[21] G. Boudreau, J. Panicker, N. Guo, R. Chang, N. Wang, and S. Vrzic. Interference coordi-nation and cancellation for 4G networks. IEEE Communications Magazine, 47(4):74–81,Apr. 2009.[22] K. Okino, T. Nakayama, C. Yamazaki, H. Sato, and Y. Kusano. Pico cell range ex-pansion with interference mitigation toward LTE-advanced heterogeneous networks. InProc. of 2011 IEEE ICC, pages 1–5.[23] M. Shirakabe, A. Morimoto, and N. Miki. Performance evaluation of inter-cell interfer-ence coordination and cell range expansion in heterogeneous networks for LTE-advanceddownlink. In Proc. of 2011 ISWCS, pages 844–848.[24] E. C. Van der Meulen. Three-terminal communication channels. Advances in appliedProbability, 3(1):120–154, Spring 1971.[25] T. Cover and A. El Gamal. Capacity theorems for the relay channel. IEEE Transactionson Information Theory, 25(5):572–584, Sep. 1979.[26] R. Pabst, B.H. Walke, D.C. Schultz, P. Herhold, H. Yanikomeroglu, S. Mukherjee,H. Viswanathan, M. Lott, W. Zirwas, M. Dohler, H. Aghvami, D.D. Falconer, and G.P.Fettweis. Relay-based deployment concepts for wireless and mobile broadband radio.IEEE Communications Magazine, 42(9):80–89, Sep. 2004.120Bibliography[27] J. N. Laneman, D. N. C. Tse, and G. W. Wornell. Cooperative diversity in wirelessnetworks: Efficient protocols and outage behavior. IEEE Transactions on InformationTheory, 50(12):3062–3080, Dec. 2004.[28] R. U. Nabar, H. Bolcskei, and F. W. Kneubuhler. Fading relay channels: Performancelimits and space-time signal design. IEEE Journal on Selected Areas in Communica-tions, 22(6):1099–1109, Aug. 2004.[29] J. N. Laneman and G. W. Wornell. Energy-efficient antenna sharing and relaying forwireless networks. In Proc. of 2000 IEEE WCNC, pages 7–12.[30] Z. Hasan, H. Boostanimehr, and V. K Bhargava. Green cellular networks: A survey,some research issues and challenges. IEEE Communications Surveys and Tutorials,13(4):524–540, Nov. 2011.[31] C. Hoymann, W. Chen, J. Montojo, A. Golitschek, C. Koutsimanis, and X. Shen.Relaying operation in 3GPP LTE: Challenges and solutions. IEEE CommunicationsMagazine, 50(2):156–162, Feb. 2012.[32] D. Astely, E. Dahlman, A. Furuskar, Y. Jading, M. Lindstrom, and S. Parkvall. LTE:The evolution of mobile broadband. IEEE Communications Magazine, 47(4):44–51,Apr. 2009.[33] E. Dahlman, S. Parkvall, and J. Skold. 4G: LTE/LTE-Advanced for Mobile Broadband.Academic Press, 2013.[34] H. G. Myung, J. Lim, and D. Goodman. Single carrier FDMA for uplink wirelesstransmission. IEEE Vehicular Technology Magazine, 1(3):30–38, Sep. 2006.[35] J. Li, X. Wu, and R. Laroia. OFDMA Mobile Broadband Communications: A SystemsApproach. Cambridge University Press, 2013.[36] G. Berardinelli, L. A. Ruiz de Temino, S. Frattasi, M. I. Rahman, and P. Mogensen.OFDMA vs. SC-FDMA: Performance comparison in local area IMT-A scenarios. IEEEWireless Communications, 15(5):64–72, Oct. 2008.[37] B. E. Priyanto, H. Codina, S. Rene, T. B. Sorensen, and P. Mogensen. Initial perfor-mance evaluation of DFT-spread OFDM based SC-FDMA for UTRA LTE uplink. InProc. of 2007 IEEE VTC, pages 3175–3179.[38] 3GPP. X2 general aspects and principles. TS 36.420, 3rd Generation PartnershipProject (3GPP), Dec. 2009.[39] 3GPP. X2 application protocol (x2ap). TS 36.423, 3rd Generation Partnership Project(3GPP), Sep. 2010.[40] A. Ghosh, R. Ratasuk, B. Mondal, N. Mangalvedhe, and T. Thomas. LTE-advanced:Next-generation wireless broadband technology. IEEE Wireless Communications,17(3):10–22, Jun. 2010.121Bibliography[41] Y. Nam, Y. Akimoto, Y. Kim, M. Lee, K. Bhattad, and A. Ekpenyong. Evolution of ref-erence signals for LTE-advanced systems. IEEE Communications Magazine, 50(2):132–138, Feb. 2012.[42] Z. Shen, A. Papasakellariou, J. Montojo, D. Gerstenberger, and Fangli X. Overviewof 3GPP LTE-advanced carrier aggregation for 4G wireless communications. IEEECommunications Magazine, 50(2):122–130, Feb. 2012.[43] D. Lee, H. Seo, B. Clerckx, E. Hardouin, D. Mazzarese, S. Nagata, and K. Sayana.Coordinated multipoint transmission and reception in LTE-advanced: Deployment sce-narios and operational challenges. IEEE Communications Magazine, 50(2):148–155,Feb. 2012.[44] J. G. Andrews. Seven ways that HetNets are a cellular paradigm shift. IEEE Commu-nications Magazine, 51(3):136–144, Mar. 2013.[45] H. Kim, G. de Veciana, X. Yang, and M. Venkatachalam. Distributed α-optimal userassociation and cell load balancing in wireless networks. IEEE/ACM Transactions onNetworking, 20(1):177–190, Feb. 2012.[46] K. Son, S. Chong, and G. Veciana. Dynamic association for load balancing and interfer-ence avoidance in multi-cell networks. IEEE Transactions on Wireless Communications,8(7):3566–3576, Jul. 2009.[47] Q. Ye, B. Rong, Y. Chen, M. Al-Shalash, C. Caramanis, and J. G. Andrews. Userassociation for load balancing in heterogeneous cellular networks. IEEE Transactionson Wireless Communications, 12(6):2706–2716, Apr. 2013.[48] Q. Ye, M. Al-Shalash, C. Caramanis, and J. G. Andrews. On/off macrocells and loadbalancing in heterogeneous cellular networks. arXiv preprint arXiv:1305.5585, 2013.[49] S. Corroy, L. Falconetti, and R. Mathar. Dynamic cell association for downlink sumrate maximization in multi-cell heterogeneous networks. In Proc. of 2012 IEEE ICC,pages 2457–2461.[50] E. Stevens-Navarro, Y. Lin, and V. W. S. Wong. An MDP-based vertical handoffdecision algorithm for heterogeneous wireless networks. IEEE Transactions on VehicularTechnology, 57(2):1243–1254, Mar. 2008.[51] S. E. Elayoubi, E. Altman, M. Haddad, and Z. Altman. A hybrid decision approach forthe association problem in heterogeneous networks. In Proc. of 2010 IEEE INFOCOM,pages 1–5.[52] E. Aryafar, A. Keshavarz-Haddad, M. Wang, and M. Chiang. RAT selection games inHetNets. In Proc. of 2013 IEEE INFOCOM, pages 998–1006.[53] D. Niyato and E. Hossain. Dynamics of network selection in heterogeneous wireless net-works: An evolutionary game approach. IEEE Transactions on Vehicular Technology,58(4):2008–2017, May 2009.122Bibliography[54] H. S. Dhillon, R. K. Ganti, and J. G. Andrews. Load-aware modeling and analysisof heterogeneous cellular networks. IEEE Transactions on Wireless Communications,12(4):1666–1677, Apr. 2013.[55] H.-S. Jo, Y. J. Sang, P. Xia, and J. G. Andrews. Heterogeneous cellular networks withflexible cell association: A comprehensive downlink SINR analysis. IEEE Transactionson Wireless Communications, 11(10):3484–3495, Oct. 2012.[56] H. S. Dhillon S. Singh and J. G. Andrews. Offloading in heterogeneous networks: Mod-eling, analysis, and design insights. IEEE Transactions on Wireless Communications,12(5):2484–2497, Dec. 2013.[57] S. Singh and J. G. Andrews. Joint resource partitioning and offloading in heterogeneouscellular networks. IEEE Transactions on Wireless Communications, 13(2):888–901, Feb.2014.[58] X. Chen and R. Q. Hu. Joint uplink and downlink optimal mobile association in awireless heterogeneous network. In Proc. of 2012 IEEE GLOBECOM, pages 4131–4137.[59] V. Emamian, P. Anghel, and M. Kaveh. Multi-user spatial diversity in a shadow-fadingenvironment. In Proc. of 2002 IEEE VTC, pages 573–576.[60] M. O. Hasna and M.-S. Alouini. Optimal power allocation for relayed transmissions overRayleigh-fading channels. IEEE Transactions on Wireless Communications, 3(6):1999–2004, Nov. 2004.[61] M.O. Hasna and M.-S. Alouini. Performance analysis of two-hop relayed transmissionsover Rayleigh fading channels. In Proc. of 2002 IEEE VTC, pages 1992–1996.[62] L. Dai, B. Gui, and L. J. Cimini. Selective relaying in OFDM multihop cooperativenetworks. In Proc. of 2007 IEEE WCNC, pages 963–968.[63] M. Kaneko, K. Hayashi, P. Popovski, K. Ikeda, H. Sakai, and R. Prasad. Amplify-and-forward cooperative diversity schemes for multi-carrier systems. IEEE Transactions onWireless Communications, 7(5):1845–1850, May 2008.[64] W. Yang, W. Yang, and Y. Cai. Outage performance of OFDM-based selective decode-and-forward cooperative networks over Nakagami-m fading channels. Wireless PersonalCommunications, 56:503–515, Apr. 2011.[65] B. Gui, L. Dai, and L. J. Cimini. Selective relaying in cooperative OFDM systems:Two-hop random network. In Proc. of 2008 IEEE WCNC, pages 996–1001.[66] W. Siriwongpairat, A. Sadek, and K. J. R. Liu. Cooperative communications proto-col for multiuser OFDM networks. IEEE Transactions on Wireless Communications,7(7):2430–2435, Jul. 2008.[67] T. S. Rappaport. Wireless Communications: Principles and Practice. Prentice Hall,Inc., second edition, 2002.123Bibliography[68] S. Kandukuri and S. Boyd. Optimal power control in interference-limited fading wire-less channels with outage-probability specifications. IEEE Transactions on WirelessCommunications, 1(1):46–55, Jan. 2002.[69] Y. D. Yao and A. U. H. Sheikh. Outage probability analysis for microcell mobile radiosystems with cochannel interferers in Rician/Rayleigh fading environment. ElectronicsLetters, 26(13):864–866, Jun. 1990.[70] H. W. Kuhn. The Hungarian method for the assignment problem. Naval ResearchLogistics Quarterly, 2:83–397, Mar. 1955.[71] D. W. Pentico. Assignment problems: A golden anniversary survey. European Journalof Operational Research, 176(2):774–793, Nov. 2007.[72] S. P. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press,2004.[73] S. H. Low and D. E. Lapsley. Optimization flow control I: Basic algorithm and conver-gence. IEEE/ACM Transactions on Networking, 7(6):861–874, Dec. 1999.[74] D. P. Bertsekas. Convex Optimization Theory. Athena Scientific, 2009.[75] D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: NumericalMethods. Prentice-Hall, Inc., 1989.[76] C. E. Leiserson, R. L. Rivest, C. Stein, and T. H. Cormen. Introduction to Algorithms.The MIT Press, 2001.[77] G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1998.[78] A. Assalini and S. Pupolin. On second-order statistical description of mutual informationfor OFDM systems. In Proc. of 2008 Wireless Personal Multimedia Communications,pages 1–5.[79] A. Assalini. Maximizing outage capacity of OFDM transmit diversity systems. IEEETransactions on Vehicular Technology, 58(9):4786–4794, Nov. 2009.[80] M. R. McKay, P. J. Smith, H. A. Suraweera, and I. B. Collings. On the mutual infor-mation distribution of OFDM-based spatial multiplexing: Exact variance and outageapproximation. IEEE Transactions on Information Theory, 54(7):3260–3278, Jul. 2008.[81] M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions with Formulas,Graphs, and Mathematical Tables. Dover, ninth dover printing, tenth gpo printingedition, 1964.[82] N. Nakagami. The m-distribution, a general formula for intensity distribution of rapidfading. In Statistical Methods in Radio Wave Propagation. Oxford, England: Pergamon,1960.124Bibliography[83] S. O. Rice. Mathematical analysis of random noise. Bell System Technical Journal,24(1):46–156, Jan. 1945.[84] W. H. Greene. Econometric Analysis. Prentice Hall, fifth edition, 2000.[85] R. E. Burkard, M. Dell’Amico, and S. Martello. Assignment Problems. Society forIndustrial and Applied Mathematics, 2009.125
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Resource allocation and performance evaluation in heterogeneous...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Resource allocation and performance evaluation in heterogeneous and relay-based wireless networks Boostanimehr, Hamidreza 2014
pdf
Page Metadata
Item Metadata
Title | Resource allocation and performance evaluation in heterogeneous and relay-based wireless networks |
Creator |
Boostanimehr, Hamidreza |
Publisher | University of British Columbia |
Date Issued | 2014 |
Description | In the last decade, mobile data demand has been exponentially growing. Telecommunication industry finds it increasingly difficult to cope with this exponential growth through conventional cellular networks with carefully planned high power macro base stations (BSs). Therefore, the densification of BSs through introduction of low power BSs has been considered for implementation. The combination of macro BSs and low power BSs such as pico and femto BSs as well as relay nodes is referred to as heterogeneous networks (HetNets). HetNets impose major technical challenges in implementation such as severe interference cases and imbalance of load among macro BSs and low power BSs. One problem that needs to be re-addressed in the context of HetNets is the cell association problem. Although centralized cell association schemes are important in realizing the potentials of HetNets, mobile operators are interested in distributed schemes in which network elements decide based on their local information. In this thesis, we consider distributed cell association algorithms with quality of service provisioning. First, we propose a unified cell association algorithm that is particularly designed for downlink. Next, we consider uplink to have a downlink and uplink aware cell association scheme. The performances of the proposed schemes are examined through numerical simulations. Cooperative relay-based communication combined with orthogonal frequency division multiplexing (OFDM) and its multi access variant, orthogonal frequency division multiple access (OFDMA) has gained an immense interest in the last decade. Among all the research topics in OFDM relay-based communication, analyzing the outage behavior has been an invariable concern to researchers. To analyze the outage behavior, most of the researchers ignore the correlation between OFDM subchannels, and also assume equal bit allocation on all the subchannels. In this thesis, we analyze the outage behavior of a three-node OFDM relay-based network when these two assumptions are relaxed. Next, we characterize the global outage probability of a multi-user single-relay OFDMA network. Finally, a network consisting of a cluster of source-destination pairs and a cluster of relays is considered where we propose a low complexity relay allocation scheme. The outage analyses and the relay allocation scheme are examined through numerical simulations. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2014-08-26 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
IsShownAt | 10.14288/1.0166959 |
URI | http://hdl.handle.net/2429/50207 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2014-09 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2014_september_boostanimehr_hamidreza.pdf [ 1.34MB ]
- Metadata
- JSON: 24-1.0166959.json
- JSON-LD: 24-1.0166959-ld.json
- RDF/XML (Pretty): 24-1.0166959-rdf.xml
- RDF/JSON: 24-1.0166959-rdf.json
- Turtle: 24-1.0166959-turtle.txt
- N-Triples: 24-1.0166959-rdf-ntriples.txt
- Original Record: 24-1.0166959-source.json
- Full Text
- 24-1.0166959-fulltext.txt
- Citation
- 24-1.0166959.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0166959/manifest