Video over Cognitive Radio Networks: A Cross-Layer Optimization Approach by Donglin Hu A dissertation submitted to the Graduate Faculty of Auburn University in partial fulfillment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 7, 2012 Keywords: Cognitive Radio, Femtocell, Cooperative Relay, Scalable Video Coding, Successive Interference Cancellation, Interference Alignment Copyright 2012 by Donglin Hu Approved by Shiwen Mao, Chair, Associate Professor of Electrical and Computer Engineering Prathima Agrawal, Ginn Distinguished Professor of Electrical and Computer Engineering Chwan-Hwa Wu, Professor of Electrical and Computer Engineering Ming Liao, Professor of College of Sciences and Mathematics Tin-Yau Tam, Professor of College of Sciences and Mathematics Abstract Cognitive radios (CR) are intelligent radio devices that can sense the radio environment and adapt to changes in the radio environment. CR represents a new paradigm of wireless communica- tions and networking by efficiently sharing spectrum between licensed users and secondary users. To harvest the high potential of CRs, the mainstream CR research has focused on developing effec- tive spectrum sensing and access techniques. Although considerable advances have been achieved, the important problem of guaranteeing application performance has not been well studied. The first part of this dissertation develops effective algorithms and protocols for spectrum sensing and access. First, we present a spectrum sensing error aware MAC protocol for a CR net- work collocated with multiple primary networks. Second, we consider the problem of interference mitigation via channel assignment and power allocation for CR users. The second part of this dissertation focuses on the problem of optimized video streaming over CR networks. First, we tackle the problem of scalable video multicast in emerging infrastructure- based CR networks. Second, we investigate the more challenging problem of streaming multiple videos over multi-hop CR networks. Cooperative CR networks are discussed in the third part of this dissertation. First, we investi- gate the problem of cooperative relay in CR networks for further enhanced network performance. Then, we study the problem of cooperative relay in CR networks for video streaming incorporating interference alignment techniques. In the fourth part of this dissertation, we consider femtocell CR networks, where femto base stations (FBS) are deployed to greatly improve network coverage and capacity. First, we investi- gate the problem of generic data multicast in femtocell networks. Second, we tackle the problem of streaming scalable videos in femtocell CR networks. ii This dissertation research provides a new perspective on how robust multi-user video stream- ing can be achieved in highly dynamic CR networks. It is among the first efforts to address the important area of video over CR networks, and offers systematic and comprehensive results and solutions. The findings may shed new light on the feasibility of CR networks in transporting real- time video and be useful for developing practical CR video systems. iii Acknowledgments First of all, I would like to express the deepest appreciation to my advisor and committee chair Prof. Shiwen Mao, who led me into this exciting area of wireless networking research and provided me with valuable support and assistance throughout my doctoral program. Without his enlightening guidance and persistent support this dissertation would not have been possible. I also would like to thank the other members of my dissertation committee, Prof. Prathima Agrawal, Prof. Chwan-Hwa Wu, and Prof. Ming Liao, for their valuable comments and sugges- tions regarding my research work. I am also benefited very much from the courses taught by Prof. Jitendra K. Tugnait. I am very grateful to my Master?s advisor Prof. Nedret Billor for her guidance in Mathematics and Statistics. Special thanks should be given to Prof. Tin-Yau Tam for his help in my work. I highly appreciate the friendship from my friends at Auburn University, including Dr. Tong Liu, Dr. Fangyang Shen, Dr. In Keun Son, Yingsong Huang, Xi Yu, Jing Ning, Yu Wang, and many others. I thank them for the discussion, cooperation, and assistance during these years. In addition, I am very grateful to Prof. Mao?s wife, Prof. Yihan Li for elaborate Thanksgiving food. I really enjoy the Thanksgiving parties at their house. Finally, I show my all appreciation to my dear wife Jiahui Shen, my two adorable sons Lucas and Lewis, my parents, my parents-in-law, my uncle Yukang Hu and my cousin Hao Tan. Without their caring and support, the achieving of my dissertation is impossible. iv Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Major Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Dissertation Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Cognitive Radio Networking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Background and Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 System Model and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.1 Primary Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.2 CR Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.3 Spectrum Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 CR MAC Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4.1 Network Model and Assumptions . . . . . . . . . . . . . . . . . . . . . . 14 2.4.2 Sensing Error Aware CR MAC Protocol . . . . . . . . . . . . . . . . . . 15 2.4.3 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4.4 Simulation Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.5 Co-channel and Adjacent Channel Interference Mitigation . . . . . . . . . . . . . 33 2.5.1 Network Model and Assumptions . . . . . . . . . . . . . . . . . . . . . . 34 2.5.2 Channel Selection and Power Allocation . . . . . . . . . . . . . . . . . . 40 v 2.5.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3 Video over CR Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2 Background and Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3 System Model and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3.1 Primary Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3.2 Infrastructure-based CR Networks . . . . . . . . . . . . . . . . . . . . . . 59 3.3.3 Multi-hop CR networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.3.4 Spectrum Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.3.5 Video Performance Measure . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.4 Video over Infrastructure Based CR Networks . . . . . . . . . . . . . . . . . . . . 63 3.4.1 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.4.2 Optimized Video Multicast in CR Networks . . . . . . . . . . . . . . . . 66 3.4.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.5 Video over Multi-hop CR Networks . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.5.1 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.5.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.5.3 Dual Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.5.4 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4 Cooperative CR Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.2 Background and Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.3 CR and Cooperative Networking . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.3.1 Network Model and Assumptions . . . . . . . . . . . . . . . . . . . . . . 108 4.3.2 Cooperative Relay in CR Networks . . . . . . . . . . . . . . . . . . . . . 109 vi 4.3.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4.4 Cooperative CR Networks with Interference Alignment . . . . . . . . . . . . . . . 120 4.4.1 Network Model and Assumptions . . . . . . . . . . . . . . . . . . . . . . 121 4.4.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 4.4.3 Solution Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.4.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 4.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 5 CR Femtocell Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 5.2 Background and Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 5.3 Multicast in Femtocell Networks with Superposition Coding and Successive Inter- ference Cancellation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 5.3.1 System Model and Problem Statement . . . . . . . . . . . . . . . . . . . 148 5.3.2 Reformulation and Power Allocation . . . . . . . . . . . . . . . . . . . . 151 5.3.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 5.4 Video over CR Femtocell Networks . . . . . . . . . . . . . . . . . . . . . . . . . 162 5.4.1 System Model and Preliminaries . . . . . . . . . . . . . . . . . . . . . . 163 5.4.2 MGS Video over Femtocell CR Networks . . . . . . . . . . . . . . . . . 167 5.4.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 6 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 6.2 Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 6.3 Open Problems and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 vii List of Figures 1.1 Spectrum measurement results [1]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1 The discrete-time two-state Markov model for the state of channel m, Sm, for m = 1,2,...,M. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Time slot structure: a time slot consists of a sensing phase and a transmission phase. . 12 2.3 The CR secondary network is collocated with M primary networks. . . . . . . . . . . 14 2.4 The time slot structure of the proposed sensing error aware CR MAC protocol. . . . . 16 2.5 Illustration of am,k as a monotone function of k, when ?m = 0.3, ?m = 0.3, and ?K = 7. 19 2.6 Throughput versus false alarm probability (with 95% confidence intervals for the sim- ulation results). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.7 Throughput versus miss detection probability (with 95% confidence intervals for the simulation results). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.8 Throughput versus channel utilization (with 95% confidence intervals for the simula- tion results). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.9 Collision probability with primary users when the maximum tolerable collision prob- ability is ? = 3.5%. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.10 Total throughput of primary users when they become more active. . . . . . . . . . . . 33 2.11 The primary and CR network model. . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 viii 2.12 The polyhedral outer approximation of a logarithm functiony = log2(x) inx0?x?x3. 43 2.13 An example of the distributed algorithm operation with two CR users. . . . . . . . . . 48 2.14 CR network throughput versus the number of licensed channels. . . . . . . . . . . . . 50 2.15 CR network throughput versus primary user channel utilization. . . . . . . . . . . . . 50 2.16 CR network throughput versus spectrum sensing error probabilities. . . . . . . . . . . 51 2.17 CR network throughput versus the ACI factor. . . . . . . . . . . . . . . . . . . . . . . 52 2.18 Composition of the total interference measured in the simulations as a function of ACI factor ?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.19 Interference. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.1 An infrastructure-based CR network collocated with N primary networks. . . . . . . . 59 3.2 The structure of a time slot. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.3 Illustration of the multi-hop video CR network architecture. . . . . . . . . . . . . . . 61 3.4 The cut-through switching model for video data. . . . . . . . . . . . . . . . . . . . . 61 3.5 Average PSNR of all multicast users. . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.6 The original (the right one) and decoded Frame 53 (the left one) at user 1 in group 1. . 78 3.7 Average PSNR of all users versus ?n (with 95% confidence intervals). . . . . . . . . . 78 3.8 Average PSNR of all users versus N (with 95% confidence intervals). . . . . . . . . . 79 3.9 Average PSNR of all users for various{?n,?n}values (with 95% confidence intervals). 80 ix 3.10 GoP average PSNRs of a tagged user in Group 1, when its channel condition varies over time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.11 Topology of the multi-hop CR network. Note that only video source nodes, video destination nodes, and those nodes along the precomputed paths are shown in the topology. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.12 Illustrate the convergence of the distributed algorithm. . . . . . . . . . . . . . . . . . 99 3.13 Video PSNRs versus spectrum sensing error. . . . . . . . . . . . . . . . . . . . . . . 100 3.14 Video PSNRs versus primary user channel utilization ?. . . . . . . . . . . . . . . . . . 101 3.15 Impact of time slot duration on received video quality. . . . . . . . . . . . . . . . . . 101 3.16 Comparison of MPEG-4 FGS video with H.264/SVC MGS video under various chan- nel utilizations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 3.17 Comparison of MPEG-4 FGS video with H.264/SVC MGS video under various false alarm probabilities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.1 Illustration of colocated primary and CR networks. The CR network consists of a number cooperative relay links, each consisting of a CR transmitter, a CR relay and a CR receiver. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.2 Illustration of the protocol operation of AF and DF, where Si ? Ri represents the transmission from source to relay and Ri ? Di represents the transmission from relay to destination, for the ith cooperative relay link. . . . . . . . . . . . . . . . . . . 112 4.3 Throughput performance versus number of licensed channels. . . . . . . . . . . . . . 118 4.4 Throughput performance versus primary user channel utilization. . . . . . . . . . . . . 119 x 4.5 Throughput performance versus transmit power of relay nodes. . . . . . . . . . . . . . 120 4.6 Illustration of the cooperative CR network. . . . . . . . . . . . . . . . . . . . . . . . 122 4.7 Competitive ratio E[?] defined in (4.51) versus channel utilization ?. . . . . . . . . . . 138 4.8 Received video quality for each CR user with a single channel. . . . . . . . . . . . . . 139 4.9 Convergence rate of the distributed algorithm with a single channel. . . . . . . . . . . 140 4.10 Reconstructed video quality vs. channel utilization ? in the multi-channel without channel bonding case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 4.11 Reconstructed video quality vs. number of transmittersK in the multi-channel without channel bonding case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 5.1 Superposition coding and successive interference cancellation. . . . . . . . . . . . . . 149 5.2 Case I vs. Case II: interference footprints. . . . . . . . . . . . . . . . . . . . . . . . . 160 5.3 Case III: impact of number of levels L. . . . . . . . . . . . . . . . . . . . . . . . . . 161 5.4 Case III: impact of MBS bandwidth B0. . . . . . . . . . . . . . . . . . . . . . . . . . 162 5.5 A femtocell CR network with one MBS and four FBS?s. . . . . . . . . . . . . . . . . 164 5.6 Rate-distortion curves of three H.264/SVC MGS videos. . . . . . . . . . . . . . . . . 167 5.7 Interference graph for the femtocell CR network shown in Fig. 5.5. . . . . . . . . . . . 175 5.8 Convergence of the two dual variables in the single FBS case. . . . . . . . . . . . . . 181 5.9 Single FBS: received video quality vs. number of channels (computed with (9) and measured by PSNR). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 xi 5.10 Single FBS: received video quality vs. number of channels (measured by MS-SSIM). . 183 5.11 Single FBS: received video quality vs. channel utilization. . . . . . . . . . . . . . . . 184 5.12 Interfering FBS?s: received video quality vs. number of channels. . . . . . . . . . . . 185 5.13 Interfering FBS?s: received video quality vs. sensing error probability. . . . . . . . . . 185 5.14 Interfering FBS?s: received video quality vs. bandwidth of the common channel. . . . 186 5.15 Video quality achieved by the algorithms when they are only executed for 5% of the time slot duration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 xii List of Tables 2.1 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 Sequential Fixing (SF) Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.3 Channel Assignment Algorithm for CR Link k . . . . . . . . . . . . . . . . . . . . . 46 2.4 Power Allocation Algorithm for CR Link k . . . . . . . . . . . . . . . . . . . . . . . 47 3.1 The Sequential Fixing (SF) Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.2 The Greedy Algorithm (GRD1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.3 The Refined Greedy Algorithm (GRD2) for Each Time Slot . . . . . . . . . . . . . . 74 3.4 Algorithm for Tile Scheduling in a Time Slot . . . . . . . . . . . . . . . . . . . . . . 75 3.5 The Sequential Fixing Algorithm (SF) for Problem OPT-CRV . . . . . . . . . . . . . 88 3.6 The Greedy Algorithm for Channel Scheduling . . . . . . . . . . . . . . . . . . . . . 91 3.7 Distribution Algorithm for Path Selection . . . . . . . . . . . . . . . . . . . . . . . . 93 4.1 Algorithm for Computing the Optimal Sensing Threshold . . . . . . . . . . . . . . . . 111 4.2 Simulation Parameters and Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.3 Basis Computation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 4.4 Comparison of Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . 131 4.5 Algorithm for the Case of a Single Channel . . . . . . . . . . . . . . . . . . . . . . . 133 4.6 Channel Selection Algorithm for the Case of Multiple Channels without Channel Bonding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 5.1 Power Allocation Algorithm For Case II . . . . . . . . . . . . . . . . . . . . . . . . . 157 5.2 Power Allocation Algorithm For Case III . . . . . . . . . . . . . . . . . . . . . . . . 159 5.3 Algorithm for the Case of Single FBS . . . . . . . . . . . . . . . . . . . . . . . . . . 173 5.4 Algorithm for the Case of Multiple Non-Interfering FBS?s . . . . . . . . . . . . . . . 174 5.5 Channel Allocation Algorithm for Case of Interfering FBS?s . . . . . . . . . . . . . . 176 xiii Chapter 1 Introduction 1.1 Background Due to significant advances in wireless access technologies and the proliferation of wireless devices and applications, there is a fundamental change in wireless network traffic. As predicted by a Cisco study, wireless data is expected to grow to 6.3 Exabytes per month by 2015, a 26- fold increase over 2010, and 66% of the increase in future wireless data traffic will be video re- lated [2]. Such dramatic increase in wireless video traffic is driven by the proliferation of mobile PCs, smartphones, tablets, etc., with 300 Million to 400 Million new mobile phone users adopting mobile services around the world and 120,000 new base stations (BS) added every year to meet the compelling need for ubiquitous access of mobile multimedia data. Such fundamental changes in wireless data volume and composition bring about great chal- lenges for the design and operation of wireless access networks. The capacity of existing and future wireless networks will be greatly stressed. Although allocating more spectrum may help, we are facing the problem of spectrum depletion since it is not a regenerable resource. Improving spec- trum efficiency thus becomes ultimate important. In addition, Quality of Service (QoS)/Quality of Experience (QoE) provisioning in wireless networks also becomes a very important problem in order to enable high quality video services in legacy and emerging wireless networks. Since most of the increase in wireless video will be concentrated in the hot-spot areas, interference be- comes the major limiting factor of network capacity and QoS provisioning. Effective interference exploitation and mitigation technologies are needed to achieve more efficient use of the spectrum and power resources. Among various potential techniques, we consider Cognitive radios (CR) as an effective so- lution to meeting the critical demand in wireless network capacity and video provisioning. We 1 1 1 1 1 Figure 1.1: Spectrum measurement results [1]. also incorporate advanced wireless communications and networking technologies in the context of CR networks, such as cooperative communications, interference mitigation and alignment, and femtocells, for optimizing the quality of multiuser video communications. A CR is an advanced device with interface to sense the radio environment, and dynamically access idle frequency bands so that CR networks are able to be deployed with existing primary network and improve network capacity. CR was motivated by a measurement study of FCC on the spectrum utilization, where many allocated spectrum are found to be seriously underutilized even in metropolitan areas (see Fig. 1.1). The CR concept represents a significant paradigm change in spectrum regulation and utilization, from exclusive use by licensed users (or, primary users) to sharing spectrum among licensed and unlicensed users (or, secondary or CR users). Although the basic concept of CR is intuitive, it is challenging to design effective CR medium access control (MAC) protocols to fully capitalize CR?s potential. In order to exploit transmission opportunities in licensed channels, the tension between primary user protection and CR user spectrum access should be balanced. In addition, CR users access the licensed channels according to the sensing results. It is critical to take channel sensing errors into account in the design of CR MAC protocols. 2 Coupled with the depleting spectrum, interference will become the major capacity limiting factor. Thus, effective interference mitigation techniques are indispensable to realize the high po- tential of CRs. There are two types of interference that should be considered in such multi-channel environment. The first type, co-channel interference (CCI), is due to the coexisting transmitters occupying the same band as the victim receiver. The second type is adjacent channel interference (ACI), which is in the form of power leakage from adjacent channels. Both types of interference should be considered in the design of CR networking protocols. Cooperative wireless relay represents another new paradigm for wireless communications and networking. It allows wireless relay nodes to assistant transmitters in data delivery. The objective of cooperative communication is to achieve cooperative diversity. Cooperation among wireless nodes enables opportunistic use of energy and bandwidth resources in wireless networks. Recently, researchers have been exploring the idea of combining these two techniques for enhanced network-wide performance [3, 4]. A femtocell is a small cellular base station (BS), typically used for serving approved users within a small coverage (e.g., a house). Femtocells usually have broadband wireline connections to the service provider network, which can be exploited to coordinate the transmissions of multiple femtocells for improved network-wide performance. Femtocells are shown effective in extending coverage, improving capacity, and reducing both power consumption and interference. Most of the benefits are achieved by the reduced distance of wireless transmissions, i.e., by bringing BS?s closer to users [5]. Although considerable understandings have been gained on various aspects of CR. the prob- lem of guaranteeing application performance has not been the focus of major CR research. To this end, we find spectrum-intensive and rate-adaptive video as a reference application, makes excellent use of the enhanced spectrum efficiency in CR networks. Unlike data, where each bit should be de- livered, video is loss tolerant and rate adaptive. They are highly suited for CR networks, where the available bandwidth heavily depends on primary user behavior. We adopt scalable video coding, such as fine grained scalability (FGS) and medium grain scalable (MGS), to encode video streams. 3 We tackle the problems of video over various CR networking paradigms, such as infrastructure based CR networks, multi-hop CR ad hoc networks, cooperative relay based CR networks, and CR femtocell networks. We formulate cross-layer optimization problems that incorporates vari- ous system parameters and control knobs, and develop effective solution algorithms with proved optimal performance of tight performance bounds. 1.2 Major Contributions The focus of this dissertation research is realtime video streaming in wireless networks, in particular, cognitive radio (CR) networks. The major contributions are summarized as follows. We first work on a sensing error-aware MAC protocol that coordinates dynamic spectrum access for CR users, which considers channel sensing errors in the protocol design [6]. We de- velop analytical models to evaluate the performance of the proposed protocols. The accuracy of the analysis is demonstrated via our simulation study. In addition, interference mitigation in CR networks is crucial not only for primary user protection, but also the quality of service of CR user themselves. Therefore, we next consider the problem of interference mitigation via channel assignment and power allocation for CR users [7]. We propose both an RLT-based centralized al- gorithm and a distributed greedy algorithm which only needs local channel gain information. The distributed algorithm is shown to outperform the centralized algorithm and a heuristic algorithm with considerable gains in our simulations. We further start to tackle the challenging problem of optimized real-time video multicast in an infrastructure-based CR network. The base station of the CR network exploits the spectrum opportunities in multiple licensed channels to multicast videos to groups of CR users [8]. A novel formulation of the CR video multicast system is developed, which considers important cross-layer design factors such as scalable video coding, video rate control, spectrum sensing, dynamic spec- trum access, modulation, scheduling, and primary user protection. The design objective is to optimize CR video quality while protecting primary users from harmful collisions. Although the problem can be solved using advanced optimization techniques, we propose a sequential fixing 4 algorithm and a greedy algorithm with low complexity and proven optimality gap. We also inves- tigate the more challenging problem of video streaming over multi-hop CR networks [9] which is formulated as a mixed integer nonlinear programming (MINLP) problem. We develop a central- ized sequential fixing algorithm to derive upper and lower bounds for the achievable video quality, and then apply dual decomposition to develop a distributed algorithm with proven optimality and convergence conditions. Next, we investigate the problem of cooperative relay in CR networks for further enhanced network performance [10]. In particular, we focus on the comparison of two representative co- operative relay strategies, decode-and-forward (DF) and amplify-and-forward (AF). Cross-point with the AF and DF curves are found when some parameter is valid, which indicates that each of them performs better in a certain parameter range and there is no case of dominance for the two strategies. We further extend our work to video streaming in cooperative CR networks [11], which incorporates interference alignment, a recent information theoretic breakthrough that allows cur- rent transmission of multiple signals. For the initial stochastic programming formulation, we first develop a reformulation that significantly reduces computational complexity. We then develop distributed optimal algorithms for the cases of a single channel and multi-channel with channel bounding, with proven convergence and convergence rate. We also developed a greedy algorithm for the multi-channel without channel bounding case, with bounded performance. This work is among the first efforts to harvest the information theoretic advances on interference alignment in the broader network context and practical perspective. Femtocell networks are another theme that my dissertation focus on. We first investigate the problem of data multicast in femtocell networks that incorporates superposition coding and suc- cessive interference cancellation [12]. The objective is to minimize the total base station power consumption, while guaranteeing successful decoding of the multicast data at each user. We for- mulate a MINLP problem and reformulate it into a simpler form. To address the problem, we develop optimal and near-optimal algorithms for three typical connection scenarios, and derive upper and lower performance bounds. We also study the problem of streaming real-time scalable 5 videos in femtocell cognitive radio networks [13], with a multistage stochastic programming prob- lem formulation. The proposed algorithms produce optimal solution in the case of non-interfering FBS?s and near-optimal solution with proven lower bound in the case of interfering FBS?s. This dissertation research provides a new perspective on how robust multi-user video stream- ing can be achieved in highly dynamic CR networks. It is among the first efforts to address the important area of video over CR networks, and offers systematic and comprehensive results and solutions. The findings may shed new light on the feasibility of CR networks in transporting real- time video and be useful for developing practical CR video systems. 1.3 Dissertation Outline The reminder of this dissertation is organized as follows. In Chapter 2, we present our work on effective spectrum sensing and access protocols for CR networks. We introduce the general architecture of CR networks and present three protocol designs and analysis for different CR networking paradigms, including a sensing error aware CR MAC protocol and resource allocation for co-channel and adjacent channel interference mitigation in CR networks. In Chapter 3, we investigate the problem of video streaming over three different CR net- work paradigms, including multiuser video multicast in the downlink of an infrastructure-based CR network and multiuser video unicast in a multi-hop CR network without any fixed network infrastructure. In Chapter 4, we focus on cooperative CR networks. We compare and analyze two typical co- operative relay strategies in CR networks and investigate the problem of multiuser video streaming over a cooperative relay CR network by adopting interference alignment. In Chapter 5, we consider femtocell networks. In particular, we tackle the problem of generic data mulicast in the downlink of femtocell networks that employs Superposition Codign (SC) and Successive Interference Cancellation (SIC), as well as resource allocation and quality of service (QoS) provisioning for multiuser video streaming in CR femtocell networks. 6 We conclude the dissertation and discuss our future work in Chapter 6. 7 Chapter 2 Cognitive Radio Networking 2.1 Introduction According to Cisco?s recent study, wireless data traffic is expected to increase by a factor of 66 times by 2013. Much of this future wireless data traffic will be video based services driven by the need for ubiquitous access to wireless multimedia content. Such drastic increase in traffic demand will significantly stress the capacity of future wireless networks. Cognitive radios (CR) provide an effective solution to meeting this critical demand by ex- ploiting co-deployed networks and aggregating underutilized spectrum for future wireless net- works [1, 14, 15]. CR was motivated by the spectrum measurements by the FCC, where a signifi- cant amount of the assigned spectrum is found to remain underutilized. CR represents a paradigm change in spectrum regulation and access, from exclusive use by primary users to shared spectrum for secondary users, which can enhance spectrum utilization and achieve high throughput capacity. Although the basic concept of CR is intuitive, it is challenging to design efficient cognitive network protocols to fully capitalize CR?s potential. In order to exploit transmission opportunities in licensed bands, the tension between primary user protection and secondary user spectrum ac- cess should be judiciously balanced. Spectrum sensing and spectrum access are the two key CR functions. Important design factors include (i) how to identify transmission opportunities, (ii) how secondary users determine, among the licensed channels, which channel(s) and when to access for data transmission, and (iii) how to avoid harmful interference to primary users under the om- nipresent of spectrum (or, channel) sensing errors. These are the problems that should be addressed in the medium access control (MAC) protocol design for CR networks. Although very good under- standings on the availability process of licensed channels have been gained recently [16,17], there 8 is still a critical need to develop analytical models that take channel sensing errors into account for guiding the design of CR MAC protocols. To support many bandwidth-intensive applications in CR networks, it is desirable to achieve high network throughput under the constraint of limited interference to primary users. Due to the use of open space as transmission medium, wireless network capacity is usually constrained by interference. A CR user?s transmission will generate interference not only to the neighboring primary users, but also to other CR users sharing the same or adjacent channels. Therefore, inter- ference mitigation is crucial not only for primary user protection, but also for the quality of service of CR user themselves. Effective interference mitigation techniques are indispensable to realize the high potential of CRs. The remainder of this chapter is organized as follows. The related work is discussed in Sec- tion 2.2. The system model and preliminary results are illustrated in Section 2.3. We present a sensing error aware MAC protocol in Section 2.4. Effective channel interference mitigation is discussed in Section 2.5. Section 2.6 concludes the chapter. 2.2 Background and Related Work CR has been considered as a ?spectrum agile radio? that enables dynamic spectrum access to exploit transmission opportunities in licensed spectrum bands [14,15]. Several CR MAC protocols have been proposed in the literature. In [18], Le and Hossain propose a MAC protocol for oppor- tunistic spectrum access in CR networks. A decentralized cognitive MAC protocol is developed in [19] that allows secondary users to explore spectrum opportunities without a central coordinator or a dedicated control channel. In a piece of recent work [20], Su and Zhang propose a negotiation- based sensing policy (NSP), in which a secondary user knows which channels are already sensed and will choose a different channel to sense. In [21], the authors consider two types of hardware constraints: sensing constraint and transmission constraint. In [22], based on the information ob- tained by a delegate secondary user, each secondary user group selects and switches to the best data channel for data communication during the next period. In [23], the authors describe a policy 9 such that a secondary user selects the channel that has the highest successful transmission proba- bility to access. Many prior works [16, 18, 20, 21] assume perfect channel sensing, within which secondary users can always sense the channel correctly. Sensing errors are not considered. The joint design of opportunistic spectrum access and sensing policies is studied in a recent work [24] in the presence of sensing errors. The authors develop a separation principle that decouples the designs of sensing and access policy. This interesting study is based on a constrained partially ob- servable Markov decision process (POMDP) formulation and thus has an exponentially growing computational complexity [24]. In [25, 26], the authors propose MAC protocols for multi-hop CR networks without the support of common control channels, but each CR user is requested to keep a list of available channels updated. The speed and accuracy of sensing process are high demanding. Co-Channel Interefence (CCI) and Adjacent Channel Interference (ACI) are the two major factors limiting wireless network capacity. The impact of CCI on network performance is well- known and comprehensively investigated in [27]. Recently, the impact of ACI has attracted con- siderable interest in the wireless community. In [28, 29], the need was demonstrated for careful channel selection to mitigate ACI in IEEE 802.11 based systems. The impact of both CCI and ACI on network throughput and performance was evaluated in [30?32]. The interference models have been developed to analyze the channel interference in a few papers. In [33], the problem of statistical-physical modeling of CCI was investigated to analyze the outage probabilities in wireless networks and to design interference-aware transceivers. ACI was described by a simple quantifica- tion model that was verified by testbed experiments in [29]. In [34], a model for the aggregate ACI in TV white space was developed to demonstrate that the weighted sum of the total ACI power should be kept below certain threshold as well as ACI in each adjacent channel. A commonly used approach to reduce CCI is to assign different channels to neighboring transmitters [13, 35]. In [36, 37], frequency domain iterative multi-user detectors were adopted for CCI cancellation. A low-cost CCI avoidance MAC scheme was presented in [38]. In [39], ACI was minimized by op- timizing reception of television receivers. In [40], Gidony and Kalet addressed the ACI mitigation problem by exploiting antenna diversity. In [41], statistical modeling of the aggregate interference 10 0 (idle) 1 (busy)1m 1-1m 2m 1-2m Figure 2.1: The discrete-time two-state Markov model for the state of channel m, Sm, for m = 1,2,...,M. in a spectrum underlay CR network is proposed, in which CR networks coexist with primary net- works and power constraints are imposed on the CR users to keep their power below the noise floor of primary receivers. 2.3 System Model and Preliminaries 2.3.1 Primary Network We assume the primary users access the channels following a synchronous slot structure as in prior work [14, 20, 42]. The channel states are independent to each other and each of the M chan- nels evolves over time following a discrete-time two-state Markov process, as shown in Fig. 2.1. Such channel model has been validated by recent measurement studies [14, 16, 20]. We define the network state vector in slot t as vectorS(t) = [S1(t),S2(t),...,SM(t)], where Sm(t) denotes the state of channel m, for m = 1,2,???,M. When channel m is idle, we have Sm(t) = 0; when channel m is busy, we have Sm(t) = 1. Let ?m and ?m be the transition probability of remaining in state 0 and the transition proba- bility from state 1 to 0 for channel m, respectively. Let ?m = Pr(Sm = 1) denote the utilization of channel m with respect to primary user transmissions. Let ?m = Pr(Sm = 0) be the probability that channel m is idle (i.e., not being used by primary users). We then have ?m = lim T?? 1 T Tsummationdisplay t=1 Sm(t) = 1??m1?? m +?m (2.1) ?m = 1?Pr(Sm = 1) = ?m1?? m +?m . (2.2) 11 Sensing Phase Transmission Phase A Time Slot Figure 2.2: Time slot structure: a time slot consists of a sensing phase and a transmission phase. 2.3.2 CR Network As presented in prior work [16, 20, 43], we assume that each secondary user is equipped with two transceivers: a control transceiver that operates over a dedicated control channel, which we assume is always available (e.g., a channel in the industrial, scientific and medical (ISM) band), and a data transceiver that is used for data communications through the M licensed channels. The data transceiver consists of an SDR that can be tuned to any of the M licensed channels to transmit and receive data. Secondary users also use their transceivers for spectrum sensing and exchanging sensing results. We assume CR nodes access the licensed channels following the same time slot structure [14]. Each time slot is divided into two phases, the sensing phase and the transmission phase, as shown in Fig. 2.2. In the sensing phase, a CR node chooses one of the M channels to sense using one of its transceivers, and then exchanges sensed channel information with other CR nodes using the other transceiver over the control channel. During the transmission phase, the CR transmitter and/or relay transmit data frames on licensed channels that are believed to be idle based on sensing results, using one or both of the transceivers. 2.3.3 Spectrum Sensing We explicitly consider channel sensing errors in the design. During the sensing process, two kinds of detection errors may occur. A false alarm refers to the case when an idle channel is considered busy. Consequently, the CR nodes will not attempt to access that channel and a spectrum opportunity will be wasted. A miss detection refers to the case when a busy channel is 12 considered idle. Since CR nodes will attempt to access this channel in the transmission phase, collisions with primary user transmissions will occur subsequently. We adopt hypothesis test to detect the availability of channel m. The null hypothesis Hm0 is ?channel m is idle.? The alternative hypothesis Hm1 is ?channel m is busy.? Let ?mi and ?mi be the probabilities of false alarm and miss detection, respectively, when CR node i senses channel m. We have ?mi = Pr{?mi = 1|Hm0 } and (2.3) ?mi = Pr{?mi = 0|Hm1 }, (2.4) where ?mi ?{0,1}is the channel m sensing result of channel m at node i. 2.4 CR MAC Protocol In this section, we present a channel sensing error aware MAC protocol for a CR network collocated with multiple primary networks. We assume primary users access the licensed channels following a synchronous time slot structure [14, 20]. The channel states are independent to each other and each evolves over time following a discrete-time Markov process [14, 16]. Secondary users use their software-defined radio (SDR)-based transceivers to tune to any of the licensed channels, to sense and estimate channel status and to access the channels when they are found (or, believed) to be available. In particular, we develop two channel sensing polices, with which secondary users collabora- tively sense the licensed channels and predict channel states. With the memoryless sensing policy, each secondary user chooses one of the M licensed channels to sense with equal probability. Dur- ing the sensing phase, secondary users also exchange sensing results through a separate control channel. This sensing policy is further improved with a mechanism to spread out secondary users to sense different channels, therefore reducing the chance that a channel is not sensed by any of the users. When spreading out secondary users to the channels, the mechanism also considers 13 Primary Network M Primary Network 2 Primary Network 1 Spectrum Spectrum Spectrum Spectrum CR network user Primary network User Primary network base stationChannel 1 Channel 2 Channel M ... ... Figure 2.3: The CR secondary network is collocated with M primary networks. the autocorrelation of channel processes to obtain more accurate sensing results. This is termed improved sensing policy. These two sensing polices are then incorporated into the p-Persistent Carrier Sense Multiple Access (CSMA) mechanism to make sensing error aware CR MAC protocols. We analyze the pro- posed CR MAC protocols with respect to the interference and throughput performance and derive closed-form expressions. Primary user protection is achieved via tunning the channel access prob- ability p of p-Persistent CSMA according to the interference analysis. The CR MACs also aims to maximize the CR network throughput while satisfying the primary user protection constraints. Through simulations, we find that the analysis is highly accurate as compared to simulation results. In addition, the proposed sensing error aware CR MAC protocols outperform two existing schemes with considerable gain margins, which justify the importance of considering channel sensing errors in CR MAC design. 2.4.1 Network Model and Assumptions The network model considered in this section is illustrated in Fig. 2.3. Consider M primary networks, each allocated with a licensed channel. We assume the primary users access the channels following a synchronous slot structure as in prior work [14,20,42]. The channel state model evolves independently following a discrete Markov process (see Section 2.3.1). 14 We assume a secondary network collocated with the M primary networks, within which N secondary users take advantage of the spectrum white spaces in M licensed channels for data transmissions. For protection of primary users, the probability of collision caused by secondary user transmissions to primary users should be upper bounded by a prescribed threshold ?m, for m = 1,2,???,M. As illustrated in Section 2.3.2, we assume that each secondary user is equipped with two transceivers: a control transceiver that operates over a dedicated control channel, which we assume is always available, and a data transceiver that is used for data communications through the M licensed channels. The data transceiver consists of an SDR that can be tuned to any of the M licensed channels to transmit and receive data. Secondary users also use their transceivers for spectrum sensing and exchanging sensing results. 2.4.2 Sensing Error Aware CR MAC Protocol For the CR network described in Section 2.4.1, we develop sensing aware MAC protocols for opportunistic spectrum access. The time slot structure of the proposed MAC protocols is shown in Fig. 2.4, which consists of a sensing phase and a transmission phase. The sensing phase is further divided into ?K mini-slots, within which each secondary user senses one of the licensed channels. CR users access the channels for data transmission during the transmission phase. LetTs, Tms, and Tdata denote the duration of a time slot, a mini-slot, and the transmission phase, respectively (see Fig. 2.4), we have Ts = ?K?Tms +Tdata. (2.5) We first discuss the two key components of the proposed protocols, i.e., channel sensing and channel access, and then analyze their performance with respect to primary user protection and the expected throughput. 15 slot slot t t idle channel 1 channel M idle busy tbusy 1 2 K Sensing Phase Transmission Phase Sensing Phase Transmission Phase 1 2 K Figure 2.4: The time slot structure of the proposed sensing error aware CR MAC protocol. Sensing Phase The first key element of the proposed MAC protocols is spectrum, or channel sensing. Al- though precise and timely channel state information is highly desirable for opportunistic spectrum access and primary user protection, contiguous full-spectrum sensing is both energy inefficient and hardware demanding. Since we assume a secondary user is equipped with one transceiver for spectrum sensing, i.e., the data transceiver with SDR capability, only one of the licensed channels can be sensed by the secondary user at a time. During the sensing phase (see Fig. 2.4), a secondary user picks a licensed channel and keeps on sensing it for one or multiple mini-slots. As discussed in Section 2.3.3, two kinds of detection errors may occur: false alarm and miss detection. We assume all secondary users have the same probability of detection errors when sensing channel m, m = 1,2,???,M. Let ?m and ?m denote the probabilities of false alarm and miss detection on channel m, respectively. The spectrum sensing performance can be represented by the Receiver Operation Characteristic (ROC) curve, where (1??m) is plotted as a function of ?m [14]. For a specific channel m in a certain time slot 16 t, the sensing error probabilities can be written as: Pr(Wm,i = 1|Sm = 0) = ?m,for all i = 1,2,??? (2.6) Pr(Wm,i = 0|Sm = 1) = ?m,for all i = 1,2,???, (2.7) where Wm,i is the ith sensing result of channel m and Sm is state of channel m. We assume that the sensing results from different users are independent and the sensing results in different mini-slots are also independent to each other. Suppose a secondary user continues to sense channel m for k mini-slots and obtains k sensing results. The conditional probability that channel m is available after the kth sensing mini-slot, denoted by am,k, can be derived as am,k = Pr(Sm = 0|Wm,1 = ?m,1,???,Wm,k = ?m,k) = Pr(Wm,i = ?m,i,i = 1,???,k|Sm = 0)Pr(Sm = 0)summationtext1 j=0 Pr(Wm,i = ?m,i,i = 1,???,k|Sm = j)Pr(Sm = j) = Pr(Sm = 0) producttextk i=1 Pr(Wm,i = ?m,i|Sm = 0)summationtext 1 j=0 Pr(Sm = j) producttextk i=1 Pr(Wm,i = ?m,i|Sm = j) = bracketleftBigg 1 + Pr(Sm = 1)Pr(S m = 0) kproductdisplay i=1 Pr(Wm,i = ?m,i|Sm = 1) Pr(Wm,i = ?m,i|Sm = 0) bracketrightBigg?1 = bracketleftbigg 1 +?dmm ?k?dmm Pr(Sm = 1)Pr(S m = 0) bracketrightbigg?1 = parenleftbigg 1 +?dmm ?k?dmm ?m? m parenrightbigg?1 , (2.8) where dm is the number of observations whose sensing result is 0 on channel m, and ?m and ?m are defined as follows. ?m = Pr(Wm,i = 0|Sm = 1)Pr(W m,i = 0|Sm = 0) = ?m1?? m , for ?m,i = 0 (2.9) ?m = Pr(Wm,i = 1|Sm = 1)Pr(W m,i = 1|Sm = 0) = 1??m? m , for ?m,i = 1. (2.10) 17 For the secondary user, it is also possible that it obtains some of the k sensing results by local measurements, and receives the remaining sensing results from the control channel in the case that some other secondary users are sensing the same channel m. By abuse of notation, we also use am,k to denote the conditional channel availability probability in this case, due to independence of the sensing results. We plot am,k as a function of k for the channel idle and busy cases in Fig. 2.5, using the same parameters as one of the simulations (see Section 2.4.4). We have the following proposition for am,k. Definition 2.1. A random variable X is said to be dominated by Y in the sense of stochastic ordering if Pr(X?x)?Pr(Y ?x) for all x Proposition 2.1. When channel m is idle, am,k is a monotone increasing function of k; when channel m is busy, am,k is a monotone decreasing function of k in the sense of stochastic ordering. Proof. From the defintion of am,k in (2.8), it follows that Pr(am,k??1) = Pr ? ? bracketleftBigg 1 + ?m? m parenleftbigg ? m 1??m parenrightbiggsummationtextki=1 ?Wm,iparenleftbigg1?? m ?m parenrightbiggsummationtextki=1Wm,ibracketrightBigg?1 ??1 ? ? = Pr parenleftBiggparenleftbigg ?m 1??m parenrightbiggsummationtextki=1 ?Wm,iparenleftbigg1?? m ?m parenrightbiggsummationtextki=1Wm,i ? parenleftbigg1 ?1 ?1 parenrightbigg? m ?m parenrightBigg = Pr parenleftBigg ksummationdisplay i=1 bracketleftbigg Wm,ilog parenleftbigg1?? m ?m parenrightbigg ? ?Wm,ilog parenleftbigg1?? m ?m parenrightbiggbracketrightbigg ??m parenrightBigg (2.11) where ?Wm,i = 1?Wm,i. Since ?m < 0.5 and ?m < 0.5 for practical sensors, both log parenleftBig 1??m ?m parenrightBig and log parenleftBig 1??m ?m parenrightBig are positive. If Sm(t) = 0, we have that Pr(Wm,i = 1) < Pr(Wm,i = 0) = Pr( ?Wm,i = 1). 18 0 2 4 6 80.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 k a m,k (a) Channel m is idle 0 2 4 6 80.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 k a m,k (b) Channel m is busy Figure 2.5: Illustration ofam,k as a monotone function ofk, when?m = 0.3, ?m = 0.3, and ?K = 7. It follows that Pr(am,k??1) < Pr(am,k+1 ??1). That is, am,k is a monotone increasing function of k in the sense of stochastic ordering. Similarly, we can show that Pr(am,k??0) < Pr(am,k+1??0) when Sm(t) = 1. That is, am,k is a monotone decreasing function of k in the sense of stochastic ordering when the channel is busy. During the sensing phase, each secondary user chooses one channel to sense with equal prob- ability at the beginning of the time slot. Secondary users also report their sensing results over the control channel, and share the corresponding channel sensing results during the mini-slots. Two threshold probabilities ?0 < ?1 are used for decision making. ? If the availability of channel m, i.e., am,k, is below ?0, the channel is believed to be busy and the secondary users will wait till the next time slot to start sensing again. ? If the availability of channel m is between ?0 and ?1, secondary users will keep on sensing the same channel to obtain more sensing results for more accurate estimation of the channel state, until the maximum number of mini-slots, ?K, is reached. 19 ? If the availability of channel m exceeds ?1, the channel is believed to be idle and the sec- ondary users stop sensing and prepare to access the channel (see Section 2.4.2). The stop time Km when secondary users stop sensing channel m, is a random variable that takes value between 1 and ?K, the maximum number of mini-slots that can be used for sensing (see Fig. 2.4). If we have ?0 ?1. There are Um users sensing channel m and UmKm observations are available after mini-slot Km, which is also a random variable. We first derive the conditional probability for event Km = 1, as Pr(Km = 1|Um = u, Sm = 0) = Pr(am,u??1) = summationdisplay d1m??1m,u ? ??u d1m ? ??bracketleftBig(? m)u?d 1m(1?? m)d 1m bracketrightBig , (2.17) 21 where d1m is the number of observations whose sensing result is 0 in the first mini-slot. Following similar reasoning as in (2.17), we can obtain the conditional probability for the event that the stop time Km = 2 as Pr(Km = 2|Um = u, Sm = 0) = Pr[(?0 1) 3: Run the power allocation algorithm given in Table 2.4; 4: Find the channel m? with the minimum Um?k value: m? = argminm?Ak(t)Umk (vectorP); 5: Set xm?k = 0 and remove m? fromAk(t); 6: END WHILE 7: Run the power allocation algorithm given in Table 2.4 with all the xmk ?s determined. The distributed algorithm consists of two tiers: (i) the upper tier is a channel assignment algorithm, which decides which channel to access for a CR transmitter, and (ii) the low tier is a power allocation algorithm, which decides how much power can be allocated to transmit on each available channel. In the channel assignment algorithm, we assume the transmit powers have been allocated to each available channel; the power allocation, denoted by an M?K vector vectorP, can be obtained from the power allocation algorithm. Define the capacity of CR link k if it uses channel m as Umk = log2(1 +?mk ). (2.61) Then in each loop, the channel with the lowest Umk (vectorP) is removed from the available channel set Ak(t) and the corresponding xmk is set to 0, until only one available channel is left. The complete channel assignment algorithm is presented in Table 2.3. With the algorithm, initially we assume CR transmitter k uses all the channels inA(t) in Step 1. Then in Steps 2?6, we iteratively remove the channels with the minimum capacity gain, until only one channel is left. Finally, the transmit power is determined for the chosen channel in Step 7. In the power allocation algorithm, the main idea is to iteratively allocate a small amount of power ? to the CR link that can achieve the largest increase in (2.52). The algorithm is presented in Table 2.4. Let vector?mk be a vector whose [(k?1)?M +m]-th element is ? and all other elements are 0, indicating that power ? is allocated to CR link k on channel m. Obviously, if CR link k is allocated with the additional power ?, the throughput of this CR link will increase; if another CR 46 Table 2.4: Power Allocation Algorithm for CR Link k 1: Initialize Pmk = 0 for all k?? and m?Ak(t); 2: Calculate EARNmk for all m?Ak(t); 3: IF (summationtextm?A(t)Pmk +???) & (Bmj (vectorP +vector?mk )?? for j?Pm) 4: EARNmk =summationtextn?A(t)[Unk(vectorP + vector?mk )?Unk(vectorP)]; 5: ELSE 6: EARNmk = 0; 7: END IF 8: Calculate COSTmk?,k for all k?negationslash= k and m?Ak?(t), where Costmk?,k =summationtextn?A(t)[Unk(vectorP + vector?mk?)?Unk(vectorP)]; 9: Broadcast all EARNmk and COSTmk?,k to all other CR links; 10: Calculate PROFITmk for all k?? and m?Ak(t), where PROFITmk = EARNmk +summationtextknegationslash=k? COSTmk,k?; 11: Find{m?,k?}= argmaxk??&m?Ak(t)PROFITmk ; 12: IF (PROFITm?k? > 0) 13: vectorP = vectorP + vector?m?k? ; 14: Go to Step 2; 15: ELSE. 16: The algorithm is terminated with solution vectorP; 17: END IF linkk?negationslash= k is allocated with the additional power ?, the throughput of CR linkk will decrease. The increase and decrease of the throughput of the CR link are termed earning and cost, respectively: EARNmk is the throughput increase for CR link k on channel m if it gets the additional power ?; COSTmk?,k is the throughput decrease for CR link k if another CR link k? negationslash= k on channel m wins the additional power allocation ?. In Steps 3?7, we calculate EARNmk , but set it to 0 if either (2.54) or (2.55) is not satisfied. In Steps 10?11, the net throughput gains (or, profit) of all possible power allocations are calculated and the combination with the largest profit is selected. In Steps 12?13, the CR link with the largest positive profit wins the additional power allocation ?, if its profit is positive. Otherwise, the power allocation algorithm is terminated with solution vectorP, because no further power allocation can improve the total throughput. A Simple Example To better explain our distributed algorithm, consider a simple example with two CR users 1 and 2. As shown in Fig. 2.13, for each channel m, CR transmitter 1 calculates 47 Calculate Broadcast Compare EARN1m COST2,1m PROFIT =1m Calculate EARN2m COST1,2m EARN1m COST1,2m + EARN2m COST2,1m + PROFIT2m = CR Transmitter 1 CR Transmitter 2 Figure 2.13: An example of the distributed algorithm operation with two CR users. EARNm1 and COSTm2,1 and CR transmitter 2 calculates EARNm2 and COSTm1,2. The two nodes then broadcast the values to each other. Once a node receives the COST from the other node, it calculates its PROFIT as shown in the figure. The power vector?mk is allocated to the node with the larger PROFITmk . This power allocation algorithm is terminated if both PROFITmk from the two nodes are non-positive. Once the power allocation algorithm is terminated, the channel with the lowest Umk (vectorP) is removed from the available channel setAk(t), until only one available channel is left, as given in Table 2.3. 2.5.3 Performance Evaluation We evaluate the performance of the proposed algorithms using MATLAB (for solving the LP relaxations). For the results reported in this section, there are M = 6 licensed channels (unless otherwise specified) with identical transition probabilities P01m = 0.4 and P10m = 0.3 for all m. The maximum collision probability with primary users is ?m = 0.2 for all m. The transmit power of primary base station is 30 dBm and the maximum acceptable interference for the primary users is ? = 10 dBm. There are K = 6 transmitter and receiver pairs in the CR network. The power of 48 CR transmitter is limited to ?m = 27 dBm for all m. The false alarm probability is ?mn = 0.3 and the miss detection probability is ?mn = 0.3 for all m and n, unless otherwise specified. Rayleigh block fading channels are used in the simulations. We consider four types of results: (i) the upper bound obtained by solving the RLT relaxation as presented in Section 2.5.2; (ii) the centralized SF algorithm solution given in Table 2.2 (a lower bound); (iii) the distributed greedy algorithm given in Tables 2.3 and 2.4; and (iv) a simple central- ized heuristic algorithm. With the centralized heuristic algorithm, each CR transmitter chooses the best available channel to access to exploit multiuser diversity gain. When the channels are assigned and all the xmk ?s are fixed. Then it solves the reduced problem (2.52) with MATLAB Optimization Toolbox to find a near-optimal power allocation. Each point in the curves is the average of 10 simulations with different random seeds. The 95% confidence intervals are plotted as error bars, which are negligible in all the cases. We first examine the impact of the number of channels M on the overall throughput of the CR network. In Fig. 2.14, we increase M from 4 to 8, and plot the total throughput of the CR network. As expected, the more licensed channels, the more spectrum opportunities for CR users and the higher the network throughput. The curves of both SF and the heuristic algorithm have lower slop than that of the distributed greedy algorithm. It implies that the greedy algorithm is more efficient in exploiting the addition spectrum opportunities for CR transmissions. We find the upper bound quite loose, while the lower bound is reasonably tight. In Fig. 2.15, we investigate the impact of primary user channel utilization? on the CR network throughput. The throughput curves achieved by the algorithms are plotted when ? is increased from 0.3 to 0.7. Clearly, a smaller ? allows more spectrum opportunities for CR transmissions. When the primary users get more busy, the spectrum opportunities for CR users decreases and the throughput of all the three algorithms decreases. It can be seen from the figure that all the three curves decrease as ? gets larger. The CR network throughput of the distributed greedy algorithm is better than that of the simple heuristic algorithm and that of the centralized SF algorithm. In particular, when ? = 0.3, the distributed greedy algorithm achieves a normalized throughput gain 49 4 4.5 5 5.5 6 6.5 7 7.5 80 10 20 30 40 50 Number of Licensed Channels (M) Throughput (Mbps) Upper bound Proposed scheme Heuristic scheme Lower bound Figure 2.14: CR network throughput versus the number of licensed channels. 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.72 4 6 8 10 12 14 16 18 20 Channel Utilization (?) Throughput (Mbps) Proposed scheme Heuristic scheme Lower bound Figure 2.15: CR network throughput versus primary user channel utilization. of 27.84% over the simple heuristic algorithm, and a normalized throughput gain of 117.62% over SF. When ? = 0.7, the distributed algroithm achieves normalized throughput gains of 19.98% and 73.67% over the simple heuristic and SF, respectively. Next we examine the impact of spectrum sensing errors on the CR network throughput. In Fig. 2.16, we test five pairs of {?,?} values as follows: {0.2,0.48}, {0.24,0.38}, {0.3,0.3}, 50 0.2 0.25 0.3 0.35 0.4 0.45 0.50 5 10 15 20 Probability of False Alarm (?) Throughput (Mbps) Proposed scheme Heuristic scheme Lower bound Figure 2.16: CR network throughput versus spectrum sensing error probabilities. {0.38,0.24}, and{0.48,0.2}. The CR network throughputs achieved by the algorithms are plot- ted in the figure. It is interesting to see that the throughput performance gets worse when the probability of one of the two sensing errors gets large. We can trade-off between false alarm and miss detection probabilities to find the optimal operating point for spectrum sensing. Again, the throughput performance of the greedy algorithm is superior to that of the heuristic algorithm and doubles that of the SF algorithm. We then investigate the impact of the ACI factor ? on the CR network throughput. The simulation results are presented in Fig. 2.17, where ? is increased from 0 to 0.5. As expected, the CR network throughput is degraded by the presence of ACI. The severer the ACI, the lower the CR network throughput. When ? is increased from 0 to 0.5, the throughput degradations are 4.0647 Mbps, 3.8068 Mbps, and 3.3793 Mbps for the distributed algorithm, the simple heuristic, and SF, respectively. The distributed greedy algorithm outperforms both the simple heuristic algorithm and SF with considerable gaps for the entire range of ? considered. We also measure both types of interference in the simulations and exam the impact of the ACI factor ? on channel interference. In Fig. 2.18, we increase ? from 0 to 0.5 with step 0.1 and plot the measured average interference in the plots. The total average interference for each licensed 51 0 0.1 0.2 0.3 0.4 0.50 2 4 6 8 10 12 14 16 18 20 Adjacent Channel Interference Factor (?) Throughput (Mbps) Proposed scheme Heuristic scheme Lower bound Figure 2.17: CR network throughput versus the ACI factor. channel is shown in Fig. 2.18(a), which consists of both ACI and CCI. It can be seen that the total interference increases as ? gets larger, since there is more power leakage from adjacent channels. The ACI and CCI components are plotted in Figs. 2.18(b) and 2.18(c), respectively. It can be seen that ACI almost linearly increases with ?. When ? = 0, ACI is zero for all the three schemes since there is no power leakage from neighboring channels. When ? = 0.5, the ACI of the proposed distributed scheme is about 92.32% of that of the simple heuristic and 58.93% of that of SF. The proposed distributed algorithm curve has the lowest slop among the three schemes, indicating more effective control of ACI as ? increases. The fractions of ACI in the total average interference are plotted in Fig. 2.18(d) for the three schemes. The fraction increases as ? gets larger, from 0% to about 22%. Clearly ACI should be considered in the resource allocation and protocol design of CR networks. Finally, we validate our proposed spectrum sensing and access scheme. We set the maximum allowable collision probability ? to be 0.2 and increase channel utilization ? from 0.3 to 0.7 in steps of 0.1. In Fig. 2.19, the measured collision rates with primary uses are plotted, along with the ? = 0.2 curve. It can be seen that the measured collision rate is always kept below ?, showing that 52 0 0.1 0.2 0.3 0.4 0.5 0.8 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 Adjacent Channel Interference Factor (?) Average Channel Interference ( ?W) Lower bound Proposed scheme Heuristic scheme (a) Average total interference on a channel 0 0.1 0.2 0.3 0.4 0.50 0.1 0.2 0.3 0.4 0.5 Adjacent Channel Interference Factor (?) Average Adjacent Channel Interference ( ?W) Lower boundProposed scheme Heuristic scheme (b) Average ACI on a channel 0 0.1 0.2 0.3 0.4 0.50.8 1 1.2 1.4 1.6 1.8 2 Adjacent Channel Interference Factor (?) Average Co?channel Interference ( ?W) Lower bound Proposed scheme Heuristic scheme (c) Average CCI on a channel 0 0.1 0.2 0.3 0.4 0.50 0.05 0.1 0.15 0.2 0.25 Adjacent Channel Interference Factor (?) Portion of ACI in Total Interference Lower bound Proposed scheme Heuristic scheme (d) Portion of ACI in the total interference Figure 2.18: Composition of the total interference measured in the simulations as a function of ACI factor ?. the proposed spectrum sensing and access scheme is quite effective with regard to primary user protection. 2.6 Conclusions In this chapter, we first studied the problem of design and analysis of MAC protocols for CR networks in this chapter. In particular, we proposed and analyzed two opportunistic multi- channel MAC protocols, adopting a memoryless sensing policy and an improved sensing policy, respectively. The impact of imperfect sensing (in the forms of miss detection and false alarm) 53 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.70.15 0.16 0.17 0.18 0.19 0.2 0.21 Channel Utilization (?) Collision Probability Maximum allowable Simulated Figure 2.19: Interference. are explicitly considered in the CR MAC design. We developed analytical models to evaluate the performance of the proposed protocols. Our simulation study demonstrates the accuracy of the analysis, as well as the superior throughput performance of the proposed CR MACs over existing approaches. Then, we investigated the problem of CCI and ACI mitigation via channel assignment and power allocation in CR networks. The objective was to maximize the total CR network throughput while keeping both collision rate and interference with primary users below tolerance thresholds. We proposed an RLT-based centralized SF algorithm that computes near-optimal solutions, and a distributed greedy algorithm that only uses local channel gain information. The proposed algo- rithms are evaluated with simulations. The distributed greedy algorithm is shown to outperform both the centralized SF algorithm and a centralized heuristic algorithm with considerable gains. 54 Chapter 3 Video over CR Networks 3.1 Introduction Video content delivery over wireless networks is expected to grow drastically in the coming years. The compelling need for ubiquitous video content access will significantly stress the ca- pacity of existing and future wireless networks. To meet this critical demand, the Cognitive Radio (CR) technology provides an effective solution that can effectively exploit co-deployed networks and aggregate underutilized spectrum for future video-aware wireless networks. The high potential of CRs has attracted substantial interest. The mainstream CR research has focused on developing effective spectrum sensing and access techniques (eg., see [14, 15]). Although considerable advances have been achieved, the important problem of guaranteeing ap- plication performance has not been well studied. We find video streaming can make excellent use of the enhanced spectrum efficiency in CR networks. Unlike data, where each bit should be delivered, video is loss-tolerant and rate-adaptive [49, 50]. They are highly suited for CR net- works, where the available bandwidth depends on primary user transmission behavior. Graceful degradation of video quality can be achieved as spectrum opportunities evolve over time. CR is an evolving concept with various network models and levels of cognitive functional- ity [14, 15]. IEEE 802.22 Wireless Regional Area Networks (WRAN) is the first CR standard for reforming broadcast TV bands, where a base station (BS) controls medium access for customer- premises equipments (CPEs) [51]. Therefore, we first consider multicasting scalable videos in such an infrastructure-based CR network. The spectrum consists of multiple channels, each al- located to a primary network. The CR network is co-located with the primary networks, where a CR BS seeks spectrum opportunities for multicasting multiple video streams, each to a group of secondary subscribers. The problem is to exploit spectrum opportunities for minimizing video 55 distortion, while keeping the collision rate with primary users below a prescribed threshold. We consider scalable video coding, such as fine-grained-scalability (FGS) and medium grain scalable (MGS) videos [52, 53]. We model the problem of CR video multicast over the licensed channels as a mixed integer nonlinear programming (MINLP) problem, and then develop a sequential fixing algorithm and a greedy algorithm to solve the MINLP, while the latter has a low computational complexity and a proved optimality gap [8]. We then tackle the problem of video over multi-hop CR networks, e.g., a wireless mesh net- work with CR-enabled nodes. This problem is more challenging than the problem above due to the lack of infrastructure support. We assume each secondary user is equipped with two transceivers. To model and guarantee end-to-end video performance, we adopt the amplify-and-forward ap- proach for video data transmission, which is well-studied in the context of cooperative communi- cations [54]. This is equivalent to setting up a ?virtual tunnel? through a multi-hop multi-channel path. The challenging problem, however, is how to set up the virtual tunnels, while the available channels at each relay evolve over time due to primary user transmissions. The formulated MINLP problem is first solved using a centralized sequential fixing algorithm, which provides upper and lower bounds for the achievable video quality. We then apply dual decomposition to develop a distributed algorithm and prove its optimality as well as the convergence condition [9]. The rest of the chapter is organized as follows. We review related work in Section 3.2 and present preliminaries in Section 3.3. We examine video over infrastructure-based CR networks in Section 3.4 and over multi-hop CR networks in Section 3.5. We concludes the chapter in Sec- tion 3.6 with a discussion of open problems. 3.2 Background and Related Work The high potential of CRs has attracted considerable interest form both industry, government and academia [1, 14]. The mainstream CR research has been focused on spectrum sensing and dynamic spectrum access issues. For example, the impact of spectrum sensing errors on the design of spectrum access schemes has been addressed in several papers [6, 24, 55, 56]. The approach 56 of iteratively sensing a selected subset of available channels has been developed in the design of CR MAC protocols [6, 20, 57]. The optimal trade-off between the two kinds of sensing errors is investigated comprehensively and addressed in depth in [24]. The important issue of QoS provisioning in CR networks has been studied only in a few pa- pers [20, 58], where the objective is still focused on the so-called ?network-centric? metrics such as maximum throughput and delay [20,55]. In [55], an interesting delay throughput trade-off for a multi-cell cognitive radio network is derived, while the goal of primary user protection is achieved by stabilizing a virtual ?collision queue?. In [58], a game-theoretic framework is described for resource allocation for multimedia transmissions in spectrum agile wireless networks. In this in- teresting work, each wireless station participates in a resource management game, which is coordi- nated by a network moderator. A mechanism-based resource management scheme determines the amount of transmission opportunities to be allocated to various users on different frequency bands such that certain global system metrics are optimized. The problem of video over CR networks has been addressed only in a few recent papers. In [59], a priority virtual queue model is adopted for wireless CR users to select channel and maximize video qualities. In [60], the impact of system parameters residing in different network layers are jointly considered to achieve the best possible video quality for CR users. The problem is formulated as a Mini-Max problem and solved with a dynamic programming approach. In [61], Ali and Yu jointly optimize video parameter with spectrum sensing and access strategy. A rate- distortion model is adopted to optimize the intra-mode selection and source-channel rate with a partially observable Markov decision process (POMDP) formulation. In [62], video encoding rate, power control, relay selection and channel allocation are jointly considered for video over cooperative CR networks. The problem is formulated as a mixed-integer nonlinear problem and solved by a solution algorithm based on a combination of the branch and bound framework and convex relaxation techniques. Video multicast, as one of the most important multimedia services, has attracted considerable interest from the research community. Layered video multicast has been researched in the mobile 57 ad hoc networks [63, 64] and infrastructure-based wireless networks [52, 65]. A greedy algorithm is presented in [65] for layered video multicast in WiMAX networks with a proven optimality gap. A few recent works [47, 66, 67] have studied multi-hop CR networks. The authors formulate cross-layer optimization problem considering factors from the PHY up to the transport layer. The dual decomposition technique [68, 69] is adopted to develop distributed algorithm. We choose similar methodology in our work and apply it to the more challenging problem of real-time video streaming. 3.3 System Model and Preliminaries 3.3.1 Primary Network We consider a spectrum band consisting of M orthogonal channels with identical band- width [21]. We assume that the M channels are allocated to K primary networks, which cover different service areas. A primary network can use any of the M channels without interfering with other primary networks. We further assume that the primary systems use a synchronous slot structure as in prior work [14, 20]. Due to primary user transmissions, the occupancy of each channel evolves following a discrete-time Markov process, as validated by recent measurement studies [14, 16, 20]. In primary network k, the status of channel m in time slot t is denoted by Skm(t) with idle (i.e., Skm(t) = 0) and busy (i.e., Skm(t) = 1) states. Let ?km and ?km be the transition probability of remaining in state 0 and that from state 1 to 0, respectively, for channel m in primary network k. As discussed in Section 2.3.1, the utilization of channel m in primary network k, denoted by ?km = Pr(Skm = 1), is ?km = lim T?? 1 T summationtextT t=1S k m(t) = 1??km 1??km +?km. (3.1) 58 a1a0a2a3a4a0a5 a6a7a8a9a10a0a11 a12 a14a15a13a4a16a16a7a17 a12a19 a1a0a2a3a4a0a5 a6a7a8a9a10a0a11 a20 a14a15a13a4a16a16a7a17 a20a19 a18a21a22a23a24a25a26a27 a18a21a22a23a24a25a26a27 a18a21a22a23a24a25a26a27 a18a21a22a23a24a25a26a27 a28a29 a30a31a32a33a34a35a36 a37a38a31a35 a28a29 a30a31a32a33a34a35a36 a39a40a38a31 a38a32a40a32a41a34a30 a42a35a41a43a40a35a44 a30a31a32a33a34a35a36 a45a38a31a35 a42a35a41a43a40a35a44 a30a31a32a33a34a35a36 a39a40a38a31 a38a32a40a32a41a34a30 ... Figure 3.1: An infrastructure-based CR network collocated with N primary networks. Note that in infrastructure-based CR networks and cooperative CR networks, we assume there is only one K = 1 primary network. In infrastructure-based CR networks introduced in the sec- tion 3.4, we adopt N as the number of licensed channels since M is denoted as the number of modulation-coding schemes. 3.3.2 Infrastructure-based CR Networks As shown in Fig. 3.1, we consider a CR base station multicasts G real-time videos to G multicast groups, each of which have Ng users, g = 1,2,???,G. The base station seeks spectrum opportunities in the N channels to serve CR users. In each time slot t, the base station selects a set of channelsA1(t) to sense and a set of channelsA2(t) to access. Without loss of generality, the base station has|A1(t)|transceivers such that it can sense|A1(t)|channels simultaneously. Note that a time slot and channel combination, termed a tile, is the minimum unit for resource allocation. We adopt the same time-slot structure as in [14, 57]. , which is illustrated in Fig. 2.4. At the beginning of each time slot, the base station senses channels inA1(t) and then chooses a set 59 Spectrum sensing Data transmission Acknowledgment A time slot Figure 3.2: The structure of a time slot. of available channels for opportunistic transmissions based on sensing results. After a successful transmission, the base station will receive an ACK from the user with the highest SNR in the target multicast group. Without loss of generality, we assume that each CR network user can access all the available channels with the channel bonding/aggregation techniques [44, 70]. 3.3.3 Multi-hop CR networks As shown in Fig. 3.3, we also consider a multi-hop CR network that is co-located with the primary networks, within which S real-time videos are streamed among N CR nodes. Let Uk denote the set of CR nodes that are located within the coverage of primary network k. A video sessionl may be relayed by multiple CR nodes if sourcezl is not a one-hop neighbor of destination dl. We assume a common control channel for the CR network [20]. We also assume the timescale of the primary channel process (or, the time slot durations) is much larger than the broadcast delays on the control channel, such that feedbacks of channel information can be received at the source nodes in a timely manner. The time slot structure is the same as that in infrastructure-based CR networks. In the sensing phase, one transceiver of a CR node is used to sense one of the M channels, while the other is tuned to the control channel to exchange channel information with other CR users. Each video source computes the optimal path selection and channel scheduling based on sensing results. In the transmission phase, the channels assigned to a video session l at each link along the path form a virtual ?tunnel? connecting source zl and destination dl. As illustrated in Fig. 3.4, each node can use one or more than one channels to communicate with other nodes using the channel bonding/aggregation techniques [44, 70]. When multiple channels are available on all the links 60 Primary network user Secondary network user Primary network base station Figure 3.3: Illustration of the multi-hop video CR network architecture. idle tunnel tunnel Source zl Intermediate node Destination dl Sensing Trans- mission ACK busy busybusy Figure 3.4: The cut-through switching model for video data. along a path, multiple tunnels can be established and used simultaneously for a video session. In the acknowledgment phase, the destination sends ACK to the source for successfully received video packets through the same tunnel. We adopt amplify-and-forward for video transmission [54]. During the transmission phase, one transceiver of the relay node receives video data from the upstream node on one channel, while the other transceiver of the relay node amplifies and forwards the data to the downstream node on a different, orthogonal channel. There is no need to store video packets at the relay nodes. Error detection/correction will be performed at the destination node. As a result, we can transmit through the tunnel a block of video data with minimum delay and jitter in one time slot. 61 3.3.4 Spectrum Sensing As discussed in Section 2.3.3, two types of sensing errors may occur during the sensing pro- cess. A false alarm may lead to waste a spectrum opportunity and a miss detection may causes collision with primary users. In a multi-hop CR network, the sensing results from various users may be different. Denote H0 as the hypothesis that channel m in primary network k is idle, and H1 the hypothesis that channel m in primary network k is busy in time slot t. The conditional probability that channel m is available in primary network k, denoted by akm(t), can be derived as [8], akm(t) = Pr(H0|Wmi = ?mi , i?Ukm,?km) = bracketleftbigg 1 +parenleftbig?kmparenrightbigukmparenleftbig?kmparenrightbig|Ukm|?ukm Pr(H1|? k m) Pr(H0|?km) bracketrightbigg?1 . (3.2) where ?mi represents a specific sensing result (0 or 1),Ukm is the subset of users inUk (i.e., the set of CR nodes that are located within the coverage of primary network k) that sense channel m, ukm is the number of users inUkm observing channel m is idle, ?km represents the history of channel m in primary network k, and ?km and ?km are defined as: ?? ? ?? ?km = P(Wmi =0|H1)P(Wm i =0|H0) = ?m1??m, when ?mi = 0 ?km = P(Wmi =1|H1)P(Wm i =1|H0) = 1??m?m , when ?mi = 1. (3.3) Based on the Markov chain channel model, we have (3.4), which can be recursively expanded: ?? ? ?? Pr(H0|?km) = ?kmakm(t?1) +?kmbracketleftbig1?akm(t?1)bracketrightbig Pr(H1|?km) = 1?Pr(H0|?km). (3.4) 62 3.3.5 Video Performance Measure Both FGS and MGS videos are highly suited for dynamic CR networks. With FGS or MGS coding, each video l is encoded into one base layer with rate Rbl and one enhancement layer with rate Rel. The total bit rate for video l is Rl = Rbl +Rel. We consider peak-signal-noise-ratio (PSNR) (in dB) of reconstructed videos. As in prior work [8, 52], the average PSNR of video l, denoted as Ql, can be estimated as: Ql(Rl) = Qbl +?l(Rl?Rbl) = Q0l +?lRl, (3.5) where Qbl is the resulting PSNR when the base layer is decoded alone, ?l a constant depending on the video sequence and codec setting, and Q0l = Qbl ??lRbl. We verified the model (3.5) with several test video sequences using the MPEG-4 FGS codec and the H.264/SVC MGS codec and found it is highly accurate. Due to the real-time nature, we assume that each group of pictures (GOP) must be delivered during the next GOP window, which consists of NG time slots. Beyond that, overdue data from the current GOP will be useless and will be discarded. In infrastructure-based network, G video stream are multicast to G groups of CR user, so we choose the group index g instead of video session index l. 3.4 Video over Infrastructure Based CR Networks In this section, we examine the problem of video over infrastructure-based CR networks. We consider cross-layer design factors such as scalable video coding, spectrum sensing, opportunistic spectrum access, primary user protection, scheduling, error control and modulation. We propose efficient optimization and scheduling algorithms for highly competitive solutions, and prove the complexity and optimality bound of the proposed greedy algorithm. 63 3.4.1 Network Model Spectrum Access At the beginning of each time slot t, the CR BS senses the M channels and compute an(t) for each channel n. Based on spectrum sensing results, the base station determines which channels to access for video streaming. We adopt an opportunistic spectrum access approach, aiming to exploit unused spectrum while probabilistically bounding the interference to primary users. Let ?n?(0,1) be the maximum allowed collision probability with primary users on channel n, andptrn(t) the transmission probability on channelnfor the base station in time slott. The prob- ability of collision caused by the base station should be kept below ?n, i.e., ptrn(t)[1?an(t)]??n. In addition to primary user protection, another important objective is to exploit unused spectrum as much as possible. The transmission probability can be determined by jointly considering both objectives, as ptrn(t) = ? ?? ?? min braceleftBig 1, ?n1?an(t) bracerightBig , if 0?an(t) < 1 1, if an(t) = 1. (3.6) If ptrn(t) = 1, channel n will be accessed deterministically. If ptrn(t) = ?n/[1?an(t)] < 1, channel n will be accessed opportunistically with probability ptrn(t). Modulation-Coding Schemes At the PHY layer, we consider various modulation and channel coding combination schemes. Without loss of generality, we assume several choices of modulation schemes, such as QPSK, 16- QAM and 64-QAM, combined with several choices of forward error correction (FEC) schemes, e.g., with rates 1/2, 2/3, and 3/4. We consider M unique combinations of modulation and FEC schemes, termed Modulation-Coding (MC) schemes, in this paper. Under the same channel condition, different MC schemes will achieve different data rates and symbol error rates. Adaptive modulation and channel coding allow us to exploit user channel variations to maximize video data rate under a given residual bit error rate constraint. When a user 64 has a good channel, it should adopt an MC scheme that can support a higher data rate. Conversely, it should adopt a low-rate MC scheme when the channel condition is poor. Let{MCm}m=1,???,M be the list of available MC schemes indexed according to their data rates in the increasing order. We assume slow fading channels with coherence time larger than a time slot. Each CR user measures its own channel and feedbacks measurements to the base station when its channel quality changes. At the beginning of a time slot, the base station is able to collect the number ng,m of users in each multicast group g who can successfully decode MCm signals for m = 1,2,???,M. Since the base layer carries the most important data, the most reliable MC scheme MCb(g) should be used, where b(g) = maxi{i : ng,i = Ng}, for all g. Without loss of generality, we assume that the base layer is always transmitted using MC1. If a user?s channel is so poor that it cannot decode the MC1 signal, we consider it disconnected from the CR network. We further divide the enhancement layer into M sub-layers, where sub-layer m has rate Reg,m and uses MCm. Assuming that MCm can carry bg,m bits of video g in one tile, we denote the number of tiles for sub-layer m of video g as lg,m?0. We have Reg = Msummationdisplay m=1 Reg,m = Msummationdisplay m=1 bg,mlg,m. (3.7) Proportional Fair Allocation Since we consider video quality in this paper, we define the utility for user i in group g as Ug,i = logQg,i = logparenleftbigQbg +?gReg(i)parenrightbig, where Reg(i) is the received enhancement layer rate of user i in group g. The total utility for group g is Ug = summationtextNgi=1Ug,i. Intuitively, a lower layer should use a lower (i.e., more reliable) MC scheme. This is because if a lower layer is lost, a higher layer cannot be used at the decoder even if it is correctly received. Considering the user classification based on their MC schemes, we can rewrite Ug as follows [65]: Ug = Msummationdisplay k=1 (ng,k?ng,k+1)log parenleftBigg Qbg +?g ksummationdisplay m=1 Reg,m parenrightBigg , (3.8) 65 where ng,M+1 = 0. The utility function of the entire CR video multicast system is U = Gsummationdisplay g=1 Ug. (3.9) Maximizing U will achieve proportional fairness among the video sessions [71] 3.4.2 Optimized Video Multicast in CR Networks Outline of the Proposed Approach As discussed, the CR video multicast problem is highly challenging since a lot of design choices are tightly coupled. First, as users see different channels, such heterogeneity should be accommodated so that a user can receive a video quality commensurate to its channel quality. Sec- ond, we need to determine the video rates before transmission, which, however, depend on future channel evolution and choice of MC schemes. Third, the trade-off between primary user protection and spectrum utilization should guide the scheduling of video packets to channels. Finally, all the optimization decisions should be made in real-time. Low-complexity, but efficient algorithms are needed, while theoretical optimality bounds would be highly appealing. To address heterogeneous user channels, we adopt FGS to produce a base layer with rate Rbg and an enhancement layer with rate ?Reg. Without loss of generality, we assume Rbg is prescribed for an acceptable video quality, while ?Reg is set to a large value that is allowed by the codec. During transmission, we determine the effective rate for each enhancement layer Reg ? ?Reg depending on channel availability, sensing, and MC schemes.1 The optimal partition of the enhancement layer should be determined such that each sub-layer uses a different MC scheme. We determine the optimal partition of enhancement layers, the choices of MC schemes, and video packet scheduling as follows. First, we solve the optimal partition problem for every GoP based on an estimated (i.e., average) number of available tiles Te in the next GoP window that can be used for the enhancement layer, using algorithm GRD1 with complexity O(MGTe). The 1The proposed approach can also be used for streaming stored FGS video. 66 tile allocations are then dynamically adjusted in each time slot according to more recent (and thus more accurate) channel status using algorithm GRD2, with complexityO(MGK), whereK?Te. Second, during each time slot, video packets are scheduled to the available channels such that the overall system utility is maximized. The TSA algorithm has complexity O(N logN). Both GRD2 and TSA have low complexity and are suitable for execution in each time slot. In real-time video, overdue packets generally do not contribute to improving the received quality. We assume that the data from a GoP should be be delivered in the next GoP window consisting of TGoP time slots.2 Since the base layer is essential for decoding a video, we assume that the base layers of all the videos are coded using MC1. For the M sub-layers of the enhance- ment layer, a more important sub-layer will be coded using a more reliable (i.e., lower rate) MC scheme. At the beginning of each GoP window, all the base layers are transmitted using the avail- able tiles. Retransmissions will be scheduled if no ACK is received for a base layer packet. After the base layers are transmitted, we allocate the remaining available tiles in the GoP window for the enhancement layer. The same rule applies to the enhancement sub-layers, such that a higher sub-layer will be transmitted if and only if all the lower sub-layers are acknowledged. This is due to the decoding dependency of layered video. In each time slot t, the base station opportunistically access every channel n with probability ptrn(t) given in (3.6). Specifically, for each channel n, the base station generates a random number xn(t), which is independent of the channel history ?n(t) and uniformly distributed in [0,1]. If xn(t) ? ptrn(t), the most important packet among those not ACKed in the previous GoP will be transmitted on channel n. If an ACK is received for this packet at the end of time slot t, this packet is successfully received by at least one of the users and will be removed from the transmission buffer. Otherwise, there is a collision with primary user and this packet will remain in the transmission buffer and will be retransmitted. In the following, we describe in detail the three algorithms. 2The proposed approach also works for the more general delay requirements that are multiple GoP windows. 67 Enhancement Layer Partitioning and Tile Allocation As a first step, we need to determine the effective rate for each enhancement layer Reg ? ?Reg. We also need to determine the optimal partition of each enhancement layer. Clearly, the solutions will be highly dependent on the channel availability processes and sensing results. Recall that the base layers are transmitted using MC1 first in each GoP window. The remain- ing available tiles can then be allocated to the enhancement layers. We assume that the number of tiles used for the enhancement layers in a GoP window, Te, is known at the beginning of the GoP window. For example, we can estimate Te by computing the total average ?idle? intervals of all the N channels based on the channel model, decreased by the number of tiles used for the base layers (i.e., Rbg/bg,1). We then split the enhancement layer of each video g into M sub-layers, each occupying lg,m tiles when coded with MCm, m = 1,2,???,M. Letting vectorl = [l1,1,l1,2,???,l1,M,l2,1,???lG,M] denote the tile allocation vector, we formulate an optimization problem OPT-Part as follows. maximize: U(vectorl) = Gsummationdisplay g=1 Msummationdisplay k=1 (ng,k?ng,k+1)?log bracketleftBigg Qbg +?g ksummationdisplay m=1 bg,mlg,m bracketrightBigg (3.10) subject to: Gsummationdisplay g=1 Msummationdisplay m=1 lg,m?Te (3.11) Msummationdisplay m=1 bg,mlg,m? ?Reg, g?[1,???,M] (3.12) lg,m?0, m?[1,???,M],g?[1,???,G]. (3.13) OPT-Part is solved at the beginning of each GoP window to determine the optimal partition of the enhancement layer. The objective is to maximize the overall system utility by choosing optimal values for the lg,m?s. We can derive the effective video rates as Reg = summationtextMm=1bg,mlg,m. The for- mulated problem is a MINLP problem, which is NP-hard [65]. In the following, we present two algorithms for computing near-optimal solutions to problem OPT-Part: (i) a sequential fixing (SF) 68 algorithm based on a linear relaxation of (3.10), and (ii) a greedy algorithm GRD1 with proven optimality gap. A Sequential Fixing Algorithm With this algorithm, the original MINLP is first linearized to obtain a linear programming (LP) relaxation. Then we iteratively solve the LP, while fixing one in- teger variable in every iteration [47,72]. We use the Reformulation-Linearization Technique (RLT) to obtain the LP relaxation [45]. RLT is a technique that can be used to produce LP relaxations for a nonlinear, nonconvex polynomial programming problem. This relaxation will provide a tight up- per bound for a maximization problem. Specifically, we linearize the logarithm function in (3.10) over some suitable, tightly-bounded interval using a polyhedral outer approximation comprised of a convex envelope in concert with several tangential supports. We further relax the integer con- straints, i.e., allowing the lg,m?s to take fractional values. Then we obtain an upper-bounding LP relaxation that can be solved in polynomial time. Due to lack of space, we refer interested readers to [45] for a detailed description of the technique. We next solve the LP relaxation iteratively. During each iteration, we find the l?g,?m which has the minimum value for (?l?g,?m??l?g,?m) or (l?g,?m??l?g,?m?) among all fractional lg,m?s, and round it up or down to the nearest integer. We next reformulate and solve a new LP with l?g,?m fixed. This procedure repeats until all thelg,m?s are fixed. The complete SF algorithm is given in Table 3.1. The complexity of SF depends on the specific LP algorithm (e.g., the simplex method with polynomial- time average-case complexity). A Greedy Algorithm Although SF can compute a near-optimal solution in polynomial time, it does not provide any guarantee on the optimality of the solution. In the following, we describe a greedy algorithm, termed GRD1, which exploits the inherent priority structure of layered video and MC schemes and has a proven optimality bound. The complete greedy algorithm is given in Table 3.2, where R = summationtextGg=1 ?Reg is the total rate of all the enhancement layers and vectorei is a unit vector with ?1? at the i-th location and ?0? at all other locations. In GRD1, all the lg,m?s are initially set to 0. During each iteration, one tile is 69 Table 3.1: The Sequential Fixing (SF) Algorithm 1: Use RLT to linearize the original problem 2: Solved the LP relaxation 3: Suppose l?g,?m is the integer variable with the minimum (?l?g,?m??l?g,?m) or (l?g,?m??l?g,?m?) value among all lg,m variables that remain to be fixed, round it up or down to the nearest integer 4: If all lg,m?s are fixed, got to Step 6 5: Otherwise, reformulate a new relaxed LP with the newly fixed lg,m variables, and go to Step 2 6: Output all fixed lg,m variables and Reg =summationtextMm=1bg,mlg,m Table 3.2: The Greedy Algorithm (GRD1) 1: Initialize lg,m = 0 for all g and m 2: Initialize A ={1,2,???,G} 3: WHILE parenleftBigsummationtext G g=1 summationtextM m=1lg,m?Te and A is not empty parenrightBig 4: Find l?g,?m that can be increased by one: vectore?g,?m = argmaxg?A,m?[1,???,M] braceleftBig U(vectorl+vectoreg,m)?U(vectorl) bg,m+R/Te bracerightBig 5: vectorl =vectorl+vectore?g,?m 6: IFparenleftbigsummationtextmb?g,ml?g,m > ?Regparenrightbig 7: vectorl =vectorl?vectore?g,?m 8: Delete ?g from A 9: END IF 10: END WHILE allocated to the ?m-th sub-layer of video ?g. In Step 4, l?m,?g is chosen to be the one that achieves the largest increase in terms of the ?normalized? utility (i.e., [U(vectorl+vectoreg,m)?U(vectorl)]/[bg,m+R/Te]) if it is assigned with an additional tile. Lines 6, 7, and 8 check if the assigned rate exceeds the maximum rate ?Reg. GRD1 terminates when either all the available tiles are used or when all the video data are allocated with tiles. In the latter case, all the videos are transmitted at full rates. We have the following Theorem for GRD1. Theorem 3.1. The greedy algorithm GRD1 shown in Table 3.2 has a complexity O(MGTe). It guarantees a solution that is within a factor of (1?e?1/2) of the global optimal solution. 70 Proof. (i) Complexity: In Step 4 in Table 3.2, it takesO(MG) to solve forvectore?g,?m. Since each iteration assigns one tile to sub-layer ?m of group ?g, it takes Te iterations to allocate all the available tiles in a GoP window. Therefore, the overall complexity of GRD1 is O(MGTe). (ii) Optimality Bound: This proof is extended from a result first shown in [65] for layered videos. We first show a property of group utility Ug(vectorl), which will be used in the proof of the optimality gap. For two vectorsvectorl1g andvectorl2g, letting ? = Ug(vectorl1g)?Ug(vectorl2g), we have ? = Msummationdisplay k=1 (ng,k?ng,k+1)?log parenleftBigg 1 + summationtextk m=1?gbg,m(l 1 g,m?l 2 g,m) Qbg +summationtextkm=1?gbg,ml2g,m parenrightBigg ? Msummationdisplay k=1 ksummationdisplay m=1 (l1g,m?l2g,m)+(ng,k?ng,k+1)?log parenleftBigg 1 +?gbg,m/ bracketleftBigg Qbg + ksummationdisplay m=1 ?gbg,ml2g,m bracketrightBiggparenrightBigg ? Msummationdisplay k=1 Msummationdisplay m=1 (l1g,m?l2g,m)+(ng,k?ng,k+1)?log parenleftBigg 1 +?gbg,m/ bracketleftBigg Qbg + ksummationdisplay m=1 ?gbg,ml2g,m bracketrightBiggparenrightBigg = Msummationdisplay m=1 (l1g,m?l2g,m)+ bracketleftBig Ug(vectorl2g +bg,m)?U(vectorl2g) bracketrightBig , (3.14) where y+ = max{0,y}. The first inequality is due to the concavity of logarithm functions. Next we prove the optimality bound. Letvectorlt be the output of GRD1 after t iterations. Let the utility gap between the optimal solution and the GRD1 solution be Ft = U(vectorl?)?U(vectorlt), andvectore?g,?m(t) the argument found in Step 4 of GRD1 after t iterations. We havevectorlt =vectorlt?1 +vectore?g,?m(t) and Ft?1 = U(vectorl?)?U(vectorlt?1) ? summationdisplay g summationdisplay m (l?g,m?lg,m)+[U(vectorlt?1 +vectoreg,m(t))?U(vectorlt?1)] ? summationdisplay g summationdisplay m (l?g,m?lg,m)+[U(vectorlt?1 +vectore?g,?m(t))?U(vectorlt?1)] bg,m +R/Teb ?g,?m(t) +R/Te ?U( vectorlt)?U(vectorlt?1) b?g,?m(t) +R/Te summationdisplay g summationdisplay m [l?g,m(bg,m +R/Te)]. 71 The first inequality is due to (3.14) and the second inequality follows Step 4 of GRD1. It follows (3.11) thatsummationtextgsummationtextml?g,m?Te andsummationtextgsummationtextmbg,ml?g,m?R. We have Ft?1?(Ft?1?Ft) 2Rb ?g,?m(t)+R/Te . Solving for Ft, we have Ft?Ft?1{1?[b?g,?m(t) +R/Te]/(2R)}. Suppose the WHILE loop in Table 3.2 has been executedk times when the solution is obtained. Fk ? Fk?1{1?[b?g,?m(k) +R/Te]/(2R)} ? F0 kproductdisplay t=1 {1?[b?g,?m(t) +R/Te]/(2R)} ? F0 braceleftBigg 1?1/(2kR) ksummationdisplay t=1 [b?g,?m(t) +R/Te] bracerightBiggk . The WHILE loop exits when one or both of two constraints are violated. If summationtextgsummationtextmlg,m ?Te is violated, there is no tile that can be used. Therefore k?Te andsummationtextkt=1R/Te?R. If constraint ?A is not empty? is violated, all the videos have been allocated sufficient number of tiles and will be transmitted at full rates. We havesummationtextkt=1b?g,?m(t)?R in this case. It follows that Fk ? F0 braceleftBigg 1?1/(2kR) ksummationdisplay t=1 [b?g,?m(t) +R/Te] bracerightBiggk ? F0 [1?1/(2k)]k ? F0e?1/2. Since F0 = U(vectorl?), we have U(vectorlk) ? (1?e?1/2)U(vectorl?). Therefore, we conclude that the GRD1 solution is bounded by (1?e?1/2)U(vectorl?) and U(vectorl?). A Refined Greedy Algorithm GRD1 computes lg,m?s based on an estimate of network status vectorS(t) in the next TGoP time slots. Due to channel dynamics, the computed lg,m?s may not be exactly accurate, especially whenTGoP is large. We next present a refined greedy algorithm, termed GRD2, which adjusts the lg,m?s based on more accurate estimation of the channel status. GRD2 is executed at the beginning of every time slot. It estimates the number of available tiles Te(t) in the next Test successive time slots, where 1 ? Test ? TGoP is a design parameter depending on the coherence time of the channels. Such estimates are more accurate than that in 72 GRD1 since they are based on recently received ACKs and recent sensing results. Specifically, we estimate Te(t) using the belief vector vectora(t) in time slot t. Recall that an(t)?s are computed based on the channel model, feedback, sensing results, and sensing errors, as given in (3.2), and (3.4). For the next time slot, an(t + 1) can be estimated as ?an(t + 1) = ?nan(t) + ?n[1?an(t)] = (?n??n)an(t) +?n. Recursively, we can derive ?an(t+?) for the next ? time slots. ?an(t+?) = (?n??n)?an(t) +?n1?(?n??n) ? 1?(?n??n) . (3.15) At the beginning section of a GoP window, all the base layers will be firstly transmitted. We start the estimation after all the base layers have been successfully received (possibly with retransmissions). The number of available tiles in the following Test time slots can be estimated as Te(t) = summationtextNn=1summationtexttmin?=0 ?an(t + ?), where ?an(t + 0) = an(t) and tmin = min{Test?1,TGoP ? (t mod TGoP)}. Te(t) may not be an integer, but it does not affect the outcome of GRD2. We then adjust thelg,m?s based onTe(t) andNack(t), the number of ACKs received in time slot t. IfTe(t)+Nack(t?1) >Te(t?1)+Nack(t?2), there are more tiles that can be allocated and we can increase some of thelg,m?s. On the other hand, ifTe(t)+Nack(t?1) Te(t) +Nack(t?2) bracketrightBig 10: Find l?g,?m that can be reduced by 1: vectore?g,?m = argmin?g,m?{m?,???,M} braceleftBig U(vectorl)?U(vectorl?vectoreg,m) bg,m+R/Te bracerightBig 11: vectorl =vectorl?vectore?g,?m 12: IF (?g /?A) 13: Add ?g to A 14: END IF 15: END WHILE 16: END IF 17: IF [Te(t) +Nack(t?1) >Te(t?1) +Nack(t?2)] 18: WHILE bracketleftBigsummationtext G g=1 summationtextM m=1lg,m?Te(t) +Nack(t?1) and A is not empty] 19: Find l?g,?m that can be increased by 1 vectore?g,?m = argmaxg?A,m?{m?,???,M} braceleftBig U(vectorl+vectoreg,m)?U(vectorl) bg,m+R/Te bracerightBig 20: vectorl =vectorl+vectore?g,?m 21: IFparenleftbigsummationtextmb?g,ml?g,m > ?Regparenrightbig 22: vectorl =vectorl?vectore?g,?m 23: Delete ?g from A 24: END IF 25: END WHILE 26: END IF 27: Update Nack(t?1) 28: END WHILE sub-layer using MCm is successfully decoded. It can be shown that Inc(g,m,i) = Msummationdisplay k=m (ng,k?ng,k+1)?log bracketleftBigg 1 + ?gbg,mQb g +?g summationtextm?1 u=1 bg,ulg,u + (i?1)?gbg,m bracketrightBigg . Inc(g,m,i) can be interpreted as the reward if the tile is successfully received. 74 Table 3.4: Algorithm for Tile Scheduling in a Time Slot 1: Initialize mg to the lowest MC that has not been ACKed for all g 2: Initialize ig to the first packet that has not been ACKed for all g 3: Sort{cn(t)}in decreasing order. Let the sorted channel list be indexed by j. 4: While (j = 1 to N) 5: Find the group having the maximum increase in U(g): ?g = argmax?g Inc(g,mg,ig) 6: Allocate the tile on channel j to group ?g 7: Update m?g and i?g 8: End while Letting cn(t) be the probability that the tile is successfully received, then we have cn(t) = ptrn(t)an(t). Our objective of tile scheduling is to maximize the expected reward, i.e., maximize: E[Reward(vector?)] = Nsummationdisplay n=1 cn(t)?Inc(?n), (3.16) where vector? ={?n}n=1,???,N and ?n is the tile allocation for channel n, i.e., representing the three-tuple {g,m,i}. The TSA algorithm is shown in Table 3.4, which solves the above optimization problem. The complexity of TSA is O(N logN). We have the following theorem for TSA. Theorem 3.2. E[Reward] is maximized if Inc(?i) > Inc(?j) when ci(t) >cj(t) for all i and j. Proof. Suppose there exists a pair of i and j where Inc(?i) > Inc(?j) and ci(t) < cj(t). We can further increase E[Reward] by switching the tile assignment, i.e., assign channelito?j and channel j to ?i. With this new assignment, the net increase in E[Reward] is cj(t)Inc(?i) +ci(t)Inc(?j)?ci(t)Inc(?i)?cj(t)Inc(?j) = [cj(t)?ci(t)][Inc(?i)?Inc(?j)] > 0. Therefore E[Reward] is maximized when the{Inc(?i)}and{ci(t)}are in the same order. 75 3.4.3 Simulation Results We evaluate the performance of the proposed CR video multicast framework using a cus- tomized simulator implemented with a combination of C and MATLAB. Specifically, the LPs are solved using the MATLAB Optimization Toolbox and the remaining parts are written in C. For the results reported in this section, we have N = 12 channels (unless otherwise specified). The channel parameters ?n and ?n are set between (0,1). The maximum allowed collision probability ?n is set to 0.2 for all the channels unless otherwise specified. The CR base station multicasts three Common Intermediate Format (CIF, 352?288) video sequences to three multicast groups, i.e., Bus to group 1, Foreman to group 2, and Mother & Daughter to group 3. The n1,m?s are {42, 40, 36, 30, 22, 12} (i.e., 42 users can decode MC1 signal, 40 users can decode MC2 signal, and so forth); the n2,m?s are{51, 46, 40, 32, 23, 12}and then3,m?s are{49, 44, 40, 32, 24, 13}. The number of bits carried in one tile using the MC schemes are 1 kb/s, 1.5 kb/s, 2 kb/s, 3 kb/s, 5.3 kb/s, and 6 kb/s, respectively. We choose TGoP=150 and Test = 10, sensing interval W = 3, false alarm probability ?n = 0.3 and miss detection probability ?n = 0.25 for all n, unless otherwise specified. In every simulation, we compare three schemes: (i) a simple heuristic scheme that equally allocates tiles to each group (Equal Allocation); (ii) A scheme based on SF (Sequential Fixing), and (iii) a scheme based on the greedy algorithm GRD2 (Greedy Algorithm). These schemes have increasing complexity in the order of Equal Allocation, Greedy Algorithm, and Sequential Fixing. They differ on how to solve Problem OPT-Part, while the same tile scheduling algorithm and opportunistic spectrum access scheme are used in all the schemes. Each point in the figures is the average of 10 simulation runs, with 95% confidence intervals plotted. We observe that the 95% confidence intervals for Equal Allocation and Greedy Algorithm are negligible, while the 95% confidence intervals for Sequential Fixing is relatively larger. The C/MATLAB code is executed in a Dell Precision Workstation 390 with an Intel Core 2 Duo E6300 CPU working at 1.86 GHz and a 1066 MB memory. For number of channels ranging from N=3 to N=15, the execution times 76 1 2 330 35 40 45 Group Index Average PSNR(dB) Equal Allocation Sequential Fixing Greedy Algorithm Figure 3.5: Average PSNR of all multicast users. of Equal Allocation and Greedy Algorithm are about a few milliseconds, while Sequential Fixing takes about two seconds. In Fig. 3.5 we plot the average PSNR among all users in each multicast group. For all the groups, Greedy Algorithm achieves the best performance, with up to 4.2 dB improvements over Equal Allocation and up to 0.6 dB improvements over Sequential Fixing. We find Sequential Fixing achieves a lower PSNR than Equal Allocation for group 3, but higher PSNRs for groups 1 and 2. This is because Equal Allocation does not consider channel conditions and fairness. It achieves better performance for group 3 at the cost of much lower PSNRs for groups 1 and 2. We also plot Frame 53 from the original Bus sequence and the decoded video at user 1 of group 1 in Fig 3.6. We choose this user since it is one of the users with lowest PSNR values. The average PSNR of this user is 29.54 dB, while the average PSNR of all group 1 users is 34.6 dB. Compared to the original frame (right), the reconstructed frame (left) looks quite good, although some details are lost. In Fig. 3.7, we examine the impact of the maximum allowed collision probability ?n. We increase ?n from 0.1 to 0.3, and plot the average PSNR values among all the users. When ?n gets larger, there will be higher chance of collision for the video packets, which hurts the received 77 Figure 3.6: The original (the right one) and decoded Frame 53 (the left one) at user 1 in group 1. 0.1 0.15 0.2 0.25 0.335 36 37 38 39 40 Maximum Allowable Collision Probability ?n Average PSNR (dB) Greedy Algorithm Sequential Fixing Equal Allocation Figure 3.7: Average PSNR of all users versus ?n (with 95% confidence intervals). video quality. However, a higher?n also allows a higher transmission probabilityptrn(t) for the base station (see (3.6)), thus allowing the base station to grab more spectrum opportunities and achieve a higher video rate. The net effect of these two contradicting effects is improved video quality for the range of ?n values considered in this simulation. This is illustrated in the figure where all the three curves increase as ?n gets larger. We also observe that the curves for Sequential Fixing and Equal Allocation are roughly parallel to each other, while the Greedy Algorithm curve has a steeper slope. This indicates that Greedy Algorithm is more efficient in exploiting the additional bandwidth allowed by an increased ?n. 78 2 4 6 8 10 12 14 1635 36 37 38 39 40 Number of Channels Average PSNR (dB) Greedy Algorithm Sequential Fixing Equal Allocation Figure 3.8: Average PSNR of all users versus N (with 95% confidence intervals). In Fig. 3.8, we examine the impact of number of channels N. We increase N from 3 to 15 in steps of 3, and plot the average PSNR values of all multicast users. As expected, the more channels, the more spectrum opportunities for the CR networks, and the better the video quality. Again, we observe that the Greedy Algorithm curve has the steepest slope, implying it is more efficient in exploiting the increased spectrum opportunity for video transmissions. We demonstrate the impact of sensing errors in Fig. 3.9. We test five sets of{?n,?n}values as follows: {0.10,0.38},{0.30,0.25},{0.5,0.17},{0.70,0.10}and{0.9,0.04}[24], and plot the average PSNR values of all users. It is quite interesting to see that the video quality is not very sensitive to sensing errors. Even as ?n is increased nine times from 10% to 90%, there is only 0.58 dB reduction (or a 1.5% normalized reduction) in average PSNR when Greedy Algorithm is used. The same can be observed for the other two curves. We conjecture that this is due to the opportunistic spectrum access approach adopted in all the three schemes. A special strength of the proposed approach is that it explicitly considers both types of sensing errors and mitigates the impact of both sensing errors. For example, when the false alarm rate is very high, the base station will not trust the sensing results and will access the channel relatively more aggressively, thus mitigating the negative effect of the high false alarm rate. 79 0 0.2 0.4 0.6 0.8 136 36.5 37 37.5 38 38.5 39 39.5 40 Probability of False Alarm ? Average PSNR (dB) Greedy Algorithm Sequential Fixing Equal Allocation Figure 3.9: Average PSNR of all users for various{?n,?n}values (with 95% confidence intervals). Finally, we demonstrate the impact of user channel variations (i.e., due to mobility). We chose a tagged user in group 1 and assume that its channel condition changes every 20 GoPs. The highest MC scheme that the tagged user can decode is changed according to the following sequence: MC3, MC5, MC4, MC6, MC5 and MC3. All other parameters remain the same as in the previous experiments. In Fig. 3.10, we plot the average PSNRs for each GoP at this user that are obtained using the three algorithms. We observe that both Greedy Algorithm and Sequential Fixing can quickly adapt to changing channel conditions. Both algorithms achieve received video qualities commensurate with the channel quality of the tagged user. We also find the video quality achieved by Greedy Algorithm is more stable than that of Sequential Fixing, while the latter curve has some deep fades from time to time. This is due to the fact that Greedy Algorithm has a proven optimality bound, while Sequential Fixing does not provide any guarantee. The Equal Allocation curve is relative constant for the entire period since it does not adapt to channel variations. Although being simple, it does not provide good video quality in this case. For optimization-driven multimedia systems, there is a trade-off between (i) grabbing all the available resource to maximize media quality and (ii) be less adaptive to network dynamics for a smooth playout. The main objective of this paper is to demonstrate the feasibility and layout the 80 0 20 40 60 80 100 12028 30 32 34 36 38 40 42 44 GoP Index Average PSNR (dB) Greedy Algorithm Sequential Fixing Equal Allocation Figure 3.10: GoP average PSNRs of a tagged user in Group 1, when its channel condition varies over time. framework for video streaming over infrastructure-based CR networks, using an objective function of maximizing the overall user utility. We will investigate the interesting problem of trading off resource utilization and smoothness in our future work. 3.5 Video over Multi-hop CR Networks In this section, we examine the problem of video over multi-hop CR networks. We model streaming of concurrent videos as an MINLP problem, aiming to maximize the overall received video quality and fairness among the video sessions, while bound the collision rate with primary users under spectrum sensing errors. We solve the MINLP problem using a centralized sequen- tial fixing algorithm, and derive upper and lower bounds for the objective value. We then apply dual decomposition to develop a distributed algorithm and prove its optimality and convergence conditions. 81 3.5.1 Network Model Spectrum Access During the transmission phase of a time slot, a CR user determines which channel(s) to ac- cess for transmission of video data based on spectrum sensing results. Let ?km be a threshold for spectrum access: channel m is considered idle if the estimate akm is greater than the threshold, and busy otherwise. The availability of channel m in primary network k, denoted as Akm, is Akm = ? ?? ?? 0, akm??km 1, otherwise. (3.17) For each channel m, we can calculate the probability of collision with primary users as: Pr(Akm = 0|H1) = summationdisplay i??km ? ??|Ukm| i ? ??(1?? m)|U km|?i(? m)i, (3.18) where set ?km is defined as: ?km = braceleftBigg i vextendsinglevextendsingle vextendsinglevextendsingle vextendsingle bracketleftbigg 1 +?im?|Ukm|?im Pr(H1|? k m) Pr(H0|?km) bracketrightbigg?1 ??km bracerightBigg . (3.19) For non-intrusive spectrum access, the collision probability should be bounded with a prescribed threshold ?km. A higher spectrum access threshold ?km will reduce the potential interference with primary users, but increase the chance of wasting transmission opportunities. For a given collision tolerance ?km, we can solve Pr(Akm = 0|H1) = ?km for ?km. The objective is to maximize CR users? spectrum access without exceeding the maximum collision probability with primary users. Let ?i,j be the set of available channels at link{i,j}. Assuming i?Uk and j?Uk?, we have ?i,j = braceleftBig m vextendsinglevextendsingle vextendsingleAkm = 0 and Ak?m = 0 bracerightBig . (3.20) 82 Link and Path Statistics Due to the amplify-and-forward approach for video data transmission, there is no queueing delay at intermediate nodes. Assume each link has a fixed delay ?i,j (i.e., processing and propaga- tion delays). LetPAl be the set of all possible paths from zl to dl. For a given delay requirement Tth, the set of feasible pathsPl for video session l can be determined as: Pl = ? ? ?P vextendsinglevextendsingle vextendsinglevextendsingle vextendsinglevextendsingle summationdisplay {i,j}?P ?i,j?Tth, P?PAl ? ? ?. (3.21) Let pmi,j be the packet loss rate on channel m at link{i,j}. A packet is successfully delivered over link {i,j} if there is no loss on all the channels that were used for transmitting the packet. The link loss probability pi,j can be derived as: pi,j = 1? productdisplay m?M (1?pmi,j)Im, (3.22) where M is set of licensed channels and Im is an indicator: Im = 1 if channel m is used for the transmission, and Im = 0 otherwise. Assuming independent link losses, the end-to-end loss probability for pathPhl ?Pl can be estimated as: phl = 1? productdisplay {i,j}?Phl (1?pi,j). (3.23) 3.5.2 Problem Statement We also aim to achieve fairness among the concurrent video sessions. It has been shown that proportional fairness can be achieved by maximizing the sum of logarithms of video PSNRs (i.e., utilities). Therefore, our objective is to maximize the overall system utility, i.e., maximize: summationdisplay l Ul(Rl) = summationdisplay l log(Ql(Rl)). (3.24) 83 Multi-hop CR Network Video Streaming Problem For the system described in Section 2.4.1, the problem of video over multi-hop CR networks consists of path selection for each video session and channel scheduling for each CR node along the chosen paths. We define two sets of index variables. For channel scheduling, we have xl,h,ri,j,m = ?? ???? ??? ?? 1, at link{i,j}, if channel m is assigned to tunnel r in pathPhl 0, otherwise. (3.25) For path selection, we have yhl = ?? ? ?? 1, if video session l selects pathPhl ?Pl 0, otherwise, (3.26) Note that the indicators, xl,h,ri,j,m and yhl , are not independent. If yhl = 0 for path Phl , all the xl,h,ri,j,m?s on that path are 0. If link{i,j}is not on pathPhl , all its xl,h,ri,j,m?s are also 0. For link{i,j} on pathPhl , we can only choose those available channels in set ?i,j to schedule video transmission. That is, we have xl,h,ri,j,m?{0,1}if m??i,j, and xl,h,ri,j,m = 0 otherwise. In the rest of the paper, we use x and y to represent the vector forms of xl,h,ri,j,m and yhl , respectively. As discussed, the objective is to maximize the expected utility sum at the end of NG time slots, as given in (3.24). Since log(Ql(E[Rl(0)])) is a constant, (3.24) is equivalent to the sum of utility increments of all the time slots, as summationdisplay l log(Ql(E[Rl(NG)]))?log(Ql(E[Rl(0)])) = summationdisplay t summationdisplay l {log(Ql(E[Rl(t)]))?log(Ql(E[Rl(t?1)]))}. (3.27) 84 Therefore, (3.24) will be maximized if we maximize the expected utility increment during each time slot, which can be written as: summationdisplay l log(Ql(E[Rl(t)]))?log(Ql(E[Rl(t?1)])) = summationdisplay l log parenleftbigg 1 +?lE[Rl(t)]?E[Rl(t?1)]Q l(E[Rl(t?1)]) parenrightbigg = summationdisplay l summationdisplay h?Pl yhl log parenleftBigg 1+ summationdisplay r summationdisplay m ?lLpxl,h,rzl,z? l,m NGTsQt?1l (1?p r l,h) parenrightBigg = summationdisplay l summationdisplay h?Pl yhl log parenleftBigg 1+?tl summationdisplay r summationdisplay m xl,h,rzl,z? l,m (1?prl,h) parenrightBigg , where z?l is the next hop from zl on path Phl , prl,h is the packet loss rate on tunnel r of path Phl , Qt?1l = Ql(E[Rl(t?1)]), and ?tl = ?lLp/(NGTsQt?1l ). From (3.22) and (3.23), the end-to-end packet loss rate for tunnel r on pathPhl is: prl,h = 1? productdisplay {i,j}?Phl productdisplay m?M (1?pmi,j)xl,h,ri,j,m. (3.28) We assume that each tunnel can only include one channel on each link. When there are multiple channels available at each link along the path, a CR source node can set up multiple tunnels to exploit the additional bandwidth. We then have the following constraint: summationdisplay m xl,h,ri,j,m?1, ?{i,j}?Phl . (3.29) Considering availability of the channels, we further have, summationdisplay r summationdisplay m xl,h,ri,j,m?|?i,j|, ?{i,j}?Phl , (3.30) where|?i,j|is the number of available channels on link{i,j}defined in (3.20). 85 As discussed, each node is equipped with two transceivers: one for receiving and the other for transmitting video data during the transmission phase. Hence a channel cannot be used to receive and transmit data simultaneously at a relay node. We have for each channel m: summationdisplay r xl,h,ri,j,m + summationdisplay r xl,h,rj,k,m?1, ?m,l,?h?Pl,?{i,j},{j,k}?Phl . (3.31) Let nhl be the number of tunnels on pathPhl . For each source zl and each destination dl, the number of scheduled channels is equal to nhl . We have for each source node summationdisplay r summationdisplay m xl,h,rzl,z? l,m = nhlyhl , ?h?Pl,?l. (3.32) Let d?l be the last hop to destination dl on pathPhl , we have for each destination node summationdisplay r summationdisplay m xl,h,rd? l,dl,m = nhlyhl , ?h?Pl,?l. (3.33) At a relay node, the number of channels used to receive data is equal to that of channels used to transmit data, due to flow conservation and amplify-and-forward. At relay node j for session l, assume{i,j}?Phl and{j,k}?Phl . We have, summationdisplay r summationdisplay m xl,h,ri,j,m = summationdisplay r summationdisplay m xl,h,rj,k,m, ?h?Pl,?l,?{i,j},{j,k}?Phl . (3.34) We also consider hardware-related constraints on path selection. We summarize such con- straints in the following general form for ease of presentation: summationdisplay l summationdisplay h?Pl wgl,hyhl ?1,?g. (3.35) To simplify exposition, we choose at most one path inPl for video session l. Such a single path routing constraint can be expressed assummationtexthyhl ?1, which is a special case of (3.35) where w1l,h = 1 for all h, and wgl?,h = 0 for all g negationslash= 1, l? negationslash= l, and h. We can also have summationtexthyhl ? ? to allow up 86 to ? paths for each video session. In order to achieve optimality in the general case of multi-path routing, an optimal scheduling algorithm should be designed to dispatch packets to paths with different conditions (e.g., different number of tunnels and delays). There are also disjointedness constraints for the chosen paths. This is because each CR node is equipped with two transceivers and both will be used for a video session if it is included in a chosen path. Such disjointedness constraint is also a special case of (3.35) with the following definition for wgl,h for each CR node g: wgl,h = ?? ? ?? 1, if node g?pathPhl 0, otherwise, (3.36) Finally we formulate the problem of multi-hop CR network video streaming (OPT-CRV) as: max: summationdisplay l summationdisplay h?Pl yhl log parenleftBigg 1+?tl summationdisplay r summationdisplay m xl,h,rzl,z? l,m (1?prl,h) parenrightBigg (3.37) subject to: (3.25)?(3.35). Centralized Algorithm and Upper/Lower Bounds Problem OPT-CRV is in the form of MINLP (without continuous variables), which is NP-hard in general. We first describe a centralized algorithm to derive performance bounds in this section, and then present a distributed algorithm based on dual decomposition in the next section. We first obtain a relaxed non-linear programming (NLP) version of OPT-CRV. The binary variables xl,h,ri,j,m and yhl are relaxed to take values in [0,1]. The integer variables nhl are treated as nonnegative real numbers. It can be shown that the relaxed problem has a concave object function and the constraints are convex. This relaxed problem can be solved using a constrained nonlinear optimization problem solver. If all the variables are integer in the solution, then we have the exact optimal solution. Otherwise, we obtain an infeasible solution, which produces an upper bound for the problem. This is given in Lines 1?2 in Table 3.5. 87 Table 3.5: The Sequential Fixing Algorithm (SF) for Problem OPT-CRV 1 : Relax integer variables xl,h,ri,j,m, yhl , and nhl ; 2 : Solve the relaxed problem using a constrained NLP solver; 3 : if (there is yhl not fixed) 4 : Find the largest yh?l? , where [l?,h?] = argmax{yhl}, and fix it to 1; 5 : Fix other yhl ?s according to constraint (3.35); 6 : Go to Step 2; 7 : end if 8 : if (there is xl,h,ri,j,m not fixed) 9 : Find the largest xl?,h?,r?i?,j?,m?, where [i?,j?,m?,l?,h?,r?] = argmax{xl,h,ri,j,m}, and set it to 1; 10: Fix other xl,h,ri,j,m?s according to the constraints; 11: if (there is other variable that is not fixed) 12: Go to Step 2; 13: else 14: Fix nhl ?s based on x and y; 15: Exit with feasible solution{x,y,n}; 16: end if 17: end if We also develop a sequential fixing algorithm (SF) for solving OPT-CRV. The pseudo-code is given in Table 3.5. SF iteratively solves the relaxed problem, fixing one or more integer variables after each iteration [8, 47]. In Table 3.5, Lines 3?7 fix the path selection variables yhl , and Lines 8?16 fix the channel scheduling variables xl,h,ri,j,m and tunnel variables nhl . The tunnel variables nhl can be computed using (3.32) after xl,h,ri,j,m and yhl are solved. When the algorithm terminates, it produces a feasible solution that yields a lower bound for the objective value. 3.5.3 Dual Decomposition SF is a centralized algorithm requiring global information. It may not be suitable for multi-hop wireless networks, although the upper and lower bounds provide useful insights on the performance limits. In this section, we develop a distributed algorithm for Problem OPT-CRV and analyze its optimality and convergence performance. 88 Decompose Problem OPT-CRV Since the domains of xl,h,ri,j,m defined in (3.29)?(3.34) for different paths do not intersect with each other, we can decompose Problem OPT-CRV into two subproblems. The first subproblem deals with channel scheduling for maximizing the expected utility on a chosen pathPhl . We have the channel scheduling problem (OPT-CS) as: Hhl = maxx summationdisplay r summationdisplay m xl,h,rzl,z? l,m (1?prl,h) (3.38) subject to: (3.29)?(3.34), xl,h,rzl,z? l,m ?{0,1}, for all l,h,r,m. In the second part, optimal paths are selected to maximize the overall objective function. Letting Fhl = logparenleftbig1 +?Tl Hhl parenrightbig, we have the following path selection problem (OPT-PS): maximize: f(y) = summationdisplay l summationdisplay h Fhl yhl (3.39) subject to: summationdisplay l summationdisplay h?Pl wgl,hyhl ?1, for all g yhl ?{0,1}, for all l,h. Solve the Channel Scheduling Subproblem We have the following result for assigning available channels at a relay node. Theorem 3.3. Consider three consecutive nodes along a path, denoted as nodes i, j, and k. Idle channels 1 and 2 are available at link{i,j}and idle channels 3 and 4 are available at link{j,k}. Assume the packet loss rates of the four channels satisfy p1i,j > p2i,j and p3j,k > p4j,k. To set up two tunnels, assigning channels{1, 3}to one tunnel and channels{2, 4}to the other tunnel achieves the maximum expectation of successful transmission on path section{i,j,k}. Proof. Let the success probabilities on the channels be ?p1i,j = 1?p1i,j, ?p2i,j = 1?p2i,j, ?p3j,k = 1?p3j,k, and ?p4j,k = 1?p4j,k. We have ?p1i,j < ?p2i,j and ?p3j,k < ?p4j,k. Comparing the success probabilities of 89 the channel assignment given in Theorem 3.3 and that of the alternative assignment, we have ?p1i,j?p3j,k + ?p2i,j?p4j,k??p1i,j?p4j,k??p2i,j?p3j,k = (?p1i,j??p2i,j)(?p3j,k??p4j,k) > 0. The result follows. According to Theorem 3.3, a greedy approach, which always chooses the channel with the lowest loss rate at each link when setting up tunnels along a path, produces the optimal overall success probability. More specifically, when there is only one tunnel to be set up along a path, the tunnel should consist of the most reliable channels available at each link along the path. When there are multiple tunnels to set up along a path, tunnel 1 should consist of the most reliable channels that are available at each link; tunnel 2 should consist of the second most reliable links available at each link; and so forth. Define the set of loss rates of the available channels on link{i,j}as ?i,j ={pmi,j|m??i,j}. The greedy algorithm is given in Table 3.6, with which each video source node solves Problem OPT-CS for each feasible path. Lines 2?3 in Table 3.6 checks if there is more channels to assign and the algorithm terminates if no channel is left. In Lines 4?10, links with only one available channel are assigned to tunnel r and the neighboring links with the same available channels are removed due to constraint (3.31). In Lines 11?17, links with more than two channels are grouped to be assigned later. In Lines 18?20, the available channel with the lowest packet loss rate is assigned to tunnel r at each unallocated link, according to Theorem 3.3. To avoid co-channel interference, the same channel on neighboring links is removed as in Lines 21?33. Solve the Path Selection Subproblem To solve Problem OPT-PS, we first relax binary variables yhl to allow them take real values in [0,1] and obtain the following relaxed path selection problem (OPT-rPS): maximize: f(y) = summationdisplay l summationdisplay h Fhl yhl (3.40) subject to: summationdisplay l summationdisplay h?Pl wgl,hyhl ?1, for all g 0?yhl ?1, for all h,l. 90 Table 3.6: The Greedy Algorithm for Channel Scheduling 1 : Initialization: tunnel r = 1, link{i,j}?s from zl to dl; 2 : if (|?i,j|== 0) 3 : Exit; 4 : else if (|?i,j|== 1) 5 : Assign the single channel in ?i,j, m?, to tunnel r; 6 Check neighboring link{k,i}; 7 : if (pm?k,i??k,i) 8 : Remove pm?k,i from ?k,i, i?k, j?i and go to Step 2; 9 : else 10: Go to Step 13; 11: end if 12: else 13: Put ?i,j in set ?hl ; 14: if (node j is not destination dl) 15: i?j, j?v; 16: Go to Step 2; 17: end if 18: end if 19: while (?hl is not empty) 20: Find the maximum value pm?i?,j? in set ?hl {i?,j?,m?}= argmin{pmi,j}; 21: Assign channel m? to tunnel r; 22: Remove set ?i?,j? from set ?hl ; 23: Check neighboring link{k,i}and{j,v}; 24: if (pm?k,i??k,i and ?k,i??hl ) 25: Remove pm?k,i from ?k,i; 26: if (?k,i is empty) 27: Exit; 28: end if 29: end if 30: if (pm?j,v??j,v and ?j,v??hl ) 31: Remove pm?j,v from ?j,v; 32: if (?j,v is empty) 33: Exit; 34: end if 35: end if 36: end while 37: Compute the next tunnel: r?r+ 1 and go to Step 2; 91 We then introduce positive Lagrange Multipliers eg for the path selection constraints in Problem OPT-rPS and obtain the corresponding Lagrangian function: L(y,e) = summationdisplay l summationdisplay h Fhl yhl + summationdisplay g eg(1? summationdisplay l summationdisplay h wgl,hyhl ) (3.41) = summationdisplay l summationdisplay h (Fhl yhl ? summationdisplay g wgl,hyhl eg) + summationdisplay g eg = summationdisplay l summationdisplay h Lhl (yhl ,e) + summationdisplay g eg. Problem (3.41) can be decoupled since the domains of yhl ?s do not overlap. Relaxing the coupling constraints, it can be decomposed into two levels. At the lower level, we have the following subproblems, one for each pathPhl , max 0?yhl ?1 Lhl (yhl,e) = Fhl yhl ? summationdisplay g wgl,hyhleg. (3.42) At the higher level, by updating the dual variables eg, we can solve the relaxed dual problem: min e?0 q(e) = summationdisplay l summationdisplay h Lhl parenleftBigparenleftbig yhlparenrightbig?,e parenrightBig + summationdisplay g eg, (3.43) where parenleftbigyhlparenrightbig? is the optimal solution to (3.42). Since the solution to (3.42) is unique, the relaxed dual problem (3.43) can be solved using the following subgradient method that iteratively updates the Lagrange Multipliers [69]: eg(? + 1) = bracketleftBigg eg(?)??(?)(1? summationdisplay l summationdisplay h wgl,hyhl ) bracketrightBigg+ , (3.44) where ? is the iteration index, ?(?) is a sufficiently small positive step size and [x]+ denotes max{x,0}. The pseudo code for the distributed algorithm is given in Table 3.7. 92 Table 3.7: Distribution Algorithm for Path Selection 1: Initialization: set ? = 0, eg(0) > 0 and step size s?[0,1]; 2: Each source locally solves the lower level problem in (3.42); if (Fhl ?summationtextgdgl,heg(?)) > 0) yhl = yhl +s, yhl = min{yhl ,1}; else yhl = yhl ?s, yhl = max{yhl ,0}; 3: Broadcast solution yhl (e(?)); 4: Each source updates e according to (3.44) and broadcasts e(? + 1) through the common control channel; 5: ???+1 and go to Step 2 until termination criterion is satisfied; Optimality and Convergence Analysis The distributed algorithm in Table 3.7 iteratively updates the dual variables until they converge to stable values. In this section, we first prove that the solution obtained by the distributed algorithm is also optimal for the original path selection problem OPT-PS. We then derive the convergence condition for the distributed algorithm. Fact 1 ( [69]). Consider a linear problem involving both equality and inequality constraints maximize: a?x (3.45) subject to: h?1x = b1, ???, h?mx = bm g?1x?c1, ???, g?rx?cr, where a, hi, and gj are column vectors in Rn, bi?s and cj?s are scalars, and a? is the transpose of a. For any feasible point x, the set of active inequality constraints is denoted by A(x) = braceleftbigj|g? jx = cj bracerightbig. If x? is a maximizer of inequality constrained problem (3.45), x? is also a maximizer of the following equality constrained problem: maximize: a?x (3.46) subject to: h?1x = b1, ???, h?mx = bm g?jx = cj,?j?A(x). 93 Lemma 3.1. The optimal solution for the relaxed primal problem OPT-rPS in (3.40) is also feasible and optimal for the original Problem OPT-PS in (3.39). Proof. According to Fact 1, the linearized problem of OPT-PS, i.e., OPT-rPS, can be rewritten as an equality constrained problem in the following form: maximize: F?y (3.47) subject to: w?jy = 1, j?A(y?) (3.48) 0?yhl ?1, for all h,l, where F, wj?s, and y are column vectors with elements Fhl , wgl,h, and yhl , respectively. We apply Gauss-Jordan elimination to the constraints in (3.48) to solve for y. Since there is not sufficient number of equations, some yhl ?s are free variables (denoted as yfi ) and the rest are dependent variables (denoted as ydj). Assuming there are r free variables, the dependent variables can be written as linear combinations of the free variables after Gauss-Jordan elimination, as ydj = rsummationdisplay i=1 ?wijyfi +?bj, j?A(y?i). (3.49) Due to Gauss-Jordan elimination and binary vectors wj?s, ?wij and ?bj in (3.49) are all integers. Therefore, if all the free variables yfi attain binary values, then all the dependent variables ydj computed using (3.49) will also be integers. Since 0?ydj ?1, being integers means that they are either 0 or 1, i.e., binaries. That is, such a solution will be feasible. Next we substitute (3.49) into problem (3.47) to eliminate all the dependent variables. Then we obtain a unconstrained problem with only r free variables, as maximize: rsummationdisplay i=1 ?Fiyfi +?b0 (3.50) 94 Since the free variables yfi ?s take value in{0, 1}, this problem can be easily solved as follows. If the coefficient ?Fi > 0, we set yfi = 1; otherwise, if ?Fi < 0, we set yfi = 0. Thus (3.50) achieves its maximum objective value. Once all the free variables are determined with their optimal binary values, we computes the dependent variables using (3.49), which are also binary as discussed above. Thus we obtain a feasible solution, which is optimal. Lemma 3.2. If the relaxed primal Problem OPT-rPS in (3.40) has an optimal solution, then the relaxed dual problem (3.43) also has an optimal solution and the corresponding optimal values of the two problems are identical. Proof. By definition, the problems in (3.41) and (3.43) are primal/dual problems. The primal problem always has an optimal solution because it is bounded. Since Problem OPT-rPS is an LP problem, the relaxed dual problem is also bounded and feasible. Therefore the relaxed dual problem also has an optimal solution. We have the strong duality if the primal problem is convex, which is the case here since Problem OPT-rPS is an LP problem. We have Theorem 3.4 on the optimality of the path selection solution, which follows naturally from Lemmas 3.1 and 3.2. Theorem 3.4. The optimal solution to the relaxed dual problem (3.42) and (3.43) is also feasible and optimal to the original path selection Problem OPT-PS given in (3.39). As discussed, the relaxed dual problem (3.43) can be solved using the subgradient method that iteratively updates the Lagrange Multipliers. We have the following theorem on the convergence of the distributed algorithm given in Table 3.7. Theorem 3.5. Let e? be the optimal solution. The distributed algorithm in Table 3.7 converges if the step sizes ?(?) in (3.44) satisfy the following condition: 0 ?m 1, if am(vector?m)??m. (4.2) 109 CR nodes only attempt to access channel m where Dm is 0. Since function am(vector?m) in (4.1) has Nm binary variables, there can be 2Nm different combinations corresponding to 2Nm values for am(vector?m). We sort the 2Nm combinations according to their am(vector?m) values in the non-increasing order. Let a(j)m be the jth largest function value and vector?(j)m the argument that achieves the jth largest function value a(j)m , where vector?(j)m = [?m1 (j),?m2 (j),???,?mN m(j)]. In the design of CR networks, we consider two objectives: (i) how to avoid harmful inter- ference to primary users, and (ii) how to fully exploit spectrum opportunities for the CR nodes. For primary user protection, we limit the collision probability with primary user with a thresh- old. Let ?m be the tolerance threshold, i.e., the maximum allowable interference probability with primary users on channel m. The probability of collision with primary users on channel m is given as Pr{Dm = 0|Hm1 }; the probability of detecting an available transmission opportunity is Pr{Dm = 0|Hm0 }. Our objective is to maximize the probability of detecting available chan- nels, while keeping the collision probability below ?m. Therefore, the optimal spectrum sensing problem can be formulated as follows. max? m Pr{Dm = 0|Hm0 } (4.3) subect to: Pr{Dm = 0|Hm1 }??m. (4.4) From their definitions, both Pr{Dm = 0|Hm1 }and Pr{Dm = 0|Hm0 }are decreasing functions of ?m. As Pr{Dm = 0|Hm1 )}approaches its maximum allowed value ?m, Pr{Dm = 0|Hm0 }also approaches its maximum. Therefore, solving the optimization problem (4.3)?(4.4) is equivalent to solving Pr{Dm = 0|Hm1 }= ?m. 110 Table 4.1: Algorithm for Computing the Optimal Sensing Threshold 1: Compute a(j)m and the corresponding vector?(j)m , for all j; 2: Initialize pc = Pr{am(vector?m) = a(1)m|Hm1 }and ?m = a(1)m ; 3: Set j = 1; 4: WHILE (pc??m) 5: j = j + 1; 6: ?m = a(j)m ; 7: pc = pc + Pr{am(vector?m) = a(j)m|Hm1 }; 8: END WHILE If ?m = a(j)m , we have Pr{Dm = 0|Hm1 }(a(j)m ) = Pr{am(vector?m) >a(j)m|Hm1 } = j?1summationdisplay l=1 Pr{am(vector?m) = a(l)m|Hm1 }= j?1summationdisplay l=1 (?mi )1??mi (l)(1??mi )?mi (l). (4.5) Obviously, Pr{Dm = 0|Hm1 }(a(j)m ) is an increasing function of j. The optimal sensing threshold ??m can be set to a(j)m , such that Pr{Dm = 0|Hm1 }(a(j)m )??m and Pr{Dm = 0|Hm1 }(a(j+1)m ) >?m. The algorithm for computing the optimal sensing threshold ??m is presented in Table 4.1. Once the optimal sensing threshold ??m is determined, Pr{Dm = 0|Hm1 }can be computed as given in (4.5) and Pr{Dm = 0|Hm0 }can be computed as: Pr{Dm = 0|Hm0 }= Pr{am(vector?m) >??m|Hm0 } = j?1summationdisplay l=1 Pr{am(vector?m) = a(l)m|Hm0 }= j?1summationdisplay l=1 (?mi )?mi (l)(1??mi )1??mi (l). (4.6) 111 Odd time slot Even time slot DF: Busy S1 R1 S2 R2 Busy R1 D1 Busy R2 D2 Idle Channel 1 Channel 2 Channel 3 Channel 4 Busy S1 R1 R1 D1 Busy S2 R2 Busy R2 D2 Idle AF: Channel 1 Channel 2 Channel 3 Channel 4 Figure 4.2: Illustration of the protocol operation of AF and DF, where Si ? Ri represents the transmission from source to relay and Ri?Di represents the transmission from relay to destina- tion, for the ith cooperative relay link. Cooperative Relay Strategies During the transmission phase, CR transmitters and relays attempt to send data through the channels that are believed to be idle. We assume fixed length for all the data frames. Let Gk1 and Gk2 denote the path gains from the transmitter to relay and from the relay to receiver, respectively, and let ?2r,k and ?2d,k denote the noise powers at the relay and receiver, respectively, for the kth co- operative relay link. We examine the two cooperation relay strategies DF and AF in the following. For comparison purpose, we also consider direct link transmission below. Decode-and-Forward (DF) With DF, the CR transmitter and relay transmit separately on con- secutive odd and event time slots: the CR transmitter sends data to the corresponding relay in an odd time slot; the relay node then decodes the data and forwards it to the receiver in the following even time slot, as shown in Fig. 4.2. Without loss of generality, we assume a data frame can be successfully decoded if the received signal-to-noise ratio (SNR) is no less than a decoding threshold ?. We assume gains on different links are independent to each other. The receiver can successfully decode the frame if it is not lost or corrupted on both links. The decoding rate of DF at the kth receiver, denoted by PkDF, can be 112 computed as, PkDF = PrbraceleftbigparenleftbigPsGk1/?2r,k??parenrightbig and parenleftbigPrGk2/?2d,k??parenrightbigbracerightbig = ?FGk1 parenleftbig?2r,k?/Psparenrightbig ?FGk2 parenleftbig?2d,k?/Prparenrightbig, (4.7) where Ps and Pr are the transmit powers at the transmitter and relay, respectively, ?FGk1(x) and ?FGk 2(x) are the complementary cumulative distribution functions (CCDF) of path gains G k 1 and Gk2, respectively. Amplify-and-Forward (AF) With AF, the CR transmitter and relay transmit simultaneously in the same time slot on different channels. A pipeline is formed connecting the CR transmitter to the relay and then to the receiver; the relay amplifies the received signal and immediately forwards it to the receiver in the same time slot, as shown in Fig. 4.2. Recall that the CR relay has two transceivers. The relay receives data from the transmitter using one transceiver operating on one or more idle channels; it forwards the data simultaneously to the receiver using the other transceiver operating on one or more different idle channels. With this cooperative relay strategy, a data frame can be successfully decoded if the SNR at the receiver is no less than the decoding threshold ?. Then the decoding rate of AF at the kth receiver, denoted as PkAF, can be computed as, PkAF = Pr braceleftBigg Pr Gk1Ps +?2r,k PsGk1Gk2 ?2d,k ?? bracerightBigg = integraldisplay +? 0 ?FGk 2 parenleftbigg(P sx+?2r,k)?2d,k? PsPrx parenrightbigg dFGk1(x). (4.8) Direct Link Transmission For comparison purpose, we also consider the case of direct link transmission (DL). That is, the CR transmitter transmits to the receiver via the direct link; the CR relay is not used in this case. Let the path gain be Gk0 with CCDF ?FGk0(x), and recall that the noise power is ?2d,k at the receiver, for the kth direct link transmission. 113 Following similar analysis, the decoding rate of DL at the kth receiver, denoted as PkDL, can be computed as PkDL = PrbraceleftbigPsGk0/?2d,k??bracerightbig= ?FGk0 parenleftbig?2d,k?/Psparenrightbig. (4.9) Opportunistic Channel Access We assume greedy transmitters that always have data to send. The CR nodes use p-Persistent CSMA for channel access. At the beginning of the transmission phase of an odd time slot, CR transmitters send Request-to-Send (RTS) with probability p over the control channel. Since there are N CR transmitters, the transmission probability p is set to 1/N to maximize the throughput (i.e., to maximize P1 in (4.10) given below). The following three cases may occur: ? Case 1: none of the CR transmitters sends RTS for channel access. The idle licensed chan- nels will be wasted. ? Case 2: only one CR transmitter sends RTS, and it successfully receives Clear-to-Send (CTS) from the receiver over the control channel. It then accesses some of or all the licensed channels that are believed to be idle for data transmission in the transmission phase. ? Case 3: more than one CR transmitters send RTS and collision occurs on the control channel. No CR node can access the licensed channels, and the idle licensed channels will be wasted. Let P0, P1 and P2 denote the probability corresponding to the three cases enumerated above, respectively. We then have P0 = (1?p)N = (1?1/N)N (4.10) P1 = Np(1?p)N?1 = (1?1/N)N?1 (4.11) P2 = 1?P0?P1. (4.12) 114 The CR cooperative relay link that wins the channels in the odd time slot will continue to use the channels in the following even time slot. A new round of channel competition will start in the next odd time slot following these two time slots. Since a licensed channel is accessed with probability P1 in the odd time slot, we modify the tolerance threshold ?m as ??m = ?m/P1, such that the maximum allowable collision requirement can still be satisfied. In the even time slot, the channels will continue to be used by the winning cooperative relay link, i.e., to be accessed with probability 1. Therefore, the tolerance threshold is still ?m for the even time slots. Capacity Analysis Once the CR transmitter wins the competition, as indicated by a received CTS, it begins to send data over the licensed channels that are inferred to be idle (i.e., Dm = 0) in the transmission phase. We assume the channel bonding and aggregation technique is used, such that multiple channels can be used collectively by a CR node for data transmission [20, 44]. With DF, the winning CR transmitter uses all the available channels to transmit to the relay in the odd time slot. In the following even time slot, the CR transmitter stops transmission, while the relay uses the available channels in the even time slot to forward data to the receiver. If the number of available channels in the even time slot is equal to or greater than that in the odd time slot, the relay uses the same number of channels to forward all the received data. Otherwise, the relay uses all the available channels to forward part of the received data; the excess data will be dropped due to limited channel resource in the even time slot. The dropped data will be retransmitted in some future odd time slot by the transmitter. With AF, no matter it is an odd or even time slot, the CR transmitter always uses half of the available licensed channels to transmit to the relay. The relay uses one of its transceivers to receive from the chosen half of the available channels. Simultaneously, it uses the other transceiver to forward the received data to the receiver using the remaining half of the available channels. 115 Let Dodm and Devm be the decision variables of channel m in the odd and even time slot, re- spectively (see (4.2)). Let Sodm and Sevm be the status of channel m in the odd and even time slot, respectively. We have, Pr{Dodm = i,Sodm = j,Devm = k,Sevm = l} (4.13) = Pr{Devm = k|Sevm = l}Pr{Dodm = i|Sodm = j}? Pr{Sevm = l|Sodm = j}Pr{Sodm = j}, for i,j,k,l?{0,1}. where Pr{Sodm = j}are the probabilities that channel m is busy or idle, Pr{Sevm = l|Sodm = j}are the channel m transition probabilities. Pr{Devm = k|Sevm = l}and Pr{Dodm = i|Sodm = j}can be computed as in (4.5) and (4.6). Let NDF, NAF and NDL be the number of frames successfully delivered to the receiver in the two consecutive time slots using DF, AF and DL, respectively. Define ?Sodm = 1?Sodm , ?Sevm = 1?Sevm, ?Dodm = 1?Dodm and ?Devm = 1?Devm. We have NDF = parenleftBigsummationtext M m=1 ?S od m ?D od m parenrightBig ? parenleftBigsummationtext M m=1 ?S ev m ?D ev m parenrightBig (4.14) NAF = floorleftbigg1 2 summationtextM m=1 ?S od m ?D od m floorrightbigg + floorleftbigg1 2 summationtextM m=1 ?S ev m ?D ev m floorrightbigg (4.15) NDL = parenleftBigsummationtext M m=1 ?S od m ?D od m parenrightBig + parenleftBigsummationtext M m=1 ?S ev m ?D ev m parenrightBig , (4.16) where x?y represents the minimum of x and y, and?x?means the maximum integer that is not larger than x. As discussed, the probability that a frame can be successfully delivered is PkDF, PkAF, or PkDL for the three schemes, respectively. Recall that spectrum resources are allocated distributedly for every pair of two consecutive time slots. We derive the capacity for the three cooperative relay 116 strategies as CDF = E[NDF]?summationtextNk=1(PkDFP1L)/(2NTs) (4.17) CAF = E[NAF]?summationtextNk=1(PkAFP1L)/(2NTs) (4.18) CDL = E[NDL]?summationtextNk=1(PkDLP1L)/(2NTs), (4.19) where L is the packet length and Ts is the duration of a time slot. The expectations are computed using the results derived in (4.13)?(4.16). 4.3.3 Performance Evaluation We evaluate the performance of the cooperative relay strategies with analysis and simulations. The analytical capacities of the schemes are obtained with the analysis presented in Section 4.3.2. The actual throughput is obtained using MATLAB simulations. The simulation parameters and their values are listed in Table 4.2, unless specified otherwise. We consider M = 5 licensed chan- nels and a CR network with seven cooperative relay links. The channels have identical parameters for the Markov chain models. Each point in the simulation curves is the average of 10 simulation runs with different random seeds. We plot 95% confidence intervals for the simulation results, which are negligible in all the cases. We first examine the impact of the number of licensed channels. To illustrate the effect of spectrum sensing, we let the decoding ratePkAF be equal toPkDF. In Fig. 4.3, we plot the throughput of AF, DF, and DL under increased number of licensed channels. The analytical curves are upper bounds for the simulation curves in all the cases, and the gap between the two is reasonably small. Furthermore, as the number of license channels is increased, the throughput of both AF and DF are increased. The slope of the AF curves is larger than that of the DF curves. There is a cross point between five and six, as predicted by both simulation and analysis curves. This indicates that AF outperforms DF when the number of channels is large. This is because AF is more flexible than DF in exploiting the idle channels in the two consecutive time slots. The DL analysis and 117 Table 4.2: Simulation Parameters and Values Symbol Value Definition M 5 number of licensed channels ? 0.7 channel transition probability from idle to idle ? 0.2 channel transition probability from busy to idle ? 0.6 channel utilization ? 0.08 maximum allowable collision probability N 7 number of CR cooperative relay links Ps 10 dBm transmit power of the CR transmitters Pr 10 dBm transmit power of CR relays L 1 kb packet length Ts 1 ms duration of a time slot 3 4 5 6 7 8 90 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Number of channels Throughput (Mbps) AF throughput (simulation) DF throughput (simulation) DL throughput (simulation) AF capacity (analysis) DF capacity (analysis) DL capacity (analysis) Figure 4.3: Throughput performance versus number of licensed channels. simulation curves also increases with the number of channels, but with the lowest slope and the lowest throughput values. In Fig. 4.4, we demonstrate the impact of channel utilization on the throughput of the schemes. The channel utilization ? is increased from 0.3 to 0.9, when primary users get more active. As ? is increased, the transmission opportunities for CR nodes are reduced and all the throughputs 118 0.3 0.4 0.5 0.6 0.7 0.8 0.90 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 Channel Utilization (?) Throughput (Mbps) AF throughput (simulation) DF throughput (simulation) DL throughput (simulation) AF capacity (analysis) DF capacity (analysis) DL capacity (analysis) Figure 4.4: Throughput performance versus primary user channel utilization. are degraded. We find the throughputs of AF and DF are close to each other when the channel utilization is high. AF outperforms DF in the low channel utilization region, but is inferior to DF in the high channel utilization region. There is a cross point between the AF and DF curves between ? = 0.5 and ? = 0.6. When the channel utilization is low, there is a big gap between the cooperative relay curves and and the DL curves. In Fig. 4.5, we examine the channel fading factor. We consider Rayleigh block fading chan- nels, where the received power is exponentially distributed with a distance-dependent mean. We fix the transmitter power at 10 dBm, and increase the relay power from one dBm to 18 dBm. As the relay power is increased, the throughput is also increased since the SNR at the receiver is im- proved. We can see the increasing speed of AF is larger than that of DF, indicating that AF has superior performance than DF when the relay transmit power is large. The capacity analysis also demonstrate the same trend. The throughput of DL does not depend on the relay node. Its through- put is better than that of AF and DF when the relay transmit power is low, since both AF and DF are limited by the relay-to-receiver link in this low power region. However, the throughputs of AF and DF quickly exceed that of DL and grow fast as the relay-to-receiver link is improved with the increased relay transmit power. The considerable gaps between the cooperative relay link curves 119 0 5 10 15 200 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Relay?s Transmit Power (dBm) Throughput (Mbps) AF throughput (simulation) DF throughput (simulation) DL throughput (simulation) AF capacity (analysis) DF capacity (analysis) DL capacity (analysis) Figure 4.5: Throughput performance versus transmit power of relay nodes. and the DL curves in Figs. 4.3, 4.4 and 4.5 exemplify the diversity gain achieved by cooperative relays in CR networks. 4.4 Cooperative CR Networks with Interference Alignment In this section, we investigate cooperative relay in CR networks using video as a reference application. We consider a base station (BS) and multiple relay nodes (RN) that collaboratively stream multiple videos to CR users within the network. It has been shown that the performance of a cooperative relay link is mainly limited by two factors: ? the half-duplex operation, since the BS?RN and the RN?user transmissions cannot be sched- uled simultaneously on the same channel [79]; and ? the bottleneck channel, which is usually the BS?user and/or the RN?user channel, usually with poor quality due to obstacles, attenuation, multipath propagation and mobility [54]. To support high quality video service in such a challenging environment, we assume a well planned relay network where the RNs are connected to the BS with high-speed wireline links, and explore interference alignment to overcome the bottleneck channel problem. Therefore the 120 video packets will be available at both the BS and the RNs before their scheduled transmission time, thus allowing advanced cooperative transmission techniques (e.g. interference alignment) to be adopted for streaming videos. In particular, we incorporate interference alignment to allow transmitters collaboratively send encoded signals to all CR users, such that undesired signals will be canceled and the desired signal can be decoded at each CR user. We present a stochastic programming formulation, as well as a reformulation that greatly re- duces computational complexity. In the cases of a single licensed channel and multiple licensed channels with channel bonding, we develop an optimal distributed algorithm with proven con- vergence and convergence speed. In the case of multiple channels without channel bonding, we develop a greedy algorithm with a proven performance bound. 4.4.1 Network Model and Assumptions The cooperative CR network is illustrated in Fig. 4.6. There is a CR BS (indexed 1) and (K?1) CR RNs (indexed from 2 to K) deployed in the area to serve N active CR users. Let U ={1,2,???,N}denote the set of active CR users. We assume that the BS and all the RNs are equipped with multiple transceivers: one is tuned to the common control channel and the others are used to sense multiple licensed channels at the beginning of each time slot, and to transmit encoded signals to CR users. We consider the case where each CR user has one software defined radio (SDR) based transceiver, which can be tuned to operate on any of the (M + 1) channels. If the channel bonding/aggregation techniques are used [44,70], a transmitter can collectively use all the available channels and a CR user can receive from all the available channels simultaneously. Otherwise, only one licensed channel will be used by a transmitter and a CR user can only receive from a single chosen channel at a time. Consider the three channels in a traditional cooperative relay link. Usually the BS and RNs are mounted on high towers, and the BS?RN channel has good quality due to line-of-sight (LOS) communications and absence of mobility. On the other hand, a CR user is typically on the ground level. The BS?user and RN?user channels usually have much poorer quality due to obstacles, 121 BS (1) M licensed channels 3 2 1 0 RN 3 RN 2 RN K CR UserRN 4 ... common control channel Figure 4.6: Illustration of the cooperative CR network. attenuation, multipath propagation and mobility. To support high quality video service, we assume a well planned relay network, where the RNs are connected to the BS via broadband wireline connections (e.g., as in femtocell networks [13]). Alternatively, free space optical links can also be used to provide multi-gigabit rates between the BS and the RNs [91]. As a result, the video packets will always be available for transmission (with suitable channel coding and retransmission) at the RNs at their scheduled transmission time. To cope with the much poorer BS?user and RN?user channels, the BS and RNs adopt interference alignment to cooperatively transmit video packets to CR users, while exploiting the spectrum opportunities in the licensed channels. Spectrum Access The BS and the RNs sense the licensed channels and exchange their sensing results over the common control channel during the sensing phase. Recall that in Section 2.5.1 and 2.5.1. Given L sensing results obtained for channel m, the corresponding sensing result vector is vector?mL = [?m1 ,?m2 ,???,?mL]. Let PAm(vector?mL) := PAm(?m1 ,?m2 ,???,?mL) be the conditional probability that 122 channel m is available, which can be computed iteratively as shown in our prior work [13]: PAm(?m1 ) = bracketleftbigg 1 + ?m1?? m ?(? m 1 ) 1??m1 (1??m 1 ) ?m1 (?m1 )?m1 (1??m1 )1??m1 bracketrightbigg?1 PAm(vector?ml ) := PAm(?m1 ,?m2 ,???,?ml ) = braceleftbigg 1 + bracketleftbigg 1 PAm(?m1 ,?m2 ,???,?ml?1)?1 bracketrightbigg ?(? m l ) 1??ml (1??m l ) ?ml (?ml )?ml (1??ml )1??ml bracerightbigg?1 ,l?2. For each channel m, define an index variable Dm(t) for the BS or RNs to access the channel in time slot t. That is, Dm(t) = ?? ? ?? 0, access channel m in time slot t 1, otherwise, m = 1,2,???,M. (4.20) With sensing result PAm(vector?mL), each channel m will be opportunistically accessed. Let the probability be PDm(vector?mL) that channel m will be accessed in time slot t (i.e., when Dm(t) = 0). The optimal channel access probability can be computed as: PDm(vector?mL) = min braceleftBig ?m/ bracketleftBig 1?PAm(vector?mL) bracketrightBig ,1 bracerightBig . (4.21) LetA(t) be the set of available channels in time slot t. It follows thatA(t) :={m|Dm(t) = 0}. Interference Alignment We next briefly describe the main idea of interference alignment considered in this paper. Interested readers are referred to [76, 90] for insightful examples, a classification of various inter- ference alignment scenarios, and practical considerations. Consider two transmitters (denoted as s1 and s2 ) and two receivers (denoted as d1 and d2). Let X1 and X2 be the signals corresponding to the packets to be sent to d1 and d2, respectively. With interference alignment, the transmitters s1 and s2 send compound signals a1,1X1 + a1,2X2 and a2,1X1 +a2,2X2, respectively, to the two receivers d1 and d2 simultaneously. If channel noise 123 is ignored, the received signals Y1 and Y2 can be written as: ? ?? Y1 Y2 ? ?? = ? ?? G1,1 G1,2 G2,1 G2,2 ? ?? T? ?? a1,1 a1,2 a2,1 a2,2 ? ?? ? ?? X1 X2 ? ??:= GT?A? vectorX, (4.22) where Gi,j is the channel gain from transmitter si to receiver dj. From (4.22), it can be seen that both receivers can perfectly decode their signals if the trans- formation matrix A is chosen to bebraceleftbigGTbracerightbig?1, i.e., the inverse of the channel gain matrix. With this technique, the transmitters are able to send packets simultaneously and the interference between the two concurrent transmissions can be effectively canceled at both receivers [76]. 4.4.2 Problem Formulation We formulate the problem of interference alignment for scalable video streaming over coop- erative CR networks in this section. As discussed in Section 4.3.1, the video packets are available at both the BS and all the RNs before their scheduled transmission time; the BS and RNs adopt interference alignment to overcome the poor BS?CR user and RN?CR user channels. Let Xj denote the signal to be transmitted to user j, which has unit power. As illustrated in Section 4.4.1, transmitter k sends a compound signal summationtextj?U ak,jXj to all active CR users, where ak,j?s are the weights to be determined. Ignoring channel noise, we can compute the received signal Yn at a user n as: Yn = Ksummationdisplay k=1 Gk,n Nsummationdisplay j=1 ak,jXj = Ksummationdisplay k=1 Nsummationdisplay j=1 ak,jGk,nXj = Nsummationdisplay j=1 Xj Ksummationdisplay k=1 ak,jGk,n, n = 1,2,???,N, (4.23) where Gk,n is the channel gain from the BS (i.e., k = 1) or an RN k to user n. For user n, only signal Xn should be decoded and the coefficients of all other signals should be forced to zero. The 124 zero-forcing constraints can be written as: Ksummationdisplay k=1 ak,jGk,n = 0, for all jnegationslash= n. (4.24) Usually the total transmit power of the BS and every RN is limited by a peak power Pmax. Since Xj has unit power, for all j, the power of each transmitted signal is the square sum of all the coefficients a2k,j. The peak power constraint can be written as Nsummationdisplay j=1 |ak,j|2?Pmax, k = 1,???,K. (4.25) Recall that each CR user has one SDR transceiver that can be tuned to receive from any of the (M + 1) channels, when channel bonding is not adopted. Let bmj be a binary variable indicating that user j selects licensed channel m. It is defined as bmj = ?? ? ?? 1, if user n receives from channel m 0, otherwise, j = 1,???,N, m = 1,???,M. (4.26) Then, we have the following transceiver constraint: summationdisplay m?A(t) bmj ?1, j = 1,???,N. (4.27) After introducing the channel selection variables bmj ?s, the overall channel gain becomes Gk,j = summationdisplay m?A(t) bmj Hmk,j, (4.28) where Hmk,j is the channel gain from the BS (i.e., k = 1) or an RN k to user j on channel m. Let wtj be the PSNR of user j?s reconstructed video at the beginning of time slot t and Wtj the PSNR of user j?s reconstructed video at the end of time slot t. In time slot t, wtj is already known, 125 while Wtj is a random variable depending on the resource allocation and primary user activity during the time slot. That is, wt+1j is a realization of Wtj. As discussed in Section 3.3.5, the quality of reconstructed MGS video can be modeled with a linear equation [53]: W(R) = ?+??R, (4.29) where W(R) is the average peak signal-to-noise ratio (PSNR) of the reconstructed MGS video, R is the average data rate, and ? and ? are constants depending on the specific video sequence and codec. We formulate a multistage stochastic programming problem to maximize the sum of expected logarithm of the PSNR?s at the end of the GOP, i.e., summationtextNj=1Ebracketleftbiglog(WTj )bracketrightbig, for proportional fair- ness among the video sessions [71]. It can be shown that the multistage stochastic programming problem can be decomposed into T serial sub-problems, one for each time slot t, as [9]: maximize: Nsummationdisplay j=1 Ebracketleftbiglog(Wtj)|wtjbracketrightbig (4.30) subject to: Wtj = wtj + ?tj (4.31) bmj ?{0,1}, ak,j?0, for all m,j,k (4.32) Constraints (4.24), (4.25) and (4.27), where ?tj is a random variable that depends on spectrum sensing, power allocation, and channel selection in time slot t. This is a mixed integer nonlinear programming problem (MINLP), with binary variables bmj ?s and continuous real variables ak,j?s. In particular, ?tj can have two possible values: (i) zero, if the packet is not successfully received due to collision with primary users; (ii) the PSNR increase achieved in time slot t if the packet is successfully received, denoted as ?tj. The PSNR increase can be computed as: ?tj = ?jBT log2 ? ?1 + 1N 0 parenleftBigg Ksummationdisplay k=1 ak,jGk,j parenrightBigg2? ?, (4.33) 126 where N0 is the noise power and B is the channel bandwidth. User j can successfully receive a video packet from channel m if it tunes to channel m (i.e., bmj = 1) and the BS and RNs transmit on channel m (i.e., with probability PDm(vector?mL)). The proba- bility that user j successfully receives a video packet, denoted as Ptj, is Ptj = summationdisplay m?A(t) bmj PDm(vector?mL). (4.34) Therefore, we can expand the expectation in (4.30) to obtain a reformulated problem: maximize: Nsummationdisplay j=1 EbracketleftbigPtj log(wtj +?tj) + (1?Ptj)log(wtj)bracketrightbig (4.35) subject to: constraints (4.24), (4.25), (4.27), and (4.32). 4.4.3 Solution Algorithms In this section, we develop effective solution algorithms to the stochastic programming prob- lem (4.30). In Section 4.4.3, we first consider the case of a single licensed channel, and derive a distributed, optimal algorithm with guaranteed convergence and bounded convergence speed. We then address the case of multiple licensed channels. If channel bonding/aggregation techniques are used [44, 70], the distributed algorithm in Section 4.4.3 can still be applied to achieve optimal solutions. We finally consider the case of multiple licensed channels without channel bonding, and develop a greedy algorithm with a performance lower bound in Section 4.4.3. Case of a Single Channel Property Consider the case when there is only one licensed channel, i.e., when M = 1. The K transmitters, including the BS and (K?1) RNs, send video packets to active users using the licensed channel when it is sensed idle. Definition 4.1. A set of vectors is linearly independent if none of them can be written as a linear combination of the other vectors in the set [77]. 127 For user j, the weight and channel gain vectors are: vectoraj = [a1,j,a2,j,???,aK,j]T and vectorGj = [G1,j,G2,j,???,GK,j]T, where T denotes matrix transpose. Due to spatial diversity, we assume that the vectorGj vectors are linearly independent [74]. Lemma 4.1. To successfully decode each signal Xj, j = 1,2,???,N, the number of active users N should be smaller than or equal to the number of transmitters K. Proof. From (4.24), it can be seen that vectoraj is orthogonal to the (N?1) vectors vectorGn?s, for nnegationslash= j. Sincevectoraj is a K by 1 vector, there are at most (K?1) vectors that are orthogonal tovectoraj. Since the vectorGj vectors are linearly independent, it follows that (N?1)?(K?1) and therefore N?K. According to Lemma 4.1, the following additional constraints should be enforced for the channel selection variables. Nsummationdisplay j=1 bmj ?K, for all m?A(t). (4.36) That is, the number of active users receiving from any channel m cannot be more than the number of transmitters on that channel, which is K in the single channel case and less than or equal to K in the multiple channels case. We first assume that N is not greater than K, and will remove this assumption in the following subsection. Reformulation and Complexity Reduction With a single channel, all active users receive from channel 1. Therefore b1j = 1, and bmj = 0, for m > 1, j = 1,2,???,N. The formulated problem is now reduced to a nonlinear programming problem with constraints (4.24), (4.25), and (4.32). If the number of active users is N = 1, the solution is straightforward: all the transmitters send the same signal X1 to the single user using their maximum transmit power Pmax. In general, the reduced problem can be solved with the dual decomposition technique [69] (i.e., a primal dual algorithm). This problem has K?N primal variables (i.e., the ak,j?s), and we need to define N(N?1) dual variables (or, Lagrangian Multipliers) for constraints (4.24) and K dual variables for constraints (4.25). These numbers could be large for even moderate-sized 128 systems. Before presenting the solution algorithm, we first derive a reformulation of the original problem (4.35) that can greatly reduce the number of primal and dual variables, such that the computational complexity can be reduced. Lemma 4.2. Each vectorvectoraj = [a1,j,a2,j,???,aK,j]T can be represented by the linear combination of r nonzero, linearly independent vectors, where r = K?N + 1. Proof. From (4.24), each vector vectoraj is orthogonal to vectorGi where j negationslash= i. Define a reduced matrix G?j obtained by deleting vectorGj from G, i.e., G?j = [vectorG1,???,vectorGj?1,vectorGj+1,???,vectorGN]. Then vectoraj is a solution to the homogeneous linear system GT?jvectorx = 0. Since we assume that the vectorGi?s are all linearly independent, the columns of G?j are also linearly independent [77]. Thus the rank of G?j is (N?1). The solution belongs to the null space of G?j. The dimension of the null space is r = K?(N?1) according to the Rank-nullity Theorem [77]. Therefore, eachvectoraj can be presented by the linear combination of r linearly independent vectors. Let ej ={vectorej,1,vectorej,2,???,vectorej,r}be a basis for the null space of G?j. There are many methods to obtain the basis, such as Gaussian Elimination. However, we show that it is not necessary to solve the homogeneous linear system GT?jvectorx = 0 to get the basis for every different j value. Therefore the computational complexity can be further reduced. Our algorithm for computing a basis is shown in Table 4.3. In Steps 1?6, we first solve the homogeneous linear system GTvectorx = 0 to get a basis [vectorv1,vectorv2,???,vectorvK?N]. Note that if K is equal to N, the basis is the empty set ?. We then set the K?N basis vectors to be the first K?N vectors in all the basses ej, j = 1,2,???,N. In Step 8, we orthogonalize each G?j and obtain (N?1) orthogonal vectors vector?j,i, i = 1,2,???,N?1. Finally in Step 9, we let the rth vector vectorej,r be orthogonal to all the vector?j,i?s by subtracting all the projections on each vector?j,i from vectorGj (recall that r = K?N + 1). The operation is: vectorej,r =vectorej,N?K+1 = vectorGj? N?1summationdisplay i=1 vectorGTjvector?j,i vector?Tj,ivector?j,ivector?j,i. (4.37) 129 Table 4.3: Basis Computation Algorithm 1: IF (K >N) 2: Solve homogeneous linear system GTvectorx = 0 and get basis [vectorv1,???,vectorvK?N]; 3: FOR i = 1 to K?N 4: vectorej,i =vectorvi, for all j; 5: END FOR 6: END IF 7: FOR j = 1 to N 8: Orthogonalize G?j and get (N?1) orthogonal vectors vectorwj,i?s; 9: Calculatevectorej,r as in (4.37); 10: END FOR Lemma 4.3. The solution space constructed by the basis [vectorv1,vectorv2,???,vectorvK?N] is a sub-space of the solution space of GT?jvectorx = 0 for all j. Proof. It is easy to see that each vector vectorvi is a solution of GT?jvectorx = 0 by substituting vectorx withvectorvi, for i = 1,2,???,K?N. Lemma 4.4. The vectors [vectorv1,vectorv2,???,vectorvK?N,vectorej,r] computed in Table 4.3 is a basis of the null space of G?j. Proof. Obviously, the vectorvi?s are linearly independent. From (4.37), it is easy to verify that vectorej,r is orthogonal to all the vector?j,i?s. Therefore,vectorej,r is also a solution to system GT?jvectorx = 0. Since vectorGj and vector?j,i are orthogonal to all thevectorvi?s, andvectorej,r is a linear combination of vectorGj and vector?j,i,vectorej,r is also orthogonal and linearly independent to all thevectorvi?s. The conclusion follows. Define coefficients vectorcj = [cj,1,cj,2,???,cj,r]T. Then we can representvectoraj as a linear combina- tion of the basis vectors, i.e.,vectoraj =summationtextrl=1cj,lvectorej,l = ejvectorcj. Eq. (4.33) can be rewritten as ?tj = ?jBT log2 parenleftbigg 1 + 1N 0 parenleftBig vectorcTjeTj vectorGj parenrightBig2parenrightbigg = ?jBT log2 parenleftbigg 1 + 1N 0 parenleftBig cj,rvectoreTj,rvectorGj parenrightBig2parenrightbigg . (4.38) The second equality is because the first K?N column vectors in ej are orthogonal to Gj. The random variable Wtj in the objective function now only depends on cj,r. The peak power constraint 130 Table 4.4: Comparison of Computational Complexity Original Problem Reformulated Problem Primal Variables KN (K?N + 1)N Dual Variables N(N?1) +K K can be revised as: Nsummationdisplay j=1 [ej(k)vectorcj]2?Pmax, k = 1,???,K, (4.39) where ej(k) is the kth row of matrix ej. With such a reformulation, the number of primal and dual variables can be greatly reduced. In Table 4.4, we show the numbers of variables in the original problem and in the reformulated problem. The number of primary variables is reduced from KN to (K?N + 1)N, and the number of dual variables is reduced from N(N?1) +K to K. Such reductions result in greatly reduced computational complexity. Distributed Algorithm To solve the reformulated problem, we define non-negative dual vari- ables vector? = [?1,???,?K]T for the inequality constraints. The Lagrangian function is L(c,vector?) = Nsummationdisplay j=1 Ebracketleftbiglog(Wtj(cj,r))|wtjbracketrightbig+ Ksummationdisplay k=1 ?k(Pmax? Nsummationdisplay j=1 [ej(k)vectorcj]2) = Nsummationdisplay j=1 Lj(vectorcj,vector?) +Pmax Ksummationdisplay k=1 ?k, (4.40) where c is a matrix consisting of all column vectorvectorcj?s and Lj(vectorcj,vector?) = Ebracketleftbiglog(Wtj(cj,r))|wtjbracketrightbig? Ksummationdisplay k=1 ?k[ej(k)vectorcj]2. The corresponding problem can be decomposed into N sub-problems and solved iteratively [69]. In Step ? ?1, for given vector vector?(?), each CR user solves the following sub-problem using 131 local information vectorcj(?) = argmaxLj(vectorcj,vector?(?)). (4.41) Obviously, the objective function in (4.41) is concave. Therefore, there is a unique optimal solu- tion. The CR users then exchange their solutions over the common control channel. To solve the primal problem, we adopt the gradient method [69]. vectorcj(? + 1) =vectorcj(?) +??Lj(vectorcj(?),vector?(?)), (4.42) where?Lj(vectorcj(?),vector?(?)) is the gradient of the primal problem and ? is a small positive step size. The master dual problem for a given c(?) is: min ?i?0,i=1,???,K q(vector?) = Nsummationdisplay j=1 Lj(vectorcj(?),vector?) +Pmax Ksummationdisplay k=1 ?k. (4.43) Since the Lagrangian function is differentiable, the subgradient iteration method can be adopted. vector?(? + 1) = [vector?(?)??(?)vectorg(?)]+, (4.44) where ?(?) = q(vector?(?))?q(vector??)||vectorg(?)||2 is a positive step size, vector?? is the optimal solution, vectorg(?) =?q(vector?(?)) is the gradient of the dual problem, and [?]+ denotes the projection onto the nonnegative axis. Since the optimal solution vector?? is unknown a priori, we choose the mean of the objective values of the primal and dual problems as an estimate for vector?? in the algorithm. The updated ?k(? +1) will again be used to solve the sub-problems (4.41). Since the problem is convex, we have strong duality; the duality gap between the primal and dual problems will be zero. The distributed algorithm is shown in Table 4.5, where 0???1 is a threshold for convergence. 132 Table 4.5: Algorithm for the Case of a Single Channel 1: IF (N = 1) 2: Set ak,j to Pmax for all k; 3: ELSE 4: Set ? = 0; vector?(0) to positive values; c(0) to random values; 5: Compute bases ej?s as in Table 4.3; 6: DO 7: ? = ? + 1 ; 8: Computevectorcj(?) as in (4.42); 9: Broadcastvectorcj(?) on the common control channel; 10: Update vector?(?) as in (4.44); 11: WHILE (||vector?(?)?vector?(??1)||>?); 12: Compute ak,j?s; 13: END IF Performance Analysis We analyze the performance of the distributed algorithm in this section. In particular, we prove that it converges to the optimal solution at a speed faster than radicalbig1/? as ? goes to infinity. Theorem 4.1. The series q(vector?(?)) converges to q(vector??) as ? goes to infinity and the square error sum summationtext? ?=1(q(vector?(?))?q(vector? ?))2 is bounded. Proof. For the optimality gap, we have: ||vector?(? + 1)?vector??||2 =||[vector?(?)??(?)vectorg(?)]+?vector??||2 ? ||vector?(?)??(?)vectorg(?)?vector??||2 = ||vector?(?)?vector??||2?2?(?)(vector?(?)?vector??)Tvectorg(?) + (?(?))2||vectorg(?)||2 = ||vector?(?)?vector??||2?2?(?)(q(vector?(?))?q(vector??)) + (?(?))2||vectorg(?)||2. Since the step size is ?(?) = q(vector?(?))?q(vector??)||vectorg(?)||2 , it follows that ||vector?(? + 1)?vector??||2 ? ||vector?(?)?vector??||2?(q(vector?(?))?q(vector? ?))2 ||vectorg(?)||2 ? ||vector?(?)?vector??||2?(q(vector?(?))?q(vector? ?))2 ?g2 , (4.45) 133 where ?g2 is an upper bound of||vectorg(?)||2. Since the second term on the right-hand-side of (4.45) is non-negative, it follows that lim???q(vector?(?)) = q(vector??). Summing Inequality (4.45) over ?, we have ?summationdisplay ?=1 (q(vector?(?))?q(vector??))2??g2||vector?(1)?vector??||2. That is, the square error sum is upper bounded. Theorem 4.2. The sequence{q(vector?(?))}converges faster than{1/??}as ? goes to infinity. Proof. Assume lim?????(q(vector?(?))?q(vector??)) > 0. Then there is a sufficiently large ?? and a positive number ? such that??(q(vector?(?))?q(vector??))??, for all ????. Taking the square sum from ?? to?, we have: ?summationdisplay ?=?? (q(vector?(?))?q(vector??))2??2 ?summationdisplay ?=?? 1 ? =?. (4.46) Eq. (4.46) contradicts with Theorem 4.1, which states that summationtext??=1(q(vector?(?))?q(vector??))2 is bounded. Therefore, we have lim??? q(vector?(?))?q(vector? ?) 1/?? = 0, (4.47) indicating that the convergence speed of q(vector?(?)) is faster than that of 1/??. Case of Multiple Channels with Channel Bonding When there are multiple licensed channels, we first consider the case where the channel bond- ing/aggregation techniques are used by the transmitters and CR users [44,70]. With channel bond- ing, a transmitter can utilize all the available channels inA(t) collectively to transmit the mixed signal. We assume that at the end of the sensing phase in each time slot, CR users tune their SDR transceiver to the common control channel to receive the set of available channelsA(t) from the 134 BS. Then each CR user can receive from all the channels in A(t) and decode its desired signal from the compound signal it receives. This case is similar to the case of a single licensed channel. Now all the active CR users receive from the set of available channelsA(t). We thus have bmj = 1, for m?A(t), and bmj = 0, for m /?A(t), j = 1,2,???,N. When all the bmj ?s are determined this way, problem (4.30) is reduced to a nonlinear programming problem with constraints (4.24) and (4.25). The distributed algorithm described in Section 4.4.3 can be applied to solve this reduced problem to get optimal solutions. Case of Multiple Channels without Channel Bonding We finally consider the case of multiple channels without channel bonding, where each CR user has a narrow band SDR transceiver and can only receive from one of the channels. We first present a greedy algorithm that leverages the optimal algorithm in Table 4.5 for near-optimal solutions, and then derive a lower bound for its performance. Greedy Algorithm When M > 1, the optimal solution to problem (4.30) depends also on the binary variables bmj ?s, which determines whether user j receives from channel m. Recall that there are two constraints for the bmj ?s: (i) each user can use at most one channel (see (4.27)); (ii) the number of users on the same channel cannot exceed the number of transmitters K (see (4.36)). Let vectorb be the channel allocation vector with elements bmj ?s, and ?(vectorb) the corresponding objective value for a given user channel allocationvectorb. We take a two-step approach to solve problem (4.30). First, we apply the greedy algorithm in Table 4.6 to choose one available channel inA(t) for each CR user (i.e., to determinevectorb). Sec- ond, we apply the algorithm in Table 4.5 to obtain a near-optimal solution for the given channel allocationvectorb. In Table 4.6, vector?mj is a unit vector with 1 for the [(j?1)?M +m]-th element and 0 for all other elements, andvectorb =vectorb+vector?m?j? indicates choosing channel m? for user j?. In each iteration, the 135 Table 4.6: Channel Selection Algorithm for the Case of Multiple Channels without Channel Bond- ing 1: Initializevectorb to a zero vector, user setU ={1,???,N} and user-channel setC=U?A(t); 2: WHILE (Cnegationslash=?) 3: Find the user-channel pair{j?,m?}, such that {j?,m?}= argmax{(j,m)?C}{?(vectorb+vector?mj )??(vectorb)}; 4: Setvectorb =vectorb+vector?m?j? and remove j? fromU; 5: IF (summationtextNj=1bm?j = K) 6: Remove m? fromA(t); 7: END IF 8: Update user-channel setC=U?A(t); 9: END WHILE user-channel pair (j?,m?) that can achieve the largest increase in the objective value is chosen, as in Step 3. The complexity of the greedy algorithm in the worst case is O(K2M2). Performance Bound We next analyze the greedy algorithm and derive a lower bound for its performance. Let ?l be the sequence from the first to the lth user-channel pair selected by the greedy algorithm. The increase in objective value is denoted as: Fl := F(?l,?l?1) = ?(?l)??(?l?1). (4.48) Sum up (4.48) from 1 to L. We have summationtextLl=1Fl = ?(?L) since ?(?0) = 0. Let ? be the global optimal solution for user-channel allocation. Define ?l as a subset of ?. For given ?l, ?l is the subset of user-channel pairs that cannot be allocated due to the conflict with the l-th user channel allocation ?l (but not conflict with the user-channel allocations in ?l?1). Lemma 4.5. Assume the greedy algorithm stops in L steps, we have ?(?)??(?L) + Lsummationdisplay l=1 summationdisplay ???l F(???l?1,?l?1). Proof. The proof is similar to the proof of Lemma 7 in [13] and is omitted for brevity. 136 Theorem 4.3. The greedy algorithm for channel selection in Table 4.6 can achieve an objective value that is at least 1|A(t)| of the global optimum in each time slot. Proof. According to Lemma 4.5, it follows that: ?(?)??(?L)+ Lsummationdisplay l=1 |?l|Fl??(?L)+(|A(t)|?1) Lsummationdisplay l=1 Fl =|A(t)|?(?L). (4.49) The second inequality is due to the fact that each user can choose at most one channel and there are at most (|A(t)|?1) pairs in ?l according to the definition. The equality in (4.49) is because summationtextL l=1Fl = ?(?L). Then we have: 1 |A(t)|?(?)??(?L)??(?). (4.50) The greedy heuristic solution is lower bounded by 1/|A(t)|of the global optimum. Define competitive ratio ? = ?(?L)/?(?) = 1/|A(t)|. Assume all the licensed channels have identical utilization ?. Since|A(t)|is a random variable, we take the expectation of ? and obtain: E[?] = ?M + Msummationdisplay n=1 parenleftbigg1 n parenrightbigg ?M?n(1??)n. (4.51) In Fig. 4.7, we evaluate the impact of channel utilization ? and the number of licensed chan- nels M on the competitive ratio. We increase ? from 0.05 to 0.95 in steps of 0.05 and increase M from 6 to 12 in steps of 2. The lower bound (4.50) becomes tighter when ? is larger or when M is smaller. For example, when ? = 0.6 and M = 6, the greedy algorithm solution is guaranteed to be no less than 52.7% of the global optimal. when ? is increased to 0.95, the greedy algorithm solution is guaranteed to be no less than 98.3% of the global optimal. 137 0 0.2 0.4 0.6 0.8 10 0.2 0.4 0.6 0.8 1 Channel Utilization (?) Ratio ( ?) M=6 M=8 M=10 M=12 Figure 4.7: Competitive ratio E[?] defined in (4.51) versus channel utilization ?. 4.4.4 Performance Evaluation We evaluate the performance of the proposed algorithms with a MATLAB implementation and the JVSM 9.13 Video Codec. We present simulation results for the following two scenarios: (i) a single licensed channel and (ii) multiple licensed channels without channel bonding, since we observe similar performance for the case of multiple licensed channels with channel bonding. For comparison purpose, we also developed two simpler heuristic schemes that do not incorporate interference alignment. ? Heuristic 1: each CR user selects the best channel inA(t) based on channel condition. The time slot is equally divided among the active users receiving from the same channel, to send their signals separately in each time slice. ? Heuristic 2: in each time slot, the active user with the best channel is selected for each available channel. The entire time slot is used to transmit this user?s signal. 138 1 2 330 32 34 36 38 40 User Index Y?PSNR (dB) Proposed scheme Heuristic 1 Heuristic 2 Figure 4.8: Received video quality for each CR user with a single channel. Case of a Single Licensed Channel In the first scenario, there are K = 4 transmitters, i.e., one BS and three RNs. The channel utilization ? is set to 0.6 and the maximum allowable collision probability ? is set to 0.2. There are three active CR users, each receives an MGS video stream from the BS: Bus to CR user 1, Mobile to CR user 2, and Harbor to CR user 3. The video sequences are in the Common Intermediate Format (CIF, 252?288). The GOP size of the videos is 16 and the delivery deadline T is 10. The false alarm probability is ?ml = 0.3 and the miss detection probability is ?ml = 0.3 for all spectrum sensors. The channel bandwidthB is 1 MHz. The peak power limit is 10 W for all the transmitters, unless otherwise specified. We first plot the average Y-PSNRs of the three reconstructed MGS videos in Fig. 4.8, i.e., only the Y (Luminance) component of the original and reconstructed videos are used. Among three schemes, the proposed algorithm achieves the highest PSNR value, while the two heuristic algorithms have similar performance. Note that the proposed algorithm is optimal in the single channel case. It achieves significant improvements ranging from 3.1 dB to 5.25 dB over the two heuristic algorithms. Such PSNR gains are considerable, since in video coding and communica- tions, a half dB gain is distinguishable and worth pursing. 139 0 20 40 60 80 100 1200 2 4 6 8 10 Interation Index (?) Optimality Gap q(?)?q? 10/sqrt(?) Figure 4.9: Convergence rate of the distributed algorithm with a single channel. We next examine the convergence rate of the distributed algorithm. According to Theo- rem 4.2, the distributed algorithm converges at a speed faster than 1/?? asymptotically. We compare the optimality gap of the proposed algorithm, i.e., |q(?)?q?|, with series 10/?? in Fig. 4.9. Both curves converge to 0 as ? goes to infinity. It can be seen that the convergence speed, i.e., the slope of the curve, of the proposed scheme is larger than that of 10/?? after about 10 iterations. The convergence of the optimality gap is much faster than 10/??, which exhibits a heavy tail. In the case of multiple channels with channel bonding, the performance of the proposed algo- rithm is similar to that in the single channel case. We omit the results for lack of space. Case of Multiple Channels without Channel Bonding We next investigate the second scenario with six licensed channels and four transmitters. There are 12 CR users, each streaming one of the three different videos Bus, Mobile, and Harbor. The rest of the parameters are the same as those in the single channel case, unless otherwise specified. Eq. (4.49) can also be interpreted as an upper bound on the global optimal, i.e., ?(?)? |A(t)|?(?L), which is also plotted in the figures. Each point in the following figures is the average 140 0.3 0.4 0.5 0.6 0.7 0.8 0.930 35 40 45 50 55 60 65 70 75 Channel Utilization (?) Average Y?PSNR (dB) Proposed scheme Heuristic 1 Heuristic 2 Upper bound Figure 4.10: Reconstructed video quality vs. channel utilization ? in the multi-channel without channel bonding case. of 10 simulation runs with different random seeds. The 95% confidence intervals are plotted as error bars, which are generally negligible. The impact of channel utilization ? on received video quality is presented in Fig. 4.10. We increase ? from 0.3 to 0.9 in steps of 0.15, and plot the Y-PSNRs of reconstructed videos averaged over all the 12 CR users. Intuitively, a smaller ? allows more transmission opportunities for CR users, thus allowing the CR users to achieve higher video rates and better video quality. This is shown in the figure, in which all four curves decrease as ? is increased. We also observe that the gap between the upper bound and proposed schemes becomes smaller as ? gets larger, from 32.65 dB when ? = 0.3 to 0.63 dB when ? = 0.9. This trend is also demonstrated in Fig. 4.7. The proposed scheme outperforms the two heuristic schemes with considerable gains, ranging from 0.8 dB to 3.65 dB. Finally, we investigate the impact of the number of transmitters K on the video quality. In this simulation we increase K from 2 to 6 with step size 1. The average Y-PSNRs of all the 12 CR users are plotted in Fig. 4.11. As expected, the more transmitters, the more effective the interference alignment technique, and thus the better the video quality. The proposed algorithm 141 2 3 4 5 630 35 40 45 50 55 60 Number of Transmitters (K) Average Y?PSNR (dB) Proposed scheme Heuristic 1 Heuristic 2 Upper bound Figure 4.11: Reconstructed video quality vs. number of transmitters K in the multi-channel with- out channel bonding case. achieves gains ranging from 1.78 dB (when K = 2) to 4.55 dB (when K = 6) over the two heuristic schemes. 4.5 Conclusions In this chapter, we first studied the problem of cooperative relay in CR networks. We modeled the two cooperative relay strategies, i.e., DF and AF, which are integrated withp-Persistent CSMA. We analyzed their throughput performance and compared them under various parameter ranges. Cross-point with the AF and DF curves are found when some parameter is varied, indicating that each of them performs better in a certain parameter range; there is no case of dominance for the two strategies. Considerable gains were observed over conventional DL transmissions, as achieved by exploiting cooperative diversity with the cooperative relays in CR networks. Then, we investigated the problem of interference alignment for MGS video streaming in a cooperative relay enhanced CR network. We presented a stochastic programming formation, and derived a reformulation that leads to considerable reduction in computational complexity. A 142 distributed optimal algorithm was developed for the case of a single channel and the case of multi- channel with channel bonding, with proven convergence and convergence speed. We also presented a greedy algorithm for the multi-channel without channel bonding case, with a proven performance bound. The proposed algorithms are evaluated with simulations and are shown to outperform two heuristic schemes without interference alignment with considerable gains. 143 Chapter 5 CR Femtocell Networks 5.1 Introduction Due to the use of open space as transmission medium, capacity of wireless networks are usually limited by interference. When a mobile user moves away from the base station, a consider- ably larger transmit power is needed to overcome attenuation, while causing interference to other users and deteriorating network capacity. To this end, femtocells provide an effective solution that brings network infrastructure closer to mobile users. A femtocell is a small (e.g., residential) cellular network, with a femto base station (FBS) connected to the owner?s broadband wireline network [5,92,93]. The FBS serves approved users when they are within the coverage. Among the many benefits, femtocells are shown effective on improving network coverage and capacity [5]. Due to reduced distance, transmit power can be greatly reduced, leading to prolonged battery life, improved signal-to-interference-plus-noise ratio (SINR), and better spatial reuse of spectrum. Femtocells have received significant interest from the wireless industry. Although highly promising, many important problems should be addressed to fully harvest their potential, such as interference mitigation, resource allocation, synchronization, and QoS provisioning [5, 92]. It is also critical for the success of this technology to support important applications such as real-time video streaming in femtocell networks. In this chapter, we first investigate the problem of data multicast in femtocell networks. It is not atypical that many users may request for the same content, as often observed in wireline net- works. By allowing multiple users to share the same downlink multicast transmission, significant spectrum and power savings can be achieved. In particular, we adopt superposition coding (SC) and successive interference cancellation (SIC), two well-known PHY techniques, for data multicast in femtocell networks [94]. With SC, 144 a compound signal is transmitted, consisting of multiple signals (or, layers) from different senders or from the same sender. With SIC, a strong signal can be first decoded, by treating all other signals as noise. Then the decoder will reconstruct the signal from the decoded bits, and subtract the reconstructed signal from the compound signal. The next signal will be decoded from the residual, by treating the remaining signals as noise. And so forth. A special strength of the SC with SIC approach is that it enables simultaneous unicast transmissions (e.g., many-to-one or one-to- many). It has been shown that SC with SIC is more efficient than PHY techniques with orthogonal channels [94, 95]. We adopt SC and SIC for the unique femtocell network environment, and investigate how to enable efficient data multicast from the femtocells to multiple users. We formulate a Mixed Integer Nonlinear Programming (MINLP) problem, which is NP-hard in general. The objective is to minimize the total BS power consumption. Then we reformulate the MINLP problem into a simpler form, and derive upper and lower performance bounds. We also derive a simple heuristic scheme that assigns users to the BS?s with a greedy approach. Finally, we consider three typical connection scenarios in the femtocell network, and develop optimal and near-optimal algorithms for the three scenarios. The proposed algorithms have low computational complexity, and are shown to outperform the heuristic scheme with considerable gains. Then, we investigate the problem of video streaming in femtocell cognitive radio (CR) net- works. We consider a femtocell network consisting of a macro base station (MBS) and multiple FBS?s. The femtocell network is co-located with a primary network with multiple licensed chan- nels. This is a challenging problem due to the stringent QoS requirements of real-time videos and, on the other hand, the new dimensions of network dynamics (i.e., channel availability) and uncertainties (i.e., spectrum sensing and errors) found in CR networks. We adopt Scalable Video Coding (SVC) in our system. SVC encodes a video into multiple substreams, subsets of which can be decoded to provide different quality levels for the recon- structed video [53]. Such scalability is very useful for video streaming systems, especially in 145 CR networks, to accommodate heterogeneous channel availabilities and dynamic network condi- tions. We consider H.264/SVC medium grain scalable (MGS) videos, since MGS can achieve better rate-distortion performance over Fine-Granularity-Scalability (FGS), although it only has Network Abstraction Layer (NAL) unit-based granularity [53]. The unique femtocell network architecture and the scalable video allow us to develop a frame- work that captures the key design issues and trade-offs, and to formulate a stochastic programming problem. It has been shown that the deployment of femtocells has a significant impact on the network performance [5]. In this paper, we examine three deployment scenarios. In the case of a single FBS, we apply dual decomposition to develop a distributed algorithm that can compute the optimal solution. In the case of multiple non-interfering FBS?s, we show that the same distributed algorithm can be used to compute optimal solutions. In the case of multiple interfering FBS?s, we develop a greedy algorithm that can compute near-optimal solutions, and prove a closed-form lower bound for its performance based on an interference graph model. The proposed algorithms are evaluated with simulations, and are shown to outperform three alternative schemes with con- siderable gains. The remainder of this chapter is organized as follows. The related work is discussed in Sec- tion 5.2. We investigate the problem of data multicast over fenmtocell networks in Section 5.3. The problem of streaming multiple MGS videos in a femtocell CR network is discussed in Section 5.4. Section 5.5 concludes this paper. 5.2 Background and Related Work Femtocells have attracted considerable interest from both industry and academia. Technical and business challenges, requirements and some preliminary solutions to femtocell networks are discussed in [5]. Since FBS?s are distributedly located and are able to spatially reuse the same channel, considerable research efforts were made on interference analysis and mitigation [35, 96]. 146 A distributed utility based SINR adaptation scheme was presented in [96] to alleviate cross-tire in- terference at the macrocell from co-channel femtocells. Lee, Oh and Lee [35] proposed a fractional frequency reuse scheme to mitigate inter-femtocell interference. Deploying femtocells by underlaying the macrocell has been proved to significantly improve indoor coverage and system capacity. However, interference mitigation in a two-tier heteroge- neous network is a challenging problem. In [97], the interference from macrocell and femtocells was mitigated by a spatial channel separation scheme with codeword-to-channel mapping. In [98], the rate distribution in the macrocell was improved by subband partitioning and modest gains were achieved by interference cancellation. In [99], the interference was controlled by denying the ac- cess of femtocell base stations to protect the transmission of nearby macro base station. A novel algorithmic framework was presented in [100] for dynamic interference management to deliver QoS, fairness and high system efficiency in LTE-A femtocell networks. Requiring no modification of existing macrocells, CR was shown to achieve considerable performance improvement when applied to interference mitigation [101]. In [102], the orthogonal time-frequency blocks and trans- mission opportunities were allocated based on a safe/victim classification. SIC has high potential of sending or receiving multiple signals concurrently, which improves the transmission efficiency. In [95], the authors developed MAC and routing protocols that ex- ploit SC and SIC to enable simultaneous unicast transmissions. Sen, et al. investigated the pos- sible throughput gains with SIC from a MAC layer perspective [103]. Power control for SIC was comprehensively investigated and widely applied to code division multiple access (CDMA) systems [104?108]. Applying game theory, Jean and Jabbari proposed an uplink power control under SIC in direct sequence-CDMA networks [104]. In [105], the authors introduced an iterative two-stage SIC detection scheme for a multicode MIMO system and showed the proposed scheme significantly outperformed the equal power allocation scheme. A scheme on joint power control and receiver optimization of CDMA transceivers was presented in [106]. In [107,108], the impact of imperfect channel estimation and imperfect interference cancellation on the capacity of CDMA systems was examined. 147 5.3 Multicast in Femtocell Networks with Superposition Coding and Successive Interfer- ence Cancellation In this section, we formulate a Mixed Integer Nonlinear Programming (MINLP) problem of data multicast in femotcell networks, which is NP-hard in general. Then we reformulate the MINLP problem into a simpler form, and derive upper and lower performance bounds. We also derive a simple heuristic scheme that assigns users to the BS?s with a greedy approach. Finally, we consider three typical connection scenarios in the femtocell network, and develop optimal and near-optimal algorithms for the three scenarios. The proposed algorithms have low computational complexity, and are shown to outperform the heuristic scheme with considerable gains. 5.3.1 System Model and Problem Statement System Model Consider a femtocell network with an MBS (indexed 0) and M FBS?s (indexed from 1 to M) deployed in the area. The M FBS?s are connected to the MBS and the Internet via broadband wireline connections. Furthermore, we assume a spectrum band that is divided into two parts, one is allocated to the MBS with bandwidth B0 and the other is allocated to the M FBS?s. The bandwidth allocated to FBS m is denoted by Bm. When there is no overlap between the coverages of two FBS?s, they can spatially reuse the same spectrum. Otherwise, the MBS allocates disjoint spectrum to the FBS?s with overlapping coverages. We assumed the spectrum allocation is known a priori. There areK mobile users in the femtocell network. Each user is equipped with one transceiver that can be tuned to one of the two available channels, i.e., connecting to a nearby FBS or to the MBS. The network is time slotted. We assume block-fading channels, where the channel condition is constant in each time slot [94]. We focus on a multicast scenario, where the MBS and FBS?s multicast a data file to the K users. The data file is divided into multiple packets with equal length 148 DL(t)D2(t)D1(t) ... Bit 0 EOF Requested layers in time slot tReceived by all To be transmitted Figure 5.1: Superposition coding and successive interference cancellation. and transmitted in sequence with the same modulation scheme. Once packet l is successfully received and decoded at the user, it requests packet (l+ 1) in the next time slot. We adopt SC and SIC to transmit these packets [94], as illustrated in Fig. 5.1. In each time slot t, the compound signal has L layers (or, levels), denoted as D1(t),???, DL(t). Each level Di(t), i = 1,???,L, is a packet requested by some of the users in time slot t. A user that has successfully decodedDi(t), for alli = 1,???,l?1, is able to subtract these signals from the received compound signal and then decodes Dl(t), while the signals from Dl+1(t) to DL(t) are treated as noise. Problem Statement For the SC and SIC scheme to work, the transmit powers for the levels should be carefully determined, such that there is a sufficiently high SNR for the levels to be decodable. It is also important to control the transmit powers of the BS?s to reduce interference and leverage frequency reuse. The annual power bill is a large part of a mobile operator?s costs [109]. Minimizing BS power consumption is important to reduce not only the operator?s OPEX, but also the global CO2 emission; an important step towards ?green? communications. Therefore, we focus on BS power allocation in this paper. The objective is to minimize the total power of all the BS?s, while guaranteeing a target rate Rtar for each user. Recall that the data file is partitioned into equal-length packets. The target rate Rtar ensures that a packet can be transmitted within a time slot, for given modulation and channel coding schemes. Define binary indicator Ikm, for all m and k, as: Ikm = ? ?? ?? 1, if user k connects to BS m 0, otherwise. (5.1) 149 Consider a general time slot t when L data packets, or levels, are requested. We formulate the optimal power allocation problem (termed OPT-Power) as follows. minimize: Msummationdisplay m=0 Lsummationdisplay l=1 Pml (5.2) subject to: Bmlog2(1 +?kmIkm)?RtarIkm, for all k (5.3) Msummationdisplay m=0 Ikm = 1,for all k (5.4) Pml ?0, for all l,m, (5.5) where Pml is the power of BS m for transmitting the level l packet; ?km is the SNR at user k if it connects to BS m. Constraint (5.3) guarantees the minimum rate at each user. Constraint (5.4) is due to the fact that each user is equipped with one transceiver, so it can only connect to one BS. Let Ul denote the set of users requesting the level l packet. A user k ?Ul has decoded all the packets up to Dl?1. It subtracts the decoded signals from the received signal and treats signals Dl+1,???,DL as noise. The SNR at user k?Ul, for l = 1,???,L?1, can be written as: ?km = HkmPml / parenleftBigg N0 +Hkm Lsummationdisplay i=l+1 Pmi parenrightBigg , (5.6) where Hkm is the random channel gain from BS m to user k and N0 is the noise power. For user k?UL that requests the last packet DL, the SNR is ?km = HkmPmL /N0. (5.7) The optimization variables in Problem OPT-Power consist of the binary variablesIkm?s and the continuous variablesPml ?s. It is an MINLP problem, which is NP-hard in general. In Section 5.3.2, we first reformulate the problem to a obtain a simpler form, and then develop effective algorithms for optimal and suboptimal solutions. 150 5.3.2 Reformulation and Power Allocation In this section, we reformulate Problem OPT-Power to obtain a simpler form, and derive an upper bound and a lower bound for the total BS power. The reformulation also leads to a simple heuristic algorithm. Finally, we introduce power allocation algorithms for three connection scenarios. Problem Reformulation Due to the monotonic logarithm functions and the binary indicators Ikm, constraint (5.3) can be rewritten as: ?kmIkm??kmIkm, m = 0,1,???,M, (5.8) where ?km = ?m =: 2Rtar/Bm?1 is the minimum SNR requirement at user k that connects to BS m. To further simplify the problem, define Qml = summationtextLi=lPmi , with QmL+1 = 0. Then power Pml is the difference Pml = Qml ?Qml+1. (5.9) Problem OPT-Power can be reformulated as: minimize Msummationdisplay m=0 Qm1 (5.10) subject to: Hkm(Qml ?Qml+1)/parenleftbigN0+HkmQml+1parenrightbigIkm??mIkm, for all k?Ul,l = 1,???,L (5.11) Qml ?Qml+1,l = 1,???,L (5.12) Msummationdisplay m=0 Ikm = 1, for all k. (5.13) 151 For l?L, constraint (5.11) can be rewritten as: Qml Ikm?bracketleftbigN0?m/Hkm + (1 + ?m)Qml+1bracketrightbigIkm. (5.14) LetUml be the subset of users connecting to BS m inUl. Since Qml ?Qml+1, (5.14) can be rewritten as, Qml = max braceleftbigg Qml+1,max k?Uml bracketleftbigN 0?m/Hkm + (1 + ?m)Qml+1 bracketrightbigbracerightbigg. (5.15) From (5.15), we define a function Qml = Fm(Qml+1,Uml ) as: Fm(Qml+1,Uml ) = ?? ? ?? Qml+1, Uml =? maxk?Uml braceleftBig N0?m Hkm + (1 + ?m)Q m l+1 bracerightBig , Uml negationslash=?. (5.16) Obviously, Fm(Qml+1,Uml ) is non-decreasing with respect to Qml+1. It follows that Qm1 = Fm(Qm2 ,Um1 ) = Fm(Fm(Qm3 ,Um2 ),Um1 ) = Fm(???(Fm(QmL+1,UmL ),UmL?1),???,Um1 ) = Fm(???(Fm(0,UmL ),UmL?1),???,Um1 ). (5.17) If none of the subsetsUml (l = 1,???,L) is empty, we can expand the above recursive term using (5.16). It follows that Qm1 = N0?m Lsummationdisplay l=1 (1 + ?m)cml max k?Uml braceleftbig1/Hk m bracerightbig, (5.18) where the exponent cml is defined as cm1 = 0 and cml+1 = cml +1. Otherwise, if a subsetUml =?for some m, we have that Qml = Qml+1, maxk?Uml braceleftbig1/Hkmbracerightbig = maxk??braceleftbig1/Hkmbracerightbig = 0, and cml = cml?1. Eq. (5.18) still holds true. 152 Finally, the objective function (5.10) can be rewritten as Msummationdisplay m=0 N0?m Lsummationdisplay l=1 (1 + ?m)cml max k?Uml braceleftbig1/Hk m bracerightbig. (5.19) Since (1 + ?m) > 0, it can be seen that to minimize the total BS power, we need to keep the cml ?s as low as possible. Performance Bounds The reformulation and simplification allow us to derive performance bounds for the total BS power consumption. First, we derive the upper bound for the objective function (5.10). Define a variable Gm = max l?{1,???,L} max k?Uml braceleftbig? m/Hkm bracerightbig, (5.20) which corresponds to the user with the worst channel condition among all users that connect to BS m. It follows that: Msummationdisplay m=0 Qm1 =N0 Msummationdisplay m=0 Lsummationdisplay l=1 (1 + ?m)cml max k?Uml braceleftbig? m/Hkm bracerightbig ?N0 Msummationdisplay m=0 Lsummationdisplay l=1 (1 + ?m)cml Gm ?N0 Msummationdisplay m=0 Gm Lsummationdisplay l=1 (1 + ?m)l?1 =N0 Msummationdisplay m=0 Gmbracketleftbig(1 + ?m)L?1bracketrightbig/?m. (5.21) In (5.21), the first inequality is from the definition of Gm. The second inequality is from the definition of cml+1. Specifically, cm1 = 0; whenUml negationslash=?, we have cml = cml?1 + 1; whenUml =?, we have cml = cml?1. It follows that cml ?l?1. Therefore, (5.21) is an upper bound on the objective function (5.10). 153 Furthermore, by defining G = maxm?{0,???,M}braceleftbigGmbracerightbig, and ? = maxm?{0,???,M}{?m}, we can get a looser upper bound from 5.21 as Msummationdisplay m=0 Qm1 ?N0G(M + 1)bracketleftbig(1 + ?)L?1bracketrightbig/?. (5.22) Next, we derive a lower bound for (5.10). Define ? ?? ?? Gl = minm?{0,???,M} maxk?Uml braceleftbig?m/Hkmbracerightbig ? = minm?{0,???,M}{?m}. (5.23) We have that Msummationdisplay m=0 Qm1 =N0 Msummationdisplay m=0 Lsummationdisplay l=1 (1 + ?m)cml max k?Uml braceleftbig? m/Hkm bracerightbig ?N0 Msummationdisplay m=0 Lsummationdisplay l=1 (1 + ?m)cml Gl ?N0 Lsummationdisplay l=1 Gl Msummationdisplay m=0 (1 + ?)cml ?N0(M + 1) Lsummationdisplay l=1 Gl(1 + ?) summationtextM m=0 cml M+1 ?N0(M + 1) Lsummationdisplay l=1 Gl(1 + ?) l?1M+1. (5.24) In (5.24), the first inequality is from the definition of Gl. The second inequality is due to the definition of ?. The third inequality is due to the fact that (1 + ?)cml is a convex function. The fourth inequality is because that each level must be transmitted by at least one BS. Thus for each level l, there is at least one cml = cml?1 +1 for some m. It follows that the sumsummationtextMm=0cml should be greater than l?1. Therefore, (5.24) provides a lower bound for (5.10). 154 Furthermore, by defining G = minl?{1,???,L}braceleftbigGlbracerightbig, we can obtain a looser lower bound from (5.24) as Msummationdisplay m=0 Qm1 ?N0G(M + 1)(1 + ?) L M+1 ?1 (1 + ?) 1M+1 ?1 . (5.25) A Simple Heuristic Scheme We first describe a greedy heuristic algorithm that solves OPT-Power with suboptimal solu- tions. With this heuristic, each user compares the channel gains from the MBS and the FBS?s. It chooses the BS with the best channel condition to connect to, thus the values of the binary vari- ables Ikm are determined. Once the binary variables are fixed, all the subsetsUml ?s are determined. Starting with QmL+1 = 0, we can apply (5.15) iteratively to find the Qml ?s. Finally, the transmit powers Pml can be computed using (5.9). With this approach, among the users requesting the level l packet, it is more likely that some of them connect to the MBS and the rest connect to some FBS?s, due to the random channel gains in each time slot. In this situation, both MBS and FBS will have to transmit all the requested data packets. Such situation is not optimal for minimizing the total power, as will be discussed in Section 5.3.2. Power Allocation Algorithms In the following, we develop three power allocation algorithms for three different connection scenarios with a more structured approach. Case I?One Base Station We first consider the simplest connection scenario where all the K users connect to the same BS (i.e., either the MBS or an FBS). Assume all the users connect to BS m. Then we have Ikm = 1 for all k, and all the subsetsUml are non-empty; Ikm? = 0 for all k and all m?negationslash= m, and all the subsetsUm?l are empty for m?negationslash= m. 155 From (5.16), we can derive the optimal solution as: Qm?l = (1 + ?m)Qm?l+1 + max k?Uml braceleftbigN 0?m/Hkm bracerightbig, = N0?m Lsummationdisplay i=l (1 + ?m)i?l max k?Uml braceleftbig1/Hk m bracerightbig, l = 1,2,???,L. (5.26) Recall that Qm?L+1 = QmL+1 = 0, the optimal power allocation for Problem OPT-Power in this case is: Pm??l = ? ?? ?? Qm?l ?Qm?l+1, m? = m, for all l 0, m?negationslash= m, for all l. (5.27) Case II?MBS and One FBS We next consider the case with one MBS and one FBS (i.e., M = 1), where each user has two choices: connecting to either the FBS or the MBS. Recall thatU0l andU1l are the subset of users who connected to the MBS and the FBS, respec- tively, and who request the level l packet. Examining (5.18), we find that the total power of BS m can be significantly reduced if one or more levels are not transmitted, since the exponent cml will not be increased in this case. Furthermore, consider the two choices: (i) not transmitting level l, and (ii) not transmitting level l? > l from BS m. The first choice will yield larger power savings, since more exponents (i.e., cml ,cml+1,???,cml??1) will assume smaller values. Therefore, we should let these two subsets be empty whenever possible, i.e., either U0l = ? or U1l = ?. According to this policy, all the users requesting the level l packet will connect to the same BS. We only need to make the optimal connection decision for each subset of users requesting the same level of packet, rather than for each individual user. Since not transmitting a lower level packet yields more power savings for a BS, we calculate the power from the lowest to the highest level, and decide whether connecting to the MBS or the FBS for users in each level. Define G0l = maxk?Ulbraceleftbig1/Hk0bracerightbig and G1l = maxk?Ulbraceleftbig1/Hk1bracerightbig. The algorithm for solving Problem OPT-Power in this case is given in Table 5.1. In Steps 2?10, the decision on whether connecting to the MBS or the FBS is made by comparing the expected increments in the total power. The user subsets U0l and U1l are determined in Steps 4 and 7. In 156 Table 5.1: Power Allocation Algorithm For Case II 1: Initialize all c0l , c1l , Q0L+1 and Q1L+1 to zero; 2: FOR l = 1 TO L 3: IF (?0(1 + ?0)c0lG0l ??1(1 + ?1)c1lG0l ) 4: SetU0l =Ul andU1l =?; 5: c0l = c0l + 1; 6: ELSE 7: SetU0l =?andU1l =Ul; 8: c1l = c1l + 1; 9: END IF 10: END FOR 11: FOR l = L TO 1 12: Q0l = F0(Q0l+1,U0l ) and P0l = Q0l ?Q0l+1; 13: Q1l = F1(Q1l+1,U1l ) and P1l = Q1l ?Q1l+1; 14: END FOR Steps 11?14, Qml ?s and the corresponding Pml ?s are computed in the reverse order, based on the determined subsetsU0l andU1l . The computational complexity of this algorithm isO(L). Case III?MBS and Multiple FBS?s Finally, we consider the general case with one MBS and multiple FBS?s in the network. Each user is able to connect to the MBS or a nearby FBS. Recall that we defineUl as the set of users requesting the level l packet, andUml as the subset of users in Ul that connect to BS m. These sets have the following properties. ? ?? ?? uniontextM m=0U m l =Ul Uml intersectiontextUm?l =?, for all m?negationslash= m. The first property is due to the fact that each user must connect to the MBS or an FBS. The second property is because each user can connect to only one BS. The user subsets connecting to different BS?s do not overlap. Therefore,Uml ?s is a partition ofUl with respect to m. 157 In addition, we defineSml as the set of possible users that are covered by BS m and request the level l packet. These sets have the following properties. ? ???? ? ???? ? uniontextM m=1S m l =S 0 l =Ul Sml intersectiontextS0l =Sml , for all mnegationslash= 0 Sml intersectiontextSm?l =?, for all m?negationslash= m and m,m?negationslash= 0. The first property is because all users in each femtocell are covered by the MBS. The second property indicates that the users covered by FBS m are a subset of the users covered by the MBS. The third property shows that the user subsets in different femtocells do not overlap. We can see that theSml ?s, for m = 1,???,M, are also a partition ofUl. Define Wm(U) = maxk?Ubraceleftbig1/Hkmbracerightbig, whereU is the set of users and m = 0,???,M. If the set U is empty, we define Wm(?) = 0. For example, consider Case II where M = 1. We have S0l =S1l =Ul, W0(Ul) = G0l , and W1(Ul) = G1l . The power allocation algorithm for Case III is presented in Table 5.2. The algorithm iteratively picks users from the eligible subsetSml and assigns them to the allocated subsetUml . In each step l, ? is the subset of FBS?s that will transmit the level l packet; the complementary set ? is the subset of FBS?s that will not transmit the level l packet. The expected increment in total power for each partition is computed, and the partition with the smallest expected increment will be chosen. ?ml is the power of BS m for transmitting the level l data packet. In Steps 6?15, the MBS and FBS combination ? is determined for transmitting the level l packet, with the lowest power ?0. In Steps 16?30, elements inSml are assigned toUml according to ?. In Steps 31?35, power sums Qml and the corresponding power allocations Pml are calculated in the reverse order from the known Uml ?s. The complexity of the algorithm isO(ML). 158 Table 5.2: Power Allocation Algorithm For Case III 1: Initialize: cml = 0 and QmL+1 = 0, for all l, m; 2: FOR l = 1 TO L 3: FOR m = 0 TO M 4: ?ml = ?m(1 + ?m)cml Wm(Sml ); 5: END FOR 6: Set ? ={1,???,M}and ? =?; 7: WHILE (?negationslash=?) 8: m? = argminm?? ?ml ; 9: Compute ?? = ?0(1 + ?0)c0lW0(uniontextm???m?Sml ); 10: IF ((summationtextm???m? ?ml + ??) < ?0) 11: Add m? to ?; 12: ?0 =summationtextm?? ?ml + ??; 13: END IF 14: Remove m? from ?; 15: END WHILE 16: IF (? =?) 17: U0l =S0l ; 18: c0l = c0l + 1; 19: SetUml =?, for all mnegationslash= 0; 20: ELSE 21: U0l =uniontextm??Sml ; 22: IF (|?|q?j, then we have p?j = 1 and q?j = 0. Otherwise, we have p?j = 0 and q?j = 1. Proof. If p?j > q?j, we have ?P0,j log(W?j + ??0,jR0,j) ? ?P1,j log(W?j + ??1,jGR1,j) according to Lemma 3. Since the objective function is linear with respect to pj and qj, the optimal value can be achieved by setting pj to its maximum value 1 and qj to its minimum value 0. The reverse statement can be proved similarly. According to Theorem 1, a CR user is connected to either the MBS or the FBS for the entire duration of a time slot in the optimal solution. That is, it does not switch between base stations during a time slot under optimal scheduling. Distributed Solution Algorithm To solve problem (5.35), we define non-negative dual vari- ables ? = [?0,?1] for the two inequality constraints. The Lagrangian function is L(p,?,?) = Ksummationdisplay j=1 bracketleftbigp j ?P0,j log(W?j +?0,jR0,j) + (1?pj) ?P1,j log(W?j +?1,jGR1,j) bracketrightbig+ ?0(1? Ksummationdisplay j=1 ?0,j) +?1(1? Ksummationdisplay j=1 ?1,j) = Ksummationdisplay j=1 Lj(pj,?0,j,?1,j,?0,?1)+?0+?1, (5.35) where Lj(pj,?0,j,?1,j,?0,?1) = pj ?P0,j log(W?j +?0,jR0,j) + (1?pj) ?P1,j log(W?j +?1,jGR1,j)??0?0,j??1?1,j. The corresponding problem can be decomposed into K sub-problems and solved iteratively. In Step ??1, for given ?0(?) and ?1(?) values, each CR user j solves the following sub-problem 171 using local information. [p?j(?),??0,j(?),??1,j(?)] = argmax pj,?0,j,?1,j?0 Lj(pj,?0,j,?1,j,?0(?),?1(?)). (5.36) There is a unique optimal solution since the objective function in (5.36) is concave. The CR users then exchange their solutions. The master dual problem, for given p(?) and ?(?), is: min ??0 L(p(?),?(?),?) = Ksummationdisplay j=1 Lj(pj(?),?0,j(?),?1,j(?),?0,?1) +?0 +?1. (5.37) Since the Lagrangian function is differentiable, the gradient iteration approach can be used. ?i(? + 1) = bracketleftBigg ?i(?)?s? parenleftBigg 1? Ksummationdisplay j=1 ??i,j(?) parenrightBiggbracketrightBigg+ , i = 0,1, (5.38) wheresis a sufficiently small positive step size and [?]+ denotes the projection onto the nonnegative axis. The updated ?i(? + 1) will again be used to solve the sub-problems, and so forth. Since the problem is convex, we have strong duality; the duality gap between the primal and dual problems is zero. The dual variables ?(?) will converge to the optimal values as ? goes to infinity. Since the optimal solution to (5.36) is unique, the primal variables p(?) and ?i,j(?) will also converge to their optimal values when ? is sufficiently large. The distributed solution procedure is presented in Table 5.3. In the table, Steps 3?8 solve the sub-problem in (5.36); Step 9 updates the dual variables. The threshold ? is a prescribed small value with 0???1. The algorithm terminates when the dual variables are sufficiently close to the optimal values. Case of Multiple Non-interfering FBS?s We next consider the case of N > 1 non-interfering FBS?s. The coverages of the FBS?s do not overlap with each other, as FBS 1 and 2 in Fig. 5.5. Consequently, each FBS can use all the available licensed channels without interfering other FBS?s. Assume each CR user knows the 172 Table 5.3: Algorithm for the Case of Single FBS 1: Set ? = 0, ?0(0) and ?1(0) to some nonnegative value; 2: DO % (each CR user j executes Steps 3?8) 3: ?0,j(?)= bracketleftBig ? P0,j ?0(?)? W?j R0,j bracketrightBig+ , ?1,j(?)= bracketleftBig ? P1,j ?1(?)? W?j R1,jG bracketrightBig+ ; 4: IFbracketleftbig?P0,j log(W?j +?0,j(?)R0,j)??0(?)?0,j(?)bracketrightbig>bracketleftbig ?P1,j log(W?j +?1,j(?)GR1,j)??1(?)?1,j(?)bracketrightbig 5: Set pj(?) = 1 and ?1,j(?) = 0; 6: ELSE 7: Set pj(?) = 0 and ?0,j(?) = 0; 8: END IF 9: MBS updates ?i(? + 1) as in (5.38); 10: ? = ? + 1; 11: WHILEparenleftbigsummationtext1i=0(?i(? + 1)??i(?))2 >?parenrightbig nearest FBS and is associate with it. LetUi denote the set of CR users associated with FBS i. The resource allocation problem becomes: maximize: Ksummationdisplay j=1 pj ?P0,j log(W?j +?0,jR0,j) + Nsummationdisplay i=1 summationdisplay j?Ui qj ?Pi,j log(W?j +?i,jGRi,j) (5.39) subject to: Ksummationdisplay j=1 ?0,j?1 summationdisplay j?Ui ?i,j?1, i = 1,???,N pj +qj = 1, j = 1,???,K ?i,j, pj, qj?0, i = 1,???,N, j = 1,???,K. Since all the available channels can be allocated to each FBS with spatial reuse, problem (5.39) can be solved using the algorithm in Table 5.3 with some modified notation: ?1,j(?) now becomes ?i,j(?) and ?1(?) becomes ?i(?), i = 1,???,N. The dual variables are iteratively updated as ?0(? + 1) = bracketleftBigg ?0(?)?s? parenleftBigg 1? Ksummationdisplay j=1 ??0,j(?) parenrightBiggbracketrightBigg+ (5.40) ?i(? + 1) = bracketleftBigg ?i(?)?s? parenleftBigg 1? summationdisplay j?Ui ??i,j(?) parenrightBiggbracketrightBigg+ , i = 1,???,N. (5.41) 173 Table 5.4: Algorithm for the Case of Multiple Non-Interfering FBS?s 1: Set ? = 0, and ?0(0) and ?i(0) to some nonnegative values, for all i; 2: DO % (each CR user j executes Steps 3?8) 3: ?0,j(?)= bracketleftBig ? P0,j ?0(?)? W?j R0,j bracketrightBig+ , ?i,j(?)= bracketleftBig ? Pi,j ?i(?)? W?j Ri,jG bracketrightBig+ ; 4: IFbracketleftbig?P0,j log(W?j +?0,j(?)R0,j)??0(?)?0,j(?)bracketrightbig>bracketleftbig ?Pi,j log(W?j +?i,j(?)GRi,j)??i(?)?i,j(?)bracketrightbig 5: Set pj(?) = 1 and ?i,j(?) = 0; 6: ELSE 7: Set pj(?) = 0 and ?0,j(?) = 0; 8: END IF 9: MBS updates ?i(? + 1) as in (5.40) and (5.41); 10: ? = ? + 1; 11: WHILE parenleftBigsummationtext N i=0(?i(? + 1)??i(?)) 2 >? parenrightBig The modified solution algorithm is presented in Table 5.4. As in the case of single FBS, the algorithm is jointly executed by the CR users and MBS, by iteratively updating the dual variables ?0(?) and ?i(?)?s, and the resource allocations ??0,j(?) and ??i,j(?)?s. It can be shown that the distributed algorithm can produce the optimal solution for problem (5.39). Case of Multiple Interfering FBS?s Formulation Finally, we consider the case of multiple interfering FBS?s. Assume that the cover- ages of some FBS?s overlap with each other, as FBS 3 and 4 in Fig. 5.5. They cannot use the same channel simultaneously, but have to compete for the available channels in the transmission phase. Define channel allocation variables ci,m for time slot t as: ci,m = ? ?? ?? 1, if channel m is allocated to FBS i 0, otherwise. (5.42) Given an allocation, the expected number of available channels for FBS i is Gi=summationtextm?A(t)ci,mPAm. We use interference graph to model the case of overlapping coverages, which is defined below. 174 FBS 1 FBS 2 FBS 3 FBS 4 Figure 5.7: Interference graph for the femtocell CR network shown in Fig. 5.5. Definition 5.1. An interference graph GI = (VI,EI) is an undirected graph where each vertex represents an FBS and each edge indicates interference between the two end FBS?s. For the example given in Fig. 5.5, we can derive an interference graph as shown in Fig. 5.7. FBS 3 and 4 cannot use the same channel simultaneously, as summarized in the following lemma. Lemma 5.4. If channel m is allocated to FBS i, the neighboring vertices of FBS i in the interfer- ence graph GI, denoted asR(i), cannot use the same channel m simultaneously. Further define index variables dki as dki = ?? ? ?? 1, if FBS i is an endpoint of link k?GI 0, otherwise. (5.43) The interference constraint can be described as summationtextNi=1dkici,m ?1, for m = 0,???,M, and for all link k?GI. We then have the following problem formulation. maximize: Ksummationdisplay j=1 pj ?P0,j log(W?j +?0,jR0,j) + Nsummationdisplay i=1 summationdisplay j?Ui qj ?Pi,j log(W?j +?i,jGiRi,j) (5.44) subject to: Ksummationdisplay j=1 ?0,j?1 summationdisplay j?Ui ?i,j?1, i = 1,???,N pj +qj = 1, j = 1,???,K Gi = summationdisplay m?A(t) ci,mPAm, i = 1,???,N Nsummationdisplay i=1 dkici,m?1,m = 0,???,M,for link k?GI, ?i,j,pj,qj,ci,m?0, i = 1,???,N, j = 1,???,K, m = 0,???,M. 175 Table 5.5: Channel Allocation Algorithm for Case of Interfering FBS?s 1: Initialize c to a zero matrix, FBS setN ={1,???,N}, and FBS-channel setC=N?A(t); 2: WHILE (Cis not empty) 3: Find FBS-channel pair{i?,m?}, such that {i?,m?}= argmax {i,m}?C {Q(c + ei,m)?Q(c)}; 4: Set c = c + ei?,m?; 5: Remove{i?,m?}fromC; 6: RemoveR(i?)?m? fromC; 7: END WHILE Solution Algorithm The optimal solution to problem (5.44) depends on the channel allocation variables ci,m. Problem (5.44) can be solved with the algorithm in Table 5.4 if the ci,m?s are known. Let Q(c) be the suboptimal objective value for a given channel allocation c, where c = [vectorc1,vectorc2,???,vectorcN] and vectorci is a vector of elements ci,m, for FBS i and channels m?A(t). If all the FBS?s are disjointedly distributed with no overlap, each FBS can use all the available channels. We have ci,m = 1 for all i and m?A(t), i.e., it is reduced to the case in Section 5.4.2. To solve problem (5.44), we first apply a greedy algorithm to allocate the available channels in A(t) to the FBS?s (i.e., to determine c). We then apply the algorithm in Table 5.4 with the computed c to obtain a near-optimal solution. Let ei,m be a matrix with 1 at position{i,m}and 0 at all other positions, representing the allocation of channel m ?A(t) to FBS i. The greedy channel allocation algorithm is given in Table 5.5, where the FBS-channel pair that can achieve the largest increase in Q(?) is chosen in each iteration. The worst case complexity of the greedy algorithm is O(N2M2). Performance Lower Bound We next present a lower bound for the greedy algorithm. Let e(l) be the l-th FBS-channel pair chosen in the greedy algorithm, and ?l denote the sequence {e(1),e(2),???,e(l)}. The increase in object value (5.44) due to the l-th allocated FBS-channel pair is denoted as ?l := ?(?l,?l?1) = Q(?l)?Q(?l?1). (5.45) 176 Since Q(?0) = Q(?) = 0, we have Lsummationdisplay l=1 ?l = Q(?L)?Q(?L?1) +???+Q(?1)?Q(?0) = Q(?L)?Q(?0) = Q(?L). For two FBS-channel pairse(l) ande(l?), we saye(l) conflicts withe(l?) when there is an edge connecting the FBS in e(l) and the FBS in e(l?) in the interference graph GI, and the two FBS?s choose the same channel. Let ? be the global optimal solution. We define ?l as the subset of ? that conflicts with allocation e(l) but not with the previous allocations{e(1),e(2),???,e(l?1)}. Lemma 5.5. Assume the greedy algorithm in Table 5.5 stops in L steps. The global optimal solution ? can be partitioned into L non-overlapping subsets ?l, l = 1,2,???,L. Proof. According to the definition of ?l, the L subsets of the optimal solution ? do not intersect with each other. Assume the statement is false, then the union of these L subsets is not equal to the optimal set ?. Let the set difference be ?L+1 = ?\(?Ll=1?l). By definition, ?L+1 does not conflict with the existing L allocations{e(1),???,e(L)}, meaning that the greedy algorithm can continue to at least the (L+ 1)-th step. This conflicts with the assumption that the greedy algorithm stops in L steps. It follows that ? =?Ll=1?l. Let ?(?2,?1) = Q(?2)?Q(?1) denote the difference between two feasible allocations ?1 and ?2. We next derive a lower bound on the performance of the greedy algorithm. We assume two properties for function ?(?2,?1) in the following. Property 5.1. Consider FBS-channel pair sets ?1, ?2, and ?, satisfying ?1 ??2 and ???2 =?. We have ?(?2??,?1??)??(?2,?1). Property 5.2. Consider FBS-channel pair sets ?, ?1, and ?2 satisfying ?1?? =?, ?2?? =?, and ?1??2 =?. We have ?(?1??2??,?)??(?1??,?) + ?(?2??,?). In Property 1, we have ???1 = ? since ?1 ? ?2 and ???2 = ?. This property states that the incremental objective value does not get larger as more channels are allocated and as 177 the objective value gets larger. Property 2 states that the incremental objective value achieved by allocating multiple FBS-channel pair sets does not exceed the sum of the incremental objective values achieved by allocating each individual FBS-channel pair set. These are generally true for many resource allocation problems [71]. Since we choose the maximum incremental allocation in each step of the greedy algorithm, we have Lemma 5.6 that directly follows Step 3 in Table 5.5. Lemma 5.6. For any FBS-channel pair ? ? ?l, we have Q(?l?1 ??)?Q(?l?1) = ?(?l?1 ? ?,?l?1)??l. Lemma 5.7. Assume the greedy algorithm stops in L steps, we have Q(?)?Q(?L) + Lsummationdisplay l=1 summationdisplay ???l ?(???l?1,?l?1). Proof. The following inequalities hold true according to the properties of the ?(?,?) function: Q((?Li=l+1?i)??l) = Q((?Li=l+2?i)??l) + ?((?Li=l+1?i)??l,(?Li=l+2?i)??l) ?Q((?Li=l+2?i)??l) + ?(?l+1??l,?l) ?Q((?Li=l+2?i)??l+1) + ?(?l+1??l,?l) ?Q((?Li=l+2?i)??l+1) + summationdisplay ???l+1 ?(???l,?l). We have ?0 =?and ?L+1 =?(see Lemma 5.5). With induction from l = 0 to l = L?1, we have Q((?Li=1?i)??) = Q(?) and Q(?)?Q(?L) +summationtextLl=1summationtext???l ?(???l?1,?l?1). Lemma 5.8. The maximum size of ?l is equal to the degree, in the interference graph GI, of the FBS selected in the l-th step of the greedy algorithm, which is denoted as D(l). 178 Proof. Once FBS i is allocated with channel m, the neighboring FBS?s in GI, R(i), cannot use the same channel m anymore due to the interference constraint. The maximum number of FBS- channel pairs that conflict with the selected FBS-channel pair{i,m}, i.e., the maximum size of ?l, is equal to the degree of FBS i in GI. Then we have Theorem 5.2 that provides a lower bound on the objective value achieved by the greedy algorithm given in Table 5.5. Theorem 5.2. The greedy algorithm can achieve an objective value that is at least 11+Dmax of the global optimum, where Dmax is the maximum node degree in the interference graph GI of the femtocell CR network. Proof. According to Lemmas 5.7 and 5.8, we have: Q(?)?Q(?L) + Lsummationdisplay l=1 D(l)?l = Q(?L) + ?D Lsummationdisplay l=1 ?l = (1 + ?D)Q(?L), (5.46) where ?D = summationtextLl=1D(l)?l/summationtextLl=1 ?l. The second equality is due to the facts that summationtextLl=1 ?l = Q(?L). To further simplify the bound, we replace D(l) with the maximum node degree Dmax. We then have ?D?summationtextLl=1Dmax?l/summationtextLl=1 ?l = Dmax and 1 1 +DmaxQ(?)?Q(?L)?Q(?), (5.47) which provides a lower bound on the performance of the greedy algorithm. When there is a single FBS in the CR network, we have Dmax = 0 and Q(?L) = Q(?) according to Theorem 5.2. The proposed algorithm produces the optimal solution. In the case of multiple non-interfering FBS?s, we still have Dmax = 0 and can obtain the optimal solution using the proposed algorithm. For the femtocell CR network given in Fig. 5.5 (with interference graph 179 shown in Fig. 5.7), we have Dmax = 1 and the low bound is a half of the global optimal. Note that (5.46) provides a tighter bound for the optimum than (5.47), but with higher complexity. These are interesting performance bounds since they bound the achievable video quality, an application layer performance measure, rather than lower layer metrics (e.g., bandwidth or time share). 5.4.3 Simulation Results We evaluate the performance of the proposed algorithms using MATLAB and JSVM 9.13 Video codec. Two scenarios are used in the simulations: a single FBS CR network and a CR network with interfering FBS?s. In every simulation, we compare the proposed algorithms with the following three more straightforward heuristic schemes: ? Heuristic 1 based on equal allocation: each CR user chooses the better channel (i.e., the common channel or a licensed channel) based on the channel conditions; time slots are equally allocated among active CR users; ? Heuristic 2 exploiting multiuser diversity: the MBS and each FBS chooses one active CR user with the best channel condition; the entire time slot is allocated to the selected CR user. ? SCA-MAC proposed in [23]: with this scheme, the successful transmission rate is evaluated based on channel packet loss rate and collision probability with primary users; the channel- user pair with the highest transmission probability is selected. We choose SCA-MAC because it adopts similar models and assumptions as in this paper. Once the channels are selected, the same distributed algorithm is used for scheduling video data for all the three schemes. We adopt the Raleigh block fading model and the packet loss probability is between [0.004, 0.028]. The frame rate is set to 30 fps and the GoP size is 16. The base layer mode is set to be AVC compatible. The motion search mode is set to Fast Search with search range 32. Each point in the figures presented in this section is the average of 10 simulation runs with different random seeds. We plot 95% confidence intervals in the figures, which are generally negligible. 180 0 50 100 150 200 250 300 350 4000.74 0.76 0.78 0.8 0.82 0.84 0.86 0.88 0.9 0.92 Iteration Index (?) Dual Variables ?0(k) ?1(k) Figure 5.8: Convergence of the two dual variables in the single FBS case. Case of Single FBS In the first scenario, there are M = 8 channels and the channel parameters Pm01 and Pm10 are set to 0.4 and 0.3, respectively, for all m. The maximum allowable collision probability ?m is set to 0.2 for all m. There is one FBS and three active CR users. Three Common Intermediate Format (CIF, 352?288) video sequences are streamed to the CR users, i.e., Bus to CR user 1, Mobile to CR user 2, and Harbor to CR user 3. We have T = 10 as the delivery deadline. Both probabilities of false alarm ? and miss detection ? are set to 0.3 for all the FBS?s and CR users, unless otherwise specified. First we investigate the convergence of the distributed algorithm. The traces of the two dual variables are plotted in Fig. 5.8. To improve the convergence speed, the correlation in adjacent time slots can be exploited. In particular, we set the optimal values for the optimization variables in the previous time slot as the initialization values for the variables in the current time slot. By doing so, the convergence speed can be improved. It can be seen that both dual variables converge to their optimal values after 300 iterations. After convergence, the optimal solution for the primary problem can be obtained. 181 4 5 6 7 8 9 10 11 1232 33 34 35 36 37 38 Number of Licensed Channels (M) Y?PSNR(dB) Proposed scheme (9) and PSNR Heuristic 1 (9) and PSNR Heuristic 2 (9) and PSNR SCA?MAC (9) and PSNR Figure 5.9: Single FBS: received video quality vs. number of channels (computed with (9) and measured by PSNR). Our proposed scheme achieves the best performance among the three algorithms, with up to 4.3 dB improvement over the two heuristic schemes and up to 2.5 dB over SCA-MAC. Such gains are significant with regard to video quality, since a 0.5 dB difference is distinguishable by human eyes. Compared to the two heuristic schemes and SCA-MAC, the video quality of our proposed scheme is well balanced among the three users, indicating better fairness performance. In Fig. 5.9, we examine the impact of the number of channels M on received video quality. First, we validate the video quality measure used in our formulation by comparing the PSNR value computed using (5.32) with that computed from real decoded video frames. The average PSNR for three received videos are plotted in the figure. It can be seen that the real PSNRs are very close to those predicted by (5.32), with overlapping confidence intervals. This is also consistent with the results shown in Fig. 5.6. Second, as expected, the more licensed channels, the more spectrum opportunities for CR users and the higher PSNR for received videos. SCA-MAC performs better than two heuristics, but is inferior to the proposed scheme. We also plot the MS-SSIM of the received videos at the three CR users in Fig. 5.10 [112]. Similar observations can be made from the MS-SSIM plot. All MS-SSIMs for the four curves are more than 0.97 and very close to 1. The proposed scheme still outperforms the other three 182 4 5 6 7 8 9 10 11 120.974 0.976 0.978 0.98 0.982 0.984 0.986 0.988 0.99 Number of Licensed Channels (M) Multi?scale SSIM Proposed scheme Heuristic 1 Heuristic 2 SCA?MAC Figure 5.10: Single FBS: received video quality vs. number of channels (measured by MS-SSIM). schemes. In the remaining figures, we will use model predicted PSNR values, since the model (5.32) is sufficient to predict the real video quality. In Fig. 5.11, we demonstrate the impact of channel utilization ? on received video quality. The average PSNRs achieved by the four schemes are plotted when ? is increased from 0.3 to 0.7. Intuitively, a smaller ? allows more spectrum opportunities for video transmission. This is illustrated in the figure where all the three curves decrease as ? gets larger. The performance of both heuristics are close and the proposed scheme achieves a gain about 3 dB over the heuristics and 2 dB over SCA-MAC. We also compare the MGS and FGS videos while keeping other parameters identical. We find that MGS video achieves over 0.5 dB gain in video quality over FGS video. The results are omitted for brevity. Case of Interfering FBS?s We next investigate the second scenario with three FBS?s, and each FBS has three active CR users. Each FBS streams three different videos to the corresponding CR users. The coverages of FBS 1 and 2 overlap with each other, and the coverages of FBS 2 and 3 overlap with each other. 183 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.732 33 34 35 36 37 38 39 Channel Utilization (?) Y?PSNR (dB) Proposed scheme Heuristic 1 Heuristic 2 SCA?MAC Figure 5.11: Single FBS: received video quality vs. channel utilization. In Fig. 5.12, we examine the impact of the number of channels M on the received video quality. The average PSNRs of all the active CR users are plotted in the figure when we increase M from 12 to 20 with step size 2. As mentioned before, more channels imply more transmission opportunities for video transmission. In this scenario, heuristic 2 (with a multiuser diversity ap- proach) outperforms heuristic 1 (with an equal allocation approach). But its PSNRs are still about 0.3?0.5 dB lower that those of the proposed algorithm. The proposed scheme has up to 0.4 dB improvement over SCA-MAC. In Fig. 5.12, we also plot an upper bound on the optimal objective value, which is obtained as in (5.46). It can be seen that the performance of our proposed scheme is close to optimal solution since the gap between the upper bound and our scheme is generally small (about 0.5 dB). Next, we examine the impact of sensing errors on the received video quality. In Fig. 5.13, we test five pairs of{?,?}values: {0.2,0.48},{0.24,0.38},{0.3,0.3},{0.38,0.24}, and{0.48,0.2}. It is interesting to see that the performance of all the four schemes get worse when the probability of one of the two sensing errors gets large. We can trade-off between false alarm and miss detection probabilities to find the optimal operating point for the spectrum sensors. Moreover, the dynamic range of video quality is not big for the range of sensing errors simulated, compared to that in 184 12 13 14 15 16 17 18 19 2033 33.5 34 34.5 35 35.5 36 Number of Licensed Channels (M) Y?PSNR(dB) Upper bound Proposed scheme Heuristic 1 Heuristic 2 SCA?MAC Figure 5.12: Interfering FBS?s: received video quality vs. number of channels. 0.2 0.25 0.3 0.35 0.4 0.45 0.533 33.5 34 34.5 35 35.5 36 Probability of False Alarm (?) Y?PSNR (dB) Upper bound Proposed scheme Heuristic 1 Heuristic 2 SCA?MAC Figure 5.13: Interfering FBS?s: received video quality vs. sensing error probability. Fig. 5.12. This is because both sensing errors are modeled and treated in the algorithms. Again, our proposed scheme outperforms the two heuristic schemes and SCA-MAC with considerable margins for the entire range. We also investigate the impact of the bandwidth of the common channelB0. In this simulation, we fix B1 at 0.3 Mbps and increase B0 from 0.1 Mbps to 0.5 Mbps with step size 0.1 Mbps. The 185 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.533 33.5 34 34.5 35 35.5 36 Bandwidth of Common Channel (MHz) Y?PSNR (dB) Upper bound Proposed scheme Heuristic 1 Heuristic 2 SCA?MAC Figure 5.14: Interfering FBS?s: received video quality vs. bandwidth of the common channel. results are presented in Fig. 5.14. We notice that the average video quality increases rapidly as the common channel bandwidth is increased from 0.1 Mbps to 0.3 Mbps. Beyond 0.3 Mbps, the increases of the PSNR curves slow down and the curves get flat. This implies that a very large bandwidth for the common channel is not necessary, since the gain for additional bandwidth diminishes as B0 gets large. Again, the proposed scheme outperforms the other three schemes and the gap between our scheme and the upper bound is small. Next, we stop the distributed algorithm after a fixed amount of time, and evaluate the subop- timal solutions. In particular, we vary the duration of time slots, and let the distributed algorithm run for 5% of the time slot duration at the beginning of the time slot. Then the solution obtained this way will be used for the video data transmissions. The results are presented in Fig. 5.15. It can be seen that when the time slot is 5 ms, the algorithm does not converge after 5%?5 = 0.25 ms and the PSNR produced by the distributed algorithm is close to that of Heuristic 1, and lower than those of Heuristic 2 and SCA-MAC. When the time slot is sufficiently large, the algorithm can get closer to the optimal and the proposed algorithm produces better video quality as compared to the two heuristic algorithms and SCA-MAC. Beyond 20 ms, the increase in PSNR is small since all 186 20 40 60 80 10033 33.5 34 34.5 35 35.5 36 Time Slot Duration (ms) Y?PSNR (dB) Upper bound Proposed scheme Heuristic 1 Heuristic 2 SCA?MAC Figure 5.15: Video quality achieved by the algorithms when they are only executed for 5% of the time slot duration. the curves gets flat. Therefore the proposed algorithm could be useful even when there is no time for it to fully converge to the optimal. During the simulations, we find the collision rate with primary users are strictly kept below the prescribed collision tolerance ?. These results are omitted for brevity. 5.5 Conclusions In this chapter, we first addressed the problem of multicasting FGS video in CR networks. The problem formulation took video quality and proportional fairness as objectives, while con- sidering cross-layer design factors such as FGS coding, spectrum sensing, opportunistic spectrum access, primary user protection, scheduling, error control and modulation. We proposed efficient optimization and scheduling algorithms for highly competitive solutions, and proved the complex- ity and optimality bound of the proposed greedy algorithm. Our simulation results demonstrate not only the viability of video over CR networks, but also the efficacy of the proposed approach. Then, we studied the challenging problem of streaming multiple scalable videos in a multi-hop CR network. The problem formulation considered spectrum sensing and sensing errors, spectrum 187 access and primary user protection, video quality and fairness, and channel/path selection for con- current video sessions. We first solved the formulated MINLP problem using a sequential fixing scheme that produces lower and upper bounds on the achievable video quality. We then applied dual decomposition to derive a distributed algorithm, and analyzed its optimality and convergence performance. Our simulations validated the efficacy of the proposed scheme. 188 Chapter 6 Conclusions and Future Work 6.1 Conclusions In the previous chapters, we investigated several challenging problems of effective CR net- working and scalable video streaming over CR networks. Our research consisted of network mod- eling, cross-layer design and optimization, performance analysis, algorithm development, and sim- ulation validation. In Chapter 2, we first studied the problem of design and analysis of MAC protocols for CR networks. We explicitly considered sensing errors in the design of MAC protocols and developed analytical models to evaluate the performance of the proposed protocols. In the second part, we considered the problem of interference mitigation via channel assignment and power allocation for CR users. We proposed a distributed greedy algorithm that only needs local channel gain information. It was shown to outperform other two alternatives via simulations. In Chapter 3, a more challenging problem, scalable video streaming in CR networks, was investigated. We first studied the problem of scalable video multicast over infrastructure based CR networks. We proposed an efficient greedy algorithm with proved complexity and optimal- ity bound. Then, we considered the problem of streaming multiple videos over multi-hop CR networks. We developed a distributed algorithm by applying dual decomposition and proved its optimality and convergence conditions. In Chapter 4, we first investigated the problem of cooperative relay in CR networks. We compared two typical cooperative relay strategies and developed an analysis for the comparison. We found each of the strategies performed better in a certain parameter range and diversity gain was achieved by cooperative relays. Then, we investigated the problem of interference alignment for MGS video streaming in a cooperative relay enhanced CR network. We developed a distributed 189 optimal algorithm for the case of a single channel and the case of multi-channel bonding, with proven convergence and convergence speed. We also proposed a greedy algorithm for the multi- channel without channel bonding case, with a proven performance bound. In Chapter 5, we first investigated the problem of data multicast in femtocell networks that incorporates SC and SIC. We developed optimal and near-optimal algorithms with low compu- tational complexity, as well as performance bounds. Then, we tackled the problem of streaming multiple MGS videos in a femtocell CR networks. A distributed optimal algorithm was devel- oped in the case of non-interfering FBS?s and a greedy algorithm for near-optimal solutions was proposed in the case of interfering FBS?s with proved lower bound. 6.2 Summary of Contributions Wireless video has been a challenging area with considerable research efforts. However, video over CR networks has not been well studied, since the main stream CR research has focused on spectrum sensing and access. It was not clear if video can be offered in such highly dynamic networks even a few years ago. There is a compelling need for innovative research in this area given the Cisco prediction of exploding wireless video traffic in the next few years. In this dissertation, we investigated the problem of effective CR networking with applica- tion to multi-user video communications over four emerging CR networking paradigms, including infrastructure-based CR networks, multi-hop ad hoc CR networks, CR femtocell networks, and relay-assisted CR networks. This research provides in-depth treatment of the problems with both theory and algorithm ingredients. The findings not only successfully demonstrate the feasibility of video CR networks, but also shed useful insights on developing practical CR video systems. 190 6.3 Open Problems and Future Work Although considerable progresses have been made through this dissertation work in the area of video over CR networks, there are many interesting open problems to be explored in this im- portant problem area. Some of such open problems are briefly described below, which we plan to investigate in our future research. In most of our prior work, we assumed that the occupancy of each licensed channel evolves over time following a two state discrete-time Markov process and the primary user activities on different channels are independent. Although this assumption makes the problem manageable, it may not hold true in certain CR networks. The primary user transmission may be modeled as a more general process, while the primary transmissions on different channels may be statistically correlated. Thus, a more sophisticate spectrum sensing and access scheme is required to be inte- grated into the cross-layer optimization framework. The accuracy of the sensing process could be improved by exploiting the sensing results from adjacent channels and historic sensing results. Similarly, another assumption is that the lowest video quality requirement for CR users can always be guaranteed. However, the network capacity for CR users strongly depends on both the primary user transmissions and randomly fading and shadowing channels. Therefore, an admission control mechanism is required that can estimate the level of QoS that a new video session will have and whether there is enough bandwidth available to serve that session. A simple yet efficient admission control mechanism that considers both primary user activities and channel conditions is essential for QoS provisioning for video over CR networks. We investigated several challenging problems in CR networks using video as a reference ap- plication. In an operating CR network, there will be multiple applications that generate different types of traffic flows, all sharing the extra bandwidth provided by CRs. It is thus interesting to investigate how to provide quality of service (QoS) guarantees for different traffic flows each with different characteristics and different QoS requirements. This is a general problem for both wire- line and wireless networks. The Internet adopts the Integrated Services (intserv) and Differenti- ated Services (diffserv) approaches to address this problem. We conjecture a certain classification 191 scheme should be adopted to intelligently identify and classify application traffic according to their characteristics and QoS requirements, and a resource allocation scheme will be used to treat the different classes of traffic flows differently. These are interesting problems that worth further investigation. We presented a theoretical framework for video streaming in CR networks and demonstrated the performance with extensive simulations. In the future, we are interested in building a CR video streaming testbed network, such that the system performance can be demonstrated under a realistic wireless environment. Our research will focus on the combination of hardware components (e.g. USRP models) and software techniques (e.g. network optimization algorithms). Such a CR video testbed can not only validate the theoretical results, but also reveal new practical constraints that should be considered in the modeling and analysis, as well identifying new research problems. 192 Bibliography [1] I. Akyildiz, W. Lee, M. Vuran, and S. Mohanty, ?NeXt Generation/dynamic spectrum ac- cess/cognitive radio wireless networks: A survey,? Elsevier Computer Networks, vol. 50, no. 13, pp. 2127?2159, Sept. 2006. [2] Cisco, ?Cisco visual networking index: Global mobile data traffic forecast update, 2009- 2014,? Feb. 2010, [online] Available: www.cisco.com/en/US/solutions/collateral/ns341/ ns525/ns537/ns705/ns827/white paper c11-520862.html. [3] Q. Zhang, J. Jia, and J. Zhang, ?Cooperative relay to improve diversity in cognitive radio networks,? IEEE Commun. Mag., vol. 47, no. 2, pp. 111?117, Feb. 2009. [4] J. Jia, J. Zhang, and Q. Zhang, ?Cooperative relay for cognitive radio networks,? in Proc. IEEE INFOCOM?09, Apr. 2009, pp. 2304?2312. [5] V. Chandrasekhar, J. G. Andrews, and A. Gatherer, ?Femtocell networks: a survey,? IEEE Commun. Mag., vol. 46, no. 9, pp. 59?67, Sept. 2008. [6] D. Hu and S. Mao, ?Design and analysis of a sensing error-aware MAC protocol for cogni- tive radio networks,? in Proc. IEEE GLOBECOM?09, Honolulu, HI, Nov./Dec. 2009. [7] ??, ?Co-channel and adjacent channel interference mitigation in cognitive radio net- works,? in Proc. IEEE MILCOM?11, Baltimore, MD, Nov. 2011, pp. 1?6. [8] D. Hu, S. Mao, Y. Hou, and J. Reed, ?Fine grained scalability video multicast in cognitive radio networks,? IEEE J. Sel. Areas Commun., vol. 29, no. 3, pp. 334?344, Apr. 2010. [9] D. Hu and S. Mao, ?Streaming scalable videos over multi-hop cognitive radio networks,? IEEE Trans. Wireless Commun., vol. 9, no. 11, pp. 3501?3511, Nov. 2010. [10] ??, ?Cooperative relay in cognitive radio networks: Decode-and-forward or amplify-and- forward?? in IEEE GLOBECOM?10, Miami, FL, Dec. 2010, pp. 1?5. [11] ??, ?Cooperative relay with interference alignment for video over cognitive radio net- works,? in Proc. IEEE INFOCOM?12, Orlando, FL, Mar. 2012. [12] ??, ?Multicast in femtocell networks: a successive interference cancellation approach,? in Proc. IEEE GLOBECOM?11, Huston, TX, Dec. 2011, pp. 1?6. [13] ??, ?On medium grain scalable video streaming over cognitive radio femtocell networks,? IEEE J. Sel. Areas Commun., vol. 30, no. 4, Apr. 2012. 193 [14] Q. Zhao and B. Sadler, ?A survey of dynamic spectrum access,? IEEE Signal Process. Mag., vol. 24, no. 3, pp. 79?89, May 2007. [15] Y. Zhao, S. Mao, J. Neel, and J. H. Reed, ?Performance evaluation of cognitive radios: Met- rics, utility functions, and methodologies,? Proc. IEEE, Special Issue on Cognitive Radio, vol. 97, no. 4, pp. 642?659, Apr. 2009. [16] A. Motamedi and A. Bahai, ?MAC protocol design for spectrum-agile wireless networks: Stochastic control approach,? in Proc. IEEE DySPAN?07, Dublin, Ireland, Apr. 2007, pp. 448?451. [17] S. Geirhofer, L. Tong, and B. Sadler, ?Cognitive medium access: constraining interference based on experimental models,? IEEE J. Sel. Areas Commun., vol. 26, no. 1, pp. 95?105, Jan. 2008. [18] L. Le and E. Hossain, ?OSA-MAC: A MAC protocol for opportunistic spectrum access in cognitive radio networks,? in Proc. IEEE WCNC?08, Las Vegas, NV, Mar./Apr. 2008, pp. 1426?1430. [19] Q. Zhao, L. Tong, A. Swami, and Y. Chen, ?Decentralized cognitive MAC for opportunistic spectrum access in ad hoc networks: A POMDP framework,? IEEE J. Sel. Areas Commun., vol. 25, no. 3, pp. 589?600, Apr. 2007. [20] H. Su and X. Zhang, ?Cross-layer based opportunistic MAC protocols for QoS provisionings over cognitive radio wireless networks,? IEEE J. Sel. Areas Commun., vol. 26, no. 1, pp. 118?129, Jan. 2008. [21] J. Jia, Q. Zhang, and X. Shen, ?HC-MAC: A hardware-constrained cognitive MAC for efficient spectrum management,? IEEE J. Sel. Areas Commun., vol. 26, no. 1, pp. 106?117, Jan. 2008. [22] B. Hamdaoui and K. Shin, ?OS-MAC: An efficient MAC protocol for spectrum-agile wire- less networks,? IEEE Trans. Mobile Comput., vol. 7, no. 8, pp. 915?930, Aug. 2008. [23] A. Hsu, D. Wei, and C. Kuo, ?A cognitive MAC protocol using statistical channel allocation for wireless ad-hoc networks,? in Proc. IEEE WCNC?07, Hong Kong, P.R. China, Mar. 2007, pp. 105?110. [24] Y. Chen, Q. Zhao, and A. Swami, ?Joint design and separation principle for opportunistic spectrum access in the presence of sensing errors,? IEEE Trans. Inf. Theory, vol. 54, no. 5, pp. 2053?2071, May 2008. [25] Y. R. Kondareddy and P. Agrawal, ?Synchronized mac protocol for multi-hop cognitive radio networks,? in Proc. IEEE Int. Conf. Communications ICC ?08, Beijing, China, May 2008, pp. 3198?3202. [26] Y. R. Kondareddy, P. Agrawal, and K. Sivalingam, ?Cognitive radio network setup without a common control channel,? in Proc. IEEE Military Communications Conf. MILCOM 2008, San Diego, CA, Nov. 2008, pp. 1?6. 194 [27] L. Yang and M.-S. Alouini, ?Performance comparison of different selection combining al- gorithms in presence of co-channel interference,? IEEE Trans. Veh. Technol., vol. 55, no. 2, pp. 559?571, Mar. 2006. [28] J. Nachtigall, A. Zubow, and J.-P. Redlich, ?The impact of adjacent channel interference in multi-radio systems using IEEE 802.11,? in Proc. IWCMC?08, Crete Island, Greece, Aug. 2008, pp. 874?881. [29] V. Angelakis, S. Papadakis, V. A. Siris, and A. Traganitis, ?Adjacent channel interference in 802.11a is harmful: Testbed validation of a simple quantification model,? IEEE Commun. Mag., vol. 49, no. 3, pp. 160?166, Mar. 2011. [30] M. G. Sanchez, M. A. Acuna, I. Cuinas, R. M. Rodriguez-Osorio, L. de Haro, and A. Garcia- Pino, ?Cochannel and adjacent channel interference in actual terrestrial TV scenarios - part I: Field measurements,? IEEE Trans. Broadcast., vol. 48, no. 2, pp. 111?115, June 2002. [31] Z. A. Shamsan, L. F. Abdulrazak, and T. A. Rahman, ?Co-channel and adjacent channel interference evaluation for IMT-Advanced coexistence with existing fixed systems,? in Proc. IEEE International RF and Microwave Conference 2008, Kuala Lumpur, Malaysia, Dec. 2008, pp. 65?69. [32] C.-S. Sum, R. Funada, J. Wang, T. Baykas, M. A. Rahman, and H. Harada, ?Error perfor- mance and throughput evaluation of a multi-Gbps millimeter-wave WPAN system in the presence of adjacent and co-channel interference,? IEEE J. Sel. Areas Commun., vol. 27, no. 8, pp. 1433?1442, Oct. 2009. [33] K. Gulati, B. Evans, J. Andrews, and K. Tinsley, ?Statistics of co-channel interference in a field of Poisson and Poisson-Poisson clustered interferers,? IEEE Trans. Signal Process., vol. 58, no. 12, pp. 6207?6222, Dec. 2010. [34] E. Obregon, L. Shi, J. Ferrer, and J. Zander, ?A model for aggregate adjacent channel in- terference in TV white space,? in Proc. IEEE VTC-Spring 2011, Budapest, Hungary, May 2011, pp. 1?5. [35] H.-C. Lee, D.-C. Oh, and Y.-H. Lee, ?Mitigation of inter-femtocell interference with adap- tive fractional frequency reuse,? in Proc. IEEE ICC?10, Cape Town, South Africa, May 2010, pp. 1?5. [36] A. M. A. Ahmed and I. Marsland, ?Co-channel interference cancellation in multihop relay networks,? in Proc. IEEE ICC?08 Workshops, Beijing, P.R. China, May 2008, pp. 62?67. [37] ??, ?Co-channel interference cancellation in wireless cellular networks,? in Proc. IEEE VTC-Spring 2008, Marina Bay, Singapore, May 2008, pp. 698?702. [38] G. Miao, Y. Li, N. Himayat, and S. Talwar, ?Co-channel interference avoidance MAC in wireless cellular networks,? IEEE Trans. Commun., vol. 57, no. 11, pp. 3897?3405, Nov. 2009. 195 [39] O. Bendov and C. B. Patel, ?Television receiver optimization in the presence of adjacent channel interference,? IEEE Trans. Broadcast., vol. 51, no. 1, pp. 38?42, Mar. 2005. [40] D. Gidony and I. Kalet, ?Adjacent channel interference cancellation for MSK-type signals using antenna diversity in Rayleigh fading environment,? IEEE Trans. Commun., vol. 52, no. 2, pp. 317?325, Feb. 2004. [41] A. Babaei and B. Jabbari, ?Interference modeling and avoidance in spectrum underlay cog- nitive wireless networks,? in Proc. IEEE Int Communications (ICC) Conf, 2010, pp. 1?5. [42] D. Hu, S. Mao, and J. Reed, ?On video multicast in cognitive radio networks,? in Proc. IEEE INFOCOM?09, Rio de Janeiro, Brazil, Apr. 2009. [43] H. Nan, T.-I. Hyon, and S.-J. Yoo, ?Distributed coordinated spectrum sharing MAC protocol for cognitive radio,? in Proc. IEEE DySPAN?07, Dublin, Ireland, Apr. 2007, pp. 240?249. [44] C. Corderio, K. Challapali, D. Birru, and S. Shankar, ?IEEE 802.22: An introduction to the first wireless standard based on cognitive radios,? J. Commun., vol. 1, no. 1, pp. 38?47, Apr. 2006. [45] S. Kompella, S. Mao, Y. T. Hou, and H. D. Sherali, ?On path selection and rate allocation for video in wireless mesh networks,? IEEE/ACM Trans. Netw., vol. 17, no. 1, pp. 212?224, Feb. 2009. [46] D. Hu and S. Mao, ?Resource allocation for medium grain scalable videos over femtocell cognitive radio networks,? in Proc. IEEE ICDCS?11, Minneapolis, MN, June 2011, pp. 258?267. [47] Y. Hou, Y. Shi, and H. Sherali, ?Spectrum sharing for multi-hop networking with cognitive radios,? IEEE J. Sel. Areas Commun., vol. 26, no. 1, pp. 146?155, Jan. 2008. [48] M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali, Linear Programming and Network Flows, 4th ed. New York, NY: John Wiley & Sons, Inc., 2010. [49] S. Mao, S. Lin, Y. Wang, S. S. Panwar, and Y. Li, ?Multipath video transport over wireless ad hoc networks,? IEEE Wireless Commun., vol. 12, no. 4, pp. 42?49, Aug. 2005. [50] S. Mao, S. Kompella, Y. T. Hou, H. D. Sherali, and S. F. Midkiff, ?Routing for multiple con- current video sessions in wireless ad hoc networks,? in Proc. IEEE ICC?05, Seoul, Korea, May 2005, pp. 1229?1235. [51] IEEE, ?Draft standard for wireless regional area networks part 22: Cognitive wireless RAN medium access control (MAC) and physical layer (PHY) specifications: Policies and proce- dures for operation in the TV bands,? May 2007, IEEE P802.22 Draft Standard (D0.3). [52] M. van der Schaar, S. Krishnamachari, S. Choi, and X. Xu, ?Adaptive cross-layer protection strategies for robust scalable video transmission over 802.11 WLANs,? IEEE J. Sel. Areas Commun., vol. 21, no. 10, pp. 1752?1763, Dec. 2003. 196 [53] M. Wien, H. Schwarz, and T. Oelbaum, ?Performance analysis of SVC,? IEEE Trans. Cir- cuits Syst. Video Technol., vol. 17, no. 9, pp. 1194?1203, Sept. 2007. [54] N. Laneman, D. Tse, and G. Wornell, ?Cooperative diversity in wireless networks: Efficient protocols and outage behavior,? IEEE Trans. Inf. Theory, vol. 50, no. 11, pp. 3062?3080, Nov. 2004. [55] R. Urgaonkar and M. J. Neely, ?Opportunistic scheduling with reliability guarantees in cog- nitive radio networks,? IEEE Trans. Mobile Comput., vol. 8, no. 6, pp. 766?777, June 2009. [56] T. Shu and M. Krunz, ?Throughput-efficient sequential channel sensing and probing in cog- nitive radio networks under sensing errors,? in Proc. ACM MobiCom?09, Beijing, China, Sept. 2009, pp. 37?48. [57] Q. Zhao, S. Geirhofer, L. Tong, and B. Sadler, ?Opportunistic spectrum access via periodic channel sensing,? IEEE Trans. Signal Process., vol. 36, no. 2, pp. 785?796, Feb. 2008. [58] A. Fattahi, F. Fu, M. van der Schaar, and F. Paganni, ?Mechanism-based resource allocation for multimedia transmission over spectrum agile wireless networks,? IEEE J. Sel. Areas Commun., vol. 25, no. 3, pp. 601?612, Apr. 2007. [59] H.-P. Shiang and M. van der Schaar, ?Dynamic channel selection for multi-user video streaming over cognitive radio networks,? in Proc. IEEE ICIP?08, San Diego, CA, Oct. 2008, pp. 2316?2319. [60] H. Luo, S. Ci, and D. Wu, ?A cross-layer design for the performance improvement of real- time video transmission of secondary users over cognitive radio networks,? IEEE Trans. Circuits Syst. Video Technol., vol. 21, no. 8, pp. 1040?1048, Aug. 2011. [61] S. Ali and F. Yu, ?Cross-layer QoS provisioning for multimedia transmissions in cognitive radio networks,? in Proc. IEEE WCNC?09, Budapest, Hungary, Apr. 2009, pp. 1?5. [62] Z. Guan, L. Ding, T. Melodia, and D. Yuan, ?On the effect of cooperative relaying on the performance of video streaming applications in cognitive radio networks,? in Proc. IEEE ICC?11, Kyoto, Japan, June 2011, pp. 1?6. [63] S. Mao, X. Cheng, Y. Hou, and H. Sherali, ?Multiple description video multicast in wireless ad hoc networks,? ACM/Kluwer Mobile Netw. Appl. J., vol. 11, no. 1, pp. 63?73, Jan. 2006. [64] W. Wei and A. Zakhor, ?Multiple tree video multicast over wireless ad hoc networks,? IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 1, pp. 2?15, Jan. 2007. [65] S. Deb, S. Jaiswal, and K. Nagaraj, ?Real-time video multicast in WiMAX networks,? in Proc. IEEE INFOCOM?08, Phoenix, AZ, Apr. 2008, pp. 1579?1587. [66] Y. Hou, Y. Shi, and H. Sherali, ?Optimal spectrum sharing for multi-hop software defined radio networks,? in Proc. IEEE INFOCOM?07, Anchorage, AK, Apr. 2007, pp. 1?9. 197 [67] Z. Feng and Y. Yang, ?Joint transport, routing and spectrum sharing optimization for wire- less networks with frequency-agile radios,? in Proc. IEEE INFOCOM?09, Rio de Janeiro, Brazil, Apr. 2009, pp. 1665?1673. [68] D. Palomar and M. Chiang, ?A tutorial on decomposition methods for network utility max- imization,? IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1439?1451, Aug. 2006. [69] D. P. Bertsekas, Nonlinear Programming, 2nd ed. Nashua, NH: Athena Scientific, 1999. [70] H. Mahmoud, T. Y?ucek, and H. Arslan, ?OFDM for cognitive radio: Merits and challenges,? IEEE Wireless Commun., vol. 16, no. 2, pp. 6?14, Apr. 2009. [71] F. Kelly, A. Maulloo, and D. Tan, ?Rate control in communication networks: shadow prices, proportional fairness and stability,? J. Operational Research Society, vol. 49, no. 3, pp. 237? 252, Mar. 1998. [72] Y. Hou, Y. Shi, and H. Sherali, ?Optimal base station selection for anycast routing in wireless sensor networks,? IEEE Transactions on Vehicular Technology, vol. 55, no. 3, pp. 813?821, May 2006. [73] O. Simeone, Y. Bar-Ness, and U. Spagnolini, ?Stable throughput of cognitive radios with and without relaying capability,? IEEE Trans. Commun., vol. 55, no. 12, pp. 2351?2360, Dec. 2007. [74] D. Tse and P. Viswanath, Fundamentals of Wireless Communication. Cambridge, UK: Cambridge University Press, 2005. [75] V. Cadambe and S. A. Jafar, ?Interference alignment and the degrees of freedom for the k user ntererence channel,? IEEE Trans. Inf. Theory, vol. 54, no. 8, pp. 3425?3441, May 2008. [76] L. E. Li, R. Alimi, D. Shen, H. Viswanathan, and Y. R. Yang, ?A general algorithm for interference alignment and cancellation in wireless networks,? in Proc. IEEE INFOCOM 2010, San Diego, CA, Mar. 2010. [77] G. Strang, Introduction to Linear Algebra, 4th ed. Wellesley, MA: Wellesley Cambridge Press, 2009. [78] T. Cover and A. Gamal, ?Capacity theorems for the relay channel,? IEEE Trans. on Info. Theory, vol. 25, no. 5, pp. 572?584, Sept. 1979. [79] A. Sendonaris, E. Erkip, and B. Aazhang, ?User cooperation diversity - Part I: System description,? IEEE Trans. Commun., vol. 51, no. 11, pp. 1927?1938, Nov. 2003. [80] ??, ?User cooperation diversity - Part II: Implementation aspects and performance analy- sis,? IEEE Trans. Commun., vol. 51, no. 11, pp. 1939?1948, Nov. 2003. [81] M. Khojastepour, A. Sabharwal, and B. Aazhang, ?On capacity of Gaussian ?cheap? relay channel,? in Proc. IEEE GLOBECOM?03, San Francisco, CA, Dec. 2003, pp. 1776?1780. 198 [82] Y. Zhao, R. Adve, and T. Lim, ?Improving amplify-and-forward relay networks: Optimal power allocation versus selection,? IEEE Trans. Wireless Commun., vol. 6, no. 8, pp. 3114? 3123, Aug. 2007. [83] A. Bletsas, A. Khisti, D. Reed, and A. Lippman, ?A simple cooperative diversity method based on network path selection,? IEEE J. Sel. Areas Commun., vol. 24, no. 3, pp. 659?672, Mar. 2006. [84] T. C.-Y. Ng and W. Yu, ?Joint optimization of relay strategies and resource allocations in cooperative cellular networks,? IEEE J. Sel. Areas Commun., vol. 25, no. 2, pp. 328?339, Feb. 2007. [85] J. Cai, X. Shen, J. Mark, and A. Alfa, ?Semi-distributed user relaying algorithm for amplify- and-forward wireless relay networks,? IEEE Trans. Wireless Commun., vol. 7, no. 4, pp. 1348?1357, Apr. 2008. [86] Y. Shi, S. Sharma, Y. Hou, and S. Kompella, ?Optimal relay assignment for cooperative communications,? in Proc. ACM MobiHoc?08, Hong Kong, P. R. China, May 2008, pp. 3?12. [87] L. Ding, T. Melodia, S. Batalama, and J. Matyjas, ?Distributed routing, relay selection, and spectrum allocation in cognitive and cooperative ad hoc networks,? in IEEE SECON?10, Boston, MA, June 2010, pp. 1?9. [88] L. Ding, S. Pudlewski, T. Melodia, S. Batalama, J. Matyjas, and M. Medley, ?Distributed spectrum sharing for video streaming in cognitive radio ad hoc networks,? in Intl. Workshop on Cross-layer Design in Wireless Mobile Ad Hoc Networks, Niagara Falls, Canada, Sept. 2009, pp. 1?13. [89] S. Katti, S. Gollakota, and D. Katabi, ?Embracing wireless interference: Analog network coding,? in Proc. ACM SIGCOMM?07, Kyoto, Japan, Aug. 2007, pp. 397?408. [90] S. Gollakota, S. David, and D. Katabi, ?Interference alignment and cancellation,? in Proc. ACM SIGCOMM?09, Barcelona, Spain, Aug. 2009, pp. 159?170. [91] I. K. Son and S. Mao, ?Design and optimization of a tiered wireless access network,? in Proc. IEEE INFOCOM 2010, San Diego, CA, Mar. 2010, pp. 1?9. [92] R. Kim, J. S. Kwak, and K. Etemad, ?WiMAX femtocell: requirements, challenges, and solutions,? IEEE Commun. Mag., vol. 47, no. 9, pp. 84?91, Sept. 2009. [93] I. Guvenc, S. Saunders, O. Oyman, H. Claussen, and A. Gatherer, ?Femtocell net- works,? EURASIP J. Wireless Comm. and Networking, 2010, article ID 367878, 2 pages, doi:10.1155/2010/367878. [94] A. Goldsmith, Wireless Communications. Cambridge, UK: Cambridge University Press, 2006. 199 [95] L. Li, R. Alimi, R. Ramjee, H. Viswanathan, and Y. R. Yang, ?muNet: Harnessing multiuser capacity in wireless mesh networks,? in Proc. IEEE INFOCOM?09 Mini Symp., Rio de Janeiro, Brazil, Apr. 2009, pp. 2876?2880. [96] V. Chandrasekhar, J. G. Andrews, T. Muharemovic, Z. Shen, and A. Gatherer, ?Power con- trol in two-tier femtocell networks,? IEEE Trans. Wireless Commun., vol. 8, no. 8, pp. 4316? 4328, Aug. 2009. [97] F.-S. Chu and K.-C. Chen, ?Mitigation of macro-femto co-channel interference by spatial channel separation,? in Proc. IEEE VTC-Spring?11, Budapest, Hungary, May 2011, pp. 1?5. [98] S. Rangan, ?Femto-macro cellular interference control with subband scheduling and inter- ference cancelation,? in Proc. IEEE GLOBECOM?10 Workshops, Miami, FL, Dec. 2010, pp. 695?700. [99] Z. Bharucha, H. Haas, G. Auer, and I. Cosovic, ?Femto-cell resource partitioning,? in Proc. IEEE GLOBECOM Workshops, Honolulu, HI, Dec. 2009, pp. 1?6. [100] R. Madan, A. Sampath, A. Khandekar, J. Borran, and N. Bhushan, ?Distributed interference management and scheduling in LTE-A femto networks,? in Proc. IEEE GLOBECOM?10, Miami, FL, Dec. 2010, pp. 1?5. [101] S.-M. Cheng, S.-Y. Lien, F.-S. Chu, and K.-C. Chen, ?On exploiting cognitive radio to mitigate interference in macro/femto heterogeneous networks,? IEEE Wireless Commun. Mag., vol. 18, no. 3, pp. 40?47, 2011. [102] S. Kaimaletu, R. Krishnan, S. Kalyani, N. Akhtar, and B. Ramamurthi, ?Cognitive inter- ference management in heterogeneous femto-macro cell networks,? in Proc. IEEE ICC?11, Kyoto, Japan, June 2011, pp. 1?6. [103] S. Sen, N. Santhapuri, R. R. Choudhury, and S. Nelakuditi, ?Successive interference cancel- lation: A back-of-the-envelope perspective,? in Proc. ACM Hotnets?10, Monterey, CA, Oct. 2010, pp. 1?6. [104] C. A. S. Jean and B. Jabbari, ?On game-theoretic power control under successive inter- ference cancellation,? IEEE Trans. Wireless Commun., vol. 8, no. 4, pp. 1655?1657, Apr. 2009. [105] C. S. Park and K. B. Lee, ?Transmit power allocation for successive interference cancella- tion in multicode MIMO systems,? IEEE Trans. Commun., vol. 56, no. 12, pp. 2200?2213, Dec. 2008. [106] N. Benvenuto, G. Carnevale, and S. Tomasin, ?Joint power control and receiver optimization of CDMA transceivers using successive interference cancellation,? IEEE Trans. Commun., vol. 55, no. 3, pp. 563?573, Mar. 2007. [107] A. Agrawal, J. G. Andrews, J. M. Cioffi, and T. Meng, ?Iterative power control for imperfect successive interference cancellation,? IEEE Trans. Wireless Commun., vol. 4, no. 3, pp. 878? 884, May 2005. 200 [108] J. G. Andrews and T. H. Meng, ?Optimum power control for successive interference can- cellation with imperfect channel estimation,? IEEE Trans. Wireless Commun., vol. 2, no. 2, pp. 375?383, Mar. 2003. [109] U. Ewaldsson, ?Cut your network?s electricity bill and carbon footprint,? Global Telecoms Business, Feb. 28, 2010. [110] T. Rappaport, Wireless Communications: Principles & Practice, 2nd ed. Indianapolis, IN: Prentice Hall PTR, 2001. [111] Q. Zhang and S. Kassam, ?Finite-state Markov model for Rayleigh fading channels,? IEEE Trans. Commun., vol. 47, no. 11, pp. 1688?1692, Nov. 1999. [112] Z. Wang, L. Lu, and A. C. Bovik, ?Video quality assessment using structural distortion measurement,? Signal Processing: Image Commun., no. 2, pp. 121?132, Feb. 2004. 201 Appendices Publications from This Dissertation Work Book Chapter 1. Donglin Hu and Shiwen Mao, ?Video over cognitive radio networks: when compression meets the radios,? in Advanced Video Communications over Wireless Networks, C. Zhu and Y. Li (editors), New York, NY: CRC Press, in press. (39 pages) Journal Publications 1. Donglin Hu and Shiwen Mao, ?A Successive Interference Cancellation approach to multicast in femtocell networks,? IEEE Transactions on Wireless Communications, under submission. 2. Donglin Hu and Shiwen Mao, ?Cooperative relay with interference alignment for video streaming in cognitive radio networks,? IEEE Journal on Selected Areas in Communications - Cognitive Radio Series, vol.30, no.11, Nov.2012, under review. (11 pages) 3. Donglin Hu and Shiwen Mao, ?On co-channel and adjacent channel interference mitigation in cognitive radio networks,? Elsevier Ad Hoc Networks Journal, under review. (18 pages) 4. Donglin Hu and Shiwen Mao, ?On cooperative relay in cognitive radio networks,? ICST Transactions on Mobile Communications and Applications, in press. (9 pages) 5. Donglin Hu and Shiwen Mao, ?A sensing error aware medium access control protocol for cognitive radio networks,? ICST Transactions on Mobile Communications and Applications, vol.1, no.2, 2012, in press. (10 pages) 202 6. Donglin Hu and Shiwen Mao, ?On medium grain scalable video streaming over femtocell cognitive radio networks,? IEEE Journal on Selected Areas in Communications, Special Issue on Femtocell Networks, vol.30, no.4, Apr. 2012, in press. (11 pages) 7. Donglin Hu and Shiwen Mao, ?Streaming scalable videos over multi-hop cognitive radio networks,? IEEE Transactions on Wireless Communications, vol.9, no.11, pp.3501?3511, Nov. 2010. 8. Shiwen Mao and Donglin Hu, ?Video over cognitive radio networks: when compression meets the radios,? invited paper, E-Letter of Multimedia Communications Technical Com- mittee (MMTC), IEEE Communications Society, Special Issue on Advances in Network- Adaptive Multimedia Communications, vol.5, no. 6, pp.14?16, Nov. 2010. 9. Donglin Hu, Shiwen Mao, Y. Thomas Hou, and Jeffrey H. Reed, ?Fine grained scalability video multicast in cognitive radio networks,? IEEE Journal on Selected Areas in Commu- nications, Special Issue on Wireless Video Transmission, vol.28, no.3, pp.334?344, Apr. 2010. Conference Publications 1. Donglin Hu, Shiwen Mao, and Nedret Billor, ?On compressed sensing in wireless sensor net- works,? under review for IEEE Global Communications Conference (GLOBECOM) 2012, Anaheim, CA, Nov. 2012. (6 pages) 2. Donglin Hu and Shiwen Mao, ?Cooperative relay with interference alignment for video over cognitive radio networks,? in Proc. IEEE IEEE International Conference on Computer Communications (INFOCOM) 2012, pp.1?9, Orlando, FL, Mar. 2012. 3. Donglin Hu and Shiwen Mao, ?Multicast in femtocell networks: a successive interference cancellation approach,? in Proc. IEEE Global Communications Conference (GLOBECOM) 2011, Houston, TX, pp.1?6, Dec. 2011. 203 4. Donglin Hu and Shiwen Mao, ?Co-channel and adjacent channel interference mitigation in cognitive radio networks,? in Proc. IEEE Military Communications Conference (MILCOM) 2011, Baltimore, MD, pp.1?6, Nov. 2011. 5. Donglin Hu and Shiwen Mao, ?Resource allocation for medium grain scalable videos over femtocell cognitive radio networks,? in Proc. The 31st IEEE International Conference on Distributed Computing Systems (ICDCS) 2011, Minneapolis, MN, pp.258-267, June 2011. 6. Donglin Hu and Shiwen Mao ?Cooperative relay in cognitive radio networks: decode-and- forward or amplify-and-forward?? in Proc. IEEE Global Communications Conference (GLOBECOM) 2010, Miami, FL, pp.1?5, Dec. 2010. 7. Donglin Hu and Shiwen Mao, ?Design and analysis of a sensing error-aware MAC protocol for cognitive radio networks,? in Proc. IEEE Global Communications Conference (GLOBE- COM) 2009, Honolulu, HI, pp.1?6, Nov./Dec. 2009. 8. Donglin Hu, Shiwen Mao, and Jeffrey H. Reed, ?On video multicast in cognitive radio net- works,? in Proc. IEEE International Conference on Computer Communications (INFO- COM) 2009, Rio de Janeiro, Brazil, pp.2222?2230, Apr. 2009. 204