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