Dynamic Resource Allocation for Cognitive Radio Systems by Ziaul Hasan Hashmi B.Tech, Indian Institute of Technology, Kanpur, 2005 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Applied Science in The Faculty of Graduate Studies (Electrical and Computer Engineering) The University Of British Columbia (Vancouver) June, 2008 c Ziaul Hasan Hashmi 2008 Abstract Cognitive Radio (CR) is considered to be a novel approach to improve the underutilization of precious radio resources by exploiting the unused licensed spectrum in dynamically changing environments. Designing efficient resource allocation algorithms for dynamic spectrum sharing and for power allocation in OFDM-CR networks is still a challenging problem. In this thesis, we specifically deal with these two problems. Dynamic spectrum sharing for the unlicensed secondary users (SU)s with device coordination could minimize the wastage of the spectrum. But this is a feasible approach only if the network considers the fairness criterion. We study the dynamic spectrum sharing problem for device coordinated cognitive radio networks with respect to fairness. We propose a simple modified proportional fair algorithm for a dynamic spectrum sharing scenario with two constraints, time and utility. Utility is measured by the amount of data processed and time is measured as the duration of a slot. This algorithm could result in variable or fixed length time slots. We will discuss the several controls possible on the algorithm and the possible extension of this algorithm for multicarrier OFDM based CR systems. Traditional water-filling algorithm is inefficient for OFDM-CR networks due to the interaction with primary users (PU)s. We consider reliability/availability of subcarriers or primary user activity for power allocation. We model this aspect mathematically with a risk-return model by defining a general rate loss function. We then propose optimal and suboptimal algorithms to allocate power under a fixed power budget for such a system with linear rate loss. These algorithms as we will see allocate more power to more reliable subcarriers in a water-filling fashion with different water levels. We compare the performance of these algorithms for our model with respect to water-filling solutions. Simulations show that suboptimal schemes perform closer to optimal scheme although they could be implemented with same complexity as water-filling algorithm. We discuss the linearity of loss function and guidelines to choose its coefficients by obtaining upper bounds on them. Finally we extend this model for interference-limited OFDM-CR systems. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Cognitive Radio Features . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 3 List of Symbols . . . . . . . . . . . . 5 5 6 7 9 10 10 11 11 11 12 13 3 Power Allocation for OFDM-CR System Based on PU Activity . 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Optimal Power Allocation for Cognitive Radios Based on Sub-channel Availability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 A Risk-Return Model for Power Allocation . . . . . . . . . . 3.3.2 Optimal Power Allocation for Linear Rate Loss . . . . . . . . 20 20 21 2 Dynamic Spectrum Sharing for Cognitive Radio 2.1 Introduction . . . . . . . . . . . . . . . . . . . . 2.2 Proportional Fair Allocation . . . . . . . . . . . 2.3 System Model . . . . . . . . . . . . . . . . . . . 2.3.1 Algorithm . . . . . . . . . . . . . . . . . . 2.4 Various Comments . . . . . . . . . . . . . . . . . 2.4.1 Time and Utility Controls . . . . . . . . . 2.4.2 Decentralized Cooperative Networks . . . 2.4.3 Utility Measure . . . . . . . . . . . . . . . 2.4.4 Variable Discrete Slotted Time . . . . . . 2.4.5 Multicarrier Systems . . . . . . . . . . . . 2.5 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 22 24 iii Table of Contents 3.4 3.5 3.6 Suboptimal Schemes for Power Allocation Based on Sub-channel Availability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Scheme 1: Relative Water Levels . . . . . . . . . . . . . . . . 3.4.2 Scheme 2: Proportional Water Levels . . . . . . . . . . . . . Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Simulation Parameters and Assumptions . . . . . . . . . . . . 3.5.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . Discussions on the Loss Function . . . . . . . . . . . . . . . . . . . . 3.6.1 Other Forms of Loss function . . . . . . . . . . . . . . . . . . 26 26 27 27 27 29 30 31 4 Power allocation for Interference Constrained OFDM-CR system 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 System Model for Interference Limited Secondary User System . . . 4.2.1 Sub-channel Power Constraint . . . . . . . . . . . . . . . . . 4.2.2 Interference Constraint due to Co-located Primary User Bands 4.3 Optimal Power allocation for Interference-limited OFDM-CR system 4.3.1 Risk-return model for Power Allocation . . . . . . . . . . . . 4.3.2 Optimal Power allocation for Interference-limited OFDM-CR system with Linear Rate Loss . . . . . . . . . . . . . . . . . . 4.4 Suboptimal Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 35 35 36 39 40 40 40 5 Future Work and Conclusions . . . . . . . . . . . . . . . . . . . . . . 5.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 46 47 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 42 45 Appendices A Proof of Proposition 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 B Proof of Preposition 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 iv List of Figures 2.1 2.2 Time Controlled: Throughputs of users . . . . . . . . . . . . . . . . . Utility Controlled: Throughputs of users . . . . . . . . . . . . . . . . 15 16 2.3 2.4 2.5 Time & Utility Controlled: Throughputs of users . . . . . . . . . . . System Throughputs . . . . . . . . . . . . . . . . . . . . . . . . . . . Slot lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 18 19 3.1 3.2 Opportunistic spectrum in an OFDM-based CR system . . . . . . . . 21 A snapshot of simulation results for different power allocation schemes. 28 3.3 3.4 3.5 Expected capacity vs. rate loss/unit power (C). . . . . . . . . . . . . Allocated power vs. primary user activity (α1 ). . . . . . . . . . . . . Expected capacity vs. primary user activity (α1 ). . . . . . . . . . . . 32 33 34 4.1 4.2 A Typical Cognitive Radio System Model . . . . . . . . . . . . . . . Opportunistic spectrum in an OFDM-based CR system with side by 37 side PU bands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 v List of Symbols λi ri : : Average rate or throughput for user i Instantaneous transmittable data rate at the current time slot of user i Nu W i, j, k, n : : : Number of transmitting-receiving pairs of secondary user nodes Fixed licensed Bandwidth Indexes tk N0 : : Length of time slot just before the decision time instant k Power spectral density for background additive Gaussian noise hi,k ri,k ηi : : : Channel gain at transmitter for user i and time instant k Maximum achievable rate for user i at time instant k Fraction of capacity guaranteed for user i pi Tmax : : Transmit power of user i Maximum time slot length θmax λi,k Λk : : : Maximum channel utilization limit Throughput for user i at time instant k Overall system throughput at time instant k bi,k ∗ ri,k : : Channel assignment binary index at time slot k for user i True rate for user i at time instant k ρi,n ρ κi : : : Priority for user i at time instant n Priority value Tuning parameter for user i α, κ, β ravg M : : : Tuning parameters Average rate Maximum time slot factor Tmin ⌊·⌋ : : Minimum time slot size Largest integer less than or equal to · Nc : Number of subcarriers vi List of Symbols Φn : Priority matrix at time instant n v ρi,j,n ri,j,n : : : Allocation vector Priority for user i over subcarrier j at time instant n Maximum achievable rate for user i in subcarrier j at time instant k E{|h|2 } : M : Average channel power gain Number of sub-channels N αj ϕ(·) : : : Number of subcarriers Probability that channel gets reoccupied by j PU Mapping function over subcarrier index · to PU index Z+ B : : Set of Positive integers Subcarrier bandwidth Pi hi ri : : : Power allocated over subcarrier i Channel gain at transmitter of SU for subcarrier i Maximum achievable rate in subcarrier i η Ti T : : : Fraction of capacity guaranteed by transceiver pairs of SU Time for which SU was able to use subcarrier i Total time frame ∆ri Ri : : Rate loss over subcarrier i True rate achieved L(·) E{Ri } C : : : Average rate loss for invested power · Expected rate over subcarrier i Normalized average cost per unit power P Ptotal : : Power allocation vector Total power budget [·]+ λ τ, ν : : : Equivalent to max{0, ·} Threshold constant/Lagrange multiplier for power budget Design parameters Pimax ′ Ptotal : : Power for which E{Ri } is maximum Re-adjusted power budget S PT d : : : SU’s total transmission power Interference power limit at the margin of protection area Distance between SU and PU transmitters n : Path attenuation factor vii List of Symbols R : Radius of protection area Sj PjT dj : : : SU’s total transmission power over sub-channel j Interference power constraint set by jth primary user Distance between SU and jth PU transmitters nj Rj : : Path attenuation factor between SU and jth PU transmitters Radius of protection area for the jth PU Wl L Ji : : : Bandwidth of lth PU band Number of PU bands Total interference generated on SU by PUs over jth subcarrier Tj Iil : : Power constraint on jth sub-channel Interference introduced by the ith subcarrier on lth PU band dil ψ(f ) kil : : : distance in frequency between ith subcarrier and lth PU band Power spectral density per unit power in frequency f Factor which depends on interrelated parameters between ith Ki Ith : : subcarrier and lth PU band Summation of kil factors over L PU bands Total interference threshold prescribed by L PU bands δ γj : : Lagrange multiplier for total interference constraint on L PU bands Lagrange multiplier for total power over sub-channel j µi wi Pi∗ : : : Lagrange multiplier for positive power constraint on subcarrier i Threshold level for subcarrier i Optimum power allocation for subcarrier i |S| : Cardinality of set S viii List of Abbreviations CR DSA DSS : : : Cognitive Radio Dynamic Spectrum Access Dynamic Spectrum Sharing PU SU : : Primary/Licensed User Secondary/Unlicensed User OFDM : OFDMA : SNR : Orthogonal Frequency Division Multiplexing Orthogonal Frequency Division Multiple Axis Signal to Noise Ratio SDR FCC : : Software Defined Radio Federal Communications Commission QoS : Quality of Service ix Acknowledgement First and foremost, I would like to thank my supervisor, Prof Vijay K. Bhargava, for his guidance, encouragement and support. I would also like to thank Prof. Ekram Hossain for clarifying all my doubts, contributing valuable suggestions and constant support to my thesis work. Finally, I express my gratitude and appreciation to all the members of our lab for their insightful inputs and for providing friendly as well as intellectually challenging environment which helps to learn and stimulates creativity. Special thanks to my parents, whose have supported me throughout my years of education in every possible way. This research was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) under a Strategic Project Grant. x Chapter 1 Introduction The electromagnetic radio spectrum is one of the most precious and scarce natural resource. Wireless networks today follow a fixed spectrum assignment strategy, the use of which is licensed by government agencies. This results in a large portion of assigned spectrum being used only intermittently or not at all due to various factors such as amount of traffic load on licensed users or geographical variations [1]. Actual measurements by FCC [2] support this fact by showing a severe underutilization of the licensed spectrum by the licensed or primary user (PU). Due to limited availability of radio spectrum and high inefficiency in its usage, new insights into the use of spectrum have challenged the traditional approaches to spectrum management. This necessitates a new communication paradigm to harness the underutilized wireless spectrum by accessing it opportunistically. This new communication technology is referred as Dynamic Spectrum Access(DSA) or Cognitive Radio(CR). Derived from J.Mitola’s doctoral thesis [3], a cognitive radio is an intelligent wireless communication system that relies on opportunistic communication between unlicensed or secondary users (SU)s over temporarily unused spectral bands that are licensed to their PUs. The FCC suggests that any radio having adaptive spectrum awareness should be referred to as “Cognitive Radio” [4]. 1.1 Cognitive Radio Features Cognitive Radio networks has been seen as a promising solution to improve the current spectrum underutilization while accommodating the increasing amount of services and applications in wireless networks [5, 6]. Cognitive radio technology could potentially allow a complete SU system to simultaneously or opportunistically operate in the same frequency band as the PU. However, the development of cognitive radio is still at a conceptual stage due to a number of challenges it faces in how the it learns and adapts 1 Chapter 1. Introduction to the local spectral activity at each end of the link. The inherent feature of these CR networks would be their ability to recognize their communication environment and adapt the parameters of their communication scheme to maximize the quality of service (QoS) for the SUs while minimizing the interference to the PUs. Nevertheless, CR networks need to have a high degree of flexibility in order to overcome high variation in channel quality and interference. It will be build over software defined radio (SDR) due to implicit realization of these characteristics in SDR technology, which is already in production and is now available. The key features of CR transceivers are awareness of the radio environment (in terms of spectrum usage, power spectral density of transmitted/received signals), dynamic adaptability (adaptive tuning to system parameters such as transmit power, carrier frequency, modulation strategy etc.) and highly efficient cooperative or noncooperative behavior (when there is competition between multiple CR transceivers). For a CR network to be deployed for practical usage a number of new technologies have to be developed. Of particular interest are the challenges involved in the design of physical and link layers. A number of new mechanisms within these layers such as measurement of network parameters, reliable spectrum sensing (detecting unused spectrum), spectrum mobility (maintaining seamless transition to a new spectrum), coexistence (with PUs and other CR networks), spectrum management, reliability (in terms of QoS), resource allocation (such as transmit power allocation and dynamic spectrum sharing (DSS)) and so on, have to be designed for most efficient and practically harmless access and sharing of opportunistic radio spectrum. In addition, it is critical to best optimize these mechanisms for different situations in order to enhance network performance. Since PU channels have to utilized by secondary users in a CR network without causing any degradation in service to PUs, Orthogonal Frequency Division Multiplexing (OFDM) has been identified as an potential transmission technology for future CR systems [21]. This is mainly due to its great flexibility in dynamically changing spectral environments and allocating unused spectrum among SUs, which allows for simple adaptation of sub-carriers to fast changing conditions in radio spectrum. Besides, OFDM allows for multiuser diversity overcoming frequency selective fading which helps to enhance the spectrum utilization in general. A major challenge is to design efficient resource allocation algorithms (spectrum sharing and power alloca2 Chapter 1. Introduction tion) that works well in OFDM based CR networks. In this thesis, we specifically look at these two problems of dynamic spectrum sharing and power loading in CR networks and we then propose and design practical algorithms for them. 1.2 Thesis Outline Although, CR networks could be both cooperative or non-cooperative, cooperation amongst CR networks increases the overall efficiency of the network by maximizing use of resources with less contentions. However, with cooperation, fairness becomes a very important criterion to distribute resources among the participating users. Fair sharing will although reduce the overall usage of resources but will provide a better tradeoff and an incentive to make starved users to participate. The problem is hard because each user may have a different measure of value of the resource. Several resource division/allocation algorithms have been proposed in literature such as maximum throughput, round-robin, max-min fairness,proportional fair etc. Proportional fairness has been considered to be a best compromise amongst all these. In Chapter 2 of this thesis, we review the proportional fair algorithm for cooperative networks. We then tweak this algorithm to allow further controls possible on this algorithm with applications in dynamic spectrum sharing for multiuser CR networks. In particular, we introduce time and utility controls. Each of these controls gives us better flexibility depending on channel conditions. We extend this algorithm for variable discrete slotted times. We also discuss the extension of these controls for OFDM-CR systems. In Chapter 3, we deal with power allocation problem for single user OFDM-CR system. It has been observed in literature [17, 19] that classical power allocation algorithms for OFDM systems such as uniform power loading or water-filling are no longer optimal for CR networks. This is because of special properties of CR networks such as interference constraints etc. In this chapter we identify and formulate another criteria which is based on PU activity and as we will see, it plays an important role for power allocation in OFDM-CR networks. We observe that there are some subcarriers which are more often occupied by different PUs and there are some which are not accessed by PU oftentimes. We develop a risk return model based on a special rate loss function that we will define in this chapter and we incorporate this mathematically. We then form a convex optimization problem, solution to which no longer follows 3 Chapter 1. Introduction the general water-filling method. Instead we now have water-filling only on subcarriers belonging to similar PU activity bands. Since the computational complexity of this new solution is higher we propose two heuristic suboptimal algorithms with complexity identical to water-filling. We also do a comparative evaluation of all these algorithms based on simulation results. Finally, we discuss briefly the properties of loss function. We did not consider the affect on interference generated by both PUs and SU on each other in Chapter 3. There are two possible co-existence scenarios for PUs. The first one in when both PU and SU are co-located in the same area with side-by-side bands. The authors in [20] have shown that due to non-orthogonality of transmitted signals mutual interference may occur in this case. The second scenario is the one in which PU may exist in the same frequency band but geographically apart. Both these scenarios restrict the SU to keep its transmit power level low without causing any harmful interference to PUs. The authors in [17, 18] have modeled a CR network for the first co-existence scenario and hence proposed an optimal and sub-optimal power loading schemes for this model. Similarly, in [19], a power allocation algorithm has been proposed for the second scenario. In Chapter 4 of this thesis, we extend our risk-return model to include these two PU co-existence scenarios and we then propose a joint interference-limited model for OFDM-CR networks. We formulate a convex optimization problem for this model and we find the optimal solution for power allocation. As we will notice, the optimal solution is computationally complex to evaluate so we briefly discuss some possible sub-optimal schemes. Finally we propose and discuss some future work and draw conclusions in chapter 5. 4 Chapter 2 Dynamic Spectrum Sharing for Cognitive Radio 2.1 Introduction Dynamic spectrum access (DSA) is an important characteristic of a cognitive radio system to access the unused spectrum in a more efficient manner. In presence of more than one cognitive user, the problem of allocation of the unused spectrum amongst the users is better known as “dynamic spectrum allocation” problem or simply “spectrum sharing”. Spectrum sharing problem has been studied in a lot of interesting scenarios for both centralized and decentralized systems [10–14]. Typically for a decentralized system, game theoretic approaches have been proposed by modeling the problem as cooperative and non-cooperative games [10–12]. Several methods for a centralized system have been proposed for more specific cases. Device coordination for the cognitive radio networks [15] has been an suggested as an important feasible approach to make an efficient and fair division of the spectrum. It helps minimizing the wastage of the spectrum and maximizing the overall utility in a non-competitive manner. In this chapter, we will study the spectrum sharing problem in case of both centralized and decentralized systems when the cognitive users cooperate by sharing their information amongst each other. Selecting a cognitive user to use an available spectrum at any time should consider a balance between the current possible rates and fairness. Secondary users cooperate with each other with an interest in maximizing their own allocated resources and minimizing the wastage of available spectrum. If the user with highest rate is chosen at each slot, then other users with low SNRs will be starved and such an allocation scheme would be unfair and against their interest in cooperation. Fair sharing will although reduce the overall maximum possible throughput but will also provide better 5 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio opportunity to the users with lower SNRs. The balance between overall system throughput and fairness could be defined in various ways. Proportional fairness is such a fairness criterion which compares ratio of possible rates and past throughput for each user and selects the one which has maximum ratio. It is related to the fairness criterion given in [7]. In this chapter we will study proportional fair algorithm applied to dynamic spectrum sharing. We will assume perfect channel sensing by the secondary users and spectrum pooling of the opportunistically available spectrum. We will also assume that information is being shared perfectly amongst all the cognitive/secondary users and that there is no user hidden from any other user. In such a scenario, we will propose a modified proportional fair based algorithm for dynamic spectrum sharing in case of device coordinated cognitive radio systems. Instead of constant length time slots, we propose variable length time slots controlled by the utilization and time limits defined later in this chapter. We will first study this problem for centralized systems and then generalize it for decentralized systems. We will also define different controls possible based on the proposed modifications. Later in this chapter we will suggest another possible variation to this algorithm which although involves variable length time slots but are multiples of some minimum duration slot. Further we will also discuss the possible extension of our algorithm for multicarrier systems such as OFDMA. The chapter is organized as follows. In Section 2.2, we review the proportional fair allocation mechanism. We introduce our system model, proposed modifications and the formal algorithm in Section 2.3. Various comments about the possible versions of the algorithm and feasible extensions for multicarrier systems are given in Section 2.4. Simulation results are presented in Section 2.5. 2.2 Proportional Fair Allocation Proportional fairness criterion was introduced by Kelly et.al [8] in the context of game theory. It is a Pareto efficient allocation scheme which maximizes the sum of logarithmic average user rates. Hence, a proportional fair allocation could be defined 6 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio as the one that maximizes log λi (2.1) i where λi is the average rate or throughput for user i. One can easily prove that proportional fairness or maximization of logarithmic average rates is achieved by selecting the user i at certain time according to the following rule arg max i ri λi (2.2) where ri is the instantaneous transmittable data rate at the current time slot of user i. 2.3 System Model We consider a time-slotted system where at every time-slot some user is assigned an opportunistically available band of frequencies. This allocation changes at the end of the time slot and evolves as a fair distribution scheme based on proportional fairness. An important aspect of this proposed allocation mechanism is controlling overuse of the spectrum. We could model our system as described below. The cognitive radio network we consider, consists of a set of Nu transmittingreceiving pairs of secondary user nodes and a fixed licensed bandwidth W available for all the secondary users whenever the primary user is not using this band. We assume that no two users are allowed to use this bandwidth at the same time. Further, we assume perfect channel sensing by the secondary users and spectrum pooling of the opportunistically available spectrum. We consider a standard assumption that every secondary user has infinite backlog of data to transmitted. We denote secondary users by using the indices from i = 1 to Nu . We first a consider a central server controlling the allocation. We will later on discuss by reasoning that if users cooperate effectively then a central server could be avoided. We call the time instant when the server has to make decision for spectrum allocation as decision time instant. We denote the length of time slot just before the decision time instant k by tk and we assume t0 = 0. The estimated channel gain at the transmitter of the the secondary user i at decision time instant k is denoted by hi,k . We assume that this estimated channel 7 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio gain remains constant for any secondary user during the length of the time slot. We also assume that the background additive Gaussian noise is of power spectral density N0 . Therefore maximum achievable rate as per the Shannon capacity limit for any secondary user i at any given time instant k is given by ri,k = ηi W log2 1 + |hi,k |2 pi N0 W (2.3) where pi is the power with which the secondary user i transmits and ηi is the fraction of the Shannon capacity which can be reliably guaranteed by the transmitter-receiver pair for this user. ηi would generally depend on decoder pairs deployed by these users. Our algorithm limits the overuse of the allocated spectrum by using two quantities Tmax and θmax which we will define below. Tmax is the maximum time slot length or the maximum time any user could use the allocated bandwidth i.e 0 ≤ tk ≤ Tmax for k ≥ 0. We call the term θmax as the maximum channel utilization limit. θmax can be defined as follows: If for some time ∗ slot k the band is assigned to user i and this user transmits with some actual rate ri,k , ∗ then the amount of channel use should be limited by 0 ≤ ri,k tk ≤ θmax . Therefore, once a user has used the channel to the limit θmax , it has to leave the channel although its time limit may still be lesser than Tmax . Alternatively, once the user has occupied the band for maximum time limit Tmax , it has to leave the bandwidth even though its channel usage may still be lesser than θmax . We denote throughput of each user i at time instant k by λi,k and overall system throughput at time instant k by Λk . Initial throughput of each user λi,0 = 0 for i = 1 to Nu at time instant 0. Also, let bi,k be a binary index to represent that at time slot k whether the user i was assigned the band or not; bi,k = 0 means that the band was not given to the user i at time slot k and bi,k = 1 means that the band was assigned to the user i. Hence, net throughput for user i at decision time instant n is given by λi,n = n ∗ k=1 ri,k bi,k tk n k=1 tk (2.4) 8 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio and overall system throughput at time instant n is given by Nu ∗ i=1 ri,k bi,k tk n k=1 tk n k=1 Λn = (2.5) Throughput for each user can also be calculated iteratively as follows λi,n = λi,n−1 n−1 ∗ k=1 tk + ri,n bi,n tn n k=1 tk (2.6) ∗ ri,k here is the true rate at which user i transmitted in time slot k. The central server uses a more general modified form of proportional fair algorithm to calculate priorities. Denoting the priority for user i at time instant n + 1 by ρi,n+1 , it is given by the following expression (ri,n+1 )α ρi,n+1 = (2.7) (λi,n + κi )β Parameters α, β and κi tune the fairness of the system, such that either bandwidth distribution is fair for all users or throughput of the channel is maximized. If α = 0 and β = 1, then this system reduces to a round-robin system giving equal share to all users. If α = 1 and β = 0 then the system reduces to a maximum throughput system. κi , i ≤ N is a positive number to tune the system for each individual user depending upon the class of applications they are using. We could also assume κi to be same for all users, i.e, κi = κ for all i ≤ N. Once the server has calculated the priorities for each user, the user with the highest priority is assigned the band. Therefore a user is chosen according to the following rule arg max ρi,n+1 i≤Nu (2.8) The algorithm is formally written in the following subsection. 2.3.1 Algorithm Input: W, N0 , Nu , α, β, κ, Tmax , θmax and pi , ηi for i ≤ Nu 1. Set λi,0 = 0, t0 = 0, n = 1 2. for i → 1 to Nu 9 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio Set bi = 0 and Estimate hi,n Set ri,n = ηi W log2 1 + |hi,n |2 pi N0 W Set ρi,n = )α (ri,n (λi,n−1 +κ)β 3. j = arg maxi≤Nu ρi,n , Set bj = 1 ∗ ∗ 4. Choose true rate rj,n ≤ rj,n and set ri,n = 0 for i = j ∗ 5. if rj,n Tmax ≥ θmax ∗ tn = θmax /rj,n else tn = Tmax 6. for i → 1 to NuP Set λi,n = λi,n−1 n−1 ∗ b tk +ri,n i,n tn k=1 tk k=1 P n 7. Set n = n + 1, go to step 2. 2.4 2.4.1 Various Comments Time and Utility Controls Based on the values of Tmax and θmax , there are three kind of controls possible for our algorithm. Assuming an average user rate of ravg we could state these controls as follows Fixed Utility Control If ravg Tmax ≫ θmax , the time slot length is unlikely to go the maximum time limit Tmax . Such a system is mostly controlled by the utilization limit θmax . This control is useful when channel is quite often favorable to most of the users and is changing very fast over the duration of Tmax . Therefore after varying but small time slot duration, new values of channel gains are estimated again. Fixed Time Control When ravg Tmax ≪ θmax , the system is unlikely to reach the utilization limit θmax and so the time slot duration is generally always Tmax . Hence, the algorithm behaves as 10 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio fixed time controlled or like a normal proportional fair algorithm. This control is more apt when channel stays constant or is often unfavorable to a majority of the users at least over the duration of Tmax . Both Time and Utility Control When ravg Tmax ≈ θmax , algorithm is controlled by both time and utilization limits. Time and Utility control could be applicable for the case when channel behaves fast but stays more or less the same over Tmax and is often both good or bad for a big subset of users. 2.4.2 Decentralized Cooperative Networks Although, we assumed a central server in our system model of our algorithm but this scheme could also be implemented for decentralized systems. In order to achieve this, every user just has to share its priority values ρ to all the other possible users in the system. Once all the users have received a set of all priority values, whoever has the highest priority value would access the band. This happens without any possibility of collision because due to the random nature of the system there will be only one such user. The user which has been assigned the band must follow the protocol by notifying other users and leaving the available band once either its utility or time has reached the upper limit. 2.4.3 Utility Measure For the utilization limit θmax , we took a simple utilization criterion of amount of data transferred. But in general, this could be a complex concave function of several parameters. 2.4.4 Variable Discrete Slotted Time In the above proposed algorithm we considered a variable time slot duration with some upper time limit Tmax . It is also possible to allocate bands to the users in multiples of some fixed slot size. Such a system would have a minimum time slot size Tmin and maximum time slot factor M such that tk = mTmin , where m is a positive 11 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio integer and m ≤ M. The algorithm still works in a similar manner except that now tk would be chosen as follows tk = ⌊ θmax ∗ ⌋Tmin Tmin rj,k MT min ∗ if rj,n MTmin ≥ θmax (2.9) otherwise where ⌊x⌋ is the function that returns the highest integer less than or equal to x. This modified version of algorithm is very useful for multicarrier systems which we will discuss in the next subsection. In case of multicarrier systems, it is important to have decision times synchronized for subcarrier allocation. This is possible if we use our variable discrete slotted time proportional fair algorithm. 2.4.5 Multicarrier Systems Orthogonal frequency division multiplexing (OFDM) has been recognized as a potential transmission technology for cognitive radio systems due to its flexibility in allocating resources among the cognitive users [6]. Therefore cognitive radio networks require efficient and fair spectrum allocation schemes for multiuser OFDM systems. Proportional fair algorithm for multicarrier systems was proposed in [9]. If Nc is the number of subcarriers and Nu is the number of users, then this algorithm requires NuNc number of comparisons. A simplified scheme which uses proportional fairness in each subcarrier was also proposed in [9]. Using this simplified scheme for variable discrete slotted time algorithm it is possible to design a simple fair spectrum allocation scheme for multicarrier systems. The central server calculates a priority matrix Φn+1 of dimensions Nu × Nc where ij’th element of this matrix is the priority for user i over subcarrier j at time instant n + 1 given by ρi,j,n+1 as follows ρi,j,n+1 = (ri,j,n+1)α (λi,n + κi )β (2.10) where ri,j,n+1 is the maximum achievable rate as per shannon capacity limit for any secondary user i in subcarrier j at time instant n + 1. The server takes the decision after every smallest possible time slot length which in this case would be Tmin as defined above. If some user is still using a subcarrier, then it is given an infinite priority for that subcarrier. The problem is slightly more complex in this case because 12 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio of the online throughput calculation at each step as some users might still be using the some of the subcarriers. Once the server has the priorities of every user in each subcarrier, the user with the highest priority is assigned the subcarrier. We define this mathematically in form of an allocation vector v of length Nc . Each element of vector v is calculated by finding out the row index of the element which is maximum in the corresponding column of the priority matrix Φn+1 . 2.5 Simulation Results For simulations, we take a Rayleigh fading channel with average channel power gain i.e. E{|h|2 } equal to 1. We consider a balanced throughput-fairness ratio system with tuning parameters α = 1, β = 1 and κ = 1. We assume perfect encoder and decoder pairs for every cognitive user with efficiency ηi = 1 for all i ≤ Nu . We simulated the proposed algorithm for a system with an average SNR of 10dB. We assume that the transmit powers are identical and time-invariant, i.e the wireless network is fully loaded. We take the transmit power for user i as pi = 10mW for all i ≤ Nu , noise power N0 = 10−6 W/Hz and available bandwidth W = 100kHz. We consider a cognitive network consisting of three users i.e. Nu = 3. We simulated our algorithm for such a system to compare overall system throughput, individual average rate and time slot lengths for three different controls as discussed in Section IV. We simulated the three controls for a maximum time slot length of Tmax = 10−2 . For fixed time control, we set Tmax = 10−2 and θmax = 15000. Fig. 2.1 shows the individual throughputs of each user with respect to time. It is clear from the graph that individual throughputs converge with time. In the case of fixed utility control, we take the same time limit Tmax = 10−2 and θmax = 2000. Individual throughputs of each user with respect to time are plotted in Fig. 2.2. Convergence rate is much faster compared to time controlled case. This should be true in theory as in this case more decisions are taken in the same time window compared to the fixed time control case. For the case of both time and utility controlled mechanism, we again take the same time limit i.e. Tmax = 10−2 and utilization limit θmax = 7500. Plots of individual throughputs in this case are presented in Fig. 2.3. Comparing Fig. 2.3 with figures 2.1 and 2.2, we observe that convergence rate in this case lies between fixed time and 13 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio fixed utility. Using the same previous analogy as in the fixed utility case, we could say that this is so because number of decisions in this case lies between fixed time and fixed utility control algorithms. Two more comparative plots for the three controls are given in figures 2.4 and 2.5. In Fig. 2.4, we plotted the overall system throughputs vs. time for all the three controls on the same axes. It can be observed from the plots that the fixed utility case converges faster than both time and utility controlled mechanism which converges faster than the fixed time control algorithm. Fig. 2.5 shows a comparative plot of the time slot lengths for the three controls. As expected, in the case of time control, slot lengths are always equal to the upper limit Tmax . For utility control, slot lengths never reach this limit and for the time and utility control case, slot lengths often jump to this limit but not always. 14 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio 5 6 x 10 User 1 User 2 User 3 Individual Throughput in bits/sec 5 4 3 2 1 0 0 0.2 0.4 0.6 0.8 1 1.2 Time (in seconds) 1.4 1.6 1.8 2 Figure 2.1: Time Controlled: Throughputs of users 15 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio 5 6 x 10 User 1 User 2 User 3 Individual Throughput in bits/sec 5 4 3 2 1 0 0 0.2 0.4 0.6 0.8 1 1.2 Time (in seconds) 1.4 1.6 1.8 2 Figure 2.2: Utility Controlled: Throughputs of users 16 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio 5 6 x 10 User 1 User 2 User 3 Individual Throughput in bits/sec 5 4 3 2 1 0 0 0.2 0.4 0.6 0.8 1 1.2 Time (in seconds) 1.4 1.6 1.8 2 Figure 2.3: Time & Utility Controlled: Throughputs of users 17 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio 5 10 x 10 Time Control Utility Control Time & Utility Control Overall System Throughput in bits/sec 9.5 9 8.5 8 7.5 7 6.5 6 5.5 0 0.2 0.4 0.6 0.8 1 1.2 Time (in seconds) 1.4 1.6 1.8 2 Figure 2.4: System Throughputs 18 Chapter 2. Dynamic Spectrum Sharing for Cognitive Radio Tmax Time Control Utility Control Time & Utility Control 0.01 Time Slot length in seconds 0.008 0.006 0.004 0.002 0 0 0.2 0.4 0.6 0.8 1 1.2 Time (in seconds) 1.4 1.6 1.8 2 Figure 2.5: Slot lengths 19 Chapter 3 Power Allocation for OFDM-CR System Based on PU Activity 3.1 Introduction Recent studies have shown that power allocation problem under a fixed budget is non trivial for cognitive radio systems. Traditional water-filling power allocation [16] approaches for OFDM-based cognitive radio (CR) systems have been found to be inefficient due to interaction with licensed or primary users [17, 19]. A step based power allocation approach was proposed in [17] when primary user (PU) band is present in the vicinity of OFDM subcarriers. This power allocation technique is designed considering the limit on the interference (interference temperature limit) caused by the unlicensed or secondary user (SU) subcarriers to the nearby primary user band. Another power allocation approach for cognitive radio which deviates from water filling allocation scheme was proposed in [19]. This allocation algorithm considers the limit on the interference caused to the primary user present in the same subcarrier band but physically apart from the secondary user. In this chapter, we consider another aspect of CR networks for power allocation in the secondary user subcarriers which we define as “reliability” of the channel. We model our system in a way to allocate more power to more reliable subcarriers. By reliable here we mean, the subcarriers that are available fairly more often than the one which gets busy very quickly. Such a behavior is observable when there are more than one sub-channels that belong to different primary users. These primary users differ on their activity or usage of their licensed band. In the next section, we discuss how we model our system mathematically to incorporate reliability of the primary user band to allocate power to subcarriers belonging to different primary users. We assume a cost function which gives the rate loss whenever primary user reoccupies 20 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity PUj-Primary User j PU1 PU2 PUj PUM ............................. 1 2 i N Figure 3.1: Opportunistic spectrum in an OFDM-based CR system the sub-channel. As we will see, optimal allocation solution for such a model is no longer the general water-filling solution. For a special case of linear loss function, the optimal power allocation approach turns out to be water filling with different water levels for subcarriers belonging to the different primary users. These water levels are higher for the subcarriers which have lesser primary user activity. We also propose two heuristic suboptimal algorithms which are also water-filling with different waterlevels for sub-channels belonging to different primary users. We will then discuss the simulation results and compare the performance for these algorithms with respect to water-filling algorithm. We will also comment on the linearity of loss function and some suggestions for intuitively choosing its coefficients by obtaining upper bounds. 3.2 System Model We consider a wireless system consisting of M sub-channels licensed to different primary users. Each of these primary users behaves differently or has uncorrelated activity in their band. All the sub-channels are divided into multiple subcarriers and they are opportunistically available to some secondary or cognitive user which uses the band in OFDM fashion [6, 20, 21]. We assume that total number of subcarriers are N. Fig. 3.1 shows such a system with M sub-channels licensed to different primary users and are divided into multiple subcarriers. We assume a centralized system where the CR controller gathers all the information (channel gains, etc.). 21 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity We model primary user activity or the channel availability of the licensed band for the secondary user by a Markovian process. Assuming each primary user has a different transition matrix depending upon its activity, let αj be the probability that the channel gets reoccupied by the j’th primary user sometime uniformly during the current time frame given that the channel was available for secondary user in the previous time frame. Also let us define a mapping ϕ : Z+ → Z+ , where ϕ maps subcarrier index to the primary user index as follows: ϕ(i) = j if ith subcarrier is licensed to primary user j. (3.1) Z+ being the set of positive integers. We assume that the background additive Gaussian noise is of power spectral density N0 and each subcarrier has a bandwidth of B Hz. The estimated channel gain at the transmitter of the the secondary user for subcarrier i is denoted by hi . We consider a slow channel fading such that channel gain remains constant for several time frames. If the power allocated to the subcarrier i is denoted by Pi then, the achievable rate ri as per the Shannon capacity limit is given by |hi |2 Pi ri = η ln 1 + N0 B (3.2) where η is the fraction of the Shannon capacity which can be reliably guaranteed by the transmitter-receiver pair of the secondary user. η would generally depend on decoder pairs deployed by these users but for simplicity we normalize it to unity. 3.3 Optimal Power Allocation for Cognitive Radios Based on Sub-channel Availability 3.3.1 A Risk-Return Model for Power Allocation In order to incorporate the availability (or reliability) of sub-channels in our power allocation model, we refer to a general risk-return scenario. We would treat the power allocated to a subcarrier as an investment in the band. Cognitive Radio environment could be thought as a risky environment compared to non-cognitive atmosphere which 22 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity could be treated like a free market or risk-free atmosphere. There are few fundamental differences compared to general risk-return scenario. In the cognitive environment, there is always a rate loss whenever a primary user comes back to reuse the channel. As an example, suppose the secondary user was able to use the channel for time Ti in a time frame T , rate loss would be given by ∆ri = ri − ri Ti T (3.3) True rate Ri achieved is therefore ri − ∆ri . This rate loss that we discussed above is a simple representation of loss due to time factor but in general there are other costs involved while allocating power and we model those costs also as rate loss dependent on power invested in the band. For example, loss in the rate which was possible with a different power allocation scheme, interference caused to primary users. We model this rate loss as the risk involved in the cognitive environment. We define a real-valued increasing, concave and normalized average rate loss function L(p) for a power p invested in a subcarrier whenever a primary user reoccupies a sub-channel during the current time frame. This function L may also involve cost of allocating resources. Therefore, given the probability αϕ(i) that the primary user will be active at sometime during the current time frame and the power invested Pi in the i’th subcarrier, the expected rate loss or risk involved for that subcarrier in the cognitive environment is given by E{∆ri } = αϕ(i) L(Pi ). (3.4) Hence, the expected capacity of the i’th subcarrier in the cognitive environment is as follows: E{Ri } = ri − E{∆ri } = ri − αϕ(i) L(Pi ) (3.5) If E{Ri } is a concave increasing function of power Pi , we could find an optimum power allocation using standard convex optimization techniques. This optimization 23 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity problem could be stated as follows: N max P1 ,P2 ...PN E{Ri } (3.6) i=1 2 E{Ri } with a constraint on total power budget. For E{Ri } to be concave ∂ ∂P < 0 for all 2 i subcarriers. This relation gives the following condition on L for the problem to be easily tractable using convex optimization approach: ∂2L >− ∂Pi2 1 αϕ(i) N0 B |hi |2 + Pi ∀i ∈ {1, 2, ..., N} 2 (3.7) Also, assuming E{Ri } is positive, increasing function of power within total power i} budget Ptotal i.e. ∂E{R ≥ 0 for Pi ≤ Ptotal , it gives ∂Pi ∂L ≤ ∂Pi αϕ(i) 1 N0 B |hi |2 ∀i ∈ {1, 2, ..., N} (3.8) + Pi This condition is important so the secondary user would not hold any power and invest all power within total budget to get maximum profit. We also assume, that zero power invested gives no loss, i.e L(0) = 0. Choosing a common loss function for all subcarriers which satisfies all desired properties is not easy. We will now consider a special case when this rate loss function L is approximated with a linear expression. Clearly, this would satisfy (3.7) as in this case 3.3.2 ∂2L ∂Pi2 = 0 for all subcarriers. Optimal Power Allocation for Linear Rate Loss A linear rate loss function could be represented as follows: L(p) = Cp (3.9) The quantity C is normalized average cost per unit power for the secondary user to allocate resources. C could be visualized as average rate loss per unit power (units bits/s/W) and would depend on a number of factors such as interference caused to primary users, time-delays and numerical complexities involved while allocating 24 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity resources. Also C is chosen such that it satisfies (3.8) for all subcarriers. The expected rate/capacity in the i’th subcarrier for the secondary user is therefore given by E{Ri } = ri − αϕ(i) CPi . (3.10) A power allocation vector P = [P1 P2 ..PN ] gives the amount of power allocated to each subcarrier. With these definitions in consideration, our goal is therefore to find the power allocation vector that maximizes the expected rate. The optimization problem can therefore be written as follows: N ∗ P = arg max P E{Ri } (3.11) i=1 or more simply N P∗ = arg max P ln 1 + i=1 |hi |2 Pi N0 B − αϕ(i) CPi (3.12) subject to Pi ≥ 0 ∀i ∈ {1, 2, ..., N} and (3.13) N Pi = Ptotal (3.14) i=1 Proposition 1. Solution to the optimization problem defined by (3.12), (3.13) and (3.14) is given by Pi∗ = 1 N0 B − λ + αϕ(i) C |hi |2 + ∀i ∈ {1, 2, ..., N} (3.15) where [x]+ ≡ max{0, x} and λ is threshold constant to be determined by the total transmit power constraint as follows N i=1 N0 B 1 − λ + αϕ(i) C |hi |2 + = Ptotal (3.16) Proof. See Appendix A. 25 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity As it could be seen from the solution of the optimization problem defined in previous section, we allocate more power to the bands which are more likely to be available. The optimal power allocation approach for this model is still a water filling but with different water levels for each sub-channel. The water level of a subcarrier 1 licensed to primary user j is now λ+α . Determining the threshold constant in this jC case is more difficult than normal water filling. In case of normal water-filling (when αj = 0) the equation reduces to a piecewise linear equation with breakpoints which gives a unique solution with several iterations. The threshold constant λ in (3.16) is part of a non-linear equation and we must rely on numerical methods to quickly determine the threshold constant. In the next section, we discuss several suboptimal schemes by relaxing (3.16) to take form of a piecewise linear equations, which are easily solvable using iterative algorithms. 3.4 Suboptimal Schemes for Power Allocation Based on Sub-channel Availability It is both intuitively and mathematically clear that we would achieve better expected capacity by allocating more power to the bands with higher probability of their availability. We will now propose two heuristic suboptimal schemes, each proposing higher water level to the bands with higher availability or lesser primary user activity. 3.4.1 Scheme 1: Relative Water Levels 1 to In this scheme we modify the water level for j’th primary user’s band from λ+α jC 1 − τ αj C. Here τ is a predetermined design parameter for this scheme so that we λ observe an increase in expected capacity. This is a relative adjustment of water level and it reduces the constraint equation to the following piecewise linear equation in λ, solvable by iterative algorithms N i=1 N0 B 1 − τ αϕ(i) C − λ |hi |2 + = Ptotal (3.17) 26 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity Power allocated for subcarrier i is hence given by 1 N0 B Pi = − τ αϕ(i) C − λ |hi |2 3.4.2 + ∀i ∈ {1, 2, ..., N} (3.18) Scheme 2: Proportional Water Levels Here we adjust the the water level proportional to probabilities αj for j’th primary 1 user’s band. The water level is given by (αj +νC −1 )λ with ν being a design parameter similar to previous scheme. The quantity C carries a negative power in denominator to ensure that higher the value of C, more is the difference in water levels. Again, this proportional adjustment of water level makes constraint equation piecewise linear and iterative algorithms could easily be used to determine threshold λ. Constraint equation is given as follows: N i=1 N0 B 1 − −1 (αϕ(i) + νC )λ |hi |2 + = Ptotal (3.19) ∀i ∈ {1, 2, ..., N} (3.20) Allocated power to subcarrier i is therefore given by 1 N0 B Pi = − −1 (αϕ(i) + νC )λ |hi |2 + Owing to the similarity in the structure, these suboptimal schemes can be implemented with same complexity as practical water-filling solutions [22]. 3.5 3.5.1 Performance Evaluation Simulation Parameters and Assumptions For simulations, we take a rayleigh fading channel with average channel power gain i.e. E{|h|2 } equal to 1. We consider a system consisting of three different primary users namely P U1 , P U2 and P U3 and a total opportunistic bandwidth of 1 MHz available to a secondary user. This bandwidth is divided into N = 16 subcarriers of equal subcarrier width. Subcarriers 1 to 8 belong to P U1 with an activity pattern or probability of reoccupying the band sometime during the current time frame as 27 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity −6 −6 Water filling algorithm x 10 5 5 amount of power allocated to each subchannel Noise to Carrier Ratio 4.5 4 4 3.5 3 3 2.5 2.5 2 2 1.5 1.5 1 1 0.5 0.5 0 2 4 6 8 10 subchannel indices 12 14 16 −6 0 18 (a) Water-filling Algorithm 5 4 4 3.5 3 3 2.5 2.5 2 2 1.5 1.5 1 1 0.5 0.5 0 2 4 6 8 10 subchannel indices 12 14 4 6 16 8 10 subchannel indices 12 14 16 18 Optimal filling algorithm x 10 amount of power allocated to each subchannel Noise to Carrier Ratio 4.5 3.5 0 2 −6 5 amount of power allocated to each subchannel Noise to Carrier Ratio 4.5 0 (b) Scheme 1: Relative water levels Suboptimal Scheme 2: Proportional Water Levels x 10 amount of power allocated to each subchannel Noise to Carrier Ratio 4.5 3.5 0 Suboptimal Scheme 1: Relative Water Levels x 10 18 (c) Scheme 2: Proportional water levels 0 0 2 4 6 8 10 subchannel indices 12 14 16 18 (d) Optimal allocation scheme Figure 3.2: A snapshot of simulation results for different power allocation schemes. 28 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity α1 = 0.10. Furthermore, subcarriers 9 to 12 are licensed to P U2 with α2 = 0.89 and subcarriers 13 to 16 belongs to P U3 with α2 = 0.50. We consider a total power budget Ptotal = 10−5 W and noise power N0 = 10−11 W/Hz. Assuming a linear rate loss function with normalized cost per unit power C = 3 × 103 bits/s/mW, we simulate the power allocation for this system based on optimal scheme discussed in Section III and two suboptimal schemes discussed in Section IV. For suboptimal scheme 1, we use the value of constant τ = 4 × 10−12 and for scheme 2 we use ν = 1.05 × 106 . We use an iterative algorithm for the water-filling and suboptimal schemes which iteratively sets zero power to the subcarriers with negative power. To simulate the optimal scheme, we used sequential quadratic programming [24] for the original optimization problem. 3.5.2 Simulation Results Fig. 3.2 shows different power allocations obtained using the traditional water-filling algorithm and the optimal and suboptimal schemes discussed in this chapter. It could be easily observed from Figs. 3.2(b), 3.2(c) and 3.2(d) that more power is allocated to the subcarriers which have lesser primary user activity. Also, each sub-channel follows a water-filling allocation with different water levels. This sub-channel waterfilling as we proved is a special case, when rate loss function is linear. Simulations show that average expected normalized capacities with 100 iterations for water-filling, scheme 1, scheme 2 and optimal schemes are 4.6216, 7.2216, 8.8776, 9.5848 bits/s respectively, giving a maximum gain of 3.17 dB by the optimal scheme compared to water-filling. Fig. 3.3 compares the expected capacities obtained by different algorithms as the cost per unit power C varies, keeping the other parameters unchanged. It is clear from this graph that as C increases, the expected capacity drops linearly for water-filling algorithm and this drop is lowest for the optimal scheme. We now compare the performance of different schemes with variations in primary user activity. Without changing other variables that generate Fig. 3.2, we plot the power allocated to sub-channel licensed to P U1 and overall expected capacity achieved by the secondary user for different α1 in figures 3.4 and 3.5 respectively. As expected, Fig. 3.4 shows that power allocated in P U1 ’s band by the water-filling algorithm is independent of primary user activity. The allocated power by suboptimal schemes 29 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity 1 and 2 drops almost linearly with primary user activity, whereas this drop is faster and more significant with the optimal scheme. On the other hand, expected capacity drops linearly for water-filling scheme and almost linearly (but is always more) for schemes 1 and 2 as shown in Fig. 3.5. For the optimal scheme, the expected capacity is always larger than other schemes but drops quickly initially but this drop stabilizes as α1 increases. Notice that, capacities become negative in Fig. 3.5. This is because we used a constant value of C to simulate this graph and we were more interested in the general trend rather than actual values. In the next section we discuss the linearity of loss function to address these issues. 3.6 Discussions on the Loss Function As we have mentioned before, linear loss function is an approximation for a general loss function though there are several advantages choosing a linear loss function. First of all, it reduces the computational burden and simplifies the allocation problem. Secondly, it also preserves the linearity to the overall expected loss/risk as weighted additive sum of powers as follows: E{L(P)} = C(αϕ(1) P1 + αϕ(2) P2 + .... + αϕ(N ) PN ) (3.21) But the effectiveness of the algorithm depends on the optimum choice of C which we defined as average cost for unit power. C could be chosen by various learning algorithms or trial-error methods observing the achieved and targeted rates. Averaging out the rate loss with respect to total power invested would give us a rough estimate of C. We will provide here some general guidelines to intuitively choose its value. According to equation (3.8), optimal solution is valid when C satisfies 1 C≤ αϕ(i) N0 B |hi |2 ∀i ∈ {1, 2, ..., N} (3.22) + Pi Taking the minimum over the left hand side of equation (3.22), we obtain the following upper bound for C: 1 C≤ maxi αϕ(i) N0 B |hi |2 (3.23) + Ptotal 30 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity If (3.23) is satisfied, overall expected capacity will always be increasing with increasing power budget and the optimal and suboptimal algorithms will still be valid. However we can also choose C so as to satisfy a weaker relaxed condition with positive expected rates i.e. E{Ri } ≥ 0 for Pi ≤ Ptotal . Expected rate E{Ri }, is maximum for the following power: Pimax = If i 1 αϕ(i) C − N0 B |hi |2 (3.24) Pimax ≥ Ptotal , we could distribute the power by investing all the power within budget in the band. This would give us a following upper bound on the value of C C≤ N 1 i αϕ(i) Ptotal + N N0 B i |hi |2 (3.25) For this case we add an additional constraint on original optimization problem, i.e, Pi ≤ Pimax since E{Ri } is decreasing for Pi > Pimax . In order to tackle this additional constraint, we could just modify the original water-filling, optimal and suboptimal algorithms by introducing an iterative technique for power allocation. If allocated power by the previous algorithms exceeds Pimax for any subcarrier i, we set the power Pimax for that subcarrier and re-run these algorithms for remaining subcarriers with ′ a new power constraint Ptotal = Ptotal − Pimax . As we could see from expressions (3.23), (3.25) bounds on C depend inversely on power budget. 3.6.1 Other Forms of Loss function In general, loss function could be approximated to a piecewise linear expression of the form Cp + b with different values of C and b in different ranges of invested power. As we have already seen from expressions (3.23), (3.25), in the linear case, bounds on C depends inversely on power budget. Therefore, for higher power range, C should be lower. Another class of more practical loss functions could be logarithmic loss functions. Loss function could also depend on subcarrier channel gain. 31 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity 16 Waterfilling Algorithm Scheme 1 Scheme 2 Optimal Scheme 14 Expected Normalized Capacity 12 10 8 6 4 2 0 0 0.5 1 1.5 2 2.5 Cost/Rate Loss per unit power 3 3.5 6 x 10 Figure 3.3: Expected capacity vs. rate loss/unit power (C). 32 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity −6 9 x 10 Waterfilling Algorithm Scheme 1 Scheme 2 Optimal Scheme 8 7 Power Allocated 6 5 4 3 2 1 0 0.1 0.2 0.3 0.4 0.5 0.6 Probability (α1) 0.7 0.8 0.9 1 Figure 3.4: Allocated power vs. primary user activity (α1 ). 33 Chapter 3. Power Allocation for OFDM-CR System Based on PU Activity 8 Waterfilling Algorithm Scheme 1 Scheme 2 Optimal Scheme 6 Expected Normalized Capacity 4 2 0 −2 −4 −6 −8 −10 −12 0.1 0.2 0.3 0.4 0.5 0.6 Probability (α1) 0.7 0.8 0.9 1 Figure 3.5: Expected capacity vs. primary user activity (α1 ). 34 Chapter 4 Power allocation for Interference Constrained OFDM-CR system 4.1 Introduction In the previous chapter, we considered a power allocation problem for OFDM based cognitive radio systems considering the reliability of the opportunistic bands licensed to different PUs. As we discussed, we quantified this reliability based on the primary user activity. We approached this problem by defining an average rate loss function L(p) and then introduced a risk-return model to incorporate the sub-channel availability. So far, what we did not considered is the fact that a SU is not allowed to create interference to the primary users beyond a certain limit which is known as Interference temperature [6]. We also did not take into account the interference created by the primary users to the secondary user. To generalize our model for a more practical system we must add these additional constraints and factors and generalize our system model. In this chapter, we will extend our risk-return based model to a more general case by limiting the interference created to the primary users. We will consider two different interference limited models for OFDM based CR systems to further extend our system model. The first model as proposed in [17] is for a OFDM-CR system in which a PU band is present in the close vicinity or adjacent to opportunistic SU subcarriers. Since there is mutual interference between CR and primary users when both type of users coexist in side by side band, use of classical power loading schemes such uniform loading and water filling may result in higher mutual interference in the primary users’ band. The authors in [17] have considered a downlink SU system with no constraint on total power. Power is allocated in this CR system in order to maximize the total transmission capacity of the SU keeping the amount interference generated to the PU 35 Chapter 4. Power allocation for Interference Constrained OFDM-CR system bands within tolerable range. This idea is further extended to multiple PU bands in [18]. The second model proposed in [19] considers the limit on the amount of interference created to the PU or licensed user using the same subchannel as the SU but is geographically located at a certain distance from SU. This allows the SU to transmit within the same sub-channel but keeping the transmit power level low enough to avoid unacceptable interference to the PUs that cannot be detected due to the large distance from SU. This requirement puts additional power constraint on every primary user sub-channel for OFDM-based CR systems. Both these models and the one that we proposed in last chapter results in a power allocation solution which is no longer water-filling in a general sense. In the next subsection we define a joint system model combining all three models we discussed so far; one proposed in previous chapter and others proposed in [18, 19]. Considering all the constraints, we then find an optimal solution to this power allocation problem based on convex optimization theory. As we will see, this power allocation solution remains no longer water-filling in any form. 4.2 System Model for Interference Limited Secondary User System We consider a very typical cognitive radio wireless system as shown in Figure. 4.1. This model is very similar and inspired from the one presented in [19]. As shown in this figure, there is a secondary user SU who wants trying to transmit data in an opportunistically available or underutilized sub-channel. A sub-channel is said to be available if the interference to the PU receivers is within the acceptable range. This underutilized opportunistically available sub-channel is licensed to primary user PU1 which is located at a certain distance geographically apart from SU, thus allowing the SU to transmit while keeping the interference level low. PU1 shields itself from SU interference by defining a protection area of radius R and adding a requirement on SU to keep its interference power level at the margin of this area within a certain level P T [19]. Therefore SU’s total transmission power S for this channel has a power 36 Chapter 4. Power allocation for Interference Constrained OFDM-CR system Figure 4.1: A Typical Cognitive Radio System Model constraint given by S ≤ P T (d − R)n (4.1) where d is the distance between SU transmitter and PU1 transmitter and n is the path attenuation factor. This is simple example of power constraint and in practice there could be much more complex relation based on fading and path loss together. However, later on in this chapter, we consider only the value of this constraint rather than the actual relation. As shown in Figure. 4.1, there could be another primary user PU2 which is co-located or closely located in the same area as SU but is using a band which is adjacent or in between the available sub-channel. We consider a typical arrangement in spectrum domain of the available subcarriers and PU bands as proposed in [17] is shown in Figure. 4.2. As shown in this figure, it is assumed that there are L frequency bands numbered from 1 to L with bandwidths W1 , W2 , ...WL which have been occupied by the PU(s). We assume that SU has the knowledge of position and relative distance of these PU bands to assess the interference created to these PU bands. In between these bands there are M sub-channels licensed to different PUs which are divided into N subcarriers. We again assume that each of these PUs behaves differently or has uncorrelated activity in their sub-channel. These sub-channels are 37 Chapter 4. Power allocation for Interference Constrained OFDM-CR system opportunistically available to some SU which uses these sub-channels in an OFDM fashion. If we take off these PU bands from the Figure. 4.2 and view this spectrum as one contiguous frequency band, our model will look very similar to the one shown in Figure. 3.1. We will hence keep all the terms and definitions we introduced in section 3.2. Therefore, αj is the probability that the sub-channel j gets reoccupied by the j’th PU during the current time frame, mapping function ϕ : Z+ → Z+ , maps subcarrier index to the primary user index, background additive Gaussian noise is of power spectral density N0 and each subcarrier has a bandwidth of B Hz. The estimated channel gain at the transmitter of the the secondary user for subcarrier i is denoted by hi . We consider a slow channel fading such that channel gain remains constant for several time frames. We introduce a new term, Ji which is the sum of all the interference created by geographically apart primary users of the same sub-channels and the interference created by L side by side co-located PU bands. This interference will be different for different subcarriers as it is the sum of two different types of primary user interference. Those subcarriers which are right adjacent to the PU bands will incur higher amount of interference. The authors in [18, 20] discuss how to estimate the interference created by these L PU bands by integrating the power density spectrum of the PU signal across the ith subcarrier. If the power allocated to the subcarrier i is denoted by Pi then, the achievable rate ri as per the Shannon capacity limit is now given by |hi |2 Pi ri = η ln 1 + N0 B + Ji (4.2) where η is the fraction of the Shannon capacity which can be reliably guaranteed by the transmitter-receiver pair of the secondary user. As we discussed before, η would generally depend on decoder pairs deployed by these users but for simplicity we normalize it to unity. Next we discuss and define two different interference constraints on the SU based on two possible co-existence scenarios of different PUs and a SU we discussed so far: one in which a geographically apart primary user is using the sub-channel and the second scenario is the case when a PU(s) is using an adjacent or side by side bands. 38 Chapter 4. Power allocation for Interference Constrained OFDM-CR system SC J: Sub Channel J B W1 1 2 3 4 SC 1 PU Band 1 W2 . . . WL PU Band 2 PU Band L SC 1 . . . N SC M Figure 4.2: Opportunistic spectrum in an OFDM-based CR system with side by side PU bands 4.2.1 Sub-channel Power Constraint As discussed in [19], if a PU signal is detected in a sub-channel, then all the subcarriers belonging to that sub-channel are allocated zero power. On the other hand if the PU is not located close to the SU, SU can possibly transmit keeping the sum total of power allocated to all subcarriers for that sub-channel within a constraint limit as described in the previous section. Assuming Tj as the power constraint on jth sub-channel, we can define Tj as follows Tj PjT (dj 0 if PUj is detected nj − Rj ) if PUj is not detected (4.3) where PjT is the interference power constraint set by PUj at the margin of the area whose radius is Rj , dj is the distance between SU’s and PUj ’s transmitter and nj is the corresponding path attenuation factor. So given that total power allocated to subcarriers belonging to sub-channel j is Sj , we can say that Sj ≤ Tj (4.4) Sj could be therefore be given by the following expression Sj Pi (4.5) i s.t φ(i)=j 39 Chapter 4. Power allocation for Interference Constrained OFDM-CR system 4.2.2 Interference Constraint due to Co-located Primary User Bands The interference Iil introduced by the ith subcarrier on lth PU band can be expressed as follows [17, 20] Iil dil +Wl /2 = Pi ψ(f )df (4.6) dil −Wl /2 where ψ(f ) is a function in frequency f which depends on symbol duration and fading gain between CR transmitter and PU receiver, dil represents the distance in frequency between ith subcarrier and lth PU band. Therefore interference Iil can we represented as Iil = kil Pi , where kil is factor which depends on interrelated parameters between ith subcarrier and lth PU band. If Ith is the total interference threshold prescribed by the L PU bands, then we can rewrite a constraint equation as follows, N L N Iil L kil Pi ≤ Ith = i=1 l=1 (4.7) i=1 l=1 which can be further simplified to, N Ki Pi ≤ Ith (4.8) i=1 where, Ki = 4.3 L l=1 kil . Optimal Power allocation for Interference-limited OFDM-CR system 4.3.1 Risk-return model for Power Allocation We will refer to the risk-return model proposed in 3.3.1 and continue to use the definition of loss function L(p) as introduced in this section. Hence the expected 40 Chapter 4. Power allocation for Interference Constrained OFDM-CR system capacity of the ith subcarrier is given by E{Ri } = ri − E{∆ri } = ln 1 + |hi |2 Pi N0 B + Ji − αϕ(i) L(Pi ) (4.9) Our goal is to find a power allocation scheme which maximizes total expected capacity. Therefore, we can write the optimization problem as follows: N E{Ri } max P1 ,P2 ...PN (4.10) i=1 with a constraint on power budget and interference generated to primary users. For E{Ri } to be concave function of power Pi , so that we could use standard convex 2 i} optimization techniques, ∂ E{R < 0 for all subcarriers. This relation gives the fol∂P 2 i lowing condition on L for the problem to be easily tractable using convex optimization approach: ∂2L 1 >− ∀i ∈ {1, 2, ..., N} (4.11) 2 2 ∂Pi i + P αϕ(i) N0|hB+J i 2 i| Also, assuming E{Ri } is positive, increasing function of power within power budget i} ≥ 0, it gives Ptotal and interference limits Ith and Tj , (∀j), i.e. ∂E{R ∂Pi ∂L ≤ ∂Pi αϕ(i) 1 N0 B+Ji |hi |2 ∀i ∈ {1, 2, ..., N} (4.12) + Pi We again assume, that zero power invested gives no loss, i.e L(0) = 0. As we discussed in section 3.3.1, choosing a common average loss function for all subcarriers which satisfies all desired properties is difficult, so we consider a special case of linear rate ∂2L loss in the next section. Linear function will satisfy (4.11) as in this case ∂P 2 = 0 for i all subcarriers. 41 Chapter 4. Power allocation for Interference Constrained OFDM-CR system 4.3.2 Optimal Power allocation for Interference-limited OFDM-CR system with Linear Rate Loss We defined a linear rate loss in section 3.3.2 as follows: L(p) = Cp where C is normalized average cost per unit power for the secondary user to allocate resources and carries units bits/s/W. Also C is chosen such that it satisfies (4.12) for all subcarriers. If P is the power allocation vector as defined in section 3.3.2, the optimization problem for this interference-limited model can be written as follows: N P∗ = arg max P ln 1 + i=1 |hi |2 Pi N0 B + Ji − αϕ(i) CPi (4.13) subject to Pi ≥ 0 ∀i ∈ {1, 2, ..., N} M N Sj = j=1 (4.14) Pi ≤ Ptotal (4.15) i=1 Sj ≤ Tj and ∀j ∈ {1, 2, ..., M} (4.16) N Ki Pi ≤ Ith (4.17) i=1 Proposition 2. There is power allocation vector P which is a solution to the optimization problems defined by (4.13,4.14,4.15,4.16,4.17) and it is of the form Pi∗ N0 B + Ji = wi − |hi |2 + ∀i ∈ {1, 2, ..., N} (4.18) where wi is the subcarrier threshold level, determined as follows: Assume A {j|Sj < Tj }, B {j|Sj = Tj } 42 Chapter 4. Power allocation for Interference Constrained OFDM-CR system 1: Assign wi = wi = 1 αϕ(i) C 1 γϕ(i) + αϕ(i) C ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ A (4.19) ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ B (4.20) where γj > 0, ∀j ∈ B is determined by the following |B| equations Pi∗ = Tj ∀j ∈ B (4.21) i s.t φ(i)=j If the solution to above equations Pi∗ exists and satisfies N ∗ i=1 Ki Pi < Ith , then it is optimal. N i=1 Pi∗ < Ptotal and 2: Assign 1 λ + αϕ(i) C 1 wi = λ + γϕ(i) + αϕ(i) C wi = ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ A (4.22) ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ B (4.23) where λ > 0 and γj > 0, ∀j ∈ B are determined by the following |B|+1 equations N Pi∗ = Ptotal (4.24) i=1 Pi∗ = Tj ∀j ∈ B (4.25) i s.t φ(i)=j If the solution to above equations Pi∗ exists and satisfies it is optimal. N i=1 Ki Pi∗ < Ith , then 3: Assign 1 δKi + αϕ(i) C 1 wi = δKi + γϕ(i) + αϕ(i) C wi = ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ A (4.26) ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ B (4.27) 43 Chapter 4. Power allocation for Interference Constrained OFDM-CR system where δ > 0 and γj > 0, ∀j ∈ B are determined by the following |B|+1 equations N Ki Pi∗ = Ith (4.28) i=1 Pi∗ = Tj ∀j ∈ B (4.29) i s.t φ(i)=j If the solution to above equations Pi∗ exists and satisfies it is optimal. N i=1 Pi∗ < Ptotal , then 4: Assign 1 λ + δKi + αϕ(i) C 1 wi = λ + δKi + γϕ(i) + αϕ(i) C wi = ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ A (4.30) ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ B (4.31) where λ > 0, δ > 0 and γj > 0, ∀j ∈ B are determined by the following |B| + 2 equations N Pi∗ = Ptotal (4.32) Ki Pi∗ = Ith (4.33) i=1 N i=1 Pi∗ = Tj ∀j ∈ B (4.34) i s.t φ(i)=j If the solution to above equations Pi∗ exists then it is optimal. Proof. See Appendix B As we could notice from Preposition 2, the optimal power allocation divides the sub-channels in two different sets: set A for which the allocated power is strictly smaller than corresponding sub-channel power constraint and set B, where the allocated power is equal to the corresponding per sub-channel power constraint. Also Preposition 2 states that there could be four different scenarios under which power is allocated to different sub-carriers. We see from cases 1 and 2, as long we are strictly 44 Chapter 4. Power allocation for Interference Constrained OFDM-CR system below the threshold limit Ith for some Ptotal , the power allocation is quite similar to sub-channel water-filling with a common water level for sub-channels in set A and different water levels for different sub-channels in set B. The water level/threshold level is case 1 is the highest compared to rest other cases and this case is the easiest to solve. In cases 3 and 4, the power allocation is no longer water-filling in any form and every sub-carrier i has an individual subcarrier threshold level wi . Case 4 though is highly unlikely due to the random nature of Ki values but we do not rule out this case altogether. Looking at the structure of optimal solution from Preposition 2, we could easily deduce that finding an optimal solution involves high computational complexity. In the worst case (as in case 4), we might have to solve M + 2 non-linear equations to solve for variables γj , λ and δ. Non-linearity is introduced mainly due to αj C term in the denominator of the each subcarrier threshold level. Another difficult problem is to find a best partition of the sub-channels into set A and B. If we use exhaustive search, we may require up to 2M number of iterations and each iteration running all four cases. Due to these computational issues, we need suboptimal algorithms to find power allocation which is close to optimal solution. 4.4 Suboptimal Techniques If we take a careful look at the optimal solution, we could observe an intuitive idea behind optimal solution. Those subcarriers which are closer to PU bands have higher Ki values, hence they cause higher amount of interference to the side by side PU bands. Therefore such subcarriers should have less power allocated in order to avoid any harmful interference caused to PU users. Also, those sub-channels which have higher PU activity (or higher αj value) have a lower power level compared to other subcarriers. Therefore, heuristic approaches have to be designed in way to follow these simple analogies of optimal solution. The authors in [18] have proposed a ladder based allocation algorithm. In the last chapter we proposed a suboptimal relative water level algorithm. Also the authors in [19] have proposed iterative partitioned water-filling algorithm. So for our joint model, if we combine all three we could have a plausible suboptimal algorithm. 45 Chapter 5 Future Work and Conclusions 5.1 Future Work Since the CR network is a very dynamic environment, design and performance evaluation of the spectrum allocation and power adaptation algorithms, which are capable of learning dynamically is of prime importance. In future, the objective is to extend our approach to game theoretic analysis of the dynamic spectrum allocation problem and to design algorithms that are capable of learning and evolving. Another goal of future research will be to develop efficient auction mechanisms which are useful when there is a central server distributing the resources without sharing the information of users amongst each other. Typically in such scenario users bid to obtain the resources with respect to their physical constraints and utilization limits. An important goal of development of such algorithms is not only maintaining fairness but also maximizing overall system throughput. Also in future we plan to extend our modified proportional fairness criterion for OFDM-CR systems. As we learned that classical subcarrier allocation and bit and power loading algorithms, e.g. uniform power loading and water-filling algorithms, are inefficient and may result in higher mutual interference to the primary users. The goals of the future research will be to devise efficient suboptimal schemes keeping the interference limit low for the joint interference-limited model we proposed in Chapter 4. We will study the effect of subcarrier nulling mechanism as discussed in [17, 18]. Also we plan to do a comparative evaluation of suboptimal and optimal schemes for this joint model for OFDM-CR system. Future work also includes analysis and solutions for piecewise linear and logarithmic loss functions which may be dependent on subcarrier channel gain. Another objective will be to devise and analyze more efficient subcarrier allocation, power and rate adaptation algorithms for multiuser OFDM-CR systems which will maximize the capacity of the SU users while keeping the interference introduced 46 Chapter 5. Future Work and Conclusions to the primary users band within the tolerable range. We will extend the multiuser problem for both socio-optimal and non-cooperative cases. We also plan use concepts of coalition game theory to devise cooperative schemes for power allocation. 5.2 Conclusion In chapter 2, we looked at the problem of dynamic sharing with respect to fairness criterion. We considered device coordinated systems, where fairness plays an important role. In particular, we looked at the proportional fairness criterion. We proposed and discussed a simple modified version of proportional fair algorithm for cognitive radio systems. We stated the different controls possible possible for our algorithm, namely time control, utility control and both time/utility control. We discussed the application of the algorithm for both centralized and decentralized systems. We also discussed the possible extension of our algorithm for variable but discrete time slot lengths and then for multicarrier OFDM based cognitive radio networks based on this. We simulated our algorithm for a simple system and discussed the outcomes of simulations for all the three viable controls. We approached the power allocation problem for OFDM-CR networks in Chapter 3 taking into account reliability of available channels which depends on primary user activity. We introduced a risk-return model to incorporate the sub-channel availability by defining an average rate loss function in presence of a primary user. The advantage of this model is that it takes into account channel reliability based on primary user activity for power allocation which was not considered in [17, 19]. Owing to complex nature of the optimal solution, we also suggested two suboptimal schemes and compared their performance with respect to water-filling and optimal schemes. We briefly discussed the linearity of loss function and defined upper bounds on linear coefficients. As an extension of this work, we found an optimal solution to a joint model which combines other power allocation schemes for CR networks ([17–19]) in Chapter 3. We hence extended our model to a interference limited OFDM-CR network. Finally we suggested some possible suboptimal techniques for this joint model. 47 Bibliography [1] Ian F. Akyildiz, Won-Yoel Lee, Mehmat C. Vuran and S. Mohanty, “NeXt generation/dynamic spectrum access/cognitive radio wireless networks: A survey”, in Computer Networks Journal (Elsevier), September 2006. [2] FCC frequency spectrum inventory table: http://www.fcc.gov/oet/info/database/spectrum. [3] J. Mitola III, “Cognitive Radio: An Integrated Agent Architecture for Software Defined Radio”, PhD Dissertation, Royal Institute of Technology (KTH), Sweden, May 2000. [4] FCC. Et docket no. 03-322. “Notice of Proposed Rule Making and Order”, Dec. 2003. [5] V. K. Bhargava, and E. Hossain, Cognitive Wireless Communication Networks, Springer, 2007. [6] S. Haykin, “Cognitive Radio: Brain-Empowered Wireless Communications”, IEEE Journal of Selected Areas in Communications, vol. 23, no. 2, pp. 201-220, Feb 2005. [7] F.P. Kelly,“Charging and rate control for elastic traffic”, Eur. Trans. Telecommun., vol. 8, pp. 33-37, 1997. [8] F.P. Kelly, A.K. Maulloo and D.K.H. Tan,“Rate control in communication networks:shadow prices, proportional fairness and stability”, Journal of the Operational Research Society, vol. 49, pp. 237-252, 1998. [9] H. Kim, K. Kim, Y. Han, and S. Yun, “A proportional fair scheduling for multicarrier transmission systems,” Vehicular Technology Conference (VTC), 2004, vol.1, pp. 409-413, Sept. 2004. 48 Bibliography [10] J. Huang, R. Berry, and M. Honig, “Auction-based Spectrum Sharing”, ACM/Springer Journal of Mobile Networks and Applications (MONET) special issue on WiOpt’04, vol. 11, no. 3, pp. 405-418, June 2006. [11] Duo Zhang and Zhi Tian, “Adaptive Game-based Radio Spectrum Allocation in Doubly Selective Fading Channels”, Proc. of ICC., Glasgow, Scotland, June 2007. [12] R. Etkin, A. Parekh, and D. Tse, “Spectrum Sharing for Unlicensed Bands”, Proc. of IEEE DySPAN, pp. 251-258, Nov. 2005. [13] J. Acharya and Roy D. Yates, “A Framework for Dynamic Spectrum Sharing between Cognitive Radios”, Proc. of ICC., Glasgow, Scotland, June 2007. [14] K. Zhou and Y.H. Chew, “On the Dynamic Allocation of Frequency Bands to Secondary Users”, Proc. of IEEE GLOBECOM, pp. 1-5, Nov. 2006. [15] Jun Zhao, Haitao Zheng, and Guang-Hua Yang, “Distributed coordination in dynamic spectrum allocation networks”, Proc. of IEEE DySPAN, pp. 259-268, Nov. 2005. [16] D. Tse and P. Vishwanath, Fundamentals of Wireless Communications, Cambridge University Press, 2005. [17] G. Bansal, J. Hossain, and V. K. Bhargava, “Adaptive power loading for OFDMbased cognitive radio systems,” in Proc. of IEEE ICC’07, pp. 5137-5142, June 2007. [18] G. Bansal, J. Hossain, and V. K. Bhargava, “Adaptive power loading for OFDMbased cognitive radio systems,” to appear in IEEE Transactions on Wireless Communications, 2008. [19] P. Wang, M. Zhao, L. Xiao, S. Zhou, and J. Wang, “Power allocation in OFDMbased cognitive radio systems,” in Proc. of IEEE Globecom’07, pp. 4061-4065, Nov. 2007. [20] T. Weiss, J. Hillenbrand, A. Krohn, and F. K. Jondral, “Mutual interference in OFDM-based spectrum pooling systems,” in Proc. of IEEE VTC, vol. 4, pp. 1873-1877, May 2004. 49 Bibliography [21] T. Weiss, and F. K. Jondral, “Spectrum pooling: an innovative strategy for the enhancement of spectrum efficiency”, IEEE Communication Magazine, vol. 43, no. 3, pp. S8-S14, Mar 2004. [22] D. P. Palomar, and J. R. Fonollasa, “Practical algorithms for a family of waterfilling solutions,” IEEE Transactions on Signal Processing, vol. 53, no. 2, pp. 686-695, Feb. 2005. [23] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. [24] Dimitri P. Bertsekas Nonlinear Programming, Athena Scientific, 2003. 50 Appendix A Proof of Proposition 1 This is a convex optimization problem and could be solved using standard Lagrange multipliers method. Using multipliers µi for inequality constraints in (3.13) and λ for equality constraint in (3.14), we can write the Karush-Kuhn-Tucker (KKT) [23] conditions as follows: N Pi∗ = Ptotal i=1 Pi∗ ≥ 0 ∀i ∈ {1, 2, ..., N} µi ≥ 0 ∀i ∈ {1, 2, ..., N} µi Pi∗ = 0 ∀i ∈ {1, 2, ..., N} 1 + αϕ(i) C − µi + λ = 0 + Pi∗ |hi |2 ∀i ∈ {1, 2, ..., N} − N0 B (A.1) We can eliminate µi from (A.1) and rewrite the KKT conditions as follows: N Pi∗ = Ptotal i=1 Pi∗ ≥ 0 1 λ + αϕ(i) C ≥ N0 B + Pi ∗ |hi |2 Pi∗ λ + αϕ(i) C − N0 B |hi |2 1 + Pi ∗ =0 ∀i ∈ {1, 2, ..., N} ∀i ∈ {1, 2, ..., N} ∀i ∈ {1, 2, ..., N} (A.2) 51 Appendix A. Proof of Proposition 1 Now if λ + αϕ(i) C < |hi |2 , N0 B the third condition in (A.2) can hold if Pi∗ > 0 which implies Pi∗ = 1 N0 B − λ + αϕ(i) C |hi |2 (A.3) |hi |2 , then Pi∗ > 0 is not possible because this would imply N0 B 1 , violating the fourth condition. Therefore, the only N0 B +Pi ∗ |hi |2 this case is Pi∗ = 0. Also if λ + αϕ(i) C ≥ |hi |2 > λ + αϕ(i) C ≥ N 0B solution possible in Combining the above results, the solution can be rewritten as Pi∗ 1 λ+αϕ(i) C = 0 − N0 B |hi |2 if λ + αϕ(i) C < if λ + αϕ(i) C ≥ |hi |2 N0 B |hi |2 N0 B (A.4) which is equivalent to Pi∗ 1 N0 B = − λ + αϕ(i) C |hi |2 + ∀i ∈ {1, 2, ..., N} (A.5) and the constant λ can be obtained by the equality constraint in (3.14) as follows: N i=1 N0 B 1 − λ + αϕ(i) C |hi |2 + = Ptotal (A.6) 52 Appendix B Proof of Preposition 2 We can rewrite the optimization problem as follows: N ∗ P = arg min P αϕ(i) CPi − ln 1 + i=1 |hi |2 Pi N0 B + Ji (B.1) subject to Pi ≥ 0 ∀i ∈ {1, 2, ..., N} (B.2) N Pi ≤ Ptotal (B.3) Ki Pi ≤ Ith (B.4) i=1 N i=1 (B.5) and Sj ≤ Tj ∀j ∈ {1, 2, ..., M} (B.6) where Sj is given by Sj = Pi (B.7) i s.t φ(i)=j We now use convex optimization theory [23] to solve this optimization problem. Using Lagrange multipliers µi for inequality constraints in (B.2), λ for inequality constraint (B.3), δ for inequality constraint (B.4) and γj for inequality constraint (B.6), the Karush-Kuhn-Tucker (KKT) conditions will include equations (B.2,B.3,B.4,B.6) with optimum solution Pi∗ and the following equations: 53 Appendix B. Proof of Preposition 2 µi ≥ 0 ∀i ∈ {1, 2, ..., N} (B.8) λ≥0 (B.9) δ≥0 (B.10) γj ≥ 0 ∀j ∈ {1, 2, ..., M} (B.11) µi Pi∗ = 0 ∀i ∈ {1, 2, ..., N} (B.12) N λ( Pi∗ − Ptotal ) = 0 (B.13) Ki Pi∗ − Ith ) = 0 (B.14) i=1 N δ( i=1 γj (Sj − Tj ) = 0 ∀j ∈ {1, 2, ..., M} (B.15) and 1 − N0 B+Ji |hi |2 + Pi∗ + αϕ(i) C − µi + λ + δKi + γϕ(i) = 0 ∀i ∈ {1, 2, ..., N} (B.16) We can rewrite (B.16) as follows µi = λ + δKi + γϕ(i) + αϕ(i) C − 1 N0 B+Ji |hi |2 + Pi∗ (B.17) Substituting (B.17) into (B.8) and (B.12), we can eliminate µi , which yields λ + δKi + γϕ(i) + αϕ(i) C ≥ 1 N0 B+Ji |hi |2 λ + δKi + γϕ(i) + αϕ(i) C − + Pi∗ 1 N0 B+Ji |hi |2 Now if λ + δKi + γϕ(i) + αϕ(i) C < + Pi∗ |hi |2 , N0 B+Ji Pi∗ = 0 ∀i ∈ {1, 2, ..., N} (B.18) ∀i ∈ {1, 2, ..., N} (B.19) then (B.18) can hold only if Pi∗ > 0, which from equation (B.19) gives, Pi∗ = 1 N0 B + Ji − λ + δKi + γϕ(i) + αϕ(i) C |hi |2 (B.20) 54 Appendix B. Proof of Preposition 2 2 i| On the other hand, if λ + δKi + γϕ(i) + αϕ(i) C ≥ N0|hB+J then Pi∗ > 0 is not possible as i it would violate (B.19). So Pi∗ = 0 is the only solution in this case. Combining these results, the solution can be rewritten as follows: Pi∗ = 1 λ+δKi +γϕ(i) +αϕ(i) C − 0 N0 B+Ji |hi |2 if λ + δKi + γϕ(i) + αϕ(i) C < if λ + δKi + γϕ(i) + αϕ(i) C ≥ |hi |2 N0 B+Ji |hi |2 N0 B+Ji (B.21) which is equivalent to Pi∗ where wi = N0 B + Ji = wi − |hi |2 1 , λ+δKi +γϕ(i) +αϕ(i) C + ∀i ∈ {1, 2, ..., N} (B.22) is defined as subcarrier threshold level. Next, in order to determine the values of λ, δ, and γj we first divide the sub-channels in two sets A and B such that if (i) Sj < Tj , then j ∈ A and if (ii) Sj = Tj , then j ∈ B. Depending upon the constraints, either of these sets could be empty. Now for any j ∈ A, since Sj < Tj , equation (B.15) suggests γj = 0. Similarly, for j ∈ B, since Sj = Tj , (B.11,B.15) leads to γj ≥ 0. We observe from the equations (B.13,B.14), any value λ > 0 or δ > 0 demands the equality sign for the constraint equations (B.3) and (B.4) respectively. Also we notice that each Pi∗ is maximum when either λ = 0 or δ = 0 compared to case when λ > 0, or δ > 0 respectively. So if we are unable to satisfy equality for the constraint equations (B.3) and (B.4) for any positive values for λ or δ, then we should set largest possible Pi∗ (larger Pi∗ makes each inequality tighter, since Ki > 0) which suggests either λ = 0 or δ = 0 or both depending on the constraint equations. This leads to four possible cases, Case 1: λ = 0 and δ = 0 Let us assign wi = wi = 1 αϕ(i) C 1 γϕ(i) + αϕ(i) C ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ A (B.23) ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ B (B.24) where γj , ∀j ∈ B is determined by the following |B| equations 55 Appendix B. Proof of Preposition 2 Pi∗ = Tj ∀j ∈ B (B.25) i s.t φ(i)=j ∗ If the solution to above equations Pi∗ exists and satisfies N i=1 Pi < Ptotal and N ∗ ∗ i=1 Ki Pi < Ith , then this suggests λ = 0, δ = 0 and Pi is the optimal solution. Case 2: λ > 0 and δ = 0 Let us assign 1 λ + αϕ(i) C 1 wi = λ + γϕ(i) + αϕ(i) C wi = ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ A (B.26) ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ B (B.27) where λ and γj , ∀j ∈ B are determined by the following |B| + 1 equations N Pi∗ = Ptotal (B.28) i=1 Pi∗ = Tj ∀j ∈ B (B.29) i s.t φ(i)=j If the solution to above equations Pi∗ exists and satisfies N i=1 Ki Pi∗ < Ith , then this suggests δ = 0 and Pi∗ is the optimal solution. Case 3: λ = 0 and δ > 0 Let us assign 1 δKi + αϕ(i) C 1 wi = δKi + γϕ(i) + αϕ(i) C wi = ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ A (B.30) ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ B (B.31) 56 Appendix B. Proof of Preposition 2 where δ and γj , ∀j ∈ B are determined by the following |B| + 1 equations N Ki Pi∗ = Ith (B.32) i=1 Pi∗ = Tj ∀j ∈ B (B.33) i s.t φ(i)=j If the solution to above equations Pi∗ exists and satisfies this suggests λ = 0 and Pi∗ is the optimal solution. N i=1 Pi∗ < Ptotal , then Case 4: λ > 0 and δ > 0 Let us assign 1 λ + δKi + αϕ(i) C 1 wi = λ + δKi + γϕ(i) + αϕ(i) C wi = ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ A (B.34) ∀i ∈ {1, 2, ..., N} such that ϕ(i) ∈ B (B.35) where λ, δ and γj , ∀j ∈ B are determined by the following |B| + 2 equations N Pi∗ = Ptotal (B.36) Ki Pi∗ = Ith (B.37) i=1 N i=1 Pi∗ = Tj ∀j ∈ B (B.38) i s.t φ(i)=j If the solution to above equations Pi∗ exists then that is the optimal solution. Clearly, if there is solution which falls in the category of any of the four cases, it would satisfy all KKT conditions. Due to strict concavity of the objective function there will be a unique solution. This completes the proof of Proposition 2. 57
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Dynamic resource allocation for cognitive radio systems
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Dynamic resource allocation for cognitive radio systems Hashmi, Ziaul Hasan 2008
pdf
Page Metadata
Item Metadata
Title | Dynamic resource allocation for cognitive radio systems |
Creator |
Hashmi, Ziaul Hasan |
Publisher | University of British Columbia |
Date Issued | 2008 |
Description | Cognitive Radio (CR) is considered to be a novel approach to improve the underutilization of precious radio resources by exploiting the unused licensed spectrum in dynamically changing environments. Designing efficient resource allocation algorithms for dynamic spectrum sharing and for power allocation in OFDM-CR networks is still a challenging problem. In this thesis, we specifically deal with these two problems. Dynamic spectrum sharing for the unlicensed secondary users (SU)s with device coordination could minimize the wastage of the spectrum. But this is a feasible approach only if the network considers the fairness criterion. We study the dynamic spectrum sharing problem for device coordinated cognitive radio networks with respect to fairness. We propose a simple modified proportional fair algorithm for a dynamic spectrum sharing scenario with two constraints, time and utility. Utility is measured by the amount of data processed and time is measured as the duration of a slot. This algorithm could result in variable or fixed length time slots. We will discuss the several controls possible on the algorithm and the possible extension of this algorithm for multicarrier OFDM based CR systems. Traditional water-filling algorithm is inefficient for OFDM-CR networks due to the interaction with primary users (PU)s. We consider reliability/availability of subcarriers or primary user activity for power allocation. We model this aspect mathematically with a risk-return model by defining a general rate loss function. We then propose optimal and suboptimal algorithms to allocate power under a fixed power budget for such a system with linear rate loss. These algorithms as we will see allocate more power to more reliable subcarriers in a water-filling fashion with different water levels. We compare the performance of these algorithms for our model with respect to water-filling solutions. Simulations show that suboptimal schemes perform closer to optimal scheme although they could be implemented with same complexity as water-filling algorithm. We discuss the linearity of loss function and guidelines to choose its coefficients by obtaining upper bounds on them. Finally we extend this model for interference-limited OFDM-CR systems. |
Extent | 588031 bytes |
Subject |
Cognitive radio Wireless communications Algorithms |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2008-06-27 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0066457 |
URI | http://hdl.handle.net/2429/961 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2008-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2008_fall_hashmi_ziaul.pdf [ 574.25kB ]
- Metadata
- JSON: 24-1.0066457.json
- JSON-LD: 24-1.0066457-ld.json
- RDF/XML (Pretty): 24-1.0066457-rdf.xml
- RDF/JSON: 24-1.0066457-rdf.json
- Turtle: 24-1.0066457-turtle.txt
- N-Triples: 24-1.0066457-rdf-ntriples.txt
- Original Record: 24-1.0066457-source.json
- Full Text
- 24-1.0066457-fulltext.txt
- Citation
- 24-1.0066457.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0066457/manifest