UPLINK SCHEDULING AND RESOURCE ALLOCATION SCHEMESFOR LTE-ADVANCED SYSTEMS THAT INCORPORATE RELAYSOR CARRY HETEROGENEOUS TRAFFICbyRukhsana RubyB.Sc. Bangladesh University of Engineering & Technology, 2004M.Sc. University of Victoria, 2009A 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 2015c© Rukhsana Ruby, 2015AbstractScheduling and resource allocation is one of the important tasks of the radio resourcemanagement layer in long term evolution (LTE) and LTE-Advanced wireless systems.Uplink scheduling and resource allocation is considered more challenging comparedto the downlink case because of individual users’ power constraints and the discretenature of spectrum assignment. Downlink scheduling and resource allocation hasextensively been studied for relay equipped or heterogeneous traffic networks, butless work has been considered for the LTE uplink case. In this thesis, we haveproposed a few uplink scheduling and resource allocation schemes of LTE-Advancedsystems that incorporate relay(s) or carry heterogeneous traffic.First, we have proposed a basic uplink scheduling and resource allocation schemefor decode-and-forward relay aided systems. Existing uplink scheduling works havelooked at the problem from different angles instead of basic scheduling and resourceallocation. In addition of having optimal resource allocation, the proposed scheme isadaptive. If the system has some bad or redundant relays, the proposed scheme candetect and recommends them to be deactivated.Having observed the difficulty in deciding which users to serve for a relay under theconstraint of limited power, second, we have proposed a joint source and relay powerallocation scheme for an amplify-and-forward relayed system. Existing works of thisproblem have ignored one term in their problem formulation, and hence failed to offerthe optimal solution for all possible scenarios. We have taken care of that missingiiAbstractterm in our work, and have shown the performance improvement comparing withthe existing works. In this solution, all entities in the network work in an altruisticmanner towards maximizing the network capacity. However, in the real world, thenodes may want some benefits while sacrificing their resource. To model the selfishbehavior of the nodes, in the third work, we have proposed a game theoretical solutionof this problem.Fourth, we have proposed an uplink scheduling and resource allocation schemefor a network which carries heterogeneous traffic. Although there are some existinguplink scheduling works dealing QoS in heterogeneous traffic networks, those werenot careful about detailed standard specific all constraints. In addition to meet theconflicting requirements of QoS for different traffic, the proposed scheme takes theresource utilization constraint into account which is designed to benefit the networkoperators.iiiPrefaceMany of the results that are presented in this thesis have been published in academicjournals or presented at academic conferences:• Rukhsana Ruby and Victor C.M. Leung, "Uplink scheduling solution for en-hancing throughput and fairness in relayed long-term evolution networks," IETCommunications, Volume 8, Issue 6, 17 April 2014, p. 813–825. (Linked toChapter 3)• Rukhsana Ruby, Victor C.M. Leung and David G. Michelson, "Uplink Schedulerfor SC-FDMA based Heterogeneous Traffic Networks with QoS Assurance andGuaranteed Resource Utilization," IEEE Transaction on Vehicular Technology,2014, p. 1–17. (Linked to Chapter 6)• Rukhsana Ruby, Victor C.M. Leung and David G. Michelson, "Centralized andGame Theoretical Solutions of Joint Source and Relay Power Allocation for AFRelay based Network," IEEE Transactions on Communications, 2015, p. 1–16.(Linked to Chapters 4 and 5)• Rukhsana Ruby, Amr Mohamed and Victor C.M. Leung, "Utility-Based UplinkScheduling Algorithm for Enhancing Throughput and Fairness in Relayed LTENetworks," IEEE LCN, 2010: 520-527. (Linked to Chapter 3)• Rukhsana Ruby and Victor C.M. Leung, "Optimal Edge Nodes Selection andivPrefacePower Allocation in Relay Enabled Network," IEEE CCECE, 2011: 1347-1350.(Linked to Chapter 4)• Rukhsana Ruby and Victor C.M. Leung, "Towards QoS assurance with revenuemaximization of LTE Uplink Scheduling," IEEE CNSR, 2010: 202-209. (Linkedto Chapter 6)I defined the research problems considered in this thesis and am the principalcontributor to all works presented here. Prof. Leung and Prof. Michelson providededitorial feedback concerning the entire thesis and provided specific guidance andfeedback concerning Chapters 1, 2 and 7. Chapters 3, 4, 5 and 6 are based on thejournal manuscripts listed above. Although the work on Chapter 3 began with theconference paper that I wrote with Dr. Amr Mohamed, the problem formulation andsolution approach in the journal paper is significantly different.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviNotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xixAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Research Problems and Contributions . . . . . . . . . . . . . . . . . 31.2 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . 72 Background and Related Work . . . . . . . . . . . . . . . . . . . . . 92.1 Evolution of LTE-Advanced Systems . . . . . . . . . . . . . . . . . . 102.1.1 Uplink Spectrum Access Mechanism . . . . . . . . . . . . . . 12viTable of Contents2.1.2 Uplink Scheduling and Resource Allocation . . . . . . . . . . 132.2 Relays in LTE-Advanced Systems . . . . . . . . . . . . . . . . . . . . 152.3 Heterogeneous Traffic in LTE-Advanced Systems . . . . . . . . . . . 192.4 Summary of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 223 Uplink Scheduling and Resource Allocation for DF Relayed Systems 233.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.3 System Model and Problem Formulation . . . . . . . . . . . . . . . . 273.3.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . 273.3.2 Motivation Behind Deploying Relays . . . . . . . . . . . . . . 283.3.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . 303.4 Solution Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.5 Proposed Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.5.1 Iterative Λ Update Procedure . . . . . . . . . . . . . . . . . . 363.5.2 Low Complexity Suboptimal Algorithm . . . . . . . . . . . . 393.5.3 SOA2 Extended Algorithm . . . . . . . . . . . . . . . . . . . 403.5.4 Performance Improvement using Power Control . . . . . . . . 433.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 443.6.1 Simulation Methodology . . . . . . . . . . . . . . . . . . . . . 443.6.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . 463.7 Summary of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 564 Joint Source and Relay Power Allocation for AF Relayed Network(Centralized Solution) . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.2 System Model and Problem Formulation . . . . . . . . . . . . . . . . 64viiTable of Contents4.3 Centralized Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.3.1 Suboptimal Source Power Allocation (Greedy Solution) . . . 714.3.2 Suboptimal Source Power Allocation (Fair Solution) . . . . . 714.3.3 Suboptimal Relay Power Allocation . . . . . . . . . . . . . . 724.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 734.4.1 Simulation Methodology . . . . . . . . . . . . . . . . . . . . . 734.4.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . 744.5 Summary of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 785 Joint Source and Relay Power Allocation for AF Relayed Network(Game Theoretical Solution) . . . . . . . . . . . . . . . . . . . . . . . 795.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.2 System Model and Problem Formulation . . . . . . . . . . . . . . . . 825.3 Game Theoretical Solution . . . . . . . . . . . . . . . . . . . . . . . 835.3.1 Game Theoretical Source Power Allocation . . . . . . . . . . 855.3.2 Game Theoretical Relay Power Allocation . . . . . . . . . . . 955.3.3 Further Discussion . . . . . . . . . . . . . . . . . . . . . . . . 1005.4 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1025.5 Summary of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 1086 Uplink Scheduling and Resource Allocation for Heterogeneous Traf-fic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1096.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1096.2 System Model and Problem Formulation . . . . . . . . . . . . . . . . 1166.2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . 1166.2.2 The Utility Function . . . . . . . . . . . . . . . . . . . . . . . 1196.3 Solution Approach and Scheduling Algorithm . . . . . . . . . . . . . 125viiiTable of Contents6.4 Characteristics of Proposed Scheduling Scheme . . . . . . . . . . . . 1326.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 1366.5.1 Simulation Methodology . . . . . . . . . . . . . . . . . . . . . 1366.5.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . 1396.6 Summary of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 1537 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . 1557.1 Summary of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 1557.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1587.2.1 Self Configurable Uplink Scheduling and Resource Allocationof DF Relayed Systems . . . . . . . . . . . . . . . . . . . . . 1587.2.2 Joint Multi-Source and Multi-Relay Power Allocation for AFRelayed Network . . . . . . . . . . . . . . . . . . . . . . . . . 1597.2.3 Game Theoretical Solution of Joint Sources and Relay PowerAllocation for AF Relayed Network under Imperfect CSI . . . 1607.2.4 Uplink Scheduling and Resource Allocation for Multi-Cell Het-erogeneous Traffic Networks . . . . . . . . . . . . . . . . . . . 160Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161AppendicesAppendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173A Proof of the Properties for I(p) . . . . . . . . . . . . . . . . . . . . . 173B Proof of the Properties for I(λ) . . . . . . . . . . . . . . . . . . . . . 175ixTable of ContentsC Additional Research Work . . . . . . . . . . . . . . . . . . . . . . . . 177xList of Tables3.1 Total allocated RBs. . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.2 Number of active relays/edge nodes. . . . . . . . . . . . . . . . . . . 584.1 Source power comparison between optimal and suboptimal greedy so-lutions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764.2 Source relay power comparison between optimal and suboptimal solu-tions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765.1 Source transmit power comparison between optimal and game theo-retical solutions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1065.2 Source relay power comparison between optimal and game theoreticalsolutions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1076.1 Simulation parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . 139xiList of Figures1.1 Bandwidth and latency requirements of potential applications [1]. . . 21.2 LTE uplink resource grid for one slot [2]. . . . . . . . . . . . . . . . . 42.1 In OFDM, each frequency component carries unique information. InSC-FDMA, the information is spread across multiple subcarriers [3]. . 122.2 LTE frame structure [2]. . . . . . . . . . . . . . . . . . . . . . . . . . 132.3 The increasing trend of emerging heterogeneous traffic (Ericsson con-sumer lab) [4]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.1 Individual user’s throughput w.r.t. its allocated RBs. . . . . . . . . . 293.2 Simulation scenario (setup-1). . . . . . . . . . . . . . . . . . . . . . . 453.3 System throughput comparison among our relayed algorithms andthose without relay (setup-1). . . . . . . . . . . . . . . . . . . . . . . 463.4 Comparison between throughput maximization and fair algorithms(setup-1). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.5 System throughput comparison among our relayed algorithms andthose without relay (setup-2). . . . . . . . . . . . . . . . . . . . . . . 513.6 System throughput comparison among our relayed algorithms andthose without relay (setup-3). . . . . . . . . . . . . . . . . . . . . . . 523.7 System throughput comparison among our relayed algorithms andthose without relay (setup-4). . . . . . . . . . . . . . . . . . . . . . . 53xiiList of Figures3.8 Individual user’s throughput as a function of the distance from basestation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.9 Individual user’s allocated RBs as a function of the distance from basestation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.1 System model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.2 Comparison between our centralized solutions and others. . . . . . . . 755.1 System model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825.2 Source power allocation game. . . . . . . . . . . . . . . . . . . . . . . 1035.3 Relay power allocation game. . . . . . . . . . . . . . . . . . . . . . . 1065.4 System throughput comparison between optimal and game theoreticalsolutions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1086.1 Characteristics of the utility function. . . . . . . . . . . . . . . . . . . 1206.2 Sample subframe structure for stage 2 of Algorithm 7. . . . . . . . . . 1306.3 VoIP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1416.4 Per RB normalized rate loss comparison between our scheme and other(VoIP). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1426.5 Video streaming. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1456.6 Cell throughput comparison between our scheme and others (Video). 1466.7 Per user average packet delay comparison between homogeneous andheterogeneous setup (VoIP). . . . . . . . . . . . . . . . . . . . . . . . 1496.8 Per user average packet delay comparison between homogeneous andheterogeneous setup (Audio). . . . . . . . . . . . . . . . . . . . . . . 1496.9 Per user normalized throughput comparison between homogeneous andheterogeneous setup (Video). . . . . . . . . . . . . . . . . . . . . . . . 150xiiiList of Figures6.10 Per user normalized throughput comparison between homogeneous andheterogeneous setup (FTP). . . . . . . . . . . . . . . . . . . . . . . . 1506.11 Admission region with QoS guarantee comparison between our schemeand other. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152xivList of Algorithms1 Iterative algorithm to determine (x∗,P∗). . . . . . . . . . . . . . . . . 592 Intermediate fraction of Algorithm 1. . . . . . . . . . . . . . . . . . . 603 Suboptimal RB allocation algorithm. . . . . . . . . . . . . . . . . . . 604 SOA2 extended RB allocation algorithm. . . . . . . . . . . . . . . . . 615 Iterative algorithm for optimal λt. . . . . . . . . . . . . . . . . . . . . 616 Fair algorithm for subdividing transmit power among the sources. . . 727 Suboptimal RB allocation algorithm. . . . . . . . . . . . . . . . . . . 131xvList of Abbreviations1G First Generation Cellular2G Second Generation Cellular3G Third Generation Cellular3GPP Third Generation Partnership Project4G Fourth Generation CellularAF Amplify and ForwardAMR Adaptive Multirate CodecAWGN Additive White Gaussian NoiseBER Bit Error RateCDMA Code Division Multiple AccessCF Compress and ForwardCSI Channel State InformationDF Decode and ForwardE-UTRA Evolved UMTS Terrestrial Radio AccessEXP ExponentialFD Full DuplexFTP File Transfer ProtocolGP Geometric ProgrammingHD Half DuplexHoL Head of LinexviList of AbbreviationsHSDPA High Speed Downlink Packet AccessIFDMA Interleaved Frequency Division Multiple Accessi.i.d Independent and Identically DistributedIP Internet ProtocolKKT Karush-Kuhn-TuckerLFDMA Localized Frequency Division Multiple AccessLTE Long Term EvolutionLWDF Largest Weighted Delay FirstMAC Medium Access ControlM-LWDF Modified LWDFMT Maximum ThroughputMW Max WeightOFDM Orthogonal Frequency Division MultiplexingOFDMA Orthogonal Frequency Division Multiple AccessPAPR Peak to Average Power RatioPDU Protocol Data UnitPF Proportionally FairQCI Quality of Service Class IndicatorQoS Quality of ServiceRB Resource BlockRLC Radio Link ControlRTP Real Time ProtocolSC-FDMA Single Carrier Frequency Division Multiple AccessSE Stackelberg EquilibriumSINR Signal to Interference and Noise RatioxviiList of AbbreviationsSNR Signal to Noise RatioTCP Transmission Control ProtocolTTI Transmission Time IntervalUDP User Datagram ProtocolUMTS Universal Mobile Telecommunications SystemVoIP Voice over IPxviiiMathematical NotationsE(·) Statistical expectation.ln(x) Logarithmic of x with base 2.ex Exponential function of x.HdB H is a number in decibel unit.∑Sum operator.∏Multiplication operator.√x Square root of x.x−1 Inverse of x, 1/x.[x]+ Non–negative value of x, [x]+ = max{x, 0}.|x| Absolute value of x.x±y Either x+ y or x− y.x∓y Either x− y or x+ y.bxc Floor operation on x, largest integer value not greater than x.dxe Ceiling operation on x, largest integer value smaller than x.a?b : c if expression a is true then return b, else return c.O(·) Order of a function, f(x) is O(x) if limx→0 f(x)/x = 0.MT Transpose of matrix M.∂H∂xPartial derivative of function H with respect to x.∂2H∂x2Partial derivative of function ∂H∂xwith respect to x.∂2H∂x∂yPartial derivative of function ∂H∂xwith respect to y.xixMathematical Notationsx ∈ X x is a variable which points to an element of set X.∀x ∈ X x can be any element of set X.∃x ∈ X x is some element of set X, not necessarily points to any element of X.[X|y] This is a set which contains all elements of set X except y.[x ∈ X|x 6=y] x points to an element of X given that x 6=y.R The set of real numbers.[x, y) The set which contains all real numbers in between x and y, including xand excluding y.A∪B Union of sets A and B.Rn A vector which has n elements, and each element is from set R.xxAcknowledgmentsFirst of all, I am grateful to Almighty GOD for giving me courage, strength andmaking the way towards pursuing this degree. HE gave me energy time to time toget up when I was about to fall down during the critical periods of my life.Second, I am thankful to my supervisor Prof. Victor C.M. Leung for supportingme financially some parts of the program. I appreciate the help of my co-supervisorProf. David G. Michelson for his assistance in the final year.Insightful comments by my committee members Prof. Vikram Krishnamurthyand Prof. Jane Wang helped me to materialize all problems in the thesis. Theysupported the ideas of my PhD proposal at the beginning, and finally the thesis. Iam thankful to them as well.Special thanks to WiNMoS group members Dr. Jun Bae Seo, Dr. Haoming Li, Dr.Hu Jin, Javad Hajipour, Hasen Nisanfar, Xin Ge and others for giving me feedbackwhen I presented my works in our private group meetings. I have some collaboratorsin my group with whom I have some works as a co-author. They are Li Zhou, XuanDong, Saad Mahboob, Shiguo Wang, Javad Hajipour and Arghavan Emami. Theymade my time worthy and enjoyable, and I would like to acknowledge them. Manythanks to my friend Dr. Yanyan Zhuang and my housemate Victoria Karner to getalong with me during my loitering time.Finally, I am immensely indebted to my family, i.e., my mother and sisters fortheir love and blessings. They were my inspiration to live in this planet. This thesisxxiAcknowledgmentsis dedicated to the loving memory of my father.xxiiChapter 1IntroductionCellular networks as well as wireless services have undergone unprecedented devel-opment over the last few decades. With the increasing demand of subscribers, hand-held devices now support sophisticated applications, such as interactive video, onlinegames, etc. In order to make these applications work with the subscribers at theminimum quality of service (QoS), network operators need very high data rate trans-mission media. Accordingly, digital signal processing techniques, microprocessor tech-nology, and radio frequency (RF) engineering have made a considerable advancement,and thus cellular network technologies are emerging, such as Long Term Evolution(LTE) and LTE-Advanced. In general, the performance of cellular networks is basedpredominantly on its achievable throughput, i.e., how many data bits can be conveyedsuccessfully in a given amount of time; average end to end delay of the data packets,i.e., on average how much time is required to transmit a data packet; fairness, i.e., dothe subscribers experience the same QoS regardless of their distance from the basestation, etc. Figure 1.1 shows different types of emerging applications and their QoSrequirements in terms of throughput and latency.Conventionally, the performance of such systems can be improved by increas-ing the channel bandwidth and/or transmit power. However, the amount of channelbandwidth is limited due to the physical limitation, and thus cannot be exploited lav-ishly. On the other hand, there is great need to conserve power when the transmitteris battery operated as in the case of cellular handsets. A feasible response to these1Chapter 1. IntroductionFigure 1.1: Bandwidth and latency requirements of potential applications [1].2Chapter 1. Introductionissues is to design the system in such a way that these resources are used efficientlyand effectively. While making the design of such systems, several optimization prob-lems need to be solved in order to produce suitable scheduling and resource allocationschemes. However, depending on the transmission direction, the formulation of thescheduling and resource allocation problems, and the corresponding solutions mayvary. For example, the formulation of the downlink scheduling problem is differentcompared to the uplink one because of the varying nature of constraints. Moreover,for the uplink scheduling, physical channels may need to be assigned among the sub-scribers in a certain manner compared to the downlink one. These problems makefurther difference if the system is equipped with digital relays or the system is loadedwith the subscribers running different applications with distinct QoS.In this thesis, we have proposed a few uplink scheduling and resource allocationschemes that improve the performance of LTE-Advanced systems that incorporaterelays or carry heterogeneous traffic. In order to recognize the contributions of thisthesis, the readers are encouraged to go through Chapter 2. In addition to relatedworks in the context of this thesis, we have briefly summarized the evolution ofLTE-Advanced systems and their radio resource management policies in Chapter 2.Moreover, since the scheduling concept in this thesis is based on the uplink spectrum-users mapping, we have briefly reviewed the uplink spectrum access mechanism there.The remainder of this chapter is organized as follows. We briefly summarize thecontributions of this thesis in Section 1.1, while Section 1.2 describes its structure.1.1 Research Problems and ContributionsIn the LTE uplink, the time-frequency resource unit is the resource block (RB),defined as 7 (occasionally 6) consecutive orthogonal frequency division multiplexing3Chapter 1. IntroductionFigure 1.2: LTE uplink resource grid for one slot [2].(OFDM) or single carrier frequency division multiple access (SC-FDMA) symbolsin the time domain and 12 consecutive subcarriers in the frequency domain. Thephysical description of RBs is shown in Figure 1.2. The resources we have consideredin this thesis are RBs and power. At the minimal transmission time interval (TTI)of the LTE frame structure, the available number of RBs is fixed and constant. Thedetailed description of LTE frame and channel structure is given in Chapter 2. Thebasic scheduling and resource allocation is to select a set of users, determining RB-user mapping and setting of transmit power on each RB in each TTI.• Contribution 1: First, we have proposed a basic uplink scheduling and re-source allocation scheme for a LTE network which has some pre-configured4Chapter 1. Introductionstatic decode-and-forward (DF) relays with full duplex (FD) functionality. Asmentioned in Chapter 2 that there were extensive works on the basic down-link scheduling for relay equipped LTE networks taking various factors, suchas fairness, quality of service (QoS), spatial reuse into account. There weresome contemporary uplink scheduling works as well, however those looked atthe scheduling problem from different angles instead of giving solution for thebasic uplink scheduling and resource allocation. The basic uplink schedulingand resource allocation is necessary to measure the system performance pre-cisely in the granular level. To solve the problem, first, we have formulated theproblem assuming the routing information of all nodes are pre-configured. Dualdecomposition method is usually used to solve this type of problem. Havingnoticed the high computational complexity of this solution, we have proposeda set of suboptimal scheduling schemes. Deploying a large number of relaysmay not be useful to the basic user nodes, and hence the proposed schemes areadaptive and have ability to distinguish useful relays from the not-useful ones.Besides, if the relays are in the bad locations, sometimes, the proposed schemescan distinguish those bad relays. Through extensive simulation, we have shownthe performance improvement of our scheduling schemes comparing with otherexisting work in the literature.• Contribution 2: In the first work, we have seen, if a relay needs to help manysources, even if the assignment of RBs are known, optimal power allocationamong the relay and sources is a difficult problem. There are many existingworks in this context no matter the relay has DF or amplify-and-forward (AF)functionality. Although the performance of a DF relay is better, researchersoften recommend AF relays because of its simplicity. In the existing works5Chapter 1. Introductionwith AF relay, the authors have not considered the direct link signal to noiseratio (SNR) in their problem formulation. Hence, given the power constraint,for some sources, when the direct link SNR is better than the relayed linkone, performance of the solution deviates from the optimal one. In this work,we have solved the same problem, however considering the direct link SNRin the problem formulation. Because of incorporating the direct link SNR,the resultant problem is non-convex. We have used geometric programming(GP)-based method to solve this problem. Furthermore, having noticed thehigh computational complexity of the optimal solution, we also have proposedtwo suboptimal solutions that take greedy and fair nature of the sources intoaccount.• Contribution 3: In the previous work, all nodes in the network are altruistic.They work selflessly towards maximizing the network capacity. However, in thereal world, the user nodes are not that selfless, they want to maximize their owninterest while sacrificing their resource. In order to model such selfish behaviorof the nodes, we have proposed a game theoretical solution of this problemin this work. Although there are some existing game theoretical solutions forthe relay power allocation, there is no complete joint source and relay powerallocation solution for this problem. By the help of two Stackelberg games, ourproposed game theoretical solution is partially distributed. Finally, throughsimulation, we have proved that the proposed game theoretical solution achievescomparable performance with the centralized optimal solution.• Contribution 4: Fourth, we have proposed a basic uplink scheduling andresource allocation scheme for LTE heterogeneous traffic systems considering allstandard specific constraints and individual user QoS demand. As mentioned6Chapter 1. Introductionin Chapter 2 that there were many works done on the downlink schedulingfor homogeneous and heterogeneous traffic networks. Compared to that, notmuch works have been done on the uplink scheduling for heterogeneous trafficnetworks. A few works which dealt the uplink scheduling for QoS-aware LTEnetworks, have not considered detailed standard specific constraints in theirformulation. However, in order to measure the system performance precisely,it is required to take all constraints into account. In order to capture the QoScriteria of different traffic, we have adopted a utility function which is alreadyused for the downlink operation of code division multiple access (CDMA)-basedsystems. Furthermore, to facilitate the interest of the service providers, weconsider an additional concept, opportunity cost function which is constructedbased on the granular resource utilization. Dual decomposition method hasbeen used in order to solve the formulated problem. Having noticed the highcomputational complexity of the optimal solution, we have given a suboptimalalgorithm with relatively lower complexity. Through extensive simulation, wehave justified the efficacy and effectiveness of our scheme comparing with otherexisting solutions of LTE systems.1.2 Organization of the ThesisIn Chapter 2, we briefly summarize the background and existing works in order tojustify the contributions of this thesis. In Chapter 3, we propose an uplink schedulingand resource allocation scheme for DF relay (with FD functionality) based systems(contribution 1). We propose the centralized solution for joint source and relay powerallocation of an AF-relay-based system (contribution 2) in Chapter 4. In Chapter 5,we provide the game theoretical solution of the problem in Chapter 4 (contribution7Chapter 1. Introduction3). We present an uplink scheduling and resource allocation scheme for a systemcarrying heterogeneous traffic (contribution 4) in Chapter 6. Finally, in Chapter 7,we summarize the thesis with some directions for future research.8Chapter 2Background and Related WorkIn this chapter, we provide the background materials to support the contribution ofthis thesis. As mentioned in the previous chapter, the demand for the bandwidth incellular networks is continuously increasing due to the varying traffic with differentQoS requirements. To cope with this increasing demand, we have seen unprece-dented levels of improvement in the physical layer. However, this improvement is notsufficient to sustain the satisfactory performance of new applications. Among manypossible ways to improve the performance of cellular networks, smart implementationof the radio resource management layer is one given the limited amount of resource.As this thesis is linked to the radio resource management of LTE-Advanced systems,we would like to give an overview of the evolution of such systems and their radioresource management policies. Scheduling and resource allocation is one of the tasksin this layer, and the objective of this thesis is to prove that optimal implementa-tion of this task can enhance the system performance. Although this task is equallyimportant for both the downlink and uplink operations, in this thesis, we will onlystick to the uplink scheduling and resource allocation to fill the gap in the literature.Furthermore, LTE-Advanced systems recommend several new techniques to improvethe system performance. Relaying is one of the mechanisms. Since two problems ofthis thesis are analogous to the relays and one problem is pertinent to heterogeneoustraffic, we will briefly summarize each of the concepts in separate section.The rest of the chapter is organized as follows. Section 2.1 briefly summarizes the9Chapter 2. Background and Related Workevolution of LTE-Advanced systems and their radio resource management policies.Moreover, we describe the channel structure of such systems, and define the uplinkscheduling and resource allocation in this section. Section 2.2 and Section 2.3 providethe brief overview of relay technologies and emerging heterogeneous traffic of LTE-Advanced systems, respectively. Finally, Section 2.4 summarizes this chapter.2.1 Evolution of LTE-Advanced SystemsThe ever increasing demands of users have triggered researchers and industries tocome up with a comprehensive manifestation of the fourth generation (4G) mobilecommunication system. Looking past, wireless access technologies have followed dif-ferent evolutionary paths aimed at the unified target: performance and efficiency inthe high mobility environment. The first generation (1G) has fulfilled the basic mobilevoice, while the second generation (2G) has introduced capacity and coverage. Thisis followed by the third generation (3G), which has quest for data at higher speeds toopen the gates for truly mobile broadband experience, which is further realized by the4G. LTE-Advanced is considered as one of the 4G technologies. The 4G technologiessupport advanced mobile (low to high) services for high data rate applications whilesatisfying the service demands of multi-user heterogeneous traffic environments. Inorder to achieve optimal operations of the 4G technologies, intelligent implementationof the radio resource management layer is required.Radio resource can be both time and physical spectrum. All problems in thisthesis consider spectrum as radio resource. The limitation in radio spectrum comesfrom the fact that the spectrum is finite and it is not free. The more wireless applica-tions and technologies are used, the more bandwidth is required. Moreover, physicalspectrum alone does not mean bandwidth. Wireless devices need power in order to10Chapter 2. Background and Related Workuse the spectrum for physical data transmission. However, the continuous growth inwireless data traffic results in the increase of energy consumed by wireless networks,which leads to undesirable increase in carbon dioxide (CO2) emission. CO2 is consid-ered as the chief greenhouse gas that are resulted from wireless networks and otherhuman activities, and causes the global warming and climate changes. Despite thereare serious efforts to reduce the amount of CO2 emission at the base stations andmobile subscribers, efficient power management on the limited spectrum is urgentlyrequired.Although there are several aspects of radio resource management at different levelsof the network for achieving different services, this thesis is dedicated to the schedulingof spectrum and power management. Scheduling in LTE like systems can be done atthree different levels: admission, class, and packet level. Admission level schedulingis responsible for accepting or rejecting new user connections. It aims at satisfyingthe long term goal of users by maximizing the number of admitted connections whilemaintaining the satisfaction of ongoing ones. Class level scheduling deals with theaggregate demand of admitted users. It determines the number of transmission timeframes that each class needs in order to maintain the satisfaction of its admittedusers. Once the time frames are provisioned between different classes, packet levelscheduling is utilized in order to determine which of the user packets are transmittedin a single frame.This thesis deals with the packet level scheduling. Such schedulers may operatefor both the downlink and uplink transmissions. Centralized controller is mainlyresponsible for any of these scheduling operations. However, for the uplink scheduling,individual mobile nodes may make some autonomous decisions. All problems weconsider in this thesis are for the uplink spectrum scheduling and power allocation.11Chapter 2. Background and Related WorkFigure 2.1: In OFDM, each frequency component carries unique information. InSC-FDMA, the information is spread across multiple subcarriers [3].The following two subsections describe the uplink spectrum access mechanism, andthe definition of uplink scheduling and resource allocation, respectively.2.1.1 Uplink Spectrum Access MechanismLTE and LTE-Advanced take advantage of orthogonal frequency division multipleaccess (OFDMA), a multi-carrier scheme that allocates radio resources to multipleusers. OFDMA uses OFDM access technique. SC-FDMA is recommended as the3GPP LTE uplink transmission technique. It is a modified form of OFDMA, andhas similar performance and almost the same overall complexity as OFDMA has.Similar to OFDM, SC-FDMA also multiplexes subcarriers, but it transmits on thesubcarriers in sequence not in parallel which is the case in OFDM. This prevents powerfluctuations in SC-FDMA signals, i.e., low peak to average power ratio (PAPR) [5].Figure 2.1 shows the difference between OFDM and SC-FDMA.As depicted in Figure 2.2, one OFDM/SC-FDMA frame constitutes 20 slots, eachbeing 0.5 ms long. Each slot is called a subframe or TTI.The structure of one slot can be more clearly understood by looking at the resource12Chapter 2. Background and Related WorkFigure 2.2: LTE frame structure [2].grid structure in Figure 1.2 of Chapter 1. The transmit signal in each slot is describedby a resource grid with NRBNRBsc subcarriers and Nsymb OFDM/SC-FDMA symbols.The number of subcarriers for each RB NRBsc is standardized as 12 for the LTEuplink. NRB depends on the uplink transmission bandwidth determined for the cell,but should always be between 6 and 110. These numbers correspond to the smallestand largest uplink bandwidth [6], respectively. When time domain is considered, thenumber of OFDM/SC-FDMA symbols in each slot is 7 for the normal cyclic prefix.However, when the long cyclic prefix is used, this number decreases to 6. From thescheduling point of view at the radio resource management layer, RB is consideredas the minimal resource unit to access although each RB can be broken down intoresource elements.2.1.2 Uplink Scheduling and Resource AllocationThe definition of basic scheduling and resource allocation is the selection of a set ofusers/relays, determining RB-user/relay mapping, and setting of transmit power oneach RB. Because of interference, more than 1 user cannot be assigned to the sameRB. Moreover, for each node in the network no matter it is base station or mobileuser or relay, there is always a maximum limit on the amount of power available forthe purpose of transmission. Depending on the type of transmission, the number of13Chapter 2. Background and Related Workmaximum power constraints varies as well. For example, for the downlink operation,there is always one power constraint in the scheduling problem no matter the numberof users/relays in the system. On the other hand, for the uplink operation, the numberof power constraints proportionally increases with the number of users/relays in thesystem. Because of the growing number of power constraints, solution of the uplinkscheduling problem is more computationally intensive compared to the downlink one.The allocation of RBs to each user is an important issue which has an influence onthe system performance of the LTE uplink data transmission. Although SC-FDMAis the recommended technique for LTE uplink data transmission, OFDMA is oftenused in the literature to show the maximum possible multi-user, multi-channel di-versity for OFDM-based systems. Chapter 3 of this thesis assumes OFDMA as theuplink transmission technique. Taking OFDMA into consideration, some of the up-link scheduling and resource allocation works from different aspects, such as channelmodel, spatial multiplexing, fairness, etc. are [7, 8]. SC-FDMA has two types ofRB mapping [9]: Localized FDMA (LFDMA) and Interleaved FDMA (IFDMA). InLFDMA, the scheduler assigns consecutive RBs to convey information from a par-ticular user. In IFDMA, users are assigned RBs that are distributed over the entirefrequency band in order to avoid allocating adjacent RBs that are simultaneously indeep fade. Through LFDMA, full multi-user, multi-channel diversity is not achiev-able due to the contiguity constraint of RBs. Unlike OFDMA, not much works havebeen conducted on the uplink scheduling for LFDMA technique. Some existing worksin this context are [10, 11, 12, 13]. Even lesser works have been done for the uplinkscheduling and resource allocation considering IFDMA as the transmission technique.14Chapter 2. Background and Related Work2.2 Relays in LTE-Advanced SystemsOFDM and OFDMA technologies are well-known for mitigating frequency selectivefading and inter-symbol interference which results in increased performance. Evenunder the deployment of these technologies, nodes at the edge of a cell are often unableto achieve desired performance because of high path loss and shadow fading. In orderto tackle this problem, 3G/4G technologies have incorporated relaying concept whichis proven to alleviate the dead spots or enhance the coverage for such nodes andimprove the network capacity.Several relay strategy techniques have been proposed in the literature, such as AFand DF (Other less common scheme, such as compress-and-forward (CF)) as forward-ing schemes used by the relays [14, 15, 16]. DF strategy is a layer-2 based scheme,where relays act as bridges or routers for the traffic flowing from user terminals tothe base station. Through DF, the relay node retransmits just the replica of sourcenode’s transmitted signal. Whereas AF means, the relay nodes amplify source node’stransmitted signal and then retransmit towards the destination node. The relay op-eration can further be classified into FD and half duplex (HD) modes. In FD mode,relay node can transmit and receive simultaneously at the same frequency band inone frame, but needs to endure self interference due to the signal leakage betweenrelay output and input. In the HD mode, the relay is restricted to transmit andreceive over orthogonal (time division and frequency division) channels for avoidingself interference on it. Previous works mainly concentrated on the HD mode, whichenjoys much lower implementation complexity than the FD mode. However, FD isa more challenging and attractive mode which can provide better performance thanthe HD mode if self interference can be reduced efficiently. The problem in Chapter 3considers that the system is equipped with DF relays of FD mode, whereas Chapters15Chapter 2. Background and Related Work4 and 5 assume that the system has an AF relay with FD mode.Over the last few years, numerous works have been conducted on the basic down-link scheduling for OFDM-based DF relay enhanced cellular networks. In order tomaximize the system capacity, some heuristics for subcarrier and power allocationare given in [17], [18] and one detailed thorough work with required proofs is [19].For minimizing power, there are some contemporary works, e.g., [20]. Once peoplehave got an idea about optimal resource allocation to maximize the overall rate, theystarted looking at the problem from fairness point of view. For assuring fairness,some works are [21, 22]. Consequently, for ensuring QoS of users, one work is [23].All these works are based on the assumption that routing information of relays isfixed. Joint intra-cell routing and queue-aware downlink scheduling solutions havebeen proposed in [24], [25]. [24] is for HD relayed systems, whereas [25] is for FDrelayed systems. Taking inter-cell interference into account, optimal resource alloca-tion solution in multi-cell scenario is given in [26]. Furthermore, [27] and [28] haveincorporated spatial reuse factor in their resource allocation formulation.Under the deployment of fixed DF relays, uplink capacity analysis for LTE orOFDMA-based systems has appeared in some recent papers. Reference [29] hasstudied the uplink capacity of relay enhanced 802.16j networks that have OFDM-based physical layer. Resources they have considered are transmission duration ofrelays, mobile nodes and their assigned power. Optimizing the subframe durationand power, another work is [30]. Unlike [29], they co-schedule macro cell users andrelays at the same subframe, and then optimize their transmission power in order tomitigate inter-cell interference. Subsequent another subframe sharing work in uplinksystems is [31]. In [32], network coding has been used for the purpose of resourceallocation in OFDMA-based relay enabled systems. Relay node applies network16Chapter 2. Background and Related Workcoding between the uplink and downlink transmissions in order to attain its objective.Similar coding-aware another work is [33], however their attained resource allocationis proportionally fair. Despite all these sophisticated advancement on the uplinkresource allocation of LTE like systems, basic scheduler (finding RB-user mapping,and their power assignments) is still not studied that much. Chapter 3 proposes abasic uplink scheduler for DF relay enhanced LTE systems. After the publicationof our work, a few uplink resource allocation schemes appeared in the literaturerecently, such as [34, 35, 36]. Unlike us, [34, 35] proposed the resource allocationschemes on the assumption that the physical layer is based on SC-FDMA technique.Whereas, considering OFDMA-based physical layer, the resource allocation schemeof [36] optimizes the routes of all user nodes.As the deployment cost of relay is high, there might be a few number of relaynodes in the cell which can help the edge nodes to transmit their data. From thisperspective, one of the key problems in a relay equipped node is to make decisionwhich edge nodes to be helped and how much power need to be disseminated amongthem in order to maximize the system throughput. There are some existing worksin this context for a DF relay are [37, 38]. However, DF relays decode, re-modulateand retransmit the received signal, and hence incur high computational complexity.Therefore, researchers often recommend to use AF relays because of its simplicity.Power optimization of such networks with AF relays have extensively been studied.At the beginning of such exploration, people focused on a simple network with onesource and one relay [39]. And, then, relay power allocation under a single-sourcemulti-relay network has been studied varying different optimization criterion, i.e.,outage probability minimization or sum relay power minimization under sources’SNR or outage probability constraints [40], [41], [42].17Chapter 2. Background and Related WorkPerformance optimization of multi-source single-relay network has also been givenattention from different angles, such as interference cancellation schemes are proposedin [43] and [44]. In [45], network decoding is applied to combat interference amongusers. At the same time, joint multi-source and multi-relay power optimization hasappeared in a few papers [46], [47] under different optimization criterion, i.e., sumrate maximization, sum power minimization, etc. Although in [46], each source isessentially served by only one relay, [47] made performance improvement by assistingsingle source with the help of multiple relays. The drawback of their approach is, theyhave totally ignored SNR due to the direct link transmission in their optimizationformulation. Their approaches work very well when the direct link channel qualityis worse than the relayed link one. However, the performance starts to deviate fromthe optimal one when the direct link’s quality is better than the relayed link one.Having noticed this, we put the direct link SNR in the original formulation, and ourwork in Chapter 4 is to allocate power among the sources and relay based on thatformulation.In the solution of the problem in Chapter 4, all entities in the network are altru-istic, work selflessly towards maximizing the network capacity. However, in the realworld, nodes especially the users are not that selfless. They want to maximize theirown revenue or utility while sacrificing their resource. In order to model such selfishbehavior of the user nodes, game theory is a natural and flexible tool. Moreover,necessity of the game theoretical solution for this problem can be explained in otherway. In the altruistic solution of the problem, the users with better channel qualityare given more preference since these users contribute more towards the maximiza-tion of network capacity. However, this makes those users more valuable comparedto other users with worse channel condition, which is essentially not a fair attitude.18Chapter 2. Background and Related WorkFigure 2.3: The increasing trend of emerging heterogeneous traffic (Ericsson consumerlab) [4].Game theory allows all users to compete for their interests, i.e., utilities. The winningsituation of the game is decided by their actions. In this way, all users are treatedin the fair manner. Chapter 5 provides the game theoretical solution of the problemin Chapter 4. With the publication of our work, a few contemporary game theoreti-cal power allocation solutions appeared for slightly different types of relay equippednetworks in [48, 49, 50] recently.2.3 Heterogeneous Traffic in LTE-AdvancedSystemsWith the rapid advancement of LTE, LTE-Advanced, and other mobile broadbandnetworks, the number of smartphone subscribers have increased throughout the world.Smart phone devices host several applications, including games, video, file sharing,19Chapter 2. Background and Related Workmusic streaming, etc., which generate heterogeneous traffic in the network. More-over, due to the participation of large volume of users in the social networking sites,various types of traffic are continuously increasing. In future, we can anticipate moreadvanced applications which require more resources than the current applications do.Figure 2.3 shows the increasing proportion of data due to different applications in thenetwork over the years. However, to keep the demands of all these applications in-tact with the growing number of subscribers, it is very essential to design an efficientscheduler which can satisfy the conflicting requirements of different traffic.QoS ensured resource allocation for OFDM-based networks especially LTE sys-tems has appeared in some survey papers [51], [52]. For homogeneous traffic networks,the downlink scheduling and resource allocation problem has extensively been stud-ied. For example, for delay sensitive traffic, some works are [53, 54], whereas for thetraffic with data rate requirement, one work is [55]. Even specifically for VoIP, thereare some works, e.g., [56].The scheduling problem in heterogeneous traffic networks is more challengingthan in the homogeneous ones because of the conflicting requirements of differenttraffic. There are three design issues that need to be considered while formulatingthe problem of an ideal scheduler for heterogeneous traffic networks. Wireless usersexperience varying channel quality condition time to time due to the stochastic fadingeffects, and hence their achievable data rates are affected. The scheduler shouldchoose the user with good channel quality condition in order to maximize the systemthroughput. However, if the user with better channel quality condition is alwaysselected, the users with worse channel condition may starve. This issue is knownas fairness and another very important factor to keep into consideration. Third,different applications have different QoS requirements, and the utility function of the20Chapter 2. Background and Related Workscheduler should be defined in such a way that it has the ability to capture thosemetrics simultaneously and effectively.Similar to homogeneous traffic networks, the downlink scheduling and resourceallocation has extensively been studied for heterogeneous traffic environments. Theseworks mainly adopted three categories of designs. First, some works gave strict prior-ity to high priority traffic compared to lower priority ones, such as [57, 58]. Second,the authors in [59] have addressed mixed traffic (delay sensitive, guaranteed bit rate,best effort) by designing the scheduler on the time and frequency domains. The pri-ority sets are populated based on the QoS class indicator (QCI) of each data flow andclassified as guaranteed bit rate (GBR) and non-GBR. Third, different utility func-tions are used for different types of traffic (traffic with data rate requirement, trafficwith delay constraint) [60, 61]. Besides these, there are some general mechanismsfor handling mixed traffic. For example, the authors in [54] have proposed a lowcomplexity RB allocation algorithm using LOG/EXP, earliest deadline first (EDF)rules, and tested their scheme with mixed streaming and live video traffic.On the other hand, there are very few works for the uplink scheduling with QoSassurance. These works are mainly for homogeneous delay sensitive traffic [62, 63].One recent work on energy efficient QoS assured scheduler is [64], where QoS isconsidered as user’s instantaneous rate. For heterogeneous traffic environments, re-cently, [65] has proposed a scheduler which is based on the time and frequency domainscheduler [59]. One drawback of this work is, they did not consider traffic class intheir design. Moreover, they evaluated the performance of this scheduler in theircustomized simulation scenario, which is not practical. Having noticed the draw-back of [65] and in order to design a utility based scheduler for heterogeneous trafficenvironments, Chapter 6 of this thesis proposes an uplink scheduling and resource21Chapter 2. Background and Related Workallocation scheme of LTE systems conveying heterogeneous traffic. Once our schedul-ing scheme is off the shelf, a few works came forward consequently for heterogeneoustraffic networks, such as [66, 67, 68]. In [66], the authors proposed the schedulingscheme considering rate constraint of each user, and evaluated the performance oftheir scheme in a limited simulation scenario. On the other hand, [67, 68] are for thedownlink scheduling.2.4 Summary of the ChapterIn order to strengthen the contributions of this thesis, in this chapter, we have brieflycompiled the evolution of LTE-Advanced systems and their radio resource manage-ment policies. Furthermore, we have revised the relay technologies available in thestandard of such systems as well as the increasing trend of emerging heterogeneoustraffic that is expected to be met by these systems.22Chapter 3Uplink Scheduling and ResourceAllocation for DF Relayed Systems3.1 IntroductionUplink scheduling and resource allocation for OFDMA-based systems is a challengingproblem because of individual nodes’ power constraints and the discrete nature ofresource assignment. Emerging 3G/4G cellular network technologies, i.e., LTE, LTE-Advanced are based on OFDMA-based air interface where granular resource to accessis named as RB. Scheduling and resource allocation task in a typical LTE systemdetermines the set of users, assignment of RBs to these users and setting of transmitpower for each RB. In addition to providing high data rate, OFDMA is well-known formitigating frequency selective fading and inter-symbol interference. Even under thedeployment of OFDMA technologies, far distant nodes of a cell are unable to achievedesired performance because of higher path loss. In order to tackle this problem,3G/4G technologies have incorporated relaying concept which is proven to enhancethe coverage for such nodes and improve the network capacity. In this work, wehave considered a network enhanced with fixed digital DF relays deployed by serviceproviders in strategic locations. Scheduling problem appears to be more challengingunder such enhancement of networks. Moreover, the blind employment of relays inthe network brings a few more key questions. If service providers deploy more and23Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsmore relays, those may consume system resource while starving regular user nodeswhich is not an expected characteristic of an ideal resource scheduler. Under theblind deployment of a large number of relays, an ideal scheduler should be able todetermine which relays are useful and which are not contributing towards the overallsystem performance.In this chapter, we have formulated the uplink scheduling and resource allocationproblem of FD relay aided LTE networks as a convex optimization problem. Becauseof the LTE standard, resource constraint and deployed relays, the resultant problemhas three types of constraints. We have used dual decomposition method in orderto solve this problem. While exploring the solution structure, we have found, forthe given Lagrangian factors due to a relay constraint, the authors in [7] have givenmany suboptimal algorithms in order to obtain optimization variables, i.e., RB as-signments, power allocated on them. We have used their suboptimal algorithms inorder to find the principle optimization variables. Revealing the guiding principleof the optimal Lagrange multipliers due to the relay constraints, we have proposedan iterative procedure in order to obtain the suboptimal value of these multipliers,which essentially optimizes resource allocation across the network. The iterative pro-cedure has the ability to deactivate relays if they hamper the performance of otherindependent nodes in the system. The nodes connected to a deactivated relay act asindependent nodes. Because of the fast fading, the iterative procedure may not besuitable to be deployed as a scheduler, and hence a suboptimal algorithm has alsobeen proposed for RBs and their power assignments with the help of one heuristicproposed by [7]. Afterward, we have shown that if the proposed problem is formu-lated in the game theoretical way, the resultant solutions ensure fairness across theuser nodes. An extensive simulation has been conducted in order to justify that de-24Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsploying some low cost relays, we can essentially improve the system performance interms of overall throughput and occasionally fairness.The remainder of this chapter is organized as follows. A brief overview of literaturerelevant to our work is given in Section 3.2. In Section 3.3, we explain the terminologyused for the uplink scheduling of relay aided networks, and formulate the optimizationproblem. Solution approach of the formulated problem is presented in Section 3.4.Based on the solution approach, our designed algorithms are given in Section 3.5. Weprovide the simulation results in Section 3.6, and finally Section 3.7 concludes thischapter.3.2 Related WorkOver the last few years, numerous works have been conducted on scheduling andresource allocation of OFDM-based relay enhanced cellular networks. In [17], Huanget. al. proposed a centralized heuristic solution in order to perform subcarrier andpower allocation resulting in the capacity maximization of downlink systems. Sim-ilar other works are [69], [70] and [71]. Minimizing total power subject to the rateconstraint in such systems first appeared in [72]. In [20], the authors have studiedsimilar problems proposed in [17], [72], however they have improved the results byfinding optimal frame duration for the base station and relays. Most recent sumrate maximized resource allocation for downlink relayed systems is proposed by [18]subject to the sum sources and relays power constraint. Optimal resource allocationwhile ensuring max-min fairness has been proposed in [73], [21]. Whereas, for en-suring proportional fairness, some studies are [22], [74]. QoS-based subchannel andpower allocation was proposed by [23] in order to ensure QoS requirements of bothdirect and relayed users.25Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsJoint intracell routing and queue aware downlink scheduling solutions have beenproposed in [24], [25]. [24] considers the relays are of quasi FD mode, whereas [25]shows the performance improvement compared to the other one by adopting therelays with HD mode. Furthermore, [25] has conducted performance evaluationon asymmetric traffic, whereas the former one performed that on symmetric traf-fic. [75] has presented a scheduling and resource allocation scheme over broadcastblock fading channels in order to maximize long term average achievable rate regionof the users. Instead of single cell, [26] proposed a resource allocation scheme forOFDM-based DF relayed systems taking multi-cell interference and heterogeneoususer rate requirements into account. In order to achieve stable data rate for multi-media users, the authors in [76] have proposed a downlink scheduling technique forMIMO OFDM-based macro cells where there are some fixed relays. Besides propos-ing typical scheduling algorithms for relay enhanced networks, there are some worksdone in the last couple of years targeting on further performance improvement by ex-ploiting some environmental or inherent factors. While exploiting the multi-user andmulti-channel diversity of OFDM-based systems, [77], [27] and [28] have incorporatedanother factor, spatial reuse while developing their scheduling algorithms.All works discussed above are for the downlink scheduling on more or less HDrelayed OFDM-based systems. To date, not many works have been conducted onthe uplink resource allocation for OFDMA-based relay enhanced cellular networks.Given fixed routing information, [78] has proposed a subcarrier and power allocationscheme for OFDMA-based wireless mesh networks with the objective of maximizingNash bargaining fairness criterion. Unlike us, their scheduling scheme is partiallydistributed, each mesh router is independently responsible to allocate number of sub-carriers to its mesh clients, later each mesh client solves a mixed integer programming26Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsproblem for detailed resource allocation. Reference [29] has studied the uplink capac-ity of relay enhanced 802.16j networks with OFDMA-based physical layer. Resourcesthey have considered are transmission duration of relays, mobile nodes and their as-signed power. Unlike us, one assumption of their work is, the relay or mobile nodegets hold of all RB like subcarriers of its allotted transmission duration. In [32], net-work coding has been used for the purpose of resource allocation in OFDMA-basedrelay enabled systems. Relay node applies network coding between the uplink anddownlink transmissions in order to attain its objective. Another sum rate maximiza-tion work is [19] where the main assumption is, users are served by multiple DF relaysinstead of one. Taking individual power constraint for users and relays, they proposeda few suboptimal algorithms upon the non-convexity proof of the original problem.Similar to our work, uplink subchannel and power allocation has appeared previouslyin one paper [79] for OFDMA-based systems. However, that paper assumed that therelays are with HD functionality instead of FD.3.3 System Model and Problem Formulation3.3.1 Problem StatementWe consider a typical LTE cellular network, in which NT users transmit to the samebase station. There are some nodes across the cell edge, which suffer from highershadowing effect due to the long distance from the base station. In order to remedythis shadowing effect, a set of NK relays are deployed at reasonably fair distance fromthe base station. These relay nodes help transmit protocol data units (PDUs) fromthe base station to the edge nodes, and vice versa. Similar to the terminal nodes, theirphysical layer is based on OFDMA subcarriers combined in time division multiple ac-27Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemscess (TDMA) RBs. Since relay nodes serve a number of terminal nodes, transmissionpower of the relays is considerably larger than that of typical user nodes. In addition,any relay is assumed to have the ability to receive and transmit concurrently usingorthogonal RBs. In order to mitigate the self interference on the transmit and receiptRBs, the relays are equipped with separate antennas for two distinct operations. Ourgoal in this work is to allocate RBs across the user terminals and relays to maximizetheir aggregate utility.3.3.2 Motivation Behind Deploying RelaysOur sample network is presumed to be deployed in a rural environment. The channelgain for a particular node t over RB j in such an environment can be represented bythe following equation [8]1Ht,j,dB = (−κ− λlog10dt)− ξt,j + 10log10Ft,j. (3.1)In Equation 3.1, the first term κ captures propagation loss, dt is the distance inkm from mobile terminal t to the base station. λ is the path loss exponent, whichis set to a value of 3.76. The second term, ξt,j captures the log-normal shadowingeffect for the reference distance 1 km. Ft,j corresponds to the Rayleigh fading effectwith a parameter a such that E[a2] = 1. In the subsequent discussions, we will seethat there is a power constraint on each node and power is equally subdivided amongthe allocated RBs of a user according to the proposed suboptimal algorithms in [7].Under this condition and because of the parameter assigned for the Rayleigh fadingeffect on each RB, each node cannot get as many RBs as available since after a few1Instead of rural environments, if some other environments, such as urban, semi-urban would beconsidered, the channel model would be different. Hence, the resultant outcome of our proposedscheduling algorithms would be different.28Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systems1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6405060708090100110120Number of Allocated RBsThroughput (Mbps) User Dist = 0.3kmUser Dist = 0.4kmFigure 3.1: Individual user’s throughput w.r.t. its allocated RBs.allocations, its achieved rate deteriorates. Figure 3.1 justifies this argument whichdepicts the rate of 2 users at different distance from the base station with respectto the number of allocated RBs. We see, after allocating the 4th RB, the rate forthe user with distance 0.3 km gets degraded and it keeps degraded. Similar situationis for the other user, however it happens after allocating different number of RBs.Therefore, if the load is low in the network, we will see later that many RBs remainunallocated. Observing these unused RBs and worse condition of the edge nodes,we believe, deploying some relays will enhance the performance of the edge nodes aswell as the overall system while consuming the redundant RBs. Moreover, we haveseen the results under different deployment scenarios that even if a relay takes users’resource away, achieved throughput using that relay is larger than that without usingit.29Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systems3.3.3 Problem FormulationWe denote a set T = {1, 2, · · · , NT} for the terminal nodes, a set K = {1, 2, · · · , NK}for the relay nodes. Total number of RBs available in each scheduling epoch is NRBand the corresponding set for this is R = {1, 2, · · · , NRB}. Although each RB isequivalent to 12 subcarriers, in the LTE standard, granular resource access by user isRB. pt,j and pk,j are the instantaneous transmission power of user terminal t and relaynode k, respectively on RB j. For the uplink transmission, each node has constrainton the maximum power it can use at each scheduling epoch, and thus Pt and Pk arethe maximum power for the terminal and relay nodes, respectively. We denote a setP meeting the requirement of these constraints. These can be represented byNRB∑jpt|k,j ≤ Pt|k, ∀t∈T, ∀k∈K. (3.2)Let xt,j denote the fraction of RB j allocated to node t, where the total allocationacross all nodes should be no larger than 1, i.e.,NK+NT∑t=1xt,j ≤ 1, ∀j∈R, (3.3)where x denotes the set satisfying the constraint in Equation 3.3. According to theLTE standard, there is a constraint that each RB cannot be assigned to more thanone node, i.e., xt,j∈{0, 1}. In the subsequent discussions, we will see how we havedealt this constraint.The relay nodes are configured in such a way that they have more capability comparedto the ordinary terminal nodes. Besides, one relay serves a number of terminal nodes,and therefore the total rate achieved by the terminal nodes cannot be more than thatof the corresponding relay, and vice versa. In order to ensure proper utilization of30Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsachieved rate, we have used approximation sign in the constraint. Less than signwould work as well. However, it would cause wastage of consumed resource by therelays. Let there are NTk number of terminal nodes connected to the kth relay, andthe corresponding set is Tk. Denote the instantaneous rate of the kth relay is rk,whereas that of the tth user connected to the kth relay is rtk. According to thisconstraint∑t∈Tkrtk ≈ rk, ∀k∈K. (3.4)The utility function is defined as service satisfaction of each individual node in termsof throughput, delay or other QoS criteria. The optimization problem is to allocatea set of RBs IRB,k or IRB,t to each relay or terminal node such that the sum utilityof all nodes is maximized. This can be formulated in the following waymaximizeNT∑t=1U(IRB,t, Pt) +NK∑k=1U(IRB,k, Pk). (3.5)In this work, we first define the utility function of a node as its mere rate. Then,for the second step, in [78], we have seen, if the objective function is the product of allnodes’ rate (Nash product), the resultant resource allocation is fair across them. Itis a well-known result in game theory that the solution to the cooperative bargainingproblem maximizes the Nash product [80]. The objective function is further modifiedby taking logarithmic of it knowing the fact that logarithmic function is strictlyconcave. Hence, the resulting objective function becomes the sum of logarithmicrate for all nodes which is proven to ensure Nash bargaining fairness. In order toensure fair resource allocation among all nodes, we have studied the utility functionas logarithmic of node’s rate. When the utility function is mere rate, the objectivefunction yields31Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsargmaxx,P∑t∈(T∪K)rt; rt =∑j∈Rxt,jlog(1 +pt,jet,jxt,j), (3.6)subject to the constraints in Equations 3.2, 3.3 and 3.4. et,j represents the SNRper unit transmit power for node t on RB j. Typically, et,j is named as channel gain.Since each RB consists of 12 subcarriers, gain et,j is the average of all subcarriers onRB j. Moreover, while computing the gain, the physical distance for the terminalsconnected to a relay is determined assuming the end point as that relay. Whereas,for other nodes including the relays, the end point is the base station or centralizedcontroller.In this section, we have introduced the sample network architecture, motivationfor relay based systems, and then formulate the problem after defining all terminolo-gies to explain the uplink scheduling problem.3.4 Solution ApproachAs the number of relays in the system is NK , the total number of terminal nodesconnected to the relays is N ′T =∑k∈KNTk . The rest of the terminal nodes areindependent, and they directly send their data to the base station and this number isN ′′T = NT −N ′T ; the corresponding set is T′′. Taking these issues into consideration,the objective function in Equation 3.6 can further be broken down intoargmaxx,Pχ(x,P) :=∑t∈T′′rt +∑k∈Krk +∑k∈K∑t∈Tkrtk. (3.7)The objective function in Equation 3.7 has no duality gap and we can solve itby considering a dual formulation. Keeping the constraints in Equations 3.2 and 3.3intact and taking dual variables Λ = (Λ)k∈K for the constraint in Equation 3.4, the32Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsresulting Lagrangian becomesL(Λ,x,P) :=∑t∈T′′rt +∑k∈Krk +∑k∈K∑t∈Tkrtk (3.8)+∑k∈KΛk(∑t∈Tkrtk − rk):=∑t∈T′′rt +∑k∈K(rk − Λkrk) +∑k∈K∑t∈Tk(rtk + Λkrtk).According to the duality theory, the optimal solution of Equation 3.7 can be givenbyargminΛargmax(x,P)L(Λ,x,P). (3.9)The problem in Equation 3.8 has the similar form as the formulated problemwithout a relay in [7] except the rate function for the relays and the terminals con-nected to the relays are modified by adding additional terms due to the constraint inEquation 3.4 and its associated dual variables. The way of obtaining optimal solutionvector (x,P) for this problem has been discussed in [7]. Having observed the highcomputational complexity of the optimal solution, the authors in [7] have proposed afew suboptimal algorithms. We plan to use these suboptimal algorithms (SOA1 andSOA2) in order to obtain resource vectors (x,P) for the given Λ. We have extendedboth heuristics in order to achieve our desired objective. SOA1 has also two variants.We have used variant 5A since variant 5B uses constant power for each allocated RBwhich is not pragmatic. In this section, we have used SOA1(5A) in order to obtainx and P. SOA1 runs NRB number of times, and in the jth iteration, node t∈T∪Kcomputes the following metric for its best RB, denoted by lt(j)33Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsgt(j) =∑j∈Ωt(j−1)∪lt(j)log(1 +Ptetj|Ωt(j − 1)|+ 1)−∑j∈Ωt(j−1)log(1 +Ptetj|Ωt(j − 1)|),(3.10)where Ωt(j) denotes the set of the tth node’s accumulated RBs in the jth itera-tion. We define the first and second terms of Equation 3.10 as gat (j) and gbt (j),respectively. The metric defined in such way is for the throughput maximizationscheme, whereas for ensuring Nash bargaining fairness, metric gt(j) is considered aslog(gat (j))− log(gbt (j)) which has been proved in [8]. The following lemma shows andproves the way this metric has been computed for our relay oriented problem.Lemma 3.1: For relay k∈K, gk(j) is computed as (1− Λk)gak(j)− (1− Λk)gbk(j)and for its descendents t∈Tk, gt(j) is computed as (1 + Λk)gat (j)− (1 + Λk)gbt (j).Proof : If we compare the uplink scheduling problem of [7] and our Equation3.8, we notice, the rate function of the kth relay is replaced by (rk − Λkrk) and therate function of its descendents is replaced by (rtk − Λkrtk), rest of the other nodes’contribution towards the objective function are as same as it is in Equation (UL) of[7]. The selection criterion of OFDM tone in SOA1 (5A)[7], gi(n) is just the functionof rate accompanied with the OFDM tones from sets Ki(n) and Ki(n) ∪ li(n). Weredefine set K as Ω. Since the selection criterion is just a rate function of some setwith RBs, it is for the kth relay would be set as gak(j) − gbk(j) − Λk(gak(j) − gbk(j)),i.e., (1− Λk)gak(j) − (1− Λk)gbk(j). Similarly, for its descendant nodes (t∈Tk), gt(j)is defined as gat (j)− gbt (j)− Λk(gat (j)− gbt (j)), i.e., (1 + Λk)gat (j)− (1 + Λk)gbt (j).Once we obtain the suboptimal x and P, and we substitute in Equation 3.8, theright hand side of the equation becomes the function of Λ, i.e., L(Λ). The solutionto Equation 3.7 is given by minimizing L(Λ) over Λ >= 0. Moreover, L(Λ) isdiscontinuous and non-differentiable with respect to Λ. Hence, we use subgradient34Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsbased search approach in order to obtain optimal Λ. In each iteration of the searchmethod, for the given Λ, the suboptimal algorithms [7] find resource vectors (x,P).Iterations continue until the optimal Λ is obtained. Each step of the search methodupdates Λk in the following wayΛk(u+ 1) =∣∣∣∣∣Λk(u) + κk∣∣∣∣∣∑t∈Tkrtk − rk∣∣∣∣∣∣∣∣∣∣ , k = 1, · · · , NK .The value of Λk(u) can be both positive or negative because of the equality con-straint associated with this dual variable. If we look at Equation 3.8, it is rational tosay that the absolute value of Λk is in between 0 and 1. This is because, no matterthe value of κk is positive or negative, if its absolute value becomes greater than 1,either the terminal nodes’ (t∈Tk) or the kth relay’s individual utility turns out tozero or negative value which is not a desired expectation of this maximization prob-lem. In order to obtain optimal Λ, the ideal requirements are the continuous natureof function L(Λ) and the optimal value of L(Λ) is known. Since the Lagrangian func-tion does not have any of the properties, we have proposed an iterative, suboptimal,adaptive approach in order to find Λ∗ which gives more privilege to the independentuser nodes. At the first iteration,∣∣∣ ∂L∂Λk∣∣∣ gets the largest value, the following iterationsgradually reduce this term until Λ∗k is achieved. Given this observation, κk is setonly at the first iteration, i.e,∣∣∣ ∑t∈Tkrtk−rk∣∣∣, this quantity remains constant in thesubsequent iterations. How does  look like, is given in Observation 3.1.Observation 3.1: Because of the discontinuity nature of L(Λ) and also from thesimulation, we observe, if the value of  is≤ 0.1, nearly optimal solution is achievable2.With large value of  which is > 0.1, the iterative Λ update procedure requiresless number of iterations to achieve convergence, however the accuracy deteriorates.2Setting  as ≤ 0.1 provides the reasonable tradeoff between the accuracy and speed.35Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsTherefore, the value of  is the tradeoff between the accuracy and speed.3.5 Proposed Algorithms3.5.1 Iterative Λ Update ProcedureAn iterative algorithm for updating Λ using suboptimal algorithm SOA1 [7] is givenin Algorithm 1. This algorithm is adaptive, if there is a lack of resource or setup ofany relay and its terminal nodes is infeasible, dynamically it can disable that relayor can disconnect terminal nodes from the corresponding relay. In this subsection,we will explain how this algorithm works. Before getting into the loop of obtainingresource vectors (x∗,P∗), we will discuss different categories of relay placement. Thepositions of relays and their terminal nodes can be infeasible. Under the infeasiblesetup of any relay, the inner loop for obtaining the principle resource vectors does notexecute. We define the feasibility of a relay as a setup, when (1) there are multipleterminal nodes connected to that relay, the rate obtained by the relay is larger thanthe sum rate of its terminal nodes, (2) there is only one terminal node connected tothat relay, achieved rate by the relay can be lower compared to the terminal one, andvice versa. The rest of the other possible setups are considered as infeasible. Lines[7 − 21] are for checking the feasibility of each relay and turns them to the feasibleone if necessary. The vector Λ does not get updated unless all relays in the networkyield to the feasible ones. If any relay is found such that its rate is lower than the sumrate of its terminal nodes (attached to it), the algorithm looks for the terminal nodewith the largest (lowest) rate, disconnects it from that relay, makes it independentand runs the inner loop resource allocation algorithm. This operation for that relaycontinues unless the rate re-achieved by the relay is larger than the sum rate of its36Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsdescendent nodes, or there is only one node remaining attached node to that relay.Once all relays are feasible, resource allocation is conducted across all nodes in thenetwork taking vector Λ into account. Λ is updated in each iteration and the innerloop for the resource allocation is re-executed for the updated Λ. This procedurecontinues unless all relays in the network achieve convergence. The convergence for arelay is achieved when its rate is approximately equal to the sum rate of its attachednodes, slightly larger rate of the relay is preferred. While continuing the Λ updateprocedure, any or some relays can be infeasible. Infeasibility happens when eitherthe rate of a relay or a terminal node becomes 0. However, if a relay is in the ratedecrementing process, obtaining 0 rate is considered as convergence for that relay ifthere is no starved independent node in the network. The reasons behind obtaining0 rate in each iteration: (1) if the relay is in the process of decrementing its rate andits channel quality in any RB is so good or it has more usable power that it cannotallocate any RB meeting the upper limit of the decremented rate, (2) if the relay is inthe process of incrementing its rate and its position is not that good or there is a lackof RB due to the consumption by others, it cannot allocate any RB while satisfyingthe lower limit of the incremented rate. Similar phenomenons go with the terminalnodes attached to the relays. In either case, if the achieved rate for the relay or anyof its terminal nodes appears to 0, that corresponding relay becomes infeasible. Ifthe rate of all terminal nodes attached to any relay becomes 0 or the relay’s ratebecomes 0 and there is some starved independent node, that relay is forced to bedisabled. Whenever such situations happen, the Λ update procedure is reinitialized(Lines [35− 37] in the algorithm). In the algorithm, we have defined a flag vector Ffor all nodes: 0 for the independent node, −1/− 2/− 3 for the relay when its rate islarger than the sum rate of its terminal nodes, when its rate is lower than the sum37Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsrate of its descendants and when it is disabled, respectively. The node with the flagvalue greater than 0 is for a terminal node attached to any relay and the flag denotesthe index of the corresponding relay. Vector θ keeps the track of feasibility status forall relays.As we discussed before resource allocation procedure is inside the inner loop, it isalmost similar to SOA1 algorithm presented in [7] except the marginal utility gk|t(j)is computed using the formula (gak|t(j)± Λkgak|t(j))− (gbk|t(j)± Λkgbk|t(j)) for the kthrelay or the tth terminal node (t∈Tk) attached to it. Instead of computing gk|t(j)using Λ, we can compute it in a regular manner as presented in [7], but for the relayor terminals nodes, we need to keep another variable which is called virtual rate. Thevirtual rate is computed in each iteration after resource allocation is performed. Inthe algorithm, virtual rate vector is defined as V. At the beginning, the virtual ratefor all nodes is initialized as ∞. For the independent nodes, over the iterations ofthe algorithm, it remains unchanged. However, for the kth relay, the virtual rate is(rk ∓ Λkrk) and for the t∈Tkth node, it is (rt ± Λkrt). ± sign is for the flag value−1 and −2 of the kth relay, respectively. Similar computation goes for the otherrelays. Lemma 3.2 proves that resource allocation using virtual rate is approximatelyequivalent to the original procedure.Lemma 3.2: Inside the inner loop, if the flag value of the kth relay is −1, itsupper bound of rate is rk − Λkrk, its t∈Tkth descendent’s lower bound of the rateis rtk − Λkrtk. Whereas, when the flag of the kth relay is −2, its upper and tthdescendent’s lower bound of the rate are rk + Λkrk and rtk − Λkrtk, respectively.The upper bound of the rate for the independent nodes is considered as ∞. Havingconsidered these assumptions, the selection criterion of RB follows the same procedureas in SOA1(5A) [7].38Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsProof: In the original procedure illustrated in Lemma 3.1, we have seen, the RBselection criterion gk(j) for the kth relay has additional term Λk(gak(j)− gbk(j)) sub-tracted from it. Similarly, for the kth relay’s descendent node t∈Tk, gt(j) has theadditional term Λk(gat (j) − gbt (j)) added to the original one. It means, no matterfor the relay or its adjacent nodes, their instantaneous rate is just subtracted/addedby some term which is proportional to Λk. Intuitively, instead of computing gk|t(j)using Λk, we can use some sort of customized rate to limit their upper or lowerbound. While doing resource allocation inside the inner loop, we do not know inadvance the instantaneous rate of all nodes, hence we take the rate obtained in theprevious iteration and compute their customized rate using Λk(∀k∈K) as depictedin Lemma 3.2. The resulting resource allocation produces approximately the similaroutcome as given by the original procedure. The above arguments are for the relaywhose flag is −1. In the similar manner, for the flag value −2, it can be justifiedthat considering the upper bound of virtual rate for the kth relay as rk + Λkrk andits connected (t∈Tk)th node’s lower bound of virtual rate as rtk −Λkrtk, if we followSOA1 [7], the resultant scheduling decision does not make much difference. The RBselection criterion of the independent nodes is not influenced by the dual variables ofthe relays, and hence their upper bound of rate is ∞.3.5.2 Low Complexity Suboptimal AlgorithmAs explained above, Algorithm 1 undergoes a number of iterations before all relaysin the network achieve convergence. However, in the fast fading environment, thescheduler may need to take quick RB allocation decision because of smaller schedulinginterval. Considering this issue, we have presented a suboptimal Algorithm 3 whichperforms scheduling decision without considering Λ. This algorithm is similar to39Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsthe original RB allocation algorithm, SOA1 except a terminal node connected to therelays checks feasibility of its current possible RB allocation with respect to its relaywhich is depicted in the lines [10−14] of Algorithm 3. The way of maximizing overallrate and ensuring fairness across the nodes, the criterion of SOA1 works followingthe similar manner explained in the previous section.3.5.3 SOA2 Extended AlgorithmWe have extended SOA2 [7] as follows. This algorithm has 2 steps: RB numberassignment nt, t∈T∪K and actual RB-node matching determination. In order toachieve the first objective, we need to solve the following problem in Equation 3.11maxnt>=0,nk>=0∑t∈T′′U ′t +∑k∈KU ′k +∑k∈K∑t∈TkU ′tk (3.11)s.t. :∑t∈T∪Knt <= NRB,∑t∈Tkr′tk ≈ r′k, ∀k∈K,where r′t =∑ntj=1 log(1 +Ptnte′t,j). For the throughput maximization scheme, U′t = r′t.and for ensuring fairness, U ′t = log(r′t). e′t is the sorted vector of et over all RBsin the descending order. r′k and r′tk have the similar interpretation as r′t has. Theobjective function in Equation 3.11 is a concave problem over a non-integer convexset {nt >= 0, t∈T∪K} and does not have duality gap. Taking the help of virtualthroughput discussed in Algorithm 1 and the dual variables, the resultant Lagrangianbecomes40Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsL(n, λ) :=∑t∈T′′,r′t<=VtU ′t +∑k∈K,U ′k<=VkU ′k+∑k∈K∑t∈Tk,r′tk<=VtkU ′tk − λ(∑t∈T∪Knt −NRB).For a given λ, the optimal solution of above problem can be obtained by solvingthe following NT +NK sub-problems. We can solve each sub-problem by a bisectionsearch over the range [0, NRB].nt(λ) := argmaxnt,r′t<=Vt(U ′t − λnt) , ∀t∈T∪K. (3.12)Let the solution of all sub-problems are n∗t (λ), t∈T∪K, and the resultant utilitiesare U∗t (λ), t∈T∪K. Substituting these back to the LagrangianL(λ) :=∑t∈T′′U∗t +∑k∈KU∗k +∑k∈K∑t∈TkU∗tk − λ(∑t∈T∪Kn∗t (λ)−NRB),which is a convex function of λ. The optimal value of λ results in the minimumvalue of L(λ) and can further be obtained by another bisection search over therange [0,max{maxt∈T U ′t ,maxk∈K U ′k}]. The computational detailed complexity ofeach procedure is given in [7]. Integer approximation of n∗t , t∈T∪K is performed asfollows. We sort the nodes according to the mantissa of n∗t , fr(n∗t ) = n∗t − bn∗t c. Itproduces a node permutation set αt, t∈T∪K such that fr(n∗α1) >= fr(n∗α2) >= · · · .Then, we calculate the number of unallocated RBs, NARB = N −∑t∈T∪Kbn∗t c. Fi-nally, we adjust the nodes with large mantissas such that all unallocated RBs, NARBare allocated, i.e., n∗αt = bn∗αtc+ 1.41Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsOnce we have RB number assignments n∗t , t∈T∪K, our next objective is to findout actual node-RB mapping. For this, we have followed exact SOA2-CUM procedureof [7]. For this purpose, they have used Hungarian Algorithm which requires virtualnode splitting. We denote Utj as the utility of the tth node over RB j, and Utas the utility vector over all RBs, j∈R. For the throughput maximization and fairschemes, Utj is rtj and log(rtj), respectively; rtj is the rate of the tth node on RB j.In the similar manner, if we denote the utility vector for other nodes, we can makematrix Γ =[UT1 ,UT2 , · · ·]Twith size (NT +NK)×NRB. Next, we need to split eachnode t into n∗t virtual nodes by adding n∗t − 1 copies of the row vector to matrix Γ.The size of the expanded matrix would be (NT + NK)×N ′RB, where N ′RB <= NRB.Now, if we define the permutation matrix C with size (NT + NK)×N ′RB and solveproblem (19) of [7], we obtain our desired node-RB mapping matrix C∗. If we applyHungarian Algorithm to our problem without any modification, the resultant kthrelay’s rate might become lower than∑t∈Tk rtk, which is not feasible. In order tomake all relays feasible, we need to follow either of the following steps.• While solving the problem in Equation 3.11, if we obtain our gain vectore′k, k∈K as the ascending order of ek, while keeping the gain vector of othernodes as the descending order, the resultant final outcome ensures that eachrelay obtains larger rate than the sum rate of its descendant nodes.• Another alternative is as follows: we obtain the gain vector of all nodes in thedescending order, however we want to apply some tricks on matrix Γ. First,we get a RB set R′ with size∑k∈K n∗k which contains best possible RBs for allrelays. Then, we fix the rows of matrix Γ such that Utj = 0, t∈T, j∈R′.42Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systems3.5.4 Performance Improvement using Power ControlNow, we are set with power and RB allocation (x∗,P∗) for all nodes t∈T∪K. For thetth node, the set of RBs is IRB,t. The algorithms presented before subdivide powerPt among all RBs uniformly, j∈IRB,t. Therefore, allocated power pt,j on RB j can beover-shot or under-shot. Hence, there is a scope of optimizing power for the settledtth node. We can formulate the problem as followsargmax∑jpt,j = Ptχt(x∗, Pt) ∀t∈T∪K. (3.13)The dual function for the problem in Equation 3.13 is Lt(x∗, λt). The solution ofthe dual problem is λ∗t = argminλt>0 Lt(x∗, λt). A solution of the dual problem existsif and only if λt =|IRB,t|Pt+∑j∈IRB,t1et,j. This statement can be verified by the equation,∑j∈IRB,t(1λt− 1et,j)− Pt = 0. |IRB,t| is the length of set IRB,t. Given λ∗t , optimalpower allocation for the problem in Equation 3.13 is pt,j = 1λ∗t −1et,j, ∀j∈IRB,t.This type of problem and solution has already been given in [81] for the downlinktone allocation in OFDM-based systems. Their problem has an upper bound ofSINR for each OFDM tone, whereas we do not have that restriction. They alsohave provided an iterative algorithm in order to obtain optimal λt. Since we do nothave the SINR upper bound constraint, we have shown the modified algorithm inAlgorithm 5. Before initiating the algorithm, we need to have one vector at whichcontains SINR et,j for the RBs in set IRB,t, i.e., at = {et,j}j∈IRB,t . The complexity ofthis algorithm for the tth node is |IRB,t|. Since there are NT +NK number of nodesin the network, the overall complexity for this decision is∑t∈T∪K |IRB,t|.In the first 3 subsections of this section, we have proposed the generic Λ updatestrategy (applicable to both SOA1 and SOA2), a low complexity suboptimal RB43Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsallocation algorithm with the help of original OFDMA tone allocation scheme, andrelay oriented SOA2 algorithm which takes the assistance of the generic Λ updatetechnique described in the first subsection. In the 4th subsection, we have given theoptimal power allocation strategy of a node once it obtains RBs using the previouslydiscussed methods.3.6 Performance EvaluationWe have implemented relay enabled proposed algorithms in matlab and evaluate theperformance of those comparing with the ones without relay [7] assuming the utilityas both mere rate and the logarithmic of rate. In the following subsection, we describehow we configure the parameters of a network to perform our desired performanceevaluation, and then in the next subsection, we show some results to justify ourarguments.3.6.1 Simulation MethodologyFor setting up the network, we put the base station at the center, user nodes atdifferent distance surrounding the base station. We also deploy some relay nodes inorder to pass data from the edge nodes to the base station. We run the simulationover 200 TTIs. One TTI is equivalent to 1 ms and it consists of 50 RBs. Each RBis analogous to 12 subcarriers [6]. These total 50×12 subcarriers are spread over10 MHZ bandwidth. The theoretical limit [82] of channel capacity is β = −1.5ln(5Pb),where Pb is bit error rate (BER) and we configure it as 10−6. For the user node, themaximum power is set as 220 mW and for a relay, it is moderately a large numberdepending on the number of terminal nodes it serves. The way how channel gain iscomputed is given in Equation 3.1. All results described in the following subsections44Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsFigure 3.2: Simulation scenario (setup-1).are the average of 20 simulation runs.In the following subsection, we compare our algorithms based on utility function,U = r, with the original algorithms without relay [7] in terms of different performancemetrics. Then, we compare the algorithms based on two utility functions, i.e., U = rand U = ln(r). In all figures, for the utility function U = r, we denote Algorithm 1,Algorithm 3 and Algorithm 4 as sopt(1), sopt(2) and sopt(3), respectively. On theother hand, for the utility function U = ln(r), we indicate them as fsopt(1), fsopt(2)and fsopt(3).The physical structure of the simulated cell looks like a circle. The base stationis at the center of the circle. We have designed a few scenarios in order to evaluatethe performance of our proposed algorithms by placing terminal nodes at differentdistance from the center of the circle. The Rayleigh fading effect is statisticallysimilar for all nodes in the network. Therefore, the distance as well as the shadowing45Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systems10 15 20 25 30 35 40 45405060708090100110120130Number of UsersSystem Throughput (Mbps) SOA1 w/o relaySOA2 w/o relaysopt(1) w. relaysopt(3) w. relaysopt(2) w. relayFigure 3.3: System throughput comparison among our relayed algorithms and thosewithout relay (setup-1).effect plays the pioneer role to distinguish the channel gain among them. Quite a lotscenarios are possible in terms of nodes placement in the network. It is not worth toshow results of all scenarios, however we have justified the efficacy of our solutionsby illustrating the results of some.3.6.2 Simulation ResultsFirst, we will show the results in terms of average system throughput, fairness, uti-lized number of RBs, number of active relays, number of terminals nodes served bythe relays, etc. To measure the fairness quantitatively, we use Jain’s fairness indexalgorithm [83]. This is a well-known metric used in network engineering to determinewhether users or applications receive fair share of system resources. This metric isdefined as follows46Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systems10 15 20 25 30 35 40 45405060708090100110120130Number of UsersSystem Throughput (Mbps) sopt(1) w. relaysopt(3) w. relaysopt(2) w. relayfsopt(1) w. relayfsopt(3) w. relayfsopt(2) w. relay(a) System Throughput vs. Number of Users10 15 20 25 30 35 40 450.350.40.450.50.550.60.650.70.750.8Number of UsersJain Fairness Index sopt(1) w. relaysopt(3) w. relaysopt(2) w. relayfsopt(1) w. relayfsopt(3) w. relayfsopt(2) w. relay(b) Jain Fairness Index vs. Number of UsersFigure 3.4: Comparison between throughput maximization and fair algorithms(setup-1).47Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsfairness(r1, r2, · · · , rn) =(∑iri)2(n.∑ir2i) ,where r1, r2 · · · represent individual nodes’ throughput. Tentatively, we considerthere are a few independent nodes and a few edge nodes in the network. We haveplaced some relays in order to help the edge nodes forwarding their data. For thepurpose of clarity, we enumerate a few scenarios: (1) the channel condition of someor all relays can be statistically better/worse/equal than that of some or all indepen-dent nodes, (2) the channel condition of some or all edge nodes can be statisticallybetter/worse/equal than that of some or all relays, etc. The channel gain of the edgenodes is computed considering its physical location with respect to its relay node. Inall cases, our algorithms are adaptive, i.e., if we cannot accommodate relays due tothe constraint of resource (power or RB), the scheduler does not count on those relaysand assume their connected user terminals as the independent ones. Four scenarioswe have presented, have 4 different contours at different distance around the basestation on which we have placed our terminal nodes. The relay nodes are placedat the 5th contour. In the similar manner, as mentioned in the analytical section,we denote the number of terminal nodes as NT . Among these nodes, NT/2 is thenumber of independent nodes and the rest of them are edge nodes. Every 2 edgenodes, one from the 3rd contour and another one from the 4th contour are connectedto 1 relay placed at the 5th contour. Therefore, the number of relays in the networkis NK = NT/43.3One of the assumptions of this work is that the routing information of the network is pre-configured. Hence, even if the nodes would be placed in a random manner, the route informationof each node would need to be configured manually. To avoid this manual configuration, we wouldhave followed some sort of design for the network setup.48Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsFor the first scenario, the contours of the independent nodes are [0.3; 0.4] kmaway and the contour of the relays is 0.4 km away from the base station. Other twocontours for the edge nodes are [0.7; 0.8] km away from the base station, whereasfrom the designated relay, they are approximately [0.3; 0.4] km away. Figure 3.2depicts such system where the 5th contour is superimposed on the 2nd contour.Figure 3.3 illustrates gradual increment of system throughput with the increasingNT . The more the number of users, the higher the throughput which is obvious inthe figure. For using relays, our proposed solutions achieve higher throughput thanwhen they are not used. As presented in [7], SOA2 has higher throughput thanSOA1. Therefore, relay enhanced SOA2 has the highest performance except whenthe number of nodes in the system is 48, this is because sopt(3) is more intolerantthan sopt(1) in achieving convergence and hence less number of relays remain activeby the former one compared to the later one as we increase the number of nodes in thesystem. Moreover, with the increased number of terminal nodes, the number of relaysis increasing as well. However, in each scheduling epoch, there is a limited numberof RBs. In this scenario, the channel gain for half of the independent nodes is bettercomparing with the relay ones, the channel condition for half of the independentnodes is almost similar to the later ones. Moreover, maximum transmit power of therelays is larger than that of the regular terminal nodes. Therefore, when they havestatistically similar channel gain, the relay nodes have higher priority in schedulingdecision. At the first few data points, when the number of nodes is less comparedto the number of available RBs, all of the relays stay active and all edge nodesconnected to them are served properly because of the availability of RBs. Table 3.2shows these findings of our scheduling algorithms. With the increased number ofnodes, the scheduler cannot accommodate relays any more for the lack of resource49Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systemsand increased number of starved independent nodes. However, the channel conditionand power of the relay nodes are better than the independent ones, we see, even forthe number of nodes 48, sopt(1) ensures some active relays and edge nodes servedby them. If we would gradually increase NT , we would see decremented number ofrelays as well as decremented number of edge nodes.Table 3.1 shows the average number of used RBs in each scheduling epoch. Thistable proves that at low load, the scheduler leaves some unallocated RBs when relaysare not used. This has motivated us to place some relays in order to serve edgenodes, which improves the performance of the edge nodes as well as the overall one.Moreover, precisely from the simulation, we have seen an interesting phenomenonwhen there are 3 remaining RBs unallocated and there are 3 edge nodes and 1 relayto serve them. Instead of subdividing 3 RBs among 3 edge nodes, giving 1 to therelay and other 2 to the edge nodes incur better performance comparing with theformer one. At low load, even after deploying relays, all RBs are not used at eachscheduling epoch. With the increased number of employed nodes, all RBs are utilizedby either the terminal nodes or relays.When the utility function is defined as mere rate, attained throughput is muchlarger comparing with the case when it is logarithmic of rate which has been depictedin Figure 3.4(a). However, if we look at Figure 3.4(b), fairness is much better withU = ln(r) than that with U = r. Thus, taking or not taking logarithmic functionintroduces the tradeoff between throughput maximization and fairness.In the second scenario, the contours of the independent nodes are [0.2; 0.3] kmaway from the base station. The positions of the relays and edge nodes are as sameas in the previous scenario. The basic observations in Figure 3.5, such as increasedthroughput with increased number of terminal nodes, having better performance of50Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systems10 15 20 25 30 35 40 45150200250300350400450Number of UsersSystem Throughput (Mbps) SOA1 w/o relaySOA2 w/o relaysopt(1) w. relaysopt(3) w. relaysopt(2) w. relayFigure 3.5: System throughput comparison among our relayed algorithms and thosewithout relay (setup-2).our algorithms with the deployed relays than that without relays, existence of tradeoffbetween throughput maximization and fairness due to two utility functions are assame as before. In this setup, the channel gain of all independent nodes is betterthan that of the relays. Therefore, with the increased number of nodes, the schedulerruns out of RBs and it subdivides available RBs among the nodes with better channelquality, i.e., independent nodes. As a result, we see, when the number of nodes is 48,no relays remain active and hence all edge nodes connected to the relays are treatedas regular independent nodes. With Algorithm 3, we still see some active relays, thisis because this algorithm does not try to reduce the duality gap. It just allocatesresource among the independent nodes including relays based on the marginal utility.Since the maximum power of the relays is larger, some relays still have chance tohave some RBs even when they have worse gain than the independent nodes fromthis scheduler’s point of view. This scheduler gives privilege to the edge nodes if andonly if their relays already have some allocation. On the other hand, our extended51Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systems10 15 20 25 30 35 40 4510152025303540455055Number of UsersSystem Throughput (Mbps) SOA1 w/o relaySOA2 w/o relaysopt(1) w. relaysopt(3) w. relaysopt(2) w. relayFigure 3.6: System throughput comparison among our relayed algorithms and thosewithout relay (setup-3).SOA1 and SOA2 go through a process of reducing duality gap for the constraint inEquation 3.4, and it becomes almost impossible when there is a constraint of resourcewith the increased number of terminal nodes. Because of these reasons, when thenumber of terminal nodes is large, Algorithm 3 can accommodate a few relays as wellas few edge nodes, and therefore it incurs slightly larger throughput comparing withothers. This increased performance can be assumed as negligible. Whereas with ourother heuristics, since the scheduler deactivates almost all relays, their performancereduces to the original ones. Table 3.2 is for the active relays and edge nodes for thisscenario. Moreover, Table 3.1 reflects average number of used RBs resulting fromthis scenario.The third scenario is the opposite of the second one. The contours of the indepen-dent nodes are placed at [0.5; 0.6] km away from the base station, i.e., the channel gainof all relays is larger than theirs. Because of this reason, the relays always have moreprivilege in terms of RB allocation even when the number of nodes in the network52Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systems10 15 20 25 30 35 40 45152025303540Number of UsersSystem Throughput (Mbps) SOA1 w/o relaySOA2 w/o relaysopt(1) w. relaysopt(3) w. relaysopt(2) w. relayFigure 3.7: System throughput comparison among our relayed algorithms and thosewithout relay (setup-4).is large. Therefore, our main heuristics have more flexibility in reducing the dualitygap for each relay and rearrange RBs among the relays and edge nodes. However, atincreased load, the scheduler cannot fully ignore all independent nodes and it is hardto achieve convergence for all relays because of the resource constraint. Hence, togive more provision to the independent nodes, the scheduler deactivates some relays.Relay enhanced SOA2 is more intolerant in attaining convergence than Algorithm 1,which results in less number of active relays. Due to this reason, it has same or worseperformance compared to the other one at some points which has been depicted inFigure 3.6. Whereas, Algorithm 3 is ignorant and hence it has always worse perfor-mance than the main ones. Other basic observations for this scenario are as same asfor the previous ones.For the above all cases, all relays are feasible even at the beginning of iterations.We have prepared setup-4 in such a way that the attained rate of the relay nodesis smaller than the sum rate of their edge nodes. Therefore, according to the steps53Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systems[7−21] in Algorithm 1, Algorithm 4, to make it feasible, one edge node from all relaysget disconnected and those nodes yield to be independent ones. The rest of the othersettings of this setup are as same as the 3rd one. Hence, if we look at Table 3.2, wesee, the number of active edge nodes is as same as the number of active relays evenwhen the system has less number of nodes, and has sufficient resource to serve. Sincethe channel gain of the independent nodes is not that good compared to the relaysand their edge nodes, the relays get more priority in consuming resource. Hence, wesee, at low load, all relays remain active by serving their only one connected edgenode. However, with the increased load, due to the lack of resource and starvedindependent nodes, more and more relays cannot be active. Since relay enhancedSOA2 is more intolerant, at higher load, it cannot serve as many relays as sopt(1)can. Since sopt(2) is ignorant of allocating resource for the independent nodes, relaysand their connected edge nodes, at higher load, more relays are active whereas theirconnected nodes do not get any RB which is just the wastage of resource. The restof the other observations are as same as for the previously discussed scenarios.In order to see what happens to each single independent node because of thedeployed relays, we have made a scenario with 8 terminal nodes and 1 relay. The5th node is relay and it serves last 2 nodes. The distance of the nodes towards thebase station is [0.2; 0.3; 0.4; 0.45; 0.6; 0.7; 0.85; 0.9] km. Figures 3.8 and 3.9 illustrateaverage throughput and the number of allocated RBs for each single user, respectively.Most important observation from these 2 figures is, better independent nodes havelower throughput than the original ones because of taking away better RBs by therelay. Due to the employed relay, the best independent node has a lower number ofRBs than the original ones. However, the employed relay improves the performanceof the edge nodes drastically, whereas SOA1 and SOA2 cause starvation to them.54Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed Systems0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 105101520253035404550User Distance (km)User Throughput (Mbps) SOA1 w/o relaySOA2 w/o relaysopt(1) w. relaysopt(3) w. relaysopt(2) w. relayFigure 3.8: Individual user’s throughput as a function of the distance from basestation.0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1012345678User Distance (km)Total Allocated RBs SOA1 w/o relaySOA2 w/o relaysopt(1) w. relaysopt(3) w. relaysopt(2) w. relayFigure 3.9: Individual user’s allocated RBs as a function of the distance from basestation.55Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsSOA2 gives more provision to the nodes with better channel and so does the samerelay enhanced SOA2 compared to sopt(1). Because of the property in Figure 3.1,even with the deployed relay, all RBs in each scheduling epoch are not used.3.7 Summary of the ChapterIn this work, we have presented the solution of the uplink scheduling for FD relayequipped LTE networks. First, we have shown optimization based formulation for ourdefined problem. From the dual formulation, we have noticed, we can use the sub-optimal algorithms proposed for OFDMA-based uplink scheduling problem withoutrelay [7]. Based on this finding, we have proposed a family of suboptimal algorithmsin order to perform resource allocation for our problem. Furthermore, for the fair re-source allocation across the system, we have given a Nash bargaining solution whichdoes not require much technical involvement on the top of the original formulationand its solution. Our proposed heuristics are adaptive, if due to the resource con-straint, the relays do not contribute much to the real consumers in the system, theyare recommended to be disabled. By designing some scenarios for actual systems,we have done extensive simulation on our proposed solutions and have proved thatrelays can enhance the performance of the system without consuming its obligatoryresources.56Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsTable 3.1: Total allocated RBs.Alg/# Users SOA1 SOA2 sopt(1) sopt(3) sopt(2)Setup-18 16 18 17 18 1216 24 30 31 32 2024 32 38 40 42 3132 40 44 46 48 3940 44 46 49 50 4548 50 50 50 50 50Setup-28 18 26 28 28 2116 28 48 32 48 2624 35 48 44 48 3032 41 50 49 50 4040 49 50 50 50 4648 50 50 50 50 50Setup-38 10 10 12 14 1116 18 20 20 32 1924 28 30 31 42 2932 36 40 40 48 3840 45 50 50 50 4648 50 50 50 50 50Setup-48 9 10 13 14 916 16 20 28 28 1724 24 30 29 30 2432 32 40 40 40 3240 40 50 48 48 4048 48 50 50 50 4657Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsTable 3.2: Number of active relays/edge nodes.Alg/ Tot # Rlys/# Users sopt(1) sopt(3) sopt(2) fsopt(1) fsopt(3) fsopt(2) Tot # EdgesSetup-18 2/4 2/4 2/2 2/4 2/4 2/2 2/416 4/8 4/8 4/4 4/8 4/8 4/4 4/824 6/12 6/12 6/6 6/12 6/12 6/6 6/1232 8/16 8/16 8/8 8/15 8/14 8/8 8/1640 10/10 10/10 10/10 10/10 10/10 10/10 10/2048 6/6 4/4 12/12 5/5 3/3 12/12 12/24Setup-28 2/4 2/4 2/2 2/4 2/4 2/2 2/416 4/8 4/8 4/4 4/8 4/8 4/4 4/824 6/12 6/12 6/6 6/12 6/12 6/6 6/1232 8/14 8/12 9/8 6/6 8/12 8/10 8/1640 10/10 10/10 11/10 9/9 8/8 10/10 10/2048 0/0 0/0 8/7 0/0 0/0 8/7 12/24Setup-38 2/4 2/4 2/2 2/4 2/4 2/2 2/416 4/8 4/8 4/4 4/8 4/8 4/4 4/824 6/12 6/12 6/6 6/12 6/12 6/6 6/1232 8/16 8/16 8/9 8/16 8/16 8/9 8/1640 10/17 10/15 10/11 10/17 10/15 10/11 10/2048 12/20 12/18 12/12 12/20 12/18 12/12 12/24Setup-48 2/2 2/2 2/2 2/2 2/2 2/2 2/416 4/4 4/4 4/4 4/4 4/4 4/4 4/824 6/6 6/6 6/6 6/6 6/6 6/6 6/1232 8/8 8/8 8/8 8/8 8/8 8/8 8/1640 9/9 9/9 10/10 9/9 9/9 10/10 10/2048 8/8 8/8 12/10 8/8 8/8 12/10 12/2458Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsAlgorithm 1 Iterative algorithm to determine (x∗,P∗).1: for k∈K do2: F(t) := {k}, ∀t∈Tk.3: end for4: V := {∞},θ := {0}, u := 1,Λ(u) := {0}.5: repeat6: Inner Loop for obtaining (x∗,P∗).7: for ∀k∈K do8: if NTk > 1 then9: if∑t∈Tk gbt (j) > gbk(j) then10: t∗ := argmaxt∈Tkgbt (j).11: F(t∗) := 0.12: else13: θ(k) := 1.14: end if15: else16: if∑t∈Tk gbt (j) > gbk(j) then17: F(k) := −2.18: end if19: θ(k) := 1.20: end if21: end for22: if ∀k∈K(θ(k) = 1) then23: if u = 1 then24: κ(k) := |∑t∈Tk gbt (j)−gbk(j)|, ∀k∈K.25: end if26: for ∀k∈K do27: F(t) := 0, θ(k) := 0, ∃t∈Tkgbt (j) = 0.28: if∑t∈Tk gbt (j) = 0 OR (gbk(j) = 0 AND ∃t∈T(F(t) = 0, gbt (j) = 0))then29: F(k) := −3, θ(k) := 0.30: end if31: Mark the kth relay if its convergence is achieved.32: end for33: if∑t∈Tk gbt (j) ≈ gbk(j), ∀k∈K then34: Convergence has been achieved.35: else if ∃k∈Kθ(k) = 0 then36: Initialize u, V and Λ.37: end if38: Follow Algorithm 2.39: end if40: until Λ∗ is found59Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsAlgorithm 2 Intermediate fraction of Algorithm 1.1: for ∀k∈K do2: if the kth relay is not converged then3: Λk(u) := Λk(u− 1) + κ(k) ∗ |∑t∈Tk gbt (j)− gbk(j)|.4: rf := F(k) = −2?1 : −1.5: V(k) := gbk(j)− (0− rf)Λk(u)gbk(j).6: V(t) := gbt (j) + (0− rf)Λt(u)gbt (j), ∀t∈Tk.7: end if8: end for9: Remove disabled relays from sets K and F.Algorithm 3 Suboptimal RB allocation algorithm.1: j := 0, Ωi(j) = ∅ for each terminal or relay i.2: for k∈K do3: F(t) = k, ∀t∈Tk.4: end for5: while j < NRB do6: j := j + 1.7: Update RB index li(j) for each node i.8: Calculate metrics gbi (j) and gai (j) for each node i.9: Set ξ := {i|F(i) <= 0}.10: for i∈{i|F(i) > 0} do11: if(∑t∈Tk,t 6=i gbt (j) + gai (j))<= gbF(i)(j) then12: ξ := ξ∪i.13: end if14: end for15: Find i∗ := argmaxi∈ξ(gai (j)− gbi (j)).16: if (gai∗(j)− gbi∗(j)) <= 0 then17: Break the loop.18: end if19: Assign the j’th RB to node i∗Ωi(j) ={Ωi(j − 1)∪li(j) if i = i∗Ωi(j − 1) Otherwise.20: end while60Chapter 3. Uplink Scheduling and Resource Allocation for DF Relayed SystemsAlgorithm 4 SOA2 extended RB allocation algorithm.1: Perform steps [1− 4] of Algorithm 1.2: Solve problem (10) and obtain resultant U∗t (λ∗), r∗t (λ∗), t∈T∪K.3: Map r∗t (λ∗) to gbt (j), t∈T∪K.4: Perform steps [7− 39] of Algorithm 1 which requires to repeat steps [2− 3] untilΛ∗ is obtained.5: Apply Hungarian Algorithm as described in order to achieve C∗, i.e., (x∗,P∗).Algorithm 5 Iterative algorithm for optimal λt.1: [a] = sort(a, ‘descend’).2: j := 0, Gn = 0, Gd = 0.3: j := j + 1.4: while j <= |IRB,t| do5: Gn := Gn + 1,.6: Gd := Gd +1at(j).7: λt(j) =GnPt+Gd.8: if λt(j) >= at(j + 1) then9: λ∗t = λt(j).10: Break the loop.11: end if12: end while61Chapter 4Joint Source and Relay PowerAllocation for AF Relayed Network(Centralized Solution)4.1 IntroductionEmerging relay technique in 3G/4G networks, such as LTE and LTE-Advanced hasbrought numerous problems to optimize its deployment. In recent years, cooperativerelay networks have received tremendous attention. Two most popular cooperationprotocols are considered - DF, AF [84]. DF relays retransmit just the replica ofsource’s transmitted signal. Whereas AF means, the relay nodes amplify source’ssignal first, and then retransmit towards the destination. We adopt the AF protocolin our work because of its simple signal processing mechanism. Our problem presentedin this chapter focus on a network having one relay node, a set of sources, and singledestination. Given fixed amount of power to be distributed among the sources andrelay is an optimization problem, and exhibits the trade off between fair resourceallocation and overall network performance. If resource is limited in the network,serving all sources may lead to the degradation of network capacity. In this situation,best possible few sources should be selected for the transmission while ignoring others.62Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)To put our work into context, we outline the chronological order of evolved re-search on the power optimization of AF relayed networks. At the beginning of suchexploration, people focused on a simple network with one source and one relay [39].And, then, relay power allocation for a single-source multi-relay network has ex-tensively been studied varying different optimization criterion, i.e., outage probabil-ity minimization or sum relay power minimization under the sources’ SNR or out-age probability constraints [40], [41], [42]. Performance optimization of multi-sourcesingle-relay network has also been given attention from different angles, such as inter-ference cancellation schemes are proposed in [43] and [44]. In [85] and [45], networkdecoding is applied to combat interference among the users. In [86], the resourceincluding both subcarrier and relay power allocation problem is studied to maximizethe sum rate. At the same time, joint multi-source multi-relay power optimizationhas appeared in a few papers [46], [47] under different optimization criterion, i.e., sumrate maximization, sum power minimization, etc. Although in [46], each source isessentially served by only one relay, [47] made performance improvement by assistingsingle source with the help of multiple relays. The drawback of their approach is, theyhave totally ignored SNR due to the direct link transmission in their optimizationformulation.Due to the inefficient bandwidth utilization of relays while transmitting on theorthogonal channels, at one point, many people gave emphasis on the best relayselection schemes. Multi-relay selection and their power allocation recently appearedin some works [87], [88], [89] because of their ability to attain better performance.Joint relay and opportunistic source selection for a bidirectional network has beenconsidered in [90] to optimize the outage probability and BER.In this chapter, we have formulated the problem considering individual source,63Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)relay, and total system power constraints. Total power constraint is imposed to reducethe interference in the neighboring network. Our formulated problem is almost similarto [46], [47], although [46] has not taken individual source and total power constraints,and in [47], each source is served by multiple relays4. The main drawback of theirwork is, they have totally skipped SNR due to the direct link in their formulation.Putting the direct link SNR in the original formulation, we have solved the problemusing GP. Because of the direct link SNR, the original problem is not amenable toGP. Hence, we have used single condensation method in order to solve this problemusing GP. Since the original problem has many variables, and single condensationmethod may need many iterations to attain convergence, we have transformed ourproblem to the problem with two variables (one source and one relay) which is muchcomputationally cheap. Once we obtain the source transmit power, we subdivide itamong all original sources using greedy and fair algorithms. For dividing the relaypower among them, we apply water filling method given that the sources are assignedwith transmit power using the proposed heuristics.The rest of the chapter is organized as follows. We explain the system modeland its detailed mechanism in Section 4.2. In Section 4.3, we provide the centralizedsolution of our defined problem. We evaluate the performance of this solution inSection 4.4, and finally we conclude the chapter in Section 4.5.4.2 System Model and Problem FormulationIn this section, we consider an LTE system, in which there exists a base station, onerelay node and N source nodes which need help from the relay to get their packets4For the sake of simplicity without losing the generality, we consider, the sources are served bya single relay node.64Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)Figure 4.1: System model.transmitted to the base station. The edge nodes essentially act as servers which havesome special applications and the destination node needs to get the content of thatapplication on time. For example, the application could be some video which needsto be displayed on the destination. The relay node amplifies the received signal fromthe source nodes and then forwards towards the destination as depicted in Figure 4.1.Although the system has one destination, the proposed solution can easily be adaptedto a multi-destination network. The transmit channel of each source or the relay isa single or aggregate RB(s). We assume a block-fading channel (or quasi-static)model: the channels remain invariant over a time slot whose duration is less thanthe coherence time of the channels. Denote the channel gain between source si anddestination d is Gsi,d; the channel gain between source si and relay r is Gsi,r; and thechannel gain between relay r and destination d is Gr,d.The entire transmission operation using the AF relay consists of two phases (i.e.,time slots). At each phase, the sources or relay use orthogonal RBs for multipletransmissions. At the first phase, source si broadcasts its information to both des-tination d and relay node r. The received signals ysi,d and ysi,r at destination d andrelay r can be expressed as65Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)ysi,d =√EsiGsi,dxsi + ηsi,d and ysi,r =√EsiGsi,rxsi + ηsi,r, (4.1)where Esi represents the transmit power at node si, xsi is the broadcast informationsymbol with unit energy from source si to nodes d and r. ηsi,d and ηsi,r are theadditive noises received at destination d and relay r, respectively. In the second step,the relay amplifies its received signal and forwards it to destination d. Denote thepower the relay uses to help source si is Eri . The signal received at destination d forsource si can be shownyri,d =√EriGr,d(√EsiGsi,rxsi + ηsi,r)√EsiGsi,r + σ2+ ηri,d. (4.2)ηri,d is the received noise from relay r to destination d (for source si). Without loss ofgenerality, we assume that the noise power is the same additive white gaussian noisefor all links, denoted by σ2. After maximum ratio combining of both the direct andrelay paths, the effective received SNR for source si’s transmission can be given byΓsi,r,d =EsiGsi,dσ2+EsiGsi,rEriGr,dσ2 (EsiGsi,r + EriGr,d + σ2). (4.3)If the set consisting of the source nodes is Ls = {s1, s2, · · · , sN}, the total capacityachieved by the system can be given byRs,r,d = γLW∑si∈Lslog2 (1 + Γsi,r,d) . (4.4)Because the transmissions are orthogonal, γL = 1/(2N) and W is the aggregatebandwidth in the system. Since W and γL are constants, we skip these terms in thesubsequent discussion.Our goal is to allocate power among the sources and relay so that the system66Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)capacity is maximized. As in traditional network resource optimization problems,there are constraints on the sources and relay power. Moreover, in order to mitigatethe interference imposed on another network due to the transmission operations inthis network, there is a total power constraint, meaning total power allocated tothe sources and relay node cannot exceed Emax. For the sake of simplicity, we haveconverted the maximization problem into the minimization one by introducing minussign in front of the objective function, i.e, Rs,r,d.min∏si∈Lsσ2(σ2 + EsiGsi,r + EriGr,d)(σ2 + EsiGsi,d)(σ2 + EsiGsi,r + EriGr,d) + EsiGsi,rEriGr,d(4.5)where Esi ≤ Emaxs , si∈Ls,∑si∈LsEri ≤ Emaxr ,∑si∈LsEsi +∑si∈LsEri ≤ Emax,{Esi}si∈Ls ≥ 0, {Eri}si∈Ls ≥ 0.The aforementioned optimization problem is valid if and only if∑si∈Ls Esi +Emaxr >Emax and∑si∈Ls Emaxsi> Emax.4.3 Centralized SolutionThe problem in Equation 4.5 is not convex due to the non-convexity property ofthe objective function. This statement can be proved very easily by the help ofspecial type of convex optimization formulation, i.e., GP [91, 92]5. A GP is a typeof mathematical optimization problem characterized by the objective and constraint5The objective function is the ratio of two posynomials, which is non-convex.67Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)functions that has a special form. It focuses on monomial and posynomial functions.A monomial is a function, h : Rn→R, where the domain contains all real vectorswith non-negative components, h(x) = cx1a1x2a2 · · · xnan . A posynomial is a sum ofmonomials, f(x) =∑kckx1a1kx2a2k · · · xnank . GP is an optimization problem withthe formminimize f0(x) subject to fi(x) ≤ 1, hj(x) = 1,where f0 and fi are posynomials and hj are monomials. This problem in the aboveform is not convex. However, with a change of variables: yi = logxi and bik = logcik,we can transform it into convex form given the assumption that the logarithm of asum of exponentials is a convex function.As mentioned, the objective function is the ratio of two posynomials which can-not be solved by GP. There are ways to transform such type of problem to GPform, i.e., single condensation method, double condensation method [92]. We haveused single condensation method which requires to approximate the denominatorof the objective function by some monomial term. We denote the denominator byF ({Esi}si∈Ls , {Eri}si∈Ls) and the resultant monomial is given by∏si∈Ls(σ2 + EsiGsi,d)(σ2 + EsiGsi,r + EriGr,d) + EsiGsi,rEriGr,d≈ λ∏si∈LsEaisiEbiri,where ai =EsiF({Esi}si∈Ls ,{Eri}si∈Ls)∂F({Esi}si∈Ls ,{Eri}si∈Ls)∂Esi,bi =EriF({Esi}si∈Ls ,{Eri}si∈Ls)∂F({Esi}si∈Ls ,{Eri}si∈Ls)∂Eri,and λ =F({Esi}si∈Ls ,{Eri}si∈Ls)∏si∈LsEaisiEbiri.68Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)The derivations are below∂F({Esi}si∈Ls ,{Eri}si∈Ls)∂Esi=[Gsi,d(σ2 + EsiGsi,r + EriGr,d) + (σ2 + EsiGsi,d)Gsi,r +Gsi,rEriGr,d]∏sj∈Ls,sj 6=si[(σ2 + EsjGsj ,d)(σ2 + EsjGsj ,r + ErjGr,d) + EsjGsj ,rErjGr,d],∂F({Esi}si∈Ls ,{Eri}si∈Ls)∂Eri=[Gr,d(σ2 + EsiGsi,d) + EsiGsi,rGr,d]∏sj∈Ls,sj 6=si[(σ2 + EsjGsj ,d)(σ2 + EsjGsj ,r + ErjGr,d) + EsjGsj ,rErjGr,d].Finally, the overall procedure for the joint source and relay power allocation isgiven as follows.1. Set the initial value of power E(0) :=[E(0)s1 , · · · , E(0)sN , E(0)r1 , · · · , E(0)rN], n := 1.2. Determine[a(n)1 , · · · , a(n)N],[b(n)1 , · · · , b(n)N]and λ(n).3. Solve the optimization problem with the help of GP.4. Denote the optimal power allocation in the nth round as E(n).5. If ||E(n) − E(n−1)|| ≤ , where  is a pre-defined threshold, the enumerationsstop; otherwise, n := n+ 1 and reiterate from step 2 to 5.The above procedure updates 2N principal variables in every iteration. Eachiteration needs to update 2N +1 number of intermediate variables to assist updating69Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)the principal variables. In order to simplify this procedure, we can consider, thesystem has only one source node denoted by s∗. Node s∗ is the representative ofall sources. The gain between node s∗ and node r is the weighted average of thegains between the sources and relay. In the similar manner, the gain between nodes∗ and node d is determined. After this transformation, the objective function is stillthe ratio of two posynomials. In order to cast it to GP, we can approximate thedenominator (denoted by H(Es∗ , Er)) of it by the monomial(σ2 + Es∗Gs∗,d)(σ2 + Es∗Gs∗,r + ErGr,d) + Es∗Gs∗,rErGr,d≈µEcs∗Edr ,where c = Es∗H(Es∗ ,Er)∂H(Es∗ ,Er)∂Es∗, d = ErH(Es∗ ,Er)∂H(Es∗ ,Er)∂Er, and µ = H(Es∗ ,Er)Ecs∗Edr. Further-more,∂H∂Es∗= Gs∗,d(σ2 + Es∗Gs∗,r + ErGr,d) + (σ2 + Es∗Gs∗,d)Gs∗,r +Gs∗,rErGr,d,∂H∂Er= (σ2 + Es∗Gs∗,d)Gr,d + Es∗Gs∗,rGr,d.The iterative procedure used to obtain optimal Es∗ and Er follows the sameprocedure mentioned above. However, it requires to update two principal variablesand three auxiliary variables in each iteration to achieve convergence. The followingtwo subsections are for distributing power E∗s∗ among all original sources, and thethird subsection is for disseminating relay power E∗r .70Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)4.3.1 Suboptimal Source Power Allocation (Greedy Solution)From the optimal solution, we have observed that the sources with better channelcondition obtain more power compared to others. Since each source has individualpower constraint and this power is moderately lower than the total allowable powerfor all sources, we can propose a greedy power allocation for the source nodes giventhe total allowable for them is E∗s∗ . If the direct link SNR of a source is better thanits relayed link one, it is likely, that source obtains zero relay power. Therefore, itis rational to distribute E∗s∗ among the sources taking direct link SNR into account.We sort Gsi,d, si∈Ls in decreasing order and allocate the maximum individual powerto each sorted source until there is no left over power.The above approach for distributing power among the sources is greedy. This issimilar to the MaxCIR technique [93] which assigns subcarrier among the users inOFDM-based networks according to their channel condition. The drawback of thisapproach is, the sources with worse channel may starve and may never get chanceto transmit as they are assigned zero power. This reminds us one important issue,which is called fairness. In order to tackle fairness, we have proposed an algorithmwhich considers both the instantaneous channel condition and fairness.4.3.2 Suboptimal Source Power Allocation (Fair Solution)At scheduling time instant t, we denote the gains between the sources and relay asa vector αt = {αt(1), αt(2), · · · , αt(N)}; the gains between the sources and desti-nation as a vector γt = {γt(1), γt(2), · · · , γt(N)}; the gain between the relay anddestination as βt. Moreover, the average rate of the sources is denoted by a vectorζ¯t = {ζ¯t(1), ζ¯t(2), · · · , ζ¯t(N)}. We initialize all elements of this vector as 0 at time71Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)t = 0. A fair algorithm is presented in Algorithm 66. The steps in the algorithm arefollowed in the channel coherent time of each time instant t.Algorithm 6 Fair algorithm for subdividing transmit power among the sources.1: Get αt, γt and βt.2: Sort γt in the descending order and get sorted index set I := {I1, I2, · · · , IN}.3: Set χ := E∗s∗ .4: for ∀i∈I do5: if ¯ζt−1(i) = 0 then6: η(i) := min (Emaxs , χ).7: χ := χ− η(i).8: end if9: end for10: if χ > 0 then11: Let the last unallocated index j := i.12: for ∀j∈I do13: Set M(j) := γt(j)¯ζt−1(j) .14: end for15: Sort index vector I according to the descending order of vector M.16: for ∀j∈I do17: Set η(j) := min(χ∗M(j)∑Nj=iM(j), Emaxs).18: χ := χ− η(j).19: end for20: end if4.3.3 Suboptimal Relay Power AllocationIn order to subdivide relay power E∗r among all sources, we have adopted water fillingapproach and the resultant formulated problem is given byargmax∑si∈LsEri = E∗r∑si∈Lslog2(1 +EsiGsi,rEriGr,dσ2(EsiGsi,r + EriGr,d + σ2)). (4.6)6Here, the fairness metric is the ratio of the user’s instantaneous rate in time instant t and itspast average throughput.72Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)By invoking the Lagrange multiplier µ for the total relay power constraint of theproblem in Equation 4.6, we obtain the Lagrangian∑si∈Ls log2(1 +EsiGsi,rEriGr,dσ2(EsiGsi,r+EriGr,d+σ2))+µ(E∗r −∑si∈Ls Eri). Following the K.K.T condition, we take the differentiation ofthe Lagrangian with respect to Eri , and we obtainµσ2(σ2 + EsiGsi,r + EriGr,d)2 + µEsiGsi,rE2riG2r,d + (4.7)µ(σ2 + EsiGsi,r)EsiGsi,rEriGr,d − (σ2 + EsiGsi,r)EsiGsi,rGr,d = 0.After simplifying, the resultant Eri is −EsiGsi,r+2σ22Gr,d+ 12Gr,d√E2siG2si,r+4EsiGsi,rGr,dµ.Substituting Eri , si∈Ls back into the equation∑si∈Ls Eri − E∗r = 0, we obtain theupper bound of µ, which is∑si∈Ls√4EsiGsi,rGr,d2Gr,dE∗r+∑si∈Ls(2σ2+EsiGsi,r). As the lower bound of µ is 0,we apply a bisection search between these two bounds in order to obtain optimal µ.Replacing the optimal µ in Eri , finally we obtain optimal Eri , i.e., E∗ri, si∈Ls.4.4 Performance EvaluationIn this subsection, we will evaluate the performance of our proposed solutions. Sec-tion 4.4.1 is for the methodology we have adopted to evaluate the performance andthe following one presents the results while comparing with the approach proposedin [46] and [47].4.4.1 Simulation MethodologyWe presume an LTE network with 5 source nodes, one relay and one destinationnode, i.e, base station. The maximum power of individual source is Emaxs = 30mW, and that of the relay node is Emaxr = 50 mW, the total available power in73Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)the system is Emax = 120 mW. Noise variance σ2 has been set as 1. The channelbetween two nodes suffers from the shadowing and Rayleigh fading effects. We takethe same channel model and the similar values of its parameters as mentioned inChapter 3. Moreover, we assume, each channel has a unit capacity. One of the majorassumptions of the works [46], [47] is, the channel condition between the source anddestination is always worse than that between the source and relay. However, thatnot necessarily happens in practice, and for the counter scenario, their model fails toprovide optimal solution. In order to fix the model up, we have considered the SNRdue to the direct link in our formulation, and the resultant solution is optimal whichis able to give better performance even when the direct link’s channel is better thanthat of the relayed link. In order to evaluate the performance of our solution, wehave selected 6 different scenarios, each of which has 5 distinct source nodes. In theevaluation part, we have denoted each scenario by Scenario Number. The positionsof all nodes are in the following coordinates:• Destination: (0,12).• Relay: (0,6).• Sources: X-coordinates are fixed at {−1,−2,−3,−4,−5} for all scenarios. IfScenario Number is denoted by ns, their Y-coordinates is 2ns, if ns∈{1, 2, 3, 4, 5};and 2ns, if ns = 6.All the results we have presented here are the average of 100 simulation runs.4.4.2 Simulation ResultsFigure 4.2(a) presents the total average system throughput with respect to 6 differentscenarios of the source nodes. Notice that the positions of the relay and destination74Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)1 2 3 4 5 61234567Scenario NumberSystem Throughput OptSopt−GreedySopt−FairGP w/o Direct Link [41,42](a) System throughput.1 2 3 4 500.10.20.30.40.50.60.70.80.91Source IndexIndividual Source Throughput Sopt−GreedySopt−FairGP w/o Direct Link(b) Individual source throughput.1 2 3 4 5 605101520253035404550Scenario NumberTotal Relay Power OptSopt−Greedy/FairGP w/o Direct Link [41,42](c) Total relay power.Figure 4.2: Comparison between our centralized solutions and others.75Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)Table 4.1: Source power comparison between optimal and suboptimal greedy solu-tions.Scenario s1 s2 s3 s4 s5Number Opt Greedy Opt Greedy Opt Greedy Opt Greedy Opt Greedy1 28.29 30 26.46 30 15.24 10 0 0 0 02 29.12 30 28.21 30 12.66 10 0 0 0 03 30.0 30 30 30 10 12 0 0 0 04 30.0 30.0 30.0 30.0 30.0 30.0 30.0 30.0 0 05 30.0 30.0 30.0 30.0 30.0 30.0 30.0 30.0 0 0Table 4.2: Source relay power comparison between optimal and suboptimal solutions.Scenario s1 s2 s3 s4 s5Number Opt Sopt Opt Sopt Opt Sopt Opt Sopt Opt Sopt1 36.19 35.01 13.78 14.98 0 0 0 0 0 02 36.96 35.91 13.031 14.08 0 0 0 0 0 03 32.24 31.12 17.75 16.84 0 0 0 0 0 0are fixed, we are varying the positions of 5 sources towards the destination. As thesources move to the destination, the resultant channel gain becomes better for them,hence gradually their throughput get improved. For the 5th and 6th scenarios, theabsolute distance between the sources and destination is close, however the sourcesare on the different sides of the destination. Since their absolute distances are close,the resultant throughput are close for these two scenarios. Now if we intuitivelycompare all approaches, for scenarios 1 and 2, the direct link’s channel condition isworse than the relayed link, the resultant outcome proposed by [46], [47] does notdeviate much from our optimal solution. For scenario 3, the channel quality of thedirect link is close to the relayed link and from this scenario, the procedure withoutconsidering the direct link SNR starts to differ from our optimal approach. And,for scenarios 4, 5 and 6, channel of the relayed link is worse than that of the directlink. For these scenarios, Figure 4.2(c) shows that allocated power for the relay is0, and the total allowable power is distributed among the sources considering their76Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)channel gain towards the destination. However, the technique without consideringthe direct link SNR always assigns full power to the relay no matter the relayed linkis worse or better than the direct link. Since our suboptimal approach for allocatingpower to the source and relay is based on somewhat weighted averaging of all gains,for scenario 3, relayed power by this approach is little less than the optimal one.For rest of the other scenarios, the suboptimal approach confers to the optimal one.Table 4.1 and Table 4.2 compare the detailed breakdown of power allocation betweenthe optimal and suboptimal schemes. We have noticed that once we obtain the totalallowable power for the sources, we can distribute this power among the sources by 2techniques, i.e., greedy and fair algorithms. From Figure 4.2(a), the greedy one hasclose performance comparing with the optimal one. Greedy algorithm gives privilegeto the sources with better channel condition, and makes starvation for others. Forbeing fair to the sources with worse channel condition, the resultant system through-put by the fair algorithm deteriorates compared to the other one. Even for scenarios1, 2, and 3, achieved throughput by this algorithm is worse compared to the GPsolution without considering the direct link SNR, however for the other scenarios, itoutperforms.Figure 4.2(a) has sources at different distance from the relay as well as from thedestination. In order to have detailed performance comparison of these four ap-proaches, for scenario 4, we have shown each individual source’s throughput contri-bution towards the overall performance of the system in Figure 4.2(b). In the X-axis,we put source node index and in the Y-axis, the corresponding node’s throughputcontribution has been projected. As discussed in the previous paragraph, the relaypower is 0 for this scenario. Therefore, the technique without considering the directlink SNR has worse performance except some fluctuation comparing with the fair77Chapter 4. Joint Source and Relay Power Allocation for AF Relayed Network (Centralized Solution)one. The greedy algorithm first assigns full allowable power to the source with thebest channel, and this process goes on for all sources with better channel qualityuntil the total allowable power runs out. Because of this nature of power subdivision,source 5 obtains 0 power since its channel condition is the worst compared to the restothers. The fair algorithm assigns some power to the sources with worse channel overthe time, and hence those sources contribute some throughput towards the overallperformance. Because of giving some privilege to this type of sources, the sourceswith the best channel quality obtain less amount of power compared to that obtainedby the greedy one. Therefore, with the fair algorithm, the source node with the bestchannel has worse performance compared to the greedy one.4.5 Summary of the ChapterIn this chapter, we have studied both transmit and relay power allocation problemin a multi-source single-AF-relay network. Since the existing works [46], [47] of thisproblem have not considered the direct link SNR in their formulation, the resultantsolution deviates from the optimal one if the direct link SNR is better than the relayedlink one. Having noticed this, we put the missing term in the original formulation,and have solved this using GP. Because of incorporating the direct link SNR in theproblem formulation, the problem is not directly amenable to GP. Hence, we haveused single condensation method in order to cast it to GP. Since this solution iscomputationally expensive with the growing number of sources, we also have giventwo suboptimal solutions. The suboptimal solutions are designed considering thegreedy and fair nature of the source nodes. Extensive simulation results verify thatthe proposed suboptimal solutions achieve close performance of the optimal one.78Chapter 5Joint Source and Relay PowerAllocation for AF Relayed Network(Game Theoretical Solution)5.1 IntroductionIn the aforementioned solution of our defined problem in Chapter 4, the nodes inthe network are assumed to be altruistic, and willing to cooperate in optimizing theoverall network performance. In many practical solutions, however, nodes are selfishand aim to optimize their own benefits or utilities, which may result in conflict ofsharing resource among them. Game theory is a flexible and natural tool to model,and analyze these behaviors of the nodes. This tool has extensively been appliedfor several problems in cooperative relay networks. In [94], uplink of a network withmultiple users can form a coalition in order to maximize their transmission ratesor utilities. In [95], [96], a bargaining game has been designed in order to showthe interaction between two users, where one user acts as a relay for the other onewith the purpose of attaining bandwidth [95] and power allocation [96]. In [97], theusers define the payment rates for the relays, and they share the payments amongthemselves who are willing to help the users. [98] shows cooperation for two nodes79Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)in two different mesh networks. An analytical framework is proposed to determinewhen the cooperation is beneficial, and the expected performance gain is estimated.Game theoretical power allocation for a multi-user multi-relay network has alsoextensively been studied. For example, non-cooperative game theory has been appliedto show the competition among the relays in order to assign optimal power.Theauthors in [99] have presented a solution for relay power allocation of such network,where two kinds of users are considered: variable, constant rate users. They haveused dual decomposition method in order to solve their formulated problem, andbased on that, they have given a distributed solution. For a single-user multi-relaynetwork, a two level Stackelberg game has been proposed in [100] for selecting the bestrelays and determine their power. For a multi-user single-relay network, source powerallocation problem has also been modeled using a two level Stackelberg game [101].The relay sets the price for the users, and they play a non-cooperative game in orderto maximize their individual utility. One more recent work for a multi-source single-relay network is [102] for the purpose of relay power allocation following some fairresource allocation rule. The relay acts as a leader and sets the price for power,whereas the users work as customers or followers for the purpose of maximizing theirutilities. In this work, since the relay needs to know the complete information of thenetwork, the same authors proposed a fully distributed relay power allocation schemefor the users [103].Having observed the non-convexity nature of our problem, and to model theselfish nature of the sources, in this chapter, we have proposed a game theoreticalsolution with two steps7. Two Stackelberg games operating in two consecutive stepshave been designed in order to solve this problem. For connecting these two games,7Since the joint sources and relay power allocation of this network is a non-convex problem, it isimpossible to capture this problem with a best-response-strategy-based single game.80Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)we have introduced one centralized entity, which is aware of the complete channelstate information (CSI) in the network. In the first step, this entity plays as abuyer level game for buying power from the source nodes. The sources are non-cooperative among themselves in terms of selling their power to the centralized entity.On the other hand, the centralized entity is willing to maximize its own utility bysettling the optimal amount of power when the prices are announced by the sources.In the second step, on behalf of the relay node, the centralized entity plays as aseller level game for selling/disseminating relay power to the sources. In turn, thesources themselves compete for the relay power given the price set by the centralizedentity. As there is a total power constraint in the system, at the beginning of thegame, the centralized entity applies some intelligent measure in order to determinehow much power is dedicated for source transmission and how much is for relayoperation8. Although there are some works on source power control [101], and on relaypower allocation [102] for a multi-source single-relay network, there is no completesolution for joint sources and relay power allocation for such network in the literature,which we believe to fill up. Moreover, the work in [101] considers that the sourcenodes transmit simultaneously in the same frequency/time domain which results ininterference among them, and not a practical notion of a relayed system. Throughextensive simulation while showing the results from different stand points, we havejustified that the game theoretical solution achieves comparable performance withthe centralized one.The rest of the chapter is organized as follows. System model with its mechanismis briefly summarized in Section 5.2. Game theoretical solution of defined problem8Except the centralized entity, no other nodes need to know the CSI of other nodes. At thebeginning of these games, the centralized entity uses the complete CSI to decide the amount ofpower for the transmit and relay operations in aggregate level. However, two games decide theamount of power for the individual source. In each game, the interaction between the sources andthe centralized entity is completely distributed.81Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)Figure 5.1: System model.is given in Section 5.3. We evaluate the performance of this solution in Sections 5.4and compare the performance with the centralized optimal solution given in Chapter4. Finally, Section 5.5 concludes the chapter.5.2 System Model and Problem FormulationFor the system shown in Figure 5.1, detailed description of the problem is given inChapter 4. Our objective is to solve the following optimization problemmax∑si∈Lslog2(1 +EsiGsi,dσ2+EsiGsi,rEriGr,dσ2 (EsiGsi,r + EriGr,d + σ2))(5.1)where Esi ≤ Emaxs , si∈Ls,∑si∈LsEri ≤ Emaxr ,∑si∈LsEsi +∑si∈LsEri ≤ Emax,{Esi}si∈Ls ≥ 0, {Eri}si∈Ls ≥ 0,82Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)where the channel gain between source si and destination d is Gsi,d; the channel gainbetween source si and relay r is Gsi,r; and the channel gain between relay r anddestination d is Gr,d. Emaxsi is the maximum power constraint of source si and Emaxris that of relay r. For mitigating the interference in the neighboring network, themaximum allowable power Emax is imposed in this network.5.3 Game Theoretical SolutionSince joint sources and their relay power allocation is a non-convex problem, by em-ploying a single cooperative or non-cooperative game, it is not possible to assigntransmit and relay power of a source jointly.9 Hence, we plan to consider sources andtheir relay power allocation as two distinct problems. First, putting some assumptionon the relay power distribution, the sources will decide their optimal power indepen-dently. In the next step, in order to improve the performance of the network further,optimal relay power distribution for the sources is decided. However, in order to con-nect these two problems, we need an entity in the network whom we call "Network".Primarily, Network is aware of the complete CSI of the sources. It is also aware ofthe individual source, relay, and total system power constraints.In the centralized solution of this problem, all nodes in the network work selflesslyto maximize the network capacity. However, in the real world, selfish nodes may nothave a common goal or belong to a common authority. Therefore, a reimbursementmechanism is required such that the sources can earn some benefits while contributingpower towards maximizing the capacity of the network. Since there is a restriction9If we would formulate the problem with only one best-response-strategy-based game, we wouldnot be able to design any cost function which is convex with respect to both transmit and relaypower of each source. However, this is the fundamental requirement of formulating a best-response-strategy-based game: the cost function has to be convex with respect to its variable (transmit power,relay power or price).83Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)on the total power taken from the sources, the authority node "Network" is likelyto choose the most beneficiary sources whose contribution are better compared toothers. Following the characteristics of the sources and Network, a Stackelberg gameis appropriate to model this problem while considering their joint benefits. Networkplays the buyer level game since it aims to achieve the best performance from powergiven by the sources while giving the least possible reimbursement to them. On theother hand, each source plays the seller level game, in which it aims to earn thepayment that not only covers its power cost but also gains as much extra profit aspossible.In order to improve the performance of the network further, Network wants theoptimal distribution of relay power among the sources. However, due to the selfishnature, the sources may want to have as much power as possible to maximize theirown SNR. Furthermore, relay power is limited, if one source takes the whole power,it results in starvation for others. Given the total relay power budget, the objectiveof the sources is non-cooperative. To discourage the sources having as much power asthey want, pricing is an effective mechanism. If price is imposed on the relay power,they will ask for the amount of power which maximizes their individual utility inorder to keep the balance between power and price. In order to model such behaviorsof the sources for their relay power, we have introduced second a Stackelberg game.In this game, Network is the entity that will decide the price of unit relay power.Given the unit power price, the sources demand some power which maximizes theirown utility or benefit.In order to ensure the correct and unique convergence of the first game, Networkneeds to know how much total power is dedicated for the transmit operation of thesources. The rest of the power subtracted from the total network power is for the relay84Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)operation. Following the formula given below, the total relay power of the sourcesis determined. For the first game, if the relay power is not 0, Network assumes thatavailable relay power is subdivided equally among the sources which need the helpof relay.si∈L1s if Gsi,d 0Usi = (pi − ci)Esi . (5.7)The fundamental purpose of above game is to decide the optimal price pi for sourcesi to maximize its profit Usi ; the actual number of sources who will finally be selectedby Network, and the corresponding power consumption Esi , si∈Ls to maximize U sn.The following subsection shows the outcome of the game in detail.Analysis of Source Power Allocation GameWe first examine the proposed game in detail, and obtain the closed form outcome ofthe game. Based on the outcome, we establish that obtained solution is the uniqueequilibrium called the Stackelberg Equilibrium (SE) of the game. Then, from theproperties of the game, in the following subsection, we outline a distributed priceupdate function, and the interaction mechanism of the entities.(i) Network/Buyer Level Analysis: Before taking decision about the amount ofpower it will buy from the sources, it is crucial to know the prices asked by them.Taking the partial derivative of U sn with respect to Esi , from Equation 5.5, we obtain∂U sn∂Esi= a∂R′s,r,d∂Esi− pi, si∈Ls.For U sn being strictly concave with respect to {Esi}si∈Ls , condition ∂Usn∂Esi> 0, si∈Lsshould be satisfied. This means, pi of the source should satisfy pi < a∂R′s,r,d∂Esi.At the beginning, source si has knowledge of its cost ci, which is the bare expense87Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)required for its contribution towards the overall system performance, however is un-aware of the prices of other sources. In order to get its utility Usi non-negative, atthe first iteration, source si sets its price pi = ci. If under this lowest initial price,Network is reluctant to buy power from that source, si will not exist in the gameanymore.Consequently, before initiating the game, Network applies some intelligence in or-der to sort out the sources which it will play the game with. At first, Network tenta-tively set Esi = 0, si∈Ls, if for some source, say si, it holds that ci ≥(a∂R′s,r,d∂Esi)|Esi=0,si will be disregarded by Network.For the remaining sources in set Ls, by the first order optimality condition, thefollowing equation must be satisfied at the optimal point.∂U sn∂Esi= 0, si∈Ls. (5.8)Solving Equation 5.8, we can get its solution {E∗si}si∈Ls shown in Lemma 5.1.Lemma 5.1: The optimal power consumption by source si∈Ls depends on thecontents of the sets L1s and L2s which were determined by Network at the beginningof the game.Case 1: L1s is non-empty, and L2s is empty.E∗si(pi) =0 pi ≥ pubi√aBsiE′riGsi,rGr,dG2si,rσ2(pi−aGsi,dσ2)− BsiGsi,rplbi < pi < pubiEmaxsaGsi,dσ2< pi ≤ plbiUndefined pi ≤ aGsi,dσ2,88Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)where Bsi = E′riGr,d+σ2, plbi =aBsiE′riGsi,rGr,dσ2(Emaxs Gsi,r+Bsi)2+aGsi,dσ2and pubi =aE′riGsi,rGr,dBsiσ2 +aGsi,dσ2.Case 2: L1s is empty, and L2s is non-empty.Optimal power E∗si , si∈L2s of this case is obtained by solving the following opti-mization problem. In order to contribute non-negation utility towards the overallperformance, the price lower and upper bounds of the sources si∈L2s are plbi = 0 andpubi =aGsi,dσ2, respectively.argmax{Esi}si∈L2s∑si∈L2saEsiGsi,dσ2−∑si∈L2spiEsi . (5.9)From the solution of this optimization problem, we observe that full power Emaxs isassigned to the sources following the descending order of the metricaGsi,dσ2− pi, si∈L2suntil the total allowable power E ′s runs out.Case 3: Both L1s and L2s are non-empty.This case is the hybrid scenario of above Case 1 and Case 2. Similar to thesolution method of Case 2, we define metric Asi , si∈L1s⋃L2s for the sources in thiscase.11 The physical meaning of Asi is the profit of source si for the given price pi.Asi =aGsi,d − pi si∈L1saGsi,d +aGsi,rE′riGr,d(Gsi,r+E′riGr,d)− pi si∈L2s. (5.10)We sort Asi , si∈L1s⋃L2s in the descending order. Then, following the order, weassign power among the sources in the following manner until the total allowablepower E ′s runs out.11When the direct link SNR is better than the relayed link one, relay service is not used for thatcase and this makes different types of functions for the profit of different sources.89Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)E∗si(pi) =Emaxs si∈L1smin(Emaxs , Es∗i (pi))si∈L2s. (5.11)The last allocated source may not get the full power following the formula definedabove. It obtains the left over power from E ′s after assigning among the sources whichhave relatively better value for metric Asi .After Network announces optimal power (E∗si)+ to the sources si ∈Ls, they willgradually increase the prices pi, si ∈Ls to get possibly more benefit round by round.This will lead Network to buy decreasing amount of Esi . In order to earn the maximalutility instead of being disregarded by Network, source si also needs to ask properprice.(ii) Source/Seller Level Analysis: Replacing the output from Lemma 5.1 intoEquation 5.7, we havemax{Esi}>0Usi = (pi − ci)E∗si(pi). (5.12)Notice that this game among the sources is non-cooperative, and there exists atradeoff between the price pi and utility Usi of source si. There is an optimal price toset for all sources in order to avoid being disregarded by Network, and maximize itsown utility. The optimal price depends upon the source’s channel condition as wellas its own price. Network only chooses the most beneficiary sources for meeting upits own interest. Following the first order optimality condition, it results in∂Usi∂pi= E∗si(pi) + (pi − ci)∂E∗si(pi)∂pi= 0, si∈Ls. (5.13)Solving Equation 5.13, we obtain the optimal price p∗i = p∗i (Gsi,r, Gr,d, Gsi,d, σ2), ∀si∈Ls.90Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)The solutions in Lemma 5.1 and p∗i are an equilibrium of each round in this game.The properties and convergence procedure of the equilibrium are illustrated in thefollowing subsection.Properties of Source Power Allocation GameIn this subsection, we prove the existence of an SE in this game, and prove theoptimality of the SE by the following properties.Property 5.1: The utility function of Network U sn is concave with respect to{Esi}si∈Ls , where Esi ≥ 0, ∀si∈Ls, when the prices of the source nodes are constant.Proof: Taking the second order derivatives of U sn, we get∂2U sn∂E2si= −2a(E′riGr,d + σ2)E ′riG2si,rGr,d(EsiGsi,r + E′riGr,d + σ2)3, ∀si∈L1s,and∂2U sn∂Esi∂Esj= 0, si, sj∈L1s.From the above 2 equations, it is pretty much straightforward that ∂2Usn∂E2si∂2Usn∂E2sj−( ∂2Usn∂Esi∂Esj)2 > 0, ∀si 6=sj. Furthermore, U sn is continuous with respect to Esi . So,when Esi ≥ 0, U sn is strictly concave in {Esi}si∈L1s and jointly concave as well. ForCase 2, when L1s is empty, Usn is non-differentiable with respect to {Esi}si∈L2s , and thesecond derivative of U sn with respect to any si∈L2s is 0. This concludes the concavityproperty of U sn with respect to {Esi}si∈L2s for Case 2. Case 3 is the hybrid scenario ofboth Cases 1 and 2. Since U sn is concave for both Cases 1 and 2, it is straightforwardto say that U sn is concave with respect to Esi for Case 3.Property 5.2: The optimal power consumption Esi has a decreasing trend withpi when the prices of other sources are some fixed quantity.91Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)Proof: Taking the first order derivative, we have∂E∗si(pi)∂pi= − 12σGsi,r√aBsiE′riGsi,rGr,d(pi − aGsi,dσ2 )3< 0, (5.14)which implies that E∗si is decreasing with pi. For Case 2, if the prices of other sourcesare constant, increment of pi drives Network to buy non-increasing amount of powerfrom source si. In other way, we can say that if one source increases its price whileother sources keep their prices constant, Network will buy less power from that source.Property 5.3: The utility Usi of source si is concave in terms of its price pi itasks for, given that its power consumption is the optimized amount demanded fromNetwork as calculated in Lemma 5.1 and also the prices of other sources are somefixed quantity.Proof: E∗si(pi) is a continuous function of pi. Since Usi is a function of E∗si(pi) andpi, Usi is continuous in pi. Taking the derivatives, we obtain∂Usi∂pi= E∗si(pi) + (pi − ci)∂E∗si(pi)∂pi, (5.15)∂2Usi∂pi= 2∂E∗si(pi)∂pi+ (pi − ci)∂2E∗si(pi)∂pi2, (5.16)where∂2E∗si(pi)∂pi2=3√Bsi4σGsi,r√aE ′riGsi,rGr,d(pi − aGsi,dσ2 )5.We know that pi > ci. Furthermore, we have observed in Case 1 that if pi aGsi,dσ2and the following statement istrue.92Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)√1(pi − aGsi,dσ2 )3>√√√√ 1(pi−aGsi,dσ2)5(pi−ci)2.Because of the above statement and Usi is continuous with respect to pi, fromEquation 5.16, we can conclude that ∂2Usi∂pi< 0, which justifies the concavity propertyof Usi with respect to pi for Case 1. For other cases, it is straightforward to concludethe concavity property of Usi with respect to pi.Remark 5.1: Source Selection procedure by Network described in Section 5.3.1(i)is sufficient.Proof: This is because, any source is rejected by Network at the beginning bythis rule, however mistakenly taken by Network to play the game with, eventuallythat source will be rejected. The proof of this statement is as follows. Suppose thatthe source rejection criterion is applied for some source node si, i.e.,∂Usn∂Esi< 0, whenEsi = 0 and pi = ci. And, Network does not exclude source si and in the followingprice update process, all source nodes gradually increase their prices to get moreutilities. To prove that the new resulting E∗si(ci + δ) < 0, it suffices to prove that∑sj∈Ls∂Esi∂pj≤ 0, i.e., ∂Esi∂pi≤ 0 since we know that ∂Esi∂pj= 0, sj∈ [Ls|si]. Property 5.2already has proved ∂Esi∂pi≤ 0.On the other hand, for Case 1, if any source node si satisfies the source rejectioncriteria at the beginning, si is not rejected by Network in the final outcome of thegame. Since optimal power E∗si(pi) is a function of only source si’s price, it does notget affected if other sources increment their prices. Property 5.3 says that ∂Usi∂pi≥ 0.Assume that p¯i is the price for which source si obtains 0 power. Hence, when sourcesi increments its price from ci to some price, say pnewi , this new price must be lessthan p¯i. This is because, in order to satisfy Property 5.3, it will ask such price whichwill increase its utility instead of obtaining 0 utility (achieved at price p¯i). However,93Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)for Cases 2 and 3, since Network assigns power among the sources in a greedy mannerbased on some metric, there is possibility that some source(s) get(s) rejected in thefinal outcome of the game due to the total power constraint.Theorem 5.1: {E∗si}si∈Ls and {p∗i }si∈Ls are the SE for the source power allocationgame.Proof: Having obtained the prices {p∗i }si∈Ls from the sources, due to Property5.1, U sn({E∗si(p∗i )}si∈Ls) ≥ U sn ({Esi(p∗i )}si∈Ls). That implies, {E∗si(p∗i )}si∈Ls is theoptimal response strategy for Network and the SE of the game. When the optimalresponse is released by Network, source si keeps increasing its price pi until it reachesto p∗i . According to Property 5.3, Usi(p∗i , E∗si(p∗i )) ≥ Usi(pi, E∗si(pi)). Therefore, p∗i isthe optimal response for source si and the SE of the game.Iterative Source Price Update FunctionThe sources increase their utilities by incrementing their prices from acceptable lowerquantity, ci (cost of power for delivering data) towards the optimal ones. The priceupdate function of the sources can be designed as follows. In each iteration of theprice update procedure until the convergence happens, for the sources si∈L1s in Case1, it applies that∂Usi∂pi=∂∂pi[(pi − ci)E∗si(pi)]= E∗si(pi) + (pi − ci)∂E∗si(pi)∂pi≥ 0.By Property 5.2, we know that∂E∗si (pi)∂pi< 0. After re-arranging, the above equationappears topi ≤ ci − E∗si(pi)[∂E∗si(pi)∂pi]−1. (5.17)94Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)Here, it is important to note that the value of∂E∗si (pi)∂piis negative before pi risesto p∗i . For the sake of simplicity, the price update procedure can be represented invector form, p ≤ I(p), where p = {pi}si∈L1s ; I(p) = {Ii(p)}si∈L1s , where Ii(p) is theprice update function for source si. Consequently, each iteration of the price updatealgorithm can be expressed as p(t+ 1) = I(p(t)). I(p) is a standard function, andit has the similar properties as a standard function has. Because of these properties,the authors in [104] have proved that starting from some initial power vector p,after n iterations, In(p) produces unique fixed prices. The properties of the standardfunction I(p) have been proved in Appendix A. For Case 2, E∗si(pi), ∀si∈L2s is non-differentiable with respect to pi. Therefore, the price update function for this case isp(t+1) = p(t) + δ. Whereas, for Case 3, the sources ∀si∈L1s follow the similar priceupdate procedure as Case 1, and the sources ∀si∈L2s follow the procedure in Case 2.5.3.2 Game Theoretical Relay Power AllocationIn order to enhance the performance of the network further, we present the formu-lation of another Stackelberg game in order to distribute relay power E ′r among thesources in set L1s below.1. Sources/Buyers: We first model the sources as followers who aim to get mostbenefits at the least possible payment. The utility function of source si, si∈L1scan be defined byUri = η(E∗siGsi,dσ2+E∗siGsi,rEriGr,dσ2(E∗siGsi,r + EriGr,d + σ2))− λEri . (5.18)η is the gain per unit of SNR, and λ denotes the price per unit of power sold bythe centralized node "Network". Eri can be explained as the amount of relay95Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)power source si would like to buy from Network when the price λ is announced.2. Network/Seller: Network is modeled as a leader who aims to maximize itsrevenue by setting a proper price. Constant c is introduced to denote the costper unit of power. The utility function of Network is defined asU rn = (λ− c)∑si∈L1sE∗ri(λ). (5.19)λ has the same meaning as in Equation 5.18. In order to earn profit, the pricemust be higher than the cost, which means λ > c. E∗ri(λ), si∈L1s depends notonly on source si’s channel condition, but also depends on the global price. IfNetwork asks a larger price than what the source expects, the source will buyless power. On the other hand, if the price is too low, the profit obtained byEquation 5.19 will be unnecessarily small. So, there is a tradeoff for setting theprice. A proper price can distribute the total allowable relay power among thesources optimally.Analysis of Relay Power Allocation GameIn this section, we first show that given a price λ, there exists an unique SE of eachsource game. Then based on this, we prove, there is a unique optimal equilibrium forthe whole Stackelberg game. Moreover, we design a price update function for Networkand prove its convergence to the unique equilibrium in the following subsection.(i) Source Level Analysis: Each source node (si∈L1s) determines how much powerit should buy to maximize its utility. According to Equation 5.18, the power sourcesi will buy under the price λ can be determined by solving the equation∂Uri∂Eri= 0.96Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)E∗ri(λ) =0 if λ ≥ λubri1Gr,d[√ηBriE∗siGsi,rGr,dλσ2− Bri]if λubri < λ < λlbriE ′r if λ ≤ λlbri, (5.20)where Bri = E∗siGsi,r + σ2, λlbri =ηBriE∗siGsi,rGr,dσ2(E′rGr,d+Bri )2 and λubri =ηE∗siGsi,rGr,dBriσ2 .(ii) Network Level Analysis: Network needs to find a global optimal price so as tomaximize its revenue. Given E∗ri(λ), si∈L1s, the best price can be obtained by solvingthe following equation∂U rn∂λ=∑si∈L1sE∗ri(λ) + (λ− c)∑si∈L1s∂E∗ri(λ)∂λ. (5.21)Hence, the best price is given byλ∗ = f({Gsi,r}si∈L1s , Gr,d, c, η, σ2) . (5.22)Lemma 5.2: The optimal price is inside the interval [λlb, λub), where λlb =maxsi∈L1sλlbri and λub = maxsi∈L1sλubri .Proof: We prove the lower bound by contradiction. If λ < maxsi∈L1s λlbri, one sourcewill definitely obtain E ′r relay power and at most one source will obtain some relaypower which results in the amount of allocated relay power is more than the allowablepower E ′r. This is not a feasible solution. On the other hand, if λ = maxsi∈L1s λlbri,one source will obtain E ′r relay power and the rest others may obtain 0 relay power,which is considered as a feasible solution. Considering the feasibility of the allocatedrelay power among all sources, λ should be ≥ maxsi∈L1s λlbri .For the upper bound, if λ ≥ maxsi∈L1s λubri , all sources obtain 0 relay power whichis also not an expected solution. Therefore, λ must be < maxsi∈L1s λubriin order to97Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)assign some relay power among the sources.Properties of Relay Power Allocation GameIn this subsection, we elaborate the properties of the relay power allocation game andprove that the solutions derived in Equations 5.20 and 5.22 are the unique optimalequilibrium for each round of this game.Property 5.4: Given price λ, Uri is concave with respect to Eri , when Eri > 0and Erj , ∀sj∈ [L1s|si] are fixed quantity.Proof: Taking the second order derivative of Uri in Equation 5.18, we get∂2Uri∂E2ri=−2ηBriE∗siGsi,rGr,dσ2(Bri + EriGr,d)3< 0. (5.23)Moreover, Uri is continuous in Eri . So, when Eri > 0, Uri is concave with respectto Eri .Property 5.5: The best amount of power bought by each source decreases asthe price increases.Proof: Taking the derivative of E∗ri(λ) with respect to λ, we obtain∂E∗ri(λ)∂λ=−12Gr,d√ηBriE∗siGsi,rGr,dσ2λ3< 0. (5.24)This justifies the decrementing trend of the optimal relay power for sources si∈L1swith the incrementing λ.Property 5.6: If λ > c, U rn is concave with respect to price λ and the powerconsumption is the optimized purchase amount.98Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)Proof: From Equations 5.21 and 5.24, we obtain∂2U rn∂λ2= 2∑si∈L1s∂E∗ri(λ)∂λ+ (λ− c)∑si∈L1s∂2E∗ri(λ)∂λ2, (5.25)∂2E∗ri(λ)∂λ2=34Gr,d√ηBriE∗siGsi,rGr,dσ2λ5. (5.26)Since√1λ3>√1λ5(λ−c)2, ∂2Urn∂λ2< 0, which justifies the concavity property of U rn withrespect to λ.Property 5.7: Given the relay power price λ, E∗ri(λ) is a non-decreasing functionof E∗si and Gsi,r.Proof: See Lemma 5.2 of [102].Theorem 5.2: {{E∗ri}si∈L1s , λ∗} solved in above discussions are the SE for theproposed game.Proof: According to Property 5.4, given λ and the power of other sources {E∗rj}sj∈[L1s|si]is constant, the best response of source si is E∗ri(λ). And, according to Property 5.6,incrementing λ gradually increases the value of U rn until it reaches λ∗. It implies thatUri(E∗ri(λ∗)) ≥ Uri(Eri(λ∗)),U rn({E∗ri(λ∗)}si∈L1s) ≥ U rn({E∗ri(λ)}si∈L1s).So, {{E∗ri}si∈L1s , λ∗} are the SE of the relay power allocation Stackelberg game.99Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)Iterative Relay Power Price Update FunctionIn order to achieve appropriate convergence of this game, Network needs to updateits price correctly in each round. According to Property 5.6, U rn is a concave functionwith respect to λ. Therefore, Network increases the price λ from its initial price untilthe convergence happens. For the sake of obtaining non-negative utility, Networksets the initial price c. According to Equation 5.21 and Property 5.5, if ∂∂λU rn > 0, wehaveλ < c−∑si∈L1sE∗ri(λ)∑si∈L1s∂E∗ri(λ)∂λ−1.We denote I(λ) asI(λ) = c−∑si∈L1sE∗ri(λ)∑si∈L1s∂E∗ri(λ)∂λ−1. (5.27)Hence, the price update method is λ(t+1) = I(λ(t)). I(λ) fulfills the properties of astandard function which has been proved in Appendix B. Setting the initial price asc (i.e.,λlb), λ will converge to a unique equilibrium after sufficient iterations.5.3.3 Further DiscussionNext, we will briefly discuss the possible implementation of the proposed game the-oretical solution for this power allocation problem. As noted before, there is a cen-tralized entity called "Network" in the network. Network is responsible to lead twogames in order to obtain the transmit and relay power allocation of the sources.There is a total power constraint in the network which is the sum of required powerfor both transmit and relay operations of the sources. In order to decide appropri-100Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)ate convergence of two games separately, Network needs to know how much poweris separately allocated for both games. As discussed before, in order to decide theamount power for both games, Network should be aware of the complete CSI of thenetwork. On the assumption of using block fading channel model, at the beginningof the first time slot (the entire transmit operation requires two phases or time slots),a training process is conducted for Network to obtain global CSI. Research on theefficient channel training and estimation can be found in [105, 106]. The trainingand estimation is performed at the relay and the destination in order to obtain thechannel gains from the sources to themselves. For collecting the channel gain fromthe relay to the destination, another round of training and estimation is performedat the relay. Finally, all these acquired channel gains are notified to Network by thefeedback method. Network can be a separate computationally powerful entity in thenetwork or; any of the sources or the relay can play this role depending on theircomputational capability.Once Network knows the allowable power for two games, first it starts the gamewith the sources for their transmit power. When the convergence is achieved for thisgame and set L1s is not empty, Network initiates the second game, and continuesuntil the convergence happens. In order to improve the performance of the networkfurther, Network can re-distribute the power especially for the case when both setsL1s and L2s are non-empty. The way how Network does this is described as follows.1. Sort the list L2s in the descending order of Gsi,d, si∈L2s, and denote the sortedlist as OL2s.2. Sort the list L1s in the ascending order ot Gsi,d, si∈L1S, and denote the sortedlist as OL1s.3. Take source si from OL2s which is not assigned with full power Emaxs .101Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)4. Take source sj from OL1s.5. Compute x = min(E∗sj , E∗rj)and y = min(2x,E∗si). Add y to E∗si , and subtracty/2 from E∗sj and E∗rj.6. If E∗si = Emaxs , move si to the next source of list OL2s.7. If E∗sj = 0 and E∗rj> 0, add E∗rj to E∗sj.8. If E∗sj = 0, move sj to the next source of list OL1s.9. If si or sj does not point to a valid source, terminate this process, otherwiserepeat the steps from 5.With this implementation, we actually assume that Network is trustworthy. Allsources believe that Network will not change the parameter values (e.g., CSI), howeverconducts all these operations in the systematic manner.5.4 Simulation ResultsIn order to evaluate the game theoretical solution, we undertake the similar net-work setup, channel model and the parameters as given in Section 3.3.4 of Chapter3. Similar simulation scenario is undertaken as was taken for evaluating the perfor-mance of the centralized approach. For the game theoretical solution, there are someparameters, which we set as a = 100, η = 10012.Within a certain price range, the utility of each source is concave. Ideally, conver-gence of the source power allocation game should be decided by the individual source12Setting a and η as arbitrarily random values, only the resultant converged prices {pi}si∈Ls andλ are affected. However, main outcome of the game {Esi}si∈Ls and {Eri}si∈L1s are unique regardlessof the values of a and η.102Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)1 2 3 4 5 651015202530Scenario NumberUnit Source Power Price Source s1Source s2Source s3Source s4Source s51 2 300.51Scenario NumberUnit Source Power Price(a) Converged price comparison among all sources.1 2 3 4 5 61002003004005006007008009001000Scenario NumberIndividual Source Utility Source s1Source s2Source s3Source s41 2 30102030Scenario NumberIndividual Source Utility(b) Individual converged utility comparison amongall sources.1 2 3 4 5 6200Network Utility (Uns)1000Sum Source Utility (M)Scenario NumberMUns(c) Converged Network utility and sum source util-ity comparison.1 2 3 4 5 6 7 8 9 100.180.190.20.210.22IterationsUnit Source Power Price Source s1Source s21 2 3 4 5 6 7 8 9 1011.522.5IterationsUnit Source Power Price Source s1Source s2(d) Convergence for scenario 1 (up) and scenario 4(down).Figure 5.2: Source power allocation game.103Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)nodes. However, to make the game theoretical solution comparable with the central-ized one, Network should be aware of total power constraint, i.e., the sum power soldby the sources should be equal to the total allowable source power. Therefore, if thesum of converged power is less than the total source power budget, the remainingpower is distributed among the sources based on their contribution towards the util-ity of Network node. On the other hand, if the sum of the converged power is lessthan the total power budget, overflown power is subtracted from the sources basedon their inverse utility contribution.Figures 5.2(a), 5.2(b) and 5.2(c) compare individual converged source power pricepi, utility Usi , sum source utility M , and Network node’s utility Usn for different sce-narios explained previously. As the sources move towards the relay or the destination,prices asked by them are increased. Since their channel condition gradually improveswith the increasing scenario number, they demand high price for unit source power.For scenario number 1, 2 and 3, the price of the sources is the sum of relayed anddirect link contribution towards maximizing Network’s utility. Whereas for other sce-narios, the price is only for the direct link contribution. Since the absolute channelcondition of scenarios 5 and 6 is almost same, the prices of the sources are almostequivalent for these two scenarios. In each scenario, the sources with better channelcondition contribute more towards maximizing Networks’s utility, and hence they de-mand higher price compared to others. Furthermore, the utility of individual sourcefollows the same trend as its price since the utility is the product of its price andsold power. At the convergence point, all scenarios satisfy the same power constraint,and hence the utility of individual source is increased with the increasing price. Con-sequently, the sum utility of all sources M is increased with the increasing scenarionumber. In Figure 5.2(b), we have skipped the utility of source s5 because of its104Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)achieved 0 utility resulting from nearly 0 sold power. Since the channel conditionof the sources is getting better with the increasing scenario number, even though Mis subtracted form the first factor of Network’s utility, because of using moderatelylarger value of a, the utility of Network is increased as well. There is a discrepancybetween scenario 3 and scenario 4 in terms of the utility of Network node, this isbecause former one uses the relay for transmission, whereas the latter one does not.Moreover, the converged price of each source for scenario 4 is close to the upperbound of its price, and hence the value of M does not deviate much from the firstfactor of U sn. However, the scenarios without relay power follow the same increasingtrend with the better channel quality condition because of the increasing first factorof U sn compared to its M . Table 5.1 shows the final outcome of the game, a detailedbreakdown of the source power. In order to have comparison, the table also showsthe power obtained from the centralized optimal solution.At the beginning, when the game is started, Network selects the set Ls of ben-eficiary sources following the procedure in Remark 5.1. Taking the consideration oftheir own cost, the sources announce their prices. Consequently, Network calculatesthe amount of power it wants to buy from the sources for maximizing its own utility.Considering this interaction as one iteration, Figure 5.2(d) shows the convergenceprocess for scenarios 1 and 4. For scenarios 4, 5 and 6, convergence speed dependson the step size δi, si∈Ls. The larger the step size, the speedier the convergence.Similar to the source power allocation game, for the relay power allocation game,the convergence point should be decided by the seller of the game, i.e., Network. Inorder to have valid comparison with the centralized solution, the sum relay powershould meet some power constraint. At the convergence point of Network node,the power constraint should be satisfied. If the constraint is not satisfied at the105Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)Table 5.1: Source transmit power comparison between optimal and game theoreticalsolutions.Scenario s1 s2 s3 s4 s5Number Opt Game Opt Game Opt Game Opt Game Opt Game1 28.29 24.32 26.46 19 15.24 16 0 10.68 0 51e-32 29.12 25.1 28.21 21.0 12.66 12.13 0 7.1 0 4e-33 30.0 27.23 30 24.4 10 11.55 0 6.80 0 71e-44 30.0 30.0 30.0 30.0 30.0 30.0 30.0 30.0 0 05 30.0 30.0 30.0 30.0 30.0 30.0 30.0 30.0 0 01 2 30.120.130.140.150.160.170.180.190.20.21Scenario NumberUnit Relay Power Price (λ)1 2 366.577.588.599.51010.5Scenario NumberNetwork Utility (Unr)(a) Relay power price (left) and converged Networkutility (right) comparison.1 2 3 4 5 6 7 8 9 100.1520.1540.1560.1580.160.1620.1640.1660.1680.17IterationsUnit Relay Power Price (λ)(b) Convergence for scenario 2.Figure 5.3: Relay power allocation game.convergence point, relay power of each source is adjusted based on its contributiontowards the utility of Network node.Figure 5.3(a) shows the increasing price and utility of Network node for the relaypower allocation game with respect to different scenarios. Similar to the source powerallocation game, the increasing scenario number implies better channel quality con-dition. It means, unit relay power results in more contribution towards maximizingthe utility of individual source. Hence, Network demands larger relay power pricewhile selling its power to the sources. Since the power budget is same for all sce-narios, with the increasing price, the utility of Network node has increasing trend as106Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)well. Table 5.2 shows the final outcome of the game. It compares the power obtainedby the relay power allocation game with the centralized optimal solution. It seems,individual source who has better channel condition buys more power compared toothers. This is because, given the unit price, the source with better channel condi-tion incurs larger utility compared to those with worse ones. Moreover, the utility ofindividual source is the increasing function of its transmit power. Since the sourcewith better channel condition is assigned larger transmit power from the previousgame, this source is likely to be assigned with more relay power compared to others.Therefore, the larger demanded power is well adjusted balance between their utilityand price.After carefully considering the initial price, when Network announces it, thesources demand power which is the balance between their individual utility andprice. Considering this interaction between the sources and Network as a single step,Figure 5.3(b) shows the convergence behavior of the relay power allocation game atscenario 2. The figure shows the increasing price of Network node with the increasingiteration until the convergence happens.Table 5.2: Source relay power comparison between optimal and game theoreticalsolutions.Scenario s1 s2 s3 s4 s5Number Opt Game Opt Game Opt Game Opt Game Opt Game1 36.19 46 13.78 4.0 0 0 0 0 0 02 36.96 46.3 13.031 3.7 0 0 0 0 0 03 32.24 43.5 17.75 6.5 0 0 0 0 0 0Taking the power presented in Table 5.1 and Table 5.2, Figure 5.4 compares thethroughput obtained from the game theoretical solution with the centralized optimalsolution.107Chapter 5. Joint Source and Relay Power Allocation for AF Relayed Network (Game Theoretical Solution)1 2 3 4 5 61234567Scenario NumberSystem Throughput OptGameFigure 5.4: System throughput comparison between optimal and game theoreticalsolutions.5.5 Summary of the ChapterIn this chapter, we have proposed a game theoretical solution of the problem describedin Chapter 3. In the centralized solution, all nodes work selflessly towards maximizingthe network capacity. The game theoretical solution proposed in this chapter canmodel the selfish behavior of the nodes in the network. Since joint single-source andsingle-relay power allocation is even a non-convex problem, two Stackelberg games areappropriate to determine the transmit and relay power of the sources. A centralizedentity namely Network is required to make a bridge between these two games, andit is the leader of both games. For disseminating transmit power among the sources,Network plays the buyer level game and the sources are power sellers. Their roles areinterchanged for disseminating relay power among the sources. Extensive numericalresults have been provided in order to show different properties, convergence conditionof the solution. Finally, we have shown that the game theoretical solution achievescomparable performance with the centralized optimal solution.108Chapter 6Uplink Scheduling and ResourceAllocation for Heterogeneous TrafficNetworks6.1 IntroductionBased on OFDM and OFDMA principals, LTE and LTE-Advanced permit granu-lar subcarrier division among the diverse users into time-frequency-based resourceunits called RBs. Despite numerous advantages of OFDM and OFDMA, their ma-jor disadvantage is, their waveforms have high PAPR. To reduce PAPR, LTE andLTE-Advanced agree on using SC-FDMA for the uplink transmission which imposescontiguous RB allocation to a user. Typical scheduling of such systems involves thedetermination of the set of users, assignment of RBs to these users and setting oftransmit power for each RB. Uplink scheduling even for the conventional LTE sys-tems with best effort traffic is considered challenging because of individual users’power constraints, the discrete nature of RB assignment while maintaining contigu-ity pattern. With the invention of numerous applications with distinct fascinatingfeatures, now a days, LTE systems are more likely to carry heterogeneous traffic withdifferent QoS demands. Scheduling RBs while satisfying diverse QoS of different new109Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksapplications brings more challenges to the uplink scheduling problem on the top ofits own inherent difficulties. Besides all these system and traffic specific issues, theservice providers may want to have domination on the RB allocation determined bytheir policy. This introduces further challenges to the uplink scheduling problem inLTE systems conveying heterogeneous traffic.Resource allocation problems for OFDM-based networks especially downlink LTEsystems have appeared in some survey papers recently [51], [52]. In homogeneous traf-fic networks, for two types of traffic, e.g., elastic traffic, traffic with QoS requirements,scheduling problems have extensively been studied. For the elastic traffic, in order toperform the scheduling decision, the utility of the users is represented by a concavefunction [107]. Subject to the objective of maximizing the sum of general concaveutility functions, one recent work [108] has proposed some computationally efficientalgorithms. Channel-aware throughput maximization technique for such systems isknown as maximum throughput (MT). For fair resource allocation, typical propor-tional fair (PF) metric [109], [110], [111] is the ratio of the instantaneous data rateon a RB and the past average throughput. In [112], [113], PF scheme is formulatedas an optimization problem with the objective of maximizing achieved throughputunder the typical constraints of LTE systems.Among QoS-aware schedulers in homogeneous traffic networks, [55] ensures guar-anteed throughput by separating jobs in the time and frequency domains. In thetime domain, they first separate traffic based on their current and pre-specified set-tled throughput. Then, they apply some PF scheme on the same priority users inorder to obtain final RB assignment. More works on providing throughput guar-antee for real time flows include [114], [115]. [116] calculates the priority indicatorusing head of line (HOL) packet delay, and ensures target delay bound for the de-110Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networkslay sensitive traffic. Modified largest weighted delay first (M-LWDF)[117] has beenintroduced for OFDMA-based networks in [53] by putting past throughput in thedenominator of the original metric. Two promising strategies, i.e., LOG and EXPrules have been explained in [54]. Their RB selection metrics are based on the log-arithmic and exponential functions of the packet HOL delay, respectively. UnlikeLOG, EXP scheduler takes the overall network status into account. Similar to these,there is another scheduling rule, i.e., maxweight (MW) [118] for delay sensitive traf-fic. Analytical results in terms of queue distribution for the schedulers with theserules are given in [119], [120], [121]. In [122], the authors adapt EXP rule by takingthe characteristics of PF and exponential function of the packet HOL delay into ac-count. A two level packet scheduler working in the larger LTE frame, and then in thegranular frame level for real time traffic has been given in [123]. A similar approach,however working in 3 discrete levels has been presented in [124]. The third level ofthis scheduler is called cut-in process which discards packets whose delay deadlinehas been expired. A recent work [125] combines EXP rule, cooperative game andvirtual token mechanism in order to ensure bounded delay and guaranteed bit ratefor users.Scheduling problem in heterogeneous traffic networks is considered more chal-lenging compared to the homogeneous one because of the conflicting requirementsof different traffic. There are three design issues that need to be considered whileformulating the scheduling problem of an ideal scheduler for heterogeneous trafficnetworks. Wireless users experience varying channel quality condition time to timedue to the stochastic fading effects, and hence their achievable data rates are affected.The scheduler should choose the user with good channel quality condition in order tomaximize the system throughput. However, if the user with better channel quality111Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networkscondition is always selected, the users with worse channel condition may starve. Thisissue is known as fairness, and another very important factor to keep into consider-ation. Third, different applications have different QoS requirements and the utilityfunction of the scheduler should be defined in such a way that it has the ability tocapture those metrics simultaneously and effectively.Similar to homogeneous traffic networks, the downlink scheduling has extensivelybeen studied for OFDM-based networks carrying heterogeneous traffic. These worksmainly adopted three categories of designs. First, some works gave strict priorityto the high priority traffic compared to the low priority ones, such as [57, 58]. [57]has proposed a solution for VoIP and data traffic while giving strict priority to VoIPusers. A scheduling policy with strict priority across the classes is also studied in [58].Within a class, the proposed scheduler does chunk by chunk resource allocation. Thework in [126] has given strict priority to SIP traffic over other data traffic. Second, theauthors in [59] have addressed mixed traffic (delay sensitive, guaranteed throughput,best effort) by designing the scheduler on the time and frequency domains. Thepriority sets are populated based on the QCI of each data flow, and classified asGBR and non-GBR. Third, the scheduler is designed by representing the satisfactionof users by the utility function. In [60, 61], different utility functions are used torepresent different types of traffic (traffic with data rate requirement, traffic withdelay constraint). Although [60] did not consider the channel condition of users inthe scheduling decision, [61] took all required issues into account. Besides these, thereare some general mechanisms for handling mixed traffic. For example, the authorsin [54] have proposed a low complexity RB allocation algorithm using LOG/EXP,EDF rules, and tested their scheme with mixed streaming and live video traffic. Thework in [127] studied a scheduling policy that gives equal priority to all packets with112Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksdifferent QoS unless their delay reaches close to their deadline.Unlike downlink operation, not much works have been conducted for the uplinkLTE systems. Most works focused on throughput maximization objective. For ex-ample, [10, 128, 129, 11] have given different heuristics based on different principlesupon stating that the problem is NP-hard. Although these works take RB contigu-ity constraint into account, skip individual users’ power constraint. However, thisconstraint is an important factor in scheduling decision, and limits the overall sys-tem performance. On the other hand, there are few works for the uplink schedulingwith QoS assurance. These works are mainly for homogeneous delay sensitive traf-fic [62, 63]. One recent work on energy efficient QoS assured scheduler is [64], whereQoS is considered user’s instantaneous rate. For heterogeneous traffic environments,recently, [65] has proposed a scheduler which is based on the time and frequencydomain scheduler [59]. One drawback of this work is, they did not consider the trafficclass in their design. Moreover, they evaluated the performance of this scheduler intheir customized simulation scenario, which is not practical.Having noticed the drawback of [65], and in order to design a utility based sched-uler for the heterogeneous traffic environment, in this chapter, we have proposed anuplink scheduling scheme for a LTE system carrying heterogeneous traffic. This workis based on the utility function [130] has used. The difference is, their solution issuitable for the downlink scheduling, and designed for CDMA-based systems. Theutility function of [130] is general, one single function can handle diverse types oftraffic, instantaneous channel condition and so forth. Typically, this utility functionis used in economics in order to maintain social welfare (another name of fairness) ofthe society, however rarely applied in communications. Moreover, this utility functioncan distinguish inter or intra class based traffic prioritization. Besides capturing three113Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networkskey design issues of the heterogeneous traffic environment by this utility function, inorder to assist the service providers, the proposed uplink scheduling problem consistsof a constraint which imposes some control on RB allocation. The distinctive noveltyand contributions of this chapter are briefly summarized as follows.1. For representing the satisfaction of a user, we have adopted the utility func-tion already used for the downlink scheduling operation of a CDMA-based sys-tem [130]. Although we have adopted their utility function and same definitionof QoS measures for different traffic, we have solved a distinct problem for adifferent system, i.e., uplink scheduling of LTE systems. Furthermore, the waythey have solved the downlink scheduling problem is different compared to us.Given pre-defined physical layer data rate of users and given certain systemcapacity, their work schedules a set of users instead of CDMA tones. Whereas,our scheduling scheme determines every single RB-user mapping, their assignedpower which is the true notion of an ideal scheduler given the incoming packetsin each scheduling epoch.2. For obeying every detailed specifications of the LTE standard, our formulatedproblem takes individual user’s power and RB contiguity constraints into ac-count. Individual user’s power constraint is required in order to correctly mea-sure the overall system performance. On the other hand, in order to avoid highPAPR of the generated waveform, we assign contiguous RBs to each user.3. Besides the standard specific constraints, our formulation consists of anotherfactor, opportunity cost function. Physical meaning of this function is howmuch utilization of resource the service provider can sacrifice in order to achieveother system or user specific benefits. The cost function can work in bothgranular and aggregate resource utilization levels. For this work, we assume it114Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksto be dependent on RB utilization as the latter one can be achieved throughthe former one, however not vice versa. Furthermore, service providers mayrelate opportunity cost function to revenue as desired.4. By setting certain parameter for the opportunity cost function, our schedulingscheme can be transformed to two extreme ends of scheduling mechanisms, i.e.,MT and PF schedulers. By providing enough evidence, we have proved thisstatement analytically.5. Dual decomposition method has been used in order to show the optimal solutionstructure of our formulated problem. Finally, from the guiding principles of theoptimal solution, we have given a low complexity scheduling algorithm.6. Extensive simulation has been conducted assuming the network has best efforttraffic, traffic with throughput requirement and traffic with delay bound. Whilecomparing with other scheduling solutions of LTE systems, we have proved theeffectiveness and efficacy of our scheme.The rest of the chapter is organized as follows, Section 6.2 gives the overviewand components of the system while elaborating detailed formulation of the problem.Solution approach and the resultant algorithm are presented in Section 6.3. Weinvestigate some interesting characteristics of our scheduling scheme in Section 6.4.In order to show the effectiveness of the proposed scheme, we provide simulationresults followed by the simulation methodology in Section 6.5. Finally, Section 6.6concludes the chapter.115Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks6.2 System Model and Problem FormulationWe consider an uplink scheduling problem of a typical LTE cellular network. Wedenote the set which contains available RBs at each scheduling epoch by N. Thenumber of users in the system is M . The users are again categorized into C classes,where class c has higher priority than class c+1. Let Mc denote the number of classc users; M =C∑cMc and the set holding all users is M. Each class is accompaniedwith diverse kinds of QoS criteria. At each scheduling instant, all users transmittheir CSI to the base station. In the channel coherent time, based on the traffic type,channel state and their QoS requirements, the base station assigns appropriate RBsto the corresponding users as well as determines power of each RB. The purpose of thescheduler equipped in the centralized controller is to maximize the sum satisfactionof all users.6.2.1 Problem FormulationSince SC-FDMA-based resource allocation allows service providers to allocate re-source in granular RB level, for a particular user i of a certain class c, we define its util-ity function for each and every RB j, ∀j∈N. At scheduling time instant t, the satisfac-tion of user i of class c on RB j is perceived by the utility function Ucij({Xzcij(t)}mciz=1),where {Xzcij(t)}mciz=1 = {X1cij(t), X2cij(t), · · · Xmcicij (t)}. {X1cij(t), · · · Xmcicij (t)} arecomputed quantitative QoS measures in terms of the (c, i)th user’s satisfactions inLTE uplink systems during the scheduling decision of RB j at time instant t. Typ-ically, QoS measures are the average throughput, current data rate, average delay,etc. mci represents the maximum number of QoS measures for user (c, i). Therefore,we can write the objective function as116Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksmaxC∑cMc∑iN∑jUcij({Xzcij}mciz=1(t)). (6.1)If xcij denotes the fraction of RB j allocated to user (c, i), the total allocationacross all users should be no larger than 1, i.e.,∑(c,i)∈Mxcij(t) ≤ 1, ∀j∈N. (6.2)According to the LTE standard, there is a constraint on xcij to be an integer {0, 1}.We will see later, how we have handled this constraint while solving this problem.Besides this, due to the contiguity constraint of SC-FDMA, RBs are allocated to user(c, i) in a contiguous manner. It impliesif xcin(t) = 1 && xci(n+1)(t) = 0, xcij(t) = 0, n+ 2≤j≤N, (6.3)if xcin(t) = 1 && xci(n−1)(t) = 0, xcij(t) = 0, 1≤j≤n− 2.Each user (c, i) has power limitation during a scheduling epoch, and its maximumpower is denoted by Pci. For transmitting on RB j, we denote the (c, i)th user’stransmission power is pcij and total power used on all allocated RBs cannot exceedthe maximum power Pci.13∑j∈Npcij(t) ≤ Pci, ∀(c, i)∈M. (6.4)Moreover, there are upper and lower bounds of each QoS measure, and these arepre-defined values set by the users. For example, the zth QoS measure of user (c, i)13According to Figure 3 of [3], different levels of power for the allocated RBs of a user is allowed.117Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networkshas an upper bound νz,maxci and a lower bound νz,minci (e.g., maximum and minimumaverage throughput).νz,minci ≤ Xzcij(t) ≤ νz,maxci , ∀(c, i) ∈M, ∀z, 1 ≤ z ≤ mci. (6.5)The constraints presented in Equations 6.2, 6.3, 6.4 and 6.5 are either enforced bythe LTE standard or set by the users. Another constraint we would like to introduceis for the sake of service providers, i.e., opportunity cost. The concept of opportunitycost can be used to manage the tradeoff between fairness and resource utilization. Inorder to ensure fairness across the network, the scheduler may be forced to serve lowrate generating users resulting in rate loss. To limit this rate loss, we have proposedthe cost function called opportunity cost. Similar to other metrics, the opportunitycost is also defined in granular user and RB level. At scheduling instant t, whileallocating RB j, we define the opportunity cost for user (c, i) as OCcij(t). OCcij(t)is a function of the rate for user (c, i) on RB j, Rcij(t). Rcij(t) is given byRcij(t) = xcij(t)log(1 +pcij(t)ecij(t)xcij(t)), (6.6)where ecij is the normalized received SNR per unit of transmit power of user (c, i) onRB j from the base station. At the beginning of scheduling instant t, the schedulergathers complete information of this metric for all users and all RBs. The maximumrate that the scheduler can earn out of RB j at time t is given byRmaxj (t) = max(c,i)∈MRcij(t), ∀j ∈ N. (6.7)Using these metrics, OCcij(t) is defined as follows.118Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksOCcij(t) = Rmaxj (t)−Rcij(t). (6.8)In other way, the opportunity cost is a measure of how much rate the network oper-ator would forgo if user (c, i) is selected for the transmission on RB j at schedulinginstant t, while there is some other user (c, i)∗ that generates the highest rate on thisRB. Taking the interest of network operators into account, the objective function inEquation 6.1 can further be constrained by the opportunity cost functionOCcij(t) ≤ H, ∀(c, i)∈M, ∀j∈N. (6.9)The network operator can determine the required level of fairness and resourceutilization by choosing the appropriate value of H. If H = Rmaxj , the rate loss isno more than % of the maximum achievable rate Rmaxj on RB j. Moreover, H = 0implies that the network operator cannot tolerate any rate loss, therefore it alwayspicks the highest rate generating user while allocating any RB. In order to ignore theopportunity cost, the network operator can set H = Rmaxj . In this case, all users aretreated equally by the scheduler.6.2.2 The Utility FunctionIn this section, we introduce a utility function which is able to meet all require-ments of an ideal utility function. In order to satisfy all requirements of the problemdescribed in the previous subsection, the feasible utility function should have the con-cavity property. The more the allocated resource, the more satisfied the user is, i.e.,the utility function should be non-decreasing with Xzcij, ∀j∈N, ∀z∈ [1,mci]. Whileallocating a RB at time instant t, if the values of all QoS measures for a user (c, i)119Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks−0.8 −0.7 −0.6 −0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2−120−100−80−60−40−200XcijUtility ac=2ac=4ac=6(a) Utility comparison for different ac and Xcij .−0.8 −0.7 −0.6 −0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.220406080100120XcijMarginal Utility ac=2ac=4ac=6(b) Marginal utility comparison for different ac andXcij .Figure 6.1: Characteristics of the utility function.120Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksare minimum, the utility value for that user attains its unique minimum value Uminci ,whereas when the values reach to their maximum, the utility appears to its uniquemaximum value Umaxci . In the rest of other cases, the utility value remains in betweenthese two quantities, or in other way, Uminci ≤Ucij({Xcij(t)}mciz=1)≤Umaxci . Furthermore,once the utility value for a user reaches to its maximum value, additional allocatedresource cannot deviate it from its maximum quantity Umaxci .In addition of having above fundamental properties, the utility function shouldsupport inter-class prioritization. We denote a parameter ac, ∀c, 1≤c≤C to distin-guish inter-class prioritization. The larger the value of ac, the higher the priority ofclass c. The proposed utility function is already used for the scheduling purpose inCDMA-based networks. As our problem is different, we interpret this function in adifferent way. The utility function for user (c, i) while allocating RB j at time instantt is given byUcij({Xzcij}mciz=1(t)) = 1 − e−acmci∑z=1Xzcij(t). (6.10)We plot the utility function with respect to arbitrary QoS measure Xcij for 3 userswith different ac in Figure 6.1(a). We observe, the utility function has the diminishingproperty. When the quantitative value of Xcij is low, the rate of change of the utility(slope) is larger. It implies, if the scheduler gives priority to the user with low QoSmeasure, the contribution of this user towards the maximization of overall utility ishigher compared to others. Hence, the scheduler needs to take this into account whilemaking the scheduling decision of RB j. In order to show the decreasing trend of theslope with the increasing value of Xcij, we plot Figure 6.1(b). We define the slope ofthe utility function as marginal utility. Moreover, larger value of ac makes the utility121Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksfunction steeper with respect to QoS measures. In other way, the slope of the utilityfunction is steeper with larger ac at low value of Xcij. Therefore, for this particularutility function, the slope of a user’s utility plays an important role in the schedulingdecision of RBs. From the perspective of economics, this type of utility function hasanother definition. If the users with low QoS measure are given higher priority ingaining additional resource, this maximizes the social welfare as well as fairness ofthe system.In order to fully explain the utility function, we need to specify the QoS measures,i.e., {Xzcij}mciz=1. The QoS measures further require to define the traffic types of whichthey belong to. We consider, the network has the similar types of traffic as [130]mentioned in their work. Since the traffic types are similar, we adopt similar formof QoS definitions. However, our QoS measure is the quantity when we schedule theRBs instead of the users. Hence, we reiterate the QoS metrics of each traffic typewith their exact interpretation in the following.1. Traffic with minimum throughput requirement: In order to ensure min-imum throughput, we need to design QoS measure so that the scheduler giveshigher priority to the user with lower throughput. While allocating RB j, letdenote the average throughput achieved by user (c, i) up to time t is ¯ζcij(t).The maximum incoming data rate for this user is ζmaxci , whereas the minimumrequired one is ζminci . As we discussed before, the property of our utility functionis such that the scheduler gives priority to the user with lower QoS measure.Therefore, the QoS metric of user (c, i) for this type of traffic at time t whileallocating RB j has been defined as X1cij(t) =(µ1ci − ζminci¯ζcij(t)), where 0 ≤ µ1ci ≤ 1.Smaller value of µ1ci gives more weight to this metric. This metric is also termedas fairness measure for this type of traffic. If any user obtains lower throughput122Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networkswhen the scheduler tends to allocate one RB, because of the lower value of thismetric, the scheduler is forced to give provision to this user. Consequently, totalutility of the system is maximized and the welfare of the system is maintained.2. Traffic with bounded delay constraint: There are some traffics (e.g., audio,VoIP) which have some certain delay constraint. In order to design the metricfor this class of traffic, let denote packet HOL delay of user (c, i) is Dcij(t) attime instant t while making the scheduling decision of RB j. The maximumdelay bound that user (c, i) can tolerate is Dmaxci . Similar to the case of trafficwith throughput requirement, this metric represents the fairness. We define thismetric as X1cij(t) =(µ1ci − Dcij(t)Dmaxci), 0 ≤ µ1ci ≤ 1. Lower value of µ1ci gives moreweight to this metric. If any user (c, i) of this traffic type starts to experiencehigher packet delay, X1cij(t) appears to get lower value while allocating RB j,and hence the scheduler gives more priority to that user.3. Best effort traffic: Best effort traffic has usually lower priority comparedto other traffic types described earlier. If any user receives considerably lowerthroughput comparing with other users in the system, in order to ensure fairdistribution of resource, we need to design a metric for this type of traffic. De-note the measure X1cij(t) = ¯ζcij(t)max(c,i)¯ζcij(t)− µ1ci , 0 ≤ µ1ci ≤ 1. The starvationof the users with lower average throughput results in unfairness. Hence, byserving those users at some point, the scheduler maintains the social welfare ofthe system. If the scheduler would serve a user with higher average throughput,it might further increase that individual user’s throughput, however that con-tribution is lower towards the system compared to the case when the schedulerwould serve a user with lower average throughput. The role of µ1ci is the weight123Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksfor this measure, and larger value gives additional weight to this metric.4. Traffic with minimum throughput and bounded delay requirements:If the traffic has both minimum throughput requirement and bounded delayconstraint, the QoS measure for this type of traffic can be defined as X1cij(t) =(µ1ci − wt¯ζcij(t)ζminci− wd Dcij(t)Dmaxci). Similar to other types of traffic discussed above,lower value of µ1ci gives higher priority to this QoS factor. Whether we wantto give priority to delay bound or minimum throughput of this traffic type, isdetermined by the values of wd and wt. wd and wt are normalized by 1, i.e.,wd +wt = 1. If we want to ensure equal priority to both delay and throughputof this type of traffic, we can set wd = wt = 0.5.No matter the traffic type, we need another QoS metric which gives priorityto the user with better channel condition. We define this metric as X2cij(t) =µ2ci − Rcij(t)(max(c,i)Rcij(t)) , 0 ≤ µ2ci ≤ 1. We normalize the user’s instantaneous rateon RB j by the maximum possible rate achieved using this RB. The normalized ratehas been subtracted from µ2ci, because we want to make sure that the user with betterinstantaneous rate obtains lower quantity compared to the one with worse channelcondition. µ2ci works as a penalty of not serving users with good channel condition.Larger value of µ2ci gives more weight to this QoS measure. The users with betterchannel condition will have lower quantitative value for metric X2cij(t), and henceaccording to the property of the utility function, the scheduler should give moreprovision to those users while allocating RB j at time t.So, we have concluded that we have two QoS measures: one for ensuring fairnessof specific traffic type, X1cij(t) and another one is common to all users X2cij(t) forensuring the provision when the users have better channel condition.124Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks6.3 Solution Approach and Scheduling AlgorithmIn the previous section, we have seen that the marginal utility of a user is the per-formance metric to maximize in order to maintain the social welfare of the system.Hence, at each scheduling epoch, we want to maximize the sum marginal utility of allusers across all RBs, i.e., we want to maximize∑(c,i)∈M∑j∈N exp{−ac[X1cij +X2cij]}.It implies, the objective function is to maximize∑(c,i)∈M∑j∈N−ac[X1cij +X2cij]. Wedenote Rmaxj by Γmaxj . Since the objective function and the constraint in Equation 6.8have Γmaxj , it is required to add an additional constraint in the problem formulationin order to support this assignment. Taking all constraints, the resultant formulationyieldsmax(x,P)∑(c,i)∈M∑j∈Nac(RcijΓmaxj− µ2ci −X1cij)(6.11)∑(c,i)∈Mxcij ≤ 1, ∀j∈N,∑j∈Npcij ≤ Pci, ∀(c, i)∈Mif xcin = 1 && xci(n+1) = 0, xcij = 0, n+ 2≤j≤Nif xcin = 1 && xci(n−1) = 0, xcij = 0, 1≤j≤n− 2Γmaxj −Rcij ≤ Γmaxj , Rcij ≤ Γmaxj .The problem in Equation 6.11 has no duality gap and we can solve it by formu-lating it as a dual problem with the associated dual variables α = (αci)(c,i)∈M forthe constraint in Equation 6.2, β = (βj)j∈N for the constraint in Equation 6.3 andγ = (γcij)(c,i)∈M,j∈N for the constraint in Equation 6.9 and δ = (δcij)(c,i)∈M,j∈N forthe last supportive constraint. The resultant Lagrangian looks like125Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksL(α,β,γ, δ,x,P) :=∑(c,i)∈M,j∈Nac(RcijΓmaxj− µ2ci −X1cij)(6.12)+∑(c,i)αci(Pci −∑jpcij)+∑jβj1−∑(c,i)xcij+∑(c,i)∑jγcij(Γmaxj − Γmaxj +Rcij)+∑(c,i)∑jδcij(Γmaxj −Rcij).From the duality theory, the optimal solution to the problem in Equation 6.12 isgiven bymin(α,β,γ,δ)>=0max(x,P)L (α,β,γ, δ,x,P) . (6.13)In order to solve this problem, first we find the optimal value of x and P givenfixed values of α, β, γ and δ. Once we obtain P, we rearrange the Lagrangian insuch a way that it becomes the function of mutually exclusive per user cost function,denoted by βcij. The optimal value of βj is the maximum possible value of βcijover all users for RB j taking the RB contiguity constraint in Equation 6.3 intoaccount. Because of the RB contiguity constraint, multi-user diversity of OFDMA-based systems may not be achievable. Finally, the optimal values of α, γ and δare obtained by the help of subgradient-based numerical search method. Taking thederivative of Equation 6.12 with respect to pcij, and following the K.K.T condition,we obtain optimal pcij, i.e.,p∗cij = xcij[ac(1 + γcij − δcij)αci− 1ecij].Substituting p∗ into Equation 6.12, we obtain126Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksL(α,β,γ,x) :=∑(c,i)∑jxcij (f(αci, γcij, δcij, ecij)− βj) (6.14)+∑(c,i)αciPci +∑jβj +∑(c,i)∑jγcijΓmaxj (− 1) +∑(c,i)∑jδcijΓmaxj ,where f(αci, γcij, δcij , ecij) = ac(hcijΓmaxj− µ2ci −X1cij)+γcijhcij−δcijhcij+ 1ecij−ac(1+γcij−δcij)αci,hcij = log(acecij(1+γcij−δcij)αci), Γmaxj = max(c,i) hcij. We denote the (c, i)th user’s costfunction on RB j f(αci, γcij, δcij, ecij) by βcij. Given that xcij∈[0, 1], the optimal valueof x is obtained by following the procedure below. For the sake of procedure, we copythe elements of set N in another set N′.1. First, for each RB j∈N′, find the best RB metric among all users and denoteit by β˜j = max(c,i)∈M βcij. Second, find a RB permutation {νj}j∈N such thatβ˜ν1 >= β˜ν2 >= · · · >= ˜βνN . Select the RB with index ν1 and its designateduser (c, i)|ν1 (to which it obtains the maximum value of the cost function),check whether the selected RB and its designated user meets the RB contiguityconstraint. It means, if the designated user has already some RBs allocated,selected RB should be the contiguous to its allocated RB block; otherwiseselected RB should be belonged to the designated user without any hesitation.If the RB with index ν1 fails to satisfy the RB contiguity constraint, then theRB with index ν2 is chosen and this operation continues until the selected RBsatisfies the RB contiguity constraint. We denote finally selected RB as ν∗ andits designated user is (c, i)|ν∗ . There might be ties in this assignment whichcan be resolved by some inefficient search. Therefore, optimal x for RB ν∗ isobtained as follows.127Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksx∗cij =1 if j = ν∗, (c, i) = (c, i)|ν∗0 if j = ν∗, {(c, i)∈M|(c, i) 6=(c, i)|ν∗}.2. Since the Lagrangian is a sum of the users’ cost functions βcij, we can minimizeL(.) over β for the given values of α, γ and δ by setting β∗ν∗ = β˜ν∗ . More thanone user can obtain the value β∗ν∗ , however the ties can be broken arbitrarilywithout losing the optimality.3. Remove RB ν∗ from set N′.Substituting optimal x and β into the Lagrangian, the resultant Lagrangian yieldsL(α,γ, δ) =∑(c,i)∑j[βcij − β∗j]++∑(c,i)αciPci+∑jβ∗j+∑(c,i)∑jγcijΓmaxj (− 1)+∑(c,i)∑jδcijΓmaxj .(6.15)Notice that the Lagrangian in Equation 6.15 is the function of α, γ and δ. Now,the optimal values of α, γ and δ can be obtained by minimizing L(.), and this is theoptimal solution of Equation 6.15. We have adopted the subgradient-based searchapproach in order to obtain optimal α, γ and δ. The subgradient search requires thefollowing updates in each iterationαci(t+ 1) = αci(t)− κ(t)(Pci −∑jp∗cij(t))(6.16)γcij(t+ 1) = γcij(t)− κ(t)(Γmaxj (t)− Γmaxj (t) + hcij(t))(6.17)δcij(t+ 1) = δcij(t)− κ(t)(Γmaxj (t)− hcij(t)). (6.18)128Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksThe step size κ(t) in iteration t+ 1 is given byκ(t) =L˜− L (α(t),γ(t), δ(t))∣∣∣ dL(.)dα(t) ∣∣∣2 + ∣∣∣ dL(.)dγ(t) ∣∣∣2 + ∣∣∣dL(.)dδ(t) ∣∣∣2, (6.19)where∣∣∣ dL(.)dα(t) ∣∣∣ =√∑(c,i)∈M(Pci −∑j p∗cij(t))2,∣∣∣ dL(.)dγ(t) ∣∣∣ =√∑(c,i)∈M∑j∈N(Γmaxj (t)− Γmaxj (t) + hcij(t))2, and∣∣∣dL(.)dδ(t) ∣∣∣ =√∑(c,i)∈M∑j∈N(Γmaxj (t)− hcij(t))2. L˜ is the estimate of the Lagrangiandetermined from the previous iterations. Given that P = max(c,i)∈M Pci and emax =max(c,i)∈M maxj∈N ecij, for this problem, each element ofdL(.)dαis bounded within therange [0, P ] and that of vectors dL(.)dγ, dL(.)dδis within [0, (1 + logemaxP )]. Under thisstatement, the optimal values of the Lagrangians are achievable within the finitenumber of iterations. The detailed procedure of achieving convergence is given inExercise 6.3.2 of [131]. This problem has M + 2MN number of dual variables, andit requires several thousands of iterations to achieve convergence. Moreover, in eachiteration, there is an issue of resolving ties which requires some inefficient search.Given these disadvantages, this procedure as a scheduler may not be efficient toimplement in the fast time scale. Hence, we have proposed a suboptimal algorithmpresented in Algorithm 7.In Algorithm 7, gci(j) is given bygci(j) =∑n∈Ω′ci(j−1)log(1 + p∗cinecin)−∑n∈Ωci(j−1)log(1 + p∗cinecin), (6.20)where Ω′ci(j) = Ωci(j − 1)∪lci(j). lci(j) is the best unallocated RB for user (c, i). p∗cijis the power on RB j after doing the power control on the set Ωci(j) or Ω′ci(j) foruser (c, i). Power control of user (c, i) on the set Ωci(j) is equivalent to solving thefollowing optimization problem129Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksFigure 6.2: Sample subframe structure for stage 2 of Algorithm 7.argmax∑n∈Ωci(j)pcin = Pci∑n∈Ωci(j)log (1 + pcinecin) . (6.21)The problem in Equation 6.21 can be solved by dual formulation which we havegiven in Section 3.5.4 of Chapter 3. The complexity of this operation is found tobe |Ωci(j)|. Furthermore, in the 1st stage of the algorithm, Γci(j) = gci(j). In the2nd stage, we define Us(j) as∑s∈Lsj∑(c,i)∈Lj −ac (X1ci +X2ci), and the parametersinside the sum term are determined presuming the network status at the beginningof current scheduling epoch.The worst case computational complexity of step 5 is O(MNlogN). Other steps,such as steps 8, 10 have the worst case complexity of O(M), which is dominated bystep 5. Hence, total computational complexity of the algorithm before step 14 (orstage 2) is O(MN2logN). For the 2nd stage of the algorithm, we discuss its worstcase complexity as follows. In the worst case, from the 1st stage, 1 user gets 1 RBandM RBs of all users are adjacent. Therefore, the remaining number of unallocated130Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksAlgorithm 7 Suboptimal RB allocation algorithm.1:  is tolerable rate loss percentage and set by the service provider.2: Set j := 0, Ωci(j) := ∅ for each user (c, i).3: while j < N do4: Set j := j + 1.5: Get the best RB index lci(j) for each user (c, i).6: If user (c, i) had already RBs allocated, lci(j) is selected from at most 2 con-tiguous RBs, otherwise lci(j) is arbitrarily chosen.7: Calculate metric gci(j) and Γci(j) for each user (c, i).8: Calculate Γmax(j) := max(c,i)Γci(j).9: Calculate H := Γmax(j).10: Determine users (c, i)∈Lj so that (Γmax(j)− Γci(j)) <= H.11: Find (c, i)∗ := argmax(c,i)∈Ljac(gci(j)Γmax(j)− µ2ci −X1cij).12: Assign the jth resource block to user (c, i)∗Ωci(j) :={Ωci(j − 1)∪lci(j) if (c, i) = (c, i)∗Ωci(j − 1) Otherwise.13: end while14: repeat15: Take one unallocated RB j.16: Let the users set on the right or left of RB j is Lj (presented in Figure 6.2).17: Obtain the base cumulative rate χ(j) =∑(c,i)∈Lj Rci.18: Obtain the base cumulative utility U(j) =∑(c,i)∈Lj Uci.19: We index shifting operation by s and set holding all indexes is Lsj.20: Provide edge users in set Lj (e.g., user 1 in Figure 6.2) available RBs ifnecessary, ∀s∈Lsj.21: Determine the cumulative rate χs(j) and the cumulative utility Us(j), ∀s∈Lsj.22: Determine shifting set L′sj so that (χmax(j)−χs(j)) <= H and Us(j) >= U(j).23: Find optimal s, s∗ := argmaxs∈L′sj Us(j).24: until No Improvement is possibleRBs is N −M , and the loop of the 2nd stage runs N −M times. Inside the loop,we may need to shift M times, and each shifting requires power control and otherprimitive steps, which are of O(1) complexity. Hence, the worst case complexity ofthe 2nd stage is (N −M)M , which is again dominated by the complexity of the 1ststage.131Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks6.4 Characteristics of Proposed Scheduling SchemeIn this section, we first prove that our scheduling scheme achieves much fairer re-source distribution compared to [130]. Second, we discuss the impact of opportunitycost function on the scheduling outcome, and show that for certain value of H, theproposed scheduling scheme can bridge between the MT (which has the best globalperformance) and PF (which is well-known for proportional fairness) schemes. In thelast paragraph, we have briefly discussed the practicality of our scheduling schemewith respect to other schedulers implemented in practice.Conjecture 6.1: Our scheduling scheme (both the optimal and Algorithm 7) ismore efficient in terms of achieving fairness compared to [130].Proof: Consider an epoch where there is 3 RBs and 3 remaining users availableto schedule. User 1 has the best SNR condition for all RBs, i.e., e1j >> e2j, e1j >>e3j, ∀j∈[1, 3]. User 2 has almost similar SNR condition compared to user 3, howeverslightly better. The packet HOL delay for user 1 is much smaller compared to user2, i.e., D1 << D2 (or ζ1 >> ζ2) and D2 ≈ D3 (or ζ2 ≈ ζ3). If we would apply thescheduling technique presented in [130], it is likely that the rate obtained by user 1is much higher compared to that of user 2 or 3 due to the favorable physical layercondition. In our simulation, we observe, if any user has favorable channel condition,it is more likely, that user obtains more RBs comparing with others. Hence, in ourscenario, there is a chance that user 1 gets 2 RBs and user 2 gets 1. However,the result is not fair given the packet HOL delay or throughput. With our scheme,possible RB allocations are: 1) user 1 may get first RB due to its good SNR conditionon all RBs, then RB 2 is assigned to user 2 due to its better SNR condition on theremaining RBs and almost similar packet HOL delay or throughput compared to user3, finally user 3 gets the remaining last unallocated RB. 2) user 1 may obtain the 1st132Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksRB due to the similar reason described above, user 2 gets remaining 2 RBs becauseof its SNR condition and the worst QoS performance compared to user 3.These 2scheduling decisions are considered as fair compared to that by [130].In order to show that there is no scenario that the scheduling technique [130]outperforms our scheme, we introduce a counter example of this example. Similar tothis example, consider user 1 has the best channel condition on all RBs compared tothe other two users. Unlike before, the average packet HOL delay or throughput ofthis user is much worse compared to the other two users. The channel condition ofuser 2 is little better compared to user 3 on all RBs, however much worse comparedto user 1. Furthermore, the packet HOL delay or throughput for these two usersare almost similar, however better than user 1. For the similar reason explained inthe previous example, by the scheduler [130], user 1 obtains first 2 RBs and user2 obtains the 3rd RB. On the other hand, by our scheduling scheme, two possibleRB allocations are: 1) user 1 gets first 2 RBs because of its best channel conditionand worse packet HOL delay or throughput. The rest 1 RB will be allocated touser 2 because of its slightly better channel condition compared to user 3. 2) user 1obtains all 3 RBs. The scheduling decisions by both [130] and our scheduling schemeare considered as fair. Hence, there is no scenario for which the scheduler [130] canperform better than our scheduler. Our scheduling scheme always achieves better oras good as performance in terms of fairness comparing with [130].Lemma 6.1: Under the special case (H = 0), Algorithm 7 converges to the MTscheme.Proof: In the 1st stage of Algorithm 1, the MT scheme assigns RB lci(j) to user(c, i) when it achieves the maximum quantity for gci(j) compared to other users;whereas for the 2nd stage, it selects shifting operation which has utility greater than133Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksthe base cumulative utility and have the maximum value comparing with other shift-ing operations. Set H = 0, at the 1st stage, our scheduler selects only one userfor set Lj whose gci(j) has the maximum quantity in order to satisfy the conditionΓmax(j) − Γci(j) <= 0. Afterward, since Lj has only one user, eventually this userwill be picked for RB lci(j). For the 2nd stage, similar situation happens, L′sj containsonly the shifting operation which incurs the highest utility and has larger value com-pared to the base cumulative utility. Hence, the converging trend of our algorithmtowards the MT scheme has been proved.Lemma 6.2: For the special value (the maximum achievable rate, RateMax) ofH, Algorithm 7 is transformed to the PF scheme.Proof: At scheduling epoch t, while scheduling RB j, the PF algorithm assigns RBlci(j) to user (c, i) if its metric log2(1+gci(j)¯ζcij) obtains larger quantity compared to otherusers. Note that the PF metric is an increasing function of gci(j) and a decreasingfunction of its long term throughput ¯ζcij. Consider about our scheme with H = Rmaxj ,set Lj contains all potential users in the system. And, then, the scheduler picks theuser whose marginal utility, i.e., slope obtains the highest quantity. The slope of auser is the increasing function of gci(j) and has a decreasing trend with respect to itslong term throughput ¯ζcij. Mathematically, we can equate both functions in order tofind the instantaneous value for the constants. Hence,log2(1 +gcij¯ζcij) = − ac(µ1ci −ζminci¯ζcij+ µ2ci −gcijΓmaxj).Simplifying this, we obtainµ2ci + µ1ci = −1aclog2(1 +gcij¯ζcij) +ζminci¯ζcij+gcijΓmaxj.Therefore, we can conclude, at scheduling instant t while allocating RB j, if the134Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksvalue of µ2ci+µ1ci is equivalent to the right hand side of above equation (for user (c, i)),and if we ignore the opportunity cost function, over the infinite time, our schedulingalgorithm converges to the PF scheme. In the similar manner, for the 2nd stageof Algorithm 7, we can prove that at scheduling epoch t, certain value of constant∑(c,i)∈Lj µ2ci + µ1ci results in the asymptotic convergence towards the PF scheme.Proofs 6.1 and 6.2 remind us that the presented scheduling algorithm in thisthesis is generalized. In general, this scheduler works in between these two extremecases which has been proved in the next section. Since the optimal solution is aniterative procedure, for this, there is no closed form proof for Lemma 6.1 and Lemma6.2. However, for the same condition of these two Lemmas, the optimal solutionconverges to the MT and PF schemes, respectively. Adjusting the parameter of theopportunity cost function, we can convert this scheduler to two conventional extremecases of scheduling scheme.Furthermore, we have noticed that Huawei [132] has implemented an enhancedPF scheduler for the GBR traffic. Packet delay budget of different GBR traffic andaggregate RB quality are considered while designing this scheduler. For the uplinkscheduling, this scheduler first calculates priority metric of each user which is a func-tion of average packet delay and approximate average channel quality over all RBs ofthat user, and then based on the priority, it allocates RBs among those users. Thepriority metric is calculated using MW formula, and M-LWDF is similar version ofthe MW rule. Whereas, our scheduler does one by one RB allocation based on theinstantaneous RB’s channel quality and average packet delay, which is apparentlymore dynamic. Moreover, our scheduler can deal the traffic with throughput require-ment, and the design of the scheduler is flexible for diverse QoS (e.g., packet lossratio, packet jitter) oriented traffic. Besides, the scheduler designed by Ericsson [133]135Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksapplies conventional traffic policing and shaping concept while allocating RBs amongdifferent QoS-based traffic. Policing ensures that the users do not get the agreedupon configured rate, whereas traffic shaping makes sure that the users get at leastminimum settled QoS specified in their agreement with the vendor. Based on thetraffic policing and shaping mechanisms, our scheduler is dynamic and can achievethe similar level of performance as the scheduler equipped with these policies.6.5 Performance EvaluationIn this section, we will evaluate Algorithm 7 for four classes of traffic. First, weoutline the simulation methodology we have adopted. Then, the simulation resultsare split in two parts for Homogeneous and Heterogeneous traffic, respectively.6.5.1 Simulation MethodologyFor setting up the network, we put the base station at the center of a cell, user nodesat different distance surrounding the base station. Cell radius is assumed as 1 km.We run the simulation over 5000k TTIs. One TTI is equivalent to 1ms and it consistsof 25 RBs. Each RB is analogous to 12 subcarriers [6]. These total 25×12 subcarriersare spread over 5 MHZ bandwidth. The theoretical limit [82] of the channel capacityis given by β = −1.5ln(5Pb), where Pb denotes the BER. BER for the channel is configuredas 10−6. Each user’s maximum power is set as 220 mW. In order to calculate thepath loss effect of the channel, we assume the reference distance as 1 km and theSNR for this reference distance is 28 dB. The reference shadowing effect is the lognormal distribution with variance 3.76. With this variance, log-normal shadowingpower is determined as 10.6 dB according to [134]. Rayleigh fading effect is capturedby a parameter a such that E[a2] = 1. The channel gain for a particular user (c, i)136Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksover RB j is computed byGcij,dB = (−κ− λlog10dci)− ξcij + 10log10Fcij. (6.22)In Equation 6.22, the first term κ captures propagation loss, the value of whichis 128.1 dB. dci is the distance in km from user (c, i) to the base station, and λ is thepath loss exponent which is set to a value 3.76. The second term ξcij captures the pathloss effect for the reference distance 1 km. Whereas, the last term Fcij corresponds tothe rayleigh fading effect. Feedback duration due to the exchange of CSI, schedulingdecisions between the users and base station is considered as negligible. Perfect CSIestimation is assumed at the base station.In order to demonstrate the ability of our uplink scheduling scheme, we needto justify that users with different QoS measures obtain expected service which hasalready been specified theoretically. In the previous section, we have designed theutility function with 3 different QoS measures. Now, we want to define 4 differentclasses for the users where each class is accompanied with one QoS measure. Fourdifferent classes are: VoIP (class 1), audio streaming (class 2), video streaming (class3) and FTP (class 4). Class 1 has the highest priority and class 4 is the type oflowest priority. Class 1 and 2 traffics have delay bound constraint. Video streaminghas minimum throughput constraint14, whereas class 4 is the type of best effort traffic.In order to distinguish priority of different classes, we set the parameters for ac andµci, which are shown in Table 6.5.1.For VoIP traffic, we have taken adaptive multi rate (AMR) codec [135] method.According to this model, packets are generated using a negative exponentially dis-14There are two types of video traffic, e.g., interactive video with stringent real-time requirements;video streaming and video download with some minimum bandwidth requirement. In our simulation,each video flow is of second type.137Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networkstributed ON-OFF pattern to replicate the talk and silent duration of a VoIP call.The mean duration of ON and OFF periods are 3 s. During the ON period, in every20 ms interval, a voice packet of 244 bits is generated. Including the compressedIP/UDP/RTP header, the data rate for each VoIP flow becomes 13.6 Kbps. Accord-ing to [136], the maximum acceptable delay for voice is 250 ms. Considering the delayinduced by the core network and the delay for RLC and MAC buffering, the tolerabledelay at the radio interface should be at most 100 ms [6], which represents a verystrict requirement. For modeling audio streaming traffic, we have also used AMRcodec. The size of the packets generated for each audio streaming user is uniformlydistributed between 244 and 488 bits, and hence the data rate varies from 12 Kbpsto 64 Kbps. The maximum delay threshold has been set 150 ms for each user. Videostreaming is modeled with a minimum data rate of 64 Kbps and a maximum datarate of 384 Kbps. The size of the packets in each video flow is uniformly distributedbetween 1200 and 2400 bits. Hence, the resultant each video flow generates the num-ber of packets which is uniformly distributed between 1 and 3 at the interval of 19ms.15 The data rate of each user with FTP traffic is assumed as maximum 128 Kbpswith the size of a packet 1200 bits. Packet generation interval of each FTP flow is 10ms. In the simulation, we assume each user is equipped with one class of traffic andit keeps holding that flow until the simulation is finished. All the results describedin the following subsection are average of 20 simulation runs. As the simulation tool,we have modified the matlab-based LTE simulator [137] with all functionalities ofour scheduling scheme.15Each video flow is designed following the trace file "sony" taken from"http://trace.eas.asu.edu/h264/". The statistics of this trace is: a. Inter-arrival time be-tween two bursts is constant (33 ms), b. Burstiness of the video is determined by the size of theburst. The maximum frame burst of this video is 326, 905 bytes and the minimum one is 20, 209bytes. Burstiness of our each video flow is determined by the number of packets and packet size.According to our statistics, maximum frame size of each video flow is 7200 bits and the minimumone is 1200 bits.138Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksTable 6.1: Simulation parameters.Traffic Type ac µ1ci µ2ciVoIP 4 0.4 0.3Audio 3.5 0.4 0.3Video 3.0 0.4 0.3FTP 2.5 0.4 0.66.5.2 Simulation ResultsFirst we show the simulation results for homogeneous traffic, i.e., VoIP and traffic withthroughput requirement (video streaming). With regard to this experimentation, wehave compared the results obtained by our scheduling algorithm with the existingwork. For VoIP traffic, we have compared our results with M-LWDF [63], EXP [54]rules and [62]. EXP and M-LWDF rules are specifically developed for the downlinkscheduling of delay sensitive multimedia traffic in OFDM-based systems, whereas [62]is for the uplink scheduling scheme. Since these schemes have limitations and arenot directly comparable to our scheme, we have extracted scheduling rules fromthose works and substitute in our algorithm in order to have valid comparison. Thescheduler under M-LWDF rule assigns RB lci(j) to the user (c, i)∗ abiding by theformula(c, i)∗ = argmax(c,i)∈Ngci(j)ζ¯ciDcij.The scheduler with EXP rule obeys the following rule for RB lci(j)(c, i)∗ = argmax(c,i)∈Nbciexp aciDcij1 +√(1/N)∑(c,i)Dcij gci(j),where bci = 1/E[gci] and aci = 6Dmaxci .139Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksFor ensuring guaranteed bitrate, we did not find much work in the literatureexcept [55]. Therefore, for the homogeneous video streaming setup, we have doneperformance comparison with [55] as well as with the MT and PF schemes.Although [54] is the solution for mixed traffic, they did not consider the trafficwith guaranteed bit rate while evaluating the performance. The most recent workdealing all types of traffic is [59], and we have taken it as a performance benchmarkwhile presenting the results of mixed traffic obtained by our scheme.For the performance metrics, we consider average packet delay, average normalizedthroughput, proportion of per RB rate loss on behalf of the service provider, perRB normalized utilization, total system’s effective rate, fairness in the system. Formeasuring fairness over all users in the system, we have used well-known fairnessindicator named as Jain Fairness Index (JFI) [83]. Proportion of per RB rate lossis the indication of how much proportion of rate is sacrificed from the maximumone (that could be achieved) while taking the scheduling decision of each RB. Onthe other hand, per RB utilization is the measure of RB utilization over the entiresimulation interval. While computing RB utilization, 0 is counted when any RB staysvacant and contributes to the average per RB utilization. Furthermore, we consider,the users are spread uniformly between 0.5 km to 0.8 km distance from the basestation.In the second part of the simulation results, we have studied the performance ofthe multiplexed traffic. The simulation scenario is designed in such a way that we seethe strength of our scheduling scheme which can prioritize different classes of trafficand can reach to an elegant scheduling decision.140Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks100 150 200 250 300 350 400 450 50020406080100120140160180200Number of UsersPer User Average Packet Delay (ms) Our(RateLoss=MaxRate)M−LWDFOur(RateLoss=0.5MaxRate)Our(RateLoss=0)EXP[54](a) Per user average packet delay comparison be-tween our scheme and others (infinite buffer).100 150 200 250 300 350 400 450 50020406080100120140160180200Number of UsersPer User Average Packet Delay (ms) Our(RateLoss=MaxRate)M−LWDFOur(RateLoss=0.5MaxRate)Our(RateLoss=0)EXP[54]Pkt Loss >= 2% Pkt Loss >= 2%(b) Per user average packet delay comparison be-tween our scheme and others (finite buffer).100 150 200 250 300 350 400 450 5000.350.40.450.50.550.60.650.70.750.80.85Number of UsersJFI of Average Packet Delay Our(RateLoss=MaxRate)M−LWDFOur(RateLoss=0.5MaxRate)Our(RateLoss=0)EXP[54](c) JFI of average packet delay comparison betweenour scheme and others.100 150 200 250 300 350 400 450 5000.30.40.50.60.70.8Number of UsersPer RB Normalized Utilization Our(RateLoss=MaxRate)M−LWDFOur(RateLoss=0.5MaxRate)Our(RateLoss=0)EXP[36](d) Per RB normalized utilization comparison be-tween our scheme and others.Figure 6.3: VoIP.141Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks100 150 200 250 300 350 400 450 500−0.1−0.0500.050.10.15Number of UsersPer RB Normalized Rate Loss Our(RateLoss=MaxRate)M−LWDFOur(RateLoss=0.5MaxRate)Our(RateLoss=0)EXP[54]Figure 6.4: Per RB normalized rate loss comparison between our scheme and other(VoIP).6.5.2.1 Homogeneous Traffic (VoIP)Figure 6.3(a) depicts the average packet delay of VoIP traffic with respect to thetotal number of users in the system. First observation from this figure is, with theincreased number of users, the average packet delay is increased for all cases. Wehave shown the results of our algorithm for different maximum tolerable rate loss,i.e., RateMax, 0.5RateMax and 0. As we mentioned before that if maximum tolerablerate loss is RateMax, it treats all users as if the network operator does not haveproblem with any rate loss, this setting treats all users equally. The figure indicates,for the parameters given in Table 6.5.1, our scheme (with the maximum tolerablerate loss RateMax) has better performance compared to the scheduler with EXP andM-LWDF rules. The M-LWDF and EXP rules are specifically designed for the delaysensitive multimedia network. The formula of the M-LWDF scheduler is based onthe product of the packet HOL delay and PF factor. Hence, the resultant schedulingpolicy ensures fairness among the users. The scheduler with EXP rule is more robust142Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksthan the scheduler with M-LWDF rule. This is because the exponential functiongrows much faster with its argument. Furthermore, the EXP scheduler also takes theoverall network status into account, because the delay of considered user is somehownormalized over the sum of experienced delay of all users. Better performance of ourscheme with respect to M-LWDF and EXP rules justifies its efficacy for the usage ofdelay sensitive VoIP traffic.16 At low load, [62] performs almost in the similar mannercompared to our algorithm with negligible deviation. However, at high load, the userswith moderately better channel condition have more priority, while the users withworst channel condition almost starve, because the scheduling rule depends on thetime difference between the current and recent burst. Therefore, within a fixed timeperiod, the users with good channel condition get scheduled while keeping the userswith worst channel starved. While serving these users, another burst of traffic arrivesfor all users and hence the delay based metric is replaced by the same value for allusers including the users with worst channel. Therefore, in the second round, for thesame value of delay based metric, the same set of users with good channel conditionget served which results in starvation for the users with worst channel. If the delaybased metric of [62] would consider the time of first burst instead of recent, it wouldperform better at high load. When the maximum tolerable rate loss is 0, our schemeperforms poorly. This is because the scheduler cannot tolerate any rate loss and itonly serves the high rate generating users which causes higher packet delay for otherusers. Due to the higher packet delay of the low rate generating users, the resultantaverage packet delay of the system gets larger. The performance of our scheduler withthe maximum tolerable rate loss 0.5RateMax has in-between performance of other twofor the similar reason. Instead of using infinite buffer, if we use finite buffer at each16By adjusting the parameters µ1ci, µ2ci in our scheduler and the parameters aci and bci in the EXPscheduler, better or comparable performance (with respect to our scheduler) can be achievable bythe scheduler with EXP or M-LWDF rule.143Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksterminal with limited size, we observe packet loss. We define the outage of a systemwith VoIP users when its packet loss exceeds 2%. This is because if a user suffersat least 2% packet loss, it is likely that the packets of that user cannot be decoded.Therefore, due to the limited buffer, even though the average packet delay of thesystem is below the noted limit, QoS is not met for the users in the system becauseof more than 2% packet loss. Hence, we see in Figure 6.3(b) that the coverage ofthe system with finite buffer is at earlier point compared to that with infinite buffer.This justification applies for all schedulers.Our scheduler with the maximum tolerable rate loss RateMax experiences loweraverage delay. It implies, the scheduler gives more priority to the users with worsechannel condition compared to the scheduler with M-LWDF or EXP rule. Therefore,in terms of fairness, our scheduler with the maximum tolerable rate loss RateMaxoutperforms the rest others as depicted in Figure 6.3(c). The utility function com-bined with its parameters of our scheduler is specifically designed to preserve thefairness across the system while exploiting users’ varying channel quality condition.With the decrementing maximum tolerable rate loss, we see the decrementing JFI.This behavior is expected, because the scheduler picks selectively high rate generatingusers, and hence the scheme with the maximum tolerable rate loss 0 has the worstfairness. The metrics, such as percentage of RB utilization and rate loss are the bestfor this case and have been illustrated in Figures 6.3(d) and 6.4, respectively. Withthe decrementing tolerable rate loss, the scheduler gradually ignores the users withbetter channel condition and tries to serve the users whose average delay tends todeviate from the prescribed bound, and hence we see the decrementing RB utilizationand incrementing rate loss.144Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks60 80 100 120 140 160 1800.40.50.60.70.80.91Number of UsersPer User Normalized Throughput Our(RateLoss=MaxRate)Our(RateLoss=0)MTPFOur(RateLoss=0.5MaxRate)[47](a) Per user normalized throughput comparison be-tween our scheme and others.60 80 100 120 140 160 1800.30.40.50.60.70.80.91Number of UsersJFI of Normalized Throughput Our(RateLoss=MaxRate)Our(RateLoss=0)MTPFOur(RateLoss=0.5MaxRate)[47](b) JFI of normalized throughput comparison be-tween our scheme and others.60 80 100 120 140 160 1800.40.50.60.70.80.9Number of UsersPer RB Normalized Utilization Our(RateLoss=MaxRate)Our(RateLoss=0)MTPFOur(RateLoss=0.5MaxRate)[47](c) JFI of average packet delay comparison betweenour scheme and others.60 80 100 120 140 160 180−0.1−0.0500.050.10.15Number of UsersPer RB Normalized Rate Loss Our(RateLoss=MaxRate)Our(RateLoss=0)MTPFOur(RateLoss=0.5MaxRate)[47](d) Per RB normalized rate loss comparison be-tween our scheme and others.Figure 6.5: Video streaming.6.5.2.2 Homogeneous Traffic (Video Streaming)In order to present results for this case, a simulation setup similar to that usedin the previous subsection has been undertaken. Figure 6.5(a) shows the averagenormalized throughput with the increasing total number of users. It is expectedthat increased number of users deteriorates per user normalized throughput due tothe limited number of RBs available at each scheduling epoch. In the figure, wehave shown the performance of our scheme with three maximum tolerable rate loss,145Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks60 80 100 120 140 160 18014161820222426Number of UsersCell Throughput (Mbps) Our(RateLoss=MaxRate)Our(RateLoss=0)MTPFOur(RateLoss=0.5MaxRate)[47]Figure 6.6: Cell throughput comparison between our scheme and others (Video).i.e., RateMax, 0.5RateMax and 0. Our scheme with the maximum tolerable rate lossRateMax has the best performance. Because of the fairness measure in terms of peruser average throughput inside the exponential utility function, our scheme ensuresfairness across the users. In [55], the scheduler works in both time and frequencydomains. Time domain task partitions the users based on their throughput beingless and greater than the noted limit. The former list has absolutely higher prioritythan the latter one. Moreover, the priority metric for the first list is determinedfrom blind equal throughput, whereas the metric for the second one is the ratio ofinstantaneous wide band channel quality and the past average throughput. From thesorted priority list, N number of users are passed to the frequency domain schedulerwhich applies PF scheme in order to finalize the scheduled users. The PF scheme usesthe product of the instantaneous RB quality and inverse throughput in order to ensurefairness. This scheduler pre-processes the users while giving priority to the ones withlower throughput before applying the PF technique on them. Therefore, at low load,the PF technique and [55] perform almost similarly as the higher priority list selected146Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksby the time domain scheduler is empty, and hence there is no basic performancedifference between them. However, at high load, the higher priority list [55] getsbigger and bigger, and consequently it performs better compared to the PF one. Itis unusual to see that the MT scheme has lower per user normalized throughput,however, there is a intuitive reason behind it. This scheduler gives higher priority tothe users with better channel condition even though those contribute less towards theoverall system throughput, and hence several users with worse channel remain under-provisioned. Same thing happens to our scheduler with the maximum tolerable rateloss 0. The higher rate generating users are given priority in the scheduling decisionat the expense of the lower rate generating users, and hence the resultant normalizedaverage throughput of the system is lower. If we use limited buffer at each userterminal, we notice even lower coverage for all cases because of the buffer overflowresulting in packet loss.Unlike the results discussed in the previous paragraph, we observe better perfor-mance for the MT scheduler or our scheme with the maximum allowable rate loss0 in terms of overall cell throughput or percentage of RB utilization. The resultswith this respect are given in Figures 6.6 and 6.5(c), respectively. The MT or ourscheme with the maximum tolerable rate loss 0 selects only the users with betterchannel condition or the higher rate generating users. In either case, such behaviorof the scheduler increases cell throughput or enhances per RB utilization, howeverat the expense of the throughput for the users with worse channel condition or thelow rate generating users. Since [55] keeps busy in serving the low rate generatingusers at high load, per RB utilization is the worst for this scheduler. Because wegive priority to the best users at each scheduling epoch, the percentage of rate lossis 0 for the MT scheme or our scheme with the maximum tolerable rate loss 0 as147Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksdepicted in Figure 6.5(d). Whereas, the scheduling decision of other scheme [55] notnecessarily depends on user channel condition or rate, they check per user’s instantthroughput and relevant constraint. And, hence, the scheduler of this policy suffershigher rate loss. The fairness in terms of JFI comparison among all schemes is givenin Figure 6.5(b). Because of the exponential nature of the utility function, if any usergoes under the minimum throughput, our scheduler (with the maximum tolerablerate loss RateMax) is forced to serve that user, and hence ensures fairness across theusers while exploiting their instantaneous channel conditions. Because of the natureof the utility function, the PF scheme ensures fairness across the system, howeveris not as good as our scheme. At low load, the scheduler [55] behaves like the PFscheme and so thus the fairness. However, at higher load, its time domain scheduleris almost ignorant of the spectral efficiency, gives priority to the users with lowerthroughput, and hence achieves the highest fairness compared to all. Our schemedoes not deviate much from [55] in terms of fairness. With the decreasing maximumtolerable rate loss, our scheme also suffers from fairness measure because of givingprivilege to the higher rate generating users.6.5.2.3 Heterogeneous TrafficIn order to prove that our approach can handle multiplexed traffic efficiently, we havedeployed N users splitted equally and uniformly into 4 classes. Moreover, maximumtolerable rate loss is assumed as RateMax and buffer size in each terminal is consideredas infinite. Figures 6.7 and 6.8 compare the average packet delay of VoIP and audiostreaming users, respectively with that of [59]. In the same figure, we have shownthe results from the homogeneous setup obtained by our scheme. As VoIP has higherpriority than the audio streaming, in the heterogeneous setup, the VoIP users willalways incur lower packet delay comparing with the audio streaming users. Moreover,148Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks100 150 200 250 300 3500102030405060708090100Number of UsersPer User Average Packet Delay (ms) HetHom[51]Figure 6.7: Per user average packet delay comparison between homogeneous andheterogeneous setup (VoIP).100 150 200 250 300 35020406080100120140160180Number of UsersPer User Average Packet Delay (ms) HetHom[51]Figure 6.8: Per user average packet delay comparison between homogeneous andheterogeneous setup (Audio).149Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks100 150 200 250 300 35000.20.40.60.81Number of UsersPer User Normalized Throughput HetHom[51]Figure 6.9: Per user normalized throughput comparison between homogeneous andheterogeneous setup (Video).100 150 200 250 300 35000.20.40.60.81Number of UsersPer User Normalized Throughput HetHom[51]Figure 6.10: Per user normalized throughput comparison between homogeneous andheterogeneous setup (FTP).150Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networksthe heterogeneous VoIP users always have lower average packet delay than the casewith the homogeneous setup. This is because total users in the multiplexed case isequally divided among the rest 3 lower priority classes, and hence there are fewerVoIP users in this case comparing with the single type one. [59] always gives thehighest priority to the VoIP users whenever they have data in the queue no matterthe accumulated delay of the users is much lower than the bounded limit. On theother hand, the audio streaming users under multiplexed setup not necessarily alwayshave lower packet delay comparing with that of homogeneous case although there aresome lower priority users along with them. Since the data rate of each audio streaminguser is larger than that of a VoIP user, at low load, when the network is unsaturated,multiplexed less number of audio streaming users have enough resource to get theirpackets transmitted. However, as we increase the load, the number of VoIP usersincreases, they may occupy the entire resources of the network, in that case, we willbe able to see higher packet delay for the multiplexed case comparing with the singleclass case. Audio streaming is the second highest priority class and the data rate ofthe users with this class is much larger than that with VoIP, the scheduler in [59]apparently serves the users of this type whenever they have packets in the queue nomatter their packet HOL delay is lower or higher than the noted limit. This reasonresults in lower average packet delay compared to our scheme. However, when thenetwork will be saturated with the VoIP users, the audio streaming users will achievecloser or worse performance compared to our algorithm.Figures 6.9 and 6.10 depict the average normalized throughput for the videostreaming and FTP users, respectively. Similar to the previous figures, here, we haveshown the results for the homogeneous setup achieved by our scheduler. Since videostreaming is higher priority type, the users of this type incur higher throughput than151Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networks20 30 40 50 60 70 80 9010203040506070Number of VoIP UsersNumber of Video Users Het[51]Figure 6.11: Admission region with QoS guarantee comparison between our schemeand other.that of FTP. Similar to the audio streaming users, at low load, under multiplexedcase, the video streaming users achieve better performance comparing with the ho-mogeneous users. In addition, each video streaming user has much higher data ratecomparing with the combined VoIP and audio streaming users. If we increase thenumber of users in the network and it goes close to the saturation with the VoIP andaudio streaming users, the video streaming users will start to starve. And, at thatpoint, we will see the poor performance of the heterogeneous video streaming users.Same reasoning applies to the FTP users, at low load, we will see better performancefor the heterogeneous case. However, when all resource of the network is consumedby all higher priority traffic, the performance of the heterogeneous FTP users startsto deteriorate. Because of the blind provision towards the VoIP and audio streamingusers given by the scheduler [59], the video streaming users perform poorly comparedto our algorithm. For the similar reason, the throughput of FTP users is even worsecomparing with our scheme.152Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic NetworksFigure 6.11 compares the admission region of VoIP and video streaming usersin the system under multiplexed setup with [59]. Since [59] redundantly gives moreprovision to the VoIP users, the average per user packet delay designed by themis lower than that by our scheme as depicted in Figure 6.7. It starves the videostreaming users although the delay of VoIP users is lower than the required limit.Therefore, from the figure, we observe, although the number of VoIP users withQoS assurance is equal to our scheme, the number of video streaming users withguaranteed throughput is lower at increased load.6.6 Summary of the ChapterLTE and LTE-Advanced are specifically envisioned for the applications with high datarate. According to this standard, the spectrum is divided into time-frequency-basedresource units called RBs. Varying emergent applications prompt the development ofheterogeneous traffic networks with diverse QoS requirements. Besides the demandsof end users, resource utilization is an important matter to consider in order toassist the network operators. In this chapter, we have presented an uplink schedulingtechnique for LTE heterogeneous traffic networks which is able to maintain varyingQoS provision of end users while keeping the resource utilization (in RB level) ofservice providers in the prescribed range. In order to solve this problem, we havefirst formulated the problem considering all LTE standard specific constraints whilecapturing QoS factors of the users in a smart utility function. In addition to these,the formulation consists of a constraint which allows the service provider to keepgranular RB utilization level in some certain range. Having considered the discretenature of RB allocation, we have shown the optimal solution structure of the problemwhich has high computational complexity. From the guiding principles of the optimal153Chapter 6. Uplink Scheduling and Resource Allocation for Heterogeneous Traffic Networkssolution structure, we have proposed a suboptimal algorithm with polynomial timecomplexity. Furthermore, we have evaluated our scheduler in a network which hasthree different types of users, i.e., traffic with delay constraint, traffic with minimumdata rate requirement and best effort traffic. The results obtained from extensivesimulation show that the proposed scheme exhibits the tradeoff between the fairness ofend users and the resource utilization of service providers. By showing the simulationresults for both homogeneous and heterogeneous traffic networks in terms of severalperformance metrics, we have justified the efficacy and effectiveness of our schedulingscheme envisioned to be deployed in future LTE systems.154Chapter 7Conclusion and Future WorkIn Section 7.1 of this final chapter, we briefly review our results and highlight thecontributions of this thesis. In Section 7.2, we provide a few possible future worksresultant from the work of this thesis.7.1 Summary of the ThesisThis thesis is focused on the uplink scheduling and resource allocation of LTE-Advanced systems that incorporate relay(s) or carry heterogeneous traffic. The mainresults of each chapter are summarized as follows.In Chapter 3, we have proposed a uplink scheduling and resource allocation schemefor DF relay (with FD functionality) equipped LTE systems. Although there aremany sophisticated advancement on the uplink scheduling in relay aided systems,basic scheduling scheme is still missing. We fill that gap in the literature. Besidesproviding the solution for basic scheduling and resource allocation, the proposedsolutions are adaptive. If the relays are in the bad locations or cannot contribute muchtowards maximizing the network capacity, they are recommended to be disabled.However, due to the implementation complication, the solutions allocate resource forsome relays, which are not useful for the system. This is because the subgradientsearch in the solutions can reduce the duality gap of some bad relays. Throughimproving the convergence condition of the subgradient search, such types of problems155Chapter 7. Conclusion and Future Workcan be avoided. Furthermore, although SC-FDMA is the recommended transmissiontechnique for the LTE uplink, OFDMA is considered for this scheduling scheme.Perhaps, the idea of designing suboptimal algorithm in Chapter 6 can be used if SC-FDMA is taken as the transmission technique. The deployed relays in this problemare of FD functionality, and hence they do not need buffer to store incoming packets.This makes the deployment of relays cheaper and easier.We have seen in the problem of Chapter 3 that it is difficult for a relay to decidewhich users to serve under the power constraint even when the assignments of RBsare known. Hence, in Chapter 4, we have proposed a joint sources and relay powerallocation scheme for an AF relayed network. We have chosen to use AF relay herebecause of its simplicity. Existing solutions of this problem ignores the direct linkSNR in their problem formulation. Therefore, their schemes are unable to providecorrect solution when the direct link SNR of the sources are better than their relayedlink ones. Noticing this, we put the direct link SNR back in our formulation, and havesolved this using GP-based optimization technique. Having noticed the high com-putational complexity of the optimal solution, we also have proposed 2 suboptimalsolutions of this problem taking greedy and fair nature of the sources into account.Through extensive simulation, we have shown that the proposed solutions correctlyallocate power among the sources and relay even when their direct link SNR arebetter than their relayed link ones. Moreover, the suboptimal solutions achieve veryclose performance of the optimal one.We have observed the selfless nature of the users in the solution of the problemin Chapter 4. However, in the real world, the users in the network always want toearn some benefits while sacrificing their resource. To model such behavior of theusers, we have proposed a game theoretical solution of this problem in Chapter 5.156Chapter 7. Conclusion and Future WorkExcept at the beginning of the game, the nature of the game theoretical solution isdistributed. Therefore, it requires relatively less signaling overhead as it is supposedto be. Through extensive simulation, we have shown several properties of this solu-tion. Moreover, we have proved that the proposed solution can achieve comparableperformance with the centralized optimal solution under certain convergence condi-tion. The cost functions designed for this solution ignored the log term of the ratefunctions. The solution would be more accurate if the log term would be incorporatedin the cost functions.In Chapter 6, we have proposed an uplink scheduling and resource allocationscheme for heterogeneous traffic networks. To the best of our knowledge, our pro-posed scheme is complete for such systems in terms of meeting conflicting require-ments of various traffic and taking all standard specific detailed constraints. Besides,the conflicting requirements of different users in heterogeneous traffic networks, thescheme includes a constraint that allows the service provider to keep granular resourceutilization level in some prescribed range. The optimal solution of this problem iscomputationally intensive because of the slow subgradient search. Hence, from theguiding principle of this solution, we have proposed a suboptimal solution with rel-atively lower complexity. Besides showing the performance improvement achievedby our scheduling scheme comparing with other existing works, we have shown thatproposed scheme offers a reasonable tradeoff between ensuring fairness to end usersand ensuring effective resource utilization, a consideration of some importance to thenetwork operators. In the simulation, one of the assumptions is that one user holdsonly one type of traffic. However, our scheduling scheme is general enough to handlethe scenario when the users in the network host different types of traffic. Althoughmulti-cell interference is an important issue to consider in the scheduling solution, we157Chapter 7. Conclusion and Future Workhave ignored this issue while formulating our scheduling problem.Although it is apparent that resource allocation in the uplink system can beobtained in a distributed manner, the RBs in the network are global and belongedto the network. Hence, the solutions provided for all problems in this thesis arecentralized in nature. Even the game theoretical solution in Chapter 5 is not fullydistributed. Main advantage of a centralized solution is that, theoretically, optimalsolution can be found. However, centralized solution features high computation andcommunication overhead, lack of scalability and slow responsiveness. Actual cost ofthe centralized solution comes from the signaling network. The centralized entityrequires a reliable signaling network to gather the information of the entire network.In order to ensure reliable data transmission, the signaling network may need to useprotocols with high overhead, such as TCP/IP.7.2 Future WorkWe have listed a set of future works evolved from the outcome of the research workin this thesis.7.2.1 Self Configurable Uplink Scheduling and ResourceAllocation of DF Relayed SystemsOne of the assumptions of the problem in Chapter 2 is that the routing information ofthe entire network is pre-configured. That means, all users know whom to transmit,as well as the relays know which users are connected to them and whom to transmit.Under this setting, it may happen that the users are connected to the bad relays,whereas there are better relays to route. In such circumstances, the performance158Chapter 7. Conclusion and Future Workwould be better if the solution schemes would allow the users in selecting helperrelays on the fly. Hence, one of the future works is to design a self configurableuplink scheduling scheme of such systems.7.2.2 Joint Multi-Source and Multi-Relay Power Allocationfor AF Relayed NetworkIn Chapter 3, we have briefly described a joint source and relay power allocationproblem on the assumption that one single source is served by one relay. The solutionwe have given is to maximize the sum throughput of the system. Two more variantsof this problem can be1. Allocate power among the sources and relay in a way that maximizes the min-imum source SNR.2. Allocate power among the sources and relay in a way that minimizes the sumsource power.Furthermore, we can enhance our problem in such a way that instead of singlerelay, each source can be assisted by multiple relays. Under this network setup, wecan formulate the power allocation problem. Similar idea has been discussed in [47],however their problem formulation totally skipped the SNR due to the direct link.Incorporating that factor, we can reformulate the problem and come up with betterresults.159Chapter 7. Conclusion and Future Work7.2.3 Game Theoretical Solution of Joint Sources and RelayPower Allocation for AF Relayed Network underImperfect CSIOne of the assumptions of our work in Chapter 4 is that all entities in the networkobtain perfect CSI through the channel estimation and feedback method. However,in practice, this assumption is not realistic and the nodes in the network may notobtain correct CSI. One of the future directions related to this work is to investigatethe impact of imperfect CSI on the network due to the channel fluctuations andestimation errors. Bayesian game [138] is very appropriate to capture such conditionin the problem.7.2.4 Uplink Scheduling and Resource Allocation forMulti-Cell Heterogeneous Traffic NetworksOne of the drawbacks in the work of Chapter 5 is that the scheduling scheme has nottaken interference into account from the neighboring cells. However, this is practicalthat a cell has many neighboring cells which impose interference on the transmissionof the users especially at the edge of that cell. Furthermore, the standard of LTErecommends to have several congested small cells which impose interference on theusers of the macro cell. Therefore, one future work in this context is to design anuplink scheduler for heterogeneous traffic networks taking multi-cell interference intoaccount.160Bibliography[1] G. Intelligence, “Understanding 5G: Perspectives on future technologicaladvancements in mobile,” Dec 2014. [Online]. Available: www.gsmaintelligence.com[2] B. Hanta, “SC-FDMA and LTE Uplink Physical Layer Design,” in SeminarLTE: Der Mobilfunk der Zukunft, University of Erlangen-Nuremberg, LMK,2009.[3] T. S. 3GPP, “Group services and system aspects - policy and charging controlarchitecture,” p. 23, Nov 2009.[4] Ericsson, “Ericsson mobility report: On the pulse of the networked society,”June 2014. [Online]. Available: www.ericsson.com[5] H. Myung, J. Lim, and D. Goodman, “Single carrier FDMA for uplink wirelesstransmission,” IEEE Veh. Technol. Mag., vol. 1, no. 3, pp. 30–38, Sept 2006.[6] 3GPP, “Further advancements for E-UTRA, physical layer aspects,” vol. TR36.813 v0.1.1, p. 23, Nov 2008.[7] J. Huang, V. G. Subramanian, R. Agrawal, and R. Berry, “Joint schedulingand resource allocation in uplink ofdm systems for broadband wireless accessnetworks,” IEEE J.Sel. A. Commun., vol. 27, no. 2, pp. 226–234, 2009.[8] E. Yaacoub and Z. Dawy, “A game theoretical formulation for proportionalfairness in LTE uplink scheduling,” in Proc. IEEE WCNC, April 2009.[9] H. Myung, J. Lim, and D. Goodman, “Single carrier FDMA for uplink wirelesstransmission,” IEEE Veh. Technol. Mag., vol. 1, no. 3, pp. 30–38, Sept 2006.[10] H.-L. Chao, C.-K. Chang, and C.-L. Liu, “A novel channel-aware frequency-domain scheduling in LTE uplink,” in Proc. IEEE WCNC, 2013, pp. 917–922.[11] X. Wang and S. Konishi, “Optimization formulation of packet scheduling prob-lem in LTE uplink,” in Proc. IEEE VTC-Spring, 2010, pp. 1–5.[12] S. N. Marwat, T. Weerawardane, Y. Zaki, C. Goerg, and A. Timm-Giel, “Analysis of radio resource allocation in LTE uplink,” Wirel. Pers.161BibliographyCommun., vol. 79, no. 3, pp. 2305–2322, Dec. 2014. [Online]. Available:http://dx.doi.org/10.1007/s11277-014-1986-6[13] H.-L. Wang, S.-J. Kao, and F.-M. Chang, “An activity selection based singlecarrier-frequency division multiple access uplink scheduling for LTE networks,”in International Conference on Information Science, Electronics and ElectricalEngineering (ISEEE), vol. 3, April 2014, pp. 1493–1496.[14] S. W. Peters, A. Y. Panah, K. T. Truong, and R. W. Heath, “Relay architecturesfor 3GPP LTE-advanced,” EURASIP J. Wirel. Commun. Netw., vol. 2009, pp.1–14, 2009.[15] R. Pabst, B. H. Walke, D. C. Schultz, and et al., “Relay-based deploymentconcepts for wireless and mobile broadband radio,” IEEE Commun. Magazine,vol. 42, no. 9, pp. 80–89, September 2004.[16] L. Le and E. Hossain, “Multihop cellular networks: potential gains, researchchallenges, and a resource allocation framework,” IEEE Commun. Magazine,vol. 45, no. 9, pp. 66–73, September 2007.[17] L. Huang, M. Rong, L. Wang, Y. Xue, and E. Schulz, “Resource allocation forOFDMA based relay enhanced cellular networks,” in Proc. IEEE VTC-Spring,2007, pp. 3160–3164.[18] T. Girici, “Joint power, subcarrier and subframe allocation in multihop relaynetworks,” Int. J. Commun. Syst., vol. 22, no. 7, pp. 835–855, Jul. 2009.[Online]. Available: http://dx.doi.org/10.1002/dac.v22:7[19] T. Wang and L. Vandendorpe, “Sum rate maximized resource allocation inmultiple DF relays aided OFDM transmission,” IEEE J. Sel. A. Commun.,vol. 29, pp. 1559–1571, 2011.[20] T. Girici, C. Zhu, J. Agre, and A. Ephremides, “Optimal radio resource man-agement in multihop relay networks,” in Proc. WiOpT, 2008, pp. 443–451.[21] H. Li, H. Luo, X. Wang, C. Lin, and C. Li, “Fairness-aware resource allocationin OFDMA cooperative relaying network,” in Proc. IEEE ICC, ser. ICC’09.Piscataway, NJ, USA: IEEE Press, 2009, pp. 3750–3754. [Online]. Available:http://dl.acm.org/citation.cfm?id=1817770.1817971[22] L. Wang, Y. Ji, and F. Liu, “Joint optimization for proportional fairness inOFDMA relay-enhanced cellular networks,” in Proc. IEEE WCNC, 2010, pp.1–6.[23] W.-P. Chang, J.-S. Lin, and K.-T. Feng, “QoS-based resource allocation forrelay-enhanced OFDMA networks,” in Proc. IEEE WCNC, 2011, pp. 321–326.162Bibliography[24] M. Salem, A. Adinoyi, M. Rahman, H. Yanikomeroglu, D. Falconer, and Y.-D.Kim, “Fairness-aware radio resource management in downlink OFDMA cellularrelay networks,” IEEE Trans. Wirel. Commun., vol. 9, no. 5, pp. 1628–1639,2010.[25] ——, “Fair resource allocation toward ubiquitous coverage in OFDMA-basedcellular relay networks with asymmetric traffic,” IEEE Trans. VEH. TECH-NOL., vol. 60, no. 5, pp. 2280–2292, 2011.[26] D. Ng and R. Schober, “Resource allocation and scheduling in multi-cellOFDMA systems with decode-and-forward relaying,” IEEE Trans. Wirel. Com-mun., vol. 10, no. 7, pp. 2246–2258, 2011.[27] K. Sundaresan and S. Rangarajan, “Efficient algorithms for leveraging spatialreuse in OFDMA relay networks,” in Proc. IEEE INFOCOM, 2009, pp. 1539–1547.[28] ——, “Adaptive resource scheduling in wireless OFDMA relay networks,” inProc. IEEE INFOCOM, 2012, pp. 1539–1547.[29] J.-M. Liang, Y.-C. Wang, J.-J. Chen, J.-H. Liu, and Y.-C. Tseng,“Energy-efficient uplink resource allocation for IEEE 802.16j transparent-relaynetworks,” Comput. Netw., vol. 55, no. 16, pp. 3705–3720, Nov. 2011. [Online].Available: http://dx.doi.org/10.1016/j.comnet.2011.04.021[30] D. W. Kifle, O. Bulakci, A. B. Saleh, S. Redana, and F. Granelli, “Joint back-haul co-scheduling and relay cell extension in LTE-ADVANCED networks up-link performance evaluation,” in Proc. European Wireless, 2012, April 2012,pp. 1–8.[31] O. Bulakci, A. B. Saleh, S. Redana, B. Raaf, and J. Hamalainen, “Resourcesharing in LTE-Advanced relay networks: uplink system performance analysis.”EUR. Trans. Emerg. Telecommun. Technol., vol. 24, no. 1, pp. 32–48, 2013.[32] B.-G. Kim and J.-W. Lee, “Opportunistic resource scheduling for OFDMA net-works with network coding at relay stations,” IEEE Trans. Wirel. Commun.,vol. 11, no. 1, pp. 210–221, 2012.[33] B. Tang, B. Ye, S. Lu, and S. Guo, “Coding-aware proportional-fair schedulingin OFDMA relay networks,” IEEE Trans Paral. Distr. Sys., vol. 24, no. 9, pp.1727–1740, 2013.[34] X. S. Xiaoxia Zhang and L.-L. Xie, “Uplink achievable rate and power allocationin cooperative LTE-advanced networks,” IEEE Trans. Veh. Technol., pp. 1–12,2015.163Bibliography[35] C. Nam, C. Joo, and S. Bahk, “Joint subcarrier assignment and power allocationin full-duplex OFDMA networks,” IEEE Trans. Wirel. Commun., vol. 14, no. 6,pp. 3108–3119, June 2015.[36] B. R. Ho Young Hwang, Hyukjoon Lee and S. Kim, “Joint resource alloca-tion, routing and CAC for uplink OFDMA networks with cooperative relaying,”Wirel. Netw., pp. 1–11, Aug 2015.[37] X. Gong, S. Vorobyov, and C. Tellambura, “Joint bandwidth and power alloca-tion in wireless multi-user decode-and-forward relay networks,” in Proc. IEEEICASSP, March 2010, pp. 2498–2501.[38] L. Han, J. Mu, W. Wang, and B. Zhang, “Optimization of relay placement andpower allocation for decode-and-forward cooperative relaying over correlatedshadowed fading channels,” EURASIP J. Wirel. Comm. Netw, vol. 41, 2014.[39] X. Deng and A. Haimovich, “Power allocation for cooperative relaying in wire-less networks,” IEEE Commun. Lett., vol. 9, no. 11, pp. 994–996, 2005.[40] T. Quek, M. Win, H. Shin, and M. Chiani, “Optimal power allocation foramplify-and-forward relay networks via conic programming,” in Proc. IEEEICC, 2007, pp. 5058–5063.[41] Y. Zhao, R. Adve, and T. Lim, “Improving amplify-and-forward relay net-works: optimal power allocation versus selection,” IEEE Trans. Wirel. Com-mun., vol. 6, no. 8, pp. 3114 –3123, august 2007.[42] W. Su, A. K. Sadek, and K. J. Ray Liu, “Cooperative communication protocolsin wireless networks: Performance analysis and optimum power allocation,”Wirel. Pers. Commun., vol. 44, no. 2, pp. 181–217, Jan. 2008. [Online].Available: http://dx.doi.org/10.1007/s11277-007-9359-z[43] L. Li, Y. Jing, and H. Jafarkhani, “Multisource transmission for wireless relaynetworks with linear complexity,” IEEE Trans. Signal Process., vol. 59, no. 6,pp. 2898–2912, 2011.[44] ——, “Interference cancellation at the relay for multi-user wireless cooperativenetworks,” IEEE Trans. Wirel. Commun., vol. 10, no. 3, pp. 930–939, 2011.[45] S. Yao and M. Skoglund, “Analog network coding mappings in gaussianmultiple-access relay channels,” IEEE Trans. Commun., vol. 58, no. 7, pp.1973–1983, 2010.[46] K. Phan, T. Le-Ngoc, S. Vorobyov, and C. Tellambura, “Power allocation inwireless multi-user relay networks,” IEEE Trans. Wirel. Commun., vol. 8, no. 5,pp. 2535–2545, 2009.164Bibliography[47] W. H. Fang, M. J. Deng, and Y. T. Chen, “Joint source and relay power alloca-tion in amplify-and-forward relay networks: a unified geometric programmingframework,” IET Commun., vol. 5, no. 16, pp. 2301–2309, 2011.[48] Z. Zhang, H. Liu, and H. Zhang, “Cooperative communications with selfishbusy relay’s source selection: Whether to cooperate and whom to cooperatewith,” in Proc. IEEE WCNC, April 2014, pp. 2751–2756.[49] D. Wu, Y. Cai, and M. Guizani, “Auction-based relay power allocation: Paretooptimality, fairness, and convergence,” IEEE Trans. Commun., vol. 62, no. 7,pp. 2249–2259, July 2014.[50] H. Xiao and S. Ouyang, “Power control game in multisource multirelay coopera-tive communication systems with a quality-of-service constraint,” IEEE Trans.Intell. Trans. Sys., vol. 16, no. 1, pp. 41–50, Feb 2015.[51] R. Kwan and C. Leung, “A survey of scheduling and interference mitigationin LTE,” JECE, vol. 2010, pp. 1:1–1:10, Jan 2010. [Online]. Available:http://dx.doi.org/10.1155/2010/273486[52] F. Capozzi, G. Piro, L. Grieco, G. Boggia, and P. Camarda, “Downlink packetscheduling in LTE cellular networks: Key design issues and a survey,” IEEECommun. Surv. Tutor., vol. 15, no. 2, pp. 678–700, Second 2013.[53] H. Ramli, R. Basukala, K. Sandrasegaran, and R. Patachaianand, “Performanceof well known packet scheduling algorithms in the downlink 3GPP LTE system,”in Proc. IEEE MICC, 2009, pp. 815–820.[54] B. Sadiq, R. Madan, and A. Sampath, “Downlink scheduling for multiclasstraffic in LTE,” EURASIP J. Wirel. Commun. Netw., vol. 2009, pp. 14:9–14:9,Mar. 2009. [Online]. Available: http://dx.doi.org/10.1155/2009/510617[55] G. Monghal, K. Pedersen, I. Kovacs, and P. Mogensen, “QoS oriented time andfrequency domain packet schedulers for the UTRAN long term evolution,” inProc. IEEE VTC-Spring, 2008, pp. 2532–2536.[56] S. Saha and R. Quazi, “Priority-coupling-a semi-persistent MAC schedulingscheme for VOIP traffic on 3GPP LTE,” in Proc. IEEE ConTEL, 2009, pp.325–329.[57] M. Lerida, “Adaptive radio resource management for VOIP and data traffic in3GPP LTE networks,” in KTH Royal Institute of Technology, Stockholm, 2008.[58] M. Gidlund and J.-C. Laneri, “Scheduling algorithms for 3GPP long-term evo-lution systems: From a quality of service perspective,” in Proc. IEEE ISSSTA,2008, pp. 114–117.165Bibliography[59] Y. Zaki, T. Weerawardane, C. Gorg, and A. Timm-Giel, “Multi-QoS-aware fairscheduling for LTE,” in Proc. IEEE VTC-Spring, 2011, pp. 1–5.[60] K.-H. Liu, L. Cai, and X. Shen, “Multi-class utility-based scheduling for UWBnetworks,” IEEE Trans. Veh. Technol., 2008.[61] X. Wang, G. Giannakis, and A. Marques, “A unified approach to QoS-guaranteed scheduling for. channel-adaptive wireless network,” Proc. IEEE,vol. 95, pp. 2410–2431, 2007.[62] H. Safa, W. El-Hajj, and K. Tohme, “A QoS-aware uplink schedulingparadigm for LTE networks,” in Proc. IEEE AINA. Washington, DC,USA: IEEE Computer Society, 2013, pp. 1097–1104. [Online]. Available:http://dx.doi.org/10.1109/AINA.2013.38[63] S. Kwon and N.-H. Lee, “Uplink QoS scheduling for LTE system,” in Proc.IEEE VTC-Spring, 2011, pp. 1–5.[64] H. Ye, G. Lim, L. Cimini, and Z. Tan, “Energy-efficient resource allocation inuplink OFDMA systems under QoS constraints,” in Proc. IEEE MILCOM, Nov2013, pp. 424–428.[65] S. N. K. Marwat, Y. Zaki, C. GÃűrg, T. Weerawardane, and A. Timm-Giel, “Design and performance analysis of bandwidth and QoS aware LTE up-link scheduler in heterogeneous traffic environment.” in Proc. IEEE IWCMC.IEEE, 2012, pp. 499–504.[66] S. Cicalo and V. Tralli, “Fair resource allocation with QoS support for the uplinkof LTE systems,” in European Conference on Networks and Communications(EuCNC), June 2015, pp. 180–184.[67] R. Musabe and H. Larijani, “Cross-layer scheduling and resource allocation forheterogeneous traffic in 3G LTE,” J. Comp. Netw. Commun., pp. 1–13, Aug2014.[68] X. T. Samira Niafar and D. H. Tsang, “The optimal user scheduling for LTE-adownlink with heterogeneous traffic types,” in Proc. IEEE QSHINE, 2014, pp.1–7.[69] R. Kwak and J. Cioffi, “Resource-allocation for OFDMA multi-hop relayingdownlink systems,” in Proc. IEEE GLOBECOM, 2007, pp. 3225–3229.[70] M. Kaneko and P. Popovski, “Adaptive resource allocation in cellular OFDMAsystem with multiple relay stations,” in Proc. IEEE VTC-Spring, 2007, pp.3026–3030.166Bibliography[71] O. Oyman, “OFDM2A: A centralized resource allocation policy for cellularmulti-hop networks,” in Asilomar Conference on Signals, Systems and Com-puters, ACSSC, 2006, pp. 656–660.[72] C. Muller, A. Klein, F. Wegner, M. Kuipers, and B. Raaf, “Dynamic subcarrier,bit and power allocation in OFDMA-based relay networks,” in 12th Interna-tional OFDM Workshop, 2007, pp. 656–660.[73] L. You, M. Song, and J. Song, “Cross-layer optimization for fairness in OFDMAcellular networks with fixed relays,” in Proc. IEEE GLOBECOM, 2008, pp. 1–6.[74] L. Huang, M. Rong, L. Wang, Y. Xue, and E. Schulz, “Resource scheduling forOFDMA/TDD based relay enhanced cellular networks,” in Proc. IEEE WCNC,2007, pp. 1544–1548.[75] M. Shaqfeh and H. Alnuweiri, “Joint power and resource allocation for block-fading relay-assisted broadcast channels,” IEEE Trans. Wirel. Commun.,vol. 10, no. 6, pp. 1904–1913, 2011.[76] V. Venkatasubramanian and T. Haustein, “A novel scheduling frameworkfor QoS-aware OFDMA resource allocation in a network with small relaycells and macro users.” EURASIP J. Wirel. Commun. Netw., vol. 2012, p.309, 2012. [Online]. Available: http://dblp.uni-trier.de/db/journals/ejwcn/ejwcn2012.html[77] K. Sundaresan and S. Rangarajan, “On exploiting diversity and spatial reusein relay-enabled wireless networks,” in Proc. ACM MobiHoc, ser. MobiHoc’08. New York, NY, USA: ACM, 2008, pp. 13–22. [Online]. Available:http://doi.acm.org/10.1145/1374618.1374622[78] K.-D. Lee and V. C. Leung, “Fair allocation of subcarrier and powerin an OFDMA wireless mesh network,” IEEE J. Sel. A. Commun.,vol. 24, no. 11, pp. 2051–2060, Nov. 2006. [Online]. Available: http://dx.doi.org/10.1109/JSAC.2006.881628[79] L. You, P. Wu, M. Song, J. Song, and Y. Zhang, “Cross-layer optimisationfor uplink transmission in OFDMA cellular networks with fixed relays.” Europ.Trans. Telecommun., vol. 22, no. 6, pp. 296–314, 2011.[80] F. Carmichael, “A guide to game theory,” Dec 2004.[81] J. Huang, V. Subramanian, R. Agrawal, and R. Berry, “Downlink schedulingand resource allocation for OFDM systems,” IEEE Trans. Wirel. Commun.,vol. 8, no. 1, pp. 288 –296, jan. 2009.167Bibliography[82] X. Qiu and K. Chawla, “On the performance of adaptive modulation in cellularsystems,” IEEE Trans. on Commun., vol. 47, no. 6, pp. 884–895, 1999.[83] R. Jain, D. Chiu, and W. Hawe, “A quantitative measure of fairness and dis-crimination for resource allocation in shared systems,” DEC Research ReportTR-301, 1984.[84] J. Laneman and G. Wornell, “Distributed space-time-coded protocols for ex-ploiting cooperative diversity in wireless networks,” IEEE Trans. Inform. The.,vol. 49, no. 10, pp. 2415 – 2425, oct. 2003.[85] T. Wang and G. Giannakis, “Complex field network coding for multiuser co-operative communications,” IEEE J. Sel. A. in Commun., vol. 26, no. 3, pp.561–571, 2008.[86] G. Sidhu and F. Gao, “Resource allocation for relay aided uplink multiuserOFDMA system,” in Proc. IEEE WCNC, 2010, pp. 1–5.[87] Y. Jing and H. Jafarkhani, “Single and multiple relay selection schemes andtheir achievable diversity orders,” IEEE Trans. Wirel. Commun., vol. 8, no. 3,pp. 1414–1423, 2009.[88] G. Amarasuriya, M. Ardakani, and C. Tellambura, “Adaptive multiple relayselection scheme for cooperative wireless networks,” in Proc. IEEE WCNC,2010, pp. 1–6.[89] H.-S. Chen, W.-H. Fang, and Y.-T. Chen, “Relaying through distributed gabbaspace-time coded amplify-and-forward cooperative networks with two-stagepower allocation,” in Proc. IEEE VTC-Spring, 2010, pp. 1–5.[90] M. Ju and I.-M. Kim, “Joint relay selection and opportunistic source selectionin bidirectional cooperative diversity networks,” IEEE Trans. Veh. Technol.,vol. 59, no. 6, pp. 2885–2897, 2010.[91] M. Chiang, “Geometric programming for communication systems,” Commun.Inf. The., vol. 2, no. 1/2, pp. 1–154, Jul. 2005. [Online]. Available:http://dx.doi.org/10.1516/0100000005[92] S. Boyd, S.-J. Kim, L. Vandenberghe, and A. Hassibi, “A tutorial on geometricprogramming,” Optimization and Engineering, vol. 8, no. 1, pp. 67–127, 2007.[93] S. Borst, “User-level performance of channel-aware scheduling algorithms inwireless data networks,” IEEE/ACM Trans. Netw., vol. 13, pp. 636–647, June2005.168Bibliography[94] W. Saad, Z. Han, M. Debbah, and A. Hjørungnes, “A distributed coalitionformation framework for fair user cooperation in wireless networks,” IEEETrans. Wirel. Commun., vol. 8, no. 9, pp. 4580–4593, Sep. 2009. [Online].Available: http://dx.doi.org/10.1109/TWC.2009.080522[95] Z. Zhang, J. Shi, H.-H. Chen, M. Guizani, and P. Qiu, “A cooperation strategybased on nash bargaining solution in cooperative relay networks,” IEEE Trans.Veh. Technol., vol. 57, no. 4, pp. 2570–2577, 2008.[96] G. Zhang, H. Zhang, L. Zhao, W. Wang, and L. Cong, “Fair resource sharing forcooperative relay networks using nash bargaining solutions,” IEEE Commun.Lett., vol. 13, no. 6, pp. 381–383, 2009.[97] L. Chen, L. Libman, and J. Leneutre, “Conflicts and incentives in wirelesscooperative relaying: A distributed market pricing framework,” IEEE Trans.P. Dist. Sys., vol. 22, no. 5, pp. 758–772, 2011.[98] X. Fafoutis and V. Siris, “Performance incentives for cooperation between wire-less mesh network operators,” in Proc. IEEE INFOCOM Workshops, 2010, pp.1–6.[99] Y. Shen, G. Feng, B. Yang, and X. Guan, “Fair resource allocation and admis-sion control in wireless multiuser amplify-and-forward relay networks,” IEEETrans. Veh. Technol., vol. 61, no. 3, pp. 1383–1397, 2012.[100] B. Wang, Z. Han, and K. J. R. Liu, “Distributed relay selection and powercontrol for multiuser cooperative communication networks using stackelberggame,” IEEE Trans. Mob. Comp., vol. 8, no. 7, pp. 975–990, 2009.[101] S. Ren and M. Van Der Schaar, “Pricing and distributed power control in wire-less relay networks,” IEEE Trans. Signal Process., vol. 59, no. 6, pp. 2913–2926,2011.[102] Q. Cao, H. V. Zhao, and Y. Jing, “Power allocation and pricing in multi-user relay networks using stackelberg and bargaining games,” CoRR, vol.abs/1201.3056, 2012.[103] Q. Cao, Y. Jing, and H. Zhao, “Power allocation in multi-user wireless relaynetworks through bargaining,” IEEE Trans. Wirel. Commun., vol. 12, no. 6,pp. 2870–2882, 2013.[104] R. Yates, “A framework for uplink power control in cellular radio systems,”IEEE J. Sel. A. Commun., vol. 13, no. 7, pp. 1341–1347, 1995.169Bibliography[105] S. Sun and Y. Jing, “Channel training design in amplify-and-forward mimorelay networks,” IEEE Trans. Wirel. Commun., vol. 10, no. 10, pp. 3380–3391,October 2011.[106] ——, “Training and decoding for cooperative network with multiple relays andreceive antennas,” IEEE Trans. Commun., vol. 60, no. 6, pp. 1534–1544, June2012.[107] F. P. Kelly, A. K. Maulloo, , and D. Tan, “Rate control for communicationnetworks: shadow prices, proportional fairness and stability,” Journal of theOperational Research Society, vol. 49, pp. 237–252, 1998.[108] R. Madan, S. Boyd, and S. Lall, “Fast algorithms for resource allocation inwireless cellular networks,” IEEE/ACM Trans. Netw., vol. 18, no. 3, pp. 973–984, 2010.[109] P. Kela, J. Puttonen, N. Kolehmainen, T. Ristaniemi, T. Henttonen, andM. Moisio, “Dynamic packet scheduling performance in utra long term evo-lution downlink,” in Proc. IEEE ISWPC, 2008, pp. 308–313.[110] D. Tse and P. Viswanath, “Fundamentals of wireless communication,” in Cam-bridge University Press; Edition 1, 2005.[111] J. Huang, V. Subramanian, R. Agrawal, and R. Berry, “Downlink schedulingand resource allocation for OFDM systems,” IEEE Trans. Wirel. Commun.,vol. 8, no. 1, pp. 288–296, 2009.[112] R. Kwan, C. Leung, and J. Zhang, “Proportional fair multiuser scheduling inLTE,” IEEE Signal Process. Lett., vol. 16, no. 6, pp. 461–464, 2009.[113] F. Calabrese, C. Rosa, K. Pedersen, and P. Mogensen, “Performance of propor-tional fair frequency and time domain scheduling in LTE uplink,” in EuropeanWireless Conference (EW), 2009, pp. 271–275.[114] N. Chen and S. Jordan, “Throughput in processor-sharing queues,” IEEE Trans.Aut. Contr., vol. 52, no. 2, pp. 299–305, 2007.[115] ——, “Downlink scheduling with probabilistic guarantees on short-term averagethroughputs,” in Proc. IEEE WCNC, 2008, pp. 1865–1870.[116] D. Skoutas and A. Rouskas, “Scheduling with QoS provisioning in mobile broad-band wireless systems,” in European Wireless Conference (EW), 2010, pp. 422–428.[117] M. Andrews, “CDMA data QoS scheduling on the forward link with variablechannel conditions,” Bell Laboratories, Apr 2000.170Bibliography[118] G. Song and G. Li, “Cross-layer optimization for OFDM wireless networks parti: Theoretical framework,” IEEE Trans. Wirel. Commun., vol. 4, no. 2, March2005.[119] V. J. Venkataramanan and X. Lin, “On wireless scheduling algorithms for mini-mizing the queue-overflow probability,” IEEE/ACM Trans. Netw., vol. 18, no. 3,pp. 788–801, 2010.[120] A. L. Stolyar, “Large deviations of queues sharing a randomly time-varyingserver,” Queueing Syst. The. Appl., vol. 59, no. 1, pp. 1–35, May 2008.[Online]. Available: http://dx.doi.org/10.1007/s11134-008-9072-y[121] B. Sadiq and G. de Veciana, “Large deviation sum-queue optimality of a radialsum-rate monotone opportunistic scheduler,” CoRR, vol. abs/0906.4597, 2009.[122] R. Basukala, H. Mohd Ramli, and K. Sandrasegaran, “Performance analysisof EXP/PF and M-LWDF in downlink 3GPP LTE system,” in First AsianHimalayas International Conference on Internet, 2009, pp. 1–5.[123] G. Piro, L. Grieco, G. Boggia, R. Fortuna, and P. Camarda, “Two-level downlinkscheduling for real-time multimedia services in LTE networks,” IEEE Trans.Multim., vol. 13, no. 5, pp. 1052–1065, 2011.[124] W. K. Lai and C.-L. Tang, “QoS-aware downlink packet schedulingfor LTE networks,” Comp. Netw., no. 0, 2013. [Online]. Available:http://www.sciencedirect.com/science/article/pii/S1389128613000352[125] M. Iturralde, A. Wei, T. Ali Yahiya, and A. L. Beylot, “Resource allocation forreal time services using cooperative game theory and a virtual token mechanismin LTE networks,” in Proc. IEEE CCNC, 2012, pp. 879–883.[126] M. Wemersson, S. Wanstedt, and P. Synnergren, “Effects of QoS schedulingstrategies on performance of mixed services over LTE,” in Proc. IEEE PIMRC,2007, pp. 1–5.[127] H. Lei, M. Yu, A. Zhao, Y. Chang, and D. Yang, “Adaptive connection admis-sion control algorithm for LTE systems,” in Proc. IEEE VTC-Spring, 2008, pp.2336–2340.[128] I. Wong, O. Oteri, and W. Mccoy, “Optimal resource allocation in uplink SC-FDMA systems,” IEEE Trans. Wirel. Commun., vol. 8, no. 5, pp. 2161–2165,2009.[129] F. Liu, X. She, L. Chen, and H. Otsuka, “Improved recursive maximum expan-sion scheduling algorithms for uplink single carrier FDMA system,” in Proc.IEEE VTC-Spring, 2010, pp. 1–5.171Bibliography[130] B. Al-Manthari, H. Hassanein, N. A. Ali, and N. Nasser, “Fair class-baseddownlink scheduling with revenue considerations in next generation broadbandwireless access systems,” IEEE Trans. Mob. Comp., vol. 8, pp. 721–734, 2009.[131] D. P. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Scientific,2003.[132] L. Huawi Technologies Co., “eRAN scheduling feature parameter description,”2013. [Online]. Available: http://www.huawei.com[133] M. Mojtahed and S. Xirasagar, “Quality of service over LTE networks,” 2013.[Online]. Available: www.lsi.com[134] V. Garg, “Wireless communication & networking,” June 2007.[135] K. YONG-SEOK, “Capacity of VoIP over HSDPA with frame bundling,” IEICETrans. Commun., vol. E89-B, pp. 3450–3453, 2006.[136] J. Puttonen, T. Henttonen, N. Kolehmainen, K. Aschan, M. Moisio, andP. Kela, “Voice-over-ip performance in utra long term evolution downlink,” inProc. IEEE VTC-Spring, 2008, pp. 2502–2506.[137] J. Blumenstein, J. C. Ikuno, J. Prokopec, and M. Rupp, “Simulating the longterm evolution uplink physical layer,” in 53rd International Symposium EL-MAR, Zadar, Croatia, September 2011.[138] D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA: The MIT Press,1991.172Appendix AProof of the Properties for I(p)• Positivity: I(p) > 0. By Property 5.2, ∂E∗si(pi)∂pi< 0. Moreover, because ofpracticality, ci > 0, and according to Lemma 5.1, E∗si(pi) ≥ 0. And, followingthe definition in Equation 5.16, Ii(pi) ≥ ci > 0. Therefore, in this price updateprocess, source si, ∀si∈L1s starts increasing its price from ci.• Scalability: ∀α > 1, αI(p) > I(αp). Subtracting I(αp) from αI(p) for sourcesi, we haveαIi(pi)− Ii(αpi) = (α− 1)ci (A.1)+[E∗si(pi)∂E∗si(αpi)/∂pi− αE∗si(pi)∂E∗si(pi)/∂pi].Since α > 1, (α−1)ci > 0. Then, the problem reduces to proving E∗si(αpi)∂E∗si (αpi)/∂pi>αE∗si (pi)∂E∗si (pi)/∂pi. Now,E∗si (αpi)∂E∗si (αpi)/∂pi= −2pi + 2ciα +2σ√Bsiα√aE′riGsi,rGr,d(αpi − aGsi,dσ2)3/2, (A.2)173Appendix A. Proof of the Properties for I(p)αE∗si (pi)∂E∗si (pi)/∂pi= −2αpi + 2αci + 2ασ√Bsi√aE′riGsi,rGr,d(pi − aGsi,dσ2)3/2. (A.3)For the second part of Equation A.1 being> 0, pi should satisfy pi >aGsi,dσ2(α−1/α)α−1 ,and pi >aGsi,dσ21/α− 3√α1− 3√α . Or, in other way, pi > xaGsi,dσ2, where x∈R. However, xgrows slowly with the increasing value of α. Since ci >aGsi,dσ2, and pi > ci forCase 1, the price update function of source si satisfies this property.• Monotonicity: If p ≥ p′, then I(p) ≥ I(p′). To satisfy this property, it issufficient to prove ∂I(p)∂p≥ 0. Hence, for source si, we have∂Ii(pi)∂pi= 2[1− 3σ√Bsi2√aE ′riGsi,rGr,d√pi − aGsi,dσ2]. (A.4)For ∂Ii(pi)∂pibeing ≥ 0, pi should be ≤ aGsi,dσ2 +4aE′riGsi,rGr,d9σ2Bsi. It is apparent thatupper bound of pi for the monotonicity property is close to pubi in Case 1 ofLemma 5.1.174Appendix BProof of the Properties for I(λ)• Positivity: I(λ) ≥ 0. By Property 5.5, ∂Eri (λ)∂λ< 0, ∀si∈L1s. Furthermore,setting the cost c as λlb, c > 0. In Equation 5.20, we observe Eri(λ) ≥ 0, ∀si∈L1s.And, according to Equation 5.27, I(λ) ≥ c > 0. Therefore, in this price updateprocess, Network increases price from c.• Monotonicity: if λ ≥ λ′, I(λ) ≥ I(λ′). To satisfy this property, it is enough toprove ∂I(λ)∂λ≥ 0. So,I(λ) = c+ 2λ−∑si∈L1s Bri∑si∈L1s√ηBriE∗siGsi,rGr,dσ2λ3/2 , (B.1)∂I(λ)∂λ= 21− 3∑si∈L1s Bri2∑si∈L1s√ηBriE∗siGsi,rGr,dσ2λ1/2 . (B.2)For ∂I(λ)∂λ≥ 0, it must satisfy that λ ≤ 49σ2(∑si∈L1s√ηBriE∗siGsi,rGr,d∑si∈L1sBri)2, the righthand side of which is close to λub of Lemma 5.2.• Scalability: For all α ≥ 1, αI(λ) ≥ I(αλ). We haveαI(λ) = αc+ 2αλ− 2α∑si∈L1s Bri∑si∈L1s√ηBriE∗siGsi,rGr,dσ2λ3/2, (B.3)175Appendix B. Proof of the Properties for I(λ)I(αλ) = c+ 2αλ− 2∑si∈L1s Bri∑si∈L1s√ηBriE∗siGsi,rGr,dσ2αλ3/2. (B.4)Since α > 1, and c is positive, (α − 1)c is always > 0. Furthermore, for thesecond part of αI(λ) − I(αλ) being positive, it must satisfy that α3/2 ≥ α,which is true for all α ≥ 1176Appendix CAdditional Research WorkSome research works that are not directly related to this dissertation but have beenpublished during my time as a PhD student at UBC are as follows.• Li Zhou, Chunsheng Zhu, Rukhsana Ruby, Xiaofei Wang, Xioating Ji and JiboWei, "QoS-Aware Energy-Efficient Resource Allocation in HetNets," acceptedfor International Journal of Communication Systems, 2014, p. 1–19.• Xuan Dong, Shaohe Lv, Rukhsana Ruby, Yong Lu, Xiaodong Wang, XingMingZhou and Victor C.M. Leung, "Virtual Frame Aggregation: Cluster ContentionBased Channel Access in Multicarrier Wireless Networks," IEEE ICC, 2015, p.1–7.• Li Zhou, Rukhsana Ruby, Haitao Zhao, Xiaoting Ji, Jibo Wei and Victor C.M.Leung, "A Graph-based Resource Allocation Scheme with Interference Coordi-nation in Small Cell Networks," IEEE GLOBECOM Workshops, 2014, p. 1–6.• Rukhsana Ruby, Saad Mahboob and David G. Michelson, "Optimal Configura-tion of Distributed MIMOAntennas in Underground Tunnels," IEEE APS/URSI,2014: 65–66.• Saad Mahboob, Rukhsana Ruby, and Victor C.M. Leung, "Transmit AntennaSelection in a Very-Large MIMO System using Convex Optimization," IEEEBWCCA, 2012: 228–233.177Appendix C. Additional Research Work• Rukhsana Ruby, Victor C.M. Leung and John Sydor, "Optimal TransmissionStrategy for a Secondary User in IEEE 802.11 Based Networks," IEEE PIMRC,2012: 1243–1248.• Rukhsana Ruby, Salim Hanna, John Sydor and Victor C.M. Leung, "Inter-ference Sensing using CORAL Cognitive Radio Platforms," Chinacom, 2011:949–954.• Rukhsana Ruby, and Victor C.M. Leung, "Performance Analysis of a Hetero-geneous Traffic Scheduler using Large Deviation Principle," to be submitted toComputer Communications, 2015.178