Adaptive Resource Allocation for Multiuser OFDM-based Cognitive Radio Systems by Tao Qin B. Eng., McMaster University, Canada, 2005 A THESIS S U B M I T T E D IN PARTIAL F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F A P P L I E D S C I E N C E in T H E F A C U L T Y O F G R A D U A T E STUDIES (Electrical and Computer Engineering) T H E UNIVERSITY O F BRITISH C O L U M B I A April 2007 © Tao Qin, 2007 Abstract Major challenges in the design of next generation wireless communication systems include harsh propagation environments and scarce resources such as power and spectrum. Cognitive radio (CR) is a promising concept for improving the utiliza-tion of scarce radio spectrum resources. Orthogonal frequency division multiplexing (OFDM) is regarded as a technology which is well-matched for CR systems. Dynamic resource allocation is an important task in such systems. In this thesis, a novel fair multiuser resource allocation algorithm for OFDM CR systems is presented. Although not optimal, the algorithm has low computational complexity. The algorithm attempts to maximize the total transmit bit rate (system throughput) of a group of secondary (unlicensed or CR) users subject to (1) a total transmit power constraint for secondary users, (2) a maximum tolerable interference level which can be tolerated by primary (licensed) users. The algorithm is fair in the sense that it tries whenever possible to allocate bits to users who have not re-ceived their fair share of service. Simulation results show that the proposed algorithm achieves a performance close to optimal. The effect on system throughput of changing various system parameter values is also examined. A novel cost minimization algorithm for multiuser OFDM cognitive radio systems is also proposed. The objective is to minimize a cost function which takes into account the interference power experienced by the primary user as well as the base station transmit power for secondary users given minimum bit rate requirements for each secondary user. It is found that the proposed algorithm provides a performance which is fairly close to optimal. The influence of a relative weight parameter on the base station (BS) transmit power for secondary users and the primary user interference power is also discussed. 11 Contents Abstract u Contents " i List of Tables v i List of Figures vii i List of Symbols x i i List of Abbreviations x v Acknowledgements x v i i Dedication xvii 1 Introduction 1 1.1 Evolution of Wireless Communication Systems 1 1.2 Motivation 2 1.3 Thesis Contributions 4 1.4 Thesis Organization 4 2 Preliminaries 6 2.1 Wireless Communication Channel 6 i i i 2.1.1 Signal Propagation in a Wireless Channel 6 2.1.2 Large-Scale Path loss 7 2.1.3 Small-Scale Fading and Multipath 8 2.2 Orthogonal Frequency Division Multiplexing 12 2.2.1 Orthogonality 12 2.2.2 OFDM System 13 2.3 Cognitive Radio 14 2.4 Mutual Interference in OFDM-based Cognitive Radio System 16 2.4.1 Interference Introduced by Secondary User Signal 17 2.4.2 Interference Introduced by Primary User Signal 18 3 Fair Adaptive Resource Allocation 19 3.1 Introduction 19 3.2 System Model 20 3.3 Proposed Algorithms 22 3.3.1 Basic Algorithm . . . 22 3.3.2 Reduced Complexity Algorithm 25 3.4 Simulation Results 29 4 Cost Minimization Resource Allocation 45 4.1 Introduction 45 4.2 System Model 46 4.3 Proposed Algorithm 47 4.3.1 Maximal Cost Reduction by a New Subcarrier 48 4.3.2 Proposed Resource Allocation Algorithm 50 4.4 Simulation Results 51 5 Conclusions and Suggestions for Future Work 64 iv 5.1 Contributions of the Thesis 64 5.2 Future work 65 Bibliography 67 v List o f Tables 3.1 Average values of number of bits, bk, and power, Pk, loaded onto sub-carrier k as well as interference power, Ik, seen by the primary user due to the signal transmitted on subcarrier k over 10000 channel real-izations with fj,R — 1 36 3.2 Average (over 10000 allocation periods) values of number of bits, bk, and power, Pk, loaded onto subcarrier k as well as interference power, Ik, seen by the primary user due to the signal transmitted on subcarrier k for constant channel power gains, |/imfc|2 and \gk\2, equal to 4/n. . . 38 3.3 Power gains |/iTOfc|2 and |<7fc|2 of subcarrier k 41 3.4 RC Algorithm results of bk, Pk and Ik for same channel realization gains as in Table 3.3 with identical NBRW 42 3.5 RC Algorithm results of bk, Pk and Ik for same channel realization gains as in Table 3.3 with no NBRW 43 3.6 Optimization software results of bk, Pk and Ik for same channel real-ization gains as in Table 3.3 with no NBRW 44 4.1 Average values of number of bits, bk, and power, Pk, loaded onto sub-carrier k as well as interference power, Ik, seen by the primary user due to the signal transmitted on subcarrier k and cost, Ck, on subcarrier k over 10000 channel realizations with HR = 1 55 vi 4.2 Values of number of bits, bk, and power, Pk, loaded onto subcarrier k as well as interference power, Ik, seen by the primary user due to the signal transmitted on subcarrier k for constant channel power gains, |/imfc|2 and \gk\2, equal to 4/7T 58 4.3 Power gains \hmk\2 and | ~ (2-12) [ 0, g < 0 where A > 0 denotes the peak amplitude of the dominant signal and I0(-) is the modified Bessel function of the first kind and zero-order. The delay spread and coherence bandwidth are parameters that describe the time dispersive nature of the channel in a local area. The mean excess delay is the first moment of the power delay profile and is defined to be i (2.13) The root mean squared (rms) delay spread is the square root of the second central moment of the power delay profile and is defined to be aT = ^ / T 2 - {rf (2.14) where n _ ^ (2.15) The coherent bandwidth is a range of frequencies over which two frequency com-ponents have significant correlation. If the coherence bandwidth is defined as the bandwidth over which the frequency correlation function is above 0.9, then the co-herence bandwidth of the channel is approximately [23] ftSJ5(k ( 2 1 6 ) Doppler spread and coherence time are parameters which describe the time vary-ing nature of the channel in a small-scale region. If we assume that the channel is 10 wide sense stationary, the Doppler power spectrum of a mobile channel for an omni-directional mobile antenna and the received plane wave with uniformly distributed arrival angle can be given by 2 Mfd) = ^ 2 (2-17) where fd,max is the maximum Doppler shift given by v fd,max — ~fc (2.18) C where v is the velocity of the mobile and c is the velocity of light. The coherence time, T c, is the time domain dual of the maximum Doppler spread, fd,max, and is used to characterize the time varying nature of the frequency disper-siveness of the channel in the time domain. The Doppler spread and coherence time are inversely proportional to one another, i.e., Tc « j^—- (2-19) Jd,max If the channel has a constant gain and linear phase response over a bandwidth which is greater than the bandwidth of the transmitted signal, the received signal will undergo flat fading. In other words, a signal undergoes flat fading if Bs « Bc where Bs is the bandwidth of transmitted signal and Bc is the coherence bandwidth of the channel. If the channel has a constant gain and linear phase response over a bandwidth that is smaller than the bandwidth of transmitted signal, i.e., Bs > Bc and T s < crT the received signal will undergo frequency selective fading. When this occurs, the received signal includes multiple versions of the transmitted waveform, therefore the received signal is distorted and ISI will be induced by the channel. If the channel impulse response varies rapidly within the symbol duration, i.e., the coherence time of the channel is smaller than the symbol period of the transmitted signal, the channel is referred to as fast fading. That is, a signal undergoes fast fading if Ts > Tc. If Ts « T c, the channel is said to be slow fading. 11 2.2 Orthogonal Frequency Division Multiplexing High-data-rate communications are limited not only by noise but often more sig-nificantly by the intersymbol interference (ISI) due to the time dispersive nature of wireless channels. Generally, the effects of ISI are negligible as long as the delay spread is significantly shorter than the duration of one transmitted symbol. O F D M [24] has been considered as a very promising solution for supporting high-data-rate transmis-sion in future broadband wireless communication systems due to its resistance to ISI. The basic idea of O F D M is to divide the available spectrum into several subcarriers so that the information symbols are transmitted in parallel on the subcarriers over the wireless channel. This allows us to design a system supporting high data rates while maintaining symbol durations much longer than the delay time of channel. By doing so, each subcarrier experiences almost a flat fading, and the effects of the multipath channels are reduced [25,26]. 2.2.1 Orthogonality Let K and Ts denote the number of subcarriers and the the signal symbol duration respectively. Let uk, k = 0,1, . . . , K — 1 denote the signal symbol for each subcarrier k and / 0 and fk = /o + k/Ta denote the carrier frequencies of subcarrier 0 and k subcarrier respectively. We assume that the transmitted signal, s(t), is rect(t) — 1, |*| < Ts/2. The baseband representation, Sb(t), of the transmitted signal can be expressed as Ek=o uk • rect{t - 3f) • exp [j2ir^{t) 0, 0 < t < Ts t>Ts (2.20) A block diagram which shows the generation of an O F D M signal and the recovery of the data symbols is shown in Fig. 2.1. 12 exp(j2nfot) -exp02nfot) S / P u0 exp(i2nf,t) Ul exp(j2TrfK.,t) U 0 M I Channel .J u 0 -exp(j2nf,t) I •exp(j2TTfK.1t) p/s* Figure 2.1: Generation and reception of O F D M signals. The subcarriers are orthogonal since \ fTa I 1, A; = n — / exp(j2-fkt) • exp(-j2nfnt) = J s - y ° I 0, fc/n The data symbol on subcarrier k can be recovered as follows: 4 / x r . + t . ~i K-l -j2--(t-ts) ra=0 exp n — k, - j 2 7 T - ^ - ( i - 0 eft — Uk n j2--(t-ts) dt (2.21) (2.22) As we can see from (2.22), the data symbol, Uk, on subcarrier k can be retrieved since the result of integral for other subcarriers is zero. Thus orthogonality is established. 2.2.2 O F D M System The O F D M baseband signal can be generated using an Inverse Discrete Fourier Trans-form (IDFT). Let K samples are taken at times t = nTs/K, n — 0 ,1 , . . . i f — 1 in (2.20) yielding K-l ,nTf » = s ^ = E u ^ k n l K > n = 0,1,..., A- - 1. (2.23) fc=0 13 Since (2.23) is the IDFT of uk- Therefore, the data symbols, uk, can be retrieved at the receiver by using a DFT, i.e. K-1 uk = £ s n e - j 2 w k n / K , i = 0,1,..., K - 1 . (2.24) n=0 The Fast Fourier Transform (FFT) is used in practice as it is computationally more efficient than the DFT. A block diagram of an OFDM system is shown in Fig. 2.2. As shown, cyclic prefix is usually inserted in order to avoid ISI [25]. Input data Scrial-to-:'; parallel- • 'buffer Multicarrier -modulatory • (IFF'i) Add cyclic*prefix^ * and parallel-to-'serial convert D.-A * 'converter I Output to 1 transmitter Transmitter Output data Detector. Multicarrier demodulator .' (ITT):-Remove cyclic prefix .*and-serial-.' 'to-parallel ^convert. i'arallel-;to>serial s converter 1 M— • . A/D converter" 1 • J Receiver Figure 2.2: Block diagram of a multicarrier OFDM digital communication system (taken from [25]). 2.3 Cognitive Radio As high performance wireless data networks and services are widely deployed, the scarcity of spectrum resources will represent a serious impediment. It is reported in [4] that most of the licensed spectrum bands are poorly utilized, resulting in spectrum holes [5]: "A spectrum hole is a band of frequencies assigned to a primary user, but, at a particular time and specific geographic location, the band is not being utilized by that user." 14 Spectrum utilization can be improved significantly by allowing a secondary (un-licensed) user to access spectrum holes [5]. CR [27,28], based on the concept of software-defined radio, has been proposed as a means to improve spectrum efficiency by exploiting spectrum holes. Cognitive radio is a spectrum sharing technology as is ultra-wide band (UWB). The key difference is that while the UWB signal spectrum overlaps with that of primary user signals, a CR signal spectrum resides mainly in the spectrum holes. As a result, a CR device may transmit at high signal powers for long range communication applications such as broadband wireless access in ways that cause no harmful interference to the primary users. There are three key concepts in CR [6]: • Sensing - The ability to identify spectrum holes. • Flexibility - The ability to easily change transmit signal frequency and spectrum shape to fit spectrum holes. • Non-interference - Transmission to secondary users should not cause harmful interference to primary users. Through interaction with the RF environment, a CR system performs the fol-lowing tasks [5]: 1. Radio-scene analysis, which involves: • estimation of interference "temperature" to ensure no harmful interference to primary user. • detection of spectrum holes. 2. Channel identification, which involves: • estimation of channel-state information (CSI); 15 • prediction of channel capacity for use by the transmitter. 3. Transmit-power control and dynamic spectrum management. Task 1) and 2) are carried out in the receiver, and task 3) is carried out in the transmitter. Through interaction with the RF environment, these three tasks form a cognitive cycle which is shown in a basic form in Fig. 2.3. Figure 2.3: Basic cognitive cycle (taken from [5]). 2 .4 Mutual Interference in OFDM-based Cogni-tive Radio System CR provides a novel approach for improving the utilization of radio spectrum. It is suggested in [6] that OFDM is an ideal physical layer candidate for wide-band CR systems. However, if the primary users employ non-OFDM based signaling (e.g., 16 single-carrier CDMA), there may be mutual interference between the primary and secondary users due to the non-orthogonality of their respective transmit signals [7]. In [21], a model for the downlink of an OFDM CR system with one base station (BS), one primary and one secondary user is proposed as shown in Fig. 2.4. The primary user and the secondary user share adjacent frequency bands as shown in Fig. 2.4. The primary user band, of width Wp Hz, is surrounded on each side by K/2 subcarriers with each subcarrier occupying a band of width Ws Hz. The K subcarriers are used for transmission to the secondary user using OFDM. As the BS can transmit simultaneously to both primary and secondary user, the primary user's signal causes interference to the secondary user and vice-versa [7,21]. In this thesis, we consider an extension of the model to M multiple secondary users. Figure 2.4: Primary user band of width Wp and secondary user sub-bands, each of width W3 (taken from [21]). 2.4.1 Interference Introduced by Secondary User Signal This interference is caused by the side lobes of the OFDM signal. The transmit signal on each subcarrier is a rectangular non-return-to-zero (NRZ) signal. The power spectral density (PSD) of the kth subcarrier signal is modeled as [7] 17 where Pk is the transmit power of the kth subcarrier signal and Ts is the symbol duration which consists of the sum of useful symbol duration and guard interval. The interference power introduced by this signal into the primary user's band is pdk+WP/2 h(dk,Pk) = / \9k\2 Mf) df = Pk IFk, (2.26) Jdk-WP/2 where Qk is the channel gain from the BS to the primary user for subcarrier k, dk is the spectral distance between subcarrier Ac and the center frequency of the primary user band and IFk = Ts f4**^/2 (lfl f c | S '"/rf a) $ denotes the interference factor for subcarrier k. 2.4.2 Interference Introduced by Primary User Signal The interference power introduced by the signal destined for the primary user, here-after referred to as the primary user's signal, into the subcarrier k band at user m is rdk + WS/2 Smk(dk) = / |/W| 2 $RR(ejw) dw, (2.27) Jdk-WS/2 where hmk is the subcarrier k gain from the BS to user m and $RR(ejw) is the PSD of the primary user's signal. 18 Chapter 3 Fair Adaptive Resource Allocation 3.1 Introduction In multimedia wireless communication, many applications do not have a prescribed bit transmission rate, e.g., best effort services (Hypertext transfer protocol (Http), Email, File transfer protocol (Ftp), etc.). For these services, the objective of resource allocation is to maximize the system throughput while ensuring some level of fairness among users. This chapter focuses on fair resource allocation in a multiuser OFDM based cognitive radio system. Fair scheduling for OFDM systems have been studied in [10,13] assuming that the power is equally distributed among the subcarriers but power and bit allocation on each subcarrier have not been investigated. A power loading algorithm for a fixed subcarrier allocation was studied in [17]. Joint subcarrier and power allocation to maximize the transmitted bit rate with proportional fairness was investigated in [16,19] assuming infinite granularity in bit rate. In [20], a proposed algorithm was to maximize the system throughput with total power budget and integer bit constraint while achieving proportional fairness among users. The above-mentioned algorithms can be applied in conventional multiuser OFDM 19 systems with only one type of users (e.g., secondary users). They do not consider mu-tual interference which may arise between primary and secondary users. In contrast, the mutual interference is considered in [21] for the case of one secondary user and the throughput of the secondary user is maximized subject to a maximum interference power that can be tolerated by the primary user. We now propose and evaluate a low complexity resource allocation algorithm to maximize the total transmit bit rate in a multiuser OFDM-based CR system with secondary user power, fairness, integer bit loading constraints as well as a maximum interference power that can be tolerated by the primary user. The algorithm first allocates bits to users to ensure fairness, and then uses a greedy approach for subcarrier, power and bit loading allocations. 3.2 System Model We consider the resource allocation and mutual interference model described in Sec-tion 2.4. We consider resource allocation on the downlink of an OFDM CR radio system in which a base station (BS) serves one primary and M secondary users. The primary user and the secondary users share adjacent frequency bands as shown in Fig. 2.4. The primary user band, of width Wp Hz, is surrounded on each side by K/2 subcarriers with each subcarrier occupying a band of width Wa Hz. The subcar-riers are used for transmission to the secondary users using OFDM. As the BS can transmit simultaneously to both primary and secondary users, the primary user's sig-nal can cause interference to the secondary users and vice-versa [7,21]. It is assumed that the channel is slowly time-varying and that the BS has perfect channel state information. Let Pmk denote the transmit power allocated to subcarrier k of user m. Following [11], the maximum number of bits in a symbol transmitted on this subcarrier is set 20 to i I i , I ^ mk | Pmk log 2 1 + ^ | . o g 2 | l + r ( — (3.1) where |_-J denotes the floor function, N0 is the one-sided noise PSD and Smk is given by (2.27). The parameter V in (3.1) depends on required target bit error rate (BER); V increases as the target B E R is decreased. For convenience, the term F is set to unity in the remainder of this thesis. Let amk 6 {0,1} be a subcarrier allocation indicator, i.e., amk = 1 if and only if subcarrier k is allocated to user m. It is assumed that each subcarrier can be used for transmission to at most one user at any given time. Let the total interference power seen by the primary user due to the signals destined for secondary users be M K I total ^^amkPmklFk, (3.2) m=l fc=l and the total transmit power for signals destined to secondary users be M K Ptotal = Y2 amkPmk- (3-3) m=l k=\ Our objective is to maximize the total bit rate for secondary users subject to total transmit power, fairness and primary user interference constraints. Specifically, the optimization problem is expressed as follows: M K max Ws ^ amkbmk (3.4) subject to m= =i /t=i e {0,1}, Vm,k (3.5) M ^ ^ &mk < 1, Vfc (3.6) > 0, Vm,/c (3.7) •Ptotal < p 1 max, (3.8) ftotal < Ith, (3.9) 21 where PMAX is the total secondary user power budget and Ith is the primary user's maximum tolerable interference power. Inequality (3.6) follows from the assumption that a subcarrier can be allocated to at most one user. Inequalities (3.8) and (3.9) correspond to the power and interference constraints respectively. The nominal bit rate weight (NBRW) for user m is denoted by A m so that A m / 2~2iLi is the fraction of the total secondary user bits loaded that is to be fairly allocated to user m. It is also convenient to denote the total number of bits per symbol period allocated to user i by Bi = Ylk=i ^ a n ^ define the total bit rate, Ri, of user i as PH = WsBi. The total bit rate for all secondary users is Rs = 2~2m=\ Rm-3.3 Proposed Algorithms An optimal solution to the integer programming problem in (3.4) is computationally complex and thus not suitable for wireless communications systems in which channel conditions are constantly changing. In Section 3.3.1, a low-complexity algorithm is proposed based on the basic algorithm described in Section 3.3.2. 3.3.1 Basic Algori thm The basic algorithm (BA) is based on a greedy approach: it successively assigns bits, one at a time, to the user and subcarrier requiring the smallest incremental increase in power or producing the smallest incremental increase in interference. For convenience, we denote these two subcarriers by kp and kj respectively. From (3.1), the incremental power required for transmitting one bit to user m on subcarrier k is given by APMK = NoW;+fmk^, (3.10) 22 From (2.26) and (3.10), the incremental interference power generated by such a trans-mission to the primary user is We associate the process of loading bits with a tree structure. At each node, up to two branches can be spawned corresponding to the subcarriers kp and kj. At each level of the tree, one bit is allocated. The result of the algorithm is a path in the tree whose length gives the total number of bits loaded; the path also specifies the subcarrier, bit and power loading for each secondary user. A pseudo-code description of the basic algorithm is given below. *** Basic Algorithm (BA) *** 1. Initialization (root node) (a) Set P = 0, I = 0. (b) Set Bm = 0 for m € {1,2,.. . , Af}. (c) Set bmk = 0 and calculate APmk as in (3.10) and AImk as in (3.11), for m € {1,2,. . . , M} and A: € {1, 2, . . . , K}. 2. While (there are new nodes) for each node (a) Determine m* = argminm Bm/\m; ties are first broken in decreasing order of A, then randomly 1 . (b) Determine kp = argmin^ APm.fc. (c) Determine k\ = argmin^ AIm*k-create a (new) child node with parameter values obtained by updating the corresponding parameter values of the parent node as follows: l rThe throughput could be improved by taking into account the gains of subcarrier and their spectrum distances to the primary user band when breaking ties. AImk = APmk IFk. (3.11) (d) If (P + APm.kp < Pmax) and (/ + APm*kp IFkp < hh) 23 Bm* — Bm* + 1, bm*kP — bm*kP + 1, P = P + APm*kp, 1 = 1 + APm.kp IFkp, calculate APm*kp as in (3.10) and AIm*kp as in (3.11), set APmkp = oo, AImkp = oo, Vm ^ m*. Otherwise, no child node is created. (e) If (7 + A / m . f e , Pmax), then set m* to be the user with the next higher value of Bm/Xm and go to step b). Stop if all users have been considered. Similarly, a minimum interference (MI) algorithm is used to determine the total power, PMI, required for transmitting to the secondary users if at each bit loading, we choose the subcarrier which minimizes the incremental interference power introduced into the primary user's band. *** Algorithm MI *** 1. Step 1 - Initialization (a) Set PMi = 0, / = 0. (b) Set S m = 0 for m € {1,2,.. . , Af}. (c) Set bmk = 0 and calculate AImk as in (3.11), for m € {1,2,.. . , M} and A; € {1,2,... ,K}. 2. Step 2 (a) Determine m* = argminm Bm/Xm; ties are first broken in decreasing order of A, then randomly. 26 (b) Determine ki = argmin/; AIm*k-(c) If (I + Alm^k, < Ith), perform the following updates: Bm* = Bm» + 1, bm*kj = bm'kj + 1, 1 = 1 + AJm.fc 7, PMI = PMI + Alm-kJIFk,, calculate AIm*k, as in (3.11), set AImkj = oo, Vrn ^ rn*, and go to step 2a). (d) If (7 +A/m»fc7 > Ith), then set m* to be the user with the next higher value of Bm/\m and go to step b). Stop if all users have been considered. The relative importance of the secondary user power and primary user interfer-ence is measured using yp = P m i ~ P m a x f (3.12) Pmax and VI=lMP-Itk^ ( 3 1 3 ) Ith respectively. Note that VP is negative when Pmax > PMI and VI is negative when Ith > IMP-The RC algorithm uses VI and VP as follows: *** Algorithm RC *** 1. Step 1 - Initialization (a) Set P = 0, I = 0. (b) Set Bm = 0 for m € {1,2,.. . , M}. (c) Set bmk = 0 and calculate APmu as in (3.10) and AImk as in (3.11), for m € {1, 2 , . . . , M} and k £ {1,2,..., K}. 2. Step 2 27 (a) Determine m* = argminm J3 m /A m ; ties are first broken in decreasing order of A, then randomly. (b) Determine hp = argminm APm.fc. (c) Determine kj = arg min*, AIm*k. (d) Compute X = ^ W ^ p - ^ , > a n d y = " W ^ V / f t , - * ^ ) . (e) If X > Y, set k* = kj; otherwise set k* = kp. (f) If (P + A / W < Pmax) and (/ + A W < Ith), perform the following updates: Bm* = Bm* + 1, bm*k* — bm*k* + 1, I = I + AIm.k,,P = P + APm.k,, calculate APm*k* as in (3.10) and AIm*k+ as in (3.11), set APmk. = oo, AImk* =oo, V m / m * , and go to step 2a). (g) If (P + A P m . f c . > Pmax) Or (7 + AIm*k* > 7f/i), then set m* to be the user with the next higher value of Bm/\m and go to step b). Stop if all users have been considered. The number, B, of bits allocated to secondary users is given by X)m=i Bm-The complexity of the RC algorithm is 0(numJbits x K), where numJoits denotes the total number of bits loaded. This is much lower than the 0(2num-blts) complexity for the basic algorithm. In the case when no NBRWs are specified, algorithms BA, MP, MI and RC can still be used to determine Rs with the following slight modifications. For example, in algorithm RC steps 2a) and 2g) are omitted; steps 2b), 2c), 2d) and 2e) are changed to 2b): Determine (mp,kp) = argminm]fc APmfc, 28 2c): Determine (mi,kj) = argminm>fc AImk, 2d): Compute X = v ^ r t f ^ - " - * ) a n d y = ^ A / m / > / / f t f - A p m f , t p ) 2e): If X > Y, set (m*,k*) = (mj,kj); otherwise set (m*,k*) = (mp,kp). 3.4 Simulation Results In this section, average bit rate results for the RC algorithm, obtained using computer simulations, are provided. Results for the basic algorithm are not available due to the long computational times required. We consider a system with one primary and M secondary users. The secondary user band is 5 MHz wide and consists of 16 subcarriers, each with a bandwidth, Ws, of 0.3125 MHz. The primary user bandwidth is Wp = Ws and the symbol duration is Ts = 4 [is. It is assumed that the subcarrier gains hmk and gk, for m € {1,2,. . . , M} , k E {1,2,.. . , K} are outcomes of independent, identically distributed (i.i.d.) Rayleigh random variables (rv's) with means PR. The noise is assumed to be additive white Gaussian noise (AWGN) with PSD, A^0. The PSD, ^ RR(e'w), of the signal transmitted to the primary user is assumed to be that of an elliptically filtered white noise process. The total secondary user bit rate results are obtained by averaging over 10,000 channel realizations. In order to evaluate the performance of the RC algorithm, an integer program-ming optimization software package was used. However, the long computational time allowed only 20 channel realizations to be used. It was found that among the 20 channel realizations, the total bit rate obtained using the RC algorithm was 6.4% lower than the optimal solution in the worst case. Averaged over the 20 channel realizations, the difference was 3.5%. Fig. 3.1 shows the total bit rate, Rs, of 4 the secondary users as a function of the maximum tolerable interference power level, Ith, of the primary user for different 29 nominal bit rate weights (NBRW) with Pmax = 1 W, the transmit power, Pp, to the primary user equal to 5 W, JV0 = 10 - 8 W/Hz and HR = 1. As to be expected, it can be seen that Rs increases with Ith and that the highest bit rate is obtained when there is no NBRW are specified. For the case when there is no NBRW requirement, Rs is obtained using a slight modification of the RC algorithm. As the bit rate requirements for users become less uniform, Rs decreases due to an effective decrease in diversity. 18 17 16 ~ / * .x-' /•.•'' < — ~ P -2W - A - PP=4W _ * _ P=6W ...X... P=8W / x . . . . v..... '• >< i 0.002 0.004 0.006 0.008 0.01 0.012 lth (in Watts) Figure 3.3: Total bit rate, Rs, of 4 secondary users versus maximum tolerable inter-ference power, Ith, of the primary user with Pmax — 1 W, /Vn = 10~8 W/Hz, fj,R = 1 and identical nominal secondary user bit rate weights. identical nominal secondary user bit rate weights. It can be seen that Rs increases with HR. Fig. 3.5 shows the total bit rate, Rs, of the 4 secondary users as a function of the maximum tolerable interference power level, Ith, of the primary user for different values of the AWGN PSD, with Pmax = 1 W, Pp = 5 W and identical nominal secondary user bit rate weights. It can be seen that Ra decreases with A^ o- When the noise level is higher, the secondary users experience more noise, resulting in a degradation in Rs. Fig. 3.6 shows the total bit rate, Rs, of secondary users versus the maximum tolerable interference power, Ith, of the primary user for different number, M, of secondary users with Pmax = 1 W, Pp = 5 W, Af0 = 10~8 W/Hz, / Z R = 1 and identical nominal secondary user bit rate weights. It can be seen that for small values of Ith, Rs increase with M. For larger values of Ith, Rs seems to peak for M = 6 and 32 Figure 3.4: Total bit rate, Rs, of 4 secondary users versus maximum tolerable interfer-ence power, Ith, of the primary user with Pmax = 1 W, Pp = 5 W, N0 — 10~8 W/Hz and identical nominal secondary user bit rate weights. Figure 3.5: Total bit rate, R3, of 4 secondary users versus maximum tolerable in-terference power, Ith, of the primary user with Pmax = l W , P p = 5 W , / i j i = l and identical nominal secondary user bit rate weights. 33 decreases as M is increased further. This is due to the fact that one subcarrier can be used by at most one user, and fairness constraints may result in subcarriers with poor channel gains being allocated to same users. Fig. 3.7 shows that with no fairness constraints, Rs increases with M as a result of a larger diversity gain. 17.5 Figure 3.6: Total bit rate, Rs, of secondary users versus maximum tolerable interfer-ence power, Ith, of the primary user with Pmax = 1 W, Pp = 5 W, N0 = 10 - 8 W/Hz, — 1 and identical nominal secondary user bit rate weights. For the next set of simulation results, the parameter values are set as follows: Ith — 5 x lCT 3 W, Pmax = 1 W, Pp = 5 W, N0 = lCT 8 W/Hz and identical nominal sec-ondary user bit rate weights, NBRW=1 : 1 : 1 : 1 are used. Let bk, Pk and Ik denote respectively the number of bits loaded on subcarrier k due to the signal transmitted on subcarrier k. Table 3.1 lists the average value of bk, Pk and Ik as a function of subcarrier k. The average values are obtained using 10000 channel realizations with HR = 1. The results from Table 3.1 are also plotted in Fig. 3.8 to Fig. 3.10. It can be seen that relatively more bits and power are loaded onto the subcarriers which are relatively 34 19 0 0.002 0.004 0.006 0.008 0.01 0.012 Interference threshold of primary user(in Watts) Figure 3.7: Total bit rate, Rs, of secondary users versus maximum tolerable interfer-ence power, Ith, of the primary user with P m a x = 1 W, Pp — 5 W, NQ = 10 - 8 W/Hz, Hn = 1 and no nominal secondary user bit rate weights. farther away from the primary user band. This is because a subcarrier which is close to the primary band introduces more interference for the same loaded power. Table 3.1 also shows that ^2k Pk < Pmax and Y2k ^ < Ith as required. Table 3.2 lists the average value of bk, Pk and Ik as a function of subcarrier k assuming constant channel power gains equal to 4/7r. The results from Table 3.2 are also plotted in Fig. 3.11 to Fig. 3.13. An average over 10000 allocation periods is used since ties among users with equal fairness priorities are broken by a random selection in the RC algorithm. It can be seen that total number of bits loaded is similar to that in Table 3.1 for the nonconstant user gains. Simulation results for one sample channel realization also provide insight into the RC algorithm. The subcarrier power gains |/imfc|2 and \gk\2 are listed in Table 3.3 and shown in Fig. 3.14. The interference factor, IFk and the interference power introduced by primary user's signal into subcarrier k band at user m, Smk, are computed from 35 Table 3.1: Average values of number of bits, bk, and power, Pk, loaded onto subcar-rier k as well as interference power, Ik, seen by the primary user due to the signal transmitted on subcarrier k over 10000 channel realizations with JJLR = 1 k bk Pk h 1 4.4503 8.85E-02 6.38E-05 2 4.2572 ,8.31E-02 6.54E-05 3 4.0747 7.80E-02 7.04E-05 4 3.7871 6.66E-02 1.06E-04 5 3.4739 5.75E-02 1.82E-04 6 3.1539 5.21E-02 2.74E-04 7 2.7398 4.68E-02 4.30E-04 8 0.3128 1.57E-02 2.94E-04 9 0.3109 1.55E-02 2.96E-04 10 2.7402 4.70E-02 4.19E-04 11 3.1734 5.29E-02 2.69E-04 12 3.4619 5.68E-02 1.84E-04 13 3.8073 6.76E-02 1.05E-04 14 4.0995 7.96E-02 7.00E-05 15 4.2806 8.48E-02 6.67E-05 16 4.4606 8.92E-02 6.36E-05 Total 52.5841 0.982 2.96E-03 - < » > < » » i i < < • < < < » < » -T T -0 2 4 6 8 10 12 14 16 Figure 3.8: Average number of bits, bk, loaded per subcarrier over 10000 channel realizations with fiR — 1 36 0.1 0.09 h 0.08 „ 0.07 t/i c m g 0.06 _c 0* 0.05 | 0.04 0.03 0.02 0.01 0 0 2 4 6 8 10 12 14 16 k Figure 3.9: Average power, Pk, loaded per subcarrier over 10000 channel realizations with \IR = 1 Figure 3.10: Average interference, Ik, per subcarrier over 10000 channel realizations with JJLR = 1 37 Table 3.2: Average (over 10000 allocation periods) values of number of bits, bk, and power, Pfc, loaded onto subcarrier k as well as interference power, Ik, seen by the primary user due to the signal transmitted on subcarrier k for constant channel power gains, \hmk\2 and \gk\2, equal to 4/TT. k h Pk h 1 4.79054 1.23E-01 1.18E-04 2 4.38795 9.62E-02 1.04E-04 3 4.15695 8.56E-02 1.01E-04 4 3.44091 5.38E-02 1.09E-04 5 3.43027 5.86E-02 2.28E-04 6 2.971 4.41E-02 2.71E-04 7 2.43961 3.71E-02 4.01E-04 8 0 0 0 9 0 0 0 10 2.44809 3.73E-02 4.01E-04 11 2.92612 4.29E-02 2.64E-04 12 3.43067 5.87E-02 2.28E-04 13 3.43807 5.37E-02 1.09E-04 14 4.15655 8.56E-02 1.01E-04 15 4.38348 9.58E-02 1.03E-04 16 4.79117 1.23E-01 1.18E-04 Total 51.19 0.9952 2.66E-03 38 5 • 4.5 -4 -3.5 • i 1 1 1 1 r~ 2 21 1.5 -1 • 0.5 • 0 • 4 6 8 10 12 14 16 k Figure 3.11: Average number of bits, bk, loaded per subcarrier over 10000 channel realizations for constant channel power gains equal to 4/n. 0.14 12 14 16 Figure 3.12: Average power, Pk, loaded per subcarrier over 10000 channel realizations for constant channel power gains equal to 4/7T. 39 Figure 3.13: Average interference, Ik, per subcarrier over 10000 channel realizations for constant channel power gains equal to 4/-7T. (2.26) and (2.27) and shown in Fig. 3.15. Table 3.4 lists RC Algorithm results of bk, Pk and Ik for same channel realization gains as in Table 3.3 with identical NBRW and Fig. 3.16 shows bits loaded, bk, by the RC algorithm for one channel realization with identical NBRW given the channel gains as in Table 3.3. It shows that the subcarriers which are relatively far from the primary user band and which have higher channel gains and lower interference powers are loaded with more bits. Tables 3.5, 3.6 list results obtained using the RC algorithm and an integer pro-gramming (IP) software tool respectively for the same channel realization as in Ta-ble 3.3 but with no NBRW. It can be seen that the IP tool allows a total of 55 bits to be loaded compared to 53 for the RC algorithm. 40 Table 3.3: Power gains |/imfc|2 and \gk\2 of subcarrier Ac \h„ |2 ik 1 k m = 1 m = 2 m = 3 m = 4 1 3.2696 1.1201 0.0285 0.0285 1.066666667 2 1.4643 0.3143 0.0335 0.0335 0.705882353 3 3.6124 0.4277 0.3962 0.3962 0.537634409 4 0.6835 0.5574 0.3517 0.3517 0.9375 5 0.8245 0.2532 0.0348 0.0348 2.64516129 6 1.7045 0.9063 0.4533 0.4533 0.25 7 0.1013 0.1931 0.3499 0.3499 1.705882353 8 0.2559 1.4854 0.3177 0.3177 2.945121951 9 2.7717 2.5351 1.5518 1.5518 2.221544715 10 0.1593 0.052 0.0216 0.0216 0.411764706 11 0.2714 0.7534 0.6052 0.6052 0.354166667 12 0.3617 0.5237 0.2586 0.2586 1.419354839 13 2.4509 1.2138 0.4888 0.4888 3.125 14 1.0655 0.3891 3.3885 3.3885 0.860215054 15 1.1155 0.4223 0.8137 0.8137 1.058823529 16 0.4893 1.7369 2.3656 2.3656 1.2 2 0 2 4 6 8 10 12 14 16 18 W~ 41 1 1 1 1 1 1 ' ' 1 2 0 2 4 6 8 10 12 14 16 18 0 2 4 6 8 10 12 14 16 18 0 2 4 6 8 10 12 14 16 18 Figure 3.14: Power gains \hmk\2 and \gk\2 of subcarrier Ac 41 Figure 3.15: Interference factor, IFk and the interference power introduced by primary user's signal into subcarrier k band at user m, Smk Table 3.4: RC Algorithm results of bk, Pk and Ik for same channel realization gains as in Table 3.3 with identical NBRW k user # Pk h 1 4 4 4.16E-02 3.32E-05 2 1 4 6.28E-02 3.77E-05 3 1 5 9.81E-02 4.91E-05 4 4 3 3.28E-02 4.93E-05 5 1 2 2.08E-02 1.71E-04 6 2 4 1.11E-01 1.33E-04 7 3 2 4.28E-02 6.21E-04 8 0 0 0 0 9 0 0 0 0 10 4 1 1.01E-02 3.54E-05 11 3 4 1.37E-01 2.32E-04 12 4 2 1.15E-02 5.07E-05 13 2 4 7.84E-02 3.92E-04 14 3 6 2.03E-01 1.62E-04 15 4 3 3.39E-02 3.05E-05 16 2 5 1.12E-01 1.00E-04 Total 4 49 0.995 0.00210 42 0 0 ll L 1 i 1 1 1 0 2 4 6 8 10 12 14 16 1 8 1 1 1 0 2 4 6 8 10 12 14 16 18 -, 1 , 1 i 0 2 4 6 8 10 12 14 16 1 8 ] 1 1 , 1 " i I I 0 2 4 6 8 10 12 14 16 18 k Figure 3.16: RC Algorithm results of number of bits, bk, loaded for same channel realization gains as in Table 3.3 with identical NBRW Table 3.5: RC Algorithm results of bk, Pk and Ik for same channel realization gains as in Table 3.3 with no NBRW k user # bk Pk h 1 1 5 8.54E-02 6.83E-05 2 1 5 1.30E-01 7.78E-05 3 1 6 1.99E-01 9.97E-05 4 4 3 3.28E-02 4.93E-05 5 4 3 3.31E-02 2.72E-04 6 1 3 4.05E-02 4.86E-05 7 4 2 2.39E-02 3.47E-04 8 0 0 0 0 9 0 0 0 0 10 4 2 3.04E-02 1.06E-04 11 2 2 2.43E-02 4.13E-05 12 4 4 5.76E-02 2.53E-04 13 1 4 5.89E-02 2.94E-04 14 3 5 9.99E-02 7.99E-05 15 4 4 7.26E-02 6.54E-05 16 3 5 9.68E-02 8.71E-05 Total 4 53 0.985 0.00189 43 Table 3.6: Optimization software results of bk, Pk and Ik for same channel realization gains as in Table 3.3 with no NBRW k user # Pk h 1 1 5 8.54E-02 6.83E-05 2 1 5 1.30E-01 7.78E-05 3 1 4 4.75E-02 2.37E-05 4 4 3 3.05E-02 4.58E-05 5 4 3 3.31E-02 2.72E-04 6 4 4 8.93E-02 1.07E-04 7 4 3 5.59E-02 8.10E-04 8 0 0 0 0 9 0 0 0 0 10 4 3 7.08E-02 2.48E-04 11 3 3 6.38E-02 1.08E-04 12 4 4 5.76E-02 2.53E-04 13 1 4 5.89E-02 2.94E-04 14 3 5 9.99E-02 7.99E-05 15 4 4 7.26E-02 6.54E-05 16 3 5 9.68E-02 8.71E-05 Total 4 55 0.992 0.00254 44 Chapter 4 Cost Minimization Resource Allocation 4.1 Introduction In Chapter 3, we discussed fair resource allocation for applications which do not re-quire a prescribed bit transmission rate in a multiuser OFDM based CR system. How-ever, certain applications such as Voice over Internet Protocol (VoIP) and multimedia video require a minimum bit rate guarantees for users admitted into the system. In this chapter we study resource allocation for such applications in a multiuser OFDM based CR system. In [8], the authors consider OFDM transmission in a multiuser environment and formulate a problem of minimizing the overall transmit power by adaptively assigning subcarriers to the users along with the number of bits and power level for each sub-carrier. An algorithm is proposed which finds a suboptimal solution by allowing the number of loaded bits to be a real number. Since two Lagrange multipliers have to be found at same time, the complexity of the algorithm is 0(K4) where K is number of subcarriers. The algorithms proposed in [9,14] model the problem of minimizing 45 the total power as a nonlinear optimization problem with integer variable constraint. In [11,12], a minimization of the total power is attempted by approximately allo-cating equal power to each subcarrier. In [15], an algorithm based on greedy single user subcarrier and bit allocation algorithm to allocate the subcarriers and number of bits to each user. If a subcarrier is desired by more than one user, the algorithm assigns the subcarrier to a user appropriately so that total transmit power is min-imized. In [18], an algorithm is proposed based on the concept of marginal utility to solve the problem with a better performance than [15] at approximately the same computational complexity. The above-mentioned algorithms can be applied in conventional multiuser OFDM systems with only one type of users (e.g., secondary users) as they do not consider mu-tual interference which may arise between primary and secondary users. In contrast, the mutual interference is considered in [21] for the case of one secondary user and the throughput of the secondary user is maximized subject to a maximum interference power that can be tolerated by the primary user. In this chapter, a resource alloca-tion algorithm is proposed which minimizes a cost function which takes into account interference experienced by a primary user as well as power required to transmit to secondary users in a multiuser OFDM-based CR system with secondary user bit rate constraints. The algorithm iteratively allocates subcarriers in such a way as to reduce cost. 4.2 System Model The system model is identical to that described in Section 3.2. Recall that the total interference power seen by the primary user due to the signals destined for secondary users is Itotai (see Eq. (3.2)) and the total transmit power for signals destined to secondary users is Ptotai (see Eq. (3.3)). 46 Our objective is to minimize a weighted sum of interference and power subject to a minimum required bit rate for each secondary user. More specifically, the optimization problem is expressed as follows: subject to min Ctotai(oi) = [aItotai + (1 - a)Ptotai] (4.1) ®mk i*mk amk e {0,1}, Vrn,fc (4.2) M m=l K J2amk < 1, VAC (4.3) bmk G Z, Vm,A: (4.4) Pmk > 0, Vm,Ac (4.5) Y.amkbmk > BZ\ Vm (4.6) fc=i where denotes the minimum required number of bits per symbol period for user 77i. It is also convenient to define the minimum required bit rate, RTrntq, of user m as Rmtq = W3Bmzq. The total minimum bit rate for all secondary users is Rrseq = ]Cm=i RTm- Inequality (4.3) follows from the assumption that a subcarrier can be allocated to at most one user, whereas (4.6) guarantees a minimum bit rate for each secondary user. The term a 6 [0,1] is a parameter which indicates the relative importance of power and interference. Increasing a implies that interference reduction is relatively more important than power savings. 4.3 Proposed Algorithm An optimal solution to the optimization problem in (4.1) is computationally complex and may not suitable for wireless communications systems in which channel condi-tions are constantly changing. In this section, a suboptimal algorithm with reduced computational load is proposed. Its performance is discussed in Section 4.4. 47 4.3.1 M a x i m a l Cost Reduction by a New Subcarrier In [18], the marginal utility of a new subcarrier j for user m refers to the maximal power reduction possible if subcarrier j is assigned to user m. We extend this concept and define the marginal cost reduction as the maximal reduction in Ctotai{ot) possible if subcarrier j is assigned to user m. From (3.1), the power savings gained by reducing one bit on subcarrier k for user m is given by A P " , = N ° W * + ^ 2 ^ - \ (4.7) \lhnk\ and from (2.26), the resulting interference power reduction to the primary user is A / " f e = AP-k IFk. (4.8) From (3.1), the increase in BS transmit power needed to support one additional bit on subcarrier k for user m is given by AP-k = N ° W s + " m k 2 ^ , (4.9) and from (2.26), the resulting increase in interference power to the primary user is AI+k = AP+kIFk. (4.10) Let Lm denote the number of subcarriers already allocated to user m. Let bmi, Pmi and Imi denote the current number of bits, transmit power and interference power for the Ith (1 < I < Lm) subcarrier of user m respectively. The proposed algorithm reassigns bits of user m to a (new) available subcarrier only if such a reassignment results in a reduction in the cost C t o t o i ( a ) . The marginal cost reduction achievable by transferring bits from existing sub-carriers of user m to an available (unused) subcarrier j can be calculated as follows: *** Algorithm I 48 1. Step 1 - Initialization (a) For each subcarrier lm(l < I < Lm) currently used by user m, calculate the power reduction possible A P ~ ( and A / ~ ; while reducing one bit from subcarrier I as in (4.7) and (4.8) respectively. The cost reduction is A C ~ ; = a A 7 ^ + (1 — a)AP~ ( . (b) Set b m j = 0, ACZL = 0, calculate A P * • and A I m j for increasing one bit on the subcarrier j of user m as in (4.9) and (4.10) respectively. The cost is A C * = aAImj + (1 - a )AP+, 2. Step 2 (a) Determine I* = argmax; A C ~ ( for I E {1,2,..., Lm}. (b) If AC~j . < ACmj, go to step 3. Otherwise, transfer one bit from subcarrier I* of user m to subcarrier j (which is available) and by performing following updates : bml* = bml* 1) bmj b m j -\- 1, ACZL = ACZL + (AC-lt - ACmj), calculate AP~t, as in (4.7) and A / ~ , , as in (4.8), set A C - ( . = a A J - z , + (1 - « ) A P ; , , calculate AP^ as in (4.9) and AI+j as in (4.10), set A C + ^ a A / ^ . + U - c O A P ^ , and go to step 2a). 3. Step 3 The marginal cost reduction of subcarrier j to user m is AC^al and bmi is the loaded bits on subcarrier I of user m, for I E {1, 2 , . . . , L m + 1}. 49 4.3.2 Proposed Resource Allocation Algori thm The proposed resource allocation algorithm is based on the marginal cost reduction of a subcarrier. The goal is to minimize the total cost C t o t a;(a) while satisfying the minimum bit rate requirements of the secondary users. Towards this end, a subcarrier with largest marginal cost reduction is allocated to the corresponding user until there is no further cost reduction possible *** Algorithm II *** 1. If M > K, declare no feasible solution and stop. Otherwise go on. 2. Initialization (a) Set bmk = 0, for m € {1,2,.. . , M} and k e {1,2,.. . , K}. (b) SetU = {l,...,K}. (c) V m k = a(NoW£SkfIFk + (1 ~ a)iN°Z+Jmh)> for m E { M . - - - . ^ } a n d ke {1,2,. . . , i f}. 3. While (a) Determine (m*,k*) = argmnw Vmk-(b) Set 6m. f e. = B™?, U = U -{k*}. (c) Set Vm.k = 00, for k € {1,2,..., K}, Vmk* = oo, for m £ {1,2,..., M}. 4. Set AC?Jal = 0,\/rn,k$U. Run Algorithm I to compute AC£^ , Vm, k e C/. 50 5. While maxm f c AC^al > 0 (a) Determine (m*,k*) = arg max^ A CJ^al, for m 6 {1,2, . . . , M } and k € {1,2,...,AT>. (b) Run Algorithm I to update bm*k, for k € U. (c) Set U = U - {k*}, ACrZ = 0, for m € {1,2,.. . , M}. (d) Run Algorithm I to compute AC^ah for m e {1, 2 , . . . , M} and k eU. 6. Compute 7 t o t a ( , F t o t a ; as in (3.3) and (3.2), compute altotai + (1 - a)Ptotai-In the algorithm, U represents the set of currently available (unused) subcarriers and Vmk is the cost if one bit is loaded for user m on a currently empty subcarrier k. In step 3), exactly one subcarrier is assigned to each user with a non-zero bit rate requirement and all the bits of any given user are loaded onto its assigned subcarrier. In step 5), a (user, unassigned subcarrier) pair with maximal cost reduction is selected and some of the bits loaded onto currently assigned subcarriers of the user will be redistributed using Algorithm I. This step is repeated until no further reduction in Ctotai{a) is possible. 4.4 Simulation Results In this section, average total cost, C t o t a/(a), results for the proposed algorithm, ob-tained using computer simulations, are provided. The performance of the algorithm relative to the optimal solution is also discussed. We consider a system with one primary and M secondary users. The secondary users have identical minimum bit rate weight (BRW) requirements, i.e., PJ^ — Rrseq/M, unless otherwise specified. The secondary user band is 5 MHz wide and 51 consists of 16 subcarriers, each with a bandwidth, Ws, of 0.3125 MHz. The primary user bandwidth is Wp = Ws and the symbol duration is Ts = 4 fis. It is assumed that the subcarrier gains hmk and gk, for m € {1,2,.. . , M}, k 6 {1,2,.. . , K} are outcomes of independent, identically distributed (i.i.d.) Rayleigh random variables (rv's) with means equal to 1. The additive white Gaussian noise (AWGN) PSD, No, is set to 10 - 8 W/Hz. The PSD, $RR.(ejw), of the signal transmitted to the primary user is assumed to be that of an elliptically filtered white noise process. The Ctotai(&) results are obtained by averaging over 10,000 channel realizations. In Fig. 4.1, the average cost function Ctotai(a) value obtained using the proposed algorithm is plotted as a function of the total minimum bit rate, Rr3eq, requirement for 4 secondary users with a = 250/251. As expected, it can be seen that Ctotai(ot) increases with Rrseq. In order to assess the performance of the proposed algorithm, an integer pro-gramming optimization software package was used to solve the problem in (4.1). However, the long computational time allowed only 10 channel realizations to be used. It was found that among the 10 channel realizations, the total cost obtained using the proposed algorithm was 3.5% higher than the optimal solution in the worst case. Averaged over the 10 channel realizations, the difference was 2.2%. Fig. 4.2 shows the average cost function Ctotai(a) value as a function of the total minimum bit rate, Rrseq, requirement for 4 secondary users with a — 250/251 and different BRW for secondary users. As to be expected, it can be seen that Ctotai increases with Rrseq and that the lowest cost is obtained when BRW is uniform. As the bit rate requirements for users become less uniform, Ctotai increases due to an effective decrease in diversity. Fig. 4.3 shows the BS transmit power, Ptotal, for secondary users and the interfer-ence power, Itotai, experienced by the primary user as a function of a assuming that 52 0.025 0.02 r 0.005 k 31 L _ 1 1 1 • 1 12 14 16 18 20 22 24 26 Ffeq (in Mbps) Figure 4.1: Total system cost, Ctotai, versus total required transmit bit rate, Rrseg, of 4 secondary users with uniform BRW and a = 250/251. 0.1 5 10 15 20 25 30 35 Ff°q (in Mbps) Figure 4.2: Total system cost, Ctotai, versus total required transmit bit rate, Rrseq, of 4 secondary users with different BRW and a = 250/251. 53 the total bit rate, Rr3eq, required by 4 secondary users is 18.75 Mbps. As a increases, so does Ptotai whereas Itotai decreases. 1.8 1 2I 1 1 1 1 . 1 lo 0 0.2 0.4 0.6 0.8 1 a value Figure 4.3: Total power required, Ptotai, by secondary users and interference, Itotai, introduced to primary user versus a value with the total required bit rate for 4 secondary user Rrseq = 18.75 Mbps and uniform BRW. For the following simulations results, a total minimum bit rate, Rrseq — 18.75 Mbps, requirement for 4 secondary users with a = 250/251 and identical minimum bit rate weight (BRW) requirements are assumed. Let bk, Pk, h and Ck denote the number of bits loaded, required transmit power for secondary user, interference power expe-rienced by the primary user due to secondary user signal and cost for subcarrier k respectively. Table 4.1 and Figs. 4.4 to 4.7 show that average value of bk, Pk, h and Ck over 10000 channel realizations. As expected, the average number of bits, bk, loaded and the average power, Pk, on subcarrier k, increase with the spectrum distance to the primary user band. The reason is that a subcarrier which is far away from the primary user band will introduce less interference to the primary user than one closer to the 54 primary user band if both subcarriers have equal allocated power. Table 4.1: Average values of number of bits, bk, and power, Pk, loaded onto subcarrier k as well as interference power, Ik, seen by the primary user due to the signal trans-mitted on subcarrier k and cost, Ck, on subcarrier k over 10000 channel realizations with HR = 1 k bk Pk h Ck 1 5.2196 1.38E-01 1.12E-04 6.60E-04 2 5.0489 1.34E-01 1.19E-04 6.53E-04 3 4.8841 1.31E-01 1.27E-04 6.46E-04 4 4.5499 1.14E-01 1.76E-04 6.30E-04 5 4.0237 9.25E-02 2.41E-04 6.08E-04 6 3.4717 7.56E-02 2.72E-04 5.72E-04 7 2.6925 5.49E-02 2.92E-04 5.09E-04 8 0.1193 6.31E-03 2.05E-05 4.55E-05 9 0.1083 5.80E-03 1.83E-05 4.14E-05 10 2.6841 5.45E-02 2.93E-04 5.09E-04 11 3.4752 7.60E-02 2.74E-04 5.75E-04 12 4.0055 9.16E-02 2.42E-04 6.06E-04 13 4.5544 1.15E-01 1.76E-04 6.34E-04 14 4.8942 1.30E-01 1.28E-04 6.47E-04 15 5.0521 1.34E-01 1.21E-04 6.55E-04 16 5.2165 1.38E-01 1.11E-04 6.59E-04 Total 60 1.491 0.00272 0.00865 Table 4.2 and Figs. 4.8 to 4.11 shows the number of loaded bits, bk, for a constant channel gain case. As expected, bk increase with the spectrum distance to the primary user band. Since there is no diversity of channel gains, the allocation for subcarriers will depend on the spectrum distance to the primary user band. Note that Fig. 4.8 shows that subcarriers 13 and 14 carrying 5 bits each; since subcarrier 13 is closer to the primary user band than subcarrier 14, the power on subcarrier 13 is higher than that of subcarrier 14 as can be seen in Fig. 4.9. Simulation results for one sample channel realization also provide insight into the cost minimization algorithm. The subcarrier power gains \hmk\2 and \gk\2 are listed in Table 4.3 and shown in Fig. 4.12. The interference factor, IFk and the interference 55 6 4 •Q q 5 8 10 12 14 Figure 4.4: Average number of bits, bk, loaded per subcarrier over 10000 channel realizations with (j,R — ^ 0.14 0.12 0.1 « c 0.08 I 0.06 0.04 0.02 8 10 12 14 16 k Figure 4.5: Average power, Pk, loaded per subcarrier over 10000 channel realizations with fJ,R = 1 56 S5 x 10 T l 8 10 12 14 16 k Figure 4.6: Average interference, Ik, per subcarrier over 10000 channel realizations with fj,R = 1 ( » ( 1 ( 1 i » < » ( » I < » < • < » — i • -T T -0 2 4 6 8 10 12 14 16 k Figure 4.7: Average cost, Ck, per subcarrier over 10000 channel realizations with = 1-57 Table 4.2: Values of number of bits, bk, and power, Pk, loaded onto subcarrier k as well as interference power, Ik, seen by the primary user due to the signal transmitted on subcarrier k for constant channel power gains, |/imfc|2 and \gk\2, equal to 4/TT. k user# bk Pk h Ck 1 1 6 2.68E-01 2.56E-04 1.32E-03 2 3 5 1.40E-01 1.51E-04 7.06E-04 3 3 5 1.47E-01 1.74E-04 7.60E-04 4 1 5 1.58E-01 3.21E-04 9.50E-04 5 1 4 8.41E-02 3.27E-04 6.61E-04 6 3 3 4.48E-02 2.76E-04 4.53E-04 7 3 2 2.34E-02 2.53E-04 3.45E-04 8 0 0 0 0 0 9 0 0 0 0 0 10 4 2 2.34E-02 2.53E-04 3.45E-04 11 4 3 4.48E-02 2.76E-04 4.53E-04 12 2 4 8.41E-02 3.27E-04 6.61E-04 13 2 5 1.58E-01 3.21E-04 9.50E-04 14 4 5 1.47E-01 1.74E-04 7.60E-04 15 4 5 1.40E-01 1.51E-04 7.06E-04 16 2 6 2.68E-01 2.56E-04 1.32E-03 Total 4 60 1.731 0.00352 0.0104 I [— •E 3 - • — • -0 2 4 6 8 10 12 14 16 k Figure 4.8: Number of bits, bk, loaded per subcarrier for constant channel power gains equal to 4/rr. 58 0.25 0.15 0.05 Figure 4.9: Power, Pk, loaded per subcarrier for constant channel power gains equal t O 4/7T. 3.5 2.5 X 10" S 2 CO g c ^ 1.5 0.5 0 2 4 - • — • -8 10 12 14 16 k Figure 4.10: Interference, Ik, per subcarrier for constant channel power gains equal to 4 / TT . 59 x 10"' Figure 4.11: Cost, Ck, per subcarrier for constant channel power gains equal to 4/TT. power introduced by primary user's signal into subcarrier k band at user ?7i, Smk, are shown in Fig. 4.13. Table 4.4 lists cost minimization algorithm results of bk, Pk, h and Ck for same channel realization gains as in Table 4.3 and Fig. 4.14 shows the number of bits, bk, loaded for same channel realization given in Table 4.3. It can be observed that more bits are allocated to subcarriers with higher channel gains and more distance to the primary user band. 60 Table 4.3: Power gains |fomfc|2 and \gk\2 of subcarrier k \K |2 k | k m — 1 m = 2 m = 3 m = 4 9k 2 1 0.7978 1.0967 1.105 1.9659 1.733333333 2 0.3041 1.5026 1.4111 4.8599 0.470588235 3 0.6567 6.792 0.4001 1.908 0.967741935 4 0.5636 0.5215 0.6929 0.0849 0.1875 5 1.1499 1.2774 0.3847 0.0576 5.258064516 6 0.6636 0.2516 1.3921 0.7334 0.583333333 7 0.6688 1.5011 0.479 0.4795 1.376470588 8 1.4466 2.7116 0.0526 1.6703 4.776422764 9 0.2655 0.9286 3.4747 1.2998 0.193089431 10 2.1545 0.8001 0.0334 0.9012 2.552941176 11 1.991 2.6844 0.6031 1.2403 0.041666667 12 1.215 0.5384 0.9744 0.3345 1.096774194 13 2.2001 1.2498 0.1159 1.8746 0.3125 14 2.2413 1.8125 0.8786 0.1137 0.752688172 15 2.4599 0.0369 1.5414 0.316 2.235294118 16 0.5244 1.4083 0.87 1.7632 0.666666667 Figure 4.12: Power gains \hmk\2 and \gk\2 of subcarrier k 61 Smk 0.1 m = 1 0.05 h 0 Smk 0.2 m = 2 0 1 0 Smk 0.2 m=3 0 2 0 2 0.1 r 0 Sm * 0.1 0.05 0 I 0.4 0.2 0 0 2 m=4 IF, 0 2 8 10 1 2 14 16 1£ 8 10 1 2 14 16 18 8 10 1 8 10 1 2 14 16 1£ 2 14 16 18 0 2 4 6 8 10 1 k 2 14 16 18 Figure 4.13: Interference factor, IFk and the interference power introduced by primary user's signal into subcarrier k band at user m, Smk Table 4.4: Cost Minimization algorithm result of bk, Pk, Ik and Ck for same channel realization gains as in Table 4.3 k user # &fc Pu h Cfc 1 4 5 1.05E-01 1.37E-04 5.55E-04 2 4 6 1.70E-01 6.79E-05 7.44E-04 3 2 6 1.74E-01 1.56E-04 8.49E-04 4 3 5 2.22E-01 6.66E-05 9.51E-04 5 2 2 1.68E-02 2.74E-04 3.39E-04 6 2 2 4.91E-02 1.38E-04 3.33E-04 7 4 2 3.56E-02 4.17E-04 5.57E-04 8 0 0 0 0 0 9 0 0 0 0 0 10 4 2 2.65E-02 5.74E-04 6.77E-04 11 2 5 1.59E-01 3.17E-05 6.63E-04 12 1 4 8.58E-02 2.92E-04 6.33E-04 13 1 5 1.26E-01 6.31E-05 5.66E-04 14 1 6 2.33E-01 1.63E-04 1.09E-03 15 3 5 1.26E-01 2.40E-04 7.43E-04 16 3 5 1.67E-01 8.36E-05 7.49E-04 Total 4 60 1.695 0.00270 0.00945 62 b k 10 m=1 r —i r-0 2 4 6 8 10 12 14 16 18 b„ 1 0 k m=2 _ o 0 m=3 -i r-0 2 4 6 8 10 12 14 16 18 I I 1 IE 0 2 4 8 10 12 14 16 18 k m=4 10 _j i_ 0 2 4 8 10 12 14 16 18 k Figure 4.14: Cost Minimization Algorithm results of number of bits, bk, loaded for same channel realization gains as in Table 4.3 63 Chapter 5 Conclusions and Suggestions for Future Work The problem of dynamic loading of subcarriers, power, and bits in a multiuser O F D M cognitive radio system was studied. In this chapter, we summarize the main contri-butions of this thesis and provide some suggestions for further study. 5 .1 Contributions of the Thesis 1. New optimization models for fair adaptive resource allocation and minimum cost resource allocation for multiuser O F D M C R systems were formulated. 2. A low complexity (RC) algorithm for allocating resources on the downlink of a multiuser O F D M C R system in which there is no minimum user bit rate requirements was proposed. The objective is to maximize the total bit rate, Ra, of secondary users given constraints on the total power available to the BS for transmission to secondary users and on the interference that the primary user can tolerate. The algorithm is fair in the sense that it tries to allocate bits to users who have not received their fair share of service as much as possible. It is 64 found that the algorithm has a much lower computational complexity than an optimal algorithm but still provides a Rs performance which is close to optimal. The effect of changing various system parameter values on the performance of the algorithm was also studied. 3. A sub-optimal algorithm for allocating resources on the downlink of a multiuser OFDM CR system in which there is a set of minimum user bit rate requirements was proposed. The objective is to minimize a cost function which takes into account the interference power, Itotah experienced by the primary user as well as the base station transmit power, Ptotal, for secondary users, given minimum bit rate requirements for each secondary user. It is found that the proposed algorithm provides a performance which is fairly close to optimal. The influence of the relative weight parameter, a, on Itotai and Ptotai was also discussed. .2 Future work • The two algorithms proposed in this thesis are based on the assumptions that the wireless channel does not change much during each resource allocation time and perfect channel information is available. In practice, channel estimation errors are inevitable. In corporation of imperfect channel estimation and/or fast fading would represent an interesting extension to the present work. • In this thesis we proposed a resource allocation algorithm for a multiuser OFDM CR system in which there is no minimum user bit rate requirements and one for a multiuser OFDM CR system in which there is a set of minimum user bit rate requirements. In future wireless communication system, many different types of applicants will be supported. The design of resource allocation algorithms in such systems is an important issue. 65 • It is widely recognized that multiple-input multiple-output (MIMO) antenna architectures can increase the spectral efficiency of wireless communication sys-tems [29]. OFDM can also be combined with MIMO antenna at the transmitter and receiver to increase the a diversity gain and to enhance the system capac-ity [30]. It would be useful to study the benefits of MIMO in the design of adaptive resource allocation algorithms for OFDM based CR systems. 66 Bibliography [1] T. S. Rappaport, Wireless Communications: Principles and Practice, 2nd ed. Prentice-Hall, 2001. [2] M. Steer, "Beyond 3G," IEEE Microwave Magazine, vol. 8, no. 1, pp. 76-82, Feb. 2007. [3] I. Lee et ai, "Guest Editorial 4G Wireless Systems," IEEE Journal on Selected Areas in Communications, vol. 24, no. 3, pp. 413 - 418, March 2006. [4] Federal Communications Commission, "Spectrum Policy Task Force," Report of ET Docket 02-135, Nov. 2002. [5] S. Haykin, "Cognitive radio: brain-empowered wireless communications," IEEE Journal on Selected Areas in Communications, vol. 23, no. 2, pp. 201-220, Feb. 2005. [6] H. Tang, "Some physical layer issues of wide-band cognitive radio systems," in Proc. of IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks, DySPAN 2005, Nov. 2005, pp. 151 - 159. [7] T. Weiss et al, "Mutual interference in OFDM-based spectrum pooling systems," in Proc. of IEEE Vehicular Technology Conference, VTC 2004-Spring, vol. 4, May 2004, pp. 1873 - 1877. 67 [8] C. Y . Wong et ai, "Multiuser OFDM with adaptive subcarrier, bit, and power allocation," IEEE Journal on Selected Areas in Communications, vol. 17, no. 10, pp. 1747 - 1758, Oct. 1999. [9] S. Pietrzyk and G. M. Janssen, "Multiuser subcarrier allocation for QoS provision in the OFDMA systems," in Proc. of IEEE Vehicular Technology Conference, VTC 2002-Fall, vol. 2, Sept. 2002, pp. 1077 - 1081. [10] A. Wang et ai, "Asymptotic analysis of fair scheduling in the OFDM systems," in Proc. of IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC 2003, vol. 2, Sept. 2003, pp. 1186 - 1191. [11] J. Jang and K. B. Lee, "Transmit power adaptation for multiuser OFDM sys-tems," IEEE Journal on Selected Areas in Communications, vol. 21, no. 2, pp. 171 - 178, Feb. 2003. [12] Y. Teng et al., "Proposal of adaptive subchannel and bit allocation method for OFDM access wireless LAN systems," in Proc. of IEEE Vehicular Technology Conference, VTC 2003-Spring, vol. 2, April 2003, pp. 910 - 914. [13] H. Kim et al., "A proportional fair scheduling for multicarrier transmission sys-tems," in Proc. of IEEE Vehicular Technology Conference, VTC 2004-Fall, vol. 1, Sept. 2004, pp. 409 - 413. [14] C. Y. Wong et ai, "A real-time sub-carrier allocation scheme for multiple access downlink OFDM transmission," in Proc. IEEE VTS 50th of Vehicular Technology Conference, 1999. VTC 1999 - Fall, vol. 2, Sept. 1999, pp. 1124 - 1128. [15] G. Zhang, "Subcarrier and bit allocation for real-time services in multiuser OFDM systems," in Proc. of IEEE International Conference on Communica-tions, vol. 5, June 2004, pp. 2985 - 2989. [16] I. C. Wong et al., "A low complexity algorithm for proportional resource allo-cation in OFDMA systems," in Proc. of IEEE Workshop on Signal Processing Systems, SIPS 2004, 2004, pp. 1 - 6. [17] Z. Shen et al., "Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints," IEEE Transactions on Wireless Communications, vol. 4, no. 6, pp. 2726 - 2737, Nov. 2005. [18] G. Yu et al, "A Novel Resource Allocation Algorithm for Real-time Services in Multiuser OFDM systems," in Proc. of IEEE Vehicular Technology Conference, VTC 2006-Spring, vol. 3, May 2006, pp. 1156 - 1160. [19] C. Mohanram and S. Bhashyam, "A sub-optimal joint subcarrier and power al-location algorithm for multiuser OFDM," IEEE Communications Letters, vol. 9, no. 8, pp. 685 - 687, Aug. 2005. [20] G. Yu et al, "Subcarrier and bit allocation for OFDMA systems with propor-tional fairness," in Proc. of IEEE Wireless Communications and Networking Conference, WCNC 2006, vol. 3, April 2006, pp. 1717 - 1722. [21] G. Bansal, M. J. Hossain, and V. K. Bhargava, "Adaptive Bit and Power Loading for OFDM-based Cognitive Radio Systems," to be presented at IEEE Interna-tional Conference on Communications, 2007. [22] J. G. Proakis, Digital communications, 4th ed. New York: McGraw-Hill, 2000. [23] W. C. Lee, Mobile Cellular Telecommunications Systems. New York: McGraw-Hill, 1989. [24] R. van Nee and R. Prasad, OFDM for Wireless Multimedia Communications, 1st ed. Artech House, Inc, 2000. 69 [25] J. G. Proakis and M. Salehi, Communication Systems Engineering, 2nd ed. Prentice Hall, 2001. [26] T. Keller and L. Hanzo, "Adaptive multicarrier modulation: a convenient frame-work for time-frequency processing in wireless communications," Proceedings of the IEEE, vol. 88, no. 5, pp. 611 - 640, May 2000. [27] J. Mitola and G. Q. Maguire, "Cognitive radio: making software radios more personal," IEEE Personal Communications, vol. 6, no. 4, pp. 13 - 18, Aug. 1999. [28] J. Mitola, "Cognitive radio: An integrated agent architecture for software defined radio," Ph.D. dissertation, Royal Institute of Technology (KTH), Stockholm, Sweden, 2000. [29] S. Haykin and M. Moher, Modern Wireless Communications. New York: Pren-tice Hall, 2004. [30] G. L. Stiiber et ai, "Broadband MIMO-OFDM wireless communications," Pro-ceedings of the IEEE, vol. 92, no. 2, pp. 271 - 294, Feb. 2004. 70