Cognitive Spectrum Access, Multimedia Content Delivery, and Full-duplexRelaying in Wireless NetworksbyBojiang MaM.A.Sc., University of Victoria, Canada, 2011B.E., Southeast University, China, 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)December 2016c© Bojiang Ma, 2016AbstractDue to the growing number of wireless communication devices and emerging bandwidth-intensive applications, the demand of data usage is increasing rapidly. Utilizing variousradio access technologies and multiple frequency bands in wireless networks can provideefficient solutions to meet the growing demand of data. These techniques are promising forthe fifth generation (5G) wireless communication systems. However, to fully exploit theirbenefits, spectrum and spatial reuse, power saving, throughput and utility enhancementare crucial issues. In this thesis, we propose different resource allocation algorithms toaddress the aforementioned issues in wireless communication networks. First, we studythe resource allocation problem for a hybrid overlay/underlay cognitive cellular network.We propose a hybrid overlay/underlay spectrum access mechanism to improve the spectrumand spatial reuse. We formulate the resource allocation problem as a coalition formationgame among femtocell users, and analyze the stability of the coalition structure. Wepropose an efficient algorithm based on the solution concept of recursive core. The proposedalgorithm achieves a stable and efficient spectrum allocation. Next, we study the resourceallocation problem for multimedia content delivery in millimeter wave (mmWave) basedhome networks. We characterize different usage scenarios of multimedia content delivery.We formulate a joint power and channel allocation problem, which captures the spectrumand spatial reuse of mmWave communications, based on a network utility maximizationframework. The problem is a non-convex mixed integer programming (MIP) problem.We reformulate the non-convex MIP problem into a convex MIP problem and propose aiiAbstractresource allocation algorithm based on the outer approximation method. We also developan efficient heuristic algorithm which has a substantially lower complexity than the outerapproximation based algorithm. Finally, we study full-duplex relay-assisted device-to-device (D2D) communication in mmWave based wireless networks. To design an efficientrelay selection and power allocation scheme, we formulate a multi-objective combinatorialoptimization problem, which balances the trade-off between power consumption and systemthroughput. The problem is transformed into a weighted bipartite matching problem. Wethen propose a joint relay selection and power allocation algorithm, which can achieve aPareto optimal solution in polynomial time.iiiPrefaceChapters 2–4 of this thesis are based on the works performed under the supervision ofProf. Vincent W.S. Wong and the collaboration with Prof. Jianwei Huang, Dr. Man HonCheung, Dr. Hamed Shah-Mansouri, Dr. Binglai Niu, and Mr. Zehua Wang.Unless otherwise stated, for all chapters and corresponding papers, I conducted theliterature survey on related topics, identified the challenges, formulated the problems,performed the analyses and simulations. I wrote all paper drafts for which I am the firstauthor. My supervisor guided the research, validated the analyses, and provided commentsto improve the manuscripts. The collaborators’ contributions are listed below:• Prof. Jianwei Huang provided helpful comments on the system model, algorithmdesign and other parts of the paper related to Chapter 2.• Dr. Man Hon Cheung validated the analyses and provided comments for the paperrelated to Chapter 2.• Dr. Hamed Shah-Mansouri validated the analyses and provided valuable commentsfor the papers related to Chapters 3 and 4.• Dr. Binglai Niu and Mr. Zehua Wang provided comments on the simulation of thepaper related to Chapter 3.ivPrefaceJournal Papers, Published• Bojiang Ma, Man Hon Cheung, Vincent W.S. Wong, and Jianwei Huang, “HybridOverlay/Underlay Cognitive Femtocell Networks: A Game Theoretical Approach,”IEEE Trans. on Wireless Commun., vol. 14, no. 6, pp. 3259–3270, June 2015.• Bojiang Ma, Hamed Shah-Mansouri, and Vincent W.S. Wong, “Resource Manage-ment for Multimedia Content Delivery in Millimeter Wave Home Networks,” IEEETrans. on Wireless Commun., vol. 15, no. 7, pp. 4826–4838, July 2016.Journal Paper, Submitted• Bojiang Ma, Hamed Shah-Mansouri, and Vincent W.S. Wong, “Full-duplex Relayingfor D2D Communication in mmWave based 5G Networks,” submitted, 2016.Conference Papers, Published• Bojiang Ma, Man Hon Cheung, and Vincent W.S. Wong, “Interference Managementfor Multimedia Femtocell Networks with Coalition Formation Game,” in Proc. ofIEEE Int’l Conf. on Commun. (ICC), Budapest, Hungary, June 2013.• Bojiang Ma, Binglai Niu, Zehua Wang, and Vincent W.S. Wong, “Joint Power andChannel Allocation for Multimedia Content Delivery Using Millimeter Wave in SmartHome Networks,” in Proc. of IEEE Global Commun. Conf. (GLOBECOM), Austin,TX, Dec. 2014.• Bojiang Ma, Hamed Shah-Mansouri, and Vincent W.S. Wong, “A Matching Ap-proach for Power Efficient Relay Selection in Full Duplex D2D Networks,” in Proc.of IEEE Int’l Conf. on Commun. (ICC), Kuala Lumpur, Malaysia, May 2016.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Opportunities and Challenges in Future Wireless Networks . . . . . . . . . 31.1.1 Two-tier Cognitive Cellular Networks . . . . . . . . . . . . . . . . 31.1.2 Wireless Home Networks . . . . . . . . . . . . . . . . . . . . . . . 41.1.3 Relay-assisted D2D Communication Networks . . . . . . . . . . . . 61.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3 Summary of Results and Contributions . . . . . . . . . . . . . . . . . . . 121.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14viTable of Contents2 Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks . . 162.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2.1 Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3.1 Subchannel Allocation Under the Hybrid Overlay/Underlay AccessScheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3.2 Coalition Formation Game in Partition Form . . . . . . . . . . . . 262.3.3 Modified Recursive Core for Coalition Formation Game with Nega-tive Externalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.3.4 Stability Analysis of the Modified Recursive Core . . . . . . . . . . 352.4 Algorithm Design based on the Modified Recursive Core . . . . . . . . . . 362.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 Multimedia Content Delivery in mmWave based Home Networks . . . 483.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.2.1 Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.2.2 Integrated TDMA/FDMA/SDMA Scheduling for Wireless Home Net-works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.2.3 Utility Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593.4 Outer Approximation based Power and Channel Allocation Algorithm . . 633.5 Greedy Based Heuristic Algorithm . . . . . . . . . . . . . . . . . . . . . . 683.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71viiTable of Contents3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764 Full-duplex Relay-assisted D2D Communication in 5G Networks . . . 784.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 784.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 804.2.1 Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824.2.2 Throughput of a User Pair . . . . . . . . . . . . . . . . . . . . . . 844.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854.3.1 Reformulation Using Weighted Sum Method . . . . . . . . . . . . . 894.3.2 Bipartite Graph Construction . . . . . . . . . . . . . . . . . . . . . 904.3.3 Pareto Optimal Relay Selection . . . . . . . . . . . . . . . . . . . . 964.3.4 Algorithm Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 974.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1085 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 1105.1 Research Contributions and Results . . . . . . . . . . . . . . . . . . . . . 1105.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 112Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115AppendixA Proof of Theorem 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125viiiList of Tables2.1 List of key notations and variables used in this chapter . . . . . . . . . . . 212.2 Simulation parameters used in this chapter . . . . . . . . . . . . . . . . . . 393.1 List of key notations and variables used in this chapter . . . . . . . . . . . 513.2 Simulation parameters used in this chapter . . . . . . . . . . . . . . . . . . 724.1 List of key notations and variables used in this chapter . . . . . . . . . . . 80ixList of Figures1.1 Two-tier cellular network, wireless home network, and full-duplex relay-assisted D2D network. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.1 Hybrid overlay/underlay cognitive spectrum access system. . . . . . . . . . 182.2 Hybrid overlay/underlay cognitive femtocell networks. . . . . . . . . . . . . 192.3 Interference scenario for downlink communications in femtocell networks. . 232.4 Snapshot of coalition formation in a cognitive femtocell network for |F| = 12,|N | = 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402.5 Aggregate throughput of FAPs versus number of FAPs |F| when |N | = 5,|M| = 9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.6 Aggregate throughput of FAPs versus number of subchannels |M| when|N | = 3, |F| = 10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.7 Individual throughput of FUE versus the total number of switches when|N | = 2, |M| = 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.8 Average number of iterations to reach the optimal stable partition versusthe number of FAPs |F| when |N | = 4, |M| = 6. . . . . . . . . . . . . . . 442.9 Average coalition size of MRC algorithm versus the number of FAPs |F|when |M| = 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.10 Aggregate throughput of MRC algorithm and DCFA algorithm versus thenumber of FAPs |F|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46xList of Figures3.1 An example of a wireless home network. Solid arrows represent the mul-timedia content delivery links. Dashed lines illustrate the control messageexchange links. The access point also acts as a coordinator to schedule thetransmissions among the device pairs. . . . . . . . . . . . . . . . . . . . . . 523.2 An example of transmission pattern using directional transmitting and re-ceiving antennas. The antenna patterns illustrate gains in different direc-tions. The obstacles have different sizes and are located randomly. Fre-quency band 1 is allocated to link m to avoid possible interference withlinks i and j. Frequency band 2 is allocated to links i and j to improvespatial reuse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.3 Structure of the proposed integrated TDMA/FDMA/SDMA scheduling schemefor mmWave home networks. . . . . . . . . . . . . . . . . . . . . . . . . . . 573.4 An example of utility versus effective throughput for different scenarios. . . 603.5 Aggregate throughput versus number of links with the home area of 10 m× 10 m and Θ3dB = 15o. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733.6 Aggregate throughput versus half power beam width with the home area of10 m × 10 m. The number of links |Q| = 10. . . . . . . . . . . . . . . . . 743.7 Aggregate utility versus number of links with the home area of 10 m × 10m and Θ3dB = 15o. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753.8 Aggregate utility versus usage scenarios with the home area of 10 m × 10m. The number of links |Q| = 10. . . . . . . . . . . . . . . . . . . . . . . 764.1 An mmWave based D2D network with full-duplex relays and directionaltransmissions. D2D user pairs can choose whether or not to use full-duplexrelays. The base station coordinates the resource allocation in the network. 81xiList of Figures4.2 (a) A bipartite graph with four D2D user pairs and three relays. (b) Amatching example with four edges (l1, r2), (l2, r1), (l3, r2), and (l4, r3). (c)The one-to-one matching with virtual relays in dashed frames. . . . . . . . 914.3 Total transmission power versus number of D2D user pairs |L| with |R| = 4. 1014.4 Total transmission power versus number of relays |R| with |L| = 13. . . . . 1024.5 Total transmission power versus minimum data rate requirement Cminli , ∀li ∈L with |R| = 4 and |L| = 13. . . . . . . . . . . . . . . . . . . . . . . . . . 1034.6 System throughput versus number of D2D user pairs |L| with |R| = 4. . . 1044.7 System throughput versus number of relays |R| with |L| = 13. . . . . . . . 1054.8 System throughput versus loop-interference gain hLI . . . . . . . . . . . . . 1064.9 Optimal power consumption and system throughput versus weighting factorλ2 when λ1 = 1 with |R| = 4 and |L| = 13. . . . . . . . . . . . . . . . . . . 1074.10 Pareto optimal frontier for different number of D2D user pairs. . . . . . . . 108xiiList of Abbreviations5G Fifth generationARS All relays selectionBRP Beamforming refinement protocolCCI Co-channel interferenceCN Core networkCR Cognitive radioCRN Cognitive radio networkCSMA/CA Carrier sense multiple access with collision avoidanceD2D Device-to-deviceDCFA Distributed coalition formation algorithmFAP Femtocell access pointFDMA Frequency division multiple accessFGW Femtocell gatewayFUE Femtocell user equipmentHDTV High-definition televisionIEEE Institute of electrical and electronics engineersIP Internet protocolLOS Line-of-sightmmWave Millimeter waveMAC Medium access controlxiiiList of AbbreviationsMBS Macrocell base stationMIMO Multiple-input multiple-outputMIP Mixed integer programmingMILP Mixed-integer linear programmingMRC Modified recursive coreMUE Macrocell user equipmentNLOS Non-line-of-sightNLP Nonlinear programmingNTU Non-transferable utilityOA Outer approximationOFDMA Orthogonal frequency division multiple accessPU Primary userQoS Quality of serviceRB Resource blockRF Radio frequencySDMA Space division multiple accessSHSS Scalable heuristic STDMA schedulingSINR Signal-to-interference plus noise ratioSTDMA Space time division multiple accessSU Secondary userTDMA Time division multiple accessTU Transferable utilityVMCCT Vertex multi-coloring concurrent transmissionWLAN Wireless local area networkWPAN Wireless personal area networkxivAcknowledgmentsFirst of all, I want to express my deep appreciation to my supervisor, Prof. Vincent W.S.Wong, for his patient guidance, extensive feedback and invaluable help during my PhDstudies. From him, I learned not only how to be a good researcher, but also the correctattitude to work and life. Besides, I appreciate him to allow me attending and presentingour work at various conferences.I sincerely thank Prof. Jianwei Huang, Dr. Hamed Shah-Mansouri, and Dr. Man HonCheung, for their constructive advice on my research. I am grateful to Dr. Binglai Niuand Mr. Zehua Wang for their comments about my work on multimedia content deliveryin wireless home networks.Also, I thank the members of my doctoral committee, Prof. Vijay K. Bhargava, Prof.Victor C.M. Leung, and Prof. Sathish Gopalakrishnan for the time and effort in evaluatingmy work and providing feedback and suggestions.I am indebted to my parents and my wife for their love, which makes me through thistough process.This work was supported by the Natural Sciences and Engineering Research Council(NSERC) of Canada.xvDedicationTo my parents, for their unconditional support and love from overseas. I know they missme. I miss them too. To my wife, for her understanding, encouraging, support, and love.xviChapter 1IntroductionDue to the fast increasing demand of data usage in wireless networks, the telecommuni-cations industry is driven to improve the spectrum efficiency through various techniques,such as signal beamforming, massive multiple-input multiple-output (MIMO), successiveinterference cancellation, etc. However, the improvement with these approaches is far fromfully satisfying the increasing data demand. A heterogeneous wireless network architec-ture that includes various radio access technologies (e.g., cellular network, wireless localarea network (WLAN)), multiple frequency bands (e.g., 900 MHz, 2.4 GHz, 5 GHz, 38GHz, and 60 GHz bands), base stations of different coverage (e.g., macrocell and femtocellbase stations), and different wireless communication technologies (e.g., cognitive radio1and device-to-device (D2D) communication), is filling the gap, and is promising for thefifth generation (5G) wireless communication systems. Three candidate networks for thefuture heterogeneous wireless communication systems are two-tier cognitive cellular net-works, wireless home networks, and relay-assisted D2D communication networks. Fig. 1.1briefly illustrates these three types of networks. Fig. 1.1 (a) shows a two-tier cellular net-work with femtocells and macrocells. Femtocell users and macrocell users utilize cognitiveradio technology to further exploit the potentials of spectrum reuse. Fig. 1.1 (b) showsa wireless home network, which is located in the coverage of a larger cellular network.1According to the Federal Communications Commission (FCC), cognitive radio is defined as a radio orsystem that senses its operational electromagnetic environment and can dynamically and autonomouslyadjust its radio operating parameters to modify system operation, such as maximize throughput, mitigateinterference, facilitate interoperability, access secondary markets [1].1Chapter 1. IntroductionFigure 1.1: Two-tier cellular network, wireless home network, and full-duplex relay-assistedD2D network.The list of devices in the wireless home network includes tablet, high-definition television(HDTV), TV box, laptops, wireless game console, and wireless monitor. Multimedia con-tent is delivered via the data links between devices. Fig. 1.1 (c) shows a relay-assisted D2Dcommunication enabled network. Full-duplex relay-assisted D2D communication with di-rectional transmissions helps improve the throughput of D2D links and reduce the powerconsumption of mobile devices. For all of the aforementioned networks, efficient resourceallocation schemes are crucial to improve network performance and users satisfaction.In this thesis, we propose various resource allocation schemes to improve the spectrumefficiency, user utility, and power saving for wireless networks. The cooperative gametheory, mixed integer programming optimization theory, and matching theory are used inthe design of the proposed schemes. The rest of this chapter is organized as follows. InSection 1.1, we provide an overview of opportunities and challenges in the aforementionedthree types of wireless networks. We introduce the related work in Section 1.2. The results2Chapter 1. Introductionand contributions in this thesis are summarized in Section 1.3, and the thesis organizationis provided in Section 1.4.1.1 Opportunities and Challenges in Future WirelessNetworksTwo-tier cognitive cellular networks, wireless home networks, and relay-assisted D2D com-munication enabled networks are three important wireless networks in future communi-cation systems. The ongoing research and standardization process also highlight the po-tentials of these wireless networks. In this section, we introduce the opportunities andchallenges in these three types of wireless networks.1.1.1 Two-tier Cognitive Cellular NetworksIn a two-tier cellular network, femocells are located in the coverage of a macrocell basestation. A femtocell access point (FAP) is a small low-power cellular base station, deployedeither by the users or service providers in order to improve the coverage and capacity ofcellular systems. There have been increasing interests in femtocell deployment in wirelesscellular networks. Subscribed femtocell customers can autonomously deploy FAPs to createcellular hotspots [2]. Due to the autonomous deployment of FAPs, interference manage-ment becomes a challenging issue [3]. One promising solution to address the interferenceissue is to use orthogonal frequency division multiple access (OFDMA) for femtocells [4, 5].In OFDMA systems, the available spectrum is divided into orthogonal subchannels. Thesystem allocates different users with different groups of orthogonal subchannels. However,in an area with lots of femtocells, it is unlikely that all users can be allocated differentorthogonal channels at the same time, since the number of channels may be far less than3Chapter 1. Introductionthe number of users. Furthermore, in order to utilize the limited licensed spectrum moreefficiently, the service providers would consider frequency reuse in the network planning.The frequency reuse requires adaptive scheduling algorithms to mitigate the co-channel in-terferences among users using the same channel. Cognitive radio (CR) can be a promisingtechnology to realize such flexible interference management [6].Spectrum overlay and spectrum underlay are two approaches commonly considered incognitive radio networks (CRNs). In an overlay cognitive system, secondary users (SUs)are only allowed to use unoccupied spectrum holes (channels). Spectrum underlay allowsSUs to simultaneously operate in frequency bands where primary users (PUs) are active,but under strict SU transmission power constraints [7]. The hybrid overlay/underlay spec-trum access combines the benefits of both overlay and underlay methods, creating a newapproach to further exploit both the unused spectrum regions and the under-utilized spec-trum areas. Hybrid overlay/underlay CR spectrum access is flexible to deal with differentfemtocell densities in both urban areas and rural areas [8]. When the spectrum is lesscrowded such as in rural areas, SUs are more likely to transmit on idle subchannels. Incase of dense deployment of femtocells such as in urban areas, where not all users canfind unused spectrum bands, the hybrid access scheme helps further improve the spectrumefficiency and system throughput, while guaranteeing the quality of service (QoS) of PUs.However, an efficient resource allocation scheme is crucial to obtain the benefits of hybridoverlay/underlay CR.1.1.2 Wireless Home NetworksWireless home networks, which facilitate communications among devices inside homes, canimprove the quality of life of the residents [9]. With the popularity of devices such as smartHDTV, tablets, and smartphones, multimedia content delivery has been a major source of4Chapter 1. Introductiondata traffic in home networks. Therefore, the number of devices and their traffic demandare increasing. It is important to improve the spectrum efficiency to better utilize thelimited spectrum resources and meet the QoS requirements at the same time. The recentlydeveloped millimeter wave (mmWave) band technology shows the potential to providehigh data rate transmissions as well as high spectrum efficiency [10, 11]. The mmWavetechnology can provide over 1 Gbps data rate for short range communication [12], whichis promising for multimedia content delivery [13, 14]. Since the mmWave systems utilizedirectional transmissions [15], they result in small interfering ranges and can provide agood opportunity for spectrum reuse in wireless home networks.IEEE released the 802.15.3c [16] and 802.11ad [17] standards2 for the wireless personalarea network (WPAN) and WLAN based on mmWave band technology. Both standardsaim to enhance the throughput in the 60 GHz band. The applications include the support ofwireless uncompressed video streaming, super broadband Internet access, and wireless officespace in smart homes [18]. 802.15.3c and 802.11ad standards have similar medium accesscontrol (MAC) protocols. They have signalling period for control purpose, transmissioncoordination period for scheduling decision announcement, and data transfer interval. Theyuse carrier sense multiple access with collision avoidance (CSMA/CA) for the contention-based access periods and time division multiple access (TDMA) for the reservation-basedaccess periods. The IEEE 802.11ay [19, 20] study group is formed in 2015 to extend IEEE802.11ad and further improve the throughput and different usage scenarios of mmWavenetworks. However, the standardization process is still ongoing (October 2016) and stabledocuments are yet to be released.Spectrum sharing and scheduling are important issues in resource allocation for mmWave2The IEEE 802.11ac which works on 5 GHz frequency band is also a good choice to satisfy the currentdemand of home networks. It can be regarded as an extension of 802.11a/g in terms of the MAC in 5 GHzband. In Chapter 3, we focus on the mmWave based home networks which can further satisfy the usagerequirements in future home networks.5Chapter 1. Introductionwireless networks. TDMA, frequency division multiple access (FDMA), and space divisionmultiple access (SDMA) are three different multi-user access methods that schedule userswith the shared resources. TDMA and FDMA eliminate interference among users by allo-cating non-overlapping resources. SDMA improves the system throughput by consideringspatial reuse under interference control. TDMA has been used as the scheduling schemefor several industrial standards [16, 17, 21]. It can prevent co-channel interference and issimple to be implemented. However, TDMA does not fully exploit the spatial reuse andresults in a low spectrum efficiency. Meanwhile, mmWave technology adopts directionalantennas which provide a significant opportunity to further utilize FDMA and SDMA.Considering the features of mmWave signals, an integrated scheme, which employs SDMAtogether with FDMA and TDMA, can combine the benefits of each scheme and improvethe spectrum efficiency.1.1.3 Relay-assisted D2D Communication NetworksD2D communication, where mobile devices communicate with each other directly, addsanother dimension and provides new opportunity to wireless networks. Relay-assistedD2D communication, which allows relays to help D2D communication is promising for thefuture wireless networks. D2D communication can provide high data rate transmissionsand offload data traffic from cellular base stations [22]. Relays in D2D networks canfurther reduce the energy consumption of mobile devices, enhance the quality of datatransmission, assist connection establishment among devices, and increase the range ofD2D communication [23]. The recently developed full-duplex techniques allow relays tosimultaneously transmit and receive signals by enabling self-interference cancellation. Byusing full-duplex relaying in D2D communication, where relays operate in full-duplex mode,the spectrum efficiency can be improved over traditional half-duplex relaying systems.6Chapter 1. IntroductionHowever, the limited battery capacity of mobile devices has become a major barrierto obtain the aforementioned benefits of D2D communication. Meanwhile, the increasingtraffic demand of emerging applications requires a higher throughput of D2D communica-tion. In order to fully exploit the potentials, full-duplex relays with mmWave technologyand directional transmissions can substantially save the power of mobile devices and im-prove the data rate. However, the relay selection schemes designed for omni-directionaltransmissions cannot fully exploit the possible spatial reuse that can further improve thespectrum efficiency in directional communications. In addition, the relay selection schemesproposed for half-duplex relays may not be efficient in full-duplex relay-assisted D2D sys-tems, since self-interference does not exist in half-duplex relaying systems. An efficientrelay selection scheme designed for full-duplex systems with directional transmissions isessential to reduce the power consumption of devices, extend their battery lifetime, andincrease the throughput.1.2 Related WorkTwo-tier Cognitive Cellular NetworksSeveral recent studies have considered two-tier cellular networks cognitive capabilities.Meerja et al. in [24] proposed a sensing scheme for the overlay cognitive femtocell net-works, and determined the throughput by using a Markov chain model. Lien et al. in[25] proposed a CR resource management scheme, which guarantees the QoS in terms ofdelay for femtocell networks. Attar et al. in [26] studied the interference managementschemes with cognitive macrocell and femtocell base stations, and proposed game theo-retic mechanisms to mitigate the interference. Urgaonkar et al. in [27] investigated theopportunistic cooperation between femtocell users and macrocell users, and designed a7Chapter 1. Introductioncontrol algorithm for cooperation under both the relay model and the interference model.Adhikary et al. in [28] discussed the impact of open and closed access interference can-celations in cognitive femtocells, and proposed a downlink interference alignment scheme.Al-Rubaye et al. in [29] proposed a priority queuing strategy for data packets delivery inindoor cognitive femtocell systems. From a game theoretic point of view, Gharehshiran etal. in [30] considered a collaborative subchannel allocation for cognitive femtocell networksusing coalitional game theory. In [31], Pantisano et al. used coalition formation game tostudy the cooperations between macrocell and femtocell in the uplink spectrum sharing.In [32], Guruacharya et al. applied the concept of network MIMO to small cell networksand proposed a scheme based on coalition formation game to perform the cluster-wise jointbeamforming.In the analysis of the cooperation between femtocells and macrocells with CR capa-bilities, femtocell users are usually regarded as unlicensed SUs of the CRNs and accessthe spectrum with the overlay scheme [24, 26, 27, 30]. However, such treatment may beoversimplifying. In traditional CRNs, SUs are assumed to be unlicensed low priority users.However, in cognitive femtocell networks, the femtocell users are also regular subscribers ofthe same cellular provider which serves the macrocell users, hence they should have a higherpriority than the SUs in traditional CRNs. In the closely related work [30], Ghareshiranet al. focused on the behavior of the users with a cognitive ability, but did not address thespectrum sharing issue for PUs and SUs of the cognitive femtocell networks. They formu-lated the subchannel allocation problem as a cooperative game in characteristic form, butdid not consider the interference.Wireless Home NetworksThere are several studies which investigate the resource allocation problem in wireless homenetworks. Wu et al. in [13] summarized the challenges of mmWave multimedia communi-8Chapter 1. Introductioncation in home networks and developed a QoS-aware multimedia scheduling scheme whichachieves a balance between users’ satisfaction and computational complexity. Yiakoumiset al. in [33] proposed a home network slicing control mechanism, which allows differentservice providers to deploy services using a shared infrastructure. They also presenteda method to customize the slices for high quality services. A resource reservation-basedbackoff mechanism is proposed in [34], which reuses time slots for transmission in backoffcycles to improve QoS for video delivery in home networks. In [35], Li et al. designed adistributed power control scheme with different radio access technologies, which aims tomaximize the aggregate data rate of home networks. Sundaresan et al. in [36] developeda detection algorithm to locate the throughput bottlenecks in home networks. It uses tim-ing and buffer information to accurately detect the bottlenecks in both cable and wirelesslinks. Li et al. in [37] proposed a new rate adaptation scheme to reduce the latency fordelay-sensitive applications in home networks.Meanwhile, spatial reuse has been considered for mmWave technology in several studies.Park et al. in [38] investigated the potentials for spatial reuse and interference managementin mmWave wireless networks and developed a simulation model to evaluate the spatialreuse performance. In [39], Chen et al. proposed a spatial reuse strategy for mmWaveWPANs with different directional antennas based on beamforming information. Spacetime division multiple access (STDMA) scheme allows concurrent transmissions in thesame time slot. A scalable heuristic STDMA scheduling (SHSS) algorithm is proposed in[40] to enhance the throughput of mmWave based networks. In [41], Singh et al. investi-gated interference management for mmWave mesh networks, and proposed an analyticalframework to estimate the impact of antenna pattern and density of concurrent links on theMAC protocol. Qiao et al. in [42] formulated an optimization problem to maximize the ag-gregate throughput of indoor mmWave networks by considering concurrent beamforming.9Chapter 1. IntroductionThey proposed an iterative beam searching algorithm, which increases the throughput andimproves the energy efficiency of the system. Athanasiou et al. in [43] considered multi-user SDMA in client association problem and proposed an association algorithm based onsubgradient methods.Special characteristics of mmWave communications (e.g., directional transmission viabeamforming, low multiuser interference) have been utilized to improve various perfor-mance metrics. From the perspective of mmWave local area networks, in [44], Shokri-Ghadikolaei et al. investigated the important challenges of MAC design in short rangemmWave networks. They showed that collision-aware MAC can improve the efficiencyof mmWave networks. In [45], Son et al. developed a directional MAC protocol to al-low concurrent transmissions to exploit spatial reuse in mmWave WPANs. Kim et al.in [46] considered the video transmission in a sport stadium using mmWave technologyand formulated a relay selection and coding rate adaption problem to maximize the videoquality. From the perspective of mmWave cellular networks, Zheng et al. in [47] studiedthe challenges and protocols in 5G mmWave based cellular systems. Their simulation re-sults show the potential of achieving a very high capacity in the future mmWave cellularsystems. In [48], Di Renzo introduced a novel analysis framework using stochastic geom-etry for mmWave cellular networks. The analysis and simulation results showed that thenoise-limited approximation is accurate for typical cellular network densities. Besides, themeasurement results for mmWave home networks are provided in [49–52].Relay-assisted D2D Communication NetworksResource allocation in D2D communication enabled networks has been widely studied in theliterature [53–61]. Niu et al. in [53] proposed a scheduling scheme for D2D transmissionsto exploit spatial reuse in mmWave heterogeneous cellular systems. In [54], Rehman etal. proposed a scheduling algorithm for mmWave D2D networks using vertex coloring10Chapter 1. Introductionapproach. Their method improved the aggregate throughput by scheduling the conflictingflows with different priority. Li et al. in [55] investigated the uplink resource allocationproblem for D2D networks. They proposed a scheme for transmission mode selection andresource sharing by formulating a coalition formation game. In [56], Wang et al. studieda joint channel and power allocation problem for D2D communication and proposed aniterative algorithm to optimize the energy efficiency. Qiao et al. in [57] proposed a resourcesharing scheme to enable concurrent transmissions for D2D communication in mmWavebased wireless networks. In [58], Nguyen et al. proposed fair scheduling policies to exploitspatial and frequency reuse in D2D-enabled cellular systems. Xing et al. in [59] proposedresource reuse algorithms to improve the spectrum efficiency of D2D communication incellular networks. In [60], Sheng et al. proposed an iterative algorithm based on fractionalprogramming and the Lyapunov optimization technique to balance the trade-off betweenenergy efficiency and delay in D2D communication. Zhang et al. in [61] studied the channelallocation problem by using hypergraph theory, where D2D users are allowed to share theuplink channels with cellular users.Several existing studies show that relaying can enhance D2D communication [62–66].In [62], Shi et al. studied the energy-efficient spectrum sharing problem in D2D wirelessregional area networks. They proposed a mechanism for relay-assisted networks to optimizeenergy consumption and channel utilization. Hasan et al. studied a multi-user relay-assisted D2D network in [63] and formulated a robust optimization problem by consideringthe channel uncertainties. They showed that relay-assisted communication can significantlyimprove the aggregate data rate. Wang et al. in [64] studied the feasibility of enablingfull-duplex capability to D2D communication in heterogeneous networks. They identifiedseveral challenges and provided potential solutions for the interference mitigation issue infull-duplex D2D networks. In [65], Zhang et al. proposed a power allocation scheme which11Chapter 1. Introductionaims to maximize the data rate of D2D users in a relay-assisted D2D network underlayingthe cellular system. Al-Hourani et al. in [66] derived a closed-form expression for energysaving geometrical zone where relaying is efficient. The aforementioned existing worksreveal the benefits of using relays in D2D communication. Nevertheless, none of themjointly consider the importance of energy saving for battery-powered devices and systemthroughput for high data rate applications.1.3 Summary of Results and ContributionsThis thesis studies several resource allocation problems in different types of wireless net-works. The results are divided into three chapters. The results and contributions in eachchapter are as follows:1. In Chapter 2, a hybrid overlay/underlay cognitive radio scheme for the two-tier cel-lular networks is proposed. In order to characterize and mitigate the interference,a subchannel allocation problem is formulated as a coalition formation game withnegative externalities. Stability and efficiency of the network game are analyzed. Astable and efficient solution of the coalition formation game lying in the recursivecore of the game is obtained. Based on the solution concept of the recursive core,a modified recursive core (MRC) algorithm is proposed, which provides an efficientand stable coalition formation for the hybrid cognitive radio scheme. Simulation re-sults show that the proposed MRC algorithm achieves a higher aggregate throughputthan the overlay only scheme, underlay only scheme, and a hybrid overlay/underlayscheme without MRC. Results also show a substantial improvement compared toanother coalition formation algorithm from [30]. Part of the work of Chapter 2 hasbeen presented in [67] whereas the full paper has been published in [68].12Chapter 1. Introduction2. In Chapter 3, a variety of utility functions are introduced to characterize differentusage scenarios and types of multimedia services in wireless home networks. A novelintegrated TDMA/FDMA/SDMA scheduling scheme, which allows concurrent trans-missions using directional antenna for mmWave based home networks, is proposed.The proposed scheme further increases the spectrum efficiency by exploiting the po-tentials of spatial reuse. A channel and power allocation problem is formulated byconsidering QoS and energy efficiency requirements of users. The objective of the for-mulated problem is to maximize the aggregate network utility. The problem, whichis a non-convex mixed integer programming (MIP) problem, is reformulated into aconvex MIP problem. An algorithm based on the outer approximation (OA) methodis proposed to obtain the optimal solution of the reformulated problem. To reducethe computational complexity of the OA based algorithm, a low complexity heuristicalgorithm is proposed. The performance of our proposed algorithms is evaluated interms of aggregate utility and throughput for different home networks. The pro-posed algorithm is also compared to recently proposed scheduling algorithms from[40] and [54]. Results show that the proposed algorithm substantially outperformsthe algorithms in the literature in terms of aggregate throughput and utility. Partof the work of Chapter 3 has been presented in [69] whereas the full paper has beenpublished in [70].3. In Chapter 4, a relay selection and power allocation scheme is proposed for full-duplexrelay-assisted D2D communication in mmWave based networks. By considering theimpact of self-interference in full-duplex relaying systems, a multi-objective combina-torial optimization problem is formulated. The objective of the formulated problem isto reduce the total transmission power and improve the system throughput. CertainQoS requirements of different services and physical constraints of the devices and13Chapter 1. Introductionrelays are also considered. To mitigate the complexity of the combinatorial problem,the problem is transformed into a one-to-one weighted bipartite matching problem,which can be solved optimally. An algorithm is proposed for the matching problem,and is proved to achieve a Pareto optimal solution of the relay selection and power al-location problem in polynomial time. The performance of our proposed algorithm isevaluated under different network settings and compared with an existing algorithmproposed in [71]. Simulation results show the trade-off between power consumptionand system throughput. Compared to the algorithm from [71], the proposed al-gorithm improves the power consumption and the system throughput significantly.Part of the work of Chapter 4 has been presented in [72] whereas the full paper hasbeen submitted for publication in IEEE Transactions on Wireless Communications.1.4 Thesis OrganizationThe rest of this thesis is organized as follows. In Chapter 2, we study the subchannelallocation problem for hybrid overlay/underlay cognitive femtocell networks. We proposea hybrid overlay and underlay spectrum access mechanism to improve the performance ofcognitive femtocell networks. We formulate a subchannel allocation problem as a coalitionformation game among femtocell users under the hybrid access scheme, and analyze thestability of the coalition structure. We propose an efficient algorithm based on the solutionconcept of recursive core, and achieve a stable and efficient allocation. In Chapter 3, wecharacterize different usage scenarios of multimedia content delivery by introducing a setof utility functions. We formulate a joint power and channel allocation problem based ona network utility maximization framework, which captures the spatial and frequency reuseof mmWave communications. We reformulate the problem into a convex MIP problemand propose a resource allocation algorithm based on OA method. We develop an efficient14Chapter 1. Introductionheuristic algorithm which has a lower complexity than the OA based algorithm. In Chapter4, we study full-duplex relay-assisted D2D communication in mmWave based 5G networks.We formulate a multi-objective combinatorial optimization problem, which balances thetrade-off between power consumption and system throughput. We transform the prob-lem into a weighted bipartite matching problem and propose a joint relay selection andpower allocation algorithm based on the Hungarian method. We prove that the proposedalgorithm can achieve a Pareto optimal solution in polynomial time. Finally, Chapter 5concludes the thesis and provides some potential future works. Chapters 2–4 in this thesisare self-contained and included in separate journal or conference papers. The notationsare defined separately for Chapters 2–4.15Chapter 2Hybrid Cognitive Spectrum Accessin Two-Tier Cellular Networks2.1 IntroductionIn this chapter, we study the subchannel allocation problem for cognitive two-tier cellularheterogeneous networks. To improve the overall system performance, besides designingspectrum access schemes for primary users (PUs) and secondary users (SUs), it is alsoimportant to encourage the cooperation among SUs, which may also generate interferenceamong themselves. Coalitional game theoretical approaches allow SUs to form coalitions,which can mitigate the interference cooperatively and improve the spectrum efficiency. Inthis chapter, we consider the femtocell users operating under a hybrid cognitive radio (CR)access scheme, which is more adaptive to the density change of the femtocell deployment,and can improve the spectrum efficiency substantially verified by our extensive simulations.Moreover, the femtocell users have a higher priority comparing to those in the previousstudies [24, 26, 27, 30]. Specifically, we apply the cooperative game theory [73, 74] tostudy the subchannel allocation problem in such a hybrid CR based femtocell network.To achieve the cooperation among SUs, femtocell users can form coalitions and coordinatetheir transmissions using the femtocell gateway. We formulate the problem as a coalitionformation game in partition form [74] with negative externalities (due to the interference),and propose a modified recursive core algorithm to find an efficient stable solution of the16Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networksgame. The main contributions of this chapter are as follows:• We design a hybrid overlay/underlay CR scheme for femtocell networks. We formu-late the subchannel allocation problem as a coalition formation game with negativeexternalities, to effectively characterize and mitigate the interference. We analyze thestability and efficiency for the network game, and characterize a stable and efficientsolution of the coalition formation game lying in the recursive core of the game.• Based on the solution concept of the recursive core [75], we propose a modifiedrecursive core (MRC) algorithm to achieve an efficient and stable coalition formationfor the hybrid CR scheme.• Simulation results show that our proposed MRC algorithm achieves a higher aggre-gate throughput for femtocells than the overlay only scheme, underlay only scheme,and a hybrid overlay/underlay scheme without MRC. It also outperforms anotherrecently proposed coalition formation algorithm [30].The rest of the chapter is organized as follows. In Section 2.2, we present the systemmodel. We formulate the coalition formation problem in Section 2.3, and propose thealgorithm based on the recursive core in Section 2.4. Simulation results are presented inSection 2.5, followed by a summary in Section 2.6.2.2 System ModelWe consider a cognitive femtocell network with some femtocell access points (FAPs) andfemtocell user equipment (FUEs). The femtocell network is within the range of a macrocellbase station (MBS). The macrocell user equipment (MUEs) are regarded as PUs and theFUEs are regarded as SUs. However, different from a traditional cognitive radio network17Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular NetworksFigure 2.1: Hybrid overlay/underlay cognitive spectrum access system.(CRN), the FUEs have a higher priority in a cognitive femtocell network. In Fig. 2.1, weshow the four spectrum sharing schemes for (a) OFDMA, (b) cognitive overlay, (c) cognitiveunderlay, and (d) hybrid cognitive overlay/underlay, respectively. In Fig. 2.1 (a), all usersare allocated orthogonal subchannels in different time slots using OFDMA and no cognitiveusers are considered. Figs. 2.1 (b), (c), and (d) consider the CR systems. In Fig. 2.1 (b),SUs detect and use idle spectrum holes to transmit under the cognitive overlay scheme. InFig. 2.1 (c), SUs can use the same subchannel with PUs without performing any detectionunder the cognitive underlay scheme, as long as the signal-to-interference plus noise ratio(SINR) requirements of PUs are satisfied. Fig. 2.1 (d) represents our proposed hybridoverlay/underlay spectrum sharing scheme, where we allow the SUs to adapt the ways ofaccessing the licensed spectrum according to the status of the PUs. If the PU is detectedto be idle at the selected subchannel, then the SU uses the idle subchannel with the overlayscheme. If no idle subchannel is available, the SU uses an occupied subchannel when theSINR requirements of PUs are satisfied with the underlay scheme.Users in both the macrocell and femtocells utilize resources belonging to the same ser-18Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular NetworksFigure 2.2: Hybrid overlay/underlay cognitive femtocell networks.vice provider. An example of hybrid overlay/underlay cognitive femtocell network systemis shown in Fig. 2.2. In the network, each FAP is connected to the core network (CN)through an Internet protocol (IP) backhaul and femtocell gateway (FGW) [2]. The FGWserves as the coordinator of FAPs for a local area, such as FAPs in the same apartmentsbuilding or nearby houses. For a sparse femtocell deployment, such as femtocells in thedetached houses in the rural area, the spectrum resources are sufficient for both MUEsand FUEs to occupy completely orthogonal subchannels. In such a sparse scenario, thecognitive overlay is preferred to maximize the performance of each user. On the otherhand, femtocell deployment can be highly dense in apartment or office buildings. In sucha dense scenario, the number of available subchannels may not be sufficient for all users19Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networksto occupy different orthogonal subchannels. Multiple users may have to share a commonsubchannel, under the condition that the interference level for each MUE is acceptable.Therefore, the hybrid overlay/underlay access method becomes the most flexible option ina high density deployment case.Let us consider a set of FAPs F in the coverage of a macrocell, where an FAP is indexedby i. The set of FUEs associated with FAP i is Ki, and the size of Ki is usually between1 and 4 [76]. The operator has a total available spectrum of W Hz. We consider a set oflicensed subchannelsM (with the size |M| = WB), where each subchannel has a bandwidthof B Hz and consists of several consecutive subcarriers. The key notations used in thischapter are listed in Table 2.1.We assume that the number of subchannels is not sufficient for all MUEs and FUEsto have separated subchannels. In a shared spectrum system, signals from a macrocelland femtocells are likely to transmit simultaneously in the same subchannels. Therefore,co-channel interference (CCI) may occur. The FAP has the cognitive ability to detectwhether a co-channel user (macrocell user or femtocell user) is nearby, and is responsibleof allocating subchannels to its users. When an FAP is about to allocate subchannels, itwill first sense the spectrum environment to determine the available spectrum bands. Thesensing coordination among multiple FAPs can be implemented by exchanging neighboringfemtocell information through the FGW. We assume that each FAP is equipped with twotransceivers. One of them is used for spectrum sensing, while the other one is used forboth intra-femtocell and inter-femtocell communications on the selected channels. Thus,FAP can perform spectrum sensing and data transmission simultaneously.Once an FAP has sensed the spectrum, it will send the information regarding theused and unused spectrum list to the database at the FGW. FAPs from other femtocellscan access these information from the database, and share the spectrum information with20Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular NetworksTable 2.1: List of key notations and variables used in this chapterSymbols MeaningA(Q) Set of coalition structureb The MBSB Subchannel bandwidthC(F , v) Recursive core of game (F , v)dik Distance between FAP i and FUE kF Set of FAPsG(m)ik Fading between FAP i and FUE k on subchannel mh(m)ik Average channel gain between FAP i and FUE k on subchannel mI(m)ik Interference power for FUE k in FAP i on subchannel mKi Set of FUEs in FAP iM Set of total available subchannelsMFAPi Set of subchannels allocated to FAP iMMUEn Set of subchannels allocated to MUE nMS Set of subchannel pool of the coalition SN Set of MUEsN(m)0 Background noise power level on subchannel mP(m)ik Transmission power for FUE k of FAP i on subchannel mR(m)ik Transmission rate of FUE k in FAP i on subchannel mRik Transmission rate of FUE k in FAP iSINR(m)ik SINR for FUE k in FAP i on subchannel mv Value of the gameW Total available spectrum bandwidthxi(S, pi) Payoff of player i in coalition S under partition piγ Path loss exponentpi Coalition structure or partitionneighboring FAPs. We assume that the backhaul has abundant bandwidth for the transferof data and control packets3. When an FAP detects the return of a MUE to a previouslyavailable subchannel, it will coordinate with other FAPs based on the proposed cooperative3We consider a typical femtocell scenario with less than four FUEs in an FAP [76], and each FAPonly serves subscribed users (i.e., closed access). The operator can check backhaul requirement at theinstallation of an FAP to make sure the backhaul bandwidth is enough for the designed uses [77].21Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networksgame and adjust the subchannel allocation to its FUEs.2.2.1 Channel ModelWe focus on the downlink communications from the FAPs to the FUEs and from the MBSto the MUEs4. We will use the co-channel SINR in evaluating the average link qualityand thus the data rate of each user. With concurrent transmissions of multiple users (canbe both FUE and MUE) on the same subchannel, the transmission rate of each user isconstrained by the aggregate interference from other users. The interference scenario isshown in Fig. 2.3, where the solid-line arrow represents the signal of downlink transmissionand the dash-line arrow represents the interference signal. Note that only FUEs and MUEson the same subchannel will interfere each other.We use P(m)ik to represent the transmission power of FAP i to FUE k on subchannelm ∈M, the corresponding downlink received SINR isSINR(m)ik =P(m)ik |h(m)ik |N(m)0 + I(m)ik, (2.1)where h(m)ik is average channel gain of the link between FAP i and FUE k in channel m, andincorporates the impact of both fading and path loss. Specifically, we have h(m)ik = G(m)ik d−γik ,where G(m)ik is the fading between FAP i and FUE k on subchannel m (signal attenuationat reference distance is included), dik is the distance between FAP i and FUE k, γ is thepath loss exponent, N(m)0 is the background noise power of subchannel m, and I(m)ik is theaggregate interference power received by FUE k on subchannel m with FAP i as the source4The analysis can be generalized to other scenarios with minor modifications, such as the changesin the parameters characterizing the positions of the information source, interference sources, and thetransmission power. For example, in an uplink communication scenario that uses a different frequencyband, the interference sources are the FUEs and the MUEs instead of the FAPs and the MBS. Our methodis still applicable by considering the corresponding channel models. In the scenario that the femtocells andthe macrocell use separate frequency bands, our formulation is also applicable by treating the transmittingFAPs as PUs.22Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular NetworksFigure 2.3: Interference scenario for downlink communications in femtocell networks.node. For the link between FAP i and FUE k, we assume that FUE k can achieve atransmission rate R(m)ik on subchannel m according to the Shannon capacity formula, i.e.,R(m)ik = ηB log2(1 + SINR(m)ik), (2.2)where η ∈ [0, 1] is a coefficient describing the efficiency of the transceiver design. In thehybrid overlay/underlay CR access scheme, FUEs attempt to find unoccupied subchannelsfirst. If no spectrum hole exists, the FUEs will share a subchannel with MUEs subject tointerference constraints. We denote b as the MBS. For the hybrid overlay/underlay accessscheme in (2.1), we haveI(m)ik =∑j∈F\{i}P(m)jk |h(m)jk |+ P(m)bk |h(m)bk |, (2.3)where the first summation represents the interference from other FAPs in the same sub-23Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networkschannel m, and the second term represents the interference from the MBS transmitting inthe same subchannel m.Using equations (2.1), (2.2), and (2.3), the data rate Rik of FUE k with FAP i as thesource node can be written asRik =∑m∈MR(m)ik . (2.4)Note that the transmission rate of FUE k with FAP i as the source node is the summa-tion of data rates on all used subschannels. For a subchannel m that is not allocated to aFUE k by FAP i, the transmission power P(m)ik and the data rate R(m)ik are both zero. Withthe OFDMA approach, an FAP can communicate with all its FUEs simultaneously. There-fore, we define the data rate of FAP i as the aggregate data rate of all FUEs associatedwith FAP i, which can be represented asRi =∑k∈KiRik=∑k∈Ki∑m∈MηB log2(1 +P(m)ik |h(m)ik |N(m)0 + I(m)ik).When OFDMA is used in the femtocell networks, different FUEs associated with thesame FAP will be allocated orthogonal subchannels and do not interfere with each other.However, there still exist interference from FUEs associated with other FAPs as well asMUEs. One way to reduce such interference is to encourage mobile devices to form coali-tions, such that devices in the same coalition can coordinate and reduce interferences, thusimprove the performance of the network.24Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks2.3 Problem FormulationIn this section, we formulate the subchannel allocation problem in hybrid overlay/underlaycognitive femtocell networks as a coalition formation game. Our goal is to form a stablecoalition structure to maximize the aggregate throughput of femtocell users.2.3.1 Subchannel Allocation Under the HybridOverlay/Underlay Access SchemeAs the spectrum resources available in all cells belong to the same service provider, ourtarget is to perform a centralized subchannel allocation to efficiently utilize the limitedlicensed spectrum. The key idea is to enable FAPs to cooperate with each other, in orderto minimize mutual interferences and increase the aggregate throughput. To achieve this,we will formulate the coalition formation problem, and find the stable and efficient partitionthat maximizes the aggregate throughput for all femtocell users.In CRNs, the roles of PUs and SUs are often predetermined. For the ease of exposition,we consider MUEs as PUs of the network, and the subchannel allocation for MUEs isperformed prior to the coalition formation of FAPs. However, it should be noted thatFUEs have a higher priority than that assumed in [24, 26, 27, 30], since here the femtocellequipment can transmit with the maximum power allowed in the same subchannels asthe macrocell equipment. We then need to establish a subchannel allocation rule forthe cooperative FAPs within the same coalition, so that they can avoid strong mutualinterference. Let us denote MS as the set of available subchannels for the coalition S.For FAP i ∈ S, we denote MFAPi as the set of subchannels allocated to FAP i. Whencoalitions are formed, in order to let each FUE have at least one subchannel, we let FAPi, which is in coalition S, allocate one subchannel to each of its |Ki| FUEs. We design the25Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networkssubchannel allocation as the following two steps. In step 1,MFAPi is computed as follows:MFAPi ={(i− 1)|Ki|+ 1 mod |MS |},...{(i− 1)|Ki|+ l mod |MS |},...{(i− 1)|Ki|+ |Ki| mod |MS |}={MFAPi1 , . . . ,MFAPil , . . . ,MFAPi|Ki|},where i ∈ S. In step 2, in order to avoid allocating subchannel {0} to an FAP, we check andreplace element {0} with {|MS |} inMFAPi as follows: For 1 ≤ l ≤ |Ki|, ifMFAPi⋂{0} 6= ∅and MFAPil = {0}, we set MFAPil = {|MS |}.As an example, consider a coalition S with size |S| = 3, the number of FUEs ineach coalition member FAPs 1, 2, 3: {|K1|,K2|,K3|} = {2, 3, 4}, the available number ofsubchannels for the coalition |MS | = 6, the subchannel allocation decision is MFAP1 ={{1}, {2}}, MFAP2 = {{4}, {5}, {6}}, MFAP3 = {{3}, {4}, {5}, {6}}. From the example,we note that different FAPs might have overlapping subchannel allocations, since∑i∈S |Ki|can be larger than |MS |. This is allowed in the hybrid overlay/underlay cognitive systems,and does not conflict with the goal that the aggregate throughput of SUs is maximizedwhile the SINR levels for PUs are guaranteed.2.3.2 Coalition Formation Game in Partition FormAfter defining the subchannel allocation rules, in this subsection, we introduce the basicelements of games and formulate our coalition formation game as a game in partitionform. In general, a coalition formation game involves a set of players, who attempt toform coalitions, in order to improve their performance or utilities. To specify a coalition26Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networksformation game, we need to specify a set of players and a value which quantifies the benefitsof the game. The definition of the value determines the form (e.g., characteristic form,partition form) and type (e.g., transferable utility (TU), non-transferable utility (NTU)) ofthe game [74].Next, we introduce the elements of the coalition formation game:Players : The set of FAPs F = {1, . . . , F}.Coalition: The set of players S ⊆ F that coordinate their transmissions and subchannelallocations form a coalition S.Partition: Let A(Q) be the set of partition or coalition structure of set Q . For apartition pi ∈ A(Q), we have ∪S∈piS = Q and Sˆ ∩ S˜ = ∅, ∀ Sˆ, S˜ ∈ pi with Sˆ 6= S˜. As anexample, for Q = {1, 2, 3}, pi ∈ A(Q) can be one of the following five coalition structures:{{1}, {2}, {3}},{{1}, {2, 3}},{{2}, {1, 3}},{{3}, {1, 2}}, and{{1, 2, 3}}.Strategy : Each player chooses to join a proper coalition which results in the largestvalue of the game.From the elements of the game above, we note that FUEs are not players. Theyaccept the subchannel allocations from their corresponding FAPs. However, FUEs can beallocated both occupied and unoccupied subchannels. Given a partition pi and FAP i ∈ S,we can compute the interference for FUE k in FAP i from other equipment transmittingin subchannel m as,I(m)ik (S, pi) =∑j∈F\{i}P(m)jk (S, pi)|h(m)jk |+ P(m)bk |h(m)bk |, (2.5)where P(m)jk (S, pi) is the transmission power of FAP j to FUE k on subchannel m underpartition pi. Note that P(m)jk (S, pi) is a function of (S, pi), since the subchannel allocationis based on the coalition and partition as mentioned. The first summation represents theaggregate interference from all other FAPs (j ∈ F\{i}) in the same subchannel m, and the27Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networkssecond term represents the interference from the MBS transmitting in the same subchannelm. Equation (2.5) shows that the interference received by an FUE depends not only onwhich coalition the FUE has joined, but also on how other FAPs form coalitions. Giventhe interference on any subchannel of any FUE in FAP i in coalition S under the partitionpi as shown in (2.5), the aggregate data rate of the users in FAP i isRi(S, pi) =∑k∈Ki∑m∈MFAPiηB log2(1 +P(m)ik (S, pi)|h(m)ik |N(m)0 + I(m)ik (S, pi)). (2.6)Due to the fact that the players are the subscribed users of the wireless service provider,the payoffs of the players are not determined solely by the data rate that they can achieve.The payoff will be reduced if a player acts selfishly and has negative impact on the net-work, such as generating severe interference to other users. Meanwhile, the wireless serviceproviders are the operators of the networks. They can control the payoffs of the usersfrom two aspects. They can physically provide different services to cooperative and non-cooperative users, and financially give rewards and punishment. The users are encouragedto act cooperatively and improve the overall performance of the network. With the consid-erations mentioned above and to be simple, for the cooperative coalition formation game,we define the payoff of player i ∈ S, which is the average data rate allocated to player igiven the partition of the network is pi, i.e.,xi(S, pi) =∑i∈F Ri(S, pi)|F|. (2.7)We note that for any coalition S ⊆ F , the payoff of every player in the coalition dependson the overall partition pi of the network, i.e., on the players in S as well as on the playersin F\S. This is referred to the coalition formation game in partition form [74].28Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks2.3.3 Modified Recursive Core for Coalition Formation Gamewith Negative ExternalitiesNegative externality is often used to characterize the indirect cost imposed by one user onother users when sharing some common resources. In this chapter, the negative externalitycorresponds to the interferences generated by a user to another user. Due to the externality,the proposed game is a coalition formation game in partition form with externalities.In order to solve the above coalition formation game with negative externality, wepropose the solution concept of modified recursive core. The recursive core [75] is animportant solution concept for coalition formation games in partition form consideringexternality5. For any partition pi, that⋃S∈pi S = F , the value of the game equals thesummation of the payoff for all players’ payoffs as follows [31].v(pi) =∑i∈Fxi(S, pi)=∑S∈pi∑i∈Sxi(S, pi).(2.8)Subsequently, we use the recursive core as the solution concept for the game (F , v).The recursive core can be regarded as a generalization of the concept of core for games incharacteristic form, to games in partition form. If the recursive core concept is applied toa coalition formation game in characteristic form, it degenerates to the concept of the core[78].Recursive core is defined recursively using the residual core, which is the core of aresidual game. Therefore, prior to introducing the concept of recursive core, we need tointroduce the concept of a residual game and residual core [75]:5Different from the core or Shapley value, recursive core allows modeling of externalities for games inpartition form.29Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular NetworksDefinition 2.1 Let (F , v) be a coalition formation game. A residual game (R, v) is acoalition formation game in partition form with a set of players R, after the partitions forplayers in F\R have been decided. The players that in F\R are called deviators, while theplayers in R are called residual players.Let a coalition formation game (F , v) have a set of deviators S, and a set of residualplayers R = F\S. The residual game (R, v) is defined as a game in partition based on theset of players R. Once the residual game is defined, it can be solved as an independentgame in partition form, regardless the fact that it is a residual game. In fact, a game inpartition form can be regarded as a group of residual games, and each one of the residualgames can be solved independently. The solution of any residual game is defined as theresidual core as follows [75]:Definition 2.2 The residual core of a residual game (R, v) is a set of possible partitionsof R.Note that if we have F instead of R in Definition 2.2, then the corresponding residualcore becomes the recursive core. Given any coalition formation game (F , v), residual gamesare games with fewer players than the original game and are therefore less complicated.Since a residual core for a residual game of a larger game is also the recursive core for thegame of all the residual players, the criterion that a partition can be formed is the sameas defined in recursive core. Given the coalition formation game (F , v), the outcome as apair which consists the payoff vector and the partition, the recursive core can be found byplaying residual games recursively, which is defined as follows [75].Definition 2.3 The recursive core C(F , v) of a coalition formation game (F , v) is induc-tively defined as follows:30Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks1. One-player Game. The recursive core of a coalition formation game with only playeri is the only outcome and partition C({i}, v) =((v({i})), {i}).2. Inductive Assumption. Suppose that the residual core C(R, v) for all games withat most |F| − 1 players has been defined. Let Ω(R, v) denote a set of all possibleoutcomes of game (R, v). The inductive assumption A(R, v) about the game (R, v)isA(R, v) =C(R, v), if C(R, v) = ∅,Ω(R, v), otherwise.3. Dominance. Define x as the payoff vector of the players and piF as the partition ofthe user set F . The outcome (x, piF) is dominated via the coalition S forming par-tition if for at least one outcome (yF\S , piF\S) ∈ A(F\S, v), there exists an outcome((yS ,yF\S), piS ∪ piF\S) ∈ Ω(F , v) such that (yS ,yF\S) ≻ x.4. Recursive Core. The recursive core of a game of |F| players is the set of undominatedoutcomes denoted by C(F , v).The following statement better explains the concept of dominance in step 3. Given acurrent partition piF and the corresponding payoff vector x, a deviation of the members ofS from piF to piS ∪ piF\S results an outcome ((yS ,yF\S), piS ∪ piF\S), where (yS ,yF\S) ≻ x.This outcome is more rewarding for the players of S, and thus (x, piF) is dominated viathe coalition S.According to the above definition of recursive core, we can obtain the recursive corerecursively. We first start with a one-player game. The only outcome is defined as therecursive core of the one-player game. We then consider a game with more players. Pro-ceeding recursively by considering the inductive assumption, we obtain the undominatedoutcomes as the residual core of each game with at most |F| − 1 players. We obtain the31Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networksrecursive core C(F , v) for the game (F , v) from the residual core of the game with |F| − 1players.Note that based on the different residual cores for the residual games, any possibleoutcome of the original game can be in the recursive core. However, with the process ofsearching residual core and using residual core to reach the final recursive core, we solve thegame with a lower complexity comparing with the exhaustive search method. In addition,since every partition solely determines the payoffs for all the players, the recursive core canbe regarded as a set of partitions that allows the players to organize in a way that achievethe Pareto optimal payoff vectors.The idea of the original recursive core is to find a set of undominated outcomes ofthe (F , v). However, as the objective is to improve the aggregate performance for thenetwork instead of each individual player, for the game of our network, we only need oneundominated outcome which improves the aggregate payoffs of all players. This reduces thecomputational complexity significantly. To do so, instead of searching for the residual core(i.e., a set of undominated outcomes for residual games), we search for one undominatedoutcome that results in the largest value of each residual game and keep the outcome as themodified residual core of each residual game. By recursively finding the modified residualcore of a larger residual game, we obtain the modified recursive core of the original gamein the end.Before introducing the specific process of obtaining modified recursive core, we need todefine a preference relation for each FAP. The definition is as follows:Definition 2.4 For any FAP j ∈ F , we define a preference relation j as a complete,reflexive and transitive binary relation over the set of all coalitions that FAP j can possiblyform.Note that according to the definition of binary relation, a binary relation Z on a set32Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular NetworksT is: (a) complete if ∀t, t′ ∈ T : tZt′ or t′Zt; (b) reflexive if ∀t ∈ T : tZt; (c) transitiveif ∀t, t′, t′′ ∈ T : [tZt′ and t′Zt′′] ⇒ tZt′′. Since we let the FAPs autonomously form thecoalitions, the above definition is used to compare the preference of FAP j over differentcoalition structures (i.e., partitions). For FAP j ∈ F , given two partitions pi1 ⊆ A(F) andpi2 ⊆ A(F), pi1 j pi2 indicates that FAP j prefers joining a coalition to form partition pi1over joining another coalition to form partition pi2, or at least, FAP j has no preference.Moreover, ≻j is defined as a strict transitive binary relation, and pi1 ≻j pi2 indicates thatFAP j strictly prefers to form partition pi1 than partition pi2. We define the operation todecide the preference as follows:pi1 ≻j pi2 ⇔ v(pi1) > v(pi2), (2.9)where pi1 ⊆ A(F) and pi2 ⊆ A(F) are any two partitions that contain FAP j, and the vjis as in (2.8).According to the definitions of the preference relation in (2.9), FAP j ∈ F prefersjoining a new coalition to form a new partition that FAP j has never been a member of, ifand only if such a decision results in a larger value of the game v. It is important to notethat the preference is also rational that the players prefer the strategy which maximizestheir payoffs, since the payoffs of players are proportional to the value of the game accordingto (2.7) and (2.8).Besides a larger value of the game for the new partition, we also need the SINR forall MUEs to be greater than a threshold. The SINR of MUE n on subchannel m can becomputed as follows:SINR(m)n =P(m)bn |h(m)bn |N(m)0 +∑i∈F P(m)in (S, pi)|h(m)in |, (2.10)33Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networkswhere P(m)bn is the transmission power of the MBS on subchannelm, |h(m)bn | is average channelgain of the link between the MBS and MUE n, P(m)in (S, pi) is the transmission power ofFAP i on subchannel m in coalition S under partition pi, |h(m)in | is average channel gainof the link between FAP i and MUE n. We define the switch rule for coalition formationconsidering the SINR constraint of MUEs as follows:Definition 2.5 (Switch Rule) Given a partition pi, and coalitions Si,Sl ∈ pi, FAP j ∈ Siis willing to leave its current coalition Si and join another coalition Sl with i 6= l, if andonly if Sl⋃{j} ≻j Si and SINR(m)n > θ, n ∈ N , m ∈ M, where θ is the threshold accordingto the SINR requirements of MUEs.The switch rule indicates that an FAP is willing to leave its current coalition and joinanother coalition, if and only if the new coalition is strictly preferred over the currentcoalition. According to the switch rule, all the FAPs can make decisions autonomously toform coalitions in the system.In our game, we define the modified recursive core by modifying the third and fourthsteps in the original recursive core in Definition 2.3. In the third step (i.e., dominance),instead of defining the undominated outcome according to the payoff vectors of the players,we use the value of game in (2.8) in the MRC. Specifically, we let each player switchcoalitions according to the switch rule and autonomously join the coalition that results inlarger value of the game v, until the coalition structure converges to the one that resultsin the largest value of the game (and maximum payoff), and no player wishes to leave thecurrent coalition. The outcome of MRC, which results in the largest value of the game, isone of the undominated outcomes in the original recursive core definition. In the fourthstep (i.e., core generation), the MRC is defined as the outcome with the optimal value ofthe game rather than the set of undominated outcomes. Consequently, the achieved MRClies in the original recursive core.34Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks2.3.4 Stability Analysis of the Modified Recursive CoreTo analyze the stability of partition achieved by our method, we next define the stabilityof coalition structure [79, 80]. As in [79], Apt et al. proposed the concept of the defectionfunction D, which is a function that associates with every network partition. By definingDp as a defection function that allows formation of all partitions, one can decide whichcoalition to join given the partition of pi 6.Definition 2.6 A partition pi = {S1,S2, . . . ,SP} is Dp-stable if for all partitions pi′ 6= pi,v(pi) ≥ v(pi′).In other words, a coalition partition pi is Dp-stable if no player has an incentive to movefrom its current coalition to another coalition. Therefore, no player can result in a largervalue of the game by acting according to the switch rule when the current partition isDp-stable.Theorem 2.1 Using the modified recursive core, starting from any initial partition, allthe FUEs will always converge to a final partition pi∗, which is Dp-stable.Proof Suppose the partition pi∗ is not Dp-stable. In other words, we can find a player j ∈ Fthat can act according to the switch rule to achieve a larger value of game. However, dueto the finite number of partitions of a set, the assumption contradicts to the second stepof finding the modified recursive core which no player can leave partition pi∗ to obtain alarger value of game. Therefore, the partition pi∗ is a Dp-stable partition. 6The p represents the defection function is about the formation of all partitions, which is the functionwe need in our definition.35Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks2.4 Algorithm Design based on the ModifiedRecursive CoreIn this section, we propose an MRC algorithm as shown in Algorithm 2.1 to solve thesubchannel allocation problem for the hybrid overlay/underlay cognitive femtocell networkusing coalition formation game described in Section 2.3. It allows each FAP to decidewhich coalition it should join in order to maximize the value of the game (i.e., the aggregatethroughput of all SUs in the network).We start with the recursive core searching process, by considering the initial partitionof the game with all FAPs as singleton coalition (Line 2). Let MMUEn be the set ofsubchannels allocated to MUE n. The initial subchannel allocation allocates each MUE anunoccupied suchannel (Line 3), and allocates all FUEs the same subchannel initially (Line4). We use vector V to record the value of the game for comparison of different iterations,and initialize the value of V (Line 6). Next, we let the players autonomously join potentialcoalition which results in a larger value of the game one by one in each iteration. In theiteration k, different possible coalition structures pi(k) are considered by each FAP. Playeri either joins a coalition S ∈ pi(k−1)∗ formed in the previous iteration, or forms a newcoalition (when S = ∅) (Lines 9 and 10). As an example, in the first iteration where k = 1,player 1 can either stay as a singleton coalition {1} (i.e., the partition pi(1) = pi(0)) or joinone of the coalitions {{2}}, . . . , {{|F|}}. Corresponding to each different partition, thesubchannels MFAPi are allocated according to (2.5) (Line 11). After verifying that theSINR level for all MUEs satisfies the threshold θ (Line 13), we evaluate the value of thegame using (2.8) (Line 14). Next, we record the partition pi(k) that results in the largestvalue of the game v(pi(k)) so far (Lines 16 and 20). We also keep a record of the best valueof the game to verify the convergence (Line 23). Under the condition that the value of36Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular NetworksAlgorithm 2.1: Modified Recursive Core Algorithm for Hybrid Overlay/UnderlayCognitive Femtocell Coalition Formation Game1 Initialize Pi, ∀ i ∈ F , hi,j, ∀ j, i ∈ F , j 6= i, N0, θ2 Set pi(0)∗ := {{1}, {2}, . . . , {|F|}}3 Set {{MMUE1 }, {MMUE2 }, . . . , {MMUE|N | }} := {{1}, {2}, . . . , {|N |}}4 Set {{M(0)FAP1 }, {M(0)FAP2 }, . . . , {M(0)FAP|F| }} :=5 {{{1}, . . . , {1}}, {{1}, . . . , {1}}, . . . , {{1}, . . . , {1}}}6 Set k := 1, V := {V1, V2, . . . , V|F|} := {1, 2, . . . , |F|}7 while V1 6= V|F| do8 for i ∈ F do9 for S ∈ {pi(k−1)∗\{i}} ∪ ∅ do10 Set pi(k) := {pi(k−1)∗\S,S ∪ {i}}11 Update M(k)FAPi according to (2.5)12 Compute SINR(m)n , ∀ m ∈MMUEn , n ∈ N using (2.10)13 if SINR(m)n > θ, ∀ m ∈MMUEn , n ∈ N then14 Determine v(pi(k)) using (2.8)15 if v(pi(k)) > v(pi(k−1)) then16 Set pi(k)∗ := pi(k)17 Set M(k)FAP∗i :=M(k)FAPi18 Set v(pi(k))∗ := v(pi(k))19 else20 Set pi(k)∗ := pi(k−1)21 Set M(k)FAP∗i :=M(k−1)FAPi22 Set v(pi(k))∗ := v(pi(k−1))23 Set Vi := v(pi(k))∗24 Set k := k + 125 Set pi∗ := pi(k−1)∗, MFAP∗i :=M(k−1)FAP∗i , ∀ i ∈ F26 Output: (Modified Recursive Core for the game) Output the stable core ofgame (F , v) consisting of both the final partition pi∗ and subchannel allocationdecision MFAP∗i .game remains the same for the first and |F|-th iteration (Line 7), all the |F| players aresatisfied with the formed coalitions. Therefore we obtain the MRC and the correspondingsubchannel allocation.We now discuss the computational complexity and other practical implementation de-37Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networkstails of our algorithm. Regarding the computational complexity of solving cooperativegames, computing the core is NP-complete in general [81]. Computing the Shapley value issharp-P-complete, which means that it is as hard as any counting problem in NP [82]. Thecomputational cost in finding the modified core [30] using exhaustive search is O(M2KN !),where M,K and N are the number of base stations, number of active users, and numberof subchannels respectively. In our algorithm, the computational cost for each FAP to findthe optimal coalition is O(|F|2), where |F| is the number of the FAPs. Regarding thefrequency of updating the coalition structure, since the FAPs are stationary once installed,it is not necessary to update the coalition structure frequently. Regarding the informa-tion required by the algorithm, the approximated average channel gain can be obtainedaccording to the locations of users, which can be calculated by triangulation methods withnetwork listening and announced to all FAPs by the service provider. The transmissionpower levels for MBS and FAP are fixed and known by all devises. The noise power in thecoverage range of an FAP can be measured locally at each FAP.2.5 Performance EvaluationIn this section, we evaluate the performance of the proposed MRC algorithm throughnumerical simulations. We assume that |F| FAPs are randomly placed in a square regionof l × l m2. The coverage range of each FAP is a disk with radius r. We assume thatthe FUEs can sense the number of available subchannels. Each FAP is responsible forthe downlink communications of all its FUEs concurrently. We will vary the number ofFAPs, MUEs, and subchannels in the network to evaluate the performance of the proposedalgorithm. Unless stated otherwise, we adopt the simulation parameters from a typicalfemtocell setting as summarized in Table 2.2.Using MATLAB as our simulation tool, we repeat the experiment 1000 times using38Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular NetworksTable 2.2: Simulation parameters used in this chapterParameter ValueSubchannel bandwidth B 1 MHzFAP transmission power Pf 20 dBmMBS transmission power Pm 40 dBmTransceiver design efficiency coefficient η 1FAP deployed region l × l 200 m× 200 mFAP coverage radius r 15 mMBS coordinator (−400,−400) mPath loss exponent γ 3SINR threshold for each MUE θ 10 dBMonte Carlo simulations for each network setting, and calculate the average value of theperformance metrics over different network topologies.We first present a sample coalition formation for a cognitive femtocell network deployedwithin a 200×200m2 square region with twelve FAPs and eight MUEs, and each FAP hastwo FUEs. Fig. 2.4 shows the coalition formation result. The blue diamonds and redcircles represent the FAPs and FUEs in the femtocell network, and the green squaresrepresent the MUEs, respectively. FAPs 1 and 4 form a coalition, FAPs 2, 7 and 11 form acoalition, FAPs 6, 10 and 12 form a coalition, FAPs 3, 5, 8 and 9 form singleton coalitions,respectively.To evaluate the performance of the proposed hybrid spectrum access scheme, we im-plement the MRC algorithm for the hybrid spectrum access scheme. We evaluate theaggregate throughput of all femtocell users under different MUE densities [83], and differ-ent FUE densities by varying the number of MUEs |N | and FAPs |F| in the system. Forthe overlay spectrum access scheme, the subchannels are only allocated when there arevacant subchannels in the system. Otherwise, the FUEs will keep waiting until a vacantsubchannel appears. For the underlay spectrum access scheme, each FUE is randomly al-39Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular NetworksFigure 2.4: Snapshot of coalition formation in a cognitive femtocell network for |F| = 12,|N | = 8.located one subchannel under the condition that the SINR of the MUE in that subchannelis greater than the threshold θ. For the hybrid overlay/underlay access scheme withoutMRC, we first allocate vacant subchannels to the FUEs. If all the vacant subchannels areoccupied, we then randomly allocate the occupied subchannels to FUEs, while satisfyingthe SINR requirements of the MUEs in those subchannels. For our proposed hybrid spec-trum access scheme with MRC, when there are vacant subchannels, each FUE is allocateda vacant subchannel. When no vacant subchannel exists, the FAPs form coalitions andallocate subchannels with coordination according to Algorithm 2.1.In Fig. 2.5, we plot the aggregate throughput of FAPs versus the number of FAPsin the network. As shown in Fig. 2.5, the aggregate throughput obtained by our hybridaccess MRC algorithm outperforms the hybrid scheme without MRC, overlay, and underlay40Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks5 8 11 14 17 20 23 263540455055606570Number of FAPsAggregate Throughput of FAPs (Mbit/s) Hybrid Overlay/Underlay with MRCHybrid Overlay/Underlay without MRCUnderlayOverlayFigure 2.5: Aggregate throughput of FAPs versus number of FAPs |F| when |N | = 5,|M| = 9.spectrum access schemes. The aggregate throughput of overlay scheme remains flat, sincethe number of unoccupied subchannels for overlay FAPs remains fixed regardless of thenumber of FAPs. However, the hybrid MRC algorithm continues to improve the aggregatethroughput and outperforms the hybrid scheme without MRC and the underlay scheme.This is because the MRC increases the aggregate throughput by allocating subchannelsin an optimal manner through coalition formation, whereas the hybrid scheme withoutMRC and underlay scheme cannot successfully mitigate the interference among femtocells,especially when the number of FAPs is large. When there are 26 FAPs in the network,the MRC scheme outperforms the hybrid without MRC, underlay, and overlay schemes by15%, 16%, and 72%, respectively.In Fig. 2.6, we show the aggregate throughput of FAPs versus the total number of41Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks1 2 3 4 5 6 7 8 9 10020406080100120140Number of SubchannelsAggregate Throughput of FAPs (Mbit/s) Hybrid Overlay/Underlay with MRCHybrid Overlay/Underlay without MRCUnderlayOverlayFigure 2.6: Aggregate throughput of FAPs versus number of subchannels |M| when |N | =3, |F| = 10.available subchannels, while fixing the number of FAPs in the network at ten. For theoverlay scheme, the aggregate throughput remains zero when all subchannels are occupiedby MUEs, and increases linearly with respect to the number of available subchannels. Forthe hybrid scheme without MRC, when there are no vacant subchannels, it achieves almostthe same performance as the underlay scheme. It outperforms the underlay scheme whenthe number of vacant subchannel increases. This is due to the higher chance for the hybridschemes to allocate a vacant subchannel to an FUE. However, as the hybrid scheme withoutMRC cannot mitigate the interference among femtocells, we can significantly improve theperformance by allowing FAPs to form coalitions according to the MRC algorithm. Whenten subchannels are available, the hybrid scheme with MRC outperforms the hybrid schemewithout MRC, underlay, and overlay schemes by 19%, 35% and 62%, respectively.42Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks0 2 4 6 8 10 122345678910Number of SwitchesUser Throughput (Mbit/s) FUE 1FUE 2FUE 3FUE 4Figure 2.7: Individual throughput of FUE versus the total number of switches when |N | =2, |M| = 4.In Fig. 2.7, we show the throughput of an individual user versus the total number ofswitches (i.e., the number of switch rule executed) under a particular network topology.With two MUEs, four FUEs, and four available subchannels, the throughput of each userconverges after six switches.In Fig. 2.8, we show the average number of iterations versus the number of FAPs, ina network of six subchannels and four active MUEs. The average number of iterationincreases as the number of FAPs increases. With twenty FAPs in the network, the av-erage number of iterations is less than 5.5. This indicates that, on average, each playerswitches less than 5.5 times to join the optimal coalition and the network achieves thestable partition.In Fig. 2.9, we plot the average coalition size versus the number of FAPs, when six43Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks4 6 8 10 12 14 16 18 2033.544.555.5Average Number of IterationsNumber of FAPsFigure 2.8: Average number of iterations to reach the optimal stable partition versus thenumber of FAPs |F| when |N | = 4, |M| = 6.subchannels are available and two to four active MUEs exist. The average size of eachcoalition increases as the number of FAPs increases. This is because more FAPs result ina smaller distance between FAPs on average and a higher possibility of subchannel reuse.The size of each coalition decreases when the number of MUE decreases. It indicates thatwhen more resources become available, FAPs intend to be less cooperative.In Fig. 2.10, we compare the performance of our coalition formation algorithm withthe distributed coalition formation algorithm (DCFA) in [30]. We use the same networkconfiguration to compare the performance of coalition formation algorithm in a fair manner.We plot the aggregate throughput versus the number of FAPs in the network for both MRCalgorithm and DCFA algorithms. Under different numbers of subchannels and differentFAP densities, our MRC algorithm outperforms the DCFA algorithm substantially. With44Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks6 8 10 12 14 16 181.51.61.71.81.922.12.22.3Number of FAPsAverage Size of a Coalition Number of MUEs N = 4Number of MUEs N = 3Number of MUEs N = 2Figure 2.9: Average coalition size of MRC algorithm versus the number of FAPs |F| when|M| = 6.DCFA algorithm, only when the interference is negligible, the achieved modified core andthe corresponding coalition structure will result in an efficient and non-blocking payoffvector of players. When the interference is not negligible, such as in the densely populatedhybrid overlay/underlay systems in this chapter, the coalition structure and subchannelallocation obtained by DCFA may not be the optimal result. The impact of the interferencecan greatly degrade the performance using DCFA. Our MRC algorithm takes the negativeexternality due to interference into consideration when forming coalitions, and resultsin better solutions comparing to DCFA algorithm. With 23 FAPs, two MUEs and sixsubchannels in the network, our MRC algorithm outperforms the DCFA algorithm by18%.45Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networks8 10 12 14 16 18 20 22354045505560657075Number of FAPsAggregate Throughput of FAPs(Mbit/s)MRC with N = 2, M = 8 DCFA with N = 2, M = 8MRC with N = 2, M = 6 DCFA with N = 2, M = 6Figure 2.10: Aggregate throughput of MRC algorithm and DCFA algorithm versus thenumber of FAPs |F|.2.6 SummaryIn this chapter, we studied the resource allocation problem in a two-tier cellular network.Particularly, we developed a hybrid overlay/underlay spectrum sharing mechanism for theFUEs with cognitive capability. We formulated the subchannel allocation problem for thehybrid overlay/underlay cognitive cellular networks as a coalition formation game withnegative externalities. The formulated problem characterizes the interactions and coop-erations among the communication links between the FAPs and the FUEs. An MRCalgorithm is proposed based on the concept of recursive core in coalitional game theory.Simulation results showed that the proposed MRC algorithm achieves a significant im-provement in terms of the aggregate network throughput compared to the overlay scheme,46Chapter 2. Hybrid Cognitive Spectrum Access in Two-Tier Cellular Networksthe underlay scheme, a hybrid overlay/underlay scheme without MRC, and an existingcoalition formation algorithm in the literature.47Chapter 3Multimedia Content Delivery inmmWave based Home Networks3.1 IntroductionIn Chapter 2, we studied the resource allocation problem for a two-tier cellular hetero-geneous network. As a part of future wireless heterogeneous networks, wireless homenetworks facilitate wireless communications among devices inside a home to improve thequality of life of the residents. In this chapter, we study the resource allocation problemfor multimedia content delivery in wireless home networks.Millimeter wave (mmWave) based technology is being regarded as a promising candi-date for multimedia content delivery in home networks in the foreseeable future. However,the studies for multimedia transmission using mmWave is limited. The existing resourceallocation schemes in mmWave networks do not capture the characteristics of various ap-plications in mmWave multimedia home networks. Although optimization framework hasfrequently been used to tackle the resource allocation problem for indoor wireless net-works, there are several differences for the scheduling and power allocation problem usingmmWave. First, the propagation features of mmWave transmission, such as high attenua-tion and sensitivity to blockage, makes it possible to utilize spatial reuse to further improvethe spectrum efficiency. Second, the multiuser interference in directional communicationin mmWave transmission is substantially less than that in omnidirectional systems. Third,48Chapter 3. Multimedia Content Delivery in mmWave based Home Networksthe characteristics of mmWave create the specific constraints for the resource allocation,such as possible channel bonding. Moreover, the existing works do not fully exploit thediversity of frequency division, which can further improve the energy efficiency and channelutilization.It is essential to design a novel scheduling mechanism to better utilize the special fea-tures of mmWave communications (such as wide bandwidth, directional communication,small interfering range), and satisfy the new requirements for various types of multimediacontent delivery (such as high data rate for uncompressed high-definition video transmis-sion and flexible data rate for file downloading). It is also important to consider energyefficiency for growing number of battery-powered portable devices in home networks.In this chapter, we study the scheduling and power allocation problem in the wirelesshome networks based on mmWave technology. We adopt directional antennas for practicalmmWave communications. We consider potential concurrent transmissions in the network,which deliver various types of multimedia content (e.g., uncompressed video). The maincontributions of this chapter are as follows:• We introduce utility functions to characterize different usage scenarios and types ofmultimedia services in the wireless home networks.• We propose a novel integrated TDMA/FDMA/SDMA scheduling scheme that allowsconcurrent transmissions using directional antenna for mmWave home network tofully exploit the potential of spatial reuse and further increase the spectrum efficiency.• We formulate a channel and power allocation problem, which considers QoS andenergy efficiency requirements of users, and maximizes the aggregate network utility.The formulated problem is a non-convex mixed integer programming (MIP) problem.We reformulate the non-convex problem into a convex MIP problem and design analgorithm based on the outer approximation (OA) method to obtain the optimal49Chapter 3. Multimedia Content Delivery in mmWave based Home Networkssolution of the reformulated problem. We further propose a heuristic algorithm,which has a lower computational complexity than the OA based algorithm.• Through extensive numerical studies, we evaluate the performance of our proposedalgorithms in terms of aggregate utility and throughput for different home networks.We further compare both proposed algorithms with recently proposed scheduling al-gorithms [40] and [54]. Results show a substantial improvement in terms of aggregatethroughput and utility compared with the proposed algorithms in [40] and [54].The rest of the chapter is organized as follows: In Section 3.2, we present the systemmodel. We formulate the resource allocation problem in Section 3.3, and propose thescheduling algorithm in Section 3.4. We develop a low complexity heuristic algorithm inSection 3.5. Simulation results are presented in Section 3.6. A summary is given in Section3.7. The key notations and variables used in this chapter are listed in Table 3.1.3.2 System ModelWe consider a wireless home network as shown in Fig. 3.1. The network devices areequipped with mmWave technology. The list of devices includes smart TV, TV set-topbox, laptops, HD projector, and wireless display. The devices are coordinated by the accesspoint via the control links. The multimedia content is delivered via the data links. Eachdata link consists a transmitting device and a receiving device. We denote the set of datalinks by Q, where each data link serves a different pair of users. We assume the multimediacontents, such as videos for wireless display and files to be shared, are available at thetransmitting devices. Short control messages need to be exchanged between the accesspoint and devices for resource allocation purpose. Note that the network setting is similarto the IEEE 802.15.3c and 802.11ad standards, which only allow one radio frequency (RF)50Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksTable 3.1: List of key notations and variables used in this chapterSymbols MeaningB Bandwidth of each channelC Set of available channelsG0 Antenna gain of a pair of communicating devicesGi,j Antenna gain between transmitter i and receiver jht,ci,j Channel gain between transmitter i and receiver j in time slot ton channel cImaxi Estimated maximum interference received by receiver iI t,ci Interference received by receiver i in time slot t on channel cLslot Length of each time slotLsp Length of scheduling periodLa Length of alignment periodLb Length of beacon periodLc Length of control periodN0 Background noise powerpt,ci Transmission power at transmitter i in time slot t on channel cpmax Maximum transmission powerp Power allocation vectorQ Set of data linksV Set of data links with battery-powered transmitting devicesZ Set of data links with minimum data rate requirementri Effective throughput of link iri Effective throughput of link i when interference is limited to Imaxirmini Minimum data rate requirement for link iS1, S2, S3 Usage scenariosT Set of time slotsUi Utility of user iUi Utility of user i when interference is limited to Imaxixt,ci Time slot and channel allocation variable for link i in time slot ton channel cx Time slot and channel allocation vectorη Efficiency of transceiverξ Threshold of energy efficiencyΘ3dB Beam-level beam widthΨst Sector-level beam width for transmitterΨsr Sector-level beam width for receiver51Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksFigure 3.1: An example of a wireless home network. Solid arrows represent the multimediacontent delivery links. Dashed lines illustrate the control message exchange links. Theaccess point also acts as a coordinator to schedule the transmissions among the devicepairs.chain between a pair of transmitter and receiver. If multiple RF chains are required formultimedia content sharing, the spatial gain can be limited by the number of RF chainsthat one device can create.3.2.1 Channel ModelWe consider the mmWave transmissions operate in the frequency band from 57 GHz to 64GHz. This band is used in 802.15.3c [16], 802.11ad [17], and 802.11ay [19]. There are threechannels in this frequency range according to the mmWave band channelization. Eachchannel has a bandwidth of 2160 MHz. The channel model at the 60 GHz band is quitedifferent from that for 2.4 or 5 GHz bands. One important difference is that the 60 GHzcommunication requires directional antenna. We adopt the wireless channel model in the52Chapter 3. Multimedia Content Delivery in mmWave based Home Networks60 GHz indoor situation [51], which is proposed specifically for mmWave communication.Each transmitting antenna distributes the power in the main lobe and several side lobes. Inthis chapter, we consider the large scale channel characterizations. Specifically, we considerthe impact of blockage and reflections for both line-of-sight (LOS) and non-line-of-sight(NLOS) cases. If the LOS is blocked, we consider possible NLOS communications. This isbecause the first order reflection in mmWave networks can be significant [84] and makesNLOS communication possible. The shadowing and multipath effects caused by blockageand reflections of mmWave signals are included in the channel model [51, pp. 7] [52, pp.141]. In the mmWave channel model, the channel gain between the transmitter of link iand receiver of link j (i, j ∈ Q) is represented as hi,j =1PL(di,j), where di,j is the distancebetween the corresponding transmitter and receiver. The path loss is given by [51]PL(d)[dB] =ALOS + 10nLOS log10 (ddbp) +XσLOS + 20 log10(4pifcdbps),if LOS exists,ANLOS + 10nNLOS log10 (ddbp) +XσNLOS + 20 log10(4pifcdbps),if LOS is blocked,(3.1)where ALOS and ANLOS are the attenuation in LOS and NLOS signals, nLOS and nNLOS are thepath loss exponents, and XσLOS and XσNLOS are zero-mean Gaussian random variables withstandard deviation σLOS and σNLOS that model the shadowing effects of LOS and NLOSenvironments, respectively. In addition, fc is the carrier frequency, dbp is the referencedistance, and s is the speed of light. Channel estimation helps to determine the afore-mentioned parameters. It is performed periodically by the transmitter and receiver viatransmitting and analyzing orthogonal pilot sequences [85].In mmWave technology, directional antenna is used to improve the antenna gain. A53Chapter 3. Multimedia Content Delivery in mmWave based Home Networksdirectional transmitting antenna model is proposed in [86]. In this model, the transmittingantenna achieves a high gain in the main lobe and an averaged low gain in the side lobes.The antenna gain in different directions is given as follows [86]:Gtx(Θtx) =Gtx0 10−1.204(Θtx/Θ3dB)2, if 0◦ ≤ Θtx < Θml/2,Gtxsl , if Θml/2 ≤ Θtx ≤ 180◦,(3.2)where Gtx0 and Gtxsl represent the maximum transmitting antenna gain and the average sidelobe gain, respectively. The transmitting angle is denoted as Θtx. Θ3dB is the angle ofthe half-power beam width, and Θml is the angle of the main lobe. In addition, Gtx0 =100.9602−2 ln sin(Θ3dB/2), Gtxsl = 10−0.04111 lnΘ3dB−1.0597, and Θml = 2.6Θ3dB.We consider the network devices are equipped with directional receiving antennas wherethe antenna models are the same as transmitting ones. The receiving antenna gain isdenoted by Grx(Θrx). The receiving angle is denoted as Θrx, which is the angle betweenthe line from the signal source to the receiving antenna and the pointing direction of theantenna. The antenna gain for directional receiving antenna is given as follows:Grx(Θrx) =Grx0 10−1.204(Θrx/Θ3dB)2, if 0◦ ≤ Θrx < Θrr/2,Grxsl , if Θrr/2 ≤ Θrx ≤ 180◦,(3.3)where Grx0 and Grxsl represent the maximum receiving gain and the average side lobe gain,respectively, and Θrr is the angle of receiving range.In Fig. 3.2, we show the transmission pattern using directional transmitting and re-ceiving antennas. The directional beams of transmitters and receivers are shown by theoval-like shapes. Different grids represent the communication in different frequency bands.The antenna gain of each pair of communicating devices is denoted by G0 = Gtx(0)Grx(0).54Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksFigure 3.2: An example of transmission pattern using directional transmitting and receivingantennas. The antenna patterns illustrate gains in different directions. The obstacles havedifferent sizes and are located randomly. Frequency band 1 is allocated to link m to avoidpossible interference with links i and j. Frequency band 2 is allocated to links i and j toimprove spatial reuse.We denote the angle between lines from transmitter j to receivers i and j by Θtxj,i. Simi-larly, we denote the angle between lines from receiver i to transmitters j and i by Θrxj,i. Theantenna gain between transmitter j and receiver i is denoted as Gj,i = Gtx(Θtxj,i)Grx(Θrxj,i).3.2.2 Integrated TDMA/FDMA/SDMA Scheduling forWireless Home NetworksIn home networks, the access point also acts as the coordinator (similar to the piconet co-ordinator in WPAN and personal basic service set central point in WLAN). We propose anintegrated scheduling scheme based on a scheduling period structure. Each scheduling pe-riod begins with a beacon period for network synchronization. It is followed by the control55Chapter 3. Multimedia Content Delivery in mmWave based Home Networksmessage exchanging period. During this period, transmitters can send the transmissionrequest messages and the coordinator broadcasts the scheduling decision. The remain-ing time of the scheduling period is the data transfer interval. The multimedia contentdelivery usually has different QoS requirements. Therefore, QoS-constrained multimediacontent is usually scheduled in the contention-free periods according to the standards. Weassume all multimedia content is transferred using the reservation-based time slots in thedata transfer interval. Each time slot starts with an alignment period, followed by thedata transmission period. In both IEEE 802.15.3c and 802.11ad standards, TDMA is usedduring the reservation-based period, which only allows one transmission pair in a time slot.To further explore the spectral reuse for mmWave technology, we allow co-channel concur-rent transmissions in the same time slot using SDMA. To meet the QoS requirements ofdifferent services, such as wireless display or video gaming, the reservation-based period iscentrally scheduled by the coordinator for each transmission pair.In Fig. 3.3, we illustrate the structure of a scheduling period with the proposed in-tegrated TDMA/FDMA/SDMA scheme. The scheduling period consists of the beacon,control, and data transfer interval. We use Lb, Lc, Lslot, and Lsp to denote the length ofthe beacon period, control period, time slot, and the scheduling period, respectively. Ineach time slot, we use La to represent the duration of the alignment period. Accordingto the standard [17, pp. 300], during the alignment period in data transfer interval, thebeamforming refinement protocol (BRP) is executed for the alignment. Exhaustive searchis used to find the refined beams. We define the sector-level beam width for the transmitterand receiver as Ψst and Ψsr, respectively. We also denote the time required to transmit pilotsequences as Tp. The overhead of the alignment can be modeled as La = ⌈ΨstΘ3dB⌉⌈ ΨsrΘ3dB⌉Tp[87], where ⌈·⌉ is the ceiling function. Note that the beam-level beam width is Θ3dB.In the data transfer interval, each device is allocated different channel and time slot.56Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksFigure 3.3: Structure of the proposed integrated TDMA/FDMA/SDMA scheduling schemefor mmWave home networks.Different from WPAN/WLAN specifications 802.15.3c and 802.11ad, we allow differentdevices to occupy the same frequency band within the same time slot (e.g., users u1 and u4in the first time slot and first frequency band) based on SDMA. FDMA is also integrated inscheduling mechanism by dividing the whole frequency band into three separate channelsaccording to [16]. By integrating FDMA, more flexibility is provided for the schedulingmechanism to improve the channel utilization.The coordinator is responsible for allocating the resource blocks to all links to optimizethe network performance. We denote T as the set of time slots, and C as the set of availablemmWave frequency bands. We further denote pt,ci and ht,ci,i as the transmission power atthe transmitting device of link i and the corresponding channel gain of the link on channelc ∈ C in time slot t ∈ T , respectively. We use pi = (p1,1i , · · · , p1,|C|i , · · · , p|T |,1i , · · · , p|T |,|C|i )to denote the power allocation decision vector for the transmitting device of link i, andp = (p1, · · · ,pi, · · · ,p|Q|) to denote the power allocation vector for all links. The effective57Chapter 3. Multimedia Content Delivery in mmWave based Home Networksthroughput ri for link i can be modeled asri(p) = ηBLslot − LaLsp∑t∈T∑c∈Clog2(1 +pt,ci G0ht,ci,iN0 + It,ci), (3.4)where B is the bandwidth of each channel, η ∈ [0, 1] is the efficiency of the transceiver, andN0 is the noise power. In addition, It,ci =∑j∈Q\{i} pt,cj Gj,iht,cj,i is the received interferencepower of link i on channel c in time slot t.3.2.3 Utility FunctionsUtility is considered as an important metric to efficiently allocate resource blocks to het-erogeneous multimedia traffic. The utility reflects the relative satisfaction level of a userregarding the allocated resources. We define utility functions to characterize the users’experience for different types of multimedia content delivery. We consider the followingusage scenarios for mmWave applications: S1) Uncompressed video streaming: HDTVsignal transmission with adaptive modulation coding; S2) Workstation desktop and con-ference ad-hoc: transmissions between computer devices or in an ad-hoc manner; S3) Kioskfile downloading: video and music sharing on portable devices. Note that although theutility functions are used to model the satisfaction level of users, they are determined bythe coordinator (i.e., not provided by the users themselves) based on the usage scenarios.The purpose is to prevent the users from providing untruthful utilities.We define S1, S2, and S3 as the sets of users that use services under usage scenarios S1,S2 and S3, respectively. Some services in scenarios S1 and S2, such as video streaming orconference ad-hoc, have a minimum data rate requirement. Since each transmission linkserves a corresponding user, we use set Q to represent the set of the users as well as thelinks. In the remaining parts of the chapter, we use the terms link and user interchangeably.We use the following quasi-concave function to characterize the satisfaction level of user58Chapter 3. Multimedia Content Delivery in mmWave based Home Networksi ∈ S1 ∪ S2 with respect to effective throughput:Ui(ri(p)) =0, ri(p) < rmini ,K1i ln(1 +K2i ln(1 + (ri(p)− rmini )), ri(p) ≥ rmini ,(3.5)where coefficients K1i and K2i are application dependent parameters, and rmini is the min-imum data rate requirement for user i under specific usage scenario. The satisfaction ofuser i increases quickly at the beginning when rmini is achieved and then the marginal in-crement becomes smaller as the data rate increases. This type of function is widely usedfor applications with minimum data rate requirement. The services in scenario S3, suchas file downloading, do not have a minimum data rate requirement (i.e., rmini = 0, i ∈ S3).Moreover, the utility increases linearly with respect to the effective throughput. For theseservices, we use the following linear utility function [88] for user i ∈ S3 as follows:Ui(ri(p)) = K3i ri(p), (3.6)whereK3i is an application dependent parameter. Examples of utility functions for differentscenarios are shown in Fig. 3.4.3.3 Problem FormulationThe use of directional antenna can allow more concurrent transmissions. However, only aproper scheduling scheme can fully exploit the potentials of the spatial reuse. Therefore,we propose an integrated TDMA/FDMA/SDMA scheme, which considers spatial reuseof directional antenna and co-channel interference management in order to improve thespectrum efficiency of the home networks.Apart from the benefits, the high power consumption of mmWave communication brings59Chapter 3. Multimedia Content Delivery in mmWave based Home Networks0 1 2 3 4 5 6 7 800.511.522.5Effective Throughput (Gbps)Utility Scenario 1Scenario 2Scenario 3Figure 3.4: An example of utility versus effective throughput for different scenarios.a challenge to the battery-powered devices such as smartphones and tablets. Therefore,energy efficiency becomes a critical challenge for mmWave based systems. We define theenergy efficiency of user i as the ratio between the amount of data transmitted and theenergy consumed, which isLspri(p)(Lslot − La)∑t∈T∑c∈Cpt,ci, (3.7)where (Lslot − La)∑t∈T∑c∈C pt,ci represents the energy consumed by user i to transmitLspri(p) amount of data. We use V ⊂ Q to denote the set of links with battery-poweredtransmitting devices. We consider a threshold of the energy efficiency for these links in setV.To formulate the problem, we define binary variables xt,ci ∈ {0, 1}, t ∈ T , c ∈ C, wherext,ci = 1 if time slot t in channel c is allocated to link i. Otherwise, xt,ci = 0. We also definetime slot and channel allocation vector xi = (x1,1i , · · · , x1,|C|i , · · · , x|T |,1i , · · · , x|T |,|C|i ) for user60Chapter 3. Multimedia Content Delivery in mmWave based Home Networksi, and vector x = (x1, · · · ,xi, · · · ,x|Q|) for all users. We consider the aggregate networkutility as the performance criterion. The optimal resource allocation decision depends onthe allocated resource blocks and the transmission power of the transmitting devices. Wedenote the maximum transmission power as pmax. The threshold of energy efficiency isdenoted by ξ. To find the optimal resource allocation decision, the utility maximizationproblem is formulated as follows:maximizex, p∑i∈QUi (ri(p)) (3.8a)subject to ri(p) ≥ rmini , i ∈ Q, (3.8b)ri(p) ≥ ξLslot − LaLsp∑t∈T∑c∈Cpt,ci , i ∈ V, (3.8c)0 ≤ pt,ci ≤ xt,ci pmax, i ∈ Q, t ∈ T , c ∈ C, (3.8d)∑c∈Cxt,ci ≤ 3, i ∈ Q, t ∈ T , (3.8e)xt,ci ∈ {0, 1}, i ∈ Q, t ∈ T , c ∈ C, (3.8f)where constraint (3.8b) ensures that the minimum throughput requirement is satisfied foreach user. Constraint (3.8c) implies that the ratio between the effective throughput andpower consumption is greater than the minimum threshold ξ. Constraint (3.8d) guaranteesthat the transmission power of link i is not greater than pmax. According to the lateststandardization progress of mmWave networks (i.e., IEEE 802.11ay [19]), channel bondingis considered to allow each transmission pair to use up to three mmWave channels in atime slot. Therefore, we consider constraint (3.8e) to indicate that each link can utilize nomore than three bonded channels during a time slot.Note that the objective function in (3.8a) is non-convex due to the interference term I t,ciin (3.4). Moreover, the time slot and channel allocation variables x are binary. Thus, prob-61Chapter 3. Multimedia Content Delivery in mmWave based Home Networkslem (3.8) is a non-convex MIP problem, which is in general hard to solve. However, we canreformulate the problem and obtain a suboptimal solution. To reformulate problem (3.8),we first evaluate the potential interference received by each link. Due to the directionalcommunication of mmWave networks, multiuser interference is greatly reduced comparedwith omni-directional systems. The mmWave systems show a transitional behavior frominterference-limited to noise-limited regime, depending on several factors such as density oftransmitters and operating beam width [89]. The interference observed by different linksmay be completely different. In this chapter, we estimate the interference for each link byassuming all links transmit in the same channel with maximum transmission power pmax.The estimated interference of link i is denoted as Imaxi . A similar idea is used in [87], whichprovides a conservative estimation of the interference. We defineri (pi) , ηBLslot − LaLsp∑t∈T∑c∈Clog2(1 +pt,ci G0ht,ci,iN0 + Imaxi), (3.9)andUi (pi) ,K1i ln(1 +K2i ln(1 +(ri (pi)− rmini))), i ∈ S1 ∪ S2,K3i ri (pi) , i ∈ S3.(3.10)We then reformulate the non-convex MIP problem into the following minimization problem.minimizex, p−∑i∈QUi (pi) (3.11a)subject to∑j∈Q\{i}pt,cj Gj,iht,cj,i ≤ Imaxi , i ∈ Q, t ∈ T , c ∈ C, (3.11b)ri(pi) ≥ rmini , i ∈ Q, (3.11c)ri(pi) ≥ ξLslot − LaLsp∑t∈T∑c∈Cpt,ci , i ∈ V, (3.11d)62Chapter 3. Multimedia Content Delivery in mmWave based Home Networksconstraints (3.8d)–(3.8f).Problem (3.11) is an MIP problem with convex objective function. Compared with problem(3.8), the new constraint (3.11b) ensures that for each user, the received interference poweris less than the estimated maximum interference. Constraints (3.11c) and (3.11d) aretransformed into convex constraints with a smaller feasible region.3.4 Outer Approximation based Power and ChannelAllocation AlgorithmTo solve problem (3.11), we use the OA method, which is a standard technique to solveconvex MIP problems and provides their optimal solution [90, 91]. The convergence ofOA method has been proven in [90]. The OA method solves the convex MIP problemiteratively. Two problems, namely the subproblem and master problem, are involved ineach iteration. The subproblem is a convex nonlinear programming (NLP) problem andthe master problem is a mixed-integer linear programming (MILP) problem. The NLPsubproblem is obtained from the original convex MIP problem by fixing the value of integervariables. The NLP subproblem provides an upper bound of the optimal value of theoriginal convex MIP problem. The MILP master problem uses the solution of the NLPsubproblem as an input, and provides a lower bound of the optimal value of the originalconvex MIP problem. We iteratively solve the subproblem and master problem until theirsolutions converge.To use the OA method, we first transform problem (3.11) into a standard MIP formatby simplifying the notation. We define63Chapter 3. Multimedia Content Delivery in mmWave based Home Networksf(p) = −∑i∈QUi (pi) ,φt,ci (p) =∑j∈Q\{i}pt,cj Gj,iht,cj,i − Imaxi , i ∈ Q, t ∈ T , c ∈ C,ψ1i (pi) = rmini − ri(pi), i ∈ Q,ψ2i (pi) = ξLslot − LaLsp∑t∈T∑c∈Cpt,ci − ri(pi), i ∈ V.Then, problem (3.11) can be rewritten in the standard form as:minimizex, pf(p) (3.12a)subject to φt,ci (p) ≤ 0, i ∈ Q, t ∈ T , c ∈ C, (3.12b)ψ1i (pi) ≤ 0, i ∈ Q, (3.12c)ψ2i (pi) ≤ 0, i ∈ V, (3.12d)constraints (3.8d)–(3.8f).After transforming the original problem into the standard form, we can formulate theNLP subproblem and MILP master problem in each iteration. We denote k as the indexof each iteration.NLP subproblem (kth iteration)The NLP subproblem is obtained by fixing the value of binary variables x. By doing so,the problem only consists of the continuous variables p. In iteration k, given x(k) as aconstant vector, the NLP subproblem is as follows:minimizepf(p) (3.13a)subject to 0 ≤ pt,ci ≤ xt,c(k)i pmax, i ∈ Q, t ∈ T , c ∈ C, (3.13b)64Chapter 3. Multimedia Content Delivery in mmWave based Home Networksconstraints (3.12b)–(3.12d).Constraint (3.13b) is similar to (3.8d), where xt,c(k)i is given as a constant. In problem(3.13), the objective function and the constraints are all convex. Therefore, it is a convexproblem which can be solved by using convex optimization solvers such as CVX [92]. Wedenote the optimal solution of problem (3.13) by p∗. It is clear that the optimal valuef(p∗) obtained from problem (3.13) is an upper bound of the optimal value of problem(3.12). In order to find a lower bound of the original problem, we formulate the masterproblem.MILP master problem (kth iteration)Both the objective function and the constraints in the master problem are based on outerlinearization [91]. If the value f(p∗) obtained by solving the NLP subproblem is thetightest upper bound among all iterations, we use p∗ as the input p(k) to formulate themaster problem. We introduce ϕ as an auxiliary variable to formulate the MILP problem.The solution of the MILP problem provides a lower bound of the original convex MIPproblem [91, pp. 8]. The MILP master problem in iteration k isminimizex, p, ϕϕ (3.14a)subject to f(p(kˆ)) +∇f(p(kˆ))(p− p(kˆ))T ≤ ϕ, kˆ = 1, ..., k, (3.14b)φt,ci (p(kˆ)) +∇φt,ci (p(kˆ))(p− p(kˆ))T ≤ 0, i ∈ Q, t ∈ T , c ∈ C, kˆ = 1, ..., k,(3.14c)ψ1i (p(kˆ)i ) +∇ψ1i (p(kˆ)i )(pi − p(kˆ)i )T ≤ 0, i ∈ Q, kˆ = 1, ..., k, (3.14d)ψ2i (p(kˆ)i ) +∇ψ2i (p(kˆ)i )(pi − p(kˆ)i )T ≤ 0, i ∈ V, kˆ = 1, ..., k, (3.14e)constraints (3.8d)–(3.8f).65Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksThe gradient vectors in problem (3.14) are as follows:∇f(p(kˆ)) =−ηB(Lslot − La)Lsp ln 2(Ĉ1,11 , · · · , Ĉt,ci , · · · , Ĉ|T |,|C||S1∪S2|, C¯1,11 , · · · , C¯t,cj , · · · , C¯|T |,|C||S3|),(3.15)where Ĉt,ci , i ∈ S1 ∪ S2, t ∈ T , c ∈ C, isĈt,ci =(1 +K2i ln(1 +(ηBLslot − LaLsp∑t∈T∑c∈Clog2(1 +G0ht,ci,ipt,c(kˆ)iN0 + Imaxi)− rmini)))−1(1 +(ηBLslot − LaLsp×∑t∈T∑c∈Clog2(1 +G0ht,ci,ipt,c(kˆ)iN0 + Imaxi)− rmini))−1×K1iK2iG0ht,ci,iN0 + Imaxi +G0ht,ci,ipt,c(kˆ)i,(3.16)and C¯t,cj , j ∈ S3, t ∈ T , c ∈ C, isC¯t,cj =K3jG0ht,cj,jN0 + Imaxj +G0ht,cj,jpt,c(kˆ)j. (3.17)In addition,∇φt,ci (p(kˆ)) = (Gt,c1,iht,c1,i, · · · , Gt,ci−1,iht,ci−1,i, 0, Gt,ci+1,iht,ci+1,i, · · · , Gt,c|Q|,iht,c|Q|,i), (3.18)and∇ψ1i (p(kˆ)i ) =−ηB(Lslot − La)G0Lsp ln 2(C˘1i , · · · , C˘ti , · · · , C˘|T |i), (3.19)where C˘ti , i ∈ Q, t ∈ T , is defined as the tth component in the gradient vector, andC˘ti =(ht,1i,iN0 + Imaxi +G0ht,1i,i pt,1(kˆ)i, · · · ,ht,|C|i,iN0 + Imaxi +G0ht,|C|i,i pt,|C|(kˆ)i). (3.20)66Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksThe gradient vector ∇ψ2i (p(kˆ)i ) is∇ψ2i (p(kˆ)i ) =(C˜1i , · · · , C˜ti , · · · , C˜|T |i), (3.21)in which C˜ti , i ∈ V, t ∈ T , is defined as the tth component in the gradient vector, andC˜ti =Lslot − LaLsp(ξ −ηBG0ht,1i,iln 2(N0 + Imaxi +G0ht,1i,i pt,1(kˆ)i) ,· · · , ξ −ηBG0ht,|C|i,iln 2(N0 + Imaxi +G0ht,|C|i,i pt,|C|(kˆ)i)). (3.22)Note that the MILP master problem can be solved using standard optimization solverssuch as MOSEK [93]. The MILP master problem has more constraints (i.e., the constraintsadded in the kth iteration) compared to the one formulated in the previous iteration asshown in (3.14b)–(3.14e). Therefore, the lower bound of the optimal value of the convexMIP problem, which is obtained by solving the master problem, is tightened in each iter-ation. Similarly, by solving the subproblem and the master problem iteratively, the gapbetween the lower and upper bounds decreases. When the gap is smaller than a threshold,the solution of (3.12) is obtained.The OA based scheduling and power allocation algorithm is shown in Algorithm 3.1.The proposed algorithm contains four steps. In the first step, we initialize the schedulingvariables and power variables, the initial upper bound UB, and the initial lower boundLB, respectively (as shown in Line 1). In the second step, we solve NLP subproblem (3.13)to obtain solution p. We update the current upper bound UB to be the minimum valueof the previous UB and f(p) (as shown in Line 4). We then set the value of p(k) as p (asshown in Line 5). In the third step, we solve MILP master problem (3.14). We update thelower bound by setting it as ϕ and set the value of x(k+1) as x (as shown in Lines 7 and67Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksAlgorithm 3.1: Integrated TDMA/FDMA/SDMA Resource Management based onOA Method1 Initialize x(1), p(0), k := 1, UB := +∞, LB := −∞2 while UB − LB > ε do3 Solve problem (3.13) to obtain solution p4 UB := min(UB, f(p))5 p(k) := p6 Solve problem (3.14) to obtain solution x and optimal value ϕ7 LB := ϕ8 x(k+1) := x9 Set k := k + 110 output Scheduling decision x∗ := x(k) and optimal power p∗ := p(k−1)8). Then, we set k := k + 1. In the fourth step, we evaluate the difference between thecurrent upper bound UB and lower bound LB. If UB − LB ≤ ε, the algorithm returnsthe optimal solution x∗ and p∗. Otherwise, it returns to the second step (Line 3).Compared with the generalized Benders decomposition method used in [69], althoughOA based algorithm has reduced the computational complexity of MIP problem (3.11),the complexity of Algorithm 3.1 is still very high due to the MILP problem in each itera-tion. MILP problems are generally NP-hard [94]. In particular, the worst-case complexityincreases exponentially with the number of binary variables. The worst-case complexity ofeach iteration in the OA based algorithm is O(2|Q||T ||C|), which is the complexity of solvingproblem (3.14) in worst case. Thus, OA based algorithm is too complex for the real-timescheduling.3.5 Greedy Based Heuristic AlgorithmTo overcome the computational complexity of the OA based algorithm, we propose a greedybased heuristic channel and power allocation algorithm in this section. The proposedheuristic greedy algorithm is shown in Algorithm 3.2. In this algorithm, Z denotes the68Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksAlgorithm 3.2: Integrated TDMA/FDMA/SDMA Resource Management based onGreedy Algorithm1 Initialize pi := (pmax, . . . , pmax), i ∈ Q, xt,ci := 0, i ∈ Q, t ∈ T , c ∈ C2 while Z 6= ∅ do3 W :={(i, t, c) ∈ {Z, T , C} | xt,ci = 0,∑j∈Z\{i}pmaxGj,iht,cj,i ≤ Imaxi ,∑c∈Cxt,ci ≤ 3}4 if W 6= ∅ then5 Sort ∆ri(xi, xt,ci ), (i, t, c) ∈ W in a non-increasing order6 Select the first element of the sorted list and record i, t, c7 Set xt,ci := 18 if ri(pi) ≥ rmini then9 Z := Z \ {i}10 else11 Return infeasible12 do13 W˜ :={(i, t, c) ∈ {Q, T , C} | xt,ci = 0,∑j∈Q\{i}pmaxGj,iht,cj,i ≤ Imaxi ,∑c∈Cxt,ci ≤ 3,∆Ui(xi, xt,ci ) > 0}14 if W˜ 6= ∅ then15 Sort ∆Ui(xi, xt,ci ), (i, t, c) ∈ W˜ in a non-increasing order16 Select the first element of the sorted list and record i, t, c17 Set xt,ci := 118 while W˜ 6= ∅19 Given Q,V, and x¯∗ = (xt,ci )i∈Q,t∈T ,c∈C, solve problem (3.23) to obtain p¯∗ as thepower allocation20 output Channel and power allocation decision x¯∗ and p¯∗subset of links which require a minimum data rate. In the algorithm, we consider eachtime slot in a certain channel as a resource block (RB). We denote ∆ri(xi, xt,ci ) as theestimated potential rate increment for link i if time slot t in channel c is allocated to it andmaximum transmission power pmax is used. We also define ∆Ui(xi, xt,ci ) as the estimatedpotential utility increment for link i.69Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksThe proposed algorithm separates the channel allocation and power allocation, whichcan reduce the computational complexity. There are three major steps in the algorithm.In the first step, we allocate the RBs to guarantee the minimum data rate requirementsof the links, assuming the maximum power is used at the transmitting devices (Lines 2 to11). Due to the directional communication, an RB can be shared by different links if theSINR requirements of all links are satisfied. Therefore, we find the link with the largestestimated rate increment and allocate the corresponding RB slot to that link (Lines 5 to7). Specifically, we form set W of indexes i, t, and c, subject to the conditions that RBt, c has not been allocated to link i, the interference requirement will be satisfied if RB t, cis allocated to this link, and no other channel is allocated in the same time slot (Line 3).Then, we sort the potential rate increment for different links and RBs in a non-increasingorder (Line 5), and record i, t, c corresponding to the largest element of the sorted list (Line6). In the second step, we allocate the RBs to all links by considering the utility increment(Lines 12 to 18). In each iteration, we allocate an RB to that link which results in thelargest estimated network utility increment (Lines 14 to 17). The selection of the RBsand the links should also satisfy the constraint that a link cannot utilize multiple channelssimultaneously. The second step terminates when W˜ = ∅. Now, we have allocated thechannels and obtained channel allocation result x. In the third step, we obtain the powerof each transmitter by solving the following problem based on the obtained x. The powerallocation problem is as follows:maximizep∑i∈QUi (pi) (3.23a)subject to ri(pi) ≥ rmini , i ∈ Q, (3.23b)ri(pi) ≥ ξLslot − LaLsp∑t∈T∑c∈Cpt,ci , i ∈ V, (3.23c)70Chapter 3. Multimedia Content Delivery in mmWave based Home Networks0 ≤ pt,ci ≤ xt,ci pmax, i ∈ Q, t ∈ T , c ∈ C. (3.23d)Problem (3.23) is a convex optimization problem and can be solved by using convex opti-mization solvers. The optimal solution of this problem is denoted by p¯∗. Finally, Algorithm3.2 returns the channel and power allocation decision (Line 20).In the following, we provide the complexity analysis of the greedy algorithm. In the firststep of the algorithm from Lines 1 to 11, the number of iterations mainly depends on thesize of set W. Given |W|, the complexity of sorting in Line 5 is O (|W| log(|W|)), which isO (|Z||T ||C| log(|Z||T ||C|)) in worst case. Since the time required for executing the lines inthe first step except Line 5 is constant, and the number of iterations executing the first stepis O(|W|), the complexity of the first step is O (|W|2 log(|W|)). Similarly, the complexity ofthe second step (Lines 12 to 18) is O(|W˜|2 log(|W˜|)). Note that the convex problem (3.23)can be solved in polynomial time. Due to the fact that Z ⊆ Q and |W˜| ≥ |W|, the overallcomplexity of the algorithm is O(|W˜|2 log(|W˜|)), i.e., O ((|Q||T ||C|)2 log(|Q||T ||C|)). Itcan be seen that the complexity of the greedy algorithm is reduced compared to the OAbased algorithm, which significantly improves its applicability for the real-time scheduling.3.6 Performance EvaluationIn this section, we evaluate the performance of the proposed OA based and the greedyalgorithms. We further compare both of the proposed algorithms with scalable heuristicSTDMA scheduling (SHSS) algorithm [40] and vertex multi-coloring concurrent transmis-sion (VMCCT) algorithm [54]. This is because [40] and [54] also focus on the spatial reuse inindoor mmWave networks. The key differences between our algorithms and the algorithmproposed in [40] and [54] are that we further utilize mmWave channelization and propose anOA based scheduling algorithm to maximize the aggregate utility for multimedia content71Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksTable 3.2: Simulation parameters used in this chapterParameter ValueFrequency band 57.05 - 64.00 GHzBandwidth of each channel B 2.160 GHzNoise power spectrum density N0/B −174 dBm/HzMaximum transmission power pmax 10 dBmCarrier frequency fc1, fc2, fc3 58.32, 60.48, 62.64 GHzPath loss reference distance dbp 1 mAttenuation of signals ALOS, ANLOS 7.1, 18 dBPath loss exponent nLOS, nNLOS 2.0, 2.5Shadowing standard deviation σLOS, σNLOS 1.5, 3.4Length of scheduling period Lsp 65 msLength of beacon period Lb 0.3 msLength of control period Lc 5 msPilots transmission duration Tp 655 nsSector level beam width Ψsr, Ψst 90odelivery in mmWave networks. We consider the transmitting devices are randomly locatedin the home with a uniform distribution. The receiving devices are randomly located withan average distance of 2 m around the transmitting devices. A random number of trans-mitting devices operate on battery. Their links form set V. The service requested by eachlink is randomly selected from S1, S2, and S3. The parameters for the utility function areK1i = 1, K2i = 0.7, rmini = 0.95 Gbps, i ∈ S1; K1i = 1.5, K2i = 1, rmini = 1.54 Gbps, i ∈ S2;and K3i = 0.15, i ∈ S3 [16]. The energy efficiency threshold ξ is 105 bit/joule [95]. Thelength of each time slot Lslot is (Lsp−Lb−Lc)/|T |. Note that the number of time slots isequal to the number of links in the network7. Other simulation parameters are summarized7According to the IEEE 802.15.3c and 802.11ad standards, the duration of a time slot can vary [51, pp.26][17, pp. 151, 178]. The duration of a time slot is determined based on transmission requests of activelinks. In our system, we assume all devices are active during the scheduling period and the total numberof time slots is equal to the number of links. Since the duration of data transfer interval is the product ofthe duration of each time slot and the number of time slots, the duration of a time slot depends on thenumber of active links in the network.72Chapter 3. Multimedia Content Delivery in mmWave based Home Networks2 4 6 8 10 12 14 160102030405060Number of linksAggregate Throughput (Gbps) OA based AlgorithmGreedy AlgorithmVMCCT AlgorithmSHSS AlgorithmFigure 3.5: Aggregate throughput versus number of links with the home area of 10 m ×10 m and Θ3dB = 15o.in Table 3.2 [16, 17, 51]. We repeat the experiment using Monte Carlo simulations for eachnetwork setting, and calculate the average value of the performance metrics over differentnetwork settings.We first compare the performance of our proposed algorithms with SHSS and VMCCTalgorithms. Since SHSS and VMCCT algorithms aim to improve the throughput of thenetwork using spatial reuse, we compare the algorithms in terms of throughput. In Fig. 3.5,we plot the aggregate throughput of the proposed OA based, greedy, SHSS, and VMCCTalgorithms for different number of links in the network. Note that each link represents a pairof devices. Although the proposed algorithms aim to increase the network utility, they bothachieve a higher aggregate throughput compared to the SHSS and VMCCT algorithms.This is because SHSS algorithm randomly selects the concurrent transmitting devices basedon aggregate interference. However, we improve the spatial reuse by allocating the channels73Chapter 3. Multimedia Content Delivery in mmWave based Home Networks0 10 20 30 40 50 60051015202530354045Half Power Beam Width Θ3dB ( o )Aggregate Throughput (Gbps) OA based AlgorithmGreedy AlgorithmVMCCT AlgorithmSHSS AlgorithmFigure 3.6: Aggregate throughput versus half power beam width with the home area of 10m × 10 m. The number of links |Q| = 10.while considering the throughput and utility increment of each link. Moreover, VMCCTalgorithm has a fixed exclusive region to forbid concurrent transmissions while we considerall possible concurrent transmissions to improve the spatial reuse.In Fig. 3.6, we compare the aggregate throughput of our proposed algorithms withSHSS and VMCCT algorithms for different half power beam width Θ3dB to show the impactof alignment overhead. When the beam width is very narrow, the alignment overhead isdominant and reduces the overall throughput. However, OA based and greedy algorithmsalways outperform SHSS and VMCCT algorithms.We now evaluate the aggregate utility of OA based, greedy, SHSS, and VMCCT algo-rithms for different number of links in the network. As shown in Fig. 3.7, the aggregateutility of greedy algorithm is close to the OA based algorithm. Greedy algorithm achievesat least 90% of the aggregate utility of the OA based algorithm and outperforms VMCCT74Chapter 3. Multimedia Content Delivery in mmWave based Home Networks2 4 6 8 10 12 14 16051015Number of LinksAggregate Utility OA based Algorithm with Home Area = 144 m2OA based Algorithm with Home Area = 100 m2Greedy Algorithm with Home Area = 144 m2Greedy Algorithm with Home Area = 100 m2VMCCT Algorithm with Home Area = 144 m2VMCCT Algorithm with Home Area = 100 m2SHSS Algorithm with Home Area = 144 m2SHSS Algorithm with Home Area = 100 m2Figure 3.7: Aggregate utility versus number of links with the home area of 10 m × 10 mand Θ3dB = 15o.and SHSS algorithms by 22% and 39%, respectively, when the number of links is 16 andhome area is 100 m2. We also evaluate the aggregate utility of the proposed greedy al-gorithm for different home sizes. We compare the results for two different home sizes of144 m2 and 100 m2, respectively. As shown in this figure, a larger home size results in aslightly higher aggregate utility. This is due to the longer distance between the interferingdevices in a larger home area. The highest utility is achieved with home area of 144 m2with 16 links, which is close to the case of 100 m2. Therefore, the proposed algorithmsperform well in homes of different sizes.In Fig. 3.8, we compare the performance of the proposed OA based, greedy, SHSS,and VMCCT algorithms when there is only one usage scenario in the network. Fig. 3.8shows the aggregate network utility for three types of usage scenarios, where we fix thenumber of links to be 10. It is shown that the greedy algorithm achieves at least 90% of75Chapter 3. Multimedia Content Delivery in mmWave based Home NetworksS1 S2 S305101520 Usage ScenarioAggregate UtilityOA based AlgorithmGreedy Algorithm VMCCT AlgorithmSHSS AlgorithmFigure 3.8: Aggregate utility versus usage scenarios with the home area of 10 m × 10 m.The number of links |Q| = 10.the aggregate utility compared to the OA based algorithm in different scenarios. In usagescenario S3, the aggregate utility of OA based and greedy algorithms is close to each other.This shows when the minimum data rate requirement is zero and the utility is a linearfunction of the effective throughput for scenario S3, the greedy algorithm is more likelyto approach the optimal solution. Both OA based and greedy algorithms outperform theSHSS and VMCCT algorithms. Although the aggregate utility obtained by the OA basedalgorithm is slightly higher than greedy algorithm, we later present that the running timeof the greedy algorithm is much less than the OA based algorithm.3.7 SummaryIn this chapter, we investigated the resource management problem for multimedia contentdelivery in mmWave based wireless home networks. Specifically, we introduced different76Chapter 3. Multimedia Content Delivery in mmWave based Home Networksutility functions, which characterize different usage scenarios and types of multimedia ser-vices in the network. We formulated a non-convex MIP optimization problem to maximizethe aggregate network utility. The formulated problem considered possible concurrenttransmissions in mmWave home network, and QoS and energy efficiency requirements ofusers. We reformulated the problem into a convex MIP problem. We then designed an OAbased algorithm to find the optimal solution of the reformulated problem. Furthermore, weproposed a greedy algorithm with a substantially lower computational complexity. Sim-ulation results showed that both of the proposed algorithms have significant performanceimprovement compared to existing algorithms in the literature.77Chapter 4Full-duplex Relay-assisted D2DCommunication in 5G Networks4.1 IntroductionIn Chapters 2 and 3, we studied the resource allocation problems in candidate networks ofthe future heterogeneous wireless communication systems. Device-to-device (D2D) com-munication enabled heterogeneous networks, which are regarded to be promising for 5Gwireless communication systems, allow mobile devices to communicate with each otherdirectly. However, potentials of D2D communication enabled wireless networks have notbeen fully exploited.In this chapter, we study relay-assisted D2D communication for 5G wireless commu-nication systems, where mobile devices transmit using directional antennas in mmWavefrequency band. We consider the relays have full-duplex capability and can assist de-vice discovery, connection establishment, and data transmission for the potential D2Dcommunication. We also consider the practical case of full-duplex relays, where the self-interference cannot be fully eliminated due to imperfect self channel estimation and hard-ware constraints.The main contributions of this chapter are summarized as follows:• Full-duplex relaying in D2D communication: We design a joint relay selection and78Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networkspower allocation scheme for full-duplex relay-assisted D2D communication in mmWavebased wireless networks. We formulate a multi-objective combinatorial optimiza-tion problem, which considers the impact of self-interference in full-duplex relayingsystems. The formulated problem aims to reduce the total transmission power andimprove the system throughput while satisfying certain QoS and physical constraints.• Low complexity Pareto optimal algorithm based on matching theory : We transformthe problem into a one-to-one weighted bipartite matching problem, which can besolved optimally in polynomial time. We further propose an algorithm to solve thematching problem optimally in polynomial time. We also prove that the proposedalgorithm can achieve a Pareto optimal solution of the multi-objective optimizationproblem.• Enhanced performance: Through extensive numerical studies, we evaluate the per-formance of our proposed algorithm under different network settings and compare itwith an existing algorithm proposed in [71]. Simulation results illustrate the trade-off between power consumption and system throughput. They also show that ourproposed algorithm improves the power consumption and system throughput by upto 48% and 18%, respectively, compared to the algorithm from [71].This chapter is organized as follows. In Section 4.2, we present the system model.In Section 4.3, we formulate the joint relay selection and power allocation problem andtransform the problem into a one-to-one weighted matching problem. We also propose analgorithm that achieves a Pareto optimal solution of the formulated problem. Simulationresults are presented in Section 4.4. A summary is given in Section 4.5. The key notationsand variables used in this chapter are listed in Table 4.1.79Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G NetworksTable 4.1: List of key notations and variables used in this chapterSymbols MeaningB Bandwidth of each channelCli,rj Throughput of D2D user pair li assisted by relay rjCminli Minimum throughput requirement for D2D user pair liD Set of destination devicesE Set of edgesF A matchingG Bipartite graphhi,j Channel gain between transmitter i and receiver jhLI Loop-interference gainL Set of source-destination user pairsL(z) Path loss functionN0 Background noise powerNrj Number of channels that relay rj can usePsi,rj Transmission power of source device si to relay rjPrj ,di Transmission power of relay rj to destination device diPmaxr Maximum transmission power of each relayPmaxs Maximum transmission power of a source devicePs Transmission power matrix of source devicesR Set of relaysRv Set of virtual relaysS Set of source deviceswli,rj Weight of edge (li, rj)W Weighting matrix of the edgesxli,rj Relay selection indicator for user pair li and relay rjX Relay selection matrixλ1 Non-negative coefficient for power consumptionλ2 Non-negative coefficient for system throughput4.2 System ModelWe study an mmWave cellular network with full-duplex relay-assisted D2D communicationas shown in Fig. 4.1. The service provider has incentives to deploy relays to facilitate D2D80Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G NetworksDirectional beamD2D userCellular base stationFull-duplex relayFigure 4.1: An mmWave based D2D network with full-duplex relays and directional trans-missions. D2D user pairs can choose whether or not to use full-duplex relays. The basestation coordinates the resource allocation in the network.communication and offload data from the base station. Full-duplex relays are deployed toassist D2D users8 who either suffer from poor direct link quality or require an extendedcommunication range. The cellular base station sends short control messages to D2D usersand relays to coordinate the resource allocation process. We denote the set of relays asR. The sets of source and destination devices which are assisted by relays are denoted asS and D, respectively, where S⋂D = ∅. We further denote the set of source-destinationD2D user pairs as L. The ith source device si ∈ S and the ith destination device di ∈ Dform a source-destination user pair li = (si, di) ∈ L.We assume that the base station, D2D users, and relays are with the same serviceprovider. The relays which assist D2D user pairs share parts of the channel resources thatthe service provider owns, while those users that do not require assistance from relays usedifferent spectral resources. A relay can assist multiple D2D communication pairs usingdifferent channels. Each relay is equipped with two sets of antennas that enable full-duplexoperation. Decode-and-forward protocol is employed by the relays. The D2D user pairs8In the remaining parts of this chapter, we use the terms “device” and “user” interchangeably.81Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networkscommunicate based on OFDMA, so that each D2D user pair is allocated a non-overlappingchannel.4.2.1 Channel ModelA promising mmWave frequency band that has been considered for future cellular system isthe 38 GHz band [11, 96]. This band is selected based on several factors, such as the signalpropagation feature and licensing issue. The channel model of mmWave communicationis different from the current cellular channel model. One important difference is thatmmWave communications require directional antennas. In this chapter, we consider acellular system that operates on the frequency of 38 GHz and adopt the channel modelintroduced in [97]. This model is proposed for mmWave cellular systems. Specifically,we consider the impact of blockage and reflections for both LOS and NLOS cases. If theLOS is blocked, we consider potential NLOS communications due to reflections [98]. Letz denote the distance between the transmitter and receiver. The path loss function L(z)in dB isL(z) =LLOS(z0) + 10αLOS log(z) + ZσLOS, if LOS exists,LNLOS(z0) + 10αNLOS log(z) + ZσNLOS, if LOS is blocked,(4.1)where LLOS(z0) and LNLOS(z0) are the free-space path loss at reference distance z0 for LOSand NLOS signals, respectively. Moreover, αLOS and αNLOS are the path loss exponents forLOS and NLOS cases, and ZσLOS and ZσNLOS are zero-mean Gaussian random variables withstandard deviations σLOS and σNLOS that model the shadowing effects of LOS and NLOSenvironments, respectively. Channel estimation is used to determine the aforementionedparameters. The transmitter and receiver perform channel estimation periodically viatransmitting and analyzing orthogonal pilot sequences [85].82Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G NetworksIn mmWave technology, directional antenna is used to improve the antenna gain. Asectored directional transmitting antenna model is proposed in [99]. We use this sectoredantenna model, where the antennas achieve a constant high gain in the main lobe and aconstant low gain in the side lobe. Let Θt represent the angle of departure of signals. Thetransmitting antenna gain is given as follows:Gt(Θt) =M t, 0◦ ≤ Θt ≤ ΘtHPBW,mt, ΘtHPBW < Θt ≤ 180◦,(4.2)whereM t, mt, and ΘtHPBW are the main lobe gain, side lobe gain, and half power beamwidthfor the transmitting antenna, respectively. Similarly, let Θr represent the angle of arrivalof signals. The receiving antenna gain is given as follows:Gr(Θr) =M r, 0◦ ≤ Θr ≤ ΘrHPBW,mr, ΘrHPBW < Θr ≤ 180◦,(4.3)whereM r, mr, and ΘrHPBW are the main lobe gain, side lobe gain, and half power beamwidthfor the receiving antenna, respectively. The antenna gain between devices i and j is denotedas Gi,j = Gt(Θti,j)Gr(Θrj,i), where Θti,j is the angle of departure of signal from transmitter ito receiver j, and Θrj,i is the angle of arrival of signal in receiver j sent from transmitter i.Note that if i and j belong to a pair of communicating devices, Θti,j and Θrj,i are both 0o,since we assume the transmitting and receiving antennas are accurately aligned. The totalgain (including channel and antenna gains) between devices i and j can be represented ashi,j = Gi,j/L(zi,j), where zi,j is the distance between the corresponding devices.83Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks4.2.2 Throughput of a User PairThroughput is an important performance metric in D2D communication. Different appli-cations have different throughput requirements. To obtain the throughput of a user pair,we need to determine the signal-to-interference plus noise ratio (SINR) in each hop of therelayed communication. For user pair li = (si, di) which is assisted by relay rj , we denotePsi,rj as the transmission power of source device si to relay rj. We further denote thetransmission power of relay rj to destination device di as Prj ,di . Then, the SINR fromsource si to relay rj isSINRsi,rj =hsi,rjPsi,rjhLIPrj ,di +N0, (4.4)where hLIPrj ,di represents the self-interference received by full-duplex relay rj, hLI is theloop-interference gain for the full-duplex relay, and N0 is the noise power. Note that themutual interference among different user pairs is avoided since each user pair is allocatedan orthogonal channel. Similarly, the SINR from relay rj to destination device di isSINRrj ,di =hrj ,diPrj ,dihsi,diPsi,rj +N0, (4.5)where hsi,diPsi,rj is the interference induced by source device si. In a full-duplex relayingsystem using decode-and-forward protocol, the throughput of user pair li ∈ L assisted byrelay rj ∈ R can be obtained from [100]:Bmin(log2(1 + SINRsi,rj), log2(1 + SINRrj ,di)), (4.6)where B is the bandwidth of each channel.84Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks4.3 Problem FormulationIn this section, we formulate a joint relay selection and power allocation problem by tak-ing both the power consumption and the system throughput into consideration. This ismotivated from the fact that the limited battery capacity of mobile devices requires a lowpower consumption, while applications such as video sharing require a high throughputdata transmission. Our objective is to minimize the power consumption and simultane-ously maximize the system throughput of the D2D network. We formulate the problemas a multi-objective optimization problem to consider both of the aforementioned factors.To do so, we consider the impact of self-interference in full-duplex relaying systems andderive a closed-form expression of the throughput of a user pair. Note that for full-duplexrelays, a higher transmission power of a relay increases the received power in the destina-tion device of D2D user pairs. However, it also induces a higher self-interference at thesame time. This means that transmitting with full power does not necessarily increasethe throughput. According to (4.6), the throughput of a user pair assisted by a relayis the minimum throughput of the source-to-relay and relay-to-destination links. Thus,the transmission power of the source device is wasted if the source-to-relay throughputis greater than the relay-to-destination throughput. The same situation holds regardingthe transmission power of the relays. In other words, the power of a full-duplex relaycan be adjusted according to the allocated transmission power of the source devices. Thesource-to-relay throughput should be equal to the relay-to-destination throughput in orderto save power consumption [101, 102]. This helps us to obtain a closed-form expression forthe source-to-destination throughput. Consider D2D user pair li = (si, di) ∈ L and relayrj ∈ R, the above condition implies that SINRsi,rj = SINRrj ,di. In this case, from (4.4)85Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networksand (4.5), Prj ,di can be expressed as a function of Psi,rj as follows:Prj ,di(Psi,rj) =√4hsi,rjhLIhrj ,dihsi,diP2si,rj+ 4N0hsi,rjhLIhrj ,diPsi,rj +N20h2rj ,di−N0hrj ,di2hLIhrj ,di.(4.7)Therefore, the throughput of user pair li ∈ L assisted by relay rj ∈ R can be expressed asfollows when we substitute (4.5) and (4.7) into (4.6):Cli,rj(Psi,rj) = B log2(1 +hrj ,diPrj ,di(Psi,rj)hsi,diPsi,rj +N0). (4.8)To introduce our objectives, we consider the power consumption of mobile devices.Since the relays are plugged into the power source and have sufficient power supply, theobjective is to minimize the total transmission power of the transmitting D2D devicesby selecting relays efficiently. We denote Ps = (Psi,rj)si∈S,rj∈R as the transmission powermatrix. The total transmission power can be represented as:f1(Ps) =∑si∈S∑rj∈RPsi,rj . (4.9)Another important design objective is to maximize the system throughput. Maximizingthe system throughput is equivalent to minimizing the following function:f2(Ps) = −∑li∈L∑rj∈RCli,rj(Psi,rj). (4.10)The design objectives in (4.9) and (4.10) are both important for the system. A single-objective formulation that solely considers either (4.9) or (4.10) is insufficient to capture thecomplete design goals of the system. However, these objectives are conflicting in the sensethat a higher throughput may result in a higher power consumption. This fact motivates86Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networksus to formulate a multi-objective problem, which considers both objectives simultaneously.To formulate the multi-objective optimization problem, we introduce the QoS require-ments for different applications as well as the physical constraints of the devices and relays.We denote Cminli as the minimum throughput requirement for D2D user pair li. To guar-antee that the minimum data rate requirement is satisfied for each D2D user pair, weintroduce the following constraint:∑rj∈RCli,rj(Psi,rj) ≥ Cminli, ∀ li = (si, di) ∈ L. (4.11)We define matrix X = (xli,rj)li∈L,rj∈R to indicate the relay selection for the user pairs,where binary variable xli,rj = 1 if user pair li selects relay rj. Otherwise, xli,rj = 0. Then,the following constraint ensures that each user pair can be assisted by only one relay:∑rj∈Rxli,rj = 1, ∀ li ∈ L. (4.12)Furthermore, the number of D2D user pairs assisted by relay rj should be less than orequal to the number of channels that rj can use. We denote Nrj as the number of channelsin relay rj . Then, this constraint is ensured via the following inequality:∑li∈Lxli,rj ≤ Nrj , ∀ rj ∈ R. (4.13)We denote Pmaxs as the maximum transmission power of each mobile device, and Pmaxr asthe maximum transmission power of each relay. To incorporate the physical constraints formobile devices and relays such that their transmission powers do not exceed the maximum87Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networkstransmission power allowed, we introduce the following constraints:0 ≤ Psi,rj ≤ xli,rjPmaxs , ∀ li = (si, di) ∈ L, rj ∈ R, (4.14)0 ≤ Prj ,di(Psi,rj) ≤ xli,rjPmaxr , ∀ li = (si, di) ∈ L, rj ∈ R. (4.15)Notice that since Psi,rj ≥ 0, Prj ,di(Psi,rj ) is always non-negative. Let P−1rj ,di(·) denote theinverse of function Prj ,di(Psi,rj). Since Prj ,di(Psi,rj), given in (4.7), is strictly increasing, theinverse function always exists. Thus, from (4.15), we have0 ≤ Psi,rj ≤ P−1rj ,di(xli,rjPmaxr ), ∀ li = (si, di) ∈ L, rj ∈ R. (4.16)When xli,rj = 1, P−1rj ,di(xli,rjPmaxr ) = P−1rj ,di(Pmaxr ), while Psi,rj = 0 when xli,rj = 0. There-fore, inequality (4.16) can be rewritten as:0 ≤ Psi,rj ≤ xli,rjP−1rj ,di(Pmaxr ), ∀ li = (si, di) ∈ L, rj ∈ R. (4.17)Consequently, constraint (4.15) can be converted into the following equivalent constraint:0 ≤ Psi,rj ≤xli,rj P˜maxs , ∀ li = (si, di) ∈ L, rj ∈ R, (4.18)where constantP˜maxs = P−1rj ,di(Pmaxr )=√4hsi,rjhLIhrj ,dihsi,di(Pmaxr )2 + 4N0hsi,rjhrj ,dihsi,diPmaxr +N20h2si,rj−N0hsi,rj2hsi,rjhsi,di.(4.19)88Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G NetworksBy combining (4.14) and (4.18), we have0 ≤ Psi,rj ≤ xli,rj min(Pmaxs , P˜maxs), ∀ li = (si, di) ∈ L, rj ∈ R. (4.20)Then, the multi-objective relay selection and power allocation problem can be formulatedas:minimizeX,PsF (Ps) =(f1(Ps), f2(Ps))T(4.21a)subject to xli,rj ∈ {0, 1}, ∀ li ∈ L, rj ∈ R, (4.21b)constraints (4.11)− (4.13), and (4.20).Problem (4.21) is a multi-objective combinatorial optimization problem. The weightedsum approach is commonly used to transform a multi-objective optimization problem intoa scalar optimization problem [103].4.3.1 Reformulation Using Weighted Sum MethodIn this subsection, we reformulate problem (4.21) using the weighted sum method. Theweighted sum approach considers a linear combination of all design objectives and is com-monly used in solving multi-objective optimization problems [104]. Pareto optimality is animportant solution concept for the multi-objective optimization problems. An outcome isPareto optimal when a single design objective (e.g, f1(Ps)) cannot be improved withoutdegrading the other objective (e.g, f2(Ps)). Multi-objective problem (4.21), which consid-ers both power consumption and system throughput, can be reformulated as a weightedsum problem. The Pareto optimal solution of problem (4.21) can be obtained by solving89Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networksthe following problem:minimizeX,Psλ1f1(Ps) + λ2f2(Ps) (4.22)subject to constraints (4.11)− (4.13), (4.20), and (4.21b),where λ1 and λ2 are non-negative coefficients to adjust the weights of objectives f1 andf2. For example, if λ1 = 1, λ2 = 0, problem (4.22) minimizes the power consumption.By changing the value of λ1 and λ2, different Pareto optima can be obtained. Problem(4.22) can be solved using standard optimization techniques such as branch-and-bound,generalized Benders decomposition, and outer approximation. However, none of the afore-mentioned methods can guarantee to obtain the solution in polynomial time due to theinteger programming required to solve the problem. In the next subsection, we transformthe multi-objective combinatorial optimization problem into a matching problem [105] toobtain the Pareto optimal solution. We then propose a Pareto optimal relay selection andpower allocation algorithm.4.3.2 Bipartite Graph ConstructionMatching theory can provide tractable solutions for combinatorial problems. As an examplein resource allocation in wireless networks, matching theory can address how resources canbe allocated to users [105]. Users and resources are considered as vertices in disjoint setsthat will be matched to each other. In this chapter, we regard vertex sets as the set ofD2D user pairs L and the set of relays R. We consider all possible relay selections asdifferent matchings. The goal is to find the best matching (i.e., relay selection) betweenD2D user pairs and relays, which results in the optimal solution of problem (4.22) and isalso the Pareto optimal solution of problem (4.21). To achieve this goal, we construct a90Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G NetworksFigure 4.2: (a) A bipartite graph with four D2D user pairs and three relays. (b) A matchingexample with four edges (l1, r2), (l2, r1), (l3, r2), and (l4, r3). (c) The one-to-one matchingwith virtual relays in dashed frames.bipartite graph as shown in Fig. 4.2(a), which consists two disjoint vertex sets and edges. Amatching is represented by a set of distinct edges. We use tuple (li, rj) to denote the edgethat connects D2D user pair li with relay rj. For instance, as shown in Fig. 4.2(b), thegraph with four solid edges (l1, r2), (l2, r1), (l3, r2), and (l4, r3) corresponds to a matchingexample. A weight is allocated to each edge of the graph. The purpose of constructingthe weighted graph is to transform problem (4.22) into an equivalent matching problem.Therefore, we will determine the weights of edges in order to achieve this goal. We alsodefine the minimum weighted matching as a matching where the sum of the weights ofthose edges selected in the matching has the minimum value. We then obtain the minimumweighted matching, from which we can determine the optimal solution of problem (4.22).To determine the weight of each edge in the graph, we first introduce the matchingrules. These rules guarantee that the optimal matching is within the feasible region ofproblem (4.22). By considering constraint (4.12), only a single edge can be connectedwith a D2D user pair in the matching. Meanwhile, we allow at most Nrj edges to beconnected with relay rj ∈ R in order to satisfy constraint (4.13). Constraints (4.12) and91Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks(4.13) indicate that the equivalent matching problem is a many-to-one matching. Wefurther consider constraints (4.11) and (4.20) which are related to the transmission powervariables. According to constraint (4.12), each D2D user pair can only be assisted by onerelay. We assume that D2D user pair li is assisted by relay rj (i.e., xli,rj = 1, xli,rk =0, ∀rk ∈ R \ {rj}). If there exists a transmission power Psi,rj that satisfies both of thefollowing inequalities:Cli,rj(Psi,rj) ≥ Cminli, (4.23)and0 ≤ Psi,rj ≤ min(Pmaxs , P˜maxs), (4.24)then Psi,rj is in the feasible region implied by constraints (4.11) and (4.20), and rj is afeasible relay for D2D user pair li. Otherwise, we regard relay rj as an infeasible relay.That is, D2D user pair li will not use relay rj. In this case, infeasible relay rj is excludedfrom the consideration of D2D user pair li, and edge (li, rj) will not be selected in thematching. By doing so, the optimal matching will be in the feasible region of problem(4.22) and satisfies all of its constraints.In order to find the feasible relays for a D2D user pair, we first consider (4.23) and(4.24). When we substitute (4.7) and (4.8) into (4.23), we obtain√4hsi,rjhLIhrj ,dihsi,diPsi,rj2 + 4hsi,rjhLIN0hrj ,diPsi,rj +N20h2rj ,di−N0hrj ,di2hLI(hsi,diPsi,rj +N0)≥ 2(Cminli/B) − 1,(4.25)Note that the left-hand side of (4.25) is an increasing function of Psi,rj . Therefore, whenwe consider that relay rj is selected to assist user pair li, we can determine the minimumtransmission power of source device si. That is, to achieve the minimum data rate require-ment Cminli , the minimum transmission power of source device si with assistance of relay92Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networksrj denoted by Pminsi,rjcan be obtained from (4.25). We havePminsi,rj ,hLIN0(2(Cminli/B) − 1)2+N0hrj ,di(2(Cminli/B) − 1)hsi,rjhrj ,di − hLIhsi,di(2(Cminli/B) − 1)2 . (4.26)Similarly, from (4.24), we can also determine the maximum transmission power of sourcesi to relay rj denoted by Pmaxsi,rj, wherePmaxsi,rj , min(Pmaxs , P˜maxs). (4.27)If Pminsi,rj > Pmaxsi,rj, there is no feasible transmission power that satisfies both (4.23) and(4.24). In this case, relay rj is found as an infeasible relay for D2D user pair li and edge(li, rj) is an infeasible edge in the graph. In order to exclude such infeasible edge, we set itsweight to +∞ so that the edge will not be considered when using the minimum weightedmatching method. After excluding all infeasible edges from consideration, the remainingedges are the feasible relays for the corresponding D2D user pairs.We can now determine the weight of each feasible edge in the graph. We assume rjis a feasible relay for D2D user pair li (i.e, Pminsi,rj≤ Pmaxsi,rj ). We denote the weight of edge(li, rj) by w(li, rj), where li = (si, di) ∈ L, rj ∈ R. To determine w(li, rj), we assumethat only D2D user pair li and its feasible relay rj exist in the network. Equivalently,the bipartite graph only has one edge (i.e., edge (li, rj)). This assumption implies thatxli,rj = 1, xlm,rn = 0 and Psm,rn = 0 for all (lm, rn) 6= (li, rj), lm = (sm, dm) ∈ L, rn ∈ R.We then convert problem (4.22) into the following new problem:minimizePsi,rjλ1Psi,rj − λ2Cli,rj(Psi,rj) (4.28a)subject to Pminsi,rj ≤ Psi,rj ≤ Pmaxsi,rj. (4.28b)93Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G NetworksFor a particular edge (li, rj), the weight w(li, rj) is determined by the optimal value ofproblem (4.28). We will later show that solving problem (4.22) is equivalent to finding theminimum weighted matching, where the sum of the weights of the edges selected in thematching has the minimum value. Let P ∗si,rj denote the optimal solution of problem (4.28)that uniquely exists due to the following theorem.Theorem 4.1 Problem (4.28) is a strictly convex optimization problem, which has a uniqueoptimal solution.The proof of Theorem 4.1 is given in Appendix A.Therefore, the optimal solution P ∗si,rj , which represents the optimal power of D2D userpair li = (si, di) assisted by relay rj , can be obtained by using standard optimization tech-niques such as gradient method. Once P ∗si,rj has been obtained, the optimal throughput,denoted by C∗li,rj = Cli,rj(P∗si,rj), can be determined as well. We can then compute theweight of edge (li, rj), when we assume that user pair li is assisted by relay rj. The weightof edge (li, rj) is set to gli,rj(P∗si,rj) = λ1P∗si,rj− λ2C∗li,rj .Given a matching, the resource allocation matrix X is fixed and the constraints ofproblem (4.22) are all satisfied. For example, in the matching shown in Fig. 4.2(b) thatincludes edges (l1, r2), (l2, r1), (l3, r2), and (l4, r3), we have xl1,r2 = xl2,r1 = xl3,r2 = xl4,r1 =1. Let F denote a matching and E denote the set of all edges of the bipartite graph. Formatching F ⊆ E , we show that the minimum weighted sum of power consumption andthroughput is equivalent to the summation of the weights of all edges in the matching.To do so, we formulate the following problem which minimizes the weighted sum of powerconsumption and throughput for matching F :minimizePsλ1∑(li,rj)∈FPsi,rj − λ2∑(li,rj)∈FCli,rj (Psi,rj ) (4.29a)subject to Pminsi,rj ≤ Psi,rj ≤ Pmaxsi,rj, ∀ (li, rj) ∈ F , (4.29b)94Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networkswhere li = (si, di). Since λ1 and λ2 are constants, the objective function is equal to∑(li,rj)∈F(λ1Psi,rj − λ2Cli,rj(Psi,rj))=∑(li,rj)∈Fgli,rj(Psi,rj). (4.30)The objective of problem (4.29) is to minimize the summation of all user pairs’ weightedsum for a given matching. According to (4.29) and (4.30), the optimal transmission powerof each source device is independent from others when we know the matching. Therefore,given matching F , for each edge (li, rj) ∈ F , we can obtain the optimal transmissionpower of source device si, denoted by P∗si,rj, by solving problem (4.28). The optimal valueof problem (4.28) for edge (li, rj) is gli,rj(P∗si,rj). Thus, given matching F , the optimal valueof problem (4.29) is∑(li,rj)∈Fgli,rj(P∗si,rj). (4.31)Notice that wli,rj = gli,rj(P∗si,rj), ∀ (li, rj) ∈ F . Therefore, the optimal value of problem(4.29) can also be represented as∑(li,rj)∈Fwli,rj , which is the summation of the weightsof all edges in matching F . Up to now, given a matching, we have shown that the mini-mum weighted sum of power consumption and throughput equals to the summation of theweights of all edges in the matching.We now focus on finding the optimal matching (i.e., minimum weighted matching). Weconstruct bipartite graph G = (L,R, E ,W ), where D2D user pair set L and relay set Rare the sets of vertices, and W = (wli,rj )li∈L,rj∈R is the weighting matrix of the edges. Theminimum weighted matching can be obtained as follows:F∗ = arg minF⊆E∑(li,rj)∈Fwli,rj . (4.32)95Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G NetworksBy constructing the bipartite graph, we have transformed the combinatorial relay se-lection and power allocation problem into a many-to-one matching problem. However, itis still difficult to obtain the optimal solution for this many-to-one matching problem inan efficient manner. Note that in our system, although each relay can assist multiple D2Duser pairs, eventually, each user pair is allocated a non-overlapping channel. By utilizingthis feature, we can further transform the many-to-one matching problem into a one-to-onematching problem which can be solved optimally in polynomial time. Since each relay rjhas Nrj channels, we replace rj with Nrj virtual relays, which are located at the samelocation. Each virtual relay is assigned a non-overlapping channel, as shown in Fig. 4.2(c).We use rjk to represent the virtual relay that operates on the kth channel of relay rj. Then,we denote the set of virtual relays as Rv = {r11, · · · , r1Nr1 , · · · r|R|1, · · · , r|R|Nr|R|}, whichrepresents a new vertex set. For ease of exposition, we denote rvj as the jth virtual relayin set Rv. We denote the new set of edges as Ev and the new weighting matrix as W v.By doing so, we transform the many-to-one matching problem into a one-to-one matchingproblem denoted by a new bipartite graph Gv = (L,Rv, Ev,W v). It has been proven thatone-to-one matching problems can be solved in polynomial time [106, Ch. 3].4.3.3 Pareto Optimal Relay SelectionUp to now, we have constructed the bipartite graph to obtain a solution of problem (4.22)using a one-to-one matching. In the following, we prove that the obtained solution is aPareto optimal resource allocation in terms of power consumption and system throughput.We first formally define the Pareto optimal resource allocation in Definition 4.2 with thehelp of Definition 4.1 [107, Ch. 1]:Definition 4.1 In a minimization problem, given resource allocation decision matrices Aand A′, the allocation outcome(f1(A), f2(A))is dominated by(f1(A′), f2(A′))if f1(A′) ≤96Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networksf1(A), f2(A′) ≤ f2(A) and(f1(A), f2(A))6=(f1(A′), f2(A′)).Definition 4.2 A resource allocation decision A is Pareto optimal if and only if theredoes not exist another resource allocation A′ dominating A.Based on the definition of Pareto optimal resource allocation, we have the following theo-rem.Theorem 4.2 The solution of problem (4.22), denoted by P ∗s , is a Pareto optimal resourceallocation.Proof Assume P ∗s is the solution of problem (4.22) and is not Pareto optimal. Then,there exists an allocation P˜s such that f1(P˜s) ≤ f1(P ∗s ) and f2(P˜s) ≤ f2(P∗s ). Given λ1and λ2, we have λ1f1(P˜s) + λ2f2(P˜s) ≤ λ1f1(P ∗s ) + λ2f2(P∗s ). This means P∗s is not theoptimal solution of problem (4.22). Here, we have the contradiction which completes theproof. 4.3.4 Algorithm DesignIn this subsection, we propose a relay selection and power allocation algorithm as shownin Algorithm 4.1 based on the Hungarian method [108] to solve the one-to-one matchingproblem. As proven in Theorem 4.2, our proposed algorithm achieves a Pareto optimalsolution of the multi-objective optimization problem (4.21). We define Xv∗ as the optimalvirtual relay selection matrix. The algorithm contains two main steps. As shown inAlgorithm 4.1, we first create the weighted bipartite graph by computing the weights ofall edges in the graph (Lines 2 to 12). By computing the minimum value of the weightedsum of power consumption and minus throughput, we obtain the weight of each edge (Line7). If the minimum data rate requirement cannot be satisfied, we set the correspondingweight to +∞ (Lines 8 to 9). By doing so, we exclude the virtual relays which would result97Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G NetworksAlgorithm 4.1: Relay selection and power allocation algorithm1 input L, S, D, Rv, Cminli ,∀li ∈ L, Pmaxs , Pmaxr , λ1, λ2, hLI , and hsi,rj , hrj ,di , hsi,di ∀li = (si, di) ∈ L, rj ∈ R2 for li ∈ L do3 for rvj ∈ Rv do4 Calculate Pminsi,rvjand Pmaxsi,rvjusing (4.26) and (4.27)5 if Pminsi,rvj≤ Pmaxsi,rvjthen6 Solve problem (4.28) to obtain P ∗si,rvj7 wvli,rvj:= λ1P∗si,rvj− λ2C∗li,rj(P ∗si,rvj)8 else9 wvli,rvj:= +∞10 if Pminsi,rvj> Pmaxsi,rvj∀ rvj ∈ Rv then11 Return infeasible12 W v := (wli,rvj )li∈L,rvj∈Rv13 Xv∗ := Hungarian(W v)14 output: Virtual relay selection decision Xv∗, and transmission power matrix P ∗s .in an infeasible solution for the corresponding D2D user pairs. If the minimum data raterequirement for a user pair cannot be satisfied regardless of which virtual relay the userpair uses (Line 10), this user pair will have to communicate using the cellular base station(instead of D2D mode) and operate under the resource allocation rules for regular cellularusers. If the minimum data rate requirement can be satisfied, then the Hungarian method[108] is used to obtain the optimal virtual relay selection matrix Xv∗ (Line 13).The optimal matching that minimizes the summation of the weights can be obtainedby the Hungarian method. The Hungarian method is proposed in [108]. However, for thesake of completeness, we briefly present the Hungarian method in Algorithm 4.2. We usez∗ = (z∗l1 , · · · , z∗li, · · · , z∗l|L|) to indicate the current matching result. For example, z∗l3= rv5means that user pair l3 is matched with virtual relay rv5 . We define m = (mli,rvj )li∈L,rvj∈Rvas a marking indicator of the edges of the bipartite graph (i.e., the elements of W v). Thisindicator is used to mark the element that has the minimum weight. The edge correspond-98Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G NetworksAlgorithm 4.2: Hungarian method1 input Weighting matrix W v2 initialize z∗ = (z∗li)li∈L := {0}1×|L|, Xv∗ = (x∗li,rvj)li∈L,rvj∈Rv:= {0}|L|×|Rv|,m = (mli,rvj )li∈L,rvj∈Rv:= {0}|L|×|Rv|, A := L, and B := Rv,3 for li ∈ L do4 Set wli,rvj := wli,rvj − minrvk∈Rv{wli,rvk}, ∀ rvk ∈ Rv5 while A 6= ∅ do6 Set z∗li := rvj , ∀ li ∈ A, rvj ∈ B, such that wli,rvj = 07 Set A := A \ {li}8 Set B := B \ {rvj }9 while true do10 Set cr = (crli)li∈L := {0}1×|L|11 Set cc = (ccrvj )rvj∈Rv:= {0}1×|Rv |12 Set crli := 1,∀ li ∈ L, such that z∗li> 013 if z∗li 6= 0 ∀ li ∈ L then14 Break15 while true do16 Set mli,rvj := 1 ∀ li ∈ L, rvj ∈ Rv, such that ccrvj = 0 and wli,rvj = 017 if ∄ (li, rvj ) ∀ li ∈ L, rvj ∈ Rv, such that mli,rvj = 1, crli = 0, and wli,rvj = 0 then18 Break19 else20 Set crli := 1, ccrvj := 0 ∀ li ∈ L, rvj ∈ Rv, such that mli,rvj = 1, crli = 0, andwli,rvj = 021 Set J := {(li, rvj ) ∈ L ×Rv | crli = ccrvj = 0}22 Set a := min(li,rvj )∈J{wli,rvj }23 Update wli,rvj := wli,rvj + a ∀ li ∈ L, such that crli = 024 Update wli,rvj := wli,rvj − a ∀ rvj ∈ Rv, such that ccrvj = 025 Set z∗li := rvj ∀ li ∈ L, rvj ∈ Rv, such that wli,rvj = 0, mli,rvj = 1, and crli = ccrvj= 026 for li ∈ L do27 Set x∗li,rvj:= 1 ∀ rvj ∈ Rv, such that z∗li = rvj28 output: Virtual relay selection decision Xv∗ing to the marked element is regarded as a potential edge in the optimal matching. Elementwli,rvj is marked when mli,rvj is set to 1. Ifmli,rvj = 0, element wli,rvj is not marked. We definecr = (crli)li∈L and cc = (ccrvj )rvj∈Rvas the row cover indicator and column cover indicator,99Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networksrespectively. The purpose of covering a row (or a column) is to exclude the elements of thatrow (or column) from further operations. For example, row i of the weighting matrix W vis covered and excluded from operations if crli = 1. The main steps of the algorithm areintroduced as follows. First, the minimum value of each row of W v is subtracted from allelements in its row (Lines 3 and 4). Then, zeros in the modified matrix W v are found andtheir indices are recorded in z∗ (Lines 5 to 8). Next, the algorithm verifies whether all userpairs and virtual relays are matched by checking the number of zeros in z∗ (Lines 13 and14). If there is no zero in z∗, the matching is obtained. Otherwise, the weighting matrixis updated according to the mark indicator m and cover indicators cr and cc (Lines 15to 24). Specifically, the minimum uncovered element is subtracted from each covered row,and then added to each uncovered column. By doing so, new zeros will be resulted. Thealgorithm then finds and records the indices of the new zeros (Line 25) and runs the whileloop (Lines 9 and 25) again. If z∗ has no zeros, the recorded indices will be returned as thematching results of the algorithm (Lines 26 and 27). The convergence of the Hungarianmethod is proven in [108].We now discuss the computational complexity of Algorithm 4.1. The computationalcomplexity of the Hungarian method is proven to be O(|L|3) [106]. The complexity ofcomputing the weights of all edges (Lines 2 to 12) in the graph is O(|L||Rv|), which ispolynomial. Therefore, Algorithm 4.1 can obtain a Pareto optimal solution in polynomialtime.4.4 Performance EvaluationIn this section, we evaluate the performance of our proposed algorithm and compare it witha recently proposed relay selection algorithm called all relays selection (ARS) algorithm[71]. The reason we choose [71] is because it also focuses on optimal relay selection in D2D100Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks1 3 5 7 9 11 1300.10.20.30.40.50.60.70.80.91Number of D2D user pairs |L|Totaltransmissionpower(mW) ARSProposed Algorithm 48%Figure 4.3: Total transmission power versus number of D2D user pairs |L| with |R| = 4.networks. ARS let each D2D user pair choose the best relay from all candidate relays.We assume the D2D devices and relays are randomly located in a 1 km × 1 km region.Each relay can use four channels (i.e., Nrj = 4, ∀rj ∈ R). The bandwidth of each channelB = 1 MHz, and the noise power spectrum density is −174 dBm/Hz. Other simulationparameters are as follows: Pmaxs = 2 Watt, Pmaxr = 10 Watt, Cminli= 5 Mbps, ∀li ∈ L,M t = M r = 10 dB, mt = mr = −5 dB, ΘtHPBW = ΘrHPBW = 15o, α = 2, and σ = 1.5[97, 100]. We use Monte Carlo simulations and calculate the average value of the totaltransmission power and the system throughput over different network settings.We first set λ1 = 1 and λ2 = 0 to study the single-objective optimization problem forminimizing the transmission power. In Fig. 4.3, we compare the total transmission powerof devices in our proposed algorithm with that obtained by ARS for different number ofD2D user pairs. As shown in this figure, our proposed algorithm substantially outperformsARS. When the number of D2D user pairs is 13, our proposed algorithm results in 48% less101Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks4 5 6 7 8 90.10.20.30.40.50.60.70.80.91Number of relays |R|Totaltransmissionpower(mW) ARSProposed Algorithm48%Figure 4.4: Total transmission power versus number of relays |R| with |L| = 13.transmission power than ARS. This is because the proposed algorithm achieves the optimalsolution, while ARS let each user pair to choose its best relay and cannot guarantee anoptimal solution for the system.In Fig. 4.4, we compare the total transmission power versus different number of relayswhen the number of D2D user pairs is 13. Fig. 4.4 shows that the total transmissionpower is decreasing in both algorithms as the number of relays increases. This is becauseeach D2D user pair has more opportunity to select a nearby relay. Results show that ourproposed algorithm significantly outperforms ARS when a small number of relays exist.This indicates that our algorithm is more efficient compared to ARS, especially in thenetworks with few relays.In Fig. 4.5, we compare the total transmission power versus different minimum datarate requirements of D2D user pairs when there are 13 D2D user pairs with 4 relays inthe network. Results show that a higher transmission power is consumed by ARS under102Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks1 2 3 4 5 600.20.40.60.811.21.41.61.822.2Minimum data rate of D2D user pairs Cminli(Mbps)Totaltransmissionpower(mW) ARSProposed Algorithm 30%Figure 4.5: Total transmission power versus minimum data rate requirement Cminli , ∀li ∈ Lwith |R| = 4 and |L| = 13.different data rate requirements in comparison with our proposed algorithm. When theminimum data rate requirement Cminli = 6 Mbps, our proposed algorithm outperformsARS by 30%. Results also show that more power is saved for applications with a high datarate requirement by using our proposed algorithm. This achievement is promising sincethe data rate requirements of the emerging applications on mobile devices are increasingrapidly.We now set λ1 = 0 and λ2 = 1, which gives the optimal relay selection and powerallocation for maximizing the system throughput. In Fig. 4.6, we compare the optimalthroughput versus different number of D2D user pairs when there are 4 relays in thenetwork. Results show that our proposed algorithm achieves a higher throughput comparedto ARS under different number of D2D user pairs. When the number of D2D user pairs is103Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks1 3 5 7 9 11 13020406080100120140160180Number of D2D user pairs |L|Systemthroughput(Mbps) Proposed AlgorithmARS 18%Figure 4.6: System throughput versus number of D2D user pairs |L| with |R| = 4.13, the proposed algorithm achieves 18% higher throughput than ARS. Results also showthat the throughput improvement of our proposed algorithm over ARS increases as thenumber of D2D user pairs increases. This is because when the ratio between D2D userpairs and relays increases, ARS cannot guarantee that each D2D user pair can use its idealrelay and substantially degrades the performance of the system.In Fig. 4.7, we show the optimal throughput versus different number of relays whenthe number of D2D user pairs is 13. Our proposed algorithm substantially improves thesystem throughput compared to ARS under different number of relays. When the numberof relays is 9, our proposed algorithm results in 13% higher throughput than ARS. Althoughthe improvement slightly decreases as the number of relays increases, the minimum gapbetween our proposed algorithm and ARS remains significant.In Fig. 4.8, we compare the optimal throughput versus different loop-interference gain.104Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks4 5 6 7 8 9145150155160165170175180185190195Number of relays |R|Systemthroughput(Mbps) Proposed AlgorithmARS13%Figure 4.7: System throughput versus number of relays |R| with |L| = 13.We consider the loop gain range from −158 dB to −150 dB. As shown in this figure,the system throughput slightly decreases as the loop-interference gain increases. Thisshows that a stronger self-interference will result in a lower throughput. However, ourproposed algorithm achieves a higher throughput than ARS. When the loop-interferencegain hLI = −158 dB, our proposed algorithm achieves 16% higher throughput comparedto ARS.We now consider the multi-objective optimization problem and vary λ1 and λ2 to studythe trade-off between the power consumption and the system throughput. In Fig. 4.9, weplot the optimal power consumption and system throughput versus weighting factor λ2,when λ1 = 1. We can observe that when λ2 decreases, the optimal solution tends to savepower which results in a lower throughput. This is because the dominant optimizationobjective is to minimize the power consumption in this case. Results also show that theincrement of the throughput is not as fast as the increment of the power. In other words, the105Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks−158 −157 −156 −155 −154 −153 −152 −151 −150100120140160180200Loop-interference gain hLI (dB)Systemthroughput(Mbps) Proposed AlgorithmARS16%Figure 4.8: System throughput versus loop-interference gain hLI .marginal throughput increment becomes smaller when the transmission power increases.This provides useful insights of the system design to balance the power consumption andsystem throughput.In Fig. 4.10, we plot the Pareto optimal frontier of power consumption and systemthroughput for different number of D2D user pairs by varying λ2 when λ1 = 1. The Paretooptimal frontier shows the Pareto optimal power consumption and system throughput thatcan be achieved. In other words, each frontier curve shows the optimal throughput giventhe power consumption budget. As shown in this figure, with the same weighting factor,more D2D user pairs result in a higher power consumption and system throughput. Whenthe power increases, the throughput slightly increases. This indicates that by consuminga very high transmission power, the throughput will not increase significantly.106Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks10−4 10−3 10−2 10−1 100 101 102050100150200250300350400Weighting factor λ2Totaltransmissionpower(mW)(a) Optimal power consumption10−4 10−3 10−2 10−1 100 101 10290100110120130140150160170180Weighting factor λ2Systemthroughput(Mbps)(b) Optimal system throughputFigure 4.9: Optimal power consumption and system throughput versus weighting factorλ2 when λ1 = 1 with |R| = 4 and |L| = 13.107Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networks0 0.01 0.02 0.03 0.04 0.05 0.06020406080100120140Total transmission power (mW)Systemthroughput(Mbps) Number of D2D user pairs |L| = 10Number of D2D user pairs |L| = 8Number of D2D user pairs |L| = 6λ2 = 10−4λ2 = 10−3λ2 = 10−2Figure 4.10: Pareto optimal frontier for different number of D2D user pairs.4.5 SummaryIn this chapter, we studied the resource allocation problem for full-duplex relay-assistedD2D communication in mmWave based wireless networks. We formulated the joint relayselection and power allocation problem as a multi-objective optimization problem, whichbalances the trade-off between power consumption and system throughput. The formulatedproblem characterizes self-interference cancellation in full-duplex relaying systems. We alsoconsidered the QoS requirements for various applications and the physical constraints ofthe mobile devices and relays. The problem is a combinatorial optimization problem and iscomplex to solve using standard optimization techniques. To mitigate the complexity of thecombinatorial problem, we transformed the problem into a one-to-one matching problemby constructing a weighted bipartite graph. We proposed an algorithm to find the solutionin polynomial time. It is proven that the solution obtained by our proposed algorithm isPareto optimal. Simulation results showed that our proposed algorithm improves the power108Chapter 4. Full-duplex Relay-assisted D2D Communication in 5G Networksconsumption and the system throughput substantially compared to a recently proposedalgorithm in the literature.109Chapter 5Conclusions and Future WorkIn this final chapter, we highlight the contributions and conclude the results of this thesisin Section 5.1. We also propose ideas for future research topics in Section 5.2.5.1 Research Contributions and ResultsThis thesis studies several resource allocation problems in wireless networks. Optimiza-tion theory, game theory, and matching theory are used in solving the resource allocationproblems. In the following, we briefly review the contributions and draw the conclusions.In Chapter 2, we studied the subchannel allocation problem for hybrid overlay/underlaycognitive cellular networks. We formulated the problem as a coalition formation game withnegative externalities. We proposed an MRC algorithm based on the solution concept ofrecursive core. Simulation results showed that a substantial improvement of the aggregatenetwork throughput was achieved over the overlay scheme, the underlay scheme, a hy-brid overlay/underlay scheme without MRC, and a recently proposed coalition formationalgorithm. In conclusion, in a cognitive two-tier cellular network considering mutual in-terference, a proper hybrid overlay/underlay scheme can further improve spectrum reuse.Cooperation, instead of competition, is crucial to exploit the mutual benefits for the de-vices in the networks where common resources are shared. Our proposed approach can alsobe used in other types of resource-limited networks, where the design goal is to improvethe system performance via cooperation.110Chapter 5. Conclusions and Future WorkIn Chapter 3, we studied the resource management problem for multimedia contentdelivery in mmWave based wireless home networks. An integrated TDMA/FDMA/SDMAscheduling scheme, which considered concurrent transmissions for mmWave home net-works to increase the spectrum efficiency, was proposed. A non-convex MIP networkutility maximization problem was formulated. The problem was transformed into a convexMIP problem. An OA based algorithm was proposed to find the optimal solution of theconvex MIP problem. In order to reduce the computational complexity, we further de-veloped a greedy algorithm. Simulation results showed that both algorithms substantiallyoutperformed recently proposed algorithms in the literature. To conclude, mmWave com-munication technology is promising for high data rate services in wireless home networks.It is necessary to consider to spatial and spectrum reuse to fully exploit the potentials ofdirectional mmWave communication. In mmWave based systems, the trade-off betweenantenna gain and signal alignment overhead should be considered. An optimized beamwidth can significantly improve the system performance. In order to maximize the users’utility in a home network, the scheduling scheme should be optimized based on differentusage scenarios.In Chapter 4, we studied the resource allocation problem for full-duplex relay-assistedD2D communication in mmWave based wireless networks. To balance the trade-off betweenthe power consumption and the system throughput, we formulated a multi-objective op-timization problem. The formulated problem characterized self-interference in full-duplexrelaying systems. The problem was a combinatorial problem which was complex to solveusing standard optimization techniques. To tackle the complexity, the problem was trans-formed into a one-to-one matching problem. An algorithm was proposed to find the solutionin polynomial time. We proved that the solution obtained by the proposed algorithm wasPareto optimal. Simulation results showed that our algorithm improved the power sav-111Chapter 5. Conclusions and Future Working and the system throughput substantially compared to a recently proposed algorithm.In conclusion, in a full-duplex relay-assisted D2D networks, the mobile device and thefull-duplex relay should coordinate their transmission power to achieve the required datarate while saving power. The optimal transmission power is related to the self-interferencecancellation gain of the full-duplex relay. The minimum weighted matching approach iseffective and efficient in finding the optimal solution that balances the power consumptionand the system throughput. This approach is also promising for other scenarios where theresource allocation problem can be formulated using a weighted graph.5.2 Suggestions for Future WorkIn the following, we discuss different possibilities for extension of the presented work.1. Imperfect channel estimation and different subchannel allocation schemesin a coalition:In Chapter 2, we proposed the MRC based hybrid cognitive access scheme for two-tiercellular networks. Full knowledge of channel information was assumed to be availablefor the proposed scheme. However, imperfect channel information may result ininaccurate interference estimation. The best strategy of an FAP under imperfectchannel information is worth exploring, since poor channel estimation might make anFAP choose a poor coalition. Robust game theory is a promising tool to analyze theinteractions among FAPs with imperfect channel estimation. In addition, differentsubchannel allocation schemes within a coalition can be explored. More informationsuch as the location of each FUE may also improve the subchannel allocation schemeto further reduce the mutual interference of different links within a coalition. Thescenarios where MUEs and FUEs in cognitive femtocell networks have the same112Chapter 5. Conclusions and Future Workpriority can be considered. In such scenarios, the roles of MUEs and FUEs in thecognitive network will not be predetermined.2. Hybrid reservation/contention based wireless home networks and inter-ference among multiple home networks:In Chapter 3, we proposed the integrated scheduling scheme for multimedia contentdelivery in home networks. We assumed that all multimedia content was deliv-ered using the reservation-based time slots in the data transfer interval. It will beinteresting to include the contention-based transmission as a potential method forQoS-constrained applications, since it might further improve the channel utilizationwhen the device density is low. However, reducing the collision probability intro-duced by contention-based transmissions while increasing the channel utility will bea challenging issue. Meanwhile, the growing number of wireless devices in adjacenthome networks will result in a higher interference among multiple home networks.How to coordinate multiple home networks will be crucial, since coordination amongdifferent home networks may significantly improve the users’ utility. Other utilityfunctions for future usage scenarios can also be considered. Further optimization ofthe greedy algorithm based on various sets of utility functions is worth studying.3. Possible channel reuses for dense D2D enabled wireless networks and dis-tributed resource allocation algorithm:In Chapter 4, we proposed the resource allocation algorithm, where each D2D userpair can be allocated an independent channel. In future, possible channel reuse forthe case of dense D2D communication is promising to explore. How to effectivelyeliminate the mutual interference in D2D communication networks with full-duplexrelays will be challenging and important. It is also interesting to study the resource113Chapter 5. Conclusions and Future Workallocation in a system where full-duplex relays can serve cellular users as well asD2D users. Meanwhile, a distributed algorithm that can reduce the communicationoverhead imposed by exchanging control messages is also worth exploring.114Bibliography[1] Federal Communications Commission, “Notice of proposed rule making and order:Facilitating opportunities for flexible, efficient, and reliable spectrum use employingcognitive radio technologies,” ET-docket, no. 03-108, Feb. 2005.[2] V. Chandrasekhar, J. G. Andrews, and A. Gatherer, “Femtocell networks: A survey,”IEEE Commun. Mag., vol. 46, no. 9, pp. 59–67, Sep. 2008.[3] V. Chandrasekhar and J. G. Andrews, “Uplink capacity and interference avoidancefor two-tier femtocell networks,” IEEE Trans. Wireless Commun., vol. 8, no. 7, pp.3498–3509, Jul. 2009.[4] D. Lo´pez-Pe´rez, A. Valcarce, G. De La Roche, and J. Zhang, “OFDMA femtocells:A roadmap on interference avoidance,” IEEE Commun. Mag., vol. 47, no. 9, pp.41–48, Sep. 2009.[5] Y. Sun, R. Jover, and X. Wang, “Uplink interference mitigation for OFDMA fem-tocell networks,” IEEE Trans. Wireless Commun., vol. 11, no. 2, pp. 614–625, Feb.2012.[6] S. Haykin, “Cognitive radio: Brain-empowered wireless communications,” IEEE J.Sel. Areas Commun., vol. 23, no. 2, pp. 201–220, Feb. 2005.[7] Q. Zhao and B. Sadler, “A survey of dynamic spectrum access,” IEEE Signal Pro-cessing Magazine, vol. 24, no. 3, pp. 79–89, May 2007.[8] J. Zou, H. Xiong, D. Wang, and C. Chen, “Optimal power allocation for hybridoverlay/underlay spectrum sharing in multiband cognitive radio networks,” IEEETrans. Veh. Technol., vol. 62, no. 4, pp. 1827–1837, May 2013.[9] N. Saito, “Ecological home network: An overview,” Proceedings of the IEEE, vol.101, no. 11, pp. 2428–2435, Nov 2013.[10] T. S. Rappaport, R. W. Heath Jr, R. C. Daniels, and J. N. Murdock, MillimeterWave Wireless Communications. Pearson Education, 2014.[11] T. S. Rappaport, S. Sun, R. Mayzus, H. Zhao, Y. Azar, K. Wang, G. Wong, J. Schulz,M. Samimi, and F. Gutierrez, “Millimeter wave mobile communications for 5G cel-lular: It will work!” IEEE Access, vol. 1, pp. 335–349, May 2013.115Bibliography[12] A. Ghosh, T. Thomas, M. Cudak, R. Ratasuk, P. Moorut, F. Vook, T. Rappaport,G. MacCartney, S. Sun, and S. Nie, “Millimeter-wave enhanced local area systems: Ahigh-data-rate approach for future wireless networks,” IEEE J. Sel. Areas Commun.,vol. 32, no. 6, pp. 1152–1163, June 2014.[13] D. Wu, J. Wang, Y. Cai, and M. Guizani, “Millimeter-wave multimedia communi-cations: Challenges, methodology, and applications,” IEEE Commun. Mag., vol. 53,no. 1, pp. 232–238, Jan. 2015.[14] S. Scott-Hayward and E. Garcia-Palacios, “Multimedia resource allocation inmmWave 5G networks,” IEEE Commun. Mag., vol. 53, no. 1, pp. 240–247, Jan.2015.[15] T. Bai, A. Alkhateeb, and R. Heath, “Coverage and capacity of millimeter-wavecellular networks,” IEEE Commun. Mag., vol. 52, no. 9, pp. 70–77, Sep. 2014.[16] IEEE Std 802.15.3c-2009, “IEEE standard for information technology-telecommunications and information exchange between systems-local and metropoli-tan area networks-specific requirements. part 15.3: Wireless medium access control(MAC) and physical layer (PHY) specifications for high rate wireless personal areanetworks (WPANs) amendment 2: Millimeter-wave-based alternative physical layerextension,” pp. 1–187, Oct. 2009.[17] IEEE 802.11 Working Group, “IEEE standard for information technology–telecommunications and information exchange between systems–local and metropoli-tan area networks–specific requirements-Part 11: Wireless LAN medium access con-trol (MAC) and physical layer (PHY) specifications amendment 3: Enhancementsfor very high throughput in the 60 GHz band,” IEEE Std 802.11ad-2012, pp. 1–628,Dec. 2012.[18] E. Charfi, L. Chaari, and L. Kamoun, “PHY/MAC enhancements and QoS mecha-nisms for very high throughput WLANs: A survey,” IEEE Communications SurveysTutorials, vol. 15, no. 4, pp. 1714–1735, Fourth Quarter 2013.[19] IEEE 802.11 Working Group, “Status of project IEEE 802.11ay,” Available athttp://www.ieee802.org/11/Reports/tgay update.htm, accessed: June 2015.[20] IEEE P802.11 Wireless LANs, “IEEE 802.11 TGay Use Cases,” IEEE 802.11-2015/0625r3, Sep. 2015.[21] ISO/IEC/IEEE, “ISO/IEC/IEEE Int’l Standard for Information technology–Telecommunications and information exchange between systems–Local andmetropolitan area networks–Specific requirements-Part 11: Wireless LAN MediumAccess Control (MAC) and Physical Layer (PHY) Specifications Amendment 3: En-hancements for Very High Throughput in the 60 GHz Band (adoption of IEEE Std116Bibliography802.11ad-2012),” ISO/IEC/IEEE 8802-11:2012/Amd.3:2014(E), pp. 1–634, March2014.[22] M. N. Tehrani, M. Uysal, and H. Yanikomeroglu, “Device-to-device communication in5G cellular networks: Challenges, solutions, and future directions,” IEEE Commun.Mag., vol. 52, no. 5, pp. 86–92, May 2014.[23] X. Chen, B. Proulx, X. Gong, and J. Zhang, “Exploiting social ties for cooperativeD2D communications: A mobile social networking case,” IEEE/ACM Trans. Netw.,vol. 23, no. 5, pp. 1471–1484, Oct. 2015.[24] K. A. Meerja, P.-H. Ho, and B. Wu, “A novel approach for co-channel interfer-ence mitigation in femtocell networks,” in Proc. of IEEE Global Commun. Conf.(GLOBECOM), Houston, TX, Dec. 2011.[25] S. Lien, C. Tseng, K. Chen, and C. Su, “Cognitive radio resource management forQoS guarantees in autonomous femtocell networks,” in Proc. of IEEE Int’l Conf. onCommun. (ICC), Cape Town, South Africa, May 2010.[26] A. Attar, V. Krishnamurthy, and O. Gharehshiran, “Interference management usingcognitive base-stations for UMTS LTE,” IEEE Commun. Mag., vol. 49, no. 8, pp.152–159, Aug. 2011.[27] R. Urgaonkar and M. J. Neely, “Opportunistic cooperation in cognitive femtocellnetworks,” IEEE J. Sel. Areas Commun., vol. 30, no. 3, pp. 607–616, Mar. 2012.[28] A. Adhikary, V. Ntranos, and G. Caire, “Cognitive femtocells: Breaking the spa-tial reuse barrier of cellular systems,” in Proc. of IEEE Information Theory andApplications Workshop (ITA), San Diego, CA, Feb. 2011.[29] S. Al-Rubaye, A. Al-Dulaimi, and J. Cosmas, “Cognitive femtocell,” IEEE VehicularTechnology Magazine, vol. 6, no. 1, pp. 44–51, Mar. 2011.[30] O. Gharehshiran, A. Attar, and V. Krishnamurthy, “Collaborative sub-channel allo-cation in cognitive LTE femto-cells: A cooperative game-theoretic approach,” IEEETrans. Commun., vol. 61, no. 1, pp. 325–334, Jan. 2013.[31] F. Pantisano, M. Bennis, W. Saad, and M. Debbah, “Spectrum leasing as an incentivetowards uplink macrocell and femtocell cooperation,” IEEE J. Sel. Areas Commun.,vol. 30, no. 3, pp. 617–630, Apr. 2012.[32] S. Guruacharya, D. Niyato, M. Bennis, and D. I. Kim, “Dynamic coalition formationfor network MIMO in small cell networks,” IEEE Trans. Wireless Commun., vol. 12,no. 10, pp. 5360–5372, Oct. 2013.117Bibliography[33] Y. Yiakoumis, K.-K. Yap, S. Katti, G. Parulkar, and N. McKeown, “Slicing homenetworks,” in Proc. of ACM SIGCOMM Workshop on Home Networks, Toronto,Canada, Aug. 2011.[34] Y. He, J. Sun, R. Yuan, and W. Gong, “A reservation based backoff method for videostreaming in 802.11 home networks,” IEEE J. Sel. Areas Commun., vol. 28, no. 3,pp. 332–343, Mar. 2010.[35] T. Li, N. B. Mandayam, and A. Reznik, “A framework for distributed resourceallocation and admission control in a cognitive digital home,” IEEE Trans. WirelessCommun., vol. 12, no. 3, pp. 984–995, Mar. 2013.[36] S. Sundaresan, N. Feamster, and R. Teixeira, “Locating throughput bottlenecks inhome networks,” in Proc. of ACM SIGCOMM, Chicago, IL, Aug. 2014.[37] C.-Y. Li, C. Peng, G.-H. Tu, S. Lu, X. Wang, and R. Chandra, “Latency-aware rateadaptation in 802.11n home networks,” in Proc. of IEEE INFOCOM, Hong Kong,Apr. 2015.[38] M. Park and P. Gopalakrishnan, “Analysis on spatial reuse and interference in 60-GHz wireless networks,” IEEE J. Sel. Areas Commun., vol. 27, no. 8, pp. 1443–1452,Oct. 2009.[39] Q. Chen, X. Peng, J. Yang, and F. Chin, “Spatial reuse strategy in mmWave WPANswith directional antennas,” in Proc. of IEEE Global Commun. Conf. (GLOBECOM),Anaheim, CA, Dec. 2012.[40] C.-S. Sum and H. Harada, “Scalable heuristic STDMA scheduling scheme for practi-cal multi-Gbps millimeter-wave WPAN and WLAN systems,” IEEE Trans. WirelessCommun., vol. 11, no. 7, pp. 2658–2669, July 2012.[41] S. Singh, R. Mudumbai, and U. Madhow, “Interference analysis for highly directional60-GHz mesh networks: The case for rethinking medium access control,” IEEE/ACMTrans. Netw., vol. 19, no. 5, pp. 1513–1527, Oct. 2011.[42] J. Qiao, X. Shen, J. Mark, and Y. He, “MAC-layer concurrent beamforming protocolfor indoor millimeter-wave networks,” IEEE Trans. Veh. Technol., vol. 64, no. 1, pp.327–338, Jan. 2015.[43] G. Athanasiou, P. C. Weeraddana, C. Fischione, and L. Tassiulas, “Optimizing clientassociation for load balancing and fairness in millimeter-wave wireless networks,”IEEE/ACM Trans. Netw., vol. 23, no. 3, pp. 836–850, June 2015.[44] H. Shokri-Ghadikolaei, C. Fischione, P. Popovski, and M. Zorzi, “Design aspects ofshort-range millimeter-wave networks: A MAC layer perspective,” IEEE Network,vol. 30, no. 3, pp. 88–96, May 2016.118Bibliography[45] I. K. Son, S. Mao, M. Gong, and Y. Li, “On frame-based scheduling for directionalmmWave WPANs,” in Proc. of IEEE INFOCOM, Orlando, FL, Mar. 2012.[46] J. Kim, Y. Tian, S. Mangold, and A. Molisch, “Joint scalable coding and routing for60 GHz real-time live HD video streaming applications,” IEEE Trans. Broadcast.,vol. 59, no. 3, pp. 500–512, Sep. 2013.[47] K. Zheng, L. Zhao, J. Mei, M. Dohler, W. Xiang, and Y. Peng, “10 Gb/s HetSNetswith millimeter-wave communications: access and networking – challenges and pro-tocols,” IEEE Comm. Magazine, vol. 53, no. 1, pp. 222–231, Jan. 2015.[48] M. Di Renzo, “Stochastic geometry modeling and analysis of multi-tier millimeterwave cellular networks,” IEEE Trans. Wireless Commun., vol. 14, no. 9, pp. 5038–5057, Sep. 2015.[49] J. Guillory, E. Tanguy, A. Pizzinat, B. Charbonnier, S. Meyer, C. Algani, and H. Li,“A 60 GHz wireless home area network with radio over fiber repeaters,” J. Lightw.Technol., vol. 29, no. 16, pp. 2482–2488, Aug. 2011.[50] N. Moraitis and P. Constantinou, “Indoor channel measurements and characteriza-tion at 60 GHz for wireless local area network applications,” IEEE Trans. AntennasPropag., vol. 52, no. 12, pp. 3180–3189, Dec. 2004.[51] IEEE P802.15 Working Group for Wireless Personal Area Networks, “TG3c channelmodeling sub-committee final report,” IEEE 802.15-0584-003c, Mar. 2007.[52] IEEE P802.11 Working Group AD, “Channel models for 60 GHz WLAN systems,”IEEE 802.11-09/0334r8, May 2010.[53] Y. Niu, C. Gao, Y. Li, L. Su, D. Jin, and A. Vasilakos, “Exploiting device-to-devicecommunications in joint scheduling of access and backhaul for mmWave small cells,”IEEE J. Sel. Areas Commun., vol. 33, no. 10, pp. 2052–2069, Oct. 2015.[54] W. U. Rehman, J. Han, C. Yang, M. Ahmed, and X. Tao, “On scheduling algorithmfor device-to-device communication in 60 GHz networks,” in Proc. of IEEE WirelessCommunications and Networking Conference (WCNC), Istanbul, Turkey, Apr. 2014.[55] Y. Li, D. Jin, J. Yuan, and Z. Han, “Coalitional games for resource allocation inthe device-to-device uplink underlaying cellular networks,” IEEE Trans. WirelessCommun., vol. 13, no. 7, pp. 3965–3977, July 2014.[56] F. Wang, C. Xu, L. Song, and Z. Han, “Energy-efficient resource allocation for device-to-device underlay communication,” IEEE Trans. Wireless Commun., vol. 14, no. 4,pp. 2082–2092, Apr. 2015.119Bibliography[57] J. Qiao, X. S. Shen, J. W. Mark, Q. Shen, Y. He, and L. Lei, “Enabling device-to-device communications in millimeter-wave 5G cellular networks,” IEEE Commun.Mag., vol. 53, no. 1, pp. 209–215, Jan. 2015.[58] P. C. Nguyen and B. D. Rao, “Fair scheduling policies exploiting multiuser diversityin cellular systems with device-to-device communications,” IEEE Trans. WirelessCommun., vol. 14, no. 9, pp. 4757–4771, Sep. 2015.[59] H. Xing and M. Renfors, “Resource management schemes for network assisteddevice-to-device communication for an integrated OFDMA cellular system,” in Proc.of IEEE Int’l Symposium on Personal, Indoor and Mobile Radio Communications(PIMRC), Hong Kong, China, Aug. 2015.[60] M. Sheng, Y. Li, X. Wang, J. Li, and Y. Shi, “Energy efficiency and delay tradeoff indevice-to-device communications underlaying cellular networks,” IEEE J. Sel. AreasCommun., vol. 34, no. 1, pp. 92–106, Jan. 2016.[61] H. Zhang, L. Song, and Z. Han, “Radio resource allocation for device-to-device un-derlay communication using hypergraph theory,” IEEE Trans. Wireless Commun.,vol. 15, no. 7, pp. 4852–4861, July 2016.[62] H. Shi, R. Prasad, V. Rao, I. Niemegeers, and M. Xu, “Spectrum- and energy-efficientD2DWRAN,” IEEE Commun. Mag., vol. 52, no. 7, pp. 38–45, July 2014.[63] M. Hasan, E. Hossain, and D. I. Kim, “Resource allocation under channel uncer-tainties for relay-aided device-to-device communication underlaying LTE-A cellularnetworks,” IEEE Trans. Wireless Commun., vol. 13, no. 4, pp. 2322–2338, Apr. 2014.[64] L. Wang, F. Tian, T. Svensson, D. Feng, M. Song, and S. Li, “Exploiting full duplexfor device-to-device communications in heterogeneous networks,” IEEE Commun.Mag., vol. 53, no. 5, pp. 146–152, May 2015.[65] G. Zhang, K. Yang, P. Liu, and J. Wei, “Power allocation for full-duplex relaying-based D2D communication underlaying cellular networks,” IEEE Trans. Veh. Tech-nol., vol. 64, no. 10, pp. 4911–4916, Oct. 2015.[66] A. Al-Hourani, S. Kandeepan, and E. Hossain, “Relay-assisted device-to-device com-munication: A stochastic analysis of energy saving,” accepted for publication in IEEETrans. Mobile Computing, 2016.[67] B. Ma, M. H. Cheung, and V. W. S. Wong, “Interference management for multimediafemtocell networks with coalition formation game,” in Proc. of IEEE Int’l Conf. onCommun. (ICC), Budapest, Hungary, June 2013.120Bibliography[68] B. Ma, M. H. Cheung, V. W. S. Wong, and J. Huang, “Hybrid overlay/underlaycognitive femtocell networks: A game theoretic approach,” IEEE Trans. WirelessCommun., vol. 14, no. 6, pp. 3259–3270, June 2015.[69] B. Ma, B. Niu, Z. Wang, and V. W. S. Wong, “Joint power and channel allocationfor multimedia content delivery using millimeter wave in smart home networks,” inProc. of IEEE Global Commun. Conf. (GLOBECOM), Austin, TX, Dec. 2014.[70] B. Ma, H. Shah-Mansouri, and V. W. S. Wong, “Multimedia content delivery inmillimeter wave home networks,” IEEE Trans. Wireless Commun., vol. 15, no. 7,pp. 4826–4838, July 2016.[71] H. Feng, H. Wang, X. Chu, and X. Xu, “On the tradeoff between optimal relayselection and protocol design in hybrid D2D networks,” in Proc. of IEEE Int’l Conf.on Commun. (ICC), London, UK, June 2015.[72] B. Ma, H. Shah-Mansouri, and V. W. S. Wong, “A matching approach for powerefficient relay selection in full duplex D2D networks,” in Proc. of IEEE Int’l Conf.on Commun. (ICC), Kuala Lumpur, Malaysia, May 2016.[73] M. J. Osborne and A. Rubinstein, A Course in Game Theory. MIT Press, 1994.[74] W. Saad, Z. Han, M. Debbah, A. Hjorungnes, and T. Basar, “Coalitional gametheory for communication networks: A tutorial,” IEEE Signal Processing Magazine,vol. 26, no. 5, pp. 77–97, Sep. 2009.[75] L. A´. Ko´czy, “A recursive core for partition function form games,” Theory and De-cision, vol. 63, no. 1, pp. 41–51, Aug. 2007.[76] J. Andrews, H. Claussen, M. Dohler, S. Rangan, and M. Reed, “Femtocells: Past,present, and future,” IEEE J. Sel. Areas Commun., vol. 30, no. 3, pp. 497–508, Apr.2012.[77] P. Xia, V. Chandrasekhar, and J. G. Andrews, “Open vs. closed access femtocellsin the uplink,” IEEE Trans. Wireless Commun., vol. 9, no. 12, pp. 3798–3809, Dec.2010.[78] D. Ray, A Game-Theoretic Perspective on Coalition Formation. New York, USA:Oxford University Press, 2008.[79] K. R. Apt and A. Witzel, “A generic approach to coalition formation,” Int’l GameTheory Review, vol. 11, no. 03, pp. 347–367, Sep. 2009.[80] W. Saad, Z. Han, T. Basar, M. Debbah, and A. Hjorungnes, “A coalition formationgame in partition form for peer-to-peer file sharing networks,” in Proc. of IEEEGlobal Commun. Conf. (GLOBECOM), Miami, FL, Dec. 2010.121Bibliography[81] V. Conitzer and T. Sandholm, “Complexity of constructing solutions in the corebased on synergies among coalitions,” Artificial Intelligence, vol. 170, no. 6, pp.607–619, May 2006.[82] X. Deng and C. H. Papadimitriou, “On the complexity of cooperative solution con-cepts,” Mathematics of Operations Research, vol. 19, no. 2, pp. 257–266, May 1994.[83] D. Ngo, L. Le, and T. Le-Ngoc, “Distributed Pareto-optimal power control for util-ity maximization in femtocell networks,” IEEE Trans. Wireless Commun., vol. 11,no. 10, pp. 3434–3446, Oct. 2012.[84] L. Wang, J. Chen, X. Wei, J. Cui, and B. Zheng, “First-order-reflection MIMOchannel model for 60 GHz NLOS indoor WLAN systems,” in Proc. of IEEE Int’lConf. on Communication Systems (ICCS), Macau, China, Nov. 2014.[85] A. Alkhateeb, O. El Ayach, G. Leus, and R. W. Heath, “Channel estimation andhybrid precoding for millimeter wave cellular systems,” IEEE J. Sel. Topics SignalProcess., vol. 8, no. 5, pp. 831–846, July 2014.[86] I. Toyoda, T. Seki, K. Iigusa, H. Sawada, Y. Fujita, A. Miura, and N. Orihashi,“Reference antenna model with side lobe for TG3c evaluation,” IEEE 802.15-06-0474-00-003c, Mar. 2007.[87] H. Shokri-Ghadikolaei, L. Gkatzikis, and C. Fischione, “Beam-searching and trans-mission scheduling in millimeter wave communications,” in Proc. of IEEE Int’l Conf.on Commun. (ICC), London, UK, June 2015.[88] R. R.-F. Liao and A. T. Campbell, “A utility-based approach for quantitative adap-tation in wireless packet networks,” Wireless Networks, vol. 7, no. 5, pp. 541–557,Sep. 2001.[89] H. Shokri-Ghadikolaei and C. Fischione, “The transitional behavior of interferencein millimeter wave networks and its impact on medium access control,” IEEE Trans.Commun., vol. 64, no. 2, pp. 723–740, Feb. 2016.[90] M. A. Duran and I. E. Grossmann, “An outer-approximation algorithm for a class ofmixed-integer nonlinear programs,” Mathematical Programming, vol. 36, no. 3, pp.307–339, 1986.[91] R. Fletcher and S. Leyffer, “Solving mixed integer nonlinear programs by outer ap-proximation,” Mathematical Programming, vol. 66, no. 1-3, pp. 327–349, Aug. 1994.[92] M. Grant, S. Boyd, and Y. Ye, “CVX: Matlab software for disciplined convex pro-gramming, version 2.1,” Mar. 2015.122Bibliography[93] “The MOSEK optimization software,” Online at http://www.mosek.com, accessed:Oct. 2016.[94] R. G. Michael and S. J. David, “Computers and intractability: A guide to the theoryof NP-completeness,” WH Freeman & Co., San Francisco, 1979.[95] G. Miao, N. Himayat, and G. Li, “Energy-efficient link adaptation in frequency-selective channels,” IEEE Trans. Commun., vol. 58, no. 2, pp. 545–554, Feb. 2010.[96] J. G. Andrews, S. Buzzi, W. Choi, S. V. Hanly, A. Lozano, A. C. K. Soong, andJ. C. Zhang, “What will 5G be?” IEEE J. Sel. Areas Commun., vol. 32, no. 6, pp.1065–1082, June 2014.[97] T. S. Rappaport, F. Gutierrez, E. Ben-Dor, J. N. Murdock, Y. Qiao, and J. Tamir,“Broadband millimeter-wave propagation measurements and models using adaptive-beam antennas for outdoor urban cellular communications,” IEEE Trans. Antennasand Propagation, vol. 61, no. 4, pp. 1850–1859, Apr. 2013.[98] T. S. Rappaport, E. Ben-Dor, J. N. Murdock, and Y. Qiao, “38 GHz and 60 GHzangle-dependent propagation for cellular and peer-to-peer wireless communications,”in Proc. of IEEE Int’l Conf. on Commun. (ICC), Ottawa, Canada, June 2012.[99] T. Bai and R. W. Heath, “Coverage and rate analysis for millimeter-wave cellularnetworks,” IEEE Trans. Wireless Commun., vol. 14, no. 2, pp. 1100–1114, Feb. 2015.[100] T. Riihonen, S. Werner, and R. Wichman, “Hybrid full-duplex/half-duplex relayingwith transmit power adaptation,” IEEE Trans. Wireless Commun., vol. 10, no. 9,pp. 3074–3085, Sep. 2011.[101] ——, “Mitigation of loopback self-interference in full-duplex MIMO relays,” IEEETrans. Signal Processing, vol. 59, no. 12, pp. 5983–5993, Dec. 2011.[102] D. W. K. Ng, E. S. Lo, and R. Schober, “Dynamic resource allocation in MIMO-OFDMA systems with full-duplex and hybrid relaying,” IEEE Trans. Commun.,vol. 60, no. 5, pp. 1291–1304, May 2012.[103] K. Li, Q. Zhang, S. Kwong, M. Li, and R. Wang, “Stable matching-based selection inevolutionary multiobjective optimization,” IEEE Trans. Evolutionary Computation,vol. 18, no. 6, pp. 909–923, Dec. 2014.[104] R. T. Marler and J. S. Arora, “Survey of multi-objective optimization methods forengineering,” Structural and Multidisciplinary Optimization, vol. 26, no. 6, pp. 369–395, Apr. 2004.[105] Y. Gu, W. Saad, M. Bennis, M. Debbah, and Z. Han, “Matching theory for futurewireless networks: Fundamentals and applications,” IEEE Commun. Mag., vol. 53,no. 5, pp. 52–59, May 2015.123Bibliography[106] D. B. West, Introduction to Graph Theory. Prentice Hall, 2001.[107] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning,1st ed. Addison-Wesley Longman Publishing Co., Inc., 1989.[108] H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval ResearchLogistics Quarterly, vol. 2, no. 1-2, pp. 83–97, Mar. 1955.124Appendix AProof of Theorem 4.1Since constraint (4.28b) is affine, to prove that problem (4.28) is strictly convex, we needto show that its objective function is strictly convex as well. To do so, we calculate thesecond-order derivative of−Cli,rj (Psi,rj ). Notice that the first term of the objective functionof problem (4.22) is linear in Psi,rj . We rewrite Cli,rj(Psi,rj) as follows:Cli,rj (Psi,rj) = B log2(Ψli,rj(Psi,rj)), (A.1)whereΨli,rj(Psi,rj) = 1 +hrj ,diPrj ,di(Psi,rj )hsi,diPsi,rj +N0. (A.2)According to (A.1), the second-order derivative of −Cli,rj (Psi,rj) can be written as:BΨ′2li,rj(Psi,rj)Ψ2li,rj(Psi,rj)−BΨ′′li,rj(Psi,rj)Ψli,rj(Psi,rj), (A.3)whereΨ′li,rj(Psi,rj) (A.4)=N0√4hsi,rjhLIhrj ,dihsi,diP2si,rj+ 4hsi,rjhLIN0hrj ,diPsi,rj +N20h2rj ,di125Appendix A. Proof of Theorem 4.1(hsi,di(√4hsi,rjhLIhrj ,dihsi,diP2si,rj+ 4hsi,rjhLIN0hrj ,diPsi,rj +N20h2rj ,di−N0hrj ,di)+ 2hsi,rjhLIhsi,diPsi,rj + 2hsi,rjhLIN0)hrj ,di2hLI(hsi,diPsi,rj +N0)2ln 2,andΨ′′li,rj(Psi,rj) = (A.5)−Ωli,rj(Psi,rj)hLI(hsi,diPsi,rj +N0)3 (4hsi,rjhLIhrj ,dihsi,diP2si,rj+ 4hsi,rjhLIN0hrj ,diPsi,rj +N20h2rj ,di) 32ln 2,in whichΩli,rj(Psi,rj) (A.6)= N0hrj ,dih2si,di(4hsi,rjhLIhrj ,dihsi,diP2si,rj+ 4hsi,rjhLIN0hrj ,diPsi,rj +N20h2rj ,di) 32+ 8N0h2si,rjh2LIh2rj ,dih3si,diP3si,rj+N0hrj ,di(18h2si,rjh2LIN0hrj ,dih2si,di− 6hsi,rjhLIN0h2rj ,dih3si,di)P 2si,rj+N0hrj ,di(12h2si,rjh2LIN20hrj ,dihsi,di − 6hsi,rjhLIN20h2rj ,dih2si,di)Psi,rj−N40h4rj ,dih2si,di + 2h2si,rjh2LIN40h2rj ,di.Note that when Psi,rj ≥ 0, Ψli,rj(Psi,rj) > 0 and Ψ′li,rj(Psi,rj ) > 0. If Ψ′′li,rj(Psi,rj) is negative,(A.3) is always positive. Note that Ψ′′li,rj(Psi,rj ) is definitely negative if Ωli,rj (Psi,rj) > 0. Wenow show that Ωli,rj(Psi,rj) > 0. We first calculate the first-order derivative of Ωli,rj(Psi,rj)as follows:Ω′li,rj(Psi,rj) (A.7)= 6hsi,rjhLIN0h2rj ,dihsi,di(2hsi,diPsi,rj +N0)126Appendix A. Proof of Theorem 4.1(hsi,di√4hsi,rjhLIhrj ,dihsi,diP2si,rj+ 4hsi,rjhLIN0hrj ,diPsi,rj +N20h2rj ,di−N0hrj ,dihsi,di+ 2hsi,rjhLIhsi,diPsi,rj + 2hsi,rjhLIN0).Since Ωli,rj(0) = 2h2si,rjh2LIN30hrj ,di > 0 and Ω′li,rj(Psi,rj) > 0, we have Ωli,rj(Psi,rj) > 0.Thus, Ψ′′li,rj (Psi,rj ) < 0. Therefore, the second-order derivative of −Cli,rj(Psi,rj), given in(A.3), is positive, which completes the proof. 127
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Cognitive spectrum access, multimedia content delivery,...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Cognitive spectrum access, multimedia content delivery, and full-duplex relaying in wireless networks Ma, Bojiang 2016
pdf
Page Metadata
Item Metadata
Title | Cognitive spectrum access, multimedia content delivery, and full-duplex relaying in wireless networks |
Creator |
Ma, Bojiang |
Publisher | University of British Columbia |
Date Issued | 2016 |
Description | Due to the growing number of wireless communication devices and emerging bandwidth-intensive applications, the demand of data usage is increasing rapidly. Utilizing various radio access technologies and multiple frequency bands in wireless networks can provide efficient solutions to meet the growing demand of data. These techniques are promising for the fifth generation (5G) wireless communication systems. However, to fully exploit their benefits, spectrum and spatial reuse, power saving, throughput and utility enhancement are crucial issues. In this thesis, we propose different resource allocation algorithms to address the aforementioned issues in wireless communication networks. First, we study the resource allocation problem for a hybrid overlay/underlay cognitive cellular network. We propose a hybrid overlay/underlay spectrum access mechanism to improve the spectrum and spatial reuse. We formulate the resource allocation problem as a coalition formation game among femtocell users, and analyze the stability of the coalition structure. We propose an efficient algorithm based on the solution concept of recursive core. The proposed algorithm achieves a stable and efficient spectrum allocation. Next, we study the resource allocation problem for multimedia content delivery in millimeter wave (mmWave) based home networks. We characterize different usage scenarios of multimedia content delivery. We formulate a joint power and channel allocation problem, which captures the spectrum and spatial reuse of mmWave communications, based on a network utility maximization framework. The problem is a non-convex mixed integer programming (MIP) problem. We reformulate the non-convex MIP problem into a convex MIP problem and propose a resource allocation algorithm based on the outer approximation method. We also develop an efficient heuristic algorithm which has a substantially lower complexity than the outer approximation based algorithm. Finally, we study full-duplex relay-assisted device-to-device (D2D) communication in mmWave based wireless networks. To design an efficient relay selection and power allocation scheme, we formulate a multi-objective combinatorial optimization problem, which balances the trade-off between power consumption and system throughput. The problem is transformed into a weighted bipartite matching problem. We then propose a joint relay selection and power allocation algorithm, which can achieve a Pareto optimal solution in polynomial time. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2017-01-21 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0340549 |
URI | http://hdl.handle.net/2429/60167 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2017-02 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2017_february_ma_bojiang.pdf [ 2.54MB ]
- Metadata
- JSON: 24-1.0340549.json
- JSON-LD: 24-1.0340549-ld.json
- RDF/XML (Pretty): 24-1.0340549-rdf.xml
- RDF/JSON: 24-1.0340549-rdf.json
- Turtle: 24-1.0340549-turtle.txt
- N-Triples: 24-1.0340549-rdf-ntriples.txt
- Original Record: 24-1.0340549-source.json
- Full Text
- 24-1.0340549-fulltext.txt
- Citation
- 24-1.0340549.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0340549/manifest