Resource Allocation and Optimization for Multiple-User Legacy and Cognitive Radio Systems by Tariq Al-Khasib M.A.Sc., The University of British Columbia, 2004 B.Sc., Jordan University of Science and Technology, 2001 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in The Faculty of Graduate Studies (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) May 2010 c Tariq Al-Khasib 2010 Abstract The rapid transition towards user mobility and the increased demand it carries for bandwidth and data rates has been the driver for significant advancements in research and development in wireless communications in the last decade. These advancements materialized through enhancements to the well established legacy systems and conceptual innovations with great potential. Not far from that, in this thesis, we consider a diverse set of tools and techniques that facilitate efficient utilization of system resources in legacy and Cognitive Radio (CR) systems without hindering the integrity and robustness of the system design. First, we introduce the concept of service differentiation at the receiver, which can be realized by means of a new multiple-user Multiple-Input Multiple-Output (MIMO) detector based on the well known V-BLAST algorithm. We devise the DiffSIC algorithm that is able to differentiate between users in service based on their priorities or imminent needs. DiffSIC achieves its goal by determining the optimal order of detection, at the receiver, that best fits the users’ profiles. Second, we propose a channel allocation technique for the transmitter of MIMO multipleuser access systems which enhances the system capacity without aggravating the complexity of the receiver. In particular, we allow users to share resources to take full advantage of the degrees of freedom available in the system. Moreover, we show how to realize these ii Abstract enhancements using simple, yet powerful, modulation and detection techniques. Next, we propose new robust system designs for MIMO CR systems under the inevitable reality of imperfect channel state information at the CR transmitter. We apply innovative tools from optimization theory to efficiently and effectively solve design problems that involve multiple secondary users operating over multiple frequency carriers. At last, we observe the effect of primary users’ activity on the stability of, and quality of service provided by, CR systems sharing the same frequency resource with the primary system. We propose admission control mechanisms to limit the effect of primary users’ activity on the frequency of system outages at the CR system. We also devise pragmatic eviction control measures to overcome periods of system infeasibility with a minimally disruptive approach. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x List of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiv 1 Introduction and Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 iv Table of Contents 1.2.1 Layered vs. Cross Layered Approach . . . . . . . . . . . . . . . . . . 2 1.2.2 Multiple-Input Multiple-Output (MIMO) . . . . . . . . . . . . . . . 3 1.2.3 Cognitive Radio Systems . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.4 Orthogonal Frequency Division Multiplexing (OFDM) . . . . . . . . 8 Thesis Contributions and Organization . . . . . . . . . . . . . . . . . . . . . 9 2 DiffSIC: Optimal SIC Detection with Service Differentiation . . . . . . . 12 1.3 2.1 Introduction 2.2 System Model 2.3 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 DiffSIC Ordering Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.1 SER Analysis for ZF-SIC Detectors . . . . . . . . . . . . . . . . . . 19 2.3.2 DiffSIC Ordering Algorithm . . . . . . . . . . . . . . . . . . . . . . . 21 2.3.3 Multiple Detection Chains . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3.4 Extension to MMSE-SIC . . . . . . . . . . . . . . . . . . . . . . . . 23 Reduced Complexity Approximations for DiffSIC . . . . . . . . . . . . . . . 26 2.4.1 Low-Complexity SER Approximation . . . . . . . . . . . . . . . . . 26 2.4.2 Approximation for Selecting Order of Detection . . . . . . . . . . . . 27 2.5 Performance Under Channel Estimation Errors . . . . . . . . . . . . . . . . 31 2.6 Performance Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3 Uplink Channel Allocation Strategies for Multiple-User MIMO Systems 47 3.1 Introduction 3.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 v Table of Contents 3.3 Capacity Analysis 3.4 Bit Error Rate (BER) Results . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4 Designs for MIMO Cognitive Radio Systems with Imperfect CSI . . . . 61 4.1 Introduction 4.2 System Model 4.3 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2.1 Single SU, Single-Carrier CR Systems . . . . . . . . . . . . . . . . . 63 4.2.2 Single SU, Multiple-Carrier CR Systems . . . . . . . . . . . . . . . . 65 4.2.3 Multiple SUs, Multiple-Carrier CR Systems . . . . . . . . . . . . . . 66 4.2.4 Channel Uncertainty Model . . . . . . . . . . . . . . . . . . . . . . . 67 Single SU CR System: Single-Carrier Case . . . . . . . . . . . . . . . . . . . 69 4.3.1 Capacity Maximization Subject to a Power Constraint . . . . . . . . 69 4.3.2 Power and Interference Minimization Subject to Rate Constraint . . 71 . . . . . . . . . . . . . . . . . 73 4.4.1 Total Interference Constraint . . . . . . . . . . . . . . . . . . . . . . 73 4.4.2 Per-carrier Interference Constraints . . . . . . . . . . . . . . . . . . . 75 Single SU CR System: Multiple-Carrier Case 4.5 Multiple SUs CR System: Multiple-Carrier Case . . . . . . . . . . . . . . . 77 4.6 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.6.1 Single SU CR System 81 4.6.2 Multiple SUs CR System 4.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 vi Table of Contents 5 Admission and Eviction Control in OFDMA Cognitive Radio Systems 5.1 Introduction 5.2 System Model 5.3 5.4 5.5 5.6 92 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.2.1 Signaling Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.2.2 PU Activity Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.2.3 SU Arrival Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Admission Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.3.1 Fixed Power Threshold . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.3.2 Fixed Carrier Release 5.3.3 Predictive Carrier Release . . . . . . . . . . . . . . . . . . . . . . . . 103 . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Resource Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.4.1 Optimal User Removal (OptRem) . . . . . . . . . . . . . . . . . . . 110 5.4.2 Random User Removal (RandRem) 5.4.3 User Removal Based on Lagrange Multipliers (LagRem) . . . . . . . . . . . . . . . . . . 111 . . . . . . . 112 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.5.1 Performance of User Removal Algorithms . . . . . . . . . . . . . . . 113 5.5.2 Performance of Admission Control Algorithms . . . . . . . . . . . . 117 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6.1 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 vii Table of Contents A Derivation of Error Probability Expressions for ZF-SIC PAM Signals B Proof of Theorem 4.1 . 146 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 C List of Publications and Submissions . . . . . . . . . . . . . . . . . . . . . . 151 viii List of Tables 3.1 Channel allocation strategies . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2 Simulation setups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.1 p1 p2 from Algorithm 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 ix List of Figures 2.1 Block diagram of the equivalent real-valued transmission system using a SIC detector. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 15 Comparison of analytical and simulated SER performance results for one fixed channel realization. 4-QAM signal constellation and ZF-SIC detector using fixed order of detection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 34 Comparison of analytical and simulated SER performance results for one fixed channel realization. 16-QAM signal constellation and ZF-SIC detector using fixed order of detection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 35 Comparison of the efficacy of reduced complexity SER approximations. SER approximation method from Algorithm 2.1 (Method 1) and SER approximation by considering error sequences with errors at lower layers first (Method 2). SER for user 4 is shown. The total number of error sequences is 36 = 729. 4-QAM signal constellation and ZF-SIC detector. . . . . . . . . . . . . . . . 2.5 36 SER performance comparison between DiffSIC and V-BLAST for one fixed channel realization. User priorities are c = [0, 0, 0, 1]. 4-QAM signal constellation and ZF-SIC detector. . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 x List of Figures 2.6 Average SER performance comparison between DiffSIC and V-BLAST. User priorities are c = [0, 0, 0, 1]. 4-QAM signal constellation and ZF-SIC detector. 2.7 38 Average SER performance comparison between DiffSIC and V-BLAST. Mt = Mr = 4. User priorities are c = [0, 0, 0, 1]. 4-QAM signal constellation and MMSE-SIC detector. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 40 Average SNR gain for high priority user with DiffSIC over V-BLAST when SER approximation according to Algorithm 2.1 is used. User priorities are c = [0, 0, 0, 1]. 4-QAM signal constellation and ZF-SIC detector. . . . . . . . 2.9 41 Average SNR gain for high priority user with DiffSIC over V-BLAST when a reduced number of orders Nmax is used according to Algorithm 2.2 vs sensitivity parameter S. User priorities are c = [0, 0, 0, 1]. 4-QAM signal constellation and ZF-SIC detector. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.10 Average SNR gain for high priority user with DiffSIC over V-BLAST when a reduced number of orders Nmax is used according to Algorithm 2.2 vs sensitivity parameter S. User priorities are c = [0, 0.25, 0.5, 1]. 4-QAM signal constellation and ZF-SIC detector. . . . . . . . . . . . . . . . . . . . . . . . 43 2.11 Average SNR gain for high priority user with DiffSIC over V-BLAST when SER approximation according to Algorithm 2.1 and a reduced number of orders Nmax is used according to Algorithm 2.2 (S = 0.999). 4-QAM signal constellation and ZF-SIC detector. . . . . . . . . . . . . . . . . . . . . . . . 44 xi List of Figures 2.12 SER performance of DiffSIC and V-BLAST for perfect (P = ∞) and imperfect (P = 5) channel estimation (SNR for imperfect channel estimation is shifted for proper comparison). One fixed channel realization with user priorities of c = [0, 0, 0, 1], 16-QAM signal constellation and ZF-SIC detector. . . . . . . . 3.1 Channel allocation. (a) 2 users using 2 subbands, (b) Allocation Strategy #1 (c) Allocation Strategy #2 (d) Allocation Strategy #3. . . . . . . . . . . . . 3.2 45 50 Block diagram of the equivalent transmission system with linear and SIC detectors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3 Ergodic capacity for the 3 different allocation strategies. . . . . . . . . . . . 55 3.4 Outage probability for the 3 different allocation strategies, SNR = 10, 15 and 20 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 BER performance for different allocation strategies using WL-MMSE-SIC detection with 2 receive antennas. . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 58 BER performance for different allocation strategies using WL-MMSE-SIC detection with one receive antenna. . . . . . . . . . . . . . . . . . . . . . . . . 3.7 56 59 Average BER performance of all users for the three allocation strategies using WL-MMSE-SIC detection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.1 Single SU, single-carrier cognitive radio system with L PUs. . . . . . . . . . 64 4.2 Multiple SUs, multiple-carrier cognitive radio system with L PUs and N carriers. 67 xii List of Figures 4.3 Average of the maximum link capacity of a single-carrier, single SU CR system in the presence of a single PU versus the maximum allowable interference at the PU for different values of ǫ. Maximum allowable power at the SU transmitter is P = 20 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 81 Average transmitted power Tr(Q) from the SU when optimizing for the link capacity of a single-carrier, single SU CR system in the presence of a single PU versus the maximum allowable interference at the PU for different values of ǫ. Maximum allowable power at the SU transmitter is P = 20 dB. . . . . 4.5 83 Average of the relative interference threshold violation ((Tr(GQGH )−I)+ /I) versus the level of uncertainty associated with the CSI that was not taken into account in the design process. A single-carrier, single SU, CR system is considered in the presence of a single PU with a maximum allowable power at the SU transmitter of P = 20 dB. . . . . . . . . . . . . . . . . . . . . . . 4.6 84 Average of the maximum sum rate of a multiple-carrier (N = 8), single SU CR system in the presence of a single PU versus the maximum allowable interference I at the PU for different values of ǫ. Maximum allowable power at the SU transmitter is P = 20 dB. . . . . . . . . . . . . . . . . . . . . . . . 4.7 Average of the total transmitted power n 85 Tr(Q) from the SU when optimiz- ing for the link capacity of a multiple-carrier (N = 8), single SU CR system in the presence of a single PU versus the maximum allowable interference I at the PU for different values of ǫ. Maximum allowable power at the SU transmitter is P = 20 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 xiii List of Figures 4.8 Average of the maximum sum rate of a multiple-carrier (N = 8), single SU CR system versus the number of PUs for a fixed maximum allowable interference I = −10 dB at each PU for different values of ǫ. Maximum allowable power at the SU transmitter is P = 20 dB. . . . . . . . . . . . . . . . . . . . . . . . 4.9 87 Outage probability of the robust power minimization for a multiple-carrier (N = 8), single SU CR system in the presence of a single PU versus the maximum allowable interference I at the PU for different values of ǫ. The target sum rate is 10 bps/Hz. . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.10 Average minimum transmit power from the SU of a multiple-carrier (N = 8), single SU CR system in the presence of a single PU versus the maximum allowable interference I at the PU for different values of ǫ. The target sum rate is 10 bps/Hz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.11 Average of the maximum sum rate obtained from solving the primal and dual optimization problems of a multiple-carrier (N = 4), Multiple SUs (K = 2) CR system in the presence of a single PU versus the maximum allowable interference I at the PU for different values of ǫ. Maximum allowable power at each SU transmitter is P = 17 dB. . . . . . . . . . . . . . . . . . . . . . . 90 5.1 Multiple-user downlink cognitive radio system. . . . . . . . . . . . . . . . . . 96 5.2 Average of the maximum number of SUs, among 5 SUs, the system can maintain while achieving a feasible resource allocation given a sum power constraint: Comparing three different user removal algorithms. . . . . . . . . . . 114 xiv List of Figures 5.3 Average RT SU drop rate versus a range of RT SU arrival rates (λRT ): Comparing three different user removal algorithms. . . . . . . . . . . . . . . . . . 116 5.4 Average RT SU drop rate versus a range of RT SU arrival rates (λRT ) when an RBZ based on fixed power threshold is installed. . . . . . . . . . . . . . . 118 5.5 Average RT SU drop rate versus a range of RT SU arrival rates (λRT ) when an RBZ based on fixed carrier release is installed. . . . . . . . . . . . . . . . 119 5.6 Average RT SU blocking rate versus size of the installed RBZ that is based on the fixed carrier release algorithm. . . . . . . . . . . . . . . . . . . . . . . 120 5.7 Average number of “good” RT SUs admitted to the system at any given time slot versus size of the installed RBZ that is based on the fixed carrier release algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.8 Average RT SU drop rate versus a range of RT SU arrival rates (λRT ) when an RBZ based on predictive carrier release is installed. . . . . . . . . . . . . 123 5.9 Average RT SU drop rate versus the required dropping risk probability (prisk ) for different levels of RT SU arrival rates (λRT ) when an RBZ based on predictive carrier release is installed. . . . . . . . . . . . . . . . . . . . . . . . . 124 A.1 Effect of signal bias on error probability of PAM signals. . . . . . . . . . . . 147 xv List of Algorithms 2.1 Approximate SER calculation . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Determine a reduced set of detection orders for DiffSIC . . . . . . . . . . . . 30 5.1 Find expected carrier drop . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.2 Optimal user removal (OptRem) . . . . . . . . . . . . . . . . . . . . . . . . . 111 xvi List of Abbreviations AWGN Additive White Gaussian Noise BC Broadcast Channel BE Best Effort BER Bit Error Rate BS Base Station CDMA Code Division Multiple Access CP Cyclic Prefix CR Cognitive Radio CSDPS Channel State Dependent Packet Scheduling CSI Channel State Information DFT Discrete Fourier Transform DiffSIC Differentiated Successive Interference Cancellation DPC Dirty Paper Coding DSP Digital Signal Processor EGC Equal Gain Combining FDMA Frequency Division Multiple Access xvii List of Abbreviations GI Guard Interval ICI Inter-Carrier Interference IP Internet Protocol ISI Inter-Symbol Interference LagRem User Removal Based on Lagrange Multipliers LMI Linear Matrix Inequality MAC Medium Access Control MC Markov Chain MCM Multiple-Carrier Modulation MF Matched Filtering MIMO Multiple-Input Multiple-Output ML Maximum Likelihood MLD Maximum Likelihood Detection MMSE Minimum Mean-Square Error MRC Maximal Ratio Combining MUD Multiple-User Detection OFDM Orthogonal Frequency Division Multiplexing OFDMA Orthogonal Frequency Division Multiple Access OptRem Optimal User Removal PAM Pulse Amplitude Modulation xviii List of Abbreviations PER Packet Error Rate PHY Physical PIC Parallel Interference Cancellation PU Primary User QAM Quadrature Amplitude Modulation QoS Quality of Service RandRem Random User Removal RBZ Resource Buffer Zone RF Radio Frequency RT Real Time SC Selection Combining SDMA Space Division Multiple Access SDP Semi-Definite Programming SDR Software Defined Radio SER Symbol Error Rate SIC Successive Interference Cancellation SIMO Single Input Multiple Output SNR Signal-to-Noise power Ratio STBC Space Time Block Codes STTC Space Time Trellis Codes xix List of Abbreviations SwC Switched Combining TCP Transmission Control Protocol TDD Time Division Duplex TDMA Time Division Multiple Access V-BLAST Vertical Bell Laboratory Layered Space Time WL Widely Linear ZF Zero Forcing xx Notation We use bold upper case and lower case letters for matrices and vectors, respectively. [·]T transpose [·]H Hermitian transpose [·]−1 matrix inversion · 2 ℓ2 -norm of a vector In n × n identity matrix ℜ(·) real part ℑ(·) imaginary part Tr(·) trace of a matrix vec(·) converts matrix into column vector ⊗ Kronecker product of two matrices log det(·) base 2 logarithm of the determinant of a matrix A≥0 matrix A is positive semidefinite Pr(·) probability of some event E(·) expectation RN space of real vectors of dimension N RN ×N space of real matrices of dimension N × N xxi Notation CN space of complex vectors of dimension N CN ×N space of complex matrices of dimension N × N xxii Acknowledgements All praise and thanks are due to almighty God, the source of all good and guidance. I would like to express my sincere gratitude and appreciation to my supervisor Dr. Lutz Lampe for his endless support, expert guidance and great patience. Without him this thesis could not be produced in its present form. I would also like to express my appreciation and gratitude to my co-supervisor Dr. Hussein Alnuweiri for his support and valuable advice. I owe my deepest appreciation and regards to my parents Jamal and Sameera. Their continuous love, support, and prayers made this work possible. I am also indebted to my lovely wife Ahlam whose constant love, persistent encouragement, and endless patience kept me going against the hardships and stressful moments during the years of my PhD. I would also like to thank the great brothers I made during my stay in Vancouver. I would like to specifically thank Aiman Erbad, Jamal Abdelwahid, Dr. Tamer Khattab, Dr. Amr Salem, Dr. Khalid Ibrahim, Dr. Abubaker Abusbeaa, Dr. Mohammed Senousy, Dr. Ali Al Shidhani, Dr. Wajeeh Moughrabiah, Uthman Al-Saiari, Abdel Hamid Ismail, Zaman Mollah, Ghassan Alsharif, Haitham Eissa, Dr. Aissa Ikhlef, Dr. Mohammad Gadala, Dr. Ismail Laher, Dr. Ahmad Ashour, Yehya Imam, Samer Al-Kiswany, Mohammad Khouj, and Walid Abdulrahman for all the support and the wonderful times we spent together. xxiii Dedication Dedicated with love To My Parents: JAMAL and SAMEERA My Wife : AHLAM My Beautiful Daughter : SARA xxiv Chapter 1 Introduction and Overview 1.1 Motivation Recognizing the inevitable evolution towards wireless ubiquity, we aim through this research effort to develop and evaluate viable system alternatives and communication techniques for realizing next-generation wireless access and wireless networking devices. Such techniques and devices may provide a much improved alternative to current wireless communication standards in terms of data rate, spectral and power efficiency, and quality-of-service. Although wireless communication theory provides ample choice of modulation, coding and detection techniques for implementing robust and sophisticated wireless systems, advancements are rapidly and constantly materializing in an effort to fulfill the user needs. The key features that characterize successful solutions for future wireless data networks are: Higher data rates: to match and replace their wired counterparts, wireless access points must be able to transmit, receive, and switch data at (multi) gigabit-per-second rates. Moreover, bandwidth availability must remain consistent under diverse channel conditions. Service differentiation and Quality of Service (QoS) guarantees: future wireless networks should be able to provide quantitative service guarantees to traffic flows, and must be able to combat interference and reject traffic from undesirable or intruding traffic sources. 1 Chapter 1. Introduction and Overview Adaptability and robustness: future wireless data networks should be able to utilize the available resources and exercise all degrees of freedom the system might offer efficiently. This requires the system to adapt to changing conditions and parameters without giving up on the versatility and robustness of the system design. The above arguments provide the main motivation for this research which addresses several key challenges and produces early results on the shape and capability of future wireless communication systems. 1.2 Background In this section, we briefly discuss key concepts that are generally relevant to most of the topics discussed in this thesis. More specific background topics and literature reviews that are of special importance to individual chapters are discussed separately within chapters’ introductions. 1.2.1 Layered vs. Cross Layered Approach In the framework of layered architecture design, modularity and simplicity were the main drivers. Different functionalities were divided among several modules, called layers, each of which is responsible for a set of tasks that are static and predetermined. Layers were able to share information with neighboring layers through static and standard channels. While the layered approach proved to be efficient for wired data communication networks, more problems started to arise as data communication networks migrated towards the wireless domain. Discovering these problems, researchers tried to propose solutions within the layered 2 Chapter 1. Introduction and Overview framework, and they succeeded to do so by introducing several packet-based wireless network standards such as 802.11 [1]. The availability of more processing power and the introduction of applications that require high data rates pushed for more research into optimizing network parameters to obtain higher rates and increase transmission reliability. Srivastava et al. [2] identified the reasons why designers tend to violate the layered architecture when wireless links are part of the communication system. The first of these reasons stems from the unique problems identified by wireless links, such as the famous problem of the Transmission Control Protocol (TCP) considering a packet loss due to error as an indicator to network congestion [3, 4]. Secondly, the opportunistic nature of communication over wireless links due to the fluctuating quality of the medium. Lastly, the new modalities of communications offered by wireless links. Space utilization through Multiple-Input Multiple-Output (MIMO) and the broadcast nature of the medium are examples of these modalities. Srivastava et al. [2] also identified the different cross-layer frameworks that people tend to use in their proposals. Whether it was direct communication between different layers or a shared database that is accessible by all layers, these frameworks maintained the layered manifestation of the reference architecture, and at the same time have overcome the isolating and static nature of modulus design. 1.2.2 Multiple-Input Multiple-Output (MIMO) Wireless MIMO techniques have been widely recognized as one of the means for higher data rates and efficient spectrum utilization in current and future wireless communication 3 Chapter 1. Introduction and Overview standards [5–7]. MIMO communications provide additional spatial degrees of freedom that can result in several orders-of-magnitude increase in data rate and significant decrease in interference in point-to-point, point-to-multipoint and multipoint-to-point transmission. In MIMO systems, one or both of the transmitter and receiver are equipped with multiple antennas. MIMO takes advantage of the multiple-path propagation feature of the wireless medium through which spatial degrees of freedom emerge when channels between different transmit and receive antennas are sufficiently uncorrelated. These degrees of freedom can be either utilized to enhance the quality of the signal at the receiver, in terms of Signal-to-Noise power Ratio (SNR) or Bit Error Rate (BER), or to increase the effective data rate to levels that were not conceivable before. These enhancements can materialize by means of spatial precoding, spatial multiplexing, and/or spatial diversity coding [8]. In spatial precoding, a.k.a. spatial beamforming, the channel knowledge at the transmitter is utilized to focus the transmission energy in the direction of the intended receiver [9, 10]. This enhances the signal quality at the intended receiver and, at the same time, reduces the amount of interference caused to neighboring devices communicating over the same frequency band. However, this requires the availability of Channel State Information (CSI) at the transmitter, which is only feasible if Time Division Duplex (TDD) was utilized for uplink and downlink communications or a feedback channel was available to carry accurate CSI to the transmitter in a timely manner. Spatial multiplexing, on the other hand, can significantly increase the data rate by allowing the transmitter to simultaneously send independent streams of data on different antennas [11, 12]. These streams get separated at the receiver and data corresponding to each stream get successfully decoded if the spatial signatures of the transmit antennas were 4 Chapter 1. Introduction and Overview sufficiently different at the receiver. Optimal algorithms based on Maximum Likelihood Detection (MLD) are available in the literature. Other sub-optimal and less complex, linear and non-linear, alternatives can also be exploited. Assuming that Mt and Mr are the number of transmit and receive antennas, respectively, it was shown in [13] and [14] how the capacity of a MIMO wireless link grows linearly with min(Mt , Mr ). Finally, spatial diversity when implemented at the transmitter, receiver or both, can help enhance the quality of the signal at the receiver. Like any other form of diversity, spatial diversity at the transmitter can be accomplished by allowing copies of the same data set, usually coded, to be transmitted in parallel such that the effective channel quality can be enhanced. Famous examples of transmit diversity techniques include the early work by Tarokh et al. [15] in which Space Time Trellis Codes (STTC) were utilized at the transmitter along with a multidimensional Viterbi decoder at the receiver to achieve diversity as well as coding gains. Space Time Block Codes (STBC), introduced by Alamouti [16] and later by Tarokh et al. [17], simplify the process of detection at the receiver while maintaining the diversity gains achieved by STTC [18]. Similarly, having multiple antennas at the receiver reduces the chance of system outages when the channels associated with different antennas are sufficiently uncorrelated. Techniques such as Switched Combining (SwC), Selection Combining (SC), Equal Gain Combining (EGC) , and Maximal Ratio Combining (MRC) can be used to take advantage of this diversity [19, 20]. Spatial diversity can be best utilized when multiple users are present in the system. In multiple-user systems, large spatial separation between users is inherently leading to less correlation between their channels at the receiver [21]. This luxury of space might not be available between antennas of a MIMO device especially at the user terminal. Similar to 5 Chapter 1. Introduction and Overview legacy multiple user access techniques like Time Division Multiple Access (TDMA) and Frequency Division Multiple Access (FDMA), Space Division Multiple Access (SDMA) can utilize the spatial degrees of freedom to significantly increase the system capacity. On the uplink side, usually referred to as the multiple access channel, multiple antennas at the Base Station (BS) can be used to separate the signals from different users in a manner similar to that of detecting different stream from different antennas in the single user case. The capacity of the system is a K-dimensional region, K being the number of users, that represents the feasible set of rates that users can achieve simultaneously [21–23]. The downlink side, usually referred to as the Broadcast Channel (BC), is more complicated since there is, usually, no cooperation between users at the receiving side. Therefore, precoding techniques, like the capacity achieving Dirty Paper Coding (DPC) [24] or other liner and non-linear alternatives [25–29], should be used. As was mentioned earlier, precoding at the transmitter requires the presence of instantaneous CSI that can only be suboptimally acquired due to estimation and quantization errors. 1.2.3 Cognitive Radio Systems As more services migrate towards the wireless domain to support user mobility, the need for more spectrum is higher than ever. That is why, dynamic spectrum allocation, a.k.a. Cognitive Radio (CR), has received a growing attention from the research community in the last few years in an effort to solve the scarcity problem of the Radio Frequency (RF) resource. CR solutions rely on the well established fact that the allocated frequency spectrum is highly underutilized [30–32]. Thus, a CR system, consisting of one or more Secondary Users (SUs), can be allowed to operate within a pre-assigned spectrum band as long as it guarantees no 6 Chapter 1. Introduction and Overview harmful disturbance to the operations by the spectrum owners, usually referred to as the Primary Users (PUs). This can be achieved by either fully prohibiting any transmission from SUs in the presence of any PU activity, or by limiting the transmission power at the SU transmitter such that the interference generated at the PU receiver does not exceed a predetermined level known as the interference temperature [33]. Realization of any viable CR system faces some major challenges that need to be addressed in current and future research efforts. The biggest challenge is manifested in the need for intelligent algorithms for sensing and prediction of traffic by PUs to identify spectrum holes that represent a transmission opportunity for SUs [34, 35]. This sensing mechanism can be extended to include channel estimation of the SU to PU link to effectively design the SU transmitter such that no harmful interference is caused at the PU receiver [36, 37]. Another equally important challenge is in the need for state of the art system designs that can take full advantage of the discovered resource without affecting the operations of the primary system in any harmful way. The ongoing work on the first IEEE CR standard, Wireless Regional Area Networks (WRAN) 802.22 [38, 39], is a bold attempt towards overcoming some of these challenges. In 802.22, license-exempt devices are allowed to communicate over the licensed TV broadcast band on a non-interfering basis. However, the rather simple and almost static nature of TV broadcast channels keeps the door open for innovative ways to addressing the above challenges in more complicated and dynamic environments. 7 Chapter 1. Introduction and Overview 1.2.4 Orthogonal Frequency Division Multiplexing (OFDM) In Multiple-Carrier Modulation (MCM), the channel is divided into several lower rate subchannels over which data is transmitted in parallel. This allows the transmit symbol duration of each sub-carrier to be extended beyond the channel delay spread such that each subchannel can be considered frequency flat. The simplest way this can be achieved is by dividing the channel into frequency non overlapping bands. However, such a design is not practical and spectrally inefficient [40]. Much greater spectral efficiency is possible if sub-channels were overlapping but orthogonal to each other to prevent Inter-Carrier Interference (ICI). Such an approach is called Orthogonal Frequency Division Multiplexing (OFDM). OFDM implementation was impractical until Weinstein and Elbert [41] showed how Discrete Fourier Transform (DFT) could be used to practically implement OFDM in the baseband. OFDM can also help mitigate Inter-Symbol Interference (ISI), and ICI avoidance as well, via adding a Cyclic Prefix (CP) of the original OFDM symbol into a Guard Interval (GI). Efficient utilization of a GI is made possible due to the long duration of the OFDM symbol when compared to single carrier counterparts. OFDM can completely eliminate ISI and ICI if the length of the GI is chosen to be longer than the duration of the channel impulse response [42]. OFDM can also be extended to become a multiple access technique by allowing different users to share OFDM symbols. By dynamically allocating different carriers to different users, Orthogonal Frequency Division Multiple Access (OFDMA) can efficiently exploit all types of diversity, including time, frequency, space, and multiple-user diversities [43]. 8 Chapter 1. Introduction and Overview 1.3 Thesis Contributions and Organization The previous section described key concepts that are of great relevance to most of the contributions made in this thesis. Specifically, the main body of this thesis consists of four major parts that deal with the problems of resource allocation/optimization in multiple-user single/multiple antenna legacy and CR wireless communication systems. In the first two parts, Chapters 2 and 3, we build on the well established work of legacy wireless communication systems and propose two innovative and practical solutions for resource allocation at the transmitter and multiple-user detection at the receiver. The other two parts, Chapters 4 and 5, focus on developing efficient resource allocation/optimization techniques for CR systems. The broad nature of the investigated topics was a natural reaction to research opportunities that were appealing and required deeper examination. Nonetheless, the discussed topics and the proposed techniques all share the common goal of achieving advancements in efficient utilization of system resources in multiple-user wireless communication systems under practical and realistic assumptions. Topics discussed in the background section above can also be viewed as a uniting base for the contributions made in the following chapters. In Chapter 2, we introduce a new Differentiated Successive Interference Cancellation (DiffSIC) ordering technique for uplink multiple-user systems. Unlike classical Successive Interference Cancellation (SIC), DiffSIC is capable of differentiating users according to their priority or class of service by selecting a detection order that best fits the users’ service profiles. In addition, DiffSIC is able to achieve the optimal SIC detection order that results in the best overall system performance. In order to develop DiffSIC, we introduce analytical 9 Chapter 1. Introduction and Overview methods towards finding instantaneous Symbol Error Rates (SERs) for the Zero Forcing SIC (ZF-SIC) and Minimum Mean-Square Error SIC (MMSE-SIC) detectors. Furthermore, we devise two procedures to reduce the computational complexity associated with the computation of SER and the enumeration of detection orders. We present a number of numerical results which clearly demonstrate the ability of DiffSIC to accomplish service differentiation and overall performance improvement in general. In Chapter 3, we introduce a new channel allocation scheme for uplink multiple-user MIMO systems. In such a system, different users are treated as multiple antennas and spacetime multiple-user detection algorithms are used at the receiver to separate users sharing the same channel. In our allocation scheme, users are allowed to share multiple uplink channels simultaneously. This improves the overall uplink system capacity and fairly equalizes the BER performance of different users. In Chapter 4, we study the problem of resource allocation and optimization for MIMO CR systems under the assumption of imperfect CSI of the channels between the SUs and the PUs at the SUs. We formulate robust design optimization problems for CR systems with one or more SUs communicating over a single or multiple frequency carriers in the presence of multiple PUs. We propose a Linear Matrix Inequality (LMI) transformation that facilitates proper treatment of channel uncertainty at the SU transmitter and we provide solutions to the design problems based on convex optimization and Lagrange dual decomposition techniques. Finally, we demonstrate the importance of the proposed formulations and the implications of ignoring channel uncertainties when designing for CR systems. In Chapter 5, we tackle the problem of admission and eviction control of Real Time (RT) SUs in multiple-user OFDMA CR systems and propose new solutions that are practical 10 Chapter 1. Introduction and Overview and efficient at the same time. In CR systems, the fluctuating nature of the available frequency resource due to PU activity necessitates the introduction of admission and eviction measures at the CR system if a guaranteed QoS is required by RT SUs. This problem has been recently addressed in the literature with simplified assumptions that might become unrealistic in practical system setups. In particular, we propose three different ways to install a Resource Buffer Zone (RBZ) at the time of admission to limit future call drops resulting from fluctuating PU activity. We also study the effect of PU activity on the feasibility of the resource allocation problem and propose three different methods to resolve system outages once they occur. Numerical results obtained through Monte Carlo simulations demonstrate the efficacy of the proposed techniques. Finally, in Chapter 6, we conclude this thesis and provide insight into some pending issues that can be addressed in future research efforts. 11 Chapter 2 DiffSIC: Optimal SIC Detection with Service Differentiation 2.1 Introduction In spatial multiplexing MIMO techniques, independent data streams transmitted from different antennas at the transmitter can be recovered at the receiver when their spatial signatures are sufficiently different. The application of spatial multiplexing to uplink multiple-user systems is particularly relevant due to the inherent spatial separation between the antennas of different user that might not be available between antennas on the same handset. Also, the lack of cooperation between users makes spatial multiplexing the only technique that can fully take advantage of the available spatial diversity. Towards that, multiple users can simultaneously communicate with a BS that is equipped with multiple receive antennas, and space-time Multiple-User Detection (MUD) can be used at the receiver to separate the signals from these users [44, 45]. Since optimal space-time MUD algorithms are often too complex and time consuming, linear and non-linear approximations of optimal algorithms are used. In particular, non-linear detectors using Successive Interference Cancellation (SIC) are powerful and significantly outperform linear detectors. In these detectors, the order of 12 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation detection substantially affects the performance of individual users. The classical SIC detector is the Vertical Bell Laboratory Layered Space Time (V-BLAST) detector [46] that aims at finding the detection order that carries the least amount of error propagation. In the context of a layered transmission approach, the Medium Access Control (MAC) layer is normally responsible for providing service differentiation through frame scheduling, while the Physical (PHY) layer’s responsibility is to deliver the packets passed by the MAC layer with the least amount of errors. This concept has changed when researchers started to think across layers and noticed that getting the PHY layer involved in the packet scheduling effort could enhance the performance of the system dramatically [2]. The Channel State Dependent Packet Scheduling (CSDPS) [47] was one of the first schedulers to address this problem. But, this involvement always took place in the scheduling process of the MAC (i.e. the status from the PHY layer was used in the scheduling process of the MAC), and had nothing to do with PHY layer transmission and detection tools and algorithms that were used. We claim that the service differentiation process can take advantage of the PHY layer capabilities to gain more improvement at the user level. To this end, we propose a new SIC ordering algorithm that works at the BS of a multiple-user uplink system and can differentiate users in service by altering the detection sequence. In particular, this Differentiated SIC (DiffSIC) works in favor of high priority customers, while low priority users may experience a (short-term) performance degradation. DiffSIC considers Symbol Error Rate (SER) as the relevant performance measure, and therefore we also derive the necessary SER expressions in this chapter. We note that an enhancement in SER, or interchangeably the Packet Error Rate (PER), performance of a user’s communications link directly affects the performance of 13 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation data communications over that link. In error-intolerant applications (commonly running over TCP/IP), such as file transfers and web browsing, a more reliable link translates directly into less retransmissions which, in turn, means lower delay and higher efficiency. On the other hand, in applications such as voice or video over IP, certain levels of error can be tolerated as long as they do not extremely deteriorate the content quality to a point where it becomes noticeable by the end user. We present a number of simulation results which substantiate that DiffSIC is capable of changing link reliabilities according to the needs of such applications. We would like to emphasize that DiffSIC takes place at the BS and requires no involvement of or feedback to the users. If such a feedback is available or used for user differentiation anyway [48, 49], DiffSIC could still be applied as an additional fine-grain service differentiation tool. Also, through a feedback channel, high priority users can be advised to use a higher signal constellation size to take full advantage of the improved signal quality they enjoy at the receiver. 2.2 System Model We consider the uplink of a multiple-user system, where each user is equipped with a single transmit antenna, while the BS has Mr receive antennas. Each user acts as a single antenna of a MIMO transmitter, and space is utilized by allowing Mt users to communicate simultaneously to the BS such that Mt ≤ Mr 1 . The uplink transmitters use square M -ary Quadrature Amplitude Modulation (QAM) constellations and SIC is used at the BS to sep1 The ideas presented in this chapter are readily extended to multiple-user MIMO systems where individual users have multiple antennas and different applications/streams that might have different service requirements. 14 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation n a H r F y aˆ z + - B Figure 2.1: Block diagram of the equivalent real-valued transmission system using a SIC detector. arate different users. The block diagram of the equivalent discrete-time transmission system is shown in Figure 2.1. The received signal at the BS can be represented in the complex baseband vector form as r = Ha + n, (2.1) where r = [r1 · · · rMr ]T is the received signal vector, H is the Mr × Mt channel matrix, a = [a1 · · · aMt ]T is the transmitted QAM signal vector with average element-wise symbol energy Es , and n = [n1 · · · nMr ]T is the i.i.d. circularly symmetric complex Gaussian noise vector with covariance matrix σn2 I Mr . The transmission model in (2.1) can also be written in its equivalent real-valued format ¯a r¯ = H ¯+n ¯ (2.2) 15 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation where ℜ (a1 ) ℜ (r1 ) ℑ (a ) ℑ (r ) 1 1 .. .. , a ¯ = r¯ = . . ℜ (a ) ℜ (r ) Mt Mr ℑ (aMt ) ℑ (rMr ) and −ℑ (h1,1 ) · · · ℜ (h1,1 ) ℑ (h ) ℜ (h1,1 ) ··· 1,1 .. .. ... ¯ H= . . ℜ (h Mr ,1 ) −ℑ (hMr ,1 ) · · · ℑ (hMr ,1 ) ℜ (hMr ,1 ) ··· ℜ (n1 ) ℑ (n ) 1 .. , n ¯ = . ℜ (n ) Mr ℜ (h1,Mt ) ℑ (h1,Mt ) .. . ℑ (nMr ) −ℑ (h1,Mt ) ℜ (h1,Mt ) .. . . ℜ (hMr ,Mt ) −ℑ (hMr ,Mt ) ℑ (hMr ,Mt ) ℜ (hMr ,Mt ) Thus the Mt × Mr M -ary QAM system gets transformed into a 2Mt × 2Mr real valued L-ary √ Pulse Amplitude Modulation (PAM) system where L = M . The SNR of the equivalent system remains intact since both the noise and symbol energies get divided by 2. The signal r¯ is processed at the receiver by a SIC detector to separate signals from different users. The detector is illustrated in Figure 2.1 and can be expressed as [20, Ch. 10.3.4] ¯a ˆ z¯ = F¯ r¯ − B ¯, (2.3) ¯ and a ˆ where F¯ , B ¯ are the 2Mt × 2Mr matrix forward filter, the 2Mt × 2Mt strictly lower triangular matrix feedback filter, and the vector of 2Mt detected symbols, respectively. In ZF-SIC, the forward filter F¯ can be derived using the Cholesky decomposition of the Hermitian matrix ¯ ¯ =G ¯ H G, ¯=H ¯ HH R (2.4) 16 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation ¯ is a lower triangular matrix with real and positive diagonal elements. G ¯ can be where G ¯ = Γ ¯M ¯ , where Γ ¯ is diagonal with real and positive further decomposed according to G ¯ is lower triangular and monic. The forward filter F¯ can then be written elements, and M as ¯ −1 G ¯ −H H ¯ H, F¯ = Γ (2.5) ¯ is the strictly lower triangular matrix such that and the feedback matrix B ¯=M ¯ − I 2Mt . B (2.6) ¯ and M ¯ can be derived using a similar technique to the For MMSE-SIC, the matrices F¯ , B ¯ in (2.4), has to be replaced by the matrix one used in ZF-SIC. The only difference is that R, ¯=H ¯ HH ¯ + σn2 I Mt R (2.7) The reader is referred to [20, Ch. 10.3.4] for full details. In SIC detectors, the order of detection greatly affects the performance of individual users. The user that is detected first receives no gain from the SIC, while the user detected last achieves its best performance if correct decisions were assumed. Given a channel realization, there is always a detection order that gives the best average performance. In V-BLAST, instantaneous post-detection SNRs are used to achieve a detection order in a sequential manner [46]. As we will see later in this chapter, this criterion does not always result in the best order, in terms of SER performance, although it gives a very good approximation considering its low processing requirements. 17 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation It was shown in [50, 51] that when considering the real-valued model in (2.2) shaping the equivalent real-valued channel matrix such that the real and imaginary parts of one transmitter get detected in sequence renders these two parts of the signal independent. This ¯ and limits the in turn reduces the complexity of computing the matrix filters F¯ and B number of possible orders of detection back to Mt !. The equivalent model in (2.2) will be used throughout this chapter with the assumption that the real and imaginary parts of one user are detected in sequence. 2.3 DiffSIC Ordering Algorithm As it was mentioned earlier, in SIC receivers, applying the detection order that leads to the best average system performance might not always be desirable. Users with high priority can be given an advantage by choosing detection orders that work in their favor. The proposed DiffSIC algorithm gives the flexibility of differentiating users according to their class of service. DiffSIC exploits the predicted SER performance to determine the order of detection. Therefore, we first derive SER expressions for SIC taking error propagation into account. Then, we present the DiffSIC algorithm and its adaptation to the case when multiple detection chains are employed at the receiver. As in the related literature, e.g., [42, 52, 53], we mainly focus on ZF-SIC for its better analytical tractability, but the extension to MMSE-SIC is also shown. 18 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 2.3.1 SER Analysis for ZF-SIC Detectors The following analysis is similar to those in [42, 53], but adapted to the real-valued transmission model in (2.2) and with an efficient extension to non-binary transmission, which renders the computational complexity of the final expression independent of the constellation size M. Given a channel realization H, the error probability for M -ary QAM transmission at the i-th layer, 1 ≤ i ≤ Mt , can be calculated as M −QAM L−P AM Pi|H = 1 − 1 − P2i−1| ¯ H L−P AM 1 − P2i| , ¯ H (2.8) L−P AM L−P AM where P2i−1| and P2i| are the error probabilities of the equivalent real and imaginary ¯ ¯ H H L-ary PAM signals, respectively. Note that the i-th layer of the complex-valued system model in (2.1) corresponds to the (2i − 1)-st and 2i-th layers of the equivalent real-valued system model in (2.2). The error probability for the real-valued model can be written as AM = Pi|L−P ¯ H Pi|ei−1 Pr(ei−1 ), (2.9) ei−1 ∈E i−1 where E i−1 is the set of all possible error sequences ei−1 = [e1 , e2 , ..., ei−1 ] of layers prior to layer i, Pi|ei−1 is the probability of error at the i-th step given the error sequence ei−1 , and Pr(ei−1 ) is the probability that such an error sequence occurs. To find the conditional error probability Pi|ei−1 , we need to consider the detector output ¯ is strictly lower triangular, the decision variable z¯i at the i-th layer z¯ given in (2.3). Since B 19 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation can be written as z¯i = a ¯i + f¯i n ¯+ =a ¯i + f¯i n ¯+ i−1 k=1 i−1 ¯bik a ˆ¯k ¯k − a ¯bik ek , (2.10) k=1 where f¯i is the i-th row of the matrix forward filter F¯ and ¯bik is the element at the i-th row ¯ Since the rows of F¯ are orthogonal in case and k-th column of the matrix feedback filter B. of ZF-SIC, the decision variables z¯i at different layers are independent for a given ei−1 . For non-binary signal constellations, we make the assumption that errors between nearestneighbor signal points with minimum Euclidean distance dmin = 6 E M −1 s dominate the performance. This limits the set of error symbols ei to Ei = {−dmin , 0, +dmin } and renders the complexity for computing the SER, and thus the DiffSIC algorithm introduced below, independent of the size M of the signal constellation used by the users2 . Simulation results in Section 2.6 show that such an assumption is reasonable for SNR values where communication systems usually operate. Then, from (2.10), we derive in Appendix A that Pi|ei−1 can be written as (1) (2) Pi|ei−1 = Pi|ei−1 + Pi|ei−1 , where (1) Pi|ei−1 dmin /2 + L−1 Q = L Mr j=1 i−1 k=1 (2.11) ¯bik ek f¯ij2 σn2 /2 , (2.12) 2 Here we assume that all users use that same constellation size. Nevertheless, the analysis is still applicable if different constellation sizes were used by different users as long as dmin is adjusted accordingly 20 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation and (2) Pi|ei−1 dmin /2 − L−1 Q = L Mr j=1 i−1 k=1 ¯bik ek f¯ij2 σn2 /2 . (2.13) In (2.12) and (2.13), f¯ij refers to the element at the i-th row and j-th column of the forward filter F¯ and Q(·) is the complementary cumulative distribution function of a Gaussian random variable. Finally, we note that Pr(ei−1 ) follows from the recursion i−1 Pr(ei−1 ) = k=1 where Pr(ek |ek−1 ), 1 − Pk|ek−1 Pr(ek |ek−1 ) = P (1) k|ek−1 P (2) k|ek−1 2.3.2 (2.14) , ek = 0, , ek = +dmin , (2.15) , ek = −dmin . DiffSIC Ordering Algorithm The DiffSIC algorithm utilizes the SER expression (2.8) to determine the order of detection that best fits the service profile of different users. We first define the set of permutation matrices {P ℓ |ℓ = 1, . . . , Mt !} corresponding to all possible channel detection orders such that H ℓ = HP ℓ is the ordered channel matrix. Then, for each detection order ℓ we compute the cost Xℓ associated with this detection order as Mt Xℓ = i=1 M −QAM . ci Pi|H ℓ (2.16) 21 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation M −QAM The contribution from user i to the cost Xℓ is given by means of its SER Pi|H and the ℓ priority indicator ci . The optimal order ℓopt can then be found as ℓopt = argmin Xℓ . (2.17) ℓ The choice of the priority indicator vector c = [c1 , c2 , ..., cMt ] is done at higher layers and is based on the service profiles of users. Without loss of generality we limit ci such that ci ∈ [0, 1] with 1 being the highest priority. The different priority classes essentially determine how greedy the algorithm should be to achieve the performance differentiation. The larger the difference between high priority and low priority assignments, the greedier the algorithm, and the better the performance of high priority users. Clearly, at the same time, DiffSIC may deteriorate the performance of low priority and best effort users (ci = 0). The computational complexity of the DiffSIC algorithm lies in the repeated evaluation of the SER expression in (2.8). While the expression itself can be written in terms of elementary functions (e.g., using exponential approximations for the error function [54]), the number of possible error events (32(Mt −1) ) and orderings (Mt !) render the detection complexity larger than for regular V-BLAST especially for large dimensions Mt . We argue that this extra complexity may be affordable, especially in slowly time-varying channels, since DiffSIC is executed only infrequently compared to the detection process. This is decidedly different from ordering based on individual received vectors as advocated in e.g. [55]. Furthermore, the complexity of DiffSIC can significantly be reduced by approximating the calculation of M −QAM Pi|H in (2.8) focusing on dominant error events or by using a subset of the total number ℓ of detection orders available. Such approximations are discussed in detail in Section 2.4. 22 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 2.3.3 Multiple Detection Chains In the case where the receiver has the capacity to employ multiple SIC chains, a different order of detection can be exploited per chain and DiffSIC can be used to simultaneously work in favor of multiple users. The parallel use of several SIC detectors with different orders is known from multiuser detection for Code Division Multiple Access (CDMA) under the name of parallel arbitrated search for interference cancellation (PASIC) [56, 57]. Different from PASIC, here we do not apply parallel detectors to arbitrate among candidate symbol estimates obtained with different pre-selected orders. Instead, DiffSIC chooses different orders of detection to achieve the best available performance for each user given a channel matrix H. Results shown in Section 2.6 demonstrate the performance benefits that are obtained with multiple detection chains. 2.3.4 Extension to MMSE-SIC The DiffSIC algorithm is also readily extendable to Minimum Mean-Square Error SIC (MMSE-SIC) receivers. Such an extension primarily depends on the availability of instantaneous SER estimates for MMSE-SIC receivers. The decision variable for MMSE-SIC detection at layer i can be written as 2Mt i−1 m ¯ ik a ¯k + z¯i = k=i ¯bik ek + n ˜¯ i , (2.18) k=1 ¯ and n ˜¯ i = f¯i n ¯ . Different where m ¯ ik is the element in the i-th row and k-th column of M from ZF-SIC (cf. Eq. (2.10)), the MMSE forward filter F (i) does not transform the channel ˜ H into a monic and causal transfer function and (ii) the elements of the noise vector n ¯ = 23 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation ˜¯ 1 , . . . , n ˜¯ 2Mt ] = F¯ n [n ¯ are correlated. Hence, the instantaneous SER analysis for MMSESIC detectors is different from that for ZF-SIC detectors in two aspects. First, the noise correlation increases the dependency between layers beyond the error propagation problem. Second, the imperfect interference suppression renders the error rate at a layer dependent on higher, yet to be detected, layers. Taking the two mentioned effects into account, the error probability for MMSE-SIC at the i-th layer in (2.9) is given by AM Pi|L−P = ¯ H Pi|ei−1 ,ai+1 Pr(ei−1 ) Pr(ai+1 ), (2.19) ai+1 ∈Ai+1 ei−1 ∈E i−1 where Ai+1 is the set of all possible L-PAM symbol sequences ai+1 = [ai+1 , ..., a2Mt ] of layers to be detected and Pi|ei−1 ,ai+1 is the probability of error at layer i given the error and symbol AM sequences ei−1 and ai+1 . Pi|L−P in (2.19) can be rewritten as ¯ H AM Pi|L−P = ¯ H 1 L2Mt −i Pi,ei−1 |ai+1 , (2.20) ai+1 ∈Ai+1 ei−1 ∈E i−1 where Pi,ei−1 |ai+1 is the joint error probability given the symbol sequence ai+1 . Pi,ei−1 |ai+1 can be calculated as Pi,ei−1 |ai+1 = 1 i−1 (αk ) 2 k=1 (1) De i−1 ,a i+1 ˜ ˜ p(n ¯ i ) dn ¯i + (2) De i−1 ,a i+1 ˜ ˜ p(n ¯ i ) dn ¯i , (2.21) ˜ ˜ ˜¯ 1 , . . . , n ˜¯ i ], αk is equal to 1 when ek = 0 and (L − 1)/L otherwise, p(n where n ¯ i = [n ¯ i ) is ˜ the probability density function (pdf) of n ¯ i , and D (1,2) ei−1 ,ai+1 are the noise regions that lead 24 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation to an error at layer i given ei−1 and ai+1 in both directions of the constellation point. The i-variate noise pdf is given by ˜ p(n ¯ i) = 1 (2π)i/2 1 T −1 ˜ Mi n ˜ ¯ ¯i , exp − n 2 i |M i | (2.22) T where M i = σn2¯ F¯ i F¯ i is the i × i noise covariance matrix and F¯ i contains the first i rows of F¯ . Evaluation of (2.21) in closed form is not possible. However, using again the nearestneighbor-error approximation, the regions D (1,2) ei−1 ,ai+1 are composed of a positive and negative orthant, and for this case several approximations for (2.21) have been proposed in literature, e.g. [58–60]. Here we adopt the method by Joe [60] that utilizes conditional expectations and regression with binary variables to approximate multivariate normal probabilities for rectangular regions. This approximation is sufficiently accurate and fast to compute (please refer to [60] for details). Thus, by substituting (2.19) into (2.8) we obtain a semi-analytical expression to quickly evaluate the SER for MMSE-SIC systems with a moderate number of users. Further simplifications tackling complexity due to the averaging over ai+1 in (2.19) are possible but not pursued here. Instead, in the following section we introduce some approximations to lower the complexity of DiffSIC with respect to the number of error vectors and detection orders that need to be considered. 25 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 2.4 Reduced Complexity Approximations for DiffSIC The computational complexity of the optimal DiffSIC algorithm introduced in Section 2.3 has two main contributors, namely the cost of calculating the SER in (2.8) and the number of detection orders explored by the algorithm. Therefore, in this section, we present two simplifications that will help to reduce the cost of SER computation and the number of enumerated detection orders. These can be applied separately or in combination to lower the computational complexity. Furthermore, while the simplifications are applicable to both ZF- and MMSE-SIC, for clarity of exposition we restrict our attention to ZF-SIC receivers. 2.4.1 Low-Complexity SER Approximation The complexity of calculating the SER in (2.9) grows exponentially with the number of layers, since the number of error sequences in the set E i−1 = {−dmin , 0, +dmin }i−1 is equal to 3i−1 . In this section we introduce a reduced complexity approximation of this calculation by employing an effective subset Ψi−1 ⊂ E i−1 . In [53, 61] it was suggested that, on average, errors at the first layer have a dominant effect on the performance of subsequent layers. Thus, the dominant contributions to the error probability at layer i are coming from error sequences in ei−1 ∈ Ψi−1 = {−dmin , 0, +dmin } × {0}i−2 that have errors only at the first step. While the conclusions in [53, 61] are intuitively valid, they are not necessarily true for every channel realization nor will they lead to the best approach towards reduction in SER computational complexity as will exemplarily be shown in Section 2.6. We generalize the suggestion in [53, 61] in that we select the subset Ψi−1 of error sequences that dominate the sum in (2.9). We limit the size |Ψi−1 | to a predefined threshold Ni−1 and thus control 26 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation and reduce the algorithm’s complexity by limiting the number of evaluations of (2.11). This approximate SER calculation is formalized in Algorithm 2.1. In Algorithm 2.1 we use the fact that the higher the probability of error at one layer, the larger its influence in determining the dominant terms in the error calculation of subsequent layers. Thus, after scanning the initial calculation of errors at every layer assuming no previous errors (Algorithm 2.1, line 8), the algorithm branches the error sequence that is most likely to occur. That is, the most likely error event with sequence [ek−1 , 0i−k+1 ] is followed-up by also considering the sequences [ek−1 , −dmin , 0i−k ] and [ek−1 , +dmin , 0i−k ] for error rate calculation (Algorithm 2.1, lines 14-17). This is extremely helpful, especially when the exact probabilities of error are not needed. We use this algorithm to approximate the cost function in (2.16). Results in Section 2.6 confirm that Algorithm 2.1 can significantly reduce the amount of calculations needed and preserve the gains of DiffSIC at the same time. The amount of savings in computational complexity depends mainly on the number Ni−1 and can be quantified as 2.4.2 Ni−1 3i−1 × 100%. Approximation for Selecting Order of Detection The number of available detection orders grows factorially with the number of layers. Thus, at a certain level, it becomes impractical for DiffSIC to consider all possible detection orders when looking for the optimal order that best serves the differentiated needs of users. In this section we describe a reduced complexity search algorithm that can be adjusted to the computational capabilities of the receiver’s processor. The algorithm narrows the set of detection orders to be considered down to a predetermined maximum number of orders Nmax , where DiffSIC can kick back in and choose the best order among the shortened list. 27 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation Algorithm 2.1 Approximate SER calculation Input: i, H ℓ , Ni−1 AM Output: Pi|L−P ¯ H 1: // Initialize set of error sequences 2: Ψi−1 = e1i−1 = {0i−1 } 3: // Initialize error sequence count 4: J = 1 for each k ∈ {1, 2, · · · , i} 5: Calculate Pk|e1 k−1 6: // Initialize SER estimate and decision matrix E AM = Pi|e1 7: Pi|L−P ¯ H i−1 8: E(k, 1) = Pk|e1 k−1 Pr(e1i−1 ), Pr(e1k−1 ) for each k ∈ {1, 2, · · · , i − 1} 9: while (J < Ni−1 ) do 10: // Find dominant error event, i.e., the error event that is most likely to happen 11: ˆ ˆj] = [k, argmax k∈{1,...,i−1},j∈{1,...,J} 12: {E(k, j)} ˆ ˆj) = −1 E(k, 13: ˆ which gives two new sequences // Branch error sequence at layer k, 14: eJ+1 = [ejk−1 , −dmin , 0i−k ], eJ+2 = [ejk−1 , +dmin , 0i−k ], Ψi−1 := Ψi−1 , eJ+1 , eJ+2 15: Calculate Pk|ej ˆ ˆ k−1 for each k ∈ {kˆ + 1, · · · , i} and j ∈ {J + 1, J + 2} 16: ˆ and j ∈ {J + 1, J + 2} E(k, j) = −1 for each k ∈ {1, · · · , k} 17: E(k, j) = Pk|ej k−1 Pr(ejk−1 ) for each k ∈ {kˆ + 1, · · · , i − 1} and j ∈ {J + 1, J + 2} 18: // Update the SER estimate and error sequence count 19: J+2 AM AM + Pi|eJ+1 Pr(eJ+1 := Pi|L−P Pi|L−P ¯ ¯ i−1 ) + Pi|eJ+2 Pr(ei−1 ) H H 20: // Update error sequence count 21: J := J + 2 i−1 i−1 22: end while 28 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation The proposed heuristic solution to reduce the number of orders to be considered by the DiffSIC algorithm is to fix the first F users in the detection chain such that (Mt −F )! ≤ Nmax . This is accomplished by choosing these first users of the detection sequence similar to the way V-BLAST orders users with the exception that a scaled version of the instantaneous post-detection SNRs is applied, where the scaling factor decreases with user priority. Thus, high priority users are pushed towards the end of the detection chain. The rationale for this is that even though error propagation in SIC eliminates any diversity gains for higher layers, SNR gains when moving from lower to higher layers often outweigh the effect of error propagation on SER. This is consistent with our observation that also the full-fledged ordering algorithm in DiffSIC often places high priority users at higher layers. The pseudocode for our heuristic solution is shown in Algorithm 2.2. The scaling of SNRs is done by multiplying the noise enhancement factor Γii for user i with the relative priority (ci − min{cu }) (Algorithm 2.2, lines 7,14), where U is the set of users still to be ordered, u∈U and a sensitivity parameter S ∈ [0, 1]. The sensitivity parameter balances the influence of SNR (1/Γii ) and user priority ci on the detection order. More specifically, the scaling is designed such that when S = 0, no differentiation is attained, and the algorithm behaves exactly as V-BLAST in determining the order of detection for the first F users, whereas when S → 1, the resulting order of detection is mostly determined by the users’ priorities with V-BLAST being utilized only if equal priorities are present. If S = 1, sorting is done purely according to priorities. As an example, consider a 4 × 4 system where users’ priorities are c = [0, 0.25, 0.50, 1.0] and S = 0.5. The total scaling vector at the first level (Algorithm 2.2, Line 8, for F = 0) will be (1 − S) + S(c − min{c}) = [0.50, 0.63, 0.75, 1.0]. Thus, the noise enhancement term is amplified for users with higher priorities, which discourages the early 29 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation Algorithm 2.2 Determine a reduced set of detection orders for DiffSIC Input: Sensitivity parameter S, users’ priorities c = [c1 , . . . , cMt ] Output: [k1 , . . . , kF , kFl +1 ], l ∈ [1, 2, . . . , D] 1: // H + denotes the pseudo inverse of H, 2: // H k¯i is the “deflated” version of H, in which columns k1 , k2 · · · ki have been zeroed 3: Initialize k0 = 0, U = {1, . . . , Mt }, F = 0 4: // First stage 5: while ((Mt − (F + 1))! > Nmax ) do 6: Γ = H+ (H + )H k¯F k¯F 7: kF +1 = argmin Γii (1 − S) + S ci − min{cu } u∈U i∈U 8: U := U \ kF +1 9: F := F + 1 10: end while 11: // second stage 12: D = ⌊Nmax /(MT − (F + 1))!⌋ 13: for l = 1 to D do 14: kFl +1 = argmin l−1 1 i∈U \{kF +1 ,...,kF +1 } Γii (1 − S) + S ci − min{cu } u∈U 15: end for 16: // The detection orders considered by DiffSIC start with [k1 , . . . , kF , kFl +1 ], l ∈ [1, 2, . . . , D] detection of these users. Since Nmax is not necessarily a factorial number, Algorithm 2.2 contains two stages, where F users are ordered first and then D selections for the (F + 1)st user are allowed such that (Mt − (F + 1))!D ≤ Nmax (Algorithm 2.2, lines 12-15). Numerical results in Section 2.6 will 30 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation illustrate the complexity-performance tradeoff achievable with Algorithm 2.2 for DiffSIC. 2.5 Performance Under Channel Estimation Errors In the formulation of DiffSIC we have assumed perfect uplink channel estimation at the receiver. However, channel estimation errors can lead to serious performance degradation as they not only affect data estimation but also the decision on the order of detection to be used. While this is true for general SIC receivers, such as V-BLAST, one could expect stronger degradations for DiffSIC, which relies on accurate SER estimation taking error propagation into account. It is therefore relevant to consider the effect of channel estimation errors on the performance of DiffSIC. Towards this end, we assume that the users transmit pilot sequences of length P , which we organize as the rows of the Mt × P matrix S p , and the corresponding received signal is Rp = HS p + n . (2.23) Based on Rp the receiver performs channel estimation, and the estimated channel matrix is used for subsequent data detection. Making the often used assumption that the elements of H are circularly symmetric complex Gaussian random variables, then it has been shown in [36] that maximum-likelihood (ML) and MMSE channel estimation with subsequent ML detection and joint ML processing of pilot and data signal can be cast into the same framework considering the equivalent channel model ˜ + ∆Ha + n = Ha ˜ +v , r = Ha (2.24) 31 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation ˜ is the MMSE channel estimate, ∆H = H − H ˜ is the estimation error, which where H ˜ and v = ∆Ha + n. Furthermore, if the elements of H are i.i.d. is independent of H, 2 with variance σH , the pilot sequences are orthogonal, and constant modulus data signaling, i.e., 4QAM, is used, then the elements of the effective noise vector v are also i.i.d. circu2 larly symmetric complex Gaussian distributed with variance σv2 = Mt Es σ∆H + σn2 , where −2 2 σ∆H = 1/(Es P σn−2 + σH ) is the variance of the elements of ∆H. Hence, in this case, any SIC detector, including DiffSIC, can use the equivalent system model in (2.24) with the ˜ and the effect of pilot-symbol based channel estimation is fully MMSE channel estimate H, accounted for by assuming the equivalent received SNR ˜ 22 } E{ Ha P/Mt =γ· , 2 E{ v 2 } 1 + P/Mt + 1/γ where γ = P/Mt 1+P/Mt +1/γ 2 M t Es σ H 2 σn (2.25) is the received SNR with perfect channel knowledge and the factor is the penalty due to the estimation error. Since this factor approaches a constant for increasing SNR γ, we conclude that performance differences between DiffSIC and VBLAST are essentially maintained regardless of the quality of channel estimation. In the case of non-constant modulus transmission the variance of the effective noise becomes data dependent. A pragmatic approach is to still apply (2.24) with the assumption of i.i.d. elements of v with variance σv2 given above. Simulation results presented in the next section indicate that also in this case the performance difference between DiffSIC and V-BLAST is maintained. 32 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 2.6 Performance Results In this section, we present a number of numerical results to demonstrate the benefits of DiffSIC. Unless otherwise specified, we assume a 4 × 4 multiple-user system, where Mt = 4 different users share the uplink to a BS that is equipped with Mr = 4 receive antennas and employs ZF-SIC. The channel coefficients are modeled as i.i.d. circularly symmetric complex Gaussian random variables. The SNR-axis in the following figures refers to the SNR per 2 antenna, i.e., γ/Mt = Es σH /σn2 . For the first set of results, we consider a single channel realization to illustrate the accuracy of the error-rate analysis and the potential of the DiffSIC algorithm. In particular, we √ apply the randomly generated channel realization (j = −1) 0.3272 − 0.1758j 0.7813 + 0.1981j H = 0.9494 + 0.4254j −0.3129 + 0.0488j 1.5202 − 0.1892j −0.7676 + 1.4247j 0.8977 + 0.1377j 0.7665 + 0.2656j 0.1350 − 0.6723j −0.1142 + 1.0922j 0.2340 + 0.6777j . 0.2692 − 0.2224j −0.6342 − 0.8060j −0.4942 − 0.4101j 0.1021 − 0.8831j −0.7175 − 0.0370j Figures 2.2 and 2.3 compare the individual SER results for the four users obtained with the analysis from Section 2.3.1 to those obtained through Monte Carlo simulation assuming a fixed sequential order of detection. In Figure 2.2, we observe that the simulation results perfectly match the calculated SER values for all users when transmission with 4-QAM is assumed. In the case of the 16-QAM constellation in Figure 2.3, we note some discrepancies between analytical and simulation results, which are due to only considering errors between nearest-neighbor signal points in the error propagation model as devised in (2.10). However, 33 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 0 10 −1 SER 10 −2 10 −3 10 −10 Analytical Simulation −5 0 5 10 SNR [dB] 15 20 25 Figure 2.2: Comparison of analytical and simulated SER performance results for one fixed channel realization. 4-QAM signal constellation and ZF-SIC detector using fixed order of detection. it can be seen that this only affects the SER analysis at high SER values and the discrepancies quickly diminish for low SERs usually of interest. For the sake of clarity, we show results for 4-QAM transmission in the following, but we note that the conclusions made are valid for general QAM constellations. The SER calculation can be made much faster by adopting the low-complexity SER approximation introduced in Section 2.4.1. Figure 2.4 compares the performance of our SER approximation method from Algorithm 2.1 (Method 1) to a reduced complexity SER calcu34 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 0 SER 10 −1 10 −2 10 −10 Analytical Simulation −5 0 5 10 SNR [dB] 15 20 25 Figure 2.3: Comparison of analytical and simulated SER performance results for one fixed channel realization. 16-QAM signal constellation and ZF-SIC detector using fixed order of detection. lation technique following the suggestions in [53] (Method 2) in which error sequences with early errors are considered first. The figure shows the relative deviation of the approximated SER from the actual SER for user 4 (detected last in the detection chain) for different SNR values. It can be observed that our algorithm achieves a tight SER approximation much faster than Method 2 while, at the same time, the number of error sequences that are explored is significantly reduced. For example, only 10% of the total number of error sequences is sufficient to bring down the deviation from the actual SER to about 5% at an SNR of 35 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 100 SNR = 0 dB (Method 1) SNR = 0 dB (Method 2) SNR = 10 dB (Method 1) SNR = 10 dB (Method 2) 90 Deviation from actual SER, in % 80 70 60 50 40 30 20 10 0 0 5 10 15 20 25 30 Fraction of error sequences explored, in % Figure 2.4: Comparison of the efficacy of reduced complexity SER approximations. SER approximation method from Algorithm 2.1 (Method 1) and SER approximation by considering error sequences with errors at lower layers first (Method 2). SER for user 4 is shown. The total number of error sequences is 36 = 729. 4-QAM signal constellation and ZF-SIC detector. 10 dB. Having confirmed the accuracy of the semi-analytical SER expressions and the efficiency of the proposed approximation, we now shift our attention to the potential of the DiffSIC algorithm. To this end, Figure 2.5 shows the SER-curves for the same scenario as in Figure 2.2, but with ordering of users according to the channel realization (V-BLAST) and with DiffSIC taking user priorities into account. In this example, user 4 is the only high priority 36 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 0 10 −1 10 −2 SER 10 −3 10 −4 10 −5 10 −6 10 −10 VBLAST : high priority (user 4) VBLAST : low priority (users 1−3) DiffSIC : high priority (user 4) DiffSIC : low priority (users 1−3) −5 0 5 10 15 SNR [dB] Figure 2.5: SER performance comparison between DiffSIC and V-BLAST for one fixed channel realization. User priorities are c = [0, 0, 0, 1]. 4-QAM signal constellation and ZF-SIC detector. user with a priority indicator of c4 = 1. The other three users are best effort with priority levels set to ci = 0, i = 1, 2, 3. We observe that the high-priority user enjoys a significant SER advantage of several orders of magnitude under DiffSIC compared to V-BLAST. This advantage will reflect substantially on the user’s service experience. Certainly, these gains come at the expense of low priority, best effort users, whose performance degradation depends on the particular channel realization. For the example shown in Figure 2.5 we observe that low priority users suffer a substantial degradation compared to V-BLAST as a result of 37 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 0 10 VBLAST (all users) DiffSIC: equal priority (all users) DiffSIC: low priority (users 1−3) DiffSIC: high priority (user 4) DiffSIC: 4 detection branches (all users) −1 SER 10 −2 10 −3 10 −4 10 −4 −2 0 2 4 6 8 SNR [dB] 10 12 14 16 18 Figure 2.6: Average SER performance comparison between DiffSIC and V-BLAST. User priorities are c = [0, 0, 0, 1]. 4-QAM signal constellation and ZF-SIC detector. their low class of service level. But the very purpose of DiffSIC is to enable the receiver to prefer some users over others, according to priority assignments, and the accomplishment of this task is evidenced in Figure 2.5. In the second set of results, we consider the average SER performance for fading channels. In Figure 2.6 we compare the average SER for DiffSIC and V-BLAST. A number of interesting conclusions can be drawn from this figure. First, for the case of equal priority users, it can be seen that DiffSIC slightly outperforms the V-BLAST algorithm. This confirms that 38 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation the V-BLAST ordering is sub-optimal yet surprisingly powerful given the low computational complexity it enjoys. Second, for the case of users with unequal priorities, the preferable treatment of the high priority user under DiffSIC provides it with a clear advantage compared to V-BLAST, e.g., an SNR advantage of 4 dB at SER of 10−3 . Third, if four parallel detection branches are used, each of which applies the DiffSIC optimal order for one of the users, then this 4 dB gain over V-BLAST is achieved for all users. The corresponding SER curve in Figure 2.6 exactly coincides with the SER curve for the high priority user in a single-branch DiffSIC detector. The SNR gains of DiffSIC over V-BLAST are also present when MMSE-SIC detectors are used at the receiver. In Figure 2.7 we consider a 4 × 4 system, where user 4 is the only high priority user and MMSE-SIC is used at the receiver. In this example, the high priority user enjoys an about 4 dB SNR gain at SER = 10−4 when DiffSIC is employed instead of V-BLAST. As shown before, the full SNR gains accomplished for the high-priority user could be extended to all users if multiple detection chains were available at the receiver. We now consider the incorporation of Algorithms 2.1 and 2.2 from Section 2.4 to reduce the computational complexity of DiffSIC. As before, the priority profile c = [0, 0, 0, 1] is chosen. Figure 2.8 shows the effect of using the SER approximation from Algorithm 2.1 in determining the order of detection on the SER performance of the high priority user compared to V-BLAST. It is clear that the more error sequences are explored by the algorithm the wider the differentiation gap gets. However, we observe from Figure 2.8 that the major part of the gains is realized with only a small fraction of the total number of error sequences being considered. More specifically, we are able to attain almost the full advantage of DiffSIC at only 10% of the computational complexity, which is consistent with the SER results shown 39 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 0 10 VBLAST (all users) DiffSIC: high priority (user 4) DiffSIC: low priority (users 1−3) −1 10 −2 SER 10 −3 10 −4 10 −4 −2 0 2 4 6 SNR [dB] 8 10 12 14 16 Figure 2.7: Average SER performance comparison between DiffSIC and V-BLAST. Mt = Mr = 4. User priorities are c = [0, 0, 0, 1]. 4-QAM signal constellation and MMSE-SIC detector. in Figure 2.4. Next, Figure 2.9 shows the SNR gains of the high-priority user for a target SER of 10−3 as a function of sensitivity parameter S and the maximal number of detection orders Nmax . Note that the total number of orders is (Mt = 4)! = 24. We observe that already a good fraction of the maximal gain of about 3.9 dB (see Figure 2.8) is achieved with relatively few orders. Even a single order allows for notable gains of up to almost 2 dB. For the considered priority profile c = [0, 0, 0, 1], the sensitivity parameter S → 1 yields the best performance on average. This corresponds to pushing the high priority user to the end 40 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 4 3.5 3 SNR gain [dB] 2.5 2 1.5 1 −3 SER = 10 SER = 5 × 10−3 0.5 −2 SER = 10 Maximum Gains 0 2 4 6 8 10 12 14 16 18 20 Fraction of error sequences explored, in % Figure 2.8: Average SNR gain for high priority user with DiffSIC over V-BLAST when SER approximation according to Algorithm 2.1 is used. User priorities are c = [0, 0, 0, 1]. 4-QAM signal constellation and ZF-SIC detector. of the detection chain and V-BLAST ordering for lower layers whose order is then fixed in DiffSIC. The effect of the sensitivity parameter is more apparent when multiple priority levels are present. We therefore present in Figure 2.10 the same plot as in Figure 2.9 but with users having four different priority levels, namely c = [0, 0.25, 0.5, 1]. It can be seen that a sensitivity parameter 0 < S < 1 which balances the effects of the channel quality and user priority is preferable. While the optimal value of S changes with system configuration, i.e., 41 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 3.5 3 SNR gain [dB] 2.5 2 1.5 1 1 order 3 orders 6 orders 9 orders 0.5 0 0 0.9 0.99 0.999 Sensitivity parameter S Figure 2.9: Average SNR gain for high priority user with DiffSIC over V-BLAST when a reduced number of orders Nmax is used according to Algorithm 2.2 vs sensitivity parameter S. User priorities are c = [0, 0, 0, 1]. 4-QAM signal constellation and ZF-SIC detector. user priorities c and maximal number of orders Nmax , these values can be pre-calculated off-line and assigned accordingly. The two approximation techniques proposed in this chapter can also be used in combination to further reduce the computational complexity of DiffSIC. The 3-dimensional plot in Figure 2.11 shows the average SNR gains the high priority user achieves under DiffSIC over V-BLAST when both reduced complexity approximations are utilized. The figure clearly shows that by adopting both algorithms simultaneously we can reduce the computational 42 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 3 2.5 1 order 3 orders 6 orders 9 orders SNR gain [dB] 2 1.5 1 0.5 0 −0.5 0 0.9 0.99 0.999 Sensitivity parameter S Figure 2.10: Average SNR gain for high priority user with DiffSIC over V-BLAST when a reduced number of orders Nmax is used according to Algorithm 2.2 vs sensitivity parameter S. User priorities are c = [0, 0.25, 0.5, 1]. 4-QAM signal constellation and ZF-SIC detector. complexity substantially without loosing much on the SNR gains. We thus conclude the complexity-reduced DiffSIC is an attractive tool to accomplish user differentiation at the receiver in an uplink multiple-user system. Finally, we provide simulation results that support the use of the equivalent system model in (2.24) with appropriate SNR shifts even for non-constant modulus transmission. In Figure 2.12 we consider the single channel realization H from the beginning of this section, and we show the SER performance curves for V-BLAST and DiffSIC for a 16-QAM 43 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 4 SNR gain [dB] 3.5 3 2.5 2 1.5 20 20 Nu 15 15 mb er o 10 f or 10 der 5 5 sN ma x 0 f err tion o Frac , in % nces que or se Figure 2.11: Average SNR gain for high priority user with DiffSIC over V-BLAST when SER approximation according to Algorithm 2.1 and a reduced number of orders Nmax is used according to Algorithm 2.2 (S = 0.999). 4-QAM signal constellation and ZF-SIC detector. transmission under the assumption of perfect and imperfect channel estimation. For the case in which channel estimation errors occur, we assume a transmit pilot sequence length of ˜ is a damped version of the channel H such that H ˜ = P = 5, and the channel H 2 −σ 2 σH ∆H H 2 σH 2 ˜ + ∆H. The figure clearly shows how the shifted to maintain a variance of σH for the sum H version of the SER curves (according to (2.25)) under channel estimation errors coincide with the corresponding SER curves under the perfect channel estimation assumption. Thus, the performance gap between V-BLAST and DiffSIC is maintained regardless of the channel 44 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation 0 10 −1 SER 10 −2 10 −3 10 V-BLAST (P = ∞) High Priority (P = ∞) Low Priority (P = ∞) V-BLAST (P = 5) - shifted High Priority (P = 5) - shifted Low Priority (P = 5) - shifted −4 10 0 2 4 6 8 10 SNR [dB] 12 14 16 18 20 Figure 2.12: SER performance of DiffSIC and V-BLAST for perfect (P = ∞) and imperfect (P = 5) channel estimation (SNR for imperfect channel estimation is shifted for proper comparison). One fixed channel realization with user priorities of c = [0, 0, 0, 1], 16-QAM signal constellation and ZF-SIC detector. estimation quality. 2.7 Conclusions In this chapter, we have introduced the new Differentiated Successive Interference Cancellation (DiffSIC) ordering technique for uplink multiple-user systems. DiffSIC relies on the 45 Chapter 2. DiffSIC: Optimal SIC Detection with Service Differentiation SER evaluation for ZF-SIC and MMSE-SIC, for which we have presented semi-analytical expressions, to find the order of detection that best fits the users’ needs. We have also presented an SER approximation method, which is interesting in its own right and helps to achieve the differentiation gains with reduced computational complexity. In addition, we have devised a heuristic ordering algorithm to be used with DiffSIC, which takes channel quality and user priorities into account. We have shown numerical and simulation results which demonstrate that DiffSIC is capable of differentiating users according to their class of service. In particular, DiffSIC improves the SER performance of high-priority users significantly compared to those achieved with V-BLAST receivers. Furthermore, if DiffSIC is applied in combination with multiple detectors, these SER performance enhancements can be realized for multiple users. We thus believe that DiffSIC is a powerful detection tool to accomplish service differentiation and performance improvement in general. 46 Chapter 3 Uplink Channel Allocation Strategies for Multiple-User MIMO Systems 3.1 Introduction After introducing a receiver-based user differentiation technique in the pervious chapter, in this chapter we switch to the transmitter side of a similar multiple-user uplink system. In particular, we demonstrate a channel allocation technique that can result in enhanced overall system capacity or improved signal quality at the receiver. Contrary to the DiffSIC algorithm presented in Chapter 2, we aim through the channel allocation method described in this chapter at equalizing the performance among users that otherwise are treated unfairly in conventional channel allocation techniques. In this sense, the resource allocation method proposed in this chapter can be seen as an antithesis to DiffSIC from Chapter 2. Considering the uplink of a multiple-user system, Sfar et al. [62] proposed to group users in a number of groups equal to the number of orthogonal channels available for the uplink access. For example, if there are 2 orthogonal frequency bands available for the uplink transmission and 4 users are trying to access the uplink to the BS, then users are split into two groups, each having two users. Data from different groups is easily separated at the 47 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems receiver due to frequency orthogonality, while data from users within the same group is separated using the space, assuming that different users will have sufficiently uncorrelated channels to the receiver. Optimal MIMO detection algorithms at the receiver are too complex and time consuming. Other linear and non-linear approximations of optimal algorithms are usually used. These algorithms include linear Matched Filtering (MF), linear ZF and linear MMSE [20, 23]. Non-linear approximations might utilize the concept of Successive Interference Cancellation (SIC), see Chapter 2, or Parallel Interference Cancellation (PIC) [20]. We propose to further increase the uplink system capacity by allowing users to share multiple orthogonal channels simultaneously, i.e., users become members of multiple groups. Compared to the strategy described in [62], this will enhance the overall system capacity and fairly equalize the BER performance of different users at the same time. Ergodic capacity calculations as well as simulation results will be presented throughout this chapter to support these two claims3 . 3.2 System Model We consider a multiple-user OFDMA-based4 MIMO system, where users try to access the uplink using a limited number of orthogonal subbands. Each user is equipped with a single 3 In parallel to the work presented in this chapter, Visuri and Bolcskei described in [63] the tradeoff between the amount of signaling collision, i.e. multiple users sharing one subband, and the complexity of detection at the receiver. By introducing a variable amount of collision between users, a family of multiple access schemes emerge ranging from a CDMA like scheme in which all users share all subbands to an FDMA scheme where each subband is assigned to a single user. 4 The ideas presented in this chapter are readily extended to any other multiple-access technique with orthogonal channels including CDMA and TDMA systems. Also, CDMA systems with non-orthogonal codes and asynchronous transmission can be accommodated. 48 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems transmit antenna, while the BS has Mr receive antennas. Each user acts as a single antenna in a MIMO system, and space is utilized by allowing Mt users to share the same subband. Sfar et al. [62] refers to users sharing the same subband as a group, we will use the same terminology in this chapter. Frequency is used at the receiver to separate different groups, and space-time multiple-user detection techniques will be used to separate users within the same group. The following example illustrates the proposed channel allocation techniques. In this example, three users are sharing the uplink of an OFDMA system where only two orthogonal subbands are available. The proposed technique can be generalized for any number of users or subbands. The relatively small-size example discussed in this chapter is for illustrative purposes only. Example: In the system shown in Figure 3.1(a), two subbands are available for the uplink access. If two users are trying to access the uplink, then two groups will be formed with one user in each. Thus, each user will be assigned a different subband, and the frequency alone will be used to separate users at the receiver. Assume that a third user arrives to the system and tries to access the uplink. Running out of uplink channels, the system will assign the user to one of the existing groups [62]. This will create unbalanced interference within the two groups, see Figure 3.1(b). This unbalanced assignment gives preference to some users over others, which might not be desired. In our technique, the new user is admitted to both groups at the same time by assigning it both subbands as shown in Figure 3.1(c). Ergodic capacity calculations show that this approach can improve the system capacity and enhance the fairness of the system as well. Further capacity and fairness enhancements could be attained if all three users were admitted 49 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems *URXS 6XEEDQG 07 *URXS 6XEEDQG 07 *URXS 6XEEDQG $3 $3 *URXS 6XEEDQG 07 07 07 (a) (b) *URXS 6XEEDQG 07 *URXS 6XEEDQGV 07 07 $3 $3 07 07 07 *URXS 6XEEDQG (c) (d) Figure 3.1: Channel allocation. (a) 2 users using 2 subbands, (b) Allocation Strategy #1 (c) Allocation Strategy #2 (d) Allocation Strategy #3. to both groups as seen in Figure 3.1(d). The block diagram of the equivalent per-subband transmission system is shown in Figure 3.2. The received signal of a single group can be represented in the complex baseband vector form r = Ha + n, (3.1) 50 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems Q D + U ) \ k ] % Figure 3.2: Block diagram of the equivalent transmission system with linear and SIC detectors. where r = [r1 ...rMr ] is the received signal vector, H is the Mr × Mt channel matrix, a = [a1 ...aMt ] is the transmitted signal vector, and n = [n1 ...nMr ] is the noise vector. The received signal r will then be processed by a multiple-user detector to separate different users in the same group. The diagram in Figure 3.2 also shows the generalized matrix-valued view of linear and SIC detectors [20, 64]. The detector can be expressed as ˆ, z = F r − Ba (3.2) ˆ are the forward filter, the feedback filter, and the detected symbols, where F , B and a respectively. For linear detectors no feedback is required. Thus, the feedback matrix B is equal to zero. The forward filters of the linear Matched Filtering (MF), ZF and MMSE detectors are H H ,(H H H)−1 H H and (H H H + N0 I Mt )−1 H H , respectively, where N0 is the noise spectral density. For ZF-SIC and MMSE-SIC detectors, details on how to obtain the forward and feedback filters were provided in Section 2.2. 51 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems In SIC detectors such as ZF-SIC and MMSE-SIC, the order of detection greatly affects the performance of individual users. The user that is detected first receives no gain from the SIC, while the user detected last achieves the best performance if correct decisions were assumed. Depending on the channel realization, there is always a detection order that gives the best performance. The DiffSIC algorithm, described in Chapter 2, can be used to obtain this optimal order of detection. Alternatively, the standard V-BLAST algorithm can be used to find the order of detection that minimizes error propagation. 3.3 Capacity Analysis In this section, we calculate the ergodic capacity for each one of the allocation strategies described earlier in Section 3.2. In these calculations, Gaussian signaling, optimal coding, and optimal detection are assumed. These assumptions could be far from being practical, but it would give us a hint on what kind of gains are expected through these new channel allocation strategies. We will refer to the three allocation strategies as Strategy #1, Strategy #2 and Strategy #3 as shown in Figure 3.1. In the analysis provided below, we assume that there are 3 users, U1 , U2 and U3 , trying to access the uplink of the system while only 2 orthogonal channels, Subbands S1 and S2 , are available for the uplink traffic. Each user maintains one transmit antenna, while the receiver utilizes 2 receive antennas. Table 3.1 illustrates how the subbands are assigned to users under each one of the allocation strategies discussed earlier. The results obtained below could be generalized easily for any number of users, subbands, or receive antennas. In allocation Strategy #1, User U1 faces no interference while both Users U2 and U3 share 52 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems Table 3.1: Channel allocation strategies User U1 User U2 User U3 Strategy #1 S1 S2 S2 Strategy #2 S1 S2 S1 &S2 Strategy #3 S1 &S2 S1 &C2 S1 &S2 Subband S2 . This system could be divided into two separate systems: • A 1 × 2 Single Input Multiple Output (SIMO) system, where User U1 transmits using Subband S1 . H 1 is the corresponding 2 × 1 channel matrix. • A 2 × 2 MIMO system, where Users U2 and U3 share Subband S2 . H 2 is the corresponding 2 × 2 channel matrix. The total capacity in this strategy is [14]: H C = EH1 ,H2 log det(I Mr + ρH 1 H H 1 ) + log det(I Mr + ρH 2 H 2 ) , (3.3) where EH1 ,H2 is the expectation over H 1 and H 2 , and ρ is the SNR at each receiver branch. Using the same approach, in Strategy #2 Users U1 and U2 will face the same interference from User U3 . User U3 will transmit using both Subbands S1 and S2 while using the same power as the other two users do. Thus, User U3 needs to transmit using half the total power on each subband. This system setup could be divided into two equivalent systems: • A 2 × 2 MIMO system, where Users U1 and U3 share Subband S1 • A 2 × 2 MIMO system, where Users U2 and U3 share Subband S2 53 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems The total capacity in this strategy is C = 2 × EH log det(I Mr + ρHQH H ) , 1 where H is a 2 × 2 channel matrix, and Q = 0 . Similarly, the total capacity in 0 0.5 Strategy #3 is: (3.4) C = 2 × EH log det(I Mr + ρHQH H ) , (3.5) where H is a 2 × 3 channel matrix, and Q = 0.5I 3 . Another widely used measure of system capacity is the outage probability. In this context, the channel capacity is viewed as a random variable that depends on the instantaneous channel response. The probability that the channel capacity falls below a predetermined outage capacity is called the outage probability. Figure 3.3 shows some improvement in capacity for allocation Strategies #2 and #3 over Strategy #1. This improvement is also reflected on the outage probability curves shown in Figure 3.4. Despite the Gaussian signaling, optimal coding, and optimal detection assumptions made, these figures show some potential for improvement when using the new allocation schemes. Another interesting feature of channel allocation Strategies #2 and #3 is their BER equalization effect. This effect will be presented more clearly in the next section through simulation results. 54 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems 30 Strategy #1 Strategy #2 Strategy #3 Capacity [bit/s/Hz] 25 20 15 10 5 0 0 5 10 10 log10 (SNR) [dB] 15 20 Figure 3.3: Ergodic capacity for the 3 different allocation strategies. 3.4 Bit Error Rate (BER) Results In the previous section, capacity calculations showed some potential for performance enhancement when the new channel allocation strategies are in use. In this section, we test these allocation schemes in a more realistic environment. The system setup is the same as the one described earlier. Three users are trying to access the uplink of an OFDMA-based system, where two orthogonal subbands are available. The three channel allocation strategies we have investigated are the same strategies previously described in Table 3.1. We have implemented and tested several linear and non-linear detectors. Furthermore, 55 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems 1 Strategy #1 Strategy #2 Strategy #3 0.9 0.8 SNR = 10 dB Outage Probability 0.7 0.6 SNR = 15 dB 0.5 0.4 0.3 SNR = 20 dB 0.2 0.1 0 5 10 15 20 Rate (bit/s/Hz) 25 30 35 Figure 3.4: Outage probability for the 3 different allocation strategies, SNR = 10, 15 and 20 dB. real and complex-valued constellations at the transmitter were also tested. The use of realvalued constellations at the transmitter allows Widely Linear (WL) detectors [65] to be used at the receiver. In WL detectors only the real part of the Matched Filter (MF) output is used in the detection process. Varanasi [66] showed that using only the real part of the MF output at the receiver provides a sufficient statistics for the detection of the transmitted symbols. Schober et al. [67] also showed that in complex baseband channels, using the real part of the MF output can improve the receiver performance significantly and the number of users could be doubled. Another interesting property of real-valued modulation at the 56 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems Table 3.2: Simulation setups Strategy #1 Strategy #2 User U1 User U2 User U3 Constellation QPSK 4-ASK 4-ASK Detector MRC Constellation 4-ASK Detector Strategy #3 Constellation WL-MMSE-SIC 4-ASK 2 × BPSK WL-MMSE-SIC 2 × BPSK Detector 2 × BPSK 2 × BPSK WL-MMSE-SIC transmitter is the improvement that could be achieved when the system is overloaded and linear detectors are used at the receiver [68]. Each one of the aforementioned allocation strategies was tested against several system setups utilizing real and complex constellations at the transmitter alongside several linear, WL, and non-linear detectors. The results showed that for the three different strategies, the use of real constellations at the transmitter alongside WL detectors at the receiver gave the best results except for User U1 in Strategy #1, where complex constellations gave better results since this user does not face any interference in that specific allocation strategy. Table 3.2 describes the best simulation setup for each one of the three allocation strategies, and the multiple-user detector used at the receiver for each setup. We only show results for the WL MMSE SIC detector with ordering based on the V-BLAST algorithm as it gives the best performance results compared to other types of detectors. Note that we have used BPSK, a real-valued constellation, on each subband whenever two subbands are assigned to a user to keep the rate constant. QPSK and 4-ASK are used alternatively since they maintain the same data rate at the receiver. Figures 3.5 and 3.6 show the BER performance of the three users under each one of the 57 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems −1 10 −2 BER 10 Strategy #1, users 2 & 3 Strategy #1, user 1 Strategy #2, users 1 & 2 Strategy #2, user 3 Strategy #3, all users −3 10 0 2 4 6 10 log10(SNR) [dB] 8 10 Figure 3.5: BER performance for different allocation strategies using WL-MMSE-SIC detection with 2 receive antennas. allocation strategies discussed earlier. In Figure 3.5, the receiver had two receive antennas, while in Figure 3.6, the receiver had a single receive antenna. Both Figures 3.5 and 3.6 clearly show how the channel assignment in Strategy #1 results in an unbalanced BER performance between Users U2 and U3 on one side and User U1 on the other. This unbalanced performance is a direct result of the unbalanced channel allocation of Strategy #1, where Users U2 and U3 share a single subband while User U1 faces no interference on the second available channel. Allocation Strategy #2, on the other hand, is more balanced since User U3 interferes with both Users U1 and U2 equally. Compared to allocation Strategy #1, this strategy equally 58 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems −1 BER 10 Strategy #1, users 2 & 3 Strategy #1, user 1 Strategy #2, users 1 & 2 Strategy #2, user 3 Strategy #3, all users −2 10 0 2 4 6 10 log10(SNR) [dB] 8 10 Figure 3.6: BER performance for different allocation strategies using WL-MMSE-SIC detection with one receive antenna. distribute interference caused by User U3 and does not concentrate this interference on a single user. Finally, allocation Strategy #3 perfectly equalizes the BER performance of the three users since all the users are admitted to both transmission subbands. Figure 3.7 shows the average BER of all users under each one of the allocation strategies when one or two antennas are present at the receiver. The figure shows how the new allocation strategies enhance the overall system performance, which is consistent with the ergodic capacity calculations of Section 3.3. 59 Chapter 3. Uplink Channel Allocation Strategies for Multiple-User MIMO Systems Strategy #1 Strategy #2 Strategy #3 One receive antenna −1 10 BER Two receive antennas −2 10 −3 10 0 2 4 6 10 log10(SNR) [dB] 8 10 Figure 3.7: Average BER performance of all users for the three allocation strategies using WL-MMSE-SIC detection. 3.5 Conclusions In this chapter we introduced a new channel allocation scheme for uplink multiple-user MIMO systems in which users are allowed to share multiple uplink channels simultaneously. We have shown through ergodic capacity calculations and simulation results that such a technique improves the overall uplink system capacity, and fairly equalize the BER performance of different users. 60 Chapter 4 Designs for MIMO Cognitive Radio Systems with Imperfect CSI 4.1 Introduction After considering concepts for receiver design and channel allocation in legacy wireless communication systems in the previous two chapters, we shift our attention, for the rest of this thesis, and consider the contemporary and more appealing topic of Cognitive Radio (CR) systems. Although the concepts discussed in Chapters 2 and 3 were presented in a legacy system setup, they are still applicable to general wireless communication environments including CR systems. However, the concepts discussed here and in the next chapter are strictly applicable to CR systems due to the special nature of system resources and constraints. In CR systems, Secondary Users (SUs) are allowed to communicate over a licensed frequency band as long as communications by the spectrum owners, a.k.a. Primary Users (PUs), are protected and their priority over the shared spectrum resource is honored. Thus, SUs wishing to communicate over a licensed band would either restrict their transmissions to periods in which the primary system is inactive, or limit their transmission powers such that 61 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI the amount of interference generated at any PU receiver does not exceed a pre-determined level. Most of the work in the CR-related literature falls under one of the following two categories. The first set of work deals with the problem of measuring, sensing and prediction of the unused resources, cf. e.g. [34, 35]. The other set of work deals with the problem of efficient utilization of the discovered resources, cf. e.g. [69–74]. While both of these categories are of great importance, in this chapter, we focus our attention on the latter. Assuming perfect knowledge of the channels between the SU transmitter and PUs at the SU transmitter, the design of CR systems subject to constraints on the interference caused at PUs has been studied in [69, 70]. However, in practical scenarios, perfect knowledge of the channels to PUs may not be possible. Under the assumption of partial knowledge of these channels at the SU transmitter, robust designs for CR systems with single antenna SU and PU receivers were considered in [71, 72]. In [71], the assumption of a MISO channel allowed the problem to be formulated as a Second Order Cone Programming (SOCP) problem. On the other hand, the problem was transformed in [72] into a Semi-Definite Programming (SDP) problem by means of rank relaxation. In the context of multicast channels, robust design of CR systems was studied in [73]. In this chapter, we study different design problems for MIMO CR systems with partial knowledge of the CSI of PUs channels at the SU transmitter. We first consider general single user systems with multiple antennas at both the transmitter and receiver of the CR system in the presence of multiple PUs with multiple receive antennas each. We formulate the robust capacity maximization of such system, and we show its equivalence to a convex optimization problem that can be efficiently solved. We demonstrate how this convex for62 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI mulation can be applied to solve other related problems such as the robust minimization of the CR transmitted power subject to rate constraints. We also solve the extension of these problems to the multiple-carrier case under different constraints on the interference caused to PUs and we utilize a Lagrange dual decomposition approach to solve the resulting optimization problems. Finally, we study extensions of these design problems to scenarios with multiple SUs and multiple carriers. 4.2 System Model We consider CR communication systems that share the communication bandwidth with a number, L, of PUs which are the licensed owners of the bandwidth. For readability and smoothness of presentation we start by presenting the simplest case of a single SU, singlecarrier CR system. We then extend the model to include CR systems that utilize multiple carriers and finally, we discuss the general case of multiple SUs, multiple-carrier CR systems. The same structure of presentation will be used throughout this chapter. 4.2.1 Single SU, Single-Carrier CR Systems For the single SU, narrowband CR system depicted in Figure 4.1, we assume that the SU transmitter is equipped with Mt,SU transmit antennas and communicates with a SU receiver that is equipped with Mr,SU receive antennas. In this MIMO system, the vector of signals received at the SU receiver can be written as y = Hx + n, (4.1) 63 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 385[ * + 687[ 385[ / */ 685[ 6LQJOH 68 6LQJOH&DUULHU &5 6\VWHP 3ULPDU\ 6\VWHP Figure 4.1: Single SU, single-carrier cognitive radio system with L PUs. where H ∈ CMr,SU ×Mt,SU is the channel matrix between the SU transmitter and receiver, x is the vector of transmitted signals from the SU transmitter whose covariance matrix is E xxH = Q, and n is the i.i.d. circularly symmetric complex Gaussian noise vector at the SU receiver whose covariance matrix is E nnH = I Mr,SU 5 . The transmission from the CR system will also be received by each PU because of the shared bandwidth, and the vector of received signals at the ℓth PU receiver can be expressed as y PU,ℓ = Gℓ x, ℓ ∈ {1, · · · , L}, (4.2) where Gℓ ∈ CMr,P U ×Mt,SU is the channel matrix between the SU transmitter and the ℓth PU receiver. The received signal from the CR transmitter, y PU,ℓ , will result in added interfer5 Without loss of generality, this model can accommodate the case of non-singular noise covariance matrix Σn by pre-multiplying the channel matrix H by Σ−1/2 . n 64 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI ence to the different PUs and typically constraints that limit this interference are enforced to protect the rights of the PUs as licensed owners of the bandwidth. These interference constraints take the form Tr E y PU,ℓ y H PU,ℓ = Tr Gℓ QGH ≤ Iℓ , ℓ ℓ ∈ {1, · · · , L}, (4.3) where Iℓ is the maximum allowable interference level at the ℓth PU receiver resulting from the CR system transmission. This maximum level is often referred to as the interference temperature [33]. The interference temperature is usually set at a level that satisfies the QoS requirement of the PU. We assume that this maximum level is known at the SU transmitter. This is possible through public regulatory guidelines that govern the use of the frequency band of interest. 4.2.2 Single SU, Multiple-Carrier CR Systems In Section 4.4, we will consider a multiple-carrier extension of the above CR system. In this scenario, the PUs and the SU share a group of N parallel channels. We will denote n as the carrier index and H n as the channel matrix between the SU transmitter and the SU receiver over the nth carrier. Similarly, we define Gℓ,n to be the channel matrix between the SU transmitter and the ℓth PU receiver over the nth carrier. In this multiple-carrier system, we will consider two types of interference constraints. The first is a total interference constraint in which the sum of CR interference from all carriers is assumed to be below a maximum allowable level, N n=1 Tr Gℓ,n Qn GH ℓ,n ≤ Iℓ , ℓ ∈ {1, · · · , L}. (4.4) 65 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI The second type of constraints is a per-carrier interference constraint in which we set a maximum limit Iℓ,n on the interference from each carrier, Tr Gℓ,n Qn GH ℓ,n ≤ Iℓ,n , ℓ ∈ {1, · · · , L}, n ∈ {1, · · · , N }. (4.5) One possible choice of the maximum allowable limits Iℓ,n is such that N Iℓ,n = Iℓ . (4.6) n=1 In this case, the per-carrier interference constraint is more restrictive than the total interference constraint. However, as we will demonstrate in Section 4.4, design problems with per-carrier interference constraint can have lower complexity than the corresponding ones with a total interference constraint. 4.2.3 Multiple SUs, Multiple-Carrier CR Systems Finally, In Section 4.5, we will consider the extension of the above multiple-carrier system to the case of the multiple SUs as shown in Figure 4.2. In this scenario, we will denote k = 1, · · · , K to be the SU transmitter index, and H k,n is the the channel matrix between the k th SU transmitter and the SU receiver over the nth carrier, n = 1, · · · , N . On the other hand, Gℓ,k,n represents the channel matrix between the k th SU transmitter and the ℓth PU receiver over the nth carrier. 66 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI Q Q Q *Q 385[ / 687[ 3ULPDU\ 6\VWHP */.Q 385[ *.Q 1 +Q 685[ 687[ . +.Q 0XOWLSOH 68V 0XOWLSOH&DUULHU &5 6\VWHP Figure 4.2: Multiple SUs, multiple-carrier cognitive radio system with L PUs and N carriers. 4.2.4 Channel Uncertainty Model For readability and ease of presentation, in this section, we focus on the single SU, singlecarrier CR system (see Section 4.2.1). Nevertheless, the same model described here is directly applicable to the multiple SUs, multiple-carrier CR systems (Sections 4.2.2 and 4.2.3) on a per-SU and per-carrier basis. We make the common assumption that the channel between the SU transmitter and receiver, H, is perfectly known at the SU transmitter (cf. e.g. [69– 71]). However, we only assume partial channel knowledge of the channels Gℓ between the SU transmitter and PUs. The discrepancy in quality of channel state information is clearly motivated by the fact that SU transmitter and receiver belong to the same communication system, which provides a number of possibilities for refining channel estimation, while the SU and PUs do not cooperate to facilitate estimation of the channels between SU transmitter 67 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI and PU receivers. One possible approach to obtain an estimate of the channels Gℓ is to let the SU transmitter detect pilot symbols from the PUs’ communication if a TDD system is used; see e.g. [69, 74]. We would like to emphasize that taking channel uncertainty into account when designing for CR systems is of a great importance. Since the amount of power allowed at the SU transmitter is regulated by the amount of interference it causes the PU receiver, CR designs have to consider uncertainty in CSI to avoid causing interference at the PUs beyond the limits of the primary system. Bounded Channel Uncertainty Model In this model, the uncertainty in the channel estimation is described by the bounded region ˆ ℓ + E ℓ , Tr E ℓ Rℓ E H ≤ ǫ2 , U (ǫℓ ) = Gℓ |Gℓ = G ℓ ℓ (4.7) ˆ ℓ is the estimate of Gℓ , E ℓ is the corresponding estimation error matrix, and Rℓ is where G a Hermitian shaping matrix that describes the shape of the uncertainty region U (ǫℓ ). The model in (4.7) allows for a unified treatment for both spherical and elliptical uncertainty regions. Similar models for bounded channel uncertainties were considered in the context of single user MIMO systems (e.g. [75, 76]), and in the context of multiple-user systems (e.g. [77]). In this chapter, we will design CR systems for which a constraint on the amount of interference at each PUs is satisfied for every Gℓ ∈ U (ǫℓ ). 68 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI Statistical Channel Uncertainty Model In this model, the error matrix E ℓ is described as zero-mean with a given covariance matrix E EH ℓ E ℓ = ΣE ℓ . For this model, we will adopt an approach to the design of CR systems in which the average, over the channel uncertainty, of the SU generated interference is below a maximum allowable limit. The bounded channel uncertainty model has a special relevance to CR systems’ design since the interference limits at the PUs are usually hard and need to be strictly observed. Accordingly, we will focus, throughout this chapter, on obtaining design formulations for the first model, but we will point out how to obtain the corresponding formulations for the second model too. 4.3 Single SU CR System: Single-Carrier Case In this section, we consider the narrowband CR system with a single secondary transmitter and receiver from Section 4.2.1. 4.3.1 Capacity Maximization Subject to a Power Constraint We will start with the capacity maximization problem subject to a total transmitter power constraint and constraints to limit interference with each of the L PUs. For the bounded channel uncertainty model in (4.7), we will design CR systems such that the interference constraints are enforced for every Gℓ ∈ U (ǫℓ ). This problem can be formulated as: max Q log det I + HQH H (4.8a) 69 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI s.t. Tr (Q) ≤ P, Tr Gℓ QGH ≤ Iℓ , ℓ (4.8b) ∀ Gℓ ∈ U(ǫℓ ), ℓ ∈ {1, · · · , L}, Q ≥ 0, (4.8c) (4.8d) where P is the total allowable power for the secondary transmitter. While the problem formulation in (4.8) is convex, the inequality in (4.8c) represents L sets with infinitely many constraints, one for each Gℓ in U(ǫℓ ). However, each of these infinite sets of constraints can be exactly characterized by a single LMI constraint. This result is summarized in the following theorem. Theorem 4.1. For the bounded channel uncertainty model in (4.7), the optimization problem in (4.8) is equivalent to max Q,Sℓ ,µℓ log det I + HQH H (4.9a) s.t. Tr (Q) ≤ P, (4.9b) ˆ ℓ QG ˆ H + Tr G ˆ ℓS ℓG ˆ H + µ ℓ ǫ 2 ≤ Iℓ , Tr G ℓ ℓ ℓ S ℓ Q ≥ 0, µℓ ≥ 0, ℓ ∈ {1, · · · , L}, ℓ ∈ {1, · · · , L}, (4.9c) (4.9d) Q µℓ R ℓ − Q Q ≥ 0. (4.9e) Proof. See Appendix B. The above optimization problem is convex and can be efficiently solved using interior 70 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI point methods [78–80]. We observe from the design formulation in (4.9) that the uncertainty of the PUs’ channels results in an increased interference that is created at the PUs. This is evident from the extra interference terms on the left hand side of the constraint (4.9c) compared to the corresponding constraints in the case of perfect channel state information of the PUs’ channels. A similar observation can be made if we consider the statistical model for channel uncertainty. For this model, one approach to the design of the CR system is to limit the average interference, over the channel uncertainty, that is created at the PUs due to the existence of the SUs. That is, to set E Tr Gℓ QGH ℓ = Tr E Gℓ QGH ℓ ˆ ℓ QG ˆ H + Tr (ΣEℓ Q) ≤ Iℓ . = Tr G ℓ (4.10) Similar to the design formulation in (4.9) for the case of bounded uncertainty model, the channel uncertainty in the statistical model results in an increased interference (Tr(ΣE ℓ Q)) at the primary receiver. In the following sections, we will focus on the design formulations for the bounded uncertainty model. Corresponding formulations for the statistical uncertainty model can be obtained using a similar approach. 4.3.2 Power and Interference Minimization Subject to Rate Constraint We now demonstrate that the design approach presented in Section 4.3.1 can be applied to obtain design formulations for other related CR problems. One of these problems is the robust design of the CR transmitter in a way to minimize the transmitted power subject to 71 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI achieving a minimum rate constraint, Ctar , for the secondary receiver and subject to satisfying each PU’s maximum interference constraint for every channel Gℓ ∈ U(ǫℓ ). This problem is of a particular interest to CR systems with battery-powered mobile SU transmitters. Minimizing the transmitted power from these terminals translates directly to a longer terminal and network lifetime. Using an approach similar to the one presented in the previous section, this robust design problem is equivalent to the following convex optimization problem: min Q,Sℓ ,µℓ s.t. Tr (Q) (4.11a) log det I + HQH H ≥ Ctar , (4.11b) ˆ ℓ QG ˆ H + Tr G ˆ ℓSℓG ˆ H + µ ℓ ǫ 2 ≤ Iℓ , Tr G ℓ ℓ ℓ S ℓ Q ≥ 0, µℓ ≥ 0, ℓ ∈ {1, · · · , L}, ℓ ∈ {1, · · · , L}, (4.11c) (4.11d) Q µℓ R ℓ − Q Q ≥ 0. (4.11e) Similarly, one may design the CR transmitter in a way to minimize the total, or weighted sum, interference to the PUs subject to a minimum rate constraint. By limiting the interference generated at the different PUs to the minimum possible level, the CR system may leave some room for other CR systems to use available resource. In other cases, the frequency band the PU is using might be unlicensed or leased by the secondary network. In such a case, there is no solid interference threshold that needs to be strictly preserved and causing the lowest interference is mutually beneficial. The formulation for this design problem can be 72 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI obtained by extending the design variables in (4.11) to include Iℓ and replacing the objective in (4.11a) by the (weighted) sum of Iℓ . 4.4 Single SU CR System: Multiple-Carrier Case In the previous section, we considered a CR system with a single SU transmitter and receiver that share the same narrowband channel with L PUs. In this section, we will consider a communications scenario in which the SU and PUs share a number of parallel channels such as in multiple-carrier communication systems. 4.4.1 Total Interference Constraint Given the channel uncertainty model in (4.7) and assuming a total interference constraint (cf. (4.4)) for each PU, the robust sum rate maximization problem can be formulated as N max Qn ,Sℓ,n ,µℓ,n log det I + H n Qn H H n (4.12a) Tr (Qn ) ≤ P, (4.12b) n=1 N s.t. n=1 N n=1 ˆ ℓ,n Qn G ˆ H + Tr G ˆ ℓ,n S ℓ,n G ˆ H + µℓ,n ǫ2 ≤ Iℓ , Tr G ℓ,n ℓ,n ℓ,n S ℓ,n Aℓ,n (Qn , S ℓ,n , µℓ,n ) = Qn µℓ,n ≥ 0, ∀ℓ, ∀n, Qn µℓ,n Rℓ,n − Qn ≥ 0, ∀ℓ, ∀n ∀ℓ, (4.12c) (4.12d) (4.12e) 73 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI Qn ≥ 0, ∀n. (4.12f) Similar to the design formulation in (4.9), the optimization problem in (4.12) is convex and can be solved efficiently. An alternative approach to solving (4.12) is through deriving the Lagrange dual of the robust optimization problem in (4.12). The Lagrange dual decomposition approach has been used extensively in the literature to solve different resource allocation and optimization problems [81–85]. As we demonstrate below, this approach results in decomposing the optimization problem in (4.12) into N independent and similar sub-problems that can be solved in parallel. To obtain the Lagrange dual problem of (4.12) we will first define the following convex regions Bn = {(Qn , S ℓ,n , µℓ,n ) | Qn ≥ 0, µℓ,n ≥ 0, Aℓ,n (Qn , S ℓ,n , µℓ,n ) ≥ 0, ∀ℓ ∈ {1, · · · , L}} . (4.13) Using the above definition, the Lagrange dual function of the primal problem in (4.12) can be written as N g(λ, η) = max {Qn ,Sℓ,n , n=1 µℓ,n }∈Bn log det I + H n Qn H H n −λ L − N ηℓ ℓ=1 n=1 Tr (Qn ) − P ˆ ℓ,n Qn G ˆ H + Tr G ˆ ℓ,n S ℓ,n G ˆ H + µℓ,n ǫ2 − Iℓ Tr G ℓ,n ℓ,n ℓ,n η ℓ Iℓ , gn (λ, η) + λP + n=1 n=1 L N = N (4.14) ℓ=1 74 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI where the functions gn (λ, η) are defined as gn (λ, η) = max {Qn ,Sℓ,n ,µℓ,n }∈Bn log det I + H n Qn H H n − λTr (Qn ) L − ηℓ ˆ ℓ,n Qn G ˆ H + Tr G ˆ ℓ,n S ℓ,n G ˆ H + µℓ,n ǫ2 . Tr G ℓ,n ℓ,n ℓ,n ℓ=1 (4.15) For a given λ and η, the functions gn (λ, η) are efficiently evaluated, since each one represents a convex optimization problem. Furthermore, they are independent and can be simultaneously evaluated. Finally, the dual problem can be written as min λ,η g(λ, η) s.t. λ ≥ 0, η ≥ 0. (4.16) The dual problem in (4.16) can be efficiently solved using gradient based approaches such as the ellipsoid method [81]. 4.4.2 Per-carrier Interference Constraints In this section, we study the robust design of the CR system under per-carrier interference constraints. In this scenario, the interference generated by the secondary transmission over each carrier should be allowed a maximum level for each PU. Under the assumption of perfect channel knowledge of the PUs’ channels, the design of the CR system was considered in [69]. The design formulation for the robust design problem in (4.12) replaces each PU’s total 75 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI interference constraint in (4.12c) by the N sets of per-carrier interference constraints ˆ ℓ,n Qn G ˆ H + Tr G ˆ ℓ,n S ℓ,n G ˆ H + µℓ,n ǫ2 ≤ Iℓ,n , Tr G ℓ,n ℓ,n ℓ,n ∀ℓ, ∀n. (4.17) While design formulation with the per-carrier interference constraints result is a larger number of constraints in the primal problem, the dual problem can be significantly simplified. To see this, let us define the convex regions Cn Cn = (Qn , S ℓ,n , µℓ,n ) | Qn ≥ 0, µℓ,n ≥ 0, Aℓ,n (Qn , S ℓ,n , µℓ,n ) ≥ 0, ˆ ℓ,n Qn G ˆ H + Tr G ˆ ℓ,n S ℓ,n G ˆ H + µℓ,n ǫ2 ≤ Iℓ,n , ℓ ∈ {1, · · · , L} . (4.18) Tr G ℓ,n ℓ,n ℓ,n The Lagrange dual function of the robust design problem with per-carrier interference constraints becomes N g(λ) = max {Qn ,Sn ,µℓ,n }∈Cn n=1 log det I + H n Qn H H n −λ N n=1 Tr (Qn ) − P N gn (λ) + λP, = (4.19) n=1 where gn (λ) = max Qn ,Sℓ,n ,µℓ,n ∈Cn log det I + H n Qn H H n − λTr (Qn ) . (4.20) The dual problem can then be written as min λ g(λ) s.t. λ ≥ 0. (4.21) 76 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI Compared to (4.16), the problem in (4.21) is a single variable optimization problem and since g(λ) is convex in λ, bisection search over λ can be used to obtain the optimal solution [78, page 249]. 4.5 Multiple SUs CR System: Multiple-Carrier Case Finally, we proceed to the general case in which we consider a CR system with multiple SUs in an uplink multiple-carrier communication scenario. In order to avoid interference between the SUs themselves, we assume that each carrier is assigned, at most, to one SU at any time. That is, if the carrier of index n = 1, · · · , N is assigned to user kˆ (Qk,n ˆ = 0), then Qk,n = 0 ˆ Given a set of maximum allowable powers P = {P1 , · · · , PK } for each SU for every k = k. k = 1, · · · , K, the joint problem of carrier assignment and robust resource allocation for sum rate maximization under a total interference constraint can be formulated as K N max Qk,n ,Sℓ,k,n , µℓ,k,n log det I + H k,n Qk,n H H k,n , (4.22a) k=1 n=1 N s.t. Tr Qk,n ≤ Pk , n=1 K N k=1 n=1 ∀k, (4.22b) 2 ˆ ℓ,k,n Qk,n G ˆH ˆ ˆH Tr G ℓ,k,n + Tr Gℓ,k,n S ℓ,k,n Gℓ,k,n + µℓ,k,n ǫℓ,k,n ≤ Iℓ , ∀ℓ, (4.22c) S ℓ,k,n Aℓ,k,n (Qk,n , S ℓ,k,n , µℓ,k,n ) = Qk,n Qk,n µℓ,k,n Rℓ,k,n − Qk,n ≥ 0, µℓ,k,n ≥ 0, 77 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI ∀ ℓ, ∀ k, ∀ n, Qk,n ≥ 0, ∀ k, ∀ n, ˆ if Qk,n ˆ = 0 then Qk,n = 0, S ℓ,k,n = 0, µℓ,k,n = 0 ∀ k = k, ∀ ℓ, ∀ n. (4.22d) (4.22e) (4.22f) Alternative formulations using per-carrier interference constraints, per-user interference constraints, or both can be easily derived and the solution to the new formulations should, in general, be less complex. Problem (4.22) is no longer convex due to the exclusivity constraint in (4.22f). Thus, the primal problem can no longer be solved using convex optimization tools, and an exhaustive search over all possible carrier assignments is needed to obtain a globally optimal solution. However, this approach can be prohibitively complex, especially when the number of carriers, N , is large. One approach to overcome this prohibitive complexity is to use a Lagrange dual decomposition approach similar to the one presented in Section 4.4. To briefly demonstrate how the Lagrange dual approach can be used to reduce the complexity associated with the non-convex constraint in (4.22f), we will first define the following non-convex sets Dn = (Qk,n , S ℓ,k,n , µℓ,k,n ) | Qk,n ≥ 0, µℓ,k,n ≥ 0, Aℓ,k,n (Qk,n , S ℓ,k,n , µℓ,k,n ) ≥ 0, ˆ if Qk,n ˆ = 0 then Qk,n = 0 ∀k = k, ℓ ∈ {1, · · · , L}, k ∈ {1, · · · , K} . (4.23) Using this definition, the Lagrange dual function can be written in the following carrier 78 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI separable form: L K N n=1 η ℓ Iℓ , λk Pk + gn (λ, η) + g(λ, η) = k=1 (4.24) ℓ=1 where K gn (λ, η) = max {Qk,n ,Sℓ,k,n , k=1 µℓ,k,n }∈Dn log det I + H k,n Qk,n H H k,n − λk Tr Qk,n L − 2 ˆ ℓ,k,n Qk,n G ˆH ˆ ˆH ηℓ Tr G ℓ,k,n + Tr Gℓ,k,n S ℓ,k,n Gℓ,k,n + µℓ,k,n ǫℓ,k,n . ℓ=1 (4.25) For any given value of (λ, η), the evaluation of gn (λ, η) requires solving the optimization problem in (4.25) over the domain defined by the sets Dn . Because of the exclusivity constraint (cf. (4.22f)), calculating the maximum of the summation in (4.25) corresponds to selecting the user that maximizes the terms inside the summation. Hence, the solution for the maximization in (4.25) can be obtained through solving K independent subproblems, one for each user. Now, the dual problem of (4.22) can be expressed as min λ,η g(λ, η) s.t. λ ≥ 0, η ≥ 0, (4.26) and similar to problem (4.16), it can be solved using gradient based algorithms such as the ellipsoid method. It is worth mentioning that while the primal problem in the single user multiple-carrier case in (4.12) is convex, the multiple-user problem with the exclusivity constraint in (4.22) 79 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI is not, and generally the duality gap is non-zero6 . Thus, the solution obtained by using the Lagrange dual decomposition approach is an upper bound for the optimal solution of (4.22). Nevertheless, the approach can significantly reduce the complexity of the problem in (4.22). It is also worth mentioning that the design problem of a downlink robust CR system with multiple-carriers can be solved in an analogous way after replacing the peruser power constraints in (4.22b) for the uplink system by the single power constraint K k=1 N n=1 Tr Qk,n ≤ P . In this case, the vector of dual variables λ in the uplink dual problem reduces to a single variable. This, in turn, helps reduce the complexity of finding the optimal Lagrange multipliers for the dual optimization problem. 4.6 Simulation Results In this section we present some numerical results to evaluate the performance of the proposed algorithms. We consider CR systems in which SU transmitters and receivers are equipped with two antennas each, Mt,SU = Mr,SU = 2. Similarly, each PU receiver is equipped with two antennas, Mr,P U = 2. The coefficients of the channel H between any SU transmitter and its corresponding receiver are modeled as i.i.d. circularly symmetric complex Gaussian random variables with unit variance. The coefficients of Gℓ are modeled similarly with a variance equal to7 10−3 . Average plots are generated using Monte Carlo simulations over 5000 channel sets. 6 For the case of single antenna users in the non-CR context, it was shown that the duality gap vanishes as N grows [81, 84–86]. 7 The choice of channels variances represents a typical scenario in which the PUs are farther from the SU transmitter than the SU receiver. Nevertheless, absolute values are of little significance for the ensuing performance evaluation, as a change to the variance of the coefficients of Gℓ would be compensated by a change of Iℓ . 80 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 12 11 10 Average Capacity (bps/Hz) 9 8 7 6 5 4 3 ε=0 ε = 0.02 ε = 0.04 ε = 0.06 2 1 −20 −18 −16 −14 −12 −10 −8 Interference Threshold, I (dB) −6 −4 −2 0 Figure 4.3: Average of the maximum link capacity of a single-carrier, single SU CR system in the presence of a single PU versus the maximum allowable interference at the PU for different values of ǫ. Maximum allowable power at the SU transmitter is P = 20 dB. 4.6.1 Single SU CR System Capacity maximization for a single-carrier CR system We first consider a CR system with a single SU and a single PU (L = 1), and we study the robust capacity maximization problem in (4.8). In Figure 4.3, we plot the average capacity of the CR system versus the maximum allowable level of interference at the PU for different levels of bounded channel uncertainty following the model in (4.7). We also compare the 81 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI proposed design with the case of perfect knowledge of the channel G (i.e., ǫ = 0) which was studied in [69]. As one might expect, when I increases, the SU transmitter is allowed to transmit more power and the average capacity increases. When I reaches a sufficiently large level, the transmitted power (Tr(Q)) reaches the maximum level P and the capacity remains constant. This is true for all levels of channel uncertainty and can also be observed in Figure 4.4 in which we plot the average transmitted power (Tr(Q)) versus the maximum allowable interference I. In order to show how important it is to take the channel uncertainty into account when designing for CR systems, let us assume that the design process took place under the assumption of perfect CSI at the SU transmitter while in fact there was some uncertainty associated with the CSI used in the design problem. Figure 4.5 plots the average of the relative interference threshold violation ((Tr(GQGH ) − I)+ /I) versus the level of uncertainty associated with the CSI that was not taken into account in the design process. We observe that the channel uncertainty, when not considered in the design process, leads to frequent violations of the interference constraints. Hence, design formulations and solutions as presented in this chapter are needed to avoid harmful interference in practical CR systems. Sum rate maximization for a multiple-carrier CR system In this experiment, we consider a single SU CR system with N = 8 carriers and a single PU (L = 1) with a total interference constraint (cf. (4.4)). In Figure 4.6, we plot the average of the maximum sum rate versus I, and in Figure 4.7 we plot the average of the total transmitted power over all carriers ( N n=1 Tr(Qn )) versus I for different values of ǫ in (4.7). By comparing Figures 4.6 and 4.7, we observe that there exists an interval over which 82 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 22 20 Average Transmitted Power, Tr(Q) (dB) 18 16 14 12 10 8 6 4 ε=0 ε = 0.02 ε = 0.04 ε = 0.06 2 0 −20 −18 −16 −14 −12 −10 −8 −6 Interference Threshold, I (dB) −4 −2 0 Figure 4.4: Average transmitted power Tr(Q) from the SU when optimizing for the link capacity of a single-carrier, single SU CR system in the presence of a single PU versus the maximum allowable interference at the PU for different values of ǫ. Maximum allowable power at the SU transmitter is P = 20 dB. the average sum rate increases with I even though the average total transmitted power has already reached its maximum limit P (compare Figures 4.6 and 4.7 for I ∈ [−7, −4] dB for ǫ = 0.02 and for I ∈ [−14, −6] dB for ǫ = 0). This can be attributed to the ability of the joint design problem to allocate resources over different carriers to satisfy the total interference constraint. 83 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 1 Average Relative Interference Threshold Violation (Violation / I) 10 I = −9 dB I = −7 dB I = −5 dB I = −3 dB 0 10 −1 10 −2 10 −3 10 −4 10 −5 10 −3 10 −2 10 Level of Uncertainty, ǫ −1 10 Figure 4.5: Average of the relative interference threshold violation ((Tr(GQGH ) − I)+ /I) versus the level of uncertainty associated with the CSI that was not taken into account in the design process. A single-carrier, single SU, CR system is considered in the presence of a single PU with a maximum allowable power at the SU transmitter of P = 20 dB. In Figure 4.8, we study the effect of increasing the number of PUs on the robust sum rate maximization problem in (4.12). We consider a scenario in which all PUs have the same maximum allowable interference Iℓ = I, ℓ = 1, · · · , L, and we plot the average of the 84 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 55 50 45 Average Sum Rate (bps/Hz) 40 35 30 25 20 15 10 ε=0 ε = 0.02 ε = 0.04 ε = 0.06 5 0 −20 −18 −16 −14 −12 −10 −8 Interference Threshold, I (dB) −6 −4 −2 0 Figure 4.6: Average of the maximum sum rate of a multiple-carrier (N = 8), single SU CR system in the presence of a single PU versus the maximum allowable interference I at the PU for different values of ǫ. Maximum allowable power at the SU transmitter is P = 20 dB. maximum sum rate versus the number of PUs, L, for different values of ǫ. Intuitively, as the number of PUs increases, interference constraints increase, the feasible region of the design problem in (4.12) shrinks and consequently the maximum sum rate decreases. 85 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 22 20 n Tr(Qn ) (dB) 18 16 14 Aveareg Total Power, 12 10 8 6 4 ε=0 ε = 0.02 ε = 0.04 ε = 0.06 2 0 −20 −18 −16 −14 −12 −10 −8 Interference Threshold, I (dB) −6 −4 −2 0 Figure 4.7: Average of the total transmitted power n Tr(Q) from the SU when optimizing for the link capacity of a multiple-carrier (N = 8), single SU CR system in the presence of a single PU versus the maximum allowable interference I at the PU for different values of ǫ. Maximum allowable power at the SU transmitter is P = 20 dB. Transmit power minimization for a multiple-carrier CR system In this experiment, we consider the robust power minimization problem in the multiplecarrier communication scenario considered above (extension of the robust design formulation in (4.11) to the multiple-carrier case). For this design problem, the target sum rate is 10 bps/Hz, and we study the feasibility of this robust design formulation for different levels 86 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 50 ε=0 ε = 0.02 ε = 0.04 ε = 0.06 45 Average Sum Rate (bps/Hz) 40 35 30 25 20 15 1 2 3 4 5 Number of PUs 6 7 8 Figure 4.8: Average of the maximum sum rate of a multiple-carrier (N = 8), single SU CR system versus the number of PUs for a fixed maximum allowable interference I = −10 dB at each PU for different values of ǫ. Maximum allowable power at the SU transmitter is P = 20 dB. of channel uncertainty, ǫ, in (4.7). The problem becomes infeasible if no set {Qn } can be found that achieves the target sum rate while satisfying the interference constraints for every channel realization Gℓ,n within the bounded U(ǫ). In this case, we assume an outage event ˆ ℓ,n } and used them to has occurred. We generated 13,000 random sets of channels {H n , G plot the probability of outage versus I in Figure 4.9. As expected, the probability of outage decreases as I increases for a fixed ǫ, and increases with ǫ for a given value of I. To capture 87 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 0 10 −1 Outage Probability 10 −2 10 −3 10 −4 10 ε=0 ε = 0.02 ε = 0.04 −5 10 −34 −32 −30 −28 −26 −24 −22 −20 Interference Threshold, I (dB) −18 −16 −14 −12 Figure 4.9: Outage probability of the robust power minimization for a multiple-carrier (N = 8), single SU CR system in the presence of a single PU versus the maximum allowable interference I at the PU for different values of ǫ. The target sum rate is 10 bps/Hz. the average sum power versus I relationship, we selected all feasible sets of channels for which all the compared designs with different ǫ were feasible at I = −19 dB, and for these 1895 selected sets we plotted the average power versus I. It can be seen from Figure 4.10 that a higher channel uncertainty level mandates additional transmit power to achieve a target rate in the CR system since the robust design problem can be viewed as a design problem with perfect channel information with more restrictive interference constraints. 88 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 6 ε=0 ε = 0.02 ε = 0.04 5.8 n Tr(Qn ) (dB) 5.6 5.4 Aveareg Total Power, 5.2 5 4.8 4.6 4.4 4.2 −30 −28 −26 −24 −22 Interference Threshold, I (dB) −20 −18 −16 Figure 4.10: Average minimum transmit power from the SU of a multiple-carrier (N = 8), single SU CR system in the presence of a single PU versus the maximum allowable interference I at the PU for different values of ǫ. The target sum rate is 10 bps/Hz. 4.6.2 Multiple SUs CR System Finally, we consider a CR system with two SUs (K = 2), four carriers (N = 4), and a single PU (L = 1) in a system setup similar to the one presented in Figure 4.2. In Figure 4.11, we plot the average of the maximum sum rate against the maximum interference I. We compare the maximum rate obtained by the solution of the dual problem in (4.26) to the 89 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 25 Average Sum Rate (bps/Hz) 20 15 10 5 Lagrange Dual (ε = 0.02) Lagrange Dual (ε = 0.04) Exhaustive Search (ε = 0.02) Exhaustive Search (ε = 0.04) 0 −20 −18 −16 −14 −12 −10 −8 Interference Threshld, I (dB) −6 −4 −2 0 Figure 4.11: Average of the maximum sum rate obtained from solving the primal and dual optimization problems of a multiple-carrier (N = 4), Multiple SUs (K = 2) CR system in the presence of a single PU versus the maximum allowable interference I at the PU for different values of ǫ. Maximum allowable power at each SU transmitter is P = 17 dB. one obtained by solving the primal problem in (4.22) by employing an exhaustive search over all possible combinations of carrier allocation amongst the two SUs. It is clear from Figure 4.11 that even for a CR system with as little as N = 4 carriers, the difference in sum rate is almost negligible (i.e. duality gap is almost zero). This proves the effectiveness and the usability of the proposed dual technique for practical CR systems design. 90 Chapter 4. Designs for MIMO Cognitive Radio Systems with Imperfect CSI 4.7 Conclusions In this chapter, we introduced new algorithms for robust resource optimization in MIMO CR systems. We studied several optimization problems and provided solutions based on an LMI transformation that facilitated efficient treatment of the imperfect CSI of the PUs’ channels at the SUs’ transmitters. Systems with multiple MIMO PUs and multiple MIMO SUs utilizing multiple frequency bands were considered and efficient solutions were provided for each case. We presented numerical results that demonstrated the effectiveness and robustness of the proposed algorithms. We also demonstrated the detrimental effect of designing for CR systems without taking channel uncertainties into account on the level of interference at the PUs. 91 Chapter 5 Admission and Eviction Control in OFDMA Cognitive Radio Systems 5.1 Introduction In Chapter 4, the availability of partial CSI of the PU links at the CR transmitter enabled us to efficiently utilize the available resources without causing any harmful interference at the PU receiver. In this chapter we assume that such CSI information is not available and only the ON/OFF status of the PU channel, i.e. the channel being Free or Busy, is available at the CR transmitter through active sensing. Given this PU activity model, we study the problems of admission and eviction control in CR networks subject to fluctuations in the set of available frequency resources due to PU activity. Similar to Chapter 4, we choose OFDMA for transmission between a CR base station and the set of SUs admitted for service. OFDMA has been recognized to be one of the prime candidates to enable CR communications due to the flexible nature of carrier assignment. Carriers that are occupied by the PUs can be identified and excluded when transmitting to SU receivers. Thus, resource allocation techniques similar to the ones used in multiple-user OFDMA [84, 85, 87] can be used to allocate the available carriers to different SUs in an 92 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems exclusive manner (i.e. each carrier is assigned to one SU) in the CR context. Considering the rate maximization under a total power constraint problem presented in [84, 85, 87], the optimization problem can be easily identified to be non-convex due to the carrier exclusivity condition. In [87], this constraint was relaxed to allow for time sharing between different users on the same carrier. Thus the problem becomes convex and a solution can be found using standard convex optimization tools. Nonetheless, the problem remains complex due to the large number of optimization variables especially when the number of available carriers is high. On the other hand, the solutions in [84, 85] utilizing a Lagrange dual decomposition approach are particularly apt, as the resource allocation problem can be divided into several, per-carrier, sub-problems that can be solved efficiently in parallel. Furthermore, it was shown in [81, 84] how the duality gap between the primal and dual problems approaches zero as the number of carriers increases. If spectrum overlap with the PUs is allowed by constraining the amount of interference experienced by the PUs due to the CR transmission, the techniques from [84, 85, 87] can be extended as shown in [69, 70]. Looking back at the works in [69, 70, 84, 85, 87], we can see that only Best Effort (BE) users were considered with no guarantees on the rate achieved by each user. However, in most Real Time (RT) applications, a constant bit rate is necessary to achieve a satisfactory user experience. For this reason, extensions to include per-user rate constraints were studied in [88, 89]. We note that introducing the new rate constraints to the problem of rate maximization could deem the problem infeasible due to the limited amount of power the system is allowed to utilize. The authors in [88, 89] assumed that the problem is always feasible, although recognizing that this might not always be true. We argue that the possibility of overloading the system at some point necessitates the introduction of admission and evic93 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems tion control mechanisms that deal with the two fundamental tasks of i) accepting/rejecting requests by new users in a way that limits the probability of calls being dropped during the lifetime of the user’s session and ii) dealing with the problem of infeasibility when it occurs due to changes in system resources dominated by unexpected PU activity on some of the previously available carriers. The authors in [90] recognized the possible infeasibility problem and proposed to fairly allocate the available resources to all the users when infeasibility occurs. This way, however, the rate constraint of almost every user in the system gets violated. Furthermore, [90] falls short of providing an admission control mechanism that limits such a disliked possibility. Admission and eviction control for CR systems was the subject of several recent studies [91, 92]. In [91], a fractional guard channel reservation scheme was used to control the balance between the blocking rate of newly arriving users and the dropping rate of the already admitted ones. The authors used a continuous time Markov chain model to describe the dynamics of the system, and by solving the global balance equation they were able to obtain the stationary probabilities of blocking and dropping a user. In [92], the authors proposed the use of a semi-Markov decision process to solve a profit maximization problem. By assigning a cost/revenue to each action of interest (admission, blocking, eviction, and completion), they were able to come up with an admission/eviction policy that maximizes the revenue of the system. In both [91] and [92], rate requirements by users were translated directly into bandwidth requirements. That is, there is a deterministic link between the amount of bandwidth currently available and the ability to admit or the necessity to evict a user at any point in time. While such an assumption was necessary for [91, 92] to apply tools from Markov decision process theory, it ignores the current link conditions in the CR 94 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems system, which limits the practicality of the resulting schemes. In this chapter, we tackle the problem of admission and eviction control in a CR environment while taking into account the important effect of the instantaneous channel conditions of users on the admission, resource optimization, and eviction dynamics of the system. We propose the use of a Resource Buffer Zone (RBZ) to limit the number of RT call drops due to the fluctuating nature of the available frequency resource. Unlike the RBZ described in [91], the buffer zone we install is only used at the time of admission of a new RT SU and can be freely utilized by the system afterwards to achieve the highest possible system throughput. We propose three different ways to set up such a buffer zone, two of which use statically allocated RBZs consisting of reserved power levels or frequency carriers that get held back at the time of admission. The third technique predicts the size of the RBZ based on current system dynamics. We also tackle the problem of user removal that is necessary to treat any infeasibility situation the system could face due to the dynamic nature of the available set of resources resulting from independent PU activity. We present three algorithms for user removal and discuss their advantages and disadvantages. Results show how the proposed admission control techniques can be efficiently used to reduce the drop rate of admitted RT SUs. The results also show how we can resolve any system infeasibility using user removal algorithms that have low complexity and high efficiency at the same time. 5.2 System Model We consider a multiple-user downlink CR system, as schematically illustrated in Figure 5.1, that shares a frequency bandwidth with a primary system, which is the licensed owner of 95 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems 68 68 68 &5 %6 3ULPDU\ 1HWZRUN &RJQLWLYH 5DGLR 1HWZRUN Figure 5.1: Multiple-user downlink cognitive radio system. the spectrum. The CR system can utilize any portion of the bandwidth as long as it is not actively used by the primary system. The bandwidth of interest is B Hz and is divided at the CR Base Station (BS) into N OFDMA sub-bands. 5.2.1 Signaling Model OFDMA is utilized at the CR BS for signal transmission to multiple SUs in which an exclusive carrier allocation is assumed to prevent interference between different SUs. The received signal at the k th SU on the nth carrier can be written as yk,n = hk,n xk,n + vk,n , (5.1) 96 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems where hk,n , xk,n and vk,n are the channel gain, transmitted signal and the zero mean unit variance i.i.d. circularly symmetric complex Gaussian noise associated with the k th SU and nth carrier, respectively. We define pk,n and rk,n as the transmit power and rate associated with the nth carrier and the k th SU, respectively. Tight bounds on pk,n as a function of the BER requirement, and carrier loading, rk,n , are available in the literature for uncoded M-ary Quadrature Amplitude Modulation (QAM) signals transmitted over Additive White Gaussian Noise (AWGN) channels, as in (5.1). For example, in [64, 93] pk,n is tightly approximated by pk,n ≈ βk,n (2rk,n − 1) , (5.2) where βk,n > 0 is a function of |hk,n | and the BER requirement. We observe that the approximation of pk,n is convex8 , increasing in rk,n , and that pk,n = 0 when rk,n = 0. The convexity of the approximation in (5.2) is of great importance as it facilitates the use of efficient convex optimization techniques that are necessary to solve the feasibility and resource optimization problems discussed in Sections 5.3 and 5.4, respectively. 5.2.2 PU Activity Model On the primary system’s side, the same bandwidth of interest, B Hz, can support up to L PUs with a bandwidth of B/L Hz each. It is widely accepted that the activity on each one of the PU bands is independent and can be modeled using a two state Markov Chain (MC) 8 For real-valued rates, rk,n , convexity of pk,n is well defined. When rk,n belongs to a discrete set of rates, convexity of the discontinuous staircase function means that the lines connecting consecutive corners of the staircase constitute a convex continuous function [85]. 97 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems [90, 94, 95]. Once a PU band is busy, it becomes free in the next time slot with probability pb→f . Otherwise, the PU band remains busy with probability 1 − pb→f . On the other hand, once the PU band is in the free state, it becomes busy or stays free in the next time slot with probabilities pf→b and 1 − pf→b , respectively. It can be easily shown that this model is equivalent to a PU activity model that has independent exponentially distributed busy and free times similar to the one adopted in [92]. The CR BS continuously senses the spectrum of interest and only those carriers that carry no primary communications can be utilized for secondary transmission. At any time instance t, the set of free carriers is Nfree (t). The cardinality of the set of free carriers, Nfree (t), evolves according to a fully connected MC in which each state represents the number of free PU bands that experience no active PU transmission in the time slot of interest. Thus, while in state i ∈ 0, · · · , L at time t, the MC indicates the availability of Nfree (t) = iN/L free carriers that can be utilized for CR transmission. The state transition matrix P can be obtained using [90] L pi,j = ℓ=0 L−i i ℓ pf→b (1 − pf→b )i−ℓ pℓ−i+j (1 − pb→f )L−j−ℓ , ℓ ℓ − i + j b→f (5.3) where pi,j is the element from the ith row and j th column of P that represents the transition probability from the ith state to the j th state. 5.2.3 SU Arrival Process We consider two types of SUs based on their rate requirements. Non Real-Time (NRT) SUs have no rate requirements and are considered for BE service. The second set of users is the 98 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems RT users that have a minimum rate requirement that is necessary to achieve a satisfactory user experience. We assume that the SU arrival to the CR system follows a Poisson process with rates λRT and λNRT for RT and NRT traffic, respectively. We also assume that the call duration of each RT and NRT user, k, is exponentially distributed with an average of 1/µk . These assumptions are common in the literature for data and voice traffic over wireless links and are not far from reality (e.g. [91, 92, 96, 97]). Upon their arrival, NRT SUs are always admitted and they receive as much resources as the system allows in a best effort manner. On the other hand, RT SUs are admitted only when there are enough system resources, including power and frequency carriers, to support their minimum rate requirement, assuming that they have higher priority than NRT SUs. Specifically, NRT SUs receive little or no resources when the system goes through a high load of RT traffic. The preemptive priority the PUs have over the shared frequency resource makes the CR system vulnerable to infeasibility situations in which the system can no longer support the set of already admitted RT SUs without violating the maximum allowable level of transmission power (Pmax ). Thus, it is the task of an admission control entity to guarantee, to a certain level of accuracy, the availability of enough system resources to support the admitted set of RT SUs for the entire length of their call durations. It is also the task of a user removal algorithm to resolve such system infeasibilities once they occur. In the following two sections we address both of these problems, admission control and user removal, in detail. Without loss of generality, we assume that all system events, including SU arrival, SU departure, and PU activity changes are discrete time events that are synchronized based on a unified system clock. This is a practical assumption since transmission decisions are often 99 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems made on a frame-by-frame basis. 5.3 Admission Control Upon the arrival of a new RT SU, an admission control mechanism is invoked to decide on whether to admit or reject the new request. The decision is made based on the availability of enough resources and the ability to maintain these resources over the course of the connection’s lifetime. The two main goals of any admission control system are to i) minimize the number of users that get dropped before their actual session end time and to ii) minimize the number of users being blocked for lack of resources. The set of carriers that are free from any PU activity, Nfree (t), continuously changes according to the MC model discussed in Section 5.2.2. Thus, an already admitted RT SU can possibly lose service if the available set of free carriers can no longer support all admitted RT SUs without violating the maximum transmit power threshold (Pmax ). The user drop rate can be reduced by installing an RBZ consisting of unallocated system resources to deal with any expected variations over the life-time of the user’s session. Obviously, the larger the RBZ is the lower the drop rate. On the other hand, a too large RBZ would underutilize the system and prevent users from being admitted while resources are setting idle. The concept of an RBZ has been used extensively in the cellular networks context [98, 99]. In cellular networks, dropping an ongoing call is perceived to be more annoying than blocking a new call request. Thus, some system channels are reserved to serve calls handing over from neighboring cells. Similarly, we propose two types of admission control policies based on a static RBZ that is composed of portions of one of the available resources: frequency carriers 100 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems or transmission power. In the third proposed admission control technique, we use a pragmatic approach towards estimating the size of the RBZ, in terms of number of frequency carriers, dynamically such that a pre-defined level of protection against RT SU call drops is achieved. 5.3.1 Fixed Power Threshold In this scheme, a fixed portion of the available transmission power will be held back when a user is admitted. In other words, upon the arrival of a new RT SU with a minimum rate constraint, the following optimization problem is solved (for clarity, we drop the time index t) pk,n min (5.4a) + n∈N free k∈KRT s.t. n∈Nfree rk,n ≥ Rk , + ∀k ∈ KRT , if pk,n ˆ = 0 then pk,n = 0, + ∀ k = kˆ ∈ KRT , ∀ n ∈ Nfree , (5.4b) (5.4c) + where KRT is the set of the already admitted RT SUs plus the newly arriving SU seeking admission and Rk is the minimum rate requirement of the k th SU. Assuming that the sum power constraint at the CR BS is Pmax , the new user is admitted to the system if and only if the total amount of power required to fulfill the rate requirements of all RT SUs is lower than a predetermined threshold. That is, if pk,n > αPmax , (5.5) + n∈N free k∈KRT 101 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems the new user is blocked for lack of resources. The factor α ∈ [0, 1] limits the maximum allowable power level at the BS at admission time. This way, the system is allowed to “breathe”, i.e. even if the set of available resources change, up to a certain limit, after the user becomes admitted, the call is not dropped and the required rate is maintained. The lower α is, the higher the probability the call is maintained for the whole call duration without interruption. On the other hand, a low α increases the probability of rejecting new requests from RT users. One of the most efficient ways to solve the problem in (5.4) is to solve the Lagrange dual of the problem. The Lagrangian of the optimization problem in (5.4) can be written as + KRT + KRT Nfree L(pk,n , rk,n , η) = k=1 n=1 pk,n − k=1 ηk Nfree n=1 rk,n − Rk , (5.6) where ηk is the Lagrange multiplier associated with the k th rate constraint. The Lagrange dual problem can then be written as max g(η) (5.7a) + s.t. ηk ≥ 0 ∀k ∈ 1, 2, · · · , KRT , (5.7b) where g(η) is the Lagrangian dual function such that g(η) = p min L(pk,n , rk,n , η). ,r k,n (5.8) k,n The minimization in (5.8) can be decomposed into Nfree independent problems which can be solved in parallel in closed form. The reader is referred to [84] and [85] for a detailed 102 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems analysis of the solution. 5.3.2 Fixed Carrier Release The other available resource dimension that can be employed to implement an RBZ in OFDMA systems is frequency. We then propose, in the second scheme, to forge an RBZ by voluntarily surrendering a fixed number, C, of the available carriers for admission purposes only. The carriers to surrender are picked randomly and the system is then checked for feasibility as in (5.4), but with a reduced set of available carriers Nˆfree . If the problem turns feasible, i.e. + k∈KRT ˆfree n∈N pk,n ≤ Pmax , the new user is admitted and the full list of available carriers Nfree is used for resource allocation. 5.3.3 Predictive Carrier Release The previous two protection schemes are static in the sense that the size of the RBZ is fixed and needs to be chosen beforehand. This requires the availability of actual or simulated system measurements for the system administrator to be able to set the corresponding system parameters, α and C, accordingly. Alternatively, in this scheme, we try to predict the size of the RBZ, in term of number of carriers C, dynamically such that the system achieves a certain level of protection against call drops of RT SUs. Towards that, we assume that a user drop happens mainly due to a decline in the number of carriers available for secondary transmission after the user was admitted. Although a user drop could also happen when the total number of available carriers remains the same or even increases if the set of available carriers is different from the one at admission time, we ignore 103 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems this possibility since we assume that i) the number of available carriers is usually large (64 2048), ii) the channels are frequency selective across carriers, i.e. there is sufficient frequency diversity across carriers, iii) the diversity created by the presence of multiple users reduces the effect of carrier shuffling due to PU activity, iv) and most importantly, unlike [91, 92], the resource allocation process, presented in Section 5.4 below, is dynamic and will produce a new carrier allocation map that achieves the best possible performance. In general, a user that is admissible at time T0 is only admitted if it would still be admissible at all time slots, T0 < t ≤ T0 + Tmax , in the foreseen future with some probability pprotect . Thus, based on the argument presented above, we need to determine by how many carriers the number of free carriers at time T0 , Nfree (T0 ), is expected to drop within a time interval of size Tmax given an accuracy of prediction that is greater or equal to pprotect . The RT SU dropping rate, pdrop , is directly related to the prediction accuracy, pprotect , only when the load of the system is high enough to keep the system full at most of the times. It is at that system environment when the existence of an RBZ reflects directly on preventing a user drop, and 1 − pprotect can be viewed as an estimate of pdrop . In particular, the need for an admission control is manifested and only takes effect when the network experiences high system loads. On the other hand, at lower system loads, 1 − pprotect can be considered an upper bound on the SU drop rate. It should also be noted that at low system loads, the installation of an RBZ does not affect the operation of the system nor does it affects the efficiency of the resource allocation. Thus, for the rest of this section, we will refer to the probability 1 − pprotect as the dropping risk probability (prisk ). Our goal is to find, up to a dropping risk probability (prisk ), what is the maximum number of PU bands (Cmax ) that are expected to be lost to PUs in future time slots until the first 104 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems SU departure happens. Limiting the time horizon of the prediction algorithm to the time the first SU departure is expected to happen is intuitively valid since the departure of an SU releases some of the system resources that add directly to the protection of the already admitted users. But, we note that other choices for the time horizon are possible. Without loss of generality, we assume that T0 = 0 to simplify the notation in the following. From the properties of the exponential distribution, the time until the first departure amongst KRT RT SUs each with exponentially distributed call duration with mean also exponentially distributed with mean 1 µ = 1 KRT k=1 µk 1 , µk is . Thus, the probability that the first SU departs after time T is p1 (T ) = Pr(First SU departs after T time slots) = exp(−µT ). (5.9) On the other hand, the probability that the total number of free PU bands drops by C bands by time T is, p2 (C, T ) = Pr(Xt ≤ X0 − C for any t ≤ T |X0 ) T = Pr(Xt ≤ X0 − C, Xt−1,··· ,1 > X0 − C|X0 ) t=1 T X0 −C = t=1 j=0 Pr(Xt = X0 − C − j, Xt−1,··· ,1 > X0 − C|X0 ), (5.10) where Xt is the number of free PU bands at time t such that Nfree (t) = Xt N/L. Assuming ¯ (X −C) is equal to the transition matrix P but with all the transition probabilities that P 0 leading to states less than or equal to X0 −C set to zero, then Pr(Xt = X0 −C −j, Xt−1,··· ,1 > 105 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems X0 − C|X0 ) in (5.10) is equal to aX0 ,X0 −C−j (t, X0 − C), where t−1 ¯ A(t, X0 − C) = P (X0 −C) P , (5.11) and ai,j (t, X0 − C) represents the element of matrix A(t, X0 − C) on the ith row and j th column. The joint probability that both events happen, i.e. the probability that the total number of free PU bands drops by C bands by time T and the first SU departs after time T , is equal to the product of the two probabilities, i.e. p1 (T )p2 (C, T ), since both events are independent. Define CT as the minimum number of PU bands that makes p1 (T )p2 (C, T ) ≤ prisk . Then we need to determine Cmax = max T ∈{T0 ,··· ,Tmax } CT . (5.12) The time horizon, Tmax , is the time at which p1 (Tmax ) ≤ prisk . The pseudocode in Algorithm 5.1 provides an efficient implementation of the procedure discussed above. As an example, consider a CR system that has N = 128 carriers, out of which Nfree (T0 ) = 100 are free from any PU activity at time T0 . At the primary system side, the same band is divided amongst 128 PUs that switch independently between the Free and Busy states according to pb→f = 0.2 and pf→b = 0.05. Assume that the CR system has 10 already admitted RT SUs with independent call durations that are exponentially distributed with identical mean 1 µRT = 30 time slots each. For a dropping risk probability of prisk = 0.01, the product p1 p2 from Algorithm 5.1 evolves with time T as shown in Table 5.1. It is clear from Table 5.1 that the maximum drop in the number of free carriers the system could face is Cmax = 9 carriers. Thus, the size of the RBZ that needs to be installed to achieve a dropping 106 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems Algorithm 5.1 Find expected carrier drop Input: prisk , X0 Output: Cmax 1: T = 1 2: Cmax = 0 3: p1 = 1 4: while p1 > prisk do 5: p1 = exp(−µT ) 6: p2 = 1 7: while p1 p2 > prisk do 8: p2 = Pr(Xt ≤ X0 − Cmax for any t ≤ T |X0 ) 9: Cmax = Cmax + 1 10: end while 11: T =T +1 12: end while 13: Cmax = Cmax − 1 risk of at most 1% is 9 carriers. It should be noted that most figures in Table 5.1 are shown for illustrative purposes only. Algorithm 5.1 only captures the shaded numbers in Table 5.1, which are suffecient to obtain Cmax in (5.12). The undelined figure on each row of Table 5.1 corresponds to CT as defined above. 107 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems Table 5.1: p1 p2 from Algorithm 5.1 5.4 C=0 C=1 C=2 C=3 C=4 C=5 C=6 C=7 C=8 C=9 T=1 0.3461 0.2539 0.1729 0.1089 0.0633 0.0340 0.0168 0.0077 T=2 0.3113 0.2463 0.1834 0.1282 0.0841 0.0518 0.0301 0.0166 0.0086 T=3 0.2485 0.2041 0.1587 0.1165 0.0809 0.0531 0.0331 0.0196 0.0111 0.0060 T=4 0.1909 0.1606 0.1283 0.0972 0.0698 0.0475 0.0308 0.0190 0.0113 0.0064 T=5 0.1439 0.1232 0.1005 0.0778 0.0572 0.0399 0.0266 0.0169 0.0103 0.0060 T=6 0.1073 0.0932 0.0772 0.0608 0.0455 0.0324 0.0219 0.0142 0.0088 0.0052 T=7 0.0794 0.0698 0.0586 0.0468 0.0355 0.0257 0.0177 0.0116 0.0073 0.0044 T=8 0.0584 0.0519 0.0441 0.0357 0.0274 0.0200 0.0140 0.0093 0.0059 0.0036 T=9 0.0428 0.0384 0.0330 0.0270 0.0210 0.0155 0.0109 0.0073 0.0047 0.0029 T = 10 0.0313 0.0283 0.0245 0.0203 0.0159 0.0119 0.0084 0.0057 0.0037 0.0023 T = 11 0.0228 0.0208 0.0182 0.0151 0.0120 0.0090 0.0065 0.0044 0.0029 0.0018 T = 12 0.0166 0.0152 0.0134 0.0113 0.0090 0.0068 0.0049 0.0034 0.0022 0.0014 T = 13 0.0120 0.0111 0.0099 0.0084 0.0067 0.0051 0.0037 0.0026 0.0017 0.0011 T = 14 0.0087 0.0081 0.0072 0.0062 0.0050 0.0039 0.0028 0.0020 0.0013 0.0008 Resource Optimization After having investigated the problem of admission control in Section 5.3, we now turn our attention to the problems of resource optimization and eviction control of already admitted SUs. At any system event such as a new SU being admitted, an already admitted SU leaving the system, or a change to the system’s resources, i.e. available carriers, due to PU activity, the following optimization problem is solved to efficiently and optimally allocate the available system resources max rk,n (5.13a) k∈K n∈Nfree s.t. n∈Nfree rk,n ≥ Rk , ∀k ∈ KRT , (5.13b) 108 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems k∈K n∈Nfree pk,n ≤ Pmax , if pk,n ˆ = 0 then pk,n = 0, (5.13c) ∀ k = kˆ ∈ K, ∀ n ∈ Nfree , (5.13d) where K is the set of all, RT and NRT, admitted users. This problem and the power minimization problem in (5.4) can be efficiently solved using a Lagrange dual decomposition similar to the one presented in Chapter 4 and [84, 85, 88, 89]. In particular, each one of the rate constraints in (5.4b) and (5.13b) as well as the sum power constraint in (5.13c) gets associated with a Lagrange multiplier and the Lagrange dual problem is solved. It should be noted that the problem in (5.13) might become infeasible if the set of available carriers becomes insufficient to provide the required data rates by the admitted users. The infeasibility problem could still be faced even when an admission control mechanism as proposed in Section 5.3 is used. Changes to the available system resources beyond those predicted can still occur forcing the system into an infeasible state. When the system can no longer support the promised rates, a decision needs to be made to bring the system into a feasible state again. One possible solution could be to drop the rate requirements for all users and then allocate the available resources to the already admitted users in a fair manner. This approach was investigated in [90]. Another approach could be to drop as few users as possible to bring the system back to a feasible state. We believe that the latter user removal approach is more appropriate, since dropping the rate requirement of all users could lead to serious QoS degradation for most of the users by violating the promised rate guarantees. A user removal approach would limit the unsatisfactory effects to a limited set of users while satisfying the needs of most of the already admitted users. 109 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems In the following sub-sections, we propose three different algorithms to resolve system infeasibilities through user removal. The first two approaches represent the two extreme alternatives in terms of performance complexity tradeoff. In the third algorithm, we devise an innovative approach that delivers performance advantages over the long run and still maintains a low computational complexity profile. 5.4.1 Optimal User Removal (OptRem) We consider the Optimal Removal (OptRem) algorithm to be the one that i) minimizes the number of users that need to be dropped to make the problem in (5.13) feasible, and ii) if there exist multiple user dropping choices with equivalent number of users, choose the one that maximizes the overall achievable rates. The pseudocode for the OptRem algorithm is shown in Algorithm 5.2. It tests all user combinations that involve a single user removal for feasibility. If a single user removal yields no feasible combinations, i.e. set F (Line 4) is empty, all user combinations with two users removed are tested and so forth until a non empty set of feasible combinations is obtained (Lines 4-8). Once a non-empty set F is available, the algorithm picks the user combination that maximizes the system sum rate (Line 9). The OptRem algorithm is very complex since it explores up to D d=1 K K−d user combina- tions, D being the number of users actually dropped, before coming up with the list of users to be dropped. This complexity grows as the number of already admitted users increases and as the number of users to be removed at a time, D, increases. 110 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems Algorithm 5.2 Optimal user removal (OptRem) 1: // Initialize number of RT SUs to drop 2: d = 1 3: repeat K K−d 4: S : set of all 5: F : set of feasible combinations in S 6: d=d+1 user combinations 7: until F is not empty 8: find combination in F with highest sum rate 5.4.2 Random User Removal (RandRem) The OptRem algorithm, discussed above, can be classified as the most extreme solution in terms of computational complexity. Another, pragmatic and lower-complexity heuristic is the Random Removal (RandRem) algorithm. Once the system hits a state of infeasibility, this algorithm randomly picks one user for call termination and the system gets checked for feasibility again. If the system remains infeasible, the process is repeated until a feasible set of users is achieved. Compared to the OptRem algorithm above, RandRem can result in unnecessary user drops before bringing the system to a feasible state. The extra loss would only happen if a single user drop was not sufficient to alleviate the problem of infeasibility. This can be mostly observed when the PU dynamics are very fast or the range of user rate requirements is very large. 111 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems 5.4.3 User Removal Based on Lagrange Multipliers (LagRem) The Lagrange multiplier associated with each rate constraint in the admission control problem in (5.4) or the resource allocation problem in (5.13) represents a measure of how difficult it was to meet the corresponding constraint. That is, the higher the Lagrange multiplier the bigger the effect of that constraint on the system’s objective function [100]. Thus, dropping it would give the biggest possible room for other users to achieve their needs. That being said, when the problem in (5.13) becomes infeasible, we propose to sequentially drop the user with the highest Lagrange multiplier until the system becomes feasible. We will refer to this algorithm as the LagRem algorithm. As we will see in Section 5.5, this method leads to desirable long term effects in contrast to the OptRem algorithm. To explain, the “optimality” of the OptRem algorithm introduced above is only guaranteed on a short term basis since the user dropping decision is based on the instantaneous conditions of the system. Such a decision might turn out to be sub-optimal over the long term dynamics of the system. Since the OptRem algorithm frees the least amount of resources necessary to bring the system back to a feasible state it creates a tight fit, in terms of number of users and achievable rates, that might cause more drops in the near future as the system progresses. Different from this, the LagRem algorithm is best suited for long term activity by design since it drops the user that gives the biggest room possible for other users to maintain their sessions. Furthermore, it enjoys a low computational complexity that is equal to that of the RandRem algorithm discussed above. 112 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems 5.5 Simulation Results In this section, we present simulation results to evaluate the proposed admission control mechanisms from Section 5.3 and the user removal algorithms from Section 5.4. We adopt the approximation from (5.2) with βk,n according to [64] for the per-tone transmission power, pk,n , as a function of the required BER and the carrier loading, rk,n . We assume that the rates rk,n can take real values9 and the minimum BER requirement is 10−4 . 5.5.1 Performance of User Removal Algorithms Short Term Performance of User Removal Algorithms We start by evaluating the short term performance of the three user removal algorithms from Section 5.4. Towards that end, we assume that 5 SUs with minimum rate requirements of {5, 10, 15, 20, 25} bits/symbol were initially admitted based on an earlier channel realization that is of no significance. We then generated 10,000 i.i.d. channel realizations and tested for system feasibility with the presence of all 5 users given a sum power constraint. If the problem turns infeasible given a specific channel realization, we invoke the three removal algorithms to achieve a feasible set of users. Figure 5.2 shows the average number of supported users using the three removal algorithms for different levels of the sum power constraint along with the 99% confidence intervals. In this figure, we assume the presence of no primary system and the band is divided into N = 64 frequency carriers. The relatively low number of users and frequency carriers is inevitable due to the very high complexity of the OptRem 9 Without loss of generality, a finite set of discrete carrier loadings, rk,n , can be easily accommodated, see e.g. [85] for an optimization problem similar to (5.4). 113 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems 5 Average Number of Supported Users 4.5 4 3.5 3 2.5 2 OptRem LagRem RandRem 1.5 19.5 20 20.5 21 21.5 22 22.5 Sum Power Constraint (dB) 23 23.5 24 Figure 5.2: Average of the maximum number of SUs, among 5 SUs, the system can maintain while achieving a feasible resource allocation given a sum power constraint: Comparing three different user removal algorithms. algorithm. The figure clearly shows the superiority of the OptRem algorithm and how it supports the highest number of users compared to the other two algorithms. However, the complexity of the OptRem algorithm is prohibitive, especially when the number of admitted users is high or the number of users to be removed is high. The figure also shows how the LagRem algorithm has a performance that is close to that of the OptRem algorithm when the removal 114 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems of one user is sufficient to bring the system into a feasible state. It also performs better than the RandRem algorithm especially in the region that involves up to two user drops. This region is of great significance since one or two user removals are usually sufficient, in most realistic models, to bring the system to a feasible state. Long Term Performance of User Removal Algorithms After confirming the superiority of the OptRem algorithm on short term basis, we now consider the performance of the three user removal algorithms in the long run. For this, and for the rest of this section, we consider the downlink of a CR system which shares the bandwidth with a primary system that has priority over the band of interest. This bandwidth is divided into N = 128 OFDMA narrowband carriers, and the channels between the CR BS and the different SUs are i.i.d. circularly symmetric unit variance complex Gaussian across tones and SUs. We would like to emphasize that the assumed channel model is not critical to the performance of the proposed algorithms, and was chosen for simplicity. We further assume, for simplicity and ease of analysis, that all arriving RT SUs have the same rate requirement of R = 20 bits/symbol and the same average call duration of 1 µ = 30 time slots. The maximum power that the CR BS can utilize is Pmax = 30 dB (note the power normalizations applied to channel gains and noise). The number of PUs occupying the same bandwidth is L = 128. Each one of the PU bands transitions between the busy and free states with probabilities pf→b = 0.05 and pb→f = 0.2. In Figure 5.3, we plot the average drop rate of admitted RT SUs versus their arrival rate to the system for the three different removal algorithms. Interestingly, we see that the OptRem algorithm achieves the worst performance, in terms of RT SU drop rate, compared 115 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems −1 Average RT SU Drop Rate 10 −2 10 OptRem LagRem RandRem 0.3 0.35 0.4 0.45 0.5 RT SU Arrival Rate (λRT ) 0.55 0.6 0.65 Figure 5.3: Average RT SU drop rate versus a range of RT SU arrival rates (λRT ): Comparing three different user removal algorithms. to the other two algorithms. This is mainly due to the fact that the OptRem algorithm releases the least amount of system resources necessary to achieve a feasible solution to the resource allocation problem. Recall that the OptRem algorithm maintains the highest number of users possible and the highest sum rate possible amongst the admitted users set. This way, the algorithm tightly fits as many users and as much rate as possible making the system vulnerable to more service outages in the near future. In contrast to this, the LagRem algorithm is designed to remove users that have the biggest influence on the system 116 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems performance and thus, creating the biggest room, resource wise, that accommodates future system dynamics better than other removal techniques. That is why the LagRem algorithm achieves the lowest drop rate in the long run. For the rest of the results presented in this section, we will assume that the LagRem algorithm is used to resolve any system infeasibility due to its low complexity and superior long term performance. 5.5.2 Performance of Admission Control Algorithms Admission Control With Static RBZs After evaluating the performance of the different user removal algorithms, we move forward towards evaluating the performance of the three admission control mechanisms from Section 5.3. First, in Figure 5.4, we present simulation results for the power threshold based RBZ technique from Section 5.3.1. Figure 5.4 shows the average drop rate of RT SUs against their arrival rate, λRT , for different admission power thresholds, α = {0.9, 0.94, 0.98}. The figure clearly shows how the drop rate of RT SUs decreases as more power gets held back when admitting new arrivals. The power gap between admission time and resource optimization time in current and future time slots protects admitted RT SUs against a level of resource fluctuation that is proportional to the size of the power gap. The second alternative towards installing a fixed RBZ for user protection against call drops after admission is through the use of the fixed carrier release method from Section 5.3.2. Similar to Figure 5.4, Figure 5.5 plots the average RT SU drop rate for different arrival rates and different levels of carrier release C. It can be seen that the more carriers we voluntarily release while testing for admissibility, the more protection the admitted users get against 117 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems −2 Average RT SU Drop Rate 10 −3 10 α = 0.9 α = 0.94 α = 0.98 −4 10 0.3 0.35 0.4 0.45 0.5 RT SU Arrival Rate (λRT ) 0.55 0.6 0.65 Figure 5.4: Average RT SU drop rate versus a range of RT SU arrival rates (λRT ) when an RBZ based on fixed power threshold is installed. call drops while in service due to PU activity. In Figures 5.4 and 5.5, the RBZ is static and is usually assigned before any system activity can begin. Thus, some measurements, actual or simulated, are necessary for these thresholds to be set if a specific level of RT SU drops is required. By looking at plots similar to the ones in Figures 5.4 and 5.5, a system administrator seeking a drop rate that is below 1%, for example, would pick a fixed power threshold or a fixed number of carriers to be released according to the maximum anticipated system load. 118 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems −1 10 Average RT SU Drop Rate −2 10 −3 10 C C C C −4 10 0.3 0.35 0.4 0.45 0.5 RT SU Arrival Rate (λRT ) 0.55 0.6 = = = = 0 4 8 11 0.65 Figure 5.5: Average RT SU drop rate versus a range of RT SU arrival rates (λRT ) when an RBZ based on fixed carrier release is installed. To see the effect of the RBZ on the number of RT SUs that get blocked from service, Figure 5.6 plots the average blocking rate of RT SUs versus the size of the RBZ, in terms of released carriers C, for different levels of RT SU arrival rates. As the size of the RBZ increases, more carriers are held back at the time of admission, which reduces the number of RT SUs the system can support. Thus, more RT SUs get denied admission for the sake of protecting already admitted RT SUs. Although the number of of RT SUs that get admitted drops as the size of the RBZ increases, the number of dropped RT SUs decreases too. Thus, 119 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems 0 Average RT SU Block Rate 10 λRT = 0.45 λRT = 0.55 λRT = 0.65 −1 10 0 5 10 15 Number of Guard Carriers (C) 20 25 Figure 5.6: Average RT SU blocking rate versus size of the installed RBZ that is based on the fixed carrier release algorithm. the number of RT SUs that successfully finish their sessions, referred to as “good” RT SUs, does not necessarily drop in the same manner. To illustrate this, Figure 5.7 plots the average number of good RT SUs admitted to the system at any given time slot versus the size of the RBZ for different levels of RT SU arrival rates. At low RBZ sizes, the reduction in the drop rate is more significant than the reduction in the admission rate. Thus, the number of good users increases. As the RBZ size increases, the drop rate eventually approaches zero, and any increase in the RBZ size only prevents new RT SUs from being admitted causing a 120 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems Average Number of Good RT SUs per OFDMA Symbol 12.5 12 11.5 11 10.5 λRT = 0.45 λRT = 0.55 λRT = 0.65 10 0 5 10 15 Number of Guard Carriers (C) 20 25 Figure 5.7: Average number of “good” RT SUs admitted to the system at any given time slot versus size of the installed RBZ that is based on the fixed carrier release algorithm. drop in the overall number of good RT SUs. The system administrator could either choose the size of the RBZ, C, such that the overall system goodput is maximized regardless of the dropping and blocking rates associated with that C or, alternatively, aim at maintaining a minimum level of RT SU dropping rate and choose C that achieves the best overall system goodput given the dropping rate constraint. 121 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems We believe that the latter approach is preferable since it provides a guarantee on the level of QoS as seen by the end user. Admission Control With Predictive RBZ Figures 5.4 through 5.7 reveal the inherent tradeoff between the dropping rate and blocking rate and its implications on the overall system performance. To capture all of these effects, the availability of actual or simulated measurements is crucial to set the size of the RBZ accordingly. If these measurements were not available beforehand, protection based on predictive carrier release RBZ becomes the preferred option. In the predictive carrier release approach, a target maximum level of dropping rate, prisk , is specified and the algorithm sets the size of the RBZ accordingly without compromising the overall system performance. In Figure 5.8, we plot the average RT SU drop rate against the RT SU arrival rate when the requested dropping risk probability was prisk = {0.7%, 1%, 7%}. Recall that the dropping risk probability, prisk , represents the maximum level of call drops the system should encounter when the system load is high. The figure clearly shows how the algorithm successfully protects against a level of RT SU dropping rate that is proportional to the requested prisk . The figure also shows how the average RT SU drop rate approaches prisk as the arrival rate of RT SUs increases. The same observations can be made when looking at Figure 5.9, in which the average RT SU drop rate curves are all below the 45◦ line that represents the point at which the requested dropping risk probability matches the actual drop rate. Again, as the system load increases, the closer the performance curve moves towards the 45◦ line. We believe that adopting an admission control mechanism that is based on the predictive RBZ algorithm alongside the LagRem algorithm for infeasibility resolution constitutes a complete 122 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems −2 Average RT SU Drop Rate 10 −3 10 prisk = 0.007 prisk = 0.01 prisk = 0.07 0.3 0.35 0.4 0.45 0.5 RT SU Arrival Rate (λRT ) 0.55 0.6 0.65 Figure 5.8: Average RT SU drop rate versus a range of RT SU arrival rates (λRT ) when an RBZ based on predictive carrier release is installed. and versatile solution for multiple-user OFDMA CR systems. 5.6 Conclusions In this chapter, we studied the problem of admission and eviction control of RT SUs in multiple-user OFDMA CR networks. We proposed three different ways to protect against service outages by means of an RBZ that gets installed at the time of user admission. Two 123 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems −1 Average RT SU Drop Rate 10 −2 10 λRT = 0.65 λRT = 0.55 λRT = 0.45 45◦ Line −3 10 −2 10 Required RT SU Dropping Risk Probability (prisk ) Figure 5.9: Average RT SU drop rate versus the required dropping risk probability (prisk ) for different levels of RT SU arrival rates (λRT ) when an RBZ based on predictive carrier release is installed. of the proposed methods are static and require the availability of actual or simulated system measurements to effectively choose the static RBZ size. The third method is dynamic and adapts the size of the RBZ according to the current conditions of the system by predicting resource availability in the future. We also devised three different methods to deal with the problem of system infeasibility that might occur due to PUs activity on the shared resource. We showed how the user removal method based on Lagrange multipliers gave 124 Chapter 5. Admission and Eviction Control in OFDMA Cognitive Radio Systems the best performance on a long-term basis. In conclusion, admission and eviction control mechanisms are essential components of any viable CR system and the proposed techniques are excellent candidates to effectively realize these mechanisms. 125 Chapter 6 Conclusions and Future Work In this chapter, we present a summary of the topics discussed in this thesis and the contributions we made throughout this research. We also discuss open issues that can be addressed in future research efforts. 6.1 Thesis Contributions As we mentioned in the introduction of this thesis (Chapter 1), the topics discussed and presented here were directly linked to open research problems for which we made notable contributions. The topics all fall under the broader area of practical aspects in resource allocation and optimization for multiple-user wireless communication systems. We first introduced the new Differentiated Successive Interference Cancellation (DiffSIC) ordering technique for uplink multiple-user systems. Without any changes to the transmitter, DiffSIC works at the receiver to differentiate between users in service according to their priority levels. This is accomplished by altering the order of detection in a SIC receiver to optimally achieve the desired differentiation effect. DiffSIC relies on the availability of instantaneous SER figures for ZF-SIC and MMSE-SIC, for which we have presented semianalytical expressions. We have clearly demonstrated how the DiffSIC algorithm is capable 126 Chapter 6. Conclusions and Future Work of realizing significant improvements to the performance of high priority users in comparison to the classical V-BLAST algorithm. Moreover, these performance gains can be extended to more users when multiple detection chains are used at the receiver. We have also presented two methods to reduce the complexity associated with the DiffSIC algorithm by i) approximating the SER figures used by the algorithm and ii) by limiting the number of detection orders the algorithm has to consider to achieve differentiated performance. We showed how both approximations can help significantly reduce the computational complexity of DiffSIC and at the same time fully achieve the promised differentiation gains of the optimal, full-fledged, algorithm. Considering the transmitter side of a similar system to that in Chapter 2, we introduced in Chapter 3 a new channel allocation scheme for uplink multiple-user MIMO systems. In this scheme, users are allowed to share multiple uplink channels simultaneously in an effort to enhance the system capacity without compromising the integrity or increasing the complexity of the receiver design. We have shown how these gains can be realized using simple and practical modulation and detection techniques. Shifting our focus to CR systems, in Chapter 4, we identified and solved new design problems for MIMO CR systems with partial knowledge of the CSI of PUs channels at the SU transmitter. We formulated several optimization problems and proved their equivalence to convex optimization counterparts, which can be solved efficiently. We first considered CR systems with multiple MIMO PUs and single MIMO SU and presented numerical results that demonstrated the effectiveness and robustness of the proposed techniques. We demonstrated the detrimental effect of designing for CR systems without taking channel uncertainties into account on the level of interference generated at the PUs. We also included extensions to 127 Chapter 6. Conclusions and Future Work treat multiple-carrier CR systems under total or per-carrier constraints and systems with multiple SUs. We demonstrated how a Lagrange dual decomposition approach can be utilized to effectively handle these extensions. Finally, we studied the problem of admission and eviction control in multiple-user OFDMA CR networks without ignoring the important effect of channel conditions on the decision process. We proposed three different ways to protect against service outages by means of an RBZ that gets installed at the time of user admission. We also tackled the problem of user eviction as one of the best measures to handle system infeasibilities resulting from the fluctuating nature of the available resources. Towards that, we presented three algorithms for user removal with different complexity and performance profiles. We showed how an admission control mechanism based on the predictive carrier release algorithm alongside a user removal functionality based on LagRem algorithm constitute a complete and effective solution for RT SUs protection in multiple-user CR systems. 6.2 Future Work In this section, we present extensions to the work presented in this thesis that can be the subject of any future research effort. In relevance to Chapter 2, other methods for attaining service differentiation at the receiver can be investigated. Given the limited processing power any receiver design might have and given the recent advancements in Software Defined Radio (SDR) techniques, service differentiation can be achieved by proportionally allocating processor time in a way that helps achieve the desired performance. 128 Chapter 6. Conclusions and Future Work For example, the complexity of the detection algorithm greatly affects the performance of the detected stream. Optimal detection using MLD is well known for its very high complexity, while other sub-optimal detectors can have a complexity anywhere in the range below MLD. This wide range of complexities, gives the receiver the ability to differentiate users by assigning them different detection algorithms with different complexities according to their class of service. In SDR systems, most of the PHY layer processing is moved to powerful Digital Signal Processors (DSPs) that are programmable and reconfigurable. There is a firm believe in the industry that it is only a matter of a few years time, before embedded or digital signal processors become capable of implementing the PHY layer of a wireless Access Point or base station entirely in software. In relevance to the work presented in Chapter 4, one interesting direction would be to extend the bounded uncertainty model we used to other contemporary problems in which a perfect CSI assumption could lead to undesirable effects. For example, in [101–103] the authors assumed perfect CSI when formulating optimization problems related to MIMO relay communication systems. We plan to extend the works in [101–103] to account for uncertainties in CSI of channels to and from different relays in the network. Another extension is to include uncertainties related to the channel between the SU transmitter and receiver when designing for MIMO CR systems. Although, such uncertainties are usually less critical and easier to control given the cooperative nature between the parties involved, including them would enhance the performance of the CR system and effectively utilize the system resources. Finally, another topic that remains open until today is how to enhance the process of obtaining CSI of the channels between different PUs and the SU transmitter such that 129 Chapter 6. Conclusions and Future Work the uncertainty region is as tight as possible. This rests in the ability of obtaining such information with the least amount of changes to the communication protocols adopted by current primary systems. The use of environmental learning [104] and cooperative sensing [105–107] is promising and could yield to much improved system performance. 130 Bibliography [1] “IEEE Standard for Information Technology-Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,” IEEE Std 802.11-2007 (Revision of IEEE Std 802.11-1999), pp. C1–1184, 12 2007. [2] V. Srivastava and M. Motani, “Cross-layer design: a survey and the road ahead,” IEEE Commun. Mag., vol. 43, pp. 112–119, 2005. [3] D. Bertsekas, R. Gallager, and T. Nemetz, Data networks. Prentice-hall Englewood Cliffs, NJ, 1987. [4] A. Leon-Garcia and I. Widjaja, Communication networks: fundamental concepts and key architectures. McGraw-Hill Science Engineering, 2004. [5] “IEEE Standard for Information technology–Telecommunications and information exchange between systems–Local and metropolitan area networks–Specific requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 5: Enhancements for Higher Throughput,” IEEE Std 802.11n-2009 (Amendment to IEEE Std 802.11-2007 as amended by IEEE Std 802.11k131 Bibliography 2008, IEEE Std 802.11r-2008, IEEE Std 802.11y-2008, and IEEE Std 802.11w-2009), pp. c1–502, 29 2009. [6] “IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum 1,” IEEE Std 802.16e-2005 and IEEE Std 802.16-2004/Cor 1-2005 (Amendment and Corrigendum to IEEE Std 802.16-2004), pp. 0–1–822, 2006. [7] J. Lee, J. K. Han, and J. C. Zhang, “MIMO technologies in 3GPP LTE and LTEAdvanced,” EURASIP J. on Wireless Commun. and Networking, vol. 2009, 2009. [8] J. Mietzner, R. Schober, L. Lampe, W. Gerstacker, and P. Hoeher, “Multiple-antenna techniques for wireless communications - a comprehensive literature survey,” Communications Surveys & Tutorials, IEEE, vol. 11, no. 2, pp. 87–105, Quarter 2009. [9] B. Van Veen and K. Buckley, “Beamforming: a versatile approach to spatial filtering,” IEEE ASSP Mag., vol. 5, no. 2, pp. 4–24, April 1988. [10] H. Van Trees, Detection, estimation, and modulation theory. Wiley-Interscience, 2001. [11] G. J. Foschini, “Layered spacetime architecture for wireless communication is a fading environment when using multiple antennas,” Bell Labs. Tech. J., vol. 1, no. 2, pp. 41–59, Autumn 1996. [12] B. Vucetic and J. Yuan, Space-time coding. John Wiley & Sons Inc, 2003. 132 Bibliography [13] G. J. Foschini and M. J. Gans, “On limits of wireless communications in a fading environment when using multiple antennas,” Wireless Personal Commun., vol. 6, no. 3, pp. 311–335, Mar. 1998. [14] I. E. Telatar, “Capacity of multiantenna Guassian channels,” Eur. Trans. Telecommun., vol. 10, no. 6, pp. 585–595, 1999. [15] V. Tarokh, N. Seshadri, and A. R. Calderbank, “Space-time codes for high data rate wireless communication: Performance criterion and code construction,” IEEE Trans. Inform. Theory, vol. 44, pp. 744–765, 1998. [16] S. M. Alamouti, “A simple transmit diversity technique for wireless communications,” IEEE J. Select. Areas Commun., vol. 16, pp. 1451–1458, Oct. 1998. [17] V. Tarokh, H. Jafarkhani, and A. Calderbank, “Space-time block codes from orthogonal designs,” IEEE Trans. Inform. Theory, vol. 45, no. 5, pp. 1456–1467, Jul 1999. [18] D. Gesbert, M. Shafi, D. S. Shiu, P. Smith, and A. Naguib, “From theory to practice: An overview of MIMO space-time coded wireless systems,” IEEE J. Select. Areas Commun., vol. 21, pp. 281–302, Apr. 2003. [19] T. Rappaport, Wireless communications: principles and practice. Prentice Hall PTR Upper Saddle River, NJ, USA, 2001. [20] J. R. Barry, E. A. Lee, and D. G. Messerschmitt, Digital Communication, 3rd ed. Kluwer, 2004. 133 Bibliography [21] D. Gesbert, M. Kountouris, R. Heath, C.-B. Chae, and T. Salzer, “Shifting the mimo paradigm,” IEEE Signal Processing Mag., vol. 24, no. 5, pp. 36–46, Sep. 2007. [22] E. Biglieri, R. Calderbank, and A. Constantinides, MIMO wireless communications. Cambridge Univ Pr, 2007. [23] D. Tse and P. Viswanath, Fundamentals of wireless communication. Cambridge Univ Pr, 2005. [24] M. Costa, “Writing on dirty paper,” IEEE Trans. Inform. Theory, vol. 29, no. 3, pp. 439–441, May 1983. [25] M. Bengtsson and B. Ottersten, Optimal and suboptimal transmit beamforming, in Handbook of Antenna in Wireless Communications, L. C. Godara, Ed. CRC Press, Aug. 2001. [26] F. Rashid-Farrokhi, L. Tassiulas, and K. Liu, “Joint optimal power control and beamforming in wireless networks using antenna arrays,” IEEE Trans. Commun., vol. 46, no. 10, pp. 1313–1324, Oct 1998. [27] A. Wiesel, Y. Eldar, and S. Shamai, “Linear precoding via conic optimization for fixed mimo receivers,” IEEE Trans. Signal Processing, vol. 54, no. 1, pp. 161–176, Jan. 2006. [28] M. Schubert and H. Boche, “Iterative multiuser uplink and downlink beamforming under sinr constraints,” IEEE Trans. Signal Processing, vol. 53, no. 7, pp. 2324–2334, July 2005. 134 Bibliography [29] M. Shenouda and T. Davidson, “Nonlinear and linear broadcasting with QoS requirements: Tractable approaches for bounded channel uncertainties,” IEEE Trans. Signal Processing, vol. 57, no. 5, pp. 1936–1947, May 2009. [30] I. Mitola, J. and J. Maguire, G.Q., “Cognitive radio: making software radios more personal,” IEEE Personal Commun., vol. 6, no. 4, pp. 13–18, Aug 1999. [31] G. Staple and K. Werbach, “The end of spectrum scarcity [spectrum allocation and utilization],” IEEE Spectr., vol. 41, no. 3, pp. 48–52, Mar. 2004. [32] Federal Communications Commission Spectrum Policy Task Force, “Report of the Spectrum Efficiency Working Group,” FCC, Tech Report, Nov. 2002. [33] S. Haykin, “Cognitive radio: brain-empowered wireless communications,” IEEE J. Select. Areas Commun., vol. 23, no. 2, pp. 201–220, Feb. 2005. [34] T. Yucek and H. Arslan, “A survey of spectrum sensing algorithms for cognitive radio applications,” IEEE Commun. Surveys and Tutorials, vol. 11, no. 1, pp. 116–130, Mar. 2009. [35] I. F. Akyildiz, W.-Y. Lee, M. C. Vuran, and S. Mohanty, “Next generation/dynamic spectrum access/cognitive radio wireless networks: a survey,” Comput. Netw. (Elsevier), vol. 50, no. 13, pp. 2127–2159, Sep. 2006. [36] J. Giese and M. Skoglund, “Space-time constellation design for partial CSI at the receiver,” IEEE Trans. Inform. Theory, vol. 53, no. 8, pp. 2715–2731, Aug. 2007. 135 Bibliography [37] M. Ozdemir and H. Arslan, “Channel estimation for wireless ofdm systems,” IEEE Commun. Surveys & Tutorials, vol. 9, no. 2, pp. 18–48, Quarter 2007. [38] IEEE 802 LAN/MAN Standards Committee 802.22 WG on WRANs. [Online]. Available: http://grouper.ieee.org/groups/802/22/ [39] C. Stevenson, G. Chouinard, Z. Lei, W. Hu, S. Shellhammer, and W. Caldwell, “IEEE 802.22: The first cognitive radio wireless regional area network standard,” IEEE Commun. Mag., vol. 47, no. 1, pp. 130–138, January 2009. [40] R. V. Nee and R. Prasad, OFDM Wireless Multimedia Communications. Artech House, 2000. [41] S. B. Weinstein and P. M. Ebert, “Data transmission by frequency-division multiplexing using the discrete fourier transform,” IEEE Trans. Commun. Technol., vol. 19, pp. 628–634, October 1971. [42] N. Prasad and M. K. Varanasi, “Analysis of decision feedback detection for MIMO rayleigh-fading channels and the optimization of power and rate allocations,” IEEE Trans. Inform. Theory, vol. 50, pp. 1009–1025, Jun. 2004. [43] F. Khaled and K. Stefan, Multi-carrier & spread spectrum systems: From OFDM & MC-CDMA to LTE & WiMAX. John Wiley and Sons, 2008. [44] S. Verdu, Multiuser Detection. Cambridge University Press, 1998. [45] H. Huang, S. Schwartz, and S. Verdu, “Combined multipath and spatial resolution 136 Bibliography for multiuser detection: Potentials and problems,” in Proc. IEEE Int. Symp. Inform. Theory, 1995, p. 380. [46] P. W. Wolniansky, G. J. Foschini, G. D. Golden, and R. A. Valenzuela, “V-BLAST: An architecture for realizing very high data rates over the rich-scattering wireless channel,” in Proc. URSI Int. Symp. Signals, Systems, and Electronics, 1998. [47] P. Bhagwat, P. P. Bhattacharya, A. Krishna, and S. K. Tripathi, “Enhancing throughput over wireless LANs using channel state dependent packet scheduling,” in Proc. IEEE Conf. on Computer Commun. (INFOCOM), 1996, pp. 1133–1140. [48] R. Zhang, Y.-C. Liang, R. Narasimhan, and J. Cioffi, “Approaching MIMO-OFDM capacity with per-antenna power and rate feedback,” IEEE J. Select. Areas Commun., vol. 25, no. 7, pp. 1284–1297, September 2007. [49] R. Zhang and J. Cioffi, “Approaching MIMO-OFDM capacity with zero-forcing VBLAST decoding and optimized power, rate, and antenna-mapping feedback,” IEEE Trans. Signal Processing, vol. 56, no. 10, pp. 5191–5203, Oct. 2008. [50] M. Siti and M. Fitz, “A novel soft-output layered orthogonal lattice detector for multiple antenna communications,” in Proc. IEEE Int. Conf. on Commun., vol. 4, June 2006, pp. 1686–1691. [51] L. Azzam and E. Ayanoglu, “Reduced complexity sphere decoding for square QAM via a new lattice representation,” in Proc. IEEE Global Telecommun. Conf., Nov. 2007, pp. 4242–4246. 137 Bibliography [52] S. Loyka and F. Gagnon, “Performance analysis of the V-BLAST algorithm: An analytical approach,” IEEE Trans. Wireless Commun., vol. 3, no. 4, pp. 1326–1337, Jul. 2004. [53] ——, “V-BLAST without optimal ordering: analytical performance evaluation for Rayleigh fading channels,” IEEE Trans. Commun., vol. 54, no. 6, pp. 1109–1120, Jun. 2006. [54] M. Chiani, D. Dardari, and M. Simon, “New exponential bounds and approximations for the computation of error probability in fading channels,” IEEE Trans. Wireless Commun., vol. 2, no. 4, pp. 840–845, Jul. 2003. [55] S. Kim and K. Kim, “Log-likelihood-ratio-based detection oridering in V-BLAST,” IEEE Trans. Commun., vol. 54, pp. 302–307, Feb. 2006. [56] G. Barriac and U. Madhow, “PASIC: A new paradigm for low-complexity multiuser detection,” in Proc. Conf. on Inform. Sci. and Syst., The Johns Hopkins University, Mar. 2001. [57] R. de Lamare and R. Sampaio-Neto, “Minimum mean-squared error iterative successive parallel arbitrated decision feedback detectors for DS-CDMA systems,” IEEE Trans. Commun., vol. 56, no. 5, pp. 778–789, May 2008. [58] R. H. Bacon, “Approximations to multivariate normal orthant probabilities,” The Annals of Mathematical Statistics, vol. 34, no. 1, pp. 191–198, 1963. [59] A. Solow, “A method for approximating multivariate normal orthant probabilities,” Journal of Statistical Computation and Simulation, vol. 37, pp. 225–229, 1990. 138 Bibliography [60] H. Joe, “Approximations to multivariate normal rectangle probabilities based on conditional expectations,” Journal of the American Statistical Association, vol. 90, no. 431, pp. 957–964, 1995. [61] V. Kostina and S. Loyka, “On optimum power allocation for the V-BLAST,” IEEE Trans. Commun., vol. 56, no. 6, pp. 999–1012, Jun. 2008. [62] S. Sfar, K. B. Letaief, and R. D. Murch, “Achieving high capacities in CDMA systems using multiuser detection based on BLAST,” in Proc. IEEE Int. Conf. on Commun., vol. 2, June 2001, pp. 565–569. [63] S. Visuri and H. B¨olcskei, “Multiple-access strategies for frequency-selective mimo channels,” IEEE Trans. Inform. Theory, vol. 52, no. 9, pp. 3980–3993, Sept. 2006. [64] J. G. Proakis, Digital Communications, 4th ed. New York: McGraw-Hill, 2001. [65] B. Picinbono and P. Chevalier, “Widely linear estimation with complex data,” IEEE Trans. Signal Processing, vol. 43, no. 8, pp. 2030–2033, Aug 1995. [66] M. K. Varanasi, “Group detection in synchronous Gaussian code-division multipleaccess channels,” IEEE Trans. Inform. Theory, vol. 41, pp. 1983–1096, 1995. [67] R. Schober, W. Gerstacker, and L. Lampe, “On suboptimum receivers for DS-CDMA with BPSK modulation,” Elsevier Signal Processing, vol. 85, pp. 1149–1163, June 2005. [68] A. Lampe and M. Breiling, “Asymptotic analysis of widely linear MMSE multiuser detection - complex vs real modulation,” in Proc. IEEE Inform. Theory Workshop, September 2001. 139 Bibliography [69] R. Zhang and Y.-C. Liang, “Exploiting multi-antennas for opportunistic spectrum sharing in cognitive radio networks,” IEEE J. Select. Topics Signal Processing, vol. 2, no. 1, pp. 88–102, Feb. 2008. [70] G. Bansal, M. Hossain, and V. Bhargava, “Optimal and suboptimal power allocation schemes for OFDM-based cognitive radio systems,” IEEE Trans. Wireless Commun., vol. 7, no. 11, pp. 4710–4718, Nov. 2008. [71] L. Zhang, Y.-C. Liang, and Y. Xin, “Robust cognitive beamforming with partial channel state information,” in Proc. Conf. Inform. Sciences and Systems, March 2008, pp. 890–895. [72] G. Zheng, K.-K. Wong, and B. Ottersten, “Robust cognitive beamforming with bounded channel uncertainties,” IEEE Trans. Signal Processing, vol. 57, no. 12, pp. 4871–4881, Dec. 2009. [73] K. Phan, S. Vorobyov, N. Sidiropoulos, and C. Tellambura, “Spectrum sharing in wireless networks via QoS-aware secondary multicast beamforming,” IEEE Trans. Signal Processing, vol. 57, no. 6, pp. 2323–2335, June 2009. [74] L. Zhang, Y.-C. Liang, and Y. Xin, “Joint beamforming and power allocation for multiple access channels in cognitive radio networks,” IEEE J. Select. Areas Commun., vol. 26, no. 1, pp. 38–51, Jan. 2008. [75] A. Abdel-Samad, A. Gershman, and T. Davidson, “Robust transmit beamforming based on imperfect channel feedback,” in Proc. IEEE Veh. Technol. Conf., vol. 3, Sept. 2004, pp. 2049–2053 Vol. 3. 140 Bibliography [76] J. Wang and D. Palomar, “Worst-case robust MIMO transmission with imperfect channel knowledge,” IEEE Trans. Signal Processing, vol. 57, no. 8, pp. 3086–3100, Aug. 2009. [77] M. Shenouda and T. Davidson, “On the design of linear transceivers for multiuser systems with channel uncertainty,” IEEE J. Select. Areas Commun., vol. 26, no. 6, pp. 1015–1024, August 2008. [78] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, March 2004. [79] J. F. Sturm, “Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,” 1999. [80] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming (web page and software). http://stanford.edu/˜boyd/cvx,” June 2009. [81] W. Yu and R. Lui, “Dual methods for nonconvex spectrum optimization of multicarrier systems,” IEEE Trans. Commun., vol. 54, no. 7, pp. 1310–1322, Jul. 2006. [82] W. Yu, “A dual decomposition approach to the sum power Gaussian vector multiple access channel sum capacity problem,” in Proc. Conf. Inf. Sciences and Systems, 2003. [83] L. Xiao, M. Johansson, and S. Boyd, “Simultaneous routing and resource allocation via dual decomposition,” IEEE Trans. Commun., vol. 52, no. 7, pp. 1136–1144, July 2004. 141 Bibliography [84] K. Seong, M. Mohseni, and J. Cioffi, “Optimal resource allocation for OFDMA downlink systems,” in Proc. IEEE Int. Symp. Inform. Theory, Jul. 2006, pp. 1394–1398. [85] I. Wong and B. Evans, “Optimal downlink OFDMA resource allocation with linear complexity to maximize ergodic rates,” IEEE Trans. Wireless Commun., vol. 7, no. 3, pp. 962–971, Mar. 2008. [86] Z.-Q. Luo and S. Zhang, “Duality gap estimation and polynomial time approximation for optimal spectrum management,” IEEE Trans. Signal Processing, vol. 57, no. 7, pp. 2675–2689, July 2009. [87] C. Y. Wong, R. Cheng, K. Lataief, and R. Murch, “Multiuser OFDM with adaptive subcarrier, bit, and power allocation,” IEEE J. Select. Areas Commun., vol. 17, no. 10, pp. 1747–1758, Oct. 1999. [88] W. Jiao, L. Cai, and M. Tao, “Competitive scheduling for OFDMA systems with guaranteed transmission rate,” Comput. Commun., vol. 32, no. 3, pp. 501–510, Feb. 2009. [89] M. Tao, Y.-C. Liang, and F. Zhang, “Resource allocation for delay differentiated traffic in multiuser OFDM systems,” IEEE Trans. Wireless Commun., vol. 7, no. 6, pp. 2190– 2201, Jun. 2008. [90] Y. Zhang and C. Leung, “Cross-layer resource allocation for mixed services in multiuser OFDM-based cognitive radio systems,” IEEE Trans. Veh. Technol., vol. 58, no. 8, pp. 4605–4619, Oct. 2009. 142 Bibliography [91] V. P. Diego Pacheco-Paramo and J. Martinez-Bauset, “Optimal admission control in cognitive radio networks,” in Proc. 4th Int. Conf. on Cognitive Radio Oriented Wireless Networks and Commun., Jun. 2009. [92] H. Kim and K. Shin, “Optimal admission and eviction control of secondary users at cognitive radio hotspots,” in Proc. 6th Annual IEEE Commun. Society Conf. on Sensor, Mesh and Ad Hoc Commun. and Networks, Jun. 2009, pp. 1–9. [93] A. Goldsmith and S.-G. Chua, “Variable-rate variable-power MQAM for fading channels,” IEEE Trans. Commun., vol. 45, no. 10, pp. 1218–1230, Oct. 1997. [94] D. Niyato and E. Hossain, Medium access control protocols for dynamic spectrum access in cognitive radio networks: A survey, invited chapter in Cognitive Radio Networks, Y. Xiao and F. Hu, Eds. CRC Press, 2008. [95] H. Su and X. Zhang, “Cross-layer based opportunistic MAC protocols for QoS provisionings over cognitive radio wireless networks,” IEEE J. Select. Areas Commun., vol. 26, no. 1, pp. 118–129, Jan. 2008. [96] L. Kleinrock, Queueing systems: Computer applications. Wiley-Interscience, 1976. [97] A. Leon-Garcia and I. Widjaja, Communication Networks. McGraw Hill, 2000. [98] S. Tekinay and B. Jabbari, “Handover and channel assignment in mobile cellular networks,” IEEE Commun. Mag., vol. 29, no. 11, pp. 42–46, Nov. 1991. [99] N. Tripathi, J. Reed, and H. VanLandinoham, “Handoff in cellular systems,” IEEE Personal Commun. Mag., vol. 5, no. 6, pp. 26–37, Dec. 1998. 143 Bibliography [100] G. Gange, K. Marriott, and P. J. Stuckey, “Smooth linear approximation of non-overlap constraints,” in Proc. 5th int. conf. on Diagrammatic Representation and Inference. Berlin, Heidelberg: Springer-Verlag, 2008, pp. 45–59. [101] Y. Rong, X. Tang, and Y. Hua, “A unified framework for optimizing linear nonregenerative multicarrier mimo relay communication systems,” IEEE Trans. Signal Processing, vol. 57, no. 12, pp. 4837–4851, Dec. 2009. [102] C. Li, X. Wang, L. Yang, and W.-P. Zhu, “A joint source and relay power allocation scheme for a class of mimo relay systems,” IEEE Trans. Signal Processing, vol. 57, no. 12, pp. 4852–4860, Dec. 2009. [103] J. Mietzner, L. Lampe, and R. Schober, “Distributed transmit power allocation for multihop cognitive-radio systems,” IEEE Trans. Wireless Commun., vol. 8, no. 10, pp. 5187–5201, October 2009. [104] F. Gao, R. Zhang, Y.-C. Liang, and X. Wang, “Multi-antenna cognitive radio systems: Environmental learning and channel training,” in Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, April 2009, pp. 2329–2332. [105] G. Ganesan and Y. Li, “Cooperative spectrum sensing in cognitive radio networks,” in Proc. First IEEE Int. Symp. on New Frontiers in Dynamic Spectrum Access Networks, Nov. 2005, pp. 137–143. [106] S. Mishra, A. Sahai, and R. Brodersen, “Cooperative sensing among cognitive radios,” in Proc. IEEE Int. Conf. on Commun., vol. 4, June 2006, pp. 1658–1663. 144 [107] E. Peh and Y.-C. Liang, “Optimization for cooperative sensing in cognitive radio networks,” in Proc. IEEE Wireless Commun. and Networking Conf., March 2007, pp. 27–32. [108] V. A. Yakubovich, “S-procedure in nonlinear control theory,” Vestnik Leningrad University, vol. 4, no. 1, pp. 73–93, 1977. [109] F. Zhang, The Schur complement and its applications. Springer, 2005. 145 Appendix A Derivation of Error Probability Expressions for ZF-SIC PAM Signals In this appendix, we derive the instantaneous SER expressions for ZF-SIC PAM signals that appeared in Chapter 2 (Equations 2.11, 2.12, and 2.13). The effect of error propagation (see (2.10)) in ZF-SIC can be viewed as a signal bias that can affect the way error probabilities are calculated for PAM signals in Additive White Gaussian Noise (AWGN) channels. Because of this signal bias, the error probability to the left side of the signal constellation point is different from the error probability to the right side of it. These probabilities become identical if no error propagation was present. See Figure A.1 for an illustration of these two different probabilities. For each one of the L − 2 inner signal points, the error probability to the left and to the right of the signal point are P (1) = Q and P (2) = Q (A.1) (A.2) d /2 + Bias min σ 2 /2 d /2 − Bias min σ 2 /2 , 146 Appendix A. Derivation of Error Probability Expressions for ZF-SIC PAM Signals GPLQ %LDV 3 3 Figure A.1: Effect of signal bias on error probability of PAM signals. respectively. For the right most signal point, only P (1) is relevant, while for the left most signal point, only P (2) is relevant. Thus the average SER can be written as P = = Substituting Bias = i−1 k=1 1 (L − 1)P (1) + (L − 1)P (2) L L−1 P (1) + P (2) L ¯bik ek and σ 2 = Mr j=1 (A.3) f¯ij2 σn2 for ZF-SIC, we get the equations in (2.12) and (2.13). 147 Appendix B Proof of Theorem 4.1 Proof. Consider the optimization problem in (4.8). Each of the L constraints in (4.8c) can be written as Iℓ − eH QT ⊗ I Mr,P U eℓ − gˆ H QT ⊗ I Mr,P U eℓ − 2ℜ gˆ H QT ⊗ I Mr,P U gˆ ℓ ≥ 0 ℓ ℓ ℓ ∀ ǫ2ℓ − eH RTℓ ⊗ I Mr,P U eℓ ≥ 0, (B.1) ℓ ˆ ℓ ), and eℓ = vec(E ℓ ). Similar to the inequality (4.8c), the inequality (B.1) where gˆ ℓ = vec(G represents an infinite set of constraints, one for each eℓ satisfying ǫ2ℓ −eH RTℓ ⊗ I Mr,P U eℓ ≥ ℓ 0. However, the quadratic forms in (B.1) enable us to obtain a single constraint that is precisely equivalent to the infinite constraints in (B.1). In particular, using the results of S-lemma [108], one can show that the set of constraints in (B.1) holds if and only if there exists µℓ ≥ 0 such that µℓ RTℓ ⊗ I Mr,P U − QT ⊗ I Mr,P U H T −ˆ gℓ Q ⊗ I Mr,P U − QT ⊗ I Mr,P U gˆ ℓ ≥ 0. 2 (B.2) Iℓ − gˆ H QT ⊗ I Mr,P U gˆ ℓ − µℓ ǫℓ ℓ 148 Appendix B. Proof of Theorem 4.1 Furthermore, one can obtain an equivalent LMI of smaller size by employing the Schur Complement Theorem [109] that is presented in the following lemma A Lemma 1 (Schur Complement Theorem). Consider the Hermitian matrix X = B BH , C such that A > 0. Then the constraint X ≥ 0 is satisfied if and only if C − BA−1 B H ≥ 0. Applying the result of the Schur Complement Theorem to the LMI in (B.2), we obtain the following equivalent inequality: Iℓ − gˆ H QT ⊗ I Mr,P U gˆ ℓ − µℓ ǫ2ℓ ℓ − gˆ H QT ⊗ I Mr,P U ℓ µℓ RTℓ − QT ⊗ I Mr,P U −1 QT ⊗ I Mr,P U gˆ ℓ ≥ 0, (B.3) which can be written in terms of Gℓ as ˆ ℓ QG ˆ H − µℓ ǫ2 − Tr G ˆ ℓ Q (µℓ Rℓ − Q)−1 QG ˆ H ≥ 0. Iℓ − Tr G ℓ ℓ ℓ (B.4) Finally, to obtain an LMI representation of (B.4), one observes that (B.4) can be written as ˆ ℓ QG ˆ H + Tr G ˆ ℓS ℓG ˆ H + µ ℓ ǫ 2 ≤ Iℓ , Tr G ℓ ℓ ℓ (B.5a) S ℓ ≥ Q (µℓ Rℓ − Q)−1 Q. (B.5b) 149 Appendix B. Proof of Theorem 4.1 S ℓ The constraint in (B.5b) is indeed equivalent to the LMI the result of Lemma 1. Q ≥ 0, by applying Q µℓ R ℓ − Q 150 Appendix C List of Publications and Submissions The following lists all our publications/submissions related to the topics discussed in this thesis Journal Papers 1. T. Al-Khasib and L. Lampe, “Admission Control and Resource Optimization for Multiple-User OFDMA Cognitive Radio Systems,” under revision for IEEE Trans. Wireless Commun., Jan. 2010. 2. T. Al-Khasib, M. Shenouda, and L. Lampe, “Dynamic Spectrum Management for Multiple-Antenna Cognitive Radio Systems: Designs with Imperfect CSI,” under revision for IEEE Trans. Wireless Commun., submitted on Sep. 2009. 3. T. Al-Khasib, L. Lampe, and H. Alnuweiri “Uplink multiple-user V-BLAST Optimal Detection Ordering with Service Differentiation,” accepted for publication in IEEE Trans. Veh. Technol., submitted on Feb. 2009. Conference Papers 1. T. Al-Khasib, M. Shenouda, and L. Lampe, “Single and Multiple Carrier Designs 151 Appendix C. List of Publications and Submissions for Cognitive Radio Systems,” Best Paper Award, in Proc. IEEE Int. Conf. on Commun. (ICC 2010), Cape Town, South Africa, May 2010. 2. T. Al-Khasib, L. Lampe, and H. Alnuweiri “Uplink multiple-user V-BLAST Optimal Detection Ordering with Service Differentiation,” in Proc. IEEE 70th Veh. Technol. Conf. (VTC-fall), Anchorage, AL, USA, Sep. 2009. 3. T. Al-Khasib, L. Lampe, and H. Alnuweiri “Uplink Channel Allocation Strategies for CDMA-based multiple-user MIMO Systems,” in Proc. IEEE Int. Symposium on Personal, Indoor and Mobile Radio Commun. (PIMRC 2006), Helsinki, Sep. 2006. 152
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Resource allocation and optimization for multiple-user...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Resource allocation and optimization for multiple-user legacy and cognitive radio systems Al-Khasib, Tariq 2010
pdf
Page Metadata
Item Metadata
Title | Resource allocation and optimization for multiple-user legacy and cognitive radio systems |
Creator |
Al-Khasib, Tariq |
Publisher | University of British Columbia |
Date Issued | 2010 |
Description | The rapid transition towards user mobility and the increased demand it carries for bandwidth and data rates has been the driver for significant advancements in research and development in wireless communications in the last decade. These advancements materialized through enhancements to the well established legacy systems and conceptual innovations with great potential. Not far from that, in this thesis, we consider a diverse set of tools and techniques that facilitate efficient utilization of system resources in legacy and Cognitive Radio (CR) systems without hindering the integrity and robustness of the system design. First, we introduce the concept of service differentiation at the receiver, which can be realized by means of a new multiple-user Multiple-Input Multiple-Output (MIMO) detector based on the well known V-BLAST algorithm. We devise the DiffSIC algorithm that is able to differentiate between users in service based on their priorities or imminent needs. DiffSIC achieves its goal by determining the optimal order of detection, at the receiver, that best fits the users' profiles. Second, we propose a channel allocation technique for the transmitter of MIMO multiple-user access systems which enhances the system capacity without aggravating the complexity of the receiver. In particular, we allow users to share resources to take full advantage of the degrees of freedom available in the system. Moreover, we show how to realize these enhancements using simple, yet powerful, modulation and detection techniques. Next, we propose new robust system designs for MIMO CR systems under the inevitable reality of imperfect channel state information at the CR transmitter. We apply innovative tools from optimization theory to efficiently and effectively solve design problems that involve multiple secondary users operating over multiple frequency carriers. At last, we observe the effect of primary users' activity on the stability of, and quality of service provided by, CR systems sharing the same frequency resource with the primary system. We propose admission control mechanisms to limit the effect of primary users' activity on the frequency of system outages at the CR system. We also devise pragmatic eviction control measures to overcome periods of system infeasibility with a minimally disruptive approach. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-05-11 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0064792 |
URI | http://hdl.handle.net/2429/24588 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2010-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2010_fall_alkhasib_tariq.pdf [ 1.05MB ]
- Metadata
- JSON: 24-1.0064792.json
- JSON-LD: 24-1.0064792-ld.json
- RDF/XML (Pretty): 24-1.0064792-rdf.xml
- RDF/JSON: 24-1.0064792-rdf.json
- Turtle: 24-1.0064792-turtle.txt
- N-Triples: 24-1.0064792-rdf-ntriples.txt
- Original Record: 24-1.0064792-source.json
- Full Text
- 24-1.0064792-fulltext.txt
- Citation
- 24-1.0064792.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0064792/manifest