WWeesstteerrnn UUnniivveerrssiittyy SScchhoollaarrsshhiipp@@WWeesstteerrnn Electronic Thesis and Dissertation Repository 11-27-2015 12:00 AM EEffifficciieenntt SScchheedduulliinngg AAllggoorriitthhmmss ffoorr WWiirreelleessss RReessoouurrccee AAllllooccaattiioonn aanndd VViirrttuuaalliizzaattiioonn iinn WWiirreelleessss NNeettwwoorrkkss Mohamad Kalil, The University of Western Ontario Supervisor: Abdallah Shami, The University of Western Ontario A thesis submitted in partial fulfillment of the requirements for the Doctor of Philosophy degree in Electrical and Computer Engineering © Mohamad Kalil 2015 Follow this and additional works at: https://ir.lib.uwo.ca/etd Part of the Digital Communications and Networking Commons RReeccoommmmeennddeedd CCiittaattiioonn Kalil, Mohamad, "Efficient Scheduling Algorithms for Wireless Resource Allocation and Virtualization in Wireless Networks" (2015). Electronic Thesis and Dissertation Repository. 3445. https://ir.lib.uwo.ca/etd/3445 This Dissertation/Thesis is brought to you for free and open access by Scholarship@Western. It has been accepted for inclusion in Electronic Thesis and Dissertation Repository by an authorized administrator of Scholarship@Western. For more information, please contact [email protected]. Efficient Scheduling Algorithms for Wireless Resource Allocation and Virtualization in Wireless Networks (Thesisformat:Monograph) by Mohamad Kalil GraduateProgram in ElectricalandComputerEngineering Athesissubmittedinpartialfulfillment oftherequirementsforthedegreeof DoctorofPhilosophy SchoolofGraduateandPostdoctoralStudies TheUniversityofWesternOntario London,Ontario,Canada (cid:13)c MohamadKalil2015 Abstract The continuing growth in demand for better mobile broadband experiences has motivated rapid development of radio-access technologies to support high data rates and improve quality of service (QoS) and quality of experience (QoE) for mobile users. However, the modern radio-access technologies pose new challenges to mobile network operators (MNO) and wireless device designers such as reducing the total cost of ownership while supporting high data throughput per user, and extending battery life-per-charge of the mo- biledevices. Inthisthesis,avarietyofoptimizationtechniquesaimedatprovidinginnova- tivesolutionsforsuchchallengesareexplored. The thesis is divided into two parts. In the first part, the challenge of extending battery life-per-charge is addressed. Optimal and suboptimal power-efficient schedulers that minimize the total transmit power and meet the QoS requirements of the users are presented. The second outlines the benefits and challenges of deploying wireless resource virtualization (WRV) concept as a promising solution for satisfying the growing demand for mobile data and reducing capital and operational costs. First, a WRV framework is proposed for single cell zone that is able to centralize and share the spectrum resources between multiple MNOs. Consequently, several WRV frameworks are proposed, which virtualize the spectrum resource of the entire network for cloud radio access network (C- RAN)-oneofthefrontrunnersforthenextgenerationnetworkarchitecture. The main contributions of this thesis are in designing optimal and suboptimal solu- tions for the aforementioned challenges. In most cases, the optimal solutions suffer from highcomplexity,andthereforelow-complexitysuboptimalsolutionsareprovidedforprac- tical systems. The optimal solutions are used as benchmarks for evaluating the suboptimal solutions. Theresultsprovethattheproposedsolutionseffectivelycontributeinaddressing the challenges caused by the demand for high data rates and power transmission in mobile networks. Keywords: Power Minimization, QoS, LTE, Packet Scheduling, Uplink, Virtualiza- tion,C-RAN,ResourceSharing ii Acknowledgements I would like to express my sincere gratitude to my supervisor, Prof. Abdallah Shami, for the immeasurable amount of support, guidance, and personal and professional advices he hasprovidedmewhilepursuingthisdegree. Icouldnotimaginehavingabettersupervisor for my PhD study. I appreciate all his contributions of time, ideas and support to make my PhD experience productive, successful and enjoyable. Thank you for motivating me along the way and for being the go-to person whenever I faced problems or felt down. I knew I couldalwaysturntohimwhenmydepletedmotivationneededrecharging. My sincere gratitude goes to my co-supervisor Dr. Arafat Al-Dweik for his continuous help and support in all stages of my PhD study. Without his involvement, this work will not have been possible. His encouragement, kindness, brilliant comments and insightful suggestions,andhispromptresponsestomyquestionswillalwaysberemembered. I would like to thank my examiners: Dr. Serguei Primak, Dr. Lian Zhao, Dr. Aleksander Essex,andDr. MichaelBauerfortakingthetimetoreviewandexaminemythesis,andfor theirinsightfulcommentsandsuggestions. I would also like to thank my Master’s thesis supervisor, Dr. Mohammad Banat, for help- ing me to begin my research journey. I would like to thank Dr. Ibrahim M. Ghareeb and Dr. Redha Radaydeh, who taught me the first courses in wireless communication and in- troducedmetothearea. Special thanks go to my colleagues and friends at Western university who made my PhD yearsajoyfulandmemorableexperience. Formost,aBIGthankstoMohamedAbuSharkh who experienced all of the ups and downs of my research, and to Fuad Shamieh who was always there for me and ready to help. Also, I would like to extend my thanks to my friends: Oscar Filio, Karim Hammad,Aidin Reyhani, Dan Wallace, ,Manar Jammal, Has- san Hawilo, Bradley de Vlugt, Elena Uchiteleva, Abdallah Moubayed, Khaled Alhazmi, EmadAqeeli,MohamedHussein,MaysamMirahmadi,KhalimMeerja,SiamackGhadimi, M.AjmalKhan,EricSouthern,PengHao,MohamedYoussef,AbdulfattahNoorwali,Mo- hammad Noor Injadat, Fadi Salo, Anas Saci, Marco Luccini, Anas Ibrahim, Jay Nadeau, andKevinMi. To my friends scattered around the world, thank you for your well-wishes, phone calls, e-mails, and being there whenever I needed a friend. For most, I would like to thank Yazan Al-Badarneh, Khair Al Shamaileh, Majdi Ababneh, Alaeddin Bani Milhim, Ali iii Acknowledgements Bani Amer, Yousef Mashaala, Bashar Alwadyan, Malek Khudirat, Qutaiba Al-Hazaime, MohamadAbuHani,HasanThiabat,andAhmadAl-Sharoa. AwarmthanksgoestoMadeleineandCarl,whomIlivedwithforalmost3years,forbeing warm,kind,andasecondfamilyforme. And most importantly, I am deeply and forever indebted to my family. You are the great- est source of love, encouragement, and inspiration. In particular, this project is dedicated to them with my sincerest thanks and appreciation to my father, God bless his soul, who passedawaylastmay,andtomymotherfortheirlove,supportandencouragementthrough- out my entire life, and for all of the sacrifices they have made on my behalf. Without them Iwouldhavebeentotallylostandnevertookastepahead. My sincere gratitude goes to my sisters Maysa, Mayada, Maram, and Marwa, and my brothers, Motaz and Mones, as well as to my grandmothers, grandfathers, father-in-law, mother-in-law, brothers-in-law, sister-in-law, aunts, uncles, and cousins for their love and support,andforbeingproudofme. Last but not least, a heartfelt thanks to my wife Tasneem for her continued support, love, and for being my best friend and great companion who helped me get through the unex- pected troubles of research in the most positive way. Words cannot describe how lucky I amtohaveyouinmylife. iv Tothememoryofmyfather,andtomymotherandmylovingwifeTasneem v Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v TableofContents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi ListofTables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix ListofFigures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 ThesisOutlineandContributions . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 ContributionsoftheThesis . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 ContributionsofChapter2 . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 ContributionsofChapter3 . . . . . . . . . . . . . . . . . . . . . . 3 1.2.3 ContributionsofChapter4 . . . . . . . . . . . . . . . . . . . . . . 4 1.2.4 ContributionsofChapter5 . . . . . . . . . . . . . . . . . . . . . . 4 2 QoS-AwarePower-EfficientSchedulerforLTEUplink . . . . . . . . . . . . . 6 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 SystemModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3.1 LTEQoSandBufferStatusReports(BSRs) . . . . . . . . . . . . . 13 2.3.2 UplinkDataTransmissionProcedure . . . . . . . . . . . . . . . . 15 2.3.3 DelayAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 SystemConstraintsandObjective . . . . . . . . . . . . . . . . . . . . . . 18 2.5 BIPFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5.1 BinaryIntegerProgramming . . . . . . . . . . . . . . . . . . . . . 24 2.5.2 ComplexityofBIP . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.6 IterativeAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.6.1 ComplexityoftheIterativeAlgorithm . . . . . . . . . . . . . . . . 27 2.7 ProportionalFairScheduler . . . . . . . . . . . . . . . . . . . . . . . . . . 29 vi TableofContents 2.8 Intra-UserScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.9 NumericalResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.9.1 Experiment1: TwoUserswithIdenticalConditions . . . . . . . . . 32 2.9.2 Experiment 2: Two Users with Identical Conditions but Different ACG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.9.3 Experiment3: TheIterativeAlgorithmEvaluation . . . . . . . . . 34 2.10 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3 Low-ComplexityPower-EfficientSchedulersforLTEUplinkwithDelay-Sensitive Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2 SystemModelDescriptionandAssumptions . . . . . . . . . . . . . . . . . 44 3.3 AllocationConstraintsandProblemDefinition . . . . . . . . . . . . . . . . 50 3.3.1 DelayConstraint . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.2 SystemConstraints . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3.3 ProblemDefinition . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.4 OptimalOfflineScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.5 Sub-OptimalPower-EfficientSchedulers . . . . . . . . . . . . . . . . . . . 59 3.5.1 MaximumTransmitPowerControlling(MTPC)Scheduler . . . . . 60 3.5.2 BitperWattControlling(BWC)Scheduler . . . . . . . . . . . . . 63 3.5.3 ComplexityoftheHeuristicAlgorithms . . . . . . . . . . . . . . . 64 3.5.4 TheControllers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.6 SimulationResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.6.1 Large-ScaleScenario . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.7 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4 WirelessResourceVirtualization: Opportunities,Challenges,andSolutions . 76 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.2 MainBenefitsofWRV . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2.1 EconomicSharingofInvestmentandCostReduction . . . . . . . . 78 4.2.2 CollaborativeBusinessModels . . . . . . . . . . . . . . . . . . . . 79 4.2.3 EnvironmentalBenefits . . . . . . . . . . . . . . . . . . . . . . . . 79 4.3 OperationalandBusinessChallengesofWRVDeployment . . . . . . . . . 80 4.3.1 TheRiskofMarketShareLossandAnti-CompetitivePractices . . 80 4.3.2 IndependenceofServiceswithRAN-Sharing . . . . . . . . . . . . 80 4.4 ScopeofVirtualizationandDepthofSharing . . . . . . . . . . . . . . . . 80 4.4.1 PassiveSharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.4.2 ActiveSharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.5 EfficientFairLow-ComplexitySchedulerforWRV . . . . . . . . . . . . . 85 4.5.1 SystemandChannelmodels . . . . . . . . . . . . . . . . . . . . . 86 4.5.2 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.5.3 ComputingtheOptimalWeightsforMNOs . . . . . . . . . . . . . 90 vii TableofContents 4.5.4 NumericalResults . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.6 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5 WirelessResourcesVirtualizationforCloudRadioAccessNetworks(C-RAN) 96 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.2 Relatedwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.3 SystemandSharingModels . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.3.1 ResourceBlocksSharingModel . . . . . . . . . . . . . . . . . . . 103 5.4 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.4.1 SpecialCase: BackloggedTrafficModel . . . . . . . . . . . . . . 106 5.4.2 RadioResourceSchedulingPolices . . . . . . . . . . . . . . . . . 107 5.4.3 ComplexityofOptimalSolution . . . . . . . . . . . . . . . . . . . 107 5.5 Low-ComplexitySolutions . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.5.1 TheComplexityoftheHeuristicAlgorithm . . . . . . . . . . . . . 113 5.6 SimulationModelandNumericalResults . . . . . . . . . . . . . . . . . . 113 5.6.1 Scenario1: BackloggedTrafficModel . . . . . . . . . . . . . . . . 114 5.6.2 Scenario2: DynamicTrafficModel . . . . . . . . . . . . . . . . . 117 5.7 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.1 ThesisSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.2 FutureWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 6.2.1 Power-EfficientSchedulersforLTE-AUplink . . . . . . . . . . . . 124 6.2.2 VirtualizationinNextGenerationRadioAccessNetwork . . . . . . 125 6.2.3 SpectrumandComputingResourcesVirtualizationinC-RAN . . . 126 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 CurriculumVitae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 viii List of Tables 2.1 Summaryofthemostsignificantnotationusedinthischapter. . . . . . . . 10 2.2 ListofMCSindices[1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Iterativeallocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Intra-userschedulingforuserk . . . . . . . . . . . . . . . . . . . . . . . . 30 2.5 Simulationdefaultparameters . . . . . . . . . . . . . . . . . . . . . . . . 31 2.6 Users’dataprofile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1 Summaryofthemostsignificantnotationusedinthischapter. . . . . . . . 45 3.2 MTPCscheduler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.3 BWCscheduler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.4 MATPcontroller. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.5 BPWRcontroller. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.6 ParametersettingsoftheuplinkLTEmodel. . . . . . . . . . . . . . . . . . 67 3.7 Parametersettingsofthelarge-scalescenario. . . . . . . . . . . . . . . . . 71 4.1 Summaryofthemostsignificantnotation. . . . . . . . . . . . . . . . . . . 85 4.2 IterativesearchmethodtofindMNOs’weights . . . . . . . . . . . . . . . 91 4.3 Numberofiterationstoconverge . . . . . . . . . . . . . . . . . . . . . . . 93 5.1 Summaryofthemostsignificantnotation. . . . . . . . . . . . . . . . . . . 102 5.2 Examplesofdifferentschedulers[2] . . . . . . . . . . . . . . . . . . . . . 108 5.3 PerRBoptimalallocationalgorithm . . . . . . . . . . . . . . . . . . . . . 111 5.4 Heuristicalgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.5 Normalized average running time of the BIP, heuristic, heuristic-RRH and staticsharingsolutions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 ix